> For the complete documentation index, see [llms.txt](https://chenchao-zhao.gitbook.io/machine-learning-demystified/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chenchao-zhao.gitbook.io/machine-learning-demystified/blogs/one-class-svm.md).

# One Class SVM

An algorithm for novelty detection and empirical distribution support estimation

#### Separate data distribution from the origin by a hyperplane

Assume the points are separable from the origin, then what is the maximum margin?

The problem can be formulated as

$$
\min\_{w} \frac12 \Vert w \Vert^2 ;\text{ subject to };(w\cdot x\_i) \ge \rho, \text{ with }\rho\ge 0
$$

for all data point $$x\_i \in \mathbb R^n$$. The problem is equivalent to the binary case where $$(x\_i; 1)$$ and $$(-x\_i; -1)$$ are the two classes.

The Lagrangian is

$$
\mathcal L(w) = \frac12 w^2 - \sum\_i \alpha\_i (w\cdot x\_i - \rho) - \mu \rho
$$

with KKT conditions $$\alpha\_i (w\cdot x\_i -\rho) = 0$$ where $$\alpha\_i \ge 0$$.

Take gradient

$$
\partial\_w \mathcal L = w - \sum\_i \alpha\_i x\_i = 0\\
\partial\_\rho \mathcal L = \sum\_i \alpha\_i - \mu = 0
$$

Then, $$w=\sum\_i \alpha\_i x\_i$$. The dual problem Lagrangian is

$$
\mathcal L^\* (\alpha) = - \frac12 \sum\_{i,j} \alpha\_i \alpha\_j \langle x\_i, x\_j\rangle \text{ with }\alpha\_i \ge 0 \text{ and } \sum\_i\alpha\_i = {\rm const.} \ge 0
$$

Without loss of generality, we set $$\sum\_i \alpha\_i = 1$$.

In other words,

$$
\max\_{\alpha};  - \frac12 \alpha^\top K \alpha ;\text{ subject to } \alpha\_i\in\[0,\infty), \alpha^\top 1 = 1
$$

or

$$
\min\_{\alpha} \frac12 \alpha^\top K \alpha ;\text{ subject to } \alpha\_i\in\[0,\infty), \alpha^\top 1 = 1
$$

The $$\rho$$ can be solved by plugging in the support vectors, $$\rho = w\cdot x\_i^\*$$ . 

The decision function is given by $$f(x) = {\rm sgn}(w\cdot x -\rho)$$ and $$f(x\_i)\ge 0$$ for all data points.

#### Inseparable case and soft margin

Now we allow the violations of classification criterion $$w\cdot x\_i \ge \rho$$, and panelize the misclassifications using Hinge loss

$$
\mathcal L^{\rm hinge} (w, \rho) = \sum\_i \max(0, -(w\cdot x\_i-\rho)) = -\sum\_i (w\cdot x\_i -\rho) 1\_{{w\cdot x\_i < \rho}}
$$

Introduce slack variable $$\xi\_i \ge 0$$ as the discrepancy $$\xi\_i = \rho - w \cdot x\_i$$ for each violation. With help of slack variables, we have

$$
w\cdot x\_i -\rho +\xi\_i \ge 0
$$

Thus, the soft margin loss function

$$
\mathcal L(w, \rho, \xi) = \frac12 \Vert w\Vert^2 + C\sum\_i \xi\_i - \sum\_i \alpha\_i (w\cdot x\_i -\rho +\xi\_i) - \sum\_i \beta\_i \xi\_i - \mu\rho
$$

where $$C\ge0$$ and $$\mu\ge 0$$. The gradients are

$$
\partial\_w \mathcal L = w - \sum\_i \alpha\_i x\_i = 0\\
\partial\_\rho \mathcal L = \sum\_i \alpha\_i - \mu = 0\\
\partial\_{\xi\_j} \mathcal L = C - \alpha\_j - \beta\_j = 0
$$

Thus, the dual problem is

$$
\mathcal L^\*(\alpha) = -\frac12 \sum\_{i,j}\alpha\_i\alpha\_j \langle x\_i,x\_j \rangle = -\frac12 \alpha^\top K \alpha
$$

Hence we have the quadratic program

$$
\min\_{\alpha} \frac12 \alpha^\top K \alpha ;\text{ subject to }, \alpha\_i \in \[0, C] ,\text{ and } \sum\_i \alpha\_i = 1
$$

where $$C=(\nu m\_{\rm sample})^{-1}$$ in the original paper and thus $$C^{-1}$$ is the upper bound of number of outliers.