Institut de Mathématiques de Luminy

THÈSES 2013-2014


Dates soutenances Noms et titres thèmes Photos
12 décembre 2013

Marc MUNSCH
Moments des fonctions thêta

ATI  
11 décembre 2013

Stéphanie DIB
Distribution de la non-linéarité
des fonctions booléennes

ATI  
10 décembre 2013

Joël COHEN
Deux résultats d'analyse harmonique
sur un groupe p-adique tordu

RGR  
31 octobre
2013
Mathias BOUREL
Agrégation de modèles en apprentissage statistique pour l’estimation de la densité
et la classification multiclasse
STA  
21 octobre
2013
Pierre RANNOU
Réécriture de diagrammes et de Σ-diagrammes
LDP  
30 septembre
2013
Thuy NGUYEN THI BICH
Étude de certains ensembles singuliers associés à une application polynomiale
SGT  
23 septembre
2013
Virgile DUCET
Construction of algebraic curves with many
rational points over finite fields
ATI  
13 septembre
2013
Milakulo TUKUMULI
Étude de la construction effective des algorithmes
de type Chudnovsky pour la multiplication dans
les corps finis
ATI  



Mathias BOUREL
(thème STA)

Titre : Agrégation de modèles en apprentissage statistique pour l’estimation de la densité et la classification multiclasse

Directeurs de thèse : Badih Ghattas, Ricardo Fraiman

Rapporteurs : Christophe Biernacki, Gonzalo Perera

Jury : Denis Allard, Christophe Biernacki, Ricardo Fraiman, Badih Ghattas, Gonzalo Perera, Christophe Pouet

Date soutenance : 31 octobre 2013

Universités d'inscription : Aix-Marseille Université

Résumé : Les méthodes d’agrégation en apprentissage statistique combinent plusieurs prédicteurs intermédiaires construits à partir du même jeu de données dans le but d’obtenir un prédicteur plus stable avec une meilleure performance. Celles-ci ont été amplement étudiées et ont données lieu à plusieurs travaux, théoriques et empiriques dans plusieurs contextes, supervisés et non supervisés. Dans ce travail nous nous intéressons dans un premier temps à l’apport de ces méthodes au problème de l’estimation de la densité. Nous proposons plusieurs estimateurs simples obtenus comme combinaisons linéaires d’histogrammes. La principale différence entre ceux-ci est quant à la nature de l’aléatoire introduite à chaque étape de l’agrégation. Nous comparons ces techniques à d’autres approches similaires et aux estimateurs classiques sur un choix varié de modèles, et nous démontrons les propriétés asymptotiques pour un de ces algorithmes (Random Averaged Shifted Histogram).
Une seconde partie est consacrée aux extensions du Boosting pour le cas multiclasse. Nous proposons un nouvel algorithme (Adaboost.BG) qui fournit un classifieur final en se basant sur un calcul d’erreur qui prend en compte la marge individuelle de chaque modèle introduit dans l’agrégation. Nous comparons cette méthode à d’autres algorithmes sur plusieurs jeu de données artificiels classiques.

Mots-clés : apprentissage statistique, Agrégation, bagging, boosting, histogramme, estimation de la densité.

Title: Ensemble methods in statistical learning to estimate the density and multiclass classification.

Abstract:
Ensemble methods in statistical learning combine several base learners built from the same data set in order to obtain a more stable predictor with better performance. Such methods have been extensively studied in the supervised context for regression and classification. In this work we consider the extension of these approaches to density estimation. We suggest several new algorithms in the same spirit as bagging and boosting. We show the efficiency of combined density estimators by extensive simulations. We give also the theoretical results for one of our algorithms (Random Averaged Shifted Histogram) by mean of asymptotical convergence under milmd conditions.
A second part is devoted to the extensions of the Boosting algorithms for the multiclass case. We propose a new algorithm (Adaboost.BG) accounting for the margin of the base classifiers and show its efficiency by simulations and comparing it to the most used methods in this context on several datasets from the machine learning benchmark. Partial theoretical results are given for our algorithm, such as the exponential decrease of the learning set misclassification error to zero.

Keywords: machine learning, aggregation, bagging, boosting, histogram, density estimation.

Fichier / File

( 1, 98 Mo )

début thèse : 11/2008




Pierre RANNOU
(thème LDP)

Titre : Réécriture de diagrammes et de Σ-diagrammes

Directeur de thèse : Yves Lafont

Rapporteurs : Pierre-Louis Curien, Vladimir Dotsenko.

Jury : Nadia Creignou, Pierre-Louis Curien, Vladimir Dotsenko, Yves Guiraud, Yves Lafont, François Lamarche, Alain Prouté, Luigi Santocanale.

Date soutenance : 21 octobre 2013

Universités d'inscription : Aix-Marseille Université

Résumé : Cette thèse a pour thème principal la réécriture de diagrammes. C’est une généralisation à la dimension 2 de la réécriture de mots (c’est-à-dire la réécriture en dimension 1). En effet, les diagrammes sont définis à l’aide de deux opérations : l’une est appelée composition horizontale, et l’autre est appelée composition verticale. On présentera dans cette thèse quelques résultats de cette théorie.
Dans un premier temps, on étudiera une généralisation à un corps quelconque K de la présentation diagrammatique du PRO L(Z2) des applications Z2-linéaires introduite par Yves Lafont (voir [10]) et étudiée par Yves Guiraud (voir [8] et [5]). On donnera ainsi la première présentation diagrammatique convergente du PRO L(K) des applications K-linéaires.
Dans un deuxième temps, on étudiera la présentation diagrammatique convergente des matrices orthogonales : les diagrammes orthogonaux. Les matrices orthogonales correspondent aux isométries de Rn (rotations et symétries). Dans ce système de réécriture, on s’intéressera surtout à une règle similaire à l’équation de Yang-Baxter. Celle-ci est décrite en utilisant une certaine application h : [0,π[3 → [0,π[3. Pour étudier les propriétés algébriques de h, nous utiliserons la confluence des pics critiques dans notre système de réécriture, et nous introduirons les diagrammes paramétriques décrivant les calculs sur les angles des portes de rotations créées par la réécriture. En particulier, l’application h satisfait l’équation du tétraèdre (aussi appelée équation de Zamolod- chikov).
Enfin, on présentera les Σ-diagrammes et une généralisation des bases de Gröbner à la dimension 2. Les Σ-diagrammes sont une approche alternative pour les calculs dans les bigèbres. Des exemples d’utilisation des Σ-diagrammes dans ce contexte seront présentés. On prouvera notamment la coassociativité et la cocomutativité de certaines coopérations.
Les deux derniers chapitres ont fait l’objet de publications :
Diagram rewriting for orthogonal matrices : a study of critical peaks, in Rewriting Techniques and Applications, 19th international Conference, Hagenbeg, Austria, July avec Yves Lafont, Lecture Notes in Computer Science 5117, p. 232-245, 2008
Properties of co-operations : diagrammatic proofs, Mathematical Structures in Computer Science 22(6), p. 970-986, 2012.

Title: Diagramm and Σ-diagramm rewriting

Abstract:
The main subject of this thesis is diagram rewriting. This is a generalisation to dimension 2 of word rewriting (that is rewriting in dimension 1). Indeed, diagrams are defined using two opera- tions: the first one is called horizontal composition and the other one is called vertical composition. We present in this thesis some results of this theory.
First, we consider a generalisation to an arbitrary field K of the diagrammatic presentation of the PRO L(Z2) ofZ2-linear maps introduced by Yves Lafont (see [10]) and studied by Yves Guiraud (see [8] and [5]). We get a convergent diagrammatic presentation of the PRO L(K) of K-linear maps.
Then we study a convergent diagrammatic presentation of orthogonal matrices: orthogonal diagrams. Orthogonal matrices correspond to isometries of Rn (rotations and symmetries). In this rewrite system, we focus especially on a rule similar to the Yang-Baxter equation. This rule is described using a certain map h : [0,π[3 → [0,π[3. To study the algebraic properties of h, we use the confluence of critical peaks in our rewrite system and we introduce the parametric diagrams describing calculations of the angles of rotation gates created by rewriting. In particular, the map h satisfies the tetrahedron equation (also called Zamolodchikov equation).
Finally, we present the Σ-diagrams and a generalisation of Gröbner’s bases to dimension 2. Σ-diagrams are an alternative approach for calculation in bialgebras. Examples of use of Σ-diagrams in this context will be presented. We prove in particular the coassociativity and cocomutativity of some cooperations.
The last two chapters have been already published:
Diagram rewriting for orthogonal matrices: a study of critical peaks, in Rewriting Techniques and Applications, 19th international Conference, Hagenbeg, Austria, July with Yves Lafont, Lecture Notes in Computer Science 5117, p. 232-245, 2008
Properties of co-operations: diagrammatic proofs, Mathematical Structures in Computer Science 22(6), p. 970-986, 2012.

Fichier / File

( 523 ko )

début thèse : 10/2007




Thuy NGUYEN THI BICH
(thème SGT)

Titre : Étude de certains ensembles singuliers associés à une application polynomiale

Directeur de thèse : Jean-Paul Brasselet

Rapporteurs : Mutsuo Oka, Ha Huy Vui.

Jury : Jean-Paul Brasselet, Krzysztof Kurdyka, Nguyen Viet Dung, Mutsuo Oka, Anne Pichon, David Trotman, Guillaume Valette, Ha Huy Vui.

Date soutenance : 30 septembre 2013

Universités d'inscription : Aix-Marseille Université

Résumé : La thèse a six chapitres.
Les chapitres 1 et 2 sont des rappels de connaissances de base sur les applications et les variétés comme : les applications propres, dominantes, finies, lipschitziennes et les applications de déterminant jacobien partout non nul ; les rappels des définitions de pseudovariétés, variétés uniréglées, stratifications, homologie d’intersection d’une variété singulière et surtout ensemble des points asymptotiques d’une application polynomiale. Nous donnons ici des exemples pour éclairer les définitions, ainsi que quelques observations sur ces applications qui nous seront utiles pour les chapitres suivants.
Le chapitre 3 concerne l’ensemble des Valette VF dont la définition est donnée dans la proposition 0.3.1.
Les chapitres 4 et 5 concernent les stratifications de l’ensemble des points asymptotiques et de l’ensemble des points critiques d’une application polynomiale F : CnCn.
Le chapitre 6 concerne les caractérisations de l’ensemble des points asymptotiques dans quelques cas particuliers.

Title: Study of certain singular sets associated with a polynomial application

Abstract:
The thesis has six chapters.
Chapters 1 and 2 are reminders of basic knowledge of applications and varieties as : specific, dominant, finished, Lipschitz applications and applications everywhere nonzero Jacobian determinant ; recalls definitions pseudovarieties, uniréglées varieties, stratifications, intersection homology variety of singular points, and above all an asymptotic polynomial. We give examples to clarify the definitions and some observations on the applications that will be useful in the following chapters.
Chapter 3 covers all Vallette VF whose definition is given in the proposition 0.3.1.
Chapters 4 and 5 deal with stratifications of all asymptotic point and the set of critical points of a polynomial application F: CnCn.
Chapter 6 deals with the characterization of all asymptotic points in some cases individuals.

Fichier / File

( 2,18 Mo )





Virgile DUCET
(thème ATI)

Titre : Construction of algebraic curves with many rational points over finite fields

Directeur de thèse : David Kohel

Rapporteurs : Everett Howe, John Voight.

Jury : Everett Howe, David Kohel, Gilles Lachaud, Marc Perret, Christophe Ritzenthaler, François Rodier, René Schoof, John Voight.

Date soutenance : 23 septembre 2013

Universités d'inscription : Aix-Marseille Université

Résumé : L'étude du nombre de points rationnels d'une courbe définie sur un corps fini se divise naturellement en deux cas : lorsque le genre est petit (typiquement g inférieur ou égal à 50), et lorsqu'il tend vers l'infini. Nous consacrons une partie de cette thèse à chacun de ces cas. Dans la première partie de notre étude nous expliquons comment calculer l'équation de n'importe quel revêtement abélien d'une courbe définie sur un corps fini. Nous utilisons pour cela la théorie explicite du corps de classe fournie par les extensions de Kummer et d'Artin-Schreier-Witt. Nous détaillons également un algorithme pour la recherche de bonnes courbes, dont l'implémentation fournit de nouveaux records de nombre de points sur les corps finis d'ordres 2 et 3 respectivement. Nous étudions dans la seconde partie une formule de trace d'opérateurs de Hecke sur des formes modulaires quaternioniques, et montrons que les courbes de Shimura correspondantes forment naturellement des suites récursives de courbes asymptotiquement optimales sur une extension quadratique du corps de base. Nous prouvons également qu'alors la contribution essentielle en points rationnels est fournie par les points supersinguliers.

Mots-clés : courbes avec beaucoup de points, corps de fonctions, théorie explicite du corps de classe, théorie de Kummer, vecteurs de Witt, équations de revêtements abéliens, algèbres de quaternions, courbes de Shimura, formes modulaires, opérateurs de Hecke, points supersinguliers, tours récursives.

Abstract: The study of the number of rational points of a curve defined over a finite field naturally falls into two cases: when the genus is small (typically g less than 50), and when it tends to infinity. We devote one part of this thesis to each of these cases. In the first part of our study, we explain how to compute the equation of any abelian covering of a curve defined over a finite field. For this we use explicit class field theory provided by Kummer and Artin-Schreier-Witt extensions. We also detail an algorithm for the search of good curves, whose implementation provides new records of number of points over the finite fields of orders 2 and 3 respectively. In the second part, we study a trace formula of Hecke operators on quaternionic modular forms, and we show that the associated Shimura curves naturally form recursive sequences of asymptotically optimal curves over a quadratic extension of the base field. Moreover, we then prove that the essential contribution to the rational points is provided by supersingular points.

Keywords: curves with many points, body functions, explicit class field theory, Kummer theory, Witt vectors, equations of Abelian coverings, quaternion algebras, Shimura curves, modular forms, Hecke operators, supersingular points, recursive towers.

Fichier / File

( 618 Ko )





Milakulo TUKUMULI
(thème ATI)

Titre : Étude de la construction effective des algorithmes de type Chudnovsky pour la multiplication dans les corps finis

Directeurs de thèse : Alexis Bonnecaze, Stéphane Ballet

Rapporteurs : Daniel Augot, Ferruh Özbudak.

Jury : Daniel Augot, Yves Aubry, Stéphane Ballet, Alexis Bonnecaze, Reynald Lercier, Traian Muntean (invité), Ferruh Özbudak, Robert Rolland, Serge Vladut.

Date soutenance : 13 septembre 2013

Universités d'inscription : Aix-Marseille Université

Résumé : On s'intéresse dans cette thèse à la complexité bilinéaire de la multiplication dans toute extension de degré $n$ d'un corps $\F_{q}$ à $q$ éléments, qui est étroitement liée au rang de tenseur de la multiplication dans $\F_{q^n}$. L'algorithme de type évaluation-interpolation, introduit par D.V et G.V Chudnovsky en 1987, est à la base des techniques algorithmiques fournissant actuellement les meilleures bornes uniformes et asymptotiques de la complexité bilinéaire. Pour obtenir ces meilleures bornes, la stratégie adoptée jusqu'à présent consistait à fixer le degré des places en augmentant le genre du corps de fonctions algébriques.
Néanmoins, l'étude de la construction effective associée à ce type de stratégie fut jusqu'à présent négligée en raison d'un obstacle, lié à la construction du point de degré $n$, relevé par Shparlinski, Tsfasman et Vladut en 1992.
On présente dans cette thèse une nouvelle stratégie qui consiste à fixer le genre du corps de fonctions algébriques tout en augmentant le degré des places.
En appliquant cette stratégie aux corps de fonctions elliptiques, on montre d'une part que le rang de tenseur de la multiplication dans $\F_{q^n}$ est quasi-linéaire en $n$, et d'autre part que la construction des algorithmes de multiplications bilinéaires issus de cette stratégie est réalisable en temps polynomial. On montre également comment construire explicitement ces algorithmes sur $\F_{q^n}$, en les illustrant par un exemple. Enfin, on établit la première construction asymétrique de l'algorithme de type Chudnovsky.

Mots-clés : rang de tenseur de la multiplication, complexité bilinéaire, algorithme de type Chudnovsky, corps de fonctions algébriques, corps finis.

Title: Study of effective construction of Chudnovsky type algorithms for the multiplication in finite fields

Abstract: In this thesis, we focus on the bilinear complexity of multiplication in any degree $n$ extension of the finite field $ \F_{q}$, which is closely related to the tensor rank of multiplication in $ \F_{q^n} $. The evaluation-interpolation type algorithm introduced by D.V and G.V Chudnovsky in 1987, is the basis of all algorithmic technique providing for now, the lower asymptotic and uniform bounds for the bilinear complexity.
So far, the strategy to obtain these lower bounds was to fix the degree of places while increasing the genus of algebraic function fields. However, the study of the effective construction associated with this kind of strategy was until now neglected because of an obstacle related to the construction of a degree $n$ point, identified par Shparlinski, Tsfasman and Vladut in 1992. We present a new strategy which consists in fixing the genus of algebraic function fields while increasing the degree of places. Applying this strategy to the elliptic function fields, we show on the one hand that the tensor rank of multiplication in $ \F_{q^n} $ is quasi-linear in $ n $, and on the other hand we prove that the construction of bilinear multiplication algorithms with this strategy is feasible in polynomial time. We also show how to construct explicitly these algorithms over $ \F_{q^n} $ for large $n$ by illustrating the construction with an example. Finally, we establish the first asymmetric construction of the Chudnovsky type algorithm.

Keywords: tensor rank of multiplication, bilinear complexity, Chudnovsky type algorithm, algebraic function fields, finite fields.

Fichier / File

( 0 Ko )





Last update : december 13, 2013, EL.