[<< | Prev | Index | Next | >>] Friday, August 02, 2013
OKR 2 - Examples of Intuitive Reasoning
Sadly my code related to On Knowledge Representation has been sitting fallow for over a year (time flies...) but I brushed it up and have been playing with it some. Here are some simple examples of it in action.
This is starting with a completely naive system, which knows nothing of numbers or any other primitive types. Although I'm not too fussed about learning right now, I may as well demonstrate how learning by example can work. I'll arbitrarily use the predicated relation "gt(x, y)" to mean x is greater than y. Note that "gt" means nothing special to the system apriori. I'll be playing teacher to the system by showing it the examples it needs, and by telling it what to focus on. (So I am definitely playing humunculous to its currently missing brainstem. But one thing at a time.)
">>" shows input to the "shell".
>> gt(a, b) >> !gt(b, a) >> >> !gt(c, d) >> !gt(d, c)Here I have just given it four observations about four interfaces a-d. These happen to comprise all the cases we would ever see of the co-relations gt(a, b) and gt(b, a). So now I'll point out that there's something interesting about that particular combination of relations (which will create a table using those as columns), and tell it to learn what it can from the examples I've given:
>> ?gt(i, j) ?gt(j, i) >> >> /ponder >> /tables long ----- Row Tables ------ ( long ) [i,j: gt(i,j),gt(j,i)] 1: T F 1: F T 2: F F(The "long" format just means to show the contents of the tables rather than just their headers.)
Notice that from the two examples I gave it, it has learned the rule "i>j -> !j>i". (The counts here aren't very meaningful since this is from a tiny number of examples, so ignore those for now.) Also note that I didn't do anything too special as a teacher here -- I just showed it enough examples to cover the space. I could have showed it many random examples, as long as they were real (i.e., it should never see that i is both greater and less than j), and the same table would emerge. Now I will tell it that the table it is learning is good enough ("/close"), and then see what it can infer about a new set of variables:
>> /close >> >> gt(x, y) >> /ponder >> /ls x x: gt(x,y) !gt(y,x)So, I told it x is greater than y, and it told me that therefor y is not greater than x.
Now, I'll tell it to consider how gt() relates over three variables, and will give it a couple more observations:
>> ?gt(i, j) ?gt(j, k) ?gt(i, k) >> >> gt(y, z) >> gt(x, z) >> /ponder x y z >> /close >> /tables long ----- Row Tables ------ ( long ) [i,j: gt(i,j),gt(j,i)] 2: F . 2: . F [k,i,j: gt(i,j),gt(j,k),gt(i,k)] 3: T F . 3: F T . 1: T T T 2: F F F(Closing a table also runs a simplification pass, which is why the first table looks different from before. A '.' means "any" and is like a missing connection in a neural or Bayesian net.)
Note in total I've only given it one example (via three observations) of three interrelated variables (x, y, z), yet it was able to fill the entire table encoding both "i>j and j>k -> i>k" and "!i>j and !j>k -> !i>k".
How? (I didn't do anything special to enable this -- it just happened...)
The three-way table gets connected to the observed relations in multiple permutations (of i, j, k : x, y, z), which creates new relations over x, y, and z, which the first (two-way) table is then able to tell us more about through inference--the outcome of which is simply observed (as a set of examples) by the three-way table.
I've already closed it, so I can test it now:
>> !gt(u, v) >> !gt(v, w) >> /ponder u v w >> /ls u u: !gt(u,v) !gt(u,w) ?gt(v,u) ?gt(w,u)So here I told it "!u>v and !v>w" and it tells me thus "!u>w". It is also telling me it doesn't know whether v or w is greater than u (they could be equal).
Let's start it over again knowing nothing. This time, we'll teach it how to compare two 8-bit binary numbers. The shell also understands "implies" type rules (which it just compiles immediately into tables), so I'll use those to brute-force program a comparator (very similar to how a hardware comparator would be done). I'll also throw in the constants 0-10 so it can communicate with us more concisely:
>> 0(x) <-> !b00(x) !b01(x) !b02(x) !b03(x) !b04(x) !b05(x) !b06(x) !b07(x) >> 1(x) <-> b00(x) !b01(x) !b02(x) !b03(x) !b04(x) !b05(x) !b06(x) !b07(x) >> 2(x) <-> !b00(x) b01(x) !b02(x) !b03(x) !b04(x) !b05(x) !b06(x) !b07(x) >> 3(x) <-> b00(x) b01(x) !b02(x) !b03(x) !b04(x) !b05(x) !b06(x) !b07(x) >> 4(x) <-> !b00(x) !b01(x) b02(x) !b03(x) !b04(x) !b05(x) !b06(x) !b07(x) >> 5(x) <-> b00(x) !b01(x) b02(x) !b03(x) !b04(x) !b05(x) !b06(x) !b07(x) >> 6(x) <-> !b00(x) b01(x) b02(x) !b03(x) !b04(x) !b05(x) !b06(x) !b07(x) >> 7(x) <-> b00(x) b01(x) b02(x) !b03(x) !b04(x) !b05(x) !b06(x) !b07(x) >> 8(x) <-> !b00(x) !b01(x) !b02(x) b03(x) !b04(x) !b05(x) !b06(x) !b07(x) >> 9(x) <-> b00(x) !b01(x) !b02(x) b03(x) !b04(x) !b05(x) !b06(x) !b07(x) >> 10(x) <-> !b00(x) b01(x) !b02(x) b03(x) !b04(x) !b05(x) !b06(x) !b07(x) >> >> beq00(x, y) <-> b00(x) <-> b00(y) >> beq01(x, y) <-> b01(x) <-> b01(y) >> beq02(x, y) <-> b02(x) <-> b02(y) >> beq03(x, y) <-> b03(x) <-> b03(y) >> beq04(x, y) <-> b04(x) <-> b04(y) >> beq05(x, y) <-> b05(x) <-> b05(y) >> beq06(x, y) <-> b06(x) <-> b06(y) >> beq07(x, y) <-> b07(x) <-> b07(y) >> >> lt00(x, y) <-> !b00(x) b00(y) >> lt01(x, y) <-> !b01(x) b01(y) or beq01(x, y) lt00(x, y) >> lt02(x, y) <-> !b02(x) b02(y) or beq02(x, y) lt01(x, y) >> lt03(x, y) <-> !b03(x) b03(y) or beq03(x, y) lt02(x, y) >> lt04(x, y) <-> !b04(x) b04(y) or beq04(x, y) lt03(x, y) >> lt05(x, y) <-> !b05(x) b05(y) or beq05(x, y) lt04(x, y) >> lt06(x, y) <-> !b06(x) b06(y) or beq06(x, y) lt05(x, y) >> lt07(x, y) <-> !b07(x) b07(y) or beq07(x, y) lt06(x, y) >> >> lt(x, y) <-> lt07(x, y)Now I can give it some examples, ask it to pay attention to certain interesting things, and see what it can tell me:
>> 3(a) >> 5(b) >> 9(c) >> >> ?lt(a, b) >> ?lt(b, c) >> >> /ls a a: 3(a) ?lt(a,b) >> >> ?lt(x, y) ?lt(y, z) ?lt(x, z) >> /ponder a b c >> /close >> /ls a a: lt(a,b) lt(a,c) !lt(b,a) !lt(c,a) !0(a) !1(a) !2(a) 3(a) !4(a) !5(a) !6(a) !7(a) !8(a) !9(a) !10(a) ...Note that it has noticed that a cannot be any other number than 3, and that it has computed that a is less than both b and c.
Furthermore, it has again populated the three-way table as before, based this time entirely on the relationships it computed. Here is that learned table, plus one example of each of the tables the shell compiled from the above rules:
>> /tables long ----- Row Tables ------ ( long ) [y,z,x: lt(x,y),lt(y,z),lt(x,z)] 3: T F . 3: F T . 1: T T T 2: F F F [x: 6(x),b00(x),b01(x),b02(x),b03(x),b04(x),b05(x),b06(x),b07(x)] 1: T F T T F F F F F 1: F T . . . . . . . 1: F . F . . . . . . 1: F . . F . . . . . 1: F . . . T . . . . 1: F . . . . T . . . 1: F . . . . . T . . 1: F . . . . . . T . 1: F . . . . . . . T [x,y: b04(y),b04(x),beq04(x,y),lt03(x,y),lt04(x,y)] 1: T F . . T 1: F . F . F 1: F . . F F 1: . T F . F 1: . T . F F 1: . . T T T [x,y: b05(y),b05(x),beq05(x,y)] 1: T T T 1: T F F 1: F T F 1: F F T [y,x: b00(x),b00(y),lt00(x,y)] 1: T . F 1: F T T 1: . F F [y,x: lt(x,y),lt07(x,y)] 1: T T 1: F F ...Now we can pose our symbolic problem again, which it is able to solve without the aid of the 8-bit rules (which it can't use since we aren't giving it any concrete value, just abstract relationships) thanks to having inferred the abstract rule from observations of the consequences of the 8-bit rules:
>> lt(u, v) >> lt(v, w) >> ?lt(u, w) >> /ponder u v w >> /ls u u: lt(u,v) lt(u,w) ?lt(v,u) ?lt(w,u) ...Starting over again, we'll teach it how to add 8-bit binary numbers:
>> 0(x) <-> !b00(x) !b01(x) !b02(x) !b03(x) !b04(x) !b05(x) !b06(x) !b07(x) ... >> beq00(x, y) <-> b00(x) <-> b00(y) ... >> sum00(x, y, s) <-> !beq00(x, y) <-> b00(s) >> sum01(x, y, s) <-> sum00(x, y, s) and ( !carry00(x, y) and !beq01(x, y) <-> b01(s) ) or ( carry00(x, y) and beq01(x, y) <-> b01(s) ) >> sum02(x, y, s) <-> sum01(x, y, s) and ( !carry01(x, y) and !beq02(x, y) <-> b02(s) ) or ( carry01(x, y) and beq02(x, y) <-> b02(s) ) >> sum03(x, y, s) <-> sum02(x, y, s) and ( !carry02(x, y) and !beq03(x, y) <-> b03(s) ) or ( carry02(x, y) and beq03(x, y) <-> b03(s) ) >> sum04(x, y, s) <-> sum03(x, y, s) and ( !carry03(x, y) and !beq04(x, y) <-> b04(s) ) or ( carry03(x, y) and beq04(x, y) <-> b04(s) ) >> sum05(x, y, s) <-> sum04(x, y, s) and ( !carry04(x, y) and !beq05(x, y) <-> b05(s) ) or ( carry04(x, y) and beq05(x, y) <-> b05(s) ) >> sum06(x, y, s) <-> sum05(x, y, s) and ( !carry05(x, y) and !beq06(x, y) <-> b06(s) ) or ( carry05(x, y) and beq06(x, y) <-> b06(s) ) >> sum07(x, y, s) <-> sum06(x, y, s) and ( !carry06(x, y) and !beq07(x, y) <-> b07(s) ) or ( carry06(x, y) and beq07(x, y) <-> b07(s) ) >> >> carry00(x, y) <-> b00(x) b00(y) >> carry01(x, y) <-> !carry00(x, y) b01(x) b01(y) or (carry00(x, y) and (b01(x) or b01(y))) >> carry02(x, y) <-> !carry01(x, y) b02(x) b02(y) or (carry01(x, y) and (b02(x) or b02(y))) >> carry03(x, y) <-> !carry02(x, y) b03(x) b03(y) or (carry02(x, y) and (b03(x) or b03(y))) >> carry04(x, y) <-> !carry03(x, y) b04(x) b04(y) or (carry03(x, y) and (b04(x) or b04(y))) >> carry05(x, y) <-> !carry04(x, y) b05(x) b05(y) or (carry04(x, y) and (b05(x) or b05(y))) >> carry06(x, y) <-> !carry05(x, y) b06(x) b06(y) or (carry05(x, y) and (b06(x) or b06(y))) >> carry07(x, y) <-> !carry06(x, y) b07(x) b07(y) or (carry06(x, y) and (b07(x) or b07(y))) >> >> sum(x, y, s) <-> sum07(x, y, s) >> >> /tables long ----- Row Tables ------ ( long ) [x,y: b00(x),b00(y),carry00(x,y)] 1: T T T 1: F . F 1: . F F [x,y: b03(y),b03(x),carry02(x,y),carry03(x,y)] 1: T T F T 1: T . T T 2: F F . F 3: F . F F 1: . T T T 3: . F F F [s,x,y: b05(s),beq05(x,y),carry04(x,y),sum04(x,y,s),sum05(x,y,s)] 1: T T T T T 4: T T F . F 4: T F T . F 1: T F F T T 4: F T T . F 1: F T F T T 1: F F T T T 4: F F F . F 2: . . . F F ...We can now ask it to add, say, 8 and 4:
>> 8(m) >> 4(n) >> sum(m, n, o) >> /ponder >> /ls o o: sum(m,n,o) !0(o) !1(o) ... 12(o) ... !19(o) !20(o)And, heck, what happens if we ask it to do subtraction? Turns out it magically knows how to do that too:
>> 7(N) >> 18(O) >> sum(M, N, O) >> /ponder >> /ls M M: sum(M,N,O) !0(M) !1(M) ... 11(M) ... !19(M) !20(M)And.... it can also answer whether two values sum to a third or not:
>> 5(u) >> 6(v) >> 10(w) >> 11(z) >> >> ?sum(u, v, w) >> ?sum(u, v, z) >> /ponder >> /ls u u: 5(u) !sum(u,v,w) sum(u,v,z) ...Spiffy, eh?
NEXT UP: OKR 3 - Type Theory Weary[<< | Prev | Index | Next | >>]