Due Date: 7 Dec 2004 6:30pm
Turn-in procedure: Please email parag@cs.washington.edu before
class on Dec 7. Any of the Word,Postscript, PDF, HTML, or Plain text
formats should be fine.
Please use the subject "CSEP546: HW3 Submission", and in the text
part of the message include your name and student id.
You can also submit a hardcopy of your work at the beginning of
the class on Dec 7.
Notes: All homeworks are to be done
individually.
- Let the instance space be the rectangle {(x,y): 0 < x < 40, 0 < y < 30},
and let + and - represent positive and negative training examples,
respectively. Suppose you are given the following training set:
- Draw the Voronoi diagram corresponding to this training set,
using Euclidean distance.
- If this Voronoi diagram represents the true concept, and examples are
drawn with uniform probability from the rectangle {(x,y): 0 < x < 40,
0 < y < 30}, what is the probability of drawing a positive example?
- Suppose instances are of the form (x, y, z) (i.e, have three features),
and you have a training set composed of positive examples at
(0, 1, 0), (1, 0, 0), (0, 1, 1) and (1, 0, 1), and negative examples at
(0, 0, 0), (1, 1, 0), (0, 0, 1) and (1, 1, 1).
- Which features would the forward selection algorithm select for
a nearest-neighbor classifier, using Hamming distance and
leave-one-out accuracy as the evaluation measure?
- Which features would the backward elimination algorithm select?
- A decision stump is a decision tree with only one internal node.
Which algorithm has higher bias: a decision stump learner or a
perceptron? And which one has higher variance? Justify your answer.
(Assume that all attributes are either Boolean or numeric.)
- Mitchell 7.5.
- Han & Kamber 6.1.
|