Ask HN: Machine learning for boolean functions?

[manx]

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?

[th3h3x]

This 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/asplo... [2]https://www.usenix.org/system/files/conference/usenixsecurit...