[Gradient Descent] – Phần 1: “Gradient Descent là gì?”

Hình 1: https://towardsdatascience.com/coding-deep-learning-for-beginners-linear-regression-gradient-descent-fcd5e0fc077d

Đây là bài viết đầu tiên trong series “Gradient Descent Cho Machine Learning” của mình tại MMLab Tutorials. Ở series này, mình sẽ tổng hợp kiến thức từ rất nhiều nguồn (tài liệu trong nước và ngoài nước) sau đó trình bày lại một cách đầy đủ, chi tiết và dễ hiểu nhất. Hy vọng bài viết sẽ hữu ích với các bạn đang tiếp cận lĩnh vực AI (Artificial Intelligence – Trí tuệ nhân tạo) nói chung và Machine Learning (Máy học) nói riêng.

Trong quá trình tìm hiểu về Machine Learning, đối với những ai đã biết về Gradient Descent thì nhiều khi chỉ biết nó dùng để làm gì chứ không thực sự hiểu rõ bản chất của nó, xem nó là cái hộp đen. Còn những ai chưa biết về Gradient Descent thì cái hộp đen này càng đen hơn, đơn giản là xem tutorial thấy chỗ đó người ta gọi hàm gì đó trong thư viện gì đó ra để dùng nên làm theo, đây là trường hợp mà phần lớn những người mới tiếp cận Machine Learning sẽ rơi vào, tức là, thấy hướng dẫn làm thế nào thì làm lại y hệt như vậy. Vô hình trung, họ sẽ chỉ biết đến Gradient Descent như là những cái tên như “adam” và “momentum”,… Điều này dẫn đến trường hợp khi một người bắt đầu giải quyết những bài toán tương tự mà họ đã làm trước đó, dùng chung một kiểu thiết lập cho Gradient Descent nhưng kết quả lại không được như mong muốn và họ lúng túng không biết mình sai chỗ nào.
Vì vậy, ngoài việc biết cách xây dựng thuật toán Machine Learning, một người train có hiệu quả hay không, mô hình có tụ hay không phụ thuộc rất lớn vào việc người đó thiết lập và tinh chỉnh các hyperparameter (siêu tham số) đã hợp lý hay chưa. Tuy nhiên, để mà thiết lập được hyperparameter hợp lý thì phải hiểu rõ bản chất của thuật toán. Đó là lúc mà họ bắt đầu nhận ra mình cần phải tìm hiểu về Gradient Descent một cách nghiêm túc.

Bài viết này sẽ hữu ích với những ai gặp trường hợp tương tự, bên cạnh đó cũng hữu ích với những ai bắt đầu học Machine Learning bởi vì tìm hiểu kĩ ngay từ đầu lúc nào cũng tốt hơn đúng không nào.

Có thể nói các thuật toán tối ưu (Optimizition Algorithm) là một trong những “hạt nhân” mạnh mẽ của hầu hết thuật toán Machine Learning. Trong bài viết này, mình sẽ làm quen với những gì cơ bản nhất của Gradient Descent – một trong những thuật toán Optimizition mà bạn có thể áp dụng với bất kì mô hình Machine Learning, Deep Learning nào.

Mục tiêu của phần 1 mở đầu cho chuỗi bài viết về Gradient Descent bao gồm:
I. Nhắc lại định nghĩa và tính chất của đạo hàm.
II. Hiểu được ý tưởng cơ bản của thuật toán Gradient Descent.

Hãy cùng bắt đầu nào

I. Đạo hàm

1.1. Khái niệm

Trước khi đi vào tìm hiểu Gradient Descent, mình sẽ cùng các bạn nhắc lại những khái niệm và tính chất của đạo hàm. Nếu như nói Gradient Descent là cốt lõi của các thuật toán Machine Learning thì đạo hàm chính là cốt lõi của Gradient Descent. Do đó, đây sẽ là kiến thức được nhắc đến xuyên suốt trong máy học và đặc biệt là trong Gradient Descent.

Phần này mình tham khảo tài liệu trên Wikipedia

Xét một hàm số, đạo hàm của một hàm số sự mô tả độ biến thiên (mức độ thay đổi giá trị) của hàm số đó.
Ký hiệu đạo hàm của hàm số f(x) theo biến x là:

\frac{\partial f(x)}{\partial x}~(hay~\frac{d f(x)}{d x},~gọi ~là~ đạo~ hàm~ của~ f(x) ~theo~ x)

Vừa rồi là đạo hàm của hàm số nói chung, vậy đạo hàm của một hàm số tại một điểm thì sao?
Đạo hàm của một hàm số tại một điểm là sự mô tả độ biến thiên của hàm số tại điểm đó.
Độ biến thiên này có nghĩa là gì? Hãy cùng xem xét định nghĩa bên dưới:

Đạo ~hàm ~của ~hàm ~số ~ y = f(x)~tại~x_0~là~: \newline {\bold{\frac{\partial ~f(x)}{\partial~ x_0}}} = \frac{f\left(x\right)-f\left(x_0\right)}{x-x_0}~khi~x ~tiến~ dần~ đến~ x_0, hay:
\bold{\frac{\partial ~f(x)}{\partial~ x_0}} = \lim_{x\rightarrow x_0}\frac{f\left(x\right)-f\left(x_0\right)}{x-x_0}
= \lim_{\mathrm{\Delta x}\rightarrow0}\frac{f\left(x_0+\mathrm{\Delta x}\right)-f\left(x_0\right)}{\mathrm{\Delta x}}

Nếu như vẫn thấy khô khan thì hình bên dưới sẽ giúp các bạn hiểu ngay

(h~ và ~ \mathrm{\Delta x}\ ~ như ~ nhau)
Hình 2: Cát tuyến của đường cong y = f(x) tại hai điểm (x, f(x)) và (x+h, f(x+h))
Hình 3: Khi h tiến dần về 0 thì cát tuyến sẽ tiến dần đến tiếp tuyến của đồ thị
Hình 4.1: Tiếp tuyến của đồ thị là giới hạn của cát tuyến khi h tiến về 0
Hình 4.2

Có thể thấy những hình minh họa trên mình đều sử dụng các đường cát tuyến và tiếp tuyến đồ thị để biểu diễn đạo hàm. Sở dĩ mình làm điều đó là bởi vì đạo hàm tại một điểm biểu hiện rõ nét nhất trong phương trình tiếp tuyến đi điểm đó. Vậy hãy cùng nhau nhìn nhận vấn đề này một cách sâu sắc hơn.

1.2. Đạo hàm và tiếp tuyến

Ví dụ ta có một hàm số y = f(x) = x2-2x+3 được vẽ trên trục tọa độ như sau:

Hình 5: Đồ thị hàm số y = f(x) = x2-2x+3

Nhẩm nhanh ta có thể tính được phương trình đạo hàm của nó là f'(x)=2x-2.
Như đã nói ở trên, đạo hàm này là sự biểu diễn độ biến thiên của hàm số f(x).
Có phương trình đạo hàm rồi, ta có thể dễ dàng tính được đạo hàm tại mọi điểm (miễn là tại điểm đó hàm số khả vi và liên tục), giả sử ta muốn tìm tiếp tuyến tại điểm x0=2 thì chỉ cần làm như sau:

Đạo hàm của f(x) tại x0= 2:
f'( x0 = 2) = 2 x0 -2 = 2.2 – 2 = 2
Gọi g(x) là phương trình tiếp tuyến tại đó, ta có:
g(x) = f'( x0 )(x- x0) + f(x0)
Với f'( 2) = 2 f( 2 ) = 3
Thay số vào phương trình ta được:
g(x) = 2x -1
Vẽ đồ thị hàm số g(x) = 2x -1:

Hình 6: Tiếp tuyến của đồ thị hàm số y = f(x) = x2-2x+3 tại x0 = 2

Nhìn vào đồ thị hàm số này, chúng ta có thể rút ra được nhận xét rằng đạo hàm tại một điểm chính là độ dốc của phương trình tiếp tuyến đi qua điểm đó hay cũng chính là độ dốc của hàm số tại điểm đó (độ dốc hay còn gọi là hệ số góc) .
Vậy có nhận xét gì về đạo hàm của hàm số khi ta tiến càng gần đến điểm cực tiểu? (hay điểm cực trị nói chung?). Trước khi đọc câu trả lời, các bạn hãy đọc lại câu hỏi và thử suy nghĩ rồi tìm ra đáp án cho chính mình.




Câu trả lời chính là: đạo hàm sẽ tiến về 0, tức độ dốc sẽ giảm dần khi tiến dần đến cực tiểu.

Hình 7: Đạo hàm sẽ tiến dần về 0 khi tiến dần đến cực tiểu và đạt giá trị bằng 0 tại điểm cực tiểu

Fun fact: Trong hàm một biến, đạo hàm này được gọi là derivative. Trong hàm đa biến, ta gọi nó với cái tên gradient.
Như vậy chúng ta đã cùng nhau nhắc lại về đạo hàm, từ bây giờ trở về sau những kiến thức trên sẽ được sử dụng rất nhiều, hãy chắc chắn rằng bạn đã nắm kĩ nó nhé.

II. Gradient Descent – Ý Tưởng

2.1. Đặt vấn đề

Hình 10: Ảnh minh họa
(Nguồn: https://www.metoffice.gov.uk/weather/learn-about/weather/types-of-weather/fog/8-facts )

Giả sử một người đang lạc ở trên đỉnh núi như trên, trời sắp tối và đỉnh núi rất lạnh khi về đêm nên cần phải đi xuống thung lũng để dựng trại, xung quanh toàn là sương mù nên anh ta không thể xác định chính xác thung lũng ở đâu. Làm thế nào để đi xuống thung lũng?
Vì đam mê toán học, trong đầu anh ấy lóe lên ý tưởng rằng sẽ cố gắng xác định đồ thị hàm số biểu diễn bề mặt của dãy núi, không chần chừ, anh ta bắt tay vào thực hiện.
Bằng một cách nào đó anh ấy đã tìm ra được hình dạng của dãy núi như sau:

Hình 11
(Nguồn: https://www.benfrederickson.com/numerical-optimization/ )

Bằng một phép nội suy, anh ta suy ra được phương trình của đồ thị hàm số trên:

f(x) =\frac{\log\left(\left|x\right|^{\left(\sin\left(x\right)+2\right)}+1\right)}{\log\left(10\right)}

Đạo hàm nó:

f'(x)=\frac{\left(\log\left(\sin\left(x\right)+2\right)+1\right)\left(\sin\left(x\right)+2\right)^{\left(\sin\left(x\right)+2\right)}}{\left(\left|x\right|^{\left(\sin\left(x\right)+2\right)}+1\right)\log\left(10\right)}

Giải phương trình đạo hàm bằng 0 và tìm được thung lũng gần đó:

Hình 12

Anh ta nói xạo đó, dễ gì mà tìm được hàm số, nói gì đến tính toán! Trong thực tế không ai làm như vậy cả.

Thực chất anh ta làm theo cách bên dưới:
– Bước 1: Khảo sát vị trí đang đứng và tất cả những vị trí xung quanh có thể nhìn thấy, sau đó xác định vị trí nào hướng xuống dốc nhiều nhất.
– Bước 2: Di chuyển đến vị trí đã xác định ở bước 1.
– Bước 3: Lặp lại hai các bước trên đến khi nào tới được thung lũng.

Hình 13

Hay nói cách khác là đi men theo mặt dốc, đây chính là ý tưởng của thuật toán Gradient Descent.

2.2. Ý tưởng Gradient Descent cơ bản – mã giả

Trong phần này, mình sẽ liên hệ ý tưởng dò đường men theo mặt dốc bên trên với ý tưởng của giải thuật Gradient Descent. Tuy Gradient Descent có rất nhiều cải tiến và biến thể khác nhau, nhưng bản chất vẫn phải thực hiện các bước cơ bản, sau đây là mã giả của thuật toán:

Trước tiên hãy định nghĩa một cách toán học: bài toán chúng ta đang giải quyết là tối ưu hàm số \( n \) biến \( f( x_1, x_2, \dots, x_n ) \), tức là ta phải đi tìm bộ số \( \theta_1, \theta_2, \dots, \theta_n \) sao cho \( f\left(\theta_1, \theta_2, \dots, \theta_n\right) \) đạt giá trị nhỏ nhất.


Bước khởi tạo: Bắt đầu với các hệ số nhỏ, hoặc hệ số ngẫu nhiên, hoặc bằng 0:

\theta_i \gets 0; \;\;\;\;\; \forall i

Quá trình này gọi là thiết lập vị trí ban đầu (starting point – điểm khởi đầu, hay initial weight – hệ số khởi tạo), điều này giống như đưa ta đến một điểm đâu đó trên ngọn núi mà chúng ta không biết.

Bước 1: Tính đạo hàm từng phần của Loss function ở vị trí hiện tại đối với từng biến:

\frac{\partial}{\partial x_i}f\left(\theta_1, \theta_2, \dots, \theta_n\right); \;\;\;\;\; \forall i

Bước này giống như việc người đàn ông xem xét các vị trí xung quanh để chọn ra hướng đi nào hướng xuống dốc.

Bước 2: Cập nhật bộ hệ số mới theo hàm cập nhật sau:

\theta_i \gets \left(\theta_i ~ – ~ {\alpha}\frac{\partial}{\partial x_i}f\left(\theta_1, \theta_2, \dots, \theta_n\right)\right); \;\;\;\;\; \forall i

Điều này tương ứng với việc di chuyển đến điểm hướng xuống dốc đã chọn trước đó.

Bước 3: Lặp lại bước 1 và 2 cho đến khi thỏa điều kiện dừng.

Khi đến cực tiểu cũng là lúc người đàn ông xuống tới thung lũng.
Hình dưới đây sẽ minh họa sự tương đồng giữa hai ý tưởng trên.

Hình 14. So sánh ý tưởng Gradient Descent và ý tưởng dò đường men theo mặt dốc

Như vậy là chúng ta đã bàn luận về ý tưởng cơ bản của thuật toán Gradient Descent, tuy nhiên đến đây vẫn chưa đủ để có thể thiết lập thông số cho thuật toán một cách hợp lý, tất nhiên, bởi vì chúng ta mới chỉ dừng lại ở mặt ý tưởng. Chẳng hạn như nhìn vào mã giả trên, có rất nhiều thứ “gây bối rối”:

  • Thiết lập initial weigh như thế nào và nó ảnh hưởng thế nào đến kết quả?
  • Loss function là gì và ở đâu ra có Loss function để đạo hàm?
  • Tính đạo hàm của Loss function như thế nào?
  • α là gì và tại sao nó lại xuất hiện ở đó?
  • Hàm cập nhật là gì, có ý nghĩa gì?
  • Điều kiện dừng là gì?

Chỉ khi nào giải tích hết được những câu hỏi trên thì mới có thể thiết lập những thông số cơ bản cho Gradient Descent. Ngoài ra, để triển khai trong thực tế dưới góc độ lập trình & toán học thì cần phải tìm hiểu kỹ hơn nữa bản chất của nó, do đó cần phải tự tay xây dựng thuật toán và phân tích thuật toán dưới một góc nhìn chuyên sâu hơn. Nhưng nhìn chung chúng ta đã đi được một bước đi vững chắc trong hành trình chinh phục Gradient Descent.

Tổng kết

Một bài viết thì sẽ không thể giải thích hết tất cả mọi thứ, do đó mình sẽ chia nhỏ kiến thức thành một series để có thể giải thích cặn kẽ nhất cho các bạn, cũng như cách mà mình đã từng giải thích cho chính mình. Trong phần I này, chúng ta đã nhắc lại về đạo hàm, phương trình tiếp tuyến và ý tưởng cơ bản của thuật toán Gradient Descent. Ở phần sau chúng ta sẽ cùng nhau giải đáp những thắc mắc bên trên bằng cách trực tiếp xây dựng thuật toán Gradient Descent “from scratch”.

Tài liệu tham khảo

[1] https://towardsdatascience.com/coding-deep-learning-for-beginners-linear-regression-gradient-descent-fcd5e0fc077d

[2] https://towardsdatascience.com/coding-a-2-layer-neural-network-from-scratch-in-python-4dd022d19fd2

[3] https://hackernoon.com/gradient-descent-aynk-7cbe95a778da?fbclid=IwAR0MYMd_28TYrg7r0mygpqGWE6fDNbFuotO-7O0vVTYrIBh0UHb-N3e-Kds

[4] https://vi.wikipedia.org/wiki/%C4%90%E1%BA%A1o_h%C3%A0m

[5] https://machinelearningcoban.com/2017/01/12/gradientdescent/

[6] https://machinelearningcoban.com/2017/01/16/gradientdescent2/

[7] https://machinelearningmastery.com/gradient-descent-for-machine-learning/?fbclid=IwAR303lja8Efw09Zld7dzL6AfT7IeciI23OCefwnwJ6w5CZvbiHyQwagjNvE


[8] https://dominhhai.github.io/vi/2017/12/ml-gd/

[9] https://medium.com/@vicohub/thu%E1%BA%ADt-to%C3%A1n-t%E1%BB%91i-%C6%B0u-gradient-descent-21a0a397928

[10] https://www.benfrederickson.com/numerical-optimization/

Tác giả:
Nguyễn Văn Khoa – CNCL2018.1

6 thoughts on “[Gradient Descent] – Phần 1: “Gradient Descent là gì?”

  1. Bài viết rất hay, cảm ơn anh đã chia sẽ. Em có góp ý là chữ bài viết hơi nhỏ (+ sẵn nhiều chữ) nên nhìn khá ngán với những bạn mới tiếp xúc với những khái niệm trên, mong anh có thể căn chỉnh bài viết cho phù hợp cỡ chữ (khi đọc em phải x1.25 kích cỡ)

    1. Admin trang web đã tiếp nhận góp ý và sẽ cân nhắc để điều chỉnh font chữ cho thân thiện với người đọc hơn. Chân thành cảm ơn góp ý của bạn!

  2. Huhu bài viết đỉnh quá huhu, chưa chắc giảng viên đã trình bày dễ hiểu như này nha =))
    Chắc bài viết được đầu tư nhiều lắm nè, nhìn danh sách tham khảo thấy xịn rồi. Cảm ơn các bạn nhiều lắm luôn nè. Hãy tiếp tục nhé các bạn.
    Với mình đề nghị web các bạn có thêm chức năng cho phép người xem điền email để nhận bài viết mới qua mail. Mình ít lên fb và cũng ko có nhớ lên web thường xuyên đâu, nên là nếu có chức năng đó thì sẽ rất tiện ạ.

    1. Chào bạn! Admin trang web đã tiếp nhận góp ý và sẽ tìm hiểu cách để thêm chức năng đó, vì thú thực là đội ngũ của tụi mình cũng không rành những phần này ạ :)))

    1. Chào bạn! Phần 2 của chuỗi bài viết hiện đang trong quá trình hoàn thiện. Nhằm đảm bảo chất lượng tốt nhất có thể nên mỗi bài viết sẽ mất nhiều thời gian để có thể xuất bản, mong bạn thông cảm cho tác giả nhé!

Leave a Reply to ADMIN Cancel reply

Your email address will not be published. Required fields are marked *