Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: Detecting anomalies is a notoriously ill-defined problem. The notion of anomaly is not a rigorous concept and different algorithms produce different results. The paper critiques a broad set of methods which involve likelihood (or density) estimations. It's main idea revolves around the 'Principle' set on Page 4. The principle claims that when data capacity and computational constraints are removed, an AD algorithm should be invariant to 'reparametrization' of the input. Roughly speaking, that means the algorithm should be invariant to arbitrary 'name changing' of the input - the result should not change if each data item x is replaced by f(x) if f is invertible. 
The paper then shows that density models do not satisfy this principle even when they are 'perfect'.

My main critique of the paper is that this principal constitutes a completely unreasonable requirement of any AD algorithm, to the point where it is meaningless. It is trivial to observe (as the authors do) that any continuous distribution could be transformed to a uniform distribution with the correct f. Even if the domain is discrete we can make the input uniform: As an example think of f being a Pseudo-Random function, like say f(x) is a digital signature of x. If we believe cryptography then no efficient algorithm would be able to say anything useful. 

To sum up - I don't think the 'principle' is a useful prism by which to measure models and definitions, and therefore I don't find the contribution of the paper sufficient for publication.

As a side remark, this principle may be useful if further constraints are put on f, for instance, if we may want the AD algorithm to be oblivious to unit change in the data, which translates to f which multiplies dimension be a constant. 


review_title: The paper offers a critique of the guarantees density models can provide when used for anomaly detection. While I support a push for formal definitions and requirements I find the critique itself off the mark.

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper presents a negative result that anomaly detection by density estimation is flawed.  

After highlighting several problems with anomaly detection, the paper focuses on a seemingly plausible invariance argument, that the lack of invariance of a distribution's random variable to change of variable - reparameterization - makes it impossible to define which events fall in dense or rare areas of the distribution. Specifically it proposes the principle that an outcome represented by a random variable X or it's transformation fX should not result in change of it's classification as outlier versus inlier.  As the paper demonstrates, it is not difficult to devise a counter example of a transform f that can flip an outcome between inlier and outlier with weak conditions on any distribution of X. 

 The paper identifies inliers by introducing "typicality" as a measure. Although interesting, it contributes little to the paper's argument and unlike the level set definition of inliers, typicality does give not a constructive tool for anomaly detection. 

 However is any practical sense, the invariance argument is specious. Consider this example, of the distribution of sunlight over the earth. If one is interested in the effects of sunlight on population health (e.g. cancer rates) one looks at the distribution of intensity over individuals. Alternately if the question is the incidence over area (solar power potential) then its the random variable of land area that is relevant.  There is an invertable deterministic function between land area and population random variables given by the population per area . Clearly a place (think outcome) with low cancer incidence (an outlier) because of sparse population may be a good place for solar power. Hence the parameterization of random variable for anomaly detection is intrinsic to the problem rather than serving as a condition for invariance. 

 In a related area, invariance as applied to prior distributions has been studied extensively, as found in E. T. Jaynes, "Probability Theory" (Cambridge, 2003), ch 12, to show when invariance is applicable. 

I have no issue with the paper's rigor and derivations, rather the issue is with the unfounded presumption that invariance to reparameterization inhibits the use of density based anomaly detection. As the paper states in the final discussion, "defining anomalies might be impossible without prior knowledge"-- this may not be a bad thing, and the same material used to argue for a knowledge-based approach to anomaly detection that includes specifying a random variable appropriate for the domain would be a valuable, acceptable paper. 
review_title: Invariance is not a required condition for density estimation. 

final_score: rating: 4: Ok but not good enough - rejection
review_content: *Quality*
I have a major concern regarding the principle stated on the page 4 that the whole paper discussion is based on. 
First, I totally disagree that anomaly detection methods should be invariant under any invertible reparametrizations. In practice, quite often the very definition of an anomaly detection problem is tighted to a concrete data representation.
In addition, anomaly detection can be thought of as a binary classification and the stated principle amounts to saying that a binary classifier should provide the same results for any (invertible) data re-parametrization, e.g. using various feature extractors. This is clearly wrong thing to ask from a classifier and instead people focus on finding useful feature extractors. Hence, in the case of anomaly detection, it comes at no surprise that one can re-parametrize the data so that the anomaly detection algorithm (density or not density based) is totally confused.

While the paper has interesting discussions and constructions of the worst case scenarios for confusing density-based anomaly detection methods, I don’t think that the paper uses them to support a useful claim. 

*Clarity*
The paper is well-written in general. 

*Originality*
To my best knowledge, the theoretical study of the role of data re-parametrization for density-based anomaly detection is new.

*Significance*
I don’t think that the results of the paper are significant in their current form and might cause a confusion with its statements.

I would encourage the authors to clarify their view on the relation between anomaly detection and the underlying data representation and clarify/justify the principle from the page 4.


Pros
* The paper presents a collection of interesting transformations between densities

Cons
* The main message of the paper is based on unrealistic principle

review_title: While the paper has interesting discussions and constructions of the worst case scenarios for confusing density-based anomaly detection methods, I don’t think that the paper uses them to support a useful claim. 

final_score: rating: 4: Ok but not good enough - rejection
review_content: **Update**

My impression after the extensive discussion is that the remaining differences are possibly too subjective to come to an agreement:

1) Whether the fact that the invertible reparameterization principle does not hold for anomaly detection represents a significant theoretical contribution. To me, I still don’t quite see why, but I do believe there are other researchers with a stronger theory background more qualified than me to evaluate this, I will therefore downgrade my experience score by 1.
2) Whether the fact that the invertible reparameterization principle does not hold has promise to further understand the practical issues like the CIFAR10 vs SVHN phenomenon beyond things that have already been discussed in the literature - I think quite likely not, the different arguments for and against have been discussed in our back and forth I think.

I invite the AC to go through the discussion here to see the detailed arguments/rebuttals.

My personal impression, in case the authors are interested, is also the manuscript might be further improved by giving more space to these two questions, i.e. the motivation of the principle and instead moving some of the proofs to the supplementary. I think it is quite straightforward to understand that the principle cannot hold and more difficult to understand why it should hold in the first place.


**Summary**
In this manuscript, the authors highlight one phenomenon about density-based anomaly detection: Even the perfect density model can assign arbitrary densities if you allow an arbitrary invertible reparametrization of your data before estimating the densities and therefore will have arbitrary inlier/outlier classification. Therefore, methods that assign anomalies purely based on low density values cannot achieve a principle proposed by the authors: “anomaly detection methods should be invariant to any invertible reparametrization f”.

**Main Impression**
The manuscript is well-structured and well-written, allowing me to quickly understand the main argument of the paper (I hope), thanks for that. I found the analyses to be technically correct to the level I was able to analyze them.

Overall, I have some doubts about how much new practically relevant things can be learned about anomaly detection from the argument laid out in the paper.

**Details about Main Criticism**
1) The fact that densities can be arbitrarily changed by invertible functions is already an important building block of normalizing flows  - in order to learn any distribution starting from a predefined prior like a gaussian distribution. So in itself it does not seem like a new aspect to me. 
2) The effect of invertible reparametrizations on anomaly detection has already surfaced in the literature: E.g., in Nalisnick, 2018, they already report very different anomaly detection results if one uses only p(z) and ignores the log-determinant for an affine Glow Network. This setup there, as far as I see, fits in the framework here, with f there implemented by the affine Glow network. 
3) I am not sure I agree with the principle that anomaly detection methods should be invariant to invertible reparametrizations. An example: Let’s say you visualize the samples from a gaussian distribution as grayscale values, with gray at zero, and positive values becoming brighter, negative values becoming darker. Then very dark values as well as very bright values would be visually outliers. Now imagine you do an invertible reparametrization such that the distribution becomes bimodal with the modes further away from the center. Visually, originally somewhat darker/brighter values would be stretched to contain a lot of very dark/very bright values. Now some very dark values/very bright values would no longer be outliers in the perfect density model, but I would argue they would also visually no longer be outliers. 
4) Further, the original parametrization of e.g., the way images are stored is not arbitrary, but a parametrization where we as humans can perceive the content. 
5) Note also that in e.g., normalizing flows literature, it is always attempted that the estimated density is a lower bound for the discrete probabilities. There are also models directly modelling the discrete probabilities, e.g., see https://arxiv.org/abs/1905.07376 https://arxiv.org/abs/2006.12459. Note that normally, for density-based models one can compare the continuous and discrete models, while the proposed reparametrization logic here is not applicable for discrete models at all. 
6) The logic also rests on the assumption of the “true” density always being not zero/positive (footnote page 2). For the phenomena the paper references, I am not sure this is a good assumption. E.g., should SVHN-like zeros really have positive density under the true density of CIFAR-like frogs? One could also argue they have different support?
7) In my view, for the case of images, the anomaly detection phenomena are already well-explained by the line of thoughts in Ren et al., 2019; Serrà et al., 2020; Schirrmeister et al., 2020 and Kirichenko et al., 2020 so I am not sure in which scenarios the invertible-reparametrization aspect adds further understanding.

To summarize again, my main problem is, I am not convinced that “the result of an anomaly detection method should be invariant to any invertible reparametrization f” and that the failure to do so by density-based methods helps understand their failures as pointed out in recent literature.
 
**Suggestion for Improvement**
What would change my mind about the value of the phenomenon highlighted here is if there are examples in the literature where people use densities that are strongly affected by a reparametrization and are not aware of it. I think such examples would also be more useful rather than showing it also works with canonical distribution etc. I think the entire principle with invertible reparameterizations is clear enough, and any analyses showing it works in many mathematical settings, could be moved to supplementary. The more important question to me is when this principle makes sense at all.


**Other Points**
Is the whole setting in 2.1 one also used in literature? References might be helpful for “one would usually pick the set of regular points X_in such that this set contains the majority (but not all) of the mass (e.g.,95%) of this distribution”

“Without any constraints on the space considered, individual densities can be arbitrarily manipulated, which reveals how little these quantities mean in general.”
-> I don’t agree this shows how little densities mean in general. I think it shows how little they mean once you allow arbitrary invertible reparametrizations, and that maybe allowing this is not a good idea ;)

“It means that learning a representation with a predefined,  well-known distribution and knowing the true density p∗(X) are not sufficient conditions to control the individual density of each point and accurately distinguish outliers from inliers.”
-> I think this statement is a bit strange. If you know the true density at original parametrization and have access to the data in original parameterization, you can evaluate it and accurately distinguish outlier/inlier if they are defined by density-levels there in the first place. Also if they are invertibly transformed and you know the invertible transformation you can also invert it… if they are not defined by density-level at original parametrization, then the question is what are they defined by anyways, and you have a whole new question in my view.

I encourage the authors to also clear up any misunderstandings of the current manuscript from my side.
review_title: A well-written paper; unclear about the reasonableness of the main principle

Meta-review: Firstly, thank you authors for your thought-provoking submission and discussion.  The key point of disagreement clearly is the fundamental assumption that "the result of an anomaly detection method should be invariant to any continuous invertible reparametrization f."  All reviewers found this assumption to be too strong, leading all four to recommend rejection.

I also recommend rejection at this time.  To me, it seems reasonable and practical to assume that anomalies are defined based on distance (in a fixed feature space).  So if we are allowed to deform the space, clearly this definition breaks down and the concept of an anomaly becomes empty.  Perhaps I am wrong about this, but nevertheless, the paper could do a much better job of convincing the reader that its fundamental reparametrization assumption is appropriate and of consequence in practice.
Decision: Reject