유한 Wasserstein 위험과 정확한 쌍대 인증

확률 차이에 운송 기하를 더한다

케이엘 재가중은 확률을 직접 비교합니다. 운송 모호 집합은 결과 사이의 기하도 사용하므로 가까운 결과로 질량을 보내는 비용과 먼 결과로 보내는 비용을 구분합니다. 이 단원은 원시와 쌍대 값을 정확히 비교할 수 있는 유한 예제를 다룹니다.

출발 위치와 허용 도착 위치는 마이너스 일과 영과 일입니다. 기준 질량은 영 점 이와 영 점 삼과 영 점 오입니다. 도착 위치도 같은 세 점으로 제한됩니다. 이 유한 지지집합의 인증을 실수 공간 모든 위치나 미지의 미래 분포에 대한 인증으로 확대하면 안 됩니다.

운송 계획과 행 질량을 정의한다

각 행렬 성분은 한 출발 위치에서 도착 위치로 보내는 확률 질량입니다. 행 질량은 고정됩니다.

$$\pi_{ij}\ge0,\qquad\sum_j\pi_{ij}=p_i.$$

열의 합이 대안 분포를 만듭니다. 행 분포는 기준 모집단을 나타내고 열 분포는 비용 안에서 불리하게 선택됩니다. 모든 질량에는 출발지가 있지만 마지막 열 분포만으로 전체 운송 계획이 정해지지는 않습니다.

기본 비용은 위치 차이의 절댓값입니다. 전체 비용은 질량과 거리의 곱을 합한 평균 비용이며 개별 질량의 최대 이동 거리가 아닙니다.

유한 최악 위험 문제를 세운다

도착지 손실을 고정한 뒤 다음 문제를 풉니다.

$$\max_{\pi\ge0}\sum_{ij}\pi_{ij}l_j \quad\text{subject to}\quad \sum_j\pi_{ij}=p_i,\qquad\sum_{ij}\pi_{ij}c_{ij}\le\rho.$$

모형과 손실은 고정되며 예측기를 학습하는 문제가 아닙니다. 선택한 운송 예산이 현실을 포함한다는 통계적 보장도 따로 필요합니다. 제자리 운송은 음이 아닌 모든 반경에서 실행 가능하므로 집합이 비어 있지 않고 최악 위험은 명목 위험 이상입니다.

음이 아닌 행 질량의 합이 고정되어 실행 가능한 다면체는 유계입니다. 따라서 최적해가 존재합니다. 상수 손실이나 동률에서는 여러 계획이 최적일 수 있으므로 화면의 계획은 선택한 증인 하나입니다.

필요한 극점 형태를 빠짐없이 열거한다

콤팩트 다면체 위의 선형 목적은 극점에서 최적값을 갖습니다. 양의 행 질량 세 개와 비활성 비용 제약에서는 각 행을 도착지 하나로 보내는 결정론적 계획이 극점이 됩니다. 비용 제약이 활성이라면 기본 실행 가능한 계획에는 최대 네 개의 양의 성분이 있어 한 행만 두 도착지로 나뉘고 나머지는 하나로 보내는 형태면 충분합니다.

계산은 모든 결정론적 배정과 예산을 맞추는 한 행의 분할을 검사합니다. 비용이 같은 방향의 분할은 새로운 고립 극점을 만들지 않아 양 끝 배정으로 충분합니다. 이 논증이 작은 선형계획에서 후보 열거가 완전한 이유이며 촘촘한 격자를 믿는 것과 다릅니다.

최대값을 갖는 후보가 전체 최적 운송 집합은 아닙니다. 목적이나 한계 예산 가치가 동률이면 한 면 전체에서 같은 값이 나올 수 있습니다.

비용의 쌍대 가격으로 상계를 유도한다

음이 아닌 가격을 선택하면 모든 실행 가능한 계획에서 다음 부등식이 성립합니다.

$$\sum_{ij}\pi_{ij}l_j =\lambda\sum_{ij}\pi_{ij}c_{ij}+\sum_{ij}\pi_{ij}(l_j-\lambda c_{ij}) \le\lambda\rho+\sum_ip_i\max_j(l_j-\lambda c_{ij}).$$

첫 항은 운송 비용에 가격을 매기고 두 번째 항은 출발 행마다 남은 손실과 가격 차이의 최대값을 사용합니다. 어떤 음이 아닌 가격도 유효한 상계이며 이를 최소화한 것이 쌍대입니다.

각 출발지의 최대값은 가격에 대한 선형 함수들의 포락선입니다. 기울기는 두 함수가 만나는 점에서만 바뀝니다. 음이 아닌 교점과 영을 비교하면 쌍대 최적 가격을 찾을 수 있습니다. 실행 가능한 원시 계획과 유효한 쌍대 상계가 같은 값을 가지면 약한 쌍대성만으로도 전역 최적성이 증명됩니다.

허용 격자에서 정확한 산술을 보존한다

기준 확률은 사십을 분모로 한 정수 질량 팔과 십이와 이십으로 표현합니다. 반경은 정수 제어값을 이십으로 나눕니다. 비용은 영과 일과 이이므로 후보 질량 분할과 가격의 분모가 제한됩니다. 계획 질량은 현재 단위에서 정수이고 가격은 이분의 일 격자입니다.

원시와 쌍대 위험은 모두 사십을 공통 분모로 한 정수 분자를 갖습니다. 행 합과 비음성과 비용 실행 가능성을 확인한 뒤 분자가 같음을 검사합니다. 이는 현재의 유한 모형에 대한 정확 인증이며 로그를 사용하는 케이엘 수치 해와 구분됩니다.

이 성질은 고정 지지집합과 질량과 예산 격자에 의존합니다. 임의의 실수 확률이나 비용으로 바꾸면 다른 산술 분석이 필요합니다. 소수 자릿수를 많이 표시하는 것으로 정확한 증명이 복구되지는 않습니다.

영 예산과 작은 예산을 계산한다

손실이 영과 일과 삼이면 명목 위험은 다음과 같습니다.

$$0.2\cdot0+0.3\cdot1+0.5\cdot3=9/5.$$

서로 다른 지지점 사이에는 양의 비용이 있으므로 영 예산에서는 제자리 이동만 가능합니다. 따라서 대안 분포는 기준 분포와 같습니다.

반경 영 점 일에서는 가운데 질량 영 점 일을 오른쪽으로 거리 일만큼 옮깁니다. 평균 비용은 영 점 일이고 대안 분포는 영 점 이와 영 점 이와 영 점 육입니다. 위험은 이입니다. 쌍대 가격 이를 쓰면 각 행에서 손실과 가격 차이의 최대값은 영과 일과 삼이고 예산 가격 항이 영 점 이를 더해 같은 위험 이를 줍니다.

이 예제는 평균 비용과 개별 반경의 차이를 보여 줍니다. 같은 이산 지지집합에서 관측값마다 영 점 일만 이동하게 하면 다른 도착지에 갈 수 없습니다. 평균 비용 예산에서는 작은 질량이 거리 일을 이동할 수 있습니다.

예산의 한계 효과와 포화를 읽는다

처음에는 가운데 질량을 오른쪽으로 옮기면 거리 한 단위당 손실 이를 얻습니다. 가운데 질량을 모두 옮긴 뒤에는 왼쪽 질량을 오른쪽으로 보내 거리당 이분의 삼을 얻습니다. 반경 영 점 오에서는 대안 분포가 영 점 일과 영과 영 점 구이며 위험은 십 분의 이십칠이고 쌍대 가격은 이분의 삼입니다.

반경 영 점 칠에서는 모든 질량이 최대 손실 도착지에 갈 수 있어 위험 삼에서 포화합니다. 선택한 쌍대 가격은 영일 수 있지만 이 임계값에서는 비용 제약이 여전히 등호입니다. 가격 영이면 제약이 반드시 느슨하다는 역방향 결론은 상보성에서 나오지 않습니다.

구간별 선형 위험 포락선은 최적 이동 패턴의 변화를 반영합니다. 그 기울기와 가격은 유한 최적화의 의미를 가지며 같은 숫자의 케이엘 반경이나 입력 섭동 반경이 같은 불확실성을 나타낸다는 뜻은 아닙니다.

흐름 그림과 쌍대 그림을 연결한다

첫 그림의 출발 행과 도착 열 사이 선은 양의 운송 질량입니다. 선 두께는 확률 질량을 나타내고 라벨은 정수 질량 단위를 보존합니다. 표시 비용과 예산을 먼저 비교한 뒤 원시와 쌍대 일치를 인증으로 읽습니다.

두 번째 그림은 가격에 따른 쌍대 상계와 선택한 가격을 보여 줍니다. 모서리나 평평한 구간에서는 여러 가격이 최적일 수 있습니다. 마지막 그림은 손실을 고정하고 평균 비용 예산을 바꾼 위험이며 물리적 운송 시간이나 학습 궤적이 아닙니다.

연습 문제와 해설

1. 영 예산에서 서로 다른 위치로 보낼 수 없는 이유는 무엇인가요? 해설: 그런 이동은 양의 비용이고 질량이 음이 아니므로 상쇄할 수 없습니다.
2. 질량 영 점 일이 거리 일을 이동할 수 있나요? 해설: 평균 비용은 곱인 영 점 일이므로 해당 예산에서 가능합니다.
3. 원시와 쌍대의 일치가 왜 최적성을 증명하나요? 해설: 모든 가능한 위험이 쌍대 상계 이하인데 실행 가능한 계획이 이미 그 값에 도달하기 때문입니다.
4. 위험이 같으면 계획도 유일한가요? 해설: 같은 최적값을 갖는 면 전체가 있을 수 있어 아닙니다.
5. 가격 영이면 비용이 반드시 예산보다 작은가요? 해설: 반경 영 점 칠의 포화 경계에서는 비용이 예산과 같으면서 최적 가격이 영일 수 있습니다.
6. 모든 손실에 이를 더하면 어떻게 되나요? 해설: 전체 운송 질량이 일이므로 위험도 이만큼 증가합니다.
7. 알려지지 않은 도착지까지 이 인증이 포함하나요? 해설: 지지집합과 손실이 문제의 명시적 제약이었으므로 아닙니다.

통계적 질문과 연결한다

Mohajerin Esfahani·Kuhn은 명시된 가정 아래 Wasserstein 강건 최적화와 재정식화 및 성능 보장을 연구합니다. 현재 유한 선형계획은 운송 모호 집합과 쌍대성을 직접 설명하며 그 전체 이론의 재현이 아닙니다. 다음 원래 주제는 수학적 보장과 실제 평가를 연결하며 실제 분포가 모형 안에 있다는 별도 질문도 다룹니다.