A Probabilistic Theory of Pattern Recognition

By Luc Devroye, László Györfi, Gábor Lugosi. 1996

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Natural Language Processing

Citations in the corpus

Natural Questions: A Benchmark for Question Answering Research (2019, background): “The Bayes optimal hypothesis (see Devroye et al., 1997) for hβ , defined asargmaxf Eq,d,a[[hβ(a, f(q, d))]], is a function of the posterior distribution p(·|q, d),11 and will generally exceed the performance of a single random annotation, Eq,d,a[[ ∑ l p(l|q, d) × hβ(a, l)]].”
Analysis of a Random Forests Model (2010, background): “To understand this remark, recall that individual (random or not) trees are proved to be consistent by letting the number of cases in each terminal node become large (see [19, Chapter 20]), with a typical variance of the order k n /n .”
Toward Causal Representation Learning (2021, background): “in terms of measures of complexity of function classes [56], [257].”
Towards Causal Representation Learning (2021, background): “low expected error, and statistical learning theory provides probabilistic guarantees in terms of measures of complexity of function classes [55, 257].”
On the empirical estimation of integral probability metrics (2012, methodology): “In the following, we present another interpretation for the kernel distance by relating it to the Parzen window classifier [37, 38] (also called the kernel classification rule [14]).”
How to Explain Individual Classification Decisions (2009, methodology): “Assuming that the data could be modeled as being IID-sampled from some unknown joint distribution P ( X, Y ), in theory, we can deﬁne the Bayes classiﬁer, g ∗ ( x ) = arg min c ∈{ 1 ,...,C } which is optimal for the 0-1 loss function (see Devroye, Gy¨orﬁ, and Lugosi, 1996).”
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results (2003, neutral): “A standard integration (see, for example, Devroye et al., 1996, p208) shows that |Es(N ) − s(EN )| ≤ E|s(N ) − s(EN )| ≤ 4 2 n .”
A Model of Inductive Bias Learning (2000, background): ““Multi-task learning” ( Caruana, 1997 ) trains extra neural network outputs to match related tasks in order to improve generalization performance on a fixed reference task.”
Enhancing The Reliability of Out-of-distribution Image Detection in Neural Networks (2017, methodology): “Conventional methods such as density estimation, nearest neighbor and clustering analysis are widely used in detecting low-dimensional out-of-distribution examples (Chow, 1970; Vincent & Bengio, 2003; Ghoting et al., 2008; Devroye et al., 2013), .”
Domain Adaptation: Learning Bounds and Algorithms (2009, methodology): “This leads us to the following deﬁnition of a distance originally introduced by Devroye et al. (1996) [pp. 271-272] under the name of generalized Kolmogorov-Smirnov distance , later by Kifer et al. (2004) as the d A distance , and introduced and applied to the analysis of adaptation in…”
Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning (2009, methodology): “As a mechanism's response must be nitely encodable, the primal parametrization seems less appealing as it did in PrivateSVM-Finite.”
Optimal Rates for the Regularized Least-Squares Algorithm (2007, background): “respect to ρX ) and a notion of complexity of the regression function fρ which generalize to arbitrary RKHs the degree of smoothness of fρ , usually defined for regression in Sobolev spaces (see [11], [30], [17], [5], [9], and references therein).”
A reliable effective terascale linear learning system (2011, background): “Furthermore, standard sample complexity arguments (see, e.g., Bartlett and Mendelson, 2002; Devroye et al., 1996) allow us to bound the function value f(w) for an arbitrary w as ∣∣∣f(w)− Ex,y[ ̃̀(w; x, y)]∣∣∣ ≤ O( 1 √ n ) .”
On integral probability metrics, φ-divergences and binary classification (2009, methodology): “Recently, Reid and Williamson [40, Section 8, Appendix E] have related MMD to Fisher discriminant analysis [43, Section 4.3] in H and SVM [59].”
Consistency of Random Forests (2014, background): “This implies that the single trees are eventually not consistent, since standard conditions for tree consistency require that the number of observations in the terminal nodes tends to inﬁnity as n grows (see, e.g., Devroye et al., 1996; Gy¨orﬁ et al., 2002).”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, methodology): “Lemma 20 (Uniform deviation bound using covering number [Pollard, 1984]; also see Devroye et al. [1996], Theorem 29.”
Robustness and generalization (2010, background): “Example 3 is such a case, as it is known that its minimax excess error is of the order √ K/n (e.g., Devroye et al. 1996).”