CÁCH TÍNH GRADIENT

     
1. Giới thiệu 2. Gradient Descent mang lại hàm 1 trở thành Ví dụ dễ dàng với Python 3. Gradient Descent đến hàm nhiều biến đổi Sau đó là ví dụ trên Python cùng một vài lưu ý khi lập trình kiểm tra đạo hàm

1. Giới thiệu

Các chúng ta hẳn thấy hình vẽ dưới đây quen thuộc:


*

Điểm blue color lục là vấn đề local minimum (cực tiểu), với cũng là vấn đề làm đến hàmsố đạt giá trị nhỏ dại nhất. Từ phía trên trở đi, tôi sẽ dùng local minimum để cầm cố chođiểm rất tiểu, global minimum để núm cho điểm nhưng mà tại đó hàm số đạt giá trịnhỏ nhất. Global minimum là 1 trong những trường hợp đặc biệt của local minimum.

Bạn đang xem: Cách tính gradient

Giả sử chúng ta đang quan tâm đến một hàm số một biến gồm đạo hàm hầu hết nơi. Xincho tôi được nhắc lại đôi điều đã thừa quen thuộc:

Điểm local minimum (x^*) của hàm số là vấn đề có đạo hàm (f’(x^*))bằng 0. Chưa dừng lại ở đó nữa, trong ở bên cạnh của nó, đạo hàm của những điểm phía bên trái(x^*) là không dương, đạo hàm của các điểm phía bên cần (x^*) làkhông âm.

Đường tiếp con đường với đồ vật thị hàm số đó tại một điểm bất kỳ có thông số góc chínhbằng đạo hàm của hàm số tại điểm đó.

Trong hình phía trên, các điểm phía bên trái của điểm local minimum màu xanh lục cóđạo hàm âm, những điểm mặt phải gồm đạo hàm dương. Và so với hàm số này, càng xavề phía trái của điểm local minimum thì đạo hàm càng âm, càng xa về phía phảithì đạo hàm càng dương.

Gradient Descent

Trong Machine Learning nói riêng và Toán tối Ưu nói chung, bọn họ thường xuyênphải tìm giá bán trị nhỏ tuổi nhất (hoặc đôi khi là khủng nhất) của một hàm số làm sao đó. Vídụ như các hàm mất đuối trong hai bài Linear Regression và K-means Clustering. Quan sát chung, việc đào bới tìm kiếm globalminimum của các hàm mất mát trong Machine Learning là rất phức tạp, thậm chí còn làbất khả thi. Nỗ lực vào đó, fan ta thường nỗ lực tìm những điểm local minimum, vàở một nấc độ như thế nào đó, coi chính là nghiệm cần tìm của bài bác toán.

Các điểm local minimum là nghiệm của phương trình đạo hàm bởi 0. Nếu bằng mộtcách nào đó hoàn toàn có thể tìm được toàn thể (hữu hạn) những điểm rất tiểu, ta chỉ cần thaytừng điểm local minimum đó vào hàm số rồi search điểm khiến cho hàm có giá trị nhỏnhất (đoạn này nghe rất quen thuộc, đúng không?). Tuy nhiên, trong đa số cáctrường hợp, bài toán giải phương trình đạo hàm bởi 0 là bất khả thi. Lý do cóthể đến từ sự tinh vi của dạng của đạo hàm, từ những việc các điểm dữ liệu có sốchiều lớn, hoặc từ việc có quá nhiều điểm dữ liệu.

Hướng tiếp cận thông dụng nhất là xuất phát từ một điểm mà bọn họ coi là gầnvới nghiệm của bài bác toán, sau đó dùng một phép toán lặp nhằm tiến dần mang đến điểmcần tìm, tức đến khi đạo hàm gần với 0. Gradient Descent (viết gọn gàng là GD) với cácbiến thể của nó là 1 trong trong những cách thức được dùng các nhất.

Vì kỹ năng về GD tương đối rộng cần tôi xin phép được chia thành hai phần. Phần 1này trình làng ý tưởng phía đằng sau thuật toán GD với một vài ba ví dụ dễ dàng giúp cácbạn có tác dụng quen cùng với thuật toán này và vài quan niệm mới. Phần 2 sẽ nói tới cácphương pháp cải tiến GD và những biến thể của GD trong những bài toán mà lại số chiều vàsố điểm tài liệu lớn. Những bài toán như vậy được hotline là large-scale.

2. Gradient Descent mang đến hàm 1 biến

Quay quay trở về hình vẽ ban sơ và một vài quan cạnh bên tôi đã nêu. Giả sử(x_t) là điểm ta tìm kiếm được sau vòng lặp thứ (t). Ta phải tìm một thuậttoán để đưa (x_t) về càng sát (x^*) càng tốt.

Trong hình đầu tiên, chúng ta lại tất cả thêm hai quan giáp nữa:

Nếu đạo hàm của hàm số tại (x_t): (f’(x_t) > 0) thì(x_t) nằm về bên cạnh phải so với (x^*) (và ngược lại). Để điểm tiếptheo (x_t+1) ngay gần với (x^*) hơn, bọn họ cần di chuyển(x_t) về phía mặt trái, tức về phía âm. Nói những khác, chúng ta cầndi chuyển ngược vệt với đạo hàm:Trong đó (Delta) là 1 trong những đại lượng ngược vết với đạo hàm (f’(x_t)).

(x_t) càng xa (x^*) về phía bên phải thì (f’(x_t)) càng lớnhơn 0 (và ngược lại). Vậy, lượng di chuyển (Delta), một phương pháp trực quannhất, là tỉ lệ thành phần thuận với (-f’(x_t)).

Hai dấn xét phía trên cho họ một cách update đơn giản là:

Trong kia (eta) (đọc là eta) là một trong những dương được call là learning rate(tốc độ học). Dấu trừ biểu hiện việc chúng ta phải đi ngược cùng với đạo hàm (Đâycũng chính là lý do phương thức này được điện thoại tư vấn là Gradient Descent - descentnghĩa là đi ngược). Các quan sát đơn giản dễ dàng phía trên, mặc dù không yêu cầu đúngcho toàn bộ các bài bác toán, là căn nguyên cho khôn xiết nhiều phương pháp tối ưu nói chungvà thuật toán Machine Learning nói riêng.

Ví dụ đơn giản và dễ dàng với Python

Xét hàm số (f(x) = x^2 + 5sin(x)) cùng với đạo hàm (f’(x) = 2x + 5cos(x))(một tại sao tôi chọn hàm này bởi nó rất khó tìm nghiệm của đạo hàm bằng 0 như hàmphía trên). Mang sử ban đầu từ một điểm (x_0) làm sao đó, tại vòng lặp thứ(t), chúng ta sẽ update như sau:

Như thường lệ, tôi khai báo vài ba thư viện quen thuộc thuộc


# To support both python 2 & python 3from __future__ import division, print_function, unicode_literalsimport mathimport numpy as np import matplotlib.pyplot as plt
Tiếp theo, tôi viết những hàm số :

grad nhằm tính đạo hàm cost để tính quý giá của hàm số. Hàm này không sử dụng vào thuật toánnhưng thường xuyên được dùng làm kiểm tra việc tính đạo hàm của đúng không ạ hoặc đểxem quý hiếm của hàm số gồm giảm theo mỗi vòng lặp tốt không. MyGD1 là phần chính tiến hành thuật toán Gradient Desent nêu phía trên. Đầuvào của hàm số này là learning rate với điểm bắt đầu. Thuật toán tạm dừng khiđạo hàm tất cả độ béo đủ nhỏ.

def grad(x): return 2*x+ 5*np.cos(x)def cost(x): return x**2 + 5*np.sin(x)def myGD1(eta, x0): x = for it in range(100): x_new = x<-1> - eta*grad(x<-1>) if abs(grad(x_new)) 1e-3: break x.append(x_new) return (x, it)

Điểm khởi sinh sản khác nhau

Sau lúc có các hàm bắt buộc thiết, tôi thử tìm kiếm nghiệm với những điểm khởi tạo thành khác nhaulà (x_0 = -5) với (x_0 = 5).


(x1, it1) = myGD1(.1, -5)(x2, it2) = myGD1(.1, 5)print("Solution x1 = %f, cost = %f, obtained after %d iterations"%(x1<-1>, cost(x1<-1>), it1))print("Solution x2 = %f, cost = %f, obtained after %d iterations"%(x2<-1>, cost(x2<-1>), it2))
Vậy là với các điểm ban đầu khác nhau, thuật toán của họ tìm được nghiệmgần tương tự nhau, tuy nhiên với tốc độ hội tụ không giống nhau. Dưới đây là hình hình ảnh minhhọa thuật toán GD cho việc này (xem giỏi trên Desktop ở chế độ full mànhình).

*
*

Từ hình minh họa bên trên ta thấy rằng nghỉ ngơi hình bên trái, tương xứng với (x_0 = -5), nghiệm quy tụ nhanh hơn, bởi vì điểm lúc đầu (x_0) sát với nghiệm ( x^* approx -1) hơn. Hơn nữa, cùng với (x_0 = 5 ) ngơi nghỉ hình bên phải, đường đi của nghiệm tất cả chứa một quanh vùng có đạo hàm khá nhỏ gần điểm bao gồm hoành độ bởi 2. Điều này để cho thuật toán la cà ở đây khá lâu. Khi vượt qua được điểm đó thì mọi bài toán diễn ra rất tốt đẹp.

Learning rate khác nhau

Tốc độ quy tụ của GD không những nhờ vào vào điểm khởi tạo lúc đầu mà còn phụ thuộc vào vào learning rate. Dưới đấy là một lấy một ví dụ với cùng điểm khởi tạo (x_0 = -5) tuy vậy learning rate khác nhau:

*
*

Ta quan gần kề thấy nhì điều:

với learning rate nhỏ (eta = 0.01), tốc độ hội tụ siêu chậm. Trong vídụ này tôi chọn tối đa 100 vòng lặp đề nghị thuật toán dừng lại trước lúc tớiđích, mặc dù đã vô cùng gần. Vào thực tế, lúc việc tính toán trở bắt buộc phứctạp, learning rate cực thấp sẽ tác động tới vận tốc của thuật toán rấtnhiều, thậm chí không lúc nào tới được đích. Cùng với learning rate bự (eta = 0.5), thuật toán tiến rất cấp tốc tới gầnđích sau vài ba vòng lặp. Tuy nhiên, thuật toán không hội tụ được vì chưng bướcnhảy thừa lớn, khiến nó cứ quẩn quanh nghỉ ngơi đích.

Việc chọn lọc learning rate rất đặc biệt trong các bài toán thực tế. Việclựa lựa chọn giá trị này nhờ vào nhiều vào từng vấn đề và phải làm một vài ba thínghiệm để lựa chọn ra giá trị xuất sắc nhất. Xung quanh ra, tùy vào một vài bài toán, GD tất cả thểlàm việc kết quả hơn bằng phương pháp chọn ra learning rate phù hợp hoặc chọnlearning rate không giống nhau ở mỗi vòng lặp. Tôi sẽ quay lại vấn đề này ở chỗ 2.

3. Gradient Descent cho hàm các biến

Giả sử ta yêu cầu tìm global minimum mang lại hàm (f(mathbf heta)) trong đó(mathbf heta) (theta) là 1 vector, thường được dùng làm ký hiệu tậphợp những tham số của một quy mô cần tối ưu (trong Linear Regression thì các thamsố chính là hệ số (mathbfw)). Đạo hàm của hàm số đó tại một điểm( heta) bất kỳ được ký hiệu là ( abla_ hetaf( heta)) (hình tamgiác ngược đọc là nabla). Tựa như như hàm 1 biến, thuật toán GD mang đến hàm nhiềubiến cũng bắt đầu bằng một điểm dự đoán ( heta_0), sau đó, làm việc vòng lặpthứ (t), quy tắc cập nhật là:

< heta_t+1 = heta_t - eta abla_ heta f( heta_t)>

Hoặc viết bên dưới dạng đơn giản và dễ dàng hơn: ( heta = heta - eta abla_ heta f( heta)).

Quy tắc yêu cầu nhớ: luôn luôn luôn đi ngược hướng với đạo hàm.

Việc đo lường đạo hàm của những hàm nhiều biến là một năng lực cần thiết. Một vài ba đạo hàm đối kháng giản hoàn toàn có thể được search thấy nghỉ ngơi đây.

Quay lại với câu hỏi Linear Regression

Trong mục này, chúng ta quay lại với bài toán Linear Regression với thử tối ưu hàm mất non của nó bằng thuật toán GD.

Hàm mất mát của Linear Regression là:

Chú ý: hàm này còn có khác một chút ít so với hàm tôi nêu trong bài Linear Regression. Chủng loại số bao gồm thêm (N) là số lượng dữ liệu vào training set. Vấn đề lấy trung bình cộng của lỗi này nhằm giúp tránh vấn đề hàm mất mát và đạo hàm có mức giá trị là một số rất lớn, ảnh hưởng tới độ đúng mực của những phép toán khi triển khai trên trang bị tính. Về mặt toán học, nghiệm của hai việc là như nhau.

Đạo hàm của hàm mất mát là:< abla_mathbfwmathcalL(mathbfw) = frac1NmathbfarX^T mathbf(arXw - y) ~~~~~(1)>

Sau đấy là ví dụ trên Python cùng một vài lưu ý khi lập trình

Load thư viện


# To support both python 2 và python 3from __future__ import division, print_function, unicode_literalsimport numpy as np import matplotlibimport matplotlib.pyplot as pltnp.random.seed(2)
Tiếp theo, bọn họ tạo 1000 điểm tài liệu được lựa chọn gần với đường thẳng (y = 4 + 3x), hiển thị bọn chúng và kiếm tìm nghiệm theo công thức:


X = np.random.rand(1000, 1)y = 4 + 3 * X + .2*np.random.randn(1000, 1) # noise added# Building Xbar one = np.ones((X.shape<0>,1))Xbar = np.concatenate((one, X), axis = 1)A = np.dot(Xbar.T, Xbar)b = np.dot(Xbar.T, y)w_lr = np.dot(np.linalg.pinv(A), b)print("Solution found by formula: w = ",w_lr.T)# Display resultw = w_lrw_0 = w<0><0>w_1 = w<1><0>x0 = np.linspace(0, 1, 2, endpoint=True)y0 = w_0 + w_1*x0# Draw the fitting line plt.plot(X.T, y.T, "b.") # data plt.plot(x0, y0, "y", linewidth = 2) # the fitting lineplt.axis(<0, 1, 0, 10>)plt.show()

*

Kiểm tra đạo hàm

Việc tính đạo hàm của hàm những biến thường thì khá tinh vi và rất đơn giản mắc lỗi, nếu chúng ta tính không nên đạo hàm thì thuật toán GD tất yêu chạy đúng được. Vào thực nghiệm, bao gồm một phương pháp để kiểm tra liệu đạo hàm tính được có đúng đắn không. Biện pháp này dựa trên định nghĩa của đạo hàm (cho hàm 1 biến):

Một cách thường được thực hiện là rước một quý hiếm (varepsilon ) vô cùng nhỏ, lấy ví dụ như (10^-6), và áp dụng công thức:

Cách tính này được gọi là numerical gradient.

Xem thêm: Tờ Khai Đơn Vị Tham Gia, Điều Chỉnh Bhxh, Bhyt ( Mẫu Tk3-Ts Theo Quyết Định 595

Câu hỏi: nguyên nhân công thức xê dịch hai phía bên trên đây lại được sử dụng rộng rãi, sao không áp dụng công thức dao động đạo hàm bên yêu cầu hoặc bên trái?

Có nhì các phân tích và lý giải cho vấn đề này, một bởi hình học, một bằng giải tích.

Giải thích bởi hình học

Quan tiếp giáp hình dưới đây:


*

Trong hình, vector màu đỏ là đạo hàm chính xác của hàm số trên điểm có hoành độ bởi (x_0). Vector màu xanh da trời lam (có vẻ là hơi tím sau khi convert trường đoản cú .pdf thanh lịch .png) biểu thị cách xê dịch đạo hàm phía phải. Vector màu xanh lá cây lục biểu hiện cách xấp xỉ đạo hàm phía trái. Vector màu sắc nâu thể hiện cách giao động đạo hàm nhì phía. Trong cha vector xê dịch đó, vector dao động hai phía màu nâu là sát với vector đỏ độc nhất nếu xét theo hướng.

Sự khác hoàn toàn giữa những cách dao động còn lớn hơn nữa nếu tại điểm x, hàm số bị bẻ cong mạnh hơn. Lúc đó, dao động trái và phải sẽ khác biệt rất nhiều. Xấp xỉ phía 2 bên sẽ ổn định hơn.

Giải thích bằng giải tích

Chúng ta cùng quay trở về một chút với Giải tích I năm đầu tiên đại học: khai triển Taylor.

Với (varepsilon) hết sức nhỏ, ta tất cả hai xấp xỉ sau:

và:

Từ kia ta có:

Từ đó, nếu xê dịch đạo hàm bằng công thức ((3)) (xấp xỉ đạo hàm phải), sai số đang là (O(varepsilon)). Trong khi đó, nếu xấp xỉ đạo hàm bằng công thức ((4)) (xấp xỉ đạo hàm nhì phía), không đúng số đã là (O(varepsilon^2) ll O(varepsilon)) nếu như (varepsilon) nhỏ.

Cả hai cách lý giải trên đây số đông cho chúng ta thấy rằng, dao động đạo hàm haiphía là xấp xỉ xuất sắc hơn.

Với hàm những biến

Với hàm nhiều biến, bí quyết ((2)) được áp dụng cho từng trở thành khi những biếnkhác cố gắng định. Cách tính này thường đến giá trị khá chủ yếu xác. Tuy nhiên, cáchnày không được thực hiện để tính đạo hàm vì độ phức hợp quá cao so với biện pháp tínhtrực tiếp. Khi so sánh đạo hàm này cùng với đạo hàm đúng đắn tính theo công thức,người ta thường giảm số chiều tài liệu và bớt số điểm tài liệu để thuận tiện chotính toán. Một khi đạo hàm tính được hết sức gần với numerical gradient, bọn chúng tacó thể tự tin tưởng rằng đạo hàm tính được là chủ yếu xác.

Dưới đó là một đoạn code dễ dàng để soát sổ đạo hàm và hoàn toàn có thể áp dụng với mộthàm số (của một vector) bất kỳ với cost và grad đang tính nghỉ ngơi phía trên.


def numerical_grad(w, cost): eps = 1e-4 g = np.zeros_like(w) for i in range(len(w)): w_p = w.copy() w_n = w.copy() w_p += eps w_n -= eps g = (cost(w_p) - cost(w_n))/(2*eps) return g def check_grad(w, cost, grad): w = np.random.rand(w.shape<0>, w.shape<1>) grad1 = grad(w) grad2 = numerical_grad(w, cost) return True if np.linalg.norm(grad1 - grad2) 1e-6 else False print( "Checking gradient...", check_grad(np.random.rand(2, 1), cost, grad))
Sau 49 vòng lặp, thuật toán đã hội tụ với một nghiệm khá ngay sát với nghiệm tìm đượctheo công thức.

Dưới đây là hình cồn minh họa thuật toán GD.

*
*

Trong hình bên trái, những đường thẳng màu đỏ là nghiệm tìm kiếm được sau mỗi vòng lặp.

Trong hình bên phải, tôi xin giới thiệu một thuật ngữ mới: đường đồng mức.

Đường đồng nấc (level sets)

Với thiết bị thị của một hàm số với hai biến đổi đầu vào cần được vẽ trong không gian bachiều, nhều khi bọn họ khó quan sát được nghiệm có khoảng tọa độ bao nhiêu. Trongtoán tối ưu, người ta hay sử dụng một bí quyết vẽ thực hiện khái niệm đường đồng mức(level sets).

Nếu các bạn để ý vào các phiên bản độ từ bỏ nhiên, để mô tả độ cao của các dãy núi,người ta dùng nhiều đường cong kín bao bọc nhau như sau:


*

Các vòng nhỏ tuổi màu đỏ hơn thể hiện các điểm sinh hoạt trên cao hơn.

Trong toán tối ưu, fan ta cũng dùng phương pháp này để thể hiện những bề mặttrong không khí hai chiều.

Quay quay trở về với hình minh họa thuật toán GD cho vấn đề Liner Regression bêntrên, hình bên đề nghị là hình biểu diễn các level sets. Tức là tại những điểm trêncùng một vòng, hàm mất mát có giá trị như nhau. Trong lấy ví dụ như này, tôi hiển thịgiá trị của hàm số tại một vài vòng. Những vòng màu xanh da trời có cực hiếm thấp, các vòngtròn màu đỏ phía ngoài có mức giá trị cao hơn. Điểm này khác một ít so với đườngđồng nấc trong tự nhiên là những vòng bên phía trong thường thể hiện một thung lũng hơnlà một đỉnh núi (vì chúng ta đang đi tìm kiếm giá trị bé dại nhất).

Tôi test với learning rate bé dại hơn, kết quả như sau:

*
*

Tốc độ hội tụ đã chậm rãi đi nhiều, thậm chí còn sau 99 vòng lặp, GD vẫn không đến gầnđược nghiệm tốt nhất. Trong các bài toán thực tế, bọn họ cần nhiều vòng lặphơn 99 khôn xiết nhiều, vị số chiều và số điểm dữ liệu thường là rất lớn.

4. Một lấy một ví dụ khác

Để hoàn thành phần 1 của Gradient Descent, tôi xin nêu thêm một ví dụ khác.


*

Hàm số (f(x, y) = (x^2 + y - 7)^2 + (x - y + 1)^2) gồm hai điểm local minimummàu xanh lục trên ((2, 3)) với ((-3, -2)), và chúng cũng là nhị điểmglobal minimum. Trong lấy ví dụ này, tùy từng điểm khởi tạo thành mà chúng ta thu được cácnghiệm cuối cùng khác nhau.

5. Thảo luận

Dựa trên GD, có rất nhiều thuật toán tinh vi và tác dụng hơn có thiết kế chonhững loại câu hỏi khác nhau. Vì bài xích này vẫn đủ dài, tôi xin phép dừng lại ởđây. Mời các bạn đón đọc bài Gradient Descent phần 2 với rất nhiều kỹ thuật nâng caohơn.

6. Tài liệu tham khảo


Nếu gồm câu hỏi, bạn có thể để lại comment bên dưới hoặc trên forum để nhận được câu vấn đáp sớm hơn.Bạn đọc hoàn toàn có thể ủng hộ blog qua "Buy me a cofee" ở góc cạnh trên phía trái của blog.

Xem thêm: Các Đội Hình Trong Đấu Trường Chân Lý Mùa 6: Top 5 Đội Hình Mạnh & Dễ Chơi Nhất

Tôi vừa xong xuôi cuốn ebook "Machine Learning cơ bản", bạn có thể đặt sách trên đây.Cảm ơn bạn.