Thuật toán Broyden, Fletcher, Goldfarb và Shanno, hoặc BFGS, là một thuật toán tối ưu hóa tìm kiếm cục bộ
Nó là một loại thuật toán tối ưu hóa bậc hai, nghĩa là nó sử dụng đạo hàm bậc hai của một hàm mục tiêu và thuộc về một loại thuật toán được gọi là phương pháp Quasi-Newton xấp xỉ đạo hàm bậc hai [được gọi là Hessian] cho các vấn đề tối ưu hóa trong đó không thể tính được đạo hàm thứ hai
Thuật toán BFGS có lẽ là một trong những thuật toán bậc hai được sử dụng rộng rãi nhất để tối ưu hóa số và thường được sử dụng để phù hợp với các thuật toán học máy như thuật toán hồi quy logistic
Trong hướng dẫn này, bạn sẽ khám phá thuật toán tối ưu hóa bậc hai BFGS
Sau khi hoàn thành hướng dẫn này, bạn sẽ biết
- Các thuật toán tối ưu hóa bậc hai là các thuật toán sử dụng đạo hàm bậc hai, được gọi là ma trận Hessian cho các hàm mục tiêu đa biến
- Thuật toán BFGS có lẽ là thuật toán bậc hai phổ biến nhất để tối ưu hóa số và thuộc nhóm gọi là phương pháp Quasi-Newton
- Cách giảm thiểu các hàm mục tiêu bằng thuật toán BFGS và L-BFGS-B trong Python
Bắt đầu dự án của bạn với cuốn sách mới của tôi Tối ưu hóa cho Máy học, bao gồm các hướng dẫn từng bước và các tệp mã nguồn Python cho tất cả các ví dụ
Bắt đầu nàoGiới thiệu nhẹ nhàng về thuật toán tối ưu hóa BFGS
Ảnh của Timo Newton-Syms, bảo lưu một số quyền
Hướng dẫn tổng quan
Hướng dẫn này được chia thành ba phần;
- Thuật toán tối ưu hóa bậc hai
- Thuật toán tối ưu hóa BFGS
- Ví dụ hoạt động của BFGS
Thuật toán tối ưu hóa bậc hai
Tối ưu hóa liên quan đến việc tìm giá trị cho các tham số đầu vào giúp tối đa hóa hoặc giảm thiểu hàm mục tiêu
Các thuật toán tối ưu hóa theo phương pháp Newton là những thuật toán sử dụng đạo hàm cấp hai của hàm mục tiêu
Bạn có thể nhớ lại từ giải tích rằng đạo hàm bậc nhất của hàm là tốc độ thay đổi hoặc độ cong của hàm tại một điểm cụ thể. Đạo hàm có thể được theo dõi xuống dốc [hoặc lên dốc] bằng một thuật toán tối ưu hóa theo hướng cực tiểu của hàm [các giá trị đầu vào dẫn đến đầu ra nhỏ nhất của hàm mục tiêu]
Các thuật toán sử dụng đạo hàm cấp một được gọi là thuật toán tối ưu hóa cấp một. Một ví dụ về thuật toán bậc nhất là thuật toán tối ưu hóa giảm dần độ dốc
- Phương pháp đặt hàng đầu tiên. Các thuật toán tối ưu sử dụng đạo hàm cấp một để tìm giá trị tối ưu của hàm mục tiêu
Đạo hàm cấp hai là đạo hàm của đạo hàm, hay tốc độ thay đổi của tốc độ thay đổi
Có thể theo đạo hàm cấp hai để xác định vị trí tối ưu của hàm mục tiêu một cách hiệu quả hơn. Điều này có ý nghĩa tổng quát hơn, vì chúng ta càng có nhiều thông tin về hàm mục tiêu thì càng dễ dàng tối ưu hóa nó.
Đạo hàm bậc hai cho phép chúng ta biết cả hướng di chuyển [như bậc nhất] nhưng cũng ước tính khoảng cách di chuyển theo hướng đó, được gọi là kích thước bước
Mặt khác, thông tin bậc hai cho phép chúng ta thực hiện phép tính gần đúng bậc hai của hàm mục tiêu và ước tính kích thước bước phù hợp để đạt được giá trị cực tiểu cục bộ...
— Trang 87, Thuật toán tối ưu hóa, 2019
Các thuật toán sử dụng đạo hàm cấp hai được gọi là thuật toán tối ưu hóa cấp hai
- Phương pháp bậc hai. Các thuật toán tối ưu sử dụng đạo hàm cấp hai để tìm giá trị tối ưu của hàm mục tiêu
Một ví dụ về thuật toán tối ưu hóa bậc hai là phương pháp của Newton
Khi một hàm mục tiêu có nhiều hơn một biến đầu vào, các biến đầu vào cùng nhau có thể được coi là một vectơ, điều này có thể quen thuộc với đại số tuyến tính
Độ dốc là sự tổng quát hóa của đạo hàm đối với các hàm nhiều biến. Nó ghi lại độ dốc cục bộ của hàm, cho phép chúng tôi dự đoán tác động của việc thực hiện một bước nhỏ từ một điểm theo bất kỳ hướng nào
— Trang 21, Thuật toán tối ưu hóa, 2019
Tương tự, đạo hàm bậc nhất của nhiều biến đầu vào cũng có thể là một vectơ, trong đó mỗi phần tử được gọi là đạo hàm riêng. Vectơ đạo hàm riêng này được gọi là gradient
- Dốc. Vectơ của các đạo hàm riêng đầu tiên cho nhiều biến đầu vào của một hàm mục tiêu
Ý tưởng này khái quát hóa thành các đạo hàm bậc hai của các đầu vào đa biến, là một ma trận chứa các đạo hàm bậc hai được gọi là ma trận Hessian
- Hessian. Ma trận đạo hàm riêng cấp hai cho nhiều biến đầu vào của hàm mục tiêu
Ma trận Hessian là hình vuông và đối xứng nếu các đạo hàm cấp hai đều liên tục tại điểm mà chúng ta đang tính các đạo hàm. Trường hợp này thường xảy ra khi giải các bài toán tối ưu giá trị thực và một kỳ vọng khi sử dụng nhiều phương pháp bậc hai
Hessian của hàm nhiều biến là một ma trận chứa tất cả các đạo hàm cấp hai đối với đầu vào. Các dẫn xuất thứ hai nắm bắt thông tin về độ cong cục bộ của hàm
— Trang 21, Thuật toán tối ưu hóa, 2019
Do đó, người ta thường mô tả các thuật toán tối ưu hóa bậc hai bằng cách sử dụng hoặc tuân theo Hessian để tối ưu hóa hàm mục tiêu
Bây giờ chúng ta đã hiểu ở mức độ cao về các thuật toán tối ưu hóa bậc hai, chúng ta hãy xem xét kỹ hơn về thuật toán BFGS
Bạn muốn bắt đầu với các thuật toán tối ưu hóa?
Tham gia khóa học xử lý sự cố email miễn phí trong 7 ngày của tôi ngay bây giờ [có mã mẫu]
Nhấp để đăng ký và cũng nhận được phiên bản PDF Ebook miễn phí của khóa học
Bắt đầu Khóa học nhỏ MIỄN PHÍ của bạn ngay bây giờ
Thuật toán tối ưu hóa BFGS
BFGS là thuật toán tối ưu hóa bậc hai
Nó là từ viết tắt, được đặt tên cho bốn người đồng khám phá ra thuật toán. Broyden, Fletcher, Goldfarb và Shanno
Nó là một thuật toán tìm kiếm cục bộ, dành cho các bài toán tối ưu lồi với một phương án tối ưu duy nhất.
Thuật toán BFGS có lẽ được hiểu đúng nhất là thuộc về một nhóm thuật toán mở rộng cho thuật toán tối ưu hóa Phương pháp của Newton, được gọi là Phương pháp Quasi-Newton
Phương pháp của Newton là một thuật toán tối ưu hóa bậc hai sử dụng ma trận Hessian
Một hạn chế của phương pháp Newton là nó yêu cầu tính nghịch đảo của ma trận Hessian. Đây là một hoạt động tính toán tốn kém và có thể không ổn định tùy thuộc vào các thuộc tính của hàm mục tiêu
Các phương pháp Quasi-Newton là các thuật toán tối ưu hóa bậc hai xấp xỉ nghịch đảo của ma trận Hessian bằng cách sử dụng gradient, nghĩa là Hessian và nghịch đảo của nó không cần phải có sẵn hoặc tính toán chính xác cho từng bước của thuật toán
Các phương pháp Quasi-Newton là một trong những phương pháp được sử dụng rộng rãi nhất để tối ưu hóa phi tuyến. Chúng được kết hợp trong nhiều thư viện phần mềm và chúng có hiệu quả trong việc giải quyết nhiều vấn đề nhỏ đến trung bình, đặc biệt khi Hessian khó tính toán
— Trang 411, Tối ưu hóa tuyến tính và phi tuyến, 2009
Sự khác biệt chính giữa các thuật toán tối ưu hóa Quasi-Newton khác nhau là cách cụ thể theo đó phép tính gần đúng của Hessian nghịch đảo
Thuật toán BFGS là một cách cụ thể để cập nhật phép tính của Hessian nghịch đảo, thay vì tính toán lại nó sau mỗi lần lặp. Nó, hoặc các phần mở rộng của nó, có thể là một trong những thuật toán tối ưu hóa bậc hai hoặc Quasi-Newton phổ biến nhất được sử dụng để tối ưu hóa số
Thuật toán gần như Newton phổ biến nhất là phương pháp BFGS, được đặt tên theo những người khám phá ra nó là Broyden, Fletcher, Goldfarb và Shanno
- Trang 136, Numerical Optimization, 2006
Một lợi ích của việc sử dụng Hessian, khi có sẵn, là nó có thể được sử dụng để xác định cả hướng và kích thước bước di chuyển để thay đổi các tham số đầu vào nhằm giảm thiểu [hoặc tối đa hóa] hàm mục tiêu
Các phương pháp Quasi-Newton như BFGS xấp xỉ Hessian nghịch đảo, sau đó có thể được sử dụng để xác định hướng di chuyển, nhưng chúng ta không còn kích thước bước
Thuật toán BFGS giải quyết vấn đề này bằng cách sử dụng tìm kiếm đường theo hướng đã chọn để xác định khoảng cách di chuyển theo hướng đó
Đối với việc tính toán và tính toán được sử dụng bởi thuật toán BFGS, tôi khuyên bạn nên sử dụng các tài nguyên trong phần đọc thêm ở cuối hướng dẫn này
Kích thước của Hessian và nghịch đảo của nó tỷ lệ thuận với số lượng tham số đầu vào cho hàm mục tiêu. Như vậy, kích thước của ma trận có thể trở nên rất lớn đối với hàng trăm, hàng nghìn hoặc hàng triệu tham số.
… thuật toán BFGS phải lưu trữ ma trận Hessian nghịch đảo, M, yêu cầu bộ nhớ O[n2], khiến BFGS không thực tế đối với hầu hết các mô hình học sâu hiện đại thường có hàng triệu tham số
— Trang 317, Học sâu, 2016
Bộ nhớ hạn chế BFGS [hoặc L-BFGS] là phần mở rộng của thuật toán BFGS giải quyết chi phí có một số lượng lớn tham số. Nó thực hiện điều này bằng cách không yêu cầu lưu trữ toàn bộ giá trị gần đúng của ma trận nghịch đảo, bằng cách giả sử đơn giản hóa ma trận nghịch đảo Hessian trong lần lặp trước của thuật toán [được sử dụng trong phép tính gần đúng]
Bây giờ chúng ta đã quen thuộc với thuật toán BFGS ở cấp độ cao, hãy xem cách chúng ta có thể sử dụng nó
Ví dụ hoạt động của BFGS
Trong phần này, chúng ta sẽ xem xét một số ví dụ về việc sử dụng thuật toán tối ưu hóa BFGS
Chúng ta có thể triển khai thuật toán BFGS để tối ưu hóa các hàm tùy ý trong Python bằng cách sử dụng hàm SciPy minimal[]
Hàm nhận một số đối số, nhưng quan trọng nhất, chúng ta có thể chỉ định tên của hàm mục tiêu làm đối số đầu tiên, điểm bắt đầu tìm kiếm làm đối số thứ hai và chỉ định đối số "phương thức" là 'BFGS'. Tên của hàm được sử dụng để tính đạo hàm của hàm mục tiêu có thể được chỉ định thông qua đối số "jac"
1
2
3
.. .
# thực hiện tìm kiếm thuật toán bfss
kết quả = giảm thiểu[mục tiêu, p, phương pháp='BFGS', jac=đạo hàm]
Hãy xem một ví dụ
Đầu tiên, chúng ta có thể định nghĩa hàm mục tiêu hai chiều đơn giản, hàm tô, e. g. x^2. Nó chỉ đơn giản là tổng của các biến đầu vào bình phương với giá trị tối ưu tại f[0, 0] = 0. 0
1
2
3
# hàm mục tiêu
def mục tiêu[x]:
return x[0]**2. 0 + x[1 ]**2. 0
Tiếp theo, hãy định nghĩa một hàm cho đạo hàm của hàm, đó là [x*2, y*2]
1
2
3
# đạo hàm của hàm mục tiêu
def đạo hàm[x]:
return [x[0] * 2, x[1] * 2]
Chúng ta sẽ xác định các giới hạn của hàm dưới dạng một hộp có phạm vi -5 và 5 trong mỗi chiều
1
2
3
.. .
# xác định phạm vi cho đầu vào
r_min, r_max = -5. 0, 5. 0
Điểm bắt đầu của tìm kiếm sẽ là một vị trí được tạo ngẫu nhiên trong miền tìm kiếm
1
2
3
.. .
# xác định điểm bắt đầu là một mẫu ngẫu nhiên từ miền
pt = r_min + rand[2] * [r_max - r_min]
Sau đó, chúng ta có thể áp dụng thuật toán BFGS để tìm giá trị cực tiểu của hàm mục tiêu bằng cách chỉ định tên của hàm mục tiêu, điểm ban đầu, phương pháp chúng ta muốn sử dụng [BFGS] và tên của hàm đạo hàm.
1
2
3
.. .
# thực hiện tìm kiếm thuật toán bfss
kết quả = giảm thiểu[mục tiêu, p, phương pháp='BFGS', jac=đạo hàm]
Sau đó, chúng tôi có thể xem lại kết quả báo cáo một thông báo về việc liệu thuật toán có hoàn thành thành công hay không và tổng số đánh giá của hàm mục tiêu đã được thực hiện
1
2
3
4
.. .
# tóm tắt kết quả
in['Trạng thái. %s' % kết quả['tin nhắn']]
in['Tổng số đánh giá. %d' % kết quả['nfev']]
Cuối cùng, chúng ta có thể báo cáo các biến đầu vào được tìm thấy và đánh giá của chúng đối với hàm mục tiêu
1
2
3
4
5
.. .
# đánh giá giải pháp
giải pháp = kết quả['x']
đánh giá = mục tiêu[giải pháp]
in['Giải pháp. f[%s] = %. 5f' % [giải pháp, đánh giá]]
Liên kết điều này lại với nhau, ví dụ hoàn chỉnh được liệt kê bên dưới
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# thuật toán bfgs tối ưu hóa cục bộ của hàm lồi
từ scipy. tối ưu hóa nhập giảm thiểu
từ numpy. ngẫu nhiên nhập ranh giới
# hàm mục tiêu
def mục tiêu[x]:
return x[0]**2. 0 + x[1 ]**2. 0
# đạo hàm của hàm mục tiêu
def đạo hàm[x]:
return [x[0] * 2, x[1] * 2]
# xác định phạm vi cho đầu vào
r_min, r_max = -5. 0, 5. 0
# xác định điểm bắt đầu là một mẫu ngẫu nhiên từ miền
pt = r_min + rand[2] * [r_max - r_min]
# thực hiện tìm kiếm thuật toán bfss
kết quả = giảm thiểu[mục tiêu, p, phương pháp='BFGS', jac=đạo hàm]
# tóm tắt kết quả
in['Trạng thái. %s' % kết quả['tin nhắn']]
in['Tổng số đánh giá. %d' % kết quả['nfev']]
# đánh giá giải pháp
giải pháp = kết quả['x']
đánh giá = mục tiêu[giải pháp]
in['Giải pháp. f[%s] = %. 5f' % [giải pháp, đánh giá]]
Chạy ví dụ áp dụng thuật toán BFGS cho hàm mục tiêu của chúng tôi và báo cáo kết quả
Ghi chú. Kết quả của bạn có thể thay đổi do tính chất ngẫu nhiên của thuật toán hoặc quy trình đánh giá hoặc sự khác biệt về độ chính xác của các con số. Cân nhắc chạy ví dụ một vài lần và so sánh kết quả trung bình
Trong trường hợp này, chúng ta có thể thấy rằng bốn lần lặp lại của thuật toán đã được thực hiện và một giải pháp rất gần với f[0] tốt nhất. 0, 0. 0] = 0. 0 đã được phát hiện, ít nhất là ở mức độ chính xác hữu ích
1
2
3
Tình trạng. Đã kết thúc tối ưu hóa thành công
Tổng số đánh giá. 4
Giải pháp. f[[0. 00000000e+00 1. 11022302e-16]] = 0. 00000
Hàm thu nhỏ [] cũng hỗ trợ thuật toán L-BFGS có yêu cầu bộ nhớ thấp hơn BFGS
Cụ thể, phiên bản L-BFGS-B của thuật toán trong đó hậu tố -B biểu thị phiên bản "được đóng hộp" của thuật toán, trong đó giới hạn của miền có thể được chỉ định
Điều này có thể đạt được bằng cách chỉ định đối số "phương thức" là "L-BFGS-B"
1
2
3
.. .
# thực hiện thuật toán tìm kiếm l-bfgs-b
kết quả = giảm thiểu[mục tiêu, p, phương pháp='L-BFGS-B', jac=đạo hàm]
Ví dụ hoàn chỉnh với bản cập nhật này được liệt kê bên dưới
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# l-bfgs-b thuật toán tối ưu cục bộ của hàm lồi
từ scipy. tối ưu hóa nhập giảm thiểu
từ numpy. ngẫu nhiên nhập ranh giới
# hàm mục tiêu
def mục tiêu[x]:
return x[0]**2. 0 + x[1 ]**2. 0
# đạo hàm của hàm mục tiêu
def đạo hàm[x]:
return [x[0] * 2, x[1] * 2]
# xác định phạm vi cho đầu vào
r_min, r_max = -5. 0, 5. 0
# xác định điểm bắt đầu là một mẫu ngẫu nhiên từ miền
pt = r_min + rand[2] * [r_max - r_min]
# thực hiện thuật toán tìm kiếm l-bfgs-b
kết quả = giảm thiểu[mục tiêu, p, phương pháp='L-BFGS-B', jac=đạo hàm]
# tóm tắt kết quả
in['Trạng thái. %s' % kết quả['tin nhắn']]
in['Tổng số đánh giá. %d' % kết quả['nfev']]
# đánh giá giải pháp
giải pháp = kết quả['x']
đánh giá = mục tiêu[giải pháp]
in['Giải pháp. f[%s] = %. 5f' % [giải pháp, đánh giá]]
Chạy ứng dụng ví dụ áp dụng thuật toán L-BFGS-B cho hàm mục tiêu của chúng tôi và báo cáo kết quả
Ghi chú. Kết quả của bạn có thể thay đổi do tính chất ngẫu nhiên của thuật toán hoặc quy trình đánh giá hoặc sự khác biệt về độ chính xác của các con số. Cân nhắc chạy ví dụ một vài lần và so sánh kết quả trung bình
Một lần nữa, chúng ta có thể thấy rằng giá trị cực tiểu của hàm được tìm thấy trong rất ít phép đánh giá
1
2
3
Tình trạng. b' HỘI TỤ. NORM_OF_PROJECTED_GRADIENT_