Lumberjack: 트리 내 Heavy Hitter 탐지를 통한 더 나은 차분 프라이버시 (Differentially Private) 랜덤

랜덤 포레스트 (Random forests)는 민감한 정형 데이터 (tabular data)를 다루는 분야에서 널리 사용되지만, 차분 프라이버시 (Differential Privacy, DP)를 적용하는 기존 방식들은 일반적으로 실용성이 없을 정도로 성능을 저하시킵니다. 본 논문에서는 대규모 랜덤 결정 트리 (random decision trees)를 구축한 후, 충분한 데이터가 포함된 노드만을 유지하도록 공격적이고 프라이버시를 보호하는 가지치기 (pruning)를 적용하여 실질적으로 더 높은 유용성 (utility)을 달성하는 차분 프라이버시 랜덤 포레스트 알고리즘인 Lumberjack을 소개합니다. 우리 접근 방식의 핵심 구성 요소는 계층적 데이터 (hierarchical data)를 위한 새로운 $(\varepsilon, δ)$-DP heavy hitter 탐지 알고리즘이며, 이 알고리즘의 오차는 높이가 $h$인 트리에 대해 $O_{\varepsilon,δ}(\sqrt{\log h})$입니다. 이는 독립적인 연구 가치가 있을 수 있습니다. 이러한 유리한 스케일링 (scaling) 덕분에 이전 연구보다 훨씬 더 깊은 트리를 사용할 수 있으며, 프라이버시 제약 조건 하에서도 향상된 표현력 (expressiveness)을 제공합니다. 벤치마크 데이터셋에 대한 실험적 평가 결과, Lumberjack은 기존의 DP 랜덤 포레스트 방법들을 일관되게 능가하며 새로운 SOTA (state of the art)를 구축했습니다. 특히, 우리의 접근 방식은 실제적인 프라이버시 예산 (privacy budgets) 상황에서 프라이버시-유용성 트레이드오프 (privacy-utility trade-off)를 대폭 개선합니다. 우리의 연구 결과는 정교하게 설계된 DP 랜덤 포레스트가 유용성 격차를 상당 부분 메울 수 있음을 시사하며, 이는 향후 연구를 위한 유망하고 아직 충분히 탐구되지 않은 방향임을 강조합니다.