Luca Mencarelli will defend his PhD thesis entitled “The Multiplicative Weights Algorithm for Mixed Integer NonLinear Programming: Theory, Applications and Limits” on Monday December 4th 2017 at 2:00 PM in the Gilles Khan room (Bâtiment Alan Turing).
Abstract: In this thesis we introduce a new heuristic algorithm for Mixed Integer NonLinear Programming (MINLP) based on the Multiple Weights Update (MWU) framework and involving a new class of Mathematical Programming (MP) reformulations, namely the pointwise reformulations. The MWU algorithm is a “meta-algorithm” with broad application in Mathematical Optimization, Machine Learning, and Game Theory. MINLP is a very interesting topic in Mathematical Optimization both for a theoretical and computational viewpoint. Moreover, formulations and reformulations constitute a key tool in MP: pointwise reformulation are a family of MINLPs, where several “complicated” terms are substituted with parameters in order to obtain easier problems.
The thesis is divided into three main parts. In the first part we introduce the more important ingredients for the heuristic algorithm, in the second one we theoretically describe the new algorithm and in the last one we practically apply the new methodology to two hard real-world problems, namely the Mean-Variance Portfolio Selection (MVPS) and the Multiple NonLinear Knapsack Problem (MNLKP). The first problem arises in financial portfolio context, where investors want to identify the portfolio with the highest return and the minimum volatility or risk; while the second problem occurs, for example, in resource allocation, where a set of resources with limited capacities must be divided among different categories.
Computational experiments indicate the new methodology behaves rather better that the benchmarks for the MVPS problems, while this is not the case for the MNLKP. Therefore, we propose a different constructive heuristic based on three different phases: a procedure based on the discretisation of the solution space and two procedures for the feasibility recovering of the solution produced by the surrogate relaxation. The constructive heuristic outperforms the benchmarks both with respect of the quality of the solution found and of the total elapsed time.
Panagiotis Korvesis will defend hid PhD thesis entitled «Machine Learning for Predictive Maintenance in Aviation», on Tuesday, November 21st, in the Grace Hopper room of the Alan Turing building.
Abstract: The increase of available data in almost every domain raises the necessity of employing algorithms for automated data analysis. This necessity is highlighted in predictive maintenance, where the ultimate objective is to predict failures of hardware components by continuously observing their status, in order to plan maintenance actions well in advance. These observations are generated by monitoring systems usually in the form of time series and event logs and cover the lifespan of the corresponding components. Analyzing this history of observations in order to develop predictive models is the main challenge of data driven predictive maintenance.
Towards this direction, Machine Learning has become ubiquitous since it provides the means of extracting knowledge from a variety of data sources with the minimum human intervention. The goal of this dissertation is to study and address challenging problems in aviation related to predicting failures of components on-board. The amount of data related to the operation of aircraft is enormous and therefore, scalability is a key requirement in every proposed approach.
This dissertation is divided in three main parts that correspond to the different data sources that we encountered during our work. In the first part, we targeted the problem of predicting system failures, given the history of Post Flight Reports. We proposed a regression-based approach preceded by a meticulous formulation and data pre-processing/transformation. Our method approximates the risk of failure with a scalable solution, deployed in a cluster environment both in training and testing. To our knowledge, there is no available method for tackling this problem until the time this thesis was written.
The second part presents our approach for analyzing logbook data, which consist of text describing aircraft issues and the corresponding maintenance actions and it is written by maintenance engineers. The logbook contains information that is not reflected in the post-flight reports and it is very essential in several applications, including failure prediction. However, since the logbook contains text written in natural language, it contains a lot of noise that needs to be removed in order to extract useful information. We tackled this problem by proposing an approach based on vector representations of words (or word embeddings). Our approach exploits semantic similarities of words, learned by neural networks that generated the vector representations, in order to identify and correct spelling mistakes and abbreviations. Finally, important keywords are extracted using Part of Speech Tagging.
In the third part, we tackled the problem of assessing the health of components on-board using sensor measurements. In the cases under consideration, the condition of the component is assessed by the magnitude of the sensorâs fluctuation and a monotonically increasing trend. In our approach, we formulated a time series decomposition problem in order to separate the fluctuation from the trend by solving an optimisation problem. To quantify the condition of the component, we compute a risk function which measures the sensorâs deviation from its normal behavior, which is learned using Gaussian Mixture Models.
Huixing Meng soutiendra sa thèse intitulée Modélisation des patterns d'analyse des performances des systèmes de production et de sûreté de fonctionnement dans l'industrie des procédés, le vendredi 17 novembre 2017 à 9h30. La soutenance aura lieu dans l'amphithéâtre Sophie Germain, au rez-de-chaussée du bâtiment Alan Turing.
Maria Rossi will defend her phd thesis on Friday, November 17 at 15:00, in the Gilles Kahn room of the Alan Turing building.
Modern science of graphs has emerged the last few years as a field of interest and has been bringing significant advances to our knowledge about networks. Until recently the existing data mining algorithms were destined for structured/relational data while many datasets exist that require graph representation such as social networks, networks generated by textual data, 3D protein structures and chemical compounds. It has become therefore of crucial importance to be able to extract in an efficient and effective way meaningful infor- mation from that kind of data and towards this end graph mining and analysis methods have been proven essential. The goal of this thesis is to study problems in the area of graph mining focusing espe- cially on designing new algorithms and tools related to information spreading and specifi- cally on how to locate influential entities in real-world social networks. This task is crucial in many applications such as information diffusion, epidemic control and viral marketing.
In the first part of the thesis, we have studied spreading processes in social networks focusing on finding topological characteristics that rank entities in the network based on their influential capabilities. We have specifically focused on the K-truss decomposition which is an extension of the k-core decomposition of the graph. Both methods partition a graph into subgraphs whose nodes and/or edges have some common characteristics. For the case of the K-truss, the edges belonging to such subgraph are contained to at least K-2 triangles. After extensive experimental analysis in real-world networks, we showed that the nodes that belong to the maximal K-truss subgraph show a better spreading behavior when compared to baseline criteria such as degree and k-core centralities. Such spreaders have the ability to influence a greater part of the network during the first steps of a spreading process but also the total fraction of the influenced nodes at the end of the epidemic is greater. We have also observed that node members of such dense subgraphs are those achieving the optimal spreading in the network.
In the second part of the thesis, we focused on identifying a group of nodes that by acting all together maximize the expected number of influenced nodes at the end of the spreading process, formally called Influence Maximization. The Influence Maximization problem is actually NP-hard though there exist approximation guarantees for efficient algorithms that can solve the problem while obtaining a solution within the 63% of op- timal classes of models. As those guarantees propose a greedy approximation which is computationally expensive especially for large graphs, we proposed the MATI algorithm which succeeds in locating the group of users that maximize the influence while also be- ing scalable. The algorithm takes advantage of the possible paths created in each node’s neighborhood and precalculates each node’s potential influence and achieves to produce competitive results in quality compared to those of baseline algorithms.
In the last part of the thesis, we study the privacy point of view of sharing such metrics that are good influential indicators in a social network. We have focused on designing an algorithm that addresses the problem of computing through an efficient, correct, se- cure, and privacy-preserving algorithm the k-core metric which measures the influence of each node of the network. We have specifically adopted a decentralization approach where the social network is considered as a Peer-to-peer (P2P) system. The algorithm is built based on the constraint that it should not be possible for a node to reconstruct partially or entirely the graph using the information they obtain during its execution. While a distributed algorithm that computes once and for all the nodes’ coreness is already pro- posed, networks that evolve over time are not taken into account. Our main contribution is an incremental algorithm that efficiently solves the core maintenance problem in P2P while limiting the number of messages exchanged and computations. Through extensive experiments we provide a security and privacy analysis of the solution regarding network de-anonymization. We showed how it relates to previously defined attack models and discuss countermeasures.
In this talk, we review the notion of Differential Privacy, its implications in terms of Bayesian Adversary, and we discuss typical implementations from the point of view of their optimality with respect to utility. Then, we consider an extension of differential privacy to general metric domains, and the consequences for the optimality results. Finally, we show an instantiation to the case of location privacy, leading to the notion of geo-indistinguishability.
The DaScIS (Data Science in the insurance Sector) Chair organizes the “Data Science in Action” event on November 16th in the campus of Ecole Polytechnique (amphi Gay Lussac ).
This half-day consists
- of presentations by senior managers and data scientists of the AXA Group, and important speakers from academia. These presentations provide insight into business issues and case studies of machine learning techniques or applying big data in the field of insurance.
- a social event - reception at 17:30
If you are going to attend please register your name and email - to this form. We need this for logistic reasons.
The full schedule of event follows below. I would like to stress among others the key note of Professor Jie Tang from Tsinghua University, Beijing with a very interesting talk on open academic data.
- 14:00 J. Biot, President Ecole Polytechnique
- 14:15 M. Vazigiannis, Chair Holder - "Presentation of the Chair Activities"
- 14:30 Gaelle Olivier - CEO of AXA Global P&C – “Strategic vision of Insurance and Data”
- 15:00 Richard Benjamins - Head of the AXA data innovation lab - "Role of AXA in Global Data community"
- 15:30 Coffee break
- 16:00 S. Guinet (Founding CEO of Kamet (AXA Strategic Ventures fund) – “Presentation of portfolio projects"
- 16:30 Jie Tang - Professor, Tsinghua University - "AMiner: toward understanding big science data"
- 17:00 Wrap up - Discussion - Marcin Detyniecki - AXA
- 17:30 Cocktail "Salle des Cadres"
Henry de Lumley, membre correspondant de l’Académie des Sciences et de l’Académie des Inscriptions et Belles Lettres, préhistorien et géologue du Quaternaire, est Directeur de l’Institut de Paléontologie Humaine, Fondation Albert Ier Prince de Monaco, Professeur émérite et ex Directeur du Muséum National d’Histoire Naturelle, Paris.
L’objectif essentiel de ses recherches, sur le terrain et en laboratoire, est consacré à l’étude de l’origine de l’Homme, de sa première présence dans les grandes régions du monde, de son évolution morphologique et culturelle, de son comportement et de son mode de vie, au sein de ses paléoenvironnements (Ethiopie, Mauritanie, Inde, Turquie, Chine, Corée du Sud).
Une approche toute particulière de ses recherches a pour but de suivre l’évolution des climats et de la biodiversité tout au long des temps quaternaires dans diverses régions du monde.
Ces études sont conduites avec une approche interdisciplinaire : stratigraphie, sédimentologie, magnéto-stratigraphie et géochronologie, palynologie, paléontologie, paléoanthropologie, paléthnologie, études technologique et typologique d’industries lithiques du Paléolithique inférieur et moyen.
Gautier Marti will defend his PhD thesis entitled Some contributions to the clustering of financial time series and applications to credit default swaps on Friday November 10th 2017 at 2pm in the Sophie Germain Auditorium of the Alan Turing building.
Summary: In this talk on clustering financial time series and its applications to credit default swaps, I will first try to give as much colors as possible on the credit default swap market, a relatively unknown market from the general public but famous for its role in the contagion of bank failures during the global financial crisis of 2007-2008 (cf. The Big Short, 2015 motion picture), while introducing the datasets that have been used in the empirical studies. Unlike the existing body of literature which mostly offers descriptive studies, we aim at building models and large information systems based on clusters which are seen as basic building blocks: These foundations must be stable. That is why the work undertaken and described in the following intends to ground further the clustering methodologies. For that purpose, we discuss their consistency and propose alternative measures of similarity that can be plugged in the clustering methodologies. We study empirically their impact on the clusters. Results of the empirical studies can be explored at <www.datagrapple.com>.
One postdoctoral researcher and one PhD student position are available at the LIX research laboratory of Ecole Polytechnique in France, in the area of:
«Exploring Relations in Structured Data with Functional Maps»
The goal of this project is to develop tools for the analysis and processing of complex geometric data, such as large-scale 3D model collections, by building on techniques from Computer Graphics, Geometry Processing and Machine Learning. The ultimate objective is to create a unified framework for representing and analyzing structured data to solve problems such as: shape comparison and matching, shape segmentation and labeling, shape deformation and recognition among others. The project will be funded, in part, by the ERC Starting Grant EXPROTEA.
The ideal candidates should have strong background in at least some of the following:
- Geometry Processing and 3D shape analysis
- Computer Graphics
- Computer Vision and Image Processing
- Knowledge of basic Differential Geometry
- Machine Learning
- Programming experience, especially in multimedia data analysis
For the postdoc position, candidates must have a PhD at the starting time of the post-doc, and should have publications in top venues in either Computer Graphics (e.g., SIGGRAPH, Eurographics, SGP) or a related field. The expected duration of the post-doc is 2 years.
For the PhD position, the candidate should have a Master's degree with preference given to those having strong research experience. The expected duration of the PhD is 3 years.
Venue and supervision
Successful candidates will be based at Ecole Polytechnique located in Palaiseau, Paris area, France. The project will be supervised by Maks Ovsjanikov (LIX, Ecole Polytechnique):
The expected salary is approximately 2400 € net for the post-doctoral position and approximately 1800 € net per month for the PhD position.
How to apply
To apply, please contact Maks Ovsjanikov (maks at lix.polytechnique.fr). In your email, please include your CV, a short cover letter and a publication list. In your cover letter, make sure to mention how your interests and experience relate to the topics in this announcement.
Reference letters are optional but may need to be provided upon request.
Prof. Ricard Gavaldà (Universitat Politècnica de Catalunya) is visiting us this week. He will give a talk on Thursday (November 9th), at 11:30, in room Henri Poincaré on Tensor decomposition for inferring latent variable models, and an application to healthcare analytics.
Abstract: We present a new tensor decomposition method for inferring the parameters of certain kinds of latent variable models. The method has a number of advantages over existing methods, including scalability, the fact that it is deterministic and not randomized, and the quality of the results. It is also particularly appropriate for clustering tasks. In this respect, we present an application to clustering patients on the basis of their sets of diagnostics, and obtain clustering on two datasets provided by the Catalan Service of Health that clinicians find meaningful and potentially useful. This is joint work with Matteo Ruffini and Esther Limón.
Jesse Read will defend his habilitation thesis on Wednesday November 8th at 14h00, in room Henri Poincaré in the Alan Turing Building.
Abstract: In multi-label classification, multiple target variables are modelled, and multiple values predicted for each instance, as opposed to the traditional learning problem where each instance is associated with a single target variable. The main challenge is detecting and dealing with dependencies among labels, and incorporating these into learning methods, which should be computationally tractable to large problems. This habilitation thesis elaborates on new approaches for tackling this challenge, and also extending the challenge to the context of data streams. In data streams instances arrive continuously in a theoretically-infinite stream. A particular focus of this work is the case where temporal dependence is involved. A number of methods and metrics are proposed to overcome numerous challenges encountered in these scenarios.
The next Comète seminar will take place next Thursday 2nd of November at 14h in Salle Grace Hopper (LIX - Alan Turing building, École Polytechnique). Laurent Fribourg, senior researcher (CNRS, LSV, ENS Paris Saclay), will talk about "Euler’s method applied to the control of switched systems". Also, Catuscia Palamidessi, director of research (INRIA Saclay, LIX, École Polytechnique), will talk about "Information Leakage Games". The abstracts of the talks are given below.
The next Comète seminar will take place next Thursday 26th of October at 14h in Salle Grace Hopper (LIX - Alan Turing building, École Polytechnique). Radu Mardare, Associate Professor at the Department of Computer Science, Aalborg University, Denmark, will talk about Quantitative Algebraic Reasoning.
Abstract: The talk is centered on the concept of Quantitative Algebra, a structure that we developed in order to provide canonical metric-based semantics for quantitative (probabilistic, stochastic, timed, weighted, priced, hybrid) systems. Quantitative algebras are universal algebras on metric spaces and are devised with an equational theory developed on top of indexed equations. An indexed equation is an equation of type s=_e t, where the index e is a positive number describing an upper bound of the distance between the terms s and t. This simple idea provides an entirely new way of thinking to algebras and Lawvere theories, and eventually induces a monad on the category of metric spaces. It also opens the discussion on the possibility of having a quantitative theory of effects for quantitative programming languages. This is a joint work with Gordon Plotkin and Prakash Panangaden that was presented to LICS 2016 and LICS 2017.
A second talk has been scheduled. Camilo Rocha, Associate Professor in the Department of Electronics and Computer Science at the Pontificia Universidad Javeriana, in Cali (Colombia), will talk about Guarded Terms for Rewriting Modulo SMT.
Abstract: Rewriting modulo SMT is a novel symbolic technique to model and analyze infinite-state systems that interact with a nondeterministic environment. It seamlessly combines rewriting modulo equational theories, SMT solving, and model checking. One of the main challenges of this technique is to cope with the symbolic state-space explosion problem. In this talk, guarded terms are presented as an approach to deal with this problem for rewriting modulo SMT. Guarded terms can encode many symbolic states into one by using SMT constraints as part of the term structure. This approach enables the reduction of the symbolic state space by limiting branching due to concurrent computation, and the complexity and size of constraints by distributing them in the term structure.
My research in COMETE involves the study of formal languages and semantic structures for concurrent systems and their relationship to logic. In this talk I shall introduce an algebraic structure, which we call SCS, for specifying the behaviour of spatially-distributed multi-agent systems. In the systems under consideration agents have spaces (local stores) where they may have epistemic information (e.g., facts, beliefs, opinions, "alternative" facts), processes and other spaces. Agents communicate by using processes that can move epistemic information and other processes across different spaces. SCS's can be seen as Scott's information systems with additional structure for specifying agents and their spaces. From a computational point of view scs can be used to specify partial information holding in a given agent's space (local information). From an epistemic point of view SCS can be used to specify information that a given agent considers true (beliefs). They can also specify the mobility of information/processes from one space to another. They also provide for process/information extrusion, a central concept in formalisms for mobile communication from concurrency theory. From an epistemic point of view extrusion corresponds to a notion we shall call utterance; a piece of information that an agent communicates to others but that may be inconsistent with the agent’s beliefs. Finally, scs can also also distributed information, understood as information that agents may conclude if they were to combine their local information. SCS have been used as semantics structures for modal logic and spatial timed reactive programming languages. In this presentation I shall talk about SCS with emphasis on recent formal developments such as the notion of distributed information and a prototype of an online multi-agent platform (DSpaceNet) where users (agents) interact much like in social networks. The distinct feature of DSpaceNet is that not only can the users post messages in their spaces but also mobile programs that can migrate across different spaces. Thus users can for example write and post their own watchdog processes that react to certain messages. This presentation is based on joint work with Michell Guzman, Salim Perchy, Sophia Knight, Prakash Panangaden, Camilo Rueda, Stefan Haar and Hector Delgado. The talk does not presuppose knowledge about concurrency theory.
LIX organizes an information afternoon for new members at LIX on Friday october 13 at 2pm in Grace Hopper room.
- Welcome from M. Regnier (Director of LIX)
- presentation of contacts PhD students at LIX (M. Albenque and A. Couvreur)
- presentation of the contact for postdocs (B. Smith)
- Miscellaneous information on LIX and the Turing Building (S. Jabinet)
- Information about professional training (J.-M. Notin)
- Presentation of the PhD student team and the PhD seminar (D. Nogeng)
The afternoon will be concluded by a coffee in the atrium of Turing building.
The next Comète seminar will take place next Wednesday 27th of September 2017 at 11h00 in Salle Grace Hopper (LIX - Alan Turing building, École Polytechnique). Julian Gutierrez, departmental lecturer in computer science at University of Oxford, will talk about "Nash Equilibrium and Bisimulation Invariance".
Abstract: Game theory provides a well-established framework for the analysis of concurrent and multi-agent systems. The basic idea is that concurrent processes (agents) can be understood as corresponding to players in a game; plays represent the possible computation runs of the system; and strategies define the behaviour of agents. Typically, strategies are modelled as functions from sequences of system states to player actions. Analysing a system in such a way involves computing the set of (Nash) equilibria in the game. However, we show that, with respect to the above model of strategies---the standard model in the literature---bisimilarity does not preserve the existence of Nash equilibria. Thus, two concurrent games which are behaviourally equivalent from a semantic perspective, and which from a logical perspective satisfy the same temporal formulae, nevertheless have fundamentally different properties from a game theoretic perspective. In this paper we explore the issues raised by this discovery, and investigate three models of strategies with respect to which the existence of Nash equilibria is preserved under bisimilarity. We also use some of these models of strategies to provide new semantic foundations for logics for strategic reasoning, and investigate restricted scenarios where bisimilarity can be shown to preserve the existence of Nash equilibria with respect to the conventional model of strategies in the literature.
Michell Guzmán will defend his Ph.D thesis entitled "On the Expressiveness of Spatial Constraint Systems" on Tuesday September 26th at 3 p.m. in the Sophie Germain room at the Alan Turing building.
Abstract: Epistemic, mobile and spatial behaviour are commonplace in today’s distributed systems. The intrinsic epistemic nature of these systems arises from the interactions of the elements of which they are comprised. Most people are familiar with digital systems where users share their beliefs, opinions and even intentional lies (hoaxes). Models of such systems must take into account the interactions with others as well as the distributed quality presented by them. Spatial and mobile behaviour are exhibited by applications and data moving across possibly nested spaces defined by, for example, friend circles, groups, and shared folders. Thus a solid understanding of the notion of space and spatial mobility as well as the flow of epistemic information is relevant in many models of today’s distributed systems. In order to analyze knowledge, space, and mobility in distributed systems, we expand upon the mathematically simple and elegant theory of constraint systems (cs), used to represent information and information change in concurrent systems. In the formal declara- tive model known as concurrent constraint programming, constraint systems provide the basic domains and operations for the semantic foundations of this model. Spatial constraint systems (scs’s) are al- gebraic structures that extend cs’s for reasoning about basic spatial and epistemic behaviour such as belief and extrusion. Both, spatial and epistemic assertions, can be viewed as specific modalities. Other modalities can be used for assertions about time, knowledge and even the analysis of groups among other concepts used in the specification and verification of concurrent systems. In this thesis we study the expressiveness of spatial constraint systems in the broader perspective of modal and epistemic behaviour. We shall show that spatial constraint systems are sufficiently robust to capture inverse modalities and to derive new results for modal logics. We shall show that we can use scs’s to express a fundamental epistemic behaviour such as knowledge. Finally we shall give an algebraic characterization of the notion of distributed information by means of constructors over scs’s.
Development of wireless networking technologies and Internet connectivity, improvement of computational capacities and availability of cheap, powerful connectable devices has empowered a substantial shift in the usage of the Internet, the emergence of new applications and possibilities and, tied to that, new challenges and needs on the Internet ecosystem. This presentation explores some of the leading trends in this transformation, and presents some contribution in some of the related research problems. In particular, the presentation focuses on the users content consumption by way of denser and broader Internet access networks, the wide-scale deployment of connected sensoring and monitoring “things”, that allow digitisation of building, cities, public infrastructures or facilities (energy grid, transport networks), and the optimization of core Internet infrastructures (datacenters) to support data collection and processing from the “Internet of things” and efficient content distribution to users.
The next Comète seminar will take place on Tuesday 12th of September 2017 at 14h00 in Salle Henri Poincaré (LIX - Alan Turing building, École Polytechnique). Rob van Glabbeek, chief research scientist at Data61, CSIRO and conjoint professor at the University of New South Wales, Sydney, Australia, will talk about "Congruence Formats in Structural Operational Semantics".
Abstract: This talk presents an overview on work on syntactic checks on structural operational language specifications that ensure that a certain semantic equivalence or preorder is a (pre)congruence. This is vital for compositional system verification. I will focus on strong and weak bisimilarity, and its divergence respecting variants. The languages I consider may have, besides constants and operators, also a recursion construct. For the latter I distinguish two kinds of congruence requirements: lean and full.
Amélie Héliou soutiendra sa thèse intitulée «Conformations moléculaire et théorie des jeux» le jeudi 31 août 2017 dans l'amphithéâtre Sophie Germain du bâtiment Alan Turing.
Résumé: Les protéines et acides ribonucléiques sont les principaux acteurs de nombreux processus cellulaires. Comprendre leurs fonctions, structures et interactions est un challenge important. Les méthodes expérimentales fournissent des informations sur la structure et la dynamique des molécules. Cependant les méthodes expérimentales sont limitées par le nombre de molécules qu’elles peuvent observer et les moyens qu’elles requièrent. Les méthodes de prédiction permettent d’obtenir des informations structurelles de façon quasi-automatique. Pour s’assurer de leur fiabilité, elles sont testées sur des données expérimentales. Nous présentons une procédure basée sur la cinétique inverse pour trouver une transition entre deux conformations d’un ARN tout en conservant sa structure secondaire. Nous obtenons des résultats comparables à l’état de l’art, ce qui montre que notre sélection des degrés de liberté est pertinente. De plus, nous utilisons des données partielles, ce qui permet d’utiliser différents types de résultats expérimentaux. Nous abordons aussi le problème du repliement protéique par une approche de théorie des jeux. Nous représentons une protéine par un jeu où les joueurs sont les acides aminés et les stratégies, les angles dièdres. La prédiction de structure peut alors être vue comme la recherche d’un équilibre dans un jeu multi-joueur où les fonctions d’utilité correspondent à la qualité du repliement. Nous montrons que l’algorithme de non-regret, appelé Hedge, garantit l’élimination des stratégies dominées et la convergence locale vers un équilibre de Nash. Puis, en limitant notre analyse aux jeux de potentiel, nous montrons qu’une classe plus large d’algorithmes, les algorithmes de régularisation, convergent vers un équilibre de Nash presque surement.
Anatolii Kostrygin soutiendra sa thèse intitulée «Analyse précise des algorithmes épidémiques» le mardi 29 août 2017 à 14h00 dans la salle Grace Hopper.
Résumé: Dans cette thèse nous étudions le problème de propagation de rumeur, c.-à-d. la dissémination collaborative, robuste et anonyme d’une information entre tous les agents d’un système distribué. Ce problème est à la base de nombreux algorithmes de communication sur des réseaux de capteurs sans-fil ou des réseaux mobiles ad-hoc. Il est aussi une brique centrale pour les nombreux algorithmes distribués avancés.
Nous proposons une méthode générale d'analyse des protocoles de la propagation de rumeur dans les graphes complets. Contrairement aux résultats précédents basés sur la structure précise des processus étudiés, notre analyse est basée sur la probabilité et la covariance des évènements correspondants au fait qu'un agent non-informé s'informe. Cela nous permet de reproduire les résultats basiques concernant les protocoles classiques de push, pull et push-pull ainsi qu'analyser les certaines variations telles que les échecs de communications ou les communications multiples réalisées par chaque agent. De plus, nous sommes capables d'analyser les certains modèles dynamiques quand le réseaux forme un graphe aléatoire échantillonné à nouveau à chaque étape. Notre méthode nous permet de déterminer l'espérance du temps de la diffusion à une constante additive près, ce qu'il est plus précis que la plupart des résultats précédents. Nous montrons que la déviation du temps de la diffusion par rapport à son espérance est inférieure d'une constante r avec la probabilité au moins 1 − exp(Ω(r)).
Nous discutons d'une hypothèse classique que les agents peuvent répondre à plusieurs appels entrants. La restriction à un seul appel entrant par agent provoque un ralentissement important de la diffusion pour un protocole de push-pull. Nous proposons une variation simple du protocole de push-pull qui rétablit une phase double logarithmique à nouveau et donc le nombre de messages passés redescend sur sa valeur optimal.