Xem mã nguồn của Suy giảm độ dốc

{{About||phương pháp [[giải tích toán học]] được gọi là "dốc nhất"|Phương pháp xuống dốc nhất}}
{{short description|Thuật toán tối ưu}}

'''Suy giảm độ dốc''' (còn gọi là '''giảm độ dốc''', [[tiếng Anh]]: '''gradient descent''') là một thuật toán [[Tối ưu hóa (toán học)|tối ưu hóa]] [[thuật toán lặp|lặp]] [[:Category:phương pháp bậc nhất|bậc nhất]] để tìm một [[Cực trị của hàm số|cực trị]] của một hàm khả vi. Để tìm cực tiểu cục bộ của một hàm sử dụng suy giảm độ dốc, người ta có thể thực hiện các bước tỷ lệ thuận với '''âm''' của [[gradient]] (hoặc độ dốc xấp xỉ) của hàm tại điểm hiện tại. Nhưng nếu thực hiện các bước tương ứng với '''dương''' của gradient thì tiếp cận được một [[Cực trị của hàm số|cực đại cục bộ]] của hàm số đó; phương pháp này được gọi là '''tăng độ dốc''' (gradient ascent). Nói chung, [[Augustin-Louis Cauchy]] được ghi công là người gợi ý về vấn đề suy giảm độ dốc vào năm 1847,<ref>{{chú thích tạp chí |first=C. |last=Lemaréchal |authorlink=Claude Lemaréchal |title=Cauchy and the Gradient Method |journal=Doc Math Extra |pages=251–254 |year=2012 |url=https://www.math.uni-bielefeld.de/documenta/vol-ismp/40_lemarechal-claude.pdf |access-date=2020-11-22 |archive-date=2018-12-29 |archive-url=https://web.archive.org/web/20181229073335/https://www.math.uni-bielefeld.de/documenta/vol-ismp/40_lemarechal-claude.pdf }}</ref> nhưng các tính chất hội tụ của nó cho các bài toán tối ưu hóa phi tuyến tính được [[Haskell Curry]] nghiên cứu lần đầu tiên năm 1944.<ref>{{chú thích tạp chí |first=Haskell B. |last=Curry |title=The Method of Steepest Descent for Non-linear Minimization Problems |url=https://archive.org/details/sim_quarterly-of-applied-mathematics_1944-10_2_3/page/258 |journal=Quart. Appl. Math. |volume=2 |year=1944 |issue=3 |pages=258–261 |doi=10.1090/qam/10667 |doi-access=free }}</ref>

== Mô tả ==
[[Tập tin:Gradient descent.svg|thumb|350px|Hình minh họa độ dốc trên một loạt [[tập mức]]. Điểm x0, x1,... là các điểm trực giao với các đường đồng mức (màu xanh) trong quá trình thực hiện thuật toán suy giảm độ dốc cho đến khi tìm được các điểm cực tiểu.]]

Độ dốc dựa trên quan sát nếu  [[hàm đa biến]] <math>F(\mathbf{x})</math> là [[Chưa xác định (toán học)|chưa xác định]] và [[hàm số khả vi|khả vi]] trong một vùng lân cận của một điểm <math>\mathbf{a}</math>, sau đó <math>F(\mathbf{x})</math> giảm ''nhanh nhất'' nếu đi từ <math>\mathbf{a}</math> theo hướng của độ dốc âm của <math>F</math> tại <math>\mathbf{a}, -\nabla F(\mathbf{a})</math>. Nó theo sau nếu

:<math> \mathbf{a}_{n+1} = \mathbf{a}_n-\gamma\nabla F(\mathbf{a}_n)</math>

đối với <math>\gamma \in \R_{+}</math> đủ nhỏ, khi đó <math>F(\mathbf{a_n})\geq F(\mathbf{a_{n+1}})</math>. Theo cách nói khác, giá trị <math>\gamma\nabla F(\mathbf{a})</math> được trừ bớt khỏi <math>\mathbf{a}</math> bởi vì chúng ta muốn di chuyển ngược lại độ dốc, hướng đến cực tiểu cục bộ. Với quan sát này, bắt đầu với một phỏng đoán <math>\mathbf{x}_0</math> đối với một cực tiểu cục bộ của <math>F</math>, và xem chuỗi <math>\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \ldots</math> là

:<math>\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n \nabla F(\mathbf{x}_n),\ n \ge 0.</math>

Khi đó, chúng ta có một chuỗi [[hàm số đơn điệu]]

:<math>F(\mathbf{x}_0)\ge F(\mathbf{x}_1)\ge F(\mathbf{x}_2)\ge \cdots,</math>

vì vậy hi vọng chuỗi <math>(\mathbf{x}_n)</math> hội tụ ở mức tối thiểu cục bộ mong muốn. Chú ý rằng giá trị ''kích thước nhảy'' (step size) <math>\gamma</math> được phép thay đổi ở mỗi lần lặp. Với các giả định nhất định về hàm <math>F</math> (ví dụ, [[hàm lồi]] <math>F</math> và [[tính liên tục Lipschitz|Lipschitz]] <math>\nabla F</math>) và các lựa chọn cụ thể của <math>\gamma</math> (ví dụ, được chọn thông qua một [[tìm kiếm dòng]] (line search) mà thỏa mãn các [[điều kiện Wolfe]], hoặc phương pháp Barzilai–Borwein<ref>{{chú thích tạp chí|last1=Barzilai|first1=Jonathan|last2=Borwein|first2=Jonathan M.|year=1988|title=Two-Point Step Size Gradient Methods|journal=IMA Journal of Numerical Analysis|volume=8|issue=1|pages=141–148|doi=10.1093/imanum/8.1.141}}</ref><ref>{{chú thích sách|last=Fletcher|first=R.|title=Optimization and Control with Applications|publisher=Springer|year=2005|isbn=0-387-24254-6|editor-last=Qi|editor-first=L.|series=Applied Optimization|volume=96|location=Boston|pages=235–256|chapter=On the Barzilai–Borwein Method|editor2-last=Teo|editor2-first=K.|editor3-last=Yang|editor3-first=X.}}</ref> được nêu như sau),

: <math>\gamma_{n} = \frac{ \left | \left (\mathbf x_{n} - \mathbf x_{n-1} \right)^T \left [\nabla F (\mathbf x_{n}) - \nabla F (\mathbf x_{n-1}) \right ] \right |}{\left \|\nabla F(\mathbf{x}_{n}) - \nabla F(\mathbf{x}_{n-1}) \right \|^2}</math>

[[Chuỗi hội tụ]] ở mức tối thiểu cục bộ có thể được đảm bảo. Khi hàm <math>F</math> là [[hàm lồi]], tất cả các cực tiểu cục bộ cũng là cực tiểu toàn cục, vì vậy trong trường hợp này, độ dốc giảm có thể hội tụ về giải pháp toàn cục.

Quá trình này được phác họa như trong hình bên cạnh. Với giả định <math>F</math> là được xác định trên mặt phẳng, và đồ thị của nó có hình [[bát ăn]]. Các đường cong màu xanh là các [[đường đồng mức]], nghĩa là, các vùng mà giá trị của <math>F</math> là không đổi (hằng số). Mũi tên màu đỏ bắt nguồn từ một điểm cho biết hướng của độ dốc âm tại điểm đó. Lưu ý độ dốc (âm) tại một điểm là [[trực giao]] (orthogonality, vuông góc) với các đường đồng mức đi qua điểm đó. Độ dốc ''suy giảm'' (rơi xuống) dẫn đường màu đỏ đến đáy của cái tô, tức là, đến điểm mà giá trị của hàm <math> F </math> là nhỏ nhất. Điểm này là điểm cần tìm trong các bài toán về suy giảm độ dốc.

== Xem thêm ==
{{Div col|colwidth=20em}}
* [[Backtracking line search]]
* [[Conjugate gradient method]]
* [[Stochastic gradient descent]]
* [[Rprop]]
* [[Luật Delta]]
* [[Điều kiện Wolfe]]
* [[Preconditioner]]
* [[Thuật toán Broyden–Fletcher–Goldfarb–Shanno]]
* [[Công thức Davidon–Fletcher–Powell]]
* [[Phương pháp Nelder–Mead]]
* [[Thuật toán Gauss–Newton]]
* [[Hill climbing]]
* [[Quantum annealing]]
{{Div col end}}

== Tham khảo ==
{{tham khảo|30em}}

== Đọc thêm ==
*{{chú thích sách |first1=Stephen |last1=Boyd |authorlink=Stephen P. Boyd |first2=Lieven |last2=Vandenberghe |chapter=Unconstrained Minimization |title=Convex Optimization |location=New York |publisher=Cambridge University Press |year=2004 |isbn=0-521-83378-7 |chapter-url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf#page=471 |pages=457–520 }}

== Liên kết ngoài ==
{{Thể loại Commons|Gradient descent}}
* [http://codingplayground.blogspot.it/2013/05/learning-linear-regression-with.html Using gradient descent in C++, Boost, Ublas for linear regression]
* [https://www.khanacademy.org/math/multivariable-calculus/multivariable-derivatives/gradient-and-directional-derivatives/v/gradient Series of Khan Academy videos discusses gradient ascent]
* [http://neuralnetworksanddeeplearning.com/chap1.html#learning_with_gradient_descent Online book teaching gradient descent in deep neural network context]
* {{chú thích web |work=3Blue1Brown |title=Gradient Descent, How Neural Networks Learn |date=ngày 16 tháng 10 năm 2017 |url=https://www.youtube.com/watch?v=IHZwWFHWa-w&list=PLZHQObOWTQDNU6R1_67000Dx_ZCJB-3pi&index=2 |via=[[YouTube]] }}

{{Thuật toán tối ưu}}
{{Điện toán khả vi}}
{{sơ khai}}

{{DEFAULTSORT:Gradient Descent}}
[[Thể loại:Tối ưu hóa (toán học)]]
[[Thể loại:Phương pháp bậc nhất]]
[[Thể loại:Thuật toán tối ưu hóa]]
[[Thể loại:Phương pháp độ dốc]]