Machine Learning for Better Combinatorial Algorithms #
Abstract #
Classification of combinatorial objects leads to NP-hard problems in Computer Science. One such problem is computing the orbits of groups actions. These orbits can be represented using Schreier trees. These trees allow us to navigate the group using only the generating set. Good Schreier trees reduce the time taken to find the group element that maps one element of a coset to another by reducing the length of the action composition chain. These “good” trees are ideally shallow. An ideal tree is one where the depth is no more than 1. In an ideal tree there is no computation performed to find the mapping group element. Generating an ideal Schreier tree is only possible if the size of the generating set is approximately equal to the size of the group. This is however not possible for large groups.
Thus we have algorithms such as the Seress shallow Schreier tree algorithm for generating shallow trees by finding better generators. However, this often comes at the cost of increased generating set size. In this talk we present another way of generating shallow Schreier trees using machine learning techniques such as deep reinforcement learning and graph embedding. Emperical results show that our deep learning based algorithm performs as well as the Seress algorithm in terms of the depth of the tree while keeping the size of the generating set constant.
Presentation #
