Memahami diferensiasi otomatis (Automatic Differentiation) dalam 30 baris Python

 (vmartin.fr)
3 poin oleh GN⁺ 2023-08-27 | 1 komentar | Bagikan ke WhatsApp
  • Diferensiasi otomatis, inti dari pelatihan jaringan saraf, diimplementasikan langsung dengan kelas Tensor untuk skalar guna menunjukkan bagaimana perhitungan nilai dan perhitungan turunan terhubung di atas graf komputasi yang sama
  • Dengan variabel Python biasa, hanya nilai hasil z = x + y yang tersisa dan hubungannya hilang, sehingga Tensor harus menyimpan nilai sekaligus riwayat operasi
  • Dengan Children(a, b, op) dan pemanggilan rekursif forward(), dibuat graf komputasi berbentuk pohon biner, dan melalui redefinisi penjumlahan serta perkalian, ekspresi bisa dihitung ulang meski nilai baru dimasukkan belakangan
  • grad(deriv_to) menetapkan turunan terhadap dirinya sendiri sebagai 1 dan terhadap skalar lain sebagai 0, lalu menerapkan aturan turunan operasi dasar secara rekursif untuk membuat graf komputasi baru
  • Implementasi ini hanya menangani skalar dan bisa lambat, sehingga operasi array, pemangkasan cabang perkalian dengan 0, penanganan node konstanta, dan cache untuk mengurangi perhitungan berulang masih menjadi area perbaikan

Hubungan hilang pada variabel Python biasa

  • Jika menghitung seperti x = 3, y = 5, z = x + y, maka di z hanya tersisa nilai hasil 8
  • Setelah itu, meski nilai x atau y berubah, z tidak bisa melacak dibuat dari variabel mana
  • Karena hubungan antarvariabel tidak tersimpan, sulit menghitung turunan terhadap variabel tertentu secara otomatis

Menyimpan riwayat operasi dengan Tensor

  • Tipe baru Tensor menyimpan nilai (value) dan mendefinisikan ulang operator agar perhitungan antar-Tensor mengembalikan Tensor baru
  • Implementasi awal hanya mendefinisikan ulang __add__, sehingga Tensor(3) + Tensor(5) dapat menghasilkan T:8
  • Pada tahap ini, z masih belum bisa mempertahankan riwayat operasi bahwa ia adalah hasil dari x + y

Graf komputasi dan forward()

  • Untuk mempertahankan riwayat operasi, diperkenalkan Children = namedtuple('Children', ['a', 'b', 'op'])
    • a: tensor masukan kiri
    • b: tensor masukan kanan
    • op: operasi sebenarnya seperti np.add, np.multiply
  • Setiap Tensor tidak hanya bisa memiliki nilai numerik, tetapi juga children, sehingga membentuk graf komputasi berbentuk pohon biner
  • forward() mengunjungi node anak secara rekursif untuk menghitung nilai sebenarnya
    • Pada x = Tensor(3), y = Tensor(5), jika z1 = x + y, z2 = z1 * y, hasilnya menjadi T:40
    • Bahkan jika graf dibuat lebih dulu dengan x = Tensor(None), y = Tensor(None), lalu x.value = 3, y.value = 5 diisi belakangan dan z2.forward() dipanggil, tetap akan dihitung T:40

Membuat diferensiasi otomatis sebagai graf komputasi

  • Diferensiasi otomatis diimplementasikan dengan menambahkan aturan turunan untuk setiap operasi dasar yang didukung Tensor
  • grad(self, deriv_to) menelusuri graf komputasi secara rekursif dan menguraikan fungsi kompleks menjadi gabungan fungsi-fungsi sederhana
  • Aturan dasarnya sebagai berikut
    • Mendiferensialkan tensor terhadap dirinya sendiri menghasilkan Tensor(1)
    • Mendiferensialkan skalar tanpa anak terhadap tensor lain menghasilkan Tensor(0)
    • Penjumlahan: (a + b)' = a' + b'
    • Perkalian: (ab)' = a'b + ab'
  • Jika z2 = (x + y) * y didiferensialkan terhadap y, maka hasil g bukan sekadar nilai, melainkan graf komputasi baru yang merepresentasikan turunan parsial
    • Dalam bentuk persamaan, g = ∂z2/∂y = x + 2*y
    • Saat x = 3, y = 5, nilai g adalah 13

Diperluas hingga pengurangan, pembagian, dan fungsi eksponensial

  • Untuk menangani ekspresi yang lebih kompleks, Tensor ditambah dengan operasi pengurangan, pembagian, fungsi eksponensial, dan negasi
  • grad() juga memuat aturan turunan untuk masing-masing operasi
    • Pengurangan: (a - b)' = a' - b'
    • Pembagian: (a/b)' = (a'b - ab') / b²
    • Fungsi eksponensial: exp(a)' = a' * exp(a)
  • forward() juga diubah agar dapat menangani operasi yang hanya memerlukan satu suku
    • Contoh: exp(a) tidak memerlukan suku kedua b
    • -x diproses dalam bentuk 0 - x

Contoh persamaan dan verifikasi dengan Sympy

  • Persamaan berikut ditulis dengan Tensor lalu dihitung turunan parsialnya terhadap x dan y
z = (12 - (x * e^y)) / (45 + x * y * e^-x)
  • Di dalam kode, ekspresi tersebut ditulis seperti berikut
x = Tensor(3)
y = Tensor(5)
z = (Tensor(12) - (x * y.exp())) / (Tensor(45) + x * y * (-x).exp())
  • Nilai turunan parsial yang dihitung adalah sebagai berikut
    • z.grad(x) → T:-3.34729777301069
    • z.grad(y) → T:-9.70176956641438
  • Hasil perhitungan yang sama dengan diff() dan evalf() dari Sympy juga identik
    • Pada xs = 3, ys = 5, nilai turunan terhadap x adalah -3.34729777301069
    • Nilai turunan terhadap y adalah -9.70176956641438

Batasan implementasi sederhana dan titik optimasi

  • Implementasi ini mendekati sistem diferensiasi otomatis paling sederhana, dan sekaligus bisa sangat lambat
  • Kelas saat ini hanya menangani skalar
    • Agar menjadi pustaka yang lebih berguna, perlu ditambahkan operasi array berukuran sebarang
  • Dari graf komputasi, ada beberapa optimasi yang memungkinkan
    • Pada node perkalian, jika salah satu anak bernilai 0, tidak perlu menelusuri lebih dalam
    • Jika suatu node dan anak-anaknya tidak bergantung pada tensor target diferensiasi x, node itu dapat dianggap sebagai konstanta dan penelusuran bisa dihentikan
    • Jika operasi yang sama berulang, cache dapat digunakan agar perhitungan identik tidak dilakukan berkali-kali

Bacaan terkait

1 komentar

 
GN⁺ 2023-08-27
Komentar Hacker News

  • Saya suka demo kode kecil dan elegan seperti ini. Karena ini membantu memahami konsep dengan langsung praktik
    Puzzle GPU dan puzzle tensor dari Sasha Rush juga contoh serupa
    https://github.com/srush/GPU-Puzzles
    https://github.com/srush/Tensor-Puzzles

  • Kalau Anda percaya bahwa hanya dengan ini Anda sudah memahami automatic differentiation sepenuhnya, Anda sedang menipu diri sendiri
    Saat grafnya berupa pohon, semuanya sangat sederhana seperti di artikel ini. Namun jika grafnya adalah directed acyclic graph yang lebih umum, misalnya x = 5; y = 2x; z = xy, implementasinya tetap sangat sederhana, tetapi memahami mengapa implementasi itu benar tidaklah mudah. Kalau Anda berpikir “itu cuma chain rule biasa”, Anda juga sedang menipu diri sendiri
    Salah satu penjelasan awal diberikan oleh Paul Werbos; ia menyebut aturan yang diperlukan sebagai chain rule untuk turunan terurut, dan membuktikannya dengan induksi dari chain rule biasa. Meski begitu, hal itu tidak langsung jelas begitu saja dari chain rule biasa. Jika ada yang meyakini sebaliknya, saya berharap mereka membuktikan bahwa saya salah; saya akan sangat senang kalau begitu

    • Kalau begitu, di mana sebaiknya membaca lebih lanjut? Orang-orang yang membuat framework seperti autograd, PyTorch, dan mxnet pasti mempelajarinya secara mendetail di suatu tempat, dan saya penasaran sumbernya. Setahu saya mxnet berasal dari dunia akademik, mungkin dari CMU
    • Sejujurnya saya tidak begitu paham apa yang diinginkan orang dalam diskusi seperti ini, dan mungkin karena abstraksi yang tersirat, yaitu turunan terurut, tidak ideal
      Jika menerapkan chain rule biasa di sepanjang sisi graf komputasi, yaitu directed acyclic graph, kita mendapatkan nilai yang benar di setiap langkah. Aturan tambahan yang diperlukan kira-kira hanya “jika satu variabel dipakai beberapa kali dalam komputasi, yaitu ada beberapa sisi keluar dari node yang sama atau, dalam arah balik, beberapa sisi masuk, maka gradien yang dihitung masing-masing harus dijumlahkan”; menurut saya ini juga cukup mendasar dan intuitif
      Misalnya jika z dimasukkan ke f(x, y) sebagai x maupun y, maka d/dz f(z, z) = f_x(z, z) + f_y(z, z), dan subskrip berarti turunan parsial. Bagi saya, cara ini secara matematis lebih sederhana daripada mencampur keduanya hingga tampak seperti “sesuatu yang melampaui chain rule”, dan juga terlihat lebih dekat dengan implementasi nyata, terutama apa yang dilakukan PyTorch, yang paling saya kenal
    • Chain rule didefinisikan untuk turunan parsial, jadi secara teknis ini tetap bisa dianggap sekadar chain rule

  • Automatic differentiation terasa seperti sihir
    Banyak ilmuwan komputer terpikat olehnya dan menulis artikel yang memperkenalkan teknik ini dari sudut pandang yang lebih luas. Tulisan saya juga salah satunya, dan mencakup “varian orang miskin” yang memakai bilangan kompleks tanpa operator overloading
    https://pizzaseminar.speicherleck.de/automatic-differentiati...

    • Pada 1994–1995, saat saya melakukan machine learning, saya belum tahu tentang automatic differentiation, dan profesor yang membuat objective function juga mencari turunan analitiknya sendiri. Saya baru mengetahuinya beberapa tahun lalu, dan terkejut saat mengingat waktu yang saya habiskan pada akhir 90-an untuk cukup mempelajari Mathematica demi membuat turunan analitik sendiri
    • Sepertinya ini berawal dari aproksimasi turunan langkah kompleks oleh J. Martins, P. Sturdza, dan J. Alonso pada 2003. Makalah itu layak dibaca
      [0]: https://doi.org/10.1145/838250.838251
    • Benar-benar terasa seperti sihir. Saya ingin tahu apakah ada materi pengantar backpropagation yang ditulis dengan cara serupa

  • Saya punya implementasi automatic differentiation Python 26 baris yang saya buat: https://gist.github.com/sradc/d9d66e3898ffe3a02e0b6b266629b0...

    • Kode pendek memang bagus, tetapi sepertinya otak saya bekerja jauh lebih baik ketika ada spasi kosong yang cukup. Saya perlu berlatih juga dengan gaya-gaya lain seperti ini

  • Ini sangat mirip dengan teknik yang dipakai dalam sistem knowledge-based engineering, dan di sana disebut dependency tracking. Jika digunakan bersama caching node atau tensor, ini dapat mengurangi jumlah komputasi, terutama berguna untuk model 3D parametrik berukuran besar
    Saat mengambil nilai, sistem memanggil pohon biner/dependensi secara rekursif untuk memeriksa variabel mana yang berubah, lalu menghitung ulang hanya yang diperlukan. Dengan objek Python kustom dan atribut yang memiliki metode __set__, __get__, ini bisa dibuat seperti fitur bawaan model berorientasi objek
    x = Tensor(3)
    y = Tensor(5)
    z = x + y
    print(x, y) # 3, 5
    print(z) # 8
    x.value = 4 # saat menetapkan nilai, tidak ada yang dihitung ulang
    print(z) # 9, karena dependensi yang berubah dihitung ulang saat nilainya diambil

  • Ada video menarik dari Andrej Karpathy tentang membuat mesin autograd, dan cukup memberi wawasan
    https://youtu.be/VMj-3S1tku0?si=wuKhELwOwoYbzpt7
    Repositori:
    https://github.com/karpathy/micrograd

  • Varian diferensiasi otomatis yang saya tahu tidak membuat graf operasi. Sebagai gantinya, ia menghitung nilai tersebut secara langsung saat itu juga

    • Mungkin yang dimaksud adalah diferensiasi otomatis mode maju. Ini lebih berguna saat dimensi keluaran fungsi relatif besar, dan berbeda dari diferensiasi otomatis mode mundur yang lebih berguna saat dimensi keluaran relatif kecil
      Keduanya bekerja, tetapi salah satunya bisa lebih efisien tergantung situasinya. Untuk kasus seperti “pelatihan jaringan saraf”, biasanya kita mengoptimalkan satu keluaran loss terhadap banyak target, jadi umumnya memakai mode mundur

  • Saya berharap diferensiasi otomatis cukup disebut aturan rantai numerik, atau setidaknya dijelaskan seperti itu. Secara harfiah memang itu saja, ditambah beberapa trik untuk menghindari perhitungan matriks Jacobian secara eksplisit pada operasi tertentu, sehingga jauh lebih jelas

    • “autodiff” yang dijelaskan di sini dan paling sering dipakai dalam implementasi backpropagation adalah diferensiasi otomatis mode balik, tetapi ada juga mode maju dan strategi-strategi di antara dua ekstrem itu. Pada akhirnya semuanya bermuara pada aturan rantai, tetapi memilih pendekatan di tingkat algoritme sama sekali bukan hal sepele
      Kalau diminta menggunakan aturan rantai untuk mempropagasikan gradien melalui graf komputasi, saya rasa kebanyakan orang secara intuitif akan membayangkan mode maju sebagai default. Saya juga begitu
      https://en.wikipedia.org/wiki/Automatic_differentiation#Beyo...
      Dilihat dari hal ini, istilah tersebut tampaknya berguna untuk menunjuk metode tertentu dalam mengakumulasi gradien sambil menelusuri persamaan yang diberikan oleh aturan rantai
    • Secara teknis itu salah. Aturan rantai numerik menggunakan metode beda hingga, dan galat akan terakumulasi selama komputasi
      Lihat bagian “perbedaan dengan metode lain”: https://en.m.wikipedia.org/wiki/Automatic_differentiation
      Seperti komentar di sekitar sini, intinya adalah implementasinya benar-benar penting dan layak dipelajari. Menyebut diferensiasi otomatis sebagai kumpulan cara untuk mengimplementasikan aturan rantai masih oke, tetapi menyebutnya “sekadar” aturan rantai numerik itu salah
    • Mungkin bisa lebih akurat, tetapi saya tidak akan menyebutnya lebih jelas

  • Diferensiasi otomatis itu hanya lensa Kartesius dari matriks Jacobian dan diferensial total dalam kategori fungsi mulus, jadi apa masalahnya? https://www.youtube.com/watch?v=ne99laPUxN4

  • Saya penasaran mengapa nama kelasnya disebut Tensor. Apakah ada cara untuk memandang ekspresi atau turunannya sebagai tensor? Atau karena skalar juga tensor, dan ini bisa diperluas untuk mendukung tipe tensor lain?

    • Bisa saja saya salah, tetapi secara matematis saya kira objek 2D disebut matriks, sedangkan objek 3D ke atas disebut tensor
      Karena algoritme diferensiasi otomatis yang dijelaskan bekerja untuk objek berdimensi tinggi sembarang, menyebut objek semacam ini tensor tampaknya masuk akal