Vanishing Component Analysisがダメそうという話
要約: Vanishing Component Analysisは問題設定のレベルで壊れていると思うので誰かなんとかしてあげてほしい(4/12追記あり)
http://d.hatena.ne.jp/m-a-o/20140323#p2
で、一時期話題になったVanishing Component Analysis([1], 以下VCA)への疑義が呈されていたので原論文を読んだ。感想はほぼ同じだったので上のエントリを読んでもらえればいいのだけど、ここでは自分なりに問題点をまとめなおしておく。
まずは背景から。多項式環とそのイデアルについては省略。今、$\mathbb{R}^n$上に$m $個の点が与えられたとすると、それら全ての点で0になる多項式の集合はイデアルをなすことがすぐに分かる(零化イデアル)。以下、点集合を$S_m $、対応する零化イデアルを$I(S_m)$と書くことにする。$i$番目の点の$j$番目の座標の値は$x^{(i)}_j$と書き、多項式$f$を$S_m $の各点で評価した値を縦に並べて得られるベクトルを$f(S_m)\ (\in \mathbb{R}^m)$と表記する。さて任意の多項式環のイデアルは有限サイズの基底を持つので、点集合が多項式で表せるような何らか(単位円上に乗ってるとか)の構造を持っていれば、$I(S_m)$の基底$<f_1, \dots, f_k>$($k$はそこそこ小さい値)が得られてそれは点集合の簡潔な表現になっていることが期待される(基底の取り方は一意でないことに注意)。例えば、$n=2, S_m=\{(-1,0), (0,1), (1,0)\}$のとき$I(S_m)=<x_2+x_1^2-1, x_1x_2, x_2^2-x_2>$となって単位円を表す多項式$x_1^2+x_2^2-1$を含んでいることが分かる。
これを機械学習の文脈に持ち込むために誤差を許すバージョンを考えようというのが今回の動機なのだが、まず誤差なしの世界ではどうすればよいか見ておく。Möller and Buchberger[2]など効率のよいアルゴリズムは種々提案されているのだが最も素朴には、1点集合$\{(x^{(i)}_1, x^{(i)}_2, \dots, x^{(i)}_n)\}$の零化イデアル$I(\{x^{(i)}\})$は$<x_1 - x^{(i)}_1, x_2 - x^{(i)}_2, \dots, x_n - x^{(i)}_n)>$となるのでこれらの積集合$\cap_{i=1}^m I({x^{(i)}})$を取るというのがある(イデアルの積はグレブナー基底を介して計算可能)。この記事を書くためにやっつけで覚えたRisa/Asirで書くと次のようになる、
https://gist.github.com/LennMars/9854807
というわけで誤差なしの世界では頑張れば計算できることは分かったのだが、誤差を許すことを考えたときの適切な定式化はすぐには分からない。今考えているのは代数方程式を(近似的に)解く問題の逆問題と言っていいと思うのだが、このような問題では自明な解を含む無数の全く見た目が異なる解が考えられてしまうのが普通なのでその中からどれを「よい」解と見なすかが常に問題になる(たいていは、式の元々の出どころの知識から外部的な拘束条件を見つけてきてくっつけることになる)。今回の問題は、データを生成している真のイデアルに何らかの意味で近いイデアルを見つけてくるということになるだろうが、まずイデアルの距離というのがよく分からない。任意の2つのイデアルは共通部分$\{0\}$を持っているし、大抵は共通部分にないいくらでも遠い多項式の組を取ることが可能である。
原論文でここをどのように考えているかはFigure 2の下半分を見れば分かる。細かいことを省いて説明する。$\tilde{f}_i\ (i=1,\dots,k)$が新しく見つけたい多項式を探す空間の生成元であり、これらのある行列$A$の右特異行列$U^T$を使った線形変換により新しい同数の多項式$g_i\ (i=1,\dots,k)$を作る($g_i=\sum_{j=1}^k U_{j,i}\tilde{f}_j$のとこ)。特異値分解の式$A=LDU^T$*1に右から直交行列$U$をかけた左辺$A U$の第$i$列が$g_i(S_m)$になっており、$L$も直交行列だからそのノルムは第$i$特異値$D_{i,i}$となる。そこでその値で場合分けし、$D_{i,i}$*2が十分小さい値$\varepsilon$以下であれば零化イデアルの基底の1つが見つかったとみなす(最後の行)。つまり、(探索空間の生成元にある条件がついてはいるが)サンプル点$S_m $上で十分小さい値を取る多項式が見つかればそれは求める基底の1つと見なしてよいという立場を取っている。
しかしこの立場はズル、すなわち明らかに求めたいものでない解を簡単に構築することを許している(でたらめな多項式の全係数に微小な値をかければよい)。ここがよく用いられる多項式回帰との前提条件の大きな違いのひとつでもあり慎重に考慮しなければならない部分のはずなのだが、原論文中にVCAアルゴリズムにおいてはこの立場で問題ないということを論じた部分はない。というわけで、冒頭に書いたとおりこの論文は問題設定のレベルで壊れていると思うわけである。
ここまで理解したところでびっくりして主要な関連研究に挙げられているApproximate Vanishing Idealアルゴリズム([3], 以下AVI)の論文を見てみたのだがそこではちゃんと"since the property of having small evaluations at the points of $\mathbb{X}$ is not preserved under multiplication by scalars, we require this property only for unitary polynomials, i.e. for polynomials whose coefficient vector has Euclidean norm 1."などと書かれている。要するに、多項式を係数だけを見ることでユークリッド空間上の点と同一視し、そのノルムが1となるようなもののみを基底に選ぶというわけである。この立場でズルができないことを自分で確認したわけではないが、先ほどよりだいぶ難しいのは確かだろう。
なお、原論文第6章の関連研究ではVCAのAVIに対する利点が論じられている。その1つにAVIでは特定の単項式順序を選択しなければならないのだが本来サンプル点の座標に順序はないのだからこれは不自然だ、と書いてあるのだが、グレブナー基底に関する標準的な議論でも不定元の順序に意味がなくともとにかくどれか1つ順序を固定することでよい性質が証明されるのだったわけでこれは妙な理屈だと思う。また(より微妙な点ではあるが)恒等的に$x_1=0$となるような$S_m $についてAVIは$x_1, x_1x_2, x_1x_2^2, \dots$を生成するがVCAは$x_1$だけを見つけることができるとあるが今は多項式環イデアルを考えているのだし多項式の次数と精度のトレードオフがあるはずなのだからとりあえず考えられる候補を全部見つけてくれるAVIの方がより自然であるように思える。総じて、これらの「利点」はむしろ使える構造をわざわざ捨てていることの傍証に見える。
もちろんVCAアルゴリズムが適当に修正した何らかの問題を正しく解いている可能性はあるが、ネット上の実装報告を見てもあまりうまく行っているように見えない。上のm-a-oさんのエントリでは「係数が、どんどん小さくなってしまったような答えが返って」くるとあり(4/12追記: m-a-oさんのコードのバグが修正されて、低次元ではうまくいってるっぽい。問題設定がどこかおかしいことに変わりはないと思うけどこのへんは差っ引いて読んでください)、原論文Figure 3の異様にいい結果*3もよく読んでないけどそういうことが起こっているのではないかという気がする。
自分で実装して挙動を確認したわけではないので自信はないが、そうしたことが起こる理屈としては、次のように、特異値分解が要らない構造を見つけてしまっているというシナリオが考えられる。VCAアルゴリズム(原論文Figure 1)中で、過去の反復で得られた、$S_m $上で0にならない多項式の集合の一部である$F_{t-1}, F_1$から、新しく見つけたい多項式を探す空間の生成元の元になる多項式の集合($C_t$とかFigure 3の$C$)を作る部分がある。ここで、その元$f_1, \dots, f_k$がたまたま($S_m $で評価した値を並べたベクトルではなく多項式の意味で)線形従属に近くなってしまったとする。すると、$f_i$から$\tilde{f}_i$を作り、またそこから行列$A$を作る手続きは$f_i$に関して線形なので、線形従属性は$A$にそのまま持ち込まれる。特異値分解はそれを見つけて小さい特異値を出力し、対応する右特異ベクトルで変換を受けて作られた$g_i$は恒等的に0に近い多項式になっている。つまり、サンプル点上で評価した値で作った行列の特異値分解を用いているので、サンプル点上だけで0になるという望ましい性質と、恒等的に0という望ましくない性質が見分けられないというわけだ。これはなんかそれっぽい気がするので実装した人は確認してみてほしい。
応用寄りで論文誌より国際会議を重視する分野に共通の傾向なのかもしれないが、基礎数理も応用も全部分かってるやばげな人が素晴らしい成果を上げる一方でこういうなんだかよくわからない研究が高評価を受けている機械学習界隈はなんだか不思議なところであると思う。
[1] Roi Livni, David Lehavi, Sagi Schein, Hila Nachlieli, Shai Shalev-Shwartz, and Amir Globerson. Vanishing component analysis. In Proceedings of the 30th International Conference on Machine Learning (ICML-13), pages 597–605, 2013.
[2] H. Michael Möller and Bruno Buchberger. The Construction of Multivariate Polynomials with Preassigned Zeros. Computer Algebra, pages 24-31, 1982.
[3] Daniel Heldt, Martin Kreuzer, Sebastian Pokutta, and Hennie Poulisse. Approximate Computation of Zero-Dimensional Polynomial Ideals. Journal of Symbolic Computation, volume 44 issue 11, pages 1566-1591, 2009.
