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

AiTechYun

编辑：chux

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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