Supervised learning for relationship extraction from textual documents

João Pedro Lebre Magalhães Pereira

Key information

Authors:

João Pedro Lebre Magalhães Pereira (João Pedro Lebre Magalhães Pereira)

Supervisors:

Helena Isabel De Jesus Galhardas (Helena Isabel De Jesus Galhardas); Bruno Emanuel Da Graça Martins (Bruno Emanuel Da Graça Martins)

Published in

11/11/2013

Abstract

Information Extraction (IE) is the task of automatically extracting structured information from unstructured data, aiming to facilitate the use of said data by other applications. A typical sub-problem is the extraction of relationships from textual documents, which aims at identifying and classifying the relationships expressed between entities mentioned in the texts. In order to extract relationships from a raw text, it is important to pre-process the data, organizing the textual contents into useful data structures, with techniques from Natural Language Processing. Furthermore, since relationships are expressed between entities, it is mandatory to identify the entities using an entity extraction method, which is another sub-problem of IE. Assigning a relationship type to a pair of entities can be seen as a classification problem. Therefore, supervised machine learning techniques can be applied. In this thesis, we used Support Vector Machines (SVM), which we trained with basis on online methods similar to Pegasos [27]. Two specific modeling choices have been tested. The first one is a simple online solution that trains SVM models considering a single kernel. The second approach is based on the idea of online multiple kernel learning. With existing datasets and common pre-processing tools, we formulated a benchmark, which was then used to evaluate kernel-based methods. We then implemented state-of-the-art kernels, specifically designed for relationship extraction. The results show that a multiple kernel learning solution obtains the best performance, and that multiple kernel learning solutions can perform better than heuristic solutions learning with a linear combinations of the same kernels. Extracção de Informação é a tarefa de extrair automaticamente informação estruturada de dados não estruturados, visando facilitar o uso da mesma por parte de outras aplicações. Um típico sub-problema é a extracção de relações de documentos textuais, com o objectivo de identificar e classificar as relações expressas entre as entidades mencionadas no texto. De forma a extrair relações em texto, é importante preprocessar os dados, organizar os conteúdos textuais em estruturas de dados úteis com a utilização de técnicas de Processamento de Língua Natural. Ademais, como as relações sâo expressas entre entidades, é necessário identificá-las, usando para isso um método de extracção de entidades, que é outro subproblema da extracção de informação. Associar um tipo de relação, a um par de entidades, pode ser visto como um problema de classificação. Como tal, podemos aplicar técnicas de aprendizagem automática supervisionada. Nesta tese, usámos máquinas de vectores de suporte (SVMs), que treinámos com base em métodos online, semelhantes ao Pegasos. Testámos dois modelos específicos. O primeiro é uma simples solução online que treina modelos SVM considerando apenas um kernel. O segundo tem por base a ideia de aprendizagem online com múltiplos kernels. Com os bancos de dados existentes e um preprocessamento comum, formulamos uma benchmark a qual usamos para comparar e avaliar métodos baseados em kernels. Posteriormente implementamos os kernels do estado-da-arte, especificamente criados para a extracção de relações. Os resultados experimentais demonstraram depois resultados concordantes com uma melhor performance associada à aprendizagem de múltiplos kernels, em comparação com outras soluções heurísticas que apenas usaram combinações lineares do mesmo conjunto de kernels.