ICML 2011メモ
TwitterでつぶやいたICML 2011の論文についてのメモ。まだあまり読めてないのだけれど、とりあえずここで一まとめ。ざっと目を通しただけなのでいろいろと間違ってるかもしれない。SVMの論文が多めなのは、SVMへの苦手意識を払拭しようとしてたから。
Large Scale Text Classification using Semi-supervised Multinomial Naive Bayes
その名のとおり、大規模データのためのMultinomial Naive Bayesの新しい半教師あり学習の仕方を提案している。従来はEMアルゴリズムを用いる手法が一般的だったが、大規模だと扱いが難しい。
提案手法のアイディアはまずラベル付きデータでConditional Log-Likelihoodを最大化し、データが足りない時はMarginal Log-Likelihoodを最大化するというもの。この考え方はgenerative modelとdiscriminative modelの傾向をもとにしている。具体的にはラベル付きデータをカウントしp(c|w)を求め、ラベルなしデータをカウントしてp(w)を求める。p(w)はNグラムデータなどから求めることができるだろうと述べられている。
分からなかったのはp(c)はどうするのかということと、semi-supervisedなEMを用いるのはラベル付きデータに含まれない未知語についてもラベルなしデータから学習するためだと思うので、そこはどうするんだろうな、ということ。
On Information-Maximization Clustering: Tuning Parameter Selection and Analytic Solution
Information-Maximization Clusteringはその名のとおりfeature vector xの分布p(x)とclusterの割り振りyの分布p(y)の情報量が大きくなるようにクラスタリングを行う。
この論文ではsqured-loss mutual informationを最大化することを目的とする。固有ベクトルの計算を行うことにより、解析的に効率的に解を求めることができる。またkernelパラメータであるnearest neighberの数を決定する手法も提案されている。
相互情報量を最大化するクラスタリング手法があること自体知らなかったので、とてもためになった。
Efficient Sparse Modeling with Automatic Feature Grouping
l1正則化項とpairwiseなl∞正則化項を用いたOSCARを最適化するための効率的なアルゴリズムを提案している。OSCARはこれら2種類の正則化項によってfeatureをグループ化することができる。提案アルゴリズムではfeatureの数dに対してO(d)の計算量で解ける。
具体的なアルゴリズムはソートしてマージしていく手続きになっている。面白そうだが、あまり回帰問題に慣れていないので、実際にどういうところで用いればいいのかはよく分からなかった。
Sparse Additive Generative Models of Text
新しいgenerative modelの定式化を提案している。従来のgenerative modelの問題点として挙げられているのは、1)Inference cost、2)overparametrization、3)lack of sparcity。提案手法ではlog-probabillityを足し合わせたlog-linear modelのような形で分布を定義している。
とても重要なことを言っているような気はするのだが理解できなかった。
Locally Linear Support Vector Machines
その名のとおり、線形カーネルSVMの速度を活かしながら複雑な分離平面を表現しましょうという論文。anchor pointの数がm、featureの数がnとして、この手法ではmnのfeature数の問題に変換が行われる。アルゴリズムとしてはstochastic gradient descentが用いられている。
実験ではk-meansを用いて得られた100のanchor pointを用いている。データはMNIST, USPS, LETTER。線形SVMよりも精度が良く既存のカーネルを用いた手法などよりも速いという実験結果が示されている。実際にはうまく工夫することによりm(=100)倍よりは速くできるようだ。
Infinite SVM: a Dirichlet Process Mixture of Large-margin Kernel Machines
入力空間を分割し各空間でSVMを学習する際に、その分割数をDirichlet processを用いて決めるというアイディア。損失関数と分布のKL divergenceの和を最小化するという問題に帰着している。そのままだとintractableなのでupper boundを変分法で最小化する。
実験ではmultinomial logitやDP mixture of multinomial logit、素のRBF-kernel SVMなどと比較し、よい結果を得たと報告されている。
個人的にはlearge-margin principleとBaysian posterior inferenceの結びつけはとても興味深く感じた。クラスタ間で要素の数が大きく異なるのはDirichlet processの表現としてstick-breaking representaionを用いているためなのかなという印象を受けたが、ただ単純にデータに偏りがあるだけのような気もする。
Multi-Label Classification on Tree- and DAG-Structured Hierarchies
カテゴリ構造が木構造やDAGの時のmulti label問題に対する手法が提案されている。この手の問題設定では、カテゴリ数が非常に多くなるということと、リーフノードのカテゴリではデータが少なくなってしまうという問題がある。提案手法ではラベルのベクトルをkernel PCAで次元を下げ、そこで全てのデータを用いて任意の学習器で学習し、テストデータに対する予測時には、圧縮した空間での予測を元のラベルベクトルに戻すという手順をとる。
実際に商品カテゴリやtaxonomyなどは木構造やDAGになっているので、この手法は非常に有用なのではないかと感じた。アルゴリズムも複雑でなく実装しやすそうだが、証明は読んでいないので正しく動作しているのかは確認していない。
perl-Algorithm-ComplementNB(complement naive Bayes)
最近は教師あり学習の分類器について調べている。そこで2年ほど前に話題になったcomplement naive BayesをPerlで実装した。コードは「y-tag/perl-Algorithm-ComplementNB - GitHub」にある。
Algorithm::ComplementNBは通常のnaive Bayesにおいてシンプルに補集合の頻度を用いたcomplement naive Bayes、Algorithm::TWCNBはオリジナルの論文に記されていたtransformed weight-normalized complemnt naive Bayesであり、こちらはTFやIDFの情報を用いたり、ドキュメントの長さで正規化したり、さらに対数をとって正規化を行ったりしている。
以下「Algorithm::NaiveBayes」とComplementNBおよびTWCNBを比較した。Algorithm::NaiveBayesのバージョンは0.04、CompelmentNBとTWCNBは0.01である。用いたデータは「Csmining Group」で公開されている「20 Newsgroups data set」と「R52 and R8 of Reuters 21578」。どちらもstemmedなものを用い、ComplementNBとTWCNBのスムージングパラメータであるalphaは1.0で計測した。評価指標はaccuracyである。
| NaiveBayes | ComplementNB | TWCNB | |
|---|---|---|---|
| 20Newsgroup | 0.810 | 0.824 | 0.835 |
| r8 | 0.961 | 0.951 | 0.941 |
| r52 | 0.869 | 0.877 | 0.868 |
結果としては、予想していたようなgainを得られなかった。ただし今回計測したのはaccuracyであり、precissionやrecallでは異なる傾向が見られるかもしれない。
以下、正解ラベルごとのaccuracyの結果である。
続きを読むFizzBuzz最短コード(FlogScript)
「anarchy golf - FizzBuzz」にポストしたもの。FizzBuzzをFlogScriptで36文字。
100,{)..{Fizz}@3%!*{Buzz}@5%!*+\`|P,ロジックとしては「FizzBuzz最短コード(GolfScript, Groovy)」のGolfScriptのものと同じ。しかし、stringとintに'*'演算を行うときには順番が決まっていたり、stringとintに'|'演算ができない点がGolfScriptとは異なっており、文字数を増やす原因になっている。逆に、コードの最後のブロックを閉じなくても良い仕様により文字数を減らすことができた。
FizzBuzz最短コード(GolfScript, Groovy)
1周回ってきたのでFizzBuzz。「anarchy golf - FizzBuzz」にポストしたやつ。
GolfScriptで37文字。
100,{)..3%!'Fizz'*\5%!'Buzz'*+\or}%n*Groovyで55文字。
100.times{println'Fizz'*(it%3/2)+'Buzz'*(it%5/4)?:++it}
FlogScriptにも挑戦したいところ。
WindowsでもChromiumを使う
Chromiumが容易にインストールできるようになってから、Ubuntu（10.04）ではFirefoxとChromiumの両方を使っている。あの青いアイコンにも愛着を感じてきたので、WindowsにもChromiumをインストールしてみた。そのときのメモ。
インストール作業自体はインストーラを実行するだけだったのだが、そのバイナリを見つけるのに少し時間がかかった。「The Chromium Projects」ではGoogle Chromeのダウンロードページへのリンクしか見つけられなかったのだ。
結局「Google Browser: Google Chrome And Chromium Download」を見て「Index of /f/chromium/snapshots」以下にバイナリがあることを知った。自前でビルドするときと同じように「BuildBot: Chromium」や「[chrome] Index of /」を参照して使うリビジョンを決める必要がある。当然のことだが、dev版やbeta版を使う時はバックアップをきちんととるなどして、何が起きても泣かないこと。
Apache Cassandra 0.7で動的キースペース作成
Apache Cassandraの0.6.xまではキースペースとカラムファミリ（RDBでいうデータベースとテーブルのような単位）を設定ファイルに記述していたため、設定変更には再起動が必要だった。しかし、0.7ではこれを動的に作成や変更ができるようになっているとのことだったので試してみた。
続きを読むGDD 2010 Japan DevQuiz
Google Developer Day 2010 JapanのDevQuizで用いたスクリプトなど。4つともPython。
問題リストに表示されていた得点は以下のとおり。
| 問題 | 得点 |
|---|---|
| Google Maps API | 1.0, 2.0, 3.0 |
| 2-legged OAuth | 5.0 |
| Shiritori | 1.0, 3.0, 6.0 |
| PAC-MAN | 35.0, 171.0, 未挑戦 |
