ANKIT CHOUDHARY:蒙特卡洛树搜索:改变DeepMind、计算机围棋游戏与世界的AlphaGo背后的算法

原文: https://www.analyticsvidhya.com/blog/2019/01/monte-carlo-tree-search-introduction-algorithm-deepmind-alphago/

故事的结局大家已然知晓,在2016年3月9日到15日的那场惊天地、泣鬼神的大战中,AlphaGo赢得了五盘制中的四局,打败了世界围棋冠军李世石,拿走了100万美元的奖金。以4-1击倒李世石的AlphaGo,由谷歌子公司DeepMind开发,他们的衍生产品如AlphaGoZero,带动了人工智能游戏领域里程碑式的发展。

本文将介绍AlphaGo背后的核心算法——蒙特卡洛算法(Monte Carlo Tree Search (MCTS)),该算法通过观察当前状态,计算得到可观的落子方案。为了找到AlphaGo真正起源与全部秘密所在,我们将首先回顾人工智能游戏的历史,概要介绍AlphaGo的组件,厘清游戏树概念,浏览下各种树算法,最后会进入本文重点——“蒙特卡洛树搜索”。

内容

1. 人工智能游戏——一个总结

2. AlphaGo的组件

3. 关于“游戏树”的概念

4. 树搜索算法

1)无知搜索

2)最佳优先搜索

3)“零和博弈”

5. 蒙特卡洛树搜索

1)树遍历与结点展开

a. 置信度上界(UCB)

b. 推演

2)一个完整案例


AI游戏,一个历史性的回顾

人工智能是一个广阔而复杂的领域,但在人工智能正式成为公认的某个能落地工业应用的学科之前,计算机科学的早期先驱者编写了游戏程序来测试计算机是否能够解决人类智力水平的任务。

为了让您对人工智能游戏创始至今的历程有个感性认识,我们来看下它的一些重要的历史发展吧:

1. A.S.格拉斯在1952年成功地开发了一款游戏的第一个软件。游戏是啥?石头-剪刀-布(Tic-Tac-Toe)。这是他在剑桥大学博士论文的一部分。

2. 几年后,亚瑟.塞缪尔(Arthur Samuel)是第一个使用强化训练的人,他学会了通过对抗自己来玩西洋跳棋游戏。

3. 1992年,杰拉尔德·特索罗(Gerald Tesauro)设计了一个名为TD-Gammon的现在很受欢迎的项目,并让机器玩出了世界级的水平。

4. 数十年来,国际象棋一直被视为“人工智能的终极挑战”。IBM的“深蓝”是第一个展示超人国际象棋能力的软件。1997年,这一系统因为击败了国际象棋的在位大师加里·卡斯帕罗夫而闻名于世。

5. 2016年,人类见证了最受欢迎的棋盘游戏AI里程碑之一。李世石,一个九段的职业围棋棋手,输掉了一场与Google DeepMind的AlphaGo机器的五局比赛,AlphaGo使用了深度强化学习方法。

6. 最近在电子游戏AI中值得注意的里程碑包括Google DeepMind开发的算法,用于在经典的Atari 2600视频游戏控制台上玩游戏,达到了超人类的技能水平。

7. 去年,OpenAI推出了OpenAI-5系列机器,它可以打复杂的“星际争霸”比赛。

这只是浮光掠影!还有很多其他例子表明人工智能程序超出了预期。身处其中,我们应该对今天的处境有一个合理的认识。
AlphaGo的组件

蒙特卡洛树搜索:MCTS,AlphaGo通过它找寻下一步落子方案。 残差卷积神经网络:ResNet,AlphaGo以它确定棋盘上的视觉感知状况。

强化学习:训练AlphaGo在当前最优情况下进行自博弈。 在这个博客中,我们将只关注蒙特卡洛树搜索的工作。这将帮助AlphaGo和AlphaGoZero在有限的时间内聪明地探索和达到有趣/良好的状态,从而使得AI达到人类水平的性能。它的应用范围超越了游戏。

MCTS理论上可以应用于任何可以用{状态、动作}对和模拟来预测结果的领域。不要担心,如果这听起来太复杂,我们将在本文中详细分析所有这些概念。


游戏树的概念

游戏树是很著名的数据结构,可以用它来表示游戏。这个概念其实很简单。游戏树的每个节点表示游戏中的特定状态。在执行移动时,一个节点过渡到其子节点。它的术语与决策树非常相似,其中终端节点被称为叶节点。

树搜索算法

我们设计这些算法的主要目的是寻找最佳的路径,以赢得比赛。换句话说,寻找一种遍历树的方法,找到获得胜利的最佳节点。大多数人工智能问题都可以归结为搜索问题,通过找到最优的方案、路径、模型或函数来解决。树搜索算法就是要构建搜索树:-根节点代表了搜索开始的状态-边表示采取的行动-节点代表了采取的状态树会有不同的分支,因为在给定的状态下,可以采取不同的动作。树搜索算法取决于探索的分支和顺序。

无知树搜索

无知树搜索算法,顾名思义,搜索一个状态空间,而不需要任何关于目标的进一步信息。这些被认为是基本的计算机科学算法,而不是人工智能的一部分。属于这种搜索类型的两个基本算法是深度优先搜索(DFS)和广度优先搜索(BFS)。

最佳优先搜索

最佳优先搜索方法通过扩展根据特定规则选择的最有希望的节点来探索一个图。这种搜索的定义特征是,与DFS或BFS不同,前者盲目地检查/扩展一个单元而不知道它的任何信息,最佳优先搜索方法使用一个评估函数(有时称为“启发式”)来确定哪个节点最有希望,然后检查该节点。

例如,A*算法保留一个“开放”节点的列表,该列表位于探索节点的旁边。请注意,此时,尚未对这些开放的节点进行探索。对于每个开放节点,对其与目标的距离进行估计。在最低成本的基础上,选择新的节点进行探索,代价是从起始节点到目标的距离加上对目标距离的估计。

零和博弈

对于单人游戏,可以使用简单的不知情或知情的搜索算法来找到到达最优博弈状态的路径。

对于有另一个玩家需要负责的两人对抗性游戏,我们应该做什么呢?因为,双方的行动是相互依赖的。

对于这些游戏,我们依靠对抗性搜索。这包括两个(或更多)敌对玩家的行动。基本的对抗性搜索算法称为Minimax。

该算法已经成功地应用于经典的全信息两人棋盘游戏,如跳棋和国际象棋。事实上,它是专门为建立国际象棋程序而发明的。

Minimax算法在循环中迭代,会在玩家1和玩家2之间交替进行,就像象棋中的白棋和黑棋玩家一样。这些叫做Min Player和Max Player。为每个玩家探索所有可能的移动。对于每个产生的状态,其他玩家的所有可能的动作也会被探索。

这种情况一直持续到所有可能的移动组合都被尝试,直到游戏结束(胜利、失败或平局)。整个游戏树是通过这个过程生成的,从根节点一直到叶子:

每个节点都会被探索到以确定最优的落子或移动步数。

蒙特卡洛树搜索

石头-剪刀-布、跳棋和国际象棋这样的游戏可以用极小极大算法来解决。然而,当每个状态都有大量的潜在行动要采取时,事情会变得很棘手。这是因为Minimax探索了所有可用的节点。很难在有限的时间内解决一个类似围棋这样的复杂游戏。围棋的分支因子约为300,也就是说,每个状态都有大约300个动作,而国际象棋通常只有30个动作可供选择。此外,围棋的位置性质是围绕对手的,因此很难正确估计给定棋盘状态的价值。

还有其他几种规则复杂的游戏,Minimax是无法解决的。比如,战舰扑克,它的信息不完善且状态不确定,再比如Backgammon和“大富翁”。发明于2007年的蒙特卡洛树搜索,提供了一个可能的解决方案。基本的MCTS算法是简单的:根据模拟游戏的结果,建立一个逐点的搜索树。该过程可分为以下步骤:

a.选择

选择好的子节点,从根节点R开始,这表示导致更好的总体结果(胜利)的状态。

b. 扩展

如果L不是终端节点(即没有结束游戏),则创建一个或多个子节点并选择一个。

c.仿真(展示)

从C运行一个模拟的播放,得到结果。

d.推演

根据仿真结果更新当前序列。
树遍历、节点扩展

在深入研究和理解树遍历和节点扩展之前,让我们熟悉一些术语。

UCB:置信度上界

  • Vi是该节点下所有节点的平均奖励/值。
  • N是父节点被访问到的次数
  • ni是子节点i被访问到的次数

推演

我们所说的推演是什么意思?在我们到达叶节点之前,我们在每个步骤随机选择一个动作,并模拟这个动作,以便在游戏结束时获得平均奖励。

Loop Forever:

if Si is a terminal state:

return Value(Si)

Ai = random(available_actions(Si))

Si = Simulate(Si, Ai)

This loop will run forever until you reach a terminal state.

这是蒙特卡洛树搜索的流程图:

树遍历与节点扩展

从S0开始,这是初始状态。如果当前节点不是叶节点,则计算UCB 1的值,并选择使UCB值最大化的节点。我们一直这样做,直到我们到达叶节点。

接下来,我们会询问这个叶节点被采样了多少次。如果它以前从未被采样过,我们只是做一个展示推演(而不是扩展)。但是,如果它以前已经被采样过,那么我们会为每个可用的操作(我们在这里称之为扩展)向树中添加一个新的节点(状态)。

这样,你就创建了一个新的节点,然后从头推演(rollout)。

一个完整的实例

让我们对算法做一个完整的演练,真正地吸收这个概念,并以一种清晰的方式理解它。 第一次迭代:

  • 我们从初始状态S0开始。在这里,我们有动作a1和a2,这导致了状态s1和s2的总得分t和访问次数N,但是我们如何在这两个子节点之间进行选择呢?
  • 这是我们计算两个子节点的UCB值的地方,并取任何节点最大化该值的值。由于尚未访问任何节点,因此第二个项对两个节点都是无限的。因此,我们将采取第一个节点。
  • 我们现在在一个叶节点上,我们需要检查我们是否访问过它。结果是,我们没有。在这个例子中,基于算法,我们一直到终端状态。假设这个推出的值是20。
  • 从S1到现在是第四阶段,或者反向传播阶段。叶节点(20)的值一直与根节点成反比。现在,t=20和n=1,对于节点s1和s0,执行“反向传播”算法。
  • 这是第一次迭代的结束。

MCTS算法会执行一定迭代,直到游戏结束,需要直到哪一步会取得最优回报。第二次迭代:

  • 我们返回到初始状态,并询问接下来要访问哪个子节点。我们再一次计算出UCB值,对于S1=20,对于S2为无穷大,为2 0 2*sqrt(ln(1)/1)。由于s2具有较高的值,所以我们将选择在s2处执行节点展示。
  • 在S2处进行推演,以得到与根节点相反的值10。根节点的值现在是30。

第三次迭代:

  • 在下图中,S1有一个较高的UCB1值,因此应该在这里展开。
  • 在s1,我们处于与初始状态完全相同的位置,对于两个节点来说,ucb 1值都是无穷大的。我们从s3开始一个展示,最后在叶节点上得到一个0的值。

第四次迭代:

  • 我们再次必须在S1和S2之间进行选择。S1的UCB值为11.48,S2为12.10。
  • 我们将在S2执行扩展步骤,因为这是我们的新的当前节点。在扩展时,创建了两个新节点-S5和S6。因为这些是两个新的状态,所以在叶节点之前进行一次展示,以得到值和进行反向传播。

这就是该算法的要点。只要需要(或在计算上可能),我们可以执行更多的迭代。基本思想是,随着迭代次数不断增加,每个节点处的值的估计变得更加精确。


尾声

Deepmind’s AlphaGo和AlphaGo Zero比文章所列举的,要复杂的多,然而,蒙特卡洛树搜索确实是其核心所在,这里列举了其C++和Python源码:

Implementation in Python

Implementation in C++

Borel–Cantelli引理及其证明

[公式]

 为概率空间内的事件序列。

如果事件的概率和是有限的:

[公式]

那么,当序列系数n趋向于无穷大的时候,概率为0:

[公式]

这里,“lim sup”表示事件序列的极限上界,每个事件都是一组结果。也就是说,L  是在无限事件序列(En)内无限多次发生的结果集。明确地,

证明:

[公式]

 是概率空间的事件:

如上的事件序列非递增:

我们由之前的定义得到:

根据次可加性:

原先的假设:

级数:

具有收敛性,则:

通用测度空间的形式:

[公式]

为集合

[公式]

的测度,

[公式]

算子

[公式]
[公式]

[公式]

 中定义的序列,如果:

则:

逆命题:

一个相关的结果,有时称为第二Borel-Cantelli引理,是第一Borel-Cantelli引理的部分逆引理.引理指出:如果事件  

En

是独立的,且其概率之和发散到无穷大,那么无限多的事件发生的概率是1。

条件1:

条件2:

事件序列相互之间互相独立。

推论:

逆命题的证明:

假设

且相互之间的事件彼此独立,  

n趋向无穷大,事件不发生概率趋向0:

事件互相独立,所以各种事件取交集概率趋向0:

命题得证。

取log:

[公式]

[公式]

满足假设:

引理推论:

另一个相关结果是Borel-Canelli引理论坛。在意义上它是引理的一个对应,即它通过完全不同的假设来代替独立假设给出了limsup为1的充分必要条件,即 {An}对于足够大的索引是单调增加的。

这一简单的结果在诸如随机过程中涉及命中概率的问题中是有用的,其本质是选择序列  。

[公式]

Ray Zhang:对Sutton和Barton《强化学习导论》第六章《时序差分学习》的读书笔记

原文地址: https://oneraynyday.github.io/ml/2018/09/30/Reinforcement-Learning-TD/

之前,“机器之心”翻译过他对蒙特卡洛方法做的笔记:

https://zhuanlan.zhihu.com/p/37926601

  • 回顾
  • 蒙特卡洛方法
  • 时序差分预测
  • 时序差分学习与动态规划的相似性
  • 时序差分学习与蒙特卡洛方法的相似性
  • TD(0)的优化特性
  • 在轨策略(on-policy)方法:Sarsa算法
  • 离轨策略(off-policy)方法:Q-学习算法
  • 案例:悬崖行走
  • Sarsa模型
  • Q-学习模型
  • 悬崖行走的地图
  • 学习曲线

时序差分学习是强化学习里最中心的概念之一。它是之前讨论的蒙特卡洛方法与动态规划的结合体。在蒙特卡洛方法中,我们有一个在给定策略π获取期望奖励V的更新法则。通常,我们会对每一幕(episode)进行仿真并得到总的奖励,然后将动作序列里每个动作对应到奖赏的值。回想下我们在蒙特卡洛仿真里的不同方法——“每次访问”与“首次访问”。我们有状态序列 Sj=(s0,s1,…)和动作序列Aj=(a0,a1,…),每一幕(episode)索引记为 j,首次蒙特卡洛方法执行如下的算法:

任意奖励

可以看作经过时间t在episode为i时候的折扣奖励。换句话说,如果一个状态在整个一集中发生一次、两次或五十次,我们只计算第一次发生的状态。以及所有奖励值的平均值得到

对每次蒙特卡洛方法,我们有:

其中#s是我们在所有剧集中看到状态的总次数。换句话说,如果一个状态不止一次发生,我们将把这些发生加到我们的近似值中,并对所有要得到的奖励值取平均得到


在许多情况下,V(S)是平稳的,两种方法(首次访问和每次访问)都将收敛到最优解。然而,在非平稳环境中,我们不希望我们的“更新幅度”接近0。下面是一个适用于非平稳情况下的每次访问蒙特卡洛方法(比如0)的法则:

常数α>0。时序差分学习在上式中,我们使用变量Gt作为时间t之后的幕(episode)的剩余奖励,它可能是由折扣系数γ所决定的。它只有在一幕结束的时候能得知。对于时序差分学习来说,这一切不再需要了。时序差分学习方法是如何做到这一点的?他们只需要向前看一步,因为他们的近似是稍微不精确和较少的样本基础。他们没有使用Gt,而是使用:

回想求Gt的式子:

然后,我们对V(St)求期望:

可以“逼近”剩下的轨迹:

是的,它不那么精确,但作为回报,我们可以在中间幕的episode进行学习。得出的V(St)在eq(0)模拟中的更新方程是:

在这种情况下,由于我们只向前看一步,所以称为TD(0)。下面是一些伪代码逻辑:

pi = init_pi()
V = init_V()
for i in range(NUM_ITER):
    s = init_state()
    episode = init_episode(s)
    while episode:
        prev_s = s
        action = get_action(pi, V)
        reward, s = episode.run(action)
        V(prev_s) += alpha * (reward + gamma * V(s) - V(prev_s))

TD(0)被认为是一种自助(bootstrap)方法,因为它使用以前的近似,而不是完全使用整个轨迹的回报。

时序差分学习与动态规划的相似性

回顾一下,我们使用Bellman方程操作符来解决强化学习问题的动态规划方法。这允许对V(S)进行有效的增量计算,我们先前证明了:

这样,我们就可以有效地得到越来越多的v的精确逼近。类似的性质,我们在上面方程中的V(St)的逼近也是迭代的,并且由于V(St)作为一个函数是未知的,所以我们从先前的估计中进行自助抽样(bootstrap)。

时序差分学习与蒙特卡洛方法的相似性

回想一下,蒙特卡洛方法要求我们估计期望值,因为我们采集了一些episode里的样本,并试图从对每一个动作中近似中求出潜在的期望值。这样,时序差分学习就像每次访问蒙特卡洛方法,因为它的V(St)近似于Gt的期望值。由于不知道期望,时序差分学习和蒙特卡洛方法都通过抽样近似V(St)。然而,蒙特卡洛方法并没有尝试在其收敛过程中使用以前的V估计,而是采用完整的样本轨迹进行估计。

TD(0)优化特性:人们可能期望TD(0)收敛到与蒙特卡洛方法相同的值。然而,事实并非如此。Sutton列举的病理例子非常清楚地解释了这一点:

在这个案例里,我们有6个episode里B的奖励为1,有2个episode奖励为0,最后V(B)=34。对于A,我们可以提出两个“合理”的建议:1. 如果A事件发生,得到的累积奖励为G。因此,V(A)=0。2. 如果A事件发生,下一个状态始终为B。因此,有:

由于唯一的下一个状态是B,而我们现在的奖励是从我们所拥有的单个样本中得到的,结果应该是0+γV(B)=3γ/4≠0。从马尔可夫的假设来看,这是有意义的,因为St⊥Rt+2是相互正交的,所以A发生在B之前的事实不应该使B产生零奖励。从某种意义上说,蒙特卡洛方法最小化了值函数近似的均方误差,时序差分学习算法则收敛于确定的等效估计上。确定等效估计是在假定过程为马尔科夫决策过程的前提下,对值函数做最大似然估计。

在轨策略算法:SARSA

在在轨策略里,我们不学习v(s),我们学习动作价值函数 q(s,a)。 这个式子比较直白:

求解v(s)的做法:

我们之所以称这个算法为sarsa,是因为它是一个经典的状态-动作-奖励-状态-动作强化学习算法,我们估计了一些π的Qπ.此π是根据当前状态输出动作概率的策略。 通常来说,在轨策略学习算法可能无法充分探索搜索空间,导致一个次优答案,或者永远停留在其当前策略中而无法终止。因此,我们通常使用ϵ-贪婪来寻找策略π,以一个较小的概率ϵ选择所有其他操作。

轨策略算法:Q-学习

时序差分学习算法的离轨策略形式叫做Q-学习,他的更新法则为:

之前,我们用:

来逼近

是用ϵ-贪婪算法求解的。现在,为了获得真实的最优值,需要得到:

ϵ-贪婪算法的选择方法就是离轨时序差分学习,而在轨策略利用argmax逼近真实的Q。悬崖行走我们可以再去看一下“悬崖行走”的例子,之前我们是在gym用蒙特卡洛方法去计算的。就像之前看到的,图上的收敛路径是这样的:

这是一种在轨策略的蒙特卡洛方法。路径如此保守、而演员一直移动到边缘的原因是由于演员有ε的概率向一个随机的方向移动,这会让他掉下悬崖摔死。即使ε接近0,策略也不是最优的,而只是安全的。现在,我在同一个蒙特卡洛方法上添加了TD功能,并重构了大部分核心功能。我们直接将上面的更新规则转换为UPDATE_Q()函数,然后传入元组(状态、动作、奖励、状态、动作),而不是一集,即[(状态,动作,奖励),…]

SARSA模型

SARSA模型的更新法则:

class FiniteSarsaModel(FiniteModel):
    def __init__(self, state_space, action_space, gamma=1.0, epsilon=0.1, alpha=0.01):
        """SarsaModel takes in state_space and action_space (finite)
        Arguments
        ---------

        state_space: int OR list[observation], where observation is any hashable type from env's obs.
        action_space: int OR list[action], where action is any hashable type from env's actions.
        gamma: float, discounting factor.
        epsilon: float, epsilon-greedy parameter.

        If the parameter is an int, then we generate a list, and otherwise we generate a dictionary.
        >>> m = FiniteSarsaModel(2,3,epsilon=0)
        >>> m.Q
        [[0, 0, 0], [0, 0, 0]]
        >>> m.Q[0][1] = 1
        >>> m.Q
        [[0, 1, 0], [0, 0, 0]]
        >>> m.pi(1, 0)
        1
        >>> m.pi(1, 1)
        0
        """
        super(FiniteSarsaModel, self).__init__(state_space, action_space, gamma, epsilon)
        self.alpha = alpha


    def update_Q(self, sarsa):
        """Performs a TD(0) action-value update using a single step.
        Arguments
        ---------

        sarsa: (state, action, reward, state, action), an event in an episode.
        """
        # Generate returns, return ratio
        p_state, p_action, reward, n_state, n_action = sarsa
        q = self.Q[p_state][p_action]
        self.Q[p_state][p_action] = q + self.alpha * \
            (reward + self.gamma * self.Q[n_state][n_action] - q)


    def score(self, env, policy, n_samples=1000):
        """Evaluates a specific policy with regards to the env.
        Arguments
        ---------

        env: an openai gym env, or anything that follows the api.
        policy: a function, could be self.pi, self.b, etc.
        """
        rewards = []
        for _ in range(n_samples):
            observation = env.reset()
            cum_rewards = 0
            while True:
                action = self.choose_action(policy, observation)
                observation, reward, done, _ = env.step(action)
                cum_rewards += reward
                if done:
                    rewards.append(cum_rewards)
                    break
        return np.mean(rewards)


Q学习模型

Q学习模型更新法则:

Python代码:

class FiniteQLearningModel(FiniteModel):
    def __init__(self, state_space, action_space, gamma=1.0, epsilon=0.1, alpha=0.01):
        """FiniteQLearningModel takes in state_space and action_space (finite)
        Arguments
        ---------

        state_space: int OR list[observation], where observation is any hashable type from env's obs.
        action_space: int OR list[action], where action is any hashable type from env's actions.
        gamma: float, discounting factor.
        epsilon: float, epsilon-greedy parameter.

        If the parameter is an int, then we generate a list, and otherwise we generate a dictionary.
        >>> m = FiniteQLearningModel(2,3,epsilon=0)
        >>> m.Q
        [[0, 0, 0], [0, 0, 0]]
        >>> m.Q[0][1] = 1
        >>> m.Q
        [[0, 1, 0], [0, 0, 0]]
        >>> m.pi(1, 0)
        1
        >>> m.pi(1, 1)
        0
        """
        super(FiniteQLearningModel, self).__init__(state_space, action_space, gamma, epsilon)
        self.alpha = alpha


    def update_Q(self, sars):
        """Performs a TD(0) action-value update using a single step.
        Arguments
        ---------

        sars: (state, action, reward, state, action) or (state, action, reward, state),
            an event in an episode.

        NOTE: For Q-Learning, we don't actually use the next action, since we argmax.
        """
        # Generate returns, return ratio
        if len(sars) > 4:
            sars = sars[:4]

        p_state, p_action, reward, n_state = sars
        q = self.Q[p_state][p_action]
        max_q = max(self.Q[n_state].values()) if isinstance(self.Q[n_state], dict) else max(self.Q[n_state])
        self.Q[p_state][p_action] = q + self.alpha * \
            (reward + self.gamma * max_q - q)


    def score(self, env, policy, n_samples=1000):
        """Evaluates a specific policy with regards to the env.
        Arguments
        ---------

        env: an openai gym env, or anything that follows the api.
        policy: a function, could be self.pi, self.b, etc.
        """
        rewards = []
        for _ in range(n_samples):
            observation = env.reset()
            cum_rewards = 0
            while True:
                action = self.choose_action(policy, observation)
                observation, reward, done, _ = env.step(action)
                cum_rewards += reward
                if done:
                    rewards.append(cum_rewards)
                    break
        return np.mean(rewards)


if __name__ == "__main__":
    import doctest
    doctest.testmod()

SARSA方法得到的悬崖地图

正如我们所看到的,它类似于蒙特卡洛方法的地图。这个动作是保守的,因为它不假定过程具有任何马尔可夫特性。蒙特卡洛方法的过程是积极意识到环境中的随机性,并试图移动到最安全的角落,然后再向右,最终走向终点。

Q学习的地图

这是一个与SARSA方法和蒙特卡洛方法非常不同的地图。Q-学习基于潜在的马尔可夫假设,因而忽略了选择其行动时的随机性,这也是它选择最优路径的原因(它理解马尔可夫假设,并因此选择了贪婪的行为,在强马尔可夫的MDP下,这是最优的)。离轨策略的方法允许Q学习有一个最优的策略,而它的ϵ贪婪的模拟允许它探索。笔者(Ray Zhang)认为Q学习更有优势。

学习曲线

我们同时运行这三种模式,并记录随着幕数的增加而增加的总回报。*_interp是日志奖励的移动平均值。看来,SARSA虽然产生了与蒙特卡洛方法大致相同的解决方案(回想起来它并不准确),但收敛到更高的回报的速度要快得多。这是因为它的价值功能能够按步骤而不是每集更新。这种引导方法允许模型比蒙特卡洛方法学习得快得多。

我们可以观察到的另一个现象是,Q学习的平均回报是不好的。这是因为Q-学习试图采取最优的行动,但会被搅乱,由于它用来进行探索的贪婪策略的随机性,它会以ϵ的概率从悬崖上掉下来。

在上面的图表中观察到的另一个有趣的现象是,蒙特卡洛方法实际上在接近结束时开始降低性能。这个…Ray Zhang没有解释(但Ray Zhang又很想讨论它)!)。

《mixup: BEYOND EMPIRICAL RISK MINIMIZATION》笔记

对论文

对论文 https://arxiv.org/pdf/1710.09412.pdf 所做的笔记

在实际工作中,用到了这个技术,感谢论文作者的Idea,写一个总结性质的回答,引用块来源于对论文和其他英语资料的翻译。

一、关于经验风险最小化和邻近风险最小化

传统的统计学习理论强调一种PAC可学习的框架。

如同论文中所指出的,我们有反映真实世界误差的期望风险:

模型的训练,在于去拟合真实的数据分布,但它只能得到所谓的“经验分布”,mixup论文里写成:

理论上认为,训练过程,既然追求收敛,也就是说,训练误差越小越好,可以看作是追逐一种“经验风险最小化”:

按照Vapnik在《统计学习理论》里得描述(见其英语版教科书第三版对“经验风险最小化原则一致性条件”的描述):

如果期望风险和经验风险都收敛于某个极小值,则学习过程是一致的。

根据霍夫丁不等式(见林轩田《机器学习基石》)

理论上,肯定经验风险越小越好,如果假设空间足够大,算法足够牛掰,那么就可以使得训练过程收敛顺畅,但这会带来一个模型复杂度的增加,在测试情况下,发生过拟合,所以需要在对逼近训练数据的推测精度和最小化学习集的容量之间做个折衷,这就是我们讨论的VC维。

神经网络的VC维是非常大的,需要足够多的训练才可以让模型shatter掉break point。

按照英语维基百科对神经网络VC维的解释:

神经网络由有向无环图G(V,E)描述,其中:

V表征点的集合,每个点都可以看作简单的计算单元。
E是边的集合,有权重。
网络的输入可以由图里的源点表示(没有入度的边)。
网络的输出可以由图里的汇聚表示(没有出度的边)。
每个中间节点通过得到其输入边缘的节点得到输出的加权和,靠边上的权重计算。
每个中间节点输出基于一定输入的单调递增函数,例如更多的sign函数或更多的sigmoid函数。这个函数称为再激活函数。

神经网络的

如果激活函数是任意权重的sign函数,则VC维最多

.

如果激活函数是任意权重的sigmoid函数,则VC维最多

或者

.

如果权重来自一个固定的集合(例如,权重是实数,最多可以用计算机中的32位浮点数来表示),那么,对于这两个激活函数,vc维数最多都是。

所谓的“深度学习”,在没有GPU的年代,因为无法对大量样本进行训练,所以只能望洋兴叹了。有了算力的支持,科学家与工程师们就只恨数据不够,在真实的测试环境中泛化能力出幺蛾子了,这就提出了“数据增强”的任务。

按照这篇论文的介绍,是用Vicinal Risk Minimization(邻域风险最小化)做数据增强。直接翻译了论文里的解释:

在VRM中,需要人类的知识来描述训练数据中每个示例周围的附近或邻域。然后,从训练样本的邻近分布中提取额外的虚拟示例,以扩大训练分布的支持度。例如,在执行图像分类时,通常将一幅图像的附近定义为其水平反射、轻微旋转和比例缩放的集合。虽然数据增强会不断提高泛化能力(Simard等人,1998年),但这一过程依赖于数据集,因此需要使用专家知识。此外,数据增强假设附近的示例共享相同的类,而不对不同类的示例之间的邻近关系进行建模

所以能取得论文认为的效果:

在我们的实验中,以下趋势是一致的:随着训练误差的不断增大,对实际数据的训练误差增大,而泛化差距减小。这支持了我们的假设,即含蓄地控制模型的复杂性。然而,我们还没有一个很好的理论来理解这种偏差-方差权衡的“甜蜜点”。例如,在CIFAR-10分类中,即使在alpha趋近无穷大的情况下(即仅对一对实例数进行训练)的情况下,实际数据的训练误差也很小,而在ImageNet分类中,实际数据上的训练误差随着alpha趋近无穷大,基于我们的ImageNet和Google命令在不同模型结构下的实验,我们推测,增加模型容量,但同时alpha保持比较大,对训练误差不会特别敏感,因此mixup是有优势的。

二、数据增强

传统的数据增强一般有两种做法:

1、几何上的反射变换:拉伸、旋转、翻转、裁剪。

2、加入噪声、遮挡、改变颜色通道、光照环境。比如论文《Random Erasing Data Augmentation》,mixup论文作者推荐的《DROPOUT AS DATA AUGMENTATION》,我粗略做了个翻译:用于数据增强的Dropout​turingforchinese.home.blog

mixup generator主要是利用VRM思想对特征和标签同时做线性插值,如同论文中所描述的:

因此,通过引入特征向量的线性插值应导致相关目标的线性插值这一先验知识,混合扩展了训练分布。混搭可以在几行代码中实现,并引入最小的计算开销。
mixup究竟在做什么?它可以理解为数据增强的一种形式,鼓励模型f在训练示例之间表现出线性行为(小范围内?)。研究人员认为,这种线性插值的做法减少了在训练集外样本上不受振荡的可能性。此外,从Occam剃须刀原则角度来看,线性是一种很好的归纳偏置,因为它是最简单的可能行为之一。

传统的无监督学习借鉴了统计学上概率密度估计的一些做法,不知道这里是否假设了,在领域内,概率密度不会发生大的振荡?

的确可以算是一种“大道至简”的数据增强方法,学术上有创新性,工程上又实用。

三、一个疑问:为什么是Beta分布不是Dirichlet分布

按照论文的说法,一个generic的vicinal分布是这样的:

其中lamda满足Beta分布(伯努利分布乘上[0,1]之间的均匀分布得到之),这个式子比较好实现的,比如这里的keras的mixup代码就是随机取索引之后利用Beta分布混合得到新的数据及其对应标签:

.https://github.com/yu4u/mixup-generator/blob/master/mixup_generator.py​github.com

论文作者说用Dirichlet分布效果不好,因为会增加计算时间。

四、其他一些小点

  1. 工程实现上,要用同样的miniti-batch加载并mixup,这样,可以减少I/O。
  2. 线性插值不能对相同label做,要对不同label进行混合。
  3. 在ImageNet实验上,alpha取[0.1,0.4]效果比较好。
  4. 可以用在GAN的实验里,本质上是鉴别器的Regularizer,在生成对抗网络求解超参数的过程中,增加了结构的鲁棒性。
  5. 消融实验部分设计很不错,值得仔细读。

知乎链接: 如何评价mixup: BEYOND EMPIRICAL RISK MINIMIZATION? – 若羽的回答 – 知乎 https://www.zhihu.com/question/67472285/answer/854386908

用于数据增强的Dropout

原文: https://arxiv.org/pdf/1506.08700.pdf

Dropout通常被解释为打包压缩大量共享参数的模型。研究人员证明,在网络中使用dropout也可以解释为在没有领域知识的输入空间中的一种数据增强。他们提出了一种将网络中的dropout噪声投影回输入空间的方法,从而生成训练数据的增广版本,并证明了在增广样本上训练确定性网络的结果相似。最后,基于观测结果提出了一种新的dropout噪声方案,在不增加计算量的情况下,改进了dropout结果。
一、导论

噪声通常被视为本质上不受欢迎的。这个词本身就有一个非常负面的含义。因此,在神经科学中,许多早期的数学模型都是以任何手段来分辨噪声,这并不令人惊讶。几十年前,随机共振(Wiesenfeld et al., 1995)在神经科学模型中的应用引发了对随机波动及其在大脑中作用的神经科学的新兴趣。关于神经元噪声的理论正在蓬勃发展,以前的确定性模型通过噪声的加入而得到了改进(Yarom & Hounsgaard, 2011)。 当涉及到发展学习算法时,生物大脑一直是一个很强的灵感。考虑到在学习过程中大脑中发生的大量噪音,人们可能会怀疑这是否有任何有益的影响。最近,机器学习中的许多技术都利用噪声来提高性能,即去噪自动编码器(incent et al., 2008)、dropout(Hinton et al., 2012)和其亲属-drop Connect(Wan et al., 2013)。这些成功的研究表明,神经元噪声在学习过程中起着重要的作用,应该对其进行更深入的研究。 使用dropout可以看作是训练大量具有共享参数的神经网络,并在测试时应用套袋以获得更好的泛化(Baldi & Sadowski, 2013)。二值噪声也可以看作是防止神经元协同适应,从而进一步提高了模型的泛化能力。在这篇论文中,研究人员提出了另一种观点,并提出像dropout这样的噪声方案隐含地包含了一种复杂的数据增强形式。在第三节中,他们提出了一种在确定性网络中复制掉噪声的数据生成方法,并在第五节中证明了该方法没有明显的准确性损失。最后,利用数据增强的思想,研究人员在第四节中提出了一种利用随机噪声水平来改进样本多样性的dropout扩展。这种简单的扩展提高了不同网络结构的分类性能,在MNIST置换不变分类任务上获得了竞争性的结果。
二、对dropout的解释

使用dropout的主要目的是对我们正在训练的神经网络进行正则化。该技术包括随机丢弃神经元的概率p,这些随机修改的网络结构被认为避免了神经元的协同适应,使随后的两个神经元无法单独依赖彼此(Srivastava et al., 2014)。对于dropout最被接受的解释是,在测试时隐含地压缩大量共享参数的神经网络(防止过拟合)。假设h(x) 是di维输入x的线性投影到dh维空间:

(1)

有a(h) 和a˜(h)两种带噪声激活函数,满足伯努利分布 M ∼ B(ph) ,rect(h)表示矩形函数:

(2)

(3)

式(3)表示训练时带Dropout的激活函数,式(2)表示测试时的激活函数。Srivastava et al. (2014)建议调整 a(h) 和 p的比例,达到对单位神经元激活的逼近平均。
三、从数据增强角度考虑问题

在许多先前的工作中,以下的知识已经广为人知,通过使用域特定变换来增加数据有助于学习更好的模型((LeCun et al., 1998; Simard et al., 2003; Krizhevsky et al., 2012; Ciresan et al., 2012))。在此工作中,研究人员在数据增强的上下文中分析Dropout。考虑到分类的任务,给定一组训练样本,目标是学习映射功能,该映射功能将每个输入映射到其相应的输出标签。为了推广,映射功能需要能够正确地映射训练样本,而且能够正确地映射从数据分发中提取的任何其它样本。这意味着它不仅必须映射由训练样本表示的输入空间子区域,而且还必须映射自然分布的所有高概率子区域。学习这种映射功能的一种方式是通过增加训练数据以使得它覆盖自然分布的较大部分。基于域的数据增强有助于人为地增强训练数据覆盖,这使得能够训练更好的映射功能。研究人员假设基于噪声的正则化技术导致在每个隐藏层增加训练数据覆盖的类似效果,并且该工作呈现多个实验观察以支持他们的假设。比如,可以将噪声投影回输入空间。给定a˜(h),有x ∗ ,我们有:

(4)

如同Goodfellow et al. (2014b)提到的对抗样本的例子,x ∗ 可以通过基于随机梯度下降的最小化损失函数 L获得:

(5)

式(5)可以通过堆叠n层神经网络进行泛化。

(6)、(7)

现在我们可以一次计算对应于所有隐藏层激活的反向投影,从而将损失L降到最小。

(8)

论文通过反证法表明,一个不太可能找到单个X,=x(1),=x(2),=···=x(n),这显著地降低了L。在附录第8.1小节中详细说明了证明。幸运的是,通过提供多个输入(x,x(1),x(2),例如。、x(n)n),其中n是隐藏层的数目。由于每个X(i)类型是由第i个隐藏层定义的表示空间中的变换的后投影,所以它建议查看Droppit作为复杂的数据增强过程,该程序在关于不同级别的表示的训练示例周围采样数据。这就告诉人们是否可以确定性地在X(i)上训练网络而不是使用Dropout的问题。答案并不重要,因为1. 使用(x, x(1)∗ , x(2)∗ , . . . , x(n) ∗ )作为输入,dropout并非同时高效地在每层工作的。 局部随机性可以防止共适应,每层只有一个x (i) ∗ 。仅有这些,可能不足以避免共适应。2. 线性投影的梯度将有很大的不同。在退出的情况下,∂h/∂W(I)总是等于它的输入变换,即˜f(i−1)(X),而确定性的训练版本将根据f(i−1)(x(1)∗)更新W(I)。….,f(i−1)(x(N)∗。虽然论文证明了单个x∗最小化8对于大型网络是很难找到的,但第5节中实验表明,对于一个相对较小的两个隐层网络,可以在合理的近似范围内这样做。研究人员进一步证明,通过将噪声投影回输入空间,进行dropout复制,这不会造成严重的精度损失。四、改进增强的集合在处理基于域的变换时,研究人员直观地寻找最丰富的变换集。在计算机视觉中,例如,平移、旋转、缩放、剪切和弹性变换经常被组合。从数据增强的角度来看,这种直觉提出了以下问题:考虑到所使用的噪声方案在输入空间中应用了一些变换,哪一个将产生最丰富的变换集?对于像Dropout这样的噪声范式,有两个重要的影响因素:~m的概率分布和用于编码h(X)的神经网络的特性。修正概率分布是改进变换集合最直接的方法,也是论文研究的重点。然而,神经网络的特征在转换过程中起着关键的作用,论文结尾部分将概述一些可能的途径。在使用Dropout的同时,神经元下降的比例非常接近概率P。它自然地满足二项分布的期望。所引起的变换与M可采取的值不同。尽管如此,它们的大小与神经元下降的比例一样恒定。这意味着,每个变换将在低维空间里把样本移位到相对恒定的距离,但却在高维空间中在随机方向上移位。 改变变换幅度的一个简单方法是用一个随机变量代替p。让ph ∼ U(0, ph) ,而Mhij ∼ B(ρh),其中h定义隐层, i 表示样本,j代表神经元。 对每层神经元使用同样的ρ式很重要的,如果不这样,我们得到分布Mhij ∼ B(ρh/2)。为了补偿测试期间激活水平的变化,通常应用缩放。也可以简单地在训练期间应用逆缩放,将等式3转换为

(9)

随机Dropout的公式,用ρ取代p

(10)

这里不需要做缩放。

图1显示了因Dropout和随机Dropout而下降的神经元比例的密度函数之间的差异。随机Dropout引起的变换明显比常规Dropout引起的变换更多样化。

图1:Dropout神经元比例的密度函数在p周围是非常近的。这导致了由DropOut引起的变换幅度的低变化。另一方面,随机Dropout在pN下具有恒定的密度函数,n是神经元的数目,因为它满足ρ ∼ U(0, p)。因此,它的变换比标准Dropout更好。这在直觉上是合乎需要的,因为变化的平移距离在恒定的大距离上是优选的。
五、实验

1.投影回输入空间的可视化

将投影到输入空间中的噪声可视化,有助于理解Dropout会导致什么样的转换。非监督模型比有监督的全链接神经网络学习更多的一般特征,从而产生更直观的变换。由于这个原因,我们训练了隐藏层上有下拉的自动编码器来生成转换的样本。该自动编码器非常类似于去噪自动编码器,唯一的区别是,伯努利掩码被应用到隐藏的激活,而不是输入。因此,没有噪声显式地应用于输入。对模型进行了300个epoch的训练,最小batch-size为100,p=0.4,MNIST的学习率为0.001,CIFAR-10为0.0001,MNIST为0.7,CIFAR-10为0.5。对于CIFAR-10,我们进行了PCA降维预处理,保留了781个特征。对于MNIST和CIFAR-10,做10次epoch迭代,学习率为100(笔误?)。图5很好地展示了x∗与自然输入空间的距离,可以清楚地看到这些类仍然是可区分的。为了帮助理解每个特性如何影响转换,研究人员为给定的输入分离出五个最活跃的特性,并分别固定它们。对固定的每个特性,使用梯度下降计算x∗。图3显示了为MNIST找到的结果。人们可以认为,噪声降低的特征只是从输入中删除。结果发现,去除这个特征会影响其他神经元的激活。正因为如此,功能在输入中被相当地破坏,使得其他高度依赖于同一子区域的特性仍然具有相同的激活级别。

图2.可视化的MNIST以及CIFAR-10数据集上的噪声样本

图3. 在MNIST中,特征对Dropout引起的转换的影响的可视化。第一列表示来自MNIST数据集的原始样本。第二列表示每个给定原始示例上最活跃的五个特性。最后一列表示通过将噪声反投影到输入空间而产生的噪声样本,同时将所选特性保持为0。我们可以看到,这些特性并不是简单地从输入中删除的,而是以这样一种方式破坏的,即高度依赖于同一子区域的其他特性仍然具有相同的激活级别。

图4. MNIST和CIFAR-10数据集在MLP架构使用不同Dropout方案的错误百分比。第1行:使用Dropout的实验。第二行:使用噪声反投影的实验。第1栏:CIFAR-10;第2栏:MNIST

图5. MNIST和CIFAR-10数据集上随机Dropout产生的噪声样本

2. Dropout和噪声样本的等效性

研究人员在MNIST和CIFA R-10数据集上进行了一系列全连接的前馈神经网络实验,研究了用相应的噪声输入代替Dropout的效果。每个网络由两个隐藏层和校正的线性单元组成,然后是一个Softmax层。一共实验了四种不同的体系结构,每一种在隐藏层中有不同数量的单元:2500-2500,2500-1250,1500-1500和1500-750。MNIST数据集由60000个训练样本和10000个测试样本组成。研究人员将训练集分成50000个样本进行训练,10000个样本进行验证。对每个网络迭代501个epoch,并根据验证误差选择最佳模型。之后,最好的模型被进一步训练在60000个样本的完整训练集上(训练验证分裂),训练150个epoch。最后75个epoch的平均误差百分比拿来进行比较。研究人员还使用上述相同的网络体系结构对CIFAR-10置换不变任务进行了实验。数据集包括50000个训练样本和10000个测试样本。实验采用非白化的PCA降维进行预处理,保留781个特征。然后采用与MNIST实验相同的方法来训练网络和比较性能。在每个epoch,为每个训练样本生成一个x∗。实验证明,对于一个两层隐层网络,可以同时为整个网络找到良好的x-∗近似。因此,我们只训练x和x∗,而不是x,x(1)∗和x(2)∗,因为它提高了速度。为了简单起见,每个epoch训练x,而不训练x*。所有x∗都是在一个epoch开始时用模型的参数值生成的。使用随机梯度下降法发现有噪声的输入X。为第一隐藏层和第二隐藏层的300.0的学习速率完成20个学习步骤。这些实验的结果如图4所示。结果提示,通过将噪声投射回输入并对该生成的数据进行确定性训练,可以复制Dropout的某种机制。在准确性方面没有显著下降,在CIFAR-10的情况下,它甚至比Dropout略胜一筹。这似乎验证了某种假设,即Dropout可以被看作数据增强。

3. 更丰富的噪声范式

研究人员对MNIST和CIFAR-10数据集进行了一系列完全连接的前馈神经网络的实验,以比较Dropout现象。每个网络由两个具有整流线性单元的隐藏层组成,之后是SoftMax层。在论文里,用三种不同的网络体系结构进行了实验,每个网络架构具有不同数量的隐藏层单元:2500-625、2500-1250和2500-2500。对每个网络进行培训,并按照上一节所述的方式对每个网络进行验证。首先,研究人员通过训练具有0.5的固定隐藏噪声水平的网络和从0.0到0.7变化的输入噪声水平来评估辍学率噪声方案,每个实验的增量为0.1。在第二实验中,研究人员将输入噪声水平固定在0.2,并且隐藏噪声水平从0.0变化到0.7,再次以0.1的增量变化。在最后一组实验中,他们使用在输入和隐藏层使用相同噪声电平的随机压降噪声方案。这种情况下的噪声电平是范围[0,x],其中x从0.0到0.8变化,增量为0.1。图6中报告了与所有数据集的所有实验相对应的分类性能。

图6:使用不同损坏方案的MLP架构在MNIST和CIFAR10数据集上训练得到的错误百分比。第1行:CIFAR-10的实验。第2行:MNIST实验。第1列:使用具有不同输入噪声并固定隐藏噪声0.5的Dropout。第2栏:使用不同隐藏噪声并固定输入噪声0.2的Dropout。列-3:使用具有不同噪声范围[0,x]的随机Dropout,用于隐藏和输入层。
六、相关工作

这篇文章发表的时候,还没有人从数据增强的角度讨论Dropout。Gal & Ghahramani (2015)从贝叶斯逼近角度解释过Dropout。Poole et al. (2014) 用了不同的噪声方案,并在自动编码器的不同位置上应用;输入、激活前和激活后。他们取得了比去噪自动编码器实验更好的结果,并且支持在MNIST分类任务中加入高斯噪声,这比基准线上加Dropout性能好。Bachman et al. (2014)强调了对Dropout的bagging解释,并提出了一种名为伪集成学习和相关正则化的泛化方法,这使得训练半监督网络成为可能。13——15年的一些研究工作,受模拟退火的启发,去Schedule噪声,认为这会有助于监督和非监督任务(Geras & Sutton, 2014; Chandra & Sharma, 2014; Rennie et al., 2014)。本文提出了一种替代方案,可以避免调度噪声,这会使模型无法适应缓慢变化的噪声分布,而是使用随机噪声。Geras & Sutton (2014) 在无监督的自动编码器上也使用了类似的方法,这是对输入操作,而非对特征,他们之前认为这方法不太管用。最后,Graham et al. (2015)工作与随机噪声有关,因为它们的子矩阵乘法和随机噪声水平ρ都在诱导单层神经元之间的独立性。他们发现,如果使用足够多不同的子矩阵模式,独立性就不会受到损害。
七、结论

本论文提出并证明了一种把Dropout当作先验知识的数据增强的解释。研究人员描述了一种新的生成样本的方法,即将掉出的噪声投影到输入空间中。实验的结果表明,神经网络可以在这样的含噪样本上进行训练,并且仍然取得了很好的效果。当然,要在较大的网络(比如ImageNet)上进行实验,以确定这一观测是否只是相对较小网络的一种特殊性质。此外,对经过训练的网络进行分析,以确定在深层神经网络上使用每层噪声反向投影时是否仍然避免了共适应。在这份工作中,可能取代Dropout的名单仅仅是随机Dropout,这远远不是详尽无遗的。如第四节所述,模型的特点和应用的噪声方案是修正由噪声引起的数据增强的重要旋钮。使用半监督代价可以通过迫使网络学习更多的一般特征来影响隐式变换。还可以对一个网络进行关于从另一个网络生成的x个∗样本的训练,类似于生成对抗网络(Goodfellow et al., 2014a)

VC理论编译(根据英语维基百科)

https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_theory

Vapnik-Cheronenkis理论(也称为VC理论)是在1960-1990年代由Vladimir Vapnik 和 Alexey Chervonenkis提出的。该理论是一种计算学习理论的形式,试图从统计的角度解释学习过程。VC理论与统计学习理论和实证过程有关。Richard M. Dudley 、 Vladimir Vapnik等人则在实证过程中运用了VC理论。 一、导论按照《统计学习理论的本质》这本书所介绍的,VC理论涵盖了四个部分:

  • 学习过程的一致性理论
  • 根据“经验风险最小化”原则,学习过程一致性所需要的充要条件是什么?
  • 学习过程收敛的非渐进理论
  • 学习过程的速率如何设定?
  • 学习的泛化理论
  • 怎样学习才能更好地完成优化的收敛,并提高泛化性能?
  • 构建学习机的理论
  • 如何设计算法才能控制泛化能力?

VC理论是统计学习理论的一个主要分支。统计学习理论的主要应用之一是为学习算法提供推广条件。从这个观点来看,VC理论与稳定性有关,它是表征推广的一种替代方法。此外,在VC类索引的过程中,VC理论和VC维在经验过程理论中起着重要作用。可以说,这些是VC理论的最重要的应用,并且被用于证明推广。本文将介绍在经验过程和VC理论中广泛使用的几种技术。讨论主要基于这本书《弱收敛和经验过程:应用于统计学的观点》。二、经验过程里的VC理论1. 经验过程的背景我们有随机变量

这些随机变量在可测空间里被定义

有任意测度

定义在可测空间

然后有函数

给定对测度的积分

假设忽略对可测量性问题的讨论,我们有

为可测函数的分类

并且定义:

我们定义经验的测量函数

这里δ代表Dirac测度。经验测度归纳出映射

其中f表示多个函数的平均值

现在假设p是数据的基本真实分布,它是未知的。经验过程理论旨在识别类

考虑以下一些定理

  • 大数定理的一致性

如果有n趋近于无穷大,

则有,

对以下

都成立

  • 中心极限定理的一致性

之前的例子

 可以称之为Glivenko-Cantelli 类,我们有这样的假设

在类

叫做Donsker或p-Donsker。显然,通过应用Slutsky定理,Donsker类在概率上是满足Glivenko-Cantelli定理的。以下声明成立

根据标准LLN,CLT参数在规则性条件下得到,并且经验过程中的困难在于,因为联合声明要适用所有情况

根据推论,我们有集合,

 集合不能台大,其几何意义含义巨大 

测量集合大小的

我们称之为“覆盖数”

表示覆盖某个球的最小半径

以此来覆盖集合

这是一个基本的规范:

覆盖数的对数为熵.下面给出了两个充分条件,在此条件下可以证明, 即

满足Glivenko-Cantelli定理或是Donsker的。一个类

P-Glivenko-Cantelli只有当它是P-可测的,且覆盖F

 满足

下一个条件是著名的Dudley定理的一个版本。如果

是这样一个函数

则 

对任意测度P都是P-Donsker的。

.用下面的L2范数求积分开平方获得:

2.均衡大多数关于如何限制经验过程的争论,依赖于均衡、利用不等式的上界和链式推导。均衡通常是证明的第一步,由于它用于许多关于有界经验损失函数的机器学习证明(包括下一节讨论的VC不等式的证明),因此在这里介绍。我们有经验过程

经验过程咋长期假设达到某种均衡

均衡过程就是某种Rademacher过程,

它是一个满足Hoeffding不等式的子高斯过程。均衡引理 对于非递减的、凸的随机过程 Φ: R → R 以及一个可测函数类,

我们有

均衡的证明与变量无关:

(有时称为幽灵样本),并以这些变量取代LHS的内在期望。在应用Jensen不等式之后,可以在不改变期望的情况下引入不同的符号(因此称为“均衡”)。
3. VC维事实证明,集合

 与熵值,的某些组合性质之间存在着迷人的联系。 覆盖数由Vapnik-Chervonenkis 集合的类(缩写为VC类)决定我们有这样一个集合

以及样本空间的子集合

是一些子集

固定集

如果

 适用于

VC Dimension就是某假设集H能够shatter的最多inputs的个数,即最大完全正确的分类能力。(注意,只要存在一种分布的inputs能够正确分类也满足)。shatter的英文意思是“粉碎”,也就是说对于inputs的所有情况都能列举出来。例如对N个输入,如果能够将2N种情况都列出来,则称该N个输入能够被假设集H shatter。在选择分类集合的时候,VC索引可以看作VC维维数+1。因此

可以看作分类器

能被“Shatter”掉的最小个数。

.Sauer引理:

是VC类从类别

 中间选出的子类别,满足

这是一个n次方的复杂度

谢天谢地,不是指数增长的,确定的VC维划分,对于分类器

应该有尽可能简单明了的结构VC维的界限,我们有函数

 这是子集合的子图

。我们有集合

如果所有的子图来自于同一个VC类,我们称之为VC子图:假设有这样一个指示器函数:

对于离散经验型测度Q(或对任何概率测度q等效)。然后可以证明这是相当显著的,因为,对于:

进一步考虑集合的对称凸缝隙

 是对这样的函数形式

进行定义。那么,

对于凸缝隙是有效的 

:

。我们有这样一个重要的推导:

如此一来,对于熵值的积分是收敛的,而有类

P-Donsker的。最后,我们考虑一个VC子图的例子.任意固定维度的向量空间

有可测函数

VC子图索引小于等于

三、VC不等式在机器学习理论中,我们有特征空间

 标签 

函数

 看作是分类器有分类器的集合

 “粉碎”(shatter)的系数称作“成长函数”。

我们知道如果一个假设空间H有break point k,那么它的成长函数是有界的,它的上界称为Bound function。根据数学归纳法,Bound function也是有界的,且上界为Nk−1。从下面的表格可以看出,N(k−1)比B(N,k)松弛很多。

图片来源:林轩田《机器学习基石》课件给定1:1映射的前提条件, 

 为

挑选出来的子集合。Shatter系数:

.Sauer引理告诉我们有具有多项式复杂度的

,则VC索引会随着样本数量n呈现多项式增长。我们有可观察的数据集:

数据满足概率分布

.定义风险函数

是0/1损失。那么,经验风险为:

对0-1损失的二分类问题,我们有泛化边界:

vc不等式表示,当样本增加时,如果

具有有限的vc维数,则经验0/1风险成为预期0/1风险的一个很好的代理。请注意,这两个不等式的RHS都将收敛到0,条件是

在n中多项式增长。 经验误差趋近与结构误差

根据霍夫丁不等式:

图片来源:林轩田《机器学习基石》课件推导展开:

图片来源:林轩田《机器学习基石》课件表示模型的可学习性在于输入与输出误差要接近,这样假设空间的泛化能力较大。
四、参考文献

从未标记的数据中学习跨模态时序表示

虽然人们可以很容易地识别视频中发生的活动,并预测接下来会发生什么事件,但对机器来说,这要困难得多。然而,理解视频的内容和动态变化,如时间定位,动作检测和自动驾驶汽车导航,对机器来说,日趋重要。为了训练神经网络来执行这样的任务,通用的做法是部署有监督学习模型,其中训练数据是由人们一帧一帧仔细标注视频获得的。这样的注解在规模上是很难获得的。因此,人们对自监督学习(无监督学习)任务很感兴趣,在这种学习中,模型被训练成各种代理任务,而这些任务的监督自然存在于数据本身。在《VideoBERT: A Joint Model for Video and Language Representation Learning (VideoBERT) 》和《Contrastive Bidirectional Transformer for Temporal Representation Learning (CBT)》,研究人员提出了从未标记视频里学习时序表示的方法。这个方法致力于在长时间距离上发现与动作和事件相关的高层语义特征。要做到这一点,研究人员就得致力于挖掘人类语言描述物与事背后的高层机制。 在视频里,对白必须在时序上对齐视觉信号,并被现成的自动语音识别系统(ASR)提取,也因此提供了一种原生的自监督学习路径。 研究人员提出的模型是一种跨模态学习的例子,它在学习时需要利用视频和音频信号信息。

图2.在视频和文本上遮蔽的信令预测(或完形填空)任务上下文中使用VideoBERT模型的说明。底部:将来自同一视频位置的可视和文本(ASR)信令(token)连接起来,以形成视频BERT的输入。一些视觉标记和文本标记被遮蔽。中间:VideoBERT应用转换器架构共同编码双向可视文本上下文。黄色和粉色框分别对应于输入和输出嵌入。顶部:训练目标是恢复遮蔽位置的正确标记。VideoBERT模型探访研究人员在超过100万个有指导性的视频(诸如烹饪、园艺、汽车修理)上训练VideoBERT模型。完成训练之后,人们能看到模型通过学习一系列的任务,可以正确地表述视频内容。比如,文本-视频预测可以用来根据视频生成指令(比如菜谱),或者输出一些表达描述内容的视频片段。不仅如此,视频-视频的预测可以通过初始的视频信令(token)推理出未来的视频内容。

图3.对烹饪视频进行了预训练之后的VideoBERT实验结果定性说明。顶部:给定一些菜谱文本,模型生成一系列可视标记。底部:给出一个可视的信令(token),我们显示了在不同的时间尺度上,由VideoBERT预测的前三个未来的信令。在这种情况下,该模型预测,一碗面粉和可可粉可能被放进烤箱烘焙,并可能成为一个布朗尼或纸杯蛋糕。模型在特征空间中使用最近于训练的训练集中的图像来可视化可视标记。为了验证Video BERT模型是否能真正学到视频与文字之间的关联,研究人员需要在烹饪视频数据集上验证“小样本学习”精度,在预训练阶段,既不需要视频,也不需要标注。为了完成分类,需要将视频标记与模板语句“现在让我向您演示如何遮蔽[Mask]”连接,并提取预测的动词和名词标记。 VideoBERT模型与作为基准的有监督学习模型的前5位测试精度相匹配,表明该模型能够在这种“小样本学习”环境下具有竞争力。用对比双向Transformer进行迁移学习虽然Video BERT在学习如何自动标记和预测视频内容方面表现出了令人印象深刻的效果,但研究人员注意到视频对象使用的视觉标记可能会丢失细粒度的视觉信息,例如较小的对象和细微的运动。为此,他们提出了对比双向变压器(CBT)模型,来消除这个标记化步骤,并通过对下游任务的转移学习,进一步评价了学习表示的质量。CBT运用了一个不同的损失函数,即对比损失函数,以最大限度地利用掩码位置与其他跨模态句子之间的相互信息。研究人员对不同任务(例如,动作分割、动作预期和视频字幕)和各种视频数据集的学习表示进行了评估。CBT在大多数情况下超过了当前最优的方法。同时,研究人员们还观察到:(1)跨模式学习目标对迁移学习性能有重要影响;(2)训练前训练集越大,表达效果越好;(3)CBT模型与平均池化、LSTM等基线方法相比,更好地利用了长时背景。

图4. 在不同时长情况下,CBT、LSTM、平均池化的预测精度比较结论该项工作证明了BERT模型在学习未标记视频的视觉语言和视觉表示方面的强大作用。研究人员发现,Video BERT模型不仅适用于“小样本”动作分类和视频文本生成(比如食谱),而且可以将学习到的时间表示特征较好地传递给各种下游任务,如动作预测。论文的后续工作包括学习低层次的视觉特征和长期的时间表示,这将使得它更好地适应视频背景。此外,研究人员还计划扩大训练前视频的数量,使其更大、更多样化。
参考论文:1. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding2. VideoBERT: A Joint Model for Video and Language Representation Learning3. Contrastive Bidirectional Transformer for Temporal Representation Learning

来源:谷歌AI博客

https://ai.googleblog.com/2019/09/learning-cross-modal-temporal.html

学习可延展不同图像分类任务的

导论
开发神经网络图像分类模型往往离不开重要的结构工程。本文研究了一种直接在感兴趣的数据集上学习模型体系结构的方法。由于这种方法在数据集较大时开销很大,因此我们建议在小型数据集上搜索体系结构构建块,然后将该块转移到更大的数据集中。这项工作的主要贡献是设计了一个新的搜索空间(我们称之为“NASNet搜索空间”),以实现可移植性。在研究人员设计的实验中,NASNet会搜索CIFAR-10数据集上最好的卷积层(或“cell”),然后将该单元应用到ImageNet数据集中,方法是将该单元的更多block叠在一起,每个单元都有各自的参数来设计一个卷积结构,该网络被命名为MNASNet。另外,研究人员还引入了一种称为ScheduledDropPath的新的正则化技术,它大大提高了NASNet模型的泛化能力。在CIFAR-10数据集上,使用NASNet+ScheduledDropPath的方法在精度上达到了2.4%的错误率,这是目前为止最先进的方法。虽然无法在ImageNet上直接搜索该单元格,但在已知的方法中,由最佳单元格构建的NASNet在ImageNet上最高准确率为82.7%,top5准确率为96.2%。与以前最先进的模型相比,我们的模型比最好的人类发明的架构精确度高出1.2%,同时减少了90亿次FLOPS,计算需求减少了28%。基于不同的计算成本进行评估,NASNet的精确度超过了最先进的人类设计模型的精度。例如,一个小型的NASNet版本也达到了74%的顶级精度,这比同等大小的、最先进的移动平台模型要好3.1%。最后,从图像分类中学习到的图像特征是通用的,可以转移到其他计算机视觉问题上。在目标检测任务上,NASNet框架结合Faster-RCNN框架将精度提高了4%,mAP为43.1%。
开发图像分类的神经网络模型需要至关重要的架构工程,在ImageNet分类任务上使用卷积网络架构,这些年的工作是突飞猛进的,由设计架构之类的工程性手段带来的效果令人印象深刻。
本论文研究了一种设计卷积神经网络的方法,它可以用于各种图像分类任务,包括ImageNet任务的定制上。该方法受到之前的神经架构搜索方法的影响,它是用强化学习的方法进行架构定制的(么么哒)。然而,把NAS和其他搜索方法直接使用到大型数据集上,太奢侈了(呜呜)。也因此,研究人员先把小的数据集(比如CIFAR-10)当作某种代理数据集,在将该数据集上训练的网络迁移到大的数据集上(比如ImageNet)。(我去,从来只有大数据分布向小数据分布迁移的道理)。研究人员设计了一个搜索空间,姑且称之为”NASNet搜索空间“,架构的复杂度与网络的深度和输入图像的尺寸无关,也借此实现了某种可迁移性。更具体地说,该搜索空间里所有卷积网络是由不同权重但架构相同的卷积层(称为”cell“)组成的。找最好的神经网络架构等同于搜索最优的细胞(cell)架构。搜索最优的Cell结构有两个好处:它比搜索整个网络架构要快;单个cell在其他问题上的泛化性能更好。在我们的实验中,通过这个方法,我们先找到了CIFAR-10的最好架构,再乘以7,然后就很成功地迁移到ImageNet上去了。(乌拉)
NASNet在CIFAR-10实现了最佳结构,然后迁移到ImageNet上,无需太多改动。在ImageNet上,NASNet实现了已经公开的方法里最先进(STA)的效果,top-1精度82.7%,top-5精度96.2%。这比之前人手工设计的结构在top-1精度上提高了1.2%,同时减少了900万次FLOPS。在CIFAR10数据集上,NASNet的错误率为2.4%,也是目前的STA。
与此同时,通过更改卷积核以及滤波器的数目,我们可以更具不同的计算需求定制不同的NASNet。受惠于这一特性,我们可以在相同和更低计算开销的情况下,设计出一系列识别精度超过手工设计架构的模型。值得一体的是,最小版本的NASNet在ImageNet上的top-1精度为74%,比之前为移动端设计的架构高出了3.1个百分点。
最后,NASNet学习到的特征,可以迁移到其他计算机视觉任务上,我们可以将其与Faster-RCNN网络融合在一起,然后发现无论是大模型还是移动优化的模型,都在COCO目标检测数据集上实现了当前最优的效果。我们的NASNet大型模型的mAP为43.1%,高于目前的STA4个百分点。
方法
这个工作主要与超参数优化有关,现在这方面的工作包括Neural Fabrics、DiffRNN 、MetaQNN和 DeepArchitect。研究人员受到所谓Meta-Learning或Learning-to-learn、LSTM和Neural Architecture Search的启发。
论文的工作主要是利用搜索方法在感兴趣的数据集上找到良好的卷积体系结构。研究人员在这项工作中使用的主要搜索方法主要是之前提出的神经架构搜索(NAS)框架。在NAS中,控制器是由递归神经网络(RNN)组成,它会去采样具有不同体系结构的子网络。子网络通过训练达到收敛,以在保持的验证集上获得一定的精确度。产生的精确度用于更新控制器,以便控制器将随着时间的推移生成更好的体系结构。训练过程中,会使用策略梯度更新控制器权重。


图1. 神经架构搜索框架。 一个控制器以概率p从搜索空间里里预测架构A。具有A架构的子网络被训练,直到达到收敛精度R。然后以R的比例因子更新控制器的梯度。
该研究工作的主要贡献在于提出了一种创新型的搜索空间,先在CIFAR-10找到最佳架构,再向更大规模数据集(数据集大、分辨率高)上做推广。网络命名为NASNet,搜索空间为NASNet搜索空间。设计的灵感主要来源于卷积神经网络的架构如同搭积木,能不能从中归纳演绎出一些怪率呢?基于以上观察,研究人员希望通过一个RNN控制器去预测卷积核出现的概率,然后这些基元表示的卷积核细胞可以在任何空间尺寸和不同滤波器深度情况下任意组合。(低层次的感知,但已经有办法达到半自动化设计的程度了)。
在以往的方法法中,卷积网络的总体架构是手动预定的。它们由重复多次的卷积单元组成,其中每个卷积单元具有相同的结构,但是不同的权重。为了易于为任意大小的图像构建可扩展的体系结构,在以特征映射为输入时,通常需要两种类型的卷积单元以服务两个主要功能:(1)返回同一维的特征映射的卷积单元,和(2)返回特征映射的卷积单元,其中特征映射高度和宽度被减小2倍。我们分别命名第一类型的Normalization Cell和第二类型的Reduction Cell。对Reduction Cell,训练程序会使应用于单元的输入的初始操作具有两倍的步幅以减小高度和宽度。


图2.为Cifar-10和ImageNet设计的不同架构
图2显示了CIFAR-10和ImageNet的Normal Cell和Reduction Cell的位置。注意:在ImageNet上,会有更多的ReductionCell,因为传入的图像大小为299×299,而CIFAR的图像大小为32×32。Normal Cell和Reduction Cell可能具有相同的体系结构,但研究人员经验性地发现,学习两种不同的体系结构是有益的。当空间激活尺寸减小时,他们使用一种常见的启发式方法将输出中的滤波器数目增加一倍,以保持大致恒定的隐藏状态维。重要的是,就像Inception和ResNet模型展现一样,我们将基本模式(Motif,CNN积木)重复次数N和初始卷积滤波器的数目作为自由参数,以适应图像分类问题的规模。
这样,变化的只是Normal Cell和Reduction Cell的个数呢,这可以通过RNN搜索得到。(妙啊!)。在问题的搜索空间中,每个单元接收作为输入的两个初始隐藏状态Hi和Hi-1,它们是前两个低层或输入图像中的两个单元的输出。给定这两个初始隐藏状态,控制器RNN递归地预测卷积单元的其余结构(图3)。每个区的控制器的预测被分组为B块,其中每个块具有由5个不同的SoftMax分类器构成的5个预测步骤,对应于块本身的选择,就是离散的。
步骤1. 从之前创建的Block集合的隐状态中,选出hi、hi-1。
步骤2.重复步骤1。
步骤3. 选择一个数学操作,把步骤1的隐状态作为输入。
步骤4. 选择一个数学操作,把步骤2的隐状态作为输入。
步骤5. 把步骤3和4的结果组合成一个新的隐状态。

在第5步的时候,RNN有两种选择,它可以对步骤3、4隐状态运算的输出做点加,也可以做拼接。最后,将在卷积单元中生成的所有未使用的隐藏状态深度连接在一起,以提供最终的单元输出。

该算法将新创建的隐藏状态附加到现有隐藏状态的集合作为后续块中的潜在输入。控制器RNN重复上述5个预测步骤,一共有B个周期,对应于卷积单元中的B块。在实验中,选择B=5提供了良好的结果,尽管由于计算限制,研究人员没有穷尽地搜索该空间。


为了使控制器RNN能够同时预测Normal Cell和Reduction Cell,我们只需使控制器总共有2×5B的预测,其中第一个5B为Normal Cell做预测,第二个5B为Reduction Cell做预测。
最后,研究人员的工作利用 NAS中的强化学习建议; 然而,也可以使用随机搜索来搜索 NASNet 搜索空间中的体系结构。 在随机搜索中,可以从均匀分布中采样决策,而不是从控制器 RNN 中的 Softmax 分类器中采样决策。 在实验中,研究人员发现随机搜索比 CIFAR 10 数据集上的强化学习略差。 虽然使用强化学习是有价值的,但这种差距不如NAS论文所阐述的那么大。 这一结果表明,1) NASNet 搜索空间构造良好,使得随机搜索能够合理地执行,2) 随机搜索可以作为某种需要严肃对待的基准。
实验
在这一部分中,我们描述了用上述方法学习卷积Cell的实验。总之,所有的架构搜索都是在CIFAR-10分类任务执行的。控制器RNN使用最优策略优化(PPO)进行训练,使用全局工作队列系统生成由RNN控制的子网络池。实验用了500块GPU训练。
搜索候选卷积核花了四天四夜,要知道之前花了28天,简直是巨大的进步(XD)。然后,精度上还干得不错。


图4. 具有B=5个块的最佳卷积单元(NASNET-A)的结构用CIFAR-10识别。输入(白色)是先前激活(或输入图像)的隐藏状态。输出(粉红色)是所有得到的分支上级联操作的结果。每个卷积单元是B块的结果。单个块对应于两个基本操作(黄色)和组合操作(绿色)。
图4是对Normal Cell和Reduction Cell操作的示意图,采用了可分离卷积的模式,在CIFAR-10上先得到比较好的结果,再推广到ImageNet上。用神经网络架构搜索方法,我们得到了三组比较好的模型,称之为NASNetA, NASNet-B and NASNet-C。
通过在CIFAR-10和一个ImageNet分类任务上展示是如何使用这种架构的,我们演示了卷积单元的用途。它有效把计算预算降了几个数量级。在学习了卷积单元之后,可以探索若干超参数来构建一个特定任务的最终网络:(1)单元重复数N和(2)初始卷积单元中的滤波器数目。在选择初始滤波器的数目后,我们使用一种常见的启发式方法,在步长为2时,将滤波器的数目增加一倍。最后,我们定义了一个简单的表示法,例如4@64来表示所有网络中的这两个参数,其中4和64分别表示网络倒数第二层的单元重复数和滤波器数目。
在训练NASNet时,我们设计出了ScheduledDropPath,一种改进的DropPath[版本,是NASNet的一种有效的正则化方法。在DropPath中,单元中的每一条路径在训练期间随机下降,并具有一定的固定概率。在我们修改的版本ScheduledDropPath中,单元格中的每条路径都以在训练过程中线性增加的概率被删除。我们发现DropPath在NASNET中不太有效,而ScheduledDropPath在CIFAR和ImageNet实验中都显著改善了NASNets的最终性能。
1)CIFAR-10实验
对于CIFAR-10的图像分类任务,我们设置了N=4或6(如图2).最好的架构的测试精度报告记录在表1,并和其他最先进的模型进行了对比。从表中可以看出,一个没有做任何数据增强的NASNet的模型达到了最先进的错误率为2.40%(平均5次),这略好于之前的最佳记录2.56%。该模型的最佳单次运行误差率为2.19%。


表1. CIFAR-10训练结果
2) ImageNet实验
在ImageNet数据集上,研究人员用了基于CIFAR-10数据集学到的最佳卷积单元架构。需要强调的是,研究人员迁移了CIFAR-10任务上的架构,但对于ImageNet数据集的权重,却需要从头进行训练。
ImageNet训练结果摘要见表2 和表3 及图 5 。 在第一组实验中,研究人员训练了几个在 299 x 299 或 331 x 331 分辨率图像上操作的图像分类系统,在不同的计算需求中进行了不同的实验,以创建与 Inception-v2、 Inception-v3和 PolyNet在计算成本上大致相同的模型。 实验证明,神经网络架构搜索方法实现了最先进的性能,浮点操作和参数比参照的模型少。 第二,实验证明,通过调整模型的规模,可以在较小的计算预算中达到最先进的性能,超过之前科学家和工程师手工设计的卷积神经网络。
表2向我们展示了用CIFAR-10发现的卷积单元可以很好地推广到ImageNet训练任务上。具体说来,基于卷积单元的每个模型都超过相应的手动设计模型的预测性能。重要的是,最大的模型在一次性的、非集成性的预测中就实现了ImageNet数据集上82.7%的准确率,超过了之前的最佳公布结果1.2个百分点。NASNet在精度上最优,同时具有更少的浮点数操作。图5是与已有模型的比较,红线是NASNet的结果,黑线是之前人工设计的模型。


表2. 云端模型在ImageNet上的训练结果


表3.计算受限环境下NASNet模型同手工设计模型的比较(比如移动端,所有模型的分辨率均为224*224)


图5. 在ImageNet数据集上,不同的模型的准确率与参数变化图
最后,研究人员展示了最佳卷积单元在资源受限的环境中表现得有多好,例如移动设备(表 3 )。 在这些设置中,浮点操作的数量受到严重限制,预测性能必须与计算资源有限的设备上的延迟需求进行权衡。 在 224 x 224 幅图像上使用基线模型MobileNet-和 ShuffleNet,他们分别获得了 70.6% 和 70.9% 的精度,但进行了5.5亿次加法与乘法运算。 由最好的卷积单元构建的体系结构获得了优越的预测性能( 74.0% 的准确性),用更小的计算量超过了之前的模型。 总之,我们发现学习的卷积单元在模型尺度上是灵活的,在计算预算中达到了近 2 个数量级的提高。
3)对目标检测任务的改进
图像分类网络提供了可移植到其他计算机视觉问题的通用图像特征。最重要的是,它解决了物体在图像中的空间定位的问题。为了进一步验证NASNet-A网络的性能,研究人员测试了基于NASNet的目标检测模型在具体任务上是否有性能提升。
把NASNet模型同Faster-RCNN框架结合在一起,然后在COCO数据集上,用8000个样本的迷你验证集做测试。

4) 架构搜索方法的有效性


图6. 用强化学习搜索神经网络的架构和随机初始化训练的比较
强化学习搜索的方法得到的模型,在最后收敛的时候,比随机初始化或随机搜索模型高一个百分点,如同之前NAS论文强调的,它或许有用,但又没那么夸张。

结论
在这项工作中,研究人员展示了如何能从不同的图像分类任务的数据中学习可伸缩的、卷积的单元,这样搜索得到的体系结构是相当灵活的,因为它可以在计算成本和参数方面进行缩放,以便很容易地解决各种问题。在所有情况下,无论是云端模型还是为了移动环境设计的模型,都取得了最优的精度,超过了所有手工设计的模型。
主要的设计思路是构建了一个搜索空间,解耦架构的复杂性和网络的深度,把较小数据集(如CIFAR-10)上通过搜索得到的模型结构向其他各种图像数据集上的分类任务做迁移。
结果展现了,不需要太多的计算资源,NASNet的模型就可以在CIFAR-10和ImageNet数据集上取得当前最优的效果。然后,把分类网络提取出来的特征用于后续的计算机视觉任务(比如,目标检测、人脸检测和图像定位)。比如,它用于Faster-RCNN,可以在特定的目标检测数据集上达到当前最优的效果。最后,在移动端和嵌入式架构上,NASNet使用了更少的计算资源,性能上也超过了之前的流线形体系结构。

关于图卷积神经网络的博文翻译

图1. 一阶滤波器架构搭建的图卷积神经网

我们知道,真实世界的许多重要数据集会以图或网络的形式展现:社交网络、知识图谱、蛋白质交互网络、万维网等等(更多例子不再罗列)。然而,到本文写作前,很少有人关注神经网络模型在这类结构上的推广。近年来,许多论文重新审视了神经网络在此类图结构上加以推广的问题(Bruna et al., ICLR 2014; Henaff et al., 2015; Duvenaud et al., NIPS 2015; Li et al., ICLR 2016; Defferrard et al., NIPS 2016; Kipf & Welling, ICLR 2017)。它们中的一些算法在之前被核方法、基于图正则化方法以及其他方法统治的领域取得了令人炫目的效果。在本篇通讯里,我将简要概述这一领域的最新发展,并指出各种方法的优缺点。这里的讨论将主要集中在最近的两篇论文上:

Kipf & Welling (ICLR 2017), Semi-Supervised Classification with Graph Convolutional Networks (博主一作)

Defferrard et al. (NIPS 2016), Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

另外,有兴趣也可以去读下Ferenc Huszar的《How powerful are Graph Convolutions?》,此文列举了图卷积神经网络的一些局限性,我也与Ferenc Huszar君进行了若干互动,此处为我的评论。概要:

  • 神经网络在图结构上推广的简单介绍
  • 谱图卷积以及图卷积神经网络(GCN)
  • 演示:简单的一阶图卷积神经网络构建的图嵌入模型
  • GCN在Weisfeiler-Lehman 算法上的可微分泛化推广

如果你熟悉了,可以直接跳到这部分内容
图卷积神经网络的威力

将已有的神经模型(如RNN或CNN)推广到任意结构的图上是一个具有挑战性的问题。最近的一些论文介绍了此类应用的专门架构(例如Duvenaud et al., NIPS 2015; Li et al., ICLR 2016; Jain et al., CVPR 2016),另一些论文利用谱图理论在我们喜闻乐见的经典的CNN架构上做图卷积来定义用于多层神经网络模型的参数化滤波器(Bruna et al., ICLR 2014; Henaff et al., 2015)。最近的工作重点立足于弥合快速启发法和慢速方法之间的差距,但更通用性的做法是在频域上做文章。Defferrard et al. (NIPS 2016)使用Chebyshev多项式自由参数构建的近似平滑滤波器组成在频域上进行神经网络的学习。他们在规则空间的数据集里(如MNIST)上取得了令人信服的结果,效果并不比二维的卷积神经网络(CNN)差。在博主和博主导师发表的论文里,我们采取了类似的方法,也是用了谱图卷积的框架,但引入了更简化的方法,之后将进行讨论。在许多情况下,进行简化可以缩短训练时间,提高预测精度,从而在一些基准的图数据集上达到最先进(state-of-the-art,STA)的分类效果。


第一部分:基本概念

目前,大多数基于图结构的神经网络模型具有一定的通用性。可以把这些模型称为图卷积神经网络(GCNS);卷积意味着滤波器参数通常在图中的所有位置上是共享的(参考下 Duvenaud et al., NIPS 2015的论述)。这些模型的目标函数致力于在图上学习信号/特征,例如:G=(V,E)其作为输入:每个节点的特征描述xi;用N×D特征矩阵X概括(N:节点数,D:输入特征数)以矩阵形式对图结构建模;通常以邻接矩阵A(或其它一些函数)的形式表示。它产生一个节点级输出Z(N×F特征矩阵,其中F是每个节点的输出特征数)。图级别的输出可以通过引入某种形式的池化操作来建模( Duvenaud et al., NIPS 2015)。每一层神经网络可以写成一个非线性函数:

其中:

L为神经网络的层数,Z为图节点输出。模型的关键在于f(. .)该怎么选择和进行参数化。


第二部分:图卷积

一个深入浅出的例子让我们来看下这个简单形式的层级传播的例子:

为第l层神经网络的权重矩阵,

类似ReLu那样的非线性激活函数。尽管简单,但却足够强大,稍后我们略微点评一二。不过,首先,让我们解决这个简单模型的两个局限性:用A乘法意味着,对于每个节点,我们需要加上所有相邻节点的所有特征向量,然后去掉节点本身(除非图中有自循环)。我们可以通过在图中强制执行自循环来“修正”这个问题:我将恒等矩阵添加到A中。第二个主要限制是,A通常不是归一化的,因此与A的乘法将完全改变特征向量的尺度(我们可以通过查看A的特征值来理解这一点)。可以通过对A做归一化,使得所有行和为1,

其中D是对角线节点度矩阵,从而消除了这个问题。做这样的乘法可以提取相邻节点特征的平均值。在实践中,这里面的动态变化十分有趣,比如,我们可以使用对称归一化:

而不再仅仅是相邻节点的平均值。结合这两个技巧,我们基本上得出了在Kipf & Welling (ICLR 2017)中引入的传播规则。

其中:

我们有单位阵:

则是下面的矩阵:

之对角矩阵。在下一节中,我们将更深入地了解这种模型是如何在一个简单的示例图上运行的:Zachary的空手道俱乐部网络。
第三部分:空手道俱乐部网络的嵌入

图2. 空手道俱乐部的图模型,不同颜色表示聚类得到的不同社团

让我们来看看我们的简单GCN模型(见前一节或 Kipf & Welling,ICLR 2017)是如何在著名的图表数据集Zachary的空手道俱乐部网络(见上图)上工作的。我们取一个随机初始化权重的三层GCN。现在,甚至在训练权重之前,我们只需插入图的邻接矩阵,X=I(即单位阵,因为我们没有任何节点特征)进入模型。三层GCN现在在正向传递过程中执行三个传播步骤,并有效地卷积周边每个节点的三阶邻域(所有节点最多到三阶)。值得注意的是,模型生成了这些节点的嵌入,这些节点与图中的社区结构非常相似(参见下图)。我们已经完全随机初始化了权重,并并且是在没有训练更新的情况下完成的!

图3. 基于初始化权重的图模型嵌入所表示的空手道俱乐部建模

是不是看上去很令人惊讶,Perozzi et al., KDD 2014论文里提出了一种思想叫深度游走(DeepWalk),它可以通过复杂的无监督学习方法来学习到这些嵌入表示,为什么不在用少量资源甚至不需要花费计算资源的情况下,就去掌握这样的特征表示呢,GCN,或许是您的选择。我们可以通过将GCN模型解释为著名的Weisfeiler-Lehman图算法(WL算法)的一个广义的、可微的版本来阐明这一点。(一维)Weisfeiler-Lehman算法的工作原理如下:对所有节点vi属于G:

  • 得到邻居节点 {vj}的特征{hvj} 
  • 用哈希函数更新节点 hvi←hash(∑jhvj), 其中哈希函数hash(⋅) 是理想的单射哈希函数。

重复K步直到收敛。实际中,WL算法会为每个独特的特征集合分配对应的图节点。这就意味着每个被分配对应特征的节点都可以被用图表示出来。像网格(grid)、链(chain)等高度规则的图会是个特例。对大多数不规则的图,特征分配可以用来检验图是否是同构的(两个图是否相同,取决于节点的排列)。回到向量形式的图卷积神经网络的层级传播规律:

其中 j 表示vi的邻居节点。cij 是边 (vi,vj) 的归一化常数,它由GCN模型的对称归一化邻接矩阵D^(-0.5)AD^(-0.5)变化而来。传播规律可以表达成原始WL算法的哈希函数的可微分和参数化形式W(I)。如果我们选择选择进行非线性拟合,并对正交化的随机权重矩阵做初始化(参考 Glorot & Bengio, AISTATS 2010),在实际应用中,传播参数的更新将会是稳定的(当然,做归一化得到cij 也是功不可没的)。现在,我们得到非常有意义的平滑嵌入,我们也可以将嵌入后节点之间良好的距离解释为局部结构的(非)相似性。
第四部分:半监督学习

由于我们的模型中的所有计算推到都是可微分的和参数化的,所以我们可以添加一些标签,对模型进行训练,并观察嵌入的变化。我们可以使用在Kipf & Welling(ICLR2017)中引入的GCN半监督学习算法。简单地将每个类/社区的一个节点(在下面的视频中突出显示的节点)进行标记,并启动对多轮训练。(用GCN进行半监督分类,每个类的标签经过300多个对隐空间内部动态变化的训练迭代步骤的进行学习,标记的节点被高亮,视频地址:https://tkipf.github.io/graph-convolutional-networks/images/video.mp4)。这个模型可以直接生成二维可视化的隐空间。

我们可以看到,一个3层的图卷积神经网模型就可以尝试线性地划分出社团。给每个类打上不同的标签。考虑到没有太多节点特征描述作为输入,这样的结果非常棒。与此同时,初始化节点特征是可以获得的,这个可以参考(Kipf & Welling, ICLR 2017)的实验,它证明了用图模型的方法可以在相关数据集上达到STA的效果。
结论:对于此项议题的研究方兴未艾。最近几个月的变化可谓是日新月异,然而,这只是摸到了模型的表皮,图神经网络如何进一步解决一些特定类型的问题仍然有待观察,比如有向和关系图的学习,如何利用学到的网络嵌入等等,都还刚刚起步,需要解决。我所罗列的东西并不完备,希望未来会有更多精彩的应用和扩展。欢迎大家有好想法的一起来分享下。

与Ferenc Huszar 商榷:

Ferenc Huszar在他的文章《 How powerful are Graph Convolutions?》提了些质疑,它举了常规化图的特定例子。它认为古典的CNN是专门为特定领域,比如图像处理设计的,图卷积模型的引入会带来烦琐的操作。目前来说,适用于任意结构图的GCN模型在应用于通用的图(如网格、链、全连通图等)时通常有一些缺点。Defferrard et al., NIPS 2016采用局部化谱操作,引入旋转对称滤波器,但在网格(grid)上,除了依然有边界效应外,却不能模仿经典CNN的效果。与此同时,WL算法也无法在普通的图上收敛。这告诉我们的是,当我们试图评估特定图形神经网络模型的有效性时,我们应该超越常规网格,因为在为任意图设计此类模型时,我们必须进行特定的权衡(但让人们了解这些权衡是很重要的),除非我们可以在找到一个普遍强大的模型(不太可能)。

1. 谱图卷积表示在图的傅立叶空间中,进行信号与滤波器的相乘。图傅立叶变换定义为图信号X(即每个节点的特征向量)和特征向量矩阵U的拉普拉斯图 L做乘法。利用对称归一化的图邻接矩阵可以很容易地计算出(归一化的)拉普拉斯图:

2. 使用频谱方法的代价是:必须在傅里叶空间中定义滤波器,并且图傅里叶变换对于计算机来说是昂贵的(它要求节点特征与图Laplacian的特征向量矩阵相乘,该特征向量矩阵是具有N个节点,整个操作费时O(N^2);计算最初的位置中的特征向量矩阵甚至更昂贵)。

3. 我简化了讨论: Douglas(2011)讲述了WL算法的数学扩展。

4. Weisfeiler-Lehman算法的节点特征是整数,会被上颜色。

5. 在这个例子中,我们没有退火学习率,所以一旦模型收敛到一个好的解决方案,事情就会变得非常“不稳定”。

Shreya Gherani:BERT庖丁解牛(N.Y.翻译)

BERT是双向转换器(Bi-Transformer)的缩写。这是谷歌在2018年末开发并发布的一种新型语言模型。BERT等经过预处理的语言模型在问答、命名实体识别、自然语言推理、文本分类等自然语言处理任务中发挥着重要作用。

BERT是多层的双向转换器堆叠,编码机制只要微调就可以运作,文章一开始有必要回顾下Transformer的架构。

Transformer的前世今生

2017年,谷歌发表了一篇题为《Attention is all your need》的论文,该论文提出了一种基于注意力的结构来处理机器翻译相关序列模型相关的问题。传统的神经机器翻译大多采用循环神经网络(RNN)或卷积神经网络(CNN)作为编解码器的元模型。然而,谷歌基于注意力的Transformer编解码模型跳出了传统的RNN和CNN范式。该模型具有非常高的并行性,在提高翻译性能的同时,训练速度也挺快。

让我们把时光倒流几年,回到attention机制真正起源与全部秘密所在。

什么是注意力(Attention)机制

注意力(Attention)机制可以看作是模糊存储的一种形式。模型的隐层算是某种存储器,模型选择从内存中检索内容。在我们深入关注之前,让我们简要回顾一下序列-序列(Seq2Seq)模型。传统的机器翻译基本上是基于Seq2Seq模型的。该模型分为编码器层和解码器层,由RNN或RNN变体(LSTM、GRU等)组成。编码器的最后隐状态产生编码向量。编码向量用来封装所有输入元素的信息,以帮助解码器做出准确的预测。输出的编码向量充当模型中解码器部分的初始隐藏状态。Seq2Seq模型的主要瓶颈是需要将源序列的全部内容压缩到一个固定大小的向量中。如果文本稍长,很容易丢失文本的一些信息。为了解决这一问题,人们开始着手关注并解决问题。注意力机制通过允许解码器回溯源序列的隐藏状态,然后提供加权平均值作为解码器的附加输入来缓解这一问题。顾名思义,使用注意力机制,模型在解码阶段会选择最适合当前节点的上下文作为输入。

https://jalammar.github.io/images/seq2seq_7.mp4

(Seq2Seq模型演讲视频)

注意力机制模型与传统的Seq2Seq模型有两个主要的区别:

首先,编码器会向解码器提供更多的数据,在这一过程中,编码器将向解码器提供所有节点的隐层状态,而不仅仅只是编码器最后一个节点的隐层状态。

其次,解码器绝非一股脑儿使用所有编码器提供的隐层状态,而是会采取一种选择机制为当前位置适配最合适的状态。为此,解码器会计算每个隐藏状态的分数值并对分数进行Softmax打分,来确定哪个隐藏状态与当前节点最密切相关,某个隐层状态如果具有更高相关性,将会得到更大多分数,而相关性较小的隐层状态则分数会比较低。接下来,隐层状态会跟每个自身的softmax分数做点乘,softmax分数高的隐状态会被放大,softmax分数低的隐状态会被抑制。这个操作会在Attention模型解码器每个时间步长上都被执行。

https://jalammar.github.io/images/attention_process.mp4

(关于Attention模型演讲视频)

让我们看看传统RNN模型Attention(Seq2Seq)执行的步骤:

1.双层RNN模型的解码端置位嵌入向量(Embedding)以<END>(表征结束>的令牌(token),并对隐状态初始化。

2.解码端的RNN接收输入,产生输出和新的隐状态向量h4,当前输出会被放弃。

3.注意力步骤:采用编码器的隐状态向量和解码器生成的隐状态向量h4产生内容向量C4。

4.将隐状态向量h4和内容向量C4拼接成一个新的向量。

5.把新的向量传给一个前向连接网络(跟模型一起训练)。

6.全连接层的输出表征当前时间上输出的词。

7.执行下一步。

https://jalammar.github.io/images/attention_tensor_dance.mp4?source=post_page————————&#8212;

(Attention张量工作视频)

Attention论文里的Transformer

Transformer模型采用了一种编解码架构。在谷歌第一篇关于Attention 论文里,编码端有6层编码器,解码端有6层解码器。结构如图所示:

图1. 编解码器架构

编码器由两层组成,一层是自注意力(self-attention层),另一层是前馈神经网络。在sel-attention层当前节点不仅关注当前单词,还能获得上下文语义。解码器除包含编码器里有的两层网络,还在两层中间添加了一个额外的注意力层(Attention Layer),以帮助当前节点获得需要关注的内容。

以下是Attention模型的架构。

图2. Transformer结构图

我们将回顾下每个模块。

自注意力

自注意力机制主要是关注学习对当前词和其周围词相关的某种人类的理解。

首先,自注意力机制会去计算三种向量。在《Attention is all your need》论文中,向量的维数为512维。有查询向量、键向量和值向量三种向量。这三个向量是通过乘以字嵌入向量和一个随机初始化矩阵(论文中的维数为(64,512)产生的,反向传播过程中更新矩阵值。

图3. Self-Attention里各种向量

接下来,需要计算自注意力机制的零碎值,当我们在编码某个位置上单词时,零碎值会决定对输入句子的其余部分,需要给予多少关注(权重)。计算零碎值方法使用查询向量和键向量。计算的结果会除以一个常数。论文中的值为8,通常这个值会是更新矩阵列数的平方根,也就是64的平方根8。然后我们对所有的分数进行softmax计算,其结果是每个词与当前位置上的单词的相关性。毫无疑问,当前位置的词的相关值自然是大的。最后一步要将值向量与Softmax结果相乘,并把它们相加。这将得到当前节点的self-attention权重。

图4. 自注意力运行机制图解

通过查询和键值之间相似度比较,可以得到权重分布等值,这一操作被叫作比例伸缩点乘(scaled dot production)。

多头Attention机制

Self-Attention机制更令人炫目的特性绝非初始化三个查询、键、值三个矩阵(Q、K、V)那么直线条,它还有一个多头Attention机制。转换器会更新8组分块数据,最后的输出结果是8个矩阵,见图5。

图5. 多头Attention机制

前馈神经网络不能直接使用8个矩阵,所以需要把8个矩阵转换为一个矩阵,先把它们拼接起来,再把这个大的矩阵乘以一个初始化的随机矩阵。详细过程见图6。

图6. 多头Attention机制是如何转换为独一的输出矩阵的

一般来说,Transformer有三种不同的方法来使用多头Attention机制。

1. 在“编码器-解码器注意力层”中,查询向量来自上一个解码器层,键向量和值向量由当前编码器输出给定。这允许解码器中的每个位置都能对应到输入序列。这模仿了Seq2Seq模型(通常是双层RNN)中的典型编码器-解码器注意(Attention)机制。

2. 编码器本身也有自注意力层(Self Attention Layer)。在这个自注意力层中间,所有的键、值和查询都来源于前一个编码器的输出。编码器中的每个位置都可以回溯到前一个编码器的对应位置。

3. 类似地,解码器中的自注意力层也允许解码器中词向量位置能回溯到之前的解码器对应位置。为了保持自回归特性,我们需要防止解码器中的左信息流,因此,在伸缩点乘(scaled dot production)操作里,我们会屏蔽softmax函数非法值(通常是无穷大)。这将在我们关于解码器掩码部分进行更详细的探讨。

位置编码

目前为止,我们依然无法让Transformer模型理解输入序列里的词顺序。为了解决这一问题,可以在Transformer模型的编码器和解码器输入端加入一个额外的位置编码向量。位置编码向量的维度等于嵌入向量的维度,嵌入向量会附加上位置编码向量,作为下一个神经网络层的输入。位置编码有多个选项,固定的或可学习的。

图7. 位置编码

残差连接与层归一化

在编码器和解码器里,都会有一个残差连接(Residual Connection)模块,残差连接层紧接着做层归一化(Layer Normalization)。跳跃连接和残差连接允许绕过非线性激活函数直接进行梯度传导。非线性激活函数在某些权重的情况下会发生梯度消失或梯度爆炸情况。跳跃连接允许坐“直通车”直接进行梯度的前向传播和反向传播。

层归一化用来解决深度学习里内部相关变量偏移(Internal Covariance Shift)的问题。内部相关变量偏移问题主要指代神经网络中发生的共变转移,比如,第三层的统计分布相对于第二层的统计分布发生偏移。之所以会产生这样的现象,是因为随着网络学习和权重的更新,网络中特定层的输出分布会发生变化。较高层为了适应这种漂移,将被迫降低学习速度。在对神经网络中的输入进行归一化之后,我们可以不用担心输入特征会发生畸变。为了理解层归一化(Layer Normalization),可以将其与批归一化(Batch Normalibation)进行比较。一个少量批处理数据会由多个具有相同数量的特性的示例组成。少量批处理数据可以是多维的矩阵或张量-一个轴表示批次,另一个表示特征维度。批归一化使整个批处理维度的输入特性规范化。层归一化的主要特点是它能对各特征之间的输入进行规范化。在批归一化中,统计信息是按批次(Batch)进行处理的,对批处理中的每个示例(Instance)都是普适的。相反,在层归一化中,统计数据是跨特性计算的,每个示例都是相互独立的。

图8. 批归一化(Batch Normalizaiton)与层归一化(Layer Normalization)

残差连接与层归一化双剑合璧之后的Transformer如图9所示。

图9. 残差连接加上层归一化后的Transformer

解码器

回到Transformer架构图,我们可以看到解码器部分类似于编码器部分,但在底部有一个基于多头注意力机制的Mask。Mask表示一个掩码,它遮盖某些值(),使其在参数更新时不会起作用。Transformer模型中有两种掩码-填充掩码(padding mask)和顺序掩码(sequence mask)。填充掩码用于可伸缩点乘(scaled dot production)操作,序列掩码仅用于解码器的自注意力(self-attention)操作。

填充掩码主要解决输入序列变长的问题。具体来说,我们在一个较短的序列之后填充零。当然,如果输入序列太长,将截取左侧有意义的内容,多余的内容将被直接丢弃。因为这些填充物的位置其实是没有意义的,自注意力机制应该避免将资源用到这些位置,为此,需要做一些处理。具体的方法是在这些位置的值中添加一个非常大的负数(负无穷大),这样在Softmax之后,这些位置的概率将接近于0!填充掩码实际上是一个张量,每个值都是布尔值,我们需要处理的位置的布尔值为假(False)。

序列掩码可以确保解码器无法看到未来的信息。也就是说,对于序列,在相关的时间步长中,我们解码的输出应该只依赖当前时间t之前的输出,而不是t之后的输出。这是Transformer转换器结构所特有的,因为Transformer无法像RNN可以顺序地输入序列。在这里,所有的输入序列都集中在一起,如果没有掩码,多头注意力会考虑解码器输入序列里每一个位置。Transformer会生成一个上三角矩阵,上三角矩阵的下三角部分为零,将该矩阵同输入序列做乘法。

在解码器的自注意力操作部分,会使用可伸缩点乘操作(scaled dot production)。填充掩码加上序列掩码构成了注意力掩码,在其他情况下,注意力掩码就是填充掩码。

另一个要注意的细节是,解码器会将输入右移。这样做的一个原因是,我们不希望我们的模型训练只是在复制解码器的输入,而是说,在给定编码器序列和特定的解码器序列情况下,模型可以预测下一个单词/字符。如果我们不改变解码序列,模型可能只会做到简单地“复制”解码器输入,解码器位置i的输入单词/字符变成输出位置i的目标单词/字符。因此,通过将解码器输入移位,模型在看到1……i-1位置的单词和字符的情况下预测i位置上的单词和字符。这使我们的模型避免进入那种复制/粘贴模式。我们在句子的第一个位置标记一个起始的令牌(token),如果不这样做,因为右移,该位置将是空的。依样画葫芦,我们在句子的最后一个位置也会加上一个令牌来表征序列的结束,并将其添加到输出的目标序列中去。

输出层

解码器的操作完成之后,要将运算得到的结果映射到输入的单词上,模型会在最后加上一个全连接层与softmax层。

模型最后的线性层是一个简单的全连接层,它将解码器堆栈产生的向量投影到一个更大的向量中,称为逻辑(Logits)向量。假设Transformer模型理解10000个独特的英语单词(模型的“输出词汇表”),这是从它的训练数据集中学到的。逻辑向量里就会有10000个单元(cell)每个单元会根据相关分数对应到唯一的单词。这样线性层的输出就可以解释成某种词汇了。然后,softmax层将这些分数转化为概率(和为1.0的正数)。概率最高的单元格将被挑出来,在这个时间步长上,输出相关的单词。

图10. Transformer模型最后的全连接层与softmax层

让我们回头看看BERT吧

BERT的架构是基于Transformer的。它是一个深层的、双向的神经网络。BERT的技术创新就在于把双层Transformer结构应用到语言模型上。它与之前那种自左向右或自右向左进行顺序训练学习文本序列的尝试完全不同。它采用了一种新颖的遮蔽语言模型(Masked Language Modeling),这实现了之前不可能的双向训练机制。在Transformer原生模型里,它分成了两个部分,编码器读取文本输入,解码器进行预测。BERT的目标是去生成一个语言模型,因此只需要Transformer 的编码器。

谷歌最初发布了两版BERT模型,如图11所示。这里,L表示Transformer的层数,H表示输出的尺寸,A表示多头注意力层的数量。在这两种版本中,前馈神经网络的被大小设置为4层。

BERTBASE::L=12,,H=768, A=12, 总参数量110M。

BERTLARGE::L=24,H=1024, A=16,,总参数量340M。

使用BERT模型有两个阶段:预训练阶段与微调阶段。在预训练阶段,模型基于未标记的数据完成预先设置任务训练。在微调阶段,模型基于预训练权重初始化并着手面向下游任务。不同的下游任务有各自独立的模型,即使他们由一套相同权重初始化。BERT可以通过统一的架构抽取出独特的特征,然后面向不同的任务。因为参数需要微调,预训练架构与下游架构之间存在着差异。

图11. BERT预训练模型与微调模型

预训练的BERT

BERT的预训练阶段有两个无监督预测任务:遮蔽语言模型(Masked Language Modeling)和下一句预测(Next Sentence Predictiom)。

掩蔽语言模型(Masked Language Modeling)-由于BERT使用双向Tramsformer和多层自注意力机制,为了训练出深度的双向表示学习模型,BERT会对输入标记的某些百分比(论文中为15%)进行随机掩蔽,然后对这些遮蔽的标记进行预测。如同标准的语言模型所操作的,与遮蔽的掩码标记所对应的最终隐层向量被输入到词汇表上的输出的softmax函数中。与从左到右进行训练语言模型不同,对目标函数进行最大似然估计的模型允许表示融合上下文,这使得对深层的、双向的Transformer进行预训练成为可能。这允许获得双向预训练模型,但缺点是预训练和微调之间存在不匹配,这是因为掩码遮蔽(masked)的令牌(token)在微调过程中不会出现。为了缓解这一弊病作者并不总是用实际的[MASK]标记替换“掩码”字。训练中,可以随机划分出15%的数据,对其令牌位置进行预测。如果某一位置的令牌(token)被选中了,(1)80%的情况下被替换为[MASK]令牌(token);(2)10%的情况下替换为随机令牌(token);(3)剩下10%情况保持不变。BERT损失函数主要考虑对被遮蔽(Masked)掉的词预测,忽略了对非非遮蔽词预测。因此,模型的收敛速度会比定向模型慢,但这一缺憾,相比增强的上下文感知能力,是微不足道的。

下一句预测——为了理解句子关系和词之间的语义关系,BRRT将下一句预测变成一个二分类问题,这样就可以通过现有的语料库进行文本生成。有A和B两类句子,其中50%的B类样本是A的下一句,剩下50%作为负样本也是能学习到句子之间的相关性。这样的方法在一些自然语言处理任务比如问答(QA)和自然语言推理(NLI)中被大量采用,使得预训练模型可以更好适应这类任务。

为了让模型在训练中区分出这两种句子,需要对输入进行些预处理。

1)每个句子的开头会加入[CLS]令牌(token),结束部分插入[SEP]令牌(token)。

2)在每个标记中添加表示句子A或句子B的句嵌入,句嵌入在概念上可以看作一种大小为2的词汇表。

3)每个token上加入位置嵌入,位置嵌入的概念与实施策略在介绍Transformer模型的章节被描述过。

如果后一句与前一句有联系,那么:

1)整个序列将被输入到Transformer模型里。

2)通过在一个简单的分类层中学习矩阵的权重与偏置,[CLS]令牌(token)转换为一个2*1的向量。

3)通过softmax函数输出是否下一句的概率。

在BERT模型里,遮蔽语言模型和下一句预测任务是同时训练的,最小化联合损失函数以完成对两个策略的训练任务。

令牌化(tokenization)-这不是说BERT把单词看作某个token。相反,它着眼于WordPieces,这意味着一个单词可以被分解成多个子单词。这种标记在处理新词时候是非常棒的,它有助于更好地表达复杂的词汇。

BERT模型输入

BERT的输入可以是单词序列中的单个句子或句子对(例如,[问题、答案])。对于给定的词,它的输入表示可以由三个部分嵌入(Embedding)求和组成。嵌入向量的图片如图12所示:

图12. BERT模型的嵌入

令牌嵌入(Token Embeddings)表示词向量,第一个词用[CLS]作为标记,可以用在随后的分类任务里,如果是非分类任务,CLS记号可以忽略不计。分割嵌入(Segment Embedding)用来区分两个不同的句子,BERT的预训练既致力于产生语言模型,也会训练一个把两句句子作为输入的分类模型。位置嵌入(Positional Embedding)编码词顺序。

BERT对NLP下游任务微调

对每个下游的NLP任务,我们只需要即插即用地给BERT模型给定输入输出,然后进行端到端参数微调就行了。在输入端,来自预训练模型的句子A和句子B可以类比释义中的句子对、逻辑推论中的建设前提、问答中的问题对。在输出端,将令牌(token)表示输入到输出层,用来完成令牌(token)级任务,比如序列标记或问题回答,输出层接收[CLS]标志,用于诸如推断蕴含和情感分析之类的分类任务。

图13. BERT微调模型示意图

BERT只需要给核心模块加入一些小的层就可以适应广泛的语言任务。

1. 情感分析之类的分类任务可以类比于预训练阶段的下一句预测,在Transformer的顶层加入一个带有[CLS]令牌(token)的分类层。

2. 在问答任务(比如SQuAD v1.1)上,软件接收一组表示问题的文本序列,提供一组表示回答的文本序列。使用BERT,问答模型可以加入两个额外的向量,一个表示回答的开始,一个表示回答的结束,来进行学习。

3. 在命名实体识别(Named Entity Recognition (NER))任务中,软件接收到一组文本序列,要从文本中找出对应的各种实体(人名、机构名、日期)。一个使用BERT的命名实体识别模型可以将输出向量里每个令牌(token)送入分类层预测其对应的NER标签。

用于特征提取的BERT

BERT不仅能进行微调,您还可以把预训练BERT当作一种基于上下文语境的词嵌入模型。可以把BERT预训练模型得到的嵌入向量馈送给紧接着的其他NLP模型——在诸如命名实体识别之类任务上,论文里的实验部分告知我们说,这样干的效果并不逊色于微调BERT模型。

图14. BERT通过Transformer的编码器生成基于上下文语境的嵌入向量(Contexualized Embeddings)

哪一个最适合作为基于上下文嵌入向量呢?这取决于任务。本文研究了六种选择(BERT微调模型得分96.4):

图15. 在CoNLL-2003命名实体识别任务数据集上不同的BERT变种模型的Dev F1分数

希望您喜欢读这篇文章,就像我喜欢写这篇文章一样!感谢网络上那些优秀的资源,帮助我在写作的时候掌握BERT模型的概念。