吴恩达ML 课程笔记

第一次学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)` 是常数项，不纳入RT¹ 中的。

我们也可以用同样的梯度下降方式迭代更新`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` 即为最终结果。 但是NN² 中，中间函数不叫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`归并并推导得³：

` 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 分就可以。如果分训练、交叉验证⁴、测试集合则是60/20/20 这样分。 CV 的结果，可以调整 RT 中的lambda ，而测试集则是看最后的效果。而模型选择，最简单就可以选择能让测试集合表现最好的模型。而要得到最好的模型，可能就需要:

• 调整lambda
• 增删features（包括增加polynomial features）
• 增加训练集等

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

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

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

则就有如后几个定义： ` 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 了⁵。

假设`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 的位置之后，目标函数值减小就比较缓慢了。

PCA⁶ 里做了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

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