Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees

문제 제기
랜덤 포레스트 (RF) 는 표 형식 데이터 예측을 위한 지배적인 방법으로, 높은 정확도와 계산 효율성을 제공합니다. 그러나 의료, 금융과 같은 민감한 분야에서의 적용은 개별 훈련 레코드에 대한 정보 유출 위험으로 인해 방해받고 있습니다. 차분 프라이버시 (DP) 는 이러한 위험을 완화하기 위한 엄격한 프레임워크를 제공하지만, 랜덤 포레스트에 DP 를 적용하는 기존 방법들은 심각한 유틸리티 저하를 겪습니다.

현재 방법들은 일반적으로 두 가지 패러다임으로 분류되며, 둘 다 중요한 한계에 직면해 있습니다:

1. 탐욕적 트리 구성: 데이터 의존적 불순도 기준에 기반하여 분할을 선택하는 표준 의사결정 트리 알고리즘을 DP 설정에 적응시키려면 분할 선택 과정에 노이즈를 주입해야 합니다. 이 노이즈는 빠르게 누적되어 열악한 트리 구조와 낮은 유틸리티를 초래합니다.
2. 완전 랜덤 트리: "엑스트라 트리 (Extra Trees)"에서 영감을 받은 이 방법들은 트리 구조를 데이터와 무관하게 생성하고, 잎 (leaf) 에 레이블을 지정하는 데만 데이터를 사용합니다. 이는 구조 학습에 프라이버시 예산을 소모하지 않도록 하지만, 이러한 트리는 깊이에 매우 민감합니다. 얕은 트리는 지나치게 큰 잎을 초래하는 반면, 깊은 트리는 신뢰할 수 있는 프라이버시 보호 예측을 위한 충분한 샘플이 없는 잎을 생성합니다. 또한, 데이터 의존적 정지가 없기 때문에 특징 공간의 정보적 구조를 포착하지 못하고 다수 클래스 예측으로 수렴하는 경우가 많습니다.

방법론: Lumberjack
이 논문은 깊은 트리의 표현력과 차분 프라이버시의 제약 사이의 간극을 메우도록 설계된 새로운 차분 프라이버시 랜덤 포레스트 알고리즘인 Lumberjack를 소개합니다. 핵심 혁신은 대규모 완전 랜덤 트리를 구성한 후, 충분히 채워진 노드만 유지하도록 공격적이고 프라이버시를 보호하는 가지치기를 적용하는 2 단계 프로세스입니다.

• 랜덤화된 구성: Lumberjack 는 분할이 데이터와 무관하게 특징 공간에서 균일하게 무작위로 선택되는 깊은 랜덤 트리 (엑스트라 트리와 유사) 를 구축합니다. 이는 탐욕적 분할 선택과 관련된 높은 노이즈 비용을 피합니다.
• 헤비 히터 감지를 통한 프라이버시 보호 가지치기: 핵심적인 과제는 프라이버시를 위반하지 않으면서 유지될 만큼 충분한 데이터 포인트를 포함하는 노드를 결정하는 것입니다. Lumberjack 는 이를 계층적 트리 구조에 대한 헤비 히터 (heavy hitter) 감지 문제로 프레임합니다. 목표는 데이터 포인트의 수가 임계값 $\tau$를 초과하는 노드를 식별하는 것입니다.
• 새로운 헤비 히터 알고리즘: 저자들은 높이 $h$인 트리에서 헤비 히터를 감지하기 위한 새로운 $(\epsilon, \delta)$-DP 알고리즘을 제안합니다.
  • 메커니즘: $\ell_2$ 민감도가 $\sqrt{h}$로 스케일링되는 순진한 상향식 탐색 대신, 이 알고리즘은 구조화된 중첩 노이즈 이진 탐색을 수행합니다. 중간 계층의 노드를 쿼리하여 "무거운 (Heavy)"또는 "가벼운 (Light)"으로 표시합니다.
  • 전파: 트리 카운트의 단조성 (부모의 카운트는 자식의 합임) 으로 인해 "무거운"노드는 모든 조상이 무겁다는 것을 의미하고, "가벼운"노드는 모든 후손이 가볍다는 것을 의미합니다. 이를 통해 알고리즘은 트리의 상당 부분을 건너뛸 수 있습니다.
  • 민감도 감소: 이 구조를 활용함으로써 알고리즘은 $\ell_2$ 민감도를 $O(\sqrt{h})$에서 $O(\sqrt{\log h})$로 줄입니다.
  • 희소 히스토그램 통합: 깊은 트리의 모든 노드 (대부분이 비어 있음) 를 쿼리하는 계산적 비현실성을 처리하기 위해, 알고리즘은 희소 히스토그램 추정 기법을 통합합니다. 이는 충분히 작은 카운트를 가진 쿼리를 결정론적으로 "가벼운 (비어 있는)"것으로 매핑하고, 비어 있지 않을 가능성이 있는 쿼리에만 가우시안 노이즈를 추가합니다.
• 통합 프라이버시 회계: 저자들은 개별 트리 간의 표준 조합에 의존하는 대신 전체 포레스트 구성에 대한 통합 프라이버시 분석을 수행하여 더 엄격한 프라이버시 경계를 도출합니다.

주요 기여

1. Lumberjack 알고리즘: 랜덤화된 트리 구성과 데이터 의존적 가지치기를 결합한 새로운 DP 랜덤 포레스트 방법으로, 엄격한 프라이버시 예산 하에서 깊고 고유틸리티 트리의 훈련을 가능하게 합니다.
2. 새로운 헤비 히터 감지: 높이 $h$인 트리에 대해 $O_{\epsilon, \delta}(\sqrt{\log h})$의 오차 스케일링을 갖는 계층적 데이터에 대한 $(\epsilon, \delta)$-DP 헤비 히터 감지를 위한 새로운 알고리즘입니다. 저자들은 이 구성 요소가 다른 계층적 데이터 문제에 대해 독립적인 관심을 가질 수 있다고 지적합니다.
3. 이론적 분석: 표준 조합 정리의 느슨한 경계를 피하고, 깊은 트리를 지원하는 방법에 대해 $O(\sqrt{\log h})$ 스케일링이 거의 최적임을 보여주는 하한을 확립하는 엄밀한 프라이버시 분석입니다.
4. 실증적 최첨단 성능: 여러 데이터셋과 프라이버시 환경에서 Lumberjack 가 기존 DP 랜덤 포레스트 베이스라인 (DiffPrivLib, SNR, Smooth Sensitivity, 탐욕적 변형 포함) 보다 일관적으로 우월함을 입증하는 광범위한 평가입니다.

결과
저자들은 Adult 데이터셋과 Folktables (California 2018) 데이터셋의 4 가지 이진 분류 작업에서 Lumberjack 를 평가했습니다.

• 성능: Lumberjack 는 프라이버시 예산 $\epsilon \in \{0.5, 1, 2, 4, 8\}$ 전반에 걸쳐 이전 모든 DP 랜덤 포레스트 방법보다 일관적으로 우월한 성능을 보였습니다.
• 비사적 방법과의 비교: 비사적 엑스트라 트리에 비해 여전히 격차가 존재하지만, Lumberjack 는 중간 수준의 프라이버시에서도 비사적 탐욕적 의사결정 트리보다 종종 더 나은 성능을 발휘합니다.
• 베이스라인 문제: 이 논문은 많은 기존 DP-RF 베이스라인 (특히 탐욕적 트리 구성을 사용하는 것들) 이 데이터 의존적 정지 기준이나 잘못된 민감도 계산과 같은 프라이버시 결함을 포함하고 있음을 지적하며, 이는 부록에서 자세히 설명합니다. 이러한 이전 연구의 결함에도 불구하고 Lumberjack 는 여전히 보고된 성능을 능가합니다.
• 확장성: 이 방법은 완전 랜덤 트리 접근법에서 관찰되는 유틸리티 붕괴 없이 깊은 트리 (최대 깊이 100) 를 성공적으로 처리합니다.

의의와 주장
이 논문은 Lumberjack 가 차분 프라이버시 랜덤 포레스트에 대한 새로운 최첨단 성능을 확립한다고 주장합니다. 저자들은 그들의 발견이 잘 설계된 DP 랜덤 포레스트가 비사적 대응물과 "유틸리티 격차의 상당 부분을 해소"할 수 있음을 시사한다고 논증합니다. 그들은 랜덤화된 구성과 원칙적인 프라이버시 인식 가지치기의 결합이 유망하고 아직 탐구되지 않은 방향임을 강조합니다.

저자들은 명시적으로 랜덤화된 포레스트에 대한 유틸리티 격차는 해결했지만, 고유틸리티 DP 탐욕적 랜덤 포레스트를 설계하는 것은 여전히 열린 과제라고 밝힙니다. 그들은 향후 작업이 프라이버시 - 유틸리티 트레이드오프를 더욱 개선하기 위해 더 정교한 조합 기법과 문제별 메커니즘이 필요할 수 있다고 제안합니다. 또한 이 논문은 기존 문헌의 프라이버시 증명 엄격성에 대한 경고 역할을 하며, 10 개 이상의 이전 논문에서 프라이버시 위반을 식별했습니다.