关于这门MOOC

Coursera上面吴恩达的机器学习。老老实实学完的，代码都是自己打的，很有成就感。

注意事项：

要把每次编程作业放在桌面，再cd改到位置
可以直接在命令行type submit来提交
吴恩达不太喜欢gut feelings，更偏好systematic way

GUIDE

GUIDE default 只有十层然后开始prune

一棵树的复杂度取决于两点：Tree的复杂度，Node的复杂度。

Node复杂度排序：Piecewise: constant< simple linear< simple polynomial< stepwise< multiple linear

有一个内置的可以建立交互作用的列的方法，在dsc-file里面序列写成0

Importance-Score 是用来提示我们不要漏掉某些在树上没有出现，但是实际也很重要的variable。

Loh说Box-plot应用场景是当我们只有20~50数据的时候，所以现在数据量很大的时候，不能用box-plot做outlier-detection

基础知识

机器学习的定义：在标准P不变的情况下，从经验E中提升自己T操作的能力。
机器学习分为：

监督学习：对于数据集中的每个数据，都有相应的真实值，以供机器来训练自己。例如：Regression & Classification
无监督学习：对于数据集中的数据，是否能找出一种结构？例如：聚类（cluster）算法、鸡尾酒宴会（分离两种声音）

Notations:

m:训练集的数据量
h:拟合出来的函数是一个从x到y的映射，例如：Guide输出的R-function
J(θ):平方误差代价函数。J=RSS/2m
:= colon-equal 赋值assignment
n:自变量的个数:x1~xn

要注意：h(x)是x的函数而J(θ)是θ的函数
J(θ)在只有一个参数的时候是抛物线，有两个参数的时候变成了一个『抛物面』。但是二维图中画不出来，所以便有一招，二维图两个轴分别代表θ0和θ1，然后画出contour plot。

Gradient Descent Algorithm梯度下降法：

可以最小化函数。想象自己在一座山上，每次迈出一步，这一步的方向是当前位置下山最快的方向。
算法：repeat until convergence{θj := θj - α * (J对θj求偏导) 对J里面的每个θ同时操作}
α被称为learning rate，也就是下山的时候该迈多大的步子。
随着越来越接近最低点，导数项会变小，步子自然地也会越迈越小。
Batch GD：每一步求导都要用到整个（Batch）训练集。

还有种方法叫Normal equation method? 答：就是正常的回归分析

3 * 3矩阵有时候也被写成R，3 * 3被放在了上标里面。n * 1的矩阵是R(4 * 1)，*1可以省略，于是就变成了常见的那个样子。
矩阵的(i,j)元素被称为：i,j entry
1-indexed & 0-indexed：y1~yn & y0~yn

Feature Scaling:

Idea: Make sure features are on a similar scale.
做法：通过除法，将他们的Range搞到（-1，1）吴恩达自己的建议是（-3，3）

经常通过画一个 min(J(θ))—No.of iterations 的图来判断收敛情况。
如果一次迭代导致的变化小于10^-3 jiu认为是收敛了
如果迭代之后MIN不降反升，那么可能是步子迈得太大，应该缩小α。
数学家证明了如果步子足够小，J（θ）应该每次迭代都会下降
α太小或者太小都有可能导致收敛的速度过慢。
所以如何寻找α？吴恩达先找一个足够大的上界和一个足够小的下界。然后三倍关系去试：0.001-0.003-0.01-0.03-0.1-…
存在一些算法来自动帮我们选择多项式回归次数
Normal Equation：就是用（x’x）-1x’y来计算β。缺点是在自变量很多的时候，矩阵不好算，而梯度更快（n大于10000）
计算n阶矩阵的逆大概需要O(n^3)
xTx不可逆一般有两种可能性：

有两列高度线性相关
数据量过少或者自变量过多（极端情况就是行数小于列数）对于这种情况，要么删一些列，要么用regularization

loss function 也叫 objective function

Optimization

除了Gradient Descend 其他方法都不需要自己输入步长 $\alpha$ 并且也比梯度下降更快，缺点只是更复杂一点

主要方法：

Gradient Descend
Conjugate Gradient
BFGS
L-BFGS
…

Classification

如果我们用线性拟合的话，一些超远处的离群值可能会对整个拟合直线产生巨大影响。

##Logistic

用的是logistic/sigmoid function $y = \frac{1}{1+e^{-z}}$ 会产生一个0~1的函数。 Threshold一般设为0.5 也就是在z>0的时候。一般来说z = $\theta^TX$ 所以， $\theta^TX=0$ 又被称为 Decision Boundry。所以Decision-boundary是一个关于hypothesis的性质而不是关于data set的性质
sigmoid在4.6的时候函数值为0.99. 在-4.6的时候函数值为0.01
Cost function. 如果用常规的square-error的话，最后的损失函数是non-convex的，会有多个局部最小值。Cost function: $cost(h_\theta(x),y) = -log(h_\theta(x))I_{y=1}-log(1-h_\theta(x))I_{y=0} =\\ -ylog(h_\theta(x))-(1-y)log(1-h_\theta(x))$
哇！我们神奇的发现，使用梯度下降法时，logistic和linear的导数部分具有同样的形式 $\theta_j:=\theta_j-\alpha\sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})x^{(i)}$

Multiclass Classification

One v.s. All

本质上还是logistic。对于每一个class，做一个属于该class和不属于该class的logistic。得到一个 $h_\theta^1(x)$ . 以此类推得到其他的。则对于一个新的test sample，我们看哪一个h最大，就将他划为哪一组。这时的y就不是一个单一的0/1随机变量，而是一个1一堆0的随机向量

Overfitting

underfitting一般会带来High bias。overfitting会带来high variance
解决overfitting的办法：1、减少features（手动/采用一些变量选择方法）2.Regularization.

Regularization

keep all features, but reduce magnitude/values of parameter.(变量前面的系数变小了) Works well when there are lots of features and each contributes a bit to the response.

Small values for parameter: 1. ‘Simpler Hypothesis’ 2.Less prone to overfitting

具体操作：在损失函数后面加上 $\lambda/2m$ 倍的所有系数平方和（除了intercept），shrink all parameters。 $\lambda$ 被称为regularization parameter
在梯度递降法里面多了一项 $-\frac{\alpha}{m}\lambda\theta_j$ . 在最小二乘法中变成了 $\widehat{\beta}=(X'X+\lambda*A)^{-1}X'Y$ 其中A是一个在1,1位置上是0的单位阵
这一招还顺带解决了 $X'X$ 矩阵不可逆的情况，使之可逆

Neural Network

传统方法会有一些问题，比如在Nonlinear-classification的情况下：如果单单用线性拟合的话，在100个feature的时候，我们要动用polynomial轻易就可以达到O(n^3)，实在是太多变量了

大脑有个一个主管学习的区域，无论给他输入什么数据，他慢慢自己都能学会。例子：一个主管听力的皮层在改为接受视觉信号之后学会了主管视觉

六部走：

Randomly initialize weights
implement forward propagation to get $h_{\Theta}(x^{(i)})$ for any $x^{(i)}$
compute cost function $J(\Theta)$
implement back-prop to compute partial derivatives
Use gradient-checking the derivatives.
Using advanced optimization method with back-prop to minimize cost function

parameters 有时也被称作weights
input layer - hidden layer - output layer
$a^{(j)}_{i}$ 表示第j层layer中第i个neuron. $\Theta^{(j)}$ 表示从第j层到第j+1层的变换（左乘）矩阵，矩阵维数为 $S_{j+1}*(S_j+1)$ 最后加的这个1是因为有 $a_0$ 截距项：Forward propagation
跟logistic的一个明显区别：不用原来的自变量x而是用经过hidden-layer变换后的新自变量
logical and/or 可以用sigmoid-function写。给intercept-a-b分别加权(-30,20,20)/(-10,20,20)
一般来说的话，先假设有一个hidden-layer，如果实在想多几个，那么也尽量保证每个hidden-layer的units个数相同。通常来说hidden-layer的units尽量也比feature（input-layer）多一点.

back-propagation 反向传播算法

先从左到右算出来函数值，再从右到左算出来导数/误差值。不计算常数项的误差
有时虽然cost-function在递降，但是可能会存在一些小bug，这是我们需要引入gradient-check：2-sided-difference 用切线斜率来估计导数： $[f(x+\epsilon)-f(x-\epsilon)]/2\epsilon$ , where $\epsilon \approx 10^{-4}$ .
random-initializing: 在 $[-\epsilon,\epsilon]$ 里面取值。rand(dim)*2 $\epsilon$ - $\epsilon$ .

Debugging a learning algorithm

Get more training samples：解决过拟合
Try small sets of features(avoid overfitting)：解决过拟合
Try getting addtional features：解决欠拟合
Try adding polynomial features：解决欠拟合
increasing/decresing $\lambda$ in the regularization term

Diagnose the ML algorithm

error for classificationo problem:
1. Misclassification cost(0,1)
2. logistic loss: $\frac{1}{m}\sum-ylog(h_\theta(x))-(1-y)log(1-h_\theta(x))$
如果只把data分成70%train-30%test（只分一次），会导致选出来一个针对30%test最优化的算法，也不够generalize。所以我们可以60%train-20%CV-20%test. 先用train来拟合参数，再用CV来选算法，最后用test来估计误差
High-bias = under-fitting. High-variance = over-fitting
这个图表示如果Train&CV的误差都很大，那么是under-fitting，如果Train小CV大很可能是over-fitting
在包含regularization的例子中，如果我们选择的 $\lambda$ 很大的话可能会导致under-fitting，相反则会导致over-fitting
所以我们该如何选择 $\lambda$ ?：将 $\lambda$ 从小到大排即是不同的模型，再用cost来拟合，CV来选择（这个CV的cost是不含regular那一项的，同理我们只用含regular的来拟合参数，报告train-error的时候也是不含regular那一项的）
一般来说，用一个复杂的神经网络+regularization，要比用一个简单的神经网络效果要好
##Learning curves:
横坐标是sample-size，纵坐标是error。其中error的计算只对用到的数据取平均（从100个样本中用了三个来拟合模型，那最后算cost的时候就只算这三个的平均cost）
在出现high-bias(under-fitting)的时候，增加数据量是没什么用的，但是overfitting的时候，增加数据量有用（模型不变的情况下）

Recommended Approach

先采用一个快速容易实现的方法，并且用CV来验证
画出learning-curves来判断我们是否需要更多数据/更多特征
Error-analysis 观看那些残差很大的点（或者是分错类的点），看他们为什么出了错
对各种不同的算法用一种方式来量化比较

有时还涉及到要不要stemming/大小写（把discount,discounts看做一个，但也会把universe和university看成一个）这时候很难说效果怎么样，所以只能在CV集合上面测试一下，然后看看出错率

Skewed class

Precision/Recall: 可以写成一个二乘二矩阵
Precison = True prositive/Predicted Positive(第一行)
Recall = True prositive/Actual Positive(第一列)
一般来说都用y=1 来表示那个稀少的类（比如患了癌症）

Trade off between Precision&Recall

我们可以调整logistic的threshold。如果调高的话，会增加precision，降低recall
一种简单的方法是计算 $\frac{P+R}{2}$ ，但明显不好，全部预测为0会得到差不多最好的结果
一种更通用的方法是计算F1-score: $2\frac{PR}{P+R}$ 。调和平均，（如果有一个0的话基本上F1-score就是0了）

Large Data Set

比的不是谁的算法吊，而是谁的数据量大（希望自己有朝一日能取到一家海量数据的公司）
遇到一个问题，问问自己，如果把这个信息告诉一个这方面的专家，他能不能做出准确的预测，如果能的话，说明这信息是充分的，那我们可以用海量数据来减小误差，如果不能，单纯增加数据量是没用的，我们必须获取其他的特征。

Support Vector Machine

cost function: $C\sum_{i=1}^m[y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})] + \frac{1}{2}\sum_{i=1}^n\theta_j^2$
hypothesis: $h_\theta(x)=I(\theta^Tx\ge0)$
Large Marigin Intuition: margin指的是分界线距离两类各自边缘的距离，svm会选出来一条线使得这个距离最大，所以更robust。
C如果越大的话（相当于regularization里面的 $\lambda$ 越小），整个SVM就会对离群值越敏感，容易出现过拟合
decision boundary那条线与 $\vec{\theta}$ 是垂直的。
疑问：SVM desicion boundary是不是只由最边缘的点决定？
VS logistic：当数据量m远小于参数个数n的时候，用logistic/不带kernal的SVM，如果n比较小（1-1000）而m适中（10-10000），可以用Gaussian-kernal。如果n小m大（50000+）这时跑SVM就慢的一批，只能多加几个feature然后用logistic/不带kernal的SVM

Kernal

kernals有好多种（Gaussian…）目的是为了刻画x和landmark之间的similarity。不用kernal又被称为linear-kernal，在数据量不足的时候一般我们不能用太复杂的kernal
一个Kernal一定要满足Mercer’s Theorem
Ng举了一个中间护舒宝形状的X外面是O的分类例子，可以在中间设置两个landmark，然后用kernal来解决
Gauss的参数 $\sigma^2$ ： $\sigma^2$ 越大， $f_i$ 的变化就越缓慢，容易导致欠拟合，higher-bias
做Gaussian之前，要对feature做scaling
其他kernal：polynomial-kernal（like $(X^Tl+a)^b$ …），string-kernal(针对text类型的数据), chi-square-kernal, histogram-intersection-kernal

基本步骤

把每一个数据点都先标记成为landmark
计算feature vector： $f_i=similarity(x,l^{(i)})$ 可以增加常数项： $f_0=1$
预测y=1，当且仅当 $\theta^Tf \ge 0$

Unsupervised Learning

Clustering Algorithm

各个聚类方法的scale时间

K-means

先随机找到两个点（只分两组的时候）
把其他的点根据距离初始点的距离划分成两大类
用分好的两大类的重心来代替原来的两个点。
循环1-3，直至converge

distortion-cost-function： $\frac{1}{m}\sum_{i=1}^m||x^{(i)}-\mu_{c^{(i)}}||^2$

Initialization: 选取k<m, 然后从数据点中随机选取k个作为 $\mu_1 \sim \mu_k$ . 有时候数据点选择的不好的话，会导致算法优化到局部最优而不是全局最优，这时我们可以做的是：随机选取100次，对于每次选择的k个随机点，我们计算他的cost，最后，在这100个随机cost中，选择cost最小的那个作为我们的initial k个点。

Elbow Method for choosing K：选择那个斜率变化最大点

Dimensionality Reduction

主要用途：

为了visualize数据，我们可以把维数强行降到2，然后打印在平面图上
加快分析速度，减少内存使用

PCA与linear的一个明显的区别：lm最小化竖着的线段平方，PCA最小化垂直线段的平方。因为lm里面y是我们更关心的点（主要目的就是为了预测y），而PCA中各个x地位是平等的。

步骤：

先计算cov矩阵 $\Sigma=\frac{1}{m}X^TX$ （包含了标准化）
计算 $\Sigma$ 矩阵的eigen：[U, S, V] = svd(Sigma) [其实eig函数也可以做，但是不如svd稳定] 其中U会返回按列排放的特征向量，S是个对角矩阵，存放了每个PC分别解释了多少的方差
最后: $z^{(i)}=U^Tx^{(i)}$
$x_{approx} = Uz^{(i)}$

一个选择PCA个数的准则是解释99%/95%的方差

在做PCA的时候，只对train做，而不做CV和test

一个不好的例子：用PCA来防止过拟合（因为少了需要拟合的参数个数）。因为有时候我们在PCA中扔掉了一部分信息，但这部分信息很可能和y很有关，所以为了防止过拟合，不如直接使用regularization。

PCA使用建议：先对raw-data直接做分析，只有当原始数据做不了的时候（比如说太慢了或者内存不够大），再开始尝试PCA

Anomaly Detection

对于那些离群的异常点检测，定义一个p值（一个关于自变量的函数），如果p值过小就被视为离群值。

Machine-learning里面习惯用MLE来估计方差（分母是m）

Gaussian Distribution

具体步骤：

假设n个 $x^{(i)}$ 是独立且是正态分布的，用已有的样本来估算均值和方差。
给定一个新样本，他的p值定义为 $\prod_{i=1}^n\Phi_i(x_i)$
跟临界值进行大小比较

一个实例：

假设我们现在的数据多了一个label：正常/不正常，我们现在有10000个正常和20个不正常
先将数据分为三组：train（6000，0）CV（2000，10）Test（2000，10）
用Train那一组来拟合参数（每个变量的均值&方差）
拿出CV，对于一个选定的临界值 $\epsilon$ ，我们将 $p(x_i)<\epsilon$ 的那些样本点赋予y=1(不正常)，其他点赋值y=0.
将y对x进行NN/logistic，计算F1-score。通过不同 $\epsilon$ 的选取，选出其中能使得F1-score最大的 $\epsilon$ 作为最后的临界值。

Anomaly-Detection v.s. Supervised-learning

一般来说，Supervised-learning一般解决的问题是当两类数量差不多的时候，而当y=1特别少（skewed-class）的时候，我们惯用Anomaly-Detection
S-L一般解决未知数据长的很像test数据的问题，所以准确性更高。但一般skwed-class的异常都是「各有各的异常」，很可能未知的数据在以前就没有出现过，这时候一般都交给A-D来做。
像Spam-Email那个例子中，因为我们有很多Spam可以供训练模型，并且可能一般来说未来出现的垃圾邮件很可能和之前的垃圾邮件长得很像，所以我们采用Supervised-learning

How to choose features?

首先我们可以画出feature的分布图，如果看起来不是很正态，我们可以做一下box-cox（或者取log）来使得它看起来正态。（但是他说好像如果正态不满足的话好像算法也没啥大问题）
经常还会遇到的一个问题是：我们经常假设如果数据越异常，p(x)就会越小，但是有时候不论是不是异常，p(x)始终都差不多，这时候我们就需要加入新的变量（这里的新不仅可以加入之前没用的变量，还可以是一些变量的函数）。

Multivariate Gaussian Distribution

如果两个变量之间存在cor，那么原来的圆形置信域就会变成椭圆形，导致一些异常点检测不出来(例子：一三象限方向的椭圆，对于二四象限的异常点有可能检测不出来，因为关于x-y轴的两个投影都不是很小)

我们只需要将原来的p(x)连乘变成多元正态里面的p(x)就可以了 $p(x)=\frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}}exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))$
同样使用样本均值和样本协方差矩阵来估计那两个参数

两种分布的对比：

多元正态自动捕捉了feature之间的协相关，单变量正态需要自己手动添加
单变量要比多元快很多
当数据量m小于变量个数n的时候（或者当feature之间线性相关的时候），多元正态协方差阵不可逆。当m比n大很多的时候（10倍），考虑用多元。

Recommander System

就拿电影评分来举例子：

Feature-vector: 每个电影可以被量化成一个向量 $x^{(i)}$ , 第一位是截距项，后面的是每一种类别涉及到的比例（爱情0.5，动作0.8…）
r(i, j) = if user j has rated movie i 示性变量
$y^{(i,j)}$ = rating by user j on movie i
$\theta^{(j)}$ = parameter vector for user j : 观众的喜好向量(爱情5，动作8…)
$m^{(j)}$ = #of movies rated by user j
For user j , movie i, predicted rating: $(\theta^{(j)})^Tx^{(i)}$
Cost-function for each $\theta^{(j)}$ : $\frac{1}{2m^{(j)}}\sum_{r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2m^{(j)}}$
Cost-function for all users: 只需要把上面这个cost-function 对所有用户求和即可

Collabrative Filtering

Optimization algorithm: 还可以给定 $\theta$ 反向来求出feature-vector $x^{(i)}$
Try to minimize: $\frac{1}{2}\sum_{r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum_{k=1}^n (x_k^{(i)})^2$
最后我们对每一个电影都算一下上面的cost然后求和。

所以实际上我们可以估计用户的初始 $\theta$ ，然后来拟合feature，再用拟合的feature重新拟合用户的 $\theta$ ，如此循环往复，最后收敛到一个合理的结果。

但是我们可以更进一步，把两种cost-function写在一起，同时对他们整体做minimization，一步到位。这时候也不用填写截距项，因为算法应该会自动添加需要的截距项。开始需要randomly initialize number，为了symmetry-breaking

Low rank matrix factorization: 将预测用户的评分写成一个矩阵： $X\Theta^T$

判断两个电影很像，small $||x^{(i)}-x^{(j)}||$

Mean Normalization

如果一个新用户曾经没有给任何电影评分，那么根据我们上面的cost-function来看，最佳的预测就是该用户的 $\theta$ 是一个零向量。这样我们也不能给他推荐什么电影，没有什么意义。

步骤：

对于每个电影，计算当前用户评分的均值。
然后将每个用户对于当前电影的评分减去均值
这时新用户的一排零，就变成了各个电影都是‘‘适中’’评分，我们就可以给他推荐电影啦

Dealing With Large Data Set

为什么我们要用更多的数据？

我们可以画出learning-curve，然后发现当m很小的时候， $J_{CV}$ 很大，我们面临了high variance的情况，这时候提高m的数量有助于更好的拟合。但是如果我们发现learning-curve呈现的是high-bias的情况，那么我们就没啥必要提高m的数量了。

Stochastic Gradient Descent

正常的一次性计算所有的梯度下降又被称为Batch-Gradient-Descent： $\theta_j:=\theta_j-\alpha\sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})x^{(i)}$

步骤：

Randomly Shuffle the dataset 随机排序
从第一个数据开始，对每个数据做一个小的单变量梯度递降。 $\theta_j:=\theta_j-\alpha (h_\theta(x^{(i)})-y^{(i)})x^{(i)}$ for every j
重复做第二步1-10遍(每一次都重新shuffle)
最后应该会落到全局最优的附近

Check for convergence:

在每一次更新 $\theta$ 之前，记录当前数据点的 $cost(\theta,(x^{(i)},y^{(i)}))$
每更新比如说1000次，计算一下1000个cost的平均
最后将这些平均数进行比较，画个图
一般来说数据取得越大（比如说用5000代替1000）， $J_\theta$ 关于迭代次数的曲线就会越平滑
如果发现 $J_\theta$ 不降反升，那么我们可以试着减少步长 $\alpha$ （learning-rate）
如果我们想试着最后落入到全局最优点，我们可以逐渐减小步长，let $\alpha = const1/(\#iteration+const2)$

Mini-batch Gradient Descent

正常的Batch每次迭代用到all m examples. Stochastic只用1个。Mini-batch取了个中间地带，每次用b个，其中b也被称为mini-batch size.

步骤：

Randomly Shuffle the dataset 随机排序
从第一个数据开始，b个b个的应用梯度下降来迭代 $\theta_j$
重复做第二步1-10遍(每一次都重新shuffle)
最后应该会落到全局最优的附近

Mini-Batch 如果想要比Stochastic跑得更快，就必须要应用Vectorization

Online Learning

一个数据网站，获取用户的数据，不停的更新原来的 $\theta$ , learning continuously
CTR: 用户搜索一个信息，我们来预测他会不会点击我们给他提供的链接，learning the predicted Click Through Rate

步骤：

永久性的循环以下步骤
获得数据（x, y）, 更新 $\theta_j:=\theta_j-\alpha (h_\theta(x)-y)x_j$
把数据(x, y)扔掉，只保留更新后的 $\theta$

Map Reduce

如果有四百个数据，在计算梯度下降的时候可以把数据分成四份，分给四个电脑去同时并行做。

为什么可以用Map-Reduce：Many learning algorithm can be expressed as computing sums of functions over the training set. 算法可以写成关于数据量的求和

有时候就算没有多台电脑，一个电脑有很多个核，也可以做Multi-core Machines

Open Source：Hadoop

Photo OCR

Photo Optical Character Recognition

主要步骤（pipeline）:

Get a Image
Text Detection
Charcter Segmentation
Character Classification

Sliding Windows

Pedestrian Detection

Supervised-learning-version:

我们给定一些固定大小的人像的正确例子（y=1），和一些不是人像的例子（y=0）
紧接着，我们在原图上从左上角开始一点点向右移（step/sliding-size）如果一个像素一个像素移动的话太慢了，所以我们会让他每次跨的大一点。过完一行，再来一行….直到整个图都被过了一遍
然后，我们将选取框放大一点，再跑一边步骤二（不管选取框是多大，在做检验的时候都要先变成和给定例子training-set中的大小一致）

现在让我们回到Text-Detection：

text-detection比行人识别的一大难点在于大小不是固定的
所以开始的时候先一个一个像素点过，形成一个黑底图，上面的白色表示可能存在text
下一步是Text-expansion 将临近的白色区域连接起来，看成一大块文字域

Character-segmentation 也可以用sliding window来做

Artificial Data Synthesis

creating data from stretch 无中生有
amplify the small data set 将小数据集变大

吴恩达用的是字母识别的例子，无中生有：自己在网上找点字体，自己加点背景上去。以小见大：从已有的字体图片，经过旋转变形生出新的字体图片

Make sure you have a low bias classfier before expending the effort. 如果当前是过拟合的话是需要更多数据，但如果是欠拟合的话，我们首先应该考虑的是在模型里面多放几个变量，而不是通过这种方式使得数据变多。

其次应该问自己的问题是，如果要把当前数据量变成十倍，需要多少工作量？

Ceiling Analysis

在一个pipeline中，先看overall accuracy。然后再去第一个环节，手动把第一个环节准确率调成100%，看看对overall有什么影响。

有助于我们发现pipeline中哪一环节是最需要花时间来提高的

吴恩达嘲讽了一手：说有个小组，花了一年时间专门研究怎么去掉背景，甚至还发了论文，但最后发现准确率从85%提高到了85.1%，并没什么卵用

NLP

Sentiment Analysis

There are many types and flavors of sentiment analysis:

Fine-grained Sentiment Analysis
Emotion detection
Aspect-based Sentiment Analysis
Intent analysis
Multilingual sentiment analysis

Some of the advantages of sentiment analysis:

Scalability
Real-time analysis
Consistent criteria

Methods and algorithms to implement sentiment analysis systems:

Rule-based systems that perform sentiment analysis based on a set of manually crafted rules.
- Classic NLP techniques like stemming, tokenization, part of speech tagging and parsing.
- 常用方式是建立两个集合，一个好一个坏。对一段文字，我们数其中好的词出现的频率和坏的词出现的频率，哪个多选哪个。一样多就是中性。这个方法坏处在于：
  1. 只算了单个的词而没有组合起来
  2. 添加更多规则之后很容易就变得超级复杂，并且不同的rule之间可能冲突，需要很多的人工进行tune
Learning-based/Automatic systems that rely on machine learning techniques to learn from data.
- 不用人工的rule，从文字中抽取feature和label，都一起扔给机器学习算法。
- Feature: 一般是numeric结果。Usually, each component of the vector represents the frequency of a word or expression in a predefined dictionary . The classical approach has been bag-of-words or bag-of-ngrams with their frequency.
- More recently, new feature extraction techniques have been applied based on word embeddings (also known as word vectors). This kind of representations makes it possible for words with similar meaning to have a similar representation, which can improve the performance of classifiers. （这一段是为了提高准确率的，但是我没搞懂他是怎么操作的）
- Classification Algorithms: Naïve Bayes, Logistic Regression, Support Vector Machines, or Neural Networks
- Metric 判断：Precision, Recall, and Accuracy（是不是也考虑F1）但是老师要求的是RMSE。Krippendorff’s Alpha 也是一个好的评分方法，0.67/0.8为界
Hybrid systems that combine both rule based and automatic approaches.
- Usually, by combining both approaches, the methods can improve accuracy and precision. 周子涵说过什么stacking

Irony and Sarcasm 讽刺语气感觉是个难点。Yeah, sure.有时候表达的是无所谓了就这样吧的意思

Comparisons: 一些例子：

This product is second to none.
This is better than old tools.
This is better than nothing.

Emojis: 疯了。丧心病狂

Western emojis (e.g. 😄) are encoded in only one character or in a combination of a couple of them whereas Eastern emojis (e.g. ¯ \ _ (ツ) _ / ¯) are a longer combination of characters of a vertical nature.

转折Ordering Effect：

听说不错，演员也好，票房也高，然而我觉得它糟糕透了。

Subjectivity classification

Goal: Classifying a sentence as subjective or objective

Text information can be broadly categorized into two main types: facts and opinions.

Opinion

There are two kinds of opinions: direct and comparative.

There are also two kinds of opinions: Explicit and Implicit.

Polarity classification

Goal: Classifying a sentence as expressing a positive, negative or neutral opinion

Baseline Algorithms:

Tokenize
- Christopher potts sentiment tokenizer
- How to handle negation?
  - Das and Chen: add NOT_ 然后把很多NOT_like 这种词也变成一个feature
- All words/Only adj ? [It seems all words is better]
Feature Extraction
Classification:
- Naive Bayes
  - $\frac{count(w,c)+1}{count(c) + V}$
  - Binarized / (boolean feature) multinomial naive bayes.
    - Word occurance matter more than word frenquency
    - Prior: $p(c) = \frac{doc\ with\ words}{all\ docs}$ . Prob: Remove duplicate in each doc and then same as above.
- MaxEnt
- SVM

正负词汇包：

The Genearal Inquiry 包含了正面以及负面的词汇
LIWC 单次分类 http://liwc.wpengine.com/
MPQA 单次分类还包含了程度http://people.cs.pitt.edu/mpqa/subj_lexicon.html
Bing Liu Opinion Lexicon
SentiWordnet

我们不能单纯的用raw count。eg. bad这个词出现的10星评论比2星评论多，是因为2星评论本来就很少。我们应该:
1. 用likelihood(ratio) $\frac{Target\ words}{Total\ words}$

scaled likelihood, make them camparable between words

logical negation 也是一个好的feature，更多出现在负面评价里面

除了用别人的词汇包，我们可以自创词汇包：semi-supervised learning of lexicon

Finding aspects or attributes: Target of sentiment：

1. Find all highly frequent phrases
2. Filter rule like: *Occur right after a sentiment word*
3. Supervised learning. 先找到商家对应的类别（比如餐厅），然后在餐厅的常见aspect中做一个classifier判断是哪一类

所以整个流程是:

Extract sentences and phrases
Sentiment classifier: 判断是积极/消极/中性
对于不是中性的评论，我们找出他们的类别
汇总在一起

还有个问题是：Baseline methods assume classes have equal frequencies. 解决办法：

不用accuracy，最好用F-score
Re-sampling. 变为同样样本数
penalize for misclassification of the rare class

对于五分类问题：

Linear / Ordinal regression
Specialized model like metric labeling

Information Exaction

目的：

Find and understand limited relevant parts of texts
Gather INformation from many pieces of texts
NER: Name Entity Recognition

Study Courses 机器学习

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

算法心得上一篇

Hexo心得体会下一篇

机器学习笔记