机器学习/统计学习基本概念概述

写在前面的话：这是我开通博客后的第一篇随笔，主要是在第二次阅读李航《统计学习方法》感觉有必要记录和整理之前的笔记，因此写在这里，以便查阅和分享，详细内容还需认真读书才行。我才疏学浅，不及入门，如有不正确的地方请读者或批评或指正或建议，我必改之！其后还会整理出本书的所有内容！

1 统计学习（statistical learning）

概念：计算机基于数据构建概率统计模型并运用模型对数据预测和分析的一门学科，又称statistical machine learning
特点：以计算机和网络为平台，以数据为研究对象，以学习为目的，以方法为中心，对数据构建模型model进行预测和分析，假设同类数据具有统计规律，通过学习使得计算机能够智能化，以及多种统计方法（supervised/unsupervised/semi-supervised/reinforcement learning），统计学习的三要素是模型model，策略strategy，算法algorithm即模型的假设空间，模型选择的策略，以及模型优化的学习算法。
监督学习方法主要包括分类，标注和回归问题，在自然语言处理，信息检索，文本数据挖掘等领域有着广泛的应用。

2 监督学习

任务：学习一个model，使得model能够对给定的input，得出相应的output来对此输入做出合理的预测。
一些概念：
输入/输出/空间：指的是相应输入输出的集合；一般输出空间小于输入空间
其中对于输入空间，每一个具体的输入是一个实例（instance），它由特征向量组成（many features）构成特征空间feature space，每一维对应一个feature。注意：概念上输入空间和特征空间是不同的，输入空间可以不做处理就当做model的输入，但是有些负责输入需要转化为特征空间的合理vector，于是二者不能混淆，也就是preprocessing，预处理。
区分：
回归：输入，输出均为连续（numinal value）；分类：输出为离散（norminal value），标注：输入输出均为变量序列seq。
联合概率分布P(X,Y)——假设存在，且training data和testing data均为P产生且独立分布的，这是一个基本假设。
假设空间：监督学习目的在于学习一个由输入到输出的映射，这个映射是model，学习目的就是找最好的model。而model是映射的集合，这个集合叫做假设空间Y=f(X)

3 三要素

3.1 model

在监督学习过程中，模型就是所要学习的条件概率分布或者决策函数。hyperthesis space是包含所有可能的条件概率分布或决策函数，假设空间的模型一般有无穷多个。

theta是参数

3.2 strategy

按照什么样的准则学习或者选择最优的模型。

loss function或cost function
用来度量预测错误的程度L(Y,f(X)),故越小越证明model正确率越高。
常见损失函数：0-1，平方，绝对，对数损失函数。
一般会求损失函数的期望：叫做risk function或expected loss，是f(X)关于联合分布P(X,Y)平均意义下的损失。

学习的意义就是选择期望风险最小的模型。由于P(X,Y)是未知的，R不能直接计算，反过来讲若P已知，则不需要学习，training的意义不必要，这样一来，根据期望最小模型，要用到联合分布，而联合分布P又是未知的，监督学习就成为一个病态问题（ill-formed problem）
若给定一个training data，模型f(X)关于训练数据集的平均损失称为经验风险empirical risk or loss

根据大数定理，当样本容量N无穷大时，经验风险就趋近于期望风险。 但是现实中训练集数目有限，这就关系到经验风险最小化和结构风险最小化。
经验风险最小化和结构风险最小化
经验风险最小化：empirical risk minimization ERM

在假设空间，损失函数，训练集确定时，样本容量足够大的时候ERM保证很好的学习策略，比如最大似然估计：当模型是概率分布，损失函数是对数损失函数，ERM就是最大似然估计。
但是，当样本量不够大时，可能会产生过拟合的问题
结构风险最小化：structural risk minimization：就是为了防止过拟合而提出的策略。等价于regularization正规化。即，在ERM基础上加上表示模型复杂度的正规项或者叫做penalty term 惩罚项

J(f)是model的复杂度，定义在假设空间的泛函，model f越复杂，复杂度就越复杂，反之成立，that is，复杂度表示了对复杂模型的惩罚。lambda>=0是系数，用来权衡empirical risk和model complexity。SRM之后的越小表示预测越精确。比如最大后验概率估计， MAP。
SRM将学习最优模型的过程转化为求解

总之，supervised learning 变成寻找ERM和RSM目标函数最优化问题。

3.3 algorithm

指的是最优化过程的具体计算方法，如果没有显式的解析解就要寻找全局最优解。

4 模型评估和模型选择

4.1 训练误差和测试误差training/testing error

给定loss function，训练模型是f hat：
training error：

N为训练集
testing error：

N'是测试集
testing error反应了model对未知数据的预测能力，越小表明能力越强，称为泛化能力（generalization ability）

4.2 overfitting and model selection

当假设空间含有不同复杂度的model(eg.含有不同的参数)时,就需要选择更好的model。若在训练集上表现很好在测试集上表现很差说明model已经overfitting 过拟合

5 模型选择方法：regularization and cross validation

这里主要讲解防止过拟合的方法

5.1 正规化regularization

在上节经验风险基础上加上regularizer or penalty term。此项一般模型的是复杂度的单调递增函数，模型越复杂，此项就越复杂（term就越大），可以是模型参数量的范数

正规项（或者叫调整项）有不同的形式，在回归问题中常是参数量的L2范数：

也可以是L1范数，

regularization作用是选择与ERM复杂度同时较小的模型。
regularization符合奥卡姆剃须刀原理（Occam‘s razor）：在所有可能选择的model中能够很好的解释已知数据且十分简单的才是最好的model。从贝叶斯估计的角度来看penalty term对应于模型的先验概率，复杂的模型有较大的先验概率简单的model有较小的先验概率。

5.2 交叉验证

若给定的数据集充足，随机的将数据集切成三部分，分别为training set，validation set，testing set（训练集，验证集，测试集），其中，训练集用于训练模型，验证集用于模型的选择，测试集用于最终对学习模型的评估。在学习到不同复杂度的model中，选择对验证集有最小预测误差的model，由于验证集有足够多的数据，对模型选择也是有效的。
但是在实际中，数据集不够多那么提出cross validation，思想是重复使用数据，把给定的数据进行切分，将切分的数据组合为训练集和测试集，在此基础上反复训练，测试以及model selection。

简单交叉验证
将数据随机分为两部分，一部分作为训练集，一部分作为测试集，然后在训练集上对不同参数/条件下的模型训练，得到不同的model，在测试集上评价各个model的testing error，选出最小的一个。
S折交叉验证
S-fold cross validation，随机将数据切为S个互不相交的大小相同的子集，然后用S-1个子集数据训练model，余下的测试model；对可能的选择（model）重复进行，最后对S次评测中平均测试误差最小的model。
留一交叉验证
s-fold cross validation 特殊情况S=N，称为leave-one-out cross validation往往在数据缺乏情况下使用，N为数据集的容量。

6 泛化能力

6.1 泛化误差

常见于用测试误差来评价泛化能力，但是测试集的数据是有限的，很有可能得到的结果是不可靠的。这里试图从理论上对学习方法的泛化能力进行分析。
泛化误差（generation error）定义：本质上就是期望误差，越小代表model越有效。

6.2 泛化误差上界generation error bound

具体来说，比较泛化误差的上界来比较model的优劣
性质：样本容量（capacity）的函数，当样本容量增加时，泛化上界趋于零，越大model越难学，上界越大。
对于binary classifier
期望风险和经验风险：

经验风险最小化函数：

泛化能力：

其中，R是泛化误差（期望风险），Rhat是样本均值（经验风险），e是N的单调递减函数。
总而言之，训练误差R hat 越小，泛化误差R越小

7 生成模型和判别模型

7.1 监督学习的任务

就是学习一个model，应用这个model对给定的输入得到预测的输出。一般形式为决策函数：Y=f(X)，或者条件概率分布P(Y|X)

7.2 监督学习方法：

生成方法（generative approach）对应生成模型（generative model）；判别方法（discriminative approach）对应判别模型（discriminative model）
生成model：由数据学习联合概率密度分布P(X,Y)，然后求出条件概率分布P(X,Y)作为预测的model，即生成模型

之所以称为生成方法，是因为model给定输入X产生Y的关系。典型的生成model有Naive Bayes,Hidden Markv Model判别model：直接学习决策函数或者条件概率分布，作为预测的model，判别方法更关心的是给定输入X，应该预测什么样的输出Y。典型的判别model，k近邻法，感知机，决策树，逻辑回归，最大熵，SVM，Boosting，条件随机场。

7.3 二者比较

生成模型，生成方法还原出联合概率密度P(Y|X)，判别model不行；学习效率高，收敛快，即样本容量增加的时候，能更快的收敛到真实model；存在隐变量（latent variable）时，可以用生成方法而不能用判别方法。
判别模型，判别方法直接学习条件概率或者决策函数，直接面对给定X预测，学习准确率更高，因为直接使用条件概率或决策函数，可以对数据进行各种程度的抽象，定义特征并使用，简化学习问题。

8 分类问题classifier

分类是supervised learning的核心问题，定义是输出变量Y是有限离散值，输入变量X可以是离散也可以是连续。

8.1 简述

分类过程分为学习和分类两个过程，学习过程就是training过程，根据已知数据利用算法学习一个分类器；分类是对新的输入实例x进行预测分类。

8.2 性能指标：准确率accuracy

定义：给定测试集，分类器正确分类的样本数/总样本数。
二类分类问题Binary class：Precision and recall（精确率和召回率），通常关注类为正类，其他类统称为负类。
预测分为四种情况：
TP——将正类分为正类；FN——将正类分为负类；FP——将负类分为正类；TN——将负类分为负类；
精确率定义：P=TP/(TP+FP);
召回率定义：R=TP/(TP+FN);
调和均值F1：P和R都高时，F1也会高

9 标注问题Tagging

9.1 概述

标注tagging是分类问题的推广也是结构预测的简单形式。标注问题的输入是一个观测序列，输出是一个标记序列或状态序列。在于学习一个model，对观测序列给出标记序列作为预测。

9.2 过程

标记问题分为学习和标记两个过程：学习是给定训练集得到一个条件概率分布:

其中，X为所有可能的观测，Y为所有可能的标记序列，一般n远远小于观测序列的长度，具体例子（一个截图）

注意：虽然标记的个数可能是有限的，但是其组合所标记序列的个数是依序列长度呈指数增长的。

9.3 评价指标

与分类一样，准确率，精确率，召回率

9.4 应用

常用的统计方法为：隐马尔可夫模型，条件随机场。
在信息提取，自然语言处理广泛应用，比如词性标注（part of speech tagging）

10 回归问题Regression

10.1 概述

用于预测输入和输出之间的关系，especially，当输入变化时，输出随之变化。回归模型表示的是输入变量到输出变量之间的映射的函数，等价于函数拟合。
按照输入变量的个数可以分为一元回归和多元回归；按照输入和输出的关系分为线性回归和非线性回归。
常用的loss function为平方损失函数，在此情况下，可以由最小二乘法least square求解。