Inductive inference for large scale text classification

Abstract

Nas últimas décadas a disponibilidade e importância dos textos em formato digital tem vindo a aumentar exponencialmente, encontrando-se neste momento presentes em quase todos os aspectos da vida moderna. A classificação de textos é deste modo uma área activa de investigação, justificada por muitas aplicações reais. Ainda assim, lidar com a sobrecarga de textos em formato digital envolve desafios inerentes, nomeadamente as elevadas dimensionalidade e escala, necessárias para representar os textos, a dificuldade de introduzir conhecimento humano no processo de aprendizagem e subjectividade da classificação. Nesta tese propomos novas técnicas para lidar de um modo eficiente com tais desafios com base num sistema de inferência indutiva. Descrevemos a aplicação de máquinas baseadas em kernels à classificação automática de documentos e estabelecemos uma framework que integra conhecimento de forma a melhorar o desempenho do sistema. Uma fonte importante de conhecimento em classificação de texto são os textos não classificados, normalmente menos onerosos e mais simples d obter do que os já classificados. Investigamos vários métodos baseados na margem de classificação e fazemos uso do seu potencial. Mostramos que os melhoramentos propostos integram novo conhecimento nos procedimentos de aprendizagem e apresentamos melhorias em relação ao desempenho de base. Métodos baseados em kernels, nomeadamente máquinas de vectores de suporte (SVMs) e máquinas de vectores relevantes (RVMs), são algoritmos estado-da-arte. Enquanto as SVMs usam o princípio da Minimização do Risco Estrutural para reduzir eficazmente o erro de treino, as RVMs são completamente probabilísticas, promovendo a esparsidade dos modelos. Os conceitos de kernel e de kernel trick permitem a sua aplicação a quase todas as aplicacões. Foi proposta uma combinação de SVMs e RVMs numa configuração híbrida, onde a confiança de classificação das RVMs é usada para determinar os exemplos a classificar pelas SVMs. Esta configuração supera ambas as máquinas de aprendizagem quando usadas isoladamente. Foram investigadas várias estratégias com métodos baseados em kernels para escalar os problemas de classificação de texto. Três novas abordagens foram propostas: primeiro usamos uma medida de similitude para remover documentos desnecessários do conjunto de treino; segundo, aplicamos uma estratégia de dividir para reinar baseada em técnicas incrementais, técnicas de boosting e aplicação de ensembles que, não só acelera os processos, como melhora o seu desempenho; finalmente distribuímos eficazmente todo o sistema de classificação de texto num ambiente de cluster, obtendo speedups significativos. As técnicas desenvolvidas no âmbito desta tese lidam com alguns dos desafios mais importantes da classificação de textos usando abordagens variadas, tais como aprendizagem activa, ensembles e ambientes distribuídos. Os resultados experimentais mostram uma melhoria geral do desempenho de classificação e, simultaneamente, uma redução do tempo de processamento que pode tornar-se crucial em aplicações reais. Terminamos a tese apresentando as conclusões do trabalho desenvolvido e discutindo uma framework para sistemas de classificação de texto que inclui as contribuições atingidas com esta tese e linhas para investigação futura na área.

In the last few decades the accessibility and importance of digital texts have been increasing exponentially. They are now present in almost every aspect of modern life. Text classification is therefore an active research area motivated by many real-world applications. Even so, handling the overload of digital texts still involves some inherent challenges, in particular the highdimensionality and high-scale of the data necessary to represent the texts, the difficulty of introducing tangible human knowledge into the learning task and the subjectivity of classification. In this thesis we propose new and efficient techniques for handling some of these challenges, based on an inductive inference system. We describe investigations into the applications to text classification of kernel-based learning machines and establish a knowledge integration framework to deal with those difficulties. One key source of knowledge in text classification is unlabeled texts, usually much less expensive and easier to gather than labeled ones. We investigate several margin-based methods to retrieve and use this potential. We show that the proposed enhancements integrate new knowledge into the learning procedures and show improvements over the baseline performances. Kernel methods, viz. support vector machines (SVMs) and relevance vector machines (RVMs), constitute state-of-the-art learning algorithms. While SVMs rely on the Structural Risk Minimization principle to effectively reduce the training error, RVMs offer a fully probabilistic framework that provides sparse models. The concepts of kernels and the kernel trick permit their successful application to practically any given application. We have proposed a combination of both SVMs and RVMs in a hybrid setting, where the RVM confidence is used to determine the SVMs' examples, outperforming both baseline learning machines. Several scaling strategies for kernel methods were investigated. We have proposed three different approaches. First we use a similitude measure to remove unnecessary documents from the training set. Second, we apply a divide-and-conquer strategy based on incremental, boosting and ensemble techniques that not only improves performance, but also speeds up procedures. Finally, we have successfully deployed the whole text classification system in a cluster distributed environment, obtaining significant speedups. The techniques developed in this thesis deal with some of the most important challenges in text classification and use different approaches, such as active learning, ensembles and cluster environments. Experimental results show a general classification performance improvement, along with a reduction of processing time that can be crucial in real applications. We finish the thesis by proposing and discussing a framework for text classification systems that includes the contributions made with this thesis, opening windows to further research in the field.