なぜ機械学習で双対問題を学ぶのか
結果から述べるのであれば、SVM(サポートベクトルマシーン)の原理で双対問題を使いたいからです。
これから実際どのように双対問題が使われているのか、また、双対問題の簡単な具体例を交えて説明していきたいと思います。
まずSVMについて簡単に説明したいと思います。
予測には過去のデータを使います｡
しかし､外れ値のような余計なデータまで使ってしまうと､予測精度が下がるかもしれません｡
そこで「本当に予測に必要となる一部のデータ」だけを使います｡
「本当に予測に必要となる一部のデータ」のことをサポートベクトルと呼び､
サポートベクトルを用いた機械学習法がサポートベクトルマシン（Sapport vector machine:SVM）です。
双対問題とは
数学において、最適化問題における主問題の補問題のことです。
どちらか一方の解法が両方の問題の解法となります。
最適化理論における双対原理とは、最適化問題を主問題と双対問題のどちらの観点からも見ることができます。
ここで、双対定理についても簡単に説明したいと思います。
双対定理（英: duality theorem）は次のように定義される。
主問題と双対問題のいずれか一方が最適解を持つなら、もう一方も最適解を持ち、主問題の最小値と双対問題の最大値は一致するというものです。
今回はなぜどちらか一方の解が両方の解として良いのかという点についても説明をしたいと思います。
双対問題の具体例
今回あげる具体例は元の主問題だけでも解を求めることができますが、双対問題を使うパターンと主問題を直接解くパターンを紹介したいと思います。
主問題が以下だとします。
\[
\max f(x_{1},x_{2})=-(x_{1}^2+x_{2}^2) \\
s.t. x_{1}-1≧0 , x_{2}-1=0
\]
これは領域を考えると解は明らかに求まります。
\((x_{1},x_{2})=(1,1)\)の時、\(f\)は最大値\(-2\)をとります。
以上が双対問題を使わない解き方です。
次に、双対問題を使った解き方を紹介します。
まず双対問題の導出します。 \[ L(x_{1},x_{2},\lambda,\mu)=-(x_{1})^2-(x_{2})^2+\lambda(x_{1}-1)+\mu(x_{2}-1) \\ =-\left(x_{1}-\frac{\lambda}{2}\right)^{2}-\left(x_{2}-\frac{\mu}{2}\right)^{2}+\left(\frac{\lambda}{2}\right)^2-\lambda+\left(\frac{\mu}{2}\right)^2-\mu (*) \] つまり、 \[ \displaystyle d(\lambda,\mu)=\max_{(x_{1},x_{2})} L(x_{1},x_{2},\lambda,\mu) \\ =\left(\frac{\lambda}{2}\right)^2-\lambda+\left(\frac{\mu}{2}\right)^2-\mu \] となります。 (\(-\left(x_{1}-\frac{\lambda}{2}\right)^2-\left(x_{2}-\frac{\mu}{2}\right)^2)\)は\(０\)以下だから)
従って、双対問題は以下になります。 \[ \displaystyle \min d(\lambda,\mu)=\max_{(x_{1},x_{2})} L(x_{1},x_{2},\lambda,\mu)~~ s.t. \lambda≧0 \] これを\(\lambda,\mu\)に関して平方完成すると、 \[ d(\lambda,\mu)=\frac{1}{4}{(\lambda-2)^{2}+(\mu-2)^{2}}-2 \] 以上から双対問題の最適解は\((\lambda,\mu)=(2,2)\)となり、\(d(2,2)=-2\)
また、(*)から \[ x_{1}=\frac{\lambda}{2}, x_{2}=\frac{\mu}{2} \] だったので、 \[ (x_{1},x_{2})=(1,1) \] の時が最適解となる。
このように、主問題と双対問題の最適解と最適値は一致することがわかりました。
\((x_{1},x_{2})=(1,1)\)の時、\(f\)は最大値\(-2\)をとります。
以上が双対問題を使わない解き方です。
次に、双対問題を使った解き方を紹介します。
まず双対問題の導出します。 \[ L(x_{1},x_{2},\lambda,\mu)=-(x_{1})^2-(x_{2})^2+\lambda(x_{1}-1)+\mu(x_{2}-1) \\ =-\left(x_{1}-\frac{\lambda}{2}\right)^{2}-\left(x_{2}-\frac{\mu}{2}\right)^{2}+\left(\frac{\lambda}{2}\right)^2-\lambda+\left(\frac{\mu}{2}\right)^2-\mu (*) \] つまり、 \[ \displaystyle d(\lambda,\mu)=\max_{(x_{1},x_{2})} L(x_{1},x_{2},\lambda,\mu) \\ =\left(\frac{\lambda}{2}\right)^2-\lambda+\left(\frac{\mu}{2}\right)^2-\mu \] となります。 (\(-\left(x_{1}-\frac{\lambda}{2}\right)^2-\left(x_{2}-\frac{\mu}{2}\right)^2)\)は\(０\)以下だから)
従って、双対問題は以下になります。 \[ \displaystyle \min d(\lambda,\mu)=\max_{(x_{1},x_{2})} L(x_{1},x_{2},\lambda,\mu)~~ s.t. \lambda≧0 \] これを\(\lambda,\mu\)に関して平方完成すると、 \[ d(\lambda,\mu)=\frac{1}{4}{(\lambda-2)^{2}+(\mu-2)^{2}}-2 \] 以上から双対問題の最適解は\((\lambda,\mu)=(2,2)\)となり、\(d(2,2)=-2\)
また、(*)から \[ x_{1}=\frac{\lambda}{2}, x_{2}=\frac{\mu}{2} \] だったので、 \[ (x_{1},x_{2})=(1,1) \] の時が最適解となる。
このように、主問題と双対問題の最適解と最適値は一致することがわかりました。
鞍点定理
\((x^*,λ^*,μ^*)\in \mathbb{R}^n×\mathbb{R}^l×\mathbb{R}^m\)が鞍点
任意の\(x\in \mathbb{R}^n\)および\((\lambda,\mu)\in \mathbb{R}^l×\mathbb{R}^m\)に対し、 (\(\lambda\)の各成分が0以上) \[ L(x,\lambda^*,\mu^*)≦L(x^*,\lambda^*,\mu^*)≦L(x^*,\lambda,\mu) \] を満たす鞍点定理
(1)\((x^*,\lambda^*,\mu^*)\)が鞍点である時、以下の性質が成り立つ
(a)\(x^*\)は主問題の最適解
(b)\((\lambda^*,\mu^*)\)は双対問題の最適解
(c)\(f(x^*)=d(\lambda^*,\mu^*)=L(x^*,\lambda^*,\mu^*)\)
(2)•\(f\)が上に凸,\(g_{i}\)が上に凸
かつ
•\(g_{i}(x)>0 (i=1,\cdots,l)\)かつ\(h_{j}(x)=0 (j=1,\cdots,m)\)を満たす\(x\in\mathbb{R}^{n}\)
が存在する
かつ
•主問題に最適解\(\hat{x}\)が存在する\(\Rightarrow (\hat{\lambda},\hat{\mu})\in\mathbb{R}^l×\mathbb{R}^m\)が存在して、\((\hat{x},\hat{\lambda},\hat{\mu})\)が鞍点となる。
証明は(1)についてのみ書きたいと思います。
\(F=\{x\in\mathbb{R}^{n} | g_{i}(x)≧0 , h_{j}(x)=0 (i=1,\cdots,l) (j=1,\cdots,m)\}\)とする。
(a)\(x^{*}\)は主問題の最適解
鞍点の条件から任意の\((\lambda,\mu)\in \mathbb{R}^l×\mathbb{R}^m\)に対し、 \[ L(x^*,\lambda,\mu)=f(x^*)+\sum_{i=1}^{l} \lambda_{i}g_{i}(x^*)+\sum_{i=1}^{m}\mu_{j}h_{j}(x^*)≧L(x,\lambda^*,\mu^*) \] もし \(g_{i}(x^*)<0\)または\(h_{j}(x)≠0\)ならば\(L(x^*,\lambda,\mu)\)は下界を持たないので矛盾。
背理法から\(g_{i}(x)≧0 , h_{j}(x)=0 \)が満たされるので\(x^*\in F\)となる。
さらに、\(\lambda=0,\mu=0\)のときの不等式から\(f(x^*)≧L(x^*,\lambda^*,\mu^*)\cdots➀\)
一方で、 \begin{eqnarray} L(x^*,\lambda^*,\mu^*)&≧&\max_{x} L(x,\lambda^*,\mu^*) (∵鞍点) \\ &≧&\max_{x\in F} L(x,\lambda^*,\mu^*) \\ &=&\max_{x\in F} f(x^*)+\sum_{i=1}^{l} \lambda_{i}g_{i}(x^*)+\sum_{i=1}^{m}\mu_{j}h_{j}(x^*) \\ &≧&\max_{x\in F} f(x)\cdots➁ \end{eqnarray} ➀,➁より、\(f(x^*)≧L(x^*,\lambda^*,\mu^*)≧\max_{x\in F} f(x) \\ x^*\in F\)だから上式の不等号は等号となる。
つまり、\(x^*\)は主問題の最適解かつ\(f(x^*)=L(x^*,\lambda^*,\mu^*)\)
(b)\((\lambda^*,\mu^*)\)は双対問題の最適解 \begin{eqnarray} d(\lambda,\mu)&=&\max_{x\in \mathbb{R}^{n}} L(x,\lambda,\mu) \\ &≧&L(x^*,\lambda,\mu) (∵x^*\in \mathbb{R}^{n}) \\ &≧&L(x^*,\lambda^*,\mu^*) (∵鞍点) \end{eqnarray} また、 \begin{eqnarray} d(\lambda^*,\mu^*)&=&\max_{x\in \mathbb{R}^{n}} L(x,\lambda^*,\mu^*) \\ &≦&L(x^*,\lambda^*,\mu^*) \end{eqnarray} よって、任意の\((\lambda,\mu)\in \mathbb{R}^{l}×\mathbb{R}^{m}\)に対し、 \[ d(\lambda^*,\mu^*)≦L(x^*,\lambda^*,\mu^*)≦d(\lambda,\mu) \] これより\((\lambda^*,\mu^*)\)は双対問題の最適解かつ\(d(\lambda^*,\mu^*)=L(x^*,\lambda^*,\mu^*)\)
以上で証明部分を終わりにしたいと思います。
(a)\(x^*\)は主問題の最適解
(b)\((\lambda^*,\mu^*)\)は双対問題の最適解
(c)\(f(x^*)=d(\lambda^*,\mu^*)=L(x^*,\lambda^*,\mu^*)\)
(2)•\(f\)が上に凸,\(g_{i}\)が上に凸
かつ
•\(g_{i}(x)>0 (i=1,\cdots,l)\)かつ\(h_{j}(x)=0 (j=1,\cdots,m)\)を満たす\(x\in\mathbb{R}^{n}\)
が存在する
かつ
•主問題に最適解\(\hat{x}\)が存在する\(\Rightarrow (\hat{\lambda},\hat{\mu})\in\mathbb{R}^l×\mathbb{R}^m\)が存在して、\((\hat{x},\hat{\lambda},\hat{\mu})\)が鞍点となる。
証明は(1)についてのみ書きたいと思います。
\(F=\{x\in\mathbb{R}^{n} | g_{i}(x)≧0 , h_{j}(x)=0 (i=1,\cdots,l) (j=1,\cdots,m)\}\)とする。
(a)\(x^{*}\)は主問題の最適解
鞍点の条件から任意の\((\lambda,\mu)\in \mathbb{R}^l×\mathbb{R}^m\)に対し、 \[ L(x^*,\lambda,\mu)=f(x^*)+\sum_{i=1}^{l} \lambda_{i}g_{i}(x^*)+\sum_{i=1}^{m}\mu_{j}h_{j}(x^*)≧L(x,\lambda^*,\mu^*) \] もし \(g_{i}(x^*)<0\)または\(h_{j}(x)≠0\)ならば\(L(x^*,\lambda,\mu)\)は下界を持たないので矛盾。
背理法から\(g_{i}(x)≧0 , h_{j}(x)=0 \)が満たされるので\(x^*\in F\)となる。
さらに、\(\lambda=0,\mu=0\)のときの不等式から\(f(x^*)≧L(x^*,\lambda^*,\mu^*)\cdots➀\)
一方で、 \begin{eqnarray} L(x^*,\lambda^*,\mu^*)&≧&\max_{x} L(x,\lambda^*,\mu^*) (∵鞍点) \\ &≧&\max_{x\in F} L(x,\lambda^*,\mu^*) \\ &=&\max_{x\in F} f(x^*)+\sum_{i=1}^{l} \lambda_{i}g_{i}(x^*)+\sum_{i=1}^{m}\mu_{j}h_{j}(x^*) \\ &≧&\max_{x\in F} f(x)\cdots➁ \end{eqnarray} ➀,➁より、\(f(x^*)≧L(x^*,\lambda^*,\mu^*)≧\max_{x\in F} f(x) \\ x^*\in F\)だから上式の不等号は等号となる。
つまり、\(x^*\)は主問題の最適解かつ\(f(x^*)=L(x^*,\lambda^*,\mu^*)\)
(b)\((\lambda^*,\mu^*)\)は双対問題の最適解 \begin{eqnarray} d(\lambda,\mu)&=&\max_{x\in \mathbb{R}^{n}} L(x,\lambda,\mu) \\ &≧&L(x^*,\lambda,\mu) (∵x^*\in \mathbb{R}^{n}) \\ &≧&L(x^*,\lambda^*,\mu^*) (∵鞍点) \end{eqnarray} また、 \begin{eqnarray} d(\lambda^*,\mu^*)&=&\max_{x\in \mathbb{R}^{n}} L(x,\lambda^*,\mu^*) \\ &≦&L(x^*,\lambda^*,\mu^*) \end{eqnarray} よって、任意の\((\lambda,\mu)\in \mathbb{R}^{l}×\mathbb{R}^{m}\)に対し、 \[ d(\lambda^*,\mu^*)≦L(x^*,\lambda^*,\mu^*)≦d(\lambda,\mu) \] これより\((\lambda^*,\mu^*)\)は双対問題の最適解かつ\(d(\lambda^*,\mu^*)=L(x^*,\lambda^*,\mu^*)\)
以上で証明部分を終わりにしたいと思います。
まとめ
双対問題を考えることで、対象の最適化問題を簡単に解くことができることが多いため双対問題を扱うことがわかりました。
また、なぜ双対問題を考えることが主問題の解を求めることと同値であることをメインに紹介してきました。
さらに、鞍点定理についても紹介しましたが、証明についてはかなり難しくなっているため定理の主張だけ抑えておくのがいいのかと思います。
