Supercomputing made super easy

I don't want to harp on about the same subject twice but I think what Hybrid DSP have achieved is something very significant. There are two basic problems when analysing very large datasets:

1. Writing the code correctly.
2. The performance (i.e. speed at which it runs).

The solution to the first problem is to use an easy to understand language that you are familiar with that enables you to write code at a high level. The solution to the second problem is to use the graphics card on your pc (or buy one for a couple of hundred pounds/dollars). Up until now, however, you couldn't do the two together - either you used a high level language and lost out on performance or you used a much more complicated and harder to understand language (Nvidia C) and got the performance gains from the graphics card.

Hybrid DSP's solution neatly solves this conundrum. By taking your code and compiling it into Nvidia C automatically we can have the best of both worlds. This opens up huge opportunities across a wide range of different problems especially in the field of data analysis.

For example, based on the results of the data mining competitions that I have entered, it seems inevitable that if you really want to squeeze the last ounce of accuracy from a forecasting technique you have to use machine learning approaches. These, however, have the very significant disadvantage that they almost always take a very long time to run. There isn't, though, a ready supply of GPGPU programmers available (at least not at a reasonable price point) who can convert accurately and fast working code into code for a GPGPU.

Now by using Hybrid DSP's product you can make a few minor tweaks to your existing code and get the benefits. To see just how simple it is you can read my post which contains so a description of how I converted some Kmeans code to run on the GPU. http://www.codeproject.com/KB/Parallel_Programming/UsingCudafyGPGPUProg.aspx

So what this seems to give us (according to those who do these kind of comparisons) is a computer equivalent to the world's fastest supercomputer in 1996 sitting under our desks for around $300 that can be programmed in any of the Microsoft .Net languages (used by millions of programmers around the world). Thats got to introduce some signifcant new ways of doing things and problems that can be solved.

(Just for the avoidance of any sort of doubt - I have no financial or any other relationship with Hybrid DSP except that I use their product.)

Massively parallel programming and the GPGPU

I don't often delve into the deep technicalities of programming, but I was running a model that took 4 days to finish and decided there must be a better way. The model was already optimised, running in parallel etc, so there was nothing for it but to have a go and using a graphics card to do the computation.

A quick Google suggested mixed views. Clearly in the best cases speedups of 40 or more possible, but that was after some pretty complex optimization (exactly what memory you use on the card and how you access seemed to play a big part in the gains that you get). However, 4 days was not really satisfactory.

Being a die hard .net user and not really willing to learn anything new a bit more Googling revealed a number of potential ways of automatically converting .net code to work with the graphics card. I had a look at 3 or 4 different methods and the one I chose is Cuda running on a Nvidia card (as it is by far the best supported GPGPU as far as I can tell) and Cudafy (available from http://www.hybriddsp.com/Products/CUDAfyNET.aspx (free) as it seemed the most elegant approach.

The effort wasn't too bad - Cudafy automatically translates .net code into something that can run on the graphics card so all you need to do is to figure out how to get Cudafy to work. It took about a day (I'd like to see a lot more documentation) but it worked pretty much as it claimed. - various little issues, like checking for integer overflows is switched on in the Visual Studio compiler and needs to be switched off when generating the graphics code took a bit of time to uncover but now they are sorted they will remain sorted. Hats off to Hybrid for producing a very easy to use product.

Converting your code is also pretty trivial - Provided that its written to be analysed in parallel in the first place that is. You add a variable that tells the "kernel" (sub routine in more traditional language) which thread is running the kernel and what you want each thread to do and let rip. Its possible to generate millions of threads and the graphics card will schedule them all over the multiple processors that it has available (240 in my case).

The results are amazing - my out of the box conversion (no memory optimizations or anything fancy just a default translation of my code) produced about a 20 fold increase in speed over the .net version. I reckon that by being a little bit fancy you could probably double the speed on the graphics card. - a day well spent. It will definitely become my method of choice for running large models and datasets.

Recommendation system competitions

Having met (physically) in the last month 3 people who were kind enough to say that they read my blog - I reckon I ought to spend a little more time keeping it up to date.

This entry describes my efforts in the Kddcup 2011 competition in which Yahoo kindly supplied some 300m music ratings. No Netflix $1m at the end of it, but considerable kudos if you can win.

From the outset I decided to limit myself to a single method (stochastic gradient descent of "real world" models of human rating behaviour since you ask). As the only psychologist (at least who has come out so far) entering these types of competition I'm determined to try and drive through approaches based on new models of human behaviour rather than try and improve a computer science approach to the problem. In addition, I set myself the target to try and create a single model that would perform close to the ensemble methods that won the Netflix prize. (mainly I must admit because I didn't have time to try out a variety of approaches).

I guess my biggest discovery - which was enough to propel me to 5th place at one stage of the competition was that ratings are not made in isolation but are made relative to the other items being rated at the time and the ratings that they receive. So one simple effect is the anchoring effect well known to behavioural (behavioral I guess for the US) economics. i.e. if you give a high value to one rating, you are likely to give a high value to the next one regardless of how much you actually like it and vice versa. This effect can plainly be seen in the Yahoo dataset as there is a very high correlation between ratings - even when adjusting for all other effects. So unless Yahoo were feeding items to be recommended in a particular order, this would seem to provide significant support for the existence of such an effect, In fact, without knowing anything at all about preferences for different items you can achieve a score of around 24.5 rmse on the validation set simply by exploiting this fact.

In addition, there are other such anchoring type effects. As a thought experiment try rating anything on (say) 5 different criteria. The question to ponder - is did you at any stage consider the relative ratings that you gave to the different criteria rather than the absolute values. This relative effect led to the development of a series of moving average models.

Rather than trying to predict preferences in isolation of previous items, I developed a series of models that compared the moving average score and the predicted moving average of the preferences to an individual items preferences and score. So if, for example, the last 5 items had an average score of 75 and calculated preferences of 70 and the item I was trying to predict had a calculated preference of 90 then I simply multipled 75 by 90/70 (or depending on the model tried) added (90-70) to 75. The advantage of this approach is that it eliminated many of the issues to do with how preferences change over time (do they change over time? - or is it just the score you attribute to a preference that changes - it still seems an open question to me) and led to a single model score of 21.5 rmse on the validation set. - alas not translated to the same score on the test set. I think, however, that is probably better than most single models based on SVD which was the preferred approach during the Netflix competition - It was certainly better than the tests that I ran using some of the standard Netflix approaches.

Anyway with the time available I realised I couldn't catch the leader - hats off to them for a very good score almost from the outset - it will be interesting to hear what they did. So that's where I left it.

The Singularity has arrived

There is increasing talk of the possibility of a singularity where super human intelligence is created. One of the first people to suggest this was Vernon Vinge who stated in 1993
"Within thirty years, we will have the technological means to create superhuman intelligence. Shortly after, the human era will be ended." These themes have been taken up by other futurologists such as Kurzweil in his recent book "The singularity is near". Now this may seem the stuff of science fiction, but I'm not so sure.

I was struck the other day at just how "intelligent" Google was. I asked it two questions "Can I burn Leylandii (a type of wood)" and what was "Mary Hopkin's greatest hit". For both these questions the answer was contained within one of the top 3 web pages that was returned. It struck me that the ability to answer questions and return pages containing the answers is indeed a form of intelligence.

Lest you need further convincing, let me ask you a question. If you were playing "Who wants to be a millionaire", would you rather a lifeline that enabled you to "ask a friend" or a lifeline that gave you 45 seconds on Google to find the answer. I'd wager that most people would prefer to ask Google.

If the knowledge of facts is important to man (what did we do at school for all those years if facts aren't important) and the definition of intelligence, then a simple test of man vs machine would be to ask a series of factual questions to an individual and to a search engine and see whether the individual can answer more questions correctly or the search engine produce the answer in (say) the top 3 web pages it returns.

I agree this isn't the Turing Test (a test to see if you can distinguish between man and machine), but it seems indisputable that Google can provide the answers to a wider range of questions than any living human being, and in one sense, therefore, is superhuman. We need to recognise that it is not necessary to ape human behaviour and human methods to create something superhuman.

Interestingly, this has not - as these authors would predict, come about as a result of some form of artificial intelligence but as the direct result of millions of individuals contributing their knowledge to a common data source (the internet) and some clever (but not that clever) data search and retrieval mechanisms. It is the record volumes of data and its accessability that has created this 'intelligence' not a fundemental breakthrough in artificial intelligence or indeed any other scientific discipline.

It also suggests that even minor improvements in data search, analysis, mining and retrieval could be of immense value when multiplied by the vast volume of data accessible through the internet. If we can improve the value of each piece of data stored on the internet even slightly by making it more relevant and accessible to the appropriate queries, when multiplied by the number of data items that exist, huge amounts of intelligence will be created.

Presented at idate 09 last week. A fascinating conference. Even a relatively new industry like online dating is in the process of being heavily challenged by new ideas. Dating sites are going to have to choose what to do next from amongst others: integrating with social networks, implementing mobile offerings, implementing personalisation techniques (the basis of my talk), implementing location based offerings etc. Constant change - standing still is not an option, prioritization is a nightmare.

It was also interesting for one other insight (at least to me). The biggest company in the online dating scene is undoubtly Google - who take a huge percentage of the total value from the industry value chain. The cost of acquisition is by far the largest cost and Google advertising is the dominant method of acquisition. I'd love for someone to crunch the numbers - my guess is that they would be astonishing.

Recommendation systems for dating

I'm very excited to announce a new spin-off from the Netflix competition. Online dating. For the last few months, I've been working with a dating expert (Nick Tsonis) to see if we can improve the way in which people find dates.

Well, our first dating recommendation system went live last month. www.yesnomayb.com Its early days to calculate whether its adding to the sum of human happiness, but first results are very, very promising. Its already taken over as the main method of finding potential dates on the site. Even with its relatively rudimentary implementation, it's preferred roughly 60/40 over the more traditional search mechanism (I'm a boy looking for a girl aged between 25-30, non-smoker etc etc).

What this suggests, in the first instance, is that when searching for hedonic items (i.e. those chosen on the basis of the pleasure they might bring (books, music, dates etc )), its very difficult to describe to a search engine exactly what you are looking for. Discovery processes based on analysing yours, and everyone elses, actual behaviour provide a better method of getting you to your desired target.

With further launches on other dating sites planned for September, October and January - we should be able to start to collect even more data on what works best in helping people find their ideal dates and, hopefully, make a sea change to the way online dating works.

Reflections on the Netflix Competition

Thanks and Congratulations

1. First and foremost to Netflix for organising such a well designed competition. It was run in an exemplary fashion throughout and should, I believe, become the model for other competitions that people might choose to run. Some of the key features that made it such a success are:

a. A clear, unambiguous target and challenging target. How a 10% target was chosen, will I suspect, remain forever a mystery but it was almost perfect - seemingly unattainable at the beginning and difficult enough so that it took almost 3 years to crack - but not so difficult as to be impossible.
b. Continuous feedback provided so one could identify whether the approaches you were investigating were going in the right direction.
c. A forum so that the competitors could share ideas and help each other (more about that later).
d. Conference sessions so competitors could meet and discuss ideas.
e. Zero entry cost (apart, of course, from the contestant's time).
f. A clear set of rules.


2. Brandyn Webb a.k.a. Simon Funk For early on giving away in complete detail one of (at the time) leading approaches to the problem, thereby opening up a spirit of co-operation between the contestants.

3. The contestants Despite the prize of a $1million dollars, the competition was conducted in a spirit of openeness and co-operation throughout with contestants sharing hints, tips and ideas in the forum, through academic papers and at the conference sessions setup to discuss approaches. This undoubtly helped us all progress, and made the process a whole lot more enjoyable.

4. And of course, the winners for driving us all forwards and keeping us targeted on trying to improve and getting to the target first. As all of us who tried, we know it wasn't easy.

Was the competition worth it?

There will, undoubtly be, some discussion about whether the science generated was worth the $1million plus untold researcher and other time trying to achieve the goal. I think the answer to this is unambiguously yes because:

a. The competition has trained several hundred, if not more, people how to properly implement machine learning algorithms on a real world, large scale dataset. I'm not sure how many people already have these skills, but I would be prepared to bet that the total pool of such ability has widened considerably. This can only be a good thing.

b. It has widened the awareness of machine learning techniques and recommender systems within the broader business community. I have had many,many requests from
businesses asking how to implement recommender systems as a result of the competition and I guess other competitors have too. The wider non machine learning community is definitely looking for new applications (see my previous posts for some examples) and this can only be good for the field as a whole.

c. It has improved the science - I leave it to the academics to argue by how much, but it is certainly true that matrix factorization techniques have been the runaway success of this competition- Marrying such techniques with real-world understanding of the problem (incorporation, for example, of date and day effects) have provided by the far the most effective single technique - Such techniques, it seems to me, now need to be applied to a much wider set of problems to test their general applicability.

d. It has gifted the research community with a huge dataset for analysis as computer scientests, statisticians and I hope, from a personal perspective, as psychologists and behavioural economists too. It was a disappointment to me that I'm still the only contestant as far as I'm aware from a social sciences background. This is, almost undoubtly, the world's largest set of data on repeated decision making and ripe for analysis. The analysis may not win the competition, but it sure should provide some insights into the way that humans make decisions.

e. It was a lot of fun. I certainly enjoyed it, and I get the impression that most of the other contestants did too.