| 1. | a) | What is bias in learning? What biases are used by the decision tree learning algorithm? |
| b) | - A machine learning problem involves four attributes plus a class. The attributes have 3, 2, 2, and 2 possible values each. The class has 3 possible values.
| i. | How many possible different examples are there? |
| ii. | How many possible different conjunctive rules are there? |
|
| c) | Describe the difference between the kind of decision boundaries formed by decision tree algorithms and nearest-neighbor instance-based learning algorithms. |
| d) | Briefly describe a commercial application of machine learning. |
| e) | Why is a decision tree that fits the data really well not necessarily better than another that doesn't fit it so well?
|
| 2. | | State, in the form of pseudo-code and in as much detail as you can, the basic algorithm for these two machine learning schemes: |
| a) | RIPPER |
| b) | k-NN |
| | - In each case be sure to include
| i. | The basic idea of the algorithm; |
| ii. | Pseudocode for the algorithm; |
| iii. | A discussion of the effect of errors, or noise, in the example; |
| iv. | A summary of the advantages and disadvantages of the method compared with other methods of machine learning.
|
|
| 3. | a) | Does pruning a decision tree such as that produced by the basic (ID3) algorithm increase or decrease performance on the training set? on the test set? sometimes or always? |
| b) | With the version space method, do either of (i) the computation time taken, (ii) the final concept learned, depend on the sequence in which examples are presented? |
| c) | What is the difference between a "supervised" and an "unsupervised" learning scheme? What is the difference between an "incremental" and a "non-incremental" scheme? |
| d) | Define human learning in terms of (a) knowledge acquisition, and (b) performance improvement. What goes wrong when you apply these definitions to machines? |
| e) | Give an example of a concept description language that produces an infinite set of concepts.
|
| 4. | | Consider a classification problem with four binary attributes, A, B, C, and D, in which the classification is positive if either A=B=0 or C=D=0 and negative otherwise. |
| a) | Draw a decision tree for this problem. |
| b) | Describe a simple method for converting a decision tree to rules and illustrate it using this example. |
| c) | What is the drawback of this simple method for converting a decision tree to rules, and how can it be overcome? |
| c) | If it is overcome using the method you suggest, what are the rules that result?
|