É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 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 IEEE
Résumé : International audience
Recent works display that large scale image classification problems rule out computationally demanding methods. On such problems, simple approaches like k-NN are affordable contenders, with still room space for statistical improvements under the algorithmic constraints. A recent work showed how to leverage k-NN to yield a formal boosting algorithm. This method, however, has numerical issues that make it not suited for large scale problems. We propose here an Adaptive Newton-Raphson scheme to leverage k-NN, N³, which does not suffer these issues. We show that it is a boosting algorithm, with several key algorithmic and statistical properties. In particular, it may be sufficient to boost a subsample to reach desired bounds for the loss at hand in the boosting framework. Experiments are provided on the SUN, and Caltech databases. They confirm that boosting a subsample -- sometimes containing few examples only -- is sufficient to reach the convergence regime of N³. Under such conditions, N³ challenges the accuracy of contenders with lower computational cost and lower memory requirement.
IEEE International Workshop on Machine Learning for Signal Processing
Southampton, United Kingdom

hal-00959125
https://hal.archives-ouvertes.fr/hal-00959125
https://hal.archives-ouvertes.fr/hal-00959125/document
https://hal.archives-ouvertes.fr/hal-00959125/file/BNNB_mlsp2013.pdf

Éditeur(s) : HAL CCSD
Résumé : International audience
In this paper, we focus on the very specificity of rumors as pieces of information for modeling their process of propagation. We consider a population of pedestrians walking in a city and we assume that a rumor is transmitted by word of mouth from one to another. Although the diffusion of a rumor is of course a multi-dimensional process driven by sociological, economical and psychological elements, in this first step, we emphasize one main dimension of this complex phenomenon only. This dimension is the neighborhood of individuals likely to spread the information. With a confrontation of two antagonistic properties of the neighborhood that are profusion and scarcity of spreaders, we highlight specific characteristics of rumors. This study could lead to the psychological mechanism involved in the decision for a person to become or not a spreader himself/herself. In summary, we study if scarcity could be the silver bullet explaining how a rumor spreads.
ASONAM 2015 : IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining
Paris, France

hal-01252936
https://hal.archives-ouvertes.fr/hal-01252936
DOI : 10.1145/2808797.2809299

Éditeur(s) : HAL CCSD
Résumé : International audience
Human spatial motions determine geographic social contacts that influence the way an information is spread on a population or a community. As mobility is a transverse dimension to social practices it is important to better understand its role. With the Eternal-Return model we propose, we simulate an artificial world populated by heterogeneous agents who differ in their mobility. We have chosen a multi-agent framework perspective for this simulation. We endow the agents with simple rules on how to move around the space and how to establish proximity-contacts. This allows to distinguish different kinds of mobile agents, from sedentary ones to travelers. To summarize the dynamics induced by mobility over time, we define the mobility-based Social Proximity Network as being the network of all distinct contacts between agents. Its properties give insight in the process of information spreading. We conduct simulations to understand how an information can be broadcast when agent-nodes are in motion.
IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining
Niagara falls, Canada

hal-00874344
https://hal.archives-ouvertes.fr/hal-00874344

Éditeur(s) : HAL CCSD
Résumé : A standard approach for large scale image classification involves high dimensional features and Stochastic Gradient Descent algorithm (SGD) for the minimization of classical Hinge Loss in the primal space. Although complexity of Stochastic Gradient Descent is linear with the number of samples these method suffers from slow convergence. In order to cope with this issue, we propose here a Stochastic Low-Rank Newton Descent SLND for minimization of any calibrated loss in the primal space. SLND approximates the inverse Hessian by the best low-rank approximation according to squared Frobenius norm. We provide core optimization for fast convergence. Theoretically speaking, we show explicit convergence rates of the algorithm using these calibrated losses, which in addition provide working sets of parameters for experiments. Experiments are provided on the SUN, Caltech256 and ImageNet databases, with simple, uniform and efficient ways to tune remaining SLND parameters. On each of these databases, SLND challenges the accuracy of SGD with a speed of convergence faster by order of magnitude.
https://hal.archives-ouvertes.fr/hal-00825414

hal-00825414
https://hal.archives-ouvertes.fr/hal-00825414
https://hal.archives-ouvertes.fr/hal-00825414/document
https://hal.archives-ouvertes.fr/hal-00825414/file/TechnicalReport.pdf

Éditeur(s) : HAL CCSD
Résumé : International audience
The general context of this paper is the Bass model which presented a theory of the adoption of new products. We propose an agent based modelling to allow to model the respective grow of competing products. We assume that there is competition for the same market among two trademarks: each one has its own rate of spontaneous innovation and its own rate of imitation. This paper deals with the relative weight of these competing behaviors on the global dynamics; in particular, we ask the question of the equivalence between mass media influence and word-of-mouth effect.
IEEE RCIS 2014 Eighth International Conference on Research Challenges in Information Science
Marrakech, Morocco

hal-01288467
https://hal.archives-ouvertes.fr/hal-01288467
https://hal.archives-ouvertes.fr/hal-01288467/document
https://hal.archives-ouvertes.fr/hal-01288467/file/poster.pdf

Éditeur(s) : HAL CCSD IEEE
Résumé : International audience
This paper proposes a novel automated approach for the categorization of cells in fluorescence microscopy images. Our supervised classification method aims at recognizing patterns of unlabeled cells based on an annotated dataset. First, the cell images need to be indexed by encoding them in a feature space. For this purpose, we propose tailored bio-inspired features relying on the distribution of contrast information. Then, a supervised learning algorithm is proposed for classifying the cells. We carried out experiments on cellular images related to the diagnosis of autoimmune diseases, testing our classification method on the HEp-2 Cells dataset of Foggia et al (CBMS 2010). Results show classification precision larger than 96% on average, thus confirming promising application of our approach to the challenging application of cellular image classification for computer-aided diagnosis.
ICPR 2012
Tsukuba, Japan

hal-00958856
https://hal.archives-ouvertes.fr/hal-00958856
https://hal.archives-ouvertes.fr/hal-00958856/document
https://hal.archives-ouvertes.fr/hal-00958856/file/icpr_2012.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
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 Elsevier
Résumé : International audience
Given a graph, its hyperbolicity is a measure of how close its distance distribution is to the one of a tree. This parameter has gained recent attention in the analysis of some graph algorithms and the classification of complex networks. We study on practical improvements for the computation of hyperbolicity in large graphs. Precisely, we investigate on relations between the hyperbolicity of a graph G and the hyperbolicity of its atoms, that are the subgraphs output by the clique-decomposition invented by Tarjan [51, 65]. We prove that the maximum hyperbolicity taken over the atoms is at most one unit off from the hyperbol-icity of G and the bound is sharp. We also give an algorithm to slightly modify the atoms, called the " substitution method " , which is at no extra cost than computing the clique-decomposition, and so that the maximum hyperbolicity taken over the resulting graphs is exactly the hyperbolicity of the input graph G. An experimental evaluation of our method for computing the hyperbolicity of a given graph from its atoms is provided for collaboration networks and biological networks. Finally, on a more theoretical side, we deduce from our results the first linear-time algorithm for computing the hyperbolicity of an outerplanar graph.
ISSN: 0304-3975

hal-01540756
https://hal.inria.fr/hal-01540756
https://hal.inria.fr/hal-01540756/document
https://hal.inria.fr/hal-01540756/file/CCDL-2017.pdf
DOI : 10.1016/j.tcs.2017.06.001

Éditeur(s) : HAL CCSD Springer
Résumé : Third International Workshop, MLMI 2012, Held in Conjunction with MICCAI 2012
International audience
Universal Nearest Neighbours (unn) is a classifier recently proposed, which can also effectively estimates the posterior probability of each classification act. This algorithm, intrinsically binary, requires the use of a decomposition method to cope with multiclass problems, thus reducing their complexity in less complex binary subtasks. Then, a reconstruction rule provides the final classification. In this paper we show that the application of unn algorithm in conjunction with a reconstruction rule based on the posterior probabilities provides a classification scheme robust among different biomedical image datasets. To this aim, we compare unn performance with those achieved by Support Vector Machine with two different kernels and by a k Nearest Neighbours classifier, and applying two different reconstruction rules for each of the aforementioned classification paradigms. The results on one private and five public biomedical datasets show satisfactory performance.
Machine Learning in Medical Imaging
Nice, France

hal-00958909
https://hal.archives-ouvertes.fr/hal-00958909
https://hal.archives-ouvertes.fr/hal-00958909/document
https://hal.archives-ouvertes.fr/hal-00958909/file/Miccai.pdf
DOI : 10.1007/978-3-642-35428-1_15

É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 Springer
Résumé : International audience
The study of information dissemination in social networks is of particular importance in many areas as marketing, politics and security for example. Various strategies are being developed to disseminate information, those aimed at disseminating information widely and those aimed at disseminating information in a more confidential manner to make it scarce. In this paper, we adapt a model dedicated to spreading rumours by word of mouth in a physical space to the context of social networks. We compare two modes of dissemination based on profusion or scarcity and study the impact of the choice of the initial node. The results obtained show to what extent each mode exploits the social network topology and especially the influence of hubs.
International Conference on Complex Networks and Their Applications (COMPLEX NETWORK)
Lyon, France

hal-01637573
https://hal.archives-ouvertes.fr/hal-01637573

Éditeur(s) : HAL CCSD
Résumé : International audience
In real world situations, each person is generally in contact with only a small fraction of the entire population and exchange information through these interactions. Their number and their frequency vary from one to another individual and may be much depending on mobility of individuals. The objective of this article is to better understand how human mobility may have an impact on mobile social networking systems. This should help to answer a question as: "How might an information, a rumor, a pathogen, etc., driven by physical proximity, spread through a population?". We present a first stage of our work in which we focus on percolation processes as information flow mechanisms. We propose a synthetic mobility model and we define an artificial world populated by heterogeneous agents who differ in their mobility. Simulations are conducted on a multi-agent programmable environment. Our experimental results clearly demonstrate positive correlations between agent mobility factors and percolation thresholds.
Procedia CS

hal-00767043
https://hal.archives-ouvertes.fr/hal-00767043
DOI : 10.1016/j.procs.2012.06.007

É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 Presses polytechniques et universitaires romandes, Publisher of the EPFL Press
Résumé : Chacun peut observer dans le monde réel l’omniprésence de systèmes complexes constitués de nombreux éléments en interaction et dont les caractéristiques globales ne peuvent se réduire à celles de leurs composants : ce sont par exemple les cellules d’un organisme vivant, les colonies de fourmis, les écosystèmes, ou encore les systèmes économiques, l’Internet et les réseaux sociaux. Dans le futur, nos sociétés devront relever l’immense défi scientifique et technologique qui consiste à comprendre ces systèmes pour les adapter, les contrôler et les modéliser. Au travers d’exemples choisis sans complication inutile, les auteurs proposent une introduction par la pratique aux systèmes complexes. Leur méthode repose sur la conviction que toute compréhension suppose un acte d’expérience; l’ouvrage est composé d’ateliers où il s’agit de simuler une dynamique collective à partir de sa modélisation orientée-agent. Les étudiants, les enseignants, les créateurs et plus largement toute personne avide de développer sa culture et d’actualiser ses connaissances tireront parti de cet ouvrage pluridisciplinaire accessible à un large public.
https://hal.archives-ouvertes.fr/hal-01284628

ISBN : 978-2-88074-991-0
hal-01284628
https://hal.archives-ouvertes.fr/hal-01284628

Éditeur(s) : HAL CCSD Information Science Reference
Evolving Application Domains of Data Warehousing and Mining: Trends and Solutions

hal-00468097
https://hal.archives-ouvertes.fr/hal-00468097

Éditeur(s) : HAL CCSD
Résumé : J'étais à l'époque dans le laboratoire I3S de Sophia-Antipolis. Je suis dorénavant au laboratoire GRIMAAG en Guadeloupe.
We focused on the communication problem within multi-agents systems, inspirited by nature and more precisely by the ants that are a perfect example of living integrating learning (ontogenesis) to genetic inheritance (phylogenesis): the Baldwin Effect.
We worked with agents represented by classifiers systems using genetic algorithm. We introduced a new fixed knowledge based classifiers system, the simplified Pittsburgh classifier system, which we studied in a spontaneous coordination multi-agents problem. Then, we successfully allowed “homogeneous” agents to communicate their “knowledge” using distributed elitism.
Finally, “heterogeneous” agents efficiently exchanged information thanks to a minimal communication model we defined, bound to reality and extended.
Nous nous sommes intéressés à la problématique de la communication au sein des systèmes multi-agents en nous inspirant de la nature et plus particulièrement des fourmis qui sont un parfait exemple de l'intégration de l'apprentissage du vivant (ontogenèse) au capital génétique de celui-ci (phylogénie) : l'effet Baldwin.
Nous avons choisi de travailler avec des systèmes de classeurs à algorithme génétique pour représenter les agents. Nous avons introduit un nouveau type de système de classeurs à base de connaissance de taille fixe, les systèmes de classeurs de type Pittsburgh simplifié, dont nous avons étudié les propriétés dans un contexte multi-agents de coordination spontanée.
Nous avons ensuite proposé avec succès aux agents "homogènes" de communiquer pour échanger leur "connaissance" à l'aide de l'élitisme distribué.
Enfin, les agents "hétérogènes" ont échangé efficacement des informations grâce à un modèle minimal de communication que nous avons ancré dans la réalité puis étendu.
https://tel.archives-ouvertes.fr/tel-00192372

tel-00192372
https://tel.archives-ouvertes.fr/tel-00192372
https://tel.archives-ouvertes.fr/tel-00192372/document
https://tel.archives-ouvertes.fr/tel-00192372/file/These.pdf