DMLA 2008-06-17 小町守 半教師あり学習 チュートリアル

本チュートリアルのねらい （自分の博士論文に関係のある）半教師あり学習についての紹介 半教師あり学習使ってみようという人を増やす 長所と短所のサーベイ 半教師あり学習使ってみようという人を増やす

イントロダクション 半教師あり学習（Semi-supervised learning） ラベルありデータとラベルなしデータの両方を利用した学習法全般 ラベルありデータ: 正解が付与されているデータ ラベルなしデータ: 正解が付与されていないデータ 種類 クラスタリング、分類、回帰、ランキング、…

本チュートリアルで想定するNLPタスク 固有表現抽出タスク 新たなパターン獲得 新しい NE シード NE 新しい NE 新しい NE 大規模データ 大規模データ 大規模データ 新たなパターン獲得

本チュートリアルで想定するNLPタスク 語義曖昧性解消タスク 分類器 シード 用例 大規模データ 大規模データ 大規模データ 新たな用例獲得

半教師あり学習の目的 ラベルありデータとラベルなしデータが存在 ラベルなしデータを使って性能向上したい （前提） ラベルなしデータは大量に獲得可能 ラベルありデータは作成にコストがかかる 人手でつけるのは面倒 専門知識が必要 アノテーションツールが使いにくい（などなど……）

半教師あり学習が有効な場合(1) 前提 インスタンスがたくさんあるところに分離平面を引きたくない

半教師あり学習が有効な場合(2) 前提: データのよい生成モデルがある Gaussian Mixture のパラメータは EM で求めることができる クラスのラベルは正解付きデータから推定

2つのアルゴリズム 分類器に基づく手法 データに基づく手法 初期分類器から始め、反復的に分類器を洗練 Self-training/co-training データに基づく手法 データに備わっている構造を発見し、分類器を構築する際に用いる グラフベースの手法

分類器の予測結果に基づく手法 仮定 アルゴリズム 分類器の出した確信度の高い予測結果は正しい ラベルありデータから分類器を教師あり学習 ラベルなしデータのラベルを予測 ラベルなしデータと予測結果（擬似的な正解ラベル）をラベルありデータに追加 繰り返し

Self-training Yarowsky 1995 語義曖昧性解消（インスタンスは語義） One sense per discourse の制約により新しいパターン獲得

実際の学習法 ラベルなしデータのラベルを予測 予測ラベルを正解と見なしてラベルありデータに追加 閾値以上の確信度の予測結果のみを追加 確信度の上位k個の予測結果のみを追加 重み付きで全ての予測結果を追加 ラベルありデータ+予測ラベル付きラベルなしデータで分類器を教師あり学習

ブートストラップ（固有表現抽出） パターン抽出とインスタンス獲得を交互に繰り返して少量のシードインスタンスを反復的に増やす インスタンス 2018/9/22 ブートストラップ（固有表現抽出） パターン抽出とインスタンス獲得を交互に繰り返して少量のシードインスタンスを反復的に増やす インスタンス コーパス パターン MacBook Air アップルMacBook Air注文 アップル#注文 iPod touch アップルiPod touch注文 #:インスタンス が入るスロット MacBook Pro アップルMacBook Pro注文

特長と問題点 特長 問題点 複雑な仮定が不要 ラッパーとして用いることができる NLP で実際よく使われている 既存の分類器との親和性が高い NLP で実際よく使われている 問題点 真の分布に基づく分類器の実現は困難 初期に間違えると間違いが増幅される 収束条件がよく分からない

Self-training の問題点(cont.) 高次元スパース空間（素性の数が膨大で、訓練事例にはほとんど現れない場合）には不向き NLP では典型的には高次元スパース空間 本質的な性能の向上は見込めない 分類器自身が知っていることを再学習しても情報量は増えない （Cf. 能動学習 active learning） ラベルなしデータの量を増やしても性能が向上しないことが多い

Co-training (Multiview Learning) 仮定 素性分割が可能 分割した素性それぞれで十分な分類器が学習可能 分割した素性が条件付き独立 アルゴリズム 分割した素性から2つの学習器を学習 ラベルなしデータをそれぞれの分類器で分類 分類器1の確信度上位k個を分類器2のラベルありデータに追加 分類器2の確信度上位k個を分類器1のラベルありデータに追加 繰り返し

CO-training Blum & Mitchell 1998 ウェブページのラベル付け View1 の分類器の予測ラベルを View2 の分類器の訓練事例に、逆も同様にして反復 View 1 による分類器 View 2 による分類器 View1 ページにリンクしているハイパーリンクのテキスト View2 ウェブページのテキストそのもの

Co-training の特長と問題点 特長 問題点 Self-training より間違いに強い タスクの特徴をうまく捉えた使い方をした場合、ラベルありデータの数が少ない場合は性能が向上したという報告あり 問題点 自然に素性を分割できる場合のみ有効 全素性を使って教師あり学習したほうがよい性能を得られる場合が多い（ランダムに素性を分割する話もある）

Co-training の兄弟 Co-EM Multiview Learning 上位k個だけでなく全部の結果を追加する 各分類器が確率的にラベルなしデータを予測 ラベルなしデータと予測結果を重みP(y|x)で追加 Multiview Learning 素性分割なし 複数のタイプの分類器を学習 ラベルなしデータを全ての分類器で予測 ラベルの多数決の結果を追加

EM (Dempster et al, 1977) ラベルありデータとラベルなしデータの対数尤度を最大化 θ π x y Ll:ラベルありデータの対数尤度 Lu: ラベルなしデータの対数尤度 θ π x y

Stable Mixing of Information (Corduneanu 2002) ラベルありデータとラベルなしデータの対数尤度を線形補間 EM で最適化することができる 最適なλの値を求めるためのステップが必要

EMの特長と問題点 特長 問題点 ラベルなしデータを自然に組み込むことができる テキスト分類タスクではよい性能を示している 適切な生成モデルを使わないとよい性能は出ない パラメータを決めるステップが入る 少量のラベルありデータのときは性能向上するが大量にラベルありデータがあるときは性能が悪化するという報告(Merialdo, 1994)もある

類似度グラフを用いる手法 仮定 前提 アイデア 類似サンプルは同一ラベルを持つ傾向にある サンプル間の類似度を定義可能 事前知識, kNN アイデア 類似度グラフに対してグラフベースのアルゴリズムを用いてクラスタリング

類似度グラフによる手法の直感的解釈 Overlap がない状態でもpropagationでうまくいく 隣接するノードは類似のラベルを持つ（図は Zhu 2007 より引用）

類似度グラフによるラベルなしデータの利用

グラフによる手法の特長と問題点 特長 問題点 グラフ理論など数学的な背景が確立 よいグラフが得られていればよい性能が得られる 適切なグラフ構造（やエッジの重み）を得ることが難しい 計算量が相対的に大きい Transductive な方法が多い Transductive: テスト事例が既知のときの学習 Inductive: 未知データを含む全データを対象

まとめ Self/co-training グラフに基づく手法 教師あり学習との親和性が高いのでよく使われてきた うまくいったりいかなかったり、タスクに応じて使わないといけない グラフに基づく手法 NLP タスクにおけるよいグラフは自明でない 計算量が相対的に大きい

資料 言語処理学会第14回年次大会チュートリアル: 半教師あり学習による分類法:—現状と自然言語処理への適用—, 鈴木潤・藤野昭典 ICML 2007 Tutorial: Semi-supervised Learning, Xiaojin Zhu. NAACL 2006 Tutorial: Inductive Semi-supervised Learning with Applicability to NLP, A. Sarkar and G. Haffari.