0
$\begingroup$

I am taking Andrew Ng's Coursera class on machine learning. He mentions that training a logistic regression model with polynomial features would be very expensive for certain tasks compared to training a neural network. Why is that though? I mean, when we talk about neural networks we're usually looking at a model with a very large number of parameters so why would logistic regression be more computationally expensive?

PS: Here's some context (at the beginning of an exercise on neural networks):

In the previous part of this exercise, you implemented multi-class logistic regression to recognize handwritten digits. However, logistic regression cannot form more complex hypotheses as it is only a linear classifier (You could add more features, such as polynomial features, to logistic regression, but that can be very expensive to train).

$\endgroup$

2 Answers 2

2
$\begingroup$

I expect what he's referring to is the combinatorial explosion in the number of terms (features) as the degree of the polynomial increases.

Let's say you have $N$ measurements/variables you're using to predict some other variable. A $k$th degree polynomial of those $N$ variables has $ N+k \choose k$ terms (see here). This increases very quickly with $k$.

Example:

Say we have N = 100 variables and we choose a third degree polynomial, we'll have $ 103\choose3$ = 176,851 features. For a five-degree polyomial it goes to: $105 \choose 5$ = ~96 million features. You'll then need to learn as many parameters as you have features.

Compare to a NN:

Compare this to using a fully connected NN say we choose K fully connected hidden layers with $M$ units each. That gives: $ (NM) + (K-1)(MM) + M$ parameters. This is linear in $K$ (though the $MM$ term attached to it might be big).

For N = 100 variables again, two hidden layers, and 350 features nodes per layer we get 157,580 parameters - less than we'd need for logistic regression with third degree polynomial features.

Representational power

(Added this section after seanv507's great comment) * See caveat below

The argument above was just a numbers game - how big of a NN can you get while still having the same parameter count as logistic regression with polynomail features. But you're getting at something when you say in your question:

I mean, when we talk about neural networks we're usually looking at a model with a very large number of parameters so why would logistic regression be more computationally expensive?

Well said.

Efficiency

Neural nets are universal function approximators, and we know that polynomials can approximate functions too. Which is better? What should one use? I'd bet that, for a given parameter "budget", a NN could better approximate "more" functions than a polynomial with the same number of parameters. It wouldn't surprise me if there was theory to back it up, but I don't know it off hand. seanv507's statement

One possibility is to assume that the nonlinear activation function is quadratic...and identify what range of polynomials the NN could represent.

is an interesting idea. Empirically, NN's have done better for many hard tasks than polynomial representations, and that's pretty strong evidence.

*Caveat

As seanv507 says - this is the hard part. The above statements won't always be true - I'd argue they're probably mostly true. If a low-degree polynomial basis nicely and reliably separates your classes, then it's probably worth using / trying polynomial features.

$\endgroup$
3
  • 1
    $\begingroup$ +1, but you are missing the ( hard) part relating the number of parameters in each to the representational power. Perhaps One possibility is to assume that the nonlinear activation function is quadratic...and identify what range of polynomials the NN could represent. $\endgroup$
    – seanv507
    Aug 24, 2019 at 16:01
  • $\begingroup$ thank you for your answer. 1- I have a clarifying question about the formula (NM)+(K−1)(MM)+M. Why the +M in the end? And shouldn't it be (K-2) instead of (K-1) since we are accounting for the weights from the input layer to the 1st hidden layer by doing (NM)? 2- As @seanv507 mentioned, could you perhaps explain how to relate the number of parameters to the representational power? $\endgroup$ Aug 25, 2019 at 14:12
  • $\begingroup$ I'll clarify what I mean. When K=2, I mean there are two hidden layers. I.e. inputs (N) > layer 1 (M) > layer 2 M > output (1), where the parens indicate the number of boxes per layer. The "arrows" are where weights are, and the number of weights (for a fully connected network) are the number of inputs times the number of outputs. So for this example we have: (NM + MM + M) which is consistent with what's above. If it's still not clear, say so and I'll try to find a picture to link to. $\endgroup$
    – bogovicj
    Aug 25, 2019 at 23:43
-1
$\begingroup$

To my understanding, the meaning of Andrew Ng's words is: since logistic regressions are linear classifiers, the only thing you can do to improve their performance is to increase the number of variables (i.e. adding more fetaures). Which means that, in order to get the same results that you would get with a Neural Network, you'd need much more input data.

I 100% agree with you that the average Neural Network has way more trainable parameters than a logistic regression, but to reach the same performance of a Neural Network, a logistic regression would require much more of them.

$\endgroup$
1
  • $\begingroup$ Polynomial features are combinations and/or transformations of the existing variables. For example, suppose you assume a given variable x is quadratically associated with your y, then you would add it into the equation as: y = intercept + beta1 * x + beta2 * x^2. In this way, you'd trick the model to behave in a non-linear (quadratic) way. That is an example of how to "improve" a linear model using polynomial features. $\endgroup$
    – Leevo
    Aug 23, 2019 at 15:02

Your Answer

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

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