Sunday, January 22, 2017

New version of IQSolver

This post describes state of work about new version of IQSolver. It is indended to become an artificial programmer's assistant - a tool which would help programmer create small programs based on sample input and output. Currently it accepts a sentence, finds a rule behind it and generates a JavaScript program.

A program was given 5 input sequences. As a result it generated the following web page. Each section contains the original input repeated and a small JavaScript code which allows to see further elements of the sequence.
Here is a short explanation of the sequences:

  1. Difference between elements is increasing
  2. Quotient of elements is -0.5
  3. Sequence of sequences. After a rule was found for one subsequence - it is tried against other subsequences to find analogy. The intermediate steps is a sequence of analogical formulas. Finally a master formula is found.
  4. Simliar to 3 but the formulas of internal sequences are more complicated
  5. AI tries to transform strings to sequence of characters which are then translated into numbers taking position in alphabet of each letter. A reverse transformation is made when displaying the results. 

Generated code

Let's take a look at the body of this page. For each consecutive inputs AI generates function starting with name "riddle" which outputs sequence given its length. The code uses some human-programmed functions (for example those starting with seqOf...) stored in a separate .js file. Its content may be seen here.

[1, 2, 4, 7]


    /**
    * Returns extension of sequence [1, 2, 4, 7]
    * @param listSize Size of generated sequence
    */
    function riddle1 (listSize) {
      var tmp1 = function(i,tab) {
        return tab[i-1]+tab[i-1]-tab[i-2]+1;
      };
      
      return listGen(
        listSize,tmp1,
        [1, 2]) /* [1, 2, 4, 7] */;
    }
  

[16, -8, 4, -2]

    /**
    * Returns extension of sequence [16, -8, 4, -2]
    * @param listSize Size of generated sequence
    */
    function riddle2 (listSize) {
      return listGen(
        listSize,
        function(i,tab) {
          return tab[i-1]*-0.5;
        },[16]) /* [16, -8, 4, -2] */;
    }
  

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

    /**
    * Returns extension of sequence [[1, 2, 3], [1, 3, 5], [1, 4, 7]]
    * @param listSize Size of generated sequence
    */
    function riddle3 (listSize) {
      var tmp1 = listGen(
        listSize,
        function() {
          return 1;
        }) /* [1, 1, 1, 1] */;
      
      var tmp2 = listGen(
        listSize,
        function(i,tab) {
          return tab[i-1]+1;
        },[2]) /* [2, 3, 4, 5] */;
      
      var tmp3 = listGen(
        listSize,
        function(i,tab) {
          return tab[i-1]+2;
        },[3]) /* [3, 5, 7, 9] */;
      
      return seqOfStruct(tmp1,tmp2,tmp3) /* [[1, 2, 3], [1, 3, 5], [1, 4, 7], [1, 5, 9]] */;
    }

[[1], [3, 6], [5, 10, 20]]

    /**
    * Returns extension of sequence [[1], [3, 6], [5, 10, 20]]
    * @param listSize Size of generated sequence
    */
    function riddle4 (listSize) {
      var tmp3 = listGen(
        listSize,
        function() {
          return listGen;
        }) /* [LIST_GEN, LIST_GEN, LIST_GEN, LIST_GEN] */;
      
      var tmp4 = listGen(
        listSize,
        function(i,tab) {
          return tab[i-1]+1;
        },[1]) /* [1, 2, 3, 4] */;
      
      var tmp1 = function() {
        return function(i,tab) {
          return tab[i-1]*2;
        };
      };
      
      var tmp5 = listGen(
        listSize,tmp1) /* [{a[n-1]*2}, {a[n-1]*2}, {a[n-1]*2}, {a[n-1]*2}] */;
      
      var tmp2 = listGen(
        listSize,
        function(i,tab) {
          return tab[i-1]+2;
        },[1]) /* [1, 3, 5, 7] */;
      
      return evalSeqOfCall(tmp3,tmp4,tmp5,
        seqOfStruct(tmp2) /* [[1], [3], [5], [7]] */) /* [[1], [3, 6], [5, 10, 20], [7, 14, 28, 56]] */;
    }

[B, D, F]

    /**
    * Returns extension of sequence [B, D, F]
    * @param listSize Size of generated sequence
    */
    function riddle5 (listSize) {
      var tmp1 = function(i,tab) {
        return numberToBigLetter(
          bigLetterToNumber(
            tab[i-1])+2);
      };
      
      return listGen(
        listSize,tmp1,
        ['B']) /* [B, D, F, H] */;
    }
  

Used functions

The above code is fully generated but it uses some human-programmed functions stored in a separate .js file. Its content may be seen here.

Sunday, September 20, 2015

Comparison with other solvers

I have recently came across an AGI conference 2015 paper [Schmid2015] comparing various programs solving number series problems. A detailed investigation was held on IGOR2 program and Artificial Neural Networks (ANN) approach. As series of 20 numerical tests were conducted. I reran these tests on IQSolver and it scored better (twice less failures).


Test details

IGOR2 was given 5 elements in series as input - it succeeded in 14 series and failed in 6. When IQSolver was also given 5 elements - it succeeded in 17 and failed in 3. By failure I consider giving different results than seems most natural for humans.
According to [Schmid2015] ANN was given 7 elements and had to predict the 8th. However, some series have only 7 elements. I assumed that in such case 6 elements were given as input. I performed the same test on IQSolver. The result for ANN was 3 failures, whereas IQSolver failed in just 1 case. Unlike IGOR2 and ANN, IQSolver was not adjusted in any way to this test - I used version available online from August 2015.

Here is the table of results copied from [Schmid2015]
Columns labeled "Human" contains results of internet test: each cell contains number of correct/incorrect/no answer

Here are the results for IQSolver. It does not produce formula but if you click on each series you will see a generated explanation along with continuation of the series. For the full series - last number is not send to IQSolver. You may first read description of how IQSolver works. I have not yet written formal, mathematical description. Do you think it would be useful?
ID   5 elements series  Correct?  Full elements series       Correct?
052,5,8,11,14+2,5,8,11,14,17,20,23+
0725,22,19,16,13+25,22,19,16,13,10,7,4+
198,12,16,20,24+8,12,16,20,24,28,32,36+
1354,48,42,36,30+54,48,42,36,30,24,18+
0828,33,31,36,34+28,33,31,36,34,39,37+
146,8,5,7,4+6,8,5,7,4,6,3,5+
209,20,6,17,3+9,20,6,17,3,14,0,11+
0112,15,8,11,4+12,15,8,11,4,7,0,3+
114,11,15,26,41+4,11,15,26,41,67,108+
093,6,12,24,48+3,6,12,24,48,96,192+
167,10,9,12,11+7,10,9,12,11,14,13,16+
188,12,10,16,12+8,12,10,16,12,20,14,24+
156,9,18,21,42-6,9,18,21,42,45,90,93-
178,10,14,18,26-8,10,14,18,26,34,50,66+
103,7,15,31,63+3,7,15,31,63,127,255+
042,3,5,9,17+2,3,5,9,17,33,65,129+
032,12,21,29,36+2,12,21,29,36,42,47,51+
02148,84,52,36,28+148,84,52,36,28,24,22+
062,5,9,19,37+2,5,9,19,37,75,149,299+
125,6,7,8,10-5,6,7,8,10,11,14,15+

Discussion about wrong results

S15 - 6,9,18,21,42,45,90,93

The correct formula is if (even; f(n-1) + 3; f(n-1) * 2), which means you should alternately increase the previous number by 3 and multiply by 2. If all 8 numbers are given then IQSolver finds the correct answer (the generated numbers match the rule) although it explains it in a more complicated way (deduced numbers are in italic):


Solution #1
[6, 9, 18, 21, 42, 45, 90, 93, 186, 189, 378, 381, 762, 765, 1530, 1533]
Explanation #1
[6, 9, 18, 21, 42, 45, 90, 93, 186, 189, 378, 381, 762, 765, 1530, 1533] may be divided into 2 sequences: 
         [6, 18, 42, 90, 186, 378, 762, 1530]; [9, 21, 45, 93, 189, 381, 765, 1533]
  Apply "-" on consecutive elements in [6, 18, 42, 90, 186, 378, 762, 1530] to get [12, 24, 48, 96, 192, 384, 768]
    Apply "/" on consecutive elements in [12, 24, 48, 96, 192, 384, 768] to get 2
  Apply "-" on consecutive elements in [9, 21, 45, 93, 189, 381, 765, 1533] to get [12, 24, 48, 96, 192, 384, 768]
    Apply "/" on consecutive elements in [12, 24, 48, 96, 192, 384, 768] to get 2
Complexity #1
5.5

It divides the series into 2 subseries. First subseries  6, 18, 42, 90  follows the formula (f(n-1)+3)*2 = 2*f(n-1) + 6. The second 9, 21, 45, 93 is just (f(n-1)*2)+3 = 2*f(n-1)+3 . These 2 linear functions are easily discovered. However, IQSolver treats both subseries independently and does not check that they have the same transformation and thus the complexity should be smaller.
Moreover, if one less input number is given - it does not find enough justification to assume 12, 24 is a series with constant quotient. To assume a certain arithmetic operation between consecutive elements always return constant value at least two values must be returned. That is why 12, 24, 48  is enough to induce the rule.

Therefore, for 7 input numbers  another answer is returned:

Solution #1
[6, 9, 18, 21, 42, 45, 90, 81, 174, 117, 318, 117, 582, -15, 1122]
Explanation #1
Apply "-" on consecutive elements in [6, 9, 18, 21, 42, 45, 90, 81, 174, 117, 318, 117, 582, -15, 1122] to get [3, 9, 3, 21, 3, 45, -9, 93, -57, 201, -201, 465, -597, 1137]
  Apply "-" on consecutive elements in [3, 9, 3, 21, 3, 45, -9, 93, -57, 201, -201, 465, -597, 1137] to get [6, -6, 18, -18, 42, -54, 102, -150, 258, -402, 666, -1062, 1734]
    Apply "-" on consecutive elements in [6, -6, 18, -18, 42, -54, 102, -150, 258, -402, 666, -1062, 1734] to get [-12, 24, -36, 60, -96, 156, -252, 408, -660, 1068, -1728, 2796]
      Obtain element by applying "-" on previous 2 elements of [-12, 24, -36, 60, -96, 156, -252, 408, -660, 1068, -1728, 2796] 
Complexity #1
5.0
And for 5 input numbers the answer is different:




Solution #1
[6, 9, 18, 21, 42, 57, 102, 153, 258, 405, 666, 1065, 1734]
Explanation #1
Apply "-" on consecutive elements in [6, 9, 18, 21, 42, 57, 102, 153, 258, 405, 666, 1065, 1734] to get [3, 9, 3, 21, 15, 45, 51, 105, 147, 261, 399, 669]
  Apply "+" on consecutive elements in [3, 9, 3, 21, 15, 45, 51, 105, 147, 261, 399, 669] to get [12, 12, 24, 36, 60, 96, 156, 252, 408, 660, 1068]
    Obtain element by applying "+" on previous 2 elements of [12, 12, 24, 36, 60, 96, 156, 252, 408, 660, 1068] 
Complexity #1
6.0

S12 5,6,7,8,10,11,14,15

When given 7 number IQSolver finds the expected solution:
Apply "-" on consecutive elements in [5, 6, 7, 8, 10, 11, 14, 15, 19, 20, 25, 26, 32, 33, 40] to get [1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7]
  [1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7] may be divided into 2 sequences: 
         [1, 1, 1, 1, 1, 1, 1]; [1, 2, 3, 4, 5, 6, 7]
    [1, 1, 1, 1, 1, 1, 1] consists only of : 1
    Apply "-" on consecutive elements in [1, 2, 3, 4, 5, 6, 7] to get 1

It generalizes sequence of difference 1, 1, 1, 2, 1, 3 into 1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 6, 1, 7.
But when only five numbers are given - sequence of differences is 1, 1, 1, 2 - there are too few repetitions to generalize. IQSolver does not generalize 1, 2 to 1,2,3,4 (althought it does for 1,2,3), maybe this should be corrected. Anyway, the solution actually found is pretty strange for humans.

Apply "-" on consecutive elements in [5, 6, 7, 8, 10, 16, 46, 286, 3406, 68926, 2296606, 124819006, 11029312606] to get [1, 1, 1, 2, 6, 30, 240, 3120, 65520, 2227680, 122522400, 10904493600]
  Apply "/" on consecutive elements in [1, 1, 1, 2, 6, 30, 240, 3120, 65520, 2227680, 122522400, 10904493600] to get [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
    Obtain element by applying "+" on previous 2 elements of [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89] 

S17 8,10,14,18,26,34,50,66

Again, IQSolver finds results for 7 input numbers:


Apply "-" on consecutive elements in [8, 10, 14, 18, 26, 34, 50, 66, 98, 130, 194, 258, 386, 514, 770] to get [2, 4, 4, 8, 8, 16, 16, 32, 32, 64, 64, 128, 128, 256]
  Apply "/" on consecutive elements in [2, 4, 4, 8, 8, 16, 16, 32, 32, 64, 64, 128, 128, 256] to get [2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
    [2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2] is repeated sequence of : [2, 1]

But for 5 input numbers it cannot  generalize sequence of differences 2, 4, 4, 8 into 2, 4, 4, 8, 8, 16, 16, 32, 32. It is too short. The answer is "inhuman" again.

Apply "-" on consecutive elements in [8, 10, 14, 18, 26, 30, 46, 48, 112, 1.1e+02, 2.2e+03, 2.2e+03, 1.7e+07] to get [2, 4, 4, 8, 4, 16, 2, 64, 0.25, 2048, 0.00098, 16777216]
  Apply "/" on consecutive elements in [2, 4, 4, 8, 4, 16, 2, 64, 0.25, 2048, 0.00098, 16777216] to get [2, 1, 2, 0.50, 4, 0.13, 32, 0.0039, 8192, 4.8e-07, 17179869184]
    Obtain element by applying "/" on previous 2 elements of [2, 1, 2, 0.50, 4, 0.13, 32, 0.0039, 8192, 4.8e-07, 17179869184] 

Other solvers

[Schmid 2015] mentioned other programs capable of solving IQ tests . Most notable examples are SeqSolver [Strannegard 2013] and ASolver  [Strannegard 2012], which score IQ tests above 140. I do not have an executable version of these programs to test them, but from their description I infer they have less abilities than IQSolver. However, their cognitive abilities are deliberately bounded to meet human constraints. 

Future development

Some improvements could be done to make IQSolver score better in IQ tests. However, solving tests is just the first step on this roadmap. The next milestones are learning rules of board games and text computer games. But, in order to make an AI capable of finding rules in complex but limited set of data a new program must be created. Therefore, I plan to build a completely new AI. Some design plans of it are given here and here.

References

[Schmid 2015] "Comparing Computer Models Solving Number Series Problems" by Ute Schmid and Marco Ragni. 8th International Conference, AGI 2015
http://agi-conf.org/2015/wp-content/uploads/2015/07/agi15_schmid.pdf

[Strannegard 2013] "Bounded Kolmogorov Complexity Based on Cognitive Models" Claes Strannegård, Abdul Rahim Nizamani, Anders Sjöberg, and Fredrik Engström
http://gup.ub.gu.se/records/fulltext/178586/178586.pdf

[Strannegard 2012] "An anthropomorphic method for number sequence problems" Claes Strannegård · Mehrdad Amirghasemi · Simon Ulfsbäcker http://engstrom.morot.org/material/bounded_kolmogorov.pdf

Wednesday, September 16, 2015

Potential applications

After this AI for performing induction in a human-like style is created, it could be used in many application, which require now man's work.  However, it must be remembered, that unless integrated with some knowledge base, this AI would only have knowledge it would gain from the input data. This is not a problems when learning games, because to play them you don't generally need to have knowledge about the outside worlds. There are notable examples: such as Charades or Dixit, and it is sometimes easier to understand the game if you have some knowledge about the domain it refers to (for example Agricola is much less intuitive when you have no idea about farming). But generally games are worlds in their own.
So if you want to know what this AI could do - think about classic Chinese room analory and imagine you learn how to process documents in Chinese (assuming you don't know 中文) about unknown domain and you cannot ask anyone what these symbols matter. Your abilities are limiter, but there are some tasks that may be performed:
  1. Transformation Builder. Building transformation between data presented in different formats. This is a really common work for data integration projects. After being given a few examples AI should catch the rule. In case of doubtful cases it could ask, which option is right, and update the rules according to answers. 
  2. Retrieving info from documents. In Gmail when you receive invoice or air ticket it retrieves basic info from it. This could be also done with future version of IQSolver - teach it by presenting it with an email or web page and data you retrieved from it.
  3. Deef Asssistant. Learning patterns in human activities so that it is learns to perform repeated activities. But remember: you don't know the language of the person you are assisting and what he is working on.
  4. Anomalies detector. As AI would learn various patterns in data - it could check if in the new portion of data some rules stopped being true. This could be used for bug detection.
I believe there are many others potential applications. If you think of some, please write them in comments.

Monday, September 14, 2015

Generating knowledge



This post is about how to make an AI, which is able to generate knowledge for OpenCog, NARS, SOAR or other AGI engine. If human is given some unknown data to analyse, he/she will find some regularities. If the data is asequence of states in some game, and sufficient time is given, human would induce its rule. If a human is given a few examples about transforming one complex data structure into another he/she will find the rule. All these tasks should be possible in IQSolver.

IQSolver will generate knowledge in the form of equations involving mathematical operators, relations (<, >=, etc.), boolean operators and quantifiers. First order logic should be enough, although maybe I haven't found appropriate example that would falsify this conjecture :). The process of designing this inductive engine is also inductive: from invented examples I induce what is necessary, so feedback and counterexamples would be appreciated :)

TESTING CONJECTURES


IQSolver generates conjectures about data. Some of them are justified by 1 observation (entries), others by many. This is similar to truth value in PLN. For example in the task of filling the sequence 1,2 - the conjecture that difference between elements is 1 - is justified by one example. And there are other conjectures, for example that the quotient is 2. On the other hand, in the sequence 1,2,3,4,5,6 -the difference-1-conjecture is justified by 5 observation, and all others are falsified. 

Some of conjectures are true for all objects they may be evaluated on. They are the most valuable, as they allow to predict or verify unknown values. However, when a conjecture is true only for some elements - it is not automatically rejected but a detailed search is done. For example when analyzing chess movements AI may conclude that always one piece moves on a space that is empty or occupied by another side's piece (building a concept of side and assigning piece symbols to it is another issue). However, this conjecture does not hold for castling, promotion or en passant. Thus, AI should make detailed analyses in this cases but do not reject the general rule. 

So what should be done if q is not always true? Maybe for conjecture q there is another conjecture p so that always p => q ? If so, a new complex conjecture will be created stating that p => q. But this conjecture is not full as it implies nothing if p is false. Perhaps there is another conjecture r such that ~p => r. Then a new conjecture would be p=>q AND ~p=>r

An implications set may be created. For example, if you analyse movements of chess pieces then you cannot make one rule for all. But it is possible to enumerate rules for each piece:
IF piece_kind == "rook" THEN x1 == x2 or y1 == y2
AND IF piece_kind == "bishop" THEN x1-y1 == x2-y2 or x1+y1==x2-y2
AND IF piece_kind == "knight" etc
Sure, simple conjecture with less elements carring the same information is better. But, if simple conjecture cannot be found, then it is valuable to have complex conjecture consisting of many implications so that always one and only one premise is true.

CONJECTURE FEATURES

To summerise, for conjecture the following numbers are held:
  1. For how many observations (elements in series) it was tested on
  2. How many times it could be evaluated (for example you cannot evaluate link prev on the first element as it has no previous element, you cannot evaluate piece_kind=="rook" if there is no piece_kind field on an object)
  3. How many times it was true
  4. If a conjecture is in a form of implication or series of implication - how many times any premise was true
  5. If conjecture is a series of implication - how many times many premises was true. This indicator is rather negative because it means the classification is not disjunctive


GENERATING SIMPLE CONJECTURES

Just to summarize what I wrote in the previous post. Simple conjectures are generated in the process of iterating over elements in series. For each element a number of formulas involving this, related elements and sub-elements are generated. Formulas above some complexity level are not generated. Formulas useful earlier has much reduced complexity.
If value of formula equals value of another formula evaluated for this and other elements then a new simple equality conjecture is created. If value of formula evaluated for consecutive element equals some earlier experienced sequence - a conjecture is also generated

COVERING CONJECTURES

Some conjectures may be always more informative than the others. For example p <=> q holds more information than p => q. However, conjecture p <=> q is created when p => q and p <= q are found. Base p=>q and p <= q conjectures are then covered. They won't be used in generating knowledge to external system nor shown as conclusion to the user. However, it may happen when analyzing more data (as will be shown later in the example) that p<=>q is true for less number of cases then p => q and then both of them are shown. The former is better because it is more informative, the latter is more often true.

__EXAMPLE__

CONSTANT SPEED

Take this sequence of 5 maps given by this table (for example the first element is a map [t:0, x:1, f:5] )
t  x  f
0  1  5
2  5  5
3  7  5
3.5  8  5
5  11  5

Many conjectures will be generated, among them:
x = t*2+1
f = 5
f = prev.f
but also
d(x) / d(t) = 2 
d(x) / d(t) = d(prev.x) / d(prev.t) 

where d(x) is an operator meaning x - prev.x (defining it as x-next.x as in the previous post would ultimately lead to the same results, but would be less intuitive. I also resigned from marking links by -> operator)

As you may have guessed - this is sampling of constant-velocity movement of an object. t is time, x is position,  d(x) / d(t) is speed.

CHANGING SPEED

Now new data become available:

t  x  f
6  12  4
7  12  3
9  10  2
10  9  2
11  8  2

Conjectures x = t*2+1 and d(x) / d(t) = 2  are false for new data. So a new conjecture will be generated  x = t*2+1 <=> d(x) / d(t) = 2 ,which is true for all elements

Conjectures f = prev.f and d(x) / d(t) = d(prev.x) / d(prev.t)  are both false for the first 3 of new records but true for the last 2. So a new conjecture is created
f = prev.f <=> d(x) / d(t) = d(prev.x) / d(prev.t)
As you may guess f stands for fuel, which is used when speed is changed. For us it sounds sensible - to change velocity in the outer space a space ship needs fuel. IQSolver would not interpret it but would find these rules and send them to knowledge engine.

REFUELING

Views about the worlds change with experience and the same happens to IQSolver. The next portion of data is 

t  x  f
16  3  2
19  0  2
20  0  1
21  0  2
30  0  11

In the last 2 entries
d(x) / d(t) = d(prev.x) / d(prev.t) but not f = prev.f 

So the equivalence
f = prev.f <=> d(x) / d(t) = d(prev.x) / d(prev.t)
is not longer true. However the previously covered conjecture now emerges to the surfuce 
f = prev.f  => d(x) / d(t) = d(prev.x) / d(prev.t)

But AI want's to find equivalence rules. So it tries to find the rule for elements for which  not (f = prev.f) and d(x) / d(t) = d(prev.x) / d(prev.t). This requires work of another submodule capable finding a conjecture which is true for some elements and false for the others. It is similar to classification problem. After the search a conjectures x==0 and d(f)=1 are generated.

The rule f = prev.f or x==0 <=> d(x) / d(t) = d(prev.x) / d(prev.t)
is not always true (for example for the third entry [t:20, x:0, f:1]), however
f = prev.f or x==0 <= d(x) / d(t) = d(prev.x) / d(prev.t)



is always true and material equivalence is true
f = prev.f or d(f) = 1 <=> d(x) / d(t) = d(prev.x) / d(prev.t)

SUMMARY 

In this post I have presented in details how very grounded and low level knowledge may be generated on data AI can make no assumptions about. Therefore, I think that such module would be useful for many other AI systems. 

Sunday, September 6, 2015

Design of the new solver

The inductive reasoning system described below is supposed to performed some functions of MOSES or CGC while being able to perform tasks these systems cannot do.
I doesn't use neural networks, genetic algorithms nor hill-climbing. It is meant to simulate the way humans induce rules.
It should universally find rules in input complex data. It is supposed to at least find any rules an average adult human would find. Therefore it should not make any limiting assumption (for example that order of elements in map matter or that it doesn't matter). It should be able to analyse data of different kinds: JSON structures, databases, DOM tree of HTML page, therefore wrappers need to be created which would return for each elements its value, components and connected elements.

I will present how it may be used to solve IQ test task and predict movement of objects. Enhancements required for learning board game and virtual worlds will be described later.

__HUMAN THINKING__

Suppose you are given this IQ test:

Example #1

[1, [3, 3]] -> [10, 7]
[2, [3, 4, -4]] -> [12, 1]
[0, [2, 3, 1, 1]] -> [6, 5]
[2, [0, 5]] -> ???
How would you solve it? What would your mind's algorithm look like?

Take the first row:
[1, [3, 3]] -> [10, 7]
Are some numbers equal? Yes, [3,3]. So maybe the first 2 elements in the subsequence are always equal? Looking down into the next entry... no it is not. Analyse the subsequence in consecutive entries. Its length is 2, 3, 4, 2 - it looks like 2,3,4,2,3,4,2,3,4 sequence but it may be coincidence. We don't know if position of entries matter - is it a sequence or set. Lets calculate other aggregate function on the subsequence - for example sum ;
[3,3] -> 9  
[3, 4, -4] -> 3
[2, 3, 1, 1] -> 7
Now compare these calculated values with the other, create expressions involving them. When comparing with the second element on the right side you may find out that :
sum([3, 3]) - 7 = 2 // [10, 7][1] == 7
sum([3, 4, -4])  - 1 = 2
sum([2, 3, 1, 1]) - 5 = 2

So
sum(key[1]) - value[1] = 2 
So
key[1] = sum(value[1]) - 2

Finally you would find that the rule is the following
[a, [b1, ..., bn]] -> [a+(b1*b2), b1+...+bn-2] 

The algorithm is described below.

__SERIES__

Induction is performed in series. Series is a sequence of elements, which are expected of being similar. AI finds the rules which apply to all or some regular subset of elements in series. Series analysis should cover all available data. Sub-series analysis will be also performed on sequences and maps which are contained in other elements.

Example of series are:
  1. Sequence of numbers in numeric IQ tests
  2. Sequence of pairs (state of board, next move) in a board game
  3. All elements on a particular board.
  4. Elements on the board in particular row, column, etc.
  5. Tables in database, rows of table and cells in row
Example #2 Table of records
t x y
1.0 2.0 4.0
1.5 3.0 5.5
3.0 6.0 10.0
4.5 9.0 14.5
This is data from movement of object without gravity with irregular time sampling (I left the numbers pretty regular to make reading the example easier)

Later we will analyse example #3 - movement of object with gravity and some wind (I assumed wind works like gravity but in different direction)
t x y
0.0 0.0 1.00
1.0 1.900 3.00
1.5 2.775 3.25
3.0 5.100 1.00
4.5 6.975 -5.75


__ELEMENT ANALYSIS__


CREATING ELEMENTS LIST


Each element in series is analysed. It is called master element. A list of nearby related elements is created. In details:
  1. For master element its components and components of components, etc. is returned.
  2. The same is made for elements related to the master elements.
  3. For each non-scalar element - experienced expressions (see Experience part below) are evaluated and if they are sensible in this context they are added to the list
  4. Interpretations are generated - to be explained another time. 
Complex elements and the master element itself is also located on the list. The generated list contains for each element
  1. a path leading to it from the master element (something like XPath language)
  2. complexity of the path (similar to Kolmogorov complexity)
  3. value of element
The size of list is limited: for each element analyses only n-least complex related elements are returned or elements up to given complexity limit.

Example #2

Analysed master element (the 1st row of input table) is the map: [x:1.0 y:2.0 z:4.0].  The list generated from it contains:
PATH  COMPLEXITY  VALUE
[this ,0,  [t:1.0 x:2.0 t:4.0] ] // the master element itself
[this.t, 1, 1.0] // operator "." is used to navigate to components
[.x, 1, 2.0] // "this" keyword is optional
[.y, 1, 4.0]
[this->next, 3, [t:1.5, x:3.0, y:5.5] ]// operator "->" is used to navigate to another element through a relation, thus "\next" is just the next row
[this->next.t, 4, 1.5]
[->next.x, 4, 3.0] 
[->next.y, 4, 5.5]

Example #1 

The first master element is
[1, [3, 3]] -> [10, 7]
so the list contains:
[this, 0, [1, [3, 3]] -> [10, 7]]
[.key, 1, [1, [3, 3]]] // "this" keyword is optional
[.value, 1, [10, 7]] 
[.key[0], 2, 1] 
[.key[1], 2,  [3, 3]] 
[.key[1][0], 3,  3]  
[.key[1][1], 3,  3] 
[.value[0], 2, 10] 
[.value[1], 2, 7] 


GENERATING EXPRESSIONS

Expression involving existing elements in list are generated and added to the list. Expression may be unary (not, sin), binary (a-b), tetrary (?). They may involve aggregate functions. Complexity of expression is generally sum of complexity of sub-expression plus complexity of the term (operator/function). It must be within certain limits to be added (such limit is necessary because for n basic elements c1*n + c2*n*n would be created where c1 is number of unary operators and c2 - number of binary operators) This process is repeated until all new expressions exceed complexity limit (perhaps limit should be greater for expression with more unique variables count)
Complexity reflects how non-obvious and non-symmetric is the expression for human mind. Wages should be configured or obtained through Experience (to be explained another time). The complexity cost rates in this example are the following:
  1. operator "." - 1 for each unique label of sub-element
  2. operator "->" - 3 for each unique label of next-element 1 for non-unique
  3. arithmetic operator - 1 for each

Example #1

(only the important elements are listed):
[sum(.key[1]), 2,  9]  // sum([3, 3])
[.value[1], 1,  7]
[sum(.key[1]) - .value[1], 4,  2]
The last expression evaluating on other master elements also return value 2

Example #2

Just some more elements. :
[t - ->next.t, 5, -0.5]
[x - ->next.x, 5, -1.0]
[(x - ->next.x)/(t- ->next.t), 8, 2.0]
We can see that the last element is speed on x as axis, but as for now AI doesn't know yet it is any special. Complexity 8 is pretty high but as there aren't many data - it should be reached. Perhaps there should be operator delta - delta(a) = a - ->next.a (or a - ->prev.a) with complexity 1 thus reducing complexity of the above term to 3 . Calculating difference with the analogical term in the next record is so common both in IQ tests and physics that it could be a bit privileged.

FINDING CONJECTURES

Now the conjectures are generated. The list is analysed: if two elements share the same value - their expression is taken to create identity conjecture. It states that for each master element in the series expressions #1 and #2 have the same value.

The newly filled list of elements is added to the multiset of values of all expressions evaluated during this series analyses. If they share the same value - a new identity conjecture is generated. The new conjecture is considered especially valuable if the expression is the same, just evaluated on the different master elements.

Example #2

Already generated expressions are evaluated for row#2:
[t - ->next.t, 5, -1.5]
[x - ->next.x, 5, -3.0]
[(x - ->next.x)/(t- ->next.t), 8, 2.0]

So in the multiset for key 2.0 there will be at least these 2 elements.
[row#1, (x - ->next.x)/(t- ->next.t), 8, 2.0]
[row#2, (x - ->next.x)/(t- ->next.t), 8, 2.0]
A new identity conjecture is created (x - ->next.x)/(t- ->next.t) == (->next.x - ->next->next.x)/(->next.t- ->next->next.t) It states that the speed in x direction is constant. Similar conjecture will by created for y

Example #1
Because sum(.key[1]) - .value[1] returns the same number for each master element - an equality conjecture for this and next master element is created.

TESTING CONJECTURES

Each conjecture is checked against other master elements. If it applies to all of them - it means that AI found a rule, great. If conjecture is only true for one master element and for other it is false- it is ignored. If it is true only for some - a detailed analyses is performed. Maybe it is true for each k master elements? Or is true always when another conjecture is true?


Example #1

Identity conjecture is true for entry#1 and entry#2. Evaluating on entry#3 leads to conclusion that in the last entry value[1] = 3
Perhaps another conjecture should be created stating that value of this expression is 2. If from the middle of the sequence value of sum(.key[1]) - .value[1] changed  to 3 then the first conjecture will be false only once while the second is false for half of records.

Example #2

The constant speed conjecture is true for the rows #1 and #2. For the other it cannot be evaluated.

EXPERIENCE

Gathering experience and applying conclusions from one task to another is a multi-aspect topic:
1. Initial complexity costs should be adjusted by how often particular part of expression was used in true conjecture.
2. Values of useful expression should be gathered in known sequences. If values of some new expression evaluated on consecutive master elements are found in some known sequence (for example Fibonacci sequence) - then a new conjecture is generated
3. If an expression is proved useful in one task then it is considered to have much less complexity when applying in another task

Example #3

Pretty complex expression  (x - ->next.x)/(t- ->next.t) was part of main conjecture in example #2. Therefore, during processing of master expression in example #3 for row #1, this expression is added with complexity 2 instead of original 8 to both elements this and this->next. Difference between them divided by time difference express acceleration.

__REMARKS__

1. Expressions are considered related if they are equal, but this should be generalized. One value may be sub-string of another. One may be a category for another or they may share the same category.
2. Language for expression should contain relations and for-all, there-exists quantifiers. Expressions like "sum all elements in sequence such there there exists value in another sequence greater than the given element" should be possible to write down. How is AI supposed to find such a rule is a different issue.

Monday, August 3, 2015

Why this approach?

In this post I want to explain the rationale behind the chosen approach.


Common sense

I believe that AGI should have so-called common sense. It's great that I can type in an automatic translator a phrase "I threw a rock through a window" and get accurate translation. However, I cannot ask a follow-up question: "what happened with the glass". Translator does not have internal representation of what a window is, that it contains glass and glass is fragile and cannot process this situation as any human with imagination can.
Another question "My neighbour claims he keeps whale in his house, should I believe him?". Answer to such question require quite a lot of common-sense knowledge about size, needs of ocean mammals and what house may contain. And the negative answer is not 100% certain. I could imagine that your neighbour may be a multi-millionaire and indeed has a huge enough pool in the house and always dreamed of having the biggest pet in the world.
As far as I know even semantic networks cannot cope with such a questions, but if you know of such implementation - please post a link to page where we can test such AI engine.

Virtual worlds

I think that it is much easier for AI to gain common-sense in virtual worlds of for example computer games. They are much simpler. Such a complex notion as human health is expressed there by one integer number. Death is decreasing this number to 0. Objects of one kind are identical. Plato with his search of ideal objects, not some shadows in the cave would be delighted.
If AGI was to learn in the real worlds - doing so in virtual ones should be much, much easier. So I propose a Balgor test: AI without being designed to any computer game (just some specification about the aim - increasing dungeon level and avoiding quitting game) should be able to go through Moria and kill Balrog. Moreover, it should collect internal rules of how the virtual world works. On the contrary, by machine learning you may breed an AI capable of playing Atari games or even Go, but you cannot ask it in any way for example how the other side should play.  These AI are like simple animals, which follow their insticts and act great in their environment. They won't become philosophers. A spider spins a complicated web, but it doesn't understand what is does and how it works. It won't analyse movement of insects and how to catch them.

AGI that undestands


There are even simpler tasks in the development path of such AGI that understands: 
  1. reasoning with full knowledge of the world instead of being given only input from senses
  2. board or card games which are even simpler as they require no computer to process environment behaviour.
  3. intelligence tests of various kinds 
In addition, I expect this AGI to learn fast, from a single example. If you want to build a Skynet :) it needs to learn from a single battle not thousands of them. Neural networks have vast area of application but they require so much repetition. Like this very interesting Chinese verbal IQ test solver, which learned from large corpus of words. It learned like a human from multiple repetitions, but would this approach be useful to decipher an ancient language from just a few found texts? Can a NN catch a rule from one numeric IQ test? Or does it require the same rule be repeated in 10 cases? Maybe it can, but I haven't found any paper nor example of such implementation

Wednesday, July 29, 2015

Deducing concepts


Suppose you need to find a rule and append new lines to the following array:







2 5 10 17 26 37 50
4 9 18 31 48 69 94
8 15 28 47 72 103 140
16 25 42 67 100 141 190

If you put the first row into iqsolver you will get an answer
Apply "-" on consecutive elements in [2, 5, 10, 17, 26, 37, 50] to get [3, 5, 7, 9, 11, 13]
  Apply "-" on consecutive elements in [3, 5, 7, 9, 11, 13] to get 2

The second row lead to a very similar solution:
Apply "-" on consecutive elements in [4, 9, 18, 31, 48, 69, 94] to get [5, 9, 13, 17, 21, 25]
  Apply "-" on consecutive elements in [5, 9, 13, 17, 21, 25] to get 4

The solutions differ however by parameters: the number which is the difference of the prime sequence is 2 in the first case and 4 in the second. There are also other hiden parameters: when creating a differential sequence from a given one - an information is lost about the value of the first element in the original sequence. I marked these transformation parameters in fuchsia for the original sequence and lime for the prime one. So if you extract them and put them along with the length of the original sequence you get all 4 parameters required to build the original sequence (just like you need parameters a and r to build an infinite geometric progression )

You may think about it as a procedure, which a programmer would create in order not to calculate these numbers herself:
[2,5,10,17,26,37,50] == double_minus_and_identity(2,2,3,7)
[4,9,18,31,48,69,94] == double_minus_and_identity(4,4,5,7)

But this double_minus_and_identity is a concept, which will be extracted by AI and applied to further sequences. Thus, a new table may be created with 4 columns - one for each parameters and number of rows matching number of original sequences:

2 2 3 7
4 4 5 7
6 8 7 7
8 16 9 7

When AI applies reasoning to the columns treating each as a separate series, it will not only conclude what are the parameters of next rows (10,32,11,7) and be able to add new row to the original arrays (32,43,64,95,136,187,248).

It will also be able to create a higher level concept. The concept (lets call it double_minus_and_identity_table) has 7 parameters (2 for each sequence in the first 3 columns and one for the last), however some of the parameters are equal. 1st and 3nd columns share the same difference (=2) which is quotient in the 2nd column. So maybe a 3-parameter (2, 3, 7) concept should be created? When you see a square (1-parameter) it may be treated as well as quadrilateral for which 4 lenghts and 1 angle should be stated. So AI should rather generate a few concept from this example and check if it can be applied to other cases or another question given by another user. And this may be called learning by experience because it will reach faster to concepts it is already familiar with. However, this may distract from learning new things. Experience may be an obstacle for fresh look.

In board games

The above described example is pretty simple, but from analysis of difference of boards of chess AI could deduce a concept of move, capture and promotion. Analysis of Go boards could lead to infering concepts of chains and liberties. It is however a problem how to find the right path among tree of possibilities, what to concentrate on. But this is a topic for another post.