機械学習プロフェッショナルシリーズ「機械学習のための連続最適化」読書メモ

サマリー

機械学習における連続最適化とは、ニューラルネットワークの重みやバイアスの最適化、回帰分析のパラメータ推定、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
共役勾配法 - Qiita


はじめに

この記事は「これなら分かる最適化数学 -基礎原理から計算手法まで-」(金谷健一著,共立出版)の3.3「共役勾配法」を基に書いている。また、自主ゼミで担当した回に向けての内容になっているため、一部「前回の内容で説明済」と...
qiita.com
一変数勾配法
N変数のばあい
共役勾配法
共役とは
「共役」とは「直交」の概念を拡張したものである
説明
正値対称行列Qに対して ベクトルx,yが(x,Qy)=0を満たすとき、 x,yをQに関して互いに共役という。
ヘッセ行列の計算回避
ヘッセ行列は、２階偏微分を含む行列であるため、その計算をしていては、コストがかかる。これを回避するためにいくつかの方法が存在する。

第7章　準ニュートン法

概要

非線形連立方程式の解、あるいは連続最適化問題の関数の極大・極小を見つけるためのアルゴリズム
ニュートン法におけるヘッセ行列の計算を回避し、効率的に最適化を行う方法

7.1 可変計量を用いる最適化法とセカント条件

7.2 正定値行列の近接的更新

7.2.1 ダイバージェンス最小化による更新則の定式化
7.2.2 ダイバージェンスの性質と更新則の関係
7.2.3 距離最小化とダイバージェンス最小化
7.2.4 更新則の導出

7.3 準ニュートン法の収束性

7.4 記憶制限付き準ニュートン法

7.5 ヘッセ行列の疎性の利用

7.5.1 関数のグラフ表現
変数間の関係をグラフ理論の用語で表現
部分グラフの全ての頂点間に枝が貼られている時クリーク(clique)、または完全部分グラフ
極大クリーク
コーダルグラフ
7.5.2 正定値行列補完
7.5.3 疎クリーク分解による更新則
memo
主に無制約最小化問題を解くための手法の一つである．手法の概要はニュートン法と同 様である．ただし，目的関数equationの点equationでのヘッセ行列equationを用いるの ではなく，ヘッセ行列の近似行列equationを用い，equationという方程式を解くことに より探索方向を求めるという点が異なる．なお，方程式を解くかわりに，equationとし 点equationでのヘッセ行列の逆行列の近似行列equationを用いて探索方向を直接求める こともある． 近似行列equation，equationの更新方法に関しては，セカント条件を満たす更新公式で ある BFGS 公式や DFP 公式が良く知られている．

第8章　信頼領域法

概要

信頼領域
数理最適化の文脈で用いられる用語、目的関数をあるモデル関数(多くの場合二次関数)で近似することが妥当である、と仮定する部分領域
信頼領域法
直線探索法と双対

8.1 アルゴリズムの構成

8.2 部分問題の近似解法

8.2.1 部分問題の最適性条件
8.2.2 ドッグレッグ法

8.3 収束性

memo
制約なし最適化問題を解く勾配法の1つ. ヘッセ行列が正定値でなくてもニュートン法が大域的収束するように工夫された解法であるが, 準ニュートン法や制約付き最適化法の枠組みにも拡張されている. k\, 回目の反復での近似解 x_k\, が与えられたとき, 目的関数の2次近似が妥当であると思われる信頼領域でその2次近似を最小化するステップ s_k\, を求める. そして関数の減少量に基づいて, 信頼領域の大きさを調節したり, x_{k+1}:=x_k+s_k\, と近似解を更新したりする.

第Ⅲ部　制約付き最適化

第9章　等式制約付き最適化の最適性条件

9.1 1次の最適性条件

9.2 2次の最適性条件

9.3 凸最適化問題の最適性条件と双対性

9.4 感度解析

第10章　不等式制約付き最適化の最適性条件

10.1 1次の最適性条件

10.2 2次の最適性条件

10.3 凸最適化問題の最適性条件

10.4 主問題と双対問題

第11章　主問題に対する最適化法

11.1 有効制約法

11.1.1 探索方向の選択
11.1.2 ラグランジュ乗数の符号
11.1.3 有効制約式の更新と最適化アルゴリズム

11.2 ペナルティ関数法

11.2.1 ペナルティ関数を用いた定式化
11.2.2 ペナルティ関数法における制約なし最適化問題の性質
11.2.3 正確なペナルティ関数法

11.3 バリア関数法

11.3.1 バリア関数法を用いた定式化
11.3.2 バリア関数法の性質

第12章　ラグランジュ関数を用いる最適化法

12.1 双対上昇法

12.1.1 ラグランジュ関数の導入と双対問題の導出
12.1.2 双対問題の勾配法による最適化
12.1.3 双対分解
12.1.4 不等式制約に対する双対上昇法
12.1.5 双対上昇法の収束
12.1.6 非線形制約の双対上昇法

12.2 拡張ラグランジュ関数法

12.2.1 拡張ラグランジュ関数
12.2.2 拡張ラグランジュ関数法
12.2.3 双対上昇法としての拡張ラグランジュ関数法
12.2.4 不等式制約の扱い
12.2.5 拡張ラグランジュ関数法の収束理論
12.2.6 凸目的関数における収束レートの理論
12.2.7 近接点アルゴリズムとの関係

12.3 交互方向乗数法

12.3.1 交互方向乗数法のアルゴリズム
12.3.2 交互方向乗数法による並列計算

第Ⅳ部　学習アルゴリズムとしての最適化

第13章　上界最小化アルゴリズム

はじめに

目的関数を単調減少させる点列を生成する逐次解法
目的関数を明示的に最適化することが困難な場合の開放の一つ

13.1 上界最小化アルゴリズム

目的関数を単調減少させる点列を生成する逐次解法の一般的な枠組み
期待値最大化(EM)アルゴリズム(expectation-maximization algorithm) もMMアルゴリズムの枠組みの一つ
確率モデルのパラメータを最尤推定する有名な手法の一つである
定義:方向微分と停留点
停留点は、極値点や最大値・最小値をとる点とはならない
最小化問題(上式)を考える
f(x)を直接解くのが難しい設定を考える
MMアルゴリズムは、この最小化問題を直接特代わりに f(x)の近似関数の最小化問題を逐次的に解くことで 解候補点列を生成するアルゴリズム
具体的な求め方
T番目の解候補点xiのまわりでの 目的関数f(x)の近似関数をu(x;xi)とした時
t+1番目の解候補点xt+1を上式として求める
最適化問題minx∈Xf(x)を 解くために近似解uが持つべき条件
条件続き
上記の条件を満たすuを 代理関数(surrogate function)とよぶ
代理関数を用いて 優越化(majorization)と最小化(minimization)の 2つのステップを繰り返すことで 解候補点列を生成するアルゴリズム
MMアルゴリズムの動作例
MMアルゴリズム
MMアルゴリズムの性質
定理:MMアルゴリズムの単調減少性
定理:MMアルゴリズムの収束性

13.2 代理関数の例

代理関数を求めるための代表的な方法
具体的には、代理関数を求めるために用いられるいくつかの不等式を提示
線形化の利用
h(x)を1回微分可能な凸関数とする
定理2.12より、上式が成り立つ
-h(x)とすることで代理関数を構成できる
二次近似の利用
h(x)を2回微分可能でヘッセ行列が有界である凸関数とする
Mを正定値行列として、M-∇2h(x)が任意のxに対して非負定値行列ならば上式が成り立つ
イェンセンの不等式の利用
h(x)を凸関数とする
確率変数Xに対して、 上式のイェンセンの不等式(Jensen's Inequality)が成り立つ
EMアルゴリズムを導出するときに用いる

13.3 EMアルゴリズム

はじめに
潜在変数(latent variable)と呼ばれる 観測できない変数を含む統計モデルの 最尤推定(maximum likelihood estimation) を行う代表的なアルゴリズム
パラメータの最尤推定を負の対数尤度の最小化とみなすことで
MMアルゴリズムの枠組みで導出できる
EMアルゴリズムの説明
前提条件
観測データをy1:n=(y1,...,yn)とする
Θをパラメータとする確率モデルp(x|θ)を考える
最尤推定は上式となる
観測データ点yiごとに潜在変数ziを仮定する
負の対数尤度に対する上界の計算
u(θ;θt)は上式となる
EMアルゴリズム
Θtが与えられた元でのz1:nの 事後分布p(z1:n|y1:n, θt)を計算し、 u(θ;θt)を導出する
代理関数を求めるステップ
u(θ;θt)の最適解θを求める
尤度の最大化を意味する
代理関数の最小化を得ステップ
E,Mを繰り返す
潜在変数は目的関数-logp(y1:n|θ)の最適化のために 代理関数を構成するために導入された補助変数

13.4 2つの凸関数の差の最適化

関数f(x)が、1回微分可能な凸関数g(x), h(x)を用いて常識のように書けるとする
関数f(x)は、h(x)が一次関数でなければ非凸な関数となる
このようなf(x)の最小化問題
定理:DC計画問題への変換
非凸な関数の最適化で非常に重要
DC計画問題の解法
∇g(xt+1)=∇h(xt)を満たすような解候補点{xi}を生成することで
目的関数f(x)を単調に減少させ、停留点を見つけることができる
CCCPのMMアルゴリズムの観点からの分析
f(x)の線形性を用いて、f(x)の代理関数として上式を導出
DC計画問題に対して、右式を繰り返し最小化する方法

13.5 近接点アルゴリズム

f(x)を凸関数として、最小化問題は上式と等価になる
f(x)+1/2c∥x-y∥2がxに関して強凸関数になるため
凸関数の最小化問題を強凸関数の最小化問題として解くことができる
近接点アルゴリズムは上式の更新を繰り返すことで、 目的関数の最小化を得アルゴリズム
代理関数を上式としたMMアルゴリズムと同じ

第14章　サポートベクトルマシンと最適化

14.1 SVMの定式化と最適化問題

はじめに
ハードマージンSVMとソフトマージンSVM
SVMの線形分類境界
Wは線形分類境界の係数ベクトル
Bはバイアス
SVMは訓練データにより最適なwとbを求める最適化問題
14.1.1 SVMの主問題
ソフトマージン最大化に基づく線形SVMの最適化問題
それぞれ、正則化項と損失項
損失関数はヒンジ損失(hinge loss)と呼ばれる
0-1損失は非凸で不連続な関数なので、そのまま最適化できない
ヒンジ損失は0-1損失の代理の損失関数
ヒンジ関数は凸関数なので、最適化できる
ただし、ヒンジ関数はyif(xi)=0において微分できない
対処のための2つのアプローチ
制約なし最適化問題を制約つき最適化問題に変換する
人工的な変数(スラック変数)を導入することで制約つき最適化に変換する
ヒンジ損失
2つの区分を持つ区分線形関数として表される
N個の人工変数を要素にもつベクトル𝝃=(𝛏1,𝛏2,...,𝛏n)を導入すると微分可能な制約付き最適化問題に変換できる
ヒンジ損失を微修正して滑らかな損失関数にする
二乗ヒンジ損失
フーバーヒンジ損失
バニラヒンジ損失
ロジスティック回帰
14.1.2 SVMの双対問題
双対問題の導出
制約つき最適化問題のラグランジュ関数
双対問題の目的関数
ラグランジュ変数α,μの非負制約のもとで双対目的関数を最大化する問題
ラグランジュ関数は主変数w,b,𝝃に関して凸
主変数に関して偏微分をして0となる点で最小となる
SVMの双対問題
14.1.3 SVMの最適性条件
SVMの特徴の一つは、 分類境界が全ての訓練事例に依存して決まるのではなく、 サポートベクトル(support vectorz9と呼ばれる 一部の事例に依存して特徴付けられる
SVMの最適性条件を整理すると、双対変数α1,...,αnとSVとの関係が明らかになる
事例集合とマージンの関係
マージン(yi(wTxi+b)が1より大きな訓練事例は、 対応する双対変数αが0となるので、 分類境界に影響を与えない
非SVを取り除いても最終的な分類協会は変わらない
14.1.4 カーネル関数を用いた非線形モデリング
SVMの特徴の一つは、カーネル関数を用いた非線形モデリングができること
入力xを何らかの特徴空間Fへ写像する関数Φを考える
このΦ(x)を新たな特徴ベクトルと解釈したときの線形分類協会
係数ベクトルwも特徴空間Fの要素として定義することに注意
双対問題でxをΦ(x)にすると
分類境界の双対表現
双対問題と分類境界で、特徴Φ(x)ガ単独ではなく内積Φ(x)TΦ(x)の形で現れる
内積をカーネル関数として定義
ある性質を満たす関数を用いると、Φ(x)を使わずに直接内積が求められる
RGF(radial basis functionカーネル
カーネル関数での表現

14.2 SVM学習のための最適化アルゴリズム

はじめに
SVMの学習特化した最適化アルゴリズム
LIBSVM,LIBLINEARで使われている
SMO(sequential minimization optimization algorithm)アルゴリズム
二乗ヒンジ損失
DCDM(dual coordinate descent method)アルゴリズム
フーバーヒンジ損失
14.2.1 カーネル SVMの双対問題の解法: SMOアルゴリズム
SVMの双対問題はn個の未知変数α1,..,αnに関する最適化問題となっている
訓練事例数nが大きくない時は、制約つき最適化の汎用的なアルゴリズムを利用して双対問題を解くことが可能
Nが大きいと膨大なコストがかかる
アプローチ
最適化されるn個の変数のうちの一部 (作業集合(working set))だけを考え、 残りの変数を定数として固定する
集合のサイズを2とした分割法
変数が2つしかない最小規模の最適化問題 (minimal optimization)を繰り返し解く
N個の変数のうち、 ある2つαsとαtのみを変数とみなし、 残りを定数として固定した双対問題を考える
双対変数をβi=yiαiとする
変数β1,...,βnを用いるとSV分類の双対問題は上式となる
Kij=K(xi,xj)
変更する2つの双対変数の添字をs,tとすると
等式制約(和がゼロ)満たすには
∆βt=-∆βs
実質上動ける変数はβs
双対問題を∆βsに関する制約つき最適化問題として書き直すと
上式は1変数∆βsの制約つき2次関数最小問題
二次関数の極値を上式とする
最適解は
2つの変数をランダムに選んでも良い
14.2.2 線形SVMの双対問題の解法: DCDMアルゴリズム
線形SVMに特化とた最適化アルゴリズム
定数項bのない分類境界を考えた場合の主問題
双対問題
双対問題の変形
DCDMアルゴリズムは、SMOアルゴリズムと同じく分割法の一種
SMOアルゴリズムでは等式制約があったので2つの変数からなる作業集合を考えた
DCDMでは等式制約がないので、一つのαsを更新する
DCDMのあるステップで、αsのみを変数とみなし、残りを定数みなして固定する
双対問題を更新幅∆αsに関して整理する
1変数∆αsに関する制約つき2時間数最小化問題
二次関数の極値
最適解
DCDMでは作業集合の選択を、n個の変数α1,...,αnを順番に作業集合として、解く過程を繰り返す
14.2.3 学習アルゴリズムの比較
SVMに特化したDCDM法と汎用的な信頼領域法、記憶制限つき準ニュートン法の比較
微分が必要なのでフーバーヒンジ損失を使う
フーバーヒンジ損失SVMの主問題
双対問題
比較に用いた実験データ
実験結果1:小規模データ
実験結果2:中規模データ
実験結果3:大規模データ

14.3 正則化パス追跡

はじめに
ハイパーパラメータ
例:損失関数と正則化項のバランスを制御するための正則化パラメータC
ハイパーパラメータの適切な選択が必要
ウォームスタートを使うことで効率的にモデル選択ができる
ハイパーパラメータの値が異なる複数の最適化問題を解く場合
ある最適化問題の解を初期値として利用することで、 別の最適化問題の解を効率的に得ることができる
正則化パス追跡 (regularization path following)
複数の最適化問題をまとめて解くことができる
正則化パラメータCが連続的に変わる時に最適解がどのように変化していくかを厳密に計算できる
パラメトリック最適化(parametric programming)と呼ばれるアプローチの一つ
パラメータ表現された最適化問題のクラスを考え、 それらの最適解をパラメータを含んだ形で得ようとするもの
双対問題の最適解を正則化パラメータCの関数として求めるため
正則化パス追跡は、最適性条件が重要な役割を示す
3つの事例集合がCに依存して 変わることを強調するため上式のように表現する
3つの事例集合は常識のように表現される
正則化パス追跡アルゴリズム
14.3.1 最適解のパラメータ表現(ステップ1)
事例集合T(C)が一定であるようなCの区間を考える
14.3.2 イベント検出(ステップ 2)
正則化パラメータCを徐々に増やした時、事例集合T(C)が変化するイベント

14.4 最適保証スクリーニング

MとIに属する事例集合をサポートベクトル(SV)
Oに属する事例集合を非サポートベクトル(非SV)と呼ぶ
Oの事例はαi=0であるため、除いても結果は変わらない
多くのSVMでは、ヒューリスティックを用いて非SVとなる事例を推定して、残りで最適化問題を解く
最適保証スクリーニング (safe screening)
非SVとなる事例を見つける
最適保証スクリーニングの例
基本的な考え方
最適化問題
勾配ベクトル
マージンが1より大きければ、 その事例は非SV(Oに含まれる)
最適解w*がわからない状態でどうするのか?
最適解が存在する範囲がわかっている状況を考える
最適解w*がΩに含まれる時、 マージンの下界が1より大きいければ、 その事例は非SVとなる
最適保証スクリーニングを 実現するための2つの課題
領域Ωが得られた時、最小化問題をいかに効率的に解くか?
最適解w*を含む領域Ωをいかに得るか?
領域Ωが超球出会った場合の、最小化問題アプローチ
超球
定理:線形スコアの下界と上界
超球に解w*が含まれているときのηTw*の下界と上界
η=yixiとするとマージンの下界を得ることででき 上式のような非SVの判定を行える
どのようにΩを見つければ良いか
定理:近似回を用いた最適解を含む超球
超球Ωの中心と半径が、任意のベクトルὥに依存する
Ὢを近似解と呼ぶ
どのような近似解を用いれば超球の半径が小さくなるのか?
近似解ὢが十分に最適解に近い時は半径r(ὢ)が小さくなる
近似解ὢとして最適解w*に近いものを選ぶことができれば
上界と下界がタイトになり
多くの非SVを安全に同定できる
とのように近似解を求めれば良いのか?
最適化アルゴリズムの途中で得られる解を近似解とする
最適解を解く途中で、非SVとなる事例を同定し、それを訓練データから取り除く
同様のの考え方の適用
訓練データが逐次に与えられる逐次学習、オンライン学習、ストリーミング学習
訓練データに変更が加わる前の最適解を近似解とみなす
変更後の最適解の非SVをスクリーニングできる
モデル選択における、 複数の正則化パラメータCに対する最適化問題
ある正則化パラメータに対する最適解を 別の正則化パラメータに対する最適化問題の近似解とみなす
定理:正則化パスのための最適化保証スクリーニング
最適保証スクリーニングの研究
El Ghaoui(17)
2016年で盛んに研究が行われている

第15章　スパース学習

15.1 スパースモデリング

スパースモデリングのような低次元部分空間を取り出す方法は、 統計学では古くからモデル選択として用いられてきた
モデル選択を行う基準
赤池情報基準 (Akaike's Information Criterion,AIC)
前提条件
統計モデル{pθ|θ∈Θ}が与えられている
Θはパラメータの集合
Pθはパラメータθに対応する確率密度関数
Θに含まれるk次元部分モデルの列Θk⊆Θ{k=1,2,...,d)があるとする
目的: このモデルの中から「適切な」モデルを選ぶ
最も次元の大きいモデルが一番高い表現力を持つが、 モデルが複雑すぎると過学習を起こす
AICは
予測誤差(汎化誤差)と訓練誤差のギャップを補正して過学習を避ける基準
モデルϴkのAICは上式となる
Θkをモデルϴにおける最尤推定量とすると、 n個の観測データ{z1,z2,...,zn}に対して
AIC(k)は期待対数尤度の漸近不偏推定量になる
AICはモデルの「複雑さ」として 次元に対する穂ペナルティ2kを足すことで 訓練誤差を補正したもの
AICを最小化することで予測誤差を近似的に最小化する
AICはモデルの次元を正則化項に用いた正則化学習とみなせる
損失関数が劣モジュラ性を満たしていると、貪慾ほうで計算できる
ベイズ情報量基準 (Bayes Information Criterion, BIC)

15.2 L1 正則化と種々のスパース正則化

15.2.1 L1 正則化
AICに変わる簡単な最適化問題で定式化れるスパースモデリング手法
L1正則化は∥・∥0の代わりに、L1ノルム∥θ∥1=∑|θj|を用いる
Cは正則化パラメータ
正則化パラメータは、交差確認法や情報基準などで決定する
L1ノルムはL0ノルムの[-1,1]dにおける凸包であることが知られている
最適解は実際にスパースになる
例:スパースな回帰:Lasso
二乗損失を用いたL1正則化学習を回帰に適用したもの
Lassoの推定量は最適化問題(上式)の解として与えられる
例:スパースな判別:L1正則化ロジスティック回帰
回帰と同様にして、判別にもL1正則化は適用可能
損失関数をロジスティック損失とすると上式のように定式化される
15.2.2 その他のスパース正則化
損失関数ℓ(z,w)を用いて、一般化した問題
損失関数ℓがwに関して凸ならば、 この最適化問題は凸最適化問題となる
∥w∥1は滑らかではなく、微分を計算できない
劣勾配法を当てはめることはできるが、収束が遅くなる
L1正則化は滑らかでないために解がスパースになる
解決するための指針
正則化項の構造を用いる
L1正則下の場合は、変数ごとに関数が分離していることを利用する
損失関数項と正則化項で最適化の難しさを分離する
あたかも正則化項がなかったような形で最適化を実行する
一般化の式
スパース正則化関数Ψ(w)
f(w)=∑ℓ(zi,w)とする
L1以外の正則化項
例:トレースノルム正則化
低ランク行列を学習するために用いられる正則化法
トレースノルム正則化 (trace-norm regularization)
B=(WTW)1/2はBB=WTWを満たす半正定値対象行列
トレースノルム正則化は特異値の和
特異値を並べたベクトル(σ1,σ2,...,σr)にL1正則化を欠けたもの
トレースノルム正則化を用いて学習した行列は、 特異値がスパース(多くの特異値が0になりやすい)性質がある
特異値の多くが0
例:グループ正則化
前提条件
D個のインデックス{1,...,d}がK個のグループG1,...,Gkに分けられるとする
グループGkは重複しても良い
各グループGkに対応する部分ベクトルをwGk=(wj)と書く
このグループ分けに沿ったグループ正則化(group regularization)は上式で与えられる
q>1
∥wGk∥q=(∑|wj|q)1/q
グループ正則化は各グループに対応する部分ベクトルのLpノルムを並べたベクトルへのL1正則化
例:エラスティックネット正則化
L1正則化とL2正則化の間をとったような方法
式
L1正則かと比べてノイズに左右されにくい安定した学習ができる
15.2.3 L1 正則化の数値的評価
人工的なデータで実験
次元p=2000
上式の線形モデルからデータを生成
Xはランダムに生成したデザイン行列
Εは独立同一な標準正規分布に従う雑音
w*はtのベクトル(最初の100成分のみ0怒和で、残りは0なスパースなベクトル)
サンプルサイズをn=1000,2000,4000でカイの挙動と推定誤差を見る
結果
サンプルサイズが小さくてもLassoの推定誤差があまり大きくならない
Lassoは変数選択を行なって必要なデータで推定をしているから

15.3 近接勾配法による解法

15.3.1 近接勾配法のアルゴリズム
正則化項の構造を利用する方法
最急降下法を少し修正した方法
アルゴリズム
ISTA(Iterative Shrinkage Thresholding Algorithm)
関数fをwkの周りで 線形近似f(w)≃f(wk) + gkT(w-wk) して最適化
微分をとったwkの周りでしか近似精度は良くない
そこまで遠くに行かないように近接項ηk/2∥w-wk∥2が足される
近接勾配法の更新式は上式となる
近接勾配法は最終的に上式となる
関数Φに付随する近接写像を上式とする
Wk-gk/ηkは関数fを最小化するための最急降下法の更新式そのもの
近接勾配法は、最急降下法で1回fを小さくしてから、Ψで決まる近接写像で補正する
近接勾配法の計算効率は正則化項Ψで決まる近接写像の計算複雑さで決まる
例:L1正則化
L1正則化に対する近接写像は、y=prox(q|c∥・∥1)とすると
ソフト閾値関数(soft thresholding)と呼ばれる
例:重複なしグループ正則化
例:トレースノルム正則化
例:正則化項がない場合
近接勾配法の更新式は、最急降下法となる
例:標示関数
続き
15.3.2 近接勾配法の収束理論
近接勾配法の収束レート
実際の応用では関数fの滑らかさLを直接計算することは難しく、 バックトラッキング法でLを探索する
アルゴリズム
FISTA(Fast ISTA)アルゴリズム
近接勾配法における加速法の収束レート
強凸関数に対する近接勾配法アルゴリズム
リスタート法
15.3.3 近接勾配法の収束レートの証明

15.3.4 近接勾配法の数値実験

人工データでの実験
サンプルサイズn=700
次元をp=1000
データ生成式
最初の100成分だけ値をもち、残り900は0
最適化問題
損失関数はメジスティクス損失とする
目的関数の収束度合いを示した図
Nesterov(restart)が最も良い
汎化ごさと非ゼロ成分の数
Nesterov(restart)が最も良い

15.4 座標降下法による解法

スパース正則化学習には座標降下法も有効
座標降下法は座標ごとの非セフ戦の計算が軽く、 また正則化項がブロックに分離されている場合に有効
座標降下法は、 一つ一つの座標(もしくは座標のブロック)を 交互に目的関数が小さくなるように更新する
多くのスパース正則化関数は、 座標(もしくはブロック)ごとに分かれた関数の和として表せる
例
L1正則化は座標ごとに絶対値をとってから足す構造
グループ正則化も、各座標のグループごとに関数が分離されている
座標ごとに分かれた構造を表した式
アルゴリズム
座標の選び方
ランダムに選ぶ
循環して選ぶ
難しい

15.5 交互方向乗数法による解法

15.5.1 交互方向乗数法と構造的正則化
損失関数の最適化と正則化項の最適化を分ける
例:重複ありのグループ正則化
グループ正則化
例:一般化フューズド正則化
グラフに沿った正則化
交互方向乗数法は拡張ラグランジェ関数をxとyを交互にうごかして最適化する方法
最適化問題における拡張ラグランジェ関数
拡張型の交互方向乗数法アルゴリズム
例:Lassoの交互方向乗数法による開放
例:凸関数の和であ世話される正則下の交互方向乗数法による開放
15.5.2 画像復元の数値実験
TV雑音除去の例
真の画像は滑らかで、隣接ピクセル間では大きな変化がないという仮定
TV正則化を用いたぼかしと雑音の除去

15.6 近接点アルゴリズムによる方法

15.6.1 スパース学習における近接点アルゴリズムとその双対問題
スパース正則化の最適化では、近接点アルゴリズムも有用
双対問題を解くための2つの定理
定理:共役関数の性質
定理:近接写像の性質
モーロー分解(Moreau decomposition)
モーロー分解により近接写像の計算を共役関数に関する近接写像の計算に置き換えられる
双対問題を最適化するために、最急降下法やニュートン法を使う
主問題における近接点アルゴリズムは、双対問題では線形等式制約つき最適化問題を乗数法で解くことで実行できる
主問題では滑らかでなかった正則化関数が双対問題では平滑かされる
双対拡張ラグランジュ関数法のアルゴリズム
フェンシェルの双対定理を用いることで、 双対拡張ラグランジュ関数法は直接的に導出できる
15.6.2 双対問題における交互方向乗数法
双対問題の拡張背グランジュ関数をy,uについて交互に最適化
正則化学習における双対交互方向乗数法

第16章　行列空間上の最適化

16.1 シュティーフェル多様体とグラスマン多様体

16.2 機械学習における行列最適化

16.2.1 独立成分分析
16.2.2 次元削減付き密度比推定

16.3 多様体の諸概念

16.4 多様体上の最適化

16.4.1 最急降下法
16.4.2 共役勾配法

16.5 レトラクションとベクトル輸送

16.6 行列多様体上の最適化

16.6.1 シュティーフェル多様体の性質
16.6.2 レトラクションの構成
16.6.3 射影によるベクトル輸送
16.6.4 数値例