搜索
機械学習による自然言語処理チュートリアル～PerceptronからCRFまで～岡野原大輔東京大学PreferredInfrastructure20088/3@PFI本郷オフィス目次•自然言語処理紹介•機械学習導入•パーセプトロン•バッチ学習(最大エントロピー法)•過学習/正則化•多クラス分類•系列分類(CRF,StructuredPerceptron)このへんで眠くなる自然言語処理(1/2)•言語情報をコンピュータで処理する–コンピュータ言語の研究との対比で自然言語–世界最初のコンピュータの出現の頃から自動翻訳は試みられている。コンピューターサイエンスの中でも歴史の長い分野–近年ビジネス的にも成功,Googleなどなど•非常に幅広い分野と接触する、境界領域–処理する手法=言語学,数学,統計学,機械学習,アルゴリズム,データマイニング,データ構造,物理–処理する対象=情報検索,ウェブ,音声情報,ユーザーインターフェース–言語が絡んでたら何でもいい自然言語処理(2/2)•分野例–構文解析（係り受け解析）–意味解析,SRL–機械翻訳（統計的機械翻訳,ルールベース）–情報検索–固有表現抽出、文書分類、単語クラスタリング、•有名な学会、ジャーナル–ComputationalLinguistic,ACL,EMNLP,CoLing,NAACL,EACL,IJCNLP,などなど–「自然言語処理の学会」–ACLanthology自然言語処理で機械学習を使う自然言語処理ルールベース編•人手でルールをひたすら書いて処理する•例：スパム排除ルール–if(s=~/H|奥様|楽しかったね/)thenスパム•単純だが強力な手法で昔から現在でも活躍–現時点でも日英機械翻訳などはルールベースの方が精度が良い自然言語処理ルールベース編•長所–内部処理が分かりやすい–人手で調整可能–頑張れば頑張るほど精度が上がる•短所：–コストが大きい(最初は精度が伸びるが、そこから伸びない、メンテナンスコスト）、–新しいドメインに弱い、–ルールに専門知識が必要（職人芸）、–一貫性が無い（時間、人によってルールが変わる）自然言語処理機械学習編•人手でルールを書く代わりに正解の訓練データを用意し、そこから正解を導くルールを導出する–自然言語処理の場合、ルールは「単語」や「品詞」の出現などを利用•ルールの候補集合を決め，その中の効くルールは学習で自動で探す–どのようにルールを作るか＝テンプレート機械学習の前にルールベースvs機械学習•何か問題を解こうとする場合は、むやみに機械学習を使わず検討してみる–訓練データを得るためのコスト対–ルールを書くためのコスト•ルールベースの方が良い場合も多い–問題のスケール、要求される精度、問題に対してもってる知識などでよく吟味–ルールの多くは素性という形で機械学習に反映させることもできるが、複雑な場合は人がやったほうがいい（文法変換などは数千行のperlでかいたそう）ベクトル表現•多くの自然言語情報は疎な高次元のデータとして扱うことができる–文書のBOW表現では、Vを単語種類数とした時，各単語に0～V-1の順番に番号を振る–i番目の単語が出現したらVi=1とするV次元のベクトルとして扱える0:Best1:Drug2:Congratuation3:FlowerDrug…Best…FlowerDrug…Congratuation…11010110各値を決めるのに使ったルールを素性（そせい、または特徴）、この高次元ベクトルを素性ベクトル（特徴ベクトル）と呼ぶ。線形識別器•分類問題：入力xをニ値(y=+1,-1)に分類–例：文書をスパム(+1)orそれ以外(-1)に分類–S(x)≧0⇒y=+1–S(x)0⇒y=-1と判断する–wi0ならば、xiが出現したらスパム度合いが増す（|wi|が大きければ大きいほど効く）•このようなwをどうやって求めるかmmTxwxwxwS...)(1100xwx重みベクトルwを求める•訓練データ(xi,yi)(yi=1or-1)を正しく分類できるようなwを求める–全てのiでyiwTxi0をみたすようにする–訓練データを分類できるのだから、未知のテストデータも分類できるのだろう（という期待。真面目には汎化性能とかを議論しなければならない）オンライン学習・バッチ学習•オンライン学習–訓練データを1例ずつ見てwを更新する–長所：あらかじめ全部の訓練例をもたなくても良い。速い（一般に訓練データ数に線形の計算量）–短所：バッチに比べ適当、訓練例の順番に偏りが大きい場合に精度が不安定•バッチ学習–訓練データを全部見てからwを求める–長所：精度が良い、理論的保証も強い(汎化性能）–短所：重い場合が多いオンライン学習パーセプトロン[Rosenblatt57]•w={0,0,….0}に初期化•loop–(xi,yi)訓練データをランダムにとってくる–s:=yiwTxi//wTxi=現在の予測–if(s0)//現在の予測が外れた•w:=w+yixi//w+αyixi,0α1とする場合–endif•endなぜ学習できるのか•更新後の重みベクトルw’:=w+yixi•これを使って、もう一度間違えた訓練例（xi,yi)を分類するとw’Txi=(w+yixi)Txi=wTxi+yixiTxi先程間違えた予測結果常に正wは正解が出るように更新されるPerceptronの収束定理[Block62][Novikoff62]•Q.直前の訓練例だけを分類できるよう更新して、全ての訓練例を分類できるようになるのか？•A.訓練例が線形分離可能ならできる•定理：もし訓練データ(xi,yi)(i=1...m)(|xi|R)が、ある重みベクトルu(|u|=1)でマージンγで分類可能なら(yi(uxi)≧γ)、アルゴリズムの更新回数は多くても(R/γ)2–xの次元数によらないことにも注意Perceptronの収束定理の証明wkをk回目の更新前の重みベクトルとおくwk+1u=wku+yi(uxi)≧wku+γこれよりwk+1u≧kγ(w0=0)また、|wk+1|2=|wk|2+2yi(wkxi)+|xi|2≦|wk|2+R2これより|wk+1|2≦kR2上記二つよりkR2≧|wk+1|2≧(wk+1u)2≧k2γ2⇒(R/γ)2≧kwkで間違った訓練例なので値は負Perceptron補足•線形識別可能で無い場合は使えないとの批判[Minsky69]–データにノイズがある場合やxorなど–廃れてしまった・・⇒最近復活！•カーネルトリックを使える[Y.Freund98]•後述の構造学習などでは、非常に強力な学習手法であることが分かってきた[Collins02,Daume06]•自然言語処理分野をはじめ多くの分野で再度、使われるようになってきた++--頭が疲れてきたかもなのでちょっと休憩続いてOLL実践編OLLを使って実際に分類をしてみよう•OLLではパーセプトロンを初め様々なオンライン学習手法がサポートされているwget;./configure;make;(makeinstall)oll_trainPtrainfilemodelfile(パーセプトロンで学習し、学習結果をmodelfileに保存する）oll_testtestfilemodelfile（学習結果をmodelfileから読み込み、testfileを分類する）訓練・テストデータのフォーマット•各行が1訓練例に対応–最初に正例なら+1,負例なら-1を書き、その後に素性番号：値の列を並べる+10:1.0201:2.2744:-0.315:3.0….-147:2.066:0.1733:1.0500:1.0+13:1.0201:2.2300:-0.315:0.3文書分類を作ってみよう（C++ですいません）mapstring,intstr2id;//文字列から素性番号への連想配列vectorstringid2str;//素性番号から文字列への逆引きintgetID(conststring&str,mapstring,int&str2id){mapstring,int::const_iteratorit=str2id.find(str);if(it!=str2id.end()){returnit-second;//登録済みのIDを返す}else{//登録されてないconstintnewID=str2id.size();str2id[str]=newID;//登録id2str.push_back(str);returnnewID;//新しいiDを返す}}intdoc2fv(conststring&doc,constinty,ofstream&outf){istringstreamis(doc);//docの単語はスペースで区切られている。きられて無い場合はmecabやら辞書の最長一致をしてくださいstringchunk;vectorintIDs;while(ischunk){IDs.push_back(getID(chunk));}sort(IDs.begin(),IDs.end());IDs.erase(unique(IDs.begin(),IDs.end()),IDs.end());//重複を除くoutfy““;//ラベルfor(size_ti=0;iIDs.size();i++){outfIDs[i]“:1“;}outfendl;}スペース区切り済みのドキュメントから素性ベクトルを作る学習バッチ編バッチ学習編•全部のデータを真面目にみてもっと精度を高くしよう•f0/1：0/1損失関数–f0/1(a)=1もしa0,=0それ以外–Σif0/1(yiwTxi)を最小化するようなwを求める10ywTxｆ0/1重みベクトルwを求める(続)バッチ学習編•Σif0/1(yiwTxi)を最小にするwを探す–数値最適化問題•この最適化問題は実は難しい！–関数f0/1(a)は微分不可能で凸でもない（極小解が複数存在する）wiwが1次元だったらΣif0/1(yiwTxi)極小解探したい値様々な損失関数によるf0/1の近似凸（穴が無い、Hessian行列が正定値）または微分可能（滑らか）な関数緑：SVM(hinge-loss)青：MaxEnt(logloss)紫：AdaBoost(exp-loss)]1[xwTy))exp(1log(xwTy)exp(xwTy線形識別器まとめ•訓練データを用意(xi,yi)(yi∈{-1,+1})•学習：損失関数Lを使ってΣiL(xi,yi,w)が最小となるwを探す•推定：分類したいデータxnewに対しs=wTxnewを求め–s0⇒y=1,–s0⇒y=-1と推定する•非常に多くの分類器がこれに属する–SVM,最大エントロピー法、NB、Adaboostなど過学習/正則化過学習•訓練データは分類できるようになっても、テストデータが分類できない場合がある•大抵、訓練データにオーバーフィットしている場合が多い–訓練データとテストデータの性質が違う場合もあるがそれはまた別の話回帰の例：青は2次曲線赤は8次曲線赤は全ての点を通っているがスムーズではない（オーバーフィット）正則化•過学習を防ぐようにwにペナルティを与える–絶対値が大きいwiにペナルティを与える–L2ノルム|w|2=w12+w22+….wm2–L1ノルム|w|=|w1|+|w2|+…+|wm|–実はこの二つがものすごい差を生む（今回は話しません）•訓練例を正しく分類しつつ過学習しない学習ΣiL(xi,yi,w)+C|w|2–Cはトレード