機械学習アルゴリズム（サポートベクトルマシン，ブースティング，多値判別）を数学的に理解するために、金森敬文『統計的学習理論』を読んで分かったことをまとめていこうと思います。自分なりに書き直した部分があるので、もし説明不足や誤りがあればご連絡いただけると幸いです。

今回はイントロダクションということで、機械学習に関数解析が出てくるまでの簡単な流れを書きたいと思います。

キーワード：直交分解、カーネル法、カーネル関数、再生核ヒルベルト空間

問題設定

まずは簡単な言葉の定義の確認から。

データとは一般に$n$次元空間$\mathbb{R}^n$の元（および部分集合）のことを指します。例えば、ある小学校の1年生全員の身長と体重の組は$\mathbb{R}^2$の元の集まりと思います。また、$100\times100$画素の白黒画像は、各画素の色の濃淡を実数値で表せば$\mathbb{R}^{10000}$の元と思うことができ、テキストデータでは各単語が出現する頻度を並べた1000次元程度のベクトルを用いることがあるようです。

データから役に立つ情報を得ることを学習するといいます。統計学における推定や予測とほぼ同義語です。

入力データがとりうる値の集合を入力空間といい、$\mathcal{X}$で表します。
出力データがとりうる値の集合を出力空間といい、$\mathcal{Y}$で表します。
入力が$x$、出力が$y$のとき、$(x,y)\in\mathcal{X}\times\mathcal{Y}$を出入力データとよびます。
出力データが有限集合（例えば$\mathcal{Y}=\{1,-1\}$など）のとき、$\mathcal{Y}$の元をラベルといいます。
入力空間から出力空間への関数$f:\mathcal{X}\to\mathcal{Y}$を（$\mathcal{X}$、$\mathcal{Y}$に対する）仮説といいます。
仮説全体の集合を（$\mathcal{X}$、$\mathcal{Y}$に対する）仮説集合といい、$\rm{Hyp}(\mathcal{X},\mathcal{Y})$と書きます。

学習アルゴリズムとは、データを仮説に変換する「関数」とみなすことができます。つまり、観測データの集合$\{(x_n, y_n)\}_n$または$\{x_n\}_n\subset\mathcal{X}$が与えられたときに、何かしらのアルゴリズムを経て適切な仮説$f:\mathcal{X}\to\mathcal{Y}$を得る操作のことを学習アルゴリズムと言えると思います。

適切な仮説をみつけるために、出力値と予測結果の誤差を測る関数（損失関数）$\ell:\rm{Hyp}(\mathcal{X},\mathcal{Y})\times\mathcal{X}\times\mathcal{Y}\to\mathbb{R}_{\ge0}$を用意します。

例.　$\mathcal{Y}=\{1, -1\}$（ラベルが2種類のみ）とし、入力データから対応するラベルを予測する問題（2値判別問題）を考えます。イメージしやすいように

1=\text{通常メール},-1=\text{迷惑メール}

と思って、迷惑メールかどうかを判別する問題を考えても構いません。このとき、代表的な損失関数として次の0-1損失 $\ell_{01}:\rm{Hyp}(\mathcal{X},\mathcal{Y})\times\mathcal{X}\times\mathcal{Y}\to[0,1]$があります：

\ell_{01}(h(x),y):=
\begin{cases}
0,& h(x)=y,\\
1,& h(x)\neq y.
\end{cases}

もし、入力データ$x$に対する真のラベル$y_x$をいくつか知っているのであれば、$x$についての和$\sum_x \ell_{01}(h(x),y_x)$を計算することで、仮説$h$がどのくらい誤っているかを測ることができます（誤りが多いと損失関数の値も大きくなる）。しかし、送られうるメールのテキストは無数にあるので、考える入力空間全体で考えようとすると和の計算が難しそうです。

予測損失と経験損失

ここでは出入力データを確率変数$(X,Y)$で表し、$(X,Y)$は確率分布$D$に従うとします。損失関数を$\ell:\rm{Hyp}(\mathcal{X},\mathcal{Y})\times\mathcal{X}\times\mathcal{Y}\to\mathbb{R}_{\ge0}$とします。このとき、$R:\rm{Hyp}(\mathcal{X},\mathcal{Y})\to\mathbb{R}$を

R(h):=\mathbb{E}_{(X,Y)\sim D}[\ell(h(X), Y)]

と定義します。$R(h)$を仮説$h$に対する予測損失といいます。平たく言えば、$R(h)$は$h$の誤差の期待値を表しています。

ここで注意したいのは、データの分布$D$は未知なので計算できません。

次に、データ$(X_i,Y_i)$が観測されたとします（$i=1,\ldots,n$）。このとき、$R^e:\rm{Hyp}(\mathcal{X},\mathcal{Y})\to\mathbb{R}$を

R^e(h):=\frac{1}{n}\sum_{i=1}^n \ell(h(X_i),Y_i)

と定義する。$R^e(h)$を仮説$h$の経験損失といいます。経験損失は観測データから誤差の平均をとっただけなので、いつでも計算できます。

データの独立性を仮定したり、大数の法則をもちいることで、データ数が十分大きければ、経験損失と予測損失は近い値をとることが分かります（詳しくはテキスト参照）。

カーネル法の基礎

ある程度用語の準備ができたので、テキストで最初に出くわす真新しい（※個人の感想）概念であるカーネル法（カーネル関数と再生核ヒルベルト空間）がどのような場面で登場するのかについて述べたいと思います。

線形モデルを用いた学習

$n$個のデータ$(x_1, y_1),\ldots,(x_n, y_n)\in\mathcal{X}\times\mathbb{R}$が観測されたとします。出力$y_i$たちを$\mathbb{R}^D$上の線形関数$f:\mathcal{X}\to\mathbb{R}$,

f(x)=\sum_{i=1}^D\beta_i\phi_i(x),\quad(\beta_i\in\mathbb{R})

で近似するモデルを線形モデルといいます（ただし$\phi_i:\mathcal{X}\to\mathbb{R}$は既知）。$\beta:=(\beta_1,\ldots,\beta_D)$，$\phi(x):=(\phi_1(x),\ldots,\phi_D(x))$とおき、$\mathbb{R}^D$の内積を$\langle\cdot,\cdot\rangle$で表すことにすると

f(x)=\langle\beta,\phi(x)\rangle

と表すこともできます。損失関数は以下を用いることにします：

\ell(\beta,\lambda):=\sum_{i=1}^n(y_i-\langle\beta,\phi(x_i)\rangle)^2 +\lambda\|\beta\|^2.

ただし、$\lambda\|\beta\|$はペナルティ項と呼ばれるもので、$\lambda>0$は人間が与える定数です。

X:=\begin{pmatrix}
\phi(x_1)\\
\vdots\\
\phi(x_n)
\end{pmatrix}\in\mathbb{R}^{n\times D},\quad \boldsymbol{y}:=
\begin{pmatrix}
y_1\\
\vdots\\
y_n
\end{pmatrix}\in\mathbb{R}^{n}

とおいたとき、$\ell(\beta,\lambda)$を最小にするパラメータ$\hat{\beta}\in\mathbb{R}^D$は

\hat{\beta}=(X^T X + \lambda I)^{-1}X^T \boldsymbol{y}

で与えられます（詳細は割愛しますが微分とか計算します）。しかし、次元$D$が非常に大きいと$\hat{\beta}$の数値計算は困難になります。この問題を解決するためにはどうしたらよいでしょうか？

直交分解

そこで、$S$を$\phi(x_1),\ldots,\phi(x_n)$が張る$\mathbb{R}^D$の部分空間とし、$\mathbb{R}^D=S\oplus S^{\bot}$と直交分解します。$\beta=\beta_S+\beta_{\bot}$とすると

\ell(\beta,\lambda)=\sum_{i=1}^n(y_i-\langle\beta_S,\phi(x_i)\rangle)^2 +\lambda\|\beta_S\|^2+\lambda\|\beta_{\bot}\|^2

と表されます。したがって最適解であるためには$\beta_{\bot}=0$が必要です。つまり、最適解の候補は$\phi(x_1),\ldots,\phi(x_n)$の線形結合した形のものを考えればよいので

\beta = \sum_{i=1}^n\alpha_i \phi(x_i)

とおきます。さらに

\begin{align*}
k(x,x')&:=\langle\phi(x),\phi(x')\rangle,\\
K_{ij}&:=k(x_i,x_j)
\end{align*}

とおくと

\begin{align*}
\ell(\beta,\lambda)
&=\sum_{i=1}^n(y_i-\langle\beta,\phi(x_i)\rangle)^2+\lambda\|\beta\|^2\\
&=\sum_{i=1}^n\left(y_i-\left\langle\sum_{j=1}^n\alpha_j \phi(x_j),\phi(x_i)\right\rangle\right)^2+\lambda\left\|\sum_{j=1}^n\alpha_j \phi(x_j)\right\|^2\\
&=\sum_{i=1}^n\left(y_i-\sum_{j=1}^n\alpha_j\langle \phi(x_j),\phi(x_i)\rangle\right)^2+\lambda\sum_{i,j=1}^n\alpha_i\alpha_j \langle \phi(x_i),\phi(x_j)\rangle\\
&=\sum_{i=1}^n\left(y_i-\sum_{j=1}^n \alpha_j K_{ij}\right)^2+\lambda\sum_{i,j=1}^n\alpha_i\alpha_j K_{ij}
\end{align*}

となります（今は実数を扱っているので$K_{ji}=K_{ij}$）。よって、$K:=(k(x_i,x_j))_{1\le i, j\le n}$とおくと、上式を最小にする$\hat{\alpha}\in\mathbb{R}^n$は

\hat{\alpha}=(K+\lambda I)^{-1}\boldsymbol{y}

となります。以上より、推定量として

\begin{align*}
\hat{f}(x)&=\langle\hat{\beta},\phi(x)\rangle=\left\langle\sum_{i=1}^n\hat{\alpha_i} \phi(x_i),\phi(x)\right\rangle\\
&=\sum_{i=1}^n\hat{\alpha_i}k(x_i,x)
\end{align*}

が得られました。推定量を求めるには$\hat{\alpha}$と$k(x,x')$を計算すればよいわけですね。

カーネル関数から生成されるヒルベルト空間

計算は省略しますが、さきほど出てきた$n$次正方行列 $K=(k(x_i,x_j))_{1\le i, j\le n}$が対称非負定値行列であることが分かります。このように、任意の$x_1,\ldots,x_n\in\mathcal{X}$に対して$K$が$n$次の対称非負定値行列となるとき、$k(x,x')$をカーネル関数と呼びます。

前節で求めた推定量$\hat{f}$にはカーネル関数を1変数化した関数の線形和でできています。そこで、次のような関数空間を考えます:

\mathcal{H}_0:=\left\{f(x)=\sum_{i=1}^n\alpha_i k(z_i,x)\mid \alpha_i\in\mathbb{R}, z_i\in\mathcal{X},n\in\mathbb{N}\right\}

この関数空間には内積を定義することができ、それを完備化することでヒルベルト空間が得られます（詳細は次回書く予定）。このように、カーネル関数から生成されるヒルベルト空間は再生核ヒルベルト空間と呼ばれるヒルベルト空間の構成法の一例になっています。

定義（再生核ヒルベルト空間）
$\mathcal{H}$を$\mathcal{X}$上の関数からなるヒルベルト空間とする。$\mathcal{H}$が再生核ヒルベルト空間であるとは、関数$k:\mathcal{X}^2\to\mathbb{R}$が存在して、任意の$x\in\mathcal{X}$、$f\in\mathcal{H}$に対して

k(x,\cdot)\in\mathcal{H},\quad\langle f,k(x,\cdot)\rangle=f(x)

が成り立つことをいう。

まとめ

テキストの中盤以降はまだ流し読みしかしていないのですが、とりあえず機械学習での関数解析の使われ方の一部だけでも分かったので、読むモチベーションが出てきました。表現定理とかもあるようなので面白そうです。これから精密に読んで、コードも書けたらと思います。