机器学习:Chapter4-5

Chapter 4: 决策树（decision tree）

what is decision tree？

基本流程

遵循分而治之(divide-and-conquer)策略,决策树学习基本算法如下:

<决策树学习基本算法.jpg>

算法line 8th, 如何选择最优划分属性?

划分选择

应使决策树的分支节点所包含的样本尽可能属于同一类别, 即节点的"纯度(purity)"越高越好.

信息增益(information gain)
信息熵(information entropy)是度量样本集合纯度的常用指标.
$Ent(D) = - \sum^{|y|}_{k=1}p_klog_2p_k$
$Gain(D,a) = Ent(D) - \sum^v_{v=1}\frac{|D^v|}{|D|}Ent(D^v)$
算法line 8th选择属性 $a^* = arg\ max\ Gain(D,a)$ .
信息增益对可取值数目较多的属性有所偏好.
增益率(gain ratio)
$Gain\_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}$
其中, $IV(a) = -\sum^v_{v=1}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$
增益率准则对可取值数目较少的属性有所偏好.

C4.5算法使用启发式: 先从后选划分属性中找出信息增益高于平均水平的属性, 再从中选择增益率最高的.

基尼指数(gini index)
数据集D的纯度使用基尼值测量: $Gini(D) = \sum^{|y|}_{k=1}\sum_{k' \neq k}p_kp_{k'}$ .
Gini(D)反映了从数据集D中随机抽取两个样本, 其类别标记不一致的概率, 故Gini(D)越小, 数据集D的纯度越高.
属性a的基尼指数定义为: $Gini\_index(D,a) = \sum^V_{v=1}\frac{|D^v|}{|D|}Gini(D^v)$ .
选择划分后基尼指数最小的属性作为最优划分属性: $a_* = arg\ min\ Gini\_index(D,a)$ .

Cart决策树使用"基尼指数"选择划分属性.

剪枝(pruning)处理

剪枝是决策树学习算法中解决"过拟合"的主要手段, 基本策略如下:

prepruning, 预剪枝: 在决策树生成过程中, 对每个节点在划分前先进行估计, 若当前节点的划分不能带来决策树泛化性能提升, 则停止划分并将当前节点标记为叶节点.
- 降低了过拟合的风险, 减少了决策树的训练时间开销和测试时间开销.
- 带来了欠拟合的风险.
postpruning, 后剪枝: 先从训练集生成一棵完整的决策树, 然后自底向上地对非叶节点进行考察, 若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升, 则将该子树替换为叶节点.
- 欠拟合风险小, 泛化性能往往由于预剪枝决策树.
- 训练时间开销比未剪枝决策树和预剪枝决策树都要大得多.

连续与缺失值

连续
在决策树学习中, 若遇到连续属性值, 可通过二分法(bi-partition)进行处理, 即将出现的连续属性的取值从小到大进行排序, 基于某个划分点t将D分为子集 $D^+_t$ (包含属性a上取值大于t的样本)和 $D^-_t$ (包含属性a上取值不大于t的样本).
如何选择最优的划分点: $Gain(D, a) = max_{t\in T_a} Gain(D,a,t) = max_{t\in T_a} Ent(D) - \sum_{\lambda\in\{-,+\}}\frac{|D^\lambda_t|}{|D|}Ent(D^\lambda_t)$
其中 Gain(D,a,t)是样本集D基于划分点t二分后的信息增益, 选择使 Gain(D,a,t)最大化的划分点.
note: 若当前节点划分属性为连续属性, 该属性还可作为其后代节点的划分属性.
缺失值

Q: 如何在属性值缺失的情况下进行划分属性选择?
给定划分属性, 若样本在该属性上的值确实, 如何对样本进行划分?

计算信息增益时带入不缺失该属性的样本所占的比例. 具体推广后的公式此处略.

多变量决策树(multivariate decision tree)

若把每个属性视为坐标空间中的一个坐标轴, 则d个属性描述的样本对应了d维空间中的一个数据点, 对样本分类意味着这个坐标空间中寻找不同类样本之间的分类边界, 决策树所形成的的分类边界具有特点: 轴平行(axis-parallel), 即分类边界由若干个与坐标轴平衡的分段组成.
多变量决策树: 能实现斜划分或者更复杂划分的决策树. (需要对属性的线性组合进行分析.)

Chapter 5: 神经网络(neural networks)

神经元(neuron)模型

神经元是神经网络中最基本的单元. 神经元接收到来自n个其他神经元传递过来的输入信号, 这些输入信号通过带权重的连接进行传递, 神经元接收到的总输入值与该神经元的阈值(threshold)进行比较, 然后通过"激活函数(activation function)"处理以产生神经元的输出.理想的激活函数是阶跃函数, 但其不连续、不光滑, 常用Sigmoid函数(亦称挤压函数, squashing function)作为激活函数.

许多个这样的神经元按一定的层次结构连接起来, 就得到了一个神经网络. 可将神经网络视为包含了许多参数的数学模型, 这个模型是若干个数学函数(如 $y_j = f(\sum_iw_ix_i-\theta_j)$ )相互嵌套而成.

感知机与多层网络

perceptron, 感知机: 由两层神经元组成, 输入层接受外界输入信号后传递给输出层. 输出层是M-P神经元, 亦称阈值逻辑单元(threshold logic unit). 感知机能容易地实现逻辑与、或、非运算. 神经网络的学习过程就是对神经元的连接权重和每个功能神经元的阈值进行学习. 将阈值 $\theta$ 看成固定输入为-1.0的哑结点(dummy node)所对应的权重w_{n+1<>\sub, 则将参数都统一为权重的学习. 对训练样例(x, y), 若当前感知机的输出为y', 则感知机权重调整规则如下:

$w_i \leftarrow w_i+\Delta w_i$ , 其中, $\Delta w_i = \eta(y-y')x_i$ 其中 $\eta$ 称为学习率(learning rate).}

感知机只能解决线性可分问题. 要解决非线性可分问题, 需使用多层功能神经元.(两层网络->单隐层网络) 输出层与输入层之间的神经元, 被称为隐层或隐含层(hidden layer), 隐含层和输出层都是具有激活函数的功能神经元(functional neural).
multi-layer feedforward neural networks, 多层前馈神经网络: 每层神经元与下一层神经元全互连, 神经元之间不存在同层、跨层连接.

误差逆传播算法

error BackPropagation, 误差逆传播算法(BP): 训练多层网络的常用算法. 主要目标是最小化训练集上的累积误差 $E=\frac{1}{m}\sum^m_{k=1}E_k$

标准BP: 每次仅针对一个训练样例更新连接权和阈值, 参数更新频繁, 针对不同样例的更新可能出现"抵消".
累积BP(accumulated error backpropagation): 直接针对累积误差最小化, 读取完整个训练集D后才对参数进行更新, 参数更新频率低.

训练集 $D = \{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}, x_i\in R^d, y_i\in R^l$
神经网络拥有d个神经元、l个输出神经元、q个隐层神经元.
输出层第j个神经元的阈值用θ_j表示, 隐层第h个神经元的阈值用λ_h表示.
输入层第i个神经元与隐层第h个神经元之间的连接权为v_ih, 隐层第h个神经元与输出层第j个神经元之间的连接权为w_hj.
隐层第h个神经元收到的输入为 $\alpha_h=\sum^d_{i=1}v_{ih}x_i$ , 输出层第j个神经元接受到的输入为 $\beta_j=\sum^q_{h=1}w_{hj}b_h$ , 其中b_h为隐层第h个神经元的输出.
假设隐层和输出神经元都使用的Sigmoid函数.

式(5.1): $y’^k_j = f(\beta_j-\theta_j)$
式(5.2): $g_j = -\frac{\partial E_k}{\partial y'^k_j}·\frac{\partial y'^k_j}{\partial \beta_j} = -(y'^k_j-y^k_j)f'(\beta_j-\theta_j) = y'^k_j(1-y'^k_j)(y^k_j-y'^k_j)$
式(5.3): $e_h = -\frac{\partial E_k}{\partial b_h}·\frac{\partial b_h}{\partial \alpha_h} = -\sum^l_{j=1}\frac{\partial E_k}{\partial \beta_j}·\frac{\partial \beta_j}{\partial b_h}f'(\alpha_h-\lambda_h)$
$= \sum^l_{j=1}w_{hj}g_jf'(\alpha_h-\lambda_h) = b_h(1-b_h)\sum^l_{j=1}w_{hj}g_j$
式(5.4): $\Delta w_{hj} = \eta g_jb_h$
式(5.5): $\Delta \theta_j = -\eta g_j$
式(5.6): $\Delta v_{ih} = \eta e_hx_i$
式(5.7): $\Delta \lambda_h = -\eta e_h$

# 标准BP算法
# input: 训练集D; 学习率η

在(0,1)范围内随机初始化网络中所有连接权和阈值
repeat
    for all (x_k,y_k) ∈ D do:
        根据当前参数和式(5.1)计算当前样本的输出 y'_k;
        根据式(5.2)计算输出层神经元的梯度项g_j;
        根据式(5.3)计算隐层神经元的梯度项e_h;
        根据式(5.4)~(5.7)更新连接圈w_hj、v_ih与阈值θ_j、λ_h .
    end for
until 达到停止条件

# output: 连接权与阈值确定的多层前馈神经网络

只需一个包含足够多神经元的隐层, 多层前馈网络就能以任意精度逼近任意复杂度的连续函数. 实际应用中, 经常使用"试错法(trial-by-error)"调整隐层神经元的个数.
缓解BP网络的过拟合:

early, stopping, 早停: 将数据集分成训练集和验证集, 验证集用来估计误差, 若训练集误差降低但验证集误差升高, 则停止训练, 返回具有最小验证集误差的连接权和阈值.
regularization, 正则化: 在误差目标函数中增加一个用于描述网络复杂度的部分, 对经验误差和网络复杂度进行折中.

全局最小与局部极小

神经网络的训练过程可看做参数(连接权和阈值)寻优过程, 即寻找一组最优参数使得误差最小. "最优"一般包括两种:

local minimum, 局部极小: 对w和θ, 若存在ϵ>0使得 $\forall(w;\theta)\in \{(w;\theta) | \parallel (w;\theta) - (w^*;\theta^*) \parallel \leq \epsilon \}$ , 都有 $E(w;\theta)\geq E(w^*;\theta^*)$ 成立, 则 $(w^*;\theta^*)$ 为局部极小解.
global minimum, 全局最小: 若对参数空间中的任意 $(w;\theta)$ 都有 $E(w;\theta)\geq E(w^*;\theta^*)$ 成立, 则 $(w^*;\theta^*)$ 为局部极小解.

局部极小解是参数空间中的某个点, 其邻域点的误差函数值均不小于该点的函数值; 全局最小解是指参数空间中所有点的误差函数值均不小于该点的误差函数值. 显然, 参数空间内梯度为零的点, 只要其误差函数值小于邻点的误差函数值, 就是局部极小点. 可能存在多个局部极小值, 但只会有一个全局最小值.
"基于梯度的搜索"是使用较为广泛的参数寻优方法. 但在存在多个局部极小的情况小, 不一定能找到全局最小, 如何跳出局部极小呢?

以多组不同参数值初始化(从多个不同的初始点开始搜索)多个神经网络, 训练后取误差最小的解作为最终参数.
simulated annealing, 模拟退火技术: 在每一步都以一定的概率接受比当前解更差的结果, 有助于跳出局部极小. 每步迭代过程中, 接受"次优解"的概率随时间的推移而逐渐降低, 从而保证算法稳定.
随机梯度下降: 标准梯度下降法精确计算梯度, 而随机梯度下降在计算梯度时加入了随机因素, 即便陷入局部极小, 计算出的梯度仍可能不为零, 有机会跳出局部极小继续搜索.
genetic algorithm, 遗传算法: 遗传算法详解 https://www.jianshu.com/p/ae5157c26af9 .

heuristic algorithm, 启发式: 一个基于直观或经验构造的算法, 在可接受的花费(计算时间和空间)下给出待解决组合优化问题的每一个实例的可行解, 该可行解与最优解的偏离程度一般不能预计.

其他常见神经网络

RBF网络

radial basis function network, 径向基函数网络: 一种单隐层前馈神经网络, 使用径向基函数作为隐层神经元激活函数, 输出层则是对隐层神经元输出的线性组合.
训练过程: 1. 通过随机采样或聚类等方式确定神经元中心c_i; 2. 利用BP算法确定参数w_i和β_i .

ART网络

adaptive resonance theory network, 自适应谐振理论网络: 竞争型学习的重要代表, 网络由比较层、识别层、识别阈值、重置模块构成.

竞争型学习(competitive learning), 一种无监督学习策略, 网络的输出神经元相互竞争, 在每一时刻仅有一个竞争获胜的神经元被激活, 其他神经元的状态被抑制(胜者通吃原则, winner-take-all).

SOM网络

self-organizing map network, 自映射网络: 竞争型学习的代表之一, 将高维输入数据映射到低维空间, 同时保持输入数据在高维空间中的拓扑结构, 即将高维空间中相似的样本点映射到网络输出层中的邻近神经元.

训练过程: 接收到一个训练样本, 每个输出层神经元会计算该样本与自身携带的权向量之间的距离, 距离最近的神经元称为竞争获胜者, 称为最佳匹配单元(best matching unit). 最佳匹配单元及其临近神经元的权向量将被调整, 以使得这些权向量与当前输入样本的距离缩小. 这个过程不断迭代, 直至收敛.

级联相关网络

结构自适应网络: 一般神经网络模型假定网络结构是事先固定的, 训练目的是利用训练样本来确定合适的连接权、阈值等参数; 结构自适应网络则将网络结构也当做学习的目标之一, 希望在训练过程中找到最符合数据特定的网络结构.

cascade-correlation network, 级联相关网络: 结构自适应网络的重要代表. 无需设置网络层数、隐层神经元数据, 训练速度较快, 但数据较小时容易过拟合.

级联: 指建立层次连接的层级结构. 训练开始时, 只有输入层和输出层, 处于最小拓扑结构; 随着训练的进行, 新的隐层神经元逐渐加入, 从而创建起层级结构.
相关: 指通过最大化新神经元的输出与网络误差之间的相关性来训练相关的参数.

Elman网络

recurrent neural network, 递归神经网络: 不同于前馈神经网络, 网络中可以出现环形结构, 从而让一些神经元的输入反馈回来以作为输入信号. 结构与信息反馈, 使得网络在t时刻的输出不仅与t时刻的输入有关, 还与t-1时刻的网络状态有关, 从而能处理与时间有关的动态变化.
Elamn: 递归神经网络的代表之一, 结构与多层前馈网络相似, 但隐层神经元的输出会被反馈回来, 与下一时刻输入层神经元提供的信号一起, 作为隐层神经元在下一时刻的输入.

Boltzmann机

神经网络中有一类模型为网络状态定义一个"能量(energy)", 能量最小化时网络达到理想状态, 而网络的训练就是在最小化能量函数.
Boltzmann机: 一种基于能量的模型(energy-based model), 神经元分为显层和隐层——显层用于数据的输入输出, 隐层则是数据的内在表达. 神经元都是布尔型的, 状态1代表激活, 0代表抑制.训练过程将每个训练样本视为一个状态向量, 使其出现概率尽可能大.

深度学习(deep learning): 可简单理解为很深层的神经网络. 对输入信号进行逐层加工, 把初始的、与输出目标联系不太密切的输入表示转化为与输出目标联系更密切的表示. 即通过多层处理, 逐渐将初始的低层特征表示转化为高层特征表示, 用简单模型完成复杂的分类等学习任务.
详等后续.

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 202,905评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,140评论 2赞 379
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 149,791评论 0赞 335
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,483评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,476评论 5赞 364
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,516评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,905评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,560评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,778评论 1赞 296
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,557评论 2赞 319
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,635评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,338评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,925评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,898评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,142评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,818评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,347评论 2赞 342