Learning From Data – A Short Course: Exercise 1.3

Page 8:

The weight update rule in (1.3) has the nice interpretation that it moves in the direction of classifying $x(t)$ correctly.

(a) Show that $y(t)w^{T}(t)x(t) < 0$ . [Hint: x(t) is misclassified by $w(t)$ .]

Because $x(t)$ is misclassified by $w(t)$ so:

$y(t) = + 1$ : $sign(w^{T}(t)x(t)) = - 1 \Leftrightarrow w^{T}(t)x(t) < 0$ . Hence: $y(t)w^{T}(t)x(t) < 0$ .
$y(t) = - 1$ : $sign(w^{T}(t)x(t)) = + 1 \Leftrightarrow w^{T}(t)x(t) > 0$ . Hence: $y(t)w^{T}(t)x(t) < 0$ .

So: $y(t)w^{T}(t)x(t) < 0$ .

(b) Show that $y(t)w^{T}(t + 1)x(t) > y(t)w^{T}(t)x(t)$ . [Hint: Use (1.3).]

My solution for (b) is wrong. Please see: http://problemania.org/wiki/index.php?title=%E3%80%8ALearning_from_Data_-_A_Short_Course%E3%80%8B_Exercise_1.3:_Iterative_perceptron_learning_algorithm (thanks Coleman).

$x(t)$ is misclassified by $w(t)$ so $y(t)w^{T}(t)x(t) < 0$ .

$w(t + 1)$ correcly classifies $x(t)$ so $y(t)w^{T}(t)x(t) > 0$ (the argument is much alike above).

Hence: $y(t)w^{T}(t + 1)x(t) > y(t)w^{T}(t)x(t)$ .

(c) As far as classifying $x(t)$ is concerned, argue that the move from $w(t)$ to $w(t + 1)$ is a move “in the right direction”.

Check the slide 13 of Lecture 01. Remind yourself the formula: $A.B = \left \| A \right \| \left \| B \right \|\cos (\theta)$ where $\theta$ is the angle between $A$ and $B$ .

4 comments on “Learning From Data – A Short Course: Exercise 1.3”

Pingback: Learning From Data – A Short Course: Problem 1.3 | Nguyen Thuy Vy
Coleman says:

November 30, 2018 at 6:18 am

I think your argument for (b) is wrong. In details, “w(t + 1) is correctly classified” cannot be guaranteed.

Reply
Coleman says:

November 30, 2018 at 6:18 am

http://problemania.org/wiki/index.php?title=%E3%80%8ALearning_from_Data_-_A_Short_Course%E3%80%8B_Exercise_1.3:_Iterative_perceptron_learning_algorithm

I think the above website lists the correct argument.

Reply
1. Vy Nguyen says:
  
  January 20, 2019 at 11:23 am
  
  Thank you. You are correct. I misinterpreted the learning algorithm.
  
  Reply

Leave a Reply Cancel reply