Deep learning: from Sudoku to protein design

Published on 17 July 2023

Artificial intelligence (AI) language models impress with their ability to respond in a coherent, structured way. But when it comes to reasoning and logic, they are still limited. For example, when ChatGPT is asked to solve a grid of the famous Sudoku puzzle, the solutions it comes up with do not respect the rules, and sometimes even modify the original numbers in the grid.

This difficulty with logical reasoning is not specific to language models. In fact, it is common to most neural networks. They are very good at extracting patterns from data, but much weaker at reasoning from data. But combined with automatic reasoning methods, a general AI should be capable of both learning and reasoning, just like humans do.

Learning to play Sudoku

For automated reasoning, solving hard Sudoku grids is a trivial task when the rules are given. But when it comes to learning them, it is a two-stage process. First, the AI must deduce the rules by observing examples of completed puzzles, then it must use these rules to complete new puzzles. Scientists from the Applied Mathematics and Informatics research unit (MIAT) and Toulouse Biotechnology Institute (TBI) have therefore combined two types of AI to learn how to play Sudoku: a neural network to learn the rules from examples, and a prover to apply these rules to solving new puzzles.

Their hybrid method learns fast (in 15 minutes!) and is minimalist: it requires just 200 examples of complete grids, a fraction of what other approaches require. Plus, it is transparent: the decision made by the discrete prover can be understood by analyzing which rules have been learned. This ’window’ into the process allows for better control and understanding.

From Sudoku to protein design

Proteins are macro-molecules essential to any kind of life as they fulfill many biological and biochemical functions in all living organisms. Designing new proteins has applications in health and green chemistry, among others.

From the proof-of-principle obtained on Sudoku grid solving, scientists have exploited its analogy with protein design. Seen as a "puzzle" in which the aim is to place atoms in space, learning protein models leads to learning its "rules of the game", which can then be used by automatic reasoning tools to design new proteins.

This research combines intuitive recognition of deep learning with meticulous logic of automated reasoning. In addition to its speed and transparency, the real strength of the method developed is its ability to model a variety of problems, from solving Sudoku to real-life issues such as designing new proteins.