Kunst Site
Blogブログ
About Site当サイトについて
Portfolioポートフォリオ
Contact問い合わせ

線形回帰モデルのDualとカーネル関数について


データサイエンス教師あり学習
更新日:2022-02-22

はじめに

最近、線形回帰モデルについて勉強したので忘れないうちにまとめてみました。

本記事では、カーネル関数を用いて線形回帰モデルの Dual を求め、そこからカーネルの世界へ拡張しました。

線形回帰モデル

線形回帰モデルは基底関数による特徴ベクトルφ(x)\varphi(x)φ(x)を用いることで複雑な関数を表現します。

f(x)=w1φ2(x)+w2φ2(x)+⋯+wmφm(x)=∑i=1mwiφi(x)f(x)=w_1\varphi_2(x)+w_2\varphi_2(x)+\dots+w_m\varphi_m(x)=\sum_{i=1}^{m}w_{i}\varphi_{i}(x)f(x)=w1​φ2​(x)+w2​φ2​(x)+⋯+wm​φm​(x)=i=1∑m​wi​φi​(x)

基底関数φ(x)\varphi(x)φ(x)と重みwwwについて行列で表すと次のように変形できます。

w=(w1w2⋮wm)          φ(x)=(φ1(x)φ2(x)⋮φm(x))\mathbf{w}=\left(\begin{array}{c} w_{1} \\ w_{2} \\ \vdots \\ w_{m}\end{array}\right)\,\,\,\,\,\,\,\,\,\, \boldsymbol \varphi(x)=\left(\begin{array}{c} \varphi_{1}(x) \\ \varphi_{2}(x) \\ \vdots \\ \varphi_{m}(x) \end{array} \right)w=​w1​w2​⋮wm​​​φ(x)=​φ1​(x)φ2​(x)⋮φm​(x)​​ f(x)=wTφ(x)f(x)=\mathbf{w}^T \boldsymbol \varphi(x)f(x)=wTφ(x)

この式では、xxxをmmm次元の特徴ベクトルに変換していると考えることができます。(線形問題)

例えば、基底関数をφi(x)=xi\varphi_i(x) = x^iφi​(x)=xiとすると多項式の形になります。

問題設定

学習データセットD=(x1,y1),…,(xn,yn)D=(x_1,y_1),\dots,(x_n,y_n)D=(x1​,y1​),…,(xn​,yn​)が与えられるとき、線形回帰モデルでは次のように表現できます。

y=(y1y2⋮ym)\mathbf{y}=\left(\begin{array}{c} y_{1} \\ y_{2} \\ \vdots \\ y_{m}\end{array}\right)y=​y1​y2​⋮ym​​​ Φ=(φT(x1)φT(x2)⋮φT(xm))=(φ1T(x1)⋯φMT(x1)⋮⋱⋮φ1T(xn)⋯φMT(xn))\Phi=\left(\begin{array}{c} \boldsymbol \varphi^T(x_1) \\ \boldsymbol \varphi^T(x_2) \\ \vdots \\ \boldsymbol \varphi^T(x_m)\end{array}\right)=\left( \begin{array}{ccc} \varphi^T_1(x_1) & \cdots & \varphi^T_M(x_1) \\ \vdots & \ddots & \vdots \\ \varphi^T_1(x_n) & \cdots & \varphi^T_M(x_n)\end{array}\right)Φ=​φT(x1​)φT(x2​)⋮φT(xm​)​​=​φ1T​(x1​)⋮φ1T​(xn​)​⋯⋱⋯​φMT​(x1​)⋮φMT​(xn​)​​

y≈Φw\mathbf{y}\approx\Phi\mathbf{w}y≈Φwとなるようなw\mathbf{w}wを求めたいのが線形回帰モデルです。

線形回帰モデルを解く

w\mathbf{w}wを求めるためには、下記の目的関数が最小になるようにします。

E=12∑i=1n(wTφ(xi)−yi)2+λ2∣∣w∣∣2E = \frac{1}{2}\sum_{i=1}^n(\mathbf{w}^T\boldsymbol \varphi(x_i)-y_i)^2+\frac{\lambda}{2}||\mathbf{w}||^2E=21​i=1∑n​(wTφ(xi​)−yi​)2+2λ​∣∣w∣∣2

この目的関数には正則化項を付けています。これにより、過学習を防ぐことができます。

w\mathbf{w}wで目的関数を偏微分していきます。

∂E(w)∂w=ΦT(Φw−y)+λw=0\frac{\partial E(\mathbf{w})}{\partial \mathbf{w}}=\boldsymbol\Phi^T(\boldsymbol\Phi\mathbf{w}-\mathbf{y})+\lambda\mathbf{w}=0∂w∂E(w)​=ΦT(Φw−y)+λw=0 ΦTΦw+λw=ΦTy\boldsymbol \Phi^T\boldsymbol\Phi \mathbf{w}+\lambda \mathbf{w} = \boldsymbol \Phi^T \mathbf{y}ΦTΦw+λw=ΦTy (ΦTΦ+λI)w=ΦTy(\boldsymbol \Phi^T \boldsymbol \Phi+ \lambda I)\mathbf{w}= \boldsymbol\Phi^T\mathbf{y}(ΦTΦ+λI)w=ΦTy

よって

w=(ΦTΦ+λI)−1ΦTy\mathbf{w}=(\boldsymbol \Phi^T \boldsymbol \Phi+ \lambda I)^{-1}\boldsymbol\Phi^T\mathbf{y}w=(ΦTΦ+λI)−1ΦTy

w=(ΦTΦ+λI)−1ΦTy\mathbf{w}=(\boldsymbol \Phi^T \boldsymbol \Phi+ \lambda I)^{-1}\boldsymbol\Phi^T\mathbf{y}w=(ΦTΦ+λI)−1ΦTyの双対を導く

いま、A=(ΦTΦ+λI)ΦTA=(\boldsymbol \Phi^T \boldsymbol \Phi+ \lambda I)\boldsymbol \Phi^TA=(ΦTΦ+λI)ΦTとするとき次のように変形できます。

A=(ΦTΦ+λI)ΦT=(ΦTΦΦT+λΦT)=ΦT(ΦΦT+λI)A=(\boldsymbol \Phi^T\boldsymbol \Phi +\lambda I)\boldsymbol \Phi^T=(\boldsymbol \Phi^T \boldsymbol \Phi \boldsymbol \Phi^T + \lambda \boldsymbol \Phi^T )=\boldsymbol \Phi^T(\boldsymbol \Phi \boldsymbol \Phi^T + \lambda I)A=(ΦTΦ+λI)ΦT=(ΦTΦΦT+λΦT)=ΦT(ΦΦT+λI)

ΦT\boldsymbol \Phi^TΦTを右からかけて、左からくくり出しています。

AAAに左から(ΦTΦ+λI)−1(\boldsymbol \Phi^T\boldsymbol \Phi +\lambda I)^{-1}(ΦTΦ+λI)−1、右から(ΦΦT+λI)−1(\boldsymbol \Phi \boldsymbol \Phi^T + \lambda I)^{-1} (ΦΦT+λI)−1をかけます。

(ΦTΦ+λI)−1A(ΦΦT+λI)−1=ΦT( PhiΦT+λI)−1=(ΦTΦ+λI)−1ΦT(\boldsymbol \Phi^T\boldsymbol \Phi +\lambda I)^{-1}A(\boldsymbol \Phi \boldsymbol \Phi^T+ \lambda I)^{-1} =\boldsymbol \Phi^T(\boldsymbol \ Phi \boldsymbol \Phi^T + \lambda I)^{-1} =(\boldsymbol \Phi^T\boldsymbol \Phi +\lambda I)^{-1}\boldsymbol \Phi^T(ΦTΦ+λI)−1A(ΦΦT+λI)−1=ΦT( PhiΦT+λI)−1=(ΦTΦ+λI)−1ΦT

したがって、ΦT(ΦΦT+λI)−1=(ΦTΦ+λI)−1ΦT\boldsymbol \Phi^T(\boldsymbol \Phi \boldsymbol \Phi^T + \lambda I)^{-1}=(\boldsymbol \Phi^T\boldsymbol \Phi +\lambda I)^{-1}\boldsymbol \Phi^TΦT(ΦΦT+λI)−1=(ΦTΦ+λI)−1ΦTなので

w=ΦT(ΦTΦ+λI)−1y\mathbf{w}=\boldsymbol \Phi^T(\boldsymbol \Phi^T\boldsymbol \Phi +\lambda I)^{-1}\mathbf{y}w=ΦT(ΦTΦ+λI)−1y

ここでΦTΦ\boldsymbol \Phi^T\boldsymbol \PhiΦTΦはグラム行列です。

グラム行列とは?

グラム行列は次のような形をしています。

K=XXT=(x1Tx1⋯x1TxN⋮⋱⋮ xNTx1⋯xNTxN)K=\mathbf{X}\mathbf{X}^T=\left( \begin{array}{ccc} \mathbf{x_1}^T\mathbf{x_1} & \cdots & \mathbf{x_1}^T\mathbf{x_N} \\ \vdots & \ddots & \vdots \\  \mathbf{x_N}^T\mathbf{x_1} & \cdots & \mathbf{x_N}^T\mathbf{x_N} \end{array} \right)K=XXT=​x1​Tx1​⋮ xN​Tx1​​⋯⋱⋯​x1​TxN​⋮xN​TxN​​​

KKKのijijij成分はiii番目のベクトルとjjj番目のベクトルの内積を表しています。

つまり、iii番目のデータとjjj番目のデータはどれくらい似ているのかを行列にしたのがグラム行列(データ同士の類似度行列)です。

ノンパラメトリック回帰

w=ΦT(ΦTΦ+λI)−1y\mathbf{w}=\boldsymbol \Phi^T(\boldsymbol \Phi^T\boldsymbol \Phi +\lambda I)^{-1}\mathbf{y}w=ΦT(ΦTΦ+λI)−1yにおいて、新規のデータx∗x^{\ast}x∗が与えられたとき、

f(x∗)=ΦT(ΦTΦ+λI)−1yφ(x∗)f(x^{\ast})=\boldsymbol \Phi^T(\boldsymbol \Phi^T\boldsymbol \Phi +\lambda I)^{-1}\mathbf{y}\boldsymbol\varphi(x^{\ast})f(x∗)=ΦT(ΦTΦ+λI)−1yφ(x∗)

(AB)T=BTAT    ,(A−1)T=(AT)−1(AB)^T=B^TA^T\,\,\,\,,(A^{-1})^{T}=(A^T)^{-1}(AB)T=BTAT,(A−1)T=(AT)−1なので

f(x∗)=yT( PhiTΦ+λI)−1ΦTφ(x∗)f(x^{\ast})=y^T(\boldsymbol \ Phi^T \boldsymbol \Phi+ \lambda I)^{-1}\boldsymbol\Phi^T \boldsymbol \varphi(x^{\ast})f(x∗)=yT( PhiTΦ+λI)−1ΦTφ(x∗)

k(x,x′)=φ(x)Tφ(x′)k(x,x^{\prime})=\boldsymbol \varphi(x)^T\boldsymbol \varphi(x^{\prime})k(x,x′)=φ(x)Tφ(x′)とするとき、 PhiT Phi\boldsymbol \ Phi^T \boldsymbol \ Phi PhiT Phi,ΦTφ(x∗)\boldsymbol\Phi^T \boldsymbol \varphi(x^{\ast})ΦTφ(x∗)はそれぞれ次のように変形できます。

K= PhiT Phi=(φ(x1)Tφ(x1′)⋯φ(x1)Tφ(xn′)⋮⋱⋮ φ(xn)Tφ(x1′)⋯φ(xn)Tφ(xn′) )=(k(x1,x1′)⋯k(x1,xn′)⋮⋱⋮ k(xn,x1′)⋯k(xn,xn′))K=\boldsymbol \ Phi^T \boldsymbol \ Phi=\left( \begin{array}{ccc} \boldsymbol \varphi(x_1)^T \boldsymbol \varphi(x_1^{\prime}) & \cdots & \boldsymbol\varphi(x_1)^T\boldsymbol \varphi(x_n^{\prime}) \\ \vdots & \ddots & \vdots\\  \boldsymbol \varphi(x_n)^T\boldsymbol \varphi(x_1^{\prime}) & \cdots & \boldsymbol \varphi(x_n)^T\boldsymbol \varphi(x_n^{\prime})  \end{array} \right)=\left( \begin{array}{ccc} k(x_1,x_1^{\prime}) & \cdots & k(x_1,x_n^{\prime}) \\ \vdots & \ddots & \vdots \\  k(x_n,x_1^{\prime}) & \cdots & k(x_n,x_n^{\prime})\end{array} \right)K= PhiT Phi=​φ(x1​)Tφ(x1′​)⋮ φ(xn​)Tφ(x1′​)​⋯⋱⋯​φ(x1​)Tφ(xn′​)⋮φ(xn​)Tφ(xn′​) ​​=​k(x1​,x1′​)⋮ k(xn​,x1′​)​⋯⋱⋯​k(x1​,xn′​)⋮k(xn​,xn′​)​​ k(x^{\ast})=\boldsymbol\Phi^T \boldsymbol \varphi(x^{\ast})=\left[ \begin{array}{c} \boldsymbol \varphi(x_1)^T\boldsymbol \varphi(x)^{\ast} \\ \vdots \\  \boldsymbol \varphi(x_n)^T\boldsymbol \varphi(x)^{\ast} \end{array} \right]=\left[ \begin{array}{c} k(x_1,x^{\ast}) \\ \vdots \\  k(x_n,x^{\ast}) \ \end{array} \ right]

よって、

f(x∗)=yT(K+λI)−1k(x∗)f(x^{\ast})=\mathbf{y}^T(K+\lambda I )^{-1}k(x^{\ast})f(x∗)=yT(K+λI)−1k(x∗)

したがって、線形回帰モデルでは次の2つの Dual な表現ができます。

f(x∗)=wTφ(x)     ,w=( PhiT Phi+λI)−1yf(x^{\ast})=\mathbf{w}^T\boldsymbol \varphi(x)\,\,\,\,\,,\mathbf{w}=(\boldsymbol \ Phi^T \boldsymbol \ Phi+ \lambda I)^{-1}\mathbf{y}f(x∗)=wTφ(x),w=( PhiT Phi+λI)−1y

入力x∗x^{\ast}x∗に対しての出力fffを特徴ベクトルを使って表した表現です。

f(x∗)=aTk(x∗)     ,a=(K+λI)−1yf(x^{\ast})=\mathbf{a}^T\mathbf{k}(x^{\ast})\,\,\,\,\,,\mathbf{a}=(K+\lambda I )^{-1}\mathbf{y}f(x∗)=aTk(x∗),a=(K+λI)−1y

類似度ベクトルを使った表現です。

こちらの方は、パラメータw\mathbf{w}wや基底関数が消えてなくなっています。(パラメトリック回帰がノンパラメトリック回帰に変わっている)

従って、基底関数は不要でありk(x,x∗)k(x,x^{\ast})k(x,x∗)がわかればいいという式になっています。

以前の式では出力yyyも必要でしたが、こちらの式では入力xxxさえわかればいいということになっています。

カーネル関数

このk(x,x∗)k(x,x^{\ast})k(x,x∗)はカーネル関数といいます。

k(x,x′)=φ(x)Tφ(x′)k(x,x^{\prime})=\boldsymbol \varphi(x)^T\boldsymbol \varphi(x^{\prime})k(x,x′)=φ(x)Tφ(x′)

これは内積の一般化とみることができます

カーネル関数には下記のような性質をもっています。

  • カーネル関数は 2 つの入力がどれくらい似ているかを表す
  • カーネル関数は半正定値対称関数である
  • 被らない任意の個数xxxがあるときカーネル関数はx×xx\times xx×xの正定値対称行列になる。ここで被ってもいいとすれば半正定値称行列になる
  • φ(x)\boldsymbol \varphi(x)φ(x)は知らなくても問題ない性質。これは、φ(x)\boldsymbol \varphi(x)φ(x)がわかればk(x,x′)k(x,x^{\prime})k(x,x′)がわかるというものでした。もしk(x,x′)k(x,x^{\prime})k(x,x′)が半正定値対称関数であれば、それに対応する基底関数は存在するので、機械学習では基底関数は使いません。したがって、もはやφ(x)\boldsymbol \varphi(x)φ(x)は知らなくてもいいですよという性質があります。これはデータ数だけで決まるので基底関数が無限個でも No problem です。

ここまでのカーネルことをまとめると

データ成分で記述されるような線形手法の問題があったときに、それを Dual な表現で表すと、内積に置き換えることができます。そして、それをカーネルに置き換えることで非線形の表現で表すことができるということです。

つまり、どんな線形手法でも Dual な表現に置き換えることで、カーネル法が適応できて非線形手法に拡張することができます。

また、このとき数値ではないデータ(文字列、グラフ、テキスト)にも内積(類似度)を定義することができるという特徴があります。

線形回帰モデルから非線形手法であるカーネルの世界という新たな世界へと繋がりました。

最後に

ここまで読んでくださってありがとうございます。

Profile

kunst

データサイエンティスト兼フロントエンジニアのkunstです!
最近は山登りにハマっています。

目次

kunst Site

Welcome to kunst Site. Stay updated with the latest posts.

Privacy PolicyAbout Blog|BlogAbout SitePortfolioContact

Copyright © 2024 kunst Site