0
$\begingroup$

Given the four points $(x_1,x_2) = (0,0),(1,0),(0,1),(1,1)$, corresponding class labels $(1,1,1,-1)$ and activation units $y = f_H (w_0+\sum_i x_i w_i )$ and

$f_H(\alpha)$ $\begin{cases} -1 ; \alpha < 0 \\ 1 ; \alpha \geq 0 \end{cases}$

We have to show by specifying parameters that the above dataset can be classified with a single activation unit.

Plotting the points, I can see that (this NAND function) is linearly separable - but i) how do I show analytically that the solution only requires one activation unit? Furthermore, the four equations for $w_0,w_1,w_2$ seem to be underdetermined ii) what would be the systematic approach by hand (I can find solutions just by random guessing, but...)?

Thank you

$\endgroup$
1
$\begingroup$

This seems like a class/homework question (please add the self-study tag if that's the case), so I'll give a hint.

It looks like you're using the term 'activation unit' to mean output unit. Any binary classification problem can be solved with a single binary output unit; having only one of them isn't a restriction on the network. Rather, the restriction comes from the network being single layer, with a linear activation function. This means the network will only be able to achieve perfect accuracy on problems that are linearly separable.

As you've noticed, this problem is indeed linearly separable. There are uncountably many choices of parameters that will correctly classify your data points. But, to show existence, all you have to do is write down one of them. One strategy is to think about the problem geometrically. The decision boundary is a hyperplane because the network is a linear classifier; the output simply says which side of the hyperplane the input falls on. From your equations, we can see that the class is 1 if and only if $\vec{x} \cdot \vec{w} + w_0 \ge 0$. The decision boundary is $\vec{x} \cdot \vec{w} + w_0 = 0$. This is the equation for a hyperplane. The weights point in the direction of the hyperplane's normal vector. Adjusting the bias term shifts the hyperplane back and forth along this direction. The input is 2d, so it's easy to draw things out. Draw some line (i.e. 1d hyperplane) that separates the points. The equation for the decision boundary says how the line corresponds to network parameters.

$\endgroup$
  • $\begingroup$ Thanks! Self-study but not homework. Anyway: "Any binary classification problem can be solved with a single binary output unit" -- The XOR problem is a classic counterexample...- or am I misunderstanding you? With one equation being $w_0 \geq 0$ and another being $0>w_0+w_1+w_2$ I have chosen $w_0=3,w_1,w_2=−2$. Then this would translate geometrically to: $−2x_1−2x_2+3=0<=>x_2=\frac{3}{2}−x_1$, hence in my case intercept 3/2 and slope -1..? Is this correct? But then the decision surface is at -3/2 and not at 0? $\endgroup$ – Pegah Jul 30 '17 at 9:53
  • 1
    $\begingroup$ Sure, hope it helps. XOR is a classic example of a problem that linear classifiers can't solve (famously applied to perceptrons). Having a single output unit doesn't imply linearity. For example, multilayer networks with nonlinear activation functions can have extremely complex, nonlinear decision boundries, even with a single output unit. Yep, your solution looks correct. Not sure I understand your question about the decision boundary being at -3/2, can you say more? Your equation for it is right. $\endgroup$ – user20160 Jul 30 '17 at 10:07
  • $\begingroup$ Thank you very much:) I understand what you mean regarding single output unit, seems to me that this question was put a bit weirdly in the material I am going through (but I guess they equate single output unit with single layer then?) So, since $f_H$ decides on the output depending on its input being either negative or non-negative, I thought that this would imply that the decision surface goes through the origin, but I see now that it is shifted by the bias $w_0$ - ..? I have the same question for the "OR"-function, where I get a contradiction in my solution - should I write another post? $\endgroup$ – Pegah Jul 30 '17 at 10:14
  • 1
    $\begingroup$ Yes, the bias term shifts the decision boundary back and forth along the normal vector. Regarding the OR question, you could edit this question and append it to the bottom if it's related, or you could ask a new question; either way is fine. $\endgroup$ – user20160 Jul 30 '17 at 22:46
  • $\begingroup$ Opened a new post for another NN, would appreciate an answer stats.stackexchange.com/questions/295251/… $\endgroup$ – Pegah Jul 31 '17 at 7:55

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.