Trang website này tập trung các slide bài xích giảng và bài xích tập của môn về tối ưu hóa đào tạo tại trường Đại học khoa học Tự nhiên, Đại học đất nước Hà Nội.

Bạn đang xem: Sử dụng thuật toán tối ưu hoá ngẫu nhiên để tìm kiếm các giải pháp tối ưu cho các vấn đề tối ưu hóa

Link đăng kí nhóm bài tập: xem bên trên classroom của từng lớp.

Mã google classroom jajnpyg (cần sử dụng gmail để đăng ký, không dùng được email hus)

Nội dung bài giảng

Bài giảng được chia thành hai phần đó là quy hoạch đường tính và quy hoạch phi tuyến. Tuy vậy hành với bài giảng là các bài tập lập trình sử dụng ngữ điệu Python.

A. Quy hoạch tuyến tính:

Nội dung chủ yếu của phần này là định lý đối ngẫu, thuật toán đối chọi hình, thuật toán đơn hình hai pha với thuật toán đối kháng hình đối ngẫu.

Tài liệu tìm hiểu thêm bắt buộc:

D. Bertsimas và J. N. Tsitsiklis, Introduction to Linear Optimization (Athena Scientific).

Tài liệu tham khảo thêm (thuật toán điểm trong không được dạy dỗ trên lớp, có thể tham khảo qua tài liệu 4 và 5):

D. Luenberger và Y. Ye, Linear and Nonlinear Programming (Springer)C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization. Algorithms and Complexity (Dover).R. J. Vanderbei, Linear Programming: Foundations and Extensions (Springer).C. Roos, T. Terlaky, J.-Ph. Vial, Interior Point Methods for Linear Optimization (Springer).S. J. Wright, Primal-dual Interior-Point Methods (SIAM).

Một số bài xích giảng online:

B. Quy hướng phi tuyến

Trong phần quy hoạch phi tuyến họ sẽ theo thứ tự xét bài toán tối ưu hóa không điều kiện và câu hỏi tối ưu hóa có đk (đẳng thức). Bọn họ sẽ phân tích khái niệm đối ngẫu, đk tối ưu, đk Karush-Kuhn-Tucker, các thuật toán buổi tối ưu hàng đầu và bậc hai.

Tài liệu tham khảo bắt buộc:

J. Nocedal and S. Wright, Numerical Optimization (Springer).S. Boyd & L. Vandenberghe, Convex Optimization (Cambridge University Press)

Tài liệu tham khảo thêm

D. Luenberger và Y. Ye, Linear và Nonlinear Programming (Springer)

Một số bài giảng online:

C. Lập trình

Song hành với môn học tập là các bài tập lập trình trên ngôn ngữ Python 3.

Hướng dẫn cài đặt phần mềm và các gói bên trên Python: link.

Slide bài giảng và bài tập

Phần 1: ra mắt chung

Tuần 1 

Phần 2: Quy hoạch tuyến tính

Tuần 2

Bài tập về nhà: bài 1

Tuần 3

Chữa BT 1 (1 tiết)

Bài tập về nhà: bài xích 2

Tuần 4

Bàu tập về nhà: bài 3

Tuần 5

Chữa BT 2 và BT 3 (2 tiết)

Bài tập về nhà: bài xích 4

Tuần 6 

Tuần 7

Chữa BT 4

Bài tập về nhà: bài xích 5

Phần mềm lindo:

Tuần 8

Ôn tập thi thân kì (1 tiết)

Đăng ký đề tài thuyết trình

Bước 1: coi danh sách các đề tài đang đăng ký. Các nhóm không được lựa chọn trùng với các đề tài đang đăng ký.Bước 2: Điền nội tin tức đề tài nhóm muốn đăng ký.

Các liên kết tương ứng được post trong classroom của mỗi lớp.

Nội dung thuyết trình là 1 ứng dụng thực tiễn bất kì của về tối ưu hóa. Giả dụ là các ứng dụng của quy mô quy hoạch tuyến tính thì đề nghị được đo lường và tính toán sử dụng ứng dụng trên tài liệu thực. Các mô hình LP rất có thể giải sử dụng những gói trên python, excel, hay lindo. Chú ý rằng lập trình trên python sẽ được review cao hơn chỉ sử dụng excel tuyệt lindo.

Bài biểu diễn được chấm điểm dựa trên độ nặng nề của nội dung, quality thuyết trình, trả lời câu hỏi và sự chuẩn bị.

Tuần 9 (buổi 1)

Chữa BT5 (2 tiết)

Bài tập về nhà: bài 6

Phần 3: quy hoạch phi tuyến

Tuần 9 (buổi 2)

Tự hiểu lại một vài kiến thức đại lý về đạo hàm

Slide bài xích giảng

Tuần 10

Thi thân kì
Chữa bài xích thi thân kì với BT6

Tuần 11

Bài tập về nhà: bài xích 7

Tuần 12 

Chữa BT 7 (2 tiết)

Tuần 13 

Lập trình và sử dụng ứng dụng cho buổi tối ưu phi tuyến

Bài tập về nhà: bài xích 8

Tuần 14 (buổi 1)

Chữa BT 8 với hỏi đáp ôn tập cuối kì

Tuần 14 (buổi 2) và tuần 15

Thuyết trình về dự án công trình (ứng dụng thực tế, quy mô hóa dưới dạng LP/IP với giải kiếm tìm nghiệm sử dụng code hoặc phần mềm)

Lưu ý: phần đa thành viên của group đều phải tham gia diễn đạt và vấn đáp câu hỏi, giảng viên hoàn toàn có thể tùy ý hòn đảo lại trang bị tự thuyết trình của các thành viên trong nhóm (mỗi thành viên phần đông phải nắm vững nội dung toàn bộ bài thuyết trình).

Tiêu chí chấm điểm:

Nội dung: Độ khó của vấn đề, sự trí tuệ sáng tạo và triển khai xong của phương án (giải thuật cùng code)Thuyết trình: Slide và trình bày
Trả lời câu hỏi. Mỗi nhóm gồm 12 phút trình bày, 8 phút vấn đáp câu hỏi
Buổi 1 (7.12): những nhóm từ là một đến 6Buổi 2 (9.12): các nhóm trường đoản cú 7 mang lại 12Buổi 3 (14.12): các nhóm từ bỏ 13 cho 19.

Lưu ý: Để máu kiệm thời gian trong mỗi buổi thuyết trình những nhóm nên copy nội dung thể hiện (slide và code) lên cùng 1 máy tính có liên kết HDMI.

Vài lời bộc bạch

Đây là lần trước tiên mình viết những bài viết mở với public như vậy, giả dụ như nội dung bài viết có bất cứ sai sót, giỏi góp ý gì cứ thì chớ ngại nói cho doanh nghiệp biết vào phần phản hồi để mình sửa nhé. Chúc mọi người đọc vui vẻ

Gradient decent (GD)

Gradient decent là một trong thuật toán cơ bạn dạng trong machine learning nói phổ biến và deep learning dành riêng để buổi tối ưu các tham số cho mô hình học máy. Ý tưởng cơ bản nhất của gradient decent là dựa vào tính chất −∇f(x)- abla f(x)−∇f(x) luôn luôn hướng về phía rất trị của hàm số f(x)f(x)f(x), và càng ngay sát với rất trị thì quý giá của −∇f(x)- abla f(x)−∇f(x) càng tiến về không. Vì vậy để search kiếm cực trị kề bên của một hàm số f(x)f(x)f(x) bất kì, ta chọn 1 điểm x0x_0x0​ để bắt đầu thuật toán GD và cập nhật giá trị của x0x_0x0​ theo bí quyết truy hồi sau:

xn+1=xn−η⋅∇f(xn)x_n+1=x_n-etacdot abla f(x_n)xn+1​=xn​−η⋅∇f(xn​)

Trong đó, ηetaη được điện thoại tư vấn là vận tốc học của thuật toán.

Đối cùng với gradient decent, bạn ta thường chọn ηetaη bao gồm độ lớn khoảng chừng 0.010.010.01 cho 0.0010.0010.001, 0.00010.00010.0001 tùy vào loại dữ liệu.

*

Gradient trong GD thường được xem bằng hai cách, cách trước tiên là cần sử dụng analytical gradient, gồm được bằng phương pháp áp dụng phương pháp đạo hàm vào hàm mất mát nhằm tính Gradient, điểm mạnh của phương pháp này là cân nặng tính toán nhẹ với độ chính xác cao, cơ mà nhược điểm là thỉnh thoảng ta sẽ chạm mặt những việc mà hàm mất mát phức hợp đến nỗi bắt buộc tính được phương pháp đạo hàm. Điều đó dẫn đến phương pháp tính thứ hai đó là numerical Gradient, bí quyết làm này mặc dù độ đúng đắn không cao và khối lượng tính toán lớn nhưng bù lại thì nó hoàn toàn có thể dùng cho hồ hết trường hòa hợp hàm mất mát. Numerical gradient thường được dùng để làm kiểm tra analytical gradient để bào đảm ta tính đúng Gradient. Numerical gradient được tính bằng phương pháp sử dụng phương pháp sai phân phía tâm:

f′(x)=f(x+ϵ)−f(x−ϵ)2ϵf"(x)=fracf(x+epsilon)-f(x-epsilon)2epsilonf′(x)=2ϵf(x+ϵ)−f(x−ϵ)​

Gradient decent cùng với momentum

Trong một vài trường hợp, thuật toán GD của họ không kiếm được một global minimum để thuật toán nhận được một kết quả tốt mà lại bị kẹt tại một local minimum, không mong muốn muốn.

*

Để tương khắc phục điểm trừ này, ta tiếp tế công thức update gradient nhân tố vnv_nvn​ gồm công thức như sau:

vn=γvn−1+∇f(xn)v_n=gamma v_n-1+ abla f(x_n)vn​=γvn−1​+∇f(xn​)

Hệ số γgammaγ trong bí quyết trên hay được đặt là 0.90.90.9 và từ đó công thức GD cùng với momentum bao gồm công thức như sau

xn+1=xn−vnx_n+1=x_n-v_nxn+1​=xn​−vn​

⇔xn+1=xn−γvn−1−∇f(xn)Leftrightarrow x_n+1=x_n-gamma v_n-1- abla f(x_n)⇔xn+1​=xn​−γvn−1​−∇f(xn​)

Trong đó, nhìn theo mắt nhìn vật lí thì vnv_nvn​ bao hàm γvn−1gamma v_n-1γvn−1​ biểu thì mang đến “đà” của quả banh màu tiến thưởng giúp quả banh vàng vượt qua local minimum không mong muốn và yếu tắc gradient cơ bản ∇f(xn) abla f(x_n)∇f(xn​), chính vì như thế mà việc thêm “đà” này còn gọi là rò rỉ rượu cồn lượng, tức tích điện ở lần update trước bị nhỉ qua lần update sau với thông số γgammaγ.

Nesterov accelerated gradient decent (NAG)

Tuy momentum giúp viên bi quà vượt được dốc nhằm tiến cho cực trị mong muốn nhưng vấn đề đó đồng thời cũng khiến nó dao động rất lâu xung xung quanh điểm cực tiểu trước lúc dừng lại. Mặc dù nhiên, với Nesterov GD thì vấn đề này sẽ được xung khắc phục. Với nhì thuật toán trước, ta chỉ tính Gradient trên điểm đang xét, tuy nhiên với NAG, gradient được tính tại điểm ngơi nghỉ “tương lai”:

Thay vì update với:

vn=γvn−1+∇f(xn)v_n=gamma v_n-1+ abla f(x_n)vn​=γvn−1​+∇f(xn​)

NAG cập nhật với:

vn=γvn−1+∇f(xn−γvn−1)v_n=gamma v_n-1+ abla f(x_n-gamma v_n-1)vn​=γvn−1​+∇f(xn​−γvn−1​)

⇔xn+1=xn−vn=xn−γvn−1−∇f(xn−γvn−1)Leftrightarrow x_n+1=x_n-v_n=x_n-gamma v_n-1- abla f(x_n-gamma v_n-1)⇔xn+1​=xn​−vn​=xn​−γvn−1​−∇f(xn​−γvn−1​)

*


*


Stochastic gradient decent (SGD)

Cập nhật Gradient chưa đến một điểm dữ liệu ngẫu nhiên và làm vấn đề này trên cục bộ dữ liệu. Mỗi lần thuật toán trải qua hết toàn bộ các điểm dữ liệu gọi là 1 trong những epoch. Để đào tạo và huấn luyện với SGD, ta có thể sẽ đề nghị chạy những epoch.

Ưu điểm của SGD là tốc độ đo lường và thống kê rất nhanh và không đề nghị nhiều bộ nhớ. Bởi vì thế cách thức này được ứng dụng không ít trong mảng online learning.

Batch and mini batch

Thay do dùng một điểm để cập nhật, ta chia nhiều điểm vào bình thường một batch rồi dùng để update Gradient. điều này giúp tận dụng tài liệu và cũng cải thiện tốc độ tính toán. Hàm mất non của SGD cùng Batch, mini batch GD ko phải khi nào cũng sút nhưng nhìn toàn diện là hội tụ càng về cuối. Cách thức này được sử dụng rộng rãi trong những bài toán Deep learning.

Stopping criteria

Có các chú ý sau khi dừng thuật toán GD:

Giới hạn số vòng lặp, tốt số epoch để ngăn cản tình trạng GD không tìm được nghiệm bởi learning rate quá rộng hoặc kiêng tình trạng mã sản phẩm của họ bị overfit. điểm yếu kém là đôi khi thuật toán GD chưa tìm kiếm được nghiệm thì đã biết thành dừng lại
So sánh giá trị gradient tại nhị lần cập nhật liên tiếp, khi quý giá này đủ bé dại thì ngừng thuật toán. điểm yếu kém là đôi khi việc tính gradient do đó sẽ không hữu dụng khi cần sử dụng SGD hoặc mini batch bởi sẽ tốn nhiều bộ lưu trữ khi có rất nhiều dữ liệu khiến cho ta không tồn tại được điểm mạnh khi dùng phương pháp này
So sánh quý hiếm của hàm mất non của nghiệm tại hai lần cập nhật liên tiếp, bao giờ giá trị này đủ bé dại thì ngừng lại. Yếu điểm của cách thức này là nếu như tại một thời điểm, điểm update của ta lâm vào hoàn cảnh vị trí điểm uốn tương đối bằng phẳng thì thuật toán cũng dừng lại trước lúc đạt giá chỉ trị ý muốn muốn.Phương pháp cuối cùng là kiểm soát sau một vài ba lần update nhất định. Vấn đề này góp giảm khối lượng tính toán cũng như giúp thuật toán quá được phần lớn điểm uốn cùng tím được rất trị phù hợp.Advance optimization

Một số hồ hết trở ngại béo trong việc tối ưu là các local minimum, những điểm uốn (điểm yên ổn ngựa), và vấn đề tiêu biến/ nở rộ Gradient (Vanishing/ exploding Gradient), ...

Ada
Grad

Trong một số trường hợp, bài toán chọn learning rate phù hợp có thể thay đổi một sự việc nhức nhối. Sự việc này đã được xử lý với Ada
Grad, vị thuật toán này vẫn coi learning rate là 1 trong những tham số biến thiên sau những lần chạy thuật toán.

Ada
Grad thường được dùng trong các vấn đề về sparse feature (đặc trưng thưa), lấy ví dụ như như các bài toán về xử lí ngôn ngữ tự nhiên, quảng cáo năng lượng điện toán, với lọc cộng tác. Thường rất nhiều những đặc trưng này hiếm khi được update để rất có thể được về tối ưu phần đông lại mang những ý nghĩa sâu sắc vô thuộc to lớn, còn những đặc trưng có tần số lộ diện cao thì được update liên tục. Bởi vì thế, vấn đề có một learning rate cố định và thắt chặt hoặc là thừa cao so với những feature được cập nhật nhiều lần hoặc là rất thấp đối với đầy đủ feature không nhiều được cập nhật.

Công thức của Ada
Grad như sau:

gn=∂w
L(yn,f(xt,w))g_n=partial_w
L(y_n,f(x_t,w))gn​=∂w​L(yn​,f(xt​,w))

sn=sn−1+gn2s_n=s_n-1+g_n^2sn​=sn−1​+gn2​

wn=wn−1−ηsn+ϵ⊙gtw_n=w_n-1-fracetasqrts_n+epsilonodot g_twn​=wn−1​−sn​+ϵ​η​⊙gt​

Trong kia s0s_0s0​ thường được chọn bởi 000.

*


*


Ta có thể hiểu sự đổi khác learning rate này như một hệ số “ma sát”, “ma sát” này còn có giá trị béo ở dốc và có mức giá trị bé dại ở vùng bằng phẳng.

Phân tích ưu và nhược của Ada
Grad:

Ưu điểm:

Hoạt động tốt với việc sparse feature, ví dụ là buổi tối ưu các bài toán lồi, không dao động thỉnh thoảng đạt vào rất tiểu yêu cầu thiết.Learning rate được tự động hóa điều chỉnh mang lại phù hợp
Chi phí đo lường không tăng trường hợp so cùng với SGD

Nhược điểm:

Trong deep learning, những bài toán hay không trọn vẹn lồi và có tương đối nhiều local minimum gây nhiễu.sns_nsn​ vào công thức update tăng một cách trong khi tuyến tính để cho learning rate bị thu bé dại nhanh.

RMSProp

Ada
Grad với tốc độ học biến đổi để ham mê nghi với dữ liệu là một phương pháp tuyệt vời trong số bài toán tối ưu lồi, mặc dù thế nó vẫn có những giảm bớt như vẫn nêu trên. Vì vậy RMSProp được lời khuyên để không giống phục những vụ việc của Ada
Grad bằng phương pháp kế thừa phát minh từ phương thức momentum vào gradient decent có tác dụng rò rỉ các giá trị của rnr_nrn​ trong bí quyết cập nhật. Ví dụ công thức của RMSProp là:

gn=∂w
L(yn,f(xt,w))g_n=partial_w
L(y_n,f(x_t,w))gn​=∂w​L(yn​,f(xt​,w))

sn=γsn−1+(1−γ)gn2s_n=gamma s_n-1+(1-gamma)g_n^2sn​=γsn−1​+(1−γ)gn2​

wn=wn−1−ηsn+ϵ⊙gtw_n=w_n-1-fracetasqrts_n+epsilonodot g_twn​=wn−1​−sn​+ϵ​η​⊙gt​

Việc khiến cho sns_nsn​ bị thất thoát cũng đồng thời chuẩn hóa giá chỉ của trị số đứng trước giá trị của sns_nsn​, vì vậy mà xử lý được vụ việc learning rate bị thu nhỏ khiến thuật toán ngừng sớm.

*

Ta thấy rằng RMSProp thừa kế được những ưu thế của Ada
Grad về vấn đề tự điều chỉnh learning rate, thuật toán đã đi được xa hơn so với Ada
Grad với cùng learning rate 0.40.40.4

Adam

Trong một câu hỏi tối ưu thường gặp, ta mong mỏi thuật toán của bản thân đầu tiên quá qua đều local minimum nhiễu một phương pháp dễ dàng, nhưng lại khi có được global minimum thì sẽ không dao hễ quá lâu mà tìm kiếm được vị trí tương xứng ngay. Điều này liên hệ ta tìm kiếm một thuật gồm hành vi được mô tả như trên.

Có một thuật toán đã hội tụ đủ mọi ưu điểm của những cách thức trước đó, đó chính là Adam, được sử dụng rất thịnh hành trong vấn đề deep learning. Thuật toán của Adam được ví như 1 quả trơn có khối lượng lớn và tất cả ma sát vì nó tất cả động lượng rò rỉ để vượt qua các local minimum để tiến đến gobal ninimum cùng không xấp xỉ lâu vì gồm ma sát thừa kế từ Ada
Grad

Thuật toán của Adam như sau:

gn=∂w
L(yn,f(xt,w))g_n=partial_w
L(y_n,f(x_t,w))gn​=∂w​L(yn​,f(xt​,w))

vn=β1vn−1+(1−β1)gnv_n=eta_1v_n-1+(1-eta_1)g_nvn​=β1​vn−1​+(1−β1​)gn​

sn=β2sn−1+(1−β2)gn2s_n=eta_2 s_n-1+(1-eta_2)g_n^2sn​=β2​sn−1​+(1−β2​)gn2​

v^n=vn1−β1n,s^n=sn1−β2nhatv_n=fracv_n1-eta_1^n, hats_n=fracs_n1-eta_2^nv^n​=1−β1n​vn​​,s^n​=1−β2n​sn​​

gn′=ηv^ns^n+ϵg"_n=fraceta hatv_nsqrthats_n+epsilongn′​=s^n​​+ϵηv^n​​

xn+1=xn−gn′x_n+1=x_n-g"_nxn+1​=xn​−gn′​

Trong đó, β1eta_1β1​ cùng β2eta_2β2​ hay được chọn là 0.90.90.9 với 0.990.990.99. Các giá trị v0v_0v0​ và s0s_0s0​ cũng thường xuyên được cho bởi 000.

Tuy nhiên, Adam tuy có lợi thế về learning rate và cồn lượng dẫu vậy trong một số trong những trường hợp độc nhất vô nhị định, Adam sẽ ban đầu phân kì. Tất cả một bài báo đã nêu lên và đối chiếu điều này:

So sánh những thuật toán tối ưu:

*

*

Ngoài ra, ta vẫn hoàn toàn có thể sử dụng những thuật toán dễ dàng và đơn giản như SGD với momentum, hoặc chỉ SGD nhưng mà kết hợp với bộ định thời vận tốc học ( Learning rate scheduling) để đạt được vận tốc học mong mỏi muốn.

Xem thêm: Smart Tivi Sony 55 Inch 55X8500G, 4K Ultra Hdr, Android Tv, Hỗ Trợ Cho Kd

Tài liệu tham khảo
Sách Machine Learning Cơ bản. Tác giả: bác bỏ Vũ Hữu Tiệp
Ngoài ra bản thân còn tham khảo một số nguồn ko kể khác nhưng thiết yếu thì chỉ tất cả hai mối cung cấp dẫn trên thôi .