In this master's thesis, we address the problem of discovering mathematical equations from data. We generate expressions using a probabilistic context-free grammar and formally frame the problem of searching for them within the framework of Markov decision processes. Since the search space of expressions is too large for exhaustive search, we approximate the optimal policy using Monte Carlo tree search, selecting actions with the UCT or PUCT strategy.
We develop the Grams method, which searches the space of expressions using Monte Carlo tree search and rewards expressions based on a predefined utility function. On a simple grammar, we show that Grams finds expressions with high values of the utility function based on the Gini index considerably faster than random sampling. We then evaluate the method on a set of 100 Feynman equations and compare it to random sampling, as implemented in the ProGED library. We determine the utility function either through an approximation of the logarithm of the posterior probability of the expression, or directly as the negative RMSE. The analysis shows that the choice of the exploration parameter and the utility function strongly affects search performance.
|
