Feature, Feature Space
昨日の例でもでてきましたが、Classifierは、結局、Featureとして与えられた部分だけしか見ずに分類をしています。
いくら賢い、理論が素晴らしい Support Vector Machine を使っても、与えられた Featureが身長と体重だけでは、男と女を区別するのは難しい。 なら、どんなデータを与えれば男か女か分かるんでしょうか？？ 画像の中には十分な情報があるはずです。 でも、単にピクセルをひとつ一つ順番に見たのでは、人間にだってその画像が、男か女か区別は付かないでしょう。 ではどうするのか？ どうやってFeature を作るべきなのか？ それは良く分かりません。
同じく、Kernel Trickに使う Kernelで、次元が高い Feature Space を定義するさいの、Kernelの作り方、選びかたは、謎のブラックボックスです。
高い予測精度を出すには、芸術的なエンジニアリングが必要です。
機械学習のシステムはそんなに賢くないのです。
分類問題
今回は Classifier (分類器)についての歴史です。 前回は、Model, Optimization, そして、Featureの話でした。 この三つを知らないと話がわからないので注意。
ふたたび、x を見て、y を予測したいとします。 例えば、x はパスポートの写真。 y は性別とします。 まず、x を数字の行列で表すとします。 高校のときに習ったベクトルです。 デジタルイメージの写真で、360*360の大きさなら、パスポートの写真は、360*360次元の空間の一点である、という感じに x のデータを数字に落とすことができます。
この x が生きる世界が Feature Space. 次元ひとつが Featureに対応します。 まあ、こんな感じで、ベクトル空間の一点としてサンプルを表すことができます。
さて、男と女を分類するにはどうするか。 歴史上のブレイクスルーが、いくつかありました。
まず、Perceptronが発明されます (Rosenblatt 1957)
これは、ニューラルネットワークの先駆けです。 分類されていない x が見付かったら、Featureひとつごとに、重みを掛け算して、合計の数字が、ある一定より大きければ、女、小さければ、男、みたいなモデルです。 この重みが学習すべき対象のパラメータ Θ です。 Featureごとの重みさえわかれば予測ができるし、重さを学習してやればそれで終わり。 簡単で非常に良いシステムです。 しかも、On-line Learningです。 ここから先に出てくるのは Batchなので、いまだに、On-line の学習方法としては良く使われています。
パスポートの例だと次元が高いので、単純に二次元のデータだと仮定して説明します。 例えば x が成人日本人の身長と体重、y が性別だとします。 すると、二次元ベクトル空間の一点が一人の人を表します。
perceptron が、具体的に何をやっているかというと、この、二次元ベクトル空間に、一本の直線（斜めでも縦でも横でも良い）を引いて、その線の上あるいは下にくるのは、女である、とか、男である、とか言っているわけです。 簡単です。 この線を適切に選ぶことが大事だというわけです。
日本人の男女の平均身長は5センチぐらい違うので、多分、これでもまあまあ分類できると思われます。 ランダムに選んでも50%で正解しますが、例えば、165センチ以上は男だ、と予測してやれば、正解率は50%よりは確実に高いと思われます。 男性の方が筋肉質で、身長に対して体重が重い、などという関係があれば、更に正解率が高くなります。
ところが、この方法は区分が直線であるため、どうしても分類できないケースも出てきます。 例えば、男は体重が多くて背が低い、あるいは、体重が少なくて背が高いかどちらかしかないが、女は体重と身長が比例している、みたいなことが起きているとします。 男が左上と右下に極端にわかれて、間に女性がいます。 このままのFeature Spaceでは、一本の線を使って、男性と女性をわけるのは不可能です。 曲線とか、二本の線を使わないとできません。
これが証明されたのが、(Minsky and Papert 1969) でした。
ショック。 なんだ、Perceptronって使えないじゃん！ というわけで、しばらくこの線の研究が減ります。 その後、いきなりfeatureに重みを付けて足し算して、ある数より上か下かをみるんではなく、もう一段階踏んでみれば大丈夫だ、とわかってきます。 featureと重みを掛け算したものを幾つか足して、それにもう一度重みをつけて掛け算して足す、など、二段階、三段階踏めば、直線以外で分類できるぞ！と、分かったのです。
が、それだとOptimizationが上手くできない。 どうしたらいんだ？
Backpropagationが発見されます。(Rumelhart, Hinton, and Williams 1986）
そしてニューラルネットワークが一躍有名になり、流行ります。 二段階、三段階踏んでも、後ろから順番に重みを直すことで、学習できるようになったのです。 これで、直線以外で分類できるようになりました。
ところが。。。 この、Backpropagationは、Optimizationの方法としてはあまりエレガントでない。 パラメータ Θ を探すとき、局部的な解答を見つけてしまって、最適解を見つけられないし、訓練に時間がかかると分かってきます。
うーむ。
そうして、時代は Perceptronに逆戻り。 Support Vector Machine系の話が出始めます。 学習にあたって、最適な、男性と女性サンプルが一番遠くに分かれるような、一本の線をビシッと見つける方がいいのではないか？ という考え方です。 この、あたらしい考え方でOptimizationするのが良い、という理論が構築されます。
Soft Margin Support Vector Machineが発見されます。 (Boser, Guyon and Vapnik 1992)
だが、そのままでは曲線を使って分類できない。 なんとか、曲線を使ってビシッと分類できないものか？？？ 曲線を扱えるModelで、うまくOptimizationはできないのか？？
ここにきて、もうひとつの方法が注目されます。
Kernel Trickです (Aizerman, Braverman and Rozonoer 1964)
もともとのFeature Space から、もっと高い次元の新しい Feature Space へ、Kernel Trickを使って移動しよう。 その高い次元の方で、綺麗にサンプルを分けられる直線を探して、元の Feature Spaceに戻してやれば、そこでは、なんと曲線になるではないか！！！
ここ10年ぐらい、Classifierでは、この系統がずっと流行っています。 ニューラルネットワークは、ICMLや、NIPSのような機械学習の国際会議では、ほとんど見られなくなってしまいました。
機械学習
しばらく、資料集の紹介だったので、ここらへんで専門に勉強しない人に向けた機械学習についての解説をすこしだけします。 主なタスクは、以下の様なものです。
(1) Supervised
訓練用にサンプルを用意して、機会に学習させた後、テスト用の別なサンプルでどれぐらい学んだかをテストします。 教師が必要で、通常人間が訓練用サンプルを準備します。
Classification (分類)
あらかじめ決めておいたカテゴリーに、サンプルを分類します。
Regression
サンプルごとに、数字を予測します。
(2) Unsupervised
訓練用のサンプルを必要としないタスク。 教師なし。
Anomaly Detection
めずらしいサンプル、ほかと違うサンプルを見つけます。
Clustering
サンプルがどのように分類できるか、カテゴリーを発見します。
Summarization ＊注意
データの傾向などを見つけます。
＊注意 自然言語処理にも、要約文を作り出すタスクがあり、自動要約と呼ばれます。
＝＝＝＝＝＝＝＝＝＝＝＝
Data Mining と Machine Learning の違い。
どちらも同じ人工知能のサブエリアなのですが、傾向として、大量のデータを処理して情報を得るのが Data Miningで、ややこしいサンプルのモデルを作って解析したり、少量のデータから出来るかぎりを搾り出す傾向にあるのが Machine Learningです。
したがって、Data Miningでは、ClassificationとRegressionの場合、データが簡単でその代わりに大量にあるケース、そして、データが大量で人には分析しきれないケースでは、Anomaly Detection, Clustering, Summarization に、より力を入れています。 アプリケーションとしては、ウェブサイトのログ解析、金融機関のクレジットカードの使用履歴から、自己破産の危険性があるリスクの高い個人を特定する、などがあります。
Machine Learningでは、Classification, Regressionに力を入れる傾向があります。 そもそもどのように数値に落としたらよいのか良く分からないぐらい複雑なデータ、サンプルであることも多いです。 分類するにしても、カテゴリーの数がサンプルの数より多かったりします。 (structured prediction) 例えば、文章を文法解析したり、プロテインのアミノアシッドの列から、プロテインの形や機能を予測してみたり、といったことです。
Data Miningの代表的な国際会議は KDD、Machine Learningの代表的な国際会議は ICML、NIPSなどがあります。
＝＝＝＝＝＝＝＝＝＝＝＝
機械学習の手順（教師ありの場合）
例えば、明日の天気を予測するシステムを作るとします。 x は衛星から見た今日の気象状況のデータで、 y は明日の天気だとします。 x をみて、y を予測するのが今回の仕事です。
Model
問題にあわせてモデルを作ります。 モデルは数式やルールで表されます。 見たことがないサンプルの x がわかれば、今持っているルールやパラメータ Θ を使って、y という予測がたてられるな、という決まりごとをあらかじめ作っておきます。
Optimization
学習のステップです。 訓練用のサンプルをみて、x と y の対応具合から、モデルのパラメータ Θ を決めます。 Θ を正しく選べれば、見たことのないサンプルでも予測ができるわけです。 モデルを訓練用データにフィットさせます。
この Model にはこの種類の Optimizationしかうまくいかない、というように、二つを綺麗に切り離すことができない種類の学習システムもあります。 最近の流れでは、ModelもOptimizationも、数学的に解きやすくて、いい特徴がある綺麗な形に直す傾向が強いです。 かなり高度な数学が必要になってきます。 ニューラルネットワークなどは、あまり良い数学的特徴を持っていないため、最近、あまり流行っていません。
一言で言えば簡単ですが、Model、Optimizationの組み合わせでいろいろな問題がでてきます。
モデルにサンプルを渡す際、サンプルのどの側面（Feature）について教えるのか選ばなければなりません。 例えば犬と猫を分類するとします。 鳴き声に注意を払えばいいのか？ ヒゲがあるかどうか見るべきか？ それとも、色の違い？ ここが違うと、同じModelとOptimizationでも、まったく結果が違ってきます。
さらに、モデルが複雑過ぎて、学習するのに時間がかかりすぎたり、うまく一般化しないことも良くあります。 訓練用のデータは完璧に分類できるのに、テスト用は全然正しく分類できなくなってしまう、（Over-fitting）など。 人間でいえば、数学の練習問題を丸暗記したけど、理解できなくてテストは全然ダメ、という感じです。
同じような Model なら、より良い、綺麗に一般化する Optimization を行うほうが良いです。 モデルの複雑さも、どの程度学習内容が一般化するかを決めるので、問題に適応したうまい組み合わせを作ることが求められます。 また、理論的に、この条件下ではこの方法が良い、という証明も盛んです。
＝＝＝＝＝＝＝＝＝＝＝＝
Modelのアプローチは、パラメータ Θ をどのように持つか、で、かなり変わってきます。
まず、最近盛んなのが、Linear Classifierという種類。
Perceptron, Winnow, Naive Bayes, Support Vector Machine, Linear Discriminant Analysis, Gaussian Processなどです。 Featureごとに重みを掛け算し、それらを全て足してから一定の数より高ければ正解、そうでなければ間違っている、という感じのモデルを様々な方法で学習します。
次は、ニューラルネットワーク。
Linear Classifierの延長線上にあります。 Featureごとに重みを掛け算し、いくつか（全てではない）足してから一定の数より高ければ、もう一度重みを掛け算して、足し算。。というように、Linear Classifierみたいなのをネットワークの形にしたがって、順番に何回か繰り返します。
そして、Decision Tree。
一つめのFeatureの数字が、ある一定より上だったらこちら、下だったらこちら、という感じで、まず、一つのFeatureだけを見て分類します。 その結果に対して、別のFeatureを見て、また分類します。 それを繰り返して、残ったこの区分は全部正解、この区分は外れ、みたいにするわけです。 どのFeatureをどの順番で、何回使って分類するかはデータを見て決めます。
Inductive Logic Programming。（ILP）
Decision Treeをさらにおしすすめて、Predicate Logicみたいなルールを作っていきます。
k-Nearest Neighbor。
がらっと方向性が変わります。 訓練用のデータがあるFeature Spaceは、ベクトル空間なので距離のコンセプトがあります。 新しいサンプルが来たときには、訓練用のサンプルのなかから、新しいサンプルに一番近い k個を見つけます。 k個の中で、多数が正解、と言っていれば新しいサンプルも正解と予測します。
他にも、Graphical Modelで、Bayesian Belief Networkなど重要ですが、それは又の機会に。
＝＝＝＝＝＝＝＝＝＝＝＝
Optimizationのアプローチは、学習時の状況で、大まかにわけて二つにわけられます。
On-line Learning
インターネットでクラスを取って勉強することではありません。 インターネットのOnlineは、線につながっている、という意味。 ここでいう、On-lineとは、一列に並んで列になって、みたいな意味です。 ダッシュ(-）はないこともあります。 どういうことかというと、学習するためのサンプルを、ひとつづつ、一回しか見ないで学習する方法論です。
Batch Learning
まとめて多くのサンプルから学習します。 On-lineで、ひとつひとつサンプルを見たのでは得ることができない統計を使えます。 したがって、Batchで学習したほうがより精度の高い予測をたてることができます。
Semi-supervised Learning
一部で有名になっています。 目的となる学習と、correlationがある別の学習を同時に行なうことで、データの構造を利用してsemi-supervised learning ができる、という論文です。
Ando & Zhang
http://www-cs-students.stanford.edu/~tzhang/papers/jmlr05_semisup.pdf
それから、Semi-Supervised Learning Literature Surveyも付け加えておきます。
http://www.cs.wisc.edu/~jerryzhu
structured output 向けの semi-supervised learning。
http://ttic.uchicago.edu/~altun/pubs/AltMcABel-NIPS05.pdf
あらかじめk-NNで作ったmatrixを、学習するさいに埋めこんでいるみたいです。
他にも、NIPSのWorkshopにあったsurvey っぽい論文
http://iitrl.acadiau.ca/itws05/Papers/ITWS08-Kai_Yu-learntolearn_REV.pdf
そして、昨日終わったばっかりの HLT 2006 の Tutorial です。
Inductive Semi-supervised Learning Methods for Natural Language Processing
自然言語処理、task & corpus
機械学習を評価するにあたって、応用問題に落としてテストすることも重要です。 個人で参加できるような、お金がかからない自然言語処理のデータセットはないかと思って探してみました。
CoNLL Shared Task
http://ilps.science.uva.nl/~erikt/signll/conll/
PKDD、SPAM分類問題
http://www.ecmlpkdd2006.org/challenge.html
GINEA
http://www-tsujii.is.s.u-tokyo.ac.jp/GENIA/
William Cohen's webpage
http://www.cs.cmu.edu/~wcohen/
Shared Taskは、通常、参加する旨をメールで送れば、Agreement formにサインした後、Corpusをダウンロードすることができます。 データさえあれば、研究所に属していなくても個人で研究しやすくなります。
最近のBayesian Methods
Clustering 系の Bayesian Methods
HLT の Tutorial が非常に面白かったので紹介します。
http://bayes.hal3.name
http://www.isi.edu/~hdaume/bayes/hlt-slides.pdf
HLT 2004 の tutorial はここ。
https://ssli.ee.washington.edu/~bilmes/bilmes_hlt04_tutorial/bilmes_tutorial.pdf
これらのモデルで、何が難しいかというと、Hidden Variableがふたつ以上隣にあり、関連があるために、推定しにくいのが問題だそうです。 だから分布が指定してあっても簡単に計算できない。
前に出てきたTutorial (non-parametric bayes)は、
このtutorialの延長線上にあります。 分布のパラメータが、データが増えるに従って増えるように直し、クラスタの数などをあらかじめ指定しなくてもすむようにすると、次のような話になります。
http://www.cs.berkeley.edu/~jordan/nips-tutorial05.ps
Graphical Modelで、non-parametric priorをつかって、いろいろな相関関係を考慮しながらクラスタリングする話です。 Hidden Variableがクラスターを表しています。
まとめトピックということで、
もう少し使いかたの具体例がある tutorial がここらへんです。
http://www.milab.is.tsukuba.ac.jp/~myama/pdf/topic2006.pdf
http://www.stanford.edu/~grenager/papers/dp_2005_02_24.ppt
他の presentations
http://l2r.cs.uiuc.edu/~cogcomp/AIML/ARCHIVE/2004-FALL/papers/braz.ppt
http://www.cs.columbia.edu/~risi/talks/chinese.pdf
http://www.cs.huji.ac.il/course/2004/learns/LatentDirichletAlloc.ppt
http://courses.ece.uiuc.edu/ece598/ffl/paper_presentations/NicolasLoeff_LDA.pdf
もうすこし細かい論文。
中華料理店プロセスと、中華料理チェーン店プロセス
(Chinese Restaurant Process & Chinese Restaurant Franchise Process)
http://www.cog.brown.edu/~gruffydd/papers/ncrp.pdf
http://www.cs.berkeley.edu/~ywteh/research/npbayes/nips2004a.pdf
http://www.cse.buffalo.edu/faculty/mbeal/papers/bayana05.pdf
http://www.cs.princeton.edu/~blei/papers/TehJordanBealBlei2004.pdf
http://en.wikipedia.org/wiki/Chinese_restaurant_process
インド料理食べ放題プロセス
(Indian Buffet Process)
http://www.cog.brown.edu/~gruffydd/papers/ibpnips.pdf
http://www.cog.brown.edu/~gruffydd/papers/ibptr.pdf
Latent Dirichlet Allocation
http://www.jmlr.org/papers/volume3/blei03a/blei03a.pdf
http://www.cs.princeton.edu/~blei/papers/BleiNgJordan2003.pdf
http://chasen.org/~daiti-m/dist/lda/
パチンコ Allocation
http://www.cs.umass.edu/~mccallum/papers/pam-icml06.pdf
==================================
Clusteringだけではない！
Bayesian Regression/Classification
Bayes Point Machine
http://research.microsoft.com/~rherb/bayes_point_machines.htm
同じくBayes Point Machine (Online)で、Non-projective Dependency Parsingしたら Max Margin (Online) に勝った話。HLT2006
http://ssli.ee.washington.edu/people/duh/papers/BPMParsing.pdf
Gaussian Process
http://www.gaussianprocess.org/
On-line Learning Algorithm
online -> batch conversionをどうやるかについての論文。
