研究内容

応用数学・学習理論

非負値行列分解の理論的推定精度について

背景と目的

非負値行列分解とは、非負値成分を持つ行列を2つの非負値成分を持つ行列の積に分解する手法です。画像や音声などの信号処理、バイオインフォマティクス、テキストマイニング、購買解析などで複合データ解析技術として広く使われています。様々な分野で数値実験的に知識発見手法として用いられており、例えば信号処理ではパワースペクトルの分解、購買解析では購買因子の分析とその因子における代表的な商品といった購買パターンの抽出に応用されています。これだけ広く応用されているにもかかわらず、その数学的な構造、とりわけ推定精度はあまり明らかにされていませんでした。推定精度の理論値が判明していれば、数値実験が成功しているかどうかの基準が得られます。逆に、もし理論値がなければ数値計算により得られた結果の正しさは一切保証されません。

一般のベイズ推定において、事後確率が正規分布で近似できてもできなくても、汎化誤差(の平均値)という形で推定精度の理論値を解明する(代数幾何学の特異点解消定理による)方法が確立されています。また、事後確率が正規分布で近似できないような場合、最尤推定や事後確率最大化推定よりもベイズ推定の方が汎化誤差を小さくできることも知られています。これら2点から、私たちはベイズ推定のフレームワークで非負値行列分解の汎化誤差の理論値について研究しています。

主結果と考察

平均誤差函数の零点集合に対し代数幾何学における特異点解消を行うことで汎化誤差の平均値の理論値を得ます。これは学習理論のゼータ関数の最大極を計算することと同様です。ゼータ関数の最大極の絶対値は実対数閾値と呼ばれる代数幾何学における双有理不変量です。極の位数も実対数閾値の多重度と呼ばれる双有理不変量です。そしてこの実対数閾値こそが、汎化誤差の平均値の学習データ数に対する漸近挙動を司ります。

上述した方法を用いて、汎化誤差の平均値の理論上界を導出しました。詳細は"Upper Bound of Bayesian Generalization Error in Non-Negative Matrix Factorization"をご覧下さい。研究業績もご覧下さい。実対数閾値は負の対数周辺尤度(自由エネルギー)の漸近挙動もまた司っています。従って実対数閾値の解明は推定精度向上のためのモデル選択だけでなく真のモデルを選ぶ確率を最大化するモデル選択にも応用することができます。詳細な考察は上述の論文をご覧下さい。

数値実験

上では理論について述べてきました.実対数閾値が満たす理論式は不等式の形をしているので,厳密値はどのようなものかを数値的に見積もってみます.

ベイズ推定においては事後分布の実現が必要不可欠です.事後分布に従うパラメータをサンプリングしてようやく事後分布についての平均操作が行えます.現実の問題では理論上の積分という無限和を計算することはできないので,数値的な有限和でこれらを近似しますが,それでも事後分布を数値的に実現する必要があります.事後分布が解析的に計算できかつその分布が簡単であれば苦労はありません.しかしそのような場合は特に機械学習では稀でしょう.上でも述べたように機械学習で用いられるモデルは事後分布が正規分布に近似することすらできないのですから.

こんなないない尽くしの状況ですが,非常に強力な数値計算手法があります.それがマルコフ連鎖モンテカルロ法(MCMC)です.MCMCはモンテカルロ積分を改良したもので,高速かつ実用上十分正確にサンプリングができます.MCMCの実装にはいくつかの手法が知られており,ギブスサンプラー,メトロポリス=ヘイスティング,ハミルトニアンモンテカルロ,レプリカ交換法などが挙げられます.個人的な感覚ですがこの4つは後者ほど難しい問題を解ける代わりに実装コストも高いように感じます.

鶏を割くに焉んぞ牛刀を用いん.非負値行列分解は最初から平均誤差函数を多項式と思ってもよいくらいには簡単そうに見えます.最初の数値実験ということもあり,まずはメトロポリス=ヘイスティング法を考えてみます.非負値制約により,truncatedな分布が必要となるのでギブスサンプラーは難しいように思えます(ナイーヴにtruncateを実装すると,いつまでも収束しませんでした).メトロポリス=ヘイスティング法ではあるパラメータを決定することが困難という課題があります.移動力という,提案分布の「分散」のようなものです.大きいほど素早くパラメータ空間を探索できますが収束しづらくなり,小さいと収束しやすいものの局所解にハマりやすいという問題があります.確率降下法に見られるトレードオフと似ているように感じます.数値実験を繰り返して良い移動力を見つけ,そうして数値計算を行いました.

数値実験結果

理論式で等号が成立している場合について,真の行列が零であるときとそうでないときがあります.真の行列が零でなくかつ理論式で等号が成立する場合,数値実験は確かにうまくいっていました.これは理論式を疑っての数値実験ではなく,むしろ理論通りの結果が出たので数値実験が正しいことを意味します.このような判定が可能なことが理論値を求めるメリットの一つでしょう.真の行列が零行列の場合は後述します.不等号となっている場合はどうでしょうか.

理論式で等号が成立するとは限らない場合は,非負値制約の強さを思い知る結果となりました.非負値制約が真に意味を成す場合は,通常の行列分解(縮小ランク回帰)の実対数閾値の理論値よりも大きくなったのです.非負値制約があまり意味をなしていない,正確には非負値分解の内部次元と通常のランクが等しい場合,縮小ランク回帰の実対数閾値の理論値に近い結果が得られました.

この数値実験は全てが狭い意味でポジティブな結末を迎えられたわけではありません.後回しにした真の行列が零の場合を述べます.このときはメトロポリス=ヘイスティング法の良い移動力を見つけることができず,事後分布を実現することができませんでした.職人芸の努力が足りないというご批判はご尤もでございますが,小さいサイズの行列ですら採択率が0に近いか1に近いかという極端なことばかりが発生しました.これは行列の成分に0が多くごく一部だけを正の成分とした場合でも見られ,いわゆるスパース行列に対しては事後分布を実現することが困難であると実験的にわかりました.

実験結果の考察や,より詳細な実験結果につきましては,上記を基にニューロコンピューティング研究会で発表させていただきました際の論文「非負値行列分解における実対数閾値の実験的考察」(2017.3)をご参照ください.