Gradient Descent

Dulu saat di Matematika SMA, diajarkan bahwa untuk mencari nilai maksimum atau nilai minimum dari sebuah fungsi f(x), dicari x yang membuat turunan pertama f'(x) = 0. Jika turunan kedua f''(x) < 0, kurva cekung ke bawah. Artinya titik (x, f(x)) adalah titik maksimum. Jika f''(x) > 0, kurva cekung ke atas dan titik (x, f(x)) adalah titik minimum. 

Dalam kasus itu, x adalah anggota himpunan bilangan Real, sehingga dimensinya adalah 1. 

Sementara itu, Gradient Descent, atau juga bisa disebut Steepest Descent, digunakan untuk mencari nilai minimum dari sebuah fungsi multi-variabel F : Rn -> R. Artinya dimensi input untuk fungsi F(x) adalah suatu vektor x. Output dari fungsi f adalah bilangan real y. Jika yang dicari adalah nilai maksimum fungsi, maka namanya Gradient Ascent. Yah, descent dalam bahasa Inggris berarti "turun" sedangkan ascent berarti "naik."

Cara kerja Gradient Descent adalah 

1. Memberi tebakan awal θ. 
2. Tentukan nilai α sehingga φ(α) = F(θ - α ▽F(θ)) minimal (α juga bisa dianggap sebagai learning rate)
3. Lanjutkan perhitungan θ' = θ - αk ▽F(θ)
4. Periksa jika θ sudah memenuhi ambang batas, berhenti. Jika tidak, lanjutkan θ = θ' ke langkah 3.

Contoh:

Misalkan diberikan fungsi berikut

F(x, y) = 4x^2 - 4xy + 2y^2

Diperoleh ▽F(x, y) = (8x - 4y,  4y - 4x)
karena dF(x)/dx = 8x - 4y dan dF(y)/dy = 4y - 4x

1. Misalkan, pilih tebakan awal x = (2, 3)
2. Maka ▽F(x0, y0) = (8*2 - 4*3, 4*3 - 4*2) = (4, 4) 
3. Dicari nilai α sehingga φ(α) = F(θ - α ▽F(θ)) minimal

φ(α) = F((2,3) - α▽F(2, 3)) = F((2,3) - α(4,4))

                                                = F(2 - 4α, 3 - 4α)

                                                = 4(2 - 4α)^2 - 4(2 - 4α)(3 - 4α) + 2*(3 - 4α)^2

                                                = 4(16α^2 - 16α + 4) - 4(16α^2 - 20α + 6) + 2(16α^2 - 24α + 9)
                                                = 64α^2 - 64α + 16 - 64α^2 + 80α - 24 + 32α^2 - 48α + 18
                                                = 32α^2 - 32α + 10

Jadi φ(α) = 32α^2 - 32α + 10

Untuk mencari α minimal, cari turunan pertama φ'(α)

φ'(α) = 64α - 32 = 0

64α = 32

α = 1/2

Maka diperoleh

θ' = θ - 1/2 ▽F(θ) 

= (2, 3) - 1/2 (4, 4) = (2 - 2, 3 - 2) 

θ = (0, 1)

Lanjutkan iterasi sampai mencapai ambang batas yang diinginkan. 

Matriks Jacobian

Pada contoh di atas, fungsi f adalah fungsi yang memetakan vektor berdimensi N ke bilangan Real. Bagaimana jika fungsi f memetakan vektor berdimensi N ke vektor berdimensi-M?

Misalkan f : Rn -> Rm, maka matriks Jacobian  m* n sebagai berikut:

Referensi:
[1] http://www.math.usm.edu/lambers/mat419/lecture10.pdf
[2] https://www.analyticsvidhya.com/blog/2017/03/introduction-to-gradient-descent-algorithm-along-its-variants/
[3] http://www.atmos.washington.edu/~dennis/MatrixCalculus.pdf