CRFの目的関数が凹関数（concave function）であるかの証明

先日tkngさんより「CRFの目的関数は凹関数なので局所最適解は存在しない」とご指摘を受けたのですが、「あれ、凹関数であることをどうやって示せばいいのかな？」と考え、調べた結果をまとめます。大学１年生レベルの内容ですが復習がてらです。

Claim:
CRFの目的関数は凹関数である。

まずこれを示すためにはある関数が凹関数であることをどうやって示すのか？

Lemma 1:
凹関数であることを示すには関数の二階微分が正であることを示せばよい。多次元の引数を取る場合、ヘッセ行列が半正定値対称行列であることを示せばよい。

何でこれでよいか？と聞かれるとまだ説明ができませんが、イメージとしてあるのは「傾きが広義単調増加しているから関数がU字型のカーブを描く」というもの。

Lemma 2:
Log-sum-exp は凹関数である。（実数上では）

CRFの目的関数はアンダフローを防ぐため等の理由でlog-sum-expが用いられます。その為、こちらに軸をおいてこの先を進めていきます。まずCRFを用いた博士論文に「log sum expはconcaveである」との記述を見かけました。

Proof. See in Convex Optimization [Boyd & Vandenberghe, 2004].
http://d-nb.info/1043515208/34

ということでググった所、無料公開されていたので3.1.4節のSecond order conditions（71ページ）を見てみました。

Log-sum-exp is convex on R^n
https://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

いや、だから何でですか。。。と思いかけていた所、授業のスライドが公開されていたのでみてみる。（10枚目のスライドに詳しい式が載っている。）

let $f(x) = \log \Sigma_{k}\exp (x_k)$ and $z_k = \exp (x_k)$
$\150dpi \nabla^2 f(x) = \frac{1}{ {\bf 1}^{\mathrm{T}} z} {\bf diag}(z) - \frac{1}{ ({\bf 1}^{\mathrm{T}} z)^2} zz^{\mathrm{T}}$
http://www.stanford.edu/class/ee364a/lectures/functions.pdf

diag(z)はz_kをk列k行の対角成分に並べ、それ以外の要素は0とする行列です。zz^Tになっているのがなるほど、と思いました。z^Tzの場合はただの数値になりますが、この場合はn*nの行列になっています。

とりあえずこの $\bm{1}^{\mathrm{T}} z$ が意味不明でしたので簡単に二次元で計算してみます。

例：
$f(x) = \log (\exp (x_1) + \exp (x_2))$
のヘッセ行列を算出する。

$\frac{\partial f}{\partial x_1} = \frac{1}{\exp (x_1) + \exp (x_2)} * \exp (x_1)$
$\frac{\partial^2 f}{\partial x_1 \partial x_2} = -(\frac{1}{\exp (x_1) + \exp (x_2)})^2 * (\exp (x_1) * \exp (x_2))$
$\frac{\partial^2 f}{\partial x_1^2} = -(\frac{1}{\exp (x_1) + \exp (x_2)})^2 * (\exp (x_1))^2 + \frac{ \exp (x_1)}{ \exp (x_1) + \exp (x_2)}$
以下同様にx_2に関しても計算する必要があるのですが、ほぼ同じなので省略します。
三番目の式の第一項がスライドの数式の第二項に、三番目の式の第二項がスライドの数式の第一項に対応しています。あー、なるほどと思いました。意味がわかりますと、なんと簡潔に表現されているのだ！と感動します。

この後スライドの通りヘッセ行列を計算すると半正定値対称行列になります。
証明の過程で用いられているCauchy-Schwartzの式で少し詰まったので行間を後で埋めます。まだ未完成ですので後日追記します。