第２７回助教の会

こんにちは、第２７回数理助教の会ブログ担当の松島です。

先日の数理助教の会では、中務佑治さんに発表していただきました。

中務さんは今年の６月から数理第七研究室で助教に就任されている方で、主に数値線形代数を研究されています。今回は、最新の研究の成果である「Spectral divide-and-conquer algorithms for matrix eigenvalue problems and the SVD」について発表していただきました。

今回の発表で取り扱っている問題は対称正方行列における固有値分解(Symmetric eigenvalue decomposition)、そして一般の行列における特異値分解(SVD/Singular Value Decomposition) の問題です。

固有値分解では対称正方行列$A$が与えられた場合に、

$$ A = V^{\top} \Lambda V $$

となる直交行列$V$と対角行列$\Lambda$を求めます。

一方、特異値分解では$m$行$n$列の行列$A$が与えられた場合に、

$$ A = U^{\top} \Sigma V $$

となる$m$行$m$列の直交行列$U$、（各成分が負でない）$m$行$n$列の対角行列$\Sigma$、そして$n$行$n$列の直交行列$V$を求めるという問題です。

自分自身機械学習の研究をしていて、機械学習分野における固有値分解や特異値分解を用いたアルゴリズムというのもとてもなじみがありますが、固有値分解・特異値分解は一般に数理的なアプローチを行う非常に広範にわたる分野で使われている基本的な問題だと思います。なので固有値分解・特異値分解の新しいアルゴリズムというのは、それらがより具体的な問題解決のための基盤技術であるという意味でも非常に重要です。

特に最近では、多くの応用で、大きなサイズの行列を固有値分解・特異値分解するという場面が増えています。現代の計算機にはメモリの階層構造があり、高速にアクセス可能なメモリほど容量が小さくなっていくのですが、一度に高階のメモリに乗り切らないほど大きなサイズの行列を扱う場合、高階のメモリに行列の要素を移すコミュニケーションコストの方が、数値演算のコストよりも高くなってしまう事になります。そのため、大きい行列を扱う場合は、コミュニケーションコストを最小化しつつ、数値演算のコストも低く押さえることが望まれます。中務さんが発表されたのはそのような要望に応える新しいアルゴリズムの提案です。

今まで大きなサイズの行列に対して、コミュニケーションコストを最小におさえられる操作としては、行列積、コレスキー分解、QR分解が知られています。中務さんのアイディアは、これらの操作をうまく利用してやる事でコミュニケーションコストを最小に押さえられる固有値分解・特異値分解のアルゴリズムを与えようという事です。アルゴリズムの流れを固有値分解の場合で説明しますと、まず$A$の正の固有値と負の固有値がだいたい同じくらいになるように$A-\sigma I $とした後にQR分解を用いた極分解で$A-\sigma I =UH $における$U$を求めます(1.)。次に$(I+U)/2$の列空間とその直交補空間の正規直交基底に対応する行列$V_+$、$V_-$を求めます(2.)。これらを用いて$A$をブロック対角化することができるので(3.)、以上の操作をブロックに再帰的に施す事によって対角化を得る(4.)、という流れになっています。行列$A$の極分解とは

$$A=UH$$

となる直交行列$U$と半正定値行列$H$を求める事で、特に$A$が対称正方行列の場合は、$A$の全ての固有値を、符号に応じて$1$と$-1$に変えてできる行列$\mathrm{sign} (A)$に対応します。

アルゴリズムの内容もさることながら、このような数学的に定義された分解を正確に求めるためのアルゴリズムに関してはその評価も非常に重要になってきます。今、計算機上で表現されている行列$A$に対して固有値分解のアルゴリズムが直交行列$\hat{V}$と対角行列$\hat{\Lambda}$を出力したとします。このとき、$A$と$\hat{V}{}^{\top}\hat{\Lambda}\hat{V}$は非常に値が近い行列ではありますが、完全に一致するということは一般には期待できません。そのため、対象としているアルゴリズムが出力する$\hat{V}$および$\hat{\Lambda}$はどのような意味で$A$の真の固有値分解に近いのか、という問いに答えなければなりません。中務さんは、提案されているアルゴリズムが入力$A$に対して出力した$\hat{V}$および$\hat{\Lambda}$に関して、

$$A-\hat{V}{}^{\top}\hat{\Lambda}\hat{V} = e \|A\|_2$$

がいつでも成り立つ事を数学的に証明しています。ここで$e$はオーダーが$2^{-53}$程度の行列で、この値は標準的な浮動小数点計算で生じる誤差の大きさです。これはつまり、アルゴリズムが出力した$V$および$\hat{\Lambda}$が真の分解となる行列$\hat{A}=\hat{V}{}^{\top}\hat{\Lambda}\hat{V}$と、与えられた行列$A$が近いという事を示しており、特に後方安定性（Backward Stability）といわれています。このような後方安定性の議論は数値線形代数の分野においては多く見られる重要な議論のようですが、少し分野が違う自分にとっては目新しいもので、とても興味深かったです。

他にも、極分解を効率よく求めるためのポイントや特異値分解の場合への適用法、さらに極分解を効率よく求める方法の話など、興味深い内容がありましたが、ここでは割愛させていただきます。詳しくはスライドのほうをご覧ください。

Spectral divide-and-conquer algorithms for eigenvalue problems and the SVD from yuji_nakatsukasa

個人的には、先ほどの後方安定性の話の他にも数値線形代数の分野では良く知られているが自分には目新しい話というのがいくつも出てきて、このような話を共有させていただきとても勉強になりました。一方で、メモリ容量の問題で大規模な計算を行う場合計算アルゴリズム自体を再考しなければいけない、という現象はまさに自分が機械学習の分野で取り扱っていることと同じことでした。大規模データを扱うことのむずかしさと面白さというのは、「ビッグデータ」という言葉とともに多くの実社会に関する面で強調されている昨今ですが、数理工学の基礎的分野においても広く議論の的になっているとても普遍的な問題なのだということを感じました。

数理六研　松島

[参考文献]

Yuji Nakatsukasa and Nicholas J. Higham, Stable and efficient spectral divide and conquer algorithms for the symmetric eigenvalue decomposition and the SVD, SIAM Journal on Scientific Computing, Vol. 35(3), pp. A1325-A1349, 2013. pdf file. Codes available at MATLAB Central File Exchange