[Review] NDC 이상탐지를 위한 빠른 시계열모델(RLS필터주기모델)

[NDC] 이상탐지를 위한 빠른 시계열모델(RLS필터주기모델)

권리자명: (주)넥슨코리아

홈페이지: [NDC] 이상탐지를 위한 빠른 시계열모델(RLS필터주기모델)

 

배경

인게임지표 이상탐지 서비스는 인게임 내에서 몬스터, 아이템, 재화, 퀘스트 등의 지표에서 이상현상이 탐지가 된다면 게임팀에 알림을 드리고 있다. 언제어디서 이상현상이 나타날지 모르기 때문에 세분화하여 모니터링하고 탐지하고 있다.

다양한 시각으로 현상을 바라보고 있으며, 이상이 탐지되었을 때는 내부적으로 검증하는 시스템을 도입하여 통과했을 때 알림을 드리고 있다.

• 요구사항
  • 한 스텝 이후의 지점을 예측하는 short term 시계열 예측
  • 과거 정상상황과 현재와의 point 비교탐지
  • 넓은 영역에서의 시계열 지표 이상탐지
• 데이터 특징
  • 일변량데이터 (Univariate data)
  • 학습데이터에 이벤트성 outlier가 매우 빈번
  • 각 시계열마다 학습데이터의 길이와 특징이 모두 다름

특징으로 인한 결과 -> 하나의 모델로는 모든 처리가 힘들고 시스템안에서 여러 목적을 달리한 모델들을 통해 탐지를 진행하고 있다.

 

시계열 탐지 절차

1. 지표의 주기 추정 모델
2. 학습데이터 이상치 labeling, 제거 모델
3. 데이터 특성 판단 후 특성 분류 모델
4. 특성에 맞는 시계열 예측, 정상범주 계산 모델
5. 다양한 변수를 활용한 검증 모델

시계열 모델은 이 중 4번째 단계에 해당 -> 과거의 패턴을 정상상황으로 가정하고 학습해 현재와의 차이점을 비교

 

이슈상황

다양한 시각을 위해 처리영역을 늘리기 시작하며 계산비용(시간)이 급격하게 급증

원인파악: 시스템읜 단계별로 병목현상의 원인 파악 -> 4번째 단계

기존

1. 예측을 위한 시계열 모델

2. 실시간 배치 모델 적용

   ↓

개선방향

1. 탐지를 위한 시계열 모델
2. Online 모델 적용

 

리서치 내용

진행 부분

1. 모델 변경

1) 탐지를 위한 시계열 모델

2) 모델 경량화 (least square 추정으로 변경)

이상탐지 목적

과거의 정상적인 상황의 패턴을 강건하게 학습하는 것(이때 model의 Trade off를 생각할 필요가 있음)

모델의 성능을 말할때 흔히 bias(편향)와 variance(분산)의 tradeoff [1]관계를 언급하게 되는데 예측분류 모델에서는 bias와 variance의 관계를 조율해 두가지 측면에서 모두 좋은 성능을 내는 것을 목표로 하고 있다.(기존의 미래예측에 관점을 둔 모델)

[1] Bias-Variance Trade-off는 지도 학습 알고리즘이 트레이닝 셋의 범위를 넘어 지나치게 일반화하는 것을 예방하기 위해 두 종류의 오차(편향, 분산)를 최소화 할 때 겪는 문제이다.

하지만 과거의 패턴을 가져오는것이 목적이었고 확인 결과 variance를 낮추기 위해 큰 비용을 지불하고 있었다.

variance는 일반화된 예측 미래의 성능을 위한것이고 게임이상탐지팀의 목적은 미래의 정확한 예측이 아니다. 그래서 Bias에 집중하고자 과거의 데이터에 조금더 overfitting하도록 모델을 변경하도록한다.

기존모델 (SRT + MA(1) + SMA(1)):

\[\hat{Y} = \mu + Y_{t-s} + \beta_1 \left( Y_{t-1} - Y_{t-(s+1)} \right) - \gamma_1 e_{t-1} - \Phi_1 e_{t-s} + \gamma_1 \Phi_1 e_{t-(s+1)}\]

과거패턴: \(\mu + Y_{t-s} + \beta_1 \left( Y_{t-1} - Y_{t-(s+1)} \right)\)

일반화: \(\gamma_1 e_{t-1} - \Phi_1 e_{t-s} + \gamma_1 \Phi_1 e_{t-(s+1)}\)

Ma항인 예측의 일반화는 미래예측을 위한 variance를 낮추기 위한 부분이다. 그런데 Ma항의 모수는 비선형의 특징을 지니고 있다. 때문에 모수를 추정하기위해 numerical한 계산방식으로 iteration이 돌아가며 큰 계산비용이 소모하게 된다.

계산비용을 줄이고자 일반화하는 부분을 과감하게 제거하였다.

변경모델 (SRW + AR(1)):

\[\hat{Y} = \mu + Y_{t-s} + \beta_1 \left( Y_{t-1} - Y_{t-(s+1)} \right)\]

결과적으로 과거의 패턴의 Bias를 낮춘 상태로 가지고 오면서도 탐지의 목적에서 벗어나지 않을 수 있도록 모델의 tradeoff를 설정하였다. 실제 테스트 결과 탐지분류성능의 저하없이 수배이상 계산비용이 감소하는 것을 확인할 수 있었다.

모델을 단순화, 경량화 시키면서 라이브러리를 사용하는 방식에서 간단하게 직접 구현할 수 있게되었다. 이를 통해 여러 변형되고 개선된 최소제곱법을 손쉽게 적용할 수 있는 확장성을 얻게 되었다.

2. least square 온라인 모델 업데이터 적용

1) 기존 온라인 모델업데이트 방식

온라인 모델 업데이트 방식	장단점	설명
1) 실시간 배치 업데이트	장점	최적의 모델 사용
	단점	계산비용이 크다
2) 온라인 업데이트 (Oneline Gradient descent)	장점	빠른 학습 가능
	단점	하이퍼 파라미터 설정 필요 최적 모델과 성능차이 (regret): O(√N)
3) 주기 업데이트, 4) 이상치 출현업데이트	장점	1, 2번 방법의 중재 방안
	단점	정책과 시스템 설계가 필요, 상황에 따른 제약 존재

2)온라인 업데이트의 장점으로 기존 모수에 새로 들어온 데이터의 영향력의 바탕으로 학습, 업데이트하여 빠른 학습이 가능하다는 장점이 있다.

하지만 하이퍼파라밑터의 조정에 따라 결과값이 달라진다는 단점이 있으며 결정적으로 실시간 배치에 비해 점진적으로 파라미터를 업데이트하여 성능이 떨어질 수 있다는 단점이 있다. 이를 regret[2]이라고 한다. online학습에서는 regret이라고 하는 것을 최소화하는 것을 목적으로 하고 이를 regret minization이라고 한다.

[2] regret은 최적의 모수와 online학습시의 성능의 차이를 뜻한다.

OGD(Online Gradient Decent)의 경우에는 regret이 $O(\sqrt{N})$으로 알려져 있다. 이것은 데이터가 길어질수록 최적모수와의 성능차이가 커지게 된다는 의미이다.

반면 RLS 필터(Recursive least square)에서 이 두가지 방식의 장점을 취할 수 있는 점을 확인하고 이를 적용하였다.

장점 1) 예측성능 : RLS는 수식적으로 실시간배치 모델과 동일하기 때문에 regret이 0에 가깝다. -> 성능이 실시간으로 계속 배치를 돌리는 것과 동일

장점 2) 속도 : 데이터가 들어올 때마다 저장해둔 모수와 현재 데이터와의 선형결합을 통해 빠른 계산 가능 -> 변형시에는 일괄처리가 가능해서 데이터 특성이 다른 여러 지표의 모델을 한번에 처리할 수 있다

 

2) Recursive계산 예시

데이터	평균	Recursive 평균
\(x_1, x_2, \ldots, x_t\)	\(\frac{x_1 + x_2 + \ldots + x_t}{t}\)	\(\frac{x_1 + x_2 + \ldots + x_t}{t}\)
\(x_1, x_2, \ldots, x_t, x_{t+1}\)	\(\frac{x_1 + x_2 + \ldots + x_t + x_{t+1}}{t+1}\)	Recursive(step1 평균, \(x_{t+1}\))
\(x_1, x_2, \ldots, x_t, x_{t+1}, x_{t+2}\)	\(\frac{x_1 + x_2 + \ldots + x_t + x_{t+1} + x_{t+2}}{t+2}\)	Recursive(step2 평균, \(x_{t+2}\))

---

기존 계산

• 필요한 데이터 (t)개

---

Recursive 계산

• 필요한 데이터 2개 (이전 계산값, 현재값)
• 계산이 빠르며, 이전 계산값과 동일

---

수식 유도 과정:

\[\mu_k = \frac{1}{k} \sum_{j=1}^k x_j\] \[= \frac{1}{k} \left( x_k + \sum_{j=1}^{k-1} x_j \right)\] \[= \frac{1}{k} \left( x_k + (k-1) \mu_{k-1} \right)\] \[= \mu_{k-1} + \frac{1}{k} (x_k - \mu_{k-1})\]

 

3) Recursive least square필터 적용방식

⟪ Recursive least square 적용방식 ⟫

\(( t_1\))

\(( t_2\))

\(( t_3\))

…

\(( t_{new}\))

\[S_{N+1}^* = S_N^* + x_{N+1}^{*T} x_{N+1}\] \[S_{N+1}^{*-1} = S_N^{*-1} + x_{N+1}^{*T} x_{N+1}\] \[y_{N+1} = y_{N+1}^{***} + x_{N+1}^{*T} \beta_N\] \[e_{N+1} = y_{N+1}^{***} - x_{N+1} \hat{\beta}_N\] \[\beta_{N+1} = \beta_N + y_{N+1} e_{N+1}\]

 

\[S_N^* = x_N^{*T} x_N^*\] \[x_N^{**} = t_{N-1} - t_{N-s-1}\] \[y_N^{***} = t_N - t_{N-s}\]

---

⟪ Recursive least square 계산 ⟫

단계	설명
1단계	이전 스텝에 저장한 \(S_N\) 을 통한 \(S_{N+1}\) 계산
2단계	\(S_{N+1}\) 역행렬 * 신규 \(x_N\) 값
3단계	이전 스텝의 \(\beta_N\) 을 통한 현재 데이터의 예측오차
4단계	현재 데이터를 반영한 모델 \(\beta_{N+1}\) 계산

컴퓨터가 인식하는 계산의 비용은 줄어들고 시계열 학습데이터의 길이에 영향을 받지않는 동일하고 빠른 속도의 계산식을 가질 수 있게 되었다. 그리고 모든 시계열 모델이 이전 스템에 저장되었던 모수와 현재의 데이터 2개의 데이터의 선형결합을 통해 계산되게 변경되었다.

• 2가지 과정을 더 거치게 된다.
  1. 역핼렬을 없애는 과정
     • 셔먼모리슨의 행렬역변환 공식[3]
     • 계산비용 감소: \((O(p^3))\) -> \((O(p^2))\)
  2. Forget_factor 현재 값에 가중치, 과거로 갈수록 과거의 데이터는 잊혀지는 가중치 적용
     • 과거로 갈수록 영향력을 줄여주는 forget factor[4]

[3] 셔먼모리슨의 행렬역변환 공식

[4] Forgetting Factor(망각 인자, λ)는 RLS 알고리즘에서 과거 데이터의 영향력을 점진적으로 줄이고, 최근 데이터에 더 많은 가중치를 주기 위해 사용하는 하이퍼파라미터\(C(w n )= i=0 ∑ n λ n−i e 2 (i)\)

결과적으로 아래의 식이 만들어진다.

전)

\[S_{N+1} = S_N + x_{N+1}^T x_{N+1}\] \[\gamma_{N+1} = S_N^{-1} x_{N+1}^T\] \[e_{N+1} = y_{N+1} - x_{N+1} \hat{\beta}_N\] \[\hat{\beta}_{N+1} = \hat{\beta}_N + \gamma_{N+1} e_{N+1}\]

---

후)

\[K_{N+1} = \frac{\lambda^{-1} V_N x_{N+1}^T}{1 + \lambda^{-1} x_{N+1} V_N x_{N+1}^T}\] \[e_{N+1} = y_{N+1} - x_{N+1} \hat{\beta}_N\] \[\hat{\beta}_{N+1} = \hat{\beta}_N + K_{N+1} e_{N+1}\] \[V_{N+1} = \lambda^{-1} V_N - \lambda^{-1} K_{N+1} x_{N+1} V_N\]

 

성능확인

비교표

성능지표	기존 모델	변경모델
이상치 탐지성능	100%	100%
시계열 예측성능	100%	94%
계산속도	100%	1.1% (일괄처리시 ▼)

---

● 이상치 탐지성능

• 과거데이터 fit 함
• 이상 탐지성능 우수 (정상상황과 비교)

● 시계열 예측성능 (척도: MASE)

• 일반적 예측력 ▼, 탐지성능에 영향 X

● 계산속도

• 기존에 비해 수백배 빠른 처리 속도
• RLS 모델은 다수 지표의 일괄처리가 가능

※ 시계열 예측선능의 경우 bias에 집중한 결과 variance가 상승하여 수치가 조금 감소하게 되었다. 하지만 예측의 성능만 하락일 뿐 탐지에 있어서는 문제가 없다.

 

회고

대학교에서 시계열분석을 공부하면 기본적인 계절성, ARIMA를 공부하게 되고 그 이후 딥러닝인 LSTM 등을 공부하게 된다. 그러면서 자연스럽게 최신이고 예측이 높은 모델인 딥러닝 위주로 공부하게 되었다. 하지만 위 컨퍼런스를 듣고 딥러닝이 아닌 빠른 속도를 위한 시계열 모델을 중점으로 사용하여 우리가 플레이하고 있는 게임에 적용하고 있다는 사실을 이번 시간에 배우게 되었다. 이 이후 근본적으로 현업에 들어갔을 때 집중해야하는 부분이 무엇인지 분석하고 이에 맞춰서 취업준비를 해야겠다는 생각을 하였다.