[QUIZ] Inference Engine (#37)
Ruby Quiz
1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.
2. Support Ruby Quiz by submitting ideas as often as you can:
3. Enjoy!
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
There was an interesting thread on Ruby Talk recently about Truth Maintenance
Systems (TMS). One reason to use a TMS is to validate inferences, given certain
truths. We'll focus on that application here.
This week's Ruby Quiz is to build an inference engine that is capable of
answering questions based on the provided truths.
Note that our Perl friends have already done this quiz, with their own Perl Quiz
of the Week. It was an interesting problem that generated good solutions and
discussion. Because of that, I'm going to copy the format used there,
originally by Dan Sanderson and Mark Jason Dominus.
You should be able to teach your engine truths with the following inputs:
All PLURAL-NOUN are PLURAL-NOUN.
No PLURAL-NOUN are PLURAL-NOUN.
Some PLURAL-NOUN are PLURAL-NOUN.
Some PLURAL-NOUN are not PLURAL-NOUN.
You should also be able to query your engine with the following questions:
Are all PLURAL-NOUN PLURAL-NOUN?
Are no PLURAL-NOUN PLURAL-NOUN?
Are any PLURAL-NOUN PLURAL-NOUN?
Are any PLURAL-NOUN not PLURAL-NOUN?
Describe PLURAL-NOUN.
Here's a sample run straight out of the Perl Quiz to show how all of this fits
together:
> All mammals are hairy animals.
OK.
> All dogs are mammals.
OK.
> All beagles are dogs.
OK.
> Are all beagles hairy animals?
Yes, all beagles are hairy animals.
> All cats are mammals.
OK.
> All cats are hairy animals.
I know.
> Are all cats dogs?
I don't know.
> No cats are dogs.
OK.
> Are all cats dogs?
No, not all cats are dogs.
> Are no cats dogs?
Yes, no cats are dogs.
> All mammals are dogs.
Sorry, that contradicts what I already know.
> Some mammals are brown animals.
OK.
> Are any mammals dogs?
Yes, some mammals are dogs.
> Are any dogs brown animals?
I don't know.
> Some dogs are brown animals.
OK.
> All brown animals are brown things.
OK.
> Are any dogs brown things?
Yes, some dogs are brown things.
> Describe dogs.
All dogs are mammals.
All dogs are hairy animals.
No dogs are cats.
Some dogs are beagles.
Some dogs are brown animals.
Some dogs are brown things.
> Are all goldfish mammals?
I don't know anything about goldfish.
In the discussion of the Perl Quiz, some very interesting examples were posted.
Here's my favorite, which we'll call extra credit:
> All dogs are mammals
OK.
> No octopuses are mammals
OK.
> Are any octopuses dogs?
I don't know.
That's not the correct answer. See how your engine answers that question.
Pit Capitain
> This week's Ruby Quiz is to build an inference engine that is capable of
> answering questions based on the provided truths.
>
Just out of curiosity, after entering
> All Foos are Bars
OK.
what should be the response to
> No Foos are Bars
If the answer is "OK." it would mean that the set of "Foos" is empty,
because no Foo can be a Bar and not be a Bar. Questions like
> Are all Foos <whatever>?
should then be answered with Yes.
The other alternative would be to assume that when speaking of "Foos"
the set of "Foos" isn't empty and there exists at least one Foo?
Regards,
Pit
James Edward Gray II
> Ruby Quiz schrieb:
>
>> This week's Ruby Quiz is to build an inference engine that is
>> capable of
>> answering questions based on the provided truths.
>> ...
>>
>
> Just out of curiosity, after entering
>
> > All Foos are Bars
> OK.
>
> what should be the response to
>
> > No Foos are Bars
Basically, whatever you are comfortable with.
> If the answer is "OK." it would mean that the set of "Foos" is
> empty, because no Foo can be a Bar and not be a Bar. Questions like
>
> > Are all Foos <whatever>?
>
> should then be answered with Yes.
This is the correct logical interpretations, but...
> The other alternative would be to assume that when speaking of
> "Foos" the set of "Foos" isn't empty and there exists at least one
> Foo?
This makes more sense to me, so it's probably what I would choose.
Given that, I would likely just print an error message to the user,
in the example you give.
James Edward Gray II
Paolo Capriotti
Abu Abdullah
C:\>inference
> all dogs are mamals
OK
> all mamals are hairy animals
OK
> all mamals are dogs
OK ------------------ ? ? ?
Paolo Capriotti
> C:\>inference
> > all dogs are mamals
> OK
> > all mamals are hairy animals
> OK
> > all mamals are dogs
> OK ------------------ ? ? ?
why not?
Paolo
Nikolai Weibull
> why not?
A → B doesn't imply B ← A,
nikolai
--
Nikolai Weibull: now available free of charge at http://bitwi.se/!
Born in Chicago, IL USA; currently residing in Gothenburg, Sweden.
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}
Ryan Leavengood
> Paolo Capriotti wrote:
>
>
>>On 7/4/05, Abu Abdullah <ala...@eim.ae> wrote:
>>
>>
>>>C:\>inference
>>> > all dogs are mamals
>>>OK
>>> > all mamals are hairy animals
>>>OK
>>> > all mamals are dogs
>>>OK ------------------ ? ? ?
>
>
>>why not?
>
>
> A → B doesn't imply B ← A,
> nikolai
>
But here the rules are being set up, and the above relationship is being
defined for dogs and mammals. This is not a conflicting rule. I think
Abu sees it as a conflicting rule.
Ryan
Abu Abdullah
using the quiz web page as a source for testing. and selecting from the
available sample there, i selected the facts *2* , *1* and *6* respectivly.
and after supplying the *6th* rule, the engine should say *"Sorry, that
contradicts what I already know."*
James Edward Gray II
> using the quiz web page as a source for testing. and selecting from
> the available sample there, i selected the facts *2* , *1* and *6*
> respectivly.
> and after supplying the *6th* rule, the engine should say *"Sorry,
> that contradicts what I already know."*
You skipped the rules that makes it a contradiction:
No cats are dogs. (After: All cats are mammals.)
James Edward Gray II
Daniel Sheppard
http://members.iinet.net.au/~soxbox/inference.rb
#####################################################################################
This email has been scanned by MailMarshal, an email content filter.
#####################################################################################
Daniel Sheppard
Up now.
I also put up my tests at:
http://members.iinet.net.au/~soxbox/inferencetest.rb
Paolo Capriotti
> My solution is here:
>
> http://members.iinet.net.au/~soxbox/inference.rb
There are some problems:
> all dogs are mammals
OK.
> all mammals are animals
OK.
> some animals are not mammals
Sorry, that contradicts what I already know.
--
Paolo
Daniel Sheppard
-----Original Message-----
From: Paolo Capriotti [mailto:p.cap...@gmail.com]
Sent: Tuesday, 5 July 2005 2:38 PM
To: ruby-talk ML
There are some problems:
--
Paolo
#####################################################################################
Joost Diepenmaat
I'd go with this last interpretation. I'm assuming the input is not
talking about abstract concepts, but about sets of "real, existing" things.
In the same vein:
> All dogs are mammals.
> All mammals are dogs.
Could be taken to mean that the set of dogs and the set of mammals are
equivalent (so, basically dogs == mammals) OR it could be taken to be
contradictory, if we assume a maximum amount of information conveyed by
the input (i.e. if all dogs are mammals then mammals is a larger set
than dogs and there are other mammals that are not dogs)
Going for the latter interpretation will probably simplify some inferences.
Joost.
C Erler
You know that not all mammals are dogs. How does the computer ? Let's say I
enter :
All prime numbers are noncomposite.
All prime numbers are nonfactorable.
All noncomposites are prime numbers.
This is of the same form as the example given and would not be a
contradiction. The computer does not know anything about dogs or prime
numbers except what you tell it. All it can look at is the form of what
you've typed in. If the forms don't clearly indicate contradiction, the
computer does not know there is one.
Also, making the computer say "Contradiction" with that small amount of
information would mean that you could never effectively say that two names
(dogs and mammals or prime numbers and noncomposites) refer to the same
thing, even though that happens in real life.
Pit Capitain
the implementation isn't as understandable as I'd like.
Only to test whether it's possible, I chose irb for the user interface.
After loading the file, you can enter facts and queries in plain text:
irb(main):001:0> require "ie"
=> true
irb(main):002:0> all mammals are hairy animals
=> OK.
irb(main):003:0> all dogs are mammals
=> OK.
irb(main):004:0> are all dogs hairy animals?
=> Yes, all dogs are hairy animals.
irb(main):005:0> describe dogs
=> All dogs are hairy animals.
All dogs are mammals.
irb(main):006:0>
If you want to try it, note that you aren't allowed to enter dots (".")
after facts and that you have to enter question marks ("?") after queries.
Regards,
Pit
Ruby Quiz
=> 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 == :provable_true ? :provable_false : :provable_true
end
class Property
attr_reader :name, :type
def initialize(name, type)
@name = name
@type = type
end
def opposite
Property.new(@name, @type == :positive ? :negative : :positive)
end
def Property.create(x)
if x.respond_to?(:opposite)
x
else
Property.new(x, :positive)
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, :provable_false)
safe_add_edge(x.opposite, x, :provable_false)
safe_add_edge(x, x, :provable_true)
safe_add_edge(x.opposite, x.opposite, :provable_true)
x
end
# Add en edge. Never throw.
def safe_add_edge(x, y, type)
catch(:add_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)
catch(:add_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] == :provable_true and
self[v2,v3] == :provable_true
add_assertion(v1, v3, :provable_true)
end
if self[v2,v1] == :provable_false and
self[v2,v3] == :provable_true
add_assertion(v3, v1, :provable_false)
end
if self[v1,v2] == :provable_true and
self[v3,v2] == :provable_false
add_assertion(v3, v1, :provable_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 :provable_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),
:provable_true )
when /^no (.*)s are (.*)s\.?$/
return Struct::Assertion.new( Property.create($1),
Property.create($2).opposite,
:provable_true )
when /^some (.*)s are not (.*)s\.?$/
return Struct::Assertion.new( Property.create($1),
Property.create($2),
:provable_false )
when /^some (.*)s are (.*)s\.?$/
return Struct::Assertion.new( Property.create($1),
Property.create($2).opposite,
:provable_false )
# questions
when /^are all (.*)s (.*)s\?$/
return Struct::Question.new( Property.create($1),
Property.create($2),
:provable_true )
when /^are no (.*)s (.*)s\?$/
return Struct::Question.new( Property.create($1),
Property.create($2).opposite,
:provable_true )
when /^are any (.*)s not (.*)s\?$/
return Struct::Question.new( Property.create($1),
Property.create($2),
:provable_false )
when /^are any (.*)s (.*)s\?$/
return Struct::Question.new( Property.create($1),
Property.create($2).opposite,
:provable_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 :provable_true
case y.type
when :positive
return "All #{x.name}s are #{y.name}s"
when :negative
return "No #{x.name}s are #{y.name}s"
end
when :provable_false
case y.type
when :positive
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 == :positive and not x == y
if @k[x,y] == :provable_true
res << describe_edge(x,y)
elsif @k[x,y.opposite] == :provable_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
> 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!)
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