How to use deep learning to break sudoku? What is RRN? Take a look at this article and learn about it.
1. Relationship between reasoning
What is relational reasoning? Think of the picture above, don’t think of this as a sphere, a cube, etc. We can think about it in terms of the millions of numbers that make up the pixel values of the image or the angles of all the edges of the image or we can think about each 10×10 pixel region.
Try answering the following question: “What is the size of the cylinder left by the brown metal object to the left of the large sphere?” This is an example problem from the CLEVR dataset. To answer it, you need to consider the positions of objects relative to each other. This object – and interaction-centric thinking is called relational reasoning, and it’s a central part of human intelligence.
Deep neural networks are very good at recognizing objects, but when it comes to theirinteractiveWhen it comes to reasoning, even the most advanced neural networks can do little more.
For example, the existing convolutional network can easily identify each object in the image above, but because it requires inference about objects about each other, it does not answer the question we just mentioned.
2. network
Adam Santoro and his collaborators have proposed a network of relationships (RN). This is a very simple module that can add relational reasoning capabilities to any neural network. They added an RN to a standard convolutional network and trained on the CLEVR dataset to achieve superhuman performance. They also used it for BaBi, a text problem solving task, and solved 18 out of 20 tasks.
RN is an important step forward in deep learning, but it has its limitations. It is constructed in such a way that each identified object interacts only once with the other identified objects, after which the network must give an answer. This is A constraint of RN, because it cannot deduce the resulting interaction, that is, object A affects object B, which in turn affects object C, and so on. In RN, object A must affect object C directly or not at all. So that’s kind of cute.
3.Recurrent Relation Networks
To solve this limitation, we introduce recursive relational networks (RRN). RRNS perform multiple steps rather than just a single step of associative reasoning. At each step, each object is influenced by other objects, taking into account its own previous state. This allows interactions to propagate from one object to another, forming complex chains of interactions.
4.Practical experience: battle sudoku
To show that RRN can solve problems that require very complex relational reasoning, we use it to solve Sudoku puzzles.
Now, there are many algorithms to solve Sudokus. RRN differs from these traditional algorithms in two important ways:
1. This is a neural network module that learns algorithms from data, not by hand.
2. It can be added to any other neural network for end-to-end training and give the neural network a complex relational reasoning capability.
For those unfamiliar with the Sudoku puzzle, it’s a numerical puzzle with 81 cells in a 9×9 grid. Each cell is empty or contains a number (1-9) from the beginning. Our goal is to fill each empty cell with a number so that each column, row, and 3×3 non-overlapping number contains numbers 1 through 9. See the two images below, a relatively simple Sudoku: 30 given cells and the solution in red.
You can’t extrapolate Sudoku’s solution step by step. It requires many steps of method deduction, intermediate results, and possibly trying several parts of the solution before finding the right one.
We trained an RRN to solve Sudokus by considering one object per cell that affects every other cell in the same row, column, and box. We didn’t tell it any strategy or give it any other hints. The neural network learned a powerful strategy, and even the most difficult sudoku had only 17 responses, a success rate96.6%. For comparison, other neural network structures failed to solve any of these problems, despite having more parameters and being trained for longer periods.
At each step, RRN outputs a probability distribution for each cell on 1-9 numbers, indicating which number the network thinks should be in that cell.
5. Reasoning simple text
This is a simple problem in the Barbie data set.
Mary is drinking milk there.
John went to the bedroom.
Sandra went back into the kitchen.
Mary walked down the corridor.
Where’s the milk?
We also trained RRN on the BaBi dataset, and we solved 19/20 tasks. RN, by contrast, also solved 19/20 of the most advanced sparse differentiable neural computers. It’s worth noting that RRN spent about 24 hours training on four Gpus, while RN spent several days training on 10 Gpus. We think this is because RRN is designed to solve problems that require more than one step of reasoning.
6. conclusion
Recursive relational network (RRN) is a general-purpose module that can enhance the performance of any neural network model with powerful relational reasoning capabilities.
We think relational reasoning is important for many tasks. For example, playing a game, Go or Starcraft II, requires identifying and reasoning about objects in the game in order to predict the long-term consequences of actions. Another example is self-driving cars. To drive safely, it is necessary to identify related objects such as cars, cyclists, stop signs, etc., and why they will interact with each other.
This article is recommended by Beijing Post @ Love coco – Love life teacher, translated by Ali Yunqi Community organization.
It’s a Recurrent Relational Networks story.
The article is briefly translated. For more details, please check it outThe originalwen
The original link