Logistics regression with polynomial features vs neural networks for classification

Question

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).

Answer 1

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.

Answer 2

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.