Consider the two-dimensional AND dataset D that contains the following 4 examples with binary labels D...

 

Transcribed Image Text:

Consider the two-dimensional AND dataset D that contains the following 4 examples with binary labels D = {(x1,t1), (x2, t2), (X3, t3), (x4, t4)} = {([0,0], -1), ([1, 1], +1), ([0, 1], 1), ([1,0], -1)}, i.e., the truth table of the logical AND function. Φι $2 t 0 0 -1 0 1 -1 1 0 -1 1 1 +1 (a) Prove that D is linearly separable. • Do not forget to add the bias feature 0 = 1 to each example. (b) (*) Prove that the Perceptron algorithm makes at most 51 mistakes when trained on this dataset before it converges. • Hint: Use u = [-1.5, 1, 1]/√4.25 in Theorem 1 (Block, Novikoff) from this paper that proves the Perceptron convergence property. [Bonus, 10p] Find a different vector u that results in a tighter bound at (b) above, i.e. a smaller number of mistakes. (c) [Bonus, 5p] Let u and v be two vectors such that ||v|| = 1. Prove that ||u|| > uTv. Consider the two-dimensional AND dataset D that contains the following 4 examples with binary labels D = {(x1,t1), (x2, t2), (X3, t3), (x4, t4)} = {([0,0], -1), ([1, 1], +1), ([0, 1], 1), ([1,0], -1)}, i.e., the truth table of the logical AND function. Φι $2 t 0 0 -1 0 1 -1 1 0 -1 1 1 +1 (a) Prove that D is linearly separable. • Do not forget to add the bias feature 0 = 1 to each example. (b) (*) Prove that the Perceptron algorithm makes at most 51 mistakes when trained on this dataset before it converges. • Hint: Use u = [-1.5, 1, 1]/√4.25 in Theorem 1 (Block, Novikoff) from this paper that proves the Perceptron convergence property. [Bonus, 10p] Find a different vector u that results in a tighter bound at (b) above, i.e. a smaller number of mistakes. (c) [Bonus, 5p] Let u and v be two vectors such that ||v|| = 1. Prove that ||u|| > uTv.

Answer rating: 100% (QA)

a We must demonstrate the existence of a hyperplane that divides the positive cases from the negative examples in order to demonstrate that dataset D ... View the full answer