Invariant Representation of Mathematical Expressions

Motivation

Looking at the following two expressions, we can tell that they are expressing the same symbolic mathematical relationship, even though they look quite different.

a² + b² + 2ab

(x+y)²

How do we capture this similarity? Part of the problem is that the same expression can appear in factored form, (a+b)², or expanded form, a² + b² + 2ab. Thankfully, there exist libraries and platforms that can easily rewrite the expression from one form to the other (e.g. Maple and SymPy). Therefore, as long as we consistently encode every expression in the same form, this should not be of concern. The more cumbersome issue is that one expression is stated in terms of a and b while the other is expressed via x and y. Since we already have the means of resolving the identity, let us reformulate the problem and focus on the issue that requires our attention:

a² + b

x + y²

Note that the isomorphy of the two expressions is in the structure of the algebraic operation they suggest, which in words would be something along ”one variable plus the square of another variable”. Therefore, what we need is to encode the expression in such a way that exposes this structure.

We propose to use a modified form of the expression tree for this purpose, namely, a convenient way to represent the structure of a mathematical expression. The useful property of such a graph is that it makes explicit the property of interest, which is otherwise only implied in the nominal representation of the above expressions. Once we have the desired graph, then the problem of matching two expressions changes to that of graph isomorphism. Graph isomorphism is the well-established problem of deciding whether two different graphs employ the same topological structure, regardless of their apparently different representation. For instance, in figure 1, bottom, a and b are isomorphic to each other, but neither is isomorphic to c.

Figure 1: Top: The expression tree for x²+ y. Bottom: a and b are isomorphic, even though they appear different. Neither is isomorphic with c.

It should be noted that the question of whether two mathematical expressions are equal is akin to the halting problem, and in general undecidable. Therefore, the algorithm proposed here would be better considered as a heuristic that can handle most ordinary cases likely to appear in school textbooks but will nevertheless fail in the face of self-referential statements. To make matters worse, in the proposed approach, once the expressions are converted into their graphical representation, their equality amounts to isomorphism of their corresponding trees, which is conjectured to be NP-complete.

Algorithm

We start by parsing the expression and building an expression tree. Expression trees are undirected acyclic graphs built from a prefix notation of the expression. Specifically, we are interested in the algebraic expression trees. Figure 1, top, illustrates as an example of the expression tree for x²+y. To facilitate our goal of recognizing identical symbolic expressions, this initial tree is modified from its original form in the following ways:

• While it is common for these trees to be binary, here we are relaxing this constraint and allowing each sub-tree to have more than two children. However, note that since T(c0,c1, …cn), an N-ary branch, can be rewritten as T0(T1(…Tn-1(cn-1, cn),c1),c0), a binary sub-tree, our discussion here extends to binary trees too.
• In a strict tree every node, including the leaves, can have at most one parent. In our graph, we let the leaves have multiple parents. The purpose of this is to ensure that all operations involving the same symbol terminate on it, as discussed momentarily.

With the expression tree built, the adjacency matrix together with the set of vertices will uniquely identify a symbolic expression. In our tree representation, the leaves are labeled “Sym” when they represent a symbol, and “Num” when they represent a number. Note that there is no need to differentiate multiple Sym leaves (for instance by subscripting them: Sym1, Sym2, …) because all the operations performed on the same symbol, terminate on the same Sym leaf. In other words, two different leaves labeled Sym correspond to two different symbols (e.g. x and y). See figure 3 for examples.

From there, the proper way to test whether two expressions thus coded are equal, will be to test whether they have the same vertices, and more importantly, if their graphs are isomorphic. Most graph libraries come equipped with isomorphism test functionality and the reader can pick their favorite library. For our experiments, we use the NetworkX library for Python.

Figure 2: Isomorphic expression tree for a2 + b and x + y2.

Non-commutative binary operators

Special care needs to be taken for binary operators whose operands do not commute. Consider 2−x and x−2. Encoded naively, their corresponding expression trees are going to be isomorphic, suggesting that the two expressions are the same, an obviously incorrect conclusion. To this end, subtraction is encoded as a combination of addition and multiplication by −1, both of which are

Figure 3: Examples of expression trees. Parenthetic values next to the leaves are for visualization only, and are not part of the tree. a: (x + y)²; b: Sin(x)Cos(x); c: (2xy+5)/y

commutative, i.e. x − 2 becomes x + (−1 × 2). Similarly, division is rewritten as multiplication with exponentiation: a/2 = a x 2^{-1} whose expression tree will not be isomorphic to 2/a = 2 x a^{-1}.

Another such operation is “Pow”, the operation that raises its base to its power. Figure 4 shows the corresponding graphs for 2^x and x². Once again, a naive encoding would result in isomorphic expression trees. Here, we differentiate the two edges extending from “Pow” to distinguish the base from the power. In figure 4 the power-edge is colored differently to reflect this differentiation.

Figure 4: The expression trees for 2^x and x². Note that although the graphs are isomorphic, the expressions are not.

Computational expense

In practice, one may often need to compile a database of all the mathematical expressions in a certain corpus, say, to support user queries. For instance, CK-12 may want to provide supporting material in response to users’ queries. When those queries contain mathematical expressions, it would have to consult a database compiled from all the expressions within the CK-12 corpus to retrieve the relevant documents. Considering that a match in this scenario means finding a graph isomorphic to the query, the computational cost of searching the database can be prohibitively high. In our experiments, we tackled this problem by assigning a key to each graph, constructed by concatenating its nodes sorted alphabetically (for the two graphs in figure 2 the key would be AddNumPowSymSym). These keys are then used as entry points into a hash table whose values are the list of all graphs with the same key (Note that since the key does not consider the structure of the graph, different graphs may have the same key). Effectively, during a search one only needs to examine the isomorphism of the graphs whose key matches the query: a significantly smaller number than the total number of graphs in the database.

Summary

Today we have countless methods for parsing and analysis of statements expressed in natural language. However, most such methods do not possess any native means of working with mathematical expressions. Here we have proposed an encoding algorithm based on the topology of the algebraic expressions tree that yields invariant representations for mathematical expressions. Given this invariant representation, the identity of two mathematical expressions amounts to the isomorphism of their expression trees.