LPCの多段構成執筆(3)

\begin{equation*} \newcommand\ve[1]{\boldsymbol{#1}} \newcommand\mean[2]{\mathrm{E}_{#1} \left[ #2 \right]} \newcommand\parfrac[2]{\frac{\partial #1}{\partial #2}} \end{equation*}

論文書きが一旦落ち着きそうなのを見て、学習の高速化を考えている。ダイレクトに微分を計算して解くのは、やはり解析的でないこともありいい方向じゃない。

L1ロスの最適化（しかもARモデルで）を調べていたら、亀岡さんの補助関数法を思い出した（ スパース表現に基づく音声音響符号化 ）。これ、ずっと気になっていたがLPCだし気にしていなかった。結果としてはかなり有用そうで、試してみたい。最急勾配よりはよい性質がある（目的関数値が単調減少する。目的関数は凸だから大域最適値への収束が保証）。

以下に概要をまとめよう。

定義（補助関数）
\(\ve{\theta}\) をパラメータとする目的関数 \(D(\ve{\theta})\) に対し \(D(\ve{\theta}) = \min_{\ve{\alpha}} G(\ve{\theta}, \ve{\alpha})\) が成り立つとき、 \(G(\ve{\theta}, \ve{\alpha})\) を \(D(\ve{\theta})\) の補助関数(Auxiliary Function)、 \(\ve{\alpha}\) を補助変数と呼ぶ。

補助関数の基本的かつ重要な定理が以下。

定理

補助関数 \(G(\ve{\theta}, \ve{\alpha})\) に対し、以下の手続き

\begin{align*} \ve{\alpha} &\leftarrow \underset{\ve{\alpha}}{\mathrm{argmin}} \ G(\ve{\theta}, \ve{\alpha}) \tag{1} \\ \ve{\theta} &\leftarrow \underset{\ve{\theta}}{\mathrm{argmin}} \ G(\ve{\theta}, \ve{\alpha}) \tag{2} \end{align*}

を繰り返すと、目的関数の値は単調減少する。

（証明） \((\ve{\theta}^{(l)}, \ve{\alpha}^{(l)})\) から \((\ve{\theta}^{(l+1)}, \ve{\alpha}^{(l+1)})\) と更新したときに、

\begin{align*} D(\ve{\theta}^{(l)}) &:= \min_{\ve{\alpha}} G(\ve{\theta}^{(l)}, \ve{\alpha}) \\ &= G(\ve{\theta}^{(l)}, \ve{\alpha}^{(l+1)}) \quad (\because (1)) \\ &\geq G(\ve{\theta}^{(l+1)}, \ve{\alpha}^{(l+1)}) \quad (\because (2)) \\ &\geq D(\ve{\theta}^{(l+1)}) \quad (\because 補助関数の定義) \end{align*}

（証明終）

これをARモデルの絶対値誤差問題

\begin{equation*} J(\ve{a}) = \mean{}{\left| s_{t} - \sum_{i = 1}^{L} a_{i} s_{t-i} \right|} \end{equation*}

に適用することを考える。今、

\begin{equation*} |x| \leq \frac{x^{2}}{2 |w|} + \frac{|w|}{2} \end{equation*}

だから（ \(\because \frac{x^{2}}{2 |w|} + \frac{|w|}{2} - |x| = \frac{1}{2 |w|}(x^{2} + |w|^{2} - 2|w|x) = (x - |w|)^{2} \geq 0\) 、 \(x = w\) のとき等号成立）、補助変数 \(w_{t}\) を導入すると、

\begin{align*} J(\ve{a}) &= \mean{}{\left| s_{t} - \sum_{i = 1}^{L} a_{i} s_{t-i} \right|} \\ &\leq \mean{}{\frac{1}{2|w_{t}|} \left( s_{t} - \sum_{i = 1}^{L} a_{i} s_{t-i} \right)^{2} + \frac{|w_{t}|}{2}} = \mean{}{\frac{1}{2|w_{t}|} \left( s_{t} - \sum_{i = 1}^{L} a_{i} s_{t-i} \right)^{2}} + \frac{1}{2} \mean{}{|w_{t}|} \end{align*}

となる。そこで補助関数 \(I(\ve{a}, \ve{w})\) を

\begin{equation*} I(\ve{a}, \ve{w}) := \mean{}{\frac{1}{2|w_{t}|} \left( s_{t} - \sum_{i = 1}^{L} a_{i} s_{t-i} \right)^{2}} + \frac{1}{2} \mean{}{|w_{t}|} \end{equation*}

と定義する。 \(w_{t} = s_{t} - \sum_{i = 1}^{L} a_{i} s_{t-i}\) とすれば、

\begin{equation*} I(\ve{a}, \ve{w}) = \mean{}{\frac{1}{2|w_{t}|} w_{t}^{2}} + \frac{1}{2} \mean{}{|w_{t}|} = \mean{}{|w_{t}|} = J(\ve{a}) \end{equation*}

だから、この \(w_{t}\) は \(\underset{\ve{w}}{\mathrm{argmin}} \ I(\ve{a}, \ve{w})\) を満たしている。一方、 \(\ve{w}\) を固定したとき、

\begin{align*} \parfrac{}{a_{j}} I(\ve{a}, \ve{w}) &= \mean{}{\frac{1}{2|w_{t}|} 2 \left( s_{t} - \sum_{i = 1}^{L} a_{i} s_{t-i} \right)(-s_{t-j})} \\ &= \mean{}{\frac{1}{|w_{t}|} \left( \sum_{i = 1}^{L} a_{i} s_{t-i} s_{t-j} - s_{t} s_{t-j} \right)} \\ &= \sum_{i = 1}^{L} a_{i} \mean{}{\frac{1}{|w_{t}|} s_{t-i} s_{t-j}} - \mean{}{\frac{1}{|w_{t}|} s_{t} s_{t-j}} \\ &= \sum_{i = 1}^{L} a_{i} r_{ij} - r_{0j} \end{align*}

ここで \(r_{ij} := \mean{}{\frac{1}{|w_{t}|} s_{t-i} s_{t-j}}\) とおいている。さて、 \(\parfrac{}{a_{j}} I(\ve{a}, \ve{w}) = 0\ (j = 1,...,L)\) とおいて \(\ve{a}\) について解くと、

\begin{equation*} \left[ \begin{array}{ccc} r_{11} & ... & r_{1L} \\ \vdots & \ddots & \vdots \\ r_{L1} & ... & r_{LL} \\ \end{array} \right] \left[ \begin{array}{c} a_{1} \\ \vdots \\ a_{L} \\ \end{array} \right] = \left[ \begin{array}{c} r_{01} \\ \vdots \\ r_{0L} \\ \end{array} \right] \end{equation*}

だから、上記の方程式を満たす \(\ve{a}\) が \(I(\ve{a}, \ve{w})\) を最小にする。なお、 \((\ve{R})_{ij} = r_{ij}\) なる行列をおくと、 \(r_{ij} = r_{ji}\) だから \(\ve{R}\) は対称で、任意の \(\ve{x} \neq \ve{0}\) に対し、 \(\ve{s}_{t} := [ s_{t-1} ... s_{t-L} ]^{\mathsf{T}}\) とおくと、

\begin{equation*} \ve{x}^{\mathsf{T}} \ve{R} \ve{x} = \ve{x}^{\mathsf{T}} \mean{}{\frac{1}{|w_{t}|} \ve{s}_{t} \ve{s}_{t}^{\mathsf{T}}} \ve{x} = \mean{}{\frac{1}{|w_{t}|} (\ve{x}^{\mathsf{T}} \ve{s}_{t})^{2}} \geq 0 \end{equation*}

だから \(\ve{R}\) は半正定値なので、コレスキー分解などで高速に解ける（注： \(r_{00} = \mean{}{\frac{1}{|w_{t}|} s_{t}^{2}} \neq r_{11} = \mean{}{\frac{1}{|w_{t}|} s_{t-1}^{2}}\) なのでPersymmetric行列でなく、Levinson-Durbinは使えない）。

よって、次のアルゴリズムにより \(J(\ve{a})\) を単調減少させられる。

  1. \(\ve{a}\) を初期値に設定（Lebinson-Durbinとかで決める？）
  2. \(w_{t} \leftarrow s_{t} - \sum_{i=1}^{L} a_{i} s_{t-i}\) （予測）
  3. \(r_{ij} \leftarrow \mean{}{\frac{1}{|w_{t}|} s_{t-i} s_{t-j}}\)
  4. \(\ve{a} \leftarrow \left[ \begin{array}{ccc} r_{11} & ... & r_{1L} \\ \vdots & \ddots & \vdots \\ r_{L1} & ... & r_{LL} \\ \end{array} \right]^{-1} \left[ \begin{array}{c} r_{01} \\ \vdots \\ r_{0L} \\ \end{array} \right]\) （コレスキー分解などで解く）
  5. 2.に戻る

\(J(\ve{a})\) は \(\ve{a}\) に関して凸なので、この問題に関しては上記アルゴリズムは大域最適解に収束する。

例えば、提案するモデルにおいて順行方向か逆方向に2, 3, 4を実行するのは、BPの代替手段としてあり。

ちょっと試している。初期値についてはゼロでもLevinson-Durbinでもあんまり最終的な結果に差は出てこない。また、論文では平均ではなく和で計算しているが、和では安定しない（係数行列の要素が大きくなる+解が収束しない）傾向。 LPCNet（仮。名称変更予定）でLevinson-Durbinを入れ替えてみた（NNの構造選択と初期値設定で上記手法を使った）ら、割と劇的な平均絶対値残差減少が見られた。ひとまず機能追加。

補助関数の文献