정현석

개인 저장공간입니다.
Since 2021.10

7 분 소요

image

“Scalable Detection of Concept Drifts on Data Streams with Parallel Adaptive Windowing” 논문을 정리하고 리뷰한 글이다.1

고속 데이터 스트림 환경에서 머신러닝 모델의 예측 정확도를 유지하려면 통계적 분포 변화를 실시간으로 탐지하는 컨셉 드리프트(Concept Drift) 대응이 필수적이다. 대표적 윈도우 기반 적응 기법인 ADWIN(Adaptive Windowing)은 엄밀한 통계적 보장을 제공하지만, 튜플 유입마다 수행되는 윈도우 분할 검정으로 인해 처리량(throughput)이 급감하는 병목을 안고 있다. 저자들은 ADWIN의 내부 구조를 프로파일링하여 병목 지점을 특정하고, 낙관적 디커플링(Decoupling) 및 다중 스레드 병렬 검정 기법을 설계하여 대규모 스트림 환경에서도 확장 가능한 Parallel ADWIN을 제안한다.

논문 출처 : Grulich, Philipp M., et al. “Scalable Detection of Concept Drifts on Data Streams with Parallel Adaptive Windowing.” EDBT. 2018.

1. Introduction

실시간 스트림(stream) 분석 환경에서는 머신러닝(ML) 모델을 지속적으로 학습하고 유입 데이터에 즉시 적용하는 파이프라인이 보편화되고 있다. 하지만 실세계 환경에서는 시간이 흐름에 따라 데이터의 기저 분포가 변하는 컨셉 드리프트(concept drift)가 발생하여 학습된 모델과 현실 데이터 사이에 불일치(discrepancy)가 생긴다.

이러한 통계적 불일치는 모델의 예측 성능을 급격히 떨어뜨리므로, 스트림 처리 엔진은 초당 수십만 건의 데이터를 처리하면서도 드리프트를 즉각 감지하고 모델을 적응(adaptation)시킬 수 있는 고성능 솔루션을 요구한다.

컨셉 드리프트에 대처하는 가장 단순한 접근법은 고정 크기의 슬라이딩 배치 데이터를 모아 주기적으로 모델을 재학습하는 나이브(naive) 방식이다. 하지만 이러한 정기적 재학습은 현실 스트림 환경에서 다음과 같은 한계에 부딪힌다.

  1. 감지 지연: 재학습 주기 사이에 발생한 급격한 드리프트를 즉각 반영하지 못해 최신 데이터 구간에서 오작동한다.
  2. 오염된 윈도우: 드리프트 발생 이전의 과거 데이터가 고정 윈도우에 섞여 남아있어 재학습 모델의 성능 회복을 방해한다.

이러한 문제를 해결하기 위해 고안된 대표적 기법이 가변 윈도우를 유지하는 ADWIN이다.

ADaptive WINdowing (ADWIN)2은 유입 데이터의 통계적 안정성에 따라 크기가 자동으로 조절되는 전역(global) 윈도우를 관리하며, 이를 기반으로 모델의 학습 데이터셋을 최신 상태로 유지한다. ADWIN은 칼만 필터(Kalman Filter), 나이브 베이즈(Naive Bayes), k-평균 군집(k-means clustering) 등 다양한 온라인 알고리즘과 결합되었으며, 배깅(bagging) 앙상블 및 공간 절약 알고리즘 변형(space saving algorithm)과도 융합되어 널리 활용되어 왔다.

하지만 대규모 데이터 스트림에서 ADWIN을 직접 구동하면 심각한 처리량 저하가 발생한다. 저자들은 ADWIN의 확장성(scalability) 병목을 분석하고 이를 극복하기 위해 병렬화를 도입한다.

본 논문의 핵심 기여는 다음과 같다.

  1. ADWIN 병목 분석: ADWIN 알고리즘 내부 연산을 정밀 분석하여 확장성을 저해하는 근본 원인이 컷 검정(cut check) 단계에 있음을 규명한다.
  2. 단일 노드 병렬화 설계: 컷 검정과 튜플 수집을 분리하는 낙관적 분리(Cut-Check Decoupling)와 히스토그램 내부 병렬화(Intra/Inter-Cut-Check)를 결합한 확장형 ADWIN을 제안한다.
  3. 성능 검증: JMH(Java Microbenchmark Harness)3 벤치마크 환경에서 지연 시간을 15µs 이하의 마이크로초 단위로 유지하면서, Optimistic ADWIN 기준 기존 오픈소스 구현4 대비 274배(최적화 순차 구현 대비 54배)의 처리량 향상을 입증한다.

결국 관건은 스트림 수집 루프에서 무거운 통계 검정을 어떻게 격리할 것인가이다.

2. Concept Drift Detection With Adaptive Windowing

ADWIN의 핵심은 데이터 분포의 정상 상태에서는 윈도우를 점진적으로 키우고, 드리프트가 포착되는 순간 과거 데이터를 신속하게 잘라내는 적응형 윈도우 메커니즘에 있다.

2.1 The ADWIN Algorithm

ADWIN은 스트림 환경에서 실시간(on the fly)으로 컨셉 드리프트를 감지하고 ML 모델의 유효 데이터 범위를 동적으로 조정하는 알고리즘이다.

  • 윈도우 확장: 컨셉 드리프트가 감지되지 않는 정상 상태에서는 새로운 튜플(tuple)이 들어올 때마다 적응형 윈도우(adaptive window)에 추가되어 윈도우 크기가 지속적으로 증가한다. 이에 따라 모델은 더 풍부한 과거 학습 데이터에 기반해 안정적으로 예측할 수 있다.
  • 윈도우 축소: 두 하위 구간 간의 분포 차이가 유의수준을 넘어서면 오래된 과거 튜플들을 윈도우에서 잘라내어 크기를 줄인다.

알고리즘의 동작 절차는 다음과 같다. 스트림 튜플(분류 대상 피처 및 레이블로 구성된 데이터 레코드)이 도착하면 먼저 윈도우에 해당 튜플을 삽입한다. 이어서 적응형 윈도우 내부 데이터를 분석하여 컨셉 드리프트 발생 여부를 검사한다.

구체적으로 ADWIN은 Figure 1과 같이 윈도우를 두 개의 슬라이딩 하위 윈도우(sliding subwindows)로 분할할 수 있는 모든 가능한 조합을 순회한다. 두 하위 윈도우의 평균값 분포 차이가 호프딩 부등식(Hoeffding bound) 기반의 임계값을 초과하면 컨셉 드리프트로 판정하고, 과거 하위 윈도우에 속한 튜플들을 삭제한다. 이를 컷 감지(cut detection)라 부르며, 오래된 과거 데이터를 잘라낼 지점을 결정하는 핵심 연산이다.

image

2.2 Exponential Histograms

모든 튜플마다 원시 데이터를 그대로 유지하며 하위 윈도우의 전수 분할을 검사하는 나이브 ADWIN 구현은 큰 메모리와 연산 비용을 초래한다. 이를 해결하기 위해 ADWIN은 지수 히스토그램(exponential histogram)5을 핵심 내부 자료구조로 채택한다.

image

지수 히스토그램은 유입 튜플들을 기하급수적 크기를 갖는 버킷(bucket)으로 압축하여 관리한다.

  • 계층적 버킷 할당: 최근 유입된 데이터 구간에는 소수의 튜플만을 담는 작은 버킷을 배치하고, 과거로 갈수록 기하급수적(exponential)으로 증가하는 크기의 버킷을 배치한다. (Figure 2의 1단계)
  • 요약 통계량 유지: 각 버킷은 개별 원시 튜플 대신 튜플들의 합산(sum)과 분산(variance) 통계량만을 저장한다. (Figure 2의 2단계)
  • 로그 스케일 메모리 절감: 적응형 윈도우의 전체 크기가 커지더라도 관리해야 할 버킷의 수와 메모리 사용량은 대수적(logarithmically)으로 완만하게 증가한다.

이에 따라 컷 검정(cut check) 절차는 개별 원시 레코드를 전수 비교할 필요 없이 압축된 버킷 단위의 통계량만을 순회하며 평균 차이를 검정할 수 있게 된다.

지수 히스토그램을 포함한 ADWIN 알고리즘의 전체 실행 파이프라인 개요는 Figure 3과 같다.

image

2.3 Initial Performance Analysis

지수 히스토그램으로 메모리와 연산 복잡도를 로그 스케일로 압축했음에도 불구하고, 단일 스레드 기반의 기존 ADWIN은 고속 스트림 환경에서 뚜렷한 성능 한계를 노출한다.

image

프로파일링 결과 전체 수행 시간의 대부분은 튜플 삽입이 아닌 컷 검정(cut check) 루프에서 소비된다. 버킷 순회 검정이 끝날 때까지 새로운 튜플의 유입 처리가 블로킹되므로 스트림 처리 엔진의 병목으로 직결된다.

3. Parallel Adaptive Windowing

ADWIN의 처리량(throughput)을 확장하기 위해서는 병목의 근원인 컷 감지(cut detection) 연산을 수집 파이프라인과 분리하고 병렬화해야 한다.

2.3절의 프로파일링 분석에서 확인했듯 전체 지연의 대부분은 컷 검정에서 발생하므로, 본 논문은 단일 노드 다중 코어 환경에서 cut detection을 다각도로 병렬화하는 세 가지 핵심 기법을 제안한다.

3.1 Single-Node Parallelization

image

Figure 4의 의사코드는 단일 노드에서 튜플 수집과 컷 검사를 동시 수행하기 위한 병렬화 아키텍처의 전체 흐름을 요약한다. 병렬화는 상호 보완적인 세 단계 계층으로 구성된다.

  • 3.1.1 Cut-Check Decoupling: 컷 검정 연산이 튜플 수집 루프를 블로킹하지 못하도록 히스토그램 업데이트와 컷 검정 스레드를 완전히 분리한다.
  • 3.1.2 Intra-Cut-Check Parallelization: 단일 컷 검정 절차 내부에서 두 개의 작업 스레드가 히스토그램 양 끝에서 탐색을 진행하도록 분할한다.
  • 3.1.3 Inter-Cut-Check Parallelization: 드리프트 감지 후 연속 컷이 발생하는 상황을 대비해 여러 단계의 컷 검정을 동시에 투기적으로 실행한다.

3.1.1 Cut-Check Decoupling

고속 빅데이터 스트림 환경에서는 대부분의 입력 튜플 구간에서 컨셉 드리프트가 발생하지 않는다는 통계적 안정성 특성을 지닌다. 저자들은 이 점에 착안하여 낙관적(optimistic) 병렬화 전략을 도입한다.

기존 ADWIN은 신규 튜플로 지수 히스토그램을 갱신하는 작업과, 컷 검정 절차를 통해 드리프트를 탐지하는 작업을 단일 스레드에서 순차적으로 실행한다. 이로 인해 매 튜플마다 컷 검정이 완료될 때까지 신규 튜플 유입 처리가 중단되어 전체 처리량이 급감한다.

image

Optimistic ADWIN은 히스토그램 갱신 루프와 컷 검사 루프를 분리된 스레드로 격리하여 수집 블로킹을 해소한다.

주 스레드(primary thread)는 주 히스토그램(primary histogram)과 redo 로그에 유입 튜플을 논블로킹으로 계속 추가하고, 컷 검사 스레드는 독립된 스냅샷(snapshot) 히스토그램 위에서 비동기로 컷 탐지를 수행한다. 구체적인 동작 흐름은 다음과 같다.

  • Step 1 (스냅샷 복사): 별도 워커 스레드가 주 히스토그램의 깊은 복사본(deep copy)인 스냅샷 히스토그램을 생성한다.
  • Step 2 (비동기 컷 검정): 컷 검사 스레드는 주 스레드의 튜플 수집을 방해하지 않고 스냅샷 히스토그램에 대해 독립적으로 컷 검사를 수행한다.
  • Step 3 (롤백 및 리플레이): 컨셉 드리프트가 감지되면 주 히스토그램을 컷 검정에 의해 분할·정리된 스냅샷으로 교체하는 롤백을 수행한 뒤, redo 로그에 쌓인 신규 튜플들을 다시 재생(replay)하여 주 히스토그램에 반영한다.

이러한 분리 구조 덕분에 주 스레드는 컷 검사 지연 없이 최대 속도로 튜플을 수집할 수 있다. 다만 스냅샷 생성부터 컷 감지 및 롤백이 완료될 때까지 약간의 감지 통지 대기시간(latency)이 수반되는 트레이드오프가 존재한다.

결국 검정 비동기화로 수집 처리량 병목을 해소한 셈이다.

3.1.2 Intra-Cut-Check Parallelization

스레드를 분리하더라도 개별 컷 검정 자체의 수행 시간이 길어지면 스냅샷과 주 히스토그램 사이의 차이가 벌어져 롤백 비용이 증가한다. 따라서 단일 컷 검정 절차 자체를 다중 스레드로 가속하는 기법이 필요하다.

image

기존의 단일 스레드 컷 검사는 히스토그램의 가장 오래된 버킷(끝부분)부터 시작하여 최신 버킷(시작부분) 방향으로 순차 탐색을 진행한다. 두 하위 윈도우의 평균 차이를 계산하기 위해 버킷들의 누적 합과 분산 통계량을 집계하며 순회한다.

여기서 각 분할 지점에 대한 호프딩 검정은 이전 단계의 계산 결과에 종속되지 않고 독립적으로 판정될 수 있다는 점에 주목하여 하프컷 애드윈(Half-Cut ADWIN)을 도입한다.

  • 양방향 동시 탐색: 히스토그램의 전체 집계 통계량이 사전에 계산되어 있으므로, 두 개의 스레드가 히스토그램의 양 끝(가장 오래된 구간과 중간 지점)에서 동시에 순회를 시작할 수 있다.
  • 조기 종료 조건: 두 스레드가 서로의 탐색 경계인 중간 지점에 도달하거나, 어느 한 스레드라도 유효한 컷을 발견하면 즉시 검정을 종료한다.

이처럼 단일 검정 작업을 반으로 쪼갬으로써 개별 컷 검사 소요 시간을 절반 수준으로 단축한다.

3.1.3 Inter-Cut-Check Parallelization

드리프트가 감지되었을 때 단일 컷으로 끝나지 않고 연속적인 윈도우 축소가 요구되는 워크로드를 위해, 검정 절차 간의 병렬성을 활용하는 기법도 지원한다.

ADWIN이 유효한 컷을 포착하면 히스토그램에서 가장 오래된 버킷을 제거한 뒤 추가적인 드리프트 지점이 존재하는지 확인하기 위해 다음 컷 검사를 연속해서 수행한다. 이러한 반복 제거 과정을 예측하여 저자들은 비관적(pessimistic) 다중 컷 병렬화를 설계한다.

  • 투기적 연속 컷 검정: 스레드 1이 전체 버킷 $1 \dots n$에 대해 1차 컷 검사를 수행하는 동안, 스레드 2는 이전 버킷이 제거될 것을 미리 상정하고 버킷 $2 \dots n$에 대해 다음 컷 검사를 동시에 수행한다.
  • 다중 검정 확장: 이는 버킷 제거 단계마다 독립적인 워커를 할당하여 최대 $n - 1$개의 병렬 컷 검사 파이프라인으로 확장될 수 있으며, 각 검정 파이프라인 내부에는 다시 3.1.2절의 Half-Cut ADWIN을 결합할 수 있다.

4. 핵심 요약 및 시사점

4.1 성능 평가 결과

논문은 Intel Core i5-4210U 프로세서와 8GB RAM 환경에서 JMH(Java Microbenchmark Harness)3를 활용하여 4가지 ADWIN 변형의 처리량과 감지 지연 시간을 측정했다.1

  • 처리량(Throughput): C++ 메모리 최적화를 적용한 순차 재구현(Optimized Sequential)은 기존 MOA 오픈소스 구현4 대비 평균 5배 향상되었다. 컷 검정 내부를 2개 스레드로 양방향 분할한 Half-Cut ADWIN은 기존 대비 10배(순차 재구현 대비 약 2배)의 처리량을 달성했다. 수집과 검정을 완전히 분리한 Optimistic ADWIN은 Half-Cut 대비 27배, 순차 재구현 대비 54배, 기존 오픈소스 구현 대비 274배의 처리량 향상을 기록하며 초당 $10^7$건 수준의 튜플 처리를 유지했다. 기존 구현은 히스토그램 크기가 커질수록 처리량이 급감하지만, Optimistic ADWIN은 히스토그램 크기와 독립적인 처리량 확장성을 보였다.
  • 감지 지연 시간(Latency): 신규 병렬화 기법들은 기존 구현 대비 컷 검정 지연 시간을 최소 50%에서 최대 90%까지 단축했다. 별도 스냅샷이나 동시성 제어 오버헤드가 없는 Half-Cut ADWIN이 가장 낮은 지연 시간(~3µs)을 기록했다.

4.2 한계 및 트레이드오프

Parallel ADWIN의 성능 향상에는 다음과 같은 구조적 제약과 트레이드오프가 수반된다.1

  1. 감지 지연 편차: Optimistic ADWIN은 주 히스토그램과 스냅샷 간 비동기 분리로 인해 튜플 유입 시점과 다음 스냅샷 검정 시작 시점 사이에 최대 10µs 수준의 대기 지연 편차가 발생하며, 최악의 경우 지연 시간이 약 2배로 증가할 수 있다.
  2. 다중 노드 클러스터 확장 한계: 논문의 분산 클러스터 실험 결과, 네트워크 대역폭 제약 하에서 히스토그램 복제 및 다중 버전 동시성 제어(MVCC) 조정 오버헤드가 처리 연산보다 커져 노드 추가에 따른 선형 확장이 저해되었다.
  3. 메모리 오버헤드: 주 히스토그램 외에 스냅샷 복사본과 redo 로그 버퍼를 동시 유지해야 하므로, 단일 인플레이스(in-place) 구조를 취하는 기존 ADWIN 대비 메모리 점유량이 증가한다.

4.3 종합 평가

Parallel ADWIN은 엄밀한 수학적 오차 한계를 보장하는 ADWIN의 통계적 강점을 유지하면서도, 병렬화 아키텍처를 결합해 실시간 대규모 데이터 스트림 환경에서의 실용성을 확립한 연구이다.

  • 병목 격리 (Decoupling): 튜플 유입 루프와 컷 검정 루프를 주 히스토그램과 스냅샷으로 분리하여 고속 스트림 수집 성능을 저해하지 않는 비차단 파이프라인을 구축했다.
  • 계층적 병렬화 (Intra & Inter): Half-Cut 기법을 통한 단일 검정 2분할 가속과, 다중 버킷 제거를 상정한 투기적 병렬 검정을 결합하여 검정 지연을 최소화했다.
  • 실세계 스트림 적용성: 지수 히스토그램의 대수적 메모리 절감 효과에 병렬 처리량을 더함으로써 초당 수백만 건의 튜플이 유입되는 스트림 환경에서도 실시간 컨셉 드리프트 대응을 가능하게 했다.

References

  1. Philipp M. Grulich, René Knaebel, Tilmann Rabl, Volker Markl. “Scalable Detection of Concept Drifts on Data Streams with Parallel Adaptive Windowing.” In Proceedings of the 21st International Conference on Extending Database Technology (EDBT), pages 313–316, 2018. DOI: 10.5441/002/edbt.2018.28 ↩ ↩2 ↩3

  2. Albert Bifet, Ricard Gavaldà. “Learning from Time-Changing Data with Adaptive Windowing.” In Proceedings of the 2007 SIAM International Conference on Data Mining (SDM), pages 443–448, 2007. DOI: 10.1137/1.9781611972771.42 ↩

  3. OpenJDK. “Java Microbenchmark Harness (JMH).” OpenJDK JMH Project ↩ ↩2

  4. Albert Bifet, Geoff Holmes, Richard Kirkby, Bernhard Pfahringer. “MOA: Massive Online Analysis.” Journal of Machine Learning Research, 11:1601–1604, 2010. GitHub: abifet/adwin ↩ ↩2

  5. Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani. “Maintaining Stream Statistics over Sliding Windows.” SIAM Journal on Computing, 31(6):1794–1813, 2002. DOI: 10.1137/S0097539701398363 ↩

댓글남기기

참고