Dynamic programming (DP) solves a variety of structured combinatorial problems by iteratively breaking them down into smaller subproblems. In spite of their versatility, DP algorithms are usually non-differentiable, which hampers their use as a layer in neural networks trained by backpropagation. To address this issue, we propose to smooth the max operator in the dynamic programming recursion, using a strongly convex regularizer. This allows to relax both the optimal value and solution of the original combinatorial problem, and turns a broad class of DP algorithms into differentiable operators. Theoretically, we provide a new probabilistic perspective on backpropagating through these DP operators, and relate them to inference in graphical models. We derive two particular instantiations of our framework, a smoothed Viterbi algorithm for sequence prediction and a smoothed DTW algorithm for time-series alignment. We showcase these instantiations on two structured prediction tasks and on structured and sparse attention for neural machine translation.


翻译:动态编程( DP) 解决了各种结构化组合问题, 反复将其拆分为较小的子问题 。 尽管其多功能性, DP 算法通常没有差异性, 这阻碍了它们作为神经网络中一个层的使用, 而这些神经网络则通过反向反向分析来培训 。 为了解决这个问题, 我们提议用一个强大的 convex 常规化器来平滑动态编程循环操作员。 这样可以放松原始组合问题的最佳价值和解决方案, 并将广泛的DP 算法转换为不同的操作员 。 从理论上讲, 我们提供了一个新的关于通过这些 DP 操作员进行反向转换的概率视角, 并将它们与图形模型中的推断联系起来 。 我们从我们的框架中得出了两个特殊的瞬间点, 一种是平滑的 Viterbi 算法, 一种是序列预测的平滑的 Viterbi 算法, 一种是时间序列校准的光滑的 DTW 算法。 我们用两种结构化的预测任务来展示这些即时序转换, 以及结构化和微的神经机转换的注意 。

56
下载
关闭预览

相关内容

因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
专知会员服务
59+阅读 · 2020年3月19日
自动结构变分推理,Automatic structured variational inference
专知会员服务
38+阅读 · 2020年2月10日
【新书】贝叶斯网络进展与新应用,附全书下载
专知会员服务
118+阅读 · 2019年12月9日
机器学习入门的经验与建议
专知会员服务
89+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
论文浅尝 | Interaction Embeddings for Prediction and Explanation
开放知识图谱
11+阅读 · 2019年2月1日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
自然语言处理(二)机器翻译 篇 (NLP: machine translation)
DeepLearning中文论坛
10+阅读 · 2015年7月1日
Arxiv
7+阅读 · 2019年5月31日
Arxiv
26+阅读 · 2018年2月27日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
论文浅尝 | Interaction Embeddings for Prediction and Explanation
开放知识图谱
11+阅读 · 2019年2月1日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
自然语言处理(二)机器翻译 篇 (NLP: machine translation)
DeepLearning中文论坛
10+阅读 · 2015年7月1日
Top
微信扫码咨询专知VIP会员