Mapping demographic data, aggregated by geographic regions

Bit of a post for the Dutch, but you may have some data that is similarly detailed and cool (AND FREE!)... Together with a colleague I've been working on mapping demographic data of Holland on Google Maps for marketing purposes. The result is here:


There is a data dump from the CBS that you should be able to find with Google called "Districts and Neighborhoods" or "Wijken en Buurten". This data contains some demographic data about a region ( municipality, district and down to neighborhood ), as counted by the CBS. As well, there is a data set called "Core figures", which translated to "kerncijfers" also supplied by the CBS.

The core figures go down to the postal code level, which does two things:

• Finer grained information than you already have (which is not very useful for marketing purposes)
• Establish a correlation between postal code and the neighborhood it is in, thus allowing you to map groups of people to neighborhood level, which is probably a good aggregation level for marketing.

The district- and neighborhood data is delivered in the form of ESRI shape files. This allows you to convert the data into Well Known Binary format (WKB) using the shp2pgsql utility. This builds a table from the data in the SHP file and outputs this into sql into a file. Then you can simply < href="http://code.google.com/eclipse/docs/getting_started.html">Google plugin) + Hibernate. To be able to query the postgis database, you need the vivid solutions extensions.

Then I use a query to get the polygons out that I need through the postgis query API:

String wktFilter = getFilter( bounds );
WKTReader fromText = new WKTReader();
Geometry filter = null;
try{
filter = fromText.read(wktFilter.toString());
filter.setSRID( -1 );
} catch(ParseException e){
throw new RuntimeException("Not a WKT String:" + wktFilter);
}

Session s = HibernateUtil.currentSession();

Criteria testCriteria = s.createCriteria(Buurt.class);
testCriteria.add(SpatialRestrictions.intersects("theGeom",filter));
List buurten = testCriteria.list();

As such, I get the neighborhoods or other regions back that I want, based on my Google maps viewport :). That's already an important step, but doesn't finish there. Since the data in the Wijken en Buurten is RijksDriehoeksmeting (RD), it needs to be converted to the Datum that Google Maps uses. They're using WGS-84, a datum, which is basically a geoïd generally used for (probably) older GPS's. I'm using this code for now to convert between the two:

public static double[] rdtowgs( double X, double Y ) {
double dX = (X - 155000) * Math.pow( 10 , -5 );
double dY = (Y - 463000) * Math.pow( 10 , -5 );
double SomN = (3235.65389 * dY) + (-32.58297d * Math.pow( dX, 2)) + (-0.2475d * Math.pow( dY, 2)) + (-0.84978d * Math.pow( dX, 2) * dY) + (-0.0655d * Math.pow( dY, 3)) + (-0.01709d * Math.pow( dX, 2) * Math.pow( dY, 2)) + (-0.00738d * dX) + (0.0053d * Math.pow( dX, 4)) + (-0.00039d * Math.pow( dX, 2) * Math.pow( dY, 3)) + (0.00033d * Math.pow( dX, 4) * dY) + (-0.00012d * dX * dY);
double SomE = (5260.52916 * dX) + (105.94684d * dX * dY) + (2.45656d * dX * Math.pow( dY, 2)) + (-0.81885d * Math.pow( dX, 3)) + (0.05594d * dX * Math.pow( dY, 3)) + (-0.05607d * Math.pow( dX, 3) * dY) + (0.01199d * dY) + (-0.00256d * Math.pow( dX, 3) * Math.pow( dY, 2)) + (0.00128d * dX * Math.pow( dY, 4)) + (0.00022d * Math.pow( dY, 2)) + (-0.00022d * Math.pow( dX, 2)) + (0.00026d * Math.pow( dX, 5 ));
double ret[] = new double[ 2 ];
ret[ 0 ] = 52.15517d + (SomN / 3600);
ret[ 1 ] = 5.387206d + (SomE / 3600);
return ret;
}
public static double[] wgstord( double Latitude, double Longitude ) {
double dF = 0.36d * (Latitude - 52.15517440d);
double dL = 0.36d * (Longitude - 5.38720621d);

double SomX= (190094.945d * dL) + (-11832.228d * dF * dL) + (-144.221d * Math.pow( dF, 2 ) * dL) + (-32.391d * Math.pow( dL, 3) ) + (-0.705d * dF) + (-2.340d * Math.pow( dF, 3 ) * dL) + (-0.608d * dF * Math.pow( dL, 3 )) + (-0.008d * Math.pow( dL, 2 ) ) + (0.148d * Math.pow( dF, 2 ) * Math.pow( dL, 3 ) );
double SomY = (309056.544d * dF) + (3638.893d * Math.pow( dL, 2 )) + (73.077d * Math.pow( dF, 2 ) ) + (-157.984d * dF * Math.pow( dL, 2 )) + (59.788d * Math.pow( dF, 3 ) ) + (0.433d * dL) + (-6.439d * Math.pow( dF, 2 ) * Math.pow( dL, 2 )) + (-0.032d * dF * dL) + (0.092d * Math.pow( dL, 4 )) + (-0.054d * dF * Math.pow( dL, 4 ) );
double ret[] = new double[ 2 ];
ret[ 0 ] = 155000 + SomX;
ret[ 1 ] = 463000 + SomY;
return ret;
}

So there goes that! Any data coming back from the UI needs to be converted into RD first (the bounds), before querying the data on the viewport.

We're still working on refining things, like encoded polygons and possibly some caching, but in compiled form the app is a lot quicker than in the GWT shell. At the moment we're simply forwarding the individual points, but that's not as efficient and probably not as precise. That shouldn't take too long to get done however. Well, the rest of the application is just using the Google Map Library and putting that little map on the screen. That means using the proper events, hooks and scriptlets, to use the old MS word inbetween.

The figures are from 2004 and have been slightly updated for 2006, but probably not too much. The real figures about inhabitants are from 2009 and are based on the GBA, but some effort has been made to change things where problems could ensue regarding privacy.

What's the use? Well, together with the postal code, which is often requested, or with the customer's IP through geo targeting, you can start data mining. Marketers can quite easily develop certain profiles of what they're selling. By the IP the region can be quickly discovered, which may then give clues about preferences if the person is not known otherwise by login for example (any preferences or login that you have is far more useful than this silly method of customer targeting).

Based on the region/IP/postal code, you can find out what kind of products are more likely to suit the visitor. Thus, it provides a way to adjust the web content to the person that's visiting. Any other smaller clues like the first three clicks could theoretically tell you the rest of what the person is trying to do, or why your site is visited.

Some other sites like funda.nl use similar databases, although I believe they've probably paid around 7,000 EUR for a postal database which is slightly more precise. The CBS borders are those borders established by the government.

This little thing that you see on the page is interactive, only loads what it needs based on the viewport bounds and was hacked together in 16 hours.

Can computers become conscious?

This is a post to contemplate about a paper I wrote, available here. When discussing the possibility whether machines can become conscious, reference is made towards the necessity to localize memory, cognition and all these other factors. In short, to have a discrete description of the system we call the Brain. Should we not understand it in full, then all hope is lost.

I'm taking a different view on things. "Emergence" for example shows that many, many small actions that are discrete in nature and often very simple, interact together to eventually become a massively complex system that no single, descriptive, general rule can describe. It is easy to describe the simple behaviour from a single agent, but it's impossible to understand the actions and consequences of the system as a whole. I reckon that we may not need to understand this entire system, but can start from the bottom by replicating certain behaviours and look at certain clusters in the detail that is still fathomable. Then attempt to replicate those clusters and move upwards in the chain.

Oh well, to prevent a rant on the same, on to the whitepaper then:

This whitepaper draws a comparison between Restricted Boltzmann Machines and human consciousness using a quantitative analysis of the capacity for the integration of information. The probability that computers can become somewhat conscious of their inputs is discussed. Consciousness of computers implies the capacity to interpret data, understand it, manipulate it and possibly to produce new data based on previous examples.

The same neurons activated by observation are also activated when dreaming or imagining. Restricted Boltzmann Machines work in a similar way; [....] This makes it plausible to construct computers that have some kind of imagination, [....] the type of consciousness isn't necessarily equal to our own [...]

Happy reading!

Pro log

No, I'm not in favor of forest logging. Prolog is a declarative language, part of the fifth generation of programming languages. I'm following the final course for this academic year, for which 2 assignments need to be created. The first assignment was a game basically with heuristics for intelligence. The other assignment is an artificial reasoning thing, where it needs to reason about the types of relations between countries. The questions and facts are written in natural language, then stored in alternative format in a more workable representation for the computer. It can be stored to and re-read from disk. It can also derive relations between two regions that have no direct relation declared, but because X has a relation with Y and Y has a relation with Z, the program can derive the possible relations (a set) between X and Z. It's coming along quite nicely at the moment, reasoning is pretty much working. There are some types of questions that are not entirely answered yet however, but it should be possible to complete them pretty quickly.

Both assignments had very interesting elements in them, whilst at the same time generating quite a bit of frustration. Prolog is a language where you're not necessarily directly in control of memory and so on. When programming a couple of years in procedural languages (most are: C/Java/PHP/C++/Python/Perl). Well, about Java and C++, opinions are divided. They don't necessarily call it procedural, since in smart cases it's about objects reacting to events. In my view though, a C++ class can be considered a whipped up C struct with a virtual table of function pointers (except that the compiler lacks other capabilities and the STL and so on).

Cool thing about prolog are the recursive abilities that usually accompany list manipulation. The interpreter does the backtracking basically, so you just tell the environment what you want to achieve. That's why it's declarative.

The main goal of prolog is: "achieve truth". Never forget that when programming in prolog. The only thing that the interpreter is ever trying to do is find paths and instantiations that, through the declared end-goal, achieve a "true" condition. Whenever a false condition occurs, the interpreter starts backtracking and will start to search for different combinations of instantiations and paths, basically other candidates.

The thing that is not very easy for beginners in prolog is branching. If you're used to the programming of 'if-trees', those if X then Y kind of structures, then prolog doesn't give you lots of tools to handle these. The good thing is that you start to think about many problems as a very generic problem, thus your approach to solving it also becomes very generic. The bad thing is that when you really need it, the amount of code may start to rise a bit.

Well, luckily the language allows modules and there are quite some internal predicates available for making programming easier, but it isn't yet as easy (for me) as programming Java or anything else.

Part of that, I think, is related to finding the correct approaches to doing things in a certain context, also called patterns. For prolog, the practice of programming prolog isn't very well documented or discussed, where the techniques that prolog allows has a lot of examples. The main examples are "knight's tour" and "sudoku".

Scheduling optimization is a topic that is more and more important for larger companies as well, or finding "a" best solution to a set of constraints and a configuration of entities. Think of DHL and timing of getting deliveries in time, think optimization of a pick-up route in logistics (travelling salesman?), think optimizing the order in which tasks need to be executed (and by whom?) across a set of resources, think developing the order in which ships may travel down a channel to take berth, having an anchorage at the outside.

These problems should not be under-estimated. With 3-4 or less constraints, procedural languages probably allow you to find a good solution within milliseconds. But when constraints are > 5 and it is possible that these increase, the procedural language solution becomes too complex, testing the solution is too complex and time-consuming and the confidence of the developers that the solution is *right* starts to decrease.

So, prolog can be pretty cool. It's pretty much crap for web development or general systems development, but once you get into that difficult problem with >4 constraints, have a look at it and see what it does, it's pretty powerful.

The wedding was yesterday, it was absolutely amazing. The people that were present were all very special to the couple and we had a great time to get to know one another. One of the ideas of the couple was to mark the poolside with a set of decadent towels with a W on it, for the last name of the family. Here's a great shot from the pool side.

So, the wedding took place on the roof of the middle building, overlooking the ocean. It was a well-timed, proper ceremony.


After the ceremony, of course there is a reception. And in Cancun, you'd typically do that on the beach at sunset.

And then the professional photographer was making shots of the couple.

The day ended in a dinner and dance more at the center of this resort.

Chichén Itzá

Yesterday we had the opportunity to see Chichen Itza. From the coast of Mexico in the Cancun resort zone, it takes about 2.5 hrs driving by car to get there. The road is very reasonable and easy to drive. Almost no traffic whatsoever. The scenery though is a bit boring, just trees, more trees and then some more. It's cutting straight through the jungle, if you could call it that. This is one of the trees that you see frequently with red blossoms / flowers:

There's a great ballcourt on this site as well. Ths is the largest in ancient mesoamerica:


And of course the most famous and visible monuments of them all, the temple of the feathered serpent:


I think it was really worth the drive over there, but since it's in the middle of the jungle, you need to bring lots of water and be able to walk a few meters in the heat and enormous humidity. Sweat keeps pouring down your forehead in general. Getting closer to the more remote areas like the market, things become a bit quieter what tourists and merchants is concerned. Sitting down in that area listening to the birds is a bit of a spiritual experience.

The other thing is getting back to the coast :). There are two roads that both have the same number 180 and it's not always clear which is which. The old 180 road goes through all little towns and takes you into the center of Cancun. I don't think you want to go there. When you exit the site, don't take the 180 road directly to Cancun, but go exactly the way you came through that little village, then take the road from there. You'll be saving yourself 2-3 hours of travel :).

So, yesterday after we got back late, we sat down for dinner and then joined into a large mojito party with the entire family, with dancing, music and talking. Great fun! Today I don't notice any of the drinking of yesterday and am just about to head off to the beach for some relaxation and possibly some more pictures.

Sunburn, easy day, dinner

Yesterday was a very beautiful, great day. It started with some easy time at the beach, then a lunch on the beach where they were serving barbeque, paella, etc. in an area with wooden benches and some protection from the sun. Then some time at the pool and near a caribbean restaurant. In the evening, the entire group went to a restaurant on this resort, which offered new-style mexican food. It means about 10 plates of little bites and tastes, where the plates change somewhat rapidly. This was great, it gave us an opportunity to meet some other people.

So, Heidi and Jorge invited family and friends from various parts of the US and from Brazil, Holland and the UK. I may have forgotten one there. Dinner was finished by going to the lounge bar, where some extravagant, really weird magic act was taking place. Today, we're going to Chichen Itza to see the temple and will be back in time for dinner and wedding rehearsals.

Arrival at Cancun

Well, we've arrived in Cancun, after an easy flight from MC to this place. We've had to wait just a little bit, but it's worth it if this is the place you're going:

King size bed, 16:9 TV, and a jacuzzi in the back there with a door that opens up to the swimming pool area right on the ground floor. Very, very nice all...

This whole trip is because we've been invited to a wedding party over here in Cancun. Jorge and Heidi are getting married in a couple of days and the entire party is slowly gathering to full strength, just under 40 people n total as I've heard today. The wedding itself will take place on the roof of the building, 5th floor. The roof has a glass railing, so standing there, the sea breeze goes through your hair and the sea greets you wave after wave with water that's probably been all over this world already. Just a couple of days away!

So, what's the beach like in Cancun? It's got what most beaches have... SAND! but of course, there are nice touches. Some thing I haven't seen are these types of chairs and complete setups:

These are really good things. It's a kind of mattress under a reed roof kind of thing with two chairs and a small table in the middle. There's about 15 of these or so around this area. Because of the swine flu, a lot of cancellations were made, so you're sure of a spot there every day. Oh, and of course, what's the view like on the other side? :)

Great huh? Water must be about 27 degrees, there are people walking around the entire time to serve food and drinks... And the room is just a stone-throw away if you prefer to get back to some airconditioning and cool off.

Tomorrow is probably jus going to be a lazy day, not sure if there will be another post then. There might just be a chance for us to see Chichen Itza some time this week, but that remains to be seen.

Ciudad de Mexico

Well, our day started early. I had expected to sleep really long well into the morning, but for some reason it was impossible to get some good sleep. The hotel does offer a great breakfast here in Santa Fé. It's mostly suited for business people. Santa Fé is quite new in Mexico City and is hosting a couple of high-rise buildings to support the high-tech companies that are setting up shop here. Very close by, there's the largest shopping center in MC right now, Centro de Santa Fé. It has a couple of very fashionable and expensive shops around there, e.g. a boutique of Ermenegildo Zegna, Armani, just to name a few. Anyway, after breakfast, we managed to get a taxi sorted and drove through MC on the avenue of Reforma to get to the city centre. Reforma and just before Polanco, the area in the city with fancy restaurants, expensive clubs, etc., is also the avenue with a lot of houses for government officials, embassies, you name it. So the expensive house or two can be seen on the left and right. Just after this area is the park with an auditorium and Chapultepec. Due to time constraints, we haven't been able to visit that. We arrived soon on Zolaco. It's a large plaza in the middle of the city with already some of the most well known buildings around. So take out your camera and shoot. The golden hour had just passed sadly, so lighting was already creating some difficult situations. Right on the Zocalo is the Catedral Metropolitana, the oldest cathedral of the Americas:

It's impressive. The glass in the windows is not leaded or coloured, which is a bit of a shame, otherwise it'd be great to bring a tripod next time for an High Dynamic Range session. The altar and other views are equally amazing.

The other buildings around the square are very old, this area of the city is very appealing and certainly to be recommended. You do get the occasional nagger for taxis or other tourist stuff and possibly there is some pickpocketing going on, but I don't get the idea the area is unsafe. Matter of fact, you do see a plenty of mexicans, other tourists walking with their camera in full view, walking around this area of town. Police is also in abundance.

Well, taking a little stroll from the plaza towards the west, we're passing some very old houses and streets. A tower called Torre LatinoAmericana is in the city, which goes up to 43 floors or so, built in 1957. It isn't the prettiest tower in the world :) (don't mention this blog whilst I'm up here), but it provides a superb view of the city. This also shows the immense size of it. Wherever you look, the faintest houses in the distance fade into the horizon mist. Mexico City is huge and the metropolitan region is roughly the same size of that in Sao Paulo.

And standing on top of that tower, we spotted another beautiful building just next to us, the palace of fine arts, an opera house. A place of great architecture, something to definitely see in more detail. Since we're trying to see as much as we can, we've decided to come back another era.
So we moved on through the park towards other places. I've enjoyed that little walk. There are plenty of shops, restaurants and things on the sides to grab some water or some food. Other than that, it's quite stereotypical, although I found this park to be nicer than many other parks I've seen in other metropoles/cities.

At the other end of the park was a taxi stand and since we needed to prepare for the rest of our journey, we decided to check out the shopping center in Santa Fé. This is the largest in the city now and very well developed. There are three floors spanning the entire area with everything you'd generally expect in a mall, so I won't digress too much.

We'll be travelling out to Cancun tomorrow, which I think is a bit of a shame. This city offers so much to visit and see. And if you visit the really interesting villages and temples around Mexico City as well, I'm sure it's possible to stay for at least a month. Anyway, not to worry. Can't complain about Can Cun, Can you?

unas papapas, unas pepeiras

Just arrived in Mexico City after a long 11hr flight. This was taken on the way from the airport to the hotel. Tomorrow I should have time to go around the city, take cool pictures. Tonight, just getting some good food from the restaurant over here, turn on the tele, enjoy some wine and get ready for the day tomorrow.

Haven't seen face masks around the city here, only paranoid tourists just arriving at the airport use them. Some general precautions are necessary to reduce chances of infection from the virus:

1. Don't stay around sneezing people that look sick :). Don't get into crowded areas or public transport.
2. Wash hands regularly.
3. Don't touch your face with your hands when going through public places.
4. Eat healthily and loads of vitamins. Make sure to sleep properly.

Weather in Mexico is cloudy at the moment. Actually, it's better weather in Holland at the moment... The temperature is 27 degrees or so and constant, so that's cool. Not as hot as Brazil however, plus that Recife is seaside and this is more into the country. The city is huge here, there are not too many high-rise buildings, so just like London, the city expands across the country in ridiculous proportions.

Why RBM's are so strangely weird

I'm getting quite obsessed by RBM's for some strange reason. There's a very strange simplicity to the RBM, a very elegant method for learning through contrastive divergence and a very strange ability for an RBM to model many things. The current science shows and understands that RBM's certainly have limitations, but here we go to try to expand on that.

An RBM is a very strange kind of neural network. Artificial neural networks the way we know them generally work the signal in a forward direction, but RBM's work in a forward and backward direction. In a sense, you could say that it's a little bit similar to our minds in that, when we observe something, we both use the details from the input signal to enrich the actual observations, but at the same time use the information from our experience to enrich or expect what is being observed. I reckon that if we were to only rely on the observed state, that state wouldn't nearly be as rich as our mentally induced state, which blends our experience with our observations.

Here's a video that might blow your mind or not... It's a presentation from Giulio Tononi, which I found very compelling. In this theory, it's not a search about the quantity of neurons required to become conscious, or the localization of consciousness within the brain, but it's more of a theory of the most effective organization of neurons within a network for such a network to exhibit consciousness. (text)

Here's where I paid huge attention. Apparently, having a network that has all neurons connected together is total crap. And a network that is very large and has a high number of local connections can be good at something, but it doesn't have the right properties for consciousness. The best thing is a network with specialized neurons, connected in patches, with long connections now and then to other parts of the entire mesh. Much of the work there is related to quantifying consciousness. By quantifying consciousness, and if this quantification is in step with actual consciousness, one can continue to search for more effective methods of building neural nets or machines.

The property about "patchy-ness" suggests that blindly connecting neurons together isn't the most effective way to build a network. A highly regular network makes any system act like a general on/off machine, losing its specificity of function. Neurons that are not connected enough make it work like having a number of independent classifiers, which isn't good either.

Most NN's and RBM's build their theories around having x number of neurons or elements connected evenly together with other layers and then calculate a kind of "weight" from one element to another. Putting more neurons into a certain layer generally makes the network more effective, but improvement is generally asymptotic.

I wonder whether it's possible to develop a theory, complementary to the theory of the quantity of consciousness, which perhaps as some derivative allows a neural network to shape the network itself, or whether such theories provide better rules for constructing networks. One good guess would be to do observations of biological growth and connection-shaping of a brain or simpler parts and then assess the patterns that might be evolving in the generation of such a network.

Finally, the most interesting words of the hypothesis:

Implications of the hypothesis

The theory entails that consciousness is a fundamental quantity, that it is graded, that it is present in infants and animals, and that it should be possible to build conscious artifacts.

This is a huge implication. And in order to understand it, one should go to the start of this post. Consciousness == experiencing things. As said before, it means that our observations carry detail, which are processed by itself, but which are also completed by previous experiences. Thereby, our actual experiences are not just the observations we make, but a total sum of those observations plus memories, evoked emotions, etc. In a way, you could say that what we observe causes us to feel aroused, or have some kind of feelings, and seeing similar things again at a later point in time might cause us to see the actual observations + previous experiences (memory) at the same time. It's very likely that not all experiences are actually consciously lived, in the sense that we're aware of all possibilities of experiences that we could actually experience, very likely there are many experiences just below the surface of consciousness as some kind of potential or stochastic possibility, waiting to be activated by changes in the temporal context.

For example, rapid changes in our direct observations can cause instant changes to behaviour. This implies that next to observing the world like a thought-less camera, consuming light-rays and audio waves, we're also experiencing the world as a kind of stochastic possibility. The easiest example of demonstrating this is the idea of movement, of intent, of impact and likely effect.

The phrase: "I'm standing at a train station and I see a train coming towards me" contains huge amounts of information. The recognition of the train in the first place, the experience that it's moving towards you by the train becoming larger, the knowledge that the train runs over tracks that you're standing next to, the knowledge that train stations are places where trains stop and your intent to get on the train. Just telling here how much knowledge we apply to such a simple situation demonstrates how we're accepting our consciousness as the most normal thing on earth, which it certainly is not.

Well, so why are RBM's so strange in this sense? Because old-school neural networks don't have these properties. RBM's can both recognize things, but also fantasize them back. There are certainly current limitations. In previous posts I've talked about consciousness that we shouldn't perhaps limit the definition by "consciousness == when humans think or experience". When maintaining a broader definition of consciousness, one can also consider machines or A.I.'s which are extremely effective in a very particular area of functioning and might just be consciousness in that relevant area without having any kind of consciousness of things around. The definition of consciousness here however is a dangerous one, since it shouldn't be confused with behaviour, which it certainly is not.

Food for thought...

If You Liked This, You’re Sure to Love That

An article was posted in the NY Times about the Netflix prize some time ago. It fired some new ideas that I'm investigating right now. It's related to association rule mining.

A bit of lore in data mining is the beer-diapers story. Fathers buying diapers on Thursday or Friday night also bought beer for over the weekend. This apparently caused some supermarkets to put diapers and beer closer together. So far for the lore. In every basket, there are regularities with a certain probability. If there's salad in the basket, there may be tomatoes too, or baskets with milk have a high probability that there are cereals for example.

The association rules for basket research are based on nominal properties: It's there or it's not. The problem of Netflix is more of a continuous problem... It's the question about whether there is a strong correlation, or implication with a level of confidence between ratings of different movies and each movie has five different possibilities. Also, there may be a strong correlation between 1.0f on one movie and 1.0f on the other, whilst there may be little evidence on A@5.0 -> B@4.0f. So, per rating, the support and confidence may differ. What we're trying to find for each movie/rating combination (which is 17,770*5*5*17,770*size(datatype)).

movieA@ratingX -> movieB@ratingY

The idea is also to filter out those correlations that don't have strong correlations. The biggest problem in association rule mining is memory. Because the matrix of 17,770 movies x 17,770 movies x 5 ratings (and sometimes x5 again) is a very large one, you can't really use data types that consume 4 bytes of memory, because that requires 8 GB of memory. So in my current implementation, I squeezed in a float into a single byte, thereby losing lots of precision, and then popping it back in the prediction phase. Since I got 4GB, I can just about run this.

Association rules are highly dependent on frequencies of observation. And it's necessary to take into account the frequency that movies are seen together versus the frequency that a movie is rated in isolation. The higher the ratio that movies are seen together and the stronger the observed rating combination between A and B, the better the predictive strength of the rule.

So, let's say user A rated movie 1 at a 1.0. If he also rated movie 2 at a 1.0 and there are many more users that did this, it means that the rating of movie 2 can be strongly derived from this association rule. It's also possible that many users rated 5.0 for movie 1, but a 4.0 for movie 2. Or rated 4.0 for 1 and 5.0 for 2. These correlations all suggest slightly different things. What I really wanted to do was store the confidence of these rules, but memory doesn't play nicely here and I had to think of something else.

In a sense, association rules are similar to clustering. The differences are mostly in the derivation of strong correlations between some movie A and movie B, whereas in clustering that is never determined. knn and clustering at the moment do produce better results. I'm getting 1.47 for example vs. reported results of 0.95-ish for knn and clustering approaches. Those approaches go down as far as 0.920 with improvements.

The imprecise-ness is very likely caused by incorrect filtering or imprecisions due to the memory space shortage and float compression. Pseudo-code for now looks as below. I've basically loaded all ratings twice. Once grouped by movieId (which customers rated this movie at what?) and the whole set again grouped by customerId (which movies did a customer rate at what?). The most important and wasteful array is the one that maintains compressed floats into unsigned chars (so losing loads of precision there). It's dimensioned by MAX_MOVIES, MAX_MOVIES and NUM_STARS. This means that given movie 1 in the first dimension, find out if there's a strong correlation factor for movie 2 in the second dimension, given that movie 1 was rated at x stars, where x is then another index into this huge array. The retrieved byte is then divided by 63 and 1.0f is added. Thus, each predictor is compressed into a single byte, reducing precision, but allowing everything inside a 1.5GB area of memory or so.

Having the training data twice allows one to access data very quickly. A problematic issue is how to store calculated confidence for each movie.

start:
clearMovieResultArray

for all movies i {
clearMovieConfidenceArray
clearMovieCountArray

for all customers c in i->ratings {
for all other movies k in c->ratings {
if k == m continue;
support[ k->movieId ][ i->rating[c] ][ k->rating ]++;
count[ k->movieId ][ i->rating[c] ]++;
}
}

for all movies m {
if ( freq-movies-rated-together / i->ratingCount ) <>

for all possible ratingstars j (NUM_STARS) {
for all possible ratingstars k (NUM_STARS) {
// Normalize movie support.
support[ m ][ j ][ k ] = support[ m ][ j ][ k ] / count[ m ][ j ];
float sum = 0.0f;
for ( int k = NUM_STARS-1; k >= 0; k-- ) {
support[ m ][ j ][ k ] = support[ m ][ j ][ k ] / count[ m ][ j ];
sum += support[ m ][ j ][ k ] * (k+1);
}
}
MovieResult[ i ][ m ][ j ] = (unsigned char)((sum - 1.0f) * 63 );
}
}
}

predictRating( short movieId, int custId )
{
for all movies m that this customer rated {
if support exists {
genRating = ((float)MovieResult[ m->movieId ][ movieId ][ m->Rating ] / 63 ) + 1.0f;
sum += genRating;
numSupport++;
}
}

if ( sum > 0.0f ) {
sum /= numSupport;
} else {
sum = ALL_DEFAULT_RATING;
}

if (sum > MAX_RATING) sum = MAX_RATING;
if (sum < sum =" MIN_RATING;

return sum;
}

Tikhonov Regularization

This post is about Tikhonov Regularization, which is used for statistical and predictive method. For systems where the predictions are nicely along the real values, like so:


Things are swell, because the predictions are on either side of the line. Basically, you have a good chance of finding a very good solution for this, as it looks like a well-posed problem. The (re)estimations are very regular positive and negative, yielding very good values for a linear regression of your found values, such that you can predict new values which you haven't initially trained for (for which you know the actual value).

Well, the netflix prize is facing an ill-posed problem. This basically means that there are a number of different solutions possible, or there are cases where the differences become so small, that it generates numerical instability when calculating that solution. I've basically seen this happen in some of my implementations when doing the blending.

So, what's done is that a regularization factor is introduced, which is giving penalties to larger factors, thereby conditioning the problem better (reducing the number of solutions). See an example what part of a graph might look like:

Okay, so in this case, we may have a prediction function which is pretty complicated and for a large number of values, which are actually connected to other dimensions, it's looking like this for part of the range and domain. If you'd grab this part of the graph and then try to refit this with different approaches into a better estimation overall, then chances are very high you'd have numerical instability here. Notice how many black points are below the line. The red line (the real values) are way above that. Even though the distance between the point and the line aren't necessary disturbing, when trying to do a regression on this sub-space of the graph, you'd end up with some very bad factors. It may be better to just follow the red line along the bottom a bit, because if you'd regress towards different factors, you'd get the same problem elsewhere along the road.

Now, for a little bit of philosophy, read Occam's razor. This basically states: "The simplest explanation for a phenomenon is most likely the correct explanation".

Other methods for inferring evolutionary relationships use parsimony in a more traditional way. Likelihood methods for phylogeny use parsimony as they do for all likelihood tests, with hypotheses requiring few differing parameters (i.e., numbers of different rates of character change or different frequencies of character state transitions) being treated as null hypotheses relative to hypotheses requiring many differing parameters. Thus, complex hypotheses must predict data much better than do simple hypotheses before researchers reject the simple hypotheses. Recent advances employ information theory, a close cousin of likelihood, which uses Occam's Razor in the same way.

Thus, it's better to use models with fewer parameters than it is to use models that are using many, many different parameters. Find those models which describe the problem well, then merge them together.

Back to Tikhonov... If you're also a contender in the netflix prize, check out the following source, which is heavily chopped down in complexity, improved in readability and derived from the source of linalg, which was developed by gravity. This source is not likely usable without the use of their linalg source codes, since it uses PseudoInverse.cpp for example:

Link to main.cpp

The regfactor and regfactorbias also exist in linalg and those are key towards bringing down the rmse. Remember that we potentially have numerical instability, which is why we want to introduce regularization. The regularization conditions the problem, after which better solutions are found. Better solutions provide better fits, reducing error. You'd prefer these regularization terms as close to 0.0f as possible, because when this reg term goes towards 0.00f, you'll go towards the unregularized solution of least squares regression. It'd be great to get there, but the problem itself is ill-posed, so we need some regularization at least.

I did rip out the fancy parts like cross-validation (used to find optimal values) and rmse reporting, such that you can follow the code better. In the pseudo-inverse, it's basically executing the linear least square solver.

The returned array is an array of weights, which are used to multiply with a bias of 1.0f, another weight for algo1, another for algo2... If you like, you could easily add other algorithms and this thing will give you reasonable weights in return.

Digging RBM's

Okay, so here's some little information about Restricted Boltzmann Machines as it applies to the Netflix prize. I haven't got it working perfectly yet, but getting close. The paper may be a little bit challenging to start off with, but once you get the objective right, things are essentially pretty easy. I'm referring to the paper "Restricted Boltzmann Machines for Collaborative Filtering". The picture here shows the gist of the technique of producing predictions using this method. A user can be represented by its vector. The user vector is basically per column the rating of a movie. If a movie was not rated, then that column is not used in the calculation. By using all the movies that the user rated, the 'hidden part' of the network is loaded into a certain state. This state can then be used to reproduce figures on the visible state of the network, where the missing movie ratings are. And yes, to calculate user/movie ratings, it's simply the act of calculating this rating based on the hidden state in the network. This is done by weight multiplication with the active features in the hidden part, generating the softmax units for that missing movie rating. Hopefully it should approximate what the user really rated.


So is it a neural network? Not really. This Boltzmann machine has the ability to fantasize about what something should look like, based on parts of its observation. So you can use it for various purposes, from pattern recognition to completing parts of a picture or pictures, as long as there are recurring patterns (you can't ask it to reproduce something it's never seen before). Well, at least not yet :).

The way how this thing is trained can get pretty complicated. But enter "Contrastive Divergence". This method allows the machine to be trained pretty quickly. Imagine that by the vectors at the lower part, you're multiplying each individual softmax (5 softmaxes per movie) by its individual softmax weight and then add the bias from each hidden unit to that. Each rated movie in the user vector will either contribute or diminish the activation of the hidden unit. This is the positive activation phase. By the end of this phase, the hidden layer has F units, where x are activated ( 1.0f ) and y are not activated( 0.0f ). Yes, that is thus a binary activation pattern in the simple case (not Gaussian). Sampling in this paper means:

if ( hidden_unit_value > random_value_between_0.0_and_1.0 ) {
hidden_unit_value = 1.0f;
} else {
hidden_unit_value = 0.0f;
}

As soon as the hidden layer is calculated, we now reverse the process. What if the hidden layer was already trained? Then by having the state in the hidden layer as it is now, we should be able to reproduce the visible layer. But if the hidden layer has not yet been trained, we'll soon see that there's a certain error that'll occur. And if we re-do the positive phase again after that, we'll also see differences in the hidden layer activation.

Now, here comes the beatdown of the contrastive divergence algorithm:

1. If a hidden feature and a softmax unit are on together, add 1 in the box for that observation (visible_unit_i_softmax_p_feature_j). Thus, stores the frequency that both units were on together. You probably need a 3-dimensional matrix to store this information. And this makes sense, because you also have a weight per movie per softmax per feature. And we want to train those. Let's call this matrix CDpos.
   
2. After performing the negative phase and the positive phase again, repeat this process. We store those numbers in other structures suitable for this. Thus, we now have the frequency that softmaxes and features were on together in the first positive phase and the softmaxes and hidden features that were on after one negative and one positive (but you can actually do this a number of n times, as described in the paper, after learning has progressed). The number of epochs for learning is small, the paper mentions 50. Let's call this matrix CDneg.
   
3. The learning phase basically comprises subtracting CDneg from CDpos, then updating the weight through a learning rate. Thus:
   
   W(i=movie,j=feature,p=softmax) += lrate * (CDpos - CDneg);
   
   
4. You can make this fancier by including momentum and decay as mentioned in the paper:
   
   CDinc = (MOMENTUM*CDinc)+(LRATE*cd)-(DECAY*W);
   W += CDinc;
   
   UPDATE 30/04 | This should be:
   
   CDinc = (MOMENTUM*CDinc)+LRATE * (cd - (DECAY*W));
   
   
5. The trick in the negative phase is also if you want to sample the visible vector reconstruction or not. Or do this only in the training phase and more of those decisions. I'm sampling always in the training phases, but only the hidden layer in the prediction phase.
6. In the prediction phase, I'm normalizing the softmax probabilities, then add them multiplied by their factor, then divide by 5.0f. You could also take the highest probability and then guess on that number. I chose my method, because I think it's likely more accurate in the future. It's got x probability to be a 1, y for a 2, and so forth. Thus, it's dealing with probabilities and if there's a strong pressure for a 5.0, it'll be a five. Otherwise somewhere between 4 and 5.
   

The rest of the paper are further elaborations on this model. Gaussian hidden features and conditional RBM's. Conditional RBM's basically allow the machine to also learn from missing ratings (so, rather than training just on what you have, you also train on what you don't have. Brilliant!). It also allows to use the information in the qualifying and probe set. So, the machine will know they were rated, but doesn't know to what. That is information and a great thing to add to the model.

Hope that helps!

Temporal factors in Netflix data

Well, as with many other teams, I am now looking at modeling temporal effects in the netflix data set. I'm using some home-grown SVD system based initially on funks, but quickly added some other parameters to make the RMSE sink faster. I'm now at spot 268 with 0.8975 and just re-running my machine to get lower than that with some new additions.

Time is a bit of a hurdle. But I've got some ideas to get this right. The above is based on a model that uses sub-optimal parameter settings after playing around with some other experiments. But after the run I was too lazy to run it again in the proper way.

So... I'm also going to look at user temporal differences. Here's an example of the weirdest user in the set (with the most time on his hands). Interestingly, this user, bot or agent started out with a "proper" average of 3.4055 in 2001-2002, but then suddenly started using Netflix differently. If you look for posts of a psychologist on netflix, you'll understand what I mean. Some guys like to use 1.0 as "movie has no discernible, interesting features whatsoever" ( and blockbusters may well fall into that), such that 1.0 doesn't really mean "bad", it just means not very interesting whatsoever and I switched the tele off. That basically means the user removed the 1.0-3.0 scale for himself and only uses 1.0-5.0 to indicate better than average movies.

+-------+------------+---------+------------+------------+
| count | avg_bucket | globavg | start_date | end_date |
+-------+------------+---------+------------+------------+
| 402 | 3.4055 | 1.9082 | 2001-09-23 | 2002-09-23 |
| 9698 | 2.3414 | 1.9082 | 2002-09-23 | 2003-09-23 |
| 4022 | 1.3993 | 1.9082 | 2003-09-23 | 2004-09-23 |
| 3296 | 1.1271 | 1.9082 | 2004-09-23 | 2005-09-23 |
| 235 | 1.1319 | 1.9082 | 2005-09-23 | 2006-09-23 |
+-------+------------+---------+------------+------------+

So, one of my experiments was actually to re-center the ratings around the user average using some epsilon function. The idea was that the figures in these sets mean different things, so rescaling it to the global semantics sounded like a good idea. Unfortunately, it didn't work out well at all. Maybe I'll get back to that idea later though.

Looking at the results above again and many others, I do see there's some kind of trend in people using the ratings differently. Here's another:

+-------+------------+--------+---------+------------+------------+
| count | avg_bucket | stddev | globavg | start_date | end_date |
+-------+------------+--------+---------+------------+------------+
| 3452 | 3.3566 | 0.6829 | 3.2761 | 2003-09-23 | 2004-09-23 |
| 1968 | 3.1443 | 0.5545 | 3.2761 | 2004-09-23 | 2005-09-23 |
| 191 | 3.1780 | 0.6862 | 3.2761 | 2005-09-23 | 2006-09-23 |
+-------+------------+--------+---------+------------+------------+

Again, a user who's slightly changing the habits of the use of the system. Probably, they think that there's a lot of 4's and 5' at some point, after which 2/3 become more prominent. This takes some time of course. And what about this one:

+-------+------------+--------+---------+------------+------------+
| count | avg_bucket | stddev | globavg | start_date | end_date |
+-------+------------+--------+---------+------------+------------+
| 238 | 5.0000 | 0.0000 | 5.0000 | 2004-09-23 | 2005-09-23 |
+-------+------------+--------+---------+------------+------------+

LOL. We can reasonably assume that people choose movies that they like to watch (so in general, their average should be higher than 3). But this is ridiculous :).

Another interesting thing. Netflix has told us that they've frobbed the data here and there for anonymization purposes. But watch this:

+-------+------------+------------+------------+-----------------------------------+
| count | avg_bucket | start_date | end_date | title |
+-------+------------+------------+------------+-----------------------------------+
| 5 | 4.6000 | 2001-06-21 | 2001-09-23 | Lord of the Rings: The Two Towers |
| 1 | 4.0000 | 2001-09-23 | 2001-12-21 | Lord of the Rings: The Two Towers |
| 4 | 4.5000 | 2002-03-21 | 2002-06-21 | Lord of the Rings: The Two Towers |
| 11 | 4.7273 | 2002-06-21 | 2002-09-23 | Lord of the Rings: The Two Towers |
| 33 | 4.8788 | 2002-09-23 | 2002-12-21 | Lord of the Rings: The Two Towers |
| 651 | 4.7496 | 2002-12-21 | 2003-03-21 | Lord of the Rings: The Two Towers |
| 441 | 4.8413 | 2003-03-21 | 2003-06-21 | Lord of the Rings: The Two Towers |
| 8342 | 4.4839 | 2003-06-21 | 2003-09-23 | Lord of the Rings: The Two Towers |
| 17065 | 4.3618 | 2003-09-23 | 2003-12-21 | Lord of the Rings: The Two Towers |
| 13057 | 4.3979 | 2003-12-21 | 2004-03-21 | Lord of the Rings: The Two Towers |
| 13027 | 4.4752 | 2004-03-21 | 2004-06-21 | Lord of the Rings: The Two Towers |
| 10855 | 4.4567 | 2004-06-21 | 2004-09-23 | Lord of the Rings: The Two Towers |
| 15302 | 4.5075 | 2004-09-23 | 2004-12-21 | Lord of the Rings: The Two Towers |
| 22276 | 4.4670 | 2004-12-21 | 2005-03-21 | Lord of the Rings: The Two Towers |
| 17546 | 4.4310 | 2005-03-21 | 2005-06-21 | Lord of the Rings: The Two Towers |
| 19335 | 4.4759 | 2005-06-21 | 2005-09-23 | Lord of the Rings: The Two Towers |
| 12574 | 4.5484 | 2005-09-23 | 2005-12-21 | Lord of the Rings: The Two Towers |
| 655 | 4.5603 | 2005-12-21 | 2006-03-21 | Lord of the Rings: The Two Towers |
+-------+------------+------------+------------+-----------------------------------+

Lord of the Rings, the Two Towers came out 18-12-2002 or so. Whoops. That's some 50-60 ratings (possibly more) that have dates before the production date of the movie. Thus, any team that's working with temporal effects should take that into account. The first day of rating doesn't mean much. Possibly, these dates should all be set to at least the release date of the movie first. Since the DVD's aren't immediately available on Netflix, some more time would elapse before you could see them there. Not sure how much. The DVD came out August/November 2003, but rentals probably have them sooner, somewhere in between? Let's say March or so, it's impossible to tell. In any case, the rating dates aren't really useful for temporal calculations in that case (not with any kind of precision anyway). Moreover, if you're using production year + ratings, you should thus not assume that all rating dates are after the movie production year.

Consciousness and RBM's

I was exploring some thoughts regarding the origins of consciousness. It's a huge subject to read about and certainly one that allows one to specialize in different ways on this subject. So far, I've read books from Steven Pinker, Roger Penrose, John Holland, general articles on the Internet on this topic, philosophy of mind and the likes.

The one thing that really struck me when I was watching this video, is how important the "fantasizing step" for consciousness is. Fantasizing == imagination == abstract thought and (abstract) manipulations of things seen before in order to construct something new out of past experiences.

So far, neural networks have been viewed from the perspective of recognition, not so much from reproduction of certain action. Also, most neural network activity is one-way. It's true that the learning process requires backwards propagation for weight adjustment, but the general execution phase is from input -> output, never backwards.

But RBM's have the property that they can both be used for recognition as well as production. The production phase is useful for things like prediction. Basically, prediction is all about recognizing patterns or important forces that strongly suggest that reaching a certain state or value is a higher probability than any other. This can be done by reasoning, or calculation or whatever. (see from 21:38 in the video mentioned above to see this).

Now, here comes the fun part. One could consider imagination (+innovation) to be:

• Constructing coarse solutions through reasoning (needs to have A + B not C).
  
• Filling in the blanks of generated course solutions.
  
• Backtracking over complete blanks, defining the unknown as a subproblem to resolve prior to resolving the bigger picture.

The interesting parts of these thoughts is that it provides ways for a machine to actually construct thought itself, as long as the premise is true that inputs into the machine can be represented on a very abstract, symbolic level and the machine actually has some goals to follow. Thus, given some goals, it develops subgoals, interprets the environment and constantly redefines subgoals and so forth. There are things missing here of course, but you should think at a very abstract level of representation.

Think of the mind as a huge network of connections like a RBM with different stacks, where different types of processing occur. At the neurons near the eyes, the light gets interpreted and already it contains some sort of pre-processing like edge detection and so on. The next step is to start recognizing shapes between the edges and blotches of color. What does it all mean? I highly believe that we don't nearly store as much detail as we think we do for visual processing. And 100 billion neurons isn't really that much when you think about the amount of information we're really storing, especially when parts of these neurons are contributed to specific tasks like speech production, visual recognition, speech recognition, audible signals recognition, pre-frontal cortex processing (high-level abstract thought), emotional supression / understanding, and so forth.

Now, with consciousness... what if what we're seeing really is the induction of a high-level abstract thought in the pre-frontal cortex towards the lower hierarchical layers in this huge network? Then consciousness is more or less like reliving past experiences in sound, vision, emotion and the likes. It still raises questions on where this induction starts (ghost in the machine), but this may also be explained by (random?) the inverse of the operation, namely the occurrence of a certain emotion, the observation of a visual appearance, the hearing of some sound or the smell of something.

Now, especially olfactory memory, the latter one, is interesting. By smelling freshly cut grass or other specific smells, we sometimes immediately relive experiences from our youth. This is not something that is consciously driven for example, but as of yet totally happens. This is relived not just by smelling the smell, it's a visual, audible and emotional thing as well. The interesting part in this that we seem able to steer our thoughts (concentrate) on certain parts. Steering away from certain thoughts is much more difficult (don't think of a black cat! oops, I asked you not to think of one! :).

So... here goes... can thought be seen as a loop between abstract ideas and reproductions of those abstract ideas made from previous experiences? Someone not having many experiences won't have a lot of imagination in that sense and others with loads of experiences and knowledge may be able to infer more about certain qualities and consider a range of other possibilities and options (experience).

And the other question... can this be used as a stepping stone to model thought in machines? and if possible, could we call this consciousness?

RBM's, Prolog and pictures

I'm just now looking into RBM's in an effort to apply this to the Netflix prize. I'm getting reasonable results with other methods now. My place is 435 at the moment and pretty soon, I should be under 400. RBM's are a bit more difficult to implement than I imagined, loads of factors and intricate mathematical details. Other than that, I'm not throwing away my other methods. I'd like to see how RBM's can be applied to train on residuals, otherwise known as "those hard to rate movies".

There is at least one error that won't go away and that is the fact that a user can simply decide to rate a movie off by one rating point. If that happens, the error probably ranges from 0.5 to 1.4, thus creating a large difference. There's a very large group that's pretty predictable, but most groups are quite unpredictable in their behaviour (or most ratings are).

Well, on another note. I'm now being tortured with prolog. I really like the language, but hate it at the same time, since I'm so much used to procedural programming. I keep looking for for-loops, list iterations, inserts, deletes and the likes, but prolog doesn't truly have them. There is a bit of procedurality in Prolog however, but it's mostly declarative. The bad thing is that it has a couple of tricks that you need to get used to. Especially the starting phase is tricky, but having used the tricks here and there, the thinking inside the language is developing a bit.

Oh, and I made some new pictures with the camera:

http://www.flickr.com/photos/radialmind/sets/72157616654463308/

SVD hierarchies disappointing...

I had some good expectations of putting part of the problem into an SVD hierarchy in an attempt to home in on the right ratings sooner by grouping similar users together in what I called genes and then running SVD over that, followed by another detailed SVD run afterwards that would then bring my rmse under 0.9 or so.

Images make things a lot easier to discuss. The image here shows genes, think of them as groups of similar users. The ratings of each user determines the gene that they fall in by calculation of their silhouette and similarity (standard rmse function). There are likely other methods of doing this.

Now, the trick here is that each gene is incomplete, just like the matrix, but because the users are more similar, if you pick up all the users within the gene and then interpolate the rest of its own structure using an external prediction function, the gene becomes complete and becomes more able to classify other users. At least that was the general idea. In practice it doesn't really lead to incredible results.

The problem lies in the density of the information. SVD doesn't need compression or approximation, it likes a lot of information. I reckon that SVD works a lot better once you have a more or less square matrix. 17,700 by 480,000 is a relatively square matrix in SVD perspectives. But the above isn't 480,000, it become 20 x 17,700. And therein lies the rub. The information is so much condensed across the users, that it's not very good for calculating individual numbers for SVD.

It did start me thinking on problems of asymmetry. I was considering that if there are 20 columns versus 17,700 rows, then the problem is that the columns are gaining way too much credit for each learning run (assuming the lrate and K for both are equal). That is why I think square matrices are more suited for SVD. So I also tested out some inequal numbers, just to see what would happen. I wanted the movie factors to gain more information than the gene factors, because for each rating that I'd process (100,000,000), the movie factors would get hit about 5,000 times vs. 5,000,000 for the genes. That's a factor 1, 000. So I tried setting up the learning rate and regularization factor accordingly. Movies would learn 1,000 times faster than genes, still unstable. Possibly, it should both have a very slow learning rate to be successful.

Most of these numbers are empirically determined throug experimentation and have been suggested by others as most successful. Trying slightly different numbers for movies/users doesn't really help much, the overall end result is the same or worse. So best to stick with what you have. Of course, the regularization factor K is related to the choice of learning rate, and I think it's also related to the size that the factors get. In the previous examples, I noticed that the regularization factors are about 8 times the learning rate for the svd factors, but times 50 for the bias learning rate.

So it's more or less back to the drawing table. Basically, I've noticed that SVD works much better if you use a flat starting rate, for example 3.6033 or 3.6043. Then work from there. If you initialize to the movie average, it doesn't work that well. It does make sense in a way, because using an absolute base to work from creates a stable point of reference for the entire matrix.

The best thing to do is generate my new results, open up my error analyzer and find out what else to do :). It is quite possible that there simply isn't a better solution for a single / combined algorithm other than blending 5,000 results together just to get higher on the leaderboard :).

Genetic neighbors are like k-medoids

Well, I've found some new info on the Internet whilst trying to refine my algorithms here. I'm still in the process of aligning the proper techniques to be able to run a prediction through. The next one isn't optimal still, but should carry along a couple of good improvements.

The technique I "discovered" actually already existed. That's very common, so no problem there. The application and context in which I'm using it though is very different.

In k-medoids and knn, the trick is to select a centroid or "default" that will act as the center of a determined neighborhood. In KNN, generally parameters are averaged out, as such developing an idea of a class of a certain kind that you either match or not. In k-medoids, the trick is to find out which member is the best representative of the entire set (so no averaging there). This is done by finding out the cost of swapping the center to another member.

This thing above is a measure for similarity, otherwise known as "silhouette" in k-medoids. The silhouette provides information how similar a certain data point is in comparison to its default (in my case, the gene). a(x) is the similarity of the data point to the currently allocated gene, b(x) is the similarity of the data point to the next-in-line highest similar cluster. Thus, if there is a very good match with A, but a not so good match with any other cluster, then the silhouette will tend towards 1. If the other cluster is better (doesn't happen in my case), it tends towards -1. 0 is indifferent between A and B.

Now, the trick is to initialize the clusters to some values. I'm still considering how to do this to a better ability, but I'm also considering it may not matter too much in the beginning. It's optimization. Then, set the ratings for each gene to the exact ratings of the training data of the "default" member that was selected. This probably works better when you select defaults that have a high vote count.

Then, run an algorithm that determines similarity. I'm using ((1/rmse)/sumRmse) as a dirty trick for now. It seems to work well. Then record the similarity for each cluster on each customer (so we are classifying customers here for now). Movies can also be clustered in similar ways, likely. And in that case, one could determine biases between user and movie clusters or even use a different matrix factorization module to svd between those as a "global average". Possibly the mf-values for each user / movie become lower in the second layer and hopefully, through the help of clustering, noise is reduced and the mf values for each individual user become more meaningful and less of an average.

What I'm actually doing after allocating users into clusters / genes, is that I'm using that information to complete the matrix. Not user X <-> movie Y as one big matrix, but gene X <-> movie Y. If the users are really more similar, then the error in movie average hopefully goes down if the clusters are properly populated. The movie average is then used as a focal point for further calculations.

You obviously can't use "average" values any longer, because that's already set by the global movie average, unbiased and over a single gene you could say, the entire population. Thus, we need a new, external algorithm that is able to provide those numbers. Global effects could do for now, or perhaps a matrix factorization method.

The "silhouette" calculated earlier for each user then becomes useful. If the silhouette is a measure for how "powerful" a certain user falls into a gene, then we can set a threshold which users actually contribute to that gene and which don't. If you imagine a borderline between two clusters and a lot of users on that "front", then if one doesn't filter those out, those users would pull the clusters closer together, causing frequent swaps from one cluster to the other, making it less stable (I suppose, this isn't lab tested :).

In initial tests, I came up with 10 clusters and that worked well. Calculation time then is about 20 secs or so per cycle. After 10 cycles, there's just noise generating differences, but no apparent useful changes in rmse. This was before my thresholding algorithm.

After thresholding, the rmse drops quite quickly and also stays rather fixed after about 8 cycles. This may be good or bad, I don't know. I probably need some further tests to see what happens after 64 cycles... Does it then become worse? better?

The genes are calculated with a rather discrete formula, there is no learning involved there. If there is actual training data available for a gene, that is used for averaging out, but only if the threshold for that user in the gene is high enough (it's a measure of representation of that user for that gene). Choosing an incorrect threshold kills your changes and flexbility, too low and there's instability and continuous change.

The gene contains floats, and these floats are "averages", and there are as many floats as there are movies. If any real rates were found for a movie in the gene, then those are used. If no ratings were found for a movie, then the customers within that cluster are used to make predictions (if they have high enough threshold), and those predictions are averaged.

Using this method and selecting k=24 or so, I see the rmse going down to 0.957677 or so after 10 cycles. But the changes and improvements quickly become entirely level after that. Increasing the clusters significantly increases computation time. k=10 is reasonable, k=32 is already pretty gruesome to wait for.

There is a possibility that the initiation of the clusters is horribly inaccurate and incomplete. So it's possible it needs a couple of training cycles to get to a state that it is happy with. I'm not yet sure about the movement and progress of the numbers in this case.

I'm now trying to get better results by combining this method with matrix factorization in specific groups and between groups. Thinking about it... splitting up very large results into groups that are better similar towards another as compared to the global set, it makes sense to investigate more a hierarchical ordering of movies and customers and calculate between those groups as well. However, care must be taken not to make the groups too small or too large. Too large doesn't make the group distinct enough, too small doesn't generate the momentum that the numbers need to point in the right direction :).

Before, I tried to apply the similarity rating to a certain cluster in calculations, but it is woefully inaccurate. It's not really any use taking 20% of one cluster and 80% of another, the results are mediocre. What is much more telling however is the silhouette rating. That rating is much more useful for a variety of purposes, since it is a measure how deeply allocated a user is in a certain gene.

Oh... and today my new memory arrived. Super duper 4GB to run multiple instances next to one another. Although I don't have a quad yet, so it can only effectively be 2. And beyond what I mentioned in this post, there are a multitude of other improvements I am planning before my next submission.