DEVELOPER’s BLOG

技術ブログ

SVMで必要な双対問題の解説

2020.09.30 小池 壮
機械学習
SVMで必要な双対問題の解説

なぜ機械学習で双対問題を学ぶのか

結果から述べるのであれば、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)\)は\(0\)以下だから)
従って、双対問題は以下になります。 \[ \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^*)\)
以上で証明部分を終わりにしたいと思います。


まとめ

双対問題を考えることで、対象の最適化問題を簡単に解くことができることが多いため双対問題を扱うことがわかりました。

また、なぜ双対問題を考えることが主問題の解を求めることと同値であることをメインに紹介してきました。

さらに、鞍点定理についても紹介しましたが、証明についてはかなり難しくなっているため定理の主張だけ抑えておくのがいいのかと思います。

関連記事

生成AIで架空飲食チェーン店のVOC分析やってみた

ご挨拶 AWS全冠エンジニアの小澤です。 今年の目標はテニスで初中級の草トーナメントに優勝することです。よろしくお願いいたします。 本記事の目的 本記事では、生成AIでVOC分析を行うことで得られた知見を共有したいと思います。 昨今、生成AIの登場など機械学習の進歩は目覚ましいものがあります。一方、足元では自社データの利活用が進まず、世の中のトレンドと乖離していくことに課題感を持たれている方も多いかと思います。また、ガートナーの調査(2024年1月)による

記事詳細
生成AIで架空飲食チェーン店のVOC分析やってみた
AWS SRE 機械学習
機械学習で採用予定人数を予測する。狙い目企業はどこ?

2022年卒大学生の皆さん! コロナウイルスが流行していることで就活にどういう影響があるのか、とても不安ですよね。 今回は業界ごとに採用人数を予測し、「どの業界が狙い目なのか」機械学習を使った分析手順を紹介します! 目次 概要 手順 今後の課題 1.概要 データセットの内容 分析対象の7業界・各4企業 化粧品 電子機器 商社 不動産 金融 サービス IT・情報 説明変数と目的変数 特徴量 年初の株価、決算報告書提出翌日の株価、一株あたりの純資産額、従業員数

記事詳細
機械学習で採用予定人数を予測する。狙い目企業はどこ?
利用事例 機械学習
機械翻訳の歴史と今後の可能性

目次 機械翻訳とは 機械翻訳の手法 現在の機械翻訳の欠点 欠点が改善されると 今後の展望 機械翻訳とは 機械翻訳という言葉を理解するために2つ言葉を定義する。 系列 : 記号の列のことで自然言語処理の世界だと文を構成する単語の列になる。 系列変換モデル : 系列を受け取り、それを別の系列に変換する際の確率をモデル化したもの。系列変換モデルはseq2-seqモデルとも呼ばれている。 この2つの言葉から機械翻訳は、ある言語の文章(系列)を別の言語の文章(系列)

記事詳細
機械翻訳の歴史と今後の可能性
利用事例 機械学習 自然言語処理
機械学習で為替予測(FX)をしてみる

こんにちは。 皆さんはFXでお金を稼ぎたいと思ったことはあるでしょうか?もしFXでこれまでの生活を一変させるような額のお金を稼ぐことができたら夢のようですよね? 今回はそんな夢を目指して、為替の値動きを機械学習で予測してみたというお話をしたいと思います。 目次 概要 手順 結果 今後の課題 1 概要 使用したデータセット:OANDA APIを用いて取得 https://www.oanda.jp/fxproduct/api (デモ口座を開設することにより、無

記事詳細
機械学習で為替予測(FX)をしてみる
利用事例 機械学習

お問い合わせはこちらから