NATIONAL UNIVERSITY OF SINGAPORE

SCHOOL OF COMPUTING

 SEMESTER II  (1999-2000)

EXAMINATION FOR

CS3243: ARTIFICIAL INTELLIGENCE

May 2000                                               
                                                                                              Time Allowed: 2 Hours

INSTRUCTIONS TO CANDIDATES

1.   This examination paper consists of FIVE (5) questions and comprises SIXTEEN (16) printed pages including the cover page.

2.   Write your answers in the blank spaces in this answer book only.  Write on one side only.

3.   This is an OPEN BOOK examination.

4.    Please fill in your Matriculation Number below.  Also write your matriculation number on the top right hand corner of every page. 

Matriculation Number:         

1.(a) Write a LISP function named “choose” that randomly returns one of the sublists within its argument list.  Thus, suppose that “greetings” is a list containing a certain number of sublists as defined below: 

(setq  greetings  ’(   (how are you)
                              (good morning)
                              (ciao)
                               ………
                              (hello) ) ) 

Then your function “choose” may behave as follows: 

> (choose  greetings)
(GOOD MORNING) 

> (choose  greetings)
(HELLO)

You may use the system function “random” which returns a random number between 0 and n-1 where n is its argument.  Thus (random 10) will return an integer between 0 and 9.                        (6%)

1.(b)     One of the rules in ELIZA is such that when it detects one of the keywords “unhappy”, “depressed” and “upset”, it will reply “I am sorry to hear you are key”, or “Do you think coming here will make you not to be key”, or “Tell me why you are key”, where key is one of the above three keywords.  Write a LISP function named “rule1” that does so.  If none of the keywords is detected, “rule1” will return nil.  You must use the function “choose” that you have defined in 1(a). Assume that the input sentences have been converted to a list form.  Thus your “rule1” may behave as follows: 

> (rule1 ’(I have been rather depressed lately))
(TELL ME WHY YOU ARE DEPRESSED)

> (rule1 ’(My friends and colleagues make me very upset))
(DO YOU THINK COMING HERE WILL MAKE YOU NOT TO BE UPSET)

> (rule1 ’(That is why I am here to seek help))
NIL                                                                                                         (14%)

  2.   For each of the following statements, indicate whether you agree or do not agree or partially agree with the statement and give reason to support your answer.

(a)  MYCIN is a “Weak AI problem Solver” because it makes use of very specific domain knowledge and thus can only apply to a very limited range of problems, i.e. diagnosis of spinal meningitis.                                                                   (4%)

(b)   The following conceptual graph is illegal as the conceptual relation “swims” represented by an ellipse should be connected to another conceptual node represented by a box.                                                                                         (4%) 

2.(c)  The following diagram cannot be labeled using constraint propagation algorithm because the object in the diagram does not meet the assumptions required by the algorithm.  If you don’t agree with the statement, then label the diagram accordingly.                                                                                                            (3%) 

  (d)   The following diagram cannot be labeled using constraint propagation algorithm because the object in the diagram does not meet the assumptions required by the algorithm.  If you don’t agree with the statement, then label the diagram accordingly.                                                                                                          (3%)  

2.(e)  The following expression is a well formed formula because it is formed based on the syntactic rules of propositional calculus.                                                  (4%)   

~ ( A Ú B ) = ~ ( ~ A Ù ~ B )

(f)   Minimax search is a breadth-first search.                                                             (2%)

3.(a)  The following minimax search tree has static evaluation function scores with respect to the max player for all the leaf nodes, where +¥ denotes end of the game with the max player winning the game while -¥ denotes end of the game with the min player being the winner.  Use minimax search to find the values for all the non-leaf nodes. Do you get the same set of values whether you search the tree from left to right or from right to left?  Identify the leaf node which the max player is expected to reach from the root (node A).   Is it likely for the max player to win the game within 3 moves from the root including his opponent’s move?                                                          (8%) 

3.(b)  Use alpha-beta procedure in the direction from left to right to prune the search tree. Show alpha-beta values at appropriate nodes and indicate which arcs are to be pruned by the procedure.         (6%)

(c) Repeat the alpha-beta procedure but this time from right to left. Show alpha and beta values at appropriate nodes and indicate the arcs to be pruned.                                                                               (6%)

4.   Referring to Fig 11.7 in the text book (or slide 10.19 in the note), the “NUMBER” of a noun or a verb is either ‘singular’ or ‘plural’ or both.  In fact, the “NUMBER” should carry another piece of information, namely, ‘person’ in addition to being ‘singular’ or ‘plural’.  For instance, “I” and “we” are 1^st person, “you” is 2^nd person, “he”, “she”, “it”, “they” and all other nouns are 3^rd person. Among them, “I”, “he”, “she”, “it” are ‘singular’, while “we” and “they” are ‘plural’. On the other hand, “you” may be ‘singular’ or ‘plural’. Other nouns have their own ‘singular’ and ‘plural’ forms.  Also, “I”, “we”, “you”, “he”, “she”, “it” and “they” belong to a special group of nouns.  Their part-of-speech is known as “pronoun”. To represent ‘person’ together with ‘singular’ or ‘plural’, we will now use the following notations for “NUMBER” as follows: 

As a result of the above new definition for “NUMBER”, every verb will carry a corresponding “NUMBER” to match with the noun or pronoun in a sentence, based on the context. For instance, the word “am” which is a verb has the “NUMBER” 1S (as in “I am”), while another verb “are” has the “NUMBER” 1P, 2S, 2P or 3P (as in “We are”, “You are” or “Men are” etc). 

Now we assume that an Augmented Transition Network (ATN) has the following words in its dictionary entries: 

I, you, we, he, she, it, they, man, men, am, is, are, run, runs  

Note that the verbs “am”, “is” and “are” all have the same root form, i.e. “be”. 

Moreover, the ATN has a simple set of context free grammar rules as follows: 

sentence            ®     noun_phrase     verb_phrase 

noun_phrase      ®     pronoun 

noun_phrase      ®     noun 

verb_phrase      ®     verb

4.(a)  Draw the transition networks for “sentence”, “noun_phrase” and “verb_phrase”,
repectively, used by the ATN based on the context free grammar given above.  You
need not define the procedures used by the transition networks.                                                                                                     (4%)

4.(b)  Complete the dictionary entries for the ATN as follows:                            (9%) 

4.(c)  Complete the following parse tree for the following sentence: 

Men run. 

Explain how the ATN ensures that the “NUMBER” of  the noun phrase agrees with the “NUMBER” of the verb phrase.                                                                                                                (7%)     

5.      A person decides whether to eat at a restaurant based on two factors, namely, how expensive the food is as shown on its menu and whether there is a queue waiting outside the restaurant and if so, how long the queue is.  He has drawn up a decision table as follows: 

          He has also computed the information content of the above decision table based on the probabilities of his two decisions (i.e. yes or no) as follows: 

  I (decision table)  =   - P(yes) log₂ P(yes)  -  P(no) log₂ P(no) 

                                                         =    0.991  bits             

5.(a)  Suppose that the person wants to use the property “price of food on menu” (which we will abbreviate to “price”) as the root to construct a decision tree. Compute (i) the expected information needed to complete the decision tree and (ii) the information gain from the property “price”, i.e. find E(price) and gain(price).  The following mathematical formulas may be useful for your computation. 

                                                                                                                                       (8%)

5.(b)  Suppose that the person wants to use the property “queue waiting outside” (which we will abbreviate to “queue”) as the root to construct a decision tree. Compute (i) the expected information needed to complete the decision tree and (ii) the information gain from the property “queue”, i.e. find E(queue) and gain(queue).  The same mathematical formulas are reproduced for your use. 

                                                                                                                                        (7%)

5.(c)  Which property should the person choose as the root to construct his decision tree? Why? Draw the decision tree of his choice as follows.                                                                                              (5%)

END  OF PAPER