カーネル法の応用

(1)

カーネル法の応用

松井知子

統計数理研究所 2006 年 7 月 6 ・ 7 日

公開講座「カーネル法の最前線―ＳＶＭ、非線形データ解、

構造化データ― 」

(2)

実問題を扱う

• 課題：いかにデータに語らせるか

– データに潜む構造を扱う。

– データの本質をつかむ。

• カーネル法によるアプローチ

– 構造化データを扱う。

例）ベクトル ⇒ 構造化オブジェクト

– データ x が与えられた時のラベル y の条件付分布をうまく推定する。

例） Penalized Logistic Regression Machine (PLRM)

(3)

3

構造化データを扱う

• 対象データ内の構造

– 様々な String/Tree/Graph kernel

( 基本的に Convolution kernel の考えを利用）

– P-kernel, Fisher kernel ( 確率的な生成モデルを利用）

– 例）テキスト・音声・画像、構文解析木、

ゲノム・タンパク質など

• 対象データ間の構造

– Diffusion kernel

– 例）タンパク質の相互作用、 WWW 、引用ネットワークなど

• クラスデータの構造

– Kernel conditional random field

– 例）形態素解析（単語列⇒品詞列）、

タンパク質の 2 次構造予測など

(4)

話の構成

実問題を扱う

構造化データを扱う条件付分布を推定する

ソフトウエアの紹介

対象データ内の構造クラスデータの構造

Convolution kernel の考えを利用

確率的な生成モデルを利用

(5)

Convolution Kernel の考えを利用

• 対象データ x ：ストリング、木、グラフなど

– ストリングや木はグラフの特別な場合と考えられる。

• ストリング / 木 / グラフ上のカーネル関数を設計 k(s, t)= 〈 Φ(s), Φ(t) 〉

– k(s, t) は半正定値性を満たし、 s, t の類似度を表す。

– s, t は大きさが異なる場合もある。

• 設計上の一般的な考え

– 部分構造（部分列や部分木など）に分解する。

– 一致する部分構造を数え上げて Φ(s) を構成する。

⇒効率的な計算の必要性

•

動的計画法

•

接尾辞木など

基本は

convolution kernel

[Haussler 99]

(6)

ストリングと部分列

•

ストリング

–

アルファベット

Σ

：

|Σ|

個のシンボルの有限集合

–

長さ

n

のストリング

Σ

ⁿ

–

全ストリング

Σ

^*：

–

ストリング

s

の部分ストリング

t

：

s=utv (u,v

：ストリング

)

• u= ε

^の時、

t

は接頭辞

• v= ε

^の時、

t

は接尾辞

•

長さ

k

の部分ストリング：

k-gram

• S[i : j]

：

s

_i

,…,s

_jの部分ストリング

•

ストリング

s

の部分列

u

–

インデックス

i=(i

₁

,…,i

_|u|

)

が存在して、

1

≦

i

₁＜‥＜

i

_|u|≦

|s|

– j=1,…,|u|

について、

u

_j

=s

_ij

–

部分列の長さ

l(i)

は、

l(i)=i

_|u|

-i

₁

+1

•

例）

s=“kernels”

–

部分ストリング：

t=“kern”

（接頭辞）

, “nels”

（接尾辞）

, “ern”, …

U

^∞₌

^Σ

= Σ

0

* n

n

“kernels”

s t

u v

(7)

典型的な応用先

• 自然言語処理

– 文字列： Σ={a, b, c, …, z}

– 単語列： Σ={ 単語全体 }

• ゲノム解析

– ゲノム： Σ={A, T, G, C}

– タンパク質： Σ={ アミノ酸全体 }

(8)

String Kernels

• ギャップを許した部分列を扱う [Lodhi et al., 2002]

– Gapped-weighted subsequences kernel 、 O(n|x||y|)

• 不一致ペナルティを用いる [Leslie et al., 2002]

– Mismatch string kernel 、 O(k ^m+1 l ^m (|x|+|y|))

• 接尾辞木を利用する [Vishwanathan et al., 2002]

– Suffix-tree-based spectrum kernel 、 O(|x|+|y|)

• 局所アライメントをとる [Vert et al., 2004]

– Local alignment kernel 、 O(n ³ |x||y|)

(9)

Gapped-Weighted Subsequences Kernel

[Lodhi et al, 2002]

• 関連研究： All-sequences kernel

–

全ての長さの部分列の出現回数を特徴ベクトルとする。

–

任意長のストリングを座標とする特徴空間

Fall

• 関連研究： p-Spectrum kernel

–

長さ

p

u

の出現回数を特徴ベクトルとする。

–

長さ

p

u

を座標とする特徴空間

Fp

| } :

) , {(

| ) ( ,

)) ( ( ) (

:

2 1 2

1 |

|

*

uv v s

v v s

s s

R F

u u u

p

p p

=

= Φ

≅

→ Σ

Φ

Σ

∈ Σ

φ φ

| } ]

[

| {

| ) ( ,

)) ( ( ) (

:

*

u s

s s

s

R F

u u u

all

=

= Φ

≅

→ Σ

Φ

Σ

∈

∞

i φ i

φ

u u

i

⁽¹⁾

i

⁽²⁾

i

₁⁽¹⁾

i

₁⁽²⁾

u i

_|u|⁽¹⁾

v

₁

v

₂

i

_|u|⁽²⁾

s

(10)

• Gapped-weighted subsequences kernel

–

ストリング中の長さ

l(i)

に応じて重み付けした、長さ

n

の部分列

u

の出現回数を特徴ベクトルとする。

[

ギャップが多い場合には割り引く

]

–

長さ

n

の部分列

u

を座標とする特徴空間

F

_n

1 ,

) ( ,

)) ( ( ) (

:

] [ :

) (

|

*

≤

=

= Φ

≅

→ Σ

Φ

∑ = Σ

∈ Σ

λ λ

φ φ

i i

i s

u

l u u

u n

s s

s

R F

n n

l(i)

i = (i

₁

, …., i

_|u|

)

u

Gap

s

(11)

11

• カーネルの定義

– All-sequences kernel

– p-Spectrum kernel

– Gapped-weighted subsequences kernel

∑ ∑ ∑

Σ

∈ = =

=

+

u n u s u t

l l n

s t

K

] [

: : [ ]

) ( )

)

(

, (

i

i j j

j

λ

i

) ( )

( )

( ), ( )

,

( s t s t s t

K

_u

u

x

φ φ ^⋅

= Φ

Φ

= ∑

Σ

∈

∑ ∑ ∑

Σ

∈ = = =

=

* ( , ): [ ] [ ] ( , ): [ ] [ ]

1 1

) , (

u u s t s t

all

s t K

j i j

i i j i j

⎪⎩

⎪ ⎨

⎧ = = ∈ Σ

=

+ +

=

−

+

−

=

+

−

∑ ∑

=

otherwise

0 , ,

if ) 1

, (

]) :

[ ], :

[ ( )

, (

1 1

1

|

| 1

1

|

| 1

　 ^p

suffix spec p

p s

i

p t

j

suffix p spec

p

u u t t u s t s

s K

p j j t p i i s K

t s K

s t

u u i

j

s t

u

u l(i)

l(j)

i+p

j+p

u

のギャップを除いた長さ：

n

(12)

• All-sequences kernel: {“cat”, “car”, “bat”, “baa”} の例

) 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 1 ( ) car"

"

(

) 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 1 ( ) cat"

"

(

= Φ

Φ

=

= Φ

φ ε ^a ^b ^c ^r ^t ^ca ^ct ^at ^ba ^bt ^cr

0 0

1 0 0 0

1 0 0

0 1 2 1

0 1 0

cat 1 1 0 1 0 1 1 1

car 1 1 0 1 1 0 1 0

bat 1 1 1 0 0 1 0 0

baa 1 2 1 0 0 0 0 0

φ ^ar ^aa cat car bat baa

0 0

0 0 1 0

1 0 0

1 0 0 1

0 0 0 0

0 0 1 0

1

0

0 cat

car

bat

baa

(13)

• p-Spectrum kernel: {“cat”, “car”, “bat”, “baa”} の例 (p=2)

φ ^ca ât âr ^ba âa

cat 1 1 0

1 0 0

0 0

car 1 0 0 0

bat 0 1 1 0

baa 0 0 1 1

1 )

car"

"

( ), cat"

"

( )

car"

"

, cat"

"

(

) 0 , 0 , 1 , 0 , 1 ( ) car"

"

(

) 0 , 0 , 0 , 1 , 1 ( ) cat"

"

(

2 = Φ Φ =

= Φ

− spec

K

(14)

• Gap-weighted sequences kernel: {“cat”, “car”, “bat”, “baa”} の例 (n=2)

φ ^ca ^ct ât ^ba ^bt ^cr âr âa

cat λ ² λ ³ λ ² ⁰ ⁰ ⁰ ⁰ ⁰

car λ ² ⁰ ⁰ ⁰ ⁰ λ ³ λ ² ⁰

bat 0 0 λ ² λ ² λ ³ 0 0 0

baa 0 0 0 λ ² + λ ³ ⁰ ⁰ 0 λ ²

4 2

2 3

2 2 3

2 ) car"

"

( ), cat"

"

( )

car"

"

, cat"

"

(

) 0 , ,

, 0 , 0 , 0 , 0 , ( )

car"

"

(

) 0 , 0 , 0 , 0 , 0 , ,

, ( )

cat"

"

(

λ λ

λ

= Φ

Φ

=

= Φ

K

(15)

• カーネルの計算

– 直接的に計算する場合： O(|Σ| ⁿ ) を含む計算

– 動的計画法のように再帰的な式を用いる： O(n|s||t| ）

•

初期条件：

•

再帰計算（過去に計算した結果を利用）：

∑ ∑ ∑

Σ

∈ = =

= +

u

n

u s u t

l l n s t

K

] [

: : [ ]

) ( )

) (

, (

i

i j j

j

λ i

( ) ( )

(

^{を含む一致}

)

を含む一致内での一致によるもの

内と

x t

s K

x t

s t

sx K

n n

+

=

+

=

) , ( )

, (

1 ) , ( )

,

( s = K t = K

_n

ε

_n

ε

過去に計算した結果新たに計算

(16)

• （ x を含む一致）の部分の再帰計算：

– 補助関数を導入する。

– 補助関数を用いて（ x を含む一致）の部分を表し、再帰的に計算する。

•

初期条件：

1 ,

, 1 ,

) , (

] [

: : [ ]

2 |

|

₁ ₁

= −

′ = ∑ ∑ ∑

Σ

∈ = =

+

−

+ i n

t s K

u

i

u s u t

j i t s

i K

i

i j j

λ

( )

i t

s t

s K

t s t

s K

j t

s K

x

i

x t j

n

j

<

′ =

∀

′ =

′ −

∑ = −

|)

|

|,

| min(

if ,

0 )

, (

, ,

1 )

, (

]) 1 :

1 [ , ( :

0 :

2 1 λ

を含む一致

u’

j

x x

t[1:j-1]

s

u’ x

u

ギャップを除いた長さが

n-1の部分列 u

u j

₁

t

s

i

₁

λ

^|s|-i¹⁺¹

λ

^|t|-j¹⁺¹

(17)

– i=1,…,(n-1) についての再帰計算：

⎪⎩

⎪ ⎨

⎧

+ ′

′′

′′ ≠

′′ =

+ ′′

= ′

′

− ( , )) otherwise )

, ( (

if )

, ) (

, (

) , ( )

, ( )

, (

1 |

|

t s K

t sx K

x u

t sx tu K

sx K

t sx K

t s K t

sx K

i i

i u i

i i

i

λ λ

過去に計算した結果新たに計算

O(|s||t|) の再帰計算

⇒全体としては O(n|s||t|) の計算量

( ) _∑

= ′ − −

x t j

n

j

j t

s K

x

:

2 1 ( , [ 1 : 1 ])

: λ

を含む一致

(18)

• カーネルの正規化（一般に利用される）

– 長さによる影響を取り除く。

) , ( ) , (

) , (

) ( ), ) (

( )

( 1 )

( ) , (

) (

) ) (

, ˆ (

t t K s s K

t s K

t t s

s t

t s

t s s K

=

Φ Φ Φ

= Φ Φ

Φ Φ

= Φ

(19)

テキスト分類の実験

• 実験条件

–

データベース：ロイターニュース

Reuiters-21578 –

カテゴリー： “所得”、“買収”、“原油”、“穀類”

–

学習：

390

ドキュメント（

152 / 114 / 76 / 48

）

–

テスト：

90

ドキュメント（

40 / 25 / 15 / 10

）

–

識別器：

SVM

（各ドキュメントが正解カテゴリーに分類されるか判定）

– N-grams kernel

、

Bag-of-words kernel

と比較

• N-grams kernel:

特徴ベクトルは

n-grams

（長さ

n

の部分ストリング）を添え字とする。

• Bag-of-words kernel: 特徴ベクトルは単語を添え字とし、単語の頻度情報を

値にとる。

• 結果

– F

尺度（再現率と適合率を考慮した尺度）：

“所得”：

95

％、“買収”：

88

％、“原油”：

95

％、“穀類”：

85

％

– Gap-weighted subsequences kernel ~ N-grams kernel

– Gap-weighted subsequences kernel > Bag-of-words kernel

(20)

Suffix-Tree-Based Spectrum Kernel

[Vishwanathan et al., 2002]

• 対象とするカーネルの型

– num _u (s) ：部分ストリング u の出現回数 – 例） p-Spectrum kernel

• 接尾辞木を用いた効率的なカーネルの計算

– 接尾辞木による文字列照合アルゴリズム [Cormen, et al, 1990]

u u

u

u s t w

t s

K = ∑ ⋅ ⋅

Σ

∈

) ( num )

( num :

) , (

*

(21)

• s=“ababc” の接尾辞木の例

–

接尾辞木：ストリング

s

のすべての接尾辞を表したもの（

trie

）

•

辺のラベル

: s

•

根から葉までのラベルを連結したもの：

s

の接尾辞

–

計算時間

•

接尾辞木の作成：線形時間

•

あるストリング中の部分ストリングの探索、複数のストリング中に共通に出現する部分ストリングの探索：線形時間

（根から辿り、頂点に対応する文字ストリングを列挙する。）

c$

c$ c$

ab

b abc$ abc$

“ababc$” “abc$” “babc$” “bc$”

“ab” “b” “c$”

根

←葉

O(|s|+|t|)

(22)

グラフ

• ラベル付きグラフ G = (V, E)

–

頂点の集合

V

（

|V|

個）

–

辺の集合

E

⊂

V

×

V –

ラベルの集合

A

–

ラベル関数

l: V

∪

E

→

A (l(x):

頂点（

or

辺）

x

上のラベル）

–

頂点

v

から出る辺の数

d(v) –

有限長の頂点列の集合

–

パス

h

∈

V

^*

(h = v

₁

,…, v

_n、

(v

_i

, v

_i+1

)

∈

E i= 1,.., n-1

、長さ

|h|

）

–

グラフ

G

の全パス集合

H(G)

⊂

V

^*

–

パス上のラベル

l(h) = (l(v

₁

) , l(v

₁

, v

₂

) ,…, l(v

_n-1

, v

_n

) , l(v

_n

))

∈

A

^2n-1

U

^∞⁼

=

1

*

n

V

n

V

(23)

Marginalized Graph Kernel の応用例

[Mahe et al., 2004]

• カーネルの定義 [Tsuda et al., 2002]

– p1, p2: V

₁^*

, V

₂^*上の確率分布

– K

_L

: A

^*×

A

^* →

R

ラベル列間のカーネル

)) (

), ( ( )

( ) ( )

, (

) ,

( ),

, (

2 1

2 2 )

, (

1 1 2

1 2 2 2

1 1 1

* 2

* 1 2 1

h l h l K h p h p G

G K

E V G

L V

V h h

∑ ∈ ×

=

)

| ( )

( )

, , (

otherwise 0

if ) 1

, (

1 2

1 1

2 1

= −

∏

=

⎩ ⎨

⎧ =

=

i n

i

i t s

n L

v v p v

p v

v p

l l l

l K

K

(24)

• ラベル列間のカーネルの例

)

| ( )

( )

, , (

otherwise 0

if ) 1

, (

1 2

1 1

2 1

= −

∏

=

⎩ ⎨

⎧ =

=

i n

i

i t s

n L

v v p v

p v

v p

l l l

l K

K

) ( )

| ) (

( ) ( ) 1

| (

) ( )

( )

( ₀

u p v u v p

p

v v p

u p

v p v p v

p

q a

q q t

q s

= −

=

E u

v v

u p v

u p V

v

v p v

p

a V

u

a

V v q

∈

⇒

>

=

∈

∃

−

=

<

−

∑

∈

) , ( 0

)

| ( ,

1 )

| (

1 ) ( ,

1 ) (

0 ₀

の与え方

v

から出て

に遷移して

u

にいる

(25)

• カーネルの効率的な計算

–

積グラフの利用

“A” 1

2 3

“A” 4 1 2

4 3

“A”

“B”

“C” “B” “C”

1,1 1,3

2,4 3,2 4,1

4,3

“A”

“A” “A”

“C”

“B”

“A”

グラフ G ₁ グラフ G ₂

積グラフ G

(26)

• 積グラフ上の遷移

1,1 1,3

2,4 3,2 4,1

4,3

“A”

“A” “A”

“C”

“B”

“A”

1,1 1,3 2,4 3,2 4,1 4,3 1,1

1,3 2,4 3,2 4,1 4,3

積グラフ G

遷移行列 Π

(27)

• 積グラフによるカーネルの計算

1 1

1 ( ), | | )

( 2

1 1 2

) 2 ( 1

2 )

1 ( 1

1 2

2 1 ) 2 ( 1

) 1 ( 1

1

2 1 1

1 1 1

1 ) (

(h) (h)

) ,

(

)

| ( )

| (

)) ,

(

| ) ,

((

)

( )

, (

)) ,

(

| ) , ((

) , ( ))

, ( )

, ((

∞ −

= ∈ =

∈

= − −

Π

−

⎟ =

⎟

⎠

⎞

⎜ ⎜

⎝

= ⎛

=

⎪⎩

⎪ ⎨

⎧

=

∑ ∑

∑

∏

I G

G K

v v

p u

u p

v u v

u

v p

u p

v u

v u v

u v

u

t s

n h H G h n

G H h

t t

t

s s

s

n i

i i

i i t

s n

n

π π

π

π π

π _L

計算量 O(|Π|d ^N ) ))

( ), ( ( )

( ) ( )

,

( ₂ ₂ ₁ ₂

) , (

1 1 2

1

* 2

* 1 2 1

h l h l K h

p h p G

G

K _L

V V h h

∑ ∈ ×

=

(28)

分子構造の分類実験

• データ： MUTAG データベース

• 結果

– Marginalized graph kernel: 90%

– Neural network: 89%

– Decision tree: 88%

– Linear regression: 89%

(29)

話の構成

実問題を扱う

構造化データを扱う条件付分布を推定する

ソフトウエアの紹介

対象データ内の構造クラスデータの構造

Convolution kernel の考えを利用

確率的な生成モデルを利用

(30)

確率的な生成モデルを利用

• Hidden Markov model （ HMM ）などの生成モデルを利用する。

–

有限状態集合

A

（初期状態：

a

_I、最終状態：

a

_F）、

状態

b

から

a

への状態遷移確率

P

_M

(a|b)

、

状態

a

でシンボル

σ

^{を生成する確率分布}

P( σ |a)

から構成される。

• データに対するモデルの尤度を用いる。

– P-kernel

–

拡張例：タンパク質発現プロファイルの解析

[Vert, 2002]

• モデルの尤度だけでなく、幾何情報も利用する。

– Fisher kernel

–

拡張例：音声認識

[Gales et al, 2004]

（

Tangent vector of posterior log odds (TOP) kernel)

(31)

P-Kernel

•

カーネルはデータ

x, z

の同時確率で表す。

K(x,z) = P(x,z)

–

ただし、

P(x,z)

は対称、かつ半正定値性を満たすものに限る。

•

条件付き独立を仮定する。

[

半正定値性の十分条件

] P(x,z|m) = P(x|m)P(z|m)

• Marginalisation kernel

–

モデル集合Mを座標とする特徴空間F

∑ ∈

∈

=

Φ Φ

=

∈ Φ

M m

M M

M m

m P

m z P m x P

z x

z x P

z x K

F m

x P x

) ( )

| ( )

| (

) ( ), ( )

, ( )

, (

))

| ( (

: a

(32)

• HMM から生成される固定長のストリング

– n

（

= 6

）状態（で表されたストリング

h

）の

HMM M

からストリング

s

（

= s

₁

,s

₂

,…,s

₆）、

t

（

= t

₁

,t

₂

,…,t

₆）が生成される。

h

₁

h

₂

h

₃

h

₄

h

₅

h

₆

s

₁

s

₂

s

₃

s

₄

s

₅

s

₆

HMM: M

)

| ( )

( )

| ( )

, (

)

| ( )

( )

(

)

| ( )

| , (

1 1

2 1

1

∈ = −

∈

−

=

∑ ∏

∑

∏

=

i i M A

h

i i n

i

i i M

A h

n n M M

M M

i i n

i

i i

h h P h t P h s P h

P h t P h s P t

s K

h h P h

h P h P h

P

h t P h s P h

t s P

n n

K

s

(33)

タンパク質発現プロファイルの解析

[Vert, 2002]

目的：

• タンパク質発現プロファイル間の類似度をはかる。

–

タンパク質発現プロファイル：あるタンパク質が各生体に発現するかどうかの情報

アプローチ：

• 系統発生樹上の進化過程も考慮する。

• Hidden tree model による Kernel 、および SVM を用いる。

(34)

葉

根

1 0 0 1 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 1 0

• 系統発生樹

0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 0 1 1 1

タンパク質

A

^{タンパク質}

B

(35)

• 根付き木

–

^{非循環有向グラフ}

– T

^{：頂点の集合、}

T

^*

= T

^＼

{ λ }

^、

λ

^：根

– L

^⊂

T

^{：葉の集合}

– u

^∈

T*

•

親の頂点

p(u)∈T

•

子の頂点の集合

c(u)∈T

• uから辿れる葉の頂点の集合 l(u)∈T

–

頂点に割り当てられる値

A={0,1}

–

^同時確率

P

^{が頂点の変数}

{X

_u

, u

^∈

T}

^{に対して定義する。}

–

便宜上、次の確率を定義する。

{ _u _u _u _u }

S S

y X

S u

x X

S u

P y

x p

A y

A x

T S

′

′ ′

′ =

′ ∈

∀

=

∈

∀

≡

∈

′ ⊂

⊂

,

| ,

)

| (

, ,

,

(36)

• 部分木で表される進化パターン (S, z _S ) ： Hidden tree model

• カーネルの定義

) ( )

| ( )

| (

) ( )

( )

( ), (

) ,

( :

) (

1

S S

L S

L T

C

S z A

D i

L i L

i L

L L

L

D L

z p z

y p z

x p

y x

y x K

R A

S S

∑ ∑

∑

∈ ∈

=

Φ

⋅ Φ

= Φ

Φ

≡

→

Φ

(37)

音声認識

[Gales et al., 2004]

目的：

• 音声データ O から、その発声内容（単語 w _i （列））を判定する。

–

^従来、

HMM

^{が用いられている。}

アプローチ：

• Fisher kernel （次式）を拡張する。

• SVM を用いる。

{ } ^arg ^max { ⁽ ^| ⁾ }

) (

) ( )

| max (

arg )

| ( max arg

, , ,

₂

1

i i

i

T

w P P

w P w w P

P

o o

o

O O O O

O

⎭ ≈

⎬ ⎫

⎩ ⎨

= ⎧

= K

[ ⁽ ^ˆ ^, ⁾ ⁽ ^ˆ ⁾ ] ^, ⁽ ^ˆ ^, ⁾ ^log ⁽ ^| ^ˆ ⁾ ^log ⁽ ^| ^ˆ ⁾

) ˆ , ( )

ˆ , ( )

, (

1 1

θ θ θ

, θ θ

I

θ Ι

θ

p x

x x p

g x

g x g

z g

x g

z x K

N

i i t

M

M t

∇

⎟ =

⎟

⎠

⎞

⎜ ⎜

⎝

⎛

∂

= ∂ Ε

=

−

θ

(38)

• カーネルの定義

–

^{二つのクラス}

ω

₁

, ω

₂の

HMM θ

⁽¹⁾

, θ

⁽²⁾による尤度比も用いる。

x

T

x x p

p

p p

T K

, , , ,

ˆ )

| ( log

ˆ )

| ( log

ˆ )

| ( log ˆ )

| ( 1 log

) ˆ , (

) ˆ , ( ), ˆ , ( )

, (

2 1 )

2 (

) 1 (

) 2 ( )

1 (

) 2 (

) 1

(

= K

⎥ ⎥

⎥

⎦

⎤

⎢ ⎢

⎢

⎣

⎡

∇

−

= Φ

Φ Φ

=

x θ

x θ x

θ x θ

x x

θ

z θ x

θ z

x

θ θ

(39)

間違えやすい単語の識別実験

• データ：大規模音声認識用データベース

（ Fisher LDC 、 400 時間）

• 間違えやすい単語： “A/The”, “Can/Can’t”, “Know/No”

• 識別率（％）：

“A/The” “Can/Can’t” “Know/No”

従来の

HMM 58 82 68

本カーネル

61 85 72

80 89 86

（単語ラティスから計算される事後確率も特徴ベクトルに加えた場合）

(40)

話の構成

実問題を扱う

構造化データを扱う条件付分布を推定する

ソフトウエアの紹介

対象データ内の構造クラスデータの構造

Convolution kernel の考えを利用

確率的な生成モデルを利用

(41)

クラスデータが構造を持つ場合

• SVM: クラスデータ y = {-1, 1}

• 例）品詞タグ付け

– x = “The cat ate the mouse”

– y = “Det N VBD Det N”

• 例）音声認識

– x = x

₁

,x

₂

,…,x

_T^{：特徴ベクトル列}

– y = “How do we recognize speech”

(42)

Kernel Conditional Random Field

[Lafferty et al., 2004]

• x, y を組み合わせて扱う。

– x

：特徴ベクトル（例）アミノ酸配列、ヒストグラムなど

– y

：ラベル付けしたグラフ

• 対象：グラフデータ

• 目的：グラフの頂点のラベル付けグラフに関する表記：

–

β：グラフの有限集合

– g

^{∈β：グラフ}

– V(g):

^{頂点の集合}

– |g|=|V(g)|

：グラフの大きさ～頂点数

– C(g)

：クリーク（頂点が密結合している部分）の集合

：クリーク中の頂点数

x

₁

x

₂

x

₄

x

₃

x

₅

x

₆

クリークの例

(43)

43

グラフに関する表記のつづき：

– Y

^{：ラベルの有限集合}

– Y(g)

^{：グラフ}

g

^{中のラベル集合}

– Y

_c

(g) = {(c, y

_c

) | c

^∈

C(g), y

_c^∈

Y|c|}

^：

グラフ

g

中のラベル付けされたクリークの集合

– X

：入力特徴空間例）

X = R

ⁿ

– X(g)

^{：グラフ}

g

の頂点に割り当てられた特徴ベクトルの集合

• 目的：関数 h: X( β ) → Y( β ), h(g,x) ∈ Y(g) を学習したい。

• h を直接推定することは難しい⇒ XY _c ( β）上の損失関数を考える。

{ }

⎟⎟

⎟ ⎟

⎠

⎞

⎜⎜

⎜ ⎜

⎝

⎛

⎟ ⎟

⎠

⎞

⎜ ⎜

⎝

⎛ ′

⎟ ⎟

⎠

⎞

⎜ ⎜

⎝

⎛

−

=

∈

→

∑ ∑

∑

′∈ ∈

∈

)

( ( )

) (

|

) , , , ( exp

log )

) , , , ( , (

), ( ,

) ( :

g Y y

c g

C c

g C c

c c

c

y c x g f

y c x g f y

c x g f y

Y y

g C c

R XY

f

φ

β

識別関数

負の損失関数

(44)

• XY _c ( β ) 上のカーネルを考える。

• 具体例：

∑ ∑ ∑

= ∈ ∈

′

⋅

=

⋅

′ ∈

′

N

i c C g y Y

c c

i c

c c

i c

c

y c x g K y f

R y

c x g y

c x g K

1 ( )

) (

)

( | |

) ), ,

, , ((

) ( )

ˆ (

)) ,

, , ( ), ,

, , ((

α

Representer Theorem より

（学習サンプル数：

N)

) ,

( ) ( )

, , ˆ (

) ,

( ) ,

( ))

, ( ), ,

( , , ( )), ,

( ), ,

( , , ((

) ,

( ),

, (

) (

1 ( )

1 ) ( 2

1 )

, (

2 1 2

1 2

1 2 1 2

1

) 1 2 (

1

1 1

i v v

N

i v V g i v v

v

v v

c

x x

K y y

y x f

y y x

x K y

y v

v x g y

y v

v x g K

y y y

v v c

∑ ∑

i

= ∈

′

=

= ′

′

=

α

δ v ₁ y ₁

負の損失関数を最大にする識別関数

x

エッジ上のカーネル

効率的な

f

の推定アルゴリズムを提案

(45)

話の構成

実問題を扱う

構造化データを扱う条件付分布を推定する

ソフトウエアの紹介

対象データ内の構造クラスデータの構造

Convolution kernel の考えを利用

確率的な生成モデルを利用

(46)

条件付分布を推定する

• SVM はサポートベクターだけで識別境界を表す。

• x 与えられた時の y の分布をうまく推定することにより、データの本質をつかむ。

– Penalized logistic regression machine; PLRM [

^田邉

, 2001]

– Kernel multiple logistic regression; KMLR [Seeger, 2005]

– Kernel conditional random field; KCRF [Lafferty et al., 2004]

{ }

∑ ∑

∑

′ ∈ ∈

∈

⎟ ⎟

⎠

⎞

⎜ ⎜

⎝

⎛ ′

⎟ ⎟

⎠

⎞

⎜ ⎜

⎝

⎛

=

⇔

)

( ( )

) (

) ,

, , ( exp

) ,

, , ( exp

) ,

| ( )

) , , , ( , (

g Y y

c g

C c

g C c

c c

y c x g f

y c x g f x

g y p y

c x g f φ y

負の損失関数

ロジスティック変換

(47)

Penalized Logistic Regression Machine

[ 田邉 , 2001]

• 多クラスの判別予測を行う。

–

^{学習データセット}

{(x

_i

, y

_i

)}

_i=1,…,N

（例）データ

x

_i^∈

R

ⁿ

,

^クラス

y

_i ^∈

{1,…,K}

^）

– x

^{が与えられた時の}

y

^{の値を予測する。}

• x が与えられた時の y の条件付分布として、 p(x) の多項分布を考える。

( ) ( )

( )

( ) ^x ^w ^v ( ) ^x ^x

w x

f

x f

x x f

p x

N i i

i k k

M i i

i k k

K j

j k k

t K

, )

(

) ( exp

) ( ) exp

( ,

) ( ,

), ( )

(

) ( 1

) ( )

0 ) (

( 1

) (

1 1

Κ

= +

=

∑

=

ω φ

p K

Dual

^{パラメータ}

Primal

^{パラメータ}

M

：特徴ベクトルの次元 ≫

N

：サンプル数

V t

W = Φ

(48)

• 負の対数尤度

• 負の罰金付対数尤度

[ i j ] i j N

F N

j

j c

x x k

x p

PL

j

, , 1 ,

2 1

) ,

(

)) 2 (

log(

)

(

¹² ²¹

= K

=

Γ +

−

≡ ∑

K

VK

V δ

∑ =

−

≡ ^N

j

c x

p

L

j

1 )) (

log(

(V )

PLRM のパラメータ推定

罰金項

KKT conditions

N

O K

PL

) ,

) ) (P(

( = − + Γ =

∂

∂ V Y V K

V

V δ

⎟⎟

⎟ ⎟

⎠

⎞

⎜⎜

⎜ ⎜

⎝

⎛

=

) ( )

1 (

) ( 1 )

1 ( 1

N K K

N

v v

L

M O

M

L

V

(49)

• Newton+CG 法による V の推定

–

^Δ

V

⁽ⁱ⁾の推定を

CG

^{法で行う。}

[ ]

V V V

p p

V K

V Y

V V V V

V V V

2 2

1 ,

) ( )

( )

( ) ) (

( )

1 (

) ) (

(

) (

; );

( )

P(

, )

) ) (P(

) ( (

) (

∂

= ∂

′

≡

→ Γ

+

−

∂ =

= ∂

Δ

−

′ =

−

+

=

f PL

x x

PL O f

f f

N N

K i i

i i

i i i

i

δ L

α α

Newton 法

（ヘシアン行列が厳密な式で与えられている）

KCRF

^？

KMLR

^○

大規模データのための学習アルゴリズム

[Myrvoll et al., 2006]

(50)

PLRM による自動的な特徴抽出

[ 松井、田邉、 2006]

• 目的：入力音声を発声した話者が誰かを判定する。

–

^従来、

HMM/GMM

で表された各ユーザモデルと入力音声との尤度を

求め、最大尤度を示すユーザモデルの話者をその入力音声を発声した話者とする。

–

特徴量としてはメルケプストラム係数ベクトルが用いられる。

•

周波数軸を人間の聴覚の特性を考慮したメルスケールに変換

•

ケプストラム分析（対数パワースペクトルの逆フーリエ変換）

• アプローチ： PLRM により、音声データから識別的な話者特徴を暗に抽出して用いる。

–

メルスケールなどの事前知識に基づく処理を行うことなく、

256

^次元の対数パワースペクトルを直接用いる。

(51)

PLRM

-

^{メルスケーリング}

-

^次元削減

-

^{対数パワー}

-

^逆

FFT

(26

^{次元メルケプストラム}

)

音声信号

(FFT

^{スペクトル}

)

音声信号

(FFT

^{スペクトル}

)

Dual

^{パラメータの推定：}

話者間の確率密度の比

GMM

^{パラメータの推定：}

各話者の確率密度

確率推定

決定：尤度の比較

-

^{対数パワー}

(256

^{次元スペクトル}

)

決定：確率推定量の比較

GMM

PLRM による方法 GMM による方法

学習

識別特徴抽出

尤度推定

(52)

話者 10 名の識別実験

識別率

(%)

テスト

データ方法

メルケプストラム対数パワースペクトル

PLRM 90.7 (87.3, 94.7) 92.7 (89.3, 96.0) SVM 91.3 (87.3, 94.7) 88.0 (83.3, 92.0) GMM 89.3 (85.3, 93.3) 84.0 (79.3, 88.7)

PLRM 99.3 (98.7,100) 100 (99.3, 100)

SVM 98.0 (96.0, 99.3) 100 (99.3, 100)

GMM 99.3 (98.7, 100) 99.3 (98.7, 100)

文音声単語音声

※学習は

3

^{時期に発声した}

3

^文章（約

12

^秒）

(53)

話の構成

実問題を扱う

構造化データを扱う条件付分布を推定する

ソフトウエアの紹介

対象データ内の構造クラスデータの構造

Convolution kernel の考えを利用

確率的な生成モデルを利用

(54)

まとめ

• 構造化データを扱う

–

データ、目的に応じてカーネルを設計

–

カーネルを効率的に計算⇒グラム行列

– SVM

• 条件付分布をうまく推定する

– p(y|x)

をロジスティック変換の形で表す

–

負の尤度最小化（負の損失関数最大化）に基づくパラメータ推定

カーネル法の応用