Ô-tô-ma tế bào logic khả vi

• Khám phá cách thiết kế ngược các mẫu phức tạp từ những quy tắc cục bộ đơn giản
• Một cách tiếp cận kết hợp khả năng học của Neural Cellular Automata(NCA) với Differentiable Logic Gate Networks để thu được các quy tắc cục bộ rời rạc theo phương pháp học
  • "Liệu có thể học ra được quy tắc của Conway's Game of Life không?"
  • "Có thể tái hiện các mẫu phức tạp như NCA, đồng thời học được cấu trúc tuần hoàn không-thời gian không?"

Introduction

• Cellular Automata(CA) bắt đầu từ các quy tắc cục bộ đơn giản nhưng có thể hình thành những mẫu phức tạp và khó dự đoán
• Theo truyền thống, quy tắc trong CA do con người trực tiếp thiết kế, nhưng ở đây giới thiệu một phương pháp có thể “học” ngược lại các quy tắc cục bộ thỏa mãn mục tiêu khi đã cho trước mẫu hoặc hành vi đích
• Đặc biệt, Neural Cellular Automata(NCA) được thiết kế để có thể học trong không gian liên tục bằng cách kết hợp kỹ thuật deep learning với cấu trúc CA
• Differentiable Logic Gate Networks là kỹ thuật xấp xỉ liên tục các cổng logic (AND, OR, XOR, v.v.) để huấn luyện, rồi cuối cùng chuyển đổi trở lại thành mạch logic rời rạc
• Bằng cách kết hợp hai ý tưởng này, bài viết đề xuất DiffLogic CA, một mô hình CA hoàn toàn rời rạc nhưng có thể học được
• Có thể xem đây là một bước nhỏ hướng tới Programmable Matter hoặc Computronium
• Bài viết triển khai theo các phần sau
  • Tóm tắt Neural Cellular Automata
  • Tóm tắt Differentiable Logic Gate Networks
  • Cấu trúc DiffLogic CA kết hợp hai phương pháp trên
  • Thí nghiệm học quy tắc Conway’s Game of Life
  • Thí nghiệm học để tạo các mẫu phức tạp (checkerboard, thằn lằn, ảnh màu, v.v.)

Recap – Neural Cellular Automata(NCA)

• Khái niệm
  • Một hệ thống thay thế quy tắc CA truyền thống bằng dạng có thể học được bằng mạng nơ-ron
  • Mỗi ô có nhiều kênh (state) và hình thành các mẫu phức tạp thông qua tương tác cục bộ
  • Sử dụng Sobel filter và các kỹ thuật tương tự để lấy thông tin lân cận, rồi mạng nơ-ron quyết định sự thay đổi trạng thái
• Đặc điểm
  • Toàn bộ quá trình tính toán đều khả vi, nên có thể huấn luyện để tạo ra mẫu mong muốn
  • Vẫn giữ được các đặc tính cốt lõi của CA như tính song song, tính cục bộ và tính toán dựa trên trạng thái, đồng thời kết hợp kỹ thuật deep learning

Recap – Differentiable Logic Gate Networks(DLGNs)

• Ý tưởng cốt lõi
  • Thay vì NN truyền thống, hệ thống học bằng cách xấp xỉ liên tục các cổng logic (AND, OR, XOR, v.v.) dưới dạng soft gate
  • Ở giai đoạn huấn luyện, các cổng hoạt động liên tục; khi suy luận cuối cùng thì thực hiện các phép toán nhị phân thực sự
• Quá trình học
  • Học phân phối xác suất trên 16 phép toán logic khả dĩ của cổng, rồi cuối cùng hội tụ về một phép toán cụ thể
  • Dùng xấp xỉ liên tục để làm cho mô hình khả vi, và sau khi huấn luyện xong sẽ chuyển sang các cổng logic rời rạc hoàn toàn
• Ưu điểm
  • Mạch cuối cùng được cấu thành hoàn toàn từ các cổng logic nhị phân nên có hiệu quả cao về phần cứng
  • Do dựa trên logic rời rạc nên có lợi thế về khả năng diễn giải và hiệu quả năng lượng

Differentiable Logic Cellular Automata (DiffLogic CA)

• Cấu trúc
  • Trên lưới 2D, mỗi ô có trạng thái n-bit và mô phỏng theo hai bước Perception → Update
  • Bước Perception
    • Xử lý thông tin lân cận (theo từng kênh) bằng kernel mạch logic
  • Bước Update
    • Kết hợp trạng thái hiện tại với kết quả Perception bằng một mạch logic khác để quyết định trạng thái ở thời điểm tiếp theo
• Đặc điểm
  • Mọi ô hoạt động như những bộ xử lý nhỏ, độc lập và phân tán
  • Huấn luyện bằng soft (xấp xỉ liên tục), suy luận bằng cổng hard (nhị phân) nên hiệu quả cao
  • Có cùng triết lý với các kiến trúc tính toán dựa trên CA như CAM-8

Experiment 1: Learning Game of Life

• Mục tiêu
  • Học quy tắc Conway's Game of Life bằng DiffLogic CA để kiểm tra xem có thể tái tạo hoàn toàn hay không
• Thiết lập
  • Dùng trạng thái ô 1 bit
  • Perception dùng 16 kernel (mỗi kernel có cấu trúc cổng 8→4→2→1)
  • Update có 23 lớp (16 lớp đầu 128 node, sau đó là [64, 32, 16, 8, 4, 2, 1])
  • Huấn luyện trên toàn bộ các trạng thái có thể có của lưới 3x3 (512 trường hợp) để dự đoán chính xác trạng thái ở bước tiếp theo
• Kết quả
  • Loss huấn luyện tiến gần về 0 và học hoàn hảo quy tắc cục bộ của Game of Life
  • Trên lưới lớn hơn, mô hình tái hiện được mọi mẫu như glider, block đúng như Game of Life thực sự
  • Trong mạch cuối cùng, các cổng AND và OR được dùng rất nhiều

Experiment 2: Pattern Generation

• Ví dụ checkerboard
  • Các ô có trạng thái 8 bit hình thành checkerboard 16x16 trong 20 bước
  • Perception có 16 kernel, Update có 16 lớp (tối đa 256 cổng)
  • Chỉ so sánh kênh cuối cùng với mẫu đích để tính loss
• Kết quả
  • Tạo ra checkerboard chính xác, và quy tắc được hiện thực gọn gàng chỉ với một số ít cổng
  • Trên lưới lớn gấp 4 lần, cùng quy tắc vẫn scale up và hoạt động ổn định
  • Ngay cả khi một số ô bị vô hiệu hóa vĩnh viễn, mẫu cũng không bị phá hỏng nhiều; khi khôi phục các ô đó, hệ thống tự chữa lành trở lại
• Asynchronicity
  • Dù huấn luyện với cập nhật bất đồng bộ, mô hình vẫn học checkerboard mà không gặp vấn đề
  • Quy tắc được huấn luyện đồng bộ cũng hoạt động tốt khi áp dụng vào suy luận bất đồng bộ
  • Quy tắc học theo cách bất đồng bộ có xu hướng phục hồi nhanh hơn trong tình huống có nhiễu hoặc hư hỏng

Experiment 3: Growing a Lizard

• Mục tiêu
  • Huấn luyện để hình thành đường viền một con thằn lằn 20x20 trong 12 bước, nhằm kiểm chứng khả năng tạo hình phức tạp
• Thiết lập
  • Trạng thái 128 bit
  • Perception có 4 kernel (mỗi kernel có cấu trúc cổng [8, 4, 2, 1]), Update có 10 lớp (8 lớp đầu 512 cổng, sau đó là [256, 128])
  • Đặt một ô hoạt động ở trung tâm lưới và dùng điều kiện biên tuần hoàn
• Kết quả
  • Trên lưới lớn hơn (40x40), con thằn lằn vẫn phát triển bình thường
  • Dù sử dụng rất nhiều cổng, mô hình vẫn có thể huấn luyện được nếu tinh chỉnh hyperparameter phù hợp

Experiment 4: Learning the G with colors

• Mục tiêu
  • Tạo một ảnh màu 16x16 gồm 3 kênh RGB trong 15 bước để kiểm chứng khả năng sinh mẫu đa kênh
• Thiết lập
  • Trạng thái 64 bit (3 kênh đầu dùng làm RGB, mỗi kênh là 0 hoặc 1)
  • Perception có 4 kernel (mỗi kernel là [8, 4, 2]), Update có 11 lớp (8 lớp đầu 512 cổng, sau đó là [256, 128, 64])
  • Ảnh đích là một mẫu chữ G 16x16 được tô bằng một trong 8 màu
• Kết quả
  • Loss được huấn luyện xuống gần 0, và sau 15 bước mô hình tái hiện chính xác chữ G màu mục tiêu
  • Mạch sử dụng nhiều cổng TRUE và FALSE, trong đó OR nổi bật hơn cả

Summary and Discussion

• Đã làm gì
  • Đề xuất DiffLogic CA, một mô hình CA hoàn toàn rời rạc nhưng có thể học được
  • Tái tạo các quy tắc cổ điển như Game of Life và cho thấy khả năng tạo mẫu như checkerboard, thằn lằn và chữ G màu
  • Do được cấu thành từ mạch logic rời rạc, mô hình hứa hẹn khả năng diễn giải trực quan và hiệu quả phần cứng
• Ý nghĩa
  • Chứng minh rằng các mẫu tự tổ chức như trong NCA cũng có thể được học bằng các cổng logic rời rạc
  • Khi xét đến các đặc tính như phục hồi sau hư hỏng hay cập nhật bất đồng bộ, mô hình có tiềm năng ứng dụng cao trong tính toán phân tán và chịu lỗi tốt (robust)
• Hạn chế và hướng tiếp theo
  • Khi học các ảnh hoặc mẫu phức tạp, vẫn cần tinh chỉnh hyperparameter phù hợp
  • Có thể tiếp tục khám phá các cổng kiểu LSTM hoặc cấu trúc giúp quên trạng thái hiệu quả để tạo ra các mẫu phong phú hơn
  • Có thể mở rộng theo hướng tối ưu quy mô mạch và cải thiện độ ổn định huấn luyện
• Kết luận
  • DiffLogic CA là một hướng tiếp cận đầy hứa hẹn có thể nối tiếp tới các định hướng tính toán phân tán mang tính lý thuyết như Programmable Matter hoặc Computronium
  • Vì vừa hoàn toàn rời rạc vừa có thể học được, nó có tiềm năng trở thành nền tảng cho các hệ thống phân tán trong tương lai

[GN⁺]

Ý kiến Hacker News

• Rất thú vị. Tôi đang sưu tầm các nền tảng máy Turing phổ dụng mới. Tôi sưu tầm chúng như Pokémon để phục vụ các thí nghiệm lập trình di truyền. Trước đây tôi từng dùng cellular automata (CA), nhưng cách tiếp cận này hấp dẫn hơn nhiều. Tôi chưa từng nghĩ đến việc mô hình hóa kernel như các mạch logic số
  • Logic Boolean, các cổng và các ràng buộc của mạch tạo ra một cấu trúc thú vị để hình thành fitness landscape. Các tham số kết quả có thể được chuyển thẳng sang hiện thực phần cứng hoặc, qua một bước tối ưu hóa bổ sung, biên dịch thành các chương trình đơn giản. Điều đó có vẻ tốt hơn những số thực dấu chấm động mang màu sắc phép thuật trong các hộp đen có hàng chục tỷ tham số
• Tôi thích dùng cellular automata cho nghệ thuật. Thật đáng kinh ngạc khi có thể xuất hiện những mẫu hình như vậy. Có lẽ tôi nên thử DLCA
• Rất thú vị. Tôi ấn tượng với câu hỏi mà Michael Levin nêu ra 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. Có một thí nghiệm trong đó các tế bào mắt của phôi ếch di chuyển về đúng vị trí ban đầu. Khi đó vẫn chưa có câu trả lời cho việc bằng cách nào các tế bào biết lúc nào nên dừng lại
  • Hiểu được tổ chức phi phân cấp là điều quan trọng để hiểu cách xã hội vận hành. Điều đó cũng quan trọng để giải quyết bài toán tiến thoái lưỡng nan của tù nhân ở nhiều quy mô khác nhau
  • Đây cũng là câu chuyện về việc hiểu và mô hình hóa độ phức tạp
  • Lần đầu tiên tôi thấy khả năng có thể mô hình hóa những thứ như thế này. Nó có thể đi theo rất nhiều hướng. Thật đáng kinh ngạc
• Gần đây tôi suy nghĩ rất nhiều về "trí thông minh". Có vẻ như chúng ta đang ở một thời điểm mang tính quyết định để hiểu cách trí thông minh hoạt động. Trí thông minh là một hành vi phát sinh tự nhiên, không quá khác biệt so với cơ học Newton cổ điển hay điện. Cuối cùng nó quy về những quy tắc đơn giản
  • Nếu mọi thứ không rời rạc trong não chỉ là "hạ tầng" thì sao? Nếu nó chỉ là thứ hỗ trợ cho một quá trình cốt lõi vốn đơn giản nhưng quan trọng, thứ thực sự thực hiện công việc? Nếu mọi thứ cuối cùng đều quy về các cổng logic và tín hiệu điện thì sao?
  • Một thời đại thú vị đang đến gần
• Chúng đặc biệt hấp dẫn ở năng lực khái quát hóa. Nhưng tầm nhìn là gì? Trong tương lai chúng ta có thể làm gì với chúng? Về mặt triết học, chúng sẽ dạy cho chúng ta điều gì về thế giới? Tôi biết rằng cellular automata 1D tương đương Turing. Vì vậy NCA/những thứ này không quá gây ngạc nhiên
• Đây là một phát hiện đột phá. Nó không phải chuyện bàn cờ caro hay thằn lằn. Phương trình vi phân Navier-Stokes là quy tắc cập nhật chi phối chuyển động của chất lưu. Mọi độ phức tạp như sự hình thành mây hay chuyển động của ngọn lửa đều bị chi phối bởi những định luật đơn giản. Việc khám phá ra phương trình này thông qua các mẫu thực tế chính là khoa học. Ta có thể áp dụng mô hình DLCA vào bản ghi video khói để suy ra phương trình Navier-Stokes. Nếu xét thêm khả năng chính quy tắc cập nhật cũng có thể thay đổi theo những quy tắc cập nhật khác, ta sẽ bước vào một vùng rất thú vị. Đó có thể là lý do các neuron trong não kết nối với hàng nghìn neuron khác
  • Các lãnh đạo Google sẽ gạt phát hiện này đi vì nó không liên quan đến mảng quảng cáo của họ. Vài năm nữa, khi DLCA đảo lộn thế giới, họ sẽ tuyên bố rằng nhân viên của họ đã phát hiện ra nó
• Một bài báo rất thú vị. Tôi có một câu hỏi: vì các cập nhật được thực hiện bằng gradient descent "toàn cục", nên các cổng của ô không thật sự song song
  • Có hướng khả thi nào cho một phương pháp điều chỉnh trọng số mang tính cục bộ nghiêm ngặt không?
• Việc nới lỏng liên tục của đại số Boole là một ý tưởng cũ. Tổng hợp mạch là một lĩnh vực đã được nghiên cứu kỹ. Google đã thắng cuộc thi này từ 2 năm trước. Tôi tự hỏi họ đã thử áp dụng learner lên bộ dữ liệu của cuộc thi IWLS chưa. Nếu chưa, tại sao lại chưa?
• Có thể dùng cho thử thách ARC-AGI không? Có thể kết hợp với thứ gần đây không?
• Hơi tự quảng bá nhưng có liên quan => Robustness and the Halting Problem in Multicellular Artificial Development (2011)
  • Cellular automata trong đó quy tắc cập nhật được kết hợp từ perceptron và khuếch tán đẳng hướng. Trọng số của mạng nơ-ron được tối ưu hóa để cellular automata có thể vẽ hình. Có khả năng tự phục hồi (tức là tái tạo lại hình khi bị can thiệp)
  • Khi đó, automatic differentiation chưa dễ tiếp cận như bây giờ. Chúng tôi đã tối ưu hóa trọng số bằng evolutionary strategies. Tất nhiên, dùng gradient descent sẽ tốt hơn nhiều