Actualités du LIPN

A Relational Model of Lambda Calculus, and Beyond (recent developments)

damiano — Monday 16 November 2009

For this first meeting of the new season of the GdT "Logique et Programmation" we will have Giulio Manzonetto (LIPN).

In this talk, we build a categorical model D of lambda calculus living in a category of sets and relations (relational semantics).

We will characterize the equational theory of this model, and show that it satisfies interesting algebraic properties that make it suitable for dealing with non-deterministic and parallel extensions of lambda calculus.

Unlike most traditional approaches, our way of interpreting non-determinism does not require any additional powerdomain construction: we show that our model provides a straightforward semantics of non-determinism (may convergence) by means of `unions' of interpretations as well as of `parallelism' (must convergence) by means of a binary, non-idempotent, operation available on the model, which is related to MIX rule of Linear Logic.

We describe the interpretation of this parallel and non-deterministic calculus in our model and show that this interpretation is sensible with respect to our operational semantics: a term converges if, and only if, it has a non-empty interpretation.

If time permits, we will sketch an interpretation of the resource lambda calculus in D.

Learning, Transferring and Adapting Distance Measures for Quantitative Structure-Activity Relationships

Webmaster — Tuesday 7 July 2009

Quantitative structure-activity relationships (QSARs) are regression models relating chemical structure to biological activity, allowing to make predictions for toxicologically or pharmacologically relevant endpoints, which constitute the target outcomes of trials or experiments. The task is often tackled by instance-based methods (like k-Nearest
Neighbors), which are all based on the notion of chemical (dis-)similarity. Clearly, it would be desirable to determine for a given QSAR dataset, a priori, a suitable distance measure. Our starting point is the observation by Raymond and Willett that the two big families of chemical distance measures, finger-print based and maximum common subgaph based measures, provide orthogonal information about chemical (dis-)similarity. We define a simple new distance measure weighting representatives of the two families, propose an optimization scheme for learning optimal weights for those measures combined, and investigate the transfer and adaptation of the weights from one problem to another, related problem with a similar or identical endpoint. Our experiments suggest that learning distance measures for QSAR (here formally defined as regression on molecular graphs) is feasible, and that the success of transferring and adapting such distance measures depends, amongst others, on training set size.

(CANCELED for strike reasons) Une heuristique efficace pour l'ordonnancement périodique de tâches avec contraintes de stockage

jcdubacq — Tuesday 24 March 2009

The "séminaire OCAD" receives Karine Deschinkel (Laboratoire PRiSM,Université de Versailles).

Cet article traite du problème d'optimisation du besoin en stockage dans les graphes de tâches périodiques. En pratique, notre problème tend à minimiser le besoin en registres dans les programmes embarqués, où les instructions d'une boucle sont représentées par un graphe de dépendances de données cyclique (GDD).

Le problème d'ordonnancement périodique de tâches (instructions) cycliques avec minimisation du nombre de registres, dans sa forme la plus générale, peut se formuler sous forme d'un programme linéaire en nombre entiers où les variables de décision sont les dates de début de chacune des tâches, des variables binaires indiquant une réutilisation ou non de registres entre deux tâches (non nécessairement distinctes), et les distances de réutilisation. Ce problème étant NP-complet , une résolution exacte s'avère trop coûteuse en pratique.

Ici, nous avons exploité le fait que le problème en question fait apparaître un problème sous-jacent d'affectation pour lequel nous connaissons un algorithme en temps polynomial (méthode Hongroise) pour proposer une heuristique appropriée appelée SIRALINA. Cette heuristique très satisfaisante est en train d'être incluse dans un compilateur pour l'embarqué chez STMicroelectronics.

Groupe de travail "Logique et Programmation": Amir Ben-Amram

damiano — Monday 24 November 2008

The next meeting of the GdT "Logique et Programmation" will take place on

Monday, 24 November 2008,
at 1:30 pm, in room B311.

We will listen to a talk given by Amir Ben-Amram, invited researcher from the School of Computer Science at the Academic College of Tel-Aviv Yaffo, who will tell us about his latest ideas regarding size-change termination.

Thèse d'Amanda Bouffier

jcdubacq — Thursday 16 October 2008

I am delighted to invite you to my PhD titled "Analyse discursive automatique de textes. Application à la modélisation de connaissances".

It will take place on 2008-10-16 at 2pm, room B311 of the LIPN.

The jury will be composed of:

Mme Marie-Paule Pery-Woodley, professeur, ERSS, université de Toulouse Le Mirail, rapporteur
M. Patrice Enjalbert, professeur, GREYC, université de Caen, rapporteur
M. Jean-Pierre Desclés, professeur, LALIC, université Paris IV, examinateur
M. Alain Venot, professeur, LIM & BIO, université Paris XIII, examinateur
M. Daniel Kayser, professeur, LIPN, université Paris XIII, directeur de thèse
M. Thierry Poibeau, chargé de recherche CNRS, LIPN, université Paris XIII, encadrant de thèse

NLP is mainly focused on words and sentences even if most people agree that a better understanding of text structure could help extracting knowledge. In this thesis, we show that, in certain domains, textual approaches are relevant for NLP, taking as an example a specific task related to the medical domain: the automatic modelling of health practice guidelines. Clinical Guidelines are legal documents providing an aid for physicists in their diagnosis and treatment tasks. Because these recommendations are not really followed, there is a need for electronic tools that facilitate the access to these documents. Our system, GemFrame, is capable of automatically structuring Health Practice Guidelines by recognizing conditions and recommandations and computing the relations between these two kinds of segments. We have showed that these relations involve large parts of texts, beyond the sentence barrier, that justify a textual approach. We propose a strategy based on the recognition of linguistic features acquired by an original method that links linguistic observation and machine learning. The system has been fully validated on three complementary aspects: usefulness, performances and relevance of the method.

Self-Organizing Map with False-Neighbor Degree and its Behaviors

Webmaster — Thursday 18 September 2008

In the real world, it is not always true that neighboring houses are physically adjacent or close to each other. In other words, ``neighbors'' are not always ``true neighbors''. I will talk about a new proposed Self-Organizing Map (SOM) algorithm, SOM with False-Neighbor degree between neurons (called FN-SOM). The behavior of FN-SOM is investigated with learning for various input data. I will explain that FN-SOM can obtain a more effective map reflecting the distribution state of input data than the conventional SOM and Growing Grid.

Bolasso: Model Consistent Lasso Estimation through the Bootstrap

Webmaster — Thursday 3 July 2008

We consider the least-square linear regression problem with regularization by the L1-norm, a problem usually referred to as the Lasso. In this paper, we present a detailed asymptotic analysis of model consistency of the Lasso. For various decays of the regularization parameter, we compute asymptotic equivalents of the probability of correct model selection (i.e., variable selection). For a specific rate decay, we show that the Lasso selects all the variables that should enter the model with probability tending to one exponentially fast, while it selects all other variables with strictly positive probability. We show that this property implies that if we run the Lasso for several bootstrapped replications of a given sample, then intersecting the supports of the Lasso bootstrap estimates leads to consistent model selection. This novel variable selection algorithm, referred to as the Bolasso, is compared favorably to other linear regression methods on synthetic data and datasets from the UCI machine learning repository.

Distances and Kernels: Machine Learning Concepts for Structured Data in Computational Biology

Webmaster — Tuesday 20 May 2008

Distances and kernels have become essential concepts for machine learning applications in computational biology. The talk will focus on their theoretical foundations, clarifies the relationship between the concepts, presents advantages and disadvantages, and gives hints for the derivation of new distance measures and kernels as well as for their application. The focus of the talk will be on distances and kernels for structured data, in particular, sets, sequences, and graphs.

Pour le connaître : http://wwwkramer.in.tum.de/kramer/stefan.html

Counting occurrence of words in random texts

jcdubacq — Tuesday 19 February 2008

Le séminaire OCAD accueille Pierre Nicodème (chargé de recherche CNRS, École polytechnique)

We consider random texts generated by a Bernoulli source. We want to count simultaneously the number of occurrences of words within a finite set of words in a random text of size n. The use of generating functions permits to construct a multivariate function counting the occurrences in texts of all size from 0 to infinity. From there several techniques give access to texts of size n. We compute the multivariate generating function:

by the very elegant analytic inclusion-exclusion method that resorts to combinatorics.
by constructing the Aho-Corasick automaton recognizing the words, and translating later to generating functions. We compare the complexity of these two methods.

This is a joint work with F. Bassino, J. Clément and J. Fayolle.

Workshop on Implicit Computational Complexity

mogbil — Monday 11 February 2008

Implicit Computational Complexity

Implicit Computational Complexity (ICC) has emerged from various propositions to use logic and formal methods like types, rewriting systems, interpretations... to provide languages for complexity-bounded computation, in particular for polynomial time computing.

It aims at studying the computational complexity of programs without refering to a particular machine model and explicit bounds on time or memory, but instead by relying on programming or logical disciplines that imply complexity properties. Several approaches have been explored for that purpose, like restrictions on primitive recursion, lambda calculus, types, linear logic, rewriting systems .... They originally mostly came from the functional programming paradigm, but imperative programming is now also addressed. Two objectives of ICC are:

on the one hand to find natural implicit logical characterizations of functions of various complexity classes,
on the other hand to design criteria usable for the static verification of programs complexity. In particular the latter goal requires characterizations which are flexible enough to validate commonly used algorithms.

Finding out more

The home page of this workshop supported by the NO-CoST ANR project is online.

Probabilistic take on permutation tableaux

jcdubacq — Tuesday 5 February 2008

Le séminaire OCAD accueille Pawel Hitczenko (Drexel University, USA)

Permutation tableaux are relatively new combinatorial objects that are in bijections with permutations. They have ben introduced in the context of algebraic combinatorics and subsequently found applications in combinatorial aspects of some particle models (like PASEP). Permutation tableaux have been studied mostly by bijective methods. In this talk, I will describe a direct, elementary approach based on probabilistic interpretation of a basic construction. This talk is partially based on results obtained jointly with Sylvie Corteel.

From Universal Algebra and Topology to Lambda Calculus and Back

mogbil — Monday 4 February 2008

Le séminaire LCR accueille (en première partie d'une séance double) Antonino Salibra (Università Ca'Foscari di Venezia)

In this seminar we show how algebra and topology can be fruitfully applied to the operational semantics and to the model theory of the untyped lambda calculus. We explain the structure of the lattice of lambda theories (i.e., equational extensions of lambda calculus) and analyze one of the long-standing open problem of lambda calculus, regarding the existence of a topological model of the beta-eta lambda theory, where all Scott-continuous functions are representable.

Combinatorial Problems on an Opportunistic Grid Middleware

jcdubacq — Tuesday 29 January 2008

Le séminaire OCAD accueille Alfredo Goldman (chercheur, LIG, Grenoble et professeur associé, Universidad de São Paulo)

The InteGrade project is multi-university initiative aimed at building a novel object-oriented Grid middleware that focuses on leveraging the idle computing power of commodity workstations such as PCs in shared laboratories, corporate employee workstations, and household PCs. Our goal is to allow organizations to use their existing computing infrastructure to perform useful computation, without requiring the purchase of additional hardware. Moreover, users who share the idle portion of their resources should have their quality of service preserved by the InteGrade middleware. InteGrade provides support for highly-coupled parallel applications, checkpointing, security, and an integrated development environment.

In this presentation I will quickly present the main features of InteGrade, and then present some combinatorial problems related to the project.

Semantics for higher-order quantum computation

mogbil — Monday 7 January 2008

Le séminaire LCR accueille Benoît Valiron (University of Ottawa).

We give a categorical semantics for a call-by-value linear, computational lambda calculus and discuss some steps towards a concrete model. Such a lambda calculus was used by Selinger and Valiron as the backbone of a functional programming language for quantum computation. One feature of this lambda calculus is its linear type system, which includes a duplicability operator "!" as in linear logic. Another main feature is its call-by-value reduction strategy, together with a side-effect to model probabilistic measurements.

Uniform asymptotics of Poisson approximation to binomial distribution and its generalizations

jcdubacq — Tuesday 11 December 2007

Le séminaire OCAD accueille Hsien-Kuei Hwang (中央研究院 — Academia Sinica, Taipei, Taïwan)

New uniform asymptotic approximations with error bounds are derived for a generalized total variation distance of Poisson approximation to the Poisson-binomial distribution (covering binomial distribution as special case). The method of proof is also applicable to other Poisson approximation problems, and therefore to a lot of data structures and algorithms.

Cluster Validity and Feature Selection

pierre — Thursday 22 November 2007

Le séminaire A3 accueille Sandro Saitta is PhD student in Computer Science (IMAC, École Polytechnique Fédérale de Lausanne (EPFL), Switzerland)

Estimating the number of clusters in a data set is an important task of clustering. For example, algorithms such as K-means start with the number of clusters as an input. We propose a new bounded cluster validity index that is computationally efficient and can detect the single cluster case. The new index is found to be better than several indices that have been proposed in the literature. Feature selection reduces the dimensionality of a data set in order, for example, to better understand the data.

Existing methods such as Genetic Algorithm based techniques, although efficient, need complex tuning of several search parameters. We will introduce a wrapper approach combining a global search algorithm (PGSL) with the Support Vector Machines (SVM). Results show that the new method is efficient and selects a small number of features for the benchmark data sets.

Exponentials in Ludics: How and at what price

mogbil — Monday 5 November 2007

Le séminaire LCR accueille Michele Basaldella (Università di Siena).

Ludics is a research project introduced by J-Y Girard in 2001 whose aim is to overcome the distinction Syntax/Semantics (of proofs) and it consists of a theory in which both sides deal with objects of the same nature, Design, which are basic artifacts of Ludics. They are manipulated by means of cut-elimination, conceived as the unique tool for testing properties inside the theory itself. Ludics also provides a (fully complete) Game Semantics for Multiplicative Additive Focalized Linear Logic. In this talk, we will show how to extend Ludics framework by adding exponential constructions in such a way to preserve the Ludics Theorems (in particular Separation Theorem). As we will see, our approach is closely related to AJM Game Semantics in the treatment of exponentials. We will also discuss the limits of our framework as well as its strength, namely the preservation of all isomorphisms involving exponentials, and the arising of a notion of non uniform exponential, both appearing in a rather natural way.