3 ms·
Ask HN: Machine learning for boolean functions?
The machine learning tools I know work very well for continuous classification problems. I am wondering if there are any algorithms to learn arbitrary boolean functions from a training set. Basically this is a binary classification problem where the input consists of boolean values. How would you approach this problem?
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- th3h3x 9y agoThis is known as stochastic program synthesis. The training set consists of a set of input-output samples; the synthesizier tries to find a Boolean function that maps all inputs to their corresponding outputs. One algorithm that can be used for that is Markov Chain Monte Carlo (MCMC) [1]. Another approach is based on Monte Carlo Tree Search (MCTS) [2]. In the second algorithm, you define a grammar that describes possible program moves. Then, MCTS builds incrementally builds the search tree towards more promising programs. A more promising candiate program is a program that has a more similar I/O behavior than another one (based on the training set). [1]https://theory.stanford.edu/~aiken/publications/papers/asplos13.pdf https://theory.stanford.edu/~aiken/publications/papers/asplo... [2]https://www.usenix.org/system/files/conference/usenixsecurity17/sec17-blazytko.pdf https://www.usenix.org/system/files/conference/usenixsecurit...