吴恩达ML 课程笔记

Reading time ~21 minutes

第一次学Coursera 上的ML 课程的时候,遗漏了很多,而且那会儿笔记也做得不够,基础又差。 最近重温,整理一些重要的笔记吧。

Linear Regression

最简单也最常用的就是线性回归,最终就是为了学习如下的 `theta` :

`f(x) = theta^T vec x`

而怎么来学习这个f 函数及其`theta `?衡量标准是什么?最简单的,就让f 跟目标y 的差越小越好,也就是SSE(sum of square eror)这个目标函数(或叫损失函数):

` J(f) = 1/(2m) sum_(i=1)^m(f_i-y_i)^2 `

其中m 为样本的个数。

Gradient descent

而求最佳`theta` 的问题也就转化成求这个凸函数的最小值了。而要让J(f) 变小,其实就是让它的梯度渐渐接近0,那我们就可以以如后方式迭代更新:

` theta_j = theta_j - alpha del/(del theta_j) J(f) = theta_j - alpha 1/m sum_(i=1)^m (f_i - y_i) x_(ij) `

其中 `alpha ` 为learning rate,而`del/(del theta_j) f= vec x_j`

Feature scaling

比较建议就是把特征归一一下,最简单的归一就是减去mean 再除以range,这样就归一到[-1,1] 了。

Normal equation

其实如果数据量小,我们可以直接求解参数的。因为

` y = X vec theta `

其中,X 为样本矩阵,每一行为一个样本。 则求解后 `theta = (X^T X)^(-1) X^T y`

Logistic Regression

用于二分类的LR 其实就只是在线性回归的基础上加了一个sigmoid 函数,线性回归的正负数结果,也就对应了LR 的0、1 两个分类。

` f(x) = sigmoid(theta^T vec x) = g(theta^T vec x) = 1/(1+e^( - theta^T vec x)) `

因为y只可能为0 或1 ,而其损失函数则构造为:

` J_(LR)(f) = 1/(2m) sum_(i=1)^m - y_i log(f_i ) - (1-y_i ) log (1-f_i ) `

其实就是为了表征,y-f 越接近,损失函数的值就应该越小。

加上L2 的Regulization Term 则为:

` J_(LR-RT)(f) = 1/(2m) sum_(i=1)^m - y_i log(f_i ) - (1-y_i ) log (1-f_i ) + lamda/(2m) sum_(j=1)^n theta_j^2 `

其中n 为 `theta` 的长度,`theta(0)` 是常数项,不纳入RT1 中的。

我们也可以用同样的梯度下降方式迭代更新`theta `:

` theta_j = theta_j - alpha del/(del theta_j) J(f) = theta_j - alpha 1/m sum_(i=1)^m (f_i - y_i) x_(ij) `

而其中看似跟线性回归一样的梯度,实际上是通过推导损失函数的偏导数化简得来的。

Optimisation algorithms

  • Gradient descent
  • Conjugate gradient
  • BFGS
  • L-BFGS

Neural Networks

逻辑回归中 `f(x) = g(theta^T vec x)` 其实只需要学一个 `theta `。如果我们学多个比如L 个`Theta ` 会是怎样呢? `Theta ` 每一行为原来的一个`theta_i^T`,这样才能保证计算中间的`f_i` 仍然为向量。 `f_1(x) = g(Theta^1 vec x)`

` i= 2:L; f_i = g(Theta^i f_(i-1)); end `

最后得到的`f_L` 即为最终结果。 但是NN2 中,中间函数不叫f 而叫做 a (activation function),且有`a^1 = vec x`; `a^(i+1) = f_(i)`; `theta_i^T(0) -= 1`(因为每一次的`theta ` 我们都需要增加常数项)

NN 中,上标`i in [1,L]` 就代表对应层数的`Theta` 和 `a`,第一层和最后一层分别叫做输入输出层,中间的都叫做hiden layers 。

而因为`a^(i+1) = g(Theta^i a^i )` 则 `a^(i+1)` 的行数 跟`Theta^i` 行数一致,列数就正好跟 `a^(i)` 的列数一致

cost function

假设单次`a^i` 的 cost 为LR 的cost function `J_(LR)(a^i)` (设其中不包含RT)

则二分类NN 的整体cost function 即为:

` J(a) = J_(LR)(a^L) + lamda/2 * L2RT `

而L2RT 即为所有`Theta` 的L2 RT,即非常数项的平方和再除以样本个数m。

而如果NN 输出结果为多分类,即`f_L` 不为单值0/1,而是One-hot vector(即其中某一位为1其余位为0 代表确切的某个分类)。则`f_L` 的长度K 即为分类的数量。

那么多分类的cost function 则为

` J(a) = sum_(i=1)^K J_(LR)(a_i^L) + lambda/2 * L2RT `

gradient computation

同样,我们需要求出 `del/(del Theta_(ij)^l) J(a) ` 来最小化目标函数。 之前针对LR `del/(del theta_j) J(f) = (f-y) del/(del theta_j) f = Delta y del/(del theta_j) f`

则针对NN 则有一般形式:

` D_(Theta^i) = del/(del Theta^i) J(a^(i+1)) = Delta a^(i+1) del/(del Theta^i) g(Theta^i a^i) = Delta a^(i+1) a^i `

对于非常数项的`theta` 梯度应该还需要加上 ` lambda/2 L2RT` 的梯度 也就是 `lambda sum theta`

反向传播假设`a^i = g((Theta^i)^T a^(i+1))`,则由 `Delta y = Delta x del/(del x) y`归并并推导得3

` Delta a^i = (Theta^i)^T Delta a^(i+1) del/(del Theta^i) g(Theta^i a^i) = (Theta^i)^T Delta a^(i+1) dot xx (a^i dotxx (1-a^i)) `

其中`dot xx` 为点乘

Gradient checking & Random initialisation

可以通过近似`del /(del Theta) J(x) ~= (J(x+epsilon) - J(x-epsilon))/(2 epsilon)` ,用足够小的`epsilon` 来验证梯度函数的正确性。

参数初始化不能全为0,不者FP 和BP 都没办法做了,cost function 根本不会变化。 所以最后需要随机初始化`Theta`。

ADVICE FOR APPLYING ML

应用中,还是需要敏捷开发,先把模型build 起来,然后再处理细节并一步一步优化。

如果只是分训练、测试集合,一般70/30 分就可以。如果分训练、交叉验证4、测试集合则是60/20/20 这样分。 CV 的结果,可以调整 RT 中的lambda ,而测试集则是看最后的效果。而模型选择,最简单就可以选择能让测试集合表现最好的模型。而要得到最好的模型,可能就需要:

  • 调整lambda
  • 增删features(包括增加polynomial features)
  • 增加训练集等

而上述几个方面,主要就是看train/CV 集合上分别对应的偏差(目标函数值) bias/variance 表现来调整;而看这些表现也就可以通过画Learning Curves 很直观的看。

而优化模型的过程中,也可以多看bad cases ,然后再看为什么我们的算法没能学到,而总把类分错或回归问题算错。是特征没有覆盖到?还是没有归一化?还是分类中的正负样本比例不够?

而分类中正负样本比例悬殊的情况,通常就需要综合precision/recall 而使用F1 score 来判断分类器的好坏了。先对原始与预测的分类作如下定义:

predicted\actual class10
1true positivefalse positive
0false negativetrue negative

则就有如后几个定义: ` pre\cision = (# true positive)/(# predicted positive),
recall = (# true positive)/(# actual positive),
F1 = (2* pre\cision * recall)/(pre\cision+recall) `

虽然使用大数据能学到重要的规则,但是我们在选择特征的时候还是需要看,该特征是否含有足够的信息来预测我们的结果值。

SVM

SVM 中,目标函数跟LR 中类似,只是把LR 的目标函数

` J_(LR-RT)(f) = 1/(2m) sum_(i=1)^m - y_i log(f_i ) - (1-y_i ) log (1-f_i ) + lamda/(2m) sum_(j=1)^n theta_j^2 `

变成了:

` J_(SVM-RT)(f) = C sum_(i=1)^m - y_i cost_1 (f_i ) - (1-y_i ) cost_0 (f_i ) + 1/2 sum_(j=1)^n theta_j^2 `

其中,`cost_1 (f_i )` 和 `cost_0 (f_i )` 分别是y = 1/0 时,loss function 那两个log 函数的改写,并且新的这两个损失函数,不再是log 函数,而是把之前的log 函数,简化成更简单的elbow 函数,这样就比较方便的找到什么时候差不多就找到最小的loss 了5

假设`z = theta ^ T vec x = f_i`,则另: ` z >= 1 if y = 1, z <=-1 if y = 0 `

`cost_1 (z )= {0.5 - 0.5z if z<1 :}, 0 if z >=1}`

`cost_0 (z )= {0.5 + 0.5z if z>=-1 :}, 0 if z <=-1}`

故而当 `|z| >=1`, `J_(SVM-RT)(f) = 1/2 sum_(j=1)^n theta_j^2 = 1/2||theta||^2`

同时不难看出C 跟 `1/lambda` 的效果是类似的。所以:

Small C –> Higher bias, low variance
Large C –> Lower bias, high variance

另外,`theta ^T vec x = |vec x| * cos beta * |theta| = p* |theta| `,其中`beta` 是参数`theta 和 vec x` 这两个向量的夹角,p 也就是 `vec x` 投影到向量`theta` 上的长度。所以如果SVM 分割面垂直的`theta `,每一条样本`vec x` 投影到`theta ` 上的均长越长,那么这个分割面就越好。

所以为了让`J_(SVM-RT)(f)` 最小,且满足`|p * theta|>=1`,只需要让$p$ 最大化即可。

Kernels

Kernel 中我们手动找到landmarks 后(找不同的landmarks 那么对应的方差 `sigma^2 ` 也会不一样),若使用高斯函数 ` K_ (gaussian(x^i, x^l)) = e ^ ( - ||x^i- x^l||^2/ (2 sigma ^2)) = e ^ ( - (sum_(k=1)^n(x_k^i- x_k^l)^2)/ (2 sigma ^2))` ,则就需要选择`sigma^2 ` 。若`sigma^2 ` 越大,高斯函数相形的值就越高(目标函数也就越高),函数也就越平滑,那bias 就越高;反之越陡,bias 就越低。

找landmarks 的方式,假设原始特征长度n,样本长度m:

  • 将每一个sample 当作一个landmark 得到长度为m 的landmarks 数组`L`
  • 再利用核函数(本讲主要就是高斯函数)重新计算每个样本与每个landmark 的相似度,那么每个样本`x_i`都得到m 维度的特征 `vec f^i`;那么原来n 维度的特征就变成m 维了。
  • 最后就从原来的求解`theta^T vec x` 变成了求解 `theta^T vec f` 中的`theta`

其他可用Kernels: Polynomial kernel, String kernel, Chi-square kernel, histogram intersection kernel. 同时,所有的kernel function 都需要满足Mercer’s Theorem 才能优化过程收敛。

同时,SVM 和 LR 的应用场景为:

  • $n » m$ or $n « m$ . 使用LR 或 SVM without kernel
  • n is small, m is intermediate, SVM with Gaussian kernel

Clustering and PCA

K-means 思想:

  1. 随机选取 k 个centroids `mu_1 to mu_k`
  2. 对于每一个样本点`x_i`,找最近的centroid `c_i`,并合并进该cluster
  3. 每一个样本点都找到cluster 后,更新每一个cluster 的centroid
  4. 重新计算一下每一个`x_i` 对应的cluster 的centroid `mu_c(i)`
  5. 重复2-4 步,迭代n 次结束。

则目标函数即为:

`J = 1/m sum_(i=1)^m ||x^i - mu_c(i)||^2`

所以在如上第一步随机选取centroid 可能出现很大偏差的情况下,可以尝试K-means 很多次,然后选取目标函数值最小的一次结果。

而k 数量的选择,也可以使用不同k 画出目标函数值的这种方式选择。通常这也叫elbow 原则,因为在某一个k 的位置之后,目标函数值减小就比较缓慢了。

PCA6 里做了feature scaling & mean normalisation 后有,

` Sigma = (X^T X)/m`

`[U, S, V] = svd(Sigma)`

而若要降维度降成k 维度,只需要计算`Z = X * U_(reduce) = X * U( :, 1:k)`,而要还原后近似的X则为:

`X_(appro\x) = Z * U_(reduce)^T = Z * U( :, 1:k)^T`

那现在就还有另外一个问题,选择多大的k?只需要

` (sum||x^i - x_(appro\x)^i||^2) / (sum||x^i||^2 )<= 0.01 `

so that 99% variance is retained. 上式等价于如后的计算

`(sum_(i=1)^k S_(ii)) / (sum_(i=1)^n S_(ii)) >= 0.99 `

,其中S 就是SVD 解出的。

Anomaly detection

假设每一个特征下的数据都符合正太分布(不符合的,可以通过log、幂、根号等形式转换成符合正太分布的数据)。然后简单一点单个样本数据x 是否异常,就用$p(x)< \epsilon$ 来判断:

` p(x) = prod_(k=1)^n p(x_k,mu_k,sigma_k^2) = prod 1/(sqrt (2 pi) sigma_k) e ^ (- (x_k -mu_k)^2 / (2 sigma_k ^2)) `

其中n 为特征个数,$\mu,\sigma$ 对应每个特征的期望和标准差。即当样本x 的每个特征基本都处于边缘时,我们就觉着它是异常的。这个$\epsilon$ 可以用CV 集里面的异常值进行确定。

其实更一般的表达式,就是多元高斯分布。对于m 个训练样本。求均值` vec mu = 1/m sum vec x^(i) ` 和协方差 `Sigma = 1/m sum (vec x^(i)-vec mu) (vec x^(i)-vec mu)^T ` 那么同样的有:

` p(vec x, vec mu, Sigma) = 1/((2 pi)^(n/2) sqrt Sigma) e ^ (- 1/ 2 (vec x -vec mu)^T Sigma^(-1)(vec x -vec mu)) `

其中n,为特征的维数。所以当各个特征相互独立时(也就是$\Sigma$ 是对角矩阵,且主对角线上的元素就是每个特征单独的方差),也就得到前面那个$p(x)$ 的特例了。

Recommender System

假设在豆瓣网上

  • 每部电影都有n维 特征;$m^j$ 代表用户j 的评分电影数量;
  • $r(i,j)$ 用1/0 代表j 用户是否对i 这一部电影有评论;
  • `y^((:i,j:))` 代表用户j 对电影i 的实际评分;
  • $\vec \theta^j$ 代表用户j 在n 维电影特征上的权重值;
  • $\vec x^i$ 代表电影i 在n 维电影特征上的权重值;
  • `vec theta^((:j:)T) * vec x^i` 代表用户j 在电影i 上的预测评分值;

如此CF 优化的过程则是:

如果给定$\vec x$,求$\vec \theta$ 则目标函数则为:

` J(theta) = 1 / 2 sum_ (j=1)^ (n_u) sum_(i:r(i,j)=1) theta^((:j:)T) * x^i + lambda / 2 sum_ (j=1)^ (n_u) sum_(k=1)^n (theta_k^j)^2 `

如果给定$\vec \theta$,求$\vec x$ 则目标函数则为:

` J(x) = 1 / 2 sum_ (i=1)^ (n_m) sum_(j:r(i,j)=1) theta^((:j:)T) * x^i + lambda / 2 sum_ (i=1)^ (n_m) sum_(k=1)^n (x_k^j)^2 `

如果要同时优化$\vec \theta$ 和 $\vec x$;则需要把上述两者目标函数相加得到

` J(x,theta) = 1 / 2 sum_((i,j):r(i,j)=1) theta^((:j:)T) * x^i + lambda / 2 sum_ (j=1)^ (n_u) sum_(k=1)^n (theta_k^j)^2 + lambda / 2 sum_ (i=1)^ (n_m) sum_(k=1)^n (x_k^j)^2 `

而优化过程同样可以像线性回归那样使用梯度下降求解,但需要随机初始化比较小的$\vec x , \vec \theta$ 。其中$n_u$ 和 $n_m$ 分别代表用户和电影的数量。

Large scale ML

Batch gradient descent, 是针对特征j ,对全量样本计算梯度的平均后更新 ` theta_j = theta_j - alpha 1 / m sum _(i=1) ^m (f(x_i)-y_i)x_i `

而stochastic gradient descent,先对样本进行randomly shuffle 后,针对每个样本(一共m 个样本)都重新更新一下 ` theta_j = theta_j - alpha (f(x_i)-y_i)x_i ` 而若要让$\theta$ 最终收敛,则在迭代过程中就需要逐步减小$\alpha$

而mini-batch gradient descent 就是介于前两者之间,通常一次性计算2-100 个样本的平均梯度然后更新$\vec \theta$

Ceiling analysis

最后吴教授使用OCR 来分析了一下pipeline,以及整个系统,如何来确定哪一部分更值得投入精力。 简单的讲就是以Overal accuracy 作为基线,然后在pipeline 中依次人工让每个component 局部的accuray 弄成100%,然后看Overal accuracy 的提升幅度,据此判断哪一个部分提升效果对整体效果更明显。

Kullback–Leibler divergence

若用$P$ $Q$ 分别代表两个离散分布,那么用

` D_{kl}(P||Q) = sum_i P(i) log P(i)/Q(i) ` 表征两个分布的差异平均值,故其又叫相对熵。

Mathjax was not loaded successfully

  1. Regularisation Term 

  2. Neural Networks 

  3. 参照此书的“人工神经网络” 章节 《机器学习》 本博推导不一定正确 

  4. Cross Validation 

  5. Support Vector Machines 

  6. Principal Component Analysis 

Original post: http://blog.josephjctang.com/2015-08/ml-notes/

重操堆文这旧业之时间日志分析

写作的习惯,已经断了许久了。上一篇已经是去年的文章了,也是做的[时间日志分析]({% post_url 2019-02-23-time-log-analysis %}) 。 正好做时间总结,也把写作捡起来吧。# 低效时间分析用 [RescueTime](https://www.rescueti...… Continue reading

个人近期时间日志分析

Published on February 23, 2019

问问题的妙用

Published on May 27, 2018