Learning to Discover Efficient Mathematical Identities

By Wojciech Zaremba, Karol Kurach, Rob Fergus. 2014

57 citations recorded by the source corpus.

In this paper we explore how machine learning techniques can be applied to the discovery of efficient mathematical identities. We introduce an attribute grammar framework for representing symbolic expressions. Given a grammar of math operators, we build trees that combine them in different ways, looking for compositions that are analytically equivalent to a target expression but of lower computational complexity. However, as the space of trees grows exponentially with the complexity of the target expression, brute force search is impractical for all but the simplest of expressions. Consequently, we introduce two novel learning approaches that are able to learn from simpler expressions to guide the tree search. The first of these is a simple n-gram model, the other being a recursive neural-network. We show how these approaches enable us to derive complex identities, beyond reach of brute-force search, or human derivation.

Subfields: Artificial Intelligence, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Natural Language Processing

Citations in the corpus

Learning to Execute (2014, methodology): “Figure 3 shows the LSTM equations (the ﬁgure is taken from Zaremba et al. (2014b)).”
Deep Learning for Symbolic Mathematics (2019, background): “Zaremba et al. (2014) use recursive neural networks to simplify complex symbolic expressions.”
Learning Continuous Semantic Representations of Symbolic Expressions (2016, methodology): “Our work in similar in spirit to the work of Zaremba et al. (2014), who focus on learning expression representations to aid the search for computationally efﬁcient identities.”
Learning to Perform Local Rewriting for Combinatorial Optimization (2018, methodology): “For expression simplification, some recent work use deep neural networks to discover equivalent expressions [11, 2, 52].”
Can Neural Networks Understand Logical Entailment? (2018, background): “Zaremba et al. (2014) show how a neural architecture can be used to optimise matrix expressions.”
Learning Program Embeddings to Propagate Feedback on Student Code (2015, methodology): “Our models are related to recent work from the NLP and deep learning communities on recursive neural networks, particularly for modeling semantics in sentences or symbolic expressions (Socher et al., 2013; 2011; Zaremba et al., 2014; Bowman, 2013).”
Extrapolation and learning equations (2016, methodology): “In [Zaremba et al., 2014] this was done using machine learning to overcome the potentially exponential search space.”
Dynamic Neural Program Embedding for Program Repair (2017, background): “As for learning representations, there are several related efforts in modeling semantics in sentence or symbolic expressions (Socher et al., 2013; Zaremba et al., 2014; Bowman, 2013).”
Learning Equations for Extrapolation and Control (2018, methodology): “In (Zaremba et al., 2014), this was done using machine learning to overcome the potentially exponential search space.”
Protein Secondary Structure Prediction with Long Short Term Memory Networks (2014, methodology): “The LSTM cell is implemented as described in [Graves, 2013], however without peepholes, because recent papers have shown good performance without peepholes [Sutskever et al., 2014; Zaremba & Sutskever, 2014; Zaremba et al., 2014].”
Memory Augmented Recursive Neural Networks (2019, methodology): “…data in many applications including nat-ural scene classiﬁcation (Socher et al., 2011), sentiment classiﬁcation, Semantic Relatedness and syntactic parsing (Tai et al., 2015; Socher et al., 2011), neural programming and logic (Allamanis et al., 2017; Zaremba et al., 2014; Evans et al., 2018).”