5
$\begingroup$

Are there any power calculation formulas for ML methods (for binary classification) beyond Logistic Regression? (also well beyond the laughable rule of thumb 10 instances per variable)

I've done a naive google search and can't find anything.

I'd expect there to be a different calculation for but maybe there is a kind of general analysis based simply on number of features.

Maybe linear SVMs, no kernel, have a comparable power calc formula?

I'm interested in anything, Decision Trees, k-Nearest Neighbors, Naive Bayes, etc.

As complex as Deep Neural Networks seem to be, with the multiplicity of parameters they have, maybe they can be analyzed as a network of stacked Linear Regression?

$\endgroup$
11
  • 5
    $\begingroup$ What do you mean by “power calculations”? $\endgroup$ – Tim Jun 12 '20 at 16:03
  • $\begingroup$ @Tim By power calculation I meant more specifically finding the minimal sample size $n$ for a given $\beta$, probability of type II error. $\endgroup$ – Mitch Jun 12 '20 at 16:25
  • 6
    $\begingroup$ Since there’s no “betas” and no such a thing as hypothesis tests for ML models, what do you mean? $\endgroup$ – Tim Jun 12 '20 at 16:27
  • 1
    $\begingroup$ It would help if you said what hypothesis testing you’re doing with logistic regression where you’re calculating the power of that hypothesis test. Then we can talk about what would be similar for another machine learning method. $\endgroup$ – Dave Jun 12 '20 at 17:35
  • 2
    $\begingroup$ @Tim new question posted and this one rolled back to original. $\endgroup$ – Mitch Jun 12 '20 at 19:08
5
$\begingroup$

The type of power analysis you seem to be referring to is: make some assumptions about the distribution of variables, the effect size, etc., and then ask how many samples you'd need to have a (say) 80% probability of detecting an effect of that magnitude.

There are in fact many results of a similar flavor in ML theory. For instance, here's one for SVMs (rephrased from Corollary 15.7 of Shalev-Shwartz and Ben-David, Understanding Machine Learning): $\DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\E}{\mathbb{E}} \DeclareMathOperator{\sign}{sign} \newcommand{\x}{\mathbf x} \newcommand{\X}{\mathcal X} \newcommand{\D}{\mathcal D} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\w}{\mathbf w} \newcommand{\u}{\mathbf u} $

Let $\D$ be a distribution over $\X \times \{-1, 1\}$, where $\X = \{ \x : \norm\x \le \rho \}$. Consider running Soft-SVM (with no bias term) on a training set $S \sim \D^m$ and let $A(S)$ be the solution of Soft-SVM: $$A(s) = \argmin_{\mathbf w} \lambda \norm\w^2 + L_S^\mathit{hinge}(\w)$$ where $$L_S^\mathrm{hinge}(\w) = \frac1m \sum_{i=1}^m \max\{0, 1 - y \, \langle \w, \x_i \rangle \} .$$ Then, for every $B > 0$, if we set $\lambda = \sqrt{2 \rho^2 / (B^2 m)}$, then $$ \E_{S \sim \D^m}[ L_\D^{0-1}(A(S)) ] \le \E_{S \sim \D^m}[ L_\D^\mathit{hinge}(A(S)) ] \le \min_{\w : \norm\w \le B} L_\D^\mathrm{hinge}(\w) + \sqrt{\frac{8 \rho^2 B^2}{m}} ,$$ where $L_\D^\mathit{hinge}(\w) = \E_{S \sim \D} L_S^\mathit{hinge}(\w)$, and $L_\D^{0-1}(\w) = \E_{(\x, y) \sim \D} \left[ \begin{cases}0 & \sign(\langle \w, \x \rangle) = y \\ 1 & \text{otherwise} \end{cases} \right]$ is just the accuracy of $\w$.

That is,

  • The accuracy of our SVM is no worse than its hinge loss performance: this is just because for any predictor, $L^{0-1} \le L^\mathit{hinge}$. If the prediction is the wrong sign so that 0-1 loss is 1, then the hinge loss is at least 1; if the prediction is the right sign so that 0-1 loss is 0, the hinge loss is between 0 and 1.
  • The expected hinge loss performance of our SVM is not too much worse than the hinge loss for the best-possible SVM of norm at most $B$: the gap is at most $2 \rho B \sqrt{2 / m}$.

(There are similar results for high-probability bounds on the accuracy, and requiring the offset to be 0 is just a convenience; adding 1 to the kernel and centering the labels generally accounts for it, but there are presumably bounds out there explicitly incorporating the offset as well.)

Now, because it's a generic bound, its numerical value is probably quite loose on any particular problem. But even if we accept that it will be quite conservative: how do we know the best possible hinge loss for a given $B$, and then trade that off with the other term to find the best value of the overall bound?

The same kind of issues hold in power analysis for linear regression – what do we think the effect size might be? But it's often easier to reason about effect size than about the best hinge loss at a given norm. It might be easier to make a guess about accuracy, but unfortunately, I'm pretty sure no comparable bounds are available with the best-possible accuracy/0-1 loss on the right-hand side. (Finding the best linear predictor w.r.t. 0-1 loss is NP-hard, while SVMs are in P, so if you find such a bound, please let me know!)

In practice, then, the method in machine learning is almost always "try it and see how well you do on a validation set." People develop a rough intuition – you can't train a 44,654,504-parameter ResNet-101 on 60,000-image MNIST, but you can on 1,200,000-image ImageNet. But we don't really theoretically understand why this is true; it's a very active current area of research.

$\endgroup$
4
  • $\begingroup$ Excellent (and impressed by the re-LaTeXing of the original). Have you heard of similar analysis for other ML methods? Naive Bayes? ID3/CART? kNN? $\endgroup$ – Mitch Jun 14 '20 at 19:44
  • $\begingroup$ Also, that last paragraph, would be able to put that on the related question explicitly about sample size stats.stackexchange.com/questions/471854/… ? $\endgroup$ – Mitch Jun 14 '20 at 19:46
  • 1
    $\begingroup$ @Mitch, there are many similar analyses out there, e.g. for Naive Bayes, decision trees, or k-NN in Chapter 19 of the Shai-and-Shai book above. VC dimension or Rademacher theory give more general results. $\endgroup$ – Danica Jun 17 '20 at 4:56
  • $\begingroup$ That's excellent. Could you add that to your answer here (or at the other question)? $\endgroup$ – Mitch Jun 17 '20 at 13:55
4
$\begingroup$

Power analysis refers to calculating power of a hypothesis test

The power of a binary hypothesis test is the probability that the test rejects the null hypothesis ( $H_{0}$) when a specific alternative hypothesis ( $H_{1}$ ) is true

In machine learning you make no hypothesis, are not interested in testing them, and don't have any hypothesis tests available. Since there's no hypothesis tests, there is no power analysis. You can make power analysis for the hypothesis tests related to logistic regression, because logistic regression is a statistical model that is also used in machine learning as a classifier. That is not the case for other machine learning models. Moreover, even if you were using logistic regression for making predictions, rather then inference, you would not do any power analysis. Finally, power analysis for logistic regression would not tell you how accurate the predictions would be.

This is also not really a case in machine learning. In machine learning we do not care about "minimal sample size", as machine learning models are are usually used with large datasets. For small dataset, you would usually use simple algorithms like logistic regression, because with more complicated ones you risk overfitting.

As about being "confident in the classification your ML model creates", this is judged by using things like cross validation. What machine learning models do, is they learn to recognize patterns in the data and make predictions given the familiar patterns. Whatever data you give them, they will always find some patterns and make some predictions. If the data is garbage, they will give you garbage predictions.

You may also want to read the The Two Cultures: statistics vs. machine learning? thread to learning about differences between statistics and machine learning.

$\endgroup$
6
  • $\begingroup$ To be as inarticulate as possible, how do you decide how big an $n$ would be good? Logistic regression uses power analysis - without immediately invoking hypotheses, what kind of quantitative and justifiable methods are there for, say, SVMs? $\endgroup$ – Mitch Jun 12 '20 at 18:00
  • $\begingroup$ For clarity, or rather to avoid the two cultures thing, I've edited my question to limit it to SVMs. I don't think that changes anything in your answer though. I'm just asking if there is a more precise way to determine ahead of time how many instances should be in a sample to get a good SVM model, just like there is a method for logistic regression. $\endgroup$ – Mitch Jun 12 '20 at 18:16
  • $\begingroup$ @Mitch this is incorrect. Power analysis for logistic regression is not used to judge how big sample size is needed to make accurate predictions, but to judge the power of hypothesis tests used with it. $\endgroup$ – Tim Jun 12 '20 at 18:19
  • $\begingroup$ OK. I've removed mention of power analysis. My question is about how to choose n, when do you have a good idea that you have enough (something more than a rule of thumb or 'experience has shown that...'). $\endgroup$ – Mitch Jun 12 '20 at 18:22
  • $\begingroup$ @Mitch your question was about power analysis and I answered this question. $\endgroup$ – Tim Jun 12 '20 at 18:28

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