VCAの出力はなぜ直感的に期待される多項式にならないのか
昨年NIPSベストペーパーで話題になったVCAの論文読みメモです。
デンソーアイティラボラトリの塚原氏が試していた件を初めとして、幾人か実装してブログを書かれているが、なぜ単純な円にガウスノイズを乗せた程度のグラフで円の方程式がパッと出てこないのか、その理由が知りたいです。
結論からいうと、論文読んでも良くわからなかったのですが、参考リンク
アブスト
R^N上の集合に対してVanishingイデアルが定義できて、それは有限のイデアル生成系でコンパクトに表現できる。それを効率良く構成する方法を示す。我々のアプローチは数値的に安定、つまり誤差を許容する。教師あり学習に適用でき、実験ではカーネル法と同等の精度を出す分類器を作れた。
1.イントロ
与えられたデータセットをゼロ点とする関数の集合は、機械学習の文脈ではコンパクトな特徴表現の可能性を意味する。ここではそういう関数を多項式に限定する。データをゼロ点とする多項式はイデアルになり有限の要素から生成できるというヒルベルトの定理がある。今の機械学習はそういうことが出来ない。カーネルPCAではそれが出来ない事を論文中でしめしている。我々と最も近い手法は approximately vanishing ideal (AVI) algorithmという手法だがそれは元々の特徴量をどう並べ替えるかというインプットが必要な上に出力される多項式の項数も少ない。
われわれのVCAは与えられたデータと多項式の次数の上限を与えると、あとは特に追加情報を与えなくてもデータを零点とするイデアルを自動的に出力する魅力的な手法だ。
2.定式化
多項式環の定義どおり。
3. 単純だが現実的でないアプローチ
指数オーダでよければ解ける。多項式カーネルを使って作ってゼロ空間を求めてやると、自明なイデアルしか残らないことが証明できる。なのでイデアルに相当するものをカーネルを通してブラックボックス的に使えないの？という素朴な疑問は否定的に結論づけられる。
4.VCAのアルゴリズム
生成系を構成する多項式がn個だとして、データ点をn個の多項式の線形結合（係数体はR）にバイアス項を加えたもの（＊）を考え、これを1ステップずつ更新していくという方針。
そうすると、求めたい（＊）の係数（R^(n+1)空間の部分空間）は、上で作った線形結合の式にデータ点を代入したm*(n+1)行列の零空間ということになる。
アルゴリズムの進行はF,Vという2つの多項式セットを更新していくことで行う。最初はFは1/sqrt(m)という1個だけ, Vは空集合。
（なんとなく、大学受験のに例えると、Fが予備校で、Vが大学。毎年新たに誕生する高校3年生と浪人生であわせて受験生Cを構成する。浪人生は受験生と同じだけ勉強のバリエーションが広がっている。）
（そしてまず、予備校Fの空間に対して直交するように受験生Cを調整する。そうやって調整したCを、今度はC同士が直交するように正規直交基底を求める。もはや受験生というより受験生の正規直交基底を考えている。その基底ごとにデータへの成分を評価してvanishingすれば大学Vへ、しなければ予備校Fへ。っていうのを繰り返して予備校行きの学生がゼロになった時点で終了。）
5.分析
計算量
出力結果の品質保証
6.関連研究
イデアルの生成系の研究は歴史があり、グレブナー基底の計算アルゴリズムが一つのブレークスルーとなったという経緯をもつ。グレブナー基底をvanishingイデアルのために構成する方法が後に示され、本論文はそれを使っている。しかし誤差を許容しないので今まで殆ど応用されていない。
誤差を許容するvanishingイデアルの研究はあまりなされていない。最も近いのは上述したAVIだがグレブナー基底とは異なるタイプの近似的な生成系を出力する。AVIは特徴量の辞書付き順序を必要とする上に、単項式しか扱わないので殆ど項を含まない出力になる。さらに同じデータをvanishする次数の異なる単項式を複数含めてしまうという欠点もある。VCAはそのあたりの問題がない。
7.〜実験など
理論が知りたかったので以降は省略。
（ブログ主の）考察・疑問
Vの各要素は直交するのか？
- 毎ステップでVに追加するメンバーが、その時点までに既にVにいるメンバーと直交するのだろうか？
- 合格したCの基底をVにいれるときに、前回合格してVに入った基底と独立でないベクトルを構成してしまわないのか？
データから離れ度合いが気になる点
- vanishingのエラー許容度εを計算するときに、多項式の次数の高低に関係なく同じεを使ってるけど
- 次数nが高いとき、もとのデータ点でみるとεのn乗根のスケールに相当してしまわないのか？
多項式の関数空間の都合で決まった基底ごとに対応するデータへの評価（特異値の成分）で判断しているけど、それってどういう意味なのか？
