Confusion on Delta Rule and Error 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:



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:



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
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.