機械学習のための連続最適化

機械学習のための連続最適化

高度に情報化した現代社会において、データから有用な知見を得ることは、科学的に重要な発見を行い、産業・経済社会を促進する上で、極めて重要な課題となっている。今日、データは大規模化、高次元化、多様化の一途を辿っている。このようなデータを適切に扱うための基盤技術として、近年、機械学習と呼ばれる分野が勃興し、急速に発展している。統計学やデータサイエンスなど、データを扱う従来の学問分野では、主に統計的推論を適切に行うためのモデリング技術が発展してきた。

一方機械学習では、効率的な計算手法の開発により重点が置かれている点に特徴があるといえる。ビッグデータ時代を背景にして、機械学習の分野で開発された様々な手法が社会に大きなインパクトをあたえつつある。

ここでは、機械学習アルゴリズムを構成する上で欠かすことのできない計算手法である連続最適化の方法について述べる。

機械学習における連続最適化とは、ニューラルネットワークの重みやバイアスの最適化、回帰分析のパラメータ推定、SVMのパラメータ推定等の変数が実数値をとる最適化問題を解く手法となる。

連続最適化の代表的な手法には、”勾配法の概要とアルゴリズムおよび実装例について“で述べている勾配降下法、最急降下法、”共役勾配法について“で述べている共役勾配法、”準ニュートン法について“で述べている準ニュートン法、”Limited-memory Broyden–Fletcher–Goldfarb–Shanno（L-BFGS）法について“で述べているL-BFGS法などがあり、目的関数の勾配や”ヘッセ行列と正則性について“で述べているヘッセ行列などの情報を利用して、最適解に近づくように変数を更新していくアルゴリズムとなる。

また、連続最適化では、目的関数の値だけでなく、制約条件も考慮する必要がある。制約条件を考慮した最適化問題を解くには、KKT条件を満たす方法、内点法、射影勾配法、ペナルティ法、バリア関数法などの制約つき最適化問題の手法を使う。

これらの手法を適切に選択し、パラメータの最適化を行うことで、より高い予測精度やより高速な学習が実現できるが、最適化問題が非凸である場合には、初期値によっては局所最適解に陥る可能性があるため、注意が必要な場合もある。

以下詳細について述べる

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

機械学習における最適化のための基礎的理論

• 機械学習のための連続最適化 – 概要

• 連続最適化の基本事項 – 微積分・線形代数の基礎

最適化アルゴリズムを記述し、理論的性質を調べるために、微積分や線形代数の知識を利用する。ここではこれらの基本事項について述べる。まずは行列の記法を定義する。実数を要素に持つnxn行列(n次行列)の全体をℝ^nxnと表す。より一般的にはℝ^nxmはnxm次行列の全体となる。行列A∈ℝnxmの要素を明示する時にはA=(a_ij)_{i=1,…,n,j=1,…,m}のように記述し、簡単のためA=(a_ij)と書くこともある。

• 連続最適化の基本事項としての凸解析の基礎

今回は凸関数と凸集合を定義し、それらの性質について述べる。関数や集合の凸性は、最適化問題にとって訴状に重要になる。最適化問題が「凸性」を満たす時、局所的に最適なら大域的に最適であることを示すことができる。その性質を用いて、効率的な最適化アルゴリズムを設計することができる。(劣勾配、劣微分、共役関数、閉真凸関数、共役関数、強凸関数、閉真凸関数、関数値の上下界、ヘッセ行列、エピグラフ、テイラーの定理、相対的内部、アフイン包、連続性、凸包、凸関数、凸集合)

• 機械学習における連続最適化のための制約なし最適化

機械学習における連続最適化のための制約なし最適化(機械イプシロン、スケーリングを考慮しない停止条件、スケーリングを考慮した停止条件、テイラーの定理、最適化アルゴリズムの停止条件、ヘッセ行列)

• 機械学習における最適性条件とアルゴリズムの停止条件

今回は最適化問題の最適性条件のうちの反復法の停止条件について述べる。(スケーリング、影響、機械イプシロン、アルゴリズム停止条件、反復法、凸最適解、制約付き最適化問題、大域最適解、局所最適解、凸関数、2次の十分条件、2次の必要条件、1次の必要条件)

• 勾配法の基礎(直線探索法、座標降下法、最急降下法と誤差逆伝搬法)

今回は最適化問題の最適性条件について述べ、反復法の停止条件について述べる。制約なし最適化問題に対する基本的なアルゴリズムとして、直線探索法、座標降下法、最急降下法について述べる。

• 機械学習の連続最適化としてのニュートン法と修正ニュートン法

ヘッセ行列を用いる最適化法であるニュートン法について述べる。ニュートン法(Newton’s method)は勾配だけでなくヘッセ行列の情報も用いる計算法となる。ヘッセ行列が環谷に計算できるときは、ニュー新法は効率的な最適化法として有用となる。

ニュートン法を導出する。2回連続微分可能な関数f(x)を最小化するとき、反復法で天xkまで計算が進んだとする。点x_kにおいてfをテイラー展開すると以下のようになる。

• 機械学習の連続最適化としてのガウス・ニュートン法と自然勾配法

今回はヘッセ行列を用いる最適化法であるガウス・ニュートン法と自然勾配法について述べる。ガウス・ニュートン法(Gauss-Newton method)では、ヘッセ行列∇²fの第２項を省略し、点xkにおける探索方向として以下の式を用いる。

機械学習や統計学では、最適化パラメータxの空間上にユークリッド距離とは異なる距離が自然に定義されることがある。例えば標本空間Ω上の2つの確率密度関数が、パラメータx,x’∈ℝⁿを用いてp(・,x),p(・,x’)のように与えられているとする。これらの間の距離を測るとき、へリンジャー距離(Helinger distance)を用いることがある。

• 機械学習の連続最適化としての共役勾配法と非線形共役勾配法

共役勾配法はコストが小さく、またメモリ値域を節約できる方法として、大規模な問題の最適化に用いられる。最急降下法より収束性に優れた最適化法である共役勾配法について述べる。まず、凸2時間数の最適化のための方法である共役方向法と共役勾配法について述べる。次に、一般の非線形関数への拡張についていくつかの方法について述べる。

• 機械学習の連続最適化としての準ニュートン法(1) アルゴリズム概要

準ニュートン法は、ニュートン法におけるヘッセ行列の計算を回避し、効率的に最適化を行うための手法となる。今回は代表的なアルゴリズムを概観し、正定値行列空間上の幾何構造との関連を述べ、ヘッセ行列の疎性を利用する方法についても述べる。

• 機械学習の連続最適化としての準ニュートン法(2)記憶制限付き準ニュートン法

準ニュートン法は、ニュートン法におけるヘッセ行列の計算を回避し、効率的に最適化を行うための手法となる。今回は代表的なアルゴリズムを概観し、正定値行列空間上の幾何構造との関連を述べ、ヘッセ行列の疎性を利用する方法についても述べる。

• 機械学習における連続最適化での信頼領域法

信頼領域法(trust-region method)では、まず反復解の近傍で、目的関数f(x)を最適化しやすい関数m(x)で近似する。さらに、近似がよく成り立つ信頼領域を設定する。次に、信頼領域上でm(x)を近似的に最小化し、解を更新する。直線探索を用いる勾配法などでは、まず降下方向を決めてからステップ幅を決めるが、信頼領域法では、ステップ幅の上限を決めてから更新方向を決めていると解釈することもできる。

• 機械学習における等式制約付き最適化問題の最適性条件

今回は等式制約付き最適化問題の最適性条件について述べる。まず以下の最適化問題を考える。

\[\min_{x\in\mathbb{R}^n}f(x)\ s.t.\ g_i(x)=0,\ i=1,\dots,p\quad(1)\]

変数の次元と等式制約の数に関してp<nを仮定する。また、関数f,g₁,…,g_pはすべて微分可能とする。等式制約g_i(x)=0(i=1,…,p)を満たす集合は、一般に凸集合とはならない。ただし、fが凸関数でg_i(x)がすべて1次式の場合には、(1)は凸最適化問題となる。

• 機械学習における制約付き不等式最適化問題の最適性条件

不等式付き最適化問題の最適性条件について述べる。ここでは以下の最適化問題を扱う。\[\min_{z\in\mathbb{R}^n} f(x)\ s.t.\ g_i(x)\leq 0,\ i=1,\dots,p\]関数f,g1,…,gnは微分可能とする。ステップとしては、まず局所最適解に対する1次の必要条件を述べる。この条件より停留点を求めることができる。さらに局所最適解であることを確認するために、2つの必要条件と十分条件を示す。関数f,g1,…,gpがすべてpxpなら(1)は凸最適化問題となる。このとき1次の必要条件が、大域的最適解であるための十分条件になることを示す。

• 機械学習における主問題に対する最適化

制約付き最適化問題のための最適化アルゴリズムである有効制約法、バリア関数法、ペナルティ関数法について述べる。これらの方法は主に主問題に適用される。

• 機械学習におけるラグランジュ関数を用いた最適化(1)双対上昇法

制約付き最適化問題を解くには、ラグランジュ関数を用いる方法が有用となる。また、スパース正則化学習のように、たとえ制約なし最適化問題であっても線形制約付き最適化問題とみなし、ラグランジュ関数法を適用することで簡単に溶けることもある。こでは、強力なラグランジュ関数を用いた方法について述べる。

まずは双対上昇法について述べる。

• 機械学習におけるラグランジュ関数を用いた最適化(2)拡張ラグランジュ関数法

ラグランジュ関数を改良した拡張ラグランジュ関数法について述べる。”機械学習における主問題に対する最適化“で述べたペナルティ関数法やバリア関数法をうまく動かすためにはペナルティやバリアの強さckを無限大まで発散させる必要があった(ck→∞)。これは最適化問題の条件をだんだん悪化させていく。つまり少し変数を動かしただけで大きく目的関数が変化するようなことが起きることになる。よって最適化を安定されるにはペナルティの強さに応じた適切な計画が必要となる。

ここで述べる拡張ラグ楽寿関数法(augmented Lagrangian method)はこのようにペナルティを増大させる必要がない。そのため、各更新において解く内部問題の条件数が悪くなっていくことがなく、安定して最適化を実行することができる。

双対上昇法では、その主問題であるラグランジュ関数に制約を満たすことを促す作用が備わっているだけではない。そのため、その収束性を保証するには関数fが強凸性などの性質を有している必要がある。一方、拡張ラグランジュ関数は、制約式の値が0に近くなるように、通常のラグランジュ関数にペナルティ関数のようなものを足したものとして定義される。

• 機械学習におけるラグランジュ関数を用いた最適化(3)交互方向乗数法

今回は拡張ラグランジュ関数法での交互乗数法アルゴリズムについて述べる。

• 機械学習における連続最適化としての上界最小化アルゴリズム

上界最小化アルゴリズムは、目的関数を単調減少させる点列を生成する逐次解法として幅広く使われているアルゴリズムとなる。特に、目的関数を明示的に最適化することが困難な場合の解法の1つとして使われる。また、上界最小化アルゴリズムを理解することで、この枠組みに含まれる他のアルゴリズムを統一的に理解することができる。

• サポートベクトルマシンと最適化
• スパース学習
• 行列空間上の最適化