発表資料

ICML読む会資料 (鹿島担当)
教師ナシ の 構造→構造 マッピング
読んだ論文: Discriminative Unsupervised Learning of Structured Predictors
Linli Xu (U. Waterloo) , … , Dale Schuurmans (U. Alberta),
In proceeding of ICML2006
この論文では、教師ナシで、構造→構造のマッピングを学習する方法が紹介され
ます
 この論文の鑑賞ポイント


「構造→構造マッピング」は最近流行っている話題です。 でも普通、教師アリです。
じゃあ、教師ナシにするって一体どういうこと!?
 このお話の流れ



背景: 構造→構造マッピング問題
問題設定: 教師ナシ構造→構造マッピング問題
アプローチ: 「教師ナシSVM」の一般化による解法の提案
構造→構造マッピング問題は、構造データを入力として、構造データを出力する関
数を求める問題です
 品詞付け

単語列→品詞列のマッピング
入力
the
man
saw
glasses
DT
NN
VBD
NN
x
出力
y
 構文解析

出力
単語列→構文解析木のマッピング
y
入力
x
A
B
G
A
C
D
E
F
G E D
構造→構造マッピング問題は、分類問題の一般化になっています
 構造→構造マッピング問題は、多クラス分類問題の、クラスがものすごくたくさんある版
入力 X
出力 Y
2クラス
分類
構造
データ
{+1, -1}
多クラス
分類
構造
データ
{1,...,K}
構造
マッピング
構造
データ
構造
データ
この論文は、著者が以前より提案している教師ナシ分類の手法を、自然に一般化
したものです
コレとコレが分かれ
世の中の流れ
ば大体わかる
一般化
一般化
<
対応
対応
多クラス分類問題
一般化
一般化
教師ナシ
2クラス分類法
[NIPS04]
<
構造マッピング問題
対応
<
2クラス分類問題
教師ナシ
多クラス分類法
[AAAI05]
著者の世界
<
教師ナシ
構造マッピング法
[ICML06]
まず、近年の教師アリ分類学習の発展について復習します
世の中の流れ
一般化
一般化
<
対応
対応
多クラス分類問題
一般化
一般化
教師ナシ
2クラス分類法
[NIPS04]
<
構造マッピング問題
対応
<
2クラス分類問題
教師ナシ
多クラス分類法
[AAAI05]
著者の世界
<
教師ナシ
構造マッピング法
[ICML06]
教師アリ2クラス分類問題 を解くSVMは、部分構造を使った特徴空間において、
正例と負例とのマージンを最大化するように学習します
 構造をもったデータは、含まれる部分構造を使った特徴空間中の点として表現される
 この空間で正例と負例を最もうまく分ける(=マージン最大の)平面をみつける
部分構造を使った特徴空間表現
the
man
the
+1
+1
-1
+1
-1
-1
-1
man
saw
man
saw
glasses
教師アリ多クラス分類問題 を解くSVMは、部分構造とクラスを使った特徴空間において、
正解と不正解とのマージンを最大化するように学習します
 構造をもったデータとクラスラベルの組は、含まれる部分構造とクラスラベルを使った特徴
空間中の点として表現される
 この空間で正解と不正解を最もうまく分ける(=マージン最大の)平面をみつける
the
man
&
1
正
解
部分構造とクラスを使った特徴空間表現
1
不
正
the
man
saw
不
正
解
不
不
glasses
2
the
不
man
saw
&
1
man
saw
glasses
教師アリ構造マッピング問題 を解くSVMは、入力と出力の部分構造を使った特徴空間において、
正解と不正解とのマージンを最大化するように学習します
 構造をもったデータとクラスラベルの組は、含まれる部分構造とクラスラベルを使った特徴
空間中の点として表現される
 この空間で正解と不正解を最もうまく分ける(=マージン最大の)平面をみつける
the
&
DT
man
正
解
入力と出力の部分構造を使った特徴空間表現
NN
不
正
DT
DT
VBD
NN
the
man
saw
glasses
NN
VBD
NN
the
man
saw
glasses
不
不
不
正
解
DT
不
man
saw
&
NN
VBD
近年著者が提案している教師ナシ分類法の発展に沿って、
この論文の成果をみていきます
世の中の流れ
一般化
一般化
<
対応
対応
多クラス分類問題
一般化
一般化
教師ナシ
2クラス分類法
[NIPS04]
<
構造マッピング問題
対応
<
2クラス分類問題
教師ナシ
多クラス分類法
[AAAI05]
著者の世界
<
教師ナシ
構造マッピング法
[ICML06]
近年著者が提案している教師ナシ分類法の発展に沿って、
この論文の成果をみていきます
世の中の流れ
一般化
一般化
<
対応
対応
多クラス分類問題
一般化
一般化
教師ナシ
2クラス分類法
[NIPS04]
<
構造マッピング問題
対応
<
2クラス分類問題
教師ナシ
多クラス分類法
[AAAI05]
著者の世界
<
教師ナシ
構造マッピング法
[ICML06]
教師ナシ2クラス分類問題 を解くSVMは、全ての正例と負例の割り当ての中から
正例と負例とのマージンを最大化するように学習します
 ただし、正例と負例が大体半々になるような制約のもとで
部分構造を使った特徴空間表現
the
man
the
+1
+1
-1
+1
-1
-1
-1
man
saw
man
saw
glasses
教師ナシ多クラス分類問題 を解くSVMは、全ての正解と不正解の割り当ての中から
正解と不正解とのマージンを最大化するように学習します
 ただし、各クラスが大体 1/(クラス数) になるような制約のもとで
the
man
&
1
正解って
ことで
部分構造とクラスを使った特徴空間表現
1
不
正
the
man
saw
不正解っ
てことで
不
不
glasses
2
the
不
man
saw
&
1
man
saw
glasses
教師ナシ構造マッピング を解くSVMは、全ての正解と不正解の割り当ての中から
正解と不正解とのマージンを最大化するように学習します
 ただし、各部分構造の使用数が均等になるような制約のもとで
the
&
DT
man
正解って
ことで
入力と出力の部分構造を使った特徴空間表現
NN
不
正
DT
DT
VBD
NN
the
man
saw
glasses
NN
VBD
NN
the
man
saw
glasses
不
不
不正解っ
てことで
DT
不
man
saw
&
NN
VBD
教師アリSVMは2次計画であるのに対し、
教師ナシSVMは半正定値計画(SDP)になります
 2値分類の場合でみてみる
 パラメータ w だけでなく、yについても最適化する
primal
dual
 クラスが均等になるような制約をいれる
primal
 SDPに落ちる
dual
性能はよさそうですが、たぶん、かなり遅いです
 実験に使っているデータ小さい!→ たぶんムチャクチャ遅い!


synthetic: 2状態2値のHMMから長さ8の配列を10個
protein: 長さ10のアミノ酸列を10個
提
案
手
法
既存
手法
小さいほうが性能イイ
この論文では、教師ナシで、構造→構造のマッピングを学習する方法が紹介され
ました
 この論文の鑑賞ポイント


「構造→構造マッピング」は最近流行っている話題です。 でも普通、教師アリです。
じゃあ、教師ナシにするって一体どういうこと!?
 このお話の流れ



背景: 構造→構造マッピング問題
問題設定: 教師ナシ構造→構造マッピング問題
アプローチ: 「教師ナシSVM」の一般化による解法の提案
考えうるネタ: 高速化 「パーセプトロン化」できるかな?
 SVM (2次計画) 遅い → パーセプトロン (オンライン逐次)で速くする
 SDP遅すぎ → パーセプトロン化など逐次学習化できれば速くなるかも?