I am reading John Langford's paper on practical prediction theory (link), and I have the following doubt with definition of Binomial Tail inversion.

The paper says that binomial tail inversion is the largest true error such that the probability of having k or more errors is at least $\delta$.

But the expression used in the paper reads "largest true error such that probability of having k or less errors is at least $\delta$"

Can anyone help?


I think this is a typo.

In the Definition 2.1 and Definition 2.2, the estimation of $c_D$ is done by empirical summation of $\mathbf{1}(c(x_i) = y_i)$.

Later in the Definition 3.1 it used the following notation : $$ ... = \Pr_{...} \left( \sum_i Z_i < k \right) = ... $$ In this notation $Z_i=1$ corresponds to correct decisions or $c(x_i) = y_i$, and $Z_i=0$ corresponds to the mistakes or $c(x_i) \neq y_i$. I suppose that in this binomial representation $Z_i = 1$ (correct decision) corresponds to heads" (And similarly $Z_i = 0$ (wrong decision) corresponds totail").

That said, the right sentence seems to be "... having k or less errors is at least $\delta$"

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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