Thuật toán Levenberg – Marquardt hoạt động chi tiết như thế nào nhưng theo một cách dễ hiểu?

Question

Im lập trình viên muốn tìm hiểu cách thuật toán đường cong Levenberg – Marquardt hoạt động để tôi có thể tự thực hiện nó. Có một hướng dẫn tốt bất cứ nơi nào có thể giải thích cách nó hoạt động chi tiết với người đọc beeing một lập trình viên và không phải là một mathemagician.

Mục tiêu của tôi là triển khai thuật toán này trong opencl để tôi có thể chạy phần cứng tăng tốc.

Answer 1

• Hãy thử http://en.wikipedia.org/wiki/Levenberg–Marquardt_algorithm
• PDF Tutorial từ Ananth Ranganathan
• JavaNumerics có một thực hiện khá dễ đọc
• Các ICS có thực hiện C/C++

Answer 2

Hãy thử Numerical Recipes (Levenberg-Marquardt nằm trong Phần 15.5). Nó có sẵn trực tuyến và tôi thấy rằng chúng giải thích các thuật toán theo cách chi tiết (chúng có mã nguồn hoàn chỉnh, bạn có thể nhận được chi tiết hơn bao nhiêu ...), nhưng vẫn có thể truy cập được.

Answer 3

Giảm thiểu một chức năng giống như cố gắng tìm điểm thấp nhất trên bề mặt. Hãy suy nghĩ về bản thân bạn đi trên một bề mặt đồi núi và bạn đang cố gắng để đạt đến điểm thấp nhất. Bạn sẽ tìm thấy hướng đi xuống dốc và đi bộ cho đến khi nó không đi xuống dốc nữa. Sau đó, bạn sẽ chọn một hướng mới mà đi xuống dốc và đi theo hướng đó cho đến khi nó không đi xuống dốc nữa, và như vậy. Cuối cùng (hy vọng) bạn sẽ đạt đến một điểm mà không có hướng đi xuống dốc nữa. Sau đó, bạn sẽ ở mức tối thiểu (địa phương).

Thuật toán LM và nhiều thuật toán giảm thiểu khác, sử dụng lược đồ này.

Giả sử rằng hàm được giảm thiểu là F và chúng ta đang ở điểm x (n) trong lần lặp của chúng ta. Chúng tôi muốn tìm lần lặp tiếp theo x (n + 1) sao cho F (x (n + 1)) < F (x (n)), tức là giá trị hàm nhỏ hơn. Để chọn x (n + 1), chúng ta cần hai thứ, một hướng từ x (n) và kích thước bước (khoảng cách đi theo hướng đó). Thuật toán LM xác định các giá trị này như sau:

Đầu tiên, tính toán xấp xỉ tuyến tính với F tại điểm x (n). Thật dễ dàng để tìm ra hướng xuống dốc của một hàm tuyến tính, vì vậy chúng tôi sử dụng hàm xấp xỉ tuyến tính để xác định hướng xuống dốc. Tiếp theo, chúng ta cần biết chúng ta có thể đi được bao xa theo hướng được chọn này. Nếu hàm tuyến tính xấp xỉ của chúng ta là một xấp xỉ tốt cho F cho một vùng rộng xung quanh x (n), thì chúng ta có thể thực hiện một bước khá lớn. Nếu đó là một xấp xỉ tốt chỉ rất gần với x (n), sau đó chúng tôi có thể chỉ mất một bước rất nhỏ. Đây là những gì LM làm - tính toán một xấp xỉ tuyến tính với F tại x (n), do đó đưa ra hướng xuống dốc, sau đó nó tìm ra cách lớn một bước để thực hiện dựa trên chức năng tuyến tính xấp xỉ F tại x (như thế nào) n). LM tìm ra cách hàm xấp xỉ tốt như thế nào về cơ bản là thực hiện một bước theo hướng do đó xác định và so sánh mức xấp xỉ tuyến tính với F giảm xuống bao nhiêu mà hàm F thực tế giảm. Nếu chúng ở gần, hàm gần đúng là tốt và chúng ta có thể thực hiện một bước lớn hơn một chút. Nếu chúng không đóng thì hàm gần đúng là không tốt và chúng ta nên lùi lại và thực hiện một bước nhỏ hơn.

Answer 4

tôi đã sử dụng these notes from a course at Purdue University mã lên một Levenberg-Marquardt thuật toán đường cong vừa vặn chung trong MATLAB mà tính dẫn xuất số và do đó chấp nhận bất kỳ chức năng của mẫu f(x;p) nơi p là một vector của các thông số phù hợp.

Answer 5

Các ý tưởng cơ bản của thuật toán LM có thể được giải thích trong một vài trang - nhưng đối với một triển khai cấp sản xuất nhanh và mạnh mẽ, cần tối ưu hóa rất nhiều. Nhà nước của nghệ thuật vẫn là triển khai Minpack của Moré và cộng sự, được ghi chép chi tiết bởi Moré 1978 (http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf) và trong hướng dẫn sử dụng Minpack (http://www.mcs.anl.gov/~more/ANL8074b.pdf). Để nghiên cứu mã, bản dịch C của tôi (http: apps.jcns.fz-juelich.de/lmfit) có thể dễ truy cập hơn mã Fortran gốc.