Perceptron Training

Definition:

• Properties:
  • Online:
    • Look at one example at a time, and update the model as soon as we make an error
    • Compared to batch algorithms that update parameters after seeing the entire training dataset
  • Error-driven: We only update parameters if we make an error.
• Practical considerations:
  • Order of training examples matter, random is better
  • Early stopping: to avoid overfitting
  • Simple modifications dramatically improve performance: voting or averaging
• Now hypothesis $h$ is a Hyperplane that best separate a linearly separable sample
  • the bias scalar $b$ can be encoded in by adding extra dimension?

Perceptron prediction algorithm:

• $\text{PerceptronTest}(w_0,w_1,...,w_D,b,x):$
  • $a\leftarrow {\sum }_{d=1}^D{w}_d{\hat{x}}_d+b$ //compute activation for the test example
  • return sign(a)
• Standard Perceptron training algorithm: $\text{PERCEPTRONTRAIN}(D,MaxIter)$
  • $w_d\leftarrow 0,foralld=\mathrm{1...}D$ // initialize weights
  • $b\leftarrow 0$ // initialize bias
  • for iter = 1…MaxIter do
    • for all (x,y) ∈ D do
      • $a\leftarrow {\sum }_{d=1}^D{w}_d\ast x_d+b$ // compute activation for this example
      • if $y\ast a\le 0$ then // if opposite sign
        • $w_d\leftarrow w_d+y\ast x_d$,for all d = 1…D // update weights
        • $b\leftarrow b+y$ // update bias
      • $endif$
    • end for
  • end for
  • return $w_0,w_1,...,w_D,b$
• Other variations that predict based on final + intermediate parameters:
  • Require to keep track of “survival time” of weight vectors?
  • The voted perceptron:
    • $\hat{y}=\text{sign}\left({\sum }_{k=1}^K{c}^{(k)}\text{sign}\right(w^{(k)}.\hat{x}+b^{(k)}\left)\right)$
  • The averaged perceptron:
    • $\hat{y}=\text{sign}\left({\sum }_{k=1}^K{c}^{(k)}\right(w^{(k)}.\hat{x}+b^{(k)}\left)\right)$
  • Averaged Perceptron with efficient decision:
    • combination of weighted sum of $w$ and weighed sum of bias
    • $\hat{y}=\text{sign}\left(\right({\sum }_{k=1}^K{c}^{(k)}{w}^{(k)}).\hat{x}+({\sum }_{k=1}^K{c}^{(k)}{b}^{(k)}\left)\right)$
• Sometimes perceptron cant converge

Convergence of perceptron:

• Theorem Block and Novikoff
• If a training dataset $D=\{(x^{(1)},y^{(1)},...,(x^{(N)},y^{(N)})\}$ is linearly separable with a margin $\gamma$ by a unit norm hyperplane $w_{\ast }(||w_{\ast }||=1)$ with $b=0$
• The perceptron training algorithm converges after $\frac{R^2}{{\gamma }^2}$ errors during training (assuming $||x||<R$)
• Margin of a dataset:
  • Distance between the separating hyperplane $(w,b)$ and the nearest point in dataset
  • $margin(D,w,b)=\{\begin{array}{ll}{\min }_{(x,y)\in D}y(w.x+b)& \text{if w separates }D\\ -\infty & \text{otherwise}\end{array}$?
  • We want the hyperplane to have largest attainable margin on D $margin(D)={\sup }_{w,b}margin(D,w,b)$
    • less margin of error
• Perceptron converges quickly when margin is large, slowly when margin is small
• Bound does not depend on number of training examples, nor on number of features
• Proof guarantees that perceptron converges, but not necessarily to the max margin separator (there are several possible $w_{\ast }$
• Practical Implications
  • Sensitive to noise: No convergence or accuracy guarantee if the data is not linearly separable due to noise
  • Linear separability in practice
    • Data may be linearly separable in practice
    • Especially when the number of features >> number of examples
  • Overfitting:
    • Early stopping and Averaging