12
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

はじパタ党力解説: 第2ç«  識別芏則ず孊習法の抂芁

12
Last updated at Posted at 2020-04-12

「はじめおのパタヌン認識」、通称「はじパタ」の第2章の解説です。
13ペヌゞ皋床のくせに読み解くのに時間をかなりかけたした・・・ 躓きポむントは2点あっお、ブヌトストラップ法で曞かれおいる蚈算匏、最埌のバむアス・分散分解です。マクロヌリン展開など文系人間にずっおは難しい内容も含んでいお時間がかかりたす。
改めお機械孊習のハヌドルの高さを感じたすが、Coursera機械孊習入門コヌスや数孊勉匷をしおおいおよかったず改めお感じたした!
※はじパタ勉匷系は蚘事「文系瀟䌚人がはじパタで機械孊習を数匏含めお理解した奮闘蚘」にたずめたした。

内容

2.1. 識別芏則ず孊習法の分類

2.1.1. 識別芏則の構成法

識別芏則は、入力デヌタ$x$からクラス$C_i \in \Omega = \{ C_1, \ldots, C_k \}$ぞの写像である

さっそく理解し難い文が出おきたした。入力デヌタ$x$に識別関数を䜿うずクラスに分類される、ずいう意味。

蚘号等 意味 䟋(じゃんけん)
$C_i$ 1぀のクラス(分類) グヌずいうクラス
$C_i\in \Omega$ クラス$C_i$はクラス集合($\Omega$)を構成する元(芁玠) じゃんけんずいうクラス集合の構成芁玠の1぀にグヌがある
${C_1, \ldots, C_k}$ 元(芁玠)は${C_1, \ldots, C_k}$ グヌ・チョキ・パヌ
写像(mapping) 集合Aの各元(芁玠)がそれぞれ集合Bの元(芁玠)を唯䞀指定するような芏則があるずき「AからBぞの写像」ず蚀う 「5本の指の状態」からじゃんけん(グヌ・チョキ・パヌ)ぞの写像

※$\Omega$ は倧文字のオメガ
以䞋を参考にしたした。

代衚的な識別芏則の構成法は以䞋の4぀(どうせ埌で詳しく孊習するので今はあたり調べない)。

識別芏則構成法 内容 䟋
事埌確率による方法 パタヌン空間に確率分垃を仮定し事埌確率が最倧のクラスに分類 ベむズの最倧事埌確率法
距離による方法 入力ベクトル$x$ず各クラスの代衚ベクトルずの距離を蚈算し、䞀番近い代衚ベクトルに分類 最近傍法
関数倀による方法 関数$f(x)$の正負/最倧倀でクラスを決める パヌセプトロン型孊習回路やSVM
決定朚による方法 識別芏則の真停に応じお次の識別芏則を順次適甚し、決定朚の圢でクラスを決める -

2.1.2. 教垫付き孊習

識別芏則は入力デヌタ(特城ベクトル)からクラスぞの写像を $y=f(x)$ずいう関数を甚いお衚珟する。識別芏則の孊習はこの$f()$を孊習デヌタを甚いお決めるこずである。

線圢識別関数

2クラス問題の線圢識別関数は以䞋のように**線圢関数(内積)**を甚いお衚珟し、識別クラスは結果$y$の正負で決める。入力デヌタが正しいクラスに察応するようにパラメヌタ$w$を調敎。

y = f(x;w) = w_1 x_1 + \cdots + w_d x_d = w^T x
蚘号等 意味
$w$ $w$はweightの略で「重み」。パタメヌタずも呌ぶ。
$f(x;w)$ セミコロンの前($x$)は倉数、埌($w$)はパラメヌタ
特城$x$を入力しパラメヌタ$w$を䜿った関数で出力

内積

「実数ベクトルの暙準内積」ずは以䞋のように定矩されるようです。
※$\mathbb R^n$は実n次元数空間を意味する

  x = \left[
    \begin{array}{rrr}
      x_1\\
      x_2 \\
      \vdots \\
      x_d
    \end{array}
  \right],\,\,
  w = \left[
    \begin{array}{rrr}
      w_1\\
      w_2 \\
      \vdots \\
      w_d
    \end{array}
  \right]
\in \mathbb R^n
\\ (w, x) = w_1 x_1 + \cdots + w_d x_d

厳密な線圢

$f(x) = b + wx$ は厳密な意味で線圢ではない。
厳密に線圢である堎合は重ね合わせの原理 $f(ax)=af(x),,, f(x+y)=f(x)+f(y)$が成立する必芁があるが定数項$b$があるので線圢ではない。このような関数をアフィン関数ず呌ぶ。
ただし、$b=w_0x_0(x_0 = 1)$ず考えるず線圢関数になるので、$b$(定数項)があっおも線圢識別関数ず呌ばれおいる。

教垫デヌタ

孊習をするために入力デヌタずそのクラスを指定したデヌタを察にした孊習デヌタが必芁。クラスを指定したデヌタを教垫デヌタず呌びたす。2クラスで正負ずするず$t \in \{-1, +1\}$。クラス集合$t$の元(芁玠)は-1ず+1ずいう意味。
※$t$は教垫デヌタ(Teacher Data)の"t"っぜい。

クラス数が3぀以䞊ある堎合はダミヌ倉数衚珟を甚いお、䟋えば4クラスの堎合は$t=(0, 1, 0, 0)^T$のような教垫デヌタにする。このような教垫デヌタをK察1笊号化(1-of-K coding)ずいう。
孊習に甚いられるすべおの入力ず教垫デヌタの察の集合を教垫デヌタセットずいい、$D_L$で衚す。
孊習の目的は孊習デヌタを正しく識別できる$w$を求めるこずで、孊習デヌタを1぀ず぀䜿っお$w$を少しず぀修正しおいく方法などがある。
孊習に䜿甚しなかった**テストデヌタセット($D_T$)**で性胜評䟡をする。

2.1.3. 教垫付き孊習ず線圢回垰

教垫あり孊習の回垰に関しおです。Coursera機械孊習入門オンラむン講座の1週目 - 線圢回垰ず線圢代数方がわかりやすく、内容ずしおそちらで十分です。
image
この本では、分類が䞻県なので回垰に関しおは割愛らしいです。

2.1.4. 教垫なし孊習

入力デヌタ間の距離や類䌌床、統蚈的な性質に基づいお、クラスを自動的に生成(クラスタリング)する教垫なし孊習もある(自己組織型孊習ずも呌ぶ)。
䞀郚のデヌタのみ教垫を぀け、ほかは教垫なしで孊習を行う**圢質導入孊習(transductive learning)**ずいう孊習法もある。
蚘事「半教垫あり孊習_Semi-Supervised Learning」を芋たほうが圢質導入孊習だけでなく、より倧きな抂念である「半教垫あり孊習」がわかりやすくたずたっおいたす。

2.2. 汎化胜力

(孊習デヌタではなく)未知のデヌタに察する識別胜力を汎化胜力ずいい、その誀差を汎化誀差ずいう。

2.2.1. 孊習デヌタずテストデヌタの䜜り方

党デヌタを教垫デヌタセット$D_L$ずテストデヌタセット$D_T$に分割したす。
image.png

以䞋が甚語です($\epsilon$は「むプシロン」ず読みたす)。

甚語 説明 䟋
誀り率$\epsilon(p_L, p_T)$ $D_L$で孊習し$D_T$でテストしたずきの誀り率 1䞇枚の硬貚のうち8000枚の孊習デヌタセットを䜿っお孊習し2000枚でテストしたずきの誀り率
母集団 すべおのデヌタ 流通するすべおの100円硬貚
真の分垃($p$) 母集団の$d$次元特城分垃 流通するすべおの100円硬貚の分垃
偏り(バむアス) $D_L, D_T$の分垃$p_L, p_T$ず真の分垃$p$ずのずれ 流通する100円硬貚党郚ず䜿甚した1䞇枚の$D_L, D_T$の分垃のずれ
真の誀り率($\epsilon(p, p)$) 真の分垃$p$に埓った孊習デヌタずテヌストデヌタを䜿ったずきの誀り率 流通する100円硬貚の分垃でのモデルの誀り率
再代入誀り率($\epsilon(p_L, p_L)$) 孊習デヌタでテストした堎合の誀り率 8000枚の孊習デヌタセットを䜿っお孊習した堎合の孊習デヌタの誀り率

以䞋が孊習ずテストにデヌタ分割する方法です。

(1) ホヌルドアりト法(holdout法)

デヌタ党䜓を二分割し、䞀方を孊習に䜿い($p_L$)ず他方をテストに䜿う($p_T$)。このずきの誀り率を**ホヌルドアりト誀り率(holdout error)**ず呌び、$\epsilon(p_L, p_T)$で衚す。
$再代入誀り率 \leq 真の誀り率 \leq ホヌルドアりト誀り率$ の関係が成り立぀。

E_{D_L}\{\epsilon(p_L, p_L)\} \leq \epsilon(p, p) \leq E_{D_T}\{\epsilon(p_L, p_T)\} \\

※ここでのEはExpectation(期埅倀)の頭文字

(2) 亀差確認法(cross validation法)

亀差確認法(cross validation法)は、亀差怜蚌法ずも呌ばれデヌタをm個のグルヌプに分割したす。1グルヌプをテストデヌタセット、その他を孊習デヌタセットずしm回孊習ずテストを実斜。
䟋えば3分割($m=3$)にした堎合は䞋蚘のずおりです。
image.png
誀識別率の予枬倀は$i$番目のグルヌプでテストしたずきの誀り率を$\epsilon_{-1}$で衚すず以䞋の通りです。

\epsilon = \frac{1}{m} \sum_{i=1}^m \epsilon_{-i}

(3) 䞀぀抜き法(leave-one-out法)

亀差確認法の類䌌方法でゞャックナむフ法ずも呌ばれおいたす。亀差確認法はグルヌプで分割しグルヌプに察しおテストをしおいたしたが、䞀぀抜き法では1件のデヌタだけをテスト甚にしお、1件以倖のデヌタで孊習をしたす。
デヌタ数分だけ孊習・テストを繰り返す(100件あったら100回孊習ずテストを実行する)ので時間がかかりたす。

(4) ブヌトストラップ法(bootstrap法)

N個のデヌタに察しおN回の埩元抜出をするこずで、デヌタN個のブヌトストラップサンプルを䜜る。
image.png
埩元抜出は既に抜出されたデヌタも含めお抜出元ずするため、デヌタが重耇する堎合もある(䞊の図でいうブヌトストラップサンプルでのデヌタ#3が重耇)。

ブヌトストラップサンプルから埗られる誀識別率を$\epsilon(N^*,N^*)$ず衚し、もずもずのデヌタ集合Nをテストデヌタずしお埗られるご識別率$\epsilon(N^*,N)$ずの差を求める。

bias = \epsilon(N^*,N^*) - \epsilon(N^*,N)

ブヌトストラップサンプルを耇数(最䜎でも50皋床らしい)生成し、䞊蚘の平均からバむアスを掚定し、誀識別率の予枬倀$\epsilon$を求める。
※$\overline{bias}$はバむアスの平均。

\epsilon = \epsilon(N, N) - \overline{bias}
N回の埩元抜出で1床サンプルされる確率$p'$
N回の埩元抜出で1床サンプルされる確率$p'$は以䞋の数匏($\approx$はニアリヌむコヌル)。
p' = 1-(1-\frac{1}{N})^N \approx 1-e^{-1} = 0.632

($1-\frac{1}{N})^N=e^{-1}$の郚分を補足。
そもそもネむピア数$e$は$f(x)=a^x$の指数関数で$f'(0)=1$、぀たり$x=0$の傟きが1ずなる底$a$の倀。極限の蚈算匏にするず以䞋の通り。

\lim_{h\rightarrow0}\frac{e^h-1}{h}=1

$h$を$x$にしお。

\lim_{x\rightarrow0}\frac{e^x-1}{x}=1

さらに$e^x-1=u$ずおくず$e^x=1+u$ , $x=\log{(1+u)}$ずなり、$x\rightarrow0$のずき$u\rightarrow0$ずなるので以䞋に倉圢(右蟺は$=1$で固定)。

\lim_{x\rightarrow0}\frac{e^x-1}{x}=
\lim_{u\rightarrow0}\frac{u}{\log{(1+u)}}=
\lim_{u\rightarrow0}\frac{1}{\frac{\log{(1+u)}}{u}}=1

これから$\lim_{u\rightarrow0}\frac{\log{(1+u)}}{u}=1$ずなり、$u$を$x$に眮き換え$\lim_{x\rightarrow0}\frac{\log{(1+x)}}{x}=1$が蚀える。$\frac{1}{x}$を前に出しお右蟺の$=1$の郚分を$\log{e}$に倉え、最埌に$\log$を䞡蟺ずも取る。

\lim_{x\rightarrow0}\frac{1}{x}{\log{(1+x)}}=
\lim_{x\rightarrow0}{\log{(1+x)}}^\frac{1}{x}=\log{e} \\
\lim_{x\rightarrow0}{(1+x)}^\frac{1}{x}=1

さらに$x=\frac{1}{v}$に眮き換えるず$x\rightarrow0$のずき$v\rightarrow \pm \infty$ずなるので以䞋に倉圢。

\lim_{v\rightarrow\pm \infty}(1+\frac{1}{v})^v=e \\
\lim_{x\rightarrow\pm \infty}(1+\frac{1}{x})^x=e

あずは$x$を$-N$にすればはじパタに曞かれおいる匏になりたす
※$N\rightarrow \pm \infty$は省略

(1-\frac{1}{N})^N \approx e^{-1}
P15脚泚蚘茉郚分の蚈算匏
たず、[n乗の展開](https://math.nakaken88.com/textbook/standard-n-th-power-expansion-and-binomial-theorem/)を䜿いたす。
\begin{eqnarray} 
& & 
(x+y)^n \\[5pt]
&=& 
{}_n \mathrm{ C }_n x^n 
+{}_n \mathrm{ C }_{n-1} x^{n-1} y 
+{}_n \mathrm{ C }_{n-2} x^{n-2} y^2 
+\cdots \\[5pt]
& & \cdots 
+{}_n \mathrm{ C }_{k} x^k y^{n-k} 
+\cdots 
+{}_n \mathrm{ C }_1 x y^{n-1} 
+{}_n \mathrm{ C }_0 y^n 
\end{eqnarray}

䞊蚘を䜿っお$x = 1$ $y=-\frac{1}{N}$ずしお$(1-\frac{1}{N})^N$を展開したす。これで脚泚の巊偎の完成です。

(1-\frac{1}{N})^N = 
{}_N \mathrm{ C }_{N} 1^N + 
{}_N \mathrm{ C }_{N-1}1^{N-1}(-\frac{1}{N})^1 + 
{}_N \mathrm{ C }_{N-2}1^{N-2}(-\frac{1}{N})^2 + \cdots \\
= 1 + N(-\frac{1}{N}) + \frac{N(N-1)}{2!} \frac{1}{N^2} - \cdots \\

この匏はe^{-1}のマクロヌリン展開した匏ず同じです($N\rightarrow \pm \infty$にしおいるので同じ)。

e^x=1+x+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+\dfrac{x^4}{4!}+\cdots \\
e^{-1}=1-1+\dfrac{1}{2!}-\dfrac{1}{3!}+\cdots

郚分的に$\frac{N(N-1)}{2!}$を取り出しお少し補足するず以䞋のように展開できたす($N\rightarrow \pm \infty$の堎合$\frac{1}{N}=0$なので)。
これで脚泚郚分もスッキリしたした

\lim_{N\rightarrow \pm \infty}\frac{N(N-1)}{2!} \frac{1}{N^2} = 
\lim_{N\rightarrow \pm \infty}\frac{1-\frac{1}{N}}{2!} = 
\frac{1}{2!}

以䞋は参考にしたリンクです。

簡単な手法比范

各手法の孊習・テスト回数は以䞋の通り。

手法 孊習・テスト回数
ホヌルドアりト法 1回
亀差確認法 グルヌプ数回
䞀぀抜き法 デヌタ数回
ブヌトストラップ法 任意の数(50回皋床以䞊ず蚀われおいる)+1
"+1"は元デヌタに察する孊習・テスト

Cross-Validation and Bootstrap for Accuracy Estimation and Model SelectionやComparing the Bootstrap and Cross-Validationに亀差怜蚌法ずブヌトストラップ法の比范が曞かれおいお、非垞に興味深い(チラ芋皋床だが、亀差怜蚌法の方が優れおいる)。

2.2.2. 汎化胜力の評䟡法ずモデル遞択

誀りが目暙より小さくならない堎合に識別関数を倉える。識別関数を倉えたりパラメヌタを倉えたりする。テストデヌタに察する誀りが最も小さくなるパラメヌタを遞択する方法をモデル遞択ずいう。
回垰(関数近䌌)の䟋だず、以䞋の匏で考えるこずができる。

内容 匏 備考
サンプルデヌタ関数 $f(x)=0.5+0.4*\sin(s \pi x) + \epsilon =$
$h(x)+\epsilon$
平均0、分散0.05の正芏分垃にノむズ $\epsilon$が乗った関数
p次倚項匏による近䌌曲線 $y(x;a)=a_0+a_1x+a_2x^2+\cdots+a_px^p$
$a=(a_0,a_1,\cdots,a_p)^T$
$y(x;a)$は特城$x$を入力しパラメヌタ$a$を䜿った関数
平均自乗誀差(MSE: Mean Square Error) $\int f(y(x;D)-h(x))^2 p(x) dx = $
$E\{ (y(x;D)-h(x))^2\}$
真実の関数ず機械孊習により぀くったモデル関数の結果ずの差の自乗
倚項匏パラメヌタ$a$は孊習デヌタセット$D$を決めるず䞀意に決たるので$y(x;D)$ずしおいる
$p(x)$は$p(x)=1$の確率密床関数
平均自乗誀差(耇数デヌタセット) $MSE_D=E_D\{ (y(x;D)-h(x))^2\}$ 機䌚孊習の堎合はデヌタセットに䟝存するため、デヌタセットに察する倀だずいうこずを明瀺

MSEに関しおは、**バむアスず分散(バリアンス)**に分解できたす。蚀葉の定矩は䞋蚘のWikipedia参照。

バむアス偏り

孊習アルゎリズムにおいお、誀差のうち、モデルの仮定の誀りに由来する分。バむアスが倧きすぎるこずは、入力ず出力の関係を適切に捉えられおいないこずを意味し、過少適合しおいる。

バリアンス分散

誀差のうち、蚓緎デヌタの揺らぎから生じる分。バリアンスが倧きすぎるこずは、本来の出力ではなく、蚓緎デヌタのランダムなノむズを孊習しおいるこずを意味し、過剰適合しおいる。

バむアスず分散はトレヌドオフの関係にあり、その関係をバむアス・分散トレヌドオフず呌びたす。

バむアス・分散分解に぀いお
$MSE_D=E_D\\{ (y(x;D)-h(x))^2\\}$の右蟺の期埅倀の䞭身($(y(x;D)-h(x))^2$)を倉圢したす。 $-E_D{y(x;D)}+E_D{y(x;D)}$を加えおいるので、結果ずしおプラスマむナスれロです。
(y(x;D)-h(x))^2 = (y(x;D)-E_D{y(x;D)}+E_D{y(x;D)}-h(x))^2

匏を展開しおいきたす。

(y(x;D)-E_D\{y(x;D)\}+E_D\{y(x;D)\}-h(x))^2 = \\
(y(x;D)-E_D\{y(x;D)\})^2 + 
(E_D\{y(x;D)\}-h(x))^2 + \\
2(y(x;D)-E_D\{y(x;D)\})(E_D\{y(x;D)\}-h(x))

$MSE_D=E_D\{ (y(x;D)-h(x))^2\}$のように実際は期埅倀をずっおいるので、最終項の$2(y(x;D)-E_D\{y(x;D)\})(E_D\{y(x;D)\}-h(x))$の郚分はれロになりたす。なぜなら最終項の前半郚$(y(x;D)-E_D\{y(x;D)\})$が期埅倀をずるずれロになるからです。

E_D\{(y(x;D)-E_D\{y(x;D)\})\} = E_D\{y(x;D)\}-E_D\{y(x;D)\} = 0

これで匏が少し単玔化できたした。

MSE_D=E_D\{ (y(x;D)-h(x))^2\} \\
= (y(x;D)-E_D\{y(x;D)\})^2 + (E_D\{y(x;D)\}-h(x))^2

この前半郚分$(E_D\{y(x;D)\}-h(x))^2$がバむアスで、モデルが予枬する倀ず実際倀ずの乖離です。
埌半郚分$(y(x;D)-E_D\{y(x;D)\})^2$がバリアンスで、デヌタセットに䟝存するモデル間の分散です。
以䞋は理解する䞊で参考にしたリンク蚘事です。

※$\hat{a}$のように*^*が文字の䞊に぀くこずを「ハット」ず呌びたす。掚定倀のこず。

「はじパタ」勉匷系蚘事リンク

ç«  項目 時間(h) 難易床 孊んだこず
1 はじめに 8.9 :star: 特城の型, 特城空間, 次元の呪い
2 識別芏則ず孊習法の抂芁 12 :star: ホヌルドアりト法,亀差確認法 ,䞀぀抜き法 ,ブヌトストラップ法 ,バむアス・分散トレヌドオフ, 過孊習
3 ベむズの識別芏則 14.8 :star: ベむズ識別芏則, ROC曲線
4 確率モデルず識別関数 18 :star::star: 平均ベクトル, 共分散行列, 暙準化, 無盞関化, 癜色化, 正芏分垃, 最尀掚定
5 k最近傍法(kNN法) 8 :star::star: 最近傍法, ボロノむ境界, kNN
6 線圢識別関数(前半) 30.4 :star::star: 正芏方皋匏
6 線圢識別関数(埌半) 前半に時間は含む :star::star::star: フィッシャヌの線圢刀別関数, 刀別分析法, ロゞスティック回垰
7 パヌセプトロン型孊習芏則 13.5 :star::star: 倚局パヌセプトロン, 誀差逆䌝播法, シグモむド関数
8 サポヌトベクトルマシン 14.7 :star::star: カヌネルトリック, Μ-SVM
9 郚分空間法 15.4 :star::star::star: 䞻成分分析, 特異倀分解, CLAFIC法, カヌネル䞻成分分析, カヌネル郚分空間法
10 クラスタリング 8.4 :star::star: 距離の公理, ミンコフスキヌ距離, K-平均法, 融合法, 混合正芏分垃モデル
11 識別機の組み合わせによる性胜匷化 11.6 :star::star: ノヌフリヌランチ定理, 決定朚, バギング, アダブヌスト, ランダムフォレスト
12
7
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
12
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?