Generalized Neural Sorting Networks with Error-Free Differentiable Swap Functions

We appreciate your constructive comment to improve our work.

No clear distinction between the Transformer-based network vs the differentiable swap function. These are two orthogonal changes, and the Transformer seems to have much more performance impact than the swap function itself. Yet, the paper focuses mostly on the swap function.

We agree with your point. To accommodate your comment, we have updated Section 4 and added Section G and Figure 7. These updates explain our Transformer-based network in detail. Please see our revision as well as the discussion described in the Effects of Multi-Head Attention in the Problem (3) paragraph of Section 7.

As the standard deviations are not shown,

We provide the standard deviations here. These results show the standard deviations of the last three rows of Table 1.

Based on the values shown above, the training of our networks is dependent on random seeds but the dependency is not strong. To consistently present the experimental results, we omitted them in the submission.

$\lambda = 1$ seems to hinder accuracy.

You are right, but the use of our hard loss is effective for $0 < \lambda < 1$. As described in Section 7, our hard loss is likely to make loss values discrete. Therefore, the selection of appropriate balancing parameters is significant. We would like to note that this selection process is a typical problem in the deep learning community, and we also solved a similar problem by following the previous literature.

the best optimal diffsort models with identical transformer architecture to those of the Error-Free DSF

If we understand your concern correctly, we have already included this ablation study. We can see these results in Table 4. For your convenience, we highlight these results here.

The same architecture as the best Error-Free DSF with $\lambda = 0$ (thus, being equivalent to using hard min/max during inference, but being trained as "Diffsort Optimal")

Since we directly calculated accuracy from the scores $\mathbf{s}$ produced by the neural network (see Equations (19) and (20)), the results shown in the paper (including Diffsort (Optimal)) are reported by following your suggestion, which uses hard min/max during inference.

Why are the results on 4-digit MNIST with a seq length of 32 significantly better in Tab 1 than in Tab 15?

Table 15 uses fixed hyperparameters (i.e., steepness and learning rate) for fair comparison, so that it can show a thorough analysis on our models. Therefore, the results in Table 1 is better than ones in Table 15. Please see Section K for more details.

I think there is a gap in the proof of Proposition 2. Namely, the fact that the soft minimum and the soft maximum are the same as $k \to \infty$ seems like it is missing a step in how it is derived. I believe that it should hold, given the differentiability of the function, but filling in the missing step here is needed.

Thank you for pointing this out. We have updated the proof of Proposition 2. Please see Section E.

It seems to me that the paper assumes that the function used to soften the maximum is the sigmoid, and some of its properties are listed in Section 2 - however, it is not clear if the sigmoid is the only choice, or if these properties are sufficient for a function to satisfy. I would appreciate it if the authors could clarify this point.

As described in Section 2, the required properties of $\sigma$ are that $\sigma(x)$ is differentiable, $\sigma(x)$ is non-decreasing, $\sigma(x) = 1$ if $x \to \infty$, $\sigma(x) = 0$ if $x \to -\infty$, $\sigma(0) = 0.5$, and $\sigma(x) = 1 - \sigma(-x)$. If a function is (point) symmetric, bounded, and differentiable by satisfying the aforementioned properties, that function should be $s$-shaped or sigmoid. Note that the sigmoid function in machine learning, which is widely used as an activation function, is called the logistic function in this paper.

Again in Section 2, I had some trouble understanding the wire-based construction of the permutation matrix, especially since the associated Figure is in the Appendix. I believe that the point of the authors would be clearer if they moved the Figure in the main paper, as well as simplify the explanation for the construction (saying, e.g., that each wire is a step to fix a single wrong ordering, and iterative application of these steps results in a sorted set).

We have moved the figure and updated Section 2. Please refer to Section 2 and Figure 2.

I believe that Figures 1 and 2 can be simplified / combined, since they are essentially showing similar things - namely, that the function is error-free, which is not surprising given that it is not softened during the forward pass.

By considering your comment, Figure 1 only remains in the main article. Figure 2 is replaced with a figure with wire sets.

In Section 7, the paragraph "Utilization of Hard Permutation Matrices" is not very clear to me. I would appreciate it if the authors could rephrase the point they are trying to make here.

As mentioned above, I would be grateful if the authors could clarify the paragraph "Utilization of Hard Permutation Matrices" of Section 7.

The experiments shown in Section 5.2 solve a task to place image fragments on right positions. It requires swapping image fragments exactly, not combining image fragments via linear combination. Our sorting network ensures that final outcomes preserve initial instances from the application of sorting operations. We have also updated the corresponding paragraph of Section 7.

As a minor point, in Section 6, the authors should rephrase how they refer to previous works, for example: "The work (Petersen et al., 2021) has suggested ..." -> "Petersen et al. (2021) have suggested...".

Thank you for pointing this out. We have fixed it and also similar cases; please see Section 6.

We appreciate your constructive comment to improve our work.

I believe that the authors should either better motivate the need for this sort of method, or demonstrate in their experiments why learning the ordinal value directly does not perform as well.

By considering your comment, we have revised Section N of our work. For your convenience, we provide the updated paragraph that can enhance the motivation of our work here:

It is challenging to directly sort a sequence of generic data instances without using auxiliary networks and explicit supervision. Unlike earlier sorting methods, this sorting network-based research (Petersen et al., 2021; 2022) including our work ensures that we can train a neural network that predicts numerical scores and eventually sorts them, even though we do not necessitate accessing explicit supervision such as exact numerical values of the contents in high-dimensional data. In this sense, the practical significance of our proposed methods can be highlighted by offering this possibility of solving a sorting problem with high-dimensional inputs. For example, as shown in Section 5, we can compare images of street view house numbers using the sorting network where our neural network is trained without exact house numbers.

Moreover, instead of using costly supervision, our networks allow us to sort high-dimensional instances in a sequence where information on comparisons between instances is only given. This scenario often occurs when we cannot obtain complete supervision. For example, if we would sort four-digit MNIST images, ordinary neural networks are designed to solve a classification task by predicting class probabilities each of which indicates one of all labels from "0000" to "9999". If some labels are missing and further we do not know the exact number of labels, they might fail in predicting unseen data corresponding to those labels. Unlike these methods, it is possible to solve sorting problems with our networks in such a scenario.

As discussed in Section 7, the hard permutation matrices produced by our methods encourage us to swap instances exactly, instead of the linear combination of instances. This characteristic is required when we are given the final outcomes of sorting as supervision. This scenario is tested by the experiments presented in Section 5.2. In these experiments, we can consider that original images are provided as supervision. Building on the advantages of neural network-based sorting networks, we extend their practical significance into the cases that need hard permutation matrices.

Furthermore, this study can be applied in diverse deep learning tasks for learning to sort generic high-dimensional data, such as information retrieval (Cao et al., 2007; Liu, 2009) and top-$k$ classification (Berrada et al., 2018).

We thank you for your constructive feedback again.

We have answered your concerns in the rebuttal.

Please take a look into our response and let us know if you still have any concerns.

I'd like to thank the authors for responding to my points. I now better understand the points in Section 2 and 7. For Section 7 in particular (as a minor point), I believe it would be good if the authors explicitly stated that $P_soft$ is not a good idea, precisely because it mixes representations, instead of simply sorting them (potentially replacing the current first sentence in the paragraph). I also now understand why simple supervision is not a good idea, since it is also affected by the amount of samples needed for each ordinal that we are trying to sort.

Regarding the proof in Section E, I think it still contains a small issue - namely, the fact that $\bar{min}^k$ is strictly increasing and $\bar{max}^k$ is strictly decreasing does not (by itself) prove that these converge to the same limit (since it could be the case that $\lim_{k \to \infty} \bar{max}^k > \lim_{k \to \infty} \bar{min}^k$ - they could converge to different points). To fully complete the proof, I think something like $\lim_{k \to \infty} (\bar{max}^k - \bar{min}^k) = 0$ is necessary, which I believe can be derived by differentiability/continuity of $\sigma$. Explicitly showing that they both converge to $(max(x,y) + min(x,y)) / 2 = (x+y)/2$ would also suffice. I understand that this is a minor point overall, but I believe it should be corrected.

The reviewer-author discussion period is ending soon.

If your concerns are resolved, please update your review.

We appreciate your constructive comment to improve our work.

Insufficient Discussion on Limitations: While the paper mentions that its methods are limited to sorting algorithms, it doesn't provide a thorough discussion on other potential limitations, such as scalability or conditions under which the method may not work well.

Could the authors provide a more comprehensive discussion on the limitations of their approach, particularly in terms of scalability and conditions where the method may not be applicable?

By considering your comment, we have updated Sections M and N. We present those sections here:

M. Limitations

While a sorting task is one of the most significant problems in computer science and mathematics (Cormen et al., 2022), our ideas, which are built on sorting networks (Knuth, 1998; Ajtai et al., 1983), can be limited to sorting algorithms. It implies that it is not easy to devise neural network-based approaches to solving general problems in computer science, e.g., combinatorial optimization, which are inspired by our ideas. Nevertheless, the use of our algorithms enables us to learn a neural network-based sorting network for high-dimensional data, and employ the neural network in the tasks on sorting high-dimensional data instances.

In addition, while our proposed methods show the superior performance compared to the baseline methods, this line of research suffers from the performance degradation for longer sequences as shown in Tables 1, 2, and 3. More precisely, for longer sequences, the element-wise accuracy of our methods does not decline dramatically, but the sequence-wise accuracy of our methods drops due to the nature of sequences. Incorporating our contributions such as the error-free DSFs and the Transformer-based networks, we expect that the further progress of neural network-based sorting networks can be achieved. In particular, the consideration of more sophisticated neural networks with a huge number of parameters, which are capable of handling longer sequences, might help improve performance. This will be left for future work.

Furthermore, our frameworks successfully learn relationships between high-dimensional data with ordinal contents as shown in Section 5. However, our methods are supposed to fail in sorting data without ordinal information; the elaborate discussion on this topic can also be found in Section 7. In order to sort more ambiguous high-dimensional data, we can combine our work with part-based or segmentation-based approaches.

N. Broader Impacts

It is challenging to directly sort a sequence of generic data instances without using auxiliary networks and explicit supervision. Unlike earlier sorting methods, this sorting network-based research (Petersen et al., 2021; 2022) including our work ensures that we can train a neural network that predicts numerical scores and eventually sorts them, even though we do not necessitate accessing explicit supervision such as exact numerical values of the contents in high-dimensional data. In this sense, the practical significance of our proposed methods can be highlighted by offering this possibility of solving a sorting problem with high-dimensional inputs. For example, as shown in Section 5, we can compare images of street view house numbers using the sorting network where our neural network is trained without exact house numbers.

Moreover, instead of using costly supervision, our networks allow us to sort high-dimensional instances in a sequence where information on comparisons between instances is only given. This scenario often occurs when we cannot obtain complete supervision. For example, if we would sort four-digit MNIST images, ordinary neural networks are designed to solve a classification task by predicting class probabilities each of which indicates one of all labels from "0000" to "9999". If some labels are missing and further we do not know the exact number of labels, they might fail in predicting unseen data corresponding to those labels. Unlike these methods, it is possible to solve sorting problems with our networks in such a scenario.

As discussed in Section 7, the hard permutation matrices produced by our methods encourage us to swap instances exactly, instead of the linear combination of instances. This characteristic is required when we are given the final outcomes of sorting as supervision. This scenario is tested by the experiments presented in Section 5.2. In these experiments, we can consider that original images are provided as supervision. Building on the advantages of neural network-based sorting networks, we extend their practical significance into the cases that need hard permutation matrices.

Furthermore, this study can be applied in diverse deep learning tasks for learning to sort generic high-dimensional data, such as information retrieval (Cao et al., 2007; Liu, 2009) and top-$k$ classification (Berrada et al., 2018).

On the other hand, this nature of neural network-based sorting networks can yield a potential negative societal impact. If this line of research including our proposed approaches is employed to sort controversial high-dimensional data such as beauty and intelligence, it can be thought of as the unethical use cases of artificial intelligence.

Hyperparameter Sensitivity: The paper discusses various hyperparameters like steepness and learning rate but does not provide a comprehensive analysis of their impact, which could be a concern for practical implementations.

How sensitive is the model's performance to the choice of hyperparameters like steepness and learning rate? Could the authors provide more insights into this?

We have revised Section L. Please refer to Section L.

Complexity of the Model: The use of a permutation-equivariant Transformer network with multi-head attention could make the model computationally expensive, which is not addressed in the paper.

We have shown the complexity of our model empirically. As shown in Tables 1, 2, and 3, We reported FLOPs and the number of parameters. When we determined the size of our Transformer-based network, we have considered these two factors. Moreover, discussion on this issue is described in the Effects of Multi-Head Attention in the Problem (3) paragraph of Section 7; please refer to this paragraph.

Missed Opportunity for Theoretical Analysis: While the paper is empirically driven, a more in-depth theoretical analysis could strengthen the paper by providing bounds or guarantees on the performance of the proposed methods.

We have proved Propositions 1, 2, and 3 where their proofs are provided in Sections D, E, and F. By these propositions, our error-free DSF can provide more accurate signals to the neural networks we are training. However, as described in your comment, our work is to propose a new framework of neural network-based sorting networks, which can be considered as the empirically driven work. More rigorous guarantees on the performance of the proposed methods will be left for future work.

We thank you for your constructive feedback again.

We have answered your concerns in the rebuttal.

Please take a look into our response and let us know if you still have any concerns.

The reviewer-author discussion period is ending soon.

If your concerns are resolved, please update your review.

In terms of the results, it can be observed that as the sequence length increases or the number of segments grows, the performance decreases significantly.

Why does the performance drop significantly when the quantity increases?

Since our neural networks are trained from scratch using only supervision on permutation matrices, the cases with longer sequences are hard to train. In addition, this performance drop becomes more significant because the impact of the performance drop is magnified as a sequence length increases. In particular, as presented in the results of $\textrm{acc}\_{\textrm{ew}}$, an individual score $s_i$ is relatively accurate. If a sequence length increases, $\textrm{acc}\_{\textrm{em}}$ exponentially drops. For example, if $\textrm{acc}\_{\textrm{ew}} = x$, $\textrm{acc}\_{\textrm{em}}$ is approximately $x^n$ where $n$ is a sequence length.

It is worth noting that the previous studies struggled to show better performance in the same benchmarks and our methods outperform those baseline methods; please see Tables 1, 2, and 3.

We appreciate your constructive comment to improve our work.

Since the methods proposed in the paper are based on sorting networks, they are not applicable to solving general problems in computer science, such as combinatorial optimization. This implies that it may not be easy to devise a neural network-based approach for solving these types of problems using the ideas presented in this work.

I hope the author can provide a detailed explanation of the practical significance of this work.

I find it somewhat challenging to grasp the practical significance of this work. I believe that this work lacks practical significance to some extent.

By considering your comment, we have updated Section N. For your convenience, we present part of that section here:

It is challenging to directly sort a sequence of generic data instances without using auxiliary networks and explicit supervision. Unlike earlier sorting methods, this sorting network-based research (Petersen et al., 2021; 2022) including our work ensures that we can train a neural network that predicts numerical scores and eventually sorts them, even though we do not necessitate accessing explicit supervision such as exact numerical values of the contents in high-dimensional data. In this sense, the practical significance of our proposed methods can be highlighted by offering this possibility of solving a sorting problem with high-dimensional inputs. For example, as shown in Section 5, we can compare images of street view house numbers using the sorting network where our neural network is trained without exact house numbers.

Moreover, instead of using costly supervision, our networks allow us to sort high-dimensional instances in a sequence where information on comparisons between instances is only given. This scenario often occurs when we cannot obtain complete supervision. For example, if we would sort four-digit MNIST images, ordinary neural networks are designed to solve a classification task by predicting class probabilities each of which indicates one of all labels from "0000" to "9999". If some labels are missing and further we do not know the exact number of labels, they might fail in predicting unseen data corresponding to those labels. Unlike these methods, it is possible to solve sorting problems with our networks in such a scenario.

As discussed in Section 7, the hard permutation matrices produced by our methods encourage us to swap instances exactly, instead of the linear combination of instances. This characteristic is required when we are given the final outcomes of sorting as supervision. This scenario is tested by the experiments presented in Section 5.2. In these experiments, we can consider that original images are provided as supervision. Building on the advantages of neural network-based sorting networks, we extend their practical significance into the cases that need hard permutation matrices.

Furthermore, this study can be applied in diverse deep learning tasks for learning to sort generic high-dimensional data, such as information retrieval (Cao et al., 2007; Liu, 2009) and top-$k$ classification (Berrada et al., 2018).

We thank you for your constructive feedback again.

We have answered your concerns in the rebuttal.

Please take a look into our response and let us know if you still have any concerns.

Thanks for the reply. My problem was solved. I hope to present these in more detail in the final version. I will raise my score.