L'inférence grammaticale s'intéresse à l'apprentissage automatique de langages formels. Ces derniers sont organisés en plusieurs classes formant la hiérarchie de Chomsky. Parmi elles, les langages réguliers, reconnus par des automates finis déterministes, forment la classe la plus « simple » à apprendre : l'apprentissage des automates a largement été étudié et a donné naissance à plusieurs algorithmes d'inférence grammaticale.<br /><br />Toutefois, un problème concernant les données est devenu crucial : celui du bruit. Des propositions d'algorithmes ont vu le jour pour essayer de résoudre ce problème, mais nous montrons que les résultats ne sont toujours pas satisfaisants, y compris pour les langages réguliers. Or, puisqu'ils forment la base de la hiérarchie de Chomsky, ce sont toutes les classes de la hiérarchie qui ne peuvent être apprises en situations bruitées.<br /><br />Aussi, nous proposons une nouvelle classe de langages qui semble ne pas souffrir de ce handicap : celle des boules de mots. Nous démontrons que cette classe, de prime abord peu orthodoxe mais utilisée dans de nombreuses applications comme la correction orthographique ou la recherche de plus proches voisins, reste identifiable à la limite même lorsque les données d'apprentissage subissent l'influence d'un bruit non statistique.<br /><br />De plus, nous introduisons les requêtes de correction basées sur la distance d'édition et nous présentons un algorithme d'apprentissage des boules de mots à partir de telles requêtes. Nous montrons expérimentalement que de simples heuristiques a posteriori suffisent à le rendre résistant lorsque l'oracle répond approximativement à de telles requêtes. Ceci justifie encore une<br />fois la robustesse des boules de mots au bruit.<br /><br />Contrairement aux idées reçues, le bruit n'est donc pas une malédiction en inférence grammaticale : les langages à base de distance offrent de nouvelles perspectives.

Représenter un objet géométrique complexe par un ensemble de primitives simples est une tâche souvent fondamentale, que ce soit pour la reconstruction et la réparation de données, ou encore pour faciliter la visualisation ou la manipulation des données. Le choix de la ou les primitives, ainsi que celui de la méthode d'approximation, impactent fortement les propriétés de la représentation de forme qui sera obtenue.Dans cette thèse, nous utilisons les boules comme seule primitive. Nous prenons ainsi un grand soin à décrire les unions finies de boules et leur structure. Pour cela, nous nous reposons sur les faisceaux de boules. En particulier, nous aboutissons à une description valide en toute dimension, sans hypothèse de position générale. En chemin, nous obtenons également plusieurs résultats portant sur les tests d'inclusion locale et globale dans une union de boules.Nous proposons également une nouvelle méthode d'approximation par union finie de boules, l'approximation par boules à (delta,epsilon)-près. Cette approche contraint l'union de boules à couvrir un sous-ensemble de la forme d'origine (précisément, un epsilon-érodé), tout en étant contenu dans un sur-ensemble de la forme (un delta-dilaté). En nous appuyant sur nos précédents résultats portant sur les unions de boules, nous démontrons plusieurs propriétés de ces approximations. Nous verrons ainsi que calculer une approximation par boules à (delta,epsilon)-près qui soit de cardinal minimum est un problème NP-complet. Pour des formes simples dans le plan, nous présentons un algorithme polynomial en temps et en espace qui permet de calculer ces approximations de cardinal minimum. Nous concluons par une généralisation de notre méthode d'approximation pour une plus large variété de sous-ensembles et sur-ensembles. / Describing a complex geometric shape with a set of simple primitives is often a fundamental task for shape reconstruction, visualization, analysis and manipulation. The type of primitives, as well as the choice of approximation scheme, both greatly impact the properties of the resulting shape representation.In this PhD, we focus on balls as primitives. Using pencils of balls, we carefully describe finite unions of balls and their structure. In particular, our description holds in all dimension without assuming general position. On our way, we also establish various results and tools to test local and global inclusions within these unions.We also propose a new approximation scheme by union of balls, the (delta,epsilon)-ball approximation. This scheme constrains the approximation to cover a core subset of the original shape (specifically, an epsilon-erosion), while being contained within a superset of the shape (a delta-dilation). Using our earlier results regarding finite unions of balls, we prove several properties of these approximations. We show that computing a cardinal minimum (delta,epsilon)-ball approximation is an NP-complete problem. For simple planar shapes however, we present a polynomial time and space algorithm that outputs a cardinal minimum approximation. We then conclude by generalizing the approximation scheme to a wider range of core subsets and bounding supersets.

.

Nous étudions des champs aléatoires pouvant modéliser certains milieux poreux. Nous nous intéressons à leurs statistiques au second ordre et en particulier à leur autosimilarité. Sous des hypothèses de stationnarité, une mesure spectrale caractérise le champ. L'homogénéité asymptotique directionnelle de la mesure détermine l'autosimilarité asymptotique du champ; le plus petit coefficient d'homogénéité dans une échelle logarithmique en donne l'ordre. Pour déterminer l'anisotropie on peut considérer une transformée de Radon du champ dont l'ordre d'autosimilarité dépend de la direction. Ces résultats au second ordre sont adaptés à des modèles gaussiens, l'ordre d'autosimilarité s'estimant par les variations quadratiques. Nous considérons le problème de l'injectivité des transformées de Radon. Enfin, nous étudions un modèle poissonien obtenu par agrégation de petites boules. Les propriétés d'autosimilarité sont analogues au second ordre mais atypiques pour la convergence en loi.

Un problème classique est d'identifier des sous-ensembles (pré)compacts de l'ensemble des espaces métriques de longueur (la distance entre deux espaces étant celle de Gromov-Hausdorff) et d'y étudier la continuité, la rigidité ou la « bornitude » de certains invariants. Habituellement, on considère l'ensemble <B>R</B><sub><I>n,K,D</I></SUB> des variétés de dimension, courbure et diamètre bornés (par <I>n</I>, -<I>K</I><SUP>2</SUP> et <I>D</I>), qui n'est pas complet (la « bornitude » n'y découle donc pas d'une preuve unifiée de type compacité/continuité). Nous nous affranchissons des hypothèses de courbure en nous plaçant sur la famille <B>M</B>_{δ,<I>H,D</I>} des classes d'isométries d'espaces métriques de longueur de diamètre et d'entropie (volumique) bornés par <I>D</I> et <I>H</I>, qui admettent un revêtement universel et dont le groupe fondamental est δ-non-abélien (i.e. vérifie certaines des propriétés algébriques de croissance des groupes fondamentaux de variétés de courbure négative). Nous montrons que l'entropie est peu sensible à des variations locales drastiques de la métrique ou de la topologie, donc que <B>M</B>_{δ,<I>H,D</I>} est beaucoup plus grand que <B>R</B>_<I>n,K,D</I>. Nous prouvons cependant que <B>M</B>_{δ,<I>H,D</I>} est complet, et que le sous-ensemble <B>M</B>⁰_{δ,<I>H,D,V</I>} (formé des variétés de courbure négative et de volume majoré par <I>V</I>) y est d'adhérence compacte. Sur <B>M</B>⁰_{δ,<I>H,D,V</I>} nous établissons des majorations uniformes du noyau de la chaleur qui impliquent la précompacité de cette famille pour la distance spectrale, ce qui assure une description des propriétés spectrales des espaces-limites. Sur <B>M</B>_{δ,<I>H,D</I>} nous prouvons que l'entropie et le spectre marqué des longueurs (resp. le premier nombre de Betti) sont des fonctions lipschitziennes (resp. localement constantes) et nous comparons les volumes et les bornes inférieures de la courbure de deux variétés ε₀-proches. La méthode s'appuie d'une part sur une estimation de type Bishop (mais sans hypothèse de courbure) du volume des boules, d'autre part sur le calcul d'un ε₀ := ε₀ (δ,<I>H,D</I>) universel tel qu'une ε₀-approximation de Hausdorff (non continue) entre deux espaces <I>X</I> et <I>Y</I> de <B>M</B>_{δ,<I>H,D</I>} induise un isomorphisme ρ entre les groupes d'automorphismes de leurs revêtements universels et se relève en une ε₀-presque-isométrie ρ-équivariante entre ces revêtements (une version de ce résultat valable hors de <B>M</B>_{δ,<I>H,D</I>} est aussi donnée).

Dans tout ce qui suit, nous considérons une variété riemannienne compacte de dimension au moins égale à 2. A tout domaine (suffisamment régulier) $\Omega$, on peut associer la première valeur propre $\lambda_\Omega$ de l'opérateur de Laplace-Beltrami avec condition de Dirichlet au bord. Nous dirons qu'un domaine $\Omega$ est extrémal (sous entendu, pour la première valeur propre de l'opérateur de Laplace-Beltrami) si $\Omega$ est un point critique de la fonctionnelle $\Omega \rightarrow \lambda_\Omega$ sous une contrainte de volume $Vol (\Omega) = c_0$. Autrement dit, $\Omega$ est extrémal si, pour toute famille régulière $\{\Omega_t\}_{t \in (-t_0,t_0)}$ de domaines de volume constant, telle que $\Omega_0 = \Omega$, la dérivée de la fonction $t \rightarrow \lambda_{\Omega_t}$ en $0$ est nulle. Rappelons que les domaines extrémaux sont caractérisés par le fait que la fonction propre, associée à la première valeur propre sur le domaine avec condition de Dirichlet au bord, a une donnée de Neumann constante au bord. Ce résultat a été démontré par A. El Soufi et S. Ilias en 2007. Les domaines extrémaux sont donc des domaines sur lesquels peut être résolu un problème elliptique surdéterminé. L'objectif principal de cette thèse est la construction de domaines extrémaux pour la première valeur propre de l'opérateur de Laplace-Beltrami avec condition de Dirichlet au bord. Nous donnons des résultats d'existence de domaines extrémaux dans le cas de petits volumes ou bien dans le cas de volumes proches du volume de la variété. Nos résultats permettent ainsi de donner de nouveaux exemples non triviaux de domaines extrémaux. Le premier résultat que nous avons obtenu affirme que si une variété admet un point critique non dégénéré de la courbure scalaire, alors pour tout volume petit il existe un domaine extrémal qui peut être construit en perturbant une boule géodésique centrée en ce point critique non dégénéré de la courbure scalaire. La méthode que nous utilisons pour construire ces domaines extrémaux revient à étudier l'opérateur (non linéaire) qui à un domaine associe la donnée de Neumann de la première fonction propre de l'opérateur de Laplace-Beltrami sur le domaine. Il s'agit d'un opérateur (hautement non linéaire), nonlocal, elliptique d'ordre 1. Dans $\mathbb R^n \times \mathbb{R}/\, \mathbb{Z}$, le domaine cylindrique $B_r \times \mathbb{R}/\, \mathbb{Z}$, où $B_r$ est la boule de rayon $r >0$ dans $\mathbb{R}^{n}$, est un domaine extrémal. En étudiant le linéarisé de l'opérateur elliptique du premier ordre défini par le problème précédent et en utilisant un résultat de bifurcation, nous avons démontré l'existence de domaines extrémaux nontriviaux dans $\mathbb R^{n}\times \mathbb{R}/\, \mathbb{Z}$. Ces nouveaux domaines extrémaux sont proches de domaines cylindriques $B_r \times \mathbb{R}/ \mathbb{Z}$. S'ils sont invariants par rotation autour de l'axe vertical, ces domaines ne sont plus invariants par translations verticales. Ce deuxième résultat donne un contre-exemple à une conjecture de Berestycki, Caffarelli et Nirenberg énoncée en 1997. Pour de grands volumes la construction de domaines extrémaux est techniquement plus difficile et fait apparaître des phénomènes nouveaux. Dans ce cadre, nous avons dû distinguer deux cas selon que la première fonction propre $\phi_0$ de l'opérateur de Laplace-Beltrami sur la variété est constante ou non. Les résultats que nous avons obtenus sont les suivants : $\phi_0$ a des points critiques non dégénérés (donc en particulier n'est pas constante), alors pour tout volume assez proche du volume de la variété, il existe un domaine extrémal obtenu en perturbant le complément d'une boule géodésique centrée en un des points critiques non dégénérés de $\phi_0$. Si $\phi_0$ est constante et la variété admet des points critiques non dégénérés de la courbure scalaire, alors pour tout volume assez proche du volume de la variété il existe un domaine extrémal obtenu en perturbant le complément d'une boule géodésique centrée en un des points critiques non dégénérés de la courbure scalaire.

Dans le cadre de la géométrie riemannienne globale sans hypothèse de courbure en lien avec la topologie, nous nous intéressons au volume maximal des boules de rayon fixé dans les revêtements universels des graphes et des surfaces. Dans la première partie, nous prouvons que si l'aire d'une surface riemannienne fermée M de genre au moins 2 est suffisamment petite par rapport à son aire hyperbolique, alors pour chaque rayon R>0, le revêtement universel de M contient une R-boule d'aire au moins l'aire d'une cR-boule dans le plan hyperbolique, où c<1 est une constante universelle. En particulier (quitte à prendre l'aire de la surface encore plus petite), nous démontrons que pour chaque rayon R plus grand ou égal à 1, le revêtement universel de M contient une R-boule d'aire au moins l'aire d'une R-boule dans le plan hyperbolique. Ce résultat répond positivement pour les surfaces, à une question de L. Guth. Nous démontrons également que si Gamma est un graphe connexe de premier nombre de Betti b et de longueur su suffisamment petite par rapport à la longueur d'un graphe trivalent Gamma_b de premier nombre de Betti b dont la longueur de chaque arête est 1, alors pour chaque rayon R>0, le revêtement universel de Gamma contient une R-boule d'aire au moins c fois l'aire d'une R-boule dans le revêtement universel de Gamma_b, où c est dans l'intervalle (1/2 ,1). Dans la deuxième partie, nous généralisons un théorème de M. Gromov concernant le nombre maximal de courts lacets homotopiquement indépendants basés en un même point. Plus précisément, nous prouvons que sur toute surface riemannienne fermée M de genre g et d'aire normalisée à g, il existe au moins log(2g) lacets homotopiquement indépendants basés en un même point de longueur au plus C log(g), où C est une constante positive indépendante du genre. Comme corollaire immédiat de ce théorème, nous redémontrons l'inégalité systolique asymptotique sur la systole séparante. Nous démontrons également un théorème analogue pour les graphes métriques. Plus précisément, nous prouvons que sur chaque graphe métrique Gamma de premier nombre de Betti b et de longueur b, il existe au moins log(b) lacets homologiquement indépendants basés en un même point de longueur au plus 48 log(b). Ce résultat étend la borne en log(b) sur la systole homologique dûe à Bollobàs-Szemerédi-Thomason à au moins log(b) lacets homologiquement indépendants basés en un même point. En outre, nous donnons des exemples de graphes où notre résultat est optimal (à une constante multiplicative près).

Dans le cadre de la géométrie riemannienne globale sans hypothèse de courbure en lien avec la topologie, nous nous intéressons au volume maximal des boules de rayon fixé dans les revêtements universels des graphes et des surfaces. Dans la première partie, nous prouvons que si l’aire d’une surface riemannienne fermée M de genre g ≥ 2 est suffisamment petite par rapport à son aire hyperbolique, alors pour chaque rayon R ≥ 0, le revêtement universel de M contient une R-boule d’aire au moins l’aire d’une cR-boule dans le plan hyperbolique, où c ∈ (0; 1) est une constante universelle. En particulier (quitte à prendre l’aire de la surface encore plus petite), nous démontrons que pour chaque rayon R ≥ 1, le revêtement universel de M contient une R-boule d’aire au moins l’aire d’une R-boule dans le plan hyperbolique. Ce résultat répond positivement pour les surfaces, à une question de L. Guth. Nous démontrons également que si Γ est un graphe connexe de premier nombre de Betti b ≥ 2 et de longueur suffisamment petite par rapport à la longueur d’un graphe trivalent Γb de premier nombre de Betti b dont la longueur de chaque arête est 1, alors pour chaque rayon R ≥ 0, le revêtement universel de Γ contient une R-boule d’aire au moins c fois l’aire d’une R-boule dans le revêtement universel de Γb, où c ∈ ( ½ ; 1). / This thesis deals with global Riemannian geometry without curvature assumptions and its link to topology, we focus on the maximal volume of balls of fixed radius in the universal covers of graphs and surfaces. In the first part, we prove that if the area of a closed Riemannian surface M of genus at least two is sufficiently small with respect to its hyperbolic area, then for every radius R ≥ 0 the universal cover of M contains an R-ball with area at least the area of a cR-ball in the hyperbolic plane, where c ∈ (0; 1) is a universal positive constant. In particular (taking the area of M smaller if needed), we prove that for every radius R ≥ 1, the universal cover of M contains an R-ball with area at least the area of a ball with the same radius in the hyperbolic plane. This result answers positively a question of L. Guth for surfaces. We also prove an analog result for graphs. Specifically, we prove that if Γ is a connected metric graph of first Betti number b ≥ 2 and of length sufficiently small with respect to the length of a connected trivalent graph Γb of the same Betti number where the length of each edge is 1, then for every radius R ≥ 0 the universal cover of Γ contains an R-ball with length at least c times the length of an R-ball in the universal cover of Γb, where c ∈ ( ½ ; 1) is a universal constant.

Si µ est une mesure de probabilité à support compact dans uns espace vectoriel ou affine de dimension finie, le barycentre (ou centre de gravité) de µ est un point bien défini de l’espace. Mais des difficultés surgissent lorsque l’espace est remplacé par une variété riemannienne M ; dans ce cas, même en se restreignant aux variétés convexes (c’est-à-dire deux dont points quelconques sont toujours joints par une géodésique et une seule) et aux mesures à support fini, il est en général impossible d'assigner à chaque probabilité un barycentre de façon que, d'une part,pour tous λϵ [0; 1] et x et y dans M, le barycentre de µ = (1- λ ) δˣ+ λ δy soit toujours le point γ(λ), sur la géodésique telle que γ (0) = x et γ (1) = y, et que, d'autre part, soit préservée la propriété d'associativité (pour faire une moyenne, on peut commencer par faire des moyennes partielles). Dés que la mesure µ est portée par au moins trois points non tous situées sur une même géodésique, il y a de multiples façons différentes de définir son barycentre comme barycentre de barycentres partiels de barycentres partiels etc., chaque opération élémentaire ne faisant intervenir que deux points. On obtient ainsi tout un ensemble de points de M, les barycentres itérés de µ . Pour des probabilités plus générales, on appelle barycentre convexe de µ l'ensemble b(µ) des points x de M qui sont limites d'une suite (xn), ou chaque xn est un barycentre itéré d'une probabilité µn à support fini, les mesures µn tendant vers µ. / If μ is a probability measure carried on a small in a finite-dimension vectorial or affine space, the μ- barycenter (center of gravity) is a well-defined point in space. Nevertheless, difficulties arise when space is changed by Riemannian manifold M. In this case, even if we limit to convex manifolds (i.e : when any two points are joined by one geodesic and just one) and to finite-support measures, it’s, in general impossible to attribute a barycenter to each probability, in such a way, on one hand, whetever λϵ [0; 1] and x and y in M, the barycenter of µ = (1- λ ) δˣ+ λ δy will be always the point γ(λ) of the geodesic such that γ (0) = x et γ (1) =y, and on another hand, the associative property will be maintained (to make a mean, we can begin by doing partial means). Once the measure μ is carried by at least three points which are not all localed on the same geodesic, there are different manners to define its barycenter as one of partial barycenters of partial barycenters and so on, in which each elementary operation includes only two points. Thus, we get a whole set of set of points of M, the iterated barycenters of μ. For more general probabilities μ, we call convex barycenter of μ, the set b(μ) of points x of M which are limit of sequence (xn), in which each xn is an iterated barycenter of a finite support probability μn, the measure μn tending to μ.

Dans cette thèse, nous étudions les propriétés asymptotiques de paramètres fonctionnels conditionnels en statistique non paramétrique, quand la variable explicative prend ses valeurs dans un espace de dimension infinie. Dans ce cadre non paramétrique, on considère les estimateurs des paramètres fonctionnels usuels, tels la loi conditionnelle, la densité de probabilité conditionnelle, ainsi que le quantile conditionnel. Le premier travail consiste à proposer un estimateur du quantile conditionnel et de prouver sa convergence uniforme sur un sous-ensemble compact. Afin de suivre la convention dans les études biomédicales, nous considérons une suite de v.a {Ti, i ≥ 1} identiquement distribuées, de densité f, censurée à droite par une suite aléatoire {Ci, i ≥ 1} supposée aussi indépendante, identiquement distribuée et indépendante de {Ti, i ≥ 1}. Notre étude porte sur des données fortement mélangeantes et X la covariable prend des valeurs dans un espace à dimension infinie.Le second travail consiste à établir la normalité asymptotique de l’estimateur à noyau du quantile conditionnel convenablement normalisé, pour des données fortement mélangeantes, et repose sur la probabilité de petites boules. Plusieurs applications à des cas particuliers ont été traitées. Enfin, nos résultats sont appliqués à des données simulées et montrent la qualité de notre estimateur. / In this thesis, we study some asymptotic properties of conditional functional parameters in nonparametric statistics setting, when the explanatory variable takes its values in infinite dimension space. In this nonparametric setting, we consider the estimators of the usual functional parameters, as the conditional law, the conditional probability density, the conditional quantile. We are essentially interested in the problem of forecasting in the nonparametric conditional models, when the data are functional random variables. Firstly, we propose an estimator of the conditional quantile and we establish its uniform strong convergence with rates over a compact subset. To follow the convention in biomedical studies, we consider an identically distributed sequence {Ti, i ≥ 1}, here density f, right censored by a random {Ci, i ≥ 1} also assumed independent identically distributed and independent of {Ti, i ≥ 1}. Our study focuses on dependent data and the covariate X takes values in an infinite space dimension. In a second step we establish the asymptotic normality of the kernel estimator of the conditional quantile, under α-mixing assumption and on the concentration properties on small balls of the probability measure of the functional regressors. Many applications in some particular cases have been also given.