Machine learning lecture 1 course notes  (Page 7/13)

In the original linear regression algorithm, to make a prediction at a query point $x$ (i.e., to evaluate $h\left(x\right)$ ), we would:

1. Fit $\theta$ to minimize ${\sum }_i{(y^{\left(i\right)}-{\theta }^T{x}^{\left(i\right)})}^2$ .
2. Output ${\theta }^{T}x$ .

In contrast, the locally weighted linear regression algorithm does the following:

1. Fit $\theta$ to minimize ${\sum }_i{w}^{\left(i\right)}{(y^{\left(i\right)}-{\theta }^T{x}^{\left(i\right)})}^2$ .
2. Output ${\theta }^{T}x$ .

Here, the $w^{\left(i\right)}$ 's are non-negative valued weights . Intuitively, if $w^{\left(i\right)}$ is large for a particular value of $i$ , then in picking $\theta$ , we'll try hard to make ${(y^{\left(i\right)}-{\theta }^T{x}^{\left(i\right)})}^2$ small. If $w^{\left(i\right)}$ is small, then the ${(y^{\left(i\right)}-{\theta }^T{x}^{\left(i\right)})}^2$ error term will be pretty much ignored in the fit.

A fairly standard choice for the weights is If $x$ is vector-valued, this is generalized to be $w^{\left(i\right)}=exp(-{(x^{\left(i\right)}-x)}^T(x^{\left(i\right)}-x)/\left(2{\tau }^2\right))$ , or $w^{\left(i\right)}=exp(-{(x^{\left(i\right)}-x)}^T{\Sigma }^{-1}(x^{\left(i\right)}-x)/2)$ , for an appropriate choice of $\tau$ or $\Sigma$ .

Note that the weights depend on the particular point $x$ at which we're trying to evaluate $x$ . Moreover, if $|x^{\left(i\right)}-x|$ is small, then $w^{\left(i\right)}$ is close to 1; and if $|x^{\left(i\right)}-x|$ is large, then $w^{\left(i\right)}$ is small. Hence, $\theta$ is chosen giving a much higher “weight” to the (errors on) training examples close to the query point $x$ . (Note also that while the formula for the weights takes a form that is cosmetically similar to thedensity of a Gaussian distribution, the $w^{\left(i\right)}$ 's do not directly have anything to do with Gaussians, and in particular the $w^{\left(i\right)}$ are not random variables, normally distributed or otherwise.)The parameter $\tau$ controls how quickly the weight of a training example falls off with distance of its $x^{\left(i\right)}$ from the query point $x$ ; $\tau$ is called the bandwidth parameter, and is also something that you'll get to experiment with in your homework.

Locally weighted linear regression is the first example we're seeing of a non-parametric algorithm. The (unweighted) linear regression algorithm that we saw earlier is known as a parametric learning algorithm, because it has a fixed, finite number of parameters(the ${\theta }_i$ 's), which are fit to the data. Once we've fit the ${\theta }_i$ 's and stored them away, we no longer need to keep the training data around to make future predictions.In contrast, to make predictions using locally weighted linear regression, we need to keep the entire training set around. The term “non-parametric”(roughly) refers to the fact that the amount of stuff we need to keep in order to represent the hypothesis $h$ grows linearly with the size of the training set.

Classification and logistic regression

Let's now talk about the classification problem. This is just like the regression problem, except that the values $y$ we now want to predict take on only a small number of discrete values. For now,we will focus on the binary classification problem in which $y$ can take on only two values, 0 and 1. (Most of what wesay here will also generalize to the multiple-class case.) For instance, if we are trying to build a spam classifier for email,then $x^{\left(i\right)}$ may be some features of a piece of email, and $y$ may be 1 if it is a piece of spam mail, and 0 otherwise.0 is also called the negative class , and 1 the positive class , and they are sometimes also denoted by the symbols “-” and “+.” Given $x^{\left(i\right)}$ , the corresponding $y^{\left(i\right)}$ is also called the label for the training example.