机器学习中的异常检测在很多场景有重要应用,本文记录 SVDD 算法。
支持向量数据描述 SVDD(Support Vector Data Description,SVDD)是一种单值分类算法,能够实现目标样本和非目标样本的区分,通常应用于异常检测、入侵检测等领域。
SVDD 的思路是寻找一个尽可能小的高维球体,将训练数据容纳进去,那么在预测数据时,认为在球体之外的数据为异常数据。
$$ (x^{(i)}−a)^T(x^{(i)}−a)≤R^2 $$
$$ \left(x^{(i)}-a\right)^{T}\left(x^{(i)}-a\right) \leq R^{2}+\xi_{i}, \xi \geq 0 $$
$$ \begin{array}{c} \min _{a, \xi,R} R^{2}+C \sum_{i=1}^{m} \xi_{i} \\ \text { s.t. }\left(x^{(i)}-a\right)^{T}\left(x^{(i)}-a\right) \leq R^{2}+\xi_{i}, \\ \quad \xi_{i} \geq 0, i=1,2, \cdots, m .\end{array} $$
其中, C>0
$$ \begin{aligned} L(R, a, \alpha, \xi, \gamma)=& R^{2}+C \sum_{i=1}^{m} \xi_{i} -\sum_{i=1}^{m} \alpha_{i}\left(R^{2}+\xi_{i}-\left(x^{(i)^{T}} x^{(i)}-2 a^{T} x^{(i)}+a^{2}\right)\right)-\sum_{i=1}^{m} \gamma_{i} \xi_{i} . \end{aligned} $$
无法求解,幸运的是该问题总体是凸优化问题,对偶问题与原问题等价,我们尝试求解对偶问题
$$ \begin{array}{c} \sum_{i=1}^{m} \alpha_{i}=1 \\ a=\sum_{i=1}^{m} \alpha_{i} x^{(i)} \\ C-\alpha_{i}-\gamma_{i}=0 \end{array} $$
$$ \begin{array}{c} \max _{\alpha} L(\alpha)=\sum_{i=1}^{m} \alpha_{i} x^{(i)^{T}} x^{(i)}-\sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} x^{(i)^{T}} x^{(j)}\\ s.t. 0 \leq \alpha_{i} \leq C \\ \sum_{i=1}^{m} \alpha_{i}=1, i=1,2, \cdots, m . \end{array} $$
$$ (z-a)^{T}(z-a)>R^{2} $$
$$ z^{T} z-2 \sum_{i=1}^{m} \alpha_{i} z^{T} x^{(i)}+\sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} x^{(i)^{T}} x^{(j)}>R^{2} $$
正常情况下,数据并不会呈现球状分布,因此有必要使用核函数的方法提高模型的表达能力。
$$ \begin{array}{c} \min _{\mathbf{a}, R, \xi} R^{2}+C \sum_{i=1}^{n} \xi_{i}\\ s.t. \left\|\Phi\left(\mathbf{x}_{i}\right)-\mathbf{a}\right\|^{2} \leq R^{2}+\xi_{i}, \\\xi_{i} \geq 0, \forall i=1,2, \cdots, n \end{array} $$
$$ \begin{array}{c} \min _{\alpha_{i}} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)-\sum_{i=1}^{n} \alpha_{i} K\left(\mathbf{x}_{i}, \mathbf{x}_{i}\right) \\ s.t. \quad 0 \leq \alpha_{i} \leq C, \\ \sum_{i=1}^{n} \alpha_{i}=1 \\ \end{array} $$
$$ \mathbf{a}=\sum_{i=1}^{n} \alpha_{i} \Phi\left(\mathbf{x}_{i}\right) $$ $$ R=\sqrt{K\left(\mathbf{x}_{v}, \mathbf{x}_{v}\right)-2 \sum_{i=1}^{n} \alpha_{i} K\left(\mathbf{x}_{v}, \mathbf{x}_{i}\right)+\sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} K\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right)} $$
$$ \mathcal {K} \left ( x ^ { (i) ^ {T} } x ^ {(j) } \right ) = (x ^ {(i) ^ {T}} x ^ {(j)}+1) ^ {d} $$
$$ \mathcal{K}\left(x^{(i)^{T}} x^{(j)}\right)=\exp (\frac{-\left(x^{(i)}-x^{(j)}\right)^{2}}{s^{2}}) $$