狮城*青云
共3条回答277浏览
-
-
随机森林是一种集成算法(Ensemble Learning)，它属于Bagging类型，通过组合多个弱分类器，最终结果通过投票或取均值，使得整体模型的结果具有较高的精确度和泛化性能。其可以取得不错成绩，主要归功于 "随机"和“森林” ，一个使它具有抗过拟合能力，一个使它更加精准。 Bagging 是一种在原始数据集上通过有放回抽样重新选出k个新数据集来训练分类器的集成技术。它使用训练出来的分类器的集合来对新样本进行分类，然后用多数投票或者对输出求均值的方法统计所有分类器的分类结果，结果最高的类别即为最终标签。此类算法可以有效降低bias，并能够降低variance。 【 自助法 】它通过自助法（bootstrap）重采样技术，从训练集里面采集固定个数的样本，但是每采集一个样本后，都将样本放回。也就是说，之前采集到的样本在放回后有可能继续被采集到。 【OOB】 在Bagging的每轮随机采样中，训练集中大约有的数据没有被采样集采集中。 对于这部分没有采集到的数据，我们常常称之为袋外数据(Out of Bag, 简称OOB) 。这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。 【随机性】 对于我们的Bagging算法，一般会对样本使用boostrap进行随机采集，每棵树采集相同的样本数量，一般小于原始样本量。这样得到的采样集每次的内容都不同 ，通过这样的自助法生成K个分类树组成随机森林，做到样本随机性 。 【输出】 Bagging的集合策略也比较简单，对于分类问题，通常使用简单投票法，得到最多票数的类别或者类别之一为最终的模型输出。对于回归问题，通常使用简单平均法，对T个弱学习器得到的回归结果进行算术平均得到的最终的模型输出。 【弱分类器】 首先，RF使用了CART决策树作为弱学习器。换句话说，其实我们只是将实验CART决策树作为弱学习器的Bagging方法称为随机森林。 【随机性】 同时，在生成每棵树的时候， 每个树选取的特征都不仅仅是随机选出的少数特征，一般默认取特征总数m的开方。 而一般的CART树则会选取全部的特征进行建模。因此 ，不但特征是随机的，也保证了特征随机性 。 【样本量】 相对于一般的Bagging算法，RF会选择采集和训练集样本数N一样个数的样本。、 【特点】 由于随机性，对于降低模型的方差很有作用，故随机森林一般不需要额外剪枝，即可以取得较好的泛化能力和抗拟合能力(Low Variance)。当然对于训练集的拟合程度就会差一点，也就是模型的偏倚会大一些(High Bias)，仅仅是相对的。 在关于随机森林的原始论文中，显示随机森林错误率取决于两件事： 森林中任何两棵树之间的相关性。增加相关性会增加森林错误率。 森林中每棵树的力量(具有低错误率的树是强分类器)。增加单棵数据的强度(分类更精确)会降低森林错误率。 随机森林的弱分类器使用的是CART树，CART决策树又称为分类回归树。当数据集的因变量为连续型数值时，该树算法就是一个回归树，可以用叶节点观察的均值作为预测值；当数据集的因变量为离散型数值时，该树算算法就是一个分类树，可以很好地解决分类问题。但是需要注意的是，该算法是一个二叉树，即每一个叶节点只能引申出两个分支，所以当某个非叶节点是多水平(2个以上)的离散变量时，该变量就有可能被多次使用。同时，若某个非叶节点是连续变量时，决策树也将把他当做离散变量来处理(即在有限的可能值中做划分)。 特征选择目前比较流行的方法是信息增益、增益率、基尼系数和卡方检验。这里主要介绍基于基尼系数(Gini)的特征选择，因为随机森林采用的CART决策树就是基于基尼系数选择特征的。 基尼系数的选择的标准就是每个子节点达到最高的纯度，即落在子节点中的所有观察都属于同一分类，此时基尼系数最小，纯度最高，不确定度最小。对于一般的决策树，加入总共有K类，样本属于第K类的概率：pk,则该概率分布的基尼指数为： 基尼指数越大，说明不确定性就越大；基尼系数越小，不确定性越小，数据分割越彻底，越干净。 对于CART树而言，由于是二叉树，可以通过下面的表示： 在我们遍历每个特征的每个分割点时，当使用特征A=a，将D划分为两部分，即D1（满足A=a的样本集合），D2（不满足A=a的样本集合）。则在特征A=a的条件下D的基尼指数为： Gini(D)：表示集合D的不确定性。 Gini(A,D)：表示经过A=a分割后的集合D的不确定性。 随机森林中的每棵CART决策树都是通过不断遍历这棵树的特征子集的所有可能的分割点，寻找Gini系数最小的特征的分割点，将数据集分成两个子集，直至满足停止条件为止。 首先，正如Bagging介绍中提到的，每个树选择使用的特征时，都是从全部m个特征值随机产生的，本身就已经降低了过拟合的风险和趋势。模型不会被特定的特征值或特征组合所决定，随机性的增加，将控制模型的拟合能力不会无限提高。 第二，与决策树不同，RF对决策树的简历做了改进。对于普通的决策树，我们会在节点上所有的m个样本特征中选择一个最优的特征来做决策树的左右子树划分。但是RF的每个树，其实选用的特征是一部分，在这些少量特征中，选择一个最优的特征来做决策树的左右子树划分，将随机性的效果扩大，进一步增强了模型的泛化能力。 假设每棵树选取msub个特征，msub越小，此时模型对于训练集的拟合程度会变差，偏倚增加，但是会泛化能力更强，模型方差减小。msub越大则相反。在实际使用中，一般会将msub的取值作为一个参数，通过开启OOB验证或使用交叉验证，不断调整参数以获取一个合适的msub的值。 优点： （1）由于采用了集成算法，本身精度比大多数单个算法要好。 （2）在测试集上表现良好，由于两个随机性的引入，使得随机森林不容易陷入过拟合( 样本随机，特征随机 ) （3）在工业上，由于两个随机性的引入，使得随机森林具有一定的抗噪声能力，对比其他算法具有一定优势。 （4）由于树的组合，使得随机森林可以处理非线性数据，本身属于非线性分类(拟合)模型。 （5） 它能够处理很高维度(feature很多)的数据 ，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。 （6）训练速度快，可以运用在大规模数据集上。 （7）由于袋外数据(OOB)，可以在模型生成过程中取得真实误差的无偏估计，且不损失训练数据量。 （8）在训练过程中，能够检测到feature间的互相影响， 且可以得出feature的重要性 ，具有一定参考意义。 （9）由于每棵树可以独立、同时生成，容易做成并行化方法。 （10）由于实现简单、 精度高、抗过拟合能力强 ，当面对非线性数据时，适于作为基准模型。 缺点： （1）随机森林在解决回归问题时，并没有像它在分类中表现的那么好，这是因为它并不能给出一个连续的输出。当进行回归时，随机森林不能够作出超越训练集数据范围的预测，这可能导致在某些特定噪声的数据进行建模时出现过拟合。（PS:随机森林已经被证明在某些噪音较大的分类或者回归问题上会过拟合） （2）对于许多统计建模者来说，随机森林给人感觉就像一个黑盒子，你无法控制模型内部的运行。只能在不同的参数和随机种子之间进行尝试。 （3）可能有很多相似的决策树，掩盖了真实的结果。 （4）对于小数据或者低维数据(特征较少的数据)，可能不能产生很好的分类。( 处理高维数据，处理特征遗失数据，处理不平衡数据是随机森林的长处 )。 （5）执行数据虽然比boosting等快，但是比单棵决策树慢多了。 （1） 不要求是线性特征，比如逻辑回归很难处理类别型特征 ，而树模型，是一些决策树的集合，可以很容易的处理这些情况。 （2） 由于算法构建的过程，这些算法很容易处理高维的数据，大量的训练数据的场景 。 极端随机树是随机森林的一个变种，原理几乎和RF一模一样，仅有区别有： （1）对于每个决策树的训练集，RF采用的是随机采样bootstrap来选择采样集作为每个决策树的训练集，而extra trees一般不采用随机采样，即每个决策树采用原始训练集。 （2）在选定了划分特征后，RF的决策树会基于基尼系数，均方差之类的原则，选择一个最优的特征值划分点，这和传统的决策树相同。但是极端随机树比较的激进，他会随机的选择一个特征值来划分决策树。
-
-
-
PCC Vivace结合了一篇2015年NSDI的 PCC [1] 的基本框架，以及机器学习中 online convex optimization的原理 [2] ，通过调整发送端速率的调整方向、调整步长和调整阈值，来解决网络的拥塞控制问题。
这篇论文作为拥塞控制问题的解决办法之一，在Introduction段就击中了 上一篇文章 讲到的 Remy [3] 的痛点——无法自适应不同的网络应用场景。
论文也将 BBR [4] 作为主要的对比对象之一。BBR采用白盒的网络建模方式，假设网络环境已知；而PCC Vivace使用黑盒方法，感知网络在给出某发送速率之后的表现，从而调整发送速率。Dong实验发现，一方面，在网络达到稳定收敛的状态后，BBR仍表现出较大的比特率抖动和较高的丢包率。另一方面，和Remy一样，一旦建模的网络环境和真实的网络环境相差很大，算法的性能就会遭受严重的损失。
另外，论文特别提到了另一个对比对象， Sprout [5] 。Sprout是一篇2013年的NSDI，使用随机森林的方法达到蜂窝网络下的高吞吐量和低延迟。Dong承认在蜂窝网络的场景下Sprout比Vivace表现更好，但表示Vivace的目标是一种更普适的拥塞控制算法，不会局限于某一种特定的网络场景。
Vivace将时间切割成连续的 MI (Monitor Intervals)。每个MI结束时，发送端i就用下面的效用方程把MI时段观察的数据转换为效用值 u ：
其中0
理想情况下，网络收敛时，latency不会超过base RTT，.，没有使用链路缓冲时的RTT。因此第二个theorem得出了达到这种理想情况对参数b的要求。
p-loss-resilient ：这个协议不降低发送速率时，最多能忍受p的随机loss（一旦随机loss超过p就要求降低发送速率）
要使Vivace能承受p-loss-resilient，则需要设置效用方程的第三项中的参数c满足：
然而要忍受更多的随机loss是有代价的。为了简化，下面设置b=0（即效用方程的计算只依赖loss）。
上面的三条theorem都是讨论的同构的sender，这一条是关于异构sender的情况。异构senders通常需要考虑的就是资源分配的问题。举一个详细的例子，效用公式如下：
假定n个Vivace senders共用链路容量为C的瓶颈链路，各个sender被分配的资源总和为C。
（鉴于公式字符过于复杂，这里不详细列出每个字符了）
总的来说，每次计算新的发送比特率时，都会先给定一个小的差值，计算上次比特率加减差值的两个效用方程的值，两效用值相减再除以二倍差值就是比特率在此时的梯度（也就是导数）。Vivace算法通过控制这个梯度的值来控制比特率的变化程度。新的比特率=上一次比特率+梯度
首先，Vivace给这个梯度设置了一个信心放大器。顾名思义，比特率连续朝同一个方向改变的次数多了，那步子就可以迈大一点，即增加梯度。
其次，Vivace给步长设置了一个动态阈值（毕竟步子迈大了容易***），一旦这次计算的梯度超出了此时的阈值，那就把阈值拉高一点点；一旦没超过，但比特率仍朝着同一个方向前进，那就把阈值拉回比这次计算的梯度多一点点的地方等它下次争取超过；一旦比特率连变化方向都变了，那直接把阈值设为0，哪怕你之前腿比维密模还长都得全砍了。
Vivace的大体思路如上，但论文中分loss和delay进行了实现和对比，实验细节详见论文本文。
-
-
-
这一篇文章我们会介绍一种模型解释的方法, LIME, 即会通过简单的模型来解释黑盒模型. 我们会介绍LIME的简单的原理, 和一个例子, 使用LIME来解释使用Pytorch搭建的模型. 这一部分介绍使用LIME来进行模型解释. LIME的全称为 Local Interpretable Model-agnostic Explanations . 在这一部分我们会介绍LIME方法的主要的思想, 和结合Pytorch来进行解释, 解释使用Pytorch搭建的模型. 下面是一些LIME的参考资料. 之前我们也讲过一个模型解释的方法, 叫做Saliency Map, 之前的链接如下: Saliency Maps的原理与简单实现(使用Pytorch实现) 模型的可解释性书本的一章 : Local Surrogate (LIME) 原始论文 : Ribeiro, Marco Tulio, Sameer Singh, and Carlos Guestrin. “Why should I trust you?: Explaining the predictions of any classifier.” Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. ACM (2016). Python的库LIME : Lime: Explaining the predictions of any machine learning classifier LIME的想法很简单, 我们希望 使用简单的模型来对复杂的模型进行解释 . 这里简单的模型可以是线性模型, 因为我们可以通过查看线性模型的系数大小来对模型进行解释. 在这里, LIME只会对每一个样本进行解释(explain individual predictions) . LIME会产生一个新的数据集(这个数据集我们是通过对某一个样本数据进行变换得到), 接着在这个新的数据集上, 我们训练一个简单模型(容易解释的模型), 我们希望简答模型在新数据集上的预测结果和复杂模型在该数据集上的预测结果是相似的 . 我们可以将我们的问题表达为下面的表达式: 上式中每一个字母的含义: f表示原始的模型, 即需要解释的模型. g表示简单模型, G是简单模型的一个集合, 如所有可能的线性模型. Pi_x表示我们新数据集中的数据x'与原始数据instance x的距离. Ω(g)表示模型g的复杂程度. 我们希望原始模型f与新模型g预测值之间的误差是小的 . 简单来说, 我们可以通过下面的式子来衡量两个式子预测值之间的差: 于是整个LIME的步骤如下(即训练模型g的步骤) 选择我们想要解释的变量x. 对数据集中的数据进行扰动 得到新的数据, 同时计算出黑盒模型对这些新的数据的预测值. 对这些新的sample求出权重, 这个权重是这些数据点与我们要解释的数据之间的距离. 根据上面新的数据集, 预测值和权重, 训练出模型g 通过模型g来对模型f在x点附近进行解释. 那么我们 如何对数据集进行扰动来得到新的数据 , 对于表格数据, 我们可以分别扰动每一个特征, 从一个正态分布(均值和方差为这个特征的均值和方差)中进行随机抽样. 这样做会有一个问题, 即不是从我们要解释的数据为中心进行采样, 而是从整个数据集的中心进行采样. (LIME samples are not taken around the instance of interest, but from the training data's mass center, which is problematic.) 下面我们通过一张图片来对上面的过程进行解释(这张图片是上面第一个参考链接中的). 图A表示: 随机森林的分类结果, 颜色深的为一类, 颜色浅的为一类. 图B表示: 通过对特征进行扰动得到的新的数据集. 图C表示: 对每一个数据进行加权. 图D表示: 对简单的模型进行求解. 存在的问题 : 定义我们要解释的点的周围是困难的.这一部分我们会看一下如何使用LIME来对Pytorch搭建的模型进行解释. 我们会使用库LIME来完成相关的模型的解释: Lime: Explaining the predictions of any machine learning classifier 这是一个LIME和Pytorch结合的例子: Using Lime with Pytorch . 这是一个解释图片的例子, 我们下面看一个解释表格数据的例子(我们就只看一下解释的步骤, 前面模型的训练和数据的处理就不放了). 我在GIthub上上传了一个LIME与Pytorch结合使用的例子, 链接为 : Github-LIME与Pytorch结合 对于这个例子的理解, 可以参考文章: Pytorch例子演示及LIME使用例子 这一部分在这里不是很重要, 就不详细进行说明了. 我们使用Pytorch训练好的模型叫 fullModel , 导入的数据集为 XData和YData . 我们需要定义一个函数, 输入的是模型和x, 输出的是预测的概率.# 定义分类器 defbatch_predict(data, model=fullModel): """ model: pytorch训练的模型 data: 需要预测的数据 """ X_tensor = (data).float() () device = ("cuda"()else"cpu") (device) X_tensor = (device) logits = model(X_tensor) probs = (logits, dim=1) ().cpu().numpy() 上面函数的效果就是输入数据和模型, 输出的为每一个分类的概率, 下面看一下他的输出. 接着我们就是对我们的黑盒模型局部进行解释.# 创建解释器 importlime 我们需要创建模型的输入和输出. X_tensor = (XData[X_index]).float() y_tensor = ((y)).long() 接着创建解释器. 下面的feature_names就是每一个feature的名字. targets = ['back', 'land', 'neptune', 'pod', 'smurf', 'teardrop'] explainer = (XData[X_index], feature_names=[:-4].values, class_names=targets, discretize_continuous=True) 最后我们对一个样本进行解释, 下面我们解释的是第505个样本. # 解释某一个样本 exp = (XData[X_index][505], batch_predict, num_features=5, top_labels=5) 最后我们将解释的结果显示出来. (show_table=True, show_all=False) 因为这是一个多分类的问题, 我们可以显示预测为某一个分类的原因. (label=5)
-
