Éditeur(s) : HAL CCSD Elsevier
Résumé : International audience
Voting rules relying on k-nearest neighbors (k-NN) are an effective tool in countless many machine learning techniques. Thanks to its simplicity, k-NN classification is very attractive to practitioners, as it enables very good performances in several practical applications. However, it suffers from various drawbacks, like sensitivity to "noisy" instances and poor generalization properties when dealing with sparse high-dimensional data. In this paper, we tackle the k-NN classification problem at its core by providing a novel k-NN boosting approach. Namely, we propose a supervised learning algorithm, called Universal Nearest Neighbors (UNN), that induces a leveraged k-NN rule by globally minimizing a surrogate risk upper bounding the empirical misclassification rate over training data. Interestingly, this surrogate risk can be arbitrary chosen from a class of Bregman loss functions, including the familiar exponential, logistic and squared losses. Furthermore, we show that UNN allows to efficiently filter a dataset of instances by keeping only a small fraction of data. Experimental results on the synthetic Ripley's dataset show that such a filtering strategy is able to reject "noisy" examples, and yields a classification error close to the optimal Bayes error. Experiments on standard UCI datasets show significant improvements over the current state of the art.
ISSN: 0925-2312

hal-00664462
https://hal.inria.fr/hal-00664462

Éditeur(s) : HAL CCSD
Résumé : International audience
The k-nearest neighbors (k-NN) classification rule is still an essential tool for computer vision applications, such as scene recognition. However, k-NN still features some major drawbacks, which mainly reside in the uniform voting among the nearest prototypes in the feature space. In this paper, we propose a new method that is able to learn the "relevance" of prototypes, thus classifying test data using a weighted k-NN rule. In particular, our algorithm, called Multi-class Leveraged k-nearest neighbor (MLNN), learns the prototype weights in a boosting framework, by minimizing a surrogate exponential risk over training data. We propose two main contributions for improving computational speed and accuracy. On the one hand, we implement learning in an inherently multiclass way, thus providing significant computation time reduction over one-versus-all approaches. Furthermore, the leveraging weights enable effective data selection, thus reducing the cost of k-NN search at classification time. On the other hand, we propose a kernel generalization of our approach to take into account real-valued similarities between data in the feature space, thus enabling more accurate estimation of the local class density. We tested MLNN on three datasets of natural images. Results show that MLNN significantly outperforms classic k-NN and weighted k-NN voting. Furthermore, using an adaptive Gaussian kernel provides significant performance improvement. Finally, the best results are obtained when using MLNN with an appropriate learned metric distance.
Proceedings of the 10th Asian Conference on Computer Vision, ACCV 2010, November 8-12, 2010, Queenstown, New Zealand
Queenstown, New Zealand

hal-00664606
https://hal.inria.fr/hal-00664606
https://hal.inria.fr/hal-00664606/document
https://hal.inria.fr/hal-00664606/file/mlnn_accvfinal.pdf

Éditeur(s) : HAL CCSD Institute of Electrical and Electronics Engineers
Résumé : International audience
Tailoring nearest neighbors algorithms to boosting is an important problem. Recent papers study an approach, UNN, which provably minimizes particular convex surrogates under weak assumptions. However, numerical issues make it necessary to experimentally tweak parts of the UNN algorithm, at the possible expense of the algorithm's convergence and performance. In this paper, we propose a lightweight alternative algorithm optimizing proper scoring rules from a very broad set, and establish formal convergence rates under the boosting framework that surprisingly compete with those known for UNN. It is an adaptive Newton-Raphson algorithm, which belongs to the same lineage as the popular Gentle Adaboost. To the best of our knowledge, no such boosting-compliant convergence rates were previously known for these algorithms. We provide experiments on a dozen domains, including the challenging Caltech and SUN computer vision databases. They display that GNNB significantly outperforms UNN, both in terms of convergence rate and quality of the solution obtained, and GNNB provides a simple and efficient contender to techniques that can be used on very large domains, like stochastic gradient descent -- for which little is known to date. Experiments include a divide-and-conquer improvement of GNNB which exploits the link with proper scoring rules optimization.
ISSN: 0162-8828

hal-00958809
https://hal.archives-ouvertes.fr/hal-00958809
https://hal.archives-ouvertes.fr/hal-00958809/document
https://hal.archives-ouvertes.fr/hal-00958809/file/PAMI.pdf
DOI : 10.1109/TPAMI.2014.2307877

Éditeur(s) : HAL CCSD Springer Verlag
Résumé : under revision for IJCV
International audience
The k-nearest neighbors (k-NN) classification rule has proven extremely successful in countless many computer vision applications. For example, image categorization often relies on uniform voting among the nearest prototypes in the space of descriptors. In spite of its good properties, the classic k-NN rule suffers from high variance when dealing with sparse prototype datasets in high dimensions. A few techniques have been proposed to improve k-NN classification, which rely on either deforming the nearest neighborhood relationship or modifying the input space. In this paper, we propose a novel boosting algorithm, called UNN (Universal Nearest Neighbors), which induces leveraged k-NN, thus generalizing the classic k-NN rule. We redefine the voting rule as a strong classifier that linearly combines predictions from the k closest prototypes. Weak classifiers are learned by UNN so as to minimize a surrogate risk. A major feature of UNN is the ability to learn which prototypes are the most relevant for a given class, thus allowing one for effective data reduction. Experimental results on the synthetic two-class dataset of Ripley show that such a filtering strategy is able to reject "noisy" prototypes. We carried out image categorization experiments on a database containing eight classes of natural scenes. We show that our method outperforms significantly the classic k-NN classification, while enabling significant reduction of the computational cost by means of data filtering.
ISSN: 0920-5691

hal-00481712
https://hal.archives-ouvertes.fr/hal-00481712
DOI : 10.1007/s11263-012-0539-2
ARXIV : 1001.1221

Éditeur(s) : HAL CCSD
Résumé : International audience
It is an admitted fact that mainstream boosting algorithms like AdaBoost do not perform well to estimate class conditional probabilities. In this paper, we analyze, in the light of this problem, a recent algorithm, unn, which leverages nearest neighbors while minimizing a convex loss. Our contribution is threefold. First, we show that there exists a subclass of surrogate losses, elsewhere called balanced, whose minimization brings simple and statistically efficient estimators for Bayes posteriors. Second, we show explicit convergence rates towards these estimators for unn, for any such surrogate loss, under a Weak Learning Assumption which parallels that of classical boosting results. Third and last, we provide experiments and comparisons on synthetic and real datasets, including the challenging SUN computer vision database. Results clearly display that boosting nearest neighbors may provide highly accurate estimators, sometimes more than a hundred times more accurate than those of other contenders like support vector machines.
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD)
Bristol, United Kingdom

hal-00702771
https://hal.archives-ouvertes.fr/hal-00702771
https://hal.archives-ouvertes.fr/hal-00702771/document
https://hal.archives-ouvertes.fr/hal-00702771/file/ecml12-dnbnb-sub.pdf

Éditeur(s) : HAL CCSD IEEE
Résumé : Object classification is a challenging task in computer vision. Many approaches have been proposed to extract meaningful descriptors from images and classifying them in a supervised learning framework. In this paper, we revisit the classic k-nearest neighbors (k-NN) classification rule, which has shown to be very effective when dealing with local image descriptors. However, k-NN still features some major drawbacks, mainly due to the uniform voting among the nearest prototypes in the feature space. In this paper, we propose a generalization of the classic k-NN rule in a supervised learning (boosting) framework. Namely, we redefine the voting rule as a strong classifier that linearly combines predictions from the k closest prototypes. To induce this classifier, we propose a novel learning algorithm, MLNN (Multiclass Leveraged Nearest Neighbors), which gives a simple procedure for performing prototype selection very efficiently. We tested our method on 12 categories of objects, and observed significant improvement over classic k-NN in terms of classification performances.
International Workshop on Image Analysis for Multimedia Interactive Services
Desenzano del Garda, Italy

hal-00481725
https://hal.archives-ouvertes.fr/hal-00481725
https://hal.archives-ouvertes.fr/hal-00481725/document
https://hal.archives-ouvertes.fr/hal-00481725/file/pbnn_wiamis_10.pdf

Éditeur(s) : HAL CCSD
Résumé : Joint inversions are now commonly used in Earth Sciences. They have been developed to better understand Earth structure since they provide more constraints on the inverted parameters. We propose a new process to simultaneously invert several data sets in order to better image 3-D crustal and upper mantle structures. Our inversion uses 3 kind of data which present a good complementarity : (1) P receiver functions to provide Moho depth variations, (2) teleseismic delay times of P waves to retrieve velocity anomalies in the crust and upper mantle, (3) gravity anomalies to image density variations at lithospheric scale. In our scheme, receiver functions are first inverted. The resulting Moho depths are then interpolated and incorporated as a priori information into the joint inversion of teleseismic delay times and gravity anomalies process. In our new approach, we perform a model space search for Moho variations, P-velocity and density structure to find acceptable fit to the three data sets. In order to preferentially sample the good data fit region, we chose the Neighborhood algorithm of Sambridge to optimistically survey the model space. We model the delay times with a 3-D raytracing using velocity nodes evenly spaced and linked with density nodes via a linear relationship. This relationship can evolve through depth, simulating its pressure dependance. We test our scheme on synthetic examples, and apply the method in a continental rifting region where deformation processes are complex and badly known. This joint inversion thus provides more constraints on the inverted parameters, and allows us to better image crust - mantle interactions in the case of the Hangai dome (Central Mongolia). Indeed, in this area, we expect an asthenospheric upwelling to dynamically support the topography, but we image a density - velocity anomaly in the lower crust. The effects on topography and the origin (composition vs. thermal) of this anomaly are still under debate.
Les inversions conjointes sont maintenant communément utilisées en Sciences de la Terre. Elles ont été développées afin d'améliorer notre connaissance et compréhension de la structure interne de la Terre puisqu'elles apportent de plus en plus de contraintes sur les paramètres inversés. Dans cette thèse, nous proposons un nouveau processus d'inversion conjointe qui prend en compte trois paramètres différents et qui mène à l'obtention d'un modèle lithosphérique tridimensionnel. Notre méthode utilise trois types de données gravimétriques et sismologiques qui présentent une bonne complémentarité : (1) Les fonctions récepteur P afin d'obtenir les variations de profondeur du Moho, (2) les délais de temps d'arrivées P des téléséismes pour retrouver les anomalies de vitesse dans la croûte et le manteau supérieur, (3) les anomalies gravimétriques qui donnent accès aux variations de densité à l'échelle lithosphérique. Dans le schéma d'inversion proposé, nous inversons d'abord les fonctions récepteur. Les variations de profondeur du Moho qui en résultent sont alors interpolées puis incorporées comme information a priori dans le processus d'inversion conjointe gravimétrie - tomographie télésismique. Que ce soit pour les fonctions récepteur ou pour la partie conjointe, notre méthode d'inversion se base sur un algorithme de recherche afin de trouver la structure qui minimise l'écart aux trois types de données. Nous avons opté pour l'algorithme de voisinage qui présente l'avantage de concentrer sa recherche dans les régions qui minimisent l'écart aux données sans toutefois abandonner les autres régions afin de limiter les risques de convergence vers un minimum local. Nous utilisons un modèle 3-D constitué de noeuds de vitesse afin de modéliser les délais de temps. Ces noeuds de vitesse sont liés aux noeuds de densité grâce à une relation linéaire entre vitesse et densité. Cette relation peut évoluer avec la profondeur de manière à simuler les effets dus aux variations de pression. Nous avons réalisé plusieurs tests synthétiques afin d'évaluer le comportement de notre nouvelle méthode. Ils ont permis de montrer que les variations du Moho ainsi que les anomalies de vitesse et densité sont bien retrouvées. Ils ont également montré l'importance de la prise en compte de ces trois types de données dans un même schéma d'inversion, notamment en ce qui concerne la faculté de discerner les variations d'interfaces des anomalies volumiques. Nous avons ensuite appliqué la méthode dans une région continentale en phase de rifting où les processus de déformation sont complexes et mal connus. Notre nouvelle méthode a apporté davantage de contraintes sur les paramètres inversés et a permis d'obtenir un modèle correctement résolu de la croûte et du manteau supérieur sous le dôme de Hangai (Mongolie Centrale). Une anomalie asthénosphérique sous le dôme est souvent invoquée pour expliquer sa topographie élevée mais c'est une anomalie (en vitesse et densité) crustale (croûte inférieure) qui s'exprime dans nos modèles. Ses effets sur la topographie et son origine (compositionnelle et/ou thermique) sont encore débattus et nécessiteraient des études plus poussées (paramétriques, VP =VS, ...).
https://tel.archives-ouvertes.fr/tel-00783524

tel-00783524
https://tel.archives-ouvertes.fr/tel-00783524
https://tel.archives-ouvertes.fr/tel-00783524/document
https://tel.archives-ouvertes.fr/tel-00783524/file/Basuyau2011.pdf

Éditeur(s) : HAL CCSD Wiley-Blackwell
Résumé : We use InSAR to measure deformation and kinematics of the Mw = 4.9 Borujerd (2005/05/03) and Mw = 6.1 Chalan-Chulan (2006/03/31) earthquakes that occurred in the Zagros fold-and-thrust belt. The focal mechanism of the 2006 event is consistent with right lateral strike-slip motion and the event ruptured the Dorud-Borujerd segment of the Main Recent Fault. An Envisat interferogram spanning the 2006 event shows peak ground deformation of 9 cm in the satellite line-of-sight along a 10 km long fault portion. The interferogram spanning the 2005 earthquake is rather related to atmospheric artefact than to ground deformation. Dislocation models of the 2006 Chalan-Chulan event indicate dextral slip amounting to a maximum of 90 cm at a depth of 4 km. The predicted vertical displacements are in good agreement with differential levelling data. The 2006 event filled only a small part of the seismic gap located between large M = 7 events that occurred in 1909 and 1957.
ISSN: 0954-4879

hal-00411313
https://hal.archives-ouvertes.fr/hal-00411313
DOI : 10.1111/j.1365-3121.2008.00797.x

Éditeur(s) : HAL CCSD Elsevier
Résumé : International audience
Joint inversions are now commonly used in the earth sciences. They have been developed to better understand the structure of the earth, since they provide more constraints on the inverted parameters. We propose a new process to simultaneously invert several data sets in order to better image 3D crustal and upper mantle structures. Our inversion uses three kinds of data that present good complementarity: (1) P-wave receiver functions to provide Moho depth variations, (2) teleseismic delay times of P-waves to retrieve velocity anomalies in the crust and the upper mantle, and (3) gravity anomalies to image density variations at the lithospheric scale. We use a stochastic scheme, where receiver functions are first inverted. The interpolated resulting Moho depths are incorporated as a priori information into the joint inversion of teleseismic delay times and gravity anomalies process. Moreover, velocity and density can be linked by empirical relationships, which justifies the joint inversion of those parameters. In our stochastic approach, we perform a model space search for Moho variations, P-velocity, and density structure to find an acceptable fit to the three data sets. In order to preferentially sample the good data fit regions, we chose the neighborhood algorithm of Sambridge to optimistically survey the model space. We model the delay times with 3D raytracing using evenly spaced velocity-density nodes. We present here the first results given by this method on synthetic tests. (C) 2011 Elsevier Ltd. All rights reserved.
ISSN: 0098-3004

hal-00643158
https://hal.archives-ouvertes.fr/hal-00643158
DOI : 10.1016/j.cageo.2010.11.017