パターン認識と機械学習 下(第6章:その1)

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

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

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

次回:まだ
f:id:cookie-box:20180305232608p:plain:w60

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

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

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

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

何がいいんですか!?

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

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

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

上巻に戻るの早くないですか!?

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

だからここから上巻の「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} 内に入っているサンプルの割合」の期待値と分散が出るのか。…なんで  PP(1-P)/N になるんだっけ?

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

いやそこに思いっきり二項分布書いてありますし、この本の読者はそこで引っかからない想定だと思うんですが…本題から逸れますけど復習しておきますか。いまの状況で  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 になるでしょう。

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

ありがとジュン。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} でいいだろ」って感じかな。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

はい。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ちょうど章末の演習問題の 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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

見た目で判断するのはよくないのでは…ほら、この目的関数は (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}

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

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

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

こうですね。 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}

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

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

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

wa の見た目がそうまるで違うというわけではないですね。ただある位置における予測を 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 は「実空間の場所場所に各データ点が張る密度」の世界における最適化問題の答えだったんですね。

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

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

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

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

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

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

(次回があれば)つづく