Unsupervised Object Detection with Theoretical Guarantees

Authors: marian  longa
joão f henriques
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-11 13:37:12

Abstract: Unsupervised object detection using deep neural networks is typically a difficult problem with few to no guarantees about the learned representation. In this work we present the first unsupervised object detection method that is theoretically guaranteed to recover the true object positions up to quantifiable small shifts. We develop an unsupervised object detection architecture and prove that the learned variables correspond to the true object positions up to small shifts related to the encoder and decoder receptive field sizes, the object sizes, and the widths of the Gaussians used in the rendering process. We perform detailed analysis of how the error depends on each of these variables and perform synthetic experiments validating our theoretical predictions up to a precision of individual pixels. We also perform experiments on CLEVR-based data and show that, unlike current SOTA object detection methods (SAM, CutLER), our method's prediction errors always lie within our theoretical bounds. We hope that this work helps open up an avenue of research into object detection methods with theoretical guarantees.

Main paper: 
 introduction: 
 Unsupervised object detection using deep neural networks is a long-standing area of research at the intersection of machine learning and computer vision. Its aim is to learn to detect objects from images without the use of training labels. Learning without supervision has multiple advantages, as obtaining labels for training data is often costly and time consuming, and in some cases may be impractical or unethical. For example, in medical imaging, unsupervised object detection can help save specialists' time by automatically flagging suspicious abnormalities [19] , and in autonomous driving it may help automatically detect pedestrians on a collision course with the vehicle [3] . It is thus important to understand and develop better unsupervised object detection methods.While successful, current object detection methods are often empirical and possess few to no guarantees about their learned representations. In this work we aim to address this gap by designing the first unsupervised object detection method that we prove is guaranteed to learn the true object positions up to small shifts, and performing a detailed analysis of how the maximum errors of the learned object positions depend on the encoder and decoder receptive field sizes, the object sizes, and the sizes of the Gaussians used for rendering. This is especially important in sensitive domains such as medicine, where incorrectly detecting an object could be costly. Our method guarantees to detect any object that moves in a video or that appears at different locations in images, as long as the objects are distinct and the images are reconstructed correctly.We base our unsupervised object detection method on an autoencoder with a convolutional neural network (CNN) encoder and decoder, and modify it to make it exactly translationally equivariant (sec.3). This allows us to interpret the latent variables as object positions and lets us train the network without supervision. We then use the equivariance property to formulate and prove a theorem that relates the maximum position error of the learned latent variables to the size of the encoder and decoder receptive fields, the size of the objects, and the width of the Gaussian used in the decoder (sec. 4). Next, we derive corollaries describing the exact form of the maximum position error as a function of these four variables. These corollaries can be used as guidelines when designing unsupervised object detection networks, as they describe the guarantees of the learned object positions that can be obtained under different settings. We then perform synthetic and CLEVR-based [12] experiments to validate our theory (sec. 5). Finally, we discuss the implications of our results for designing reliable object detection methods (sec. 6).Concretely, the contributions of this paper are:1. An unsupervised object detection method that is guaranteed to learn the true object positions up to small shifts. 2. A proof and detailed theoretical analysis of how the maximum position error of the method depends on the encoder and decoder receptive field sizes, object sizes, and widths of the Gaussians used in the rendering process. 
related work: 
 Object Detection. Object detection is an area of research in computer vision and machine learning, dealing with the detection and location of objects in images. Popular supervised approaches to object detection include Segment Anything (SAM) [13] , Mask R-CNN [7] , U-Net [18] and others [4] . While successful, these methods typically require large amounts of annotated segmentation masks and bounding boxes, which may be costly or impossible to obtain in certain applications. Popular unsupervised and self-supervised object detection methods include CutLER [23] , Slot Attention [17] , MoNet [2] and others [5] . These methods aim to learn object-centric representations for object detection and segmentation without using training labels. Finally, unsupervised object localisation methods such as FOUND [21] and others [22] aim to localise objects in images, typically using vision transformer (ViT) self-supervised features. Compared to both current supervised and unsupervised object detection and localisation methods, our work is the only one that has provable theoretical guarantees of recovering the true object positions up to small shifts. It also requires no supervision.Identifiability in Representation Learning. Identifiability in representation learning refers to the issue of being able to learn a latent representation that uniquely corresponds to the true underlying latent representation used in the data generation process. Some recent works aim to reduce the space of indeterminacies of the learned representations, and thus achieve identifiability, by incorporating various assumptions into their models. Xi et al. [24] categorise these assumptions for generative models into constraints on the distribution of the latent variables and constraints on the generator function. Some of their categories include non-Gaussianity of the latent distribution [20] , dependence on an auxiliary variable [9, 10] , use of multiple views [16] , use of interventions [1, 15] , use of mechanism sparsity [14] , and restrictions on the Jacobian of the generator [6] . In contrast, in our work we achieve identifiability by making our network equivariant to translations, imposing an interpretable latent space structure, and requiring the data to obey our theorem's assumptions.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We discuss the limitations in sec. 6.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
synthetic experiments, clevr-based experiments, and real video experiments validating our: 
 theoretical results up to precisions of individual pixels.In this section we describe the proposed method for unsupervised object detection with guarantees. On a high level, our architecture is based on an autoencoder that is fully equivariant to translations, which we achieve by making the encoder consist of a CNN followed by a soft argmax function to extract object positions, and making the decoder consist of a Gaussian rendering function followed by another CNN to reconstruct an image from the object positions (fig. 1 ). In the following sections we describe the different parts of the architecture in detail.Autoencoder with CNN Encoder and Decoder. We start with an autoencoder, a standard unsupervised representation learning model, consisting of an encoder network ψ that maps an image x to a low-dimensional latent variable z, followed by a decoder network ϕ that maps this variable back to an image x, with the objective of minimising the difference between x and x. Typically, the encoder and decoder networks are parametrised by multi-layer perceptrons (MLPs) or convolutional neural networks (CNNs) paired with fully-connected (FC) layers, however neither of these parametrisations by default can guarantee that the learned latent variables will correspond to the true object positions (because of the universal approximation ability of MLPs and FC layers [8] ). To obtain such guarantees, we would thus like to modify the autoencoder to make it exactly translationally equivariant, that is, a shift of an object in the input image x should correspond to a proportional shift of the latent variable z, and a shift of the latent variable z should correspond to a shift in the predicted image x.We start with an autoencoder where the encoder and decoder are both CNNs. CNNs consist of layers computing the convolution between a feature map x and a filter F , defined in one dimension asEQUATIONIntuitively, this corresponds to sliding the filter F across the feature map x and at each position of the filter i computing the dot product between the feature map x and the filter F . We can prove that convolutional layers are equivariant to translations, sinceEQUATION)where τ is the translation operator that translates a feature map by t pixels, and we have used the substitution j → j + t at the second equality. Therefore, the encoder and decoder are both equivariant to translations, but this property only holds for translations of feature maps (i.e. spatial tensors).From Encoder Feature Maps to Latent Variables. So far we have only worked with images and feature maps, but the latter do not directly express positions of any detected objects. It would be preferable to convert these feature maps into scalar variables that can be interpreted as object positions that are equivariant to image translations. To do this, we first define a translation τ of a (1D) feature map x and a translation τ ′ of a scalar z asEQUATION) where i is the position in the feature map x, τ shifts an image by t pixels, and τ ′ shifts a scalar by t units. To relate translations in feature maps to translations in latent variables, we can use a function that computes a scalar property of a feature map x, such as argmax, defined as argmax(x) = {i : x[j] ≤ x[i] ∀j}. Using these definitions we can now prove the equivariance of argmax, i.e. that shifting the feature map x by τ corresponds to shifting the latent variable argmax(x) by τ ′ :EQUATION) where at the first equality we use the definition of argmax, at the second equality we use the definition of τ (eq. 3, left), at the third equality we use the substitution i → i + t, at the fourth equality we use the definition of argmax, and at the last equality we use the definition of τ ′ (eq. 3, right).However, because the argmax operation is not differentiable, for neural network training we approximate it via a differentiable soft argmax function, defined in 2D asEQUATION)where σ is the softmax function defined in one dimension as σ(x)[i] = exp(x[i])/ j exp(x[j]), σ 1 (x) and σ 2 (x) is the softmax function evaluated along the first and second dimensions of x, Θ is a temperature hyperparameter, [i, j] is the image index, I is the image width, J is the image height, and the term 1/2 ensures that the densities correspond to pixel centres. As the temperature Θ in eq. 5 approaches zero, softargmax reduces to the classical argmax function.From Latent Variables to Decoder Feature Maps. Similar to mapping from encoder feature maps to latent variables, we would now like to relate shifts in latent variables z to shifts of decoder feature maps x. To do this, we can invert the action of the argmax operation. Because argmax is a many-toone function, finding an exact inverse is not possible, but we can obtain a pseudo-inverse using the Dirac delta function defined as delta(z)[i] = δ(i -z). We can show that delta is a pseudo-inverse of argmax because argmax • delta • z = i : δ(j -z) ≤ δ(i -z) ; ∀j = z. Now, similar to the argmax function, we can prove that the delta function is equivariant to the latent variable shift τ ′ on the input and the feature map shift τ on the output, i.e.EQUATIONwhere at the first equality we have used the definition of delta, at the second equality we have used the definition of τ ′ (eq. 3, right), at the third equality we have used the definition of delta, and at the last equality we have used the definition of τ (eq. 3, left).Again, because the delta function is not differentiable, we can approximate it using a differentiable render function as render(z)[i] = N (i -z, σ 2 ) (7)where N (i -z, σ 2 ) is a Gaussian evaluated at i -z with variance given by the hyperparameter σ 2 . As the variance σ 2 in eq. 7 approaches zero, the render function reduces to the hard delta function.Additionally, because the decoder is translationally equivariant, we also condition it on positional encodings of the size of the images to provide it with sufficient information to reconstruct different parts of the background, assuming the background is static. Alternatively, if background is varying, the decoder can be conditioned on a randomly-sampled nearby video frame instead, which will provide information about the background but not the objects' positions (following Jakab et al. [11] ).We also note that since the latent variables z are ordered, this allows the encoder and decoder to learn to associate each variable with the semantics of each object and achieve successful reconstruction.We thus now have all the elements we need to create an equivariant architecture where the encoder and decoder are defined, respectively, byEQUATION) This is shown in fig. 1 . Having designed an exactly translationally equivariant architecture now allows us to obtain theoretical guarantees about the learned latent variables, which we discuss next. 1Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: Our paper focuses on fundamental research and theory and does not present direct malicious/unintended uses etc. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
theoretical results: 
 In this section we present our main theorem stating the maximum bound on the position errors of the latent variables learned with our method in terms of the encoder and decoder receptive field sizes, the object size, and the Gaussian standard deviation (thm. 4.1). We continue by deriving specialised corollaries relating the maximum position error to the encoder receptive field size (cor. 4.2), decoder receptive field size (cor. 4.3), object size (cor. 4.4), and Gaussian standard deviation (cor. 4.5). Theorem 4.1. Error Bound. Consider a set of images x ∼ X with objects of size s o , CNN encoder ψ with receptive field size s ψ , CNN decoder ϕ with receptive field size s ϕ , soft argmax function softargmax, rendering function render with Gaussian standard deviation σ G and ∆ G ∼ N (0, σ 2 G ), and latent variables z, composed as z = softargmax • ψ • x and x = ϕ • render • z (fig. 1 ). Assuming (1) the objects are reconstructed at the same positions as in the original images, (2) each object appears in at least two different positions in the dataset, and (3) there are no two identical objects in any image, then the learned latent variables z correspond to the true object positions up to object permutations and maximum position errors ∆ of For proof see appendix A. Intuitively, the assumptions ensure that each latent variable corresponds to the position of each object in the image. The error in the learned object positions then arises from both the encoding and decoding process. In the encoding process, the maximum error occurs when the encoder and the object are as far away from each other as possible while still overlapping, i.e. 2a ). Conversely, in the decoding process, the maximum error occurs when the rendered object and the latent variable are as far away from each other as possible while both still being inside the decoder receptive field, i.e. s ϕ -s o /2 (fig. 2b ). Additionally, there is an extra error of ∆ G as the latent variable is rendered by a Gaussian and the decoder can capture any part of this Gaussian. Finally, because we assume each object is reconstructed at the same position as in the original image, the errors from the encoder and decoder must cancel each other out. Therefore, the overall maximum position error is given by the lower of the two expressions for the encoder and the decoder, leading to eq. 9. Next, we present corollaries relating this error bound to different factors. EQUATIONs ψ /2 + s o /2 -1 (fig.∆(s ψ ) = s ψ 2 + so 2 -1 if 1 ≤ s ψ ≤ s ϕ -2s o + 2, s ϕ 2 -so 2 + ∆ G if s ψ > s ϕ -2s o + 2.For an illustration see fig. 3a . There are two regions of the curve (separated by a dashed line). In the left-most region, s ψ < s ϕ -2s o + 2, the error is dominated by the encoder error, and in the right-most region, s ψ ≥ s ϕ -2s o + 2, the error is dominated by the decoder error. Initially, for s ψ = 1, the error is given by s o /2 -1/2, because the 1 × 1 px encoder can match any pixel that is part of the object and so can be at most half of the object size away from the true object position that is at the centre of the object. As the encoder RF size increases up to s ϕ -2s o + 2, the position error increases linearly with it as s ψ /2 + s o /2 -1, because now any part of the encoder RF can match any part of the object (fig. 2a ). This bound is deterministic due to the deterministic encoding process.At s ψ = s ϕ -2s o + 2 (vertical dashed line in fig. 3a ), the maximum errors from encoder and decoder both become equal to s ϕ /2 -s o /2. For s ψ > s ϕ -2s o + 2, the position error is dominated by the error from the decoder which is constant ats ϕ /2 -s o /2 + ∆ G with ∆ G ∼ N (0, σ 2 G ), and so even though the encoder RF size is increasing, this has no effect as the limiting factor is now the decoder. Due to the Gaussian rendering step in the decoding process, this bound is now probabilistic, and is distributed normally with variance σ 2 G .The results of corollary 4.2 can be extended to multiple objects with different sizes (see appendix B, cor. B.1) Corollary 4.3. Error Bound vs. Decoder RF Size. The maximum position error as a function of the decoder receptive field (RF) size s ϕ for a given s ψ , s o , σ G , is∆(s ϕ ) = s ϕ 2 -so 2 + ∆ G if s o ≤ s ϕ < s ψ + 2s o -2, s ψ 2 + so 2 -1 if s ϕ ≥ s ψ + 2s o -2.For an illustration see fig. 3b . Similar to corollary 4.2, there are two regions of the curve, one for s ϕ < s ψ + 2s o -2 (left), where the error is dominated by the decoder error, and another fors ϕ ≥ s ψ + 2s o -2 (right), where the error is dominated by the encoder error. Note that this is opposite to cor. 4.2. Initially, for s ϕ = s o , the decoder receptive field has the same size as the object, ∆(s o ) = s ψ 2 + so 2 -1 if 1 ≤ s o ≤ s ϕ 2 - s ψ 2 + 1, s ϕ 2 -so 2 + ∆ G if s ϕ 2 - s ψ 2 + 1 < s o ≤ s ϕ .For 2b ). At s o = s ϕ , the object reaches the same size as the decoder, and thus the position error decreases to 0 with an additional error due to the width of the Gaussian, ∆ G . Interestingly, the triangular shape of the error curve means that small and large objects will both incur small position errors, while medium sized objects will incur higher errors. Corollary 4.5. Error Bound vs. Gaussian Size. The maximum position error as a function of the Gaussian standard deviation σ G for a given s ψ , s ϕ , s o , is∆(σ G ) = s ϕ 2 -so 2 + ∆ G if σ G < s ψ 2 - s ϕ 2 + s o -1, s ψ 2 + so 2 -1 if σ G ≥ s ψ 2 - s ϕ 2 + s o -1.For an illustration see fig. 3d . Firstly, there is an overall maximum bound for the position error due to the encoder, given by the constant s ψ /2 + s o /2 -1, which is independent of the Gaussian standard deviation. Then, initially for σ G = 0, the rendered Gaussian is effectively a delta function, and so the position error is dominated by the decoder error given by s ϕ /2 -s o /2, which describes the maximum distance between the object and the delta function with both of them fitting inside the decoder receptive field (fig. 3b ). As the Gaussian standard deviation increases, the position error increases linearly ass ϕ /2 -s o /2 + ∆ G with ∆ G ∼ N (0, σ 2 G ).Then, depending on what part of the Gaussian the decoder is convolved with, there are different bounds for the maximum position error. If the decoder is convolved with a part of the Gaussian that is within n standard deviations of its centre, the maximum position error increases linearly ass ϕ /2 -s o /2 + nσ G up to σ G = (s ψ /2 -s ϕ /2 + s o -1)/n, after which point the position error becomes dominated by the encoder value of s ψ /2 + s o /2 -1. In fig. 3d , the maximum position error bound when the decoder is convolved with a part of the Gaussian within its first and second standard deviations, is denoted by darker and lighter shades of blue, respectively. 
experimental results: 
 In this section we validate our theoretical results on synthetic experiments (sec. 5.1) and CLEVR data (sec. 5.2). Additional real video experiments are in app. E. We first validate corollaries 4.2-4.4 via synthetic experiments in sec. 5.1, demonstrating very high agreement up to sizes of individual pixels. We then apply our method to CLEVR-based [12] data containing multiple objects of different sizes in varying scenes (sec. 5.2) and show that compared to current SOTA object detection methods (SAM [13] , CutLER [23] ), only our method predicts positions within theoretical bounds.In this section we validate corollaries 4.2-4.5 via synthetic experiments. Our dataset consists of a small white square on a black background. In each experiment we fix all but one of the encoder RF size s ψ , decoder RF size s ϕ , object size s o , and Gaussian standard deviation σ G , and vary the remaining variable. We perform each experiment 20 times, corresponding to 20 random initializations of the trained parameters, and record the position error ∆ as the difference between the predicted object position z and the ground truth object position z GT . For more details see appendix C.1.Position Error vs. Encoder RF Size. In this experiment we aim to empirically validate corollary 4.2, by measuring the experimental position errors as a function of the encoder receptive field size. We vary the encoder RF sizes s ψ ∈ {1, 3, . . . , 31} and fix s ϕ = 25, s o = 9, σ G = .8 and record position errors ∆. We visualise the data points (red) and the theoretical bounds (blue) in fig. 4a . We can observe that all the data points lie at or below the theoretical boundary, which validates corollary 4.2. In particular, we observe that the deterministic boundary in the region to the left of the dashed line (corresponding to the encoder bound) is well respected, with some of the trained networks achieving exactly the maximum error predicted by theory.Position Error vs. Decoder RF Size. In this experiment we aim to validate corollary 4.3 by measuring the experimental position errors as a function of the decoder receptive field size. We vary the decoder RF sizes s ϕ ∈ {1, 3, . . . , 31} and fix s ϕ = 9, s o = 9, σ G = .8 and record position errors ∆. We visualise the results in fig. 4b . The figure shows the theory to be a strong fit to the data, validating corollary 4.3. In particular, we note that the data points fit the Gaussian distribution in the decoder part of the curve (left of the dashed line) and are very close to (1 px below) the deterministic upper bound in the encoder part of the curve (right). Position Error vs. Gaussian Size. In this experiment we aim to validate corollary 4.5 by measuring the experimental position errors as a function of the Gaussian standard deviation. We vary the Gaussian standard deviations σ G ∈ {0.1, 0.2, . . . , 2.1, 2.25, 2.5, ..., 5}, fixing s ψ = 9, s ϕ = 11, s o = 7 and record position errors ∆. We visualise the data points (red) and the theoretical bounds (blue) in fig. 4d . As all the data points lie at or below the theoretical boundary, this validates corollary 4.5. In particular, we note that all the data points lie below the encoder bound (solid blue line), and all the data points lie within the bound denoted by four standard deviations away from the Gaussian. This means that in practice, the decoder can be convolved with any part of the Gaussian that lies within 4 standard deviations (corresponding to 3.2 px) from its centre. We also note that as the Gaussian standard deviation increases, the position error increases as expected, denoted by the positive slope of the data points between the third and fourth standard deviations (lightest shade of blue).In this section we validate our theory on CLEVR-based [12] image data of 3D scenes. Our dataset consists of 3 spheres of different colours at random positions, with a range of sizes due to perspective distortion. We train and evaluate each experiment similarly to those in sec. 5.1, recording position errors for the learned objects, and compare our results with SAM [13] and CutLER [23] baselines. We compute the theoretical bounds according to our theory in sec. 4 Once again, the experimental results demonstrate high agreement with our theory, now even for more complex images with multiple objects and a range of object sizes (fig. 5 , red, blue). Furthermore, while the SAM and CutLER baselines generally achieve low position errors, this is not guaranteed, and in some cases their errors are much higher than our bound (fig. 5 , green, orange). We report the proportion of position errors from fig. 5c that lie within 2 standard deviations of our theoretical bound in table 6b and fig. 6a , showing that compared to SOTA object detection methods, only for our method are the position errors always guaranteed to be within our theoretical bound. 
discussion: 
 In light of our theoretical results, in this section we present some conclusions that can be drawn when designing new unsupervised object detection methods: 1. If the size of the objects that will be detected is known, to minimise the error on the learned object positions, one should aim to design the decoder receptive field size to be as small as possible while still encompassing the object. As the decoder RF grows beyond the object size, the error bound increases linearly with it up to a certain point (fig. 3b ).2. To minimise the error stemming from the encoder for a given object size, the encoder RF size should be kept as small as possible while still detecting the object (the RF size may be smaller than the object size), as again the error bound grows linearly with it up to a certain point (fig. 3a ).3. To minimise the error, the width of the rendering Gaussian should be kept as small as possible while still permitting gradient flow, as increasing it even slightly may result in a dramatic increase to the decoder term of the position error (fig. 3d ). This is because, in practice, the decoder is able to detect parts of the Gaussian that are even 4 standard deviations away from its centre (fig. 4d ).4. In the case that one does not know a priori the exact size of the objects to be detected, one can still design a network that minimises the position errors for a given range of sizes. In that case, one should set up the decoder RF size to be as close as possible to the size of the largest object, and keep the encoder RF size as small as possible while still detecting all objects. The position errors for different object sizes will then be distributed according to the curve in fig. 3c , where the smallest and largest objects will achieve lowest errors and medium-size objects will achieve the greatest error, approximately given by a half of the average of the encoder and decoder RF sizes.Finally, we discuss some limitations of our method. Firstly, the method can only detect dynamic objects, for example if they move in a video or if they appear at multiple locations in images. Secondly, in its current form the method learns representations that can not be used for videos with different backgrounds than the one used at training time; however, this can be overcome by conditioning the decoder on an unrelated video frame instead of the positional encodings, as in Jakab et al. [11] .Thirdly, the guarantees of our method are conditional on the images being successfully reconstructed, which depends on the network architecture and optimisation method. 
conclusion: 
 We have presented the first unsupervised object detection method that is provably guaranteed to recover the true object positions up to small shifts. We proved that the object positions are learned up to a maximum error related to the encoder and decoder receptive field sizes, the object sizes, and bandwidth of the Gaussians used to render the objects. We derived expressions for how the position error depends on each of these factors and performed synthetic experiments that validated our theory up to sizes of individual pixels. We then performed experiments on CLEVR-based data, showing that unlike current SOTA methods, the position errors our method are always guaranteed to be within our theoretical bounds. We hope our work will provide a starting point for more research into object detection methods that possess theoretical guarantees, which are lacking in current practice.A Proof of Theorem 4.1Theorem Maximum Position Error. Consider a set of images x ∼ X with objects of size s o , CNN encoder ψ with receptive field size s ψ , CNN decoder ϕ with receptive field size s ϕ , soft argmax function softargmax, rendering function render with Gaussian standard deviation σ G and ∆ G ∼ N (0, σ 2 G ), and latent variables z, composed as z = softargmax • ψ • x and x = ϕ • render • z (fig. 1 ). Assuming (1) the objects are reconstructed at the same positions as in the original images, (2) each object appears in at least two different positions in the dataset, and (3) there are no two identical objects in any image, then the learned latent variables z correspond to the true object positions up to object permutations and maximum position errors ∆ ofEQUATIONProof. By assumption (1), the positions (z 1 , z 2 ) objects in the original image x have to be the same as the positions (ẑ 1 , ẑ2 ) of the objects in the reconstructed image x. In practice, this occurs whenever the reconstruction loss is minimised.By assumption (2) (each object appears at a minimum of 2 different positions), the latent variables used by the decoder have to contain some information about each object, and thus the encoder has to learn to match all the objects. This is because the decoder CNN ϕ takes as its input the rendered Gaussians ê = render•z concatenated with positional encodings or a randomly sampled nearby frame (fig. 1 ), and if some object in the dataset only appeared at a single position the model could achieve perfect reconstruction solely by using the positional encodings or the conditioned image without having to use the Gaussian maps ê. However, because the dataset contains each object at a minimum of 2 positions, relying purely on positional encodings or on the conditioned image is now not sufficient, as without any information about the object passed to the decoder, it would be impossible for it to predict where to render the object. More formally, becausex = ϕ • render • softargmax • ψ • x,this means that for objects in x to be reconstructed at the same positions as in x (assumption 1), the encoder ψ needs to match some part of each object in x.Because z = softargmax • ψ • x is equivariant to translations of x (sec. 3), and because the encoder ψ has to match some part of each object in x (as shown previously), and also each image consists of distinct objects (assumption 3) on a known background, the image x with an object at the position (u 1 , u 2 ) is encoded by softargmax • ψ to the latent variablesEQUATIONwhere the shifts ∆ ψ1 and ∆ ψ2 arise because any part of the encoder filter (of size s ψ ) can match any part of the object (of size s o ). See fig. 2a for an illustration.Next, because x = ϕ • render • z is equivariant to translations of z (sec. 3), the latent variables z = (u 1 + ∆ ψ1 , u 2 + ∆ ψ2 ) are mapped to a predicted image x = ϕ • render • z with an object at positionEQUATION)where the shifts ∆ ϕ1 and ∆ ϕ2 arise because any part of the decoder filter (of size s ϕ ) can match any part of the the rendered Gaussian êt = render • z, where∆ G ∼ N (0, σ 2 G ). See fig. 2b for illustration.Finally, by assumption (1), the position of each object in the original image x has to be equal to the position of the object in the reconstructed image, i.e.EQUATIONThis results in the conditionsEQUATIONand therefore|∆ ψ1 | = |∆ ϕ1 |, |∆ ψ2 | = |∆ ϕ2 | (15)In words, the shift in the latent variables acquired from the encoder ∆ ψ has to be balanced by an opposite shift of the same magnitude in the decoder ∆ ϕ in order to reconstruct the object at the same position. Because the shift due to the encoder is of maximum magnitude of s ψ /2 + s o /2 -1 and the shift due to the decoder has a maximum magnitude of s ϕ /2 -s o /2 + ∆ G , this means that the maximum magnitude of the shift of the latent variables has to be the minimum of these two expressions, i.e. the learned latent variables (z 1 , z 2 ) correspond to the ground truth latent variables (u 1 , u 2 ) up toEQUATION)Additionally, because the order in which the objects get mapped to each latent variable is arbitrary, there is an additional indeterminacy arising due to variable permutations. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: Our models and data do not pose risks for misuse.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: Our paper does not use existing assets; we are the authors of all code.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: The results of corollary 4. ], σ G , is ∆(s ψ ) =      s ψ 2 + s max o 2 -1 if 1 ≤ s ψ ≤ s ϕ -2s max o + 2, s ψ 4 + s ϕ 4 -1 2 + ∆ G if s ϕ -2s max o + 2 < s ψ ≤ s ϕ -2s min o + 2, s ϕ 2 - s min o 2 + ∆ G if s ψ > s ϕ -2s min o + 2.For an illustration see fig. ∆(s ϕ ) =      s ϕ 2 - s min o 2 + ∆ G if s min o ≤ s ϕ ≤ s ψ + 2s min o -2, s ψ 4 + s ϕ 4 -1 2 + ∆ G if s ψ + 2s min o -2 < s ϕ ≤ s ψ + 2s max o -2 s ψ 2 + s max o 2 -1 if s ϕ > s ψ + 2s max o -2.For an illustration see fig. 7b . Dataset. In all of the synthetic experiments, we use the following setup. The dataset consists of black images of size s img × s img = 80 × 80 px, each with a white square with dimensions s o × s o px, centered at positions (x, y) where x, y ∈ {s pad + s o /2, s pad + s o /2 + 1, . . . , s img -s pad -s o /2}, where s pad ≥ max(s ψ , s ϕ ) -1 (to prevent unwanted edge effects). We divide the dataset into 4 quadrants and assign images from 3 quadrants to the training set and the remaining quadrant to the test set.Evaluation. For each experiment, we fix all but one variable from the following set: encoder RF size s ψ , decoder RF size s ϕ , object size s o , and Gaussian standard deviation σ G , and vary the remaining variable. For each value of the investigated variable we perform 20 experiments with different random seeds, noting down the learned position error ∆ as the absolute difference between the learned position z and the centre of the object z GT (maximum over horizontal and vertical differences, and over the test set). We discard a result if the reconstruction accuracy of the run is below 99.9%, to only consider runs where the object has been detected successfully (this is because the square is on the order of 7 × 7 px, thus only comprising 0.8% of the image).Architecture. We parametrise both the encoder ψ and the decoder ϕ as 5-layer CNNs with Batch Normalisation and ReLU activations, 32 channels, and filter sizes in {1 × 1, 3 × 3, 5 × 5, 7 × 7}, such that their receptive field sizes equal s ψ and s ϕ respectively. We train each network for 500 epochs using the Adam optimiser with learning rate 10 -3 and batch size 128. We train each experiment on a single GPU for around 6 hours with <6GB memory on an internal cluster.Dataset. Our CLEVR experiments use data generated with the CLEVR [12] image generation script.Our training and test sets consist of 150 and 50 images respectively, containing red, green and blue metallic spheres on a random background, at random positions, and with a different range of sizes (fig. 8 ). For experiments measuring position error as a function of encoder and decoder RF sizes and Gaussian s.d., we use a dataset with object sizes between 6-10 px after perspective distortion (fig. 8a ). For the experiment measuring position error as a function of object size, we use 5 datasets with object sizes 9-14 px, 11-17 px, 13-19 px, 15-24 px, 17-27 px after perspective distortion (figs. 8b, 8c). Evaluation. For each experiment, we fix all but one variable from the following set: encoder RF size s ψ , decoder RF size s ϕ , object size s o , and Gaussian standard deviation σ G , and vary the remaining variable. For each value of the investigated variable we perform experiments with different random seeds, noting down the learned position errors ∆ as the absolute difference between the learned position z of each object and the centre of the object z GT (maximum over horizontal and vertical differences and over the test set, for each object). We only consider results for objects that have been learned successfully. For experiments measuring position error as a function of encoder and decoder RF sizes and Gaussian s.d., we consider an object to be learned if the position error is less than 35 px, and if only a single variable corresponds to the object, and if the position error is stable over consecutive training iterations. For the experiment measuring position error as a function of object size, we only consider runs where all 3 objects have been learned, i.e. where the reconstruction accuracy is higher than 98.0% for the dataset with object sizes 6-10 px, 98.8% for dataset with sizes 11-17 px, 98.0% for dataset with sizes 13-19 px, 97.5% for dataset with sizes 15-24 px, and 98.0% for dataset with sizes 17-27 px.Architecture. We parametrise both the encoder ψ and the decoder ϕ as 5-layer CNNs with Batch Normalisation and ReLU activations, 32 channels, and filter sizes in {1 × 1, 3 × 3, 5 × 5, 7 × 7}, such that their receptive field sizes equal s ψ and s ϕ respectively. We train each network until convergence using the Adam optimiser with learning rate 10 -2 and batch size 128 for the experiments measuring position error as a function of encoder and decoder RF size and Gaussian s.d., and with learning rate 10 -3 and batch size 150 for the experiment measuring position error as a function of object size. We train each model on a single GPU for less than day with <8GB memory on an internal cluster.Baselines. We also evaluate the results for two State-of-the-Art baselines, SAM [13] and CutLER [23] . First, for each of our 6 datasets (containing objects of sizes 6-10 px, ..., 17-27 px), we combine its training and test set to create 4 sets of 50 images each. We then apply SAM and CutLER to all images in each 50-image set, noting down the learned position errors ∆ as the absolute difference between the predicted position z of each object and the centre of the object z GT (maximum over horizontal and vertical differences and over the 50-image set, for each object). For SAM, we take the predicted object positions to be the centres of the bounding boxes corresponding to the second, third and fourth predicted masks (first mask corresponding to the background). For CutLER, we take the predicted object positions to be the centres of the predicted bounding boxes if the method predicts 3 bounding boxes (one for each object), otherwise we discard the prediction. For both methods, we discard any result where position error is greater than 35 px, to be consistent with the evaluation for our method. Finally, this results in 12 position error values (3 objects × 4 data splits), for each method and each of our 6 datasets.To demonstrate that our method applies to objects of any shape, in this section we include experiments on our CLEVR dataset with three distinct objects -a red metallic sphere, a blue rubber cylinder and a green rubber cube. The dataset has objects of size 9-19 px after perspective distortion, and a sample from the dataset is shown in fig. 9a . We perform training and evaluation in the same way as in app. C.2. We plot the position error as a function of the encoder and decoder receptive field sizes in figs.9b and 9c, respectively. We can observe that all our experimental data (red) lies within the bounds predicted by our theory (blue), successfully validating our theory for objects with different shapes. In this section we present experimental results of applying our method to real YouTube videos, including overhead traffic footage and mini pool game footage.In this experiment we aim to learn the position of a car from an overhead traffic video. The training and test sets for this experiment consist of 25 frames each, from a video of an overhead view of a car moving for a short distance in a single lane (fig. 10a ). We train the architecture from fig. 1 In practice, it was important to set the encoder and decoder receptive field sizes to be greater than but close to the size of the objects, as for larger RF sizes the position error increased unnecessarily and the images were rendered further away from the position given by the latent variables. Also, for large receptive field sizes, the decoder filter contained too much background which caused low quality reconstructions when rendering the balls near the mini pool table edges. Justification: We clearly state our contributions and scope in the abstract and introduction.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.We note that a similar architecture was proposed by Jakab et al.[11], with empirical success in keypoint detection. However, we derive our architecture by enforcing strict translation equivariance properties, which makes our theoretical results possible. 


Decision: This paper is about unsupervised object detection, the authors propose a way to build an unsupervised object detection with theoretical guarantees, meaning known bounds on position errors, via an autoencoder architecture with latent variables.

The paper contributes to the start of the art with a unsupervised object localization architecture that can recover true object positions to a known error bound, and theoretical analysis to demonstrate error bounds, and how these bounds depend on encoder/decoder receptive field sizes, object size, and gaussian variance during rendering. Experiments are made on synthetic data generated by the authors and on CLEVR dataset, and show the validity of the bounds.

All reviewers agree that the paper is very well written and mostly easy to understand/follow, there is a good evaluation and a comparison to previous methods (SAM and cutLER), and the approach is in the right direction to solve the unsupevised object detection problem, with an innovative and novel approach.

One minor weakness is that all experiments are made on synthetic data, and its not clear how this method would perform in real data.

Some minor improvements are suggested for this paper, the proposed method actually performs object localization, as the whole theoretical guarantee is about object localization, and object detection also includes object classification which is not considered in this approach, clarify the training process, and the limitations and assumptions of the proposed approach. Also please consider the many small details mentioned by the reviewers.

Overall this paper is above the acceptance threshold, and should be accepted.

Reviews: review: paper_summary: paper_summary: This paper presents the first unsupervised object detection approach that is theoretically shown to recover the true object positions up to quantifiable small deviations that are related to the encoder and decoder receptive field sizes, the object sizes, and the widths of the Gaussians used in the rendering process. The authors conduct a thorough analysis of how the error depends on each of these variables and conduct synthetic experiments that validate our theoretical predictions up to a precision of individual pixels. 
On a high level, their architecture is based on an autoencoder that is fully equivariant to translations, which they achieve by making the encoder consist of a CNN followed by a soft argmax function to extract object positions, and making the decoder consist of a Gaussian rendering function followed by another CNN to reconstruct an image from the object positions. 
The authors also conducted synthetic experiments, CLEVR-based experiments, and real video experiments that validated their theoretical findings up to a precision of individual pixels.
strength_weakness: strength_weakness: 1. It is interesting to learn that SAM and CutLER's errors are sometimes much higher than the bound derived by the proposed method. I would be interested to hear from the authors if they have any insights on how this finding could be used to improve these methods, especially CutLER, which is also an unsupervised object detection and instance segmentation model.

2. The majority of the experiments in this paper are conducted on synthetic datasets, and it is questionable whether the findings can be generalized to real images and videos. Could the authors provide some experiments on real images or videos? 

3. Continuing on the previous point, most objects in the synthetic datasets are rigid and have very consistent shapes. However, the challenges in object detection are often in detecting the non-rigid objects or partially occluded objects. I am curious to see if the proposed method can be used to handle these cases.
questions: questions: Please check the weakness section
limitations: limitations: Yes
paper_summary: paper_summary: The paper proposes a new idea for unsupervised object detection where an CNN based auto-encoder architecture is employed and the latent representation is trained to learn position of objects in images. They further provide theoretical analysis of the proposed idea under strong assumption about the input data and model characteristics. Results from on synthetic data experiments is also provided
strength_weakness: strength_weakness: The paper lacks results and discussion on the experimental details on how the idea can be effectively implemented. This is particularly important to understand the merits of the proposed idea as it has strong assumption on model architecture and input data (e,g, size of objects). For example, it is not clear how the authors processes input data during training, how the min-batch sampling is done, what input-target pairs are?, what regulations are important to use if at all, how the over-fitting is prevented given the very simplified experimental setting.
Furthermore, it is not clear from the paper how the latent space can learn any semantic information to reconstruct the images as it modeled to learn the position of the objects.
questions: questions: - Can the authors provide more clarification on the training procedure and the important aspects that are necessary for the model work?
- Given that the latent space is learning the position encoding for the object, how is it possible to learn to model semantics for reconstruction loss?
- how does the model performance change relative to diversity of object shape and appearance in a single image?
- why is it important to use positional encoding?
- how the reconstruction quality can be guaranteed, especially in a realistic setting?
limitations: limitations: - The work is limited by its assumptions on the characteristics of the input data and model architecture. 
- The theoretical analysis is dependant on strong assumptions like "the objects are reconstructed at the same positions" which itself is not guaranteed. 
- Furthermore, the evaluations do not provide insight into what challenges one should address to successfully train a model based on the proposed idea. 
- Please see the Weaknesses for more details.
paper_summary: paper_summary: This paper explores Unsupervised Object Detection with Theoretical Guarantees. This method is a significant advancement in the field of object detection as it provides theoretical guarantees on the accuracy of the detected object positions. By introducing a new approach that ensures reliable object localization, the research contributes to enhancing the robustness and accuracy of unsupervised object detection systems.
strength_weakness: strength_weakness: This work explores the unsupervised object detection, and theoretical analysis. However, the dataset for the experiment is not common, and few comparative experiments with common SOTA object detection model. Besides, although this work provides the theoretical guarantees to recover the true object positions up to quantifiable small shifts, there is no analysis whether it only exists in the unsupervised domain,.or can be adopted in the supervised domain.
questions: questions: 1. In the experiments, the datasets for evaluation is the CLEVR data, please explain why choose it, not other popular object detection datasets?
2. This work validate the theoretical results using lots of experimental results, however only few experiments are carried out for the comparison with SOTA.
3. In object detection, the popular model is about YOLO, and also the metric including accuracy, mAP, and IoU, etc are also the common in supervised object detection.
limitations: limitations: NA
paper_summary: paper_summary: This paper proposes an autoencoder based object detection model that makes predictions about object positions in an unsupervised manner. Imporantly, the authors can provide theoretical guarantees/ bounds about the degree of the model's detection error.
strength_weakness: strength_weakness: I have summarized my questions and issues and limitations that I see here: 

In the context of the CLEVR experiments, I am wondering why the authors don’t evaluate concerning the Gaussian standard deviation as they did for the first dataset?

The authors claim the method requires dynamic objects, but they never mention this in main text. Can the authors provide more justification of this? I.e. why this is/ what part of the approach requires this?

I don’t understand how the decoder can learn to reconstruct complex shapes other than spheres (due to the Gaussian assumption). Also the authors mainly evalaute on data with objects that are spherical. Thus, is it possible to evaluate on other shape forms? If so what is the error here compared to spherical shapes? I do not mention this as a limitation, but it seems quite important to put the method into context. What would be potential ideas to mitigate handling more complex objects?

I do not have enough knowledge about the details of the CutLer and SAM models, but why should the theoretical bound of this work hold for these works as well (the authors compare these in Fig. 6)? Specifically, the authors state "only for our
method are the position errors always guaranteed to be within our theoretical bound." so my question is: why should the other methods lie within this theoretical guarantee?

I am a little confused by the related works section. The authors discuss object-centric representation methods whose goal, unlike that of their method, is to learn a full representation of an object. This includes much more information than just position. In other words, it seems the method of this paper focuses “only” on the learning the position of an object. While this does not diminish the significance of the work, I think the work could benefit from discussing more on this difference between these works, to make the comparisons more fair and also focus more on works that focus on unsupervisedly localising object in images (i.e., works that only focus on position and not on the other aspects of object reperesentations), e.g., [1,2]. So in the end I am also wondering if the authors should actually narrow down the title/contribution claims to "Unsupervised Object Localisation with Theoretical Guarantees"?

If the authors can remark on these issues above, I am happy to consider raising my score.

[1] Siméoni, Oriane, Chloé Sekkat, Gilles Puy, Antonín Vobecký, Éloi Zablocki, and Patrick Pérez. "Unsupervised object localization: Observing the background to discover objects." In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3176-3186. 2023.
[2] https://github.com/valeoai/Awesome-Unsupervised-Object-Localization
questions: questions: see above
limitations: limitations: see above

Comments: comment: Thank you for answering the questions; I have raised my rating given the clarifications, However I strongly recommend the authors to update the paper with the clarifications they have provided, in particular on overfitting, how the ordering of the objects’ positions are key for the latent space, how sensitive is the proposed solution to object shape and appearance, and why including positional encoding is important.
I would like to thank the authors for their responses. Most of my questions have been addressed. Therefore, I will maintain my current rating as weak accept.
I would like to thank the authors for their responses. I will maintain the current score.
Thanks so much for the effort and clarification. I have raised my score accordingly.

Concerning my point about other related work: I think the authors could think about differentiatting throughout the work on the difference on learning object representations and explicit object (position) detection. But, the response was fine. And I am convinced if the authors edit the main text as they had responded.