In short, I'm trying to calculate the 'Upper bound 3' [Ref, p.4] of the true error rate for my partial least squares regression model (PLS-DA), separating two classes A and B of a sample set. Let me try to be specific.

In the context of linear discriminant analysis, I'm trying to estimate the true error rate of a linear discriminant prediction model $\alpha$ given its apparent error rate (or resubstitution error estimate) using the formula below from the reference. To do this, I have a sample set of known observations $\{x_{1,...,l},\omega_{1,...,l}\}$ consisting of measurements $x$, and class belonging $\omega=\{A,B\}$ of size $l=308$.

The unknown probability of a prediction error of my classifier $\alpha$ is $P(\alpha)$ and the error frequency in the training sample i.e. the apparent error rate is $v(\alpha) = \frac{1}{l}\sum_{j=1}^{l}I_{\{\alpha(x_j)\neq\omega_j\}}$, where the summated term $I$ is the event that my classifier $\alpha$, based on the data $x$ classifies $\omega$ wrong.

Then, with the probability $1-\eta$ the upper bound of $P(\alpha)$ is [Ref, p.4]:

$P(\alpha) \leq \frac{1}{1+2q}\left(v(\alpha)+q+\sqrt{q^2 +2qv(\alpha) - 2qv(\alpha)^2} \right)$,

where $q=\frac{1}{l}\ln \left( \frac{N}{\eta} \right)$.

So far, I think I know everything except for $N$; my apparent error rate is tested to be $v(\alpha)=17\%$ by training a PLS regression model and testing it on the same set of $l=308$ observations, and I choose $\eta = 0.05$. Now, what is $N$?

I have some explanations from the reference which I do not understand:

The reference writes the following definition of N [Ref, p.1]:

We have a set of decision rules which in this paper is supposed to be of finite size $N$, $\{\alpha_1,...,\alpha_N \}$,

and in a set of examples, $N$ is calculated to $N=10^6$, $10^{12}$, or $10^{24}$ with the description [Ref, p.6]:

This corresponds to the number of possible histogram discrimination rules when they are 2 classes and when the number of cells is equal to 20, 40 and 80 respectively; this also corresponds almost exactly to the number of possible classification trees with 2 classes, 35 binary variables and depth smaller than 2, 3 and 4 respectively.

To which I've noted that $2^{20}\approx 10^6$, $2^{40}\approx 10^{12}$, and $2^{80}\approx 10^{24}$, indicating some kind of combinatorics.

Can someone please help me understand what $N$ is, or point me in the direction of understanding it. I've read the reference thoroughly and looked at some of its citations, but I lack the understanding necessary. As a consequence, I do not know what further information is required from my part, to which you are welcome to ask anything!

Thank you for any help!

[Ref] Distribution-free performance bounds with the resubstitution error estimate by Olivier Gascuel and Gilles Caraux, download pdf.

  • $\begingroup$ I'll have to read the paper in detail, but I'm deeply suspicious how much meaningful information about generalization performance can be retrieved from resubstitution/autoprediction in practice. There is no bound on overfitting other than that (apparent) error cannot be below 0. Meanwhile, if you are looking for confidence intervals for more direct estimates of generalization error (cross validation/out-of-bootstrap/resampling and test set estimates), let me know and I'll point you to relevant literature. $\endgroup$ Jan 15, 2019 at 11:54
  • $\begingroup$ You share the suspicion of my reviewer, I hear! I have other tests related to cross-validation and test set estimates that are close to the resubstitution in performance, albeit lower as they are not overfitted. I feel it would be very nice to have several tests supporting each other, and with a measurement of overfitting from above I could clearly show the problems with resubstitution in a pedagogical way. $\endgroup$ Jan 15, 2019 at 12:54
  • $\begingroup$ As I am using PLS-DA, I only have 1 discriminant rule; the summation of my weighted variables vs. some threshold. Does this imply that for 2 classes I only have 1 so called 'cell' meaning N = 2^1? I'm not at all sure about this comment. $\endgroup$ Jan 15, 2019 at 13:00
  • $\begingroup$ Some progress but not an answer (it may be very helpful if you could find the Vapnik book the paper cites - I couldn't, apparently there's a 2nd edition out and that seems to be very different from the first. E.g. it doesn't have 6 chapters, so no theorems 6.x :-/ ). Still I suspect that N is closely related to VC dimensionality. And en.wikipedia.org/wiki/… gives a somewhat different bound by Vapnik (but the citation link doesn't work...). Interesting is the "small-print": that this is applicable only if no. training cases >> VC dimension $\endgroup$ Jan 15, 2019 at 13:01
  • $\begingroup$ ... in other words, if there's no or not much danger of overfitting. For PLS-DA, you'll need to take into account a) the degrees of freedom of the latent variable projection and b) that your input is not just binary but probably continuous. Again, these are not ready thoughts, but intuitively I'd say that while PLS is a regularization, the dimensionality of PLS-DA won't be that much below a linear separation in original data space. Which is probably high, since that's when PLS is used. Think of it: your PLS-DA model has p x (number of latent variables + 1 [for centering]) coefficients to ... $\endgroup$ Jan 15, 2019 at 13:09

1 Answer 1


After a brief communication with the author of the paper (Olivier Gascuel), I received the explanation below. In short: PLS-DA predicts a value between 0 and 1, which classifies the observation by comparing the value to a threshold: all values above the threshold, e.g. 0.5, are classified as of class 1, else 0. As the threshold, 0.5 could be chosen continuously with infinite precision, the value of N is infinite as well. This means that the paper I provided by O. Gascuel is not fit for my intended use. Comments regarding Vapnik-Chervonenkis dimensionality by @cbeleites are supported by Olivier.

Dear Linus, that’s an ancient paper… but basically this paper deals with the case where the number of classifiers is finite (e.g. decision trees with categorical variables). In the (usual) case where the number of classifiers is infinite (e.g. linear discrimination, as the weights are continuous and infinitely many) another approach must be used, typically based on the Vapnik-Chervonenkis (VC) dimension. But since 1992 I’m pretty sure that new approaches have been proposed, especially in the recent period with the incredible mood for machine learning. Hope this helps, regards, Olivier.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.