Linear Classifier

Definition:

• $\underset{\text{Objective fn}}{\underbrace{\arg \underset{w,b}{\min }L(w,b)}}=\underset{\text{Loss fn}}{\underbrace{\arg \underset{w,b}{\min }\sum _{n=1}^N\Vert [y_n(w^T{x}_n+b)<0]}}+\underset{\text{Regulizer}}{\underbrace{\lambda R(w,b)}}$

The 0-1 loss:

• Small changes in in w, b can lead to big changes in the loss values
• 0-1 loss is non-smooth, non-convex.
• → Approximate 0-1 loss with surrogate loss functions, example b=0:
  • Hinge loss: $[1-y_n{w}^T{x}_n{]}_{+}=\max (0,1-y_n{w}^{T}x)$
  • Log loss: $\log (1+\exp (-y_n{w}^{T}x))$
  • Exponential loss: $\exp (-y_n{w}^{T}x$)
  • 
• Problem: The 0-1 loss above is NP-hard to optimize exactly/approximately in general
• Solution: Use surrogate loss that is somehow related to 0-1 loss
  • Different loss function approximations and regularizers lead to specific algorithms

The regularization term:

• find simple solutions (inductive bias. Occam’s Razor:)
• Ideally, we want most entries of $w$ to be zero, so prediction depends only on a small number of features
• Formally, we want to formalize $R^{cnt}(w,b)={\sum }_{d=1}^D\Vert [w_d\ne 0]$
• Again, it’s NP-hard ⇒ approximation
  • e.g., we encourage w to be small
• Norm-based regularizers:
  • $||w|{|}_2^2={\sum }_{d=1}^D{w}_d^2$
  • $||w|{|}_1={\sum }_{d=1}^D{w}_d$
  • $||w|{|}_p=({\sum }_{d=1}^D{w}_d^p{)}^{1/p}$
  • $l_p$ norms can be used as regularizers
  • Smaller $p$ favors sparse vectors $w$
    • i.e., most entries of w are close to or equal to 0
  • $l_2$ norm: convex, smooth, easy to optimize
  • $l_1$ norm: encourage sparse w, convex, but not smooth at axis points
  • $l_p,p<1$ norm: become non-convex and hard to optimize

Optimize with Gradient Descent:

• Idea: take iterative steps to update parameters in the direction of the gradient
• GradientDescent(F,k,${\eta }_1$,…):
  • $z^{(0)}\leftarrow [0,0,0,\mathrm{0...},0]$
  • for k=1,…,K do:
    • $g^k\leftarrow {\Delta }_{z}F{|}_{z^{(k-1)}}$ // compute gradient at current location
    • $z^{(k)}\leftarrow z^{(k-1)}-{\eta }^{(k)}{g}^{(k)}$ // take a step down the gradient
  • end for
  • return $z^{(K)}$
• where $F$ is function, $K$ is nb of steps and ${\eta }_1$ is step size (learning rate)
• 
• when to stop?
  • When the gradient gets close to zero
  • When the objective stop changing much
  • When the parameters stop changing much
  • Early
  • When performance on held-out validation set plateaus
• Step size: usually start with large steps and get smaller
• Subgradient:
  • Problem: some objective functions are not differentiable everywhere, ex: Hinge loss, l1 norm
  • Solution: subgradient optimization (differentiate by parts), they are only non differentiable at the end and probability at 2 ends are 0
  • Subgradient of hinge loss:
  • For a given example $n$
    • ${\partial }_w\max \left\{0,1-y_n\left(\mathbf{w}\cdot x_n+b\right)\right\}$
    • $={\partial }_w\{\begin{array}{ll}0& \text{ if }{y}_n\left(\mathbf{w}\cdot {\mathbf{x}}_n+b\right)>1\\ y_n\left(\mathbf{w}\cdot {\mathbf{x}}_n+b\right)& \text{ otherwise }\end{array}$
    • $=\{\begin{array}{ll}0& \text{ if }{y}_n\left(\mathbf{w}\cdot {\mathbf{x}}_n+b\right)>1\\ -y_n{\mathbf{x}}_n& \text{ otherwise }\end{array}$
  • HingeRegularizedGD(D, $\lambda$, MaxIter)
    • $w\leftarrow ⟨o,o,\dots o⟩,b\leftarrow o//$ initialize weights and bias
    • for iter $=1\dots$ MaxIter do
      • $g\leftarrow ⟨0,0,\dots o⟩,g\leftarrow o//$ initialize gradient of weights and bias
      • for all $(x,y)\in \mathbf{D}$ do
        • if $y(w\cdot x+b)\le 1$ then
          • $g\leftarrow g+yx$ // update weight gradient
          • $g\leftarrow g+y$ // update bias derivative
        • end if
      • end for
        • $g\leftarrow g-\lambda w//$ add in regularization term
        • $w\leftarrow w+\eta g//$ update weights
        • $b\leftarrow b+\eta g$ // update bias
      • end for
      • return $w,b$

Binary Classification with Linear Models