Optimization và Gradient Descent

Chúng ta đã tìm hiểu về score function và loss function. Giả sử score function có công thức $f(x_{i},W)=Wx_{i}$, và loss function (SVM loss) có công thức: $L_{i}=\sum_{j\neq y_{i}}max(0,s_{j}-s_{y_{i}}+\Delta )$
Mục tiêu của chúng ta là phải làm sao cho giá trị loss càng thấp càng tốt ( tức là dự đoán càng chính xác càng tốt). Trong công thức trên, $x_{i}$ và $y_{i}$ là cố định (đầu vào - đầu ra), và chỉ có W là có thể thay đổi trong mô hình. Vậy để giảm loss thì chỉ có cách đánh vào W mà thôi. Và Optimization chính là thứ giúp ta điều chỉnh được các giá trị của W để làm giảm được giá trị của loss.
 Nói suông là thế, vậy Optimization làm cách nào để điều chỉnh W giúp làm giảm loss? Sau đây là hướng tiếp cận để làm điều đó.  
Đầu tiên: Hướng tiếp cận đơn giản nhất cho Optimization là random.
Ý tưởng cực kì đơn giản. Để biết được tập W nào có loss thấp, thì ta sẽ random các tập W và tính loss dựa trên tập W đó. Sau đó ta sẽ lấy W có kết quả loss thấp nhất và dung nó để dự đoán.  
Hướng tiếp cận thứ 2 là random hướng.Ý tưởng cái này cũng đơn giản chả kém. Tưởng tượng quá trình đi tìm W là bạn đang lầm lũi bước đi trong một cái sân golf rộng lớn và uốn lượn để tìm nơi có vị trí thấp nhất.

Hướng tiếp cận thứ nhất có thể hiểu là bạn được random liên tục các vị trí trong sân golf đó. Nhưng với hướng tiếp cận thứ 2, sau khi bạn được random vị trí đầu tiên, bạn sẽ chọn đó làm vị trí gốc để tiếp tục bước đi chứ không random tiếp nữa.
Giả sử bạn lần đầu bạn được thả rơi ngay trúng sườn đồi cỏ trong sân golf, bước tiếp đến bạn sẽ random một hướng để bước. Nếu bước tiếp theo bạn có vị trí cao hơn bước hiện tại (loss cao hơn) thì bạn sẽ bỏ qua và lại random hướng. Còn nếu bước tiếp theo bạn đi có vị trí thấp hơn bước hiện tại (loss thấp hơn) thì bạn sẽ đi. Quá trình này lặp đi lặp lại đến khi nào bạn ưng ý thì thôi.  
Hướng tiếp cận thứ 3 là dựa vào độ dốc
Ý tưởng hướng tiếp cận này là chúng ta dựa vào độ dốc nơi chúng ta đang đứng, sau đó sẽ đi theo hướng có độ dốc đi xuống. Ý tưởng trực quan thì là thế, nhưng về mặt toán học để hiểu được nó, bạn phải quay về các bài học về đạo hàm. Bài này của trang machinelearningcoban giải thích rất hay và dễ hiểu về đạo hàm trên phương diện toán học. Về cơ bản, chúng ta có thể hiểu trên một cái sân gofl lớn có rất nhiều địa hình nhấp nhô uốn lượn, và do đó có rất nhiều điểm thấp trũng . Những điểm này gọi là local minimum. Trong tất cả những local minimum này, điểm có giá trị thấp nhất gọi là global minimum. Việc tìm W để Loss function có giá trị nhỏ nhất cũng như là việc tìm điểm global minimum này vậy.
Nhưng trong thực tế, rất tiếc phải nói rằng việc này rất khó có thể thực hiện được, do vậy người ta chủ yếu chỉ tìm được local minimum mà người ta ưng ý thôi.
Quay lại với toán học, với hàm f(t), tại một điểm ti bất kì, nếu ta đi theo hướng ngược với hướng của đạo hàm f'(ti) thì sẽ đạt được vị trí có giá trị thấp hơn f(ti). Đây cũng chính là cách mà người ta áp dụng vào việc tìm W cho loss nhỏ.

Gradient Descent

Gradient là dốc, descent là đi xuống. Gradient descent là đi xuống dốc, tức là đi ngược với dấu đạo hàm. Giả sử ta đang ở vị trí W, và ở bước tiếp theo ta bước đi với khoảng cách $\alpha$, ta bước theo hướng ngược đạo hàm của f(w) thì ta có vị trí đứng tiếp theo là:

$W_{t+1} = W_{t}-\alpha f'(W_{t})$

Đây là công thức gradient descent , và được lặp rất nhiều trong quá trình học của máy học.

Phân loại Gradient Descent

Dựa vào số lượng của đầu vào cho mỗi lần lặp, người ta chia gradient descent làm 3 loại:  
Batch Gradient Descent (BGD)Với BGD, thì ở mỗi lần lặp, người ta sẽ sử dụng toàn bộ tập dataset để làm input cho mô hình. Có thể các bạn sẽ thắc mắc rằng, tại sao không thấy bất kì biến nào biểu thị cho dataset input trong công thức gradient descent. Nhưng thực ra, f’(Wt) thực chất là đạo hàm của score function: $f(x_{i},W)=Wx_{i}$. Và x ở đây chính là đầu vào của dataset. Như vậy, bạn có thể hiểu BGD tức là khi x = toàn bộ training set. Nhược điểm của phương pháp này là nó sẽ làm cho quá trình tính toán rất lâu và tốn tài nguyên.
 Stochastic Gradient Descent (SGD)Ở loại này, thì mỗi lần lặp, người ta chỉ sử dụng 1 đầu vào X duy nhất. Để dễ hiểu, giả sử bạn có 1 tập dữ liệu training set với 100 tấm hình, BGD là bạn sử dụng 100 tấm đó cho mỗi lần lặp. Còn SGD là bạn chỉ sử dụng 1 tấm cho mỗi 1 lần lặp.
Mini-batch gradient descentPhương pháp này thì mỗi lần lặp, bạn sẽ chọn ra ngẫu nhiên 1 tập gồm n phần tử từ tập training set. N sẽ lớn hơn 1 và nhỏ hơn tổng số phần tử của training set. Ví dụ bạn có 100 tấm hình trong training set, n có thể là 5, 10 hay 20. Nếu n = 1 thì sẽ là SGD, còn nếu n = 100 thì sẽ là BDG.