CS229 笔记 03

Nov 16 2017

局部加权线性回归

  • Non-Parametric Learning Algorithm（非参数学习方法） Number of parameters grows with the size of sample.（参数的数目随着样本的数目增加而增加。）
  • Locally Weighted Regression（局部加权线性回归） 损失函数的定义为： $ J_\Theta=\sum_iw^{(i)}(y^{(i)}-\Theta^{\rm T}x^{(i)})^2 $ 。 其中 $ w^{(i)}={\rm {exp}}[-\frac{1}{2}(x^{(i)}-x)^2] $ . 即对于一个待预测的 $x$ ，训练集中离 $x$ 越远的样本，其对于模型的影响就越小。这也就意味着在每作出一个预测之前，都要重新训练一遍模型。

线性模型的概率解释

  • Probabilistic Interpretation（概率解释）

    假设真实房价 $y^{(i)}=\Theta^{\rm T}x^{(i)}+\varepsilon^{(i)}$ ，其中 $\varepsilon^{(i)}$ 为误差。

    因为误差是由很多其它未知因素引起的，在未知因素比较多，且假设这些未知因素是相互独立的时候，根据中心极限定理，可以认为 $\varepsilon^{(i)}$ 服从正态分布。

    即 $\varepsilon^{(i)} \sim {\scr N}(0,\sigma^2)$ ， ${\rm P}(\varepsilon^{(i)})=\frac{1}{\sqrt2 \pi \sigma}\exp\left[-\frac{(\varepsilon^{(i)})^2}{2\sigma^2}\right]$ 。

    从而对于给定的 $\Theta$ 和 $x^{(i)}$ ，$y^{(i)} \sim {\scr N}(\Theta^{\rm T}x^{(i)}, \sigma^2)$ ，即 $P(y^{(i)}|x^{(i)};\Theta)=\frac{1}{\sqrt2 \pi \sigma}\exp\left[-\frac{(y^{(i)}-\Theta^{\rm T}x^{(i)})^2}{2\sigma^2}\right]$ 。

    对于整个样本集 $X$ ，模型所做出的估计与真实值 $Y$ 的相似程度（也称作「似然性」）可以看作是模型预测出「正确」 的 $Y$ 的概率，即似然性可表示为 $L(\Theta)=P(Y|X;\Theta)$ 。

    对于每个样本 $x^{(i)}$ 及其目标值 $y^{(i)}$ ，若假设每个目标值都是独立同分布的（IID），所可则直接把 $P(y^{(i)}|x^{(i)};\Theta) $ 连乘起来，即 $L(\Theta)=P(Y|X;\Theta)=\prod_iP(y^{(i)}|x^{(i)};\Theta)$ 。

    而训练模型所需的工作就是最大化预测出「正确」 的 $Y$ 的概率，即最大似然估计（Maximize Likelihood）。

    为了方便，令 $l(\Theta)=\log L(\Theta)$ 。

    $$ \begin{eqnarray*} l(\Theta)&=&\log{L(\Theta)} \\[1em] &=&\log{\prod_{i}^{m}{P(y^{(i)}|x^{(i)};\Theta)}} \\[1em] &=&\log{\prod_{i}^{m}{\frac{1}{\sqrt2 \pi \sigma}\exp{\left[-\frac{(y^{(i)}-\Theta^{\rm T}x^{(i)})^2}{2\sigma^2}\right]}}} \\[1em] &=&\sum_{i}^{m}{\log{\frac{1}{\sqrt2 \pi \sigma}}-\frac{(y^{(i)}-\Theta^{\rm T}x^{(i)})^2}{2\sigma^2}} \\[1em] &=&m\log{\frac{1}{\sqrt2 \pi \sigma}}-\frac{1}{\sigma^2}\sum_{i}^{m}{\frac{(y^{(i)}-\Theta^{\rm T}x^{(i)})^2}{2}} \\[1em] \end{eqnarray*} $$

    要想最大化 $l(\Theta)$ ，就要最小化 $\sum_{i}^{m}{\frac{(y^{(i)}-\Theta^{\rm T}x^{(i)})^2}{2}}$ 。

    而 $\sum_{i}^{m}{\frac{(y^{(i)}-\Theta^{\rm T}x^{(i)})^2}{2}}$ 就是之前提到过的 $J(\Theta)$ 。

    这就从概率的角度解释了为什么误差要用最小二乘（Minimize Square），而不是最小化 $y^{(i)}-\Theta^{\rm T}x^{(i)}$ 的绝对值或者三次方、四次方等等。

逻辑回归

  • Logistic Regression（逻辑回归）

    虽然叫做「回归」，实际上是用来解决分类问题。

  • Logistic Function / Sigmoid Function

    $$ g(z)=\frac{1}{1+e^{-z}} $$

  • 训练过程推导

    在 Logistic Regression 中，估计函数变成了 $h_\Theta(x^{(i)})=g(\Theta^{\rm T}x)=\frac{1}{1+e^{-\Theta^{\rm T}x}}$ 。

    由于 $g(z)$ 的取值范围是 $(0,1)$ ，所以函数值可以直接看作是概率，即：

    $$ \begin{eqnarray*} P(y^{(i)}=1|x^{(i)};\Theta)&=&h_\Theta(x^{(i)}) \\[1em] P(y^{(i)}=0|x^{(i)};\Theta)&=&1-h_\Theta(x^{(i)}) \\[1em] P(y^{(i)}|x^{(i)};\Theta)&=&\left[h_\Theta(x^{(i)})\right]^{y^{(i)}}\left[1-h_\Theta(x^{(i)})\right]^{1-y^{(i)}} \\[1em] \end{eqnarray*} $$

    根据之前的讨论，令 $L(\Theta)=P(Y|X;\Theta)=\prod_i^m{P(y^{(i)}|x^{(i)};\Theta)}$ ， $l(\Theta)=\log{L(\Theta)}$ 。

    展开可得：

    $$ \begin{eqnarray*} l(\Theta)&=&\log{L(\Theta)} \\[1em] &=&\log{\prod_i^m{P(y^{(i)}|x^{(i)};\Theta)}} \\[1em] &=&\log{\prod_i^m{\left[h_\Theta(x^{(i)})\right]^{y^{(i)}}\left[1-h_\Theta(x^{(i)})\right]^{1-y^{(i)}}}} \\[1em] &=&\sum_i^m\log{\left[h_\Theta(x^{(i)})\right]^{y^{(i)}}\left[1-h_\Theta(x^{(i)})\right]^{1-y^{(i)}}} \\[1em] &=&\sum_i^m{y^{(i)}}\log{\left[h_\Theta(x^{(i)})\right]}+({1-y^{(i)}})\log{\left[1-h_\Theta(x^{(i)})\right]} \\[1em] \end{eqnarray*} $$

    $h_\Theta(x^{(i)})$ 对 $\Theta$ 求偏导：

    $$ \begin{eqnarray*} \frac{\partial}{\partial \theta_j}{h_\Theta(x^{(i)})}&=&\frac{\partial}{\partial \theta_j}{\frac{1}{1+e^{-\Theta^{\rm T}x^{(i)}}}} \\[1em] &=&\frac{-1}{\left(1+e^{-\Theta^{\rm T}x^{(i)}}\right)^2}\frac{\partial}{\partial \theta_j}{e^{-\Theta^{\rm T}x^{(i)}}} \\[1em] &=&\frac{e^{-\Theta^{\rm T}x^{(i)}}}{\left(1+e^{-\Theta^{\rm T}x^{(i)}}\right)^2}\frac{\partial}{\partial \theta_j}{\Theta^{\rm T}x^{(i)}} \\[1em] &=&\frac{e^{-\Theta^{\rm T}x^{(i)}}}{\left(1+e^{-\Theta^{\rm T}x^{(i)}}\right)^2}x^{(i)}_j \\[1em] \therefore \frac{\partial}{\partial \Theta}{h_\Theta(x^{(i)})}&=&\frac{e^{-\Theta^{\rm T}x^{(i)}}}{\left(1+e^{-\Theta^{\rm T}x^{(i)}}\right)^2}x^{(i)} \\[1em] \end{eqnarray*} $$

    $l(\Theta)$ 对 $\Theta$ 求偏导：

    $$ \begin{eqnarray*} [\nabla_\Theta l(\Theta)]_j&=&\frac{\partial l(\Theta)}{\partial \theta_j} \\[1em] &=&\frac{\partial}{\partial \theta_j}{\sum_i^m{y^{(i)}\log{[h_\Theta(x^{(i)})]}+(1-y^{(i)})\log{[1-h_\Theta(x^{(i)})]}}} \\[1em] &=&\sum_i^m{y^{(i)}\frac{\partial}{\partial \theta_j}\log{[h_\Theta(x^{(i)})]}+(1-y^{(i)})\frac{\partial}{\partial \theta_j}\log{[1-h_\Theta(x^{(i)})]}} \\[1em] &=&\sum_i^m{\frac{y^{(i)}}{h_\Theta(x^{(i)})}\frac{\partial}{\partial \theta_j}{h_\Theta(x^{(i)})}+\frac{1-y^{(i)}}{1-h_\Theta(x^{(i)})}\frac{\partial}{\partial \theta_j}{[1-h_\Theta(x^{(i)})}]} \\[1em] &=&\sum_i^m{\left(\frac{y^{(i)}}{h_\Theta(x^{(i)})}-\frac{1-y^{(i)}}{1-h_\Theta(x^{(i)})}\right)\frac{\partial}{\partial \theta_j}{h_\Theta(x^{(i)})}} \\[1em] &=&\sum_i^m{\left(\frac{y^{(i)}}{\frac{1}{1+e^{-\Theta^{\rm T}x}}}-\frac{1-y^{(i)}}{1-\frac{1}{1+e^{-\Theta^{\rm T}x}}}\right)\frac{e^{-\Theta^{\rm T}x^{(i)}}}{\left(1+e^{-\Theta^{\rm T}x^{(i)}}\right)^2}x^{(i)}_j} \\[1em] &=&\sum_i^m{\frac{2y^{(i)}-1}{1+e^{\Theta^{\rm T}x^{(i)}}}x^{(i)}_j} \\[1em] \therefore \nabla_\Theta l(\Theta)&=&\sum_i^m{\frac{2y^{(i)}-1}{1+e^{\Theta^{\rm T}x^{(i)}}}x^{(i)}} \\[1em] \end{eqnarray*} $$

    训练的目标就是找到一个理想的 $\Theta$ ，最大化 $l(\Theta)$ 。

    所以训练过程就是：

    $$ \Theta :=\Theta+\alpha \nabla_\Theta l(\Theta) $$

感知机

  • Perception Algorithm（感知机算法）

  • Step Function（阶梯函数）

    $$ g(z)=\begin{cases}1, &{z\geq0}\\[1em]0,&{\text{Otherwise}}\end{cases} $$

Machine Learning