最小二乗フィルタ

Statistical algorithm

最小平均二乗法（LMS ）アルゴリズムは、誤差信号（目標信号と実際の信号の差）の最小平均二乗を生成するフィルタ係数を求めることで、所望のフィルタを模倣する適応フィルタの一種です。これは、フィルタが現時点での誤差に基づいてのみ適応されるという点で、確率的勾配降下法です。これは、1960年にスタンフォード大学のバーナード・ウィドロウ教授と彼の最初の博士課程の学生であるテッド・ホフによって、単層ニューラルネットワークの研究に基づいて発明されました。具体的には、彼らは勾配降下法を用いてADALINEにパターン認識を訓練し、このアルゴリズムを「デルタルール」と呼びました。彼らはこのルールをフィルタに適用することで、LMSアルゴリズムが生まれました。

問題の定式化

この図はフィルタの様々な部分を示しています。は入力信号であり、これはを用いてマッチングさせたい未知のフィルタによって変換されます。未知のフィルタからの出力は であり、これはノイズ信号 と干渉してを生成します。次に誤差信号が計算され、適応フィルタにフィードバックされて、平均二乗誤差 を最小化するようにパラメータが調整されます。 ${\displaystyle x}$ ${\displaystyle h}$ ${\displaystyle {\hat {h}}}$ ${\displaystyle y}$ ${\displaystyle \nu }$ ${\displaystyle d=y+\nu }$ ${\displaystyle e=d-{\hat {y}}=y+\nu -{\hat {y}}}$ ${\displaystyle \sum e^{2}/n}$

ウィーナーフィルタとの関係

因果ウィーナーフィルタの実現は、信号処理領域を除けば、最小二乗推定の解に類似している。入力行列と出力ベクトルの最小二乗解は、 ${\displaystyle \mathbf {X} }$ ${\displaystyle {\boldsymbol {y}}}$

${\displaystyle {\boldsymbol {\hat {\beta }}}=(\mathbf {X} ^{\mathbf {T} }\mathbf {X} )^{-1}\mathbf {X} ^{\mathbf {T} }{\boldsymbol {y}}.}$

有限インパルス応答（FIR）最小平均二乗フィルタはウィーナーフィルタと関連しているが、前者の誤差基準を最小化するという問題は、相互相関や自己相関に依存しない。その解はウィーナーフィルタの解に収束する。ほとんどの線形適応フィルタリング問題は、上記のブロック図を用いて定式化できる。つまり、未知のシステムを同定し、適応フィルタは観測可能な信号、、のみを用いて、フィルタを に可能な限り近づけるように適応しようとする。ただし、 、、 は直接観測できない。その解はウィーナーフィルタと密接に関連している。 ${\displaystyle \mathbf {h} (n)}$ ${\displaystyle {\hat {\mathbf {h} }}(n)}$ ${\displaystyle \mathbf {h} (n)}$ ${\displaystyle x(n)}$ ${\displaystyle d(n)}$ ${\displaystyle e(n)}$ ${\displaystyle y(n)}$ ${\displaystyle v(n)}$ ${\displaystyle h(n)}$

記号の定義

${\displaystyle n}$現在の入力サンプルの番号です

${\displaystyle p}$フィルタタップの数

${\displaystyle \{\cdot \}^{H}}$（エルミート転置または共役転置）

${\displaystyle \mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p+1)\right]^{T}}$

${\displaystyle \mathbf {h} (n)=\left[h_{0}(n),h_{1}(n),\dots ,h_{p-1}(n)\right]^{T},\quad \mathbf {h} (n)\in \mathbb {C} ^{p}}$

${\displaystyle y(n)=\mathbf {h} ^{H}(n)\cdot \mathbf {x} (n)}$

${\displaystyle d(n)=y(n)+\nu (n)}$

${\displaystyle {\hat {\mathbf {h} }}(n)}$推定フィルタ。nサンプル後のフィルタ係数の推定値として解釈する。

${\displaystyle e(n)=d(n)-{\hat {y}}(n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\cdot \mathbf {x} (n)}$

アイデア

LMSフィルタの基本的な考え方は、フィルタの重みを最適なフィルタ重みに収束するように更新することで、最適なフィルタ重みに近づくことです。これは勾配降下法に基づいています。このアルゴリズムは、まず小さな重み（ほとんどの場合はゼロ）を仮定し、各ステップで平均二乗誤差の勾配を求めることで重みを更新します。つまり、MSE勾配が正の場合、同じ重みを以降の反復処理で使用すると誤差が正に増加し続けることを意味し、重みを減らす必要があります。同様に、勾配が負の場合、重みを増やす必要があります。重みの更新式は ${\displaystyle (R^{-1}P)}$

${\displaystyle W_{n+1}=W_{n}-\mu \nabla \varepsilon [n],}$

ここで、は平均二乗誤差を表し、は学習率係数です。 ${\displaystyle \varepsilon }$ ${\displaystyle \mu }$

負の符号は、誤差の傾斜を下って、誤差を最小化するフィルタの重みを見つけることを示しています。 ${\displaystyle \varepsilon }$ ${\displaystyle W_{i}}$

フィルタ重みの関数としての平均二乗誤差は二次関数であり、平均二乗誤差を最小化する極値は1つしかなく、これが最適な重みです。したがって、LMSは平均二乗誤差対フィルタ重み曲線を上昇/下降することで、この最適な重みに近づきます。

導出

LMSフィルタの考え方は、最急降下法を用いてコスト関数を最小化するフィルタ重みを求めるというものである。まず、コスト関数を次のように定義する。 ${\displaystyle {\hat {\mathbf {h} }}(n)}$

${\displaystyle C(n)=E\left\{|e(n)|^{2}\right\}}$

ここで、 は現在のサンプルnにおける誤差であり、は期待値を表します。 ${\displaystyle e(n)}$ ${\displaystyle E\{\cdot \}}$

このコスト関数（）は平均二乗誤差であり、LMSによって最小化されます。これがLMSの名前の由来です。最急降下法を適用するということは、フィルタ係数（重み）ベクトルの各要素について偏微分をとることを意味します。 ${\displaystyle C(n)}$

${\displaystyle \nabla _{{\hat {\mathbf {h} }}^{H}}C(n)=\nabla _{{\hat {\mathbf {h} }}^{H}}E\left\{e(n)\,e^{*}(n)\right\}=2E\left\{\nabla _{{\hat {\mathbf {h} }}^{H}}(e(n))\,e^{*}(n)\right\}}$

勾配演算子はどこにありますか ${\displaystyle \nabla }$

${\displaystyle \nabla _{{\hat {\mathbf {h} }}^{H}}(e(n))=\nabla _{{\hat {\mathbf {h} }}^{H}}\left(d(n)-{\hat {\mathbf {h} }}^{H}\cdot \mathbf {x} (n)\right)=-\mathbf {x} (n)}$

${\displaystyle \nabla C(n)=-2E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

さて、はコスト関数の最も急な上昇を指すベクトルです。コスト関数の最小値を見つけるには、の反対方向にステップを踏む必要があります。これを数学的に表現すると、 ${\displaystyle \nabla C(n)}$ ${\displaystyle \nabla C(n)}$

${\displaystyle {\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)-{\frac {\mu }{2}}\nabla C(n)={\hat {\mathbf {h} }}(n)+\mu \,E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

ここではステップサイズ（適応定数）です。これは、コスト関数を最小化する逐次更新アルゴリズムを発見したことを意味します。残念ながら、このアルゴリズムは を知るまでは実現できません。 ${\displaystyle {\frac {\mu }{2}}}$ ${\displaystyle E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

通常、上記の期待値は計算されません。LMSをオンライン環境（新しいサンプルを受信するたびに更新される環境）で実行するために、期待値の瞬間推定値を使用します。以下を参照してください。

簡素化

ほとんどのシステムでは、期待関数を近似する必要があります。これは、次の不偏推定値で行うことができます。 ${\displaystyle {E}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

${\displaystyle {\hat {E}}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}={\frac {1}{N}}\sum _{i=0}^{N-1}\mathbf {x} (n-i)\,e^{*}(n-i)}$

ここで、推定に用いる標本数を示す。最も単純なケースは ${\displaystyle N}$ ${\displaystyle N=1}$

${\displaystyle {\hat {E}}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}=\mathbf {x} (n)\,e^{*}(n)}$

この単純なケースでは更新アルゴリズムは次のようになる。

${\displaystyle {\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+\mu \mathbf {x} (n)\,e^{*}(n)}$

実際、これは LMS フィルターの更新アルゴリズムを構成します。

LMSアルゴリズムの概要

a次フィルタのLMSアルゴリズムは次のように要約できる。 ${\displaystyle p}$

パラメータ:	${\displaystyle p=}$フィルタ順序
	${\displaystyle \mu =}$ステップサイズ
初期化:	${\displaystyle {\hat {\mathbf {h} }}(0)=\operatorname {zeros} (p)}$
計算:	のために ${\displaystyle n=0,1,2,...}$
	${\displaystyle \mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p+1)\right]^{T}}$
	${\displaystyle e(n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\mathbf {x} (n)}$
	${\displaystyle {\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+\mu \,e^{*}(n)\mathbf {x} (n)}$

平均の収束と安定性

LMSアルゴリズムは期待値の正確な値を使用しないため、重みは絶対的な意味で最適重みに到達することはありませんが、平均収束は可能です。つまり、重みがわずかに変化したとしても、最適重み付近で変化します。しかし、重みの変化に伴う分散が大きい場合、平均収束は誤った結果をもたらす可能性があります。この問題は、ステップサイズの値を適切に選択しないと発生する可能性があります。 ${\displaystyle \mu }$

を大きく設定した場合、重みの変化量は勾配推定値に大きく依存するため、重みが大きく変化し、最初の瞬間に負であった勾配が正に変化する可能性があります。また、2番目の瞬間には、負の勾配の影響で重みが反対方向に大きく変化し、最適な重みを中心に大きな分散で振動し続ける可能性があります。一方、を小さく設定しすぎると、最適な重みへの収束に時間がかかりすぎます。 ${\displaystyle \mu }$ ${\displaystyle \mu }$

したがって、 の上限は次のように与えられる必要がある 。 ${\displaystyle \mu }$ ${\displaystyle 0<\mu <{\frac {2}{\lambda _{\mathrm {max} }}}}$

ここで、は自己相関行列の最大固有値です。この条件が満たされない場合、アルゴリズムは不安定になり、発散します。 ${\displaystyle \lambda _{\max }}$ ${\displaystyle {\mathbf {R} }=E\{{\mathbf {x} }(n){\mathbf {x} ^{H}}(n)\}}$ ${\displaystyle {\hat {h}}(n)}$

最大収束速度は、

${\displaystyle \mu ={\frac {2}{\lambda _{\mathrm {max} }+\lambda _{\mathrm {min} }}},}$

ここでは の最小の固有値です。 がこの最適値以下である場合、収束速度は によって決定され、値が大きいほど収束は速くなります。これは、が に近いほど収束が速くなることを意味します。つまり、達成可能な最大の収束速度はの固有値の広がりに依存します。 ${\displaystyle \lambda _{\min }}$ ${\displaystyle {\mathbf {R} }}$ ${\displaystyle \mu }$ ${\displaystyle \lambda _{\min }}$ ${\displaystyle \lambda _{\max }}$ ${\displaystyle \lambda _{\min }}$ ${\displaystyle {\mathbf {R} }}$

白色ノイズ信号は自己相関行列を持ち、ここで は信号の分散です。この場合、すべての固有値は等しく、固有値の広がりはすべての可能な行列の中で最小になります。したがって、この結果の一般的な解釈は、LMSは白色入力信号では急速に収束し、ローパスまたはハイパス特性を持つプロセスなどの有色入力信号ではゆっくりと収束するというものです。 ${\displaystyle {\mathbf {R} }=\sigma ^{2}{\mathbf {I} }}$ ${\displaystyle \sigma ^{2}}$

上の上限は平均の安定性を強制するだけであり、係数は依然として無限に大きくなる可能性があり、つまり係数の発散は依然として起こり得ること に注意する必要がある。より実用的な上限は ${\displaystyle \mu }$ ${\displaystyle {\hat {h}}(n)}$

${\displaystyle 0<\mu <{\frac {2}{\mathrm {tr} \left[{\mathbf {R} }\right]}},}$

ここで、は のトレースを表します。この境界は、 の係数が発散しないことを保証します（実際には、 の値は、境界の導出時に行われた近似と仮定のためにやや楽観的であるため、この上限に近い値を選択すべきではありません）。 ${\displaystyle \mathrm {tr} [{\mathbf {R} }]}$ ${\displaystyle {\mathbf {R} }}$ ${\displaystyle {\hat {h}}(n)}$ ${\displaystyle \mu }$

正規化最小二乗フィルタ（NLMS）

「純粋な」LMSアルゴリズムの主な欠点は、入力のスケーリングに敏感であることです。そのため、アルゴリズムの安定性を保証する学習率を選択することは非常に困難（不可能ではないにしても）です（Haykin 2002）。正規化最小平均二乗フィルタ（NLMS）は、LMSアルゴリズムの派生であり、入力のべき乗で正規化することでこの問題を解決します。NLMSアルゴリズムは次のように要約できます。 ${\displaystyle x(n)}$ ${\displaystyle \mu }$

パラメータ:	${\displaystyle p=}$フィルタ順序
	${\displaystyle \mu =}$ステップサイズ
初期化:	${\displaystyle {\hat {\mathbf {h} }}(0)=\operatorname {zeros} (p)}$
計算:	のために ${\displaystyle n=0,1,2,...}$
	${\displaystyle \mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p+1)\right]^{T}}$
	${\displaystyle e(n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\mathbf {x} (n)}$
	${\displaystyle {\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+{\frac {\mu \,e^{*}(n)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}}$

最適学習率

干渉がない場合（）には、NLMSアルゴリズムの最適学習率は ${\displaystyle v(n)=0}$

${\displaystyle \mu _{opt}=1}$

は入力と実数（未知）のインパルス応答に依存しない。干渉（）のある一般的なケースでは、最適な学習率は ${\displaystyle x(n)}$ ${\displaystyle \mathbf {h} (n)}$ ${\displaystyle v(n)\neq 0}$

${\displaystyle \mu _{opt}={\frac {E\left[\left|y(n)-{\hat {y}}(n)\right|^{2}\right]}{E\left[|e(n)|^{2}\right]}}}$

上記の結果は、信号とが互いに無相関であると仮定しており、これは実際には一般的なケースです。 ${\displaystyle v(n)}$ ${\displaystyle x(n)}$

証拠

フィルタのミスアライメントを と定義すると、次のサンプルの予想されるミスアライメントは次のように導出できます。 ${\displaystyle \Lambda (n)=\left|\mathbf {h} (n)-{\hat {\mathbf {h} }}(n)\right|^{2}}$

${\displaystyle E\left[\Lambda (n+1)\right]=E\left[\left|{\hat {\mathbf {h} }}(n)+{\frac {\mu \,e^{*}(n)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-\mathbf {h} (n)\right|^{2}\right]}$

${\displaystyle E\left[\Lambda (n+1)\right]=E\left[\left|{\hat {\mathbf {h} }}(n)+{\frac {\mu \,\left(v^{*}(n)+y^{*}(n)-{\hat {y}}^{*}(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-\mathbf {h} (n)\right|^{2}\right]}$

させて、 ${\displaystyle \mathbf {\delta } ={\hat {\mathbf {h} }}(n)-\mathbf {h} (n)}$ ${\displaystyle r(n)={\hat {y}}(n)-y(n)}$

${\displaystyle E\left[\Lambda (n+1)\right]=E\left[\left|\mathbf {\delta } (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right|^{2}\right]}$

${\displaystyle E\left[\Lambda (n+1)\right]=E\left[\left(\mathbf {\delta } (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)^{H}\left(\mathbf {\delta } (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)\right]}$

独立性を前提とすると、次のようになります。

${\displaystyle E\left[\Lambda (n+1)\right]=\Lambda (n)+E\left[\left({\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)^{H}\left({\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)\right]-2E\left[{\frac {\mu |r(n)|^{2}}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right]}$

${\displaystyle E\left[\Lambda (n+1)\right]=\Lambda (n)+{\frac {\mu ^{2}E\left[|e(n)|^{2}\right]}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-{\frac {2\mu E\left[|r(n)|^{2}\right]}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}}$

最適な学習率は で見つかり、次のようになります。 ${\displaystyle {\frac {dE\left[\Lambda (n+1)\right]}{d\mu }}=0}$

${\displaystyle 2\mu E\left[|e(n)|^{2}\right]-2E\left[|r(n)|^{2}\right]=0}$

${\displaystyle \mu ={\frac {E\left[|r(n)|^{2}\right]}{E\left[|e(n)|^{2}\right]}}}$

参照

• 再帰最小二乗法
• LMS フィルターに関連する統計手法については、「最小二乗法」を参照してください。
• WienerとLMSの類似点
• 多重遅延ブロック周波数領域適応フィルタ
• ゼロフォーシングイコライザー
• カーネル適応フィルタ
• マッチドフィルタ
• ウィーナーフィルタ

参考文献

• モンソン・H・ヘイズ：統計的デジタル信号処理とモデリング、 Wiley、1996年、ISBN 0-471-59431-8
• サイモン・ヘイキン著『適応フィルタ理論』、プレンティス・ホール、2002年、ISBN 0-13-048434-2
• Simon S. Haykin、Bernard Widrow（編）：Least-Mean-Square Adaptive Filters、 Wiley、2003年、ISBN 0-471-21570-8
• バーナード・ウィドロウ、サミュエル・D・スターンズ：適応信号処理、プレンティス・ホール、1985年、ISBN 0-13-004029-0
• ウェイフェン・リウ、ホセ・プリンシペ、サイモン・ヘイキン：カーネル適応フィルタリング：包括的入門、ジョン・ワイリー、2010年、ISBN 0-470-44753-2
• Paulo SR Diniz著：適応フィルタリング：アルゴリズムと実践的実装、 Kluwer Academic Publishers、1997年、ISBN 0-7923-9912-9

外部リンク

• 適応アンテナアレイにおけるLMSアルゴリズム www.antenna-theory.com
• LMS ノイズキャンセルデモ www.advsolned.com

Retrieved from "https://en.wikipedia.org/w/index.php?title=Least_mean_squares_filter&oldid=1316987607"