一、 关于概率的基本概念
离散型随机变量：伯努利分布p(x) = ux(1-u)(1-x)、二项分布P(X=k) = Cnkuk(1-u)n-k、
连续型随机变量：∫f(x) dx = 1。高斯分布(正态分布)、指数分
累计分布函数CDF: 随机变量X取值小于等于x的概率cdf(x) = P(X≤x)
联合概率分布(Joint Probability Distribution)、条件概率(Conditional Probability)
采样(Sampling)：给定一个概率分布p(x)生成满足条件的样本。
直接采样：均匀分布Uniform[0,1),xt+1=(axt+c) mod m线性同余发生器
逆变换采样：对[0,1]均匀采样，然后x = cdf-1(y)
期望(Expectation)：均值EX =∫xf(x)dx, EX =1/n Σxp(x)
大数定律(Law of Large Numbers)：样本均值和真实均值充分接近，均值收敛于期望值。
二、 机器学习定义
1. 机器学习≈自动构建一个映射函数
现实世界的问题都比较复杂：构造很多训练样本，让计算机自己找到规则。
2. 如何构建映射函数？从大量数据中学习规律。–function
x(reprentation) ? y(label); （注意区别：建立两个两边之间的关系—拟合问题）
y = g(x)关系不知道。服从的Pr(x,y)分布也不知道。
① 采样x(1)y(1); x(2)y(2); …; x(n)y(n). training data。
② 构造假设空间(函数族)，f1(x); f2(x); …; fk(x). 挑选最优的f*(x).
③ f*(x)是希望可以应用到位置的数据上，而拟合是希望可以适合更多的训练数据。
3. 机器学习(Machine Learning, ML)
是指从有限的观测数据中学习（或“猜测”）出具有一般性的规律，并利用这些规律对位置数据进行预测的方法。
三、 机器学习类型
回归问题（Regression）：输出是一个连续值。票房预测、股价预测、房价预测
分类问题（Classification）：手写数字识别、人脸检测、垃圾邮件检测Spam Detection
图像聚类（Clustering Images）:无监督学习问题，只有x没有y。
强化学习：通过与环境进行交互来学习。AlphaGo、
典型监督学习问题：回归输出连续值，分类输出离散值。
典型无监督学习问题：
四、 机器学习的要素
四个基本要素：数据、模型、学习准则、优化算法。
1. 数据
有x, y则是监督问题，y是连续的则是回归问题，y是离散的则是分类问题。只有x则是无监督问题。
从原始数据中怎么抽取特征，就是特征抽取问题。如果自动抽取特征的话就是一个表示学习的问题。
2. 模型
首先要给定一个假设空间，然后选择一个最优的模型。能够建模就是预测x和y之间的关系。
3. 学习准则
有一个准则来判断学习的模型是好是坏。
4. 优化算法
给定一个准则后可以用一些数学优化的算法去学到我们期望的模型。
★模型：（以回归为例）
线性模型f(x;θ) = wTx+b;
非线性模型f(x;θ) = wTΦ(x)+b; 如果Φ(x)为可学习的非线性基函数，f(x,θ)就等价于神经网络。
★学习准则
一个好的模型应该在所有去之上都与真实映射函数一致：|f(x;θ )-y| < ε
① 损失函数（Loss Function）是一个非负实数函数，用来量化模型预测和真实标签之间的差异。L(y, f(x;θ))
比如平方损失函数1/2(y-f(x;θ))2。所以就希望找一个θ能让损失函数更小。
② 期望风险（Expected Risk）：R(θ)=E(x,y)~pr(x,y)[ L(y, f(x;θ))]. pr(x,y)是真实的数据分布，L是损失函数。pr未知，所以R(θ)没法儿算 --> 大数定律来逼近。
③ 经验风险（Empirical Risk）: RDemp (θ)=1/N·Σ L(y(n), f(x(n);θ))。用经验风险来逼近期望风险。
经验风险最小化（Empirical Rick Minimization, ERM）寻找一个参数θ*，使得经验风险函数最小化。
θ* = arg min RDemp (θ). --> 优化问题
★最优化问题min f(x)
凸优化问题（Convex）、非凸优化问题(Non-convex)：极值点导数等于0.
梯度下降法（Gradient Descent）：搜索步长α也叫学习率（Leaning Rate），需要人为选择，与θ不同。
随机梯度下降法（Stochastic Gradient Descent, SGD）：只选取一个样本，无法利用并行计算的资源。
小批量（Mini-Batch）随机梯度下降法。
五、 泛化与正则化（核心）
机器学习更关注的不是训练集上的错误率，而是整个数据包括测试集上的错误率。也就是期望风险。
1. 泛化误差
期望风险与经验风险的插值。比如一个模型，经验风险特别低，期望风险特别高，那么泛化误差也就特别大。就是出现了过拟合。
所以机器学习的目标就是经验风险比较低的，同时泛化误差也比较低。
2. 优化
经验风险最小。正则化：降低模型复杂度。
正则化（Regualrization）：所有损害优化的方法都是正则化。降低泛化误差的方法。
增加优化约束、干扰优化过程
六、 线性回归
1. 回归（Regression）
训练集：{x(n), y(n)}n=1,…, N
回归问题：x(n)∈RD, y(n) ∈R, 求解x, y之间的映射关系。y=f(x;θ)
2. 线性回归（Linear Regression）
3. 经验风险最小化（ERM）
训练集D上的经验风险
矩阵微分
4. 结构风险最小化（Structure Risk Minimization, SRM）
特征之间存在共线性，XXT不可逆：特征之间存在冗余性。
经验风险基础上加上一个正则化项： 
令其最小化得到： (岭回归方法)
七、 多项式回归
曲线拟合（Curve Fitting）
多项式曲线拟合（Polynomial Curve Fitting）：如何选择多项式的次数。
损失函数
控制过拟合：正则化（Regularization）、增加训练样本数量
八、 线性回归的概率视角
1. 从概率角度来看线性回归
假设标签y为一个随机变量，其服从以均值为wTx，方差为o2的高斯分布
2. 似然函数（Likelihood）
似然函数时关于统计模型p(x;w)的参数w的函数
概率p(x;w)是描述固定参数w时随机变量x的分布情况
似然p(x;w)则是描述一直随机变量x时不同个参数w对其分布的影响。
线性回归中的似然函数：参数w在训练集D上的似然函数
最大似然估计（Maximum Likelihood Estimate, MLE）：找到一组参数w使得似然函数p(y|X;w,o)最大，偏导等于零。（等于经验风险最小解）
3. 贝叶斯的视角
贝叶斯学习：将参数w也看作随机变量。目标：给定一组观测数据X，球参数w的分布p(w|X)，也称为后验分布（Posterior）。
后验、似然、先验的关系：正比。
九、 模型选择与“偏差-方差”分解
如何选择一个合适的模型？ 模型选择：能力过强容易过拟合，限制模型复杂度容易欠拟合。在模型选择的时候测试集不可见。模型选择（Model Selection）
1. 引入验证集（Validation Set）
将训练集分为两个部分：训练集Training Set和验证集Validation Set。在训练集上训练不同模型，选择在验证集上错误最小的模型。
–> 数据稀疏问题：交叉验证（Cross-Validation），训练集分为S组，每次使用S-1组作为训练集，剩下1组作为验证集。取验证集上平均性能最好的一组。
2. 赤池信息量准则（Akaike Information Criterion, AIC）、贝叶斯信息准则（Bayesian Information Criterion, BIC）
3. 偏差-方差分解（Bias-Variance Decomposition）
模型复杂度与期望风险之间的关系
实际训练一个模型时，不同训练集会得到不同的模型。以平均性能来评价。
偏差bias,自身方差，噪声
十、 常用定理
① 没有免费午餐定理（NFL）：没有适用于所有问题的算法
② 丑小鸭定理（Ugly Duckling Theorem）：丑小鸭与白天鹅之间区别与两只白天鹅之间区别一样大。（表示特征）
③ 奥卡姆剃刀原理（Occam`s Razor）：如无必要，误增实体。简单的模型能用就不用复杂的。
1. 归纳偏置（Inductive Bias）
：很多学习算法经常会对学习的问题做一些假设，这些假设称为归纳偏置。（不一定成立，但是对学习可能有帮助）
最邻近分类器中，假设特征空间中一个小邻域大部分样本属于同一类。
朴素贝叶斯分类其中，假设每个特征的条件概率是相互独立的。
归纳偏置在贝叶斯学习中也成为先验（Prior）。
2. PAC学习
（Probably Approximately Correct, 可能近似正确）
根据大数定律，当训练集大小|D|趋于无穷大时，泛化误差趋于0，经验风险趋近于期望风险。
3. 样本复杂度
