MathJaxの環境を確認しつつ使用中。プリアンブルが無いけどページ内で一回 newcommand を行えばずっと使えるみたい。便利。
\begin{equation*}
\newcommand\innerp[2]{\langle #1, #2 \rangle}
\newcommand\ve[1]{\boldsymbol{#1}}
\newcommand\parfrac[2]{\frac{\partial #1}{\partial #2}}
\end{equation*}
逐次的更新の件について。IRLSでは以下の評価関数 \(J(\ve{\beta})\) の最小化を考える。
\begin{equation*}
J(\ve{\beta}) = \sum^{M}_{i = 1} w_{i} (y_{i} - \innerp{\ve{\beta}}{\ve{x}_{i}})^{2}
\end{equation*}
ここで \(M\) は観測数。これは二次式だから評価関数は凸関数になる。早速 \(\ve{\beta}\) で偏微分してみると、
\begin{align*}
\parfrac{}{\ve{\beta}} J(\ve{\beta}) &= \sum^{M}_{i = 1} w_{i} 2 \left(- \frac{\partial}{\partial \ve{\beta}} \innerp{\ve{\beta}}{\ve{x}_{i}} \right) (y_{i} - \innerp{\ve{\beta}}{\ve{x}_{i}}) \\
&= -2 \sum^{M}_{i = 1} w_{i} (y_{i} - \innerp{\ve{\beta}}{\ve{x}_{i}}) \ve{x}_{i}
\end{align*}
\(\parfrac{}{\ve{\beta}} J(\ve{\beta}) = 0\) とおくと、
\begin{align*}
\sum_{i = 1}^{M} w_{i} \innerp{\ve{\beta}}{\ve{x}_{i}} \ve{x}_{i} &= \sum_{i = 1}^{M} w_{i} y_{i} \ve{x}_{i} \\
\iff
\left[ \ve{x}_{1} ... \ve{x}_{M} \right]
\left[
\begin{array}{c}
w_{1} \innerp{\ve{\beta}}{\ve{x}_{1}} \\
\vdots \\
w_{M} \innerp{\ve{\beta}}{\ve{x}_{M}}
\end{array}
\right]
&=
\left[ \ve{x}_{1} ... \ve{x}_{M} \right]
\left[
\begin{array}{c}
w_{1}y_{1} \\
\vdots \\
w_{M}y_{M}
\end{array}
\right]
\\
\iff
\left[ \ve{x}_{1} ... \ve{x}_{M} \right]
\left[
\begin{array}{ccc}
w_{1} & \dots & 0 \\
\vdots & \ddots & \vdots \\
0 & \dots & w_{M}
\end{array}
\right]
\left[
\begin{array}{c}
\innerp{\ve{\beta}}{\ve{x}_{1}} \\
\vdots \\
\innerp{\ve{\beta}}{\ve{x}_{M}}
\end{array}
\right]
&=
\left[ \ve{x}_{1} ... \ve{x}_{M} \right]
\left[
\begin{array}{ccc}
w_{1} & \dots & 0 \\
\vdots & \ddots & \vdots \\
0 & \dots & w_{M}
\end{array}
\right]
\left[
\begin{array}{c}
y_{1} \\
\vdots \\
y_{M}
\end{array}
\right]
\\
\iff
\left[ \ve{x}_{1} ... \ve{x}_{M} \right]
\left[
\begin{array}{ccc}
w_{1} & \dots & 0 \\
\vdots & \ddots & \vdots \\
0 & \dots & w_{M}
\end{array}
\right]
\left[
\begin{array}{c}
\ve{x}_{1}^{\mathsf{T}} \\
\vdots \\
\ve{x}_{M}^{\mathsf{T}}
\end{array}
\right]
\ve{\beta}
&=
\left[ \ve{x}_{1} ... \ve{x}_{M} \right]
\left[
\begin{array}{ccc}
w_{1} & \dots & 0 \\
\vdots & \ddots & \vdots \\
0 & \dots & w_{M}
\end{array}
\right]
\ve{y}
\\
\iff
\ve{X} \ve{W} \ve{X}^{\mathsf{T}} \ve{\beta} &= \ve{X} \ve{W} \ve{y}
\end{align*}
\(\ve{X}\ve{W}\ve{X}^{\mathsf{T}}\) が正則（TODO: \(\ve{X}\) が行フルランク、かつ \(\ve{W}\) が正則なら行けそうに見えるけど本当か？）の場合は閉形式で係数が求まる:
\begin{equation*}
\ve{\beta} = (\ve{X} \ve{W} \ve{X}^{\mathsf{T}})^{-1} \ve{X} \ve{W} \ve{y}
\end{equation*}
ここまでは一般論。さて、更新式に注目する。\(\beta_{j}\) だけで偏微分してみると、
\begin{align*}
\parfrac{J(\ve{\beta})}{\beta_{j}} &= \sum_{i = 1}^{M} \parfrac{}{\beta_{j}} w_{i} (y_{i} - \innerp{\ve{\beta}}{\ve{x}_{i}})^{2} \\
&= -2 \sum_{i = 1}^{M} w_{i} (\ve{x}_{i})_{j} (y_{i} - \innerp{\ve{\beta}}{\ve{x}_{i}})
\end{align*}
残差のL1ノルム最小化を考えるときは \(w_{i} = \frac{1}{|y_{i} - \innerp{\ve{\beta}}{\ve{x}_{i}}|}\) とおくので代入すると、
\begin{equation*}
\parfrac{J(\ve{\beta})}{\beta_{j}} = -2 \sum_{i = 1}^{M} (\ve{x}_{i})_{j} \mathrm{sign}(y_{i} - \innerp{\ve{\beta}}{\ve{x}_{i}})
\end{equation*}
瞬間値（ \(M=1\) とする）を考えるとSigned-LMSの更新式そのものになっている。 和を取ると平均操作に近いから、LMSアルゴリズムと考えていることは同じ。
\(\parfrac{J(\ve{\beta})}{\beta_{j}}\) を更に \(\beta_{k}\) で偏微分してみると、
\begin{align*}
\frac{\partial^{2} J(\ve{\beta})}{\partial \beta_{j} \partial \beta_{k}} &= -2 \sum_{i = 1}^{M} w_{i} (\ve{x}_{i})_{j} \parfrac{}{\beta_{k}} (y_{i} - \innerp{\ve{\beta}}{\ve{x}_{i}}) \\
&= 2 \sum_{i = 1}^{M} w_{i} (\ve{x}_{i})_{j} (\ve{x}_{i})_{k} \\
&= 2 \left[ (\ve{x}_{1})_{j} \dots (\ve{x}_{M})_{j} \right]
\left[
\begin{array}{c}
w_{1} (\ve{x}_{1})_{k} \\
\vdots \\
w_{M} (\ve{x}_{M})_{k}
\end{array}
\right]
= 2 \left[ (\ve{x}_{1})_{j} \dots (\ve{x}_{M})_{j} \right] \ve{W}
\left[
\begin{array}{c}
(\ve{x}_{1})_{k} \\
\vdots \\
(\ve{x}_{M})_{k}
\end{array}
\right]
\end{align*}
2次式が出てくるのがわかる（\(\ve{W}\) は計量だ）。そして \((\ve{H})_{jk} = \frac{\partial^{2} J(\ve{\beta})}{\partial \beta_{j} \partial \beta_{k}}\) なるヘッセ行列 \(\ve{H}\) は以下:
\begin{equation*}
\ve{H} = 2 \ve{X} \ve{W} \ve{X}^{\mathsf{T}}
\end{equation*}
ヘッセ行列の性質により関数の最小値・最大値の存在がわかる。対称行列なのは間違いない（\((\ve{X})_{ij} = (\ve{X})_{ji}\) は自明）。（固有値分解とは見れない。\(\ve{H}\) は \(N \times N\) の行列であるのに対して、\(\ve{X}\) は \(N \times M\) の行列。\(\ve{X} \ve{X}^{\mathsf{T}}\) は平均化、除算を抜いた分散共分散行列になり半正定値行列。）また、任意のベクトル \(\ve{v}\) に対して、
\begin{align*}
\ve{v}^{\mathsf{T}} \ve{X} \ve{W} \ve{X}^{\mathsf{T}} \ve{v} &= \ve{v}^{\mathsf{T}} \ve{X} \ve{W}^{1/2} \ve{W}^{1/2} \ve{X}^{\mathsf{T}} \ve{v} \\
&= (\ve{W}^{1/2} \ve{X}^{\mathsf{T}} \ve{v})^{\mathsf{T}} \ve{W}^{1/2} \ve{X}^{\mathsf{T}} \ve{v} \\
&= || \ve{W}^{1/2} \ve{X}^{\mathsf{T}} \ve{v} ||_{2}^{2} \geq 0
\end{align*}
だから、\(\ve{W}\) が半正定値（\(\iff\) すべての重みが非負）ならばヘッセ行列は半正定値行列で、極小値が最小値になる。また、\(J(\ve{\beta})\) は凸関数（半正定値だから狭義の凸関数ではない）。
もう少しヘッセ行列を見る。ヘッセ行列を上手く使えたらニュートン法で解けそうな気がして。
\begin{equation*}
(\ve{H})_{jk} = 2 \sum_{i = 1}^{M} w_{i} (\ve{x}_{i})_{j} (\ve{x}_{i})_{k}
\end{equation*}
より、スペクトル分解的に見ると、
\begin{align*}
\frac{1}{2} \ve{H} &=
w_{1} \left[
\begin{array}{ccc}
(\ve{x}_{1})_{1}^{2} & \dots & (\ve{x}_{1})_{1} (\ve{x}_{1})_{N} \\
\vdots & \ddots & \vdots \\
(\ve{x}_{1})_{N} (\ve{x}_{1})_{1} & \dots & (\ve{x}_{1})_{N}^{2} \\
\end{array}
\right]
+ \dots +
w_{M} \left[
\begin{array}{ccc}
(\ve{x}_{M})_{1}^{2} & \dots & (\ve{x}_{M})_{1} (\ve{x}_{M})_{N} \\
\vdots & \ddots & \vdots \\
(\ve{x}_{M})_{N} (\ve{x}_{M})_{1} & \dots & (\ve{x}_{M})_{N}^{2} \\
\end{array}
\right] \\
&= w_{1} \ve{x}_{1} \ve{x}_{1}^{\mathsf{T}} + \dots + w_{M} \ve{x}_{M} \ve{x}_{M}^{\mathsf{T}} \\
&= \sum_{i = 1}^{M} w_{i} \ve{x}_{i} \ve{x}_{i}^{\mathsf{T}}
\end{align*}
- 信号処理的には \(\ve{x}_{1}, \ve{x}_{2}, \dots \ve{x}_{M}\) は系列で現れる。
- LMSフィルタでは \(i = 1\) の時だけを考えていたと考えられれる。 \(i = 2,\dots,M\) のときの影響は少ないのではないかと思う。
- FIRフィルタを考えるのならば、各 \(\ve{x}_{1}\) は入ってきた1次元信号データを時系列順に並べたものだから、直前のベクトル \(\ve{x}_{2}\) を使えそうな構造に見える。
- 上の仮定を使ってヘッセ行列の逆行列 \(\ve{H}^{-1}\) を逐次近似計算できない？
- 分散共分散行列がほぼヘッセ行列になってるけどこれは何？
- 金谷さんの解説 にそれとなく解説がある。フィッシャー情報行列との関連もある。。。クラメル・ラオの下限についてわかりやすい説明あり。
- 最尤法 にもそれとなく解説あり。
- 奥村さん もあり。観測からヘッセ行列を構成できる？
そして自然勾配のアイディアが出てくる。自然勾配を使ったLMSアルゴリズムは…あった…
TODO:
- 前のMTGで言われたことの整理
- 分散行列、ヘッセ行列、フィッシャー情報行列、自然勾配の整理
- OMPが気になる。試してみたい。