Multiple instance learning under real-world conditions

Carbonneau, Marc-André (2017). Multiple instance learning under real-world conditions. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation	PDF Télécharger (3MB) | Prévisualisation
Prévisualisation	PDF Télécharger (1MB) | Prévisualisation

Résumé

Multiple instance learning (MIL) is a form of weakly-supervised learning that deals with data arranged in sets called bags. In MIL problems, a label is provided for bags, but not for each individual instance in the bag. Like other weakly-supervised frameworks, MIL is useful in situations where obtaining labels is costly. It is also useful in applications where instance labels cannot be observed individually. MIL algorithms learn from bags, however, prediction can be performed at instance- and bag-level. MIL has been used in several applications from drug activity prediction to object localization in image. Real-world data poses many challenges to MIL methods. These challenges arise from different problem characteristics that are sometimes not well understood or even completely ignored. This causes MIL methods to perform unevenly and often fail in real-world applications.

In this thesis, we propose methods for both classification levels under different working assumptions. These methods are designed to address challenging problem characteristics that arise in real-world applications. As a first contribution, we survey these characteristics that make MIL uniquely challenging. Four categories of characteristics are identified: the prediction level, the composition of bags, the data distribution types and the label ambiguity. Each category is analyzed and related state-of-the-art MIL methods are surveyed. MIL applications are examined in light of these characteristics and extensive experiments are conducted to show how these characteristics affect the performance of MIL methods. From these analyses and experiments, several conclusions are drawn and future research avenues are identified.

Then, as a second contribution, we propose a method for bag classification which relies on the identification of positive instances to train an ensemble of instance classifiers. The bag classifier uses the predictions made on instances to infer bag labels. The method identifies positive instances by projecting the instances into random subspaces. Clustering is performed on the data in these subspaces and positive instances are probabilistically identified based on the bag label of instances in clusters. Experiments show that the method achieves state-of-theart performance while being robust to several characteristics identified in the survey.

In some applications, the instances cannot be assigned to a positive or negative class. Bag classes are defined by a composition of different types of instances. In such cases, interrelations between instances convey the information used to discriminate between positive and negative bags. As a third contribution, we propose a bag classification method that learns under these conditions. The method is a applied to predict speaker personality from speech signals represented as bags of instances. A sparse dictionary learning algorithm is used to learn a dictionary and encode instances. Encoded instances are embedded in a single feature vector summarizing the speech signal. Experimental results on real-world data reveal that the proposed method yields state-of-the-art accuracy results while requiring less complexity than commonly used methods in the field.

Finally, we propose two methods for querying bags in a multiple instance active learning (MIAL) framework. In this framework the objective is to train a reliable instance classifier using a minimal amount of labeled data. Single instance methods are suboptimal is this framework because they do not account the bag structure of MIL. The proposed methods address the problem from different angles. One aims at directly refining the decision boundary, while the other leverage instance and bag labels to query instances in the most promising clusters. Experiments are conducted in an inductive and transductive setting. Results on data from 3 application domains show that leveraging bag structure in this MIAL framework is important to effectively reduce the number of queries necessary to attain a high level of classification accuracy.

This thesis shows that real-world MIL problems pose a wide range of challenges. After an in-depth analysis, we show experimentally that these challenges have a profound impact on the performance of MIL algorithms. We propose methods to address some of these challenges and validate them on real-world data sets. We also identify future directions for research and remaining open problems.

Titre traduit

Apprentissage par instances multiples dans des conditions réelles

Résumé traduit

L’apprentissage par instances multiples (AIM) est un type d’apprentissage machine avec faible supervision. Les données sont groupées en ensembles que l’on nomme sacs. Une etiquette est donnée pour chacun des sacs. Par contre, les données individuelles dans les sacs, appellees instances, ne sont pas étiquetées. Comme pour les autres types d’apprentissages faiblement supervisés, l’AIM est utile quand il est coûteux même impossible d’obtenir des etiquettes pour chacune des instances. Dans tous les cas, on apprendra à partir de données arranges en sacs. Cependant, la tâche du classificateur peut être de prédire la classe des sacs ou des instances. Cette formulation se révèle utile dans plusieurs situations passant de la prediction des effets de médicaments à la reconnaissance visuelle d’objets. De par leur forme particulière, les problèmes d’AIM comportent plusieurs difficultés qui sont trop souvent mal comprises ou inconnues. Il en résulte que plusieurs méthodes AIM sont mal adaptées aux données réelles et présentent des performances inégales dependant des applications.

Dans cette thèse, des algorithmes de classification par AIM seront proposés pour la classification de sacs et d’instances, et ce, selon différentes suppositions sur les données. Chacune de ces méthodes est conçue pour être utilisée dans des situations réelles comportant des caractéristiques et défis particuliers. Comme première contribution, ces caractéristiques propres à l’AIM seront analysées et groupées en quatre catégories: le niveau auquel les prédictions sont faites, la composition des sacs, les types de distribution de données et l’ambiguïté sur les étiquettes. Chacune de ces catégories sera analysée en profondeur et les méthodes de pointe proposes pour ces cas spécifiques seront recensées. Ensuite, les applications typiques de l’AIM seront revues du point de vue de ces caractéristiques. Des expériences sont menées afin de montrer comment les caractéristiques affectent les performances de 16 types de méthodes d’AIM. Ces expérimentations et analyses permettent de tirer plusieurs conclusions pour choisir et tester des méthodes par AIM. Finalement, plusieurs sujets pour des recherches futures sont identifiés.

La seconde contribution est une méthode pour la classification de sacs basée sur l’identification probabiliste d’instances positives dans la base d’entraînement. Suite à ce processus d’identification, on entraîne un ensemble de classificateurs pour la classification d’instances. Les predictions faites sur les instances sont ensuite combinées pour prédire la classe des sacs. Pour l’identification des instances positives, les données sont projetées dans plusieurs sous-espaces aléatoires. Dans ces sous-espaces, les instances sont regroupées et les étiquettes de sacs dans chaque groupe sont utilisées pour juger de la nature des instances. Les expériences montrent que cet algorithme obtient des performances comparables à l’état de l’art tout en étant advantage robuste à plusieurs des caractéristiques identifiées au chapitre précédent.

Il existe des applications pour lesquelles les instances ne peuvent pas être attribuées à une classe positive ou négative. En fait, les classes des sacs dépendent de la composition de ceux-ci. Dans ces cas-là, ce sont les relations entre les instances qui portent l’information permettant de distinguer entre les classes de sacs. À titre de troisième contribution, une méthode pour la classification de sacs dans ces conditions est proposée. La méthode sert à prédire la personnalité d’un locuteur à partir de la voix. Cette méthode représente le spectrogramme d’un segment audio par un sac d’instances. Les parties du spectrogramme correspondent aux instances et sont encodées en utilisant un encodage creux (sparse). Une fois encodées, les instances sont agglomérées pour obtenir un vecteur de caractéristiques unique représentant le segment audio en entier. Ces vecteurs de caractéristiques sont utilisés par le classificateur de sac. Des experiences utilisant des données réelles montrent que la méthode obtient des résultats comparables à l’état de l’art tout en étant moins complexe à implémenter que les méthodes couramment utilisées dans le domaine.

Finalement, deux méthodes sont proposées pour choisir des sacs à faire étiqueter par un oracle dans un contexte d’apprentissage actif. Le but de l’apprentissage actif est d’entraîner un classificateur fiable en utilisant un minimum de données étiquetées. La structure des données en sacs rend sous-optimales les méthodes proposées pour l’apprentissage à instance simple. Les deux méthodes proposées tiennent compte de la structure en sacs mais abordent le problem différemment. La première tente de raffiner directement la frontière de décision du classificateur en portant son attention sur les instances près de celle-ci. La seconde méthode étudie la structure des instances dans l’espace afin d’identifier les régions les plus informatives. Le degree de désaccord entre les étiquettes des instances et des sacs et la proportion d’instances dont la classe est inconnue dans une région servent à déterminer la pertinence de celle-ci. Des experiences sont conduites dans un contexte d’apprentissage par induction et transduction pour trois domaines d’application. Ces expériences montrent la nécessité de considérer la structure en sacs dans un contexte d’AIM en réduisant la quantité d’étiquettes nécessaires pour l’obtention de bonnes performances de classification.

Cette thèse démontre que les problèmes d’AIM comportent une grande variété de défis et problématiques. Après une analyse en profondeur de ces défis et problématiques, des experiences sont menées afin de mesurer leur impact sur les performances des méthodes AIM. Ensuite, des méthodes sont proposées spécialement pour solutioner certaines de ces problématiques. Les méthodes sont validées expérimentalement avec des données provenant d’applications réelles. Finalement, des avenues pour recherches futures sont identifiées.

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 225-249.
Mots-clés libres:	Apprentissage automatique. Classification automatique (Statistique) Systèmes de classeurs. apprentissage, faiblement, instance, multiple, supervisé
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Gagnon, Ghyslain
Codirecteur:	Codirecteur Granger, Éric
Programme:	Doctorat en génie > Génie
Date de dépôt:	28 févr. 2018 17:18
Dernière modification:	26 juin 2018 16:14
URI:	https://espace.etsmtl.ca/id/eprint/2011

Gestion Actions (Identification requise)

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