LDA, SVM & trees formulas

Euclidean distance from ${\mathbf{x}}_0$ to the hyperplane $\mathbf{w}\cdot \mathbf{x}+b=0$, for $\mathbf{w}\ne 0$.

Class means, priors and the pooled within-class covariance, where $n_k$ is the number of samples in class $k$. Dividing by $n$ instead of $n-K$ only rescales $\hat{\Sigma }$. With equal priors the decisions are unchanged. With unequal priors the $\ln {\pi }_k$ term gets a slightly different relative weight, so borderline decisions can change.

Assign $\mathbf{x}$ to the class with the largest ${\delta }_k(\mathbf{x})$; $\ln$ is the natural logarithm. This assumes Gaussian classes with a common $\Sigma$.

This is ${\delta }_1(\mathbf{x})-{\delta }_0(\mathbf{x})>0$. The boundary is a hyperplane with normal vector ${\Sigma }^{-1}({\mathbf{\mu }}_1-{\mathbf{\mu }}_0)$. It passes through the midpoint of the means when ${\pi }_0={\pi }_1$. Unequal priors shift it away from the more probable class.

Here $m_k={\mathbf{w}}^T{\mathbf{\mu }}_k$ are the projected means and $s_k^2={\sum }_{i\in k}({\mathbf{w}}^T{\mathbf{x}}_i-m_k{)}^2$ the projected scatters. Maximise over $\mathbf{w}$. $J$ depends only on the direction of $\mathbf{w}$, not on its length.

The same direction as the two-class LDA weight vector, because $S_W=(n-2)\hat{\Sigma }$ is proportional to the pooled covariance. $S_W$ must be invertible.

The distance between the hyperplanes $\mathbf{w}\cdot \mathbf{x}+b=\pm 1$. Valid only under the canonical scaling (closest points at $\pm 1$). The bias $b$ does not affect it.

Requires linearly separable data. Maximising $2/\Vert \mathbf{w}\Vert$ is the same as minimising $\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$.

Only points with ${\alpha }_i>0$ contribute to $\mathbf{w}$; these are the support vectors. By complementary slackness, ${\alpha }_i[y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)-1]=0$, so every support vector lies exactly on $y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)=1$.

In the dual, the only change from the hard margin is the box constraint $0\le {\alpha }_i\le C$.

At the optimum ${\xi }_i=\max (0,1-y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b))$, which turns the constrained problem into this unconstrained one.

Polynomial kernel: degree $p$ a positive integer and $c\ge 0$. RBF (Gaussian) kernel: $\gamma >0$, often written $\gamma =1/(2{\sigma }^2)$. RBF values lie in $(0,1]$ and equal 1 only when $\mathbf{x}=\mathbf{z}$.

Only the support vectors (${\alpha }_i>0$) contribute to the sum.

$p_k$ is the fraction of class $k$ in node $S$. Entropy ranges from $0$ (a pure node) to ${\log }_{2}K$ (all classes equally likely), which is $1$ bit for two balanced classes.

Ranges from $0$ (pure) to $1-1/K$ (equal classes), which is $0.5$ for two balanced classes. For two classes with proportions $p,1-p$: $G=2p(1-p)$.

Ranges from $0$ to $1-1/K$. For two classes, $E=\min (p,1-p)$. Entropy and Gini respond more strongly to changes in node purity, so they are the usual criteria for growing a tree.

$S_v$ is the subset sent to child $v$ by the test $A$. The same weighted-average pattern with $G$ in place of $H$ gives the Gini reduction. Choose the split with the largest gain.

Divides the gain by the entropy (in bits) of the split proportions themselves. This penalises tests that break the node into many small branches.