#9 The concave-convex procedure

Yuille, A.L., Rangara jan, A.
Neural Computation 15(4) (2003) 915–936

ちょっと間が空いてしまったけど、継続しますよ。今日の話題は最適化に関するところ。最適化を勉強したいわけじゃないんだけど、[1]を読むためにはこれを避けては通れないので読んでおきます。この辺でも出てきてますね。SVMは二次最適化問題に帰着できるので、既存のソルバーを使って大域的最適解を得ることができますが、半教師ありに拡張すると凸ですらなくなってしまうので最適化が困難である、さてどうしよう?というようなモチベーションで読んでいくとよい感じ。

基本的な枠組み

重要なことはたぶんTheorem 2とTheorem 3でしょう。どっちも証明は難しくない。まず、Theorem 1である緩い条件のもとで、任意の関数は凸関数と凹関数の和で書き表わせる(この分解は一意には定まらない)ということが示してある*1。凹関数は凸関数にマイナスをかけたものでもあるので、凸関数の差で書き表わされていると考えることもできる。このためDifference of Convex法(DC法)と呼ばれることもある。

で、CCCPのアルゴリズムでは
$\nabla E_{\mbox{vex}}(\mathbf{x}^{t+1}) = - \nabla E_{\mbox{cave}}(\mathbf{x}^t)$
を満たすように $\mathbf{x}^{t+1}$ をupdateしていく。こういう風にupdateしていくと単調に減少することが保証されるので、(大域的に行くかは保証できないが)局所最適解に収束することが保証される!!上の式を満たすようなupdate式はエネルギー関数が具体的にどのようになっているかに依存するので一般的な形で書くことはできないが、大抵の場合解析的にupdate式を求めることができ、求めれない場合も数値計算的に求めればよいでしょう、というのがTheorem 2の付近。

Theorem 3の付近から論文中にtypo(と思う)があるので、気をつけたい。ここの3Pの上の付近と合わせて読むとよいと思う(凸関数の性質を使っているだけ)。Theorem 3では、Theorem 2で解析的にできない場合にどうすればいいかの方法を与えている。t+1ステップ目での最適な $\mathbf{x}^{t+1}$ というのは(2)式を最小にするようなものを選べばよい、最小にすべき関数は凸関数であるから例えば共役勾配法などを使って最適な点を求めていけるでしょう、というのが概要。ここも難しいことは使ってない、けどわりと使いやすくよい結果が得られている。おー。

あとはLegendre Transformationとかというのと同値だよとかEMの特殊なケースと一緒だよというようなことが書いてある。が、まあ要点はTheorem 2とTheorem 3で十分でしょう。