COMP9414: Artificial Intelligence

Revision Exercises - Prolog, General AI, Natural Language Processing, Machine Learning

These exercises are presented in the form of a partial sample exam. They cover the material lectured by Bill Wilson.

FAMILY NAME 
OTHER NAMES 
STUDENT ID 
SIGNATURE 

THE UNIVERSITY OF NEW SOUTH WALES
Sample Examination (Section B only)
COMP9414
ARTIFICIAL INTELLIGENCE

(1)TIME ALLOWED - 2 HOURS
(2)TOTAL NUMBER OF QUESTIONS - 9
(3)ANSWER ALL QUESTIONS
(4)QUESTIONS CARRY THE NUMBER OF MARKS INDICATED
(5)TOTAL NUMBER OF MARKS ON PAPER: 100
CANDIDATE ARE ADVISED TO ALLOCATE THEIR TIME AT 1.8 MINUTES PER MARK.
(6)THIS PAPER MAY NOT BE RETAINED BY THE CANDIDATE

THERE will be 2 SECTIONS in the complete paper
ANSWER EACH SECTION IN A SEPARATE BOOK

ANSWERS MUST BE WRITTEN CLEARLY IN INK. EXCEPT WHERE THEY ARE EXPRESSLY REQUIRED, PENCILS MAY ONLY BE USED FOR DRAWING, SKETCHING, OR GRAPHICAL WORK.

Section B
ANSWER IN A SEPARATE BOOK

Prolog, Knowledge Representation, Natural Language Processing, Machine Learning

  1. (15 marks) Prolog programming

    1. Given the iProlog database and rules shown below, what is the output of the Prolog query that follows?

         child_of(mary, steve).
   child_of(mary, anne).
   child_of(alice, anne).
   child_of(alice, steve).
   child_of(jane, steve).
   child_of(leslie, steve).
   female(mary).
   female(alice).
   female(jane).

   sisters(Person1, Person2) :-
      child_of(Person1, Parent1), child_of(Person1, Parent2),
      not(Parent1 = Parent2),
      child_of(Person2, Parent1), child_of(Person2, Parent2),
      female(Person1), female(Person2), not(Person1 = Person2).

      Query:

      sisters(Sis1, Sis2)?

    2. Does the following Prolog query succeed? If not, explain why not. If so, what bindings will be reported?

      believes(X, likes(mary, pizza)) = believes(frank, likes(Y, pizza))?

      Integers and floating point numbers are built into most programming languages, including Prolog. However, suppose that numbers and arithmetic operations were not available. It is still possible to define numbers in Prolog and to write programs to implement simple arithmetic operations. In the following question, you MUST NOT use any of Prologs built-in arithmetic predicates such as is, <, +, *, etc. (except in part (f)). Also, do not use the cut operation (!) in your program.

      A positive integer can be defined as zero or the successor of another number. Thus, zero can be represented by 0 and a number, such as two, can be represented by s(s(0)), where two is the successor of the successor of 0. Thus s(X) can be thought of as X+1. We call numbers written like this s-expressions.

      In parts (c) to (f), don't worry about what happens if X (and Y and Z) are not s-expressions. You don't have to cope with this, and in particular, you don't have to check for this.

      See also the Wikipedia entry on the Peano axioms.

    3. Write a Prolog predicate, s_number(X), which is true when X is a valid number. For example: 
      ?- s_number(s(s(0))).
true.

    4. Write a Prolog predicate, minus1(X,Y), which is true if X is the successor of Y, i.e. if X = Y+1, or Y=X-1. Naturally, this predicate will fail if X is 0. 
      ?- minus1(s(s(0)), Y).
Y = s(0)
?- minus1(0, Y).
false.

    5. Write a Prolog predicate, subtract(X, Y, Z), which is true if Z represents the difference between X and Y, assuming X is greater than or equal to Y. If X is less than Y, then this predicate is undefined. 
      ?- subtract(s(s(s(s(0)))), s(s(0)), Z).
Z = s(s(0))

      Hint - the base case is when Y = 0.

    6. Write a Prolog predicate value_of(X, Y), which is true if Y is the natural number, in normal notation, corresponding to the s(s(...)) expression X. 
      ?- value_of(s(s(s(s(0)))), Y).
Y = 4

  2. Knowledge Representation (5 marks)

    1. Draw a semantic network to represent the sentence "Fred finds a furry purple cube."

    2. Briefly describe the function of each part of the match-resolve-act cycle in a rule-based system

    3. Briefly describe two types of demon used in the frame system described in lectures.

  3. Natural Language Processing - Short Answers (13 marks) Answer each of the following in no more than a few words each:

    1. What is the significance of a feature like VAR being a head feature for categories like S, VP, NP?

    2. What form can grammar rules take in a regular grammar?

    3. Give an example of a predicate operator in the logical form language.

    4. Name three more components of the logical form language described in lectures, and give examples of them.

    5. What is the result of applying the λ-expression λ x likes(x, pizza) to mary, after λ-reduction?

    6. What is meant by the term subcategorization?

    7. Give an example of a sentence that exhibits structural ambiguity, and draw two trees showing the ambiguity.

    8. What general form can the rules of a context-sensitive grammar take?

    9. Write the down the condition under which two feature values agree, and apply this to the two feature values {3s,3p} and {1s,2s,1p,2p,3p}.

     

  4. Natural Language Processing - Parsing (11 marks)

    This question is longer than you would get in an actual exam. This way, you get more practice.

    Given the following lexicon and grammar information, trace the steps in chart-parsing the two sentences

    Time flies. It flies like an arrow.

    Lexicon must cover any words to be processed.
    timeNOUN, VERB
    fliesNOUN, VERB
    itPRONOUN
    likePREP, ADJ, VERB, NOUN, ADV, CONJ
    anDET
    arrowNOUN

    Grammar
    RuleName
    S → NP VPTFIF-S1
    S → VERB NPTFIF-S2
    NP → NOUNTFIF-NP1
    NP → PRONOUNTFIF-NP2
    NP → DET NOUNTFIF-NP3
    PP → PREP NPTFIF-PP1
    VP → VERBTFIF-VP1
    VP → VERB PPTFIF-VP2

    For each word processed, you should state what new active arcs and what new constituents are added. Report the active arcs in a format exemplified below:

    ARC99: A → B1 * C D 0..1 by rule TFIF-A1format 1 for reporting active arcs
    ARC101: A → B1 C1 * D 0..2 from ARC99format 2 for reporting active arcs
    Similarly, report new constituents in a format exemplified below:

    A33: A → B1 C2 D3 0..3 by rule TFIF-A1 from ARC101format 1 for reporting constituents
    A55: A → B1 4..5 by rule TFIF-A1 & constituent B1format 2 for reporting constituents
    E66: E → "word" 4..5 by lexicon entry xformat 3 for reporting constituents

    Rule TFIF-A1 would be a grammar rule that read TFIF-A1: A → B C D, rule TFIF-A1 would be a grammar rule that read TFIF-A1: A → B, and lexicon entry x would read x: word: E ... where the "... " indicates that there could be other lexical categories of which "word" is a member. The label to the left of a new constituent should be of the form <name of the constituent type> followed by a unique identifying number. For example, if the new constituent was an NP, and it was the third one found by the algorithm, you could call it NP3.

    It is not necessary to draw a diagram showing constituents and/or arcs - you can if you want to.

  5. Machine Learning - 11 Marks

    1. (6 marks) Describe the information gain calculations that are used in ID3 to to decide which attribute to "split" on.

    2. (5 marks)

      1. State the delta rule for backpropagation learning and indicate the significance of each symbol used in its statement

      2. Draw a diagram of a 3-layer feedforward neural network, with 3 neurons in each layer, labelling the layers appropriately and indicating the connections between neurons.

Solutions (when available)

CRICOS Provider Code No. 00098G