La sélection de modèle est un thème majeur de l'apprentissage statistique. Dans ce manuscrit, nous introduisons des méthodes de sélection de modèle dédiées à des SVM bi-classes et multi-classes. Ces machines ont pour point commun d'être à coût quadratique, c'est-à-dire que le terme empirique de la fonction objectif de leur problème d'apprentissage est une forme quadratique. Pour les SVM, la sélection de modèle consiste à déterminer la valeur optimale du coefficient de régularisation et à choisir un noyau approprié (ou les valeurs de ses paramètres). Les méthodes que nous proposons combinent des techniques de parcours du chemin de régularisation avec de nouveaux critères de sélection. La thèse s'articule autour de trois contributions principales. La première est une méthode de sélection de modèle par parcours du chemin de régularisation dédiée à la l2-SVM. Nous introduisons à cette occasion de nouvelles approximations de l'erreur en généralisation. Notre deuxième contribution principale est une extension de la première au cas multi-classe, plus précisément à la M-SVM². Cette étude nous a conduits à introduire une nouvelle M-SVM, la M-SVM des moindres carrés. Nous présentons également de nouveaux critères de sélection de modèle pour la M-SVM de Lee, Lin et Wahba à marge dure (et donc la M-SVM²) : un majorant de l'erreur de validation croisée leave-one-out et des approximations de cette erreur. La troisième contribution principale porte sur l'optimisation des valeurs des paramètres du noyau. Notre méthode se fonde sur le principe de maximisation de l'alignement noyau/cible, dans sa version centrée. Elle l'étend à travers l'introduction d'un terme de régularisation. Les évaluations expérimentales de l'ensemble des méthodes développées s'appuient sur des benchmarks fréquemment utilisés dans la littérature, des jeux de données jouet et des jeux de données associés à des problèmes du monde réel / Model selection is of major interest in statistical learning. In this document, we introduce model selection methods for bi-class and multi-class support vector machines. We focus on quadratic loss machines, i.e., machines for which the empirical term of the objective function of the learning problem is a quadratic form. For SVMs, model selection consists in finding the optimal value of the regularization coefficient and choosing an appropriate kernel (or the values of its parameters). The proposed methods use path-following techniques in combination with new model selection criteria. This document is structured around three main contributions. The first one is a method performing model selection through the use of the regularization path for the l2-SVM. In this framework, we introduce new approximations of the generalization error. The second main contribution is the extension of the first one to the multi-category setting, more precisely the M-SVM². This study led us to derive a new M-SVM, the least squares M-SVM. Additionally, we present new model selection criteria for the M-SVM introduced by Lee, Lin and Wahba (and thus the M-SVM²). The third main contribution deals with the optimization of the values of the kernel parameters. Our method makes use of the principle of kernel-target alignment with centered kernels. It extends it through the introduction of a regularization term. Experimental validation of these methods was performed on classical benchmark data, toy data and real-world data

Orientador: Siome Klein Goldenstein / Tese (doutorado) - Universidade Estadual de Campinas, Instituto da Computação / Made available in DSpace on 2018-08-12T17:37:15Z (GMT). No. of bitstreams: 1 Rocha_AndersondeRezende_D.pdf: 10303487 bytes, checksum: 243dccfe5255c828ce7ead27c27eb1cd (MD5) Previous issue date: 2009 / Resumo: Neste trabalho de doutorado, propomos a utilizaçãoo de classificadores e técnicas de aprendizado de maquina para extrair informações relevantes de um conjunto de dados (e.g., imagens) para solução de alguns problemas em Processamento de Imagens e Visão Computacional. Os problemas de nosso interesse são: categorização de imagens em duas ou mais classes, detecçãao de mensagens escondidas, distinção entre imagens digitalmente adulteradas e imagens naturais, autenticação, multi-classificação, entre outros. Inicialmente, apresentamos uma revisão comparativa e crítica do estado da arte em análise forense de imagens e detecção de mensagens escondidas em imagens. Nosso objetivo é mostrar as potencialidades das técnicas existentes e, mais importante, apontar suas limitações. Com esse estudo, mostramos que boa parte dos problemas nessa área apontam para dois pontos em comum: a seleção de características e as técnicas de aprendizado a serem utilizadas. Nesse estudo, também discutimos questões legais associadas a análise forense de imagens como, por exemplo, o uso de fotografias digitais por criminosos. Em seguida, introduzimos uma técnica para análise forense de imagens testada no contexto de detecção de mensagens escondidas e de classificação geral de imagens em categorias como indoors, outdoors, geradas em computador e obras de arte. Ao estudarmos esse problema de multi-classificação, surgem algumas questões: como resolver um problema multi-classe de modo a poder combinar, por exemplo, caracteríisticas de classificação de imagens baseadas em cor, textura, forma e silhueta, sem nos preocuparmos demasiadamente em como normalizar o vetor-comum de caracteristicas gerado? Como utilizar diversos classificadores diferentes, cada um, especializado e melhor configurado para um conjunto de caracteristicas ou classes em confusão? Nesse sentido, apresentamos, uma tecnica para fusão de classificadores e caracteristicas no cenário multi-classe através da combinação de classificadores binários. Nós validamos nossa abordagem numa aplicação real para classificação automática de frutas e legumes. Finalmente, nos deparamos com mais um problema interessante: como tornar a utilização de poderosos classificadores binarios no contexto multi-classe mais eficiente e eficaz? Assim, introduzimos uma tecnica para combinação de classificadores binarios (chamados classificadores base) para a resolução de problemas no contexto geral de multi-classificação. / Abstract: In this work, we propose the use of classifiers and machine learning techniques to extract useful information from data sets (e.g., images) to solve important problems in Image Processing and Computer Vision. We are particularly interested in: two and multi-class image categorization, hidden messages detection, discrimination among natural and forged images, authentication, and multiclassification. To start with, we present a comparative survey of the state-of-the-art in digital image forensics as well as hidden messages detection. Our objective is to show the importance of the existing solutions and discuss their limitations. In this study, we show that most of these techniques strive to solve two common problems in Machine Learning: the feature selection and the classification techniques to be used. Furthermore, we discuss the legal and ethical aspects of image forensics analysis, such as, the use of digital images by criminals. We introduce a technique for image forensics analysis in the context of hidden messages detection and image classification in categories such as indoors, outdoors, computer generated, and art works. From this multi-class classification, we found some important questions: how to solve a multi-class problem in order to combine, for instance, several different features such as color, texture, shape, and silhouette without worrying about the pre-processing and normalization of the combined feature vector? How to take advantage of different classifiers, each one custom tailored to a specific set of classes in confusion? To cope with most of these problems, we present a feature and classifier fusion technique based on combinations of binary classifiers. We validate our solution with a real application for automatic produce classification. Finally, we address another interesting problem: how to combine powerful binary classifiers in the multi-class scenario more effectively? How to boost their efficiency? In this context, we present a solution that boosts the efficiency and effectiveness of multi-class from binary techniques. / Doutorado / Engenharia de Computação / Doutor em Ciência da Computação

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-03-07T15:27:21Z No. of bitstreams: 1 mauricioarchanjonunescoelho.pdf: 2468130 bytes, checksum: 3f05daa8428e367942c4ad560b6375f2 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-03-10T12:19:13Z (GMT) No. of bitstreams: 1 mauricioarchanjonunescoelho.pdf: 2468130 bytes, checksum: 3f05daa8428e367942c4ad560b6375f2 (MD5) / Made available in DSpace on 2017-03-10T12:19:13Z (GMT). No. of bitstreams: 1 mauricioarchanjonunescoelho.pdf: 2468130 bytes, checksum: 3f05daa8428e367942c4ad560b6375f2 (MD5) Previous issue date: 2010-06-18 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O problema de planejamento de caminhos apresenta diversas subáreas, muitas das quais já extensamente abordadas na literatura. Uma dessas áreas em especial é a de determinação de caminhos, os algoritmos empregados para a solução deste problema dependem que os custos estipulados para os ambientes ou mapas sejam confiáveis. A dificuldade está justamente na definição dos custos referentes a cada tipo de área ou terreno nos mapas a serem examinados. Como se pode observar, o problema mencionado inclui a dificuldade em se determinar qual o custo de cada característica relevante presente no mapa, bem como os custos de suas possíveis combinações. A proposta deste trabalho é mostrar como é feita a predição desses custos em novos ambientes tendo como base a predição de dados estruturados definindo um aprendizado funcional entre domínios de entrada e saída, estruturados e arbitrários. O problema de aprendizado em questão é normalmente formulado como um problema de otimização convexa de máxima margem bastante similar a formulação de máquinas de vetores suporte multi-classe. Como técnica de solução realizou-se a implementação do algoritmo MMP (Maximum Margin Planning) (RATLIFF; BAGNELL; ZINKEVICH, 2006). Como contribuição, desenvolveu-se e implementou-se dois algoritmos alternativos, o primeiro denominado Perceptron Estruturado e o segundo Perceptron Estruturado com Margem, ambos os métodos de relaxação baseados na formulação do Perceptron. Os mesmos foram analisados e comparados. Posteriormente temos a exploração dos ambientes por um agente inteligente utilizando técnicas de aprendizado por reforço. Tornando todo o processo, desde a análise do ambiente e descoberta de custos, até sua exploração e planejamento do caminho, um completo processo de aprendizado. / The problem of path planning has several sub-areas, many of which are widely discussed in the literature. One of these areas in particular is the determination of paths, the algorithms used to solve this problem depend on the reliability of the estimated costs in the environments and maps. The difficulty is precisely the definition of costs for each type of area or land on the maps to be examined. As you can see, the problem mentioned includes the difficulty in determining what the cost of each relevant characteristic on the map, and the costs of their possible combinations. The purpose of this study is to show how the prediction of these costs is made into new environments based on the prediction of structured data by defining functional learning areas between input and output, structured and arbitrary. The problem of learning in question is usually formulated as a convex optimization problem of maximum margin very similar to the formulation of multiclass support vector machines. A solution technic was performed through implementation of the algorithm MMP (Maximum Margin Planning) (RATLIFF; BAGNELL; ZINKEVICH, 2006). As a contribution, two alternative algorithms were developed and implemented, the first named Structured Perceptron, and the second Structured Perceptron with Margin both methods of relaxation based formulation of the Perceptron. They were analyzed and compared. Posteriorly we have the exploitation of the environment by an intelligent agent using reinforcement learning techniques. This makes the whole process, from the environment analysis and discovery of cost to the exploitation and path planning, a complete learning process.

Les travaux présentés dans cette thèse relèvent de l'étude des méthodes de classification linéaires, c'est à dire l'étude de méthodes ayant pour but la catégorisation de données en différents groupes à partir d'un jeu d'exemples, préalablement étiquetés, disponible en amont et appelés ensemble d'apprentissage. En pratique, l'acquisition d'un tel ensemble d'apprentissage peut être difficile et/ou couteux, la catégorisation d'un exemple étant de fait plus ardu que l'obtention de dudit exemple. Cette disparité entre la disponibilité des données et notre capacité à constituer un ensemble d'apprentissage étiqueté a été un des problèmes centraux de l'apprentissage automatique et ce manuscrit s’intéresse à deux solutions usuellement considérées pour contourner ce problème : l'apprentissage en présence de données bruitées et l'apprentissage actif. / The works presented in this thesis fall within the general framework of linear classification, that is the problem of categorizing data into two or more classes based on on a training set of labelled data. In practice though acquiring labeled examples might prove challenging and/or costly as data are inherently easier to obtain than to label. Dealing with label scarceness have been a motivational goal in the machine learning literature and this work discuss two settings related to this problem: learning in the presence of noise and active learning.