Type systems are used to automatically check security properties of large programs. This project will extend typing methodology to a large panel of properties currently unreachable by state-of-the-art tech-niques, enabling in particular the analysis of quantitative properties of programs. We will develop a way to keep track of the extensional information inside types in order to perform the whole static analysis at the level of types. For this purpose, we will combine two (re)emerging type systems, namely graded types and intersection type systems, with the well established techniques from the field of abstract interpretation such as widening. Graded type systems formally embed a first order structure within types, while intersection types will help to circumvent the unconditional non-compositionality of fine grained resource analyses. This is how we plan to tackle the long running problem of applying abstract interpretation result in functional programming.

Project Semi-Amor aims at improving state-of-the-art for challenging Natural Language Processing (NLP) tasks where output are highly-contrained such as controlled generation, syntactic and semantic parsing and joint entity-relation extraction. In particular, we will be interested in application of Lagrangian Relaxation to tackle intractable loss functions and decoding problems. We propose to replace commonly used iterative optimization algorithms for this setting by semi-amortized inference neural networks in order to improve training and decoding time. Long-term impacts include all settings where bigger networks cannot be the only answer, for instance semantic parsing for human-machine interfaces where ill-formed output are blocking, or models for low-resource languages lacking large pretrained data.

Directed acyclic graphs are important due to their close relation to partial orders, making them very general structures. Families of DAGs have long been appearing in computer science when compacting tree-structures sharing subtrees. First properties were found in the 1970s, in particular on the enumeration of DAGs. Our expertise lies in analysis of algorithms using Analytic Combinatorics in order to structurally describe combinatorial objects, to find new specifications and to exhibit universal properties of data structures. In this project we aim at studying tree structures and their associated DAGs induced by common substructures. We plan to extend the general methodology to these DAGs, following three main directions: (i) Quantitative analysis of the compaction of tries. (ii) Typical structure of large DAGs whose decompaction relies on large binary trees. (iii) Enumeration, random sampling and satisfiability of decision diagrams (ROBDDs, ZDDs, QDDs...) and Boolean circuits.

Social media and other forms of online communication have triggered the emergence of new forms of written texts and increased the volume of multilingual user-generated content (UGC). Making these unlimited streams of non-canonical texts automatically understandable and actionable opens new scientific and social challenges. This is the main focus of the ParSiTi project. One of the most striking influences of social media on society is how they evolved to impact our perception of events. For instance, during the various Spring Revolutions, Facebook users were in the front line of the information war; more recently, during the November 2015 Paris Attacks, Twitter was used to gather information about the victims and to offer shelter to those stranded by these attacks. These events generated a steady flow of global textual interactions, crucially highlighting the lack of accurate tools to automatically process and understand these information streams. UGC, covering among others social networks, blogs and forums, differ from newspaper written languages, on which natural language processing (NLP) tools are most often trained and tested, in three important dimensions: (i) user-generated content is extremely diverse, rife with abbreviations, spelling mistakes, typographical and grammatical errors. It often lacks punctuation and mixes languages. In some cases, the spelling is akin to rough phonetisation. Added to a much richer variability, these phenomena hinder the performance of NLP pipelines. (ii) Overcoming English, the Web has now turned into a truly multilingual space. (iii) A strong contextualization as these non-canonical productions are tightly linked to contextual sources (videos, images, memes, game sessions, external URLs) and the inner nature of most social media encourages shorter sentences and threaded messages, which in turn favor the use of elliptical constructions. This leads to strong difficulties in rising ambiguities, for example in case of underspecified anaphoras, which complicate NLP tasks such as parsing or Machine Translation. The ParSiTi project aims at taking advantage of recent advances in statistical NLP and Deep Learning to address these challenges and improve access to multilingual user-generated content. We plan to design and release a fully integrated NLP software able to automatically process non-canonical texts in their context. To demonstrate the success of our approach, an accurate Machine Translation system, able to translate, in context, user-generated content between French, Arabic and English, will be developed. Such a system should prove valuable to researchers in linguistics, social sciences and for innovative private sector companies. Moreover, our software and data sets will be made freely available, so that they can be used for further work beyond the scope of the project, e.g. for information extraction or opinion mining. Developing this software is higly challenging and requires to push existing techniques to their limits, sometimes at the price of questioning assumptions that have long been taken for granted. The ParSiTi project will address three scientific challenges of increasing risk and complexity: (i) normalizing UGC and adapting parsing, along with translation models, to their peculiarities (ii) developing joint models to combine different sources of information without error propagation (iii) design context-aware models to cope with discussion anchored in a specific linguistic (e.g. comment in a threaded discussion) and extract-linguistic (e.g. images, URL, ...) contexts. ParSiTi will gather three partners: LIMSI for their expertise in Machine Translation and Deep Learning, LIPN for their expertise in joint models and parsing, and ALPAGE for their expertise in morpho-syntactic processing of social media, (deep) parsing, and out-of-domain adaptation.

Probabilities are essential in Computer Science. Many algorithms use probabilistic choices for efficiency or convenience. Recently, probabilistic programming, and more specifically, functional probabilistic programming, has shown crucial in various works in Bayesian inference and Machine Learning. Such languages are used to represent formally statistical models and for developing probabilistic data analysis. So it is becoming more and more essential to develop formal methods for probabilistic computing (semantics, type systems, logical frameworks for program verification, abstract machines etc.) to systematize the analysis and certification of functional probabilistic programs. This research activity is growing very fast at an international level, especially in the programming languages community. Our goal is to develop such formal methods. We focus our approach on the notions of linearity and computational resources which are at the core of Linear Logic (LL). We are convinced that the many connections between Proof Theory, Linear Algebra and the Theory of Programming Languages which arise within LL will play a key role in the development of formal methods for probabilistic programming. This conviction is supported by our most recent results (denotational models for probabilistic programs and their differentials, metrics for program reasoning, typing systems and realizability techniques for almost sure termination, higher-order model checking, algebraic and probabilistic rewriting systems, probabilistic models based on game semantics and geometry of interaction, etc.), thus establishing that our proposal is both topical and timely. These preliminary results have been achieved by various groups among us, working independently and scattered in different laboratories. One major objective of this project is to join our forces and complementing expertises, organizing our efforts in a strong research program, structured along the following five work-packages. Probabilities, Differentials and Machine Learning (1), this is the main axis of our proposal defining our long-term objective: give a clear semantical status to the linear methods used in Bayesian inference using LL and to the differential methods used in Machine Learning adapting the basic ideas of differential LL. (2) Denotational and (3) Operational Semantics: these are the central concepts of the project, where our research is already very active and recognized. Our aim is to push further these investigations throughout the next work-packages. (4) From Qualitative to Quantitative Observations: we move from the standard approaches to programs equivalence, based on denotational and game models, bisimulations, etc, to more sophisticated instruments based on norms and distances, more relevant in probabilistic programming. (5) Towards Effective Tools for Quantitative Observations: we extract from the theory developed so far computable devices (type systems, model-checking, etc.) allowing to perform (with suitable restrictions) program quantitative analysis. This 4 year project gathers 4 partners, IRIF -- coordinator site and LIPN (Paris), I2M (Marseille) and Inria FOCUS (Sophia and Bologna, Italy). It will hire one doctoral student and two post-doc researchers. The coordinator will be Thomas Ehrhard and the other PI's are Giulio Manzonetto, Lionel Vaux and Martin Avanzini.