MOSES Tutorial

From OpenCog
Jump to: navigation, search

Here's a very short tutorial on how to use MOSES. MOSES is a large and very complex system; the below just covers the basics of running some of the demo problem solving modes. It does not delve into using MOSES for regression on any 'real-life' classification problems. Doing so requires bucketizing data (outside of the score of MOSES), performing feature selection (although MOSES now has a very effective dynamical feature selection built into it), and tuning many of the MOSES parameters for performance.

Install

First, if you haven't done so, build and install OpenCog. There is no subsystem in the opencog/opencog repo that requires moses, so depending on how you built opencog, moses might not be installed by default.


How to install MOSES  
To install MOSES, you need to install octool (if you haven't already done so)

Install octool (OpenCog Tool)

To install octool at the Ubuntu command prompt, first download (and make executable) the octool package by typing: wget http://raw.github.com/opencog/ocpkg/master/ocpkg -O octool && chmod +rx octool

Next install MOSES

Then to install MOSES type ./octool -m


The main executable of MOSES is

moses

This executable should be in your PATH if you "make install" OpenCog after compiling. Ensuring moses is in your path is especially important to run distributed MOSES.

Note: If you get the error

moses: error while loading shared libraries: libcomboreduct.so: cannot open shared object file: No such file or directory

You should run the command below after doing make install

sudo ldconfig

Man Page

To display the manual page for MOSES, say:

man moses

Or alternately, review the man page mirror here. The command also prints detailed help:

moses --help

or simply

moses

Built-in examples

Moses has several built-in example inputs: these are specified with the -H flag, and include:

  • pa -- parity
  • dj -- disjunction
  • mux -- multiplex
  • sr -- polynomial factorization
  • cp -- regression to a combo program.

For each of the above, MOSES automatically builds an input table, and then tries to learn the combo program that reproduces that input table. So, for example, for the 3-parity problem, the input table would consist of 23=8 rows, holding all possible settings for 3 bits. MOSES then tries to learn a combo program that returns true if the number of bits is even, and false when the number of bits is odd.

The dj, mux and sr are other 'standard' demo problems often posed in machine-learning literature and competitions.

For the last case, cp, MOSES will take an input combo program, turn it into a table, and then try to learn that program. This allows testing moses to see how well it learns arbitrary combo programs.

The above do not require any input files. Regular problem solving can be done with:

  • it -- regression based on input table
  • ann-it neural-net regression

1-multiplexer

To run the example, enter:

$ moses -Hmux -k1

Option -H specifies the problem MOSES must solve, here mux stands for multiplex (the list of problems can be obtained from MOSES' help). Option -k specifies the size of the problem, here 1-bit that chooses between two lines.

The solution is returned on stdout preceded by its score, here 0.

$ moses -Hmux -k1 -r0
0 or(and(!$1 $2) and($1 $3))
0 and(or(and($1 $3) $2) or(!$1 $3)) 

A score of zero corresponds to a perfect score; negative scores indicate the number of wrong answers (number of rows that would be incorrect in a boolean truth table). Note that two different answers are provided: both of them are logically equivalent. The first answer is clearly a multiplexer: it chooses bit $2 if $1 is false, and it chooses bit $3 if $1 is true. The second answer is also correct, it is just a bit more complex and harder to understand.

The -r0 option specifies an initial random number seed. Picking different random seeds will cause the system to find different (but logically equivalent) solutions. Try some different values for -r.

The -k2 option will solve the 2-bit mutiplexer: two bits choosing between 4 lines; it takes a little longer to solve. The -k3 option specifies the three-bit multiplexer, which chooses between 8 lines; finding a solution to this requires extending the runtime with the -m flag, and can take up to half an hour of runtime.

5-parity

$ moses -Hpa -k5

This time we run MOSES on 5-parity. This problem is much harder so it takes a while to display the solution... well, to be more precise, the set of non-optimal solutions it has found given the resources allocated:

-11 or(and(or(and(or(!#1 #4) or(!#2 #5)) and(#1 !#2 #5)) !#3) and(or(and(!#1 #5) and(#4 #5) #2) #3) and(!#1 #4)) 
-11 or(and(or(and(or(!#1 #4) or(!#2 #5)) and(#1 !#2 #5)) !#3) and(or(and(#4 #5) #2) #3) and(!#1 #4) and(!#1 #5)) 
-11 or(and(or(and(or(!#1 #4) or(!#2 #5)) and(!#2 #5)) !#3) and(or(and(!#1 #5) and(#4 #5) #2) #3) and(!#1 #4 !#5)) 
-11 or(and(or(and(or(!#1 #3 #4) or(!#2 #5)) and(#1 !#2 #5)) !#3) and(or(!#1 #4) or(#2 #5) #3) and(!#1 #4 !#5)) 
-11 or(and(or(and(or(!#1 #4) or(!#2 #5)) and(#1 !#2 #5)) !#3) and(or(and(!#1 #5) and(#4 #5) #2) #3) and(!#1 #4 !#5)) 
-11 or(and(or(and(or(!#1 #4) or(!#2 #5)) and(or(#1 #4) !#2 #5)) !#3) and(or(and(#4 #5) #2) #3) and(!#1 #4) and(!#1 #5)) 
-11 or(and(or(and(or(!#1 #4) or(!#2 #5)) and(!#2 #5)) !#3) and(or(and(!#1 #4) and(#4 #5) #2) #3) and(!#1 #4) and(!#1 #5)) 
-11 or(and(or(and(or(!#1 #3 #4) or(!#2 #5)) and(#1 !#2 #5)) or(#2 !#3)) and(or(#2 #5) #1 #3 #4) and(!#1 #4 !#5)) 
-11 or(and(or(and(or(!#1 #3 #4) or(!#2 #5)) and(#1 !#2 #5)) !#3) and(or(and(!#1 #5) and(#4 #5) #2) #3) and(!#1 #4 !#5)) 
-11 or(and(or(and(or(!#1 #4) or(!#2 #3 #5)) and(#1 !#2 #5)) !#3) and(or(and(!#1 #5) and(#4 #5) #2) #3) and(!#1 #4 !#5)) 

By default the number of evaluations MOSES allocates to the resolution of a problem is 10000. You can modify the number of evaluations using the -m option. So let's try with a higher number of evaluations to see if we can reach the solution.

moses -Hpa -k5 -m100000

It's going to take a while (depending on your machine), so let's follow what's happening inside MOSES by looking at its log.

In a new terminal, but in the same directory you've been running our 5-parity example, do

tail -f moses.log

here's an example of what the displays might look like (it will be different depending on the moment you run tail)

[2011-01-24 07:40:44:340] [INFO] Deme expansion: 5
[2011-01-24 07:40:44:341] [DEBUG] Attempt to expand with exemplar: or(and(or(and(or(!#3 #4) !#2) and(!#1 #5)) or(!#1 #5)) and(#1 #2 !#5) and(!#3 #4)) 
[2011-01-24 07:40:44:341] [DEBUG] Scored: -11
[2011-01-24 07:40:44:341] [DEBUG] Representation building from exemplar: or(and(or(and(or(!#3 #4) !#2) and(!#1 #5)) or(!#1 #5)) and(#1 #2 !#5) and(!#3 #4)) 
[2011-01-24 07:40:45:257] [DEBUG] Created prototype: and(or(and(or(and([or nil !or](and([!#3 nil #3] [nil #1 !#1] [nil #5 !#5] [nil or](#4 #5) [nil or](#1 #4) [nil or](!#1 #2) [nil or](!#2 #4)) [#4 nil !#4] [nil #1 !#1] [nil #5 !#5] and([nil #1 !#1] [nil #5 !#5] [nil or !or](#1 #5))) or([!#2 nil #2] [nil #1 !#1] [nil #3] [nil #4] [nil #5 !#5] [nil and](!#1 #3) [nil and](#3 #5) [nil and !and](!#3 #4)) [nil #1] [nil #5] [nil or](#1 #4) [nil or](!#1 #3) or([nil #1] [nil #5] [nil and](!#4 #5) [nil and](#1 #3))) and(or([!#1 nil] [nil #2 !#2] [nil #3 !#3] [nil #4 !#4] [nil and !and](!#2 #3) [nil and !and](#2 #3)) [#5 nil] [nil #2] [nil #3 !#3] [nil #4 !#4] [nil or !or](#3 #4) or([nil #2] [nil #3 !#3] [nil #4 !#4] [nil and](!#2 #4))) [nil #3 !#3] [nil #4 !#4] [nil and](#1 #4) [nil and](!#2 #4) [nil and](#1 #2) [nil and](!#2 #3) [nil and](#4 #5) and([nil #4 !#4] [nil or](#1 #2) [nil or](!#3 #5) [nil or](#2 #5) [nil or](#2 #3) [nil or](#1 #3))) [or nil](and([!#1 nil] [nil #2 !#2] [nil #3 !#3] [nil #4 !#4] [nil or](!#2 #5) [nil or !or](#2 #3) [nil or !or](!#3 #4)) [#5 nil] [nil #2 !#2] [nil #3 !#3] [nil #4 !#4] [nil and !and](!#2 #4) [nil and !and](#2 #4) and([nil #2 !#2] [nil #3 !#3] [nil #4 !#4] [nil or !or](!#3 #4) [nil or !or](#2 #3) [nil or !or](#2 #4))) [nil #3 !#3] [nil #4 !#4] [nil or](#4 #5) [nil or](!#2 #3) [nil or](!#3 #4) [nil or](#2 #4) or([nil #4 !#4] [nil and](#2 #4) [nil and](!#1 #4) [nil and](#3 #5) [nil and](#2 #5) [nil and](!#2 #4))) and(or([#1 nil !#1] [nil #3 !#3] [nil #4 !#4] [nil and !and](!#3 #4) [nil and !and](#3 #4)) [#2 nil !#2] [!#5 nil #5] [nil #3 !#3] [nil #4 !#4] or([nil #3 !#3] [nil #4 !#4])) and(or([!#3 nil #3] [nil #1 !#1] [nil #2 !#2] [nil #5 !#5] [nil and !and](!#1 #2) [nil and !and](#1 #2)) [#4 nil] [nil #1 !#1] [nil #2 !#2] [nil #5 !#5] [nil or !or](#1 #5) or([nil #1 !#1] [nil #2 !#2] [nil #5 !#5] [nil and !and](!#2 #5) [nil and !and](!#1 #5))) [nil and](#2 #3) [nil and](!#4 #5) [nil and](!#1 #5) [nil and](!#2 #3) and([nil or](!#4 #5) [nil or](!#1 #3) [nil or](#4 #5))) [nil or](!#2 #3) [nil or](#1 #4) [nil or](!#2 #4) [nil or](#1 #2) or([nil and](#1 #3) [nil and](!#1 #5) [nil and](!#1 #2) [nil and](#1 #5) [nil and](!#4 #5)))
[2011-01-24 07:40:45:263] [DEBUG] Exemplar instance: [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00000000000000000000000000000000000000000000000000000000000000]
[2011-01-24 07:40:45:263] [DEBUG] Optimize deme
[2011-01-24 07:40:45:263] [DEBUG] Maximum evaluations during that expansion: 77980
[2011-01-24 07:41:22:844] [DEBUG] Close deme
[2011-01-24 07:41:22:845] [DEBUG] Actual number of evaluations during that expansion: 26950
[2011-01-24 07:41:22:845] [DEBUG] Sort the deme
[2011-01-24 07:41:22:935] [DEBUG] Compute the behavioral score of all candidates to merge
[2011-01-24 07:41:58:574] [DEBUG] Merge 19433 candidates with the metapopulation
[2011-01-24 07:42:05:727] [DEBUG] Metapopulation size is 3839
[2011-01-24 07:42:06:359] [INFO] Total number of evaluations so far: 48970
[2011-01-24 07:42:06:362] [INFO] The following candidate(s) have the best score -11
[2011-01-24 07:42:06:362] [INFO] or(and(or(and(or(!#3 #4) !#2) and(!#1 #5)) or(!#1 #5)) and(#1 #2 !#5) and(!#3 #4)) 
[2011-01-24 07:42:06:362] [INFO] or(and(or(!#1 #5) or(!#3 #4) !#2) and(!#1 #5) and(#1 #2 !#5) and(!#3 #4)) 
[2011-01-24 07:42:06:362] [INFO] or(and(or(and(!#1 #5) !#2) or(!#1 #5) or(!#3 #4)) and(#1 #2 !#5) and(!#3 #4)) 
[2011-01-24 07:42:06:362] [INFO] or(and(or(and(or(!#3 #4) !#2) and(!#1 #5) and(#2 #3)) or(!#1 #5)) and(or(#2 !#3) #4)) 
[2011-01-24 07:42:06:362] [INFO] Deme expansion: 6
...

That way you can follow in real time what MOSES is doing. You can also control the level of logging with option -l (see MOSES' help for more details).

After waiting a while, you should eventually get the solutions:

-9 or(and(or(and(or(and(!#1 #5) !#3 #4) !#2) and(or(!#3 #4) !#1 #5)) or(!#1 #5)) and(or(!#3 #4) #1 #2 !#5) and(!#3 #4)) 
-9 or(and(or(and(or(and(!#1 #5) !#3 #4) !#2) and(or(!#2 !#3 #4) !#1 #5)) or(!#1 #5)) and(or(!#3 #4) #1 #2 !#5) and(!#3 #4)) 
-9 or(and(or(and(or(and(!#1 #5) !#3 #4) !#2) and(or(!#3 #4) !#1 #2 #5)) or(!#1 #5)) and(or(!#3 #4) #1 #2 !#5) and(!#3 #4)) 
-9 or(and(or(and(or(and(!#1 #5) !#3 #4) !#2) and(or(!#3 #4) !#1 #5)) or(!#1 #2 #5)) and(or(!#3 #4) #1 #2 !#5) and(!#3 #4)) 
-9 or(and(or(and(or(and(!#1 #5) !#3) !#2) and(or(!#3 #4) !#1 #5) and(!#2 #4)) or(!#1 #5)) and(or(!#3 #4) #1 #2 !#5) and(!#3 #4)) 
-9 or(and(or(and(or(and(!#3 #4) !#2) or(!#3 #4)) and(or(!#2 !#3 #4) !#1 #5)) or(!#1 #5)) and(or(!#3 #4) #1 #2 !#5) and(!#3 #4)) 
-9 or(and(or(and(or(and(or(!#1 #2 !#3) #5) !#3 #4) !#2) and(or(!#3 #4) !#1 #5)) or(!#1 #5)) and(or(!#3 #4) #1 #2 !#5) and(!#3 #4)) 
-9 or(and(or(and(or(and(or(!#2 #3) !#1 #5) !#3 #4) !#2) and(or(!#3 #4) !#1 #5)) or(!#1 #5)) and(or(!#3 #4) #1 #2 !#5) and(!#3 #4)) 
-9 or(and(or(and(or(and(or(#3 #4) !#1 #5) !#3 #4) !#2) and(or(!#3 #4) !#1 #5)) or(!#1 #5)) and(or(!#3 #4) #1 #2 !#5) and(!#3 #4)) 
-9 or(and(or(and(or(and(!#1 #5) !#3) !#2) and(or(!#2 !#3 #4) !#1 #5) and(!#2 #4)) or(!#1 #5)) and(or(!#3 #4) #1 #2 !#5) and(!#3 #4)) 

It's better but we're still far from the optimal solution and seeing the trend we're going to need much more computational power to crack it. That is where Distributed MOSES comes handy.

Multi-threaded MOSES

To use it you simply need to invoke moses with option --jobs or -j with the number of processes. The following

moses -Hpa -k5 -j4 -m1000000

runs MOSES on the previous problem using 4 threads on your local machine with a million evaluations in total.

It's gonna take a while, if you own a 4-core machine with hyper-threading you may even replace -j4 by -j8. In the meantime let's have a look at the log

tail -f moses.log
[2011-01-24 09:28:30:518] [INFO] Launch command: moses --problem "pa" --problem-size "5" -e "or(and(or(and(or(!#1 !#3 !#4) #5) !#2 !#3) or(and(#1 #3) #4)) and(or(!#2 #5) !#1 !#3) and(or(!#3 #4) #1 #2 !#5) and(!#2 #5)) " -t 1 -x 1 -V 1 -m 823214 -g 1 -L -c -1 > /tmp/moses8sZKFi&
[2011-01-24 09:28:30:518] [INFO] corresponding to PID = 20603
[2011-01-24 09:28:58:606] [INFO] Parsing results from PID 20603
[2011-01-24 09:28:58:657] [INFO] Merge 282 candidates with the metapopulation
[2011-01-24 09:28:58:659] [INFO] The following candidate(s) have the best score -8
[2011-01-24 09:28:58:659] [INFO] or(and(or(and(or(!#1 !#3 !#4) or(!#2 #5)) !#3) or(and(#1 #3) #4)) and(or(!#2 #5) !#1 !#3) and(or(!#3 #4) #1 #2 !#5) and(!#2 #5)) 
[2011-01-24 09:28:59:087] [INFO] Metapopulation size is 7996
[2011-01-24 09:29:00:121] [INFO] Generation: 21
[2011-01-24 09:29:00:121] [INFO] Launch command: moses --problem "pa" --problem-size "5" -e "or(and(or(and(or(!#1 !#3 !#4) or(!#2 #5)) and(!#2 #5) !#3) or(and(#1 #3) #4)) and(or(!#2 #5) !#1 !#3) and(or(!#3 #4) #1 #2 !#5) and(!#2 #5)) " -t 1 -x 1 -V 1 -m 802777 -g 1 -L -c -1 > /tmp/mosestVHdQT&
[2011-01-24 09:29:00:121] [INFO] corresponding to PID = 20626

as you can see (looking at the log after a minute of computation) we have already outperformed our previous best score with -8.

If your machine doesn't have a lot of memory (say less than 4GB of RAM) it may be seriously slowed down as the cache adaptively shrinks to avoid pathological swapping.

After a while you get the following results (or similar).

-5 or(and(or(and(or(and(!#2 #3) #5) or(!#1 !#3 !#4)) and(or(#1 #2) !#3) and(!#2 #5)) or(and(or(#2 !#5) #4) and(#1 #3))) and(or(!#2 #5) or(!#4 #5) !#1 !#3) and(or(!#3 #4) #1 #2 !#5) and(!#2 !#4 #5))                                                                            
-5 or(and(or(and(or(!#1 !#3 !#4) or(!#2 #5)) and(!#2 #5) !#3) or(and(or(#1 #3) or(#2 !#5) #4) and(#1 #3) and(#2 #4))) and(or(!#2 #5) or(!#4 #5) !#1 !#3) and(or(!#3 #4) #1 #2 !#5) and(!#2 !#4 #5))                                                                            
-5 or(and(or(and(or(!#1 !#3 !#4) or(!#2 #5) or(#3 #5)) and(or(#1 #2) !#3) and(!#2 #5)) or(and(or(#2 !#5) #4) and(#1 #3))) and(or(!#2 #5) or(!#4 #5) !#1 !#3) and(or(!#3 #4) #1 #2 !#5) and(!#2 !#4 #5))                                                                            
-6 or(and(or(and(or(!#1 !#3 !#4) or(!#2 #5)) and(!#2 #5) !#3) or(and(or(#1 #3) or(#2 !#5) #4) and(#1 #3))) and(or(!#2 #5) !#1 !#3 !#4) and(or(!#3 #4) #1 #2 !#5) and (!#2 !#4 #5))                                                                            
-6 or(and(or(and(or(!#1 !#3 !#4) or(!#2 #5)) and(!#2 #5) !#3) or(and(or(#1 #3) or(#2 !#5) #4) and(#1 #3))) and(or(!#3 #4) #1 #2 !#5) and(or(!#4 #5) !#1 !#2 !#3) and (!#2 !#4 #5))                                                                            
-6 or(and(or(and(or(and(or(#1 #3) #2) !#5) #4) and(#1 #3)) or(and(or(!#1 !#3 !#4) or(!#2 #5)) and(!#2 #5) !#3)) and(or(!#2 #5) !#1 !#3 !#4) and(or(!#3 #4) #1 #2 !#5) and(!#2 !#4 #5))                                                                            
-6 or(and(or(and(or(and(or(#1 #3) #2) !#5) #4) and(#1 #3)) or(and(or(!#1 !#3 !#4) or(!#2 #5)) and(!#2 #5) !#3)) and(or(!#3 #4) #1 #2 !#5) and(or(!#4 #5) !#1 !#2 !#3) and(!#2 !#4 #5))                                                                            
-6 or(and(or(and(or(and(or(#1 #3) #2) !#5) #4) and(#1 #3)) or(and(or(!#1 !#3 !#4) or(!#2 #5)) and(!#2 #5) !#3)) and(or(!#2 #5) or(!#4 !#5) !#1 !#3) and(or(!#3 #4) #1 #2 !#5) and(!#2 !#4 #5))                                                                            
-6 or(and(or(and(or(and(!#1 !#4) !#2 #5) or(!#1 !#3 !#4)) and(!#2 #5) !#3) or(and(or(#1 #2) #3) and(or(#2 !#5) #4))) and(or(!#2 #5) or(!#4 #5) !#1 !#3) and(or(!#3 #4) #1 #2 !#5) and(!#2 !#4 #5))                                                                            
-6 or(and(or(and(or(and(!#1 !#4) !#2 #5) or(!#1 !#3 !#4)) and(!#2 #5) !#3) or(and(or(#1 !#5) #3) and(or(#2 !#5) #4))) and(or(!#2 #5) or(!#4 #5) !#1 !#3) and(or(!#3 #4) #1 #2 !#5) and(!#2 !#4 #5))                                                                            

This took 8mn on a Intel Core 2 Quad processor running at 2.5GHz. On an 8-core Xeon with hyper-threading and lots of RAM this problem can be solved in just a couple of minutes.

Distributed MOSES

MOSES can be distributed onto an MPI cluster, using the --enable-MPI option. Other MPI configuration is handled using standard MPI management techniques.

Open Network Distributed MOSES

Moses can also be distributed over the open network (without MPI), by using SSH. Suppose you have a local network of 3 machines, a 4-core machine, 2-core machine and a 1-core laptop.

We are gonna run moses from the laptop and use the other machines remotely.

Let's assume that '4core' and '2core' correspond respectively to the IPs of the remote machines.

Now before we run the example above you must meet the following requirements:

  1. You need to have MOSES installed on each machine, with moses in your PATH (this should be automatic if you install OpenCog).
  2. Your public ssh key must be registered on remote machines (see http://www.hackinglinuxexposed.com/articles/20021226.html for a detailed explanation on that).
  3. You need to have shh-agent (or a similar program) running on your laptop (most Linux distribution have one installed and running by default).
  4. Your network must be totally reliable, if a connection goes down while MOSES is running, it will crash or run forever. This will eventually be fixed but for now that is a requirement. So, running over the internet or wireless isn't recommended for big problems.
  5. It will only work on Linux or Mac OS X, not Windows. This will eventually be fixed too.

So now that you are ready type the following command to run Distributed MOSES on the same problem as above with a million evaluations

moses -Hpa -k5 -m1000000 -j4:4core -j2:2core

Easy, isn't it!

The reason the laptop has not been mentioned in the command-line is because it has only 1 core that will be entirely dedicated to gather and merge the results of the server and the desktop, if your laptop have more cores, say 6 you could run the following

moses -Hpa -k5 -m1000000 -j6 -j4:4core -j2:2core

Now the laptop can use its 6 cores are allocated to merge the results. Obviously -j6 is just shorthand for -j6:localhost.

Note that in this example we have assumed that you have an account with same user ID on the laptop, server and desktop. If you don't just need follow the conventional syntax

moses -Hpa -k5 -m1000000 -j6 -j4:asticus@4core -j2:aquarius@2core

where your user IDs on the 4-core and 2-core machines are 'asticus' and 'aquarius', respectively.

The main bottleneck is usually merging, this can be substantially sped-up if the server is running on a multi-core machine so don't forget to specify the number of threads the server can use.

Last remark

As you may anticipate if you distribute the computation over too many machines then the server in charge of merging the results may not perform fast enough and will constitute a bottleneck. The merging operation has been heavily optimized so this might not be an issue unless there's a lot machines, if so we'd need to distribute the merging as well in hierarchical manner, a la MapReduce.