Microsoft PowerPoint - ShinIshii

Size: px

Start display at page:

Download "Microsoft PowerPoint - ShinIshii"

やすもりさだい
5 years ago
Views:

1 誤り訂正出力符号の拡張による多値判別法とその応用奈良先端科学技術大学院大学石井信竹之内高志大羽成征行縄直人

2 多値判別の一般的枠組み {, L, } ラベル x : 入力 y G : F x, y R : 判別関数 arg max y F x, y でラベルを決める F x, y をどの様に構成するのか? p x, y : x, yの同時分布 F x, y u p y x とするとベイズ最適 uz は単調増加関数

3 多値判別関数 Fx,y を直接構成する Fsher の線形判別関数 Mult-class SVM, AdaBoost, Fx,y を値判別関数の組み合わせで構成する Error correctng output codng ECOC に基づく手法 Bradley-Terry モデル Haste & Tbshran, Yuknawa, et al. クラス所属確率 py x を推定できる確率出力を持つ値判別器が必要例題ごとに事後確率を計算する必要がある Loss-based decodng Detterch & Bakr, Allwen, et al. 単純な Hammng decodng を含む実装が簡単クラス所属確率に関しては言及しない

4 コード表 W : p G 行列 Class ECOC の定式化 W 値判別値判別値判別 : max p G 6 G+ + /

5 ハミング復号 0 y z 0 n n y z L L M W x z~ { }, x f { }, x f { }, x f p ハミング距離最小のコードワードによってラベルを決める

6 基本コンセプト,, ~ x x z p f f L 値判別器 ~ p f f f x x x z M M M, 0 y x z 各判別器の判別誤りビット反転ノイズ ~ z z p 確率モデル ~ max arg z z z p ~ ~ z z z z z p p p 復号法

7 確率モデルの仮定元,0,- 入力元出力,- 通信路多値判別における仮定各値判別器ビットは独立判別器ごとにノイズの性質が異なるパラメータはごとに決める非対称 False postve rate False negatve rate ε, ε f 0.

8 確率モデル p ~ z,, exp ~ z β γ δ ~ p z z Π ~ p z z p z z β z + γ ψ z, β, γ ψ z exp ~ δ, β, γ, ψ δ は正規化定数 δ ψ z z z ~ z ys z M ~ z M ŷ z p z~p

9 通信路の同定 n ~ L Z; β, γ,δ log p ~ z z ; β, γ, δ ~ βˆ, γ,δ ˆ ˆ arg max L ; β, γ, δ ˆ β ˆ ε ˆ ε log ˆ ε ˆ ε ˆ γ β, γ, δ Z ˆ ε ˆ ε log ˆ ε ˆ ε ˆ δ fˆ log fˆ ˆ ε, ˆ ε ˆ ε ˆ ε が小さい程大きい z 0のコードに対する非対称性 I z, z% : false negatve rate I z I z, z% I z 0, ~ z : false postve rate fˆ I z I z 0 ˆ ε, ˆ ε な程大きいがアンバランス

10 ラベルの復号 p z ~ z p ~ z z; β, ˆ γ,δ ˆ ˆ p z p ~ z; β, ˆ γ,δ ˆ ˆ zˆ arg max z p z ~ z で復号 MAP 復号 p zのパターンは本来個 n I y 判別問題ではp z n 0 f z W の列 otherwse 探索すべきzはGパターンのみ

11 Hammng decodng との関連 p y : 一様分布 γ 0, δ 0, L, p p p z ~ z exp β ~ z z arg max p z ~ z arg max ハミング復号の仮定各値判別器が同じ性質を持つ種の過誤の割合が等しい各クラスが同じサンプル数を持つ z z p β ~ z 重みつき Hammng dstance z

12 確率モデル z ~ z y z M z p M ~ z M z~ z~p p ŷ z z, L, z p はWの列しか値をとれない ~ z exp ~ T z Β / exp ~ T p y y z Β y Β ~ z y : p ベクトル各判別器は独立

13 数値実験 : 人工データ 0 回の繰り返し 00 点の訓練データ 000 点のテストデータ評価モデルモデルおよびモデル各値判別器はSVM カーネルはRBFカーネルと多項式カーネル比較モデル Mult-class SVM C-SVM, Spoc-SVM カーネルはRBFカーネルと多項式カーネル各値判別器をSVMとしたECOCでHammng decodng

14 数値実験 : 人工データの例 x x

15 数値実験 : 訓練誤差 Tranng error Spoc.Rbf Spoc.Poly C.Rbf C.Poly Hamm.Rbf Hamm.Poly Prop.Rbf Prop.Poly Prop.Rbf Prop.Poly

16 数値実験 : テスト誤差 Test error Spoc.Rbf Spoc.Poly C.Rbf C.Poly Hamm.Rbf Hamm.Poly Prop.Rbf Prop.Poly Prop.Rbf Prop.Poly

17 UCI データセット : テスト誤差 Spoc-svm:RBF C-svm: RBF Proposed: RBF Spoc-svm: Poly C-svm: Poly Proposed: Poly Ann-thyrod Satmage Segmentaton Irs 0.09± ± ± ± ± ± Wne 0.08± ± ± ± ± ± Glass 0.86± ± ± ± ± ±0.007

18 マルチカテゴリ問題マルチカテゴリ問題とは入力に複数のラベルタグが付与されている問題例 WEB におけるテキスト分類 Gmal 等メール仕事メール M 既存手法 : 各カテゴリを判別問題として解く多項分布の拡張 PMM SVM を応用遊び友人メルマガカテゴリ

19 値判別器のナイーブな適用入力 x x x x x カテゴリラベル列 y, -,,, - -,,, -, - 判別器 f カテゴリカテゴリ以外判別器 f カテゴリカテゴリ以外判別器 f カテゴリ以外カテゴリ予測 : f x, f x, f x

20 ECOC によるマルチカテゴリ分類入力 x x x x カテゴリラベル y パリティビット列 z, -,, -,,, 0,, - 0,, -, 0, + -,,, 0,,-,-, -, - -,, -, 0, 0 パリティ zzy はカテゴリラベル列 y から一意に決まる f x f, f, f g x g, g, g, g, g 判別器の誤りビット反転ノイズ p f x, g x y を同定

21 マルチカテゴリの推定カテゴリラベル列 y の推定 MAP 復号 arg max p y f x, g x 問題点 : 可能な y のバリエーションはカテゴリ数事前分布による拘束 y p y f x, g x p f x, g x y p y 例各入力は一度に多くのカテゴリに含まれない近似的周辺化アルゴリズムの援用 Belef propagaton など

22 実験用データ x x

23 結果 : カテゴリの誤推定率 Test error SVM Proposed method Code length of party

24 ここまでのまとめ ECOC の枠組みに基づき多数の値判別器の組み合わせによる多値判別法を構成判別誤りの非対称性を考慮特殊な場合としてHammng decodngを含む Mult-class SVMよりも優れた性能マルチカテゴリ問題への応用カテゴリラベルにパリティを付加し冗長にすることで性能向上 Encodng 問題への拡張

25 UCI データセットの概要 Dataset #Total #Tranng #Test #Attrbutes #Classes Ann-thyrod Satmage Segmentaton Irs Wne Glass fold CV fold cross-valdaton を 00 回行い平均挙動を見る

26 UCI データセット : 訓練誤差 Spoc-svm: RBF C-svm: RBF Proposed: RBF Spoc-svm:Poly C-svm:Poly Proposed:Poly Ann-thyrod Satmage Segmentaton Irs 0.08± ± ± ± ± ±0.008 Wne ± ± ± ± ± ± Glass 0.068± ± ± ± ± ±0.00

27 多重検定の問題典型例遺伝子発現に基づく有意遺伝子の抽出およびそれを用いた判別良いスコア検定統計量の選び方良いしきい値の決め方検定誤差の見積もり方各個検定が最適であること vs. 多重検定が全体として最適であること

28 有意遺伝子選択の問題 class tumor samples class non-tumor samples μ σ μ μ μ 対立仮説 H : gene s actve 対立モデル尤度 : M g μ, μ, σ N x ; μ, σ D 遺伝子の発現レベル x 帰無仮説 H 0 : 帰無モデル尤度 : f μ μ gene s nactve M σ N x ;0, σ

29 Neyman-Peason s lemma 対立モデルの尤度 g 尤度比は最強の検定スコアである f 一定の有意水準 P FP α のもとで検出力 P FN β が最大帰無モデルの尤度単純仮説パラメータを持たないが前提非単純仮説では最尤推定値をプラグインした尤度比が漸近的に最強 g θˆ f ϕˆ

30 遺伝子の有意性スコア t-score 正規モデルの尤度比スコア.e. S/N rato m m m : 各クラス内標本平均 S S : クラス内標準偏差両クラス共通 SAM score Tusher, Tbshran & Chu, 00 m S Emprcal Bayes score Efron, 00 m + S 0 S 0 : 全遺伝子で共通の定数仮説の事後確率をスコアとする事前分布 Pσ に関して多重性を利用した経験ベイズ推定値に基くさまざまな細かい改良 μ μ σ

31 多重検定における最良さ多重性を利用した場合に単純な個別検定の繰り返しよりも良い検定ができないか? 最良の多重検定スコアの定義 EFP E[FPR] が同程度である統計的検定の中で ETP E[-FNR] を最大にする統計的検定を optmal dscovery procedure ODP と呼ぶ Storey, 00 FPR: false postve rate FDR 第一種の過誤 FNR: false negatve rate 第二種の過誤

32 ODP lemma Storey, 00 以下の統計量に基く検定は ODP である前提 : N 個の単純帰無仮説 f, f,..., f N と N 個の単純対立仮説 g, g,..., g N に基く多重検定 f f f g g g S N M M M ODP G G f g ただし G {,,..., M } は対立仮説が真である遺伝子の集合 G 0 { M+, M+,..., N } は帰無仮説が真である遺伝子の集合 S ODP を全遺伝子,,N に対して共通の統計量として用い共通のしきい値を設定

33 漸近 ODP 各を構成するサンプル数無限大の極限で一致 0 G G ODP f g S 0 ˆ ˆ ˆ ˆ G ODP f g S φ θ 非単純仮説では帰無対立仮説の確率密度関数は最尤推定パラメータに基いて決定実際の多重検定状況では真の集合 G 0, G は未知そこで適当なしきい値にもとづく尤度比検定による決定で近似

34 潜在変数モデルを対立仮説とした遺伝子選択 g θ p x 各サンプルの所属クラス k が必ずしも観測されない場合 expresson level of gene at sample class label pror of class k center of class k for gene ntra-class varance of gene common among classes k, 教師無し遺伝子選択準教師付き遺伝子選択

35 教師あり教師なし準教師ありスコア教師付き : Pk P k y I k y 帰無仮説モデル H 0 : μ μ 対立仮説モデル H : μ μ このとき尤度比スコアは t- 検定で使われる S/N 比と全く同等

36 隠れ変数モデルに対する ODP ODPp パラメータを共有する ODP パラメータと隠れ変数を共有する ˆ ˆ g g θ ˆ, ˆ Z g g θ 0 ˆ ˆ ˆ ˆ G ODP f g S,..., arg max ˆ θ θ θ M x x p k M k p k x p, max arg θ θ θ ˆ,, } { def :, : k k M k x k p Z Z Z θ M k k k x N Z ˆ, ˆ σ μ M k k x N k P ˆ, ˆ σ μ

37 評価用人工データ nactve genes actve genes 非癌癌癌 / 非癌以外の 8 種の特徴量のいずれかに関して活性である遺伝子癌 / 非癌ラベルに対して活性である遺伝子

38 教師あり教師なしスコア非癌癌 nactve actve Supervsed score が検出したい遺伝子分類 nactve actve Unsupervsed score が検出したい遺伝子分類

39 教師なしスコアの比較 Lkelhood Rato ODPp θ のみ共有 ODP θ と Z を共有

40 準教師ありスコアの比較 Observaton tumor non-tumor unknown samples nactve genes actve genes

41 準教師ありスコア : 実データ前立腺がんデータ公開 - 癌組織 0 正常組織 - 約万遺伝子全 N 症例のクラスラベルのうち一部 ~ 全部を隠した場合のスコアランキングの変化オリジナルランキングと一部ラベルに基くランキングとの間の Spearman 順位相関

42 準教師ありスコア : 実データ大腸がんデータ - 0 癌組織正常組織 - 約 000 遺伝子ラベルの順位相関オリジナルの上位 % 遺伝子検出に関する AUC

43 多重検定スコアのまとめ ODP は多重検定スコアの最適性を Neyman-Pearson の拡張によって定義する隠れ変数モデルを対立仮説とするとき ODP には種類の自然な実装法がある隠れ変数を含む多重検定は隠れ変数情報の共有によって性能が大きく向上する理論的側面の整備は不十分

Microsoft PowerPoint - H17-5時限（パターン認識）.ppt

Microsoft PowerPoint - H17-5時限（パターン認識）.ppt パターン認識早稲田大学講義平成 7 年度独産業技術総合研究所栗田多喜夫赤穂昭太郎統計的特徴抽出パターン認識過程特徴抽出認識対象から何らかの特徴量を計測抽出する必要がある認識に有効な情報特徴を抽出し次元を縮小した効率の良い空間を構成する過程文字認識 : スキャナ等で取り込んだ画像から文字の識別に必要な本質的な特徴のみを抽出例文字線の傾き曲率面積など識別与えられた未知の対象を