1
$\begingroup$

I'm reading this book chapter, and I'm looking at the questions on the last page. Can someone explain question 2 on the last page to me, or show me an example of a solution so I can understand it?

The question is:

Consider a simple perceptron with $n$ bipolar inputs and threshold $\theta = 0$. Restrict each of the weights to have the value $−1$ or $1$. Give the smallest upper bound you can find for the number of functions from $\{−1, 1 \}^n$ to $\{−1, 1\}$ which are computable by this perceptron. Prove that the upper bound is sharp, i.e., that all functions are different.

What I understand:

  1. A perceptron is a very simple network with $n$ input nodes, a weight assigned to each input nodes, which are then summed to be above/not above a threshold ($\theta$).

  2. In this example, there are $n$ input nodes, and the value of each input node is either $−1$ or $1$. And we want to map them to outputs of either $−1$ or $1$.

What I'm confused about: Is it asking how many different ways can you map input values of $\{−1, 1\}$ to $\{−1, 1\}$ output?

For example, is the answer, where each tuple in this list is input1, input2 and label, as described above:

$$[(1,1,1), (1,1,-1), (-1,1,-1), (-1,1,1), (1,-1,1), (1,-1,-1), (-1,-1,-1)]$$

Improve this question
$\endgroup$
2
  • $\begingroup$ Maybe you should explain exactly which part of the exercise you don't really understand what you understand about perceptrons. Do you know what an upper bound is? Please, edit this post to clarify what you don't really understand about the exercise. In any case, as far as I understand, you need to state something like this "A perceptron with such a threshold can learn at most $m$ functions of the form $f: \{-1, 1\}^n \rightarrow \{-1, 1\}$". So, the inputs are vectors of $n$ dimensions, where each element can either be $-1$ or $1$ and the outputs are either $-1$ or $1$. $\endgroup$
    – nbro
    Jan 2, 2021 at 23:28
  • $\begingroup$ Of course, you cannot just state it without knowing what you're talking about, but you need to say why $m$ is what you say. So, an upper bound would be infinity, but that's not the smallest upper bound. Note that an upper bound is just a number that is greater than or equal to the number you're interested in (in this case, the number of functions that such a perceptron can compute). So, the number that you give (i.e. your solution) cannot be smaller than the actual number of functions that the perceptron can compute (because that would not be an upper bound). $\endgroup$
    – nbro
    Jan 2, 2021 at 23:28

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .