Joshua's Blog

上一周七天都在上班，周一终于还是决定休假一天，睡过午觉起来画一笔。

在学校读研期间研读过随机森林的相关文献，也实际使用过，算是对随机森林有些了解。今天看到一篇博文，感觉对随机森林的总结比较到位，遂转发到自己的个人网站上。原文链接为[Machine Learning & Algorithm] 随机森林（Random Forest）

什么是随机森林？

作为新兴起的、高度灵活的一种机器学习算法，随机森林（Random Forest，简称RF）拥有广泛的应用前景，从市场营销到医疗保健保险，既可以用来做市场营销模拟的建模，统计客户来源，保留和流失，也可用来预测疾病的风险和病患者的易感性。最初，我是在参加校外竞赛时接触到随机森林算法的。最近几年的国内外大赛，包括2013年百度校园电影推荐系统大赛、2014年阿里巴巴天池大数据竞赛以及Kaggle数据科学竞赛，参赛者对随机森林的使用占有相当高的比例。此外，据我的个人了解来看，一大部分成功进入答辩的队伍也都选择了Random Forest 或者 GBDT 算法。所以可以看出，Random Forest在准确率方面还是相当有优势的。

那说了这么多，那随机森林到底是怎样的一种算法呢？

如果读者接触过决策树（Decision Tree）的话，那么会很容易理解什么是随机森林。随机森林就是通过集成学习的思想将多棵树集成的一种算法，它的基本单元是决策树，而它的本质属于机器学习的一大分支——集成学习（Ensemble Learning）方法。随机森林的名称中有两个关键词，一个是“随机”，一个就是“森林”。“森林”我们很好理解，一棵叫做树，那么成百上千棵就可以叫做森林了，这样的比喻还是很贴切的，其实这也是随机森林的主要思想—集成思想的体现。“随机”的含义我们会在下边部分讲到。

其实从直观角度来解释，每棵决策树都是一个分类器（假设现在针对的是分类问题），那么对于一个输入样本，N棵树会有N个分类结果。而随机森林集成了所有的分类投票结果，将投票次数最多的类别指定为最终的输出，这就是一种最简单的 Bagging 思想。

随机森林的特点

我们前边提到，随机森林是一种很灵活实用的方法，它有如下几个特点：

1. 在当前所有算法中，具有极好的准确率/It is unexcelled in accuracy among current algorithms；
2. 能够有效地运行在大数据集上/It runs efficiently on large data bases；
3. 能够处理具有高维特征的输入样本，而且不需要降维/It can handle thousands of input variables without variable deletion；
4. 能够评估各个特征在分类问题上的重要性/It gives estimates of what variables are important in the classification；
5. 在生成过程中，能够获取到内部生成误差的一种无偏估计/It generates an internal unbiased estimate of the generalization error as the forest building progresses；
6. 对于缺省值问题也能够获得很好得结果/It has an effective method for estimating missing data and maintains accuracy when a large proportion of the data are missing

实际上，随机森林的特点不只有这六点，它就相当于机器学习领域的Leatherman（多面手），你几乎可以把任何东西扔进去，它基本上都是可供使用的。在估计推断映射方面特别好用，以致都不需要像SVM那样做很多参数的调试。具体的随机森林介绍可以参见随机森林主页：Random Forest。

随机森林的相关基础知识

随机森林看起来是很好理解，但是要完全搞明白它的工作原理，需要很多机器学习方面相关的基础知识。在本文中，我们简单谈一下，而不逐一进行赘述，如果有同学不太了解相关的知识，可以参阅其他博友的一些相关博文或者文献。

信息、熵以及信息增益的概念，这三个基本概念是决策树的根本，是决策树利用特征来分类时，确定特征选取顺序的依据。理解了它们，决策树你也就了解了大概。

引用香农的话来说，信息是用来消除随机不确定性的东西。当然这句话虽然经典，但是还是很难去搞明白这种东西到底是个什么样，可能在不同的地方来说，指的东西又不一样。对于机器学习中的决策树而言，如果带分类的事物集合可以划分为多个类别当中，熵是用来度量不确定性的，当熵越大，X=xi的不确定性越大，反之越小。对于机器学习中的分类问题而言，熵越大即这个类别的不确定性更大，反之越小。

信息增益在决策树算法中是用来选择特征的指标，信息增益越大，则这个特征的选择性越好。

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。常见的决策树算法有C4.5、ID3和CART。

集成学习通过建立几个模型组合的来解决单一预测问题。它的工作原理是生成多个分类器/模型，各自独立地学习和作出预测。这些预测最后结合成单预测，因此优于任何一个单分类的做出预测。

随机森林是集成学习的一个子类，它依靠于决策树的投票选择来决定最后的分类结果。你可以在这找到用python实现集成学习的文档：Scikit 学习文档。

随机森林的生成

前面提到，随机森林中有许多的分类树。我们要将一个输入样本进行分类，我们需要将输入样本输入到每棵树中进行分类。打个形象的比喻：森林中召开会议，讨论某个动物到底是老鼠还是松鼠，每棵树都要独立地发表自己对这个问题的看法，也就是每棵树都要投票。该动物到底是老鼠还是松鼠，要依据投票情况来确定，获得票数最多的类别就是森林的分类结果。森林中的每棵树都是独立的，99.9%不相关的树做出的预测结果涵盖所有的情况，这些预测结果将会彼此抵消。少数优秀的树的预测结果将会超脱于芸芸“噪音”，做出一个好的预测。将若干个弱分类器的分类结果进行投票选择，从而组成一个强分类器，这就是随机森林bagging的思想（关于bagging的一个有必要提及的问题：bagging的代价是不用单棵决策树来做预测，具体哪个变量起到重要作用变得未知，所以bagging改进了预测准确率但损失了解释性）。

有了树我们就可以分类了，但是森林中的每棵树是怎么生成的呢？

每棵树的按照如下规则生成：

1. 如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中的抽取N个训练样本（这种采样方式称为bootstrap sample方法），作为该树的训练集；

2. 从这里我们可以知道：每棵树的训练集都是不同的，而且里面包含重复的训练样本（理解这点很重要）。

   为什么要随机抽样训练集？

   如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的，这样的话完全没有bagging的必要；

   为什么要有放回地抽样？

   我理解的是这样的：如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是”有偏的”，都是绝对”片面的”（当然这样说可能不对），也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表决应该是”求同”，因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的，这样无异于是”盲人摸象”。

3. 如果每个样本的特征维度为M，指定一个常数m<<M，随机地从M个特征中选取m个特征子集，每次树进行分裂时，从这m个特征中选择最优的；

4. 每棵树都尽最大程度的生长，并且没有剪枝过程。

一开始我们提到的随机森林中的“随机”就是指的这里的两个随机性。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）。

随机森林分类效果（错误率）与两个因素有关：

1. 森林中任意两棵树的相关性：相关性越大，错误率越大；
2. 森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低。

减小特征选择个数m，树的相关性和分类能力也会相应的降低；增大m，两者也会随之增大。所以关键问题是如何选择最优的m（或者是范围），这也是随机森林唯一的一个参数。
回到顶部

袋外错误率（oob error）

上面我们提到，构建随机森林的关键问题就是如何选择最优的m，要解决这个问题主要依据计算袋外错误率oob error（out-of-bag error）。

随机森林有一个重要的优点就是，没有必要对它进行交叉验证或者用一个独立的测试集来获得误差的一个无偏估计。它可以在内部进行评估，也就是说在生成的过程中就可以对误差建立一个无偏估计。

我们知道，在构建每棵树时，我们对训练集使用了不同的bootstrap sample（随机且有放回地抽取）。所以对于每棵树而言（假设对于第k棵树），大约有1/3的训练实例没有参与第k棵树的生成，它们称为第k棵树的oob样本。

而这样的采样特点就允许我们进行oob估计，它的计算方式如下（note：以样本为单位）：

1. 对每个样本，计算它作为oob样本的树对它的分类情况（约1/3的树）；
2. 然后以简单多数投票作为该样本的分类结果；
3. 最后用误分个数占样本总数的比率作为随机森林的oob误分率。

oob误分率是随机森林泛化误差的一个无偏估计，它的结果近似于需要大量计算的k折交叉验证。

本文的内容主要转载自微信公众号“深度学习大讲堂”中的《深度学习中的激活函数导引》一文，可在公众号中阅读全文。

激活函数的定义与作用

在人工神经网络中，神经元节点的激活函数定义了对神经元输出的映射，简单来说，神经元的输出（例如，全连接网络中就是输入向量与权重向量的内积再加上偏置项）经过激活函数处理后再作为输出。激活函数可以定义为一种映射 $h:R\to R$，且几乎处处可导。

神经网络中激活函数的主要作用是提供网络的非线性建模能力，如不特别说明，激活函数一般而言是非线性函数。假设一个示例神经网络中仅包含线性卷积和全连接运算，那么该网络仅能够表达线性映射，即便增加网络的深度也依旧还是线性映射，难以有效建模实际环境中非线性分布的数据。加入（非线性）激活函数之后，深度神经网络才具备了分层的非线性映射学习能力。因此，激活函数是深度神经网络中不可或缺的部分。

几种常用的激活函数

以下摘抄一些常用的激活函数。

1. Sigmoid是使用范围最广的一类激活函数，具有指数函数形状。Sigmoid函数具有软饱和性，使得深度神经网络在二三十年里一直难以有效的训练，是阻碍神经网络发展的重要原因。具体来说，由于在后向传递过程中，sigmoid向下传导的梯度包含了一个$f’(x)$因子（sigmoid关于输入的导数），因此一旦输入落入饱和区，$f’(x)$就会趋近于0，导致向底层传递的梯度也变得非常小。此时，网络参数很难得到有效训练。这种现象被称为梯度消失。一般来说，使用sigmoid作为激活函数的网络在5层之内就会产生梯度消失现象。梯度消失问题至今仍然存在，但被新的优化方法有效缓解了，例如DBN中的分层预训练，Batch Normalization的逐层归一化等。

   Sigmoid的饱和性虽然会导致梯度消失，但也有其有利的一面。例如它在物理意义上最为接近生物神经元；$(0, 1)$的输出还可以被理解为概率，或用于输入的归一化，例如Sigmoid交叉熵损失函数。

2. tanh也具有软饱和性。但是使用tanh作为激活函数的网络收敛速度要比sigmoid快。因为tanh的输出均值比sigmoid更接近0，SGD会更接近 natural gradient，从而降低所需的迭代次数。

3. ReLU与传统的sigmoid激活函数相比，ReLU能够有效缓解梯度消失问题，从而直接以监督的方式训练深度神经网络，无需依赖无监督的逐层预训练，这也是2012年深度卷积神经网络在ILSVRC竞赛中取得里程碑式突破的重要原因之一。

   ReLU在x<0时硬饱和。由于x>0时导数为1，所以，ReLU能够在x>0时保持梯度不衰减，从而缓解梯度消失问题。但随着训练的推进，部分输入会落入硬饱和区，导致对应权重无法更新。这种现象被称为“神经元死亡”。ReLU还经常被“诟病”的一个问题是输出具有偏移现象，即输出均值恒大于零。偏移现象和神经元死亡会共同影响网络的收敛性。

4. PReLU是ReLU的改进版本，具有非饱和性。与LReLU相比，PReLU中的负半轴斜率a可学习而非固定。虽然PReLU引入了额外的参数，但基本不需要担心过拟合。与ReLU相比，PReLU收敛速度更快。因为PReLU的输出更接近0均值，使得SGD更接近natural gradient。

   原文中有一个论述很有意思。ResNet采用ReLU而非PReLU的原因可能在于：首先，对PReLU采用正则将激活值推向0也能够带来性能提升。这或许表明，小尺度或稀疏激活值对深度网络的影响更大;其次，ResNet中包含单位变换和残差两个分支。残差分支用于学习对单位变换的扰动。如果单位变换是最优解，那么残差分支的扰动应该越小越好。这种假设下，小尺度或稀疏激活值对深度网络的影响更大。此时，ReLU或许是比PReLU更好的选择。

其他激活函数还包括RReLU、Maxout、ELU、Noisy Activation Functions、CReLU、MPELU等，但个人感觉并没有以上几种常用，而且相对来说ReLU和PReLU的应用更广泛。

早就想看《天空之眼》，今天终于在A站看了。一部非常值得一看的政治惊悚片，猛一看好像是一个”电车难题”，不过仔细想想也不尽然，”电车难题”中的危机不由人来决定，而电影中是否应该为了消灭恐怖分子而牺牲无辜小女孩的危机却来自于官僚系统，英国军方需要首先与美国确认是否可以消灭持有美国护照的恐怖分子，正是这一次拖延导致了复杂的情况。

后续的剧情基本都是在这一复杂情况下展开，讽刺感极强，包括讨论牺牲小女孩是否合法时政客之间的踢皮球，担忧袭击的视频资料会外泄至社交网络，相对于咨询美国却毫不犹豫地选择在肯尼亚开展军事行动而不告知肯尼亚政府…在观看影片的过程中，观众会大骂圣母婊、斥责毫无底线可言的政客。而这些又都让观众思考程序正义的民主机制在遇到危机时怎么办，这一点和《寒战》类似。

角色的强烈对比使影片更有深意，比如将军在指挥室里相对冷血决定牺牲别人的女儿，而出了指挥室却要给自己的女儿更换买错了的娃娃，而我们又不应该指责他，因为这些恐怖分子如果不被消灭，他们可能会杀人更多的平民。对于英国军方的讽刺也挺到位，一个美军的Lieutenant却可以违抗一个英军Colonel的命令…

影片的矛盾也制造得也很有技巧，在小女孩这一危机产生之前还有特工的危机，不至于让观众犯困。再加上一票像艾伦·里克曼因、海伦·米伦的优秀演员，整个影片都给观众极大的愉悦

TITLE: Spatially Supervised Recurrent Convolutional Neural Networks for Visual Object Tracking

AUTHER: Guanghan Ning, Zhi Zhang, Chen Huang, Zhihai He, Xiaobo Ren, Haohong Wang

ASSOCIATION: University of Missouri, University of Missouri

FROM: arXiv:1607.05781

CONTRIBUTIONS

1. LSTM’s interpretation and regression capabilities of high-level visual features is explored.
2. Neural network analysis is extended into the spatiotemporal domain for efficient visual object tracking.

METHOD

The main steps of the method is as follows:

1. YOLO is used to collect rich and robust visual features, as well as preliminary location inferences.
2. LSTM is used to regress the location of the object in video frames.

Some Details

There are two streams of data flowing into the LSTMs. One stream includes

1. the feature representations from the convolutional layers $X_{t}$, for example the 4096-d feature from the fully-connected layer of VGG.
2. the detection information $B_{t,i}$ from the fully connected layers. Thus, at each time-step t, we extract a feature vector of length 4096. We refer to these vectors as Xt .

Another stream includes

1. the output of states from the last time-step $S_{t−1}$.

ADVANTAGES

1. The processing speed is fast because of the YOLO algorithm.
2. History of both location and appearance are considered.
3. End-to-end training is used in tracking, which means that a unified system is introduced.

DISADVANTAGES

1. YOLO may be not the best choice for detection.
2. Only single object is processed.

OTHERS

1. 4096-d feature is a representation for whole image, how about local representation.
2. Is there a method of temporal-full convolutional operation on 3D video, similar with fully convolutional operation on 2D image?

Though it is recommended using HTML5 in the field, Adobe FlashPlayer is still widely used. So it is of need to install it in our system. The main steps are as follows:

1. Download Adobe FlashPlayer from the official website. I choosed .tar.gz version.
2. Extract the archive using tar -zxvf install_flash_player_11_linux.x86_64.tar.gz
3. Copy files to corresponding directories.

1
2

sudo cp libflashplayer.so /usr/lib/mozilla/plugins/
sudo cp -r ./usr/* /usr/

deb是debian linus的安装格式，跟red hat的rpm非常相似，最基本的安装命令是：dpkg -i file.deb

dpkg 是Debian Package的简写，是为Debian专门开发的套件管理系统，方便软件的安装、更新及移除。所有源自Debian的Linux发行版都使用dpkg，例如Ubuntu、Knoppix 等。

以下是一些 Dpkg 的普通用法：

1. dpkg -i <package.deb> 安装一个 Debian 软件包，如你手动下载的文件。
2. dpkg -c <package.deb> 列出 的内容。
3. dpkg -I <package.deb> 从中提取包裹信息。
4. dpkg -r <package> 移除一个已安装的包裹。
5. dpkg -P <package> 完全清除一个已安装的包裹。和 remove 不同的是，remove 只是删掉数据和可执行文件，purge另外还删除所有的配制文件。
6. dpkg -L <package> 列出 安装的所有文件清单。同时请看 dpkg -c 来检查一个 .deb 文件的内容。
7. dpkg -s <package> 显示已安装包裹的信息。同时请看 apt-cache 显示 Debian 存档中的包裹信息，以及 dpkg -I 来显示从一个 .deb 文件中提取的包裹信息。
8. dpkg-reconfigure <package> 重新配制一个已经安装的包裹，如果它使用的是 debconf (debconf 为包裹安装提供了一个统一的配制界面)。

Yesterday, I thought it was the GPU driver that solve the heat problem of my laptop. Actually, I tried another method which is lowering the level of APM_level (Advanced Power Management level). In the manuel of hdparm, a part of description is as follow:

Get/set Advanced Power Management feature, if the drive supports it. A low value means aggressive power management and a high value means better performance. Possible settings range from values 1 through 127 (which permit spin-down), and values 128 through 254 (which do not permit spin-down). The highest degree of power management is attained with a setting of 1, and the highest I/O performance with a setting of 254. A value of 255 tells hdparm to disable Advanced Power Management altogether on the drive (not all drives support disabling it, but most do).

A sample of the commond of changing APM_level is:

1

sudo hdparm -B 192 /dev/sda

or we can add it to /etc/rc.local

I have just installed Ubuntu 14.04 on my old Thinkpad T410i. But after the machine booted, it is sooo hot that can be used for frying eggs. I searched much online. Some said that it is because Ubuntu 14.04 does not handle dual graphic units well. Though my old T410i does not show two graphic units, I tried installing NVIDIA Driver and it seems help a little to cool down the machine. The steps are as follow:

1. Add Nouveau to blacklist. Add blacklist nouveau to /etc/modprobe.d/blacklist.conf

2. Install Nvidia Driver and Prime

   1	sudo apt-get install nvidia-340 nvidia-prime

3. Install Nvidia Prime indicator

   1 2 3

   sudo add-apt-repository ppa:nilarimogard/webupd8 sudo apt-get update sudo apt-get install prime-indicator

   Then reboot the machine.