« 読了： Popper (2008) どんな未来予測でどんな予測手法が使われやすいか | メイン | 読了：VanderWeele & Knol (2014) ハーバード「交互作用」灼熱教室 »
2014年8月 6日 (水)
Guyon, I., Elisseeff, A. (2003) An introduction to variable and feature selection. Journal of Machine Learning Research, 3, 1157-1182.
題名通り、変数選択(特徴選択)についての啓蒙的レビュー。変数選択特集号の巻頭論文である。雑誌の性質はよくわからないけど、この論文は被引用頻度がものすごく高いらしい。どこかでみかけた「データマイニング必読論文」リストでも、たしか筆頭に挙げられていたと思う。
こういう工学分野の文章は苦手なんだけど、勤務先の仕事ときわめて密接に関連する話題なので、メモをとりながら頑張って読了。
1. イントロダクション
最近は数百～数万個の変数を扱う研究が増えている。その典型例は遺伝子選択とテキスト分類である。変数選択はデータ視覚化とデータ理解を促進し、測定・貯蔵の必要を減らし、訓練時間をへらし、次元の呪いを克服して予測成績を向上させる。
この特集号の研究は主に、予測のために有用な特徴の選択という課題について扱っている(opp. 関連する変数をすべて見つける課題)。従って、冗長な変数を除外するという点が問題になる。
まず変数選択のためのチェックリストを挙げよう。
- 領域知識を持っているか？ 持っていたら、アドホックな特徴のセットをつくれ。
- 特徴は同じ基準で測られているか？ でなければ基準化を検討せよ。
- 特長に相互依存性はありそうか？ もしそうなら、連言特徴なり特徴の積なりを可能な限り含めよ。
- 入力変数を極力減らす必要はあるか？ もしないなら、選言特徴なり特徴の重み付け合計なりを可能な限り含めよ。
- 特徴をそれぞれ評価したいか？ もしそうなら変数ランキングをやれ。でなければまずベースラインの結果を得よ。
- 予測変数が必要か? そうでないなら中止せよ。
- データは「汚い」かもしれないか(無意味な入力パターンとか、ノイズのある出力とか)？ もしそうなら変数ランキングをつかって外れ値を見つけよ。
- 最初に試すべきことが分かっているか？ そうでないならまずは線形予測を試せ。プローブ法を停止規準にした前向き選択法か L0ノルム最小化法を使え。さらに、同じ性質の予測変数を追加して特徴のサブセットを大きくしていけ。それで成績が上がるようなら非線形予測を試せ。
- 変数選択の新しいアイデア、時間、計算資源、十分な事例を持っているか？ もしそうなら、いろいろ試してモデル選択をやれ。
- 安定した解がほしいか？ もしそうなら、サブサンプルをとってブートストラップしろ。
2. 変数ランキング
入力変数を$x_1, \ldots, x_n$, 出力変数を $y$ とする。変数ランキングとは、$x_i$ と $y$ だけを関数に放り込んで、$x_i$ の価値を表すスコアを出す方法で、変数が直交であればランキング上位の変数群を予測子として選ぶのが最適だし、そうでなくてもランキングがあるとなにかと便利である。
ランキングの方法としては、$y$との相関を調べるとか、$y$が質的だったらROC曲線のAUCとか。情報理論的な基準を使うという手もある。良くつかわれるのは相互情報量。すなわち、$p(x, y) log \{ p(x, y) /( p(x)p(y) ) \}$ を$x, y$について積分したもの。$x,y$がともに離散変数の場合ならいいけど(積分の代わりに総和すればよい)、連続変数の場合は厄介で、正規近似すると相関係数みたいなものになってしまうので、離散化するか、Parzen windowsというようなノンパラ手法で近似するのだそうだ(←へぇー。カーネル密度推定のことかしらん？)
3. 事例
- ランキングに基づく変数選択は冗長な変数セットをもたらしかねないわけだが、しかし、いっけん冗長な変数でも、それを追加することでノイズ縮減とより良い分類が得られることがある... という例を3つ紹介。ええと、2変数2クラス(散布図上で右上と左下)の分類課題で、クラス内で無相関の場合、クラス内で相関+1に近い場合(この場合はさすがに1変数でよろしい)、クラス内で相関-1に近い場合。いずれも周辺分布は同じなので、結局、各変数を単独に評価していると最適な変数群を選び損ねるかもしれないわけだ。
- とはいえ、ランキングで役に立たなそうな変数をフィルタアウトしたいと思うのが人情なのだが(オーバーフィッティングが怖いからね)、しかしいっけん役に立たなそうな変数でも実は役に立つことがある... という例を2つ紹介。ええと、2変数2クラス(散布図上で左右)の分類課題でクラス内で相関がある場合と (なるほど、周辺からみると縦軸は役立たずにみえる)、2変数4クラスの分類課題でクラスがXORに並んでいる場合(当然ながら、周辺からみると縦軸でも横軸でもクラス判別できない)。
4. 変数サブセットの選択
この辺からだんだん未知の話になってくるので、メモも怪しいのだけれど... ええと、変数選択法は次の３つに分類できる。
- フィルター。前処理の段階で変数を選択する。ランキング上位の変数セットを選ぶとか。
- ラッパー。いま関心を持っている学習器(決定木とかナイーブ・ベイズとか最小二乗線形予測とかSVMとか)をそのままブラックボックスとして使い、所与の変数セットにスコアを与える。実際には、すべての変数セットを総当たりするのはふつう無理なので、探索方略をいろいろ工夫する(Kohavi & John, 1997, AI を読めとのこと)。もっとも、オーバーフィッティングの恐怖という意味では、精緻な探索方略よりも貪欲探索が良い。
- エンベデッド。学習のプロセスにおいて変数を選択する。ラッパーより効率が良い。このアイデア、別に新しいものではなくて、たとえばCARTはエンベデッド法である。
うーむ。全変数を叩き込んだランダム・フォレストで変数重要性を評価し、上位の変数を選んでモデリングするというのはどれになるんだろう。フィルター法だということになるんだろうなあ。
著者いわく、フィルター法をバカにしてはいけない。たとえば、まず線形予測を仮定してラッパー法とかエンベデッド法で変数選択し、やおら非線形予測モデルを組む、とか(前半戦がフィルターになっているわけだ)。情報理論的なフィルターというのもある(マルコフ・ブランケット)。この辺、私には難しいので中略。
以下、エンベデッド法についての話題。貪欲探索を用いるエンベデッド法の場合、変数追加なり削除なりによる目的関数の変化を予測するわけだが、その方法は３つある。
- ほんとに追加・削除してみて、目的関数の変化を調べる。
- 削除の場合、コスト関数の二次近似を求める方法がある。
- 目的関数における変数の敏感性を調べる(←これも削除の場合かな？)
目的関数とは、要するに適合度と変数数を組み合わせたものである。これを直接に最適化して、その結果として変数セットを得ようという方法もある。L0ノルム最小化とか(...難しいので中略)。
5. 特徴構築と空間次元縮約
変数を選ぶんじゃなくて特徴を作り直しちゃうという手もある。これは本来、領域知識が活躍する状況特有的な手法だが、一般的手法がたくさん提案されている。
特徴構築には二つの目的がある。データの再現と予測の効率化である。前者は教師なしの問題、後者は教師つきの問題である。そもそもの問題が予測なのに、教師なしな視点が入ってくるのは変な感じだが、著者いわく、場合によってはそうする理由がある。たとえば、教師なしの特徴構築のほうがオーバーフィッティングに強い。
特徴構築の方法としては...
- クラスタリング。階層的クラスタリングやk-means法なんかで変数をクラスタリングし、セントロイドを特徴にしちゃうわけだ。テキスト処理で用いられることが多い(語のクラスタリング)。
- 行列因子化。特異値分解しちゃうとか。
- 教師つきの特徴選択。ニューラルネットワークの中間層とか。ほかにも2つ紹介されているけど、難しいのでパス。
6. バリデーションの方法
えーと、モデル選択と最終モデル評価は別の問題である。後者の場合、原則として評価用のデータを別に用意する必要がある。ここで論じるのはモデル選択における交差検証の話。
- よく用いられるのはleave-one-out法だが、楽観的な結果になりがち。
- 最近ではmetric-based法というのがあって、ある変数セットを使ったモデルとその部分セットを使ったモデルについて、正解ラベルのないデータでのモデル間の差が訓練データでのモデル間の差に比べて大きいとき、これって小さいモデルのほうがいいんじゃね？と考える由。ふうん。
- プローブ法というのもある。簡単にいっちゃうと、データの中に乱数をいれておいて(これがプローブ)、前向き変数選択でこれが選ばれちゃったらストップ、というようなアイデア。(←なるほどねー。ランダム・フォレストのパーミュテーション重要性みたいなものか)
7. 発展的トピックと未解決の問題
- 変数選択における分散の問題。変数選択が安定しているとは限らないわけで、ブートストラップ法で調べるとか、「ベイジアン変数選択」(←ナンダソレハ)というようなアイデアがある。
- 他の変数がある文脈における変数ランキング。最近傍アルゴリズムによるランキング、なんていう提案がある由。
- 教師なし変数選択。信頼性とかスムーズネスとか、そういう基準で変数選択するという提案があるのだそうだ。
- 前向き選択がよいか後向き選択がよいか。後向き選択のほうがよいという意見がある($x_1, x_2, x_3$があって、最良解は$x_1とx_2$、次が$x_3$のみという場合、前向き選択だと$x_3$だけで停止するから)。
- 多クラス分類。2クラス分類から簡単に拡張できる方法と(フィッシャー基準でのランキングとかね。結局ANOVAのF値だから)、そうでもない方法がある。
- 特徴選択と特長構築の関係は、パターン選択とパターン構築の関係に等しい。とかなんとか。
- 単に予測するんじゃなくて、結果を引き起こす因果メカニズムについて推測する、という問題。このxはyの原因なのか結果なのか、というような。(←そりゃ難しそうですね...)
8. 結論
変数選択の手法は発展を遂げ、洗練されたラッパー法やエンベデッド法が登場しているが、そういうのを使ったほうが良いかどうかは場合による。次元の呪いやオーバーフィッティングは依然として怖い。だから、まずはベースラインとして、ランキングか前向き/後向き法で変数選択した線形予測をするのがお勧め。
...やれやれ、終わったぞ。
いっけん難しそうであったが、意外に平易でコンパクトなレビューで、大変助かりました。細部については理解できないところも多いのだが、この論文で勉強するような話ではなかろう。
論文：データ解析(-2014) - 読了：Guyon & Elisseeff (2003) 変数選択入門