Machine learning and pattern recognition techniques have been successfully applied to algorithmic problems in free groups. In this paper, we seek to extend these techniques to finitely presented non-free groups, with a particular emphasis on polycyclic and metabelian groups that are of interest to non-commutative cryptography. As a prototypical example, we utilize supervised learning methods to construct classifiers that can solve the conjugacy decision problem, i.e., determine whether or not a pair of elements from a specified group are conjugate. The accuracies of classifiers created using decision trees, random forests, and N-tuple neural network models are evaluated for several non-free groups. The very high accuracy of these classifiers suggests an underlying mathematical relationship with respect to conjugacy in the tested groups.
In @cite_15 , posited that pattern recognition techniques are an appropriate methodology for solving problems in combinatorial group theory. To demonstrate, they constructed a machine learning system for discovering effective heuristics for the Whitehead automorphism problem, a search problem in free groups that uses the successive application of the namesake automorphisms to reduce a word to its minimal length. As mentioned in @cite_15 , every machine learning system must contend with the following tasks: data generation, feature extraction, model selection, and evaluation. Once the system is constructed, analysis of the system's performance can yield insights into the nature of the problem at hand, and potentially be used to improve upon it. In the following sections we will delve into each of these aforementioned tasks, showing in the process how these techniques can be extended from free groups to finitely presented groups, and ultimately be adapted to solving the conjugacy decision problem The primary difference in the construction of machine learning systems for free and not-free groups is in feature extraction, which is the focus of the next section.
@cite_15
1583192151
We review some basic methodologies from pattern recognition that can be applied to helping solve combinatorial problems in free group theory. We illustrate how this works with recognizing Whitehead minimal words in free groups of rank 2. The methodologies reviewed include how to form feature vectors, principal components, distance classifers, linear classifiers, regression classifiers, Fisher linear discriminant, support vector machines, quantizing, classification trees, and clustering techniques.