FunSearch: Khám phá mới trong toán học và khoa học bằng LLM
(deepmind.google)- FunSearch của Google DeepMind kết hợp LLM được huấn luyện trước với bộ đánh giá tự động để tìm kiếm các lời giải mới có thể kiểm chứng cho các bài toán toán học và khoa học máy tính dưới dạng mã
- LLM tạo chương trình mới, bộ đánh giá tự động chấm điểm, rồi các chương trình có điểm cao được đưa lại vào pool, cải thiện lời giải thông qua quá trình lặp tiến hóa
- Với cap set problem, FunSearch đã tìm được cap set lớn nhất từng được phát hiện trong một số thiết lập, đồng thời cho thấy hiệu năng ở cả những quy mô mà các solver tính toán tối tân hiện có khó xử lý
- Cách tiếp cận tương tự cũng được áp dụng cho online bin packing, trong đó các chương trình được điều chỉnh theo đặc tính dữ liệu đã xếp cùng số lượng item vào ít bin hơn so với các heuristic hiện có
- Vì kết quả là các chương trình ngắn mà con người có thể đọc được, nhà nghiên cứu có thể xem xét cấu trúc lời giải và dùng chúng cho hợp tác người-AI nhằm cải thiện cách đặt bài toán
Ý tưởng cơ bản của FunSearch
- FunSearch tìm kiếm các hàm được viết bằng mã máy tính để tìm lời giải mới trong toán học và khoa học máy tính
- Tên gọi xuất phát từ việc nó tìm kiếm hàm (function)
- Vì LLM có thể tạo ra thông tin sai sự thật, FunSearch kết hợp LLM đưa ra đề xuất sáng tạo với bộ đánh giá (evaluator) tự động để lọc bỏ các ý tưởng sai
- Đây là một trong những trường hợp đầu tiên dùng LLM để tạo ra khám phá mới trong các bài toán mở khó của khoa học và toán học
Cấu trúc lặp tiến hóa
- Trước tiên, người dùng viết mô tả bài toán dưới dạng mã
- Bao gồm quy trình đánh giá chương trình
- Đồng thời có chương trình seed để khởi tạo pool chương trình
- Ở mỗi vòng lặp, một phần pool chương trình hiện tại được đưa vào LLM
- LLM tạo chương trình mới dựa trên các chương trình hiện có
- Chương trình mới được tự động chạy và đánh giá
- Chương trình có điểm cao được thêm lại vào cơ sở dữ liệu chương trình
- Người dùng có thể lấy chương trình đạt điểm cao nhất đã được tìm thấy bất cứ lúc nào
- FunSearch sử dụng Google PaLM 2, nhưng cũng tương thích với các LLM khác đã được huấn luyện trên mã
- Cấu trúc tìm kiếm cũng được tăng cường để xử lý các bài toán tổ hợp khó
- Bắt đầu từ kiến thức chung về bài toán và tập trung vào các ý tưởng cốt lõi cần cho khám phá mới
- Tăng tính đa dạng của ý tưởng để tránh đình trệ
- Chạy song song quá trình tiến hóa để nâng cao hiệu quả
Kết quả với cap set problem
- Đối tượng áp dụng đầu tiên là cap set problem, bài toán đã làm đau đầu các nhà toán học trong nhiều lĩnh vực nghiên cứu suốt nhiều thập kỷ
- Bài toán này yêu cầu tìm kích thước tối đa của một tập điểm trong lưới nhiều chiều sao cho không có ba điểm nào nằm trên cùng một đường thẳng, tức một cap set
- Nó cũng đóng vai trò mô hình cho các bài toán khác trong tổ hợp cực trị (extremal combinatorics)
- Vì số trường hợp khả dĩ nhanh chóng vượt quá số nguyên tử trong vũ trụ, tính toán brute-force không khả thi
- FunSearch tạo ra các lời giải dưới dạng chương trình và đã tìm được cap set lớn nhất từng được phát hiện trong một số thiết lập
- Kết quả này là mức tăng lớn nhất về kích thước cap set trong 20 năm qua, đồng thời cho hiệu năng tốt hơn ngay cả ở vùng quy mô bài toán vượt quá khả năng hiện tại của các solver tính toán tối tân hiện có
- Điều này cho thấy có thể vượt qua các kết quả hiện có trong những bài toán tổ hợp khó xây dựng trực giác, và có tiềm năng mở rộng sang các bài toán lý thuyết tổ hợp tương tự cũng như các lĩnh vực như lý thuyết truyền thông
Các chương trình ngắn mà con người có thể diễn giải
- FunSearch không phải là hộp đen chỉ xuất ra danh sách đáp án, mà tạo ra chương trình cho thấy lời giải được cấu thành như thế nào
- Điều này cũng phù hợp với cách làm phổ biến trong khoa học: giải thích các khám phá hoặc hiện tượng mới thông qua quá trình tạo ra chúng
- FunSearch ưu tiên các lời giải được biểu diễn bằng chương trình súc tích có Kolmogorov complexity thấp
- Kolmogorov complexity là độ dài của chương trình máy tính ngắn nhất có thể xuất ra lời giải
- Chương trình ngắn có thể mô tả các đối tượng rất lớn, giúp mở rộng sang các bài toán quy mô lớn kiểu tìm kim đáy bể
- Đầu ra chương trình dễ để nhà nghiên cứu hiểu
- Ở một số mã đầu ra đạt điểm cao, người ta quan sát thấy tính đối xứng thú vị; dựa vào đó, họ tinh chỉnh cách đặt bài toán để thu được lời giải tốt hơn
- Jordan Ellenberg nói rằng FunSearch cung cấp “một cơ chế hoàn toàn mới để phát triển chiến lược tấn công”, và các lời giải được tạo ra phong phú hơn nhiều về mặt khái niệm so với danh sách các con số
Ứng dụng cho online bin packing
- FunSearch cũng được áp dụng cho bin packing, một bài toán khoa học máy tính thực tiễn
- Bin packing là bài toán xếp các item có kích thước khác nhau vào số bin ít nhất có thể
- Ví dụ ứng dụng thực tế gồm xếp hàng vào container, phân bổ tác vụ tính toán trong trung tâm dữ liệu để giảm chi phí
- Online bin packing thường được xử lý bằng các heuristic dựa trên kinh nghiệm của con người
- Có thể khó tìm được bộ quy tắc cho từng tình huống cụ thể với kích thước, thời điểm và dung lượng khác nhau
- Dù rất khác cap set problem, FunSearch vẫn được thiết lập dễ dàng cho bài toán này và tạo ra các chương trình tự động điều chỉnh theo đặc tính dữ liệu
- Các chương trình được tạo ra xếp cùng số lượng item vào ít bin hơn so với các heuristic hiện có
- Các cách tiếp cận AI khác như mạng nơ-ron hoặc học tăng cường cũng có thể hiệu quả với các bài toán tổ hợp khó, nhưng có thể cần tài nguyên đáng kể để triển khai
- Vì FunSearch xuất ra mã dễ kiểm tra và triển khai, nó có thể tạo ra những lời giải ở dạng có thể đưa vào nhiều hệ thống công nghiệp thực tế
Cập nhật và mở rộng năm 2024
- Báo cáo arXiv công bố tháng 12/2024 cho thấy phương pháp FunSearch có thể được dùng để khuếch đại năng lực con người trong lập trình thi đấu tổ hợp
- Các cuộc thi lập trình truyền thống như Codeforces yêu cầu lời giải hoàn chỉnh cho các bài toán thuật toán cổ điển trong giới hạn thời gian và bộ nhớ
- Các cuộc thi tổ hợp xử lý những bài toán phức tạp, trong đó cần tìm lời giải xấp xỉ tốt nhất có thể thay vì một đáp án đúng duy nhất
- Phương pháp này có thể tạo ra lời giải tốt hơn lời giải do các thí sinh thuộc nhóm phần trăm cao nhất tìm được
- Nó sử dụng cấu trúc hợp tác trong đó lập trình viên con người viết backbone của mã lời giải, còn LLM tiến hóa một cách sáng tạo hàm điều khiển backbone đó
- Khi LLM phổ thông được cải thiện, không còn cần mô hình chuyên biệt cho mã, và có thể dùng Gemini 1.5 Flash làm nền tảng
- Ngoài lập trình thi đấu, FunSearch còn được dùng để tìm cách tối ưu hóa hàm tốt hơn trong framework Bayesian optimization
Hướng đi của khám phá dựa trên LLM
- FunSearch cho thấy nếu có cơ chế ngăn ảo giác của LLM, LLM có thể được dùng không chỉ cho các khám phá toán học mới mà còn để tạo ra các lời giải tiềm năng cho những vấn đề thực tế quan trọng
- Với các vấn đề lâu đời hoặc mới trong khoa học và công nghiệp, việc tạo ra các thuật toán hiệu quả và được tùy biến bằng các phương pháp dựa trên LLM có thể trở nên phổ biến
- FunSearch có thể được cải thiện cùng với tiến bộ chung của LLM, và dự kiến sẽ mở rộng năng lực sang nhiều bài toán khoa học và kỹ thuật khác nhau
1 bình luận
Ý kiến Hacker News
Tôi tò mò LLM cần thiết đến mức nào ở đây
Nhìn qua thì có vẻ vai trò của LLM là tạo ra thứ gì đó hợp lý, giống như một hàm Python tuân theo type signature đã cho
Nhưng có vẻ ngay cả khi không có LLM, ta vẫn nên có thể tạo ra các hàm Python ngẫu nhiên nhưng hợp lệ, thỏa mãn type signature đã cho. Về cơ bản đây cũng là một bài tập như [1], chỉ là trên một ngôn ngữ phức tạp hơn nhiều, và có thể một ngôn ngữ bị giới hạn sẽ dễ dùng hơn. Tôi cũng tự hỏi liệu cách như PushGP [2] có khả thi không
Câu hỏi là (1) giá trị gia tăng của LLM ở đây là gì, nó có giảm mạnh số lần đánh giá cần thiết để hội tụ hay không, và nếu có thì giảm bằng cách nào, (2) với cùng bài toán thì các kỹ thuật genetic programming khác có kém cạnh tranh hơn không và có tạo ra lời giải có độ thích nghi thấp hơn không, (3) nếu genetic programming truyền thống cũng đạt được mức độ thích nghi tương tự thì có khác biệt gì về chi phí tính toán khi tính cả chi phí huấn luyện LLM hay không
[1] http://www.davidmontana.net/papers/stgp.pdf
[2] https://faculty.hampshire.edu/lspector/push.html
Chỉ khỉ và máy đánh chữ là chưa đủ, và lý do dùng Palm2 ở đây là vì các ứng viên không phải ngẫu nhiên mà phải có vẻ hợp lý. Mục tiêu là không lãng phí thời gian vào những chương trình vô nghĩa
Hơn nữa, thuật toán di truyền dựa trên sinh chương trình ngẫu nhiên gặp vấn đề cold start rất lớn. Nếu mọi ứng viên đều có độ thích nghi bằng 0 thì ở giai đoạn đầu, và có lẽ cả đến cuối, nhiều khả năng sẽ không có tiến triển nào
Tôi không quá rành về thuật toán di truyền, nhưng ở mức này thì có vẻ không phải là thứ mà thuật toán di truyền không thể tìm ra. Dù vậy, tôi sẽ khá ngạc nhiên nếu có ai thực sự đã thử nhiều đến thế
Mặt khác, như có thể thấy ở phụ lục A.2 của bài báo, cách tiếp cận di truyền không dùng LLM có vẻ sẽ cần thiết kế thủ công nhiều hơn so với cách tiếp cận dùng LLM
Khác biệt mà LLM tạo ra ở đây là nó giới hạn không gian biến đổi khả dĩ chủ yếu vào các chương trình có vẻ hợp lý về mặt ngữ nghĩa
Về ý 3, một LLM đã được huấn luyện có ích cho rất nhiều mục đích nên nếu khấu hao cả chi phí huấn luyện ban đầu thì cũng không quá lớn. Có thể có thêm chi phí fine-tune để khớp với framework FunSearch, nhưng chi phí fine-tune khá nhỏ. Trong framework này, dùng nó có khả năng vẫn lợi hơn so với chỉ dùng genetic programming
LLM giúp thu hẹp đáng kể không gian tìm kiếm, dù tất nhiên nhiều khi thu hẹp sai, nhưng sau đó có thể áp dụng tổng hợp chương trình quy nạp để tinh chỉnh và kiểm thử. Theo hiểu biết hiện tại của tôi, không có LLM thì cách này là bất khả thi. Vì ngay cả với các trường hợp tầm thường, bạn cũng sẽ phải kiểm thử hàng tỷ chương trình hoàn toàn vô nghĩa
Bối cảnh quan trọng là khám phá này cho thấy một số trong tổ hợp học hiện nằm trong khoảng 2.2202~2.756, thay vì khoảng 2.218~2.756 được biết đến vào năm ngoái
Cải thiện này đạt được không hẳn bằng chứng minh toán học thiên về logic, mà bằng cách tìm ra các dãy số cụ thể có những tính chất đặc biệt. Điều đó không có nghĩa là nó kém chặt chẽ
Đây là một cách thú vị và có lẽ hữu ích để tạo ra ví dụ, và trên thực tế khá gần với thuật toán di truyền có kèm LLM
Bình luận của Subbarao về “tự đấu với chính mình”: https://twitter.com/rao2z/status/1728121216479949048
Theo bài viết, FunSearch dùng phương pháp tiến hóa được vận hành bởi LLM để thúc đẩy và phát triển các ý tưởng có điểm số cao. Những ý tưởng này tồn tại dưới dạng chương trình máy tính nên có thể tự động thực thi và đánh giá
Người dùng viết mô tả bài toán dưới dạng mã. Mô tả này bao gồm quy trình đánh giá chương trình và một chương trình hạt giống để khởi tạo pool chương trình
Ở mỗi vòng lặp, FunSearch chọn một số chương trình từ pool hiện tại, LLM mở rộng chúng một cách sáng tạo để tạo ra chương trình mới, rồi các chương trình mới được đánh giá tự động. Những chương trình tốt nhất lại được thêm vào pool hiện có, tạo thành một vòng lặp tự cải thiện
Trong tìm kiếm web, người ta cũng dùng pplx.ai và phind.com theo cách tương tự như bộ đánh giá. Đặt câu hỏi, xem chúng mang về tài liệu tham khảo và liên kết web nào, rồi tinh chỉnh câu hỏi hoặc đặt câu hỏi tiếp theo để kéo ra tài liệu sâu hơn hoặc khác hơn. Nó hoạt động tốt hơn việc lục reddit hay Google để tìm ra những viên ngọc ẩn
Tech Twitter cũng có rất nhiều nội dung tuyệt vời, nên tôi hy vọng sẽ thử dùng Grok cho nghiên cứu, nhất là khi nó đã được mở cho mọi người
https://twitter.com/gfodor/status/1735348301812383906
Có ý kiến nói rằng: “Nếu đây là bằng chứng mang tính quyết định cho thấy DeepMind đã chứng minh mạng nơ-ron thực sự có thể tạo ra tri thức mới, thì đây là khám phá quan trọng nhất kể từ lửa.”
Nếu thực sự đúng như vậy thì tôi thắc mắc vì sao mọi người lại không nói về chuyện này nhiều hơn. Việc họ làm được điều đó bằng PaLM 2, vốn kém tiên tiến hơn GPT-4 hay Gemini, cũng rất ấn tượng. Nếu vài thế hệ mô hình tiếp theo tận dụng được phương pháp này thì không biết sẽ làm được những gì nữa
LLM chỉ thay thế toán tử đột biến ngẫu nhiên, ở mức nhận yêu cầu kiểu như “hãy đề xuất một chỉnh sửa hợp lý cho đoạn Python 20 dòng này”. Nếu quy công tạo ra tri thức cho mạng nơ-ron thì có vẻ là đánh giá hơi quá hào phóng
Ngoài việc cần một cấu trúc kiểu “khó tạo nhưng dễ đánh giá”, nó còn phụ thuộc rất mạnh vào bản chất của bài toán. Phần muốn tiến hóa phải có thể tách ra thành đúng một hàm Python rất ngắn
Việc LLM có thể tìm ra lời giải mới cho hình học cao chiều, nơi suốt 20 năm không có tiến triển, rõ ràng vượt xa mức chỉ ghép nối nghe có vẻ hợp lý những mảnh dữ liệu huấn luyện bị sao chép
Điều đó gợi ý rằng nếu chỉ cần biết cách prompt và đánh giá đúng thì năng lực của LLM còn có chiều sâu tiềm ẩn
Đây là kết quả vượt xa kỳ vọng của tôi. Không ai biết đằng sau prompt tiếp theo và seed ngẫu nhiên tiếp theo sẽ là khám phá nào
LLM cũng vậy: https://www.nature.com/articles/s41587-022-01618-2
a) có bộ đánh giá hiệu quả, b) có phản hồi điểm số phong phú để định lượng mức cải thiện, tức không phải tín hiệu nhị phân, c) có thể cung cấp một khung với phần cô lập để tiến hóa
Ví dụ, bài toán sinh chứng minh định lý nằm ngoài phạm vi này vì chưa rõ phải cung cấp tín hiệu điểm số đủ phong phú như thế nào
Đây là thành tựu rất đáng nể, nhưng so với việc phát hiện ra lửa, hay vô số thứ ở giữa như điện, thì không có vẻ cùng đẳng cấp
Tóm lại, khi có mẫu/khung chương trình và hàm fitness, họ dùng LLM để tạo ra một quần thể chương trình, rồi dùng prompt tạo chương trình mới từ k phiên bản khác; họ nhận thấy k=2 là tốt. Hơi mang tính sinh học. Sau đó họ chạy chương trình trên đầu vào và chấm điểm bằng hàm fitness, còn phần tiến hóa thì dùng mô hình đảo
Về nguyên tắc, prompt có lẽ trông như thế này
def foo_v1(a, b): ...def foo_v2(a, b): ...# hãy dùng foo_v1 và foo_v2 để tạo một hàm mới. Bạn chỉ được thay đổi phần nằm trong ngoặc nhọn kép như {{ THIS }}def foo(a, b): return a + {{}}Nếu để có kết quả mới mà chỉ cần khoảng 1e6 lần gọi LLM thì đó là con số khá ấn tượng vì quá ít. Họ cũng nói việc đánh giá/chấm điểm mất vài phút
Ở đây có thể nghĩ về sự đánh đổi giữa chiều sâu và chiều rộng. Nó gắn với độ trễ và thông lượng khi chấm điểm từng chương trình và cả quần thể. Liệu có thể memoization cho tất cả chương trình không. Nếu giữ hàm loss ở dạng đa chiều, với mỗi chiều ứng với từng đầu vào hoặc bucket đầu vào, thì có thể trước tiên tìm các quần thể chương trình giỏi ở những vùng khác nhau rồi kết hợp chúng lại sau không
Tôi cũng thắc mắc liệu họ có tri thức tiên nghiệm nào về độ hiếm của cap set hay không. Không rõ trước đây đã từng có những nỗ lực tính toán nào mà không thành công hay chưa, nhưng dù sao vẫn rất tuyệt
Nói lại theo cách khác từ bài đăng trên Twitter / X, từ giờ mọi thứ có lẽ chỉ ngày càng tốt hơn
Tức là năng lực AI tăng đơn điệu, và đã như vậy suốt hàng chục năm; trong trường hợp này thì năng lực còn tự cải thiện theo kiểu đệ quy. Tôi đã thấy AI autocomplete, AI-based refactoring, rồi code review diff do AI tự tạo trong phần bình luận giúp năng suất lập trình cá nhân tăng khoảng 20~30%
Cảm giác như AI đang bước vào giai đoạn giống Intel những năm 90. Khi đó, nếu muốn code chạy nhanh gấp đôi thì chỉ cần chờ bản revision CPU Intel tiếp theo. Bây giờ mô hình AI đóng vai trò đó. Nếu bạn đã nối các luồng công việc kinh doanh như lập trình, hỗ trợ khách hàng hay phân loại bug vào hệ thống LLM, thì việc “cải thiện” hệ thống gần như chỉ còn là đổi tên model
Sau giai đoạn tích hợp ban đầu, có thể kỳ vọng trong vài năm tới sẽ có tình huống “mọi thứ đều dần tốt lên một chút như có phép màu” với nỗ lực tối thiểu
Đặc biệt là họ không so sánh kết quả khi dùng LLM với kết quả khi không dùng LLM. Theo hiểu biết của tôi, bài báo này chỉ cho thấy kết quả lập trình di truyền dùng LLM để sinh ra các hàm kernel Python có lẽ tuân theo type signature đã cho. LLM không nhất thiết là thành phần bắt buộc cho công việc này
Vì vậy, việc ở đây LLM có thực sự làm điều gì đặc biệt hay không vẫn còn là câu hỏi bỏ ngỏ
Một trong những bài toán họ xử lý là bài toán cap set
https://en.m.wikipedia.org/wiki/Cap_set
Bài toán này là tìm cap set lớn nhất, tức tập điểm lớn nhất trong lưới cao chiều sao cho không có ba điểm nào nằm trên cùng một đường thẳng. Nó quan trọng vì đóng vai trò mô hình cho các bài toán khác trong tổ hợp cực trị. Tổ hợp cực trị nghiên cứu xem các tập hợp số, đồ thị hoặc các đối tượng khác có thể lớn hoặc nhỏ đến mức nào. Không thể giải bài toán này bằng tính brute force vì số khả năng cần xét tăng nhanh đến mức sớm vượt quá số nguyên tử trong vũ trụ
FunSearch đã tạo ra lời giải dưới dạng chương trình, và trong một số thiết lập, nó tìm được cap set lớn nhất từng được biết đến cho đến nay. Đây là mức tăng lớn nhất về kích thước cap set trong 20 năm qua. Ngoài ra, bài toán này còn tăng quy mô vượt xa khả năng của các solver tính toán tiên tiến hiện nay, nên FunSearch đã vượt qua các solver đó
Tôi thắc mắc làm sao để tích hợp suy luận ký hiệu với LLM, hoặc liệu điều đó có khả thi không
Bài báo FunSearch gần đây của DeepMind nhấn mạnh rằng họ đã sử dụng mô hình ngôn ngữ lớn được huấn luyện trước để tạo ra các cải tiến mã nguồn
Điều thú vị là LLM chính là Codey dựa trên họ mô hình PaLM2, nhưng trong tài liệu bổ sung cũng có nhắc đến StarCoder, một LLM mã nguồn mở
Tuy nhiên, kho GitHub của FunSearch lại không bao gồm phần triển khai các LLM này. Ví dụ, trong
sampler.pycó đoạn mã sauĐoạn mã này cho thấy cần có một phần triển khai LLM bên ngoài. Nếu họ thực sự đã sử dụng StarCoder thành công, thì việc không có hướng dẫn tích hợp hoặc phần triển khai mặc định cho nó, hoặc cho một LLM mã nguồn mở tương tự, là điều khá bất ngờ. Nếu có những nội dung đó, khả năng tái lập và tính dễ tiếp cận của nghiên cứu hẳn đã được cải thiện đáng kể
Bất kể đây có phải là tri thức mới có thể kiểm chứng hay không, nếu nghĩ đến vấn đề hạn chế quyền tiếp cận AI bằng kích thước mô hình hoặc các biện pháp quản lý khác, thì đây là một trường hợp nghiên cứu rất đáng chú ý
Những hạn chế như vậy tạo ra lợi thế không công bằng cho các công ty có thể phát hiện ra tri thức mới hoặc các quy luật tự nhiên nhưng không chia sẻ mà chỉ kiếm tiền từ đó