À, hiểu rồi. Vậy là bạn đã biết về Linear Regression rồi nhỉ. Chắc là bạn đã khá vất vả với việc giải phương trình đạo hàm, nên muốn tìm một cách tiếp cận khác — dễ thở hơn — để tìm cực trị của hàm số.

Và bạn tới đây để tìm hiểu về Gradient Descent phải không? Bạn đã đến đúng chỗ rồi đấy.

Nhảy thẳng vào luôn à? Có vẻ bạn đang hơi vội — hoặc tự tin hơn mức cần thiết. Thông thường người ta chỉ đến đây sau khi đã làm quen với bài toán Linear Regression, và rồi tìm tới Gradient Descent để giải quyết việc tìm cực trị hàm số.

Dù sao, nếu bạn vẫn muốn ở lại, thì có lẽ bạn đã sẵn sàng bắt đầu từ nền tảng. Chúng ta vẫn tiếp tục được — nhưng bạn sẽ phải chú ý hơn từng bước. Gradient Descent mặc dù rất lợi hại nhưng nó yêu cầu một trình độ nhất định để hiểu và ứng dụng được nó.

Dù sao thì tôi cũng rất khuyến khích bạn đến đây, trước khi phải mất công cụ tìm kiếm các bài toán tối ưu chung và trong Machine Learning nói riêng. Thực tế có những bài toán rất khó — hoặc không thể tìm được thí nghiệm, yêu cầu phải giải tỉ mỉ từng dòng công thức một.

Thay vào đó, tại sao lại không thể tìm thấy trải nghiệm chậm hơn , một kết quả gần như tốt nhất mà có thể tiếp cận dễ dàng hơn? Đã có rất nhiều phương pháp để tìm kiếm độ sâu của một phương pháp như phương pháp của Newton , phương pháp cát tuyến tính tính , ... gradient Descent là một trong số những cách tiếp cận gần đây, đặc biệt chú ý đến việc tìm cực trị của hàm số, và phổ biến trong Machine Learning.

Ý tưởng của gradient Descent thật ra khá đơn giản. Hãy thử tưởng tượng bạn thả một quả bóng ở một vị trí nào đó ở trên đồi , quả bóng sẽ từ lăn xuống dốc và dừng lại tại thung lũng — vị trí thấp nhất của đồi. Đường cong của sườn dốc chính là hàm số bạn cần phải tối ưu, vị trí của bóng tối là giá trị hiện tại (điểm \(x\), hoặc \(w\) trong \(f(x)\), \(L(w)\)), và sau một khoảng thời gian, vị trí mới sẽ là điểm sau khi cập nhật chúng đi xuống dốc của hàm. Và tôi nghĩ bạn đã biết ...

Đúng rồi. Đó chính là giá trị đạo hàm của hàm số tại điểm đó.

Gần đúng, chính xác hơn là giá trị đạo hàm của hàm số tại điểm đó.

Hmm... có lẽ caffeine đã làm bạn mất tỉnh táo rồi. Đáp án hiển nhiên là đạo hàm của hàm số tại điểm đó — ngay cả những người mới học Toán cũng biết điều này.

Thật à? Bạn thật sự không biết Toán? Tôi đã gặp nhiều người tự tin thái quá, nhưng ít thấy ai dám thừa nhận như vậy.

Dù sao thì cũng được. Ghi nhớ điều này: đạo hàm = độ dốc. Đơn giản vậy thôi. Nếu bạn không hiểu điều này, tôi nghĩ phần tiếp theo sẽ như nghe như magic vậy.

Khi tôi nói "đi xuống dốc" của hàm số, có nghĩa là chuyển ngược chiều với dấu của đạo hàm . Ví dụ cụ thể với không gian 2D:

• If đạo hàm dương (dốc lên) → chuyển sang trái (giảm x)
• Nếu đạo hàm âm (dốc xuống) → chuyển sang phải (tăng x)

Rất vui, tham số sẽ được cập nhật tăng dần để tiến gần đến điểm cực tiểu mà chúng ta đang tìm kiếm.

Hoạt động dựa trên học tập dựa trên cơ sở chiến thuật này. Cụ thể là...

Đầu tiên, bạn thả bóng xuống — chọn một vị trí bất kỳ trên sườn đồi, gọi nó là \(x_0\). Quả bóng sẽ bắt đầu cuộn lên trên hàm số \(f(x)\), và nhiệm vụ của ta là dẫn nó đi theo hướng \(- f'(x)\), ngược lại theo độ dốc.

Tất nhiên, ta không muốn để bóng lăn quá nhanh và vượt qua thung lũng. Vì thế, ta cần kiểm soát tốc độ từng bước bằng một tham số gọi là learning rate (\(lr\)). Vị trí tiếp theo của bóng, \(x_1\), được tính theo công thức:

Tại \(x_1\) này, quả bóng đã tiến gần hơn đến đáy thung lũng — điểm cực tiểu mà ta đang tìm. Và nếu ta cứ tiếp tục như vậy — tìm \(x_2\), rồi \(x_3\), \(x_4\)... cho đến \(x_t\) — cuối cùng ta sẽ có trải nghiệm tăng dần dần đủ tốt cho bài toán.

Đơn giản thôi. Không cần giải quyết phương pháp phức tạp, chỉ cần tạo bóng để tìm đường xuống.

Nhưng hãy cẩn thận — nếu thiếu thận trọng và chọn \(lr\) quá lớn, một thảm họa sẽ xảy ra. Họ gọi đó là Overshooting. Quả bóng sẽ không lăn xuống nữa, mà nhảy vọt qua thung lũng, nảy lên phía bên kia, rồi lại nảy ngược lại... mãi mãi không bao giờ đến được điểm cực tiểu.

Tưởng tượng một đứa trẻ chơi đu — nếu đẩy quá mạnh, nó sẽ bay vòng qua cả thanh ngang. Learning rate cũng vậy: quá nhỏ thì chậm chạp, quá lớn thì mất kiểm soát.

Vì thế, việc chọn \(lr\) phù hợp chính là nghệ thuật của Gradient Descent.

Bây giờ thì — quay lại với vấn đề của bạn, lí do mà bạn tìm đến đây — Linear Regression. Nhiệm vụ của chúng ta là tìm \(w\) để tối ưu hóa hàm \(L(w)\)

Tôi nghĩ bạn đã biết rằng đạo hàm của \(L(w)\) là gì, nếu bạn chưa biết thì có thể tìm nó ở bài blog trước đó — Linear Regression.

Áp dụng Gradient Descent, công thức cập nhật \(w\) để tối ưu hàm \(L(w)\) là:

Và thế là xong, bài toán Linear Regression đã được giải quyết mà không cần phải giải phương trình phức tạp làm gì cả. Dễ phải không? Tới đây tôi nghĩ bạn đã có thể tự mình áp dụng thuật toán này rồi.

Bây giờ đã tới lúc tôi phải đi... tham quan ở trong Nightreign nên có lẽ đã tới lúc chào tạm biệt, Gradient Descent còn khá nhiều thứ thú vị, nhưng có lẽ để khi khác vậy.

Vậy nhé, chào tạm biệt!

Cũng đúng nhỉ? Thôi được rồi, đây là hộp mô phỏng mà tôi đang làm dở, và một đoạn code mẫu ví dụ mà tôi dùng vào 3 năm trước. Vì môi trường mô phỏng có giới hạn nên tôi chỉ có thể xây dựng cho bài toán Linear Regression 2D, và có hơi xấu một chút... Tôi hi vọng là nó đủ để bạn hiểu.

Đoạn code có một chút dài do phần visualization... (và cũng quá lâu rồi nên tôi cũng lười sửa)

import numpy as np
import matplotlib.pyplot as plt

# Generate data
N = 300
X = (np.arange(N) - N / 2) / N
X = np.vstack((X, np.ones(N)))
gW = np.array([[2], [3]])  # ground-truth weights

Y = X.T @ gW + (np.random.rand(N, 1) - 0.5) * 0.4

# Initialize random weights
w = np.random.rand(2, 1)

# Gradient Descent
lr = 1e-1
losses = []
weights_history = [w.copy()]

for e in range(1000):
    # Calculate loss
    loss = np.mean((X.T @ w - Y)**2)
    losses.append(loss)

    # Calculate gradient
    grad = 1/N * X @ (X.T @ w - Y)

    # Update weights
    w = w - lr * grad
    weights_history.append(w.copy())

    print(f"Epoch {e + 1} - Loss: {loss}")

# Plotting
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 5))
fig.patch.set_facecolor('white')

# Left plot: Data points and fitted line
ax1.scatter(X[0, :], Y, alpha=0.5, s=20, c='#2E86AB', label='Data points')

# Plot initial random line
w_init = weights_history[0]
y_init = X.T @ w_init
ax1.plot(X[0, :], y_init, '--', color='#FF6B6B', linewidth=2,
         label=f'Initial (random)', alpha=0.7)

# Plot final fitted line
y_pred = X.T @ w
ax1.plot(X[0, :], y_pred, '-', color='#06A77D', linewidth=3,
         label=f'Final fit (iter=1000)')

# Plot ground truth line
y_true = X.T @ gW
ax1.plot(X[0, :], y_true, ':', color='#F77F00', linewidth=2.5,
         label='Ground truth', alpha=0.8)

ax1.set_xlabel('x', fontsize=12, fontweight='bold')
ax1.set_ylabel('y', fontsize=12, fontweight='bold')
ax1.set_title('Linear Regression with Gradient Descent',
              fontsize=14, fontweight='bold', pad=15)
ax1.legend(loc='upper left', fontsize=10)
ax1.grid(True, alpha=0.3)

# Right plot: Loss over iterations
ax2.plot(losses, color='#D62828', linewidth=2.5)
ax2.set_xlabel('Iteration', fontsize=12, fontweight='bold')
ax2.set_ylabel('Loss (MSE)', fontsize=12, fontweight='bold')
ax2.set_title('Loss Convergence', fontsize=14, fontweight='bold', pad=15)
ax2.grid(True, alpha=0.3)
ax2.set_yscale('log')  # Log scale to see convergence better

# Add text annotations
final_loss = losses[-1]
ax2.text(len(losses)*0.7, losses[0]*0.5,
         f'Final Loss: {final_loss:.6f}',
         fontsize=11, bbox=dict(boxstyle='round', facecolor='wheat', alpha=0.8))

plt.tight_layout()
plt.show()

# Print results
print(f"Ground truth weights: w0={gW[0,0]:.4f}, w1={gW[1,0]:.4f}")
print(f"Learned weights:      w0={w[0,0]:.4f}, w1={w[1,0]:.4f}")
print(f"Final loss: {final_loss:.6f}")
print(f"Initial loss: {losses[0]:.6f}")
print(f"Loss reduction: {(1 - final_loss/losses[0])*100:.2f}%")

Đó là những gì tôi có,  hi vọng sẽ giúp bạn dễ hình dung về Gradient Descent hơn. Bây giờ thì... trước khi tôi gia nhập hội đi chơi Nightreign thì bạn còn có câu hỏi nào không? Nếu có câu hỏi gì thì hay giữ cho chính mình đi, tôi không còn thời gian nữa. Thay vào đó... hãy lấy giúp tôi cái chìa khóa trên kia giúp tôi được không?

import numpy as np
import random

data = []  # paste it here

# Extract X and y
X = np.array([d["input"] for d in data])   # shape: (N, 2)
y = np.array([d["output"] for d in data])  # shape: (N,)

N = len(X)

# Initialize parameters
W = np.random.uniform(-0.1, 0.1, size=2)  # [w1, w2]
b = 0.0

learning_rate = 0.001
epochs = 2000

for epoch in range(epochs):
    y_hat = X @ W + b
    error = y_hat - y

    loss = np.mean(error ** 2)

    dW = (2 / N) * (X.T @ error)
    db = (2 / N) * np.sum(error)

    W -= learning_rate * dW
    b -= learning_rate * db

    if epoch % 200 == 0:
        print(f"Epoch {epoch}, MSE: {loss:.4f}")

print("\nFinal model:")
print(f"w0: {b:.4f}; w1: {W[0]:.4f}; w2: {W[1]:.4f}")

Turdas, 29th of Sun's Dawn, 21E 024 - Record_Class_ML_03

Thuật toán Gradient Descent hiện tại, hay đúng hơn là Batch Gradient Descent cần phải tính toán dựa trên toàn bộ các điểm dữ liệu. Với những bài toán với bộ dữ liệu lớn, điều này đúng là khá vất vả.

Chính vì vậy, hai biến thể được sinh ra để giải quyết vấn đề này:

• Stochastic Gradient Descent (SGD): Cập nhật dựa trên từng điểm dữ liệu
• Mini-batch Gradient Descent: Cập nhật dựa trên một nhóm nhỏ điểm dữ liệu Cả hai đều nhanh hơn nhiều so với Gradient Descent gốc.

Với SGD, việc cập nhật diễn ra tại từng điểm dữ liệu riêng lẻ, nên chúng ta sẽ cập nhật lại \(w\) dựa trên đạo hàm của từng điểm của hàm mất mát \(L(w, x_i, y_i)\), ở đây hàm \(L(w, x_i, y_i)\) được hiểu là hàm mất mát khi dùng tham số \(w\) với điểm dữ liệu \((x_i, y_i)\).

\(L(w, x_i, y_i)=\frac{1}{2n}(x_{i}^Tw - y_{i})^2\)

\(\frac{\partial L}{\partial w}=\frac{1}{n}x_{i}(x_{i}^Tw - y_{i})\)

Trước đó \(\frac{1}{n}\) được thêm vào để giá trị hàm mất mát không quá lớn, nhưng khi tính trên từng điểm việc này không còn cần thiết, để công thức được đẹp mắt hơn thì sẽ loại bỏ nó đi.

\(L(w, x_i, y_i)=\frac{1}{2}(x_{i}^Tw - y_{i})^2\)

\(\frac{\partial L}{\partial w}=x_{i}(x_{i}^Tw - y_{i})\)

Hoàn hảo, bây giờ cứ mỗi vòng lặp, ta sẽ cập nhật \(w\) \(n\) lần cho \(n\) điểm dữ liệu, với mỗi lần công thức cập nhật là:

\(w_{t}:=w_{t-1}-lr*x_{i}(x_{i}^Tw_{t-1} - y_{i})\)

Bây giờ thử nó một chút xem sao nhỉ?

Tốt rồi, với SGD chúng ta cũng có thể tìm được nghiệm \(w\) mong muốn. Có thể thấy rằng quỹ đạo của nghiệm không được mượt như Gradient Descent thông thường, điều này có thể hiểu là tại vì một điểm dữ liệu không thể nào đại diện cho toàn bộ dữ liệu. Ngoài ra, tôi nghe rằng có tin đồn rằng với SGD, nghiệm có khả năng hội tụ nhanh hơn so với Gradient Descent, có vẻ đây là ưu điểm chính của SGD.

Tin đồn nghe ở đây: Machine Learning cơ bản - Stochastic Gradient Descent

Stochastic Gradient Descent mặc dù hội tụ nhanh và giải quyết được vấn đề với bộ dữ liệu lớn, nhưng nó có một điểm yếu đó chính là việc tính toán theo từng điểm dữ liệu của nó. Khi làm như vậy, SGD không thể tận dụng công nghệ Graphics Processing Unit (hay còn gọi là GPU cho nhanh) để tính toán theo ma trận một cách tối ưu.

Đó là tại sao Batch GD và SGD có một người con đó là Mini-batch Gradient Descent, thay vì cập nhật trên từng điểm dữ liệu, thuật toán sẽ cập nhật trên \(k\) điểm dữ liệu với \(k<n\), \(n\) là số điểm dữ liệu của toàn bộ tập. Việc xây dựng hàm mất mát để tính toán cũng tương tự, thay vì toàn bộ ma trận dữ liệu \(X\) và \(Y\), hàm mất mát sẽ chỉ dựa trên một batch dữ liệu \(X_{i:i+k}\) và \(Y_{i:i+k}\).

\(L(w, i)=\frac{1}{2k}(X_{i:i+k}^Tw - Y_{i:i+k})^2\)

\(L(w, i)\): hàm mất mát với batch bắt đầu từ vị trí \(i\)

Việc đạo hàm và cập nhật giống với khi thực hiện Batch Gradient Descent thông thường, vì \(X_{i:i+k}\) và \(Y_{i:i+k}\) cũng là ma trận giống như \(X\) và \(Y\).

Turdas, 29th of Sun's Dawn, 21E 024 - Record_Class_ML_02

Khi sử dụng Gradient Descent, nếu chú ý kĩ sẽ để ý rằng nghiệm sẽ hội tụ tại điểm cực tiểu, nhưng không phải là điểm cực tiểu tốt nhất. Nếu sử dụng trí tưởng tượng vật lý thì có thể nhận ra rằng — quả banh thiếu đi một lực gì đó.

Quả banh cần có "đà" — Momentum để tiếp tục lao qua dốc và tiếp tục lăn xuống. Hãy thử áp dụng nó vào Gradient Descent xem?

Trong Gradient Descent, hướng di chuyển của nghiệm \(x\) đang là \(- lr*f'(x)\), hãy đặt

\(v_{t}=lr*f'(x_{t})\)

là khoảng mà \(x\) sẽ di chuyển trong lần cập nhật thứ \(t\). Bây giờ công thức đang sẽ là:

\(x_t=x_{t-1}-v_{t}\)

Thay vì như vậy, ta sẽ cho nghiệm \(x\) được đẩy thêm một chút — ví dụ như một phần nhỏ (đặt hằng số là \(\beta\)) của khoảng di chuyển trước thì...

\(v_t=lr*f'(x_t)+\beta*v_{t-1}\)

Với \(v_0=0\)

Công thức cập nhật có vẻ ổn, để thử xem nào.

Ngon, nhưng mà lúc ở gần cực tiểu, nghiệm có vẻ vẫn di chuyển qua lại khá nhiều. Có vẻ là vì do đã có thêm "đà" nên là như vậy. Có một phương pháp có thể giải quyết điều này của Yurii Nesterov — nhìn trước tương lai — mặc dù tôi không biết có thể nhìn thấy được số đề hay không, nhưng cứ thử xem.

Công thức được cập nhật... để thay giá trị đạo hàm, thay vì tính ở điểm \(f'(x_t)\), thì sẽ tính ở điểm \(f'(x_t-\beta*v_{t-1})\)?

\(v_t=lr*f'(x_t-\beta*v_{t-1})+\beta*v_{t-1}\)

Thôi thì cứ thử xem thử...

Nó thực sự hoạt động tốt hơn là chắc chắn! Mặc dù tôi không hiểu lí do tại sao nó lại như vậy nhưng có vẻ như Nesterov sẽ biết số đề nhanh hơn cả tôi.

Có một bài viết để hiểu cách hoạt động ở đây nhưng tôi vẫn chưa đọc thời gian, có lẽ tôi sẽ đọc sau đó. — Động lực của Nesterov

Bạn đã hoàn thành rồi!