狠狠撸

2 0 1 3 / 0 7 / 2 4
VANISHING COMPONENT
ANALYSISの試作
PRESENTED BY:
（株）デンソーアイティーラボラトリ
塚原裕史

VANISHING COMPONENT ANALYSIS
?ICML2013で、Best Paperに選ばれた論文
?“Vanishing Component Analysis”,
? Roi Livni, David Lehavi, Sagi Schein, Hila Nachlieli, Shai Shalev-Shwartz and
Amir Globerson
?概要
? 特徴抽出の手法の１つと見なせる。
? 多項式環のイデアルに関するヒルベルトの基底定理がベースとなって
いる。
? データ集合から生成される多項式環のイデアルの基底を近似的に求め
る。
※詳細は、上記の論文を参照。
?試作したプログラムを以下に公開
? https://github.com/htsukahara/vca/tree/master/sources/vca-1.0.0

VCAの試作コード
?以下に公開
?https://github.com/htsukahara/vca/tree/master/sources/vca-1.0.0
?vca.mというファイルに、メインの関数があります。
?Test_vca.mというソースに、VCAのテストを記述しています。
?免責事項
?とりあえず、実装したものでパフォーマンスなどは度外視してま
す。
?なので、あまりMATLABのコードとして宜しくない点が数々ありま
す。
?また、ほとんどデバッグもしてないので、自己責任で参考にして
下さい。

トイデータでの実験（その１）
?VCAがどういうものであるかを見るために、以下のような円状
に分布した点に対してVCAを適用してみた。

?論文における tolerance ε を0.05くらいに設定して得られた
Vanishing Components:
?次のページに、これらの各コンポーネントを tolerance ε の幅を
持って、データと重ね合わせて行く。
V[1]: 0.26754 + 0.046841*x1^1 + -0.36328*x1^2 + -0.06376*x2^1 + -0.038343*x1^1*x2^1 + -0.13928*x2^2
V[2]: -0.0022844 + 0.072493*x1^1 + 0.10035*x1^2 + -0.084707*x2^1 + 0.02228*x1^1*x2^1 + -0.072097*x2^2
V[3]: 0.31232 + 0.097518*x1^1 + -0.30486*x1^2 + 0.066927*x2^1 + -0.14482*x1^1*x2^1 + -0.28477*x1^2*x2^1 + -0.25061*x2^2 + -0.25091*x1^1*x2^2
V[4]: -0.025682 + -0.054276*x1^1 + 0.096947*x1^2 + -0.071436*x2^1 + -0.15781*x1^1*x2^1 + 0.32367*x1^2*x2^1 + 0.051512*x2^2 + 0.048112*x1^1*x2^2
V[5]: -0.07578 + -0.064608*x1^1 + 0.17686*x1^2 + -0.0060866*x2^1 + -0.17827*x1^1*x2^1 + 0.14067*x1^2*x2^1 + 0.072921*x2^2 + 0.073463*x1^1*x2^2
V[6]: -0.066597 + -0.059647*x1^1 + 0.099219*x1^2 + -0.03764*x2^1 + 0.14906*x1^1*x2^1 + 0.27183*x1^2*x2^1 + -0.013572*x2^2 + -0.016161*x1^1*x2^2
V[7]: -0.0005051 + -0.12604*x1^1 + -0.027532*x1^2 + 0.011103*x2^1 + 0.059585*x1^1*x2^1 + -0.18819*x1^2*x2^1 + 0.087099*x2^2 + 0.089508*x1^1*x2^2
V[8]: -0.22565 + -0.043397*x1^1 + 0.16063*x1^2 + -0.052239*x2^1 + 0.19902*x1^1*x2^1 + 0.14291*x1^2*x2^1 + 0.18545*x2^2 + 0.18571*x1^1*x2^2
V[9]: -0.24964 + -0.10927*x1^1 + 0.35287*x1^2 + 0.040723*x2^1 + -0.0029365*x1^1*x2^1 + 0.058575*x1^2*x2^1 + 0.15359*x2^2 + 0.15801*x1^1*x2^2
V[10]: -0.00014973 + 0.07807*x1^1 + 0.10713*x1^2 + -0.099983*x2^1 + 0.029578*x1^1*x2^1 + 0.05973*x1^2*x2^1 + -0.077561*x2^2 + -0.07685*x1^1*x2^2
V[11]: -0.00060915 + -0.10393*x1^1 + 0.015087*x1^2 + -0.029904*x2^1 + 0.077024*x1^1*x2^1 + -0.17902*x1^2*x2^1 + 0.061912*x2^2 + 0.064823*x1^1*x2^2

?第１成分のみ
?思ったほど綺麗にフィットされていないが（ソースにバグがある
かもしれない）、一応、円状の構造を反映している。

?第２、３、．．．11成分まで、順次足して行くと、次第に与えら
れたデータ点群がカバーされていく様子が分かる：

?

トイデータでの実験（その２）
? この論文を読んで、すぐに感じたことは例外値に弱いんじゃな
いか？ということであった。そこで、上のデータに少し例外値を
追加してみた。

? 先と同様に、tolerance ε を0.05くらいに設定して得られたVanishing
Components
? なぜかコンポーネント数が減っている。
? 後で示すように、例外値によってコンポーネントの広がりが大きくなったこ
とによるのではないかと思う。
? 同様に、これらの各コンポーネントを tolerance ε の幅を持って、デー
タと重ね合わせて行く。
V[1]: -0.11083 + 0.038054*x1^1 + 0.048012*x1^2 + -0.018638*x2^1 + -0.022661*x1^1*x2^1 + 0.02675*x2^2
V[2]: -0.0044302 + 0.042501*x1^1 + 0.064057*x1^2 + -0.063189*x2^1 + 0.0070576*x1^1*x2^1 + -0.057631*x2^2
V[3]: -0.080122 + -0.037428*x1^1 + 0.043917*x1^2 + -0.063285*x2^1 + -0.018331*x1^1*x2^1 + 0.031794*x1^2*x2^1 + 0.017317*x2^2 + 0.034438*x1^1*x2^2
V[4]: -0.092673 + 0.0080172*x1^1 + 0.023385*x1^2 + 0.0050679*x2^1 + 0.11425*x1^1*x2^1 + 0.033886*x1^2*x2^1 + 0.02108*x2^2 + 0.0062503*x1^1*x2^2
V[5]: -0.00043356 + 0.041244*x1^1 + 0.050858*x1^2 + -0.083603*x2^1 + -0.026333*x1^1*x2^1 + 0.0011246*x1^2*x2^1 + -0.077037*x2^2 + -0.006798*x1^1*x2^2
V[6]: -0.07939 + -0.037687*x1^1 + 0.043877*x1^2 + -0.064266*x2^1 + -0.018218*x1^1*x2^1 + 0.031903*x1^2*x2^1 + 0.017488*x2^2 + 0.034398*x1^1*x2^2
V[7]: -0.041434 + -0.00309*x1^1 + 0.016984*x1^2 + 0.092335*x2^1 + -0.045016*x1^1*x2^1 + -0.014456*x1^2*x2^1 + -0.033215*x2^2 + 0.011187*x1^1*x2^2
V[8]: -0.00020317 + -0.013846*x1^1 + -0.0087921*x1^2 + -0.057156*x2^1 + -0.062559*x1^1*x2^1 + -0.035072*x1^2*x2^1 + -0.053711*x2^2 + -0.016595*x1^1*x2^2
V[9]: 0.00035545 + -0.074852*x1^1 + -0.083445*x1^2 + 0.061207*x2^1 + -0.028002*x1^1*x2^1 + -0.038829*x1^2*x2^1 + 0.055342*x2^2 + -0.0076695*x1^1*x2^2

? 第１成分：やはり円状の構造を反映している。しかし、例外値
のためか、そのサイズがかなり大きく広がってしまっている。
（ややピンぼけ？）

?同様に、第２、３、．．．９成分までを、順次足して行く。第２、
３成分くらいまでは、なんとなく定性的には、例外値がない場合
に比較的似ている感じがする。

?

簡単な所感
? 実際に作ってみて分かった事
? Vanishing componentsを誤差ε の値の範囲で同時にゼロにする範囲にデータ点
は乗っていない。但し、どれらのコンポーネントの上に大体乗っている。
（まだ、実装したばかりなので、コードにバグが残っている可能性は高
い。）
? Tolerance ε の値を小さく選びすぎると、いつまで立っても non-vanishing
componentが残り続け、論文にあるようなアルゴリズムではなかなか収束し
ない。どうもオーバーシュートのような事が起きているのか、振動している。
(最大特異値の値を見ると、tolerance ε の値よりも大きな値で、振動してい
る。)
? 特異値を見ると、それが急激に減少する時があり、その辺りで止めて良いよ
うな気がする。（例えば、上のトイデータの場合、第一成分のところで、特
異値が急激に減少している。）
? 多変数多項式のプログラムを効率良く書くのは、結構大変。今回のコードは、
効率を考えていないので、実際の問題に適用するためには、ちゃんとその辺
を設計してやる必要がある。

簡単な所感
?その他、浮かんで来た考え
? 論文ではイデアルによって表される代数多様体によって、データの点を
フィッテングするようなことが書いてあるが、実際には tolerance ε で、
それをぼかしている。しかし、このようにして表される対象は、そもそ
も代数幾何学で扱われて来たものの中にあるのだろうか？もし、そうい
うものがあれば、その知見をVCAに応用することができると思われる。
? 今回のトイデータでは、そのぼやけた代数多様体（？）は、例外によっ
てj実際のデータの分布に比べて、膨張されていた。（もっと例外値が
増えると、そもそも定性的にもまったく一致しない結果になってしま
う。）やはり例外値へのロバスト性に問題があるようである。VCAを例
外値にロバストにするという方向で拡張を考える必要がありそうである。
? 問題によっては、データの配置に対称性がある場合がある。（今回のト
イデータのように。）その場合、単項式、あるいは多項式も、その対称
性を反映する形にして上げることで、コンポーネント数及びフィッティ
ングの良さも改善できるのではないかと思われる。

狠狠撸

Vanishing Component Analysisの試作と簡単な実験

Recommended

More Related Content

Viewers also liked (20)

Recently uploaded (6)

Vanishing Component Analysisの試作と簡単な実験