Cellular Automata logic khả vi
(google-research.github.io)- DiffLogic CA là một cách tiếp cận cellular automata kết hợp Neural Cellular Automata với Differentiable Logic Gate Networks, học các quy tắc cục bộ bằng gradient trong khi vẫn duy trì trạng thái ô rời rạc
- Mỗi ô có trạng thái là một vector nhị phân n chiều; cả bước nhận thức và bước cập nhật đều được xử lý bằng mạng cổng logic để tính trực tiếp trạng thái kế tiếp
- Trong thí nghiệm Conway’s Game of Life, mô hình học một bước trên toàn bộ 512 cấu hình của lưới tuần hoàn 3x3 và nắm được toàn bộ luật; ngay cả khi suy luận hard, nó cũng tái hiện các mẫu tiêu biểu như glider, block, loaf, boat
- Thí nghiệm sinh mẫu tạo bàn cờ 16x16 trong 20 bước, vẫn hoạt động trên lưới lớn gấp 4 lần và thời gian dài gấp 4 lần, đồng thời cho thấy khả năng chịu lỗi với các ô bị hỏng và tự phục hồi sau khi được kích hoạt lại
- Mô hình cũng sinh được đường viền lizard phức tạp hơn và chữ G RGB 8 màu, nhưng việc học cấu trúc phức tạp cần nhiều tinh chỉnh siêu tham số; NCA phân cấp và các cổng giống LSTM còn là hướng cải thiện
Vấn đề mà DiffLogic CA nhắm tới
- Cellular automata thường được nghiên cứu theo cách trước hết định nghĩa quy tắc cục bộ, rồi quan sát mẫu hình nổi lên từ kết quả đó
- DiffLogic CA khám phá cách học các quy tắc cục bộ tạo ra một mẫu phức tạp mong muốn theo cách hoàn toàn khả vi
- Neural Cellular Automata hiện có có thể học các mẫu và hành vi tùy ý, nhưng về bản chất không vận hành trong không gian trạng thái rời rạc, làm giảm khả năng diễn giải và phát sinh chi phí nhân ma trận cho cập nhật trạng thái liên tục
- Differentiable Logic Gate Networks đã được dùng để khám phá mạch logic tổ hợp, nhưng chưa được chứng minh là hoạt động trong thiết lập NCA đệ quy theo cả không gian lẫn thời gian
- Toàn bộ thí nghiệm có thể được tái hiện trong notebook
Cấu trúc cơ bản của Neural Cellular Automata
- Neural Cellular Automata kết hợp deep learning với cellular automata cổ điển, học quy tắc cập nhật bằng gradient descent thay vì thiết kế quy tắc thủ công
- Mỗi ô của Growing-NCA có một vector trạng thái n chiều trên lưới 2D
- 3 kênh RGB biểu thị màu của ô
- Kênh Alpha biểu thị khả năng sống của ô; nếu giá trị alpha lớn hơn 0,1 thì ô được xem là còn sống
- Các hidden channel còn lại truyền tải thông tin phức tạp hơn về môi trường xung quanh
- Cập nhật gồm hai bước
- Bước nhận thức: áp dụng Sobel filter theo từng kênh để xấp xỉ gradient không gian, tạo perception vector kết hợp trạng thái hiện tại của ô với thông tin lân cận
- Bước cập nhật: một mạng nơ-ron có khoảng 8.000 tham số được áp dụng giống nhau cho mọi ô để quyết định mỗi ô sẽ thay đổi ra sao
- Vì mọi phép toán đều khả vi, toàn bộ hệ thống có thể học một mẫu hoặc hành vi cụ thể
Cách hoạt động của Differentiable Logic Gate Networks
- Deep Differentiable Logic Gate Networks dùng các cổng logic như AND, OR, XOR làm đơn vị cơ bản thay cho nơ-ron nhân tạo
- Mạng gồm các tầng cổng; mỗi cổng có cấu trúc thưa, nhận đầu vào từ hai cổng ở tầng trước
- Kết nối được khởi tạo ngẫu nhiên rồi không thay đổi trong quá trình học; việc học chỉ quyết định mỗi cổng sẽ thực hiện phép toán logic nào
- Trong quá trình học, mô hình không dùng trực tiếp cổng logic rời rạc mà dùng hai cơ chế
- Nới lỏng liên tục: thay các phép toán rời rạc như hard AND bằng phiên bản khả vi nhận đầu vào nằm giữa 0 và 1
- Chọn cổng xác suất: mỗi cổng có phân phối xác suất trên 16 phép toán nhị phân có thể có với hai đầu vào, và học tham số 16 chiều được biểu diễn bằng softmax
- Sau khi học xong, mỗi cổng được cố định thành phép toán có xác suất cao nhất; khi suy luận, mô hình chỉ thực hiện phép toán nhị phân thuần túy
- Để ổn định huấn luyện, phân phối cổng ban đầu được đặt lệch về phía các cổng pass-through
Cấu trúc của DiffLogic CA
- DiffLogic CA đi theo cấu trúc lưới 2D của NCA, nhưng biểu diễn trạng thái mỗi ô dưới dạng vector nhị phân n chiều
- Trạng thái ô và kênh được dùng với cùng ý nghĩa; vector trạng thái nhị phân đóng vai trò bộ nhớ làm việc lưu thông tin từ vòng lặp trước
- Bước nhận thức dùng kernel dựa trên mạng cổng logic thay cho Sobel filter
- Mỗi kernel là một mạch riêng với cấu trúc kết nối cố định, còn loại cổng được học
- Kernel được tính theo từng kênh
- Mỗi mạch dùng 4 tầng được thiết kế để tính tương tác giữa ô trung tâm và các ô lân cận
- Bước cập nhật nối bộ nhớ trước đó của ô với thông tin nhận từ hàng xóm rồi đưa đầu vào này vào Differentiable Logic Gate Network để tính trạng thái mới
- Không giống cập nhật kiểu ODE của NCA chuẩn, nơi trạng thái được cộng dần, mô hình xuất trực tiếp trạng thái nhị phân kế tiếp
- Hoạt động của một vòng có thể được nhìn như hai thanh ghi
- Thanh ghi màu xám chứa trạng thái ô hiện có
- Thanh ghi màu cam lưu kết quả của bước nhận thức
- Sau khi cập nhật, trạng thái mới được ghi vào thanh ghi màu xám, còn thanh ghi màu cam được xóa để chuẩn bị cho vòng tiếp theo
- Cấu trúc này hoạt động như một mạng gồm các máy tính nhỏ độc lập, trong đó mỗi ô giao tiếp với hàng xóm và ra quyết định dựa trên kết quả quan sát
Thí nghiệm 1: Học Conway’s Game of Life
- Game of Life là cellular automata nhị phân, trong đó mỗi ô sống hoặc chết ở thế hệ kế tiếp tùy theo trạng thái của 8 ô lân cận và trạng thái hiện tại của chính nó
- Luật gồm bốn điểm
- Ô chết sẽ sống ở thế hệ tiếp theo nếu có đúng 3 hàng xóm sống
- Ô sống sẽ tiếp tục sống nếu có 2 hoặc 3 hàng xóm sống
- Ô sống sẽ chết nếu có ít hơn 2 hàng xóm sống
- Ô sống sẽ chết nếu có nhiều hơn 3 hàng xóm sống
- Vì thí nghiệm này nhắm tới quy tắc không phụ thuộc vào các lần lặp trạng thái trước đó, trạng thái ô được đặt là 1 bit
- Cấu hình mô hình như sau
- 16 kernel mạch nhận thức
- Cấu trúc node của mỗi kernel nhận thức là
[8, 4, 2, 1] - Mạng cập nhật có 23 tầng
- 16 tầng đầu, mỗi tầng có 128 node
- Các tầng sau là
[64, 32, 16, 8, 4, 2, 1]
- Dữ liệu huấn luyện bao gồm toàn bộ 512 cấu hình có thể có trên lưới tuần hoàn 3x3
- Vì trạng thái kế tiếp của mỗi ô được quyết định bởi chính nó và 8 hàng xóm, nên có 512 cấu hình 3x3
- Nếu dự đoán đúng toàn bộ trạng thái kế tiếp của một bước, điều đó tương đương học được toàn bộ luật Game of Life
- Hàm loss cộng tổng bình phương sai khác giữa lưới dự đoán và lưới đáp án
- Cả soft loss và hard loss đều hội tụ hoàn toàn; trong suy luận hard, mạch đã học tái hiện các mẫu Game of Life trên cả lưới lớn hơn
- Số cổng hoạt động là 336, không tính pass-through A và B; OR và AND được dùng thường xuyên nhất trong mạng nhận thức và mạng cập nhật
- Có thể tương tác trực tiếp với mạch đã sinh tại mạch Game of Life
Thí nghiệm 2: Sinh mẫu bàn cờ
- Thí nghiệm sinh mẫu được thiết lập để học một quy tắc tiến hóa từ trạng thái ban đầu tùy ý tới ảnh mục tiêu
- Loss chỉ được tính ở timestep cuối, vì vậy mô hình phải tìm quy tắc chuyển trạng thái rời rạc mà không có giám sát theo từng bước trung gian
- Trạng thái ô là 8 bit, và DiffLogic CA được lặp trong 20 bước
- Cấu hình mô hình như sau
- 16 kernel mạch nhận thức
- Mỗi kernel có 8, 4, 2 cổng theo từng tầng
- Mạng cập nhật có 16 tầng
- 10 tầng đầu, mỗi tầng có 256 cổng
- Các tầng sau là
[128, 64, 32, 16, 8, 8]
- Hàm loss là tổng bình phương sai khác giữa kênh đầu tiên của lưới dự đoán và lưới mục tiêu tại timestep cuối
- Mô hình được huấn luyện để khôi phục mẫu bàn cờ 16x16 trong vòng 20 bước
- Cả soft loss và hard loss đều hội tụ, và sự hình thành mẫu rõ ràng xuất hiện ở kênh đầu tiên
- Dù mô hình không có thiên lệch hướng được tích hợp sẵn, mẫu lại có tính chất lan truyền từ góc dưới bên trái lên góc trên bên phải
- Số cổng hoạt động là 22, không tính pass-through A và B; sau khi cắt tỉa, toàn bộ hàm sinh bàn cờ thực tế có thể được triển khai bằng 5 cổng logic
- Mạch vẫn hoạt động khi mở rộng lên lưới lớn gấp 4 lần và thời gian dài gấp 4 lần, cho thấy quy tắc đã học không bị overfit vào một kích thước lưới cụ thể
Hư hỏng, tự phục hồi và cập nhật bất đồng bộ
- Trong thí nghiệm bàn cờ, nhóm thực hiện hai thí nghiệm hư hỏng, giả định một số ô bị lỗi
- Vô hiệu hóa vĩnh viễn một vùng ô lớn để mô phỏng linh kiện lỗi
- Kích hoạt lại các ô đã bị vô hiệu sau một số bước nhất định
- Hệ thống duy trì tính toàn vẹn của mẫu ngay cả khi bị hư hỏng vĩnh viễn, và sau khi các ô bị vô hiệu trở lại online, nó tái tạo đúng mẫu
- Dù không được thiết kế rõ ràng cho khả năng chịu lỗi và tự phục hồi, hệ thống vẫn cho thấy hành vi trong đó hư hỏng được khoanh vùng và chức năng tổng thể không sụp đổ đột ngột
- Trong thí nghiệm cập nhật bất đồng bộ, không cập nhật đồng thời tất cả ô, mà ở mỗi bước chỉ cập nhật một tập con ô ngẫu nhiên
- Huấn luyện bất đồng bộ được dự đoán là khó hơn NCA hiện có
- Ở mỗi bước, mô hình phải xuất toàn bộ trạng thái mới thay vì phần gia tăng
- Nó phải xử lý các tổ hợp trong đó ô xung quanh đi trước hoặc tụt sau nhau một số bước khác nhau
- Với bàn cờ, huấn luyện bất đồng bộ thành công tương đối dễ dàng; từ cùng trạng thái ban đầu, mô hình tái cấu trúc mẫu mục tiêu trong 50 bước dù dùng các thứ tự cập nhật khác nhau
- Các quy tắc hiện có được học theo kiểu đồng bộ cũng hoạt động khi áp dụng vào suy luận bất đồng bộ
- Trong bài kiểm tra vô hiệu hóa ngẫu nhiên một hình chữ nhật 10x10 pixel trong vùng ảnh ở mỗi timestep suy luận, các ô được huấn luyện bất đồng bộ phục hồi từ hư hỏng nhanh hơn một chút
- Khi đo lỗi bằng tổng trị tuyệt đối sai khác giữa ảnh mục tiêu và ảnh tái cấu trúc, huấn luyện bất đồng bộ làm tăng độ vững chắc trước các nhiễu loạn này
Thí nghiệm 3: Tăng trưởng đường viền lizard
- Thí nghiệm lizard là một lời tri ân tới công trình NCA gốc, nhằm kiểm tra liệu DiffLogic CA có thể học hình dạng tùy ý hay không
- Không giống mẫu đều đặn như bàn cờ, vốn có thể nén rất mạnh, đường viền lizard đòi hỏi nhiều ghi nhớ hơn
- Thiết lập như sau
- Trạng thái ô là 128 bit
- DiffLogic CA lặp trong 12 bước
- Có 4 kernel mạch nhận thức
- Mỗi kernel có 8, 4, 2, 1 cổng theo từng tầng
- Mạng cập nhật có 10 tầng
- 8 tầng đầu, mỗi tầng có 512 cổng
- Các tầng cuối là
[256, 128]
- Mô hình được huấn luyện để sinh mẫu lizard 20x20 trong 12 bước
- Điều kiện ban đầu là seed trung tâm để phá đối xứng như NCA, và điều kiện biên tuần hoàn được áp dụng ở rìa lưới
- Khi đánh giá trên lưới lớn hơn 40x40, mô hình vẫn sinh thành công mẫu tăng trưởng lizard, cho thấy đây không phải là lời giải dựa vào điều kiện biên
- Cả soft loss và hard loss đều hội tụ về 0
- Số cổng hoạt động là 577, không tính pass-through A và B
- Các kernel nhận thức chủ yếu dùng cổng TRUE, còn mạch cập nhật dùng gần như tất cả các cổng khả dụng
- Học sinh mẫu phức tạp khó tối ưu và cần tinh chỉnh siêu tham số trên diện rộng
Thí nghiệm 4: Sinh chữ G có màu
- Vì các thí nghiệm trước về cơ bản tập trung vào ảnh đơn sắc, nhóm thực hiện một thí nghiệm sinh ảnh màu 16x16 làm trạng thái mục tiêu phức tạp hơn
- Trạng thái ô có 64 kênh, và mô hình sinh chữ cái G có màu trong 15 bước
- Ba kênh đầu biểu thị giá trị RGB theo quy ước NCA chuẩn, nhưng ở đây mỗi giá trị bị giới hạn trong biểu diễn nhị phân 0 hoặc 1, tạo thành bảng màu 8 màu
- Cấu hình mô hình như sau
- 4 kernel mạch nhận thức
- Mỗi kernel gồm 3 tầng với 8, 4, 2 cổng
- Mạng cập nhật có 11 tầng
- 8 tầng đầu, mỗi tầng có 512 node
- 3 tầng cuối là
[256, 128, 64]
- Trạng thái ban đầu hoàn toàn là 0, và không dùng điều kiện biên tuần hoàn
- Hàm loss chỉ nhắm tới ba kênh đầu, tức kênh 0, 1, 2, tại timestep cuối, bằng cách cộng tổng bình phương sai khác giữa lưới dự đoán và lưới mục tiêu
- Cả soft loss và hard loss đều hội tụ, và mô hình tái cấu trúc chữ G có màu trong vòng 15 bước
- Số cổng hoạt động là 927, không tính pass-through A và B
- Các cổng TRUE và FALSE được dùng nhiều trong cả mạng nhận thức lẫn mạng cập nhật; trong mạng cập nhật, cổng OR được dùng nhiều nhất
- Mạch này phức tạp hơn các thí nghiệm trước cả về tìm kiếm siêu tham số lẫn kích thước mạch
Bài toán còn lại và hướng cải thiện
- DiffLogic CA đề xuất một cấu trúc và phương pháp học NCA mới, sử dụng trạng thái ô hoàn toàn rời rạc và cập nhật trạng thái bằng mạch nhị phân đệ quy đã học
- Bằng cách thay các thành phần mạng nơ-ron bằng Deep Differentiable Logic Networks, mô hình kết hợp tính linh hoạt của học khả vi với các cổng logic rời rạc
- Các thí nghiệm sao chép Game of Life và sinh mẫu cho thấy cổng logic khả vi có thể được áp dụng cho cellular automata
- Kết quả xác nhận Differentiable Logic Gate Networks có thể học hiệu quả cả trong cấu trúc đệ quy
- Mô hình hiện tại đã cho thấy khả năng học mẫu, nhưng việc học để sinh các hình dạng và cấu trúc phức tạp hơn vẫn còn khó
- Các hướng cải thiện được đề xuất gồm cấu trúc NCA phân cấp và các cổng đặc biệt giúp quên trạng thái
- Nếu tích hợp cơ chế gating giống LSTM vào quá trình cập nhật trạng thái, mô hình có thể kết hợp trạng thái quá khứ với trạng thái ứng viên mới tính được một cách phong phú hơn, qua đó tăng động lực học và năng lực biểu diễn của mô hình
1 bình luận
Ý kiến trên Hacker News
Rất thú vị. Tôi đã đi tìm một chất nền máy Turing phổ dụng mới và sưu tầm chúng kiểu như Pokémon để làm thí nghiệm lập trình di truyền. Trước đây tôi cũng từng nghịch cellular automata với rule 30/110 các kiểu, nhưng cách tiếp cận này thuyết phục hơn nhiều
Tôi chưa từng nghĩ đến việc mô hình hóa kernel như một mạch logic số. Có vẻ như các ràng buộc của logic Boolean, cổng và mạch tạo ra một cấu trúc thú vị cho bề mặt độ thích nghi. Các tham số kết quả có thể được chuyển thẳng sang triển khai phần cứng, hoặc sau một bước tối ưu hóa bổ sung thì biên dịch thành một chương trình đơn giản. Có vẻ tốt hơn việc xử lý những số thực dấu phẩy động như phép màu bên trong một hộp đen hàng chục tỷ tham số
Quá hấp dẫn. Michael Levin là người đã đặt vấn đề hay nhất về cách các tế bào động vật có thể phối hợp mà không cần phân cấp. Ví dụ có những thí nghiệm sinh học cho thấy ngay cả khi tách các tế bào mắt khỏi phôi ếch, chúng vẫn di chuyển đến vị trí lẽ ra phải có mắt
Theo tôi, câu hỏi mà ông ấy chưa thực sự trả lời được là làm sao tế bào biết khi nào phải dừng lại. Hiểu được sự tổ chức phi phân cấp cũng là chìa khóa để hiểu cách xã hội vận hành, và để giải thế tiến thoái lưỡng nan của tù nhân ở nhiều quy mô trong một thế giới tự tổ chức. Đây cũng là việc hiểu và mô hình hóa sự phức tạp thô mộc. Đây là lần đầu tiên tôi thấy một năng lực có thể mô hình hóa những thứ như vậy, và có vẻ như từ đây có vô số hướng để phát triển
Gần đây tôi suy nghĩ rất nhiều về trí tuệ, và có cảm giác như chúng ta đang ở điểm nút quyết định để tìm ra nó hoạt động như thế nào, hoặc ít nhất là thúc đẩy hiểu biết tiến lên rất xa. Trí tuệ có vẻ là một hành vi nảy sinh tự nhiên, không khác mấy so với cơ học Newton cổ điển hay điện
Cuối cùng có vẻ nó quy về những quy tắc đơn giản. Điều gì sẽ xảy ra nếu mọi thứ không rời rạc trong não thực ra chỉ là hạ tầng chống đỡ cho một quá trình cốt lõi đơn giản nhưng quan trọng mới là thứ thực sự làm việc? Nếu đi xuống đến tận cùng mà rốt cuộc chỉ còn các cổng logic và tín hiệu điện thì sao? Có vẻ sắp tới sẽ là một thời kỳ rất thú vị
Có một điểm hấp dẫn ở cách tiếp cận này, đặc biệt về khả năng khái quát hóa. Nhưng tôi tò mò tầm nhìn lớn là gì. Rồi chúng ta sẽ làm được gì? Về mặt triết học, nó dạy ta điều gì về thế giới? Chúng ta vốn đã biết cellular automata 1 chiều là tương đương Turing, nên ở một góc nhìn nào đó thì NCA hay kiểu này không quá gây sốc
Sẽ xuất hiện những cellular automata tương tác với môi trường, với cả hệ thống cấp thấp lẫn các thể chế cấp cao. Nếu xấp xỉ ở một mức nào đó, con người cũng chỉ là những tế bào riêng lẻ tương tác trong một mạng như vậy. Theo tôi tương lai của trí tuệ không phải LLM mà là các hệ automata có khía cạnh trao đổi chất. Đó là những automata cùng tiến hóa, tiêu thụ năng lượng, tạo ra giá trị, cạnh tranh và mô hình hóa lẫn nhau
Chúng ta không bị thay thế; chúng ta đang tham gia vào một quá trình chuyển hóa trong đó ranh giới giữa hệ thống công nghệ và hệ thống tế bào mờ dần rồi cuối cùng biến mất. Tôi rất biết ơn vì được chứng kiến điều này. Tham khảo: https://x.com/zzznah/status/1803712504910020687
Tôi thích nghịch cellular automata trong các tác phẩm nghệ thuật. Thật đáng kinh ngạc khi thấy những mẫu hình nào có thể nảy sinh. Ví dụ: https://gods.art/math_videos/hex_func27l_21.html
Có lẽ tôi cũng nên thử nghịch DLCA này
Ở đây có nhiều ý tưởng rất hay. Có thể chỉ là một quan sát nhỏ, nhưng phép tính này có trạng thái. Mỗi ô có bộ nhớ và có cảm nhận về môi trường xung quanh
Trong khi đó các mạng nơ-ron hiện đại phần lớn là không trạng thái. Ví dụ, tôi tò mò không biết đã có nghiên cứu nào về LLM có trạng thái hay chưa
Tự quảng bá một chút nhưng rất liên quan: Robustness and the Halting Problem for Multicellular Artificial Ontogeny (2011)
Đó là một cellular automata mà quy tắc cập nhật là perceptron kết hợp với khuếch tán đẳng hướng. Chúng tôi tối ưu trọng số mạng nơ-ron để cellular automata vẽ ra một bức hình, và khi bị nhiễu loạn thì cũng tự phục hồi để vẽ lại bức hình. Hồi đó tự động vi phân chưa dễ tiếp cận như bây giờ nên chúng tôi tối ưu trọng số bằng chiến lược tiến hóa. Tất nhiên rất có thể dùng gradient descent sẽ tốt hơn nhiều
Liệu có thể dùng cái này cho ARC-AGI challenge không? Có vẻ cũng có thể kết hợp với cách tiếp cận gần đây này: https://news.ycombinator.com/item?id=43259182
Thật sự quá ấn tượng. Là một người đã âm thầm theo dõi rất lâu và dùng nhiều mô hình hóa cùng mô phỏng, tôi thấy nó có tiềm năng lớn để hiểu rõ hơn hành vi nảy sinh của các mô hình hành vi tác tử phức tạp
Tôi muốn thấy nó được áp dụng vào những thứ như mô hình thú săn mồi/con mồi, và các mô hình khác thoạt nhìn có vẻ đơn giản nhưng ở quy mô lớn lại tạo ra các kết quả nảy sinh cực kỳ phức tạp. Tôi sẽ tiếp tục theo dõi công trình này
Mẫu caro trong kết quả trông giống như phần ngược lại của mẫu mục tiêu, tức kiểu NOT. Nhưng không thấy nhắc gì đến điều này. Tôi không rõ là nó không đủ quan trọng để nhắc tới hay là tôi đang bỏ lỡ điều gì