Diffusion trên cây cú pháp cho tổng hợp chương trình
(tree-diffusion.github.io)- Bài báo Tree Diffusion tại ICLR 2025 đề xuất một mô hình thần kinh chỉnh sửa chương trình lặp đi lặp lại dựa trên kết quả thực thi, thay vì sinh chương trình từng token một
- Điểm cốt lõi là mô hình học trên cây cú pháp được tạo từ một văn phạm phi ngữ cảnh bất kỳ, bằng cách đảo ngược nhiễu giống như diffusion trong ảnh
- Nhiễu được thêm vào dưới dạng đột biến ngẫu nhiên: thay một nút bất kỳ trong cây cú pháp bằng một nút khác có cùng kiểu hợp lệ
- Vì mã được sửa trong khi vẫn giữ trạng thái hợp lệ về mặt ngữ pháp, nên cách này dễ kết hợp với tìm kiếm (search) trong không gian chương trình
- Trong inverse graphics, phương pháp này có thể biến hình ảnh thành chương trình sinh ảnh, rồi kết hợp với tìm kiếm để gỡ lỗi chương trình đồ họa theo đặc tả yêu cầu bằng cách quan sát kết quả thực thi
Cách tiếp cận của Tree Diffusion
- Tree Diffusion là một phương pháp áp dụng diffusion trên cây cú pháp cho tổng hợp chương trình
- Bài báo, arXiv, mã nguồn và trọng số đã được công bố
- Các mô hình ngôn ngữ lớn hiện nay dùng tự hồi quy để sinh mã từng token một, và không có phản hồi từ việc quan sát kết quả đầu ra của chương trình trong quá trình sinh
- Cách huấn luyện để LLM trực tiếp đề xuất chỉnh sửa có thể khó triển khai vì cần đủ nhiều dữ liệu chỉnh sửa
- Tree Diffusion sửa chương trình bằng một mô hình đảo ngược nhiễu được áp lên cây cú pháp của văn phạm phi ngữ cảnh
Nhiễu, tìm kiếm và các trường hợp ứng dụng
- Nhiễu là một đột biến ngẫu nhiên trên cây cú pháp: chọn một nút bất kỳ rồi thay nó bằng một nút khác có cùng kiểu hợp lệ với nút bị thay
- Thay vì sinh tuần tự chương trình từ đầu, phương pháp này chỉnh sửa lặp đi lặp lại và vẫn giữ tính hợp lệ cú pháp
- Nhờ đặc tính đó, mô hình thần kinh có thể dễ dàng kết hợp với tìm kiếm trong không gian chương trình
- Trong bài toán inverse graphics, mô hình học cách nhận ảnh đầu vào và chuyển nó thành chương trình tạo ra chính hình ảnh đó
- Hệ thống kết hợp với tìm kiếm có thể viết chương trình đồ họa, kiểm tra kết quả thực thi, rồi gỡ lỗi để thỏa mãn đặc tả yêu cầu
- Kết quả cũng cho thấy hệ thống có thể viết chương trình đồ họa cho cả các bản phác thảo vẽ tay
1 bình luận
Ý kiến trên Hacker News
Nghe khá giống với công việc từng làm với Racket và việc tạo gợi ý cho MOOC
Không chắc là trường đại học nào, nhưng tôi từng xem một bài thuyết trình về việc tạo gợi ý cho sinh viên bằng cách biến đổi cây cú pháp và phân tích cần chỉnh sửa như thế nào để đi tới lời giải mục tiêu
Có lẽ là một bài nói ở RacketCon khoảng 10 năm trước, và có thể kết hợp kiểu phương pháp này với các cách tiếp cận học máy hiện đại
Tôi đã tìm thấy bài thuyết trình: https://invidious.baczek.me/watch?v=ijyFC36kVis
Kiểu đột biến cây con này thú vị ở chỗ đã được Koza và Adami bàn khá sâu từ thập niên 90 dưới tên gọi thuật toán di truyền
Chỉ là hàm tối ưu hơi khác một chút
Bài báo có một tài liệu tham khảo từ năm 2000 liên quan đến thuật toán di truyền để tạo cây chương trình nhanh, nhưng có vẻ bỏ sót phần công trình cốt lõi
Mong là các tác giả sẽ đọc và đào sâu vào công trình của họ
FFX và PGE đều rất nhanh
https://seminars.math.binghamton.edu/ComboSem/worm-chiu.pge_...
https://arxiv.org/pdf/2209.09675
Với tư cách là người tạo ra PGE, tôi vẫn luôn nghĩ rằng học tăng cường và gần đây hơn là các kỹ thuật khuếch tán có thể hữu ích cho những thuật toán như thế này
Mọi thuật toán đều cần cách nào đó để dẫn dắt việc tìm kiếm tốt hơn hoặc giúp thoát khỏi các cực trị cục bộ mà chúng rơi vào nhanh đến đáng ngạc nhiên
Phần lớn nghiên cứu về genetic programming/tính toán tiến hóa tập trung vào việc tránh hội tụ sớm
Theo phần mô tả trên trang web thì đó là “cuốn giáo trình AI có thẩm quyền nhất và được dùng nhiều nhất, được hơn 1500 trường áp dụng”
https://aima.cs.berkeley.edu/
Ôi, nhầm to rồi
Tôi có hai cuốn sách dày của Koza xuất bản năm 1992 và 1994, cụ thể là Genetic Programming: On the Programming of Computers by Means of Natural Selection và Genetic Programming II : Automatic Discovery of Reusable Programs
Hai cuốn sau đó thì tôi chưa đọc
Vấn đề lớn khi đó, một phần là phải làm cho nó đủ nhanh, một phần là làm sao để kết quả tạo ra con người có thể hiểu được
Vế sau này đặc biệt là nơi các mô hình ngôn ngữ lớn có vẻ tốt hơn nhiều
Cuối cùng người ta phải dành rất nhiều thời gian để tái cấu trúc và cắt tỉa cây nhằm có được kết quả có thể giải thích được, nên có vẻ giá trị chính bị giới hạn ở những trường hợp đáng để bỏ nhiều tài nguyên chỉ để tìm ra phiên bản tối ưu hơn của các thuật toán cực nhỏ và cô đọng
Nhưng trong hầu hết codebase lại có quá nhiều thứ dễ tối ưu hơn nhiều, nên hiếm khi đi tới mức đáng để thử kiểu này
Dù vậy, về mặt ý tưởng thì tôi vẫn rất thích
[1] https://www.genetic-programming.com/johnkoza.html
https://web.archive.org/web/20021224053225/http://smi-web.st...
https://www.genetic-programming.com/jkpdf/tr1314.pdf
Dùng Markov chain Monte Carlo cho program synthesis thật ra không phải ý tưởng mới
Tài liệu tham khảo hiện lên ngay trong đầu tôi là công trình của Josh Tenenbaum
WebPPL (ngôn ngữ lập trình xác suất trên web) cũng có rất nhiều demo như tổng hợp tàu vũ trụ 3D
Tôi cũng cực kỳ khuyến nghị cuốn The Design and Implementation of Probabilistic Programming Languages và các sách liên quan đến Probabilistic Models of Cognition
Các bài báo từ MIT Probabilistic Computing Project cũng đáng đọc
[1] Human-level concept learning through probabilistic program induction. https://www.cs.cmu.edu/~rsalakhu/papers/LakeEtAl2015Science....
[2] http://webppl.org/
[3] https://dritchie.github.io/web-procmod/
[4] https://dippl.org/
[5] http://probmods.org/
[6] http://probcomp.csail.mit.edu/
Tôi không thật sự hiểu rõ “phép màu” được nói tới ở đây.
Nếu theo cách tiếp cận truyền thống, có lẽ người ta sẽ tạo ra một ảnh ngẫu nhiên, tính một thước đo khoảng cách nào đó, rồi dùng một phương pháp tối ưu hóa như mô phỏng tôi luyện để giảm khoảng cách ấy.
Ở đây tôi hiểu là họ tối ưu hóa sự khác biệt giữa các biểu diễn ảnh, nhưng tôi không rõ việc thay đổi token của chương trình làm sao có thể khả vi.
Có vẻ ý tưởng cốt lõi là có thể huấn luyện một mô hình mạng nơ-ron để đề xuất các chỉnh sửa chương trình bằng cách biến đổi ngẫu nhiên các nút.
Khi chạy mô hình mạng nơ-ron này, nó có thể tạo ra các chỉnh sửa đúng cú pháp theo văn phạm phi ngữ cảnh, ví dụ như chỉ thay số bằng số.
Tôi tự hỏi nếu áp dụng việc này vào tối ưu hóa compiler/interpreter thì sẽ ra sao.
Liệu có thể “giải phẫu” một phần của quá trình thực thi, có lẽ ở mức assembly, để tạo ra các tối ưu hóa chuyên biệt cho mã đã biên dịch mà compiler hiện đại không thể tìm ra theo cách tất định, trong khi vẫn không làm thay đổi đầu ra không?
Ở đây đầu ra không phải là binary được tạo ra mà là kết quả chương trình được kỳ vọng.
Tôi không kỳ vọng loại công cụ này có thể “khám phá” ra assembly nếu nó không được huấn luyện trên chính các kết quả biên dịch.
Mô hình không có khái niệm về mã được chạy như thế nào hay ở đâu.
Sau hàng chục năm nghiên cứu compiler và cả supercompiler, có lẽ chúng ta đã đến gần mức mà việc tìm ra một tối ưu hóa mới tạo ra cải thiện rõ rệt là gần như bất khả thi.
Compiler ngày nay thực sự rất tốt.
Dù vậy, giá trị của kiểu tiếp cận này có thể nằm ở việc tối ưu hóa ý đồ của mã.
Nếu nó suy ra rằng bạn đang sắp xếp số, nó có thể thay mã bằng một thuật toán sắp xếp nhanh hơn nhưng vẫn giữ cùng tính chất chức năng.
Nếu bạn đang lưu dữ liệu không được dùng đến, nó có thể ngừng lưu chúng.
Đây là góc nhìn xem mã ở mức cao hơn một bậc so với những gì compiler nhìn thấy, không chỉ hiểu nó làm gì mà còn hiểu vì sao nó làm vậy.
Tôi dùng làm rối mã để tạo ra một bộ dữ liệu lớn từ một tập nhỏ các hàm đúng, rồi xây dựng một mô hình phân loại mã binary đã làm rối chưa từng thấy về hàm đã biết gần nhất.
Ứng dụng tôi nghĩ tới khi nghiên cứu khi đó là phân tích tĩnh malware, nhưng tối ưu hóa thực ra là mặt đối lập của làm rối mã.
Điều tôi muốn thử tiếp theo là một mô hình diffusion coi làm rối mã là “nhiễu” cần được loại bỏ.
Một điều tôi học được là compiler tối ưu hóa tạo ra đầu ra rất có quy luật.
Sau khi chuẩn hóa địa chỉ, kích thước “từ vựng” của các basic block khá nhỏ, cỡ khoảng 2000 token.
Một số “cụm từ” nhất định vẫn tương quan với ý nghĩa của mã nguồn gốc bất kể bạn chồng thêm bao nhiêu lớp làm rối lên trên.
Cũng có những người áp dụng các kỹ thuật tổng hợp vào superoptimization.
Vì vậy cách làm này có khả năng áp dụng được.
Trước đây tôi từng nghe nói GitHub sẽ bổ sung tích hợp với các công cụ build phổ biến.
Sẽ thế nào nếu có thể biên dịch mọi dự án biên dịch bằng LLVM trên GitHub và chạy một mô hình diffusion trên biểu diễn trung gian của chúng?
Liệu diffusion có thể hoạt động ở mức binary không?
Có thể huấn luyện một mô hình diffusion mà khi đưa prompt vào, nó tạo ra binary cuối cùng của chương trình không?
Có lẽ abstract syntax tree sẽ tốt hơn, nhưng binary ít nhất có vẻ rất dễ để kiểm tra nhanh xem có chạy được hay không.
Dù có nhiều nhược điểm, nếu làm được thì tôi rất mong đến ngày có thể nói “hãy tạo cho tôi một ứng dụng làm việc này” và mô hình diffusion sẽ tạo ra mọi byte của ứng dụng đó.
Chỉ nêu ra vì tò mò thôi.
Làm vậy sẽ tăng xác suất tạo ra chương trình hợp lệ.
Ta có thể tạo trực tiếp mã máy, nhất là khi không có lý do gì phải đi qua hàng đống tầng trung gian như Python hay JS.
Tôi muốn thấy nó được áp dụng cho SDF nữa.
Ý bạn là xấp xỉ hàm khoảng cách bằng biểu thức đại số, rồi xem chính đại số đó như một “ngôn ngữ lập trình” phải không?
File PDF render cực kỳ chậm.
Có lẽ vì nó chứa các lệnh cho hình vẽ được tạo bằng lập trình.
Nó mang lại cảm giác bài báo học thuật kiểu cũ mà dạo này tôi thấy nhớ.
https://arxiv.org/pdf/2405.20519
Phần áp dụng vào các tác vụ inverse graphics khiến tôi nhớ tới bài báo này, xuất hiện sớm hơn một tuần: https://arxiv.org/abs/2405.15306