サマリー
機械学習における連続最適化とは、ニューラルネットワークの重みやバイアスの最適化、回帰分析のパラメータ推定、SVMのパラメータ推定等の変数が実数値をとる最適化問題を解く手法となる。連続最適化の代表的な手法には、勾配降下法、最急降下法、共役勾配法、準ニュートン法、L-BFGS法などがあり、目的関数の勾配やヘッセ行列などの情報を利用して、最適解に近づくように変数を更新していくアルゴリズムとなる。また、連続最適化では、目的関数の値だけでなく、制約条件も考慮する必要がある。制約条件を考慮した最適化問題を解くには、KKT条件を満たす方法、内点法、射影勾配法、ペナルティ法、バリア関数法などの制約つき最適化問題の手法を使う。ここでは機械学習プロフェッショナルシリーズ「機械学習のための連続最適化」をベースに機械学習における連続最適化について述べている。
イントロダクション
最適化アルゴリズムを記述し、理論的性質を調べるために、微積分や線形代数の知識を利用する。ここではこれらの基本事項について述べる。まずは行列の記法を定義する。実数を要素に持つnxn行列(n次行列)の全体をℝnxnと表す。より一般的にはℝnxmはnxm次行列の全体となる。行列A∈ℝnxmの要素を明示する時にはA=(aij)i=1,…,n,j=1,…,mのように記述し、簡単のためA=(aij)と書くこともある。
テイラーの定理
微分可能な関数f:ℝn→ℝの勾配(gradient)を以下のように定義する。
\[\nabla f(x)=\left(\frac{\partial f}{\partial x_1}(x),\dots,\frac{\partial f}{\partial x_n}(x)\right)^T\in \mathbb{R}^n\]
点xでの勾配∇f(x)は、関数f(x)の投稿戦に直行するベクトルとなる。これは次のように示すことができる。関数fの値が定数c∈ℝである点の集合をfc={x∈ℝn|f(x)=c}とする。実数パラメータt∈ℝに対してfc内の1点を対応させる写像をx(t)とする。このとき、任意のtでf(x(t))=cとなるので、両辺をtで微分するとt=0において以下の式のようになる。
\[\nabla f(x(0))^T\frac{dx(0)}{dt}=0\]
つまりベクトル∇f(x(0))と\(\frac{ds(0)}{dt}\)は直交する。ここでf上の様々な曲線x(t)の「速度ベクトル\(\frac{ds(0)}{dt}\)を集めたものがfcのx(0)での接平面をなすので、勾配∇f(x(0))は等高線(等高面)fcとx(0)で直行する。
2回微分可能な関数fへのヘッセ行列(Hessian)∇2f(x)∈ℝnxnを以下のように定義する。
\[(\nabla^2f(x))_{ij}=\frac{\partial^2f}{\partial x_i\partial x_j}(x),\quad i,j=1,\dots,n\]
偏微分の可換性から、ヘッセ行列は対称行列であることがわかる。
勾配やヘッセ行列を用いると、関数fを局所的に1次式や2次式で近似することができる。その基礎となるテイラーの定理(Taylor’s theorem)について述べる。
<定理1 テイラーの定理>
関数f:ℝn→ℝが1階微分可能のとき、x,δ∈ℝに対して実数c∈(0,1)が存在して以下が成り立つ\[f(x+\delta)=f(x)+\nabla f(x+\delta)^T\delta\]また2解微分可能の時、実数c∈(0,1)が存在して以下が成り立つ。\[f(x+\delta)=f(x)+\nabla f(x)^T\delta+\frac{1}{2}\delta^T\nabla ^2f(x+c\delta)\delta\]
関数値の大雑把な評価をするのに便利なランダウの記号O(・)、o(・)を代入する。関数f:ℝn→ℝとg:ℝn→ℝが以下を満たす時、
\[\lim_{x\rightarrow a}\left|\frac{f(x)}{g(x)}\right|=0\]
以下のように書く
\[f(x)=o(g(x),\quad (x \rightarrow a)\]
また以下の時
\[\lim_{x\rightarrow a}\left|\frac{f(x)}{g(x)}\right|\lt \infty\]
以下のように書く
\[f(x)=0(g(x),\quad (x \rightarrow a)\]
これらは点aの近傍でのf(x)とg(x)の大きさの関係を表している。どの点の近傍を考えているか明らかな時は、x→aを省略することもある。定義より、f(x)=o(g(x))ならf(x)=O(g(x))となるが、f(x)=o(g(x))の方がより詳細な情報を記述していることになる。関数f(x)を原点の近傍でf(x)=O(||x||k)やf(x)=o(||x||k)のように評価することで、関数値を大雑把に見積もることもできる。
関数f:ℝn→ℝの1階微分が連続(1階連続微分可能)なら、テイラーの定理により以下の式が成り立つ。
\[f(x+\delta)=f(x)+\nabla f(x)^T\delta+o(||\delta||)\]
同様に2階微分が連続(2階微分可能)なら以下の式が成り立つ。
\[f(x+\delta)=f(x)+\nabla f(x)^T\delta+\frac{1}{2}\nabla^2 f(x)\delta+o(||\delta||^2)\]
ここでδ→0の状況を考える。常識は、勾配とヘッセ行列を用いて関数fを1次式や2次式で近似しているとみなせる。これらの矜持式はfの最適化において重要な情報を提供する。
勾配∇f(x)に関する類似の展開公式として、2回微分可能な関数fに対して以下の式が成り立つ。
\[\nabla f(x+\delta)=\nabla f(x)+\displaystyle\int_0^1\nabla^2f(x+\delta)\delta dt\]
ここで積分はベクトルの各要素ごとに行われる、
最適化問題では、関数fや勾配∇fにリプシッツ連続性を仮定することがある。関数f:ℝn→ℝがリプシッツ連続(Lipschitz continuous)であるとは、正実数L>0が存在して、任意のx,y∈ℝnに対して以下の式が成り立つことを定義する。
\[|f(x)-f(y)|\leq L||x-y||\]
定数Lをリプシッツ定数という。また勾∇fが以下のリプシッツ連続性を満たす時、fをγ平滑関数(smooth function)と呼ぶ。
\[||\nabla f(x)-\nabla f(y)||\leq \gamma||x-y||,\quad \gamma\gt 0\quad(1)\]
陰関数定理
関数F:ℝkxℝn→ℝkに対して、F(x,y)=0∈ℝkを満たす変数x∈ℝk,y∈ℝnを考える。ここでyに定数を代入すると、常識はk次元変数xとk本の等式からなる方程式とみなせる。変数の数と式の数が等しいので、方程式を満たすxが存在することが期待される。例えばFが以下の線形式で与えられるとする。
\[F(x,y)=Ax+By,\quad A\in \mathbb{R}^{k\times k},B\in\mathbb{R}^{k\times n}\]
行列Aが正則なら、与えられたyに対して以下のようにすれば、F(x,y)=0が成り立つ。
\[x=-a^{-1}By\]
一般の方程式F(x,y)=0を満たすxが変数yにどのように依存するかを調べる時、陰関数定理(implict function theorem)が有用となる。変数x∈ℝk,y∈ℝnに対して、関数F(x,y)∈ℝkの微分を以下の式とする。
\[\nabla_x F=\left(\frac{\partial F_j}{\partial x_i}\right)_{ij}\in\mathbb{R}^{k\times k},\ \nabla_y F=\left(\frac{\partial F_j}{\partial y_i}\right)_{ij}\in\mathbb{R}^{n\times k}\]
これらの行列をヤコビ行列(Jacobian)と呼ぶ。
<定理2 陰関数定理>
関数F:ℝkxℝn→ℝkはr回連続微分可能とし、点(a,b)∈ℝkxℝnにおいて次の条件が成り立つとする。\[F(a,b)=0,\quad det(\nabla_x F(a,b))\neq 0\]第2式は行列式が非ゼロであることを意味する。このとき、aの近傍Ux⊂ℝk、bの近傍Uy⊂ℝnと関数𝜑:Uy→Uxが存在し、如何成り立つ。\[𝜑(b)=a,\\y\in U_y⇒F(𝜑(y),y)=0\]さらに𝜑はr回微分可能となる。
陰関数定理より、𝜑(y)の微分をFの微分で表すことができる。実際、関数F(𝜑(y),y)=0と微分して以下が得られる。
\[\nabla 𝜑(y)=-\nabla_y F(𝜑(y),y)(\nabla_x F(𝜑(y),y))^{-1}\]
ここで以下となる。
\[\nabla𝜑(y)=(\nabla𝜑_1(y),\dots,\nabla_k(y))=\left(\frac{\partial 𝜑_j}{\partial y_i}\right)_{ij}\in\mathbb{R}^{n\times k}\]
線形式の場合の拡張になっていることがわかる。
対角行列と固有値
n次行列A=(aij)∈ℝnxnの任意の要素についてaij=aji(すなわちAT=A)となるとき、Aを対称行列(symmetric matrix)と呼ぶ。連続最適化ではヘッセ行列を扱うことが多い為、対称行列の扱いに慣れることが必須となる。
行列A=(aij)∈ℝnxnに対して以下の式を満たす値λとn次元ベクトルxをそれぞれ固有値(eigenvalue)、固有ベクトル(eigenvector)と呼ぶ。
\[\mathbf{Ax}=\lambda \mathbf{x}\]
一般に、Aの要素がすべて十数でもλやxの要素が実数とは限らず、複素数になることがある。例えば、回転行列などは、複素数の範囲で考える必要がある。
Aがn次対称行列なら、λは実数値、xはℝnの元となる。さらにn本の固有ベクトルが互いに直行するように選ぶことができる。すなわち、n次対称行列Aにおいて以下を満たすλi,xiが存在する。
\begin{eqnarray}\mathbf{Ax}_i&=&\lambda_ix_i,\ x_i\in\mathbb{R}^n,\ \lambda_i\in\mathbb{R},\ i=1,\dots,n\\\mathbf{x}_i^T\mathbf{x}_j&=&\begin{cases}1\quad (i=j)\\0\quad (i\neq j)\end{cases}\end{eqnarray}
行列Qを以下のようにおくと、QTQ=QQT=IとなるのでQは直交行列となる。
\[\mathbf{Q}=\left(\mathbf{x}_1\ \mathbf{x}_2\ \dots\ \mathbf{x}_n\right)\in\mathbb(R)^{n\times n}\]
従って対称行列は直交行列で対角化可能となる。実際、λ1,…,λnを対角要素にもつn次対角行列をΛとすると、Aの固有値、固有ベクトルの関係から以下のような式となり、A=QTAQが成り立つ。
\[\mathbf{AQ}=\mathbf{QA}\]
またAを以下の式のように表すこともできる。
\[\mathbf{A}=\mathbf{Q\Lambda Q}^T=\displaystyle\sum_{i=1}^n\lambda_ix_ix_i^T\quad(2)\]
対称行列A∈ℝnxnが、任意のx∈ℝnに対して以下の式を満たす時、Aを非負定値行列(non-negative definite matrix)と呼び、A⪰0(またはO⪯A)と表す。非負低値行列がさらに以下の条件を満たす時正定値行列(positive definite matrix)と呼び、A≻O(またはO≺A)と表す。
\[x\neq 0\ なら\ x^TAz\gt 0\]
例えば、行列X∈ℝnxmに対してXXTはn次非負定値行列であり、そらにXの指数(ランク)がnのとき低定値行列になる。
n次対称行列A,Bが任意のベクトルx∈ℝnに対して以下の式を満たす時、A⪰B(またはB⪯A)と表す。
\[\mathbf{x}^T\mathbf{Ax}\geq \mathbf{x}^T\mathbf{Bx}\]
これはA–B⪰Oと同様になる。同時にA–B≻OならA≻B(またはB≺A)と表す。
非負定値性や正定値性は、固有値に対する条件として表すことができる。行列Aが非負定値行列であることは、Aの固有値がすべて非負であることと同値になる。また行列Aが正定値行列であることは、Aの固有値がすべて正であることと同値となる。実際に、式(2)を用いると以下のようになり、左辺の符号と固有値の符号の関係がわかる。
\[\mathbf{x}^T\mathbf{Ax}=\displaystyle\sum_{i~1}^n\lambda_i(\mathbf{x}^T\mathbf{x}_i)^2\]
関数f:ℝ→ℝと対称行列Aが与えられた時、行列Aを敷き(2)のように対角化し、変換\(\mathbf{A}⟼\bar{f}(\mathbf{A})\)を以下のように定義する。
\[\bar{f}(\mathbf{A})=\displaystyle\sum_{i=1}^nf(\lambda_i)\mathbf{x}_i\mathbf{x}_i^T\]
関数f(x)=xkとすると、kが自然数なら固有ベクトルの直交性から通常の行列の積Akと\(\bar{f}(\mathbf{A})\)は一致する。対称行列Aが正則なら、f(x)=1/xに対して\(\bar{f}(\mathbf{A})\)はAの逆行列に一致する。またf(x)=x1/2とすると、非負定値行列Aに対して以下のような式となる。
\[\mathbf{A}^{1/2}=\displaystyle\sum_{i=1}^n\lambda_i^{1/2}\mathbf{x}_i\mathbf{x}_i^T\]
定義より以下が成り立つ。
\[\mathbf{A}^{1/2}\mathbf{A}^{1/2}=\mathbf{A}\]
非負定値(正定値)行列Ai対して、A1/2も非負定値(正定値)行列となる。単位行列Iは正定値行列Aを用いると以下のように表すことができる。
\[\mathbf{I}=\mathbf{A}^{1/2}\mathbf{A}^{-1/2}=\mathbf{A}^{-1/2}\mathbf{A}^{1/2}\]
ここで、A-1/2は(A1/2)-1を意味するが、これは(A-1)1/2と同じとなる。
部分空間への射影
n次元空間の部分空間Sに対して、Sの直交補空間S⊥を以下のように定義する。
\[S^{⊥}=\{\mathbf{x}\in \mathbb{R}^n|\forall \mathbf{y}\in S\quad \mathbf{x}^T\mathbf{y}=0\}\]
このときS⊥もℝnの部分空間となり、SとS⊥の共通部分はゼロベクトルの元なる。ベクトルx∈ℝnが以下となるように分解するとき、xiをxのSへの射影(projection)と呼ぶ。
\[\mathbf{x}=\mathbf(x)_1+\mathbf{x}_2\quad \mathbf{x}_1\in S,\ \mathbf{x}_2\in S^⊥\]
以下、射影は一意に存在することを示す。部分空間Sの基底をx1,…,xp,p≤nとし、行列Zを以下のようにすると、Zの階数はpなので、ZTZ∈ℝpxpは生息となる。
\[Z=\left(z_1\ \dots\ z_p\right)\in\mathbb{R}^{n\times p}\]
n次行列Pを以下のようにすると
\[\mathbf{P}=\mathbf{Z}(\mathbf{Z}^T\mathbf{Z})^{-1}\mathbf{Z}^T\]
以下の式が成り立つ。
\[\mathbf{P}^T=\mathbf{P},\quad \mathbf{P}^2=\mathbf{P}\quad(3)\]
このとき以下のように分解できる。
\[\mathbf{x}=\mathbf{Px}+(\mathbf{I}-\mathbf{P})\mathbf{x},\quad\mathbf{Px}\in S)\quad (\mathbf{I}-\mathbf{P})\mathbf{x}\in S^⊥\]
実際、定義よりPx∈Sとなり、以下の式より(I–P)x∈S⊥となるため、射影の存在がわかる。次に射影の一意性を示す。もし\(\mathbf{x}=\mathbf{x}_1+\mathbf{x}_2=\mathbf{x}’_1+\mathbf{x}’_2\)のように2通りの分解ができるなら以下のようになラリ、x1=x’1が導出される。
\[\mathbf{x}_1-\mathbf{x}’_1=\mathbf{x}_2-\mathbf{x}’_2\in S\cap S^⊥=\{0\}\]
射影x1はxまでの距離を最小にするS上の点として特徴づけられている。これはx∈Sして以下の式が成り立つことからも確認できる。
\begin{eqnarray}||\mathbf{x}-\mathbf{z}||^2&=&||\mathbf{x}-\mathbf{x}_2+\mathbf{x}_1-\mathbf{z}||^2\\&=&||\mathbf{x}-\mathbf{x}_1||^2+||\mathbf{x}_1-\mathbf{z}||^2+2(\mathbf{x}-\mathbf{x}_)^T(\mathbf{x}_1-\mathbf{z})\\&=&||\mathbf{x}-\mathbf{x}_1||^2+||\mathbf{x}_1-\mathbf{z}||^2\end{eqnarray}
最後の等式は以下を用いた。
\[\mathbf{x}-\mathbf{x}_1=\mathbf{x}_2\in S^⊥,\quad \mathbf{x}_1-\mathbf{z}\in S\]
式(3)を満たす行列を射影行列(projection matrix)と呼ぶ。射影行列の固有値は0または1であることがわかる。
行列の1ランク更新
行列Aに階数が1の行列を加えたA+xyTを、Aの1ランク更新(1 rank upgrage)と呼ぶ。このような更新式は、自然勾配法や準ニュートン法で用いられる。更新する前の行列の情報を用いて、1ランク更新した行列に関するさまざまな演算を効率的に行う為の公式が考案されている。
シャーマン・モリソンの公式(Sherman-Morrison formula)は、n次正則行列Aとx,y∈ℝnに対して、以下のように表される。
\[\mathbf{A}+\mathbf{xy}^T)^{-1}=\mathbf{A}^{-1}-\frac{1}{1+\mathbf{y}^T\mathbf{A}^{-1}\mathbf{x}}\mathbf{A}^{-1}\mathbf{xy}^T\mathbf{A}^{-1}\quad(4)\]
実際にA+xyTとの値を計算することで、公式が成り立つことが確認できる。逆行列A-1が既知なら、この公式を用いて1ランク更新の逆行列(A+xyT)-1を効率的に計算することができる。
式(4)はA+xyTが正則であるための必要十分条件が1+yTA-1x≠0であることを示している。さらに、行列式について以下の式も成り立つ。
\[det(\mathbf{A}+\mathbf{xy}^T)=(1+\mathbf{y}^T\mathbf{A}^{-1}\mathbf{x})det(\mathbf{A})\quad(5)\]
式(5)は、行列I+A-1xyTの固有値が1(n-1重)と1+yTA-1xであることからわかる。
さまざまなノルム
ノルムとはベクトルの長さに対応する量となる。機械学習や統計学では様々なノルムを扱う。最も基本的なノルムは、ユークリッドノルムとなる。定義を再確認しておくと、ベクトルx=(x1,…,xn)T∈ℝnに対して以下のように定められる。
\[||\mathbf{x}||=(\mathbf{x}^T\mathbf{x})^{1/2}=\left(\displaystyle\sum_{i=1}^n|x_i|^2\right)^{1/2}\]
一般のノルムを定義する。
<定義3 ノルム>
ベクトルxに非負値n(x)≥0を対応させる関数が以下の性質を満たす時、n(・)をノルム(norm)と呼ぶ。
-
- n(x)≥0、n(x)=0 ⇔ x=0
- 任意のα∈ℝに対してn(αx)=|α|n(x)
- 任意のx,yに対してn(x+y)≤n(x)+n(y)
ユークリッドノルムn(x)=||x||はノルムの定義を満たす。一般にp≥1に対して、ベクトルxのp-ノルムを以下のように定義する。
\[||\mathbf{x}||_P=\left(\displaystyle\sum_{i=1}^n|x_i|^P\right)^{1/P}\]
さらにp=∞に対して以下のように定義する。
\[||\mathbf{x}||_{\infty}=\max_{i=1\dots, n}|x_i|\]
ユークリッドノルムは2-ノルムになる。p-ノルムもノルムの定義を満たす。ユークリッドノルムに対して、シュワルツの不等式(Schwart’a ineuality)が成り立つ。
\[\mathbf{x}^T\mathbf{y}|\leq||\mathbf{x}||||\mathbf{y}||\]
これは、変数t∈ℝをもつ2次関数||x+ty||2の非負性の条件から導出される。統合成立条件はxとyが1次十足になることとなる。p-ノルムに関しては、シュワルツの不等式の拡張であるヘルダーの不等式(Hölder’s inequality)が成立する。
\[|\mathbf{x}^T\mathbf{y}|\leq||\mathbf{x}||_p||\mathbf{y}||_q\]
ここでp,qは以下を満たす実数の組とし、p=1, q=∞の場合も含む。
\[p,q≥1.\quad \frac{1}{p}+\frac{1}{q}=1\]
ヘルダーの不等式でp=q=2とすると、シュワルツの不等式が得られる。
ベクトルに対するユークリッドノルム||・||を用いて、行列A∈ℝnxmのノルムを以下のように定義することができる。
\[||\mathbf{A}||=\max_{x|in\mathbb{R}^m,x\neq 0}\frac{||\mathbf{A}||}{||\mathbf{x}||}\]
同様に、ベクトルのp-ノルムから行列のノルムを定義することもできる。
行列空間上の関数
行列の集合を定義域とする関数f:ℝnxm→ℝに関する公式について述べる。勾配を行列の形式で表し、X={xij}∈ℝnxmに対して∇f(X)∈ℝnxmを以下のようにする。
\[(\nabla f(\mathbf(X))_{ij}=\frac{\partial f}{\partial x_{ij}}(\mathbf{X})\]
以下具体的な関数に対する勾配を示す。行列A=(aij)∈ℝnxmに対して、f:ℝnxm→ℝを以下のように定義する。
\[f(\mathbf{X})=tr(\mathbf{XA}^T)=\displaystyle\sum_{i=1}^n\sum_{j=1}^ma_{ij}x_{ij}\]
すると導関数は以下のようになる。
\[\nabla f(\mathbf{X})=\mathbf{A}\]
これは直接計算することで確認できる。
行列Xの余因子行列を\(\tilde{\mathbf{X}}=(\Delta_{ij})\)とすると、余因子行列の性質から以下のようになる。
\[\mathbf{X}\tilde{\mathbf{X}}=det(\mathbf{X})\cdot\mathbf{I}\]
よって任意のj=1,…,nについて以下のようになる。
\[det(\mathbf{X}=\displaystyle\sum_{i=1}^nx_{ik}\Delta_{ki}\]
ここでΔki(k=1,…,n)はxijに依存しないので以下のようになる。
\[\frac{\partial}{\partial x_{ij}}der(\mathbf{X})=\Delta_{ji}=(\tilde{\mathbf{X}}^T)_{ij}\]
従って以下のようになる。
\[(\nabla f(\mathbf{X}))_{ij}=\frac{(\tilde{\mathbf{X}}^T_{ij}}{det(\mathbf{X})}=((\mathbf{X}^T)^{-1})_{ij}\]
これはn次正則行列X∈ℝnxmに対して以下のように定義したとき。
\[f(\mathbf{X})=log|det(\mathbf{X})|\]
導関数が以下のようなることを示している。
\[\nabla f(\mathbf{X})=(\mathbf{X}^T)^{-1}\]
コメント