サマリー
機械学習における連続最適化とは、ニューラルネットワークの重みやバイアスの最適化、回帰分析のパラメータ推定、SVMのパラメータ推定等の変数が実数値をとる最適化問題を解く手法となる。連続最適化の代表的な手法には、勾配降下法、最急降下法、共役勾配法、準ニュートン法、L-BFGS法などがあり、目的関数の勾配やヘッセ行列などの情報を利用して、最適解に近づくように変数を更新していくアルゴリズムとなる。また、連続最適化では、目的関数の値だけでなく、制約条件も考慮する必要がある。制約条件を考慮した最適化問題を解くには、KKT条件を満たす方法、内点法、射影勾配法、ペナルティ法、バリア関数法などの制約つき最適化問題の手法を使う。ここでは機械学習プロフェッショナルシリーズ「機械学習のための連続最適化」をベースに機械学習における連続最適化について述べている。
読書メモより。
「最小の努力で、最大の学びがここにある! ・境界分野が面白い! 基礎から最先端まで,骨太の一冊! ・機械学習に不可欠な基礎知識が身につく。 ・おだやかではない。かつてこれほどの教科書があっただろうか。」
第Ⅰ部 導入
第1章 はじめに
1.1 機械学習における推論と計算
機械学習や統計学では、精度の良い推定や予測を行うことが主な目標の一つ
データが生成されるプロセスを適切にモデリングし、 統計的に妥当な損失尺度(誤差評価の基準)を最小化する というアプローチがよく使われる
どのような損失を用いればどれくらいの統計的精度を達成できるか?
計算効率も大切
アルゴリズム例
最尤法
フィッシャーのスコア法(ニュートン法に類似した最適化法)
回帰分析における一般化線形モデルのパラメータ推定のための標準的な手法
ベイズ法
マルコフ連鎖モンテカルロ法
事後分布を求めるための高次元積分値の計算
統計モデルの構造を利用した効率的な推論や予測を行うための計算法
混合ガウス分布のパラメータ推定のためのEMアルゴリズム
階層型ニューラルネットワーク・モデルに対する誤差逆伝搬法
ベイジアンネットワーク に対する確率伝搬法
集団学習の一例であるブースティング
1.2 最適化問題の記述
1.2.1 さまざまな最適化問題
実数の集合 ℝ
N次元ユークリッド空間 ℝn
N次元の元xを列ベクトルとみなす
x=(x1,...,xn)T
Tはベクトルや行列の転置
ベクトルxのノルム(長さ)を
ユークリッドノルム
2点x,y ∈ ℝnの間の距離は、 ユークリッドノルムを用いて∥x - y∥
最適化問題は、 与えられた関数𝒇 : ℝn → ℝを ある制約条件x ∈ 𝑆 ⊂ ℝnの元で 最適化する(具体的には最小化もしくは最大化)という問題
最小化が目的の場合
「min」は関数を最小化することを意味
Minの下のxは、最適化すべき変数
「subject to ~」 は「~の条件のもとで」を意味する
「s.t.」と省略して描くこともある
𝑓を目的関数(objective function)
𝒇(x)はユークリッド空間乗で定義され、多くの場合、連続性や微分可能性などの性質を満たす
連続最適化(continuous optimization)
𝑺を実行可能領域(feasible region)
𝑺が定める条件「x ∈ 𝑺 」を制約(constraint)
例1.1 :学校の配置問題
小学校が一つもない村に、 5軒の家がありそれぞれの位置は座標αi ∈ ℝ2 (i=1,2,3,4,5)で表される
この村のある領域内 𝑺 ⊂ ℝ2に家を建てる時、 どこに立てれば良いか
制約条件
学校までの距離の2乗が平均的に最小になる場所にたてる
学校までの距離が平均的に最小になる場所にたてる
最も遠い家から学校までの距離を最小にする
例1.2 輸送問題
生産地S1,S2から消費地T1,T2,T3に品物を輸送する時、 輸送コストが最も安くなるような配送プランは?
輸送コストの総計は
生産地Siから消費地Tjへの輸送コストは、品物1単位当たりcijとする
輸送量をxijとすると、
x ∈ ℝ6をx ={x11,...,x23}
各生産地では最大ai(i=1,2)だけ生産
各消費地では最低bj(j=1,2,3)の量だけ消費される
モデル
制約
実行可能解(feasible solution)
最適化問題の制約を満たす点
最適解(optimal solution)
大域的最適解(global optimal solution)
大域解
最小化元(最大化元)
最適値(optimal value)
目的関数の下限(上限)の値
最適値が存在していても最適解が存在するとは限らない
近傍(neighborhood)
点x ∈ ℝn のε近傍を B(x,ε) ={y ∈ ℝn | ∥x -y∥ < ε}
局所最適解(local optimal solution)
制約なし最適化問題(unconstrained optimization problem)
等式制約つき最適化問題(equality constrained optimization problem)
不等式制約条件つき最適化問題(inequality constrained optimization problem)
最適解の存在についての可能性
Sが空集合となり、実行可能回が存在しない
Sは空集合ではなく、最適解が存在する
Sは空集合ではなく、最適解が存在しない
最小値の場合
S上でfがいくらでも小さくな理、最適解が-∞となる
1.2.2 反復法と収束速度
多くの最適化アルゴリズムは、 基本的な手順として「反復法(iteration method)として記述される
基本の反復アルゴリズム
初期化:初期値x0を定める、k←0とする
1. 停止条件を満たすなら、結果を出力し、計算を終了する
2. 関数f(x), 集合S, 点列の履歴x0,...,xkなどの情報を用いてxk+1を計算する
3 k ← k+1とする、ステップ1に戻る
反復法における数値解x0,x1,...,が できるだけ早く最適解x*に収束するように、 アルゴリズムを構成する
アルゴリズムの停止条件を適切に設置する必要がある
収束速度の評価尺度
{xk}∞k=0はx*に一次収束(linear convergence)
数値解xkから最適解までの誤差を‖xk-x*‖で測る
‖xk -x*‖ = 0が保証されている
超一次収束 (superlinear convergence)
2次収束(quadratic convergence)
Memo:sup(上限)とinfの意味、maxとの違い
max A : Aの最大値
任意のx∈Aに対してx≤cかつ(cはどの要素よりも小さくはない→cはAの上限)
min A : Aの最小値
sup A : Aの上限(スープ) supernum
任意のx∈Aに対してx≤cかつ(cはAの上限)
Cより小さい任意の実数に対して、r<xなるx∈Aが存在する(少しでも小さくすると上昇でなくなる) 上界の最小値 supはmaxの一般化 Maxは存在するとは限らないが、supは常に存在する inf A : Aの下限値(インフ) infimum 第2章 基礎事項 2.1 微積分・線形代数の基礎 はじめに 最適化アルゴリズムの理論的性質を調べるために、微積分や線形代数の知識を使う 行列の記法 実数を要素にもつn x n行列(n次行列)の全体をℝn x mと表す 2.1.1 テイラーの定理 微分可能な関数𝒇 : ℝn → ℝの勾配(gradient) 点xでの勾配∇𝒇(x)は、関数𝒇(x)の等高線に直行するベクトル 関数𝒇の値が定数c∈ℝである点の集合𝒇c={x ∈ ℝn | 𝒇(x)=c} 実数パラメータ t ∈ ℝに対して、 𝒇c内の1点を対応させる写像をx(t)とする 任意のtで𝒇(x(t)) = 0 両辺をtで微分 ∇𝒇(x(0))Tdx(0)/dt = 0 ベクトル∇𝒇(x(0))とdx(0)/dtは直交する 勾配∇𝒇(x(0))は等高線𝒇cとx(0)で直行する 2回微分可能な関数𝒇のヘッセ行列(Hessian)∇2𝒇(x)∈ℝnxn 勾配やヘッセ行列を用いると、関数𝒇を局所的に1次式や2次式で表せる 定理2.1 テイラーの定理 関数𝒇:ℝn→ℝが1回微分可能 x, 𝛅 ∈ ℝに対し、実数c ∈ (0, 1)が存在 𝒇(x + 𝛅) = 𝒇(x) + ∇𝒇(x + 𝜹)T𝜹 2回微分可能の時 𝒇(x + 𝛅) = 𝒇(x) + ∇𝒇(x)T𝜹 + 1/2𝜹T∇2𝒇(x + c𝜹)𝜹 リプシッツ連続(Lipchits continuous) γ-平滑関数(smooth function) 2.1.2 陰関数定理 関数F : ℝk x ℝn → ℝkに対して、F(x, y)=0 ∈ ℝkを満たす変数x∈ℝk, y∈ℝnを考える yに定数を代入すると、k次元変数xとk本の等式からなる方程式とみなせる 変数の数と式の数が同じなので、方程式を満たすxが存在することが期待される 例 F(x,y)=Ax + By, A∈ℝk x k, B∈ℝk x n 行列Aが正則なら、与えられたyに対して x = A-1Byとすれば、F(x,y)=0が成り立つ 陰関数定理(implicit function theorem) 多項関係を多変数函数に読み替えることを可能にする基本的な道具 グラフの観点では関係のグラフを函数のグラフとして表す 関係全体ではなく、関係の始域を制限することで函数が取れる 例:円のグラフは一つの解は得られないが、一部のデータだけであれば解が得られる 陰関数定理はそのような函数の存在を保証するための十分条件を与えるもの 陰関数定理を述べるためには、fのヤコビ行列(函数行列)が必要 Fの全ての偏微分によって形作られる行列 2.1.3 対称行列と固有値 N次行列A=(aij)∈ℝnxnの任意の要素についてaij=aji(すなわちAT=A)となる時 Aを対称行列(symmetric matrix) 連続最適化ではヘッセ行列を扱うことが多いため、対称行列の扱いに慣れることが大切 ヘッセ行列(Hessian matrix) 多変数スカラー値関数の二階偏導関数全体が作る正方行列 実数値関数の極値判定に用いられる 対称行列の性質 行列A∈ℝnxnに対して、Ax=λxを満たす値λとn次元ベクトルxをそれぞれ固有値(eigenvalue)、固有ベクトル(eigenvactor)と呼ぶ 対称行列A∈ℝnxnが、任意のx∈ℝnに対して、xTAx≥0ょ満たす時 Aを非負定値行列 (non-negative definite matrix) A⪰O 非負定値行列Aがさらに、x≠0なら、xTAx >0を満たす時
Aを正定値行列(positive definite matrix)と呼ぶ
A ≻ O
2.1.4 部分空間への射影
N次元空間の部分空間Sに対して、Sの直交捕空間S⊥
ベクトルxの部分空間Sへの射影x1
射影x1はxまでの距離を最小にするS上の点として特徴つけられる
射影行列の固有値は0または1
2.1.5 行列の1ランク更新
行列Aに階数が1の行列を加えたA + xyTを、 Aの1ランク更新(1 rank update)と呼ぶ
自然勾配法や準ニュートン法で用いられる
更新する前の行列の情報を用いて、1ランク更新した行列に関する様々な演算を効率的に行うための公式が考案されている
シャーマン・モリソンの公式 (Sherman-Morison formula)
2.1.6 さまざまなノルム
ノルムとは、ベクトルの長さに対応する量
最も基本的なノルムはユークリッドノルム
定義2.3 ノルムの定義
ユークリッドノルムに対してシュワルツの不等式が成り立つ
P-ノルムに対してはシュワルツの不等式の拡張である「ヘルダーの不等式」が成立する
2.1.7 行列空間上の関数
2.2 凸解析の基礎
2.2.1 凸集合・凸関数
凸関数の定義
関数f(x)のグラフ上の任意の点P=(x,f(x)),Q=(y,f(y))に対して、 この2点に挟まれた範囲でf(x)のグラフが線分PQより下にある時、 関数f(x)は(下に)凸であるという
任意のx,y,および0≤λ≤1を満たす任意のλに対して
λf(x) + (1-λ)f(y) ≥ f(λx + (1-λ)y)
z=λx + (1-λ)yとすると、R=(x,f(z)), S=(z,λf(x) + (1-λ)f(z))
不等式はSがRより上にあることを示す
定義2.4 凸集合(convex set)
空集合でない集合S⊂ℝnに対して、 u,v∈S, 0≤λ≤1 ⇨(1-λ)u + λv ∈ Sが成り立つ時、 Sを凸集合(convex set)と呼ぶ
凸集合と非凸集合の例
凸集合の性質
凸集合Sに含まれる有限この点x1,...,xk∈Sの凸結合は、Sに含まれる
S,Tを凸集合とすると、S∩Tも凸集合
凸集合とは限らない集合Sに対して、Sを含む最小の凸集合を定義することができる
定義2.5 凸包(convex-hull)
補題2.6
定義2.7 凸関数
凸関数の性質
定義2.8 μ-強凸関数
2.2.2 凸関数の最小化
定義2.9 凸関数の最適化
補題2.10
2.2.3 凸関数の連続性
アフィン包(affine hull)
定理2.11 凸関数の連続性
2.2.4 微分可能な凸関数
定理2.12 勾配による凸関数の特徴付け
定理2.13 ヘッセ行列による凸関数の特徴付け
定理2.14 関数値の上下界
2.2.5 共役関数
関数fが微分可能なら、グラフの接平面が定まる
閉真凸関数と非凸関数
定理2.15 共役関数の性質
定理2.16 強凸性と平滑性
2.2.6 劣勾配・劣微分
定義2.17 劣勾配・劣微分
定理2.18 微分可能な凸関数と列微分
定理2.19 劣勾配と共役関数の関係
第Ⅱ部 制約なし最適化
第3章 最適性条件とアルゴリズムの停止条件
3.1 局所最適解と最適性条件
関数f:ℝn→ℝに対する制約なし最適化問題
凸とは限らない一般のfの最適化では、局所最適解を求めることが現実的な解になる
目的関数が微分可能なら局所最適解における勾配がゼロベクトルになる
定理:1次の必要条件
3.2式を満たすx*を関数fの停留点(stationary point)と呼ぶ
ヘッセ行列の情報を用いて局所解かどうかも判定可能
定理:2次の十分条件
テイラーの定理を用いて目的関数fを2次間数で近似することで、様々な性質がわかる
定理:2次の必要条件
1次と2次の必要条件を使って、停留点から局所最適解てせないXを覗くことができる
局所最適解の候補点は∇f(x)=0を満たす
ヘッセ行列が負の固有値を持つ候補点は、局所最適解ではない
例
関数f(x1,x2)=x14+x24+3x12x22-2x22
一次の条件
(X1,x2)=(0,0),(0,±1)
ヘッセ行列
2次の十分条件より(x1,x2)=(0,±1)において極小値-1をとる
(X1,x2)=(0,0)は2次の必要条件を満たさないので局所最適値ではない
停留点の中で極小値をとるのは点(0,±1)
定理:凸最適化の一次の十分条件
最小化問題のまとめ
3.2 集合制約に対する最適性条件
関数f:ℝn→ℝと集合S∈ℝnから定義される制約付き最適化問題を考える
応用ではSを凸集合と考える場合が多い
定義:実行可能方向
定理:h問題(3.4)に対する一時の必要条件
点x*におけるSの任意の実行可能方向dに対して、 上式が成り立つとき、x*を問題(3.4)の停留点と呼ぶ
∇f(x*)=0と同値
定理:h問題(3.4)に対する1次の十分条件
問題(3.4)がと最適化問題の時、停留点であることと最適解であることは同値
停留点から最適解を持ちめる
3.3 最適化アルゴリズムの停止条件
∇f(x*)=0と∇2f(xk)≻らが満たされれば、 xkが局所最適解で、反復法は停止
実際の計算では数値ごさが入り厳密に∇f(xk)=0が成立しているか確認が困難
∥∇f(xk)∥<εが成り立つ時アルゴリズムが停止すると想定
Εの選び方について
計算機の不動小数点における無為酸性度をεmatchとする
例:εmatch=10-16
前提条件
関数fは2回微分か可能とする
∇f(x*)=0、∇2f(x*)≻Oが成り立つ
関数値の差をf(xk)-f(x*)=h
解の差をδ=xk-x*
テイラーの定理ようり適当なt∈(0,1)が存在して、上式が成り立つ
x*とxkが十分近いとき∥δ∥=O(√h)となる
勾配に対するテイラーの定理より上式となる
∥∇f(xk)∥は∥δ∥と同じオーダーとなる
関数f(x)をεmatchの精度で計算する時の停止条件
スケーリングの影響を考慮すると上式を用いることもできる
左は厳しすぎるので上式のような停止条件が提案されている
実際の数値計算では、勾配だけではなく関数値f(xk)や反復解xkの挙動も観察しながら、停止するかどうか判断する
最終的に提案されている停止条件
第4章 勾配法の基礎
概要
最適化問題において、関数の勾配に関する情報を解の探索に用いるアルゴリズム
座標降下法と最急降下法がある
4.1 直線探索法
直線探索法(line search)
最初に目的関数が小さくなる方向を求め
次にその方向にxをどのくらい動かすかを表すステップサイズを計算する
そのステップサイズを用いて買いを求める方法
最急降下法
ニュートン法
準ニュートン法
関数値が十分に減少したかを判定
アルミホ条件
ウルフ条件
ステップ幅の許容範囲
強ウルフ条件
ゴールドシュタイン条件
パラメータαの探索法を工夫することで、 アルミホ条件の元で適切なステップ母を得る方法の一つ
バックトラキング法アルゴリズム
補題
ステップのアプローチ
厳密な最小解を求める方法
共役勾配法
十分な減少が得られれば良いという方法
バックトラッキング法
直接探索は局所最小値を脱出するために、焼き鈍し法と組み合わせることもある
4.2 直線探索を用いる反復法
反復法と直線探索法を用いて関数fを最適化
点xkまで透徹している
Xkから探索方向dkの方向に進み、 ステップ幅αkを適切に選んで、 上式のように点xkを更新する
探索方向dkは上式を満たすように選ぶ
Dkをfのxkにおける降下方向(descent direction)と呼ぶ
テイラーの定理より上式となる
十分小さなαkでf(xk+αkdk)-f(xk)<0隣、関数値が減少する方向に進む アルゴリズム 直線探索にウルフ条件を用いると、 アルゴリズムの収束を保証するために、 上の定理が成り立つ 4.3 座標降下法 目的関数を各座標に沿って最適化していく方法 Coordinate descent method) ベクトルeiを、i番目の要素が1、その他の要素が0である単位ベクトルとする 座標降下法の探索方向は±e1,...,±enの中から選ばれる 探索方向の選び方 一様ランダムに選ぶ方法 座標軸を巡回的に1,2,..,n,1,2,..,nと選ぶ方法 巡回的に求めるときは、ステップ幅を適当に決めると収束性を保証できる 勾配∇fの要素の絶対値が最大である座標を選ぶ方法 定理4.2の余弦cosθkの下限を求める 式 続き 等々 アルゴリズム 目的関数が微分不可能な時には収束しない 4.4 最急降下法 勾配ベクトルの計算が簡単な場合は、最急降下法が手軽な方法として使われる 4.4.1 最適化アルゴリズム 直線探索を用いる反復法の一種 探索法こうとしてdk=-∇f(xk)を用いる 証明 アルゴリズム ステップ幅を決める基準としてウルフ条件を考える 4.4.2 最急降下法の収束速度 例:凸二次関数に最急降下法を適用 Q∈ℝnxnは正定値対称行列 最適解はx*、最適値はf(x*)=0 ステップ幅に対する停留条件 この結果を用いると 最終的に Qの固有値をλとする 定理:最急降下法の収束性 最小固有と最大固有値の比 条件数が1に近いほどf(x)の等高線 の形が急に近くなり、大きいほど細長くなる 補題:カントロビッチの不等式(Kantrovich's inequality) 4.4.3 バックトラッキング法による最急降下法 直線探索としてバックトラッキング法を用いる最急降下法は、 実用的なアルゴリズムとして広く使われる この方法の収束度 4.5 機械学習への応用 4.5.1 座標降下法とブースティング 座標降下法の機械学習への応用 2価データが観測されたとする 新たなデータaに対する出力b∈{+1,-1}を上式の符号で予測 H(a)が正なら、出力bは+1 H(a)が負なら、出力bは-1 H1(a),...,hn(a)は{+1,-1}に値をとる基底関数 一つ一つの基底関数は単純でも、[によって複雑な関数を使っても良い 単純な基底関数を逐次組み合わせて、 高い予測精度を達成する判別器を構成する一般的な手法 関数Hx(a)の係数x=(x1,...,xn)を観測データから適切に定める データ(ai,bt)に対してbtxHHx(a)>0なら、関数Hxで正しく判定している
できるだけ多くの観測データに対してbtxHHx(a)>0が成り立つようにxを定める
損失関数(上式)を最小化する学習法が提案されている
指数損失の計算
データの重みを上式とおく
1{A}はAが真なら1、ぎなら0を撮る
最も風桶が減少する座標時つくの方法は±h1,..,±hnの中で上式を最小にする方向に対応する
アルゴリズム
図
最適化法として座標降下法を用いる学習アルゴリズム
アダブーストのアルゴリズム
ブースティング (Boosting)
一連の弱い学習機をまとめて強い学習機を生成
弱い学習機に重みをつけて付け足していく
各種ブースティングの違いは、データ点と仮説の重みづけ
AdaBoost
アダブーストは、ブースティングの代表例
Adaptive boosting
弱い分類器tをt=1からt=Tまで順に適用
それぞの分類器が正解したか否かを判定
ノイズの多いデータや異常値に影響を受ける
4.5.2 誤差逆伝搬法
2価データが観測されたとする
多層パーセプトロン(multilayer perceptron)の学習
パラメータを調整することで様々な入出力関係を表現可能
パラメータはいくつかの適当なサイズの行列W(ℓ), ℓ=1,...,L
入力aと出力bの関係は上式として定義される
bの式で表すと
関数Φiは適当な非線形関数
例
計算過程のダイアグラム
式
データから多層パーセプトンを計算する
関数Φiは、どのℓでも同じ関数𝞿:ℝ→ℝを用いて上式と定義される
目的関数を上式と定める
連鎖律は、誤差を計算するための勾配計算が必要なことから、出力層から入力そうに伝搬する
勾配を求める
多層パーセプトロンの微分
変数uを上式とする
ℓ+1層の微分から、ℓ層の微分を求められる
パラメータに関する微分
出力から入力方向に逐次分する
課題
層の数が大きいと数値誤差のため入力層に近いそうでパラメータの非有心が停滞する
確率的最適化による勾配法
二乗誤差の和f(W)を毎回更新することは困難
データを観測するたびにパラメータを更新する手法が用いられる
確率的な設定のもとで、各ステップで少数のデータのみを用いてアルゴリズムを更新するタイプのアルゴリズム
入出力データ(a,b)から 関数Φ(a,W)のパラメータWを 学習する問題を考える
時刻tでデータ(at,bt)が一つ与えられる
パラメータWを上式のように更新する
観測データ(a1,b1),..,(aN,bN)が既に彫られている状況を考える
各時刻t=1,2,...において、データの中から一様分布に沿ってランダムに(at,bt)を生成する
上式は高い確率でf(W)ノキョクショカイニシュウソクスル
memo
典型的な誤差逆伝搬法は勾配法と等価
勾配の計算に高速自動微分を用いる
事前勾配法に関連したオンライン・アルゴリズム
第5章 ニュートン法
概要
ヘッセ行列を用いる最適化法
勾配だけでなくヘッセ行列の情報も用いる計算
memo
方程式を数値計算により解くための反復法による求根アルゴリズム
対象とする方程式系に対する条件は、領域における微分方程式と2次微分に関する符号だけであり、線形性などは特に要求しない
5.1 ニュートン法の導出
ニュートン法は勾配だけではなくヘッセ行列の情報も用いる計算法
ヘッセ行列が簡単に計算できる時には、ニュートン法は効率的な最適化手法となる
2解微分可能な関数の最小化
反復法でxkまで計算が進む
点xkでfをテイラー展開すると上式となる
ヘッセ行列∇2f(xk)が正定値行列であると仮定して、 テイラー展開の2次間での式を最小にするδを求めると常識になる
Xkを上式と更新すれば、風桶が減少することが期待される
これらから探索方向とステップ幅を 上式のようにする方法をニュートン法と呼ぶ
ニュートン法の計算アルゴリズム
関数fのヘッセ行列は正定値とする
Xkは留意点い゛はないとする
ニュートン法を実際に適用するには注意が必要
上式が保証されない
定理:ニュートン法の収束性
5.2 座標変換に対する共変性
観測された実データに基づいて最適化問題を構成する時、 データの単位系を変えると、それに伴って最適化問題も変換される
最適化アルゴリズムの挙動が、座標変換とどのように関連するのか?
ニュートン法の場合は、座標変換に対して「共変的(covariant)」
最急降下法葉でない
5.3 修正ニュートン法
ニュートン法の課題を解決
コレスキー法の適用
アルゴリズム
修正ニュートン法では共変的ではない
5.4 ガウス・ニュートン法と関連する話題
概要
統計学や機械学習では、 データに対する誤差関数の和や 平均を最小にする問題がよく現れる
目的関数がm個の関数の二乗和で書く
勾配とヘッセ関数の計算
ヘッセ関数の計算が困難な時に 計算を簡略化して、効率を向上させる最適化法
ガウス・ニュートン法
レーベンバーグ・マカート法
5.4.1 ガウス・ニュートン法の導出
ガウス・ニュートン法の探索方向
ヘッセ行列を計算しなくても良い
5.4.2 レーベンバーグ・マーカート法
アルゴリズム
5.5 自然勾配法
5.5.1 フィッシャー情報行列から定まる降下方向
機械学習や統計学では、 最適化パラメータxの空間上に ユークリッド距離とは異なる距離が 自然に定義されていることがある
ヘリンジャー距離
ヘリンジャー距離の近似
xとx'が近い時
G(x):"フィッシャー情報行列の概要と関連アルゴリズム及び実装例について"で述べているフィッシャー情報行列(Fishcer information matrix)
統計学におけるパラメータ推定などで、距離構造が局所的にdG(x,x')らよって定まる空間での勾配法
最急降下法を一般化した方法
例:期待値μ、分散vの正規分布のフィッシャー情報量
パラメータxの確率密度
log(a,x)のxに関する購買を計算すると
フィッシャー情報行列は
x=(μ,v)とx'=(μ+δμ,v+δv)の間の距離dG(x,x')は
パラメータの変動に対して、分散vが大きいほど分布間の距離が小さくなる
分散が大きいほどデータから分布を見分けるのが難しくなる
パラメータ空間の距離構造がフィッシャー情報距離行列から定まるときの、最急降下法
自然勾配法は最急降下法を一般化した方法、 距離構造や目的関数によっては、 探索方向がニュートン法にほぼ一致する
5.5.2 オンライン学習における自然勾配法
自然勾配法のオンラインアルゴリズム
後で詳細を見る
第6章 共役勾配法
概要
共役勾配法は計算コストが小さく、 またメモリ領域を節約できる方法として、 大規模な問題の最適化に用いられる
memo
反復法として利用される
対称正定値行列を係数とする連立一次方程式を解くためのアルゴリズム
際急降下法より収束性に優れた最適化法
6.1 共役方向法
6.2 共役勾配法
6.3 非線形共役勾配法
memo
コメント
[…] 機械学習プロフェッショナルシリーズ「機械学習のための連続最適化」読書メモ […]
[…] 機械学習プロフェッショナルシリーズ「機械学習のための連続最適化」読書メモ […]