Novelty Detection: Mixture Identification and Statistical Guarantees
Suppose we have labeled examples of an ordinary class and an unlabeled sample that also contains novel observations. The novel distribution is unknown, so its likelihood ratio cannot be estimated directly from labeled examples. (Blanchard, Lee, and Scott 2010) shows that comparing the ordinary distribution with the mixture can nevertheless recover the same optimal rejection ordering.
1. The population result
Let \(P_X=(1-\pi)P_0+\pi P_1\), with \(\pi>0\). A classifier \(f=1\) declares novelty. Write
Acceptance in the mixture is acceptance in either latent class, weighted by that class’s proportion. Hence
Proposition 1. Suppose the minimum false-negative risk over \(R_0(f)\le\alpha\) is attained by a classifier \(f^*\) with \(R_0(f^*)=\alpha\). Minimizing \(R_X\) under the same constraint attains the same optimum, with the constraint binding when \(0<\pi<1\).
Indeed, for any feasible \(f\),
At \(\pi=1\), the two objectives coincide directly; binding of the false-positive constraint need not follow. Randomization can help attain an exact false-positive level in a discrete model.
2. A likelihood-ratio interpretation
When densities exist,
The mixture likelihood ratio is a positive affine transformation of the novel-to-nominal ratio. It therefore preserves its ordering. A Neyman–Pearson comparison with the unlabeled mixture can select the same rejection sets as a comparison with labeled novel observations.
Low nominal density alone does not give this ordering. It is appropriate for a uniform alternative in the corresponding setting, but a novel class may put substantial mass where ordinary observations are also common. The finite example below separates these rules.
For a finite support, this ranking can be derived as a budget-allocation calculation. Let \(r_j\in[0,1]\) be the probability of rejecting at point \(j\), and let \(p_{0j}>0\), \(p_{1j}\) be the two class probabilities. Maximizing novel-class power subject to false-positive level \(\alpha\) means
Moving an amount \(\varepsilon\) of false-positive budget from point \(a\) to point \(b\) changes power by \(\varepsilon(p_{1b}/p_{0b}-p_{1a}/p_{0a})\). An optimum therefore fills points in decreasing likelihood-ratio order, randomizing at a boundary point if needed. Replacing \(p_{1j}\) by \(p_{Xj}\) adds the same constant \(1-\pi\) to every ratio and multiplies its remaining part by \(\pi>0\), preserving that order.
For example, take nominal probabilities \((0.6,0.3,0.1)\) and novel probabilities \((0.8,0.1,0.1)\). The likelihood ratios are \((4/3,1/3,1)\). At false-positive level \(0.1\), randomizing with probability \(1/6\) at the first point gives power \(0.8/6=2/15\). Rejecting the least common nominal point gives power only \(0.1\). Novelty can be concentrated where nominal observations are common.
With novelty fraction \(\pi=0.2\), the mixture probabilities are \((0.64,0.26,0.10)\) and its likelihood ratios are \((16/15,13/15,1)\). They recover exactly the useful ordering without labeled novelties or knowledge of \(\pi\). This is the statistical gain from the mixture reduction: estimating a relative ranking can solve the constrained classification problem even when decomposition of the mixture into its latent classes remains unidentified.
3. From population to sample
Suppose uniform deviations of the empirical risks are bounded by \(\epsilon_m\) on the nominal sample and \(\epsilon_n\) on the mixture sample. Minimize empirical mixture acceptance subject to an empirical false-positive constraint with slack \(\epsilon_m\). On the simultaneous deviation event, \(f^*\) is feasible and
Solving the mixture-risk identity for novel-class risk transfers these two empirical-error bounds:
For a finite-VC class, these errors have the usual square-root complexity rates. The post-double-selection probability bounds give related examples of controlling empirical errors uniformly over a class. The factor \(1/\pi\) has a clear meaning: when novelties are rare, a small change in mixture risk can hide a much larger change in novel-class risk.
4. The empirical risk bound, step by step
Let \(\widehat R_0\) use \(m\) nominal observations and \(\widehat R_X\) use \(n\) mixture observations. On the event
choose \(\widehat f\) to minimize \(\widehat R_X\) subject to \(\widehat R_0\leq\alpha+\epsilon_m\). Since \(R_0(f^*)=\alpha\), the population comparator is empirically feasible. Therefore
The constraint also gives \(R_0(\widehat f)\leq\alpha+2\epsilon_m\). Rearranging the population mixture identity,
proves the stated false-negative bound. An approximate empirical minimizer adds its optimization gap divided by \(\pi\). If exact false-positive control is preferred, tightening the empirical constraint to \(\alpha-\epsilon_m\) ensures \(R_0(\widehat f)\leq\alpha\), but the comparator must then be feasible at a lower population level. The difference between the two population optima requires a continuity or approximation argument; it cannot simply be omitted.
For a finite class of size \(K\), Hoeffding and a union bound give, for example,
These choices give simultaneous probability at least \(1-\delta\). A VC argument replaces the finite-class count by a complexity bound. Uniformity over the class is essential, since the data select the classifier as well as estimate its risk.
5. What fraction of the mixture is identifiable?
Recovering the rejection ordering requires less information than recovering the novelty fraction. To see what can be identified about the fraction, define
Proposition 2. The largest nominal component removable from \(P_X\) has weight \(\kappa^*\). If \(P_X\ne P_0\), its residual distribution is uniquely given by
It contains no further positive mixture component of \(P_0\). The original \(\pi\) equals \(\pi^*\) if the original \(P_1\) satisfies this irreducibility condition.
A proposed decomposition with nominal weight \(\kappa\) requires \(P_X(A)\geq\kappa P_0(A)\) for every measurable set. Thus \(\kappa\leq\kappa^*\). Conversely, this inequality at \(\kappa^*\) makes the residual a nonnegative measure of mass \(1-\kappa^*\), which can be normalized. If the normalized residual still contained nominal mass, removing it would contradict maximality.
An example shows why the restriction is needed. Suppose \(P_1=\eta P_0+(1-\eta)Q\), with \(0<\eta<1\). Then
Both decompositions give the same observed mixture: one has fraction \(\pi\) and a novel class containing nominal mass; the other has fraction \(\pi(1-\eta)\) and novel distribution \(Q\). Irreducibility excludes the hidden nominal component and makes the fraction identifiable.
6. Classifiers give honest lower bounds on novelty mass
For an acceptance set \(A=\{f=0\}\) with \(P_0(A)>0\),
Hence \(1-R_X(f)/(1-R_0(f))\leq\pi^*\leq\pi\). Optimizing over all measurable acceptance sets recovers \(\pi^*\); a restricted classifier class may give a weaker lower bound.
On the earlier uniform-deviation event, a feasible confidence lower bound is
Use an upper bound for the numerator and a lower bound for the positive denominator. Each empirical ratio then bounds its population ratio from above, so the infimum is at least \(\kappa^*\) and \(\underline\pi\leq\pi^*\) follows. If the eligible class is empty, the available lower bound is zero.
7. Why no unrestricted estimation rate follows
An essential infimum can be determined by a region having arbitrarily little probability. Changing the density ratio on that region can alter \(\kappa^*\) substantially, while a fixed finite sample is unlikely to visit it. For example, with \(P_0\) uniform on \([0,1]\), remove all mixture mass from an interval of length \(\varepsilon\) and redistribute it uniformly over the complement. The resulting \(P_X\) is within total variation \(\varepsilon\) of \(P_0\), yet \(\kappa^*=0\) because the removed interval has positive nominal mass and zero mixture mass. At \(P_X=P_0\), by contrast, \(\kappa^*=1\).
For any fixed sample size, the missing interval can be too small to distinguish these distributions reliably. Yet their identifiable novelty fractions differ drastically. This explains the obstruction to unrestricted uniform estimation and distribution-free upper bounds. Pointwise consistency under growing-class approximation conditions is compatible with that obstruction; useful upper bounds require restrictions on the regions that can determine the infimum.
A finite-sample form of the nonidentification obstruction
Let \(P_0\) be uniform on \([0,1]\) and let \(Q_\varepsilon\) be uniform on \([\varepsilon,1]\). Their total variation distance is \(\varepsilon\), yet the identifiable novelty fraction is zero for mixture law \(P_0\) and one for mixture law \(Q_\varepsilon\). Couple one draw from the two laws to be equal with probability \(1-\varepsilon\); independent copies give a coupling of \(n\) observations that differs with probability at most \(n\varepsilon\). The nominal labeled samples can be coupled identically, since their law is the same in the two experiments.
For any test \(\varphi\) of the two mixture laws with values in \([0,1]\), this gives
If an estimator recovered the novelty fraction to error strictly less than \(1/2\) with uniformly high probability, thresholding it at \(1/2\) would give a test with both errors small. Choosing \(\varepsilon=o(1/n)\) contradicts the displayed inequality. This proves failure of unrestricted uniform consistency, while leaving pointwise consistency for a fixed distribution entirely possible. It also explains why a uniformly valid upper confidence bound must be nearly vacuous at the nominal law when such alternatives are allowed.