カテゴリー別アーカイブ: Paper

読んだ論文のまとめなど

Learning Using Privileged Information: SVM+ and Weighted SVM

June 2013, M. Lapin+

=

学習アルゴリズムに事前知識(prior knowledge)を組み込むことで、

- 学習アルゴリズムの識別率向上
- 訓練に必要なデータ量の削減

が行える。
Vapnikら(2009)によって提案されたLUPI(Learning Using Privileged Information)パラダイムでは、訓練時にのみ使用できる付加情報を利用することでこれを可能にしている。

本論文では、

- privileged information(特権情報?)を重要度の重み付けに利用
- privileged features(特権特徴量)として表現可能な事前知識を、それぞれの訓練事例についての重みによって表現

Weighted SVMがSVM+の解を常に再現する一方、収束せずSVM+の限界となる反例を示す。
privileged informationが利用できない場合のweighted SVMの重み選択問題についても触れる。

=

# 事前知識、特権情報、重み
分類問題において、訓練データの量が限られている場合、訓練用サンプルに加えて利用可能な情報ー事前知識(prior knowledge)ーは識別性能の改善にとって重要な要素。
事前知識は異なる形式をとり、学習問題への組み込み方はアルゴリズムと同様に、独特の設定が必要。
二値分類での事前知識のSVM(Support Vector Machine)への導入に焦点を当てて解説する。

Lauer & Bloch (2008)では、事前知識をSVMに組み込むための異なる方法をレビューし、それらの方法を事前知識の型(type)に応じて分類。

本論文では、目的関数に関するものよりも、”訓練データに関する付加情報”についての場合を考える。

厳密でないが関連する設定としては、半教師あり学習のアプローチがあり、ラベルづけされていないデータが入力空間における周辺分布についてのある情報をもっているというもの。

Vapnik & Vashist(2009)において、LUPI(Learning Using Privileged Information)パラダイムが提案された。
この中では、付加情報は特権特徴量(privileged features)という形式をとり、これは訓練時に利用できるが、テスト時には使用できない。
これらの特徴量は
- 損失関数の上界をパラメータ化
- 与えられた訓練サンプルについて最適な識別器の損失を推定
するのに使用される。

高い損失の値は、与えられたデータ点が外れ値である可能性がある場合の指標という見方もできる。
故に、外れ値でない場合とは異なる取り扱いをしなければならない。

訓練事例が外れ値である可能性がある場合の付加情報は、インスタンスの重みによってエンコードされる。
よって、LUPIフレームワークと重要度重み付けの関係は非常に近いものと予想できる。

重要度重み付けの場合、非負の重みをもつ各訓練事例は、エラーのコストのバランスをとるために損失関数で使用される。
インスタンスの重みが自然にできる典型的な例は、cost-sensitive learningである。(Elkan, 2001)

もしクラスに偏りがあったり、異なる誤分類エラーが異なるペナルティーを受けたりすることがあれば、事前知識をインスタンスの重みとしてエンコードできる。
データ点への高い重みづけは、学習アルゴリズムがその点を正しく、おそらく”重要ではない”として誤分類されたコストで、識別すべきであることを示唆している。

しかしながら、本論文では、cost-sensitiveな仮定を行わない。(つまり、異なるエラーはテスト集合について異なるコストを生むという仮定はしない)

代わりに、訓練集合とテスト集合での重要度重みづけを分ける。
これにより、もしそれによりよいモデルが得られるならば、外れ値に対して高い重みづけを行うこともできる。

事前知識の異なる形式が存在し、エンコードも異なる可能性がある。
本論文では、インスタンスの重みが”事前知識の同じ型”を表現でき、特権特徴量によってエンコードされることを示す。
特に、これにより重要度の重みづけがされたという点において特権特徴量の効果を説明できる。
驚くことに、結果の重みは外れ値を強調する。これはSVMのサポートベクターにも起こる。

SVMをLUPI frameworkに拡張するSVM+アルゴリズム。
凸解析の基本ツールを使い、SVM+解の一意性とその解がweighted SVM (WSVM)と関係することを求める。
SVM+の解とWSVMのインスタンス重みには、単純なつながりがある。
さらに、その関係がSVM+アルゴリズムのさらなる理解と、SVM+の限界を学ぶために使用できる。
WSVMにおけるインスタンス重みがSVM+の特権特徴量のように同じ目的を持っていることを見た上で、特権特徴量が使用できない場合の重み選択の問題に戻る。

- SVM+のnon-trivialな解が主形式において一意であることを示す。オフセットbが一意でないWSVMよりも強い解。
- SVM+を双対最適化問題に変形。WSVMアルゴリズムと密接な繋がりがあることを明らかにする。特に任意のSVM+双対解がWSVMに対する重みを構成できることを示す。適切な重み選択によりWSVMがSVM+を擬似的に模倣できることを示し、これによりSVM+の解からWSVMの解を求めることが常に可能である。
- WSVMの解からSVM+の解が求められるかを調べる(つまり2つのアルゴリズムが同値かどうか)。同値になる必要十分条件を与え、SVM+の解がWSVMの解のstrict subsetになっていることを明らかにする。WSVMの解がSVM+によって求められない場合の例を示す。
- 特権特徴量がない場合の重み選択問題に帰着

(書きかけメモ)

[Connectome] Contour-Propagation Algorithms for Semi-Automated Reconstruction of Neural Processes

Mache et al., 2007 より

新しい技法である”Serial Block Face Scanning Electron Microscopy(SBFSEM)”は電子顕微鏡での生物組織のsectioningとimagingの自動化を可能にした。 (Denk and Horstmann, 2004)
この技法による画像のスタックは、シナプス構造を含む異なる細胞の部分を区別するのに十分な解像度をもち、これにより完全な神経回路の解剖学的知識の詳細が得られる。
画像のスタックは数千枚の画像からなり、最小ボクセルサイズはx-y軸が10-20nm、y軸が30nm。数百TB。(Briggman and Denk, 2006)
故に、(人の手で作業するには膨大で)高度な3D再構築自動化アルゴリズムが必要とされている。

最初のステップとして、細胞膜の正確な輪郭トレースのための半自動化アルゴリズムを開発。
画像のスタックのセグメント間の抽出したオブジェクトの3D観測を可能にした。
手動でのトレーシングと比べると、処理時間は大幅に向上した。

本論では、ハエの視覚神経節の一部を再構築するアルゴリズムの開発を行っている。
(Strausfeld, 1984)によると、ハエの視覚システムは蛍光顕微鏡で見ることができる解像度では、すでによく観察されているが、ultrastructural levelの知識は、visual motion processingでの回路を見るために必要である。(Borst and Haag, 2002)

原理的には3次元画像ブロックを直接セグメント化することは可能であり、事前の画像から得られる情報を使って、シーケンス内の各画像のセグメントを選択した。

処理のステップ
1. 同じmedianとinter-quartile rangeを持つように各画像の輝度値 intensity value の正規化
2. 空間フィルタの適用。Gaussian broadeningか非線形拡散nonlinear diffusionを選択。(Perona and Malik, 1990)
非線形拡散は、ノイズ除去エッジ保存フィルタリング手法であり、各場所で輝度勾配の推定に依存するフィルタの度数をを決定。これにより、強いエッジは保存されるが、そうでない部分はかなり平滑化される。
MATLAB Toolbox(D’Almeida, 2000)を利用。
フィルタ性能がパラメータのとり方にsensitiveであることから、パラメータを最適化するのが望ましいadvisable。あるいは、人の手でラベルづけされた画像からフィルタを学習(Vollgraf et al., 2004)
3. 隣り合う画像同士のクロス相関を計算。これにより、欠陥画像の検知と除去が可能。例えばゴミが入ったりした場合に。

セグメンテーションアルゴリズム
一般的なアプローチ
スタック全体を一度にやるのではなく、シーケンシャルに行った。?
オブジェクトが隣接する画像にかけて連続していると仮定。
連続性を確かなものにするため、事前の画像のセグメンテーションからの情報と、現在の画像のピクセル強度 the pixel-intensities を組み合わせる必要がある。
一つの画像のセグメントは次の画像に伝播する。
ただし、最初の画像に対しては別の戦略を用いた。(後述)

Level Set 法
陽にオブジェクトの境界を表現する方法(例:スプライン関数)は使用せず、陰に符号化距離関数Φのゼロレベル集合を使用。
foregroundとbackgroundに分ける画像セグメントI:Ω->Rを探索。I(x)は画像のグレイスケール。
(Osher and Fedkiw, 2003; Sethian, 1999)によるレベル集合フレームワークでは、Ω+={x:Φ(x)>0}をforeground(例:ニューロン内部のビクセル集合)、Ω-={x: Φ(x)<0}をbackgroundとするような関数Φ:Ω->Rを見つけたい。
オブジェクトとbackgroundを分ける輪郭contourは、Γ={x:Φ(x)=0}で与えられる。
注意すべきは、複数のオブジェクトをもつ画像は、オブジェクトをforeground領域の接続要素として定義することで、一つのセグメンテーション関数Φによってセグメント化できるということ。

この埋め込みはユニークではない、Φは時々signed distance function (SDF)によって制約を受ける。
例:絶対値は境界に境界最近傍への距離を与えることによる ?
しかしながら、その場合になることはない。
例えば、セグメンテーションに対する確率モデルが与えられたとき、Φ(x)+t (tはスカラー値オフセット)は、ピクセルxがforegroundに属する確率の対数とみなせる。この場合、Φ(x)はあるピクセルが何の領域に割り当てられているかのみならず、割り当て対する信頼度としても表現される。

陽表現と比較して、陰表現はトポロジー変化(オブジェクトの結合merging と分割splitting)に対して容易に対処でき、高次元への拡張が容易に可能であるという利点がある。
画像のエッジ検出によらない領域ベースな方法に焦点をあてながらも、fore-とbackground領域のピクセル強度の分布の差を利用することにフォーカスする。
実用上は、時間変数tを導入し、Φtが何らかのエネルギー関数E(Φ,I)を最小化するために含まれる。(Cremaers et al., 2006)

共焦点や多光子顕微鏡から得られた画像の解析のために、神経構造は円形構造が連なるチューブ様としてモデル化することが可能であるという仮定に基づくが、本論では円と異なるという観測から、その仮定はおかない。

レベル集合法は、生物医学応用で3次元物体のセグメンテーションのためによく使用される手法。(Whitaker et al., 2001)
本論で提案されている手法は、ひとつの画像から次の画像へ情報が伝播するという点やエネルギー関数の抽出形式において、既存の手法と異なる。
アプローチとしては(Jurrus et al., 2006)と関連しており、彼らの研究によるとkalman filterに基づくpropagation schemeを使用し、オブジェクトの表現にレベル集合よりも明示的な境界を使用していた。

確率的フレームワーク
統計モデル
I_nを画像n\phi_nを対応するセグメンテーションとする。
すでにセグメント化が済んだ前の画像が存在し、\phi){n-1}は既知とする。
我々は、I_n\phi_{n-1}が与えられたとき、最も確率の高いセグメンテーション\phi_nを見つけたい。P(\phi_n|I_n,\phi_{n-1})を最大化。(Cremers et al., 2006)
Bayes’ Ruleより、
  P(\phi_n|I_n, \phi_{n-1}) \propto P(I_n|\phi_n, \phi_{n-1})P(\phi_n|\phi_{n-1})
を得る。
P(\phi_n|\phi_{n-1})は、可能なセグメンテーション\phi_nについての事前分布priorとみなせることができ、隣接する画像間のオブジェクトの連続性を確証する指標として使用できる。
これは、複数の画像にかけて構造をトレースすることを助ける。
加えて、滑らかな輪郭の支持やセグメント化されたオブジェクトの形状についての事前知識としても使用される。
実際は、手作業でラベルづけされた画像から学習されるが、訓練集合が十分でないことから、事前分布のための関数形式を選択する必要があった。

単純化のために、画像I_nは前画像\phi_{n-1}と独立しているものとして、現在のセグメントを\phi_nとする。
独立性よりP(I_n|\phi_n)=P(I_n|\phi_n,\phi_{n-1})
与えられた符号付き距離dに対し、P(I_n(x)|\phi_n(x)=d)が、外部(あるいは内部。\phi(x)の符号による)のすべてのピクセルの強度に対する確率分布を与え、closest boundaryまでの距離dを与える。
簡便のため、現在の画像\phi_n\phi、一つ前の画像\phi_{n-1}\phi_0と表記する。

事後確率 P(\phi|I) 最大化は、その負のlogの最小化と同値。
エネルギー関数は、
E(\phi|I) = -{\rm log}(P(I|\phi)) - {\rm log}(P(\phi|\phi_0)) = E_I + E_\pi
これを最小化する。
エネルギーの合計は画像の独立部分E_Iと事前独立部分E_\piの和で表される。
以下、P(I|\phi)P(\phi|\phi_0)について詳細に特徴づけ、データからnon-parametricに分布を学習するような可能な代案についてもみる。

単純なアルゴリズム
ピクセル強度I(x)の分布には、平均\alpha\phi(x)-\betaと分散\sigma^2の正規分布を仮定、

[BCI] Classification of covariance matrices using a Riemannian-based kernel for BCI applications

概要
空間分散共分散行列を特徴量として使用することは、BCIの運動想起によるEEGの識別で研究されている。新しいカーネルは対称正定値行列のリーマン幾何による接続を確立することにより導出される。過去のBCIコンペのデータに対し、異なるカーネルをSVMとの組み合わせでテストした。この新しいアプローチが、従来からの空間フィルタリングによるアプローチに代わるような性能であることを示す。

キーワード
Brain-Computer Interface, 分散共分散行列, カーネル, Support Vector Machine, リーマン幾何

内容
運動想起(MI; motor imagery)は、実際の身体の動きをイメージすることで、結果として、感覚運動野sensorimotor cortexの広い皮質領域で特定の脳波の周波数帯(μ、β周波数帯)においてERS; event related synchronization / ERD; event related desynchronizationが起きる。 (Pfurtscheller and Lopes da Silva, 1999)

運動想起に基づくEEG識別のスタンダートなアプローチとしては、バンドパスフィルタリング、空間フィルタリングをして線形分類を行う方法が用いられ、分類にはFisherのLDA; linear discriminat analysisが用いられる。

空間フィルタリングの手法としては、CSP; common spatial pattern (Ramoser, 2000)がよく使用される。
このアルゴリズムは、データ依存の次元削減法とみなすことができ、2つのコンディションの分散の差を強調する目的で使用される。
その際は、分散共分散行列はユークリッド空間で扱われ、SPD; symmetric positive definite対称正定値行列の空間の歪みは考慮されない。

EEGの分類のためのリーマン幾何を考慮するシンプルな方法
このアプローチは、過去にレーダー信号と画像処理においてうまくいった。
その上、新しいカーネルはSPD行列のリーマン幾何での接続をすることによって導出できる。
似たようなアプローチ (Harandi et al., 2012; Wang et al., 2010)
リーマン計量に依存する異なるカーネルの定義も導出

SVMと組み合わせてテスト
カーネルトリックが適用できる他の分類法 ロジスティック回帰 logistic regression も行った。
現在の手法よりも優れているのは、空間フィルタリングをする必要がなく、直接適用できること。(Barachant et al., 2010)

対称正定値行列に対する新しいカーネル
EEG信号は、試行 trials とよばれる短い時間セグメントで解析される。
入力信号 {\mathbf X} \in {\mathbb R}^{E\times T} (チャンネル数E x サンプル数Tの行列)
異なるEEG信号にバンドパスフィルタを適用すると仮定、μ(8-14Hz)とβ(14-30Hz) バンドを考慮して8-35Hzのバンドパスフィルタを適用。
2クラス分類  y_p \in \{-1, +1\}

EEGのランダム信号の空間分散共分散行列はExEのサンプル分散共分散行列(SCM)
C_p = \frac{1}{T-1} {\mathbf X_p}{\mathbf X^T_p}
によって計算。
SPD ExE行列空間をP(E)をする。
SCMは外れ値 outlier に敏感なため、robustな分散共分散行列推定か正則化が推定法を改良するために適用可能

空間フィルタリングを次元削減と異なる運動クラスのEEG試行同士の分散比を強調するために使用するのはMI-basedなBCIでは一般的 (Blankertz et al., 2008)

空間フィルタ後の分散の対数 log-variance は線形分類器(LDA)への入力として使用される。

CSP (Ramoser et al., 2000) は2クラスの運動想起タスクのEEGのクラス分類のための特徴量抽出のための手法としてうまくいっている
この手法は2つのコンディションで得られるクラス内分散共分散行列を同時対角化するもの

提案手法では、EEG-basedなBCIの信号分類のための入力として、空間分散共分散行列を直接利用

分散共分散行列を識別で特徴量として使用する場合、自然な選択はこの量をベクトルとして利用するためにベクトル化することであり、それによりvector-basedな分類アルゴリズムが使用可能
対称行列であることを利用して、半ベクトル化演算子を考える
Cの上三角行列を
 \frac{(E+1)E}{2}
のカラムベクトルへ変換
 vect({\mathbf C}) = \left[ C_{(1,1)}, {\sqrt 2}C_{(1,2)}, C_{(2,2)}, {\sqrt 2}C_{(1,3)}, {\sqrt 2}C_{(2,3)}, C_{(3,3)}, \dots , C_{(E,E)} \right]^T
一般性を失わないために、{\mathbf C}の非対角成分に対して係数{\sqrt 2}を掛ける。これにより\|{\mathbf C}\|_{F} = \|{\rm vect({\mathbf C})}\|_2
{\rm unvect}({\mathbf x})により反対の操作を定義
こういうアプローチは (Farquhar, 2009; Reuderink et al., 2011)でやってる
線形分類にかけるCSPライクな空間フィルタリングは、分類のための特徴量として分散共分散のベクトル化を考えることで高次元空間において単一のステップとなることを示唆
実際、分類スコア関数 h(.) は、空間フィルタリング後のEEG信号の時間分散 \sigma^2 に線形分類器 ({\mathbf u}, b) と適用することで得られる。
空間フィルタ {\mathbf W} を用いると、
 h({\mathbf \sigma^2}) = \langle {\mathbf u}, {\mathbf \sigma^2} \rangle + b = \sigma_k u_k {\mathbf w_k^T C w_k} + b = {\rm tr}({\rm diag}({\mathbf u}) {\mathbf W^T C W}) + b = \langle {\mathbf U}, {\mathbf C} \rangle_{F} + b

SVMによる分類への適用

結果とまとめ

Algorithms for manifold learning (L.Cayton, 2005)

Manifold learning (多様体学習)のAlgorithmを比較した論文です。

多様体(manifold)とは、局所的にはユークリッド空間とみなせる位相空間のことをいいます。

例えば、地球は丸いので、地球の表面すべてを一度に2次元の地図で表現しようとすると、繋ぎ目で重複が現れたり歪みが生じたりします。

しかし、局所的にみることによって2次元座標で地図の表現ができるようになります。

あるデータにも同じことが言えて、ものすごく高次元な空間にあるデータでも、実質的には低次元で表現できる場合があります。

if data lies in a 100-dimensional space, one cannot get an intuitive feel for what the data looks like.

4次元以上の高次元のデータの場合、視覚化できないので実際にデータがどうなっているか分かりにくかったり、コンピュータで計算をするのに、ものすごく時間がかかることがあります。

機械学習やデータマイニングでは、不要な情報を捨てて、必要な情報を抽出することはいろいろな意味で重要です。
高次元のデータをうまく表現できるように低次元のデータに変換することを次元圧縮(dimension reduction)といいます。

(書きかけ)

多様体の定義

PCA

線形部分空間への射影のみ

  • Isomap
  • Locally Linear Embedding (LLE)
  • Laplacian Eigenmaps
  • Semidefinite Embedding (SDE)

Algorithms for manifold learning (L.Cayton, 2005)