hirataraのお勉強記録

2009-03-15

■ わかりやすいパターン認識第5章(P.73〜78) 23:16

前処理部、特徴抽出部、識別部がある → 特徴抽出部の話題
- 特徴の評価・・・クラス間分離機能によって評価
within-class variance between-class variance ratio: クラス内分散・クラス間分散比
- クラス間の距離だけで評価している
- 分布の重なりが評価されてない
全体で平均化して評価するため、2クラス間の分離度が反映されない
probability of error
- あるxについての誤り確率は、 $P _e (\bf{x}) = \left\{ P(w_2 | \bf{x}) if \bf{x} \in w_1 \\ P(w_1 | \bf{x}) if \bf{x} \in w_2 \right.$
- すべてのxに対する誤り確率は $P _e = \int { P _e ( \bf{x} ) p( \bf{x} ) d\bf{x} }$
Bayes decision rule: $P _e$ が最小になるように識別する判定方法。事後確率 $P( w_i | \bf{x} )$ が最大のクラスを識別結果とする
Bayes risk: loss function による損失の最小値
conditional Bayes error: $P _e(\bf{x})$ の最小値
Bayes error: $P _e$ の最小値

コメントを書く

2009-03-09

■ わかりやすいパターン認識第4章(P.60〜71) 13:22

2クラスの線形識別関数を使い、多クラスの識別を行う
- $\forall i,j \le c$ について $w_i$ と $w_j$ を識別する $g_{ij}(\bf{x})$ が与えられる*1時は、 $\forall j \ne i, g_{ij}(\bf{x}) > 0 \Leftrightarrow \bf{x} \in w_i$ で識別する*2
- majority voting: $N_i(\bf{x})$ を $g_{ij}(\bf{x}) > 0$ を満たすjの個数と定めて、 $\forall j \ne i, N_i(\bf{x}) > N_j(\bf{x}) \Leftrightarrow \bf{x} \in w_i$ とする
- $\forall i \le c$ について $w_i$ か否かを識別する $g_{i}(\bf{x})$ が与えられる*3ときは、 $g_i(\bf{x}) > 0 \/ and \/ \forall j \ne i, g_j(\bf{x}) < 0 \Leftrightarrow \bf{x} \in w_i$ で識別する
- $g_{ij}(\bf{x})$ の符号ではなく $g_{i}(\bf{x})$ と $g_{j}(\bf{x})$ の大小で任意の２クラスを識別出来る時は、 $\forall j \ne i, \/ g_i(\bf{x}) > g_j(\bf{x}) \Leftrightarrow \bf{x} \in w_i$ で識別する
線形分離できない場合は、Widrow-Hoff learning rule などで線形識別関数を求めれば、前項目の方法を適用できる
quadric discriminant function:
- 特徴ベクトルが多次元正規分布、かつ、 $\Sigma_1 = \Sigma_2$ であれば最適な識別関数は線形識別関数となる
- 超平面は $\bf{m}_1-\bf{m}_2$ に垂直。さらに $P(w_1) = P(w_2)$ であれば $\bf{m}_1$ と $\bf{m}_2$ の中点を通る
線形関数のrobustness: ２次以上の識別関数は、パターン数に対して漸近性が低い。
generalized discriminant function: Φ functionのこと。で表される。
- $\bf{y} = ( \phi_1(\bf{x}), ... , \phi_k(\bf{x}) )$ とすると線形関数の学習法が使える
特徴空間の次元数をd、学習パターン数をnとすると、 $n \gg d$ の必要がある
capacity: 。dが大きいとき、nがcapacityより小さい時はそれらが線形分離する確率はほぼ1
- つまり、nがcapacityより低い状態では、"偶然"の超平面が見つかりやすい → 信頼性が低い
- curse of dimensionality: 特徴空間の次元が増えると必要な学習パターン数が指数関数的に増えること
general position: それぞれのパターンが同一超平面上にない状態
特徴空間の次元数=識別部のパラメータ数。
over-fitting: 少数のパターンを複雑な識別関数で近似しすぎると、未知の入力に正確な出力ができなくなる。パラメータ数に対してパターン数が不足していることに起因する。
over-training: ニューラルネットワークでのover-fitting
Akaike Information Criterion: 情報量基準。パラメータ数を勘案しつつ個別パターンへの適合を行う手法
ハイパーパラメータ: 識別機のパラメータのパラメータ。ニューラルネットワークの中間ユニット数やk-NN法のkの値など
ハイパーパラメータの善し悪しを決めるには、学習パターンからを推定し、を最小にするが見つかればいい
- hold-out method: H法。 $chi$ を学習パターンとテストパターンにわけ、 $e_{\lambda}$ を推定。
- cross-validation method: CV法。をm個のグループにわけ、以外で学習、でテスト、をm回行ってを推定
  - n→∞の時、 $e_{\lambda}$ は真値に漸近する
- Leave-one-out metho: L法。n個のグループに分けるCV法。ジャックナイフ法とも呼ばれる。
- bootstrap method: BS法。学習にもテストにも $\chi$ を用いて、後から誤差修正をする。 $\chi$ から同数のサンプルを復元抽出*4した $\chi^*$ による学習でも $\chi$ の誤認識率を調べ*5、誤差を予想する。

*1：線形識別関数は $\frac{c(c-1)}{2}$ 個

*2：ただし、 $g_{ij}(\bf{x}) = - g_{ji}(\bf{x})$

*3：線形識別関数はc個

*4：重複を許し、要素を取り出す

*5：50回程度

コメントを書く

2009-03-06

■ わかりやすいパターン認識第4章(P.58〜59) 13:29

この辺の議論は線形判別法を理解してないときつそう。6章読んだら戻って来ることにする。

$J = \frac{(\tilde{m}_1 - \tilde{m}_2)^2}{k_1 \tilde{\sigma}_1^2 + k_2 \tilde{\sigma}_2^2}$ と定義すると、線形判別法をJを最大化する方法として見ることができる(らしい)
この時(つまり線形判別法も)、は不定となるので、別の方法で定めなければならない
- (1次元に)変換後のクラス平均の中点
- 変換後の書くクラスごとの分散で内分
- 事前確率も考慮して内文

コメントを書く

2009-03-05

■ わかりやすいパターン認識第4章(P.56〜58) 20:44

liner discriminant function の方がよく研究されている*1
2クラスの識別を考える
線形判別法*2によるd次元空間から一次元空間からへの変換を(d,1)行列Aで表す
- Aは超平面の法線ベクトル
- 1次元空間への射影値は $\bf{A}^t\bf{x} + a_0$ で評価関数 $g(\bf{x}) = w^t\bf{x}+w_0$ と同じ形
各クラス $w_i (i = 1, 2)$ の1次元空間上の平均を $\tilde{m}_i$ 、分散を $\tilde{\sigma}_i^2$ とする
g(x)の評価関数を $J(\tilde{m}_1, \tilde{m}_2, \tilde{\sigma}_1^2, \tilde{\sigma}_2^2)$ とする
g(x)を使って平均を求めると、 $\tilde{m}_i = w^t \bf{m}_i + w_0$ ( $\bf{m}_i$ は平均ベクトル)
g(x)を使って分散を求めると、 $\tilde{\sigma}_i^2 = w^t \Sigma_i w$ ( $\Sigma_i$ は共分散行列)
と置くと、
- $\bf{w} \propt \frac{ \bf{m}_1 - \bf{m}_2 }{s \Sigma_1 + ( 1 - s )\Sigma_2}$ となる*3

*1：簡単なので

*2：6章で出て来るようだ

*3：~~これ、なんでだろう？？ 4-41から4-42が導出できない・・・~~ああ、ベクターのとこだけが重要だからスカラ倍はどうでもいいってことか。理解。

コメントを書く

2009-03-02

■ わかりやすいパターン認識第4章(P.52〜56) 23:26

parametric learning: 確率密度関数のパラメータ推定によって識別部を構成する
nonparametric learning: 学習パターンから直接discriminant functionを得る
parameter vector: 推定すべきパラメータの組。 $\bf{\theta}$ で表す
likelihood(尤度): parameter vectorの尤もらしさ。入力されたパターン集合が得られる確率
likelifood function: likelihoodのこと
maximum likelihood method: likelihood が最大になるparameter vector を推定する
unimodal: 単峰性。極大点が唯一
multimodal: 複数の極大点
mixture density: 混合分布。複数の確率密度関数を線形結合したもの
supervised learning: パターンと所属クラスを組で与える学習
unsupervised learning: 与えられるパターンのクラスが不明
- 各パターンについて、 $p(\bf{x}_k;\bf{\theta}) = \sum _{i=1} ^c P(\omega_i)p(\bf{x}_k|\omega_i;\bf{\theta}_i)$ なので、混合分布のパラメータ推定ができれば $P(\omega_i)$ と $p(\bf{x}_k|\omega_i;\bf{\theta}_i)$ が求まる
hill-climbing method: 混合分布のパラメータ推定法。steepest descent method と等価らしい
現実のパターン認識ではparametric な学習でうまく行く場合は少ない

コメントを書く

2009-02-27

■ わかりやすいパターン認識第4章(P.49〜51) 21:04

probability density function: $p(\bf{x}|\omega_i) (i = 1, ..., c)$
a priori probability: $P(\omega_i)$
a posteriori probability: $P(\omega_i|\bf{x})$
Bayes theorem: $P(\omega_i|\bf{x}) = \frac{p(\bf{x}|\omega_i)}{p(\bf{x})} P(\omega_i)$
ベイズ則の不変項を取り除いて対数をとった $g_i(\bf{x}) = \log p(\bf{x}|\omega_i) + \log P(\omega_i)$ を識別関数と出来る
mean vector: $\bf{m}_i = \frac{1}{n_i} \sum _{\bf{x} \in \chi_i} \bf{x}$
covariance matrix: $\Sigma_i = \frac{1}{n_i} \sum _{\bf{x} \in \chi_i} (\bf{x} - \bf{m}_i)(\bf{x} - \bf{m}_i)^t$
normal distribution: $p(\bf{x}|\omega_i) = \frac{1}{ \sqrt{ (2\pi)^d |\Sigma_i|} } e^{-\frac{1}{2}(\bf{x} - \bf{m}_i)^t \Sigma_{i}^{-1} (\bf{x} - \bf{m}_i) } ( i=1, ..., c)$
Mahalanobis distance: $D_M(\bf{x}, \bf{m}_i) = \sqrt{ (\bf{x} - \bf{m}_i)^t \Sigma_i^{-1} (\bf{x} - \bf{m}_i) }$ *1
$p(\bf{x}|\omega_i)$ が正規分布のとき、識別関数 $g_i(\bf{x})$ は $\bf{x}$ の二次関数
covariance matrixが一定で $\Sigma_0 = \Sigma_i ( i = 1,...,c)$ であれば、 $\bf{x}$ の二乗項はiに依存しなくなるので、 $g_i(\bf{x})$ を線形識別関数にできる
さらに特徴間の分散が等しく( $\Sigma_0$ が単位行列)、事前確率が全クラスで等しい( $P(\omega_i) = \frac{1}{c} (i = 1,...,c)$ ) であれば評価関数はminimum distance methodと同等になる

*1：正規分布の定義で登場

コメントを書く

2009-02-25

■ わかりやすいパターン認識第3章(P.42〜P.48) 23:14

neural network: input layer, output layer, hidden layer で多層化したネットワーク
neural network を線形で繋いでも結果は線形で意味がない。非線形関数*1を用いる

backpropagation method

誤差逆伝搬法。出力層から入力層へ帰納的に重み修正する方法

1層からl層まであるとする。
1層のユニット数は次元d+1、l層のユニット数はクラス数c、中間層のユニット数は任意
n層のi番目のユニットへの入力を $h_{n_i}$ 、n層のi番目のユニットの非線形関数を $f_{n_i}$ とする
n層のi番目からの出力 $g_{n_i}$ は、 $g_{n_i} = f_{n_i}(h_{n_i})$ で表される
n層の全てのユニットを線形結合した値がn+1層の任意のユニットの値となる
上記のn層のi番目のユニットからn+1層のj番目のユニットへの重みを、とする。
- つまり、 $h_{(n+1)_j} = \sum _i w_{n_i(n+1)_j} g_{n_i}$

$h_{1_i} (0 \le i \le d + 1 )$ について $f_{1_i}$ を $w_{1_i 2_j}$ で線形結合して $h_{2_j}$ を求めることができる
帰納的に出力層の出力を得る。
- よって、 $g_{l_i}$ は $w_{n_i(n+1)_j} ( 1 \le n \le l - 1 )$ の関数(iとjは各層のユニットの数だけ存在)
- 教師信号との二乗誤差 $J$ も $w_{n_i(n+1)_j}$ の関数
を最小にするため、に対してsteepest descent method を適用する*2
- $w_{n_i(n+1)_j}$ の誤差修正には偏微分 $\frac{\partial J}{\partial w_{n_i(n+1)_j}$ が必要
- と置くと、この値は実は出力層側から再帰的に求まる
  - $\epsilon_{n_i} = \frac{\partial J}{\partial g_{n_i}} f_{n_i}'(h_{n_i}) = (\sum _j \frac{\partial J}{\partial h_{(n+1)j} } \frac{\partial h_{(n+1)j} }{\partial g_{n_i}}) f_{n_i}'(h_{n_i}) = (\sum _k \epsilon_{(n+1)_j} w_{n_i}_{(n+1)_j}) f_{n_i}'(h_{n_i})$
  - Jは2乗誤差なので、出力層lでは $\epsilon_{l_i} = \frac{\partial l}{\partial g_{l_i}} f'(h_{l_i}) = (g_{l_i} - b_{l_i}) f'(h_{l_i})$
  - $g_{n_i}$ と $h_{n_i}$ は出力値を計算する時に全て算出済
- 合成関数の偏微分を注意深く適用すれば*3、 $\frac{\partial J}{\partial w_{n_i(n+1)_j}} = \epsilon_{(n+1)_j} \frac{\partial h_{(n+1)_j}}{\partial w_{n_i(n+1)_j}} = \epsilon_{(n+1)_j} g_{n_i}$
- 以上により、必要な偏微分が全て得られる
- としてを用いると、となる。つまり出力値より微分を得られる
  - $f_{n_i}'(h_{n_i}) = g_{n_i}(1 - g_{n_i})$ となり、 $f_{n_i}$ の微分も $h_{n_i}$ も不要になる
シグモイド関数は0,1にはならないので、教師信号として0.1や0.9を利用するとよい

*1：しきい値関数、シグモイド関数

*2：generalized delta rule

*3： $J(h_{(n+1)_0}, h_{(n+1)_1}, ...)$ だが、k≠jであれば $h_{(n+1)_k}$ は $w_{n_i}_{(n+1)_j}$ を変数に含まないことに注意(hはwを重みとした直前の層の線形和)

コメントを書く

2009-02-24

■ わかりやすいパターン認識第3章(P.38〜P.41) 09:56

Widrow-Hoffの学習規則を、 $g_i(\bf{x}_p)$ に閾値関数を施したものと教師信号に $\bf{x}_p$ がクラスiなら1になるようにして適用すると、パーセプトロンの学習規則となる
perceptron learning rule → 識別関数も教師信号も２値、収束しないかも、収束すれば誤識別0
Widrow-Foff learning rule → 識別関数は連続、必ず収束、線形分離可能でも誤識別0とは限らない
重み空間の $\bf{w}^t\bf{x} = 0$ と重みベクトル $\bf{w}$ との距離を評価関数としてsteepest descent methodを適用すると、perceptron learning rule が導ける

コメントを書く

2009-02-23

■ わかりやすいパターン認識第3章(p.35-37) 09:55

gradient vector: ${\nabla J} = \frac{\partial J}{\partial {\bf w}}$
パターン行列: $\bf{X} =^{def} $\bf{x}_1, ..., \bf{x}_n$^t$
$\bf{X}^t\bf{X}$ が正則であれば、 $\bf{w}_i = $\bf{X}^t\bf{X})^{-1}\bf{X}^tb_i \(i = 1, .., c$$ ( $\bf{x}_p$ を説明変数、 $b_{ip}$ を目的変数とする重回帰分析(multiple regression analysis)の最小２乗法*1と同じ)
steepest descent method: こう配ベクトルと逆方向に値を動かすことで、最小値を探す方法。*2
Widrow-Foff learning rule: パターンが示されるごとに重みベクトルを修正する方法。最小２乗法の解をsteepest descent methodで見つける。 $\bf{w}_i' = \bf{w}i - \rho(\bf{w}_i^t\bf{x}_p - b_{ip})\bf{x}_p$

*1：平均２乗誤差の最小値を求める = パラメータに関する微分が 0になるように計算する

*2：集合知プログラミングのニューラルネットワークの実装で微分してたのもこれか

コメントを書く

2009-02-22

■ わかりやすいパターン認識第3章 09:54

Ho-Kashyapのアルゴリズム: 線形分離部可能であることを検出できる(らしい)
教師信号: discriminant functionの望ましい出力値
教師ベクトル: c個のクラスに対し、パターン $x_p$ に対する教師ベクトルは $$b_1_p, b_2_p, ... , b_c_p$^t$ ( $b_i_p$ はパターン $x_p$ のクラスiについての教師信号)
教師ベクトルについては、 $x_p \in w_i \Rightarrow b_i_p \lt b_j_p $ j \ne i$$
教師信号と識別関数の誤差 $\epsilon_{ip} = \bf{w}_i^t\bf{x}_p - b_{ip}$ を評価関数*1に使えば、 $J$\bf{w}_1, ..., \bf{w}_c$ = \frac{1}{2}\sum_{p=1}^n\sum_{i=1}^c$\bf{w}_i^t\bf{x}_p - b_{ip}$^2$