Turunan Berantai Untuk Penurunan Otomatis

Satu dari banyaknya bagian terindah dari pustaka-pustaka deep learning seperti pytorch, tensorflow dan lain-lain adalah bagian perhitungan gradient-nya, perhitungan yang digunakan pada saat proses backpropagation. Bagaimana tidak, saya ingat betul ketika di SMA dan kuliah hasil turunannya bergantung pada ekspresi yang diturunkan. Apakah itu variabel, konstanta, atau kombinasi keduanya. Pada saat akhir perkuliahan, tepatnya pada saat mengerjakan skripsi, saya berpikir, rasanya tidak mungkin jika ini dilakukan secara manual, karena untuk setiap ekspresi baru, turunannya harus dihitung ulang secara manual.

Dugaan saya tepat, ternyata bisa dilakukan turunan otomatis dengan menggunakan struktur data dan algoritma yang memanfaatkan aturan matematika yang sudah kita kenal. Kira-kira setelah lulus kuliah saya menemukan artikel dari Kemal Kurniawan, di artikel, ia membuat dengan menggunakan python & saya coba di komputer saya ini juga berhasil.

Pendekatan ini bisa dimulai dengan mendefinisikan apa itu turunan berantai. Yang saya pahami, aturan berantai atau chain rule adalah aturan dalam kalkulus untuk menghitung turunan dari fungsi yang tersusun atas fungsi-fungsi lain. Misalkan kita punya dua fungsi yang saling berantai atau berhubungan:

Yang bisa diartikan dengan

Pertanyaannya, seberapa besar perubahan x mempengaruhi L? Jawabannya adalah:

Persamaan di atas, bisa dibaca sebagai pengaruh \(x\) terhadap \(L\) sama dengan pengaruh \(z\) terhadap \(L\) dikalikan pengaruh \(x\) terhadap \(z\). Kita tidak perlu menghitung \(\frac{dL}{dx}\) secara langsung. Cukup kalikan turunan di setiap langkah.

Sebagai contoh, misalkan \(z=x^2\) dan \(L=3z\):

Dengan metode turunan berantai:

Kita bisa verifikasi: substitusi langsung memberikan \(L=3x^2\), sehingga \(\frac{dL}{dx} = 6x\). Hasilnya sama persis.

Sebelum masuk ke implementasi, di sini saya menggunakan golang (tidak ada alasan khusus di sini), kodenya ada di sini. Keseluruhan pustaka ini hanya terdiri dari satu struct dan tiga konsep utama:

• Value : Satu node dalam graf komputasi. Menyimpan nilai (Data), gradien (Grad), referensi ke node input (children), dan juga fungsi backward-nya sendiri.

type Value struct {
	Data     float64
	Grad     float64
	backward func()
	children []*Value
}

• Forward pass : Setiap operasi seperti Mul, Add, dan yang lain membuat node Value baru dan menyimpan closure backward yang berisi cara menghitung turunannya. Di proses ini, implementasi fungsi backward belum dijalankan, hanya disimpan.

func New(data float64) *Value {
	return &Value{Data: data}
}

func Add(x, y *Value) *Value {
	out := &Value{
		Data:     x.Data + y.Data,
		children: []*Value{x, y},
	}
	out.backward = func() {
		x.Grad += out.Grad
		y.Grad += out.Grad
	}
	return out
}

func Mul(x, y *Value) *Value {
	out := &Value{
		Data:     x.Data * y.Data,
		children: []*Value{x, y},
	}
	out.backward = func() {
		x.Grad += out.Grad * y.Data
		y.Grad += out.Grad * x.Data
	}
	return out
}

// And other method

Ada yang menarik di sini, kenapa += dan bukan =? Karena satu node bisa dipakai lebih dari sekali. Misalkan \(L = x \cdot x\). Node x jadi input di dua jalur sekaligus, jadi gradien dari keduanya harus dijumlahkan. Kalau pakai =, jalur kedua langsung menimpa hasil jalur pertama dan gradiennya salah.

• Backward pass : fungsi Backward() mengurutkan semua node dari output ke input (topological sort), lalu memanggil closure backward tiap node satu per satu. Di sinilah chain rule dijalankan secara berantai.

Urutan ini penting, backward suatu node baru bisa dipanggil kalau semua node di atasnya sudah selesai, karena out.Grad dari atas harus sudah terisi dulu. Kalau urutannya sembarang, bisa saja out.Grad masih nol waktu backward dipanggil, dan gradiennya salah semua. Jadi menggunakan topological sort supaya tiap node pasti diproses setelah semua penerusnya.

// Backward computes gradients for all nodes connected to the root.
//
// Algorithm:
//  1. Topological sort — ensure each node is processed only after all its descendants (so that gradients are fully accumulated when backward is called).
//  2. Set root.Grad = 1.0  (since dL/dL = 1)
//  3. Call backward() on each node, starting from the root down to the leaves.
func (root *Value) Backward() {
	// Collect all nodes in topological order
	topo := make([]*Value, 0)
	visited := make(map[*Value]bool)

	var buildTopo func(v *Value)
	buildTopo = func(v *Value) {
		if visited[v] {
			return
		}
		visited[v] = true
		for _, child := range v.children {
			buildTopo(child)
		}
		// Post-order: add node after all its children
		topo = append(topo, v)
	}
	buildTopo(root)

	// Traverse in reverse topological order (from root toward leaves)
	root.Grad = 1.0
	for i := len(topo) - 1; i >= 0; i-- {
		if topo[i].backward != nil {
			topo[i].backward()
		}
	}
}

Ilustrasinya untuk L = x * w:

x ──┐
    ├──► [Mul] ──► L
w ──┘

Forward:  L.Data = x.Data * w.Data    (kiri ke kanan)
Backward: x.Grad += L.Grad * w.Data  (kanan ke kiri)
          w.Grad += L.Grad * x.Data

// Mul: z = x * y
//
// Derivative:
//   ∂z/∂x = y  ->  dL/dx += dL/dz * y
//   ∂z/∂y = x  ->  dL/dy += dL/dz * x
func Mul(x, y *Value) *Value {
	out := &Value{
		Data:     x.Data * y.Data,
		children: []*Value{x, y},
	}
	out.backward = func() {
		x.Grad += out.Grad * y.Data
		y.Grad += out.Grad * x.Data
	}
	return out
}

Contoh End-to-End

Mari kita buktikan dengan angka agar lebih konkret. Ambil ekspresi sederhana:

dengan nilai \(x = 1.0\), \(w = 0.5\), \(b = 0.1\).

Forward pass menghitung nilai dari kiri ke kanan:

Backward pass menghitung gradien dari kanan ke kiri:

Mulai dari \(L\), kita set \(\frac{dL}{dL} = 1\) sebagai titik awal.

Kemudian turunan berantai diterapkan mundur di setiap node:

Dalam kode:

x := New(1.0)
w := New(0.5)
b := New(0.1)

s := Mul(x, w)
L := Add(s, b)
L.Backward()

fmt.Println(w.Grad) // 1.0
fmt.Println(x.Grad) // 0.5
fmt.Println(b.Grad) // 1.0

Kita bisa verifikasi secara analitik: \(L = x \cdot w + b\), maka:

Hasilnya sama persis.

Verifikasi dengan metode selisih berhingga

Bagaimana kita tahu hasil gradien dari penurunan otomatis ini benar? Salah satu caranya adalah membandingkannya dengan pendekatan numerik yang disebut metode selisih berhigga (finite difference).

Ide dasarnya sederhana, kita tidak perlu rumus turunan sama sekali. Cukup geser nilai \(x\) sedikit ke kanan dan ke kiri, lalu lihat seberapa besar \(f\) berubah.

Formula ini sebenarnya berakar dari definisi limit turunan:

Ini disebut forward difference, yang mengukur perubahan hanya dari satu arah. Kita bisa langsung memakainya, tapi ada yang lebih baik: central difference, yang mengukur dari dua arah sekaligus:

Dari beberapa artikel yang saya baca & juga bertanya ke Claude, ini lebih baik. Karena erornya \(O(h^2)\) dibanding \(O(h)\) pada forward difference. Ini berarti untuk nilai \(h\) yang sama, central difference jauh lebih akurat. Detailnya bagaimana tentu masih harus belajar lagi

Dengan \(h\) yang sangat kecil, dalam kode kita pakai \(h = 0.00001\).

Dalam kode:

func finiteDiff(f func(float64) float64, x float64) float64 {
    h := 1e-5
    return (f(x+h) - f(x-h)) / (2 * h)
}

Sebagai contoh, ambil \(f(x) = x^3 - 2x + 1\) di titik \(x = 3\). Secara analitik \(f'(x) = 3x^2 - 2\), sehingga \(f'(3) = 25\).

Dengan metode selisih berhingga:

Di test kita, kedua cara ini dibandingkan langsung:

func TestGradientCheck(t *testing.T) {
    buildGraph := func(xv float64) (*Value, *Value) {
        x := New(xv)
        x3 := Pow(x, 3)
        cx := Mul(New(2), x)
        L := Add(Sub(x3, cx), New(1))
        return x, L
    }

    fPoly := func(xv float64) float64 {
        return xv*xv*xv - 2*xv + 1
    }

    testPoints := []float64{-2.0, -0.5, 0.0, 1.0, 3.0}
    for _, xv := range testPoints {
        x, L := buildGraph(xv)
        L.Backward()

        numerical := finiteDiff(fPoly, xv)

        // Both must be equal within a tolerance of 1e-4.
        assertClose(t, x.Grad, numerical, tolFD, "...")
    }
}

Kita uji di lima titik berbeda: \(x = -2, -0.5, 0, 1, 3\). Jika autodiff kita benar, hasil x.Grad dari Backward() harus cocok dengan hasil finiteDiff di semua titik.

Sejauh yang saya tahu, ini cara yang sama yang dipakai Pytorch untuk menguji implementasi gradiennya sebelum dirilis.