2013年7月29日月曜日

第27回助教の会

こんにちは、第27回数理助教の会ブログ担当の松島です。
先日の数理助教の会では、中務佑治さんに発表していただきました。


中務さんは今年の6月から数理第七研究室で助教に就任されている方で、主に数値線形代数を研究されています。今回は、最新の研究の成果である「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)といわれています。このような後方安定性の議論は数値線形代数の分野においては多く見られる重要な議論のようですが、少し分野が違う自分にとっては目新しいもので、とても興味深かったです。

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





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




数理六研 松島

[参考文献]
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

2013年7月12日金曜日

第26回助教の会

第26回助教の会では数理情報学第6研究室の松島慎さんに発表していただきました.松島さんは昨年度博士号を取得し,現在ポスドクとして数理6研に所属しています.今回の助教の会での発表のタイトルは” Scaling up Machine Learning algorithms for classification”でして, ざっくり言うと,分類問題に対する機械学習アルゴリズムを高速化したことについて話していただけました.これは博士論文にまとめられた成果(の一部)ということです.

機械学習と言っても数理的にはある種の最適化問題を解くことで,本研究では二値分類問題に対しサポートベクターマシンで最適化問題を定式化します.要するにやりたいのは与えられたサンプル点に対し下図(1つ目)のような直線を引くことで,その直線は下図(2つ目)にある最適化問題を解くことで得られます.


この分野では,この最適化問題を近似でよいので速く解くことが求められるのですが,そのための有力なアプローチが,双対問題に対し座標降下法(Coordinate descent method)を用いるというものです.ただし,原型となるアルゴリズムでは,データが巨大化するにつれ,同時にアクセスすべきデータも増えるため,高速化のためにはデータを分割してキャッシュメモリに移し,データを局所的に参照して計算できるようにすることが不可欠になります.今回の松島さんの発表では,その目的に適うように既存のアルゴリズムを改良して実装し,実際に高速化できていることを示してくれました.

研究の核心である実装部分の話についてもう少し詳しく述べると,巨大データを扱う際には2010年にBlock Minimization という技術が提案されており,これによりハードディスク上の巨大データを小分けにしてメモリに読み込ませることで,メモリ上で高速に処理できるようになったのですが,この技術ではメモリ上で処理している間ハードディスクからの読み込みが停止するため,その時間が無駄になっていました.これに対し松島さんの方法では,できるだけ読み込みと計算処理の両方が常に動き続けるように改良されています.視覚的に分かりやすく説明しようとすると,下図のReaderとTrainerが両方同時に動くようにしたということです.


この説明については,下のYoutubeの動画が非常によくできていますので是非ご覧ください(最下部に添付の発表スライドにも埋め込まれています).

     

話は単純ですが,これを効率的に行うには,もとの座標降下法の長所である(1)反復で更新する変数は一つでよい,(2)一次収束性,(3)反復中で不必要なサンプル点を除去できる,といった性質を損なわないようにする必要があります.松島さんはそのメリットを維持した上でスケーラブルな実装を与え,実際に既存手法より数倍高速な実験例を示し,それだけでなく,既存手法では収束していなかったものでも本手法で現実的な時間で収束する例も紹介してくれました.また,松島さんの枠組みは,サポートベクターマシンに限らず広く応用できるので,最近は他の問題にも焦点を当てて研究を行っているそうです.

今回の話は数学的に難しい話は少なく,サポートベクターマシンや座標降下法などは学部生にも理解できる話なのでもっと周知する機会があってもいいような気もしました.発表を思い出すと、松島さんのやわらかい物腰のおかげか,いつも以上に質問やコメントが多かったように思います.近年,自分の研究する数値計算の分野でも,キャッシュメモリをうまく活用するアルゴリズム設計が重要視されているので興味深く感じました.そして研究の歴史に着目してみると,双対問題に座標降下法を用いることが提唱されたのが2008年で,Block Minimization が2010年です.日進月歩でこの手の研究が精力的に行われていることが伺えますね.この分野の中での松島さん自身の今後のご活躍を楽しみに思いました.

数理3研助教 相島健助