Applying language models to algebraic topology: generating simplicial cycles using multi-labeling in Wu's formula

relevance within the machine learning field

We hope that our work will be of interest for people working not only in applications of machine learning in math, but to a machine learning researchers who are interested in conditional generation and generation of synthetic and algorithmic languages. A machine learning researcher may found interest in a fact that in our work the target distribution, namely the full intersection, is not directly accessible to us and is not employed in the training process in any way. The only exception is its symmetric commutator part, which is utilized exclusively in training the negative baseline model. We also compare various modes of ensembling multiple generators which we believe is not domain specific.

difficult to understand which machine learning methods are used and why

Sorry for this. We attacked a problem first by constructing a series of deterministic and optimization-based approaches. When they became insufficient we turned our attention to deep learning models. We can definitely expand on a motivation for using attention based models for the camera-ready version (some of this motivation is related to a research on generating Dyck languages mentioned in Section 4.3). In short, we used a range of simpler neural network architectures first (described in Appendix D.1), and then moved to the attention-based models. Starting from ensembles we moved to prompting techniques that showed the best results.

the training procedure is difficult to understand

Thank you for pointing it out! You are right, we should wrote it more carefully. The training procedure fully conicides with the standard training algoirthm for autoregressive language models employing cross-entropy as a loss function.

meaningful progress for the problem in the domain of mathematics? scalability?

Our main goal was to establish a new machine learning framework for attacking the problem of computing homotopy groups of spaces. In this context, the domain of machine learning offers a unique arsenal of tools, particulary flexible generative models. We are sorry that from the paper it is unclear that research can not be expanded, we think the opposite. Due to size constraints we exclude the "future research" section from this version of the paper, we will definitely include it in the final version. For example, now we are working on different tokenization (on the level of commutators, not the generators of free group), which will help with computational constrains. Our main direction for the research is to use the following regularization technique: we increase the loss of the model's prediction if it is very similar to the predictions of the 'negative baseline model'.

completion/reduction ratio can distinguish ... repeating the same element multiple times?

During the test time we sample a batch of distinct prefixes of certain length. Then for each prefix we say that the model "completed" this prefix if it was able to generate a word from the full intersection using this prefix as a prompt. Our metrics aggreate the result across these distinct prefixes. Taking this description into account, it is easy to construct a degenerate example with a high score. Having a prefix $p$ one can continue it with $wp^{-1}$, where $w \in [R_0\dots R_n]_S$ is a fixed word. Such model would score perfectly. We are now working on the additional metrics that would help us to detect such behaviour. We think of employing pairwise similarity coefficients across the batch sample.

how do we know that the model is generalizing well, i.e. finding words which are not from the training set?

We agree that the question of generalization is very important. We guarantee that the training dataset does not contain words from the full intersection and as you can see our model is capable of generating elements from the full intersection. So, we believe that our model is able to generalize well. However we might need to investigate this question further. One way of doing so is the following. We can sample $m$ prefixes of length $l$ before training and put them away as the test dataset. During the training we would sample words that do not start with these test prefixes. Using this strategy we can further evaluate the generalization performance of our model.

Are there simpler generative models which could work well for this task?

As mentioned in Appendix D.1, LSTM ensemble works relatively well, but is still outpermormed by our final model.

The decoder part of a transformer is used to generate approximate samples from the homotopy group

It is important to clarify that in this project, our focus has been exclusively on generating samples from the numerator of the Wu formula. The generation of non-trivial elements from the homotopy group itself is a significantly more challenging problem. Our current research is laying the groundwork for this, and we are actively working on it in our current project.

how the samples drawn from the homotopy group can be used to understand the topological properties

Almost nothing is known about group-theoretic description of elements of the homotopy groups in terms of their topological properties. We can speculate that the commutator $[x_1, x_2]$ which generates $\pi_3 S^2$ and corresponds to the Hopf fibration $S^1 \to S^3 \to S^2$ is related to the Whitehead product expression for it. Deeper connections can be given using the language of $\Lambda$-algebra as well.

spaces other than the 2-dimensional sphere

Our results can be applied to spaces which have infinite cellular decompositions, but still fit into the framework of Wu's formula. Such spaces are usually unreachable by methods of the classical computational topology. Example os such space is $\Sigma\mathbb R \mathrm{P}^\infty$, i.e. a suspension over the infinite real projective plane. We are investigating this particular example currently.

proportions of repeated samples?

Our metrics count the numbers of unique generated words. We will count the repetitions as well and report them in the supplementary material if time permits.

distributions over the homotopy group ?

As for now we do not know how to describe this distribution. This problem is quite challenging since the answer is unknown theoretically (in the group-theoretic language) and the full intersection that we are sampling from is infinitely generated (see also answer to LHhA).

the significance of this work is unclear

Our work aims to transition the problem of computing homotopy groups (with no general solution currently) into a domain of machine learning where a broader array of methods can be applied. In our opinion setting such framework is important.

a constant function ... would score perfectly

You are right. In the answer to VtUd we described a construction of the degenerate example very close to a constant function that fools the metric. We are working on incorporating word similarity-based metrics to exlude such degenerate cases.

not doing anything in particular to encourage it not to learn the trivial words

By "enforcing it not to 'learn' the pattern of the trivial words" we meant that we ensure that no words from $[R_0\dots R_n]_S$ are in the training dataset. It is done by manually checking that no words in the training dataset are from the full intersection as well.

Figure 4 suggests that the models very much did predominantly learn trivial words

Non-trivial words (on which the loss in computed in Figure 4) are obtained by cyclic permutations of generators for the known non-trivial element (Table 1 of the paper). By multiplying this word by some other word from $[R_0\dots R_n]_S$ we can obtain another representative with much lower loss. Our aim here was to highlight a highly non-typical structure of the distiguished representative found by hand.

naive sampling and bracket-style ... the number of generated words

Please refer to Figure 1 in the new supplementary, which illustrate the benefits of using bracket-style sampling in terms of greater variability. It can be seen that for bigger batches bracket-style sampling provide better coverage of $R_i$.

why the bracket-style sampling is preferred to naive?

Because the samples are more diverse. A side comment: your inquiry into the differences between these methods is greatly appreciated, as it prompted further investigation on our part. We realized that we can rewrite (non-reducible) words from $R_i$ as words from a context-free grammar and use the methods of https://linkinghub.elsevier.com/retrieve/pii/0020019094900337 to sample uniformly from it with a better control over the length.

this notion of "variability" has not been defined

To provide a more precise definition, we can define variability as the ratio of the number of unique words generated per batch to the total number of words of a given length. This metric is detailed in (new) Table 1.

why the distribution (of valleys) for the bracket-style sampling is "better" than naive

The distribution for bracket style is better because it is "closer to uniform". But this is necessary condition for the ideal sampler, not sufficient. Perhaps the better illustration to illustrate the benefits of bracket style sequencing would be a plot like Figure 1 in the attachment. In general, in the paper the number of valleys serves just as an auxilary statistic of the sampler and the whole discussion of Dyck paths and Dyck languages serves an additional purpose to tie our research with the research on generating Dyck languages, as stated in the paper.

Could you provide quantitative evidence that the LLM results are "covering" the space well?

We could not provide such evidence now. For us the "degenerate pattern" you mention is defined as being an element of $[R_0\dots R_n]_S$, hence this question is more suitable for us in a context of negative sampling, where we train the model to generate elements away from $[R_0\dots R_n]_S$. Note that both $\cap_iR_i$ and $[R_0\dots R_n]_S$ are infinitely generated subgroups of free group, but their quotient (i.e. the homotopy group itself) is finite (provided $n > 2$). To our knowledge there is no known purely group-theoretical proof of this fact.

... if we limit ourselves to words with length less than some threshold?

Because of the remark above, if we are studying the question of coverage in a context of generating from intersection (not the homotopy group), we should restrict ourself to some finite subset of the free group. The word length restriction may not be natural for the type of objects like $\cap_iR_i$, in a sense that it is quite tricky to get a formula for number of words in $R_i$ of a given length, not to mention $\cap_iR_i$. We can bruteforce such computation for one $R_i$ and smaller lengths (used in Table 1 in the attachment), but these are insufficient to draw conclusions about the full intersection. We are investigating other filtrations on the free group that may be more natural for the problem.

there is potential for train/test overlap?

As mentioned above, we check that the words in the training datasets are not from the full intersection, hence train/test overlap is not possible. Additionally we can ensure the non-overlapping of the train and the test by separating a subset of prefixes, that would only be shown to the model during the test phase.