SAMPLE EXAM ANSWERS: COMS30106 "Artificial Intelligence" 1997 C. Giraud-Carrier

Question 1
----------

a) h1 is more informed than h2 means for all N, h1(N) >= h2(N).
   h1 is admissible means for all N, h1(N) <= h*(N).
   Graceful decay of admissibility means if h rarely overestimates h* by more
      than d, then the A* algorithm will rarely find a solution whose cost is d
      larger than the cost of the optimal solution.
   Practical use: no need to find a perfectly admissible heuristic; only one
      that rarely overshoots => easier to find such heuristics, easier to
      check.

b) Production system:
      data/working memory = states of knowledge, global, search space
      production rules = condition-action pairs, problem-solving knowledge,
         marked => enabled, enabled => may fire
      control strategy = search techniques to find solution in state space,
         way to resolve conflicts
      start state(s)
      termination condition of goal state(s)

   Illustration with 8-puzzle:
      working memory = all possible configurations of tiles
      production rules = legal moves of tiles
      control strategy = user-driven technique
      start state = some board configuration
      termination condition = some board configuration

c) g = cost of going from start to current state
   h = ESTIMATED cost of going from current to goal state
   g guarantees shortest path to solution
   h prunes the search space, ie reduces the number of states visited (more
      informed)
   straightforward from tree
      (each node in tree stores values for g and h)
      (i) expands depth first
      (ii) expands using h only (queue ordered in increasing values of h)
      (iii) expands using f = g + h

d) straightforward from tree
      (leaf nodes labelled with evaluation function's value)


Question 2
----------

a) User interface = human/machine interaction
   Knowledge base = theory, facts, rules (case-specific and general)
   Explanation subsystem = inspectability, why/how queries
   KB editor = modifiability, locate bugs, check consistency, add/remove/update
      rules
   Inference engine = heart of system, perform reasoning
   Shell components = all except knowledge base

b) Knowledge engineer: elicit knowledge from experts and translate into
      computer-readable form
   Novice => makes no assumptions, requires detail, pushes expert's explanation
      to the limit, increases chances of getting understandable rules, etc
   Expertise = any three of:
      changes
      is one person's view point
      is knowing how rather than knowing what
      is practise-based

c) (i) No; this problem is easily solved with traditional techniques
   (ii) Yes; large body of knowledge, symbolic approach is suitable, experts
           exist, traditional techniques do not work, etc (proper size & scope)
   (iii) No; no knowledge is available about that domain
   (iv) No; requires common sense, too large a problem, scope undefined

d) The necessary and sufficient conditions for a physical system to exhibit
      general intelligence is that it be a physical symbol system
   Answer includes
      human intelligence is symbolic
      focus of AI should be on representation and search
      argument against AI must attack the PSSH
      etc

Question 3
----------

a) Given:
      a language of instances
      a language of generalisations
      a matching predicate
      set of positive and negative examples
   Find: generalisations that
      1) are consistent with the examples
      2) extend beyond observed examples
   Any 2 of:
      replace constant with variable, eg, colour(ball,red) -> colour(x,red)
      drop conditions, eg, colour(x,red) ^ size(x,small) -> size(x,small)
      add disjunct, eg, colour(x,red) ^ size(x,small) ->
         (colour(x,red) v colour(x,blue)) ^ size(x,small)
      replace prop. with parent, eg, colour(x,red) -> colour(x,primary-colour)

b) straightforward application of the ID3 algorithm

c) 1) Generate N individuals randomly
   2) Compute fitness of all individuals
   3) Select some individuals for reproduction based on fitness
   4) For each pair of parents
         perform genetic operations (cross-over & mutation)
   5) Replace least fit individuals by new offspring
   6) If convergence or termination condition, then stop, else goto 2)

   fitness = measure of goodness of a solution
   cross-over = exploitation, pass on the good genes of the parents
   mutation = exploration, search space for new candidate solutions

Question 4
----------

a) Turing test = imitation game with 1 human, 1 machine and 1 interrogator.
      All communication with typewritten medium; interrogator must distinguish
      machine from human
   Open discussion including: humanity versus intelligence, birds analogy, does
      TT place a limit on intelligence, easy to set up and test, etc

b) supervised = output provided, classification tasks, arbitrary mappings
   unsupervised = no output provided, categorisation tasks, similar things map
      to points
   supervised: credit assessment using customer's features etc
   unsupervised: clustering data points, learning an animal taxonomy, etc

   Competitive learning:
      Let n = number of active line
      Let xi = value of input line i
      After each new training instance, update weights as:
         Delta wij = 0 if unit j loses
                  = g (xi/n - wij) otherwise
         where g is the learning rate

c) graceful degradation = (grandmother cell) the loss of units in the network
      does not result in the complete loss of any particular concept (ie no
      mapping between concept and node)
   any two of:
      biological plausibility
      massive parallelism
      distributed knowledge representation
      noise handling
      inductive learning

   Back-propagation:
      repeat
         present new training instance
         compute error of output units
         update weights to output units
         for each hidden layer
            compute error using error from next layer
            update weights
      until (error < critical value)

d) straightforward