Take It or Leave It: Intent-Controlled Partial Optimal Transport

본 논문은 부수 정보를 기반으로 한 점별 의도 기반 거부 비용을 전역 질량 거부에 대체하여 부분 최적 수송을 일반화하는 새로운 프레임워크인 의도 제어 부분 최적 수송 (IC-POT) 을 소개하며, 이를 통해 긍정-비표시 학습 및 다중 모달 위성 데이터 분석과 같은 응용 분야에서 더 구조화되고 신뢰할 수 있는 매칭을 가능하게 합니다.

핵심

두 개의 서로 다른 사람 그룹을 춤을 추게 하려고 상상해 보세요. 한 그룹은 '소스'(예를 들어 뉴욕에서 온 댄서들)이고, 다른 그룹은 '타겟'(런던에서 온 댄서들)입니다.

기존 방식 (표준 최적 수송):
전통적으로 규칙은 엄격했습니다: 단 한 명의 댄서도 파트너를 찾지 못하면 안 됩니다. 뉴욕 댄서가 코미디언 코를 쓰고 있고 런던 댄서가 튜튜를 입고 있더라도, 알고리즘은 숫자를 맞추기 위해 그들을 무조건 짝지어야 합니다. 이는 종종 터무니없고 억지스러운 매칭으로 이어져 의미가 없습니다.

'부분적' 방식 (이전 해결책):
나중에 연구자들은 "좋아, 일부 사람들은 짝을 찾지 않아도 돼"라고 말했습니다. 하지만 그들은 전역 예산으로 이를 수행했습니다. 마치 매니저가 "댄서 10% 는 옆구리에 남겨두어도 돼"라고 말하는 것과 같습니다. 매니저는 누가 제외되는지는 상관없습니다; 단지 총수가 10% 라면 됩니다. 만약 제외된 10% 가 최고의 댄서들일 경우, 매칭은 망가집니다. 이 시스템에는 세밀함이 부족합니다.

새로운 방식 (IC-POT - "받아들이거나 버리거나"):
이 논문은 **의도 제어 부분 최적 수송 (IC-POT)**을 소개합니다. 전역 예산 대신, 각 댄서마다 **개인적인 "거부 가격 태그"**를 부여합니다.

각 사람마다 다른 바운서 (클럽 입구 경비원) 가 있는 것처럼 생각하세요:

• "받아들이기" 규칙: 댄서가 신뢰할 수 있고, 옷차림이 단정하며, 분위기에 잘 맞으면 그들의 "거부 가격"은 높습니다. 알고리즘은 "이 사람을 내쫓는 데는 비용이 너무 많이 들기 때문에, 반드시 파트너를 찾아야 한다"고 생각합니다.
• "버리기" 규칙: 댄서가 명백히 어울리지 않는 경우 (예를 들어 정장 무도회에서 코미디언이거나 데이터에 노이즈가 있는 경우), 그들의 "거부 가격"은 낮습니다. 알고리즘은 "이 사람을 옆구리에 남겨두는 데는 비용이 적게 들기 때문에 그렇게 하겠다"고 생각합니다.

실제 생활에서 작동하는 방식 (논문의 예시)

저자들은 이것이 세 가지 구체적인 시나리오에서 작동함을 보여줍니다:

1. "맞추기 게임" (Positive-Unlabeled Learning)
사진 속 모든 고양이를 찾으려고 하지만, 라벨이 붙은 고양이 사진은 몇 장뿐이고 라벨이 없는 사진 (일부는 고양이, 일부는 개) 이 산처럼 쌓여 있다고 상상해 보세요.

• 문제: 일부 고양이는 그림자 속에 숨어 있어 (보기 어려움), 다른 일부는 밝고 선명합니다. 표준 "부분적" 방법은 효율성을 추구하다 그림자 속 고양이들을 버릴 수 있습니다.
• IC-POT 해결책: 시스템은 "그림자" 영역이 단순히 보기 어려울 뿐, 반드시 "고양이가 아니다"라는 것은 아니라고 압니다. 그림자 속 고양이를 거부하는 데 높은 가격 태그를 붙입니다. 이를 매칭에 포함시킵니다. 반면 명백한 개들에게는 낮은 가격 태그를 붙입니다. 결과는 무엇일까요? 개들에게 혼동되지 않고 더 많은 고양이를 찾아냅니다.

2. "언어 장벽" (Open-Partial Domain Adaptation)
새로운 나라의 사진 속 사물을 인식하도록 컴퓨터를 가르친다고 상상해 보세요. 일부 사물 (자동차, 나무) 은 두 나라 모두에 존재하지만, 일부는 새로운 나라에만 존재합니다 (고유한 지역 동물).

• 문제: 컴퓨터는 모든 사람을 짝지어야 한다는 절박함 때문에 지역 동물과 자동차를 억지로 매칭하려 할 수 있습니다.
• IC-POT 해결책: 시스템은 매칭의 "신뢰도"를 봅니다. 만약 지역 동물이 자신의 정체성에 매우 확신하면서도 옛 나라 목록에는 매칭될 대상이 없다면, 시스템은 그 동물에 낮은 거부 가격을 부여합니다. "이 동물을 매칭하지 말고 남겨두어라; 이는 옛 목록에 속하지 않는다"고 말합니다. 하지만 자동차가 명백히 자동차라면, 이를 거부하는 가격은 높기 때문에 매칭됩니다.

3. "바다 전망" (지리 물리 데이터)
이것은 가장 시각적인 예시입니다. 저자들은 파도를 관측하는 두 개의 서로 다른 위성 카메라를 비교했습니다.

• 문제: 한 카메라 (SWIM) 는 파도를 선명하게 보지만 특정 방향에서는 "정전기" (노이즈) 를 겪습니다. 다른 카메라 (SAR) 는 파도를 잘 보지만 물리학적으로 다른 방향에서는 "흐릿하게" 보입니다.
• IC-POT 해결책: 시스템은 물리학적 지식을 가격 태그로 사용합니다.
  • 파도가 카메라 A 에서는 흐릿하지만 카메라 B 에서는 선명하다면, 시스템은 "이것은 실제 파도이지만 카메라 A 가 단순히 안 좋은 날인 것이다. 거부하지 마라."라고 말합니다 (거부 비용 높음).
  • 파도가 카메라 A 에서는 선명하지만 카메라 B 에서는 "정전기"처럼 보인다면, 시스템은 "카메라 B 는 단순히 노이즈를 보고 있다. 이 매칭을 거부하라."라고 말합니다 (거부 비용 낮음).
  • 결과: 실제 파도와 결함 사이에 억지로 매칭을 시도하는 대신, 각 카메라의 특정 "결함"을 무시함으로써 파도의 완벽한 지도를 얻습니다.

큰 교훈

이 논문은 모든 불일치가 동등하게 생성되는 것은 아니다라고 주장합니다.

• 구식 방법: "데이터의 10% 를 무작위로 또는 간단한 규칙에 따라 거부하자."
• IC-POT: "각 데이터 조각을 개별적으로 살펴보자. 신뢰할 수 있으면 유지하고, 신뢰할 수 없거나 노이즈가 있으면 제외하자. 우리는 해당 데이터 조각에 대해 이용 가능한 특정 단서 (그림자, 신뢰도 점수, 또는 센서 물리학 등) 를 기반으로 이를 결정한다."

이는 "무엇을 버릴지"에 대한 결정을 둔한 도구에서 정밀하고 지능적인 도구로 바꿉니다.

기술 요약

기술 요약: 의도 제어 부분 최적 수송 (IC-POT)

문제 정의

고전적 최적 수송 (OT) 은 모든 소스 질량이 수송되어야 하고 모든 타겟 질량이 설명되어야 한다는 경직된 제약을 부과합니다. 이러한 "전체 참여" 가정은 질량의 부분 집합만 관련 있거나 신뢰할 수 있는 분포를 비교할 때 인위적인 대응 관계나 부정적 전이를 초래하는 경우가 많습니다.

부분 최적 수송 (POT) 은 미연결된 질량이 허용되도록 이 제약을 완화하지만, 기존 공식들은 일반적으로 전역 제어 메커니즘에 의존합니다. 여기에는 스칼라 수송 질량 예산, 균일 스칼라 리베이트, 또는 전역 주변 패널티가 포함됩니다. 이러한 메커니즘은 얼마나 많은 질량이 거부되는지는 제어하지만, 어떤 특정 지점이 보호되거나 폐기되어야 하는지는 제어하지 못합니다. 결과적으로, 질량을 미연결 상태로 두는 결정이 측도별 신뢰도, 지지 기하학, 또는 외부 정보 (예: 양성 - 비레이블 (Positive-Unlabeled) 학습에서의 샘플링 편향, 도메인 적응에서의 신뢰도, 또는 지구물리학에서의 센서별 아티팩트) 에 의존하는 응용 분야를 해결하지 못합니다.

방법론: IC-POT

저자들은 **의도 제어 부분 최적 수송 (IC-POT)**을 소개합니다. 이는 소스와 타겟 측도 모두에 대한 점별 (pointwise) 거부 비용을 통해 전역 거부 패러다임을 대체하는 POT 의 표적 일반화입니다.

공식화

질량 $\mu$와 $\nu$를 가진 이산 지지 $X = \{x_i\}$와 $Y = \{y_j\}$ 및 수송 비용 행렬 $C$가 주어졌을 때, IC-POT 는 미연결 소스 질량 $u$와 미연결 타겟 질량 $v$에 대한 슬랙 변수를 도입합니다. 최적화 문제는 다음과 같습니다:

$$\min_{P, u, v} \langle C, P \rangle + \langle c_s, u \rangle + \langle c_t, v \rangle$$
다음 조건 하에서:
$$P\mathbf{1} + u = \mu, \quad P^\top\mathbf{1} + v = \nu, \quad P, u, v \geq 0$$

여기서 $c_s \in \mathbb{R}^n_+$와 $c_t \in \mathbb{R}^m_+$는 점별 미연결 비용입니다. 전역 리베이트와 달리, 이러한 비용은 원래 지지 위에서 특정 질량을 미연결 상태로 두는 지역적 대안을 직접 가격 매깁니다.

구조적 속성

본 논문은 몇 가지 주요 이론적 속성을 확립합니다:

1. 축약된 라그랑주 형식: 이 문제는 부분 결합 (sub-couplings) 위에서 $\sum_{i,j} (C_{ij} - c_s(i) - c_t(j))P_{ij}$를 최소화하는 것과 동등하며, 고전적 POT 의 스칼라 리베이트를 분리 가능한 점별 리베이트로 효과적으로 대체합니다.
2. 이중 해석: 이중 형식은 $c_s(i)$와 $c_t(j)$가 이중 변수에 대한 **지역 수용 임계값 (caps)**으로 작용함을 보여줍니다. 한 지점의 이중 변수가 이 임계값에 도달하면 해당 지점은 거부됩니다.
3. 허용 가능성과 희소성: 엣지 $(i, j)$는 $C_{ij} \leq c_s(i) + c_t(j)$일 때만 최적 수송 계획에서 활성화될 수 있습니다. 이는 특정 거부 비용에 기반하여 수송 그래프를 가지치기 (pruning) 하기 위한 정확한 사전 계산 규칙을 제공하여 희소성을 보장합니다.
4. 증강 지지 동등성: IC-POT 는 각 주변에 더미 점을 추가한 증강 지지 (augmented-support) 위의 표준 균형 카ント로비치 (Kantorovich) OT 문제로 다시 표현될 수 있으며, 이는 이산 OT 프레임워크 내에서 잘 정의됨을 증명합니다.

주요 기여

본 논문은 세 가지 주요 기여를 주장합니다:

1. 미연결 행동의 명시적 모델링: 전역 제약의 암시적 결과가 아닌, 원래 지지 위의 슬랙 변수를 통해 미연결 정책을 공식화에서 명시적 객체로 만듭니다.
2. 이론적 특성화: 이 문제를 분리 가능한 점별 리베이트 일반화된 라그랑주 부분 수송으로 특성화하여, 이중 캡, 희소 허용 규칙, 그리고 상수 비용 부분 OT 와의 엄격한 분리를 확립합니다 (균일 규칙이 보존하는 대칭성을 점별 비용이 깨뜨리는 반례를 통해 입증됨).
3. 실증적 검증: 측도별 정보를 기반으로 한 점별 거부 규칙을 통합하는 것이, 거부가 구조화된 작업 (특히 양성 - 비레이블 (PU) 학습, 오픈 - 부분 도메인 적응 (OPDA), 및 지구물리 신호 비교) 에서 성능을 향상시킨다는 것을 입증합니다.

실험 결과

1. 양성 - 비레이블 (PU) 학습

PU 학습에서는 레이블이 지정된 양성을 잠재적 양성과 음성을 모두 포함하는 비레이블 풀과 매칭하는 것이 목표입니다.

• 설정: 저자들은 공변량 의존 선택 편향으로 인해 특정 지역 ( fringe) 에서 양성 샘플이 과소 관측되는 "무작위 선택 (Selected at Random, SAR)" 시나리오를 시뮬레이션했습니다.
• 결과: 상수 비용 부분 OT 베이스라인 (균일 거부) 은 이러한 과소 관측된 fringe 지역을 음수로 간주하여 보호하지 못했습니다. 반면, 선택 편향을 인코딩하는 소스 측 비용 프로파일 (낮은 관측 fringe 에서 거부를 비싸게 만듦) 을 사용하는 IC-POT 는 베이스라인보다 훨씬 뛰어난 성능을 보였습니다.
• 지표: 이질적 환경에서 IC-POT 는 0.86의 F1 점수를 달성한 반면, 상수 비용 베이스라인은 0.52였습니다.

2. 오픈 - 부분 도메인 적응 (OPDA)

OPDA 에서 타겟 도메인은 거부되어야 할 알려지지 않은 클래스를 포함합니다.

• 설정: 고정된 CLIP 증류 백본을 사용하여 저자들은 최종 거부 레이어만 수정했습니다. 균일 부분-W 베이스라인과 두 가지 IC-POT 변형 (후방 엔트로피를 사용하여 낮은 엔트로피 샘플을 보호하는 경우, 그리고 프로토타입 - 지지를 사용하여 일관된 지역 이웃 합의를 가진 샘플을 보호하는 경우) 을 비교했습니다.
• 결과: 두 IC-POT 변형 모두 여러 데이터셋 (Office-31, Office-Home, VisDA, DomainNet) 에서 균일 베이스라인을 개선했습니다. 프로토타입 - 지지 변형은 지역적으로 일관된 데이터셋에서 가장 큰 개선을 달성했습니다 (예: Office-31 에서 부분-W 의 94.08 대비 95.12 H-score).
• 발견: 표현이 고정되면, 성능 향상은 균일 스칼라 규칙이 아닌 구조 의존적 정책으로서 거부를 모델링하는지에 달려 있음을 시사합니다.

3. 지구물리 사례 연구: SWIM/SAR 해양 파도 스펙트럼

이 실험은 서로 다른 아티팩트를 가진 두 가지 다른 센서 (SWIM 및 SAR) 에서 검색된 해양 파도 스펙트럼을 비교하는 문제를 다룹니다.

• 맥락: SAR 스펙트럼은 "방위각 컷오프 (azimuth cutoff)"로 인해 에너지가 이동하는 반면, SWIM 스펙트럼은 "스펙클 (speckle)"로 인해 신뢰할 수 없는 방향 섹터를 가집니다. 목표는 물리적으로 일관된 파도 시스템만 비교하는 것입니다.
• 방법: IC-POT 는 물리적 사전 지식에서 파생된 측도별 비용을 사용합니다: SWIM 으로 지지되는 경우 컷오프로 이동된 SAR 질량을 보호하면서, 스펙클이 지배적이거나 지지되지 않는 질량은 거부 대상에 노출시킵니다.
• 결과: IC-POT 는 고가 전역 베이스라인과 비교 가능한 파도 에너지 (0.993) 를 회복하면서도 ** spurrious 수송**을 7 배 감소시켰습니다 (0.031 대 0.236).
• 의의: 공통 시스템을 회복하고 아티팩트를 거부하는 것 사이의 절충을 강요하는 스칼라 규칙과 달리, IC-POT 는 거부 정책을 데이터 자체의 물리적 본질에 의해 정의되도록 합니다.

의의 및 한계

본 논문은 IC-POT 가 "얼마나 많이 거부할 것인가"에서 "무엇을 거부할 것인가"로 부분 수송의 패러다임을 전환한다는 점에서 중요하다고 주장합니다. 미연결 정책을 명시적인 점별 변수로 만듦으로써, 도메인별 지식 (샘플링 편향, 신뢰도, 물리적 사전 지식) 이 수송 계획을 직접적으로 informing 할 수 있게 합니다.

저자가 인정하는 한계:

• 명세: 미연결 함수 ($c_s, c_t$) 는 사용 가능한 측도별 정보 또는 진단에 기반하여 사용자가 지정해야 합니다. 본 논문은 이러한 함수를 데이터에서 자동으로 학습하는 방법을 제안하지는 않지만, 향후 방향 (예: 이레벨 최적화를 통한) 으로 제안합니다.
• 확장성: 희소 솔버는 정확하지만, 대규모 응용 분야는 추가적인 근사가 필요할 수 있습니다.
• 정규화: 저자들은 표준 엔트로피 정규화 (Sinkhorn) 가 목적 함수를 변경 (전체 수송 질량에 편향 도입) 하거나 더미 점과 실제 점 사이의 규모 불일치를 초래하지 않는 한 증강 지지 공식에 직접 적용되지 않는다고 지적합니다. 따라서 IC-POT 는 표준 엔트로피 OT 솔버의 바로 교체 가능한 (drop-in) 대안이 아닙니다.

결론적으로, IC-POT 는 구조화된 거부를 위한 유연한 프레임워크를 제공하며, "미연결" 결정이 본질적으로 균일하지 않은 작업에서 측도별 거부 비용에 측도별 정보를 인코딩하는 것이 우수한 성능을 산출함을 입증합니다.