局部加权回归

线性回归算法里的成本函数：

$J(\Theta) = \frac 1 2 \sum_{i=1}^m(h_\Theta(X^{(i)})-y^{(i)})^2$

正规方程解出的参数解析表达式：

$\Theta = (X^TX)^{-1}X^Ty$

由于使用了过小的特征集合使得模型过于简单，在这种情形下数据中的某些非常明显的模式没有被成功地拟合出来，我们将其称之为:欠拟合(underfitting)。

由于使用了过大的特征集合使得模型过于复杂，算法拟合出的结果仅仅反映了所给的特定数据的特质，我们可以称之为过拟合。

在特征选择中存在上述两类问题。

这里讲到一类非参数学习算法，可以缓解对于选取特征的需求，就是局部加权回归算法。

这个算法可以让我们不必太担心对于特征的选择。

算法示意

$$ Fit \quad \Theta \quad To \quad Minimize \\ \sum_i w^{(i)}(y{(i)} - \Theta^TX{(i)})^2 \quad where \quad w^{(i)} = exp(- \frac {(X^{(i)} - x)^2} {2 \tau^2}) \\ Then \quad Return \quad \Theta^Tx \\ If \quad |X^{(i) - x}| \quad small, \quad then \quad w^{(i)} \approx 1 \\ If \quad |X^{(i) - x}| \quad large, \quad then \quad w^{(i)} \approx 0 $$ $\tau$称为波长函数， $\tau$较小，则权值随距离下降得快， $\tau$较大，则权值随距离下降得慢。

线性回归的概率解释

$$ Assume \quad y^{(i)} = \Theta^TX^{(i)} + \varepsilon^{(i)} \\ \varepsilon^{(i)} = error \\ \varepsilon^{(i)} \sim N(0, \sigma^2) \\ P(\varepsilon^{(i)}) = \frac 1 {\sqrt {2\pi} \sigma} exp(- \frac {( \varepsilon^{(i)} )^2} {2\sigma^2}) $$ 其中$\varepsilon^{(i)}$代表误差项，它表示了一种我们没有捕获到的特征，或者你也可以把它看成一种随机的噪声。

然后可以得到

$$ P(y^{(i)} | X^{(i)}; \Theta) \\ = \frac 1 {\sqrt {2\pi} \sigma} exp(- \frac {(y^{(i)} - \Theta^TX^{(i)})^2} {2\sigma^2}) \\ \sim N(\Theta^TX^{(i)}, \sigma^2) $$ $\varepsilon^{(i)}$s 是独立同分布的。

然后定义

$$ L(\Theta) = P(\overrightarrow y|X; \Theta) \\ = \Pi_{i=1}^m P(y^{(i)} | X^{(i)}; \Theta) \\ = \Pi_{i=1}^m \frac 1 {\sqrt {2\pi} \sigma} exp(- \frac {(y^{(i)} - \Theta^TX^{(i)})^2} {2\sigma^2}) $$ 这个就是参数$\Theta$的似然性。

算法的目标也就变为：

$$ Choose \quad \Theta \quad To \quad Maximize \quad L(\Theta) = P(\overrightarrow y|X; \Theta) $$ 再定义

$$ \ell(\Theta) = logL(\Theta) = log\Pi_{i=1}^m \frac 1 {\sqrt {2\pi} \sigma} exp(- \frac {(y^{(i)} - \Theta^TX^{(i)})^2} {2\sigma^2}) \\ = mlog\frac 1 {\sqrt {2\pi} \sigma} + \sum_{i=1}^m - \frac {(y^{(i) - \Theta^TX^{(i)}})^2} {2\sigma^2} $$ 然后最大化$\ell(\Theta)$就变成了最小化$ \frac {\sum_{i=1}^m(y^{(i) - \Theta^TX^{(i)}})^2} 2=J(\Theta)$

于是推导出了线性回归算法里的成本函数。

logistic回归

推导过程

$$ y \in \{0, 1\} \\ h_\Theta(X) \in [0, 1] \\ Choose \quad h_\Theta(X) = g(\Theta^TX) = \frac 1 {1 + e ^{-\Theta^TX}} \\ g(Z) = \frac 1 {1 + e^{-Z}} $$ 上述$g(Z)$公式就叫做sigmoid函数，也叫logistic函数。

同样使用概率解释下logistic回归函数。

$$ P(y|X;\Theta） = h_\Theta(X)^y(1-h_\Theta(X))^{1-y} \\ L(\Theta) = P(\overrightarrow y|X;\Theta）= \Pi_i P(y^{(i)}|X^{(i)};\Theta）\\ = \Pi_i h_\Theta(X^{(i)})^{y^{(i)}}(1-h_\Theta(X^{(i)}))^{1-y^{(i)}} \\ \ell(\Theta) = logL(\Theta) = \sum_{i=1}^m y^{(i)} logh(X_\Theta^{(i)}) + (1-y^{(i)})log(1-h_\Theta(X^{(i)})) $$ 采用梯度上升算法来最大化$\ell(\Theta)$

$$ \Theta := \Theta + \alpha \nabla_\Theta \ell(\Theta) \\ \frac \partial {\partial \Theta_j} = \sum_{i=1}^m(y^{(i)} - h_\Theta(X^{(i)}))X_j^{(i)} $$ 最后得到logistic回归的更新$\Theta​$的过程为

$$ \Theta_j := \Theta_j - \alpha \sum_{i=1}^m(h_\Theta(X^{(i)}))X_j^{(i)} $$

感知器算法

这个跟logistic算法很相似，更新$\Theta$的过程为

$$ \Theta_j := \Theta_j - \alpha \sum_{i=1}^m(h_\Theta(X^{(i)}))X_j^{(i)} $$