狠狠撸

狠狠撸Share a Scribd company logo
確率分布間の距離をどう測るか?
A summary on “On choosing and bounding
probability metrics”
June 20, 2018
松井孝太
理研 AIP データ駆動型生物医科学チーム
Table of contents
1. Introduction
2. 10 metrics on probability measures
3. Some relationships among probability metrics
4. Why Wasserstein distance?
1
Introduction
Introduction I
Alison et al. [2002], “On choosing and bounding
probability metrics” の 3 章までのまとめ
問題意識
最近 Wasserstein distance を使った ML の方法論が (と
りわけ domain adaptation の文脈で)  次々提案されて
いるが, なぜ Wasserstein distance を使うのが良いのか
を知りたかった
2
Introduction II
? 確率分布間の metric として何を使えば良いのか問題.
? metric の選び方によって問題の解釈や理論的性質, 使
える bound テクも変わってくる.
? もし metric 間の関係が明らかであれば, 1 つの metric
の理論を他の metric に拡張することができる.
この論文 (Alison et al., 2002) では
? 10 種類の重要な metric を review し, その間の関係を
サーベイする (このスライドの目的).
? 各 metric の応用や, metric を取り替えることによっ
て (様々な) 収束レートが変動することの例示.
3
10 metrics on probability
measures
Preliminary
Notation
? (?, B) : (Borel) 可測空間
? P(?) : ? 上の確率測度の集合
? ?, ν ∈ P(?) に対して, f, g をそれぞれ ?, ν の σ-有限
な λ に関する密度関数とする. (i.e. ?, ν ? λ)
? supp(?) = {ω ∈ ? | ?(ω) > 0} (? のサポート)
? ? = R のとき, F, G をそれぞれ ?, ν の累積分布関数と
する. また, X, Y をそれぞれ ? 上の確率変数とすると
き, これらから誘導される分布を L(X) = ?, L(Y) = ν
と書くこともある.
? (?, d) が有界距離空間のとき, ? の直径を以下で定義
diam(?) = sup
x,y∈?
d(x, y).
4
Preliminary
? Cb(?) : ? 上の有界連続関数の集合
De?nition 1 (弱収束, weak convergence)
?n, ? ∈ P(?), n = 1, 2, ... とする. ?f ∈ Cb(?) に対して,
∫
?
f(x)?n(dx) →
∫
?
f(x)?(dx)
が成り立つとき, {?n} は ? に弱収束するといい, ?n ? ?
と書く.
Remark 1
確率変数 Xn, X の分布を ?n, ? とするとき, ?n ? ? であれ
ば Xn は X に分布収束 (or 法則収束) するといい, Xn →d X
と書く. 5
Preliminary
P(?) は弱収束の位相によって位相空間とみなせる.
De?nition 2 (弱収束の距離付け可能性)
P(?) 上のある距離 d が定める位相が弱収束の位相と一
致するとき (すなわち, d による収束と弱収束が同値であ
るとき), P(?) は d で距離付け可能という.
Remark 2
本論文では, 弱収束が距離付け可能かどうかは, 確率分布
間の距離の評価指標の 1 つとして重視される.
6
1. Discrepancy metric
De?nition 3 (Discrepancy metric)
? を距離空間とする.
dD(?, ν) := sup
B∈B
|?(B) ? ν(B)| ∈ [0, 1],
ここで, B は ? 上の閉球全体の集合.
? base space ? の距離位相に基づいた距離 (閉球の体
積比較).
? スケール不変 (ベース空間の距離を正の定数倍しても
dD は変わらず)
? Fourier bound を達成する (cf : 群上のランダムウォー
クの収束証明)
7
2. Hellinger distance I
De?nition 4 (Hellinger distance)
? を可測空間とする. f, g をそれぞれ ?, ν(? λ) の密度関
数とするとき,
dH(?, ν) :=
[∫
?
(f1/2
? g1/2
)2
dλ
]1/2
=
[
2
(
1 ?
∫
?
(fg)1/2
dλ
)]1/2
∈ [0,
√
2]
この定義は reference measure λ のとり方によらない. ?
が可算集合のときは以下のように書ける:
dH(?, ν) :=
[
∑
ω∈?
(?(ω)1/2
? ν(ω)1/2
)2
]1/2
.
8
2. Hellinger distance II
? ? = ?1 × ?2, ν = ν1 × ν2 なる直積測度を考えると,
1 ?
1
2
d2
H(?, ν) =
(
1 ?
1
2
d2
H(?1, ν1)
) (
1 ?
1
2
d2
H(?2, ν2)
)
が成立. すなわち, ベクトル v が v = (v1, v2) のように
独立な成分を並べた形をしている場合, 対応する分布
は, 成分毎の分布の積に分解できる. 左辺は Hellinger
af?nity と呼ばれる. また, 上の事実の系として
d2
H(?, ν) ≤ d2
H(?1, ν1) + d2
H(?2, ν2)
が成立.
9
3. Relative Entropy (Kullback-Leibler divergence) I
De?nition 5 (Relative entropy)
? を可測空間とする. f, g をそれぞれ ?, ν(? λ) の密度関
数とするとき,
dI(?, ν) :=
∫
supp(?)
f log
f
g
dλ ∈ [0, +∞],
ここで, supp(?) ? ? は ? のサポートである. この定義は
reference measure λ のとり方によらない. ? が可算集合
のときは以下のように書ける:
dI(?, ν) =
∑
ω∈?
?(ω) log
?(ω)
ν(ω)
.
10
3. Relative Entropy (Kullback-Leibler divergence) II
? 慣習的に, 任意の q ∈ R に対して
0 × log
0
q
= 0
また, 任意の p ?= 0 に対して
p × log
p
0
= +∞
とする (ために, dI ∈ [0, +∞] となる).
? 非対称かつ三角不等式を満たさないため, 距離ではな
い. 一方で, 直積測度 ? = ?1 × ?2, ν = ν1 × ν2 に対して
加法性
dI(?, ν) = dI(?1, ν1) + dI(?2, ν2)
を満たす.
11
4. Kolmogorov (Uniform) metric
De?nition 6 (Kolmogorov metric)
? = R とする. Kolmogorov metric は, R 上の分布 ?, ν の
間の距離を, 対応する分布関数 F, G の間の距離として表
現する:
dK(F, G) := sup
x∈R
|F(x) ? G(x)| ∈ [0, 1],
? 単調増加な 1 対 1 変換に関して不変である.
12
5. L?evy metric
De?nition 7 (L?evy metric)
? = R とする.
dL(F, G)
:= inf{ε > 0 : G(x ? ε) ? ε ≤ F(x) ≤ G(x + ε) + ε, ?x ∈ R}
∈ [0, 1],
? L?evy metric は, R 上の弱収束位相を距離付けする:
Fn →d F as n → ∞ iff dL(Fn, F) → 0 as n → ∞.
? shift-invariant だが scale-invariant ではない.
13
6. Prokhorov ( or L?evy-Prokhorov) metric
De?nition 8 (Prokhorov metric)
? を距離空間とする.
dP(?, ν) := inf{ε > 0 : ?(B) ≤ ν(Bε) + ε, ?B ?Borel ?} ∈ [0, 1],
ここで, Bε = {x : infy∈B d(x, y) ≤ ε}.
? dP は対称性を持つ.
?
14
7. Separation distance
De?nition 9 (Separation distance)
? を可算空間とする.
dS(?, ν) := max
i
(
1 ?
?(i)
ν(i)
)
∈ [0, 1].
? dS は厳密な距離ではない.
? マルコフ連鎖の解析のために導入された.
15
8. Total variation I
De?nition 10 (Total variation)
? を可測空間とする.
dTV(?, ν) := sup
A??
|?(A) ? ν(A)|
=
1
2
max
|h|≤1
∫
hd? ?
∫
hdν ∈ [0, 1],
ここで, h : ? → R. ? が可算空間のとき,
dTV :=
1
2
∑
ω∈?
|?(ω) ? ν(ω)|
と定める. これは L1 ノルムの 1/2 倍であり, 文献によっ
ては 2dTV を total variation と定義するものもある.
16
8. Total variation II
Total variation はカップリング測度の inf として特徴付け
ができる:
dTV(?, ν) = inf{Pr(X ?= Y) | X, Y : r.v. s.t. L(X) = ?, L(Y) = ν}
(1)
17
9. Wasserstein (or Kantorovich) distance I
De?nition 11 (Wasserstein distance)
? を可分距離空間とする. ?, ν の 1-Wasserstein distance
を
dW(?, ν) = inf
π∈Π(?,ν)
∫
?×?
d(x, y)dπ(x, y)
で定義する. ここで,
Π(?, ν) := {π : prob. measure on ? × ? |
π(B × ?) = ?(B), π(? × B) = ν(B), ?B ? ?}
を ? 上のカップリング測度の集合と呼ぶ.
18
9. Wasserstein (or Kantorovich) distance II
? Kantorovich-Rubinstein duality より,
dW(?, ν) = sup
∥h∥L≤1
∫
hd? ?
∫
hdν ∈ [0, diam(?)]
が成立. ここで, sup は Lipschitz condition
|h(x) ? h(y)| ≤ d(x, y) を満たす h について取る. この
右辺を Kantorovich metric と呼ぶ.
? 特に ? = R のとき, 右辺は以下のように書ける:
∫ ∞
?∞
|F(x) ? G(x)|dx =
∫ 1
0
|F?1
(t) ? G?1
(t)|dt
19
10. χ2
-distance I
De?nition 12 (χ2
distance)
? を可測空間とする. f, g をそれぞれ ?, ν(? λ) の密度関
数とするとき,
dχ2 (?, ν) :=
∫
supp(?)∪supp(ν)
(f ? g)2
g
dλ ∈ [0, ∞].
特に ? が可算空間のとき以下のように書ける:
dχ2 (?, ν) :=
∑
ω∈supp(?)∪supp(ν)
(?(ω) ? ν(ω))2
ν(ω)
.
20
10. χ2
-distance II
この metric は対称性を持たない (すなわち距離ではない).
一方で, 直積測度 ? = ?1 × ?2, ν = ν1 × ν2 に対して,
Hellinger distance や relative entropy と同様に
dχ2 (?, ν) ≤ dχ2 (?1, ν1) + dχ2 (?2, ν2)
が成立.
21
Remarks
任意の凸関数 f に対して, ? と ν の間の f-divergence を
df(?, ν) :=
∑
ω
ν(ω)f
(
?(ω)
ν(ω)
)
で定義すると, 種々の metric を統一的に表現できる.
22
Example I : χ2
-distance
f(x) = (x ? 1)2
ととると, χ2
-distance が導出される:
df(?, ν) =
∑
ω
ν(ω)
(
?(ω)
ν(ω)
? 1
)2
=
∑
ω
ν(ω)
(
?(ω) ? ν(ω)
ν(ω)
)2
= dχ2 (?, ν)
23
Example II : relative entropy
f(x) = x log x ととると, relative entropy が導出される:
df(?, ν) =
∑
ω
ν(ω)
?(ω)
ν(ω)
log
?(ω)
ν(ω)
=
∑
ω
?(ω) log
?(ω)
ν(ω)
= dI(?, ν)
24
Example III : total variation
f(x) = |x?1|
2
ととると, total variation が導出される:
df(?, ν) =
∑
ω
ν(ω)
|?(ω)
ν(ω)
? 1|
2
=
1
2
∑
ω
|?(ω) ? ν(ω)|
= dTV(?, ν)
25
Example IV : Hellinger distance
f(x) = (
√
x ? 1)2
ととると, Hellinger distance が導出され
る:
df(?, ν) =
∑
ω
ν(ω)
(√
?(ω)
ν(ω)
? 1
)2
=
∑
ω
ν(ω)
(
?(ω)
ν(ω)
? 2
√
?(ω)
ν(ω)
? 1
)
=
∑
ω
(
?(ω) ? 2
√
?(ω)ν(ω) ? ν(ω)
)
=
∑
ω
(√
?(ω) ?
√
ν(ω)
)2
= dH(?, ν)2
26
Some relationships among
probability metrics
S
?
?
?
?
?
?■ x
TV ?x
?√
2x
H
W
on
metric
spaces
?
?
?
?
?
??
x/dmin ?
?
?
?
?
?■ diam? · x
?
√
x
?
(diam? + 1) x
?
?
?
?
?
??√
x/2
ν dom ?
?
?
?
?
?
?■
√
x?x/2
I ?log(1 + x)
χ2 non-metric
distances
?√
x
ν dom ?
?x
P
?
?
?
?
?
??x
D
?
2x
?x
K L on IR
?x
?x
?(1 + sup |G′|)x
?x + φ(x)
論文 Figure 1 の確率分布間の距離の関係の詳細を見る.
27
Kolmogorov-L?evy on R
Fact 1
確率測度 ?, ν ∈ P(R) の分布関数をそれぞれ F, G とする
とき,
dL(F, G) ≤ dK(F, G) (2)
が成立 (Huber, 1981). さらに, もし G がルベーグ測度に
対して絶対連続であれば,
dK(F, G) ≤
(
1 + sup
x
|G′
(x)|
)
dL(F, G)
が成立 (Petrov, 1995). ここで, G′
は G の微分 (密度関数)
を表す.
28
Discrepancy-Kolmogorov on R
Fact 2
確率測度 ?, ν ∈ P(R) の分布関数をそれぞれ F, G とする
とき,
dK(F, G) ≤ dD(?, ν) ≤ 2dK(F, G) (3)
が成立.
29
Prokhorov-L?evy on R
Fact 3
確率測度 ?, ν ∈ P(R) の分布関数をそれぞれ F, G とする
とき,
dL(F, G) ≤ dP(?, ν)
が成立 (Huber, 1981).
30
Prokhorov-Discrepancy I
Theorem 1
? を任意の距離空間, ν を
ν(Bε) ≤ ν(B) + ?(ε), ?B : ball on ?
を満たす任意の確率測度とする. ここで, ? は右連続な関
数とする (任意の ball を ε だけ膨らませた ball の体積の
増え方は, ある右連続関数で記述される). このとき,
dP(?, ν) = x を満たす任意の確率測度 ? に対して,
dD(?, ν) ≤ x + ?(x)
が成立. すなわち,
dD(?, ν) ≤ dP(?, ν) + ?(dP(?, ν))
31
Prokhorov-Discrepancy II
Example 1
ν として S1
または R 上の一様分布をとる (ν = U). この
とき, ?(x) = 2x ととると,
dD(?, U) ≤ 3dP(?, U)
が成立.
(proof) ν(Bx) ≤ ν(B) + ?(x) より,
?(B) ? ν(Bx) ≥ ?(B) ? ν(B) ? ?(x)
が成立. dP(?, ν) = x ならば, ??x > x に対して,
?(B) ? ν(B?x) ≤ ?x
が成立 (上式を満たす ?x の inf が dP). 32
Prokhorov-Discrepancy III
(proof つづき) 2 つの不等式を合わせると,
?(B) ? ν(B) ? ?(?x) ≤ ?x
となり, B に関して sup をとると,
sup
B
(?(B) ? ν(B)) ≤ ?x + ?(?x) (4)
を得る. ここで,
ν(B) ? ?(B) = 1 ? ν(Bc
) ? (1 ? ?(Bc
)) = ?(Bc
) ? ν(Bc
)
より (Bc
は B の補集合),
sup
B
(ν(B) ? ?(B)) = sup
Bc
(?(Bc
) ? ν(Bc
)) ≤ ?x + ?(?x) (5)
が成立.
33
Prokhorov-Discrepancy IV
(proof つづき) (4) と (5) 及び supB ≤ supB,Bc より,
dD(?, ν) ≤ ?x + ?(?x)
を得る. 右辺で ?x ↘ x とすれば, 所望の結果を得る (? は右
連続だから, ?(x) = lim
?x↘x
?(?x) は存在). 2
34
Prokhorov-Wasserstein I
Theorem 2
? が完備可分な距離空間のとき,
(dP)2
≤ dW ≤ (diam(?) + 1)dP
が成立.
(proof) J を確率変数 X, Y の同時分布とするとき,
EJ[d(X, Y)] ≤ ε × Pr(d(X, Y) ≤ ε) + diam(?) × Pr(d(X, Y) > ε)
= ε × (1 ? Pr(d(X, Y) > ε))
+ diam(?) × Pr(d(X, Y) > ε)
= ε + (diam(?) ? ε) × Pr(d(X, Y) > ε)
が成立 (ε を実現値として期待値を書き, 上からバウンド). 35
Prokhorov-Wasserstein II
dP(?, ν) ≤ ε であるとき,
Prπ(d(X, Y) > ε) ≤ ε
を満たす π ∈ Π(?, ν) がとれる (Huber, 1981). このとき,
EJ[d(X, Y)] ≤ ε + (diam(?) ? ε
≤diam(?)
)ε ≤ (diam(?) + 1)ε
が成り立つから, π ∈ Π(?, ν) に関する inf をとれば,
dW ≤ (diam(?) + 1)dP
が成立 (主張の右側の不等号).
36
Prokhorov-Wasserstein III
一方で, ε を dW(?, ν) = ε2
となるようにとると, Markov の
不等式 (Pr(|X| > a) ≤ 1
a
E[|X|]) より
Pr(d(X, Y) > ε) ≤
1
ε
EJ[d(X, Y)] ≤
1
ε
× ε2
= ε
が成立.
Lemma 1 (Strassen’s theorem)
?B ?Borel ? に対して,
Pr(d(X, Y) > ε) ≤ ε ?? ?(B) ≤ ν(Bε) + ε.
Lemma 1で ε の inf をとれば, 所望の結果を得る:
dP ≤ ε ? (dP)2
≤ ε2
= dW. 2 37
Prokhorov-Wasserstein IV
Remark 3
? ? が非有界のとき, 定理のようなバウンドは不成立.
Example 2 (Theorem 2 の反例 (Dudkey, 1989))
? = R とし,
Pn :=
(n ? 1)δ0 + δn
n
とおくと, dP(Pn, δ0) → 0 as n → ∞ だが, dW(Pn, δ0) = 1, ?n
となる.
? Theorem 2の特別な場合として, (?, d) が完備可分距
離空間で d ≤ 1 のとき, 以下が成立  (Huber, 1981):
(dP)2
≤ dW ≤ 2dP. 38
Wasserstein-Discrepancy I
Theorem 3
? が有限集合のとき,
dmin × dD ≤ dW
が成り立つ. ここで, dmin = minx?=y d(x, y) である.
Remark 4
この定理の左辺は, ? が無限集合のとき, dmin をいくらで
も小さくできる場合があり, 確率分布間の距離の比較と
しては情報がほとんどないことがある (Theorem 4の節
も参照).
39
Total variation-Discrepancy
Discrepancy はすべての ball に関する sup であり, total
variation はすべての可測集合に関する sup であるから,
明らかに
dD ≤ dTV
が成り立つ (後者の方が sup をとる範囲が広い).
Remark 5
離散分布 · 連続分布どちらの状況でも, dTV=1 = 1 かつ dD
をいくらでも小さくできる場合があるため, 逆向き
(dTV ≤ dD) は言えない.
40
Total variation-Prokhorov
? が距離空間のとき, ?, ν ∈ P(?) に対して,
dP ≤ dTV
が成立 (Huber, 1981).
41
Wasserstein-Total variation I
Theorem 4
次の bound が成り立つ:
dW ≤ diam(?) × dTV.
? が有限集合のとき, Theorem 3 と同様の bound が成立:
dmin × dTV ≤ dW.
Remark 6
? が無限集合のとき, Theorem 3と同様に dmin をいくら
でも小さくでき得るので, less information な可能性が
ある.
42
Wasserstein-Total variation II
(proof) 最初の不等式は, general な不等式
d(X, Y) ≤ 1X?=Y × diam(?)
に対して, 両辺で coupling measure に関する inf をとると
得られる (TV distance における (1) による). 逆向きの不等
式は,
d(X, Y) ≥ 1X?=Y × min
a?=b
d(a, b)
の両辺で coupling measure に関して inf をとれば OK.
43
Hellinger-Total variation
Fact 4 (LeCam, 1969)
d2
H
2
≤ dTV ≤ dH
44
Separation distance-Total variation
Fact 5 (Aldous & Diaconis, 1987)
dTV ≤ dS
逆は一般に成り立たない.
(∵) ?, ν をそれぞれ {1, ..., n}, {1, ..., n ? 1} 上の一様分布と
すると,
dTV(?, ν) =
1
n
≤ dS(?, ν) = 1
2
45
Relative entropy-Total variation
Fact 6 (Kullback, 1967)
? が可算空間のとき,
2d2
TV ≤ dI
46
Relative entropy-Hellinger
Fact 7 (Reiss, 1989)
d2
H ≤ dI
47
χ2
-Hellinger
Fact 8 (Reiss, 1989)
dH ≤
√
2d
1/4
χ2 .
さらに, ? が ν に対して絶対連続であれば,
dH ≤ d
1/2
χ2
が成立.
48
χ2
-Total variation
Fact 9
可算空間 ? において, Cauchy-Schwarz の不等式から,
dTV(?, ν) =
1
2
∑
ω∈?
|?(ω) ? ν(ω)|
√
ν(ω)
√
ν(ω) ≤
1
2
√
dχ2 (?, ν)
が成立.
Remark 7
? が連続な空間の場合でも, ? が ν に対して絶対連続で
あれば同様の結果が成立 (Reiss, 1989).
49
χ2
-Relative entropy I
Theorem 5
dI(?, ν) ≤ log(1 + dχ2 (?, ν))
が成り立つ. 特に, dI ≤ dχ2
(proof) log の concavity より, Jensen の不等式を用いると
dI(?, ν) =
∫
?
f log
f
g
dλ ≤
Jensen
log
(∫
?
f
g
fdλ
)
= log
(
1 + dχ2 (?, ν)
)
≤ dχ2 (?, ν)
が成立. 50
χ2
-Relative entropy II
(proof つづき) ここで, 2 番目の等号は以下による:
dχ2 (?, ν) =
∫
?
(f ? g)2
g
dλ =
∫
?
(
f
g
f ? 2f + g
)
=
∫
?
f
g
fdλ ? 2
∫
?
fdλ
=1
+
∫
?
gdλ
=1
=
∫
?
f
g
fdλ ? 1.
また, 最後の不等号は, log(x + 1) ≤ x から従う. 2
Remark 8
Diaconis & Saloff-Coste (1996) による bound:
dI(?, ν) ≤ dTV(?, ν) +
1
2
dχ2 (?, ν) 51
Weak Convergence I
? Figure 1 のダイアグラムは, 個々の metric 間の関係
(bound) を導出するだけでなく, 確率測度空間に誘導
される位相の関係も示している.
? 例えば, Hellinger metric と Total variation の間の相
互の矢印 H ? TV は, これら 2 つの metric が誘導す
る位相が同値であることを示す.
? また, Prokhorov や L?evy は弱位相を距離付けするが,
他のどの metric がどのような base space 上で同様
に弱位相を距離付けするかを次の定理にまとめる.
52
Weak Convergence II
Theorem 6
? P(R) に対して, L?evy は弱収束を距離付けする. また,
discrepancy や Kolmogorov は L?evy の upper bound
を与える ((2), (3) 式参照) ので, L?evy を通して弱収束
を誘導する. さらに, discrepancy と Kolmogorov は ?
が R 上のルベーグ測度に対して絶対連続のとき, 弱収
束 ?n → ? を距離付けする.
? ? が可測空間のとき, Prokhorov は弱収束を距離付け
する. また, Wasserstein による収束は弱収束を誘導す
る. さらに, ? が有界であれば, Wasserstein は弱収束
を距離付けする (Prokhorov の upper bound より).
53
Weak Convergence III
Theorem 7 (つづき)
? 次の metric による収束は弱収束を誘導する:
? Hellinger
? separation
? relative entropy
? χ2
? ? が有限かつ有界のとき, total variation と Hellinger
は弱収束を距離付けする.
54
Why Wasserstein distance?
Way Wasserstein distance? I
Wasserstein は弱収束を距離付けする distance measure
他の distance measure との関係 (tightness)
? Wasserstein ≤ (diam(?) + 1)× Prokhorov
? Wasserstein ≤ diam(?)× Total variation
? Wasserstein ≤
√
2 × diam(?) × KL div.
Key Inequality (Csisz?ar-Kullback-Pinsker)
For p, q ∈ P(?),
W1(p, q) ≤ diam(?)∥p ? q∥TV ≤
√
2diam(?)KL(p||q)
55
Way Wasserstein distance? II
Domain adaptation の文脈では...
Wasserstein distance を用いるメリット
1. 2 つの分布のサポートに overlap がない場合でも,
meaningful な距離を与えてくれる (KL などの
f-divergence は, 分布の比が発散するのでダメ).
2. 分布間の距離だけでなく, “どう近づければ良いか?”
という方法も輸送写像として同時に与えてくれる.
3. データの位相的性質を保存する (輸送写像の連続性?)
4. 汎化誤差の bound が他の metric よりも tight.
ref Courty, N. et al. [2017] “Optimal transport for domain
adaptation.” 56
Way Wasserstein distance? III
Domain adaptation を adversarial training (Wasserstein
GAN) として実現できる :
inf
fg
W1(PhS , Pht ) = inf
fg
sup
∥fw∥L≤1
EPxs [fw(fg(x))] ? EPxt [fw(fg(x))]
? Pxs , Pxt は source, target のデータ分布
? fw は discriminator (Wasserstein dist. の推定を行う)
? fg は generator (source と target の特徴抽出を行う)
ref Shen, J. et al. [AAAI2018] “Wasserstein Distance
Guided Representation Learning for Domain Adaptation”
57

More Related Content

A summary on “On choosing and bounding probability metrics”

  • 1. 確率分布間の距離をどう測るか? A summary on “On choosing and bounding probability metrics” June 20, 2018 松井孝太 理研 AIP データ駆動型生物医科学チーム
  • 2. Table of contents 1. Introduction 2. 10 metrics on probability measures 3. Some relationships among probability metrics 4. Why Wasserstein distance? 1
  • 4. Introduction I Alison et al. [2002], “On choosing and bounding probability metrics” の 3 章までのまとめ 問題意識 最近 Wasserstein distance を使った ML の方法論が (と りわけ domain adaptation の文脈で)  次々提案されて いるが, なぜ Wasserstein distance を使うのが良いのか を知りたかった 2
  • 5. Introduction II ? 確率分布間の metric として何を使えば良いのか問題. ? metric の選び方によって問題の解釈や理論的性質, 使 える bound テクも変わってくる. ? もし metric 間の関係が明らかであれば, 1 つの metric の理論を他の metric に拡張することができる. この論文 (Alison et al., 2002) では ? 10 種類の重要な metric を review し, その間の関係を サーベイする (このスライドの目的). ? 各 metric の応用や, metric を取り替えることによっ て (様々な) 収束レートが変動することの例示. 3
  • 6. 10 metrics on probability measures
  • 7. Preliminary Notation ? (?, B) : (Borel) 可測空間 ? P(?) : ? 上の確率測度の集合 ? ?, ν ∈ P(?) に対して, f, g をそれぞれ ?, ν の σ-有限 な λ に関する密度関数とする. (i.e. ?, ν ? λ) ? supp(?) = {ω ∈ ? | ?(ω) > 0} (? のサポート) ? ? = R のとき, F, G をそれぞれ ?, ν の累積分布関数と する. また, X, Y をそれぞれ ? 上の確率変数とすると き, これらから誘導される分布を L(X) = ?, L(Y) = ν と書くこともある. ? (?, d) が有界距離空間のとき, ? の直径を以下で定義 diam(?) = sup x,y∈? d(x, y). 4
  • 8. Preliminary ? Cb(?) : ? 上の有界連続関数の集合 De?nition 1 (弱収束, weak convergence) ?n, ? ∈ P(?), n = 1, 2, ... とする. ?f ∈ Cb(?) に対して, ∫ ? f(x)?n(dx) → ∫ ? f(x)?(dx) が成り立つとき, {?n} は ? に弱収束するといい, ?n ? ? と書く. Remark 1 確率変数 Xn, X の分布を ?n, ? とするとき, ?n ? ? であれ ば Xn は X に分布収束 (or 法則収束) するといい, Xn →d X と書く. 5
  • 9. Preliminary P(?) は弱収束の位相によって位相空間とみなせる. De?nition 2 (弱収束の距離付け可能性) P(?) 上のある距離 d が定める位相が弱収束の位相と一 致するとき (すなわち, d による収束と弱収束が同値であ るとき), P(?) は d で距離付け可能という. Remark 2 本論文では, 弱収束が距離付け可能かどうかは, 確率分布 間の距離の評価指標の 1 つとして重視される. 6
  • 10. 1. Discrepancy metric De?nition 3 (Discrepancy metric) ? を距離空間とする. dD(?, ν) := sup B∈B |?(B) ? ν(B)| ∈ [0, 1], ここで, B は ? 上の閉球全体の集合. ? base space ? の距離位相に基づいた距離 (閉球の体 積比較). ? スケール不変 (ベース空間の距離を正の定数倍しても dD は変わらず) ? Fourier bound を達成する (cf : 群上のランダムウォー クの収束証明) 7
  • 11. 2. Hellinger distance I De?nition 4 (Hellinger distance) ? を可測空間とする. f, g をそれぞれ ?, ν(? λ) の密度関 数とするとき, dH(?, ν) := [∫ ? (f1/2 ? g1/2 )2 dλ ]1/2 = [ 2 ( 1 ? ∫ ? (fg)1/2 dλ )]1/2 ∈ [0, √ 2] この定義は reference measure λ のとり方によらない. ? が可算集合のときは以下のように書ける: dH(?, ν) := [ ∑ ω∈? (?(ω)1/2 ? ν(ω)1/2 )2 ]1/2 . 8
  • 12. 2. Hellinger distance II ? ? = ?1 × ?2, ν = ν1 × ν2 なる直積測度を考えると, 1 ? 1 2 d2 H(?, ν) = ( 1 ? 1 2 d2 H(?1, ν1) ) ( 1 ? 1 2 d2 H(?2, ν2) ) が成立. すなわち, ベクトル v が v = (v1, v2) のように 独立な成分を並べた形をしている場合, 対応する分布 は, 成分毎の分布の積に分解できる. 左辺は Hellinger af?nity と呼ばれる. また, 上の事実の系として d2 H(?, ν) ≤ d2 H(?1, ν1) + d2 H(?2, ν2) が成立. 9
  • 13. 3. Relative Entropy (Kullback-Leibler divergence) I De?nition 5 (Relative entropy) ? を可測空間とする. f, g をそれぞれ ?, ν(? λ) の密度関 数とするとき, dI(?, ν) := ∫ supp(?) f log f g dλ ∈ [0, +∞], ここで, supp(?) ? ? は ? のサポートである. この定義は reference measure λ のとり方によらない. ? が可算集合 のときは以下のように書ける: dI(?, ν) = ∑ ω∈? ?(ω) log ?(ω) ν(ω) . 10
  • 14. 3. Relative Entropy (Kullback-Leibler divergence) II ? 慣習的に, 任意の q ∈ R に対して 0 × log 0 q = 0 また, 任意の p ?= 0 に対して p × log p 0 = +∞ とする (ために, dI ∈ [0, +∞] となる). ? 非対称かつ三角不等式を満たさないため, 距離ではな い. 一方で, 直積測度 ? = ?1 × ?2, ν = ν1 × ν2 に対して 加法性 dI(?, ν) = dI(?1, ν1) + dI(?2, ν2) を満たす. 11
  • 15. 4. Kolmogorov (Uniform) metric De?nition 6 (Kolmogorov metric) ? = R とする. Kolmogorov metric は, R 上の分布 ?, ν の 間の距離を, 対応する分布関数 F, G の間の距離として表 現する: dK(F, G) := sup x∈R |F(x) ? G(x)| ∈ [0, 1], ? 単調増加な 1 対 1 変換に関して不変である. 12
  • 16. 5. L?evy metric De?nition 7 (L?evy metric) ? = R とする. dL(F, G) := inf{ε > 0 : G(x ? ε) ? ε ≤ F(x) ≤ G(x + ε) + ε, ?x ∈ R} ∈ [0, 1], ? L?evy metric は, R 上の弱収束位相を距離付けする: Fn →d F as n → ∞ iff dL(Fn, F) → 0 as n → ∞. ? shift-invariant だが scale-invariant ではない. 13
  • 17. 6. Prokhorov ( or L?evy-Prokhorov) metric De?nition 8 (Prokhorov metric) ? を距離空間とする. dP(?, ν) := inf{ε > 0 : ?(B) ≤ ν(Bε) + ε, ?B ?Borel ?} ∈ [0, 1], ここで, Bε = {x : infy∈B d(x, y) ≤ ε}. ? dP は対称性を持つ. ? 14
  • 18. 7. Separation distance De?nition 9 (Separation distance) ? を可算空間とする. dS(?, ν) := max i ( 1 ? ?(i) ν(i) ) ∈ [0, 1]. ? dS は厳密な距離ではない. ? マルコフ連鎖の解析のために導入された. 15
  • 19. 8. Total variation I De?nition 10 (Total variation) ? を可測空間とする. dTV(?, ν) := sup A?? |?(A) ? ν(A)| = 1 2 max |h|≤1 ∫ hd? ? ∫ hdν ∈ [0, 1], ここで, h : ? → R. ? が可算空間のとき, dTV := 1 2 ∑ ω∈? |?(ω) ? ν(ω)| と定める. これは L1 ノルムの 1/2 倍であり, 文献によっ ては 2dTV を total variation と定義するものもある. 16
  • 20. 8. Total variation II Total variation はカップリング測度の inf として特徴付け ができる: dTV(?, ν) = inf{Pr(X ?= Y) | X, Y : r.v. s.t. L(X) = ?, L(Y) = ν} (1) 17
  • 21. 9. Wasserstein (or Kantorovich) distance I De?nition 11 (Wasserstein distance) ? を可分距離空間とする. ?, ν の 1-Wasserstein distance を dW(?, ν) = inf π∈Π(?,ν) ∫ ?×? d(x, y)dπ(x, y) で定義する. ここで, Π(?, ν) := {π : prob. measure on ? × ? | π(B × ?) = ?(B), π(? × B) = ν(B), ?B ? ?} を ? 上のカップリング測度の集合と呼ぶ. 18
  • 22. 9. Wasserstein (or Kantorovich) distance II ? Kantorovich-Rubinstein duality より, dW(?, ν) = sup ∥h∥L≤1 ∫ hd? ? ∫ hdν ∈ [0, diam(?)] が成立. ここで, sup は Lipschitz condition |h(x) ? h(y)| ≤ d(x, y) を満たす h について取る. この 右辺を Kantorovich metric と呼ぶ. ? 特に ? = R のとき, 右辺は以下のように書ける: ∫ ∞ ?∞ |F(x) ? G(x)|dx = ∫ 1 0 |F?1 (t) ? G?1 (t)|dt 19
  • 23. 10. χ2 -distance I De?nition 12 (χ2 distance) ? を可測空間とする. f, g をそれぞれ ?, ν(? λ) の密度関 数とするとき, dχ2 (?, ν) := ∫ supp(?)∪supp(ν) (f ? g)2 g dλ ∈ [0, ∞]. 特に ? が可算空間のとき以下のように書ける: dχ2 (?, ν) := ∑ ω∈supp(?)∪supp(ν) (?(ω) ? ν(ω))2 ν(ω) . 20
  • 24. 10. χ2 -distance II この metric は対称性を持たない (すなわち距離ではない). 一方で, 直積測度 ? = ?1 × ?2, ν = ν1 × ν2 に対して, Hellinger distance や relative entropy と同様に dχ2 (?, ν) ≤ dχ2 (?1, ν1) + dχ2 (?2, ν2) が成立. 21
  • 25. Remarks 任意の凸関数 f に対して, ? と ν の間の f-divergence を df(?, ν) := ∑ ω ν(ω)f ( ?(ω) ν(ω) ) で定義すると, 種々の metric を統一的に表現できる. 22
  • 26. Example I : χ2 -distance f(x) = (x ? 1)2 ととると, χ2 -distance が導出される: df(?, ν) = ∑ ω ν(ω) ( ?(ω) ν(ω) ? 1 )2 = ∑ ω ν(ω) ( ?(ω) ? ν(ω) ν(ω) )2 = dχ2 (?, ν) 23
  • 27. Example II : relative entropy f(x) = x log x ととると, relative entropy が導出される: df(?, ν) = ∑ ω ν(ω) ?(ω) ν(ω) log ?(ω) ν(ω) = ∑ ω ?(ω) log ?(ω) ν(ω) = dI(?, ν) 24
  • 28. Example III : total variation f(x) = |x?1| 2 ととると, total variation が導出される: df(?, ν) = ∑ ω ν(ω) |?(ω) ν(ω) ? 1| 2 = 1 2 ∑ ω |?(ω) ? ν(ω)| = dTV(?, ν) 25
  • 29. Example IV : Hellinger distance f(x) = ( √ x ? 1)2 ととると, Hellinger distance が導出され る: df(?, ν) = ∑ ω ν(ω) (√ ?(ω) ν(ω) ? 1 )2 = ∑ ω ν(ω) ( ?(ω) ν(ω) ? 2 √ ?(ω) ν(ω) ? 1 ) = ∑ ω ( ?(ω) ? 2 √ ?(ω)ν(ω) ? ν(ω) ) = ∑ ω (√ ?(ω) ? √ ν(ω) )2 = dH(?, ν)2 26
  • 31. S ? ? ? ? ? ?■ x TV ?x ?√ 2x H W on metric spaces ? ? ? ? ? ?? x/dmin ? ? ? ? ? ?■ diam? · x ? √ x ? (diam? + 1) x ? ? ? ? ? ??√ x/2 ν dom ? ? ? ? ? ? ?■ √ x?x/2 I ?log(1 + x) χ2 non-metric distances ?√ x ν dom ? ?x P ? ? ? ? ? ??x D ? 2x ?x K L on IR ?x ?x ?(1 + sup |G′|)x ?x + φ(x) 論文 Figure 1 の確率分布間の距離の関係の詳細を見る. 27
  • 32. Kolmogorov-L?evy on R Fact 1 確率測度 ?, ν ∈ P(R) の分布関数をそれぞれ F, G とする とき, dL(F, G) ≤ dK(F, G) (2) が成立 (Huber, 1981). さらに, もし G がルベーグ測度に 対して絶対連続であれば, dK(F, G) ≤ ( 1 + sup x |G′ (x)| ) dL(F, G) が成立 (Petrov, 1995). ここで, G′ は G の微分 (密度関数) を表す. 28
  • 33. Discrepancy-Kolmogorov on R Fact 2 確率測度 ?, ν ∈ P(R) の分布関数をそれぞれ F, G とする とき, dK(F, G) ≤ dD(?, ν) ≤ 2dK(F, G) (3) が成立. 29
  • 34. Prokhorov-L?evy on R Fact 3 確率測度 ?, ν ∈ P(R) の分布関数をそれぞれ F, G とする とき, dL(F, G) ≤ dP(?, ν) が成立 (Huber, 1981). 30
  • 35. Prokhorov-Discrepancy I Theorem 1 ? を任意の距離空間, ν を ν(Bε) ≤ ν(B) + ?(ε), ?B : ball on ? を満たす任意の確率測度とする. ここで, ? は右連続な関 数とする (任意の ball を ε だけ膨らませた ball の体積の 増え方は, ある右連続関数で記述される). このとき, dP(?, ν) = x を満たす任意の確率測度 ? に対して, dD(?, ν) ≤ x + ?(x) が成立. すなわち, dD(?, ν) ≤ dP(?, ν) + ?(dP(?, ν)) 31
  • 36. Prokhorov-Discrepancy II Example 1 ν として S1 または R 上の一様分布をとる (ν = U). この とき, ?(x) = 2x ととると, dD(?, U) ≤ 3dP(?, U) が成立. (proof) ν(Bx) ≤ ν(B) + ?(x) より, ?(B) ? ν(Bx) ≥ ?(B) ? ν(B) ? ?(x) が成立. dP(?, ν) = x ならば, ??x > x に対して, ?(B) ? ν(B?x) ≤ ?x が成立 (上式を満たす ?x の inf が dP). 32
  • 37. Prokhorov-Discrepancy III (proof つづき) 2 つの不等式を合わせると, ?(B) ? ν(B) ? ?(?x) ≤ ?x となり, B に関して sup をとると, sup B (?(B) ? ν(B)) ≤ ?x + ?(?x) (4) を得る. ここで, ν(B) ? ?(B) = 1 ? ν(Bc ) ? (1 ? ?(Bc )) = ?(Bc ) ? ν(Bc ) より (Bc は B の補集合), sup B (ν(B) ? ?(B)) = sup Bc (?(Bc ) ? ν(Bc )) ≤ ?x + ?(?x) (5) が成立. 33
  • 38. Prokhorov-Discrepancy IV (proof つづき) (4) と (5) 及び supB ≤ supB,Bc より, dD(?, ν) ≤ ?x + ?(?x) を得る. 右辺で ?x ↘ x とすれば, 所望の結果を得る (? は右 連続だから, ?(x) = lim ?x↘x ?(?x) は存在). 2 34
  • 39. Prokhorov-Wasserstein I Theorem 2 ? が完備可分な距離空間のとき, (dP)2 ≤ dW ≤ (diam(?) + 1)dP が成立. (proof) J を確率変数 X, Y の同時分布とするとき, EJ[d(X, Y)] ≤ ε × Pr(d(X, Y) ≤ ε) + diam(?) × Pr(d(X, Y) > ε) = ε × (1 ? Pr(d(X, Y) > ε)) + diam(?) × Pr(d(X, Y) > ε) = ε + (diam(?) ? ε) × Pr(d(X, Y) > ε) が成立 (ε を実現値として期待値を書き, 上からバウンド). 35
  • 40. Prokhorov-Wasserstein II dP(?, ν) ≤ ε であるとき, Prπ(d(X, Y) > ε) ≤ ε を満たす π ∈ Π(?, ν) がとれる (Huber, 1981). このとき, EJ[d(X, Y)] ≤ ε + (diam(?) ? ε ≤diam(?) )ε ≤ (diam(?) + 1)ε が成り立つから, π ∈ Π(?, ν) に関する inf をとれば, dW ≤ (diam(?) + 1)dP が成立 (主張の右側の不等号). 36
  • 41. Prokhorov-Wasserstein III 一方で, ε を dW(?, ν) = ε2 となるようにとると, Markov の 不等式 (Pr(|X| > a) ≤ 1 a E[|X|]) より Pr(d(X, Y) > ε) ≤ 1 ε EJ[d(X, Y)] ≤ 1 ε × ε2 = ε が成立. Lemma 1 (Strassen’s theorem) ?B ?Borel ? に対して, Pr(d(X, Y) > ε) ≤ ε ?? ?(B) ≤ ν(Bε) + ε. Lemma 1で ε の inf をとれば, 所望の結果を得る: dP ≤ ε ? (dP)2 ≤ ε2 = dW. 2 37
  • 42. Prokhorov-Wasserstein IV Remark 3 ? ? が非有界のとき, 定理のようなバウンドは不成立. Example 2 (Theorem 2 の反例 (Dudkey, 1989)) ? = R とし, Pn := (n ? 1)δ0 + δn n とおくと, dP(Pn, δ0) → 0 as n → ∞ だが, dW(Pn, δ0) = 1, ?n となる. ? Theorem 2の特別な場合として, (?, d) が完備可分距 離空間で d ≤ 1 のとき, 以下が成立  (Huber, 1981): (dP)2 ≤ dW ≤ 2dP. 38
  • 43. Wasserstein-Discrepancy I Theorem 3 ? が有限集合のとき, dmin × dD ≤ dW が成り立つ. ここで, dmin = minx?=y d(x, y) である. Remark 4 この定理の左辺は, ? が無限集合のとき, dmin をいくらで も小さくできる場合があり, 確率分布間の距離の比較と しては情報がほとんどないことがある (Theorem 4の節 も参照). 39
  • 44. Total variation-Discrepancy Discrepancy はすべての ball に関する sup であり, total variation はすべての可測集合に関する sup であるから, 明らかに dD ≤ dTV が成り立つ (後者の方が sup をとる範囲が広い). Remark 5 離散分布 · 連続分布どちらの状況でも, dTV=1 = 1 かつ dD をいくらでも小さくできる場合があるため, 逆向き (dTV ≤ dD) は言えない. 40
  • 45. Total variation-Prokhorov ? が距離空間のとき, ?, ν ∈ P(?) に対して, dP ≤ dTV が成立 (Huber, 1981). 41
  • 46. Wasserstein-Total variation I Theorem 4 次の bound が成り立つ: dW ≤ diam(?) × dTV. ? が有限集合のとき, Theorem 3 と同様の bound が成立: dmin × dTV ≤ dW. Remark 6 ? が無限集合のとき, Theorem 3と同様に dmin をいくら でも小さくでき得るので, less information な可能性が ある. 42
  • 47. Wasserstein-Total variation II (proof) 最初の不等式は, general な不等式 d(X, Y) ≤ 1X?=Y × diam(?) に対して, 両辺で coupling measure に関する inf をとると 得られる (TV distance における (1) による). 逆向きの不等 式は, d(X, Y) ≥ 1X?=Y × min a?=b d(a, b) の両辺で coupling measure に関して inf をとれば OK. 43
  • 48. Hellinger-Total variation Fact 4 (LeCam, 1969) d2 H 2 ≤ dTV ≤ dH 44
  • 49. Separation distance-Total variation Fact 5 (Aldous & Diaconis, 1987) dTV ≤ dS 逆は一般に成り立たない. (∵) ?, ν をそれぞれ {1, ..., n}, {1, ..., n ? 1} 上の一様分布と すると, dTV(?, ν) = 1 n ≤ dS(?, ν) = 1 2 45
  • 50. Relative entropy-Total variation Fact 6 (Kullback, 1967) ? が可算空間のとき, 2d2 TV ≤ dI 46
  • 51. Relative entropy-Hellinger Fact 7 (Reiss, 1989) d2 H ≤ dI 47
  • 52. χ2 -Hellinger Fact 8 (Reiss, 1989) dH ≤ √ 2d 1/4 χ2 . さらに, ? が ν に対して絶対連続であれば, dH ≤ d 1/2 χ2 が成立. 48
  • 53. χ2 -Total variation Fact 9 可算空間 ? において, Cauchy-Schwarz の不等式から, dTV(?, ν) = 1 2 ∑ ω∈? |?(ω) ? ν(ω)| √ ν(ω) √ ν(ω) ≤ 1 2 √ dχ2 (?, ν) が成立. Remark 7 ? が連続な空間の場合でも, ? が ν に対して絶対連続で あれば同様の結果が成立 (Reiss, 1989). 49
  • 54. χ2 -Relative entropy I Theorem 5 dI(?, ν) ≤ log(1 + dχ2 (?, ν)) が成り立つ. 特に, dI ≤ dχ2 (proof) log の concavity より, Jensen の不等式を用いると dI(?, ν) = ∫ ? f log f g dλ ≤ Jensen log (∫ ? f g fdλ ) = log ( 1 + dχ2 (?, ν) ) ≤ dχ2 (?, ν) が成立. 50
  • 55. χ2 -Relative entropy II (proof つづき) ここで, 2 番目の等号は以下による: dχ2 (?, ν) = ∫ ? (f ? g)2 g dλ = ∫ ? ( f g f ? 2f + g ) = ∫ ? f g fdλ ? 2 ∫ ? fdλ =1 + ∫ ? gdλ =1 = ∫ ? f g fdλ ? 1. また, 最後の不等号は, log(x + 1) ≤ x から従う. 2 Remark 8 Diaconis & Saloff-Coste (1996) による bound: dI(?, ν) ≤ dTV(?, ν) + 1 2 dχ2 (?, ν) 51
  • 56. Weak Convergence I ? Figure 1 のダイアグラムは, 個々の metric 間の関係 (bound) を導出するだけでなく, 確率測度空間に誘導 される位相の関係も示している. ? 例えば, Hellinger metric と Total variation の間の相 互の矢印 H ? TV は, これら 2 つの metric が誘導す る位相が同値であることを示す. ? また, Prokhorov や L?evy は弱位相を距離付けするが, 他のどの metric がどのような base space 上で同様 に弱位相を距離付けするかを次の定理にまとめる. 52
  • 57. Weak Convergence II Theorem 6 ? P(R) に対して, L?evy は弱収束を距離付けする. また, discrepancy や Kolmogorov は L?evy の upper bound を与える ((2), (3) 式参照) ので, L?evy を通して弱収束 を誘導する. さらに, discrepancy と Kolmogorov は ? が R 上のルベーグ測度に対して絶対連続のとき, 弱収 束 ?n → ? を距離付けする. ? ? が可測空間のとき, Prokhorov は弱収束を距離付け する. また, Wasserstein による収束は弱収束を誘導す る. さらに, ? が有界であれば, Wasserstein は弱収束 を距離付けする (Prokhorov の upper bound より). 53
  • 58. Weak Convergence III Theorem 7 (つづき) ? 次の metric による収束は弱収束を誘導する: ? Hellinger ? separation ? relative entropy ? χ2 ? ? が有限かつ有界のとき, total variation と Hellinger は弱収束を距離付けする. 54
  • 60. Way Wasserstein distance? I Wasserstein は弱収束を距離付けする distance measure 他の distance measure との関係 (tightness) ? Wasserstein ≤ (diam(?) + 1)× Prokhorov ? Wasserstein ≤ diam(?)× Total variation ? Wasserstein ≤ √ 2 × diam(?) × KL div. Key Inequality (Csisz?ar-Kullback-Pinsker) For p, q ∈ P(?), W1(p, q) ≤ diam(?)∥p ? q∥TV ≤ √ 2diam(?)KL(p||q) 55
  • 61. Way Wasserstein distance? II Domain adaptation の文脈では... Wasserstein distance を用いるメリット 1. 2 つの分布のサポートに overlap がない場合でも, meaningful な距離を与えてくれる (KL などの f-divergence は, 分布の比が発散するのでダメ). 2. 分布間の距離だけでなく, “どう近づければ良いか?” という方法も輸送写像として同時に与えてくれる. 3. データの位相的性質を保存する (輸送写像の連続性?) 4. 汎化誤差の bound が他の metric よりも tight. ref Courty, N. et al. [2017] “Optimal transport for domain adaptation.” 56
  • 62. Way Wasserstein distance? III Domain adaptation を adversarial training (Wasserstein GAN) として実現できる : inf fg W1(PhS , Pht ) = inf fg sup ∥fw∥L≤1 EPxs [fw(fg(x))] ? EPxt [fw(fg(x))] ? Pxs , Pxt は source, target のデータ分布 ? fw は discriminator (Wasserstein dist. の推定を行う) ? fg は generator (source と target の特徴抽出を行う) ref Shen, J. et al. [AAAI2018] “Wasserstein Distance Guided Representation Learning for Domain Adaptation” 57