THE UNIVERSITY OF TOKYO

数理情報工学特論第一【機械学習とデータマイニング】
3章：分類③

かしま ひさし鹿島 久嗣（数理 6 研）kashima@mist.i.～

DEPARTMENT OF MATHEMATICAL INFORMATICS

1THE UNIVERSITY OF TOKYO

構造データのモデリング、とくに配列構造のラベリング問
題について学びます

構造データのモデリング

配列データのラベル付け問題



条件付き確率場（CRF）



条件付き確率場における予測

条件付き確率場の事後確率最大化学習
ポイントは「動的計画法」(dynamic programming)

2

THE UNIVERSITY OF TOKYO

構造データのモデリング3

THE UNIVERSITY OF TOKYO様々な応用分野において、配列や木、グラフなどの構造をもったデータが現れる場面があります 様々な分野において、入出力に配列、木、グラフなどの複雑な構造をもったデータを扱う必要がしばしば生じる
ACGC– 自然言語処理： 文、構文木、文書間リンク
DNA– バイオインフォマティクス：DNA、RNA、タンパク質 しかし、これまでに紹介してきた方法で、これら構造データをどのように扱ったらよいかは自明ではないた構文木

 構造データを扱う学習問題は、入力xのもつ構造の種類（配列、木、グラフなど）発足しの別のほか、出力 y における構造の有無にがよっても大別されるで内閣– 出力 y に構造が無い場合
日本– 出力 y に構造がある場合
4

管

THE UNIVERSITY OF TOKYO出力が構造をもたない場合の例
 出力 y に構造が無く、入力 x のみが構造をもっている場合
 出力 y はこれまでに考えてきた回帰や分類などと同じく、1次元（もしくは複数次元）の実数値もしくは離散値をもつ

 応用としては：– HTMLやXMLなどの半構造文書を木もしくはグラフとして表現し文書の構造やレイアウトなどをもとに、文書の性質を予測– DNA配列やタンパク質のアミノ酸配列をもとに、それらの機能を予測– 化合物の分子構造をグラフとして表現し、その化学的性質を予測

5THE UNIVERSITY OF TOKYO出力が構造をもつ場合の例 より複雑な状況としては、出力も構造をもつような場合がある– 一般的には、構造から構造に変換する問題として捉えられる 配列ラベル付け問題（配列構造の各要素に対して出力値を与える）:– 入力 x ：配列構造

x1x2…

xT

– 出力 y ：同じ長さの配列構造

y1y2…

yT

 多くの問題が配列のラベル付け問題として定式化される– 自然言語処理：品詞付けや固有表現抽出など– ﾊﾞｲｵｲﾝﾌｫﾏﾃｨｸｽ：遺伝子発見やタンパク質の2次構造予測など

 入出力の構造は必ずしも同じ種類である必要はない– 自然言語処理：構文解析（配列→木）– ﾊﾞｲｵｲﾝﾌｫﾏﾃｨｸｽ：RNA構造予測（配列→木）6

THE UNIVERSITY OF TOKYO

配列データのラベリング問題

7

THE UNIVERSITY OF TOKYO

配列構造のラベル付け問題とは、入力配列と同じサイズの出力配列を予測する問題です 配列構造のラベル付け問題：出力が構造をもつ一番簡単な場合– 入力：長さTの配列 x = (x1, x2, …, xT)

x1x2…

xT

– 出力（予測）：同じ長さの配列 y = (y1, y2, …, yT)

y1

y2…

yT

 これまでの枠組みでいえば、入力配列 x が与えられたもとでの出力配列 y の条件付き確率 P(y | x) を得るのが目的
 入力配列のそれぞれの要素 xt (t =1,…,T ) に対応する出力配列の要素
yt (t =1,…,T ) を予測するため、配列のラベル付けと呼ばれる
 例えば、品詞付け問題は、文が単語の列として与えられたときに、各単語に対して適切な品詞を割り振る問題– 入力 x ：単語列（各 xt は「私」「は」「走る」などの単語）– 出力 y ：品詞列（各 yt は「名詞」「助詞」「動詞」などの品詞）
8

THE UNIVERSITY OF TOKYO

配列のラベル付け問題は、出力ラベル間の依存関係を考慮するという意味で（多クラス）分類問題の拡張となっています 原理上は、配列のラベル付け問題は、入力配列の要素それぞれについて独立した分類問題として考えることも可能– 文の品詞付けにおいて、ある単語のみ（例えば「私」）を見て、その品詞を予測するならば、これは通常の（多クラス）分類問題
 しかし、多くの場合、独立性の仮定は成り立たない– 上の例では、全体として整合性のある品詞列を予測する必要あり– 「名詞のあとには助詞が続きやすい」等の品詞間の依存関係を考慮し、各品詞でなく品詞「列」としてまとめて予測する必要あり
 配列のラベル付け問題は、通常の分類問題の拡張となっている– 通常の分類問題と同じように訓練データ集合としては N 個の入出力の組 {(x(i), y(i))}i=1N が与えられる– このときx(i)と y(i) はそれぞれ長さT(i)の入力配列と出力配列
9THE UNIVERSITY OF TOKYO

条件付き確率場（CRF）

10THE UNIVERSITY OF TOKYO（配列に対する）条件付き確率場のモデル
 条件付き確率場（Conditional random field; CRF）は、入力 x と出力y が共に構造をもつ条件付き確率分布P(y|x)を表現するモデル
 ここでは、最も簡単なケースとして配列データのラベル付けのためのCRFを考える– 入出力はともに長さTの配列 x = (x1, x2, …, xT) と y = (y1, y2, …, yT)– 出力ラベルの取りうる集合 Σ を Σ ≡ {1,2,…,C}のように定義し、各yt は Σ の要素（ yt ∈ Σ ）とする
 このとき、配列xが与えられたときに、これに同じ長さのラベル列
yt ∈ ΣTを割り当てる確率を：–  (x,y) は入出力配列 x と y の両方を考慮した特徴ベクトル
11THE UNIVERSITY OF TOKYO

条件付き確率場（CRF）は、多クラスロジスティック回帰モデルのある種の拡張になっています CRFのモデルは、前にふれた多クラスロジスティック回帰モデルの別表記と同じ形をしている
 y に含まれるT個のラベルを纏めて1つのクラスだと考えると、全部でCT個のクラスある（さらに、その数は入力の長さ T に依存）
 そのため、多クラスロジスティック回帰モデルの元々の形式でこれを表現しようとすると、クラスによって異なるパラメータベクトルwyを用意する必要があるため、モデルの表現として適当でない
 別形式では、パラメータの数は入出力の両方を考慮した特徴ベクトル (x,y)の次元に等しいので、 (x,y) をうまく設計してやれば、必ずしも指数個のパラメータベクトルを用意する必要は無い
別形式：

12

元々の形式：THE UNIVERSITY OF TOKYO

条件付き確率場（CRF）の特徴ベクトルの定義：
2種類の特徴を用います x と y の両方にまたがるCRFの特徴ベクトル (x,y)はどのように設計すればよいだろうか？
 配列ラベル付けのためのCRFにおいてよく用いられるのは：– 配列中での位置 t における入力 xt と出力yt の組み合わせによる特徴と– ひとつ前の位置におけるラベルyt-1 と現在位置におけるラベルyt の組み合わせによる特徴である

x1
y1
13x2
y2…
…

xt-1
yt-1

xt
yt…
…

xT
yT

THE UNIVERSITY OF TOKYO位置 t における入力 xt と出力yt の組み合わせによる特徴の定義は多クラスロジスティック回帰の別形式のものと同じです 配列中での位置 t における入力 xt と出力yt の組み合わせによる特徴
 ロジスティック回帰の別表現でも用いた入力と出力にまたがる特徴
ベクトルの定義と同様に、各位置 t に対して以下を定義：– d (・)：括弧の中身が成立するなら1を、しないならば0をとる
 各 xt の特徴ベクトルÁ(xt)をD次元とすると、これは DC次元のベク
トル

Á(xt)
yt
14

THE UNIVERSITY OF TOKYO

ひとつ前の位置のラベルyt-1 と現在位置のラベルyt の組み合
わせ特徴は、連続するラベルの組み合わせを用います ひとつ前の位置におけるラベル yt-1 と現在位置におけるラベル yt の組み合わせによる特徴は、隣り合う2つの位置のラベルを各位置 t に対して以下を定義：– これは C2次元のベクトル

xt-1
yt-1
15xtytTHE UNIVERSITY OF TOKYO

2種類の特徴ベクトルを組みあわせ、配列全体で足し合わせたものが配列全体の特徴ベクトルになります 以上の2種類の特徴ベクトルとを並べた：を、位置tにおける特徴ベクトルとする

 そして、これを全ての位置について足し合わせたもの:

が、配列全体に対する特徴ベクトルの定義となる
位置tにおける特徴ベクトル

xt-1
yt-1
16xtytTHE UNIVERSITY OF TOKYO

CRFでは、配列上で隣り合う2つのラベルの組み合わせ特徴によって、ラベル間の依存関係を効率的に捉えています CRFの特徴ベクトルは全体としてCD + C2の長さを持つ
 この特徴ベクトルの構成において特に重要なのは、隣り合う2つの位置のラベルの関係を考慮した特徴である– 各位置の入出力の特徴ベクトルだけでは、位置間の関係を取り入れていないため、各位置で独立に分類問題を解くのと変わりがなくなってしまう– 一方で、長さTの出力ラベル列に含まれるT個のラベルの組み合わせを素朴に捉えてしまうと前述のようにCT個のパラメータベクトル（DCT次元）を考えることになってしまう
 CRFの特徴ベクトルでは、ラベル間の関係を、配列上で隣り合う2つのラベルの関係にのみ限定して考えることによって、ラベル間の依存関係を効率的に捉えている
17

THE UNIVERSITY OF TOKYO補足：端っこの処理
 隣り合う2つのラベルについて定義された特徴の定義において、本来 t =1のときには y0 が定義されている必要がある
 便宜的に、y0はΣのいずれのラベルももたない
つまり、任意のc ∈ Σについてd (y0=c)=0であるものとする
 ただし、自然言語処理など、文中での位置が有用な情報を持っている場合には、y0やyT+1などに、文頭や文の末尾などを示す特殊なラベル（※）を特別に割り当てるという方法をとることもある
x1 x2 … xT
※ y1 y2 … yT ※18
THE UNIVERSITY OF TOKYO

条件付き確率場における予測

19

THE UNIVERSITY OF TOKYO

条件付き確率場（CRF）の予測は、素朴に行おうとすると指数時間かかってしまうので、動的計画法を用います 予測：入力列 x が与えられたときに、最も高い条件付き確率P(y|x)
を与えるを見つけること：

 可能な出力ラベル列 y の候補が CT 個あるため、これを素朴に実行することは計算時間の面で現実的ではない。

 しかし、特徴の定義が隣り合う2つの変数に対してのみ定義されていることを利用すると、動的計画法によってこれを効率的に（具体的にはO(TC)の計算量で）行うことができる

20

THE UNIVERSITY OF TOKYO

予測の式は単純化できます 予測の式： 分母は y に依存しない（すべてのyについて和をとっている）ためy についての最大化を行うにあたって分母は無視しても良い また、分子のexpは単調増加関数であるため、exp(・)の中身を最大化するyがこれを最大化することがわかる。
 従って、最大化問題は 以下のように書いて差支えない さらに条件付き確率場の特徴ベクトルの定義により：21THE UNIVERSITY OF TOKYO

動的計画法を用いるために、新たな量 s¿ を導入します 最大化問題：を再帰によって効率的に解くために、以下の量s¿を定義する

 すると、次が成立する：

ので、sT (yT) がすべての yT ∈ Σ について得られれば最大スコアが得られる

22

THE UNIVERSITY OF TOKYOs¿ について再帰式が成立します ここで先ほど定義したを再帰的に、すなわち s¿(y¿+1) を s¿(y¿) によって表現してみると：

 これを用いて、s¿ (y¿) を ¿ =1,2,…,T について再帰的に計算すること
ですべての yT ∈ Σ について sT (yT) が求まる
 この計算量は各¿についてO(C)であるため、配列全体としてはO(CT)23

THE UNIVERSITY OF TOKYO

最適なラベル列はバックトラックによって求まります 再帰式：

 再帰の各ステップ（¿ =1,2,…,T）において、s¿ (y¿) を再帰計算するときに、maxを与える y¿-1 を覚えておく sT (yT)がすべての yT ∈ Σ について求まり、最適な yT がわかったら、覚えていた最適な yT-1 を取り出し…と逆向きに辿る（バックトラック）することで、最適なラベル列が求まる

24

THE UNIVERSITY OF TOKYO

条件付き確率場の事後確率最大化

25

THE UNIVERSITY OF TOKYO

事後確率の最大化（もしくは最尤推定）によってCRFを学習します N個の入出力配列の組 {(x(i), y(i))}i=1Nが訓練データ集合として与えられたとする。
– i 番目の訓練データの長さをT(i)とする。
 訓練データ集合に対する事後確率の対数を取ったものの和は：

26

THE UNIVERSITY OF TOKYO

最急勾配法によって目的関数を最大化します これを最大化するために、最急勾配法を用いることにする
 更新式（現在のパラメータ!(t)から新たなパラメータ!(t+1)へ）は：– η(t)>0 は更新の幅を決定する学習率と呼ばれるパラメータ– r(!(t))は現在のパラメータ! = !(t)における目的関数L(!)の勾配：

27

THE UNIVERSITY OF TOKYO勾配を求める際に、計算の難しい箇所が2箇所あります パラメータの更新を行うためにはr(!(t))を計算する必要がある
 そのために目的関数L(!)を!について偏微分したものを計算する

 ここで問題となってくるのが2つの部分の計算：– 可能な全てのy ∈ ΣT(i)についての和を含むため、これを素朴に計算するのは、計算量の面で現実的ではない
 予測のときと同じく動的計画法を利用できる
28

THE UNIVERSITY OF TOKYOまずは簡単な方から計算します 条件付き確率場の特徴ベクトルの定義から:

 ここで以下の量を定義する：

 これを使うと我々の求めたいものは： つまり、uT(i)(yT(i))を全てのyT(i) ∈ Σについて計算できればよい
29

THE UNIVERSITY OF TOKYO

動的計画法によって求まります uT(i)(yT(i))を得るために、 u¿+1(y¿+1)をu¿(y¿)を用いて再帰表現する：

 予測のときと同様に、これを用いて¿ = 1, 2, …, T(i) について再帰的に計算することで、uT(i)(yT(i))が全ての yT(i) ∈ Σ について求まる 計算量は各¿ についてO(C)であるため、i 番目の訓練データについてはO(CT(i))となる
30

THE UNIVERSITY OF TOKYOもう一方の計算は面倒です 条件付き確率場の特徴ベクトルの定義から、以下のように書ける：

 さらに：

31

THE UNIVERSITY OF TOKYOここで先ほど再帰計算によって求めたut’-1(yt’-1)を再利用できます 先ほど再帰的に計算したut’-1(yt’-1)が現れる

これは次頁で求める vt’(yt’)
32

THE UNIVERSITY OF TOKYO

動的計画法を用いるために新たな量 v¿(y¿) を導入します 残るは、一番最後の： 新たな量v¿(y¿)を定義する：– vt’(yt’) の値が全ての yt’∈Σ に対して分かればよい これがわかればでできる

33の計算はO(T(i) C2)

THE UNIVERSITY OF TOKYOv¿ もまた動的計画法によって効率的に計算できます この量にも以下のような再帰的関係が成り立つ：

 この関係を用いて今度は ¿ = T(i)-1, T(i)-2, …, 1 のように逆向きに再帰式を適用していくことで、vt’(yt’) が、全ての yt’ ∈ Σ について求まる

34

THE UNIVERSITY OF TOKYO