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になっているので、この手法は非常に有用なのではないかと感じた。アルゴリズムも複雑でなく実装しやすそうだが、証明は読んでいないので正しく動作しているのかは確認していない。
