Differentiable Logic Cellular Automata

 (google-research.github.io)
1 पॉइंट द्वारा GN⁺ 2025-03-08 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • DiffLogic CA Neural Cellular Automata और Differentiable Logic Gate Networks को जोड़कर cellular automata का ऐसा तरीका पेश करता है, जो discrete cell state बनाए रखते हुए भी gradient-based तरीके से local rules सीखता है
  • हर cell की state n-dimensional binary vector होती है, और perception phase व update phase दोनों को logic gate network से process करके अगली state सीधे compute की जाती है
  • Conway के Game of Life experiment में 3x3 periodic grid की 512 configurations को एक step के लिए train करके पूरा rule सीखा गया, और hard inference में भी glider, block, loaf, boat जैसे representative patterns reproduce हुए
  • Pattern generation experiment ने 16x16 checkerboard को 20 steps में बनाया, और 4 गुना बड़ी grid व 4 गुना लंबे time पर भी काम किया; damaged cells के लिए fault tolerance और reactivation के बाद self-repair दिखा
  • इसने ज्यादा complex lizard outline और 8-color RGB G भी generate किया, लेकिन complex structures सीखने के लिए काफी hyperparameter tuning की जरूरत पड़ी; hierarchical NCA और LSTM जैसी gates सुधार के candidate रहे

DiffLogic CA किस समस्या को target करता है

  • Cellular automata को आम तौर पर पहले local rules तय करके, उनके परिणामस्वरूप दिखने वाले emergent patterns को observe करने के तरीके से扱ा जाता है
  • DiffLogic CA यह explore करता है कि जब कोई desired complex pattern हो, तो उसे बनाने वाले local rules को fully differentiable तरीके से कैसे सीखा जाए
  • मौजूदा Neural Cellular Automata arbitrary patterns और behavior सीख सकते हैं, लेकिन वे मूल रूप से discrete state space में operate नहीं करते, जिससे interpretability घटती है और continuous state updates में matrix multiplication की cost आती है
  • Differentiable Logic Gate Networks combinational logic circuits खोजने में इस्तेमाल हुए हैं, लेकिन space और time दोनों में recursive NCA setting में उनका behavior अभी साबित नहीं हुआ था
  • पूरा experiment notebook में reproduce किया जा सकता है

Neural Cellular Automata की basic structure

  • Neural Cellular Automata classic cellular automata में deep learning को जोड़ते हैं, ताकि हाथ से rules design करने के बजाय gradient descent से update rules सीखे जा सकें
  • Growing-NCA में हर cell के पास 2D grid पर n-dimensional state vector होता है
    • RGB के 3 channels cell का color दिखाते हैं
    • Alpha channel cell की viability दिखाता है; alpha value 0.1 से ज्यादा हो तो cell को alive माना जाता है
    • बाकी hidden channels आसपास के environment के बारे में ज्यादा complex information ले जाते हैं
  • Update दो phases में होता है
    • Perception phase: Sobel filter को channel-wise apply करके spatial gradients को approximate किया जाता है, और cell की current state व neighborhood information को मिलाकर perception vector बनाया जाता है
    • Update phase: करीब 8,000 parameters वाला neural network सभी cells पर समान रूप से apply होता है और तय करता है कि हर cell कैसे बदलेगा
  • सभी operations differentiable हैं, इसलिए पूरा system किसी specific pattern या behavior को सीख सकता है

Differentiable Logic Gate Networks का तरीका

  • Deep Differentiable Logic Gate Networks artificial neurons के बजाय AND, OR, XOR जैसे logic gates को basic unit के रूप में इस्तेमाल करते हैं
  • Network gate layers से बना होता है, और हर gate sparse structure में previous layer के दो gates से input लेता है
  • Connections random तरीके से initialize होते हैं और training के दौरान बदलते नहीं; training सिर्फ यह तय करती है कि हर gate कौन-सा logical operation perform करेगा
  • Training के दौरान discrete logic gates को सीधे इस्तेमाल नहीं किया जाता, बल्कि दो mechanisms इस्तेमाल होते हैं
    • Continuous relaxation: hard AND जैसे discrete operations को 0 और 1 के बीच inputs लेने वाले differentiable versions से replace किया जाता है
    • Stochastic gate selection: हर gate के पास दो inputs पर possible 16 binary operations की probability distribution होती है, और softmax से expressed 16-dimensional parameters सीखे जाते हैं
  • Training खत्म होने पर हर gate सबसे high probability वाले operation पर fixed हो जाता है, और inference में सिर्फ pure binary operations करता है
  • Training stability के लिए initial gate distribution को pass-through gates की तरफ biased रखा जाता है

DiffLogic CA की structure

  • DiffLogic CA NCA की 2D grid structure follow करता है, लेकिन हर cell की state को n-dimensional binary vector के रूप में represent करता है
  • Cell state और channels एक ही अर्थ में इस्तेमाल होते हैं, और binary state vector पिछले iterations की information store करने वाली working memory की तरह काम करता है
  • Perception phase Sobel filter के बजाय logic gate network-based kernels इस्तेमाल करता है
    • हर kernel fixed connection structure वाला अलग circuit होता है, और gate types सीखे जाते हैं
    • Kernel channel-wise compute होता है
    • हर circuit center cell और neighboring cells के interactions compute करने के लिए designed 4 layers इस्तेमाल करता है
  • Update phase cell की previous memory और neighbors से मिली information को concatenate करके input को Differentiable Logic Gate Network में डालता है और नई state compute करता है
  • Standard NCA की तरह state को धीरे-धीरे जोड़ने वाला ODE-style update नहीं है, बल्कि अगली binary state सीधे output होती है
  • एक round का operation दो registers के रूप में देखा जा सकता है
    • Gray register में existing cell state होती है
    • Orange register में perception phase का result store होता है
    • Update के बाद नई state gray register में लिखी जाती है, और orange register अगले round के लिए खाली किया जाता है
  • यह structure ऐसे छोटे independent computers के network की तरह operate करता है, जहां हर cell neighbors से communicate करता है और observations के आधार पर decision लेता है

Experiment 1: Conway का Game of Life सीखना

  • Game of Life एक binary cellular automaton है जिसमें हर cell 8 neighbors की state और अपनी current state के आधार पर next generation में जीवित रहता है या मरता है
  • Rules चार हैं
    • Dead cell के ठीक 3 alive neighbors हों तो वह next generation में alive हो जाता है
    • Alive cell के 2 या 3 alive neighbors हों तो वह survive करता है
    • Alive cell के neighbors 2 से कम हों तो वह मर जाता है
    • Alive cell के neighbors 3 से ज्यादा हों तो वह मर जाता है
  • यह experiment ऐसे rule पर target करता है जो previous state iterations पर depend नहीं करता, इसलिए cell state 1 bit set की गई
  • Model configuration इस प्रकार है
    • 16 perception circuit kernels
    • हर perception kernel का node structure [8, 4, 2, 1]
    • Update network में 23 layers
    • पहली 16 layers में हर एक में 128 nodes
    • बाद की layers [64, 32, 16, 8, 4, 2, 1]
  • Training data में 3x3 periodic grid की सभी possible 512 configurations शामिल हैं
    • हर cell की next state उसकी अपनी और 8 neighbors की state से तय होती है, इसलिए 3x3 configurations 512 होती हैं
    • एक step की next state को पूरी तरह match करना Game of Life का पूरा rule सीखने के बराबर है
  • Loss function predicted grid और ground-truth grid के squared difference का sum है
  • Soft loss और hard loss दोनों पूरी तरह converge हुए, और hard inference में learned circuit ने बड़ी grids पर भी Game of Life patterns reproduce किए
  • Active gates की संख्या pass-through A और B को छोड़कर 336 थी, और perception network व update network में OR और AND सबसे ज्यादा इस्तेमाल हुए
  • Generated circuit के साथ Game of Life circuit पर सीधे interact किया जा सकता है

Experiment 2: Checkerboard pattern generation

  • Pattern generation experiment को arbitrary initial state से target image में evolve होने वाले rules सीखने के लिए set किया गया
  • Loss केवल final timestep पर compute होता है, इसलिए model को intermediate step-wise supervision के बिना discrete transition rules खोजने होते हैं
  • Cell state 8-bit है, और DiffLogic CA 20 steps repeat होता है
  • Model configuration इस प्रकार है
    • 16 perception circuit kernels
    • हर kernel में layer-wise 8, 4, 2 gates हैं
    • Update network में 16 layers
    • पहली 10 layers में हर एक में 256 gates
    • बाद की layers [128, 64, 32, 16, 8, 8]
  • Loss function final timestep पर predicted grid के first channel और target grid के बीच squared difference का sum है
  • Model को 16x16 checkerboard pattern 20 steps के अंदर restore करना सिखाया गया
  • Soft loss और hard loss दोनों converge हुए, और first channel में clear pattern formation दिखी
  • Model में built-in direction bias नहीं था, लेकिन pattern bottom-left से top-right की तरफ propagate होने की property दिखी
  • Active gates की संख्या pass-through A और B को छोड़कर 22 थी, और pruning के बाद पूरा checkerboard generation function practically 5 logic gates से implement किया जा सकता था
  • 4 गुना बड़ी grid और 4 गुना लंबे time तक scale करने पर भी circuit काम करता रहा, और learned rules किसी specific grid size पर overfit नहीं थे

Damage, self-repair, और asynchronous update

  • Checkerboard experiment में कुछ cells के fail होने की situation मानकर दो damage experiments किए गए
    • बड़े area के cells को permanently deactivate करके faulty components simulate किए गए
    • कुछ steps के बाद inactive cells को फिर activate किया गया
  • System ने permanent damage की situation में भी pattern integrity बनाए रखी, और inactive cells के फिर online होने के बाद सही pattern फिर generate किया
  • Fault tolerance और self-repair को explicitly design नहीं किया गया था, फिर भी damage localized रहा और overall functionality अचानक collapse नहीं हुई
  • Asynchronous update experiment में सभी cells को एक साथ update करने के बजाय, हर step पर random subset of cells को ही update किया गया
  • Asynchronous learning को existing NCA से ज्यादा difficult माना गया था
    • हर step पर incremental नहीं, बल्कि पूरी new state output करनी होती है
    • Nearby cells के अलग-अलग steps से आगे या पीछे होने वाले combinations handle करने होते हैं
  • Checkerboard में asynchronous learning relatively आसानी से सफल हुई, और समान initial state से अलग update orders इस्तेमाल करने पर भी 50 steps के भीतर target pattern reconstruct हुआ
  • Synchronously learned existing rules को asynchronous inference में apply करने पर भी काम हुआ
  • हर inference timestep पर image area के भीतर 10x10 pixel rectangle को randomly deactivate करने वाले test में, asynchronously learned cells damage से थोड़ा तेजी से recover हुए
  • Target और reconstructed image के absolute difference sum से error measure करने पर, asynchronous learning ने ऐसी disturbances के खिलाफ robustness बढ़ाई

Experiment 3: lizard outline growth

  • Lizard experiment original NCA work को homage था, और यह जांचता है कि DiffLogic CA arbitrary shapes सीख सकता है या नहीं
  • Checkerboard जैसे highly compressible regular pattern के बजाय, lizard outline ज्यादा memorization मांगता है
  • Setup इस प्रकार है
    • Cell state 128-bit है
    • DiffLogic CA 12 steps repeat होता है
    • 4 perception circuit kernels
    • हर kernel में layer-wise 8, 4, 2, 1 gates हैं
    • Update network में 10 layers
    • पहली 8 layers में हर एक में 512 gates
    • Last layers [256, 128]
  • Model को 20x20 lizard pattern 12 steps के भीतर generate करना सिखाया गया
  • Initial condition NCA की तरह symmetry तोड़ने के लिए central seed है, और grid edges पर periodic boundary conditions apply होते हैं
  • 40x40 बड़ी grid पर evaluate करने पर भी lizard growth pattern successfully generate हुआ, जिससे दिखा कि solution boundary conditions का उपयोग करने वाला नहीं था
  • Soft loss और hard loss दोनों 0 पर converge हुए
  • Active gates की संख्या pass-through A और B को छोड़कर 577 थी
  • Perception kernels ने मुख्य रूप से TRUE gates इस्तेमाल किए, और update circuit ने लगभग सभी available gates इस्तेमाल किए
  • Complex pattern generation learning optimization में difficult है और extensive hyperparameter tuning की जरूरत पड़ी

Experiment 4: Colored G generation

  • पहले experiments effectively monochrome images पर focused थे, इसलिए ज्यादा complex target state के रूप में 16x16 color image generate करने का experiment किया गया
  • Cell state 64-channel है, और model 15 steps तक colored alphabet G generate करता है
  • पहले तीन channels standard NCA convention की तरह RGB values दिखाते हैं, लेकिन यहां हर value 0 या 1 वाली binary representation तक सीमित है, जिससे 8-color palette बनता है
  • Model configuration इस प्रकार है
    • 4 perception circuit kernels
    • हर kernel 8, 4, 2 gates वाली 3 layers से बना है
    • Update network में 11 layers
    • पहली 8 layers में हर एक में 512 nodes
    • Last 3 layers [256, 128, 64]
  • Initial state पूरी तरह 0 है, और periodic boundary conditions इस्तेमाल नहीं किए गए
  • Loss function final timestep पर पहले तीन channels, यानी channel 0, 1, 2, के लिए predicted grid और target grid के squared difference का sum है
  • Soft loss और hard loss converge हुए, और model ने 15 steps के भीतर colored G reconstruct किया
  • Active gates की संख्या pass-through A और B को छोड़कर 927 थी
  • TRUE और FALSE gates perception network और update network दोनों में काफी इस्तेमाल हुए, और update network में OR gates सबसे ज्यादा इस्तेमाल हुए
  • यह circuit पिछले experiments की तुलना में hyperparameter search और circuit size दोनों में ज्यादा complex था

Remaining tasks और improvement directions

  • DiffLogic CA fully discrete cell state इस्तेमाल करता है और learned recursive binary circuits से state update करने वाला नया NCA structure और learning method propose करता है
  • Neural network components को Deep Differentiable Logic Networks से replace करके, यह discrete logic gates में differentiable learning की flexibility जोड़ता है
  • Game of Life replication और pattern generation experiments दिखाते हैं कि differentiable logic gates को cellular automata पर apply किया जा सकता है
  • परिणामस्वरूप यह confirm हुआ कि Differentiable Logic Gate Networks recursive structures में भी effectively सीख सकते हैं
  • Current model ने pattern learning की संभावना दिखाई है, लेकिन ज्यादा complex shapes और structures generate करना सीखना अभी भी difficult है
  • Improvement directions में hierarchical NCA structures और state forgetting में मदद करने वाले special gates propose किए गए हैं
  • LSTM जैसी gating mechanism को state update process में integrate करने से past state और newly computed candidate state को ज्यादा rich तरीके से combine किया जा सकता है, जिससे model dynamics और expressiveness बढ़ सकते हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-03-08
Hacker News की रायें

  • बेहद दिलचस्प। मैं नए universal Turing machine substrates ढूंढ रहा था और genetic programming प्रयोगों के लिए उन्हें Pokémon की तरह इकट्ठा कर रहा था। पहले cellular automata के साथ भी rule 30/110 वगैरह पर हाथ आजमाया था, लेकिन यह approach कहीं ज्यादा भरोसेमंद लगती है
    kernel को digital logic circuit की तरह model करने का विचार मेरे दिमाग में नहीं आया था। Boolean logic, gates और circuits की constraints fitness landscape बनाने में दिलचस्प texture देती लगती हैं। नतीजे के parameters को सीधे hardware implementation में बदला जा सकता है, या एक अतिरिक्त optimization step के बाद साधारण program में compile किया जा सकता है। यह अरबों parameters वाले black box के अंदर के किसी जादुई floating point से निपटने से बेहतर लगता है

    • यह paper सच में बहुत महत्वपूर्ण लगता है। automata को differentiable बनाने से Boolean circuit design पर backpropagation optimization लागू करके जटिल discrete system behavior सीखा जा सकता है। यह कमाल की बात है
    • difflogic देखना चाहिए। differentiable neural network logic circuits को CUDA या C code में compile किया जा सकता है। इसका प्रमुख demo एक MNIST classifier है जो CPU पर प्रति सेकंड 10 लाख से ज्यादा images process करता है

  • रोमांचक। Michael Levin ने यह सवाल सबसे अच्छी तरह रखा है कि animal cells बिना hierarchy के कैसे सहयोग कर सकती हैं। उदाहरण के लिए, biology experiments हैं जिनमें frog embryo की eye cells को हटाने पर भी वे उस जगह migrate करती हैं जहां आंख होनी चाहिए
    मेरे हिसाब से जिस सवाल का वह ठीक से जवाब नहीं दे पाए, वह था कि cells को कैसे पता चलता है कि कब रुकना है। non-hierarchical organization को समझना समाज के काम करने के तरीके, और self-organized दुनिया के कई scales पर prisoner’s dilemma हल करने के लिए भी अहम है। यह raw complexity को समझने और model करने का काम भी है। ऐसी चीजों को model करने की क्षमता मैंने पहली बार देखी है, और यहां से आगे बढ़ने की सच में बहुत सारी दिशाएं दिखती हैं

    • हो सकता है मैं कोई obvious बात miss कर रहा हूं, लेकिन सोच रहा हूं कि इसे introductory textbooks में बताए जाने वाले जाने-पहचाने chemical gradient mechanism से क्यों handle नहीं किया जाता। मूल रूप से cells कई overlapping chemical gradients के भीतर direction पकड़ती हैं, और वे gradients बार-बार compose होते हैं, हर iteration में ज्यादा complex spatial behavior दिखाते हुए
    • Michael Levin interview Cognitive Light Cones: https://www.youtube.com/watch?v=YnObwxJZpZc

  • इन दिनों intelligence के बारे में बहुत सोच रहा हूं, और लगता है कि हम उस निर्णायक मोड़ पर हैं जहां हम यह पता लगा सकते हैं कि intelligence कैसे काम करती है, या कम से कम उसकी समझ में बड़ा कदम आगे बढ़ा सकते हैं। intelligence classical Newtonian mechanics या electricity से बहुत अलग नहीं, बल्कि naturally emergent behavior जैसी लगती है
    आखिरकार बात simple rules तक सिमटती दिखती है। क्या हो अगर brain में जो कुछ discrete नहीं है, वह असल में सिर्फ infrastructure हो, जो वास्तविक काम करने वाली simple लेकिन crucial core processes को support करता है? और अंत तक जाएं तो अगर सब logic gates और electrical signals ही हों? आगे का समय दिलचस्प होने वाला है

  • इस approach में खासकर generalization ability के लिहाज से आकर्षक बातें हैं। लेकिन बड़ी vision क्या है, यह जानने की इच्छा है। आगे इससे हम क्या कर पाएंगे? philosophically यह दुनिया के बारे में हमें क्या सिखाता है? हम पहले से जानते हैं कि 1D cellular automata Turing-equivalent हैं, इसलिए एक नजरिए से NCA या ऐसे तरीके बहुत चौंकाने वाले नहीं हैं

    • अगर satellite images से grid input लेकर wildfire spread या pollution spread जैसी समस्याओं को simulate किया जा सके, तो यह उपयोगी हो सकता है
    • energy consumption के लिहाज से ये bacteria, plants और humans से आगे पृथ्वी की dominant life form बन जाएंगे, ऐसा लगता है
      environment के साथ interact करने वाले cellular automata, और low-level systems तथा high-level institutions दोनों के साथ interact करने वाले automata आएंगे। कुछ approximation तक humans भी ऐसे network में interact करने वाली individual cells ही हैं। intelligence का भविष्य LLM नहीं, बल्कि metabolic aspects वाले automata systems हैं। ऐसे automata जो साथ evolve करते हैं, energy consume करते हैं, value produce करते हैं, compete करते हैं और एक-दूसरे को model करते हैं
      हम replace नहीं हो रहे हैं; बल्कि एक transformation में भाग ले रहे हैं जिसमें technological systems और cellular systems की boundary धुंधली होकर आखिरकार गायब हो जाती है। इसे देख पाने के लिए मैं बहुत आभारी हूं। संदर्भ: https://x.com/zzznah/status/1803712504910020687
    • self-healing properties biological evolution की याद दिलाती हैं

  • art projects में cellular automata से खेलना मुझे पसंद है। यह हैरान करता है कि कौन से patterns emerge हो सकते हैं। उदाहरण: https://gods.art/math_videos/hex_func27l_21.html
    लगता है इस DLCA को भी एक बार आजमाना चाहिए

    • सोच रहा हूं कि क्या ये patterns अनंत तक generate होते रहते हैं
    • पुरानी film Andromeda Strain याद आती है

  • इसमें कई शानदार ideas हैं। छोटा observation हो सकता है, लेकिन यह computation stateful है। हर cell के पास memory और अपने surrounding environment की perception है
    दूसरी तरफ modern neural networks आम तौर पर stateless होते हैं। उदाहरण के लिए, सोच रहा हूं कि stateful LLMs पर कोई research हुई है या नहीं

  • self-promotion है, लेकिन बहुत relevant: Robustness and the Halting Problem for Multicellular Artificial Ontogeny(2011)
    यह ऐसा cellular automata था जिसमें update rule एक perceptron था, जिसे isotropic diffusion के साथ जोड़ा गया था। neural network weights को optimize करके cellular automata से image बनवाई गई, और disturbance होने पर image को फिर से बनाने वाली self-healing capability भी दी गई। उस समय automatic differentiation आज की तरह accessible नहीं था, इसलिए weights को evolutionary strategies से optimize किया था। जाहिर है, gradient descent इस्तेमाल करने पर काफी बेहतर होने की संभावना है

  • क्या इसे ARC-AGI Challenge में इस्तेमाल किया जा सकता है? शायद इसे इस हालिया approach के साथ combine भी किया जा सकता है: https://news.ycombinator.com/item?id=43259182

  • सचमुच कमाल। लंबे समय से सिर्फ पढ़ता रहा हूं, और modeling व simulation का काफी इस्तेमाल करने वाले व्यक्ति के तौर पर, complex actor behavior models के emergent behavior को बेहतर समझने की इसमें बड़ी potential दिखती है
    predator/prey models जैसी चीजों पर, और उन दूसरे models पर इसे लागू होते देखना चाहूंगा जो simple दिखते हैं लेकिन बड़े scale पर complex emergent results पैदा करते हैं। मैं इस work पर नजर बनाए रखूंगा

  • result का checkerboard pattern target pattern का उल्टा, यानी NOT जैसा दिखता है। लेकिन इसका कोई mention नहीं है। सोच रहा हूं कि क्या यह mention करने लायक important नहीं है, या मैं कुछ miss कर रहा हूं

    • पकड़ने के लिए धन्यवाद। publication के लिए export करने की प्रक्रिया में target image invert हो गई थी, और अब इसे ठीक कर दिया गया है
    • यह exact image नहीं, बल्कि features सीख रहा है। इसलिए self-healing अच्छी तरह होती है, और इसे translation के प्रति भी invariant होना चाहिए