Sampling and Learning for Boolean Function

2020/01/21 by Chuyu Xiong, Xiong, Chuyu · 1 citation
Computer Science · #Machine Learning and Algorithms #Algorithms and Data Compression #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2001.07317

Abstract

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.

Cited by

• Sampling and Complexity of Partition Function

Related

• A new approach in machine learning
• A Circuit Complexity Formulation of Algorithmic Information Theory
• From Exact Learning to Computing Boolean Functions and Back Again
• The Probably Approximately Correct Learning Model in Computational Learning Theory
• Generalization on the Unseen, Logic Reasoning and Degree Curriculum