Information Extraction from Crowds in Dynamic Environments

Abstract

Today's society is based on information sharing. The Internet, once exclusively a computer network, evolved to a network of personal devices. Mobile phones, tablets, watches, and even common household devices are acquiring, sending, and receiving data much faster than we would imagine possible a few years ago. However, as we are producing more data, we are becoming less aware of reliable information.

Social networks are paradigmatic to this scenario. Highly accepted by most Internet users, they became a potential source of information. The extraordinary and relevant amount of data made available in social networks may be used towards the resolution of challenges faced by individuals and companies. Users can also contribute with their skills to problem solving, which is the idea in which crowdsourcing lays its foundation, i.e., a multitude of non-experts that contribute to real-world problem solving. Humans' innate aptitude to deal with intrinsically subjective tasks, and to perceive related concepts, turns them into a valuable resource.

In this thesis we present novel and efficient techniques to deal with information extraction from crowds in dynamic environments. We describe the paths we have explored and propose a framework that integrates the acquired knowledge to deal with some of the major challenges of learning in such environments.

One of the techniques that is able to introduce important information into the learning process is active learning. When combined with crowdsourcing's potential for problem solving, active learning can be of major interest. We investigate an active learning strategy that uses an assertive supervisor versus crowdsourcing. A recommendation system is used as case study, and active learning is also proposed for customization purposes. Active learning allows the integration of user feedback into the learning process, thus defining a customized crowd used for model customization.

To tackle the problem of effectively learning from crowds in dynamic environments, we use the Twitter social network as case study. We use hashtags as Twitter message classification targets, and propose the definition of semantic meta-hashtags, which cluster similar messages, to improve classification performance.

The impact of longstanding messages in Twitter is also studied to understand how informative can past events be to current learning models. A technique to define the best set of training examples using dynamic ensembles in Twitter is proposed, along with a study regarding the effect of using different metrics for combining ensembles’ models, specifically performance-based metrics.

Three different models to learn in dynamic environments are proposed: a time-window model, an ensemble-based model, and an incremental model. The time-window model is characterized by taking into account recent information in a given time-window. The ensemble model is based on the idea that the use of a committee of classifiers can provide better results than the best of the single classifiers, if correctly combined. Finally, the incremental model is characterized by retaining in a single classifier all the information gathered over time.

A benchmark dataset with drift in Twitter, where real tweets are artificially timestamped to represent different drift patterns, is also proposed. To define such dataset the Drift Oriented Tool System (DOTS), a framework that allows the definition and generation of text-based datasets with different drift patterns, is used. DOTS is made publicly and freely available and it can be used by researchers to evaluate and validate learning strategies in dynamic environments. Another important contribution is Drift Adaptive Retain Knowledge (DARK), a framework to effectively learn in dynamic environments in text classification scenarios. It uses an ensemble of classifiers with dynamic weighting schemes and variable training window sizes for model adaptation in incremental learning. A comparative study of the performance of DARK with benchmark solutions in the field, namely the Learn++.NSE algorithm, is presented and demonstrates its potential as a learning strategy in dynamic environments.The techniques proposed in this thesis deal with the some of the most important challenges regarding learning in dynamic environments. Different approaches are used, such as active learning, crowdsourcing, and ensembles. Experimental results show a classification improvement when compared to benchmark solutions in a real-world dataset. We finish this thesis by summarizing the contributions we have made and proposing further research paths.

A sociedade dos dias de hoje é baseada na partilha de informação. A Internet, tendo já sido exclusivamente uma rede de computadores, evoluiu para uma rede de dispositivos pessoais. Telemóveis, tablets, relógios, e eletrodomésticos adquirem, enviam e recebem dados a uma velocidade que antigamente não imaginávamos possível. Produzimos mais dados, mas estamos a tornar-nos incapazes de obter informação relevante.

As redes sociais são paradigmáticas neste contexto. Altamente aceites pela maioria dos utilizadores da Internet, tornaram-se numa potencial fonte de informação. A quantidade extraordinária e a relevância dos dados hoje disponibilizados pelas redes sociais podem ser usadas na resolução de imensos desafios enfrentados hoje em dia por indivíduos e empresas. Os utilizadores das redes socias podem mesmo contribuir com conhecimento para a resolução de problemas, uma ideia de base do crowdsourcing, onde uma multidão indiferenciada pode contribuir para a resolução de problemas do mundo real. A aptidão inata dos seres humanos para lidarem com tarefas altamente subjectivas, e para perceber a relação entre conceitos, torna-os num valioso recurso.

Nesta tese apresentamos novas e eficientes técnicas que nos permitem lidar com a extracção de informação colaborativa em ambientes dinâmicos. Descrevemos as abordagens desenvolvidas e propomos uma framework que integra o conhecimento adquirido, de forma a lidar com alguns dos principais desafios de aprendizagem em ambientes desta natureza. Uma das técnicas que permite a introdução de informação importante ao processo de aprendizagem é a aprendizagem activa. Quando combinada com a potencialidade da utilização de crowdsourcing na resolução de problemas, a aprendizagem activa pode relevar-se imensamente interessante. Investigámos a utilização de uma estratégia de aprendizagem activa que compara o uso de um supervisor assertivo em detrimento de crowdsourcing. Foi utilizado um sistema de recomendação como caso de estudo, tendo a aprendizagem activa sido usada para fins de personalização. A aprendizagem activa permite a integração de feedback no processo de aprendizagem, possibilitando assim a definição de grupos de utilizadores para a personalização de modelos. Para contribuir para o problema da aprendizagem efectiva em ambientes dinâmicos com recurso a grupos, utilizámos a rede social Twitter como caso de estudo. Recorremos às hashtags das mensagens de Twitter como alvo de classificação e propusemos a definição de meta-hashtags semânticas, que agrupam mensagens similares para melhorar o desempenho da classificação.

O impacto da eternidade de mensagem no Twitter é também estudado para perceber quão informativos podem ser os eventos passados em modelos de aprendizagem atuais. Uma técnica que define qual o melhor conjunto de treino a utilizar em ensembles dinâmicos no Twitter é também proposta, assim como um estudo referente ao efeito da utilização de diferentes métricas para combinar modelos de ensemble, nomeadamente métricas baseadas em performance.

São propostos três modelos diferentes para aprendizagem em ambientes dinâmicos: um baseado em janelas temporais, outro baseado em ensembles e outro incremental. O modelo baseado em janelas temporais é caracterizado por ter em conta a informação mais recente de acordo com uma determinada janela temporal. O modelo baseado em ensembles usa um grupo de classificadores que, quando corretamente combinados, permitem encontrar uma solução melhor que o a utilização do melhor classificador do grupo. Finalmente, o modelo incremental caracteriza-se por reter num único classificador toda a informação recolhida ao longo do tempo.

É apresentado um dataset de referência com drift em Twitter, onde tweets reais são temporalmente marcados artificialmente, por forma a representar diferentes padrões de drift. Para definir o referido dataset foi utilizada a framework Drift Oriented Tool System (DOTS), que permite não só a definição como a geração de datasets de texto com diferentes padrões de drift. A DOTS foi tornada pública e está disponível gratuitamente para possibilitar a sua utilização por investigadores, permitindo assim que possam avaliar e validar as suas estratégias de aprendizagem em ambientes dinâmicos.

Outra importante contribuição é a framework Drift Adaptive Retain Knowledge (DARK), que permite uma aprendizagem efectiva em ambientes dinâmicos em cenários de classificação de texto. Utiliza ensembles de classificadores com pesos dinâmicos e janelas de aprendizagem de tamanho variável para adaptação de modelos em aprendizagem incremental. É também apresentado um estudo comparativo da performance da DARK com soluções de topo na área, nomeadamente o algoritmo Learn++.NSE, e demonstrando assim o seu potencial como estratégia de aprendizagem em ambientes dinâmicos. As técnicas propostas nesta tese fazem face a alguns dos mais importantes desafios no que toca a aprendizagem em ambientes dinâmicos. São utilizadas diferentes abordagens, tais como aprendizagem activa, crowdsourcing e ensembles. Os resultados experimentais demonstram melhorias na classificação quando comparados com soluções de topo em dataset reais. Terminamos esta tese sumariando as contribuições e propondo novos caminhos de investigação.