Discriminative Learning

Linear Classifiers

Generative Classifier

1. Learn CCDs from data: $p(x|y)$
2. BDT to get decision rule $p(y|x)\to g(x)$

Data used in step 1, decision is secondary.

• Density estimation is an ill-posed problem (difficult)
  • which density to use?

Vapnik's advice

when solving a given problem, try to avoid solving a more difficult problem as an intermediate step.

Solve for decision rule directly

Linear Classifier (binary)

• input: $X\in {\mathbb{R}}^d$
• output: $y\in +1,-1$
• find a linear function: $f(x)=w^{T}x,w\in {\mathbb{R}}^d$
  • $w$ separate input space into 2 halp-spaces
  • $w$ points to into the pos-space
  • $f(x)=0$ is the dec boundary

Decision Rule

$$g=\mathrm{sgn}(f(x))=\{\begin{array}{ll}+1,& f(x)>0\\ -1,& f(x)<0\end{array}$$

bias term can be included in $w$

f(\tilde{x}) = \tilde{w}\tilde{x}= \begin{bmatrix} w \\ b \\ \end{bmatrix} \begin{bmatrix} x \\ 1 \end{bmatrix} \= w^{T}x+b

Training Set $D=x\_i,y\_i\_{i=1}^n=X,y$

Given a $w$:

• $y\_i(w^{T}x\_i)>0⟹$ correctly classified $(x\_i,y\_i)$
• $y\_i(w^{T}x)<0⟹$ misclassified $(x\_i,y\_i)$

Idea case: 0-1 loss failed because $f(x)=\{\begin{array}{llc}0,& x>01,& x<0\end{array}$ has only 0 or undefined gradient.

$$w\text{*}=\mathrm{argmax}\_w\sum \_{i=1}^n$$

Least Squares Classification (Label Regression)

$$\begin{array}{rl}\hat{w}& =\mathrm{argmin}\_w\sum \_{i=1}^n(y\_i-w^{T}x\_i{)}^2\\ & =(X{X}^T{)}^{-1}Xy\end{array}$$

FLD is a version of LSC

Perceptron

Rosenblatt 1962

criteria: only look at misclassified points

M = set of misclassified points = $i|y\_i{w}^{T}x\_i<0$

loss function, larger loss for for misclassified points far from boundary:

$$E(w)=\sum \_i\in M-y\_i{w}^{T}x\_i$$

Perceptron Algorithm: $w^{\text{*}}=\mathrm{argmin}\_wE(w)$

look at one sample at a time and minimize (gradient descent)

$$w\_t+1=w\_t+\eta y\_ix\_i$$

it’s now called stochastic gradient descent, SGD

How to set the learning rate $\eta$

• rotate $w$ towards the misclassified point
• length of $w$ increases in each iteration, each update has less effect than prev

Rosenblatt proved SGD converges in ${\left(\frac{R}{\gamma }\right)}^2$ iterations if the data is linearly separate $R=\max \_i||X\_i||$

$\gamma$: for $||\hat{w}||=1$, $\forall i,y\_i\hat{w}x\_i>\gamma$ $\hat{w}$: the optimal unit weight vector that perfectly separates the two classes with the maximum possible margin.

• many possible solution, based on initialization
• does not converge if data is not linearly separable.

Logistic Regression

(probabilistic Approach)

Binary class: $y\in 0,1$

PS6-7: when the CCD are Gaussian, $p(x|y)=N(x;\mu \_y,\Sigma \_y)$, the posterior is $p(y|x)$ is a sigmoid function

$$p(y=1|x)=\frac{1}{1+e^{-f(x)}}=\sigma (f(x))$$

where f(x) is linear

Sigmoid:

$$\sigma (z)=\frac{1}{1+e^{-z}}$$

with BDR, $f(x)$ was determined by CCD. Now we directly learn $f(x)$

linear func: $f(x)=w^{T}x$ prob:

$$\begin{array}{rl}p(y=1|x)& =\sigma (w^{T}x)=\pi \\ & =\frac{1}{1+e^{-w^{T}x}}\end{array}$$

Decision Rule:

$$\hat{y}=\{\begin{array}{ll}1,& p(y=1||x)>\frac{1}{2},\text{or }{w}^{T}x>0\\ 0,& \text{otherwise}\end{array}$$

Look at # parameters

• BDR-Gauss: $O(d^2)$
• Logistic Regression: $O(d)$, less likely to overfit.

Learning: parameter estimation

let $\pi \_i=\sigma (w^{T}x\_i)$ Bernoulli likelihood: $p(y\_i|x\_i,w)=\pi \_i^{y\_i}(1-\pi \_i{)}^{1-y\_i}$ Data log-likelihood:

$$l(w)=\sum y\_i\ln \pi \_i+(1-y\_i)\ln (1-\pi \_i)$$

MLE:

$$\begin{array}{rl}\hat{w}& =\mathrm{argmax}\_wl(w)\\ & =\mathrm{argmin}\_w\sum \_{i=1}^n\underbrace{-y\_i\log \pi \_i-(1-y\_i)\log (1-\pi \_i)}\_\text{Loss: Binary Cross Entropy}\end{array}$$

Find zero-crossings of gradient: Newton-Raphson Method

$$w^{(\text{new})}=w^{(\text{old})}-\text{[}\underset{\text{Hessian}}{\underbrace{{\nabla }^{2}l(w)}}{]}^{-1}(\underset{\text{gradient}}{\underbrace{\nabla l(w)}})$$ $$\begin{array}{rlr}& & \\ w^{(\text{new})}& =(XR{X}^T{)}^{-1}XRz& \\ R& =\mathrm{diag}(\pi \_i(1-\pi \_i),\dots ,\pi \_n(1-\pi \_n))& \text{weights}\\ z& =X^T{w}^{(old)}-R^{-1}(\pi -y)& \end{array}$$

weighted lesat squares: weights are $R$, target is $z$

R: weights depend on $w\_i$, weight higher on unconfident predictions z: $f^{old}w$ - error between pred $\pi \_i$ and $y\_i$ target depends on $w$

IRLS, IRWLS: iterative reweighted least squares

Comparison of Error (loss) functions

all have the form:

$$\hat{w}=\mathrm{argmin}\_w\underbrace{\sum \_{i=1}^{n}L(f(x\_i),y\_i)}\_\text{empirical risk}$$

“empirical risk minimization” - reduce the training error.

let $z\_i=y\_i{w}^{T}x\_i$

Ideal 0-1 loss

$$L=\{\begin{array}{llc}0,& z\_i>0& \\ 1,& z\_i<0& \end{array}$$

LSC:

$$L=(z\_i-1{)}^2$$

penalizing too correct answers

Perceptron:

$$L=\max (0,-Z\_i)$$

Logistic Regression:

$$L=\frac{1}{\log (z)}\log (1+e^{-z\_i})$$

some loss for correctly classified points: the effect is to push. the boundary away from the nearby points.

Loss for LSC & LR are convex approx to 0-1 loss