DMLA 2008-06-17 小町守半教師あり学習チュートリアル本チュートリアルのねらい  （自分の博士論文に関係のある）半教師あり学習についての紹介  長所と短所のサーベイ  半教師あり学習使ってみようという人を増やす 2 イントロダクション  半教師あり学習（Semi-supervised learning）  ラベルありデータとラベルなしデータの両方を利用した学習法全般  ラベルありデータ: 正解が付与されているデータ  ラベルなしデータ: 正解が付与されていないデータ  種類  クラスタリング、分類、回帰、ランキング、… 3 本チュートリアルで想定するNLPタスク  固有表現抽出タスク新しい新しい NE 新しい NE NE シード NE シードパターン大規模データ大規模データ大規模データ新たなパターン獲得 4 本チュートリアルで想定するNLPタスク  語義曖昧性解消タスクシード用例分類器大規模データ大規模データ大規模データ新たな用例獲得 5 半教師あり学習の目的ラベルありデータとラベルなしデータが存在  ラベルなしデータを使って性能向上したい   （前提）  ラベルなしデータは大量に獲得可能  ラベルありデータは作成にコストがかかる人手でつけるのは面倒  専門知識が必要  アノテーションツールが使いにくい（などなど……）  6 半教師あり学習が有効な場合(1)  前提  インスタンスがたくさんあるところに分離平面を引きたくない 7 半教師あり学習が有効な場合(2) 前提: データのよい生成モデルがある Gaussian Mixture のパラメータは EM で求めることができるクラスのラベルは正解付きデータから推定 8 2つのアルゴリズム  分類器に基づく手法  初期分類器から始め、反復的に分類器を洗練  Self-training/co-training  データに基づく手法  データに備わっている構造を発見し、分類器を構築する際に用いる  グラフベースの手法 9 分類器の予測結果に基づく手法 • 仮定 – • 分類器の出した確信度の高い予測結果は正しいアルゴリズムラベルありデータから分類器を教師あり学習 2. ラベルなしデータのラベルを予測 3. ラベルなしデータと予測結果（擬似的な正解ラベル）をラベルありデータに追加 4. 繰り返し 1. 10 SELF-TRAINING  Yarowsky 1995  語義曖昧性解消（インスタンスは語義） One sense per discourse の制約により新しいパターン獲得 11 実際の学習法ラベルなしデータのラベルを予測  予測ラベルを正解と見なしてラベルありデータに追加   閾値以上の確信度の予測結果のみを追加  確信度の上位k個の予測結果のみを追加  重み付きで全ての予測結果を追加  ラベルありデータ+予測ラベル付きラベルなしデータで分類器を教師あり学習 12 2015/9/30 ブートストラップ（固有表現抽出）  パターン抽出とインスタンス獲得を交互に繰り返して少量のシードインスタンスを反復的に増やすインスタンス MacBook Air コーパスパターンアップルMacBook Air注文アップル#注文 iPod touch アップルiPod touch注文 MacBook Pro アップルMacBook Pro注文 #:インスタンスが入るスロット 13 特長と問題点  特長  複雑な仮定が不要  ラッパーとして用いることができる  既存の分類器との親和性が高い  NLP  で実際よく使われている問題点  真の分布に基づく分類器の実現は困難  初期に間違えると間違いが増幅される  収束条件がよく分からない 14 SELF-TRAINING の問題点(CONT.)  高次元スパース空間（素性の数が膨大で、訓練事例にはほとんど現れない場合）には不向き  NLP  では典型的には高次元スパース空間本質的な性能の向上は見込めない  分類器自身が知っていることを再学習しても情報量は増えない  （Cf. 能動学習 active learning）  ラベルなしデータの量を増やしても性能が向上しないことが多い 15 CO-TRAINING (MULTIVIEW LEARNING) • 仮定 – – – • 素性分割が可能分割した素性それぞれで十分な分類器が学習可能分割した素性が条件付き独立アルゴリズム – – – – – 分割した素性から2つの学習器を学習ラベルなしデータをそれぞれの分類器で分類分類器1の確信度上位k個を分類器2のラベルありデータに追加分類器2の確信度上位k個を分類器1のラベルありデータに追加繰り返し 16 CO-TRAINING  Blum & Mitchell 1998  ウェブページのラベル付け View 1 による分類器 View1 の分類器の予測ラベルを View2 の分類器の訓練事例に、逆も同様にして反復 View 2 による分類器 View1 ページにリンクしているハイパーリンクのテキスト View2 ウェブページのテキストそのもの 17 CO-TRAINING の特長と問題点  特長  Self-training より間違いに強い  タスクの特徴をうまく捉えた使い方をした場合、ラベルありデータの数が少ない場合は性能が向上したという報告あり  問題点  自然に素性を分割できる場合のみ有効  全素性を使って教師あり学習したほうがよい性能を得られる場合が多い（ランダムに素性を分割する話もある） 18 CO-TRAINING の兄弟 • Co-EM – – – • 上位k個だけでなく全部の結果を追加する各分類器が確率的にラベルなしデータを予測ラベルなしデータと予測結果を重みP(y|x)で追加 Multiview Learning – – – – 素性分割なし複数のタイプの分類器を学習ラベルなしデータを全ての分類器で予測ラベルの多数決の結果を追加 19 EM (DEMPSTER ET AL, 1977)  ラベルありデータとラベルなしデータの対数尤度を最大化 log(P(y i |  )P(xi | yi,)) log(P(y |  )P(x j | y,)) i j Ll:ラベルありデータの対数尤度  y Lu: ラベルなしデータの対数尤度 θ π x y 20 STABLE MIXING OF INFORMATION (CORDUNEANU 2002)  ラベルありデータとラベルなしデータの対数尤度を線形補間 (1  )Ll  Lu EM で最適化することができる  最適なλの値を求めるためのステップが必要   21 EMの特長と問題点  特長  ラベルなしデータを自然に組み込むことができる  テキスト分類タスクではよい性能を示している  問題点  適切な生成モデルを使わないとよい性能は出ない  パラメータを決めるステップが入る  少量のラベルありデータのときは性能向上するが大量にラベルありデータがあるときは性能が悪化するという報告(Merialdo, 1994)もある 22 類似度グラフを用いる手法  仮定  類似サンプルは同一ラベルを持つ傾向にある  前提  サンプル間の類似度を定義可能  事前知識,  kNN アイデア  類似度グラフに対してグラフベースのアルゴリズムを用いてクラスタリング 23 類似度グラフによる手法の直感的解釈  Overlap がない状態でもpropagationでうまくいく  隣接するノードは類似のラベルを持つ（図は Zhu 2007 より引用） 24 類似度グラフによるラベルなしデータの利用 25 グラフによる手法の特長と問題点 • 特長 – – • グラフ理論など数学的な背景が確立よいグラフが得られていればよい性能が得られる問題点 – – – 適切なグラフ構造（やエッジの重み）を得ることが難しい計算量が相対的に大きい Transductive な方法が多い • • Transductive: テスト事例が既知のときの学習 Inductive: 未知データを含む全データを対象 26 まとめ  Self/co-training  教師あり学習との親和性が高いのでよく使われてきた  うまくいったりいかなかったり、タスクに応じて使わないといけない  グラフに基づく手法  NLP タスクにおけるよいグラフは自明でない  計算量が相対的に大きい 27 資料言語処理学会第14回年次大会チュートリアル: 半教師あり学習による分類法:—現状と自然言語処理への適用—, 鈴木潤・藤野昭典  ICML 2007 Tutorial: Semi-supervised Learning, Xiaojin Zhu.  NAACL 2006 Tutorial: Inductive Semisupervised Learning with Applicability to NLP, A. Sarkar and G. Haffari.  28