欠拟合与过拟合
假设随机变量x∈R，需要预测随机变量y。下面最左边这副图中，显示了函数y=θ0+θ1x对数据集的拟合。通过观察，我们发现数据集并不像是一条直线，因此函数对数据集并没有很好得拟合。
另外，我们给刚才的函数加上一个额外的特征x2，此时y=θ0+θ1x+θ2x2，我们获得了一条对数据集拟合更好的曲线。那么，我们是否就可以就认为加入越多的特征，函数拟合得就越好？上面最右边的图显示了用含有五阶多项式去拟合数据集的结果。我们看到，尽管曲线完美得经过了数据集中的每一个点，但是我们不能因此而断定这就是一个好的预测函数。我们将最左边的图称为欠拟合(underfitting)，表示模型并没有很好的捕捉到数据的结构。右边的图，我们将它称为过拟合(overfitting)。
局部加权线性回归(Locally weighted linear regression)
在我们之前的线性回归算法中，为了做出预测，我们需要：
1. 调整 θ使得∑i(y(i)-θTx(i))2最小化。
2. 输出θTx。
而在局部加权线性回归算法中，我们采用的做法如下：
1. 调整θ使得∑iω(i)(y(i)-θTx(i))2最小化。
2. 输出θTx。
在这里，ω(i)是一个非负的权值。直觉上，如果ω(i)相对于某个i非常大，那么我们才选取θ的时候，应该尽量让(y(i)-θTx(i))小一点；如果ω(i)很小，那么(y(i)-θTx(i))将会被忽略。
在选取权值时，一个相对比较标准的做法是：
我们注意到，权值取决于我们需要估计的x周围特定的点。若|x(i) - x|很小，那么ω(i)接近于1；若|x(i) - x|很大，ω(i)将会很小。因此，在调整θ的过程中，对于距离查询点(query point)越近的训练样本，将会赋予更高的权重。其中，参数τ控制整个函数的形状，即在训练样本远离查询点的过程中，权重下降的速度。我们将τ称为带宽参数(bandwidth parameter)。
局部加权线性回归是我们看到的第一个非参数算法(non-parametric)。而我们之前看到的线性回归被称为参数学习算法，因为它有若干个固定的参数用来拟合数据。一旦调整好参数并将它们保存，我们再也不需要为将来的预测而保留训练数据。相反，局部加权线性回归在做预测时，需要保留周围所有的训练集。
逻辑回归(Logistic regression)
现在让我们来讨论分类问题。它像是一个回归问题，但是我们需要预测的y值是仅仅是一系列离散的值。目前，我们将关注于二元分类问题，即y只能取两个值，0或者1。比如说，我们想要建立一个垃圾邮件分类器，此时x(i)可能代表一些邮件的特征，当y=1时，邮件属于垃圾邮件；否则y=0。0也被称为负类(negative class)，1被称为正类(positive class)。给定一个x(i)，相关的y(i)也被称为该训练样本的标签(label)。
我们当然也可以忽略y是一个离散的值这一事实，而采用之前的线性回归来做预测。然而，在当前问题上使用该算法表现相当差，并且线性回归无法使得h��θ(x)范围在{0, 1}。
为了修正上述不足，我们将改变h��θ(x)的形式：
其中，
被称为逻辑函数(logistic function)或者sigmoid函数。逻辑函数的图形如下图所示：
我们观察到当z->∞，g(z)将趋向于0。当z->-∞时，g(z)趋向于0。就像之前的做法一样，我们保留x0=1，即
目前，我们将采用上面给出的sigmoid函数。其他函数若能平滑得从0增长到1，同样可以被使用。但是，当我们在后面谈到广义线性模型时，我们将会看到使用sigmoid函数是一种相当自然的选择。在继续开始之前，我们先介绍一个相当有用的特性，当对sigmoid函数进行时：
那么，给定一个逻辑回归模型，如何来调整参数θ？首先我们假设：
上述式子可以形成一种更加紧凑的形式：
假设生成m个训练样本相互独立，我们可以写出关于参数θ的似然函数：
跟之前一样，将它转换为log似然函数：
接下来我们如何最大化似然函数呢？跟之前的线性回归推导过程一样，我们可以使用梯度下降。即：
我们首先使用一个训练样本(x, y)，通过对似然函数求导，推导出随机梯度下降法则：
上式中，我们使用了g'(z)=g(z)(1-g(z))。最终得出随机梯度下降法则：
如果比较之前的LMS更新法则，我们发现它们看起来基本一致。但是它们并不属于相同的算法，因为hθ(x(i))现在被定义为一个非线性函数。尽管如此，我们还是惊讶于不同的学习算法竟然会得出相同的更新法则。这是巧合，还是背后隐藏着更深层次的原因？我们将在后面介绍广义线性模型中给出答案。
