梯度下降(gradient descent)是一個求取區域最小值(local minimum)的演算法，因此也是機器學習的基本技巧之一。本篇的目標，是介紹梯度下降的基本概念與實作，以讓你對機器學習中的數學方法有簡單的認識。
Gradient descent is an algorithm for finding a local minimum. So it's one of the basic tricks in machine learning. The goal of this chapter is to walk you through the basic idea and implementation of gradient descent, so you can get a simple feel for the math behind machine learning.
梯度的意思是函數對各個變數偏微分所組成的向量，會指向讓函數值上升最快的方向，可以表示函數在不同變數上的變化率；而利用梯度下降法求極值（以最小值為例，下同），則相當於往梯度的反方向走，亦可以想像成從山坡上慢慢一步一步地走到谷底。對於每一步來說，我們需要知道目前梯度的反方向，以及決定這一步該走多長，通常以梯度的倍率表示，稱為學習率(learning rate)，寫成算式則為如下：
The gradient is a vector made up of the partial derivatives of a function with respect to each variable. It points in the direction where the function's value goes up the fastest, and it tells you how fast the function is changing with respect to each variable. When we use gradient descent to find an extreme value (we'll use minimum as the example from here on), we're basically moving in the opposite direction of the gradient. You can also think of it as slowly walking down a hillside, step by step, until you reach the bottom of the valley. For each step, we need to know the opposite direction of the current gradient, and decide how big the step should be. This is usually written as a multiple of the gradient, called the learning rate. The formula looks like this:
θt+1 = θt - η∇f(θt)
其中的 θt 是目前所在位置的函數參數，η 是學習率，θt+1 是走了新的一步以後的所在位置的函數輸入。通常，在有極值存在的狀況下，由於電腦表示小數的精確度限制等因素，我們可以在走了夠多步，或者兩步之間的輸入（下山時的水平方向）或輸出（下山時的高度方向）位置變化不大的情況下，將計算出的結果當作極值。
Here, θt is the function's parameter at the current position, η is the learning rate, and θt+1 is the function's input after taking a new step. Usually, when an extreme value exists, because of limits like how precisely a computer can represent decimals, we can treat the result as the extreme value once we've taken enough steps, or once the change in input (the horizontal direction while going downhill) or output (the height while going downhill) between two steps becomes very small.
我們來看看如何利用上述的方法，來求函數極值。因為多項式的極值求取相對簡單，因此我們以相對比較不容易手算極值的 f(x) = ex + x2 來做示範：
Let's look at how to use the method above to find a function's extreme value. Since finding the extreme value of a polynomial by hand is pretty easy, we'll demonstrate with f(x) = ex + x2, which is harder to solve by hand:
import matplotlib.pyplot as plt import numpy as np def f(x): return np.exp(x) + x ** 2 def df(x): return np.exp(x) + x * 2 x = np.linspace(-4, 4, 1000) y = f(x) plt.plot(x, y) x = -3 lr = 0.1 for i in range(100): x_new = x - lr * df(x) y_new = f(x_new) print(x_new, y_new) plt.plot(x_new, y_new, '.') plt.text(x_new, y_new, f'{i}') x = x_new plt.show()在上述範例中，除非你使用比較先進的函式庫，例如 PyTorch 等，否則函數的微分仍然需要自己計算。此外，你可以試著改變起始點和學習率，看看效果是否有所不同。
In the example above, unless you use a more advanced library like PyTorch, you still need to work out the derivative of the function yourself. Also, try changing the starting point and the learning rate, and see if the results change.
Question: 在上述範例中，如果 learning rate 小到大約 0.0001，或者大到約 0.8，則各別會發生什麼事？
Question: In the example above, what would happen if the learning rate were as small as about 0.0001, or as large as about 0.8?
多變數的狀況也非常類似，但你需要對兩個變數分別作偏微分。以下用 f(x, y) = ex+y + x2 - y2 來做示範：
The case with multiple variables works in a very similar way, but you need to take the partial derivative with respect to each variable separately. Here's a demo using f(x, y) = ex+y + x2 - y2:
import matplotlib.pyplot as plt import numpy as np def f(x, y): return np.exp(x+y) + x ** 2 - y ** 2 def dfx(x, y): return np.exp(x+y) + x * 2 def dfy(x, y): return np.exp(x+y) - y * 2 x = np.linspace(-3, 3, 100) y = np.linspace(-3, 3, 100) z = np.array([[f(c, r) for c in x] for r in y]) print(z.shape) plt.contour(x, y, z, levels=100) plt.colorbar() x = 3 y = 3 lr = 0.001 for i in range(1000): x_new = x - lr * dfx(x, y) y_new = y - lr * dfy(x, y) if i % 50 == 0: plt.plot(x_new, y_new, 'x') plt.text(x_new, y_new, f'{i+1}') x = x_new y = y_new plt.show()在上述範例中，由於初始位置的梯度非常大，在一步跨太遠的情況下，很容易造成結果發散，因此我們透過降低學習率的方式，來讓每一步不要跨太遠，使得結果可以呈現收斂。
In the example above, since the gradient is very large at the starting position, taking one step that's too big can easily make the result diverge. So we lower the learning rate to keep each step from being too big, which lets the result converge.
在比較實際的問題中，起始點的選擇可能是很有影響的。下列是一個四次式的範例，各位可以看到，我們選的起始點，並不會讓結果走到全域的最小值：
In more realistic problems, the choice of starting point can matter a lot. Below is an example with a degree-4 polynomial. As you can see, the starting point we picked doesn't let the result reach the global minimum:
import matplotlib.pyplot as plt import numpy as np def f(x): return x ** 4 - 5 * x ** 2 + 2 * x + 10 def df(x): return 4 * x ** 3 - 10 * x + 2 x = np.linspace(-2.5, 2.5, 500) y = f(x) plt.plot(x, y) x = 2 lr = 0.01 for i in range(100): x_new = x - lr * df(x) y_new = f(x_new) print(x_new, y_new) plt.plot(x_new, y_new, '.') plt.text(x_new, y_new, f'{i}') x = x_new plt.show()這時，透過 learning rate scheduling 的方式，也許有機會讓你找到比較好的解：
In this case, using learning rate scheduling might give you a chance to find a better solution:
import matplotlib.pyplot as plt import numpy as np def f(x): return x ** 4 - 5 * x ** 2 + 2 * x + 10 def df(x): return 4 * x ** 3 - 10 * x + 2 def train(start_x, lr_type='fixed', base_lr=0.15, epochs=30): x = start_x path = [x] lr = base_lr for epoch in range(1, epochs + 1): # Step Decay if lr_type == 'scheduling': if epoch % 10 == 0: lr = lr * 0.5 grad = df(x) x = x - lr * grad path.append(x) path = np.array(path) return path, f(path) start_pos = 2.1 x_fixed, y_fixed = train(start_pos, lr_type='fixed', base_lr=0.15) x_sched, y_sched = train(start_pos, lr_type='scheduling', base_lr=0.15) x_range = np.linspace(-2.5, 2.5, 100) plt.plot(x_range, f(x_range), 'k--', alpha=0.3) plt.plot(x_fixed, y_fixed, 'ro-', label='Fixed LR (0.15)', alpha=0.3) plt.plot(x_sched, y_sched, 'go-', label='Step Decay LR', alpha=0.3) for i in range(11): plt.text(x_fixed[i], y_fixed[i], str(i)) plt.text(x_sched[i], y_sched[i], str(i)) plt.title("Fixed Learning Rate vs. Learning Rate Scheduling") plt.xlabel("x") plt.ylabel("y") plt.legend() plt.show()機器學習中，我們會希望模型的輸出與標準答案的誤差盡可能的小，也就是對某個可以評估誤差的函數(loss function)求取極值。該函數的輸入分成兩部分，一部分是模型的輸出，另一部分是標準答案，而我們能變更的只有模型如何輸出，因此在計算梯度時，只會對模型輸出相關的那一部分作偏微分。舉例來說，假設你看到二維平面上有一堆點，它們的位置分布長的像是下面的 function，只是你不知道實際參數的話：
In machine learning, we want the error between the model's output and the correct answer to be as small as possible. In other words, we want to find the extreme value of a function that measures this error, called the loss function. The input to this function has two parts: one is the model's output, and the other is the correct answer. The only thing we can change is how the model produces its output, so when we calculate the gradient, we only take the partial derivative with respect to the part related to the model's output. For example, suppose you see a bunch of points on a 2D plane, and their positions look like they follow the function below, except you don't know the actual parameter values:
ŷ = f(x) = e-θ1x + θ2x + θ3
而若以 y 軸方向上的差異的平方當作 loss function，則模型輸出 ŷ 與標準答案 y 之間的差異，可以寫成：
And if we use the squared difference along the y-axis as the loss function, then the difference between the model's output ŷ and the correct answer y can be written as:
ℒ(ŷ, y) = (ŷ - y)2 = (e-θ1x + θ2x + θ3 - y)2
上列算式對 θ1、θ2、θ3 的偏微分分別是：
The partial derivatives of the expression above with respect to θ1, θ2, and θ3 are:
∂ℒ(ŷ, y) / ∂θ1 = 2(ŷ - y) ∂ŷ / ∂θ1 = 2(ŷ - y)e-θ1x(-x)，
∂ℒ(ŷ, y) / ∂θ2 = 2(ŷ - y) ∂ŷ / ∂θ2 = 2(ŷ - y)x，以及
∂ℒ(ŷ, y) / ∂θ3 = 2(ŷ - y) ∂ŷ / ∂θ3 = 2(ŷ - y)
以下範例會亂數產生一堆分布像是 ŷ = f(x) = e-θ1x + θ2x + θ3 的點，並在假設不知道原本 function 參數的情況下，用梯度下降法試圖推測出參數：
The example below randomly generates a bunch of points that follow a distribution like ŷ = f(x) = e-θ1x + θ2x + θ3, and then, pretending we don't know the original function's parameters, tries to figure them out using gradient descent:
import matplotlib.pyplot as plt import numpy as np def func(x, a, b, c): return np.exp((-a) * x) + b * x + c def loss(y_hat, y): return np.mean((y_hat - y) ** 2) def d_loss_a(x, y_hat, y, a, b, c): return np.mean(2 * (y_hat - y) * np.exp((-a)*x) * (-x)) def d_loss_b(x, y_hat, y, a, b, c): return np.mean(2 * (y_hat - y)* x) def d_loss_c(x, y_hat, y, a, b, c): return np.mean(2 * (y_hat - y)) points = [] for _ in range(100): x = np.random.rand(1) * 6 - 3 y = func(x, 1.2, 3.4, 5.6) + np.random.randn(1) * 0.01 points.append([x, y]) points = np.array(points) plt.plot(points[:, 0], points[:, 1], '.', label='Data') a = 1 b = 2 c = 3 lr = 0.001 for i in range(500): x = points[:, 0] y = points[:, 1] y_hat = func(x, a, b, c) a_new = a - lr * d_loss_a(x, y_hat, y, a, b, c) b_new = b - lr * d_loss_b(x, y_hat, y, a, b, c) c_new = c - lr * d_loss_c(x, y_hat, y, a, b, c) a = a_new b = b_new c = c_new print(a, b, c) x = np.linspace(-3, 3, 1000) y = func(x, a, b, c) plt.plot(x, y, label='Pred') plt.show()在上述範例中，我們選擇了離實際位置相當近的點做為起始。你可以試著使用其他起始位置，但是有可能會讓計算結果跟實際位置相差比較大。此外，在範例中是看過所有資料以後再計算梯度，但實務上若遇到資料集非常龐大時，你也可以每次只取一小部分計算梯度，稱為 mini-batch gradient descent，實作範例如下：
In the example above, we chose a starting point that's quite close to the actual values. You can try using a different starting point, but the result might end up pretty far from the actual values. Also, in this example, the gradient is calculated after looking at all the data. But in practice, when the dataset is very large, you can also calculate the gradient using just a small chunk of data each time. This is called mini-batch gradient descent. Here's an example implementation:
import matplotlib.pyplot as plt import numpy as np def func(x, a, b, c): return np.exp((-a) * x) + b * x + c def loss(y_hat, y): return np.mean((y_hat - y) ** 2) def d_loss_a(x, y_hat, y, a, b, c): return np.mean(2 * (y_hat - y) * np.exp((-a)*x) * (-x)) def d_loss_b(x, y_hat, y, a, b, c): return np.mean(2 * (y_hat - y)* x) def d_loss_c(x, y_hat, y, a, b, c): return np.mean(2 * (y_hat - y)) points = [] for _ in range(100): x = np.random.rand(1) * 6 - 3 y = func(x, 1.2, 3.4, 5.6) + np.random.randn(1) * 0.01 points.append([x, y]) points = np.array(points) plt.plot(points[:, 0], points[:, 1], '.', label='Data') a = 1 b = 3 c = 5 lr = 0.001 for i in range(500): batch_size = 10 for j in range(0, points.shape[0], batch_size): x = points[j:j+batch_size, 0] y = points[j:j+batch_size, 1] y_hat = func(x, a, b, c) a_new = a - lr * d_loss_a(x, y_hat, y, a, b, c) b_new = b - lr * d_loss_b(x, y_hat, y, a, b, c) c_new = c - lr * d_loss_c(x, y_hat, y, a, b, c) a = a_new b = b_new c = c_new print(a, b, c) x = np.linspace(-3, 3, 1000) y = func(x, a, b, c) plt.plot(x, y, label='Pred') plt.show()Mini-batch 的技巧，在訓練類神經網路時會經常被使用，並且通常會將資料點隨機打亂順序，以提升梯度下降時的多樣性。
The mini-batch trick is used a lot when training neural networks, and the data points are usually shuffled randomly too, to add more variety during gradient descent.
梯度下降的改進方法之一是 Momentum，亦即在梯度中加入慣性，就像一顆球在地形上滾動，當坡度方向一致時會加速前進；當坡度改變時，不會立刻停下，而是逐漸調整方向；它的好處是有機會學習的更快，在實務上也較不容易卡在平坦或淺的局部極小值附近；它的公式是：
One way to improve gradient descent is called Momentum. This means adding some inertia to the gradient, kind of like a ball rolling across terrain. When the slope direction stays the same, the ball speeds up. When the slope changes, the ball doesn't stop right away, but gradually changes direction instead. The benefit is that it can help you learn faster, and in practice it's also less likely to get stuck near a flat or shallow local minimum. Here's the formula:
Vt+1 = βVt - η∇f(θt)，以及
θt+1 = θt + Vt+1
我們回到一開始的 f(x) = ex + x2，來做 Momentum 的實作示範：
Let's go back to our earlier function, f(x) = ex + x2, and demonstrate how Momentum works:
import matplotlib.pyplot as plt import numpy as np def f(x): return np.exp(x) + x ** 2 def df(x): return np.exp(x) + x * 2 x = np.linspace(-4, 4, 1000) y = f(x) plt.plot(x, y) x = -3 lr = 0.1 v = 0 beta = 0.9 for i in range(100): v = beta * v - lr * df(x) x_new = x + v y_new = f(x_new) print(x_new, y_new) plt.plot(x_new, y_new, '.') plt.text(x_new, y_new, f'{i}') x = x_new plt.show()梯度下降的其他改進方法，還有 AdaGrad 以及 ADAM 等，若有興趣可以自行研讀。
Other ways to improve gradient descent include AdaGrad and ADAM. Feel free to look into these on your own if you're interested.