Tree Diffusion สำหรับการสังเคราะห์โปรแกรมด้วยต้นไม้ไวยากรณ์

 (tree-diffusion.github.io)
2 คะแนน โดย GN⁺ 2024-06-05 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • งานวิจัย ICLR 2025 Tree Diffusion เสนอโมเดลประสาทที่ไม่ได้สร้างโปรแกรมทีละโทเค็น แต่ทำการ แก้ไข โปรแกรมซ้ำ ๆ โดยอ้างอิงจากผลลัพธ์การรัน
  • แก่นสำคัญคือการเรียนรู้บน ต้นไม้ไวยากรณ์ ที่สร้างจากไวยากรณ์แบบไม่ขึ้นกับบริบทใด ๆ โดยใช้วิธีแบบย้อนนอยส์คล้าย diffusion ของภาพ
  • นอยส์ถูกเพิ่มด้วยการกลายพันธุ์แบบสุ่มที่เปลี่ยนโหนดใด ๆ ในต้นไม้ไวยากรณ์ให้เป็นโหนดอื่นที่มี ชนิดที่ถูกต้อง เดียวกัน
  • เพราะสามารถปรับแก้โค้ดต่อไปได้โดยยังคงสถานะที่ถูกต้องตามไวยากรณ์ จึงเชื่อมเข้ากับ การค้นหา (search) ในพื้นที่โปรแกรมได้ง่าย
  • ใน inverse graphics สามารถแปลงภาพเป็นโปรแกรมที่ใช้สร้างภาพนั้น และเมื่อผสานกับการค้นหา ก็สามารถดีบักโปรแกรมกราฟิกให้ตรงตามข้อกำหนดได้โดยดูจากผลลัพธ์การรัน

แนวทางของ Tree Diffusion

  • Tree Diffusion เป็นวิธีที่นำ diffusion บนต้นไม้ไวยากรณ์ มาใช้เพื่อการสังเคราะห์โปรแกรม
  • มีการเผยแพร่ทั้งงานวิจัย, arXiv, โค้ดและน้ำหนักโมเดล
  • โมเดลภาษาขนาดใหญ่แบบเดิมสร้างโค้ดด้วย วิธีออโตรีเกรสซีฟ ทีละโทเค็น และไม่มีฟีดแบ็กจากการสังเกตผลลัพธ์ของโปรแกรมระหว่างกระบวนการสร้าง
  • แนวทางที่ฝึกให้ LLM เสนอการแก้ไขโดยตรงอาจทำได้ยาก เพราะต้องการ ข้อมูลการแก้ไข จำนวนมากเพียงพอ
  • Tree Diffusion แก้ไขโปรแกรมด้วยโมเดลที่ย้อนนอยส์ซึ่งถูกใส่ลงบนต้นไม้ไวยากรณ์ของไวยากรณ์แบบไม่ขึ้นกับบริบท

นอยส์ การค้นหา และกรณีใช้งาน

  • นอยส์คือการกลายพันธุ์แบบสุ่มที่เลือกโหนดใดโหนดหนึ่งในต้นไม้ไวยากรณ์ แล้วแทนที่ด้วยโหนดอื่นที่มี ชนิดที่ถูกต้อง เดียวกับโหนดเป้าหมาย
  • แทนที่จะสร้างโปรแกรมจากศูนย์แบบลำดับต่อเนื่อง ระบบจะทำการแก้ไขซ้ำ ๆ พร้อมคง ความถูกต้องตามไวยากรณ์ เอาไว้
  • คุณสมบัตินี้ทำให้สามารถผสานโมเดลประสาทเข้ากับ การค้นหา ในพื้นที่โปรแกรมได้ง่าย
  • ในงาน inverse graphics ระบบเรียนรู้วิธีรับภาพเป็นอินพุต แล้วแปลงเป็นโปรแกรมที่ใช้สร้างภาพนั้น
  • ระบบที่ผสานกับการค้นหาสามารถเขียนโปรแกรมกราฟิก ตรวจสอบผลการรัน แล้วดีบักให้ตรงตามข้อกำหนดได้
  • ยังแสดงให้เห็นว่าสามารถเขียนโปรแกรมกราฟิกสำหรับสเก็ตช์ที่วาดด้วยมือได้ด้วย

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

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

 
GN⁺ 2024-06-05
ความคิดเห็นจาก Hacker News

  • ฟังดูคล้ายกับงานที่เคยทำกับ Racket และการสร้างคำใบ้สำหรับ MOOC มากกว่า
    ผมไม่แน่ใจว่าเป็นมหาวิทยาลัยไหน แต่เคยเห็นการนำเสนอที่แปลงต้นไม้ไวยากรณ์ แล้ววิเคราะห์ว่าต้องแก้อย่างไรเพื่อไปถึงคำตอบเป้าหมาย จากนั้นสร้างคำใบ้ให้นักเรียน
    น่าจะเป็นการนำเสนอใน RacketCon เมื่อราว 10 ปีก่อน และอาจนำวิธีแบบนี้มาผสานกับแนวทางแมชชีนเลิร์นนิงสมัยใหม่ได้
    เจอการนำเสนอแล้ว: https://invidious.baczek.me/watch?v=ijyFC36kVis

  • การกลายพันธุ์ของซับทรี แบบนี้น่าสนใจ เพราะ Koza และ Adamı เคยศึกษาเรื่องนี้ค่อนข้างลึกในยุค 90 ภายใต้ชื่ออัลกอริทึมเชิงพันธุกรรม
    ต่างกันเพียงฟังก์ชันเพิ่มประสิทธิภาพเล็กน้อยเท่านั้น
    ในบทความมีเอกสารอ้างอิงปี 2000 หนึ่งรายการเกี่ยวกับอัลกอริทึมเชิงพันธุกรรมสำหรับสร้างต้นไม้โปรแกรมอย่างรวดเร็ว แต่ดูเหมือนงานแกนหลักจะหายไป
    อยากให้ผู้เขียนอ่านเรื่องนี้และขุดลึกไปในงานของคนเหล่านั้น

    • ทางเลือกที่ใหม่กว่า genetic programming ของ Koza ใช้กลไกการค้นหาที่ค่อนข้างต่างออกไป
      FFX และ PGE ต่างก็เร็วมาก
      https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_...
      https://arxiv.org/pdf/2209.09675
      ในฐานะผู้สร้าง PGE ผมคิดมาตลอดว่า reinforcement learning และล่าสุดคือเทคนิค diffusion อาจช่วยอัลกอริทึมเหล่านี้ได้
      อัลกอริทึมทุกแบบต้องการวิธีที่จะชี้นำการค้นหาให้ดีขึ้น หรือช่วยให้หลุดจาก จุดเหมาะที่สุดเฉพาะที่ ซึ่งมักติดได้เร็วอย่างน่าประหลาด
      งานวิจัยส่วนใหญ่ด้าน genetic programming/evolutionary computation มุ่งไปที่การหลีกเลี่ยงการลู่เข้าก่อนเวลาอันควร
    • ก่อนหน้านี้ผมบอกว่าผู้เขียนอาจไม่ค่อยรู้จัก Koza และ Adami แต่ผมไม่ทันสังเกตว่าผู้เขียนที่ติดต่อได้คือ Stuart Russell ผู้เขียน Artificial Intelligence: A Modern Approach ร่วมกับ Peter Norvig
      ตามคำอธิบายในเว็บไซต์ หนังสือนี้คือ “ตำรา AI ที่ทรงอิทธิพลและใช้กันแพร่หลายที่สุด ซึ่งถูกนำไปใช้ในโรงเรียนมากกว่า 1,500 แห่ง”
      https://aima.cs.berkeley.edu/
      แย่เลย ผมพลาดเอง
    • พูดให้ถูกคือ genetic programming
      ผมมีหนังสือเล่มหนาสองเล่มของ Koza จากปี 1992 และ 1994 คือ Genetic Programming: On the Programming of Computers by Means of Natural Selection และ Genetic Programming II : Automatic Discovery of Reusable Programs
      ส่วนอีกสองเล่มหลังจากนั้นไม่ได้อ่าน
      ปัญหาใหญ่ที่ติดในตอนนั้น ส่วนหนึ่งคือทำให้เร็วพอ และอีกส่วนคือทำให้ผลลัพธ์ออกมาในรูปที่มนุษย์เข้าใจได้
      อย่างหลังนี้โดยเฉพาะดูเหมือนโมเดลภาษาขนาดใหญ่จะทำได้ดีกว่ามาก
      ต้องใช้เวลามากในการจัดโครงสร้างต้นไม้ใหม่และตัดแต่งกิ่งเพื่อให้ได้ผลลัพธ์ที่อ่านเข้าใจได้ ดังนั้นคุณค่าหลักจึงดูจำกัดอยู่ในกรณีที่คุ้มจะทุ่มทรัพยากรมากเพื่อหาเวอร์ชันที่ปรับให้เหมาะยิ่งขึ้นของอัลกอริทึมที่เล็กและหนาแน่นมาก
      แต่โค้ดเบสส่วนใหญ่มีผลไม้แขวนต่ำให้เก็บง่าย ๆ อยู่มากเกินไป จึงแทบไม่ค่อยไปถึงจุดที่ความพยายามแบบนี้คุ้มค่า
      ถึงอย่างนั้น ในเชิงแนวคิดผมก็ยังชอบอยู่
      [1] https://www.genetic-programming.com/johnkoza.html
    • เอกสารอ้างอิงคือพวกนี้หรือเปล่า?
      https://web.archive.org/web/20021224053225/http://smi-web.st...
      https://www.genetic-programming.com/jkpdf/tr1314.pdf
    • ถ้ามองแบบนั้น backpropagation ก็อาจเรียกได้ว่าเป็นกฎลูกโซ่จากหลายศตวรรษก่อนเหมือนกัน

  • การใช้ Markov chain Monte Carlo กับ program synthesis ไม่ใช่แนวคิดใหม่อะไรนัก
    เอกสารอ้างอิงที่นึกถึงทันทีคืองานของ Josh Tenenbaum
    WebPPL (ภาษาเว็บสำหรับ probabilistic programming) ก็มีเดโมมากมาย เช่น การสังเคราะห์ยานอวกาศ 3D
    ขอแนะนำอย่างยิ่งทั้งหนังสือ The Design and Implementation of Probabilistic Programming Languages และ Probabilistic Models of Cognition
    บทความของ MIT Probabilistic Computing Project ก็น่าอ่านเช่นกัน
    [1] Human-level concept learning through probabilistic program induction. https://www.cs.cmu.edu/~rsalakhu/papers/LakeEtAl2015Science....
    [2] http://webppl.org/
    [3] https://dritchie.github.io/web-procmod/
    [4] https://dippl.org/
    [5] http://probmods.org/
    [6] http://probcomp.csail.mit.edu/

    • น่าสังเกตด้วยว่า Shreyas ผู้เขียนคนแรก เคยเป็นนักศึกษาของ Tenenbaum ที่ MIT ก่อนจะไป Berkeley

  • “เวทมนตร์” ที่พูดถึงตรงนี้ยังไม่ค่อยเข้าใจ
    ถ้าเป็นแนวทางดั้งเดิม ก็คงสร้างภาพแบบสุ่ม คำนวณมาตรวัดระยะห่างบางอย่าง แล้วใช้วิธีเพิ่มประสิทธิภาพอย่าง simulated annealing เพื่อลดระยะนั้นให้ต่ำสุด
    ตรงนี้พอเข้าใจว่าเป็นการปรับความแตกต่างระหว่างตัวแทนภาพให้เหมาะสม แต่ไม่รู้ว่าการ เปลี่ยนโทเคน ของโปรแกรมจะทำให้หาอนุพันธ์ได้อย่างไร

    • การเปลี่ยนโทเคนของโปรแกรมโดยตัวมันเอง หาอนุพันธ์ไม่ได้
      แนวคิดหลักดูเหมือนอยู่ที่การฝึกโมเดลนิวรัลเน็ตเวิร์กให้เสนอการแก้ไขโปรแกรมด้วยการแปลงโหนดแบบสุ่ม
      เมื่อรันโมเดลนิวรัลเน็ตเวิร์กนี้ จะสามารถแก้ไขได้อย่างถูกต้องตามไวยากรณ์ตาม context-free grammar เช่น เปลี่ยนตัวเลขได้เฉพาะกับตัวเลขเท่านั้น

  • สงสัยว่าถ้านำสิ่งนี้ไปใช้กับ การเพิ่มประสิทธิภาพคอมไพเลอร์/อินเทอร์พรีเตอร์ จะเป็นอย่างไร
    จะสามารถ “ชำแหละ” บางส่วนของการรัน อาจถึงระดับแอสเซมบลี แล้วสร้างการเพิ่มประสิทธิภาพเฉพาะสำหรับโค้ดที่คอมไพล์แล้ว ซึ่งคอมไพเลอร์สมัยใหม่ค้นหาแบบกำหนดแน่นอนไม่เจอ โดยไม่เปลี่ยนเอาต์พุตได้หรือไม่?
    ในที่นี้เอาต์พุตหมายถึงผลลัพธ์ของโปรแกรมที่คาดหวัง ไม่ใช่ไบนารีที่ถูกสร้างขึ้น

    • คำตอบน่าจะเป็น “ไม่”
      ถ้าเครื่องมือแบบนี้ไม่ได้ถูกฝึกจากผลลัพธ์การคอมไพล์ ก็ไม่คาดหวังว่ามันจะ “ค้นพบ” แอสเซมบลี ได้
      โมเดลไม่มีแนวคิดว่าโค้ดรันอย่างไรหรือรันที่ไหน
      หลังจากงานวิจัยคอมไพเลอร์และซูเปอร์คอมไพเลอร์ดำเนินมาหลายสิบปี ตอนนี้เราอยู่ในจุดที่แทบเป็นไปไม่ได้แล้วที่จะค้นพบการเพิ่มประสิทธิภาพใหม่ ๆ ที่ให้ผลดีขึ้นอย่างเห็นได้ชัด
      คอมไพเลอร์ในปัจจุบันดีมากจริง ๆ
      อย่างไรก็ตาม คุณค่าของวิธีแบบนี้อาจอยู่ที่การปรับเจตนาของโค้ดให้เหมาะสม
      ถ้าตัดสินได้ว่ากำลังเรียงลำดับตัวเลข ก็อาจเปลี่ยนโค้ดเป็นอัลกอริทึมเรียงลำดับที่เร็วกว่าแต่มีคุณสมบัติเชิงฟังก์ชันเหมือนกันได้
      ถ้ากำลังเก็บข้อมูลที่ไม่ได้ใช้ ก็หยุดเก็บได้
      เป็นมุมมองที่ดูโค้ดในระดับสูงกว่าที่คอมไพเลอร์เห็นหนึ่งขั้น และเข้าใจไม่ใช่แค่ว่ามันทำอะไร แต่ยังรวมถึงว่าทำไปทำไมด้วย
    • วิทยานิพนธ์ปริญญาเอกของผมก็จัดการปัญหาคล้าย ๆ กัน
      ผมใช้การทำ obfuscation เพื่อสร้างชุดข้อมูลขนาดใหญ่จากชุดฟังก์ชันคำตอบที่มีขนาดเล็ก แล้วสร้างโมเดลที่จัดประเภทโค้ดไบนารีที่ถูก obfuscate และไม่เคยเห็นมาก่อนให้เป็นฟังก์ชันที่ใกล้เคียงที่สุดในบรรดาฟังก์ชันที่รู้จัก
      ตอนทำวิจัย แอปพลิเคชันที่นึกถึงคือการวิเคราะห์มัลแวร์แบบสแตติก แต่จริง ๆ แล้วการเพิ่มประสิทธิภาพคือ อีกด้านหนึ่งของการ obfuscation
      สิ่งที่อยากลองทำต่อไปคือโมเดล diffusion ที่มองการ obfuscation เป็น “สัญญาณรบกวน” ที่ต้องกำจัด
      สิ่งหนึ่งที่ได้เรียนรู้คือคอมไพเลอร์แบบเพิ่มประสิทธิภาพสร้างเอาต์พุตที่มีแบบแผนมาก
      เมื่อทำให้แอดเดรสอยู่ในรูปมาตรฐานแล้ว ขนาด “คำศัพท์” ของ basic block จะค่อนข้างเล็ก ราวกับมีประมาณ 2,000 โทเคน
      “วลี” บางแบบมีสหสัมพันธ์กับความหมายของซอร์สโค้ดเดิม ไม่ว่าจะโปะ obfuscation ลงไปมากแค่ไหนก็ตาม
    • สิ่งนี้เรียกว่า superoptimization: https://en.wikipedia.org/wiki/Superoptimization
      มีคนที่นำเทคนิค synthesis ไปใช้กับ superoptimization ด้วย
      ดังนั้นแนวทางแบบนี้จึงมีความเป็นไปได้ที่จะถูกนำไปใช้

  • ก่อนหน้านี้เคยมีเรื่องว่า GitHub จะเพิ่มการผสานรวมกับเครื่องมือ build ทั่วไป
    ถ้าสามารถคอมไพล์ ทุกโปรเจกต์บน GitHub ที่คอมไพล์ด้วย LLVM ได้ แล้วรันโมเดล diffusion บน intermediate representation ของมัน จะเป็นอย่างไร?

    • แล้วเอาต์พุตจะเป็นอะไร?

  • diffusion จะทำงานได้แม้ใน ระดับไบนารี หรือเปล่า?
    จะฝึกโมเดล diffusion ที่รับพรอมป์แล้วสร้างไบนารีสุดท้ายของโปรแกรมได้ไหม?
    บางที abstract syntax tree น่าจะดีกว่า แต่ไบนารีอย่างน้อยก็น่าจะทดสอบได้ง่ายมากว่าใช้งานได้หรือไม่
    ข้อเสียคงมีเยอะ แต่ถ้าเป็นไปได้ ก็รอวันที่เราบอกว่า “ช่วยทำแอปที่ทำงานแบบนี้ให้หน่อย” แล้วโมเดล diffusion สร้างทุกไบต์ของแอปนั้นขึ้นมา
    แค่โยนคำถามด้วยความสงสัย

    • ถ้าแก้ไขด้วยฟีดแบ็กจากเอาต์พุตของโปรแกรมเหมือนงานนี้ อาจเหมาะกว่าที่จะถอดไบนารีเป็นแอสเซมบลีก่อน ให้แก้ไข abstract syntax tree ของภาษาแอสเซมบลี แล้วค่อยประกอบกลับ
      แบบนั้นโอกาสที่จะสร้างโปรแกรมที่ถูกต้องจะสูงขึ้น
    • น่าจะน่าทึ่งจริง ๆ
      ในเมื่อสร้าง โค้ดภาษาเครื่อง ได้โดยตรง ก็ไม่มีเหตุผลอะไรเป็นพิเศษที่จะต้องผ่านขั้นกลางมากมายอย่าง Python หรือ JS

  • อยากเห็นการนำไปใช้กับ SDF ด้วย

    • อธิบายเพิ่มเติมได้ไหม?
      หมายถึงแนวคิดประมาณว่าใช้สมการพีชคณิตประมาณฟังก์ชันระยะ แล้วมองพีชคณิตเองเป็น “ภาษาโปรแกรม” หรือเปล่า?

  • PDF เรนเดอร์ช้ามาก
    อาจเป็นเพราะมีคำสั่งของภาพที่สร้างด้วยการเขียนโปรแกรมอยู่ในนั้น
    ให้ความรู้สึกแบบ บทความวิชาการ ที่ช่วงนี้คิดถึง
    https://arxiv.org/pdf/2405.20519

  • ส่วนที่นำไปใช้กับ งาน inverse graphics ทำให้นึกถึงเปเปอร์นี้ที่ออกมาก่อนหนึ่งสัปดาห์: https://arxiv.org/abs/2405.15306