기술 요약: 이진 목적 의사결정나무 학습을 통한 최적의 recourse 요약

문제 제기

신용, 채용, 의료와 같은 중요한 분야에서 자동화된 의사결정 시스템은 종종 불투명한 모델에 의존합니다. 실행 가능한 recourse는 개인에게 불리한 결과를 변경하기 위한 구체적인 행동을 제공하지만, 이러한 지역적 행동을 전역 감사 및 편향 감지를 위해 집계하는 것은 비용이 많이 들고 종종 일관성이 없습니다. 인구를 하위 그룹으로 나누고 각 그룹에 공유된 행동을 할당하는 Recourse 요약에 대한 기존 방법들은 여러 목적을 균형 있게 조정하는 데 어려움을 겪습니다:

1. Recourse 효과성 (손실): 할당된 행동이 분류기의 출력을 반전시키지 못하는 인구의 비율.
2. Recourse 비용: 행동을 실행하는 데 필요한 추정된 노력.
3. 해석 가능성 제약: 하위 그룹 수, 하위 그룹 설명 길이, 그리고 행동의 희소성.

현재의 접근 방식들은 일반적으로 임의의 계수를 사용하여 이러한 목적을 스칼라화하거나 임계값을 부과하여 전역 최적성 보장을 제공하지 못합니다. 그들은 종종 단일 솔루션을 생성하여 이해관계자들이 비용과 효과성 사이의 근본적인 트레이드오프를 탐색하는 것을 방해합니다. 또한, 많은 기존 방법들 (예: CET, AReS) 은 높은 계산 실행 시간을 겪으며 전역 최적점을 찾는 것을 보장하지 않습니다.

방법론: SOGAR

저자들은 **최적 및 전역 실행 가능한 recourse 요약 (SOGAR)**을 소개하며, 이는 recourse 요약 학습을 이진 목적 최적 의사결정나무 학습 문제로 공식화하는 프레임워크입니다.

핵심 공식화

• 목적: **Recourse 비용 ($C$)**과 **Recourse 손실 ($L$)**을 동시에 최소화합니다.
• 구조: Recourse 요약은 얕은 축 평행 의사결정나무로 표현됩니다. 내부 노드는 특징에 대한 테스트를 수행하여 영향을 받는 인구를 불연속적인 하위 그룹 (잎) 으로 분할합니다. 각 잎에는 단일의 희소 행동이 할당됩니다.
• 최적성: 목적을 스칼라화하는 대신, SOGAR 는 비우세 솔루션의 완전한 파레토 프론트를 계산합니다. 솔루션 $\tau$가 $\tau'$보다 적어도 하나의 목적에서 더 좋고 다른 목적에서는 나쁘지 않을 때 $\tau$가 $\tau'$를 우세합니다. 이를 통해 사용자는 재학습 없이 사후에 이상적인 트레이드오프를 선택할 수 있습니다.

기술적 구현

이 방법은 전역 최적성을 보장하는 STreeD 동적 프로그래밍 프레임워크를 활용합니다.

1. 분리 가능성: 저자들은 최적의 recourse 요약 나무를 찾는 것이 분리 가능성 (마르코프 비용/전이 함수 및 순서 보존 결합 연산자) 에 대한 필요충분조건을 만족함을 증명하여 정확한 동적 프로그래밍을 가능하게 합니다.
2. 행동 집합 및 비용: 행동은 단일 또는 다중 편집 작업 (예: 이진 값 반전, 카테고리 변경, 수치 구간 이동) 으로 정의됩니다. 비용 함수는 규모 불변성과 현실적인 노력 추정을 보장하기 위해 **최대 백분위 이동 (MPS)**을 사용합니다.
3. 효율성 향상:
   • 캐싱: 트리 탐색 중 $O(1)$ 조회를 가능하게 하기 위해 모든 행동 - 인스턴스 쌍에 대한 비용과 손실을 사전 계산합니다.
   • 병렬화: 잎 노드에서 비용과 손실을 집계하기 위한 멀티 스레드 CPU 및 GPU 가속 구현으로 실행 시간을 크게 단축합니다.
   • 제약: 해석 가능성을 보장하기 위해 프레임워크는 최대 트리 깊이, 최대 잎 수, 그리고 행동 희소성을 강제합니다.

주요 기여

1. 이진 목적 공식화: SOGAR 는 구조적 제약 하에서 효과성과 비용을 공동으로 최적화하는 recourse 요약 학습을 이진 목적 최적 의사결정나무 문제로 정의한 최초의 방법입니다.
2. 전역 최적성 및 파레토 프론트: 문제를 STreeD 프레임워크 내에서 공식화함으로써, SOGAR 는 임의의 스칼라화를 피하고 전역 최적성 보장을 제공하는 비우세 솔루션의 정확하고 완전한 파레토 프론트를 계산합니다.
3. 확장성: CPU/GPU 병렬화와 효율적인 캐싱의 도입으로 이 방법은 NP-하드 트리 학습 문제를 합리적인 시간 예산 내에 전역 최적성으로 해결할 수 있으며, 대규모 데이터셋에서도 가능합니다.
4. 편향 감사 능력: 파레토 프론트의 다양성은 다양한 운영 지점에서의 편향 감지를 가능하게 하여, 단일 솔루션 방법들이 놓칠 수 있는 불평등을 드러냅니다.

실험 결과

저자들은 Employee Attrition, German Credit, Bank Marketing, Adult Income 네 개의 표형 데이터셋을 사용하여 LightGBM, XGBoost, DNN 세 가지 분류기와 CET, AReS, GLOBE-CE, GLANCE, T-CREx 다섯 가지 베이스라인에 대해 SOGAR 를 평가했습니다.

• 성능: SOGAR 는 모든 데이터셋과 분류기에서 **무효성 지표 (비용과 손실의 합)**에 대해 모든 베이스라인을 일관되게 능가했습니다. 대부분의 데이터셋에서 가장 낮은 비용을 달성했고 경쟁력 있는 손실 값을 보였습니다.
• 효율성: SOGAR 는 GLOBE-CE 와 같은 휴리스틱 방법보다 계산 비용이 더 높지만, 단일 실행으로 전체 파레토 프론트를 생성합니다. 반면, CET 와 AReS 와 같은 베이스라인은 종종 1 시간 타임아웃 제한을 초과하거나 더 큰 데이터셋에서 솔루션을 찾지 못했습니다.
• 일반화: 실험은 최소한의 과적합을 보여주었으며, 테스트 지표는 학습 파레토 프론트와 밀접하게 일치했습니다.
• 절대 연구:
  • 깊이: 깊이 3 은 품질과 실행 시간 사이의 가장 좋은 균형을 제공했습니다. 깊이 4 는 prohibitive 한 계산 비용에 비해 미미한 이득을 가져왔습니다.
  • 희소성: 행동 희소성을 줄이는 것 ($k=2$) 은 실행 시간을 크게 단축시켰지만, 특히 복잡한 데이터셋에서 손실을 증가시켰습니다.
  • 타임아웃: 엄격한 시간 제한 (예: 10~60 초) 으로도 SOGAR 는 베이스라인을 능가하는 솔루션을 복구하여 "anytime" 능력을 입증했습니다.

편향 감사 사례 연구

Adult Income 데이터셋에서 SOGAR 는 LightGBM 분류기의 성별 편향을 감사하는 데 사용되었습니다. 파레토 프론트의 분석은 여성이 96.4% 의 솔루션에서 남성보다 일관되게 더 높은 무효성에 직면했음을 드러냈습니다. 이 불평등은 주로 저비용 영역에서 여성의 더 높은 recourse 손실과 고비용 영역에서 더 높은 비용에 기인했습니다. 이 발견은 종종 낮은 손실, 높은 비용 지점을 선택하는 단일 솔루션 방법들이 전체 트레이드오프 스펙트럼에 존재하는 편향의 실제 정도를 과소평가할 수 있음을 강조합니다.

중요성과 주장

이 논문은 SOGAR 가 다음과 같은 이유로 알고리즘적 recourse 및 해석 가능성 분야에서 중요한 진전을 나타낸다고 주장합니다:

• recourse 요약에 대한 전역 최적성을 보장하는 최초의 방법을 제공합니다.
• 전체 트레이드오프 곡선을 노출함으로써 임의의 하이퍼파라미터 튜닝 (스칼라화 계수) 의 필요성을 제거합니다.
• 분류기의 강력한 전역 감사를 가능하게 하여, 이해관계자들이 다양한 비용 - 효과성 트레이드오프에 걸쳐 지속되는 편향을 식별하고 정량화할 수 있게 합니다.
• 현대적인 하드웨어 가속과 캐싱과 결합된 정확한 최적화가 해석 가능하고 실행 가능한 recourse 요약을 생성하기 위한 탐욕적이거나 확률적 접근 방식에 대한 실현 가능한 대안임을 보여줍니다.

저자들은 SOGAR 가 휴리스틱 방법보다 더 높은 계산 비용을 incurred 하며 추가적인 특징 선택 없이는 극도로 고차원 데이터셋에서 어려움을 겪을 수 있음을 인정합니다. 그들은 SOGAR 가 감사에 도움이 되지만, 독립적인 기준보다는 포괄적인 공정성 도구의 일부여야 함을 강조합니다.