The Responsibility Problem in Neural Networks with Unordered Targets
We discuss the discontinuities that arise when mapping unordered objects to
neural network outputs of fixed permutation, referred to as the responsibility
problem. Prior work has proved the existence of the issue by identifying a
single discontinuity. Here, we show that discontinuities under such models are
uncountably infinite, motivating further research into neural networks for
unordered data.
Ben Hayes, Charalampos Saitis, György Fazekas
# The Responsibility Problem in Neural

###### Abstract

We discuss the discontinuities that arise when mapping unordered objects to neural network outputs of fixed permutation, referred to as the _responsibility problem_. Prior work has proved the existence of the issue by identifying a single discontinuity. Here, we show that discontinuities under such models are uncountably infinite, motivating further research into neural networks for unordered data.

## 1 Introduction

The _responsibility problem_(Zhang et al., 2020) describes an issue when training neural networks with unordered targets: the fixed permutation of output units requires that each assume a "responsibility" for some element. Permutations of responsibility result in discontinuities wherein small changes in a permutation invariant metric demand large changes in the layer's actual output. For feed-forward networks, the worst-case approximation of such discontinuous functions is arbitrarily poor for at least some subset of the input space (Krastios & Zamalooy, 2022)

Empirically, degraded performance has been observed on set prediction tasks (Zhang et al., 2020), motivating research into architectures for set generation which circumvent these discontinuities (Zhang et al., 2020; Kosiorek et al., 2020; Rezatofighi et al., 2018). The problem has briefly been stated formally in the literature (Zhang et al., 2020), but proven only by the existence of a single discontinuity. Here we prove an alternative statement of the responsibility problem, categorising unordered-to-ordered mappings as operations that are isomorphic to sorting and operations that are not.

In the first case, the discontinuities that arise are "classic" permutations of responsibility - that is, an element that was initially represented by one output unit becomes represented by another. Using a result from Hemasinha & Weaver (2015), we find that any mappings that preserve a consistent ordering between elements are isomorphic and thus all admit such discontinuities. In the second case, discontinuities also appear wherever the map does _not_ implement a consistent ordering. We demonstrate that, as a consequence, the set of discontinuities in both sorting and non-sorting maps is uncountably infinite.

This result is congruent with experimental evidence that performance suffers when the orderless structure of set data is not explicitly accounted for in model architectures. This has practical implications for any task that inherently involves set prediction, including object detection, point cloud generation, molecular graph generation, speech separation, and more.

## 2 The Responsibility Problem

Let \(\Theta\) denote the set of sets \(\mathbf{\theta}\) of cardinality \(|\mathbf{\theta}|=n\) with elements in \(\mathbb{R}^{d}\) where \(d\geq 2\):

\[\mathbf{\theta}\triangleq\left\{\mathbf{x}_{k}\mid\mathbf{x}_{k}\in\mathbb{R}^{d},k\in \{1,\ldots,n\}\right\}\in\Theta.\]

We are interested in the set \(\mathcal{F}\) of maps \(f\colon\Theta\to\mathbb{R}^{n\times d}\), such that all \(f\in\mathcal{F}\) select a single assignment of each element in any \(\mathbf{\theta}\in\Theta\) to each row of the resulting matrix:

\[f(\mathbf{\theta})=\begin{bmatrix}\mathbf{x}_{\pi(1)}&\mathbf{x}_{\pi(2)}&\ldots&\mathbf{x}_{ \pi(n)}\end{bmatrix}^{T},\qquad\forall f\in\mathcal{F},\ \ \forall\mathbf{\theta}\in\Theta,\ \ \ \pi=\Pi_{f}(\mathbf{\theta})\enspace,\]