[Anomaly Detection] SVDD

본 포스트는 고려대학교 산업경영공학부 강필성 교수님의 Business Analytics 강의를 정리한 내용입니다.

 

Support Vector Data Description based Anomaly detection (SVDD)

SVDD는 앞서 살펴본 SVM과 동시대에 만들어진 알고리즘이다.

SVDD는 SVM과는 달리 hyper sphere를 찾는 것이 목표이고, 이를 위해 sphere의 중심점인 $a$와 반지름인 $R$을 찾아, 정상 데이터를 해당 sphere안에 몰아넣는 것을 목적으로 한다.

여기서 sphere 밖에 있는 데이터에 대해서는 $\xi$라는 패널티를 줄 것이다.

위 그림 오른쪽을 통해 1-SVM과 SVDD의 차이를 볼 수 있다.

Optimization function

$$ \min_{R, \mathbf{a}, \xi_{i}}{R^{2}}+C\sum_{i=1}^{l}{\xi_{i}} \\ s.t. \parallel \Phi(\mathbf{x}_{i})- \mathbf{a} \parallel^{2} \ \leq \ R^{2}+\xi_{i}, \ \xi_{i} \geq 0, \forall i $$

Optimization function의 수식을 보면 sphere의 반지름인 $R^{2}$을 최소화 하면서, sphere와 멀어지는 데이터 $\mathbf{x}$에 대해 페널티 $\xi$를 준다. 여기서 $C$는 페널티 상수이다.

아래 $s.t.$을 통해 알 수 있는 제약 조건은 데이터 $\mathbf{x}_{i}$를 $\Phi$ 함수를 통해 feature space로 mapping을 진행하고, sphere의 중심으로부터 해당 point의 거리가 sphere + $\xi$ 영역 안쪽에 위치해야 한다.

위 수식을 통해 $R$과 $\mathbf{a}$, $\xi$를 구한 후 아래 계산식을 통해 정상 또는 비정상을 판별한다.

 

Decision function

$$ f(\mathbf{x}) = sign(R^{2}- \parallel \Phi(\mathbf{x}_{i}) - \mathbf{a} \parallel^{2}) $$

feature space로 변환된 데이터 $\mathbf{x}$ 가 sphere 안쪽에 위치하면 양수 임으로 정상, 바깥쪽에 위치하면 음수임으로 비정상으로 판별한다.

라그랑주 승수법을 사용하여 최적화 함수를 정의하면 다음과 같다.

$$ L = R^{2} + C\sum^{l}_{i=1}{\xi_{i}} - \sum^{l}_{i=1}\alpha_{i}(R^{2}+\xi_{i}-(\Phi(\mathbf{x}_{i})\cdot \Phi(\mathbf{x}_{i}) - 2 \cdot \mathbf{a} \cdot \Phi (\mathbf{x}_{i})+\mathbf{a} \cdot \mathbf{a}))- \sum^{l}_{i=1}\beta_{i}\xi_{i} $$

여기서 $\alpha_{i} \geq 0, \beta_{i} \geq 0$을 만족해야 한다.

위 수식을 가지고 KKT condition에 따라 각 parameter에 대해 편미분을 해서 정리하면 아래와 같다.

$$ \begin{align*} &\frac{\partial L}{\partial R} = 2R - 2R \sum^{l}_{i=1}\alpha_{i} = 0 \rightarrow \sum_{i=1}^{l}\alpha_{i} = 1 \\ &\frac{\partial L}{\partial \mathbf{a}} = 2\sum^{l}_{i=1}\alpha_{i} \cdot \Phi(\mathbf{x}_{i})- 2\mathbf{a}\sum_{i=1}^{l}\alpha_{i} = 0 \rightarrow \mathbf{a} = \sum^{l}_{i=1}\alpha_{i} \cdot \Phi(\mathbf{x}_{i}) \\ &\frac{\partial L}{\partial \xi_{i}} = C - \alpha_{i}-\beta_{i} = 0 \ \ \forall i \end{align*} $$

위 수식을 통해 나온 식들을 최적화 함수에 대입하면 다음과 같이 정리 된다.

$$ L = \sum^{l}_{i=1}\alpha_{i}\Phi(\mathbf{x}_{i}) \cdot \Phi(\mathbf{x}_{i}) - \sum^{l}_{i=1} \sum^{l}_{j=1} \alpha_{i}\alpha_{j}\Phi(\mathbf{x}_{i})\Phi(\mathbf{x}_{j}) \\ (0 \leq \alpha_{i} \leq C) $$

위 수식에 음수를 곱해서 최소화 문제로 변환할 수 있다.

$$ L = \sum^{l}_{i=1} \sum^{l}_{j=1} \alpha_{i}\alpha_{j}\Phi(\mathbf{x}_{i})\Phi(\mathbf{x}_{j})- \sum^{l}_{i=1}\alpha_{i}\Phi(\mathbf{x}_{i}) \cdot \Phi(\mathbf{x}_{i}) \\ (0 \leq \alpha_{i} \leq C) $$

1-SVM과 마찬가지로 $\alpha_{i}$의 값에 따라 위치가 달라진다.

Case 1 : $\alpha_{i}=0$ → a non-support vector

여기서 $\alpha_{i}=0$라는 의미는 $\beta_{i}$가 $C$라는 것이고, 이는 조건에 의해 $\xi_{i} = 0$이라는 것과 같다. 결국 이 객체들은 $L$에 아무것도 영향을 주지 않는 hyper sphere 안 쪽에 위치하는 점이 된다.

Case 2 : $\alpha_{i} = C$ → Support vector

해당 케이스를 만족하려면 $\beta_{i}$는 0이 되어야 하고, $\xi$는 0보다 커야 한다.

이를 만족하는 $\alpha$는 support vector가 되고, hyper sphere 바깥쪽에 위치하는 점이 된다.

Case 3 : $0 < \alpha_{i} < C$ → Support vector

해당 부등식을 만족하는 $\alpha_{i}$는 결국 $\xi$가 0이 되고, 이는 support vector 이면서 hyper sphere 위에 위치하게 된다.