[SUMMARY] Inference Engine (#37)

[Ruby Quiz]

irb(main):005:0> are any programmers happy programmers?
=> Yes, some programmers are happy programmers.
irb(main):006:0> are all Ruby programmers happy programmers?
=> Yes, all ruby programmers are happy programmers.
irb(main):007:0> are any Python programmers happy programmers?
=> I don't know.

True artificial intelligence doesn't seem that far off after all.

Did you know you could use irb as an interface like that? I didn't! Be sure
and glance at Pit Capitain's code to see just how that is done.

Daniel Sheppard sent in a nice object model, translating the rules into a class
hierarchy. I recommend browsing through that too.

Here though, I want to look into Paulo Capriotti's code. Paulo decided to model
the relationships as a directed graph, where vertices are the groups and edges
represent their relationships. To save a little work, Paulo used the graph Ruby
library as a starting point. Here's the beginning of the solution:

require 'graph'

def opposite_type(type)
type == rovable_true ? rovable_false : rovable_true
end

class Property
attr_reader :name, :type
def initialize(name, type)
@name = name
@type = type
end

def opposite
Property.new(@name, @type == ositive ? :negative : ositive)
end

def Property.create(x)
if x.respond_to?opposite)
x
else
Property.new(x, ositive)
end
end

def hash
"#{@name}##{@type}".hash
end

def eql?(other)
@name == other.name and @type == other.type
end

alias == eql?

def to_s
res = @name
if @type == :negative
"not-" + res
else
res
end
end
end

# ...

First we see the definition of a simple helper method to convert between two
opposites: Things we can prove to be true and things we can prove are false.

Next, we have a helper class for a Property. I wasn't sure what that meant at
first, so I had to dig a little. Obviously, much of this class is just support
for hashing the object (hash() and eql?()). We have a class method to create()
a Property when needed and an interesting method to give us an opposite()
Property. The to_s() method is also interesting. We can see from it that a
negated Property gets a leading "not-" when converted to a String.

All of this clicked into place for me when I turned on Paulo's debug mode and
watched the code work. Here's an example:

All dogs are mammals

adding edge dog, not-dog, provable_false
adding edge not-dog, dog, provable_false
adding edge dog, dog, provable_true
adding edge not-dog, not-dog, provable_true
adding edge mammal, not-mammal, provable_false
adding edge not-mammal, mammal, provable_false
adding edge mammal, mammal, provable_true
adding edge not-mammal, not-mammal, provable_true
...
adding edge dog, mammal, provable_true
adding edge not-mammal, not-dog, provable_true
...
adding edge not-mammal, dog, provable_false
adding edge not-dog, mammal, provable_false
...
adding edge mammal, not-dog, provable_false
adding edge dog, not-mammal, provable_false
...

As you can see, a Property is a representation of the groups we are describing
to the inference engine. Opposites represent everything not in that Property,
or group. So the "dog" Property has an opposite of "not-dog", or non-dog, if
it's easier to think of that way.

What's the rest of that stuff about edges and what we can prove though? That's
the graph being built, as I mentioned earlier. Let's examine that code now:

# ...

class Knowledge < DirectedHashGraph
attr_reader :contradiction

def initialize
@contradiction = false
super
end

# Add a property and some tautologies.
# Here we assume that the property and
# its opposite are not void.
def add_property(x)
x = Property.create(x)
safe_add_edge(x, x.opposite, rovable_false)
safe_add_edge(x.opposite, x, rovable_false)
safe_add_edge(x, x, rovable_true)
safe_add_edge(x.opposite, x.opposite, rovable_true)
x
end

# Add en edge. Never throw.
def safe_add_edge(x, y, type)
catchadd_edge_throw) do
add_edge(x, y, type)
end
end

# Add an edge. Throw if the edge already exists.
def add_edge(x, y, type)
debug_msg "adding edge #{x}, #{y}, #{type}"
if self[x,y]
unless self[x,y] == type
@contradiction = true
debug_msg " \tcontradiction"
throw :add_edge_throw, :contradiction
else
debug_msg "\ti know"
throw :add_edge_throw, :i_know
end
else
super(x, y, type)
end
end

# Add an edge and its contrapositive.
def add_assertion(*args)
x, y, type = get_stmt(*args)
catchadd_edge_throw) do
add_edge(x, y, type)
add_edge(y.opposite, x.opposite, type)
:normal
end
end

# Extract statement values.
def get_stmt(*args)
case args.size
when 1
x, y, type = args[0].x, args[0].y, args[0].type
when 3
x, y, type = args[0], args[1], args[2]
else
raise "Invalid argument list in #{caller.first}"
end
return add_property(x), add_property(y), type
end

# Discover all possible deductions
# and add the corresponding edges to the graph.
def deduce
each_vertex do |v1|
each_vertex do |v2|
each_vertex do |v3|

if self[v1,v2] == rovable_true and
self[v2,v3] == rovable_true
add_assertion(v1, v3, rovable_true)
end

if self[v2,v1] == rovable_false and
self[v2,v3] == rovable_true
add_assertion(v3, v1, rovable_false)
end

if self[v1,v2] == rovable_true and
self[v3,v2] == rovable_false
add_assertion(v3, v1, rovable_false)
end

break if @contradiction
end
end
end
end

# Return true if a statement is provable.
# Return false if its negation is provable.
# Return nil if it is undecidable.
def test(*args)
x, y, type = get_stmt(*args)
case self[x,y]
when nil
return nil
when type
return true
else
return false
end
end
end

# ...

This class isn't as complicated as it appears, once you grasp the flow of how
it's used. When an assertion is made to the engine, it will first call test()
to see if it already knows that information or if it contradicts any other
information.

Assuming the test passes, add_assertion() gets called. That method starts by
calling get_stmt() to turn its arguments into two properties and a type
provable_true or rovable_false). Note that the return sequence of
get_stmt(), uses add_property() to ensure that the graph already contains basic
relationships for that property (all dogs are dogs, for example). These basic
relationships are added using safe_add_edge(), which is really just a shell over
add_edge() that filters out the symbols that are thrown by the latter. Getting
back to add_assertion(), we can see that it too uses add_edge(), but it returns
the symbol thrown or its own :normal to indicate if we already knew about the
assertion or if it contradicts what we did know. I know that's a lot to take
in, but if you just follow the chain of method calls it's pretty basic stuff.

Finally, deduce() is called after an assertion has been added. By walking the
edges, deduce() will fill in any details the new assertion uncovers. This is
done by checking relationships between three independent complete sets of
vertices, so relationships of the form one -> two -> three will be spotted.

You can see that this class is always monitoring for a @contradiction in each of
these methods. However, I don't think this ever comes into play, since each
assertion is tested before it's added. (Correct me if I'm wrong Paulo!)

On to the user interface:

# ...

["Assertion", "Question"].each do |c|
Struct.new(c, :x, :y, :type)
end

class UI

# Parse input and return a statement
def get_statement(line)
case line
# assertions
when /^all (.*)s are (.*)s\.?$/
return Struct::Assertion.new( Property.create($1),
Property.create($2),
rovable_true )
when /^no (.*)s are (.*)s\.?$/
return Struct::Assertion.new( Property.create($1),
Property.create($2).opposite,
rovable_true )
when /^some (.*)s are not (.*)s\.?$/
return Struct::Assertion.new( Property.create($1),
Property.create($2),
rovable_false )
when /^some (.*)s are (.*)s\.?$/
return Struct::Assertion.new( Property.create($1),
Property.create($2).opposite,
rovable_false )
# questions
when /^are all (.*)s (.*)s\?$/
return Struct::Question.new( Property.create($1),
Property.create($2),
rovable_true )
when /^are no (.*)s (.*)s\?$/
return Struct::Question.new( Property.create($1),
Property.create($2).opposite,
rovable_true )
when /^are any (.*)s not (.*)s\?$/
return Struct::Question.new( Property.create($1),
Property.create($2),
rovable_false )
when /^are any (.*)s (.*)s\?$/
return Struct::Question.new( Property.create($1),
Property.create($2).opposite,
rovable_false )
# description
when /^describe (.*)s\.?$/
return Property.create($1)
else
return nil
end
end

# Return a description of the relation
# between x and y.
# Assume that x is positive and that
# x -> y is not undecidable.
def describe_edge(x, y, aff = true)
case @k[x,y]
when rovable_true
case y.type
when ositive
return "All #{x.name}s are #{y.name}s"
when :negative
return "No #{x.name}s are #{y.name}s"
end
when rovable_false
case y.type
when ositive
if aff
return "Some #{x.name}s are not #{y.name}s"
else
return "Not all #{x.name}s are #{y.name}s"
end
when :negative
if aff
return "Some #{x.name}s are #{y.name}s"
else
return "Not all #{x.name}s are not #{y.name}s"
end
end
end
end

# Return a list of sentences which describe
# the relations between x and each other node.
# Assume that x is positive.
def describe_node(x)
res = []
@k.each_vertex do |y|
if y.type == ositive and not x == y
if @k[x,y] == rovable_true
res << describe_edge(x,y)
elsif @k[x,y.opposite] == rovable_true
res << describe_edge(x,y.opposite)
elsif @k[x,y]
res << describe_edge(x,y)
elsif @k[x,y.opposite]
res << describe_edge(x,y.opposite)
end
end
end

res
end

def say(value)
case value
when true
"Yes"
when false
"No"
else
"I don't know"
end
end

def initialize
@k = Knowledge.new
end

def wait_for_input
print '> '
gets
end

def run
while line = wait_for_input
line.chomp!
line.downcase!
stmt = get_statement(line)
if stmt.class == Struct::Assertion
case @k.test(stmt)
when true
puts "I know"
when false
puts "Sorry, that contradicts what I already know"
else
@k.add_assertion(stmt)
@k.deduce
puts "OK"
end
elsif stmt.class == Struct::Question
value = @k.test(stmt)
print say(value)
if value.nil?
print "\n"
else
puts ", #{describe_edge(stmt.x, stmt.y, value).downcase}"
end
elsif stmt.class == Property
describe_node(stmt).each do |sentence|
puts sentence
end
else
puts "I don't understand"
end
end
end
end

def debug_msg(msg)
puts msg if $debug
end

if $0 == __FILE__
ui = UI.new
ui.run
end

Again, this looks like a lot of code, but it's not overly complicated, once you
find the flow. Look at the last few lines to get a hint about where to begin.
First, initialize() creates a Knowledge object to keep tract of our assertions
and answer our questions. From that point on, run() handles the interactive
session.

The first thing you need to know is that run() uses a couple of helper methods:
say() for output and wait_for_input() for input. It also calls get_statement()
to parse input. The return from get statement is either a single Property (the
"describe" command), a Struct::Assertion representing an assertion made, or a
Struct::Question representing a question asked. You can see those Structs
defined just before the UI class starts. They're just two properties and a
type.

The other thing to notice about get_statement() is that it does very basic
Regexp based parsing. It uses a super clever trick of spotting a trailing "s"
to find the two groups in a line like, "Are all Ruby programmers happy
programmers?" Of course, this does not work across all legal inputs:

All oxen are mammals. I don't understand
All James's pets are Dana's pets. OK
Are all James's pets Dana's pets?

I don't know

To see another approach, examine Pit Capitain's parsing, especially the
IE.split() method.

Getting back to run() in Paulo's UI class, you'll see that the rest of the
method just handles the three different returns from get_statement().
Assertions are handled as I explained earlier. Questions rely on
describe_edge() for answers and the "describe" command triggers a call to
describe_node(). That's the entire UI.

I promise to end this long summary very soon now, but I wanted to mention just
one more detail. Paulo uses a helper method all through the code that's defined
near the end. Here's another look at it:

def debug_msg(msg)
puts msg if $debug
end

The goal here is obvious, print a lot of extra information if I set this global
variable to true. This is a trick that we all use sometimes in testing. I just
wanted to suggest one minor change to enhance this trick: Switch $debug to
$DEBUG. Then you can trigger the messages with a command-line switch like so:

$ ruby -e 'p $DEBUG'
false
$ ruby -d -e 'p $DEBUG'
true

Slide that one into your bag of tricks, because it comes in handy.

My thanks to all three submitters for some really great code to poke around in
and play with.

Tomorrow, we have a simple but handy hack to explore. It's an easy quiz so I
want to see all you beginners out there playing along!

 

[Paolo Capriotti]

You can see that this class is always monitoring for a @contradiction in =
each of

these methods. However, I don't think this ever comes into play, since e= ach
assertion is tested before it's added. (Correct me if I'm wrong Paulo!)

Yes, if no assertion is added when the opposite is already in the
graph after a deduction, one is granted not to obtain contradictions
on successive deductions.
This follows from the fact that (after the deduce method has been
called) the assertions form a theory which satisfies the following
property:
every theorem of either of the forms a -> b, not (a -> b) is an axiom.
This is not difficult to prove. One can use, for instance, boolean
ring theory and the Stone theorem.

Paolo