Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks

Deep neural networks are powerful machines for visual pattern recognition,\nbut reasoning tasks that are easy for humans may still be difficult for neural\nmodels. Humans possess the ability to extrapolate reasoning strategies learned\non simple problems to solve harder examples, often by thinking for longer. For\nexample, a person who has learned to solve small mazes can easily extend the\nvery same search techniques to solve much larger mazes by spending more time.\nIn computers, this behavior is often achieved through the use of algorithms,\nwhich scale to arbitrarily hard problem instances at the cost of more\ncomputation. In contrast, the sequential computing budget of feed-forward\nneural networks is limited by their depth, and networks trained on simple\nproblems have no way of extending their reasoning to accommodate harder\nproblems. In this work, we show that recurrent networks trained to solve simple\nproblems with few recurrent steps can indeed solve much more complex problems\nsimply by performing additional recurrences during inference. We demonstrate\nthis algorithmic behavior of recurrent networks on prefix sum computation,\nmazes, and chess. In all three domains, networks trained on simple problem\ninstances are able to extend their reasoning abilities at test time simply by\n"thinking for longer."\n