MIT OCW, Machine Learning 01日目 線形分離とパーセプトロン

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

• • • Example
      • What kind of solution would be?
      • Model Selection
    • Linear classifiers through origin
      • Learning Algorithm: the Perceptron
    • Analysis of the Perceptron Algorithm
      • Perceptron, Convergence, and Generalization
      • Convergence in a Finite Number of Updates
      • Margin and Geometry
      • Generalization Guarantees
    • Maximum Margin Classifier?

Example

ビルの中への入場者管理業務を自動化することを考える.過去に入場しようとして許可されたものと許可されなかったものの顔写真のデータから,入場希望者の新しい顔画像をとって許可/拒否を与えるアルゴリズムを開発する.この過去のデータはそれぞれの画像にlabel付けがされている.positiveにラベル付された画像は入場許可された人の顔画像であり,negativeは入場拒否された人の顔写真である.入場拒否された人は許可された人よりずっと少ないと推測できるので,全く無関係の人の顔写真を入場拒否者データに加えて補うことが出来る.結局やるべきことは,非常に少数な既知のラベル付き画像(training set)を使って,画像をバイナリ($\pm 1$)に移す関数(classifier)を構成することである.$+1$はpositive, $-1$はnegativeを表す.
より形式的にいうと,それぞれの画像(グレースケールとする)は$\mathbf{x}$という$d$次元の縦ベクトルとして,その縦ベクトルのそれぞれの要素は画像の対応するピクセルの濃淡を表現している.training setは$\{(\mathbf{x_1}, y_1), ..., (\mathbf{x_n}, y_n) \}$によって構成され,$\mathbf{x_i}$は画像のベクトル表現,$y_i$は$\mathbf{x_i}$に対応するラベルである(positive: $+1$, negative: $-1$).classifier $f: \mathbb{R}^d \rightarrow \{-1, 1\}$をtraining set だけから構成する.画像に付属的な情報,例えば体重や身長は一切付与されない.

What kind of solution would be?

training set の要素数は50個で,それぞれの画像データは$128 \times 128$次元で,更にピクセルごとの濃淡は$0$から$255$の整数値を取るとする.例えば各ベクトルの第$i$要素が全て異なるような$i$が存在すると仮定する.このとき,
$$\{0, ..., 255\}^{16384} \ni x' \mapsto \begin{cases} 1 \ \ \ &(x'_i\text{あるpositive なtraining data }\mathbf{x}\text{があって,} \mathbf{x_i'} = \mathbf{x_i}) \\ -1 &(otherwise) \end{cases}$$
としてclassifierを定義できる.これはtraining dataには必ず正しい推測を返すが,新しいデータに対して正しい推測をしてくれるとは到底考えられない.我々の目的はtraining setに含まれない新しい画像に対して推測することなのだから,このclassifierは非合目的.我々はtraining setをよくgeneralizeするclassifier, つまりtraining setに対する成績と新しい画像に対する成績がともに良好であるclassifierを見つけたい.

Model Selection

上の問題で考えられるclassifierは$2^{256^{128 \times 128}}$個有るわけだが,そのclassifierの集合を有用そうなclassifierの部分集合(クラス)に制限することが重要になる.制限された集合が大きすぎると例で上げたような役立たずなclassifierを考えなければならなくなるし,小さすぎるとよいclassifierが見つけられないかもしれないので,適切な制限を与えることがmachine learningの一大問題であり,model selection problemともいう.

Linear classifiers through origin

ここで,linear classifiersというクラスに制限して考える.これは
$$f(\mathbf{x}; \theta) =sign (\theta_1 x_1 + \cdots + \theta_d x_d) = sign (\theta^T \mathbf{x})$$
という関数である.ただし$sign : \mathbb{R} \ni r \mapsto \begin{cases} 1 \ \ &(r \geq 0)\\ -1 &(r < 0) \end{cases}$である.
$\theta = [\theta_1, ..., \theta_d]^T \in \mathbb{R}^d$はパラメータであって,これによって具体的なclassifierが決定される.このようなclassifierは幾何学的に解釈することが出来る.$\theta^T \mathbf{x} =0$は原点を通る$d-1$次元の超平面と考えることができ,この超平面を境界にして$\mathbb{R}^n$の元を分類する.

figure 1.

2次元で考えると,fig.1 のようになる.$\theta \mathbf{x} <0$となる点を$-1$, $\theta \mathbf{x} >0$となる点を$+1$とするのである.ところで,画像を1つの縦ベクトルで表現することで失われる情報がいくつか有る.というのは,元の画像では隣り合っているピクセルが,ベクトル表現では128(あるいはそれ以上)要素分離れているかもしれない様に,平面上の位置関係が失われてしまうのである.もっとも,linear classifierはこうした情報は一切考慮しない.すべてのtraining setとこれからのデータのそれぞれのベクトルの$i, j$成分を入れ替えても,linear classifierのパラメータも同じ場所を入れ替えれば同じ分類を行う.平面的な情報を考慮したいなら,他のmodelを導入することになる.

Learning Algorithm: the Perceptron

linear classifierを導入したところで,最適なパラメータ$\theta$を求める方法を考える.これをestimation problemということがある.最適な$\theta$とは,training setに対して分類を行って最も間違いが少なくなるような$\theta$のことと考える.つまり,training error
$$\hat{E}(\theta) = \frac{1}{n} \sum_{i=1}^n \left(1 - \delta(y_t, f(\mathbf{x_t}; \theta)) \right) = \frac{1}{n} \sum_{t=1}^n Loss(y_t, f(\mathbf{x_t}; \theta)) \ \ \ \delta: \text{Kronecker's delta}$$
を最少にする$\theta$を考えるのである.関数$Loss$を,適当に重み付けすることも出来る.例えば本来$-1$とすべき画像を$+1$と分類したときこの間違いをより大きく評価するなどとできる.ここでは単純にzero-one loss, つまり正当を0, 誤答を1とするLossを使う.
実際に$\theta$を決める方法として,training setのそれぞれの要素に,誤答のたびに$\theta$を調整していくことを繰り返す方法が有る.このようなアルゴリズムで最も単純なものをperceptron update ruleという. それぞれのtraining imageに
$$\theta' \leftarrow \theta + y_t \mathbf{x_t} \ \ \ \ \text{if} \ \ y_t \neq f(x_t; \theta)$$
を行うことを行い,これを何度も繰り返す.
$y_t=1, f(\mathbf{x_t}, \theta) = -1$であったとき, $\theta' = \theta + \mathbf{x_t}$. $\theta'\mathbf{x_t}=\theta \mathbf{x_t} + \mathbf{x_t}^T \mathbf{x_t} \geq \theta \mathbf{x_t}$となるから,$\theta$は正答の方へと更新されたと言える.$y_t=-1, f(\mathbf{x_t}, \theta)= 1$の場合も同様である.

Analysis of the Perceptron Algorithm

perceptron algorithmの更新はtraing setのすべての元を正しく分類できたときに終了する.linear classifierによって正しい分類が可能であれば,perceptron algorithmは必ずこのようなclassifierを有限回の更新で見つけられる.

Perceptron, Convergence, and Generalization

$k$をperceptron algorithmによる更新の回数とし,$\theta^{(k)}$を$k$回更新した後のパラメータ$\theta$とする.
つまり$y_t(\theta^{(k)})^T\mathbf{x_t} < 0$なら$\theta^{(k+1)} = \theta^{(k)} + y_t\mathbf{x_t}$と更新する.

Convergence in a Finite Number of Updates

training dataは有界($R = \sup \{\|\mathbf{x_t}\|\}_1^n < \infty$)とする.さらに,training setを正しく分離するlinear classifierが存在するという強い仮定のもとでのみ議論する.つまり,$\gamma > 0$があって,$y_t(\theta^*)^T\mathbf{x_t} \geq \gamma$が常に成り立つような$\theta^*$が存在すると仮定する.この$\gamma$をmarginという.
1. $(\theta^*)^T \theta^{(k)}$が更新ごとに少なくとも線形に増加する
2. $\|\theta^{(k)}\|^2$は更新ごとにせいぜい線形に増加する

という補題のによって証明する.
proof 1.

$(\theta^*)^T \theta^{(k)} = (\theta^*)^T \theta^{(k-1)} + y_t (\theta^*)^T \theta^{(k-1)} \geq (\theta^*)^T \theta^{(k-1)}+ \gamma$だから,$(\theta^*)^T \theta^{(k)} \geq k\gamma$.

proof 2.

$$\begin{aligned} \|\theta^{(k)} \|^2 &= \|\theta^{(k-1)} + y_t \mathbf{x_t}\|^2 \\ &= \|\theta^{(k-1)}\}^2 + 2y_t (\theta^{(k-1)})^T \mathbf{x_t} + \|\mathbf{x_t}\|^2 \\ &\leq \|\theta^{(k-1)}\|^2 + \|\mathbf{x_t}\|^2 \ \ \ \ \ \ ( \because y_t(\theta^{(k-1)})^T \mathbf{x_t} < 0)\\ &\leq \|\theta^{(k-1)}\|^2 + R^2\end{aligned}$$
よって $\|\theta^{(k)}\|^2 \leq k R^2$.

さて, 1,2 から,
$$1 \geq \cos(\theta^*, \theta^{(k)}) = \frac{(\theta)^T \theta^{(k)}}{\|\theta^{(k)}\| \| \theta^*\|} \geq \frac{k\gamma}{\sqrt{kR^2} \|\theta^*\|} = \sqrt{k} \frac{\gamma}{R\|\theta^*\|}$$
よって$k \leq \frac{R^2\|\theta^*\|^2}{\gamma^2}$であって,たしかに有限.

Margin and Geometry

$\gamma/\|\theta^*\|$は$\theta^*$によって特徴づけられるdecision boundaryと,training setの元の距離の距離の最最小値だから$\gamma/\|\theta^*\|$は$\theta^*$がどれほどうまくtraining setを分割しているかの指標と考えることが出来る.$\gamma_{geom} := \gamma/\|\theta^*\|$とすると,$\gamma_{geom}^{-1}$は問題の難しさの指標と考えることが出来る.
また,$\gamma_{geom}$によって
$$k \leq \left( \frac{R}{\gamma_{geom}}\right)^2$$
と最大の更新回数は抑えられる.$(R/ \gamma_{geom})^2$がlinear classificationの難しさの指標であることの証明は後でVC-dimensionという概念とともに与える.

Generalization Guarantees

すでに述べたように,未知のデータ,training setにない画像に対する性能が問題となる.未知のデータが以下の2つの性質を満たすと仮定する.
1. $\| \mathbf{x_t}\| \leq R$
2. ある$\theta^*$に$y_t (\theta^*)^T \mathbf{x_t} \geq \gamma$

画像とラベルを与えられるごとに1回だけ$\theta$の更新を行う(このような更新方法をon-line algorithmという)とき,同様の議論によって,というより議論は変わらず$k \leq (R/ \gamma_{geom})^2$.よって仮定のもとでclassifierは有限会の更新で収束する.

Maximum Margin Classifier?

正しく画像を分類し$\gamma/\|\theta^*\|$が大きくなる$\theta^*$の存在を仮定して議論を行ってきたが,直接(?)このような$\theta^*$を計算するようなアルゴリズムにSupport Vector Machine, SVMがある.次節ではSVMについて詳しく論じる.