PRML §6 — kernel method @taki0313 10/10/22 @taki0313 ToC Introduction 6.1 双対表現 6.2 カーネル関数の構成 6.3 RBF ネットワーク 6.4 ガウス過程 @taki0313 1/50 Introduction @§3 回帰 / @§4 分類 — linear, parametric kernel function k(x, x′) = φ(x)T φ(x′) – – – – ある特徴空間上での内積, 対称 k(x, x′) = k(x′, x) 恒等カーネル k(x, x′) = xTx′ 不変カーネル k(x, x′) = k(x − x′) 均一カーネル k(x, x′) = k(||x − x′||) kernel trick – kernel を用いて特徴空間上でごにょごにょする技法 @taki0313 2/50 3/50 1 1 1 0.5 0.75 0.75 0 0.5 0.5 −0.5 0.25 0.25 −1 −1 0 1 1.0 0 −1 0 1 0 −1 2.0 6.0 1.0 3.0 0 1 0 1 0.0 −0.4 −1 0 1 0.0 −1 0 1 0.0 −1 Figure 1: kernel と k(x,x’) を x’ を×として x の関数にしたもの @taki0313 ToC Introduction 6.1 双対表現 6.2 カーネル関数の構成 6.3 RBF ネットワーク 6.4 ガウス過程 @taki0313 4/50 双対表現 — dual representation 正則化項付き線形回帰の評価式 ∑ T 1 – J(w) = 2 {w φ(xn) − tn }2 + λ2 wTw – w についての勾配=0 ∑ T ∑ 1 w = − λ {w φ(xn)}φ(xn) = an φ(xn) = ΦTa – ΦT = (φ(x1) · · · φ(xN)) パラメータの変換 w a — w = ΦTa → J(w) – J(a) = 12 aTΦΦTΦΦTa − aTΦΦTt + 12 tTt + λ2 aTΦΦTa グラム行列 — Knm ≡ φ(xn)T φ(xm) = k(xn, xm) @taki0313 5/50 双対表現 — dual representation K を用いて – K = ΦΦT – J(a) = 12 aTKKa − aTKt + 12 tTt + λ2 aTKa w = ΦTa を an の式に代入して – λan + aTΦφ(xn) = tn → (λIN + K)a = t 予測の式 – y (x) = aTΦφ(x) T – y (x) = k(x) (K + λIN)−1t — k(x) = k(xn, x) @taki0313 6/50 双対表現 — dual representation 7/50 kernel method — グラム行列 K(NxN) の逆行列を求める基底関数 — 計画行列 Φ(MxM) の逆行列を求める一般に… – N >> M – グラム行列の逆行列を求めるコストは大きいル k の上で行なえるのが嬉しいことらしい。 @taki0313 全てをカーネ ToC Introduction 6.1 双対表現 6.2 カーネル関数の構成 6.3 RBF ネットワーク 6.4 ガウス過程 @taki0313 8/50 カーネル関数の構成 9/50 カーネル関数 — 特徴空間上への写像 φ(x) カーネル k が有効か? ある空間上での内積になること – (xTz)2 √ = (x1z1 + x2z2)2√= x12z12 + 2x1z1x2z2 + x22z22 T – = (x12, 2x1x2, x22)(z12, 2z1z2, z22)T = φ (x) φ (z) カーネル k が有効か? グラム行列 K が半正定値行列カーネルの構成法 — (6.13) ∼ (6.22) @taki0313 カーネルの作り方 k(x, x′) = ck1(x, x′) k(x, x′) = f (x)k1(x, x′)f (x′) k(x, x′) = q(k1(x, x′)) k(x, x′) = exp(k1(x, x′)) k(x, x′) = k1(x, x′) + k2(x, x′) k(x, x′) = k1(x, x′)k2(x, x′) k(x, x′) = k3(φ(x), φ(x′)) k(x, x′) = xTAx k(x, x′) = ka(xa, x′a) + kb (xb, x′b) k(x, x′) = ka(xa, x′a)kb (xb, x′b) @taki0313 10/50 – c は定数、f は任意の関数 – q は非負の係数をもつ多項式 – Φ : x → RM – k3 は RM 上の kernel – A は対称, 半正定値 – x = (xa, xb) – ka, kb はそれぞれで有効な kernel 有名なカーネルガウスカーネル k(x, x′) = exp(− 12 ||x − x′||2) – ||x − x′||2 = xTx + (x′)Tx′ − 2xTx′ – カーネルトリック — → κ(x, x) + κ(x′, x′) − 2κ(x, x′) シグモイドカーネル k(x, x′) = tanh(axTx′ + b) @taki0313 11/50 確率的生成モデル → カーネル生成モデル p(x) → k(x, x′) = p(x)p(x′) 一般化 ∑ – 離散 — k(x, x ) = ∫ i p(x|i)p(x′|i)p(i) – 連続 — k(x, x′) = p(x|z)p(x′|z)p(z)dz ′ HMM → §13 – よく知らないので… ∑ ′ – k(X, X ) = Z p(X|Z)p(X′|Z)p(Z) @taki0313 12/50 生成モデル → カーネル parametric な生成モデル — p(x|θ) フィッシャーカーネル – フィッシャースコア — g(θ, x) = ∇θ ln p(x|θ) – フィッシャー情報量行列 — F = Eθ [g(θ, x)g(θ, x)T ] ∑ 1 g(θ, xn)g(θ, xn)T 近似 — F ∼ N – フィッシャーカーネル ∗ k(x, x′) = g(θ, x)T F−1g(θ, x′) ∗ k(x, x′) = g(θ, x)T g(θ, x′) @taki0313 13/50 ToC Introduction 6.1 双対表現 6.2 カーネル関数の構成 6.3 RBF ネットワーク 6.4 ガウス過程 @taki0313 14/50 RBF network — Radial Basis Function 15/50 関数補間 – 入力集合 {x1, x2, · · · , xN, }{t1, t2, · · · , tN } – 1 ≤ n ≤ N について f (xn ) = tn になる関数 f を求める ∑ – f (x) = wn h(||x − xn||) として {wn } を最小二乗法で求める。 — 過学習ノイズが入る場合の補間 – ノイズの分布 ν(ξ) — ∫確率変数 ξ ∑N 1 – 二乗誤差 E = 2 n=1 {y (xn + ξ) − tn }2ν(ξ)dξ @taki0313 RBF network — Radial Basis Function 16/50 変分法による最適化 – Nadaraya-Watson Model. ∑ ν(x − xn) – y (x) = tn h(x − xn), h(x − xn) = ∑ ν(x − xn) – 正則化 → 全ての関数が小さい値にならにように 1 1 0.8 0.8 0.6 0.6 0.4 0.4 0.2 0.2 0 −1 @taki0313 −0.5 0 0.5 1 0 −1 −0.5 0 0.5 1 6.3.1 Nadaraya-Watson Model 17/50 §3.3.3 — 新しい入力 x に対する予測を線形結合の式で行う ∑ – y (x, mN) = k(x, xn)tn — 等価カーネル – 和の制約を満たしている回帰密度推定 – 訓練集合 {xn, tn} → p(x, t) の推定 — Parzen 推定法 (§2.5.1) ∑ 1 – p(x, t) = N f (x − xn, t − tn ) — 各要素を中心に持つ ∫∞ – 条件付き期待値が良い∫ — y (x) = E[t|x] = −∞ tp(t|x)dt ∫ ∑ tf (x − xn, t − tn )dt tpdt n ∫ ∫ =∑ – E[t|x] = pdt m f (x − xm, t − tm )dt @taki0313 6.3.1 Nadaraya-Watson Model ∫ ∑ ∫ tpdt tf (x − xn, t − tn )dt n y (x) = E[t|x] = ∫ =∑ ∫ pdt m f (x − xm, t − tm )dt ∫ 簡単化 — 各要素の平均は 0 — tf (x, t)dt = 0 変数置換 → Nadaraya-Watson Model ∑ ∑ ∑ – y (x) = ∫ n g (x − xn)tn / m g (x − xm) = n k(x, xn)tn ∞ – g (x) = −∞ f (x, t)dt ∑ – k(x, xn) = g (x − xn)/ m g (x − xm) @taki0313 18/50 6.3.1 Nadaraya-Watson Model 条件付き確率分布— p(t|x) = p(t, x)/ ∫ 19/50 p(t, x)dt 例 — 1 次元、f (x, t) ∼ N (0, σ 2), z = (x, t) の場合 • sin(緑) 1.5 1 • データ点 (青) 0.5 0 • 条件付き期待値 (赤) −0.5 −1 −1.5 0 @taki0313 0.2 0.4 0.6 0.8 1 • 赤± 2 σ ToC Introduction 6.1 双対表現 6.2 カーネル関数の構成 6.3 RBF ネットワーク 6.4 ガウス過程 @taki0313 20/50 ガウス過程 21/50 確率過程 – 任意の有限な値集合 {y1, y2, · · · , yn } に対して矛盾のない同時分布を与えるもの – その同時分布がガウス分布 — ガウス過程 §6.1 回帰、双対性→カーネル — 非確率的モデル確率的識別モデル + カーネル法 — ガウス過程 @taki0313 6.4.1 線形回帰の復習線形回帰モデル y (x) = wT φ(x) パラメータの事前分布 p(w) = N (w|0, α−1I ) 入力 {x1, x2, · · · , xN} による評価 {y (x1), y (x2), · · · , y (xN)} による評価 → {yn }, y = (y1, y2, · · · , yN )T を評価する – E[y] = ΦE[w] = 0 – Cov [y] = ΦCov [wwT]ΦT = α1 ΦΦT = K – Knm = k(xn, xm) = α1 φ(xn)Tφ(xm) 線形回帰はガウス過程の特殊な場合 @taki0313 22/50 ガウス過程 23/50 同時分布の性質が平均、共分散で完全に記述される – 平均 (1 次モーメント) =0 とする = p(w|α) の平均を 0 – ガウス過程 ← カーネル関数 — E[y (xn), y (xm)] = k(xn, xm) 3 3 1.5 1.5 0 0 −1.5 −1.5 −3 −1 −0.5 0 0.5 1 −3 −1 −0.5 0 0.5 1 カーネル&ガウス過程から取り出した関数 @taki0313 カーネル関数の直接定義 24/50 ′ 図 (左) — ガウスカーネル k(x, x ) = ||x−x′||2 exp(− 2σ2 ) 図 (右) — 指数カーネル k(x, x) = exp(−θ|x − x′|) — オルンシュタイン-ウーレンベック過程 @taki0313 6.4.2 ガウス過程による回帰 25/50 ガウス分布のノイズを考える — tn = yn + εn p(tn |yn ) = N (tn |yn , β −1) データ y = (y1, · · · , yN )T と t = (t1, · · · , tN ) が与えられるその同時分布が等方的ガウス分布になるとする (ガウス過程) – p(t|y) = N (t|y, β −1IN) – p(y) = N (y|0, K) – K は xn , xm が似ていれば大きい値になる実際の予測のための分布 p(t) @taki0313 6.4.2 ガウス過程による回帰実際の予測のための分布 p(t) を考える ∫ – p(t) = p(t|y)p(y)dy ∼ N (t|0, C) – C(xn, xm) = k(xn, xm) + β −1δnm – データとノイズが独立なので共分散を加えるだけでいい回帰に使われるようなモデル k(xn, xm) = θ0 exp{− θ21 ||xn − xm||2} + θ2 + θ3xT n xm — (θ0, θ1, θ2, θ3) 毎のプロット : 図 6.5 @taki0313 26/50 図 6.5 — 事前分布からのサンプル (1.00, 4.00, 0.00, 0.00) (9.00, 4.00, 0.00, 0.00) (1.00, 64.00, 0.00, 0.00) 3 9 3 1.5 4.5 1.5 0 0 0 −1.5 −4.5 −1.5 −3 −1 −0.5 0 0.5 1 −9 −1 (1.00, 0.25, 0.00, 0.00) −0.5 0 0.5 1 −3 −1 9 4 1.5 4.5 2 0 0 0 −1.5 −4.5 −2 −0.5 0 0.5 1 −9 −1 −0.5 0 0.5 −0.5 0 0.5 1 (1.00, 4.00, 0.00, 5.00) (1.00, 4.00, 10.00, 0.00) 3 −3 −1 @taki0313 27/50 1 −4 −1 −0.5 0 0.5 1 図 6.6 — 同時分布からのサンプルガウス過程の事前分布からサンプリングされた関数 f 3 t 入力 {xn } 0 入力に対する {yn } (赤) サンプル {tn }(緑) −3 −1 @taki0313 28/50 0 x 1 – ノイズ入り 6.4.2 ガウス過程による回帰これまで — ガウス過程の視点からの同時分布のモデル化新しい入力に対する予測が必要 – – – – – 訓練集合 {x1, · · · , xN}, t = (t1, · · · , tN )T 入力 xN+1 , その予測値 tN+1 予測分布 p(tN+1|tN) 同時分布 p(tN) を書き下す tN+1 = (t1, · · · , tN , tN+1)T @taki0313 29/50 予測分布 p(tN+1) = N (tN+1|0, CN+1) — (6.61) より共分散行列の分割 ( ) CN k — CN+1 = — 正定値でなければならない T k c — c = k(xN+1, xN+1) + β −1, k の要素は k(xn, xN+1) 2 章の結果から、条件付き分布 p(tN+1|t) は 1 – m(xN+1) = kTC− N t 1 – σ 2(xN+1) = c − kTC− N k @taki0313 30/50 予測分布 31/50 事前分布&条件付き分布はガウス分布予測分布の平均・分散も xN+1 に依存 t2 訓練/テストデータが 1 つずつ 1 • 楕円 — 同時分布 p(t1, t2) m(x2 ) 0 t1 • t1 — 訓練データ (青) −1 • t1 に依存して p(t2|t1)(緑) −1 @taki0313 0 1 予測分布 32/50 ガウス過程による回帰の例 • sin 関数 (緑) • データ (右 3 つ以外, 青) 1 0.5 • ガウス過程による予測分布の平均 (赤) 0 −0.5 −1 0 @taki0313 0.2 0.4 0.6 0.8 1 • 標準分布の 2 倍ぐらい (薄い赤) 6.4.2 ガウス過程による回帰 33/50 K の固有値 λi → C の固有値 λi + β −1 – k(xn, xm) が ∀xn, xm に関して半正定値であればいい予測分布の平均 ∑ – m(xN+1) = an k(xn, xN+1) 1 – an は C− N t の n 番目の要素 – k が動径に依存するなら RBF が使える計算量 – ガウス過程 NxN の逆行列 O(N 3) — 基底による回帰 O(M 3) @taki0313 6.4.3 超パラメータの学習 34/50 予測が共分散の選び方にある程度依存する → parametric ハイパーパラメータ θ → p(t|θ) – θ の点推定, 共役勾配法ガウス分布&ガウス過程では… 1 N – ln p(t|θ) = − 12 ln |CN| − 12 tTC− t − N 2 ln(2π) −1 ∂ CN 1 1 T −1 ∂ CN −1 ∂ ln p(t|θ) = − Tr (C ) + – 勾配 — ∂θ N ∂θi 2 2 t CN ∂θ CN t i i 一般には非凸関数で、近似的に解く。以下略 @taki0313 6.4.4 関連度自動決定 35/50 関連度自由決定 (ARD) — ニューラルネットから提案された何か詳しくは §7.2.2 例 — 2 次元の入力空間 x = (x1, x2) をもつガウス過程 } { 1∑ ′ ′ 2 – カーネル k(x, x ) = θ0 exp − 2 ηi (xi − xi ) @taki0313 図 6.9 — ARD 事前分布からのサンプル 36/50 1 η1 = η2 = 1 (左) 0 η1 = 1, η2 = 0.01 (右) −1 1 1 0 0 −1 −1 η は入力に対する敏感さ 1 ARD の文脈から出力の予測にあまり寄与しない入力変数を求められる。 0 −1 1 1 0 0 −1 −1 @taki0313 図 6.10 — ARD におけるηの変化 2 10 目標変数 t 0 10 −2 10 −4 10 0 20 40 60 80 3 次元の入力 x1, x2, x3 最適化 — 共役勾配法 @taki0313 100 – – – – x1:ガウス分布、100 個 x2 は x1+ノイズ x3 はランダムなノイズ sin(2πx1)+ノイズ η1 > η2 >>>> η3 37/50 6.4.4 ARD 38/50 ARD → 指数・2 次カーネル ∑ ∑ 1 2 – k(xn, xm) = θ0 exp{− 2 ηi (xni − xmi ) } + θ2 + θ3 xni xmi 種々の応用において有用らしいカーネル @taki0313 6.4.5 ガウス過程による分類確率的な分類 → 事後確率 ∈ (0, 1) ガウス過程 → 実数値全体 → 活性化関数 → 分類問題 2 クラス分類問題 t ∈ {0, 1} – – – – 関数 a(x) 上でのガウス過程を考える y = σ(a) と変換する y ∈ {0, 1} へ落とす 1 次元の例 — 図 6.11 @taki0313 39/50 図 6.11 40/50 10 • 上図 5 0 −5 −10 −1 −0.5 0 0.5 1 – a(x) に対するガウス過程の事前分布からのサンプル 1 • 下図 0.75 – ロジスティックシグモイド関数で変換した 0.5 0.25 0 −1 @taki0313 −0.5 0 0.5 1 6.4.5 ガウス過程による分類目標変数 t の確率分布 — ベルヌーイ分布 – p(t|a) = σ(a)t (1 − σ(a))1−t 入力の訓練集合 {x1, · · · , xN} 対応する目標変数の観測値 t = (t1, t2 · · · , tN )T テスト点 xN+1 に対する tN+1 を予測 – 予測分布 p(tN+1|t) を決定する – 要素 a(x1), · · · , a(xN+1) を持つベクトル aN+1 @taki0313 41/50 6.4.5 ガウス過程による分類 42/50 ベクトル aN+1 い対するガウス過程による事前分布 – – – – – p(aN+1) = N (aN+1|0, CN+1) 正しいラベルが付いている → CN にはノイズが入ってない正定値保証のためにパラメータ ν の項を入れる C (xn, xm) = k(xn, xm) + νδnm カーネルはパラメータ θ によって決まる 2 クラス分類 — p(tN+1 = 1|tN) を予測する ∫ – p(tN+1 = 1|tN) = p(tN+1 = 1|aN+1)p(aN+1|tN)daN+1 @taki0313 6.4.5 ガウス過程による分類 p(tN+1 = 1|tN) = ∫ p(tN+1 = 1|aN+1)p(aN+1|tN)daN+1 解析的に解けない – 詳細略 – 漸近的にガウス分布に近づく – どうやってガウス分布として近似するか ∗ 10.1 変分推論法 ∗ 10.7 EP 法 ∗ 6.4.6 ラプラス近似 @taki0313 43/50 6.4.6 ラプラス近似ベイズの定理 & p(tN|aN+1, aN) = p(tN|aN) より ∫ p(aN+1|tN) = p(aN+1, aN|tN)daN ∫ 1 = p(aN+1, aN)p(tN|aN+1, aN)daN p(tN) ∫ 1 p(aN+1|aN)p(aN)p(tN|aN)daN = p(tN) ∫ = p(aN+1|aN)p(aN|tN)daN @taki0313 44/50 6.4.6 ラプラス近似 45/50 条件付き分布 — (6.66), (6.67) 1 T −1 – p(aN+1|aN) = N (aN+1|kTC− a , c − k CN k) N N 積分 → ラプラス近似 & ガウス分布の畳み込み p(aN) — 平均 0, 共分散行列 CN であるガウス過程によるデータについての項 (各々独立として…) ∏N ∏N antn tn 1−tn – p(tN|aN) = n=1 σ(an ) (1 − σ(an )) = n=1 e σ(−an ) @taki0313 6.4.6 ラプラス近似 46/50 定数項を無視してラプラス近似 – Ψ(aN) = ln p(aN) + ln p(tN|aN) ∑N N 1 1 T T = − 2 aNCNaN − 2 ln(2π) − 2 ln |CN| + tNaN − n=1 ln(1 + e an ) 1 – ∇Ψ(aN) = tN − σN − C− N aN σN の要素は σ(an ) 1 – ∇∇Ψ(aN) = −WN − C− N W は対角要素に σ(an )(1 − σ(an )) を持つ正定値行列 dσ da = σ(1 − σ)(4.88) 正定値行列の和も正定値行列 (演習 6.24) @taki0313 6.4.6 ラプラス近似 47/50 ヘッセ行列 A = −∇∇Ψ(aN) が正定値 — 事後分布 p(aN|tN ) の対数が凸関数凸関数 — 極小・極大 = 最小・最大逐次更新で最適解を目指せる — Newton-Raphson medhot (4.92) −1 – anew = C (I + W C ) {tN−σN + WnaN} N N N N – aN∗ に収束するまで — モード – このとき aN∗ = CN(tN−σN) 1 収束時のヘッセ行列 H = −∇∇Ψ(aN) = WN + C− N @taki0313 6.4.6 ラプラス近似収束時の、事後分布 p(aN|tN) のガウス分布による近似 – q(aN) = N (aN|a∗N, H−1) 2 つのガウス分布の畳み込み積分の評価 — 2 章 – E[aN+1|tN] = kT(tN − σN) −1 – var [aN+1|tN] = c − kT(WN + CN)−1k →ガウス分布の情報が得られたので… @taki0313 48/50 6.4.6 ラプラス近似共分散パラメータ θ の決定 – 尤度最大化, 最尤推定 ∫ – 尤度関数 p(tN|θ) = p(tN|aN)p(aN|θ)daN 近似 1 N – ln p(tN|θ) = Ψ(a∗N) − 12 ln |WN + C− | + N 2 ln(2π) Ψ(a∗N) = ln p(a∗N) + ln p(tN|a∗N) θ の微分が CN と aN の二種類の項が表れる (以下略?) @taki0313 49/50 6.4.7 ニューラルネットとの関係ニューラルネット – 隠れユニットの数 M を上手く調整すれば強い – M → ∞ ガウス過程っぽい. ただし独立 – ニューラルネット — 隠れユニットの共有とが面白いガウス過程 – 共分散関数に性質が左右される – 解析的に求められないところは近似 @taki0313 50/50