【笔记】Reptile-一阶元学习算法

Nichol A , Achiam J , Schulman J . On First-Order Meta-Learning Algorithms[J]. 2018.

是函数的一阶偏导数以肯定方式分列成的矩阵，其体现了一个可微方程与给出点的最优线性迫近。

• 假设\(F:\mathbb{R}_\mathrm{n}\rightarrow \mathbb{R}_\mathrm{m}\)是一个从n维欧氏空间映射到到m维欧氏空间的函数。这个函数由m个实函数组成：
  

• 这些函数的偏导数(假如存在)可以组成一个m行n列的矩阵，这个矩阵就是所谓的雅可比矩阵：
  

一个分析表达式按照泰勒公式成无穷级数（大概多项式），根据所研究的界说域，每一个睁开项所贡献的巨细是不会都雷同的，根据它们对分析表达式准确值的贡献巨细将这些项分门别类地叫做领头阶、次领头阶、次次领头阶…

摘自：维基百科（https://en.wikipedia.org/wiki/Transduction_(machine_learning)）

• 转导（Transduction）：从观察到的特定（训练）案例到特定（测试）案例的推理。
  
• 归纳（Induction）：从观察到的训练案例到一样平通例则的推理，然后将其应用于测试案例。
  

• 示例：
  
  
  
  给出一个点的聚集，此中一些点被标记了为A，B或C，但是大多数点没有被标记，用？表现。训练的目的是猜测全部未标记点的“最佳”标签。
  
  
  
  • 接纳归纳的头脑，是利用有标记的点来训练监视学习算法，然后让其猜测全部未标记的点的标签。但是，对于这个标题，监视学习算法将仅具有五个标记点，创建捕捉该数据布局的模子肯定会很困难。比方，假如利用近来邻人算法，则纵然很显着可以看到中央附近的点与标记为“ B”的点属于同一个聚集，也有大概会被标记为“ A”或“ C”。
    
  • 转导在实验标记任务时，可以或许思量全部点，而不但仅是标记点。在这种情况下，转导算法将根据它们本来所属的簇来标记未标记的点。因此，中央的点很大概会标记为“ B”，由于它们的位置非常靠近该聚集。
    
    
    
    • 转导的一个上风是，它可以利用较少的标记点来举行更好的猜测，由于它利用了未标记点中的天然隔断（Break）。
      
    • 转导的一个缺点是它没有创建猜测模子。假如将先前未知的点添加到聚会合，则必要对全部点重复整个转换算法，以猜测标签。假如数据在流式的数据中渐渐可用，则在盘算上大概会很昂贵。别的，这大概会导致某些旧点的猜测发生变革（取决于应用步调大概是好是坏）。另一方面，有监视的学习算法可以立即标记新点，而盘算本钱却很少。
      
    
    
  
  

• 人类在举行一项新的任务时，通常利用了大量编码于人类大脑和DNA中的先验知识。得益于此，人类具有快速学习的本领，在数学上这种本领的得到可以表明为贝叶斯推断（Bayesian Inference）过程，这也正是开辟出能到达人类水平的学习速率的算法的关键。但实际上利用深度神经网络开辟出盘算上可行的贝叶斯呆板学习算法是极具寻衅的。
  
• 与此差别，元学习算法并没有实验去模仿贝叶斯推断过程，而是试图利用任务数据集直接优化快速学习算法，这种算法作为一种“署理”，可以或许在新任务上快速顺应并学习。两类常见的元学习方法：
  
  
  
  • 基于模子：将学习算法编码为循环网络模子中的权重，从而在训练过程中对元学习模子的参数举行更新。
    
  • 基于初始化：
    
    
    
    • pre-training：在大量数据上（ImageNet）上学习网络的初始化参数，然后在新任务上举行测试时对这些参数举行微调。这种方法无法包管得出的参数便于调解，为了到达精良的性能偶然还必要一些特殊的本领（ad-hoc tricks）。
      
    • MAML：在优化过程中对初始化参数举行微分更新，以得到一个敏感的基于梯度的学习算法。但是这种算法利用了二阶微分盘算，增大了盘算开销。
      
    • FOMAML：作为MAML的变种，忽略了二阶微分项，节省了盘算开销，但丧失了部分梯度信息。
      
    
    
  
  
• 针对某些标题利用依靠于高门路度的技术大概出现的复杂性，本文探究了基于一门路度信息的元学习算法。
  

• 指出FOMAML的实现相比以前的认知更加容易。
  
• 提出了Reptile算法。这种算法与连合训练（joint training，通过训练来最小化在一系列训练任务上盼望丧失）非常相似，而且与FOMAML精密干系，但是与FOMAML差别，Reptile无需对每一个任务举行训练-测试（training-testing）分别。
  
• 对FOMAML和Reptile举行了理论分析，表明两者都对任务内泛化举行了优化。
  
• 在对Mini-ImageNet和Omniglot数据集举行实证评价的底子上，提出了实行最佳实践的一些见解。
  

• MAML优化过程的公式化表现：
  \[  \min_{\phi}\mathbb{E}_{\mathcal{T}}[L_{\mathcal{T},B}(U_{\mathcal{T},A}(\phi))]  \]
  

  对于给定的任务\(\mathcal{T}\)，内循环中利用训练样本\(A\) 举行优化，然后利用测试样本 \(B\) 盘算得到丧失，外循环利用丧失对初始化参数求梯度，即可得出新任务上参数的优化方向。
  

  \[  g_{MAML}=\frac{\partial L_{\mathcal{T},B}(U_{\mathcal{T},A}(\phi))}{\partial \phi}=L^{\prime}_{\mathcal{T},B}(\tilde{\phi})U^{\prime}_{\mathcal{T},A}(\phi), \qquad where \quad \tilde{\phi}=U_{\mathcal{T},A}(\phi))  \]
  

  此中 \(U^{\prime}_{\mathcal{T},A}(\phi)\) 可以视为是关于 \(U_{\mathcal{T},A}(\phi)\) 的雅可比矩阵，而 \(U_{\mathcal{T},A}(\phi)\) 可以视为是对初始化参数向量累加了一系列的梯度向量， \(U_{\mathcal{T},A}(\phi)=\phi+ g_1 + g_2 + \dots +g_k\) 。
  

  
  
• FOMAML的简化：
  

  将梯度向量视为常量，即可将雅可比矩阵转化为恒等利用（identity operation），以是可以简化外循环优化过程中所利用的梯度公式。
  

  \[  g_{FOMAML}=L^{\prime}_{\mathcal{T},B}(\tilde{\phi})  \]
  

  具体流程如下：
  

  
  
  • 采样任务\(\mathcal{T}\) ；
    
  • 对初始化参数实验更新利用，得到\(\tilde{\phi}=U_{\mathcal{T},A}(\phi))\)；
    
  • 利用 \(\tilde{\phi}\) 盘算对 \(\phi\) 的梯度，得到 \(g_{FOMAML}=L^{\prime}_{\mathcal{T},B}(\tilde{\phi})\)
    
  • 将\(g_{FOMAML}\) 应用到外部循环优化中。
    

  
  

• 算法描述
  
  
  
  
• 算法末了一步的模子参数更新的batch版本，可以写为如下情势：
  \[  \phi \leftarrow \phi +\epsilon \frac{1}{n} \sum_{i=1}^{n}(\tilde{\phi_i}-\phi)  \]
  

  此中\(\tilde{\phi_i}=U^{k}_{\mathcal{T}_i} \left\{ \phi \right\}\) ，表现在第i个任务上对参数的更新利用。
  

  
  
• 这个算法与在丧失盼望上举行的连合训练非常相似。
  
• 当k=1时，算法对应于盼望丧失的随机梯度降落（SGD）。
  \[  \begin{align}  g_{Reptile,k=1} & =\mathbb{E}_{\mathcal{T}}\mathrm{[\phi-U_{\mathcal{T}}(\phi)]/\alpha}\\  & =\mathbb{E}_{\mathcal{T}}\mathrm{[\nabla_{\phi}L_{\mathcal{T}}(\phi)]}  \end{align}  \]
  
• 当k>1时，更新过程包罗了\(L_{\mathcal{T}}\) 的二阶以致更高阶的微分项。
  

• 更新过程中的领头阶（Leading Order）睁开
  

  直觉是：
  

  
  
  • 利用泰勒序列睁开来近似表现Reptile与MAML的更新过程，发现两者具有雷同的领头项（leading-order terms）——领头阶（第一项）起着最小化盼望丧失的作用；次领头项（第二项）及后续项最大化任务内的泛化性。
    
  • 最大化同一任务中差别minibatch之间梯度的内积，对此中一个batch举行梯度更新会显著改善另一个batch的的体现。
    

  
  
  
  
  • 表达式界说（\(i\in[1,k]\) 指代差别的batch）
    \[  \begin{align}  &g_i=L^{\prime}_i(\phi_{i})\quad(在SGD过程中得到的梯度)\\  &\phi_{i+1}=\phi_i-\alpha g_i\quad（参数更新序列）\\  &\bar{g_i}=L^{\prime}_i(\phi_1)\quad （起始点梯度）\\  &\bar{H_i}=L^{\prime \prime}_i(\phi_1)\quad (起始点Hessian矩阵，即二门路度)  \end{align}  \]
    
  • 将SGD过程中得到的梯度，按照泰勒公式睁开
    
    
    
    
  • 近似表现MAML梯度（\(U_i\) 表现在第\(i\)个minibatch上对参数向量的更新利用）
    
    
    
    
  • 领头阶睁开
    
    
    
    
  • 当k=2时，三者的一样寻常表现情势为：
    \[  \begin{align}  &g_{MAML}=\bar{g_2}-\alpha\bar{H_2}\bar{g_1}-\alpha\bar{H_1}\bar{g_2}+O(\alpha^2)\\  &g_{MAML}=g_2=\bar{g_2}-\alpha\bar{H_2}\bar{g_1}+O(\alpha^2)\\  &g_{Reptile}=g_1+g_2=\bar{g_1}+\bar{g_2}-\alpha\bar{H_2}\bar{g_1}+O(\alpha^2)\\  \end{align}  \]
    

    此中：
    

    
    
    • 雷同于\(\bar{g_1}\quad \bar{g_2}\)的项就是领头项，用于最小化连合训练丧失；
      
    • 雷同于\(\bar{H_2}\bar{g_1}\)的项就是次领头项，作用是最大化差别批次数据上得到的梯度的内积。
      

    
    
  • 在举行minibatch采样，取三种梯度的盼望时，上述两种领头项分别用AvgGrad和AvgGradInner表现（k=2）：
    
    
    
    
    
    
    
  • 三种算法梯度的盼望表现情势可以化为：
    
    
    
    
  • 扩展到k>2的情况有：
    
    
    
    

    
    

    
    
    • 可以看到三者AvgGradInner与AvgGrad之间的系数比的关系是：MAML > FOMAML > Retile。
      
    • 这个比例与步长\(\alpha\)，迭代次数\(k\) 正干系。
      

    
    
  
  
• 找到一个接近全部解流形（Solution Manifolds）的点
  

  直觉：
  

  
  
  • Reptile收敛于一个解，这个解在欧式空间上与每个任务的最优解的流形接近。
    
    
    
    

  
  
  
  
  • 用 \(\phi\) 表现网络初始化，\(\mathcal{W_{T}}\) 表现任务\(\mathcal{T}\)上的最优参数集。优化过程的终极目的是找到一个\(\phi\)使得其与全部任务的\(\mathcal{W_{T}}\) 之间的隔断最小。
    \[  \min_{\phi}\mathbb{E}_{\mathcal{T}}[\frac{1}{2} D(\phi,\mathcal{W_T})^2]  \]
    
  • 对参数\(\phi\)的梯度为：
    
    
    
    
  • 在Reptile中每一次迭代相当于采样一个任务然后在上面实验一侧SGD更新。
    
    
    
    
  • 实际情况下，很难直接盘算出\(P_{\mathcal{W_T}}(\phi)\)，纵然得\(L_T\) 取得最小值的p。因此在Reptile中，用初始化参数\(\phi\)在\(L_T\) 上实验k步梯度降落后得到的结果来代替最优化参数\(\mathcal{W^{\star}_{T}(\phi)}\)。
    
  
  

• 仅利用一个批次的数据产生的梯度的结果并不显著，由于相当于让模子用见到过的少量的数据去优化全部任务。
  
• 举行了两步更新的Reptile（绿线）的结果要显着不如举行了两步更新的FOMAML（红线），由于Reptile在AvgGradInner上的权紧张小于FOMAML。
  
• 随着mini-batch数目的增多，全部算法的性能也在提升。通过同时利用多步的梯度更新，Reptile的体现要比仅利用末了一步梯度更新的FOMAML的体现好。
  

• shared-tail（共尾）：末了一个内循环的数据来自以前内循环批次的数据
  
• separate-tail（分尾）：末了一个内循环的数据与以前内循环批次的数据差别
  

• 通过用泰勒级数近似表现更新过程，发现SGD主动给出了与MAML盘算的二阶项雷同的项。这一项调解初始权重，以最大限度地增长同一任务中差别小批量梯度之间的点积，从而增大模子的泛化本领。
  
• Reptile通过利用多次梯度更新，找到了一个接近全部最优解流形的点。