用机器学习近似 NP 困难问题
在 2017-10-02 发布于 播客 分类
本期嘉宾：戴涵俊
话题：用机器学习解决一类NP困难问题
计算机领域有一类困扰了科学家很久的问题，叫做NP困难问题。NP困难问题在生活中很常见，例如物流、城市规划等等都可以找到NP困难问题的原型。但这类问题至今都没有有效的、多项式时间内的解。计算机理论领域的研究者从搜索、构造等角度给出过很多种近似解法。人工智能在这类问题中会有怎样的应用呢？机器学习算法如何从多个小问题中找规律来解决这一大类问题呢？AlphaGo背后的强化学习算法又是怎么和这个问题联系起来的呢？我们以NP困难中的最小点覆盖问题为例，介绍机器学习算法在NP困难的组合优化问题上的应用。
收听节目
提到的一些内容
- 戴涵俊个人主页
- 节目刚开始时我们提到了一个NP困难的问题：旅行推销员问题。
- 我们主要介绍的最小点覆盖问题也是NP困难问题中的一类
- 戴涵俊介绍的用强化学习解最小点覆盖问题的方法主要基于: Learning Combinatorial Optimization Algorithms over Graphs
- AlphaGo所用的强化学习算法和戴涵俊介绍的强化学习算法都是通过深度神经网络实现的，称为Deep Reinforcement Learning / Deep Q-Learning
- 最后提到的把图用向量来表示的graph embedding方法的相关文章：Discriminative Embeddings of Latent Variable Models for Structured Data
阅读文字版
- 点击这里阅读本期节目文字版
关注德塔赛
谢谢收听！