Optimal Transport Maps for Artificial Intelligence: Deep Neural Network Estimation and Applications = 인공지능을 위한 최적 수송 맵: 심층 신경망을 이용한 추정 및 응용

다국어 초록 (Multilingual Abstract)

The optimal transport (OT) map offers a geometric lens for aligning probability distributions and has become a powerful, efficient, and reliable tool across diverse machine learning (ML) and artificial intelligence (AI) tasks.
In this thesis, we study the estimation and real-world applications of the OT maps. First, we develop a practical estimator of the OT maps using deep neural networks (DNNs) and explore its applications to AI, particularly for visual learning tasks. Then, we introduce a novel algorithm for fair clustering based on the OT map and validate its strong empirical performance.
In the first part, we introduce a two-step scheme for the OT map estimation based on the optimal coupling. The proposed method first solves the Kantorovich problem to obtain the empirical optimal coupling, and then fits the an DNN to the coupled pairs obtained from the first step. Under standard regularity conditions, we show the minimax optimal convergence rate of the proposed estimator for Lipschitz OT maps up to logarithmic factors. Experiments on synthetic datasets and computer vision tasks show that the proposed estimator outperforms or performs competitive to existing baselines for estimating the OT map.
In the second part, we present a novel transport map-based fair clustering algorithm that achieves fairness by transporting protected groups into a common aligned space and then running standard clustering on the aligned space. Theoretically, we prove that the fair clustering can be obtained by jointly finding the coupling (i.e., matching) to build the aligned space and optimizing the cluster centers on the aligned space. Experimentally, across various benchmark datasets, the proposed algorithm can attain any given fairness level with competitive clustering cost, exhibits numerical stability, and scales easily.

국문 초록 (Abstract)

최적 수송 (Optimal Transport, OT) 맵은 확률 분포를 정렬하기 위한 기하학적 관점을 제공하며, 다양한 머신러닝 (Machine Learning; ML) 및 인공지능 (Artificial Intelligence; AI) 응용 과제에서 강력하고 효율적이며 신뢰할 수 있는 도구로 자리 잡아왔다.
본 학위 논문에서는 최적 수송 맵의 추정 방법과 그 응용에 대해 연구한다. 먼저, 심층 신경망 (Deep Neural Network; DNN) 을 활용하여 실용적인 최적 수송 맵의 추정 방법을 제안하고, 이를 특히 컴퓨터 비전 분야 인공지능 문제에 응용하는 방안을 탐구한다. 이어서, 최적 수송 맵을 기반으로 한 새로운 공정한 클러스터링 (Fair Clustering; FC) 알고리즘을 제안하고, 그 우수한 실증적 성능을 검증한다.
첫 번째 파트인 2장에서는 최적 결합 (Optimal Coupling) 에 기반한 최적 수송 맵 추정의 2단계 기법을 소개한다. 제안된 방법은 먼저 칸토로비치 (Kantorovich) 문제를 해결하여 경험적 최적 결합을 얻은 후, 첫 번째 단계에서 도출된 결합 쌍에 DNN을 학습시킨다. 표준적인 정칙성 조건 하에서, 본 추정기가 립시츠 연속 (Lipschitz continuous) 최적 수송 맵에 대해 로그 인자를 제외하고 최소최대 최적 수렴 속도를 가짐을 입증한다. 시뮬레이션 데이터셋 및 컴퓨터 비전 과제에 대한 실험 결과, 제안된 추정기는 최적 수송 맵 추정 성능에 있어 기존의 베이스라인 모델들을 능가하거나 그에 상응하는 성능을 보여줌을 확인한다.
두 번째 파트인 3장에서는 새로운 수송 맵 기반 공정 클러스터링 알고리즘을 제시한다. 이 알고리즘은 보호 그룹을 하나의 공통 정렬 공간으로 수송시킨 후, 해당 정렬 공간에서 표준 클러스터링을 실행함으로써 공정성을 달성한다. 이론적으로는, 정렬 공간을 구축하기 위한 결합 (즉, 매칭) 을 찾는 과정과 해당 공간에서 클러스터 중심을 최적화하는 과정을 결합함으로써 공정 클러스터링을 구현할 수 있음을 증명한다. 실험적으로는 다양한 벤치마크 데이터셋 분석을 통해, 제안된 알고리즘이 경쟁력 있는 클러스터링 비용으로 주어진 모든 공정성 수준을 달성할 수 있으며, 수치적 안정성과 뛰어난 확장성을 보유하고 있음을 입증한다.

목차 (Table of Contents)

• Abstract
• 1 Introduction 1
• 2 Coupling-based estimators for optimal transport map: statistical theory and applications
• 2.1 Introduction 4
• 2.1.1 Related works 7
• 2.2 Preliminaries 9
• 2.2.1 Notations and definitions 9
• 2.2.2 Optimal transport map and optimal coupling 10
• 2.2.3 Minimax optimal convergence rate 14
• 2.2.4 Existing estimators 15
• 2.3 Coupling-based estimators for the optimal transport map 17
• 2.3.1 Deep neural network estimator 19
• 2.3.2 Piecewise-polynomial estimator 21
• 2.4 Minimax optimal convergence rates of the proposed estimators 22
• 2.4.1 Deep neural network estimator 24
• 2.4.2 Piecewise-polynomial estimator 26
• 2.5 Experiments 27
• 2.5.1 Baseline methods 28
• 2.5.2 Simulations 28
• 2.5.3 Application 1: domain adaptation 30
• 2.5.4 Application 2: unpaired image translation 36
• 2.6 Conclusion and discussion 38
• 2.7 Appendix to Chapter 2 40
• 2.7.1 Notations and definitions 40
• 2.7.2 Existence, uniqueness, and duality of optimal transport maps 41
• 2.7.3 Technical lemmas 45
• 2.7.4 Proofs 51
• 2.7.5 Additional experimental results 57
• 3 A Transport map-based approach for fair clustering 60
• 3.1 Introduction 60
• 3.2 Preliminaries 64
• 3.2.1 Notations 64
• 3.2.2 Clustering objective function 64
• 3.2.3 Definition of fair clustering 65
• 3.3 Reformulation of fair clustering objective 66
• 3.3.1 Case of equal sample sizes 66
• 3.3.2 Case of unequal sample sizes 68
• 3.4 Proposed algorithms 71
• 3.4.1 FCA: Fair Clustering via Alignment 71
• 3.4.2 FCA-C: control of fairness level 74
• 3.4.3 Reducing computational complexity 78
• 3.5 Experiments 78
• 3.5.1 Settings 79
• 3.5.2 Performance comparison results 80
• 3.5.3 Applicability to visual clustering 83
• 3.5.4 Ablation studies 85
• 3.6 Conclusion and discussion 86
• 3.7 Appendix to Chapter 3 87
• 3.7.1 Supplementary discussion 87
• 3.7.2 Proofs of the theorems 92
• 3.7.3 Experiments 109
• Bibliography 135
• Abstract (in Korean) 150