Lambda calculus meets machine learning

Abstract

Neural Networks are usually used in the context of machine learning to solve statistical problems and calculate approximations. However, its use for symbolic learning has been increasing in the past years, placing them in the Neurosymbolic realm. To study the capabilities of Neural Networks in this kind of task, several works have already explored the ability of these networks to learn mathematical operations, such as addition and multiplication, logic inference, such as theorem provers, and even execution of computer programs. The latter is known to be a task too complex for neural networks. Therefore, the results were not always successful and often required the introduction of biased elements in the learning process, in addition to restricting the scope of possible programs to be executed. In this work, we will be interested in studying the ability of Neural Networks to learn how to execute programs as a whole. To achieve this, we propose a di erent approach. Instead of using an imperative pro gramming language with complex structures, we use the Lambda Calculus (λ-Calculus), a simple yet Turing-Complete mathematical formalism, which serves as the basis for modern functional languages. As the execution of a program in λ-Calculus is based on reductions, we will show that learning how to perform these reductions is enough to execute any program.

Redes neurais são geralmente utilizadas para resolver problemas estatísticos e calcular aproximações. No entanto, seu uso para aprendizagem simbólica vem aumentando nos últimos anos, colocando-as no domínio Neuro-Simbólico. Para estudar as capacidades das Redes Neurais nesse tipo de tarefa, vários trabalhos já exploraram a capacidade des sas redes em aprender operações matemáticas, como adição e multiplicação, inferências lógicas, como provadores de teoremas, e até execução de programas de computador. Esta última tarefa é conhecida por ser muito complexa para redes neurais. Portanto, nem sem pre os resultados são bem-sucedidos, e muitas vezes exigem a introdução de elementos enviesados no aprendizado, além de restrição no escopo de programas a serem executa dos. Neste trabalho, estaremos interessados em estudar a capacidade das Redes Neurais em aprender a executar programas como um todo. Para isso, propomos uma abordagem diferente. Ao invés de usar uma linguagem de programação imperativa, com estruturas complexas, usamos o Lambda Calculus (λ-Calculus), um formalismo matemático sim ples, mas Turing-Completo, que serve de base para as linguagens funcionais modernas. Como a execução de um programa em λ-Calculus é baseada em reduções, mostraremos que basta aprender a fazer essas reduções para que possamos executar qualquer pro grama.