[读书笔记] PRML Ch1 Introduction

主题1： 模式识别与机器学习的简介

模式识别与机器学习的关系
模式识别源自工程，是一类问题(problem)；机器学习源自数学，是一类方法(methodology)。对于一个具体的模式识别问题，可以用handcrafted rule-based的方法去求解，但是更复杂的PR问题往往采用机器学习的方法。

机器学习的分类
按照学习模式的不同，machine learning一般可以分成4类：
Supervised Learning
training set中全部输入都带有target value的称为supervised learning。这类学习的目标是发现input变量和target变量之间的关系。按照target value，supervised learning又可以分成两类问题：如果target value是离散变量，称为classification；如果是连续变量，称为regression。
Unsupervised Learning
输入变量全不带target value的称为unsupervised learning。这类学习的目标是发现输入变量间的内部联系。按照具体的内部联系类型，unsupervised learing又可以分成多种问题，如，clustering,density estimation,visualization。
Semi-supervised Learning
输入变量有的带target value，有的不带的称为semi-supervised learning。其实书中并没有直接提到semi-supervised learning...
Reinforcement learning
这类学习是在supervised learning的基础上，允许机器自行选择training data；同时，training在获取信息的同时也会带来cost或loss，从而引发一个tradeoff。

机器学习的基本流程
最基本的machine learning过程是：
1. 确定模型类型
2. 确定模型复杂度（即自由参数个数）
3. 确定每个模型的所有参数值
4. 最后在模型间比较选择一个最好的，也称model selection

trainning model一般是指一个或一组解析表达式，通过它可以用解析方法去表达知识或直接优化决策。根据泛化能力不同，trainning model可以只面向第3步，也可以同时涵盖所有4个步骤。对于不能表达为trainning model的部分，要么通过conputational算法去枚举或比较，要么对具体application做模型假设。

Overfitting 与 Model Selection
overfitting的具体含义书中描述的并不清晰，大体是指这么一种现象：有的时候模型在training set上误差很小，但是在非training set上误差却很大。

如果算法存在overfitting 现象，传统上要从training data中选择一个子集（称为validation set），并基于validation set去做model selection。

validation data和test data的区别在于：前者可以是在另一次run中的training data的一部分，不同run对于同一组data采取不同的training-validation划分；而后者根本不用于training的过程，通常是用于最终的实验。

validation的缺点有二：
1.validation占用了额外的training数据，这对数据稀少的application影响尤为严重。cross-validation技术用于缓解这一缺陷。它轮流从training set中选择小部分数据做validation set，并最终把多轮结果combine起来。但cross-validation引入多轮validation，增加了计算量。
2.由于validation的存在，training model无法根据training data解析地进行模型比较。当需要枚举比较的模型复杂度参数变多时，validation的计算复杂度指数上升。

一种“消除”overfitting现象的方法是向training model中加入information criterion。理想情况下，由于不存在overfitting从而可以避免validation过程；现实中，加入IC的model结果往往比validation出来的要好。但是，多数Information Criterion缺少理论解释的支持。

Regularization(shrinkage)是另一类“控制”overfitting现象的方法。它也向trainning model加入一个compensation term，然后通过一个complexity parameter来调整regularization的程度，从而控制overfitting的程度。从客观上，regularization可以避免由于模型过于flexible而train出来的参数过大的“畸形模型”，但另一方面过量的regularization会降低模型的effective complexity，这同样无法得到好的model。因此，为了选择一个最优的regularization度，仍然需要validation的过程。Regularization的作用在于，complexity parameter往往是连续变量，因此可以表达出用离散个数个模型参数所无法表达的模型，从而增加模型的泛化能力。另一个好处是，带regularization的validation是对同一套解析式内的不同参数进行比较，相比于不同解析式间的比较，计算量较小。

多维困境

主题2： 概率论支持
概率论提供了对随机事件进行描述和分析的框架。数理统计则通过“随机采样”来构造一系列随机变量，进而通过概率论提供的理论框架去反推总体的特征

基本概念：随机事件概率、随机变量、离散变量的概率分布、连续变量的概率密度函数、条件概率（及分布、密度函数）、边缘概率（及分布、密度函数）、互斥、独立、线性相关、期望、方差、协方差

运算法则：条件概率公式、全概率公式、随机变量的函数的概率密度函数计算（Jacobi factor使非线性函数的概率计算不同于simple function）

概率模型：本章只简单介绍了高斯分布，更多的模型用整个第二章来详细介绍

Maximum Likelyhood Estimation:frequentist学派的经典参数估计准则，假设合理，计算方便。但其对高斯分布总体的方差估计的期望值偏小，这是由于需要用总体期望的估计量回代求解导致的。

Bayesian理论：bayesian理论把一切未知量都看作随机变量，并通过概率法则去求其后验分布。它的本质是把概率解释为主观上的不确定性，从而扩展了其应用范围。bayesian理论的优点是无需借助额外的“准则”，局限在于计算复杂。近些年Monte Carlo等sampling类方法和近似推导方法使得bayesian理论的应用变得广泛。

主题3： 决策论支持
决策空间、loss function、
决策准则：minimize loss expectation
三类决策方法：generative model、discriminitive model、discriminant function

主题4： 信息论支持
entropy的数学性质：运算法则、differential entropy、conditional entropy、relative entropy、mutual information
entropy的信息量解释：决定最小编码长度
entropy的统计学解释：给定期望方差时，高斯分布的entropy最大；而对于高斯分布而言，方差越大entropy越大。
KL-divergency(relative entropy)一定大于等于0,这说明我们使用任何一个不同于真实分布的分布函数都会得到更差的结果。同时，依据relative entropy进行推导的方法同MLE方法在形式上是一致的。

主题5： Case Study - 一元多项式回归
如果忽略变量关系的uncertainty，一元多项式回归等价于数值计算领域的多项式曲线拟合问题，此时通常采用Root-Mean-Square为loss准则来优化参数。

如果假设目标变量在每个点处都服从独立同方差的正态分布，而其期望值是输入变量的多项式函数，那么多项式拟合便又等价于概率论中的参数估计问题，而RMS准则恰好和frequentist学派的极大似然准则（Maximum Likelihood）一致。
然而，这个数学模型存在overfitting问题，这是由于模型复杂度相比于输入数据的规模过大引起的（从数值分析角度看，当多项式阶数等于输入数据项数时，拟合变成插值，此时loss一定可以优化至0）。