全ての場合の事象を観測することができず，部分的にしか情報が得られない場合は世の中に多数存在します．例えば，映画の評判に関するアンケートを例に取ると，各人が見た映画は異なっており，全てのユーザーに対して全ての映画の評価を得ることはできません． このような全ての情報を得ることができない場合に，手持ちの情報からどれだけの情報を原理的に復元できるかという問題は応用上も重要となります．
今回の講演における問題設定は，与えられたマスク（観測できる要素が特定される情報）の下で，観測できていない要素をどれだけ理論的に復元できるかというものでした．マスクは観測できる要素を１，観測できる要素を０とする行列表現以外にも，この行列の行と列に対応する頂点集合のうち，見えている要素に対応する枝を与えた２部グラフ表現も考えられます． この２部グラフの組み合わせ的な性質が解析において重要ということでした．
上記の問題は「部分的な観測から低ランク行列を復元できるか」という問題と数学的に表現でき，この必要条件と十分条件が今回の研究により求められました．必要条件は，行列のサイズを m * n，行列のランクを r とすると
(1) 観測された要素の数が r(m+n-r) 個以上であること，
(2) 各行，各列において r 個以上の観測があること，
(3) マスクの２部グラフから任意の r-1 本の枝を取り除いても連結であること，
でした．また，ランク r 以下の行列では任意の (r+1) * (r+1) 小行列式が零になるという性質を用いると，(r+1) * (r+1)の部分マスクで枝が一本のみ欠けている場合にその欠けている要素を復元でき，この復元された要素に対応する枝をマスクに加えます．今回の研究では上記の操作を繰り返してマスクが完全グラフになる場合を r-closable と呼んでおり，これが一意穴埋め可能の十分条件ということでした．
更に，今回の研究では matroid (マトロイド)という概念を用いて，部分的な復元という視点を導入しています．従来の穴埋めに関する研究では行列の穴埋めが成功するか失敗するかという観点にのみ着目されており，この点で先行研究から大きな進展が存在します．Matroid は何らかの意味で独立な部分集合の全体と定義されており，例えば，行列の列ベクトル集合のうち線形独立な列ベクトルの全体は vector matroid (ベクトルマトロイド)と呼ばれています．今回の講演では， determinantal matroid という行列の要素全体の集合のうちランク r で独立に選べる要素の集合を用いた理論が展開されました．この determinantal matroid の独立性に関する解析から，観測できない要素のうち復元できる要素とできない要素は，観測要素に従属か独立かという点で説明できることが今回の研究によりわかりました．この独立性 or 従属性はある非線形写像のヤコビアンから得ることができます．今回の結果には様々な応用例を考えることができ，最初の映画の例だと，追加の調査を行う際に新たに評価すべき映画を指定できるということが考えられます．
観測できる要素の箇所という情報だけから原理的に復元可能な要素とそうでない要素の区別を理論的に与えた今回の研究結果からは数理研究の持つ可能性の奥深さを強く感じました．
数理６研 森野佳生
0 件のコメント:
コメントを投稿