<Extremely Fast Hoeffding Adaptive Tree (EFHAT)> 논문 스터디

[스터디 기록] Extremely Fast Hoeffding Adaptive Tree (EFHAT) — “빠르게 배우고, 빠르게 갈아치운다”

한 문장 요약: EFHAT은 “빠른 학습(EFDT의 eager split) + 빠른 드리프트 회복(HAT의 변화 감지·대체)”를 충돌 없이 결합해, 드리프트가 있든 없든 온라인 트리에서 높은 예측 성능을 안정적으로 끌어낸다.

 

1) 맥락부터 잡기: VFDT → EFDT → HAT → EFHAT

온라인 결정트리 계보를 한 줄로 그리면 이렇다.

• VFDT(Hoeffding Tree): 분할을 “아주 보수적으로” 늦게 한다. 후보 속성들 중 진짜 1등이 맞다는 충분증거가 쌓일 때까지 기다린다. 장점은 안정성, 단점은 구조 형성 속도가 느림.
• EFDT: 반대로, eager split(조금 위험하지만 빠른 분할)을 택한다. “지금 분할하지 않는 것보다 낫다”가 통계적으로 보이면 일단 분할하고, 나중에 더 나은 속성이 보이면 **revision(분할 교체)**로 갈아치운다. 정상(정적) 스트림에선 VFDT보다 훨씬 통계적 효율성이 높다.
• HAT: VFDT의 보수적 분할에 드리프트 감지(ADWIN 등) + 대체 서브트리(alternate) 성장을 붙였다. 비정상(드리프트) 스트림에서 지금까지의 표준이었다. 강점은 빠른 드리프트 대응이지만, 분할 자체는 보수적이라 학습 속도는 EFDT보다 느림.

EFHAT의 발상: “EFDT처럼 빨리 배우되, HAT처럼 빨리 갈아치우자.” 그런데 그대로 합치면 충돌이 생긴다. **EFDT의 revision(분할 교체)**가 HAT의 드리프트 감지(에러 급변)와 상호작용해 가짜 알람을 촉발시키고, 쓸데없이 서브모델을 버리는 부작용이 생긴다.
해결: EFDT의 eager split만 가져오고, revision은 과감히 버린다. 그리고 서브트리 교체는 HAT의 에러 기반 변화 감지만으로 수행한다. 결과는 “더 빠른 구조 형성 + 정확한 순간에만 대체”다.

---

2) 왜 EFDT의 revision을 버리나? (핵심 통찰)

논문이 밝히는 핵심 포인트는 세 가지다.

1. EFDT-revision × HAT-change의 충돌
   EFDT의 상시 revision은 분포가 천천히 바뀔 때 유효하지만, 드리프트 환경에서는 이 교체시도가 HAT의 에러 기반 변화 감지를 자주 건드려 불필요한 대체를 유발한다. 결과적으로 쌓아둔 구조(경험)를 자주 잃는다.
2. 드리프트 상황: “완벽하게 늦게”보다 “충분히 좋게 빨리”
   드리프트에서 중요한 건 “완벽한 분할을 찾는 것”이 아니라 새 분포에 빨리 적응하는 것이다. 즉, good-enough fast > perfect slow.
3. 역할 분담의 재정의

• EFDT의 revision은 “장기적으로 배치 최적 트리에 가까운 구조”를 추구(정상 분포 가정).
• HAT의 대체는 “지금 분포에 더 잘 맞는 구조”를 추구(드리프트 가정).
  → 드리프트에선 후자(지금-적합)가 본질.

그래서 EFHAT은 EFDT의 eager split만 남기고 revision은 제거한 뒤, HAT의 에러 기반 대체만으로 구조를 갱신한다. 이렇게 하면 충돌이 사라지고, 학습 속도(구조 형성)와 회복 속도(대체 타이밍)를 동시에 잡는다.

3) 수식은 어디에 쓰였나: Hoeffding Bound의 ‘분할 스위치’

VFDT/HAT/EFDT 공통의 수학적 기둥은 Hoeffding 부등식이다.

 

​​

• n: 현재 노드에 누적된 표본 수
• R: 분할 지표(IG, Gini 등)의 범위
• δ: 실패 확률 (신뢰도 1−δ1-\delta1−δ)
• ϵ: “지금 이 정도 표본이면 분할 결정을 해도 된다”를 알려주는 문턱값

의미:

• VFDT/HAT: 1등과 2등 속성 차이 ΔG>ϵ이면 분할(보수적: 1등이 진짜 1등임을 충분 보증해야).
• EFDT/EFHAT: 1등 속성이 “분할 안 하는 것보다 낫다”가 ϵ\epsilonϵ을 넘으면 분할(공격적: 지금 나은 선택이면 진행, 나중에 더 좋으면 교체… 단, EFHAT은 이 교체를 HAT의 드리프트 대체 쪽에만 맡긴다).

결국 ϵ은 언제 분할 스위치를 켤지를 정량화해 준다. 표본이 많아질수록 ϵ은 줄어들고, 분할은 더 자주 촉발된다.

 

 

4) EFHAT의 동작 알고리즘: “빨리 자라고, 적시에 갈아치우는” 루프

• 노드에서 분할: EFDT의 eager split 규칙으로 빨리 분할한다(학습 속도↑).
• 오류 감시(ADWIN): 프리퀀셜 에러 시계열을 감시해 변화(드리프트)를 감지한다(파라미터프리).
• 대체 서브트리 성장: 변화가 감지된 노드에 대체 서브트리를 즉시 키운다.
• 교체: 대체 서브트리가 현재 오류 기준으로 더 낫다고 판단되면 갈아끼운다.

핵심은 EFDT의 분할 교체(revision) 루프는 제거했다는 점. “교체”는 오롯이 HAT의 에러 기반 대체에 맡긴다. 덕분에 쓸데없는 가짜 알람과 헛된 교체를 피한다.

구현 관점: EFHAT은 시간·공간 복잡도가 HAT와 동일하다(분할 교체 루프를 제거했으므로), 대신 분할 트리거만 EFDT 방식으로 바뀐다.

 

 

5) 이해 관점 — 왜 EFHAT이 설득력 있나

1. 학습 속도(구조 형성)
   드리프트가 반복되는 실제 스트림에선 얼마나 빨리 분기 구조를 세우느냐가 성능의 절반을 결정한다. EFHAT은 EFDT의 eager split 덕에 구조가 빨리 생겨서 “초기 적응”이 빠르다.
2. 회복 속도(대체 타이밍)
   변화 시점에 딱 맞춰 대체 서브트리를 키우고, 현재 에러 기준으로 바꿔 끼우는 HAT의 메커니즘 덕에 회복 지연이 줄어든다. EFDT의 상시 revision은 이 타이밍을 흐리게 만들 수 있다.
3. 충돌 제거
   EFDT의 revision 루프를 뗌으로써 HAT의 변화 감지와 충돌(가짜 알람, 서브모델 소실)을 제거했다. “빠르게 배우되, 바꿀 때만 바꿔라”는 분업이 명확해졌다.
4. 복잡도·현업성
   EFHAT은 HAT와 동일한 시간·공간 복잡도를 유지하면서, 드리프트·정상 양쪽 모두에서 준수하다. “환경이 불확실한 스트림 기본 옵션”으로 적합하다.

 

 

6) 덧붙임: Hoeffding 수식의 감각을 현업에 대입하면

• δ를 작게 잡을수록(신뢰 ↑) ϵ이 커져 분할이 더 늦어진다(보수적).
• n이 늘면 ϵ이 줄어 분할이 더 빨라진다(데이터가 많아지니 결정을 당겨도 됨).
• R을 줄이면(지표 범위를 좁히거나 정규화) ϵ이 줄어 분할이 빨라진다.

EFHAT의 설계는 이 분할-트리거를 eager(“안 하는 것보다 낫다”) 기준으로 땡겨 놓고, 교체는 HAT의 에러 기반으로만 수행해 분할-교체의 두 스위치가 서로를 방해하지 않도록 만든 셈이다.

 

 

7) 마무리

이 논문이 전달하는 핵심은 단순하다. 스트림은 바뀐다. 바뀌면 빨리 배우고, 빨리 갈아치워야 한다. EFHAT은 그 두 가지를 충돌 없이 결합해, 드리프트가 있든 없든 온라인 트리의 기본값에 가깝게 다듬었다. 실험 결과도 이를 강하게 뒷받침한다(다수 실세계·합성 스트림에서 HAT·EFDT 대비 유의한 우위).

현업 적용 한 줄 조언: “분포가 고정인지 확신할 수 없을 때, 트리 기반 온라인 학습의 첫 선택지로 EFHAT을 고려하라. 빠르게 배우고, 필요한 순간에만 똑똑하게 갈아치운다.”