# What is the hypothesis space used by this AND gate Perceptron?

Per this post

The hypothesis space used by a machine learning system is the set of all hypotheses that might possibly be returned by it.

Per this post, the Perceptron algorithm makes prediction

$$\begin{equation} \hat y = \begin{cases} 1 & wx+b >= 0\\ 0 & wx+b<0 \end{cases} \end{equation}$$

we can conclude that the model to achieve an AND gate, using the Perceptron algorithm is

$$x_1 + x_2 – 1.5$$

In this case, what is the hypothesis space used by this AND gate Perceptron?

• As far as I understand, the expression $x_1 + x_2 - 1.5$ which is a model that is capable of mapping inputs to outputs is a hypothesis. There might be more models that can do this action, the whole models are called hypothesis space. – Fatemeh Asgarinejad Jul 11 '19 at 1:47

As far as I understand:

A hypothesis is a model which is capable of predicting outputs from inputs, hence the $$x_1 + x_2 - 1.5$$ is a hypothesis but not the only one. The whole models that have the same capability are regarded as hypothesis space.

We know that in AND gate:

     x1       x2     output
|---------|--------|--------|
|     0   |    0   |    0   |
|     0   |    1   |    0   |
|     1   |    0   |    0   |
|     1   |    1   |    1   |
|---------------------------|


and we have $$w .\cdot x + b$$, based on which, either $$0$$ or $$1$$ turns out as output. $$w \cdot x + b$$ $$w_1 \cdot x_1 + w_2 \cdot x_2 + b$$

trying all the inputs in this expression:

$$w_1 \cdot 0 + w_2 \cdot 0 + b <= 0$$ (because the output should be 0) $$b < 0$$

$$w_1 \cdot 0 + w_2 \cdot 1 + b <= 0$$ ---> $$w_2 + b <= 0$$ So $$w_1 < |b|$$

$$w_1 \cdot 1 + w_2 \cdot 0 + b <= 0$$ ---> $$w_1 + b <= 0$$ So $$w_2 < |b|$$

$$w_1 \cdot 1 + w_2 \cdot 1 + b > 0$$ ---> $$w_1 + w_2 + b > 0$$

Firstly, we initialize the weights and bias parameters and then if needed, change them.

Here, since $$b < 0$$ we set it as $$-1$$

Since $$w_1 < |b|$$, $$w_2 < |b|$$ and weights are not negative, we set them as 1. So we would have:

$$w_1 \cdot 0 + w_2 \cdot 0 + b = -1 < 0$$ is right, returns 0 because is negative.

$$w_1 \cdot 0 + w_2 \cdot 1 + b = w_2 + b = 1 - 1 = 0$$ wrong, it returns 1 while it should return 0

$$w_1 \cdot 1 + w_2 \cdot 0 + b <= 0$$ ---> $$w_1 + b <= 0$$ So $$w_2 < |b|$$ wrong, it returns 1 while it should return 0

$$w_1 \cdot 1 + w_2 \cdot 1 + b > 0$$ ---> $$w_1 + w_2 + b > 0$$

So we set b for a smaller value like -1.5 (Note), then all the expressions would work appropriately. Hence $$x_1 + x_2 - 1.5$$ is a hypothesis for this problem.

Note: we know that in using perceptron algorithm, when reaching at any point that is not following the current model, weights and bias are updated as follows:

w = w + yx
b = b + y


Here, in the source that you referred to, maybe for simplicity they haven't done so and have just found a sample of a plausible model (hypothesis)

The other hypothesizes should follow the previously mentioned rules, thereby, $$x_1 + x_2 - 2$$ can also be another hypothesis for this problem, etc.

• thanks for your answer. in this specific case, what is exactly the hypothesis space? is it something like $b_{min} < b < b_{max}, \quad and \quad w_{min} < w < w_{max}$. then what is the values of $b_{min}, b_{max}, w_{min}, w_{max}$ – czlsws Jul 11 '19 at 3:12
• Here the hypothesis space is all forms of w.x+b where are capable of conveying the inputs to outputs correctly. and based on the expressions like b<0 and w1 < |b| we see that bs and ws are correlated. although, If we follow the perceptron algorithm we would see that b is added by y whenever the condition of the update is true. y here is 0 or 1, hence b equals b + n*1 (n is the number of required updates) for w also, regarding w = w+yx, seemingly, here it can be at most plus 1 because yx is always 0 but in case (1,1) – Fatemeh Asgarinejad Jul 11 '19 at 3:19