Philosophy of Mathematics

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.

New kind of science

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.

Constraint programming

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:

1. Every student can follow all the registered courses
   
2. All courses are taught the correct number of times per week
   
3. A professor is teaching a course, but never teaching two courses at once
4. A classroom is not used for two different courses at once
   
5. There may be a preference for the time of day a course is taught
6. Ideally, there are no hours between courses for any student on any given day (courses taught are consecutive)
   
7. Some professors may have registered time off on particular days
8. Some professors may indicate preferences for time off, but not as a hard constraint
9. There may be preferences for using classrooms that are close together for consecutive courses
10. Classrooms are typically used for particular departments of study
11. 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

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

The "von Neumann" machine & parallel processing

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.

AI Challenge progress

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

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

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.

What knowledge may actually be about...

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

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

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

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

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

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

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

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

Cybernetics

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

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

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

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

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

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

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

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

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

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

Neural network dynamics

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

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

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

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

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

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

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

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

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

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

The brain in a vat

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

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

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

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

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

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

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

Sane Value Decomposition

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

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

A = U Ʃ V

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

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

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

Example:

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

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

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

Ʃ(1) = avg * sqrt( number_of_cells )

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

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

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

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

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

And here are U and V:

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

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

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

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

Let's look at a regular matrix:

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

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

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

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

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

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

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

Aij = Ri1 * Cj1 * Ʃ1

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

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

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

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

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

Reasoning with(in) language

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

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

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

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

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

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

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

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

Semantique

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

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:

1. For your program to return with code 2, the following paths are possible: "x,y,z,...".
2. For path 'x' to be chosen, variable i must be equal to 3, j must contain "bird" and k must be less than 5.
   
3. 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.