指数移動平均
指数移動平均(Exponential Moving Average; EMA)を得るためのテクニックの話。
以前、確か、Temporal Ensembling [1]の論文を読んだときに、なるほどー、と思ったときのメモ書きが出てきたので、文字に起こしておく。
[1] Laine S, Aila T. Temporal Ensembling for Semi-Supervised Learning. 2017.
何某かの変数 $z _ n (n \ge 1)$ を反復更新しながら、その指数移動平均：
x _ n = \frac
{z_n + α z _ {n - 1} + α^2 z _ {n - 2} + ... + α^{n-1} z _ {1}}
{1 + α + α^2 + ... + α^{n-1}}
を得たいとする。 ここで、αは定数（$0 < α < 1$）。
もちろん$z _ i (1 \le i \le n)$を全て記録しておけば良いのだが、nが大きいとか、zが巨大ベクトルとかであれば、効率が悪い。
そこで、 zの更新と同時に、次のように$X$を更新することを考える。
$X _ n = z _ {n} + α X _ {n - 1} \quad (n \ge 1),$
$X _ 0 = 0 \quad (n =0)$
ここで、右辺の$X$に、式自身を繰り返し代入すると、
- $X _ n = z _ {n} + α z _ {n - 1} + α ^ 2 X _ {n - 2}$
- $X _ n = z _ {n} + α z _ {n - 1} + α ^ 2 z _ {n - 2} + α ^ 3 X _ {n - 3}$
... - $X _ n = (z _ {n} + αz _ {n - 1} + α ^ 2 z _ {n - 2} + ... α ^ {i} z _ {n - i} + ... +α ^ {n - 1} z _ {1} ) + α ^ {n} X _ {0}$
$X _ 0 = 0$であるから、
X _ n = \sum _ {i = 0} ^ {n - 1} α ^ {i} z _ {n - i}
これで、めでたく、最初の$x _ n$式の分子が得られる。 分母は、等比数列の和
$A _ n = \sum _ {i = 0} ^ {n-1} α ^ {i} = (1 - α ^ n)/(1 - α)$
であるから、次のように$x _ n$を得る。
x _ n = \frac{1 - α}{1 - α ^ n} X _ n
分散と不偏分散と標準偏差と標準誤差と
それぞれどちらを使うべきか、時々混乱するので、整理する。
分散と不偏分散の定義
以下、手元に$n$個のサンプル $x _ i$ があって、その平均が $ m $ であるとする。
- (通常の)分散： $ σ ^ 2 _ P = \frac {1}{n} \sum _ i {(x _ i - m)} $
- 不偏分散： $ σ ^ 2 _ S = \frac {1}{n - 1} \sum _ i {(x _ i - m)} $
Excelだと、前者が「VAR.P」、後者が「VAR.S」という関数に対応するので、 添え字はそれに倣っている。
分散と不偏分散の使い分け
- 分散 $σ ^ 2 _ P$は、手元のサンプル n 個が、計算対象の全て（母集団そのもの）であるとき
- 不偏分散 $σ ^ 2 _ S$は、ある母集団から任意個抽出してきた n 個が計算対象であるとき
に使う。
（不偏分散の方は、厳密には、手元の $n$ 個から、母集団$N (> n)$個の分散を 予想したい場合に使う、と書いた方が正確か。）
ちなみに、なぜ $n$ より小さい値（$ n - 1$） で割るのか、その理由については、 次のリンク先の「数式を使わない感覚的な説明」の図が 非常に直感的で好き。
不偏標本分散の意味とn-1で割ることの証明 | 高校数学の美しい物語
標準偏差と標準誤差の定義
- 標準偏差： $ SD = σ $
- 標準誤差： $ SE = \frac{σ}{\sqrt n}$ （厳密には、標本平均の標準誤差）
標準偏差と標準誤差の使い分け
に使う。
標準偏差の方は、「データそのもの」のばらつき具合であるから、 nを増やせば増やすほど、母集団のばらつき具合の値（つまり、標準誤差）に近づく。
標準誤差の方は「データの(推定)平均値」のばらつき具合、
言い換えれば「母集団のN個からランダムにn個取って、平均値を推定」してみる試行を
何回も行ったときの、推定値のばらつき具合である。
したがって、nを増やせば増やすほど確度が高まり、0に近づいていく。
なお、定義については次のサイトを参照した。
t-SNEやUMAPで、裾の広い分布を使う理由（混雑問題）
UMAPの記事で、距離ではなく「近さ」という言葉を使った。
単純に「距離」を当てはめるのでは上手くいかない理由の1つが、混雑問題（Crowding Problem）である。
混雑問題とは、「高次元で"同じ距離"を表せる範囲が、低次元では極端に狭くなる」（という解釈で良いのだと思う）。
この事実の根拠として、同時に等間隔に配置できる点の数での説明がよくなされる。
- 3次元では4個まで（正四面体の配置）
- 2次元では3個まで（正三角形の配置）
つまり、高次元の距離を保ったまま、低次元に移すことは、本質的に無理な例が生じる、ということである。
t-SNEでは、Crowding Probremの対策として、高次元と低次元で異なる分布関数を使っている（恐らく、UMAPでも同じ恩恵に預かっている）。
- 参考
- Visualizing data using tSNE 論文紹介スライド https://www.slideshare.net/mobile/t_koshikawa/visualizing-data-using-tsne-56773191
UMAPの仕組み ── 低次元化の理屈を理解してみる
1. はじめに
- 非線形の高次元データを低次元化して可視化する道具として、t-SNEに代わってUMAPが主流になってきている。
- McInnes L, Healy J, Melville J. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. 2018.
- UMAPの仕組みを論文から理解するには数学脳不足で挫折していたが、先人達の解説記事のお蔭でやっと直感的な理解できた気がするので、ここにまとめたい。
- t-SNEと比べた説明もしているので、t-SNEを把握しているとより理解が早いかも。
- あくまで直感的、厳密な説明でないことをご容赦いただきたい。
（2021.3.26追記：コメントで指摘を頂いた、表の間違いを修正。）
（2021.7.3追記：近さ曲線の図を修正。）
2. 次元削減の方針
UMAPでやろうとしている大きな方針は、
- 高次元で｢近い｣点同士を、低次元上でも｢近く｣に配置したい
である。手順を大雑把に書くと、次のように表せる。
- Step 1. 高次元における、全ての2点の組合せに対しての「近さ$v _ {ij}$」を、数値化する。
- Step 2. 低次元における、全ての2点の組合せに対しての「近さ$w _ {ij}$」を、数値化する。
近さの組$(w _ {ij})$と$(v _ {ij})$とが整合するように、点配置（マッピング先）を繰り返し更新する。
ここで｢近さ｣は、点付近の密度に応じた値としている。つまり、点が密集する周辺では距離を厳しく、点が疎なところでは距離を緩く評価する。 （非線形データに対応するため。）
実は、ここまで書いた方針は、従来のt-SNEとほとんど同じである。考え方としては、近さの定義と、2つの「全ペアの近さ」の比べ方、その2点が違うだけ、と解釈できる。
- UMAPでは、近さを「近傍に属する強さ」、近さの組をファジー集合と見なして、ファジー集合の塊同士を交差エントロピーで比べる（この辺の言葉が難しい...）。
- t-SNEでは、近さを確率と見なして、総和が1となる近さの組をKL情報量で比べる。
ちなみに、「近さ」に距離そのものを使わない理由としては、
- 非線形に対応するため
- Crowding Problemに対応するため（後日の記事で追記済み）
が挙げられる。
3. 高次元における近さの定義
高次元側の具体的な「近さ」を、次の流れで定義する。
- 高次元のある点$\bm x _ i$に対して、他の点$\bm x _ j$の近さ$v _ {j|i}$を考える。非対称($v _ {j|i} \neq v _ {i|j}$)であることに注意。
- $v _ {j|i}$と$v _ {i|j}$から、対称化した近さ$v _ {ij}$を得る。
（ちなみに、参照先に倣って、縦棒|表記を、非対称であることを示すために使っている。）
3.1. 準備
点$\bm x _ i$に対して、$k$近傍の集合（すなわち、$k$番目に距離の小さい点までを集めた集合）を、$K _ i$と表すことにする。 （ただし、正の整数 $k$はパラメータとして与える。）
このとき、他のある点$\bm x _ j$が集合$K _ i$に属すか否かは、$\{0,1\}$の2値で表現可能である。
UMAPでは、この2値を、0以上1以下の実数に拡張した、ファジー集合(fuzzy set)として扱う。つまり、要素が集合に属すか否かを、実数で曖昧に表そう、ということである。
- なお、厳密には、「fuzzy simplicial set」らしい。この辺の理論はちゃんと理解していない。
これらをイメージするなら、次の図の(a)と(b)のような近傍グラフとなる（ちなみに、後ほど、(c)のように対称化することになる）。
3.2. 定義
さて、「点$\bm x _ i$の近傍」という集合に、他の点$\bm x _ j (j\neq i)$が属する強さ(近さ)を$v _ {j|i}$で表し、UMAPでは次のように定義する。
v_{j|i} = \exp\left(\frac{-(r_{ij} - ρ_i)}{σ_i}\right) \quad (\bm x_j \in K_i) \quad ...(1)
ここで、
- $r _ {ij}$: 点$\bm x _ i$と$\bm x _ j$の(通常の意味での)距離。一般にはユークリッド距離。
- $ρ _ i$ : 最近傍との距離。$ρ _ i = \min _ {j\in K _ i}\{r _ {ij}\}$
- $σ _ i$ : 点の疎密に対応するための割り算。後述。
なお、k近傍に含まれていなければ、
v _ {j|i} = 0 \qquad (x _ j \notin K _ i)
と考える。
式(1)において、$σ _ i$は、点が密集しているところでは小さく(狭く)、疎なところでは大きく(広く)設定したい変数である。
この$σ _ i$は、$\sum _ j v _ {j|i} = \log _ 2 k$となるように、二部探索で決められる。
($\log _ 2 k$は経験的に定められたものらしい。)
また、$ρ _ i$が特徴的で、これによって、$\bm x _ i$の最近傍な点との近さは、必ず 1 となる。
3.3. 対称化
近さが非対称だと計算が煩雑になるので、対称化して定義し直す。
(集合における和集合を、fuzzyに考えて得られたものと思われる。)
v _ {ij} = (v _ {j|i} + v _ {i|j}) - v _ {j|i}v _ {i|j}
- 数式をよく眺めてみると、少なくとも一方から見て最近傍であれば、対称化しようが必ず$v _ {ij} = 1$である。なかなかの最近傍重視。
4. 低次元における近さの定義
低次元の点$\bm y _ i$に対しても、同様の当てはめを試みる。ただし、
- 高次元の$σ$に当たる値は、一定値(=1)としたい（疎密の度合を均一化）。
- 高次元の$ρ$に当たる値は、最近傍を表す近さであるため、これも一定の値を与えたい。
ということを考慮に入れると、次のような式が出来上がる。
w _ {j|i} = \exp\left({-\max\{0,d _ {ij} - ρ'\}}\right)
= \tilde w _ {ij}
この時点で、既に$i$と$j$に関する対称性を満たしていることに注意。
$ρ'$は、パラメータmin_distに対応する。
実装上は、これを更に、t-分布ライクな分布関数で近似している。
w _ {ij} = \frac{1}{1 + a \cdot d _ {ij}^{2\cdot b} }
$a, b$には、 $w_{ij}$を$\tilde w _ {ij}$にフィッティングして得られた固定値を使う。
- t-分布ライクになっているのは、t-SNEの恩恵を預かることを意識していそう。
- なお、デフォルトのmin_distの設定値の場合、$a\simeq 1.929, b\simeq 0.7915$程になるらしい。
5.最適化
高次元での近さの組$(v _ {ij})$と、低次元での近さの組$(w _ {ij})$が、数値化できるようになった。
あとは、対応する近さが一致するように、低次元の点を配置していけば良い。
UMAPのコスト関数は、2つのfuzzy setに対する交差エントロピーで定義する。すなわち、
L = \sum_{i,j}\left[v_{ij}\log\frac{v_{ij}}{w_{ij}} +
(1-v_{ij})\log\frac{1-v_{ij}}{1-w_{ij}}\right]
確率的勾配法(SGD)で$\bm y _ i$を更新するために、$L$を微分すると、 第1項と第2項が、それぞれ引力と斥力になって現れる。
\frac{∂L^+}{∂\bm{y}_i} =
\frac{∂L^+}{∂d^2}\frac{∂d^2}{∂\bm{y}_i} =
\underbrace{
\frac{-2abd_{ij}^{2(b-1)}}{1+ad_{ij}^{2b}}
}_{f^+}
v_{ij} (\bm{y}_i - \bm{y}_j) = v_{ij} f^+ (\bm y_i - \bm y_j)
\frac{∂L^-}{∂\bm{y}_i} =
\frac{∂L^-}{∂d^2}\frac{∂d^2}{∂\bm{y}_i} =
\underbrace{
\frac{2b}{(ε+ad_{ij})(1+ad_{ij})}
}_{f^-}
(1 - v_{ij}) (\bm{y}_i - \bm{y}_j)
となる。
ここで更に、実装を簡単にするために、サンプリングを導入する。
SGDの更新の時に、全ての近傍点に対して重み付けして毎回更新するのと、重みに基づく割合でサンプリングした点だけを定数倍で更新するのとで、(反復を増やせば) 同じ意味になることを利用する。
結局、UMAPは、次の繰り返しで$(\bm y _ i)$の配置を更新することで、次元削減を実現している手法、ということになる。
- k近傍の点を$v _ {ij}$に重み付けされた割合でサンプリングして、$f ^ +$に基づいて$\bm y _ i$と$\bm y _ j$を引っ張る。
- 全ての点に対して、一様サンプリングでランダムに点を拾ってきて、$f ^ -$に基づいて$\bm y _ i$と$\bm y _ j$を引き離す。
(本来は$1 - v _ {ij}$で重み付けすべきはずだが、ほどんどの点で$1 - v _ {ij} = 1$になることから、強引に1と見なしているようである。)
6. t-SNEとの相違
次の表のようにまとめられる。
影響が大きい点は、次の2点。
a. 正規化不要 → 計算コスト削減
- t-SNEでは、近さを確率と見なすために正規化を要するため、1組の近さを計算するのに、常に$N-1$ のペアに対する計算操作が必要となる。
- UMAPでは、$k (\ll N)$ のペアに対する計算だけで済む。
特に、低次元側は、反復の度に近さを数値化し直す必要があるため、正規化不要なUMAPに計算量の大きなアドバンテージがある。 （特に$N$が大きい場合。厳密には、t-SNEでも重複計算を削るとか、多少工夫できるとはいえ、なお差は大きいと思う。）
b. Laplacian Eigenmapによる初期化 → 結果の安定化
- UMAPでは、Laplacian Eigenmap（$k$近傍グラフを行列で表して主成分分析しているようなもの？）を使って、$\bm y _ i$の初期配置を、決定的に決めている。
- t-SNEの非決定的なランダム配置で初期化するよりも、結果が安定しやすいようである。
参考
解説記事様々。大変に参考になりました。
- [1] UMAP 論文を読む https://qiita.com/cympfh/items/e8c2669c646a73205ea9
- [2] t-SNEより強いUMAPを（工学的に）理解したい https://qiita.com/odanny/items/06ab88353bcee7bf6aa7
- [3] UMAP for TSNE. https://jlmelville.github.io/uwot/umap-for-tsne.html
- [4] How Exactly UMAP Works. https://towardsdatascience.com/how-exactly-umap-works-13e3040e1668
- [5] t-SNEを理解して可視化力を高める https://qiita.com/g-k/items/120f1cf85ff2ceae4aba
数式を表示してみるテスト
katexで数式を表示してみるテスト。
7shiさんの参考記事、ありがたや。 https://7shi.hateblo.jp/entry/2018/07/28/231859
スカラー: $f _ n (\alpha)$、ベクトル: $\mathbf{b _ f}$.
\left|\int_α^β (x-α)(x-β) dx\right| = \frac{1}{6}|β-α|^3
