Tag: ML

Phase-Functioned Neural Networks for Character Control

理论部分:

 
 

http://theorangeduck.com/page/phase-functioned-neural-networks-character-control

 
 

视频内容:

讲者背景:角色动画机器学习方向的博士毕业,

动画系统,中间的就是黑盒,就是动画系统

用户输入动画系统的是按钮的指向信息,如图所示的平面的指向,是比较高级的指令,比如我们想走向哪个方向。

动画系统则像是巨大的状态机,不同的状态对应不同的动画,之间会有动画混合。这个复杂的系统直接写代码比较复杂,很难维护,

因此我们重新考虑能不能用一个简单的算法来实现这个复杂的动画交互系统。

我们希望动画系统的输入输出就变成一些参数而已。

我们再来看原来的复杂的动画系统,如果把输入输出看作是动画模型的参数,那么也是可以做到的,就像是在一个巨大的数据库里面挑东西输出。

因此我们希望做到的第二点就是直接输出下一个pose

当然可以,基本思想就是把动画系统当作是黑盒,我们给一些输入就有想要的输出,后面具体讲做法。

输入x:Trajectory Positions, Directions, Heights;Previous Joint Position, Velocities…

输出y:各关节的transform信息

要做训练我们首先需要数据,采用的是动作捕捉,每一段约十分钟,一共约两小时的非结构化的数据。

高度匹配的问题,我们捕捉的数据默认脚就是完全贴合地面的,以此来训练,我们是了大量的各种不同的地面来获得相关的数据。

然后我们来看怎么学习

一个神经网络事实上就是一个函数,

比如这个函数就可以让输入得到相应的输出

我们的函数的输入输出如图所示

而这个可以量化为vectors作为输入输出

如果是单层的最简单的NN举个例子可以像是这样,wb这两个参数就是我们需要学习得到的结果。

输入就是已知的xy

输出就是学习得到的结果wb,如这里所示

最终我们得到的这个函数叫做行为函数

这里可能涉及各种不同的函数,比如这个是非线性混合函数

这两个就是很类似的

如果是深度学习的多层的函数,其表现就是这样

这个例子就是一个三层的神经网络公式

训练的做法就是每次输入值,然后跟据得到的结果衡量错误,然后在调整网络的参数,这就是基本的思路

我们采用了GPU运算节省时间

Phase-functioned NN意思就是我们采用了一种特殊的NN方法,对于不同的motion采用不同的网络权重,避免混合motions,细节请看paper

这是我们最终获得的,简单的动画驱动模型来替代state machineg和blend tree

然后展示demo

性能展示

结论

 
 

首先完整看一遍PPT:

SIGGRAPH上面的演讲PPT

目标:游戏中的角色控制做到快速紧凑的表现力

最终结果展示

第一部分背景

前人的工作存在的可改进之处:

  1. 需要将整个数据库全存放于内存
  2. 需要手动处理数据
  3. 需要一些复杂的加速方法

NN可以带来什么帮助呢?

  1. 虚拟的无限制的数据容量(任意动作)
  2. 快速的实时的低内存使用

但是怎么来生成动作呢?

CNN:学习用户角色控制信号与角色行为的关系

demo

问题是什么?

存在歧义,会发生相同的输入得到不同的角色行为结果

实际上:

  1. 需要特殊处理解决掉歧义
  2. 一开始需要提供所有的输入轨迹情况
  3. 多层CNN对于游戏来讲还是太慢了

RNN:学习从前一帧到后一帧的对应关系

demo

RNN结果质量:

  1. 只能坚持10
  2. 无法避免漂浮
  3. 无法避免歧义

总结我们面对的问题:

  1. 我们怎么去处理大规模的数据
  2. 我们怎么解决歧义的问题
  3. 我们怎么样让生成的结果看上去不错

数据捕捉部分

非结构化的数据捕捉,一共补了差不多两小时的数据,每一段十分钟左右,摆放了很多桌子椅子来模拟复杂地形,使得尽量包含各种复杂的情况

demo

demo

地形匹配

  1. 我们希望地形数据和运动数据一起加入学习
  2. 但是同时捕捉运动和地形数据是比较麻烦的
  3. 制作一个高度图数据库,然后让一段运动匹配高度图中的一块

例子

参数设置:

  1. 最终效果不错
  2. 角色轨迹采用窗口模式
  3. 加上了步态,地形高度等信息

神经网络部分

PFNN:一个phase函数看作是权重的NN

phase是0-2pi的标量,表示的是当前locomotion cycle下当前的pose

图示:输入是当前帧pose,输出是下一帧pose,NN里面的参数是phase function

demo

特征:前回馈NN,有两个隐藏层,每层有512个影藏单元,ELU驱动函数

输出是NN的权重,循环三次方函数差值四个控制点,每个控制点由一组NN权重组成。

训练算法:

  1. 输入phase生成权重
  2. 使用权重和输入值到nn得到输出值
  3. 衡量输出错误
  4. 反向传播nn和phase函数更新控制点的值

结果

demo

结论

phase函数预计算:因为这个函数的计算对于游戏来说是比较耗时的

  1. 控制数值范围 0-2pi,在这个范围内可以预计算
  2. 运行时对于预计算的结果做差值
  3. 得到速度和内存之间的平衡

性能参数

缺点:

  1. 模型的训练时间非常耗时
  2. 对于美术的编辑和修改,不能直接得到正反馈
  3. 很难预测结果,有问题也不能直接知道为什么

优点:

  1. NN很容易处理大量的数据,可以得到万般种结果
  2. 语义分解解决了歧义的问题
  3. 简单的结构和参数化的使用方式很容易控制质量

 
 

 
 

实践部分两步走:

  1. 先看demo怎么实现的
  2. 再看network怎么处理的

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

AIAnimation使用代码分析

历尽艰难跑起来了,问题是没有办法操作,猜测Ubuntu和windows的操作代码不兼容,代码分析部分的主要目标之一就是把操作改掉:

 
 

代码结构分析

一切从main函数开始:

  • 首先是SDL初始化,Simple DirectMedia Layer(SDL) is a cross-platform development library designed to provide low level access to audio, keyboard, mouse, joystick, and graphics hardware via OpenGL and Direct3D. 可以说是一个常用的跨平台opengl支持库。

    这边就是想到应该不会是操作兼容性的问题导致不能动,一看代码原来是只支持手柄。

    可惜的是,windows平台上面跑起来好卡,感觉帧率小于10帧!

  • GLEW初始化

  • 资源加载

    • Options 里面定义的是一些我们可以修改的设置选项:

    • CameraOrbit 则是相机初始化设置

    • LightDirectional 场景光照初始化设置

      这里就是一堆GL设置

    • Character 角色初始化设置

      这部分是这里的角色的定义信息和加载,这部分很重要!

      首先我们来看一下存储的角色数据的文件包涵下面四个,坑爹的采用了二进制存储:

      顶点,三角形,父子关系,xforms信息分别四个文件。

      读文件的函数这边也很简单,将数据直接存进对应的容器,角色数据结构信息如下:

      这部分最后就是一个前向动力学的实现,这个很简单,就是子类跟着父类运动。

    • Trajectory 路径初始化设置

      这里就是定义了运动路径的数据结构,如下所示:

    • IK 初始化设置

      Ik数据结构如下所示:

      这里还提供了一个two_joint函数,这个后面用到再讲,因为暂时也看不出来其功能。

    • Shader 相关

      这部分就是加载shader的函数,并将其运用到opengl

    • Heightmap 高度图初始化设置

      这边主要来看一下高度数据的读取和存储

      高度文件数据示例,包括两个文件:

       
       

       
       

      Load()函数就是一个一个读取float存储在 vector<vector<float>> data 里面:

      xxx.txt 信息就是用来生出 data,xxx_ao.txt 信息则是用来生出 vbo/tbo(坐标,颜色等信息);vbo_data/tbo_data(索引坐标信息)。

    • Areas 区域初始化设置

      这部分的数据结构如下:

    • PFNN模型

      模型的加载和初始化,首先来看其数据结构:

      ArrayXf 这个数据结构是Eigen下面存储 float array的结构。Load函数底下就是加载的文件,很多很多文件啊!

      我们来看上图所示的文件结构就可以发现,pfnn这个网格模型相关的数据内容,主要包含的就是网络模型和角色。

    • 加载游戏世界

      load_world 这些函数,目前来看这些函数里面主要是在做地形标记,所以来说这程序跑起来需要做的地形标记?

  • Game Loop 部分
    • Input处理

      目前只支持手柄,SDL包含跨平台的输入交互模块,细节不解释,见下图

      但事实上不是所有的交互都在这里,在渲染那边很多的主要操作都是直接写在渲染的部分的,但都是用了SDL接口。

    • 渲染

      一共包含前处理,渲染处理,后处理三部分,我们分别来看。

 
 

前处理

  • 更新相机(直接按键确定)

    右手柄摇杆控制相机旋转,LR控制zoomin/zoomout,然后直接作用于相机参数。

  • 更新目标方向和速度(直接按键确定)

    这部分也是直接响应按键输入,按键就确定了用户期望的目标方向和速度。

  • 更新步态(算法数据前处理第一步)

    通过上一时刻的 trajectory 参数 和 options 参数来确定当前时刻 trajectory 的参数。

  • 预测未来的 Trajectory(算法数据前处理第二步)

    通过上一步获得的 trajectory 参数 和 character 参数,来混合获得 trajectory_positions_blend 这个对象

  • 碰撞处理(算法数据前处理第三步)

    根据 areas 的 walls 的信息,来调整 trajectory_positions_blend 的值。

    在这里,又做了一步将 trajectory_positions_blend 的值写回 trajectory

  • 跳跃(算法数据前处理第四步)

    根据 areas 的 jump 的信息,来调整 trajectory 的值。

  • Crouch 区域(算法数据前处理第五步)

    根据 areas 的 crouch_pos 的信息,来调整 trajectory 的值。

  • 墙(算法数据前处理第六步)

    根据 areas 的 walls 的信息,来直接调整 trajectory 的值。

  • Trajectory 旋转(算法数据前处理第七步)

    trajectory->rotations 的值调整

  • Trajectory 高(算法数据前处理第八步)

    根据 heightmap 的值来调整 trajectory 的值

  • 输入的 Trajectory 位置方向(pfnn输入内容第一步)

    Trajectory 信息来获得 pfnn->Xp

  • 输入的 Trajectory 步态(pfnn输入内容第二步)

    Trajectory 信息来获得 pfnn->Xp

  • 输入的 当前的 Joint 位置速度和旋转角度(pfnn输入内容第三步)

    Trajectory 信息来获得 pfnn->Xp

  • 输入的 Trajectory 高度(pfnn输入内容第四步)

    Trajectory 信息来获得 pfnn->Xp

  • Perform Regression 【核心步骤:模型predict

    上面在设置的是pfnn的参数,而这里还需要设置的是predict函数的传入参数,是character->phase

  • 时间处理,这一步就是计算一下predict时间,debug用。
  • Build Local Transformpfnn输出)

    这一步就是运用pfnn的输出结果,来获得角色每个关节的position/velocity/rotation

    这里还需要的一步就是上面得到的关节数据是世界坐标,要转换到局部坐标。

  • IK 处理

    这一步就是对上面获得的关节数据,一个一个的应用到角色的IK关节!

 
 

渲染处理

  • Render Shadow
  • Render Terrain
  • Render Character
  • Render the Rest
  • Render Crouch Area
  • Render Jump Areas
  • Render Walls
  • Render Trajectory
  • Render Joints
  • UI Elements
  • PFNN Visual
  • Display UI

这里都是opengl使用,和AI数据的使用无关,就不在赘述。

 
 

后处理

  • Update Past Trajectory

    Trajectory 数据传递更新

  • Update Current Trajectory

    Trajectory数值计算更新

  • Collide with walls

    Trajectory 碰撞更新

  • Update Future Trajectory

    Trajectory 依据 pfnn结果来做更新

  • Update Phase

  • Update Camera

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

AI4Animation 工程

这里尝试非常多次还是没有办法对于里面的demo信息完整打开且没有报错,可以跑的demo。

因此我们在AIAnimation的基础上首先来看看这个工程怎么使用起来。

 
 

首先来看重点在角色,我们来看其角色的构造:

上面是两个demo的使用结构,可以看到就一个重要的csharp文件,我们来对比分析。

Original对应的是Siggraph17的内容,Adam对应的是Siggraph18的内容,我们先来看17。

 
 

首先看大的结构:

第二个类继承Editor对象,作用是在editor里面形成层级菜单Animation,其余的三个则是分别由另外的三个类来完成。

这三个对象也分别形成了三个子标签菜单项,如上面所示的图。


  • NeuralNetwork 这个类,里面只做了一件事情,就是让用户选择NN模型,也就是说这个类处理的是交互UI表现和逻辑,没有其他。NN里面应该包含的信息都在Model这个类里面。下图就是model里面存储的数据结构:

    然后我们来看接口函数:

    这边是为了兼容和扩展多种的NN方法设置的接口。

    剩下的就是一些Tensor相关的函数,Tensor是对Eigen数据的封装,其真实的计算实现都是由Eigen实现的,这边同时提供了一堆的数据结构关联操作的方法。

    最后model里面涉及的比较重要的内容就是Parameters,这边unity里面主要做的就是加载读取和存储方法。

  • Controller 这个类,处理的是Input,主要就是WSADQE. 还有一个很重要的变量是Styles数组,记录的应该是状态权重。
  • Character 这里做的就是驱动骨架运动。

而作为核心的中介数据 Trajectory 这个类,其就是一组数据点数组,并且包含对这个数组,单个点的操作方法。单个点的数据内容很丰富,包括各种变换和状态等:

 
 

所有的核心使用方法就是在Update函数里面,这边的做法应该是和AIAnimation里面是一模一样的,我们可以对比一下:

  • 只有存在NN模型的情况下,才会执行下面的所有内容。
  • Update Target Direction / Velocity

    这里做的就是:

    TargetDirection = TargetDirection Trajectory定义的当前位置 跟据 TargetBlending 权重混合。

    TargetVelocity = TargetVelocity Controller输入速度 跟据 TargetBlending 权重混合。

  • Update Gait

    Trajectory.Points[RootPointIndex] 的每一个Style的值 = 当前值 和 用户是否点选了要成为该Style 跟据 GaitTransition 权重混合。

  • Predict Future Trajectory

    预测的位置 = 当前位置和前一个位置的差值的延续 和 TargetPosition 差值获得

    预测的style = 延续当前的style

    预测的方向 = 当前的方向 和 TargetDirection 差值获得

  • Avoid Collisions

    保证新的位置可靠,也就是考虑了碰撞。

  • Input Trajectory Positions / Directions

    给NN.Model喂数据,Trajectory的每一个Point的位置和方向(都是xz轴值)

  • Input Trajectory Gaits

    给NN.Model喂数据,Trajectory的每一个Point的Style数组

  • Input Previous Bone Positions / Velocities

    给NN.Model喂数据,Joints的每一个关节的位置和速度

  • Input Trajectory Heights

    给NN.Model喂数据,Trajectory的每一个Point的高度信息(y轴值)

  • Predict【利用模型运算】

  • Update Past Trajectory (轨迹上 i < RootPointIndex 的点)

    更新Trajectory.Points[i] 的每一个点的信息:i位置=i+1位置的值(意思就是向前取一个点)

  • Update Current Trajectory(轨迹上 RootPointIndex 所在的点)

    跟据NN的输出结果来构建一个新的点Trajectory.Points[RootPointIndex]的信息,设置其位置方向

  • Update Future Trajectory(轨迹上 RootPointIndex+1 < i < Trajectory.Points.Length的点)

    每个点新的位置 = 每个点原来位置 + 当前方向 与 跟据模型输出值混合得到的距离和方向 差值(这边做了多重的影响差值考虑)

  • Avoid Collisions

    同 5 做法一致

  • Compute Posture

    positionsrotations两个数组存每一个joint的变换;

    每个 positions[i] = NN返回结果 * 0.5 + 上一个位置按照上一个方向到达的这一个应该在的位置 * 0.5;

    每个 Velocities[i] = NN返回的结果

  • Update Posture

    每个joint的position,rotation直接取上一步数组中对应的值

  • Map to Character

    transform应用在角色上面

     
     

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

AIAnimation 工程安装

Machine Learning Techniques Lecture 15: Matrix Factorization


 
 

内容:

Matrix Factorization(矩阵分解)模型,一开始先讲linear network里面通过对ID这样的特征编码来萃取特征,然后讲基本的 matrix factirization演算法,要做的事情就是在两个特征之间交互的 做 linear regression,同时你也可以用SGD来做,这是一个有效率的方法,而且可以根据应用做适当的调整,最后总结了一下 extraction model。

 
 


 
 

上一讲:

Raidal Basis Function Network,就是把原来的原始数据通过k-means算法来找出代表,通过使用RBF函数来替代,然后整个方法就可以转化成linear aggregation问题来求解了。

 
 

这里:

Matrix Factorization

 
 


 
 

我们首先来回到机器学习基石课程最早讲过的,机器学习的目标就是从资料里面学习的到技能。例如从很多使用者那里收集的到了很多喜欢的电影的数据,每一笔资料就是某个使用者给某一部电影的分数,我们目标是得到那个使用者喜不喜欢还没上映的那部电影。棕色框就是一个实际问题的例子。

 
 

在上面的例子里面,x是一个抽象的特征,是一个编号。这样的数据怎么去做机器学习,就是这里要讲解的问题。

 
 


 
 

X 是抽象的,就是数值上没有意义,只是用来分类别的数据,比如ID,血型,程序语言。

 
 

但是我们目前学过的ML Model都作用于有数值特征的数据,例如线性模型,算分数的方式的前提就是数值有举例意义,NN等基于线性模型的方法也有这个要求。只有很少数的机器学习方法可以直接处理类别特征数据,比如讲过的 decision tree。

 
 

所以如果我们要对类别特征做机器学习,那么第一步就是将类别特征数据转换成数字数据特征,这个过程叫做encoding。

 
 

一种简单的encoding方法叫做 Binary Vector Encoding。比如血型有四种,用一个四维的向量来表示,每一种可能性占一行,1表示是的。

 
 


 
 

原来的数据每一条,都是一个( 类别 x_n, 分数 y_n)的向量表示,可以把数据整合一下,把所有相同的x_n数据合成一个,就有(类别x_n,分数向量(分数向量里面存在不知道的数据用?表示))。

 
 

我们怎么样从这么复杂的抽象数据里面做特征萃取呢,NN是典型的特征转换模型,NN里面每一层都可以看作是特征的萃取。例如电影偏好的问题,可以把NN里面的x看作是用户,y看作是电影,整个学习参数的过程就是特种萃取。N-d~-M NNet,N表示的是使用者的个数,M表示的是电影的个数,d~就是中间节点的个数。

 
 

tanh在这里不是必要的,因为这里的输入向量的特征是,里面只有一个1,其他都是0,也就是进出都是sparse的,简单,不需要转换了,因此可以使用这个特征来简化模型,也就是linear Network。

 
 


 
 

因此我们考虑 Linear Network,先来命名如上面所述,这样以后就有 h(x) = W^T * V * X。因为X只有n列是1,其他都是0,因此我们可以用 V_n 来表示 V * X 的结果,这样就有了上面表示的 hypothesis 结果。

 
 


 
 

练习

 
 


 
 

上面我们讲到了 Linear Network Model,在电影这个应用里面 V * x 的意义是对所有的电影序列 x 做了转换,然后再跟 w 做线性组合就是结果。或者对于某一部电影m来讲,关心的就只是 h_m(x) ,对应的x的那一行只有m列是1,其他都是0,这就是一个转换过了以后的线性模型。

 
 

我们想要的输出是 r_nm = W_m(权重)* V_n(n个使用者),这个结果要和我们已知的一些数据 y_n 接近,那么对于总体来说就可以写成一个Ein最小化的公式,如上面所示, r_nm – W_m^T * V_n 表示的就是已知的使用者评价和模型输出结果的误差,灰色的部分不影响最佳化结果。Ein 最小化,表示的是这个网路我们可以学到的是,一个是怎么做转换,一个是第二层的权重是多少。

 
 


 
 

矩阵化:

 
 

R每一行代表一个使用者,每一列代表一部电影,格子里面就是评分;原来的目标求解公示就可以表示成矩阵形式,如上面所示。如果我们可以把不健全的R分解成V,W,那我们就得到了使用者的特征,得到了每一部电影怎么样对这个特征做线性组合来做最佳化预测。我们从已经知道的评分出发,想办法去反推到底对于使用者来说哪些特征是重要的,对于电影来说他有那些元素,也就是说对于R的每一格都有这样的物理上的意思。举例说就是这个用户喜欢喜剧片,这部电影是喜剧片,那么用户喜欢,反之侧不然。

 
 

矩阵分解这样的方法常常被用来把抽象的特征转化成真正有意义可以进一步处理的特征。

 
 


 
 

我们怎么来做学习呢?

 
 

上面已经得到了一个最佳化问题,变数是W,V,也就是说有两个Sum动作。这个问题有两组变数,因此可以考虑 alternating minimization方法,k-means里面讲过。首先固定V,最佳化W,就是一堆的线性模型,对于每一部电影就是一个线性模型,就是做linear regression解决问题。然后固定W,最佳化V,由于上面的问题WV的角色可以看作是对称的,因此也是一个linear regression求解。这个算法叫做 alternating least squares algorithm。

 
 


 
 

alternating least squares algorithm

  1. 初始化随机的设定值,
  2. 固定V求解W,固定W求解V,
  3. 交叉迭代第二步优化直到Converge,而且一定会收敛。

 
 


 
 

这两者都存在着矩阵分解的概念,来做比较。

 
 

Linear Autoencoder:X = W(W^T * X)

第一层的W做编码,第二层的W做解码,出发点是特别的线性NN,可以看作是分解成一号矩阵W,二号矩阵(W^T * X);错误衡量用的是平方错误,但是矩阵中每一格都知道,因此算所有格子;解是全局最优,就是eigenvector;适合用来做资料的降维。

 
 

Matrix Factorization:R = V^T * W

也是一个线性NN,分解成一号矩阵V,二号矩阵W;错误衡量用的是平方错误,但是矩阵中有很多不知道,因此只算知道的;解是局部最优;适合萃取特征。

 
 

Linear autoencoder 可以看作是 matrix factorization 的特例。

 
 


 
 

练习

 
 


 
 

我们上面讲了 alternating least squares algorithm 来解决 Matrix Factorization 的问题,这里带大家来看能不能使用 Stochastic gradient descent (随机的从资料里面选取一笔资料,在这比资料有关的error衡量上面去算梯度,做梯度下降,好处是每一轮只涉及到一个点,计算很有效率,程序实现容易,可以使用不同的错误衡量方式)来求解 Matrix Factorization。

 
 


 
 

首先写出错误衡量公式,用的是平方错误。然后对模型里面所有的变数做偏微分,同样因为W,V是只有一行有意义,对于每一个nm对来说,所以就有蓝色的部分结果。

 
 

我们来看 Gradient 其包含两项,第一项是 residual(余数,我们的目标和现实的差距),第二项是 the other feature vector(另外一个特征向量)。

 
 


 
 

由上面就可以得到用 SGD 做矩阵分解的方法:

一开始的WV是随机的设置一些值,然后

  1. 随机选择一个点
  2. 计算余数项
  3. 更新SGD,公式如上面所示

 
 

非常的有效率,非常的常用。

 
 


 
 

最后给一个例子。

 
 

训练的资料比测试的资料获得的时间是比较早的,也就是有时间上的分布关系。这时候需要注重时间比较晚的资料。

 
 


 
 

练习

 
 


 
 

到此的四讲里面我们讲的是 Extraction Model,就是把资料的转换纳入到机器学习的过程中来,通过资料的转换来学习到隐藏的特征,再使用线性模型来求解的完整过程。

 
 

NN/DL :前面所有的层都是在做特征转换,最后一层就是线性模型

RBF Network:最后是一个线性模型,前面求RBF的中心就是转换后的特征

Matrix Factorization:同样最后一层是线性模型W,前面在做特征转换V,但是这里面WV是对称的,可以互换。

Adaptive/Gradient Boosting:其中的hypothesis可以看作是资料转换,最后一层就是带权重的线性转换。

K Nearest Neighbor:可以看作是用最近的中心点当作是原来的特征,就是特征转换,最后也是一个线性模型得结果。

 
 


 
 

除了模型之外,我们还通过模型来交给大家一些技巧:怎么从你的资料里面萃取出有用的特征。

 
 

NN/DL :SGD,透过 backprop 来很有效率的算出梯度的值;autoencoder,通过非监督式的方法让整个方法在一个比较好的权重开始。

RBF Network:介绍了 k-means clustering,非监督式的方式来获得分群的资料

Matrix Factorization:SGD,alternating leastQSR 交互的做线性回归

Adaptive/Gradient Boosting:functional gradient descent 来推导出怎么萃取g。

K Nearest Neighbor:lazy learning 方法,就是训练的时候不做什么事情,而是测试的时候做事情。

 
 


 
 

Extraction Models

 
 

好处:对人来说容易使用,不用拍脑袋设计特征;非常的powerful;

坏处:不是凸函数,容易得到局部最优解而不是全局最优解;容易overfitting,

 
 


 
 

练习

 
 


 
 

总结:

Matrix Factorization(矩阵分解)模型,一开始先讲linear network里面通过对ID这样的特征编码来萃取特征,然后讲基本的 matrix factirization演算法,要做的事情就是在两个特征之间交互的 做 linear regression,同时你也可以用SGD来做,这是一个有效率的方法,而且可以根据应用做适当的调整,最后总结了一下 extraction model。

 
 

下一讲:

给大家一些机器学习技法方面的总结

Machine Learning Techniques Lecture 14: Radial Basis Function Network


 
 

内容:

Radial Basis Function Network 模型,其hypothesis就基本是一堆RBF,比如高斯函数,用这些RBF作为代表来取代NN里面的神经元;学习的过程中如果决定了中心是哪些之后,剩下的就是做一步linear aggregation;然后我们介绍了k-means演算法来用于决定中心,其算法的核心就是 alternating potimization,对里面的变数交叉做最佳化;最后我们举例图示加深印象。

 
 


 
 

回顾:Deep Learning 是NN的延伸,NN很多很多层的时候,要怎么克服一些困难,比如训练的时候需要好的初始值,denoising autoencoder 就是一种做法(non-linear PCA),其和统计里面用来做资料处理的PCA 有一定的关联性

 
 

这里: Radial Basis Function Network

 
 


 
 

回顾一下很早以前讲的 Gaussian SVM,在SVM里面配合上gaussian kernel,就可以做到在一个无线多维转换的空间里面想办法找一个胖胖的边界。

 
 

如果从最后的结果得到的hypothesis来看,我们也可以说Gaussian SVM做的事情就是拿一堆Gaussian来,然后把他们做线性组合,他们的中心在Support Vector这些资料点上。

 
 

Gaussian Kernel 也叫做 Radial Basis Function(RBF) kernel,radial 代表你今天算的函数值只和x与中心点的距离有关,basis function 表示的是我们要拿来做线性组合的系数。

 
 

我们如何看待Gaussian SVM输出的函数呢,如果我们定义g_n如上面所示,其物理意义是看新的x与xn到底够不够近,越近的就给他越多的票用来投y_n是正一还是负一。我们的SVm就可以表达出那这些g_n来做加权线性组合,也就是以g_n为基础的linear aggregation。

 
 

Radial Basis Function (RBF) Network 就是这个概念的延伸,就是说怎么去线性组合radial hypothesis(只和半径有关的函数)。

 
 


 
 

为什么叫Network?

 
 

我们来看看NN和RBF的图如上面所示,RBF的第一层是Centers,就是点到中心点的距离,最后一层则是投票的动作。因此两者再输出的部分都是线性模型,类似;不一样的是第一层,NN里面是做内积在经过tanh转换,RBF是算距离,也可以把RBF看作是NN的一个分支。

 
 


 
 

蓝色部分公式就是RBF Network的hypothesis长相,蓝色部分就是RBF Basis长相,中心点是mu,Gaussian是其中一种;红色部分就是投票权重。

 
 

重要的参数:mu表示的是中心点,beta就是投票权重。

 
 

上面举得例子,RBF就是gaussian;Output就是binary classification。

 
 


 
 

kernel是把我原来的两个点转换到某个Z空间,在Z空间里面算一个向量内积。因为这样的操作关系,所以kernel就需要受到Mercer’s condition的保障,就是说其转换矩阵要是半正定的。Kernel描述的可以说是一种相似性,两个原来的向量的相似性通过转换到z空间来描述这种相似性。

 
 

RBF 则可以看作是在描述一种相似性,这个相似性则是可以直接用当前空间内的距离来描述。

 
 

因此 Kernel 和 RBF 可以看作是两种对相似性的衡量方式。Gaussian则是两者都可以解释。他们两个之外也有一些其他的不一样的相似性的表达方式,比如NN里面每一个神经元做的事情也是在比较两个向量的相似性,一个是输入的向量,一个是权重的向量,再比如DNA序列的比较,两者的相似性来源于两者互相变化的最小修改代价。

 
 

RBF Network 告诉我们的是,相似性是一个很好的定义特征转换的方法。

 
 


 
 

练习

 
 


 
 

上面讲了RBF network的基本概念,就是要找到一些中心,然后这些中心对应的RBF用beta这些系数做线性组合。那怎么找中心,干脆就把所有我们看见过的资料点统统当作是中心,这样的RBF Network叫做 full RBF Network(N笔资料就有N个中心)。他的物理意义就是我们看过的每一笔资料都应该对它周围的那些点有beta大小的影响力。举例说假设每个点有同样的影响力,相当于用距离的远近作为权重来投票,就如上面的公示所示,新的点的权重就是周围所有点的影响力的加权和(aggregation)。

 
 


 
 

这样的方法和机器学习里面的另外一些方法有有趣的相似性。我们看我们上面去确认full RBF Network结果的时候算的是一堆高斯函数来投票。这里面和你的x最近的已知点的高斯函数的权重是最高的。高斯函数衰减很快,里面最大的一项很容易掌握全局结果,因此很多时候找出最大一项作为结果就好,不需要去计算全部(selection instead of aggregation)。新的物理意义就是通过最接近x的已知点的结果来决定x,这个方法叫做好邻居法(nearest neighbor)。还可以扩展这个方法,让几个邻居来投票,这样的方法叫做 k-nearest neighbor。

 
 

这里的 k nearest neighbor 方法和 full RBF network 一样都是偷懒的方法(只有在输出的时候才去使用资料来决定,也就是说训练的时候不花力气,测试的时候花很大力气)。

 
 


 
 

这里假设中心已经确定是看过的已知点,我们还要想办法最佳化一下beta。

 
 

这里考虑平方错误的regression当作例子,这样output这层的转换就不考虑了。那我们要做的就是使用这些中心点的RBF函数来转换我们的资料,转换过后beta这边就是一个线性组合的问题,只需要通过linear regression就可以得到结果了。因此我们来看BETA的结果,里面包含的Z是一个方阵,方阵里面的每一格算的是两个向量之间的相似度,因此还是一个对称矩阵。如果你对对称方阵采用高斯函数,只要你所有的X都不一样(每笔资料都不一样),矩阵Z就会是可逆的。因此上面的beta的公式可以化简为 beta = z^-1 * y。

 
 


 
 

我们将上一页得到的结果喂到RBF函数里面去,就有上面橘色部分的推导结果,也就是说RBF网络的结果是,送入 xn 会得到 yn,也就是说Ein = 0!

 
 

这样的性质在 Function approximation(函数逼近)里面应用的很好(内差完美 exact interpolation),但是对于ML来说不好,overfitting!

 
 

因此加上regularization,比如对上面的beta计算改造一下使用ridge regression,这样的beta解如上面所示。我们回想一下,Z这个矩阵可以看作是里面包含了一堆高斯函数,就类似于 gaussian kernel matrix K,其用到的kernel ridge regression的表示如上面所示。两者类似,区别在于以前是无限多维度,这里是有限多维度做regression。

 
 


 
 

我们上面就讲到了如果你把所有的已知资料当作是center点的话,可能会有overfitting的情况,因此你需要regularization。

 
 

我们来考虑SVM的时候是没有把所有的资料都是用进去,只用了support vector。因此这里另外一种可能的regularization的方式是让center的数量少于资料的数量。物理意义是要从原来的资料里面找出一些代表来,用这些代表来表示意见。

 
 


 
 

练习

 
 


 
 

因此我们现在的目标是找出好的代表。

 
 

上面原来是每一个人都是一个代表,但是如果当两个点非常接近的时候,这两个人可以共用同一个代表。也就是说可以把资料分群,每一个群都用一个点来代表。因此要解决的问题是分群并且选择出代表,是一个典型的非监督式学习的问题,分群问题我们的期望是如果由两个点是属于同一群的话,这个代表点和原始的两个点都很接近,因此可以得到如上面Ein的公式,公式的意义是对于每一个点来说其到自己的代表点的距离平方和要是最小,Ein表示的就是选民和代表的意见的一致程度。

 
 

目标:在很好的把资料分群后Ein要最小。

 
 


 
 

我们来看一下这个最佳化问题,这是一个困难的组合最佳化问题,既要组合最佳化,又要数值最佳化。问题里面有两群变数,我们看能不能个别的对他们最佳化。

 
 

假设固定下来所有的mu,来看怎么最佳化分群。中心选定了,对于每个点只能选一个加入离他距离最近的群。

 
 


 
 

假设固定了哪些点是一群,看怎么来最佳化中心点位置mu。也就是对每一群重新去计算Ein最小得到新的mu。

 
 


 
 

从上面我们就得到了一个非常知名的演算法 K-Means Algorithm,其具体的算法描述如上面所示。

 
 

一开始的时候需要决定mu,从原始的资料里面随便选择k个;结束条件是 Converge,就是一步内S不再会有任何变化,这个算法一路收敛的,一定会有最佳结果并停止。

 
 


 
 

我们有了k-means的概念用于RBF Network,算法如下:

  1. 一开始我们采用k-means算法来得到中心点
  2. 配合使用RBF做特征转换
  3. 跑线性模型就可以得到beta
  4. 最后回传回去的就是beta和转换结果

 
 

这里使用了非监督式演算法(k-means)来萃取特征,前面提到的auto-encoder也是相思的概念。

 
 

RBF Network现在似乎不那么流行使用了。

 
 


 
 

练习

 
 


 
 

K-means 算法很漂亮,这里给一个demo,这里有四群资料,开始分群。

 
 


 
 

随机得到mu,对每一个资料点分群

 
 


 
 

决定新的中心点位置

 
 


 
 

新分群

 
 


 
 

得到新的mu

 
 


 
 

以此类推,只要你的群的数量选择适当,结果就会很好。

 
 


 
 

一开始群的数量设的不同,结果很不一样。也就是说这个算法对 初始值 和 k 敏感,也就是说最终得到的也是局部最佳解。

 
 


 
 

分完群以后做RBF Network,结果是上面这样,也就是说如果这个算法的第一步k-means结果不错,第二步再做RBF Network结果也就会比较好。

 
 


 
 

我们来看看几个方法的比较,左边是full RBF Network,右边是nearest neighbor,这两个实际上很少被使用,计算量很庞大。

 
 


 
 

练习

 
 


 
 

总结:

Radial Basis Function Network 模型,其hypothesis就基本是一堆RBF,比如高斯函数,用这些RBF作为代表来取代NN里面的神经元;学习的过程中如果决定了中心是哪些之后,剩下的就是做一步linear aggregation;然后我们介绍了k-means演算法来用于决定中心,其算法的核心就是 alternating potimization,对里面的变数交叉做最佳化;最后我们举例图示加深印象。

 
 

下一讲:

我们怎么从更加抽象的资料里面萃取特征出来。

 
 

 
 

 
 

 
 

Machine Learning Techniques Lecture 13: Deep Learning


 
 

内容:

Deep Learning模型,是之前讲的类神经网路的延伸,他是一个困难的问题,要经过很多层层层淬炼;然后讲了autoencoder,在deep learning里面它的作用就是帮我们预训练出好的weight,本质上做的事情是从资料里面找出最好的表现方式,做法是用一个浅浅的NN来找到一个好的表现方式;进一步讲到denoising autoencoder 就是在原来的资料里面埋了一些杂讯进去做学习已达到可以抗杂讯的autoencoder的效果;最后讲到这些非线性的autoencoder如果退回来变成线性的话,其实就是PCA方法,作用都是帮助我们降低资料的维度。

 
 


 
 

回顾:NN模型里面有一层一层的神经元,他们的作用就是帮我们萃取出资料面的模式(特征),通过backprop工具来计算梯度,从而通过GD/SGD法来学习的到NN模型里面的w参数。

 
 

这一讲:Deep Learning

 
 


 
 

类神经网络的核心就是一层一层的神经元和他们之间的连接关系。那么问题是我们要用多少个神经元呢?我们要用多少层呢?我们的NN结构是怎么样的呢?或者你可以主动的去设计;或者你可以把模型的结构当作是参数,通过validation来选择最好的。

 
 

在NN里面决定使用什么样的网络结构是非常核心,也是非常困难的问题。

 
 


 
 

我们这课里面不会把所有的网络结构列出来比较好坏,而是来比较基本的两种。

 
 

Shallow(浅):

相对来说学习效率很高,计算量比较小;结构简单,参数比较少;层数比较少,但是每一层放足够多的神经元,一样可以做到很复杂的事情。

 
 

Deep(深):

训练的时候一定会花更多的力气,计算量大;对结构的决定会很复杂,参数量大;层数足够多,一样可以做到很复杂的事情;deep这几年很流行的一大关键原因就是其可以得到比较有物理意义的特征。

 
 


 
 

什么叫做 Meaningful?这里举例手写识别来说明。比如我们要辨识1/5,那么每一层萃取出越来越复杂的各个部位的特征,也就是每一层代表了不一样的物理意义,最后再做辨识。越多层就可以表示越多种不一样的变化,每一层要做的事情相对就变简单了,层与层之间的物理意义就是从简单到复杂的转换。

 
 

如果今天你最终要区分的是比较复杂的高级特征,你不能一步登天,像这样每一层做的都是区分非常简单的特征,一层一层的处理合成起来也就可以处理复杂的辨识。在计算机视觉,语音等领域很流行。

 
 


 
 

深度学习里面的困难点和对应的关键技术如下。

 
 

  1. 决定整个网络的架构

除了前面提到的validation方法,研究者还会加上其自身对这个问题的了解(Domain Knowledge)。比如 Convolutional Nnet (CNN) 用来处理图像,用的就是像素之间的物理上的位置关系是很大的影响因素,因此在设计网络的时候让附近的像素连到同一个下一层的神经元,隔太远的像素之间就不管了。

 
 

  1. 模型的复杂度非常高

在资料量足够多的时候这不见得是一个很大的问题,但同时加重了计算复杂度。而对于控制模型复杂度问题本身,其基本工具就是regularization,想办法在你的模型里面踩刹车,让你的模型在即使存在杂讯的情况下依旧是稳固的。

比如最近流行的方法 Dropout,模拟的事情就是如果网络里面存在坏掉的神经元,希望在这样的情况下最终结果还是能保持比较好。

还有一种方法叫做 Denoising,如果我的输入坏掉的情况下,我的整个网络还是可以大概给我一个适当的输出。

 
 

  1. 这是一个困难的最佳化问题,非常容易卡在局部最优

既然backdrop是在帮助梯度下降(GD),梯度下降是起始点敏感的,因此现在需要比较谨慎的选择起始点,而不是random。这个会有一连串的方法来讲解怎么选起始点,一般叫做 Pre-training。

 
 

  1. 计算复杂度很高

这边是这次AI大爆发的重要原因就是有30年前难以想象的硬件计算资源GPU。

 
 

讲者个人观点里面最重要的进步来自于 regularization 和 initialization 思维方法的创新。

 
 


 
 

一个简单的深度学习框架的例子:

  1. 决定一开始比较好的权重,可以一层一层的来决定。上图最下面时输入,第一次决定的就是第一层的初始权重,然后暂时固定下来第一层去确定第二层,以此类推。
  2. 然后再通过训练来获得更好的w。

 
 


 
 

练习

 
 


 
 

上面讲了一个基本的深度学习的架构,我们现在来考虑怎么做 pre-training,也就是帮助我们的权重决定初始值。

 
 

权重的物理意义是什么,其代表的是我们要怎么做资料转换,或者说资料怎么去编码,怎么去表现资料。问题是在做完pre-training之后,我们是不知道这个权重未来会怎么被使用的。也就是说比如我们得到了第一层的权重,对于第一层的权重我们是不知道其在第二,第三层等是怎么被使用的。

 
 

好的权重就应该是能保持我要的资料的特征信息就好了。也就是说资料转换过去后原来和新的资料说明的事情没有变化。举例上面的1/5分类,做了上面图示的资料转换,前三个表示的是1,后三个标识的是5,这三个可以轻易的转换回去。

 
 

如果能够轻易的将资料转换回去(重建),那就是一个好的资料转换。因此我们也希望预训练的时候想办法做的特征转换,是一个好的资料转换。

 
 


 
 

怎么做 pre-training 呢,同样是使用一个 NN 来求解:把原始的资料转换到中间的某一些神经元,这些神经元的输出是我的心的表达方式之后,我还能够试着重建回来。

 
 

这样的NN叫做 autoencoder(自动编码器,自动从原始资料编码得到中间层,编完码之后还可以解码,其输出就是解码结果,和原来输出类似),公式表示就是 g(X) ≈ X ,图中蓝色的w就是 encoding weight,红色的叫做 decoding weight。

 
 

那么 Approximating Identity Function 有什么好处? (就是为什么要编码后的还能解码)

 
 


 
 

假设我们可以 Approximating Identity Function ,那么其必然依赖原来资料的 hidden structure,这样的方式对于 supervised/unsupervised 都有用。

 
 

For supervised learning:学习信息表示

如果能通过这个学习方式得到这个潜藏的结构的化,我们就可以通过这个潜藏结构来当作特征转换。也就是说这些潜藏结构告诉我们怎么用有效的方法来表示我们原始的资料。

 
 

For unsupervised learning:学习得到典型资料

如果我要做的是 density estimation,看看哪边是比较稠密的,哪边是稀疏的。 Approximating Identity Function 做了以后对于新进来的资料,我们可以看他是落在稠密区还是稀疏区,稠密区就是改编码器做得比较好的地方。透过编码器做得好不好,就可以挑出来哪些点不合群,也就是说可以判断到底哪些是典型的资料。

 
 

对于这里自动编码器的重点是得到符合要求的中间层,得到资料的表现方式。

 
 


 
 

我们来看看基本的自动编码器如上面黄色框公式所示。

 
 

  1. 是一个浅的NN,可以通过Backprop轻易地来训练得到。
  2. 通常情况下我们考虑的是得到的中间层比原来的资料维度更小,这样就压缩了表现形式。
  3. 这里的资料不用考虑真正的原始网络的输出结果,要扔进去的资料是(Xi, Xi),可以看作是一个unsupervised学习技术。
  4. 一般情况下用来编码的权重和用来解码的权重是一致的,加上这个条件就是 regularization 的过程,限制能力。

 
 

满足这四条的就是一个基本的 autoencoder, 就是 NN 的 pre-training 的步骤。

 
 


 
 

再回头来看 Deep Lerning 的基本算法,第一步的合理做法就是使用 auto-encoder:每次都是拿前一层的输出训练出初始化的w,同时得到输出用于下一层。

 
 

大部分的 autoencoder 都是大同小异,在这基础上做变化的。

 
 


 
 

练习

 
 


 
 

前面用 autoencoder 解决了 Deep-Learning 里面 Pre-training 的问题,这里谈一下 如何来使用 Regularization 的机制来控制模型复杂度。

 
 

上图是一个之前提到的 NN 示意图,里面有很多神经元以及层次关系,我们要小心overfit,因此我在很多时候使用 Regularization。

 
 

  1. 决定结构的时候,加上一些条件,例如前面举过的CNN的例子。
  2. 在决定权重的时候,加上一些条件
  3. 在early stoppping的时候,确定其条件

 
 

下面讲一个很有用的 regularization 方法。

 
 


 
 

先来复习一下 overfitting 的成因,上面是点的资料量和杂讯的量坐标系内overfitting的可能性,越红越容易。杂讯对于overfitting来说是极其重要的原因,因此要去处理它。

 
 


 
 

一般的思路就是把高杂讯的资料丢掉清理一下,看起来我们可以把学习的结果做得更好一些。

 
 

新的思路是如果我们没办法很容易把杂讯找出来并处理的话,我们把杂讯加到资料里面。

 
 

如果我们想要一个好的自动编码器,有输入输出差不多,你丢进去干净的资料,希望他出来干净的结果, G(x)=x;如果今天给带杂讯的资料,你丢进去带杂讯的资料,你还是希望输出干净的结果,G(X’)=X。

 
 

所以我们要的是 denoising autoencoder。做法基本和基本的一致,输入不一样,资料是干净的资料+人工的杂讯,最后得到干净的结果。有了这种自动编码器,理论上经过DL可以得到更好的结果。

 
 

意义在于,学习得到编码器的时候就加入杂讯,使得其有去杂讯的功能,这样再次使用该编码器处理真正的带杂讯的资料的时候其就具有了去杂讯的功能。

 
 

人工加入杂讯这件事情也是一种regularization的方式,因为它告诉了机器到底要把怎么样的资料处理得更好,这个想法可以用于任何机器学习的模型中。

 
 


 
 

练习

 
 


 
 

前面的部分讲的是 nonllinear autoencoder,是相对来说比较复杂的模型,那为什么不是从线性模型开始讲?(not linear first)是因为我们这里考虑的NN,DL本身已经是非线性模型,这样的架构下非线性转换比较有用。

 
 

那么对于线性的autoencoder可以怎么来做?如果是线性模型,就没有了tranh,见上面的蓝色框第一行公式。考虑一些要用到的特点,首先是把X0拿掉,会让输出和输入范围比较一致;编解码权重一致,也就是蓝色的和红色的是一致的;中间维度比原来的维度小。有了这些H(x)就可以用矩阵表示,非常的简洁,如上面的黄色框所示。

 
 

那么接下来要做的就是对W矩阵做最佳化。

 
 


 
 

今天要对h最佳化,就是对w最佳化,Ein公式如上面所示,使用的是平方错误。我们要做的就是找到一个w矩阵让这个Ein最小。

 
 

下面我们来推导得到这个W的公式解。

 
 

我们先来复习一下线性代数知识。

  1. W *W^T 是一个半正定矩阵,可以做 eigen value decomponsition,得到 V(特征向量), garma(特征值)

    特性:V 向量互相垂直,自己和自己乘就是单位矩阵;garma是对角阵,矩阵维度会小于等于原来的d。

  2. 因此上面第一步*X就也有上面表示了

    特性:V^T(Xn) 代表的就是坐标转换,几何上就是旋转和镜面反射;在乘上garma,就是scale的过程;在V,就是旋转或者镜面反射回到原来的空间,看看变成什么样的资料了。

  3. 用上面的示意对于原来的资料也可以表示成这个形式,只是在V空间变换后啥也没做就变换回去了。

 
 

因此我们可以把W的最佳化问题转换成 V和garma 的最佳化问题。

 
 


 
 

先对garma做最佳化。

 
 

灰色部分表示不对最佳化产生影响,先把w表示成V,garma,后面的变化不会影响的是长度,所以可以把红色的V涂掉,对garma最佳化没有影响。所以就有了 上面蓝色框第二条所示公式,唯一的最小化的机会就是 (I – garma) 里面0最多。因为garma是对角矩阵,因此只需要考虑对角线,因此garma矩阵对角线1越多越好,也就是说最多可以塞 d~ 个1, 因为garma矩阵有效的不大于d~ 大小,所以最后你要得到的garma就长成蓝色框右下角所示情况。【这里是几何概念推理】

 
 

剩下的交给V的最佳化求解。

 
 


 
 

对V做最佳化。

 
 

首先把最小化变成最大化,因为最大化问题看起来比较干净。最小化的时候考虑的是留下哪些维度,最大化则是考虑的要拿掉哪些维度,上图中间矩阵部分的表示。

 
 

假设今天d~是1,也就是V也只需要考虑第一行有用。然后对于平方,则可以写进去如上面灰色部分第二行所示。V * V^T = 1 则是有前面提到的线性代数性质决定的。

由上面可以得到最好的V会满足的条件,绿色的部分可以由lamda替代,原因是第二行的式子部分微分得到的三行的式子,第二航的条件V^T * V 微分得到 V 本身,有 lagrange multipier 知道最佳解两者的微分要平行,所以乘上lamda就可以有上面的等式。然后你再看V,就是eigenvector of X^T * X,而且还是最大的eigen vector,这样才是最大解。

 
 

所以当d~等于1的时候,公式解就是最大的eigen vectoe。所以整体的公式解也可以类似的推导出就是最大的d~个eigen vectors。

 
 

所以你今天在这里要做的事情就是得到资料然后做eigen value decomponsition,得到的最好的那些eigen vector方向,就是你应该投影做特征转换的方向。

 
 


 
 

这就有了非常重要的算法 PCA (Principal Component Analysis),只做2,3两步就是这里讲的linear autoencoder。

 
 

  1. 先把你的资料对应他的平均值做一个转换,得到平均值是0的资料。
  2. 再通过上面的资料计算出最大的d~个eigenvectors就是你需要的这些W的结果。
  3. 有了这些W你就可以构建特征转换,资料进来通过W计算之后送出去的就是资料转换的结果。

 
 

物理意义就是投影过去后在那个方向上的统计学上的变化量越大越好,上面步骤第一步就是做了一个平移的动作,第三部就是做一个投影的动作。

 
 

任何资料拿来,如果你要找到线性的最好的表现形式的化呢,就做PCA来降维度。

这也就是linear dimension reduction。

 
 


 
 

练习

 
 


 
 

总结:

Deep Learning模型,是之前讲的类神经网路的延伸,他是一个困难的问题,要经过很多层层层淬炼;然后讲了autoencoder,在deep learning里面它的作用就是帮我们预训练出好的weight,本质上做的事情是从资料里面找出最好的表现方式,做法是用一个浅浅的NN来找到一个好的表现方式;进一步讲到denoising autoencoder 就是在原来的资料里面埋了一些杂讯进去做学习已达到可以抗杂讯的autoencoder的效果;最后讲到这些非线性的autoencoder如果退回来变成线性的话,其实就是PCA方法,作用都是帮助我们降低资料的维度。

 
 

下一讲:

这两讲NN, DL都讲了些萃取特征的方式,下一课再讲一种,怎么从资料里面找代表。

 
 

Machine Learning Techniques Lecture 12: Neural Network


 
 

内容:

Neural Network模型,出发点是把原来的perceptron变成更多层来达到越来越复杂,越来越powerful的效果,这样的链接在生物学上模仿的就是神经元的连结。在NN里面一个网络w固定了的话就是一个hypothesis,每一层做的事情就是根据这些权重来萃取pattern,一层一层萃取出来到最后一层是直接输出。NN学到这些权重的基本方法就是gradient descent(GD),透过backprop的方去很快的算这些梯度到底是多少。最后讲到这样的基本模型还需要小心的是怎么去初始化,用什么regularizer,以及透过early stopping的机制来避免overfit。

 
 


 
 

上一讲:

Gradient Boosted Decision Tree 模型透过 functional gradient 的方式去得到一棵棵不一样的树,然后再给每一棵树以 steepest descent 的方式得到其对应的权重,合起来以后可以做到处理任何的error measure。

 
 

这一讲:

Neural Network

 
 


 
 

我们已经学过了 Perceptron 模型,就是把你的输入乘上一堆权重算出一个分数,然后判断这个分数大于0就是正一,小于0就是负一。

 
 

如果我们今天把一堆 Perceptron 用 linear aggregation 的方式组合起来的话,就如上面的图所示,从输入出发,乘上第一组的权重得到g1,乘上第二组权重得到g2,以此类推得到一堆的 Perceptron,之后各个g乘上各自的权重alpha,组合起来得到最后的G。

 
 

数学表达式如右边所示:

这个过程里面有两组权重,第一组是从输入乘上对应的权重得到一堆的g,权重是w_t;第二组是g_t投票的权重alpha_t。

这个过程里面还有两次取sin的过程,第一次是得到g,第二次是得到G。图示中使用红色的阶梯函数来表示这个动作。

 
 

这样的模型到底可以做到什么样的边界。

 
 


 
 

例如如图所示,我们有两个 perceptron g1 和 g2,把两者通过 linear aggregation 合起来可能可以做到右边图所示的结果。然后我们构造了下面的图示的函数,公式就是下右表示的那样,其G所描述的就是和上面所述的AND是一样的。

 
 

也就是说我们在第一层g上面构造一些些逻辑运算,到第二层的时候就可以得到比较复杂的边界,比如上面的AND就已经不是线性边界了,OR,NOT也可以类似的得到。

 
 


 
 

linear aggregation of perceptron 是非常 powerful 的,非常复杂的。

 
 

比如上面的例子,我们的目标是一个圆圈圈,园内是1,圆外是-1,如果用单一的perceptron就可以切出左图所示,16个的话就如中间所示的图,最终的目标是使用一堆的perceptron来逼近得到平滑的边界。也就是说我们可以任意的切出二维平面内的凸多边形,这时候的Dvc是无限大(以前有过证明),也就是说能力足够。

 
 

但是还是有做不到的事情,比如 XOR(有且只有一个true) 就做不到。我们把g当作是资料空间转化,在我们转化完以后,资料还是线性不可分的,这时候就没有办法做到。

 
 

那我们要怎么做到 XOR ?

 
 


 
 

转换一次得不到好的结果,那就得再来一次转换。

 
 

比如上面XOR的例子我们考虑两层的转换,第一层做AND,第二层做OR,这样转换的得到的就可以线性分割,就可以得到XOR的结果,图示如上面。

 
 

这里我们的perceptron就开始分层了,这就是我们这一课要讲的神经网络的基本长相。单一的 perceptron 比较简单,多个 perceptron 比较复杂,这里我们迈向更加复杂的 multi-layer perceptron。

 
 


 
 

这种层次化的perceptron组织方式一开始就是学习生物学的神经元信息处理的方式得来的,神经元对应到node,他们之间有传递关系就用权重代表,最后都会得到反馈,就是生物工程的抽象化结果。

 
 

只是模仿,不是模拟!

 
 


 
 

练习

 
 


 
 

上面讲的就是一个简单的神经网络的运作过程,我们从输入出发,经过一层一层的运算,最后一层得到输出。从数学上可以看作是对原始的输入做一次再一次的特征转换,最后通过最后一层的权重去算一个分数,然后输出结果。

 
 

我们可以看到在输出层其实就是一个线性的模型,我们学过的 linear classification(线性分类)/ linear regression(线性回归分析) / logistic regression(软性的分类) 这些线性的分类器都可以放入到这个网络里面。下面为了讲解简单,我们采用 linear regression 方法来讲,你可以轻易的延伸到其它的方法。

 
 


 
 

上面讲了输出的部分,这里说中间的部分,中间的每一步每一个节点都是在做转换。在转换的时候我们应该采用什么样的函数呢?

 
 

如果你每个节点用的都是线性函数,那么整个网路就是一个线性函数,那你直接用一个线性函数替代整个网络就可以了。

如果你每个节点用的都是阶梯函数,是离散的,很难最佳化。

 
 

因此最为常用的就是平滑的s型函数,其中最为代表性的就是 tanh(t) 函数。

 
 

图示和公式如右边,大范围的时候和阶梯函数接近,小范围的时候和线性函数接近,整体上就是大概的逼近我们原来采用的sin函数。这个函数是连续的,最佳化比较容易。tanh(s) = 2 theta(2s) -1 :就是两倍的原来logistic regression函数取2s再减去1的结果。也就是原来的logistic regression函数做放缩平移后的结果。

 
 


 
 

然后我们来描述下我们要讲的 Neural Network Hypothesis 长什么样。

 
 

如果我们固定了hypothesis的一些参数以后,我们就能从一开始的输入得到最终的输出。中间则每一层都是根据前一层的输出当作是输入,再乘上相应的权重之后,得到这一层的输出当作是下一层的输入,直到最后一层直接输出。

 
 

我们把第一次处理叫做第一层,第二次处理叫做第二层,以此类推,输入的部分叫做第0层,层数用L表示。输入层是0 – d-1层,输出层就是 1 – d 层。这样以后这个过程就可以用公式表示出来如上面所示。紫色的 S_j^L 表示的是 第L层第j个节点的输入,红色的 X_j^L 表示的是 第L层第j个节点的输出,除了最后一层其他层都需要做tanh转换再输出出去。

 
 

绿色框框的标题


表示的是我们用每一层有多少个节点来描述这个神经网络。

 
 


 
 

这网络的物理意义:每一层做的事情就是转换,权重就是从资料里面学习得来的。也可以看作是把前一层的结果x向量 和 这里的权重向量 的内积是不是比较一致,如果两个向量比较重合,则表示两者比较接近。

 
 

NNET :每一层在做 pattern extraction,每一层都是从资料中找出潜藏的模式,一层一层的把这些模式做转换匹配,看是否相似。

 
 


 
 

练习

 
 


 
 

如果我们已经有一组特定的权重的话,NN做法就是从输入开始就是一层一层的透过w和tanh来得到一层一层的输出变成下一层的输入一路计算下去,直到最后一层不做tanh而是直接输出。

 
 

现在问题是怎么学习得到权重?

 
 

如果你的网络只有一层,学习的方法我们就已讲过了,就是aggregation of perceptrons。我们可以用 Gradient boosting 每次加一个节点(神经元)进来,一个一个加直到你觉得结果可以为止。

 
 

但是现在你有很多层的话,这个可能就行不通了。现在进过很多层以后最终一定是有一个结果输出,我们希望输出的结果和y是接近的。所以我们可以定义类神经网络的输出结果和y的错误平方是e_n,如果我们可以知道这个e_n和网络中的每个w的变化关系(就是 e_n/w 的偏微分),就可以用 GD/SGD (梯度下降)的方法来一步一步做最佳化。

 
 

因此关键点就是我们怎么算出这个 e_n/w 的偏微分?

 
 


 
 

我们来看怎么计算 平方错误 对于 每一个w 的偏微分。我们从错误对于最后一层的偏微分开始处理,也就是L这一层(输出层),神经元的数量是1,前一层的神经元数量则是i,最后用 W_i1^L 表示。

 
 

为什么从最后一层开始,e_n表示的是我们的观察结果和网络输出结果的比较误差的平方,网络的输出就是最后一层的输出,因此公示网络输出的部分可以替换为 S_1^L (就是L层1节点的输出),就是这一层权重的和。如上面黄色框表示的公式那样,整个关系就是从权重到分数到错误表示的过程链。

 
 

有了这个我们再来看权重和错误的偏微分,就可以用微积分里面的连锁律(就是依靠中间人分数S)就可以轻易的求解。【绿色框所示】,会求解了最后一层,我们再来看前几层,做法也是类似的方式求解,只是其中的分数没有那么容易求解出来,所以先使用delta来表示,delta_j^L 表示的是L层第j个节点的错误相对于分数的变化量【红色框所示】。

 
 

有了delta的定义,前面绿色框里面的delta_1^L就是一个特殊的可以求解的结果,表述如上面PPT所示。我们怎么来求解其他的delta呢?

 
 


 
 

我们来看delta怎么计算,那么我们先来分析一下这个分数怎么会影响到最后的错误e_n。在类神经网络里面,这个分数再经过神经元的转换变成神经元的输出,就是s变成x,然后再经过下一层的权重变成很多不同的神经元的分数,一路以此类推,最后最后才得到e_n。【上面黄色框所示】

 
 

所以我们来看蓝色的s和错误e_n的关系,他们俩之间的中间人很多层,每一层还好几个。因此如果在这么复杂的式子上面用连锁率,可以有蓝色框所示的内容(把中间人的影响要全部加起来),求解后用delta表示的结果如上。

 
 

这个结果表示的是,如果你今天后面那一层的delta你知道是多少,那你就可以推导得到前面那一层的delta的解。同时我们还知道最后一层的delta的结果,因此可以一路往回推得到所有的结果。【绿色的部分可以求解】

 
 

同时你还需要知道蓝色部分的解,tanh的微分可以直接求解【蓝色部分可以求解】

 
 

至此你就可以求解出所有的w,就可以总结出计算w的演算法。

 
 


 
 

算法叫做 Backpropagation (Backprop) Algorithm:

 
 

一开始随便设定一些权重w_ij,每一次

  1. 【Stochastic】随机选一个点算他的梯度是多少,这个梯度可以拆解成两项,一项是x,一项是delta,所以每一个权重他的更新量就和它前一层时候的x和这一层的delta的变化量有关。要更新我们就需要算出红色的值和蓝色的值。
  2. 求红色的值,把资料喂进去,一层一层的求解。
  3. 求解delta,倒着算回来,上面讲的那样。
  4. 【Gradient descent】更新w_ij

更新了足够轮的时候,每一个w_ij就应该在一个比较好的范围内了,让Ein比较小了,就把结果回传形成神经网络模型。

 
 

你每次选择一个点,你都需要从前向后算得到x,从后往前算结果得到delta,才能球解一个,感觉时间会很久。实际操作的时候,第一步到第三步可以并行的做,然后我们把这些并行结果去平均梯度结果来更新第四步,可以加速运算,这个做法叫做 mini-batch。

 
 

这就是基本的类神经网络算法。

 
 


 
 

练习

 
 


 
 

上面介绍了NN里面最佳化的基本方法,其关键就是通过GD的方式去最佳化Ein,Ein包含的是原始的输入一层一层处理最后得到的输出和y在某个错误衡量上的比较结果。这里讲的是NN常用的一些优化方法。

 
 

上面的例子是平方错误衡量,你可以替换使用其他错误衡量。我们这边的重点不是错误衡量,而是在讲经过了那么多层tanh的转换,使用GD来得到的可能是局部最低谷(就是好多山峰的中间的山坳,而不是真的全局最低谷)。

 
 

也就是说NN不是简单的像单层的二次曲线求山谷谷底(non-convex)就是全局最优,而是有多个山峰山谷,你从当前点出发得到的是局部最优。换个角度就是说你从不同的起点出发,你可能得到不一样的局部最优解。

 
 

那有什么技巧可以让我们避免不好的山谷呢?

 
 

我们来看tanh函数,前面有图示意其函数,在两头权重很大的时候,其x的变化带来的y的变化量非常小,如果在这里每次走一小步,你走老半天也可能是原地踏步。所以一开始你需要一个小一点的随机权重,这样你不会卡住走不动,随机则意味着你可以走到不同的山谷。

 
 

NN不是一个容易的最佳化问题,里面包含很多技巧去尝试。

 
 


 
 

我们来看看这个模型的复杂度,大概的结果是 Dvc = V(神经元的数量) * D(权重,就是图中连线的数量),也就是说图的节点和连线越多,这个NN的能力(Dvc表示)就越强,但是就越容易overfit。

 
 


 
 

避免overfit的一个经典方法就是 regularizer,最佳化的过程里面加入regularizer让权重不要太大是对整体复杂度的一个限制,具体可以见以前讲regularizer的时候的推导。

 
 

这边如果我们采用以前讲过的 L2 regularizer,也就是平方和,越小越好。但是有一些缺点:权重的变化是成比例的,原来比较大的权重缩小后相对还是比较大,原来比较小的权重缩小后还是比较小。也就是说权重缩小也不会是0,也就没有办法做到通过让w是稀疏的来降维度。

 
 

我们的目标是通过让W稀疏来降低Dvc的复杂度,那么可以考虑的是 L1 regularizer。L1 是把w的绝对值得和当作是ergularizer。但是因为绝对值函数是非连续的不可微分,就很难计算(原来的函数是微分导向的性质会被破坏)。

 
 

因此可以考虑的是 weight-elimination (Scaled L2) regularizer,也就是说原来weight很大的话就把它缩小,原来很小的话也缩成一个中等分量,这样的话原来很小的就会消失不见,让w变成sparse的。常用的 weight-elimination ergularizer 如上面所示。

 
 


 
 

NN里面还有一招常用的 regularizer 机制叫做 Early Stopping。

 
 

我们看GD/SGD做的事情就是考虑其周围一个范围内的w走一小步走到另外一个地方,然后在考虑新地点的一个范围内的w再走一小步。所以虽然w很大,但是每一次你都是在一个小范围内做选择;另外你走的步越多,你看过的w就越多。所以说如果考虑的是有效的Dvc,你走的路越多,有效的Dvc就越大。那么反过来考虑你不要走太多的的路,Dvc就会比较小。

 
 

我们来看Dvc的图,山谷形状,好的Dvc会在中间。套到这里,就可以用最佳化的步数来控制Dvc的大小,就是走了一些步数感觉结果可以了就停下来。NN里面步数和Ein/Etest的关系就是上面第二张图所示,我们要的是中间步数的结果是最好的。

 
 

可以通过validation来确定什么时候要停下来比较好。

 
 


 
 

练习

 
 


 
 

总结:

Neural Network模型,出发点是把原来的perceptron变成更多层来达到越来越复杂,越来越powerful的效果,这样的链接在生物学上模仿的就是神经元的连结。在NN里面一个网络w固定了的话就是一个hypothesis,每一层做的事情就是根据这些权重来萃取pattern,一层一层萃取出来到最后一层是直接输出。NN学到这些权重的基本方法就是gradient descent(GD),透过backprop的方去很快的算这些梯度到底是多少。最后讲到这样的基本模型还需要小心的是怎么去初始化,用什么regularizer,以及透过early stopping的机制来避免overfit。

 
 

下一讲:

这里讲的是基本的类神经网路,下一讲继续做延伸变成好多好多层。

Machine Learning Techniques Lecture 11: Gradient Boosted Decision Tree


 
 

内容:

Gradient Boosted Decision Tree,一开始现讲怎么把adaboost和decision tree搭配起来,需要引进sampling 和pruning才能搭配得很好;然后讲了怎么从优化的角度来看adaboost,找到好的 hypothesis 就是找一个好的方向,找到alpha其实就是走一个适当的步长,对应到adaboost里面的exponential error这样的函数就是优化问题;我们可以把优化观点下的adaboost延伸到其他不同种的错误衡量,映入了gradientboost,他做的事情就是residual fitting,根据余数还剩多少来更新regression的问题,看看能不能做得更好;最后总结了一下aggregation的方法。

 
 


 
 

上一讲:

Random forest模型,就是一堆的decision tree,利用bagging的方式做出一些不一样的decision tree,再把他们合起来。除了基本的bagging和decision tree之外,再加上一些额外的random机制,做到了自动的validation和特征选择。

 
 

这里:

Gradient boosted decision tree

 
 


 
 

上一次讲的random forest,外层是个bagging,里面是decision tree。这里把decision tree结合到adaboost一起的话,就是 Adaboost-Dtree:

  1. 每一轮给我们的资料一群新的weight;
  2. 通过这些weight来使用decision tree学一个g;
  3. 使用linear的方式把g合起来成为G

 
 

要把decision tree搭配adaboost的话,需要把decision tree改造成可以接受权重的形式。

 
 


 
 

带权重的decision tree算法应该要根据权重来最佳化Ein。

 
 

做法:

  1. 打开演算法看看到底哪些地方涉及到权重带来的影响,然后在这些地方代入权重来计算结果。
  2. 但是像decision tree这样的演算法包含很多作者的优化和特殊处理,对于做法一很难做到,因此考虑的做法是原来的演算法不动,而是考虑外面送进演算法的资料做些手脚,把权重的影响用资料来代替。

 
 

比如bagging里面权重为n,则复制资料n份,在此基础上再抽样。因此这里也可以通过已考虑权重的资料来做sampling,这样就可以得到一组可以表达权重信息的资料。

 
 

所以Adaboost-DTree:Adaboost + sampling(通过权重来抽样) + Dtree;这就是其典型做法。

 
 


 
 

当我们通过adaboost得到g以后是怎么决定g票数的:先算一下g的错误率,然后根据上面公式得到g的票数,这是adaboost做的事情。

 
 

问题是:对于完全长成的树,把所有的资料用于训练,Ein为0,加权中后Ein应该也是0,alpha_t则会是无限大,也就是说得到一个跟强很强的权重是无限大,也就是说只要这棵树决定就好了,其他的都是无用的。

问题在于你把所有的资料都用于训练,且让树完全长成。

 
 

改进:砍树不让完全长成;不用所有的资料来训练;… 简单地说就是需要弱一点的树。

做法:我们用的是sampling后的资料,也就是说是部分的资料而不是全部的资料;不让完全长成的方法则是和前面讲的一样,那些方法都可以拿来用。

 
 


 
 

什么样的是最弱的树?

一层高的树,C&RT里面做的事情就是切一刀,想办法让两边加权的纯度越低越好,这样的再结合decision tree就是adaboost-stump。

 
 

也就是说 Adaboost -stump 是 adaboost-Dtree的一个特例。当树的层数那么小的时候,一般都不会出现Ein=0,也就不用担心上面出现权重为无穷大的情况了,这时候就不见得要做sampleing。

 
 


 
 

练习

 
 


 
 

前面复习了一下Adaboost,以及讨论了一下怎么搭配decision tree,现在进一步来看看adaboost算法的奥妙,然后再据此延伸成今天要讲的griendent boosted decision tree模型。

 
 

Adaboost 里面的权重是根据前一轮的权重乘(正确:y_n = g_t(X_n))或者除(错误:y_n != g_t(X_n))方块t,我们简化一下上面的公式变成一行,用符号来控制正负;再化简一下就变成了一个递归推进的式子,也就是U^t+1与U^t相关。根据递推来算Un就是一个连乘的形式,再化为连加的形式。

 
 

橘色的部分:voting score,是小g做投票的结果,是G的分数。

 
 


 
 

Linear model可以看作是两步,第一步是使用hypothesis做特征转换,再用线性模型组合起来,这个线性模型会告诉我们每个g是几票(灰色的条件是说投票权重不能为负的条件),

 
 

我们把g_t(Xn)看作是phine,alpha看作是每个转换过的特征的权重,voting score就是w*phine。我们在SVM里面讲过,w*phine/abs(w) 就是到分割线的距离(SVM里面的常数项b不影响理解)。所以voting score可以看作是某个空间里面还没有正规化的点到分隔线的距离。

 
 

所以 y_n(voting score) 就是 unnormalized margin,所以同样我们希望margin 越大越好,所以我们希望 exp(-y_n(voting score)) 越小越好,所以希望每一个点的权重越小越好。Adaboost 一轮一轮的进行下去,就会使得这个值越来越小,这是Adaboost的一个重要性质。也就是说Adaboost可以达到large margin的效果。

 
 


 
 

Adaboost 可以让公示里面紫色的部分越来越小,也就可以看作是其可以让上面等式的右半部分越来越小,也就是说在最后一轮括号内的部分红色和蓝色相乘是很大的,也就是达到了large margin的效果。

 
 

我们特别的来看看蓝色红色相乘的结果:

  1. 01错误的时候,如图黑色线所示,同号错误为0,异号错误为1;
  2. adaboost错误(紫色部分)的时候,如紫色线所示,是01错误的上限函数。因为是上限函数,类似以前讲过的SVM,logistic regression等等,可以大概的用它来把0/1问题做的比较好。

 
 


 
 

证明:

基本工具是 gradient descent(梯度下降法):如果你要最小化一个函数的话,你做的事情是从你当前的点出发,选择一个方向使得最靠近目标。数学上就是做泰勒展开,梯度描述的就是方向,求一个最好的方向,最终的结果就是负梯度的方向走上n大小的一步。

 
 

这里我们把g_t这个函数当作是方向(原来是向量,向量的ab相互对应,这里是函数,函数的xy相互对应),同样目标是向h(x_n)方向走n远,加入公式后就如上面所示,然后目标是变成最上面的相似公式。首先整理一下公式就出现了U_n^t,式子就简洁多了,再做泰勒展开,原来的公式就可以拆分为两部分,前半部分就是现在的Ein,那么后面一项就应该越小越好,这样就最佳化了Err。

 
 

所以目标就是找到一个好的h让后面这一项越小越好。

 
 


 
 

对于后面那一项,如果做的是binary classification,y,h都是正负1,那么就只有两种情况,yh同号和异号,结果如上面所示。然后再平移出一个项,然后就可以化简为如上所示的结果,所以结论就是要Ein^u越小越好。

 
 

Adaboost 里面的 A 做的事情就是找到一个好的g_t=h,就是好的方向,这个方向代表函数。

 
 


 
 

Adaboost 通过上面所示的式子的最佳化找出g_t,但是每次走一小步代价比较大,能不能走大步一点,或者说干脆找一个最好的n(也就是g固定的时候,n越大步越好)。

 
 

也就是说这里不再和以前gradient descent一样每次步长是一样的,每次一小步,而是一次就走一大步到离目标最近,这是greedily(贪心的)faster(快速的)的n。

这个叫做: steepest descent

 
 

运用 steepest descent 则可以把原来的式子改写成灰色框最后一行所示的结果。绿色表示所有的 正确的U_n^t/所有U_N^t,红色表示的是所有的 错误的U_N^t/所有的U_N^t(epthon_t)。

至此公式只有n是变数,其他都是已知的,单变数做最佳化的问题,微分=0就可以得到结果。

 
 

结果 steepest n = alpha_t。

所以Adaboost:把函数当作是向量一样在gradient上面走了最大的一步。

 
 


 
 

练习

 
 


 
 

上面部分对Adaboost的解释是:Adaboost就是在Err_ada上面每一步都在做最佳化,每一步的时候找出一个h,把它当作g_t,然后决定在这个g_t上面走多长的距离,最终变成这个g_t的票数就是alpha_t。

所以对于公式来说就包含两个部分,一个部分是对h做最佳化,一个部分是对n做最佳化。

 
 

根据这个概念做延伸,拿来对不同的error function做最佳化,扩展为 GradientBoost,做法思想和上面一致,只是把里面计算err的部分换成任何你想要的平滑的error function,这就是adaboost的延伸。

在这架构下你就可以使用不一样的hypothesis,而不再必须是binary classification,最常见的是使用real-output hypothesis,就是实数输出的hypotheris。同样在这里有两个步骤,第一步决定一个最佳化的h,再决定一个最佳化的n。

 
 


 
 

例如说通过GradientBoost方式来做regression:

 
 

regression里面用的err就是平方错误;把紫色部分命名为S_n表示的是当前已经算出来的err,然后再向某个方向的移动(红色蓝色乘积);

灰色框第一步:将红色蓝色部分提出到sum外面的时候做的是 err对s 的偏微分,在s_n的位置取值,这是对于每一个点。

灰色框第二步:微分后的结果。

因为前面一项可以看作是常数,我们要做的是最小化,因此就是后面那一项越小越好。后面这一项只要保证两个乘数的符号不同,结果就是负的就是在减小。我们关注的是正负,对于大小要做限制,不然无限大就是最佳解了。

 
 



上面讲到我们要对h的大小做限制,因为其大小对于我们来说不重要,大小的解决是靠后面计算中的n来解决的。

 
 

如果我们直接限制n=1这样来做限制的话,我们求解的就是有条件的最佳化问题,比较难求解;这边类似以前解决有条件最佳化问题的方法,把条件当作是最佳化问题的一个惩罚项直接加入到式子里面去。就是上面蓝色框内的红色括号部分,一个平方项。然后再可以凑出平方来化简,用来凑数的常数项这里都可以随便加,不影响结果。

 
 

常数对于最佳化都没有影响,只有最后的平方项才会影响最佳化,上面式子里面剩下的部分的意思是:我想要找一个最好的h,那么他就是要和y减掉s的平方误差上尽可能的接近,那就是做regression。因此上面问题的最佳解就是拿 (x, y-s) 来做regression,y-s就是余数。

 
 


 
 

上一步说明的是怎么找出一个好的g_t,就是求解一个(x_n, y_n – s_n)的regression问题,下一步就是怎么得到权重n,意思就是在g_t这个方向上面我们要走做大一步。

 
 

这个问题公式化就是蓝色所示,包括分数s部分,y部分,n*g_t部分,其中g_t是固定的。同样我们可以把这个式子化简为一个平方式:里面包含g_t*n,y-s两项。也就是说g_t和余数y-s越靠近越好,通过调节n使得两个越靠近越好的最佳化问题。这就是一个单变数的linear regression的问题。

 
 

这样就得到了每个g的权重n。

 
 


 
 

把上面的概念都合在一起,就得到了 Gradient Boosted Decision Tree(GBDT) 算法:
 

算法经过T轮之后回传一堆g和alpha,然后直接加权就会得到一个比较好的G。

每一轮:首先想办法求解一个regression问题,使用某一个A(base learn method,这里用的就是decision tree)求解从x_n到余数y_n-s_n得到一个g_t;然后通过一个单变数的linear regression就可以得到对应的alpha_t;然后跟新分数s_n。

 
 

这算法可以看作是 Adaboost Decision Tree 的 regression 版本,这算法在资讯检索领域应用广泛。

 
 


 
 

练习

 
 


 
 

至此介绍了这课里面要提到的所有aggregation model,我们来复习一下。

 
 

首先讲的是blending model,就是如果今天我们手上已经有了一些g,我们希望把他们合起来。

 
 

我们讲了三个基本的blending方法:第一个是uniform blending,每一个g地位一样,直接就是民主投票;第二个是non-uniform blending,就是加权投票,这里通过拿g做特征转换,然后再做一个阶段的linear model就可以得到这个权重应该是多少;第三种是conditional blending,就是在不同的时候使用不同的g,这个其实也可以看作是第二种方式的扩展,只是使用的不是linear model,而是non-linear model来得到权重。

特点:越uniform,越是追求的是稳定性,通过不同的g来修正彼此之间的错误;越non-uniform(conditional),越追求的是能力的强大,但同时带来的就是需要非常的小心避免overfitting。

 
 


 
 

然后讲的是learning model,就是手上还没有g,我们需要边学习g边决定怎么把他们混合起来。

 
 

同样讲了三种learning的面向:第一个是uniform的时候:代表性的是bagging方法,通过bootstripping的方法去学到不一样的g,最后直接就是平均就得到G;第二个是non-uniform的时候,就是linear的时候:Adaboost通过改变资料的权重的方式来得到不一样的g,边得到不一样的g边依据他们的表现来决定他们的最终的权重,从最佳化的角度就是要走最大的一步来决定这个g的票数;第三种是conditional,在不同的时候使用不同的g,有一个代表性的方法是decision tree,透过branching,在树里面通过分叉条件去使用不同的g。

 
 

在这一讲里面还把Adaboost延伸到GradientBoost,同样是需要找到一些不一样的g,不同的是不像adaboost一样重新改变权重,而是在regression的设定里面,透过看看剩下多少余数,在余数上面做learning,做完以后同样看能走多大步的方式来得到权重。

 
 

这四个就是aggregation learning model,都非常实用。

 
 


 
 

至此我们有了这些 aggregation model,我们还能进一步融合他们做一些不一样的事。

 
 

  1. Bagging + Decision Tree = Random Forest:使用的是完全长成的decision tree,还透过投影到不同的方向上让decision tree更为强大。

 
 

  1. Adaboost + Decision Tree = Adaboost D-Tree:使用的则是比较弱的decision tree,因为adaboost就是要把很多弱弱的东西合起来把它变强,一开始用太强的没意义。

 
 

  1. Gradientboost _ Decision Tree = Gradient D-Tree:同样使用的也是比较弱的decisiontree。

 
 


 
 

Aggregation 这个把g合起来变成G的概念为什么会做的好?

 
 

  1. 解决的是underfitting:一对弱弱的合起来会变强,原因是aggregation代表的就是feature transform。
  2. 解决的是overfitting:把很多个合起来以后会找到一个比较中庸的选择,原因是aggregation存在regularization的性质。

 
 

适合的使用会得到比较好的结果。

 
 


 
 

练习

 
 


 
 

总结:

Gradient Boosted Decision Tree,一开始现讲怎么把adaboost和decision tree搭配起来,需要引进sampling 和pruning才能搭配得很好;然后讲了怎么从优化的角度来看adaboost,找到好的 hypothesis 就是找一个好的方向,找到alpha其实就是走一个适当的步长,对应到adaboost里面的exponential error这样的函数就是优化问题;我们可以把优化观点下的adaboost延伸到其他不同种的错误衡量,映入了gradientboost,他做的事情就是residual fitting,根据余数还剩多少来更新regression的问题,看看能不能做得更好;最后总结了一下aggregation的方法。

 
 

下一讲:

至此讲完了aggregation,下面开始探讨说如何让机器自动的学到更多更复杂更不一样的特征,不见得是hypothesis的特征转换,而是多种多样。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Techniques Lecture 10: Random Forest


 
 

内容:

Random forest,演算法就是做bagging,然后在bagging里面做decision tree,为了让decision tree更加随机一点,通常会做randomly projected subspaces,就是随机的选择features下刀。在这样的模型里面,因为采用了bagging,可以得到Out-of-bag(OOB)结果,用来代替validation达到self-validation的效果。有了这个机制,配合premutation test(采用随机排序的特征)来测试每一个特征到底是不是你需要的,其重要性。最后图示该算法的表现。

 
 


 
 

上一讲:

决策树模型,演算法的核心是想办法通过递归的方式切割资料,切割资料的标准就是希望你的资料越纯越好。切开后就得到conditional aggregation的效果,就是根据不同的情况使用不同的小g,就是树叶。

 
 

这一讲:

随机森林

 
 


 
 

先来复习一下两个机器学习模型

 
 

Bagging:通过bootstraooing的方式得到不一样的资料,然后把这些不一样的资料送到base算法里面得到不同的小g,最后让这些不同的小g来投票得到结果。

特点是:小g的变化越大,bagging降低variance的效果越明显。

 
 

Decision Tree:拿到资料后想办法建立一棵树,通过递归的方式利用条件分割资料得到g,分割的依据是资料的纯度。

依据是:variance很大,资料稍微变一点点得到的树可能就差很多。

 
 

两者结合是不是能取长补短呢?

 
 


 
 

Random forest:random(Bagging过程里面的随机性) + forest(Baggin下面的hypothesis是由fully-grown C&RT decision tree得到)

 
 

基本算法:

每一轮的时候想办法用bootstripting的方式得到不同的资料,然后送到完全长成的Decision Tree里面得到g,然后把结果公平的投票得到大G。

 
 

优点:

Bagging的过程用以并行计算,各个独立资料运算无依赖;decision tree的过程也是很有效率;因此整个过程就是很有效率的。

C&RT这个算法有很多好处,可以处理missing feature,multi-class等(见上一课),random算法继承这些好处。

C&RT的问题在于对于资料太敏感,容易overfit,这里通过bagging来缓和这个问题。

 
 


 
 

如何让random forest做的更好。(优化:到处充满随机)

 
 

  1. Bagging + random-subspace C&RT

基本的方法通过bootstript在原来数据里面抽样来得到资料算出小g;这里我们除了在资料端做抽取,还能在feature端做抽取,这个可以看作是特征转换,将原来的高纬度特征投影到低维度空间里面,例如原来有100个特征,每轮随机选择10个特征来处理。这样可以得到更不一样的树。

 
 


 
 

  1. Bagging + random-combination C&RT tree

就是在特征投影的基础上,再选择feature数量也是随机的,而不是使用全部。例如有100个特征,选三个合起来算一个加权的分数再在上面做切割,下一次选五个再在上面做切割,也就是投影的时候不是每次把100个都投影进去。

 
 


 
 

练习

 
 


 
 

Random forest 里面的核心就是 bagging bootstript,这里再来看看 bootstript这个机制告诉了些什么东西给我们。这个机制就是通过在原始资料库里面有放回的随机抽取资料,用来学得小g。把这个随机的结果列成表就如上面所示,在算某个g的时候资料选到就标蓝色,没有就是红色,某个资料从来没被选到过就是 out-of-bag(OOB) data,我们来看看这些资料的奥秘。

 
 


 
 

到底有多少out-of-bag的资料?


假设一共有N笔资料,没被选到的资料数量是N’,如果你抽了N轮的话,一笔资料从没被选到的概率是(1 – 1/N)^N,如果N很大的话可以约等于1/e,也就是差不多1/3左右。

 
 


 
 

Validation的时候:我们把所有的资料切成两个部分,训练资料和验证资料,用验证资料来衡量g的表现,然后选择最好的。验证资料可以这么做的理由是其没有参与训练。

 
 

OOB 资料的特性:对照validation,红色部分没有参与训练,那么就可以用来做validation类似的事情。所以我们可以采用OOB来做g的好坏的验证,但是RT方法的目的是得到G而不是好的小g,这个做法不需要。我们需要的是对G的验证。

 
 

做法:

对于(Xn, Yn),可以当作是g2-gT(G_n^-)这些的validation的资料,但是不能当作g1的validation的资料。每一行都有一个G_n^-。

E_oob(G) = avg(Err(yn, G_N^-(xn))):每一笔资料X_n做出G_n^-来,然后根据yn看看表现就是err,最后把所有的做平均。估算的是G到的表现的是好还是不好。

 
 

通过 E_oob,对于bagging/Random forest来说训练完就可以马上知道G到底好不好。

 
 


 
 

Validation:训练的资料D_train通过算法A得到结果,再比较验证看结果是否正确来得到E_m。

 
 

RF:通过得到资料D的random forest,然后就可以自验证得到 E_oob 来衡量G到底好不好。而且不存在re-training。E_oob衡量G的表现通常相当准确。

 
 


 
 

练习

 
 


 
 

假设你的资料的特征维度是很高的,比如10000个维度,这时候你就比较想减低资料的维度。

  1. 把冗余的特征移掉。(比如年龄和生日两个特征)
  2. 把和你的目标无关的特征移掉。(比如病人的保险状况和是否癌症的判断无关)

 
 

好处:可以看作是对杂讯的排除,不容易overfit,结果会比较好;后续的训练测试效率更高。

缺点:降维度可能在计算上就需要花费很多力气;降维没做好的话就很容易overfit。

 
 

决策树的算法过程本身就包含特征选择的过程,每一步你用什么特征来切分就是。

 
 


 
 

Feature selection 是一个组合爆炸的问题,解决这个问题的一个方法是:把feature根据重要性排序,然后取前n重要的就好了,这种方式在线性模型里面最好用,因为权重决定了影响力。对于非线性模型要理清特征的权重就比较困难,random forest就是非线性模型,但是因为其具有的一些特征使得做特征选择相对比较容易。

 
 


 
 

基本想法:random test

若你现在在做学习,那么对于某一个你认为很重要的特征,加入一些随机杂讯后,你学习就比较困难,但因为重要所以你一定要学会他,花比较长时间。也就是很说你只要比对学习特征的时间和学习加入杂讯后特征的时间的差值,越大说明越重要。

 
 

塞什么杂讯进去?

  1. 平均、随机、高斯分布,这些会影响到目标分布,这一点RF是敏感的,不好
  2. Bootstrip(permutation)方式,目标分布是没有变化的,比较好

 
 

Permutation test:比较我原来的表现和permutation方式做过的资料后的表现的差值。

整体做法就是每一次用permutation方式对第i个维度污染一下,计算一下差值。

 
 


 
 

最后我们怎么来衡量这些performance(i):

 
 

Performance(D):拿这些重新排列的资料来重新做一次训练,得到G然后再做validation来验证,就是使用OOB得到结果 E_oob(G)。

Performance(D^p):对应上面的结果应该是 E_oob(G^p),约等于 E_oob^p(G),这样就可以保持G不变不用再re-train一遍,而是在验证的时候动手脚,验证的时候采用p变化后的资料来算错误率。

 
 

所以:

RF 的特征选择是通过 permutation(随机排序) + OOB(错误衡量) 来得到特征的重要性,然后就选出了重要特征。

这种方式做特征选择非常好用,实际上遇到非线性特征选择的时候常用。

 
 


 
 

练习

 
 


 
 

最后是一个例子

 
 

一棵树

  1. Random combination:把特征随机的集合起来再切分,看上去就是可一切斜的刀。
  2. 粗的标起来的就是bootstript选到的,其他的没选到。

 
 


 
 

T = 100 就是100棵树,最右边的边界已经很复杂了。

 
 


 
 

200棵树,最右边更平滑

 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 

对比1000棵树和1棵树

 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 

投票机制会消除一定的杂讯,让边界平滑。

 
 


 
 

RF的缺点:随机相关,对于变化敏感,因此需要大量的树来尽量减少random对结果的影响。

 
 

树的棵树越多越好,理论上无限多棵最好,实际应用的时候看你的G是否稳定,如果树的数量增加很多G稳定的时候就差不多了。

 
 


 
 

练习

 
 


 
 

总结:

Random forest,演算法就是做bagging,然后在bagging里面做decision tree,为了让decision tree更加随机一点,通常会做randomly projected subspaces,就是随机的选择features下刀。在这样的模型里面,因为采用了bagging,可以得到Out-of-bag(OOB)结果,用来代替validation达到self-validation的效果。有了这个机制,配合premutation test(采用随机排序的特征)来测试每一个特征到底是不是你需要的,其重要性。最后图示该算法的表现。

 
 

下一讲:

这里讲完了random forest,是bagging和decision tree的结合,下面讲boosted decision tree,就是adaboost和decision tree的结合,以及延伸到不只是classification的情况下的使用。