Microsoft PowerPoint - ShinIshii

誤り訂正出力符号の拡張による

多値判別法とその応用

奈良先端科学技術大学院大学

石井 信

多値判別の一般的枠組み

{

}

ラベル

入力、

・

_x

_:

_y

∈

₁

_,

_L

_,

_G

_:

判別関数

・

_F

₍

_x

_,

_y

₎

∈

_R

_:

でラベルを決める

)

,

(

max

arg

_y

F

x

y

( , )

F

x

y

をどの様に構成するのか？

の同時分布

・

_p

₍

_x

_,

_y

₎

_:

_x

_,

_y

( , )

( ( | ))

F

x

y

=

u p y

x とするとベイズ最適

は単調増加関数

)

(z

u

• 多値判別関数 F(x,y) を直接構成する

– Fisherの（線形）判別関数

– Multi-class SVM, AdaBoost, …

• F(x,y) を2値判別関数の組み合わせで構成する

– Error correcting output coding (ECOC) に基づく手法

• Bradley-Terryモデル(Hastie & Tibshirani, Yukinawa, et al.)

– クラス所属確率 p(y|x) を推定できる – 確率出力を持つ2値判別器が必要

– 例題ごとに事後確率を計算する必要がある

• Loss-based decoding (Dietterich & Bakiri, Allwein, et al.)

– 単純な Hamming decoding を含む – 実装が簡単

ECOCの定式化

• コード表W ： p×G 行列

1

1

1

1

1

1

1

1

1

1

1

0

1

0

1

0

1

1

W

−

−

⎛

⎞

⎜

₋

₋

⎟

⎜

⎟

⎜

₋

₋

⎟

= ⎜

⎟

−

⎜

⎟

⎜

₋

⎟

⎜

⎟

⎜

₋

⎟

⎝

⎠

2

/

)

1

2

3

(

max

p

=

G

−

G+1

+

Class １ ２ ３

2値判別１

2値判別２

2値判別３

:

301

90

25

6

1

6

5

4

3

2

ハミング復号

1 1

1

1

1

1

0

1

y

⇓

−

⎛

⎞

⎜

⎟

⎜

⎟

⎜

₋

⎟

= ⎜ ⎟

₋

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎝

⎠

z

　　

　　　

1

1

1

1

1

0

n n

y

⇓

⎛

⎞

⎜

₋

⎟

⎜

⎟

⎜

₋

⎟

= ⎜ ⎟

₋

⎜

⎟

⎜

⎟

⎜

⎟

⎜

⎟

⎝

⎠

z

　　

　　　

L

L

M

W

i

x

i

z~

{ }

1, 1 ) ( 1 x ∈ − f

{ }

1, 1 ) ( 2 x ∈ − f

{ }

1, 1 ) (x ∈ − f_p

⎠

⎞

⎜

⎜

⎜

⎜

⎜

⎜

⎜

⎜

⎝

⎛

−

−

−

−

−

−

−

−

−

−

1

1

0

1

0

1

0

1

1

1

1

1

1

1

1

1

1

1

ハミング距離最小のコードワードによってラベルを決める

基本コンセプト

))

(

,

),

(

(

~

2

値判別器

z

=

f

₁

x

L

f

_p

x

⎟

⎟

⎟

⎟

⎟

⎟

⎟

⎟

⎠

⎞

⎜

⎜

⎜

⎜

⎜

⎜

⎜

⎜

⎝

⎛

=

)

(

)

(

)

(

~

2 1 i p i i i

f

f

f

x

x

x

z

M

M

M

( ,

)

1

1

1

1

0

1

i i i

y

⇓

−

⎛ ⎞

⎜ ⎟

⎜ ⎟

⎜ ⎟

₋

= ⎜ ⎟

−

⎜ ⎟

⎜ ⎟

⎜ ⎟

⎜ ⎟

⎝ ⎠

x

z

　　

　　　

各判別器の判別誤り

ビット反転ノイズ

⇔

)

|

~

(

z

z

p

確率モデル

)

~

|

(

max

arg

_z

p

z

z

)

(

)

|

~

(

)

~

|

(

z

z

p

z

z

p

z

p

∝

復号法

確率モデルの仮定

• ３元（1,0,-1）入力、２元出力(1,-1)通信路

• 多値判別における仮定

– 各2値判別器（ビット）は独立

– 判別器ごとにノイズの性質が異なる

• パラメータは j ごとに決める

– 非対称

False positive rate ≠

False negative rate

1 2, f 0.5

確率モデル１

(

)

2 ) , , ( ) ( ~ exp ) , , | ~ ( ₁ zj j j j j j j j j j j j j z z z z z p

β

γ

δ

=

β

+

γ

−

ψ

β

γ

・

は正規化定数

)

(

),

,

,

(

₂ 1

z

j

β

j

γ

j

ψ

δ

j

ψ

)

|

~

(

)

|

~

(

p_{j 1}

p

z

_j

z

_j

p

z

z

=

Π

₌

・

(

)

2 1 2( ) ~ exp zj j j j z − − ×

δ

ψ

δ

)

(s

y

1

z

2

z

M

p

z

1

~

_z

2

~

_z

M

p

z~

yˆ

通信路の同定

∑

= = n i i i p Z L 1 ) ; | ~ ( log ) ; ~ ( β,γ,δ z z β,γ,δ ・

)

;

~

(

max

arg

)

ˆ

ˆ

ˆ

(

β

,

γ

,

δ

=

_β,γ,δ

L

Z

β,

γ,

δ

称性 のコードに対する非対 0 = j z 1 I( 1, 1)

ˆ : false negative rate

I( 1) i i j j i j i j i z z z ε = = = − =

∑

∑

% 2 I( 1, 1)

ˆ : false positive rate

I( 1) i i j j i j i j i z z z ε = = − = = −

∑

∑

%

∑

∑

= = = = i i j i i j i j j z z z f ) 0 I( ) 1 ~ , 0 I( ˆ j j j j j 2 1 2 1 ˆ ˆ ) ˆ 1 )( ˆ 1 ( log 4 1 ˆ

ε

ε

ε

ε

β

= − − ・ j j j f f ˆ 1 ˆ log 2 1 ˆ − = δ ) ˆ 1 ( ˆ ˆ ) ˆ 1 ( log 4 1 ˆ 2 1 2 1 j j j j j

ε

ε

ε

ε

γ

− − = が小さい程大きい j j 2 1 , ˆ ˆ ε ε な程大きい がアンバランス j j 2 1 , ˆ ˆ ε ε

ラベルの復号

)

ˆ

ˆ

ˆ

;

~

(

)

(

)

ˆ

ˆ

ˆ

;

|

~

(

)

~

|

(

δ

,

γ

,

β

z

z

δ

,

γ

,

β

z

z

z

z

p

p

p

p

=

・

⎪⎩

⎪

⎨

⎧

₌

₌

=

∑

₌

otherwise

0

if

)

(

I

1

)

(

₁

の

列

判別問題では

_p

_n

y

j

W

j

n i i

_z

z

復号）

で復号（MAP

)

~

|

(

max

arg

ˆ

z

z

z

=

_z

p

パターンのみ

は

探索すべき

_z

_G

個

のパターンは本来

p

2

z

Hamming decodingとの関連

)

,

,

1

(

0

,

0

:

)

(

y

j

p

p

一様分布、

γ

_j

=

δ

_j

=

=

L

・

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛

∝

⇒

∑

= p j j j j

z

z

p

1

~

exp

)

~

|

(

z

z

β

∑

=

−

=

p j j j j

z

z

p

1

2

~

1

max

arg

)

~

|

(

max

arg

_z

z

z

_z

β

Hamming distance

⇒ 重みつき

9 ハミング復号の仮定

¾ 各2値判別器が同じ性質を持つ ¾ 2種の過誤の割合が等しい ¾ 各クラスが同じサンプル数を持つ

確率モデル２

∑

Β

Β

=

z

z

z

z

~

)

~

exp(

/

)

~

exp(

)

|

~

(

y

T _y T _y

p

ベクトル

1

:

×

Β p

_y

各判別器は独立

の列しか値をとれない

はW

z

z

,

,

_p

)

(

₁

L

=

z

p

z~

1

~

_z

y

2

~

_z

M

yˆ

M

y

1

z

2

z

M

p

z

1

~

_z

2

~

_z

M

p

z~

yˆ

数値実験：人工データ

• 50回の繰り返し

– 200点の訓練データ、2000点のテストデータ

• 評価モデル

– モデル1およびモデル2 – 各2値判別器はSVM – カーネルはRBFカーネルと多項式カーネル

• 比較モデル

– Multi-class SVM (C-SVM, Spoc-SVM) – カーネルはRBFカーネルと多項式カーネル – 各2値判別器をSVMとしたECOCでHamming decoding

数値実験：人工データの例

−1.0 −0.5 0.0 0.5 1.0 −1.0 −0.5 0.0 0.5 1.0 x1 x2

数値実験：訓練誤差

0.2 0.3 0.4 0.5 0.6 Training error Spoc.Rbf Spoc.Poly C.Rbf C.Poly Hamm.Rbf Hamm.Poly Prop1.Rbf Prop1.Poly Prop2.Rbf Prop2.Poly

数値実験：テスト誤差

0.25 0.30 0.35 0.40 0.45 0.50 0.55 0.60 Test error Spoc.Rbf Spoc.Poly C.Rbf C.Poly Hamm.Rbf Hamm.Poly Prop1.Rbf Prop1.Poly Prop2.Rbf Prop2.Poly

UCIデータセット：テスト誤差

0.13424±0.01178 0.04852±0.00715 0.16400±0.01278 0.06805±0.01000 0.14862±0.01241 0.07595±0.01323 Glass 0.01291±0.00419 0.03360±0.00996 0.01331±0.00488 0.03794±0.00914 0.01834±0.00817 0.03286±0.00793 Wine 0.04027±0.00715 0.03380±0.00859 0.03967±0.00784 0.03667±0.00790 0.04293±0.00896 0.03600±0.00858 Iris 0.15143 0.07619 0.17048 0.05810 0.16400 0.07381 Segmentation 0.12150 0.14550 0.12050 0.14050 0.11750 0.16400 Satimage 0.03501 0.03355 0.05309 0.03384 0.05076 0.04142 Ann-thyroid Proposed: RBF Proposed: Poly C-svm: RBF C-svm: Poly Spoc-svm:RBF Spoc-svm: Poly

マルチカテゴリ問題

• マルチカテゴリ問題とは

– 入力に複数のラベル（タグ）が付与されている問題

• 例）WEBにおけるテキスト分類、Gmail等 仕事 遊び 友人 メルマガ

M

メール１

1

1

1

−

1

−

メール２

1

−

1

1

1

−

• 既存手法：

– 各カテゴリを判別問題として解く – 多項分布の拡張（PMM) – SVMを応用

カテゴリ

2値判別器のナイーブな適用

カテゴリ1 カテゴリ1以外 判別器 f1 判別器 f2 カテゴリ2 カテゴリ2以外 判別器 f3 カテゴリ3以外 カテゴリ3 入力x カテゴリラベル列y 1 2 3

( 1, -1, -1)

( 1, 1, -1)

( 1, -1, 1)

(-1, 1, 1)

1

x

2

x

3

x

4

x

))

(

3

),

(

2

),

(

1

(

:

x

x

x

f

f

f

予測

判別器の誤り⇔ビット反転ノイズ

を同定

)

|

)

(

),

(

(

y

p

f

x

g

x

ECOCによるマルチカテゴリ分類

入力 カテゴリラベルｙ 1 2 3

( 1, -1, -1)

( 1, 1, -1)

( 1, -1, 1)

(-1, 1, 1)

1

x

2

x

3

x

4

x

パリティビット列ｚ 1 2 3 4 5

( -1, 1, -1, 0, 0)

( 0, 1, -1, 0, 1)

( 1, -1, 1, 1, 0)

( 1, 0, 1,-1,-1)

+

)

,

,

(

)

(

x

=

f

₁

f

₂

f

₃

f

g

(

x

)

=

(

g

₁

,

g

₂

,

g

₃

,

g

₄

,

g

₅

)

パリティz=z(y)はカテゴ リラベル列ｙから一意に 決まる

マルチカテゴリの推定

• カテゴリラベル列 y の推定（MAP復号）

• 問題点：可能な y のバリエーションは 2

カテゴリ数

– 事前分布による拘束

• （例）各入力は一度に多くのカテゴリに含まれない

– 近似的周辺化アルゴリズムの援用

• Belief propagation など

)

(

)

|

)

(

),

(

(

))

(

),

(

|

(

y

p

y

p

y

p

f

x

g

x

∝

f

x

g

x

))

(

),

(

|

(

max

arg

_y

p

y

f

x

g

x

実験用データ

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 10 15 20 5 1 01 52 0 x1 x2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

結果：カテゴリの誤推定率

20 40 60 80 100 0.24 0.26 0.28 0.30 0.32

Code length of parity

Test error

SVM

ここまでのまとめ

• ECOCの枠組みに基づき、多数の2値判別

器の組み合わせによる多値判別法を構成

– 判別誤りの非対称性を考慮

– 特殊な場合としてHamming decodingを含む

– Multi-class SVMよりも優れた性能

• マルチカテゴリ問題への応用

– カテゴリラベルにパリティを付加し冗長にする

ことで性能向上

• Encoding問題への拡張

UCIデータセットの概要

6 9 214 Glass 3 3 178 Wine 3 4 150 Iris 7 19 2100 210 2310 Segmentation 6 36 2000 4435 6435 Satimage 3 21 3428 3772 7200 Ann-thyroid #Classes #Attributes #Test #Training #Total Dataset

CV

fold

-5

100

×

5-fold cross-validationを100回行い、平均挙動を見る

UCIデータセット：訓練誤差

0.04509±0.00310 0.00676±0.00143 0.08886±0.00781 0.00581±0.00119 0.06481±0.00620 0.00931±0.00204 Glass 0.00445±0.00106 0.00000±0.00000 0.00476±0.00123 0.00000±0.00000 0.00063±0.00078 0.00000±0.00000 Wine 0.02290±0.00253 0.02343±0.00248 0.02478±0.00266 0.02408±0.00283 0.02248±0.00241 0.02422±0.00239 Iris 0.12381 0.03333 0.17143 0.00952 0.11429 0.02857 Segmentation 0.10462 0.11995 0.10688 0.10485 0.09515 0.12469 Satimage 0.02519 0.02386 0.04745 0.02333 0.04348 0.02572 Ann-thyroid Proposed: RBF Proposed:Poly C-svm: RBF C-svm:Poly Spoc-svm: RBF Spoc-svm:Poly

多重検定の問題

• （典型例）遺伝子発現に基づく有意遺伝子

の抽出およびそれを用いた判別

9 良いスコア（検定統計量）の選び方

9 良いしきい値の決め方

9 検定誤差の見積もり方

各個検定が最適であること 多重検定が全体として最適であること vs.

遺伝子 i の 発現レベル _xi

μ

_i1

μ

_i2

σ

_i

μ

_i1

= μ

_i2 対立仮説 H₁: gene i is active 対立モデル尤度:

∏

= = M j i iDj ij i i i i N x X g 1 2 2 1, , ) ( ; , ) | (

μ

μ

σ

μ

σ

μ

_i1

= μ

_i2 帰無仮説 H₀: gene i is inactive

∏

= = M j i ij i i N x X f 1 2 ) , 0 ; ( ) | (

σ

σ

帰無モデル尤度: class 1 (tumor samples) class 2 (non-tumor samples)

有意遺伝子選択の問題

Neyman-Peason’s lemma

• 単純仮説(パラメータを持たない)が前提

• 非単純仮説では最尤推定値をプラグイン

した尤度比が漸近的に最強

「尤度比は最強の検定スコアである」

一定の有意水準 P( FP ) = α のもとで、 検出力 ( 1−P( FN ) = 1−β ) が最大 対立モデルの尤度

)

ˆ

|

(

)

ˆ

|

(

i i

X

f

X

g

ϕ

θ

)

(

)

(

X

f

X

g

帰無モデルの尤度

遺伝子の有意性スコア

• t-score

(正規モデルの尤度比スコア) – i.e. S/N ratio

• SAM score (Tusher, Tibshirani & Chu, 2001)

• Empirical Bayes score (Efron, 2002)

– 仮説の事後確率をスコアとする – 事前分布 P(σ_i) に関して多重性を利用した経験ベイズ推 定値に基く i i i S m m | | ₁ − ₂ m_ij : 各クラス内標本平均 S_i : クラス内標準偏差(両クラス共通) μ_i1 μ_i2 σ_i 0 2 1 | | S S m m i i i + − S₀ : 全遺伝子で共通の定数 さまざまな細かい改良

多重検定における最良さ

• 多重性を利用した場合に、単純な個別検定

の繰り返しよりも良い検定ができないか？

• 「最良」の多重検定スコアの定義

– FPR: false positive rate (FDR) （第一種の過誤）

– FNR: false negative rate （第二種の過誤）

(Storey, 2005) EFP = E[FPR] が同程度である統計的検定の中で ETP = E[1-FNR] を最大にする統計的検定を

ODP lemma

(Storey, 2005) • 「以下の統計量に基く検定は ODP である」 • 前提： – N個の単純帰無仮説 f₁(X), f₂(X), ..., f_N(X)と N個の単純対立仮説 g₁(X), g₂(X), ..., g_N(X)に基く多重検定 –

)

(

...

)

(

)

(

)

(

...

)

(

)

(

)

(

2 1 2 1

X

f

X

f

X

f

X

g

X

g

X

g

X

S

N M M M ODP

+

+

+

+

+

+

=

+ +

∑

∑

∈ ∈

=

0 1

)

(

)

(

G i i G i i

X

f

X

g

ただし、 G₁ = { 1, 2, ..., M } は対立仮説が真である遺伝子の集合、 G₀ = { M+1, M+2, ..., N } は帰無仮説が真である遺伝子の集合

)

( X

S

_ODP を全遺伝子 i=1,…,N に対して共通の統計量 として用い、共通のしきい値を設定

漸近ODP

• 各X を構成するサンプル数無限大の極限で一致

∑

∑

∈ ∈

=

0 1

)

(

)

(

)

(

G i i G i i ODP

X

f

X

g

X

S

∑

∑

∈

=

0 ˆ

)

ˆ

|

(

)

ˆ

|

(

)

(

ˆ

G i i i i i i ODP

X

f

X

g

X

S

φ

θ

非単純仮説では 帰無・対立仮説の確率密度関数 は最尤推定パラメータに基いて 決定 実際の多重検定状況では 真の集合 G₀, G₁ は未知 そこで適当なしきい値にもとづく 尤度比検定による決定で近似

潜在変数モデルを対立仮説とした

遺伝子選択

center of class k for gene i intra-class variance of gene i (common among classes k=1,2) class label prior of class k expression level of gene i at sample j

∏

=

j j i i

p

x

X

g

(

|

θ

)

(

( )

)

• 各サンプル j の所属クラス k が必ずしも観測さ

れない場合

• 教師無し遺伝子選択・準教師付き遺伝子選択

教師あり、教師なし、準教師ありスコア

• 教師付き： P(k) Å P( k | y(j) )= I( k = y(j) )

– 帰無仮説モデル H

₀

:

μ

_i1

=

μ

_i2

– 対立仮説モデル H

₁

:

μ

_i1

=

μ

_i2

隠れ変数モデルに対するODP

•ODPp パラメータを共有する •ODP パラメータと隠れ変数を共有する

)

ˆ

|

(

)

(

ˆ

_i

_X

_g

_X

_i

g

=

θ

)

ˆ

,

|

(

)

(

ˆ

_i

_X

_g

_X

_Z

_{i i}

g

=

_⋅⋅

θ

∑

∑

∈ = 0 ˆ ) ( ˆ ) ( ˆ ) ( ˆ G i i i i ODP X f X g X S ) | ,..., ( max arg ˆ (1) ( ) θ θ θ M i i i = p x x

∑∏

= = k M j j i j i j i k p k x p 1 ) ( ) ( ) ( ) | ( ) , | ( max arg θ θ θ

)

ˆ

,

|

(

,

}

{

) ( ) ( def 2 : 1 , : 1 i j i j i ijk k M j ijk i

x

k

p

Z

Z

Z

θ

=

=

_{= =} ⋅⋅

∏ ∑

=

⎟

⎠

⎞

⎜

⎝

⎛

=

M j k i ik j i ijk

N

x

Z

1 ) (

)

ˆ

,

ˆ

|

(

μ

σ

∏ ∑

= ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ = M j k i ik j i x N k P 1 ) ( ) ˆ , ˆ | ( ) ( μ σ

評価用人工データ

癌 非癌 active genes inactive genes 癌/非癌以外の 8種の特徴量のいずれかに関して 活性である遺伝子 癌/非癌ラベルに対して 活性である遺伝子

教師あり、教師なしスコア

active inactive active inactive Supervised score が検出したい遺伝子分類 Unsupervised score が検出したい遺伝子分類 癌 非癌

教師なしスコアの比較

Likelihood Ratio ODPp θ のみ共有 ODP θ と _Z を共有

準教師ありスコアの比較

tumor non-tumor unknown samples Observation active genes inactive genes

準教師ありスコア：実データ

全N症例のクラスラベルのうち 一部～全部を隠した場合の スコアランキングの変化 前立腺がんデータ（公開） - 52 癌組織 × 50 正常組織 - 約 1万遺伝子 オリジナルランキングと 一部ラベルに基くランキングと の間の Spearman 順位相関

準教師ありスコア：実データ

大腸がんデータ - 40 癌組織 × 22 正常組織 - 約 2000遺伝子 ラベルの順位相関 オリジナルの 上位 1%遺伝子 検出に関するAUC

多重検定スコアのまとめ

• ODP は、多重検定スコアの最適性を

Neyman-Pearson の拡張によって定義する

• 隠れ変数モデルを対立仮説とするとき、

ODP には 2種類の自然な実装法がある

• 隠れ変数を含む多重検定は、隠れ変数情

報の共有によって性能が大きく向上する

• 理論的側面の整備は不十分