Emulating PLN with MaxSAT

From OpenCog
Jump to: navigation, search


Answer Set Programming maps Prolog-type programs into SAT problems, which can provide very efficient solutions for some large-scale logic programming problems.

Here I suggest a very simple, direct way of doing something conceptually similar for certain problems expressed in OpenCog’s AtomSpace language.

What I will do is simply point out how some collections of Atoms can be directly mapped into Partial Weighted MaxSAT problems as described here:

https://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1774/1910

The OpenWBO Solver solves many large-scale Partial Weighted MaxSAT problems effectively

http://sat.inesc-id.pt/open-wbo/

and may be appropriate for usage together with OpenCog.

Weighted Disjunctions

Suppose we have N PredicateNodes

PredicateNode “Pred_k” <p_k, c_k>

for k=1,…,N

which all have the same input type (see Deep Types).

Suppose we also have knowledge about some disjunctions involving these predicates,

ORLink <p_i, c_i>
     Neg_{i(1)} Pred_{i(1)} 
      …
     Neg_{i(m)} Pred_{i(m)} 

where i(m) is in 1-N, and Neg_r is either NotLink or the identity operator

For instance we might have the predicates

PredicateNode isFat <.8,.9>
PredicateNode isUgly <7,.3>
PredicateNode isAmerican <.2,.9>

and the disjunctions

ORLink <.8,.8>
	isFat
	isUgly
	NotLink
		isAmerican 

ORLink <.77,.85>
	isFat
	isUgly 

etc.

Given a set of Atoms of this nature, we can then treat the set of ORLinks as a weighted partial MaxSAT problem, where the weight of the clause

Neg_{i(1)} Pred_{i(1)} OR …. OR Neg_{i(m)} Pred_{i(m)} 

is simply the product

p_i *  c_i

Also, if in addition to a truth value <p_i, c_i> , we have for each disjunction an attention value <a_i> (say, a ShortTermImportance value), then we can do the same kind of mapping, but using values

p_i *  c_i * a_i

for clause weights…


Different Representations

Varying on the specifics of the above, instead of PredicateNodes we might have predicates like

EvaluationLink
      PredicateNode eats
      ListLink
	Variable $X
 	ConceptNode “cheese”

or

EvaluationLink
	PredicateNode “transmits”
	ListLink
		ConceptNode “Ben”
		ConceptNode $Y
		ConceptNode $Z

(the latter being a predicate whose argument is the list ($Y,$Z) ) – sorry, I’m playing a bit fast and loose with types here…. The important thing is that all the predicates in the predicate-system under consideration have the same input type…

Musings on Normalization

The main limitation of this approach, compared to e.g. PLN on knowledge represented with probabilistic logical operators, is that it requires knowledge to be boiled down into sets of disjunctions.

In crisp Boolean logic, one can straightforwardly take any set of Boolean relationships and normalize them into a set of disjunctions of (potentially negated) variables. With probabilistically weighted Boolean relationships, one can also do this normalization, but the probabilities one winds up with may depend on what independence assumptions one has made along the way, which means they may depend on what route one has taken in doing the normalization and on what background knowledge is there in the knowledge base (Atomspace).

So in general, if one is given a bunch of Atoms representing Boolean relationships, the task of reorganizing them into a collection of ORLinks whose truth values have confidences as high as possible, is an interesting/non-trivial inference task. In some applications this may be easy – perhaps the knowledge relevant to that application is already structured nicely as ORLinks. In other applications it could be quite difficult. One could perhaps view this as a special kind of inference chaining, and write a special inference control mechanism for this case.

Implementation

So one could envision two different functions, I guess

  • A function whose input is a SetLink of predicates with common input type, and which then grabs all ORLinks joining predicates from within the SetLink, and feeds them to OpenWBO, and then feeds the answers found by OpenWBO back into the AtomSpace
  • A function whose input is a SetLink of predicates with common input type, which does a bunch of reasoning to form high-confidence ORLinks joining predicates from within the SetLink, and THEN feeds these OrLinks to OpenWBO, etc.

The first of these is pretty easy to write, the second would require some thinking about the right inference control mechanism to use...

When to invoke these within autonomous cognitive functioning is another question, of course...

SAT Link parsing in the Atomspace

One "obvious" implementation of the above sort of process would be to implement a variant of what was done with the SAT Link Parser, but using the Atomspace version of the link grammar dictionary.

In this case a specialized process would be used to construct a set of ORLinks corresponding to the syntactic constraints in a sentence, and OpenWBO would be finding a parse for the sentence...