[논문 리뷰] Fast Hoeffding Drift Detection Method for Evolving Data Streams

“Fast Hoeffding Drift Detection Method for Evolving Data Streams” 논문을 개인 공부 및 리뷰를 위해 쓴 글입니다.
논문 링크 : https://link.springer.com/chapter/10.1007/978-3-319-46227-1_7

1. Introduction

• 진화하는 환경 속에서 학습하는 것은 어려운 과제이다.
• 어려움은 입력 데이터가 오는 속도와 크기뿐 아니라, 분포의 변화가 일어날 때를 말한다.
• 이런 분포 변화는 분류 모델의 성능을 하락시킨다.
• 그래서 마지막에 조정(adaptive) 학습 알고리즘은 drift detection method를 이용하여 이런 변화를 감지하고 조치를 취한다.
  • 전형적으로, 분류 모델을 업데이트하거나, 드리프트(drift)가 검출(detect)될 때 재학습(retrain)을 진행한다.
  • 대안으로, 앙상블 학습 알고리즘을 사용하여 정확도 유지를 시도한다.
• 높은 FP 비율을 가진 drift detector는 빈번한 재학습을 유발하여 더 많은 자원을 쓰게끔 한다.
• 반면, 높은 FN 비율을 가진 drift detector는 분류 정확도의 감소(decay)를 유발한다.
• 드리프트 지점의 정확한 추정은 필수인데, (i.e.delay가 덜한 채로 drift를 검출하는) 데이터를 최대한 사용할 수 있을 뿐더러 드리프트가 어떻게 일어났는지 알려주기 때문이다.
• 따라서, FP, FN, detection delay는 drift detection method를 측정할 때 평가 항목들이다.

• Fast Hoeffding Drift Detection Method (FHDDM)은 슬라이딩 윈도우(sliding window)와 호에프딩 부등식(Hoeffding’s inequality)를 사용하여 옳은 예측의 최대확률을 계산하고 비교한다.
• FHDDM은 SOTA와 비교해 less detection delay, less FP와 FN 비율을 보여줄 것이다.

2. Related Works

• concpet drift detector는 3가지 그룹으로 나뉜다.
• (1) Sequential Analysis based Methods
  • 순차적으로 예측 결과를 평가하고, 사전 정의한 임계값을 만날 때 drift을 위한 알람(alarm)이 켜진다.
  • Cumulative Sum (CUSUM), Geometric Moving Average (GMA)가 그 예이다.
• (2) Statistical based Methods
  • 이 메서드는 예측 결과의 평균(mean)과 표준 편차(standard deviation)를 이용하여 통계적 파라미터를 증명하여 스트림의 드리프트를 검출(detect)한다.
  • Drift Detection Method (DDM), Early Drift Detection Method (EDDM), Exponentially Weighted Moving Average (EWMA)가 그 예이다.
• (3) Windows based Methods
  • 고정된 윈도우를 사용하여 과거 정보를 평균내고 가장 최근 정보를 평균내어 그 차이를 가지고 드리프트 현상이 일어났는지 본다.
  • 분포가 동일하다는 귀무 가설(i.i.d)을 사용하여 통계적 검정이나 수학적 부등식을 사용하여 차이 수준을 결정한다.
  • Adaptive Windowing (ADWIN), Hoeffding Drift Detection Methods ($HDDM_{A-test}$와 $HDDM_{W-test}$)가 그 예이다.

3. Fast Hoeffding Drift Detection Method

• Fast Hoeffding Drift Detection Method (FHDDM)은 hoeffding’s inequality를 사용하여 변하는 데이터 스트림 속에 드리프트를 검출한다.
• FHDDM은 분류 결과를 n 사이즈의 윈도우로 슬라이드한다.
• 결과적으로, 예측 결과가 true면 1을 삽입하고, false면 0을 삽입한다.
• 입력 데이터가 들어옴에 따라, 시간 $t$에서 슬라이딩 윈도우에서 $p_t^1$을 관찰할 확률을 계산하고, 1초동안 발생하는 최대 확률 $p_{max}^1$를 유지한다.
  • $p_t^1$ : 시간 $t$ 때 가장 최근의 n 인스턴스에서 정확한 분류 예측값들의 확률
• $p_t^1$이 $p_{max}^1$보다 크다면 그 값을 $p_{max}^1$으로 업데이트한다.
  • $if\ p_{max}^1< p_t^1\Rightarrow $ $p_t^1\rightarrow p_{max}^1$
• $\nabla p = p_{max}^1 - p_t^1 \ge \epsilon_d \Rightarrow Dirft := True$
  • $\epsilon_d=\sqrt{\frac{1}{2n}ln{\frac{1}{\delta}}}$

이미지 출처 [^11]

• 위 그림을 예시로 설명해본다.
• $n$=10, $\delta$=0.2라 하면, 위 정의대로 $\epsilon_d$=0.28이 된다.
• 위 예제에서 real drift가 12번째 인스턴스 직후 발생했다.
• 윈도우에 $p_{max}^1$가 0으로 삽입된다.
  • 따라서, $p_{10}^1$는 0.7이 된다.
• 11번째부터 예측 정확도가 점점 떨어지는 걸 볼 수 있다.
• 18번째부터 $p_{max}^1$와 $p_t^1$의 차이가 $\epsilon_d$ 보다 커진 것을 알 수 있으므로(0.3>0.28) FHDDM 알고리즘은 drift을 위한 alarm 수준에 이른다.

window-based approaches 비교

• 윈도우 기반 접근들은 보통 두개의 하위 윈도우($w_1$와 $w_2$)를 이용하기 때문에 상당한 메모리 사용량을 야기한다.
• 첫번째 윈도우는 처음부터 과거 정보(historical information)를 유지하는데 사용되며, 두번째 윈도우는 가장 최근 정보를 유지하는데 사용된다.
• 반대로, FHDDM은 현재 분류기의 정확도를 최고의 정확도와 비교하는데, 이때 하나의 슬라이딩 윈도우 크기 n을 이용한다.
• 따라서, $p_{max}^1$같은 하나의 레지스터와 하나의 슬라이딩 윈도우 크기 n만 차지한다.

Pseudocode of FHDDM

• 다음은 FHDDM의 수도 코드이다.

// Alogirhtm 1.
function INITIALIZE(windowSize, delta)
    n=windowSize
    δ=delta
    εd=sqrt(1/2n ln(1/δ))
    RESET()
end function
function RESET()
    w=[] // Creating an empty sliding window.
    p1_max=0
end function
function DETECT(p) // p is 1 for the correct predictions, 0 otherwise
    if w.size()=n then
        w.tail.drop() // Dropping an element from the tail
    end if
    w.push(p) // Pushing an element into the head.
    if w.size()<n then
        return False
    else
        p1=w.count(1)/w.size() // The recent probability of seeing 1s.
        if p1_max<p1 then
            p1_max=p1
        end if
        Δp=p1_max-p1
        if Δp ≥ εd then
            RESET() // Resetting parameters.
            return True // Signalling for an alarm.
        else
            return False
        end if
    end if
end function

4. On Evaluation of Concept Drift Detectors

• TP, FP, FN 비율은 concept drift detector의 성능을 평가하는 데 유용하다.
• drift detector는 높은 TP, 낮은 FP, FN를 가질수록 좋다.
• 예를 들어, FP를 측정하기 위해, 베르누이 분포로부터 비트 스트림을 생성했다.
• 검출기가 drift를 알람했다면, FP는 각 알림에 대해 카운트된다.
• 따라서, 이런 3가지 검정을 사용하여 TP, FP, FN을 셀 수 있다.
• 이 논문에서는 허용 가능한 길이 $\Delta$를 정의하여 TP, FP, FN을 세는 접근법을 소개하고 있다.
  • 허용 가능한 지연 길이 $\Delta$는 검출된 드리프트가 실제 드리프트 위치로부터 얼마나 떨어져 있는지 결정하기 위해 설정된 임계값이다.

• True Positive (TP) : 드리프트 검출기(detector)는 만약 $[t-\Delta, t+\Delta]$ 사이에 언제든지 경보(alarm)를 울리면, 시간 $t$에 발생한 드리프트를 실제로 감지한다.
  • 이 범위를 acceptable detection interval of TP라 한다.
  • 결국, TP 비율은 스트림의 총 드리프트 수를 정확하게 식별한 드리프트 수로 정의할 수 있다.
  • 반응성 드리프트 검출기를 평가하기위한 허용가능한 감지 간격은 $[t, t+\Delta]$이다.
• False Positive (FP) : 드리프트 검출기가 허용가능한 검출 간격 밖에서 감지했을 때 드리프트를 위한 경보를 틀리게 울리는 걸 말한다.
  • FP 비율은 드리프트가 일어나지 않은 총 수 분의 드리프트를 정확하게 보지 못한 것으로 정의된다.
• False Negative (FN) : 드리프트 검출기는 $[t-\Delta, t+\Delta]$에서 언제든지 경보를 울리지 않으면 t 시간에 발생한 드리프를 잘못 관과한 것을 말한다.
  • FN 비율은 스트림의 총 드리프트 수 분의 틀린 남아있는 드리프트 수로 정의한다.
  • 반응성 드리프트 검출기를 평가하기위한 허용가능한 감지 간격은 $[t, t+\Delta]$이다.

5. Experimental Analysis

• 실험에서 VFDT(;very fast decision tree)라고도 알려진 Hoeffding Tree (HT)와 Naive Bayes (NB)를 분류기로 고려했다.
• 저자들은 SINE1, MIXED, CIRCLES, 총 3가지의 합성(synthetic) 데이터셋을 사용했다.
  • 하지만, 실험을 위해 합성 데이터에 노이즈 데이터 10%를 추가했다.
  • SINE1 : abrupt concept drift
  • MIXED : abrupt concept drift
  • CIRCLES : gradual concept drift

References