ทำความเข้าใจ Automatic Differentiation ด้วย Python 30 บรรทัด

 (vmartin.fr)
3 คะแนน โดย GN⁺ 2023-08-27 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • สาธิตการทำงานของ automatic differentiation ซึ่งเป็นหัวใจของการฝึกโครงข่ายประสาทเทียม ด้วยการลงมือสร้างคลาส Tensor สำหรับสเกลาร์ขึ้นมาเอง เพื่อให้เห็นว่าการคำนวณค่าและการคำนวณอนุพันธ์เชื่อมต่อกันอย่างไรบนกราฟการคำนวณเดียวกัน
  • หากใช้ตัวแปร Python ทั่วไป จะเหลือเพียงค่าผลลัพธ์ของ z = x + y และความสัมพันธ์จะหายไป ดังนั้น Tensor จึงต้องเก็บทั้งค่าและประวัติการดำเนินการไว้ด้วยกัน
  • ใช้ Children(a, b, op) และการเรียก forward() แบบ recursive เพื่อสร้างกราฟการคำนวณแบบต้นไม้ทวิภาค และด้วยการ override การบวกและการคูณ ทำให้สามารถคำนวณนิพจน์ใหม่ได้แม้จะใส่ค่าภายหลัง
  • grad(deriv_to) กำหนดให้อนุพันธ์ของตัวเองเทียบกับตัวเองเป็น 1 และเทียบกับสเกลาร์อื่นเป็น 0 จากนั้นใช้กฎอนุพันธ์ของการดำเนินการพื้นฐานแบบ recursive เพื่อสร้างกราฟการคำนวณใหม่
  • การติดตั้งใช้งานนี้รองรับเฉพาะสเกลาร์และอาจทำงานช้า จึงยังมีงานปรับปรุงต่อ เช่น การรองรับการคำนวณกับอาร์เรย์ การตัดกิ่งกรณีคูณด้วย 0 การจัดการโหนดค่าคงที่ และการใช้แคชเพื่อลดการคำนวณซ้ำ

ความสัมพันธ์หายไปเมื่อใช้ตัวแปร Python ทั่วไป

  • หากคำนวณแบบ x = 3, y = 5, z = x + y จะเหลือเพียงค่าผลลัพธ์ 8 อยู่ใน z
  • ต่อให้เปลี่ยนค่า x หรือ y ภายหลัง z ก็ไม่สามารถติดตามได้ว่ามันถูกสร้างมาจากตัวแปรใด
  • เมื่อความสัมพันธ์ระหว่างตัวแปรไม่ถูกเก็บไว้ จึงยากที่จะคำนวณอนุพันธ์เทียบกับตัวแปรใดตัวแปรหนึ่งโดยอัตโนมัติ

เก็บประวัติการดำเนินการไว้ด้วย Tensor

  • ชนิดข้อมูลใหม่ Tensor จะเก็บค่า (value) และ override operator เพื่อให้เมื่อคำนวณระหว่าง Tensor จะคืนค่าเป็น Tensor ตัวใหม่
  • การติดตั้งขั้นแรก override แค่ __add__ ทำให้ Tensor(3) + Tensor(5) สร้าง T:8 ได้
  • แต่ในขั้นนี้ยังไม่สามารถเก็บประวัติการดำเนินการที่บอกว่า z เป็นผลลัพธ์จาก x + y ได้

กราฟการคำนวณและ forward()

  • เพื่อเก็บประวัติการดำเนินการ จึงเพิ่ม Children = namedtuple('Children', ['a', 'b', 'op'])
    • a: เทนเซอร์อินพุตฝั่งซ้าย
    • b: เทนเซอร์อินพุตฝั่งขวา
    • op: การดำเนินการจริง เช่น np.add, np.multiply
  • Tensor แต่ละตัวสามารถมี children ได้นอกเหนือจากค่าตัวเลข ทำให้ประกอบเป็นกราฟการคำนวณในรูปแบบต้นไม้ทวิภาคได้
  • forward() จะเดินไปยังโหนดลูกแบบ recursive เพื่อคำนวณค่าจริง
    • เมื่อ x = Tensor(3), y = Tensor(5) แล้ว z1 = x + y, z2 = z1 * y จะได้ T:40
    • หรือจะสร้างกราฟไว้ก่อนด้วย x = Tensor(None), y = Tensor(None) แล้วค่อยกำหนด x.value = 3, y.value = 5 ภายหลัง จากนั้นเรียก z2.forward() ก็ยังคำนวณ T:40 ได้

สร้าง automatic differentiation เป็นกราฟการคำนวณ

  • automatic differentiation ถูกติดตั้งโดยเพิ่มกฎอนุพันธ์ให้กับการดำเนินการพื้นฐานแต่ละอย่างที่ Tensor รองรับ
  • grad(self, deriv_to) จะไล่ผ่านกราฟการคำนวณแบบ recursive และแยกฟังก์ชันที่ซับซ้อนออกเป็นการประกอบกันของฟังก์ชันที่ง่ายกว่า
  • กฎพื้นฐานมีดังนี้
    • อนุพันธ์ของเทนเซอร์เทียบกับตัวมันเองคือ Tensor(1)
    • หากเป็นสเกลาร์ที่ไม่มีโหนดลูก แล้วหาอนุพันธ์เทียบกับเทนเซอร์อื่น จะได้ Tensor(0)
    • การบวก: (a + b)' = a' + b'
    • การคูณ: (ab)' = a'b + ab'
  • หากหาอนุพันธ์ของ z2 = (x + y) * y เทียบกับ y ผลลัพธ์ g จะไม่ใช่แค่ค่าเดียว แต่เป็นกราฟการคำนวณใหม่ที่แทนอนุพันธ์ย่อย
    • ในรูปสมการคือ g = ∂z2/∂y = x + 2*y
    • เมื่อ x = 3, y = 5 ค่าของ g คือ 13

ขยายไปถึงการลบ การหาร และฟังก์ชันเอ็กซ์โปเนนเชียล

  • เพื่อรองรับนิพจน์ที่ซับซ้อนขึ้น จึงเพิ่มการลบ การหาร ฟังก์ชันเอ็กซ์โปเนนเชียล และการทำค่าติดลบเข้าไปใน Tensor
  • ใน grad() ก็เพิ่มกฎอนุพันธ์ของแต่ละการดำเนินการ
    • การลบ: (a - b)' = a' - b'
    • การหาร: (a/b)' = (a'b - ab') / b²
    • ฟังก์ชันเอ็กซ์โปเนนเชียล: exp(a)' = a' * exp(a)
  • forward() ก็ถูกปรับให้รองรับการดำเนินการที่ต้องใช้โอเปอแรนด์เพียงตัวเดียว
    • ตัวอย่างเช่น exp(a) ไม่ต้องใช้พจน์ที่สอง b
    • -x จะถูกจัดการในรูป 0 - x

ตัวอย่างสมการและการตรวจสอบด้วย Sympy

  • เขียนสมการต่อไปนี้ด้วย Tensor แล้วคำนวณอนุพันธ์ย่อยเทียบกับ x และ y
z = (12 - (x * e^y)) / (45 + x * y * e^-x)
  • ในโค้ดจะเขียนได้ดังนี้
x = Tensor(3)
y = Tensor(5)
z = (Tensor(12) - (x * y.exp())) / (Tensor(45) + x * y * (-x).exp())
  • ค่าอนุพันธ์ย่อยที่คำนวณได้มีดังนี้
    • z.grad(x) → T:-3.34729777301069
    • z.grad(y) → T:-9.70176956641438
  • เมื่อนำสมการเดียวกันไปคำนวณด้วย Sympy ผ่าน diff() และ evalf() ก็ได้ผลตรงกัน
    • ที่ xs = 3, ys = 5 ค่าอนุพันธ์เทียบกับ x คือ -3.34729777301069
    • ค่าอนุพันธ์เทียบกับ y คือ -9.70176956641438

ข้อจำกัดของการติดตั้งแบบง่ายและจุดที่ควรปรับแต่ง

  • การติดตั้งนี้ใกล้เคียงกับระบบ automatic differentiation แบบพื้นฐานที่สุด และในขณะเดียวกันก็อาจช้ามาก
  • คลาสปัจจุบันรองรับเฉพาะสเกลาร์เท่านั้น
    • หากต้องการให้เป็นไลบรารีที่ใช้งานได้จริงมากขึ้น จำเป็นต้องเพิ่มการคำนวณกับอาร์เรย์ขนาดใดก็ได้
  • เมื่อพิจารณากราฟการคำนวณ จะเห็นว่ามีจุดที่สามารถปรับแต่งได้หลายอย่าง
    • ในโหนดการคูณ หากลูกตัวใดตัวหนึ่งเป็น 0 ก็ไม่จำเป็นต้องไล่ลึกลงไปอีก
    • หากโหนดใดและโหนดลูกของมันไม่ขึ้นต่อเทนเซอร์เป้าหมายของการหาอนุพันธ์อย่าง x ก็สามารถมองโหนดนั้นเป็นค่าคงที่และหยุด traversal ได้
    • หากมีการดำเนินการเดิมเกิดซ้ำ สามารถใช้แคชเพื่อหลีกเลี่ยงการคำนวณแบบเดียวกันหลายครั้งได้

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2023-08-27
ความคิดเห็นบน Hacker News

  • ชอบ เดโมโค้ดที่เล็กและงดงาม แบบนี้ เพราะมันช่วยให้เข้าใจแนวคิดได้จากการลงมือทำเอง
    GPU Puzzles และ Tensor Puzzles ของ Sasha Rush ก็เป็นตัวอย่างคล้าย ๆ กัน
    https://github.com/srush/GPU-Puzzles
    https://github.com/srush/Tensor-Puzzles

  • ถ้าคิดว่าเพียงเท่านี้ก็เข้าใจ automatic differentiation อย่างสมบูรณ์แล้ว นั่นคือการหลอกตัวเอง
    เมื่อกราฟเป็นต้นไม้ ทุกอย่างก็เรียบง่ายมากอย่างในบทความนี้ แต่ถ้ากราฟเป็นกราฟมีทิศทางแบบไม่มีวัฏจักรทั่วไปมากขึ้น เช่น x = 5; y = 2x; z = xy แม้การ implement จะยังเรียบง่ายมาก แต่การเข้าใจว่าทำไม implementation นั้นถึงถูกต้องไม่ใช่เรื่องง่าย ถ้าคิดว่า “ก็แค่ chain rule ปกติ” นั่นก็เป็นการหลอกตัวเองเช่นกัน
    หนึ่งในคำอธิบายยุคแรก ๆ มาจาก Paul Werbos เขาเรียกกฎที่ต้องใช้ว่า chain rule ของอนุพันธ์แบบมีลำดับ และพิสูจน์ด้วยอุปนัยจาก chain rule ปกติ ถึงอย่างนั้นมันก็ไม่ได้ชัดเจนทันทีจาก chain rule ปกติ หากมีใครเชื่อในทางตรงกันข้าม ก็หวังว่าจะพิสูจน์ให้เห็นว่าผมผิดได้ ซึ่งผมจะดีใจมาก

    • ถ้าอย่างนั้นควรอ่านต่อจากที่ไหน? คนที่สร้างเฟรมเวิร์กอย่าง autograd, PyTorch, mxnet น่าจะเคยเรียนเรื่องนี้อย่างละเอียดจากที่ไหนสักแห่ง เลยอยากรู้แหล่งที่มา เท่าที่รู้ mxnet มาจากแวดวงวิชาการ น่าจะเป็น CMU
    • พูดตามตรง ผมไม่ค่อยแน่ใจว่าผู้คนต้องการอะไรจากการถกเถียงแบบนี้ และสงสัยว่าอาจเป็นเพราะ abstraction ที่แฝงอยู่คือ อนุพันธ์แบบมีลำดับ นั้นไม่ค่อยเหมาะ
      หากใช้ chain rule ปกติตามเส้นเชื่อมของ computational graph หรือก็คือกราฟมีทิศทางแบบไม่มีวัฏจักร ก็จะได้ค่าที่ถูกต้องในแต่ละขั้น กฎเพิ่มเติมที่ต้องมีมีประมาณว่า “ถ้าใช้ตัวแปรหนึ่งหลายครั้งในการคำนวณ กล่าวคือมีหลายเส้นเชื่อมออกจากโหนดเดียวกัน หรือในทิศทางย้อนกลับมีหลายเส้นเชื่อมเข้ามา ก็ต้องนำ gradient ที่คำนวณได้แต่ละตัวมาบวกกัน” ซึ่งผมมองว่าค่อนข้างพื้นฐานและเข้าใจได้โดยสัญชาตญาณ
      ตัวอย่างเช่น ถ้าใส่ z ให้ทั้ง x และ y ใน f(x, y) จะได้ d/dz f(z, z) = f_x(z, z) + f_y(z, z) โดยตัวห้อยหมายถึง partial derivative สำหรับผม วิธีนี้ดูเรียบง่ายกว่าในเชิงคณิตศาสตร์ และใกล้เคียงกับสิ่งที่ implementation จริง ๆ ทำ โดยเฉพาะ PyTorch ที่ผมคุ้นเคยที่สุด มากกว่าการผสมสองอย่างเข้าด้วยกันจนดูเหมือนเป็น “สิ่งที่เกินกว่า chain rule”
    • chain rule นิยามสำหรับ partial derivative ดังนั้นในเชิงเทคนิคก็ยังมองได้ว่าเป็นเพียง chain rule อยู่ดี

  • automatic differentiation รู้สึกเหมือนเวทมนตร์
    นักวิทยาการคอมพิวเตอร์จำนวนมากหลงใหลเรื่องนี้และเขียนบทความแนะนำเทคนิคในมุมมองที่กว้างขึ้น บทความของผมก็เป็นหนึ่งในนั้น และยังรวม “เวอร์ชันคนจน” ที่ใช้ จำนวนเชิงซ้อน โดยไม่ต้องใช้ operator overloading ด้วย
    https://pizzaseminar.speicherleck.de/automatic-differentiati...

    • ตอนที่ผมทำ machine learning ช่วงปี 1994–1995 ผมไม่รู้จัก automatic differentiation และอาจารย์ที่สร้าง objective function ก็หา analytic derivative ด้วยตัวเอง เพิ่งมารู้เมื่อไม่กี่ปีก่อนนี้เอง และเมื่อคิดถึงช่วงปลายยุค 90 ที่ผมเรียน Mathematica มากพอเพื่อสร้าง analytic derivative เอง ก็รู้สึกทึ่งมาก
    • เรื่องนี้ดูเหมือนย้อนกลับไปถึง complex-step derivative approximation ของ J. Martins, P. Sturdza, J. Alonso ในปี 2003 บทความนั้นน่าอ่าน
      [0]: https://doi.org/10.1145/838250.838251
    • รู้สึกเหมือนเวทมนตร์จริง ๆ ถ้ามีสื่อแนะนำ backpropagation ที่เขียนในแนวคล้ายกันก็อยากรู้

  • ผมมี implementation automatic differentiation ด้วย Python 26 บรรทัด ที่ทำไว้: https://gist.github.com/sradc/d9d66e3898ffe3a02e0b6b266629b0...

    • สั้นก็ดี แต่ดูเหมือนสมองผมจะทำงานได้ดีกว่ามากเมื่อมี ช่องว่าง พอเหมาะ คงต้องฝึกกับรูปแบบอื่น ๆ แบบนี้บ้าง

  • คล้ายมากกับเทคนิคที่ใช้ในระบบวิศวกรรมฐานความรู้ ซึ่งที่นั่นเรียกว่า dependency tracking เมื่อนำมาใช้ร่วมกับการแคชโหนดหรือ tensor จะช่วยลดปริมาณการคำนวณได้ โดยเฉพาะกับโมเดล 3D แบบ parametric ขนาดใหญ่
    ตอนดึงค่า จะเรียก binary/dependency tree แบบ recursive เพื่อตรวจสอบว่าตัวแปรใดเปลี่ยนไป และคำนวณใหม่เฉพาะส่วนที่จำเป็น หากใช้ Python object และ attribute แบบกำหนดเองที่มีเมธอด __set__, __get__ ก็ทำให้เหมือนเป็นฟีเจอร์ในตัวของโมเดลเชิงวัตถุได้
    x = Tensor(3)
    y = Tensor(5)
    z = x + y
    print(x, y) # 3, 5
    print(z) # 8
    x.value = 4 # ตอนตั้งค่า จะไม่คำนวณอะไรใหม่
    print(z) # 9 เพราะ dependency ที่เปลี่ยนไปจะถูกคำนวณใหม่ในจังหวะที่ดึงค่า

  • Andrej Karpathy มีวิดีโอน่าสนใจเกี่ยวกับการสร้าง autograd engine และค่อนข้างให้ insight มาก
    https://youtu.be/VMj-3S1tku0?si=wuKhELwOwoYbzpt7
    repository:
    https://github.com/karpathy/micrograd

  • รูปแบบของ automatic differentiation ที่ผมรู้จักไม่ได้สร้างกราฟของการคำนวณ แต่จะ คำนวณค่าดังกล่าวทันที แทน

    • น่าจะกำลังนึกถึง forward-mode automatic differentiation อยู่ ซึ่งมีประโยชน์กว่าเมื่อมิติของเอาต์พุตของฟังก์ชันค่อนข้างใหญ่ และต่างจาก reverse-mode automatic differentiation ที่มีประโยชน์กว่าเมื่อมิติของเอาต์พุตค่อนข้างเล็ก
      ทั้งสองแบบใช้ได้ แต่แบบหนึ่งจะมีประสิทธิภาพกว่าขึ้นอยู่กับสถานการณ์ กรณีอย่าง “การฝึก neural network” มักเป็นการปรับให้เหมาะสมกับเอาต์พุต loss เดียวสำหรับเป้าหมายจำนวนมาก จึงมักใช้ reverse mode

  • อยากให้เรียก automatic differentiation ว่า กฎลูกโซ่เชิงตัวเลข ไปเลย หรืออย่างน้อยก็อธิบายแบบนั้น เพราะตามตัวอักษรมันก็มีแค่นั้นจริง ๆ และมีทริกเล็กน้อยบางอย่างเพิ่มเข้ามาเพื่อหลีกเลี่ยงการคำนวณเมทริกซ์จาโคเบียนอย่างชัดเจนในบาง operation ซึ่งจะทำให้เข้าใจชัดเจนกว่ามาก

    • “autodiff” ที่อธิบายในที่นี้และใช้บ่อยที่สุดในการทำ backpropagation คือ reverse-mode automatic differentiation แต่ก็มี forward mode และมีกลยุทธ์ที่อยู่ระหว่างสองสุดขั้วนี้ด้วย สุดท้ายทั้งหมดล้วนลงเอยที่กฎลูกโซ่ แต่ในระดับอัลกอริทึม การเลือกว่าจะใช้วิธีใดไม่ใช่เรื่องเล็กน้อยเลย
      ถ้าบอกให้ใช้กฎลูกโซ่เพื่อส่งต่อ gradient ผ่าน computational graph จริง ๆ คนส่วนใหญ่น่าจะนึกถึง forward mode เป็นค่าเริ่มต้นโดยสัญชาตญาณ ผมเองก็คงเป็นแบบนั้น
      https://en.wikipedia.org/wiki/Automatic_differentiation#Beyo...
      เมื่อดูจากประเด็นนี้ คำนี้ดูมีประโยชน์ในฐานะคำที่ชี้ถึงวิธีเฉพาะในการวนผ่านนิพจน์ที่กฎลูกโซ่ให้มาแล้วสะสม gradient
    • ในทางเทคนิคแล้วผิดครับ กฎลูกโซ่เชิงตัวเลข ใช้วิธี finite difference และ error จะสะสมไปตามการคำนวณ
      ดูส่วน “ความแตกต่างจากวิธีอื่น” ได้ที่: https://en.m.wikipedia.org/wiki/Automatic_differentiation
      ตามที่คอมเมนต์ใกล้ ๆ บอก ประเด็นสำคัญคือ implementation สำคัญมากจริง ๆ และควรค่าแก่การศึกษา การบอกว่า automatic differentiation เป็นกลุ่มของวิธีที่ implement กฎลูกโซ่นั้นพอได้ แต่การบอกว่าเป็น “แค่” กฎลูกโซ่เชิงตัวเลขนั้นผิด
    • อาจจะแม่นยำกว่านี้ได้ แต่ผมคงไม่เรียกว่าชัดเจนกว่า

  • automatic differentiation ก็เป็นแค่ Cartesian lens ของ เมทริกซ์จาโคเบียน และ total derivative ในหมวดหมู่ของฟังก์ชันเรียบไม่ใช่หรือ มีปัญหาอะไร? https://www.youtube.com/watch?v=ne99laPUxN4

  • สงสัยว่าทำไมถึงเรียกชื่อคลาสว่า Tensor มีวิธีมอง expression หรืออนุพันธ์ของมันเป็น tensor ได้ไหม? หรือเพราะ scalar ก็เป็น tensor และสามารถขยายตัวนี้ให้รองรับ tensor type อื่น ๆ ได้ด้วย?

    • อาจจะผิดก็ได้ แต่ในทางคณิตศาสตร์ ผมคิดว่าวัตถุ 2 มิติเรียกว่า matrix และวัตถุตั้งแต่ 3 มิติขึ้นไปเรียกว่า tensor
      อัลกอริทึม automatic differentiation ที่อธิบายไว้นี้ทำงานกับวัตถุมิติสูงใด ๆ ก็ได้ ดังนั้นการเรียกวัตถุแบบนี้ว่า tensor ก็ดูสมเหตุสมผล