[勉強会まとめ] d-SNE: Domain Adaptation using Stochastic Neighborhood Embedding

# 読んだ論文

CVPR2019の論文 ([論文のリンク](http://openaccess.thecvf.com/content_CVPR_2019/papers/Xu_d-SNE_Domain_Adaptation_Using_Stochastic_Neighborhood_Embedding_CVPR_2019_paper.pdf))
Domain AdaptationでSOTAをとっていた．

# どんなもの？
- ドメイン適応におけるドメインシフト問題に対処したd-SNEを提案
- SNE(Stochastic Neighbor Embedding)を応用
- ドメインの転移を促す正則化項の構成におけるスケール問題に対処するために，修正を加えたハウスドルフ距離を利用

# Stochastic Neighbor Embedding (SNE)
d-SNEの説明の前にSNEについて簡単に説明する．まず前提として，SNEでは2点間の近さを条件付き確率で表現する．次元削減前の点$x_i$から点$x_j$の近さを条件付き確率$p_{j|i}$で次のようにおく．$\sigma^2_i$は平均$x_i$のガウス分布の分散で，$p_{i|i} = 0$とする．

$${\displaystyle p_{j|i} = \frac{exp(-||x_i - x_j||^2 / 2\sigma^2_i)}{\sum_{k \neq i} exp(-||x_i - x_k||^2 / 2\sigma^2_i)}}$$

次に，次元削減後の点$y_i$から点$y_j$の近さを同様に条件付き確率$q_{j|i}$で表す．$y_i$と$y_j$はそれぞれ$x_i$と$x_j$に対応する．SNEの元論文によると，一般性を失わないために分散を$\frac{1}{2}$に設定するらしい．

$${\displaystyle q_{j|i} = \frac{exp(-||y_i - y_j||^2)}{\sum_{k \neq i} exp(-||y_i - y_k||^2)},\ q_{i|i} = 0}$$

さて，ここで次元削減を行った後のことを考えてみる．次元削減の後，元データの構造を完全に再現できていれば，$p_{j|i} = q_{j|i}$となるはずである．そこで，$p_{j|i}$と$q_{j|i}$の”差”が小さくなるように次元削減を目指せばよさそうである．これこそがSNEの基本思想．二つの確率の差はKL-divergenceを用いて表現することで定式化できる．以上から，SNEでは次の目的関数の最小化を行う．$P_i$は点$x_i$と次元削減前のすべてのデータ点から得られる条件付き確率で，$Q_i$は点$y_i$と次元削減後のすべてのデータ点から得られる条件付き確率である．
$${\displaystyle C = \sum_i KL(P_i||Q_i) = \sum_i\sum_j p_{j|i} log\frac{p_{j|i}}{q_{j|i}}}$$

SNEは目的関数$C$の最小解を勾配法によって求めることで次元削減を行う．

cf. t-SNEは2点間の近さを条件付き確率で表す際に，ガウス分布ではなく，自由度1のt分布を用いる．

# 技術や手法
## d-SNE

d-SNEでは上で説明したSNEの考え方を応用してドメイン適応に対する目的関数を構成する．

まず，潜在空間におけるソースドメインのデータ$x^s_i$とターゲットドメインのデータ$x^t_j$の距離$d$とターゲットサンプル$x^t_{j}$がソースサンプル$x^s_{i}$と同じラベルを持っている確率$p_{j|i}
$をそれぞれ定義する．距離$d$はドメイン間の距離を表しているわけではないことに注意．
$$d(x^s_{i}, x^t_{j}) = ||\Phi_{D_{s}}(x^s_{i}) - \Phi_{D_{t}}(x^t_{j})||^2_{2}$$

$$p_{ij}=\frac{exp(-d(x^s_{i}, x^t_{j}))}{\sum_{x \in D_{s} exp(-d(x, x^t_{j}))}}$$

教師あり学習の場合，$x^s_{i}$と$x^t_{j}$にはラベルがありそれぞれ$y^s_{i}$と$y^t_{j}$とする．$y^s_{i}=y^t_{j}$のとき，$p_{ij}$を最大化し，そうでないときは$p_{ij}$を最小化する．これにより，$x \in D_{s}$と$x^t_{j}$の距離が遠いほど$p_{ij}$は小さくなる．次に，ソースドメインのクラス$k$のサンプルに関して総和を取った$p_j$を計算する．これはターゲットドメイン$x^t_{j}$がソースドメイン$x$と同じクラス$k$である確率を表す．ただし，$D^s_{k}=\\{\forall x^s_{l} | y^s_{l}=k\\}$，$N^s_{k}=|D^s_{k}|$．
$$p_{j}=\frac{\sum_{x \in D^s_{k}} exp(-d(x, x^t_{j}))}{\sum_{x \in D_{s}} exp(-d(x, x^t_{j}))}=\sum_{i=0}^{N^s_{k}}p_{ij}$$

さて，ドメイン適応の目的はソースドメインの知識をターゲットドメインに転移させることなので，ソースドメインのすべてのデータ点に対して，$p_j$を最大化すれば，ソースとターゲットで共通知識を獲得し，ソースドメインの知識をターゲットドメインに転移させることができそうである．よって次式を最小化すればよい．
$$\sum_{x^t_{j} \in D^t} \frac{1}{p_{j}} = \sum_{x^t_{j} \in D^t} (\frac{\sum_{x \in D^s_{k}} exp(-d(x, x^t_{j}))}{\sum_{x \in D_{s}} exp(-d(x, x^t_{j}))},\ for\ k = y_{j})$$

実際にはこれに対数をとったもの(対数尤度)を最小化する．
$$\mathcal{L} = log(\sum_{x^t_{j} \in D^t} (\frac{\sum_{x \in D^s_{k}} exp(-d(x, x^t_{j}))}{\sum_{x \in D_{s}} exp(-d(x, x^t_{j}))},\ for\ k = y_{j}))$$

以上がd-SNEの基本的な考え方であるが，論文内ではこの対数尤度に関してスケールの問題を挙げている．この対数尤度の式には指数の和があるため，組み立てた式にはスケールの問題が存在しており，このままだと確率的最適化手法に悪影響を及ぼしてしまうらしい(ここがよくわからない．誰か教えて下さい)．そこで論文では，ハウスドルフ距離を少し修正した距離を用いることでこの問題を緩和している．先ほどの対数尤度を直接最適化するのではなく，同じクラスのサンプル間の最大距離のみを最小化し，異なるクラスのサンプル間の最小距離を最大化する．よって損失関数は次のようになる．
$$\tilde{\mathcal{L}} = sup_{x \in D^s_{k}}\\{a|a \in d(x, x_{j})\\} - inf_{x \in D^s_{not k}}\\{b|b \in d(x, x_{j})\\}\ for\ k = y_{j}$$

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/531317/98965044-8d81-8bd4-fdaa-4f37cbb72ba1.png)

## End-to-End Learning
d-SNEはEnd-to-Endの学習を行うことができる．$\Phi_{D^x}$は特徴抽出器(CNN)で，ソースドメインとターゲットドメインの入力次元が同じ場合は特徴抽出器を共有できる．いずれのドメインもラベルが与えられているので交差エントロピーを使って損失を定義し，先ほどの$\tilde{\mathcal{L}}$はネットワークの正則項として使用できる．したがって，ネットワーク全体の目的関数は次のようになる．ただし，$w_{s}, w_{t}$はそれぞれ$\Phi^s, \Phi^t$の重みパラメータ．
$$Objective Function = argmin_{w_{s}, w_{t}}\ \tilde{\mathcal{L}} + \mathcal{L^s_{cross entropy}} + \mathcal{L^t_{cross entropy}}$$

## Semi-Supervised Learning

d-SNEはMean-Teacherという手法を用いて半教師あり学習への拡張ができる．Mean-Teacherを用いた半教師あり学習への拡張について簡単に説明する．

ターゲットドメインとラベルなしデータの埋め込み(特徴表現)のL2誤差を取ることで損失$L_c$を構成する．$L_c$を最小化することで，教師なしネットワーク$\hat{\Phi}_{D_t}$を訓練する．訓練は次の手順で行う．

1. ソースとターゲットに関してネットワークを訓練
2. ターゲットドメインとラベルなしデータ$D_{tu}$を使用して$\hat{\Phi}_{D_t}$を訓練

$\hat \Phi_{D_T}$の重みは訓練済みのターゲットネットワーク$\hat \Phi_{D_T}$の重みで初期化され，学習に使用する入力はaugmentationを行う．またターゲットネットワーク$\Phi_{D_t}$は$\hat \Phi_{D_t}$のネットワークの重みの指数移動平均で更新される．

# 感想

SNEの知見をドメイン適用に応用した研究で，比較的読みやすい論文でした．比較的簡単なネットワークなので時間があれば実装してみたいなと思います．
(K.K)