《{机械公司管理}机械学习自然言语処理ー》由会员分享，可在线阅读，更多相关《{机械公司管理}机械学习自然言语処理ー（72页珍藏版）》请在金锄头文库上搜索。
1、機械学習自然言語処理PerceptronCRF,岡野原大輔 東京大学Preferred Infrastructure,2008 8/3PFI本郷,目次,自然言語処理 紹介 機械学習導入 学習 (最大法) 過学習/正則化 多分類 系列分類 (CRF, Structured Perceptron),眠,自然言語処理 (1/2),言語情報処理 言語研究対比自然言語 世界最初出現頃自動翻訳試。中歴史長分野 近年的成功, Google 非常幅広分野接触、境界領域 処理手法 = 言語学, 数学, 統計学, 機械学習, , 構造, 物理 処理対象 = 情報検索, ,音声情報, 言語絡何,自然言語処理 (2/
2、2),分野例 構文解析（係受解析） 意味解析, SRL 機械翻訳（統計的機械翻訳, ） 情報検索 固有表現抽出、文書分類、単語、 有名学会、 Computational Linguistic, ACL, EMNLP, CoLing, NAACL, EACL, IJCNLP, 自然言語処理学会http:/hillbig.cocolog- ACL anthology,自然言語処理機械学習使,自然言語処理編,人手書処理 例：排除 if (s = /H|奥様|楽/) then 単純強力手法昔現在活躍 現時点日英機械翻訳方精度良,自然言語処理編,長所 内部処理分 人手調整可能 頑張頑張精度上 短所： 大
3、(最初精度伸、伸、）、 新弱、 専門知識必要（職人芸）、 一貫性無（時間、人変）,自然言語処理機械学習編,人手書代正解訓練用意、正解導導出 自然言語処理場合、単語品詞出現利用 候補集合決，中効学習自動探 作,機械学習前 vs 機械学習,何問題解場合、機械学習使検討 訓練得 対 書 方良場合多 問題、要求精度、問題対知識吟味 多素性形機械学習反映、複雑場合人（文法変換数千行perl）,表現,多自然言語情報疎高次元扱 文書BOW表現、V単語種類数時，各単語0V-1順番番号振 i番目単語出現Vi=1V次元扱,0: Best 1: Drug 2: Congratuation 3: Flower,Dru
4、g Best Flower,DrugCongratuation,各値決使素性（、特徴）、高次元素性（特徴）呼。,線形識別器,分類問題：入力x値(y=+1,-1)分類 例：文書(+1)or以外(-1)分類 S(x)0 y=+1 S(x)0、xi出現度合増（|wi|大大効） w求,重w求,訓練(xi,yi) (yi=1 or -1)正分類w求 全i yiwTxi0 訓練分類、未知分類（期待。真面目汎化性能 議論）,学習学習,学習 訓練1例見w更新 長所：全部訓練例良。速（一般訓練数線形計算量） 短所：比適当、訓練例順番偏大場合精度不安定 学習 訓練全部見w求 長所：精度良、理論的保証強(汎化性能）
5、 短所：重場合多,学習 Rosenblatt 57,w = 0,0,.0初期化 loop (xi,yi) 訓練 s := yiwTxi /wTxi=現在予測 if (s 0) / 現在予測外 w := w + yixi / w + yixi , 01場合 endif end,学習,更新後重 w := w + yixi 使、一度間違訓練例（xi,yi)分類 wT xi =(w + yixi)T xi =wTxi + yixiTxi,先程間違予測結果,常正,w正解出更新,Perceptron収束定理Block 62Novikoff 62,Q.直前訓練例分類更新、全訓練例分類？ A. 訓練例線形分離
6、可能 定理：訓練 (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 k22 (R/)2 k,wk間違訓練例値負,Perceptron補足,線形識別可能無場合使批判Minsky 69 場合xor 廃最近復活！ 使 Y.
7、 Freund 98 後述構造学習、非常強力学習手法分Collins 02, Daume 06 自然言語処理分野多分野再度、使,+,+,-,-,頭疲休憩,続OLL実践編,OLL使実際分類,OLL初様学習手法 wget cd oll-0.01; ./configure; make; (make install) oll_train P trainfile modelfile (学習、学習結果modelfile保存） oll_test testfile modelfile （学習結果modelfile読込、testfile分類）,訓練,各行1訓練例対応 最初正例+1,負例-1書、後素性番号：値列並
8、 +1 0:1.0 201:2.2 744:-0.3 15:3.0 . -1 47:2.0 66:0.1 733:1.0 500:1.0 +1 3:1.0 201:2.2 300:-0.3 15:0.3,文書分類作（C+）,map str2id; / 文字列素性番号連想配列vector id2str;/ 素性番号文字列逆引 int getID(const string / 新iD返 ,int doc2fv(const string ,区切済素性作,学習編,学習編,全部真面目精度高 f0/1：0/1損失関数 f0/1(a) = 1 a0, = 0 以外 if0/1(yiwTxi) 最小化w求,1
9、,0,ywTx,0/1,重w求(続)学習編,if0/1(yiwTxi)最小w探 数値最適化問題 最適化問題実難！ 関数f0/1(a)微分不可能凸（極小解複数存在）,wi,w1次元,if0/1(yiwTxi),極小解,探値,様損失関数f0/1近似,凸（穴無、Hessian行列正定値）微分可能（滑）関数,緑：SVM (hinge-loss) 青：MaxEnt (log loss) 紫：Ada Boost (exp-loss),線形識別器,訓練用意 (xi,yi) (yi-1,+1) 学習：損失関数L使i L(xi,yi,w)最小w探 推定：分類xnew対s=wTxnew求 s0 y=1, s0 y
10、=-1推定 非常多分類器属 SVM, 最大法、NB、Adaboost,過学習/正則化,過学習,訓練分類、分類場合 大抵、訓練場合多 訓練性質違場合別話,回帰例： 青2次曲線 赤8次曲線 赤全点通（）,正則化,過学習防w与 絶対値大wi与 L2 |w|2=w12+w22+. wm2 L1 |w| =|w1|+|w2|+|wm| 実二差生（今回話） 訓練例正分類過学習学習 i L(xi,yi,w)+C|w|2 C C大過学習訓練fit、C小訓練fit過学習危険性 最適C別利用推定、推定,線形識別器（改）,訓練用意(xi,yi) (yi=1 or -1) 学習：損失関数L使i L(xi,yi,w)+
11、C|w|2最小w探 推定：分類xnew対s=wTxnew求 s0 y=1, s0 y=-1推定,正則化,出力確率値出場合,確率 y1確率値？ 確信度後処理使 正規化 確率値必要条件 出力値正実数（条件1 ） 可能出力値確立足合1 （条件2）,出力確率値出場合 (続) Logistic回帰,条件1満wTxexp入 条件2満正規化 形確率Logistic回帰呼（最大一致）,最大（後読）,先程強引導出、別意味 各素性関符号付期待値fk=iyixik/N x,y上確率分布p(x,y)各素性期待値一致分布（ x,yp(x,y)log p(x,y) dx dy)最大確率分布先程最尤推定結果一致,Logis
12、tic回帰学習,訓練生成確率最大w求,log loss損失関数！先程見,多分類,多分類,x,+1,-1,入力,出力,例：分類,？,x,1,2,入力,出力,？,k,例：文書分類,難,多分類,入力x 出力 1,2,m 重w種類数分用意 w1 wm wTyx 一番大y推定結果 argmaxywTyx w1 wm求？,学習,w1 wm 全部0,0,0初期化 loop (xi,yi) 訓練 y* := argmaxywyTxi (現在予測結果） if (y* yi) / 現在予想外 wyi := wyi + xi wy*:= wy* xi / 正解 /高罰！ endif end,多版最大,推定argma
13、xy wyTx 行点同 学習訓練生成確率最大w求 後CRF時,系列分類問題（構造出力学習）,系列分類問題,分類対象系列（列） 値分類多値分類系列分類,x,+1,-1,入力,出力,例：分類,？,x,1,2,入力,出力,？,k,例：文書分類（、金融、芸能,x,A,A,A,A,A,C,A,B,E,C,E,E,E,E,E,.,.,例品詞分類、形態素解析固有表現抽出,系列分類問題（続）,分類対象系列（列） 一般k個多値分類分解 多値分類、|Y|k個候補探思 品詞分類 各単語付品詞分類 固有表現抽出 各単語固有表現抽出先頭(B)、途中(I)、以外(O)分類問題解 形態素解析 形態素上選問題 画像認識、時系
14、列解析多分野使,固有表現抽出,：人名地名固有表現文中抜出 訓練用意何 各文字割当問題 B: 固有表現先頭 I : 固有表現途中 O : 固有表現以外,地名抽出問題正解例,系列分類順次適用,前順分類問題独立解 直前分類結果素性利用,既決,分類(B or I or O?),使情報：入力（位置文字京、一前文字東、一後文字市、一前I） HMM違、入力情報全部位置使注意,系列分類、解方,問題点 後情報自由使例：人名抽出様単語直前漢字列人名、前順番見時O判定 HMMViterbi使推定 全候補中最列、動的計画法効率求 MEMM自由素性使,B,I,O,B,I,I,I,B,B,B,O,O,O,各候補上頂点対応
15、、各枝分類結果重,系列問題上最大求問題,0.5,0.4,0.1,0.85,他枝 重 省略,Start,I,O,End,上重O次B選決,Viterbi復号,上最大重動的計画法解 各位置候補数k、系列長N時O(k2N)時間解 各重最大法確率値求特MEMM (Maximum Entropy Markov Model)呼 確率値log重、通常最大重解,MEMM順次適用問題点1. label bias,簡単経路（曖昧性小経路）存在場合選 学習時正解系列周辺考慮、知系列確率値非常不安定,Kudo 04,MEMM順次適用問題点2. length bias,単位等場合（形態素解析）、短経路選,Kudo 04,
16、条件付確率場CRF (Conditional Random Fields),問題部分問題分，一表 但(x,y)、系列y=y1y2yk上全素性足合 o(x)x上定義全系列集合 先程二問題（label bias, length bias)問題自然解消,yx上全！,B,I,O,B,I,I,I,B,B,B,O,O,O,CRF,Start,I,O,End,枝素性(x,i=1,yp=O, yn=B)取出,先程、素性中exp中入,頂点素性(x,i=1,y=I)取出,B,I,O,B,I,I,I,B,B,B,O,O,O,Start,I,O,End,B,I,O,B,I,I,I,B,B,B,O,O,O,Start,I,O,End,CRF,MEMM,青線負例,赤線
