Departamento de Computación

La lógica de Markov es un lenguaje para representar conocimiento que combina lógica y probabilidades, creando un sistema eficiente de inferencia y aprendizaje. La inferencia implica sustitución y búsqueda. La sustitución transforma la representación lógica en clausulas proposicionales con pesos que codifican una Red Markov, formando la red lógica de Markov (MLN) sustituida. La búsqueda sobre una MLN sustituida provee de inferencia probabilística. El aprendizaje determina los pesos de las clausulas o su estructura, aplicando inferencia repetidamente. Como el espacio de soluciones de una MLN puede crecer rápidamente, su procesamiento se vuelve muy costoso, por lo que se ha buscado mejorarlo. El paralelismo en multinúcleos se utiliza en sistemas para MLNs como Tuffy y RockIt, pero no conocemos ningún otro trabajo basado en el paralelismo masivo que las Unidades de Procesamiento Gráfico (GPUs) proveen.

Esta tesis presenta el diseño, implementación y evaluación de plataformas paralelas para MLNs en GPUs. Diseñamos la paralelización de las etapas más lentas del procesamiento de MLNs, describiendo los problemas encontrados y nuestras propuestas para solucionarlos. Para evaluar nuestros diseños los integramos en Tuffy y RockIt, pues crear todo desde cero va más allá del enfoque de esta tesis. Nuestras contribuciones incluyen: sustitución procesada en paralelo utilizando nuestro sistema de programación lógica; búsqueda particionando y resolviendo un problema de satisfacibilidad booleana con nuestro algoritmo paralelo o un problema de programación lineal; aprendizaje de parametros con sustitución paralela y resolución de un problema de optimización, ajustado con nuestro algoritmo de muestreo paralelo; y aprendizaje de la estructura utilizando Programación Lógica Inductiva, cuya operación más intensiva es calculada con nuestro sistema de programación lógica. Nuestras plataformas fueron probadas con aplicaciones de la literatura y funcionaron muy bien, pues algunas fueron procesadas en minutos mientras otros sistemas no terminaron después de horas. Además, los componentes base de nuestras plataformas también funcionaron bien y pueden usarse como sistemas autónomos.

Abstract

Markov Logic is a language for knowledge representation that combines logic and probabilities, providing a powerful framework for inference and learning tasks. Inference involves grounding and search. Grounding transforms logic representations into a set of weighted propositional clauses that encode a Markov network, the grounded Markov logic network (MLN). Search over the grounded MLN provides probabilistic inference. Learning can be used to find clause weights or structure, by applying inference repeatedly. As the solution space of MLNs can grow rather quickly, their processing can become very expensive, motivating research on their optimization. Multicore parallelism is already used in some well known MLN systems like Tuffy and RockIt, but we know of no other work based on bulk parallelism that Graphics Processing Units (GPUs) support.

This document presents the design, implementation and evaluation of parallel MLN platforms for GPUs. We have designed the parallelization of the most time consuming parts of the MLN process, describing the design issues encountered in both MLNs and GPUs, and our approaches to solving said issues. To evaluate our designs we integrated them into Tuffy and RockIt, as creating a whole system from scratch is beyond the scope of this work. Our contributions include: grounding processed in parallel using our logic programming system; search performed by partitioning and solving a satisfability problem with our parallel algorithm or an integer linear programming problem; parameter learning through parallel grounding and solving an optimization problem, whose parameters are adjusted through our parallel sampling algorithm; and structure learning using Inductive Logic Programming, whose most compute intensive operation is also solved with our parallel logic programming system. Our platforms were tested with applications from the literature and performed very well, with some applications being processed in minutes while other systems could not finish after several hours. Moreover, the core components of our platforms also performed well and can be used as stand-alone systems for general applications.