1
$\begingroup$

I see this example ON NN notes:

enter image description here

how this solution is achieved? is there any clear trick or usual step for solving this question quickly?I think the solution in the question be wrong. no idea anyway... please be aware that this is PhD entrance exam question and we should think the information is not enough in the question.

some idea tell us that 5, 5 is answer because for NN there is no difference on condition (1) and (2) in the question.

some idea tell us there is 3, 3 solution, but with complex neurons (this is not should used here in general, because this is general question even with lack of information)

some idea tell us there is at least 5, 5 solution because we cannot model with 3 nodes here... (not for first reason)

here one implementation of these structure in MATLAB for each case with 3 or 5 nodes and I think with $5$ we get the better result.

enter image description here $A) 4, 5$

$B) 5, 3$

$C) 5, 4$

$D) 5, 5$

$\endgroup$
1
2
+50
$\begingroup$

I believe the solutions should be a total of 3 neurons for each question. This is because two neurons are sufficient to calculate the lines that separate all the points. Then, an extra neuron can be used to decide to which class does a point belong to. Let's see why:

1st Question: Output of the neurons $=1$ or $=0$

First, we should note that both classes are separable if we use two lines:

enter image description here

Let's call these lines $l_1$ and $l_2$ (the order doesn't matter). Because of the fact that a line depends only on 2 parameters (let's call them $k$ and $c$), we know that the points $(x_1,x_2)$ that belong to these red and blue lines will satisfy: $$ l_1 = x_1 + k_1\,x_2 + c_1 = 0 \\ l_2 = x_1 + k_2\,x_2 + c_2 = 0$$

If a point $(x_1,x_2)$ doesn't belong to these red or blue lines (like all the points in the picture), then the above equalities would not hold.

In this situation, we have that the points lying at one side of the line will lead to a quantity $l_i > 0$, and the points to the other side will lead to a quantity $l_i < 0$ (with $l_i$ being $l_1$ or $l_2$).

Given this, we know that the first thing a neuron computes is the weighted sum of its inputs using its weights ($w_i$) and bias ($b_i$): $$ w_ix_1+w'_ix_2+b_i$$ This means that we can calculate the previous lines using two neurons. This can be achieved by setting $w_i = 1$, $w'_i=k_i$ and $b_i = c_i$. Just like in the next NN:

enter image description here

So, for example, the first neuron will be calculating the value of $l_1$ and the second neuron will be calculating the value of $l_2$.

As said earlier, all the points that need to be classified will have values of $l_i$ $>0$ or $<0$, so we can use an activation function that returns a neuron output of $1$ if $l_i>0$ and $0$ if $l_i<0$.

This way, we will end up with four possible combinations of outputs: $$ \begin{align} (0,0)\,\, \text{and} \,\, (1,1)\quad &\text{For one class}\\ (1,0)\,\, \text{and} \,\,(0,1)\quad &\text{For the other class} \end{align}$$ Thereby we can use this to finally know to which class does a point belong to. Note that the first class has these values repeated $\Rightarrow$ If we substract them we will end up with a value of $0$. However, if we substract the values of the second class, we would end up with $1$ or $-1$.

Hence we can use an activation function at the output neuron that outputs a value of $1$ when the substraction of its inputs is $0$ and that outputs a value of $0$ otherwise, achieving the correct classification. Thereby, our final NN would be like:

enter image description here

2nd Question: Output of the neurons $=1$ or $=-1$

The only thing that changes w.r.t. the previous reasoning is that the neurons will output $-1$ when $l_i<0$ (instead of outputing $0$). This way, we would have the next four cases with the hidden layer output: $$ \begin{align} (-1,-1)\,\, \text{and} \,\, (1,1)\quad &\text{For one class}\\ (1,-1)\,\, \text{and} \,\,(-1,1)\quad &\text{For the other class} \end{align}$$ Where again, the first class has these values repeated and the second class doesn't $\Rightarrow$ we can still use the previous NN to correctly classify the data.

Edit regarding the comments

The above explanation respects the constraints given by the question (neuron outputs $\in\{0,1\}$ or $\in\{-1,1\}$), but it also assumes that we are able to choose freely how is the activation function w.r.t. its inputs.

Below in the comments we have talked about using simpler activation functions, concretely perceptrons, which have the next behaviour: $$ \text{output} = \begin{cases} 1 \text{ if } \mathbf{w\cdot x}+ b > 0\\ 0 \text{ otherwise} \end{cases}$$

Perceptrons have already been considered above in the answer for the first two neurons, which are able to transform our initial data to XOR data.

Given this, it's important to note that 3 perceptrons are enough to model any logical function (as argued in posts like this one from Medium). This means that with the above reasoning we would need 3 more neurons, making a total of 5 neurons needed.

$\endgroup$
11
  • 3
    $\begingroup$ It seems that without bias the first problem would require 5 neurons for the intended answer... honestly it start to feel like a poorly worded homework question. $\endgroup$
    – lcrmorin
    Nov 28 '20 at 22:28
  • $\begingroup$ Exam (or interview) generally fall under the "homework" category... they are a bit frowned upon as it seems you expect us to explain something made by someone else. It appears challenging as it isn't very well defined (and that it is not a question that would appear in real life problems). Honestly, if you don't have to explain your answer, the best way to answer the question rapidly would be to get the intuition behind the "3" answer provided above and then rule out A, C, D, then go on to others questions. If a question is really bothering you ask the teacher after the test. $\endgroup$
    – lcrmorin
    Nov 29 '20 at 1:25
  • $\begingroup$ ps: as per the answer here : stackoverflow.com/questions/41712420/… the real answer seems to be 2. $\endgroup$
    – lcrmorin
    Nov 29 '20 at 1:30
  • $\begingroup$ You are completely shifting the question from something about intuition to solve a small problem in 4 minute to a more complex one about simulation... regarding simulation about xor, see this question stats.stackexchange.com/questions/213666/… and the associated answer and paper. When doing simulation you'll have to tackle the problem of weight initialisation. As is your simulation are not enough to conclude. $\endgroup$
    – lcrmorin
    Nov 30 '20 at 15:38
  • $\begingroup$ A McCulloch neuron is a perceptron neuron? If so, the answer is yes This is because any logical function can be built from 3 perceptrons, e.g. see this post from Medium. Note that with the first two neurons explained in the answer, we are able to transform our initial data to XOR data $\Rightarrow$ with 3 more neurons (5 in total) this XOR data can be modelled with perceptrons. $\endgroup$
    – Javier TG
    Dec 1 '20 at 21:39
0
$\begingroup$

This question is similar to this one and this one, but seems to be ill-posed. Either because it implies an unknown (undefined) way how the neurons process the inputs, or because the provided solution (5, 3) is wrong.

Concretely, usual neurons only sum their inputs and the bias and pass the sum through a step function. These are the typical neurons used in practice, so, without further information, educated reader would simply assume such neurons by default. Under this assumption, we need 5 neurons, no matter whether the step function produces {0, 1} or {-1, 1} as the output. See the left part of the figure below.

neural networks

The first layer simply defines two linear boundaries, u (blue) and v (red). In the next layer, we perform logical AND: $w = u \wedge v$ and $z = \bar{u} \wedge \bar{v}$. $w$ is 1 for the black triangles above the red and the blue line, and 0 otherwise. $z$ is 1 for the black triangles below the red and the blue line, and 0 otherwise. In the last (3rd) layer, we combine these by a logical OR: $y = w \vee z$ is 1 for the triangles, and 0 otherwise. I refrain from explaining how to implement AND, OR and NOT in a neural network. You can look up my explanation here.

However, if the neurons are allowed to multiply their inputs (something highly unusual in practice, but theoretically possible), then we can achieve the classification using only three neurons (right part of the figure above). The first layer again defines two linear boundaries, but now the output is +1 if a point is on one side of the boundary and -1 on the other. So, the black triangles above the two boundaries have $(u, v) = (+1, +1)$, while those below the both boundaries have $(u, v) = (-1, -1)$. In the second (last!) layer, we simply multiply the two: $y = u \cdot v$. $y$ is one for the triangles, and -1 otherwise.

If this was an exam question, I consider it highly unfair, because it requires highly unusual neurons and there is no hint to that. Actually, if you develop this idea further, you can come up with just a single neuron, one which combines the functionality of the three neurons in the right figure. There is nothing in the question suggesting that neurons cannot do that...

$\endgroup$

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.