[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] Inference Engine (#37

James Gray

7/1/2005 12:31:00 PM

The three rules of 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:

http://www.rub...

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.
3 Answers

Pit Capitain

7/3/2005 1:25:00 PM

0

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

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 Gray

7/3/2005 3:36:00 PM

0

On Jul 3, 2005, at 8:24 AM, Pit Capitain wrote:

> 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

Joost Diepenmaat

7/5/2005 1:20:00 PM

0

On Sun, Jul 03, 2005 at 10:24:50PM +0900, Pit Capitain wrote:
> 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
>
> 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?

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.