Out-of-Distribution Detection using Maximum Entropy Coding

• URL: http://arxiv.org/abs/2404.17023v1
• Date: Thu, 25 Apr 2024 20:28:43 GMT
• Title: Out-of-Distribution Detection using Maximum Entropy Coding
• Abstract summary: For discrete distributions, the definitive answer is in principle given by Kolmogorov-Martin-L"of randomness. We transform data into a standard distribution in the latent space using a bidirectional generate network and use maximum entropy coding there.
• Score: 4.7768369720936255
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a default distribution $P$ and a set of test data $x^M=\{x_1,x_2,\ldots,x_M\}$ this paper seeks to answer the question if it was likely that $x^M$ was generated by $P$. For discrete distributions, the definitive answer is in principle given by Kolmogorov-Martin-L\"{o}f randomness. In this paper we seek to generalize this to continuous distributions. We consider a set of statistics $T_1(x^M),T_2(x^M),\ldots$. To each statistic we associate its maximum entropy distribution and with this a universal source coder. The maximum entropy distributions are subsequently combined to give a total codelength, which is compared with $-\log P(x^M)$. We show that this approach satisfied a number of theoretical properties. For real world data $P$ usually is unknown. We transform data into a standard distribution in the latent space using a bidirectional generate network and use maximum entropy coding there. We compare the resulting method to other methods that also used generative neural networks to detect anomalies. In most cases, our results show better performance.

Related papers

• High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
  We present algorithms for diffusion model sampling which obtain $$-error in $mathrmpolylog (1/)$ steps.<n>Our approach also yields the first $mathrmpolylog (1/)$ complexity sampler for general log-concave distributions.
  arXiv  Detail & Related papers  (2026-02-01T17:05:31Z)
• On the query complexity of sampling from non-log-concave distributions [2.4253233571593547]
  We study the problem of sampling from a $d$-dimensional distribution with density $p(x)propto e-f(x)$, which does not necessarily satisfy good isoperimetric conditions. We show that for a wide range of parameters, sampling is strictly easier than optimization by a super-exponential factor in the dimension $d$.
  arXiv  Detail & Related papers  (2025-02-10T06:54:16Z)
• Uniformity testing when you have the source code [16.232881331802687]
  We study quantum algorithms for verifying properties of the output probability distribution of a classical or quantum circuit. We consider the basic task of uniformity testing, which is to decide if the output distribution is uniform on $[d]$ or $epsilon$-far from uniform in total variation distance.
  arXiv  Detail & Related papers  (2024-11-07T18:48:29Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  Previous private estimators on distributions over $mathRd suffer from a curse of dimensionality. We present an algorithm whose sample complexity has improved dependence on dimension.
  arXiv  Detail & Related papers  (2024-11-01T17:59:53Z)
• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  We show that for a broad class of data structures their bounds cannot be significantly improved. This is a novel emphstatistical-computational trade-off for density estimation.
  arXiv  Detail & Related papers  (2024-10-30T15:03:33Z)
• Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space [1.2277343096128712]
  In this paper, we show that much less space suffices -- we give an algorithm that uses space $O(log4 varepsilon-1)$ in the streaming setting. We also state 9 related open problems that we hope will spark interest in this and related problems.
  arXiv  Detail & Related papers  (2024-10-29T15:24:27Z)
• Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
  conditional distributions is a central problem in machine learning.<n>We propose a new paradigm that integrates both paired and unpaired data.<n>We show that our approach can theoretically recover true conditional distributions with arbitrarily small error.
  arXiv  Detail & Related papers  (2024-10-03T16:12:59Z)
• Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
  We show that for a large class of symmetric distributions, the same error as in the Gaussian setting can be achieved efficiently. We propose a sequence of efficient algorithms that approaches this optimal error. Our algorithms are based on a generalization of the well-known filtering technique.
  arXiv  Detail & Related papers  (2023-02-21T17:52:23Z)
• Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence [3.9586758145580014]
  We design fast algorithms for repeatedly sampling from strongly Rayleigh distributions. For a graph $G=(V, E)$, we show how to approximately sample uniformly random spanning trees from $G$ in $widetildeO(lvert Vrvert)$ time per sample. For a determinantal point process on subsets of size $k$ of a ground set of $n$ elements, we show how to approximately sample in $widetildeO(komega)$ time after an initial $widetildeO(nk
  arXiv  Detail & Related papers  (2022-04-06T04:11:26Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
  arXiv  Detail & Related papers  (2022-02-15T03:49:28Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• Inductive Mutual Information Estimation: A Convex Maximum-Entropy Copula Approach [0.5330240017302619]
  We propose a novel estimator of the mutual information between two ordinal vectors $x$ and $y$. We prove that, so long as the constraint is feasible, this problem admits a unique solution, it is in the exponential family, and it can be learned by solving a convex optimization problem. We show that our approach may be used to mitigate mode collapse in GANs by maximizing the entropy of the copula of fake samples.
  arXiv  Detail & Related papers  (2021-02-25T21:21:40Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
  arXiv  Detail & Related papers  (2020-06-12T10:21:40Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.