Bio

Michael Udemba is an undergraduate mathematical physics student at the University of Nottingham as well as an experienced tutor in math and physics. He is intensely interested in the seemingly endless variety of applications of machine learning, as well as making cool pictures with mathematics, his favorite kinds of which are 3D fractals, focal surfaces, nonlinear phase portraits and, more recently, cellular automata and other simple programs like those featured in A New Kind of Science. When he isn’t studying, Michael enjoys playing, writing and listening to music, going for long walks and reading.

Computational Essay: Did My Parents Name Me Wrong? (According to very questionable classifiers)

Project: Finding the Minimum Change Path Between Symbolic Expressions

Goal

The primary goal is to implement an algorithm for finding the minimum sequence of edit operations required to change one expression into another. The edit operations are performed on the tree forms of the expressions and are restricted to insertion, deletion and replacement. It is possible to approach this problem entirely from the point of view of the tree edit distance problem, first investigated by Kuo-Chong Tai in 1979. An auxiliary goal is to develop tools for more efficient handling of trees, like tree traversal and edit operations.

Summary of Results

While working on my project, I have introduced fairly rudimentary tools for working with trees in the Wolfram Language, like pre-order traversal, more general node insertion and deletion, listing sub-trees and the beginnings of node ancestry. These tools, along with a few others I have created, have allowed me to successfully implement a variation of Kuo-Cho Tai’s tree edit distance algorithm to find the minimum change path between fairly simple, non-atomic expressions in the Wolfram Language.

Future Work

The rather ridiculous time complexity of my algorithm is due to a lack of checking for ancestry preservation in mappings, so it would be worth continuing to develop tools for handling trees in the Wolfram Language so that Tai’s algorithm, as well as some more time-efficient algorithms can be implemented properly. Additionally, I have implicitly assumed that the cost of all edit operations are equal. This need not be the case, and in the future, I would like to consider a cost associated with an operation that depends not only on the nature of the operation, but where in the tree the operation was applied, allowing one to find the minimum cost mapping given arbitrary constraints, summarized by abstract cost functions.