La vitrine de diffusion des mémoires et thèses de l'ÉTS

Semi-supervised machine learning techniques for classification of evolving data in pattern recognition

Tencer, Lukas (2017). Semi-supervised machine learning techniques for classification of evolving data in pattern recognition. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Télécharger (278MB) | Prévisualisation


The amount of data recorded and processed over recent years has increased exponentially. To create intelligent systems that can learn from this data, we need to be able to identify patterns hidden in the data itself, learn these pattern and predict future results based on our current observations. If we think about this system in the context of time, the data itself evolves and so does the nature of the classification problem. As more data become available, different classification algorithms are suitable for a particular setting. At the beginning of the learning cycle when we have a limited amount of data, online learning algorithms are more suitable. When truly large amounts of data become available, we need algorithms that can handle large amounts of data that might be only partially labeled as a result of the bottleneck in the learning pipeline from human labeling of the data.

An excellent example of evolving data is gesture recognition, and it is present throughout our work. We need a gesture recognition system to work fast and with very few examples at the beginning. Over time, we are able to collect more data and the system can improve. As the system evolves, the user expects it to work better and not to have to become involved when the classifier is unsure about decisions. This latter situation produces additional unlabeled data. Another example of an application is medical classification, where experts’ time is a rare resource and the amount of received and labeled data disproportionately increases over time.

Although the process of data evolution is continuous, we identify three main discrete areas of contribution in different scenarios. When the system is very new and not enough data are available, online learning is used to learn after every single example and to capture the knowledge very fast. With increasing amounts of data, offline learning techniques are applicable. Once the amount of data is overwhelming and the teacher cannot provide labels for all the data, we have another setup that combines labeled and unlabeled data. These three setups define our areas of contribution; and our techniques contribute in each of them with applications to pattern recognition scenarios, such as gesture recognition and sketch recognition.

An online learning setup significantly restricts the range of techniques that can be used. In our case, the selected baseline technique is the Evolving TS-Fuzzy Model. The semi-supervised aspect we use is a relation between rules created by this model. Specifically, we propose a transductive similarity model that utilizes the relationship between generated rules based on their decisions about a query sample during the inference time. The activation of each of these rules is adjusted according to the transductive similarity, and the new decision is obtained using the adjusted activation. We also propose several new variations to the transductive similarity itself.

Once the amount of data increases, we are not limited to the online learning setup, and we can take advantage of the offline learning scenario, which normally performs better than the online one because of the independence of sample ordering and global optimization with respect to all samples. We use generative methods to obtain data outside of the training set. Specifically, we aim to improve the previously mentioned TS Fuzzy Model by incorporating semi-supervised learning in the offline learning setup without unlabeled data. We use the Universum learning approach and have developed a method called UFuzzy. This method relies on artificially generated examples with high uncertainty (Universum set), and it adjusts the cost function of the algorithm to force the decision boundary to be close to the Universum data. We were able to prove the hypothesis behind the design of the UFuzzy classifier that Universum learning can improve the TS Fuzzy Model and have achieved improved performance on more than two dozen datasets and applications.

With increasing amounts of data, we use the last scenario, in which the data comprises both labeled data and additional non-labeled data. This setting is one of the most common ones for semi-supervised learning problems. In this part of our work, we aim to improve the widely popular tecjniques of self-training (and its successor help-training) that are both meta-frameworks over regular classifier methods but require probabilistic representation of output, which can be hard to obtain in the case of discriminative classifiers. Therefore, we develop a new algorithm that uses the modified active learning technique Query-by-Committee (QbC) to sample data with high certainty from the unlabeled set and subsequently embed them into the original training set. Our new method allows us to achieve increased performance over both a range of datasets and a range of classifiers.

These three works are connected by gradually relaxing the constraints on the learning setting in which we operate. Although our main motivation behind the development was to increase performance in various real-world tasks (gesture recognition, sketch recognition), we formulated our work as general methods in such a way that they can be used outside a specific application setup, the only restriction being that the underlying data evolve over time. Each of these methods can successfully exist on its own. The best setting in which they can be used is a learning problem where the data evolve over time and it is possible to discretize the evolutionary process.

Overall, this work represents a significant contribution to the area of both semi-supervised learning and pattern recognition. It presents new state-of-the-art techniques that overperform baseline solutions, and it opens up new possibilities for future research.

Titre traduit

Techniques semi-supervisées d'apprentissage machine pour la classification des données en évolution en reconnaissance de formes

Résumé traduit

La quantité de données enregistrées et traitées au cours des dernières années a augmenté de façon exponentielle. Pour créer des systèmes intelligents qui peuvent apprendre de ces données, nous devons être en mesure d’identifier les modèles cachés dans les données elles-mêmes, apprendre ces modèles et prédire les résultats futurs sur la base de nos observations actuelles. Si nous pensons à ce système dans un contexte temporel, les données elles-mêmes évoluent, tout comme la nature du problème de classification. Lorsque plus de données deviennent disponibles, différents algorithmes de classification sont adaptés à un contexte particulier. Au début de la phase d’apprentissage lorsque nous disposons d’une quantité limitée de données d’entrainement, les algorithmes d’apprentissage en ligne sont plus appropriés. Lorsque de grandes quantités de données deviennent disponibles, nous avons besoin d’algorithmes qui peuvent traiter de grandes quantités de données partiellement étiquetées dues à la limitation d’étiquetage manuel.

Un exemple typique où les données évoluent est la reconnaissance de geste. Ce dernier exemple est présent tout au long de notre travail. Nous avons besoin des systèmes de reconnaissance des gestes pour fonctionner rapidement et avec très peu d’échantillons au début. Au cours du temps, nous sommes en mesure de collecter plus de données pour que la performance du système s’améliore. À mesure que le système évolue, l’utilisateur s’attend à ce qu’il fonctionne mieux et qu’il n’ait plus besoin de s’impliquer lorsque le classificateur est incertain quant aux décisions. Dans cette dernière situation des données supplémentaires non étiquetées sont alors produites. Un autre exemple typique d’une application est la classification de données médicales, où le temps des experts (cliniciens, chirurgiens) est une ressource rare et la quantité de données reçues et étiquetées augmente de façon déséquilibrée au cours du temps. Bien que le processus de l’évolution des données soit continu, nous pouvons identifier trois contributions dans différents scénarios. Lorsque le système est nouveau avec peu de données, l’apprentissage en ligne est utilisé pour apprendre après chaque échantillon et capturer les connaissances très rapidement. Avec l’augmentation de quantités de données, les techniques d’apprentissage hors ligne deviennent davanatge applicables. Une fois que la quantité de données est massive et que le processus d’étiquetage ne couvre pas toutes les données, nous avons une autre configuration qui combine les données étiquetées et celles non étiquetées. Ces trois configurations définissent nos axes de contributions avec comme applications la reconnaissance des gestes et la reconnaissance de croquis en ligne.

La configuration d’apprentissage en ligne fait largement restreindre la gamme de techniques qui peuvent être utilisées. Pour les applications que nous visons, la technique de base que nous avons adopté est le modèle évolutif TS-Fuzzy (Evolving TS-Fuzzy Model). L’aspect semi-supervisé que nous utilisons est en fait la relation entre les règles créées par ce modèle. Plus précisément, nous proposons un modèle de similarité transductive qui utilise la relation entre les règles générées en fonction de leurs décisions sur un échantillon pendant le temps d’inférence. L’activation de chacune de ces règles est ajustée en fonction de la similarité transductive, et la nouvelle décision est obtenue en utilisant l’activation ajustée. Nous proposons également plusieurs nouvelles variantes de la similarité transductive elle-même.

Une fois la quantité de données devenue importante, nous outre-passons la configuration de l’apprentissage en ligne en bénéficiant du scénario d’apprentissage hors ligne, qui donne en général de meilleurs résultats à cause de l’indépendance de l’ordre des échantillons et l’optimisation globale par rapport à tous les échantillons. Nous utilisons des méthodes génératives pour obtenir des données hors de l’ensemble de données d’apprentissage. Plus précisément, nous visons à améliorer le modèle TS Fuzzy précédemment mentionné en incorporant l’apprentissage semi-supervisé dans la configuration de l’apprentissage hors ligne sans compter sur les données non étiquetées. Nous utilisons l’approche d’apprentissage ‘Universum’ et avons développé une méthode appelée UFuzzy. Cette méthode s’appuie sur des exemples générés artificiellement avec une incertitude élevée (ensemble Universum) et ajuste la fonction de coût de l’algorithme pour forcer la limite de décision pour être proche des données Universum. Nous étions en mesure de prouver l’hypothèse derrière la conception du classificateur UFuzzy que l’apprentissage Universum peut améliorer le TS Fuzzy Model et avons obtenu des performances améliorées pour plus de deux douzaines de base de données et d’applications.

Avec l’augmentation de la quantité de données, on utilise le dernier scénario, dans lequel les données comprennent à la fois des données étiquetées et des données non étiquetées supplémentaires. Dans cette partie de notre travail, nous visons à améliorer les techniques d’autoapprentissage (self-training) largement populaires, et leur successeur aide-à-l‘apprentissage (help-training en anglais), qui sont à la fois des méta-cadre de travail (meta-frameworks) audessus des méthodes régulières de classification mais qui exigent une représentation probabiliste des résultats de classification, ce qui peut être difficile à obtenir par les classificateurs discriminatifs.

Par conséquent, nous proposoons un nouvel algorithme qui utilise la technique d’apprentissage actif modifié requête-par-comité (QbC ou Query-by-Committee) pour échantillonner les données avec une grande certitude à partir de l’ensemble non étiqueté et ensuite les intégrer dans l’ensemble d’entraînement original. Notre nouvelle méthode nous permet d’obtenir des performances accrues sur une large gamme de base de données et de classificateurs.

Ces trois travaux sont connectés en relaxant graduellement les contraintes sur le cadre d’apprentissage dans lequel nous opérons. Bien que notre motivation principale était d’améliorer les performances dans diverses tâches du monde réel (reconnaissance de gestes, reconnaissance de croquis), nous avons formulé notre travail en tant que méthodes générales de telle sorte qu’elles puissent être utilisées en dehors d’une configuration d’application spécifique, avec la seule spécificication que les données sous-jacentes évoluent au cours du temps. Chacune de ces méthodes peut exister séparément avec succès. La meilleure configuration dans laquelle ells peuvent être utilisées est le problème d’apprentissage où les données évoluent avec le temps. Il est également possible de discrétiser le processus évolutif.

Dans l’ensemble, ce travail représente une contribution importante dans le domaine de l’apprentissage semi-supervisé et de la reconnaissance des formes. Il présente de nouvelles methods s’apparentant au contexte de collecte de données et dont la performance dépasse celle des techniques de l’état de l’art. Ce travail ouvre également de nouvelles possibilités pour la recherche future.

Type de document: Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires: "Manuscript-based thesis presented to École de technologie supérieure in partial fulfillment for the degree of doctor of philosophy". Bibliographie : pages 175-197.
Mots-clés libres: Apprentissage automatique. Classification automatique (Statistique) Reconnaissance optique des formes (Informatique) Gestes. Données volumineuses. Systèmes flous. Systèmes de classeurs. croquis, incrémental, semi-supervisé, apprentissage par ordinateur, apprentissage en ligne, similarité transductive, modèles incrémental, apprentissage actif, sommet-formation, apprentissage universum, reconnaissance gestuelle, reconnaissance de sketch, reconnaissance d’objets
Directeur de mémoire/thèse:
Directeur de mémoire/thèse
Cheriet, Mohamed
Programme: Doctorat en génie > Génie
Date de dépôt: 27 nov. 2017 15:40
Dernière modification: 27 nov. 2017 15:40

Actions (Identification requise)

Dernière vérification avant le dépôt Dernière vérification avant le dépôt


Plus de statistique...