Mas 557 기계학습 이론 및 응용

Homework #2

due date: 3/29/07

1. Give decision trees to represent the following boolean functions:

(a) [eqn: A WEDGE LNOT B]

(b) [eqn: A`XOR`B] (exclusive or)

(c) [eqn: LEFT [ A LOR B RIGHT ] LAND LEFT [ C` LOR D RIGHT ]]

2. Consider the following set of training examples:

instance	classification	a1	a2	a3
1	+	T	T	T
2	+	T	T	F
3	-	T	F	T
4	-	T	F	F
5	-	F	T	T
6	+	F	T	F

(a) What is the entropy of this collection of training examples with respect to the target function classification?

(b) What is the best root node for the decision tree from a view point of reducing the entropy?

(c) Does the ID3 algorithm always provide the best solution for the boolean logic? (yes or no)  Justify your answer.

3. Why do we need the pruning method in ID3 algorithm?  Describe your reason.

4. Consider the following weight update rule of perceptron for binary classification:

[eqn: {under{w}} _{k+1} = {under{w}} _{k} - {under{x}} _{k}]  for [eqn: k >= 1]

where [eqn: {under{w}} _{k} ^{T} {under{x}} _{k} <= 0].

(a) Does this weight update rule always guarantee the convergence to the optimal solution [eqn: {under{w}} ^{*}]? (yes or no).  If not, under what condition does this weight update rule guarantee the convergence to [eqn: {under{w}} ^{*}]?

(b) Show that the convergence step is finite under the condition of (a).