1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Fatemeh Asgarinejad Jul 11 at 1:47
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – czlsws Jul 11 at 3:12
  • $\begingroup$ 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) $\endgroup$ – Fatemeh Asgarinejad Jul 11 at 3:19

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.