*注意)この「べじぱみゅの学習メモ」のカテゴリー記事は、ワタクシ自身がこれまでに勉強したいろいろな項目について、テキストにあんまり書いてない内容などを勝手に妄想したメモです。
ワタクシ自身の備忘録のために書いており「初学者にわかりやすく説明する」というものではございません。
導入なしに唐突に話が始まり、おそらく意味不明な文章かもしれません。
しかし、せっかく考えたことなので、記事の内容がもし誰か1人でもお役に立てれば幸いです。

「2次計画法」が大事!


「ある制約のもとで、ある関数を最小化する」
という問題は科学技術のあらゆる領域で目にします。今回の「最小化」の対象は、前回の最後に述べた「理論値と実験値との偏差の 2 乗」です。

そして「制約」についてですが、まずは「非負制約」です。濃度なので当然ながらマイナスの値にはなれません。そして「」も縛ります。実はこの辺の縛り方にはいろいろディープな要素があるのですが、今回は最も単純に「それぞれの深さにおいて、全元素の濃度の和は 1」という縛りをかけます。こうすることで深さごとの I 種類の元素に関する「相対濃度」が得られます。 
 
この問題は「数理計画法」の一例なのですが、その中でもとくに「2 次計画法」がよく使われます。なぜ 2 次なのか、というところですが、2 次関数は

最も単純な「非線形関数」である
扱いが比較的容易(難易度的には実質、線形関数とほぼ変わらない)

という特徴があります。一般の非線形関数を近似するのにもただの線形ではさすがに粗すぎるけども 2 次関数なら少なくとも局所的にはほどよく近似できちゃうことが多く、2 次関数の最小化手法である 2 次計画法は理論的にも応用的にも極めて重要なのです。
 
さて、そんな 2 次計画法のなかでも最も単純だけど応用範囲の広い問題を考えていきます。ここでは次の形の関数を考えます。  
2次計画法の対象関数
変化させる変数の数を n 個とします。ベクトル x はその n 個の変数を並べたものです。Q は n 行 n 列の行列で関数の 2 次の部分を表し、c はn 行ベクトルで関数の 1 次の部分を表すものです。

このまま一般の 2 次関数として進めてもいいのですが、Q は「正定値対称行列」とします。「対称」はまさに対象行列のことで、「正定値」は直感的に言うと「任意のベクトル x に対して xQx が正になる」です。かなり強い縛りにも聞こえますがですが、多くの応用問題では Q は正定値対象行列なので、これはそれほど大きな縛りではありません。ちなみに今回の ARXPSデータ理論値に関しても、そもそも 2 次の部分は「d’の 2 乗」に相当する部分であり、まさにどんな x に対しても正になります。
 
ARXPSに当てはめる

この形式を先ほどの ARXPS の件に当てはめると
Qとcの内訳
こうなります。Q に何やら余計な項がついていますが、これは「
正則化」です。今回述べる方法は行列 Q に逆行列が存在することが必要となります(それが必要ない手法もあるのですが、今回の手法はその縛りを補って余りあるものです)。

実は S^TS は逆行列が存在しないか、極めて不安定なのです。これは「未知数より縛りの数が少ない」ことに関連しており、もしこれが逆ならちゃんと逆行列が存在します。とにかく、逆行列をムリヤリ存在させるため、n 行 n 列の単位行列 E を「ちょっとだけ」足しておきます(ε=0.001 とか)。こうすることで基本的に Q は安定して逆行列をもつようになります。

なお、以前の記事でお話したように、ここでεを大きくしすぎてしまうともともとの「偏差の 2 乗和を最小化」という命令が薄れ「x の 2 乗和を最小化する」ことに重きがおかれるようになります。あえてそうしたい場合もありますが、ここではあくまで「偏差の 2 乗和の最小化」だけを考えます。
 
そしてパラメータ行列 x に関する「縛り」としては
等式制約

まずこの等式制約を課します。今回のケースだと行列 A を 

「和が1」の等式制約

のように K 行 K 列単位行列を横に I 個並べたものに設定しベクトル b を「全部 1」にすれば、「それぞれの深さごとに合計が 1」という縛りになります。さらに

不等式制約
この非負制約を課します。不等式制約は一般の線形関数縛りにしても手間はそれほど変わりませんが、今回の問題を含め実際のケースでは単純に「非負だけ」が最もメジャーな縛りなので、これでいきましょう。
 
2次計画法で扱う、上記の問題に関する
ラグランジュ関数

ラグランジュ関数

こうなります。そして一般的な数理計画法のテキストにある、「最適な x」(縛りを満たす中で対象関数を最小にするx)が満たす「
KKT 条件」は以下の 5 つです。最終的にこれを満たすx, y, z ベクトルを得ることを目指します。

KKT条件

これを解く(上記 5 条件を満たすベクトルを探す)方法はいくつかあります。代表的なのは非線形方程式に関するニュートン法に基づくもので、ある初期値を決め、そこから対象関数が減少する方向にちょっとずつじりっ、じりっと調整を重ねていくものです。

直感的にわかりやすい方法で比較的万能ではあるのですが、大域収束しにくいなどいろいろと問題はあります。今回のメインではないのでここではお話しません。 次回もっとエレガントな方法を取り上げます。



はっぴぃ理系らいふ、いぇい
ヽ(・ε・)人(・ε・)ノ キミモナカマニナロウゼ
   

【文責 べじぱみゅ