Body: <p>I'm reading <a href="https://page.mi.fu-berlin.de/rojas/neural/chapter/K3.pdf" rel="nofollow noreferrer">this</a> 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?</p>
  <p>The question is:</p>
  <blockquote>
  <p>Consider a simple perceptron with <span class="math-container">$n$</span> bipolar inputs and threshold <span class="math-container">$\theta = 0$</span>. Restrict each of the weights to have the value <span class="math-container">$−1$</span> or <span class="math-container">$1$</span>. Give the smallest upper bound you can find for the number of functions from <span class="math-container">$\{−1, 1 \}^n$</span> to <span class="math-container">$\{−1, 1\}$</span> which are computable by this perceptron. Prove that the upper bound is sharp, i.e., that all functions are different.</p>
  </blockquote>
  <p>What I understand:</p>
  <ol>
  <li><p>A perceptron is a very simple network with <span class="math-container">$n$</span> input nodes, a weight assigned to each input nodes, which are then summed to be above/not above a threshold (<span class="math-container">$\theta$</span>).</p>
  </li>
  <li><p>In this example, there are <span class="math-container">$n$</span> input nodes, and the value of each input node is either <span class="math-container">$−1$</span> or <span class="math-container">$1$</span>. And we want to map them to outputs of either <span class="math-container">$−1$</span> or <span class="math-container">$1$</span>.</p>
  </li>
  </ol>
  <p>What I'm confused about:
  Is it asking how many different ways can you map input values of <span class="math-container">$\{−1, 1\}$</span> to <span class="math-container">$\{−1, 1\}$</span> output?</p>
  <p>For example, is the answer, where each tuple in this list is input1, input2 and label, as described above:</p>
  <p><span class="math-container">$$[(1,1,1), (1,1,-1), (-1,1,-1), (-1,1,1), (1,-1,1), (1,-1,-1), (-1,-1,-1)]$$</span></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-02T23:28:03.410Z
Comments.Text: 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$.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-02T23:28:52.300Z
Comments.Text: 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).
Comments.UserDisplayName: nbro
Tags: <machine-learning><function-approximation><perceptron>
Title: What is the smallest upper bound for a number of functions in a range that are computable by a perceptron?
UserDisplayName: Slowat_Kela
ThreadText: # What is the smallest upper bound for a number of functions in a range that are computable by a perceptron?
  
  (Asked by: username_0 on 2021-01-02)
  
  I'm reading [this](https://page.mi.fu-berlin.de/rojas/neural/chapter/K3.pdf) 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)]$$
  
  **Tags:** machine-learning, function-approximation, perceptron
  > **Comments:**
  > **username_1**: 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$.  
  > **username_1**: 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).  
  
  ---
  
  ## 0 answers
  
  