Andrew Ng机器学习课程笔记(第八周至第十一周)

Machine Learning Dec 29, 2017

本笔记基于Coursera上吴恩达(Andrew Ng)的机器学习课程内容集结而成。(课程链接
全课程分为十一周,每周都有1-3个测验。第二周至第九周附有编程作业,一共8份。

更新:
3/1/2018: 更正kNN为k-平均算法

第八周

非监督学习(Unsupervised Learning)

非监督学习是使用非标签的数据来建立模型。非监督学习可用于建立数据集群,为数据分类。

k-平均演算法 (K-Means Algoithm)

  1. 随机在数据集中选择两点为集群中心(cluster centroids)。
  2. 为所有数据选择最近的集群中心。
  3. 移动集群中心到下属数据的中心点。
  4. 重新运行2-3直至建立集群。

K代表的是集群的数量。\({x^{(1)}, x^{(2)}, \dots,x^{(m)}}\)代表训练组。
在为数据选择最近的集群中心的步骤中,公式为:
\[c^{(i)} = argmin_k\ ||x^{(i)} - \mu_k||^2\]
其中\(c^{(i)}\)代表的是离数据\(x^{(i)}\)最近的集群中心的编号。
移动集群中心到下属数据的中心点,公式为:
\[\mu_k = \dfrac{1}{n}[x^{(k_1)} + x^{(k_2)} + \dots + x^{(k_n)}] \in \mathbb{R}^n\]
如果一个集群中心并没有任何下属的数据,可以为该中心重新随机设计一点,也可以直接消除该数据集。在一定数量的循环过后,模型会收敛,集群并不会有所变化。

优化目标

代价函数:
\[J(c^{(i)},\dots,c^{(m)},\mu_1,\dots,\mu_K) = \dfrac{1}{m}\sum_{i=1}^m ||x^{(i)} - \mu_{c^{(i)}}||^2\]
其中,\(c^{(i)}\)代表的是数据\(x^{(i)}\)所属的集群中心编号;\(\mu_{(k)}\)是集群中心;\(\mu_{c^(i)}\)代表的是\(x^{(i)}\)所属的集群中心。
优化目标是要\(min_{c,\mu}\ J(c,\mu)\)。代价函数的数值只会下降,不会上升。

随机初始

  1. 保证集群的数量少于训练样本数量。(K < m)
  2. 随机选择K个不重复的训练样本。
  3. 设置\(\mu_1,\dots,\mu_K\)在训练样本上。

k-平均演算法可能会困在局部最优解。为了减少发生的几率,算法模型需要至少跑几次以上。

集群的数量

肘部法则:为Cost J和K画图显示两者关系。Cost J在K到一定数量后,下降的幅度减少,趋于平缓。找出那一点的K值。(通常是Cost J的曲线是逐步下降的,那一转折点并不明显。)

下游目的(downstream purpose):选择一个最能达到想要目地的K值。也就是说,在选择K个集群,出来的结果最为有用,能达到想要的目的。

数据降维

降到数据的维度,以达到减少臃肿数据的目的。同时,透过该方法也能做到数据可视化的目的。

主成份分析(Principal Component Analysis (PCA))

PCA的目的是要减少每一个特征到投影线的平均距离,也就是减少投影误差。
PCA并不是线性回归,线性回归是减少平方误差,PCA是减少垂直距离。
预先处理:

  1. 给予一个训练集\(x^{(1)},x^{(2)},x^{(3)}...x(m)\)
  2. 特征缩放\(\mu_j = \dfrac{1}{m}\sum^m_{i=1}x_j^{(i)}\)
  3. 用\(x_j^{(i)} - \mu_j\)取代\(x_j^{(i)}\)
  4. 缩放所有特征\(x_j^{(i)} = \dfrac{x_j^{(i)} - \mu_j}{s_j}\)

2D数据缩放到1D数据,可以用公式来表示:
\[\Sigma = \dfrac{1}{m}\sum^m_{i=1}(x^{(i)})(x^{(i)})^T\]

PCA过程:

  1. 计算出协方差矩阵(covariance matrix)\(\Sigma = \dfrac{1}{m}\sum^m_{i=1}(x^{(i)})(x^{(i)})^T\)
  2. 找出协方差矩阵的特征向量(eigenvector)
  3. 取出头K个栏位的矩阵计算出z \(z^{(i)} = Ureduce^T \cdot x^{(i)}\)
    总结所有步骤:
Sigma = (1/m) * X' * X; % compute the covariance matrix
[U,S,V] = svd(Sigma);   % compute our projected directions
Ureduce = U(:,1:k);     % take the first k directions
Z = X * Ureduce;        % compute the projected data points

由压缩数据重建,由1D变2D的话(\(z \in \mathbb{R} \rightarrow x \in \mathbb{R}^2\)):\(x_{approx}^{(1)} = U_{reduce} \cdot z^{(1)}\)

K的数值可以参考这方法:

  1. 计算出平均平方投影错误。\(\dfrac{1}{m}\sum^m_{i=1}||x^{(i)} - x_{approx}^{(i)}||^2\)
  2. 计算出\(\dfrac{1}{m}\sum^m_{i=1}||x^{(i)}||^2\)
  3. 选一个最小的k值
    \[\dfrac{\dfrac{1}{m}\sum^m_{i=1}||x^{(i)} - x_{approx}^{(i)}||^2}{\dfrac{1}{m}\sum^m_{i=1}||x^{(i)}||^2} \leq 0.01\]
    可以这样表示:
    \[\dfrac{\sum_{i=1}^kS_{ii}}{\sum_{i=1}^nS_{ii}} \geq 0.99\]

使用PCA来减少过拟合问题是一个坏的用法。不要假设每个模型都需要PCA,先正常运行一次,再考虑是否需要PCA。

第九周

异常检测

设置\(x^{(i)}\)为i的特征。用数据设置模型p(x)。根据\(p(x) < ϵ\)识别一些不正常的活动。如果检测出过多/太多的异常,可以减少阀值\(ϵ\)。

高斯分布(正态分布)

x的高斯机会分布可以这样表示:\(x \sim \mathcal{N}(\mu, \sigma^2)\)。
完整的公式表示是:
\[\large p(x;\mu,\sigma^2) = \dfrac{1}{\sigma\sqrt{(2\pi)}}e^{-\dfrac{1}{2}(\dfrac{x - \mu}{\sigma})^2}\]
估算参数\(\mu\)为数据集的平均值:
\[\mu = \dfrac{1}{m}\displaystyle \sum_{i=1}^m x^{(i)}\]
然后估算参数\(\sigma^2\),用平均误差公式:
\[\sigma^2 = \dfrac{1}{m}\displaystyle \sum_{i=1}^m(x^{(i)} - \mu)^2\]
假设数据集的每个数据都是独立的,我们可以得出公式:
\[p(x) = \displaystyle \prod^n_{j=1} p(x_j;\mu_j,\sigma_j^2) \]

评估检测系统

用训练集\(\lbrace x^{(1)},\dots,x^{(m)} \rbrace\)算出模型系统的\(p(x)\)值。
在验证集上,预测一下结果:
如果 \(p(x) < ϵ\),y = 1
如果 \(p(x) \ge ϵ\),y = 0
然后使用F1数值等方法评估模型。

使用异常检测的情况:

  • 有一个很小数目的正样本和很多数目的负样本
  • 有很多种不同的异常,难于从正样本中找出,未来异常可能跟以往的异常情况不一样。

使用监督学习的情况:

  • 大数目的政府样本
  • 有足够多的正样本,可以推测出新的正样本的样子。

可以为数据进行变形(transforms)以便适合高斯分布。(例如:\(\log(x),\log(x+1),\sqrt(x),x^{1/3}\))

多元高斯分布
\[p(x;\mu,\Sigma) = \dfrac{1}{(2\pi)^{n/2} |\Sigma|^{1/2}} exp(-1/2(x-\mu)^T\Sigma^{-1}(x-\mu))\]

推荐系统

\(n_u \)为用户的数量,\(n_m \)为电影的数量,\(r(i,j) = 1\)为用户j评价了电影i,\(y(i,j) = 1\)为用户j给电影i的评分。
\(\theta^{(j)} \)为用户j的参数向量,\(x^{(i)} \)为电影i的参数向量。预测用户j在电影i的评分会是:\((\theta^{(j)})^Tx^{(i)}\)。
设置\(m^{(j)}\)为用户j评分过的电影数量。
\(\theta^{(j)}\)的数值可以透过这方法得出:
\[min_{\theta^{(1)},\dots,\theta^{(n_u)}} = \dfrac{1}{2}\displaystyle \sum_{j=1}^{n_u} \sum_{i:r(i,j)=1} ((\theta^{(j)})^T(x^{(i)}) - y^{(i,j)})^2 + \dfrac{\lambda}{2} \sum_{j=1}^{n_u} \sum_{k=1}^n(\theta_k^{(j)})^2\]

协同过滤(collaborative filtering)

代价函数可以更改为:
\[J(x,\theta) = \dfrac{1}{2} \displaystyle \sum_{(i,j):r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \dfrac{\lambda}{2}\sum_{i=1}^{n_m} \sum_{k=1}^{n} (x_k^{(i)})^2 + \dfrac{\lambda}{2}\sum_{j=1}^{n_u} \sum_{k=1}^{n} (\theta_k^{(j)})^2\]
算法分为几个步骤:

  1. 初始设置\(x^{(i)},...,x^{(n_m)},\theta^{(1)},...,\theta^{(n_u)}\)为一些较小的随机数值。
  2. 用梯度下降的方法最小化\(J(x^{(i)},...,x^{(n_m)},\theta^{(1)},...,\theta^{(n_u)})\)数值。公式为:
    \[\begin{gather}
    x_k^{(i)} := x_k^{(i)} - \alpha\left (\displaystyle \sum_{j:r(i,j)=1}{((\theta^{(j)})^T x^{(i)} - y^{(i,j)}) \theta_k^{(j)}} + \lambda x_k^{(i)} \right) \cr
    \theta_k^{(j)} := \theta_k^{(j)} - \alpha\left (\displaystyle \sum_{i:r(i,j)=1}{((\theta^{(j)})^T x^{(i)} - y^{(i,j)}) x_k^{(i)}} + \lambda \theta_k^{(j)} \right)
    \end{gather}\]
  3. 用\(\theta\)和特征\(x\),预测出评分\(\theta^Tx\)。

第十周

随机梯度下降法

这方法不用一次性计算出所有数据的梯度,而是运用各个数据来缓慢寻找准确的梯度。
\[cost(\theta,(x^{(i)}, y^{(i)})) = \dfrac{1}{2}(h_{\theta}(x^{(i)}) - y^{(i)})^2\]
训练组的代价函数为:
\[J_{train}(\theta) = \dfrac{1}{m} \displaystyle \sum_{i=1}^m cost(\theta, (x^{(i)}, y^{(i)}))\]

该算法的步骤为:

  1. 随机打乱数据组的排序。
  2. 从第一个数据到最后一个数据,计算\(\Theta_j := \Theta_j - \alpha (h_{\Theta}(x^{(i)}) - y^{(i)}) \cdot x^{(i)}_j\)

小型批量梯度下降

假设每次批量处理10个数据:
\[\theta_j := \theta_j - \alpha \dfrac{1}{10} \displaystyle \sum_{k=i}^{i+9} (h_\theta(x^{(k)}) - y^{(k)})x_j^{(k)}\]

随机梯度下降收敛

较小的学习效率很有可能找到一个更好的结果。所以学习效率代数应该要缓慢下降。公式为:
\[\alpha = \dfrac{const1}{iterationNumber + const2}\]

MapReduce和平行数据处理

MapReduce会讲计算工作拆分,最后合并起来计算。
\[\Theta_j := \Theta_j - \alpha \dfrac{1}{z}(temp_j^{(1)} + temp_j^{(2)} + \cdots + temp_j^{(z)})\]

第十一周

机器学习系统流程:图片识别(Photo OCR)

图片识别流水线:图像->文字检测->文字拆分->文字识别

取得更多数据的方法

  1. 换背景
  2. 扭曲/反转
  3. 添加白噪/噪点

上线分析

分析出改进哪一个部分最具性价比。
假设该部分能100%准确做到想要的效果,最终结果能提升多少。