Actualités du LIPN

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.

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.

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.

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

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.