1
$\begingroup$

I'm currently reading Mitchell's book for Machine Learning, and he just started gradient descent. There's one part that's really confusing me.

At one point, he gives this equation for the error of a perceptron over a set of training examples.

$$E(\vec{w})\equiv \frac12 \sum_{d \in D}(t_d-o_d)^2$$

$O_d$ is the actual output of $ \vec{W} \cdot \vec{X}$, where $ \vec{X}$ is the input vector and $\vec{W}$ is the weights vector.

$t_d$ is the target output, what we want to get.

The sum over all the $D$ means we sum over every single $\vec{X}$ we can input.

Okay, so far so good, I understand that.

However, he then gives this example:

enter image description here

But that is just not true!!!! That equation for the error does NOT give us a single minimum!!!

According to his previous rule, if we're considering the error for a single weight vector and a single training vector, the equation for the error would be:

$$E(\vec{w}) = \frac{1}{2} (t_d - (w_0 x_0 + w_1 x_1))^2$$

Which has an infinite number of minimums!!! Every time $(w_0 x_0 + w_1 x_1) = t_d$

I graphed it here to show you:

enter image description here

In that picture, $x$ and $y$ are the two rows of the weight vector $\vec{w}$.

Please help! I've been confused about this for the last three hours!

Thanks

Improve this question
$\endgroup$
2
$\begingroup$

You are right, the least square solution need not be unique as you have illustrated.

In general, we are trying to solve for $w$ in the system $$Xw=t$$

which of course need not even be consistent (meaning has a solution). In the event that it has a solution, the uniqueness is also not guaranteed if the matrix $X$ has non-zero vector in the nullspace of $X$.

For the least square solution, we are trying to minimize

$$\frac12(Xw-t)^T(Xw-t)$$

of which the minimal is attained when $$X^T(Xw-t)=0$$

that is $$X^TXw=X^Tt$$

and it is only unique when $X^TX$ has full column rank. However, note that uniqueness is not needed for gradient descent to work.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you Siong, I just liked your answer and I really appreciate it. However, I'm still really confused. I understand that if you have a whole matrix X of data points (which I'm assuming are the rows in the matrix X), the solution w may not even exist. However, note that in his example he's talking about a SINGLE vector x!!!! Not an entire matrix! And then he's saying the minimum is unique, but it's not...we have a free variable ! $\endgroup$ – joshuaronis Jan 23 '19 at 1:50
  • $\begingroup$ Wait a sec...nevermind, I think I read what he wrote wrong. Maybe he IS referring to an entire matrix X... $\endgroup$ – joshuaronis Jan 23 '19 at 1:51
  • $\begingroup$ Yep, I think he was! Now that I wrote it out that way in my graphing program I got a single local minimum...athough I'm still not sure why. My equation was this: $E = .5 *( (t_0 - (w_0 * x_0 + w_1 * x_1))^2 + (t_1 - (w_0 * x_0+ w_1* x_1))^2 + (t_2 - (w_0 * x_0 + w_1* x_1))^2 + (t_3 - (w_0 * x_0 + w_1* x_1))^2 )$ where each of the $x_s$ were different... why is it that now there's a global minimum, intuitively? Or is that not necessarilly true? $\endgroup$ – joshuaronis Jan 23 '19 at 1:54
  • 1
    $\begingroup$ because your matrix is of full column rank. Just looking at the first two terms of the summation, $.5/.3 \ne .4/.2$ and we can conclude that. $\endgroup$ – Siong Thye Goh Jan 23 '19 at 1:58
  • $\begingroup$ Thank you!!! Got you!!! Everythings so much easier when you look at it with Linear Algebra! This author hasn't used linear algebra once so far! Maybe I should start looking for a different book to self learn... $\endgroup$ – joshuaronis Jan 23 '19 at 2:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.