加州大学研究团队开发新型深度学习算法,机器自行解决复杂魔方问题,无需人工协助

加州大学研究团队开发新型深度学习算法,机器自行解决复杂魔方问题,无需人工协助

加州大学研究团队最近开发了一种新型的深度学习算法DeepCube,在没有任何人工协助的情况下机器自学如何解魔方。

这是个意义重大的里程碑,因为新方法解决了计算机科学中的一个重要问题:如何在最少的帮助下让机器解决复杂的问题。

魔方是由匈牙利发明家Erno Rubik于1974年开发的一种立体拼图,这个难题一直引起计算机科学家和数学家的极大兴趣。一个问题就是从任何位置解决问题所需的最小步数。2014年的答案是26。

另一个常见的挑战是设计可以从任何位置解决立方体的算法。但是尝试自动化这个过程都依赖于人类手工制作的算法。

最近,计算机科学家们试图找到机器自己解决问题的方法。一个想法是使用像棋和围棋这样的游戏非常成功的相同方法。

加州大学研究团队开发新型深度学习算法,机器自行解决复杂魔方问题,无需人工协助

在这些场景中,深度学习机器被赋予游戏规则,然后与自己对抗。至关重要的是,它在每一步都会根据它的表现得到奖励。这个奖励过程非常重要,因为它有助于机器区分好坏。换句话说,这有助于机器学习。

但是这在许多现实世界中并不适用,因为奖励通常很难确定。

例如,魔方的随机变化不容易获得奖励,因为很难判断新配置是否更接近解决方案。一系列随机轮流可以持续很长时间而不会达成解决方案,所以最终状态奖励只能很少提供。

在国际象棋中,相比之下,有一个相对较大的搜索空间,但每一步都可以相应地进行评估和奖励。魔方的情况并非如此。

加州大学欧文分校的Stephen McAleer及其同事开创了一种新的深度学习技术,称为“自主学习迭代(Autodidactic iteration)”,可以让机器自行解决魔方的问题,而无需人工协助。已经掌握的技巧是找到机器创建自己的奖励系统的方法。

这也是它的工作原理。给定一个未解决的多维数据集,机器必须决定具体的移动是否改进了现有的配置。要做到这一点,它必须能够评估移动。

自主学习迭代通过从完成的多维数据集开始,然后向后查找与提议的移动相似的配置。这个过程并不完美,但是深度学习可以帮助系统找出哪些动作通常比其他的更好。

经过训练后,该网络将使用标准搜索树来搜索每个配置建议的移动。

结果证明此算法性能非常好。McAleer指出,“我们的算法能够解决100%的随机方块,同时实现30次移动的中位数,小于或等于使用人类领域知识的解决者的步数。”

这很有趣,因为它对深度学习所面临的各种其他任务有影响,包括诸如推箱子之类的难题,以及素数分解等问题。

的确,McAleer他们还有其他目标:“我们正在努力扩展这种方法,以寻找其他组合优化问题的近似解决方案,例如预测蛋白质三级结构。”

这些问题是否适合这种方法尚不清楚。McAleer和Co认为他们的方法是对问题进行推理的一种形式。他们指出,推理的一个定义是:“用代数方法处理先前获得的知识以便回答一个新的问题。”

这正是他们的算法DeepCube所做的。相比之下,传统的深度学习机器只是识别某些图案。“DeepCube能够自学如何推理,以便用纯粹的强化学习来解决只有一种奖励状态的复杂环境。”

论文网址:arxiv.org/pdf/1805.07470.pdf

本文为ATYUN(www.atyun.com)编译作品,ATYUN专注人工智能
请扫码或微信搜索ATYUN订阅号及时获取最新内容

发表评论