DCFO: Density-Based Counterfactuals for Outliers -- Additional Material

기술 요약: DCFO - 이상치를 위한 밀도 기반 반사실적 설명

문제 제기
이상치 탐지는 사기 탐지 및 시스템 고장 진단과 같은 분야에서 이상을 식별하는 데 필수적입니다. 그러나 특정 데이터 포인트가 이상치로 플래그되는 이유를 설명하는 것은 여전히 큰 과제로 남아 있습니다. 모델의 예측을 변경하기 위해 필요한 최소한의 변화를 식별하는 반사실적 설명은 설명 가능한 AI(XAI) 에서 인기 있는 기법이지만, 기존 방법들은 특히 국소 이상치 인자 (LOF) 와 같은 이상치 탐지 알고리즘에 적용하는 데 어려움을 겪습니다.

LOF 는 상대적 국소 밀도에 기반하여 이상성 정도를 정량화합니다. LOF 에 대한 반사실적 설명을 생성하는 데 있어 근본적인 과제는 LOF 의 비연속성입니다. 관측치의 작은 변화가 $k$-최근접 이웃 집합을 급격히 변경시켜 이상치 점수에서 불연속적인 점프를 유발할 수 있기 때문입니다. 이러한 불연속성은 예측 전환이 매끄럽다는 가정에 의존하는 표준 경사 기반 최적화 방법을 무력화시킵니다. 반면, 경사가 필요 없는 베이지안 최적화나 유전 알고리즘과 같은 대안적 접근법은 고차원 설정에서 과도한 계산 비용을 초래하거나 일관되게 유효한 반사실적 설명을 생성하지 못하는 경우가 많습니다. 또한, 많은 기존 반사실적 방법은 분류 작업을 위해 설계되어 이상치 탐지의 특정 불균형 특성을 고려하지 못하거나, 실제 세계 데이터에 종종 존재하는 실행 불가능한 특성을 처리하지 못합니다.

방법론: DCFO
저자들은 LOF 에 대한 반사실적 설명을 생성하기 위해 특별히 설계된 **이상치를 위한 밀도 기반 반사실적 설명 (DCFO)**을 제안합니다. DCFO 의 핵심 혁신은 근본적인 비연속성에도 불구하고 효율적인 경사 기반 최적화를 가능하게 하는 LOF 의 내부 구조를 활용하는 데 있습니다.

1. 영역 기반 분할: DCFO 는 LOF 점수가 매끄럽게 작용하도록 데이터 공간을 영역으로 분할합니다. 영역은 점 $x$의 $k$-최근접 이웃 집합과 해당 이웃들의 $k$-최근접 이웃을 인코딩하는 고유한 "키" $K(x)$로 정의됩니다. 이러한 영역 $R_K$ 내에서는 LOF 계산에 영향을 미치는 점들의 집합이 고정됩니다.
2. 미분 가능성: 저자들은 특정 영역 $R_K$ 내에서 LOF 점수 함수, 즉 $LOF_K(x)$가 (유클리드 거리와 같은 잘 정의된 거리 함수를 가정할 때) 거의 모든 곳에서 연속적이고 미분 가능함을 증명합니다. 이 속성은 효율적인 경사 기반 최적화 도구의 사용을 가능하게 합니다.
3. 최적화 과정:
   • 알고리즘은 이상치 $p_i$로 시작하여 해당 영역 키 $K$를 계산합니다.
   • 제약 조건 $LOF_K(x) \leq t$ (여기서 $t$는 이상치 임계값) 하에 $p_i$와의 거리를 최소화하는 점 $x$를 찾기 위해 제약 최적화 문제를 풉니다.
   • 최적화는 순차적 최소 제곱 프로그래밍 (SLSQP) 을 사용합니다.
   • 최적화기가 현재 영역을 벗어나는 경우 (즉, 키가 변경되는 경우), 알고리즘은 새로운 영역의 키를 사용하여 새로운 점에서 최적화를 재귀적으로 재개합니다.
   • 다양성을 보장하기 위해, 이 방법은 영역 경계를 넘은 점들의 탐색 대기열을 유지하여 이러한 점들에서 새로운 최적화를 시작함으로써 여러 개의 서로 다른 반사실적 설명을 생성할 수 있게 합니다.
4. 제약 조건 처리:
   • 실행 불가능한 특성: DCFO 는 사용자가 불변 특성 (예: 나이) 을 지정할 수 있도록 합니다. 최적화기는 실행 불가능한 특성을 고정된 상태로 유지하면서 실행 가능한 변수만 조정하도록 제한됩니다.
   • 현실성: 더 낮은 LOF 점수 (더 높은 국소 밀도에 해당) 를 목표로 함으로써, 이 방법은 반사실적 설명을 자연스럽게 특징 공간의 현실적이고 밀도가 높은 영역으로 유도하여 현실적이지 않은 이상치를 방지합니다.

주요 기여

• 최초의 LOF 전용 반사실적 방법: DCFO 는 국소 이상치 인자 (LOF) 알고리즘에 대한 반사실적 설명을 생성하도록 명시적으로 설계된 첫 번째 방법입니다.
• 알고리즘적 혁신: 비미분 가능한 LOF 문제를 일련의 미분 가능한 하위 문제로 변환하여 경사 기반 최적화 사용을 가능하게 하는 공간 분할 전략을 도입했습니다.
• 특성 처리: 실행 불가능한 특성을 처리하고, 여러 개의 다양한 반사실적 설명을 생성하며, 밀도 타겟팅을 통해 현실성을 보장하는 메커니즘을 통합했습니다.
• 실증적 검증: 저자들은 50 개의 OpenML 데이터셋에 대한 광범위한 벤치마크를 제공합니다.

실험 결과
본 논문은 DCFO 를 세 가지 경쟁자, 즉 베이지안 최적화 기반인 Baycon, 유전 알고리즘 기반인 EACE, 그리고 이상치를 가장 가까운 정상치로 이동시키는 Baseline과 비교 평가합니다.

• 유효성: DCFO 는 50 개 데이터셋 전반에 걸쳐 1.00의 유효성 점수를 달성하여 모든 이상치에 대해 유효한 반사실적 설명을 성공적으로 찾았습니다. 반면, Baycon 은 0.84, EACE 는 0.38, Baseline 은 0.88 의 점수를 기록했습니다. 저자들은 LOF 의 비연속적인 특성으로 인해 EACE 와 Baseline 이 유효한 반사실적 설명을 생성하지 못하는 경우가 많았다고 지적합니다.
• 근접성: DCFO 는 경쟁자들보다 원래 이상치에 더 가까운 반사실적 설명을 일관되게 생성했습니다. 임계 차이 도표 (Nemenyi 검정) 를 사용한 통계적 분석은 DCFO 의 근접성 성능이 2 위인 Baycon 보다 통계적으로 유의미하게 우수함을 확인했습니다.
• 다양성: 여러 개의 반사실적 설명을 생성할 때, DCFO 는 다른 방법들에 비해 통계적으로 유의미하게 우수한 다양성을 보여주어 실행 가능한 대안의 더 넓은 범위를 제공했습니다.
• 실행 불가능한 특성: 특성의 하위 집합이 제한된 실험에서 DCFO 는 Baycon 보다 더 높은 유효성과 더 나은 근접성을 유지하여 특성 제약에 대한 견고성을 입증했습니다.
• 효율성: Baseline 이 가장 빠르긴 했으나, DCFO 의 경사 기반 접근법은 베이지안 (Baycon) 및 유전 (EACE) 접근법보다 훨씬 효율적이었습니다.

의의 및 주장
본 논문은 DCFO 가 널리 사용되지만 불투명한 LOF 알고리즘을 해석 가능하게 만들어 이상치 탐지를 위한 XAI 의 중요한 공백을 해소한다고 주장합니다. LOF 의 불연속성을 처리하기 위해 데이터 공간을 분할함으로써 DCFO 는 기존 방법들이 신뢰성 있게 생성하지 못하는 실행 가능하고 유효하며 다양한 설명을 제공합니다. 저자들은 그들의 방법이 단순히 인스턴스가 왜 이상치인지 설명하는 것을 넘어, 이를 수정하기 위한 구체적이고 최소한의 단계를 제공하여 예방 조치를 용이하게 하고 이상치 탐지 시스템에 대한 신뢰를 구축한다고 강조합니다. 이 작업은 기초적인 단계로 제시되었으며, 향후 연구는 다른 LOF 변형으로 접근법을 확장하고 변경된 특성의 수를 최소화하는 방향으로 제안됩니다.