Giới thiệu về kỹ thuật xuống dốc [gradient descent]
Trong phần 1, chúng ta sử dụng kỹ thuật xuống dốc để tìm điểm cực tiểu của hàm mất mát trong phương pháp hồi quy tuyến tính. Phần 2 của loạt bài Máy học phổ thông sẽ xem xét kỹ thuật xuống dốc cặn kẽ hơn.
Nội dung chính
- Giới thiệu về kỹ thuật xuống dốc [gradient descent]
- Tìm điểm cực tiểu của một pa-ra-bôn
- Lập ra công thức xuống dốc
- Xem xét ảnh hưởng của tốc độ học
- Tìm điểm cực tiểu của hàm bậc 4
- Cực tiểu cục bộ và cực tiểu toàn cục
- Ảnh hưởng khác của tốc độ học
- Tìm điểm cực tiểu của hàm đa biến
- Định nghĩa dốc [gradient]
- Tài liệu đọc thêm
Kỹ thuật xuống dốc là một thuật toán tối ưu hóa [optimization algorithm] để tìm giá trị cực tiểu của một hàm. Như nhiều thuật toán tối ưu hóa khác, kỹ thuật xuống dốc lặp đi lặp lại một thủ tục tính toán để tìm ra giá trị kế tiếp, thường là tốt hơn, từ giá trị hiện tại.
Vì không phải là thuật toán chính xác, kỹ thuật xuống dốc không hứa hẹn trả về giá trị cực tiểu toàn cục [global minimum] mà chỉ có khả năng cao sẽ tìm thấy giá trị cực tiểu cục bộ [local minimum]. Mặc dù có khuyết điểm lớn này nhưng trong thực tế kỹ thuật xuống dốc vẫn được sử dụng nhiều bởi vì:
- Hàm cần tìm giá trị cực tiểu thường đơn giản và chỉ có một vài, hoặc thậm chí chỉ có duy nhất, cực tiểu. Như đã xét qua ở phần 1, hàm mất mát của hồi quy tuyến tính chỉ có duy nhất một cực tiểu.
- Chúng ta có thể thực hiện kỹ thuật xuống dốc nhiều lần với nhiều vị trí khởi đầu ngẫu nhiên, và chọn lại giá trị cực tiểu đã tìm được trong tất cả các lần xuống dốc.
- Trong nhiều bài toán, lời giải chính xác không quan trọng bằng lời giải tốt vừa đủ. Chúng ta sẽ thấy rằng trong máy học, sự gần đúng được tận dụng rất nhiều. Suy cho cùng, ai có thể đoán được giá nhà trong tương lai một cách chính xác? Chúng ta chỉ có thể ước lượng gần đúng mà thôi.
Với những điều trên, chúng ta sẽ xem xét kỹ thuật xuống dốc thông qua một vài ví dụ cụ thể.
Tìm điểm cực tiểu của một pa-ra-bôn
Lập ra công thức xuống dốc
Một trong những bài toán thường gặp ở chương trình phổ thông là khảo sát hàm số. Bạn đọc chắc chắn đã quá quen thuộc với việc vẽ đồ thị pa-ra-bôn, hoặc tạo bảng biến thiên. Chúng ta sẽ bắt đầu từ đó.
Gọi hàm \[y = x^2 - 2x - 5\]. Đạo hàm bậc nhất của hàm này là \[y^\prime = 2x - 2\], có nghiệm tại \[x = 1\]. Đồ thị của hàm này được thể hiện trong hình sau.
Đồ thị và tiếp tuyến tại ba điểm
import math from matplotlib import pyplot as plt def f[x]: return x**2 - 2*x - 5 def f_prime[x]: return 2*x - 2 def tangent[x0]: slope = f_prime[x0] angle = math.atan[slope] magnitude = int[abs[slope]] y0 = f[x0] dx = magnitude * math.cos[angle] dy = dx * slope return x0, y0, dx, dy xs = list[x / 100.0 for x in range[-250, 450]] ys = [f[x] for x in xs] plt.plot[xs, ys, 'b-'] plt.plot[[1], [f[1]], 'yo'] plt.arrow[*tangent[-2], width=0.07, fc='red', ec='none', zorder=2] plt.plot[*tangent[-2][:2], marker='o', color='red', zorder=3] plt.arrow[*tangent[2], width=0.07, fc='green', ec='none', zorder=2] plt.plot[*tangent[2][:2], marker='o', color='green', zorder=3] plt.savefig['gradient-descent-1.png']
Nếu chúng ta lập bảng biến thiên, chúng ta sẽ có bảng sau:
\begin{equation*} \begin{array}{c|cccccc} x & -\infty & & & & +\infty \\ \hline f^\prime[x] & & - & 1 & + & & \\ \hline f[x] & +\infty & & & & +\infty \\ & & \searrow & & \nearrow & \\ & & & -6 & & \end{array} \end{equation*}
Dựa vào bảng biến thiên, ta thấy rằng giá trị của hàm giảm xuống khi biến số tiến từ \[-\infty\] đến nghiệm của đạo hàm bậc nhất và tăng lên khi biến số tiếp tục tiến về \[+\infty\]. Dựa vào đồ thị, ta thấy độ tăng hay giảm giá trị của hàm [trên trục \[y\]] phụ thuộc vào góc của tiếp tuyến, cũng là giá trị của đạo hàm bậc nhất. Tổng hợp hai nhận xét này, chúng ta đi đến kết luận chủ đạo của kỹ thuật xuống dốc:
- Khi giá trị của đạo hàm bậc nhất là âm [tức là dốc xuống], ta cần tăng giá trị của biến [đi xuống theo dốc]. Khi giá trị đó là dương [tức là dốc lên], ta cần giảm giá trị của biến [đi xuống ngược dốc]. Nói một cách khác, giá trị biến cần phải thay đổi theo chiều ngược lại so với dấu của đạo hàm. Đây là lý do của tên gọi của kỹ thuật này.
- Ta có thể dùng giá trị của đạo hàm bậc nhất để điều chỉnh độ tăng / giảm của biến.
Từ hai kết luận chủ đạo đó, ta lập ra công thức cập nhật biến theo kỹ thuật xuống dốc như sau:
\begin{equation*} x^{[t+1]} = x^{[t]} - \alpha \times f^\prime \left[ x^{[t]} \right] \end{equation*}
Ký hiệu \[x^{[t]}\] có nghĩa là giá trị của biến \[x\] tại thời điểm \[t\]. Dấu trừ trong công thức trên thể hiện điểm 1, và tích của \[\alpha\] với đạo hàm bậc nhất thể hiện điểm 2.
Hệ số \[\alpha > 0\] được gọi là tốc độ học [learning rate]. Nhiều tài liệu khác sử dụng ký hiệu \[\eta\] hay \[\gamma\] để chỉ cùng một ý. Khi tốc độ học lớn, sự thay đổi của biến cũng cao, và ngược lại. Trong thực tế, tốc độ học thường được làm giảm dần [decay] theo thời gian nhằm tránh trường hợp biến nhảy qua nhảy lại ở hai bên điểm cực tiểu.
Cuối cùng, cài đặt kỹ thuật xuống dốc để tìm điểm cực tiểu trong ví dụ này đơn giản như sau:
import random import sys def f_prime[x]: return 2*x - 2 # Chọn ngẫu nhiên giá trị ban đầu của x. x = random.randint[-sys.maxint, sys.maxint] # Chọn alpha vừa phải. alpha = 0.1 # Lặp 1000 lần. for _ in range[1000]: x = x - alpha * f_prime[x] print[x]
Kết quả nhận được khi chạy chương trình này trùng khớp với điểm cực tiểu:
1.0
Xem xét ảnh hưởng của tốc độ học
Đoạn ảnh sau minh họa ảnh hưởng của hệ số \[\alpha\] đến việc xuống dốc. Hai điểm đỏ và xanh lá cây ở trong hình đều xuất phát cùng một chỗ. Ở bên trái, với tốc độ học thấp, chúng ta thấy điểm đỏ di chuyển khá chậm. Ở bên phải, với tốc độ học cao hơn, ta thấy điểm xanh chỉ chuyển từ nhánh phải qua nhánh trái mà không thật sự đi xuống.
Ảnh hưởng của tốc độ học
# encoding: utf-8 from matplotlib import pyplot as plt from matplotlib import animation def f[x]: return x**2 - 2*x - 5 def f_prime[x]: return 2*x - 2 def run[t]: global dot1, dot2, x_slow, x_bounce x_slow = x_slow - 0.02 * f_prime[x_slow] x_bounce = x_bounce - 1.0 * f_prime[x_bounce] dot1.set_data[[x_slow], [f[x_slow]]] dot2.set_data[[x_bounce], [f[x_bounce]]] plt.suptitle[u'Bước {}'.format[t]] # Cùng bắt đầu từ một điểm. x_slow = 2.5 x_bounce = 2.5 xs = list[range[-100, 300]] fig, [ax1, ax2] = plt.subplots[1, 2] ax1.plot[[x / 100.0 for x in xs], [f[x / 100.0] for x in xs]] ax1.set_title[r'$\alpha = 0.02$'] dot1 = ax1.plot[[x_slow], [f[x_slow]], 'ro'][0] ax2.plot[[x / 100.0 for x in xs], [f[x / 100.0] for x in xs]] ax2.set_title[r'$\alpha = 1.0$'] dot2 = ax2.plot[[x_bounce], [f[x_bounce]], 'go'][0] anim = animation.FuncAnimation[fig, run, repeat=False, frames=40] anim.save['gradient-descent-2.gif', writer='imagemagick']
Tìm điểm cực tiểu của hàm bậc 4
Ví dụ kế tiếp của chúng ta là một hàm bậc 4. Chúng ta sẽ xem xét hàm \[y = x^4 + 4x^3 + x^2 - 4x + 3\]. Đạo hàm bậc nhất là \[y^\prime = 4x^3 + 12x^2 + 2x - 4\]. Đồ thị của hàm này được thể hiện trong hình bên dưới.
Đồ thị hàm bậc 4 với hai cực tiểu
from matplotlib import pyplot as plt def f[x]: return x**4 + 4*x**3 + x**2 - 4*x + 3 xs = [x / 100.0 for x in range[-360, 140]] ys = [f[x] for x in xs] plt.plot[xs, ys] plt.grid[] plt.axhline[y=0, color='black'] plt.axvline[x=0, color='black'] plt.savefig['gradient-descent-3.png']
Cực tiểu cục bộ và cực tiểu toàn cục
Chúng ta thấy rằng đồ thị trên có hai điểm cực tiểu cục bộ. Điểm cực tiểu cục bộ bên trái cũng là điểm cực tiểu toàn cục. Hình sau minh họa kỹ thuật xuống dốc với bốn điểm khởi đầu ngẫu nhiên.
Xuống dốc với khởi đầu ngẫu nhiên
import random import sys from matplotlib import pyplot as plt from matplotlib import animation def f[x]: return x**4 + 4*x**3 + x**2 - 4*x + 3 def f_prime[x]: return 4*x**3 + 12*x**2 + 2*x - 4 def run[t]: global alpha, dot_xs, dots [dot.set_data[[x], [f[x]]] for dot, x in zip[dots, dot_xs]] for i in range[len[dot_xs]]: dot_xs[i] = dot_xs[i] - alpha * f_prime[dot_xs[i]] # Khởi tạo ngẫu nhiên. xs = list[range[-360, 140]] nr_dots = 4 dot_xs = [random.randint[min[xs], max[xs] - 1] / 100.0 for _ in range[nr_dots]] alpha = 0.01 fig, ax = plt.subplots[] ax.plot[[x / 100.0 for x in xs], [f[x / 100.0] for x in xs]] dots = [ax.plot[[x], [f[x]], 'o'][0] for x in dot_xs] anim = animation.FuncAnimation[fig, run, repeat=False, frames=40] anim.save['gradient-descent-4.gif', writer='imagemagick']
Ta thấy rằng tùy vào vị trí khởi đầu mà điểm tròn có thể lọt vào cực tiểu cục bộ hay cực tiểu toàn cục. Nhận xét này dẫn đến một cách đơn giản để tăng cao tỷ lệ tìm được cực tiểu toàn cục: lập lại việc xuống dốc nhiều lần với khởi điểm khác nhau.
Ảnh hưởng khác của tốc độ học
Ví dụ đầu tiên trong bài viết này đã cho thấy ảnh hưởng của tốc độ học đến việc hội tụ của kỹ thuật xuống dốc. Trong ví dụ này, chúng ta sẽ thấy một ảnh hưởng khác của tốc độ học.
Tốc độ học lớn có thể giúp nhảy qua hố
from matplotlib import pyplot as plt from matplotlib import animation def f[x]: return x**4 + 4*x**3 + x**2 - 4*x + 3 def f_prime[x]: return 4*x**3 + 12*x**2 + 2*x - 4 def run[t]: # Chờ 10 khung hình đầu tiên. if t