パターン認識と機械学習下（第6章：その1）

以下の本を読みます。上巻を読むこともあります。何か問題点がありましたらご指摘いただけますと幸いです。

パターン認識と機械学習下 (ベイズ理論による統計的予測)

作者: C.M.ビショップ,元田浩,栗田多喜夫,樋口知之,松本裕治,村田昇
出版社/メーカー: 丸善出版
発売日: 2012/02/29
メディア: 単行本
購入: 6人クリック: 14回
この商品を含むブログを見る

次回：まだ

f:id:cookie-box:20180305232608p:plain:w60

上巻読んでないですよね？

f:id:cookie-box:20180305231302p:plain:w60

プロデューサーが面倒だから上巻はとばしてもいいんじゃないかって。

何がいいんですか！？

だから下巻の最初の「第6章カーネル法」から読み始めてみたんだけど、最初の段落は「ふつう回帰／分類モデルを学習するときにはパラメータ $w$ を学習して、学習しちゃったら訓練データ自体はもう使わないよね」って話で、それはそうだよねって感じなんだけど、次の段落では「でも予測時にも訓練データを使う手法も中にはあったよね」って言ってるんだ。上巻でそういう手法をいくつか扱ったみたいなんだけど、特に 2.5.1 節では「カーネル関数」について触れたみたいだから、上巻に戻って読んでおいた方がいい気がするんだ。だってこの章のタイトル「カーネル法」だし…。

上巻に戻るの早くないですか！？

だからここから上巻の「2.5.1節カーネル密度推定法」にとぶけど、ここではデータは ${\mathbb R}^D$ の要素みたいだな。観測データから真の密度 $p(x)$ を推定したいって状況で…なぜかわかんないけど ${\mathbb R}^D$ のある部分領域 $\mathcal{R}$ に注目すると、データが $\mathcal{R}$ 内に入る確率は $P=\int_{\mathcal{R}}p(x)dx$ のはずで、この $P$ をつかうと「 $N$ 個のサンプルを得たときに $\mathcal{R}$ 内に入っているサンプルの割合」の期待値と分散が出るのか。…なんで $P$ と $P(1-P)/N$ になるんだっけ？

いやそこに思いっきり二項分布書いてありますし、この本の読者はそこで引っかからない想定だと思うんですが…本題から逸れますけど復習しておきますか。いまの状況で $N$ 個のサンプルのうち $K$ 個が $\mathcal{R}$ 内に入る確率は、表が出る確率が $P$ のコインを $N$ 回投げるという試行をしたときに内 $K$ 回が表になる確率に等しいですよね。この試行で例えば最初の $K$ 回のみが表になる確率は $P^K (1-P)^{N-K}$ ですが、 $N$ 回のうち $K$ 回が表になるパターンは他にもあります。つまり、全部で $_{N}{\rm C}_{K}$ パターンありますから、 $K$ 回表になる確率は結局 $_{N}{\rm C}_{K} P^K (1-P)^{N-K}$ ですね。であれば、表が出る回数の期待値と分散は計算するだけです。

　　 $\displaystyle E[K] = \sum_{K = 0}^N K \, _{N}{\rm C}_{K} P^K (1-P)^{N-K} = \sum_{K = 1}^N \frac{K \cdot N!}{K! (N-K)!} P^K (1-P)^{N-K}$
　　 $\displaystyle \qquad \, \, = NP \sum_{K = 1}^N \frac{(N - 1)!}{(K - 1)! (N-K)!} P^{K-1} (1-P)^{N-K} = NP$
　　 $\displaystyle V[K] = E[K^2] - E[K]^2 = \sum_{K = 0}^N K^2 \, _{N}{\rm C}_{K} P^K (1-P)^{N-K} - N^2 P^2$
　　 $\displaystyle \qquad \, \, = \sum_{K = 1}^N \frac{K(K-1) \cdot N!}{K! (N-K)!} P^K (1-P)^{N-K} + \sum_{K = 1}^N \frac{K \cdot N!}{K! (N-K)!} P^K (1-P)^{N-K} - N^2 P^2$
　　 $\displaystyle \qquad \, \, = N(N - 1)P^2 \sum_{K = 2}^N \frac{(N - 2)!}{(K - 2)! (N-K)!} P^{K-2} (1-P)^{N-K} + NP - N^2 P^2 = NP(1-P)$

したがって、 $E[K/N]=E[K]/N=P$ および $V[K/N]=E[K]/N^2=P(1-P)/N$ になるでしょう。

ありがとジュン。1個1個のサンプルが $\mathcal{R}$ の中にあるかどうかがコインの表か裏かって感じなのか。続く (2.244) 式は「すごくたくさんの $N$ 個のサンプルを得たら $\mathcal{R}$ の中に入ってるサンプル数 $K$ のばらつきは小さくなってもうぴったり $NP$ も同然だろ」ってことだよな、たぶん。で、(2.245) 式は「領域 $\mathcal{R}$ が小さかったらこの領域内で確率密度は一様だろ」ってことか。(2.246) 式はそれらを合わせて「じゃあもう領域 $\mathcal{R}$ 内の確率密度はサンプルがこの中に入った割合 $K/N$ を体積 $V$ で割った値 $\displaystyle \frac{K}{NV}$ でいいだろ」って感じかな。

1次元でイメージするとヒストグラム状の経験分布のようなものでしょうね。

それで、 $K$ を固定し $V$ を推定するのが $K$ 近傍法…？ $K$ 近傍法って前にプロデューサーがやってたよな。確か、未知データをクラス分類するときに、その未知データに近い既知データを $K$ 個取ってきて、その $K$ 個の中に多く含まれるクラスに分類するやつだっけ。

まあそんな感じですね。なるほど、 $K$ 近傍法をつかうのであれば訓練データを捨ててはいけませんね。しかし、 $K$ 近傍法はクラス分類の手法であって密度推定の手法では…ああ、122～123ページを読むと密度推定手法としての $K$ 近傍法が紹介されていますね。 $K=5$ なら $5$ と決めて、その場所場所でサンプルを $5$ 個含む領域の大きさを測って、その大きさほどの広がりをもつ滑らかな関数を重ね合わせて推定密度とするということですか。この節では観測データから真の密度を推定するのに、空間全体の密度の形を考えようというのではなく、空間を少しずつ切り分けて、その場所場所の密度はどうなっているんだろうというアプローチを取るんですね。だから部分領域 $\mathcal{R}$ などというものを持ち出したんですね。

まだ120～121ページ読んでないのに勝手に先進むなよ！ …120ページに戻ると、 $V$ の方を固定するのがカーネル密度推定法なのか。(2.247) 式の $k(u)$ は、 $u$ を中心とする超立方体内では 1、その外では 0 を取る関数だな。これがカーネル関数の一例なんだ。ただの超立方体じゃん…。で、(2.248) 式と (2.249) 式は何やってんのこれ？

(2.246) 式の主張は「ある点 $x$ における密度は $x$ を含む小さな領域 $\mathcal{R}$ 内に含まれるサンプルの割合を、その領域の体積で割った値に等しい」でしょう。これを具体的に各サンプルの座標の式で書き表したのが (2.249) 式というだけですよ。小さな領域に具体的な形は必要ですから、ここでは $x$ を中心とする一辺の長さが $h$ の超立方体に決めてしまって、するとその中に含まれるサンプルの個数は「各サンプルの周りに超立方体の領域を張り巡らせたときに位置 $x$ に何重にその領域が重なるか」と定式化できるので、結局 (2.249) 式が成り立つわけですね。

ふーん…あれ、てことは、もうこれで密度推定終わったんだ。なんかすぐ終わったな。ん？でも、「この場合、立方体の淵で、人為的な不連続が生じてしまう（上巻121ページ）」？…そりゃそうだよな。ガッタガタだよこれ…だから、ふつうは超立方体じゃなくガウス関数をつかうのか。…なあジュン、(2.250) 式って結局「 $N$ 個の観測データからの推定密度 $p(x)$ を、各サンプルの周りに張り巡らせたガウス分布を $1/N$ ずつの比率で混合したものとする」ってことだよな。そういわれたらあーなんかそういう分布を考えるのってアリそうだなって何となくわかるしこの式からでよかったんじゃない？

それを $x$ における推定密度とすることをどうやって正当化するんです？どのような条件下でそのような近似ができるか明らかですか？何となくじゃダメでしょう？

はい。

(2.250) 式以降は、 $h$ の大きさのバランスを取ることが肝要なことや、カーネル関数 $k(u)$ にはもっと別の関数を選んでもよいことなどが書かれていますね。

それで話は最近傍法に移って… $K$ 近傍密度推定法だと空間全体上の積分が発散するってなんで？ $V$ の方を固定してたのを $K$ の方を固定するように変えただけでなんでそんなことになっちゃったの？

僕も厳密には追えてませんが、空間内の各点について $K$ 番目に近いサンプルまでの距離を $h$ として (2.246) 式を適用すると空間全体上での積分が発散するんでしょうね。本節における密度推定法は「領域 $\mathcal{R}$ はその内部で密度一定とみなせるほどじゅうぶん小さい」という仮定から出発していますが、体積 $V$ の方を可変にしてしまうともはや領域を小さいままに保てません。そこが正規化できなくなった敗因なのでは。

あー確かに。既知データたちからめっちゃ遠い地点から既知データを $K$ 個囲むように領域 $\mathcal{R}$ を取ろうと思ったらめっちゃでかくなるよな、たぶん。

123ページは、クラス分類としての $K$ 近傍法の話に触れられていますね。未知データがクラス $c$ に帰属する事後確率が $K_c / K$ になることが示されています（ $K_c$ は未知データに近い既知データを $K$ 個取ってきたときにその中に含まれているクラス $c$ のデータの個数）。「未知データの近所に多いクラスに分類する」というのが結局どのような分類をすることを意味するのかこれでわかりましたね。…これくらいで下巻の1ページに戻りましょうか。

そうだ、元々下巻読んでたんだったよな。1ページの第2段落に戻ると、2.5.1節でみてきたようなカーネル密度推定法や最近傍法では、入力空間中の任意の2点の類似度を測れなければならないっていってるな。そりゃ空間内の各点に既知データからの距離に応じた密度が割り当てられるしな。それに、「予測には時間がかかる（1ページ）」…ってのは、カーネル密度推定法だったら全ての既知データとの間の距離を測って密度を足し上げなきゃいけないからしんどいってことだよなたぶん。で次の段落は…双対表現って何？？

いや、それをこの後 6.1 節で扱うので…ただ少し調べると双対表現（dual representation）という用語は数学や心理学にもあるようですが、ここでの双対表現とはカーネル法用語というか、PRML用語といった感じがしますね…そもそも英語では「対となる表現」というごく一般的な意味の言葉でしょうし。

ふーん？まあ今は気にしなくていいってことか。この第3段落によると、「目的の回帰／分類を達成するようなパラメータ $w$ を学習する」って問題を対となる別の問題に書き換えることができて、そっち側で解いたときは予測時にカーネル関数をつかうことになるってことかな？でそっち側で解くときは何か $x$ を特徴空間へ飛ばす写像 $\phi(\cdot)$ を決めておいて、カーネル関数は $k(x,x')=\phi(x)^{\top}\phi(x')$ という式になるってことか。え、カーネル関数ってガウス関数とかだったよな？こんな内積みたいな感じじゃなかったと思うんだけど。

ちょうど章末の演習問題の 6.11 が、ガウスカーネルが無限次元の特徴ベクトルの内積であることを示せ、となっていますよ。ちょっとやってみましょうか。(6.23)～(6.25) 式よりはじめて、

　　 $k(x, x') = \exp(-|| x - x' ||^2 / 2\sigma^2)=\exp(- x^{\top}x / 2\sigma^2 - x'^{\top}x' / 2\sigma^2 + x^{\top}x' / \sigma^2)$
　　 $\qquad \quad \, \, = \exp(- x^{\top}x / 2\sigma^2) \exp(- x'^{\top}x' / 2\sigma^2) \exp(x^{\top}x' / \sigma^2)$
　　 $\qquad \quad \, \, \displaystyle = \exp(- x^{\top}x / 2\sigma^2) \exp(- x'^{\top}x' / 2\sigma^2)\left( 1 + \frac{x^{\top}x'}{ \sigma^2} + \frac{(x^{\top}x')^2}{ 2\sigma^4} + \cdots \right)$

これを眺めると、例えば $x$ が2次元の場合、 $\phi(\cdot)$ を以下のような無限次元への非線形変換とすればよいのではないでしょうか。これでガウス関数が $k(x,x')=\phi(x)^{\top}\phi(x')$ という内積みたいな感じになりますよね。

　　 $\displaystyle \phi(x) = \exp(- x^{\top}x / 2\sigma^2) \left( \begin{array}{c} 1 \\ x_1 / \sigma \\ x_2 / \sigma \\ x_1^2 / \sqrt{2} \sigma^2 \\ x_2^2 / \sqrt{2} \sigma^2 \\ x_1 x_2 / \sigma^2 \\ \vdots \end{array} \right)$

うおおいだから勝手に先進むなよ！あと無限次元て！そんなホイホイ次元を無限にしていいのかよ！？

まだ予測時にカーネル関数をつかうような解き方の中で特徴ベクトル $\phi(x)$ がどのような制約を受けるのかわかりませんね。

序文に戻るぞ。といっても、序文の続きにはカーネル関数の例はこうですとか、カーネル関数を導入するとカーネルトリックというまだよくわからないテクニックが使えるようになりますってあるだけで、カーネル関数によって何がよくなるのかとかはよくわかんないな。

第2段落で「訓練データを記憶しておくような（＝ノンパラメトリックな、ですね）方法は訓練データ間の距離の定義も要るし時間もかかる」といっていたので、カーネル関数がそれを解決してくれるのではないかと思うんですがね。よくわからないので 6.1 節に進みましょうか。

ここでは (6.2) 式を最小化したいっていうシチュエーションなのか。線形回帰モデルの重みを求めるときの目的関数は確かにこんな感じだよな。じゃあ $t_n$ は被説明変数か。

そして右辺第2項は、重みベクトルが密になりすぎないようにするための正則化項でしょうね。

上巻ぶっとばしてるから色々察する必要があるな…それで、(6.3) 式は $\displaystyle \frac{\partial J}{\partial w}=0$ を式変形してるんだよな。え、行列 $\Phi$ って？どっから出てきたの？あと計画行列って何？

$N=3$ で特徴空間が2次元の場合だとこうですよ。ちゃんと行列ですよね。計画行列は上巻の第3章139ページで出てきた言葉のようですが、見たまま各行が各データの特徴量ベクトルになっているような行列のことのようですね。なので、行数はデータサイズ、列数は特徴空間の次元数になりますね。

$\displaystyle \sum_{n=1}^3 a_n \phi(x_n) = \begin{pmatrix} a_1 \phi(x_1)_1 + a_2 \phi(x_2)_1 + a_3 \phi(x_3)_1 \\ a_1 \phi(x_1)_2 + a_2 \phi(x_2)_2 + a_3 \phi(x_3)_2 \end{pmatrix} = \begin{pmatrix} \phi(x_1)_1 & \phi(x_2)_1 & \phi(x_3)_1 \\ \phi(x_1)_2 & \phi(x_2)_2 & \phi(x_3)_2 \end{pmatrix} \begin{pmatrix} a_1 \\ a_2 \\ a_3 \end{pmatrix}$

$\displaystyle \qquad \qquad \quad \, \, = \begin{pmatrix} \phi(x_1)_1 & \phi(x_1)_2 \\ \phi(x_2)_1 & \phi(x_2)_2 \\ \phi(x_3)_1 & \phi(x_3)_2 \end{pmatrix} ^{\top} \begin{pmatrix} a_1 \\ a_2 \\ a_3 \end{pmatrix} = \Phi ^{\top} a$

結局また上巻読みにいったのか。

上巻 3.1.1 節の最小2乗法はいま下巻 6.1 節でみている最適化問題の正則化項がないバージョンなんですね。しかし、こちらの下巻では正則化項があるから同じ形にはなりません。というか、(6.3) 式で $w$ から $a$ に主役を交代させてしまっていますね。こうして $w$ の最適化問題を $a$ の最適化問題にすりかえるのが双対表現ですか。

$a$ と $w$ の関係は (6.4) 式だから、変数変換みたいなもんなんだな。でもさジュン、変数変換ってそうすることで簡単になるときとかにするんじゃないの？ (6.5) 式とかかえって見た目おぞましくなってない？

見た目で判断するのはよくないのでは…ほら、この目的関数は (6.7) 式のように各要素がデータの各組合せのカーネル関数になっているような行列＝グラム行列でかくことができますよ。(6.6) 式は丁寧にかくと以下ですね。各要素が $m$ 番目のデータが $n$ 番目のデータの位置につくる密度になっています。

$\displaystyle K = \Phi \Phi ^{\top} = \begin{pmatrix} \phi(x_1)_1 & \phi(x_1)_2 \\ \phi(x_2)_1 & \phi(x_2)_2 \\ \phi(x_3)_1 & \phi(x_3)_2 \end{pmatrix} \begin{pmatrix} \phi(x_1)_1 & \phi(x_2)_1 & \phi(x_3)_1 \\ \phi(x_1)_2 & \phi(x_2)_2 & \phi(x_3)_2 \end{pmatrix}$

$\displaystyle \qquad \qquad \, \, \, = \begin{pmatrix} \phi(x_1)^{\top} \phi(x_1) & \phi(x_1)^{\top} \phi(x_2) & \phi(x_1)^{\top} \phi(x_3) \\ \phi(x_2)^{\top} \phi(x_1) & \phi(x_2)^{\top} \phi(x_2) & \phi(x_2)^{\top} \phi(x_3) \\ \phi(x_3)^{\top} \phi(x_1) & \phi(x_3)^{\top} \phi(x_2) & \phi(x_3)^{\top} \phi(x_3) \end{pmatrix}$

あっカーネル関数…って別に、カーネル関数だったら何がうれしいのかわからないし…。とりあえず先に行くか。(6.8) 式って、(6.3) 式を (6.4) 式に代入するとほんとにこうなる？

こうですね。 $K^{\top}=K$ であることに注意してください。この後は自分でやってください。

$\displaystyle a = - \frac{1}{\lambda} \begin{pmatrix} w^{\top} \phi(x_1) - t_1 \\ w^{\top} \phi(x_2) - t_2 \\ w^{\top} \phi(x_3) - t_3 \end{pmatrix} = - \frac{1}{\lambda} \begin{pmatrix} a^{\top} \Phi \phi(x_1) \\ a^{\top} \Phi \phi(x_2) \\ a^{\top} \Phi \phi(x_3) \end{pmatrix} + \frac{t}{\lambda}= - \frac{1}{\lambda} (a^{\top} \Phi \Phi^{\top})^{\top} + \frac{t}{\lambda}= - \frac{1}{\lambda} K a + \frac{t}{\lambda}$

あーほんとだ…でもやっぱりこの答えってさ、上巻 3.1.4 節の正則化最小二乗法の (3.28) 式とそっくりじゃない？ $w$ じゃなくて $a$ を主役にした意味とかあったの？双対表現とかいう名前まで付けてさ。

$w$ と $a$ の見た目がそうまるで違うというわけではないですね。ただある位置における予測を $a$ の方をつかってかくと「各訓練データ点を相手としたカーネル関数」のみの式（ $\phi(x)$ は出てこない）でかける点が違うんじゃないでしょうか。この式 (6.9) に関連してメモしておくと $a^{\top} \Phi \phi(x) = \phi(x)^{\top} \Phi ^{\top} a$ なので $k(x) = \Phi \phi(x)$ であってこれはデータサイズの次元をもつ縦ベクトルですね。各要素は各データが位置 $x$ につくる密度ですね。この $k(x)$ の係数が $a$ です。 $w$ が特徴空間における最適化問題の答えだったのなら、 $a$ は「実空間の場所場所に各データ点が張る密度」の世界における最適化問題の答えだったんですね。

ふーん、そういわれると係数の意味がちょっとわかりやすくなるのかな…あれでも、4ページに、双対表現にすると求める逆行列のサイズが大きくなってしまうってかいてある？

上の方で書き下した例でも、 $w$ は2次元で $a$ は3次元でしたよね。それに現実では訓練データ点が3点などということはなく、いくらでも大きくなりますからね。特徴空間の次元数はたかがしれているかもしれませんが。そしていまハヤトがいったように、わかりにくい特徴空間を明示的に扱うことを避けることができ、無限次元の特徴すら取り扱うことができるとありますね。

特徴を無限次元とれるっていわれると確かにすごそうだけど…特徴の次元って多ければ多いほどいいってもん？それに、無限次元っていっても特徴量どうしの内積が入力空間でまともな密度になるような特徴量を取らないとダメだよな…？そんなすごい自由って感じでもないような…。なんかいまいちカーネル法のよさが見えてこないな…この先を読むとわかるのかな…？

（次回があれば）つづく