Fairness under Graph Uncertainty: Achieving Interventional Fairness with Partially Known Causal Graphs over Clusters of Variables

이 논문은 개별 변수 수준의 인과 그래프에 대한 상세한 지식이 부족한 상황에서도 변수 클러스터 수준의 그래프를 활용하여 보정 클러스터 집합을 식별하고, 최악의 경우 개입 분포 간 불일치를 최소화하는 효율적인 커널 기반 학습 프레임워크를 제안함으로써 공정성과 정확성 간의 균형을 개선합니다.

핵심

이 논문은 **"인공지능이 사람을 판단할 때, 편견 없이 공정한 결정을 내리려면 어떻게 해야 하는가?"**라는 질문에 대한 새로운 해법을 제시합니다.

기존의 방법들은 "세상의 모든 인과관계 (원인과 결과) 를 완벽하게 알고 있어야만" 공정한 AI 를 만들 수 있다고 믿었습니다. 하지만 현실에서는 세상의 모든 관계를 완벽하게 아는 것은 불가능에 가깝죠. 이 논문은 **"완벽한 지도가 없어도, 대략적인 지도만 있으면 공정한 결정을 내릴 수 있다"**는 것을 증명했습니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 문제 상황: "완벽한 지도"를 기다리는 실수

상황:
어떤 회사가 신입 사원을 뽑으려고 AI 를 도입했습니다. AI 는 지원자의 성별, 인종 (민감한 정보) 과 학력, 시험 점수 등을 보고 합격 여부를 결정합니다.

기존의 문제점:
기존의 공정한 AI 기술들은 "우리가 세상의 모든 인과관계를 완벽하게 파악하고 있어야 한다"고 요구했습니다.

• 예를 들어, "성별이 학업 성취도에 영향을 미쳤는지?", "학업 성취도가 시험 점수에 영향을 미쳤는지?" 등 모든 변수 간의 연결고리를 완벽하게 파악해야만 AI 가 편견 없이 작동한다고 믿었습니다.

현실:
하지만 현실에서는 이런 '완벽한 지도 (인과 그래프)'를 그리는 게 너무 어렵습니다. 데이터가 너무 많고, 변수들 사이의 관계가 복잡해서 실수가 생기기 쉽죠. 완벽한 지도를 그리려고 애쓰다가 오히려 AI 가 더 불공정해지거나, 아예 공정한 AI 를 만들 수 없는 상황에 처하게 됩니다.

---

2. 이 논문의 해법: "대략적인 지도 (클러스터)"로 해결하기

이 논문은 **"완벽한 지도 대신, '개념별 지도'를 그려보자"**고 제안합니다.

비유: 도시 지도 vs. 구역별 지도

• 완벽한 지도 (기존 방법): 도시의 모든 골목길, 모든 건물의 위치를 하나하나 다 표시한 지도입니다. 그리는 데 시간이 너무 오래 걸리고, 한 군데라도 잘못 그리면 전체 지도가 무용지물이 됩니다.
• 개념별 지도 (이 논문): 도시를 '강남구', '강북구', '강서구'처럼 큰 **구역 (클러스터)**으로 나눈 지도입니다. 각 구역 안의 골목길은 정확히 몰라도, "강남구와 강북구 사이에는 다리가 있다"는 정도만 알면 됩니다.

핵심 아이디어:

1. 그룹화: 성별, 학력, 시험 점수 등 수많은 정보를 '성별 그룹', '학력 그룹', '신체 능력 그룹'처럼 큰 덩어리 (클러스터) 로 묶습니다.
2. 간단한 관계 파악: 개별 변수들 사이의 복잡한 관계보다는, 이 그룹들 사이의 관계만 파악하면 됩니다. 그룹끼리의 관계는 훨씬 더 쉽고 정확하게 파악할 수 있습니다.
3. 최악의 경우 대비: "아마도 이 그룹과 저 그룹 사이에는 이런 관계가 있을지도 모른다"는 여러 가지 가능성을 고려합니다. 그리고 **가장 나쁜 경우 (가장 불공정할 수 있는 상황)**를 가정해서 AI 를 훈련시킵니다. 이렇게 하면, 실제 관계가 어떤 경우든 AI 는 항상 공정한 결정을 내리게 됩니다.

---

3. 어떻게 작동할까? "공정한 저울" 만들기

이 논문은 AI 를 훈련시킬 때 두 가지 중요한 기술을 사용합니다.

① '가장 나쁜 경우'를 상정하는 훈련 (Worst-case Fairness)

• 마치 비행기 설계와 비슷합니다. 비행기 설계자는 "바람이 불지 않을 때"만 생각하지 않습니다. "태풍이 불고, 엔진이 고장 날 수도 있는 가장 나쁜 상황"을 가정해서 설계합니다.
• 이 논문도 마찬가지입니다. "어떤 인과관계가 사실일지 모르니, 가장 불공정해질 수 있는 모든 시나리오를 다 고려해서 AI 를 훈련시킨다"는 뜻입니다. 이렇게 하면 어떤 시나리오가 진짜든 AI 는 편견 없이 작동합니다.

② '평균의 평균'을 이용한 빠른 계산 (Barycenter MMD)

• 모든 가능한 상황을 하나하나 비교하면 계산량이 너무 많아져서 AI 가 멈춰버립니다.
• 이 논문은 **"모든 그룹의 평균적인 상태 (중심)"**를 먼저 구한 뒤, 각 그룹이 그 중심에서 얼마나 벗어났는지만 재는 clever한 방법을 썼습니다.
• 비유: 100 명의 학생 점수를 비교할 때, "A 와 B, A 와 C, B 와 C..." 식으로 100 명을 모두 서로 비교하는 게 아니라, **"전체 평균 점수"**를 먼저 정하고, "각 학생이 평균에서 얼마나 차이가 나는지"만 재는 것과 같습니다. 이렇게 하면 계산 속도가 엄청나게 빨라집니다.

---

4. 결론: 왜 이것이 중요한가?

이 연구는 **"완벽한 지식을 요구하지 않아도, 현실적인 조건에서 공정한 AI 를 만들 수 있다"**는 것을 증명했습니다.

• 기존: "세상의 모든 인과관계를 다 알아야 공정한 AI 를 만들 수 있어." (너무 어렵고 비현실적)
• 이 논문: "세상의 큰 흐름 (그룹 간 관계) 만 알면 돼. 그리고 가장 나쁜 상황을 대비해서 훈련하면 돼." (실현 가능하고 효과적)

한 줄 요약:

"완벽한 지도가 없어도, 큰 그림 (그룹) 만 보고 '가장 나쁜 상황'을 대비하면, AI 는 누구에게나 공정한 결정을 내릴 수 있다."

이 방법은 채용, 대출 승인, 의료 진단 등 우리 삶에 큰 영향을 미치는 AI 의사결정에서, 불완전한 정보 속에서도 공정성을 지키는 강력한 도구가 될 것입니다.

기술 요약

1. 문제 정의 (Problem)

• 배경: 알고리즘적 의사결정 (채용, 대출 등) 은 민감한 속성 (성별, 인종 등) 에 대한 공정성을 보장해야 합니다. 인과적 공정성 (Causal Fairness) 은 법적 요구사항과 부합하지만, 기존 방법론들은 **개별 변수 수준의 완전한 인과 그래프 (Ground-truth Causal Graph)**에 접근할 수 있다고 가정합니다.
• 한계: 실제 응용 분야에서는 완벽한 도메인 지식이 부족하여 전체 인과 그래프 구조를 관측 데이터로부터 학습하는 것은 매우 어렵고 계산 비용이 큽니다. 특히 고차원 환경에서는 조건부 독립성 테스트가 폭발적으로 증가하여 추론 오류가 누적되고, 이는 공정성 보장의 신뢰성을 훼손합니다.
• 핵심 질문: 개별 변수 수준의 완전한 인과 구조를 알지 못하더라도, **변수 군집 (Clusters of Variables) 단위로 정의된 부분적으로 알려진 인과 그래프 (Cluster CPDAG)**를 활용하여 개입적 공정성 (Interventional Fairness) 을 달성할 수 있는가?

2. 제안 방법론 (Methodology)

저자는 C-IFair라는 새로운 학습 프레임워크를 제안하며, 이는 크게 세 가지 단계로 구성됩니다.

2.1. 군집 인과 그래프 (Cluster CPDAG) 활용

• 기존 변수 수준의 CPDAG(Completed Partially Directed Acyclic Graph) 대신, 사용자가 정의한 변수 군집 (Clusters) 단위로 구성된 Cluster CPDAG를 사용합니다.
• 군집화 (Clustering) 는 그래프 크기를 줄여 조건부 독립성 테스트 횟수를 기하급수적으로 감소시키며, 통계적 검정력을 높입니다.
• Cluster CPDAG는 방향성 간선, 무방향 간선뿐만 아니라, 군집 간의 조건부 독립 관계를 명시적으로 나타내는 **독립성 호 (Independence Arcs)**와 **연결/분리 마크 (Connection/Separation Marks)**를 포함합니다.

2.2. 조정 군집 집합 (Adjustment Cluster Sets) 탐색 알고리즘

• 개입적 공정성을 보장하기 위해서는 민감한 속성 ($A$) 에서 예측 결과 ($\hat{Y}$) 로 가는 백도어 경로 (Back-door paths) 를 차단할 수 있는 **조정 집합 (Adjustment Set)**이 필요합니다.
• Cluster CPDAG는 여러 가능한 인과 DAG 들을 포함하므로 단일 조정 집합을 식별할 수 없습니다. 따라서 저자는 **최악의 경우 (Worst-case)**를 대비하여 모든 가능한 DAG 에 대해 유효한 조정 집합을 보장하는 **조정 군집 집합들의 집합 ($Z_1, \dots, Z_M$)**을 열거하는 그래픽 알고리즘을 개발했습니다.
  • Parent Enumeration: 민감한 속성의 부모 군집 후보를 식별합니다.
  • Adjustment Set Completion: 독립성 호와 연결/분리 마크를 고려하여 백도어 경로를 차단하기 위해 필요한 추가 군집들을 큐 기반 전파 (Queue-based propagation) 를 통해 보충합니다.
  • Refinement: 식별 불가능한 경우 (Unidentifiable cases) 에는 군집을 단일 노드로 분할하여 그래프를 정제 (Refine) 한 후 조정 집합을 다시 구합니다.

2.3. 최악의 경우 불공정성 페널티 및 효율적 추정

• 최악의 경우 페널티: 식별된 $M$개의 조정 집합 중 어떤 것이 실제 DAG 에 유효한지 불확실하므로, 모든 집합에 대한 개입 분포 간 불일치를 측정하고 그 **최댓값 (Worst-case)**을 페널티 함수로 사용합니다.
• 효율적 MMD (Maximum Mean Discrepancy) 추정:
  • 기존 pairwise MMD 계산의 $O(N_A^2)$ 복잡도를 Barycenter Kernel MMD를 사용하여 $O(N_A)$로 줄였습니다. (여기서 $N_A$는 민감 속성 값의 개수)
  • 커널 함수의 특징 매핑을 **랜덤 푸리에 특징 (Random Fourier Features, RFF)**으로 근사하여 샘플 크기 $n$에 대한 계산 복잡도를 $O(n^2)$에서 $O(n)$으로 줄였습니다.
  • 역확률 가중치 (IPW) 를 결합하여 개입 분포를 추정합니다.
• 최종 목적함수는 예측 오차와 이 페널티 함수의 합을 최소화하는 것입니다.

3. 주요 기여 (Key Contributions)

1. 그래프 알고리즘 개발: Cluster CPDAG 의 독립성 호와 마크를 고려하여, 실제 군집 DAG 에 유효한 조정 군집 집합을 열거하는 새로운 알고리즘을 제안했습니다.
2. 학습 프레임워크 제안: 조정 집합들 간의 최악의 경우 불공정성을 페널티화하여 개입적 공정성을 달성하는 프레임워크를 구축했습니다.
3. 계산 효율성 향상: 민감 속성 값의 개수와 샘플 크기에 대해 확장성이 좋은 Barycenter Kernel MMD를 도입하여 대규모 데이터셋에서도 실용적으로 적용 가능하게 했습니다.
4. 실험적 검증: 합성 데이터와 실세계 데이터 (Adult, German Credit, OULAD) 를 통한 광범위한 실험을 통해 기존 방법론보다 **공정성과 정확도 간의 더 나은 균형 (Trade-off)**을 달성함을 증명했습니다.

4. 실험 결과 (Results)

• 합성 데이터 (Synthetic Data): 선형 및 비선형 인과 구조를 가진 데이터셋에서 C-IFair 는 기존 방법론 (Unaware, No-DesCs, $\epsilon$-IFair, $\ell$-IFair) 보다 낮은 RMSE(오차) 와 낮은 Unfairness(불공정성) 를 동시에 달성했습니다. 특히 고차원 설정 ($d=15$) 에서 변수 수준 CPDAG 기반 방법 ($\ell$-IFair) 보다 우월한 성능을 보였습니다.
• 실세계 데이터 (Real-world Data): Adult, German Credit, OULAD 데이터셋에서 C-IFair 는 AUC(분류 성능) 와 Unfairness 모두에서 Oracle(진짜 인과 그래프를 아는 이상적인 경우) 을 제외하고 가장 좋은 성능을 보였습니다.
• 강건성 (Robustness):
  • 허용 가능한 특징 (Admissible Features) 존재 시: 허용 가능한 특징이 포함된 복잡한 설정에서도 최상의 성능을 유지했습니다.
  • 밀집 그래프 (Dense Graphs): 그래프가 밀집되어 조정 집합의 수가 많아지는 상황에서도 효과적이었습니다.
  • 가정 위반 (Assumption Violation): 군집 분할이 허용 불가능 (Inadmissible) 하여 순환이 발생하는 경우에도, 학습된 그래프가 일부 인과 관계를 포착하여 여전히 경쟁력 있는 성능을 보여주었습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 실용성: 실제 환경에서 완벽한 인과 그래프를 알기 어렵다는 현실적인 제약을 완화했습니다. 변수 수준의 그래프 학습은 어렵지만, 군집 수준의 그래프는 상대적으로 쉽고 안정적으로 추론 가능하다는 점을 활용했습니다.
• 효율성: 계산 복잡도를 획기적으로 낮추어 대규모 데이터셋에서의 적용 가능성을 열었습니다.
• 미래 방향: 추후 연구에서는 Cluster CPDAG 를 **Cluster MPDAG (Maximally Oriented Partially Directed Acyclic Graph)**로 확장하여 인과 구조의 불확실성을 더욱 줄이고, 추가적인 도메인 지식을 통합하는 방향으로 발전시킬 수 있습니다.

이 논문은 인과적 추론의 불확실성 하에서도 신뢰할 수 있는 공정성 있는 알고리즘을 설계할 수 있는 강력한 이론적, 실증적 기반을 마련했다는 점에서 의의가 큽니다.