Tesis sobre el tema "Similarity metric learning"

The success of many computer vision problems and machine learning algorithms critically depends on the quality of the chosen distance metrics or similarity functions. Due to the fact that the real-data at hand is inherently task- and data-dependent, learning an appropriate distance metric or similarity function from data for each specific task is usually superior to the default Euclidean distance or cosine similarity. This thesis mainly focuses on developing new metric and similarity learning models for three tasks: unconstrained face verification, person re-identification and kNN classification. Unconstrained face verification is a binary matching problem, the target of which is to predict whether two images/videos are from the same person or not. Concurrently, person re-identification handles pedestrian matching and ranking across non-overlapping camera views. Both vision problems are very challenging because of the large transformation differences in images or videos caused by pose, expression, occlusion, problematic lighting and viewpoint. To address the above concerns, two novel methods are proposed. Firstly, we introduce a new dimensionality reduction method called Intra-PCA by considering the robustness to large transformation differences. We show that Intra-PCA significantly outperforms the classic dimensionality reduction methods (e.g. PCA and LDA). Secondly, we propose a novel regularization framework called Sub-SML to learn distance metrics and similarity functions for unconstrained face verifica- tion and person re-identification. The main novelty of our formulation is to incorporate both the robustness of Intra-PCA to large transformation variations and the discriminative power of metric and similarity learning, a property that most existing methods do not hold. Working with the task of kNN classification which relies a distance metric to identify the nearest neighbors, we revisit some popular existing methods for metric learning and develop a general formulation called DMLp for learning a distance metric from data. To obtain the optimal solution, a gradient-based optimization algorithm is proposed which only needs the computation of the largest eigenvector of a matrix per iteration. Although there is a large number of studies devoted to metric/similarity learning based on different objective functions, few studies address the generalization analysis of such methods. We describe a novel approch for generalization analysis of metric/similarity learning which can deal with general matrix regularization terms including the Frobenius norm, sparse L1-norm, mixed (2, 1)-norm and trace-norm. The novel models developed in this thesis are evaluated on four challenging databases: the Labeled Faces in the Wild dataset for unconstrained face verification in still images; the YouTube Faces database for video-based face verification in the wild; the Viewpoint Invariant Pedestrian Recognition database for person re-identification; the UCI datasets for kNN classification. Experimental results show that the proposed methods yield competitive or state-of-the-art performance.

Le suivi d’objets multiples dans une scène est une tâche importante dans le domaine de la vision par ordinateur, et présente toujours de très nombreux verrous. Les objets doivent être détectés et distingués les uns des autres de manière continue et simultanée. Les approches «suivi par détection» sont largement utilisées, où la détection des objets est d’abord réalisée sur toutes les frames, puis le suivi est ramené à un problème d’association entre les détections d’un même objet et les trajectoires identifiées. La plupart des algorithmes de suivi associent des modèles de mouvement et des modèles d’apparence. Dans cette thèse, nous proposons un modèle de ré-identification basé sur l’apparence et utilisant l’apprentissage de métrique de similarité. Nous faisons tout d’abord appel à un réseau siamois profond pour apprendre un maping de bout en bout, des images d’entrée vers un espace de caractéristiques où les objets sont mieux discriminés. De nombreuses configurations sont évaluées, afin d’en déduire celle offrant les meilleurs scores. Le modèle ainsi obtenu atteint des résultats de ré-identification satisfaisants comparables à l’état de l’art. Ensuite, notre modèle est intégré dans un système de suivi d’objets multiples pour servir de guide d’apparence pour l’association des objets. Un modèle d’apparence est établi pour chaque objet détecté s’appuyant sur le modèle de ré-identification. Les similarités entre les objets détectés sont alors exploitées pour la classification. Par ailleurs, nous avons étudié la coopération et les interférences entre les modèles d’apparence et de mouvement dans le processus de suivi. Un couplage actif entre ces 2 modèles est proposé pour améliorer davantage les performances du suivi, et la contribution de chacun d’eux est estimée en continue. Les expérimentations menées dans le cadre du benchmark «Multiple Object Tracking Challenge» ont prouvé l’efficacité de nos propositions et donné de meilleurs résultats de suivi que l’état de l’art
Multiple object tracking, i.e. simultaneously tracking multiple objects in the scene, is an important but challenging visual task. Objects should be accurately detected and distinguished from each other to avoid erroneous trajectories. Since remarkable progress has been made in object detection field, “tracking-by-detection” approaches are widely adopted in multiple object tracking research. Objects are detected in advance and tracking reduces to an association problem: linking detections of the same object through frames into trajectories. Most tracking algorithms employ both motion and appearance models for data association. For multiple object tracking problems where exist many objects of the same category, a fine-grained discriminant appearance model is paramount and indispensable. Therefore, we propose an appearance-based re-identification model using deep similarity metric learning to deal with multiple object tracking in mono-camera videos. Two main contributions are reported in this dissertation: First, a deep Siamese network is employed to learn an end-to-end mapping from input images to a discriminant embedding space. Different metric learning configurations using various metrics, loss functions, deep network structures, etc., are investigated, in order to determine the best re-identification model for tracking. In addition, with an intuitive and simple classification design, the proposed model achieves satisfactory re-identification results, which are comparable to state-of-the-art approaches using triplet losses. Our approach is easy and fast to train and the learned embedding can be readily transferred onto the domain of tracking tasks. Second, we integrate our proposed re-identification model in multiple object tracking as appearance guidance for detection association. For each object to be tracked in a video, we establish an identity-related appearance model based on the learned embedding for re-identification. Similarities among detected object instances are exploited for identity classification. The collaboration and interference between appearance and motion models are also investigated. An online appearance-motion model coupling is proposed to further improve the tracking performance. Experiments on Multiple Object Tracking Challenge benchmark prove the effectiveness of our modifications, with a state-of-the-art tracking accuracy

Dans de nombreux problèmes d’apprentissage automatique et de reconnaissance des formes, il y a toujours un besoin de fonctions métriques appropriées pour mesurer la distance ou la similarité entre des données. La fonction métrique est une fonction qui définit une distance ou une similarité entre chaque paire d’éléments d’un ensemble de données. Dans cette thèse, nous proposons une nouvelle methode, Triangular Similarity Metric Learning (TSML), pour spécifier une fonction métrique de données automatiquement. Le système TSML proposée repose une architecture Siamese qui se compose de deux sous-systèmes identiques partageant le même ensemble de paramètres. Chaque sous-système traite un seul échantillon de données et donc le système entier reçoit une paire de données en entrée. Le système TSML comprend une fonction de coût qui définit la relation entre chaque paire de données et une fonction de projection permettant l’apprentissage des formes de haut niveau. Pour la fonction de coût, nous proposons d’abord la similarité triangulaire (Triangular Similarity), une nouvelle similarité métrique qui équivaut à la similarité cosinus. Sur la base d’une version simplifiée de la similarité triangulaire, nous proposons la fonction triangulaire (the triangular loss) afin d’effectuer l’apprentissage de métrique, en augmentant la similarité entre deux vecteurs dans la même classe et en diminuant la similarité entre deux vecteurs de classes différentes. Par rapport aux autres distances ou similarités, la fonction triangulaire et sa fonction gradient nous offrent naturellement une interprétation géométrique intuitive et intéressante qui explicite l’objectif d’apprentissage de métrique. En ce qui concerne la fonction de projection, nous présentons trois fonctions différentes: une projection linéaire qui est réalisée par une matrice simple, une projection non-linéaire qui est réalisée par Multi-layer Perceptrons (MLP) et une projection non-linéaire profonde qui est réalisée par Convolutional Neural Networks (CNN). Avec ces fonctions de projection, nous proposons trois systèmes de TSML pour plusieurs applications: la vérification par paires, l’identification d’objet, la réduction de la dimensionnalité et la visualisation de données. Pour chaque application, nous présentons des expérimentations détaillées sur des ensembles de données de référence afin de démontrer l’efficacité de notre systèmes de TSML
In many machine learning and pattern recognition tasks, there is always a need for appropriate metric functions to measure pairwise distance or similarity between data, where a metric function is a function that defines a distance or similarity between each pair of elements of a set. In this thesis, we propose Triangular Similarity Metric Learning (TSML) for automatically specifying a metric from data. A TSML system is loaded in a siamese architecture which consists of two identical sub-systems sharing the same set of parameters. Each sub-system processes a single data sample and thus the whole system receives a pair of data as the input. The TSML system includes a cost function parameterizing the pairwise relationship between data and a mapping function allowing the system to learn high-level features from the training data. In terms of the cost function, we first propose the Triangular Similarity, a novel similarity metric which is equivalent to the well-known Cosine Similarity in measuring a data pair. Based on a simplified version of the Triangular Similarity, we further develop the triangular loss function in order to perform metric learning, i.e. to increase the similarity between two vectors in the same class and to decrease the similarity between two vectors of different classes. Compared with other distance or similarity metrics, the triangular loss and its gradient naturally offer us an intuitive and interesting geometrical interpretation of the metric learning objective. In terms of the mapping function, we introduce three different options: a linear mapping realized by a simple transformation matrix, a nonlinear mapping realized by Multi-layer Perceptrons (MLP) and a deep nonlinear mapping realized by Convolutional Neural Networks (CNN). With these mapping functions, we present three different TSML systems for various applications, namely, pairwise verification, object identification, dimensionality reduction and data visualization. For each application, we carry out extensive experiments on popular benchmarks and datasets to demonstrate the effectiveness of the proposed systems

Similarity search is a task fundamental to many machine learning and data analytics applications, where distance metric learning plays an important role. However, since modern online applications continuously produce objects with new characteristics which tend to change over time, state-of-the-art similarity search using distance metric learning methods tends to fail when deployed in such applications without taking the change into consideration. In this work, we propose a Distance Metric Learning-based Continuous Similarity Search approach (CSS for short) to account for the dynamic nature of such data. CSS system adopts an online metric learning model to achieve distance metric evolving to adapt the dynamic nature of continuous data without large latency. To improve the accuracy of online metric learning model, a compact labeled dataset which is representative of the updated data is dynamically updated. Also, to accelerate similarity search, CSS includes an online maintained Locality Sensitive Hashing index to accelerate the similarity search. One, our labeled data update strategy progressively enriches the labeled data to assure continued representativeness, yet without excessively growing its size to ensure that the computation costs of metric learning remain bounded. Two, our continuous distance metric learning strategy ensures that each update only requires one linear time k-NN search in contrast to the cubic time complexity of relearning the distance metric from scratch. Three, our LSH update mechanism leverages our theoretical insight that the LSH built based on the original distance metric is equally effective in supporting similarity search using the new distance metric as long as the transform matrix learned for the new distance metric is reversible. This important observation empowers CSS to avoid the modification of LSH in most cases. Our experimental study using real-world public datasets and large synthetic datasets confirms the effectiveness of CSS in improving the accuracy of classification and information retrieval tasks. Also, CSS achieves 3 orders of magnitude speedup of our incremental distance metric learning strategy (and its three underlying components) over the state-of-art methods.

PriceRunner is an online shopping comparison company. To maintain up-todate prices, PriceRunner has to process large amounts of data every day. The processing of the data includes matching unknown products, referred to as offers, to known products. Offer data includes information about the product such as: title, description, price and often one image of the product. PriceRunner has previously implemented a textual-based machine learning (ML) model, but is also looking for new approaches to complement the current product matching system. The objective of this master’s thesis is to investigate the potential of using an image-based ML model for product matching. Our method uses a similarity learning approach where the network learns to recognise the similarity between images. To achieve this, a siamese neural network was trained with the triplet loss function. The network is trained to map similar images closer together and dissimilar images further apart in a vector space. This approach is often used for face recognition, where there is an extensive amount of classes and a limited amount of images per class, and new classes are frequently added. This is also the case for the image data used in this thesis project. A general model was trained on images from the Clothing and Accessories hierarchy, one of the 16 toplevel hierarchies at PriceRunner, consisting of 17 product categories. The results varied between each product category. Some categories proved to be less suitable for image-based classification while others excelled. The model handles new classes relatively well without any, or with briefer, retraining. It was concluded that there is potential in using images to complement the current product matching system at PriceRunner.

Even though the prospect of fusing images issued by different medical imagery systems is highly contemplated, the practical instantiation of it is subject to a theoretical hurdle: the definition of a similarity between images. Efforts in this field have proved successful for select pairs of images; however defining a suitable similarity between images regardless of their origin is one of the biggest challenges in deformable registration. In this thesis, we chose to develop generic approaches that allow the comparison of any two given modality. The recent advances in Machine Learning permitted us to provide innovative solutions to this very challenging problem. To tackle the problem of comparing incommensurable data we chose to view it as a data embedding problem where one embeds all the data in a common space in which comparison is possible. To this end, we explored the projection of one image space onto the image space of the other as well as the projection of both image spaces onto a common image space in which the comparison calculations are conducted. This was done by the study of the correspondences between image features in a pre-aligned dataset. In the pursuit of these goals, new methods for image regression as well as multi-modal metric learning methods were developed. The resulting learned similarities are then incorporated into a discrete optimization framework that mitigates the need for a differentiable criterion. Lastly we investigate on a new method that discards the constraint of a database of images that are pre-aligned, only requiring data annotated (segmented) by a physician. Experiments are conducted on two challenging medical images data-sets (Pre-Aligned MRI images and PET/CT images) to justify the benefits of our approach.

One way of modeling human knowledge is by using multidimensional spaces, in which an object is represented as a point in the space, and the distances among the points reflect the similarities among the represented objects. The distances are measured with some metric, commonly some instance of the Minkowski metric. The instances differ with the magnitude of the so-called r-parameter. The instances most commonly mentioned in the literature are the ones where r equals 1, 2 and infinity.

Cognitive scientists have found out that different metrics are suited to describe different dimensional combinations. From these findings an important distinction between integral and separable dimensions has been stated (Garner, 1974). Separable dimensions, e.g. size and form, are best described by the city-block metric, where r equals 1, and integral dimensions, such as the color dimensions, are best described by the Euclidean metric, where r equals 2. Developmental psychologists have formulated a hypothesis saying that small children perceive many dimensional combinations as integral whereas adults perceive the same combinations as separable. Thus, there seems to be a shift towards increasing separability with age or maturity.

Earlier experiments show the same phenomenon in adult short-term learning with novel stimuli. In these experiments, the stimuli were first perceived as rather integral and were then turning more separable, indicated by the Minkowski-r. This indicates a shift towards increasing separability with familiarity or skill.

This dissertation aims at investigating the generality of this phenomenon. Five similarity-rating experiments are conducted, for which the best fitting metric for the first half of the session is compared to the last half of the session. If the Minkowski-r is lower for the last half compared to the first half, it is considered to indicate increasing separability.

The conclusion is that the phenomenon of increasing separability during short-term learning cannot be found in these experiments, at least not given the operational definition of increasing separability as a function of a decreasing Minkowski-r. An alternative definition of increasing separability is suggested, where an r-value ‘retreating’ 2.0 indicates increasing separability, i.e. when the r-value of the best fitting metric for the last half of a similarity-rating session is further away from 2.0 compared to the first half of the session.

Les performances des algorithmes d'apprentissage automatique dépendent de la métrique utilisée pour comparer deux objets, et beaucoup de travaux ont montré qu'il était préférable d'apprendre une métrique à partir des données plutôt que se reposer sur une métrique simple fondée sur la matrice identité. Ces résultats ont fourni la base au domaine maintenant qualifié d'apprentissage de métrique. Toutefois, dans ce domaine, la très grande majorité des développements concerne l'apprentissage de distances. Toutefois, dans certaines situations, il est préférable d'utiliser des similarités (par exemple le cosinus) que des distances. Il est donc important, dans ces situations, d'apprendre correctement les métriques à la base des mesures de similarité. Il n'existe pas à notre connaissance de travaux complets sur le sujet, et c'est une des motivations de cette thèse. Dans le cas des systèmes de filtrage d'information où le but est d'affecter un flot de documents à un ou plusieurs thèmes prédéfinis et où peu d'information de supervision est disponible, des seuils peuvent être appris pour améliorer les mesures de similarité standard telles que le cosinus. L'apprentissage de tels seuils représente le premier pas vers un apprentissage complet des mesures de similarité. Nous avons utilisé cette stratégie au cours des campagnes CLEF INFILE 2008 et 2009, en proposant des versions en ligne et batch de nos algorithmes. Cependant, dans le cas où l'on dispose de suffisamment d'information de supervision, comme en catégorisation, il est préférable d'apprendre des métriques complètes, et pas seulement des seuils. Nous avons développé plusieurs algorithmes qui visent à ce but dans le cadre de la catégorisation à base de k plus proches voisins. Nous avons tout d'abord développé un algorithme, SiLA, qui permet d'apprendre des similarités non contraintes (c'est-à-dire que la mesure peut être symétrique ou non). SiLA est une extension du perceptron par vote et permet d'apprendre des similarités qui généralisent le cosinus, ou les coefficients de Dice ou de Jaccard. Nous avons ensuite comparé SiLA avec RELIEF, un algorithme standard de re-pondération d'attributs, dont le but n'est pas sans lien avec l'apprentissage de métrique. En effet, il a récemment été suggéré par Sun et Wu que RELIEF pouvait être considéré comme un algorithme d'apprentissage de métrique avec pour fonction objectif une approximation de la fonction de perte 0-1. Nous montrons ici que cette approximation est relativement mauvaise et peut être avantageusement remplacée par une autre, qui conduit à un algorithme dont les performances sont meilleures. Nous nous sommes enfin intéressés à une extension directe du cosinus, extension définie comme la forme normalisée d'un produit scalaire dans un espace projeté. Ce travail a donné lieu à l'algorithme gCosLA. Nous avons testé tous nos algorithmes sur plusieurs bases de données. Un test statistique, le s-test, est utilisé pour déterminer si les différences entre résultats sont significatives ou non. GCosLA est l'algorithme qui a fourni les meilleurs résultats. De plus, SiLA et gCosLA se comparent avantageusement à plusieurs algorithmes standard, ce qui illustre leur bien fondé
Almost all machine learning problems depend heavily on the metric used. Many works have proved that it is a far better approach to learn the metric structure from the data rather than assuming a simple geometry based on the identity matrix. This has paved the way for a new research theme called metric learning. Most of the works in this domain have based their approaches on distance learning only. However some other works have shown that similarity should be preferred over distance metrics while dealing with textual datasets as well as with non-textual ones. Being able to efficiently learn appropriate similarity measures, as opposed to distances, is thus of high importance for various collections. If several works have partially addressed this problem for different applications, no previous work is known which has fully addressed it in the context of learning similarity metrics for kNN classification. This is exactly the focus of the current study. In the case of information filtering systems where the aim is to filter an incoming stream of documents into a set of predefined topics with little supervision, cosine based category specific thresholds can be learned. Learning such thresholds can be seen as a first step towards learning a complete similarity measure. This strategy was used to develop Online and Batch algorithms for information filtering during the INFILE (Information Filtering) track of the CLEF (Cross Language Evaluation Forum) campaign during the years 2008 and 2009. However, provided enough supervised information is available, as is the case in classification settings, it is usually beneficial to learn a complete metric as opposed to learning thresholds. To this end, we developed numerous algorithms for learning complete similarity metrics for kNN classification. An unconstrained similarity learning algorithm called SiLA is developed in which case the normalization is independent of the similarity matrix. SiLA encompasses, among others, the standard cosine measure, as well as the Dice and Jaccard coefficients. SiLA is an extension of the voted perceptron algorithm and allows to learn different types of similarity functions (based on diagonal, symmetric or asymmetric matrices). We then compare SiLA with RELIEF, a well known feature re-weighting algorithm. It has recently been suggested by Sun and Wu that RELIEF can be seen as a distance metric learning algorithm optimizing a cost function which is an approximation of the 0-1 loss. We show here that this approximation is loose, and propose a stricter version closer to the the 0-1 loss, leading to a new, and better, RELIEF-based algorithm for classification. We then focus on a direct extension of the cosine similarity measure, defined as a normalized scalar product in a projected space. The associated algorithm is called generalized Cosine simiLarity Algorithm (gCosLA). All of the algorithms are tested on many different datasets. A statistical test, the s-test, is employed to assess whether the results are significantly different. GCosLA performed statistically much better than SiLA on many of the datasets. Furthermore, SiLA and gCosLA were compared with many state of the art algorithms, illustrating their well-foundedness

The lack of training data is a common problem in machine learning. One solution to thisproblem is to use transfer learning to remove or reduce the requirement of training data.Selecting datasets for transfer learning can be difficult however. As a possible solution, thisstudy proposes the domain similarity metrics document vector distance (DVD) and termfrequency-inverse document frequency (TF-IDF) distance. DVD and TF-IDF could aid inselecting datasets for good transfer learning when there is no data from the target domain.The simple metric, shared vocabulary, is used as a baseline to check whether DVD or TF-IDF can indicate a better choice for a fine-tuning dataset. SQuAD is a popular questionanswering dataset which has been proven useful for pre-training models for transfer learn-ing. The results were therefore measured by pre-training a model on the SQuAD datasetand fine-tuning on a selection of different datasets. The proposed metrics were used tomeasure the similarity between the datasets to see whether there was a correlation betweentransfer learning effect and similarity. The results found a clear relation between a smalldistance according to the DVD metric and good transfer learning. This could prove usefulfor a target domain without training data, a model could be trained on a big dataset andfine-tuned on a small dataset that is very similar to the target domain. It was also foundthat even small amount of training data from the target domain can be used to fine-tune amodel pre-trained on another domain of data, achieving better performance compared toonly training on data from the target domain.

In recent years, various metrics have been developed for measuring the similarity of states in probabilistic transition systems (Desharnais et al., 1999; van Breugel & Worrell, 2001a). In the context of Markov decision processes, we have devised metrics providing a robust quantitative analogue of bisimulation. Most importantly, the metric distances can be used to bound the differences in the optimal value function that is integral to reinforcement learning (Ferns et al. 2004; 2005). More recently, we have discovered an efficient algorithm to calculate distances in the case of finite systems (Ferns et al., 2006). In this thesis, we seek to properly extend state-similarity metrics to Markov decision processes with continuous state spaces both in theory and in practice. In particular, we provide the first distance-estimation scheme for metrics based on bisimulation for continuous probabilistic transition systems. Our work, based on statistical sampling and infinite dimensional linear programming, is a crucial first step in real-world planning; many practical problems are continuous in nature, e.g. robot navigation, and often a parametric model or crude finite approximation does not suffice. State-similarity metrics allow us to reason about the quality of replacing one model with another. In practice, they can be used directly to aggregate states.

This dissertation aims at developing audio-based musical version identification (VI) systems for industry-scale corpora. To employ such systems in industrial use cases, they must demonstrate high performance on large-scale corpora while not favoring certain musicians or tracks above others. Therefore, the three main aspects we address in this dissertation are accuracy, scalability, and algorithmic bias of VI systems. We propose a data-driven model that incorporates domain knowledge in its network architecture and training strategy. We then take two main directions to further improve our model. Firstly, we experiment with data-driven fusion methods to combine information from models that process harmonic and melodic information, which greatly enhances identification accuracy. Secondly, we investigate embedding distillation techniques to reduce the size of the embeddings produced by our model, which reduces the requirements for data storage and, more importantly, retrieval time. Lastly, we analyze the algorithmic biases of our systems.
En esta tesis se desarrollan sistemas de identificación de versiones musicales basados en audio y aplicables en un entorno industrial. Por lo tanto, los tres aspectos que se abordan en esta tesis son el desempeño, escalabilidad, y los sesgos algorítmicos en los sistemas de identificación de versiones. Se propone un modelo dirigido por datos que incorpora conocimiento musical en su arquitectura de red y estrategia de entrenamiento, para lo cual se experimenta con dos enfoques. Primero, se experimenta con métodos de fusión dirigidos por datos para combinar la información de los modelos que procesan información melódica y armónica, logrando un importante incremento en la exactitud de la identificación. Segundo, se investigan técnicas para la destilación de embeddings para reducir su tamaño, lo cual reduce los requerimientos de almacenamiento de datos, y lo que es más importante, del tiempo de búsqueda. Por último, se analizan los sesgos algorítmicos de nuestros sistemas.

Gegenstand der vorliegenden Dissertation ist die Entwicklung von Algorithmen und Methoden mit dem Ziel, Archäologen bei der täglichen wissenschaftlichen Arbeit zu unterstützen. Im Teil I werden Ideen präsentiert, mit denen sich die extrem zeitintensive und stellenweise stupide Funddokumentation beschleunigen lässt. Es wird argumentiert, dass das dreidimensionale Erfassen der Fundobjekte mittels Laser- oder Streifenlichtscannern trotz hoher Anschaffungskosten wirtschaftlich und vor allem qualitativ attraktiv ist. Mithilfe von nicht fotorealistischen Visualisierungstechniken können dann wieder aussagekräftige, aber dennoch objektive Bilder generiert werden. Außerdem ist speziell für Gefäße eine vollautomatische und umfassende Merkmalserhebung möglich. Im II. Teil gehen wir auf das Problem der automatisierten Gefäßklassifikation ein. Nach einer theoretischen Betrachtung des Typbegriffs in der Archäologie präsentieren wir eine Methodologie, in der Verfahren sowohl aus dem Bereich des unüberwachten als auch des überwachten Lernens zum Einsatz kommen. Besonders die letzteren haben sich dabei als überaus praktikabel erwiesen, um einerseits unbekanntes Material einer bestehenden Typologie zuzuordnen, andererseits aber auch die Struktur der Typologie selbst kritisch zu hinterfragen. Sämtliche Untersuchungen haben wir beispielhaft an den bronzezeitlichen Gräberfeldern von Kötitz, Altlommatzsch (beide Lkr. Meißen), Niederkaina (Lkr. Bautzen) und Tornow (Lkr. Oberspreewald-Lausitz) durchgeführt und waren schließlich sogar in der Lage, archäologisch relevante Zusammenhänge zwischen diesen Fundkomplexen herzustellen
The topic of the dissertation at hand is the development of algorithms and methods aiming at supporting the daily scientific work of archaeologists. Part I covers ideas for accelerating the extremely time-consuming and often tedious documentation of finds. It is argued that digitizing the objects with 3D laser or structured light scanners is economically reasonable and above all of high quality, even though those systems are still quite expensive. Using advanced non-photorealistic visualization techniques, meaningful but at the same time objective pictures can be generated from the virtual models. Moreover, specifically for vessels a fully-automatic and comprehensive feature extraction is possible. In Part II, we deal with the problem of automated vessel classification. After a theoretical consideration of the type concept in archaeology we present a methodology, which employs approaches from the fields of both unsupervised and supervised machine learning. Particularly the latter have proven to be very valuable in order to assign unknown entities to an already existing typology, but also to challenge the typology structure itself. All the analyses have been exemplified by the Bronze Age cemeteries of Kötitz, Altlommatzsch (both district of Meißen), Niederkaina (district of Bautzen), and Tornow (district Oberspreewald-Lausitz). Finally, we were even able to discover archaeologically relevant relationships between these sites

In movement science with inertial sensor many different methodologies resolving specific aspects of movement recognition have been proposed. They are very interesting, and useful, but none of them are generally explicative of what is going on in the semantic sense. When we go down to the movement recognition/classification area (for example in Ambient Intelligence) we do not have a feasible model that can be considered generally predictive or usable for activity recognition. Also, in the field of movement recognition with inertial sensors many technological issues arise: technological diversity, calibration matters, sensor model problems, orientation and position of sensors, and a lot of numerous specificities that, with all the above aspects, and the lack of public dataset of movements sufficiently generic and semantically rich, contribute to create a strong barrier to any approach to a classification matters with wearable sensors. We have also to notice that a movement is a phenomenon explicitly or implicitly (voluntary or involuntary) controlled by brain. The individual free-will introduce a further matter when we want to temporary predict the movements looking at the close past. Pattern can change at any time when ambient, psychological context, age of the subject change. Also, pathological issues, and physiological differences and the will of the subject, introduce important differences. For all these reasons I considered that a semantical /lexical approach to movement recognition with sensors, driven by machine learning techniques could be a promising way to solve some of these challenge and problems. In this Ph.D. Thesis wearable inertial sensors has been used to classify movements, the choice of inertial sensors has been driven by technological and practical advantages, they are cheap, lightweight, and - differently from video cameras - are not prone to the hidden face, or luminance problems. The main idea is to use inertial sensor to understand what a person is doing for ambient-intelligent, healthcare, medical-sport applications. My principal concerns was to propose a method that was not centered on technology issues but on data analysis, that could be a general framework and could also create a general representation of movement,that could be useful also in other area of research, like reasoning. Inertial sensors are treated just as an example, a particular type of sensors, the method is new, reusable, algorithmically simple, net and easy to understand. Accuracy is very high outperforming the best results given in literature, reducing the error rate of 4 times.

La géolocalisation par le réseau a suscité beaucoup d'attention ces dernières années. Dans un contexte où les signaux sont à bandes étroites, par exemple pour l'Internet des Objets, les techniques de géolocalisation basées sur le RSSI se distinguent. Nous proposons tout d'abord quelques méthodes pour le problème de la géolocalisation basée sur le RSSI. En particulier, nous introduisons un estimateur semi-paramétrique de Nadaraya-Watson de la vraisemblance, suivi d'un estimateur de maximum à postériori de la position de l'objet. Les expériences démontrent l'intérêt de la méthode proposée sur les performances d'estimation. Une approche alternative est donnée par une régression de type k-NN qui utilise une métrique appropriée entre les vecteurs de RSSI. Nous nous intéressons donc au problème de l'apprentissage de similarité et nous introduisons un objectif spécifiquemet choisi pour améliorer la géolocalisation. La fonction de similarité est choisie comme une somme d'arbres de régression et est apprise séquentiellement au moyen d'une version modifiée de l'algorithme XGBoost. La dernière partie de la thèse est consacrée à l'introduction d'un test d'hypothèse d'indépendance conditionnelle (IC). En effet, pour de nombreux estimateurs, les composantes des vecteurs RSSI sont supposées indépendantes sachant la position. La contribution est cependant fournie dans un cadre statistique général. Nous introduisons la fonction de copule partielle pondérée pour tester l'indépendance conditionnelle. La procédure de test proposée résulte des éléments suivants : (i) la statistique de test est une transformation de Cramér-von Mises de la copule partielle pondérée, (ii) les régions de rejet sont calculées à l'aide d'une procédure de "bootstrap" qui imite l'indépendance conditionnelle en générant des échantillons. Sous l'hypothèse nulle, la faible convergence du processus de la copule partielle pondérée est établie et confirme le bien-fondé de notre approche
The Network-Based Geolocation has raised a great deal of attention in the context of the Internet of Things. In many situations, connected objects with low-consumption should be geolocated without the use of GPS or GSM. Geolocation techniques based on the Received Signal Strength Indicator (RSSI) stands out, because other location techniques may fail in the context of urban environments and/or narrow band signals. First, we propose some methods for the RSSI-based geolocation problem. The observation is a vector of RSSI received at the various base stations. In particular, we introduce a semi-parametric Nadaraya-Watson estimator of the likelihood, followed by a maximum a posteriori estimator of the object’s position. Experiments demonstrate the interest of the proposed method, both in terms of location estimation performance, and ability to build radio maps. An alternative approach is given by a k-nearest neighbors regressor which uses a suitable metric between RSSI vectors. Results also show that the quality of the prediction is highly related to the chosen metric. Therefore, we turn our attention to the metric learning problem. We introduce an original task-driven objective for learning a similarity between pairs of data points. The similarity is chosen as a sum of regression trees and is sequentially learned by means of a modified version of the so-called eXtreme Gradient Boosting algorithm (XGBoost). The last part of the thesis is devoted to the introduction of a Conditional Independence (CI) hypothesis test. The motivation is related to the fact that for many estimators, the components of the RSSI vectors are assumed independent given the position. The contribution is however provided in a general statistical framework. We introduce the weighted partial copula function for testing conditional independence. The proposed test procedure results from the following ingredients: (i) the test statistic is an explicit Cramér-von Mises transformation of the weighted partial copula, (ii) the regions of rejection are computed using a boot-strap procedure which mimics conditional independence by generating samples. Under the null hypothesis, the weak convergence of the weighted partial copula process is established and endorses the soundness of our approach

M.Ing.
Nearest neighbour classifiers are well suited for use in practical pattern recognition applications for a number of reasons, including ease of implementation, rapid training, justifiable decisions and low computational load. However their generalisation performance is perceived to be inferior to that of more complex methods such as neural networks or support vector machines. Closer inspection shows however that the generalisation performance actually varies widely depending on the dataset used. On certain problems they outperform all other known classifiers while on others they fail dismally. In this thesis we allege that their sensitivity to the metric used is the reason for their mercurial performance. We also discuss some of the remedies for this problem that have been suggested in the past, most notably the variable-kernel similarity metric learning technique, and introduce our own extension to this technique. Finally these metric learning techniques are evaluated on an aircraft recognition task and critically compared.

A large number of machine learning algorithms are critically dependent on the underlying distance/metric/similarity function. Learning an appropriate distance function is therefore crucial to the success of many methods. The class of distance functions that can be learned accurately is characterized by the amount and type of supervision available to the particular application. In this thesis, we explore a variety of such distance learning problems using different amounts/types of supervision and provide efficient and scalable algorithms to learn appropriate distance functions for each of these problems. First, we propose a generic regularized framework for Mahalanobis metric learning and prove that for a wide variety of regularization functions, metric learning can be used for efficiently learning a kernel function incorporating the available side-information. Furthermore, we provide a method for fast nearest neighbor search using the learned distance/kernel function. We show that a variety of existing metric learning methods are special cases of our general framework. Hence, our framework also provides a kernelization scheme and fast similarity search scheme for such methods. Second, we consider a variation of our standard metric learning framework where the side-information is incremental, streaming and cannot be stored. For this problem, we provide an efficient online metric learning algorithm that compares favorably to existing methods both theoretically and empirically. Next, we consider a contrasting scenario where the amount of supervision being provided is extremely small compared to the number of training points. For this problem, we consider two different modeling assumptions: 1) data lies on a low-dimensional linear subspace, 2) data lies on a low-dimensional non-linear manifold. The first assumption, in particular, leads to the problem of matrix rank minimization over polyhedral sets, which is a problem of immense interest in numerous fields including optimization, machine learning, computer vision, and control theory. We propose a novel online learning based optimization method for the rank minimization problem and provide provable approximation guarantees for it. The second assumption leads to our geometry-aware metric/kernel learning formulation, where we jointly model the metric/kernel over the data along with the underlying manifold. We provide an efficient alternating minimization algorithm for this problem and demonstrate its wide applicability and effectiveness by applying it to various machine learning tasks such as semi-supervised classification, colored dimensionality reduction, manifold alignment etc. Finally, we consider the task of learning distance functions under no supervision, which we cast as a problem of learning disparate clusterings of the data. To this end, we propose a discriminative approach and a generative model based approach and we provide efficient algorithms with convergence guarantees for both the approaches.
text

Remotely-sensed hyperspectral imagery has become one the most advanced tools for analyzing the processes that shape the Earth and other planets. Effective, rapid analysis of high-volume, high-dimensional hyperspectral image data sets demands efficient, automated techniques to identify signatures of known materials in such imagery. In this thesis, we develop a framework for automatic material identification in hyperspectral imagery using adaptive similarity measures. We frame the material identification problem as a multiclass similarity-based classification problem, where our goal is to predict material labels for unlabeled target spectra based upon their similarities to source spectra with known material labels. As differences in capture conditions affect the spectral representations of materials, we divide the material identification problem into intra-domain (i.e., source and target spectra captured under identical conditions) and inter-domain (i.e., source and target spectra captured under different conditions) settings. The first component of this thesis develops adaptive similarity measures for intra-domain settings that measure the relevance of spectral features to the given classification task using small amounts of labeled data. We propose a technique based on multiclass Linear Discriminant Analysis (LDA) that combines several distinct similarity measures into a single hybrid measure capturing the strengths of each of the individual measures. We also provide a comparative survey of techniques for low-rank Mahalanobis metric learning, and demonstrate that regularized LDA yields competitive results to the state-of-the-art, at substantially lower computational cost. The second component of this thesis shifts the focus to inter-domain settings, and proposes a multiclass domain adaptation framework that reconciles systematic differences between spectra captured under similar, but not identical, conditions. Our framework computes a similarity-based mapping that captures structured, relative relationships between classes shared between source and target domains, allowing us apply a classifier trained using labeled source spectra to classify target spectra. We demonstrate improved domain adaptation accuracy in comparison to recently-proposed multitask learning and manifold alignment techniques in several case studies involving state-of-the-art synthetic and real-world hyperspectral imagery.

Over the last few decades, there has been an increasing number of attempts at creating systems capable of comparing and classifying chemical compounds based on their structure and/or physicochemical properties. While the rate of success of these approaches has been increasing, particularly with the introduction of new and ever more sophisticated methods of machine learning, there is still room for improvement. One of the problems of these methods is that they fail to consider that similar molecules may have di erent roles in nature, or, to a lesser extend, that disparate molecules may have similar roles. This thesis proposes the exploitation of the semantic properties of chemical compounds, as described in the ChEBI ontology, to create an e cient system able to automatically deal with the binary classi cation of chemical compounds. To that e ect, I developed Chym (Chemical Hybrid Metric) as a tool that integrates structural and semantic information in a unique hybrid metric. The work here presented shows substantial evidence supporting the e ectiveness of Chym, since it has outperformed all the models with which it was compared. Particularly, it achieved accuracy values of 90.9%, 87.7% and 84.2% when solving three classi cation problems which, previously, had only been solved with accuracy values of 81.5%, 80.6% and 82.8% respectively. Other results show that the tool is appropriate to use even if the problem at hand is not well represented in the ChEBI ontology. Thus, Chym shows that considering the semantic properties of a compound helps solving classi cation problems. Therefore, Chym can be used in projects that require the classi cation and/or the comparison of chemical compounds, such as the study of the evolution of metabolic pathways, drug discovery or in preliminary toxicity analysis.

Schemas describe the data structures of various domains such as purchase order, conference, health and music. A large number of schemas are available on the Web. Since different schema elements may have the same semantics but exist in distinct schemas, it is important to manage their semantic heterogeneity. Schema matching is usually used to determine mappings between semantically correspondent elements of different schemas. It can be conducted manually, semi-automatically and automatically. Man- ual matching is a time-consuming, error-prone and expensive process. Fully-automated matching is not possible because of the complexity of the schemas. This research investigated semi-automatic schema matching systems to overcome manual works for schema mapping. In general, these systems use machine learning and knowledge engineering approaches. Machine learning approaches require training datasets for building matching models. However, it is usually very diffcult to ob- tain appropriate training datasets for large datasets and to change the trained models once mapped. Knowledge engineering approaches require domain experts and time- consuming knowledge acquisition. In order to solve these problems, an incremental knowledge engineering approach - Ripple-Down Rules (RDR) can be a promising approach since it allows its knowledge to grow incrementally. However, acquiring matching rules is still a time-intensive task. In order to overcome the limitations of these independent approaches, a hybrid approach called Hybrid-RDR has been developed by combining a machine learning approach with the Censor Production Rules (CPR) based RDR approach. First, the most suitable machine learning algorithm, J48 is determined by comparing eleven machine learning approaches including decision trees, rules, Naive Bayes, AdaBootM1, and later combined with CPR based RDR for building Hybrid-RDR ap- proach. This approach constructs a matching model using J48. When new data are available, the model may suggest incorrect matchings for some cases which are corrected by incrementally adding rules to the knowledge base. The approach reuses the previous match operations (rules) and handles the schema matching problems using an incremental knowledge acquisition process. So users do not need to add, delete or modify schema matching results manually. The Hybrid-RDR approach works for element-level matching that only considers matching names of schema elements. Structure-level matching that considers the hierarchical structure of the schema, is required to adjust incorrect matches found from the element-level matching. A Knowledge-based Schema Matching System (KSMS) has also been developed that performs element-level matching using Hybrid-RDR and structure-level matching using Similarity Flooding algorithm. This algorithm considers the concept that two nodes are similar when their neighbor elements are similar. The final mappings are generated by combining the results of element-level matching and structure-level matching using aggregation functions. In order to evaluate the performance of the system, evaluations using real world schemas found on the Web have been conducted. Experimental results have shown that the system determines good performance both at element-level matching and structure-level matching. This research has resolved the ongoing problem of elements having different names within different schemas. The KSMS allows for matching of different schemas to produce accurate mappings.