記事の目的
機械学習手法の多くは、概ね以下のフローを辿りアルゴリズムが構成されます。
１．目的関数と制約条件を定式化し、最適化問題を考える
２．制約条件のもとで目的関数を最小化（もしくは最大化）する更新式を求める
３．収束条件を満たすまで交互最適化を行う
特に、２．の更新式を求めるのところで、凸関数の概念が必要になります。
ただし、多くの機械学習の文献では、「読者の皆は凸関数になってるのわかるよね！！」という感じで議論が進み明確に説明することはありません。そんな感じなので、卒研ゼミや研究指導していても、**この関数は凸関数だから偏微分して整理すればこの式が出てくるよね（ニッコリ）**と言ってもあんまり理解してもらえません。ということで、機械学習を勉強するうえでは、凸関数を知っておいたほうがよかろうということでこの記事を書きます。
凸関数 is 何
簡単に言うと、高校生のときに出てきた下に凸な関数を**凸関数(convex function)と言います。例えば、$f(x) = x^2$は凸関数です。反対に、上に凸な関数を凹関数(concave function)**と言い、$f(x) = -x^2$は凹関数になります。
凸関数は非線形な関数の最小化（最大化）を考える際に必要となります。機械学習分野では、凸関数の最小化（$f(x) = x^2$を最小化する$x$を求める）という形で最適化問題を定義することが多いです。凹関数の最大化（$f(x) = -x^2$を最大化する$x$を求める）の場合は、目的関数に-1を書けて、凸関数の最小化に変形して考えます。
何故そのようにするかというと、同じ枠組みで議論を進める方が全体の見通しが良い、くらいの説明に留めておきます。興味がある方は、システム最適化、最適化数学、数理計画法などのテキストの序論あたりを読むとなんとなく雰囲気が掴めると思います。
凸関数の定義
凸関数の定義は概ね以下となります。もっと良い定義の仕方もありますが、ここでは機械学習に使うことを考えて、説明を少し簡略化しています。
定義 凸関数
$f$を$p$変数の実数値関数とする.ここで、任意の$x, y \in \Re^p$と任意の$0\leq\lambda\leq 1$に対して、
$$
f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)
$$
が成り立つならば、凸関数と呼ばれる。
条件式がやや難しそうですが、簡単に考えると、まず２点$x, y$を選びます。すると、左辺は$x, y$間のどこかの関数$f$上の値、右辺は$f(x)$と$f(y)$をつないだ直線上のどこかの値、になっています。$0\leq\lambda\leq 1$に対して、常にこの式が成り立つとき、関数$f$は凸関数となります。図を書くとスッキリとわかると思います。余白はあっても時間が足りない。準備が遅くて本当にすいません。
このへんを見てください。
凸関数の見分け方
１変数関数の場合は、２階微分が常に正であれば凸関数となります。つまり、傾きの傾きが常に正になるということなので、傾きが常に増加するということです。
多変数関数の場合は、ヘッセ行列が半正定値になれば凸関数となります。行列が半正定値であることを調べるには、固有値がすべて非負であることを示せればOKです。固有値が非負なので、固有値に０を含んでも大丈夫です。最近は行列計算のパッケージが手軽に使えるので、そういった調べ方もありです。ただし、数値計算的に求めることになるので、注意が必要な場合もあります。
凸関数の例
例えば回帰分析の目的関数は以下で表されます。
$$
J(w) = \sum^n_{k=1}(y_k- (w^Tx_k + b))^2 \longrightarrow \min
$$
ここで、$k$はデータ番号、$n$はデータ数、$y_k \in \Re$は目的変数、$x_k \in \Re^p$は説明変数、$b$は回帰式の切片を意味します。繰り返しの説明になりますが。$y_k$はスカラーで$x_k$は$p$次元の実ベクトルになっています。$J(w)$の式は残差の総和を最小化という式になっています。
この式は、総和の記号がついていますが、$(y_k- (w^Tx_k + b))^2$だけを見ると自乗の関数、つまり凸関数になっています。そして、凸関数には、凸関数の和は凸関数という重要な性質があります。つまり、$J(w)$は凸関数になっているので、$J(w)$を$w$について偏微分して整理してやれば、目的関数を最小にする$w$が求まります。
機械学習チョットデキルを目指して
本記事では凸関数の例として回帰分析を例に取り上げました。この他にも、代表的クラスタリング手法である$k$-meansや混合ガウスモデル、また判別問題を扱うサポートベクターマシンなど、多くの機械学習手法は、凸関数を用いて構成されています。$k$-meansについてはそのうち別の記事で書こうと思います。
機械学習は、大学１〜２年で学ぶ線形代数、解析、確率統計などに基づいて構成されています。個人的には、情報系や工学系の数学の基準として、応用面では機械学習やパターン認識、理論面ではシステム最適化（最適化数学）があると思っています。本記事では扱いませんでしたが、ラグランジュの未定乗数法の使い方だけでも理解しておくと、機械学習の勉強はずっとやりやすくなると思います。式変形などの教科書の行間を埋める作業は、力がつく重要な取り組みですが、とても時間がかかることがあります。一人で頑張るには限界があると思いますので、友人・教員・Webなど様々なインフラを活用して頑張ってください、というか私もやっていかないとマジでやばいです。