行列補完
- 提唱者
- Emmanuel Candès & Benjamin Recht
- 年
- 2009
- 種類
- Convex low-rank recovery
- 系統
- Missing data
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
行列補完(Matrix Completion)は、行列のエントリのごく一部(小さく、おそらくランダムなサブセット)から低ランク行列を復元する技術である。2009年にEmmanuel CandèsとBenjamin Rechtによって導入されたこの手法は、問題を核ノルム最小化(rank minimizationに対する凸緩和)として定式化し、エントリが一様にランダムに観測され、かつ行列が非干渉条件(incoherence condition)を満たす場合に厳密な復元が可能であるという理論的保証を提供する。
手法の背後にある直感
ユーザーと映画の評価を含む部分的に記入されたスプレッドシートを想像してほしい。ほとんどのセルは空白である。もし基盤となるデータが単純な構造を持っているならば――例えば、好みがジャンルの好みや時代といった少数の潜在的因子だけで説明されるとすれば――たとえ少数の評価しか知らなくても、残りを自信を持って埋めるのに十分である。行列補完は、この隠れた低次元構造を利用する。これは、絵が数種類の形状しか持たないことを知っている状態でジグソーパズルを完成させるのに似ている。
歴史学
行列補完は圧縮センシングの文献から出現した。CandèsとRecht(2009)は核ノルム最小化による最初の厳密復元定理を確立し、それに続いてCandèsとTaoによる非干渉の力の研究が行われた。この手法は、低ランク協調フィルタリング手法が推薦精度で最先端を達成したNetflix Prizeコンペティションを通じて広く一般の注目を集めた。Recht、Fazel、Parriloによる後続の研究は、機械学習におけるトレースノルム正則化との核ノルム最小化の関連性を結びつけた。
使うべき場面
データが系統的に欠損したエントリを持つ行列として整理でき、かつ真の信号が低ランクであると信じる理由がある場合に、行列補完を使用する――例えば、推薦システム、ゲノミクス、ソーシャルネットワーク分析、画像復元などである。主要な仮定は、エントリがランダムに欠損しており、行列が非干渉条件を満たすことである。構造化された、またはランダムでない欠損、非常に高いランク構造を持つ行列、または低ランク仮定が正当化されない場合には適さない。代替案としては、一般的な欠損データに対するMICE補完や、非負性が要求される場合のNMFが挙げられる。
限界と注意点
- 半正定値計画法の計算コストは、行列次元に対して悪くスケールする
- 非干渉条件の仮定は、構造化された欠損や外れ値を持つ実際のデータセットでは失敗する可能性がある
- 真のランクが行列次元に比べてそれほど小さくない場合、性能が低下する
- 核ノルム最小化はノイズに敏感である。ロバストなバリアントは追加の複雑さを加える
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 多項式時間凸計画法の下で、穏やかな条件下での証明可能な厳密な復元
- 行列が真に低ランクである場合、非常に高い欠損率を処理できる
- ランクに関する事前知識は不要。核ノルム最小化が暗黙的にそれを発見する
- ランダム行列理論と凸解析に根差した強力な理論的保証
応用
- 協調フィルタリングと推薦システム(ユーザーとアイテムの評価予測)
- ゲノミクスとバイオインフォマティクス(欠損測定値を持つ遺伝子発現行列の復元)
- コンピュータビジョン(画像インペインティングとビデオ背景差分)
- センサーネットワークローカライゼーション(部分距離測定値からの位置行列の復元)
- 神経科学(部分fMRI観測からの機能的接続行列の補完)
使い方
使い方
アルゴリズムは、エントリがインデックス集合Ω上のエントリのみが観測されている行列Mから始まる。これらの観測された値が、復元問題の制約を形成する。スパース性パターンは一様にランダムにサンプリングされたと仮定され、これは厳密な復元保証が確立される理論的設定である。
数式
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}行列のランクを直接最小化することはNP困難であるため、CandèsとRechtは、半正定値計画法(semidefinite programming)を通じて問題を扱いやすく保ちながら、低ランク解を促進する核ノルム(特異値の合計)を最小化することを提案している。核ノルムは、圧縮センシングにおけるベクトルに対するL1ノルムが果たす役割と同じ役割を行列に対して果たす。
数式
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\Omega復元が可能であるためには、真の行列の特異ベクトルが標準基底に対してあまりにも整列していないことが必要であり、これは非干渉パラメータμによって定量化される。エネルギーを少数の行または列に集中させる行列は非干渉的である。高度に局在化された行列は、この条件に違反し、ランダムサンプルから復元することはできない。なぜなら、観測されていないエントリに情報が過剰にエンコードされているからである。
数式
\max_{i} \|U^\top e_i\|^2 \leq \frac{\mu r}{n_1},\quad \max_{j} \|V^\top e_j\|^2 \leq \frac{\mu r}{n_2}観測されたエントリの数が、μに比例し、ランクr、n log nを掛けた閾値を超えると、核ノルム最小化問題の最小化子は、高い確率で真の行列を厳密に復元する。この結果は、必要なサンプルサイズがランクr行列の固有自由度よりも対数多項式(polylogarithmically)しか大きくないことを示しており、このアプローチが情報理論的にほぼ最適であることを意味する。
数式
\text{If } |\Omega| \geq C \cdot \mu r n \log n,\; \text{then } \hat{X} = M \text{ with high probability}よくある落とし穴
- 実際の観測がユーザー選択または偏っている(例:高く評価されたアイテムのみが評価される)場合に、一様なランダム欠損を仮定すること。これは理論的なサンプリングモデルに違反する
- 構造化された欠損や外れ値を持つ実際のデータセットでは、非干渉条件の仮定が失敗する可能性がある
- ノイズのある設定で、核ノルム最小化をスケーリングまたは正則化なしで使用すること。この場合、厳密復元定式化は不適切である
- 行列補完を行列分解のヒューリスティックと混同すること。交互最小二乗法(ALS)は局所的最小値に収束する可能性があり、核ノルム最小化の復元保証を欠く
よくある質問
核ノルム最小化だけが行列補完を解く唯一の方法か?
いいえ。交互最小二乗法(ALS)や、因数分解形式(例:M ≈ UV^TとなるようなUとVに対するSGD)での勾配降下法は、スケーラビリティのために実際には広く使用されている。しかし、これらの非凸アプローチは、核ノルム最小化の厳密復元保証を欠き、注意深い初期化なしでは局所的最小値に収束する可能性がある。
厳密な復元にはどのくらいのデータが必要か?
CandèsとRechtは、非干渉パラメータμを持つn×nランクr行列に対して、約C・μ・r・n・log(n)個のエントリが観測されれば十分であることを示した。実際には、これは低ランク行列が、その固有自由度のわずかな倍数にすぎないサンプルからしばしば復元できることを意味する。n×n行列の固有自由度はr(2n−r)である。
非干渉条件とは何か、そしてなぜそれが重要なのか?
非干渉は、特異ベクトルが座標基底に沿ってどれだけ広がっているかを測定する。特異ベクトルが集中している行列――例えば、1つの行にのみ非ゼロであるランク1行列――は、その情報の大部分を少数のエントリに格納している。もしそれらのエントリが観測されなかった場合、他のエントリがどれだけ知られていても復元は不可能である。
関連する手法
参考文献
Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.
DOI 文献を開くコピーしました。