كيف تعمل خوارزمية Levenberg-Marquardt بالتفصيل ولكن بطريقة مفهومة؟

Question

أنا مبرمج يريد أن يتعلم كيف تعمل خوارزمية Levenberg-Marquardt Curvefitting حتى أتمكن من تنفيذها بنفسي. هل هناك برنامج تعليمي جيد في أي مكان يمكنه أن يفسر كيف يعمل بالتفصيل مع القارئ بنينغ مبرمج وليس عالم الرياضيات.

هدفي هو تنفيذ هذه الخوارزمية في OpenCL حتى أتمكن من قيامك بإجراء تشغيل الأجهزة المتسارعة.

Answer 1

• يحاول http://en.wikipedia.org/wiki/levenberg-marquardt_algorithm.
• PDF التعليمي من Ananth Ranganathan.
• Javanumerics. لديه تنفيذ مقروء جدا
• ICS لديه C / C ++ تطبيق

Answer 2

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

خوارزمية LM، والعديد من خوارزميات التقليل الأخرى، استخدم هذا المخطط.

لنفترض أن الوظيفة التي يتم تقليلها هي F ونحن في النقطة س (ن) في التكرار لدينا. نود أن نجد التكرار التالي x (n + 1) بحيث f (x (n + 1)) <f (x (n))، أي قيمة الوظيفة أصغر. من أجل اختيار x (n + 1) نحتاج إلى شيئين، وهو اتجاه من x (n) وحجم خطوة (إلى أي مدى للذهاب في هذا الاتجاه). تحدد خوارزمية LM هذه القيم على النحو التالي -

أولا، حساب تقريب خطي إلى F عند النقطة X (N). من السهل معرفة اتجاه الهبوط لوظيفة خطية، لذلك نستخدم وظيفة تقريبية خطية لتحديد الاتجاه الهبوطي. بعد ذلك، نحتاج أن نعرف إلى أي مدى يمكننا الذهاب في هذا الاتجاه المختار. إذا كانت وظيفتنا الخطية تقريبا هي تقريب جيد للحصول على مساحة كبيرة حول X (N)، فيمكننا اتخاذ خطوة كبيرة إلى حد ما. إذا كان تقريب جيد فقط قريب جدا من X (N)، فيمكننا اتخاذ خطوة صغيرة فقط.

هذا ما يفعله LM - يحسب تقريب خطي إلى F في X (N)، وبالتالي إعطاء الاتجاه الهبوطي، فهو أرقام مدى سرعة اتخاذ خطوة بناء على مدى جودة الوظيفة الخطية تقارب F في X (N). أرقام LM على مدى جودة وظيفة التقريب من خلال اتخاذ خطوة في الاتجاه أساسا وبالتالي تحديد ومقارنة مقدار التقريب الخطي إلى F انخفض إلى مقدار انخفاض الوظيفة الفعلية. إذا كانت قريبة، فإن وظيفة التقريب جيدة ويمكننا اتخاذ خطوة أكبر قليلا. إذا لم تكن قريبة، فستكون وظيفة التقريب جيدة، ويجب أن نتراجع وتأخذ خطوة أصغر.

Answer 3

يمكن شرح الأفكار الأساسية لخوارزمية LM في بعض الصفحات - ولكن بالنسبة لتنفيذ درجة الإنتاج سريعة وقوية، فإن العديد من التحسينات الدقيقة ضرورية. لا تزال دولة الفن هي تطبيق MORÉ et al.، موثقة بالتفصيل بواسطة Moré 1978 (http://link.springer.com/content/pdf/10.1007/bfb0067700.pdf.) وفي دليل المستخدم MINPACK (http://www.mcs.anl.gov/~more/anl8074b.pdf.). لدراسة التعليمات البرمجية، بلدي C الترجمة (https://jugit.fz-juelich.de/mlz/lmfit.) ربما يكون أكثر سهولة من رمز FORTRAN الأصلي.

Answer 4

يحاول الوصفات العددية (levenberg-marquardt في القسم 15.5). إنه متاح عبر الإنترنت، وأجد أنهم يفسرون الخوارزميات بطريقة مفصلة (لديهم شفرة مصدر كاملة، كم أكثر تفصيلا يمكنك الحصول عليها ...)، بعد الوصول إليها.

Answer 5

انا إستعملت هذه الملاحظات من دورة في جامعة بوردو للحصول على كود خوارزمية مناهج منحنى Levenberg-Marquardt عام في MATLAB يحسب المشتقات العددية، وبالتالي يقبل أي وظيفة من النموذج f(x;p) أين p هو متجه من المعلمات المناسب.