本記事は機械学習の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
定義：補助関数と補助変数
$\theta=\theta_{i=1,\ldots,I}$を変量とする目的関数$D(\theta)$に対し，新しい変数$\bartheta$を導入して以下が成り立つとき，
D(\theta) &= \min_{\bartheta}G(\theta,\bartheta)\label{D}
\end{align}
$G(\theta,\bartheta)$を$D(\theta)$の補助関数，$\bartheta$を補助変数という。
補助関数法を記述するために必要な定義です。
定理：補助関数法
補助関数$G(\theta,\bartheta)$に対し，以下のステップを繰り返す。
\bartheta&~\larr~\argminbartheta G(\theta,\bartheta)\label{bartheta}\\[0.7em]
\theta&~\larr~\argmintheta G(\theta,\bartheta)\label{theta}
\end{align}
このとき，目的関数$D(\theta)$は単調減少する。
補助関数法は，目的関数の上限となるように定義された補助関数を反復的に降下させることによって，近似的に解を探索する手法です。EMアルゴリズムの一般化とも捉えることができ，適当な補助関数が見つかった場合には，上記更新式により目的関数の収束が保証されます。
証明
まずは，更新式($\ref{bartheta}$)と更新式($\ref{theta}$)を更新回数$k$を用いて書き直します。
\bartheta^{(k+1)}&=\argminbartheta G(\theta^{(k)},\bartheta)\label{bartheta_k}\\[0.7em]
\theta^{(k+1)}&=\argmintheta G(\theta,\bartheta^{(k+1)})\label{theta_k}
\end{align}
更新式($\ref{bartheta_k}$)により求められた$\bartheta^{(k+1)}$を用いると，補助関数$D$の定義($\ref{D}$)より，
G(\theta^{(k)},\bartheta^{(k+1)}) &= D(\theta^{(k)})\label{GD}
\end{align}
が成り立ちます。次に，式($\ref{theta_k}$)より$\theta^{(k+1)}$は$G(\theta,\bartheta^{(k+1)})$を最小化する$\theta$ですので，
G(\theta^{(k+1)},\bartheta^{(k+1)}) &\leq G(\theta^{(k)},\bartheta^{(k+1)})\label{GG}
\end{align}
が成り立ちます。式($\ref{GG}$)に式($\ref{GD}$)を代入すると，
G(\theta^{(k+1)},\bartheta^{(k+1)}) &\leq D(\theta^{(k)})\label{タネ1}
\end{align}
が得られます。ここで，再び補助関数$D$の定義($\ref{D}$)より，任意の$\theta$に対して
D(\theta) &\leq G(\theta, \bartheta^{(k+1)})
\end{align}
が成り立ちますので，$\theta=\theta^{(k+1)}$を代入すると，
D(\theta^{(k+1)}) &\leq G(\theta^{(k+1)}, \bartheta^{(k+1)})\label{タネ2}
\end{align}
が得られます。式($\ref{タネ1}$)と式($\ref{タネ2}$)より，
D(\theta^{(k+1)}) &\leq D(\theta^{(k)})
\end{align}
が得られます。以上より，更新ステップを繰り返すことで目的関数$D(\theta)$が単調減少することが示されました。
コメント