AIAnimation 工程安装

AIAnimation 工程安装

Glenn – networked physics

https://gafferongames.com/

 
 

Glenn Fiedler is the founder of Network Next where he’s hard at work as CEO/CTO. Network Next is creating a new internet for games and e-sports.

 
 

第一篇:

Networked Physics in Virtual Reality

https://gafferongames.com/post/networked_physics_in_virtual_reality/

 
 

Introduction

 
 

About a year ago, Oculus approached me and offered to sponsor my research. They asked me, effectively: “Hey Glenn, there’s a lot of interest in networked physics in VR. You did a cool talk at GDC. Do you think could come up with a networked physics sample in VR that we could share with devs? Maybe you could use the touch controllers?”

【一年前,Oculus来找我做网络物理VR相关的研究】

 
 

I replied “F*** yes!” cough “Sure. This could be a lot of fun!”. But to keep it real, I insisted on two conditions. One: the source code I developed would be published under a permissive open source licence (for example, BSD) so it would create the most good. Two: when I was finished, I would be able to write an article describing the steps I took to develop the sample.

【我很开心的答应了,条件是成果必须开源而且可以对外宣讲】

 
 

Oculus agreed. Welcome to that article! Also, the source for the networked physics sample is here, wherein the code that I wrote is released under a BSD licence. I hope the next generation of programmers can learn from my research into networked physics and create some really cool things. Good luck!

【因此就有了这篇博文以及源代码,我希望大家使用这里的相关技术可以做出酷酷的游戏】

 
 

What are we building?

 
 

When I first started discussions with Oculus, we imagined creating something like a table where four players could sit around and interact with physically simulated cubes on the table. For example, throwing, catching and stacking cubes, maybe knocking each other’s stacks over with a swipe of their hand.【Oculus那边希望的场景是四个人围在桌子边,桌上有一堆的方块可以做物理交互。】

 
 

But after a few days spent learning Unity and C#, I found myself actually inside the Rift. In VR, scale is so important. When the cubes were small, everything felt much less interesting, but when the cubes were scaled up to around a meter cubed, everything had this really cool sense of scale. You could make these huge stacks of cubes, up to 20 or 30 meters high. This felt really cool!【但是我在接触VR一段时间后发现 Scale 在VR里面非常重要。如果桌上一堆小的方块你会觉得不那么有趣,但是如果放大到一米一个左右,你会发现整个世界非常的酷。】

 
 

It’s impossible to communicate visually what this feels like outside of VR, but it looks something like this…

 
 

 
 

… where you can select, grab and throw cubes using the touch controller, and any cubes you release from your hand interact with the other cubes in the simulation. You can throw a cube at a stack of cubes and knock them over. You can pick up a cube in each hand and juggle them. You can build a stack of cubes and see how high you can make it go.【这种感觉很难表达,看起来就像这个图所示的这些方块你可以物理的交互他们。】

 
 

Even though this was a lot of fun, it’s not all rainbows and unicorns. Working with Oculus as a client, I had to define tasks and deliverables before I could actually start the work.【在Oculus工作,我需要在开工前确定任务目标】

 
 

I suggested the following criteria we would use to define success:

  1. Players should be able to pick up, throw and catch cubes without latency.
  2. Players should be able to stack cubes, and these stacks should be stable (come to rest) and be without visible jitter.
  3. When cubes thrown by any player interact with the simulation, wherever possible, these interactions should be without latency.

【目标包括这三个点:首先是玩家可以无延迟感知的拾取,扔抓方块们;然后是玩家可以堆叠立方体,并且会保持稳定(静止);做到正式的延迟最小化。】
 

At the same time I created a set of tasks to work in order of greatest risk to least, since this was R&D, there was no guarantee we would actually succeed at what we were trying to do.【与此同时我创造了一系列工作任务,将工作风险最小化。因为这是研发,我们不能保证我们实际上能够成功实现我们的目标。】

 
 

 
 

Network Models

 
 

First up, we had to pick a network model. A network model is basically a strategy, exactly how we are going to hide latency and keep the simulation in sync.【首先我们需要选择网络模型,网络模型就是一套我们怎么隐藏延迟保持同步的机制。】

 
 

There are three main network models to choose from:

  1. Deterministic lockstep
  2. Client/server with client-side prediction
  3. Distributed simulation with authority scheme

【一共三种模型:确定性锁步(帧同步),客户端预测和客户端/服务器模式,采用授权方案的分布式模拟】

 
 

I was instantly confident of the correct network model: a distributed simulation model where players take over authority of cubes they interact with. But let me share with you my reasoning behind this.【我很有信心的选择了我认为正确的网络模型:分布式模拟,每个玩家是其交互方块的authority,我来慢慢解释为什么选这个。】

 
 

First, I could trivially rule out a deterministic lockstep network model, since the physics engine inside Unity (PhysX) is not deterministic. Furthermore, even if PhysX was deterministic I could still rule it out because of the requirement that player interactions with the simulation be without latency.【首先我很确性的排除帧同步的方案,因为unity的物理引擎结果的不确定性。此外,即使PhysX是确定性的,我仍然可以排除它,因为这里我们的要求是玩家模拟交互没有延迟。】

 
 

The reason for this is that to hide latency with deterministic lockstep I needed to maintain two copies of the simulation and predict the authoritative simulation ahead with local inputs prior to render (GGPO style). At 90HZ simulation rate and with up to 250ms of latency to hide, this meant 25 physics simulation steps for each visual render frame. 25X cost is simply not realistic for a CPU intensive physics simulation.【理由是帧同步隐藏延时,我需要保留两个仿真副本,并在渲染之前使用本地输入预测权威仿真。在90HZ的模拟速率下隐藏时间达到250ms,这意味着每个视觉渲染帧需要25个物理模拟步骤。 对于CPU密集型物理模拟来说,25X成本根本不现实。】【这边我的理解:90hz说的就是一秒刷新90帧,250ms延时意味着4帧/s,一帧25个物理模拟步骤意味着一秒一共需要100个物理模拟步骤,这是对不上的。其实这边理解很简单的应该就是每秒需要计算90次物理模拟步骤,对于CPU压力会很大。】

 
 

This leaves two options: a client/server network model with client-side prediction (perhaps with dedicated server) and a less secure distributed simulation network model.【这样就还剩下两种方案】

 
 

Since this was a non-competitive sample, there was little justification to incur the cost of running dedicated servers. Therefore, whether I implemented a client/server model with client-side prediction or distributed simulation model, the security would be effectively the same. The only difference would be if only one of the players in the game could theoretically cheat, or all of them could.【由于这是一个非竞争性的样本,没有理由承担运行专用服务器的成本来保证公平和安全。】

 
 

For this reason, a distributed simulation model made the most sense. It had effectively the same amount of security, and would not require any expensive rollback and resimulation, since players simply take authority over cubes they interact with and send the state for those cubes to other players.【因为这些理由,我们选择分布式模拟的方案。它实际上具有相同的安全性,并且不需要任何昂贵的回滚和重新模拟,因为玩家只需对与其交互的立方体授权并将这些立方体的状态发送给其他玩家。】

 
 

 
 

Authority Scheme

 
 

While it makes intuitive sense that taking authority (acting like the server) for objects you interact can hide latency – since, well if you’re the server, you don’t experience any lag, right? – what’s not immediately obvious is how to resolve conflicts.【尽管直观地表明,为你所交互的对象赋予权限(像服务器一样)可以隐藏延迟因为如果你是服务器,那么你不会遇到任何延迟,对吧?这里存在的明显问题就是如何解决冲突。】

 
 

What if two players interact with the same stack? What if two players, masked by latency, grab the same cube? In the case of conflict: who wins, who gets corrected, and how is this decided?【如果两个玩家与同一个堆栈交互会怎样?
如果两个玩家,在延迟的掩盖下抓住同一个立方体怎么办? 在冲突的情况下:谁获胜,谁得到纠正,这是如何决定的?】

 
 

My intuition at this point was that because I would be exchanging state for objects rapidly (up to 60 times per-second), that it would be best to implement this as an encoding in the state exchanged between players over my network protocol, rather than as events.【因为我会经常快速地交换对象的状态(每秒最多60次),所以直觉上最好在网络中交换状态时使用编码,而不是作为事件。】

 
 

I thought about this for a while and came up with two key concepts:

  1. Authority
  2. Ownership

【这里先列出两个关键的概念:AuthorityOwnership

 
 

Each cube would have authority, either set to default (white), or to whatever color of the player that last interacted with it. If another player interacted with an object, authority would switch and update to that player. I planned to use authority for interactions of thrown objects with the scene. I imagined that a cube thrown by player 2 could take authority over any objects it interacted with, and in turn any objects those objects interacted with, recursively.【每个方块都必须要有Authority,默认的或者就是最后一次与他交互的玩家。如果其他玩家于这个方块交互,authority需要跟新切换到这个新的玩家。我计划使用Authority来处理投掷对象与场景的交互。
我想到玩家2抛出的立方体可以对与其交互的任何其他对象拥有Authority,并且对这些对象进行交互的任何对象都是递归的。】

 
 

Ownership was a bit different. Once a cube is owned by a player, no other player could take ownership until that player reliquished ownership. I planned to use ownership for players grabbing cubes, because I didn’t want to make it possible for players to grab cubes out of other player’s hands after they picked them up.Ownership 则不一样,一旦一个立方体属于一个玩家,其他玩家在这个玩家释放Ownership权限前都无法获得这个立方体的Ownership权限。我计划将Ownership用于抓取立方体的玩家,因为我不想让玩家抢夺其他玩家手中抓取的立方体。】

 
 

I had an intuition that I could represent and communicate authority and ownership as state by including two different sequence numbers per-cube as I sent them: an authority sequence, and an ownership sequence number. This intuition ultimately proved correct, but turned out to be much more complicated in implementation than I expected. More on this later.【我想到可以通过 an authority sequence, and an ownership sequence number 来做表示和同步,这个最后被证明是可行的,后面说实现细节。】

 
 

 
 

State Synchronization

 
 

Trusting I could implement the authority rules described above, my first task was to prove that synchronizing physics in one direction of flow could actually work with Unity and PhysX. In previous work I had networked simulations built with ODE, so really, I had no idea if it was really possible.【要证实我可以实现上述的权威规则,我的第一个任务是证明UnityPhysX情况下物理同步是可行的。】

 
 

To find out, I setup a loopback scene in Unity where cubes fall into a pile in front of the player. There are two sets of cubes. The cubes on the left represent the authority side. The cubes on the right represent the non-authority side, which we want to be in sync with the cubes on the left.【我设置了一个unity测试场景,两坨方块,左边的是Authority,右边的是同步得到的结果,就是Non-Authority。】

 
 

 
 

At the start, without anything in place to keep the cubes in sync, even though both sets of cubes start from the same initial state, they give slightly different end results. You can see this most easily from top-down:【两边一模一样的初始化开始,但是得到了不一样的最终结果,如下图。】

 
 

 
 

This happens because PhysX is non-deterministic. Rather than tilting at non-determinstic windmills, I fight non-determinism by grabbing state from the left side (authority) and applying it to the right side (non-authority) 10 times per-second:【这是因为Physx是不确定性的,我通过每秒10次同步状态来解决不确定性这个问题。】

 
 

 
 

The state I grab from each cube looks like this:【对于每个方块同步的状态组成如下】

 
 

 
 

And when I apply this state to the simulation on the right side, I simply snap the position, rotation, linear and angular velocity of each cube to the state captured from the left side.【当我将这个状态应用到右侧的模拟中时,我只需将左侧每个立方体捕获的位置,旋转,线性和角速度等状态赋给右侧。】

 
 

This simple change is enough to keep the left and right simulations in sync. PhysX doesn’t even diverge enough in the 1/10th of a second between updates to show any noticeable pops.【这个简单的改变就可以保证从左边到右边的模拟同步,Physx不会产生足够的不一致。】

 
 

 
 

This proves that a state synchronization based approach for networking can work with PhysX. (Sigh of relief). The only problem of course, is that sending uncompressed physics state uses way too much bandwidth…【这证实physx支持基于网络状态的同步,唯一的问题当然是发送未压缩的物理状态使用了太多的带宽

 
 

 
 

Bandwidth Optimization

 
 

To make sure the networked physics sample is playable over the internet, I needed to get bandwidth under control.【接下来我们要做的就是优化带宽】

 
 

The easiest gain I found was to simply encode the state for at rest cubes more efficiently. For example, instead of repeatedly sending (0,0,0) for linear velocity and (0,0,0) for angular velocity for at rest cubes, I send just one bit:【一个简单的高收益方法就是更有效地编码静态方块。例如下方所示,velocity选项变的可有可无。】

 
 

 
 

This is lossless technique because it doesn’t change the state sent over the network in any way. It’s also extremely effective, since statistically speaking, most of the time the majority of cubes are at rest.【这是无损的一种方法,没有改变任何的网络状态,但同时非常的有效,因为场景中存在的大量方块都是静态的。】

 
 

To optimize bandwidth further we need to use lossy techniques. For example, we can reduce the precision of the physics state sent over the network by bounding position in some min/max range and quantizing it to a resolution of 1/1000th of a centimeter and sending that quantized position as an integer value in some known range. The same basic approach can be used for linear and angular velocity. For rotation I used the smallest three representation of a quaternion.【为了进一步优化带宽,我们需要使用有损技术。
例如我们通过在某些最小/最大范围内限定并量化为1/1000厘米的分辨率,其可以用整数来替代,有效的减少数据量。 相同的基本方法可以用于速度和角速度。 旋转我使用了通过三个值来表示的四元数来表示。】

 
 

But while this saves bandwidth, it also adds risk. My concern was that if we are networking a stack of cubes (for example, 10 or 20 cubes placed on top of each other), maybe the quantization would create errors that add jitter to that stack. Perhaps it would even cause the stack to become unstable, but in a particularly annoying and hard to debug way, where the stack looks fine for you, and is only unstable in the remote view (eg. the non-authority simulation), where another player is watching what you do.【这虽然节省了带宽,但也增加了风险。
我担心的是如果我们联网了一堆立方体(例如,1020个立方体放在另一个立方体上),也许量化会产生jitter这类的错误。 也许甚至会导致堆栈变得不稳定(自己是好的,别人看到的你都是有问题的)。】

 
 

The best solution to this problem that I found was to quantize the state on both sides. This means that before each physics simulation step, I capture and quantize the physics state exactly the same way as when it’s sent over the network, then I apply this quantized state back to the local simulation.【我发现这个问题的最佳解决方案是量化双方的状态。
就是说在每个物理模拟步骤之前,我捕获和量化物理状态,同时用于本地模拟和网络发送。】

 
 

Now the extrapolation from quantized state on the non-authority side exactly matches the authority simulation, minimizing jitter in large stacks. At least, in theory.【现在,Non-Authority方的状态和Authority的模拟完全匹配,最大限度的减少了Jitter。

 
 

 
 

Coming To Rest

 
 

But quantizing the physics state created some very interesting side-effects!【但量化物理状态创造了一些非常有趣的副作用!】

 
 

  1. PhysX doesn’t really like you forcing the state of each rigid body at the start of every frame and makes sure you know by taking up a bunch of CPU.PhysX并不真的喜欢你在每一帧开始时强制每个刚体的状态,且这事CPU占用严重。】
  2. Quantization adds error to position which PhysX tries very hard to correct, snapping cubes immediately out of penetration with huge pops!【量化会增加PhysX尝试纠正的位置错误,这个有时候会导致方块失控。】
  3. Rotations can’t be represented exactly either, again causing penetration. Interestingly in this case, cubes can get stuck in a feedback loop where they slide across the floor!【旋转不能这么搞,会导致立方体可能会卡在反馈回路中,并在地面上滑动!】
  4. Although cubes in large stacks seem to be at rest, close inspection in the editor reveals that they are actually jittering by tiny amounts, as cubes are quantized just above surface and falling towards it.【尽管大堆中的立方体似乎处于静止状态,但编辑人员仔细检查发现,实际上它们实际上在微小的抖动。】

 
 

There’s not much I could do about the PhysX CPU usage, but the solution I found for the depenetration was to set maxDepenetrationVelocity on each rigid body, limiting the velocity that cubes are pushed apart with. I found that one meter per-second works very well.【关于PhysX CPU使用情况我没有太多可以做的,但是我发现的解决方案的解决方案是在每个刚体上设置maxDepenetrationVelocity,限制立方体被推开的速度。 我发现每秒一米的效果非常好。】

 
 

Getting cubes to come to rest reliably was much harder. The solution I found was to disable the PhysX at rest calculation entirely and replace it with a ring-buffer of positions and rotations per-cube. If a cube has not moved or rotated significantly in the last 16 frames, I force it to rest. Boom. Perfectly stable stacks with quantization.【让立方体完全静止是非常困难的。
我找到的解决方案是完全停用PhysX,并将其替换为每个立方体的位置和旋转的ring-buffer。 如果一个立方体在最后的16帧中没有明显的移动旋转,我强迫它休息(静止)。 】

 
 

Now this might seem like a hack, but short of actually getting in the PhysX source code and rewriting the PhysX solver and at rest calculations, which I’m certainly not qualified to do, I didn’t see any other option. I’m happy to be proven wrong though, so if you find a better way to do this, please let me know 🙂【这可能看起来不是完美的解决方案,最好的就是进入PhysX源代码并重新编写PhysX解算器,加入休眠计算,我没有办法这么做,但我没有看到任何其他好的替代方案,你能解决的话求告诉我。】

 
 

 
 

Priority Accumulator

 
 

The next big bandwidth optimization I did was to send only a subset of cubes in each packet. This gave me fine control over the amount of bandwidth sent, by setting a maximum packet size and sending only the set of updates that fit in each packet.【我做的下一个带来巨大带宽优化的做法是每个网络包发送一组方块的数据。
这使我能够很好地控制发送带宽量,方法是设置最大数据包并只发送每个数据包的更新集。(优先级分包发送)】

 
 

Here’s how it works in practice:【具体做法】

 
 

  1. Each cube has a priority factor which is calculated each frame. Higher values are more likely to be sent. Negative values mean “don’t send this cube”.【每个立方体都具有优先系数,更高的值更可能被发送,负值意味着”不要发送这个立方体”。】
  2. If the priority factor is positive, it’s added to the priority accumulator value for that cube. This value persists between simulation updates such that the priority accumulator increases each frame, so cubes with higher priority rise faster than cubes with low priority.【如果方块的优先级因子为正,则将其添加到其优先级累加器值。
    该值在模拟期间持续存在,每帧不清0
  3. Negative priority factors clear the priority accumulator to -1.0.【否定优先因子将优先累加器清除为-1.0。】
  4. When a packet is sent, cubes are sorted in order of highest priority accumulator to lowest. The first n cubes become the set of cubes to potentially include in the packet. Objects with negative priority accumulator values are excluded.【按照优先级累加器数值从高到低排列方块,前n个立方体成为一个数据包中的立方体集合,排除具有负优先级累加器值的对象。】
  5. The packet is written and cubes are serialized to the packet in order of importance. Not all state updates will necessarily fit in the packet, since cube updates have a variable encoding depending on their current state (at rest vs. not at rest and so on). Therefore, packet serialization returns a flag per-cube indicating whether it was included in the packet.【立方体按照重要性排序串行化到数据包,不是所有的方块状态都需要更新。】
  6. Priority accumulator values for cubes sent in the packet are cleared to 0.0, giving other cubes a fair chance to be included in the next packet.【数据包中发送的方块的优先累加器值被清除为0.0,使其他多维数据集有机会被包含在下一个数据包中。】

 
 

For this demo I found some value in boosting priority for cubes recently involved in high energy collisions, since high energy collision was the largest source of divergence due to non-deterministic results. I also boosted priority for cubes recently thrown by players.【因为高能碰撞是非确定性结果引起的最大分歧源,因此我提高了最近抛出的立方体的优先级。】

 
 

Somewhat counter-intuitively, reducing priority for at rest cubes gave bad results. My theory is that since the simulation runs on both sides, at rest cubes would get slightly out of sync and not be corrected quickly enough, causing divergence when other cubes collided with them.【有点反直觉,降低休息立方体的优先级给出了不好的结果。
我猜测是由于收发双方都在模拟运行,静止立方体的略有的不同步不能很快纠正的话,其他立方体与它们碰撞时就会引起分歧。】

 
 

 
 

Delta Compression

 
 

Even with all the techniques so far, it still wasn’t optimized enough. With four players I really wanted to get the cost per-player down under 256kbps, so the entire simulation could fit into 1mbps for the host.【即使采用了上面所讲的所有技术,仍然不够。
我希望每人带宽低于256kbps当四个人在场景里面玩耍的时候,这样主机也就控制在1mbps。】

 
 

I had one last trick remaining: delta compression.【我还剩下最后一招:增量压缩】

 
 

First person shooters often implement delta compression by compressing the entire state of the world relative to a previous state. In this technique, a previous complete world state or ‘snapshot’ acts as the baseline, and a set of differences, or delta, between the baseline and the current snapshot is generated and sent down to the client.【第一人称射击者通常对相对于先前状态的整个世界的所有状态来实施增量压缩。
在这种技术中,先前的完整世界状态充当基准,并且生成过去和当前之间的一组差异或增量,并将其发送到客户端。】

 
 

This technique is (relatively) easy to implement because the state for all objects are included in each snapshot, thus all the server needs to do is track the most recent snapshot received by each client, and generate deltas from that snapshot to the current.【由于所有对象的状态都包含在每个快照中,所以该技术相对容易实现,因此所有服务器需要执行的操作是跟踪每个客户端接收到的最新快照,并生成从该快照到当前的增量。】

 
 

However, when a priority accumulator is used, packets don’t contain updates for all objects and delta encoding becomes more complicated. Now the server (or authority-side) can’t simply encode cubes relative to a previous snapshot number. Instead, the baseline must be specified per-cube, so the receiver knows which state each cube is encoded relative to.【但是使用了优先级累加器后,数据包不包含所有对象的更新,这使得增量编码变得更加复杂。
现在服务器不能简单地将立方体相对于先前的快照进行编码。 而是必须指定每个多维数据集的基线,以便接收器知道每个多维数据集相对于哪个进行编码。】

 
 

The supporting systems and data structures are also much more complicated:【支持系统和数据结构也复杂得多】

  1. A reliability system is required that can report back to the sender which packets were received, not just the most recently received snapshot.【系统需要能够向发送方报告接收到哪些数据包,而不仅仅是最近接收到的快照】
  2. The sender needs to track the states included in each packet sent, so it can map packet level acks to sent states and update the most recently acked state per-cube. The next time a cube is sent, its delta is encoded relative to this state as a baseline.【发送者需要跟踪发送的每个数据包中包含的状态,因此它可以将数据包级别映射到发送状态,并更新最近每个多维数据集的最近查询状态。
    下一次发送多维数据集时,它的增量将相对于此状态编码为基准。】(这边意思就是说数据包级别和发送状态是一个变量标识的,也由此来识别编码基准)
  3. The receiver needs to store a ring-buffer of received states per-cube, so it can reconstruct the current cube state from a delta by looking up the baseline in this ring-buffer.【接收器的环形缓冲区需要存储每个立方体接收到的状态,因此它可以在该环形缓冲区中查找任意一个当前的立方体状态的基线来重建当前状态。】

 
 

But ultimately, it’s worth the extra complexity, because this system combines the flexibility of being able to dynamically adjust bandwidth usage, with the orders of magnitude bandwidth improvement you get from delta encoding.【但这一切的复杂性是值得的,因为这方案能够动态调整带宽的使用,同时获得数量级级别的带宽改进。】

 
 

 
 

Delta Encoding

 
 

Now that I have the supporting structures in place, I actually have to encode the difference of a cube relative to a previous baseline state. How is this done?【上面讲到了整个增量压缩的架构,实际上怎么进行差异编码这里来讲。】

 
 

The simplest way is to encode cubes that haven’t changed from the baseline value as just one bit: not changed. This is also the easiest gain you’ll ever see, because at any time most cubes are at rest, and therefore aren’t changing state.【最简单的方法是用一位来标记有没有变化。
这其实收益非常大,因为在任何时候大多数立方体都不会改变状态。】

 
 

A more advanced strategy is to encode the difference between the current and baseline values, aiming to encode small differences with fewer bits. For example, delta position could be (-1,+2,+5) from baseline. I found this works well for linear values, but breaks down for deltas of the smallest three quaternion representation, as the largest component of a quaternion is often different between the baseline and current rotation.【更高级的策略是对当前值和基准值之间的差异进行编码,目的就是用较少的位对差异进行编码。
例如标记起点从基线(-1+ 2+ 5)开始。 我发现这适用于线性值,但是对于用三个值表示的四元数作用不大。】

 
 

Furthermore, while encoding the difference gives some gains, it didn’t provide the order of magnitude improvement I was hoping for. In a desperate, last hope, I came up with a delta encoding strategy that included prediction. In this approach, I predict the current state from the baseline assuming the cube is moving ballistically under acceleration due to gravity.【此外,虽然编码差异带来了一些收益,但它达不到数量级的提升。
最后我想出了一种包含预测的增量编码策略。 在这种方法中,假设立方体由于重力而在加速度下运动,我可以基于此来预测基线的当前状态】

 
 

Prediction was complicated by the fact that the predictor must be written in fixed point, because floating point calculations are not necessarily guaranteed to be deterministic. But after a few days of tweaking and experimentation, I was able to write a ballistic predictor for position, linear and angular velocity that matched the PhysX integrator within quantize resolution about 90% of the time.【预测因子写入固定值这做法很难,因为浮点计算不一定保证确定性。
但经过几天的调整和实验之后,我可以写出一个弹道预测器,与PhysX结果匹配的位置,速度和角速度相似性大于90%。】

 
 

These lucky cubes get encoded with another bit: perfect prediction, leading to another order of magnitude improvement. For cases where the prediction doesn’t match exactly, I encoded small error offset relative to the prediction.【这些幸运的cubes用一个bit来表示,使得压缩效果达到了数量级的提升。
这种情况下我的编码结果和真实的结果有一个小的错误偏移量。】

 
 

In the time I had to spend, I not able to get a good predictor for rotation. I blame this on the smallest three representation, which is highly numerically unstable, especially in fixed point. In the future, I would not use the smallest three representation for quantized rotations.【但是对于旋转量是没有办法这么做的,因为四元数的三个值数值上是非常不稳定的。 将来,我不会使用三个值表示的四元数来表示旋转。】

 
 

It was also painfully obvious while encoding differences and error offsets that using a bitpacker was not the best way to read and write these quantities. I’m certain that something like a range coder or arithmetic compressor that can represent fractional bits, and dynamically adjust its model to the differences would give much better results, but I was already within my bandwidth budget at this point and couldn’t justify any further noodling 🙂【编码差异和错误补偿也是非常明显的,因为这种封装方式并不是读取和写入这些数值的最佳方式。
我确定采用范围编码器或算术压缩器,并根据差异动态调整这两个工具模型会得到更好的结果,但此时我已经达到了我带宽目标,不再继续处理了🙂

 
 

 
 

Synchronizing Avatars

 
 

After several months of work, I had made the following progress:【经过几个月的工作,我取得了以下进展:】

 
 

  • Proof that state synchronization works with Unity and PhysX【证明状态同步适用于UnityPhysX
  • Stable stacks in the remote view while quantizing state on both sides【远程和本地状态同步且稳定】
  • Bandwidth reduced to the point where all four players can fit in 1mbps【四个玩家的情况下带宽控制在了1mbps

 
 

The next thing I needed to implement was interaction with the simulation via the touch controllers. This part was a lot of fun, and was my favorite part of the project 🙂【我需要实现的下一件事是通过Touch控制器交互,这部分我非常喜欢且非常有趣】

 
 

I hope you enjoy these interactions. There was a lot of experimentation and tuning to make simple things like picking up, throwing, passing from hand to hand feel good, even crazy adjustments to ensure throwing worked great, while placing objects on top of high stacks could still be done with high accuracy.【我希望你喜欢这些交互,这里我们为了保证拾取,投掷,传球等动作效果好,做了疯狂的实验和调整】

 
 

But when it comes to networking, in this case the game code doesn’t count. All the networking cares about is that avatars are represented by a head and two hands driven by the tracked headset and touch controller positions and orientations.【一般情况下头和双手都是由头盔和手柄的位置和方向驱动的。但是对于网络传输过去的avatar,本地设备驱动是不奏效的。】

 
 

To synchronize this I captured the position and orientation of the avatar components in FixedUpdate along the rest of the physics state, and applied this state to the avatar components in the remote view.【我获取了avatar组件的位置和旋转量来同步传输和应用给远端的avatar。】

 
 

But when I first tried this it looked absolutely awful. Why?【但是当我第一次尝试这个时,它看起来非常糟糕。
为什么?】

 
 

After a bunch of debugging I worked out that the avatar state was sampled from the touch hardware at render framerate in Update, and was applied on the other machine at FixedUpdate, causing jitter because the avatar sample time didn’t line up with the current time in the remote view.【debug的时候发现,硬件设备的位置跟新和基于渲染的frame更新,时间是不一致的,这个会导致远程跟新jitter。】

 
 

To fix this I stored the difference between physics and render time when sampling avatar state, and included this in the avatar state in each packet. Then I added a jitter buffer with 100ms delay to received packets, solving network jitter from time variance in packet delivery and enabling interpolation between avatar states to reconstruct a sample at the correct time.【为了解决这个问题,我存储物理和渲染的时候的avatar的状态差异,并将其包含在每个avatar状态的数据包中。
然后我添加了一个100ms的延迟抖动缓冲区接收数据包,解决数据包传输时间差异造成的网络抖动,并在avatar状态之间启用插值,确保效果。】

 
 

To synchronize cubes held by avatars, while a cube is parented to an avatar’s hand, I set the cube’s priority factor to -1, stopping it from being sent with regular physics state updates. While a cube is attached to a hand, I include its id and relative position and rotation as part of the avatar state. In the remote view, cubes are attached to the avatar hand when the first avatar state arrives with that cube parented to it, and detached when regular physics state updates resume, corresponding to the cube being thrown or released.【为了同步由Avatar持有的cubes,当一个cube处于化身状态时,我将其优先因子设置为-1,从而阻止它以常规物理状态更新发送。当一个cube附着在手上时,我会将其ID和相对位置以及旋转作为avatar的状态的一部分。 在远端当第一个avatar状态到达时,立方体与该虚拟形体相连,并在常规物理状态更新恢复时分离,对应于正在抛出或释放的立方体。】

 
 

 
 

Bidirectional Flow

 
 

Now that I had player interaction with the scene working with the touch controllers, it was time to start thinking about how the second player can interact with the scene as well.【现在我已经可以使用控制器与场景进行交互了,现在开始考虑第二个玩家如何与场景互动。】

 
 

To do this without going insane switching between two headsets all the time (!!!), I extended my Unity test scene to be able to switch between the context of player one (left) and player two (right).【要做到这一点,为了测试的时候无需一直在两个头盔之间进行疯狂的切换,我扩展了Unity测试场景,以便能够在玩家1(左)和玩家2(右)之间切换。】

 
 

I called the first player the “host” and the second player the “guest”. In this model, the host is the “real” simulation, and by default synchronizes all cubes to the guest player, but as the guest interacts with the world, it takes authority over these objects and sends state for them back to the host player.【我把第一个玩家称为”host”,第二个玩家称为”guest”。
在这个模型中,host是”真实”模拟,默认情况下所有立方体都会同步到guest玩家,但是随着guest与世界的交互,它需要对这些对象进行控制,并将状态发送回host玩家。】

 
 

To make this work without inducing obvious conflicts the host and guest both check the local state of cubes before taking authority and ownership. For example, the host won’t take ownership over a cube already under ownership of the guest, and vice versa, while authority is allowed to be taken, to let players throw cubes at somebody else’s stack and knock it over while it’s being built.【为了解决冲突,host和guest在获得权限和所有权之前都会检查立方体的本地状态。例如,host不会对guest拥有所有权的cubes拥有所有权,反之亦然。】

 
 

Generalizing further to four players, in the networked physics sample, all packets flow through the host player, making the host the arbiter. In effect, rather than being truly peer-to-peer, a topology is chosen that all guests in the game communicate only with the host player. This lets the host decide which updates to accept, and which updates to ignore and subsequently correct.【进一步推广到四个玩家,在网络物理示例中,所有数据包都会流经host玩家,让host仲裁。
这实际上不是真正的点对点,而是选择游戏中的所有guest仅与host玩家通信的拓扑方式。 这让host可以决定接受哪些更新以及忽略哪些更新并随后进行更正。】

 
 

To apply these corrections I needed some way for the host to override guests and say, no, you don’t have authority/ownership over this cube, and you should accept this update. I also needed some way for the host to determine ordering for guest interactions with the world, so if one client experiences a burst of lag and delivers a bunch of packets late, these packets won’t take precedence over more recent actions from other guests.【要应用这些更正,我需要某种方式让host覆盖guest的结果。我还需要一些方法让host确定这些guests与整个世界互动的顺序。因此如果一个客户端经历了一段时间的延迟并延迟发送大量数据包,这些数据包的优先级将低于来自其他客户的数据包。】

 
 

As per my hunch earlier, this was achieved with two sequence numbers per-cube:【按照我之前的做法,这一切通过每个立方体的两个序列号实现的:】

  1. Authority sequence
  2. Ownership sequence

 
 

These sequence numbers are sent along with each state update and included in avatar state when cubes are held by players. They are used by the host to determine if it should accept an update from guests, and by guests to determine if the state update from the server is more recent and should be accepted, even when that guest thinks it has authority or ownership over a cube.【这些序号随着每个状态更新一起发送,并包含玩家持有的cubes的状态。
host使用它们来确定是否应接受来自guest的更新,对于guest来讲则是强制更新来自host的状态信息。】

 
 

Authority sequence increments each time a player takes authority over a cube and when a cube under authority of a player comes to rest. When a cube has authority on a guest machine, it holds authority on that machine until it receives confirmation from the host before returning to default authority. This ensures that the final at rest state for cubes under guest authority are committed back to the host, even under significant packet loss.【每次玩家取得和释放cube的权限,权限序列都会增加。
当guest具有一个cube的权限时,它将保持这个权限直到它从host接收到返回默认状态的信息。 这确保了即使在大量丢包的情况下,guest权限下的cubes处于静止状态也会被提交给主机(因为主机不确认就一直随着avatar发送信息)。】

 
 

Ownership sequence increments each time a player grabs a cube. Ownership is stronger than authority, such that an increase in ownership sequence wins over an increase in authority sequence number. For example, if a player interacts with a cube just before another player grabs it, the player who grabbed it wins.【每次玩家抓取cube时,ownership序列都会增加。
ownership比authority更强大,因此ownership序列的增加会赢得authority 序列号的增加。 例如,如果玩家在另一个玩家抓住它之前与立方体进行交互,那么抓住它的玩家将获胜。】

 
 

In my experience working on this demo I found these rules to be sufficient to resolve conflicts, while letting host and guest players interact with the world lag free. Conflicts requiring corrections are rare in practice even under significant latency, and when they do occur, the simulation quickly converges to a consistent state.【根据我在这个demo中的经验,我发现这些规则足以解决冲突,同时让host和guest与世界进行互动。
即使在严重的等待时间下,需要更正的冲突在实践中也很少见,而且当它们确实发生时,仿真会迅速收敛到一致的状态。】

 
 

 
 

Conclusion

 
 

High quality networked physics with stable stacks of cubes is possible with Unity and PhysX using a distributed simulation network model.UnityPhysX使用分布式仿真网络模型,可以实现高品质的网络物理和稳定的立方体堆栈。】

 
 

This approach is best used for cooperative experiences only, as it does not provide the security of a server-authoritative network model with dedicated servers and client-side prediction.【这种方法最适合仅用于协作体验,因为它不能提供具有专用服务器和客户端预测的服务器权威网络模型的安全性。(也就是安全性是不够的)】

 
 

Thanks to Oculus for sponsoring my work and making this research possible!【感谢Oculus赞助我的工作并使这项研究成为可能!】

 
 

The source code for the networked physics sample can be downloaded here.

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

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的情况下的使用。

Machine Learning Techniques Lecture 9: Decision Tree


 
 

内容:

介绍了Decision Tree模型,他的hypothesis就是对于不同的条件,不同的路径上面有不同的小g;他的算法就是把这种树形结构通过对资料越切越纯直到不能再切为止,递归的建立起来。一种实例算法C&RT则是对Decision Tree进一步做了四个决定:怎么做regression,怎么砍树,怎么处理类别输入,怎么处理特征丢失。最后可视化的举例看这个演算法的演进过程。

 
 


 
 

上一讲:

Adaptive Boosting 演算法,透过调整每一笔资料的权重的方式来得到不一样的hypothesis,同时在计算过程中决定每一个hypothesis的权重,然后用linear 的方式合起来,这样的方式被证明可以让分类结果变得比较好。

 
 

这一讲:

Decision Tree

 
 


 
 

我们先来看看 aggregation model:就是可以通过很多的g合起来变成大G来提升效果。这包括两种主要的面向。

Blending:我们已经得到了一些小g,可以透过uniform/non-uniform/conditional的方式把他们合起来,这三种情况下的blending的做法叫做 averaging/linear/stacking。

Learning:我们并不知道有哪些小g,需要边学习小g,边把他们合起来,同样可以透过uniform/non-uniform/conditional 的方式把他们合起来,这三种情况下的blending的做法叫做 Bagging/Adaboost/Decision Tree。

 
 

Decision Tree 就是补完这张表格,在不同情况下使用不同的小g,而且是边学习边合起来使用。这个方法的起源非常早,都比机器学习这个名词的出现还早,其做法就是模仿的人类的认知决策过程。

 
 


 
 

什么叫做Decision Tree?

 
 

这里是一个例子:你到底要不要下班后打开线上课程学习?

首先看是否下班早,早回则看一下是否有约会,晚回则看一下是否是作业的deadline,再确定会不会打开线上课程。

 
 

我们怎么来表达这个hypothesis?

 
 

小g:叶子节点,最后的决定;q:非叶子节点,条件,每一个都是比较简单的判断;所有的合起来就是G。

就是模仿人类的决策过程。

 
 


 
 

Decision Tree 也可以看作是:

每一个非叶子节点产生的每一个分支,都是一颗子树。b代表的就是分支,G_c就是在c的情况下的子树。

把一颗大大的树拆成几棵小树,递归定义。

 
 


 
 

在讲算法之前,先告诉大家一下有关Decision Tree的Disclaimers

 
 

优点:描述了整个做决定的过程,人很好理解,具有可解释性;非常简单;计算效率高。

缺点:基本没有什么理论保证,专注于流程设计;怎么去设计分支很难;通常没有什么比较具有代表性的好坏的算法。

 
 


 
 

练习

 
 


 
 

上面的黄色框表示的是递归公式表示的Decision Tree,够过这个公式可以把其演算法写出来:

输入是所有的资料,目标是产生一个树(G),过程中我们需要知道的是怎么产生分支(g)。

  1. 先看怎么做分支
  2. 根据分支分块
  3. 每一个分块用来学出小小的树,看是否要停下,不停下的话每棵小树再继续上面三步
  4. 所有的小树合起来就是G

 
 

一共包括四个决定:要分几支,怎么做分支,什么时候要停下开始组合G,叶子节点的结果是什么。对于每一个具体的Decision Tree演算法,都是对上面的四个决定做了独特的设计。

 
 


 
 

今天要给大家介绍的演算法: Classification & Regression Tree (C&RT)

 
 

  1. 每次一刀切成两份,就是分成两支(binary tree);
  2. 最后回传的g是constant,叶子就是一个常数,常数是由当前叶子范围内的Ein是最小的;

 
 


 
 

  1. 利用decision stump来切两半,也就是说只看一个feature,并通过这个feature把资料分成两半。

    切开后怎么样是最好呢?purifying:看切开后得到的资料看起来比较纯(y近似),用切开后两边会最纯的情况作为这次的切分。也就是说切开后纯度越来越高。

 
 


 
 

怎么衡量纯度?

可以看切开后要回传的常数是否够好来描述纯度,也就是用Ein来衡量。一般使用的时候classification的时候Gini比较常用,regression的时候regression error比较常用来衡量纯度。

 
 


 
 

  1. 所有的y都一样的话会被迫停下来,完全的纯,回传常数;

    所有的x都一样的话也会被迫停下来,完全没有下刀的情况;

    长到被迫停下来的树叫做fully-grown tree

 
 


 
 

练习

 
 


 
 

把 C&RT 做的四项选择写入到 decision tree 的算法里面就得到了 C&RT 的算法描述。上面的橙色,红色,绿色,蓝色对应的就是四个决定。

这种算法的一大好处就是处理multi-class classification和binary classification一样简单。

 
 


 
 

按照上面讲的 fully-grown tree 的切割方式来切的话,一定会得到Ein=0的树。但是这样是会比较不妙,会有overfit。

 
 

我们需要一些regularizer的机制来控制复杂度来放置overfit。

 
 

Pruned Decision Tree:

一种方式是控制树叶的数量,也就是不让切特别多刀,树叶的数目和切的刀数相关。

所以做法可以是把所有的树都做出来,看看每棵树的Ein是多少,算算其复杂度是多少,然后用lamda平衡一下,我们不要只选择切的很深的Ein很小的树。

这件事情不那么好做,我们要考虑遍历所有的可能的树的结构不现实。

 
 

实际上的做法:

首先得到一颗完全长成的树,然后尝试着去合并一次两片叶子,做所有的情况,找出只合并两片叶子Ein最小的树G_1。再从这摘掉一片叶子的树出发在同上面的方法再去摘一片叶子,得到最好的摘掉两片叶子的树G_2。以此类推得到G_n。

我们接下来就是在这些摘掉x片叶子最好的树里面做选择,找到一个平衡的最佳解,就是去确定lamda,方法是validation。

 
 


 
 

C&RT 还有一些其他的特征:

 
 

【类别支持】

  1. 输入部分不一定是数字,可能是类别,例如病人的症状等,会影响怎么去做切割。

这时候需要用 Decision Subset 来做切割:可以穷举类别,人为定义左右或者大小来做。

 
 


 
 

对于人来说:

例如我使用体重来区分人群,但是有个人进来忘了称体重,怎么办?可能是去马上去量体重;可能通过目测身高估体重,所以可以改通过身高区分。

 
 

【支持特征丢失的资料】

  1. 对于特征丢失的资料,怎么用我们的Decision Tree来处理呢?

训练的时候会为每个特征找一些替代品,通过替代品做切割得到的结果要和原来的方式类似,替代品是训练的时候就已经学习好了的。

 
 


 
 

练习

 
 


 
 

一个例子

 
 


 
 

确定下刀,两边各自组成树,合起来就是大树。

 
 


 
 

第二刀

 
 


 
 

第三刀

 
 


 
 

第四刀

 
 


 
 

区域都纯洁了

 
 


 
 

回传叶子节点的类型

 
 


 
 

递归上一层

 
 


 
 

再上一层

 
 


 
 

回到大树

 
 


 
 

和Adaboost对比:Adaboost每一刀一定是贯穿整个区域,但是decision Tree就不一定,因此相对来说比较有效率。

 
 


 
 

复杂的例子

 
 


 
 

C&RT 算法的好处:

  1. 人看得懂的决策方式
  2. 可以容易的处理多类别分类
  3. 可以容易的处理类别输入
  4. 可以支持测试资料的特征残缺
  5. 训练测试都很有效率

几乎没有其他的模型有这么多的好处,因此也是一种常用的方法。

 
 

实际上还有 C4.5 这种 decision tree 算法,自己可以去看一下做了哪些特殊决定得到的。

 
 


 
 

练习

 
 


 
 

总结:

介绍了Decision Tree模型,他的hypothesis就是对于不同的条件,不同的路径上面有不同的小g;他的算法就是把这种树形结构通过对资料越切越纯直到不能再切为止,递归的建立起来。一种实例算法C&RT则是对Decision Tree进一步做了四个决定:怎么做regression,怎么砍树,怎么处理类别输入,怎么处理特征丢失。最后可视化的举例看这个演算法的演进过程。

 
 

下一讲:

至此讲完了Aggregation的基本模型,下一讲进入一个更高的境界,开始把已有的aggregation方法混起来用,叫做Aggregation of Aggregation。

Machine Learning Techniques Lecture 8: Adaptive Boosting


 
 

内容:

介绍了 Adaboost 演算法,一开始先给大家一个小学生课堂的例子来告诉大家这个演算法想像上是长什么样子的。这算法的关键是每一轮的时候透过重新的给每一个example不一样的权重,提高错误的权重,降低正确的权重来得到不一样的g,最后再把g整合成G。最后给了一个adaboost配合decision stump以后的实例,可以工作的很好。

 
 


 
 

上一讲:开始讲aggregation model,就是想办法把很多的小g合起来变成一个更符合你需求的大G。然后讲到blending,就是如果你已经有很多小g在手上的时候,你可以让他们求平均或者加权投票或者更复杂的非线性组合它们。那如果手上只有一堆已有的资料,那么可以通过bootstrap的方式得到一堆资料集,然后得到一堆小g求大G,这样的演算法叫做bagging。

 
 

今天从这系概念出发,讲一个有趣的演算法。

 
 


 
 

举例:老师交学生辨识图中有没有苹果做法

 
 

首先去网络上手机苹果图片。

 
 


 
 

收集了10张苹果图片,10张不是苹果的图片。老师就是想通过这些数据来学到怎样区分图中有没有苹果的二元分类。

 
 


 
 

放到一起,前十张是苹果,后十张不是苹果。(对应到机器学习里面的supervised learning,告诉x,y)

 
 

第一个学生觉得:苹果是圆形的,不是苹果的很多不是圆形。

根据是不是圆形分类,有些是对的,有些是错的(蓝色的就是错的部分)。

 
 


 
 

为了让学生更认识到这种分类方式的缺陷,老师就把已经作对了的图片缩小,没做对的放大,突出错误的地方。

 
 

然后再问学生还有没有其他的规则来分类?

 
 

第二个学生觉得:苹果是红色的,不是苹果很多都不是红色的。

根据颜色分类,有些是对的,有些是错的。(蓝色标出了错误的)

 
 

同样老师标出了错误的,让后放大缩小来突出错误的。

 
 


 
 

然后再问怎样的才是苹果?

 
 

第三个学生说苹果也可能是绿色的,也是有对有错。

然后老师同样的去放大缩小,然后再以此类推。

 
 


 
 

经过这样的反复,最后会得到的分类结果一般来说总比第一个学生说的单一的分类方法效果好。

 
 


 
 

学生就是小gt,就是上图的水平垂直线;整个班级就是大G,就是把小g融合起来,就是上面弯弯曲曲的黑色边界,很顺利的分开了圈圈叉叉;老师的作用是每一次都强调一下犯错误的地方。

 
 

这就是今天讲的演算法的基本思路。

 
 


 
 

练习

 
 


 
 

我们先从Bagging开始讲起:其核心就是bootstraping抽样动作。如果我们假设得到上面所示的一笔资料四个数据,那接下来做的就是在这个数据的基础上让Ein最小。那么从原始的数据库来看,资料可以标示为资料+U(表示当前这个取出的新的data包含这个数据的个数)。这时候Ein如何方便的标识:算一笔资料的错误率,然后乘上系数U,如上图绿色框所示。

 
 

所以Bagging做的事可以看作是透过bootstrap的方式产生一组U,然后去最小化Ein^u。

 
 


 
 

上面就是一种 Weighted Base Algorithm,就是演算法带有权重参数,可以应用在已有的各种算法里面,譬如SVM(上限发生变化),Logistic regression(抽样的时候U是抽中的权重),蓝色的部分就是原来的公式会变化的部分。

 
 


 
 

如果我们的 weighted base algorithm 会根据这些u来决定,那么我们应该怎么去改变u让得到的g越不一样越好?(上一讲提到过,如果g越不一样,aggregation做的结果越好)
 

g_t 是由 u_t 来当weight,g_t+1 由 U_t+1 来得到的。如果g_t在使用u_t+1的时候非常的不好,后续的过程中就会选到和g_t很不一样的g_t+1。比如对于binary classification,我们的期望是让g_t在u_t+1的时候分类结果最差,就是1/2,和丢铜板一样。

 
 


 
 

怎么做,如红色的部分公式,方块代表犯错误的点的u加起来是多少;圆圈代表的是没犯错的点的u加起来是多少,然后我们想做的就是让犯错的u和没犯错的u调到一样。

举个例子见上面的表格,我们先看现在t时刻的犯错的u=1126,没犯错的6211,目前不相等。然后用放大缩小的方式让两边相等,就是左边的乘6211权重,右边乘1126权重,就等了(或者可以乘以相应的对方的比例)。【简单地说就是配上系数使两边相等,这样下一轮得到的数据用这一轮的分类结果表现就应该会非常差】

 
 


 
 

练习

 
 


 
 

上一小结说的就是 optimal re-weighting:为了让g_t 和 g_t+1 很不一样,对犯错误的点放大。按照上面的求解策略,这里可以定义一个方块t参数,对于错误的和正确的点做如上蓝色框所示的参数相乘。

 
 

当错误率必定是大于1/2的时候,方块t一定大于1,也就是说错误的一定是放大,正确的一定会是缩小操作。(对应到了分苹果的例子的老师的操作)

 
 

这个就是adaboost里面得到不一样的g的方法的理论依据。

 
 


 
 

至此就有了一个初步的演算法的长相:

  1. 参数化原来的bootstrap操作,则可以看作是我们在每一轮里面得到g都是透过u得来的,u就是每个example的权重。
  2. 在每一轮的时候,透过方块t来更新u,目的是让现在的g在下一轮的分类中变的很烂,选出的g就会很不一样。
  3. 透过这些不一样的g来合成大G。

 
 

但是还存在一些问题要解决:

  1. 一开始的u是多少,就是1/N,每个点都一样,让一开始的结果和Ein最小。
  2. 合成G的时候怎么弄,g1对Ein是最好的,g2对Ein就很差了,也就是说各个的权重不一样,不要uniform。

 
 

下面要讲的算法就是在产生g的过程中顺便决定了怎么样把这些g合起来(aggregate linearily on the fly)。

 
 


 
 

算法:

一开始u = 1/N;然后对于每一步有三件事情做,

  1. 生成由u表示的dataset来得到g;
  2. 由u的当前结果来更新u为下一轮做准备;
  3. 计算合成的时候的参数alpha;

最后合成的时候直接每个g乘以自己对应的alpha得到G

 
 

我们希望每个g都很好,很好的概念是方块t应该要很大,所以alpha可以看作是方块出来的某一个单调函数的结果,方块越大,alpha越大。

Alpha = ln(方块t),这是设计这个演算法的人做的选择。物理意义会是 1/2的错误率的时候权重为0,错误率为0的时候权重为无穷大,还是很合理的。

 
 

Adaptive Boosting 包含三个元素:

  1. 通过产生的数据集得到的g(Student)
  2. 用方块t对资料放缩重要性(teacher)
  3. 由g合成成G(Class)

 
 


 
 

Adaptive Boosting (Adaboost) Algorithm 算法:

一开始u = 1/N表示所有的点重要性都一样;然后对于每一步有三件事情做,

  1. 得到一个g;
  2. 把错误的乘以方块t,正确的乘以方块t;
  3. 决定alpha;

最后合成的时候直接每个g乘以自己对应的alpha得到G

 
 


 
 

Adaboost的理论特性,我们来看看把VC bound 用在这里的话会得到什么样的保证。

 
 

Eout(G) <= Ein(G)(已经看过的资料上的表现) + 模型复杂度付出的代价(绿色部分,Dvc(h)表示的是g付出的代价,还要合上T,蓝色部分是标准的Dvc告诉我们的事)

 
 

这个演算法得很好的性质:我们可以在相对很短的时间内把第一项(红色部分)做的很小,大概只要花log(n)轮就能做到Ein(G)为0,也就会把第二项做到很小。

 
 

boosting的意思是:我们的任意g只要比乱猜好一点,那么我们就可以让整个演算法越变越强,强到Ein是0,Eout也是很小。

 
 


 
 

练习

 
 


 
 

上面讲到我们弱弱的演算法g需要比乱猜好一点,什么样的演算法可以做到这件事情呢?

 
 

回头看ML foundations作业里面有一个特殊的模型 decision stump,如上所示公式。

包含三个参数:特征是什么,你要切在那里,正方向是哪面;通过搜寻有限多的组合得到最好的decision stump。这是少数真的能把Ein做到最好的hypothesis,对于weighted Ein也可以搜寻所有的组合想办法做到最好。

物理意义就是二维平面上支持切垂直和水平刀。复杂度是 资料的数量乘以feature的数量。

 
 

Decision stump 单独用能力就是太弱了,因为只能切垂直水平刀,那么我们来配合使用adaboost。

 
 


 
 

资料

 
 


 
 

切一刀,放大的三个圈圈就是犯错误的,没犯错误的缩小。

 
 


 
 

再切,以此类推

 
 


 
 

已经得到了非线性边界

 
 


 
 


 
 


 
 

切完了

 
 


 
 

复杂的例子

 
 


 
 

Adaboost + decision stump 实际上确实也蛮好用的,用于实时人脸辨识。

 
 


 
 

练习

 
 


 
 

总结:

介绍了 Adaboost 演算法,一开始先给大家一个小学生课堂的例子来告诉大家这个演算法想像上是长什么样子的。这算法的关键是每一轮的时候透过重新的给每一个example不一样的权重,提高错误的权重,降低正确的权重来得到不一样的g,最后再把g整合成G。最后给了一个adaboost配合decision stump以后的实例,可以工作的很好。

 
 

下一讲:

Bagging 是 uniform aggregation;Adaboost 是 linear aggregation;下一讲给大家介绍 conditional aggregation 的方法。