- Transformer và LLM mạnh ở hội thoại, hiểu hình ảnh và hoàn thiện mã, nhưng khó đạt hiệu năng ổn định trong lập kế hoạch nhiều bước và suy luận bậc cao
- Bài báo này biến các bài toán lập kế hoạch và lời giải tối ưu thành chuỗi token, đồng thời đưa cả dấu vết thực thi về cách A* giải bài toán vào dữ liệu huấn luyện
- Searchformer trước tiên mô phỏng quá trình tìm kiếm của A*, sau đó được tinh chỉnh để tạo ra các chuỗi tìm kiếm ngắn hơn trong khi vẫn giữ được kế hoạch tối ưu
- Trong thí nghiệm Sokoban, các mô hình thuộc họ Searchformer giải được 93,7% tác vụ kiểm thử và dùng trung bình ít hơn 26,8% số bước tìm kiếm so với bản cài đặt chuẩn dựa trên A*
- Dù dấu vết thực thi làm chuỗi sinh ra dài hơn 10×~100×, mô hình vẫn tạo ra kế hoạch tối ưu cho các tác vụ chưa biết thường xuyên hơn ngay cả khi dùng ít chuỗi huấn luyện hơn so với các mô hình chỉ học lời giải lớn hơn
Những việc Transformer làm tốt và các bài toán lập kế hoạch còn yếu
- Kiến trúc dựa trên Transformer cho thấy hiệu năng cao trên nhiều tác vụ
- hội thoại ở mức con người
- hiểu hình ảnh chất lượng cao
- sinh video
- sinh đa phương thức
- hoàn thiện mã
- Các mô hình như LLM được huấn luyện trên dữ liệu quy mô Internet có thể khái quát hóa tốt trong các trường hợp sử dụng thực tế
- Tuy vậy, vẫn còn những giới hạn trong các bài toán lập kế hoạch và suy luận
- LLM vẫn cho thấy điểm yếu trong các bài toán lập kế hoạch nhiều bước
- Khó khăn cũng xuất hiện khi thực hiện suy luận bậc cao
Giới hạn của prompt suy nghĩ theo từng bước
- Các hướng tiếp cận gần đây cố gắng cải thiện hiệu năng bằng cách khiến Transformer sinh ra các “ý nghĩ” trung gian trước khi trả lời
- Prompting Chain-of-Thought (CoT) và Tree-of-thoughts (ToT) khuyến khích mô hình “suy nghĩ” theo từng bước
- Những kỹ thuật này thường hiệu quả, nhưng đôi khi cũng có thể làm giảm hiệu năng vì các lý do như self-enforcing
- Một cách làm hoạt động tốt trên một bộ dữ liệu có thể thất bại trên bộ dữ liệu khác
- Ví dụ là khi kiểu suy luận cần thiết thay đổi, như giữa suy luận không gian và suy luận toán học
- Cách để Transformer và LLM thực hiện ổn định việc lập kế hoạch, ra quyết định nhiều bước và suy luận vẫn là một chủ đề nghiên cứu sôi động
Đưa động lực học tìm kiếm A* vào dữ liệu huấn luyện
- Cách tiếp cận này tập trung vào việc huấn luyện Transformer giải các bài toán lập kế hoạch phức tạp một cách vững chắc hơn
- Mô hình được huấn luyện giống LLM, tức là dự đoán từ tiếp theo khi được cho một chuỗi từ
- Thí nghiệm được thực hiện trên bộ dữ liệu sinh tổng hợp dùng ngôn ngữ tổng hợp và từ vựng tổng hợp
- Các bài toán lập kế hoạch và kế hoạch lời giải tối ưu được biểu diễn thành chuỗi từ gọi là token
- Quá trình tính toán mà A* thực hiện được ghi lại dưới dạng chuỗi token dấu vết thực thi
- Dấu vết thực thi tạo thành một bộ dữ liệu chuỗi chứa động lực học tìm kiếm của A*
- Thông qua các chuỗi được tăng cường bằng tìm kiếm, Transformer được huấn luyện để tạo ra các chuỗi token mã hóa đồng thời động lực học tìm kiếm của A* và kế hoạch tối ưu
Quy trình huấn luyện của Searchformer
- Mô hình cuối cùng là Searchformer được xây dựng qua hai giai đoạn
- Đầu tiên, Transformer được huấn luyện để mô phỏng quá trình tìm kiếm của A*
- Sau đó, mô hình được tinh chỉnh để vẫn xuất ra kế hoạch tối ưu nhưng tìm được kế hoạch trong ít bước tìm kiếm hơn
- Quá trình này được gọi là search dynamics bootstrapping
- Mục tiêu là thu được một Transformer có thể giải các bài toán lập kế hoạch phức tạp với ít bước tìm kiếm hơn bản cài đặt chuẩn dựa trên A*
Thí nghiệm Sokoban và khả năng khái quát hóa
- Trên puzzle Sokoban, các mô hình thuộc họ Searchformer giải được 93,7% tổng số tác vụ kiểm thử
- Số bước tìm kiếm trung bình ít hơn 26,8% so với bản cài đặt chuẩn A*
- Các thí nghiệm kiểm soát độ phức tạp của tác vụ, kích thước bộ dữ liệu và kích thước mô hình đã xác nhận hiệu quả của việc đưa dấu vết thực thi vào
- Khi thêm dấu vết thực thi vào dữ liệu huấn luyện, độ dài chuỗi sinh ra tăng 10×~100×
- Dù vậy, hiệu năng vẫn tăng trên một tập tác vụ kiểm thử độc lập
- Mô hình được tăng cường bằng tìm kiếm tạo ra kế hoạch tối ưu cho các tác vụ chưa biết thường xuyên hơn ngay cả khi có số chuỗi huấn luyện ít hơn 10 lần so với mô hình chỉ học lời giải lớn hơn
- Mô hình được tăng cường bằng tìm kiếm được huấn luyện trên dữ liệu gồm mô tả tác vụ, lời giải và dấu vết thực thi
- Mô hình chỉ học lời giải được huấn luyện bằng các chuỗi chỉ gồm mô tả tác vụ và lời giải của tác vụ
- Kết quả này cho thấy việc đưa động lực học tìm kiếm của A* vào quá trình huấn luyện Transformer có thể cải thiện hiệu năng trên các bài toán lập kế hoạch
1 bình luận
Ý kiến trên Hacker News
Cũng từng có nghiên cứu thú vị hơn về việc dùng transformer cho lập kế hoạch chuyển động robot 0
Bài toán di chuyển cánh tay robot từ điểm A đến điểm B đồng thời tránh va chạm rất khó vì có số chiều cao và liên tục; các phương pháp lập kế hoạch truyền thống thường tốn nhiều tính toán mà hiệu năng lại không tốt
Vì vậy đây là một trong những lý do khiến chuyển động robot trông “thiếu tự nhiên” và robot không làm tốt nhiều tác vụ mà ta mong muốn; cách tiếp cận này có vẻ lập kế hoạch các đường đi gần tối ưu nhanh hơn và khá cạnh tranh với các phương pháp khác
Trước khi đi theo hướng nghiên cứu này, tôi tò mò liệu họ đã thử thuật toán J sửa đổi* — một tối ưu hóa của A* cho đồ thị game/tìm đường — hay chưa
Ai quan tâm có thể xem trong Game AI Pro 2 0
Bài báo này kiểm tra transformer dự đoán vết thực thi tốt đến đâu, chẳng hạn như trong trường hợp trình biên dịch JIT, và liệu điều đó có giúp cải thiện heuristic ở những nơi như tìm đường hay không
Tuy vậy transformer chậm, nên tôi nhìn nhận khá thận trọng
Các bài toán lập kế hoạch vốn đã được xử lý tốt bằng những kỹ thuật đã định hình như tìm kiếm trên đồ thị, bộ giải SAT, vận trù học, Prolog
Thường thì trọng tâm là tối ưu hóa giữa nhiều phương án khả dĩ, và tôi không chắc transformer có phù hợp với việc đó không
Vai trò của các kỹ thuật thuộc họ LLM có vẻ nghiêng về dịch mô tả ngôn ngữ tự nhiên thành chương trình có thể thực thi hơn, nhưng Prolog ngay từ đầu cũng được thiết kế cho xử lý ngôn ngữ tự nhiên cổ điển nên đã khá gần với mục tiêu đó
Dịch máy trước đây cần giải mã ngữ pháp phức tạp có dùng tìm kiếm, nhưng hiện nay dùng transformer với cách giải mã đơn giản hơn nhiều và thực tế gần như không cần tìm kiếm
Giờ có thể đi tới cả cấu trúc đệ quy hoàn chỉnh
Ý tưởng là học heuristic cho tìm kiếm kiến trúc mạng nơ-ron (NAS) bằng các mô hình dự đoán tốt nhất hiện nay, rồi tìm những khối mạng nơ-ron mới tốt hơn transformer hay mamba
Điểm kỳ dị đang đến…
Nếu quan tâm đến các trò kiểu Sokoban, có thể xem https://thinky.gg
Có một biến thể Sokoban thú vị tên Sokopath, và một biến thể NP-hard khác tên Pathology, trong đó mục tiêu là đi từ điểm A đến điểm B với số bước ngắn nhất
Cộng đồng đã thử tạo nhiều bộ giải, nhưng khi lưới lớn hơn 5x5 thì trở nên rất khó; cộng đồng thinky cũng đã dùng simulated annealing để tìm ra các màn thú vị có số bước tối đa rất lớn
“Giảm 26,8% số bước tìm kiếm so với tìm kiếm A* tiêu chuẩn”
Tức là trong Sokoban, nó chỉ nhỉnh hơn A* một chút, vốn còn rất xa so với mức hiện đại nhất (https://festival-solver.site/)
Tôi không rõ điều gì ở bài báo này đáng ấn tượng, hay vì sao nó được đưa lên Hacker News
Nhưng nếu miền tìm kiếm có những ràng buộc khác có thể tận dụng, thì có thể vượt A*
Ví dụ Jump Point Search khai thác tính chất của tìm kiếm trên lưới khi chỉ được di chuyển theo một số cách nhất định
Nếu có thể tạo ra một thuật toán tìm kiếm tổng quát “tự động” khai thác hiệu quả các tính chất đặc thù của miền nền tảng mà không cần con người phân tích thủ công, thì chẳng phải sẽ hữu ích sao
A* gần như là lời giải cơ sở “ngây thơ”, và họ không trực tiếp suy nghĩ về thiết kế thuật toán
Việc một encoder-decoder transformer đơn giản làm được đến mức này khá ấn tượng
“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 ...”
Bài báo này thú vị vì là một ví dụ dùng transformer cho ra quyết định, chứ tôi không quá quan tâm hiện tại nó đã đạt mức A* hay chưa
Tất nhiên giả thuyết đó có phiên bản mạnh và phiên bản yếu, và phiên bản mạnh có lẽ không đúng; nhưng chừng nào có vẻ như ta đang tiến gần hơn tới “một cách đúng duy nhất” để tự nhiên học làm việc, thì đây vẫn là một tin quan trọng
Nếu transformer có thể lập kế hoạch, điều đó có thể có nghĩa là trí tuệ nhân tạo tổng quát chỉ cần được đào tạo tốt hơn
Cũng cần học trực tuyến và nhiều tầng khác nữa
Có một bản tóm tắt bài báo này dưới dạng audiobook cho người học bằng thính giác
https://player.oration.app/09fefe41-f2a7-4257-a25e-30e479b30d6f
Tôi rất lạc quan về việc dùng heuristic đã học cho các thuật toán rời rạc như A*, Focal search, và nhiều họ quy hoạch tuyến tính nguyên
Trong hầu hết thư viện tối ưu hóa rời rạc hiện đại như CPLEX, khác biệt về hiệu năng phần lớn được giải thích bởi heuristic và việc tinh chỉnh
Thay thế các routine tìm kiếm tối ưu đã được hiểu rõ bằng một cách tiếp cận học đầu-cuối thì kém thuyết phục hơn, nhưng có thể đó chỉ là lo lắng không cần thiết
Tuy nhiên có vẻ các tác giả đã bỏ lỡ cơ hội đó
Có khi tôi cũng nên dùng transformer để giải tic-tac-toe rồi xin tiền VC
Vài năm nữa có lẽ mọi người sẽ viết bài về việc code thật hiệu quả hơn AI đến mức nào ;)
Nếu học được heuristic chấp nhận được, có thể duy trì hiệu năng trong trường hợp xấu nhất, và đó luôn là tiêu chuẩn của các thuật toán kiểu này
Việc tìm các lời giải nhanh hơn ở trường hợp trung bình hoặc p99 nhưng không cung cấp bảo đảm cho trường hợp xấu nhất thì hoàn toàn không hiếm
Tôi tò mò liệu có ai đang tổng hợp danh sách các thuật toán cổ điển hoặc bài toán NP-complete được deep learning làm tốt hơn không