T-42 対数線形モデル高速学習のための基底関数高畠一哉赤穂昭太郎産業技術総合研究所ヒューマンライフテクノロジー 2014/11/18 1 / 18 対数線形モデル elθx pθ (x) = , Z lθx = ∑ y θy ϕyx , Z= ∑ elθx x x ∈ X: 確率変数の具現値．本論文では x = (x0 , ..., xn−1 ), xi ∈ Xi , |Xi | < ∞ とする． y ∈ Y : 基底番号．|Y | < ∞． θ = {θy }: パラメータ． ϕy : X → R．基底関数．まずは基底 {ϕy } を定めないことには話が始まらない．計算が速くできる基底などというのはいかがでしょうか? 2 / 18 スコア最小化によるデータからの学習データの経験分布 pD に対し score(θ) = − ⟨ln pθ ⟩pD + r(θ) |{z} | {z } 対数尤度正則化項を反復法で最小化する．とりあえず負の対数尤度の勾配ベクトルを求めよう (以下 ∂y = ∂/∂θy と略記)． −∂y ⟨ln pθ ⟩pD = ⟨ϕy ⟩pθ − ⟨ϕy ⟩pD = Eθy − EDy ∏ Eθy の計算量が支配的で |X| = i |Xi | 回の積和演算が必要．1 基底にこれだけかかるので全基底のためには |X||Y | 回の積和演算が必要．コレが反復法の 1 ステップ毎にかかるので．．．(*_*) 3 / 18 値域 X は大きい |X| はちょっとした問題でもすぐに大きくなる．例 1 x が 20 次元 2 値ベクトルの場合 |X| = 220 ．例 2 x = (x0 , x1 ) がアナログ量を各々10 ビットで量子化したものの場合 |X| = 220 ．計算量の都合上 |Y | ≪ |X| とせざるを得ない．広大な関数空間にごく低次元の部分空間しか張れない． (;_;) 4 / 18 アイデア I: 勾配ベクトル高速計算 2 次元離散フーリエ変換はなぜ速い? ∑ Fy0 y1 = fx0 x1 αy0 x0 β y1 x1 x0 x1 α : 1 の原始 |X0 | 乗根, β : 1 の原始 |X1 | 乗根このまま計算すると積和回数 (|X0 ||X1 |)2 ( ) ∑ ∑ Fy0 y1 = fx0 x1 αy0 x0 β y1 x1 x1 x0 このようにして 1 次元ごとにフーリエ変換すると積和回数 |X0 ||X1 |(|X0 | + |X1 |)．この原理を用いて勾配ベクトルを高速計算しよう． 5 / 18 y もベクトル (y0 , ..., yn−1 )(yi ∈ Yi ) で表す． ϕiy : Xi → R をローカル基底と呼ぶ． ϕy = ∏ ϕiyi i とローカル基底の積を基底にすると ∑ Eθy = pθ (x)ϕyx x = ∑ xn−1 ( ( ... ∑ ) ) pθ (x)ϕ0y0 x0 ... ϕn−1 yn−1 xn−1 x0 内側のカッコから順に計算していく． 6 / 18 G0x = pθ (x) G1y0 x1 ...xn−1 = ∑ G0x ϕ0y0 x0 x0 .. . Gny = ∑ n−1 Gn−1 y0 ...yn−2 xn−1 ϕyn−1 xn−1 xn−1 として最終的に ⟨ϕy ⟩pθ = Gny が求まる． Gi → Gi+1 にかかる積和回数 |Y0 |...|Yi ||Xi |...|Xn−1 | 簡単のため |Xi | = a, |Yi | = b としてみると． 7 / 18 pθ → ⟨ϕyx ⟩pθ にかかる積和回数 { n−1 ∑ nan+1 = na|X| i+1 n−i b a = ab(an −bn ) ab(|X|−|Y |) = a−b a−b i=0 a=b a ̸= b G0 = pθ を求めるにはまず指数部 lθ を求める． ∑ lθx = θy ϕ0y0 x0 ...ϕn−1 yn−1 xn−1 y = ∑ yn−1 ( ( ... ∑ ) ) θy ϕ0y0 x0 ... ϕn−1 yn−1 xn−1 y0 θ → lθ にかかる積和回数 pθ → ⟨ϕyx ⟩pθ と同じ lθ → pθ にかかる積和回数 (cexp + 2)|X| (cexp :指数計算 1 回にかかる積和回数) 8 / 18 ローカル変換の高速化 |Yi | を大きくとりたい場合 (例えば例 2) はさらに高速化が可能． Gi から Gi+1 を求める漸化式において yi , xi 以外の全ての変数を固定し (i) g... = (Gi...xi ... ) (|Xi | × 1 ベクトル) (i+1) g... = (Gi+1 ...yi ... ) (|Yi | × 1 ベクトル) (i) i Φ = (ϕyi xi ) (|Yi | × |Xi | 行列) と定義すると (i+1) (i) g... = Φ(i) g... これをローカル変換と呼ぶことにする． 9 / 18 ローカル変換には通常 |Yi ||Xi | 回の積和演算が必要であるが |Xi | = |Yi | = 2ki である場合には Φ(i) をフーリエ変換行列やアダマール行列にとれば高速変換アルゴリズムにより積和演算を ki |Yi | 回に減らせる．ローカル変換を全ての y0 ...yi−1 xi+1 ...xn−1 について行うことにより Gi から Gi+1 が求まる． Gi → Gi+1 にかかる積和回数 ki |Y0 |...|Yi−1 ||Yi ||Xi+1 |...|Xn−1 | = ki 2ki n |Xi | = |Yi | = 2k のとき pθ → ⟨ϕyx ⟩pθ にかかる積和回数 kn2kn = kn|X| = |X| log2 |Y | θ → lθ にかかる積和回数も上記に同じ． |Xi | ̸= |Yi | のときは信学技報参照． 10 / 18 アイデア II: 近似無しの反復法 (準) ニュートン法の欠点 C ∞ クラスの凸関数でも収束しないことがある．微分不可能 (例えば L1 正則化) だとそのままでは使えない．何らかの改造が必要．微分不可能な点ではどうするの? そもそもテイラー近似が成り立たない． θy 以外のパラメータを固定した 1 変数関数 uy (θy ) = Eθy の導関数は ⟨ ⟩ u′y = −∂y ⟨ϕy ⟩pθ = ϕ2y p − u2y θ 11 / 18 ここで ∀x, ϕyx = ±1 となるような基底を使うと u′y = 1 − u2y この常微分方程式の一般解は uy = tanh(θy − c)． uy (θy0 ) が既知とすると c = θy0 − tanh−1 uy (θy0 )．よって負の対数尤度 vy (θy ) = − ⟨ln pθ ⟩pD について vy′ (θy ) = uy (θy ) − EDy ∫ θy 0 vy (θy ) = vy (θy ) + uy (η) − ⟨ϕyx ⟩pD dη = vy (θy0 ) [ θy0 + ln 2 cosh(η − c) − ⟨ϕyx ⟩pD η ]θy θy0 と近似なしに求まる．＼ (^-^) ／ 12 / 18 正則化項として重み付き L1 正則化項を採用することにする．スコアも θy だけの 1 変数関数と見れば ∑ scorey (θy ) = vy (θy ) + wy |θy |, wy ≥ 0 y wy v ′ = u − ED (c, −ED ) θy = 0 −wy vy′ (0) > wy |vy′ (0)| ≤ wy vy′ (0) < −wy 導関数 vy′ と階段関数 −sign(θ)wy の交点が最小点 θymin ラインサーチなしに最小点が分かる．＼ (^-^) ／ 13 / 18 反復法 1) 2) 3) 4) 5) θ = 0 とする．何らかの収束条件を満たせば停止する． y ′ = arg miny scorey (θymin ) とする． θy′ を = θy′ min に更新する． 2 に戻る．常に最小値に収束する訳ではない．例えば f (θ) = |θ0 − θ1 | + ϵ(θ02 + θ12 ) の (1, 1) は停留点． θ1 θ0 14 / 18 点 θ からどの軸方向を見ても θ 自身が最小値であるとき軸最小と呼ぶ．定理提案した反復法が凸関数 f (θ) の最小値に収束するための必要十分条件は f の全ての軸最小点がまた極小点となることである．証明の概要) 必要条件は自明．十分条件は点列 {θt } の集積点 a は軸最小となる． a は軸最小だから条件より極小，f が凸関数だからそれは最小 a に収束する部分列 {θti } をとれば凸関数の連続性により limi→∞ f (θti ) = f (a)．元の列は単調減少で部分列が収束するので limt→∞ f (θt ) = f (a)． 15 / 18 L1 正則化とフルスパンモデル score(θ) = − ⟨ln pθ ⟩pD + ∑ wy |θy |, wy ≥ 0 y L1 正則化は与えられた基底のうちどれが不要かを教えてくれるが，どんな基底が不足しているかについては何も教えてくれない．ならば任意の指数部 lθ を表しうるだけの基底 (|Y | = |X| となる) を最初に与えれば良い．この |Y | = |X| なるモデルをフルスパンモデルと呼ぶ．従来は計算量の都合で |Y | を大きく取れなかったが本手法によればフルスパンモデルも可能となる． wy ≥ 2 とすると必ず θy = 0 と抑制できる．この性質を用いて不要な基底を意図的に排除できる． 16 / 18 例 1) ϕy の従属変数が何個の xi に関わっているかを次数とよび Ord(ϕy ) と表す．ボルツマンマシンは 2 体ポテンシャルつまり Ord(ϕy ) ≤ 2 なる基底だけを用いるモデルで，その最尤推定による学習は以下の設定で実現できる． { 2 Ord(ϕy ) > 2 wy = 0 Ord(ϕy ) ≤ 2 例 2) 同様に m 体ポテンシャルマシンとでも呼ぶべきものの最尤推定による学習は { 2 Ord(ϕy ) > m wy = 0 Ord(ϕy ) ≤ m で実現できる．計算量は 2 体に比べてほとんど増えない． 17 / 18 まとめ対数線形モデルの勾配ベクトルが高速にできるような基底関数を提案した．確率変数の値域の大きさを |X|，基底の個数を |Y | とするとき計算量は O(|X| log |Y |)．任意の Gibbs 分布を表すことのできるフルスパンモデルも実現可能となる． (準) ニュートン法とは違い近似を全く用いない反復法を提案した．この手法では最小化する凸関数の微分可能性を必要としない．反復のステップ毎にスコアが単調減少する．簡単な必要十分条件により収束が保証される．フルスパンモデルを L1 正則化に用いることで基底の取りこぼしのない学習モデルが得られる．フルスパンモデルで不要な基底を意図的に排除することができる． 18 / 18