「はじめてのパターン認識」読書会 第一回の発表資料です(質疑応答の内容など反映してあります)。
$$\newcommand{\x}{{\bf x}}$$
$$\newcommand{\t}{{\bf t}}$$
$$\newcommand{\w}{{\bf w}}$$
$$\newcommand{\DL}{{\mathcal D}_L}$$
$$\newcommand{\DT}{{\mathcal D}_T}$$
$$\newcommand{\E}[2]{{E_{#1}\lbrace #2 \rbrace }}$$
自己紹介
- トデス子(@todesking)
- ScalaとSparkをつかう
- プログラマー的な者ですが今は機械学習チーム的なところでトピックモデルをやっている
- データサイエンティスト的な人を募集しています
「はじめてのパターン認識」って?
- パターン認識=いわゆる機械学習
- 機械学習の入門書として有名
- 機械学習の代表的な技術についてだいたいカバーしてある
- 記述はわりとゆるふわ
まずは全体の構成について軽く説明します
1章 はじめに
- パターン認識とは何か
- 特徴の型
- 名義尺度とか間隔尺度とか
- 1-of-k表現
- 特徴をベクトルとして表現する
- 高次元空間の性質
第二章 識別規則と学習法の分類
- 識別規則の分類
- 教師付き学習と教師なし学習
- 識別(分類)と回帰
- 汎化能力
第三章 ベイズの識別規則
- ベイズの識別規則
- ROC曲線
- 分類問題の性能を評価するための代表的な指標のひとつ
第四章 確率モデルと識別関数
- データの変換手法
- 無相関化、標準化などの、学習の下準備のためのデータ変換手法
- 多次元正規分布
- 多次元正規分布を使ったベイズの識別規則
- 確率モデルパラメータの最尤推定
第五章 k-最近傍法(k-NN)
- 最近傍法
- k-NN法とその発展
第六章 線形識別関数
- 線形識別関数
- ロジスティック回帰
第七章 パーセプトロン型学習規則
- パーセプトロン
- 誤差逆伝搬法
第八章サポートベクターマシン(SVM)
- 線形SVM(ハードマージン、ソフトマージン)
- カーネル法
- SVMの発展(ν-SVM、1クラスSVM)
第九章 部分空間法
- 主成分分析による次元削減
- カーネル主成分分析
第10章 クラスタリング
- k-means
- 階層クラスタリング
- 混合正規分布とEMアルゴリズム
第11章 識別機の組み合わせによる性能強化
- 決定木
- バギング
- ブースティング
- ランダムフォレスト
本日の内容
- 1章 はじめに
- 2章 識別規則と学習法の概要
特徴をどう表現するか? 特徴を分類する方法にはどのようなものがあるのか? 学習結果のよさをどう評価するのか? といった内容です。
具体的な学習手法については次回以降。
1章 はじめに
- 1.1 パターン認識とは
- 1.2 特徴の型
- 1.3 特徴ベクトル空間と次元の呪い
- 章末問題
1.1 パターン認識とは
物事の類型を知るはたらき、およびその内容
パターン認識の流れ
- 特徴抽出
- 対象から特徴ベクトルを得る
- 分類
- 識別規則を用いて、特徴ベクトルからクラスを得る
特徴ベクトル
特徴ベクトル=対象から得られた特徴を数値化し、ベクトルとして表現したもの
$x_1 = (1.1, 0.5, -2.0)$
クラス
分類の結果を表す値
$y_1 \in { 10円, 50円, 100円, ... }$
例: 自動販売機で、投入された硬貨の種類と真贋を判定する
- 対象: 投入口に入れられた物体
- 特徴ベクトル: 重さ、大きさ、色、材質……
- 識別規則: ???
- 出力: ${10円硬貨, 50円硬貨, ..., 偽物}$のいずれか
識別に有効な特徴をいかに早く抽出できるかが重要
パターン認識と特徴抽出
パターン認識の対象としたいものは多数ある
- 音声
- 画像
- 株価などの時系列データ
- Webサーバのアクセスログ
これらの多様なデータから特徴抽出する方法は多岐に渡るが、いったん特徴ベクトルの形にしてしまえば、その後は同じ識別規則を適用できる。
本書では、特徴ベクトルにしたあとの処理についての解説をする。
識別規則
入力データが所属する正しいクラスを同定するための規則
識別規則を作るためには、入力データとそのクラスを対にしたたくさんの事例(学習データ)から対応関係を学習する必要がある。
識別規則をいかに学習するかが重要で、本書の主題。
汎化能力
識別規則は学習データを使って作られるが、実際に使用する際は未知のデータに対して適用する。
学習データにない未知のデータに対して正しいクラスを識別できる能力を汎化能力という。
未知のデータに対する能力をいかに評価するかがパターン認識の成否を決める鍵の一つ
1.2 特徴の型
パターン認識の対象から得られる特徴は、いくつかの種類に分類できる。
- 定性的特徴
- 名義尺度
- 順序尺度
- 定量的特徴
- 比例尺度
- 間隔尺度
1.3.1 特徴ベクトル空間
特徴ベクトル=対象から得られた特徴を数値化し並べたもの
特徴数が$d$個であれば、$d$次元ベクトルとなるり、このベクトルは$d$次元線形空間を張る。
16x16画素の画像データの場合、$16 \times 16 = 256$次元ベクトル空間中の1点として表現される。
1.3.2 次元の呪い
16x16画素の画像データにおいて、各画素が16階調だとする。
この画像データ=256次元のベクトルが取りうる値の数は$16^{256} \sim 1.80 \times 10^{308}$通りという膨大なものになる。
可能な組み合わせの0.1%くらいは用意したいね、と思ったら$10^{305}$個のデータが必要に……
学習データとして1000種類の画像を用意しても、$10^3$通りの組み合わせをカバーするにすぎない。
1.3.2 次元の呪い
Bellmanは、未知の複雑な関数を学習するのに必要なデータの数が、次元の増加とともに指数関数的に増加することを次元の呪いと呼んだ。
「次元の呪い」として知られている現象はこの他にもいくつかあるが、いずれもベクトルの次元が高くなることで困難が起こるというもの。
次元の呪い
Wikipediaによれば、
The curse of dimensionality refers to various phenomena that arise when analyzing and organizing data in
high-dimensional spaces (often with hundreds or thousands of dimensions) that do not occur in low-dimensional
settings such as the three-dimensional physical space of everyday experience.
次元の呪いとは、高次元空間のデータを分析・整理するときに起こる、低次元空間では起こらない様々な現象を指す。
組合せ爆発によるもの(ref: フカシギの数え方)、距離の性質によるもの、等
5.3.2(p65)に次元の呪いの別の例あり(体積の大半が周辺部にいく)
高次元空間の持つ性質
文書の分類を、文書に出現した単語の頻度を特徴として行なうことを考える。
全文書中に登場する単語の種類は、推定24万(「広辞苑」に含まれる見出し語数)
特徴ベクトルとして
$x = (1, 0, ..., 2, 5, 0, 0, 0, ..., 0)$
という24万次元のベクトルが得られる。
$d$次元の単位超立方体=各辺の長さが1の$d$次元立方体において、中心から頂点までの長さは
$$D(d) = \left(d\times\left(\frac{1}{2}\right)^2\right)^{\frac{1}{2}} = \frac{1}{2}\sqrt{d}$$
となる。一方中心から面までの長さは$\frac{1}{2}$なので、中心から頂点までは中心から面までの長さの$\sqrt{d}$倍となる。
例題1.2
$d$次元超立方体の面の数は$2d$個であることを示せ
→各軸にそれぞれ2つの超面をもつので$2d$個
$d$次元超立方体は、5.4.4の近似近傍探索と、11.2の決定木で重要な働きをする
特徴量をベクトルではなくテンソルで表現する
紹介されていた論文: Detecting the Number of Clusters in n-Way Probabilistic Clustering
データの関係性をハイパーグラフ(グラフ構造の強いやつ。すごい)として記述する。
ハイパーグラフはテンソルとして表現できる。
MLP「関係データ分析」に記述あり。
醜いアヒルの子定理
$n$匹のアヒルの中にいる醜いアヒルの子を見分けようとする…… というシチュエーションからこの名前になった。
考えられる特徴量はいくつもあるが、それら全てを平等に扱うと、「醜いアヒルと普通のアヒルは、普通のアヒル同士と同じくらい似ている」
という結論になってしまう。
目的に応じてどの特徴量が重要なのかは違うので、特徴抽出は大切だという教訓がある。
章末問題
1.1 あなたの利き手でない方の人差指と中指の指紋を区別したい。どのような特徴を取ればよいか観察せよ。
1.2 辺の長さが$a$の$d$次元超立方体について、
(1) 頂点の数が$2^d$であることを示せ
(2) 表面積を求めよ
(3) 超立方体を構成する$m$次元超平面($0 \le m \le d - 1$)の個数が$2^{d-m}\binom dm$で表されることを、3次元立方体で確かめよ。
(4) 超立方体を構成する$m$次元超平面の総数を求めよ
(5) その式から、5次元超立方体を構成する超平面の数を求めよ
皆さんへの宿題とします(´･_･`)
2章 識別規則と学習法の概要
- 2.1 識別規則と学習法の分類
- 2.2 汎化能力
- 章末問題
学習データを使って識別規則を作る方法と、その識別規則が未知のデータに対してどれだけ性能を発揮できるかを表す汎化能力について。
2.1.1 識別規則の構成法
- 識別規則: 入力データ${\bf x}$からクラス$C_i \in \Omega = { C_1, ..., C_K}$への写像
- 特徴ベクトル${\bf x}$を入れたらどのクラスに当てはまるか返してくれる関数と思えばよし
この写像をどのように作るか。
2.1.1 識別規則の構成法
- 事後確率
- 入力がクラス$c$に属する確率$P(c|\x)$が最大となるクラスを返す
- 確率$P(c|\x)$を求める必要がある
- 例: MAP推定(3章)
2.1.1 識別規則の構成法
- 距離
- 入力ベクトル$\x$と各クラスの代表ベクトルの距離を比較し、一番近いクラスを返す
- 距離 の定義と、代表ベクトルの決め方が必要
- 例: 最近傍法、k-NN(5章)
2.1.1 識別規則の構成法
- 関数値
- ある関数$f(\x)$の値によってクラスを決める。基準は正負や最大値など。
- 関数$f$およびクラス決定の基準が必要
- この関数を識別関数という
- 例: パーセプトロン(7章)、SVM(8章)
2.1.1 識別規則の構成法
- 決定木(11章)
- 木構造になったルール
- 入力$\x$についてある規則を適用し、その真偽によってどちらかの枝に進む
- たどり着いた葉によってクラスを決める
2.1.2 教師付き学習
識別規則を$\x$を入力としてクラス$y$を返す関数$y=f(\x)$の形で表す。
識別規則の学習とは、この$f$を学習データから決めること。
例: 線形識別関数
識別関数$f$を
$y=f(\x;\w) = w_1x_1 + \cdot \cdot \cdot + w_dx_d = \w^T\x$
という形で表し、$y$の正負により二つのクラスどちらかに割り当てる。
学習データを元にパラメータ$\w$を調整することで、入力データから正しいクラスを得られるような識別規則を作る。
例題2.1
線形識別関数として、定数項$b$がついた
$f(\x;\w) = b = \w^T\x$がよく使われる。この関数は厳密な意味で線形か?
線形であるのは、重ね合わせの定理$f(ax) = af(x), f(x + y) = f(x) + f(y)$が成り立つ場合である。
定数項$b$の存在により、$$
f(x) + f(y) = b + \w^T(\x + {\bf y}) = f(x) + f(y) - b
$$
となり、よって$f$は線形ではない。
このような関数をアフィン関数という。
入力ベクトル$\x = (x_1, x_2, ..., x_n)$にダミー要素$x_0 = 1$を加え、$f(\x) = w_0 x_0 + w_1 x_1$という形式にすれば線形関数となるため、
定数項がついている場合も線形識別関数と呼ばれる。
教師付き学習
クラスの識別規則を学習するためには、入力データ$\x$とそのクラス$t$を対にした学習データが必要になる。
クラスを指定するデータを教師データという。ラベルとも。
2クラスの場合は$t={+1, -1}$で表現するのが一般的。
3クラス以上の場合は、1-of-k表現(one-hot encodingとも)と呼ばれる形式を使うことが多い。
教師付き学習
クラスが全部で$C$個ある場合、$i$番目のクラスを、$i$番目の要素が1で残りの要素は0の$C$次元ベクトルで表す。
例: クラス3の場合 $t = (0, 0, 1, 0, 0)^T$
クラスは名義尺度のため、数字として扱うよりこのほうが扱いやすいため……
だが、ラベルを1-of-kしたいのって一部の場合だけでは?? kNNだったら普通の数字でいいのでは
線形多クラス識別問題(6.2, p78)では、この表現が有効に使われている。
学習に使われる入力データと教師データの対の集合$(\x_i, \t_i) (i = 1, ..., N)$を学習データセットと言い、$\DL$で表す。
教師付き学習
学習の目的は、$\DL$を使ってなるべく良い識別規則を与える$\w$を求めること(どうなれば「良い」のかはこのあとやります)
ノンパラというのがあってね…… というのは省略。
具体的な学習の方法は3章以降。
教師付き学習と線形回帰
入力値$\x$を元に、いくつかあるクラスのどれかを出力するのを識別(分類)と言う。
出力が連続値なのを回帰(関数近似)という。
線形関数によって近似を行う場合は線形回帰と呼ばれる。
機械学習は大きく「識別」「回帰」に分けることができるが、はじパタでは主に識別問題を中心に扱う。
教師なし学習
教師データが存在しない学習もある。
クラスタリングが代表的(10章)
教師なし学習、自己組織化学習などという。
教師ありデータと教師なしデータを両方使う形質導入学習もある
他に半教師あり学習なども。
半教師あり学習のモデル仮定などを見ると良いかも?
2.2 汎化能力
よい識別規則とはどのようなものか?
手元にあるデータを正しく分類できるだけではだめで、未知のデータに対しても正しく動かなければならない。
未知のデータに対する性能を汎化能力、その際の誤差を汎化誤差という。
汎化能力を推定する
- 汎化能力=未知のデータに対する性能
- 測定不能！！
- しかし、手元にあるデータを使って推定することはできる。
- 「クロスバリデーション」と「情報量基準」(AIC, BIC, WAIC, ...)というのがメジャー
- 本書ではクロスバリデーションについて解説
- 理論的な話についてはベイズ統計の理論と方法がおすすめです(むずかしい)
2.2.1 学習データとテストデータの作り方
(本書では「正例のみのデータを使って100円玉を識別する」というマニアックな例が出てきますが、ややこしいので別の例を使います)
硬貨を10円玉と100円玉に分類する識別規則を作りたい。手元にあるデータ10000個を、8000個の学習データ$\DL$と2000個のテストデータ$\DT$に分割し、
$\DL$を使用して作った識別規則の$\DT$に対する誤り率を$\epsilon(p_L, p_T)$で表す。
また、学習データ$\DL$に対する誤り率(再代入誤り率)を$\epsilon(p_L, p_L)$で表す。
例題2.2 再代入誤り率が大きい場合、どのような対処法を考える必要があるか
学習に使用したデータを正しく分類できないということは、識別機の性能が足りないということなので、何らかの方法で性能を上げる必要がある。
例えばパラメータを増やす、別のモデルを使うなどの方法がある。
(1) ホールドアウト法
手元のデータを二つに分割し、一方を学習に使い、もう一方をテストに使用する。こうして得られた誤り率$\epsilon(p_L, p_T)$をホールドアウト誤り率という。
真の分布を$p$としたとき、$p$を学習とテスト両方に使ったときの誤り率を真の誤り率$\epsilon(p, p)$と表す。この値は直接計算できない。
計算可能なホールドアウト誤り率と再代入誤り率を使って、真の誤り率について知ることはできないだろうか。
(1) ホールドアウト法
真の誤り率、再代入誤り率、ホールドアウト誤り率の間には次の関係がある。
$$\E{\DL}{ \epsilon(p_L, p_L) } \le \epsilon(p, p) \le \E{\DL}{ \epsilon(p_L, p_T) }$$
つまり、
再代入誤り率の期待値 $\le$ 真の誤り率 $\le$ ホールドアウト誤り率の期待値
(1) ホールドアウト法: 余談
期待値の表記$E_{x}\lbrace f(x) \rbrace$というのはけっこうよく出てきます。
これは、$x$の分布$p(x)$が与えられたときの$f(x)$の期待値という意味で、$\int f(x)p(x) dx$と解釈すればよい。
(1) ホールドアウト法
再代入誤り率の期待値 $\le$ 真の誤り率 $\le$ ホールドアウト誤り率の期待値
つまり、ホールドアウト法を使うことで真の誤り率がどの程度なのか推定できる！！
本書には特に書いてないですが、この式が適用できる条件があります(とは言え、一般的には適用できることが多いらしい)。
なるべく間違った結果を返すように作った識別規則は、この条件を満たさないので適用範囲外らしい。
- 文献 [15]: Introduction of Statistical Pattern Recognition (Statistical Pattern Recognitionという本とは別です)
- 「わかりやすいパターン認識」5章資料
- 機械学習プロフェッショナルシリーズ「統計的機械学習」
- この条件が成り立つための性質についての記述があるとのこと。
あたりを参照するとよさそう。
(1) ホールドアウト法
(ある条件のもとでは)ホールドアウト法で汎化性能が推定できることがわかった。
しかし、手元のデータの一部をテスト用にとっておく必要があるため、
- 学習データを多くすれば識別規則の性能が上がりそうだが、性能を精度よく推定できない
- テストデータを多くすれば性能を精度よく推定できるが、性能が上がらない
というジレンマがある。
(2) 交差確認法
- 手元のデータを$m$個のグループに分割し、$m-1$個のグループを使って学習し、残り1個のグループでテストする。
- テストに使うグループを変えて$m$回繰り返し、平均の誤り率を求める
この手順によって、性能と推定精度を両立できる。
ただし、グループの分割のしかたによる偏りがあるため、分割のしかたを変えて繰り返すことが必要。
(3) 一つ抜き法(leave-one-out法、ジャックナイフ法)
交差確認法において、グループの要素数を1個にしたもの。
ところで渡邊澄夫先生によるクロスバリデーションとWAICの関係についての解説が読めます。
(4) ブートストラップ法
手元にある$N$個のデータを元に学習し、同じデータで測定した再代入誤り率を$\epsilon(N, N)$で表す。
この誤り率は真の誤り率より低く出るはず。この差をバイアスと言う。
$N$個のデータから$N$回復元抽出を行って作ったブートストラップサンプルを用いてバイアスを修正することができる。
あるブートストラップサンプル$N^*$を用いて測定した再代入誤り率$\epsilon(N^*, N^*)$と、元々のデータ集合を用いた誤り率の差
$$bias = \epsilon(N^*, N^*) - \epsilon(N^*, N)$$
を、たくさんのブートストラップサンプルで求めた平均値$\overline{bias}$がバイアスの推定値となる。
真の誤り率の推定値は、バイアスを使って
$$\epsilon = \epsilon(N, n) - \overline{bias}$$
で与えられる。
11.5(ランダムフォレスト)では、ブートストラップ法を使った別の誤り率推定法について説明してある
2.2.2 汎化能力の評価法とモデル選択
パラメータ数をいくつにするか、どのような式を使うかなど、識別規則には様々な選択肢がある。
複数モデルがある場合、何らかの基準を決めて一番良いものを選ぶことをモデル選択という。
本書では、色々なモデルを同じデータで学習させ、同じテストデータを使って評価した誤り率が最小になるものを選ぶと
いう方法が紹介されていますが、他にも情報量基準を使う方法などあります。
モデル選択: 多項式回帰の例
ノイズ$\epsilon$が含まれた関数$f(x) = h(x) + \epsilon$から得られたデータを元に、信号成分$h(x)$を推定する回帰問題を考える。
$$ h(x) = 0.5 + 0.4\sin(2\pi x) $$
$$ \epsilon \sim N(\epsilon, 0, 0.05) $$
モデル選択: 多項式回帰の例
$f$がどんな関数なのかわからないので、さまざまな$p$次多項式を使ってみる。
$$y(x;a) = a_0 + a_1 x + a_2 x^2 + ... + a_p x^p$$
ここで$y(x;a)$という表記は、パラメータ$a$を指定した関数$y(x)$という気持ちが込められていて、よく出てきます。
モデル選択: 多項式回帰の例
多項式のパラメータ$a$は、学習データセット$D$から一意に定められるため(※二乗誤差を最小にする場合)、$y(x;a)$を$y(x;D)$と表す。
真の関数$h(x)$とどの程度近いかを、平均二乗誤差MSE
$$MSE = \int (y(x;D) - h(x))^2 p(x)dx \\ = E_x\lbrace y(x;D) - h(x)^2 \rbrace$$
で評価する。評価には$x$の確率分布$p(x)$が必要だが、区間$[0, 1]$で一様に分布しているので$p(x)=1$
平均二乗誤差を使う理由として、微分可能なので扱いやすい、ノイズが正規分布の場合は誤差が平均してゼロになる、などの理由がある。
これ以外の関数を使うこともあり、極端な外れ値を含む場合は絶対値を使ったり、$|x| \lt a$の範囲で$x^2$、それ以外では接続部の勾配が等しくなるような直線で構成された関数を使ったりする。らしい。
モデル選択: 多項式回帰の例
一つのデータセットだけで評価したMSEはノイズが乗っているため、多数のデータセットで求めたMSEの平均$MSE_D$を使う。
$$MSE_D = E_D\lbrace (y(x;D) - h(x))^2 \rbrace $$
モデル選択: バイアスとバリアンス
複数のデータセットで学習したモデルを比較してみる(図については本を参照してください……)
一次式を使った場合は、データから大きく外れている(バイアスが大きい)。
しかし、どのデータセットを使ってもだいたい同じ直線が得られる(バリアンスが小さい)。
6次式を使った場合は、逆にデータへの当てはまりは良いがデータセットによって大きく違う曲線になる(低バイアス、高バリアンス)
一般的に、モデルのバイアスを下げようとするとバリアンスが大きくなるという傾向がある(バイアス・バリアンストレードオフ)
モデル選択: バイアスとバリアンス
MSEの平均$MSE_D$の式は、バイアスとバリアンスの成分に分解できる。
$$E_D\lbrace (y(x;D) - h(x))^2 \rbrace \\ = (E_D\lbrace y(x;D) \rbrace - h(x)) ^2 + \\ E_D \lbrace (y(x;D) - E_D \lbrace y(x;D)\rbrace)^2\rbrace$$
導出は皆さんへの宿題とします！！！！！！！
モデル選択: 多項式回帰の例
多項式の次数を大きくすると、学習データに対する当てはまりは良くなる。
しかし、テストデータに対する当てはまりは、ある程度次数が大きくなると逆に悪くなる(過学習: オーバーフィッティング)
例の場合、汎化能力は3次の多項式を使うのが一番高いことがわかる。
モデル選択
例では回帰を使ったが、識別問題でも同様に、交差確認法やブートストラップを使って汎化誤差を推定することでモデルを選択することができる。
これらの手法はデータの分布を統計モデルで記述しなくていいのでよく使われる。
一方、AICやBIC、MDLといった情報量基準を使う方法もある。