$k$-최근접 이웃 (k-Nearest Neighbors) 분류를 위한 효율적인 Banzhaf 기반 데이터 가치 평가

데이터 가치 평가 (Data valuation), 즉 개별 데이터 포인트가 모델 성능에 기여하는 정도를 정량화하는 작업은 머신러닝 (Machine learning) 분야의 근본적인 과제로 부상했습니다. Banzhaf 지수 (Banzhaf value)와 같은 게임 이론적 (Game-theoretic) 접근 방식은 공정한 데이터 가치 평가를 위한 원칙적인 프레임워크를 제공하지만, 지수적인 계산 복잡도 (Exponential computational complexity) 문제를 겪습니다. 본 연구에서는 $k$-최근접 이웃 ($k$NN) 분류기에서 Banzhaf 지수를 계산하기 위해 특별히 설계된 효율적인 알고리즘을 개발함으로써 이 문제를 해결합니다. 먼저, 우리는 이 문제가 #P-hard임을 증명하여 문제의 이론적 난해함 (Theoretical hardness)을 확립합니다. 이러한 난해함에도 불구하고, 우리는 $k$NN 분류기의 국소성 (Locality) 특성을 활용하여 실용적인 정확 알고리즘 (Exact algorithms)을 개발합니다. 우리의 주요 기여는 상당한 계산 성능 향상을 달성하는 동적 계획법 (Dynamic programming) 프레임워크입니다. 구체적으로, 가중 $k$NN (Weighted $k$NN) 분류기를 위해 $O(Wkn^2)$의 시간 복잡도를 갖는 의사 다항 시간 (Pseudo-polynomial) 알고리즘을 제시하며, 여기서 $W$는 상위 $k$개 가중치의 최대 합입니다. 또한, 비가중 $k$NN (Unweighted $k$NN)을 위한 특화된 알고리즘을 제시하여 데이터 포인트 수에 대해 선형적인 $O(nk^2)$의 시간 복잡도를 달성합니다. 우리는 또한 효율적인 몬테카를로 추정 (Monte Carlo estimation) 방법도 제공합니다. 실제 데이터셋에 대한 광범위한 실험을 통해 우리 접근 방식의 실용적인 효율성과 데이터 가치 평가 응용에서의 효과를 입증합니다.