(cache) Spark MLlibでcos類似度の総当たり計算が高速に実行できるDIMSUMがすごい(2)理論編

reference

Zadeh, Reza Bosagh, and Gunnar Carlsson. “Dimension independent matrix square using mapreduce.” arXiv preprint arXiv:1304.1467 (2013).

DIMSUMとは

行列$A$の列ベクトルの全てのペアのcos類似度を近似的に高速に求めるアルゴリズム。Twitterでの実証実験では実時間で40%計算が速くなったと報告されている。

アルゴリズム

列ベクトルのノルム$\left | c_{j} \right |$が大きい要素をサンプルしないことで計算量を下げている。直観的には、ノルムが大きい列では要素は一つあたりの要素$a_{ij}a_{ik}$が内積に占める割合が小さくなるため、サンプルぜずにすっ飛ばしても影響が少なくなると考えることができる。

$\bf{ DIMSUMMapper}$
for all pairs ($a_{ij},a_{ik}$) in $r_{i}$ do
  with probability ${\rm min}\left ( 1,\gamma \frac{1}{\left \| c_{j} \right \|\left \| c_{k} \right \|} \right )$ emit $((c_{j},c_{k})\rightarrow a_{ij}a_{ik})$
end

$\bf{ DIMSUMReducer}$
if $\frac{\gamma}{\left \| c_{j} \right \|\left \| c_{k} \right \|}>1$ then
  output $b_{ij} \rightarrow \frac{1}{\left \| c_{j} \right \|\left \| c_{k} \right \|}\sum^{R}_{i=1}v_{i}$
else
  output $b_{ij} \rightarrow \frac{1}{\gamma}\sum^{R}_{i=1}v_{i}$
end if

まとめると

	サンプル率$\gamma$	シャッフルサイズ	reduce-complexity
特異値を保存	$\Omega(n/\epsilon^{2})$	$n^2/\epsilon^2$	$n/\epsilon^2$
類似度を保存	$2\log(n)/s$	$n \log(n)/s$	$\log(n)/s$
共通	–	$O(nL\gamma)$	$O(\gamma)$

$A$: $m \times n$行列($m»n$)
$s$: cos類似度の最小値
$L$: 一行の中で非ゼロ要素の最大数

特異値を保存する場合

$A^{\rm T}A$を近似計算する目的

行列Aは($m \times n$)の大きさで、$m$が$n$に比べて非常に大きいとします。$A$を直接固有値分解(SVD)するとき、そのまま行うと$A=U\Sigma V^{\rm T}$となりますが、比較的小さい$n \times n$行列の$A^{\rm T}A$を固有値分解しても、$A^{\rm T}A=V\Sigma^{2} V^{\rm T}$となり、$\Sigma$と$V$は求めることができます。このようにして$A^{\rm T}A$を利用すると固有値分解を小さい計算量で実現することができます。しかしながら、$A^{\rm T}A$の計算量は大きいので、固有値の精度が落ちない範囲で近似計算できると嬉しいという話です。

$A^{\rm T}A$を近似計算する条件

特異値が保存される条件は以下の定理１で与えられます。

定理 1 $\gamma=\Omega(n/\epsilon^{2})$でDは対角要素が$d_{ii}=\left | c_{i} \right |$の行列、$B$はDIMSUMアルゴリズムの出力であるとき、

$\frac{\left \| DBD - A^{\rm T}A\right \|_{2}}{\left \| A^{\rm T}A\right \|_{2}} \leq \epsilon$

が少なくとも$\frac{1}{2}$の確率で成り立つ。

ここで$\left | X\right |_{2}$はスペクトルノルムで、$X$の最大特異値と同じです。$DBD$とすることで$A^{\rm T}A$とスケールを合わせています。定理1が証明できればDIMSUMアルゴリズムで求めた$B$の特異値が保存されていることになります。

証明

定理1を証明するのに、Latalaの定理を用いる。

Latalaの定理

$E\left \| X\right \| \leq C \left [ {\rm max}_{i} \left ( \sum_{j} E[x_{ij}^2]\right)^{\frac{1}{2}} + {\rm max}_{j} \left ( \sum_{i} E[x_{ij}^2]\right)^{\frac{1}{2}} + \left ( \sum_{ij} E[x_{ij}^4]\right)^{\frac{1}{4}} \right]$

この定理の証明はここではしない。

ある一行に注目したとき、$a_{ki}a_{kj}$の値を採用するかしないかの$k$回目のサンプルの結果を$X_{kij}$に入れる。

$X_{kij}=\left\{\begin{matrix} a_{ki}a_{kj} &~{\rm with~prob}~ p_{ij}\\ 0 & ~{\rm with~prob}~ 1- p_{ij} \end{matrix}\right.$

このとき、$B$の要素$b_{ij}=\frac{1}{\gamma}\sum_{k=1}^{m}X_{ijk}$と表すことができる。$A_{ij} \in [0,1]$なので、

$E[B] = D^{-1}A^{\rm T}AD^{-1}, E[DBD] = A^{\rm T}A$ が成り立つ。

まずは$E\left | B - D^{-1}A^{\rm T}AD^{-1}\right |$の上界についてLatalaの定理を使って考える。つまり、$E[(b_{ij}-Eb_{ij})^2]$,$E[(b_{ij}-Eb_{ij})^4]$の上界を考えればいい。

$E[(b_{ij}-Eb_{ij})^2] = Var[b_{ij}] \leq \frac{1}{\gamma}$ $E[(b_{ij}-Eb_{ij})^4] \leq \frac{2}{\gamma^2}$

よって

$E\left \| B - D^{-1}A^{\rm T}AD^{-1}\right \| \leq C_{0} [(\frac{n}{\gamma})^{\frac{1}{2}}) + (\frac{n}{\gamma})^{\frac{1}{2}}) + (\frac{2n^2}{\gamma^2})^{\frac{1}{4}})] \ \leq C_{1} (\frac{n}{\gamma}^{\frac{1}{2}})$

ここで、$\gamma = 4C_{1}^2 \frac{n}{\epsilon^2}$とすると

$E\left \| B - D^{-1}A^{\rm T}AD^{-1}\right \| \leq \epsilon$ $\begin{align*} \frac{\left \| DBD - A^{\rm T}A\right \|_{2}}{\left \| A^{\rm T}A\right \|_{2}} &= \frac{\left \| D \right \|^2 \left \| B - D^{-1}A^{\rm T}AD^{-1}\right \|_{2}}{\left \| A^{\rm T}A\right \|_{2}}\\ &\leq \frac{c_{*}^2 \left \| B - D^{-1}A^{\rm T}AD^{-1}\right \|_{2}}{\left \| A^{\rm T}A\right \|_{2}}\\ & \leq \frac{c_{*}^{2}\epsilon}{\left \| A^{\rm T}A\right \|_{2}}\\ & \leq \frac{c_{*}^{2} \epsilon}{c_{*}^{2}}\\ & = \epsilon \end{align*}$

ここで、$c_{*}^2$は列ベクトルの最大値です。

特異値の保存が必要ないとき

$A^{\rm T}A$が近似計算できる条件

DIMSUMアルゴリズムで$A^{\rm T}A$を近似できる条件は以下の定理2で与えられます。

定理2

$A$を($m \times n$)の行列で$A_{ij} \in [0,1]$とする。任意の列ベクトルの$c_{i},c_{j}$に対して${\rm cos}(c_{i},c_{j})\geq \epsilon$とする。$B$はDIMSUMの出力で、$B$の要素$b_{ij}=\frac{1}{\gamma}\sum_{k=1}^{m}X_{ijk}$と表すことができる。このとき、以下の不等式が成り立つ。

$\newcommand{\c}[1]{\left \| c_{#1} \right \|} \newcommand{\pr}{\rm{Pr}} \newcommand{\ata}{A^{\rm T}A} \begin{align} \pr[\c{i}\c{j}b_{ij} > (1+\delta)[\ata]_{ij}] \leq \left ( \frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\alpha\\ \pr[\c{i}\c{j}b_{ij} < (1-\delta)[\ata]_{ij}] < \exp(-\alpha \delta^2 /2) \end{align}$

$\c{i}\c{j}b_{ij}$によって$[\ata]_{ij}$を予測している。