OpenCogPrime:EmbeddingBasedInference

From OpenCog
Jump to: navigation, search

Embedding Based Inference Control

One important application for dimensional embedding in OCP is to help with the control of

  • Logical inference
  • Direct evaluation of logical links

We describe how it can be used specifically to stop the OCP system from continually trying to make the same unproductive inferences.

To understand the problem being addressed, suppose the system tries to evaluate the strength of the relationship

SimilarityLink foot toilet

Assume that no link exists in the system representing this relationship.

Here "foot" and "toilet" are hypothetical ConceptNodes that represent aspects of the concepts of foot and toilet respectively. In reality these concepts might well be represented by complex maps rather than individual nodes.

Suppose the system determines that the strength of this Link is very close to zero. Then (depending on a threshold in the MindAgent), it will probably not create a SimilarityLink between the "foot" and "toilet" nodes.

Now, suppose that a few cycles later, the system again tries to evaluate the strength of the same Link,

SimilarityLink foot toilet

Again, very likely, it will find a low strength and not create the Link at all.

The same problem may occur with InheritanceLinks, or any other (first or higher order) logical link type.

Why would the system try, over and over again, to evaluate the strength of the same nonexistent relationship? Because the control strategies of the inference and logical relationship mining MindAgents are simple. These MindAgents work by selecting Atoms from the AtomTable with probability proportional to importance, and trying to build links between them. If the foot and toilet nodes are both important at the same time, then these MindAgents will try to build links between them — regardless of how many times they've tried to build links between these two nodes in the past and failed.

How do we solve this problem using dimensional embedding? Generally:

  • one will need a different embedding space for each link type for which one wants to prevent repeated attempted inference of useless relationships [though, sometimes, very closely related link types might share the same embedding space; this must be decided on a case-by-case basis]
  • in the embedding space for a link type L, one obviously only wants to embed Atoms of a type that can be related by links of type L

It is too expensive to create a new embedding very often. Fortunately, when a new Atom is created or an old Atom is significantly modified, it's easy to reposition the Atom in the embedding space by computing its relationship to the pivot Atoms. Once enough change has happened, however, new pivot Atoms will need to be recomputed, which is a substantial computational expense. We must update the pivot point set every N cycles, where N is large; or else, whenever the total amount of change in the system has exceeded a certain threshold.

Now, how is this embedding used for inference control? Let's consider the case of similarity first. Quite simply, one selects a pair of Atoms (A,B) for SimilarityMining (or inference of a SimilarityLink) based on some criterion such as:

importance(A)*importance(B) * simproj(A,B)

where

distproj(A,B) = dE( proj(A) , proj(B) )

simproj = 2-c*distproj

and c is an important tunable parameter.

What this means is that, if A and B are far apart in the SimilarityLink embedding space, the system is unlikely to try to assess their similarity.

There is a tremendous space efficiency of this approach, in that, where there are N Atoms and m pivot Atoms, N^2 similarity relationships are being approximately stored in m*N coordinate values. Furthermore, the cost of computation is m*N times the cost of assessing a single SimilarityLink. By accepting crude approximations of actual similarity values, one gets away with linear time and space cost.

Because this is just an approximation technique, there are definitely going to be cases where A and B are not similar, even though they're close together in the embedding space. When such a case is found, it may be useful for the AtomSpace to explicitly contain a low-strength SimilarityLink between A and B. This link will prevent the system from making false embedding-based decisions to explore (SimilarityLink A B) in the future. Putting explicit low-strength SimilarityLinks in the system in these cases, is obviously much cheaper than using them for all cases.

We've been talking about SimilarityLinks, but the approach is more broadly applicable. Any symmetric link type can be dealt with about the same way. For instance, it might be useful to keep dimensional embedding maps for

SimilarityLink
ExtensionalSimilarityLink
EquivalenceLink
ExtensionalEquivalenceLink

On the other hand, dealing with asymmetric links in terms of dimensional embedding, however, requires more subtlety. In the next subsection we'll discuss this.

Dimensional Embedding and InheritanceLinks

Next, how can we use dimensional embedding to keep an approximate record of which links do not inherit from each other? Because inheritance is an asymmetric relationship, whereas distance in embedding spaces is a symmetrical relationship, there's no direct and simple way to do so.

However, there is an indirect approach that appears to work, which involves maintaining two different embedding spaces, and combining information about them in an appropriate way. The two embedding spaces correspond to intensional and extensional information.

In this subsection, we'll discuss an approach that should work for InheritanceLink, SubsetLink, ImplicationLink and ExtensionalImplicationLink. But we'll explicitly present it only for the InheritanceLink case.

Although the embedding algorithm described above was intended for symmetric weighted graphs, in fact we can use it for asymmetric links in just about the same way. The use of the embedding graph for inference control differs, but not the basic method of defining the embedding.

In the InheritanceLink case, for the intensional embedding space, we can define pivot Atoms in the same way, and then we can define

projint(A)_i

to be equal to

(InheritanceLink A A_i).tv.s

where A_i is the i'th pivot Atom.

Similarly, for the InheritanceLink extensional embedding space, we define

projext(A)_i

to be equal to

(InheritanceLink A_i A).tv.s

Define

Int(A) = {X : InheritanceLink X A or SubsetLink X A or MemberLink X A)
 
Ext(A) = {X : InheritanceLink A X or SubsetLink A X}
 
SimInt(A,B) = ||Int(A) Intersection Int(B) ||/ || Int(A) Union Int(B)  

SimExt(A,B) = ||Ext(A) Intersection Ext(B) ||/ || Ext(A) Union Ext(B) 

The intensional embedding space will then have

2^{-cd(proj_int(A), proj_int(B))}

correlate with

SimInt(A,B)

whereas the extensional embedding space will have

2^{-cd(proj_ext(A), proj_ext(B))}

correlate with

SimExt(A,B)

Furthermore, if

Int(B) within Int(A)

then one can say something geometrically about the relationship between projint(A) and projint(B) in the intensional embedding space. Suppose one creates an (n-1)-dimensional hyperplane crossing through all the coordinate axes and also projint(B). This hyperplane divides the embedding space in two halves, one of which contains the origin. The half that does not contain the origin is where projint(A) should ideally lie. Arithmetically, one may compute

int_inh(A,B) = Sum_i (||| projint(A)_i ' projint(B)_i |||)

as an estimate of the likelihood that

InheritanceLink A B

Similarly, in the extensional embedding space, one may compute

ext_inh(A,B) = Sum_i ( |||projext(B)_i ' projext(A)_i |||)

as an estimate of the likelihood that

InheritanceLink A B

One may then decide whether it's worth evaluating

(InheritanceLink A B).tv.s

(via InheritanceMining or inference) based on:

importance(A) * importance(B) * f(int_inh(A,B), ext_inh(A,B))

where for instance we may choose

f(x,y) = c*(x+y)

where c is a normalizing parameter (that may, for instance, map f(int_inh(A,B), ext_inh(A,B)) into [0,1] for pairs (A,B)

distproj(A,B) = d_E( proj(A) , proj(B) )