Symmetry Discovery Beyond Affine Transformations

We thank the reviewer for their comments. We have responded below.

Terminology: With no intent to confuse the reader, we used the term "machine learning function" to cover very general types of functions which may appear within the context of machine learning. Such a function could be a regression function, a classification function, or a function offering a manifold description of given data, as in level set estimation or in the presence of a metric tensor.

The elbow curve notion refers to a relatively sudden increase in function values, perceived as an elbow shape, since the function values immediately preceding the elbow point are usually close together. This is sometimes referred to as finding a "kink," as in [R1] within the context of selecting the "best" number of clusters $k$ for $k$-means clustering.

In general, Eq. (10) may not have a solution, as is the case with OLS regression. Eq. (10) is estimated/fitted by constrained optimization of a selected loss function. We will clarify this in the revision.

Capabilities and Limitations: We have clarified many points regarding the capabilities and limitations of our method in our response to the reviewers. We will include a discussion of these points in the revised version.

Only using toy datasets: Current SOTA papers in symmetry detection commonly use simulated data. An experiment with simulated data allows for the identification of ground truth symmetry, allowing one to quantify the accuracy of a given method. Symmetry detection on real-world data can be applied, but it is harder to evaluate the ability of new methods to properly detect symmetry if ground truth symmetry is not known, as is generally the case with real data. Thus our experiments are consistent with other SOTA papers in this area.

Nevertheless, we present an additional experiment on real data that we will include in the revision. This comes from a publicly-available dataset that deals with weather for four decades in the vicinity of Bear Lake, Utah. The dataset, along with a report describing how the data was sourced, is publicly available [R2].

The dataset gives daily weather attributes. It contains $14,610$ entries with 81 numeric attributes including the daily elevation level of the lake. The dataset contains precisely 40 years' worth of data from October of 1981 through September of 2021.

We believe an understanding of the behavior of the weather in the past is relevant to this problem. Therefore, we first construct $13,149$ time series of length $1461$ in $81$ dimensions by means of a sliding window of length $1461$ days: the first time series is constructed using the first $1461$ days (the number of days in four years). The next time series is constructed using the second day through day 1462, and so forth.

After converting the raw data to time series data, we apply a transformation on the data meant to extract time-relevant features of the data known as the Multirocket transform [R3]. We select $168$ kernels in our transform. The Multirocket transform transforms the data from $13,149$ time series of length $1461$ in $81$ variables to tabular data: $13,149$ entries in $1344$ variables.

For such high-dimensional data, we turn to PHATE, a SOTA data visualization method [R4]. Using PHATE, we reduce the dimension to $2$, so that our new dataset has $13,149$ entries in $2$ variables. The resulting data appears to approximately lie on a circular shape and is shown in Figure 1 of the rebuttal attachment.

Figure 1 in the rebuttal attachment suggests that the data is largely periodic. In fact, further experimentation reveals that the points for a given calendar year correspond to a traversal around the circular-like shape. Thus, for the analysis of non-seasonal weather patterns, it may be of use to examine features of this embedded dataset which are invariant under the periodic transformation, the approximate symmetry.

Indeed, our method reveals an approximate invariant function given by

$

f(x,y) = 0.33592 x^2 + 0.94189 y^2 - 2.9743 \cdot 10^{-4} = 0.

$

In Figure 2 of the rebuttal attachment, we replot the embedded data, colored this time by the value of the approximate invariant function. This experiment shows that symmetry can occur in real data, and that our method can detect symmetry and estimate invariant functions for real data.

Transformation class: The transformations our method can handle are 1-parameter subgroups of transformation groups (Lie groups). We will clarify this in the revision.

Solving method: Solutions to Eqs. (10), (13), and (14) are estimated using constrained regression. The specific loss function and hyperparameters vary by experiment, but we will clarify these details in the revision.

Noise: Noise is common in regression problems, and it affects the quality of least squares estimates. We have noise present in the experiment that compares our method with LieGAN, since the dataset is not technically rotationally symmetric, but rather approximately rotationally symmetric.

When our method fails: It may fail if the number of independent parameters exceeds the number of datapoints. The success of the method depends on optimization and loss function choices, as well as hyperparameters. We will clarify these points in the revision.

[R1] T. Hastie, R. Tibshirani, and J. Feiedman, ``The Elements of Statistical Learning: Data Mining, Inference, and Prediction,'' 2nd ed. Springer, 2009.

[R2] B. D. Shaw et al., “Supplementary files for: ‘interactive modeling of bear lake elevations in a future climate’,” 2024.

[R3] C. W. Tan, A. Dempster, C. Bergmeir, and G. I. Webb, “Multirocket: Effective summary statistics for convolutional outputs in time series classification,” CoRR, abs/2102.00457, 2021.

[R4] K. Moon et al., “Visualizing structure and transitions in high-dimensional biological data,” Nature Biotechnology, vol. 37, pp. 1482 – 1492, 2019.

We thank the reviewer for their comments. We have responded below to the concerns raised.

Use of Polynomials: In general, level set estimation can be applied using linear combinations of any set of smooth functions, though our experiments do specialize to polynomial functions. However, smooth functions can be approximated by polynomials of sufficiently high degree and are thus universal approximators [R1].

The elbow curve: Instability can arise, and the results of the elbow curve can be misleading. This seems to primarily occur when the problem of degenerate expressions, discussed first in lines 182 - 204, is not properly controlled. For level set estimation, if both $f=0$ and $hf=0$ are discoverable expressions based on the pre-defined search space (for example, $x-y=0$ and $x^2-xy=0$), the loss function values may not generally follow an elbow curve, and any perceived elbow may not occur at the correct number of components for level set estimation. We discuss some workarounds for this problem, both for level set estimation and for vector field estimation, in lines 182-204, as well as 226-231.

Scaling beyond toy examples: Vector fields with polynomial coefficients can characterize highly complex and non-trivial symmetries. Especially due to their universal approximation properties [R1], we expect that many symmetries that occur in the real world are expressible or approximately expressible in this form. Additionally, our method advances the current SOTA methods, as current SOTA methods consider a more restricted class of symmetries. Thus, we believe our contribution is an important advance. See our overall rebuttal for more details on our contributions. See also our response to reviewer U1Sk for an experiment on real data.

Feature function choice: The features are chosen, in general, based on the types of symmetries sought. For example, if only affine symmetries are being sought, the feature functions for the vector fields are chosen to be affine functions. If no assumption on the form of the symmetries can be made, one can choose the features to be arbitrary polynomials, due to their universal approximation property [R1].

Computational complexity: The computational complexity of polynomial regression is comparatively low, especially in a single dimension [R2]. Moreover, manifold optimization algorithms on the matrix manifolds used herein are also of low computational complexity, with a recent manifold optimization algorithm obtaining computational complexity of $\mathcal{O}(\log(T)/\sqrt{T})$, where $T$ is the number of iterations [R3]. In contrast, current SOTA methods employ large neural networks, which networks are known to take more computational resources to train.

There is no combinatorial explosion in our method. In fact, we can obtain a precise count of the number of parameters our method requires. Each vector field in $m$ dimensions using polynomials of degree $n$ has the following number of coefficients:

$

\dfrac{(m+n)!}{n!(m-1)!}.

$

The coefficients can increase quickly, particularly in higher dimensions, but for every fixed value of $m$, the number of coefficients increases as a polynomial function of $n$ rather than combinatorially. However, each coefficient in our model increases the power of our method to detect symmetries. In contrast, while SOTA methods employing large neural networks must have parameters like ours which characterize the symmetries, they also have additional parameters. The number of parameters in our method increases according to the number of vector fields in a basis of our search space, whereas in methods such as LieGAN, these parameters are required in addition to other parameters present in the neural network architecture.

To address the potential issue of having a “large” number of parameters, which number is dwarfed by the number of parameters present in neural networks that take $m$ inputs, we suggest limiting the search space to infinitesimal isometries: Killing vectors, that is. We discuss this restriction further in Appendix A.

[R1] A. Pinkus, “Weierstrass and approximation theory,” Journal of Approximation Theory, vol. 107, no. 1, pp. 1–66, 2000.

[R2] L. Li, “A new complexity bound for the least-squares problem,” Computers & Mathematics with Applications, vol. 31, no. 12, pp. 15–16, 1996.

[R3] H. Kasai, P. Jawanpuria, and B. Mishra, “Riemannian adaptive stochastic gradient algorithms on matrix manifolds,” 2019.

We thank the reviewer for their comments. We have responded below to the concerns raised.

Pre-determined models: We believe that we are the first to detect continuous symmetries in the context of machine learning beyond the affine group, despite work on the subject spanning decades. Our method of estimating vector fields is regression with general additive models, where the coefficients of the model features are constrained: we specialize to polynomials for the purpose of illustration and better comparison with existing methods for symmetry detection. We have showcased examples in which polynomial-based models are most appropriate, and although experiments which make use of other types of smooth functions can be devised, the only aspect of our method which changes in these cases is the components of the feature matrix used to estimate the coefficients. Therefore, our method can be trivially adapted to non-polynomial models. Later in this response, we will present the results of an experiment which uses non-polynomial functions.

A suitable pre-determined model for the detection of manifold symmetries would rely on the nature of the manifold itself. However, it appears that although the manifold assumption is widely used in machine learning, very little work has been done to characterize the manifolds on which data is assumed to lie. Therefore, our choice to specialize to polynomial-based models is no less valid than other specializations. Additionally, polynomials can be used to approximate any continuous function [R1] and thus, in theory, can characterize any continuous symmetry, at least locally.

Covering the GT vector field: If the degrees of the polynomial functions of a vector field are sufficiently high, the vector field can approximate a suitable ground truth vector field. We also reiterate that current SOTA methods, if recharacterized in terms of vector fields, would assume that the coefficients of the vector fields are degree 1 polynomials. Our presentation of symmetry detection in terms of vector fields opens up a great many possibilities for types of functions used, although we use polynomials for better comparison with existing methods and due to their universal approximation property [R1].

LieGAN comparison: For every value of $N$, our method usually outperformed LieGAN for most trials. However, the average score of our method was brought down by outlier trial runs for our method, likely due to poor initialization of the model parameters. However, such a shortcoming could be easily overcome by fine-tuning. In the spirit of a fair comparison, we did not perform any (albeit simple) hyperparameter tuning for our method, since we did not perform any hyperparameter tuning for the LieGAN method.

It is also evident that the error bars for the scores in both methods overlap, except for $N=200$ where our method vastly outperforms LieGAN. Thus, the experimental results seem to suggest that our method is comparable to LieGAN in terms of accuracy, except when $N$ is low. Ultimately, the purpose of this experiment was to show that our method competes with SOTA in terms of accuracy when detecting affine symmetries, while offering a computational advantage. However, using the median as the estimate and the IQR for the error bars gives the results in Table 1 of the rebuttal attachment.

We now present an additional experiment that uses both linear terms and a few sinusoidal terms as a pre-determined model. First, we generate 2048 numbers $x_i$ and 2048 numbers $y_j$, each from $U(0,2\pi)$. Next, for each pair $(x_i,y_i)$, we obtain $z_i$ by means of $z_i = \sin(x_i)-\cos(y_i)$, so that a ground-truth level set description of the data is given as $z-\sin(x)+\cos(y) = 0.$

We first apply our level set estimation method to estimate this level set. We optimize the coefficients of the model

$

    a_0 + a_1 x + a_2 y + a_3 z + a_4 \cos(x) + a_5 \cos(y) + a_6 \cos(z) + a_7 \sin(x) + a_8 \sin(y) + a_9 \sin(z)=0

$

subject to $\sum_{i=0}^9 a_i^2 = 1$. In light of Eq. (10) in the paper, the matrix $B$ has a row for each of the 2048 tuples $(x_i,y_i,z_i)$, and 10 columns, which columns correspond to the 10 different feature functions in our pre-determined model. The vector $w$ contains all 10 parameters $\\{a_i\\}_{i=0}^{9}$.

Using the $L_1$ loss function and the (Riemannian) Adagrad optimization algorithm with learning rate $0.01$, our estimated level set description is

$

    -0.57737 z - 0.57713 \cos(y) + 0.57756\sin(x) = 0,

$

which is approximately equivalent to the ground truth answer up to a scaling factor.

Relevant reference: We will include a brief discussion of the paper by Desai et al. We note that LieGAN outperformed this work in their experiments, and thus a comparison is unnecessary.

Details about Section 4.2 experiment: For this experiment, the search space for level set estimation was limited to cubic polynomials, while the search space for vector fields was limited to quadratic coefficients. In this setting, the only valid symmetries are constant multiples of the given ground truth symmetry. It is a good point that $fX$ may not have a favorable cosine similarity. Thus, it seems that the cosine similarity metric can only be applied where the issue of uniqueness can be controlled, as in this particular example. We will discuss this limitation in the revision. The purpose of this experiment is to show that our method can detect non-affine symmetries, where current SOTA cannot. See also our overall rebuttal for further discussion.

[R1] A. Pinkus, “Weierstrass and approximation theory,” Journal of Approximation Theory, vol. 107, no. 1, pp. 1–66, 2000.

I appreciate for the authors' anthusiastic discussion and additional experiment. Clarifying my conclusion first, I raised my score to weak accept.

The first version of the manuscript evaluated symmetry detection in the coefficient space of a predetermined model of vector fields, but the authors finally proposed the way to evaluate in the space of vector fields. The reason why I leaned toward rejection was based on the coefficient space evaluation. The latter evaluation is much technically sound than the former one, for me. Of course evaluating on the space of vector fields still has limitations, since handling symmetries in the sense of {$S$ | $f\circ S = f$} and the sense of the vector fields are not equivalent e.g. X and fX. However, overcoming these remained challenges is considered as a good future work, but the authors are not needed to provide a method and results to overcome them. I think attaching relavent discussions from this rebuttal & discussion period into the revision will be fine.

There are also remained concerns which I hope the authors to adress them in the revision (not need to response during this discussion period, which has only one hour left).

• The vector field similarity depends on the choice of the bounding volume. It will be clarified.
• For $\mathrm{sim}\left(X,Y\right)$, The current formula seems to depend on choice of coordinates so that lacking geometric meaning. Please check. I think the summation symbol should appearr three times, once in the numerator and twice in the denominator.

I appreciate the response and the additional discussion by the authors. Some of my concerns have been resolved, but some others still remain.

Q1. LieGAN comparison for affine symmetry detection By the additional experiment in the rebuttal attachment, now the benefit of the proposed method against LieGAN has become clear. While the weakness about initialization must be discussed in the paper, the result is sufficient to support the benefit.

Other concerns are related the "predetermined models". Here I would like to reorganize the other concerns as followings by narrowing down the scope from what are general non-affined symmetries to coefficients of predetermined models of vector fields:

Q2. Is finding vector fields enough to say "we solve non-affine symmetry detection problem"?

Q3. Is finding coefficients of predetermined regression models of vector fields enough to say "we solve non-affine symmetry detection problem"?

Q4. Is the coefficients of predetermined models of vector fields a plausible evaluation metric?

The authors address Q2 and Q3 well. While the authors' discussion about these questions including the new experiment with sin, cos model should be added to the manuscript, Q2 and Q3 cannot be a reason to reject this paper. Now I agree that This paper has its own benefit which support possibility to be accepted, including SOTA performance for affine symmetry detection and an approach to reduce non-affined symmetry detection to finding a vector field.

However, Q4 is a concern in academic perspective that this paper can lead to misunderstanding among future researchers about what non-affine symmetry is and how it should be evaluated. One of reason I asked "The case that pre-determined parametric model of vector fields does not cover the GT vector field used for data generation is not discussed." is that I wanted the authors to realize the cosine similarity metric for coefficients do not have any sense for that case and to provide another plausible metric. The universal approximation property does not defense this issue.

Let me explain why the evaluation metric of cosine similarity for coefficients is weird by analogy to another formulation of problem. Suppose that there is a computer vision method where a neural network produces output images. Then the method must be evaluated using an image distance metric between output images from the proposed network and GT images. On the other hand, it will be so weird and misleading if one assume there is an GT network parameters which exactly produces GT images and evaluating the method using distance between network parameters.

It seems illogical to claim the benefit of the non-affine symmetry detection results when there hasn't been sufficient discussion on how non-affine symmetry should be evaluated. This could potentially establish an incorrect evaluation method for future researchers, which might undermine the benefits of the proposed method.

For this reason, my current score is "borderline reject". The minimum requirement for acceptance is as following:

• Clarify that: the evaluation metric is incomplete since it is not defined on vector fields themselves but depends on choice of parametric representations of vector fields. Then large changes in vector fields might raise relatively small changes in coefficients and vice versa.
• At least one additional experiment for the case that pre-determined parametric model of vector fields does not cover the GT vector field used for data generation. Then the authors should clarify they currently do not know plausible evaluation metric for this case and finding such metric is an important future work, and qualitative results which shows GT and estimated vector fields must be included.

We thank the reviewer for their comments. We have responded below to the concerns raised.

Assumptions: The single chart assumption is not necessary. Consider $f(x,y,z) = -x^2-y^2+z^2-1$. The surface $f=0$ is a hyperboloid of two sheets. We can estimate a continuous symmetry of this hyperboloid--a rotation in the $(x,y)$ plane--though a single coordinate chart cannot be given. Level set estimation does not deal with coordinate charts, which is a benefit of using a level set to characterize an embedded manifold.

We are also not assuming that the symmetry group has dimension 1. We do assume that the group has 1-parameter subgroups. There may be several 1-parameter subgroups, which our method can handle. The discovered vector fields are compatible in the sense that they admit a common set of invariant functions. This is described in lines 112-120, where we seek vector fields (each representing a 1-parameter subgroup) which annihilate the machine learning functions.

Discrete transformations: If one can express the discrete transformation parametrically, this method can be applied to discrete transformations. Many examples stem from continuous symmetries with a fixed continuous parameter, such as a rotation in the plane by a fixed but arbitrary angle $\theta$, where $\theta$ is the parameter to be optimized.

Another example is a 2-d reflection about a straight line passing through the origin. Such a line can be characterized by the equation $ax+by=0$, and a formula for the reflection can be written as

$

    S(x,y;a,b) = \dfrac{1}{a^2+b^2} \begin{bmatrix}
        a^2-b^2 & -2ab\\\\
        -2ab & b^2-a^2
    \end{bmatrix}
    \begin{bmatrix}
        x\\\\
        y
    \end{bmatrix}.

$

Optimizing the parameters $a$ and $b$ in $f(S(x)) = f(x)$ for some function $f$ would yield the "best fit" line of reflection under which $f$ is symmetric.

Permutations may not be expressible parametrically, and we will state this explicitly as a limitation of the method, since previous work with permutation groups has been done and is of interest.

Polynomials vs. MLPs: Since MLPs are universal approximators (as are polynomial functions), our method can be applied to MLPs as well. The main reason MLPs are not used here is because of the difficulty in using them for level set estimation: the MLP would need to output 0 for every input and yet not be the zero function. Meanwhile, we assume that the invariant functions are polynomials primarily for two reasons. First, in the case of affine symmetry, the invariant functions are typically expressed in terms of polynomials. Secondly, polynomials can approximate smooth functions with an arbitrary degree of accuracy [R1] and are easy and transparent to manipulate.

Additional Discussion: We will include a discussion on the number of parameters needed to estimate the symmetries in dimension $m$ using degree $n$ polynomials. This point is discussed in response to reviewer uBWo. The number of parameters relates to the dimension of the symmetry group and can also provide insight on the number of samples needed.

[R1] A. Pinkus, “Weierstrass and approximation theory,” Journal of Approximation Theory, vol. 107, no. 1, pp. 1–66, 2000.