Giới thiệu
Các nhà toán học thích một câu đố hay. Ngay cả những thứ trừu tượng như phép nhân ma trận (bảng số hai chiều) cũng có thể giống như một trò chơi khi bạn cố gắng tìm ra cách hiệu quả nhất để thực hiện. Nó giống như việc cố gắng giải một khối Rubik trong càng ít bước di chuyển càng tốt — đầy thử thách nhưng đầy lôi cuốn. Ngoại trừ khối Rubik, số lần di chuyển có thể ở mỗi bước là 18; đối với phép nhân ma trận, ngay cả trong những trường hợp tương đối đơn giản, mỗi bước có thể xuất hiện hơn 1012 tùy chọn.
Trong hơn 50 năm qua, các nhà nghiên cứu đã tiếp cận vấn đề này theo nhiều cách, tất cả đều dựa trên các tìm kiếm trên máy tính được hỗ trợ bởi trực giác của con người. Tháng trước, một nhóm tại công ty trí tuệ nhân tạo DeepMind đã chỉ ra cách giải quyết vấn đề từ một hướng mới, báo cáo trong một giấy in Thiên nhiên rằng họ đã đào tạo thành công một mạng thần kinh để khám phá các thuật toán nhanh mới cho phép nhân ma trận. Cứ như thể AI đã tìm ra một chiến lược chưa biết để giải một khối Rubik cực kỳ phức tạp.
“Đó là một kết quả rất gọn gàng,” nói Josh Alman, một nhà khoa học máy tính tại Đại học Columbia. Nhưng ông và các chuyên gia nhân ma trận khác cũng nhấn mạnh rằng sự hỗ trợ của AI như vậy sẽ bổ sung chứ không thay thế các phương pháp hiện có — ít nhất là trong thời gian tới. “Nó giống như một bằng chứng về khái niệm cho một thứ gì đó có thể trở thành một bước đột phá,” Alman nói. Kết quả đơn giản sẽ giúp các nhà nghiên cứu trong nhiệm vụ của họ.
Như để chứng minh điều đó, ba ngày sau Thiên nhiên giấy ra mắt, một cặp nhà nghiên cứu người Áo đã minh họa cách các phương pháp mới và cũ có thể bổ sung cho nhau. Họ đã sử dụng phương pháp tìm kiếm thông thường có sự trợ giúp của máy tính để nâng cao hơn nữa một trong những thuật toán mà mạng lưới thần kinh đã phát hiện ra.
Kết quả cho thấy rằng, giống như quá trình giải một khối Rubik, con đường dẫn đến các thuật toán tốt hơn sẽ đầy những khúc ngoặt.
nhân ma trận
Phép nhân ma trận là một trong những phép toán cơ bản và phổ biến nhất trong toán học. Để nhân một cặp n-bởi-n ma trận, mỗi ma trận có n2 các phần tử, bạn nhân và cộng các phần tử này lại với nhau theo các kết hợp cụ thể để tạo ra sản phẩm, một phần ba n-bởi-n ma trận. Công thức chuẩn để nhân hai n-bởi-n ma trận yêu cầu n3 các phép nhân, do đó, một ma trận 2 nhân 2, chẳng hạn, yêu cầu tám phép nhân.
Đối với các ma trận lớn hơn, với hàng nghìn hàng và cột, quy trình này nhanh chóng trở nên cồng kềnh. Nhưng vào năm 1969, nhà toán học Volker Strassen phát hiện ra một thủ tục để nhân một cặp ma trận 2 nhân 2 bằng cách sử dụng bảy bước nhân thay vì tám, với chi phí đưa ra nhiều bước cộng hơn.
Thuật toán Strassen phức tạp không cần thiết nếu bạn chỉ muốn nhân một cặp ma trận 2 nhân 2. Nhưng anh ấy nhận ra rằng nó cũng sẽ hoạt động với các ma trận lớn hơn. Đó là vì bản thân các phần tử của ma trận có thể là ma trận. Ví dụ: một ma trận có 20,000 hàng và 20,000 cột có thể được mô phỏng lại dưới dạng ma trận 2 nhân 2 có bốn phần tử là mỗi ma trận 10,000 x 10,000. Sau đó, mỗi ma trận này có thể được chia nhỏ thành bốn khối 5,000 x 5,000, v.v. Strassen có thể áp dụng phương pháp của mình để nhân ma trận 2 nhân 2 ở mỗi cấp của hệ thống phân cấp lồng nhau này. Khi kích thước ma trận tăng lên, khoản tiết kiệm được từ ít phép nhân hơn sẽ tăng lên.
Khám phá của Strassen đã dẫn đến việc tìm kiếm các thuật toán hiệu quả cho phép nhân ma trận, từ đó đã truyền cảm hứng cho hai trường con riêng biệt. Người ta tập trung vào một câu hỏi về nguyên tắc: Nếu bạn tưởng tượng nhân hai n-bởi-n ma trận và để cho n chạy về phía vô cùng, làm thế nào để số bước nhân trong thuật toán nhanh nhất có thể quy mô với n? Các kỷ lục hiện tại để có tỷ lệ tốt nhất, n2.3728596, thuộc về Alman và Virginia Vassilevska Williams, một nhà khoa học máy tính tại Viện Công nghệ Massachusetts. (Một tài liệu chưa xuất bản gần đây in sẵn đã báo cáo một cải tiến nhỏ bằng cách sử dụng một kỹ thuật mới.) Nhưng các thuật toán này hoàn toàn có lợi ích về mặt lý thuyết, chiến thắng các phương pháp như của Strassen chỉ dành cho các ma trận lớn một cách vô lý.
Trường con thứ hai nghĩ ở quy mô nhỏ hơn. Ngay sau công trình của Strassen, nhà khoa học máy tính người Mỹ gốc Israel Shmuel Winograd cho thấy rằng Strassen đã đạt đến một giới hạn lý thuyết: Không thể nhân ma trận 2 nhân 2 với ít hơn bảy bước nhân. Nhưng đối với tất cả các kích thước ma trận khác, số phép nhân tối thiểu cần thiết vẫn là một câu hỏi mở. Và các thuật toán nhanh cho các ma trận nhỏ có thể có tác động lớn, vì các lần lặp lại lặp đi lặp lại của một thuật toán như vậy có thể đánh bại thuật toán của Strassen khi các ma trận có kích thước hợp lý được nhân lên.
Thật không may, số lượng khả năng tuyệt đối là rất lớn. Ngay cả đối với ma trận 3 nhân 3, “số lượng thuật toán có thể vượt quá số lượng nguyên tử trong vũ trụ,” cho biết Alhussein Fawzi, một nhà nghiên cứu DeepMind và là một trong những người lãnh đạo công việc mới.
Đối mặt với menu tùy chọn chóng mặt này, các nhà nghiên cứu đã đạt được tiến bộ bằng cách biến phép nhân ma trận thành một bài toán có vẻ như hoàn toàn khác — một bài toán dễ xử lý hơn cho máy tính. Có thể biểu diễn nhiệm vụ trừu tượng nhân hai ma trận dưới dạng một loại đối tượng toán học cụ thể: một mảng ba chiều các số được gọi là tenxơ. Sau đó, các nhà nghiên cứu có thể chia tenxơ này thành một tổng các thành phần cơ bản, được gọi là tenxơ “hạng 1”; mỗi trong số này sẽ đại diện cho một bước khác nhau trong thuật toán nhân ma trận tương ứng. Điều đó có nghĩa là việc tìm kiếm một thuật toán nhân hiệu quả tương đương với việc giảm thiểu số lượng số hạng trong phép phân tách tensor — càng ít số hạng, càng ít bước liên quan.
Bằng cách này, các nhà nghiên cứu đã khám phá ra những điều mới thuật toán mà nhân lên n-bởi-n ma trận sử dụng ít hơn tiêu chuẩn n3 các bước nhân cho nhiều cỡ ma trận nhỏ. Nhưng các thuật toán vượt trội không chỉ tiêu chuẩn mà còn cả thuật toán Strassen cho các ma trận nhỏ vẫn nằm ngoài tầm với — cho đến tận bây giờ.
Game On
Nhóm DeepMind đã tiếp cận vấn đề bằng cách biến phân tách tensor thành trò chơi một người chơi. Họ bắt đầu với một thuật toán học sâu có nguồn gốc từ AlphaGo — một AI khác của DeepMind vào năm 2016 học chơi cờ vây đủ tốt để đánh bại những người chơi hàng đầu của con người.
Tất cả các thuật toán học sâu đều được xây dựng xung quanh mạng nơ-ron: mạng nơ-ron nhân tạo được sắp xếp thành các lớp, với các kết nối có thể khác nhau về cường độ thể hiện mức độ ảnh hưởng của mỗi nơ-ron đến các nơ-ron ở lớp tiếp theo. Sức mạnh của các kết nối này được điều chỉnh qua nhiều lần lặp lại quy trình đào tạo, trong đó mạng nơ-ron học cách biến đổi từng đầu vào mà nó nhận được thành đầu ra giúp thuật toán hoàn thành mục tiêu tổng thể của nó.
Trong thuật toán mới của DeepMind, được đặt tên là AlphaTensor, các đầu vào đại diện cho các bước trên đường đi đến sơ đồ nhân ma trận hợp lệ. Đầu vào đầu tiên của mạng nơ-ron là tensor nhân ma trận ban đầu và đầu ra của nó là tensor hạng 1 mà AlphaTensor đã chọn cho lần di chuyển đầu tiên. Thuật toán trừ tenxơ hạng 1 này khỏi đầu vào ban đầu, tạo ra một tenxơ cập nhật được đưa trở lại mạng dưới dạng đầu vào mới. Quá trình lặp lại cho đến khi cuối cùng mọi phần tử trong tenxơ bắt đầu được giảm xuống 1, nghĩa là không còn tenxơ hạng XNUMX nào nữa để lấy ra.
Tại thời điểm đó, mạng nơ-ron đã phát hiện ra một phân tích tensor hợp lệ, vì nó được đảm bảo về mặt toán học rằng tổng của tất cả các tensor hạng 1 chính xác bằng tensor bắt đầu. Và các bước cần thực hiện để đạt được điều đó có thể được dịch ngược lại thành các bước của thuật toán nhân ma trận tương ứng.
Đây là trò chơi: AlphaTensor liên tục phân tách một tensor thành một tập hợp các thành phần hạng 1. Mỗi lần, AlphaTensor nhận được phần thưởng nếu tìm ra cách giảm số bước. Nhưng những con đường tắt dẫn đến chiến thắng không hề trực quan chút nào, giống như đôi khi bạn phải tranh giành một mặt được sắp xếp hoàn hảo trên Khối Rubik trước khi bạn có thể giải được toàn bộ.
Nhóm hiện đã có một thuật toán, về mặt lý thuyết, có thể giải quyết vấn đề của họ. Họ chỉ cần đào tạo nó đầu tiên.
Đường dẫn mới
Giống như tất cả các mạng thần kinh, AlphaTensor cần rất nhiều dữ liệu để huấn luyện, nhưng phân rã tensor là một vấn đề nổi tiếng khó khăn. Có một vài ví dụ về sự phân tách hiệu quả mà các nhà nghiên cứu có thể cung cấp cho mạng. Thay vào đó, họ đã giúp thuật toán bắt đầu bằng cách đào tạo nó về bài toán nghịch đảo dễ dàng hơn nhiều: cộng một loạt các tenxơ hạng 1 được tạo ngẫu nhiên.
“Họ đang sử dụng bài toán dễ để tạo ra nhiều dữ liệu hơn cho bài toán khó,” nói Michael Littman, một nhà khoa học máy tính tại Đại học Brown. Kết hợp quy trình đào tạo ngược này với học tăng cường, trong đó AlphaTensor tạo ra dữ liệu đào tạo của chính nó khi nó loay hoay tìm kiếm các phân tách hiệu quả, hoạt động tốt hơn nhiều so với phương pháp đào tạo của chính nó.
Nhóm DeepMind đã đào tạo AlphaTensor để phân tách các tenxơ đại diện cho phép nhân của ma trận lên đến 12 x 12. Nó tìm kiếm các thuật toán nhanh để nhân các ma trận của các số thực thông thường và cả các thuật toán dành riêng cho một cài đặt hạn chế hơn được gọi là số học modulo 2. (Đây là phép toán chỉ dựa trên hai số, vì vậy các phần tử của ma trận chỉ có thể là 0 hoặc 1 và 1 + 1 = 0.) Các nhà nghiên cứu thường bắt đầu với không gian hạn chế hơn nhưng vẫn rộng lớn này, với hy vọng rằng các thuật toán được khám phá ở đây có thể được điều chỉnh cho phù hợp làm việc trên ma trận của các số thực.
Sau khi đào tạo, AlphaTensor đã khám phá lại thuật toán của Strassen trong vòng vài phút. Sau đó, nó đã phát hiện ra hàng nghìn thuật toán nhanh mới cho mỗi kích thước ma trận. Chúng khác với các thuật toán nổi tiếng nhất nhưng có cùng số bước nhân.
Trong một số trường hợp, AlphaTensor thậm chí còn đánh bại các kỷ lục hiện có. Những khám phá đáng ngạc nhiên nhất của nó đã xảy ra trong số học modulo 2, nơi nó tìm thấy một thuật toán mới để nhân ma trận 4 nhân 4 trong 47 bước nhân, một cải tiến so với 49 bước cần thiết cho hai lần lặp lại thuật toán Strassen. Nó cũng đánh bại thuật toán nổi tiếng nhất cho ma trận 5 nhân 5 modulo 2, giảm số phép nhân cần thiết từ kỷ lục trước đó là 98 xuống còn 96. (Nhưng kỷ lục mới này vẫn chậm hơn 91 bước cần thiết để đánh bại Thuật toán Strassen sử dụng ma trận 5 nhân 5.)
Kết quả cao mới đã tạo ra rất nhiều phấn khích, với một số nhà nghiên cứu hết lời khen ngợi về sự cải tiến dựa trên AI trên hiện trạng. Nhưng không phải tất cả mọi người trong cộng đồng phép nhân ma trận đều ấn tượng như vậy. Vassilevska Williams nói: “Tôi cảm thấy nó hơi bị cường điệu hóa. “Đó là một công cụ khác. Nó không giống như, 'Ồ, máy tính đánh bại con người', bạn biết không?
Các nhà nghiên cứu cũng nhấn mạnh rằng các ứng dụng ngay lập tức của thuật toán phá kỷ lục 4 nhân 4 sẽ bị hạn chế: Nó không chỉ có giá trị trong số học modulo 2, mà trong cuộc sống thực, bên cạnh tốc độ, còn có những cân nhắc quan trọng khác.
Fawzi đồng ý rằng thực sự, đây mới chỉ là khởi đầu. “Có rất nhiều cơ hội để cải tiến và nghiên cứu, và đó là một điều tốt,” ông nói.
Một bước ngoặt cuối cùng
Điểm mạnh nhất của AlphaTensor so với các phương pháp tìm kiếm trên máy tính lâu đời cũng là điểm yếu lớn nhất của nó: Nó không bị hạn chế bởi trực giác của con người về hình thức của các thuật toán tốt, vì vậy nó không thể giải thích các lựa chọn của mình. Điều đó gây khó khăn cho các nhà nghiên cứu để học hỏi từ những thành tựu của nó.
Nhưng điều này có thể không phải là một nhược điểm lớn như nó có vẻ. Vài ngày sau kết quả AlphaTensor, nhà toán học Manuel Kauers và sinh viên tốt nghiệp của mình Jakob Moosbauer, cả hai thuộc Đại học Johannes Kepler Linz ở Áo, đã báo cáo một bước tiến khác.
Giới thiệu
Khi bài báo DeepMind ra mắt, Kauers và Moosbauer đang trong quá trình tìm kiếm các thuật toán nhân mới bằng cách sử dụng tìm kiếm thông thường có sự trợ giúp của máy tính. Nhưng không giống như hầu hết các tìm kiếm như vậy, bắt đầu lại từ đầu với một nguyên tắc hướng dẫn mới, phương pháp của họ hoạt động bằng cách liên tục điều chỉnh một thuật toán hiện có với hy vọng tiết kiệm được nhiều phép nhân hơn từ nó. Lấy thuật toán của AlphaTensor cho ma trận 5 nhân 5 modulo 2 làm điểm bắt đầu, họ ngạc nhiên khi thấy rằng phương pháp của họ đã giảm số bước nhân từ 96 xuống 95 chỉ sau vài giây tính toán.
AlphaTensor cũng gián tiếp giúp họ thực hiện một cải tiến khác. Trước đây, Kauers và Moosbauer đã không quan tâm đến việc khám phá không gian của ma trận 4 nhân 4, tin rằng sẽ không thể vượt qua hai lần lặp lại của thuật toán Strassen. Kết quả AlphaTensor đã khiến họ phải xem xét lại và sau một tuần thời gian tính toán bắt đầu lại từ đầu, phương pháp của họ đã tạo ra một thuật toán 47 bước khác không liên quan đến thuật toán mà AlphaTensor đã phát hiện ra. Kauers nói: “Nếu ai đó nói với chúng tôi rằng có điều gì đó để khám phá cho 4 nhân 4, thì chúng tôi đã có thể làm điều đó sớm hơn. “Nhưng OK, đó là cách nó hoạt động.”
Littman mong đợi nhiều điều bất ngờ như vậy hơn, ví tình huống này giống như lần đầu tiên một người chạy hoàn thành một dặm trong vòng chưa đầy bốn phút, một kỳ tích từng được coi là không thể. “Mọi người nói, 'Ồ, đợi đã, chúng ta có thể làm được điều này', và bây giờ rất nhiều người có thể làm được,” anh nói.
Trong tương lai, Fawzi hy vọng sẽ khái quát hóa AlphaTensor để giải quyết nhiều nhiệm vụ toán học và tính toán hơn, giống như tổ tiên AlphaGo của nó cuối cùng đã phân nhánh sang các trò chơi khác.
Kauers coi đây là phép thử thực sự cho việc áp dụng máy học để khám phá các thuật toán mới. Ông chỉ ra rằng việc tìm kiếm các thuật toán nhân ma trận nhanh là một bài toán tổ hợp mà máy tính tìm kiếm, có hoặc không có sự trợ giúp của con người, đều phù hợp. Nhưng không phải tất cả các vấn đề toán học đều dễ dàng xác định. Anh ấy nói, nếu máy học có thể khám phá ra một ý tưởng thuật toán mới về chất lượng, thì “thì đây sẽ là một yếu tố thay đổi cuộc chơi.”
