مرشح المربعات الصغرى

خوارزميات المربعات الصغرى ( 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}$.

تتمثل الفكرة الأساسية وراء مرشح LMS في الاقتراب من أوزان المرشح المثلى${\displaystyle (R^{-1}P)}$يتم ذلك عن طريق تحديث أوزان المرشح بطريقة تتقارب نحو الوزن الأمثل. يعتمد هذا على خوارزمية التدرج الهبوطي. تبدأ الخوارزمية بافتراض أوزان صغيرة (صفر في معظم الحالات)، وفي كل خطوة، يتم تحديث الأوزان عن طريق إيجاد تدرج متوسط ​​مربع الخطأ. أي، إذا كان تدرج متوسط ​​مربع الخطأ موجبًا، فهذا يعني أن الخطأ سيستمر في الزيادة بشكل موجب إذا تم استخدام نفس الوزن في التكرارات اللاحقة، مما يعني أننا بحاجة إلى تقليل الأوزان. وبالمثل، إذا كان التدرج سالبًا، فنحن بحاجة إلى زيادة الأوزان. معادلة تحديث الوزن هي

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

أين${\displaystyle \varepsilon }$يمثل متوسط ​​مربع الخطأ و${\displaystyle \mu }$هو معامل معدل التعلم .

تشير الإشارة السالبة إلى أننا نتجه نحو أسفل منحدر الخطأ.${\displaystyle \varepsilon }$لإيجاد أوزان المرشح،${\displaystyle W_{i}}$مما يقلل الخطأ.

يُعدّ متوسط ​​مربع الخطأ دالةً لأوزان المرشح دالة تربيعية ، ما يعني أن لها قيمة قصوى واحدة فقط، وهي القيمة التي تُقلّل متوسط ​​مربع الخطأ، والتي تُمثّل الوزن الأمثل. وبالتالي، تقترب خوارزمية LMS من هذه الأوزان المثلى بالصعود/الهبوط على منحنى متوسط ​​مربع الخطأ مقابل وزن المرشح.

تعتمد فكرة مرشحات LMS على استخدام أسلوب الانحدار الأسرع لإيجاد أوزان المرشحات${\displaystyle {\hat {\mathbf {h} }}(n)}$والتي تُقلل دالة التكلفة . نبدأ بتعريف دالة التكلفة على النحو التالي:

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

أين${\displaystyle e(n)}$يمثل الخطأ عند العينة الحالية n و${\displaystyle E\{\cdot \}}$يشير إلى القيمة المتوقعة .

دالة التكلفة هذه (${\displaystyle C(n)}$يمثل متوسط ​​مربع الخطأ، ويتم تقليله باستخدام خوارزمية LMS. ومن هنا جاء اسم خوارزمية LMS. تطبيق خوارزمية الانحدار الأسرع يعني حساب المشتقات الجزئية بالنسبة إلى كل عنصر من عناصر متجه معاملات المرشح (الأوزان).

${\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} (ن)}$

${\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} (ن)\,ه^{*}(ن)\يمين\}}$

أين${\displaystyle {\frac {\mu }{2}}}$يمثل حجم الخطوة (ثابت التكيف). هذا يعني أننا وجدنا خوارزمية تحديث تسلسلي تُقلل دالة التكلفة. لسوء الحظ، لا يمكن تطبيق هذه الخوارزمية حتى نعرف${\displaystyle E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$.

عمومًا، لا يتم حساب القيمة المتوقعة المذكورة أعلاه. بدلًا من ذلك، لتشغيل نظام إدارة التعلم في بيئة متصلة بالإنترنت (يتم تحديثها بعد استلام كل عينة جديدة)، نستخدم تقديرًا فوريًا لتلك القيمة المتوقعة. انظر أدناه.

بالنسبة لمعظم الأنظمة، دالة التوقع${\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} (ni)\,e^{*}(ni)}$

أين${\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 لـ${\displaystyle p}$يمكن تلخيص مرشح الترتيب th على النحو التالي

حدود:	${\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 }$لم يتم اختياره بشكل صحيح.

لو${\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} }}$.

إشارة الضوضاء البيضاء لها مصفوفة ارتباط ذاتي${\displaystyle {\mathbf {R} }=\sigma ^{2}{\mathbf {I} }}$أين${\displaystyle \sigma ^{2}}$يمثل تباين الإشارة. في هذه الحالة، تتساوى جميع القيم الذاتية، ويكون انتشار القيم الذاتية هو الأدنى بين جميع المصفوفات الممكنة. ولذلك، فإن التفسير الشائع لهذه النتيجة هو أن خوارزمية LMS تتقارب بسرعة مع إشارات الإدخال البيضاء، وببطء مع إشارات الإدخال الملونة، مثل العمليات ذات خصائص التمرير المنخفض أو التمرير العالي.

من المهم ملاحظة أن الحد الأعلى المذكور أعلاه على${\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 }$لا ينبغي اختيار قيمة قريبة من هذا الحد الأعلى، لأنه متفائل إلى حد ما بسبب التقريبات والافتراضات التي تم وضعها في اشتقاق الحد).

يتمثل العيب الرئيسي لخوارزمية LMS "الخالصة" في أنها حساسة لتغيير حجم مدخلاتها.${\displaystyle x(n)}$وهذا يجعل اختيار معدل التعلم أمراً بالغ الصعوبة (إن لم يكن مستحيلاً).${\displaystyle \mu }$يضمن ذلك استقرار الخوارزمية (هايكين، 2002). مرشح المربعات الصغرى المعياري (NLMS) هو أحد أنواع خوارزمية المربعات الصغرى (LMS) التي تحل هذه المشكلة عن طريق التطبيع باستخدام قوة المدخلات. يمكن تلخيص خوارزمية NLMS على النحو التالي:

حدود:	${\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)}}}$

• المربعات الصغرى المتكررة
• للاطلاع على التقنيات الإحصائية ذات الصلة بمرشح LMS، انظر المربعات الصغرى .
• أوجه التشابه بين وينر ونظام إدارة التعلم
• معادل إجباري صفري
• مرشح تكيفي للنواة
• فلتر مطابق
• فلتر وينر

• مونسون هـ. هايز: المعالجة الإحصائية للإشارات الرقمية والنمذجة، وايلي، 1996، رقم ISBN 0-471-59431-8
• سايمون هايكين: نظرية المرشحات التكيفية، برنتيس هول، 2002، رقم ISBN 0-13-048434-2
• سايمون س. هايكين، برنارد ويدرو (محرران): مرشحات تكيفية بمتوسط ​​مربعات دنيا، وايلي، 2003، رقم ISBN 0-471-21570-8
• برنارد ويدرو، صموئيل د. ستيرنز: معالجة الإشارات التكيفية، برنتيس هول، 1985، رقم ISBN 0-13-004029-0
• ويفنغ ليو، خوسيه برينسيبي، وسيمون هايكين: الترشيح التكيفي باستخدام النواة: مقدمة شاملة، جون وايلي، 2010، رقم ISBN 0-470-44753-2
• باولو إس آر دينيز: الترشيح التكيفي: الخوارزميات والتطبيق العملي، دار نشر كلوير الأكاديمية، 1997، رقم ISBN 0-7923-9912-9

• خوارزمية LMS في مصفوفات الهوائيات التكيفية www.antenna-theory.com
• عرض توضيحي لتقنية إلغاء الضوضاء LMS www.advsolned.com