diff options
Diffstat (limited to 'AnalogyUtils.md')
| -rw-r--r-- | AnalogyUtils.md | 234 |
1 files changed, 234 insertions, 0 deletions
diff --git a/AnalogyUtils.md b/AnalogyUtils.md new file mode 100644 index 0000000..1dedb58 --- /dev/null +++ b/AnalogyUtils.md @@ -0,0 +1,234 @@ +# Analogy-Utils +Python driver for interacting with the Mapper rules in [mapper.py](mapper.py). + +### Running Example +We will use the following running example from +[examples/letter_analogies/letter_analogy.py](examples/letter_analogies/letter_analogy.py): +``` +If abc becomes bcd and efg becomes efh, then what does ijk become? +``` +For notational simplicity, we will label the nodes corresponding to letters +like so: +``` +If abc becomes (b')(c')(d') and efg becomes (f')(g')(h'), then what does ijk become? +``` + +We will also assume facts related to the position of letters in the strings as +well as alphabetical ordering: +``` +(n1, a, Left), (n1, b, Right) +(n2, b, Left), (n2, c, Right) +... +(s1, a, Pred), (s1, b, Succ) +(s2, b, Pred), (s2, c, Succ) +(s3, a, Pred), (s3, b', Succ) +(s4, b, Pred), (s4, c', Succ) +... +``` +and so forth. + +### Broad Idea: Joint Traversal +Our goal is to form a map identifying corresponding nodes. + +If we think of the triplet structure as a graph, the basic idea behind our +approach is to do a joint, breadth-first traversal of the graph. We start by +assigning two nodes to correspond to each other, then we extend the +correspondance by following edges from each node iteratively and +simultaneously. + +### Starting the Analogy +We seed the analogy by telling it that two given nodes should correspond to +each other. In fact, we tell it that two _facts_ should correspond to each +other. In this case, a pretty safe fact to start with is that `abc` and `efg` +are both letter strings that are "pre-transformation." In other words, we +want to abstract the facts: +``` +(t1, abc, TransformFrom) and (t2, efg, TransformFrom) +``` +to form abstract nodes `^t` and `^???` with fact: +``` +(^t, ^???, TransformFrom). +``` + +##### In Code +In order to do this, we use the `Analogy.Begin` method, roughly like: +``` +analogy = Analogy.Begin(rt, { + no_slip[":MA"]: t1, + no_slip[":A"]: abc, + no_slip[":MB"]: t2, + no_slip[":B"]: efg, + no_slip[":C"]: TransformFrom, +}). +``` + +### Extending the Start +If `extend=True` is passed to `Analogy.Begin` (the default) then it will +automatically start to build out from this fact. Essentially, it will look at +all other facts regarding `t1` and `t2` and try to lift (antiunify) them into +abstract facts. In this case, we find that there are corresponding facts: +``` +(t1, b'c'd', TransformTo) and (t2, f'g'h', TransformTo) +``` +Hence in the abstract we can add the node `^?'?'?'` as well as the fact: +``` +(^t, ^?'?'?', TransformTo). +``` + +##### In Code +Again, this happens automatically in `Analogy.Begin(..., extend=True)`. At this +point, the abstraction consists of two abstract groups, `^???` and `^?'?'?'`, +where the latter is the post-transformation of the former. Hence the only +correspondance we know between the two examples so far is that they both +involve pairs of letter strings before and after the transformation. This is +all that is claimed by our initial mapping of `t1` and `t2`, hence +`Analogy.Begin` finishes. + +### Pivots: Extending With New Fact Nodes +To extend the analogy further, we need to involve additional fact nodes. We do +this by pivoting off of nodes already in the analogy and identifying fact nodes +that claim similar things about nodes already mapped to each other. For +example, we might have fact nodes `h1` and `h2` expressing that `a` is the +start of string `abc` and `e` is the start of string `efg`: +``` +(h1, abc, Group), (h1, a, Head) +and +(h2, efg, Group), (h2, e, Head). +``` +Note that `abc` and `efg` are already mapped to each other in the analogy, and +`h1` and `h2` both claim the same thing about `abc`/`efg` (namely, that they're +groups). Hence, we can infer that `h1` and `h2` might correspond to each other, +forming a new abstract node `^h` with fact: +``` +(^h, ^???, Group). +``` + +##### In Code +We perform this pivoting to a new fact node with the method +`Analogy.ExtendMap`: +``` +analogy.ExtendMap([Group]). +``` + +### Building off a Fact Node +We've now recognized that both `abc` and `efg` are groups of letters, but `h1` +and `h2` also claim something else: that each group has a head letter that +starts it. Because we've mapped `h1` and `h2` to each other, we can follow this +fact as well to infer that the heads of each group should probably correspond +as well. In other words, we can lift `a` and `e` to abstract node `^1` and add +fact: +``` +(^h, ^1, Head). +``` + +##### In Code +The call to `Analogy.ExtendMap` where we added `^h` in the first place will +automatically follow all facts of this form when possible. It does this by +calling the method `Analogy.ExtendFacts(^h)` which in turn repeatedly calls +the `NewConcrete` rule to add nodes like `^1` and `Analogy.LiftFacts(^h)` to +lift any other triplets like `(^h, ^1, Head)`. + +### Summary of Analogy-Making by Traversal +In general, the operations described above are enough to create an analogy. We +pivot repeatedly between: +(i) Abstracting fact nodes that make claims about nodes already in the +analogy. E.g., `h1` and `h2` claim `abc` and `efg` (which we know correspond) +are groups, hence, `h1<->h2` is probably consistent with our analogy so we +can abstract them to `^h`. +(ii) Abstract nodes for which claims are made in those corresponding fact +nodes. E.g., we think `h1` and `h2` correspond, and `h1` claims `a` is a head +while `h2` claims `e` is a head of corresponding groups `abc` and `efg`. Hence, +we might infer that in fact `a` and `e` correspond, forming some abstract node +`^1` which is also a head of the abstract group `^???`. + +### Avoiding Bad Maps +Unfortunately, this approach can run into problems. For example, after we say +that `a` and `e` correspond, we might notice that there are fact nodes `s1` and +`m1` with facts: +``` +(s1, a, Pred), (s1, b, Succ) +and +(m1, e, Pred), (m1, f, Succ). +``` +We could then map `s1<->m1` and follow this to map `b<->f`, which would +work perfectly. However, there might _also_ be a fact node `m3` with facts: +``` +(m3, e, Pred), (m3, f', Succ), +``` +which actually maps _across groups_ `efg` and `f'g'h'`. The problem is that we +pivot to groups based only on a single triplet, and, hence, looking at only a +single triplet it's not clear if we should map +``` +(s1, a, Pred)<->(m1, e, Pred) +or +(s1, a, Pred)<->(m3, e, Pred). +``` +Both options look equally good when deciding whether `s1` should correspond to +`m1` or `m3`. If we pick `s1<->m1`, we saw that everything works and we map +`b<->f` as desired. However, if we map `s1<->m3` then we will infer that +actually `b<->f'`, which is probably wrong. We need some way to decide +between the two equally plausible mappings. + +##### Heuristic 1: Follow Unique Claims First +The first heuristic is to avoid such scenarios when possible by following +claims which are _unique_. In this case, the problem only came about because +the first `a` was actually an alphabetical predecessor of two different nodes, +the `b` in `abc` and the `b'` in `b'c'd'`. So when we follow predecessor -> +successor, we have to make a choice of which successor we want to choose. + +If we instead had followed the claim that that `a` is _to the left_ of some +other letter, there would only be one choice: the `b` in `abc`. Similarly, the +only thing to the right of the `e` is the `f` in `efg`. Hence, if we had +followed the `Left`/`Right` relation instead of `Pred`/`Succ`, we would have +arrived at the most reasonable option `b<->f`. + +This generally means following _structural_ relations first, and _semantic_ +relations only after that. + +In code, this usually looks like calling `analogy.ExtendMap` multiple times +with different parameters, of decreasing level of uniqueness. + +##### Heuristic 2: All or Nothing +Following `Left`/`Right` relations first gives us the desired correspondance of +`b<->f`. However, this doesn't immediately solve the original problem of +determining if `s1<->m1` or `s1<->m3`. Once we have decided `b<->f`, however, +we can try both `s1<->m1` and `s1<->m3` and apply our second heuristic: take +_only the fact nodes where all facts lift_. In this case, we could try to +correspond `s1<->m3` but then we would find that we could _not_ make the facts +``` +(s1, b, Succ) and (m3, f', Succ) +``` +correspond to each other, because we do not have `b<->f'`. Thus, `s1<->m3` +would leave facts which don't lift to the abstraction while `s1<->m1` would be +able to lift all the relavant facts. Hence, we would prefer `s1<->m1`. + +In the code, this is implemented in `analogy.ExtendFacts` by calling +`analogy.LiftFacts` to try and lift all relevant facts to the abstract and +then `analogy.FactsMissing` to check if all facts were lifted. If some can't +be lifted, then `ExtendFacts` will return `False` and `ExtendMap` will give +up on that mapping. + +##### Heuristic 3: Voting +In the near future we would like to take an alternate approach, which is +somewhat closer to the original Copycat: voting. Essentially, in this case we +have that following `s1<->m1` leads to a better analogy because then we can +lift all facts and it also agrees with the unique mapping when we follow +`Left`/`Right` to get `b<->f`. + +### Completing an Analogy +Suppose we have already mapped `abc->bcd` and `efg->fgh` and want to start +solving `ijk->?`. We: +* First call `Analogy.Begin(..., exists=True)` to map `ijk` into the _existing_ + analogy noting correspondances between `abc->bcd` and `efg->fgh`. +* Then, we call `Analogy.ExtendMap` as before to complete the analogy between + `ijk->?` and `abc->bcd`/`efg->fgh`. +* Then, we set `analogy.state="concretize"`. +* Then, we again call `Analogy.ExtendMap`. It will continue to traverse the + existing analogy between `abc->bcd` and `efg->fgh`, but, because we set + `state="concretize"`, instead of looking for nodes already in the structure + that might correspond to abstract nodes, it just adds new nodes to the + structure and lowers the corresponding facts from the abstract to these + nodes. +* Finally, we run inference rules which solve those lowered facts. E.g., we + might lower a fact that says that `_1` is the successor of `a`, then infer + that `_1` is the letter `b`. |