机器学习系列之coursera week 1 Introduction 以及模型评估
目录
前言
笔者最近在听coursera机器学习的课程，每听完一周的课会在此写一篇复习，以及对课程知识的一些补充
1.coursera week 1 review
1.1 Introduction
一. welcome
Machine Learning（ML）
-grew out of work in AI
-new capability for computers
Examples:
-Database mining
-Applications can't program by hand（不能通过手工写出来的程序）, e.g. handwriting recongnition
-self-customizing program
-understanding human learning
二. what is ML
-Arthur Sumuel(1959): Feild of study that gives computers the ability to learn without being explicitly programmed.
-Tom Mitchell(1998): well-posed learning problem: A computer program is said to learn from experience E with respect to some task T and som performance measure P, if its performance on T, as measured by P, improves with experience E.
（当且仅当，有了经验E后，通过P评判，程序在完成T时，性能有所提升）
ML algorithms
-supervised learning
-unsupervised learning
other: Reinforcement learning, recommender systems
三. supervised learning
def: 部分数据有正确的标签（值），尽可能的去拟合它们，并对新的数据做出预测。可分为：
回归问题：输出连续值
分类问题：输出离散值
四. unsupervised learning
def： 未给出数据分类也不知道最后结果变成什么样，对数据自动学习并发现其中的结构。可分为：聚类和鸡尾酒party算法
1.2 Model and cost function
一. Model representation
m = num of training examples
x's = features
y's = 因变量
How do we represent h?
e.g
三. Cost function
Using a function named cost function to measure the accuracy of your hypothesis function
Hypothesis:
θi: model parameters
how to choose θi?
Idea: choose θ0，θ1 so that h(x) is close to y for our training examples
即：
令：
J被叫做cost function
Hypothesis:
parameters： θ0, θ1
cost function：
goal:find
h(x): for fixed θ0, θ1, this is a function of x
J: function of the paramter θ0, θ1
其图形如下:
（引自coursera machine learning week 1 cost function-intution II）
其等值线图如下：
（引自coursera machine learning week 1 cost function-intution II）
等值线图相当于3d图的投影，其上每个椭圆表示J相同的点的集合。
1.3 Parameter learning
一. Gradient descent
（引自coursera machine learning week 1 Gradient Descent ）
function: J(θ0, θ1)
goal: find
outline:
1. start with some θ0, θ1
2. keeo changing θ0, θ1 to reduce J(θ0, θ1) until we hopefully end up at a minimum
Gradient descent algorithm:
correct: simultaneous update. (同时更新)
incorrect:
simplified: J(θ1)
（引自coursera machine learning week 1 Gradient Descent intution）
for α:
if α is too small, gradient descent can be slow.
if α is too large, gradient descent cant overshoot the minimum. It may fail to converge or even diverge
Gradient descent can converge to a local minimum, even with the learning rate α fixed. Beacuse as we approach a loal minimum, gradient descent will automatically take smaller steps, so , no nedd to decrease α over time.
二. Gradient descent for linear regression
Gradient descent algorithm:
linear regression model:
推导有：
Gradient descent algorithm:
update θ0, θ1 simultaneously
当损失函数为凸函数时，梯度下降可达到全局最优，上述算法又叫：
batch gradient descent
batch: each step of gradient descent uses all the training examples
到这里week 1 的内容已经全部复习完，下面参考西瓜书补充模型评估
2.模型评估
2.1 经验误差和过拟合
通常我们把分类错误的样本数占样本总数的比例称为“错误率”（error rate），即如果在m个样本中有a个样本错误，则错误率E=a/m；相应的，1 - a/m称为“精度”（accuracy）。更一般的，学习期的实际预测输出与样本的真实输出之间的差异称为“误差”（error），学习器在训练集上的误差称为“训练误差”或“经验误差”，在新样本上的误差称为“泛化误差”，显然我们希望得到泛化误差小的学习器，然而实际上，我们事先并不知道新样本是什么样的，实际能做的是努力使经验误差最小化。
我们实际希望的，是在新样本上能表现得很好的学习器。为了达到这个目的，为了达到这个目的，应该从训练样本中尽可能学出适用于新样本的的普遍规律，这样才能在遇到新样本时做出正确判断。然而，当学习器把样本训练得太好了的时候，很可能已经把训练样本本身的一些特点当作了所有潜在样本都会具有的一般性质，这样会导致泛化性能降低，这种现象在机器学习中叫做过拟合（overfitting），相对的是欠拟合（underfitting），是指对训练样本的一般性质尚未学好。
欠拟合比较容易克服，如，在神经网络训练中增加训练次数；而过拟合很难解决，是目前机器学习面临的障碍之一，各类算法都有一些针对过拟合的措施，来缓解过拟合。
2.2 评估方法
通常，我们可通过实验测试来对学习器的泛化误差进行估计，因此需要一个测试集（testing set）来测试学习器对新样本的判别能力，然后将测试集上的误差作为泛化误差的近似。
2.2.1 留出法
留出法（hold-out）直接将数据集D划分为两个互斥的集合，其中一个集合作为训练集S，另一个作为测试集T。在S上进行训练，在T上进行测试。
需要注意的是，训练/测试集的划分要尽可能保持数据分布的一致性，避免因数据划分过程引入额外的偏差而对最终结果产生影响，例如在分类任务中至少保持样本类别比例一致。如果从采样的角度看数据集的划分过程，则保留类别比例的方法叫做分层抽样。
需要注意的是，单次使用留出法得到的估计结果往往不够稳定，在使用留出法时，一般要采用若干次随机划分，重复进行实验评估后取平均值作为最终结果。测试集至少含30个样例。
2.2.2 交叉验证法
交叉验证（cross-validation）先将数据集D划分为k个大小相似的互斥子集，D1，D2.....Dk。每个子集都尽可能保持数据分布的一致性，即从D中分层采样得到。每次用k-1个子集作为训练集，剩下的那个做测试集，这样就可以进行k次实验，最终结果取这k次实验的平均值。通常把交叉验证法称为K折交叉验证（k fold cross-validation），如图1。
图1
k折交叉验证通常要随机使用不同的划分重复p次，最终结果是这p次k折交叉验证结果的均值，如10*10折交叉验证。
假设数据集D有m个样本，令k=m，则得到交叉验证的一个特例，留一法（leave-one-out，简称LOO）。留一法的评估结果往往比较准确，但是在数据集比较大的时候计算成本太高。
2.2.3 自助法
自助法（bootstrapping），直接以自助采样法（bootstrapping sampling）为基础。给定包含m个样本的数据集D，我们对它进行采样产生数据集D'：每次随机从D中挑选出一个样本，将其复制放入D'中，然后将该样本放回D中，使得该样本在下次采样时任然可以被采到，重复这个过程m次后，就得到了包含m个样本的D'。显然，在D'中会有一部分样本重复出现，而另外一部分样本不出现。可以做个估计，样本在m次采样中始终不被采到的概率为(1 - 1/m)^m，取极限得：
即通过自助采样，原始数据中有约36.8%的样本未出现在D'中。于是我们将D'作为训练集，将D\D'作为测试集，这样的测试结果称为“包外估计”。
自助法在数据集较小，难以有效划分训练集，测试集时很有用；还能从原始数据集中产生多个不同的训练集，这对集成学习很有用，但是自助法产生的数据集改变了原始数据集的分布，会引入偏差。
2.2.4 调参与最终模型
大多数学习算法都有一些参数需要设定，参数配置不同，学得的模型的性能往往有显著差别。对参数进行设定的步骤称为参数调节，简称调参（parameter tuning）。
现实中的做法是，对每个参数设定一个范围和变化步长来进行选择。显然，这样的参数往往不是最佳的选择，但这是计算开销和性能之间进行折中的结果。
另外需要注意的是，我们通常把学得模型在实际使用中遇到的数据称为测试集，为了加以区分，模型评估与选择中用于评估测试的数据集常称为验证集。例如，在研究对比不同算法的泛化性能时，我们用测试集上的判别效果来估计模型在实际使用时的泛化能力，而把训练数据另外划分为训练集和验证集，基于验证集上的性能来进行模型选择和调参。
2.3 性能度量
对学习器的泛化性能进行评估，不仅需要有效可行的实验估计方法，还需要衡量模型泛化能力的评价标准，这就是性能度量。
在预测任务中，给定样例集，其中yi是xi的真实标记。要估计学习器f的性能，就要把学习器结果f(x)与y进行比较。
回归任务最常用的性能度量是“均方误差”（mean squared error，MSE）
下面主要介绍分类中的性能度量。
2.3.1 错误率与精度
错误率是分类错误的样本占样本总数的比例，精度则是分类正确的样本占样本总数的比例。对于样例集D，错误率为
精度为
2.3.2 查准率，查全率与F1
错误率和精度虽常用，但并不能满足所有任务需求。以西瓜问题为例，若我们关心“挑出来的西瓜中有多少比例是好瓜”，或者“所有的好瓜有多少比例被挑出来”，错误率就不够用了，常用查准率（precision）和查全率（recall）度量。
对于二分类问题，可以将样例根据真实情况与学习器预测类别的组合划分为真正例（true positive，TP），假正例（false positive，FP），真反例（true negative，TN），假反例（false negative，FN），显然有TP+FP+TN+FN=m。分类混淆矩阵（confusion matrix）如图2：
图2
查准率P与查全率R分别定义为：
注：查准率：预测结果的正例中，真正例所占比例；查全率：真实情况正例中，真正例所占比例。
查准率和查全率是一对相互矛盾的 度量 ，一般来说，查准率高，查全率往往低；而查全率高，查准率往往偏低。
以查准率为纵轴，查全率为横轴作图，就得到了查准率-查全率曲线，简称“P-R曲线”。
其画法如下：对于每个样本，经过学习器学习后会得到一个概率p，如果我们设定阈值t，当p>=t时，判断为正例；当p<t时，判断为反例。于是，可以将所有样本经过学习器学习后的概率按从大到小排序。首先，我们将阈值设为最大，即将所有的样本判为反例，分别计算（R，P），然后依次将每个概率pi设为阈值，并更新混淆矩阵，计算（R，P），最后得到的图即为P-R曲线，图3。
图3
若一个学习器的曲线完全被另一个包住，则可以认为后者优于前者。但如果发生交叉，则一般难以判断谁好谁坏，一种方法是比较曲线下面积（AUC），如图2；另一种方法是比较平衡点（Break-Even Point，BEP），平衡点即“查准率=查全率的点”，即做一条直线P=R，与曲线相交的点即是，平衡点大的优于平衡点小的。
但是BEP还是过于简单，更常用的是F1度量：
F1是基于查准率和查全率的调和平均，即：
在一些情况下，对查准率和查全率的重视程度不一样。F1度量的一般形式----Fβ：
其中β>0度量了查准率和查全率的相对重要性。β=1是退化成标准F1；β>1是查准率的影响更大；β<1时查全率的影响更大。
如果想在n个二分类混淆矩阵上综合考察查准率和查全率，一种做法是现在各个混淆矩阵上计算出所有P和R，再计算平均值，这样就得到了宏查准率（macro-P），宏查全率（macro-R），宏F1（macro-F1）：
另外一种做法是，对各个混淆矩阵对应元素进行平均，得到，再基于这些平均值得到微查准率（micro-P），微查全率（micro-R），微F1（micro-F1）：
2.3.3 ROC与AUC
ROC全称“受试者工作特征”（Receiver operating characteristic）曲线，它可以阐明一个二分类学习器，在阈值确定的情况下，的诊断能力，它是从一般情况下泛化性能好坏的角度出发研究学习器泛化性能的有力工具。
ROC曲线以真正率（true positive rate，TPR）为纵轴，假正率（false positive rate，FPR）为横轴，其中
注：TPR，在真实情况的正例中，真正例占的比例；FPR，在真实情况的反例中，假正例占的比例。
其画法有两种，一种与上面提到的P-R 曲线画法一样，另一种是：给定m个正例和n个反例，根据学习器预测结果对样例进行排序，先将阈值设为最大，求出TPR和FPR，然后依次将每个样例的预测值作为阈值，设前一个点的坐标为（x，y），若当前样例为真正例则其坐标为（x，y+1/m）；若当前为假正例，则其坐标为（x+1/n，m）。最后可得到ROC曲线，图4。
注：m=TP+FN，n=FP+TN
图4
若一个学习器的ROC曲线被 另一个包住，则认为后者性能优于前者。若发生交叉，则需要比较ROC曲线下面积，AUC（Area Under ROC Curve），其估算为：
形式化的看，AUC考虑的是样本预测的 排序质量，因此它与排序误差与紧密联系，令D+和D-分别表示正，反例集合，则排序损失为：
即考虑每一对正，反例，若正例预测值小于反例预测值，记一个罚分，若相等，记0.5个罚分。其与AUC的关系为：
到这里，这篇博客就写完了，第二节思路是按西瓜书来的。
参考
西瓜书