Creating a single layer perceptron for the OR problem

Question

I am working on the following problem

Find the linear least squares unit weights for the `OR' problem, ie. $v_1^T = (0,0), v_2^T = (1,0), v_3^T = (0,1), v_4^T = (1,1)$ and $u_1 = 0, u_2 = u_3 = u_4 = 1$.

Here $v$ represent inputs and $u$ outputs. For problems like this I usually find a matrix $W$ (the weights) such that $$u_i=Wv_i \quad i=1,2,3,4$$ but I think it is obvious a matrix doesn't exist. my reasoning being that the problem is equivalent to finding the matrix $W = \begin{pmatrix} x_1 & x_2 \end{pmatrix} $ such that $$\begin{pmatrix} 0 & 1 & 1 & 1 \end{pmatrix} = \begin{pmatrix} x_1 & x_2 \end{pmatrix} \begin{pmatrix} 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \end{pmatrix}$$ And looking at the two middle columns of the left vector and right matrix we must have $x_1=x_2 =1$ but then we get $1 + 1 = 1$, a contradiction.

In a unit perceptron a function may be applied to the output, and a step function $$f(x) \begin{cases} 0 & x \leq 0 \\ 1 & x > 0 \end{cases}$$ would work here.

My question here is, is this correct? I wasn't quite sure if I am answering the right question. I am pretty sure $u_i = f(Wv_i)$ but I am not too familiar with what is meant by "linear least squares unit weights" in this context?

Answer 1

The fact that you mention linear least squares error seems to hint that they want you to use a completely linear model $u_i=Wv_i$ for your perceptron. In this case you won't get exact answers like $0$ and $1$; you will only get approximations with some amount of error.

That said, I don't think a linear model makes sense for this problem, since it is a classification problem with two classes. Using a non-linear step-like function $f$ before the final output of a perceptron classifier is a pretty standard thing to do, so I see no problem with using $u_i=f(Wv_i)$.

Assuming you can use $f$, using the weights $x_1 = x_2 = 1$ as you mentioned solve this problem exactly with zero error.