2. 線形計画と凸2次計画
2.4 凸2次計画問題
線形計画問題を拡張し、1次式で表された制約の下で凸2次関数と呼ばれる関数を最小化するような最適化問題を考える。
変数の2次関数は、次対称行列およびを用いて
と一般に書ける。もしに対してが成り立つとき、は半正定値であるといい、が半正定値であるとき、
を凸2次関数と呼ぶ。
このとき、凸2次計画を以下のとおり定式化する。
2.5 応用例
2.5.1 回帰分析と正則化
変数について、観測データとしてがあるとする。変数を変数に回帰させた回帰モデル
を考える。このときに最小二乗法で回帰係数を推定する問題を考えれば、この最適化問題は
と書ける。
ノルムを用いると、この問題は
と書ける。記述を簡単化するためにとおけば、
と書き直すことができる。この目的関数を展開すると、
が得られるが、は対称かつ半正定値であるから、この問題は凸2次計画問題の特別な場合に相当する。
任意のに対して、
であるから、確かには対称かつ半正定値である。
次にリッジ回帰を考える。観測データに対してその真の値がと書けると仮定すると、三角不等式から
が得られる。右辺第1項は最小二乗法における目的関数であったが、右辺第2項が大きければ、清のデータと予測値の差が大きくなり得ることが分かる。そのため、が大きいと右辺第2項が大きくなり得るためにデータが含む誤差の影響を受けやすいと言える。そこで右辺の両項を両方とも小さく出来ることが望ましい。そこで
と定式化()すれば、双方を抑えることを実現できる。この回帰手法をリッジ回帰という。
このように目的関数に追加の項を導入して誤差に対する予測モデルのロバスト性を高めたり予測モデルの単純さを保つことは正則化という。他にノルム正則化付き最小二乗法()
はとしてを成分として多く含むベクトルを求めたい場合に用いる。これは凸2次計画問題に帰着できる。実際、
と変形できるからである。
他にも差の絶対値の最大値(最大値ノルム)を最小化する問題
は近似問題と呼ばれる。また
も考えられ、これらはいずれも線形計画化問題に帰着できる。
2.5.2 サポートベクターマシン
データ点が与えられているとする。そして各点には2種類のうちいずれかのラベル(たとえば〇と×)が与えられているとする。この2種類のデータ点を分類するような直線(超平面)を求めたい。このような問題を2クラス分類と呼ぶ。ここではサポートベクトルマシンを導入し、それが凸2次計画で解けることを示す。
ラベルを表すダミー変数(たとえば〇ならば×ならば)とすれば、各データ点に対して条件
が成立するようにを定める。これはより簡潔に
と書ける。すなわちもし上記のまとめた条件を満たすようなが存在するならば、2種類のデータ点は超平面で分離される。この場合に線形分離可能であるという(一般にデータは線形分離可能とは限らない。)。
この条件はさらに
と置き換えることができる。実際、条件は条件
が成立することと同値だが、これはおよびを合貯めてと置き換えればその条件を得る。この条件下において、境界面から最も近い点までの距離をマージンという。
この問題はマージンをなるべく大きく出来るのが望ましい。ここでの大きさがであることから、マージン最大化は最小化と同値である。したがってサポートベクトルマシンは、
というを決定係数とする凸2次計画問題に帰着できる。
他方でデータが線形分離可能でない場合、上記の最適化問題は実行可能解を持たない、すなわち誤分類されるデータ点が必ず存在する。誤分類の程度は小さく、かつ正しく部類されるデータ点に関するマージンは大きい境界面を求めることが目的になる。この目的のためには、誤分類されたデータ点について、制約
を違反した程度に応じてペナルティを課す。たとえば、
と定義すると、は制約を満たすとそうでない場合に正の値を取る。このようにして違反することを抑える働きをする。これは最適化問題
を解くことで実現できる。
なおこの問題は
と変形できる。これはを決定変数とする凸2次計画問題である。
3. 凸計画
- 線形計画問題や凸2次計画問題を含むより一般的な枠組みとして凸計画がある。
- 凸計画問題では任意の局所最適解が大域的最適解であるという性質がある。
3.0 数学的準備:勾配ベクトルとヘッセ行列
以降の議論で用いるために、数学的な準備をする。
集合で定義されたがで微分可能であるならば、に対して
が成り立つ。ここで
と表し、は
を満たすものとする。
更にがで2回微分可能ならば、に対して
が成り立つ。ここでは
を満たす。
を変数とするがにおいて微分可能ないし2回微分可能であるとは、その成分の実数値関数
がそれぞれにおいて微分可能ないし2回微分可能であることを意味する。
以上を踏まえて、勾配ベクトル、ヘッセ行列およびヤコビ行列を定義する。
定義3.1 勾配ベクトル、ヘッセ行列およびヤコビ行列 に対して、
をそれぞれの勾配ベクトルおよびヘッセ行列という。特にが2回微分可能かつそれらの導関数が連続であれば、ヘッセ行列は対称である。
また に対して、
をヤコビ行列という。
これらの計算上の性質について簡単にまとめておく。
定義3.2 勾配ベクトルとヘッセ行列の性質 が与えられたとき、変数ベクトルに関する勾配ベクトルおよびヘッセ行列について、以下が成り立つ。
として定義に則り計算する。
である。また
について、
が成り立つ。
更に
である。 )
例:勾配・ヘッセ行列
関数の点における勾配とヘッセ行列を求める。
まず勾配とヘッセ行列の各成分を定義により求めるとである。したがって点における勾配とヘッセ行列は
である。
参考文献
*1:なお最適化に影響しないため、とおいた。