Perceptron

• Choose some initial value for weights: $w_1$
• Initialize counter $m=1$
• For a certain number of iterations:
  • Go over every example $(x_i, y_i)$
  • If example is classified correctly: $y_i(w_m^Tx_i) > 0$, do nothing
  • If example is not classified correctly: $y_i(w_m^Tx_i) \leq 0$:
    • $w_{new} = w_{old} + \eta y_ix_i$

$w_{m+1} = w_{m} + \eta y_i x_i$

$y_i ((w_m+\eta y_i x_i)^T x_i))$

$= y_i w_m^T x_i + \eta y_i^2 x_i^Tx_i$

Does not guarantee that value is greater than 0, but will always add a positive value (moving in right direction).

Linear Separability

Let $X_0 \in \mathbb{R}^n, X_1 \in \mathbb{R}^n$. $X_0, X_1$ are linearly separable if for some vector $w$, all points in $X_0$ have $w^T x_0 > 0$ and all points in $X_1$ have $w^T x_1 < 0$ or vice-versa.

Convergence

• The perception will never converge if not linearly separable
• Must need a maximum iteration
• Want to find the best separator (NP hard)

Alternatives

• Voted, average perceptron
• Choose some $w_1$ as the weights
• Initialize counter $m=1$, and cost function $c_1 = 1$
• Go through each example, if classified correctly, increment cost function, if not, reset cost function