誤り訂正出力符号の拡張によ る 多値判別法とその応用

誤り訂正出力符号の拡張によ 多値判別法とその応用 る

奈良先端科学技術大学院大学 石井　信

竹之内高志　大羽成征　行縄直人

多値判別の一般的枠組み

  ラベル

入力、

・ x : y  1 ,  , G : 判別関数

・ F ( x , y )  R :

でラベルを決める )

, ( max

arg

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 





Class　１　　　２　　　３

2 値判別１

2 値判別２

2 値判別３

:

2 3 4 5 6

1 6 25 90 301

ハミング復号

1

1

1 1 1 1 0

1 y



  

 

 

  

     

 

 

 

  z

1 1 1 1 1 0

n

n

y



 

  

 

  

     

 

 

 

  z



 

W x

z

~

 ^{1 , 1} 

)

1

( x  

f

 ^{1 , 1} 

)

2

( x  

f

 ^{1 , 1} 

)

( x  

f





 

 

 

 

























1 1

0

1 0

1

0 1

1

1 1

1

1 1

1

1 1

1

基本コンセプト

)) (

, ),

(

~ (

2 値判別器 z  f

x  f

x

 

 

 

 





 

 

 

 







) (

) (

) (

~

2 1

i p

i i

i

f f f

x x x

z





 ( , )

1 1 1 1 0

1

i i

i

y



  

   

  

  

  

   

    x

z 　 　 　 　 　

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

 )

~ | ( z z p

確率モデル

~ )

| ( max

arg

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

   

確率モデル１

 ^{~ ( ) ( , , )} 

exp )

, ,

~ |

( z

z

z

z

z

p           

・

は正規化定数 )

( ),

, ,

(

1

z





 

 )

~ | ( )

~ |

(

p z

z

p z z  

・

 ^~

^{( )} 

exp z



   

) (s y

z

z

 z

~ z

~ z

 z

~

y ˆ

通信路の同定





i

i

p

Z L

1

)

;

~ | ( log )

~ ;

( β, γ, δ z z β, γ, δ

・

)

~ ; ( max

arg ˆ )

ˆ ˆ

( β , γ , δ 

L Z β, γ, δ

称性 のコードに対する非対

 0 zj 1

I( 1, 1)

ˆ : false negative rate

I( 1)

i i

j j

i

j i

i j

z z

  ^z ^{ }



 

2

I( 1, 1)

ˆ : false positive rate

i i

j j

i

j i

z z

  ^{  }

 

 

^







 ⁱ _i

i j i

j

j z

z f z

) 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 ) (

1 I )

(

判別問題では

y j W j p n

n i

i

z

z

復号）

で復号（

MAP

~ )

| ( max

ˆ arg z z

z 

p

パターンのみ は

探索すべき

z G

のパターンは本来

2

z

Hamming decoding との関連

) , ,

1 (

0 ,

0 :

)

( y j p

p



 

  

・

 

 



 

 

 p j

j j j

z z p

1

exp ~

~ )

|

( z z 







j

j j j

z p z

1

2

1 ~ max

arg

~ )

| ( max

arg

z z



Hamming distance



 ハミング復号の仮定



2

 2



確率モデル２

 ^





z

z z

z

~

exp( ~ )

/

~ ) exp(

)

~ |

( y

p

ベクトル

1

: 



p

各判別器は独立

の列しか値をとれない は

W

z z , ,

) (



 z

z

~

~ z

y

~ z



y ˆ y 

z

z

 z

~ z

~ z

 z

~

y ˆ

数値実験：人工データ

• 50

– 200

2000

•

–

1

2 –

2

SVM

–

RBF

•

– Multi-class SVM (C-SVM, Spoc-SVM)

–

RBF

–

2

SVM

ECOC

Hamming

decoding

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

数値実験：訓練誤差

数値実験：テスト誤差

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

Spoc-svm:RBF 差

Spoc-svm: Poly

C-svm: RBF C-svm: Poly

Proposed: RBF Proposed: Poly Ann-thyroid 0.05076

0.04142

0.05309 0.03384

0.03501 0.03355

Satimage 0.11750

0.16400

0.12050 0.14050

0.12150 0.14550 Segmentation 0.16400

0.07381

0.17048 0.05810

0.15143 0.07619 Iris 0.04293±0.00896

0.03600±0.00858

0.03967±0.00784 0.03667±0.00790

0.04027±0.00715 0.03380±0.00859 Wine 0.01834±0.00817

0.03286±0.00793

0.01331±0.00488 0.03794±0.00914

0.01291±0.00419

0.03360±0.00996

Glass 0.14862±0.01241 0.16400±0.01278 0.13424±0.01178

マルチカテゴリ問題

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

–

• 例） WEB におけるテキスト分類、 Gmail 等

仕事 遊び 友人



メール１

1

1

 1

 1

メール２

 1 1 1

 1

• 既存手法：

–

–

PMM)

– SVM

カテゴ リ

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

カテゴリ 1

カテゴリ 1 以外

判別器

f1

判別器

f2

カテゴリ

2 カテゴリ 2 以外

判別器

f3

カテゴリ 3

　入力 x カテゴリラベル 列 y

　　　 1 　 2 　 3

( 1, -1, -1) ( 1, 1, -1) ( 1, -1, 1) (-1, 1, 1) x

x

x

x

予測 :

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

p ( f ( x ), g ( x ) | y )

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

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

( 1, -1, -1) ( 1, 1, -1) ( 1, -1, 1) (-1, 1, 1) x

x

x

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

p y f x g x

実験用データ

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

ここまでのまとめ

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

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

–

–

Hamming decoding

– Multi-class SVM

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

–

• Encoding 問題への拡張

UCI データセットの概要

Dataset #Total #Training #Test #Attributes #Classes

Ann-thyroid 7200 3772 3428 21 3

Satimage 6435 4435 2000 36 6

Segmentation 2310 210 2100 19 7

Iris 150 4 3

Wine 178 3 3

Glass 214 9 6

CV fold

- 5

 100

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

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

Spoc-svm: RBF Spoc-svm:Poly

C-svm: RBF C-svm:Poly

Proposed: RBF Proposed:Poly Ann-thyroid 0.04348

0.02572

0.04745 0.02333

0.02519 0.02386

Satimage 0.09515

0.12469

0.10688 0.10485

0.10462 0.11995 Segmentation 0.11429

0.02857

0.17143 0.00952

0.12381 0.03333 Iris 0.02248±0.00241

0.02422±0.00239

0.02478±0.00266 0.02408±0.00283

0.02290±0.00253 0.02343±0.00248 Wine 0.00063±0.00078

0.00000±0.00000

0.00476±0.00123 0.00000±0.00000

0.00445±0.00106 0.00000±0.00000 Glass 0.06481±0.00620

0.00931±0.00204

0.08886±0.00781 0.00581±0.00119

0.04509±0.00310

0.00676±0.00143

多重検定の問題

• （典型例）遺伝子発現に基づく有意遺 伝子の抽出およびそれを用いた判別

 良いスコア（検定統計量）の選 び方  良いしきい値の決め方

 検定誤差の見積もり方

各個検定が最適であること

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

vs.

遺伝子 i の 発現レベル　

x









= 

対立仮説

H

:

gene i is active

:





j

i iDj ij

i i

i

i

N x

X g

1

2 2

1

, , ) ( ; , )

|

(     



= 

帰無仮説

H

:

gene i is inactive





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

f X

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

S m

m |

|



_m

_:

S

:

_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]

optimal discovery procedure (ODP)

ODP lemma (Storey, 2005)

•

ODP

•

– N

f

(X), f

(X), ..., f

(X)

N

g

(X), g

(X), ..., g

(X)

–

) (

...

) (

) (

) (

...

) (

) ) (

(

2 1

2 1

X f

X f

X f

X g

X g

X X g

S

N M

M ODP M











 













0 1

) (

) (

G i

i G i

i

X f

X g

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

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

) ( X

S

_i=1,…,N

　　として用い、共通のしきい値を設定

漸近 ODP

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









0 1

) (

) (

) (

G i

i G i

i

ODP

f X

X g

X

S 







ˆ0

ˆ )

| (

ˆ )

| (

) ˆ (

G i

i i

i

i i

ODP

f X

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

: 

= 

– 対立仮説モデル H

: 

= 

このとき、尤度比スコアは

t-

S/N

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

•ODPp パラメータを共有する

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

ˆ )

| (

)

ˆ _i ( X g X _i

g  

ˆ ) ,

| (

)

ˆ _i ( X g X Z _{i i}

g  _ 









ˆ0

) ˆ (

) ˆ (

) ˆ (

G i

i i

i

ODP

f X

X g X

S

)

| ,...,

( max

ˆ arg





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









 

 

 







j k

i ik

j i ijk

N x Z

1

)

(

| ˆ , ˆ )

(  

 

 

 







j k

i ik j

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

オリジナルランキングと

一部ラベルに基くランキングと

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

大腸がんデータ

- 40

× 22

-

2000

ラベルの順位相関 ^{オリジナルの}

上位 1% 遺伝子 検出に関する AUC

多重検定スコアのまとめ

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

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

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

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

• 隠れ変数を含む多重検定は、隠れ変数情 報の共有によって性能が大きく向上する

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