Space of Functions Computed by Deep-Layered Machines

Area of Science:

• Theoretical computer science
• Machine learning theory
• Information theory

Background:

• Random-layered machines, including deep neural networks (DNNs) and Boolean circuits, are fundamental computational models.
• Understanding the function space these models compute is crucial for advancing AI and complexity theory.
• Previous research has explored their capabilities, but a unified analysis of their function distribution and entropy behavior across different architectures remains incomplete.

Purpose of the Study:

• To analyze and compare the space of Boolean functions computed by random-layered machines.
• To investigate the distribution of functions in recurrent and layer-dependent architectures.
• To characterize the behavior of function space and macroscopic entropy in the large depth limit.

Main Methods:

• Mathematical analysis of function distributions in random-layered machines.
• Comparison of function spaces in recurrent versus layer-dependent architectures.
• Characterization of function space and entropy at large depths, considering initial conditions and computing elements.

Main Results:

• The distribution of Boolean functions computed by recurrent and layer-dependent architectures is identical.
• The space of functions computed at the large depth limit is characterized based on initial conditions and computing elements.
• Macroscopic entropy of Boolean functions exhibits monotonic increase or decrease with growing depth.

Conclusions:

• Deep neural networks and Boolean circuits compute the same distribution of functions.
• The depth of random-layered machines significantly impacts the macroscopic entropy of computed Boolean functions.
• This finding offers insights into the computational power and complexity of deep learning models and circuit designs.