<, which gives this method its name: **Logistic regression** or **logit**.
To determine the parameters $\beta$ and $\beta_0$, we first realize that the probability distribution of the two-class classifier is the [Bernoulli](https://en.wikipedia.org/wiki/Bernoulli_distribution), with $y_i\in\lbrace 0,1\rbrace$ being the outcomes of the binary trial:
$$
\mathcal{L}(\hat\beta) = \prod_i p(1\,|\, x_i)^{y_i} (1-p(1\,|\, x_i))^{1-y_i}.
$$
The log-likelihood is then
$$
\log\mathcal{L}(\beta, \beta_0)=\sum_i y_i (\beta^\top x_i +\beta_0)- \log\left( 1+\exp(\beta^\top x_i +\beta_0)\right),
$$
which one can find the maximum of by various gradient techniques, the traditional one is called [iteratively reweighted least squares (IRLS)](https://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares).
At this point, it's useful to understand the relation of regression and classification we've been exploiting here. The logit classifier is equivalent to a regression problem for
$$
y = \begin{cases}1 & \beta^\top x_i +\beta_0 + \epsilon > 0\\0&\text{else}\end{cases}
$$
where the error term $\epsilon$ follows the logistic distribution (if the standard normal distribution is used instead, it is the [probit model](https://en.wikipedia.org/wiki/Probit_model)). This is manifestly discriminative even though we have probabilistic forms of each class.
So, one might wonder how logit classifier differs from LDA. It's the Gaussian assumption in LDA, which is useful to learn the bulk properties of the classes by inferring the analytic PDF from all samples, but it's also more sensitive to outliers since they are expected to follow the Gaussian form, too.
### Support Vector classifier
And now we will make the linear boundary assumption fully discriminative. We will ignore the class distributions entirely and focus only on optimal separability by requiring that the hyperplane between two classes has a maximally wide margin as show in the image below, where the margin is labeled as **w**.
We therefore demand of the hyperplane to satisfy
$$
\max_{\beta, \beta_0:\lVert\beta\rVert=1}(w)\ \ \text{subject to}\ \forall i: y_i (\beta^\top x_i+\beta_0)\geq w.
$$
To simplify the formulation, I have changed the definition of the response variable to $y_i\in\lbrace-1,1\rbrace$. We can get rid of the constraint $\lVert\beta\rVert=1$ by redefining $\beta_0$ and requiring that $y_i(\beta^\top x_i+\beta_0)\geq w\lVert\beta\rVert$. As this constraint can be fulfilled by *any* rescaling of $\beta$ and $\beta_0$, we can set $\lVert\beta\rVert=w^{-1}$ and rewrite the constrained optimization problem above as
$$
\min_{\beta,\beta_0}\lVert\beta\rVert\ \ \text{subject to}\ \forall i: y_i (\beta^\top x_i+\beta_0)\geq 1.
$$
And to make it even simpler we will instead minimize the most convenient cost function of them all, $\frac{1}{2}\lVert\beta\rVert^2$, because all norms are equivalent and some are easier to compute.
Before we go into solving this problem, let's make it more powerful by adding robustness to outliers. Imagine the two classes can be linearly separated as shown in the image above apart from a few points that will fall on the wrong side of the discriminating. We'll parameterize the fractional misclassification $\xi_i$ as the amount (in units of $\beta$) by which a sample is on the wrong side of the boundary. This will relax the constraint to $y_i (\beta^\top x_i+\beta_0)\geq 1-\xi_i$, but now we have one more constraint, namely $\forall i: \xi_i\geq0$, and another term in the const function: $\gamma\sum_i \xi_i$, which weighs the total misclassification error with a factor $\gamma$. As so often for constrained optimization problems, we can solve it by writing down the Lagrange function
$$
L_p =\frac{1}{2}\lVert \beta\rVert^2 + \gamma \sum_i \xi_i + \sum_i \alpha_i \left[y_i (\beta^\top x_i+\beta_0) - (1-\xi_i)\right] - \sum_i\mu_i\xi_i
$$
where the first terms are the extended cost function, the third is the classification constraint (with a set of Lagrange multipliers $\alpha_i$), and the last ensures that the $\xi_i$ are non-negative. A not particularly illuminating derivation will result in the following solution for $\beta$:
$$
\hat\beta=\sum_i \hat\alpha_i y_i x_i,
$$
with the interesting property that the coefficients $\hat\alpha_i \neq 0 \Leftrightarrow y_i (\beta^\top x_i+\beta_0)\geq 1-\xi_i$. This means that the solution is obtained only from those samples $x_i$ that satisfy the constraint, and they are thus call *support vectors*. The samples on the margin ($\xi_i=0$) then determine $\beta_0$.
We've now seen three classifiers with linear boundaries: LDA, logit, and SV, which each optimize different objective functions. However, they all require linear separability in the feature space (or something close to that). Sometimes that's simply out of the question. The canonical way out is the [kernel trick](https://en.wikipedia.org/wiki/Kernel_trick), which replaces ordinary dot products by some other kernel function. For classifiers, this means one can pull of the linear separability in some higher-dimensional space. The combination of the support vector classifier with the kernel trick is called **Support Vector Machine**.
]]>
Data Science in Astronomy: Classification Theory