線形予測法のソースを表示

'''線形予測法'''（せんけいよそくほう、{{lang-en-short|linear prediction}}）は、[[離散信号]]の将来の値をそれまでの標本群の[[線型写像]]として予測する数学的操作である。

[[デジタル信号処理]]では、線形予測法を[[線形予測符号]] (LPC) と呼び、[[デジタルフィルタ]]のサブセットと見ることができる。（[[数学]]の一分野としての）[[システム分析]]では、線形予測法は[[モデル (自然科学)|数学的モデル]]や[[最適化問題|最適化]]の一種と見ることができる。

== モデル ==
系列 <math>x(n)</math> に対して <math>p</math> 次の線形予測法で推定した値 <math>\widehat{x}(n)</math> は予測係数 <math>a_i</math> を用いて次で表される。

:<math>\widehat{x}(n)
= -(a_1 x(n-1) + a_2 x(n-2) + ... + a_p x(n-p))
= -\sum_{i=1}^p a_i x(n-i)
= - \boldsymbol{a_{1:p}}^{\top} \boldsymbol{x_{n-1:n-p}} </math>

すなわち線形予測法とは <math>p</math> 次の過去系列を用いた[[線形回帰]]である。

この誤差は多次元信号においてベクトル[[ノルム]] <math>\|.\|</math> を用いて次のように定義される。

: <math>e(n) = \|x(n) - \widehat{x}(n)\|\,</math>

== パラメータ推定 ==
線形予測法における予測係数 <math>a_i</math> には様々な推定方法が存在する。

最適化においてパラメータ <math>a_i</math> の典型的な選択法は、[[二乗平均平方根]]基準であり、これを[[自己相関]]基準とも呼ぶ。これは、以下の式で得られる二乗誤差 E[e<sup>2</sup>(n)] の期待値を最小化する手法である。

:<math>\sum_{i=1}^p a_i R(i-j) = -R(j)</math>

ここで 1 &le; ''j'' &le; ''p'' であり、''R'' は信号 ''x''<sub>''n''</sub> の[[自己相関]]であり、次のように定義される。

:<math>\ R(i) = E\{x(n)x(n-i)\}\,</math>

ここで ''E'' は[[期待値]]である。多次元の場合、これは[[Lp空間|L<sub>2</sub>ノルム]]を最小化することに対応する。

上の式を[[最小二乗法|正規方程式]]または Yule-Walker 方程式と呼ぶ。行列形式でこの方程式を表すと、次のようになる。

:<math>Ra = -r,\,</math>

ここで、自己相関行列 ''R'' は対称な[[テプリッツ行列]]であり、その要素は ''r''<sub>''i'',''j''</sub> = ''R''(''i'' &minus; ''j'') である。また、ベクトル ''r'' は自己相関ベクトル ''r''<sub>''j''</sub> = ''R''(''j'') であり、ベクトル ''a'' は係数ベクトルである。

より汎用的な形式として、次を最小化する方式もある。

:<math>e(n) = x(n) - \widehat{x}(n) = x(n) + \sum_{i=1}^p a_i x(n-i) = \sum_{i=0}^p a_i x(n-i)</math>

ここで、係数 <math>a_i</math> について <math>a_0=1</math> とし、自明な解を防ぐのが一般的である。これにより上述と同じになるが、正規方程式は以下のようになる。

:<math>\ Ra = [1, 0, ... , 0]^{\mathrm{T}}</math>

ここで、インテックス ''i'' の範囲は 0 から ''p''、''R'' は (''p''&nbsp;+&nbsp;1) 行 (''p''&nbsp;+&nbsp;1) 列の行列である。

パラメータの最適化は大きな問題であり、他にも様々な手法が提案されている。

その中でも自己相関手法が最もよく使われており、例えば[[GSM]]での音声符号化に使われている。

行列方程式 ''Ra'' = ''r'' の解の計算は、比較的時間のかかる処理である。[[ガウスの消去法]]を使った解法が最も古くからあるが、''R'' と ''r'' の対称性をうまく利用していない。より高速なアルゴリズムとして、1947年に Norman Levinson が考案した[[レビンソン再帰]]という再帰的解法がある。その後、Philippe Delsarte らが、これを改良した分割レビンソン再帰というアルゴリズムを発表した。これは、乗除算回数を約半分にしたもので、パラメータベクトルの特殊な対称性をそれぞれの再帰で利用する。

=== 二乗予測誤差 ===
元信号を用いた推定法の1つが予測誤差の二乗を最小化する手法である<ref>"最小二乗誤差推定による定式化" p.7 of 亀岡. (2014). ''[http://hil.t.u-tokyo.ac.jp/~kameoka/aa/AA14_03.pdf 応用音響学 第3回]''. 東京大学.</ref>。
線形予測値 <math>\widehat{x_n}</math> と真の信号 <math>x_n</math> の間の予測誤差 <math>e_n</math> は <math>0</math> 次の係数 <math>a_0 = 1</math> を用いて次で表される。
:<math>e_n
= 1 x_n - \widehat{x_n}
= a_0 x_n + \boldsymbol{x_{n-1:n-P}}{}^{\top} \boldsymbol{a_{1:P}}
= \boldsymbol{x_{n:n-P}}{}^{\top} \boldsymbol{a_{0:P}}</math>
ここで全時点にわたる予測誤差の二乗和をもって誤差関数 <math>e = \sum_{n}^N {e_n}^2
</math> とし、これを最小化して予測係数を推定する。最小値において予測係数の偏微分は <math>0
</math> になるので <math>a_q \ (1 \leq q \leq P)
</math> において次が成立する。<math>{\partial e \over \partial a_q}
= \sum_{n}^N{\partial\over\partial a_q} (\boldsymbol{x_{n:n-P}}{}^{\top} \boldsymbol{a_{0:P}})^2
= \sum_{n}^N 2 x_{n-q} (\boldsymbol{x_{n:n-P}}{}^{\top} \boldsymbol{a_{0:P}})
= 2 \sum_{n}^N \sum_{p=0}^P x_{n-q} x_{n-p} a_p
= 2 \sum_{p=0}^P a_p \sum_{n}^N x_{n-q} x_{n-p}
= 0
</math>

ここで <math>\sum_{n}^N {x_{n-q} x_{n-p}}
</math> がラグ <math>\left\vert p-q \right\vert
</math> の[[自己相関#信号処理|自己相関関数]]になっていることから <math>r_{\left\vert p-q \right\vert}
</math> と表記すると <math>\sum_{p=0}^P r_{\left \vert p-q \right \vert } a_p
= 0
</math> となり、ベクトル表記すると <math>\boldsymbol{r_{0-q :  P-q}} {}^{\top} 
 \boldsymbol{a_{0:P}} = 0


</math> となる。<math>1 \leq q \leq P
</math> 全てを行列に集約すると以下になる。

<math>\begin{pmatrix}
  r_1 & r_0     & r_1     & ... & r_{P-1} \\
  r_2 & r_1     & r_0     & ... & r_{P-2} \\
  ... & ...     & ...     & ... & ...     \\
  r_P & r_{P-1} & r_{P-2} & ... & r_0     \\
\end{pmatrix}
\begin{pmatrix}
  1   \\
  a_1 \\
  a_2 \\
  ... \\
  a_P \\
\end{pmatrix}
= \boldsymbol{0}
</math>

すなわちユールウォーカー方程式に帰着する。この <math>p
</math> 元連立一次方程式を解くことで予測係数が求まる。解くにあたって[[ガウスの消去法]]などの汎用解法が利用できるが、この行列は[[テプリッツ行列]]を導くからLevinson再帰を用いた高速解法が存在する。実務的にはこれがLPCでよく利用される。

=== スペクトル変換 ===
信号の符号化（エンコード）では元信号を用いて予測係数を得ることが有用であるが、信号生成タスクでは元信号を利用することができない。そのような場合に利用可能な、元信号を直接用いない推定法の1つがスペクトルの変換である。この手法ではスペクトルを自己相関関数へ変換しユールウォーカー方程式へ持ち込みこれを解くことで予測係数を推定する。

この手法の中心にある原理は[[ウィーナー＝ヒンチンの定理]]である。この定理は[[スペクトル密度#パワースペクトル密度|パワースペクトル密度]]のフーリエ逆変換が[[自己相関#信号処理|自己相関関数]]となることを示している。

ゆえに[[スペクトログラム#%E3%83%A1%E3%83%AB%E3%82%B9%E3%83%9A%E3%82%AF%E3%83%88%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0|メルスペクトログラム]]や[[ケプストラム#メル周波数ケプストラム係数|MFCC]]を[[スペクトル密度#パワースペクトル密度|パワースペクトル密度]]へ変換し、それにフーリエ逆変換を適用、得られた自己相関で[[テプリッツ行列]]を構成しユールウォーカー方程式を解くことで予測係数が得られる<ref>"The prediction coefficients <math>a_k
</math> are computed by first converting ... Bark-frequency cepstrum into a linear-frequency power spectral density ... then converted to an autocorrelation using an inverse FFT. From the auto-correlation, the Levinson-Durbin algorithm is used to compute the predictor" Valin & Skoglund. (2018). ''[[arxiv:1810.11846|LPCNet: Improving Neural Speech Synthesis Through Linear Prediction]]''. arxiv.</ref>。

== 係数表現 ==
線形予測における係数は複数の形式で表現できる<ref>"Linear predictive coefficients (LP coefficients) have other representations: line spectral frequencies (LSF) ... etc" Tamanna Islam. (2000). ''[http://www.mmsp.ece.mcgill.ca/Theses/2000/IslamT2000.pdf Interpolation of Linear Prediction Coefficients for Speech Coding]''. Master thesis of Engineering. McGill University. p.20.</ref>。以下は代表的な係数表現である。

* 線形予測係数（{{lang-en-short|linear predictive coefficients}}; LP coefficients）: 定義式における <math>a_i</math>。ノイズに対する脆弱性が知られる
* line spectral frequencies; LSF
* reflection coefficients; RC
* autocorrelations; AC
* [[Log Area Ratio|ログ面積比]]（{{lang-en-short|log area ratios}}; LAR）
* arcsine of reflection coefficients; ASRC
* impulse responses of LP synthesis filter; IR

係数表現によってノイズ耐性や計算量の特性が異なる。例えば[[音声符号化]]における線形予測（[[線形予測符号|線形予測符号化]]）ではアナログ回線に由来するノイズへ耐性を持たせるために、LP coefficients 以外の係数表現がしばしば用いられてきた。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
* [[予測区間]]
* [[線形予測符号]]
* [[Warped Linear Predictive Coding]]

== 参考文献 ==
* G. U. Yule. On a method of investigating periodicities in disturbed series, with special reference to wolfer’s sunspot numbers. Phil. Trans. Roy. Soc., 226-A:267–298, 1927.
* J. Makhoul. Linear prediction: A tutorial review. Proceedings of the IEEE, 63 (5):561–580, April 1975.
* M. H. Hayes. Statistical Digital Signal Processing and Modeling. J. Wiley & Sons, Inc., New York, 1996.

== 外部リンク ==
* [http://labrosa.ee.columbia.edu/matlab/rastamat/ PLP and RASTA (and MFCC, and inversion) in Matlab]

{{DEFAULTSORT:せんけいよそくほう}}
[[Category:信号処理]]
[[Category:音声処理]]
[[Category:時系列分析]]