We study a fundamental bi-criteria optimization problem for variable selection in statistical learning;

the two criteria are a loss/residual function and a model control/regularization. The former function measures the fitness of the learning model to data and the latter function is employed as a control of the complexity of the model. We focus on the case where the loss function is convex and the model control function is a difference-of-convex (dc) sparsity measure.

From the perspective of optimality theory, we study the question of when a d(irectional)-stationary solution of the non-convex optimization problem has some kind of global optimality properties; from the perspective of computational performance, we compare the numerical results of sparse linear regression using several dc sparsity functions. The study is applicable to both exact and surrogate sparsity functions.

This is ongoing joint work with Miju Ahn (University of Southern California) and Jack Xin (University of California at Irvine).

A temporal graph is a graph in which the edge set can change from step to step. The temporal graph exploration problem TEMP is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time. We consider only temporal graphs that are connected at each step. For such temporal graphs with n nodes, we show that it is NP-hard to approximate TEMP with ratio O(n^{1-epsilon}) for any epsilon>0. We also provide an explicit construction of temporal graphs that require Theta(n²) steps to be explored. We then consider TEMP under the assumption that the underlying graph (i.e. the graph that contains all edges that are present in the temporal graph in at least one step) belongs to a specific class of graphs. We show that temporal graphs can be explored in O(n.log³n) steps if the underlying graph is a (2 x n) grid.

We call an algorithm space-efficient if it matches the running times of standard algorithms or come close to it, but uses less space. The talk gives an overview of known space-efficient basic graph algorithms in a setting where an n-vertex input graph is read-only and the computation must take place in a working memory of O(n) bits or little more than that. We then shortly discuss the importance of graph representations in the context of space-efficient algorithms. We conclude the talk with the presentation of three algorithms for depth-first search that demonstrate some useful tricks to obtain further space-efficient algorithms.

Withthe aim of enhancing visualization of data sets, i.e., to make them easy to interpret, a powerful tool is to reduce the complexity of the data set by reducing its dimensionality in an interpretable manner, or to transform the data so that interpretability is enhanced. This is frequently done by solving a Mathematical Optimization problem, which may be far from trivial, but tractable.

In this talk we will present two examples of such complexity reduction strategy. First, we will address a Principal Component Analysis model with sparsity in their components, so that loadings have a clearer interpretation. Then we will address a classification model (Support Vector Machine) for data involving categorical variables, to be grouped in such a way that the weights in the score function are easier to interpret. Our numerical results will show that the use of Mathematical Optimization-based approaches may lead to results outperforming the state of the art.

In this talk, we will discuss two new data mining problems, namely, ranked tiling and rank matrix factorisation, which we introduce to mine a set of interesting patterns in rank matrices. In this type of matrix, each row defines a complete/partial ranking of the columns. Rank matrix occurs naturally in applications like sports or other competitions. It is also a useful abstraction when dealing with numeric data in which the rows are incomparable.

Ranked tiling studies the problem of finding areas called ranked tiles that have high average rank scores. Each ranked tile is defined by a set of rows and a set of columns. Mining such ranked tiles is useful as they reveal prominent local relations between sets of rows and columns. In contrast, rank matrix factorisation considers the problem of decomposing a rank matrix into a product of two smaller matrices, one of which contains k partial rankings of columns. That decomposition summaries the original matrix in a succinct way. In each case, I will show how we can formalise and solve the data mining problem using optimisation principles.

We will also discuss how to use the mined patterns to find biomarkers of patient subtypes, which is an important problem in the area of personalised medicine.

FIB-SEM imaging combines scanning electron microscope (SEM) visualization with focused ion beam (FIB) milling and is becoming the method of choice to elucidate the 3D organization of the cellular architecture. However, this new technology has some inherent limitations due to the milling and scanning processes that may cause defects in the obtained image stacks. The first type of defects are curtaining effects which appear as vertical ripples from top to bottom of the SEM image. The second type appears in SEM images as horizontal irregular strips with inhomogeneous change in intensity values when compared to the preceding image in the stack. A third defect is revealed by an image deformation which results from specimen drifting during SEM image acquisition. In this talk, I will present our solutions to correct these defects by using Fourier analysis and correlation-based local deformation estimation to improve the visual quality of FIB-SEM data and to facilitate the segmentation of organelles and the subsequent extraction of quantitative information. The efficiency of the proposed correction solutions for FIB-SEM images of biological samples is demonstrated through a number of experiments.

In this talk, we consider exact algorithms for the following problem: determine for a graph G, given with a proper vertex color, whether it is a subgraph of a properly colored interval graph, i.e., we must turn G into an interval graph by adding edges between vertices with different colors. The problem is known to be NP-complete for the case of four colors. In this talk, we show that for any fixed number of colors the problem can be solved in 2^O(n/log n) time, and give a matching lower bound assuming the Exponential Time Hypothesis for any fixed number of colors >= 6.

Enabling computers to understand human behavior has the potential to revolutionize many areas that benefit society such as clinical diagnosis, human-computer interaction, and social robotics. Critical to the understanding of human behavior or any temporally-varying phenomenon in general is the ability to segment, classify, and cluster time series data.

In the first part of this talk, I will present Segment-based Support Vector Machines (Seg-SVMs), a framework for supervised, weakly-supervised, and unsupervised time series analysis. Seg-SVMs outperform state-of-the-art approaches by combining three powerful ideas: energy-based structure prediction, bag-of-words representation, and maximum-margin learning. I will provide an overview of Seg-SVMs and demonstrate their benefits for one particular problem: early event detection.

In the second part of this talk, I will describe an algorithm to harness the power of big data for large-scale human behavior analysis. In particular, I will present Instance Ranking SVM (IRSVM), a novel Multiple Instance Learning (MIL) formulation for learning from data with little annotation. IRSVM outperforms existing MIL algorithms by embracing the correlation of data instances and anticipating the deficiency of the instance classifier.

Bio.Minh Hoai is a research fellow at Oxford University. He obtained Ph.D from Carnegie Mellon University in 2012 and B.E. from The University of New South Wales in 2005. He is the recipient of the CVPR2012 Best Student Paper Award. He was a member of the mathematical Olympiad team representing Vietnam in the 41st International Mathematical Olympiad, where he won a Gold Medal

Cet exposé propose une étude comparative entre l'Apprentissage par Renforcement Inverse (ARI) et l'Apprentissage par Imitation (AI).

L'ARI et l'AI sont deux cadres de travail qui utilisent le concept de Processus Décisionnel de Markov (PDM) et dans lesquels nous cherchons à résoudre le problème d'Apprentissage par Démonstrations (AD). L'AD est un problème où un agent appelé apprenti cherche à apprendre à partir de l'observation des démonstrations d'un autre agent appelé expert.

Dans le cadre de travail de l'AI, l'apprenti essaie d'apprendre directement la politique de l'expert alors que dans le cadre de l'ARI, l'apprenti essaie d'apprendre la récompense qui explique la politique de l'expert. Cette récompense est ensuite optimisée pour imiter l'expert.

On peut donc légitimement se demander s'il y a un intérêt à estimer une récompense qui devra ensuite être optimisée ou si l'estimation d'une politique est suffisante. Cette question assez naturelle n'a pas encore été réellement traitée dans la littérature pour l'instant. Ici, des réponses partielles à la fois d'un point de vue théorique et pratique sont produites.

This talk provides a comparative study between Inverse Reinforcement Learning (IRL) and Apprenticeship Learning (AL).

IRL and AL are two frameworks, using Markov Decision Processes (MDP), which are used for the imitation learning problem where an agent tries to learn from demonstrations of an expert.

In the AL framework, the agent tries to learn the expert policy whereas in the IRL framework, the agent tries to learn a reward which can explain the behavior of the expert. This reward is then optimized to imitate the expert.

One can wonder if it is worth estimating such a reward, or if estimating a policy is sufficient. This quite natural question has not really been addressed in the literature right now. We provide partial answers, both from a theoretical and empirical point of view.

Clustering and visualizing community genomic sequence data (aka metagenomic data) is a challenging problem in computational biology. We have recently developed an approach that is based on nonlinear dimension reduction of composition-based genomic features via a variant of Stochastic Neighbourhood Embedding. The latter casts the problem of data visualization as a non-convex optimization problem, and a challenging problem is the development of efficient solvers. In this talk I will give a general introduction to the problem and discuss possibilities to model it as a DC program.

This research presents a significant improvement of machine learning algorithms by reformulating them as discrete optimization problems and by unifying them into a framework. In fact, we study (i) a class of feature (parameter) selection methods, e.g. correlation-based and mutual information-based feature (parameter) selection, (ii) supervised learning algorithms, e.g. Lp-norm support vector machines and (iii) un-supervised learning algorithms, e.g. K-means clustering algorithm. We prove that these algorithms can be casted into a mixed 0-1 linear programming problem (M01LP), in which the number of variables and constraints are linear in the number of input parameters. The obtained M01LP is solved by means of branch and bound algorithm. The new formulation of machine learning algorithms allows to (1) realize the same representation of many different algorithms, (2) easily combine these algorithm to study their reliability including their generalization and robustness, (3) optimize the parameter selection process and learning model selection process.

Our theoretical findings are supported by a number of experiments on real-world datasets from the field of information security and digital forensics. The experimental results show that our new proposed approaches (5) decreased the computational efforts due to optimal learning algorithms and optimal parameter selection, (6) increased the reliability including the generalization and robustness and (7) increased the efficiency and effectiveness of network-based intrusion detection systems, host-based intrusion detection systems, web attack detection systems, botnet malware detection systems and malicious PDF file detection.

Newton's method is one of the fundamental tools in numerical analysis, operations research, optimization and control. It has numerous applications in management science, industrial and financial research, data mining. Newton's method is a method for finding successively better approximations to the roots (or zeroes) of a real or complex function. The Newton's method in one variable has a second order of convergence.

In recent years, some cubically convergent modified Newton's methods for multiple roots have been proposed and analyzed. These methods can be collected into two classes. The first one is based on the second derivative of the function f. The second one is based on the function f and its derivative f0.

In this work, we are interested in the second class. We describe a general family of iterative methods, which use exactly two values of f and one value of f0 at each iteration, for approximating a multiple root z with multiplicity m of a complex valued function. Almost all the families of methods existing in the literature are particular cases of this general method. We give some su±cient conditions that guarantee a third order of convergence and we discuss how to choose a small asymptotic error constant which may a®ect the convergence speed. Using Mathematica with its higher precision computation, we present some numerical examples to illustrate the theoretical results.

We consider a multiobjective optimization problem with face of data uncertanity and its robust counterpart. We establish the sufficient optimality condition for a robust efficient solution and a weakly robust efficient solution of the uncertain multiobjective optimization problem under the assumption that the objective functions are convex and the inequality constraints are generalized convex.

We formulate Mond-Weir type dual for the uncertain multiobjective optimization problem and establish weak and strong duality theorems.

Keywords : Uncertain multiobjective optimization, Robust multiobjective optimization, Sufficient optimality condition, Robust duality

It is well known that many graph problems can be solved in linear time for graphs of bounded treewidth with help of dynamic programming on the tree decomposition.

The running time of such algorithms is typically at least exponential in the treewidth, but for many problems, only algorithms that are superexponential are known. In this talk, a new method is discussed to obtain faster algorithms on tree decompositions. Central ideas are "group dominance" to sparsify tables in a dynamic programming algorithm, a way to establish such group dominance by showing that certain matrices have small rank, and an explicit small size basis for these matrices.

The technique will be explained in an informal way at the hand of one central example: the Steiner Tree problem. Recent experimental work that shows that the technique gives significant speedups will also be discussed.

This is joint work with Marek Cygan, Stefan Fafiani, Stefan Kratsch, and Jesper Nederlof.

L'algorithme des forêts aléatoires proposé par Breiman permet d'obtenir de bons résultats en fouille de données comparativement à de nombreuses approches. Cependant, en n'utilisant qu'un seul attribut parmi un sous-ensemble d'attributs tiré aléatoirement pour séparer les individus à chaque niveau de l'arbre, cet algorithme perd de l'information. Ceci est particulièrement pénalisant avec les ensembles de données en grandes dimensions où il peut exister de nombreuses dépendances entre attributs. Nous présentons un nouvel algorithme de forêts aléatoires d'arbres obliques obtenus par des séparateurs à vaste marge (SVM). La comparaison des performances de notre algorithme avec celles de l'algorithme de forêts aléatoires des arbres de décision C4.5 et de l'algorithme SVM montre un avantage significatif de notre proposition.

The random forests method is one of the most successful ensemble methods. However, random forests do not have high performance when dealing with very-high-dimensional data in presence of dependencies. In this case one can expect that there exist many combinations between the variables and unfortunately the usual random forests method does not effectively exploit this situation. We here investigate a new approach for supervised classification with a huge number of numerical attributes. We propose a random oblique decision trees method. It consists of randomly choosing a subset of predictive attributes and it uses SVM as a split function of these attributes. We compare, on 25 datasets, the effectiveness with classical measures (e.g. precision, recall, F1-measure and accuracy) of random forests of random oblique decision trees with SVMs and random forests of C4.5. Our proposal has significant better performance on very-high-dimensional datasets with slightly better results on lower dimensional datasets.

Keywords: High Dimensional Data, Random Forests, Oblique Decision Trees, Support Vector Machines.

Linear Programming with Linear Complementarity Constraints (LPLCC) is an area of active research in Optimization, due to its many applications, algorithms, and theoretical existence results. In this paper, a number of formulations for important nonconvex optimization problems are first reviewed. The most relevant algorithms for computing a complementary feasible solution, a stationary point, and a global minimum for the LPLCC are also surveyed, together with some comments about their efficiency and efficacy in practice.

La plupart des métaheuristiques ont été conçues, à l'origine, pour la résolution des problèmes d' « optimisation difficile » de nature discrète. Cependant, les ingénieurs sont souvent confrontés à des problèmes d'optimisation à variables continues : amélioration des performances d'un circuit électronique, identification des paramètres d'un modèle de gisement d'hydrocarbures, apprentissage d'un réseau de neurones ou d'une base de règles floues.

De tels problèmes peuvent être également « difficiles », dans un sens différent de celui consacré par la théorie de la complexité : fonction objectif non connue analytiquement ou bruitée, variables corrélées ou évoluant dans des gammes disparates, présence de non-linéarités, etc...

Les métaheuristiques offrent, dans ce cadre, un avantage précieux : elles n'exploitent pas les gradients de la fonction objectif. Ces techniques doivent cependant être adaptées au cas continu ; nous décrirons dans cet exposé quelques approches pour quatre métaheuristiques : le recuit simulé, la recherche tabou, les algorithmes génétiques et les algorithmes de colonies de fourmis. Nous esquisserons enfin le portrait d'un nouveau-né de la famille des métaheuristiques : la méthode des essaims particulaires, qui a été - quant à elle - conçue d'emblée dans le cas continu.

In practical applications of optimization it is common to have several conflicting objective functions to optimize. Frequently, these functions are subject to noise or can be of black-box type, preventing the use of derivative-based techniques.

We propose a novel multiobjective derivative-free methodology, calling it direct multisearch (DMS), which does not aggregate any of the objective functions. Our framework is inspired by the search/poll paradigm of direct-search methods of directional type and uses the concept of Pareto dominance to maintain a list of nondominated points (from which the new iterates or poll centers are chosen).

The aim of our method is to generate as many points in the Pareto front as possible from the polling procedure itself, while keeping the whole framework general enough to accommodate other disseminating strategies, in particular when using the (here also) optional search step.

DMS generalizes to multiobjective optimization (MOO) all direct-search methods of directional type.

We prove under the common assumptions used in direct search for single objective optimization that at least one limit point of the sequence of iterates generated by DMS lies in (a stationary form of) the Pareto front. However, extensive computational experience has shown that our methodology has an impressive capability of generating the whole Pareto front, even without using a search step.

This is joint work with: A.L. Custódio, J.F.A. Madeira and Luis Nunes Vicente.

1. BARTHELEMY, J.-P., and BRUCKER, F. (2007), ”Binary Clustering”, Discrete Applied Mathematics, avaiable online.
2. BRUCKER, F., and BARTHELEMY, J.-P. (2007), ”Éléments de Classification”, Hermes Publishing, London.
3. BERTRAND, P. (2000), ”Set Systems and Dissimilarities”, European Journal of Combinatorics, 21, 727–743.

1. – l'application d'une méta-heuristique d'optimisation connue (les algorithmes génétiques) pour optimiser la disposition des caractères sur le clavier logiciel et ainsi minimiser les déplacements à effectuer lors de saisie de texte en français. Le clavier GAG (Généré par Algorithme Génétique) est le résultat de cette optimisation.
2. – le système KeyGlass : celui-ci propose au fur et à mesure de la saisie des caractères supplémentaires à proximité du dernier caractère qui a été saisi. Ceci a pour but de diminuer les distances (avec le pointeur du dispositif de pointage) nécessaire à parcourir pour saisir du texte.

1. – d'une part sur des réductions de l'espace des états par agrégation des ressources ;
2. – d'autre part sur l'utilisation de la ré-optimisation, en cas de faible modification des données, en exploitant l'historique des résolutions des différentes instances du processus.

1. R. Arcangé­li, Dm-splines sur un domaine borné­ de ℝn. Publication UA 1204 CNRS N° 86/2 (1986).
2. A. Kouibia, Aproximació­n de curvas y supercies paramé­tricas mediante splines variacionales, Thèse doctorale, Universidad de Granada, 28 de Mai 1999.
3. A. Kouibia and M. Pasadas, Construction of Surfaces by discrete variational splines with Parallelism Conditions, J. Comput. Appl. Math. 164-165, 455-467, 2004.
4. A. Kouibia and M. Pasadas, Approximation by Discrete Variational Splines, J. Comput. Appl. Math. 116, 145156, 2000.
5. A. Kouibia and M. Pasadas, Variational bivariate interpolating splines with positivity constraints, Appl. Numer. Math. 44, 507-526, 2003.
6. A. Kouibia, M. Pasadas and J. J. Torrens, Construction of Surfaces with Parallelism Conditions, Numerical Algorithms 33, 331-342, 2003.
7. A. Kouibia and M. Pasadas, Construction of Surfaces by discrete variational splines with Parallelism Conditions, J. Comput. Appl. Math. 164-165, 455-467, 2004.
8. A. Kouibia and M. Pasadas, Approximation of surfaces by fairness bicubic splines, Adv. Comput. Math. 20, 87-103, 2004.
9. A. Kouibia, M. Pasadas, D. Sbibih, B. Bachir and A. Zidna, Linear interpolation Geometric continuity G2 of blended curves and surfaces, Preprint (2007).
10. M. Pasadas, Aproximación de curvas y supercies paramé­tricas con condiciones de tangencia, Thèse doctorale, Universidad de Granada (1995).

1. P1. Le traitement des séquences des mots/clés inconnus vis-à-vis du (des) dictionnaire(s) d'EI ;
2. P2. La richesse d'EI pour une classification pertinente.

1. – le modèle est un approximateur universel, i.e. que toute fonction continue définie sur un espace fonctionnel peut être approchée arbitrairement bien par un PMC fonctionnel ;
2. – de plus, l'estimation des paramètres du modèle est consistante. L'originalité de ce résultat vient du fait que non seulement l'estimation s'effectue sur un nombre fini d'individus (les fonctions observées), mais que de plus chacune de ces fonctions n'est connue qu'en un nombre fini de points d'observation (discrétisation).

1. creation of a set of depth images,
2. computation of blur filters,
3. stratification of the image,
4. blurring of each depth image,
5. and composition of the blurred depth images to form a single vision-simulated image.

1. – la maximalité en tant que code (au sens de l'inclusion) ;
2. – le fait que tout mot de A* puisse être facteur d'un mot de X*. Cette propriété est appellée densité de X* dans A*, ou encore complétude de X.

1. – la grande majorité des problèmes NP-complets naturels sont dans NLIN (sont reconnaissables en temps non déterministe linéraire) ;
2. – beaucoup de ces problèmes sont même encore plus faciles :
   1. certains problèmes de graphes (exemples : cycle hamiltonien et non planarité) sont reconnus sur RAMs en temps non déterministe linéaire O(n) en le nombre n de sommets du graphe concerné, donc indépendamment de son nombre d'arètes ;
   2. d'autres problèmes (Sac à dos, Clique, etc) sont résolubles par RAMs en temps linéaire O(n) et espace sous-linéaire O(√n) (et donc en temps déterministe sous-exponentiel 2O(√n) ;
   3. enfin, divers problèmes NP-complets paramètrés classiques, typiquement k-Vertex-cover (recouvrement d'un graphe par k sommets), sont résolubles en temps polynomial, et souvent linéaire, en utilisant seulement un nombre limité f(k) de pas non déterministes, c'est-à-dire un nombre de pas non déterministes dépendant du paramètre k, mais indépendant de la taille de la donnée.

1. 1 belongs to S;
2. if the positive integer x belongs to S, then 2x and 4x-1 belong to S;
3. S is the smallest set of positive integers with these properties.

1. t2(n)≠O(t1(n));
2. t2(n)-space Turing machines (TMs) are strictly more powerful than t1(n)-space TMs;
3. t2(n)·log(t1(n))-time TMs are strictly more powerful than t1(n)-time TMs.

1. nous rappellerons d'abord la définition originale des ensembles d'approximation ainsi que leur structure algébrique multivaluée. Nous montrerons comment l'étude de ces algèbres permet de définir des langages d'interrogation souple de bases de données.
2. nous introduirons ensuite les notions de système d'information et de décision considérés par cette théorie ainsi que les méthodes qu'elle propose d'extraction de connaissances (règles de classification et d'association). Usuellement présentées en termes de recherche d'implicants premiers, les algorithmes utilisés s'énoncent plus naturellement dans la théorie des hypergraphes.
3. enfin nous aborderons la notion d'espace de dépendance introduite par Pawlak et Novotny, que l'on peut facilement rattacher à la notion classique de dépendance fonctionnelle. Nous présenterons alors de manière très simple le théorème de Guigues et Duquenne sur les bases des systèmes de fermeture (ou des treillis de Galois). Ce théorème issu d'une autre approche de la fouille des données, permet en effet de résumer dans le cas fini, l'ensemble des dépendances exactes en un sous-ensemble réduit, unique et sans redondances.

1. R. Baeza-Yates, B. Ribeiro - Neto, Modern Information Retrieval, ACM Press, Addison-Wesley, 1999, 510 p.
2. Z. Pawlak, Rough Sets, Theoretical Aspects of Reasoning about Data, Kluwer, Dordrecht, 1991.
3. A. Lelu, Modèles neuronaux pour l'analyse de données documentaires et textuelles, Thèse de doctorat de l'Université de Paris 6, 1993.
4. F. Ibekwe - Sanjuan, A linguistic and mathematical method for mapping thematic trends from texts, ECAI 98, Henri Prade (ed.), John Willey and Sons, Ltd (1998) pp. 170 -- 174.

1. Fractals generated by m-Fermat cellular automata (e.g. linear cellular automata with states in a finite field). Applications - fractal structures of Gaussian binomial coefficients and Stirling numbers.
2. Fractals associated with m-Carlitz sequences of polynomials, Applications - fractals associated with the sequence of Legendre polynomials and the zero Bessel function.
3. Fractals associated with random multiplication of polynomials.
4. Self-similar functions generated by cellular automata.
5. Automaticity of double sequences generated by m-Fermat cellular automata.
6. Automaticity of double sequences generated by m-Carlitz sequences of polynomials.
7. Automaticity of coarse-graining invariant orbits of one-dimensional linear cellular automata.

1. T(u=v) si et seulement si les deux termes clos du premier ordre u et v ont la même valeur ;
2. T(A→B) si et seulement si T(A)⇒T(B) ;
3. T(∀X.A) si et seulement si T(A[X←D]) pour toute formule D(x) a une variable libre définissant une partie de ℕ.

1. – communications locales, entre processeurs a distance constante ;
2. – communications distantes ;
3. – diffusions (broadcast), si l'architecture le permet.