# Regret 最小化の概要
## 設定: 確率質量関数
*y**t* は *t* ごとに存在するパラメータ
*θ**t* ∈ \[0, 1\] をもつベルヌーイ分布に従う値とする。
ベルヌーイ分布の確率質量関数 *p*(*y**t* ∣ *θ**t*)
は
*p*(*y**t* ∣ **w***t*, **x***t*) = *θ**t**y**t*(1 − *θ**t*)1 − *y**t*
である。
ロジスティックシグモイド関数の逆関数として知られるロジット変換 *a* は
$$a(\theta)=\ln\frac{\theta}{1-\theta}\tag{2}$$
と定義され、これを *θ**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}
$$
となる。この変換によって確率質量関数のパラメータは
*θ**t* ∈ \[0, 1\] から *a**t* ∈ (−∞, +∞) となる。
## 設定: ロジスティック誤差関数
(4) から導出される負の対数尤度
−ln *p*(*y**t* ∣ *a**t*)
によるロジスティック誤差関数を
*E*(*y**t*, *a**t*) = −*y**t**a**t* + ln (1 + *e**a**t*)
と定義する。
## 設定: *a**t* の系列変化が滑らか
*a**t* の系列の変化が滑らかであるという事前知識を考慮した式
$$\lambda \sum\_{t=1}^{T+1}(a_t-a\_{t-1})^2\tag{6}$$
を導入する。*λ* は予測する系列の滑らかさの度合いを決める係数である。
## 設定: リグレット
リグレットとは、オフライン予測の結果とオンライン予測の予測結果それぞれの損失を比較し、相対的に評価する指標である。
オンライン予測の予測結果の系列を
*a*1, *a*2, …, *a**T* とし、損失関数を
*l*(*y**t*, *a**t*)
とする。オフライン予測の予測結果の系列を
*â*1, *â*2, …, *â**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)
の第２項はスムーザの目的関数であり、オフライン予測の最適な損失を表している。なお、ここで
*â*0, *â**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}$$
を解く。
## 本研究との兼ね合い
*θ**t* は
*σ**t* = *σ*(**w***t**T***x***t*)
と対応する。
*a**t* は
**w***t**T***x***t* と対応する。
(12) は、本研究では
*E*(*y**t*, **w***t*) = −*y**t***w***t**T***x***t* + ln (1 + *e***w***t**T***x***t*)
と表される。
## 損失関数の導出
*f*(*a*) を
*f*(*a*) = ln (*e**a*/2 + *e*−*a*/2)
とおく。ここで、*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) ≤ 0
となるため、 *g*(*a*2) は凹関数である。これにより、
*g*(*a*2) ≤ *g*(*ξ*2) + *g*′(*ξ*2)(*a*2 − *ξ*2)
であるから、 *g*′(*a*2) = *ϕ*(*a*) とすると
*f*(*a*) ≤ *f*(*ξ*) + *ϕ*(*ξ*)(*a*2 − *ξ*2)
が成り立つ。
$$
\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}
$$
ここで、 *â*0, *â**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}$$
とする。*α* は任意の定数である。
ここで、ある時点における minimax 損失 *V*\* を
*V*\* = min*a*max*y**V*(*a*, *y*)
とする。
∀*y*0 ∈ {0, 1}, *V*\* = *V*(*α*, *y*0) = *ϕ*(*ξ*)*α*2
## オンライン予測式の導出
(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*(**Y**0)
となる
予測の式を立てる際に試行 *t* におけるある実数値を *d**t*
、大きさ *t* × *t* の行列を **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*(**Y***T*) を証明する。(31) を再掲する。
*V*(**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*(**Y***t*) が成り立つと仮定したとき
*V*(**Y***t* − 1) が成立することを証明する。
(32) に (38) の *V*(**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) の **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}
$$
が成り立ち、
**F***t**T***1***t* = **F***t* − 1*T***1***t* − 1 + *f*(*ξ**t*)
$$
\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*(*ξ**t*) の ± は？ *L*\* の証明をして、
**F***t**T***1***t*
の正負が反対にならないか確かめる。