機械学習における連続最適化とは、ニューラルネットワークの重みやバイアスの最適化、回帰分析のパラメータ推定、SVMのパラメータ推定等の変数が実数値をとる最適化問題を解く手法となる。ニュートン法、L-BFGS法などがあり、目的関数の勾配やヘッセ行列などの情報を利用して、最適解に近づくように変数を更新していくアルゴリズムとなる。連続最適化では、目的関数の値だけでなく、制約条件も考慮する必要がある。ペナルティ法、バリア関数法などの制約つき最適化問題の手法を使う。ここでは機械学習プロフェッショナルシリーズ「機械学習のための連続最適化」をベースに機械学習における連続最適化について述べている。前回は「連続最適化」の概要について述べた。今回は連続最適化の基本事項として微積分・線形代数について述べる。イントロダクション最適化アルゴリズムを記述し、理論的性質を調べるために、微積分や線形代数の知識を利用する。ここではこれらの基本事項について述べる。行列の記法を定義する。実数を要素に持つnxn行列(n次行列)の全体をRnxnと表す。一般的にはRnxmはnxm次行列の全体となる。行列A∈Rnxmの要素を明示する時にはA=(aij)i=1,...,n,j=1,...,mのように記述し、簡単のためA=(aij)と書くこともある。微分可能な関数f:Rn→Rの勾配(gradient)を以下のように定義する。\mathbb{R}^n\]点xでの勾配∇f(x)は、関数f(x)の投稿戦に直行するベクトルとなる。これは次のように示すことができる。関数fの値が定数c∈Rである点の集合をfc={x∈Rn|f(x)=c}とする。実数パラメータt∈Rに対してfc内の1点を対応させる写像をx(t)とする。このとき、任意のtでf(x(t))=cとなるので、両辺をtで微分するとt=0において以下の式のようになる。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)∈Rnxnを以下のように定義する。i,j=1,\dots,n\]偏微分の可換性から、ヘッセ行列は対称行列であることがわかる。勾配やヘッセ行列を用いると、関数fを局所的に1次式や2次式で近似することができる。theorem)について述べる。f(x+\delta)^T\delta\]また2解微分可能の時、実数c∈(0,1)が存在して以下が成り立つ。^2f(x+c\delta)\delta\]関数値の大雑把な評価をするのに便利なランダウの記号O(・)、o(・)を代入する。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:Rn→Rの1階微分が連続(1階連続微分可能)なら、テイラーの定理により以下の式が成り立つ。f(x)^T\delta+o(||\delta||)\]同様に2階微分が連続(2階微分可能)なら以下の式が成り立つ。f(x)\delta+o(||\delta||^2)\]ここでδ→0の状況を考える。常識は、勾配とヘッセ行列を用いて関数fを1次式や2次式で近似しているとみなせる。これらの矜持式はfの最適化において重要な情報を提供する。勾配∇f(x)に関する類似の展開公式として、2回微分可能な関数fに対して以下の式が成り立つ。最適化問題では、関数fや勾配∇fにリプシッツ連続性を仮定することがある。continuous)であるとは、正実数L>0が存在して、任意のx,y∈Rnに対して以下の式が成り立つことを定義する。L||x-y||\]定数Lをリプシッツ定数という。function)と呼ぶ。関数F:RkxRn→Rkに対して、F(x,y)=0∈Rkを満たす変数x∈Rk,y∈Rnを考える。ここでyに定数を代入すると、常識はk次元変数xとk本の等式からなる方程式とみなせる。変数の数と式の数が等しいので、方程式を満たすxが存在することが期待される。Fが以下の線形式で与えられるとする。n}\]行列Aが正則なら、与えられたyに対して以下のようにすれば、F(x,y)=0が成り立つ。theorem)が有用となる。変数x∈Rk,y∈Rnに対して、関数F(x,y)∈Rkの微分を以下の式とする。k}\]これらの行列をヤコビ行列(Jacobian)と呼ぶ。陰関数定理>関数F:RkxRn→Rkはr回連続微分可能とし、点(a,b)∈RkxRnにおいて次の条件が成り立つとする。0\]第2式は行列式が非ゼロであることを意味する。このとき、aの近傍Ux⊂Rk、bの近傍Uy⊂Rnと関数φ:Uy→Uxが存在し、如何成り立つ。U_y⇒F(φ(y),y)=0\]さらにφはr回微分可能となる。陰関数定理より、φ(y)の微分をFの微分で表すことができる。実際、関数F(φ(y),y)=0と微分して以下が得られる。F(φ(y),y))^{-1}\]ここで以下となる。k}\]線形式の場合の拡張になっていることがわかる。matrix)と呼ぶ。連続最適化ではヘッセ行列を扱うことが多い為、対称行列の扱いに慣れることが必須となる。行列A=(aij)∈Rnxnに対して以下の式を満たす値λとn次元ベクトルxをそれぞれ固有値(eigenvalue)、固有ベクトル(eigenvector)と呼ぶ。\mathbf{x}\]一般に、Aの要素がすべて十数でもλやxの要素が実数とは限らず、複素数になることがある。回転行列などは、複素数の範囲で考える必要がある。Aがn次対称行列なら、λは実数値、xはRnの元となる。n本の固有ベクトルが互いに直行するように選ぶことができる。n次対称行列Aにおいて以下を満たすλi,xiが存在する。j)\end{cases}\end{eqnarray}行列Qを以下のようにおくと、QTQ=QQT=IとなるのでQは直交行列となる。n}\]従って対称行列は直交行列で対角化可能となる。実際、λ1,...,λnを対角要素にもつn次対角行列をΛとすると、Aの固有値、固有ベクトルの関係から以下のような式となり、A=QTAQが成り立つ。\[\mathbf{AQ}=\mathbf{QA}\]またAを以下の式のように表すこともできる。matrix)と呼び、A⪰0(またはO⪯A)と表す。matrix)と呼び、A≻O(またはO≺A)と表す。0\]例えば、行列X∈Rnxmに対してXXTはn次非負定値行列であり、そらにXの指数(ランク)がnのとき低定値行列になる。n次対称行列A,Bが任意のベクトルx∈Rnに対して以下の式を満たす時、A⪰B(またはB⪯A)と表す。\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:R→Rと対称行列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⊥を以下のように定義する。\mathbf{x}^T\mathbf{y}=0\}\]このときS⊥もRnの部分空間となり、SとS⊥の共通部分はゼロベクトルの元なる。ベクトルx∈Rnが以下となるように分解するとき、xiをxのSへの射影(projection)と呼ぶ。S^⊥\]以下、射影は一意に存在することを示す。部分空間Sの基底をx1,...,xp,p≤nとし、行列Zを以下のようにすると、Zの階数はpなので、ZTZ∈Rpxpは生息となる。p}\]n次行列Pを以下のようにすると\[\mathbf{P}=\mathbf{Z}(\mathbf{Z}^T\mathbf{Z})^{-1}\mathbf{Z}^T\]以下の式が成り立つ。\mathbf{P}^2=\mathbf{P}\quad(3)\]このとき以下のように分解できる。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が導出される。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}最後の等式は以下を用いた。matrix)と呼ぶ。射影行列の固有値は0または1であることがわかる。upgrage)と呼ぶ。このような更新式は、自然勾配法や準ニュートン法で用いられる。更新する前の行列の情報を用いて、1ランク更新した行列に関するさまざまな演算を効率的に行う為の公式が考案されている。formula)は、n次正則行列Aとx,y∈Rnに対して、以下のように表される。\[\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∈Rnに対して以下のように定められる。\[||\mathbf{x}||=(\mathbf{x}^T\mathbf{x})^{1/2}=\left(\displaystyle\sum_{i=1}^n|x_i|^2\right)^{1/2}\]一般のノルムを定義する。ノルム>ベクトルxに非負値n(x)≥0を対応させる関数が以下の性質を満たす時、n(・)をノルム(norm)と呼ぶ。x=0任意のα∈Rに対して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=∞に対して以下のように定義する。n}|x_i|\]ユークリッドノルムは2-ノルムになる。p-ノルムもノルムの定義を満たす。ineuality)が成り立つ。\[\mathbf{x}^T\mathbf{y}|\leq||\mathbf{x}||||\mathbf{y}||\]これは、変数t∈Rをもつ2次関数||x+ty||2の非負性の条件から導出される。統合成立条件はxとyが1次十足になることとなる。inequality)が成立する。\frac{1}{p}+\frac{1}{q}=1\]ヘルダーの不等式でp=q=2とすると、シュワルツの不等式が得られる。ベクトルに対するユークリッドノルム||・||を用いて、行列A∈Rnxmのノルムを以下のように定義することができる。0}\frac{||\mathbf{A}||}{||\mathbf{x}||}\]同様に、ベクトルのp-ノルムから行列のノルムを定義することもできる。行列の集合を定義域とする関数f:Rnxm→Rに関する公式について述べる。勾配を行列の形式で表し、X={xij}∈Rnxmに対して∇f(X)∈Rnxmを以下のようにする。x_{ij}}(\mathbf{X})\]以下具体的な関数に対する勾配を示す。行列A=(aij)∈Rnxmに対して、f:Rnxm→Rを以下のように定義する。\[f(\mathbf{X})=tr(\mathbf{XA}^T)=\displaystyle\sum_{i=1}^n\sum_{j=1}^ma_{ij}x_{ij}\]すると導関数は以下のようになる。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に依存しないので以下のようになる。x_{ij}}der(\mathbf{X})=\Delta_{ji}=(\tilde{\mathbf{X}}^T)_{ij}\]従って以下のようになる。f(\mathbf{X}))_{ij}=\frac{(\tilde{\mathbf{X}}^T_{ij}}{det(\mathbf{X})}=((\mathbf{X}^T)^{-1})_{ij}\]これはn次正則行列X∈Rnxmに対して以下のように定義したとき。\[f(\mathbf{X})=log|det(\mathbf{X})|\]導関数が以下のようなることを示している。f(\mathbf{X})=(\mathbf{X}^T)^{-1}\]次回は機械学習における連続最適化の基本事項としての凸解析の基礎について述べる。確率的最適化における凸解析の基本事項(2)フェンシェルの双対定理と近接写像と強凸関数このコンテンツはパスワードで保護されています。閲覧するには以下にパスワードを入力してください。コメントをキャンセルメールアドレスが公開されることはありません。※サイト次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。作成者hummingbirdAI/IT技術全般およびそれらを使ったビジネス立案に関してアドバイスいたします。作成者hummingbirdAI/IT技術全般およびそれらを使ったビジネス立案に関してアドバイスいたします。お困りごとがあればご連絡くださいhummingbirdをフォローするモバイルバージョンに移動タイトルとURLをコピーしました。