生成式算法

1. 机器学习中常见算法优缺点之朴素贝叶斯算法

在机器学习中有很多算法，而有一种算法有着坚实的数学背景，并且被广泛使用，这种算法就是朴素贝叶斯算法。当然，朴素贝叶斯算法的优点有很多，但这种算法的缺点也是我们不能忽视的，那么大家知道不知道朴素贝叶斯算法的优点和缺点是什么呢？下面我们就给大家介绍一下这个问题。
那么什么是朴素贝叶斯算法呢？其实朴素贝叶斯属于生成式模型，也就是关于生成模型和判别式模型，主要还是在于是否需要求联合分布，这种算法是一种比较简单的算法，你只需做一堆计数即可。如果注有条件独立性假设，朴素贝叶斯分类器的收敛速度将快于判别模型，比如逻辑回归，所以你只需要较少的训练数据即可。即使NB条件独立假设不成立，NB分类器在实践中仍然表现的很出色。它的主要缺点是它不能学习特征间的相互作用，用mRMR中R来讲，就是特征冗余。
那么朴素贝叶斯算法的优点是什么呢？这种算法的优点有五个，第一就是朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。第二就是对大数量训练和查询时具有较高的速度。即使使用超大规模的训练集，针对每个项目通常也只会有相对较少的特征数，并且对项目的训练和分类也仅仅是特征概率的数学运算而已。第三就是对小规模的数据表现很好，能个处理多分类任务，适合增量式训练（即可以实时的对新增的样本进行训练）。第四就是对缺失数据不太敏感，算法也比较简单，常用于文本分类。第五就是朴素贝叶斯对结果解释容易理解。
当然，朴素贝叶斯算法的缺点也是很明显的，朴素贝叶斯算法的缺点有四点，第一就是需要计算先验概率。第二就是分类决策存在错误率。第三就是对输入数据的表达形式很敏感。第四就是对由于使用了样本属性独立性的假设，所以如果样本属性有关联时其效果不好。
那么朴素贝叶斯应用领域是什么呢？其实朴素贝叶斯算法在欺诈检测中使用较多。当然，我们还可以用朴素贝叶斯算法来决定一封电子邮件是否是垃圾邮件。还可以用朴素贝叶斯算法判断一篇文章应该的类别，同时也能够使用贝叶斯算法去判断一段文字表达的是积极的情绪还是消极的情绪。从中我们可以看出朴素贝叶斯算法是一个十分实用的算法。
在这篇文章中我们给大家介绍了关于朴素贝叶斯算法优缺点的相关知识，通过对这些知识的讲解相信大家已经对朴素贝叶斯算法有了一定的了解，希望这篇文章能够帮助大家。

2. 什么是列生成算法

列生成
设yi(i∈N＼{0})为前述线性规划(LP)的对偶变量(al variable)，则对应可 行路线r=(0,i1,i2, …, ik, 0)有即约代价(reced cost)fr：

它可表示为r上弧的边际代价(marginal cost)之和：

这里弧(i,j)的边际代价定义为

fij=Cij-yj，(i,j)∈r

当对任意r∈R有fr0时， 线性规划(LP)求得最优解。
在实施列生成时，可行路线r通过动态规划产生。设Fi(S,t)表示从中心出发，经过S中的 所有点i(PiSN)一次且仅仅一次，在t时刻或之前到达客户i的路线的最小边际成本， 则Fi(S,t)可用如下递归公式计算：

对所有的j,S,t, j∈N, SN, ajtbj.

3. 无人驾驶(三)行人跟踪算法

姓名：王梦妮

学号：20021210873

学院：电子工程学院

【嵌牛导读】本文主要介绍了无人驾驶中所需的行人跟踪算法

【嵌牛鼻子】无人驾驶 环境感知 计算机视觉 卡尔曼滤波 粒子滤波 均值漂移

【嵌牛提问】无人驾驶中所用到的行人跟踪算法有哪些

【嵌牛正文】

行人跟踪一直是视觉领域的一个难点，实际应用环境复杂、遮挡以及行人姿态变化等外界因素都影响着行人跟踪算法的研究。行人跟踪算法模型主要分为生成模型和判别模型。

（一）生成式模型

生成式模型是一种通过在线学习行人目标特征，建立行人跟踪模型，然后使用模型来搜索误差最小的目标区域，从而完成对行人的跟踪。这种算法在构建模型只考虑了行人本身的特征，忽略了背景信息，没有做到有效利用图像中的全部信息。其中比较经典的算法主要有卡尔曼滤波，粒子滤波，mean-shift等。

（1）卡尔曼滤波算法

卡尔曼滤波算法是一种通过对行人构建状态方程和观测方程为基础，计算最小均方误差来实现跟踪的最优线性递归滤波算法，通过递归行人的运动状态来预测行人轨迹的变化。

首先设定初始参数，读取视频序列。然后进行背景估计，产生初始化背景图像。然后依次读取视频序列，利用Kahnan滤波算法，根据上一帧估计的背景和当前帧数据得到当前帧的前景目标。然后对前景目标进行连通计算，检测出运动目标的轨迹。经典的卡尔曼滤波算法．只能对线性运动的行人实现跟踪，之后学者改进了卡尔曼滤波算法，能够实现对非线性运动的行人进行跟踪，计算量小，能实现实时跟踪，但是跟踪效果不理想。

（2）粒子滤波

    粒子滤波的核心就是贝叶斯推理和重要性采样。粒子滤波可用于非线性非高斯模型，这是由于贝叶斯推理采用蒙特卡洛法，以某个时间点事件出现的频率表示其概率。通过一组粒子对整个模型的后验概率分布进行近似的表示，通过这个表示来估计整个非线性非高斯系统的状态。重要性采用就是通过粒子的置信度来赋予不同的权重，置信度高的粒子，赋予较大的权重，通过权重的分布形式表示相似程度。

（3）均值漂移（mean-shift）

    Mean-shift算法属于核密度估计法。不必知道先验概率，密度函数值由采样点的特征空间计算。通过计算当前帧目标区域的像素特征值概率来描述目标模型，并对候选区域进行统一描述，使用相似的函数表示目标模型与候选模板之间的相似度，然后选择在具有相似函数值最大的候选模型中，您将获得关于目标模型的均值漂移向量，该向量表示目标从当前位置移动到下一个位置的向量。通过连续迭代地计算均值偏移矢量，行人跟踪算法将最终收敛到行人的实际位置，从而实现行人跟踪。

（二） 判别式模型

判别模型与生成模型不同，行人跟踪被视为二分类问题。提取图像中的行人和背景信息，并用于训练分类器。通过分类将行人从图像背景中分离出来，以获取行人的当前位置。以行人区域为正样本，背景区域为负样本，通过机器学习算法对正样本和负样本进行训练，训练后的分类器用于在下一帧中找到相似度最高的区域，以完成行人轨迹更新。判别式模型不像生成式模型仅仅利用了行人的信息，还利用了背景信息，因此判别式模型的跟踪效果普遍优于生成式模型。

（1）基于相关滤波的跟踪算法

      核相关滤波(KCF)算法是基于相关滤波的经典跟踪算法，具有优良的跟踪效果和跟踪速度。这是由于其采用了循环移位的方式来进行样本生产，用生成的样本来训练分类器，通过高斯核函数来计算当前帧行人与下一帧中所有候选目标之间的相似概率图，找到相似概率图最大的那个候选目标，就得到了行人的新位置。KCF算法为了提高跟踪精度，使用HOG特征对行人进行描述，同时结合了离散傅里叶变换来降低计算量。

（2）基于深度学习的跟踪算法

    近年来，深度学习在图像和语音方面取得了较大的成果，因此有许多科研人员将深度学习与行人跟踪相结合，取得了比传统跟踪算法更好的性能。DLT就是一个基于深度学习的行人跟踪算法，利用深度模型自动编码器通过离线训练的方式，在大规模行人数据集上得到一个行人模型，然后在线对行人进行跟踪来微调模型。首先通过粒子滤波获取候选行人目标，然后利用自动编码器进行预测，最终得到行人的预测位置即最大输出值的候选行人目标位置。2015年提出的MDNet算法采用了分域训练的方式。对于每个类别，一个单独的全连接层用于分类，并且全连接层前面的所有层都是共享，用于特征提取。2017年提出的HCFT算法使用深度学习对大量标定数据进行训练，得到强有力的特征表达模型，结合基于相关滤波的跟踪算法，用于解决在线进行跟踪过程中行人样本少、网络训练不充分的问题。此外，通过深度学习提取特征，利用数据关联的方法来实现跟踪的算法，其中最为着名的就JPDAF与MHT这两种方法。