Suy giảm độ dốc

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 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 đạ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 được Haskell Curry nghiên cứu lần đầu tiên năm 1944.

Mô tả 

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

đối với  đủ nhỏ, khi đó . Theo cách nói khác, giá trị  được trừ bớt khỏi  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  đối với một cực tiểu cục bộ của , và xem chuỗi  là

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

vì vậy hi vọng chuỗi  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)  được phép thay đổi ở mỗi lần lặp. Với các giả định nhất định về hàm  (ví dụ, hàm lồi  và Lipschitz ) và các lựa chọn cụ thể của  (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 được nêu như sau),

 

Chuỗi hội tụ ở mức tối thiểu cục bộ có thể được đảm bảo. Khi hàm  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  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  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  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 

 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

Tham khảo

Đọc thêm

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
 

Tối ưu hóa (toán học)
Phương pháp bậc nhất
Thuật toán tối ưu hóa
Phương pháp độ dốc