2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Isn't that an affine function? Without $a_0$ it would be linear. $\endgroup$ – Martin Thoma Jul 26 '17 at 20:45
  • 1
    $\begingroup$ Degree 1 functions are sometimes called linear. It depends on the context. $\endgroup$ – Yuval Filmus Jul 26 '17 at 20:46
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think I understand how you get to (r,s) if r=x and s=root(y), but where does r - s = 0 come from? $\endgroup$ – Stephen Jul 26 '17 at 16:26
  • $\begingroup$ I thought more about it and I think I might have the derivation. Is this right? Or am I not following your lead? $$y = x^2$$ $$s^2 = r^2$$ $$s = r$$ $$r - s = 0$$ $\endgroup$ – Stephen Jul 27 '17 at 2:06
  • 1
    $\begingroup$ @Stephen What I meant is that directly working in $(x,y)$ space to classify may require the use of a non-linear classifier since the classification boundary in this space is $y-x^2=0$ (for the example in my answer). However, if you transform into the space of $(r,s)$ where the transformation used is $ r=x, s=\sqrt y $ then, in this space, we have the classification boundary as $r-s = 0$ which can be easily learnt by a linear model of classification! $\endgroup$ – LastIronStar Jul 27 '17 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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