Deep Mind AlphaTensor จะค้นพบอัลกอริธึมใหม่

Deep Mind ได้ขยาย AlphaZero ไปสู่คณิตศาสตร์เพื่อปลดล็อกความเป็นไปได้ใหม่ๆ สำหรับอัลกอริทึมการวิจัย

AlphaTensor สร้างขึ้นจาก AlphaZero ซึ่งเป็นตัวแทนที่แสดงประสิทธิภาพเหนือมนุษย์ในเกมกระดาน เช่น หมากรุก โกะ และโชกิ และงานนี้แสดงการเดินทางของ AlphaZero ตั้งแต่การเล่นเกมไปจนถึงการแก้ปัญหาทางคณิตศาสตร์ที่ยังไม่ได้แก้เป็นครั้งแรก

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

ในช่วงยุคทองของอิสลาม นักคณิตศาสตร์ชาวเปอร์เซีย Muhammad ibn Musa al-Khwarizmi ได้ออกแบบอัลกอริธึมใหม่เพื่อแก้สมการเชิงเส้นและสมการกำลังสอง อันที่จริง ชื่อของ al-Khwarizmi ซึ่งแปลเป็นภาษาละตินว่า Algoritmi นำไปสู่คำว่า อัลกอรึทึม แต่ถึงแม้จะคุ้นเคยกับอัลกอริธึมในปัจจุบัน ซึ่งใช้กันทั่วทั้งสังคมตั้งแต่พีชคณิตในห้องเรียนไปจนถึงการวิจัยทางวิทยาศาสตร์ที่ล้ำสมัย กระบวนการค้นพบอัลกอริธึมใหม่นั้นยากอย่างเหลือเชื่อ และเป็นตัวอย่างของความสามารถในการให้เหตุผลอันน่าทึ่งของจิตใจมนุษย์

พวกเขาตีพิมพ์ใน ธรรมชาติ AlphaTensor เป็นระบบปัญญาประดิษฐ์ (AI) ตัวแรกสำหรับการค้นพบอัลกอริธึมที่แปลกใหม่ มีประสิทธิภาพ และสามารถพิสูจน์ได้สำหรับงานพื้นฐาน เช่น การคูณเมทริกซ์ สิ่งนี้ทำให้กระจ่างเกี่ยวกับคำถามเปิดอายุ 50 ปีในวิชาคณิตศาสตร์เกี่ยวกับการหาวิธีที่เร็วที่สุดในการคูณเมทริกซ์สองตัว

จากการฝึกตั้งแต่เริ่มต้น AlphaTensor ค้นพบอัลกอริธึมการคูณเมทริกซ์ที่มีประสิทธิภาพมากกว่าอัลกอริธึมที่ออกแบบโดยมนุษย์และด้วยคอมพิวเตอร์ที่มีอยู่ แม้จะมีการปรับปรุงอัลกอริธึมที่รู้จัก แต่พวกเขาทราบว่าข้อจำกัดของ AlphaTensor คือความจำเป็นในการกำหนดชุดของปัจจัยที่เป็นไปได้ F ล่วงหน้า ซึ่งแยกพื้นที่การค้นหาออก แต่อาจทำให้พลาดอัลกอริธึมที่มีประสิทธิภาพได้ ทิศทางที่น่าสนใจสำหรับการวิจัยในอนาคตคือการปรับ AlphaTensor เพื่อค้นหา F จุดแข็งที่สำคัญประการหนึ่งของ AlphaTensor คือความยืดหยุ่นในการสนับสนุนการสุ่มตัวอย่างที่ซับซ้อนและผลตอบแทนที่ไม่แตกต่างกัน (ตั้งแต่อันดับเทนเซอร์ไปจนถึงประสิทธิภาพเชิงปฏิบัติบนฮาร์ดแวร์เฉพาะ) นอกเหนือจากการค้นหาอัลกอริธึม สำหรับการดำเนินการแบบกำหนดเองในพื้นที่ที่หลากหลาย (เช่น ฟิลด์จำกัด) พวกเขาเชื่อว่าสิ่งนี้จะกระตุ้นแอปพลิเคชันของ AlphaTensor ไปสู่การออกแบบอัลกอริธึมที่ปรับเมตริกที่เราไม่ได้พิจารณาในที่นี้ เช่น ความเสถียรของตัวเลขหรือการใช้พลังงาน

การค้นพบอัลกอริธึมการคูณเมทริกซ์มีนัยยะกว้าง เนื่องจากการคูณเมทริกซ์อยู่ที่แกนหลักของงานการคำนวณหลายอย่าง เช่น การผกผันของเมทริกซ์ การคำนวณดีเทอร์มิแนนต์ และการแก้ระบบเชิงเส้น

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

เกมนี้ท้าทายอย่างเหลือเชื่อ – จำนวนอัลกอริธึมที่เป็นไปได้ที่ต้องพิจารณานั้นมากกว่าจำนวนอะตอมในจักรวาลอย่างมาก แม้แต่ในกรณีของการคูณเมทริกซ์ขนาดเล็ก เมื่อเทียบกับเกม Go ซึ่งยังคงเป็นความท้าทายสำหรับ AI มานานหลายทศวรรษ จำนวนการเคลื่อนไหวที่เป็นไปได้ในแต่ละขั้นตอนของเกมนั้นใหญ่กว่า 30 ลำดับ (มากกว่า 10 ^ 33 สำหรับการตั้งค่าอย่างใดอย่างหนึ่งที่พวกเขาพิจารณา)

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

จากนั้นพวกเขาได้ฝึกตัวแทน AlphaTensor โดยใช้การเรียนรู้แบบเสริมกำลังเพื่อเล่นเกม โดยเริ่มต้นโดยไม่มีความรู้ใดๆ เกี่ยวกับอัลกอริธึมการคูณเมทริกซ์ที่มีอยู่ ด้วยการเรียนรู้ AlphaTensor จะค่อยๆ ดีขึ้นเมื่อเวลาผ่านไป โดยค้นพบอัลกอริธึมการคูณเมทริกซ์แบบเร็วในอดีตอีกครั้ง เช่น Strassen's ซึ่งในที่สุดก็เหนือกว่าสัญชาตญาณของมนุษย์และค้นพบอัลกอริทึมได้เร็วกว่าที่เคยรู้จัก

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

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

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

ธรรมชาติ – ค้นพบอัลกอริธึมการคูณเมทริกซ์ที่เร็วขึ้นด้วยการเรียนรู้การเสริมแรง

นามธรรม
การปรับปรุงประสิทธิภาพของอัลกอริทึมสำหรับการคำนวณพื้นฐานอาจส่งผลกระทบในวงกว้าง เนื่องจากอาจส่งผลต่อความเร็วโดยรวมของการคำนวณจำนวนมาก การคูณเมทริกซ์เป็นงานดึกดำบรรพ์ที่เกิดขึ้นในหลายระบบ ตั้งแต่โครงข่ายประสาทเทียมไปจนถึงกิจวัตรการคำนวณทางวิทยาศาสตร์ การค้นพบอัลกอริธึมโดยอัตโนมัติโดยใช้แมชชีนเลิร์นนิงมอบโอกาสในการเข้าถึงมากกว่าสัญชาตญาณของมนุษย์และให้ประสิทธิภาพเหนือกว่าอัลกอริธึมที่ออกแบบโดยมนุษย์ที่ดีที่สุดในปัจจุบัน อย่างไรก็ตาม การทำให้ขั้นตอนการค้นหาอัลกอริธึมเป็นอัตโนมัตินั้นซับซ้อน เนื่องจากพื้นที่ของอัลกอริธึมที่เป็นไปได้นั้นมีขนาดใหญ่มาก ที่นี่ เรารายงานวิธีการเรียนรู้การเสริมแรงเชิงลึกโดยใช้ AlphaZero1 สำหรับการค้นพบอัลกอริธึมที่ถูกต้องและมีประสิทธิภาพสำหรับการคูณเมทริกซ์ตามอำเภอใจ AlphaTensor ตัวแทนของเราได้รับการฝึกฝนให้เล่นเกมแบบเล่นคนเดียวโดยมีวัตถุประสงค์เพื่อค้นหาการสลายตัวของเทนเซอร์ภายในพื้นที่ปัจจัยจำกัด AlphaTensor ค้นพบอัลกอริธึมที่มีประสิทธิภาพเหนือกว่าความซับซ้อนที่ล้ำสมัยสำหรับเมทริกซ์หลายขนาด ที่เกี่ยวข้องอย่างยิ่งคือกรณีของเมทริกซ์ 4 × 4 ในฟิลด์จำกัด ซึ่งอัลกอริธึมของ AlphaTensor ปรับปรุงอัลกอริธึมสองระดับของ Strassen เป็นครั้งแรก นับตั้งแต่การค้นพบเมื่อ 50 ปีที่แล้ว2 นอกจากนี้เรายังแสดงความยืดหยุ่นของ AlphaTensor ผ่านกรณีการใช้งานต่างๆ: อัลกอริธึมที่มีความซับซ้อนล้ำสมัยสำหรับการคูณเมทริกซ์ที่มีโครงสร้างและการปรับปรุงประสิทธิภาพในทางปฏิบัติโดยการเพิ่มประสิทธิภาพการคูณเมทริกซ์สำหรับรันไทม์บนฮาร์ดแวร์เฉพาะ ผลลัพธ์ของเราเน้นย้ำความสามารถของ AlphaTensor ในการเร่งกระบวนการค้นหาอัลกอริทึมในปัญหาต่างๆ และปรับให้เหมาะสมสำหรับเกณฑ์ต่างๆ