L'émergence de l'informatique nomade a rendu indispensable l'utilisation des interfaces orientées stylo sur des petits périphériques mobiles disposant de ressources limitées : l'utilisateur écrit et dessine directement des textes, des croquis, des commandes, etc. sur l'écran tactile du système. Pour permettre une mise en oeuvre conviviale et efficace de ces nouvelles modalités de communication, il est nécessaire de concevoir des moteurs de reconnaissance robustes et performants pour interpréter l'écriture manuscrite et les tracés graphiques. L'objectif de ces travaux est donc d'améliorer les performances des systèmes de reconnaissance existants en étudiant deux axes de recherches, le rejet et l'adaptation. Le premier axe de recherche, le rejet, permet de décider si la réponse du classifieur peut être considérée comme pertinente ou non. Pour cela il s'agit de délimiter le domaine de validité des connaissances du classifieur. Nous définissons différentes notions de rejet qui représentent différents cas d'utilisation du rejet : - le rejet de distance : la forme à reconnaître ne correspond pas du tout à une forme que le classifieur a appris à reconnaître, la réponse du classifieur ne peut donc être pertinente et il faut la rejeter ; - le rejet d'ambiguïté : la forme peut appartenir à deux classes distinctes, le classifieur ne peut pas prendre de décision sûre, il faut donc rejeter la forme. Pour mettre en oeuvre ces rejets, nous définissons une option générique de rejet utilisant la notion de fonctions de confiance qui permet, grâce à des seuils, de décider du rejet. Nous proposons un algorithme générique nommé AMTL pour fixer ces seuils avec ou sans contre-exemples disponibles. Nous démontrons les capacités de généralisation de notre approche en la comparant avec les solutions plus classiques. Notre approche est particulièrement efficace dans un contexte de ressources limitées. Le principe du second axe de recherche, l'adaptation, est de spécialiser automatiquement un système de reconnaissance de caractères conçu pour reconnaître l'écriture de n'importe quel utilisateur (système omni-scripteur) en un système spécialisé dans la reconnaissance de l'écriture d'une seule personne (système mono-scripteur), l'utilisateur principal du périphérique mobile. Cette adaptation se fait à la volée, c'est-à-dire au fur et à mesure de l'utilisation du système par le scripteur. Nous proposons une approche nommée ADAPT permettant de réaliser cette adaptation sur les systèmes d'inférence floue. Les prototypes flous du système sont déplacés, déformés et crées à la volée en tenant compte de tous les paramètres du classifieur. Pour améliorer encore l'efficacité de l'adaptation, nous proposons d'augmenter la quantité de données disponibles lors de l'adaptation pour éviter à l'utilisateur de saisir plusieurs dizaines de fois chaque caractère. Pour cela nous synthétisons de nouveaux caractères à partir de ceux déjà entrés par l'utilisateur en considérant les propriétés particulières de l'écriture manuscrite. Pour valider nos approches, nous proposons une série d'expérimentations dans différents contextes, depuis des conditions expérimentales idéales jusqu'à une utilisation en conditions réelles sur un périphérique mobile.

L’internet et les nouvelles formes de média de communication, d’information, et de divertissement ont entraîné une croissance massive de la quantité des données numériques. Le traitement et l’interprétation automatique de ces données permettent de créer des bases de connaissances, de rendre les recherches plus efficaces et d’effectuer des recherches sur les médias sociaux. Les travaux de recherche sur le traitement automatique du langage naturel concernent la conception et le développement d’algorithmes, qui permettent aux ordinateurs de traiter automatiquement le langage naturel dans les textes, les contenus audio, les images ou les vidéos, pour des tâches spécifiques. De par la complexité du langage humain, le traitement du langage naturel sous forme textuelle peut être divisé en 4 niveaux : la morphologie, la syntaxe, la sémantique et la pragmatique. Les technologies actuelles du traitement du langage naturel ont eu de grands succès sur les tâches liées auxdeux premiers niveaux, ce qui a permis la commercialisation de beaucoup d’applications comme les moteurs de recherche. Cependant, les moteurs de recherches avancés (structurels) nécessitent une interprétation du langage plus avancée. L’extraction d’information consiste à extraire des informations structurelles à partir des ressources non annotées ou semi-annotées, afin de permettre des recherches avancées et la création automatique des bases de connaissances. Cette thèse étudie le problème d’extraction d’information dans le domaine spécifique de l’extraction des événements biomédicaux. Nous proposons une solution efficace, qui fait un compromis entre deux types principaux de méthodes proposées dans la littérature. Cette solution arrive à un bon équilibre entre la performance et la rapidité, ce qui la rend utilisable pour traiter des données à grande échelle. Elle a des performances compétitives face aux meilleurs modèles existant avec une complexité en temps de calcul beaucoup plus faible. Lors la conception de ce modèle, nous étudions également les effets des différents classifieurs qui sont souvent proposés pour la résolution des problèmes de classification multi-classe. Nous testons également deux méthodes permettant d’intégrer des représentations vectorielles des mots appris par apprentissage profond (deep learning). Même si les classifieurs différents et l’intégration des vecteurs de mots n’améliorent pas grandement la performance, nous pensons que ces directions de recherche ont du potentiel et sont prometteuses pour améliorer l’extraction d’information. / Internet as well as all the modern media of communication, information and entertainment entails a massive increase of digital data quantities. Automatically processing and understanding these massive data enables creating large knowledge bases, more efficient search, social medial research, etc. Natural language processing research concerns the design and development of algorithms that allow computers to process natural language in texts, audios, images or videos automatically for specific tasks. Due to the complexity of human language, natural language processing of text can be divided into four levels: morphology, syntax, semantics and pragmatics. Current natural language processing technologies have achieved great successes in the tasks of the first two levels, leading to successes in many commercial applications such as search. However, advanced structured search engine would require computers to understand language deeper than at the morphology and syntactic levels. Information extraction is designed to extract meaningful structural information from unannotated or semi-annotated resources to enable advanced search and automatically create knowledge bases for further use. This thesis studies the problem of information extraction in the specific domain of biomedical event extraction. We propose an efficient solution, which is a trade-off between the two main trends of methods proposed in previous work. This solution reaches a good balance point between performance and speed, which is suitable to process large scale data. It achieves competitive performance to the best models with a much lower computational complexity. While designing this model, we also studied the effects of different classifiers that are usually proposed to solve the multi-class classification problem. We also tested two simple methods to integrate word vector representations learned by deep learning method into our model. Even if different classifiers and the integration of word vectors do not greatly improve the performance, we believe that these research directions carry some promising potential for improving information extraction.

La théorie statistique de l’apprentissage est un domaine de la statistique inférentielle dont les fondements ont été posés par Vapnik à la fin des années 60. Il est considéré comme un sous-domaine de l’intelligence artificielle. Dans l’apprentissage automatique, les machines à vecteurs de support (SVM) sont un ensemble de techniques d’apprentissage supervisé destinées à résoudre des problèmes de discrimination et de régression. Dans cette thèse, notre objectif est de proposer deux nouveaux problèmes d’aprentissagestatistique: Un portant sur la conception et l’évaluation d’une extension des SVM multiclasses et un autre sur la conception d’un nouveau noyau pour les machines à vecteurs de support. Dans un premier temps, nous avons introduit une nouvelle machine à noyau pour la reconnaissance de modèle multi-classe: la machine à vecteur de support hyperbolique. Géometriquement, il est caractérisé par le fait que ses surfaces de décision dans l’espace de redescription sont définies par des fonctions hyperboliques. Nous avons ensuite établi ses principales propriétés statistiques. Parmi ces propriétés nous avons montré que les classes de fonctions composantes sont des classes de Glivenko-Cantelli uniforme, ceci en établissant un majorant de la complexité de Rademacher. Enfin, nous établissons un risque garanti pour notre classifieur.Dans un second temps, nous avons créer un nouveau noyau s’appuyant sur la transformation de Fourier d’un modèle de mélange gaussien. Nous procédons de la manière suivante: d’abord, chaque classe est fragmentée en un nombre de sous-classes pertinentes, ensuite on considère les directions données par les vecteurs obtenus en prenant toutes les paires de centres de sous-classes d’une même classe. Parmi celles-ci, sont exclues celles permettant de connecter deux sous-classes de deux classes différentes. On peut aussi voir cela comme la recherche d’invariance par translation dans chaque classe. Nous l’avons appliqué avec succès sur plusieurs jeux de données dans le contexte d’un apprentissage automatique utilisant des machines à vecteurs support multi-classes. / Statistical learning theory is a field of inferential statistics whose foundations were laid by Vapnik at the end of the 1960s. It is considered a subdomain of artificial intelligence. In machine learning, support vector machines (SVM) are supervised learning models with associated learning algorithms that analyze data used for classification and regression analysis. In this thesis, our aim is to propose two new statistical learning problems : one on the conception and evaluation of a multi-class SVM extension and another on the design of a new kernel for support vectors machines. First, we introduced a new kernel machine for multi-class pattern recognition : the hyperbolic support vector machine. Geometrically, it is characterized by the fact that its decision boundaries in the feature space are defined by hyperbolic functions. We then established its main statistical properties. Among these properties we showed that the classes of component functions are uniform Glivenko-Cantelli, this by establishing an upper bound of the Rademacher complexity. Finally, we establish a guaranteed risk for our classifier. Second, we constructed a new kernel based on the Fourier transform of a Gaussian mixture model. We proceed in the following way: first, each class is fragmented into a number of relevant subclasses, then we consider the directions given by the vectors obtained by taking all pairs of subclass centers of the same class. Among these are excluded those allowing to connect two subclasses of two different classes. We can also see this as the search for translation invariance in each class. It successfully on several datasets in the context of machine learning using multiclass support vector machines.

Dans le cadre de cette thèse, notre intérêt se porte sur la précision de la classification et l'optimalité du parcours de l'espace de recherche. L'objectif recherché est d'améliorer la précision de classification en étudiant les différents types de règles et de réduire l'espace de recherche des règles. Nous avons proposé une approche de classification IGARC permettant de générer un classifieur formé d'une base de règles de classification génériques permettant de mieux classer les nouveaux objets grâce à la flexibilité de petites prémisses caractérisant ces règles. De plus cette approche manipule un nombre réduit de règles en comparaison avec les autres approches de classification associative en se basant sur le principe des bases génériques des règles associatives. Une étude expérimentale inter et intra approches a été faite sur 12 bases Benchmark.Nous avons également proposé une approche Afortiori. Notre travail a été motivé par la recherche d'un algorithme efficace permettant l'extraction des règles génériques aussi bien fréquentes que rares de classification en évitant la génération d'un grand nombre de règles. L'algorithme que nous proposons est particulièrement intéressant dans le cas de bases de données bien spécifiques composées d'exemples positifs et négatifs et dont le nombre d'exemples négatifs est très réduit par rapport aux exemples positifs. La recherche des règles se fait donc sur les exemples négatifs afin de déterminer des règles qui ont un faible support et ce même par rapport à la population des exemples positifs et dont l'extraction pourrait être coûteuse. / Within the framework of this thesis, our interest is focused on classification accuracy and the optimalité of the traversal of the search. we introduced a new direct associative classification method called IGARC that extracts directly a classifier formed by generic associative classification rules from a training set in order to reduce the number of associative classification rules without jeopardizing the classification accuracy. Carried out experiments outlined that IGARC is highly competitive in comparison with popular classification methods.We also introduced a new classification approach called AFORTIORI. We address the problem of generating relevant frequent and rare classification rules. Our work is motivated by the long-standing open question of devising an efficient algorithm for finding rules with low support. A particularly relevant field for rare item sets and rare associative classification rules is medical diagnosis. The proposed approach is based on the cover set classical algorithm. It allows obtaining frequent and rare rules while exploring the search space in a depth first manner. To this end, AFORTIORI adopts the covering set algorithm and uses the cover measure in order to guide the traversal of the search space and to generate the most interesting rules for the classification framework even rare ones. We describe our method and provide comparisons with common methods of associative classification on standard benchmark data set.

Nos travaux concernent la reconnaissance de l'écriture manuscrite qui est l'un des domaines de prédilection pour la reconnaissance des formes et les algorithmes d'apprentissage. Dans le domaine de l'écriture en-ligne, les applications concernent tous les dispositifs de saisie permettant à un usager de communiquer de façon transparente avec les systèmes d'information. Dans ce cadre, nos travaux apportent une contribution pour proposer une nouvelle architecture de reconnaissance de mots manuscrits sans contrainte de style. Celle-ci se situe dans la famille des approches hybrides locale/globale où le paradigme de la segmentation/reconnaissance va se trouver résolu par la complémentarité d'un système de reconnaissance de type discriminant agissant au niveau caractère et d'un système par approche modèle pour superviser le niveau global. Nos choix se sont portés sur des Séparateurs à Vastes Marges (SVM) pour le classifieur de caractères et sur des algorithmes de programmation dynamique, issus d'une modélisation par Modèles de Markov Cachés (HMM). Cette combinaison SVM/HMM est unique dans le domaine de la reconnaissance de l'écriture manuscrite. Des expérimentations ont été menées, d'abord dans un cadre de reconnaissance de caractères isolés puis sur la base IRONOFF de mots cursifs. Elles ont montré la supériorité des approches SVM par rapport aux solutions à bases de réseaux de neurones à convolutions (Time Delay Neural Network) que nous avions développées précédemment, et leur bon comportement en situation de reconnaissance de mots.

.

Dans ce document, nous présentons une nouvelle approche en apprentissage machine pour la classification. Le cadre que nous proposons est basé sur des circuits booléens, plus précisément le classifieur produit par notre algorithme a cette forme. L’utilisation des bits et des portes logiques permet à l’algorithme d’apprentissage et au classifieur d’utiliser des opérations vectorielles binaires très efficaces. La qualité du classifieur, produit par notre approche, se compare très favorablement à ceux qui sont produits par des techniques classiques, à la fois en termes d’efficacité et de précision. En outre, notre approche peut être utilisée dans un contexte où la confidentialité est une nécessité, par exemple, nous pouvons classer des données privées. Ceci est possible car le calcul ne peut être effectué que par des circuits booléens et les données chiffrées sont quantifiées en bits. De plus, en supposant que le classifieur a été déjà entraîné, il peut être alors facilement implémenté sur un FPGA car ces circuits sont également basés sur des portes logiques et des opérations binaires. Par conséquent, notre modèle peut être facilement intégré dans des systèmes de classification en temps réel. / In this document we present a novel approach in machine learning for classification. The framework we propose is based on boolean circuits, more specifically the classifier produced by our algorithm has that form. Using bits and boolean gates enable the learning algorithm and the classifier to use very efficient boolean vector operations. The accuracy of the classifier we obtain with our framework compares very favourably with those produced by conventional techniques, both in terms of efficiency and accuracy. Furthermore, the framework can be used in a context where information privacy is a necessity, for example we can classify private data. This can be done because computation can be performed only through boolean circuits as encrypted data is quantized in bits. Moreover, assuming that the classifier was trained, it can then be easily implemented on FPGAs (i.e., Field-programmable gate array) as those circuits are also based on logic gates and bitwise operations. Therefore, our model can be easily integrated in real-time classification systems.

Dans l'apprentissage machine, la classification est le processus d’assigner une nouvelle observation à une certaine catégorie. Les classifieurs qui mettent en œuvre des algorithmes de classification ont été largement étudié au cours des dernières décennies. Les classifieurs traditionnels sont basés sur des algorithmes tels que le SVM et les réseaux de neurones, et sont généralement exécutés par des logiciels sur CPUs qui fait que le système souffre d’un manque de performance et d’une forte consommation d'énergie. Bien que les GPUs puissent être utilisés pour accélérer le calcul de certains classifieurs, leur grande consommation de puissance empêche la technologie d'être mise en œuvre sur des appareils portables tels que les systèmes embarqués. Pour rendre le système de classification plus léger, les classifieurs devraient être capable de fonctionner sur un système matériel plus compact au lieu d'un groupe de CPUs ou GPUs, et les classifieurs eux-mêmes devraient être optimisés pour ce matériel. Dans ce mémoire, nous explorons la mise en œuvre d'un classifieur novateur sur une plate-forme matérielle à base de FPGA. Le classifieur, conçu par Alain Tapp (Université de Montréal), est basé sur une grande quantité de tables de recherche qui forment des circuits arborescents qui effectuent les tâches de classification. Le FPGA semble être un élément fait sur mesure pour mettre en œuvre ce classifieur avec ses riches ressources de tables de recherche et l'architecture à parallélisme élevé. Notre travail montre que les FPGAs peuvent implémenter plusieurs classifieurs et faire les classification sur des images haute définition à une vitesse très élevée. / In the machine learning area, classification is a process of mapping a new observation to a certain category. Classifiers which implement classification algorithms have been studied widely over the past decades. Traditional classifiers are based on algorithms such as SVM and neural nets, and are usually run by software on CPUs which cause the system to suffer low performance and high power consumption. Although GPUs can be used to accelerate the computation of some classifiers, its high power consumption prevents the technology from being implemented on portable devices such as embedded systems or wearable hardware. To make a lightweight classification system, classifiers should be able to run on a more compact hardware system instead of a group of CPUs/GPUs, and classifiers themselves should be optimized to fit that hardware. In this thesis, we explore the implementation of a novel classifier on a FPGA-based hardware platform. The classifier, devised by Alain Tapp (Université de Montréal), is based on a large amount of look-up tables that form tree-structured circuits to do classification tasks. The FPGA appears to be a tailor-made component to implement this classifier with its rich resources of look-up tables and the highly parallel architecture. Our work shows that a single FPGA can implement multiple classifiers to do classification on high definition images at a very high speed.

No description available.

La maintenance du logiciel est une phase très importante du cycle de vie de celui-ci. Après les phases de développement et de déploiement, c’est celle qui dure le plus longtemps et qui accapare la majorité des coûts de l'industrie. Ces coûts sont dus en grande partie à la difficulté d’effectuer des changements dans le logiciel ainsi que de contenir les effets de ces changements. Dans cette perspective, de nombreux travaux ont ciblé l’analyse/prédiction de l’impact des changements sur les logiciels. Les approches existantes nécessitent de nombreuses informations en entrée qui sont difficiles à obtenir. Dans ce mémoire, nous utilisons une approche probabiliste. Des classificateurs bayésiens sont entraînés avec des données historiques sur les changements. Ils considèrent les relations entre les éléments (entrées) et les dépendances entre changements historiques (sorties). Plus spécifiquement, un changement complexe est divisé en des changements élémentaires. Pour chaque type de changement élémentaire, nous créons un classificateur bayésien. Pour prédire l’impact d’un changement complexe décomposé en changements élémentaires, les décisions individuelles des classificateurs sont combinées selon diverses stratégies. Notre hypothèse de travail est que notre approche peut être utilisée selon deux scénarios. Dans le premier scénario, les données d’apprentissage sont extraites des anciennes versions du logiciel sur lequel nous voulons analyser l’impact de changements. Dans le second scénario, les données d’apprentissage proviennent d’autres logiciels. Ce second scénario est intéressant, car il permet d’appliquer notre approche à des logiciels qui ne disposent pas d’historiques de changements. Nous avons réussi à prédire correctement les impacts des changements élémentaires. Les résultats ont montré que l’utilisation des classificateurs conceptuels donne les meilleurs résultats. Pour ce qui est de la prédiction des changements complexes, les méthodes de combinaison "Voting" et OR sont préférables pour prédire l’impact quand le nombre de changements à analyser est grand. En revanche, quand ce nombre est limité, l’utilisation de la méthode Noisy-Or ou de sa version modifiée est recommandée. / Software maintenance is one of the most important phases in the software life cycle. After the development and deployment phases, maintenance is a continuous phase that lasts until removing the software from operation. It is then the most costly phase. Indeed, those costs are due to the difficulty of implementing different changes in the system and to manage their impacts. In this context, much research work has targeted the problem of change impact analysis/prediction. The existent approaches require many inputs that are difficult to extract. In this Master thesis, we propose a probabilistic approach that uses Bayesian classifiers to predict the change impact. These classifiers are trained with historical data about changes. The consider the relations between the elements of a system (input), and the dependencies between the occurred changes (output). More precisely, a complex change in a system is divided into a set of elementary changes. For each type of elementary change, we create a classifier. To predict the impact of complex change, the individual decisions of each classifier are combined using different strategies. We evaluate our approach in two scenarios. In the first, we extract the learning data from the oldest versions of the same system. In the second scenario, the learn data comes from other systems to create the classifiers. This second scenario is interesting because it allows us to use our approach on systems without change histories. Our approach showed that it can predict the impact of elementary changes. The best results are obtained using the classifiers based on conceptual relations. For the prediction of complex changes by the combination of elementary decisions, the results are encouraging considering the few used inputs. More specifically, the voting method and the OR method predict better complex changes when the number of case to analyze is large. Otherwise, using the method Noisy-Or or its modified version is recommended when the number of cases is small.