2008 |
Meyer, Patrick E Information-theoretic variable selection and network inference from microarray data PhD Thesis 2008, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210396b, title = {Information-theoretic variable selection and network inference from microarray data}, author = {Patrick E Meyer}, url = {https://dipot.ulb.ac.be/dspace/bitstream/2013/210396/1/baf3a39e-3c11-496d-8b3b-b952a1827ca0.txt}, year = {2008}, date = {2008-01-01}, abstract = {Statisticians are used to model interactions between variables on the basis of observed 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.}, Statisticians are used to model interactions between variables on the basis of observed<p>data. In a lot of emerging fields, like bioinformatics, they are confronted with datasets<p>having thousands of variables, a lot of noise, non-linear dependencies and, only, tens of<p>samples. The detection of functional relationships, when such uncertainty is contained in<p>data, constitutes a major challenge.<p>Our work focuses on variable selection and network inference from datasets having<p>many variables and few samples (high variable-to-sample ratio), such as microarray data.<p>Variable selection is the topic of machine learning whose objective is to select, among a<p>set of input variables, those that lead to the best predictive model. The application of<p>variable selection methods to gene expression data allows, for example, to improve cancer<p>diagnosis and prognosis by identifying a new molecular signature of the disease. Network<p>inference consists in representing the dependencies between the variables of a dataset by<p>a graph. Hence, when applied to microarray data, network inference can reverse-engineer<p>the transcriptional regulatory network of cell in view of discovering new drug targets to<p>cure diseases.<p>In this work, two original tools are proposed MASSIVE (Matrix of Average Sub-Subset<p>Information for Variable Elimination) a new method of feature selection and MRNET (Minimum<p>Redundancy NETwork), a new algorithm of network inference. Both tools rely on<p>the computation of mutual information, an information-theoretic measure of dependency.<p>More precisely, MASSIVE and MRNET use approximations of the mutual information<p>between a subset of variables and a target variable based on combinations of mutual informations<p>between sub-subsets of variables and the target. The used approximations allow<p>to estimate a series of low variate densities instead of one large multivariate density. Low<p>variate densities are well-suited for dealing with high variable-to-sample ratio datasets,<p>since they are rather cheap in terms of computational cost and they do not require a large<p>amount of samples in order to be estimated accurately. Numerous experimental results<p>show the competitiveness of these new approaches. Finally, our thesis has led to a freely<p>available source code of MASSIVE and an open-source R and Bioconductor package of<p>network inference. |
Brohée, Sylvain Etude bioinformatique du réseau d'interactions entre protéines de transport ches les Fungi PhD Thesis 2008, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210432, title = {Etude bioinformatique du réseau d'interactions entre protéines de transport ches les Fungi}, author = {Sylvain Brohée}, url = {https://dipot.ulb.ac.be/dspace/bitstream/2013/210432/15/0e52a8b3-982c-4616-9287-1e1e0b0cb703.txt}, year = {2008}, date = {2008-01-01}, abstract = {Les protéines associées aux membranes sont d'une importance cruciale pour la cellule. Cependant, en raison d'une plus grande difficulté de manipulation, les données biochimiques les concernant sont tr`es lacunaires, notamment au point de vue de la formation de complexes entre ces protéines. 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}, Les protéines associées aux membranes sont d'une importance cruciale pour la cellule. Cependant, en raison d'une plus grande difficulté de manipulation, les données biochimiques les concernant sont tr`es lacunaires, notamment au point de vue de la formation de complexes entre ces protéines.<p><p>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.<p><p>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 |
Christensen, Anders Lyhne Fault detection in autonomous robots PhD Thesis 2008, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210508, title = {Fault detection in autonomous robots}, author = {Anders Lyhne Christensen}, url = {https://dipot.ulb.ac.be/dspace/bitstream/2013/210508/4/aa65b29d-78b4-4739-9e96-25b7349058f8.txt}, year = {2008}, date = {2008-01-01}, abstract = {In this dissertation, we study two new approaches to fault detection for autonomous robots. The first approach involves the synthesis of software components that give a robot the capacity to detect faults which occur in itself. Our hypothesis is that hardware faults change the flow of sensory data and the actions performed by the control program. By detecting these changes, the presence of faults can be inferred. In order to test our hypothesis, we collect data in three different tasks performed by real robots. During a number of training runs, we record sensory data from the robots both while they are operating normally and after a fault has been injected. We use back-propagation neural networks to synthesize fault detection components based on the data collected in the training runs. We evaluate the performance of the trained fault detectors in terms of the number of false positives and the time it takes to detect a fault. 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. }, In this dissertation, we study two new approaches to fault detection for autonomous robots. The first approach involves the synthesis of software components that give a robot the capacity to detect faults which occur in itself. Our hypothesis is that hardware faults change the flow of sensory data and the actions performed by the control program. By detecting these changes, the presence of faults can be inferred. In order to test our hypothesis, we collect data in three different tasks performed by real robots. During a number of training runs, we record sensory data from the robots both while they are operating normally and after a fault has been injected. We use back-propagation neural networks to synthesize fault detection components based on the data collected in the training runs. We evaluate the performance of the trained fault detectors in terms of the number of false positives and the time it takes to detect a fault.<p>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.<p><p>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.<p>Alternatively, the faulty robot might be able to detect the fault itself using endogenous fault detection and decide to stop flashing.<p>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.<p><p>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.<p> |
Meyer, Patrick E Information-theoretic variable selection and network inference from microarray data PhD Thesis 2008, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210396c, title = {Information-theoretic variable selection and network inference from microarray data}, author = {Patrick E Meyer}, url = {http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210396}, year = {2008}, date = {2008-01-01}, note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |
Brohée, Sylvain Etude bioinformatique du réseau d'interactions entre protéines de transport ches les Fungi PhD Thesis 2008, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210432b, title = {Etude bioinformatique du réseau d'interactions entre protéines de transport ches les Fungi}, author = {Sylvain Brohée}, url = {http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210432}, year = {2008}, date = {2008-01-01}, note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |
Meyer, Patrick E Information-theoretic variable selection and network inference from microarray data PhD Thesis 2008, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210396, title = {Information-theoretic variable selection and network inference from microarray data}, author = {Patrick E Meyer}, url = {https://dipot.ulb.ac.be/dspace/bitstream/2013/210396/1/baf3a39e-3c11-496d-8b3b-b952a1827ca0.txt}, year = {2008}, date = {2008-01-01}, abstract = {Statisticians are used to model interactions between variables on the basis of observed 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.}, Statisticians are used to model interactions between variables on the basis of observed<p>data. In a lot of emerging fields, like bioinformatics, they are confronted with datasets<p>having thousands of variables, a lot of noise, non-linear dependencies and, only, tens of<p>samples. The detection of functional relationships, when such uncertainty is contained in<p>data, constitutes a major challenge.<p>Our work focuses on variable selection and network inference from datasets having<p>many variables and few samples (high variable-to-sample ratio), such as microarray data.<p>Variable selection is the topic of machine learning whose objective is to select, among a<p>set of input variables, those that lead to the best predictive model. The application of<p>variable selection methods to gene expression data allows, for example, to improve cancer<p>diagnosis and prognosis by identifying a new molecular signature of the disease. Network<p>inference consists in representing the dependencies between the variables of a dataset by<p>a graph. Hence, when applied to microarray data, network inference can reverse-engineer<p>the transcriptional regulatory network of cell in view of discovering new drug targets to<p>cure diseases.<p>In this work, two original tools are proposed MASSIVE (Matrix of Average Sub-Subset<p>Information for Variable Elimination) a new method of feature selection and MRNET (Minimum<p>Redundancy NETwork), a new algorithm of network inference. Both tools rely on<p>the computation of mutual information, an information-theoretic measure of dependency.<p>More precisely, MASSIVE and MRNET use approximations of the mutual information<p>between a subset of variables and a target variable based on combinations of mutual informations<p>between sub-subsets of variables and the target. The used approximations allow<p>to estimate a series of low variate densities instead of one large multivariate density. Low<p>variate densities are well-suited for dealing with high variable-to-sample ratio datasets,<p>since they are rather cheap in terms of computational cost and they do not require a large<p>amount of samples in order to be estimated accurately. Numerous experimental results<p>show the competitiveness of these new approaches. Finally, our thesis has led to a freely<p>available source code of MASSIVE and an open-source R and Bioconductor package of<p>network inference. |
Christensen, Anders Lyhne Fault detection in autonomous robots PhD Thesis 2008, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210508b, title = {Fault detection in autonomous robots}, author = {Anders Lyhne Christensen}, url = {http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210508}, year = {2008}, date = {2008-01-01}, note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |
2007 |
Minout, Mohammed Modélisation des aspects temporels dans les bases de données spatiales PhD Thesis 2007, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210672, title = {Modélisation des aspects temporels dans les bases de données spatiales}, author = {Mohammed Minout}, url = {https://dipot.ulb.ac.be/dspace/bitstream/2013/210672/1/1722265c-a6ce-4c36-af45-1bd2f7e47833.txt}, year = {2007}, date = {2007-01-01}, abstract = {L'introduction du temps dans les bases de données classiques et spatiales appara^it de plus en plus, aujourd'hui, comme une nécessité pour une gestion optimale de l'historicité. En effet, les applications de bases de données spatio-temporelles sont présentes dans un grand nombre d'applications. Le besoin, par exemple, est de sauvegarder l'historique des géométries des parcelles dans le syst`eme d'information d'un plan cadastral, la prévention d'incendie dans le syst`eme de gestion foresti`ere, le syst`eme de navigation des véhicules, etc. Cet historique des phénom`enes permet de mieux comprendre ce qui s'est produit dans le passé, de mani`ere `a éventuellement anticiper certaines évolutions futures. 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. }, L'introduction du temps dans les bases de données classiques et spatiales appara^it de plus en plus, aujourd'hui, comme une nécessité pour une gestion optimale de l'historicité. En effet, les applications de bases de données spatio-temporelles sont présentes dans un grand nombre d'applications. Le besoin, par exemple, est de sauvegarder l'historique des géométries des parcelles dans le syst`eme d'information d'un plan cadastral, la prévention d'incendie dans le syst`eme de gestion foresti`ere, le syst`eme de navigation des véhicules, etc. Cet historique des phénom`enes permet de mieux comprendre ce qui s'est produit dans le passé, de mani`ere `a éventuellement anticiper certaines évolutions futures.<p><p>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.<p><p>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.<p><p>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.<p><p>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.<p><p>Au niveau physique, nous proposons une méthode d'adaptation du schéma logique en schéma physique pour le mod`ele relationnel-objet.<p>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.<p><p>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.<p> |
Labella, Thomas Halva Division of labour in groups of robots PhD Thesis 2007, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210738, title = {Division of labour in groups of robots}, author = {Thomas Halva Labella}, url = {https://dipot.ulb.ac.be/dspace/bitstream/2013/210738/1/a17d211c-b53d-41ca-a5b2-44ddfb729e63.txt}, year = {2007}, date = {2007-01-01}, abstract = {In this thesis, we examine algorithms for the division of labour in a group of robot. The algorithms make no use of direct communication. Instead, they are based only on the interactions among the robots and between the group and the environment. 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.}, In this thesis, we examine algorithms for the division of labour in a group of robot. The algorithms make no use of direct communication. Instead, they are based only on the interactions among the robots and between the group and the environment.<p><p>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.<p><p>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.<p><p>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.<p><p>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.<p><p>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.<p><p>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. |
Minout, Mohammed Modélisation des aspects temporels dans les bases de données spatiales PhD Thesis 2007, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210672b, title = {Modélisation des aspects temporels dans les bases de données spatiales}, author = {Mohammed Minout}, url = {http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210672}, year = {2007}, date = {2007-01-01}, note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |
Labella, Thomas Halva Division of labour in groups of robots PhD Thesis 2007, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210738b, title = {Division of labour in groups of robots}, author = {Thomas Halva Labella}, url = {http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210738}, year = {2007}, date = {2007-01-01}, note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |
2006 |
Doyen, Laurent Algorithmic analysis of complex semantics for timed and hybrid automata PhD Thesis 2006, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210853, title = {Algorithmic analysis of complex semantics for timed and hybrid automata}, author = {Laurent Doyen}, url = {https://dipot.ulb.ac.be/dspace/bitstream/2013/210853/1/ad5afed5-fe61-4ada-951e-97b80d788a2f.txt}, year = {2006}, date = {2006-01-01}, abstract = {In the field of formal verification of real-time systems, major developments have been recorded in the last fifteen years. It is about logics, automata, process algebra, programming languages, etc. From the beginning, a formalism has played an important role: timed automata and their natural extension,hybrid automata. Those models allow the definition of real-time constraints using real-valued clocks, or more generally analog variables whose evolution is governed by differential equations. They generalize finite automata in that their semantics defines timed words where each symbol is associated with an occurrence timestamp. 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. }, In the field of formal verification of real-time systems, major developments have been recorded in the last fifteen years. It is about logics, automata, process algebra, programming languages, etc. From the beginning, a formalism has played an important role: timed automata and their natural extension,hybrid automata. Those models allow the definition of real-time constraints using real-valued clocks, or more generally analog variables whose evolution is governed by differential equations. They generalize finite automata in that their semantics defines timed words where each symbol is associated with an occurrence timestamp.<p><p>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.<p>With the increasing complexity of nowadays systems, those models are however limited in their classical semantics, for modelling realistic implementations or dynamical systems.<p><p>In this thesis, we study the algorithmics of complex semantics for timed and hybrid automata.<p>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. <p>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.<p> |
Norguet, Jean-Pierre Semantic analysis in web usage mining PhD Thesis 2006, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210890, title = {Semantic analysis in web usage mining}, author = {Jean-Pierre Norguet}, url = {https://dipot.ulb.ac.be/dspace/bitstream/2013/210890/2/80865cd4-01d4-4b3a-895f-7cd6614e5210.txt}, year = {2006}, date = {2006-01-01}, abstract = {With the emergence of the Internet and of the World Wide Web, the Web site has become a key communication channel in organizations. To satisfy the objectives of the Web site and of its target audience, adapting the Web site content to the users' expectations has become a major concern. In this context, Web usage mining, a relatively new research area, and Web analytics, a part of Web usage mining that has most emerged in the corporate world, offer many Web communication analysis techniques. These techniques include prediction of the user's behaviour within the site, comparison between expected and actual Web site usage, adjustment of the Web site with respect to the users' interests, and mining and analyzing Web usage data to discover interesting metrics and usage patterns. However, Web usage mining and Web analytics suffer from significant drawbacks when it comes to support the decision-making process at the higher levels in the organization. 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. }, With the emergence of the Internet and of the World Wide Web, the Web site has become a key communication channel in organizations. To satisfy the objectives of the Web site and of its target audience, adapting the Web site content to the users' expectations has become a major concern. In this context, Web usage mining, a relatively new research area, and Web analytics, a part of Web usage mining that has most emerged in the corporate world, offer many Web communication analysis techniques. These techniques include prediction of the user's behaviour within the site, comparison between expected and actual Web site usage, adjustment of the Web site with respect to the users' interests, and mining and analyzing Web usage data to discover interesting metrics and usage patterns. However, Web usage mining and Web analytics suffer from significant drawbacks when it comes to support the decision-making process at the higher levels in the organization.<p><p>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.<p><p>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. <p><p>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. <p><p>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. <p><p>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. <p> |
Doyen, Laurent Algorithmic analysis of complex semantics for timed and hybrid automata PhD Thesis 2006, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210853b, title = {Algorithmic analysis of complex semantics for timed and hybrid automata}, author = {Laurent Doyen}, url = {http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210853}, year = {2006}, date = {2006-01-01}, note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |
Norguet, Jean-Pierre Semantic analysis in web usage mining PhD Thesis 2006, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/210890b, title = {Semantic analysis in web usage mining}, author = {Jean-Pierre Norguet}, url = {http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210890}, year = {2006}, date = {2006-01-01}, note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |
2005 |
Soares, Ana Da Silva Fluid queues: building upon the analogy with QBD processes PhD Thesis 2005, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/211053, title = {Fluid queues: building upon the analogy with QBD processes}, author = {Ana Da Silva Soares}, url = {https://dipot.ulb.ac.be/dspace/bitstream/2013/211053/14/78b25498-9f78-4827-a0a0-5d7d0df0ba2a.txt}, year = {2005}, date = {2005-01-01}, abstract = {Les files d'attente fluides sont des processus markoviens `a deux dimensions, o`u la premi`ere composante, appelée le niveau, représente le contenu d'un réservoir et prend des valeurs continues, et la deuxi`eme composante, appelée la phase, est l'état d'un processus markovien dont l'évolution contr^ole celle du niveau. Le niveau de la file fluide varie linéairement avec un taux qui dépend de la phase et qui peut prendre n'importe quelle valeur réelle. 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.}, Les files d'attente fluides sont des processus markoviens `a deux dimensions, o`u la premi`ere composante, appelée le niveau, représente le contenu d'un réservoir et prend des valeurs continues, et la deuxi`eme composante, appelée la phase, est l'état d'un processus markovien dont l'évolution contr^ole celle du niveau. Le niveau de la file fluide varie linéairement avec un taux qui dépend de la phase et qui peut prendre n'importe quelle valeur réelle.<p><p>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.<p><p>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.<p><p>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.<p><p>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.<p><p>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.<p><p>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.<p><p>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.<p><p>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.<p><p>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. |
Soares, Ana Da Silva Fluid queues: building upon the analogy with QBD processes PhD Thesis 2005, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/211053b, title = {Fluid queues: building upon the analogy with QBD processes}, author = {Ana Da Silva Soares}, url = {http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/211053}, year = {2005}, date = {2005-01-01}, note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |
2004 |
Birattari, Mauro The problem of tuning metaheuristics as seen from a machine learning perspective PhD Thesis 2004, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/211128b, title = {The problem of tuning metaheuristics as seen from a machine learning perspective}, author = {Mauro Birattari}, url = {http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/211128}, year = {2004}, date = {2004-01-01}, note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |
Venet, David Algorithms for the analysis of gene expression data PhD Thesis 2004, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/211127b, title = {Algorithms for the analysis of gene expression data}, author = {David Venet}, url = {http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/211127}, year = {2004}, date = {2004-01-01}, note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |
Blum, Christian Theoretical and practical aspects of ant colony optimization PhD Thesis 2004, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/211187b, title = {Theoretical and practical aspects of ant colony optimization}, author = {Christian Blum}, url = {http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/211187}, year = {2004}, date = {2004-01-01}, note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |
Birattari, Mauro The problem of tuning metaheuristics as seen from a machine learning perspective PhD Thesis 2004, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/211128, title = {The problem of tuning metaheuristics as seen from a machine learning perspective}, author = {Mauro Birattari}, url = {https://dipot.ulb.ac.be/dspace/bitstream/2013/211128/6/30c55008-ccb8-4155-a97f-a560db6bf50f.txt}, year = {2004}, date = {2004-01-01}, abstract = { 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}. },note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } <p>A metaheuristic is a generic algorithmic template that, once properly instantiated, can be used for finding high quality solutions of combinatorial optimization problems.<p>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 parametric tuning for referring to the tuning of numerical parameters, either continuous or discrete but in any case ordinal. <p>On the other hand, we use the expression 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 tuning we refer to the composite structural and parametric tuning.</p><p><p><p>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.</p><p><p><p>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.</p><p><p><p>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 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 International Timetabling Competition organized in 2003 by the Metaheuristics Network and sponsored by PATAT, the international series of conferences on the Practice and Theory of Automated Timetabling.</p> |
Venet, David Algorithms for the analysis of gene expression data PhD Thesis 2004, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/211127, title = {Algorithms for the analysis of gene expression data}, author = {David Venet}, url = {https://dipot.ulb.ac.be/dspace/bitstream/2013/211127/14/4293bf3b-fad2-4bbf-889d-0ff93c97a58c.txt}, year = {2004}, date = {2004-01-01}, abstract = {High-throughput gene expression data have been generated on a large scale by biologists. The thesis describe a set of tools for the analysis of such data. It is specially gearded towards microarray data.}, High-throughput gene expression data have been generated on a large scale by biologists.<p>The thesis describe a set of tools for the analysis of such data. It is specially gearded towards microarray data. |
Blum, Christian Theoretical and practical aspects of ant colony optimization PhD Thesis 2004, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/211187, title = {Theoretical and practical aspects of ant colony optimization}, author = {Christian Blum}, url = {https://dipot.ulb.ac.be/dspace/bitstream/2013/211187/2/7de69405-9131-49f6-98ab-247576e132d1.txt}, year = {2004}, date = {2004-01-01}, abstract = {Combinatorial optimization problems are of high academical as well as practical importance. Many instances of relevant combinatorial optimization problems are, due to their dimensions, intractable for complete methods such as branch and bound. Therefore, approximate algorithms such as metaheuristics received much attention in the past 20 years. Examples of metaheuristics are simulated annealing, tabu search, and evolutionary computation. One of the most recent metaheuristics is ant colony optimization (ACO), which was developed by Prof. M. Dorigo (who is the supervisor of this thesis) and colleagues. This thesis deals with theoretical as well as practical aspects of ant colony optimization. * 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. }, Combinatorial optimization problems are of high academical as well as practical importance. Many instances of relevant combinatorial optimization problems are, due to their dimensions, intractable for complete methods such as branch and bound. Therefore, approximate algorithms such as metaheuristics received much attention in the past 20 years. Examples of metaheuristics are simulated annealing, tabu search, and evolutionary computation. One of the most recent metaheuristics is ant colony optimization (ACO), which was developed by Prof. M. Dorigo (who is the supervisor of this thesis) and colleagues. This thesis deals with theoretical as well as practical aspects of ant colony optimization.<p><p>* 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. <p><p>* 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.<p><p>* 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.<p><p>* 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.<p><p>* 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.<p><p> |
2000 |
Bontempi, Gianluca Local learning techniques for modeling, prediction and control PhD Thesis 2000, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/211823, title = {Local learning techniques for modeling, prediction and control}, author = {Gianluca Bontempi}, url = {http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/211823}, year = {2000}, date = {2000-01-01}, note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |
Bontempi, Gianluca Local learning techniques for modeling, prediction and control PhD Thesis 2000, (Funder: Universite Libre de Bruxelles). @phdthesis{info:hdl:2013/211823b, title = {Local learning techniques for modeling, prediction and control}, author = {Gianluca Bontempi}, url = {http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/211823}, year = {2000}, date = {2000-01-01}, note = {Funder: Universite Libre de Bruxelles}, keywords = {}, pubstate = {published}, tppubtype = {phdthesis} } |