Search

This paper introduces a new learning-based approach for approximately solving the Kidney-Exchange Problem (KEP), an NP-hard problem on graphs. The problem consists of, given a pool of kidney donors and patients waiting for kidney donations, optimally selecting a set of donations to optimize the quantity and quality of transplants performed while respecting a set of constraints about the arrangement of these donations. The proposed technique consists of two main steps: the first is a Graph Neural Network (GNN) trained without supervision; the second is a deterministic non-learned search heuristic that uses the output of the GNN to find paths and cycles. To allow for comparisons, we also implemented and tested an exact solution method using integer programming, two greedy search heuristics without the machine learning module, and the GNN alone without a heuristic. We analyze and compare the methods and conclude that the learning-based two-stage approach is the best solution quality, outputting approximate solutions on average 1.1 times more valuable than the ones from the deterministic heuristic alone., Comment: 12 pages

Over the last decades, deep neural networks based-models became the dominant paradigm in machine learning. Further, the use of artificial neural networks in symbolic learning has been seen as increasingly relevant recently. To study the capabilities of neural networks in the symbolic AI domain, researchers have explored the ability of deep neural networks to learn mathematical constructions, such as addition and multiplication, logic inference, such as theorem provers, and even the execution of computer programs. The latter is known to be too complex a task 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 analyze the ability of neural networks to learn how to execute programs as a whole. To do so, we propose a different approach. Instead of using an imperative programming language, with complex structures, we use the Lambda Calculus ({\lambda}-Calculus), a simple, but Turing-Complete mathematical formalism, which serves as the basis for modern functional programming languages and is at the heart of computability theory. We will introduce the use of integrated neural learning and lambda calculi formalization. Finally, we explore execution of a program in {\lambda}-Calculus is based on reductions, we will show that it is enough to learn how to perform these reductions so that we can execute any program. Keywords: Machine Learning, Lambda Calculus, Neurosymbolic AI, Neural Networks, Transformer Model, Sequence-to-Sequence Models, Computational Models, Comment: Keywords: Machine Learning, Lambda Calculus, Neurosymbolic AI, Neural Networks, Transformer Model, Sequence-to-Sequence Models, Computational Models

Encoder-decoder architectures are prominent building blocks of state-of-the-art solutions for tasks across multiple fields where deep learning (DL) or foundation models play a key role. Although there is a growing community working on the provision of interpretation for DL models as well as considerable work in the neuro-symbolic community seeking to integrate symbolic representations and DL, many open questions remain around the need for better tools for visualization of the inner workings of DL architectures. In particular, encoder-decoder models offer an exciting opportunity for visualization and editing by humans of the knowledge implicitly represented in model weights. In this work, we explore ways to create an abstraction for segments of the network as a two-way graph-based representation. Changes to this graph structure should be reflected directly in the underlying tensor representations. Such two-way graph representation enables new neuro-symbolic systems by leveraging the pattern recognition capabilities of the encoder-decoder along with symbolic reasoning carried out on the graphs. The approach is expected to produce new ways of interacting with DL models but also to improve performance as a result of the combination of learning and reasoning capabilities.

Current advances in Artificial Intelligence (AI) and Machine Learning (ML) have achieved unprecedented impact across research communities and industry. Nevertheless, concerns about trust, safety, interpretability and accountability of AI were raised by influential thinkers. Many have identified the need for well-founded knowledge representation and reasoning to be integrated with deep learning and for sound explainability. Neural-symbolic computing has been an active area of research for many years seeking to bring together robust learning in neural networks with reasoning and explainability via symbolic representations for network models. In this paper, we relate recent and early research results in neurosymbolic AI with the objective of identifying the key ingredients of the next wave of AI systems. We focus on research that integrates in a principled way neural network-based learning with symbolic knowledge representation and logical reasoning. The insights provided by 20 years of neural-symbolic computing are shown to shed new light onto the increasingly prominent role of trust, safety, interpretability and accountability of AI. We also identify promising directions and challenges for the next decade of AI research from the perspective of neural-symbolic systems., Comment: 37 pages

Computational learning theory states that many classes of boolean formulas are learnable in polynomial time. This paper addresses the understudied subject of how, in practice, such formulas can be learned by deep neural networks. Specifically, we analyze boolean formulas associated with model-sampling benchmarks, combinatorial optimization problems, and random 3-CNFs with varying degrees of constrainedness. Our experiments indicate that: (i) neural learning generalizes better than pure rule-based systems and pure symbolic approach; (ii) relatively small and shallow neural networks are very good approximators of formulas associated with combinatorial optimization problems; (iii) smaller formulas seem harder to learn, possibly due to the fewer positive (satisfying) examples available; and (iv) interestingly, underconstrained 3-CNF formulas are more challenging to learn than overconstrained ones. Such findings pave the way for a better understanding, construction, and use of interpretable neurosymbolic AI methods.

The study and understanding of human behaviour is relevant to computer science, artificial intelligence, neural computation, cognitive science, philosophy, psychology, and several other areas. Presupposing cognition as basis of behaviour, among the most prominent tools in the modelling of behaviour are computational-logic systems, connectionist models of cognition, and models of uncertainty. Recent studies in cognitive science, artificial intelligence, and psychology have produced a number of cognitive models of reasoning, learning, and language that are underpinned by computation. In addition, efforts in computer science research have led to the development of cognitive computational systems integrating machine learning and automated reasoning. Such systems have shown promise in a range of applications, including computational biology, fault diagnosis, training and assessment in simulators, and software verification. This joint survey reviews the personal ideas and views of several researchers on neural-symbolic learning and reasoning. The article is organised in three parts: Firstly, we frame the scope and goals of neural-symbolic computation and have a look at the theoretical foundations. We then proceed to describe the realisations of neural-symbolic computation, systems, and applications. Finally we present the challenges facing the area and avenues for further research., Comment: 58 pages, work in progress

A existência de publicações de alta qualidade é um dos indicadores da maturidade de uma área de pesquisa. O Instituto de Informática da UFRGS vem, então, trabalhando arduamente para conquistar um espaço de reconhecimento nacional para a Revista de Informática Teórica e Aplicada (RITA). Nosso objetivo é continuar no caminho do aperfeiçoamento e qualificação desta publicação. Atualmente, já estamos com uma publicação ininterrupta da Revista por 18 anos, desde 1989. Este é um caso de sucesso nas publicações universitárias brasileiras, nesta trilha de qualidade e de ampla difusão do conhecimento estamos lançando a Edição Eletrônica da Revista de Informática Teórica e Aplicada, sendo este o primeiro número com edição em papel e eletrônica.

Esta edição da Revista RITA - Revista de Informática Teórica e Aplicada é dedicada à área de Realidade Virtual, contendo artigos estendidos escritos a partir dos cinco melhores trabalhos apresentados no SVR 2008 – Brazilian Symposium on Virtual and Augmented Reality, realizado em maio de 2008, em João Pessoa, Paraíba. Para a organização desta edição, contamos com a participação dos coordenadores do Comitê de Programa do evento, professores Alberto Raposo, da Pontifícia Universidade Católica do Rio de Janeiro, e Judith Kelner, da Universidade Federal de Pernambuco, na qualidade de Editores Convidados. O SVR, promovido pela Sociedade Brasileira de Computação, reúne anualmente a comunidade brasileira com interesse em realidade virtual, realidade aumentada e áreas correlatas. Esta é a primeira ocasião em que artigos do SVR são apresentados em versão estendida na RITA. O Comitê de Programa do evento realizou a seleção dos melhores trabalhos, os quais foram estendidos pelos autores e submetidos a uma nova revisão, coordenada pelos Editores Convidados. Esperamos que essa edição da RITA contribua para a divulgação mais ampla dos trabalhos realizados nas áreas cobertas pelo SVR e incentive estudantes e pesquisadores à submissão dos resultados de suas pesquisas tanto à RITA como às próximas edições do Simpósio. A todos, editores convidados, revisores e autores, gostaríamos de dirigir nossos agradecimentos, por contribuírem com este número especial da Revista RITA. Luis C. Lamb José Palazzo M. Oliveira Lisandro Z. Granville Instituto de Informática, Universidade Federal do Rio Grande do Sul Porto Alegre, RS, Brasil