Regret 最小化の概要
設定: 確率質量関数
\(y_t\) は \(t\) ごとに存在するパラメータ \(\theta_t\in[0,1]\) をもつベルヌーイ分布に従う値とする。
ベルヌーイ分布の確率質量関数 \(p(y_t\mid\theta_t)\) は
\[p(y_t\mid\mathbf w_t,\mathbf x_t)=\theta_t^{y_t}(1-\theta_t)^{1-y_t}\tag{1}\]
である。
ロジスティックシグモイド関数の逆関数として知られるロジット変換 \(a\) は
\[a(\theta)=\ln\frac{\theta}{1-\theta}\tag{2}\]
と定義され、これを \(\theta_t\) について表すと
\[ \begin{split} e^{a_t} &=\frac{\theta_t}{1-\theta_t} \\ \theta_t &= e^{a_t}(1-\theta_t) \\ \end{split}\tag{3} \]
となる。これを \((1)\) に適用すると、
\[ \begin{split} p(y_t\mid a_t) &= \theta_t^{y_t}(1-\theta_t)^{1-y_t} \\ &= e^{a_ty_t}(1-\theta_t)^{y_t}(1-\theta_t)^{1-y_t} \\ &= e^{a_ty_t}(1-\theta_t) \\ &= \exp\{ y_ta_t - \ln (1+e^{a_t}) \} \end{split}\tag{4} \]
となる。この変換によって確率質量関数のパラメータは \(\theta_t\in[0,1]\) から \(a_t\in(-\infty,+\infty)\) となる。
設定: ロジスティック誤差関数
\((4)\) から導出される負の対数尤度 \(-\ln p(y_t\mid a_t)\) によるロジスティック誤差関数を
\[E(y_t,a_t)=-y_ta_t+\ln(1+e^{a_t})\tag{5}\]
と定義する。
設定: \(a_t\) の系列変化が滑らか
\(a_t\) の系列の変化が滑らかであるという事前知識を考慮した式
\[\lambda \sum_{t=1}^{T+1}(a_t-a_{t-1})^2\tag{6}\]
を導入する。\(\lambda\) は予測する系列の滑らかさの度合いを決める係数である。
設定: リグレット
リグレットとは、オフライン予測の結果とオンライン予測の予測結果それぞれの損失を比較し、相対的に評価する指標である。
オンライン予測の予測結果の系列を \(a_1,a_2,\ldots,a_T\) とし、損失関数を \(l(y_t,a_t)\) とする。オフライン予測の予測結果の系列を \(\hat a_1,\hat a_2,\ldots,\hat a_T\) とする。
リグレット \(R\) は
\[R=\sum_{t=1}^T l(y_t,a_t)-\min_{\hat a_1,\ldots,\hat a_T}\left\{\sum_{t=1}^Tl(y_t,\hat a_t)+\lambda \sum_{t=1}^{T+1}\left(\hat a_t-\hat a_{t-1}\right)^2\right\}\tag{7}\]
で定義される。\((12)\) の第２項はスムーザの目的関数であり、オフライン予測の最適な損失を表している。なお、ここで \(\hat a_0,\hat a_{T+1}\) が使われているが、両方とも \(0\) として扱われる。第１項はオンライン予測の損失であるため、「オンライン予測の損失からスムーザの損失を引いたもの」がリグレットとなる。
目的
損失関数 \(l\) として \((12)\) の \(E(y_t,a_t)\) を用い、ミニマックス問題
\[\min_{a_t}\max_{y_t}\cdots\min_{a_T}\max_{y_T}\sum_{t=1}^T l(y_t,a_t)-\min_{\hat a_1,\ldots,\hat a_T}\left\{\sum_{t=1}^Tl(y_t,\hat a_t)+\lambda \sum_{t=1}^{T+1}\left(\hat a_t-\hat a_{t-1}\right)^2\right\}\tag{8}\]
を解く。
本研究との兼ね合い
\(\theta_t\) は \(\sigma_t=\sigma(\mathbf w_t^T\mathbf x_t)\) と対応する。
\(a_t\) は \(\mathbf w_t^T\mathbf x_t\) と対応する。
\((12)\) は、本研究では
\[E(y_t,\mathbf w_t)=-y_t\mathbf w_t^T\mathbf x_t+\ln(1+e^{\mathbf w_t^T\mathbf x_t})\tag{10}\]
と表される。
損失関数の導出
\(f(a)\) を
\[f(a)=\ln\left(e^{a/2}+e^{-a/2}\right)\tag{11}\]
とおく。ここで、\(f(a)=g(a^2)\) とおくと、
\[g(a^2)=\ln\left(e^{\sqrt {a^2}/2}+e^{-\sqrt {a^2}/2}\right)\]
となる。 \(g'(a^2)\) は
\[g'(a^2)=\frac{1}{4a}\tanh\frac{a}{2}\tag{12}\]
となる。
\[g''(a^2)\le 0\tag{13}\]
となるため、 \(g(a^2)\) は凹関数である。これにより、
\[g(a^2)\le g(\xi^2)+g'(\xi^2)(a^2-\xi^2)\tag{14}\]
であるから、 \(g'(a^2)=\phi(a)\) とすると
\[f(a)\le f(\xi)+\phi(\xi)(a^2-\xi^2)\tag{15}\]
が成り立つ。
\[ \begin{split} \ln(1+e^a) &= \ln(e^{a/2}+e^{-a/2})+\ln(e^{a/2}) \\ &= f(a) + \frac{a}{2} \end{split} \tag{16} \]
であるから、 \((5)\), \((15)\) より、
\[ \begin{split} E(y_t,a_t) &=-y_ta_t+\ln(1+e^{a_t}) \\ &= -y_ta_t+f(a_t)+\frac{a_t}{2} \\ &\le -y_ta_t+\frac{a_t}{2}+f(\xi_t)+\phi(\xi_t)(a_t^2-\xi_t^2) \end{split} \tag{17} \]
目的は、損失関数 \(l\) として \(E(y_t,a_t)\) を用いることであるから
\[l(y_t, a_t)=-a_ty_t+\frac{a_t}{2}+f(\xi_t)+\phi(\xi_t)(a_t^2-\xi_t^2)\tag{18}\]
となる。
オフライン予測による損失
\((8)\) より
\[ R =\sum_{t=1}^T l(y_t,a_t)-\min_{\hat a_1,\ldots,\hat a_T}\left\{\sum_{t=1}^Tl(y_t,\hat a_t)+\lambda \sum_{t=1}^{T+1}\left(\hat a_t-\hat a_{t-1}\right)^2\right\} \]
であった。この第２項に注目したとき、オフライン予測を行った際の損失 \(L\) は
\[ L =\sum_{t=1}^Tl(y_t,\hat a_t)+\lambda \sum_{t=1}^{T+1}\left(\hat a_t-\hat a_{t-1}\right)^2 \tag {19} \]
となる。
最小化問題を解くために、\(L\) をベクトルや行列を用いて表現する。
\[ \begin{align} \hat{\mathbf a} &=\begin{pmatrix}\hat a_1 & \cdots & \hat a_T \end{pmatrix}^T \\ \mathbf y &= \begin{pmatrix}y_1 & \cdots & y_T\end{pmatrix}^T \\ \mathbf f &= \begin{pmatrix}f(\xi_1) & \cdots & f(\xi_T)\end{pmatrix}^T \\ \boldsymbol \xi &= \begin{pmatrix}\xi_1 & \cdots & \xi_T\end{pmatrix}^T \\ \mathbf\Phi &=\mathrm {diag}(\phi(\xi_t),\ldots,\phi(\xi_T)) \\ \mathbf K &= \begin{pmatrix}2 & -1 \\ -1 & 2 & -1 \\ & \ddots & \ddots & \ddots \\ & & -1 & 2 & -1 \\ & & & -1 & 2\end{pmatrix} \end{align} \]
\[ \begin{split} \lambda \sum_{t=1}^{T+1}\left(\hat a_t-\hat a_{t-1}\right)^2 &= \lambda\left\{\begin{pmatrix}\hat{\mathbf a} \\ \hat a_{T+1}\end{pmatrix}-\begin{pmatrix}\hat a_0 \\ \hat{\mathbf a}\end{pmatrix}\right\}^T\left\{\begin{pmatrix}\hat{\mathbf a} \\ \hat a_{T+1}\end{pmatrix}-\begin{pmatrix}\hat a_0 \\ \hat{\mathbf a}\end{pmatrix}\right\} \\ &= \lambda \begin{pmatrix}\hat a_0 \\ \hat{\mathbf a} \\ \hat a_{T+1}\end{pmatrix}^T\left\{\begin{pmatrix}\mathbf 0^T \\ \mathbf I\end{pmatrix}-\begin{pmatrix}\mathbf I \\ \mathbf 0^T\end{pmatrix}\right\}\left\{\begin{pmatrix}\mathbf 0 & \mathbf I\end{pmatrix}-\begin{pmatrix}\mathbf I & \mathbf 0\end{pmatrix}\right\}\begin{pmatrix}\hat a_0 \\ \hat{\mathbf a} \\ \hat a_{T+1}\end{pmatrix} \\ &= \lambda \begin{pmatrix}\hat a_0 \\ \hat{\mathbf a} \\ \hat a_{T+1}\end{pmatrix}^T\left\{\begin{pmatrix}0 & \mathbf 0^T \\ \mathbf 0 & \mathbf I\end{pmatrix}-\begin{pmatrix}\mathbf 0^T & 0 \\ \mathbf I & \mathbf 0\end{pmatrix}-\begin{pmatrix}\mathbf 0 & \mathbf I \\ 0 & \mathbf 0^T\end{pmatrix}+\begin{pmatrix}\mathbf I & \mathbf 0 \\ \mathbf 0^T & 0\end{pmatrix}\right\}\begin{pmatrix}\hat a_0 \\ \hat{\mathbf a} \\ \hat a_{T+1}\end{pmatrix} \\ &= \lambda \begin{pmatrix}\hat a_0 \\ \hat{\mathbf a} \\ \hat a_{T+1}\end{pmatrix}^T\begin{pmatrix}1 & -1 \\ -1 & 2 & -1 \\ & \ddots & \ddots & \ddots \\ & & -1 & 2 & -1 \\ & & & -1 & 1\end{pmatrix}\begin{pmatrix}\hat a_0 \\ \hat{\mathbf a} \\ \hat a_{T+1}\end{pmatrix} \end{split} \]
ここで、 \(\hat a_0, \hat a_{T+1}\) は \(0\) であるため、
\[ \begin{split} \lambda \sum_{t=1}^{T+1}\left(\hat a_t-\hat a_{t-1}\right)^2 &= \lambda \begin{pmatrix}0 & \hat{\mathbf a}^T & 0\end{pmatrix}\begin{pmatrix}1 & -1 \\ -1 & 2 & -1 \\ & \ddots & \ddots & \ddots \\ & & -1 & 2 & -1 \\ & & & -1 & 1\end{pmatrix}\begin{pmatrix}0 \\ \hat{\mathbf a} \\ 0\end{pmatrix} \\ &= \hat{\mathbf a}^T\begin{pmatrix}-1 & 2 & -1 \\ & \ddots & \ddots & \ddots \\ & & -1 & 2 & -1\end{pmatrix}\begin{pmatrix}0 \\ \hat{\mathbf a} \\ 0\end{pmatrix} \\ &= \hat{\mathbf a}^T\mathbf K\hat{\mathbf a} \end{split} \]
\[ \begin{split} L =&\sum_{t=1}^Tl(y_t,\hat a_t)+\lambda \sum_{t=1}^{T+1}\left(\hat a_t-\hat a_{t-1}\right)^2 \\ =& \sum_{t=1}^T\left\{-a_ty_t+\frac{a_t}{2}+f(\xi_t)+\phi(\xi_t)(a_t^2-\xi_t^2)\right\}+\lambda\hat{\mathbf a}^T\mathbf K\hat{\mathbf a} \\ =& -\hat{\mathbf a}^T\mathbf y+\frac{1}{2}\hat{\mathbf a}^T\mathbf 1+\mathbf f^T\mathbf 1+\hat{\mathbf a}^T\mathbf\Phi\hat{\mathbf a}-\boldsymbol\xi^T\mathbf\Phi\boldsymbol\xi+\lambda\hat{\mathbf a}^T\mathbf K\hat{\mathbf a} \\ =& \hat{\mathbf a}^T(\mathbf\Phi+\lambda\mathbf K)\hat{\mathbf a}+\left(-\mathbf y+\frac{1}{2}\mathbf 1\right)^T\hat{\mathbf a}+\mathbf f^T\mathbf 1-\boldsymbol\xi^T\mathbf\Phi\boldsymbol\xi \\ =& \left\{\hat{\mathbf a}+\frac{1}{2}(\mathbf\Phi+\lambda\mathbf K)^{-1}\left(-\mathbf y+\frac{1}{2}\mathbf 1\right)\right\}^T(\mathbf\Phi+\lambda\mathbf K)\left\{\hat{\mathbf a}+\frac{1}{2}(\mathbf\Phi+\lambda\mathbf K)^{-1}\left(-\mathbf y+\frac{1}{2}\mathbf 1\right)\right\} \\ &+ -\frac{1}{4}\left(-\mathbf y+\frac{1}{2}\mathbf 1\right)^T(\mathbf\Phi+\lambda\mathbf K)^{-1}\left(-\mathbf y+\frac{1}{2}\mathbf 1\right)+\mathbf f^T\mathbf 1-\boldsymbol\xi^T\mathbf\Phi\boldsymbol\xi \end{split} \]
\(L\) を最小にする \(\hat{\mathbf a}\) は
\[\mathbf{\hat a}=\frac{1}{2}(\mathbf\Phi+\lambda\mathbf K)^{-1}\left(\mathbf y-\frac{1}{2}\mathbf 1\right)\tag{20}\]
であり、その時の損失 \(L^*\) は
\[ L^* =-\frac{1}{4}\left(\mathbf y-\frac{1}{2}\mathbf 1\right)^T\left(\mathbf \Phi+\lambda \mathbf K\right)^{-1}\left(\mathbf y-\frac{1}{2}\mathbf 1\right)+\mathbf f^T\mathbf 1 - \boldsymbol\xi^T\mathbf\Phi\boldsymbol\xi\tag{24} \]
となる。
ある時点での minimax 損失
ある時点における損失 \(V\) を
\[V(a,y)=-ay+\frac{a}{2}+\phi(\xi)a^2+\alpha\left(x-\frac{1}{2}\right)\tag{27}\]
とする。\(\alpha\) は任意の定数である。
ここで、ある時点における minimax 損失 \(V^*\) を
\[V^*=\min_a\max_yV(a,y)\tag{28}\]
とする。
\[\forall y^0\in\{0,1\},\ V^*=V(\alpha,y^0)=\phi(\xi)\alpha^2\tag{29}\]
オンライン予測式の導出
\((8)\) , \((18)\) より
\[R=\sum_{t=1}^T l(y_t,a_t)-\min_{\hat a_1,\ldots,\hat a_T}\left\{\sum_{t=1}^Tl(y_t,\hat a_t)+\lambda \sum_{t=1}^{T+1}\left(\hat a_t-\hat a_{t-1}\right)^2\right\}\]
\[l(a_t,y_t)=-a_ty_t+\frac{a_t}{2}+f(\xi_t)+\phi(\xi_t)(a_t^2-\xi_t^2)\]
であり、 \((9)\) より、minimax リグレット \(R^*\) は
\[R^*=\min_{a_t}\max_{y_t}\cdots\min_{a_T}\max_{y_T}\sum_{t=1}^T l(y_t,a_t)-\min_{\hat a_1,\ldots,\hat a_T}\left\{\sum_{t=1}^Tl(y_t,\hat a_t)+\lambda \sum_{t=1}^{T+1}\left(\hat a_t-\hat a_{t-1}\right)^2\right\}\]
であった。\(R\) の第二項は \(-L^*\) であらわせるため、
\[ \begin{align} \mathbf Y_t &=\begin{pmatrix}y_1 & \cdots & y_t\end{pmatrix}\tag{30} \\ V(\mathbf Y_T) &= -L^* \tag{31}\\ V(\mathbf Y_{t-1}) &= \min_{a_t}\max_{y_t}\left\{-a_ty_t+\frac{y_t}{2}-f(\xi_t)+\phi(\xi_t)(a_t^2-\xi_t^2)\right\}+V(\mathbf Y_t) \tag{32} \end{align} \]
このように定義すると、\(R^*\) は
\[R^*=V(\mathbf Y_0)\tag{33}\]
となる
予測の式を立てる際に試行 \(t\) におけるある実数値を \(d_t\) 、大きさ \(t\times t\) の行列を \(\mathbf R_t\) とおき、
\[ \begin{align} d_t &= \frac{c_t}{16}\tag{34} \\ \mathbf R_t &= \begin{pmatrix}\mathbf A_t & \mathbf b_t \\ \mathbf b_t^T & c_t\tag{35}\end{pmatrix} \\ \mathbf R_T &= \left(\mathbf \Phi_T+\lambda\mathbf K_T\right)^{-1}\tag{36} \\ \mathbf R_{t-1} &= \mathbf A_t + \phi(\xi_t)\mathbf b_t\mathbf b_t^T\tag{37} \end{align} \]
と定義する。
定理 1
\[ V(\mathbf Y_t)=\frac{1}{4}\left(\mathbf Y_t-\frac{1}{2}\mathbf 1_t\right)^T\mathbf R_t\left(\mathbf Y_t-\frac{1}{2}\mathbf 1_t\right)-\mathbf F_t^T\mathbf 1_t+\Xi_t^T\mathbf\Phi_t\Xi_t+\sum_{s=t+1}^Td_s\tag{38} \]
\[ a_t=\frac{1}{2}\left(\mathbf Y_{t-1}-\frac{1}{2}\mathbf 1_{t-1}\right)^T\mathbf b_t\tag{39} \]
証明
\((38)\) の証明に帰納法を用いる。
The basis
\(V(\mathbf Y_T)\) を証明する。\((31)\) を再掲する。
\[V(\mathbf Y_T)=-L^*\]
\((24)\) を再掲する。
\[L^* =-\frac{1}{4}\left(\mathbf Y-\frac{1}{2}\mathbf 1\right)^T\left(\mathbf \Phi+\lambda \mathbf K\right)^{-1}\left(\mathbf Y-\frac{1}{2}\mathbf 1\right)+\mathbf F^T\mathbf 1 - \mathbf\Xi^T\mathbf\Phi\mathbf\Xi\]
これらの式に現在の記法に倣って添え字を加え、\((36)\) を使うと
\[V(\mathbf Y_T)=\frac{1}{4}\left(\mathbf Y_T-\frac{1}{2}\mathbf 1_T\right)^T\mathbf R_T\left(\mathbf Y_T-\frac{1}{2}\mathbf 1_T\right)-\mathbf F_T^T\mathbf 1_T + \mathbf\Xi_T^T\mathbf\Phi_T\mathbf\Xi_T\tag{40}\]
となり、 \((38)\) が成り立つ。
The steps
\(V(\mathbf Y_t)\) が成り立つと仮定したとき \(V(\mathbf Y_{t-1})\) が成立することを証明する。
\((32)\) に \((38)\) の \(V(\mathbf Y_t)\) を代入すると
\[ \begin{split} V(\mathbf Y_{t-1}) =& \min_{a_t}\max_{y_t}\left\{-a_ty_t+\frac{y_t}{2}-f(\xi_t)+\phi(\xi_t)(a_t^2-\xi_t^2)\right\} \\ &+\frac{1}{4}\left(\mathbf Y_t-\frac{1}{2}\mathbf 1_t\right)^T\mathbf R_t\left(\mathbf Y_t-\frac{1}{2}\mathbf 1_t\right)-\mathbf F_t^T\mathbf 1_t+\Xi_t^T\mathbf\Phi_t\Xi_t+\sum_{s=t+1}^Td_s \\ \end{split}\tag{41} \]
となる。\((35)\) の \(\mathbf R_t\) の定義より
\[ \begin{split} \left(\mathbf Y_t-\frac{1}{2}\mathbf 1_t\right)^T\mathbf R_t\left(\mathbf Y_t-\frac{1}{2}\mathbf 1_t\right) =& \left\{\begin{pmatrix}\mathbf Y_{t-1} \\ y_t\end{pmatrix}-\frac{1}{2}\begin{pmatrix}\mathbf 1_{t-1} \\ 1\end{pmatrix}\right\}^T\begin{pmatrix}\mathbf A_t & \mathbf b_t \\ \mathbf b_t^T & c_t\end{pmatrix}\left\{\begin{pmatrix}\mathbf Y_{t-1} \\ y_t\end{pmatrix}-\frac{1}{2}\begin{pmatrix}\mathbf 1_{t-1} \\ 1\end{pmatrix}\right\} \\ =&\left\{\begin{pmatrix}\mathbf Y_{t-1} \\ y_t\end{pmatrix}-\frac{1}{2}\begin{pmatrix}\mathbf 1_{t-1} \\ 1\end{pmatrix}\right\}^T\begin{pmatrix}\displaystyle\mathbf A_t\left(\mathbf Y_{t-1}-\frac{1}{2}\mathbf 1_{t-1}\right)+\mathbf b_t\left(y_t-\frac{1}{2}\right) \\\displaystyle \mathbf b_t^T\left(\mathbf Y_{t-1}-\frac{1}{2}\mathbf 1_{t-1}\right)+c_t\left(y_t-\frac{1}{2}\right)\end{pmatrix} \\ =&\left(\mathbf Y_{t-1}-\frac{1}{2}\mathbf 1_{t-1}\right)^T\mathbf A_t\left(\mathbf Y_{t-1}-\frac{1}{2}\mathbf 1_{t-1}\right) \\ &+2\left(y_t-\frac{1}{2}\right)\left(\mathbf Y_{t-1}-\frac{1}{2}\mathbf 1_{t-1}\right)^T\mathbf b_t \\ &+c_t\left(y_t-\frac{1}{2}\right)^2 \end{split}\tag{42} \]
が成り立ち、
\[\mathbf F_t^T\mathbf 1_t=\mathbf F_{t-1}^T\mathbf 1_{t-1}+f(\xi_t)\tag{43}\]
\[ \mathbf\Xi_t^T\mathbf\Phi_t\mathbf\Xi_t = \mathbf\Xi_t^T\begin{pmatrix}\mathbf\Phi_{t-1}\mathbf\Xi_{t-1} \\ \phi(\xi_t)\xi_t\end{pmatrix}=\mathbf\Xi_{t-1}^T\mathbf\Phi_{t-1}\mathbf\Xi_{t-1}+\phi(\xi_t)\xi_t^2\tag{44} \]
\[ \begin{align} V(\mathbf Y_{t-1}) &= \frac{1}{4}\left(\mathbf Y_{t-1}-\frac{1}{2}\mathbf 1_{t-1}\right)^T\mathbf A_t\left(\mathbf Y_{t-1}-\frac{1}{2}\mathbf 1_{t-1}\right)+\mathbf F_{t-1}^T\mathbf 1_{t-1}+\mathbf\Xi_{t-1}^T\mathbf\Phi_{t-1}\mathbf\Xi_{t-1} \end{align} \]
\(f(\xi_t)\) の \(\pm\) は？ \(L^*\) の証明をして、 \(\mathbf F_t^T\mathbf 1_t\) の正負が反対にならないか確かめる。