0. 初めに
HACARUS東北チームのデータサイエンティスト、鈴木です。
以前のブログにもありますように、弊社では、業務の一環としてスパースモデリングを学び直す勉強会（以下スパモ勉強会）を行っております。
コロナウィルスが猛威を奮い、以前までは当たり前のように出来ていたやり取りが難しくなっている中、スパモ勉強会はHACARUSメンバーの相互交流促進にも寄与しています。
スパモ勉強の第二弾として、LASSOの解法を題材に記事を書きます。なお、第二弾は複数の記事に分けて連載していこうと思います。今回はその一回目の連載として、LASSOの解を求める上で重要な概念となる凸最適化問題を紹介しようと思います。
凸最適化問題とは、以下の様な問題になります。
\[ \mathrm{minimize}_{\mathbf{x} \ \in \ \mathbb{R}^{n}} \ f(\mathbf{x}) \ \mathrm{subject} \ \mathrm{to} \
\mathbf{x} \in C\]
ここで、数式中にある\(f\)、\(C\)は何でも良い訳ではなく、数学的な条件が課せられます。その数学的条件には、例えば「\(f\)は凸関数である」や「\(C\)は閉凸集合である」などがありますが、初学者の方にとっては、そもそもこれらの意味が分からないと思います。そこで、本稿では、まず「凸関数」や「凸集合」といった数学的な用語の説明・定義をご紹介し、最後に凸最適化問題を改めて定義したいと思います。
本稿は以下の流れで構成されています。各項目にはジャンプすることが出来るので、必要に応じて読み飛ばしてください。
1. 凸集合
初めに凸集合について紹介します。少し固い話になってしまいますが、まず定義をして、その後に具体例を考えていこうと思います。
なお、以降の章でも基本的に同じ流れを取りますが、具体例は省略する場合もあります。また、補足を加える場合もあります。
定義
集合 \(\mathit{C} (\subset \mathbb{R}^{n}) \) が任意の \( {\bf x} , {\bf y} \in \mathit{C}\) 及び任意の \(
\rm{\lambda} \in [0, 1]\) に対して
\[
\bf{\lambda} \bf{x} + \rm{(1 – \lambda)} \bf{y} \in \mathit{C}
\tag{1}
\label{eq:conv-set}
\]
を満たすとき、\(\mathit{C}\) は凸集合であると言います。
具体例
凸集合の定義式は(1)ですが、式だけを眺めていてもピンとこないかと思います。ここでは、\(n=2\) の例を考えて凸集合を解釈していきましょう。
図1. 凸集合と非凸集合の具体例
上の図では、左側の円板が表す集合は凸集合で、右側の扇形が表す集合は凸集合ではありません（このような集合を非凸集合と呼びます）。
凸集合と非凸集合の違いは図の赤色で示されている部分にあります。
すなわち、図の黒色で示されている部分は集合上の点 \(\mathbf{x}, \mathbf{y}\) を結ぶ線分上の全ての点が集合に含まれていますが、対して赤色で示されている部分は集合に含まれない点が存在します。
このように、集合が凸集合であるとは、集合に含まれるどのような2点 \(\mathbf{x}, \mathbf{y}\) を選んでもそれを結ぶ線分上の点全てが同じ集合に含まれる場合にいいます。
上の図ですと、扇形の集合は黒で表される \(\mathbf{x}, \mathbf{y}\) を選んだ際には条件式を満たしますが、赤で表される \(\mathbf{x},\mathbf{y}\) を選んだ際には集合に含まれない部分が線分上にあるので非凸集合です。
このイメージを持って頂ければ、例えば球で表される集合が凸集合かどうか、平面で表される集合が凸集合かどうかもすぐに判断できるはずです。
2. 指示関数
\(\mathbf{x} \in \mathbb{R}^{n}\) がある集合 \(C\) に属しているかどうかを数で表現したい状況はよくあります。例えば、\(C\) に属していたら1、属していなければ0などです。
実はこれが一般的な指示関数の定義なのですが、数理最適化の文脈では \(0, \infty\) で定義することがあります。
定義
\(C \subset \mathbb{R}^{n}\) に対して、以下のように定義される関数 \(I_{C} : \mathbb{R}^{n} \to \mathbb{R} \cup \{ \infty \}\)
を(ここでは)指示関数と呼びます。
\[
I_{C}(\mathbf{x}) =\left\{\begin{array}{ll}
0 & ( \, \mathbf{x} \in C) \\
\infty & ( \, \mathbf{x} \notin C) \\
\end{array} \right.
\tag{2}
\label{eq:2}
\]
補足
上で、一般的な指示関数は0,1で定義されていると述べましたが、なぜ数理最適化では \(0, \infty\) で定義されるのかと疑問に思われた方がいらっしゃるのではないかと思います。
その最たる理由としては、\(0, \infty\) で定義される指示関数を用いることで、以下のように制約ありの最適化問題をそれと等価な制約なしの最適化問題に書き直すことが出来るためです。
\[
\mathrm{minimize} _{\mathbf{x} \in \mathbb{R}^{n}} f(\mathbf{x}) \ \mathrm{s.t.}\ \mathbf{x} \in C \,
\Longleftrightarrow
\, \mathrm{minimize}_{\mathbf{x} \in \mathbb{R}^{n}}\left\{ f(\mathbf{x}) + I_{C}(\mathbf{x})\right\} \\
\]
上の最適化問題では、\(\mathbf{x} \in C\) という制約を指示関数を用いてなくしました。
等価であることは最小化問題であることと、\(\mathbf{x} \notin C\) である \(\mathbf{x}\) を考えてみれば分かるかと思います。
3. 実効定義域
定義
関数 \(f : \mathbb{R}^{n} \to \mathbb{R} \cup \{ \infty \}\)
に対して、以下の式で定義される \(\mathrm{dom}(f)\)を関数 \(f\) の実効定義域と呼びます。
\[ \mathrm{dom}(f) = \{\mathbf{x} \in \mathbb{R}^{n} \mid f(\mathbf{x}) < \infty\} \tag{3} \label{eq:3} \]
具体例
定義式(3)から、実効定義域は関数 \(f\) が有限の値を取る入力集合であることが分かります。
ここでは、\(n=2, C=\{(x_{1}, x_{2}) | {x_{1}}^{2} + {x_{2}}^{2} \le 1\}\)とした時の(2)式で表される指示関数 \(I_{C}\)
の実効定義域について考えてみます。
指示関数は二つの値しかとらないので、二次元平面上に値を書き込むと以下の図のようになります。
\(I_{C}\) が有限の値を取るのは図の青色の部分(単位円の内側)ですので、指示関数 \(I_{C}\) の実効定義域は、以下のようになります。
\[ \mathrm{dom}(I_{C}) = \{(x_{1}, x_{2}) | {x_{1}}^{2} + {x_{2}}^{2} \le 1\} = C \]
図2. 指示関数 \(I_{C}\) の実効定義域
4. プロパー
3.で定義した実効定義域に付随する用語として、プロパーというものがあります。定義はシンプルです。
定義
関数 \(f : \mathbb{R}^{n} \to \mathbb{R} \cup \{ \infty \}\) の実効定義域 \(\mathrm{dom}(f)\) が空でないとき、関数 \(f\)
はプロパーであると言います。
具体例
3.の具体例で紹介した指示関数 \(I_{C}\) は実効定義域が空集合ではないので、プロパーな関数です。
5. 凸関数
ここでは凸関数について紹介します。
定義を見れば分かると思いますが、凸集合の定義とよく似ています。
定義
プロパーな関数 \(f : \mathbb{R}^{n} \to \mathbb{R} \cup \{ \infty \}\) が任意の \( {\bf x} , {\bf y} \in \mathrm{dom}(f)\)
及び任意の\(\rm{\lambda} \in [0, 1]\) に対して以下の条件を満たすとき、 \(f\) は凸関数であると言います。
\[
f(\lambda {\bf x} + (1 – \lambda) {\bf y}) \le \lambda f({\bf x}) + (1 – \lambda)f({\bf y}) \tag{4}
\]
具体例
天下り的ですが、放物線 \(f(x) = x^{2}\) は凸関数です(7.で証明をします)。放物線を例に凸関数を図から理解していこうと思います。
図3. 凸関数の例
\( s , t \in \mathrm{dom}(f)\) を固定して考えます。
例えば、ここでは図の点A,Bのような位置関係になるとしましょう。
放物線は凸関数なので、 \(s , t\) に対して、条件式(4)が成立しています。
条件式(4)は図において何を意味しているのでしょうか。
不等式の左辺と右辺を別々に考えていきます。
まず、右辺ですが、 \(f(s)\) は点Aのy座標、 \(f(t)\) は点Bのy座標であるため、 \(\lambda f(s) + (1-\lambda)f(t)\) は線分ABを
\(\lambda \ : (1-\lambda)\) に内分する点(この点をDとする)のy座標に対応していることが分かります。
次に、左辺ですが、 \(\lambda s + (1-\lambda)t\) は点Dのx座標です。
従って、 \(f(\lambda s+(1-\lambda)t)\) は、点Dとx座標が同じである放物線上の点(この点をCとする)のy座標です。
これらにより、条件式(4)は、上図において (点Cのy座標) ≤ (点Dのy座標) を表現していることが分かります。
ここで、 \(\lambda\) は \([0,1]\) の範囲内で自由に動くことが出来ることに注意して下さい。
すなわち、線分AB上の任意の点は点Dであり、点Dに伴って変化する点Dとx座標が同じ放物線上の点もまた点Cです。
ここまでをまとめると、固定された \( s , t \in \mathrm{dom}(f)\) に対して条件式(4)が成立するということは、
線分ABが常に関数 \(f\) よりも上側にあること意味していると分かります。
実際は \( s , t\) は任意の値なので、線分ABも動き回りますが、いずれにしても線分が関数よりも上側にあるような関数が凸関数であるというイメージを持って頂ければと思います。
6. 閉集合
次に閉集合の定義を確認します。閉集合は厳密には距離空間に対して定義されますが、本稿の文脈上はEuclid空間での定義を行えば十分なので、そこまでに留めます。
定義
Euclid空間 \(\mathbb{R}^{n}\)の部分集合 \(U\) が開集合であるとは、任意の点\(p \in U\)に対して、ある \(\epsilon > 0\)が存在し、\(\{ x \in \mathbb{R}^{n} | ||x-p||_{2} < \epsilon \} \subset U\)
が成立することを言う。また、\(U \subset \mathbb{R}^{n}\) が閉集合とは、\(U\) の補集合が開集合となることである。
具体例
難しいことをいっているように聞こえますが、例をあげると分かりやすいです。例えば、\([-1, 1]\)は閉集合、\((-1, 1)\)は開集合であり、\([-1, 1)\)は閉集合でも開集合でもありません。
7. 凸最適化問題
ここまで数学的な用語の説明が続きましたが、いよいよ凸最適化問題を紹介します。
定義
関数 \(f : \mathbb{R}^{n} \to \mathbb{R} \cup \{ \infty \}\) がプロパーな凸関数、集合 \(C \subset
\mathbb{R}^{n}\) が閉凸集合であるとき、\(\mathbf{x} \in C\) なる \(\mathbf{x}\) の中で \(f(\mathbf{x})\) を最小にする
\(\mathbf{x}\) を求める問題を凸最適化問題と呼びます。
なお、凸最適化問題に限った話ではなく、一般の最適化問題にも当てはまりますが、数式では主に以下のいずれかで最適化問題を記述します。
\[ \mathrm{minimize}_{\mathbf{x} \ \in \ \mathbb{R}^{n}} \ f(\mathbf{x}) \ \mathrm{subject} \ \mathrm{to} \
\mathbf{x} \in C\]
\[ \mathrm{min}_{\mathbf{x} \ \in \ \mathbb{R}^{n}} \ f(\mathbf{x}) \ \mathrm{s.t.} \ \mathbf{x} \in C\]
具体例
\(n=1, f(x) = x^{2}, C = \mathbb{R}\) とし、関数 \(f\) の最小値を求める最適化問題を考えてみます。これを数式で表すと、
\[ \mathrm{minimize}_{x \ \in \ \mathbb{R}} \ x^{2} ( \mathrm{subject} \ \mathrm{to} \ {x} \in\mathbb{R})
\tag{5}\]
のように表現することが出来ます。
なお、subject to 以下はこの場合は自明なので書き下さなくても構いません。
この最適化問題は凸最適化問題なのか否かを確認してみたいと思います。
まず、関数 \(f\) ですが、任意の \( s , t \in \mathrm{dom}(f)\) 及び任意の \(\mathrm{\lambda} \in [0, 1]\) に対して
\begin{align*}
\lambda f(s) + (1-\lambda)f(t) – f(\lambda s+(1-\lambda)t)
&= \lambda s^{2} + (1-\lambda) t^{2} – (\lambda s+(1-\lambda)t)^{2}\\
&= \lambda s^{2} + (1-\lambda) t^{2} – (\lambda^{2} s^{2} + 2 \lambda (1-\lambda) st + (1-\lambda)^{2} t^{2})\\
&= \lambda (1-\lambda)(s^{2} -2st + t^{2})\\
&= \lambda (1-\lambda)(s – t)^{2}\\
&\ge 0
\end{align*}
のようになるため、凸関数であることが分かります。似たような手順を踏むことで \(C\) が閉凸集合であることが示されます。
従って、最適化問題(3)は凸最適化問題であることが分かりました。
ところで、上の具体例からも分かる通り、ある最適化問題が凸最適化問題なのか否かを判定することは一般に煩雑です。
このような手間をかけてまで凸最適化問題であることを示す理由は一体何なのでしょうか？
それは、凸最適化問題には以下で紹介する凸最適化問題のみが持つ重要な性質があるためです。
8. 凸最適化問題の重要な性質
性質
任意の局所最適解は大域的最適解であり、最適解全体は凸集合となる。
補足
上の性質が何故重要なのかというと、大域的最適解を求めることは一般に困難だからです。
「最適化」問題なのですから、望ましい解は実行可能領域内で目的関数を最も最小にする大域的最適解です(ここでは、最大化問題は最小化問題と等価なので最小化に限定しています)。
しかし、大域的最適解を求めることは困難で、それに比べて局所最適解を求めることは容易であるため、局所最適解で妥協する事は良くあります。
ところが、最適化問題が凸最適化問題である事が判明した途端、局所最適解を求めるという「妥協」が「最適」なアプローチに変貌するわけですから、上の性質は重要なものであるといえます。
9. まとめ
ここまでの簡単なまとめをしようと思います。
今回はLASSOの解を求める上で重要な凸最適化問題について、それを定義するために必要な概念を含めて紹介をしました。
凸最適化問題に至るまでが長いですが、特に凸集合と凸関数はよく耳にする単語ですのでイメージをシッカリ持っておくと良いかと思います。
また、要所要所に「凸」という単語が出てきていることから推測される通り、最適化を考える際に凸かどうかの議論は非常に重要な役割を果たします。
凸に関連する定理や用語は他にもありますので、興味を持って頂けた方々は是非調べてみて下さい。
10. 終わりに
ずいぶんと長くなってしまいましたが、ここまで読んで頂きありがとうございました。
ブログを書くのは人生で初めてだったので、貴重な経験をすることが出来て光栄に思います。
今回の記事ではLASSOを解くための数学的な準備の部分を紹介しましたが、次回の記事では凸最適化の性質をもとにしたLASSOに対するアプローチを紹介する予定です。
次回の記事も鈴木が執筆する予定ですので、今回の記事で興味を持っていただけた方は是非読んで頂きたいです。
