Suy giảm độ dốc

Đối với phương pháp giải tích toán học được gọi là "dốc nhất", xem Phương pháp xuống dốc nhất.

Thuật toán 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 lặp bậc nhất để tìm một 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 gradien (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 gradien thì tiếp cận được một 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, 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 lần đầu tiên được nghiên cứu bởi Haskell Curry năm 1944.

Mô tả

Hình minh họa độ dốc trên một loạt tập mức

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

$\mathbf {a} _{n+1}=\mathbf {a} _{n}-\gamma \nabla F(\mathbf {a} _{n})$

đối với $\gamma \in \mathbb {R} _{+}$ đủ nhỏ, sau đó $F(\mathbf {a_{n}} )\geq F(\mathbf {a_{n+1}} )$. Theo cách nói khác, thuật ngữ $\gamma \nabla F(\mathbf {a} )$ được trừ khỏi $\mathbf {a}$ở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, người ta bắt đầu với một phỏng đoán $\mathbf {x} _{0}$ đối với một cực tiểu cục bộ của $F$, và xem chuỗi $\mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots$ là

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.$

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

$F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} _{2})\geq \cdots ,$

so hopefully the sequence $(\mathbf {x} _{n})$ converges to the desired local minimum. Note that the value of the step size $\gamma$ is allowed to change at every iteration. With certain assumptions on the function $F$ (for example, $F$ Convex function and $\nabla F$ Lipschitz continuity) and particular choices of $\gamma$ (e.g., chosen either via a Line search that satisfies the Wolfe conditions, or the Barzilai–Borwein method shown as following),

$\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}}}$

Chuỗi hội tụ to a local minimum can be guaranteed. When the function $F$ is Convex function, all local minima are also global minima, so in this case gradient descent can converge to the global solution.

This process is illustrated in the adjacent picture. Here $F$ is assumed to be defined on the plane, and that its graph has a Bát ăn shape. The blue curves are the Đường đồng mứcs, that is, the regions on which the value of $F$ is constant. A red arrow originating at a point shows the direction of the negative gradient at that point. Note that the (negative) gradient at a point is Orthogonality to the contour line going through that point. We see that gradient descent leads us to the bottom of the bowl, that is, to the point where the value of the function $F$ is minimal.

Xem thêm

• Backtracking line search
• Conjugate gradient method
• Stochastic gradient descent
• Rprop
• Delta rule
• Wolfe conditions
• Preconditioner
• Broyden–Fletcher–Goldfarb–Shanno algorithm
• Davidon–Fletcher–Powell formula
• Nelder–Mead method
• Gauss–Newton algorithm
• Hill climbing
• Quantum annealing

Đọc thêm

• Boyd, Stephen; Vandenberghe, Lieven (2004). “Unconstrained Minimization”. Convex Optimization. New York: Cambridge University Press. tr. 457–520. ISBN 0-521-83378-7.

Liên kết ngoài

• Using gradient descent in C++, Boost, Ublas for linear regression
• Series of Khan Academy videos discusses gradient ascent
• Online book teaching gradient descent in deep neural network context
• “Gradient Descent, How Neural Networks Learn”. 3Blue1Brown. ngày 16 tháng 10 năm 2017 – qua YouTube.