이전 글 [SR-CNN(1)]에서 Anomaly detection 및 Online detecion에 대한 정의와 Fourier Transform(푸리에 변환)에 대해 살펴보았습니다. 이전 글의 내용과 논문 [Time-Series Anomaly Detection Service at Microsoft]를 바탕으로 본 글 [SR-CNN(2)]에서는 "Spectral Residual(SR)"과 "SR-CNN"에 대해 본격적으로 살펴보고자 합니다.
▶ [Key Words of SR-CNN]: Anomaly Detection, Time Series, Spectral Reisual(SR)
1. Introduction
▶ Time-series anomaly detection이란,
Sequence of real values $\mathbf{x} = x_1, x_2, \cdots, x_n$이 주어진 경우,
time series anomaly detection의 목적은 $x_i$가 anomaly point 여부에 따른 output $y_i \in \{0,1\}$에 대해
output sequence $y=y_1,y_2, \cdots, y_n$을 생산하는 것입니다.
▶ Introduction(SR-CNN에 대한 간략한 소개)
논문에서는 기존 모델보다 더 나은 accuracy, efficiency와 generality를 갖는 time series anomaly detection model인 SR-CNN을 개발했습니다. SR-CNN은 Spectral Residual(SR)과 Convolutional Neural Network(CNN)을 결합한 모델로 SR의 output인 saliency map을 기반으로 CNN을 학습시킵니다. 자세한 내용은 "section 2. Methodology"에서 살펴보도록 하겠습니다.
▶ 논문에서 강조하는 3가지
- 첫째, visual saliency detection의 기술을 time-series data에서의 anomalies(비정상)을 탐지하는데 사용했습다.
- 둘째, time-series anomaly detection의 accuracy(정확도)를 향상시키기 위해서 SR과 CNN을 결합했습니다.
- 셋쩨, 제안된 모델은 기존의 모델보다 더 좋은 generality와 efficiency를 가집니다.
2. Methodology
본격적으로 Spectral Residual(SR)과 SR-CNN에 대해 설명하도록 하겠습니다.
2.1 Spectral Residual(SR)
▶ Spectral Residual(SR)이란,
Spectral Residual(SR)은 Fast Fourier Transform(FFT) 기반 접근방법으로 unsupervised learning(비지도 학습) 알고리즘이며 visual saliency detection에서 뛰어난 성능(performance)과 경건함(robustness)이 증명되어 있습니다.
※ Reference(참고): Saliency detection에 대한 자세한 내용은 '유니디님의 Saliency detection이란?' 블로그를 참조
Saliency detection이란, 관심 있는 물체를 관심이 없는 배경(background)으로부터 분리시키는 것을 의미합니다. Saliency detecion과 관련된 개념으로는 이미지안의 객체를 분리하거나 위치 정보를 출력하는 object detection, 이미지를 특징이 비슷한 것들끼리 뭉쳐서 여러 세그먼트로 분할하는 image segmentation 등이 존재합니다.
▶ Question: 왜 visual saliency detecion에서 입증된 SR을 time series anomaly detection에서 사용하는가?
Anomaly point는 시각적인 관점(visual perspective)에서 salient이기 때문에 visual saliency detection과 time series anomaly detection은 비슷한 task라고 주장할 수 있습니다. 따라서, visual saliency detection의 기술을 time-series data에서의 anomalies(비정상)을 탐지하는데 사용했습니다.
※ salient: something or qualities of something are the most important things about them
▶ Algorithm
SR은 3가지의 주요한 단계로 구성됩니다.
[Step 1] Log amplitude spectrum을 얻기 위해 fourier transform(푸리에 변환)
[Step 2] Spectral residual 계산
[Step 3] Inverse Fourier Transform(푸리에 역변환)을 통해 frequency domain에서 spatial domain으로의 변환
수식으로 구체적으로 살펴보면 다음과 같습니다.
- Given a sequence $\mathbf{x} \in \mathbb{R}^{n \times 1}$과 $h_q(f) = \dfrac{1}{q^2} \begin{bmatrix}
1 & 1 & 1 & \cdots & 1 \\
1 & 1 & 1 & \cdots & 1 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & 1 & 1 & \cdots & 1
\end{bmatrix} \in \mathbb{R}^{q \times q}$가 주어졌을 때,
[Step 1] Fourier Transform to get the log amplitude spectrum
$$A(f) = Amplitude(\tilde{\varrho}(\mathbf{x})), \tilde{\varrho} : \text{ Fourier Transform}\tag{1}$$
$$P(f)=Phrase(\tilde{\varrho}(\ mathbf {x})) \tag{2}$$
$$L(f) = log(A(f)) \tag{3}$$
※ amplitude spectrum 및 phase spectrum에 대한 보충 설명은 [SR-CNN(1)]을 참조
- 식 $(1) \, A(f)$은 sequence $\mathbf{x}$의 amplitude spectrum으로 fourier transform의 크기 $|\tilde{\varrho}|$입니다.
- 식 $(2) \, P(f)$는 sequence $\mathbf{x}$의 phase specturm으로 fourier transform의 편각입니다.
- 식 $(3) \, L(f)$는 $A(f)$에 log을 취한 값이며 log amplitude specturm 값입니다.
※ Fast Fourier Transform(FFT)는 sequence의 sliding window $w$ 안에서 수행되어집니다.
[Step 2] Caculation of spectral residual
$$AL(f) = h_q(f) \cdot L(f) \tag{4}$$
$$R(f) = L(f) - AL(f) \tag{5}$$
- 식 $(4) \, AL(f)$는 $h_q(f)$을 통해 input sequence $\mathbf{x}$를 convoluting(합성곱)을 함으로써 $L(f)$의 average spectrum으로 근사한 값입니다.
- 식 $(5) \, R(f)$는 spectral residual 값으로 log spectrum $L(f)$에서 averaged log spectrum $AL(f)$를 뺀 값입니다.
[Step 3] Inverse Fourier Transform that transforms the sequence back to spatial domain
$$S(\mathbb{x}) = ||\tilde{\varrho}^{-1}(exp(R(f)+iP(f))) \, \tilde{\varrho}^{-1} : \text{ Inverse Fourier Transform} \tag{6}$$
식 $(6) \, S(\mathbb{x})$는 saliency map으로 inverse fourier t ransform을 통해 sequence $\mathbb{x}$를 다시 spatial domain으로 변환시킨 값입니다.
▶ Example
[Figure 1]은 SR model의 결과의 한 예시로 saliency map에서의 innovation point(red point)는 original input(time-series input)에서보다 훨씬 유의한 (significant) 것을 알 수 있습니다. 즉, saliency map을 기반으로 더 쉽고 정확하게 anomaly points를 찾을 수 있습니다.
▶ Discriminate Anomaly point: Saliency map에서 anomaly point 판단을 어떻게 하는가?
주어진 saliency map $S(\mathbb{x})$와 임의의 threshold $\tau$가 주어졌을 때 $O(x_i)$를 다음과 같이 정의합니다.
$$O(x_i) = \begin{cases} 1 &\text{if } \dfrac{S(x_i)-\bar{S(x_i)}}{\bar{S(x_i)}} > \tau \\
0 &\text{otherwise}\end{cases} $$
- $x_i$: sequence $\mathbf{x}$의 임의의 점
- $S(x_i)$: saliency map에 상응하는 점
- $\bar{S(x_i)}$는 $S(x_i)$의 앞선 $z$개의 점들의 지역 평균(local average) 값
즉, $\dfrac{S(x_i)-\bar{S(x_i)}}{\bar{S(x_i)}}$ 값이 임계값 $\tau$보다 크면 anomaly point로 판단하는 것입니다.
▶ SR은 anomaly point가 sliding window 중앙에 위치할 때 가장 잘 작동합니다.
우리는 짧은 대기시간(low latency) 안에 anomaly point를 발견하는 알고리즘을 기대합니다. 즉, streaming data $x_1, x_2, \cdots, x_n$이 주어졌을 때, 가장 최근의 점 $x_n$이 가능한 한 빨리 anomaly point인지 아닌지에 대해 판단해야 합니다.
그러나 SR은 anomaly window가 중앙에 위치할 때 가장 잘 작동하기 때문에 SR model에 sequence data $\mathbb{x}$를 넣기 전에 $x_n$ 이후의 데이터 $x_{n+1}, x_{n+2}, \cdots$를 추정해서 $x_1, \cdots, x_m, x_{n+1}, \cdots$를 SR model의 input data로 사용해 $x_n$이 anomaly point인지 아닌지 판단합니다.
"The value of estimated point: $x_{n+1}$"
$$\bar{g} = \dfrac{1}{m} \sum^m_{i=1}g(x_n, x_{n-i})
\\
x_{n+1} = x_{n-m+1} + \bar{g} \cdot m$$
- $g(x_i, x_j)$는 $x_i$와 $x_j$ 사이의 straight line의 gradient 값입니다.
- 예를 들어, 데이터셋 $(x_n, S(x_n)), (x_{n-i}, S(x_{n-i}))$이 주어진 경우, $g(x_n,x_{n-i}) = \dfrac{S(x_{n-i}) - S(x_n)}{x_{n-i} - x_n}$입니다.
- $\bar{g}$는 이전 점들(preceding points) gradient 값의 평균값입니다.
- $m$은 이전 시점 혹은 점들을 고려한 개수입니다.
논문의 저자들은 가장 처음으로 추정된 점 $x_{n+1}$이 그 이후에 추정된 점들 $x_{n+2}, x_{n+3}, \cdots, x_{n+\kappa}$보다 더 결정적인 역할을 하기 때문에 $x_{n+2}, x_{n+3}, \cdots, x_{n+\kappa}$ 대신 $x_{n+1}$을 $\kappa$번 사용합니다.
▶ Hyper-parameter of SR
SR의 hyper-parameter로는 다음 3가지가 존재합니다.
- sliding window size $w$
- estimated points numbker $\kappa$
- anomaly detecion threshold $\tau$
2.2 SR-CNN
SR-CNN은 SR의 한계점을 지적하며 새로운 방법론을 제안합니다.
▶ Limitation of SR
기존의 SR 방법론은 하나의 threshold를 이용해 anomaly point 여부를 판단하는데 이 방법은 naive하기 때문에 더 정교한 decision rule이 필요합니다. 이에 대해 잘 디자인 된 synthetic data를 가지고 anomaly detector 역할인 discriminative model을 훈련하여 anomaly points 여부를 판단하는 방법론을 제안합니다.
▶ Synthetic Data: syntehtic data(합성 데이터)는 어떻게 만드는가?
다음 3가지 과정을 통해 synthetic data를 생성합니다.
[Step 1]. Sequence data $\mathbb{x}$에서 랜덤하게 몇 개의 점들을 선택합니다.
[Step 2].선택된 기존의 점을 대체할 injection value를 계산합니다.
※ injection points는 anomalies로 라벨링, 그 외의 점들은 normal로 라벨링합니다.
$$x=(\bar{x} + \text{mean})(1+\text{var}) \cdot r + x$$
- $\bar{x}$: 이전 시점의 점들(preceding points)의 지역 평균
- mean & var: 현재 sliding window 안에 존재하는 모든 점들의 평균과 분산
- $r \sim N(0,1)$: $r$은 표준정규분포로부터 랜덤하게 샘플링된 값
[Step 3]. [Step 2]에서 생성한 데이터를 가지고 SR model를 통해 saliency map을 생성합니다. 이 saliency map이 synthetic data이며 discriminate model의 훈련 데이터로 사용됩니다.
※ Synthetic data를 사용함으로써 장점은 수동으로 지정한 데이터가 필요하지 않다는 점입니다.
▶ Discriminative Model: CNN
Discrimnative model로는 convolutional neural network(CNN)을 사용합니다. 만약 labeled data가 충분히 이용가능하다면, supervised learning(지도 학습) 모델인 CNN은 saliency detection에서 end-to-end training을 통해 우수한 성능을 보입니다.
※ [end-to-end training]: 수동 피처 엔지니어링(manual feature engineering)이나 중간 처리 단계 없이 입력 데이터에서 출력 데이터로 직접 작업을 수행하는 방법을 학습하는 일종의 머신러닝 모델
만약, large scaled labeled data를 모으기 어려운 경우는, input data로부터 바로 CNN을 훈련시키는 것은 정확도가 많이 저하됩니다. 따라서, 이에 CNN의 training data를 original data를 사용하지 않고 synthetic data를 사용합니다.
[Figure 2]를 참조하면, CNN은 2개의 1-D convolution layer와 2개의 fully connected layer로 구성된 것을 확인할 수 있습니다. 2개의 1-D convolution layer의 filter size는 모두 sliding window $w$와 동일합니다. Channel size의 경우, 첫번째의 1-D convolution layer는 $w$, 두번째의 1-D convolution layer는 $2w$로 설정합니다. 손실 함수로는 cross entropy loss를 사용하며 stochastic gradient(SGD) 방법으로 최적화가 이루어집니다.
▶ SR-CNN의 학습 과정([Figure 2] 참조)
1. Raw input data를 가지고 synthetic data를 생성합니다.
2. 생성된 synthetic data는 discriminate model인 CNN의 훈련 데이터로 사용됩니다.
3. CNN은 anomaly detector 역할로 anomaly labels를 산출합니다.
3. Metrics
논문에서 SR-CNN을 accuracy, efficientcy와 generality 관점에서 모델을 평가합니다.
▶ Accuracy
정확도 측면에서는 precision, recall, F1-score로 판단합니다. 각 객체마다의 예측값과 실제값을 비교하는 point-wise metrics에 관점을 두지 않고 적당한 delay threshold $k$ 안에서 연속적인 anomaly point 발생시에 알람을 띄우는 것입니다. Anomaly point가 처음 발생하고 나서 $k$ 시점 이내에 탐지만 가능하다면 잘 탐지하는 것으로 인정합니다.
- [Example]
첫번째 행은 true label로 총 10개의 점과 2개의 anomaly segments가 존재하며 두번째 행은 prediction results(예측 결과값)입니다. Delay threshold $k=1$로 설정한 경우, 첫번째 anomaly segments는 delay가 1이므로 correct, 두번째 anomaly segments는 delay가 2이므로 incorrect합니다. 세번째 행은 예측 결과를 조정한 값으로 이를 기반으로 precision, recall, F1-score를 계산합니다.
▶ Efficiency
Efficiency의 경우는 짧은 대기시간(low latency)가 중요합니다. 즉, anomaly points가 들어온 경우 얼마나 빠르게 판단하는지를 측정합니다.
[Table 1]과 [Table 2]를 통해 SR-CNN의 accruacy(F1-score, Precision, Recall)와 efficiency(Time(s))를 확인해 본 결과 대부분의 결과에 있어 SR-CNN의 accuracy가 가장 좋은 것을 확인할 수 있습니다. 반면, efficiency의 경우 SR이 SR-CNN보다 더 작은 것을 확인할 수 있습니다. 이에 대해서 개인적으로 생각해본 결과 SR의 경우는 임의의 하나의 threshold를 가지고 anomaly point 여부를 판단하지만 SR-CNN의 경우는 discriminate model(CNN)을 훈련함으로써 anomaly point를 판단하기 때문에 더 많은 시간이 상대적으로 소요된다고 생각합니다.
▶ Generality
Generality를 판단하기 위해 같은 dataset을 stable, unstable, season 3개의 그룹으로 나누어 F1-score를 평가합니다.
[Table 3]를 확인해 본 결과 전체적으로(overall) 보았을 떄 SR-CNN의 성능이 가장 좋은 것을 통해 generality가 다른 모델에 비해 더 좋다는 것을 확인해 볼 수 있습니다.
본 글은 visual saliency detection에서 우수한 성능을 입증한 Spectral Residual(SR)를 time series anomlay detection에 응용한 SR-CNN에 대해서 살펴보았습니다. Discriminate model인 CNN을 사용한 이유는 anomaly point 여부를 더 정교한 decision rule을 통해 판단하고자 사용하였습니다.
