Why does Bengio, Goodfellow and Courville deep learning theory book claim $\hat{y} = x w_1 ... w_i ... w_l$ is a non-linear function of $w_i$?

Question

In chapter 8 section 8.7.1 it tries to explain batch normalization. In the second paragraph of that section it tells us to consider the simple example:

$$ \hat{y} = x w_1 ... w_i ... w_l $$

and then claims:

The output $\hat y$ is a linear function of the input x, but a nonlinear function of the weights $w_i$.

which I believe is incorrect, however, I wanted to make sure I was not wrong myself. I will argue here why I think its wrong.

Recall the definition of a linear function to be $ f(x+y) = f(x) + f(y) $. Now lets consider the function they wrote and see if it obeys that property. First it clearly obeys it with respect to x:

$$ \hat{y}(x) + \hat{y}(y) = x w_1 ... w_i ... w_l + y w_1 ... w_i ... w_l $$

then by factoring out $w_1 ... w_i ... w_l$ we get:

$$ \hat{y}(x) + \hat{y}(y) = ( x + y ) w_1 ... w_i ... w_l = \hat{y}(x + y) $$

One can do nearly an identical proof but with respect to $w_i$:

$$\hat{y}(w_i) + \hat{y}(w'_i) = x w_1 ... w_i ... w_l + x w_1 ... w'_i ... w_l $$

but instead by factoring everything first from the left and then from the right. Similarly to why $abc+ab'c = a(bc + b'c) = a(b + b')c$ is true. Do that and we get:

$$\hat{y}(w_i) + \hat{y}(w'_i) = (x w_1 ... )(w_i ... w_l + w'_i ... w_l) = (x w_1 ... )(w_i + w'_i)( ... w_l) = \hat{y}(w_i + w'_i)$$

which yields the desired result (that $\hat y$ linear wrt to $w_i$).

From the above argument I can't see why they'd say its non-linear. Maybe I have a misunderstanding what they are trying to say? Or is there a small mistake on the draft of the book? If its not to much to ask, can a potential answer try to address why is my proof is wrong?

Answer 1

It is not incorrect. It is nonlinear in $\mathbf{w}$. Can you take a matrix, premultiply the weight vector by it, and get that? What I mean is that there is no $\mathbf{A}$ such that $\mathbf{A} \mathbf{w} = x w_1 \cdots w_l$.

The key is to see that it is a function in $\mathbf{w}$.

$$f(\mathbf{w}) = x w_1 \cdots w_l$$

Pick two of these vectors, $\mathbf{w^1}$ and $\mathbf{w^2}$. Clearly

$$f(\mathbf{w^1} + \mathbf{w^2}) \neq f(\mathbf{w^1}) + f(\mathbf{w^2})$$.

I think the trouble is that you are thinking about it as a function in $x$. Your proof is correct if you were trying to demonstrate it's linear in this guy. Also, if you fix all the weight elements except one, $w_i$, and think about the function as a function in this one $w_i$, then it would be linear in that. But it is not linear in weight vectors $\mathbf{w}$.

Answer 2

As @amoeba said, it is non-linear in the combination $\mathbf \prod_{i=1}^{n} w_{i}$. Let's see an example where each $w_{i}$ is doubled. Then the new value becomes $2^{n}$ times the old value whereas it should have been just 2 times the old value for a linear function.

Answer 3

To be fair, it is easy to misunderstand it to mean "a nonlinear function of each of the weights $w_i$." In that case, your analysis would be correct.

For what it's worth, since we're working with real numbers here, you can use a simpler definition of linear function:

$$ f(\alpha x) = \alpha f(x) $$

In other words, that scaling the input scales the output by the same amount. Clearly for our function

$$ \hat{y} = x w_1 ... w_i ... w_l $$

Multiplying $x$ by some $\alpha$ will also scale $\hat{y}$ by the same amount, and similarly for each $w_i$.