2013


Retour à la vue des calendrier
Mardi 8 Janvier
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Aller-retour et voyageur de commerce dans les réseaux de transports urbain
Description: Pierre Parent Le problème de l'aller-retour se pose lorsque l'on dispose d'un véhicule
personnel, et que l'on peut faire une partie du trajet à l'aide de celui-ci,
et le restant via les transports en communs. Il s'agit alors de trouver quel
trajet choisir à l'aller et au retour, pour minimiser le temps total, sachant
que si la voiture est garée à un endroit à l'aller on doit passer la
rechercher à ce même endroit au retour.

Dans le problèmes de voyageur de commerce nous avons un certain nombre
d'endroit à visiter en ville, et il s'agit de trouver le trajet optimal
passant par tout ces points en utilisant les transports en commun. La difficulté
réside dans le fait que les trains, arrivent et partent à des heures fixées de
la journée.

Nous proposerons des méthodes de résolution pour les deux problèmes, ainsi que
des résultats expérimentaux.
Mardi 15 Janvier
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Génération aléatoire de permutations alternées
Description: Philippe Marchal Désiré André (dans son article de 1879) a montré que le développement en série de tan(x) et sec(x) est lié à une jolie suite combinatoire, les nombres Eulériens, qui comptent le nombre de permutations alternées.J'introduis un nouvel algorithme, basé sur des idées de théorie des probabilités,qui permet d'engendrer une telle permutation de longueur n en temps n log n.Je montrerai que l'idée peut aussi s'étendre à d'autres classes de permutations contraintes.
Jeudi 24 Janvier
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Analyse de données temporelles
Description: Ahlame Douzal Mes travaux de recherche portent sur l'analyse de données temporelles et s'articulent en trois parties : -la représentation de séries temporelles, -la définition de métriques et leur apprentissage, -ainsi que la proposition de nouvelles approches de classification dédiées aux séries temporelles. Le déploiement de statistiques d'autocorrélation spatiale sur des structures de contiguïté particulières, telle que temporelle, met en évidence des propriétés intéressantes. Elles permettent, par exemple, d'appréhender le comportement des séries (aléatoire, chaotique), d'évaluer le niveau de saillance d'un événement, ou de mesurer la dépendance locale ou globale entre une structure évolutive et les observations associées. Ces propriétés ont guidé nos principaux travaux.Ainsi, notre première contribution concerne la représentation compacte de séries multivariées. Nous avons étudié une approche de réduction de la dimension temporelle de séries multivariées, par segmentation, préservant les corrélations inférées par la série ; l'identification de segments saillants étant guidée par la variance locale. Dans la deuxième partie de notre travail, nous nous sommes intéressé à la définition de métriques intégrant la composante forme des séries et leur positionnement dans un cadre plus général. L'alignement de séries étant un concept fondamental dans la définition de métriques, notre intérêt a porté, ensuite, sur l'apprentissage de couplages pour la discrimination de classes de séries complexes. L'approche proposée vise à lier les séries selon les caractéristiques communes au sein des classes et différentielles entre les classes. Le couplage ainsi appris permet de dériver une métrique locale pondérée restreignant la comparaison des séries aux attributs discriminants. Enfin, le troisième volet de nos travaux est dédié à l'extension des arbres de classification/régression à des variables prédictives temporelles. L'arbre temporel de classification proposé recours à un nouveau critère de coupure fondé sur une métrique adaptative et la localisation de sous-séquences discriminantes.
Mardi 29 Janvier
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinaison automatique d'algorithmes et heuristiques
Description: Yanik Ngoko Sur de nombreux problèmes combinatoires comme SAT ou CSP, on peut
facilement trouver, étant donné un sous ensemble d'heuristiques, un sous
ensemble d'instances du problème sur lequel aucune heuristique ne domine
complètement les autres(*). Ceci a motivé de nombreux travaux ayant pour
but de combiner plusieurs heuristiques résolvant le même problème afin
d'exploiter leur diversité.

Dans cet exposé, nous nous intéressons à cette problématique en contexte
parallèle et homogène. Dans les solutions décrites, une combinaison est
obtenue en exécutant de façon concurrente dans le temps et dans l'espace
(coeurs, processeurs, régistres caches etc.) plusieurs heuristiques,
jusqu'à ce que l'une d'elles trouve une solution satisfaisante. Pour
apprendre à construire de telles combinaisons, nous proposons une
solution d'apprentissage basée sur une estimation du temps d'exécution
des heuristiques sur un jeu d'instances représentatives. Le coeur de
notre proposition peut être formulé comme un  problème combinatoire dont
nous prouvons la  np-completude et l'inapproximabilité. Nous proposons
pour sa résolution plusieurs heuristiques, avec garanti de performance
sous certaines hypothèses.

Finalement, nous présentons quelques résultats de notre approche de
combinaison sur les problèmes SAT et CSP.

(*) Par exemple dans le temps pris pour donner une solution satisfaisante..
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Initiation à la théorie de Galois différentielle et applications aux fonctions holonomes
Description: Thierry Combot Nous présenterons la théorie de Galois différentielle appliquée auxéquations différentielles à coefficients polynomiaux puis auxéquations aux différences. On montrera ensuite comment calculer cesgroupes de Galois, et quels sont les algorithmes disponibles. Onprésentera alors les méthodes disponibles pour résoudre ceséquations en introduisant les fonctions liouviliennes. Enfin nousappliquerons ces méthodes pour l'analyse du comportementasymptotique des solutions : le groupe de Galois donne en particulier des relations algébriques a priori sur les constantes apparaissant dans ces développements asymptotiques, et permettent dans le cas liouvillien de les expliciter.
Lundi 4 Février
Heure: 00:59 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Séquences fréquentes maximales et applications
Description: Antoine Doucet Une séquence d'items (par exemple, des mots, ou des caractères), est
définie par l'ordre dans lequel ces items apparaissent dans un
document, indépendamment de la distance qui les y sépare. Une
séquence est dite fréquente, si elle apparaît dans plus de documents
qu'un seuil de fréquence documentaire donné. Elle est dite maximale
dès lors que l'insertion de tout autre item induit une fréquence
inférieure au seuil.

Appliquées par exemple au niveau phrastique, les séquences
fréquentes maximales (SFM) forment ainsi des descripteurs compacts,
qui ne sont ni limités en taille, ni par la distance les séparant
dans le corpus initial.

Je détaillerai tout d'abord notre méthode non supervisée permettant
l'extraction et la sélection efficace de séquences fréquentes
maximales depuis des corpus de texte de toute taille, quel qu'en
soit le genre, et quelle qu'en soit la langue.

Je présenterai ensuite plusieurs applications de ces travaux,
notamment en extraction de synonymes, utilisant les SFM comme pivots
d'alignement de paraphrases. J'aborderai également nos applications
en recherche d'information multilingue, en veille épidémiologique
multilingue et en détection de nouveauté dans des flux de dépêches
d'agence de presse.
Mardi 5 Février
Heure: 10:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Inversion de Lagrange multivariée
Description: Axel Bacher
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Separable non-convex underestimators for binary quadratic programming
Description: Emiliano Traversi We present a new approach to constrained quadratic binary
programming. Dual bounds are computed by choosing appropriate global
underestimators of the objective function that are separable but not
necessarily convex. Using the binary constraint on the variables, the
minimization of this separable underestimator can be reduced to a linear
minimization problem over the same set of feasible vectors. For most
combinatorial optimization problems, the linear version is considerably
easier than the quadratic version. We explain how to embed this approach
into a branch-and-bound algorithm and present experimental results.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: La conjecture de Hadamard
Description: Shalom Eliahou<
Mardi 12 Février
Heure: 10:00 - 13:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Journée en l'honneur du départ à la retraite de Pierre Nicodème : accueil
Description: Pierre Nicodème
Heure: 10:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Computer algebra for the enumeration of lattice walks
Description: Alin Bostan
Heure: 11:30 - 14:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Newton iteration in computer algebra and combinatorics
Description: Bruno Salvy
Heure: 14:30 - 17:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Some patterns in Pierre Nicodème's works
Description: Julien Clément
Mardi 19 Février
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Discrete optimization using semidefinite methods
Description: Angelika Wiegele Many real-world applications, although being non-linear, can be well
described by linearized models. Therefore, Linear Programming (LP)
became a widely studied and applied technique in many areas of science,
industry and economy. Semidefinite Programming (SDP) is an extension of
LP. A matrix-variable is optimized over the intersection of the cone of
positive semidefinite matrices with an affine space. It turned out, that
SDP can provide significantly stronger practical results than LP. Since
then SDP turned out to be practical in a lot of different areas, like
combinatorial optimization, control theory, engineering, and more
recently in polynomial optimization.

In this talk I will present some ideas how to model discrete
optimization problems using semidefinite programming in order to obtain
semidefinite relaxations. Some of this relaxations proved to be
succesful when using in a branch-and-bound framework. Furthermore, I
want to present a new idea of how to strengthen semidefinite relaxations. 
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Énumeration exacte et asymptotique de pastèques avec barrière
Description: Christian Krattenthaler Le modèle des promeneurs vicieux (sic!)a été introduit par Michael Fisher en mécanique statistique en 1984.De nombreuses variantes ont été étudiées depuis,en particulier celle que je condidère dans mon exposé :lorsque qu'il y a une interaction entre ces promeneurs et un mur.Ce modèle a été originellement proposé par Owczarek, Essam et Brak, qui ont établi quelques résultats partiels.Je montrerai comment complètement déterminer le comportement asymptotiquede la fonction de partition correspondante (et celle d'un autre paramètre pertinent).Nous rencontrerons comme de bien entendu (attendu!) mes chers amis : déterminants, une bijection de tableau et des séries hypergéometriques.
Jeudi 21 Février
Heure: 00:59 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Analyse syntaxique en dépendances et prédiction structurée
Description: Joseph Leroux
Mardi 26 Février
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé:  Réservation de voies dans un réseau de transport 
Description: Feng Chu
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Un petit survol des grands algorithmes de la théorie des graphes, illustrés via le logiciel libre PIGALE
Description: Patrice Ossona de Mendez
Mardi 5 Mars
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatorial aspects of the Jacobi conjecture
Description: Axel de Goursac We expose the reformulation of the Jacobian conjecture in terms of the combinatorics of Feynman diagrams of a certain Quantum Field Theory. We will also discuss considerations about Dixmier conjecture and Noncommutative Quantum Field Theory.
Vendredi 8 Mars
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Some Results for Linear Logic Full Completeness
Description: Hugh Steele Many full completeness theorems have been established for fragments of
linear logic since the notion was first defined by Samson Abramsky and
Radha Jagadeesan in their 1992 paper. For the most part, these results
are obtained on a case-by-case basis: the subject of each proof is
precisely one category.

In this talk it is shown that the Hyland-Tan double glueing
construction can transform all tensor-generated compact closed
categories with finite biproducts into fully complete models of
unit-free MLL. The arguments employed are based around considering the
combinatorics behind the construction using standard linear algebra.
It is also discussed how another double glueing construction may be
able to create similar categories satisfying unit-free MALL full
completeness.
Mardi 12 Mars
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Reverse Chvatal-Gomory rank.
Description: Roland Grappe We introduce the reverse Chvatal-Gomory rank r*(P) of an integral
polyhedron P, defined as the supremum of the Chvatal-Gomory ranks of all
rational polyhedra whose integer hull is P. A well-known example in
dimension two shows that there exist integral polytopes P with r*(P)
infinite. We provide a geometric characterization of polyhedra with this
property in general dimension, and investigate upper bounds on r*(P)
when this value is finite.
This is a joint work with Michele Conforti, Alberto Del Pia, Marco Di
Summa and Yuri Faenza. 
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Bipartite subfamilies of planar graphs
Description: Juanjo Rué Perna I will survey the techniques used to get asymptotic results for subfamilies of planar graphs, as well as how to relate this methodology with the context of map enumeration. In the second part of the talk, I willexplain the ideas behind some on-going projects related to the enumeration of bipartite subfamilies of graphs.
Vendredi 15 Mars
Heure: 13:30 - 14:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Linear Dependent Types For Differential Privacy
Description: Marco Gaboardi Differential privacy offers a way to answer queries about
sensitive information while offering strong, provable privacy guarantees.
Several tools have been developed for certifying that a given query is
differentially private. In one approach, Reed and Pierce[31] proposed a
functional programming language, Fuzz, for writing differentially private
queries. Fuzz uses linear types to track sensitivity, as well as a
probability monad to express randomized computation; it guarantees that any
program that has a certain type is differentially private. Fuzz can
successfully verify many useful queries. However, it fails when the
analysis depends on values that are not known statically.
We present DFuzz, an extension of Fuzz with a combination of linear indexed
types and lightweight dependent types. This combination allows a richer
sensitivity analysis that is able to analyze a larger class of queries,
including queries whose sensitivity depends on runtime information. As in
Fuzz, the differential privacy guarantees follows directly from the
soundness theorem for the type system. We demonstrate the enhanced
expressivity of DFuzz by certifying differential privacy a broad class of
iterative algorithms that could not be typed previously. We conclude by
discussing the challenges of DFuzz type checking.
Mardi 19 Mars
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Accelerated Column Generation for Cutting Stock and Bin Packing
Description: Accelerated Column Generation for Cutting Stock and Bin Packing One successful method for solving the cutting stock (CS) and bin packing
problem (BP) is branch-and-price.  The column generation master program
is a set covering problem where columns correspond to feasibly filled
bins that cover a subset of the items.  It is known that standard column
generation suffers from slow convergence (tailing off).  For CS, valid
inequalities on the dual prices of the covering constraints, so-called
dual optimal inequalities, were identified to be helpful to mitigate the
tailing off effect.  The presentation addresses three issues:  First,
the standard approach is the a priori construction of dual optimal
inequalities before solving the master program.  We show that the most
violated inequalities can be easily identified in the column generation
process and so be added dynamically.  For standard benchmark problems,
computation times were approximately halved.  Second, for BP not all CS
inequalities are dual optimal, i.e., fulfilled by at least one optimal
solution of the LP-relaxation of the master program.  We present a way
to handle these cases and to reconstruct primal feasible solutions
needed in the branch-and-bound process.  Third, we generalize our
results to the BP with conflicts. 
Jeudi 21 Mars
Heure: 12:30 - 14:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Fouille de sous-graphes fréquents à base d'arc consistance
Description: Brahim Douar Avec la croissance importante du besoin d'analyser une grande masse de données structurées tels que les composés chimiques, les structures de protéines ou même les réseaux sociaux, la fouille de sous-graphes fréquents est devenue un défi réel en matière de fouille de données. Ceci est étroitement lié à leur nombre exponentiel ainsi qu'à la NP-complétude du problème d'isomorphisme d'un sous-graphe général. Face à cette complexité, et pour gérer cette taille importante de l'espace de recherche, les méthodes classiques de fouille de graphes ont exploré des heuristiques de recherche basées sur le support, le langage de description des exemples (limitation aux chemins,  aux arbres, etc.) ou des hypothèses (recherche de sous-arborescence communes, de chemins communs, etc.). Dans le cadre de notre travail de recherche, nous nous basons sur une méthode d'appariement de graphes issue du domaine de la programmation par contraintes, nommée AC-projection, qui a le mérite d'avoir une complexité polynomiale. Nous introduisons des approches de fouille de graphes permettant d'améliorer les approches existantes pour ce problème. En particulier, nous proposons deux algorithmes, FGMAC et AC-miner, permettant de rechercher les sous-graphes fréquents à partir d'une base de graphes. Ces deux algorithmes profitent, différemment, des propriétés fortes intéressantes de l'AC-projection. En effet, l'algorithme FGMAC adopte un parcours en largeur de l'espace de recherche et exploite l'approche par niveau introduite dans Apriori, tandis que l'algorithme AC-miner parcourt l'espace en profondeur par augmentation de motifs, assurant ainsi une meilleure mise à l'échelle pour les grands graphes.  Ces deux approches permettent l'extraction d'un type particulier de graphes, il s'agit de celui des sous-graphes AC-réduits fréquents. Dans un premier temps, nous prouvons, théoriquement, que l'espace de recherche de ces sous-graphes est moins important que celui des sous-graphes fréquents à un isomorphisme près. Ensuite, nous menons une série d'expérimentations permettant de prouver que les algorithmes FGMAC et AC-miner sont plus efficients que ceux de l'état de l'art. Au même temps, nous prouvons que les sous-graphes AC-réduits fréquents, en dépit de leur nombre sensiblement réduit, ont le même pouvoir discriminant que les sous-graphes fréquents à un isomorphisme près. Cette étude est menée en se basant sur une évaluation expérimentale de la qualité des sous-graphes AC-réduits fréquents dans un processus de classification supervisée de graphes.
Jeudi 28 Mars
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Matrice chapeau à noyau discriminante : nouvel outil pour la détection de points aberrants dans les jeux de données
Description: Franck Dufrenois Les données que nous manipulons et étudions sont généralement imparfaites, « polluées » par la présence d'observations aberrantes et constitue un handicap pour expliquer le phénomène dominant sous-jacent aux données. Ces « outliers » signalent soit la présence  d'un phénomène résiduel étranger et/ou la nature imparfaite des « capteurs » que nous utilisons. Les outils statistiques classiques doivent donc introduire dans leur principe des propriétés de robustesse afin d'isoler la structure d'intérêt.En régression, le terme employé est la « régression robuste » et en classification, plusieurs termes sont utilisés: problème de classification à une classe, détection de nouveautés. Le terme « une classe » signifie qu'un sous ensemble des observations forme statistiquement un échantillon représentatif et que l'autre regroupe des événements « rares », souvent impossible à caractériser statistiquement et donc ne pouvant être définis par une classe additionnelle.Bien qu'à priori conceptuellement différent, je propose dans cet exposé de montrer qu'il existe une passerelle entre la régression robuste et la classification à une classe. En particulier, je montre que la régression linéaire robuste peut être formulée à partir d'un critère de Fisher linéaire à une classe, critère traditionnellement employé pour séparer linéairement deux classes. Cette nouvelle mesure de contraste est basée sur les propriétés de décomposition en sous espace de la matrice chapeau. La matrice chapeau est une quantité auxiliaire utilisée en régression, permettant en particulier, via ses éléments diagonaux, de détecter la présence de données atypiques.La maximisation de cette mesure de contraste fournit à la fois le sous espace projectif optimale (au sens du critère) ainsi que le vecteur indicateur séparant la population en deux classes : la classe « dominante » et la classe  « outliers ». Elle est conduite sous la forme d'un processus d'optimisation itératif, alternant entre l'estimation du sous espace projectif optimal et la mise à jour de l'état du vecteur indicateur. Si l'estimation du sous espace projectif est équivalent à résoudre un problème de valeurs propres généralisées, la mise à jour de l'état du vecteur indicateur est basé sur l'hypothèse de gaussianité perturbant le sous ensemble linéaire dominant. Il en résulte que les coefficients diagonaux  de la matrice chapeau « projetés » sur le sous espace optimal suivent une loi du  χ^2permettant une description formelle des points aberrants et leur identification par test d'hypothèse.L'itération de cette procédure en deux étapes fournit à la fois le vecteur des paramètres de la régression et les labels des données. La fonctionnalité de cet algorithme est bivalente : il agit à la fois comme un régresseur et un classifieur. Cette caractéristique confère « naturellement » à notre outil un très bon niveau de robustesse.Dans une seconde partie, nous verrons comment étendre cette mesure de contraste pour isoler une population dominante non linéaire du reste des données. L'utilisation de l'astuce du noyau « the kernel trick » maintenant couramment employé pour « sortir du linéaire » nos outils statistiques standards, sera là encore mis à contribution. L'idée majeure de cette astuce repose sur l'action de « plonger » les données d'entrée dans un espace de redescription de dimension plus importante voir infinie et surtout, afin d'éviter le problème récurrent de la course à la dimension, de remplacer le produit scalaire par une fonction noyau. La fonction noyau qui sera utilisée durant ce travail sera la fonction gaussienne En particulier, nous montrerons dans cette partie qu'il existe un encadrant supérieure de notre mesure de contraste, dépendant uniquement du vecteur indicateur, permettant ainsi de séparer l'estimation du vecteur indicateur de l'estimation du sous espace projectif. Nous montrerons également que cet encadrant moyennant une légère modification constitue une fonction objective concave, dont la maximisation est équivalent à résoudre un problème linéaire à variables binaires sans contraintes.  Si à première vue ce problème peut être considéré comme NP difficile, sa nature concave nous permettra de le résoudre facilement par une approche de type perturbation avec initialisation. L'état du vecteur indicateur sera ainsi déterminé. Une frontière de décision séparant les outliers des données dominantes sera ensuite estimée comme solution d'un problème de valeurs propres généralisé .Bien évidemment, le problème de la sélection du modèle sera également abordé. Le choix de l'échelle de la gaussienne ainsi que le paramètre de régularisation sera discuté.La performance de cette approche sera étudiée sur des données synthétiques ainsi que sur des données réelles. La phase d'initialisation de notre approche nous permet de travailler soit en mode « non supervisé » soit en mode « semi-supervisé ». Nous pourrons comparer cette approche avec  des méthodes récentes non et semi supervisées.Les données que nous manipulons et étudions sont généralement imparfaites, « polluées » par la présence d'observations aberrantes et constitue un handicap pour expliquer le phénomène dominant sous-jacent aux données. Ces « outliers » signalent soit la présence  d'un phénomène résiduel étranger et/ou la nature imparfaite des « capteurs » que nous utilisons. Les outils statistiques classiques doivent donc introduire dans leur principe des propriétés de robustesse afin d'isoler la structure d'intérêt.En régression, le terme employé est la « régression robuste » et en classification, plusieurs termes sont utilisés: problème de classification à une classe, détection de nouveautés. Le terme « une classe » signifie qu'un sous ensemble des observations forme statistiquement un échantillon représentatif et que l'autre regroupe des événements « rares », souvent impossible à caractériser statistiquement et donc ne pouvant être définis par une classe additionnelle.Bien qu'à priori conceptuellement différent, je propose dans cet exposé de montrer qu'il existe une passerelle entre la régression robuste et la classification à une classe. En particulier, je montre que la régression linéaire robuste peut être formulée à partir d'un critère de Fisher linéaire à une classe, critère traditionnellement employé pour séparer linéairement deux classes. Cette nouvelle mesure de contraste est basée sur les propriétés de décomposition en sous espace de la matrice chapeau. La matrice chapeau est une quantité auxiliaire utilisée en régression, permettant en particulier, via ses éléments diagonaux, de détecter la présence de données atypiques.La maximisation de cette mesure de contraste fournit à la fois le sous espace projectif optimale (au sens du critère) ainsi que le vecteur indicateur séparant la population en deux classes : la classe « dominante » et la classe  « outliers ». Elle est conduite sous la forme d'un processus d'optimisation itératif, alternant entre l'estimation du sous espace projectif optimal et la mise à jour de l'état du vecteur indicateur. Si l'estimation du sous espace projectif est équivalent à résoudre un problème de valeurs propres généralisées, la mise à jour de l'état du vecteur indicateur est basé sur l'hypothèse de gaussianité perturbant le sous ensemble linéaire dominant. Il en résulte que les coefficients diagonaux  de la matrice chapeau « projetés » sur le sous espace optimal suivent une loi du  χ^2permettant une description formelle des points aberrants et leur identification par test d'hypothèse.L'itération de cette procédure en deux étapes fournit à la fois le vecteur des paramètres de la régression et les labels des données. La fonctionnalité de cet algorithme est bivalente : il agit à la fois comme un régresseur et un classifieur. Cette caractéristique confère « naturellement » à notre outil un très bon niveau de robustesse.Dans une seconde partie, nous verrons comment étendre cette mesure de contraste pour isoler une population dominante non linéaire du reste des données. L'utilisation de l'astuce du noyau « the kernel trick » maintenant couramment employé pour « sortir du linéaire » nos outils statist