기술 요약: 비지도 학습을 통한 구조 기반 순열 학습

문제 정의

많은 학습 작업은 관찰 시점에 데이터가 자연스럽게 순서가 정해지지 않은 경우를 포함하며, 이는 잠재된 순열을 복원하여 근본적인 구조를 드러내야 함을 요구합니다. 예로는 정렬 (단조성 복원), 퍼즐 재구성 (공간적 연속성 복원), 그리고 외판원 문제 (TSP) 와 같은 라우팅 문제가 있습니다. 이러한 설정에서는 실제 정답 순열 (ground-truth permutations) 을 얻기 어려운 경우가 많아, 직접적인 레이블 지도 학습 대신 작업별 구조적 속성 (예: 부드러움, 단조성, 기하학적 일관성) 에 기반한 비지도 학습이 필요합니다.

미분 가능한 순열 학습, 특히 Gumbel–Sinkhorn 방법과 같은 최근의 발전은 순열을 연속적 완화 (continuous relaxations) 를 통해 최적화되는 잠재 연산자로 다룰 수 있게 합니다. 이러한 방법들은 Birkhoff 다면체 내의 이중 확률 행렬을 사용하여 이산적 순열 행렬을 근사하며, 전역 온도 매개변수 $\tau$(또는 역온도 $\beta$) 로 제어됩니다. 그러나 문제 크기와 모호성이 증가함에 따라 중요한 한계가 발생합니다: 할당 행렬의 서로 다른 부분이 서로 다른 속도로 수렴합니다. 일부 행/열은 학습 초기에 결정론적으로 변하는 반면, 다른 일부는 대칭성이나 약한 구조적 단서로 인해 모호한 상태로 남습니다. 단일 전역 온도는 모든 할당을 동시에 명확하게 하거나 확산되게 강제하여, 안정성과 이산화 사이의 불가피한 트레이드오프를 만들어냅니다. 공격적인 어닐링은 초기 오류를 고정시키고, 보수적인 어닐링은 크고 모호한 순열이 수렴하는 것을 방해합니다.

방법론

저자들은 단일 전역 온도를 할당 엔트로피에서 유도된 국소적으로 변하는 행 및 열 의존적 역온도 필드로 대체하는 엔트로피 적응형 Gumbel–Sinkhorn 공식을 제안합니다. 이 접근법은 현재 소프트 순열 할당의 불확실성에 기반하여 온도를 조절합니다.

핵심 메커니즘

1. 엔트로피 추정: 각 학습 단계에서 기본 역온도 $\beta_0(t)$를 사용하여 결정론적 소프트 할당 $Q$를 계산합니다:
   $$Q = \text{Sinkhorn}(\beta_0(t) \cdot \text{stopgrad}(S))$$
   여기서 $S$는 호환성 점수를 나타냅니다. stop-gradient는 엔트로피 제어기가 온도 추정 자체를 통해 역전파되지 않도록 보장합니다.
2. 불확실성 계산: $Q$로부터 정규화된 행 및 열 엔트로피 ($H^{\text{row}}_i$ 및 $H^{\text{col}}_j$) 를 계산합니다. 0 에 가까운 값은 확신 있는 할당을, 1 에 가까운 값은 높은 불확실성을 나타냅니다.
3. 적응형 온도 필드: 요소별 역온도 필드 $\beta \in \mathbb{R}^{n \times n}$를 구성합니다. 고엔트로피 행 또는 열의 경우, 탐색을 유지하기 위해 역온도를 감소시킵니다 (유효 온도 증가). 저엔트로피 영역의 경우, 이산화를 장려하기 위해 역온도를 기본 수준으로 유지합니다.
   $$\beta^{\text{row}}_i = \frac{\beta_0(t)}{1 + b(H^{\text{row}}_i)}, \quad \beta^{\text{col}}_j = \frac{\beta_0(t)}{1 + b(H^{\text{col}}_j)}$$
   여기서 $b(\cdot)$는 엔트로피가 임계값 $H_0$을 초과할 때만 활성화되는 유계 단조 함수입니다. 최종 요소별 필드는 평균입니다: $\beta_{ij} = \frac{1}{2}(\beta^{\text{row}}_i + \beta^{\text{col}}_j)$.
4. 샘플링: 최종 소프트 순열 $P$를 이 적응형 필드를 사용하여 샘플링합니다:
   $$P = \text{Sinkhorn}(\beta \odot (S + g))$$
   여기서 $g$는 Gumbel 노이즈이며 $\odot$는 요소별 곱을 나타냅니다.

이론적 해석

이 논문은 요소별 역온도 필드를 사용하여 Sinkhorn 정규화를 적용하는 것이 국소적으로 재조정된 비용을 가진 엔트로피 정규화 할당 문제를 푸는 것과 동등함을 입증합니다. 이는 적응형 온도 제어가 모호한 영역에서의 대칭성 깨짐을 지연시키는 동시에 확신 있는 영역이 집중되도록 허용하면서 전역 이중 확률 제약을 유지하는 최적 수송 해석을 제공합니다.

주요 기여

1. 통합 프레임워크: 재배열된 데이터의 작업별 구조적 손실로부터 직접 잠재 연산자로서 순열을 학습하기 위한 프레임워크로, 실제 정답 순열 없이 비지도 학습을 가능하게 합니다.
2. 엔트로피 적응형 Gumbel–Sinkhorn: 전역 온도를 할당 엔트로피에서 유도된 국소적으로 변하는 필드로 대체하는 새로운 변형입니다. 이는 확신 있는 할당은 초기에 이산화되도록 허용하면서도 모호한 영역에서는 탐색을 유지할 수 있게 합니다.
3. 최적 수송 해석: 적응형 온도 제어가 Birkhoff 다면체에서의 국소 비용 재조정과 동등하다는 증명으로, 방법의 행동에 대한 이론적 기반을 제공합니다.
4. 실증적 검증: 정렬, 퍼즐 재구성, 비지도 TSP 에 대한 실험을 통해 엔트로피 적응형 제어가 고정되거나 전역적으로 어닐링된 기준선보다 더 신뢰할 수 있는 수렴과 더 높은 품질의 순열을 산출하며, 특히 문제 크기 ($n$) 와 할당 모호성이 증가함에 따라 효과가 있음을 입증했습니다.

실험 결과

이 방법은 세 가지 주요 작업에서 평가되었습니다:

• 리스트 정렬: 높은 모호성을 가진 데이터셋 (값이 $[10, 11]$ 범위) 에서 엔트로피 적응형 온도는 전역 어닐링 및 NeuralSort 보다 일관되게 우수한 성능을 보였습니다. $n$이 300 으로 증가함에 따라 성능 격차가 벌어졌으며, 적응형 방법은 훨씬 더 높은 Kendall $\tau$ 점수를 유지했습니다.
• 퍼즐 재구성: CelebA-Test 이미지를 격자 (최대 $7 \times 7$) 로 분할한 결과, 적응형 방법은 전역 어닐링에 비해 더 높은 Kendall $\tau$를 달성하고 무작위 시드에 걸쳐 더 안정적인 수렴을 보였습니다. 개선 효과는 경계 일관성 단서가 모호한 더 큰 퍼즐에서 가장 두드러졌습니다.
• 비지도 TSP: UTSP 프로토콜에 적용된 결과 (도수 위반 기반 적응 변형 사용), 이 방법은 표준 Gumbel–Sinkhorn 및 UTSP 기준선보다 투어 길이와 최적성 격차를 줄였으며, 특히 더 큰 노드 수 ($n=500, 1000$) 에서 두드러졌습니다.

모든 경우에서 적응형 방법은 하이퍼파라미터 선택 (엔트로피 임계값 $H_0$ 및 최대 부스트 $b_{\text{max}}$) 에 대한 강건성을 보였으며, 고모호성 영역에서 전역 온도 스케줄과 관련된 불안정성을 피했습니다.

중요성 및 주장

이 논문은 구조로부터의 효과적인 순열 학습이 최적화 과정에서 어디에서 언제 엔트로피가 붕괴되는지를 관리하는 데 결정적으로 의존한다고 주장합니다. 할당 불확실성이 이질적임을 인정함으로써, 제안된 방법은 전역 온도 스케줄에 내재된 안정성 - 이산화 트레이드오프를 해결합니다.

저자들은 이 작업을 Gumbel–Sinkhorn 계열에 대한 경량 확장으로 위치지우며, 근본적인 완화 기하학이나 수렴 속성을 변경하지 않으면서 확장성과 안정성을 개선한다고 명시합니다. 그들은 이 방법이 최적화 안정성을 개선하지만, 매우 대칭적이거나 정보가 약한 목적 함수의 근본적인 모호성을 해결하지는 못하며, 여전히 일부 형태의 대칭성 깨짐 (예: 퍼즐의 앵커 타일) 이 필요할 수 있음을 지적합니다.

제안된 미래 방향으로는 엔트로피 적응형 제어를 엔드 - 투 - 엔드로 학습하는 것과 불확실성 인식 이산화를 더 복잡한 조합 구조 및 다중 모드 매칭 문제로 확장하는 것이 포함됩니다.