เหนือกว่า A*: การวางแผนที่ดียิ่งขึ้นด้วยการใช้ Transformer

 (arxiv.org)
2 คะแนน โดย GN⁺ 2024-02-25 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Transformer และ LLM ทำได้ดีในงานสนทนา การทำความเข้าใจภาพ และการเติมโค้ด แต่ยังยากที่จะให้ประสิทธิภาพที่เสถียรใน การวางแผนหลายขั้นตอน และการให้เหตุผลระดับสูง
  • งานวิจัยนี้แปลงโจทย์การวางแผนและวิธีแก้ที่เหมาะที่สุดให้อยู่ในรูปของลำดับโทเค็น และใส่ ร่องรอยการทำงาน ของการที่ A* แก้ปัญหาลงไปในข้อมูลฝึกด้วย
  • Searchformer ถูกฝึกให้เลียนแบบกระบวนการค้นหาของ A* ก่อน แล้วจึงปรับละเอียดให้สร้างลำดับการค้นหาที่สั้นลงโดยยังคงแผนที่เหมาะที่สุดไว้
  • ในการทดลองกับ Sokoban โมเดลตระกูล Searchformer แก้โจทย์ทดสอบได้ 93.7% และใช้ ขั้นตอนการค้นหาน้อยลงเฉลี่ย 26.8% เมื่อเทียบกับ A* เวอร์ชันอ้างอิง
  • แม้ร่องรอยการทำงานจะเพิ่มภาระจนทำให้ลำดับที่สร้างยาวขึ้น 10×~100× แต่ก็ยังสร้างแผนที่เหมาะที่สุดสำหรับโจทย์ที่ไม่เคยเห็นได้บ่อยกว่าโมเดลขนาดใหญ่แบบ solution-only แม้ใช้ลำดับฝึกน้อยกว่า

สิ่งที่ Transformer ทำได้ดี และโจทย์การวางแผนที่ยังอ่อนอยู่

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

ข้อจำกัดของพรอมป์ตแบบคิดเป็นขั้นตอน

  • แนวทางช่วงหลังพยายามเพิ่มประสิทธิภาพโดยชักนำให้ Transformer สร้าง “ความคิด” ระหว่างทางก่อนตอบ
  • พรอมป์ตแบบ Chain-of-Thought(CoT) และ Tree-of-thoughts(ToT) กระตุ้นให้โมเดล “คิด” เป็นลำดับขั้น
  • เทคนิคเหล่านี้มักได้ผล แต่ก็อาจทำให้ประสิทธิภาพลดลงได้จากสาเหตุอย่าง self-enforcing
  • วิธีที่ได้ผลดีในชุดข้อมูลหนึ่งอาจล้มเหลวในอีกชุดข้อมูลหนึ่ง
    • ตัวอย่างเช่น กรณีที่ประเภทของการให้เหตุผลที่ต้องใช้แตกต่างกัน เช่น การให้เหตุผลเชิงพื้นที่กับการให้เหตุผลทางคณิตศาสตร์
  • วิธีทำให้ Transformer และ LLM สามารถทำการวางแผน การตัดสินใจหลายขั้นตอน และการให้เหตุผลได้อย่างเสถียร ยังคงเป็นหัวข้อวิจัยที่มีการศึกษาอย่างเข้มข้น

วิธีใส่พลวัตการค้นหาของ A* ลงในข้อมูลฝึก

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

ขั้นตอนการฝึกของ Searchformer

  • โมเดลสุดท้าย Searchformer ถูกสร้างขึ้นเป็นสองขั้นตอน
    • ขั้นแรก ฝึกให้ Transformer เลียนแบบกระบวนการค้นหาของ A*
    • จากนั้นปรับละเอียดให้ค้นหาแผนได้ด้วยขั้นตอนการค้นหาที่น้อยลง ขณะเดียวกันก็ยังส่งออกแผนที่เหมาะที่สุด
  • กระบวนการนี้เรียกว่า search dynamics bootstrapping
  • เป้าหมายคือการได้ Transformer ที่แก้โจทย์การวางแผนซับซ้อนได้โดยใช้ขั้นตอนการค้นหาน้อยกว่า A* เวอร์ชันอ้างอิง

การทดลองกับ Sokoban และประสิทธิภาพการทำการทั่วไป

  • ในปริศนา Sokoban โมเดลตระกูล Searchformer แก้โจทย์ทดสอบทั้งหมดได้ 93.7%
  • จำนวนขั้นตอนการค้นหาเฉลี่ย น้อยกว่า 26.8% เมื่อเทียบกับ A* เวอร์ชันอ้างอิง
  • การทดลองที่ควบคุมความซับซ้อนของโจทย์ ขนาดชุดข้อมูล และขนาดโมเดล ยืนยันผลของการใส่ร่องรอยการทำงาน
  • เมื่อนำร่องรอยการทำงานเข้าไปในข้อมูลฝึก ความยาวของลำดับที่สร้างจะเพิ่มขึ้น 10×~100×
  • ถึงอย่างนั้น ประสิทธิภาพบนชุดโจทย์ทดสอบอิสระก็ยังเพิ่มขึ้น
  • search-augmented model สร้างแผนที่เหมาะที่สุดสำหรับโจทย์ที่ไม่เคยเห็นได้บ่อยกว่า solution-only model แม้มีลำดับฝึกน้อยกว่าถึง 10 เท่า
    • search-augmented model ฝึกด้วยข้อมูลที่รวมคำอธิบายโจทย์ วิธีแก้ และร่องรอยการทำงาน
    • solution-only model ฝึกด้วยลำดับที่มีเพียงคำอธิบายโจทย์และวิธีแก้โจทย์
  • ผลลัพธ์นี้แสดงให้เห็นว่า การใส่ พลวัตการค้นหา ของ A* เข้าไปในกระบวนการฝึกของ Transformer สามารถยกระดับประสิทธิภาพในโจทย์การวางแผนได้

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

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

 
GN⁺ 2024-02-25
ความเห็นจาก Hacker News

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

  • ก่อนจะไปถึงแนวทางวิจัยนี้ ก็สงสัยว่าได้ลอง อัลกอริทึม J แบบดัดแปลง* ซึ่งเป็นการปรับแต่ง A* สำหรับกราฟเกม/การหาเส้นทางหรือยัง
    ใครสนใจดูได้ใน Game AI Pro 2 0

    • ที่เกี่ยวข้องก็มี https://github.com/anvaka/ngraph.path ด้วย
    • ถ้ามองอย่างเป็นธรรม ผู้เขียนก็ระบุไว้ช่วงท้ายของบทความแล้วว่าตัวหาเส้นทางของพวกเขายังไม่ถึงระดับที่แข่งขันกับ เทคนิคล้ำสมัยล่าสุด ได้
      งานนี้ทดสอบว่าทรานส์ฟอร์เมอร์ทำนาย execution trace ได้ดีแค่ไหน เช่นในกรณีอย่าง JIT compiler และดูว่าสิ่งนั้นช่วยปรับปรุงฮิวริสติกในงานอย่างการหาเส้นทางได้หรือไม่
      แต่อย่างไรก็ดี ทรานส์ฟอร์เมอร์ก็ช้า เลยทำให้มองเรื่องนี้อย่างระมัดระวัง
    • ชอบหนังสือชุดนี้และก็ดีใจที่ Steve Rabin ยังทำต่อ แต่ อีบุ๊ก 120 ดอลลาร์ นี่เกินคาดจริง ๆ

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

    • น่าสนใจถ้าจะลองเทียบ Prolog กับ LLM เพื่อจุดประสงค์คล้ายกัน

  • การแปลภาษาด้วยเครื่องในอดีตเคยต้องใช้การถอดรหัสไวยากรณ์ที่ซับซ้อนและอาศัยการค้นหา แต่ตอนนี้ใช้ ทรานส์ฟอร์เมอร์ กับการถอดรหัสที่ง่ายกว่ามากและแทบไม่ต้องค้นหาเลย
    ตอนนี้เราอาจไปถึงโครงสร้างแบบเวียนกลับเต็มรูปแบบได้ด้วย
    แนวคิดคือใช้โมเดลพยากรณ์ระดับแนวหน้าปัจจุบันมาเรียนรู้ฮิวริสติกของ neural architecture search (NAS) แล้วค้นหาบล็อกโครงข่ายประสาทแบบใหม่ที่ดีกว่า transformer หรือ mamba

    • “ทุกครั้งที่เราปลดนักภาษาศาสตร์ ประสิทธิภาพของระบบรู้จำเสียงจะดีขึ้น” — Frederick Jelinek
    • สุดท้ายเราอาจกำลังเข้าสู่โลกที่แม้แต่คนที่พัฒนาเทคโนโลยีเองก็ไม่เข้าใจกลไกการทำงานของมันอีกต่อไป
      ภาวะเอกฐานกำลังมา…

  • ถ้าสนใจเกมสาย Sokoban ก็อาจลองดู https://thinky.gg
    มี Sokopath ซึ่งเป็น เกมดัดแปลงของ Sokoban ที่สนุก และยังมีอีกเกมชื่อ Pathology ซึ่งเป็นเวอร์ชันดัดแปลงแบบ NP-hard ที่เป้าหมายคือเดินจากจุด A ไปจุด B ด้วยจำนวนก้าวที่สั้นที่สุด
    ในชุมชนมีคนพยายามสร้างตัวแก้หลายตัว แต่พอกริดเกิน 5x5 ก็ยากมากแล้ว และชุมชน thinky ก็ยังค้นพบด่านน่าสนใจที่มีจำนวนก้าวสูงมากด้วย simulated annealing

  • “ลดจำนวนขั้นตอนการค้นหาได้ 26.8% เมื่อเทียบกับการค้นหา A* มาตรฐาน”
    ก็แปลว่าสำหรับ Sokoban มันแค่ดีกว่า A* ที่ห่างไกลจากระดับล้ำสมัยอยู่นิดหน่อยเท่านั้น (https://festival-solver.site/)
    เลยไม่ค่อยเข้าใจว่าอะไรในงานนี้น่าประทับใจ หรือทำไมถึงขึ้น Hacker News

    • ภายใต้ข้อจำกัดเฉพาะที่ A* นิยามไว้ มันคืออัลกอริทึมการค้นหาที่เหมาะที่สุดอยู่แล้ว จึงทำได้ดีกว่านี้ไม่ได้
      แต่ถ้าในโดเมนที่ค้นหามีข้อจำกัดอื่นที่นำมาใช้ได้ ก็อาจทำได้ดีกว่า A*
      ตัวอย่างเช่น Jump Point Search ใช้ประโยชน์จากคุณสมบัติของการค้นหาบนกริดที่เคลื่อนที่ได้เฉพาะบางรูปแบบ
      ถ้าสามารถสร้างอัลกอริทึมการค้นหาทั่วไปที่ “ใช้ประโยชน์” จากคุณสมบัติเฉพาะของโดเมนต้นทางได้อย่างมีประสิทธิภาพแบบอัตโนมัติ โดยไม่ต้องให้มนุษย์มาวิเคราะห์เอง ก็น่าจะมีประโยชน์มากไม่ใช่หรือ
    • เพราะมันไปถึงคำตอบที่ใช้ได้ดีและดีกว่า A* แบบมาตรฐานด้วยทรานส์ฟอร์เมอร์
      A* ก็ใกล้เคียงกับคำตอบพื้นฐานแบบ “ตรงไปตรงมา” และคนกลุ่มนี้ก็ไม่ได้ลงมือออกแบบอัลกอริทึมโดยตรง
      แค่ ทรานส์ฟอร์เมอร์แบบ encoder-decoder ธรรมดาก็ทำได้ถึงระดับนี้ ถือว่าน่าประทับใจพอสมควร
    • ก็เขียนไว้ชัดตั้งแต่บรรทัดแรกของบทคัดย่อ
      “Transformers have enabled tremendous progress in various application settings, such architectures still lag behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks ...”
      งานนี้น่าสนใจเพราะเป็นตัวอย่างของการใช้ทรานส์ฟอร์เมอร์กับการตัดสินใจ และไม่ได้สนใจมากนักว่าตอนนี้มันอยู่ในระดับ A* หรือยัง
    • ที่ขึ้น HN ก็เพราะชุมชนชอบมัน
    • นี่เป็นหลักฐานเพิ่มอีกชิ้นที่สนับสนุน ประสิทธิผลที่ดูเกินเหตุของทรานส์ฟอร์เมอร์ ว่ามันไม่ใช่แค่เครื่องทำนายโทเคนถัดไป แต่เป็นแนวทางอเนกประสงค์อย่างแท้จริงที่ใช้ได้กับงานเรียนรู้แทบทุกแบบ
      แน่นอนว่าสมมติฐานนี้มีทั้งเวอร์ชันเข้มและเวอร์ชันอ่อน และเวอร์ชันเข้มก็คงไม่จริง แต่ก็ดูเป็นข่าวสำคัญในแง่ที่เรากำลังเข้าใกล้ “วิธีจริงหนึ่งเดียว” ที่ธรรมชาติใช้ในการเรียนรู้การทำงานมากขึ้น

  • ถ้าทรานส์ฟอร์เมอร์วางแผนได้ ก็อาจหมายความว่าสำหรับ ปัญญาประดิษฐ์ทั่วไป เราแค่ต้องมีการฝึกที่ดีกว่านี้

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

  • สำหรับคนที่เรียนรู้ผ่านการฟัง มีคนทำสรุปบทความนี้ในรูปแบบออดิโอบุ๊กไว้แล้ว
    https://player.oration.app/09fefe41-f2a7-4257-a25e-30e479b30d6f

  • ค่อนข้างมองโลกในแง่ดีมากเกี่ยวกับการใช้ฮิวริสติกที่เรียนรู้แล้วกับอัลกอริทึมเชิงไม่ต่อเนื่องอย่าง A*, Focal search และตระกูล การโปรแกรมเชิงเส้นจำนวนเต็ม หลายแบบ
    ในไลบรารี optimization แบบไม่ต่อเนื่องสมัยใหม่ส่วนใหญ่ เช่น CPLEX ความแตกต่างของประสิทธิภาพมักอธิบายได้ด้วยฮิวริสติกและการจูน
    แต่การแทนที่ขั้นตอนการค้นหาแบบเหมาะที่สุดที่เข้าใจกันดีอยู่แล้วด้วยแนวทางเรียนรู้แบบ end-to-end นั้นฟังดูน่าเชื่อน้อยกว่า แม้อาจจะเป็นความกังวลเกินไปก็ได้
    เพียงแต่ดูเหมือนผู้เขียนจะพลาดโอกาสนั้นไป

    • ก็ดูเหมือนเป็นแค่ กระแสฟองสบู่/การปั่นเกินจริง รอบ ๆ ทรานส์ฟอร์เมอร์กับ AI
      ผมเองก็คงลองใช้ทรานส์ฟอร์เมอร์แก้ tic-tac-toe แล้วไปขอเงิน VC ดูบ้าง
      อีกไม่กี่ปีข้างหน้าอาจมีคนเขียนกันเต็มไปหมดว่าโค้ดจริงมีประสิทธิภาพกว่า AI แค่ไหน ;)
    • เห็นด้วย
      ถ้าเรียนรู้ ฮิวริสติกที่ยอมรับได้ ก็ยังรักษาประสิทธิภาพในกรณีเลวร้ายที่สุดไว้ได้ และนั่นก็เป็นมาตรฐานของอัลกอริทึมพวกนี้มาโดยตลอด
      การหาคำตอบที่เร็วขึ้นในกรณีเฉลี่ยหรือกรณี p99 แต่ไม่สามารถรับประกันกรณีเลวร้ายที่สุดได้นั้น ไม่ใช่เรื่องแปลกเลย

  • สงสัยว่ามีใครรวบรวมรายชื่อ อัลกอริทึมคลาสสิก หรือปัญหา NP-complete ที่ทำได้ดีขึ้นด้วยดีปเลิร์นนิงไว้บ้างไหม

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