Orientadores: Anderson de Rezende Rocha, Hélio Pedrini / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T12:33:40Z (GMT). No. of bitstreams: 1 Carvalho_TiagoJosede_D.pdf: 74759719 bytes, checksum: dc371f3262b700f91afa5e0269df1e05 (MD5) Previous issue date: 2014 / Resumo: Antes tomadas como naturalmente genuínas, fotografias não mais podem ser consideradas como sinônimo de verdade. Com os avanços nas técnicas de processamento de imagens e computação gráfica, manipular imagens tornou-se mais fácil do que nunca, permitindo que pessoas sejam capazes de criar novas realidades em minutos. Infelizmente, tais modificações, na maioria das vezes, têm como objetivo enganar os observadores, mudar opiniões ou ainda, afetar como as pessoas enxergam a realidade. Assim, torna-se imprescindível o desenvolvimento de técnicas de detecção de falsificações eficientes e eficazes. De todos os tipos de falsificações de imagens, composições são de especial interesse. Esse tipo de falsificação usa partes de duas ou mais imagens para construir uma nova realidade exibindo para o observador situações que nunca aconteceram. Entre todos os diferentes tipos de pistas investigadas para detecção de composições, as abordagens baseadas em inconsistências de iluminação são consideradas as mais promissoras uma vez que um ajuste perfeito de iluminação em uma imagem falsificada é extremamente difícil de ser alcançado. Neste contexto, esta tese, a qual é fundamentada na hipótese de que inconsistências de iluminação encontradas em uma imagem são fortes evidências de que a mesma é produto de uma composição, apresenta abordagens originais e eficazes para detecção de imagens falsificadas. O primeiro método apresentado explora o reflexo da luz nos olhos para estimar as posições da fonte de luz e do observador da cena. A segunda e a terceira abordagens apresentadas exploram um fenômeno, que ocorre com as cores, denominado metamerismo, o qual descreve o fato de que duas cores podem aparentar similaridade quando iluminadas por uma fonte de luz mas podem parecer totalmente diferentes quando iluminadas por outra fonte de luz. Por fim, nossa última abordagem baseia-se na interação com o usuário que deve inserir normais 3-D em objetos suspeitos da imagem de modo a permitir um cálculo mais preciso da posição 3-D da fonte de luz na imagem. Juntas, essas quatro abordagens trazem importantes contribuições para a comunidade forense e certamente serão uma poderosa ferramenta contra falsificações de imagens / Abstract: Once taken for granted as genuine, photographs are no longer considered as a piece of truth. With the advance of digital image processing and computer graphics techniques, it has been easier than ever to manipulate images and forge new realities within minutes. Unfortunately, most of the times, these modifications seek to deceive viewers, change opinions or even affect how people perceive reality. Therefore, it is paramount to devise and deploy efficient and effective detection techniques. From all types of image forgeries, composition images are specially interesting. This type of forgery uses parts of two or more images to construct a new reality from scenes that never happened. Among all different telltales investigated for detecting image compositions, image-illumination inconsistencies are considered the most promising since a perfect light matching in a forged image is still difficult to achieve. This thesis builds upon the hypothesis that image illumination inconsistencies are strong and powerful evidence of image composition and presents four original and effective approaches to detect image forgeries. The first method explores eye specular highlight telltales to estimate the light source and viewer positions in an image. The second and third approaches explore metamerism, when the colors of two objects may appear to match under one light source but appear completely different under another one. Finally, the last approach relies on user¿s interaction to specify 3-D normals of suspect objects in an image from which the 3-D light source position can be estimated. Together, these approaches bring to the forensic community important contributions which certainly will be a strong tool against image forgeries / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-26T07:59:40Z (GMT). No. of bitstreams: 1 Kulaif_AndreaCarolinaPeres_M.pdf: 1163458 bytes, checksum: ce006fc65c25e72acbf0a2efeb2a3450 (MD5) Previous issue date: 2014 / Resumo: Máquinas de Aprendizado Extremo (ELMs, do inglês Extreme Learning Machines) são redes neurais com uma camada de entrada, uma camada intermediária e uma camada de saída. Sua arquitetura é equivalente à do perceptron de múltiplas camadas (MLP, do inglês Multilayer Perceptron), mas os pesos e o número de neurônios da camada intermediária em ELMs são definidos arbitrariamente e a priori, enquanto os pesos da camada de saída são os únicos parâmetros ajustáveis durante o processo de treinamento supervisionado. O ajuste desses pesos da camada de saída leva a um problema de otimização linear, responsável pelo fato de o treinamento de uma ELM ser ao menos uma ordem de magnitude mais rápido do que o treinamento de uma MLP. No entanto, o desempenho das ELMs é bastante influenciado pelo grau de regularização adotado no ajuste dos pesos da camada de saída. Além disso, por serem definidos de forma arbitrária e não estarem susceptíveis a treinamento, geralmente opera-se com um número elevado de neurônios na camada intermediária, sendo muito comum a presença de neurônios redundantes e pouco funcionais, de modo que sua extração não compromete o desempenho da rede neural como um todo. Em vista desse cenário, esta dissertação apresenta contribuições, junto a ELMs voltadas para tarefas de regressão, em duas frentes principais: (1) Definição de um grau apropriado de regularização no cálculo dos pesos da camada de saída de ELMs; e (2) Ajuste do número de neurônios na camada intermediária, pela extração automática de neurônios redundantes ou pouco funcionais. Mostra-se neste trabalho que, diferentemente do que é praticado na literatura, o grau de regularização mais indicado para uma ELM não varia apenas entre problemas de regressão distintos, mas dentro do mesmo problema de regressão, ainda que se mantenha constante o número de neurônios na camada intermediária. Uma vez detectada a necessidade do ajuste do grau de regularização a cada configuração de ELM, propõe-se aqui uma busca unidimensional mais refinada do que aquela já existente na literatura. Quanto à proposta apresentada para definição do número de neurônios na camada intermediária, faz-se uma análise do espaço de características gerado pelos neurônios dessa camada e aplica-se poda de neurônios que pouco ou nada contribuem para gerar este espaço de características. Além disso, propõe-se o emprego de LASSO e Elastic Net como técnicas de regularização, as quais promovem poda adicional de neurônios que não contribuem para a tarefa de regressão. Para as duas contribuições do trabalho, são apresentados resultados experimentais e comparações com outras propostas da literatura. Há um aumento de custo computacional com as propostas deste trabalho, mas é expressivo o ganho em desempenho em alguns cenários / Abstract: Extreme learning machines are neural networks composed of one input layer, one hidden layer, and one output layer. Their architecture is equivalent to the one of the multilayer perceptron, but the weights and the number of hidden neurons in ELMs are defined a priori and in an arbitrary manner, while the weights at the output layer are the only adjustable parameters during supervised learning. The adjustment of the weights at the output layer leads to a linear optimization problem, responsible for the fact that the training of an ELM be at least one order of magnitude faster than training an MLP. However, the performance of ELMs is greatly influenced by the regularization degree adopted when setting the weights of the output layer. Moreover, by being arbitrarily defined and not susceptible to learning, it is usual to adopt a large number of neurons in the hidden layer, thus promoting the presence of redundant and poorly functional neurons, so that their extraction does not compromise the neural network performance as a whole. Under those circumstances, this dissertation presents contributions to ELMs devoted to regression problems on two main fronts: (1) Definition of a proper degree of regularization when computing the weights at the output layer of ELMs; and (2) Adjustment of the number of neurons at the hidden layer, by the automatic extraction of redundant or poorly functional neurons. It is shown in this work that, different from what is done in the literature, the most suitable degree of regularization for an ELM varies not only among different regression problems, but within the same regression problem and even if it is kept constant the number of neurons at the hidden layer. Once detected the need for adjustment of the degree of regularization for each ELM configuration, it is proposed here a one-dimensional search endowed with more refined steps than that available in the literature. Regarding the proposal to properly define the number of neurons in the hidden layer, an analysis of the feature space generated by neurons in the hidden layer is performed and neurons with no or even a shallow contribution to span the feature space are pruned. Furthermore, the use of LASSO and Elastic Net as regularization techniques are proposed here, which promotes additional pruning of neurons that do not contribute to the regression task. For both contributions of this work, experimental results and comparisons with other proposals in the literature are presented. There is an increase in the computational cost with the proposals of this work, but it is significant the gain in performance in some scenarios / Mestrado / Engenharia de Computação / Mestra em Engenharia Elétrica

Orientadores: Akebo Yamakami, Tiago Agostinho de Almeida / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-22T13:22:48Z (GMT). No. of bitstreams: 1 Silva_RenatoMoraes_M.pdf: 4136928 bytes, checksum: 218846058592353cb167c8c2d61e1bfd (MD5) Previous issue date: 2013 / Resumo: Com o crescente aumento do volume de informações disponíveis na Web, as ferramentas de busca tornam-se cada vez mais importantes para os usuários da Internet. Consequentemente, com o objetivo de se tornar mais visíveis, os sites concorrem entre si para ganhar melhores posições nos resultados das buscas feitas por esses usuários. Porém, muitos ganham maior visibilidade através de estratégias que enganam as ferramentas de busca. Esses sites, conhecidos como Web spam, causam prejuízos pessoais e econômicos aos usuários. Diante desse cenário, este trabalho apresenta uma análise do desempenho de diversos métodos de aprendizado de máquina aplicados na detecção automática de Web hosts que propagam Web spam. Os experimentos foram realizados usando duas bases de dados reais, públicas e de grande porte, das quais foram extraídos três diferentes conjuntos de vetores de atributos: baseados no conteúdo das páginas Web, baseados nos links das páginas Web e formados pela transformação dos atributos baseados nos links. Também foi analisada a viabilidade da redução de dimensionalidade do espaço dos atributos. Outra contribuição desse trabalho é a proposta de uma abordagem de classificação de Web spam, em que as predições obtidas com cada tipo de vetor de atributos são combinadas e uma decisão final é obtida usando-se voto majoritário simples. Os resultados obtidos indicam que os métodos de bagging de árvores de decisão, redes neurais perceptron de múltiplas camadas, floresta aleatória e boosting adaptativo de árvores de decisão são promissores na tarefa de detecção de Web spam. Além disso, verificou-se que os métodos de aprendizado tem melhor desempenho quando os vetores de atributos baseados no conteúdo e os vetores formados pela transformação dos atributos baseados nos links são combinados. Por fim, a combinação das predições obtidas com cada tipo de vetor de atributos gera bons resultados e por isso, essa é uma abordagem recomendada para o combate de Web spamming / Abstract: Due to the increasing volume of information available on the Web, search engines become increasingly important to Internet users. Consequently, with the purpose of becoming more visible, the Web sites compete to achieve better positions in the results of the searches made by such users. However, many of them achieve a good visibility through strategies that try to circumvent the search engines. This kind of Web sites are known as Web spam and they are responsible for personal injury and economic losses to users. Given this scenario, this work presents a performance analysis of established machine learning techniques employed to automatically detect Web hosts that disseminate Web spam. The experiments were performed with two real, public and large datasets, from which were extracted three different sets of features vectors: contentbased ones, link-based ones and features vectors generated by the transformation of the link-based features. We also analyzed the viability of the dimensionality reduction of the feature space. Another contribution of this work is the proposal of a Web spam classification approach which combines the predictions achieved by each type of features vector and using a simple majority voting. The results indicate that bagging of decision trees, multilayer perceptron neural networks, random forest and adaptive boosting of decision trees are promising in the task of spam hosts classification. Furthermore, we have conclude that the learning techniques perform better when we have combined the content-based features vectors and the features vectors generated by the transformation of the link-based features. Finally, the combination of the predictions achieved with each type of features vector has achieved superior results and therefore it is a recommended approach to automatically detect Web spam / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Paulo Augusto Valente Ferreira / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-23T18:31:10Z (GMT). No. of bitstreams: 1 Becker_CassianoOtavio_M.pdf: 861514 bytes, checksum: 07ea364d206309cbabdf79f51037f481 (MD5) Previous issue date: 2013 / Resumo: Esta dissertação investiga o problema de otimização de hiperparâmetros para modelos de aprendizado do computador baseados em regularização. Uma revisão destes algoritmos é apresentada, abordando diferentes funções de perda e tarefas de aprendizado, incluindo Máquinas de Vetores de Suporte, Mínimos Quadrados Regularizados e sua extensão para modelos de aprendizado semi-supervisionado, mais especificamente, Regularização em Variedades. Uma abordagem baseada em otimização por gradiente é proposta, através da utilização de um método eficiente de cálculo da função de validação por exclusão unitária. Com o intuito de avaliar os métodos propostos em termos de qualidade de generalização dos modelos gerados, uma aplicação deste método a diferentes conjuntos de dados e exemplos numéricos é apresentada / Abstract: This dissertation investigates the problem of hyper-parameter optimization for regularization based learning models. A review of different learning algorithms is provided in terms of different losses and learning tasks, including Support Vector Machines, Regularized Least Squares and their extension to semi-supervised learning models, more specifically, Manifold Regularization. A gradient based optimization approach is proposed, using an efficient calculation of the Leave-one-out Cross Validation procedure. Datasets and numerical examples are provided in order to evaluate the methods proposed in terms of their generalization capability of the generated models / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-27T03:14:35Z (GMT). No. of bitstreams: 1 Kurka_DavidBurth_M.pdf: 1660677 bytes, checksum: 7258daf8129b4dac9d1f647195775d3c (MD5) Previous issue date: 2015 / Resumo: Com o surgimento e a popularização de Redes Sociais Online e de Serviços de Redes Sociais, pesquisadores da área de computação têm encontrado um campo fértil para o desenvolvimento de trabalhos com grande volume de dados, modelos envolvendo múltiplos agentes e dinâmicas espaço-temporais. Entretanto, mesmo com significativo elenco de pesquisas já publicadas no assunto, ainda existem aspectos das redes sociais cuja explicação é incipiente. Visando o aprofundamento do conhecimento da área, este trabalho investiga fenômenos de compartilhamento coletivo na rede, que caracterizam eventos de difusão de informação. A partir da observação de dados reais oriundos do serviço online Twitter, tais eventos são modelados, caracterizados e analisados. Com o uso de técnicas de aprendizado de máquina, são encontrados padrões nos processos espaço-temporais da rede, tornando possível a construção de classificadores de mensagens baseados em comportamento e a caracterização de comportamentos individuais, a partir de conexões sociais / Abstract: With the advent and popularization of Online Social Networks and Social Networking Services, computer science researchers have found fertile field for the development of studies using large volumes of data, multiple agents models and spatio-temporal dynamics. However, even with a significant amount of published research on the subject, there are still aspects of social networks whose explanation is incipient. In order to deepen the knowledge of the area, this work investigates phenomena of collective sharing on the network, characterizing information diffusion events. From the observation of real data obtained from the online service Twitter, we collect, model and characterize such events. Finally, using machine learning and computational data analysis, patterns are found on the network's spatio-temporal processes, making it possible to classify a message's topic from users behaviour and the characterization of individual behaviour, from social connections / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientadores: Fernando José Von Zuben, Goran Neshich / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-27T03:11:20Z (GMT). No. of bitstreams: 1 Salim_JoseAugusto_M.pdf: 12514135 bytes, checksum: e429e34406344ef77064e5f5e46194be (MD5) Previous issue date: 2015 / Resumo: As enzimas têm sua função determinada essencialmente por alguns resíduos específicos, denominados resíduos de aminoácidos catalíticos. A função de uma determinada proteína é mantida por milhares de anos de pressão seletiva que ocasionam a preservação de uma estrutura composta por padrões físicos, químicos e estruturais necessários para mantê-la. É frequente observar que enzimas quaisquer presentes em organismos distantemente relacionados exerçam exatamente a mesma função biológica e possuam o mesmo conjunto de resíduos de aminoácidos catalíticos, apesar de possuírem sequências proteicas muito dissimilares. Estes padrões que se conservaram por anos de evolução para manter a função das enzimas têm sido bastante estudados na literatura. Assim, o presente trabalho buscou identificar, dentre os descritores estruturais de proteínas (disponíveis na base de dados da plataforma Blue Star STING) aqueles de maior relevância para discriminar os resíduos de aminoácidos catalíticos dos não catalíticos, por meio do nanoambiente no qual estes se inserem. Buscou-se por modelos classificadores capazes de favorecerem uma interpretação de suas escolhas através de regras na forma SE-ENTÃO, compostas por descritores e seus respectivos valores. Regras foram extraídas para conjuntos de enzimas responsáveis pela catálise da mesma reação enzimática (mesma sub-subclasse EC), de forma a caracterizar o nanoambiente comum aos seus resíduos de aminoácidos catalíticos. Primeiramente, foram considerados apenas descritores estruturais de proteínas, ou seja, excluem-se descritores de conservação de estrutura primária. Esta opção foi feita com base no fato de a conservação de um determinado resíduo em uma determinada posição ser uma consequência (e não causa) de sua crucial função para a atividade de uma enzima. Buscou-se, portanto, compreender a fundo o "por que" de um resíduo ser conservado, utilizando uma "linguagem" puramente estrutural. As doze mais representativas sub-subclasses EC foram escolhidas e regras foram extraídas de forma a caracterizar os resíduos de aminoácido catalíticos de seus membros. Os resultados obtidos variam de acordo com o número de amostras catalíticas disponíveis, sendo as classes com maior número de amostras as que resultaram em regras com maior capacidade de generalização. Ainda que a caracterização dos resíduos de aminoácidos catalíticos possa ser feita apenas com os dados disponíveis, a predição de novas amostras introduz diversos desafios discutidos neste trabalho. Diferentes técnicas de amostragem e seleção de atributos foram estudadas e o impacto de tais técnicas no treinamento é também discutido. Novos descritores estruturais de proteína foram adicionados ao Blue Star STING, assim como foi feito o desenvolvimento de uma biblioteca de programação para facilitar e agilizar a extensão do conjunto de descritores do Blue Star STING / Abstract: The function of enzymes are determined by specific residues, called catalytic amino acids residues. The protein function is maintained for thousands of years of selective pressure which preserves in its structure many physical-chemical and structural patterns. Frequently, enzymes from distinct organisms exert exactly the same biological function due to similar catalytic amino acid residues, even with low sequence similarities. The majority of catalytic amino acid residues prediction methods use sequence conservation features to provide classification. Seeking to understand these conserved patterns in enzyme structures, that even after years of evolution perform the same biological function, the present work searches to identify which protein structural descriptors (available in Blue Star STING platform) are capable of discriminating the amino acid catalytic residues from non-catalytic residues by means of their nanoenvironments properties. Therefore, we studied the use of classification methods available in the literature and STING structural protein descriptors to predict amino acid catalytic residues with no dependency of homologous enzymes. Considering methods capable of extracting IF-THEN rules composed of descriptors and their respective values, sets of rules were built to characterize the amino acid catalytic residues of enzymes catalyzing the same chemical reaction (same EC sub-subclass). Furthermore, it was considered only structural protein descriptors, i.e. no sequence conservation descriptor were considered. The conservation of certain amino acid in a given position is a consequence (not cause) of its crucial function for the enzyme activity. Therefore, the main purpose was to understand in depth the reason why a residue is preserved, employing a purely structural language. Twelve most representative EC sub-subclasses were considered and rules were extracted to characterize the amino acid catalytic residues of their members. The results vary as the number of available structures for each sub-subclass increases. Once it is possible to characterize the amino acid residues of a set of enzymes catalyzing the same chemical reaction, the prediction of amino acid residues in new enzymes faces several challenges discussed in this work, been the major problem the lack of data for amino acid catalytic residues in available databases. Many different techniques as sampling and feature selection methods are employed to alleviate the imbalance of data, and their impact on training are discussed. As a result, we also incorporate new structural protein descriptors to Blue Star STING and developed a new programming library to allow faster and easier extension of the Blue Star STING descriptors set / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientadores: Alexandre Xavier Falcão, Giovani Chiachia / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T14:41:07Z (GMT). No. of bitstreams: 1 Martins_SamuelBotter_M.pdf: 4782261 bytes, checksum: 63cd58756e3fe70ffe625d42974b1a78 (MD5) Previous issue date: 2015 / Resumo: Sistemas automáticos de reconhecimento de faces tem atraído a atenção da indústria e da academia, devido à gama de possíveis aplicações, tais como vigilância, controle de acesso, etc. O recente progresso em tais sistemas motiva o uso de técnicas de aprendizado em profundidade e classificadores específicos para cada usuário em cenários de operação não-controlado, que apresentam variações consideráveis em pose, iluminação, etc. Sistemas automáticos de reconhecimento de faces possibilitam construir bases de imagens anotadas por meio do processo de cadastramento de novos usuários. Porém, à medida que as bases de dados crescem, torna-se crucial reduzir o número de amostras negativas usadas para treinar classificadores específicos para cada usuário, devido às limitações de processamento e tempo de resposta. Tal processo de aprendizado discriminativo durante o cadastramento de novos indivíduos tem implicações no projeto de sistemas de reconhecimento de faces. Apesar deste processo poder aumentar o desempenho do reconhecimento, ele também pode afetar a velocidade do cadastramento, prejudicando, assim, a experiência do usuário. Neste cenário, é importante selecionar as amostras mais informativas buscando maximizar o desempenho do classificador. Este trabalho resolve tal problema propondo um método de aprendizado discriminativo durante o cadastramento de usuários com o objetivo de não afetar a velocidade e a confiabilidade do processo. Nossa solução combina representações de alta dimensão com um algoritmo que rapidamente minera imagens faciais negativas de um conjunto de minerção grande para assim construir um classificador específico para cada usuário, baseado em máquinas de vetores de suporte. O algoritmo mostrou ser robusto em construir pequenos e eficazes conjuntos de treinamento com as amostras negativas mais informativas para cada indivíduo. Avaliamos nosso método em duas bases contendo imagens de faces obtidas no cenário de operação não-controlado, chamadas PubFig83 e Mobio, e mostramos que nossa abordagem é capaz de alcançar um desempenho superior em tempos interativos, quando comparada com outras cinco abordagens consideradas. Os resultados indicam que o nosso método tem potencial para ser explorado pela indústria com mínimo impacto na experiência do usuário. Além disso, o algoritmo é independente de aplicação, podendo ser uma contribuição relevante para sistemas biométricos que visam manter a robustez à medida que o número de usuários aumenta / Abstract: Automatic face recognition has attracted considerable attention from the industry and academy due to its wide range of applications, such as video surveillance, access control, online transactions, suspect identification, etc. The recent progress in face recognition systems motivates the use of deep learning techniques and user-specific face representation and classification models for unconstrained scenarios, which present considerable variations in pose, face appearance, illumination, etc. Automatic face recognition systems make possible to build annotated face datasets through user enrollment. However, as the face datasets grow, it becomes crucial to reduce the number of negative samples used to train user-specific classifiers, due to processing constraints and responsiveness. Such a discriminative learning process during the enrollment of new individuals has implications in the design of face recognition systems. Even though it might increase recognition performance, it may affect the speed of the enrollment, which in turn may affect the user experience. In this scenario, it is important to select the most informative samples in order to maximize the performance of the classifier. This work addresses this problem by proposing a discriminative learning method during user enrollment with the challenges of not negatively affecting the speed and reliability of the process, and so the user experience. Our solution combines high-dimensional representations from deep learning with an algorithm for rapidly mining negative face images from a large mining set to build an effective classification model based on linear support vector machines for each specific user. The negative mining algorithm has shown to be robust in building small and effective training sets with the most informative negative samples for each given individual. We evaluate our approach on two unconstrained datasets, namely PubFig83 and Mobio, and show that it is able to attain superior performance, within interactive response times, as compared to five other baseline approaches that use the same classification scheme. The results indicate that our approach has potential to be exploited by the industry with minimum impact to the user experience. Moreover, the algorithm is application-independent. Hence, it may be a relevant contribution for biometric systems that aim to maintain robustness as the number of users increases / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Algoritmos de aprendizado de máquina são frequentemente os mais indicados em uma grande variedade de aplicações de mineração dados. Entretanto, a maioria das pesquisas em aprendizado de máquina refere-se ao problema bem definido de encontrar um modelo (geralmente de classificação) de um conjunto de dados pequeno, relativamente bem preparado para o aprendizado, no formato atributo-valor, no qual os atributos foram previamente selecionados para facilitar o aprendizado. Além disso, o objetivo a ser alcançado é simples e bem definido (modelos de classificação precisos, no caso de problemas de classificação). Mineração de dados propicia novas direções para pesquisas em aprendizado de máquina e impõe novas necessidades para outras. Com a mineração de dados, algoritmos de aprendizado estão quebrando as restrições descritas anteriormente. Dessa maneira, a grande contribuição da área de aprendizado de máquina para a mineração de dados é retribuída pelo efeito inovador que a mineração de dados provoca em aprendizado de máquina. Nesta tese, exploramos alguns desses problemas que surgiram (ou reaparecem) com o uso de algoritmos de aprendizado de máquina para mineração de dados. Mais especificamente, nos concentramos seguintes problemas: Novas abordagens para a geração de regras. Dentro dessa categoria, propomos dois novos métodos para o aprendizado de regras. No primeiro, propomos um novo método para gerar regras de exceção a partir de regras gerais. No segundo, propomos um algoritmo para a seleção de regras denominado Roccer. Esse algoritmo é baseado na análise ROC. Regras provêm de um grande conjunto externo de regras e o algoritmo proposto seleciona regras baseado na região convexa do gráfico ROC. Proporção de exemplos entre as classes. Investigamos vários aspectos relacionados a esse tópico. Primeiramente, realizamos uma série de experimentos em conjuntos de dados artificiais com o objetivo de testar nossa hipótese de que o grau de sobreposição entre as classes é um fator complicante em conjuntos de dados muito desbalanceados. Também executamos uma extensa análise experimental com vários métodos (alguns deles propostos neste trabalho) para balancear artificialmente conjuntos de dados desbalanceados. Finalmente, investigamos o relacionamento entre classes desbalanceadas e pequenos disjuntos, e a influência da proporção de classes no processo de rotulação de exemplos no algoritmo de aprendizado de máquina semi-supervisionado Co-training. Novo método para a combinação de rankings. Propomos um novo método, chamado BordaRank, para construir ensembles de rankings baseado no método de votação borda count. BordaRank pode ser aplicado em qualquer problema de ordenação binária no qual vários rankings estejam disponíveis. Resultados experimentais mostram uma melhora no desempenho com relação aos rankings individuais, alem de um desempenho comparável com algoritmos mais sofisticados que utilizam a predição numérica, e não rankings, para a criação de ensembles para o problema de ordenação binária. / Machine learning algorithms are often the most appropriate algorithms for a great variety of data mining applications. However, most machine learning research to date has mainly dealt with the well-circumscribed problem of finding a model (generally a classifier) given a single, small and relatively clean dataset in the attribute-value form, where the attributes have previously been chosen to facilitate learning. Furthermore, the end-goal is simple and well-defined, such as accurate classifiers in the classification problem. Data mining opens up new directions for machine learning research, and lends new urgency to others. With data mining, machine learning is now removing each one of these constraints. Therefore, machine learning's many valuable contributions to data mining are reciprocated by the latter's invigorating effect on it. In this thesis, we explore this interaction by proposing new solutions to some problems due to the application of machine learning algorithms to data mining applications. More specifically, we contribute to the following problems. New approaches to rule learning. In this category, we propose two new methods for rule learning. In the first one, we propose a new method for finding exceptions to general rules. The second one is a rule selection algorithm based on the ROC graph. Rules come from an external larger set of rules and the algorithm performs a selection step based on the current convex hull in the ROC graph. Proportion of examples among classes. We investigated several aspects related to this issue. Firstly, we carried out a series of experiments on artificial data sets in order to verify our hypothesis that overlapping among classes is a complicating factor in highly skewed data sets. We also carried out a broadly experimental analysis with several methods (some of them proposed by us) that artificially balance skewed datasets. Our experiments show that, in general, over-sampling methods perform better than under-sampling methods. Finally, we investigated the relationship between class imbalance and small disjuncts, as well as the influence of the proportion of examples among classes in the process of labelling unlabelled cases in the semi-supervised learning algorithm Co-training. New method for combining rankings. We propose a new method called BordaRanking to construct ensembles of rankings based on borda count voting, which could be applied whenever only the rankings are available. Results show an improvement upon the base-rankings constructed by taking into account the ordering given by classifiers which output continuous-valued scores, as well as a comparable performance with the fusion of such scores.

Atualmente, o meio mais comum de busca de informações é a WEB. Assim, é importante procurar métodos eficientes para recuperar essa informação. As máquinas de busca na WEB usualmente utilizam palavras-chaves para expressar uma busca. Porém, não é trivial caracterizar a informação desejada. Usuários diferentes com necessidades diferentes podem estar interessados em informações relacionadas, mas distintas, ao realizar a mesma busca. O processo de realimentação de relevância torna possível a participação ativa do usuário no processo de busca. A idéia geral desse processo consiste em, após o usuário realizar uma busca na WEB permitir que indique, dentre os sites encontrados, quais deles considera relevantes e não relevantes. A opinião do usuário pode então ser considerada para reordenar os dados, de forma que os sites relevantes para o usuário sejam retornados mais facilmente. Nesse contexto, e considerando que, na grande maioria dos casos, uma consulta retorna um número muito grande de sites WEB que a satisfazem, das quais o usuário é responsável por indicar um pequeno número de sites relevantes e não relevantes, tem-se o cenário ideal para utilizar aprendizado parcialmente supervisionado, pois essa classe de algoritmos de aprendizado requer um número pequeno de exemplos rotulados e um grande número de exemplos não-rotulados. Assim, partindo da hipótese que a utilização de aprendizado parcialmente supervisionado é apropriada para induzir um classificador que pode ser utilizado como um filtro de realimentação de relevância para buscas na WEB, o objetivo deste trabalho consiste em explorar algoritmos de aprendizado parcialmente supervisionado, mais especificamente, aqueles que utilizam multidescrição de dados, para auxiliar na recuperação de sites na WEB. Para avaliar esta hipótese foi projetada e desenvolvida uma ferramenta denominada C-SEARCH que realiza esta reordenação dos sites a partir da indicação do usuário. Experimentos mostram que, em casos que buscas genéricas, que o resultado possui um bom diferencial entre sites relevantes e irrelevantes, o sistema consegue obter melhores resultados para o usuário / As nowadays the WEB is the most common source of information, it is very important to find reliable and efficient methods to retrieve this information. However, the WEB is a highly volatile and heterogeneous information source, thus keyword based querying may not be the best approach when few information is given. This is due to the fact that different users with different needs may want distinct information, although related to the same keyword query. The process of relevance feedback makes it possible for the user to interact actively with the search engine. The main idea is that after performing an initial search in the WEB, the process enables the user to indicate, among the retrieved sites, a small number of the ones considered relevant or irrelevant according with his/her required information. The users preferences can then be used to rearrange sites returned in the initial search, so that relevant sites are ranked first. As in most cases a search returns a large amount of WEB sites which fits the keyword query, this is an ideal situation to use partially supervised machine learning algorithms. This kind of learning algorithms require a small number of labeled examples, and a large number of unlabeled examples. Thus, based on the assumption that the use of partially supervised learning is appropriate to induce a classifier that can be used as a filter for relevance feedback in WEB information retrieval, the aim of this work is to explore the use of a partially supervised machine learning algorithm, more specifically, one that uses multi-description data, in order to assist the WEB search. To this end, a computational tool called C-SEARCH, which performs the reordering of the searched results using the users feedback, has been implemented. Experimental results show that in cases where the keyword query is generic and there is a clear distinction between relevant and irrelevant sites, which is recognized by the user, the system can achieve good results

A Sumarização Multidocumento consiste na produção automática de um único sumário a partir de um conjunto de textos que tratam de um mesmo assunto. Essa tarefa vem se tornando cada vez mais importante, já que auxilia o processamento de grandes volumes de informação, permitindo destacar a informação mais relevante para o usuário. Nesse trabalho, são propostas e exploradas modelagens baseadas em Aprendizado Gerativo, em que a tarefa de Sumarização Multidocumento é esquematizada usando o modelo Noisy- Channel e seus componentes de modelagem de língua, de transformação e decodificação, que são apropriadamente instanciados para a tarefa em questão. Essas modelagens são formuladas com atributos superficiais e profundos. Em particular, foram definidos três modelos de transformação, cujas histórias gerativas capturam padrões de seleção de conteúdo a partir de conjuntos de textos e seus correspondentes sumários multidocumento produzidos por humanos. O primeiro modelo é relativamente mais simples, pois é composto por atributos superficiais tradicionais; o segundo modelo é mais complexo, pois, além de atributos superficiais, adiciona atributos discursivos monodocumento; finalmente, o terceiro modelo é o mais complexo, pois integra atributos superficiais, de natureza discursiva monodocumento e semântico-discursiva multidocumento, pelo uso de informação proveniente das teorias RST e CST, respectivamente. Além desses modelos, também foi desenvolvido um modelo de coerência (ou modelo de língua) para sumários multidocumento, que é projetado para capturar padrões de coerência, tratando alguns dos principais fenômenos multidocumento que a afetam. Esse modelo foi desenvolvido com base no modelo de entidades e com informações discursivas. Cada um desses modelos foi inferido a partir do córpus CSTNews de textos jornalísticos e seus respectivos sumários em português. Finalmente, foi desenvolvido também um decodificador para realizar a construção do sumário a partir das inferências obtidas. O decodificador seleciona o subconjunto de sentenças que maximizam a probabilidade do sumário de acordo com as probabilidades inferidas nos modelos de seleção de conteúdo e o modelo de coerência. Esse decodificador inclui também uma estratégia para evitar que sentenças redundantes sejam incluídas no sumário final. Os sumários produzidos a partir dessa modelagem gerativa são comparados com os sumários produzidos por métodos estatísticos do estado da arte, os quais foram implementados, treinados e testados sobre o córpus. Utilizando-se avaliações de informatividade tradicionais da área, os resultados obtidos mostram que os modelos desenvolvidos neste trabalho são competitivos com os métodos estatísticos do estado da arte e, em alguns casos, os superam. / Multi-document Summarization consists in automatically producing a unique summary from a set of source texts that share a common topic. This task is becoming more important, since it supports large volume data processing, enabling to highlight relevant information to the users. In this work, generative modeling approaches are proposed and investigated, where the Multidocument Summarization task is modeled through the Noisy-Channel framework and its components: language model, transformation model and decoding, which are properly instantiated for the correspondent task. These models are formulated with shallow and deep features. Particularly, three main transformation models were defined, establishing generative stories that capture content selection patterns from sets of source texts and their corresponding human multi-document summaries. The first model is the less complex, since its features are traditional shallow features; the second model is more complex, incorporating single-document discursive knowledge features (given by RST) to the features proposed in the first model; finally, the third model is the most complex, since it incorporates multi-document discursive knowledge features (given by CST) to the features provided by models 1 and 2. Besides these models, it was also developed a coherence model (represented by the Noisy-Channel´s language model) for multi-document summaries. This model, different from transformation models, aims at capturing coerence patterns in multi-document summaries. This model was developed over the Entity-based Model and incorporates discursive knowledge in order to capture coherence patterns, exploring multi-document phenomena. Each of these models was treined with the CSTNews córpus of journalistic texts and their corresponding summaries. Finally, a decoder to search for the summary that maximizes the probability of the estimated models was developed. The decoder selects the subset of sentences that maximize the estimated probabilities. The decoder also includes an additional functionality for treating redundancy in the decoding process by using discursive information from the CST. The produced summaries are compared with the summaries produced by state of the art generative models, which were also treined and tested with the CSTNews corpus. The evaluation was carried out using traditional informativeness measures, and the results showed that the generative models developed in this work are competitive with the state of the art statistical models, and, in some cases, they outperform them. .