기술 요약: 흐름 매칭을 통한 편향 없는 순열 학습

문제 정의

순열 학습은 정렬, 순위 매기기, 매칭과 같은 작업의 기초가 됩니다. 그러나 기존 미분 가능한 방법들은 일반적으로 이산 순열 행렬을 연속적인 비르호프 다면체 (이중 확률 행렬) 로 완화하기 위해 엔트로피 정규화된 싱크혼 반복에 의존합니다. 이 접근법은 두 가지 치명적인 한계를 도입합니다:

1. 구조적 붕괴: 엔트로피 정규화는 해를 다면체의 내부로 편향시킵니다. 여러 순열이 동등하게 유효한 경우 (예: 대칭성, 구별 불가능한 항목, 또는 비용의 근접한 동점 때문) 결정론적 완화는 분포를 단일 "연성 (soft)" 해로 붕괴시켜 불확실성이나 다중 모드 분포를 표현하지 못합니다.
2. 실행 가능성 저하: 표준 다양체-ODE 체계나 반복적 투영 방법은 제약 조건을 근사화할 뿐입니다. 이러한 방법에서의 제약 위반은 적분 시간에 따라 기하급수적으로 증가하거나 벡터장의 리프시츠 상수에 의존할 수 있어, 네트워크 표현력이나 적분 범위가 증가함에 따라 실행 불가능한 해를 초래합니다.

본 논문은 집합 값 감독 또는 모호한 입력의 경우 목표가 단일 "최고" 순열이 아니라 다양한 유효 해를 샘플링하고 불확실성을 전파할 수 있는 최적 순열에 대한 분포가 되어야 한다고 주장합니다.

방법론: PermFlow

저자들은 제약이 없는 공간으로의 완화를 피하고 단위 행렬 합과 열 합을 가진 아핀 부분 공간에서 직접 작동하는 조건부 흐름 매칭 (CFM) 프레임워크인 PermFlow를 제안합니다.

1. 기하학적 보존 동역학

$\mathbb{R}^{n \times n}$에서 흐름을 학습하고 반복적으로 투영하는 대신, PermFlow 는 순열 행렬의 기하학을 처음부터 존중하도록 흐름 동역학을 구성합니다.

• 아핀 제약 다양체: 모델은 $B_a = \{X \in \mathbb{R}^{n \times n} : X\mathbf{1} = \mathbf{1}, X^\top\mathbf{1} = \mathbf{1}\}$인 다양체에서 작동합니다.
• 접공간 프로젝터: 저자들은 임의의 행렬을 접공간 $T = \{\Delta : \Delta\mathbf{1} = 0, \Delta^\top\mathbf{1} = 0\}$으로 투영하는 폐형식 중심화 연산자 $C(U)$를 정의합니다.
  $$C(U) = U - \frac{1}{n}U\mathbf{1}\mathbf{1}^\top - \frac{1}{n}\mathbf{1}\mathbf{1}^\top U + \frac{1}{n^2}\mathbf{1}\mathbf{1}^\top U \mathbf{1}\mathbf{1}^\top$$
  이 연산자는 직교 프로젝터입니다. 속도장을 $v_\theta(X, t) = C(f_\theta(X, t))$로 정의함으로써, 결과적인 상미분 방정식 (ODE) $\dot{X}_t = v_\theta(X_t, t)$은 $X_0 \in B_a$이면 모든 $t$에 대해 $X_t \in B_a$임을 보장합니다. 이는 리프시츠 가정이나 적분 단계 크기와 무관하게 정확한 대수적 항등식으로 성립합니다.

2. 최단 목표 결합을 통한 조건부 흐름 매칭

모델은 조건부 흐름 매칭을 사용하여 속도장을 학습합니다.

• 초기화: 균일한 이중 확률 행렬에 가우시안 노이즈를 추가하고 이를 접공간으로 투영하여 노이즈가 있는 행렬 $\tilde{X}_0$를 생성합니다.
• 최단 목표 결합: 다중 모드를 처리하기 위해, 훈련 과정은 프로베니우스 거리를 기반으로 $\{P^1, \dots, P^M\}$인 기준 지면 순열 집합에서 각 노이즈 초기화 $\tilde{X}_0$를 가장 가까운 유효 목표 순열 $P^*$와 결합합니다.
  $$P^* = \arg \min_{P \in \{P^1, \dots, P^M\}} \|\tilde{X}_0 - P\|_F$$
  이 결합은 다양체의 서로 다른 영역에서 시작하는 궤적이 서로 다른 유효 순열로 라우팅되도록 하여, 기울기 상쇄를 방지하고 전체 다중 모드 구조를 포착하는 분기 동역학 학습을 장려합니다.
• 훈련 목적 함수: 모델은 $\tilde{X}_0$와 $P^*$ 사이의 선형 보간 경로에서 분석적으로 정의된 일정한 속도와 예측된 속도 간의 불일치를 최소화합니다.

3. 추론

추론 중에는 $K$개의 독립적인 노이즈 초기화가 추출되어 학습된 ODE 동역학을 통해 진화됩니다. 그런 다음 각 궤적은 헝가리안 알고리즘을 사용하여 가장 가까운 이산 순열로 반올림됩니다. 이 과정은 목표 분포의 유효 모드를 모두 포괄하는 다양한 후보 순열 집합을 생성합니다.

주요 기여

1. 정확한 실행 가능성 프레임워크: 저자들은 순열 행렬의 아핀 부분 공간에서 직접 속도장을 매개변수화하는 CFM 프레임워크를 제안합니다. 폐형식 접공간 프로젝터의 사용은 엔트로피 정규화나 반복적 수정에 의존하지 않고, 모든 신경망 $f_\theta$에 대해 모든 시간 단계 $t$에서 행렬 합과 열 합 제약이 정확히 보존되도록 보장합니다.
2. 다중 모드 모호성 해결: 이 프레임워크는 모호한 순열 예측을 위해 특별히 설계되었습니다. 최단 목표 결합을 사용하여 확률적 흐름은 유효 순열에 대한 조건부 분포를 학습하여, 단일 모드로 붕괴되는 결정론적 완화와 달리 여러 조합 모드의 명시적 표현과 샘플링을 가능하게 합니다.
3. 이산 객체로의 경험적 확장: 본 논문은 조건부 흐름 매칭이 비전 및 언어와 같은 연속 영역을 넘어 구조화된 조합 객체로 성공적으로 확장될 수 있음을 보여줍니다. 이는 본질적으로 이산적인 순열 학습에 흐름 매칭을 적용한 초기 사례 중 하나입니다.

실험 결과

저자들은 혼합된 숫자 모호성을 가진 시각적 정렬 작업 (NoisyMNIST) 과 대칭 선형 할당 문제 (SLAP) 에 대해 PermFlow 를 평가했습니다.

• 시각적 정렬 (NoisyMNIST):

  • 작업: 일부 숫자가 혼합되어 두 가지 유효한 정렬 순서를 생성하는 숫자 시퀀스 정렬.
  • 결과: PermFlow 는 다양한 샘플링 예산에 걸쳐 약 98% 의 클린 정확도와 약 99% 의 커버리지 (두 가지 유효 모드 모두 발견) 를 달성합니다.
  • 기반 실패: Gumbel-Sinkhorn 기반은 온도와 관계없이 약 0% 의 커버리지와 약 0% 의 클린 정확도를 달성하여, 이분산 분포를 표현하는 데 구조적으로 실패합니다.

• 대칭 선형 할당 (SLAP):

  • 작업: 매칭된 쌍을 교환해도 동등하게 최적의 해가 나오는 대칭 비용 행렬에서 최적 매칭을 찾는 작업.
  • 결과: PermFlow 는 높은 커버리지 ($N=20$인 경우 94–96%, $N=100$인 경우 83–86%) 와 거의 완벽한 모드 균형 (두 최적 순열을 동일한 빈도로 샘플링) 을 달성합니다. 최적성 격차는 작게 유지됩니다 (~2.2%).
  • 기반 실패: Gumbel-Sinkhorn 은 대칭 비용 행렬이 점수 행렬이 대칭적인 최적 해를 구별하지 못하게 하기 때문에 다시 완전히 실패합니다 (0% 커버리지, 높은 최적성 격차).

중요성과 주장

본 논문은 PermFlow 가 기존 완화 기반 방법보다 엄격하게 더 강력한 실행 가능성 보장을 제공한다고 주장합니다. 싱크혼 방법은 소멸하지 않는 잔차를 남기고 다양체-ODE 체계는 기하급수적으로 증가하는 제약 위반으로 고통받는 반면, PermFlow 는 구성에 의해 정확한 실행 가능성을 유지합니다.

저자들은 이 작업을 여러 유효 해가 공존하는 조합 예측 문제에 대한 엔트로피 완화의 실현 가능한 대안으로 위치시킵니다. 순열 분포를 붕괴시키는 대신 그 전체 다중 모드 구조를 포착함으로써, PermFlow 는 모호성의 정량화와 다양한 유효 해 생성을 가능하게 하여 현재 미분 가능한 정렬 및 매칭 접근법의 근본적인 한계를 해결합니다.