AI Challenge

Simon Funk put an AI challenge online, where you need to control two mechanical hands and flap a ball from right to left. The simulation itself is all in python and getting started is really easy.

My approach is extended from some ideas I am looking at with a colleague. The video above are some initial results of my implementation. The best performance is seemingly at the start I reckon, although you can definitely see that the left hand is replaying its strategy once it is getting into the same situation (the ball slowly rolling towards it).

The research is highly focused on how intention, (intrinsic) reward and perceptions from the external environment all work together to hopefully do something useful in the end. It's a great challenge to work on, there are great dynamics in this physical simulation.

I'm using an ATI GPU for the computation, which I hope to extend further in the future to get better results. Notice in the video how the arms don't really move very determined in all cases. For a large amount of the time, they are fighting the gravity and seem to have trouble generating enough energy to overcome the counterforces playing on their 'muscles'. They don't really need to much about the state of the entire world in order to execute some "good" actions (once again, 'good' is in the eyes of the beholder and depends on how much fun something is, social interaction, the benefits it "feels" it gets, etc).

Anyway, these are the results after one day so far. Now let's see if it can be made better.

FlightGear hacking

On the right is an image of a free flight simulator called FlightGear. It's used a lot for research purposes, but certainly also just to have fun and it is licensed under the GPL. You can fly anywhere in the world with the planes provided and the entire framework is reasonably extendable. There is actually a choice for the Flight Dynamics Model that you wish to use. Each FDM has different strengths and weaknesses. One focuses on airflow around the body parts and weight and another one more on the steering and so forth. The objective is realism and trying to simulate how things behave prior to real life development and tests. Thus, that cuts down on the costs of development significantly really. Its objective is not to compete with consumer-level flight simulator, nice flashy graphical details and so on, but the focus is on correctness of the flight model and other items around it.

For example, the airports are correct, the runway placing, approach lights, the sky and environment model are accurate qua stars, sun and moon given the time of day, the handling of the instruments are correct (the magnetic compass lags behind a bit just as in a real airplane), some planes may break when put under too much stress (although the pilot is likely to break before that!). The scenery uses the SRTM data that I also used to do the hillshading in mapnik (see previous post).

There are a lot of customization capabilities for FlightGear too, making it very suitable for research. The way it works is pretty simple. You specify an option parameter that states a direction of input or output (if input, then the simulator accepts an external file or socket for instructions to control ailerons, rudder, etc. ). More details can be found under /usr/share/games/FlightGear/Docs/README.IO if interested. The option looks roughly like this:

--generic=socket,out,10,localhost,16661,udp,myprotocol

So, this chooses a socket transport, outgoing data, 10 times per second, localhost, port 16661, udp protocol using the protocol as specified in the myprotocol.xml file. Easy!

The receiving application can then start processing a stream of data coming from the flight simulator. It can also send back a number of commands to control the aircraft, the environment, sounds, AI models or whatever. Basically, it's quite a nice way to try out a couple of concepts before having to dig too deep into the bowels of the flight simulator package itself. The same methods are actually used to store a flight path of a plane and then replay the flight later (at the specified frequency intervals). The same methods are used to connect flightgear instances together and do some multiplayer flights or track the positions of flightgear users on a large map.

Hill shading OpenStreet maps

I've been fooling around with OpenStreetmaps again, this time just trying out a couple of experiments that others did and hopefully in the process develop some interesting ideas to use the data. I've blogged about Openstreetmaps before. A couple of things have changed as Karmic came out. Some build steps require you to download more software and some packages may have been removed since then. I've had bigger problems getting mapnik to work, but that was related to the projection of the import of OSM into Postgis. When starting 'osm2pgsql', don't use the "-l" flag, because that indicates conversion to latlong. The standard mapnik projection however is mercator. Most of the times, when nothing shows up in the rendered image, it's a projection problem somewhere. Just verify it all makes sense going backwards from the mapnik process and you should find it quick enough.

Anyway, a very interesting experiment I tried relates to hillshading. This is an effect where elevation data from different sources are merged (nowadays people use 'mashed') with map data in order to shade particular areas of the map to show where the hills are located. Elevation data for most of the world can be downloaded for free from the Shuttle Radar Topography Mission. You should get version 2.1. For the US, there's elevation data available with 30m horizontal accuracy, the rest of the world only gets 90m (or 3 arcseconds). Some tools exist to help you out in managing that data: srtm2osm (I didn't use this) or a script called srtm_generate_hdr.sh (which I did use). Downloaded the data first, then produced the HDR files.

Then run a simple script:

cd /home/gt/srtm/
for X in *.hgt.zip
do
yes | /home/gt/srtm/srtm_generate_hdr.sh $X
done

This basically generates a number of TIF files for each particular region. These TIF files are height maps. When you look into them, you may be able to recognize certain parts of your country, but don't over-interpret the images you see, because the actual height doesn't really show up there.

In the Ubuntu repositories, there is a package called "python-gdal", which is a set of utilities in python to drive gdal utilities. This can easily be used to stitch the generated TIF files together to generate one huge height map for the entire region. I've used this to get a height map for the Benelux for example, resulting in a 55.0MB file.

Problem is that the projection is incorrect, so you need to assign the latlong projection first, then warp the image, reprojecting it to mercator (what mapnik uses) and in the process attempt to take out any invalid data points (set to 32767).

#> gdal_translate -of GTiff -co "TILED=YES" -a_srs "+proj=latlong" combined.tif combined_adapted.tif
#> gdalwarp -of GTiff -co "TILED=YES" -srcnodata 32767 -t_srs "+proj=merc +ellps=sphere +R=6378137 +a=6378137 +units=m" -rcs -order 3 -tr 30 30 -multi combined_adapted.tif warped.tif

Cool! So we now have a warped.tif in mercator projection that is basically an elevation map of the terrain. This is however not yet an image which uses the elevation data to 'shade' particular areas of the map. Think of putting the elevation data under a spotlight and then moving the spotlight to some particular origin (somewhere NW), located high above the map. This would create shady areas on the parts of the map where there are hills facing away from the lightsource. The other sides would be normally visible.

Perry Geo luckily did this work for me. You can download his utility here. I had to modify the Makefile to set the GDAL include path (-I/usr/include/gdal) and modify the included gdal library (gdal1.5.0). These tools create a 400-500MB hillshade file (18555x24128 pixels) if you use it for the entire Benelux region. That's still manageable, but in the process of getting there you may need 4GB of memory and a fast processor. The following image shows a minute detail of the Dutch coastline (scaled down 33%).

So that's cool. This image can be used as a bottom layer for some mapnik generated tiles. If mapnik then paints other layers above it slightly translucent, the shading will slightly shine through the image, creating a sense of height throughout the map.

A standard mapnik image from a region in Belgium, close to Maastricht which has a number of hills looks like this:

The same region in Google Maps, rendering terrain data, looks like this:

So, my rendered image looks different from Google's, but the styling wasn't optimized for terrain data in the mapnik renderer.

There's also a reason why the zoom level wasn't increased to about 18 or so. Remember that we downloaded the SRTM3 set, which provides 90m accuracy in the horizontal plane. The height map therefore interpolates between subplanes of equal elevation. This doesn't necessarily improve quality :). Google Maps doesn't go beyond zoomlevel 15, which is a reasonable one. Trying to render images at increased zoomlevels creates pixelated images that don't look nice at all. The height map can improve slightly with better algorithms, but no matter what you do, it will never be perfect. Google Maps even has a couple of areas with hills that look a bit blotchy, irregular or pixelated. The idea is just to get a sense of height of a mountain range anyway and drawing the contours around this map certainly helps to find out where the mountains are (especially for hiking and cycling maps, which use these techniques regularly).

Original sources with the tutorials are here and here.

ATI Stream on Ubuntu 9.10 Karmic

Just as Nvidia has CUDA for GPU programming, the ATI cards also have an SDK to get those hardware-threads revving for solving complex, scientific or brute-force problems, called ATI Stream. I have a 64-bit OS with a quad-core Intel i920 and one HD5850 ATI Radeon on Ubuntu Karmic 9.10. On the 27th, some new drivers for the ATI card were released on the ATI website, which I think together with the nopat flag have resolved my problems getting the SDK to run.

After downloading the SDK, you need to set the LD_LIBRARY_PATH for the system to find the opencl shared libraries and whatever else is in lib. It's actually not as easy to find the installation documents, they're hidden 2-levels deep in links, but here's the full documentation for the SDK (the link to which could be stated more visibly on the ATI Stream page).

Officially, ATI Stream is not yet supported for Ubuntu 9.10. I initially got only segfaults for any application or it just wouldn't find devices even when the latest Catalyst drivers from the ATI site (27-Jan-2010) were downloaded and installed and a full restart was performed. However, when the "nopat" option is supplied as a kernel boot parameter, things work a lot better :). Right now, most samples seem to run except for one specific one that my card doesn't seem to support. Because Karmic uses grub2, the location for modifying kernel boot parameters changed. You need to modify /etc/default/grub instead of /boot/grub/menu.lst. I inserted nopat here:

GRUB_CMDLINE_LINUX_DEFAULT="quiet splash nopat"

After these modifications, the /usr/lib/OpenCL/vendors links and the environmental changes for LD_LIBRARY_PATH, yours should be working as well.

There is some more information about OpenCL, which I think is a very nice advance into ensuring portability of GPU code to other platforms. A very good explanation about CPU vs. the GPU can be found here :).

I'm planning to use it for some really new and innovative experiments involving different perspectives on neural networks, network spiking and so on. The idea is that I need a large number of parallel processors, which can be very modest in processing power, as they only need to move a very bit of data and perform extremely simple processing steps. The details and the complexities of the work is in the synchronization, so I'll take some looks into that :).

What knowledge may actually be about...

I've been cycling in the rain today and suddenly got this awesome thought train. Nothing much to do with rain, but I guess that the cooling characteristics of the cold rain with the cold weather probably caused some superconductivity somewhere. I can't get into too much details what I've come up with to resolve the below general and (as I argue) incorrect assunptions, but I can at least discuss the problems I perceived that might restrict the ability to develop more intelligent behaviours in computer programs. :)

To give you a starting frame of thought, I'm arguing that there are many assumptions about the origin, extent or representation of knowledge in many artificial intelligence reasoning models, in neural networks and whatever else is there. Here is why.

Most computer programs function by taking some parameters from an environment, file or whatever as input and based on that perform some action. A program without input or output is not a computer program. The general idea is thus that by applying some function F(X) on a range of input parameters X, one can derive an action or actions Y that should most logically ensue. The diagram here helps to illustrate this further. It is a depiction of a so-called Markov diagram. These are often used in A.I. to reason about and between states. One can move from state to state along the transitions, but the arrows also restrict movement to just any other state. The diagram need not be statically defined a priori, there are sometimes ways to dynamically extend the diagram at execution time, most of the times determined by a set of rules. M here is the entire world, consisting of possible transitions or relations R, states S (which is more of a placeholder in this case) and measurable parameters T from which you determine the current state S.

The above model works very well for a set of discrete parameters, since they always fit into one single state. For continuous parameters however, it becomes more difficult, because if every single value is considered, the number of states in the model would become infinite. Hence, classification is needed to reduce the number of states, or the development of some kind of 'probability distribution', where one is actually a little bit in all states at once, or one can come up with a fuzzy reasoning method for reasoning between just two states S1 and S2, which are closest to the current 'continuous' state.

The huge assumption made here is that all information leading to some desired action can be derived from a snapshot of the external world, just by inspecting some range of percepts X. Reasoning and intelligence is then reduced to the application of some function F(X), even though this can be quite a complicated affair when there are a possibly very large number of percepts X or a wide range of possible actions Y. The complexity due to the dimensionality of the problem is irrelevant for this conclusion however. Even more worrying here is that there's only one single assignment of intention or purpose in this entire system. The purpose is the definition of the function F(X) in itself, but it'll be difficult to change this as soon as the system has been constructed or trained... Hmmm... :). So one cannot expect this system to generalize a bit and then specialize further into other things.

So, resuming... having a function F(X) implies a direct, causal relationship between (a range of) perception(s) and a most logical (range of) action(s), which only holds if the purpose is fixed and pre-defined and doesn't change. Or worse... the context does not change. Also, knowledge is then only defined as the function that needs to be applied to the percepts in order to derive the action Y, it is not contextual knowledge about what is required in which context. In effect, the only way to make the system more able to deal with situations is to measure more and more in that single snapshot and then trying to fit the function F(X) to suit those measurements.

However, instead of considering that it is the state(s) embedding the information, one should consider that it is the transitions that allow one to collect the real knowledge about events, since transitions embody relationships. The transitions maintain the real information about some state S1, the next state S2, the difference in the percepts, the action(s) that was undertaken and whether S2 is actually a better state to be in when compared to S1, so deriving whether the action was desirable or not, given a certain context. Note that this doesn't yet require much information about a goal state Sg, so one might as easily conclude that there is no direct need to know about the eventual goal state or have a real conception about what it looks like, we can at this point still assume we're slowly and gradually moving towards the goal state and there's still a capability to change direction or impact the environment to reach the goal anywhere (but this is getting too complicated at this point).

This is why I think that discarding the thought that there is a causal relationship between percepts and most likely or desired action should be a first objective in order to develop more intelligent systems. Knowledge is more likely some kind of imagination or dreaming of the effect of actions from any given particular 'general state' and the kind of changes in perceptions how one can measure such progress, all this framed into a particular context. This should allow systems to reason with shorter horizons or reason at different levels with different horizons, but always reason with specific and particular contexts at each level. The definition of how many transitions you allow before making conclusions, or the extent of correlation between events is then part of the game and part of the experience...

Cybernetics

For my work, I've been looking at neural networks in more detail, but specifically how they may be applied to problems with temporal properties. Most artificial neural networks do not store their values or activations as some kind of remanent activation very well. Such neural networks can only work in situations where the input applied to the network is complete enough to derive conclusions from it. In that case, it doesn't matter if there is a known formula for the correlation between input and output values or whether there is one, albeit a complex one, that is being approximated. Such direct correlations after one single frame of observance is the typical neural network that you get today. More recent developments also give you recurrent networks or LSTM cells, but those model patterns or 'data' over time. Thus, they establish correlations or relations between sequences of events. For all these networks, you'd generally expect a mathematical explanation or approach to back up the learning methods applied for it (if they haven't been trained with evolutionary algorithms).

Even in the case of evolutionary algorithms though, there is significant complexity involved in training the network so that it performs well. Unless the input/output correlation between classification or pattern recognition is very strong, which makes any problem quite easy. Basically, this means that in the same way that a formula calculates a set of output value(s) in a deterministic way (and 1+1 is always assumed to equal 2 and never changes), a neural network is just a very deterministic approximator. Given a trained network, any two inputs yield always the same output. This is true, unless you use an RNN. But the RNN is designed to work on temporal problems, so given the same sequence, this yields the same output to classify or reproduce the sequence.

The picture above shows a neuron receptor that is involved in a process called chemo-taxis. This process allows the worm to navigate in an environment where food is available. The worm has no eyes, can feel heat (thermotaxis), and wriggles its way within some environment. If the worm is wriggling towards a food source, it's climbing up an increasing gradient where the chemicals picked up by the neuron increase. When it climbs up an increasing gradient, the worm is less likely to make sharp turns. If the worm is on a decreasing gradient or doesn't detect any food source, it is more likely to make sharper turns.

Such a problem sounds very simple to resolve, but remember that we have eyes. How do you locate a particular source of smell if you only have a nose? You need to move around in a room, being careful not to cause any harm to the body. Depending on the sensitivity of the olfactory sense and the distance of the smelly source, the distance between one sample and another must be larger or may be smaller. The samples also must be taken within a certain amount of time, otherwise no significant difference can be observed.

The above shows how some organism, actor or agent must interact with the environment in order to sense it and make conclusions about the layout or composition of the environment. Without the ability to perform actions in the environment, I don't think there can be any development of intelligence at all.

Such statements are derived from a particular field of knowledge called 'cybernetics'. This sounds like some science fiction term I'm sure, but it's not just related to cyborg, cyberspace, the internetz or what have you.

Cybernetics is a recent term from the 40's and 50's defined by Norbert Wiener. The word is derived from the greek "kybernētēs", which means helmsman, rudder, etc. and has the same root as government. It was initially intended to study self-regulatory systems, but quickly expanded to other areas like management (Stafford Beer), biology and also computer science. The science is quite broad in scope now and poses questions about how systems make sense of their environment by interacting with it. Finding out what an environment is about isn't exactly the same as just perceiving it.

The difference with Artificial Intelligence is quite strong. Cybernetics is more theoretical, whereas A.I. has basically just gone ahead with a lot of assumptions, trying to wrap reality into mathematical models and executing them on a computer. My criticism of A.I. until this point is that it is simply too deterministic for anything 'new' to come out of it. The term A.I. has been a bit bold as well. Sure, we have large-scale systems analyzing emails and other kinds of data and knows how to extract information from it to make predictions, classifications or specific groupings of data. But those capabilities have been intended by designers. There is nothing that such algorithms or machines can ever do different but execute those particular implementations.

In that sense, expecting anything truly intelligent to come out of A.I. as it is currently approached (through mathematical formulas) is very hopeful at best. A better understanding of knowledge, its roots and how it may be represented over time and interacts with new environments is needed.

That is not saying that A.I. is useless. It's saying that A.I. certainly has approaches for doing pseudo-cognitive work by helping out massaging details out of very large mountains of data or finding specific correlations that we cannot even imagine. So there's certainly room for the A.I. as we know it now and some new kind of vision on what truly intelligent machines can bring us. Those kinds of machines however need a different basis than just mathematics and strong correlative behaviour. They need to find out for themselves what is important and have their own ways of interacting with the environment (which is how they find that out :).

Neural network dynamics

The picture to the left is an LSTM cell that can be used in some neural networks to 'remember' sequences of previous inputs. It can therefore re-create similar outputs as have been observed in previous runs or it can be used to associate one thing with another in temporal terms. Anyway, the reason for posting today is that there are particular dynamics that one should understand to choose the right 'kind' of network or even if one should use a neural network anyway. The more obvious design criteria are related to explain-ability of certain classifications or outputs. If you expect a neural network to give you reasons for why it indicated a certain classification or output, you're out of luck. So they have limited use in knowledge based systems where there must be traceability of the observations that lead to some conclusion or the observations that need to be taken in order to derive a certain final conclusion (enrichment and convergence towards a certain diagnosis for example). So in such cases, you should definitely use different technology.

Input signals can be interpreted or preprocessed in many ways and the exact method that you choose to model your network may have complicating effects on the design you require in the neural network that is supposed to resolve the problem. For example, if you have a mine sweeper as in http://www.ai-junkie.com/, then it is given its own orientation and the direction to the closest mine as input. Then you have a couple of weights and the end result is the output at two terminals, which is defined as the activation of the right and the left track of the mine sweeper. The overall goal is to get mine sweepers that consistently reorient their own direction to match the direction of the closest mine, such that they can clean up the mines as fast as possible.

However, another possible design choice is to use the distance to the closest mine instead. This really changes the entire problem scope, because a single 'frame' of the entire situation doesn't immediately provide all the information that is necessary such that the tank can be directed to the tank. Maybe this reorientation of the tank isn't successful from frame 1 to frame 2, but certainly in the direction/orientation approach, you can rest assured that you can guarantee convergence to match the two together and the ability to train a network to exhibit this obvious correlation (and basically behaviour).

In the case of distance however, the mine may be in a radius around the tank at any distance. The only way in which the tank can find out more about the actual location of the mine is to choose a single action and observe the difference in the distance. This particular action therefore is a very important key decision that determines the action that the tank should take in the frame thereafter (the time between frames in a simulation isn't necessarily 0.0000001 seconds, we could easily take 1 second and be happy with it. It does determine the resolution and accuracy of the end solution, but even minor fluctuations should provide this information).

So, the reasoning that takes place here cannot be executed successfully by observing a single frame of information. In other words, you need changes in the external environment, sometimes induced by your personal actions, in order to determine what happens next. This often occurs in robotics or other controller situations, where the relation or 'directionality' is not always known. Or sometimes you can derive it, but you don't know how you should react to it. Also, changes induced by other forces in that environment will then allow the system to react to those in similar terms, since the observation is changing.

The point is that there are certain dynamics in real-life scenario's that standard feed-forward neural networks can never deal with. Because FFN's must have full information available in a single frame that conclusively can result in the output situation to converge to some expected result. In cases where the external environment has a larger reaction period... for example the temperature of cooling water for a very large diesel engine, these neural networks will very likely never be able to react successfully, because they do not understand or embed the concept of memory.

This is why the type of the network is important and why there has been so much research into Recurrent Neural Networks. These RNN's have the capability to store observations of a number of past events into the memory of the network, such that the observations made in history impact the actual decisions that are taken at the output. Standard RNN's can remember information for about 10 timeframes (whatever the time resolution is you've chosen), whereas LSTM's have the capability to remember significant events up to 1000 timesteps. The idea is that significant reoccurrences of some events cause these cells to suddenly behave different and indicate to output neurons that some event is reoccurring, inducing a different kind of response than in other, more regular or random situations.

Now... there's a worm on this earth called Caenorhabditis elegans, which has exactly 302 neurons. This worm reacts to the smell (chemical concentration) of bacterial residu, because it knows that it can feed on the bacteria that are necessarily present there. Some bacteria infect the worm and harm it, whereas others are excellent feeding grounds. It innately avoids the smell of some types of bacteria that are harmful, but there are two types of harmful bacteria that it is especially attracted to. Lab research has shown that after exposure to these two harmful bacteria, it learns to avoid them later. Other behaviour includes social feeding, where worms gather together on large piles of food, up to some threshold determined by the amount of oxygen that these worms observe by one or two sensor neurons that detect oxygen.

If you ever wonder what a neural network in biology looks like, here's a full description of such a network. You can trace the network from sensor neurons to motor neurons and the actual muscle. But beware! You'll also see that this type of network is extremely intricate.

This shows that the dynamics of particular problems aren't necessarily obvious. Those things you can observe and how they interact with other dynamics of the problem interact together to which a solution has to be found that doesn't violate critical constraints, but still allow the problem to converge to some optimal solution.

Fitness functions

I'm reading up on Genetic Algorithms and the most important thing for these algorithms is to choose a correct fitness function. This is a function that determines a score for the performance of a certain instance or candidate for the solution or closest approximation of a given problem.

For some mathematical problems, if you have a set of data that you wish to approximate, this fitness function can be given by, for example, the root mean square error of the differences of the calculated result and the known result. A neural network wouldn't be used if the actual function was available, so let's assume that the problem is somewhat hard and cannot be approximated appropriately with either a rule or a function approximation.

Neural networks are sometimes trained using genetic algorithms by gencoding of the neuron weights, randomizing these in the first generation and then incrementally mutate, mix, pair and select these network instances until one network is found that seems to perform appropriately.

Eventually, after 50 generations or so, networks emerge that exhibit the desired behaviour expressed in the fitness function. But if we take this as an analogue to the biological world (where both ann's and ga's come from), then this fitness function isn't a single expression.

If what Darwin says it's true, imagine the time it must have taken to evolve from simpler organisms into more complex ones and the evolutions and changes that must have occurred in populations. The genetic effects are measured over the entire population (not on individuals).

For computers, we assume the role of overall biological system, but I argue that this is only suitable for the simplest of cases (assuming this role actually means defining the fitness function).

Besides considering plain survivability of a particular instance, the social behaviour of the overall group should also be considered (the generation that the individual net is part of). Some animals for example increase their survival rates by working together on occasion, which may leave room for other developments to occur that are highly favourable (although negatively impacting survivability). And if one individual succeeds in subverting or influencing another individual to their own gain, then this is one thing that should be taken along in the fitness function.

Come to think of it; many GA's are only used during a training session, but discarded otherwise. Most neural network training so far has been about pursuing a particular unknown function with a large amount of observational data. But each network generally is constructed as a lone individual in the entire population. still, there is at least some research that has been undertaken in the area of neural network ensembles, where cooperation is sometimes used to solve sub-problems, or in the application of environments where multiple objectives are present. As such, successful combinations of neural networks are what count most, not individual results. So, cooperation becomes an important factor for individual survival.

As with the previous post, for anything interesting to come out of neural networks, it may be necessary to find a fitness or cost function of a very complex environment in which this neural network is supposed to execute actions. This sounds really easy, but consider an example of a robot that needs to find a way through a corridor as fast as possible.

A simple fitness function is a measure of the amount of time taken to reach the end of the corridor. We may now feed the robot some sensory data, for example when it bumps into a wall. We always start off a robot in the correct direction. The robot can rotate two tracks on either side. Rotating a track faster than another makes the robot turn to one side, such that it gets a steering ability. Rotating both tracks to the same speed make it go forward.

You may think that the robot that goes fastest wins, but then the scientist sees that the robot has so much speed, it hits the wall with unforgiving force and breaks off a track. So a very stern measure would be to restrict the speed of the tracks, such that none of the individuals can move at that speed. A different solution however is to somehow factor in this speed or wall-hitting force and penalize those robots where this occurs often. Then we may have two different kinds of winners:

• Robots that still maintain a very high speed, but hit the walls sometimes
• Robots that maintain lower speeds and gradually arrive at the end of the corridor in good time.

Both strategies have their advantages and disadvantages. The one that is faster can also run faster from danger and therefore can maybe survive better. The one that is more careful has less chances of considerable harm.

So the judges are out on all of this technology. For specific tasks, they work because we can think of a suitable fitness function for them. As soon as things get tougher and wider though, the environment needs to penalize and reward those individuals appropriately. Good environments also allow for diversity in the population. And then one wonders whether such diversified elements continue to specialize in their own populations and wander away from their original ones. A bit like evolution outside of their normal populations.

The brain in a vat

Daniel C. Dennett started out his writing on "Consciousness Explained" with a description of a demon, who is trying to trick a brain inside a vat into thinking it's actually inside its real body and world with real worldly experiences. You can easily compare this account to the hooked up people inside the Matrix, where each individual's brain is fooled into having a body, relatives, material things and the day-to-day worries of their lives, but actually hooked up to a large computer, the Matrix, which is conjuring up these illusions to every brain. Dr. Dennett's is giving this a bit more thought and considers the things you need to do for the brain to get tricked like this. Now, let us assume that, contrary to the story of the Matrix, the people in this thought experiment actually have had real-world experiences to compare these senses too. First of all, you'll need to be able to simulate the senses; vision, smell, hearing, tasting and so forth. And here comes the difficult part. The demon or the computer need to be able to detect some outcome, the chosen action and react on that appropriately as the physical world would re-induce their worldly feedback to such actions, in a way that this brain is used to.

In the example, he's referring for example to lying on the beach with your eyes closed and running your fingers through the sand and the feeling that the course grains of sand give you on your fingers. You could also refer to the action of jumping, the feeling of being in the air for only a little while and the thump when you get back on your feet. Or whistling in some echo-ey tunnel made of mostly metal and the sound this returns to your ears, or the joint coordination of some sports game, etc...

So, the difficulty of tricking a brain is in the first place hooking it up in the right places, sending it the right kinds of signals and reading the brain at the right places. A more difficult thing however is that outside the brain, there's a physical world that the brain expects to get feedback from in very specific ways. Especially once it has experiences in this world, it'll look strange if anything of that changes. The illusion will wear off very quickly due to these little differences (although you would argue that if the illusion is near-perfect, the brain will probably start doubting itself?).

The point here is that the whole thing of "Artificial Intelligence" isn't that close yet as people may try to make you think. Computers live in some kind of "model" of the reality, it's a transduction of what is really there to be perceived. Some other transduction is also very likely affecting us (and trying to tell someone else what you experience or what a bat experiences is very difficult to achieve. We simply cannot easily imagine how it'd be to experience something else entirely). This model is an electronic or otherwise suitable representation of the world around a robot or AI, and therefore subject to our imagination and experience, but not necessarily the most ideal.

Worse yet, biological entities around us are evolved in the physical world. Probably according to Darwin's Origin of Species, where evolution is largely a function of natural selection of creatures, constantly (needing to) adapting to their environment. The same ideas can be found in Genetic Algorithms, a method of engineering where algorithms or parameters thereof are encoded as genetic material and then mutated and crossed over just as biological material. This is sometimes useful in cases where the actual (very long!) functions are very difficult to discover.

In supervised learning, where the actual solution is perfectly known, artificial neural networks can be taught these patterns by feeding the input and then checking the outcome and recalibrating the parameters of the network until the performance of the network no longer improves. There are difficulties in this kind of training, namely that a network that is too large overfits the training and performs generally badly on unknown cases that it may have to predict. A network that is too small is generally not capable of holding the information that is needed to capture the actual function, so underperforms.

So, for neural networks, one either ends up remodelling the entire world and calculating elements of that, such that a network can be trained to recognize or predict it, in which case you're better off sticking to this representation of the world instead. The alternative is not pretty either. One must find a method to evolve a network such that it has the correct architecture for the job at hand and train it without knowing the elements in advance. More so, because these more complex networks don't generally have classification outputs like most ann's do, but instead, I think, probably thrive on the state within the network itself, induced on their neural surroundings.

Combinatorial explosions

I'm reading, next to "Consciousness explained", a book from one of my favourite writers Steven Pinker. This one is called "A blank slate", otherwise known as tabula rasa, where this blank slate refers to the idea as the brain being a type of blackboard that is written to by experiences, or whether certain capabilities and intricacies are preprogrammed, otherwise called innate. Pinker's writing is everything from an exploration, to various explanations, but not in the least a (strong) argument about how we should interpret this "blank slate" and how, in the search for an explanation about intelligence and consciousness. Probably it's best to see his presentation over at TED talks. But be aware that this presentation doesn't cover the topic of the book entirely and that there are many more little facts and explorations that the presentation certainly doesn't cover. Other than that, it provides a good insight into his kind of thinking and scientific approaches and validations.

The combinatorial explosion comes into effect when the number of variables increases by such an amount, that a true understanding of every state and how states influence each other becomes an impossible task. In two examples given, there's the case where the human genome was analyzed and in some reports counted as the number 30,000. The total DNA is a bit more than that, but 1.5% of this are these 30,000 genes, the rest is considered "junk DNA" (apparently and allegedly). Well, looking up the numbers on different sources, you get different numbers here as well. Some sources say 35,000, others 30,000 and Wikipedia claims 23,000. Which one is the true number, we'll never know :).

There's a kind of worm though that has roughly about 18,000 genes (or 20,000 as in other claims?). This worm has 203 neurons or so exactly, avoids certain smells and crawls around looking for food. How come such a worm with 18,000 genes is so strikingly different in behaviour and intelligence from us humans, where we have "only" 35,000 genes? Are we so much like worms?

If you consider the numbers as a linear base, then this must indeed be shocking. But genes amongst themselves interact and may then inhibit or activate other genes that create different proteins, which in turn influences the way an organism develops and grows and at which time-scale in life.

Here we go... The combinations of 18,000 genes interacting amongst themselves is already staggering, but 35,000 genes is a factor 2^17,000 larger. Whoops! That has the potential to be substantially more complex than anything we've ever seen before :). This doesn't mean that all these genes do interact, but the amount of information in this sense cannot easily be captured by just listing the numbers of genes. The actual information is contextually determined by the numbers that actually do interact together, and whether there are also combinations of 3-4-5 genes that form some kind of composition together. In those cases, the complexities go up to 3^x or 4^x even (we assumed interacting genes together before).

Now, it is interesting to find out how these genes interact and how influence these genes really have on our thinking and behaviour. We generally consider the environment a very important element in the analysis of behaviour and growing up, sometimes to such an extent that the entire evaluation is attributed to how some environment determined a person's actions and behaviour. But if we find out that general behaviour, personality twists, general motives and so on aren't necessarily determined by the environment, but hardcoded in genes. It's just our experience that allows us to exhibit this behaviour or not, then the picture severely changes. I'm starting here with my own thoughts by the way, this is not necessarily what was written in the book.

In that case, experience is more of a method to determine probabilities, elements of chance and other things that either inhibit our motives or stimulate them. In this view, our personality and things we do are genetically determined, while our dynamic interaction and behaviour choices are mostly governed by experiences from the environment. The general observations that one can draw from this is that personality twists, likes and dislikes probably come out as characteristic features of a person, but they are genetic. Whereas specific choices not to do something or go for it all the way are potentially given by variables in the environment. This sheds a totally new light on behaviour and how we perceive it in general.

Another thing that I found interesting is the way how it interlinks with computer science books about modularity and compositions of specific system parts with a particular purpose. Rather than thinking of a computer as a single thing, you can divide it into multiple elements like the CPU, the harddrive, graphics card, etc. But if you look closer, than the CPU is a large number of transistors with a number of pins plugging into the motherboard somewhere, such that it is linked with memory and buses on the motherboard to give it the power it has. The CPU is often called the central part and other parts are ancillary to that (well, you might also argue that the motherboard is the main part, because that's what everything is slotted into).

In this way, you can look at the entire computer from totally different views, each explaining very different purposes and levels of abstraction. Looking at the transistors of the CPU, there is no point in discussing why a word processor does all the things that it is told to do, the level of detail is too high to consider it. A more appropriate level is to consider the functions of the computer as a whole and then to explain how people interact with it, why a computer reacts and acts the way it does (it's been told to do that by its designers) and so on. There is also the level of how devices interact that is interesting. To handle keystrokes for example, you could consider yourself part of this system, the input provider. The keyboard is a transducer that converts a small burst of electricity into a scancode, which is read from the USB port of the computer. This scancode, a byte, is then processed by the CPU and sent to the OS and program, which determine if the scancode should be discarded or accepted. The program may then decide to attach the scancode to some array of bytes it has in memory, completing a long line of character strings. For feedback into this entire cycle, the graphics card gets a pointer into this array and repaints the screen when needed.... PHEW!

For each of these things, you can go down to the signal level even, but also further than that on the physics level of electrons. Explaining this process through electrons is going to be a long sit-in, so let's not do that here. At the highest level, it just seems to make sense. You press a key on the keyboard and that makes the character appear there on screen where the cursor is... Is that so hard to understand? :).

Similarly in the understanding of our thought processes, there surely seems to be good room for finding out how networks interact and process or store information. I don't think the sciences in neural networks can be called complete, in the sense that we know everything about them and what they do. One idea for example is that neural networks are very good at processing signals and outputting another. Basically directly responding to signals. But the way how we compose neural networks in amateuristic ways doesn't yet provide handholds for doing more things with them. Biological networks may have a lot of "failover cells" in them that are not strictly necessary to make something function. Also, the human brain consists of 100,000,000 neurons, but 60,000,000 of those are necessary for direct, muscular responses, instinct and movement (the reptilian brain). That leaves "only" 40,000,000 cells for human reasoning, visual perception, auditory perception, speech and other functions. Hmmm... that does shed a different light on things.

Basically, numbers by themselves don't give you information about actual complexity. It's about the interactions between these components, what they can do together in unison that's yielding the most power.

Comments about the CRU hack...

http://www.realclimate.org/index.php/archives/2009/11/the-cru-hack/

http://www.realclimate.org/index.php/archives/2009/11/the-cru-hack-context/

Sane Value Decomposition

Oh no! Another article about SVD! Well, this one is not specifically about SVD, but it is describing some of my theories about parametrization of SVD and why so many people get different results and possibly why I didn't win! :).

To explain my theories, we need to first understand SVD in some reasonable way. The SVD formula goes:

A = U Ʃ V

Which means that the above (for the purposes of this explanation) square matrix is decomposed into other equally sized matrices U, Ʃ and V. The U and V are orthogonal matrices, the Ʃ matrix contains the so-called singular values.

More intuitively said, the U matrix is a depiction of the actions of the rows in the matrix, whereas the U matrix is a depiction of the columns. Multiplying the values in a row of U with a column in the V transposed matrix (V.T), multiplied by the value in the diagonal of Ʃ that corresponds to the row,column selected, you get the value of the original cell in A. So, svd on a matrix A gives a strict representation of the values in A, but in a different 'decomposed' way.

But we don't have to go all fully-dimensional, because having all matrices around means we need three times more storage than the original one, and that's not the point. So the idea is to reduce the dimensions of each matrix and keep only the first x around. x however should be a reasonable percentage of the rank (row/column size), because if x is too low relatively speaking, you're not getting good results. I will show how this all works in more detail using python, a language that's very quickly starting to become my favourite language for experiments!

Example:

This is a square matrix with random values between 1-5 of n x m = 5 x 5 dimensions. So 25 numbers in total.

[ [3,5,2,4,4],
  [3,2,5,5,3],
  [4,4,5,4,3],
  [2,3,4,5,2],
  [1,5,5,2,2] ]

One thing I discovered (which many sites probably mention in not so readable terms :), is that when the matrix becomes relatively large, the first singular value on the diagonal approximates the average multiplied by the square root of the total numbers available in the matrix ( in the case above, the average is 3.48 ).

Ʃ(1) = avg * sqrt( number_of_cells )

The second singular value for larger, irregular matrices is approximated by:

Ʃ(2) = sqrt( 2 * Ʃ(1) )

So there certainly is a pattern being generated. Each singular value in the decomposition is actually a gain factor. So, if the matrix is really, really large, the singular values become in the orders of 1000's and the values in the first columns of U, V become 1/1000 in the case of this particular range for the Netflix data ( 1-5 across the matrix ).

Here are the actual singular values when the matrix is decomposed:

sigma = mat( [ 17.76224954, 3.5139895, 3.16968094, 1.60407331, 0.73105457 ] )

And here are U and V:

mw = mat( [[-0.44379232, -0.33273609 ,-0.80072792 , 0.11314317 ,-0.19587877], \
    [-0.4616133  , 0.58960592 , 0.15588499 ,-0.08007446 ,-0.63919166], \
    [-0.5053614  , 0.05135939 , 0.03629005 ,-0.69454331 , 0.50819749], \
    [-0.41956887 , 0.28391073 , 0.09075436 , 0.69668699 , 0.49974748], \
    [-0.39816248 ,-0.67705869 , 0.57007135 , 0.11412068 ,-0.21225762] ] )

cw = mat( [[-0.33638547 , 0.24667399 ,-0.32741104 ,-0.73031105 , 0.43063272], \
    [-0.47365356 ,-0.80039862 ,-0.13379567 , 0.1795791  , 0.29131499], \
    [-0.52873629 , 0.082443   , 0.81168849 ,-0.18044758 ,-0.14913599], \
    [-0.50662787 , 0.5372694  ,-0.21592459 , 0.61450025 , 0.17445861], \
    [-0.3553354  ,-0.05530591, -0.4116298  ,-0.15564457 ,-0.82280841] ] )

Notice how in the U and V matrix, the numbers are maintained at roughly the same magnitude throughout each dimension (you need to read rows and each column further to the right is one dimension deeper). This can be done because if you follow the implementation of SVD correctly, the singular value is the gain factor. So, choosing the correct 'gain' is essential for proper functioning of the model, or you need to adjust the parameters in each dimension.

What some people did in Netflix for example is to assume a gain of 1.0f (the singular values were not used) and then initialize each dimension to some 'low' value. Naturally, you can see that these 'low' values are actually really low in the beginning, but once the model starts to hit other dimensions, you may suddenly hit a gain factor that is above the singular value of the actual matrix Ʃ. That means the model becomes immediately instable and will start producing very high values.

Let's look at a regular matrix:

[[4 4 4 4 4]
 [5 5 5 5 5]
 [3 3 3 3 3]
 [2 2 2 2 2]
 [1 1 1 1 1]]

U:
[[-0.54446573 -0.21442291  0.76382282 -0.25982498  0.08152026]
 [-0.65208362 -0.46955287 -0.55122106  0.17692309  0.13842191]
 [-0.3619848   0.49755586  0.15572615  0.71006801 -0.30489008]
 [-0.31846257  0.36154464 -0.26944015 -0.60360543 -0.57526478]
 [-0.21422565  0.59604242 -0.12602146 -0.1807017   0.74182633]]
sigma:
[ 17.71717246   1.04811144   0.           0.           0.        ]
VT:
[[-0.53913501  0.50275905  0.61561055 -0.13109677  0.24577241]
 [-0.40915723 -0.26153467  0.04808419  0.872681   -0.01748586]
 [-0.35699995 -0.56822929 -0.1744093  -0.31507809  0.64805378]
 [-0.37793419 -0.44513203  0.23939904 -0.33777929 -0.69829541]
 [-0.52119151  0.39724791 -0.72868447 -0.08872685 -0.17804491]]

Whoops, what happened? We now only have 2 dimensions left, but after the third dimension all values are 0? This is because the matrix is so regular that it can be described perfectly with two factors. Hmmm.... So if there is good regularity in the data, then we need less numbers to represent the matrix! Of course, the above is taken to the extreme, but looking at recommendation systems, there are certainly regularities:

• Some users are very constant in their ratings and generally use a scale of 4-5 for everything.
  
• Nobody wants to rent bad items, those are generally avoided, so the likelihood that someone gets an unexpectedly bad item is relatively low. That means that relatively speaking, ones and twos occur less often than 3-5.

In essence also, you don't get a lot of information if rows or columns only contains 5's. The information is in the irregularities actually (or temporal trends, but that's another story! :).

More on the theory... Suppose we stick with the irregular 5x5 matrix above. It's basically random. I wanted to find out how fast I can converge to this 5x5 matrix using both some clever initialization techniques and gradient descent. (gradient descent is where you assume some random factors mw/cw, then calculate using those factors your prediction, compare this with the real number and adjust the factor by the error that you get from the comparison. This way, you can "train" the decomposed matrices U and V individually without having to store the entire matrix A in memory (which you don't have anyway, except for a small percentage of, say, 1% of it ).

When you look at the matrix, in the first feature / component that you calculate, you need to make a jump from 0 to somewhere in the 1-5 region. And all numbers 1-5 are positive. This is good, because you know that either the features need to be both positive or both negative. Make your choice. A good approximation for each feature further on is the sqrt( average ) of each respective column and row. This is because in the final calculation, the value in the cell is hopefully already quite well approximated by:

Aij = Ri1 * Cj1 * Ʃ1

In practice, for slightly larger matrices and those that are totally random, the root mean square error of each estimation vs. the real value will be around 1.41 or so. Of course, this is a function of the range used in the actual matrix A. It also shows that if the matrix is highly irregular, you're not converging very quickly to an error rate where your model becomes useful for making nice approximations.

Learning matrices is a tricky operation. Assuming the matrix from above, which has full information available, is square and relatively easy to learn, if the learning rate is too high, the model becomes unstable and the RMSE increases at some point exponentially. Ideally, you start from a good initial point, so that the gradient descent only needs to settle to the minimum, but this is only possible in the start situation. A good initialization of a model uses the following formulas:

1. Calculate GLOB_AVG from entire matrix
   
2. Ʃ1 = GLOB_AVG * sqrt( num_cells )
   
3. Ri1 = sqrt( Ravg / Ʃ1 )
4. Cj1 = sqrt( Cavg / Ʃ1 )
5. lrate_first_cycle == slow (it's almost there) == 1 / Ʃ1
6. INIT = ( GLOB_AVG / ( 2 * sqrt( 2 * GLOB_AVG * sqrt( num_cells ) ) ) )
   
7. Rix (x>1) = rand( -INIT, INIT )
8. Cjx (x>1) = rand( -INIT, INIT )
9. lrate_other_cycles == depends on the data :)
   

The latter comment was made, because I don't have sufficient empirical insight yet into how the learning rate should be calculated. It also depends on the objective. If you have full data available and you just want to deconstruct quickly, then you might want to go for fast and high learning rates. But for others, accuracy is more important and not having too many factors lying around. Then a fast enough, but much slower learning rate is more appropriate.

I'm still looking into data inside matrices that may be imbalanced. E.g., having 17000 ratings on a single row vs. sometimes 1-5 ratings in a column. The problem here is that a single row is updated 17000 times vs. an update frequency of 5 for a column. Obviously, this might give rise to a very quick imbalance in the model and maybe trying out different learning rates, one for columns and one for rows may be an answer. Some practical experiments there however have shown that this further destabilizes the model... so what can you do?? :).

Netflix prize revisited

The netflix prize has been over for some months. I ended up 215th in the high score table. Considering my involvement over time, it's probably where I should have ended up. Other groups have been at the prize for three years and rightfully ended up in the top 40.

If you still have a research interest in the Netflix prize, you can still download the data from the UCI Machine Learning Repository. This set also includes the actual ratings that were used to rate the submissions. It also includes the winning submission set.

A very interesting implementation for solving this problem is the PyFlix implementation. This implementation requires the downloaded data, but converts it into a binary database that is mmap-ed later into the process space. That's quite clever, because using mmap you can also dump some index or mmap some index once you need it. Certainly, you shouldn't do this within loops, but it goes to show that for performance computing, using files is generally a much better approach than databases. Of course you need to work on the files to get them to do something for you.

If you look at the Basic Usage of the Trac page of PyFlix, you'll see some examples of the very nice interface that was built on top of the data. Now, researchers often have not so much data to proof their concepts and the interface built on top of the netflix data in such a way is remarkably elegant for looking into similarities and trying out a couple of concepts from the python interpreter directly.

I have found however that a production implementation of svd or any other algorithm isn't truly viable in Python because of the CPU constraints and the overhead in a number of things. One of those things being the following flags (gcc) for the binaries built on my machine:

-Wall -march=core2 -mtune=core2 -O2

These show that the binaries to be built are tuned specifically to my processor that I am running, instead of generic "i386" architectures. I'm also no expert on Python, so there may be many ways to totally optimize python such that it runs much better. The flags above will generate code that is much more efficient and reduces a single cycle of 27 seconds on generic i386 architectures to 7 secs in total.

Although programmers don't worry about memory in general that much, since they don't need to (readibility of code and other quality attributes need to be paid attention to as well), for certain loops that are executed a very large number of times (in the millions), it becomes much more important to focus on the actual performance of that loop. This is a very nice article about memory, written by the maintainer of the glibc library of Linux. The glibc library is the glue between the kernel and your application basically and it has a number of handy low-level utility functions that every application uses (like strlen, strstr, etc.).

One of the important aspects of maintaining performance is trying to sort data (if possible functionally and technically), such that the processor doesn't get a cache miss to acquire the data. It will then be much quicker in those kinds of loops. Another kind of performance hog is the ordering of data, for example:

my2DArray[ ROWS ][ COLS ];

When cycling through this loop, you'll want to do this by rows first, then cycle on the columns. The columns are probably linearly aligned in memory, one after the other. So you'd typically iterate through this array through:

for i = 0 to ROWS:
  for j = 0 to COLS:
      my2DArray[ i ][ j ]

Compare that to:

for j = 0 to COLS:
  for i = 0 to ROWS:
      my2DArray[ i ][ j ]

The second has cache misses all over the place, which is very bad for performance. Ideally, for computational tasks you find an algorithm that both keeps data close in the processor cache as long as possible, but of course only if that is feasible.

The implementation of pyflix is sneakily reading from disk and doing quite a bit of things in the background for every iteration of the rating loop. This is severely hurting performance in the long run. The good thing is that there's a very elegant API to access the data for other purposes and this API does include a rather fast index. It's as if a very tiny little specific database engine was written to access the data, which is a remarkable and impressive feat by itself!

SVD in Python

Here's a small example of Singular Value Decomposition using Python:

from scipy import linalg, mat, dot;
matrix = mat( [[2,1,0,0], [4,3,0,0]] );
print "Original matrix:"
print matrix
U, s, V = linalg.svd( matrix )
print "U:"
print U
print "sigma:"
print s
print "VT:"
print V
dimensions = 1
rows,cols = matrix.shape
#Dimension reduction, build SIGMA'
for index in xrange(dimensions, rows):
 s[index]=0
print "reduced sigma:"
print s
#Reconstruct MATRIX'
reconstructedMatrix= dot(dot(U,linalg.diagsvd(s,len(matrix),len(V))),V)
#Print transform
print "reconstructed:"
print reconstructedMatrix

This code prints the following:

Original matrix:
[[2 1 0 0]
[4 3 0 0]]
U:
[[-0.40455358 -0.9145143 ]
[-0.9145143   0.40455358]]
sigma:
[ 5.4649857   0.36596619]
VT:
[[-0.81741556 -0.57604844  0.          0.        ]
[-0.57604844  0.81741556  0.          0.        ]
[ 0.          0.          1.          0.        ]
[ 0.          0.          0.          1.        ]]
reduced sigma:
[ 5.4649857  0.       ]
reconstructed:
[[ 1.80720735  1.27357371  0.          0.        ]
[ 4.08528566  2.87897923  0.          0.        ]]

And with one more dimension for sigma:

reduced sigma:
[ 5.4649857   0.36596619]
reconstructed:
[[ 2.  1.  0.  0.]
[ 4.  3.  0.  0.]]

This is how you can use Python for quick tests and experiments on SVD.

Abstract thought

Thought... what is it? I've posted before on the topic of consciousness and thought. Without any final conclusion, the topic of thought is discussed in philosophy with differing opinions on the matter. Some say that thought has mystic properties and is only reproducible in biological matters, some in that camp go as far to state that thought is purely human and is what separates us from animals. Could be, since there surely are specific differences in the way we learn, reason and behave, even compared to monkeys. See "Ape Genius" here for example. The last video talks about a very important difference, namely pointing. The questions posed in the research is whether apes are more or less thinking like us or share specific traits that make them behave like us. Looking at the videos and specifically the parts about cooperation and learning, I have personally come to the conclusion that there is not that much in common (the problem is that in a way, apes look more like us than, say, horses, so we're inclined to believe they think like us for that reason. But are they really the same once you completely ignore the 'look-alike'? ). Back to the question at hand... there are other streams in philosophy that believe thought is computational. Then there are once again subdivisions in that region. Some say that the mind is partly computational, but has other traits that are incredibly hard to model and execute on a computer for example.

Scientists now believe that they can recreate thought by replicating neural networks. So the idea is to think of a common task and then proof that this task can be satisfiably executed by an artificial neural network running in a computer. The problem here is that the neural network is trained for a very particular task and there is no reasoning taking place other than the execution of that particular task. So the neural network expects a range of inputs and will calculate the correct output based on those. If the inputs are out of range, the output is not guaranteed to be useful. Also, you will only get a meaningful output for a specific purpose, not an output that is meaningful in different scenarios.

The biggest problem here is that we can't think in sufficiently abstract terms and the relations between those terms. Because we cannot imagine 'pure thought', what it looks like and how it can be alternatively represented, we keep pushing buttons in the hope that somewhere we find an interesting response somewhere that indicates some kind of causality of the external world and internal processing.

In order to simulate thought in a computer, one must assume that thought is purely computational, otherwise the motivation and the execution of the research is contradictory. Pure computational thought requires us to think differently about representations and find other ways to represent parts of the meta-model of the outside world. The world out there has a form and when we see a cat, we don't pick it up, put it in our head and reproduce it later in thought. So, thought requires us to model those things differently in our minds such that they can be reproduced later. Whether this be a word or a number is not truly relevant. The relevance is related to how the relations between these concepts can be maintained. So, reasoning about things isn't exactly about representing the concepts, but about representing the relations between concepts, what things do to one another or how they are typically related.

Singular Value Decomposition, often discussed on this blog within the context of collaborative filtering, has the ability to express patterns of co-occurrence or relations between numbers or items. And here starts the rub. For SVD to be useful, the designer / modeler needs to determine the correct way to put the numbers into the matrix before the calculation is started. The model dictates for example that users go into columns and movies go into rows. Then for each combination, a number is inserted, yielding a huge matrix of interrelations between instances. The interesting thing here is then that one movie relates to many users and one user relates to many movies. So, in essence, the preference of a user is modeled within this matrix and related to the type and characteristics of a movie. In a sense, this means that preference is modeled against characteristics. We don't have any data available about movie characteristics or user preferences directly, but generating this matrix we can suddenly start reasoning with those, although the exact meaning of preferences and meaning of characteristics, appearing as numbers, may not be derive-able.

And here goes... in order to make those preferences and characteristics meaningful, one should have a classification system at hand that can compare classes with one another. Classification means comparing two things to one another and trying to find the most important characteristic that make them match or differ. That operation is different from the calculation performed earlier.

So this goes back to our incapacity to think in truly abstract terms. We can get a feeling for something, but then if it is abstract, can't describe it. Although we are certain about incompatibility, incongruence or similarity for example. A computer model where these abstracts can be manipulated and translated into something meaningful, classified and everything backwards is going to be a very important step.

I think of the brain not as a huge number of neurons that are interconnected, but I think of each neuronal group as some kind of classifier or work item. In that sense, one can question whether it makes sense to simulate 100 billion neurons if the total effect of those biological computations can be simulated more effectively using stricter and cheaper mathematical operations, or a simulation of neuron groups in a neural group network instead, severely reducing the dimensions that are (thought) to be necessary.

This is a great question for research. Can a machine that is constructed from bits, which are 0's and 1's, therefore have no intermediate state, work with numbers and symbols in such a way that it starts to approximate fluid thought?

Building a mapserver with a karmic koala

I've updated my Linux system to Karmic Koala over the weekend. It seems to work quite well. For the first time, I decided to kill all the binaries that somehow made it to my machine over a course of 2 years and do a fresh binaries install, keeping my home mount with data. That worked out well and the machine even booted my RAID-0 array with dmraid without any problems this time. Ubuntu 9.10 works like a treat, you should try it!


Getting down to business, if you want to find out how Google / TeleAtlas renders maps, here's a page that gives you an idea how the process works. A mapserver is basically an image server with a HUGE, HUGE, HUGE number of tiles behind it. Each zoomlevel maintains its own set of images basically, so that's why adding a zoomlevel to a finer-grained level will be costly space-wise. The tiles are constructed by adding GIS information of different types together from a rather large database. The tutorial that I found here is very easy to follow and the most comprehensive on the subject.

In this tutorial, they end up building a little world map, which I attempted and worked out, as you can see. The world map on the right was constructed by the information of SHAPE files on my server. The overview is a very generic image, but the information in the SHAPE file is so great, that I can zoom in to great extents and produce the complete coastline of Antarctica or any country in Europe. Thanks to the efforts of the Openstreetmaps project that is and people and organizations that collaborate with them. Notice also how the world seems to appear slightly distorted. I think this is related to the chosen projection method.

Well, once that is working, you can load your own spatial data in postgis and postgres and start drawing specific parts of your interest on detailed images. Instead of writing your own programs to do that, just use the utilities and scripts of the mapnik project. An example of that is here, central Amsterdam:

So this is great. I can now produce very detailed streetmaps of any region in Holland, reason about those places and ways through a database with spatial reasoning predicates, find out extents of regions, and so forth. Mapnik also provides scripts to generate tiles from a given 'planet' database. Tiling a country however can produce a very large amount of data on your PC, so use with care :). The above image was produced using standard styling rules. It is possible to adjust this styling or replace it entirely, such that it becomes more personal. These generated images, together with a bit of JavaScript and the original PostGis database as a backup to the locations of points of interest are at the core of Google Maps.

Well, another interesting application of GIS information is by super-imposing data from different sources over the data in the database, or not rendering specific sets of data from the source in the database so that they have less information, making it easier to focus on the important bits. You can see how Bjørn Sandvik made a thematic mapper for Google Earth by generating KML from thematic data merged with (simplified versions of) world boundaries. Although KML takes some time to render, especially when in 3D (he wrote a nice, detailed paper about the techniques though), you can generate 2D images by loading your thematic data in PostGis first, then relating your data rows with the geographical data. Using a clever query and the pgsql2shp tool, it should be possible to output a file with the attributes you require for rendering. The last step is then to spit out an XML rendering file for mapnik, which basically filters your attributes, assigns colors or other styling measures and then run it through the mapnik renderer.

There's lots of things one can do here. Be reminded that dealing with these tools can be a bit daunting at first. There's generally no need to write complicated mergers/processors, because you can use PostGis as an intermediate data store, which can output .shp files (the most portable format I reckon), which other tools can visualize or process further.

Drawing your country with openstreetmap

In some previous project, I worked with GIS data to show demographic data on Google Maps. The underlying database is PostGreSQL. This post shows how you can use (part of) the database of OpenStreetMap (verify license!) to extract features from the dataset to paint this onto an SVG or PNG image. Using the PostGIS database in combination with the loaded data, you can extract features (these are like gmaps overlays, or GIS layers) and include them in the image. You want to include railroads and regular roads? Not a problem! You only want to include waterways and the general shape of the country? Can do! The image above was constructed by taking water, waterways, train railroads and forest areas of Holland. Then I zoomed in a bit to show the level of detail.

Since I mostly use Ubuntu, I'll explain the steps used to get things done.

Prerequisites:

• Postgres 8.3 + Postgres 8.3 server-dev package
  
• Postgis
• cmake
• qmake
• libqt4-dev
  
• bz2-dev library
• geos library
• gdal libraries (libgdal, gdal binaries *and* libgdal1-dev)
  
• libxml2-dev header files and library
• Benelux or other data: ( http://planet.openstreetmap.nl/ ) (no need to unpack! 170M packed, 1.8G unpacked )
  

Then, you probably need to download the SVN version of a utility called osm2pgsql. This utility allows you to load in the Benelux data into your postgis database. You can get it using:

svn co http://svn.openstreetmap.org/applications/utils/export/osm2pgsql/

Then, make and make install. This probably doesn't copy the default.style across from the svn checkout directory to where it is expected. So:

# mkdir /usr/share/osm2pgsql
# cp default.style /usr/share/osm2pgsql

Now, you're ready to load the Benelux data:

osm2pgsql --slim -c -l -d  planet-benelux-latest.osm.gz

Ok, so let's start visualizing this for a bit. You'll want to get qgis, compile that, install it, run it and then connect to your database:

# svn co https://svn.osgeo.org/qgis/branches/Release-1_1_0 qgis_1.1.0
# cd qgis-1.1.0
# mkdir build
# cd build
# ccmake ..
(verify output, resolve errors). Press 'g' to generate scripts

Then you should be able to run qgis from the command line: qgis. This starts up the application. If you look for a couple of ESRI shape files, you can load them up and play around with them to see how things work. For the open street map data we have downloaded, we can connect to the database using "Add Postgis Layer". This allows you to select the host, database and tables to load in. It takes a while to get data out of the database, but eventually you get there and it shows all of the Benelux in a particularly bad colorful display :).

A better way to get your data out is by using multiple layers, instead of one. There are a set of utilities that can be useful to load ESRI shapes into the database, but also to get them out. Since we can use where statements, disjunctions and conjunctions in SQL, it is simple to pick out what you're looking for, put this into a shape file and load it into qgis for visualization. Note that the polygons are great for showing a bit of volume and color and that lines are more useful for borders:

pgsql2shp -f forests  "select osm_id, landuse, "name", way from planet_osm_polygon where landuse='forest'"
pgsql2shp -f water  "select name, way from planet_osm_polygon where \"natural\"='water'"
pgsql2shp -f waterwegen  "select name, way from planet_osm_polygon where not waterway is null"
pgsql2shp -f railways  "select name, way from planet_osm_line where railway = 'rail'"

These exported shape files can now be imported into QGis. Then adjust the properties per layer, specifying pen for drawing a black line around polygon areas or not (I didn't in this case). The lines only use a pen and don't have fill colors. Match wood / forest areas with green and water with blue, then select particular types for roads and railways and you're set!

Using the Print Composer function in QGis, you can now export what you've been creating. Make sure to use the Add Map button first, then export to either SVG (Inkscape?) or PNG.

Here's a page that explains the features in the database, but note that the features are not consistently used throughout the database, so you should always check your results:

http://wiki.openstreetmap.org/wiki/Map_Features

More detailed zoom-in near Amsterdam area using the same restricted set of layers and a comparison with Google Maps:


Notice how Google maps have painted areas in a more generalized way, whereas the openstreetmap image is still the original ESRI format. It should not be very difficult to start painting images of GIS data in a format like the Google one above, then overlay the original high-resolution data over those images to indicate the position of cafés, cinema's, etc...

Good luck!

Reasoning with(in) language

Natural language processing is (eventually) very much related to understanding what is being written and (re-)recognising words in the particular semantic contexts that apply. After playing around with the NLTK for a while, I come to realize that the toolkit is much geared towards analysis of specific texts, or helps in defining a EBNF representation of a particular grammar such that a particular category of text can be parsed more successfully or specific parsers / analyzers can be researched. There isn't any mention I've seen where a generic classifier (NP/VP/DET) exists that understands what words are for, more or less like an incremental learner that just goes along and finds out what goes where. Discovering the requirements for such a process is the real question. What makes up language? Why can language appear so fluid and in so many forms and how come we recognize language so very quickly after the utterance, even though that particular utterance has likely not been spoken before? Or is there indeed a difference in the speed of interpretation of familiar utterances versus non-familiar utterances? That is a very interesting research question. For now, I'm thinking up whether there are ways to discover the semantic information of words automatically, or possibly let the computer express to us that something could not be recognized or didn't make sense, so that we could tell the computer how things actually worked.

One thing that I find is going to take up a lot of time is to explain to computers how the world works. The advantage we have is the number of senses, which tells us a lot more of the combinations of observations, how these join together (specifying the situation in greater detail) and the possible consequences that could ensue (whether it's danger or normal, etc). Our language also contains words that allow us to express the particular information about observations of the senses into great detail.

What is needed for computers to start learning is to define a generic model for the world, such that objects (instances of types or classes) can interact with other objects (thereby classes), so that by observation of a particular instance, the computer must be able to generalize that instance towards a class or a class higher up the tree, continuing to find consistencies or inconsistencies in that existence. This yields a number of questions that require the computer / agent to research them for truth or false. The result could be that the class that was initially constructed isn't entirely valid, or the instance belongs to a totally different class that was not known until that time.

Most models I've seen revolve around recognizing a stream of information that refers to elements in the world and a pre-designed reasoning model that the computer uses to use those observations appropriately. But that requires up-front design and then rules out the learning of computers more or less automatically. What designers mean with "learning machines" sometimes is not learning new concepts, but most of the times it is related to learning to recognize particular situations such that the corresponding actions (which are finitely defined in most computer programs) may be chosen.

Well, I have no idea about what this model should look like, but there is no reason why it could not look like a generic model setup for multi-agent worlds. That particular situation has relations, which describe possible relations that one entity/instance could have with another and in what way. Then there are functions, which could be thought of as actions or manipulators of instances, functions that do stuff to entities. Of course, these functions shouldn't directly issue a particular action, but only manipulate the object "in the mind's eye". So there's a clear distinction between observation and the observations made about objects in the real world and this real situation vs. the representation of those objects in working memory. Only when conclusions made in working memory make sense should the computer start a 'world action' by invoking some kind of control function.

The picture above was inspired by the action of 'pointing'. Looking at animals in the kingdom there are no animals that actually point to things to teach something to others (well, disregarding the pointer dogs :). So pointing is very specific to the human learning experience and probably the one that has allowed us to learn in the first place. Pointing is about attracting a person's attention towards something that is happen, since it is considered important for learning or for other people to start taking some kind of action. So it's about teaching, but also about group behaviour and a simple way of communication. It is quite remarkable that no other animal has developed this particular trait, being such a simple one.

The expectation for many programs is that they are complete in the sense that basic functionality should work once things are bootstrapped or "learned". With that I mean that the capabilities of the program are pre-determined and programmed in, it only needs to find out when to execute those actions, which is generally determined by inspecting a pre-determined stream of information and then either learning after which sequence of patterns it needs to invoke which action and so on.

It is quite interesting how we neglect the fact that we could teach the program things as well by telling it. And even more importantly, how little research there has been so far about computer programs determining that their knowledge is insufficient to solve the case at hand and for methods to complete that knowledge such that it can be executed in the future. That to me, means that we're still thinking of the computer program as a complete specification with prior requirements that is executing a particular job.