What exactly is a linear function, and what is a nonlinear function?

Question

I am learning a bit about machine learning, and I frequently see things labeled "linear function" or "nonlinear function."

For example when discussing a neural network created by combining individual logistic regression nodes, a book I read noted that logistic regression is a linear function, and that the entire network would be no more powerful than a linear model except that a nonlinear function (such as relu or tanh) is applied to each node. I don't really appreciate this, because I don't have a firm grasp on the definition of linear function.

To use a simpler (to me) example, I was confused when I learned that both SVM and linear regression are linear models. It is easy for me to see how linear regression is a linear model, because its calculations are similar to the definition of a line, y = mx + b, that I learned in middle school. SVM seems more exotic to me.

So how can we know if something is a linear function/model versus a nonlinear one? Does it have to do with how the inputs are gathered, or the nature of the calculations afterward?

Answer 1

A linear function is a function of the form $$ \ell(x_1,\ldots,x_d) = \sum_{i=1}^d a_i x_i + a_0, $$ where sometimes the constant term isn't allowed.

A linear classifier is a classifier which is of the form "$\ell(x_1,\ldots,x_d) \geq 0$", where $\ell$ is linear.

Using the "kernel trick", you can masquerade non-linear classifiers as linear classifiers; SVM with a non-linear kernel is linear in that sense. In brief, we fix a mapping $\Phi\colon \mathbb R^d \to \mathbb R^D$ (where $D$ is possibly infinite), and then use a classifier of the form "$\ell(\Phi(\vec{x})) \geq 0$". The kernel trick is a way to evaluate the classifier (and train the model) without actually computing $\Phi$.

Answer 2

how can we know if something is a linear function/model versus a nonlinear one?

A (classification)model is considered to be linear if it uses a linear combination of the input variables(that define a data point) to determine the class it belongs to.

For instance, in the SVM technique (without kernels), given the training set of data points, the algorithm comes up with a separating hyperplane i.e., a generalisation of the line in 2D and the plane in 3D (each of which can be represented by linear equation, of the form, $\overline \alpha^{T}(\overline x-\overline c)=0$ where $\overline c$ is some point that lies on the hyperplane and $\overline \alpha$ is the normal vector to the hyperplane, usually taken to be of unit magnitude).

Does it have to do with how the inputs are gathered, or the nature of the calculations afterward?

The choice of inputs gathered can definitely simplify the model in question. Another way to simplify the model is to transform the inputs from one space to another. For example, if the set of data points are labeled by which side they lie on with respect to the parabola $y= x^2$, then instead of working with input points of the form $(x,y)$ directly, we can transform the data to $(r,s) = (x,\sqrt y)$, then the classifer in the transformed space has the neat form $r-s = 0$ which is a linear classifier and thus easier to learn. Moreover, the inputs being transformed into a space where they satisfy linear relationships among themselves are easier to interpret usually.