Sampling and Learning for Boolean Function
This work addresses the challenge of efficient learning in universal machines, though it appears incremental as it builds on previous studies with new tools and strategies.
The authors tackled the problem of universal learning by introducing new tools for Boolean functions and circuits, establishing a relationship between proper sampling sets and circuit complexity, and demonstrating that their learning strategies achieve universal learning with significantly reduced data requirements.
In this article, we continue our study on universal learning machine by introducing new tools. We first discuss boolean function and boolean circuit, and we establish one set of tools, namely, fitting extremum and proper sampling set. We proved the fundamental relationship between proper sampling set and complexity of boolean circuit. Armed with this set of tools, we then introduce much more effective learning strategies. We show that with such learning strategies and learning dynamics, universal learning can be achieved, and requires much less data.