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.

*1:内容の正しさには関係ないのだがこの表式はおかしい。こう書いたら普通はLDU分解だと思う。転置が付いてるから違うけど

*2:原論文の$D_{i,j}$はタイポであろう

*3:早々に誤差が0に収束しているように見える。本当に0に収束しているのだったら明らかに変な結果だし、そうでないならどこに収束したのかちゃんと見えるようなグラフにすべきだ（4/12追記: 明らかに変という程でもないかも?でも都合のいい結果の載せ方をしてるんじゃないかと思わせるグラフではあると思う）

ICFPC2012に参加しました

event

去年に引き続きLennMars他二名で参加しました。チーム名は地下ということでスニーカー文庫刊のあるライトノベルから頂戴してTeamKunikidaです。以下ソース。

https://bitbucket.org/LennMars/icfpc2012/src

メンバーが自分以外にOCamlが書けるわけではない情報系1人とプログラマですらない人1人という面子だったので設計には悩みました。結局メインをOCamlで書き、情報系の彼がコード書きに参加できるようOCamlからC++を呼べるようにしておくというのが事前に決めた方針でした。しかし彼は結局ほとんど参加できなかったのでFFI周辺の面倒な作業に時間を取られただけだった感はあります。
結果的にどういう設計になったかというと、C++側では目的地へのルートを計算するためのdijkstra法などを、OCaml側では目的地決めやら評価関数やらの細かい部品と型を整備してノンプログラマでも見様見真似でAIを設計出来るように、という分担をしました。例えばこんな型が定義されています。stateは盤面状態の型。

(*  plan__util.ml *)
type loc = int * int
type plan = state -> command list
type cond = state -> bool
type eval = state -> int
type direct = state -> loc option (* define where to go *)
type move = int * int -> plan (* define how to go. [] is unreacheable *)
type search = (plan * cond) array -> eval -> plan (* select preferable plan. Plans may be synthesized within a search *)
type transmute = state -> state

最終的にメインループに渡されるのは現在の状態から適当な長さのコマンド列を返すplan型の値であり、AIの設計者は盤面の評価関数の型evalの値や複数のplanからA*で探索を行って合成したplanを返す関数の型searchの値などを組み合わせることで新しいplanを書きます。
これらの型の値はhttps://bitbucket.org/LennMars/icfpc2012/src/98929be6c8ef/src/main/plans.mlにまとめてあり、これを見て同じ型同士の値を適当に入れ替えるなどしてOCamlをよく知らない人でもplanが書けるようになったらいいなあ、と思いながら設計しました。実際、https://bitbucket.org/LennMars/icfpc2012/src/98929be6c8ef/src/main/plan_coarse_safety2.mlなどは非プログラマの人が書いたものです。

というようなことがやりたかった訳ですが、仕様変更に追いつくのが大変で主要な道具であるdijkstra法やA*の完成度が低く、また今年も本当に面白いところに辿り着くまでに終わってしまったなあという悔いがあります。来年までに手を二倍速くするかOCamlが書ける一緒にやってくれる人を見つけたいですね……。


(8/28追記)
最終結果はRound1を86位で通過、Round2を89位で敗退でした。たまにセグフォで落ちるようなプログラムの割に案外いい成績でびっくりしてます。なおこのセグフォの原因は未だによく分かってません、先日参加したOCaml Crashで詰められればよかったのだけど時間足らず。

Implementation of Range Min-Max Tree

C++ Data Structure

前に論文を読んで放置していた、簡潔木構造の1バージョンであるrange min-max treeを実装した。

https://github.com/LennMars/SuccinctTrees

基本的な仕組みは
K. Sadakane and G. Navarro. Fully-functional succinct trees. In Proc. 21st SODA, pages 134–149, 2010.
パラメータ設定は
D. Arroyuelo, R. C ́novas, G. Navarro and K. Sadakane. Succinct trees in practice. In Proc. ALENEX, pages 84–97, 2010.
を参照した。

現論文に"easily implemented"とあるように300行程度の簡潔な実装で、特に真面目な最適化はしていない。どのような入力に対してどれくらいの性能が求められるのかいまいち勘所がよく分からないが、単純なクエリにおいては2番目の論文に載っているのとだいたい同程度の性能が出ているように見える。

Overcoming Browser Cookie Churn with Clustering

paper

グラフアルゴリズムの話が面白かったので別項目で気になったことをいくつか書く。勉強会での発表者便所さんのスライドはこちら。
http://d.hatena.ne.jp/repose/20120407/1333809676

Interval Graphと貪欲彩色アルゴリズム

Interval Graphとは、実数区間を頂点とし、二区間に重複がある場合対応する頂点間に枝を引いたグラフである。論文中で関連する引用がされていないので恐らく超有名な話なのだろうがよく知らなかったので軽く調べた。

Interval Graphは次の貪欲アルゴリズムで最低の色数で彩色できる。

  • Input:頂点の集合
  • Output:頂点と色の対応

  1. 頂点を対応する区間の始まりの値でソートする
  2. 各頂点について順番に、
    1. 既に色を塗った頂点で間に枝がないものが見つかればその色を塗る
    2. 見つからなければ新しい色を塗る

計算量は、ソートにO(|V|\log|V|)、頂点のループにO(|V|+|E|)で合計O(|V|log|V|+|E|)である。入力の時点ではどこに枝があるかは分かっていないが、ソートによってある頂点から出ている枝はその本数に比例した時間で見つけられるので、ここに由来する計算量はO(|E|)で済むというのが上手いところである。最適性の直観的な根拠は、二頂点間に枝があるなら、ソートした順番でその二頂点の間にある頂点は二頂点の若い方との間に必ず枝があることによる。

実はInterval Graph\subsetChordal Graph\subsetPerfectly Orderable Graph\subsetPerfect Graphであり、貪欲アルゴリズムの最適性はPerfectly Orderable Graphの性質である。グラフがPerfectly Orderableであるとは、頂点のある順序が、全ての誘導部分グラフ(よって自分自身も含む)について貪欲アルゴリズムが最適な解を見つけることを言う。そのような順序はperfect orderingとよばれ、次と同値である：任意の頂点と、その隣接頂点のうちその順序で先に来るものがクリークをなす。Interval Graphの頂点を区間の始まりでソートしたものはperfect orderingになっている(多分)。perfect orderingはChordal Graph一般について効率的に求めることができる。

論文中のAlgorithm2は上のアルゴリズム中で頂点に塗る色を、候補である枝を共有しない既存の色のうち、適当に決めた類似度が最大のものを選択するようにしたものである。ナイーブに実装すると色の候補数がバウンドされずスケールしないのでクッキー内の情報を利用して候補を狭めたり並列化したりしている。結構無理のあるヒューリスティクスだよなあと勉強会中でも話題になったが恐らくこうでもしないと本当に計算が終わらないのだと思う。計算時間と性能のトレードオフが知りたいところであるが論文中に定量的な言及はない。なお、候補のうちどの色を選んでも必要色数の最適性は崩れないが、Algorithm2では類似度がすべて一定値未満なら別の色を塗ることになっているのでこれは成り立たない。

参考：
http://en.wikipedia.org/wiki/Greedy_coloring
http://en.wikipedia.org/wiki/Chordal_graph

Theorem 1の証明のスケッチ

(後で書きます)

感想

event
  • 某研究所の人はやっぱりスライドや発表がちゃんとしている
  • 行動データを扱う研究特有の問題が見えて大変そうだなと思った（他人事）
    • Finding Your Friends and Following Them to Where You Areのときにあまり妥当でなさそうな既存研究との比較(Figure 4)が話題に
      • まあデータが違うのなら別の問題を解いているわけで本来比較しようもないが
      • 企業ならともかく大学の研究ならデータは積極的に公開したほうが分野のためだと思う
        • クロールしたデータの研究利用は可だが公開は不可という事例も多いか……
    • 競うべき明確な目標があると分野の発展に寄与するがいずれ本質的か怪しい改善に終止するようになるというのは一般的な現象っぽい
      • 話題に出たrelevance一点主義とか
      • 別分野だと昔の分散透過性研究とか
    • 適切な正解データを用意するのが難しいという問題も

Bigarrayモジュールを用いたOCamlとCの連携

OCaml

OCamlのマニュアルとかにやり方は大体書いてあるし出来るのは知っていたのだが実際にやろうとしたらコンパイルオプションとかでえらく苦労したので動いたミニマルな例をメモしておいた。
https://gist.github.com/1442320