• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 36
  • 30
  • 2
  • Tagged with
  • 70
  • 70
  • 42
  • 39
  • 16
  • 16
  • 15
  • 14
  • 13
  • 13
  • 12
  • 10
  • 10
  • 10
  • 9
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
21

Topics in Convex Optimization: Interior-Point Methods, Conic Duality and Approximations

Glineur, François 26 January 2001 (has links) (PDF)
Optimization is a scientific discipline that lies at the boundary<br />between pure and applied mathematics. Indeed, while on the one hand<br />some of its developments involve rather theoretical concepts, its<br />most successful algorithms are on the other hand heavily used by<br />numerous companies to solve scheduling and design problems on a<br />daily basis.<br /><br />Our research started with the study of the conic formulation for<br />convex optimization problems. This approach was already studied in<br />the seventies but has recently gained a lot of interest due to<br />development of a new class of algorithms called interior-point<br />methods. This setting is able to exploit the two most important<br />characteristics of convexity:<br /><br />- a very rich duality theory (existence of a dual problem that is<br />strongly related to the primal problem, with a very symmetric<br />formulation),<br />- the ability to solve these problems efficiently,<br />both from the theoretical (polynomial algorithmic complexity) and<br />practical (implementations allowing the resolution of large-scale<br />problems) points of view.<br /><br />Most of the research in this area involved so-called self-dual<br />cones, where the dual problem has exactly the same structure as the<br />primal: the most famous classes of convex optimization problems<br />(linear optimization, convex quadratic optimization and semidefinite<br />optimization) belong to this category. We brought some contributions <br />in this field:<br />- a survey of interior-point methods for linear optimization, with <br />an emphasis on the fundamental principles that lie behind the design <br />of these algorithms,<br />- a computational study of a method of linear approximation of convex <br />quadratic optimization (more precisely, the second-order cone that <br />can be used in the formulation of quadratic problems is replaced by a <br />polyhedral approximation whose accuracy can be guaranteed a priori),<br />- an application of semidefinite optimization to classification, <br />whose principle consists in separating different classes of patterns <br />using ellipsoids defined in the feature space (this approach was <br />successfully applied to the prediction of student grades).<br /><br />However, our research focussed on a much less studied category of<br />convex problems which does not rely on self-dual cones, i.e.<br />structured problems whose dual is formulated very differently from<br />the primal. We studied in particular<br />- geometric optimization, developed in the late sixties, which<br />possesses numerous application in the field of engineering<br />(entropy optimization, used in information theory, also belongs to<br />this class of problems)<br />- l_p-norm optimization, a generalization of linear and convex<br />quadratic optimization, which allows the formulation of constraints<br />built around expressions of the form |ax+b|^p (where p is a fixed<br />exponent strictly greater than 1).<br /><br />For each of these classes of problems, we introduced a new type of<br />convex cone that made their formulation as standard conic problems<br />possible. This allowed us to derive very simplified proofs of the<br />classical duality results pertaining to these problems, notably weak<br />duality (a mere consequence of convexity) and the absence of a<br />duality gap (strong duality property without any constraint<br />qualification, which does not hold in the general convex case). We<br />also uncovered a very surprising result that stipulates that<br />geometric optimization can be viewed as a limit case of l_p-norm<br />optimization. Encouraged by the similarities we observed, we<br />developed a general framework that encompasses these two classes of<br />problems and unifies all the previously obtained conic formulations.<br /><br />We also brought our attention to the design of interior-point<br />methods to solve these problems. The theory of polynomial algorithms<br />for convex optimization developed by Nesterov and Nemirovski asserts<br />that the main ingredient for these methods is a computable<br />self-concordant barrier function for the corresponding cones. We<br />were able to define such a barrier function in the case of<br />l_p-norm optimization (whose parameter, which is the main<br />determining factor in the algorithmic complexity of the method, is<br />proportional to the number of variables in the formulation and<br />independent from p) as well as in the case of the general<br />framework mentioned above.<br /><br />Finally, we contributed a survey of the self-concordancy property,<br />improving some useful results about the value of the complexity<br />parameter for certain categories of barrier functions and providing<br />some insight on the reason why the most commonly adopted definition<br />for self-concordant functions is the best possible.
22

Sur la commande de satellites à entrées saturantes

Boada, Josep 10 December 2010 (has links) (PDF)
La théorie de la commande a évolué de façon significative dans le domaine de l'automatique non-linéaire. Cependant, les méthodes utilisées actuellement dans l'industrie aérospatiale sont le plus souvent basées sur des techniques de commande linéaire. Les spécifications, toujours plus exigeantes en termes de fiabilité et performance, imposent l'utilisation de techniques de plus en plus complexes. Ainsi, l'industrie cherche des solutions dans les nouvelles techniques de la théorie de la commande non-linéaire. En particulier, la limitation des actionneurs représente un phénomène non-linéaire commun dans la plupart des systèmes physiques. Des actionneurs saturés peuvent engendrer la dégradation de la performance, l'apparition de cycles limites ou d'états d'équilibre non désirés et même l'instabilité du système bouclé. Le but de la thèse est d'adapter et de développer les techniques de synthèse anti-windup à la commande de haute précision des axes angulaires et linéaires de satellites. Dans le domaine spatial, cet objectif se retrouve dans les missions de commande en accélération et aussi du vol en formation. Ces missions utilisent des propulseurs de haute précision où leur capacité maximale est très basse. Ces systèmes propulsifs présentent une modélisation particulière. Des fonctions de répartition adaptées à la synthèse anti-windup ont été étudiées. De plus, en tenant compte de l'état de l'art de la synthèse anti-windup, il y a un vrai besoin d'utiliser des techniques de symétrisation pour la fonction saturation. Le but principal de ce travail consiste à utiliser les techniques développées sur une application aérospatiale. A titre d'exemple, une stratégie complète est proposée afin de contrôler l'attitude et la position relative d'une mission de vol en formation.
23

Inertial Gradient-Descent algorithms for convex minimization / Algorithmes de descente de gradient inertiels pour la minimisation convexe.

Apidopoulos, Vasileios 11 October 2019 (has links)
Cette thèse porte sur l’étude des méthodes inertielles pour résoudre les problèmes de minimisation convexe structurés. Depuis les premiers travaux de Polyak et Nesterov, ces méthodes sont devenues très populaires, grâce à leurs effets d’accélération. Dans ce travail, on étudie une famille d’algorithmes de gradient proximal inertiel de type Nesterov avec un choix spécifique de suites de sur-relaxation. Les différentes propriétés de convergence de cette famille d’algorithmes sont présentées d’une manière unifiée, en fonction du paramètre de sur-relaxation. En outre, on étudie ces propriétés, dans le cas des fonctions lisses vérifiant des hypothèses géométriques supplémentaires, comme la condition de croissance (ou condition de Łojasiewicz). On montre qu’en combinant cette condition de croissance avec une condition de planéité (flatness) sur la géométrie de la fonction minimisante, on obtient de nouveaux taux de convergence. La stratégie adoptée ici, utilise des analogies du continu vers le discret, en passant des systèmes dynamiques continus en temps à des schémas discrets. En particulier, la famille d’algorithmes inertiels qui nous intéresse, peut être identifiée comme un schéma aux différences finies d’une équation/inclusion différentielle. Cette approche donne les grandes lignes d’une façon de transposer les différents résultats et leurs démonstrations du continu au discret. Cela ouvre la voie à de nouveaux schémas inertiels possibles, issus du même système dynamique. / This Thesis focuses on the study of inertial methods for solving composite convex minimization problems. Since the early works of Polyak and Nesterov, inertial methods become very popular, thanks to their acceleration effects. Here, we study a family of Nesterov-type inertial proximalgradient algorithms with a particular over-relaxation sequence. We give a unified presentation about the different convergence properties of this family of algorithms, depending on the over-relaxation parameter. In addition we addressing this issue, in the case of a smooth function with additional geometrical structure, such as the growth (or Łojasiewicz) condition. We show that by combining growth condition and a flatness-type condition on the geometry of the minimizing function, we are able to obtain some new convergence rates. Our analysis follows a continuous-to-discrete trail, passing from continuous-on time-dynamical systems to discrete schemes. In particular the family of inertial algorithms that interest us, can be identified as a finite difference scheme of a differential equation/inclusion. This approach provides a useful guideline, which permits to transpose the different results and their proofs from the continuous system to the discrete one. This opens the way for new possible inertial schemes, derived by the same dynamical system.
24

Modélisation du langage à l'aide de pénalités structurées / Modeling language with structured penalties

Nelakanti, Anil Kumar 11 February 2014 (has links)
La modélisation de la langue naturelle est l¿un des défis fondamentaux de l¿intelligence artificielle et de la conception de systèmes interactifs, avec applications dans les systèmes de dialogue, la génération de texte et la traduction automatique. Nous proposons un modèle log-linéaire discriminatif donnant la distribution des mots qui suivent un contexte donné. En raison de la parcimonie des données, nous proposons un terme de pénalité qui code correctement la structure de l¿espace fonctionnel pour éviter le sur-apprentissage et d¿améliorer la généralisation, tout en capturant de manière appropriée les dépendances à long terme. Le résultat est un modèle efficace qui capte suffisamment les dépendances longues sans occasionner une forte augmentation des ressources en espace ou en temps. Dans un modèle log-linéaire, les phases d¿apprentissage et de tests deviennent de plus en plus chères avec un nombre croissant de classes. Le nombre de classes dans un modèle de langue est la taille du vocabulaire, qui est généralement très importante. Une astuce courante consiste à appliquer le modèle en deux étapes: la première étape identifie le cluster le plus probable et la seconde prend le mot le plus probable du cluster choisi. Cette idée peut être généralisée à une hiérarchie de plus grande profondeur avec plusieurs niveaux de regroupement. Cependant, la performance du système de classification hiérarchique qui en résulte dépend du domaine d¿application et de la construction d¿une bonne hiérarchie. Nous étudions différentes stratégies pour construire la hiérarchie des catégories de leurs observations. / Modeling natural language is among fundamental challenges of artificial intelligence and the design of interactive machines, with applications spanning across various domains, such as dialogue systems, text generation and machine translation. We propose a discriminatively trained log-linear model to learn the distribution of words following a given context. Due to data sparsity, it is necessary to appropriately regularize the model using a penalty term. We design a penalty term that properly encodes the structure of the feature space to avoid overfitting and improve generalization while appropriately capturing long range dependencies. Some nice properties of specific structured penalties can be used to reduce the number of parameters required to encode the model. The outcome is an efficient model that suitably captures long dependencies in language without a significant increase in time or space requirements. In a log-linear model, both training and testing become increasingly expensive with growing number of classes. The number of classes in a language model is the size of the vocabulary which is typically very large. A common trick is to cluster classes and apply the model in two-steps; the first step picks the most probable cluster and the second picks the most probable word from the chosen cluster. This idea can be generalized to a hierarchy of larger depth with multiple levels of clustering. However, the performance of the resulting hierarchical classifier depends on the suitability of the clustering to the problem. We study different strategies to build the hierarchy of categories from their observations.
25

Problèmes de reconstruction en Imagerie par Résonance Magnétique parallèle à l'aide de représentations en ondelettes

Chaari, Lotfi 05 November 2010 (has links) (PDF)
Pour réduire le temps d'acquisition ou bien améliorer la résolution spatio-temporelle dans certaines application en IRM, de puissantes techniques parallèles utilisant plusieurs antennes réceptrices sont apparues depuis les années 90. Dans ce contexte, les images d'IRM doivent être reconstruites à partir des données sous-échantillonnées acquises dans le "k-space". Plusieurs approches de reconstruction ont donc été proposées dont la méthode SENSitivity Encoding (SENSE). Cependant, les images reconstruites sont souvent entâchées par des artéfacts dus au bruit affectant les données observées, ou bien à des erreurs d'estimation des profils de sensibilité des antennes. Dans ce travail, nous présentons de nouvelles méthodes de reconstruction basées sur l'algorithme SENSE, qui introduisent une régularisation dans le domaine transformé en ondelettes afin de promouvoir la parcimonie de la solution. Sous des conditions expérimentales dégradées, ces méthodes donnent une bonne qualité de reconstruction contrairement à la méthode SENSE et aux autres techniques de régularisation classique (e.g. Tikhonov). Les méthodes proposées reposent sur des algorithmes parallèles d'optimisation permettant de traiter des critères convexes, mais non nécessairement différentiables contenant des a priori parcimonieux. Contrairement à la plupart des méthodes de reconstruction qui opèrent coupe par coupe, l'une des méthodes proposées permet une reconstruction 4D (3D + temps) en exploitant les corrélations spatiales et temporelles. Le problème d'estimation d'hyperparamètres sous-jacent au processus de régularisation a aussi été traité dans un cadre bayésien en utilisant des techniques MCMC. Une validation sur des données réelles anatomiques et fonctionnelles montre que les méthodes proposées réduisent les artéfacts de reconstruction et améliorent la sensibilité/spécificité statistique en IRM fonctionnelle.
26

Détection active de pannes dans les systèmes dynamiques en boucle fermée / Active fault detection in closed-loop dynamic systems

Esna Ashari Esfahani, Alireza 08 June 2010 (has links)
L'objectif de cette thèse est de développer une nouvelle méthodologie pour la détection active de défaillances, basée sur approche multimodèle et robuste des fautes. Ce travail prolonge des recherches effectuées dans le projet Metalau de l'Inria. L'apport essentiel de cette thèse est la prise en compte de modèles évoluant en boucle fermée. On utilise une approche multi-modèle pour modéliser le modèle en fonctionnement normal et le modèle défaillant. Les avantages potentiels de l'utilisation d'un feedback dynamique linéaire et ses propriétés de robustesse sont analysés dans la construction de signaux de détection auxiliaires. On compare les résultats obtenus avec ceux du cas boucle ouverte. La formulation du problème de détection active dans le cas d'un modèle en boucle fermée est nouvelle et repose sur la prise en considération de la norme du signal de détection auxiliaire comme critère d'optimisation. On considère aussi des fonctions coût plus générales, telles celles qui sont utilisées pour mesurer la performance de feedbacks dans des problèmes de la théorie de la commande linéaire robuste. La solution complète repose sur la résolution de plusieurs problèmes d'optimisation non standards / The aim is to develop a novel theory of robust active failure detection based on multi-model formulation of faults. The original method was already proposed by the Metalau group of INRIA. We have continued to work on the extension of this approach to more general cases. The focus is on the effects of feedback on the previous approach. The multi-model approach is still used to model the normal and the failed systems; however the possible advantages of using linear dynamic feedback in the construction of the auxiliary signal for robust fault detection is considered and the results are compared to the previously developed open-loop setup. An original formulation of the active fault detection problem using feedback is developed. The norm of the auxiliary signal is considered as a possible cost criterion. Also, we have considered a more general cost function that has already been used for measuring the performance of feedback configurations in Linear Control Theory. We have given a complete solution to this problem. In order to find a complete solution, several mathematical problems are solved
27

Méthodes proximales pour la résolution de problèmes inverses : application à la tomographie par émission de positrons / Proximal methods for the resolution of inverse problems : application to positron emission tomography

Pustelnik, Nelly 13 December 2010 (has links)
L'objectif de cette thèse est de proposer des méthodes fiables, efficaces et rapides pour minimiser des critères convexes apparaissant dans la résolution de problèmes inverses en imagerie. Ainsi, nous nous intéresserons à des problèmes de restauration/reconstruction lorsque les données sont dégradées par un opérateur linéaire et un bruit qui peut être non additif. La fiabilité de la méthode sera assurée par l'utilisation d'algorithmes proximaux dont la convergence est garantie lorsqu'il s'agit de minimiser des critères convexes. La quête d'efficacité impliquera le choix d'un critère adapté aux caractéristiques du bruit, à l'opérateur linéaire et au type d'image à reconstruire. En particulier, nous utiliserons des termes de régularisation basés sur la variation totale et/ou favorisant la parcimonie des coefficients du signal recherché dans une trame. L'utilisation de trames nous amènera à considérer deux approches : une formulation du critère à l'analyse et une formulation du critère à la synthèse. De plus, nous étendrons les algorithmes proximaux et leurs preuves de convergence aux cas de problèmes inverses multicomposantes. La recherche de la rapidité de traitement se traduira par l'utilisation d'algorithmes proximaux parallélisables. Les résultats théoriques obtenus seront illustrés sur différents types de problèmes inverses de grandes tailles comme la restauration d'images mais aussi la stéréoscopie, l'imagerie multispectrale, la décomposition en composantes de texture et de géométrie. Une application attirera plus particulièrement notre attention ; il s'agit de la reconstruction de l'activité dynamique en Tomographie par Emission de Positrons (TEP) qui constitue un problème inverse difficile mettant en jeu un opérateur de projection et un bruit de Poisson dégradant fortement les données observées. Pour optimiser la qualité de reconstruction, nous exploiterons les caractéristiques spatio-temporelles de l'activité dans les tissus / The objective of this work is to propose reliable, efficient and fast methods for minimizing convex criteria, that are found in inverse problems for imagery. We focus on restoration/reconstruction problems when data is degraded with both a linear operator and noise, where the latter is not assumed to be necessarily additive.The methods reliability is ensured through the use of proximal algorithms, the convergence of which is guaranteed when a convex criterion is considered. Efficiency is sought through the choice of criteria adapted to the noise characteristics, the linear operators and the image specificities. Of particular interest are regularization terms based on total variation and/or sparsity of signal frame coefficients. As a consequence of the use of frames, two approaches are investigated, depending on whether the analysis or the synthesis formulation is chosen. Fast processing requirements lead us to consider proximal algorithms with a parallel structure. Theoretical results are illustrated on several large size inverse problems arising in image restoration, stereoscopy, multi-spectral imagery and decomposition into texture and geometry components. We focus on a particular application, namely Positron Emission Tomography (PET), which is particularly difficult because of the presence of a projection operator combined with Poisson noise, leading to highly corrupted data. To optimize the quality of the reconstruction, we make use of the spatio-temporal characteristics of brain tissue activity
28

Supervised metric learning with generalization guarantees / Apprentissage supervisé de métriques avec garanties en généralisation

Bellet, Aurélien 11 December 2012 (has links)
Ces dernières années, l'importance cruciale des métriques en apprentissage automatique a mené à un intérêt grandissant pour l'optimisation de distances et de similarités en utilisant l'information contenue dans des données d'apprentissage pour les rendre adaptées au problème traité. Ce domaine de recherche est souvent appelé apprentissage de métriques. En général, les méthodes existantes optimisent les paramètres d'une métrique devant respecter des contraintes locales sur les données d'apprentissage. Les métriques ainsi apprises sont généralement utilisées dans des algorithmes de plus proches voisins ou de clustering.Concernant les données numériques, beaucoup de travaux ont porté sur l'apprentissage de distance de Mahalanobis, paramétrisée par une matrice positive semi-définie. Les méthodes récentes sont capables de traiter des jeux de données de grande taille.Moins de travaux ont été dédiés à l'apprentissage de métriques pour les données structurées (comme les chaînes ou les arbres), car cela implique souvent des procédures plus complexes. La plupart des travaux portent sur l'optimisation d'une notion de distance d'édition, qui mesure (en termes de nombre d'opérations) le coût de transformer un objet en un autre.Au regard de l'état de l'art, nous avons identifié deux limites importantes des approches actuelles. Premièrement, elles permettent d'améliorer la performance d'algorithmes locaux comme les k plus proches voisins, mais l'apprentissage de métriques pour des algorithmes globaux (comme les classifieurs linéaires) n'a pour l'instant pas été beaucoup étudié. Le deuxième point, sans doute le plus important, est que la question de la capacité de généralisation des méthodes d'apprentissage de métriques a été largement ignorée.Dans cette thèse, nous proposons des contributions théoriques et algorithmiques qui répondent à ces limites. Notre première contribution est la construction d'un nouveau noyau construit à partir de probabilités d'édition apprises. A l'inverse d'autres noyaux entre chaînes, sa validité est garantie et il ne comporte aucun paramètre. Notre deuxième contribution est une nouvelle approche d'apprentissage de similarités d'édition pour les chaînes et les arbres inspirée par la théorie des (epsilon,gamma,tau)-bonnes fonctions de similarité et formulée comme un problème d'optimisation convexe. En utilisant la notion de stabilité uniforme, nous établissons des garanties théoriques pour la similarité apprise qui donne une borne sur l'erreur en généralisation d'un classifieur linéaire construit à partir de cette similarité. Dans notre troisième contribution, nous étendons ces principes à l'apprentissage de métriques pour les données numériques en proposant une méthode d'apprentissage de similarité bilinéaire qui optimise efficacement l'(epsilon,gamma,tau)-goodness. La similarité est apprise sous contraintes globales, plus appropriées à la classification linéaire. Nous dérivons des garanties théoriques pour notre approche, qui donnent de meilleurs bornes en généralisation pour le classifieur que dans le cas des données structurées. Notre dernière contribution est un cadre théorique permettant d'établir des bornes en généralisation pour de nombreuses méthodes existantes d'apprentissage de métriques. Ce cadre est basé sur la notion de robustesse algorithmique et permet la dérivation de bornes pour des fonctions de perte et des régulariseurs variés / In recent years, the crucial importance of metrics in machine learningalgorithms has led to an increasing interest in optimizing distanceand similarity functions using knowledge from training data to make them suitable for the problem at hand.This area of research is known as metric learning. Existing methods typically aim at optimizing the parameters of a given metric with respect to some local constraints over the training sample. The learned metrics are generally used in nearest-neighbor and clustering algorithms.When data consist of feature vectors, a large body of work has focused on learning a Mahalanobis distance, which is parameterized by a positive semi-definite matrix. Recent methods offer good scalability to large datasets.Less work has been devoted to metric learning from structured objects (such as strings or trees), because it often involves complex procedures. Most of the work has focused on optimizing a notion of edit distance, which measures (in terms of number of operations) the cost of turning an object into another.We identify two important limitations of current supervised metric learning approaches. First, they allow to improve the performance of local algorithms such as k-nearest neighbors, but metric learning for global algorithms (such as linear classifiers) has not really been studied so far. Second, and perhaps more importantly, the question of the generalization ability of metric learning methods has been largely ignored.In this thesis, we propose theoretical and algorithmic contributions that address these limitations. Our first contribution is the derivation of a new kernel function built from learned edit probabilities. Unlike other string kernels, it is guaranteed to be valid and parameter-free. Our second contribution is a novel framework for learning string and tree edit similarities inspired by the recent theory of (epsilon,gamma,tau)-good similarity functions and formulated as a convex optimization problem. Using uniform stability arguments, we establish theoretical guarantees for the learned similarity that give a bound on the generalization error of a linear classifier built from that similarity. In our third contribution, we extend the same ideas to metric learning from feature vectors by proposing a bilinear similarity learning method that efficiently optimizes the (epsilon,gamma,tau)-goodness. The similarity is learned based on global constraints that are more appropriate to linear classification. Generalization guarantees are derived for our approach, highlighting that our method minimizes a tighter bound on the generalization error of the classifier. Our last contribution is a framework for establishing generalization bounds for a large class of existing metric learning algorithms. It is based on a simple adaptation of the notion of algorithmic robustness and allows the derivation of bounds for various loss functions and regularizers.
29

Graph-based variational optimization and applications in computer vision / Optimisation variationnelle discrète et applications en vision par ordinateur

Couprie, Camille 10 October 2011 (has links)
De nombreuses applications en vision par ordinateur comme le filtrage, la segmentation d'images, et la stéréovision peuvent être formulées comme des problèmes d'optimisation. Récemment les méthodes discrètes, convexes, globalement optimales ont reçu beaucoup d'attention. La méthode des "graph cuts'", très utilisée en vision par ordinateur est basée sur la résolution d'un problème de flot maximum discret, mais les solutions souffrent d'un effet de blocs,notamment en segmentation d'images. Une nouvelle formulation basée sur le problème continu est introduite dans le premier chapitre et permet d'éviter cet effet. La méthode de point interieur employée permet d'optimiser le problème plus rapidement que les méthodes existantes, et la convergence est garantie. Dans le second chapitre, la formulation proposée est efficacement étendue à la restauration d'image. Grâce à une approche du à la contrainte et à un algorithme proximal parallèle, la méthode permet de restaurer (débruiter, déflouter, fusionner) des images rapidement et préserve un meilleur contraste qu'avec la méthode de variation totale classique. Le chapitre suivant met en évidence l'existence de liens entre les méthodes de segmentation "graph-cuts'", le "randomwalker'', et les plus courts chemins avec un algorithme de segmentation par ligne de partage des eaux (LPE). Ces liens ont inspiré un nouvel algorithme de segmentation multi-labels rapide produisant une ligne de partage des eaux unique, moins sensible aux fuites que la LPE classique. Nous avons nommé cet algorithme "LPE puissance''. L'expression de la LPE sous forme d'un problème d'optimisation a ouvert la voie à de nombreuses applications possibles au delà de la segmentation d'images, par exemple dans le dernier chapitre en filtrage pour l'optimisation d'un problème non convexe, en stéréovision, et en reconstruction rapide de surfaces lisses délimitant des objets à partir de nuages de points bruités / Many computer vision applications such as image filtering, segmentation and stereovision can be formulated as optimization problems. Recently discrete, convex, globally optimal methods have received a lot of attention. Many graph-based methods suffer from metrication artefacts, segmented contours are blocky in areas where contour information is lacking. In the first part of this work, we develop a discrete yet isotropic energy minimization formulation for the continuous maximum flow problem that prevents metrication errors. This new convex formulation leads us to a provably globally optimal solution. The employed interior point method can optimize the problem faster than the existing continuous methods. The energy formulation is then adapted and extended to multi-label problems, and shows improvements over existing methods. Fast parallel proximal optimization tools have been tested and adapted for the optimization of this problem. In the second part of this work, we introduce a framework that generalizes several state-of-the-art graph-based segmentation algorithms, namely graph cuts, random walker, shortest paths, and watershed. This generalization allowed us to exhibit a new case, for which we developed a globally optimal optimization method, named "Power watershed''. Our proposed power watershed algorithm computes a unique global solution to multi labeling problems, and is very fast. We further generalize and extend the framework to applications beyond image segmentation, for example image filtering optimizing an L0 norm energy, stereovision and fast and smooth surface reconstruction from a noisy cloud of 3D points
30

Compétition sur la visibilité et la popularité dans les réseaux sociaux en ligne / Competition over popularity and visibility on online social networks

Reiffers-Masson, Alexandre 12 January 2016 (has links)
Cette thèse utilise la théorie des jeux pour comprendre le comportement des usagers dans les réseaux sociaux. Trois problématiques y sont abordées: "Comment maximiser la popularité des contenus postés dans les réseaux sociaux?";" Comment modéliser la répartition des messages par sujets?";"Comment minimiser la propagation d’une rumeur et maximiser la diversité des contenus postés?". Après un état de l’art concernant ces questions développé dans le chapitre 1, ce travail traite, dans le chapitre 2, de la manière d’aborder l’environnement compétitif pour accroître la visibilité. Dans le chapitre 3, c’est le comportement des usagers qui est modélisé, en terme de nombre de messages postés, en utilisant la théorie des approximations stochastiques. Dans le chapitre 4, c’est une compétition pour être populaire qui est étudiée. Le chapitre 5 propose de formuler deux problèmes d’optimisation convexes dans le contexte des réseaux sociaux en ligne. Finalement, le chapitre 6 conclue ce manuscrit. / This Ph.D. is dedicated to the application of the game theory for the understanding of users behaviour in Online Social Networks. The three main questions of this Ph.D. are: " How to maximize contents popularity ? "; " How to model the distribution of messages across sources and topics in OSNs ? "; " How to minimize gossip propagation and how to maximize contents diversity? ". After a survey concerning the research made about the previous problematics in chapter 1, we propose to study a competition over visibility in chapter 2. In chapter 3, we model and provide insight concerning the posting behaviour of publishers in OSNs by using the stochastic approximation framework. In chapter 4, it is a popularity competition which is described by using a differential game formulation. The chapter 5 is dedicated to the formulation of two convex optimization problems in the context of Online Social Networks. Finally conclusions and perspectives are given in chapter 6.

Page generated in 0.4582 seconds