Defended PhD Theses

data. In a lot of emerging fields, like bioinformatics, they are confronted with datasets

having thousands of variables, a lot of noise, non-linear dependencies and, only, tens of

samples. The detection of functional relationships, when such uncertainty is contained in

data, constitutes a major challenge.

Our work focuses on variable selection and network inference from datasets having

many variables and few samples (high variable-to-sample ratio), such as microarray data.

Variable selection is the topic of machine learning whose objective is to select, among a

set of input variables, those that lead to the best predictive model. The application of

variable selection methods to gene expression data allows, for example, to improve cancer

diagnosis and prognosis by identifying a new molecular signature of the disease. Network

inference consists in representing the dependencies between the variables of a dataset by

a graph. Hence, when applied to microarray data, network inference can reverse-engineer

the transcriptional regulatory network of cell in view of discovering new drug targets to

cure diseases.

In this work, two original tools are proposed MASSIVE (Matrix of Average Sub-Subset

Information for Variable Elimination) a new method of feature selection and MRNET (Minimum

Redundancy NETwork), a new algorithm of network inference. Both tools rely on

the computation of mutual information, an information-theoretic measure of dependency.

More precisely, MASSIVE and MRNET use approximations of the mutual information

between a subset of variables and a target variable based on combinations of mutual informations

between sub-subsets of variables and the target. The used approximations allow

to estimate a series of low variate densities instead of one large multivariate density. Low

variate densities are well-suited for dealing with high variable-to-sample ratio datasets,

since they are rather cheap in terms of computational cost and they do not require a large

amount of samples in order to be estimated accurately. Numerous experimental results

show the competitiveness of these new approaches. Finally, our thesis has led to a freely

available source code of MASSIVE and an open-source R and Bioconductor package of

network inference.},
note = {Funder: Universite Libre de Bruxelles},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}

L'objectif global de notre travail consiste `a combler ces lacunes et `a préciser les interactions entre protéines membranaires chez la levure Saccharomyces cerevisiae et plus précisément, entre les transporteurs. Nous avons commencé notre travail par l'étude d'un jeu de données d'interactions `a grande échelle entre toutes les perméases détectées par une méthode de double hybride spécialement adaptée aux protéines insolubles (split ubiquitin). Premi`erement, la qualité des données a été estimée en étudiant le comportement global des données et des témoins négatifs et positifs. Les données ont ensuite été standardisées et filtrées de faccon `a ne conserver que les plus significatives. Ces interactions ont ensuite été étudiées en les modélisant dans un réseau d'interactions que nous avons étudié par des techniques issues de la théorie des graphes. Apr`es une évaluation systématique de différentes méthodes de clustering, nous avons notamment recherché au sein du réseau des groupes de protéines densément interconnectées et de fonctions similaires qui correspondraient éventuellement `a des complexes protéiques. Les résultats révélés par l'étude du réseau expérimental se sont révélés assez décevants. En effet, m^eme si nous avons pu retrouver certaines interactions déj`a décrites, un bon nombre des interactions filtrées semblait n'avoir aucune réalité biologique et nous n'avons pu retrouver que tr`es peu de modules de protéines de fonction semblable hautement inter-connectées. Parmi ceux-ci, il est apparu que les transporteurs d'acides aminés semblaient interagir entre eux.

L'approche expérimentale n'ayant eu que peu de succ`es, nous l'avons contournée en utilisant des méthodes de génomique comparative d'inférence d'interactions fonctionnelles. Dans un premier temps, malgré une évaluation rigoureuse, l'étude des profils phylogénétiques (la prédiction d'interactions fonctionnelles en étudiant la corrééélation des profils de présence - absence des g`enes dans un ensemble de génomes), n'a produit que des résultats mitigés car les perméases semblent tr`es peu conservées d`es lors que l'on consid`ere d'autres organismes que les},
note = {Funder: Universite Libre de Bruxelles},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}

The results show that good fault detectors can be obtained. We extend the set of possible faults and go on to show that a single fault detector can be trained to detect several faults in both a robot's sensors and actuators. We show that fault detectors can be synthesized that are robust to variations in the task. Finally, we show how a fault detector can be trained to allow one robot to detect faults that occur in another robot.

The second approach involves the use of firefly-inspired synchronization to allow the presence of faulty robots to be determined by other non-faulty robots in a swarm robotic system. We take inspiration from the synchronized flashing behavior observed in some species of fireflies. Each robot flashes by lighting up its on-board red LEDs and neighboring robots are driven to flash in synchrony. The robots always interpret the absence of flashing by a particular robot as an indication that the robot has a fault. A faulty robot can stop flashing periodically for one of two reasons. The fault itself can render the robot unable to flash periodically.

Alternatively, the faulty robot might be able to detect the fault itself using endogenous fault detection and decide to stop flashing.

Thus, catastrophic faults in a robot can be directly detected by its peers, while the presence of less serious faults can be detected by the faulty robot itself, and actively communicated to neighboring robots. We explore the performance of the proposed algorithm both on a real world swarm robotic system and in simulation. We show that failed robots are detected correctly and in a timely manner, and we show that a system composed of robots with simulated self-repair capabilities can survive relatively high failure rates.

We conclude that i) fault injection and learning can give robots the capacity to detect faults that occur in themselves, and that ii) firefly-inspired synchronization can enable robots in a swarm robotic system to detect and communicate faults.

},
note = {Funder: Universite Libre de Bruxelles},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}

data. In a lot of emerging fields, like bioinformatics, they are confronted with datasets

having thousands of variables, a lot of noise, non-linear dependencies and, only, tens of

samples. The detection of functional relationships, when such uncertainty is contained in

data, constitutes a major challenge.

Our work focuses on variable selection and network inference from datasets having

many variables and few samples (high variable-to-sample ratio), such as microarray data.

Variable selection is the topic of machine learning whose objective is to select, among a

set of input variables, those that lead to the best predictive model. The application of

variable selection methods to gene expression data allows, for example, to improve cancer

diagnosis and prognosis by identifying a new molecular signature of the disease. Network

inference consists in representing the dependencies between the variables of a dataset by

a graph. Hence, when applied to microarray data, network inference can reverse-engineer

the transcriptional regulatory network of cell in view of discovering new drug targets to

cure diseases.

In this work, two original tools are proposed MASSIVE (Matrix of Average Sub-Subset

Information for Variable Elimination) a new method of feature selection and MRNET (Minimum

Redundancy NETwork), a new algorithm of network inference. Both tools rely on

the computation of mutual information, an information-theoretic measure of dependency.

More precisely, MASSIVE and MRNET use approximations of the mutual information

between a subset of variables and a target variable based on combinations of mutual informations

between sub-subsets of variables and the target. The used approximations allow

to estimate a series of low variate densities instead of one large multivariate density. Low

variate densities are well-suited for dealing with high variable-to-sample ratio datasets,

since they are rather cheap in terms of computational cost and they do not require a large

amount of samples in order to be estimated accurately. Numerous experimental results

show the competitiveness of these new approaches. Finally, our thesis has led to a freely

available source code of MASSIVE and an open-source R and Bioconductor package of

network inference.},
note = {Funder: Universite Libre de Bruxelles},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}

Etant donné ces nouveaux besoins, cette th`ese se focalise sur la modélisation et l'implantation des aspects temporels dans bases de données. En effet, la conception d'une application de base de données se fait par un encha^inement de trois phases (conceptuelle, logique et physique). Au niveau conceptuel, plusieurs mod`eles conceptuels ont été proposés intégrant les caractéristiques temporelles et spatiales.

Malheureusement, au niveau logique, les mod`eles de données des SGBD actuels n'offrent pas les concepts nécessaires pour implanter le mod`ele conceptuel spatio-temporel. Nous proposons donc de nouvelles r`egles de traductions d'un schéma conceptuel, basé sur le mod`ele MADS (Modélisation des Applications `a des données spatio-temporelles), en un schéma logique MADSLog pour les mod`eles cibles `a savoir : relationnel et relationnel-objet. Chaque r`egle transforme un concept structurel, temporel et spatial du mod`ele MADS en un ou plusieurs concepts supportés par la cible. Par exemple, la propriété spatiale définissant la géométrie d'un type d'objet est traduite par la création d'un nouvel attribut de type spatial dans ce type d'objet. Un outil CASE(Computer-Aided Software Engineering) appelé Schema Translateur est développé dans cette th`ese implémentant toutes les r`egles de traductions.

La traduction de schémas conceptuels en schémas logiques peut impliquer une perte sémantique en raison de la différence de la puissance d'expression entre le mod`ele conceptuel et le mod`ele de données des SGBD existants. D'o`u la nécessité de générer un ensemble de contraintes d'intégrité afin de préserver la sémantique définie dans le schéma conceptuel. Ces contraintes sont exprimées `a ce niveau par des formules logiques.

Avec l'apparition de GML (Geographic Markup Language ) qui est conccu pour la modélisation, le transport et le stockage d'informations géographiques. Nous transformons également le schéma conceptuel MADS en GML. De nouveaux schémas GML temporel et spatial sont définis qui peuvent ^etre employés par n'importe application de base de données spatio-temporelle.

Au niveau physique, nous proposons une méthode d'adaptation du schéma logique en schéma physique pour le mod`ele relationnel-objet.

Elle permet de définir les tables, les types abstraits, les types d'objets, les domaines, etc. Notre proposition permet aussi la génération des contraintes d'intégrité au niveau physique. En effet, chaque contrainte d'intégrité (structurelle, temporelle ou spatiale) qui est définie en calcul logique est exprimée soit directement par des contraintes déclaratives ou soit par des déclencheurs du SGBD choisi. Les déclencheurs spatiaux sont fondés sur les fonctionnalités prédéfinies dans Oracle, alors que les déclencheurs temporels sont basés sur les opérateurs et méthodes appliquées sur les types temporels.

Enfin, la traduction de requ^etes est une deuxi`eme clef de cette recherche. Le but de la traduction de requ^etes, exprimées en alg`ebre, étant de reconstituer l'information au sens MADS `a partir de la base de données stockées dans le SGDB cible. Elle permet de traduire les expressions algébriques MADS, qui sont définies sur le schéma conceptuel et non sur le schéma physique, en requ^etes opérationnelles qui peuvent ^etre exécutées sur une base de données spatiale et temporelle sous un SGBD ou un SIG.

},
note = {Funder: Universite Libre de Bruxelles},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}

Division of labour is the mechanism that decides how many robots shall be used to perform a task. The efficiency of the group of robots depends in fact on the number of robots involved in a task. If too few robots are used to achieve a task, they might not be successful or might perform poorly. If too many robots are used, it might be a waste of resources. The number of robots to use might be decided a priori by the system designer. More interestingly, the group of robots might autonomously select how many and which robots to use. In this thesis, we study algorithms of the latter type.

The robotic literature offers already some solutions, but most of them use a form of direct communication between agents. Direct, or explicit, communication between the robots is usually considered a necessary condition for co-ordination. Recent studies have questioned this assumption. The claim is based on observations of animal colonies, e.g., ants and termites. They can effectively co-operate without directly communicating, but using indirect forms of communication like stigmergy. Because they do not rely on communication, such colonies show robust behaviours at group level, a condition that one wishes also for groups of robots. Algorithms for robot co-ordination without direct communication have been proposed in the last few years. They are interesting not only because they are a stimulating intellectual challenge, but also because they address a situation that might likely occur when using robots for real-world out-door applications. Unfortunately, they are still poorly studied.

This thesis helps the understanding and the development of such algorithms. We start from a specific case to learn its characteristics. Then we improve our understandings through comparisons with other solutions, and finally we port everything into another domain.

We first study an algorithm for division of labour that was inspired by ants' foraging. We test the algorithm in an application similar to ants' foraging: prey retrieval. We prove that the model used for ants' foraging can be effective also in real conditions. Our analysis allows us to understand the underlying mechanisms of the division of labour and to define some way of measuring it.

Using this knowledge, we continue by comparing the ant-inspired algorithm with similar solutions that can be found in the literature and by assessing their differences. In performing these comparisons, we take care of using a formal methodology that allows us to spare resources. Namely, we use concepts of experiment design to reduce the number of experiments with real robots, without losing significance in the results.

Finally, we apply and port what we previously learnt into another application: Sensor/Actor Networks (SANETs). We develop an architecture for division of labour that is based on the same mechanisms as the ants' foraging model. Although the individuals in the SANET can communicate, the communication channel might be overloaded. Therefore, the agents of a SANET shall be able to co-ordinate without accessing the communication channel.},
note = {Funder: Universite Libre de Bruxelles},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}

The decidability and algorithmic analysis of timed and hybrid automata have been intensively studied in the literature. The central result for timed automata is that they are positively decidable. This is not the case for hybrid automata, but semi-algorithmic methods are known when the dynamics is relatively simple, namely a linear relation between the derivatives of the variables.

With the increasing complexity of nowadays systems, those models are however limited in their classical semantics, for modelling realistic implementations or dynamical systems.

In this thesis, we study the algorithmics of complex semantics for timed and hybrid automata.

On the one hand, we propose implementable semantics for timed automata and we study their computational properties: by contrast with other works, we identify a semantics that is implementable and that has decidable properties.

On the other hand, we give new algorithmic approaches to the analysis of hybrid automata whose dynamics is given by an affine function of its variables.

},
note = {Funder: Universite Libre de Bruxelles},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}

Indeed, according to organizations theory, the higher levels in the organizations need summarized and conceptual information to take fast, high-level, and effective decisions. For Web sites, these levels include the organization managers and the Web site chief editors. At these levels, the results produced by Web analytics tools are mostly useless. Indeed, most of these results target Web designers and Web developers. Summary reports like the number of visitors and the number of page views can be of some interest to the organization manager but these results are poor. Finally, page-group and directory hits give the Web site chief editor conceptual results, but these are limited by several problems like page synonymy (several pages contain the same topic), page polysemy (a page contains several topics), page temporality, and page volatility.

Web usage mining research projects on their part have mostly left aside Web analytics and its limitations and have focused on other research paths. Examples of these paths are usage pattern analysis, personalization, system improvement, site structure modification, marketing business intelligence, and usage characterization. A potential contribution to Web analytics can be found in research about reverse clustering analysis, a technique based on self-organizing feature maps. This technique integrates Web usage mining and Web content mining in order to rank the Web site pages according to an original popularity score. However, the algorithm is not scalable and does not answer the page-polysemy, page-synonymy, page-temporality, and page-volatility problems. As a consequence, these approaches fail at delivering summarized and conceptual results.

An interesting attempt to obtain such results has been the Information Scent algorithm, which produces a list of term vectors representing the visitors' needs. These vectors provide a semantic representation of the visitors' needs and can be easily interpreted. Unfortunately, the results suffer from term polysemy and term synonymy, are visit-centric rather than site-centric, and are not scalable to produce. Finally, according to a recent survey, no Web usage mining research project has proposed a satisfying solution to provide site-wide summarized and conceptual audience metrics.

In this dissertation, we present our solution to answer the need for summarized and conceptual audience metrics in Web analytics. We first described several methods for mining the Web pages output by Web servers. These methods include content journaling, script parsing, server monitoring, network monitoring, and client-side mining. These techniques can be used alone or in combination to mine the Web pages output by any Web site. Then, the occurrences of taxonomy terms in these pages can be aggregated to provide concept-based audience metrics. To evaluate the results, we implement a prototype and run a number of test cases with real Web sites.

According to the first experiments with our prototype and SQL Server OLAP Analysis Service, concept-based metrics prove extremely summarized and much more intuitive than page-based metrics. As a consequence, concept-based metrics can be exploited at higher levels in the organization. For example, organization managers can redefine the organization strategy according to the visitors' interests. Concept-based metrics also give an intuitive view of the messages delivered through the Web site and allow to adapt the Web site communication to the organization objectives. The Web site chief editor on his part can interpret the metrics to redefine the publishing orders and redefine the sub-editors' writing tasks. As decisions at higher levels in the organization should be more effective, concept-based metrics should significantly contribute to Web usage mining and Web analytics.

},
note = {Funder: Universite Libre de Bruxelles},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}

Dans cette th`ese, nous explorons le lien entre les files fluides et les processus QBD, et nous appliquons des arguments utilisés en théorie des processus de renouvellement pour obtenir la distribution stationnaire de plusieurs mod`eles fluides.

Nous commenccons par l'étude d'une file fluide avec un réservoir de taille infinie; nous déterminons sa distribution stationnaire, et nous présentons un algorithme permettant de calculer cette distribution de mani`ere tr`es efficace. Nous observons que la distribution stationnaire de la file fluide de capacité infinie est tr`es semblable `a celle d'un processus QBD avec une infinité de niveaux. Nous poursuivons la recherche des similarités entre les files fluides et les processus QBD, et nous étudions ensuite la distribution stationnaire d'une file fluide de capacité finie. Nous montrons que l'algorithme valable pour le cas du réservoir infini permet de calculer toutes les quantités importantes du mod`ele avec un réservoir fini.

Nous considérons ensuite des mod`eles fluides plus complexes, de capacité finie ou infinie, o`u le comportement du processus markovien des phases peut changer lorsque le niveau du réservoir atteint certaines valeurs seuils. Nous montrons que les méthodes développées pour des mod`eles classiques s'étendent de mani`ere naturelle `a ces mod`eles plus complexes.

Pour terminer, nous étudions les conditions nécessaires et suffisantes qui m`enent `a l'indépendance du niveau et de la phase d'une file fluide de capacité infinie en régime stationnaire. Ces résultats s'appuient sur des résultats semblables concernant des processus QBD.

Markov modulated fluid queues are two-dimensional Markov processes, of which the first component, called the level, represents the content of a buffer or reservoir and takes real values; the second component, called the phase, is the state of a Markov process which controls the evolution of the level in the following manner: the level varies linearly at a rate which depends on the phase and which can take any real value.

In this thesis, we explore the link between fluid queues and Quasi Birth-and-Death (QBD) processes, and we apply Markov renewal techniques in order to derive the stationary distribution of various fluid models.

To begin with, we study a fluid queue with an infinite capacity buffer; we determine its stationary distribution and we present an algorithm which performs very efficiently in the determination of this distribution. We observe that the equilibrium distribution of the fluid queue is very similar to that of a QBD process with infinitely many levels. We further exploit the similarity between the two processes, and we determine the stationary distribution of a finite capacity fluid queue. We show that the algorithm available in the infinite case allows for the computation of all the important quantities entering in the expression of this distribution.

We then consider more complex models, of either finite or infinite capacities, in which the behaviour ff the phase process may change whenever the buffer is empty or full, or when it reaches certain thresholds. We show that the techniques that we develop for the simpler models can be extended quite naturally in this context.

Finally, we study the necessary and sufficient conditions that lead to the independence between the level and the phase of an infinite capacity fluid queue in the stationary regime. These results are based on similar developments for QBD processes.},
note = {Funder: Universite Libre de Bruxelles},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}

A metaheuristic is a generic algorithmic template that, once properly instantiated, can be used for finding high quality solutions of combinatorial optimization problems.

For obtaining a fully functioning algorithm, a metaheuristic needs to be configured: typically some modules need to be instantiated and some parameters need to be tuned. For the sake of precision, we use the expression \emph{parametric tuning} for referring to the tuning of numerical parameters, either continuous or discrete but in any case ordinal.

On the other hand, we use the expression \emph{structural tuning} for referring to the problem of defining which modules should be included and, in general, to the problem of tuning parameters that are either boolean or categorical. Finally, with \emph{tuning} we refer to the composite \emph{structural and parametric tuning}.

Tuning metaheuristics is a very sensitive issue both in practical applications and in academic studies. Nevertheless, a precise definition of the tuning problem is missing in the literature. In this thesis, we argue that the problem of tuning a metaheuristic can be profitably described and solved as a machine learning problem.

Indeed, looking at the problem of tuning metaheuristics from a machine learning perspective, we are in the position of giving a formal statement of the tuning problem and to propose an algorithm, called F-Race, for tackling the problem itself. Moreover, always from this standpoint, we are able to highlight and discuss some catches and faults in the current research methodology in the metaheuristics field, and to propose some guidelines.

The thesis contains experimental results on the use of F-Race and some examples of practical applications. Among others, we present a feasibility study carried out by the German-based software company \emph{SAP}, that concerned the possible use of F-Race for tuning a commercial computer program for vehicle routing and scheduling problems. Moreover, we discuss the successful use of F-Race for tuning the best performing algorithm submitted to the \emph{International Timetabling Competition} organized in 2003 by the \emph{Metaheuristics Network} and sponsored by \emph{PATAT}, the international series of conferences on the \emph{Practice and Theory of Automated Timetabling}.

The thesis describe a set of tools for the analysis of such data. It is specially gearded towards microarray data.},
note = {Funder: Universite Libre de Bruxelles},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}

* A survey of metaheuristics. Chapter 1 gives an extensive overview on the nowadays most important metaheuristics. This overview points out the importance of two important concepts in metaheuristics: intensification and diversification.

* The hyper-cube framework. Chapter 2 introduces a new framework for implementing ACO algorithms. This framework brings two main benefits to ACO researchers. First, from the point of view of the theoretician: we prove that Ant System (the first ACO algorithm to be proposed in the literature) in the hyper-cube framework generates solutions whose expected quality monotonically increases with the number of algorithm iterations when applied to unconstrained problems. Second, from the point of view of the experimental researcher, we show through examples that the implementation of ACO algorithms in the hyper-cube framework increases their robustness and makes the handling of the pheromone values easier.

* Deception. In the first part of Chapter 3 we formally define the notions of first and second order deception in ant colony optimization. Hereby, first order deception corresponds to deception as defined in the field of evolutionary computation and is therefore a bias introduced by the problem (instance) to be solved. Second order deception is an ACO-specific phenomenon. It describes the observation that the quality of the solutions generated by ACO algorithms may decrease over time in certain settings. In the second part of Chapter 3 we propose different ways of avoiding second order deception.

* ACO for the KCT problem. In Chapter 4 we outline an ACO algorithm for the edge-weighted k-cardinality tree (KCT) problem. This algorithm is implemented in the hyper-cube framework and uses a pheromone model that was determined to be well-working in Chapter 3. Together with the evolutionary computation and the tabu search approaches that we develop in Chapter 4, this ACO algorithm belongs to the current state-of-the-art algorithms for the KCT problem.

* ACO for the GSS problem. Chapter 5 describes a new ACO algorithm for the group shop scheduling (GSS) problem, which is a general shop scheduling problem that includes among others the well-known job shop scheduling (JSS) and the open shop scheduling (OSS) problems. This ACO algorithm, which is implemented in the hyper-cube framework and which uses a new pheromone model that was experimentally tested in Chapter 3, is currently the best ACO algorithm for the JSS as well as the OSS problem. In particular when applied to OSS problem instances, this algorithm obtains excellent results, improving the best known solution for several OSS benchmark instances. A final contribution of this thesis is the development of a general method for the solution of combinatorial optimization problems which we refer to as Beam-ACO. This method is a hybrid between ACO and a tree search technique known as beam search. We show that Beam-ACO is currently a state-of-the-art method for the application to the existing open shop scheduling (OSS) problem instances.

},
note = {Funder: Universite Libre de Bruxelles},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}