Drift detection method

Drift detection method 개념 정리

Author

Don Don

Published

March 9, 2024

MLOps란

  • MLops란 ML + Ops로 머신러닝 모형을 어떻게 운영하고 관리할 것인지에 대한 방법론

  • 데이터 분석을 통해 서비스를 개선한다는 의미는 문제 정의 - 데이터 탐색 - 모형 개발 - 모형 배포 - 유지 관리 등의 일련의 절차들이 시스템화되는 것을 의미함

  • 이 중 마지막 부분인 Monitoring 부분에 대해 알아보자

Monitoring

  • 머신러닝 모형은 향후 데이터도 비슷한 데이터가 들어올 것이다를 가정함

    • 주어진 데이터를 기준으로 모형을 구축하기 때문에 어쩔 수 없는 부분임
  • 실제 모형을 구축하고 운영할 때 대부분의 경우 시간이 지날수록 모형의 성능은 떨어지는 경향이 있음

    • drift가 발생한 경우(X의 분포가 바뀌었을 때, X와 Y의 관계가 바뀌었을 때 등)
  • 모델을 production level에서 관리하기 위해서는 drift가 발생하는 경우를 지속적으로 모니터링해줘야 하며, 이상이 발생했을 시에 대응 시나리오가 존재해야 함

    • X의 분포 변화 정도 or 모형 성능 변화에 따라 모델 retraining or rebuilding, .. etc

Drift란?

  • 시간에 따른 데이터의 변화를 의미함

  • drift는 광의의 개념이고 Concept drift, Data drift, Label drift, Feature drift 등 다양한 종류의 drift가 존재함

concept drift

  • 시간에 따른 X와 Y의 관계 변화를 의미함

    • 고객이 구매한 제품을 예측할 때, 고객 선호도가 변경되는 경우

    • 금융 위기 이후 회사의 수익을 예측하는 경우

  • X와 Y의 관계 변화는 하나로 정의할 수 없고, 다양한 시나리오가 있을 수 있음

    full stack deeplearning lecture 11
    • X와 Y의 분포 변화가 독립적으로 문제가 되는 것이 아니라 X의 분포가 바뀌면 Y의 분포도 바뀔 수 있고, Y^의 분포도 바뀔 수 있음 or 안바뀔 수도 있음

Drift 발생 시나리오 종류

  1. instantaneous drift(shift)

    • 새로운 도메인에 기존 학습 모델을 배포하는 경우

    • 전처리 파이프라인에서 버그가 발생하는 경우

    • 외부 발생 요인(ex. covid)

  2. Gradual drift

    • 시간이 지나면서 유저 선호도가 바뀔 경우

    • 시간이 지나면서 새로운 개념의 ex. 말뭉치가 도입되는 경우

  3. Periodic drift

    • 계절 요인이 존재할 경우

    • 학습시 사용했던 시간대와 다른 시간대를 이용할 경우(ex. 오전 - 오후)

  4. Temporary drift

    • 악의적인 유저가 모델을 공격하는 경우

    • 인구통계학적으로 다르게 분류된 유저가 제품을 사용한 후 이탈한 경우

모니터링 방법

  • 다양한 유형의 drift가 발생했을 때, 시나리오별로 대응 체계를 구축해야 함

  • 핵심은 어떻게 drift를 판단할 수 있는지?

  • 가장 간단하게는 target Y가 존재하는 경우 모델 성능의 변화를 보고 drift 여부를 탐지할 수 있음

  • 또는 분포에 대한 통계 검정, 거리 측도 등을 통해 분포의 유사성을 판단할 수 있음

  • 또는 Statistical process control을 통해 drift 발생 유무를 탐지할 수 있음

Divergence metrics

  • 실제 모니터링 상황에서는 Y가 없는 경우가 빈번함

  • Y가 없을 때는 성능으로 drift를 탐지할 수 없고, 분포의 유사성을 측정하여 drift를 탐지해야 함

  • 이 때 사용하는 것이 divergence metric임

  • Rule-based distance

    • min, max, mean 등의 통계량을 비교
  • f-divergence 기반

    • KL-divergence
    • Jensen-shannon divergence
    • Hellinger divergence
    • etc..

Example

import pandas as pd 
import numpy as np 

from sklearn.datasets import load_iris

# distance metrics 
from scipy.spatial.distance import jensenshannon
from scipy.special import rel_entr
from scipy.stats import chi2_contingency, ks_2samp, kstwo, wasserstein_distance

Example data

data = load_iris()
iris_data = pd.DataFrame(np.c_[data.data, data.target], columns=data.feature_names + ['target'])
iris_two = iris_data[iris_data.target!= 2]
iris0 = iris_two[iris_two.target==0]

# Divide the data into two set _1 and _2
iris0_1 = iris0.iloc[:25]
iris0_2 = iris0.iloc[25:]


data = iris0_2.iloc[:, 0]
reference_data = iris0_1.iloc[:, 0]

Histogram 생성

  • 분포 생성 방법은 가장 간단하게는 histogram부터 kernel density 등 다양한 방법이 있음

  • 이 중 히스토그램을 이용해서 분포를 생성함

    • 히스토그램에서 bin을 나누는 방식도 다양한 방법이 있음

      • “scott”, “sturges”, “fd”, “doane”, .. etc
    • 이 중 non-normal data에 비교적 성능이 좋은 “donna” 방법 이용

      • drift 탐지 관련 패키지인 nannyml에서도 이 방법을 이용함

nh=1+log2(n)+log2(1+|g1|σg1)g1=mean[(xμσ)3]σg1=6(n2)(n+1)(n+3)

def make_hist(reference_data, data):
    len_reference = len(reference_data)
    bins = np.histogram_bin_edges(reference_data, bins='doane')
    reference_proba_in_bins = np.histogram(reference_data, bins=bins)[0] / len_reference 

    len_data = len(data)
    data_proba_in_bins = np.histogram(data, bins=bins)[0] / len_data # reference data 기준 bins 

    leftover = 1 - np.sum(data_proba_in_bins) 
    if leftover > 0:
        data_proba_in_bins = np.append(data_proba_in_bins, leftover)
        reference_proba_in_bins = np.append(reference_proba_in_bins, 0)

    return reference_proba_in_bins, data_proba_in_bins

f divergence

Df(P||Q)=q(x)f(p(x)q(x))

KL-divergence

KL(P||Q)=p(x)log(p(x)q(x))

def kl_divergence(reference_data, data):
    """
    참고 : https://github.com/NannyML/nannyml/blob/3c6504660f2fb301e549bdf80ca56c4b114fba06/nannyml/drift/univariate/methods.py#L260
    from scipy.special import rel_entr
    """  
    
    P, Q = make_hist(reference_data, data)
    
    epsion = 0.000001
    P = P + epsion
    Q = Q + epsion

    vec = rel_entr(P, Q)
    distance = np.sum(vec)
    return distance

kl_divergence(reference_data, data)
1.5021860165248588

정규분포일 때, KL-divergence

[log(p(x))log(q(x))]p(x)dx=[12log(2π)log(σ1)12(xμ1σ1)2+12log(2π)+log(σ2)+12(xμ2σ2)2]×12πσ1exp[12(xμ1σ1)2]dx={log(σ2σ1)+12[(xμ2σ2)2(xμ1σ1)2]}×12πσ1exp[12(xμ1σ1)2]dx=E1{log(σ2σ1)+12[(xμ2σ2)2(xμ1σ1)2]}=log(σ2σ1)+12σ22E1{(Xμ2)2}12σ12E1{(Xμ1)2}=log(σ2σ1)+12σ22E1{(Xμ2)2}12=log(σ2σ1)+12σ22[E1{(Xμ1)2}+2(μ1μ2)E1{Xμ1}+(μ1μ2)2]12=log(σ2σ1)+σ12+(μ1μ2)22σ2212.
def gaussian_kl_divergence(reference_data, data): 
    
    epsion = 0.000001
    P = reference_data + epsion
    Q = data + epsion

    mu1 = np.mean(P)
    mu2 = np.mean(Q)

    sig1 = np.std(P)
    sig2 = np.std(Q)

    mu_diff = pow(mu1 - mu2, 2)
    sig_diff = sig1**2 - sig2**2

    distance = np.log(sig2/sig1) + (mu_diff + sig_diff)/(2*sig2**2)
    return distance

gaussian_kl_divergence(reference_data, data)
0.10386846525275067

Exponential divergence

Ex=p(x)log2(p(x)q(x))

def exponential_divergence(reference_data, data):
   
    P, Q = make_hist(reference_data, data)
    
    epsion = 0.000001
    P = P + epsion
    Q = Q + epsion

    distance = np.sum(P*(np.log(P/Q))**2)
    return distance


exponential_divergence(reference_data, data)
16.544668384201483

Pearson divergence

pr=q(x)(p(x)q(x)1)2

def pearson_divergence(reference_data, data):
   
    P, Q = make_hist(reference_data, data)
    
    epsion = 0.000001
    P = P + epsion
    Q = Q + epsion

    distance = np.sum(Q*(((P/Q)-1)**2))
    return distance


pearson_divergence(reference_data, data)
14400.29444211036

Squared hellinger divergence

Sh=q(x)(p(x)q(x)1)2

def hellingar_distance(reference_data, data):
    """
    참고 : https://github.com/NannyML/nannyml/blob/3c6504660f2fb301e549bdf80ca56c4b114fba06/nannyml/drift/univariate/methods.py#L260
    distance = np.sqrt(np.sum((np.sqrt(P) - np.sqrt(Q)) ** 2)) / np.sqrt(2)
    """
    P, Q = make_hist(reference_data, data)
    
    epsion = 0.000001
    P = P + epsion
    Q = Q + epsion

    distance = np.sum(Q*((np.sqrt(P/Q)-1)**2))
    return distance


hellingar_distance(reference_data, data)
0.30639829306375294

Jeffrey divergence

Jef=(p(x)q(x))logp(x)q(x)

def jeffrey_distance(reference_data, data):

    P, Q = make_hist(reference_data, data)
    
    epsion = 0.000001
    P = P + epsion
    Q = Q + epsion

    distance = np.sum((P - Q)*np.log(P/Q))
    return distance

jeffrey_distance(reference_data, data)
3.4329079921766494

Renyi divergence

Ri=1α1log(p(x)αq(x)α1),0<α<inf

  • renyi divergence는 kl divergence의 일반화 꼴

  • α=1일 때 Kl-divergence

def renyi_distance(reference_data, data, alpha):

    """
    참고 : https://en.wikipedia.org/wiki/R%C3%A9nyi_entropy
    """

    P, Q = make_hist(reference_data, data)
    
    epsion = 0.000001
    P = P + epsion
    Q = Q + epsion

    if alpha < 0: 
        raise ValueError("'number' must be positive")
    
    if alpha == 1: 
        raise ValueError("'number' cannot be 1")

    distance = 1/(alpha -1)*np.sum(np.log(P**alpha) - np.log(Q**(alpha-1)))
    return distance

renyi_distance(reference_data, data, alpha = 0.01)
25.52115244332236

Chernoff divergence

Ch=log(p(x)αq(x)α1),0α1

def chernoff_distance(reference_data, data, alpha):
     
    """
    https://threeplusone.com/pubs/on_information.pdf
    """

    P, Q = make_hist(reference_data, data)
    
    epsion = 0.000001
    P = P + epsion
    Q = Q + epsion

    if alpha < 0: 
        raise ValueError("'number' must be positive")
    
    if alpha > 1: 
        raise ValueError("'number' must be less than 1")
    
    #distance = 4/(1 - alpha**2)*np.sum(Q*(1 - (Q/P)^((1+alpha)/2)))
    distance = -np.log(np.sum((P**alpha)/(Q**(alpha-1))) )
    return distance

chernoff_distance(reference_data, data, alpha = 0.01)
0.018358570378002852

Alpha-Beta divergence

AB=1αβ(p(x)αq(x)βαα+βp(x)α+ββα+βq(x)α+β)

def alpha_beta_distance(reference_data, data, alpha, beta):
    
    """
    https://arxiv.org/pdf/1805.01045.pdf
    """
    
    P, Q = make_hist(reference_data, data)
    
    epsion = 0.000001
    P = P + epsion
    Q = Q + epsion
    
    distance = (-1/(alpha*beta))*np.sum((P**alpha*Q**beta) - (alpha/(alpha + beta))*(P**(alpha + beta)) - (beta/(alpha + beta))*(Q**(alpha + beta)))
    return distance

alpha_beta_distance(reference_data, data, alpha = 0.01, beta = 0.02)
111.42684257864133

Jensen shannon divergence

def js_divergence(reference_data, data):

    P, Q = make_hist(reference_data, data)
    
    epsion = 0.000001
    P = P + epsion
    Q = Q + epsion

    distance = jensenshannon(P, Q, base=2)
    return distance

js_divergence(reference_data, data)
0.3999777589033326

Total variance divergence

Tv=12|p(x)q(x)|

def total_variation_distance(reference_data, data):

    P, Q = make_hist(reference_data, data)
    
    epsion = 0.000001
    P = P + epsion
    Q = Q + epsion

    distance = 0.5 * np.sum(np.abs(P - Q))
    return distance

total_variation_distance(reference_data, data)
0.27999999999999997

Statistical process control

  • 새로 들어온 데이터에 대해 사전에 정의한 오류율과 기준으로 drift를 감지하는 방법

    • Drift detection method(DDM)

      • 각 데이터 샘플에 대한 예측 오류를 베르누이 확률변수로 나타내고, n 개 중에 발생한 오류의 수의 비율을 나타내는 오류율의 평균에 대한 신뢰구간 추정을 통해 오류율이 급격하게 증가하는 부분을 탐지

      • warning level : pt+stpmin+2smin,pt:prob of misclassification,si:std

      • change level : pt+stpmin+3smin

      • 오류율이 천천히 변화할 경우 감지 성능이 떨어짐

    • Early drift detection method(EDDM)

      • DDM에서 정의한 오류 횟수 대신에 두 오류 사이의 거리를 이용하여 gradual drift에 대한 탐지

      • warning level : (pt+2st)(pmax+2smax)<α=0.9

      • EDDM은 gradual drift에 대한 변화 탐지에 주로 활용됨

    • CUMSUM test

      • input data x1,,xt

        g0=0gt=max(0,gt1+(xtv)),v:parameter(given)

      • gt>λ일 경우 change point로 탐지, gt=0으로 초기화(λ : threshold(given))

        • v,λ에 따라 성능이 유동적임
    • page-hinkley test : CUMSUM test에서 파생된 test

      • mT=t=1T(xtx¯Tδ),x¯T=1Tt=1txt,δ:허용되는 변화의 크기(given)

      • MT=min(mt,t=1,,T)

      • test monitors : PHT=mTMT>λ,λ:threshold(given)

        • λ를 작게 설정할 경우 거의 모든 change point를 감지할 수 있지만, 잘못 감지할 확률이 증가
      • 이전 데이터와 새로 들어온 데이터 간에 연관성이 작을 수 있음

      • mt를 정의할 때 fading factor를 도입함

        • mT=fadingFactor×mT+(xtx¯Tδ),fadingFactor:[0,1](parameter(given)

Time data based method

  • ADWIN : window 내에 두 개의 subwindow를 비교하면서 두 개의 subwindow가 사전에 정한 ϵc만큼 충분히 다르다면 concept drift가 존재한다고 판단하는 알고리즘

    book : Anomaly detection through stream processing, Knowledge Discovery from Data Streams
    • m=21|W0|+1|W1|

    • ϵcut=12mln4|W|δ

    paper : Scalable Detection of Concept Drifts on Data Streams with Parallel Adaptive Windowing

그림을 통해 보면 정해진 window W 에서 두 개의 subwindow를 나눈다. 각 subwindow에서 μ^W0μ^W1을 계산한다. subwindow를 한 칸씩 sliding해나가면서 |μ^W0μ^W1|ϵc 조건을 만족할 때까지 반복한다. 조건을 만족할 경우 W의 head 값(old data)을 삭제한다. 문제는 subwindow를 조합별로 계산해야 하므로 계산 효율성이 매우 떨어진다.

참고 자료

MLops 관련

page-Hinkley and ADWIN

Citation

BibTeX citation:
@online{don2024,
  author = {Don, Don and Don, Don},
  title = {Drift Detection Method},
  date = {2024-03-09},
  url = {https://dondonkim.netlify.app/posts/2022-03-01-distance/distance.html},
  langid = {en}
}
For attribution, please cite this work as:
Don, Don, and Don Don. 2024. “Drift Detection Method.” March 9, 2024. https://dondonkim.netlify.app/posts/2022-03-01-distance/distance.html.