发表于 | 分类于 ，

第一周

1.1 训练,验证,测试集

1.训练,验证,测试集 数据一定需要同分布
2.训练,验证,测试集 能够更好的衡量偏差和方差

1.2&1.3 偏差,方差(Bias/Variance)

1.偏差,方差最终的值都是基于人眼的,如果人眼误差也比较高的话,那么训练测试误差比较高也比较正常
2.训练集,测试集数据来自同分布
3.高方差可以解释为：拟合了数据集中的错误样本和中间的一些活跃数据
4.首先看偏差，偏差可以接受后，然后评估下验证集的性能来评估方差
5.一般可以根据训练，测试cost曲线来判断高偏差或者高方差,具体可以参考我github:正则化以及偏差方差检测

1.4&1.5 正则化

1.解决高方差一般有两种方法：一个是正则化，另外是准备更多的数据
2.L2正则化有时候也称为”权重衰减”，因为在用梯度下降计算参数的时候会在前面乘以小于1的数值
3.疑问：为什么很少使用L2做正则化
3.为什么能防止过拟合？(过拟合的本质就是参数过多，参数过大，维数过高)

  • a.直观上理解当lambda足够大的时候，权重矩阵w接近于0，就把很多隐藏单元给消除了一样
  • b.sigmoid,tanh激活函数的曲线可以发现，当x值在0附件的时候，曲线接近于直线，呈现直线的性质，并不是非直线

1.6&1.7 正则化(Dropout)

1.为了不影响Z[4]的期望值，我们需要用Z[4]a[3]/0.8来修正或弥补我们所需要的那20%
2.在测试阶段不能用dropout，因为我们不需要在测试阶段结果是随机的
3.直观理解Dropout和L2正则比较像
4.不能只依赖任何一个特征，因为都有可能被删除
5.根据过拟合的程度设置keep-prob的值，比如W[1]：7x3，W[2]：7x7,W[3]：7x3,所以W[2]层参数最多，可以设置keep-prob稍小一些，比如0.7，第一层可以设置为1，第一层不应该dropout。
6.过拟合才用Dropout方法，CV上通常没有足够多的数据，所以经常会用到
7.Dropout缺点：使代价函数J不再被明确定义，个人理解因为中间的神经元不确定是否被dropout，所以每次都神经元个数什么的都不一样

1.8 其他正则化方法

1.数据扩展(通过旋转，缩放，裁剪等)
2.early stoping

  • 为什么能工作： 因为随机初始的w值都是比较小的，在刚开始训练的时候也不会很大，在后面迭代次数多的时候，w值就会比较大了，这就会使Loss比较大，这个时候stoping是比较好的
  • 缺点: 如果提早停止了梯度下降，也就停止了J的继续优化，不能得到更小的代价函数J
  • 与正则化lambda比较: lambda会尝试多轮的值，进行选择

1.9 归一化输入

1.标准化:零均值，归一化方差
2.为什么能归一化效果更好

  • a.从Loss效果图分析： 归一化后数据更均匀，可以从任何一点入手进行GD迭代，否则曲线就比较凌乱
  • b.从sigmoid或者tanh的曲线图分析： 归一化后区间在0附件的时候，梯度变化最大的

3.不用Normalize： 如果数据本身就处于相似范围，比如已经是1–2，或者0–1，区别不大：1–100

1.10 梯度消失或爆炸

1.这里只讨论了激活函数的指数级数增长或下降，但它也适用于L相关的导数或者梯度问题，比如另一篇文章梯度问题就是讨论的梯度指数问题

2.见另一篇梯度问题

1.11 神经网络权重初始化

见权重初始化练习：Initialization

In general, initializing all the weights to zero results in the network failing to break symmetry. This means that every neuron in each layer will learn the same thing
初始化参数全部为0的时候，每一层的梯度变化的一样的，有就是每一层学习到的是一样的，就不会有比较好的结果

The cost starts very high. This is because with large random-valued weights, the last activation (sigmoid) outputs results that are very close to 0 or 1 for some examples, and when it gets that example wrong it incurs a very high loss for that example. Indeed, when log(a[3])=log(0)log⁡(a[3])=log⁡(0) , the loss goes to infinity.
Poor initialization can lead to vanishing/exploding gradients, which also slows down the optimization algorithm.
If you train this network longer you will see better results, but initializing with overly large random numbers slows down the optimization.
当随机初始值比较大的时候，最后的输出sigmoid就是0或者1，这个时候如果碰见是0，那么计算lost的时候log(0)就是无限大，所以第一次迭代 Cost after iteration 0: inf
初始化参数过大会使开始训练的时候梯度下降得比较慢，Loss比较大，迭代会比较慢，当然最后也会收敛

Different initializations lead to different results
Random initialization is used to break symmetry and make sure different hidden units can learn different things
Don’t intialize to values that are too large
He initialization works well for networks with ReLU activations.

1.12&1.13 梯度的数值逼近及注意项

1.双边误差比单边误差小
2.误差值如果小于10−7是比较安全的，如果大于10−5就需要多注意下，如果大于10−3那么应该是有bug
3.如果J包含了正则项，那么求梯度D的时候也一定要包含正则项，感觉这个不用担心，因为有正则项的J，用数学公式求梯度函数一定会有正则项
4.Dropout和梯度逼近不能同时使用，个人理解是因为梯度逼近是对最终的真实的J做的梯度逼近，而Dropout国产中个的J′去掉了多个神经元并不是真实的J
5.参考NeuralNetwork中的梯度的数值逼近计算

发表于 | 分类于 ，

聚类任务

  • 在无监督学习中（unsupervised learning）中，训练样本的标记信息是未知的，目标是通过对无标记的训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。此类学习任务中研究最多、应用最广的是“聚类”（clustering）
  • 聚类试图将数据集中的样本划分为若干通常是不相交的子集，每个子集称为一个“簇”（cluster）。
  • 聚类既能作为一个单独的过程，用于找寻数据内的分布结构，也可作为分类等其他学习任务的前驱过程。

性能度量

  • 聚类性能度量亦称聚类“有效性指标”（validity index）
    • 与监督学习中的性能度量作用相似。对聚类结果，我们需通过某种性能度量来评估其好坏；
    • 另一方面，若明确了最终将要使用的性能度量，则可直接将其作为聚类过程的优化目标，从而更好地得到符合要求的聚类结果。
      聚类是将样本集D划分为若干不相交的子集，即样本簇。直观上看，我们希望“物以类聚”，即同一簇的样本尽可能彼此相似，不同簇的样本尽可能不同。换言之，聚类结果的“簇内相似度”（intra-cluster similarity）高且“簇间相似度”（inter-cluster similarity）低。
  • 聚类性能度量大致有两类：
    • “外部指标”（external index）
      将聚类结果与某个“参考模型”（reference model）进行比较；
      • 常用的聚类性能度量外部指标有：
        • Jaccard系数（Jaccard Coefficient，简称 JC）
        • FM指数（Fowlkes and Mallows Index，简称FMI）
        • Rand指数（Rand Index，简称RI）
    • “内部指标”（internal index）
      直接考察聚类结果而不利用任何参考模型
      • 常用的聚类性能度量内部指标有
        • DB指数（Davies-Bouldin Index，简称DBI）
        • Dunn指数（Dunn Index，简称DI）

距离计算

  • 给定样本$x_i=（x_{i1}，x_{i2}；…；x_{in}），与x_j=（x_{j1}；x_{j2}；…；x_{jn}）$
  • 最常用的是”闵可夫斯基距离“（Minkowski distance）
  • p=2时，闵可夫斯基距离即欧氏距离（Euclidean distance）
  • p=1时，闵可夫斯基距离即曼哈顿距离（Manhattan distance）

原型聚类

原型聚类亦称”基于原型的聚类“（prototype-based clustering），此类算法假设聚类结构能通过一组原型刻画，在现实聚类任务中极为常用。

  • 通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示、不同的求解方式，将产生不同的算法
    • 我的理解就是直接通过先假设几个样本就为几类簇，然后再迭代更新
  • k均值算法
    给定样本集$D={x_1，x_2，…，x_m}$，”k均值“（k-means）算法针对聚类所得簇划分$C={C_1，C_2，…，C_k}$最小化平方误差
    • 直观来看，上面式子在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，E值越小则簇内样本相似度越高
      • 其中$\mu_i$，是簇$C_i$的均值向量

  • 学习向量量化
    与k均值算法类似，“学习向量量化”（Learning Vector Quantization，简称LVQ）也是试图找到一组原型向量来刻画聚类结构，但与一般的聚类算法不同的是，LVQ假设数据样本带有类别标记，学习过程用样本的这些监督信息来辅助聚类

    • 和KMeans的区别：
      • LVQ数据样本带有标签
      • 初始化方式不同，LVQ是初始化一组向量，KMeans初始化几个簇点
      • 迭代方式不同，LVQ是循环找到每个样本点和向量簇最近的向量，然后根据该样本点的类别是否和该向量表示的类别是否相同，另该向量靠近或更远离该点

  • 高斯混合聚类
    与k均值、LVQ用原型向量来刻画聚类结构不同，高斯混合（Mixture-of-Gaussian）聚类采用概率模型来表达聚类原型

密度聚类

密度聚类亦称“基于密度的聚类”（density-based clustering），此类算法假设聚类结构能通过样本分布的紧密程度确定。通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。

  • DBSCAN是一种著名的密度聚类算法

层次聚类

层次聚类（hierarchical clustering）试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚合策略，也可采用“自顶向下”的分拆策略。

  • AGNES 是一种采用自底 向上聚合策略的层次聚类算法.它先将数据集中 的每个样本看作一个初始聚类簇，然后在算法运行的每一步中找 出距离最近的两个粟类簇进行合并，该过程不断重复，直至达到预设的聚类簇个数
  • Louvain算法

发表于 | 分类于 ，

决策树一般分为三步：特征划分，树生成，树剪枝

基本概念(特征划分)

熵：表示随机变量的不确定性

  • X是一个取有限个值的离散随机变量，其概率分布为$P(X=x_i)=p_i, i=1,2,..,n$
  • 熵定义为$H(X)=-\sum_{i=1}^np_ilogp_i$
  • 又定义可知，熵只依赖于X的分布，而与X的取值无关

条件熵

  • 条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y 的不确定性，也就是给定随机变量X的条件下Y的条件熵
  • 定义为：$H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)$

信息增益

  • 表示得知特征X的信息而使得类Y的信息不确定性减少的程度
  • 特征A对心里数据集D的信息增益定义为：$g(D,A)=H(D)-H(D|A)$
    • 个人理解为不确定性的减少量

信息增益比

  • 以信息增益作为划分数据集的特征，存在偏向于选择取值较多的特征的问题
  • $g_R(D,A)=\frac{g(D,A)}{H_A(D)}$其中$H_A(D)=-\sum_{i=1}^{n}\frac{|D_i|}{D}log_2\frac{|D_i|}{D}$,n是特征A取值的个数

树生成

就是根据特征选择来区分

  • ID3:使用的信息增益进行特征划分
  • C4.5:使用信息增益比进行特征的划分

树剪枝

  • 生成树一般按照局部最优原则生成，容易过拟合

剪枝（pruning）是决策树学习算法对付”过拟合“的主要手段。

决策树剪枝的基本策略有”预剪枝“（prepruning）和”后剪枝“（post-pruning）

  • 预剪枝是指在决策树生成过程中，对每个节点在划分前进行估计，若当前的划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点
  • 后剪枝是先从训练集生成一颗完整的决策树，然后自底向上的对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点

剪枝处理降低了”过拟合“风险，但也带来了”欠拟合“的风险。

  • 一般情形下，后剪枝决策树欠拟合风险较小，泛化性能往往优于预剪枝决策树
  • 但后剪枝训练开销比未剪枝决策树和预剪枝决策树都要大很多

CART(classification and regression tree)算法

  • CART是在给定输入随机变量X的条件下输出随机变量Y 的条件概率分布的学习方法，分类回归树即可以用于分类，也可以用于回归

CART决策树的生成

  • 回归树：使用平方误差最小化的准则进行特征选择
    • 启发式方法(即随机选择第j个变量和它的取值进行划分),遍历特征和各个特征的取值
  • 分类树：使用基尼指数(Gini index)(和熵类似)
    • 假设有K个类，样本点属于第k类的概率为$p_k$，则概率分布的基尼指数定义为$Gini(p)=\sum_{k=1}^Kp_k(1-p_k)$
    • 如果样本集合D根据特征A是否取某一可能值a被分割为$D_1和D_2$两部分，则在特征A的条件下，集合D的基尼指数定义为$Gini(D,A)=\frac{D_1}{D}Gini(D_1)+\frac{D_2}{D}Gini(D_2)$
      • 基尼指数Gini(D)表示集合D的不确定性
      • 基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性，基尼指数越大，样本集合的不确定性也就越大，这个和熵比类似

CART决策树的剪枝

  • 用验证数据集对已生成的数进行剪枝并选择最优子树，这时是用的损失函数最小作为剪枝的标准

小结

发表于 | 分类于 ，

朴素贝叶斯发学习与分类

  • 基本概念
    • 先验概率分布：$P(Y=c_k),k=1,2..K(c_1,c_2…为类分类标签)$
    • 条件概率分布:$P(X=x|Y=c_k)$
    • 贝叶斯定理：有了先验概率分布和条件概率分布，就能够得到联合概率分布$P(X,Y)=P(Y)P(X|Y)$
    • 后验概率分布：$P(Y=c_k|X=x)$
      • 意义：对给定输入x，通过学习到的模型计算后延概率分布，将后验概率最大的类作为x的类输出
    • 所以基于贝叶斯定理的后验概率:$P(Y=c_k|X=x)=\frac {P(Y=c_k,X)}{P(X)}=\frac {P(Y=c_k)P(X|Y=c_k)}{P(X)}$
    • 基于条件独立性假设的朴素贝叶斯法：
      $P(X=x|Y=c_k)=P(X=x^{(1)},X=x^{(2)}…X=x^{(n)}|Y=c_k)=\prod_{j=1}^{n}P(X=x^{(j)})|Y=c_k$

贝叶斯&朴素贝叶斯法

  • 背景：
    • 贝叶斯决策论（Bayesian decision theory）是概率框架下的基本方法。
    • 假设有N种可能的类别标记，即$y={c_1，c_2，…，c_N}，λ_{ij}$是一个将真实标记为cj的样本误分类为ci产生的期望损失(expected loss），即在样本x上的“条件风险”（conditional rsik）
  • 任务：我们的任务是寻找一个判断准则，以最小化总体风险
  • 解决方法：贝叶斯判断准则
    • 使用贝叶斯判定准则来最小化决策风险，首先要获得后验概率P(c|x)
    • 然而，在现实任务中这通常难以直接获得。从这个角度来看，机器学习所要实现的是基于有限的训练样本尽可能准确的估计出后验证概率P(c|x)。大体来说主要有两种策略:
      • 判别式模型:给定x，可通过直接建模P(y|x)来预测c
      • 生成式模型:先对联合概率分布P（x，c）建模，然后再由此获得P（y|x):
        $P(Y=c_k|X=x)=\frac {P(Y=c_k,X)}{P(X)}=\frac {P(Y=c_k)P(X|Y=c_k)}{P(X)}$(贝叶斯公式)
        • 因为P(X)都是一样的，于是生成式转换为问题：$y=arg maxP(Y=c_k)P(X|Y=c_k)$
  • 朴素贝叶斯分类器
    • 基于贝叶斯公式来估计后验概率P(y|x)的主要困难在于:类条件概率P(x|y)是所有属性(x取值有多个)上的联合概率，难以从有限的训练样本直接估计而得。
    • 为了避开这个障碍，朴素贝叶斯分类器（naive Bayes classifier）采用了“属性条件独立性假设”（attribute conditional independence assumption）
      • 即对已知类别，假设所有属性$(x^{(j)})$相互独立。换言之，假设每个属性独立地对分类结果发生影响。即$P(X=x|Y=c_k)=P(X=x^{(1)},X=x^{(2)}…X=x^{(n)}|Y=c_k)=\prod_{j=1}^{n}P(X=x^{(j)})|Y=c_k$

朴素贝叶斯的参数估计(概率估计方法)

在朴素贝叶斯法中，学习意味着估计$P(Y=c_k)和P(X=x^{(i)}|Y=c_k)$这里有多种方法进行估计：

  • 极大释然估计
    • 先验概率计算：
    • 条件概率计算：
  • 贝叶斯估计
    上面的极大释然估计可能会出现要估计的概率值为0的情况，这时会影响到后验概率等的计算，使分类产生偏差贝叶斯估计会适当加一个极小系数$(\lambda)$来避免这种情况
    • 当$(\lambda)=0$时，就是极大释然估计
    • 当$(\lambda)=1$时，称为拉普拉斯平滑
      • 先验概率计算：
      • 条件概率计算：

小结

发表于 | 分类于 ，

集成学习方法

GB(Gradient Boosting)理解

  • 理解梯度下降

    • 求解目标函数$J(\theta)$的最优解，本质上是一轮一轮的求解w
    • 对于最终的最后解W*,是由初始值$w_0$经过M次迭代得到的

  • 对比理解多轮迭代后的GB函数最优解

    • $f(x)$经过M次迭代，得到$F(x)=\sum_{i=1}^m\theta _if_i(x)$
    • 这里是反向思考：因为梯度下降是通过梯度下降的方法求出w参数值，最后就是经过了M轮迭代求出最优解w. 这里的w是参数，同样的思想对比到函数F(x)上,将F(x)视为整体类似于w，最后通过多轮迭代求出F(x)最优解
    • 梯度增强的作者们意识到，如果使用“梯度下降”（Gradient Descent）来优化一个目标函数，最后的预测式可以写成一个加和的形式。也就是，每一轮梯度的值和一个叫“学习速率”（Learning Rate）的参数共同叠加起来形成了最后的预测结果。这个观察非常重要，如果把这个观察和我们的目标，也就是构造弱学习器的加权平均联系起来看，我们就会发现，其实每个梯度的值就可以认为是一个弱学习器，而学习速率就可以看作是某种意义上的权重
    • 每一轮迭代，我们把当前所有学习器的加权平均结果当作这一轮的函数值，然后求得针对某一个损失函数对于当前所有学习器的参数的一个梯度。然后，我们利用某一个弱学习器算法，可以是线性回归模型（Linear Regression）、对数几率模型（Logistic Regression）等来拟合这个梯度。最后，我们利用“线查找”（Line Search）的方式找到权重。
      • 说得更直白一些，那就是我们尝试利用一些简单的模型来拟合不同迭代轮数的梯度
      • 梯度增强的一个特点就是梯度下降本身带来的，那就是每一轮迭代一定是去拟合比上一轮小的一个梯度，函数对目标的整体拟合也是越来越好的。这其实也就是增强算法和梯度下降的一个完美结合

  • 可以看出上述是一个求解梯度的过程，因此也称为基于梯度的Boost方法(即GB:Gradient Boosting)

  • 算法

    • 这里的m是m个机器学习模型，n应该是样本的数量。这里就能够看出，boost方法就是前一轮的结果会影响后一轮
    • 一般定义不同的Loss函数，就能得到不同的算法，比如这里用二分类任务中常用的$L(y,F)=log(1+exp(-2yF)), y \in {(-1,1)}$,就能得到如下算法：

DT理解

参考决策树

发表于 | 分类于 ，

个体与集成

集成学习（ensemble learning）的一般结构：先产生一组“个体学习器”（individual learner），再用某种策略将他们结合起来

  • 集成也可包含不同类型的个体学习器

    • 在一般的经验中，如果把好坏不等的东西掺到一起，那么通常结果会是比坏的好一些，比好的要坏一些。集成学习把多个学习器结合起来，如何能获得比最好的单一学习器更好的性能呢

  • 考虑一个简单的例子：在二分类任务中，假定三个分类器在三个测试样本的表现如下图所示

    • 集成学习的结果通过投票法（voting）产生，即“少数服从多数”。
    • 这个简单的例子显示出：要获得好的集成，个体学习器应“好而不同”。
      • 个体学习器要有一定的“准确性”，即学习器不能太坏
      • 而且要有“多样性”（diversity），即学习器之间有差异。
      • 事实上，如何产生并结合“好而不同”的个体学习器，恰是集成学习研究的核心

  • 多学习器结合的好处

    • 从统计的方面看，由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能，此时若使用单学习器可能因误选而导致泛化性能不佳，结合多个学习器减小这一风险；
    • 从计算的方面来看，学习算法往往会陷入局部极小，有的局部极小点所对应的泛化性能可能很糟，而通过多次运行之后进行结合，可降低陷入糟糕局部极小点的风险；
    • 从表示的方面来看，某些但学习器则肯定无效，而通过结合多个学习器，由于响应的假设空间有所扩大，有可能学得更好的近似

  • 结合不同子模型的分类

Bagging

各个子模型训练的时候是随机在样本库中抽取部分样本，并行训练，最后的多个模型参数取平均值

  • 随机抽取样本(有放回的)
  • 并行训练模型，各个模型之间无影响
  • 最后样本合成时，以平均值参数进行合成$F(x)=\frac 1m\sum_{i=1}^mf_i(x)$

Boosting

Boosting是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似：

  • 先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续收到更多的关注(其实就是改变权重，对判断正确的样本进行降权，判断错误的进行加权)
  • 然后基于调整后的样本分布来训练下一个基学习器；
  • 如此重复进行，直到基学习器数目达到事先指定的值T，最终将这T个学习器进行加权结合
    特点：
  • 每个学习区直接相互影响，串行化学习，最终的模型是对各个学习器加权求和,$F(x)=\sum_{i=1}^m\theta _if_i(x)$

发表于 | 分类于 ，

参考文章：
机器之心：读懂概率图

图模型

  • 图模型为很多存在依赖关系的真实世界任务提供了可以解释的建模方式。图模型为我们提供了一种用有原则的方式解决这些任务的方法
  • 概率图模型（PGM/probabilistic graphical model）是一种用于学习这些带有依赖（dependency）的模型的强大框架

  • 图的每个节点（node）都关联了一个随机变量，而图的边（edge）则被用于编码这些随机变量之间的关系

    • 我们可以将图的模式分为两大类——贝叶斯网络（Bayesian network）和马尔可夫网络（Markov networks）

  • “生成式”（generative）模型考虑联合分布P(Y,R,O)；
    “判别式”（discriminative）模型考虑条件分布P(Y,R|O);

  • 条件独立

    • 图结构实际上带有关于这些变量的重要信息。具体来说，它们定义了这些变量之间的一组条件独立（conditional independence），也就是这种形式的陈述——「如果观察到 A，那么 B 独立于 C。」

有向图模型:贝叶斯网络

“生成式”（generative）模型考虑联合分布P(Y,R,O),属于生成模型，借助有向无环图(DAG图)来刻画属性简的依赖关系，并使用条件概率表来描述属性的联合概率分布，这里重点是计算联合概率分布

  • 例子
    • 让我们看看与每个节点关联的表格，它们的正式名称是条件概率分布（CPD/conditional probability distribution）

隐马可科夫模型

隐马尔可夫模型（Hidden Markov Model，简称HMM）是结构最简单的动态贝叶斯网（dynamic Bayesian network），这是一种著名的有向图模型，主要用于时序数据建模，在语音识别、自然语言处理等领域有广泛应用

  • 其中几个重要的参数：

    • a.状态转移概率，y1,y2….的转移概率。
    • b.输出观察概率y输出x的概率。
    • c.初始状态概率，y1

  • HMM解决的问题

    • 如何评估模型与观测序列之间的匹配程度，例如许多任务已有观察序列{x1,x2,x3…xn-1}求x(n)的最有可能值，就是转换为判定模型，$P(x|\theta)$最大的匹配程度
    • 根据观测序列推断出隐藏的模型状态，已经{x1,x2,x3…x(n)},求{y1,y2,y3…y(n)}。如语音识别中，观测值为语音符号，隐藏状态为文字
    • 如何训练模型，使其能最好的描述观测数据，即调整模型参数[A,B,PI]，使得该观测序列出现的概率最大

马尔可夫随机场

马尔科夫随机场是典型的马尔科夫网络，是一种著名的无向图模型，多个变量之间的联合概率分布能够基于团分解为多个因子的乘积

  • 团：
    对于图中的任意两点都有线相连，则称该结点子集为一个”团”，若在一个团中加入另外的节点都不再形成团，那么陈该该结点子集为”极大团”

  • 势函数：
    亦称”因子”(factor)，这是定义在变量子集上的非负实函数，主要用于定义概率分布函数:

  • 多个变量之间的联合概率分布能够基于团分解为多个因子的乘积

条件随机场

是一种判别式无向图模型，对条件分布进行建模。试图对多个变量在给定观测值后的条件概率进行建模。

  • 具体说就是给定$X={x_1,x_2,x_3,….x_n}和Y={y_1,y_2,y_3…y_n}$然后建立模型P(Y|X)。然后对后面给定的$(x_{11},x_{12},x….)$直接使用P(Y|X)模型进行预测。标记变量y可以是结构型变量，即其分量直接具有某种相关性

学习和推断

  • 学习(参数估计)：
    如果都知道各个变量，各个属性间的依赖关系，只需要对各个条件概率表进行计数，就能够得到联合概率分布。但实际情况中几乎不会轻易得到所有的关系依赖，所有贝叶斯网络的首要任务是根据训练数据找出最“恰当”的贝叶斯网，也就是学习出属性间的依赖关系，得到联合概率分布。使用的是评分函数算法

  • 推断(推理)：通过第一步的学习得到了联合概率分布，属性，变量间的依赖关系，也就是得到了贝叶斯网络后，就可以通过它来回答”查询”，及通过一些已知属性变量的观测值来预测一些其他的属性

    • 我们可以使用推理来解答一些问题:

      • 边际推理（marginal inference）：寻找一个特定变量的概率分布。比如，给定一个带有变量 A、B、C 和 D 的图，其中 A 取值 1、2 和 3，求 p(A=1)、p(A=2) 和 p(A=3)。
      • 后验推理（posterior inference）：给定某些显变量 v_E（E 表示证据（evidence）），其取值为 e，求某些隐藏变量 v_H 的后验分布 p(v_H|v_E=e)。
      • 最大后验（MAP）推理（maximum-a-posteriori inference）：给定某些显变量 v_E，其取值为 e，求使其它变量 v_H 有最高概率的配置

    • 解答这些问题的流行的算法
      其中既有精准的算法，也有近似的算法。所有这些算法都既可用于贝叶斯网络，也可用于马尔可夫网络

      • 精确推断方法
        希望能计算出目标变量的边际分布或条件分布的精确值。遗憾的是，一般情形下，此类算法的计算复杂度随着极大团规模的增长呈指数增长，适用范围有限
        • 变量消去
          精确推断的实质是一类动态规划算法，它利用图模型所描述的条件独立性来消减计算目标概率值所需的计算量。变量消去是最直观的精确推断算法，也是构建其他精确推断算法的基础。
          变量消去法有一个明显的缺陷：若需计算多个边际分布，重复使用变量消去法将对造成大量的冗余计算。
        • 信念传播
          信念传播（Belief Propagation）算法将变量消去法中的求和操作看作一个消息传递过程，较好的解决了求解多个边际分布时重复计算问题。
      • 近似推断方法
        希望在较低时间复杂度下获得原问题的近似解。此类方法在现实任务中更常用
        • 采样：通过使用随机化方法完成近似
          • MCMC采样:概率图模型中最常用的采用技术是马尔可夫链蒙特卡罗（Markov Chain Monte Carlo，简称MCMC）方法
        • 变分推断（variational inference）
          • 变分推断通过使用已知简单分布来逼近所需推断的复杂分布，并通过限制近似分布的类型，从而得到一种局部最优、但具有确定解的近似后验分布

应用举例

  • 三门问题(贝叶斯网络)

    • 问题描述：
      主持人会向你展示三扇关着的门，其中一扇门之后有一辆车，其它门后则有一些无价值的东西。你可以选择一扇门。然后，主持人会打开剩下的两扇门中没有车的一扇。现在，你可以选择是否更换选择的门：坚持你之前选择的那扇门，还是选择主持人剩下的那扇关闭的门。你会更换吗？
      • 直觉上看，主持人似乎并没有透露任何信息。事实证明这种直觉并不完全正确。让我们使用我们的新工具「图模型」来理解这个问题
    • 网络构造
      • 定义变量
        • D：背后有车的门
        • F：你的第一个选择
        • H：主持人打开的门
        • I：F 是否是 D？
      • D、F 和 H 可取值为 1、2 或 3；I 可取值 0 或 1。D 和 I 是未被观察到的，而 F 是已观察到的。在主持人打开其中一扇门之前，H 都是未被观察到的。因此，我们使用贝叶斯网络来解决我们的问题
    • 计算逻辑
      注意箭头的方向——D 和 F 是相互独立的，I 显然依赖于 D 和 F，主持人选择的门也取决于 D 和 F。目前你对 D 还一无所知。（这与学生网络的结构类似，即知道学生的智力水平不能让你获得有关课程难度的任何信息
      • 现在，主持人选择了门 H 并打开了它。所以现在 H 已被观察到
      • 然后下面就是通过计算变量的CPD来得到最大的条件概率(判别式模型),详情见机器之心：读懂概率图

  • 图像去噪

    • 真实图像和噪音图像

    • 目标：现在你的目标是恢复原始图像。让我们看看如何使用概率图模型来实现

    • 思考步骤

      • 首先第一步是思考哪些变量是观察得到的，哪些变量不能观察到，以及我们可以如何将它们连接起来构成一个图
      • 让我们将有噪声图像中的每个像素都定义为一个观察到的随机变量，并将基准图像中的每个像素都定义为一个未被观察到的变量。由此，如果该图像的大小为 MxN，那么观察到的变量和未被观察到的变量都各有 MN 个。让我们将观察到的变量表示为 X_ij，未被观察到的变量定义为 Y_ij。每个变量都可取值 +1 或 -1（分别对应于黑色像素和白色像素）。
        • 模型：给定观察到的变量，我们希望找到未观察到的变量的最有可能的值。这对应于 MAP 推理

      • 现在让我们使用一些领域知识来构建图结构。很显然，在有噪声图像中的 (i,j) 位置观察到的变量取决于在基准图像中的 (i,j) 位置未观察到的变量。原因是大多数时候它们是相等的。

      • 我们还能得到什么信息？对于基准图像，邻近的像素通常有一样的值——在颜色变化的边界不是这样，但在每个单一颜色的区域内有这个性质。因此，如果 Y_ij 和 Y_kl 是邻近像素，那么我们将它们连接起来

    • 图结构

      • 其中，白色节点表示未被观察到的变量 Y_ij，灰色节点表示观察到的变量 X_ij。每个 X_ij 都连接到对应的 Y_ij，每个 Y_ij 都连接到它的相邻节点。
      • 注意这是一个马尔可夫网络，因为图像的像素之间不存在因果关系，因此这里不适合使用贝叶斯网络中有方向的箭头

发表于 | 分类于 ，

算法

  • 选取离样本最近的K个点

    • 计算距离的方式可以有多种，欧氏距离等等

  • 分类策略

    • 比较简单的就是直接看这K个点钟类别最多的一个，来作为当前样本点的类别

特点

  • K近邻不用进行训练
  • 选择K个点的时候，每次都需要计算全部的样本，计算量比较大

发表于 | 分类于 ，

算法步骤：

  • 随机选择K个簇中心点$\mu_1,\mu_2,\mu_3…\mu_k$
  • 然后依次加入其它节点，采用距离最近(该节点到各簇中心距离)的判别方式
  • 重新计算各簇中心点(因为有新节点加入)，直到所有节点都已加入

Random initialization

  • 会重复KMeans n次，找出cost最小的k值

    Cost funciton

    所有点到各簇中心点距离和

发表于 | 分类于 ，

间隔与支持向量

  • 支持向量：假设超平面(w,b)能将训练样本正确分类，即对于$(x_i,y_i)\in D$,若$y_i=1$,则有$w^Tx_i+b>0$;若$y_i=-1$,则有$w^Tx_i+b<0$令 如图 6.2所示，距离超平面最近的这几个训练样本点使式(6.3)的等号成立， 它们被称为”支持向量” (support vector)
    • svm是解决分类问题，但并不会计算所以的点,只计算支持向量
  • 间隔：两个异类支持向量到超平面的距离之和被称为”间隔” (margin).

硬间距与软间距

  • 硬间距:前面介绍的支持向量机形式是要求所有样本均满足约束(6.3)， 即所有样本都必须划分i丘确
  • 软间距：软间隔则是允许某些样本不满足约束6.3，允许某些样本不满足:$y_i(w^Tx_i+b)>=1$
    • 在最大化间隔的同时，不满足约束的样本应尽可能少
    • 松弛变量($\varepsilon$)与软间隔支持向量机
  • 优化目标：

替代损失

  • $l_{0/1}$非凸、非连续，数学性质不太好，使得式 (6.29)不易直接求解.于 是，人们通常用其他一些函数来代替$l_{0/1}$
  • 三种常用的替代损失函数:

约束求解&拉格朗日乘子求解&KKT

  • 求解最优问题：1.无约束（一般直接求导）2.等式约束（用拉格朗日求解）3.不等式约束（用KKT求解）
  • 拉格朗日乘子：通过拉格朗日这位大神的办法重新定义一个无约束问题（大家都喜欢无拘无束），这个无约束问题等价于原来的约束优化问题，从而将约束问题无约束化
  • 式(6.35)中每个样本都有一个对应的松弛变量， 用 以表征该样本不满 足约束(6.28)的程度.但是，与式(6.6)相似，这仍是一个二次规划问题于是?类 似式 (6.8)，通过拉格朗日乘子法可得到式 (6.35)的拉格朗日函 数
  • 推导
    参考1
    参考2

核函数

支持向量回归

传统回归模型通常直接基于模型输出 f(x) 与真实输出y之 间的差别来计算损失，当且仅当 f(x) 与 y 完全相同时，损失才为零.与此不同， 支持向量回归 (Support Vector Regression，简称 SVR)假设我们能容忍 f(x) 与 y 之间最多有$\epsilon$的偏差，即仅当 f(x) 与 u 之间的差别绝对值大于 E 时才计算损 失.如国 6.7所示?这相当于以 f(x) 为中心?构建了一个宽度为$2\epsilon$的问隔带，若 训练样本落入此间隔带，则认为是被预测正确的.