ICML読む会資料 （鹿島担当） 教師ナシ の 構造→構造 マッピング 読んだ論文： Discriminative Unsupervised Learning of Structured Predictors Linli Xu (U. Waterloo) , … , Dale Schuurmans.

Presentation on theme: "ICML読む会資料 （鹿島担当） 教師ナシ の 構造→構造 マッピング 読んだ論文： Discriminative Unsupervised Learning of Structured Predictors Linli Xu (U. Waterloo) , … , Dale Schuurmans."— Presentation transcript:

1 ICML読む会資料 （鹿島担当） 教師ナシ の 構造→構造 マッピング 読んだ論文： Discriminative Unsupervised Learning of Structured Predictors Linli Xu (U. Waterloo) , … , Dale Schuurmans (U. Alberta), In proceeding of ICML2006

2 この論文では、教師ナシで、構造→構造のマッピングを学習する方法が紹介されます
この論文の鑑賞ポイント 「構造→構造マッピング」は最近流行っている話題です。 でも普通、教師アリです。 じゃあ、教師ナシにするって一体どういうこと！？ このお話の流れ 背景： 構造→構造マッピング問題 問題設定： 教師ナシ構造→構造マッピング問題 アプローチ： 「教師ナシSVM」の一般化による解法の提案

3 構造→構造マッピング問題は、構造データを入力として、構造データを出力する関数を求める問題です
品詞付け 単語列→品詞列のマッピング 構文解析 単語列→構文解析木のマッピング

4 構造→構造マッピング問題は、分類問題の一般化になっています
構造→構造マッピング問題は、多クラス分類問題の、クラスがものすごくたくさんある版 入力 X 出力 Y ２クラス 分類 構造 データ {+1, -1} 多クラス 分類 {1,...,K} 構造 マッピング 構造 データ

5 この論文は、著者が以前より提案している教師ナシ分類の手法を、自然に一般化したものです
コレとコレが分かれば大体わかる 世の中の流れ 一般化 ＜ 一般化 ＜ ２クラス分類問題 多クラス分類問題 構造マッピング問題 対応 対応 対応 一般化 ＜ 一般化 ＜ 教師ナシ ２クラス分類法 教師ナシ 多クラス分類法 教師ナシ 構造マッピング法 [NIPS04] [AAAI05] [ICML06] 著者の世界

6 まず、近年の教師アリ分類学習の発展について復習します
世の中の流れ 一般化 ＜ 一般化 ＜ ２クラス分類問題 多クラス分類問題 構造マッピング問題 対応 対応 対応 一般化 ＜ 一般化 ＜ 教師ナシ ２クラス分類法 教師ナシ 多クラス分類法 教師ナシ 構造マッピング法 [NIPS04] [AAAI05] [ICML06] 著者の世界

7 教師アリ２クラス分類問題 を解くSVMは、部分構造を使った特徴空間において、正例と負例とのマージンを最大化するように学習します
構造をもったデータは、含まれる部分構造を使った特徴空間中の点として表現される この空間で正例と負例を最もうまく分ける（＝マージン最大の）平面をみつける 部分構造を使った特徴空間表現 +1 +1 -1 +1 -1 マージン -1 -1

8 教師アリ多クラス分類問題 を解くSVMは、部分構造とクラスを使った特徴空間において、正解と不正解とのマージンを最大化するように学習します
構造をもったデータとクラスラベルの組は、含まれる部分構造とクラスラベルを使った特徴空間中の点として表現される この空間で正解と不正解を最もうまく分ける（＝マージン最大の）平面をみつける 正解 部分構造とクラスを使った特徴空間表現 ＆ 不 正 不正解 不 不 マージン 不 ＆

9 教師アリ構造マッピング問題 を解くSVMは、入力と出力の部分構造を使った特徴空間において、 正解と不正解とのマージンを最大化するように学習します
構造をもったデータとクラスラベルの組は、含まれる部分構造とクラスラベルを使った特徴空間中の点として表現される この空間で正解と不正解を最もうまく分ける（＝マージン最大の）平面をみつける 正解 ＆ 入力と出力の部分構造を使った特徴空間表現 不 正 不 不 マージン 不正解 不 ＆

10 近年著者が提案している教師ナシ分類法の発展に沿って、 この論文の成果をみていきます
世の中の流れ 一般化 ＜ 一般化 ＜ ２クラス分類問題 多クラス分類問題 構造マッピング問題 対応 対応 対応 一般化 ＜ 一般化 ＜ 教師ナシ ２クラス分類法 教師ナシ 多クラス分類法 教師ナシ 構造マッピング法 [NIPS04] [AAAI05] [ICML06] 著者の世界

11 近年著者が提案している教師ナシ分類法の発展に沿って、 この論文の成果をみていきます
世の中の流れ 一般化 ＜ 一般化 ＜ ２クラス分類問題 多クラス分類問題 構造マッピング問題 対応 対応 対応 一般化 ＜ 一般化 ＜ 教師ナシ ２クラス分類法 教師ナシ 多クラス分類法 教師ナシ 構造マッピング法 [NIPS04] [AAAI05] [ICML06] 著者の世界

12 教師ナシ２クラス分類問題 を解くSVMは、全ての正例と負例の割り当ての中から正例と負例とのマージンを最大化するように学習します
ただし、正例と負例が大体半々になるような制約のもとで 部分構造を使った特徴空間表現 マージン最大 +1 +1 -1 +1 -1 -1 -1

13 教師ナシ多クラス分類問題 を解くSVMは、全ての正解と不正解の割り当ての中から正解と不正解とのマージンを最大化するように学習します
ただし、各クラスが大体 1/（クラス数） になるような制約のもとで マージン最大 正解ってことで 部分構造とクラスを使った特徴空間表現 ＆ 正 不 不正解ってことで ＆

14 教師ナシ構造マッピング を解くSVMは、全ての正解と不正解の割り当ての中から正解と不正解とのマージンを最大化するように学習します
ただし、各部分構造の使用数が均等になるような制約のもとで マージン最大 正解ってことで ＆ 入力と出力の部分構造を使った特徴空間表現 不 正 不 不 不 不正解ってことで ＆

15 教師アリSVMは２次計画であるのに対し、 教師ナシSVMは半正定値計画（SDP）になります
２値分類の場合でみてみる パラメータ ｗ だけでなく、ｙについても最適化する クラスが均等になるような制約をいれる SDPに落ちる primal dual dual primal

16 性能はよさそうですが、たぶん、かなり遅いです
実験に使っているデータ小さい！→ たぶんムチャクチャ遅い！ synthetic: 2状態2値のHMMから長さ8の配列を10個 protein: 長さ10のアミノ酸列を10個 提案 手法 既存 手法 小さいほうが性能イイ

17 この論文では、教師ナシで、構造→構造のマッピングを学習する方法が紹介されました
この論文の鑑賞ポイント 「構造→構造マッピング」は最近流行っている話題です。 でも普通、教師アリです。 じゃあ、教師ナシにするって一体どういうこと！？ このお話の流れ 背景： 構造→構造マッピング問題 問題設定： 教師ナシ構造→構造マッピング問題 アプローチ： 「教師ナシSVM」の一般化による解法の提案

18 考えうるネタ： 高速化 「パーセプトロン化」できるかな？
SVM （２次計画） 遅い → パーセプトロン （オンライン逐次）で速くする SDP遅すぎ → パーセプトロン化など逐次学習化できれば速くなるかも？