coursera机器学习笔记

线性回归

LMS梯度下降法(基于最小均方)

时间复杂度:$O(kn^2)$
梯度下降法指的是参数(权重)同时更新,而不是先更新$\theta_0$再更新$\theta_1$

正确:

错误:

批量梯度下降法(Batch Gradient Descent)

再推导:
$\frac{\partial}{\partial \theta_j}J(\theta) = \frac{\partial}{\partial \theta_j}\frac{1}{2}(h_\theta(x)-y)^2$
$=2·\frac{1}{2}(h_\theta(x)-y)·\frac{\partial}{\partial \theta_j}(h_\theta(x)-y)$
$=(h_\theta(x)-y)·\frac{\partial}{\partial \theta_j}(\sum_{i=0}^n\theta_ix_i-y)$
$=(h_\theta(x)-y)x_j$

二元

$repeat\{$
$\theta_0:=\theta_0-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})$
$\theta_1:=\theta_1-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x^{(i)}$
$\}$

多元

$repeat\{$
$\theta_j:=\theta_j-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$
$\}$

随机梯度下降法(Stochastic Gradient Descent)

效率较低,常用于在线学习
$Loop\{$
$\space \space for\space i=1\space to\space m,\{$
$\space \space \space \space \theta_j := \theta_j+\alpha(y^{(i)}-h_\theta(x^{(i)}))x_j^{(i)}$
$\space \space \}$
$\}$

计算$J(\theta) = \frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2$不太现实,所以一般判断是否收敛有两种方式:

  1. 在使用$(x^{(i)},y^{(i)})$训练之前,计算$\frac{1}{2}(h_\theta(x^{(i)})-y^{(i)})^2$,训练之后,再重新计算该值
  2. 每1000次迭代或者2000次迭代后,计算总的cost值

随机梯度下降法会进入局部最优值,要进入全局最优值,可以缓慢减少学习速率$\alpha$,例如:

小批量梯度下降法(Mini-Batch Gradient Descent)

每次选取b个(少量,比如10个)进行梯度下降法。

特征缩放和均值化

当特征之间的数值范围比较接近时,梯度下降法能够更有效地工作。
特征缩放,将变量值除以(最大值-最小值)。
另外一个,均值化

$s_i$一般是最大值减最小值或者标准差。

选择学习效率

根据迭代次数对代价函数进行画图

最好的是第一个,称之为收敛;
第二个为学习效率较小的状态,原因是多次迭代仍然下降幅度较大;
第三个为学校效率较大的状态,原因是如下图,逐次上升。

多项式回归

例如拟合$h_\theta(x)=\theta_0+\theta_1x_1+\theta_2x_1^2+\theta_3x_1^3$
造出$x_2=x_1^2$和$x_3=x_1^3$
但这种情况需要很注意归一化问题。

正规方程Normal Equation

特征维数比较少时使用,不需要归一化,不需要迭代,不需要选择学习效率。

时间复杂度:$O(n^3)$

不适用情况

一般时$X^TX$无法求逆,原因有两个:

  1. 大量重复多余的特征,例如之间线性相关;
  2. 过多的特征$m \leq n$。

局部线性回归

用预测点周围的点计算线性回归,给训练集的点赋予权重进行计算。
$J(\theta)=\sum_i w^{(i)}(y^{(i)}-\theta^Tx^{(i)})^2$
$w^{(i)}=exp(-\frac{(x^{(i)}-x)^2}{2\tau^2})$
一个标准取法是上述。

证明最小二乘法

$y^{(i)}=\theta^Tx^{(i)}+\epsilon^{(i)}$
$\epsilon是误差,遵循高斯分布$
$p(\epsilon^{(i)})=\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(\epsilon^{(i)})^2}{2\sigma^2})$
$p(y^{(i)}|x^{(i)};\theta)=\frac{1}{\sqrt{2\pi}\sigma}exp(-\frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2})$
$likelihood \space function:$
$L(\theta)=L(\theta;X,\vec y)=p(\vec y|X;\theta)$

$log \space likelihood l(\theta):$

最大化l$(\theta)$,即最小化$\frac{1}{2}\sum_{i=1}^m(y^{(i)}-\theta^Tx^{(i)})^2$

Logistic回归

Sigmoid函数/Logistic函数

Logistic回归

Logistic回归,因为$0 \leq h_\theta \leq 1$,使用Logistic函数,所以才叫Logistic回归,但一般用来分类。

假设:
$P(y=1|x;\theta)=h_\theta(x)$
$P(y=0|x;\theta)=1-h_\theta(x)$
$p(y|x;\theta)=(h_\theta(x))^y(1-h_\theta(x))^{1-y}$

求导:

所以:
$\theta_j:=\theta_j-\alpha[-(y^{(i)}-h_\theta(x^{(i)}))x_j^{(i)}]$

决策边界

分开两类的超平面

cost function

分类之后,需要计算cost function,直接用线性回归的cost function,无法计算,因为不是凸函数。采用新的cost function。
$\space$
$J(\theta)=\frac{1}{m}\sum_{i=1}^mCost(h_\theta(x^{(i)}, y)$
$\space$
$Cost(h_\theta(x^{(i)}, y) = -log(h_\theta(x))\space if\space y=1$

$Cost(h_\theta(x^{(i)}, y) = -log(1-h_\theta(x))\space if\space y=0$

$Cost(h_\theta(x^{(i)}, y) = -ylog(h_\theta(x))-(1-y)log(1-h_\theta(x))$
$\space$
$J(\theta)=-\frac{1}{m}\sum_{i=1}^m[-y^{(i)}log(h_\theta(x^{(i)}))-(1-y^{(i)})log(1-h_\theta(x^{(i)}))]$
$向量形式:$
$h=g(X\theta)$
$J(\theta)=\frac{1}{m}·(-y^Tlog(h)-(1-y)^Tlog(1-h))$
$更新公式:$
$\theta_j:=\theta_j-\frac{\alpha}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$

更优的优化算法

  • 共轭梯度法
  • 牛顿法(二阶)

$\theta:=\theta-\frac{f(\theta)}{f’(\theta)}$
$目的是让l(\theta)最小值,即l’(\theta)=0$
$\theta:=\theta-\frac{l’(\theta)}{l’’(\theta)}$
$向量形式为:$
$\theta:=\theta-H^{-1} \nabla_\theta l(\theta)$
$其中H_{ij}=\frac{\partial^2l(\theta)}{\partial \theta_i \partial \theta_j}$

  • 拟牛顿法

多分类

一对多(One-vs-all)

感知器学习算法Perceptron Learning Algorithm

$g(z)=1,if \space z \ge 0$
$g(z)=0, if \space z < 0$
$let \space h_\theta(x) = g(\theta^Tx)$
$\theta_j:=\theta_j+\alpha(y^{(i)}-h_\theta(x^{(i)}))x_j^{(i)}$

过拟合(overfit)

欠拟合(underfit) 高偏差
过拟合(overfit) 高方差

防止过拟合

  1. 减少特征个数
    减少一些多余的或者贡献较小的特征,可以采用特征选择算法(model selection algorithm)。

  2. 正则化
    给$\theta$前加上系数,限制$\theta$的作用。

正则化

当不确定具体需要限制哪些$\theta$的作用时,采用总体的限制,比如范数

梯度下降法

$更新公式:$
$\{$
$\theta_0:=\theta_0-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_0^{(i)}$
$\theta_j:=\theta_j-\alpha[\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}+\frac{\lambda}{m}\theta_j] \space j \in \{1,2…n\}$
$\}$
$上式可写作:$
$\theta_j:=\theta_j(1-\alpha \frac{\lambda}{m})-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)} \space j \in \{1,2…n\}$
可以看作,相比于原本的更新公式,该更新公式每次更新会减小一点$\theta$的值。

Normal Equation

$\theta = (X^TX+ \lambda·L)^{-1}X^Ty$


L为$(n+1)*(n+1)维$。

Logistic回归

$J(\theta) = -\frac{1}{m}\sum_{i=1}^m[y^{(i)}log(h_\theta(x^{(i)}))+(1-y^{(i)})log(1-h_\theta(x^{(i)}))]+\frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2$
$更新公式:$
$\{$
$\theta_0:=\theta_0-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_0^{(i)}$
$\theta_j:=\theta_j-\alpha[\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}+\frac{\lambda}{m}\theta_j] \space j \in \{1,2…n\}$
$h_\theta(x)=\frac{1}{1+e^{-\theta^Tx}}$
$\}$

神经网络

$s_j表示第j层拥有的神经元数目,所以\Theta^{(j)}的维数s_{j+1}\times(s_j+1)$

$z^{(j)} = \Theta^{(j-1)}a^{(j-1)}$
$a^{(j)} = g(z^{(j)})$

逻辑运算的例子

多分类的例子

cost function

$\begin{gather} J(\Theta) = - \frac{1}{m} \sum_{i=1}^m \sum_{k=1}^K \left[y^{(i)}_k \log ((h_\Theta (x^{(i)}))_k) + (1 - y^{(i)}_k)\log (1 - (h_\Theta(x^{(i)}))_k)\right] + \frac{\lambda}{2m}\sum_{l=1}^{L-1} \sum_{i=1}^{s_l} \sum_{j=1}^{s_{l+1}} ( \Theta_{j,i}^{(l)})^2\end{gather}$
上式为多分类时cost function,$L$为神经网络层数,$K$为分类类数,直接导致最终结果的向量维数,等于最后一层的神经元数。即对每一种类别采用logistic回归时的cost function。

误差反向传播

误差反向传播四个核心公式:

  1. $\delta_i^{(L)} = -(y_i-a_i^{(L)})f’(z_i^{(L)})$

  2. $\delta_i^{(l)}=(\sum_{j=1}^{n_{l+1}}\delta_j^{(l+1)}w_{ji}^{(l+1)})f’(z_i^{(l)})$

  3. $\frac{\partial E}{\partial w_{ij}^{(l)}}=\delta_i^{(l)}a_j^{(l-1)}$

  4. $\frac{\partial E}{\partial b_i^{(l)}}=\delta_i^{(l)}$

具体参考coursera深度学习里的推导,主要用的是求导的链式法则。

梯度检验Gradient Checking

$\dfrac{\partial}{\partial\Theta}J(\Theta) \approx \dfrac{J(\Theta + \epsilon) - J(\Theta - \epsilon)}{2\epsilon}$
$\dfrac{\partial}{\partial\Theta_j}J(\Theta) \approx \dfrac{J(\Theta_1, \dots, \Theta_j + \epsilon, \dots, \Theta_n) - J(\Theta_1, \dots, \Theta_j - \epsilon, \dots, \Theta_n)}{2\epsilon}$
将结果与梯度比较,若正确则将梯度检验关闭,因为梯度检验速度很慢

随机初始化Random Initialization

随机初始化是为了打破对称。

1
Theta1 = rand(1,1) * (2 * INIT_EPSILON) - INIT_EPSILON;

训练步骤

  1. 随机初始化权重
  2. 向前传播,得到$h_\theta(x^{(i)})$
  3. 计算cost function $J(\theta)$
  4. 向后传播,计算偏导数
  5. 使用梯度检验,之后关闭
  6. 使用梯度下降等方法最小化成本函数

建议

  1. $训练:测试:验证=6:2:2$
  2. $高方差 or 高偏差$

  1. 正则化的作用

  1. 学习曲线

收集更多数据量对高方差是有作用的。

总结:

  1. 收集更多数据量:高方差
  2. 尝试更少的特征数:高方差
  3. 收集更多的特征:高偏差
  4. 增加多项式次数:高偏差
  5. 减小$\lambda$:高偏差
  6. 增加$\lambda$:高方差

朴素贝叶斯

特征量

如果每个特征需要N个样本,那么对于10个特征将需要N10个样本,对于包含1000个特征的词汇表将需要N1000个样本。可以看到,所需要的样本数会随着特征数目增大而迅速增长。如果特征之间相互独立,那么样本数就可以从N1000减少到1000×N。

朴素贝叶斯常见模型

  1. 高斯模型
    假设这些一个特征的所有属于某个类别的观测值符合高斯分布,目前还没看到例子,不理解

  2. 多项式模型
    按照次数作为特征,常用于文本

  3. 伯努利模型
    出现/不出现,对应01向量

k-means聚类

步骤

  1. 随机初始化k个点
  2. 将样本归类到最近的点
  3. 计算同个簇的点的均值点,作为新的簇中心点
  4. 将23重复,直到样本归类不再发生变化

k的取值

肘部法:最近一次明显下降的点。

PCA降维

步骤

  1. 特征均值化
  2. 计算协方差矩阵$\Sigma = \frac{1}{m} \sum_{i=1}^n (x^{(i)})(x^{(i)})^T$
  3. $[U,S,V]=svd(Sigma);$
  4. $Z = U(1:K)’*X;$
  5. 重建:$X=U(1:K)*Z$

K的取值

根据贡献率选取:

贡献率:99%
上式同等于:

作用

  1. 特征降维,以提高运算速度,减少内存使用;
  2. 降至2~3维,以可视化数据;
  3. 不可用于改善过拟合。

异常检测

高斯分布检测系统

  1. 选取正常样本
  2. 计算参数$\mu,\sigma^2$
  1. 来了一个检测样本,计算$p(x)$

$判断p(x) < \varepsilon$

仍然要分出训练集、测试集和交叉验证集

异常检测 vs 监督学习

异常检测

  1. 只有少量的异常样本
  2. 许多不同的异常类别
  3. 未来可能出现新的异常类别

监督学习

  1. 大量的正常和异常样本

特征选择

将样本特征画图,如果不像正态分布,可用多种函数映射成正态分布。

多元高斯分布检测分布

动机:当出现以下这种异常点,无法检测。

协方差矩阵$\Sigma$

步骤

  1. 计算$\mu,\Sigma$
  1. 计算$p(x)$

$判断p(x) < \varepsilon$

当$m >> n$时,才使用多元高斯分布,其他情况使用普通高斯分布。

推荐系统

$n_u = 用户数量$
$n_m = 电影数量$
$r(i,j) = 1 如果用户j给电影i评了分$
$y^{(i,j)} = 用户j给电影i评的分$

基于内容的推荐系统

$对于每个用户j,我们要学习出一个\theta^{(j)};而对于每部电影i,我们要学习出一个x^{(i)},则预测评分为(\theta^{(j)})^T(x^{(i)})$
$m^{(j)} = 用户j评分的电影部数$
$优化目标为:$

$\space$
$梯度下降法:$

$基于内容的推荐系统需要事先对每部电影给出x^{(i)},操作性不够强$

基于协同过滤的推荐系统

$假设每个用户的\theta^{(j)}已给出,则要学习出x^{(i)}$
$优化目标:$

$结合基于内容的推荐系统,我们可以先随机取值\theta,然后学习出x,再学习出\theta……$
$不用那么麻烦的办法,同时训练学习出\theta和x:$

步骤

  1. $随机初始化x和\theta为小的随机值$
  2. $使用梯度下降法,最小化J(x^{(1)},…,x^{(n_m)},\theta^{(1)},…,\theta^{(n_u)})$
  1. $\theta^Tx即为预测评分$

均值化

  1. 每行求平均值

  1. 矩阵每个值都减去该行的平均值

  1. 最后算出来的评分再加上该平均值$(\theta^{(j)})^T(x^{(i)})+\mu_i$

Map-reduce

将样本分开到每个计算机计算,之后再加和。
有将样本加和的步骤都可以采用Map-reduce。

一分一毛,也是心意。