Linear classifier

Binary linear classifier

A binary linear classifiers is defined as follows

$$score=ww\cdot xx$$

where $xx$ is the feature vector we want to classify and $ww$ is the vector which the classifier thinks is important. It will returns the first class if the score is greater than zero, else the other class. If a data set is linearly inseparable a linear classifier often has a hard time of optimal learning.

Logistic regression

The name is somewhat confusing because it is a classifier. It is a linear classifier that gives probabilistic scores. To get probabilites we need to use a logistic or sigmoid function

$$P(\text{positive output}|xx)=\frac{1}{1+e^{-score}}$$ $$P(\text{negative output}|xx)=1-\frac{1}{1+e^{-score}}=\frac{1}{1+e^{score}}$$

In a linear model with probabilites we can train the model by selecting features that assign a high probability to the data. Therefore, we need to adjust $ww$ so that each our output label gets a high probability.

Formally this is defined by the likelihood function

$$\mathcal{L}(ww)=P(y_1|{xx}_1)\cdots P(y_m|{xx}_m)$$

which translate to

$$\mathcal{L}(ww)=\frac{1}{1+e^{-y_1\cdot (ww\cdot {xx}_1)}}\cdots \frac{1}{1+e^{-y_m\cdot (ww\cdot {xx}_m)}}$$

in our case. We can convert this to the log loss function by using log on each side.

Multiclass classification

Two main ideas

• break down the problem into simplier pieces and create a classifer for each piece
• adjust the model to handle multiclass directly

There are two approaches we can use to convert a multiclass problem to a binary problem

• one-versus-rest ^[1]

• one-versus-one ^[2]

Built in classifiers like the perceptron or logistic regression will to this autoamtically (one-versus-rest).

Instead of using the sigmoid we use the softmax function in the multiclass scenario.

$$P(y_i|xx)=\frac{e^{scor{e}_i}}{{\sum }_k{e}^{scor{e}_k}}$$

when training, instead of using the log loss we get the cross-entropy loss instead.

Linear regression

Similarly like the linear classifier, a linear regression model calculate its score like this

$$y=ww\cdot xx$$

where $xx$ is the encoded feature vector and $ww$ is the weights. The output $y$ is now numerical.

In linear-squares regression with the error function

$${ww}^{\ast }=\arg \underset{ww}{\min }\frac{1}{N}\sum _{i=1}^N(y_i-ww\cdot {xx}_i{)}^2$$

The error function finds the weight vector that minmizes the squared error over the training set. For each training instance we look at the predicted value and calculate the distance of it between the labeled value.

However this could be quite expensive which is why stochastic gradient descent is often used in practice. In stochastic gradient descent we consider just a single instance

$$f_i(ww)=(ww\cdot {xx}_i-y_i{)}^2$$

Thus, the gradient of the least squared loss with respect to $ww$ is

$$\nabla f_i(ww)=2\cdot (ww\cdot {xx}_i-y_i)\cdot {xx}_i$$

Keeping the model simple

We can keep the model simple by adding a regularization term to the linear regression model. By adding this term we can keep the weights small. For example, by penalizing the squared length we achieve

$$\Vert ww{\Vert }^2=w_1\cdot w_1+\dots +w_n\cdot w_n=ww\cdot ww$$

which is called a $L_2$ regularizer . Another common regularizer is

$$\Vert ww\Vert =|w_1|+\dots +|w_n|$$

which is aclled a $L_1$ regularizer.

If we combine the loss function with the regularizer we get

$$\frac{1}{N}\sum _{i=1}^N\text{Loss}(ww,{xx}_i,y_i)+\alpha \cdot \text{Regularizer}(ww)$$

Bias

A linear classifier could be expressed with a bias term and will in such cases look like this

$$score=ww\cdot xx+b$$

where $b$ is the bias (often also called offset or intercept).

Different models

Classifiers

• perceptron
• logistic regression

Regressors

• linear regression ^[3] (no regularization)

• ridge ^[4] (the combination of least squares loss with $L_2$ regularization)

• lasso ^[5] (the combination of least squares loss with $L_1$ regularization)

• linear SVR ^[6]

References