A Radial Mind

W5100 chip garbage output

2012-01-15T01:28:00.000-08:00

I've got my hands on an Arduino + W5100 ethernet chip. This allows an Arduino to communicate with other clients over an ethernet connection.

When I compiled the example in Arduino however, there is one noticeable bug that is resolved in the newest ethernet library distribution:

http://code.google.com/p/arduino/issues/detail?id=605&start=200

The other thing is that the example code contains: if ( client == true ) , which can be replaced by a simpler ( if client ).

After these fixes, the W5100 behaves properly. On to the next challenge!

Ocelot install

2011-10-14T00:27:00.000-07:00

I've just installed Ocelot and ran into loads of problems. The install process crashed on me right when it was finalizing some updates, so I had to rerun a couple of dpkg configures. Ubuntu didn't even boot into X, nor the normal shell, but I managed to boot into a previous Linux kernel of natty.

The most important thing that could go wrong is probably the '/var/run' to '/run' relocation. The install script is supposed to copy contents of /var/run to /run, contents of /var/lock to '/run/lock' and then delete /var/run and /var/lock altogether and replace them by symlinks.

(i) create directories /run and /run/lock,
(ii) move contents of /var/run into /run and /var/lock into /run/lock,
(iii) delete directories /var/run and /var/lock
(iv) create replacement simlinks; e.g. 'ln -s /run /var/run' and 'ln -s /run/lock /var/lock'

Not doing this gives you problems like 'waiting 60 seconds for network...' and longer boot times, but X never starting. Before you think it's an issue with the graphics driver (which is also likely), make sure the above is correct and sorted first.

Charmed by pythons

2011-10-05T11:18:00.000-07:00

In my latest project I'm using Python to construct the basis for a GUI application. Because one of the main design goals is to make this as modular as possible, it is also used to construct an application messaging bus and another object to keep application data in one single place. My experiences so far are extremely positive. I'm used to formally specified languages where there is no possibility to become confused about the meaning of a parameter or what its type is. This makes it slightly easier at times to understand what a parameter is doing, but at the same time removes some of the flexibilities that these programming languages offer. Python seems to be the ultimate mix between form and function, although it takes some time to get used to the idiosyncrasies of this particular language. Once you stop worrying that your application isn't going to be used after three years anyway and that nobody wants to extend your particular piece of code, Python becomes something that you can start to embrace.

What I had to get used to at first:

How python expects you to indent your code. I set my editors to 4 spaces instead of tabs to make my life easier. Still, you download a snippet of code from the Internet and you end up rewriting tabs as spaces and vice versa.
The same indentation levels is how scope is managed, whereas C and Java use scope braces.
The ability to simply assign a variable some value and how it persists over time. There is still a gotcha or something to remember here, because sometimes variable assignments are persisted in the instance and not the class. But usually this turns up soon enough.
Some short-hand notations for iterators over collections, sets, lists, deques and dictionaries. It takes some time to get used to how double braces differ from brackets and from square brackets (they mean different things), but when you know Java and the differences between sets, maps and lists, these notations become rather natural.
How some declarations or references of C libraries eventually must be interpreted to understand which classes must be instantiated and where C-enumerated types are declared in the python bindings (at least it's consistent!)

The awesome thing in python is that it's not just something you run on the command line anymore. We're using this together with the Gtk 2/3 libraries, Clutter and libchamplain. These are highly graphical applications written in C or C++ and python with the GObject bindings give you access to all the functionalities in those classes.

The two coolest things in python is that we now have access to a very clean and empty user interface application that we can enrich using a set of plugins. If you know what a model/view/control (MVC) separation of concerns is, then python definitely knows how to support that. For our data and for our messaging bus, we've created a singleton object in the VM which every object can get to in a very simple way. Any plugin can declare data items that it wants to store and it can itself use the message bus to declare new kinds of signals that other plugins can react to, or it uses the messaging bus to declare interest in messages of other plugins.

This way, the application is 100% modular, but there's still a sense of control onto what kind of data is stored, where it is stored and it warns developers when a plugin wants to get access to data that hasn't been put there in the first place.

The plugins we've defined are all of a specific type and have their specific pre-determined uses. Communication plugins usually run in a separate thread and they're responsible for opening their own sockets. They then receive or send information from/to the system. Using the messaging bus notification signals, they extract information from the model and send this on, or they receive new information from the environment and add this to the model.

At some point though, one needs to be aware that any application can ever do so much. The multi-threadedness is highly governed by the ability of the main thread to keep up with whatever is going on in the environment. That is... in a graphical environment like clutter or gtk you can't update or manage components from just any thread, but you can only do that from the main thread that is running Clutter.main() or Gtk.main(). This usually means you add notifications to the message queue of the main thread, which is only emptied when the main thread becomes idle.

Thus... if you are in an environment where lots of user interactions happen and the UI is never truly idle, the communication message handling may start to delay by quite a bit and you may notice 'halts' in the UI updates from these systems. Because of that, this is not necessarily the way to go for everyone. But this is the best of both worlds really... you can't have blocking sockets in UI thread code, you can't/shouldn't obstruct the general UI thread with system messages (making user interaction choppy) and other considerations like that.

So, the main design concepts of this system are:

Keep data in one place wherever possible (if multiple plugins use that data, don't copy it for every plugin).
Allow data to be private to plugins when no other plugin or code uses it.
Pass in required references to objects that make sense to be externally referenced. Because the use of each plugin is clear, you can also separate these.
Communication plugins probably need a separate thread for communication handling. Be careful with blocking sockets, because UDP sockets may continue blocking forever. Therefore, TCP sockets may be blocking (as far as you shutdown and close them). UDP sockets should not be blocking.
Use a special singleton instance for a messaging bus where messages are declared on and where hooks can be inserted. This allows you to manage mbus code in one place and you have a nice intermediate class that passes signals around.
Do not pass large amounts of data on this message bus. If large, hierarchical pieces of data are manipulated, store them in one place in a model and allow plugins to query them if they are so interested on the receipt of these signals.
Define what your UI should look like. That is probably the only thing that ends up being highly specific code to the application. But if you have your mbus+model objects defined already (and these are generic), you'll find the main application window is nothing but a 'shell' from which plugin code is run and the logic is defined by what plugins do and which kind of clutter/gtk classes are contained in your widgets.

So yes... I've been slightly charmed by the elegance of python in certain expressions. It's a rather mathematical way of seeing things, but it starts to make sense a lot. The abundance of libraries, extensions and base libraries, most especially its support for Gnome repository bindings for all sorts of purposes make this a very attractive language to program in.

Ritewing Zephyr

2011-08-18T11:47:00.000-07:00

So to the right is an example Ritewing Zephyr. I'm working on building my own zephyr and the build log is on my website: http://www.radialmind.org/projects/zephyrbuild. This plane will be a joy to fly. I'm looking forward on having everything done. There are quite a number of videos on them already. Check below for some examples.

Digital Video Broadcasting... how it works...

2011-07-04T14:07:00.000-07:00

I'm reading up on Digital Video Broadcasting standards. The DVB standard is for receiving digital video back in your home. There are a couple of subtypes in this main category which distinct themselves by their error correcting facilities (based on what's needed over the medium that they are transmitted), bandwidth, etc. The DVB-S standard is one of the things I'm most interested in. Digital Video Broadcasting is usually done with MPEG-2 transport streams. Suppose you have a video on your computer and a bit of music, along with some information on what else is available on your channel. The transport stream is composed by multiplexing all the information together (rather fast) and creating one larger bitstream that can be transported using either DVB-T (terrestrial), DVB-S (satellite) or DVB-C (cable).

I had thought that analog TV would be more resilient to noise created in the atmosphere, but this is not necessarily the case. If you send a file over the ether composed of 0's and 1's, then any noise or interference in the stream may cause a bit to be misread or misinterpreted or missed. Since the playback of a file is usually dependent on all the bits being read correctly, this is where you may get huge problems already. One or slightly more bits falling over may already cause the entire stream unusable.

Unless.... you add error correction. But this increases the size of the entire stream... How then...? Well, the MPEG-TS doesn't carry nearly as much information as an analog video stream, because analog stuff is not compressed, although in the analog world you can remove some information without significantly reducing the quality of your experience (one example here is mp3). In analog video, this means you can easily reduce a bit of the color in an image, although luminance (that which you'd see as black and white) is far more important for a person's perception of an image.

Back to MPEG-2 however... digital compression standards rely on encoding those things that matter only once, where 'motion' in the video would typically require you to encode a bit more about some spatial event for example. So a green screen that doesn't change a pixel will be very easy to transmit and extremely cheap, whereas a fast-paced action movie may temporarily reduce in quality a bit, because all the parts on screen are in motion all the time.

Let's assume that we have some digitally encoded video+audio and that it is ready for transmission. For transmission in DVB-S and all the error correction abilities we need to have at the receiver side, the huge file is packetized into 187 bytes and then a sync byte attached to the start of this "packet". The interesting thing here is that this file may be rather regular in terms of how one byte and its neighbor relate to one another. One interesting finding is that equal bytes that follow up one another may cause more reception problems at the rx side than a noisy transmission will be, because there's more variation.

For this reason, each byte in the packet, excluding the sync byte, is 'AND-ed' with a pseudo random number generator (a simple one that is). This means that some bits now turn on, others turn off and this machine has a certain period over which it operates. This PRNG is reset after every 8 frames of transmission.

What we're getting now is already an interesting stream of information that's nicely packeted, more resistant to some errors. Each packet is fed through a "Reed Solomon" encoder. This is an error-correcting encoder that has the ability to correct 8 bytes of information from this packet at the rx side. So this is the first stage where we're adding additional information to the stream that is going to help us later on. Reed-Solomon (RS) is also used frequently in other mechanisms, like storage, data transfer for other applications (CD? HD? etc.). Sometimes it's getting replaced by other algorithms like Turbocoder (space missions, etc.) and so on. Just think... the images you're seeing from Space sent by those satellites also use these schemes to ensure no bits get inverted/changed during this transfer.

The next step after the RS is some interleaving. Interleaving is a process where you shuffle parts of one packet with parts of another packet. The reason for doing this is that errors typically occur in bursts, not like 'hit and run' errors. By shuffling the original position of bytes in one packet with another, the deinterleaver relocates the parts to their original position later. If any error burst occurred, the spread of the damage caused by the error burst is much lower (it didn't zero out 3 bytes in a row, but perhaps one). Thus, it makes the signal again more robust against interference and errors.

After the interleaving, another forward error correction scheme is used called "Viterbi encoding". This may in worst case duplicate the number of bits in the transmissions stream. More bits mean higher bandwidth. The challenge is to fit the entire MPEG-2 stream within around 6MHz of RF bandwidth, so both the original MPEG-2 stream bitrate as well as what happens after that is very important. If Viterbi encoding can be less aggressive, slightly more MPEG-2 data can be sent in the channel before it uses all the allocated (planned) bandwidth.

The steps after this are 'baseband shaping' and 'I/Q modulation'. This means that the digital signal is mapped to an analog signal for transmission. Words you'll see here are "constellation". The kind used in DVB-S is quadrature phase shift keying. This means that a sequence of 2 bits is taken together and mapped to some vector 45 degrees in a constellation space. Being this far apart prevents any errors that may occur and you'd typically choose that based on the amount of expected noise in the channel. DVB-C, the cable kind, has so little expected noise that it uses 64 positions in this constellation instead. This means that in theory, it has 16 times more bandwidth.

Different analog video signals occupy 5-8 MHz in bandwidth. Expressed in Mbits/sec, PAL video equates to 216 Mbits/sec, whereas MPEG-2 compressed PAL reduces that to 2.5-6 Mbit/sec. High value means bitrate when there's lots of motion, the other when there's little. Compressed HDTV is higher than that in the order of 12-20 Mbits/sec. However, this is measured against MPEG-2. H.264 encoding is three times more efficient, so this gets HD video back into reach for actual transmissions. The alternative would be to use different modulation techniques or to occupy a larger portion than 6 MHz in the transmission region.

Some issues still arise... DVB-S was specifically created for LOS conditions away from reflective buildings and other interference sources. As soon as DVB-S is used for terrestrial transmissions this may have a huge impact on video quality. Tests so far indicate this is not necessarily the case and I reckon that with the circular polarized antennas that for example FPV fliers are using for their analog video, the multipathing issues that threaten DVB-S may well be reduced to a minimum.

Quad tuning

2011-06-28T11:36:00.000-07:00

I made a post to the diydrones website some days ago, explaining some modifications I made to the Arducopter source code. A colleague of mine explained me a couple of things about issues related to aircraft control. The standard Arducopter code has the attitude controller in place and the GPS Hold. I added the velocity controller. As you can see from the diagram, this means that the GPS Hold controller immediately changes the attitude of the quad on the basis of some difference in position. The attitude controller itself just maintains a certain angle setting.

The attitude of the quad may induce a certain acceleration into some direction. When you steer a quad to some location by hand, you don't maintain the angle until you get there, but steer towards the other direction for a brief moment to zero the velocity with the intention to have zero velocity on the intended position.

My experiences with the GPS Hold code in the arducopter are poor. Others have had more success, but I could never find the right settings that made the quad behave correctly in all circumstances.

Because the GPS Hold controller controls the angles directly, but doesn't look at the velocity, it will only zero the velocity after it has passed through the setpoint. This means that with some larger drifts around a setpoint, overshoot cannot be avoided. Aggressive settings then cause overshoot into one direction; the quad then slows down, reverses direction and overshoots the other direction. Thus it oscillates around a position. Higher D-gains help in this regard, but I couldn't get this to calibrate correctly. The I-term does more evil than good and should be used very sparingly.

With the velocity controller in the middle I had more success. The velocity controller is also a better means to control where one is going. Letting go of the sticks means that the quad already attempts to hover around doing nothing. With little wind you'll see that this leads to a near-perfect GPS Hold operation. The GPS Hold code that you do put in than only removes the little offset that does take place due to small disturbances and other inaccuracies due to some dampening filter on the GPS course/speed readings.

In order to calibrate things correctly, start with the last controller going backwards. The attitude of the quad must be maintained with near perfection. Indoors in a large enough area, it should not travel significantly in any direction. If the quad does that, it may indicate:

most likely cause: too many vibrations in the quad causing the IMU to get slightly confused at times or over time. It may then tilt somewhat into any direction causing speed to build up.
motors not pointing straight up, so that propellers have thrust in the xy-plane.
Incorrect response of ESC / motor due to incorrect ESC calibration, defect motor, etc.

I cannot stress enough how important it is to remove vibrations as best as you can, because you get much better results that way. In my case, I've flown with the quad in a situation where it was moving about quite a bit in outdoor environments and making a sound like a lawn mower (you know, where the mower blades cut reeds, those kinds of 'graty' sounds). I found out eventually that my bolts appeared to be tightened, but with a proper spanner could still tighten it further by 1/4 turn. This improvement for about 5 bolts resolved the graty sounds entirely and on the next launch, it hummed perfectly. That is how much bolts / nuts may impact stability, the way how motors are balanced and in turn impact the vibrations on the IMU. So make sure that works ok.

To calibrate the attitude controller, set the tx into attitude control mode of course. Then zero I and D and start with the P setting. You're looking for a P-setting that is just high enough to cause the quad to just about oscillate. Then lower the P setting a little notch (this is a relative operation) and work on the I and D terms next. The I-gain has two purposes:

Increase the speed at which you find your setpoint.
Resolve any bias that may accumulate in your system.

The bias for example is wind. If your quad already remains very level, in outdoor environments a level quad will drift away slowly on the wind. Suppose that you're activating the GPS Hold controller. Without the I-gain, you'll drift downwind until proportionally speaking, your quad has such an angle that it finds an equilibrium with the wind conditions. The I-gain will start to kick in, increase the angle and the idea is that the build-up of the I-gain over time and the decrease of the P-gain eventually establish a new equilibrium on the exact setpoint. That would be perfect.

The D-gain is there to reduce the speed of approximation towards some setpoint, such that it reduces overshoot of the setpoint (similar to how the GPS Hold working on angles should work).

For the attitude controller, I'm using some suggested values that are not special at all: P=3.4, I=0.015, D=1.2. These are the values for my quad and mine is custom built with relatively large distances between props. It's likely that if you have a smaller quad, you can sustain some more aggressive values.

Soon as the attitude controller is stable, work on the velocity controller. This only has two variables to adjust: P and I. At some point, especially with systems that have low frequency of reads, there's no point to use D-terms anymore. The P-gain for the velocity controller should not be too high to prevent instability. The velocity controller depends on the GPS information and this is basically some complicated piece of hardware nowadays with its own filters, dampeners and other algorithms. It's likely that a high frequency GPS (10Hz) together with doppler shift readings for speed give the best results. I set the P-gain to 0.04, which equates to a 4 degree angle when speed is 1 meter per second. If this is set more aggressive, it's possible that you see a circling motion occur due to the way how ground course is calculated in some GPS's. The I-term is basically determined on the basis of how much 'angle' one would need to compensate for windy conditions (in order to still develop a certain velocity).

Since the velocity controller is already very effective in keeping the quad fixed in place, the GPS Hold controller is just there to resolve any difference in position that still does occur over times in the 20-30 second area. It slowly develops a certain velocity that the quad should have towards the setpoint and slowly retargets the quad towards a certain position. My GPS hold controller only uses a P-setting. An I-term could be added to make it slightly more aggressive, but I never felt a need to do that.

Declaring multiple variables one line of code

2011-06-08T13:10:00.001-07:00

Quiz time! Consider the following variable declaration in a C program:

float x, y = 0.0f;

What is the value of x?

Answer: undetermined

This issue hit me, after so many years of ultra-explicit programming. A colleague way back in the UK taught me to prefer the explicit style of programming, since it's less likely to fall into traps like these. So coding programs in that style looks like:

char temp[ 512 ] = {"\0"};
int x = 0;
float y = 1.0f;

Everything gets initialized immediately after it is declared, so there is much less of a probability of picking up rogue / uninitialized values that way. This style also caused me to declare one variable per line.

I decided to take a shortcut after so many years for a quick experiment. Not just that... I decided to do this within a piece of embedded code running on a quadrotor.

The above shortcut led to the uninitialized value picking up the negative maximum value for an Arduino float: -2,147,483,648. Subsequently, this value was used in a calculation to add this particular value to an existing position. The result was a negative max float for latitude and longitude. This led to a quadrotor immediately hitting the limiter of the control system (-20 degree bank angle) and taking off to some undetermined location fractions after it was told to go into a position hold mode (where it stays in the same location in the xy plane at least).

After this line was changed to:

float x = 0.0f;
float y = 0.0f;

Things started working again. Since debugging on embedded systems is a huge pain in the *&(@#$, it took me some time to find and slap my head in disbelief.

This kind of thing is really easy to read over when you review code and definitely has the potential to have immense consequences... Another thing to seriously look out for.
( the assumption is that reviewers assume x = 0.0f as well, since it's part of the same line).

Proper code for multiple declarations in the same line look like this:

float x = 0.0f, y = 1.0f;

or:

float x = y = 0.0f;

Video annotations made easy

2011-05-31T10:24:00.000-07:00

There's a project in the lab that looks at the use of some new technology and how this technology is best applied within a certain context (also perhaps, how people should change their behavior to improve the outcome). Anyway, what we will end up doing is observe a number of people and making video recordings. Throughout the experiment, these people will be talking to exchange ideas and point all noses in the same direction. At the same time, some interaction will occur through this technology, which is not easily captured on screen. However, because we deal with the tech directly, we can send events or information on a different channel, such that it can be superimposed back on video or at least related in time with certain points in the interaction.

I considered that for the purposes of analysis, it would be handy to make annotations on the video stream itself and refer to it later in time. The idea is that you can call attention or apply markers on the stream, such that particular events are easier to recognize and navigate to later. In essence, it's the same as what YouTube provides, except that we don't want these videos to be put on there yet, also because the duration of the video may be well about an hour or so.

ELAN is a nice tool that I found that has all the characteristics that we intend to use. It allows you to import an audio or video stream, which then can be annotated over the entire timeline for different events. As far as the technology events go, I've proposed to overlay that on the original video using a library called opencv. What you get is a static image that has all the events of the interaction between people, their audio, the things they did using the technology with annotations (in the form of subtitles) added by the experimenters. That way, the output video is a comprehensive output of the entire experiment, which can be replayed in good quality video players that can use subtitles in the SRT format.

Anyway, ELAN can also export to other text formats, including HTML or anything, which will also allow you to translate or transcribe entire videos and post a log of what happened somewhere. The only thing that it doesn't allow you to do yet is to output the whole thing to some directory, where you get a flash video file of some sorts, together with an HTML file + Javascript to be able to jump to each annotation from there.

Arduino MAX7456 OSD & APRS

2011-05-15T10:38:00.000-07:00

I've just finished up the hardware and software on an Arduino Duemilanove, connected to a MAX7456 OSD chip and implementing an APRS / AX.25 datastream over the audio channel. Video from a PAL or NTSC cam is fed into the OSD chip, which overlays the image with some relevant data variables. These variables then become visible to a human pilot in the form of some kind of HUD, allowing the pilot to make better decisions on throttle settings, landing, coming back home and so on.

The APRS / AX.25 link borrows most of the code for the signal sending from the Trackuino project. With the right filter and decoupling behind it and the right Fast PWM implementation, the signal quality is very impressive indeed (with quality meaning how perfectly the signal approximates sine waves at different frequencies).

The OSD used to be hooked up by a simple loop, where the OSD was temporarily turned off to refresh the video buffer and then turned on again. Needless to say, this results in flicker occurring at times and also characters sometimes appearing in wrong locations (due to the internal generation of VSYNC signals and the write operations being carried out at the same time).

The current hardware implementation uses INT0 on the arduino (Pin 2 on Duemilanove), which is connected through a 1K Ohm resistor to +5V and with a wire to the VSYNC pin on the OSD chip. This allows the chip to work already. Interesting points here:

I used to refresh the buffer every VSYNC trigger, resulting in no image whatsoever. The OSD now writes new information every x cycles or whenever anything has changed.
After every change to the buffer, you should re-enable the display by writing 0x0C to VM0.

The APRS / AX.25 link on audio was already seemingly working, but I couldn't get the data parsed for some reason. I suspected that the tools I was using ( multimon / soundmodem ) couldn't deal with the data or were expecting different formats. By closely inspecting the incoming audio signal however, I noticed some strange plateau's in the signal, as if the arduino stopped writing in the y-direction for a brief moment in time. Turned out that the VSYNC interrupt was interfering with the AX.25 modem interrupts, so I just made sure that either of these interrupts is active at any given time and wait for the other interrupt to finish before starting the other work. This shouldn't cause a huge performance problem for receivers downstream.

The RC circuit I use to clean the signal is in the config.h file of the trackuino sources:

// 8k2 10uF
// Arduino out o--/\/\/\---+---||---o
// R | Cc
// ===
// 0.1uF | C
// v

This reduces the 5V pin-out signal to 500mV peak-to-peak in the process of generating a very nice output. Together with the FastPWM implementation, this generates a very nice sine wave indeed.

It is very important that this signal is clean and sine-wave like. The slight delay caused by the VSYNC meant that, due to CRC checking at the RX end, the signal didn't validate. I caught on to this by being able to, once in a while, decipher a single slash '/', but longer strings couldn't be parsed at all.

The output of this signal goes to the mono audio in of the A/V transmitter on the craft. The audio signal is received by the receiver, is converted into a line-out, which is then sampled by the on-board ADC within my USB Hauppauge stick. The laptop can query the digital audio samples from the stick directly and analyze the signal to determine the frequencies. The frequency modulation is converted into a bitstream of 0's and 1's and eventually, the complete string rematerializes at the receiver end.

As said, there are some utilities for doing this on an Ubuntu computer. I've tried out soundmodem, which gives you a KISS / MKISS interface, but it's probably too complex for the simple purpose I need this for (which is to parse the string out of the data and hand this to some other process). I found 'multimon' as well in AFSK1200 mode and this does the job very nicely as well. 'multimon' was written in 1997 or so and works using the OSS interface on Linux, which is now deprecated (the old /dev/dsp interface ).

You can however load a set of alsa oss tools to simulate OSS devices and convert things on the CPU if needed. What I use to use multimon on an ALSA computer without having to modify any of the internal code:

> aoss multimon -a AFSK1200

This then outputs the data strings to the console.

So there you have it. One single, heavily used Arduino board to generate the OSD video stream and periodically (300ms?) send more telemetry (to your liking) to the ground station using APRS/AX.25 on the audio channel of the A/V transmitter. It is not a weight-effective means of doing this, because it adds one full arduino board to the weight, but it does handle all the processing quite nicely. You do need a 328P processor at least due to the size of the execution image that is to be loaded and the RAM that the code uses for internal buffers and so on.

HAM license

2011-05-09T11:30:00.000-07:00

Well, nothing to do with the picture at the left actually, but I got my HAM license. This basically means that I can, as amateur and non-commercially, use some otherwise restricted frequency bands to perform research and other experimentations. One of the reasons to look into this relates to my work/hobby of dealing with UAV's. These require stable control lines, where delays in reception or processing over one second may incur a loss of the craft and also relates to getting direct video feeds from these aircraft using transmission equipment and sophisticated antennas.

Interestingly, the uav hobby seems to be ever increasing, especially recently when there are more kits around that are affordable and where one can get a craft in the air for under $200. There are also more self-built models in the sky and people are fooling around with new and old antennas and finding ways of making them easier or less expensive to build.

I don't have my callsign yet. I may at some point acquire some tx/rx equipment and start listening on some frequencies and explore this world a bit further. About the exam: 2 questions wrong out of 40. This is not a bad score at all. One question wrong about the use of capacitors in a feed line to a loudspeaker and the other one was I think something about legislation.

Faster than wind

2011-03-07T12:08:00.000-08:00

How fast can you go in a vehicle going downwind in relation to the wind, using only the same wind for propulsion? Can you actually go faster than this wind, overtake it?

This is an interesting Wired story about someone who proves that you can achieve up to 3.5x or 2.8x the velocity of the wind. The real speed is governed by a number of factors, including friction and the strength of the vehicle itself:

http://www.wired.com/magazine/2011/02/ff_fasterthanwind/all/1

Hauppage USB live 2 on Linux

2011-02-22T12:15:00.000-08:00

I've used the USB live2 stick for displaying analog (tv) video on Linux, when I was still on Ubuntu Lucid. Things worked ok back then, so kept the card. Then in a flash of non-inspiration, the "update-manager" appeared and I upgraded to the most recent version. The drivers immediately stopped working and these were pretty special at the time, because I compiled them to get it to work.

I use this stick in combination with a a GoPro HD camera, which in the same timeline I did the Ubuntu upgrade was upgraded to new firmware, which allowed it to stream TV out at the same time as recording video. Great feature! Unfortunately, since the new firmware allowed configuration settings for PAL, I decided to change that along with it. This appeared the real problem for the driver problems.

On Windows the driver is getting its output and all the lights work. So I figured it must've been a driver problem. Turns out that when I configure the GoPro camera to use the NTSC standard instead, I am getting output on Ubuntu Maverick and a decent one at that. For some reason, it appears as if the combination of the driver with PAL and GoPro output is incompatible with one another.

So, if you have a GoPro, attempt to use this together with USB Live2, try changing settings to NTSC instead and see if you get output that way. By the way, I'm using this in combination with an analog video receiver and yes, the same problems apply!

Philosophy of Mathematics

2011-02-20T12:21:00.000-08:00

In my line of work, I'm often confronted with people that face problems and want to have resolved. In some of these problems, mathematics are an essential part in the resolution of these problems. In some private part of research, I'm trying to find the real origins of intelligence and find myself going way back and forwards in time, space and mathematics, trying to come up with the answers. Some of the questions that are popping up sometimes is that there may be things incomplete about the language of mathematics itself, rather than failure in trying to find the right set or sequence of equations / formulas to apply. A lot of research over the past decennia in Artificial Intelligence has produced enormous amounts of very important and interesting applications, but none of these I find exhibit a strong sense of generality in their applications, which allow the same technique to be used over and over and over again in different situations. Most AI applications require hard-wired components of machinery in order to provide any solution.

This causes one to go back in time to try to find the origins of mathematics, in search for an answer whether maths by itself is (eventually) inherently limited and whether there's a bound for reality, a bound for mathematics or whether both of these worlds will run parallel forever (they are complementary forever), or whether the abstract thought being developed in mathematics will eventually diverge from reality by so much, that we're now dabbling in the abstract model itself to find both problems and solutions within that model, even there's no physical counterpart that would be subject to the abstract problem.

If you look at civilizations as they develop language, at some point in their language they start to associate a "count" of something with a body part. Some civilizations evolve this further to start using more abstract tokens like sticks to count beyond the maximum number of body parts you may have. In simple societies, it is unlikely you need more than the number of parts on your body to explain some concept (you could also modify the definition of how you refer to something). Those which do evolve, eventually use abstract representations to refer to some abstract notion as a "count". This "count" has no other concept other than our visual perception of being some number of concepts.

The numbers 0-9 as we know them now have evolved over a rather long period of time and came to us from India and Arabia. The number system is base-10, which allows for relatively very easy manipulation of the numbers during calculus. For this reason, they were eventually adopted and used over the Roman glyphs that dominated, for example, in Italy at the time.

The reason why numbers became useful are related to trade. The problem with trade is that you need to figure out how much to give of this for how much of that. So the practical problem required some way to refer to some 'count' of this and some 'count' of that, also some notion eventually that 'x' of this equals 'y' of that. Hence, the bartering and trading very quickly gave birth to the notion of equality and thus the equation.

Geometry evolved after that and served to be able to make rather precise calculations about areas of land, as well as how to carve and build appealing feats of engineering, build houses, bridges, etc. Even though not all forms and shapes could be accurately described at that point, there were some basic rules that could be used already to help out in the engineering effort. It is for these purposes already necessary to think in terms of half objects or fractional objects, like a third of a pie or two-thirds down a bridge. Engineering also required the use of unknowns

As you may notice until now, the roots of mathematics are housed in the manipulation of the 'counts' of things... how many meters, how many pears, how many of that for ... .

Then Newton came along and decided to use equations not just for static problems, but dynamic problems like apples falling from a tree. And here we also notice introductions of for example the differential equation. What the differential actually does is chop up some event over a larger period of time into many smaller parts, analyze their behavior in these smaller parts and develop a new equation that exhibits how the system changes over some time assuming that there is not significant deviation within that system. For a singular system, i.e. one that does not interact in the abstract model it is given with any other system, this kind of mathematics is very well suited for solving problems.

After Newton, a lot of new discoveries were made primarily on the side of physics. We do not only know how to count cows, trade land and figure out how far something is, but we can also use it to describe movement and how things move in space over time (however, with important assumptions). With Newton and the mathematics thereafter, people started to feed more abstract ideas into the language. Take into account that for every addition to this language, the deliberations have to be tested against the axioms of the language itself in order to provide consistency.

The problem with more abstract ideas is that some notions may have no reality counterparts, or that the elements that they describe in theory cannot be measured because they are either too small or too big (infinity is one such example). Just thinking about infinity itself and whether it existed or not has driven people mad (literally!).

Newtonian equations work very well for situations in which you assume a disturbance and the rest of the system is free of distortions for a certain length of time and this system has consistent and homogeneous properties (friction, etc.). But for different systems, even a very simple pendulum where you deal with oscillations, even the single system without a second interacting pendulum can only be practically computed to some degree of accuracy. That is, the real exact solution is the elaboration of some power series, depending mostly on the amplitude of the system.

So there exists already a rather simple dynamic system for which there's no real exact solution possible, because the power series extends towards infinity. If we use a supercomputer to compute the exact result, we'll never be able to calculate the result solution before the point in time we'll need it. And yet... looking at the real world and looking at a pendulum swing, there's the thing doing it. What's causing this inherent problem in mathematics, where it cannot be used with 100% accuracy on a pendulum (given some assumed mass), but can be used very precisely on the exchange of goods on a market?

There's something about mathematics that's horribly incomplete yet and it's something to do with recursion in mathematics. We need an ability to compute the outcome of recursion sets very, very quickly. The above demonstrates that the model of the real world of mathematics is really just a model and breaks down for certain practical uses of mathematics, depending on the complexity of the situation.

Chaos Theory

2011-02-15T12:56:00.000-08:00

Chaos. The word itself evokes feelings of disorder, of things that are not orderly arranged, a jumbled up room full of stuff, stripes of paint seemingly without reason on a canvas, the results of the actions of satan, uninterpretable perceptions, everything that cannot be described with a simple description or looks untidy. The scientific meaning of chaos however is slightly different. It's not so much about being tidy, but about losing predictability and periodicity. The interesting thing is that from a scientific perspective mos
t, if not all, things around us have chaotic properties and are in one sense or another chaotically interfering with one another. Chaos theory researches the effect of sensitivity to initial conditions, which is when a very slight error in a volume, speed or other characteristic may lead to profound differences in the outcome of results over a longer period of time. Lorenz first discovered that certain systems are highly sensitive to initial conditions when he tried to predict the weather. He ran the simulation once and then printed results. At some point he wanted to verify his findings by running the algorithm again and to his astonishment, even after he verified that the numbers were the same, the outcomes were significantly different. The only difference was that the interpretation of the numbers by the computer were slightly truncated somewhere at the 1000th decimal number.

Normal periodic and linear systems do not typically amplify these errors, but just show a similar, linear difference in the outcome. Basically, your result is slightly off. What Lorenz found here is that after some point in time, the system started behaving completely differently from the initial run of the process. Sensitivity to initial conditions is what he discovered and he came up with a strong analogy for the phenomenon; the "Butterfly Effect". The analogy is that sensitivity to initial conditions could mean that a butterfly flapping its wings in Brazil could in theory cause a tornado in Texas to occur.

Other interesting discoveries were made by the russian Belousov, who mixed up a couple of chemicals together and discovered that it changed color to yellow, but then back again. Not only that, it was actually oscillating between clear and yellow. This phenomen had never been witnessed and at that time was seen as impossible. For that reason, his paper that he submitted to a journal was straight-out rejected. Even after a revisal nobody wanted to publish the results on the basis of lack of evidence. It was only years later after informal circulation in Moscow that eventually the results were picked up by Western scientists, who improved the experiments further and demonstrated that a petri-dish with a certain solution of chemicals may eventually demonstrate autonomous oscillation, autonomous meaning without induction of external disturbances. Thus, a system which switches between states in a temporal manner. The actual patterns that occur in such dishes *may* look like the following. The interesting bit is that this is dependent of..... the exact initial conditions!

As for the pattern itself... there's another great scientist called Benoit Mandelbrot, who's not a typical mathematician in the sense that he knew algebra very well :). He studied in Paris in the 2nd world war, so naturally the study was frequently interrupted. Also, he wasn't always that much interested in doing math tables and all that, but instead he had a great visual attention to detail. This made him look at coastlines and mountains and discover recurrences of smaller details in larger ones and come up with the idea of a very simple formula, describing a hugely complex shape overall. He called that a fractal:

The idea is that a very simple formula, z <=> z^2+c, gives rise to the picture above (calculated in the complex plane of course and where the result does not escape to infinity. The figure is self-similar in the sense that one can zoom in on the image and discover that the same shape is in many other different smaller locations at a fraction of the size, but in this case equal to the first one.

The interesting idea here emerges that very simple rules of interaction between elements can produce hugely complex systems at a larger scale. The complexity of the figure and the simplicity of the equation should give you some idea of that power. The relationship between the two has always been quite clear from an intuitive perspective, but reviewing these mathematical details suddenly changes that.

Chaos theory has put the world of Newtonian physics upside down. The idea of being in control of particular phenomena or occurrences just because we are able to predict it (to some extent).

The notions of chaos and order are not necessarily exclusive. In the majority of cases, when scientists mention chaos they do not mean "100% randomness" in their discourse, but they probably refer to: "some chaotic elements involved that deny a straightforward linear solution to the problem". This is because 100% randomness in systems yields no patterns whatsoever, just white noise. Therefore, there is a grey area between the notions of order and chaos and in many cases, when you feed energy into a system that behaves periodical, at some point you'll push it into chaos, where it'll behave unpredictably, but may eventually return to predictability and periodicity again, although that pattern of order may be different from the one you had before. Many systems, given a certain feed of energy, swing back between the two forever. This is what the Lorenz attractor at the top demonstrates, as well as demonstrating how the system is highly dependent on initial conditions (here, interpret this as infinitesimally small differences in the initial condition, the reciprocal of infinitely large).

What is different in mathematics when you compare Newtonian physics with Chaos Theory?

The expressions in chaos are very simple, but recursive.
Chaos math usually deals with interactions between systems or elements.
Newtonian physics require orderly systems to be able to predict what happens.
Chaos has its own cycles and may skip from apparent order to chaos and flip between the edge of chaos and back without warning.
When you put too much energy into chaotic systems, they become totally unstable and generate totally unpredictable results, leaning towards randomness the more energy you put in.

New kind of science

2011-02-12T11:32:00.000-08:00

I'm reading a book by Stephen Wolfram, which is called "A new kind of science". I picked up the title after viewing a number of very interesting lectures on YouTube from Robert Sapolsky at Stanford University about "Human Behavioral Biology". It is a privilege to be able to peek into his classes this way. One of the lectures is dedicated to cellular automata and he's explaining their relevance to biology. There's a book mentioned from Stephen Wolfram, so that's how I got there.

Anyway, there are very mathematical ways to explain how CA's work, but here's Wikipedia's one. One way to look at CA is also as a kind of state machine with many different states at very short intervals from one another, where these states are actually macro-states, the global sum of internal states of each cell. Because rather small changes in internal states can significantly affect the global outcome of the global state, the horizon over which one can make calculations to derive future states is rather limited. I.e., one needs to calculate every state inbetween in order to find the final answer.

Some three centuries ago we started discovering/inventing physics laws and formulas to make our lives easier. Nowadays these laws and formulas were used to construct airplanes and we went to the moon with them. Most of these laws come with rather large assumptions. Most of the time, it is:"Assuming nothing happens that introduces a significant error, we can derive our future position/velocity/acceleration by multiplying x with y over a z time period". We're just lucky that macro-objects like our vehicles behave that way in a consistent manner.

But looking at smaller interactions or larger systems like the weather, we can't use those laws as directly as that. The number of collisions and forces between objects make the entire thing so complex, that you can no longer work with laws that require these assumptions. So the complication is that you now have to represent many other bodies interacting with your system and calculate the state of this "universe" or "world" for each intermediate state, until you get to the goal state you want. Luckily the interactions are not usually really complex when you get to an appropriate level. Unfortunately, exactly knowing these interactions remains difficult in many cases and very slight differences in the "rule" can eventually produce very large deviations from the overall pattern.

It is the expectation that this kind of thinking will produce more understanding about the world around us, as there are so many processes that function according to these principles:

the billowing of smoke and vapour
pressure of gas
the way vortexes are produced by wings
interactions between neurons?
the structure of snowflakes
the ways how cells react to other agents?

Also really interesting is the way how such cellular automata can be used in combination with stochastic processes, the idea being that knowledge may not be complete for each "cell", but given their observations so far, they may like to assume certain facts about the overall structure and modify their behavior accordingly.

TryCopter

2011-01-29T05:02:00.000-08:00

Here's a video of a tricopter I was building:

There were some issues to resolve, but nothing much out of the ordinary. The biggest problem was ensuring the right firmware is loaded on the controller board and that this firmware functions properly. I bought the blue controller board from korea (www.kkmulticopter.com), but in my case the "blue board only" firmware created problems with yaw compensation. Most notably, the correction for pitch was the wrong way around, so if I were to fly this thing for real, it would have flipped over head over heels, so to say.

Other than that, there are loads of upgrades possible for this thing. My first approach was to ensure I can get this thing to fly. Other attempts will focus on more precision of the frame itself, possibly attaching my ArduPilot Mega controller board for GPS hold / altitude hold and those kind of applications and it would be very nice if I could use that board for more precision when flying.

Brazil's progress

2011-01-03T13:30:00.000-08:00

Taking a bit of time off in Brasil, I'm really surprised by the changes that have taken place over the last 2-3 years. The first thing that one notices after disembarking an airplane is the large number of cars that are circling the roads nowadays. The cars themselves are no longer the usual about-to-break-down 9-15 year old Fiat Uno's anymore. Brasilians nowadays drive Honda Civics with the same options and luxury as in Europe (although Flex choice here is probably unique), the chinese are exporting their cars over here, you see large Hyundai 4x4's, Range Rovers, Mercedes, BMW and a lot more normal cars that are more reliable than 3 years ago. Indications that the global crisis that has hit Europe and US hasn't in the least bit hit anything in Brasil. There are now small funds available here and there for starting companies, the business itself is becoming less this-and-that, the people at the beach that used to walk by now have handcarts or Puchs, for those people that have made a name for themselves and/or sell reliable products.

In fact, the Brasilian analysts are commenting that yet another middle-class has surfaced in Brasil, which I somehow guessed due to the disappearance of the garbage/bottle collectors that used to roam the area around our appartment. It seems that the poorest of Brasil don't need to go as far in the city anymore in order to survive. My guess is that the poorest are now roaming around the outskirts of the city, closer to the poorer suburbs.

A disadvantage of the development is that these changes are taking place so fast that it is impossible to keep up with infrastructure. Building hospitals, roads, trains, metro's and all that takes time and there are likely not enough people to provide the capacity required to build all that even if the planning would be ready. Besides that, any type of construction requires engineers and engineers is exactly the kind of people that the world is short of.

The city I am in has also been built on the perspective that there are no serious changes in the economics of Brasil, for example considerable increases in salary or requirements of role/ability. The high-rise buildings are spread around the city and you could assume that each one of those appartments owns a car. The problem starts when those people purchase a second car for the wife, or even a third or fourth car for their children. One family, four cars. It is a good possibility in this city if the wages allow it, because many people still do not feel safe enough to walk on the streets or take public transport. The car as a status symbol, even if it's just a trodden down Fiat Uno of 6-year old, still better than taking a taxi. Probably, with the amount of traffic in the city, it's even a cheaper option.

The concern here is not so much the traffic on the roads or the traffic jams, but the result of a never-ending traffic jam in the city and what this does to people. Three years ago there were times in the city that you could just pass through and not be bothered much by any other car. Now people get delayed easily by 10-30 minutes per trip and this is costly to both their time available for family / business, as well as their health (nerves).

A small trip to the beaches in the south is a clear demonstration how in three years time, people are now reckless road warriors, competing for their own piece on the road. Even though the objective is to go to a tranquil place near the beach to relax after a long weekend, it seems that the haste of Europe has now been implanted in their brains and they seek to pass cars in front of them by any means possible, resulting in dangerous situations everywhere you go.

About every 10-20 minutes, there is a reckless driver behind, on the side or before you, trying to take another opportunity to move one car ahead in the long line of cars that everyone is part of. Family of mine driving in PE counted the number of hours on the road and the number of road deaths or very dangerous situations. They counted 6 such situations and have been on the road for a total of 6 hours.

One of the problems with such growth is that only few people drive defensively. Most drivers on these roads are offensive, they try to pass on every side, only thinking about how they left their homes 30 minutes late, then lost another 20 minutes in traffic and how to make up for that lost time. My advice to Brasilian drivers would be to take traffic into account, plan their days before and take safety seriously. From here on, the traffic in the cities will only get worse as there is still no end to the increase of car sales. The government has been very slow to respond to increase the road infrastructure and reliable public transport is inexistent.

So... even though the economic situation in all of Brasil and especially Pernambuco is very favourable, there are serious challenges ahead for the president and all governors to ensure that this growth will continue. One of those challenges is good, reliable public transport that also middle-class people will want to take advantage of. And invest in more road police work and make it work smarter. A lot of drivers are so badly mannered, they pass in convoys on the right and left in order to get ahead. They do that because there is no police stopping them. A good measure for people using the hard shoulders, reserved for ambulance and police is to be waiting at the end at a large terrain, where every individual can be fined in all tranquility. Who cares if they have to wait three hours before they can continue their journey?

Possibly, a number of new campaigns are necessary for awareness in road safety, educations in driving behavior and so on for the road situation to become more bearable for those drivers that are more serious and responsible.

Optimization in scheduling problems

2010-11-30T12:25:00.000-08:00

The CSP solver talked about before is an effective way to calculate all possible solutions. Some problems however are either underconstrained or just have a very large number of possible solutions. In those cases, exploring the entire solution space may be very expensive; or certain application areas may be subjective to particular time windows in which the solution must have been developed (dynamic scheduling problems). Even in dynamic scheduling, there are differences with regards to the exact time window that is allowed. A scheduling system for shipping berths for example has a different allowed time window than a scheduling system for elevators.

The image shown here is a 'fitness' landscape. It's a bit of an imaginary landscape that displays how effective or costly a solution is. The peaks are desirable solutions, whereas the valleys are much less desirable. In this case, it's a one-dimensional graph, but for other solution spaces it could well be more of a 2D or even 3D space. The number of dimensions for the fitness landscape is actually determined by the number of cost functions you have.

This is where we get to the optimization part. A cost function is a function that determines the cost of a range of tuples that are (part of) a solution. This cost function is what guides the desirability of a certain solution and that is what basically drives the optimization. Ideally, one would like to find the best solution first. In reality, the best solution doesn't come first without a bit of back-tracking. Even worse, there is no guarantee in practical planners that the best solution will be found, only a solution that is 'good enough' given a certain threshold.

If you've paid attention, then I've talked about the use of a 'cost function', which actually only calculates the cost of a particular solution so far. So how does one actually form very good solutions? Because this sounds like it's more like trying out each possibility in turn until we're happy with the solution so far? This is why the cost function must be paired with a heuristic function. The cost function is used to calculate the actual cost/benefit. The heuristic function is used to calculate the expected cost or benefit for using the valuation in a particular domain variable over a slightly further horizon.

This is not exactly all. The cost functions do not have to be commensurate or agree with another. Sometimes a particular tuple choice is good for cost function A, but very bad for function B. So the balance between the importance cost functions must be determined prior to starting the solution process. Most cost functions are pretty linear, but it's also possible that continually preferring solutions that favour function A eventually raise the costs non-linearly, such that further in the solution space function B becomes cheaper than function A. Those are very difficult to solve.

There may also be other situations in which you don't want the ideal solution, but want to allow for a certain flexibility overall. For example, in a schedule for berthing ships where you expect changes to occur, you might want to favour a solution where a minor change in the schedule doesn't flip the entire schedule around, but where the change is constrained to one or two flips between tupelizations (because the more tuples are flipped due to the change, the more costly the change will have become).

Optimization is rather difficult to do effectively and it's an NP-complete problem. So either you arrange the computation power to go through all solutions, or find better methods to achieve proper solutions. There are two ways to do the optimization. You could try to do optimization at the same time as solving a CSP (basically, define the ordering of values for a variable when tuples are picked), or generate some schedule that is more or less good and then try to improve it through local search.

Local search basically means that you have a complete schedule, but pick two tuples of a set and flip valuations around (whilst preferably not violating the constraints) in the hopes of finding a schedule that is slightly better. Local search however, if you look at the image, is a bit tricky, because you may have to force the solution to go through a valley. And how can you tell whether the solution, when going up another hill, is actually going to be a solution with a higher peak than the one you had before? And if you're just going to try this out, how do you prevent the exploration of the entire solution space, which is what you wanted to prevent in the first place?

Basically, optimization is a bit like navigating a landscape in fog. You get only slight clues that there's a hill or a valley and at some point you must decide whether to carry on downhill to eventually find another monsterpeak, or stop searching altogether and call it your best solution. That is very difficult to do without a map. Constructing the map is equal to calculating the entire solution space.

Sudoku, CSP and playing with sets

2010-11-21T05:21:00.000-08:00

Sudoku is solvable as a constraint satisfaction problem. It is described as a problem where you should populate a grid of 9x9 tiles with numbers ranging from 1-9 in such a way, that there are no duplicate numbers in a row, column or local tile-block. Because an empty grid would allow you to derive any combination imaginable, the puzzle starts with a reasonable amount of number already filled in, usually in the order of thirty something. A naive approach in solving the puzzle uses a brute-force like mechanism: - Start from the first empty tile, determine which valuations can be made, continue to the next, etc... A much better and clever way to solve the puzzle is to find places where only one value is possible, fill this in and see if this modifies the state space, such that another single valuation can be made in a different location. I've taken some time to try to solve this puzzle using the CSP solver that is running on the database. The first naive approach took over an hour and still did not return a single solution. The second approach however worked out to a solution under three seconds. It can solve very easy puzzles as shown here, but also the hardest of them. Harder ones just take slightly longer, because there is less information. Here's how my state space is organized and queries operate:

Create a table to denote the grid. Each record denotes a single tile as a column, row combination and also records to which block that tile belongs.
Create another table that records per record the valuation for that single tile, the tuple.
Inspect the puzzle and create tuple records for each already given number. These constrain the valuations you can make from there.
Then launch this query every time there's still some tile left to evaluate:

select sc.col, sc.row, count(*) as count from sudoku_cell sc
left join tuple t on sc.col = t.col and sc.row = t.row, my_values mv
where mv.some_assignment not in ( select t.assignment from tuple t where t.col = sc.col )
and mv.some_assignment not in ( select t.assignment from tuple t where t.row = sc.row )
and mv.some_assignment not in ( select t.assignment from tuple t where t.block = sc.block )
and t.assignment is null group by sc.col, sc.row order by count asc;

The result is an ordering of tiles, described by the number of valuations that can be made for each specific tile, given the current state of the puzzle. Of course, when you have a tile there where one valuation can be made, that brings you one step closer to the solution.

How does Sudoku help us to understand human reasoning better and how computer algorithms work in comparison to human reasoning?

All this work with SQL got me thinking about the method that computers use in reasoning from the perspective of set theory. Reasoning in computers is highly dependent on set theory, especially when you use SQL like I do. Logic in computer programs are basically running sets through algorithms that determine if a member is part or not part of a set (unions, intersections, etc.). Some sets are made to relate to one another through attributes or keys from either member of each set.

When you want to do anything useful in SQL, you need discriminators that determine the scope of your set and then operations from one set on another. Sometimes the relationship is a parent-child or a direct relationship from one member to another, so you can join the elements together to form a superset. Sometimes you wish to eliminate those values that are apparent in another set without attempting to make a full join. A lot of logic in SQL revolves around the use of "WHERE x NOT IN" or "WHERE x IN" kind of statements. So how does this all work in general? No matter what the query, you typically start out in a form like:

SELECT x,y,z,... FROM TABLE abc;

and very likely, the next improvement to this query is an attached WHERE statement, which reduces the returned set to those values that do not violate the conditions. Another mechanism used for querying is to join tables together on some suggested relation and on the basis of that relationship, further limit the returned results (mostly on attributes in the rows of the related table). This allows you to make rather complicated queries like: "only return those cats that have more than 5 kittens" or "query all orders that have line items higher than threshold X, created between now and three months ago".

The reason for mentioning this is that it may help in the future to construct queries. If one set is empty, it cannot have any effect on another set, because they are fully disjoint. So in order to do anything useful, your query must return rows, at least one.

A tougher example is what I had to do for the Zebra puzzle. There are cases where you have a rule that discriminates members of a set. There may also be no rule. So you can't depend on any useful result returned from the rule query. The idea is then to return all rows unless there's a rule that dictates some should not be returned. The eventual query for solving the puzzle turned out as a very complex beast with multiple IN, NOT IN statements. It's probably helpful to describe them a bit here:

SELECT all colors that can be assigned to the current house being considered, where

the color is not already used in a tuple,
the color is not in any rule that specifically binds the color to a different house,
If there's a rule that dictates the house I'm currently considering has a certain color (a set that is composed of one color), the color must be in that set (return 1). If no such rule exists, return all possible colors (so if no rule exists, allow any color as long as this particular rule is concerned),
the color is not in a set, composed by rules that are active on houses to which I'm not a neighbor. So if a rule dictates that a house must be blue and I am not a neighbor to that house, then exclude blue from the set,
the color is not in a set, composed by all colors that are determined by rules for which the rule dictates the neighbor of the currently considered house should have that color. So, if a rule dictates that my neighbor's house should be blue, then the currently considered house cannot be blue.

You can understand that such reasoning causes programs to explode in complexity. The logic interpreters like Prolog hide a lot of these details (backtracking, generation of possible values), but at some point you may want to start optimizing how sets are generated, which is where you get similar complexity. And you can only be effective when you know how exactly the interpreter is handling things for you.

In Sudoku there's a similar issue that is easier to understand, but not often modeled in solvers. For example, given the above specific sudoku puzzle, the computer finds that column 4, row 1 and row 7 both have one possible valuation. When I solved this puzzle by hand however, I was not immediately drawn to those possibilities, because there are lots of openings around those tiles, so instinctively not a place that could lead to a quick inference. What I did notice very quickly is that tile (9,8) can only contain a 7 because of the two columns 7 and 8 both containing a 7 and the rest of the tile block being populated. The constraints that the computer is using however still do allow a valuation of 1, 2, 3, 6 or 7.

This is the kind of knowledge of experts. Reasoning very quickly over many different sets of data, instantly reasoning over intersections, unions and so on. There are some visual combinations of elements that are very quick to analyze for humans, but which pose challenges for computers. Those quick analyses are very interesting to look at, because it's mostly expert knowledge that is not easily converted into some problem statement or constraint:

For a specific tile block, determine the set of possible valuations in that tile block that are still to be made. This is set X. Then count for each valuation the number of tiles it can be legally assigned to in the tile block. If there is a valuation with only one legal tile allocation, this is the placement to make.

In order to understand this, we need to have an idea about the relationship of one tile with another. This relationship is that one tile is placed in the same block as another tile. Limiting domains is a good way to increase performance if the cost of doing that is less than traversing the possibilities in brute-force. Such complicated relationships are not often modeled in reasoners due to their complexity, but as you can now see they are often and quickly used by human reasoners.

It's difficult to combine these results in one particular query or reasoning mechanism. Another way of looking at this is that they are different strategies for resolving the problem. The problem is only concerned with the tuples, the more there are found the better. Trying out different constraint combinations and understanding how at a higher level these change the solution space is a very important concern for such problem solvers. A downside of this is that the state space and complexity goes up significantly, but at the benefit of finding solutions much faster or much better than a standard CSP can guarantee.

Constraint programming

2010-11-11T13:06:00.000-08:00

I've blogged before about the difference between inductive and imperative programming. I've started to look more into constraint satisfaction problem programming, which actually able to provide you with solutions to a surprisingly larger amount of problems than you'd initially think. Typical examples of CSP solvers include the textbook examples like the n-queens puzzle, the region coloring scheme, the "SENDMOREMONEY" problem, the "Zebra" puzzle, eight number puzzle, Sudoku and so on. Real life examples tend to go down the route of static scheduling problems. I explicitly mention "static" here, because dynamic scheduling problems are those with the potential to vary significantly over a very short amount of time. A famous one for dynamic scheduling problems is the choice of the actions for a set of lifts in a busy skyscraper building. There are expectations from lift users to be served within a certain amount of time (requiring the insight in the required capacity at design time of course), but also the strategy of the elevators per individual and as a group needs to be adjusted.

But I digress, because static scheduling problems are rather similar without explicit time constraints on calculation duration. Typically, the values that you consider for CSP solutions are in the numeric, boolean or finite domain (sets). For example, you could have a domain that dictates whether a truck is used or not (boolean), how many hours it would take to perform a transport (integer), or in which timeslot or time of day a particular transport is initiated (set/finite domain).

There are various approaches to CSP. Many academic research papers mostly worry about the algebra and theory notations, mostly the functional and semantic correctness of the algorithm, which means that they mostly worry about constraint violation or not, not necessarily complexity or how long it would take to run the algorithm.

A naive approach starts from the brute-force approach. Just run through every possible combination in your entire domain set. Then verify for each combination you come up with, verify if any constraint is violated and then backtrack and try something else. This approach will take a very long time.

This is where it is useful to start applying as much knowledge as possible you have about your domain. I see the following concerns for resolving a CSP:

The primary concern is that the solution does not violate hard constraints.
The secondary concern is that it runs in reasonable time.
The tertiary concern is that it provides a good enough solution early on, ideally the first solution.

The concerns should be considered in the design and implementation. Actually combining variables from different domains together can be called tuplization, the action of constructing a list of tuples which form the solution. The domains may have the following properties:

Some domains have less elements than others and invoke more constraints. Start with the domain that has little elements, but most severely restricts future possibilities. Backtracking can be reduced by the order in which you process domains.
There is usually one domain, usually the first domain that you consider, which you only need to traverse once. So, if you have a domain {A,B,C,D}, then taking A and finding all combinations where A is valid, then B, then C will find you all the solutions. There is no further need to process {B,A,C,D}, {C,A,B,D}, {D,A,B,C}, etc... So traverse this domain once only in the order that is given.
Variables in domains may be ordered by (contextual) desirability.
Some domains have variables that can be used more than once, sometimes even unlimited, although they usually have some relationship with other variables in other domains that eventually reduces this domain as well.

Can you implement a CSP solver with an imperative programming language? Yes, but there are considerations to make on the approach, most specifically the algorithm you wish to use for exploring the search space. I consider that for CSP solvers that apply lots of knowledge benefit more from a depth-first algorithm instead of a breadth-first algorithm. The reason is that I do not think it is very effective to verify the constraints each and every time you wish to perform a selection, but you should maintain the state in memory as you pick the tuples out (and roll these back afterwards).

For example, consider a scheduling problem for a university. You have classrooms, professors, timeslots (hours) and students. These domains need to be combined in such a way that:

Every student can follow all the registered courses
All courses are taught the correct number of times per week
A professor is teaching a course, but never teaching two courses at once
A classroom is not used for two different courses at once
There may be a preference for the time of day a course is taught
Ideally, there are no hours between courses for any student on any given day (courses taught are consecutive)
Some professors may have registered time off on particular days
Some professors may indicate preferences for time off, but not as a hard constraint
There may be preferences for using classrooms that are close together for consecutive courses
Classrooms are typically used for particular departments of study
Some classrooms are available for exceptions only, but are typically to be avoided (auditorium)

So the CSP here has a number of hard constraints (such things that when combined, would invalidate the overall solution), but also a number of preferences (those things that bear some cost when it needs to be used, but can be born or considered if there is no cheaper alternative).

In the above constraints, it is probably cheaper to maintain a large 'status list' for each room, professor, timeslot and student, such that it can be easily verified whether a tuplization, given the current state of the solution, would violate a constraint or not. Better yet, with a simple query, it is now possible to select only those variables from a domain which are still assignable, given the current choice of variables in another domain.

Many CSP solvers use C++ or Java constructs with huge libraries to maintain this state for you and attempt to expose a usable, although probably not complete, interface for you to manipulate. Any CSP engine should attempt to leave the manipulation of state space (those modifications you think you should perform to maintain a correct view of the situation) externally to the engine, but guide the user in the process of performing the tuplization. Or rather, it is rather easy to develop an engine that lets an application engineer insert a couple of domains or functions that provide these for every tuplization step, which also allows for pluggable points to perform changes when one tuple has been selected and of course steps to undo those changes.

Now connect a CSP engine to an SQL database, then you could use the functionality of the database engine (indexing, transaction management, transaction isolation, tables, type checking, flushing to disk, etc.). The SQL then allows you to query at each tuplization step what the remaining elements are for each domain. You only need to order those elements to improve the order of desirability of the selection you are making.

There are no guarantees for finding optimals here, so the ordering and other heuristics are still guesses overall (that a selection will not have severe negative effects on possible future selections, increasing the cost significantly). But you know that the selection process for variables in the domain only provide those variables that actually can be assigned sensibly, given the current partial assignment of variables in the tuple. This is why the order in which you process domains is important, it has consequences for how much knowledge you can apply in the model and the position where it can be applied.

Neural Dynamics

2010-11-08T11:50:00.000-08:00

One of my main interests is understanding the dynamics within and between neurons that allows them to tune in to the behaviour of organisms which is in the interest of that organism at a higher level. In previous posts, I discussed a mechanism for these neurons to be excited by neurotransmitters released by a pre-synaptic neuron using, mostly, regulation of ionic fluxes (currents) through ion channels within the membrane.

The problem with these channels is that they are not linear in nature, but exponentially cause the opening of other channels (or inhibition).

Although it sounds like these are great mechanisms as a basis for intelligence, it's only the basis of operations for transmission of a signal from one end to another. Moreover, the channels do not typically behave the same way, because these are open for a different amount of time. So the voltage being measured is the resulting voltage from the sum of channels opening and generating some current. Each channel by itself can be associated with a particular probability for opening or closing and for a certain amount of time. Only at a macro-level when you assume, say, 1.000 channels, will it look like following some binomial or other probability distribution ( which is what also generates the nonlinear behavior at a macro level ).

So the fundamentals of neuroscience are providing a slightly more complete picture of the entire dynamics at work. Where the ion channels provide a mechanism for propagation, summing and integration of signals, it does not yet explain a useful integration and propagation as such. The synapse is still a very mysterious field of research with mostly speculation. It's still very much a mystery whether the famous Hebbian rule of "fire together, wire together" is a reality or more like some probabilistic phenomenon observed most of the time (but where the real dynamics are slightly more complicated).

Interesting discourses related to the power of integration of neurons can be found in the connections of axons from several pre-synaptics towards the dendritic tree of a post-synaptic one. Most neural models connect the axon more or less directly to the neuron cell body, thereby only allowing for the summation and integration of signals at the level of the soma, where all signals come together. The branches in the dendrite tree however may already perform a couple of integrations prior to the voltage potential reaching (or not) the ion channels near the soma, where presumably the action potential is actually truly activated and propagated.

The result here being that some signals, due to their proximity, can lead to very different results when added together at a local level, rather than at a global level. The underlying reason is that an inhibitory signal can entirely cancel out another signal of different magnitude (so the result is not necessarily mathematically correct). A good example of these effects is by looking at formulas in maths. Integration at the level of the soma would equate to a formula like:

Y = A - B + C + D - E

But integration at branching points in the dendritic tree can cancel out any prior summation of positive signals just by applying a signal of similar magnitude on a place higher up (lower up?) in the branch, so you could get:

( C + D - F - G + H + K + L - M - ....... whatever .... ) - E = 0
Y = A - B

The difference here being that the placement of connections in the dendritic tree is important and that there is only a certain range available for excitations or inhibitions. So besides 'just' integration of signals, this suggests that certain more or less 'logical' operations may also exist, which can be very useful for more complex separations of data and signals. It must be said that this tree is not necessarily typically "logical", as some effects have been noted where activations at the remotest end of the dendritic tree cause increases or decreases of the action potential at about 200-300 um into the axon. So the real effects of how neurons connect to one another's tree is still food for thought.

All this is speculation of course. The most useful thing that a neural algorithm needs is a better learning algorithm. Most of these algorithms in classical neural nets are back-propagating ones. This means you measure at the output, calculate the error, then back-propagate this error within the network to follow some kind of gradient. You need the derivatives from the neuron activation functions for this to happen.

If you want this to work in nature, you'd need a second brain to calculate the error and then have this applied inside the network. Hardly plausible. Somewhere is a mechanism at work which has local knowledge only and which adjusts the synaptic efficacy accordingly. This adjustments taking a certain amount of time and which is highly regulated by Long Term Potentiation (the ability of a neuron to become more excitable over a longer period of time). It seems that all in all, there are certain time windows where a neuron starts to synthesize proteins, which eventually modify the behavior of the neuron, change the structure or otherwise influence the synaptic gaps (by making more synaptic vesicles for example).

ZeroMQ

2010-10-16T07:35:00.000-07:00

I'm evaluating a couple of products for a larger project at work. The project will use at some point some kind of distributed storage, which may possibly be filled by the "ceph" project. Although it is experimental, there are a good couple of features that work already. For these evaluations, I've looked at some other work that has been done in this area. Most notably of course is the work that Google has done (GFS, Chubby, Percolator and BigTable). Some of the concepts described there are also implemented in Ceph, most specifically the Paxos algorithm for reliable replication.

Distributed storage is great for anything you'd like to query and which should be available 3-4 seconds after the data is "created" (although it's very likely created earlier). Distributed storage though is not a very good basis for broadcasting/multicasting/unicasting data as fast as possible after it was produced, because clients end up polling the file system for changes. For efficiency's sake and your own sanity, it is then better to use some kind of message queue. Two main architectures here: "bus" and "broker". The bus is basically a local subnet broadcast, where everything attached to the bus will have to parse messages and discard them if there is no interest. The broker(s) can be configured to receive messages from producers and route them through some broker network, reducing the number of times messages are copied and thus get re-transmitted through a separate link. Buses are useful only if you want all servers to know about the data, or the majority of them. Brokers are useful if you have geographically dispersed locations, want full control on how data is retransmitted, etc... Some brokers can also act more like "hubs", if you follow the "pubsubhubbub" project.

Sidenote: if you can avoid 'realtime' and mq altogether and do it through some file system, I'd recommend it. The concepts are simpler, it's easier to deal with faults and should you need any group locks, then the file system, even the distributed one called ceph, will be able to provide that for you. A mq puts the onus on the client for data caching, storing, reordering and all that. So file-based applications are always easier to write (at least from the client perspective :).

A quite complete evaluation of message queues was made by SecondLife. Note what is said about "AMQP". I believe that standards should evolve from things that work and not the other way around. For more information, check out:

http://bhavin.directi.com/selecting-a-message-queue-amqp-or-zeromq/

http://www.imatix.com/articles:whats-wrong-with-amqp

I've downloaded 0MQ and decided to give it a spin. The first thing I did was visit the IRC channel on a saturday and there were 50 people in there. That's usually a very good sign it's quite popular. There's a good chance that 0MQ is getting some serious attention soon. It may not be the absolute topper in performance speed, but it may be best if you're looking for flexible solutions, prototyping and esxperimentation. Having said that, if you're not running a super-duper high-performance site that needs to squeeze all the juice of your CPU's and NIC's, ZeroMQ will do just very fine for you, no problems whatsoever.

To set the expectations right... it's a bit more of a library for internetworking your applications together using multicast/tcp/ipc protocols, but that's already a big gain if there's a library that does that for you. This is typically a layer where many developers think they want something special, but ends up being the same requirement like everybody else's. Relying on a 3rd party lib that's widely used everywhere, and thus tested, is a very good decision. The only thing you end up doing is writing the application or service specific implementation and the message marshalling stuff. The library does the rest.

For anyone doing Enterprise messaging, 0MQ won't give you much yet. There are no tools to replay messages, retrieve them from error logs and what have you (or development tools). You may need something like OpenAMQ instead or RabbitMQ. To be honest, you do not necessarily need anything more complicated other than 0MQ if you develop everything in house.

Many services nowadays use XML/XSD to specify message formats. My main gripe with XML is that for too many people, it's about dealing with format instead of function. The issues with namespaces and all these other things make XML a really big beast to handle. Read _message matching_ to get some ideas where this will go wrong. Delayed brokers eventually slow down your entire business, make brokers unreliable, cause delays in some transactions that need to go fast, or negatively impact other processes that run on the same machine, requiring you to set up 2 brokers with double the probability something goes wrong... etc... Better get rid of it, move on and separate 'meaning' from 'transmission' and then verify things later. No need to encapsulate each message with the entire ontology each time a message is sent. I have a couple of interesting ideas in this respect that I'll share later as a research publication perhaps.

Update: 0MQ isn't without 'issues', but as far as I could determine so far there aren't any serious bugs in the code like memory leaks or reconnects, etc... I found two issues so far:

Messages are not being throttled at the server side. So if you look at the weather server example, which sends a lot of messages as fast as possible, under the water these messages actually get piled up in a list for the I/O subsystem to transfer them asynchronously. If the I/O subsystem simply cannot keep up, then you'll deplete your memory resources very quickly. The solution is to add high water marks or swaps, or use other methods for throttling the throughput of messages.
zmq_poll works, but because it assumes you're listening on multiple sockets, the idea is to visit each socket pool as fast as possible to collect any new messages that may have arrived. You then get one message per call and some kind of interleaving between each socket pool (if they're both really fast). Although this sounds nice, the underwater code assumes that you do not want to maintain any kind of "sleep" or other function to give back some CPU time for other processors. So, when you start 10 clients as in the examples implementing the zmq_poll, no client will yield and they all try to get 100% CPU time. If your client app can deal with it, the workaround is to embed a simple 'x' ms sleep in there. I recommend you sleep only when the last cycle didn't actually read any messages (no event was set).

Ion channels of excitable membranes

2010-10-10T11:29:00.000-07:00

I've just finished reading a book about ion channels in excitable membranes. Some types of excitable membranes are neurons, hence the interest. The kinetics of these types of cells are really interesting to try to understand. The more complicated or integral parts of sensory processing (and what this means) are performed in such cells.

The different types of channels and subtypes thereof have over time evolved by responding to particular messages or refined their function to respond better to what is happening in the environment. As this blog is not academic, I can voice some gut feelings / hypothesis here without bothering too much about scientific grounding and such. Most of the time, people philosophize over the function of the brain using analogies with existing machineries, comparing it to a computer and so on, but most of the time it becomes really difficult to trace this down towards actual cell function.

I think computer scientists made a bit of a mistake to make sweeping generalizations over the function of a neuron some 60 years ago. The attempt was made to map the function of neurons to something that could run on computer hardware. It started with a model where neurons, because they emitted a potential ( a pulse?! ), could be compared to logic building blocks which either emit a 0 or 1. Just like electronics. The "1" in electronics is basically the 5V of action potential that you'd normally put on a component to communicate a signal.

At some point, the "binary" neuron made way for the sigmoid neuron (so the 'processing kernel' was simply replaced) and this led to networks that were slightly more capable of performing some kind of function. At the moment, a lot of research is undertaken on Spiking Neural Nets (SNN), but there's still not a ground-breaking success in those networks.

I think the reason is that classical nets didn't pose any constraints on the timing of events, because they were mostly used for situations in which each state was information complete and where it was possible to derive the entire output from the combination of inputs (or let's make the output some approximation, as long as it worked, it was fine). Spiking nets do require specific timing constraints and there's not enough knowledge yet to support how such neurons should function over the domain of the signal and time to respond appropriately.

The refinement of using a sigmoid kernel (or tanh kernel) over a binary one is an important one already. The binary kernel was so abrupt in the change, that it was only useful in very specific situations. The sigmoid kernels are more useful, because you can generate proper outputs over a larger dynamic range. But the use of a replaced kernel hasn't been fully exploited yet.

The ion channels of membranes come in roughly three types:
- excitatory (generating the potential)
- regulatory / rectifying (attempting to establish equilibrium)
- modulatory, or acting over a longer time period, having an effect on the excitability of the cell

Classical nets are generally built with some assumed kernel in place and all kernels having the same configuration or parameters. The modulatory effects are not modeled in any way and the calibrati0n of the network is highly focused on the calculation of the weights, assumed to be the efficiency in transfer of neurotransmitters in the synapse.

The book I am reading demonstrates that the fast excitatory and regulatory actions themselves can be modulated somehow (this is like saying that the sigmoid function changes its shape), but that over time or multiple "calculations", this shape can also be modified on the basis of the output of this shape in previous steps (so the output of the kernel is changed as a function of the output of the same kernel in previous steps through some kind of accumulation function).

The classical nets seem very useful to have some alternative, mathematical model using neural networks for very complicated problems, but their abilities may be enhanceable by looking at biologic models in more detail. Neurons do not always function the same way, but you need to look at their behavior over time to see the longer-term effects of repetitive firing, the way how other inputs may influence their behavior (neurotransmitters) and either increase excitability or decrease it (or even suspend it).

However, I am convinced that networks that need to perform real-time tasks, or otherwise tasks where time is explicitly a concern can only be built with networks where this type of modulation and excitation is explicitly built in. The classical nets were never built from this perspective, but they remain interesting for classification or historical data analysis. The controllers (robotics?) of tomorrow and so on should attempt to understand more the dynamics and kinetics of the ion channels in neurons and the ability of neurons to time things.

The "von Neumann" machine & parallel processing

2010-09-14T13:35:00.000-07:00

It's been a while since I last posted a message. I've been thinking a lot about machine architectures and the most prevalent one, the "von Neumann" one (see right). This architecture basically serves the Turing machine very well. The Turing machine is a bit more of a philosophical model, whereas the von Neumann architecture is a specification for the implementation of one. The CPU here is a serial processor unit which, in any way you put it, never executes more than one instruction at any given time, or per clock cycle. The CPU then has a couple of pins available that are connected to outside devices or buses. Sometimes the buses don't really contain anything, but you could put some PCI, PCIe, ISA or other kinds of electronics in them, or you could attach some device to a serial, parallel, USB or FireWire port and then the more advanced Operating Systems would allow the automatic registration of these devices and subsequent allocations of address spaces and such (through a driver and hardware-specific communication protocol like USB has).

The architecture above is very well suited for mathematical calculations, because you could write programs that are expected to execute code in a serial way and this architecture would per definition execute those commands one after the other, store the intermediate results in memory, pick them up again at a later stage, post-process them with other results, produce output to screen, write it to disk, send it over the internet and whatever other "logic" you dare to endeavour in.

The above describes a regular PC and everything is deterministically determined. Its very architecture makes it very hard, if not impossible, to write programs on it that behave in ways that you would not be able to explain, assuming you have the tools available to verify the signals and so on (so it's a theoretical statement). This deterministic processing is what makes the design viable. It is by its nature serial, because the CPU must retrieve one instruction to execute, fetch something from memory, store it into memory and do this in the correct order for the program to function correctly.

One architecture that is too complex for us to design is one where the CPU is no longer processing one instruction per clock cycle, one after the other in serial fashion, but a CPU where you can have a very high number of processing units and memory is not in one place, but distributed around this network as well.

Most applications that we write nowadays are data-driven. Now, the interesting thing here is that I think more and more applications are written data-driven style instead of purely as code. Anywhere else but the enterprise world that is :). Data-driven programming means that you move logic, output or processing from code (long switch statements or branches) into processing tables, datafiles or whatever. Almost, if not all, machine learning programs are always by definition data-driven programs. The algorithm itself is usually quite compact as a program, but frequently needs mountains of data to function correctly.

The main complication in the entire thing is that purely serially written code avoids the complexity of having to synchronize results later on, most importantly at the right time. This latter thing is also what plagues certain parallel architectures and programs that already do exist and also complicates designs for GPU's, FPGA's and so on. You could also call it the binding problem in psychology. It's easy to think of channels of processing where a little bit of the entire thing happens in that single stage, but connecting the dots later to make it a larger whole that means more than each channel individually is a very large challenge. Maybe not if you have the time to put it together thoroughly at leisure, but certainly at realtime.

Flying with Ardupilot Mega

2010-08-20T08:41:00.001-07:00

I'm experimenting with the ArduPilot Mega source code and settings and have finally succeeded to get it working properly using a FlightGear simulator and the board setup through a serial USB link. I've made a flight, slightly rough around the edges, around San Francisco airport in the simulator with some tweaked waypoints. You can find that file here.

The biggest problem in getting the link working has been the communication between the PC and the arduino board and FlightGear. FG may reduce or increase framerates and start buffering data when the interface program is not consuming them fast enough. The current interface is almost ready for real use, but can I think still increase the speed in which it passes data around.

In order to get stuff working, you should check the source code out of code.google.com and make sure that you're pointing to the correct library location. Download the GPS_IMU.zip which is used for the communication with the USB 'ground station' (the flightgear link). Then reduce the NAV_P gain in the APM_PID_Gains.h file to something like .5 and reduce the other P gains too (you'll notice if the gain is set too high when it becomes unstable in flight and increases the roll or pitch constantly).

As I said, the flow of data was the biggest problem, so communication with flightgear is now attempted to be optimized. FlightGear does not care too much if there is nothing to read, but writing more than it can handle will buffer data on the IP buffers. So you should aim to write 1-2 Hz less than the link setting. Also pay attention to the frame rate that FG is able to put out, because that is the minimum update frequency you can use.

Reading from a port should be done as fast as possible and ideally outside of the main "50 Hz" loop. Since Arduino attempts to follow a 50Hz loop, you could attempt to follow the same in the interface application, but there's a possibility that you overload the link. The older XPlane app issued the attitude and additionally the GPS at 5 Hz, but I modified that to output XPlane attitude @ roughly 42.5 Hz and GPS @ 5 Hz. That leaves a bit of space to get rid of any overload that might occur on the arduino side.

Reading from the serial port should also occur as fast as possible. This way, you can keep everything in the same loop once you use a couple of global variables for whatever data is read from the links. Once something can be written, then just set up the packets and kick it out the door.

There are probably some configs to change in the Arduino source code before thinsg will work for you:

I have airspeed sensor set to 0.
The example waypoint file has been modified to allow the cessna to make the turns (better:).
GCS_PROTOCOL is set to 3.
GPS_PROTOCOL is set to 3.
GPS_IMU is included.
The #ifdef GPS_PROTOCOL != 3 before the GPS.read() is commented ( around line 610 in main source file, inside update_GPS function).

I first ran in STABILIZE mode and verified that I got responsiveness on the sticks. If your interface is buffering too much, reading too slow or writing too fast then you may get responses after 5 seconds. That will never converge to a model that can fly properly.

Then after STABILIZE mode you can quickly verify FLY_BY_WIRE_A and B to see if that works out. Then I loaded the waypoints and turned on AUTO mode. For that to work, just start flightgear and pause it. Zoom out a bit with Shift-X until you see the throttle stick. Hit "H" to see the HUD to get more info. Then make sure the switch is set to manual with throttle at zero. Start up the interface. Wait for the servo's to wiggle and the interface to print "Ready to Fly". Now you can switch to AUTO mode, but you have to control the throttle manually. I basically set throttle to full.

Because I don't have a rudder attached (nor is this set in the ardupilot.xml file), the plane veers off to the left due to the propeller torque until it lifts off the ground. The ardupilot mega will then slowly turn back to the heading it had when it was going 3 m/s (12 knots). Initially I used 10 degrees pitch, but noticed that it tried to drill itself into the ground. Making that 20 degrees again fixed it. Also make sure that your NAV P gains are correctly set, as these will determine how eager the autopilot is to get to the setpoint. Since the stock cessna of FlightGear is a bit slow in relation to an easystar, these P gains probably have to be reduced. It will then be less strict in following the waypoints, but allows for easier flight.

Have fun!

Making HD videos in France

2010-08-16T11:17:00.000-07:00

I've returned from a small holiday in France and took the UAV to fly over there. I used the GoPro HD camera in the cockpit and shot a couple of videos @ 60 fps, 1280x720p. The results are on YouTube with a slightly reduced bitrate (more compression):

And another one near the castle of Castlenaud:

And I returned to the camping to make a high-altitude video from up above:

Nothing got seriously broken and it's great to see the videos to improve my flying skills. The video was also transmitted live to my netbook on the ground, but I didn't use that for navigating around (yet). I first need to check into an automatically adjusting tripod setup that will track the plane for a patch antenna. That will ensure, usually, a very good video link.

Hauppauge USB Live 2 & Ubuntu

2010-08-05T09:15:00.000-07:00

I'm running Ubuntu and purchased a USB Live 2 stick from Hauppauge to visualize some direct composite video coming from a 5.8Ghz receiver. This video is transmitted from an RC plane to see what's going on up there on a netbook. I'm not flying it FPV for lack of goggles and because I want to keep track of where the plane is. Basically, the intention is to put the family behind the netbook to see what the plane sees and I'll stare at the dot in the distance.

The USB stick arrived yesterday in the mail and after plugging it in, nothing happened. USB devices get recognized by their ID's and as soon as you register a driver for it, the kernel will visit all eligible drivers to see if one wants to step up to communicate with the device. Apparently the support for USB live 2 is not available in the stock distribution of Lucid yet. After searching around I suddenly hit a post made on the 3rd of August (sic!) that support for USB Live 2 was just completed on a development branch in v4l2. So the day before I got the stick development just finished with the first version of the driver.

Blog: http://www.kernellabs.com/blog/?p=1445&cpage=1#comment-1632

I managed to install this on both my netbook and general PC. These are a 32-bit Lucid Lynx distribution on a Samsung N210 and a 64-bit installation on a more powerful machine with ATI HD5850 and i7 920. You should make sure that you're not holding back any linux packages, since I got screen corrruptions with kernel 2.6.32-23. The latest version now is 2.6.32-24 and there it worked (or it was something else, who knows?). After the clean install, you need to grab gcc, do an update/upgrade of all packages and make sure the latest kernel headers are present:

> apt-get install gcc
> apt-get install linux-headers-generic    ( <-- ensure it's the latest & greatest @ 2.6.32-24 )

Then I used the entire v4l2 source tree available here (at 05-Aug-2010 that is, things may change rapidly here)

> hg clone http://kernellabs.com/hg/~dheitmueller/polaris4
> cd polaris4
/polaris4> sudo -s
/polaris4> make

( then edit v4l/.config:
1. find CONFIG_DVB_FIREDTV=m
2. change this into:
3. CONFIG_DVB_FIREDTV=n
4. (notice the n instead of m at the end, that's all).
5. This essentially deactivates the build of a problematic module, so if you have a problem there
  you can deactivate it.

/polaris4> make
( yes again ).

If all went well:
/polaris4> make install

And then reboot. The reboot will ensure you're not using any old drivers. The rollback procedure for this is to reinstall the linux-image-...version... you were using. That will replace all your modules with the stock Ubuntu Lucid distribution.

Any time you get a new linux-image installed, you have to do another make, make install in this custom directory to overwrite the module files again. Remember that!

As you can tell, after doing this some video-related things may not work properly. For my netbook, I'm only going to use it in the field and some simple stuff. So far things haven't broken, so that should be relatively safe. It looks pretty stable so far.

I've noticed that the image when there's no signal may be plain blue. That is usually the case when the signal hasn't been tuned at all, but in this card you must ensure there's a video signal going into it.

The USB Live2 is a great little gadget with quite good image quality and zero lag on the Linux drivers. In Windows it's possible you get lag up to 3 seconds even, but that's because your driver must be configured to use "GAME" mode (if you're flying or gaming with this that is, otherwise it doesn't matter too much).

In order to visualize things, I now use tvtime (apt-get install tvtime). There's a handy configuration XML file in /etc/tvtime.xml where you can make all the default settings. The coolness about this utility is that you can change a large number of settings without restarting and adjust the image quality, brightness or contrast itself. Great for outdoors flying and getting a bit more out of the display.

The USB Live 2 uses the cx231xx kernel driver.

Mesh networks

2010-08-01T13:35:00.000-07:00

An interesting technology to be playing with are wireless self-healing mesh networks. Mesh networks are characterized by a rather chaotic characterization and where the data sent by one node is not necessarily sent directly to the receiver, but may make a number of hops before it gets there. This allows you to introduce a number of routes between the source of the data being generated and the coordinating node where the data needs to go.

A lot of propositions offer mesh networking for near real-time video display and those types of applications, instantly pushing the limits of the capabilities of bandwidth and network stability. I think the low-speed networks are slightly more interesting myself due to the low-cost ability to set this up and the speed at which such networks can be realized. This makes it very interesting for situations in which you need to cover a certain area for monitoring of some type. As long as the modules being placed have the right kinds of sensor and logic unit, you can start collecting data from this environment in no time.

Sometimes you want to collect more data than the sensors can give you, for example due to bandwidth constraints on this technology or the sensors that the installation is offering. In that case the cooperation of other mobile sensors that can be directed towards positions can help. Think UAV's being directed to that location, but still have means to be 'part' of the network as they move around a larger area of say 10 km to assist with the sensors they offer. The whole idea should be to plot interesting data about this larger area in no time and to do this as autonomously as possible.

Joystick pong (how to write custom usb drivers for the nanoboard)

2010-05-22T08:04:00.000-07:00

I've just worked out how to write custom drivers for the nanoboard to extend the capabilities of the platform through different USB devices. It isn't really that difficult for similar devices (you could just copy things across), but for more complicated devices you need to understand how the USB protocol works. The nanoboard USB host driver already takes care of a lot of the details for you. The specific device driver that you are writing only has to indicate if it wants to be a device driver for a particular detected device. The device driver call basically does a test using the data that is passed in. This data comes straight from the interface and device descriptors that were received from the bus. This is sometimes where the problems start. My joystick on Windows isn't recognized as a joystick per se. It's a Human Interface Device without a boot capability. It's working properly in games, but that's about it. The HID protocol isn't passed by it (which should be 04, for joysticks). This causes issues for people writing device drivers, because you can't know what type of device something is.

Also, not all joysticks pass the same ranges of data. The USB HID descriptor does indicate the ranges for USB, but this complicates things a bit for the device driver writer.

Anyway, the sample joystick driver is here and a new version of the pong game is here.
( the joystick driver should be put in the "Library/Software Platform/services/usbhost" directory of Altium designer).

In order to write drivers for other devices, it's helpful to boot into Linux and inspect the descriptors that are sent across the wire. A useful page comes from a guy who has rewired his old joystick to make it USB compatible. Other useful pages are the HID tools page and a page explaining how to use usbmon software to analyze the USB in more detail. Wireshark can also capture things from the USB. (usbmon on my lucid ubuntu seems to have been compiled into the kernel already. Just see if the /sys/kernel/debug/usb tree is there).

You can then use the kernel debug interface to inspect what's going on in the system. Under linux, cd'ing to:

/sys/kernel/debug/usb

will give you a devices file, which is useful to find out how a device is recognized. My joystick is incorrect, because it doesn't provide subclasses or protocols, as can be seen here:


T:  Bus=03 Lev=01 Prnt=01 Port=00 Cnt=01 Dev#=  2 Spd=1.5 MxCh= 0
D:  Ver= 1.10 Cls=00(>ifc ) Sub=00 Prot=00 MxPS= 8 #Cfgs=  1
P:  Vendor=046d ProdID=c215 Rev= 2.04
S:  Manufacturer=Logitech
S:  Product=Logitech Extreme 3D
C:* #Ifs= 1 Cfg#= 1 Atr=80 MxPwr= 30mA
I:* If#= 0 Alt= 0 #EPs= 1 Cls=03(HID  ) Sub=00 Prot=00 Driver=usbhid
E:  Ad=81(I) Atr=03(Int.) MxPS=   7 Ivl=10ms

Compare that to the mouse (but notice how the same driver is used):

T:  Bus=07 Lev=01 Prnt=01 Port=00 Cnt=01 Dev#=  2 Spd=1.5 MxCh= 0
D:  Ver= 2.00 Cls=00(>ifc ) Sub=00 Prot=00 MxPS= 8 #Cfgs=  1
P:  Vendor=046d ProdID=c018 Rev=43.01
S:  Manufacturer=Logitech
S:  Product=USB Optical Mouse
C:* #Ifs= 1 Cfg#= 1 Atr=a0 MxPwr=100mA
I:* If#= 0 Alt= 0 #EPs= 1 Cls=03(HID  ) Sub=01 Prot=02 Driver=usbhid
E:  Ad=81(I) Atr=03(Int.) MxPS=   5 Ivl=10ms

Another cool thing to do is to look under:

/sys/kernel/debug/hid

This will show a couple of weird ID's, but those are the currently attached devices. In those directories, you can inspect the rdesc file for each of them. The rdesc file describes the format of the data, so indicates to the host device driver how it should interpret the data stream.

Devices may have multiple interfaces. The keyboard and mouse typically have a 'boot' interface, which allows the devices to be configured in the boot sequence. Notice that under linux, the same 'usbhid' driver takes care of most HID devices. This is because of the rdesc file, indicating the way how the driver should interact with the device. I'm not exactly sure at the moment how the driver would communicate this to the applications or HAL layer above it in a generic way.

Notice that HID are not always strictly input devices. Some HID's have outputs (device input) which allow the setting of LED's, force feedback, etc.

So how does one read these HID files to discover the data format? Let's look at a simpler example, the mouse:

Field(0)
 Physical(GenericDesktop.Pointer)
 Usage(3)
   Button.0001
   Button.0002
   Button.0003
 Logical Minimum(0)
 Logical Maximum(1)
 Report Size(1)
 Report Count(3)
 Report Offset(0)
 Flags( Variable Absolute )
Field(1)provides
 Physical(GenericDesktop.Pointer)
 Usage(3)
   GenericDesktop.X
   GenericDesktop.Y
   GenericDesktop.Wheel
 Logical Minimum(-127)
 Logical Maximum(127)
 Report Size(8)
 Report Count(3)
 Report Offset(8)
 Flags( Variable Relative )

The logical minimum and maximum determine the value range. This could also be used to rescale the values if you want a consistent output. The "report Size" is the size in bits of one individual field. "Usage(x)" indicates the number of fields that are being described. Report Count(x) does the same. The Report offset(x) describes the offset of these fields within the entire data stream. So, this mouse protocol uses the three bits in the first byte to describe the state of up to three buttons. It uses 3 bytes after that, indicating X and Y motions and the motions of the wheel.

This is basically how I figured out how my joystick worked. You could also specify your own rdesc / hid file using the HID tools mentioned above. Of course, computers don't need to communicate in ASCII, they'd use the compiled HID information as an array of bytes to convey the same information. The manufacturer and product ID are 16-bit fields that need to be looked up in a file on the host somewhere, if one cares about it.

Update: Here's another version using a lower resolution and lower color palette. Because of the USB code and the other drivers, the generated ROM image is larger than 32k and doesn't fit in local processor memory. This requires the use of a small amount of RAM, which constantly reads in new code to execute whenever required from memory. This memory (SRAM) is the external RAM on the nanoboard, which is shared with the VGA driver. Because the VGA driver gets priority, the game slows down whenever the processor tries to update the frame (because the processor cannot read in code to execute from SRAM memory at the same time the frame is being drawn to the monitor).

Pong!

2010-05-20T13:38:00.001-07:00

This is a late-night shot of the game Pong!, running on a soft-core TSK-3000 RISC processor on the nanoboard. You control the paddle with the remote left and right. There aren't that many examples on the Internet on how to use the actual VGA display for the nanoboards. Actually, I found none. There were two examples from the tutorials shipped with Altium designer that demonstrated how the VGA connector should be used. There are a number using the TFT display on the board, but that's too small for a couple of things.

Pong! on the nanoboard goes public domain. It's imperfect and inefficient, but it does show how to render things on the VGA monitor (not the TFT). This implementation uses double-buffering, which in embedded devices is very costly because of memory requirements.

The display is not yet stable, it's flickering due to issues with VSYNC. I haven't figured out yet how to use the interrupts properly and let the framework driver rely on them, or whether the API calls have been used correctly. I'm hoping for some feedback in the forums, after which I could provide some updates here and there and show better practices in doing this.

Another thing I'm looking into is the best practice for writing one's own drivers for USB. There's a software stack available that can already inspect USB signals and packets that tell a host device what a connected device is about. There's very likely going to be a point where someone wants to write their own USB device for interfacing with the nanoboard, but is wondering whether to start from scratch at the signal level, or whether the usb-host sw platform can be used in any way. Without hacking into the standard altium designer library that is.

Well, plenty of ground to cover still with this device. It's a lot of fun and I'm starting to find my way around it already. I'm feeling quite confident about my abilities to prototype using the hardware on and around the board. It's just so easy. The difficulties start to arise when more complicated designs are required, especially those requiring more memory or specific hardware protocols or interfaces (custom designs). As with the above, my next goal will be to find out how to connect a USB joystick (and I'll opensource that as well). And from there... onwards...

Tutorials finished!

2010-05-19T09:45:00.000-07:00

Well, I got things up and running like a charm in the meantime. After the inital GB downloads (which may get fixed ? see comments previous post! ), I've completed most tutorials of the Nanoboard today. There were only three that I couldn't run due to some interoperability issue with the Xilinx tools, but that happens sometimes. It's been logged, noted and people are working on it!

So far... I can say it's truly amazing and a pleasure to work with this board, especially for those who are newbies in the field of electronics. The tutorials provide a very basic overview of what the board really can do, so keep that in mind. Of course those applications can be done quite easily on Arduino boards or whatever.

But then have a look at the extensive royalty-free library... you'll discover 119 subdirectories loaded with microprocessors, circuits, memory blocks, opamps and plenty of other electronics that can be inserted in the schematics diagrams. People at work sometimes do use some exotic hardware and this makes it likely I can find the same chips and IC's they work with. In combination with the other tools and outputs, you can generate all kinds of testbeds for running their code on this FPGA, but analyzing the signals or some other things to help out.

It wasn't very clear to me that the real use of the board is probably about trying out different processors and designs up-front, before you solder things together. But now that I think about it, this certainly makes sense. At work some people work on UAV's for example. They require very small, light-weight boards that provide lots of functionality and a good amount of processing power. Everything is embedded and hardware supported. You couldn't put a nanoboard in one of those planes due to weight and power cable concerns :). But simulating a particular board or processor, or just having a platform where you can run embedded ideas from is a great nice-to-have. Since it's very close to the PC that could run a simulator like FlightGear, you could just hook up this board to a FlightGear stream of simulation data, where the board must attempt to fly the plane level or other kinds autopilot functions.

So yes, I am certainly pleased with my purchase. If anybody is ever thinking of going into FPGA programming, this is the board you want. It's probably twice the price of a regular board, but you get three times the value back for it. The extensive library of 'soft-design' hardware, the ability to still run VHDL code on the chip, the way how it interfaces with your computer, the Altium Designer software (only for a year though, so check out the conditions) and the overall hardware that is attached to the board (TFT touch, PS/2, S/PDIF, USB, SD-card, MIDI, audio, RS-485, RS-232, ethernet, VGA-out).

Definitely recommended! It's Arduino++.

Altium Nanoboard 3000

2010-05-17T11:18:00.000-07:00

I've managed to get my hands on a really cool FPGA board from Altium. It's very promising with a TFT touchscreen display, RS485, RS232, 3x USB 2.0, S/PDIF in-out, SD-card reader, headphones/line-in/line-out, 4-ch DAC, 4-ch ADC, 4x relays, PWM, SVGA output, MIDI and a TSK-3000A RISC 32-bit processor.

Unfortunately, where this technology is really amazing, getting things to work on your computer is not so. Your mind will dazzle from all the license files, registrations, threats about non-compliance with export restrictions and whatever else these companies come up with to make your life difficult. For someone having gotten used to Ubuntu and the software it brings through straight installs, getting a minimal "Hello World" out of this board is proving to be extremely challenging for a newbie. And I'm saying that as an experienced programmer.

The biggest crap factor are the Xilinx tools. They offer a "webpack", but the download is around 2.6GB (not much of a "webpack" if you ask me). The 12.1 version is incompatible with Altium Designer, so that's where problems are starting. So then I downloaded 11.1 as required, but that is not supported on Windows 7. Altium Designer so far has no particular problems with Windows 7. So I upgraded Altium Designer as much as possible, but that didn't improve the chances of compatibility with 12.1.

Basically, I got a dreaded "Xilinx ISE not found" message in red above my FPGA chip, which was actually due to a missing environment variable (no longer set in 12.1?). Altium Designer just picks up the "XILINX" path variable, which should point to the "ISE" subdirectory of the Xilinx ISE installation. If XILINX is not there, it will show the above message. Populating XILINX as the env variable by itself is not enough, as even a very simple example won't compile due to differences in compilation options.

If you get: "No Process Flow", then you should simple "configure" the project by right-clicking on the nanoboard icon in the devices view and generate the constraint files.

The information about what to do next is not really available on the Internet. Most suppliers lock down their forums entirely, so you need a login to find out if others have had the same problem. Since most companies probably follow the instructions on what OS to use and so on, this doesn't seem to have occurred much. Luckily, I found one solution that seems to be going to work. You need a lot of patience and flick your common sense in "off mode" for this to work:

Download the ISE Webpack 11.1 anyway (2.6 GB or so).
Download the ISE Webpack 11.3 as well (another 2.7 GB..... *sigh*). Downloading only 11.3 will not work, because the installer asks for the 11.1 install directory (hooray!). Even though the size of the installation file clearly shows otherwise.
Then install 11.1, but not from the main folder. Go into "bin/nt" and start "xsetup.exe" from there.
Wait for this to install. Takes a while. Feel free to *not* install "webtalk", because that just sends how you use the tools to xilinx and why'd you want to do that?
Then install 11.3. It will ask for where you installed 11.1 to. 11.3 is luckily compatible with x64 already.
This upgrade takes quite some time (apparently it checks every file if it needs upgrading?).
Restart Altium Designer... and now it should show up. ( See "XILINX" environment variable if it doesn't ).

Another word on what these companies do that I find very strange. Altium Designer and Xilinx Webtalk basically monitor the way how you use the tools and send this over to their servers "for improving your experience". So you've got basically a hidden spy on your computer now that indicates to them what you use, how long you use it, on which days etc... ugh!

I'm certainly not some experienced FPGA designer, I just decided that I wanted to learn about this technology and play around with it. My intention is to grab a board that could do a number of interesting things, rather than starting from the bottom-level basics. Altium Designer allows me to focus on certain high-level topics, such that I can create some truly interesting marvels first before having to delve into the low-level details first. I prefer it that way, because I don't get hit by the low-level nit-picky details in the face immediately. Eventually however, I already noticed that one needs to gain the knowledge about electronics, wiring and so on in order to use these things effectively and knowledgeably.

My install got finished and it's all compiling now. I'm going to check through the tutorials, see if I can write a couple of things myself, play around with things a bit. Given the software that Altium provides, if you are a learner like me, I can certainly recommend what they are offering in these nanoboards...

Field Programmable Gate Arrays

2010-05-12T23:39:00.000-07:00

I've been looking atFPGA's and ordered my own board to arrive in the mail pretty soon I hope. The difference between a normal CPU and an FPGA is best explained here. Notice how FPGA's are independent and act directly on the signal, whereas the CPU typically executes one instruction per 'clock cycle', but then may need to retrieve values from memory, put this into a register, execute another instruction, push back from register to memory and so on. Once you think about it, it's already pretty amazing that a single CPU can be so darn fast.

FPGA's however do not typically need to do this. It requires a totally different thinking about computing, but benefits from using much simpler logical elements wired together in different ways. This configuration of logic elements is what provides it with an application.

The FPGA's limitations are more the number of elements (and thereby the functionality it can possibly embed), because it's program is embedded in hardware and isn't read from memory and then executed by the same device. This is also how they are very different. FPGA's are also not programmed with a standard programming language (since it's inherently parallel and the program is basically the configuration how logic elements wire together). Another language called VHDL is used for this purpose, which does not require you to think about all things in parallel (one of the reasons why computers are easy to program is because we can think about events serially, as happening one-by-one. Multi-threaded computing is already getting more complicated, because you need to imagine how threads and processes may interact together and the results these may create).

You can build a host of very interesting things on FPGA's. One is an M&M sorter :), but a not too complex board can already simulate a C-64 and run the game Commando.

Of course, the FPGA gets very interesting when you need to process a large, complex signal. Think about video signals for video compression for example or speech recognition. Lots of research is undertaken there at the moment. But simpler implementations are also possible, for example PID controllers for temperature regulators etc... I do think though that FPGA's are slightly overkill and possibly unnecessarily complicated.

An alternative to FPGA's are Arduino boards, which are basically CPU's again and can also be programmed in C. So a lot of fun when you want a new kind of hobby.

AI Challenge progress

2010-03-14T07:29:00.000-07:00

This video shows some different progress with the AI Challenge. The previous video demonstrated how the computer was directly manipulating the joints through a neural network. In this video, there's a proportional controller attached to each joint, which only tries to get the angles of each joint to some particular value.

These values are set by a joystick that I attached to the computer. I've tried to control the arms directly, but that's basically hopeless. Besides just looking at the position, you also need to control the angular velocities at the same time for three arms at a time. This implementation therefore reduces the "cognitive stress" and already it's starting to make it possible to make predictions and expectations and to (sometimes) actually hit the ball. It remains somewhat difficult however.

So far, I haven't used IK solvers or any complicated math theories to do this, just one observation of angles and a direct reaction to whether that angle is desirable or not. The intention is to see how far I could take this and see if that is actually useful. Right now, I am supplying the angles directly, but progress can still be made to possibly focus on controlling something else (the hand?) and see if the simulation can iteratively figure out how to get there or something. The rest of the solution can then be given to understand the trajectory of the ball in a really simple way, find out when it's in range and where that will be and finally project a path (over time) where the joints actually need to start doing something.

Inductive vs. imperative programming

2010-03-08T11:33:00.000-08:00

For work I'm currently looking at LISP programming. Lisp is one of a family of functional programming languages like Haskell, OCaml, Erlang and Scheme. Lisp itself is the oldest of these and it is based on the manipulation of lists (..of lists...(...of lists)). If you look at Lisp code, you'll quickly get dizzy from all the parentheses on the screen.

One interesting property of Lisp is that it can be a huge stream of code intermixed with data, or data becoming code (messages), or code producing more data (recursion etc.). There have been some libraries that were written for Lisp, which gave it more capabilities including screen widgets and so forth. Standard Lisp however doesn't have unification and backtracking abilities like Prolog does. So, even though Lisp has been used in AI applications, it isn't directly comparable with Prolog for example.

This article is a still relevant consideration about the use of Prolog and why it hasn't taken off so much as it could have. Most programmers work out particular problems procedurally themselves (sometimes giving rise to very costly and sneaky bugs), many times due to incorrect control code statements and so on.

Logic programming is an area where you inductively reach a conclusion. When you state a fact, the interpreter confirms that this fact may be stated (is true). If you state a relation with a variable (a query), the interpreter tries to find all possible valuations that do not contradict with any other logical facts or statements made about these valuations. The result can be either null / nil / zero / no or a number of valuations that the interpreter knows about.

Logic programming is inductive programming. This means that some facts are declared ahead of time and then the program builds up some execution tree and finds out the rest. Imperative programming on the contrary means that the programmer decides the entire flow of what the program does, when it does it and how. This is the most common way of programming (C, PHP, C#, VB, C++, python, Java, etc.). So there is no 'hidden' code in any imperative programming besides the grouping of CPU instructions through assembly language -> 2nd generation languages -> 3rd generation languages and upwards.

A recent area of interest is called constraint programming, which is quite similar to logic programming, except that you don't really derive facts from other facts or prove them right/wrong. There are libraries available for a host of different programming languages, including the imperative programming ones.

Now, without a lot of very intelligent optimizations, these solvers would basically run loops over loops over loops and take a very long time to compute queries. This may have a large impact on the usefulness of inductive programming in real-world scenarios. Also, considering the article above, the success of some language doesn't really depend on its capabilities, but on how easy it is to get started with it and how well/fast someone can verify that some intention is working out correctly as intended. In that light, imperative languages are easier to follow and verify, because the entire execution diagram is right in front of you (except for the funny race conditions, deadlocks, non-reentrant code, library errors, static variables and so on).

Constraints are both problematic to code for correctly, but incredibly helpful for coming up with solutions within your own lifetime :). Some article I read used the example of a number of ships for which a schedule needs to be developed. Any berth can be taken at any particular moment in time. Scheduling problems are the best example for constraint programming, because they can have a large number of constraints associated with them and often have a very large number of substitutes (multiplying the number of loops in total).

The idea is that through constraints, you can decrease the number of items that are under consideration, but this is not the whole story. Sometimes constrains are imposed on the combination of values from domain R with domain S. In such cases, the rule can consistently be firing over some iteration mechanism that dumbly retries other valuations, continuously hitting the constraint. The general thing here is that research is focusing on smarter algorithms to bring down the number of iterations that are required.

Why is this all so relevant? Because planning and reasoning systems with formal declarations still depend on this brute-force mechanism of trying out combinations of different values. For very complex problems, it is very difficult to write imperative software that always computes the correct solutions and results for all cases, given an expanding set of constraints that may be imposed on them. The idea is that, once you have a generic iteration mechanism and a generic method for declaring rules and properties of objects, you only need to extend a so-called knowledge base and the system does the rest.

I think however that it is wise to start thinking about blends of programming languages. Either by expanding the compiler to embed the inductive code into the imperative code or by creating embeddable interpreters that can be loaded with particular objects, exposed inside the interpreter runtime and then fired off with a query to find any objects that apply. But certainly, sometimes by restating the problem or by starting off with an intelligent choice made by a human, one can sometimes just resolve the problem directly with procedural code. For schedules however, I don't see that happening so quickly.

Check out the following libraries and projects:

Python: http://labix.org/python-constraint

Minion: http://minion.sourceforge.net/cases.html

C++: http://research.microsoft.com/apps/pubs/default.aspx?id=64335

Java: http://www.emn.fr/z-info/choco-solver/index.html

AI Challenge

2010-02-27T11:38:00.000-08:00

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

2010-02-15T13:11:00.000-08:00

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

2010-02-14T01:26:00.000-08:00

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

2010-01-29T13:53:00.000-08:00

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...

2010-01-27T11:07:00.000-08:00

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

2010-01-25T14:08:00.000-08:00

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

2010-01-11T12:20:00.000-08:00

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

2010-01-04T11:27:00.000-08:00

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

2009-12-21T11:43:00.000-08:00

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

2009-12-14T10:45:00.000-08:00

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...

2009-11-30T23:11:00.000-08:00

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

2009-11-17T11:36:00.000-08:00

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:

Calculate GLOB_AVG from entire matrix
Ʃ1 = GLOB_AVG * sqrt( num_cells )
Ri1 = sqrt( Ravg / Ʃ1 )
Cj1 = sqrt( Cavg / Ʃ1 )
lrate_first_cycle == slow (it's almost there) == 1 / Ʃ1
INIT = ( GLOB_AVG / ( 2 * sqrt( 2 * GLOB_AVG * sqrt( num_cells ) ) ) )
Rix (x>1) = rand( -INIT, INIT )
Cjx (x>1) = rand( -INIT, INIT )
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

2009-11-11T10:02:00.000-08:00

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

2009-11-09T13:35:00.000-08:00

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

2009-11-04T12:45:00.001-08:00

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

2009-11-01T10:22:00.000-08:00

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

2009-10-27T13:37:00.000-07:00

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

2009-10-22T11:48:00.000-07:00

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.

Natural Language ToolKit

2009-10-17T00:58:00.000-07:00

Due to my interest in the z-machine, I'm looking at natural language parsing and the complexities that entail it. There's actually a very nice python-based project that allows one to study natural language processing, it's called nltk. NLTK is more like a set of tools for getting frequency distributions, frequency plots, extracting information, processing raw text, etc. Basically, within a single line of text you can specify a lot of characteristics about the text or words you're interested in, then you run a function from words within another selected set and you get the results you're looking for (at least, that's the idea). There are a lot of Python functions and objects prebuilt into the toolkit offering a lot of generic tools that you'd typically use and to which you can feed specific sets of data for processing or parametrize with your specific intention. It's probably not that effective immediately for a particular application, but this is research and first you need to find out what to do before you start off working on some solution that you think might work. It's all about getting really deep into the matter very quickly, experimenting things, looking at results. I haven't worked extensively with Python, but neither Java nor C allows for this enormously compact syntax for querying and manipulating data sets. Because the number of functions are pretty large, it may be a bit daunting to find out what objects or functions there are, or what they do. Therefore, I suggest to install Eclipse or another IDE and run pydev within that for code completion purposes.

Get the latest distribution of NLTK from here. You can install NLTK on Ubuntu as follows:

$ sudo -s
# apt-get install python-numpy python-matplotlib prover9
# unzip nltk-2.0b3.zip
# cd nltk-2.0b3/
# sudo python setup.py install
# python
Python 2.6...... (......)
>>> import nltk
>>> nltk.download()

The following shows a cumulative frequency plot of the words that occurred most often first:
There are many other things that can be done. This is a textual example of collocations in the "Inaugural Address". Collocations are words that appear together frequently.

>>> text7.collocations()
Building collocations list
million *U*; New York; billion *U*; Wall Street; program trading; Mrs.
Yeargin; vice president; Stock Exchange; Big Board; Georgia Gulf;
chief executive; Dow Jones; S&P 500; says *T*-1; York Stock; last
year; Sea Containers; South Korea; American Express; San Francisco

These examples are taken from the book of NLTK. So, NLTK isn't really about making text accessible or some kind of engine that you can use for parsing / understanding text. It's a toolkit for language processing experimentation, so that using that knowledge you can roll your own stuff afterwards. A specific design goal is low-threshold access to the tools and functions of the toolkit. This should allow people without programming experience to use machine processing tasks for their own research. This hopefully puts it well within reach for anyone looking into natural language processing, filtering spam, building search engines, building translation engines and so forth.

Rolling your own heap manager in Linux

2009-10-07T14:00:00.000-07:00

I was looking at ways to maintain a lot of data in memory, which may get modified in any way through constant interaction and then methods to maintain that state across process invocations. One of the ways to do this is by picking out structures and objects and store them elsewhere, but that involves a lot of work. Since the process I am working has full knowledge of what happens inside it, I've considered the possibility to dump an entire data heap to disk, so that it can be read in later and immediately reused.

One of the things that you can't do in that case is maintain file descriptors or other state-bound items that are tied to sockets and so on. So, the heap may only maintain data and even with state one should be very careful, since state is often bound to the currently executing process. There's ways around those things too however, so I decided to just go along and do this heap writing/reading.

The idea is to set up a 2GB file as the standard and maximum size of a heap and then map the contents of that file into memory using mmap. Let's call this the file heap. The mmap call will automatically increase the memory address space when necessary (read up on brk() and sbrk()). This 2GB looks contiguous to the process (although Linux may have this in totally different pages in physical memory ). The idea thereafter is that the process handling uses different memory pages, storing current state that is related to current handling and that any data modifications are done using the file heap.

So, data -> file heap, any other necessary memory allocations are allocated from the standard glibc heap (using standard malloc() and free() ). This way, any data allocated with a specific s_malloc() or s_free() call will automatically be added to the internal data file in places that are available to it and programming will feel quite natural overall. It's just like dealing with normal memory.

When the program terminates through a standard quit call (or when it catches specific signals), the msync() call is called, syncing all memory changes to the disk file synchronously, the memory is detached and the application exits. This should guarantee ok consistency between runs. Another run attaches to the file and all the data is there in the right place. For now, the application requires that this mmap is attached to the same base address, so that any pointers inside the file still point to something valid later. An alternative is specific linux structs and allocation functions that maintain this householding, but that increases size significantly.

These methods and custom malloc() and free() implementations should allow the application to also do garbage collections, maintain reference counts and other clever stuff that I can't think of right now. The good thing is that this doesn't require the application to keep everything properly aligned, it deals with less complexity. The preallocated heap is then filled up until it's full. Theoretically, it's also a good idea to pre-slice the heap into three different areas and then work with three heaps instead. This means that all three heaps have good knowledge about the maximum size they should be having and they can arrange their memories with their own specialized algorithms.

Semantique

2009-10-06T13:35:00.000-07:00

I've slowly started on a new experiment related to the other posts. I've read through documents and source code describing how the original adventure games were created. The z-machine is the most well-known specification. In its most basic form, an adventure game is a blob of data intermixed with code. The z-machine, the program that runs the adventure, is nothing more but a host to the adventure game (story file) and after loading the file in, which is part data and part executable, it starts execution. In general, this causes the game to print the current location. All other things are initialized to their general value. I've said that these games also had code in a way. This code is actually pretty neat, because it is using quite simple constructs from the virtual machine execution engine located inside it.

So, the z-machine is a regular virtual machine that can execute opcodes and also find object properties and values and so forth. Because the game is more or less static, in the sense that the objects contained in the game never change, except to the observer, each object remains in the same position in memory. So, you could refer to the east door in room #3 as object 63 for example, and then use that identifier to reason with that object. Each object has a number of attributes that can be set, which allow you to specify if some door is open or closed. There are also user-definable properties per object.

My interest is mostly in the fact that this model isn't widely used in programs. I intend to write a much more basic proof of concept, where I reserve 2G of memory and start loading concepts into this space. Then I can dump the contents of this space to disk and reload it later, where it will have the same state as before (in contrast to pickling or serialization processes on a per-object basis).

Using Ragel, it should not be too difficult to set up a parsing language which can accept standard sentences in close to natural language, such that it manipulates the state of that heap. Perhaps add a property dynamically to some class, or set an attribute of a certain object instance and so forth.

The idea is that the program, which is not in the strictest sense a virtual machine because it does not yet have opcodes, can be used to insert class descriptions at runtime using language descriptions and then using more sentences you could make specific instances of those "things". Then I'd like to make it possible to load "boot programs" that declare things of a certain type and later on the opcodes as a number of simple operations that can be executed, such that the program can start reasoning on a slightly higher level, without having all capabilities of the program pre-programmed and compiled in. This probably requires dynamic compilation, address substitution and so on, but that'll only be fun :).

At the front of this large bit of memory is a large dictionary of words that it understands, just like the z-machine. The idea is that these words refer to classes, instances or relations, describing their use and their meaning. Then when a word is seen in a stream later, it should be possible to dynamically resolve what should be happening and how the environment changes by looking up the knowledge links, enforcing the restrictions by nouns (an object/class's capability) and the intention of an action (the verb). This probably requires the coding of a couple of rules, but those rules are previously declared and dynamically compiled into another base and referred to as well.

As soon as the dynamic execution environment, programmed and thus driven through natural language, encounters an error, it will report the error in a human-friendly format (because it has access to property descriptions and other natural language stuff inserted earlier). This program won't be as powerful as a real programming language, but I'm only interested in its behaviour for reasoning. If you're interested, you should have a look at Appendix A of the standard rules zip file on this page, that gives an overview how I imagine rules and code is going to be done inside this application.

So in short, the z-machine and adventure games are used as inspiration for developing an environment in which (restricted) natural language is going to drive the logic and what is happening. It will still depend on the "program" (the sentences fed to it) what the environment eventually does (well, I think?), so theoretically it can also be used as a chatbot, or perhaps even a reasoning environment for scheduling problems....? Time will tell!

On reasoning with ontologies in AI

2009-10-04T04:06:00.000-07:00

The image here shows a very simple ontology of cities and countries. A larger graph of one such as the left can be used to make assertions about the location of cities and countries and the sizes of cities. I'll use the graph to show how artificial intelligence is much about reasoning and traversing within graphs. One of the techniques much referenced is "state-space search". Now, that sounds as if someone found a way to make a computer really smart, but once you start working out the details, you realize that such graphs are predefined either statically or dynamically. The static graphs are loaded from some datastore somewhere, the dynamic graphs (probably the usual kind) are the graphs that are dynamically built. A big problem in AI for graph searches is actually knowing which branches to expand, because ideally you expand only those branches with solutions on them. Expanding any others is a waste of time and effort. Currently, AI uses heuristics to approach that problem.

Graphs may also be used in knowledge based systems. The idea is that you insert a lot of knowledge in the form of statements (facts) and that you let the system derive new facts on what is given. So, for example, if you say that a Chicago is a city, and that in cities there live people, then it means that people live in Chicago, so any questions relating to "do people live in Chicago?" can be answered. When you approach the boundaries of the scope of the knowledge, the performance degrades considerably.

So what exactly is reasoning? If we look back at the adventure game of Zork, you could consider the flow of an adventure game as a finite state machine:

In adventure games, the players are reasoners and the pre-defined stories are basically FSM's, created by programmers or story writers. Another way of describing the objective of an adventure game is to find the sequence of commands that leads to a successful finish state. Some game commands don't change the game state, but instead inspect the value of some property or attribute (commands like look, listen, smell, etc.) and return a pre-configured string. Succesful manipulative commands always change the game state, but not necessarily in a way that is useful to get to the end of the game. For example, you could open / close a milk bottle in the fridge repeatedly without having any effect towards reaching the objective. For brevity, any commands that change the world state to something non useful are not visualized in the above graph.

Reasoning in the above graph is really easy, because you simply have to follow the graph from start->finish or vice versa and you solved the problem. It's a single path here. End of complexity?! . Actually, real problems are much more complicated than that, because they have different states that are modified at different moments. To put all the information into a single graph would create one that is too complicated to handle. A state machine can and should handle only one specific memory location (the integer describing the current state) and then the state machine should be accompanied with rules on how that state may be changed. The following graph shows three different state machines, where some transitions contain particular restrictions on when the transition can be executed successfully and when it can't.

We've just made a distinction per state machine based on the observed value of the memory location. So, if FSM_1 governs the locations, then each location is described by a single number. If FSM_2 governs having the key or not, then 6 means not having the key and 7 means having the key.

Reasoning has just become a bit harder in this case. Instead of just finding the reverse path, any reasoning program must start with a potential path that may be possible and then for each transition find out if there are constraints along that transition that might prohibit that change. Further complications arise when a given constraint is based on an event very early in the game, so following a path that eventually fails is very costly. This means that the heuristics for evaluating if the value may ever change in the desired direction becomes of great importance.

The above also shows how software is written. The software specification comes up with a set of rules, which are essentially dynamic generators for several state diagrams. The programmer adds his own variables to that. The programmer then glues various state diagrams together through "if" statements, making the diagrams depend on one another. Then add in a couple of state modifiers (which move one machine from state A -> B) and the party is complete.

Reasoning in this model means generating a deconstruction of the program or specification and inverting it. So a computer that can reason about programs should be able to look at the debug info of a computer program and make statements about how to achieve goal states. A bit like:

For your program to return with code 2, the following paths are possible: "x,y,z,...".
For path 'x' to be chosen, variable i must be equal to 3, j must contain "bird" and k must be less than 5.
For path 'y' to be successful, .....

This shows that in step 2, the reasoning mechanism establishes sub-goals from which reasoning needs to continue. In this case, the sub goals refer to some location in memory and a desirable value for that location. Let's assume that k should never be less than 5, because the knowledge base dictates that it is meaningless (the program contains an error in that case to compare the value to something meaningless). The sub-goal will then disappear from the board altogether, leaving only i or j as possible candidates. Reasoning becomes easier if the reasoning system has access to the inverted program, which I imagine to be a description of some program in reverse.

A genuinely new look at computer-based reasoning could research how conditional jumps are used and whether they are useful for a basis of reasoning. Can they be used to model the complexities of actual reasoning itself? The idea is that without looking at the contents of fields and understanding the semantics, as long as we understand the structure of a state machine (the way how states change), we may be able to reason with it. After all, a name to refer to something is just a pointer to some memory about the properties and classification of such a thing. Just like a computer may have a pointer to a piece of memory that has other pointers to other capabilities.

But what if we only have a start and an end goal and a very large ontology? Then we don't have a program to analyze, only fragments of diagrams that are not connected to one another. The added complexity here is that we should use the rules within the ontology to find ways to connect ontologies and subdiagrams together such that it still makes sense.

Is this different from other logic languages like prolog? Hmmm.. I don't know yet. A good test would be to see if there are different consequences of using such a model. Most programming languages require tests to be written for certain things. And it gets very repetitive to insert lots of facts about the things, plus that an ontology depends a lot on the proper classifications. It's probably related to a different look on things, like complete separation of terms (nouns and verbs) or something.

Lessons from Zork

2009-10-03T12:21:00.000-07:00

If you're in your 30's like me and as a child, you got a Commodore, MSX or one of those other computers in that generation, you might remember playing text-based adventure games. I was hooked on them at age 9 actually and they taught me English (well, and the dictionary did :). Because of those games, I scored 9/10 for all English classes. We never heard of the Internet back then, but there were already English-spoken movies with subtitling on TV then, so that helped as well a bit. However, this post isn't meant to recollect those stories, it's about the design of the interpreters in those times. Just recently, I'm very interested in different designs and approaches to parsing, because it's playing a central role to Natural Language Processing and in that sense to Artificial Intelligent programs that can deal with input in natural language. The Zork text-adventure games were the start of a range of games in the genre. And one of its important necessary features is to accept input from human beings giving orders, process it and then reply back with the results to that command.

Zork actually had a very interesting design of handling this. The story itself was loaded into a z-machine, which executed based on user input. If you want to experiment with such interpreters, have a look at frotz. There's actually a very low-key community in the world who's still playing adventure-games or, as they call it now, reading interactive fiction. They publish their work here and there. Here's an archive for reference.

Initially, you may think that writing a work of interactive fiction or text adventure is a lot of coding work, but there's actually a very cool application that you can use to produce them, called inform. And there is no real coding involved, everything is typed in natural language. Since at one time, a computer needs to run your story, the only not so natural thing is that you declare properties and attributes about things that you personally already take for granted. Because to a computer it is not obvious that a bed can support a person and you can enter it, that needs to be declared explicitly in the story (the story eventually becomes the program). Using inform, a lot more people can write stories and adventures.

At this point, it's probably better to show an example:

The troll can be conscious or unconscious.
Check attacking the unconscious troll with something:
say "The unconscious troll cannot defend himself:  He dies.";
say "Almost as soon as the troll breathes his last breath, a cloud
of sinister black fog envelops him, and when the fog lifts, the
carcass has disappeared.";
remove the troll from play instead.

So notice how the troll is given attributes and properties and how some sort of reasoning process is inserted into this process just by applying natural language. The sequence of words (the phrase) used to manipulate the behaviour of the story (the program) is fixed. The descriptions, what you put between the double quotes, is just a sequence of characters and remains unintelligible to the computer. The story is then first compiled into a slightly lower-level language, which compilers towards z-code can interpret:

[ TakeDrink;
canteen--;
if (canteen lt 0) {
   thirst=0; UpdateThirst();
} else {
   thirst=4;
   "Better watch for an oasis !";
}
];

This lower-level language is the language in which the older text adventures were coded. They used a lot of variables (often global) and contained very simple code that influenced game play. The limit was that of the programmer basically. It probably feels a bit like scripting.

For inform, by declaring items as a kind (a category of what it is, e.g: The spoon is a thing), they instantly get a couple of capabilities and the program knows what can be and cannot be done to them, because the inform compiler combines it with a default rule set (which may be overridden in the text). The (intended) interaction of the player with its environment is always communicated by verbs and nouns. In the case of inform, the file already has a large number of default rules, actions and behaviours for all these verbs and possible interactions. Per verb, the program maintains a number of rules with regards to impossible actions, or perhaps temporarily impossible actions due to some state in the interpreter (maybe the player should eat spinach first before they can open the door?). For further reading, the architecture of inform is listed here.

The interpreter for these programs executes so called opcodes, just like Java basically, so it is a kind of virtual machine. An interpreter is like an implementation of a virtual processor and memory on your computer that has the ability to do things at a slightly higher level of execution and protection (this is another way of saying that you're grouping cpu opcodes together in a useful way). In contrast to a function or method in a programming language, the interpreter makes no assumptions on the context in which it is used, it's only a dumb operational thing. The function or method for general programming languages exist within a very specific context of application.

Because Zork and the z-machine were initially developed for computers with very limited resources (64K? 128K?), there is a lot of optimization being done to cram the strings together (5-bit) and there are limits set on the memory addresses of the interpreter. Nowadays though, those limits can be relaxed heavily and possibly this could allow some very nice programs to be created using these virtual interpreters. Read on here for more information on these z-machines and their relevance to AI.

The text in the link above mentions Prolog. I've come to both respect and hate prolog. Prolog is also an interpreter, but works with a very general-purpose language and is very much related to programming in the general sense. Prolog always attempts to prove that your statements unify to something (become true) and does all in its efforts to make it so. It is strongly related to first-order predicate logic and research that entails it.

Now... you may know that when the program behaviour needs to be extended or modified, you generally need to stop the program, change the sources, recompile and then kill the running application and restart with the modified version. In that sense, a program on a computer is static. It was never considered in the architecture of hardware and software that programs needed to change at runtime. This is because they were executing tasks that were entirely thought out before the implementation. Then the implementation takes place, you run it and it can take care of business for a while.

An interpreter is an ideal environment for running experiments where the program can change at runtime and must be able to modify its behaviour and view on the world. If this interpreter can connect to programs online, the natural language can also be used as a means to communicate ontologies with other programs or humans, much in the same way that the above declarations in adventure games are used to extend the ontology of the adventure game (since that is what it essentially does). The difference is that the ontology is compiled beforehand and from that point onwards becomes static.

The bad thing about AI is that it's feeling the pull of the initial computer years and the way how we think about computers, or actually consider what processing is. To most computer-savvy people, it's the most normal thing to kill applications, recode them, restart them and then observe what it does. I think we should probably regard computers slightly differently to make more progress in AI.

Possibly because of the argument above, ontologies for the web are also mostly expressed as some sort of static files. The idea is that knowledge is temporarily static and then doesn't change? Also, even though they look meaningful to us (although interspersed with nonsense brackets and dashes and other signs), the computer just sees xyzxyzxyz and absdfoip and it's all nonsense to it, except the way in which it appears and can be recognized later. It's the reasoning over those forms of appearance that it can pretend to be processing them semantically. The gotcha is in the fact that when we look at the files, they look meaningful, but that's because the words give us a short replay of the vision, hearing or feeling related to the terms.

The truth is that the computer has no knowledge at all about the meaning of the terms and just executes some other code when it sees xyzxyzxyz again or when it knows that abcabcabc was in one way related to xyzxyzxyz. If you want to do yourself a favour to understand ontologies properly, recode the entire ontology in such nonsense terms and it becomes clear that it's easy to be misguided about how much computers really know.

Conclusion: The design of the z-machine interpreter is a very interesting concept for further AI research. One should not only consider interpreters to be relevant at runtime, but also integrate interpreters with compiler constructs, such that a phrase of input doesn't necessarily only modify the state of the interpreter, but may also modify the program itself (adding knowledge to the knowledge base). This allows one machine to talk to another using natural language (easier to debug) and it requires only one interface implementation, since humans use the same channel of input. The interpreter should also have the requirement that it can sync its state to disk and start up later with that memory load, such that it can continue executing from where it left off the last time. An adventure game interpreter is coded with a goal in mind and that is executing until somehow it reaches an end state (you could visualize the interpreter as a markov chain and even as a finite state machine), where knowledge is fixed and the transitions of one knowledge element to another or one contextual state to another is determined by rules.

Ongoing question: Now, this gives us one interesting question to ponder over next: for an environment in which knowledge may be modified and received and states relating to that knowledge manipulated (the context), who or what will set the goals for this interpreter to achieve and what do those goals look like? Can the interpreter determine its own goals and negotiate with us or other computers to try to achieve them?

CSV file parsing with ragel

2009-10-01T14:49:00.000-07:00

I wanted to get my feet wet a bit more with Ragel to get acquainted with the ways it works. Some good examples demonstrating the syntax are here. It's definitely a very impressive piece of software. Setting up a toy language is a bit too much work for just toying around, so I decided to find out how to parse a CSV file. I started out with the sample to do parameter parsing from the command line and adjusted it to read a 3-column CSV file. It's probably not the most efficient code and leaves things to be improved:


#include 
#include 
#include 

#define MAX_BUF_LEN  1023

struct csvline {
 char *f1;
 char *f2;
 int   f3;
};

struct csvdata {
 int cs;
 int buflen;
 char buffer[ MAX_BUF_LEN + 1 ];
 int field;
 struct csvline line;
};

void print_data( struct csvdata *data, int lineno );

%%{
 machine csv;
 access data->;

 # Append to the buffer.
 action append {
  if ( data->buflen < MAX_BUF_LEN )
   data->buffer[ data->buflen++ ] = fc;
 }

 # Terminate a buffer.
 action term {
  if ( data->buflen < MAX_BUF_LEN )
   data->buffer[ data->buflen++ ] = 0;

  switch( data->field ) {
   case 0:
    data->line.f1 = (char *)calloc( data->buflen, sizeof( char ) );
    strncpy( data->line.f1, data->buffer, data->buflen );
    data->field++;
    break;
   case 1:
    data->line.f2 = (char *)calloc( data->buflen, sizeof( char ) );
    strncpy( data->line.f2, data->buffer, data->buflen );
    data->field++;
    break;
   case 2:
    data->line.f3 = atoi( data->buffer );
    data->field++;
    break;
   default:
    // ignore
    break;
  }
 }

 # Clear out the buffer
 action clear { data->buflen = 0; }

 # Helpers that collect strings
 LF = "\n";
 string = [^,]* >clear $append;
 string2 = [^,]* >clear $append %term;
 comma = "," %term;
 main := ( string comma )+ string2 ? LF;
}%%

%% write data;

void csv_init( struct csvdata *data ) {
 data->buflen = 0;
 %% write init;
}

void csv_exec( struct csvdata *data, const char *d, int len )
{
 const char *p = d;
 const char *pe = d + len;

 %% write exec;
}

int csv_finish( struct csvdata *data )
{
 if ( data->cs == csv_error )
  return -1;
 if ( data->cs >= csv_first_final )
  return 1;
 return 0;
}

#define BUFSIZE 2048

int main( int argc, char **argv )
{
 struct csvdata csvdata;
 FILE *csvfile;
 int lineno = 0;
 char buf[ MAX_BUF_LEN + 1 ] = {"\0"};

 if (( csvfile = fopen( "test.csv", "r" ) ) == NULL ) {
  fprintf( stderr, "Could not open file test.csv\n" );
  return -1;
 }
 
 while ( fgets( buf, MAX_BUF_LEN, csvfile ) != NULL ) {
  // One more line to process
  memset( &csvdata, 0x00, sizeof( csvdata ));
  csv_exec( &csvdata, buf, strlen( buf ) );
  if ( csv_finish( &csvdata ) != 1 ) {
   fprintf( stderr, "error occurred in line: %d\n", lineno );
  } else {
   print_data( &csvdata, lineno );
  }
  lineno++;
 }

 return 0;
}

void print_data( struct csvdata *data, int lineno ) {
 fprintf( stdout, "[line %d] f1: %s", lineno, data->line.f1 );
 fprintf( stdout, ", f2: %s", data->line.f2 );
 fprintf( stdout, ", f3: %d\n", data->line.f3 );
}

The following test.csv file was used:


test1,test2,4000
more,data,5032335
and,even,111
more,data,1213
errorhere
invalid line

And this is how to compile and visualize:


compile.sh:
-----------

#!/bin/bash

ragel main.rl
ragel -V main.rl > test.dot
gcc -o main main.c

visualize.sh:
-------------

#!/bin/bash

dot -Tpng -otest.png test.dot
eog test.png

FSM and ragel

2009-09-29T14:07:00.001-07:00

The diagram on the right is a depiction of a state machine to parse command line arguments. I'm looking at ragel lately, because the architecture and design are genuinely compelling. The philosophy and architecture behind it are not necessarily limited to lexing input or protocols (although that is what ragel basically does). I'm looking at this from the perspective of applied research in intelligent agents knowledge base sharing and upgrading. One of the ideas I was having is whether there is a possibility to develop a common knowledge between two computer processes that is not necessarily static (like 'pre-defined'), but whether it may actually have dynamic properties such that it can reason with its internal state and knowledge base to resolve specific dead-ends and so on.

( btw, just inbetween, for an explanation how I post code on blogger without using syntax highlighter: http://kevin-berridge.blogspot.com/2007/08/posting-code-on-blogger.html ).

The above diagram was generated by specifying a sort of language for the command line arguments that the application understands. Language is to be interpreted in the broadest sense of the word. Think of it as any stream of input characters in which you can convey ideas or specifications of actions to undertake.

In the above diagram, a state is reached when the state machine can successfully pick up the next character from the stream. So, the state machine can move to a different state if it finds that the next character in the stream contains that specific symbol. It's a bit like a filter. Some states have multiple exit points (so they can go over a number of transitions), which is fine. The interesting characteristic of ragel in comparison with lexer is that you're both string matching and executing code at the same time. So when using ragel, you get the opportunity to start executing things which at a later point may not be completable because the final part of the input is missing. It takes a bit of programming to either discard the state or use it any way, it's not applicable in every context. I can imagine that if you work on transaction-based systems, you just panicked with these statements :). There, you typically wait until the full request is in, generate a response and wait for the client to actually tell you to commit and do it for real.

Another interesting part of ragel is that it doesn't use glibc or other heavier functions (possibly that much). In the above example, you'd typically use some strXXX function from glibc to find out what the user supplied. You also need to make sure your buffers are correctly set up and you don't go over them (I always use strNXXXX functions just in case I get caught out). ragel on the other hand works on your supplied buffers immediately and uses pointer arithmetic. There are two output modes: table-based, where the transition of one state to another is more of a path description and goto-based.

Goto's should probably be considered evil, but with state machines I'm starting to think that machine intelligence could greatly benefit from execution contexts that can switch very quickly from one state to another. Earlier posts made in 2007 have already rambled on about stackless python and so on. Having a stack that grows infinitely doesn't help much.

Now, in the philosophy of ragel, would there be a possibility to develop an agent language that runs in some kind of engine where the agent would continuously instruct the engine what to execute next? Maybe a thread-based context of instructions could help to make this multi-processing.

In that line of thought, consider that a state is basically an identifiable place or state of mind or state in a computer. Having an apple in your hand could be considered a state. A large problem in AI is how you make computers reason from one state to another. Generally this is done with a pre-defined knowledge base that defines all the rules before anything is executed. Such machines or robots become applicable to one thing only (that what is in the knowledge base) and not much else.

Now, a start state is known, maybe it's idle or maybe it's about being hungry or some pro-active state where the AI is trying to achieve something (possibly governed by some emotion engine?). The interaction of several state machines together would be really interesting here. The idea is to get from "start" to "goal" state. If the computer would simulate in its engine how it could get from start to goal by going over the transitions, then it may be able to find different ways of achieving its objective. If transitions have costs associated with them, then the AI could reason about the best method to achieve the objective.

Taking a transition also means using its internal resources. It isn't necessarily a trivial task. A robot could be in a start state somewhere identifiable in the current space and it may deem that it is necessary to move to another location, thus another state. The current focus is then how to get from start -> location. The transition to do that is movement and movement is concerned about finding a path from start->location, possibly using intermediate states that could be used to achieve it. If the transition finds through observation that everything is blocked, then it may decide to panic or find other ways (more costly?) to attempt.

What is described here is a design for a flexible reasoning engine depending fully on (a combination of) state machines, which execute snippets of code inbetween its reasoning processes. Combine this with a shareable language between other robots and human beings (interactive terminal?) and the computer could start asking questions...:

Q: "how start->goal?"
A: "apply movement transition"
( robot downloads movement knowledgebase and code? )

A basic scenario involves a monkey, a box, a cage with three prescribed locations and a banana. The objective for the monkey is to grab the banana, which it can only do if the box is in the middle of the room, the monkey is standing on the box and it reaches out to grab the banana. This is a reasoning problem, as the details and specifics of actually executing those actions are of a different domain. Actually, the interesting part would be to communicate to other modules of an AI that something is an objective and leave it to sensors and other stuff to actually carry out the specific task. When those modules all agree the task has been executed, they could communicate this back to the reasoning module, which is now confirmed in the new state.

Ragel doesn't just apply actions when it's doing a transition. It can also do this when leaving states and entering them. This allows for some more flavours of interestingness. The idea is that an AI should be able to dynamically extend its knowledge base (which a couple of implementations do), ideally through communication using a simple, non-ambiguous language to communicate those knowledge gems.

In the example of the monkey above, a goal state could be to "have the banana". The computer then doesn't know how to get into that state, so it needs to understand the differences in the following:

how to grab a banana
how to reach out for a banana
how to climb on a box (and whether it is strong enough to support the monkey)
whether the monkey robot is tall enough to reach the banana without the box
how to move the box around the room (and that the monkey cannot be on the box to do this).
whether the box is in the middle of the room

Using these states, you can draw a state diagram of actions to be executed in a certain order. Eventually, if you leave the reasoning to the computer, it should reach a sequence of actions that is least costly to execute (the shortest way to get there) and that is what it should try.

Writing fast protocol-compliant programs quickly

2009-09-28T12:58:00.000-07:00

I've used bison and flex for some text parsing. Another project of mine was done with ANTLR (see xssprotect), where it's basically an HTML tag filter that allows well-known tags and attributes and removes all others. Flex and Bison work together in a way, but you need to keep on your toes to understand which does what. The combination isn't suitable for all kinds of parsing and one of the reasons why programming languages are non-ambiguous by nature is so that it compiles into machine- or interpretercode exactly as intended by the programmer without unwanted side effects. Regular file parsing with flex and bison becomes more difficult once you don't have control over the format of the input file; that is, if you don't control what it should look like. This is because bison is dependent on the lexer, and the lexer should output the correct tokens such that bison can apply them properly. You could say that the lexer is more about syntax and bison is more about semantics and ordering.

So flex feeds bison and bison allows you to execute actions that should take place once things are recognized. The general tutorials all over the internet always show the same example: a calculator. Some code in flex looks like this:


%{
#include
%}
%s BRACKET
%%
[A-Za-z0-9]+            {  printf("Symbol: %s\n",yytext);  }
"("                     {  BEGIN BRACKET; }
")"             {  BEGIN INITIAL; /* Switch Back */}
[A-Za-z \t]+    {  printf("BRACKET: %s\n",yytext);  }
.|\n                    {  }
%%
int yywrap(void) { return 1;  }
int main(int arg,char *argv[])
{
  yylex();
  printf("Bye...Bye...\n");
  return 0;
}

This is input to flex. It's just printing symbols outside any context and when it encounters any brackets ( or ), it switches to different states, such that certain tokens can be disregarded, or you can start regarding them. The curly brackets are basically standard C code. Other parsers that are more advanced typically use them to return a token value (an integer), such that bison can use it. Bison would then typically attach it to a certain context.

Hence, it becomes clear why programming languages have so many magic tokens, like: { ( [ ] ) } " ' 0x * & ^ % $ # @ \ | ; : and so on. Most of these tokens are delimiters to create some kind of action. The { } tokens are probably the most interesting, as many mature languages use these to control scope of variables and instructions.

Bison scripts look like the following:


input:   /* empty */
    | input line
;
line:
      '\n'
    | exp '\n'   { printf ("\t%.10g\n", $1); }
    | error '\n' { yyerrok;                  }
;
exp:      NUM                { $$ = $1;                         }
    | VAR                { $$ = $1->value.var;              }
    | VAR '=' exp        { $$ = $3; $1->value.var = $3;     }
    | FNCT '(' exp ')'   { $$ = (*($1->value.fnctptr))($3); }
    | exp '+' exp        { $$ = $1 + $3;                    }
    | exp '-' exp        { $$ = $1 - $3;                    }
    | exp '*' exp        { $$ = $1 * $3;                    }
    | exp '/' exp        { $$ = $1 / $3;                    }
    | '-' exp  %prec NEG { $$ = -$2;                        }
    | exp '^' exp        { $$ = pow ($1, $3);               }
    | '(' exp ')'        { $$ = $2;                         }
;
/* End of grammar */
%%

You should notice how the C instructions, also in this case, permeate the general function of the processor. The processor basically has a stack of memory of tokens that were processed before, whether these are simple expressions or tokens ( a "1" is a token and an expression, a "1+1" is an expression composed of two other expressions and an operator). This calculator function above shows how bison works iteratively down your sentence and then compiles a sort of tree structure. This tree structure can be influenced to take operator precedence into account. Also, you could choose to make it contextual here.

The differences between flex and bison should become somewhat clear by these examples. Lexer doesn't know anything about the meaning of what it is processing, just that it complies with the lexing rules. An integer is a sequence of 0-9 digits without any dots or comma's. A float is a sequence of 0-9 digits with a dot or comma in the middle somewhere (followed by more digits). A char token has some alphabetic characters in them. You could easily construct your own language by prefixing or postfixing them and then making sure the rules are processed in the right order.

You could also make the parser interactive, so it becomes a command line application. Rather than verifying the exact thing was entered, you could now attempt to handle whatever was typed. So basically you could create some kind of adventure game with the above. In the adventure game, you'd probably end up recognizing verbs specifically, but maybe use a more dynamic method for dealing with nouns (objects and rooms differ from game to game). That way, the engine is reusable for entirely different contexts.

Now that you know about bison; you'll find ragel and lemon are of better use. These tools have been used to parse SQL, or geographic data (libgeom) for calculating paths and distances and so on. Without too much effort, you could script together a method for doing geometric calculations that way, such that you can invoke this from the command line.

Notice how the parser does force you to think in tree structures though. Check out this link for why state machines are quite interesting from a protocol design / implementation perspective. Often, when you parse code yourself, you find yourself knee-deep in invalid states, states that should not be reached from certain contexts, and so on. Why program that yourself? :)

State machines are also often used in Artificial Intelligence, so it makes sense in certain places to mix up these things with artificial reasoning. The problem with state machines is that it's possible to have missed some dead-end. In that case, the machine may become stuck forever and might not be able to find a sequential state to go to. Ragel though has a nice way of showing it's rules in a directed graph. That should help to make things clearer and spot those difficult places.

Linux: epoll performance and gotcha's

2009-09-20T13:21:00.000-07:00

This is a graph of a very small test I have been running to test the performance of synchronous vs. asynchronous I/O. The previous post already showed how lighttpd is using the epoll interface. I wanted to do some testing on my own with my own implementation.
In this test, I'm using a single dual-core machine (E6850) with 4GB memory on a 1333 MHz bus with CL9. The forking server is very crude, which basically forks after accepting a connection. This could certainly be done more effectively by pooling threads and so on, but that is what the sock queue already simulates. The idea is to show the effect of creating new processes to handle new traffic and how this affects overall machine performance.

The forking server shows varying performance. At some point, the socket queue of the process within the kernel is full and the client is either waiting 3, 9 or 12 seconds to obtain a connection, probably because the kernel stalls connections (SYN flood protection?) or needs to clean up resources before it continues to accept new ones. Actually, I didn't wait for this process to finish. When you add the time required, it was running about 1 minute and did 5800 connections. So that performance is very poor. Programming wise though, things are very easy, especially using standard C available on every decent UNIX machine, since it was just an accept and a fork. (The gotcha was that you need to close the parent's file descriptor and waitpid on child's processes, otherwise it's holding on to resources).

All processes had their file descriptor limit increased to 65536 (ulimit -n 65536) and processes were run as root to prevent having to build in some setrlimit call and other complexities.

The socket queue with 8 threads is basically a round-robin fire and forget mechanism. It is implemented with glib and similarly to fork, it isn't as difficult to implement. Basically, it has one thread to continuously accept new connections as fast as it can, then it hands the socket descriptor to one of the queues in a round-robin way. The threads at the other end consume from their queue when a descriptor becomes available and process the socket until empty. Since this is all running locally, there is virtually zero latency and we know that each client connects and writes as fast as possible. Since the server doesn't create new threads or sockets, this is actually quite efficient. Problem may become when sockets actually start blocking, then you may need more threads to handle them.

The epoll() method with 8 threads is the most fancy one and actually skips a couple of other possibilities in the middle. It's strictly using asynchronous I/O, which is also the most difficult to implement. The advantage is that none of the threads ever block and are therefore always looking to do something useful. In this case, I configured eight worker threads as well. The performance is very similar to the queue one, but in different circumstances the epoll() method will certainly outperform the others. The reason is that the previous one will block waiting for something to read. Alternatives to epoll() is poll() with a self-maintained list of socket array. Eventually, those lists need maintenance and therefore they need to be processed linearly in each thread at some point. That is O(n) time, so it doesn't scale as well as epoll(), which has O(1) performance, plus the array maintenance that needs to be coded.

The simple client used in these tests is an absolute psychopath. It attempts to connect up to 125 sockets at the same time and maintain that number (that means a barrage of 125 SYN packets in a very quick succession from one thread in the beginning and as many as it can, up to 125, whenever connections get processed). This client also uses asynchronous sockets. The technique is similar to non-blocking connect() calls with select() or poll(), but in this case you feed the descriptors to epoll() to let the kernel figure everything out. The gotcha here is that the data structure used in the epoll_event structure is not a 4-attribute structure, but a union. That means that you can set only any one of the fields, but not two. For example, writing the fd field to store the socket descriptor overwrites a ptr and vice-versa.

Thus, the implementation for the client is like:

open socket
set socket to non-blocking
call connect(), this doesn't wait around until it completes. It almost always returns "EINPROGRESS".
store the socket + connected info in a specialized structure in epoll through the data.ptr attribute.
open another socket.

After 125 sockets are open at the same time:

see if any sockets have completed already, write a little bit of data and close the socket.
this may free up a couple of places, after which new SYN's are sent.

The quicker the server accepts new sockets, the faster it can go, especially when clients are suffering from a bit of latency. In the epoll and queued sockets structure above, I cycled through 30,000 connection requests in 4-5 seconds. That's about 6,000 processed connections per second. This is in an environment where both client and server run on the same machine. The problem that this load faces is that the machine runs out of sockets, because due to the speed, there are a lot of sockets in the "ESTABLISHED" state (that's how quick the NIC is and how relatively slow the NIC is :). Sockets in ESTABLISHED state consume file descriptors and you can only have so many open before you run out. Modern servers should be able to handle 10,000 connections at the same time however. Running this on two different computers should give twice the number of sockets available.

The idea of the above is to develop software where the system becomes network-constrained. A lot of software, due to its architecture, doesn't use all of the network's bandwidth, but it probably uses all of CPU or memory. Threads and processes require a stack space to operate, because they call functions and leave other data on the stack for reference. The 90's way of handling traffic was to add threads and processes, which increases the requirements for memory and CPU. The context switch and process management becomes a bigger bottleneck (since that's what the kernel does). The Linux kernel has a very nice scheduling system now, which is default, which also has O(1) performance. So you could have 10,000 processes hanging around quite easily, but at some point you do noticeably see performance degradation, especially once the kernel needs to traverse the process lists every x (here 1) ms. That is why having one process/thread per socket is a bad idea.

Increasing throughput on LAN's has some more considerations and options for tweaking. Most Linux distributions are pre-configured for internet use, which means that their window sizes are different from a LAN. This is because if the round trip time is high and you send a large packet, which somehow gets lost, the cost of resending that packet is high. So a smaller packet would do better. But if you only send 1 byte per packet, then you're not getting anywhere either. Linux actually seems to optimize that in the kernel now. High performance servers sometimes need a bit more local ports to deal with incoming traffic. This can be modified non-permanently in /proc/sys/net/ipv4/ip_local_port_range.

Supercharging reliable packet transfer capacity

2009-09-19T05:50:00.000-07:00

Lighttpd is a very light, high performance web server that uses a different architecture for handling connections. It is being used for meebo and youtube, but probably with modifications. Although Apache is the best known webserver around and has been used for years as a very reliable webserver, the rise in network communications capacity is showing that the software itself is now more likely the bottleneck in communications than the hardware itself. Apache with its threaded architecture doesn't scale as well or use the hardware resources as well as lighttpd can. The reason is related to the specific use of resources on the operating system, like the number of file handles, threads, and so on. Two very important issues become copying data from socket to kernel memory and finally to user memory. This is one copy too many and people are researching how to prevent this first copy taking place, such that data arriving at the network card can be copied straight into user memory when available. The second problem is related to the overhead of thread/process context switches and the repercussions a high number of threads and processes have on overall system performance. In effect, the consequence of these systems is that the kernel spends more time figuring out which thread/process to run and housekeeping efforts become larger.

In communications where sockets are associated with threads (let's assume for the remainder of this type that threads and processes are interchangeable), the threads typically block on particular operations within the communication cycle. So, writing to a socket may succeed immediately, or it may block the sender until either the socket is disconnected or the remote end has received the data, such that the client buffer sending the data becomes free. If the thread blocks on either send or receive, the thread is put into a particular blocking state, signalling the kernel that it only needs to be woken up if some buffer becomes empty or data arrives at the socket. Having, let's say, 10,000 threads around then sounds like a lot, but in the end only a couple of those threads are actually executable on the CPU. The advantage of this approach is that programming is pretty clear and the program is easy to understand. The disadvantage is that this model is not scaleable towards the actual hardware capacity installed.

In looking at some specific problems I am facing, I also noticed that this above model doesn't scale at all for situations where clients send out notification packets. Those are characterized by clients sending a bit of data and closing the connection immediately. They can then pick up another notification to be sent, send it immediately and cycle on that. It is also possible that there are a large number of clients sending data.

For these situations, TCP state transitions look like this:

client         send ->     <-  send     server
ESTABLISHED     FIN           --        ESTABLISHED
FIN_WAIT1       --            ACK       CLOSE_WAIT
FIN_WAIT2       --            --        CLOSE_WAIT

...... server processes .......

FIN_WAIT2       --            FIN       LAST_ACK
TIME_WAIT       ACK           --        CLOSED

The "CLOSE_WAIT" state is maintained until the server has accepted the socket (which is already in CLOSE_WAIT now), reads the data, then closes the socket itself. A more serious problem arises when the number of sockets in CLOSE_WAIT equals the size of the backlog queue of the listening socket. Let's say this is 128, which is a reasonable number for Linux. The number of sockets in CLOSE_WAIT becomes 128, the server doesn't accept any more connections and it only allows more connections when the server picks up one of the pending connections by calling accept(), handles it and closes it. If the number of clients is relatively high, this server becomes a bottle-neck for any communications up-stream.

Lighttpd supports a new architecture that is available for newer kernels. Actually, it supports a couple of new constructs for handling TCP traffic, that which are given by kqueue, epoll, select, poll and so on. The ideas of these architectures is that a thread should not be created just to wait for data to come in, but the thread selects which sockets are in a state that a successful read or write can take place and the CPU will initiate those actions. The idea is that you use less threads to do the same kind of work with better use of resources, such that you become more efficient overall, such that you can handle more connections and communication overall, increasing the throughput which should easily be handled by the server.

A very good discussion on performance is here. It is also linking to a very good presentation.

Grozzr

2009-09-13T09:41:00.000-07:00

If you want a geeky way of doing groceries, try out http://grozzr.appspot.com. It's a minimalist application to write shopping lists online on Google. Because it's hosted on AppEngine, you can return to the list later, add stuff, remove stuff, and so forth. Cool thing is that it is integrated with Android. If you have an Android phone, you can download an Android app online which syncs the online list with one of the shopping list applications you may have installed (like OI shopping list or Trolly). See the QR code below where you can download the app from:

I've written this to make this slightly easier. No pen and paper and you always have access to the shopping list. I'm trying to add as little features as possible and do the one thing really well, which is writing shopping lists. One thing I might add is the ability to send the list to an email address of another user who might have an android phone, who could then use a temporary key to access the list and sync without having to login. But nothing much beyond that.

Try it out and let me know what you think!

Tried out a new distribution: Fedora

2009-09-09T14:19:00.000-07:00

I've used Fedora for the first time now. Like Ubuntu and Debian relationships, Fedora is a distribution that started after RedHat release 9 for home-users. RedHat sponsors Fedora heavily, but has put RedHat Enterprise Linux after the Fedora developments. So basically, the community is expected to innovate on the platform and RedHat sits around these developments, sponsoring Fedora where required and streaming those developments back into the enterprise product.

I'm now using a couple of Linux distro's actually. Some of the servers are running on CentOS, where CentOS is basically the opensource distribution of RHEL, as RedHat is required to release the software under the GPL license. So in a sense, CentOS == RHEL without the support contracts.

It's the first time I've been using SELinux as well. I can't say I'm truly happy about it, it's a bit invisible to the first-time user. I've managed to get things started ok and some nice things are coming out of Fedora, but I do think that Ubuntu support for many desktop tasks is slightly better. It's probably because of the widely visited Ubuntu forums. All-in-all, Ubuntu is slightly friendlier for using the platform, but Fedora has some great and innovative features and probably contains things I haven't even discovered yet.

From the software perspective, they seem to have more or less the same availability. RedHat systems use "yum" for package management though and Ubuntu (+Debian) use apt, that's the difference. Personally, I slightly prefer apt still. Install-wise, things are pretty easy nowadays. It all installs without a hitch.

Truth about Amsterdam

2009-09-07T11:36:00.001-07:00

Apparently some guy called Bill O'Reilly from Fox News has painted a very untrue and wacko picture about Amsterdam. Now some people from Amsterdam set up a website to show people what it is really like. I worked right in the center of Amsterdam for the last year, my uncle and aunt lived there for their entire lives, I've studied there for five years and it's really just great. What drugs? What violence? What weapons? What crime?

Come to Amsterdam and see for yourself! I promise you'll have a great time!

Distributed Hash Tables

2009-09-05T02:40:00.000-07:00

I've looked shortly at DHT, als called Distributed Hash Tables. DHT is not only a way to store data in some cloud of computers, it can also serve as a resilient, robust cloud of storage. It's basically a technology that has a very simple manipulation interface (get, remove, set). The differences between specific DHT's relate to geography and oriëntation of nodes, data versioning, hash generation, language of implementation and so on. If you want a clean version, look for projects like bamboo, openchord, opendht, and the likes. Other projects already put in some more functionality, like Project Voldemort.

There are some disadvantages to the use of DHT:

It doesn't provide absolute guarantees on data consistency and integrity (but doesn't necessarily make a total mess either, check Amazon's paper on "Dynamo").
It's not very useful for "group" queries, range queries or other kinds of data lookups.
It doesn't natively support events or triggers very well.
There is no authority in the network. So nodes have to cooperate between them in case certain decisions need to be made.
Lookup of data is O(log(n)) and may take 2 or more seconds, depending on the real location, how many nodes there are and individual latencies between nodes.

There are clear advantages too:

It's highly resilient to network leavers/joiners or other big changes around the network. Most implementations handle node changes very well.
Data is automatically distributed, according to specific configuration options. The specific way how data is eventually organized depends on the chosen strategy in the design. For example, the way how nodes are organized (-ing) together is very important.
Data is replicated across nodes, so it's difficult to lose it.
The removal of any single node doesn't impact the network overall in any way.

Now, if you read the wikipedia page, you'll also see products that use this technology. BitTorrent is a protocol that is very effective in the distribution of file parts, but before you can start sharing a file, you need a way to find it. Finding files works by creating hash keys of them, which is basically an alternate key. By setting up a server where you can browse contents and which has an index of files that are in the network, you can find the content you're looking for and then by downloading a .torrent file, you get the hash key used to find peers in the network that can serve the content you're looking for. From that point onwards, you can communicate with the individual peers to start downloading.

Because keys allow multiple values, you can add yourself as a peer to share the file as well, so that others can negotiate with you on the file parts you may have that they don't. So, DHT in this context is used as a very effective mechanism to find peers to communicate with.

There are other uses of DHT once you start building some logic on top of this simple interface. You could create a virtual file system for example. A key with "/" can be loaded with a set of values, which are the 'subdirectories' that are valid under /. Then you just keep going until there are no more files. To get a file directly, you should be able to look for a key : "/work/myfiles/important-document", in order to get information about the location of that file.

Because projects like Hadoop have different ways for large file replication (blocks of X MB) across a huge cluster, using a DHT layer under this system could store the locations of each replicated block. Nodes themselves can manage their own files this way. This could possibly remove the need for the authoritative and centralized HDFS file directory server and make the network overall more robust and resilient (the HDFS central server is a single point of failure).

It's also possible to store files in two formats: the /x/y/z way, which is meant for finding information and the /nodeX/files way, which indicates the files located on a single machine. If each node itself manages and maintains that information, the rest of the network can react to node crashes by just looking up this information from somewhere and act on this.

The above method for storing information doesn't deviate much from Prefix Hash Trees. A complication in DHT is that you cannot access data by parts of the key (a search) because they are all hashed and unreadable, so you can only find data when you have the key in its entirety. You could create a database in this network as a kind of directory, but that introduces a single point of failure again. The schemes above make this slightly more accessible. This is also the reason why DHT's are not the right solution for every problem. It works when you access lots of data by the same primary key. Facebook uses it for showing entire user profiles, slashdot for storing and retrieving rendered comments. The only thing you need next is a method for expiring entries.

DHT's are generally stored in memory, making them really fast for lookups. Most of the times this is acceptable, but sometimes you want a bit more persistence by having individual nodes store their bits around this network. The biggest problems are faced once a node goes offline for a longer period of time and then reconnects. It is possible that the data it stores is now partly expired and you don't want those bits of information to get back on the network overall. It is also possible that certain updates have changed the information, so that it is newer, which the old keys do not contain. Amazon's Dynamo has more or less solved this by the use of "vector clocks". At some point, you need reconciliation.

Virtually, you could store everything in this network, but you need to know of course what something is as you retrieve it. If you're only looking at non-binary data, an efficient method for storing the data could be JSON. I doubt you'd need "protocol buffers", as they're designed for streaming access to large amounts of data. But possibly you could use the compiler in the project anyway to store it in the described format. That allows you at least to have the storage part covered, so that later you can create apps on top of DHT in python, C or Java.

What is so nice about DHT? The design allows you to work on top of a distributed system, if designed right of course, where you need not worry about fault tolerance within the application. Basically, once you are connected, you just write and read to your heart's content and it should work.

Android: Piggy-backing on the WebKit browser

2009-08-28T14:22:00.000-07:00

I've been looking for ways to not store or request username/password combinations for an Android app. The application I'm developing basically needs to get some data from a Google AppEngine application that is deployed, but that app uses authenticated users for doing some queries. I am actually reluctant to request username/password for the application to login, since I don't want people to even believe the combinations can be misused.

Ideally, I want the users to log in using some login provider on the android platform, or reuse login capabilities for gmail/calendar synchronization services, but I don't think that may be possible.

The objective is to just sync some data from the web, after the user logged in with their credentials. The login is then used to perform the query with. All this without needing to have another app register precious login details in its own space, which may get lost or recovered somehow by others.

Webkit to the rescue!

WebKit on Android can be used to show HTML help pages that were bundled along with the app. Also, you can programmatically construct a browser view then use events on the webkit browser to detect when a user finished its conversation (the login process) and then recover the cookies and use that to call the actual service with. The following snippest show how this can be used in practice:

WebView webview;

private class HelloWebViewClient extends WebViewClient {
@Override
public boolean shouldOverrideUrlLoading(WebView view, String url){
view.loadUrl(url);
return true;
}
@Override
public void onPageFinished(WebView view, String url) {
super.onPageFinished(view, url);
CookieManager mgr = CookieManager.getInstance();
Log.i( "HelloAndroid", url );
Log.i( "HelloAndroid", mgr.getCookie( url ) );
}
}

@Override
public void onCreate(Bundle icicle) {
super.onCreate(icicle);
setContentView(R.layout.main);

webview = (WebView) findViewById(R.id.webview);
webview.getSettings().setJavaScriptEnabled(true);
webview.setWebViewClient(new HelloWebViewClient());
webview.loadUrl("http://yourapp.appspot.com");
}

That's a good start for temporarily using the browser to do the login. The advantage is that username/password combinations never travel through your app and the standard web mechanism is used to obtain a set of cookies to use for navigating further. The username/password remain very volatile in this entire process.

Since I am sort of running the application in a browser, there are ways for this android app to 'step out' of the browser through one of the events and call local services. As a matter of fact, there is a very nice addJavascriptInterface call, which can register a specific interface in Javascript, which can be called by downloaded HTML pages. Certainly, care must be taken security-wise not to have any other pages loaded in the same browser instance that could also call the javascript interface.

class Logger
{
public void log(String content)
{
Log.i( "HelloAndroid", url );
}
}

..... setWebViewClient(new HelloWebViewClient());
webview.addJavascriptInterface(new Logger(), "Logger");
webview.loadUrl( ........

If then your remote HTML file contains:

window.Logger.log( 'hello Android!' );

You basically have a way to let your android phone do things through the remote server app. The WebViewClient should probably contain a couple of safety controls to disallow browsing to foreign destinations.

Why is this so interesting? because you can now create a server-based GWT app and create a nice-looking browser-based interface (generated or stored server-side) and possibly avoid a good deal of code for native interfaces.

It should even be possible to finish up the browsing part if the server dictates so and continue with some intent on the handset device (and possibly return later).

My intention is to just sync some information for another app and then use that data for other purposes locally. The browser allows me to use GWT all the way, so I can use that to do the very effective GWT-RPC calls to communicate data across effectively. The GWT client code can then call the pre-meditated interfaces in the android app, and we're done!

On towards the next phases... :)

Confabulation and how it relates to SVD?

2009-08-17T09:22:00.000-07:00

I've been reading up on this confabulation theory. It's pretty interesting work, the theory, but the practical implementation isn't as nice as the ideas behind the theory :). The use of matrices in the implementation seems to basically make this a problem of statistical analysis. The difference with Bayesian theories and other probability frameworks is that this theory assumes a "causal" relationship between one and the other, not in the way that Bayes does, but through cogency maximalization.

In the end though, and reading the word "matrices" somewhere inbetween, it all sounds a bit like singular value decomposition with a twist, rather than something entirely new. I've been looking for ways to replicate their results somehow. I came up with the following:

Using Hadoop as an underlying platform for simple tasks (like counting words, ordering them, etc.), you take out a lot of complexity out of a program. So I'm using Hadoop to count word frequencies and the frequencies that words are seen together and at which distance.
Hadoop provides a platform where I'm mostly using files, intermediate results stored in files and reducers to bring back some sanity. If I'd had to program that myself, I would be more concerned about stability and reliability than the core of this little research, statistical analysis (in short).
The results are used to train a couple of SVD's á la Netflix - gradient descent. Because I've got a good 1GB file of frequencies, I don't need to process text anymore, it's all ready for learning. (text processing required 5hrs to process and get the results together. The problem in learning is that the statistical significance is only apparent after the entire lot was processed, or you'd have to heuristically make estimates).
The SVD's are about 60M in size. On my machine with memory left, I could theoretically get to 33 SVD's, working together.
The pre-processed files allow me to process the entire "frequency" file line by line, one after the other. I post-processed it to take out any words I did not recognize.
Since I know the statistical significance of each word, how it relates to another and by what distance, I can just keep on training the features of each SVD. Not knowing that beforehand makes training slightly difficult (doh!).

I also thought about possible results of confabulation if it were implemented as a chat bot. Suppose that the technology were ready to produce sentences as if a chat session was going on. The Turing test is one important test, where judges need to make clear distinctions between humans and computers. Since this is a subjective test, I can't help but think that there's also an element of expectation involved. The judges know what a computer does, how it operates and what its limitations are. Now, if someone invents something really cool that breaks that barrier, the judges may temporarily be baffled and come to incorrect conclusions. But as soon as they learn about the research, they may adjust their expectations, raising the bar for the future.

In short, *can* the Turing test ever succeed? Because what if a computer OVER-performs, giving away its true nature? It seems that for a Turing test to succeed, the computer must be on the exact cognitive level of a human being, not higher or lower.

Anyway... Hadoop is really cool and useful. Having another computer in the network would half processing times. Hadoop + custom programs + post-processing scripts sound like really useful ways to pre-process huge amounts of text before you let a machine learn days on end. Since the end product are files that are in a more "edible" format, it should be a lot faster to do the research cycle.