Document

誤り訂正出力符号の拡張による
多値判別法とその応用
奈良先端科学技術大学院大学
石井信
竹之内高志大羽成征行縄直人
多値判別の一般的枠組み
・ x : 入力、 y  1,, G:ラベル
・ F (x, y)  R : 判別関数
arg maxy F (x, y)でラベルを決める
F (x, y)をどの様に構成するのか？
・ p(x, y) : x, yの同時分布
F (x, y)  u( p( y | x))とするとベイズ最適
u(z)は単調増加関数
• 多値判別関数 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 行列
Class １
２
３
 1 1 1 


 1 1  1 
 1 1 1 
W 

 1 1 0 
 1 0 1 


1 1 
 0
2値判別１
2値判別２
2値判別３
:
G
G 1
max p  (3  2  1) / 2
2 3 4
5
6
1 6 25 90 301
ハミング復号
y
1

 1
 
 1
 1
1
z  
 1
 0
 
 1
 y
xi
n
W

 1
 
 1
 n  1
z  
 1
 1
 
 0
f1 ( x)  1,1
f 2 ( x)  1,1

f p ( x) 1,1
~z i
 1 1

 1 1
 1 1

 1 1

 1 0

 0 1
ハミング距離最小のコードワードによってラベルを決める
 1
1
1
0
1
 1
基本コンセプト
2値判別器 ~
z  ( f1 (x),, f p (x))
(xi , y i )
確率モデル
p( ~
z | z)

 1 
 
 1
 1 
i
z  
 1 
 0
 
 1
 f1 ( x i ) 


 f 2 (xi ) 



~z i  






 f (x i ) 
 p

各判別器の判別誤り
ビット反転ノイズ
復号法
arg maxz p(z | ~
z)
p(z | ~
z )  p(~
z | z ) p(z )
確率モデルの仮定
• ３元（1,0,-1）入力、２元出力(1,-1)通信路
• 多値判別における仮定
– 各2値判別器（ビット）は独立
– 判別器ごとにノイズの性質が異なる
• パラメータは j ごとに決める
– 非対称
False positive rate ≠
False negative rate
1   2 , f  0.5
確率モデル１
z 2j
~
~
・ p( z j | z j  j ,  j ,  j )  exp z j (  j z j   j )  1 ( z j ,  j ,  j ) 
1 z 2j
~
 exp z j j  2 ( j ) 
1 ( z j ,  j ,  j ), 2 ( j )は正規化定数
・ p(~
z | z)   pj1 p(~
zj | zj)
y (s)
z1
~z
1
z2
~
z2


zp
~
zp
yˆ
通信路の同定
n
~
・ L( Z ; β, γ, δ)   log p(~
z i | z i ; β, γ, δ)
i 1
~
ˆ
ˆ
ˆ
(β, γ, δ)  arg maxβ, γ,δ L(Z ; β, γ, δ)
ˆ
ˆ
ˆ
f
(
1


)

ˆ
ˆ
1
1
(
1


)(
1


)
j
1
j
2
j
1
1j
2j
ˆ
ˆ


log
ˆ
 j  log
・  j  log
j
2
ˆ
ˆ
1  fˆ j
4
1 j (1   2 j )
4
ˆ1 jˆ2 j
ˆ1 j , ˆ2 jが小さい程大きい
ˆ1 j , ˆ2 jがアンバランス
な程大きい
ˆ1 j
i
i
j
i
j
i
ˆ2 j
z j  0のコードに対する非対称性
I(z  1, z  1)


: false negative rate
 I(z  1)
I(z  1, z  1)


: false positive rate
 I(z  1)
i
j
i
i
j
i
i
j
i
j
fˆ j 
i
i
~
I(
z

0
,
z
i j
j  1)
i
I(
z
i j  0)
ラベルの復号
~
p
(
z | z; βˆ , γˆ , δˆ ) p(z)
~
・ p( z | z ) 
p(~
z ; βˆ , γˆ , δˆ )
zˆ  arg maxz p(z | ~
z )で復号（ MAP復号）
zのパターンは本来 2 p 個
1 n
i
I
(
y
 j ) if z  W のj列
 
判別問題ではp(z)   n i 1
0
otherwise

探索すべきzはGパターンのみ
Hamming decodingとの関連
・ p( y) : 一様分布、  j  0,  j  0( j  1,, p)
p


~
~
 p(z | z )  exp   j z j z j 
 j 1

arg max p(z | ~
z )  arg max
z
z
1 ~
zjzj
p

j 1
j
2
 重みつき Hamming distance
 ハミング復号の仮定
 各2値判別器が同じ性質を持つ
 2種の過誤の割合が等しい
 各クラスが同じサンプル数を持つ
確率モデル２
yy
z1
~z
11
z2
~
z2


zp

~
~
zz p
yˆ
p
z  ( z1,, z p )はWの列しか値をとれない
p(~
z | y)  exp(~
z T  y ) /  exp(~
zT y )
~
z
 y : p 1ベクトル
各判別器は独立
数値実験：人工データ
• 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.03967±0.00784 0.04027±0.00715
0.03600±0.00858 0.03667±0.00790 0.03380±0.00859
Wine
0.01834±0.00817 0.01331±0.00488 0.01291±0.00419
0.03286±0.00793 0.03794±0.00914 0.03360±0.00996
Glass
0.14862±0.01241 0.16400±0.01278 0.13424±0.01178
0.07595±0.01323 0.06805±0.01000 0.04852±0.00715
マルチカテゴリ問題
• マルチカテゴリ問題とは
– 入力に複数のラベル（タグ）が付与されている問題
• 例）WEBにおけるテキスト分類、Gmail等
仕事
1
遊び
1
友人
1
メルマガ
1
メール１
メール２

• 既存手法：
– 各カテゴリを判別問題として解く
– 多項分布の拡張（PMM)
– SVMを応用
カテゴリ
2値判別器のナイーブな適用
入力x
判別器
f1
カテゴリラベル列y
1 2 3
x1
x2
x3
x4
カテゴリ1以外
( 1, -1, 1)
( 1, 1, -1)
(-1, 1, 1)
( 1, -1, -1)
カテゴリ1
判別器
f2
カテゴリ2
カテゴリ2以外
判別器
f3
カテゴリ3
カテゴリ3以外
予測 :
( f 1(x), f 2(x), f 3(x))
ECOCによるマルチカテゴリ分類
入力
x1
x2
x3
x4
カテゴリラベルｙ
1 2 3
パリティビット列ｚ
1 2 3 4 5
( 1, -1, 1) ( 1, -1, 1, 1, 0)
( 1, 1, -1) ( 0, 1, -1, 0, 1)
+
(-1, 1, 1) ( 1, 0, 1,-1,-1)
( 1, -1, -1) ( -1, 1, -1, 0, 0)
パリティz=z(y)はカテゴ
リラベル列ｙから一意に
決まる
f (x)  ( f1 , f 2 , f3 ) g(x)  ( g1 , g2 , g3 , g4 , g5 )
判別器の誤り⇔ビット反転ノイズ
p(f (x), g(x) | y)を同定
マルチカテゴリの推定
• カテゴリラベル列 y の推定（MAP復号）
argmaxy p( y | f (x), g(x))
p( y | f (x), g(x))  p(f (x), g(x) | y) p( y)
• 問題点：可能な y のバリエーションは 2カテゴリ数
– 事前分布による拘束
• （例）各入力は一度に多くのカテゴリに含まれない
– 近似的周辺化アルゴリズムの援用
• Belief propagation など
実験用データ
結果：カテゴリの誤推定率
ここまでのまとめ
• 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
5 - fold CV
 100
9
6
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.02478±0.00266 0.02290±0.00253
0.02422±0.00239 0.02408±0.00283 0.02343±0.00248
Wine
0.00063±0.00078 0.00476±0.00123 0.00445±0.00106
0.00000±0.00000 0.00000±0.00000 0.00000±0.00000
Glass
0.06481±0.00620 0.08886±0.00781 0.04509±0.00310
0.00931±0.00204 0.00581±0.00119 0.00676±0.00143
多重検定の問題
• （典型例）遺伝子発現に基づく有意遺伝子
の抽出およびそれを用いた判別
 良いスコア（検定統計量）の選び方
 良いしきい値の決め方
 検定誤差の見積もり方
各個検定が最適であること
vs.
多重検定が全体として最適であること
有意遺伝子選択の問題
class 1
(tumor samples)
class 2
(non-tumor samples)
si
対立仮説 H1:
対立モデル尤度:
遺伝子 i の
mi1 mi2
mi1 = mi2
発現レベル xi
gene i is active
M
g ( X i | mi1 , mi 2 , s i )   N ( xij ; miDj , s i2 )
j 1
帰無仮説 H0:
mi1 = mi2
gene i is inactive
M
2
帰無モデル尤度: f ( X i | s i )   N ( xij ;0, s i )
j 1
Neyman-Peason’s lemma
対立モデルの尤度
g( X )
「尤度比は最強の検定スコアである」
一定の有意水準 P( FP ) = a のもとで、
検出力 ( 1P( FN ) = 1 ) が最大
f (X )
帰無モデルの尤度
• 単純仮説(パラメータを持たない)が前提
• 非単純仮説では最尤推定値をプラグイン
した尤度比が漸近的に最強
ˆ
g ( X | i )
f ( X | ˆi )
遺伝子の有意性スコア
si
• t-score (正規モデルの尤度比スコア)
– i.e. S/N ratio
| mi1  mi 2 |
Si
mi1 mi2
mij : 各クラス内標本平均
Si : クラス内標準偏差(両クラス共通)
• SAM score (Tusher, Tibshirani & Chu, 2001)
| mi1  mi 2 |
Si  S 0
S0 : 全遺伝子で共通の定数
• Empirical Bayes score (Efron, 2002)
– 仮説の事後確率をスコアとする
– 事前分布 P(si) に関して多重性を利用した経験ベイズ推
定値に基く
さまざまな細かい改良
多重検定における最良さ
• 多重性を利用した場合に、単純な個別検定
の繰り返しよりも良い検定ができないか？
• 「最良」の多重検定スコアの定義
EFP = E[FPR] が同程度である統計的検定の中で
ETP = E[1-FNR] を最大にする統計的検定を
optimal discovery procedure (ODP) と呼ぶ
(Storey, 2005)
– FPR: false positive rate (FDR) （第一種の過誤）
– FNR: false negative rate （第二種の過誤）
ODP lemma
•
(Storey, 2005)
「以下の統計量に基く検定は ODP である」
g1 ( X )  g 2 ( X )  ...  g M ( X )
SODP ( X ) 

f M 1 ( X )  f M  2 ( X )  ...  f N ( X )
 g (X )
iG1
i
 f (X )
iG0
i
ただし、 G1 = { 1, 2, ..., M } は対立仮説が真である遺伝子の集合、
G0 = { M+1, M+2, ..., N } は帰無仮説が真である遺伝子の集合
• 前提：
– N個の単純帰無仮説 f1(X), f2(X), ..., fN(X)と
N個の単純対立仮説 g1(X), g2(X), ..., gN(X)に基く多重検定
– SODP (X ) を全遺伝子 i=1,…,N に対して共通の統計量
として用い、共通のしきい値を設定
漸近ODP
S ODP ( X ) 
 g (X )
iG1
i
 f (X )
iG0
i
実際の多重検定状況では
真の集合 G0, G1 は未知
そこで適当なしきい値にもとづく
尤度比検定による決定で近似
SˆODP
 g ( X | ˆ )
(X ) 
ˆ)
f
(
X
|


i
i
i
i
i
iGˆ 0
非単純仮説では
帰無・対立仮説の確率密度関数
は最尤推定パラメータに基いて
決定
• 各X を構成するサンプル数無限大の極限で一致
潜在変数モデルを対立仮説とした
遺伝子選択
g ( X | i )   p( xi( j ) )
j
• 各サンプル j の所属クラス k が必ずしも観測さ
れない場合
expression level
of gene i at sample j
center of class k
class label
for gene i
prior of class k
intra-class variance
of gene i
(common among
classes k=1,2)
• 教師無し遺伝子選択・準教師付き遺伝子選択
教師あり、教師なし、準教師ありスコア
• 教師付き： P(k)  P( k | y(j) )= I( k = y(j) )
– 帰無仮説モデル H0: mi1 = mi2
– 対立仮説モデル H1: mi1 = mi2
このとき、尤度比スコアはt-検定で使われる S/N 比と全く同等
隠れ変数モデルに対するODP
SˆODP
•ODPp パラメータを共有する
gˆ i ( X )  g ( X | ˆi )
 gˆ ( X )
(X ) 
 fˆ ( X )
i
i
iGˆ 0
i
ˆi  arg max p( xi(1) ,..., xi( M ) |  )


( j)

    P(k ) N ( xi | mˆ ik , sˆ i ) 
M
j 1  k
  arg max p( xi( j ) | ki( j ) , ) p(ki( j ) |  )
M

•ODP パラメータと隠れ変数を共有する
gˆ i ( X )  g ( X | Zi ,ˆi )


( j)
    Zijk N ( xi | mˆ ik , sˆ i ) 
j 1  k

M
k
j 1
Z i  {Z ijk } j 1:M ,k 1:2 ,
def
Z ijk  p(ki( j ) | xi( j ) ,ˆi )
評価用人工データ
inactive genes
active genes
非癌
癌
癌/非癌ラベルに対して
活性である遺伝子
癌/非癌以外の
8種の特徴量のいずれかに関して
活性である遺伝子
教師あり、教師なしスコア
非癌
癌
active
inactive
Supervised score が検出したい遺伝子分類
inactive
active
Unsupervised score が検出したい遺伝子分類
教師なしスコアの比較
Likelihood
Ratio
ODPp
θ のみ共有
ODP
θ と Z を共有
準教師ありスコアの比較
Observation
tumor
non-tumor
unknown samples
inactive genes
active genes
準教師ありスコア：実データ
前立腺がんデータ（公開）
- 52 癌組織 × 50 正常組織
- 約 1万遺伝子
全N症例のクラスラベルのうち
一部～全部を隠した場合の
スコアランキングの変化
オリジナルランキングと
一部ラベルに基くランキングと
の間の Spearman 順位相関
準教師ありスコア：実データ
大腸がんデータ
- 40 癌組織
× 22 正常組織
- 約 2000遺伝子
ラベルの順位相関
オリジナルの
上位 1%遺伝子
検出に関するAUC
多重検定スコアのまとめ
• ODP は、多重検定スコアの最適性を
Neyman-Pearson の拡張によって定義する
• 隠れ変数モデルを対立仮説とするとき、
ODP には 2種類の自然な実装法がある
• 隠れ変数を含む多重検定は、隠れ変数情
報の共有によって性能が大きく向上する
• 理論的側面の整備は不十分

Download Report