我们研究了具有从少数潜在状态产生的丰富观察的情节MDP中的探索问题。在某些可识别性假设下,我们演示了如何通过一系列回归和聚类步骤来诱导地估计从观察到状态的映射 - 其中先前解码的潜在状态为后来的回归问题提供标签 - 并用它来构建良好的勘探政策。我们对学习状态解码函数和探索策略的质量提供有限样本保证,并通过对一类硬探索问题的经验评估来补充我们的理论。我们的方法成倍地提高了超过$ Q $ -learning的水平,即使在$ Q $ -learning已经进入潜伏状态时也是如此。
translated by 谷歌翻译
最近的作品揭示了为什么深网适合任何数据的神秘性,并且尽管非常过度参数化但仍然概括。本文分析了具有randominitialization的简单2层ReLU网络的训练和推广,并对近期工作提供了以下改进:(i)使用比最近的论文更严格的训练速度表征,解释为什么用随机标签训练神经网络导致最初在[Zhang et al。 ICLR'17。 (ii)使用数据相关复杂性度量,与网络大小无关的泛化界限。我们的衡量标准明确区分了MNIST和CIFAR上的随机标签和真实标签,如实验所示。此外,近期报纸要求样本复杂度随着大小增加(缓慢),而我们的示例复杂度完全独立于网络大小。 (iii)通过梯度下降网络实现2层ReLU的广泛平滑函数的可学习性。关键思想是通过相关内核的属性跟踪训练和概括的动态。
translated by 谷歌翻译
我们证明对于一个$ L $层完全连接的线性神经网络,如果每个隐藏层的宽度是$ \ tilde \ Omega(L \ cdot r \ cdot d _ {\ mathrm {out}} \ cdot \ kappa ^ 3 )$,其中$ r $和$ \ kappa $是输入数据的排名和条件数,$ d _ {\ mathrm {out}} $是输出维度,高斯随机初始化的梯度下降收敛于全局最小值线性率。找到$ \ epsilon $ -sopoptimal解决方案的迭代次数是$ O(\ kappa \ log(\ frac {1} {\ epsilon}))$。对于宽深线性网络的总运行时间,我们的多项式上界和窄线性神经网络的$ \ exp \ left(\ Omega \ left(L \ right)\ right)$下界[Shamir,2018]一起证明了宽层对于优化深度模型是必要的。
translated by 谷歌翻译
可以从限制常微分方程(ODE)的角度研究基于梯度的优化算法。由于成熟的ODE不能区分两种根本不同的算法--Nesterov的强凸函数加速梯度法(NAG-SC)和Polyak的重球法 - 我们研究了一种产生高分辨率ODE的替代限制过程。我们证明了这些ODEs允许一个一般的Lyapunov函数框架,用于分析连续和离散时间的收敛。我们还表明这些ODE是底层算法的更准确的替代品;特别是,他们不仅区分NAG-SC和Polyak的重球方法,而且它们允许识别我们称之为“梯度校正”的术语,该术语在NAG-SC中存在但在重球法中不存在并且是负责的对于这两种方法收敛的定性差异。我们还使用高分辨率ODE框架来研究Nesterov的(非强)凸函数的加速梯度法,揭示了迄今未知的结果--- NAG-C在倒数立方时最小化平方梯度范数。最后,通过修改NAG-C的高分辨率ODE,我们获得了新的优化方法,这些方法被证明可以保持NAG-C对于平滑凸函数的加速收敛速度。
translated by 谷歌翻译
我们研究了梯度下降对学习多层齐次函数所施加的隐式正则化,包括具有线性,ReLU或Leaky ReLU激活的前馈全连通和卷积深度神经网络。我们严格证明梯度流(即有限步长内的梯度下降)有效地强制执行不同层次的平方之间的差异在没有任何明确的规则化的情况下保持不变。该结果意味着如果权重最初很小,则梯度流自动平衡所有层的大小。利用adiscretization参数,我们分析了具有正步长的梯度下降,得到了非凸低阶非对称矩阵分解问题,没有任何正则化。受我们对梯度流的研究结果的启发,我们证明了步长为$ \ eta_t = O \ left(t ^ { - \ left(\ frac12 + \ delta \ right)} \ right)$($ 0 <\ delta \ le \)的梯度下降frac12 $)自动平衡两个低秩因子并收敛到有界全局最优。此外,对于秩为1美元的非对称矩阵分解,我们给出了更精细的分析,显示梯度下降,恒定步长在全球线性速率下收敛到全局最小值。我们认为,在学习同质模型时检验一阶算法所假设的不变性的想法可以作为研究深度模型学习优化的基本构件。
translated by 谷歌翻译
A widespread folklore for explaining the success of Convolutional Neural Networks (CNNs) is that CNNs use a more compact representation than the Fully-connected Neural Network (FNN) and thus require fewer training samples to accurately estimate their parameters. We initiate the study of rigorously characterizing the sample complexity of estimating CNNs. We show that for an m-dimensional convolutional filter with linear activation acting on a d-dimensional input, the sample complexity of achieving population prediction error of is r Opm{ 2 q 2 , whereas the sample-complexity for its FNN counterpart is lower bounded by Ωpd{ 2 q samples. Since, in typical settings m ! d, this result demonstrates the advantage of using a CNN. We further consider the sample complexity of estimating a one-hidden-layer CNN with linear activation where both the m-dimensional convolu-tional filter and the r-dimensional output weights are unknown. For this model, we show that the sample complexity is r O ` pm`rq{pm`pm`rq{ 2 ˘ when the ratio between the stride size and the filter size is a constant. For both models, we also present lower bounds showing our sample complexities are tight up to logarithmic factors. Our main tools for deriving these results are a localized empirical process analysis and a new lemma characterizing the convolutional structure. We believe that these tools may inspire further developments in understanding CNNs.
translated by 谷歌翻译
我们提供了关于过度参数化在学习神经网络中有效的原因的新理论见解。对于具有二次激活和$ n $训练数据点的$ k $隐藏节点浅网络,我们只要$ k \ ge \ sqrt {2n} $显示,过度参数化使本地搜索算法能够找到\ emph {global}一般情况下,尽管参数的数量可能超过样本量,但使用Rademacher复杂度理论,我们表明,如果数据是从常规分布中采样的,那么解决方案也可以很好地推广。高斯。为了证明$ k \ ge \ sqrt {2n} $,损失函数有benignlandscape属性,我们采用平滑分析的想法,这可能有其他应用于研究神经网络的损失表面。
translated by 谷歌翻译
我们考虑学习具有非重叠卷积层和ReLU激活的单隐层神经网络的问题,即$ f(\ mathbf {Z},\ mathbf {w},\ mathbf {a})= \ sum_j a_j \ sigma(\ mathbf {w} ^ T \ mathbf {Z} _j)$,其中卷积权重$ \ mathbf {w} $和输出权重$ \ mathbf {a} $是要学习的参数。当标签是具有固定权重$(\ mathbf {w} ^ *,\ mathbf {a} ^ *)$的相同架构的教师网络的输出时,我们用高斯输入$ \ mathbf {Z} $证明,有一个有害的局部最小化器。令人惊讶的是,在存在虚假局部最小化的情况下,随机初始化权重的权重归一化的梯度下降仍然可以证明恢复具有恒定概率的真实参数,可以通过多次重启来提升到1美元的概率。 Wealso表明,在恒定的概率下,相同的程序也可以归结为虚假的局部最小值,表明局部最小值在梯度下降的动力学中起着重要的作用。此外,水平分析表明梯度下降动力学有两个阶段:它开始缓慢,但在几次迭代后收敛得更快。
translated by 谷歌翻译
能够从大型自由文本语料库中自动发现同义实体,对结构化知识发现具有变革性的影响。现有作品要么需要结构化注释,要么无法有效地合并上下文信息,从而降低信息使用效率。在本文中,我们提出了一个从无文本语料库中进行同义词发现的框架,没有结构化注释。作为同义词发现的关键组件之一,我们引入了一个新的神经网络模型SynonymNet来确定两个给定的实体是否是彼此的同义词.SynonymNet不使用实体特征,而是利用提到实体的多个内容,并通过双边匹配模式比较上下文级别相似性​​来确定同义性。实验结果表明,所提出的模型在通用和特定领域的同义词数据集上实现了最先进的结果:Wiki + Freebase,PubMed + UMLS和MedBook +与最佳基线方法相比,MKG在曲线下面积(AUC)和平均平均精度(MAP)方面的改善率高达4.16%。
translated by 谷歌翻译
能够将单词识别为时段并检测话语的意图是自然语言理解中的一个热门问题。现有工作要么以流水线方式分别处理时隙填充和意图检测,要么采用顺序标记时隙的联合模型,同时总结容量级意图而不明确保留字,时隙和意图之间的分层关系。为了利用语义层次结构进行有效建模,我们提出了一种基于胶囊的神经网络模型,该模型通过动态路由协议模式实现了插槽填充和意图检测。提出了一种重新路由模式,以使用推断的意图表示来进一步激励槽填充性能。两个真实世界数据集的实验表明,与其他替代模型架构相比,我们的模型的有效性,以及现有的自然语言理解服务。
translated by 谷歌翻译