Learnability of the Boolean Innerproduct in Deep Neural Networks

Area of Science:

• Computational neuroscience
• Machine learning theory

Background:

• Boolean inner product functions are fundamental in computational learning theory.
• Deep neural networks (DNNs) offer potential for efficient representation, but their trainability is a key concern.
• Previous work shows depth 3 networks can represent these functions compactly, unlike shallower networks.

Purpose of the Study:

• To investigate the learnability of Boolean inner product functions using deep neural networks.
• To evaluate the impact of network architecture on training difficulty and accuracy.
• To identify strategies for improving the training of compact deep network representations.

Main Methods:

• Systematic simulation study of Boolean inner product function learnability.
• Comparison of depth 2 and depth 3 neural network architectures with threshold neurons.
• Analysis of training performance across varying input dimensions (n≤16).
• Exploration of architectural modifications: partially connected layers and additional hidden units.

Main Results:

• Depth 3 networks, while theoretically compact, proved significantly harder to train than depth 2 networks for small input sizes.
• Average accuracy reached 94% with increasing input dimensions, suggesting the potential of deep architectures.
• Replacing fully connected layers with partially connected (convolutional-like) layers improved accuracy to 99%.
• Adding a few units to the first hidden layer also enhanced learnability.

Conclusions:

• Deep neural network architectures, specifically depth 3, are powerful for representing Boolean inner product functions but present training challenges.
• Architectural innovations, such as sparse connectivity and layer augmentation, are crucial for overcoming training difficulties and achieving high performance.
• The findings support the utility of deep learning for complex computational problems and highlight avenues for future research in efficient training algorithms.