少年老い易く学成り難し

BreimanとAdaboostのconsistency

皐月 05/21 (土) 04:58 [Permalink]

UC BerkeleyのLeo Breimanと言えば同じくUC Berkeleyのマイケル・ジョーダンクラスの有名人でStanfordのJ. Friedmanらと一緒にCART(C&RT)を提案したのでも有名ですが、前にRIKENで見たときはでぷーっとしてはったイメージ(隣にいたFriedmanがやせてたからかもしれない)。で、それはどうでもいいんだけど、(ぼくは同じ人物だと思っているのだけど)たぶんもともと数学者で確率論の定評のあるテキストProbabilityやProbability and Stochastic Processesを書いている(数学では確率過程を研究してはったのかな?)。ま、これらの本の実物見た事ないけど(後者は古い)。

で、もともと良い理論は応用できるつうとこに興味があるようすで、決定木もそうだし、NIPSとかに(一年を除き)毎年行っているらしく、The Mathematics of GeneralizationでNIPSに投げられる理論研究についてふむうと述べてたりした記憶がある。決定木も結果が分かり易いため(これは実は応用を念頭におくならとても重要な事である)提案当時から今まで変わらぬ人気がある。そのあとboostingに触発されbaggingやarcingの話題を研究していたりした。アダブ(adaboost)と並んで有名なArc-GVとかはBreimanのやつ。

で、何が言いたいかというと、彼も齢なのでリタイヤしたという噂とか手が震えていたとかそういう噂のはなしではなく(どっちかというとLeoファンです)、とりあえず、ホームページにあったIMSの会議のWALD LecturesのPDFを見たぞ、と。そいで、彼がAdaboostがなんでうまく動くのかとかAdaboostの一致性に強い興味を持っていた(る)ことが書かれている。延々続く漸近論のファンじゃないけど識別器が一致性を持つかどうかはすごく重要と言っている(同意)。Adaboostは一致性を持ち無限に繰り返したらベイズリスクに近づくと思っていたらしいけど、実はAdaboostは(少なくともそのままでは)一致性を持たない。つまりループ繰り返したら良くなっていくとは限らない(というか最良の停止時間を持つらしい?)。

BreimanがAdaboostをconsistentだと思ってたとかって点はちょっと不思議で要するに間違えたところに識別器を足してく感じなわけだから(たとえば二つのクラスのサンプルの分布がオーバラップしてるとかだと)込み入ったとこに直感的にもオーバフィットすると私は思ったのだけど、BreimanがAdaboostていうときはどのアルゴリズムを指しているんだろーか…。つうか、入門解説とかにのってるアルゴリズムだと訓練誤差ゼロになってしまったら繰りかえせませんし…(Breimanはそのような場合restartする手続きを書いていたりしたけど)。ちなみに、無限設定でやると一致性を持つものを作れることを示してみたけどサンプルは有限だからダメじゃんと自ら言ってたり。ちなみにLugosi先生やってたように正則化を入れたらもちろんBayes riskに一致するものを作れる。

で、このへんの話はThe Annals of StatisticsのVol.32, No.1, 2004に特集であって、Discussionに入っているメンバーもBertlettやBickelからFreundやSchapire(これは特集の趣旨からして当然か…)、上のFriedmanやJordan、HastieやTibshirani, 果てはLugosiせんせとKoltchinskiiせんせなど。こそっとAlex Tsybakovの論文も載ってる…。

で、この号イイから手元に欲しい！と思ったけど、IMSのノンメンバーだと一冊3万くらいしますけどー！！！ってオチ。Annalsに3万はねえだろ！！内容は学内からオンラインで得られるのだし。はぁー、でも印刷物が欲しい…。何かIMSへ一旦入会したほうが安いんでねぇのか、これ。入会するかどうかは迷い中…。でも、IMSてこの辺の数理統計の雑誌を牛耳っているのでイイ感じもしてきた！

ILP

卯月 04/14 (木) 23:16 [Permalink]

コメントいただいたので「帰納論理プログラミング」という本を購入した。あー、たしかに何か似てる感じー。決定木の説明も載ってるけど分割統治でないILPが注目ぽい。そいで、結構やってはる方いるのかーっていうか調べてたら元北大現京大のY先生このあたり専門だったんかーと(コメントもらったのも違うY先生だ…。両方、やまつよ先生とは違います…)。データベース（論理）まわりから発生した理論なので趣きはだいぶ違うけれど、これも結局、識別なので、計算論的学習とかとターゲットは似ていて交流なんかもちょっとあるみたい。でも、パターン認識の本には載ってなかった…。データがカテゴリカル、でブール式の学習とかそういうのと似たフレーバ。

せっかく買ったんで、ちょっと勉強してみます。

パターン識別の数値実験評価での認識率のワナ

睦月 01/07 (金) 09:03 [Permalink]

シンプソンのパラドックスのはなしを聞いて思ったのだけれど、識別手法とかデータセットでクロスバリデーションなどで数値実験して比較する場合とか、(ちょっと違うけど)似たところに起因した現象があるなって。

実験の結果、正当数/質問数で、各クラス以下のような検査結果になった(交差検証やleave one outなどで求めたとする)。あるいは未知のテストデータが120個以下の配分で来たと思ってもよし。

この結果の「認識率」だけをみたら、90/120で識別法Aのほうが良さそうだっていう結論が普通くだされるのだけれど、ちょっと待て、と。識別法Bはどのクラスの識別についても、きっかり7割で正当を出している。しかし、識別法Aは「全部クラス1と判定した」のと同じだぞ！！クラス2とクラス3のラベルのデータは「ひとつも識別できてませんから！！」

ちなみにノンパラ検定しようとして「どちらかの識別法だけが間違えた個数」を見ても総数では 「識別法Aが識別できて識別法Bではダメ(20個)」と 「識別法Bが識別できて識別法Aではダメ(14個)」とこのデータセットに対しては結局「Aが有利」という結論が導かれそうなのだ。ふむう。どっちが良い、ということはなかなか単純には言えないぞ、と。

理論的にも識別誤差だけに注目したら「事前確率のあまりに低いクラスは捨てる」とゆうのはあながち間違ってないから、結構、タチが悪いんですな、これ。実際にはクラスの意味づけも重要かと。

識別器2D可視化

睦月 01/06 (木) 05:52 [Permalink]

後注：ニューラルネットの中間層の素子数を調整してみました。あと画像を若干大きめにし、文章を足し、画像クリックしたら拡大されるようにしました。また、一応、どうやってRで実装するかについて書いたとこへのリンクたしときました(サイト内ですが)。

以前の内容をこちらに移動しときます。統計的識別の問題は、回帰や密度推定より簡単な問題で、 特徴空間上の有限個の例題を使って、特徴空間上の任意の検査点におけるクラスラベル値を返す関数を作る問題です。したがって、決定論的識別なら、特徴空間を各クラスの決定領域へ排他的に分割すればよいことになります。有限個しか例題がないので常にベストなものというのは理論的に存在しませんので、結局、与えられた問題によってケースバイケースに使い分ける必要があります(だからたくさん識別方法が存在するのだけれど)。

いくつかの分かり易い人工データ(moon,cross,sphere2d)の2クラス識別を以下の12の識別器

1. 適応バンド幅推定つきのKernel密度推定で密度を推定したplugin Bayes識別器
2. 1-Nearest Neighboor Method
3. 5-Nearest Neighboor Method
4. 3-Layer Perceptron
5. Support Vector Machine
6. Relevance Vector Machine
7. Bayes Point Machine
8. Gaussian Process Classifier
9. Kernel Fisher Discreminant Analysis (Kernel化したBayes線形識別器)
10. Regression Tree (CART)
11. Breiman's Random Forest
12. Friedman's Gradient Boosting Machine (1ノードの木(Decision Stump)のLogitBoost)

で分離平面(所詮、各クラスの定義関数をデータから推論するだけなので2dの場合、識別境界が描ける)を描いたものを作ってみた。実装はRでそこらへんに出回っているものです。こまかいことは旧日記のこのあたりか、Rのページなどを参考にしてみてください。

ニューラルネットは、入力-隠れ層-出力の3層パーセプトロン(最大エントロピー基準,正則化なし,パラメタは中間層素子数)です。その他の識別手法もカッコ内が用いたパラメタです。以下の縮小画像での順番は上記の識別子番号で以下の表の順番です。

2色で色づけされているものは出力が離散なもの、グラデーションされているものはそうでないもので(どのあたりを重要視したか分かるので残した)、離散化した境界も実際の識別境界として併せて書いてあります。詳細はクリックして拡大するか、psファイルを印刷してみてください。

■ for cross data [ click to enlarge / download ps file ]

■ for moon data [ click to enlarge / download ps file ]

■ for sphere2d data [ click to enlarge / download ps file ]

パターン認識に関するいくつかの認識

師走 12/25 (土) 17:17 [Permalink]

こないだの話を聞いてちょっと思っていることのメモ。識別と知識発見は基本的に目的がことなる。後者では識別の良さとか汎化とかって概念が重要でないことも多い。

(1)識別において最も重要なのは「特徴量」であって、識別アルゴリズム「ではない」。へぼい特徴しかなかったらどんなアルゴリズムも良い結果をもたらさないし、逆にすごく良い特徴量があったら、単純な識別アルゴリズムで良い性能が得られる。

例：「いくつかの根拠(それぞれが特徴量になる)から血液型を判定するアルゴリズム(4クラス分類問題)」
対象者Xの特徴量としていくつか質問の答えを5段階で評価してもらったものを使う：「おおざっぱな性格か?」「自己中心的であるか?」など。あらかじめ採取した例題を用いて識別ルールを構成する。たとえば、「おおざっぱ ≥ 3 かつ 自己中心的 ≥ 3 ならば B型」のような推論規則が得られ、今後の対象者の血液型の判定にはこのルールが用いられる。どんな識別アルゴリズムがこの問題に対して良いのか？ちっとも自明ではない。

しかし、待てよ、と。血液型をちゃんと調べたいなら、医療的に採取した血液の各種データを特徴量とすれば簡単な識別アルゴリズム(ある性質があるかないか、とか)で、もっとまともな分類が可能であるわけである。

というわけで、なんでもかんでも特徴をとってきてoff-the-shelfに解きゃよいってもんではない。画像認識なら画像用の、文字認識なら文字の、テキスト分類ならテキスト分類の良い特徴量が必要である。ちなみにKernel法のKernelの設計の問題はある意味特徴量の研究である。が、入力特徴にやはり依存しており、それがへぼいとどうしようもない。

(2)用途によっては認識率が良けりゃ良いってものではない。例えば、クラスAとクラスBの判定問題(欠陥判定とか重要メールの判定とか)で、クラスBのデータは出現数が少なくて(クラス事前確率が低くて)、他のクラスに比べてサンプルがすくないとすると、判定アルゴリズム「すべてクラスA」は識別率の上では非常に良い性能を示す。が、明らかに「クラスB」を無視してほしくない場合もある。ものすごいスパムメールがたくさん来る人がスパムフィルタを使ったとして、「おまえに来るメールはすべてスパム」と学習されたら、確かにスパムはほとんど正しくスパムと判定されてはいるが、嬉しい事態ではない。クラスの意味づけとか、訓練データのアンバランスとか、事前確率の偏りとかがときにすごく重要である。

(3)質の良い教師データが必要である。たとえばデータをぱかぱかとれるからといってなんでもかんでもとってくりゃ良いというものではない。原理的には大抵の手法はサンプルが多いほうが性能が良いことが期待できる(特に漸近論によって保証されている手法は)。

まず第一に統計的にiid性が崩れるので標準的な手法を適用するメリットが薄れる(モデルが意味わからない)。また、誤りや欠損や事故入力を多く含みやすくなり、外れ値処理が面倒になる。また、原理的には特徴も多いほうが良いが訓練データが有限個しかないからどうしたって次元の影響が多かれ少なかれ出てしまう。また、もっと根本的な問題として100億データありゃ漸近保証に近いでしょ！！って期待はできるけど、メモリやハードディスクなどの制約上、こんどはそもそもアルゴリズムが終了しない。

しかし例題(教師データ)の質を保証することや、例題のクラスラベルをつけることには、人手が介入するので、高コスト・高負荷である。したがって、統計的保証が得られるくらいの十分なサンプル数がえられることは結構まれである。

ま、そんなこともあり、探索的データ解析(exploratory data analysis)として、与えられた訓練データがどれくらいまともな識別構造をもっているのかとか、どれくらい識別がむずかしそうか、とか、あるいは計算論的学習理論というか、その問題が例題数nに対して、どれくらいの計算コストを必要とし、どれくらいメモリを食うかって分析が重要かなーと。