Perceptron

Topics

• Mistake Bound Theorem
• Voted Perceptron

$H=\left\{h|h:\mathbb{X}\to \mathbb{Y},h(\mathbf{x})=\text{sign}(a)\right\}$

• The set of hypotheses $h(x)$ we hope to be $\hat{y}$, or the function that can predict the labels of a data point
• $a$ is the activation function

Margin

$$\text{Margin}(\mathcal{D},w)=\{\begin{array}{ll}{\text{min}}_{(x,y)\in \mathcal{D}}\frac{y_n{w}^T{x}_n}{\Vert w\Vert }& \text{for separating hyperplane }w\\ -\infty & \text{else}\end{array}$$

• The margin of a hyperplane (when varying $w$) is the minimum distance between the given hyperplane and a sample
• If there’s no hyperplane, it’s $-\infty$

$\text{Margin}(\mathcal{D})={\text{max}}_w\text{Margin}(\mathcal{D},w)$

• The margin of a dataset is the margin of the hyperplane with the greatest margin

Training

• PerceptronTrain(data = N samples/instances = $\left\{(x_1,y_1),\dots ,(x_n,y_n)\right\}$, maxIter)
  • for i = 1 through to maxIter
    • Potentially shuffle data here
    • for (x, y) in data
      • $a:=w^{{}^{\top }}x$
      • if $ay\le 0$ (i.e. the data is misclassified) then
        • $w=w+yx$
  • return $w$
• AveragedPerceptronTrain(data = N samples/instances = $\left\{(x_1,y_1),\dots ,(x_n,y_n)\right\}$, maxIter)
  • for i = 1 through to maxIter11
    • Potentially shuffle here
    • for (x, y) in data
      • $a:=w^{{}^{\top }}x$
      • if $ay\le 0$ (i.e. the data is misclassified) then
        • $w=w+yx$
          • This effectively moves the boundary plane defined by $w$ toward classifying more correct examples
      • $\mu =\mu +w$
  • return $\mu$

$O(dn)$