Sample Final Exam for review purposes

CMPT310, Fall 2000, Qiang Yang and Janet Hsiao

 

  1. For the following Boolean function, calculate the entropy of the data set from formula

 

A and not B

 

  1. Build a decision tree for the above formula

 

  1. Train a perceptron for the above formula

 

  1. What is the error rate of the above decision tree on “A and B”?
  2. Build a grammar to parse the following sentence:

I will spend my Christmas in Vancouver

 

  1. Consider the following natural language understanding problem:

 

S à N VP

N à I | AI

VP à V N

V à like | took

 

And the sentence: I like AI

 

Now, formulate the natural language parsing problem on this sentence as a constraint satisfaction problem.  What heuristic methods would you choose to solve it?

 

  1. Define stratified n-fold cross validation and 0.632 bootstrap estimation.

 

  1. Define supervised and unsupervised learning.  Which of the following is unsupervised learning: decision-trees, neural networks, cluster?

 

  1. Describe an algorithm to perform a three-person game in English.