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.

New algorithm: Genetic neighbors

I'm developing a new algorithm that I'm just testing now. I call it "genetic neighbors". It's for use in the netflix prize.

The challenge in the netflix prize is to populate a very large matrix based on 1.5-2% of given values in that matrix. Thus, about 98-98.5% of values need to be interpolated. Some people have resorted to the use of pearson correlation between users for k-nearest neighbor calculation (which in my view is misguided, since it gives a relative correlation between two users, which outside that context does not mean much). This approach attempts to create an absolute ground of reference for correlation calculations.

I was pointed to a link by a friend of mine from (now) the U.S., where it mentioned something about genetic link calculation. This approach basically assumes a set of movie ratings as a type of gene and then tries to match users on that. The neat thing is also that a user need not match a 100%, a user can match 80% with one gene and 50% with another.

The match of the user also has an effect on the formation of that gene, thus, each gene mutates based on the input of different users, according to their match with that gene. The idea is also inspired by incremental "knn", but works very differently, since it's not a relation between users, but a similarity / clustering on an absolute term within this model (the gene). The gene is considered complete in the sense that it has a prediction for each movie within the gene, it is possible to match other users against it wherever they are from. With only very little information, a user can belong to a number of different genes with different weights, such that each gene contributes to the final prediction weighted by its correlation with the user based on historical information. Mistakes will of course be made there, but the more information becomes available, it is expected that predictions become more precise.

Also, I'm experimenting with how this algorithm learns. If a user doesn't have a strong profile (relatively little ratings), then it should not contribute that much to a gene. It's also another challenge (yet again!) to find the correct parameters. I'm also relying on gradient descent for learning the genes.

The difference in this program is also the organization of the rating information. Most programs probably use a type of replicated table in the application in the form of a struct and an array. In this model however, the ratings are allocated under the user structure, which greatly improves the speed in gene calculation and genetic training and also reduces memory requirements.

Doing this cluster analysis, it's also clear to see that the users don't really fit that easily into a cluster. They're sharing some parts of one gene with parts of another gene. Setting up a gene for each individual user would be ideal, but then there wouldn't be any re-use of cluster-specific knowledge of other users.

Something to watch: FACETS

FACETS is probably one of the most interesting research projects that's taking place right now. Well, together with the LHC :). Previously, I posted on the architecture of mind. That post resembles the envisioning of a totally different kind of hardware as it would apply to (re)modeling the human brain. Well, the people at heidelberg uni are now doing this. They're constructing hardware that uses a radically different design than micro-processors. From their site:

By creating specialized digital hardware processors it might be possible to gain an advantage over microprocessor-based systems. Still, it is unlikely that this will be more than an order of magnitude, since they are based on the same technology as microprocessors: The neural circuits remain to be realised with numerical solutions of differential equations. The biggest problem lies in the fundamentals of Moore's law itself: the scaling of process technology. In the current semiconductor roadmap the progress has already slowed down. The transistor density of high-performance microprocessors is likely to increase only by a factor of 25 from 2004 to 2018. A power consumption of 300 Watts is predicted for such a hypothetical chip while the on-chip operating frequency will be in the 50 GHz range.

I've blogged before on consciousness and how this might relate to computers, and what a design could look like. And some more. And more.

Changing the hardware is extremely important and much more likely to become successful.

A large problem is still the coordination between things and the problems related to associative memory. That is, when we say "cat", we instantly recall associations related to the word, strongest first (black? kitten? dead mouse?).

Most explicit knowledge systems scan their entire memory base, or have otherwise explicitly defined boundaries around knowledge to hierarchically exclude certain pools of knowledge programmatically. Thus, a key pointing to some piece of information is not recognized as such and doesn't cause a specific part of memory to highlight. It's requiring a sweep of memory to see with which asset of knowledge it's associated.

In order to be successful in the future, I think it's necessary to find ways to prevent that, to directly find some location/pool/hierarchy where something is probably located, such that it finds a match or has the ability to locate it together with other like members.

Early morning

early morning
Originally uploaded by gtoonstra

Last week I purchased a digital SLR camera for starting to make some proper photo's. I got up early today to see how I'd do, how the camera performs and try to make some good shots. Here's one of my favs, even though the sky is horribly overlit. It's a little bit eery, somewhat mysterious. Sharpness is quite ok, could have been better with a tripod. Good division of fore, middle and background and everything.

More netflix...

In the calculation run tonight, I ran the entire algorithm with a couple of different factors. I did not manage to significantly improve my ranking, but I did manage to get closer to the probe rating by training over the entire data-set, including the probe. I'm now researching at which point data overfitting starts to occur. I reckon it is related to the learning rate and I reckon it is about after ( 50 cycles + current-feature-num ).

If you only react to the probe rmse improvements to determine to switch to the next feature, this may never become apparent. I've run a wide number of different configurations, always using probe rmse as early stopping method (once it stops improving), but now I reckon that it may be too late. I'm now looking at early stopping once the hill has been reached, but using a simple calculation (as above). I'll probably post about those results in the future.

I've noticed that as time progresses, the point of highest improvement moves backwards and you need more epochs to get there. Thus, the first feature shows improvement immediately after the first epoch, but the 10th for example only shows improvement after 16-20 epochs, also "stopping" 16-20 epochs later than the first.

I've tried squeezing out as much rmse improvement as possible by using different parameters and global effect reductions, but this results in a flat line of no more improvement after about 32 features. Actually, applying the movie/user bias global effect worsens the result significantly, so I've turned that off. Instead, I'm relying on the bias training together with the features for the moment.

Using K = 0.03f or K = 0.01f also doesn't have any effect in the long run. Actually, the weird thing is that the probe rmse for the first feature isn't really affected by it at all. Also, in the long run I'm seeing the same numbers come back.

I've also tried gradually modifying K and lrate and neither did that have any effect. Note that in all these experiments, the probe rmse is the leading thing to determine to continue or not. I used to rely on a standard MAX_EPOCH setting that switched to the next feature, where I did get differences. The following sketch is instrumental in my explanation:


The graph shows how more or less the improvements build up and decay. The x-axis shows the epochs, the y is the probe rmse improvement. The vertical dashed line is the cut-off point where training stops. Thus, it shows that whenever training is stopped at the cut-off point, it is irrelevant what the parameters are, since the area doesn't seem to change much. I should have drawn the smaller bell-curve higher, so that the surface area under it makes it clear they have the same gain in total (which in my setup now is the case).

The learning rate squeezes the bell-curve together (allowing earlier stopping), but it also makes the total result less accurate (since overshoot may occur). The K has a similar effect to learning as it holds back (regularizes) the learning. But overall it should not matter too much.

So my approach now is to find out at which point before the cut-off it is best to stop learning and move on to the next feature. My guess is that over-fitting starts occurring right after the training has passed the hill. By aligning my parameters, I'm going to try to put that hill on a predictable point, such that I can simply set a maximum epoch and then move on to the next.

Al go rhythms

Mr. Larry Freeman, see link, is a software engineer from Fremont, who has taken the time to explain the "global effects removal" technique sometimes used by contenders in the Netflix prize and reflects on a number of mathematical issues. It's quite interesting for non-academic people, since it's bite-sized pieces.

I'm already grateful for explaining and demonstrating the global effect removal technique. I've tried putting it into my implementation, but sadly could not significantly improve my ratings. As you may guess, I'm using RSVD together with bias determination á la Funk and Paterek. I'm not using any blending whatsoever.

One of the reasons it doesn't work so well is probably that my implementation already covers biases by training biases along with svd factors in the first phase. Thus, the benefit of it is greatly reduced. I do notice however that using the technique requires my factors to be severely changed. I had lambda=0.05f as suggested by Paterek for calculating the biases, but now that these have been factored out, I reckon they have to be a lot higher to prevent over-fitting.

From the first 3 iterations in the svd algorithm, I can tell how things will turn out towards the end, unless my parameters are really wrong. I've seen a very good first rate at 0.951 (lower than the netflix start average ), which only ended up in a disappointing end rate of 0.9120 (higher than my ultimate post of 0.9114).

Thing that's interesting to research is to factor in global effects into the training phase. I imagine that I'm getting better results with biases, as opposed to global effects pre-processing. That's probably because all global effects are global averages, whereas some kind of gradient descent training may be able to discern the real features and the way they influence (or seem to influence) specific people. Those features may be different from the ones identified for global features, but one thing I'd like to definitely do is use the date more. Consider ratings made on a certain day, find out how much they differed and then make predictions on the change of the date.

This is not related to the production date of the movie versus the date of rating (I think that's very difficult and probably there's no causal relationship between them). One of the tricks in this netflix competition is to find causal relationships, as they make huge differences in the outcome. (in another way, you could say that if a business rule could be developed based on a certain observation that's mostly true, then that's great discovery!).

Improving the position on the leaderboard (up to 884 from 1138)

I've been busy with some algorithm refinements after reading papers on the netflix prize. I've gotten some very gradual results, but tomorrow should come up with some very good improvements after taking out a serious bug :).

It's quite a difficult problem to understand, but with more runs and perceptions of how the runs and data behaves, you get a feel for what to do. My advice to new starters is not to tie down too much to your algorithms. Fiddling with parameters is not going to significantly improve your results. Find ways to understand the data, the crux of the problem is that your algorithm is using a very sparse matrix as a basis to predict values in those cells where no value is present. Since the matrix is only 1.5% or so full, that's not a lot of data to start from.

I'm measuring performance mostly against the probe, not against the test set. The test set is just used to train the features.

So, the difficulty of applying SVD to the netflix prize is that the matrix is extremely sparse, generating loads of inaccuracies, and also that through having such a little amount of values available, the elasticity between values doesn't develop. With elasticity, I mean that you can perceive the original matrix row by row, as similarities between movies, but also column by column, looking at users. In a full matrix, the SVD algorithm develops a much closer prediction ability, because the values allow it to approximate whatever function it is that the matrix would embody. So, one movie that has high ratings for many users could at some point drop significantly for some other "type" of users. The problem is that there's not that many measuring points to find that out.

The harder predictions are those that fall far from the average that the algorithm generally would predict. But since those perceived values are rare, the features do not really embody such strong divergence.

I actually found that the key to solving everything without the use of blending is to do more work up-front, to better approximate the actual function, such that SVD can fill in the rest. The earlier you descend down to the real values (the rmse decreases), the better it is overall.

I've also seen posts from other people where they seem to be able to leave the SVD algorithms run for 1,000 features. In my implementation, I clearly see that there's a point where it develops divergence, so the rmse increases. In my original implementation that was around 32 features, right now it's about 42 features. I've decreased learning rate and improved the parameters and surely I'll post those once I see significant improvements.

Overall, if you're not significantly changing the heart of your algorithm and do not use ridiculous parameters, this point where divergence occurs is more or less the same. But also the improvements in rmse from one feature to the other remains more or less equal. Thus, if you are seeing a pattern of 0.176155, 0.007401, 0.004668 as improvements, if your rmse is lower for another round because you improved parameters or did more work, I've found that the descent is more or less the same, thus reaching an rmse that is as low as the difference in improvement of the first feature.

Using wilder parameters (much lower learning rate or stronger regularization) can make things look really good from the start, but divergence or instability is much more likely to occur after 15-16 features or so. Thus, I'm not tweaking those parameters that much anymore, as the strength of SVD isn't so much in the parameters, it's in how things are learned and what you do before/after. The differences for good values of lrate and k are only relatively marginal.

The learning rate only affects how fast the algorithm learns. But slightly lower rates allow your rmse to descend deeper, because it realizes a better approximation of the function. I have found though that changing K throughout the svd run has some positive results. Apparently, data easily overfits and increasing the value of K gave me some good results up to feature 14, yielding instability afterwards, but that was probably due to hitting the boundaries of its effectiveness.

I've calculated that, if performance really is linear with regards to the starting rmse, I'll need to start with an rmse of around 0.8957 in order to hit the 10% mark. So, by just looking at the first feature, and assuming that this performance is linear, I can easily see the results of my changes to the algorithm.

(EDIT: See results. Still rmse was lowering, so will reproduce another run with some other small tweaks and a larger change). More tomorrow!

Chasing the Netflix prize

As I'm naturally interested in algorithms, especially when these are related to Machine Learning or Artificial Intelligence... I'm posting some results here from my research into the Netflix prize so far. My results so far are not very impressive, but I'm gaining lots of new insights into the behaviour of Machine Learning algorithms and the relations between parameters, what they do. You can see on the left an attempt at lowering the Root Mean Square Error, or RMSE. That is the key feature to reduce in the Netflix prize. RMSE is calculated as follows:

1. Predict the number that a user would rate a certain movie with one decimal accuracy.
2. Compare the predicted number with the real rating that we know (training data).
3. Multiply the error with itself (square) and add that to a sum.
4. Divide the sum of the squared errors by the number of predictions made.
5. Take the square root of that sum.

Netflix initially had a performance of 0.9514 rmse. Their challenge is to improve this by 10%, thus 0.8563 rmse.

In the picture above, you can see a blue line, which is a very potent reduction of rmse on the training set. It's actually a perfect logarithmic regression, and it follows that line perfectly. However (and I don't have sufficient probe points in red in the graph to demonstrate this), the performance on a set of data that is unknown (a probe to test against or the qualifying set) is gradually decreasing. Meaning, for data that is unknown to the algorithm (the predictions to be made) are getting worse, much worse. That means that the rmse for the probe and qualifying set is getting larger as the algorithm progresses. Thus, the training set is overfitting the parameters very heavily, yielding negative returns for the other data sets.

Looking at the projection of the red line, the rmse of the separated probe (known ratings, but excluded from the rating set) is not converging at some point. My conclusion is that I need to think of something else.

In some of my later iterations that I'm not showing here, it's interesting to see how the performance of the dataset is logarithmic, whilst the performance of the rmse on the probe/qualifying set is neither linear nor logarithmic. The start of the probe rmse is sort of linear, but possibly will become logarithmic after some time. At the moment, I'm at position 1120 on the leaderboard, but I've only touched the surface of this problem and I submitted those results based on a Matrix Factorization algorithm (MF) with only 16 features. As a comparison, some other people have submitted results using over 600 features, calculated over 120 epochs (runs for one feature) or so.

Understanding the value of Data Mining

Artificial Intelligence is quite a large area, academically speaking. Truly accessible applications for business are not so common however. Data mining may be one of them, but as a manager you should approach data mining correctly. Some people may tell you that having a data warehouse is the first pre-requisite to be able to undertake the first steps in data mining. Other managers will tell you they've gotten "SQL in their fingers" and will be able to come up with some interesting discoveries given some experimentation time. Some lucky miners have access to a large data warehouse and just run a few queries to confirm suspicions or new theories.

The thing is, data mining is not like a hobby, it's a true profession. You'll know the difference between a hobbyist and a professional when you ask them how they think about data mining. Find out if they think it's about developing a hypothesis and then testing the data against it, or whether it's discovering new truths about data. True data mining is guided by business perspective. Let someone from the business tell you where it aches or where they want to improve and then go off to find their answers. Are customer leaving? Does the business want to become more efficient in one area? What is the knowledge they lack, rather than the knowledge they want to confirm?

Data mining, to be efficient, needs a focus. It's easy to tell a company that the only way to even consider commencing in mining is having a data warehouse. Time has proven that the establishment of such a DWH is time-consuming and doesn't provide the necessary payback because half is not used.

Factor in your business goals with these requirements. What do you want to achieve? Let an expert go over these goals and consider the data flows that are needed. Then just get those data flows from wherever you can get them, load them in a database (general ETL), don't necessarily model it out, especially if you need it only once, derive your conclusions and move on if it's not giving the payback you require.

Especially in these times, managers need to be more focused on the evaluation of what provides payback and what doesn't. Don't linger around, find out which things are promising, eliminate those things that cost money.

Data mining can be very strategic also for not so established companies. Once you gather sufficient volumes of data, you can start considering it, but you definitely need expert guidance here, it's not a job that the common software engineer can get away with.

Worst of all, don't rely on anyone offering "neural networks" to tell you about things. Make sure to use proper algorithms to smooth and massage your data, so it becomes more interpretable for human beings. Graph it out, since that's the best way to visualize complex data sets. One picture is better than 5,000 numbers.

And finally, it's very, very unlikely that any data mining algorithm will tell you: "Please do A in order to achieve B". In general, data mining results require interpretation and understanding, especially understanding about its limitations.

Developing your custom kernel with qemu

I'm preparing a presentation that is hopefully going to be shown at an internal event at Sogeti. We're discussing the internals of Operating Systems. For this presentation, the intention is to compile a pre-created, very simple and basic kernel, which doesn't do much but print "Hello World!".

Well, if you're interested in doing kernel development yourself, there are plenty of resources around to help you get started. The not-so-easy thing is getting your development environment in order, so that you can actually run and debug the kernel. Here's a set of commands that help you do that. I'm using qemu as a VM emulator, gcc and nasm for development and Ubuntu as a host development system.

1. qemu-img create myos.img 32M
2. losetup /dev/loop1 ./myos.img
3. fdisk -u -C65 -S63 -H16 /dev/loop1
4. ( create a primary bootable partition across the entire disk)
5. losetup -d /dev/loop1
6. losetup -o32256 /dev/loop1 ./myos.img
7. mkfs -t ext3 /dev/loop1
8. mount -t ext3 /dev/loop1 /mnt/image
9. df -Th
10. losetup /dev/loop2 ./myos.img
11. ln -s /dev/loop2 /dev/loop
12. cd /mnt/image
13. mkdir boot
14. mkdir boot/grub
15. cd boot/grub
16. cp /boot/grub/stage1 ./
17. cp /boot/grub/stage2 ./
18. cp /boot/grub/e2fs_stage1_5 ./
19. grub
20. grub>device (hd0) /dev/loop
21. grub>root (hd0,0)
22. grub>setup (hd0)
23. grub>quit
24. vi /mnt/image/boot/grub/menu.lst
25. menu.lst:
    timeout 0
    default 0
    title minimal­kernel
    root (hd0,0)
    kernel (hd0,0)/minimal­kernel
26. rm /dev/loop
27. losetup -d /dev/loop0
28. losetup -d /dev/loop1
29. mbchk kernel.bin
30. cp kernel.bin /mnt/image/minimal-kernel
31. umount /mnt/image

And then run it with:

qemu -m 100 -hda myos.img -boot c -no-kqemu

There you go! Of course, once the image is created and sorted, for development you only need to repeat step 30. You can remount the image in a build script:

mount -o loop,offset=32256 ./myos.img /mnt/image

Here are more resources:

• http://www.osdever.net
• http://www.jamesmolloy.co.uk/tutorial_html/
• http://www.osdever.net/bkerndev/index.php (Bran's kernel development tutorial)
• Intel Architecture Software Developer’s Manual (search Google)
  
• http://oreilly.com/catalog/linuxdrive3/book/index.csp (Linux device drivers, 3rd edition. FREE as in beer!)
• http://tldp.org/LDP/tlk/tlk.html
• http://www.ibm.com/developerworks/linux/library/l-linuxboot
  

Physical Symbol Systems

At the university, I'm now following a course on knowledge systems. There's plenty of room for one to be sceptical about knowledge systems, in the sense that it's possible to think of general procedural programs as knowledge systems too, the knowledge system is identified by the ability to separate knowledge from processing (the inference engine). This great distinction, if followed to the letter, means that knowledge systems are only valid once knowledge is explicitly declared and not mingled with source code of the inference engine. This rules out most procedural program implementations, if not all. In a simple interpretation, I'd say that knowledge systems can only be built in Prolog.

I don't want to discuss this item for the rest of my post however. What is more interesting is the hypothesis stated by Alan Newell and Herbert Simon (picture above). They stated:

A physical symbol system has the necessary and sufficient means for general intelligent action.

This implies a couple of things. First, that intelligence can be thought of as symbol manipulation. Second, since computers can be thought of as symbol manipulation machines, computers can in theory become intelligent.

Many efforts on representing knowledge in computers generally start with some written-down term of a particular symbol. Reasoning with text however is a bit daunting, that is, the symbol itself cannot be broken down and its meaning is invoked through its connections with other symbols and concepts.

Thinking very abstractly however, symbols are representations of knowledge, and symbols need not be visual. I could for example describe a cow as 0x7A832B12 and add further different representations of the same thing. Colloquially, I could add the image of a cow, the sound and the smell and tie them together as representations of the same thing.

Symbol reasoning systems then require the computer to categorise the symbols themselves, to find ways they are equal, ways they are different and how symbols might be related to other symbols and in which way. It's even possible that the relation itself is yet another symbol.

A limitation of our thoughts might be that we rely on our language too much in order to be able to debug knowledge systems. I'm considering that language itself might not be the most efficient way to develop reasoning systems.

Another important quote that I read today is that there is no true way yet to assign meaning to symbols, however meaning can be represented in a computer, that is.

Hmm.... the ideas I have about this subject are really abstract and it's almost impossible to write them down in a sensible way, at this time. But why rely on our or any other language for a representation of our knowledge? If knowledge has different appearances, then shouldn't we let a computer choose how it decides to store it? The designer of any program makes full decisions about data, and data structures.

For learning machines though, we may need to innovate on how data and knowledge is stored, such that more complex systems could possibly use it in different ways, hopefully with the ability to derive new knowledge from existing knowledge, which seems a current hard limitation for a computer at this time.

So... goal: Build a knowledge system without a specific design for the storage of knowledge, or built it as a hybrid combination of implicit knowledge with explicit knowledge.

The world explicitly in "math vision"

Computers don't have sense of anything. They're basically only good at processing according to a couple of defined guidelines (the program) and nothing much else really. It's just a processor, like a blender processes food and was designed to do so.

Artificial Intelligence is so interesting, because it comes up with novel ways to reason with input. In a very narrow (or is it broad?) definition, any computer program is artificially intelligent, because any program uses "if-then" rules. However, engineers typically do not accept that definition, because the intelligence conveyed by such programs are not surprising and do not supersede our own capacity for reasoning. Popularly speaking, being intelligent means that someone, some animal or something is behaving in a way that surprises one.

A (regular) program cannot execute other rules than those "if-then" rules it has been designed to handle. That generally makes it very explicit and consistent in its behaviour (unless bugs are in the program). Let's assume that any program I'm describing here has been 100% tested and is guaranteed 100% bug-free.

The world to physicists and mathematicians looks different in many ways. There's a constant awareness of approximations of behaviours through formulas and the awareness that some problems that look ridiculously simple are astoundingly hard to solve or describe mathematically.

For A.I. to continue into its own field, it'll be an ongoing battle to get the computer to reason and "understand"? (this latter term should be used very carefully) its environment better. Roger Penrose highlighted four different viewpoints on the mind (mind != brain), where on one extreme the mind is 100% mystical and unexplainable and at the other extreme it's 100% computational. Dr. Penrose is a physicist and he doesn't seem to be inclined to believe that the mind is 100% computational (viewpoint A), but there's a strange missing link that allows computational processing machines to become aware (although one could also argue that awareness actually means introspection abilities), the state vector reduction between quantum physics and that of classical physics.

When one mentions "make the computer smarter", one generally assumes that the computer should become more like us.... but thinking about it... there's no reason why it must or should. I've argued before that humanity is pretty arrogant when it comes to words about intelligence and it basks in the light of its own narcissistic tendencies. Consciousness is not truly a pre-requisite for life-like intelligent action. Although consciousness itself is very likely not achievable in non-biological machines... can some sort of consciousness be simulated or modeled?

Some posts back I wrote about rule mining. For a computer to simulate consciousness, it should be able to deduce new rules, descriptions by analysing its perceptions. However, in order to even start doing that, it must see the importance of doing so in the first place. And in order to see the importance, it must understand the context and environment. So this is a circular argument, seemingly? Well, we certainly don't get born with objectives and understanding from day one. So there's a learning element involved and impulses that determine our goals. Baby's do have certain goals, although simple: "eat, poop, sleep" and they'll keep on crying until the goals are satisfied. Babies are human, but popularly, we're not considering them conscious yet. Possibly we start considering little children conscious when they start talking...?

Here's an account of a professor who has autism. The read is very interesting, especially the last summation, where four different levels of consciousness are given:

1. Consciousness within one sense.
2. Consciousness where all the sensory systems are integrated.
3. Consciousness where all the sensory systems are integrated with emotions.
4. Consciousness where sensory systems and emotions are integrated and thoughts are in symbolic language.

Next to the brain, we're also responding to chemical changes in the brain. In fact, just as the ear receives auditory information and the eyes receive visual information, we could think of chemicals and proteins to produce chemical information for our brains to process. Those proteins and chemicals indicate our own state to ourselves, besides the faster processes like pain (if pain were transmitted through chemicals, it'd probably take at least 20 seconds before a response occurred, not efficient!).

Quite some time ago, I mentioned that emotions are the driving forces behind humanity. What I really meant was that without emotions or feelings, we won't feel any urge to start doing anything. It's like a computer on a desk with 0% CPU usage, 0% disk I/O. Only when the proper impulse is given, is the goal generated and will we start to find ways to achieve those goals.

So it naturally follows that a 'conscious' computer should have goal-generating abilities to function more like an animal. The problem here is that one doesn't just code a "goal-generating algorithm". Different people pursue different goals. It depends on experience, outside stimuli, upbringing, different chemical compositions, talent, preference... So it's something that more or less 'grows on you'. How can the same thing be grown in an A.I.?

At a lower level... the building blocks that make US tick and develop the preference in the first place... what is it? I mean, what actually did develop consciousness or shaped it into being? If we assume babies are not conscious, then something at a lower level is developing/placing something there.

This suggests a lower level of being that is using consciousness as a tool for achieving its ultimate goal(s). That goal may be very simple (survival? pro-creation? endless aim for better well-being?), but through our conscious "processing"? layer, it translates this into several different sub-goals.