Deep Mind AlphaTensor sẽ khám phá các thuật toán mới

Deep Mind đã mở rộng AlphaZero sang toán học để mở ra những khả năng mới cho các thuật toán nghiên cứu.

AlphaTensor, được xây dựng dựa trên AlphaZero, một đặc vụ đã thể hiện thành tích siêu phàm trên các trò chơi cờ, như cờ vua, cờ vây và cờ shogi, và tác phẩm này cho thấy hành trình của AlphaZero từ khi chơi trò chơi đến lần đầu tiên giải các bài toán chưa giải được.

Người Ai Cập cổ đại đã tạo ra một thuật toán để nhân hai số mà không cần bảng nhân, và nhà toán học Hy Lạp Euclid đã mô tả một thuật toán để tính ước số chung lớn nhất vẫn còn được sử dụng cho đến ngày nay.

Trong Thời kỳ hoàng kim của đạo Hồi, nhà toán học người Ba Tư Muhammad ibn Musa al-Khwarizmi đã thiết kế các thuật toán mới để giải các phương trình tuyến tính và bậc hai. Trên thực tế, tên của al-Khwarizmi, được dịch sang tiếng Latinh là Algoritmi, đã dẫn đến thuật ngữ thuật toán. Tuy nhiên, bất chấp sự quen thuộc với các thuật toán ngày nay – được sử dụng trong toàn xã hội từ đại số trong lớp học đến nghiên cứu khoa học tiên tiến – quá trình khám phá các thuật toán mới là vô cùng khó khăn và là một ví dụ về khả năng suy luận đáng kinh ngạc của trí óc con người.

Họ đã xuất bản trên tạp chí Nature. AlphaTensor là hệ thống trí tuệ nhân tạo (AI) đầu tiên khám phá các thuật toán mới, hiệu quả và có thể chứng minh là đúng cho các tác vụ cơ bản như phép nhân ma trận. Điều này làm sáng tỏ một câu hỏi mở đã tồn tại 50 năm trong toán học về việc tìm ra cách nhanh nhất để nhân hai ma trận.

Được đào tạo từ đầu, AlphaTensor khám phá ra các thuật toán nhân ma trận hiệu quả hơn các thuật toán hiện có do con người và máy tính thiết kế. Mặc dù đã cải thiện các thuật toán đã biết, nhưng họ lưu ý rằng hạn chế của AlphaTensor là nhu cầu xác định trước một tập hợp các mục nhập hệ số tiềm năng F, điều này làm rời rạc hóa không gian tìm kiếm nhưng có thể dẫn đến bỏ lỡ các thuật toán hiệu quả. Một hướng thú vị cho nghiên cứu trong tương lai là điều chỉnh AlphaTensor để tìm kiếm F. Một điểm mạnh quan trọng của AlphaTensor là tính linh hoạt của nó để hỗ trợ các phần thưởng ngẫu nhiên và không thể phân biệt phức tạp (từ thứ hạng tensor đến hiệu quả thực tế trên phần cứng cụ thể), ngoài việc tìm kiếm các thuật toán cho các hoạt động tùy chỉnh trong nhiều không gian khác nhau (chẳng hạn như các trường hữu hạn). Họ tin rằng điều này sẽ thúc đẩy các ứng dụng của AlphaTensor theo hướng thiết kế các thuật toán tối ưu hóa các số liệu mà chúng tôi không xem xét ở đây, chẳng hạn như độ ổn định số hoặc mức sử dụng năng lượng.

Việc khám phá ra các thuật toán nhân ma trận có ý nghĩa sâu rộng, vì phép nhân ma trận nằm ở cốt lõi của nhiều tác vụ tính toán, chẳng hạn như nghịch đảo ma trận, tính toán định thức và giải các hệ thống tuyến tính.

Quá trình và tiến trình tự động hóa khám phá thuật toán
Đầu tiên, họ biến bài toán tìm thuật toán hiệu quả để nhân ma trận thành một trò chơi một người chơi. Trong trò chơi này, bàn cờ là một tensor ba chiều (mảng số), cho biết thuật toán hiện tại còn sai bao nhiêu. Thông qua một tập hợp các bước di chuyển được phép, tương ứng với các hướng dẫn của thuật toán, người chơi cố gắng sửa đổi tensor và loại bỏ các mục nhập của nó. Khi người chơi quản lý để làm như vậy, điều này dẫn đến một thuật toán nhân ma trận chính xác có thể chứng minh được cho bất kỳ cặp ma trận nào và hiệu quả của nó được nắm bắt bằng số bước được thực hiện để loại bỏ tenxơ.

Trò chơi này vô cùng thách thức – số lượng các thuật toán có thể xem xét lớn hơn nhiều so với số lượng nguyên tử trong vũ trụ, ngay cả đối với các trường hợp nhân ma trận nhỏ. So với trò chơi cờ vây, trò chơi vẫn là một thách thức đối với AI trong nhiều thập kỷ, số lượng nước đi có thể có ở mỗi bước trong trò chơi của họ lớn hơn 30 bậc độ lớn (trên 10^33 đối với một trong các cài đặt mà họ xem xét).

Về cơ bản, để chơi tốt trò chơi này, người ta cần xác định được những chiếc kim nhỏ nhất trong một đống cỏ khô khổng lồ của các khả năng. Để giải quyết những thách thức của miền này, vốn khác hẳn với các trò chơi truyền thống, chúng tôi đã phát triển nhiều thành phần quan trọng bao gồm một kiến ​​trúc mạng nơ-ron mới kết hợp các thành kiến ​​quy nạp cụ thể cho từng vấn đề, một quy trình để tạo ra dữ liệu tổng hợp hữu ích và một công thức để tận dụng tính đối xứng của vấn đề.

Sau đó, họ đào tạo một tác nhân AlphaTensor bằng cách sử dụng phương pháp học tăng cường để chơi trò chơi, bắt đầu mà không cần biết gì về các thuật toán nhân ma trận hiện có. Thông qua quá trình học hỏi, AlphaTensor dần dần cải thiện theo thời gian, khám phá lại các thuật toán nhân ma trận nhanh trong lịch sử như của Strassen, cuối cùng vượt qua lĩnh vực trực giác của con người và khám phá ra các thuật toán nhanh hơn những gì đã biết trước đây.

Khám phá tác động đến các nghiên cứu và ứng dụng trong tương lai
Từ quan điểm toán học, kết quả của họ có thể hướng dẫn nghiên cứu sâu hơn về lý thuyết độ phức tạp, nhằm mục đích xác định các thuật toán nhanh nhất để giải các bài toán tính toán. Bằng cách khám phá không gian của các thuật toán khả thi theo cách hiệu quả hơn so với các phương pháp trước đây, AlphaTensor giúp nâng cao hiểu biết của chúng ta về sự phong phú của các thuật toán nhân ma trận. Hiểu không gian này có thể mở khóa các kết quả mới để giúp xác định độ phức tạp tiệm cận của phép nhân ma trận, một trong những vấn đề mở cơ bản nhất trong khoa học máy tính.

Vì phép nhân ma trận là thành phần cốt lõi trong nhiều tác vụ tính toán, bao gồm đồ họa máy tính, truyền thông kỹ thuật số, đào tạo mạng nơ-ron và tính toán khoa học, các thuật toán do AlphaTensor phát hiện có thể làm cho các phép tính trong các lĩnh vực này hiệu quả hơn đáng kể. Tính linh hoạt của AlphaTensor trong việc xem xét bất kỳ loại mục tiêu nào cũng có thể thúc đẩy các ứng dụng mới để thiết kế các thuật toán tối ưu hóa các số liệu như sử dụng năng lượng và độ ổn định số, giúp ngăn ngừa các lỗi làm tròn nhỏ do lăn cầu tuyết khi thuật toán hoạt động.

Mặc dù ở đây họ tập trung vào vấn đề cụ thể là phép nhân ma trận, chúng tôi hy vọng rằng bài báo của chúng tôi sẽ truyền cảm hứng cho những người khác trong việc sử dụng AI để hướng dẫn khám phá thuật toán cho các nhiệm vụ tính toán cơ bản khác. Nghiên cứu của họ cũng chỉ ra rằng AlphaZero là một thuật toán mạnh mẽ có thể được mở rộng vượt ra ngoài lĩnh vực trò chơi truyền thống để giúp giải các bài toán mở trong toán học. Dựa trên nghiên cứu của chúng tôi, họ hy vọng sẽ thúc đẩy khối lượng công việc lớn hơn – áp dụng AI để giúp xã hội giải quyết một số thách thức quan trọng nhất trong toán học và các ngành khoa học.

Nature – Khám phá thuật toán nhân ma trận nhanh hơn với học tăng cường

Tóm tắt
Cải thiện hiệu quả của các thuật toán cho các tính toán cơ bản có thể có tác động rộng rãi, vì nó có thể ảnh hưởng đến tốc độ tổng thể của một lượng lớn các phép tính. Phép nhân ma trận là một trong những nhiệm vụ cơ bản như vậy, xảy ra trong nhiều hệ thống—từ mạng thần kinh đến quy trình tính toán khoa học. Việc tự động khám phá các thuật toán bằng cách sử dụng máy học mang lại triển vọng vượt ra ngoài trực giác của con người và vượt trội so với các thuật toán do con người thiết kế tốt nhất hiện nay. Tuy nhiên, việc tự động hóa quy trình khám phá thuật toán rất phức tạp vì không gian của các thuật toán khả thi là rất lớn. Ở đây chúng tôi báo cáo một phương pháp học tăng cường sâu dựa trên AlphaZero1 để khám phá các thuật toán hiệu quả và có thể chứng minh là đúng cho phép nhân các ma trận tùy ý. Đặc vụ của chúng tôi, AlphaTensor, được đào tạo để chơi trò chơi một người chơi trong đó mục tiêu là tìm các phép phân tách tensor trong một không gian thừa số hữu hạn. AlphaTensor đã phát hiện ra các thuật toán vượt trội so với độ phức tạp tối tân đối với nhiều kích thước ma trận. Đặc biệt có liên quan là trường hợp ma trận 4 × 4 trong một trường hữu hạn, trong đó thuật toán của AlphaTensor lần đầu tiên cải thiện thuật toán hai cấp của Strassen, theo hiểu biết của chúng tôi, kể từ khi phát hiện ra nó 50 năm trước2. Chúng tôi tiếp tục giới thiệu tính linh hoạt của AlphaTensor thông qua các trường hợp sử dụng khác nhau: thuật toán với độ phức tạp hiện đại nhất dành cho phép nhân ma trận có cấu trúc và cải thiện hiệu quả thực tế bằng cách tối ưu hóa phép nhân ma trận cho thời gian chạy trên phần cứng cụ thể. Kết quả của chúng tôi làm nổi bật khả năng của AlphaTensor trong việc đẩy nhanh quá trình khám phá thuật toán trên một loạt vấn đề và để tối ưu hóa cho các tiêu chí khác nhau.