|
|
Methods for class prediction with high-dimensional gene expression data
Šilhavá, Jana ; Matula, Petr (referee) ; Železný, Filip (referee) ; Smrž, Pavel (advisor)
Dizertační práce se zabývá predikcí vysokodimenzionálních dat genových expresí. Množství dostupných genomických dat významně vzrostlo v průběhu posledního desetiletí. Kombinování dat genových expresí s dalšími daty nachází uplatnění v mnoha oblastech. Například v klinickém řízení rakoviny (clinical cancer management) může přispět k přesnějšímu určení prognózy nemocí. Hlavní část této dizertační práce je zaměřena na kombinování dat genových expresí a klinických dat. Používáme logistické regresní modely vytvořené prostřednictvím různých regularizačních technik. Generalizované lineární modely umožňují kombinování modelů s různou strukturou dat. V dizertační práci je ukázáno, že kombinování modelu dat genových expresí a klinických dat může vést ke zpřesnění výsledku predikce oproti vytvoření modelu pouze z dat genových expresí nebo klinických dat. Navrhované postupy přitom nejsou výpočetně náročné. Testování je provedeno nejprve se simulovanými datovými sadami v různých nastaveních a následně s~reálnými srovnávacími daty. Také se zde zabýváme určením přídavné hodnoty microarray dat. Dizertační práce obsahuje porovnání příznaků vybraných pomocí klasifikátoru genových expresí na pěti různých sadách dat týkajících se rakoviny prsu. Navrhujeme také postup výběru příznaků, který kombinuje data genových expresí a znalosti z genových ontologií.
|
|
|
Constraint satisfaction for inductive logic programming
Chovanec, Andrej ; Barták, Roman (advisor) ; Železný, Filip (referee)
Inductive logic programming is a discipline investigating invention of clausal theories from observed examples such that for given evidence and background knowledge we are finding a hypothesis covering all positive examples and excluding all negative ones. In this thesis we extend an existing work on template consistency to general consistency. We present a three-phase algorithm DeMeR decomposing the original problem into smaller subtasks, merging all subsolutions together yielding a complete solution and finally refining the result in order to get a compact final hypothesis. Furthermore, we focus on a method how each individual subtask is solved and we introduce a generate-and-test method based on the probabilistic history-driven approach for this purpose. We analyze each stage of the proposed algorithms and demonstrate its impact on a runtime and a hypothesis structure. In particular, we show that the first phase of the algorithm concentrates on solving the problem quickly at the cost of longer solutions whereas the other phases refine these solutions into an admissible form. Finally, we prove that our technique outperforms other algorithms by comparing its results for identifying common structures in random graphs to existing systems.
|
|
|
Learning for Classical Planning
Chrpa, Lukáš ; Barták, Roman (advisor) ; Železný, Filip (referee) ; Berka, Petr (referee)
This thesis is mainly about classical planning for artificial intelligence (AI). In planning, we deal with searching for a sequence of actions that changes the environment from a given initial state to a goal state. Planning problems in general are ones of the hardest problems not only in the area of AI, but in the whole computer science. Even though classical planning problems do not consider many aspects from the real world, their complexity reaches EXPSPACE-completeness. Nevertheless, there exist many planning systems (not only for classical planning) that were developed in the past, mainly thanks to the International Planning Competitions (IPC). Despite the current planning systems are very advanced, we have to boost these systems with additional knowledge provided by learning. In this thesis, we focused on developing learning techniques which produce additional knowledge from the training plans and transform it back into planning do mains and problems. We do not have to modify the planners. The contribution of this thesis is included in three areas. First, we provided theoretical background for plan analysis by investigating action dependencies or independencies. Second, we provided a method for generating macro-operators and removing unnecessary primitive operators. Experimental evaluation of this...
|
|
|
Modelling and Solving Problems Using SAT Techniques
Balyo, Tomáš ; Barták, Roman (advisor) ; Železný, Filip (referee) ; Biere, Armin (referee)
Solving planning problems via translation to satisfiability (SAT) is one of the most successful approaches to automated planning. In this thesis we describe several ways of encoding a planning problem represented in the SAS+ formalism into SAT. We review and adapt existing encoding schemes as well as introduce new original encodings. We compare the encodings by calculating upper bounds on the size of the formulas they produce as well as by running extensive experiments on benchmark problems from the 2011 International Planning Competition (IPC). In the experimental section we also compare our encodings with the state-of-the-art encodings of the planner Madagascar. The experiments show, that our techniques can outperform these state-of-the-art encodings. In the presented thesis we also deal with a special case of post-planning optimization -- elimination of redundant actions. The elimination of all redundant actions is NP-complete. We review the existing polynomial heuristic approaches and propose our own heuristic approach which can eliminate a higher number and more costly redundant actions than the existing techniques. We also propose a SAT encoding for the problem of plan redundancy which together with MaxSAT solvers allows us to solve the problem of action elimination optimally. Experiments done with...
|
|
|
Modelling and Solving Problems Using SAT Techniques
Balyo, Tomáš ; Barták, Roman (advisor) ; Železný, Filip (referee) ; Biere, Armin (referee)
Solving planning problems via translation to satisfiability (SAT) is one of the most successful approaches to automated planning. In this thesis we describe several ways of encoding a planning problem represented in the SAS+ formalism into SAT. We review and adapt existing encoding schemes as well as introduce new original encodings. We compare the encodings by calculating upper bounds on the size of the formulas they produce as well as by running extensive experiments on benchmark problems from the 2011 International Planning Competition (IPC). In the experimental section we also compare our encodings with the state-of-the-art encodings of the planner Madagascar. The experiments show, that our techniques can outperform these state-of-the-art encodings. In the presented thesis we also deal with a special case of post-planning optimization -- elimination of redundant actions. The elimination of all redundant actions is NP-complete. We review the existing polynomial heuristic approaches and propose our own heuristic approach which can eliminate a higher number and more costly redundant actions than the existing techniques. We also propose a SAT encoding for the problem of plan redundancy which together with MaxSAT solvers allows us to solve the problem of action elimination optimally. Experiments done with...
|
|
|
Semantic annotations
Dědek, Jan ; Vojtáš, Peter (advisor) ; Maynard, Diana (referee) ; Železný, Filip (referee)
Four relatively separate topics are presented in the thesis. Each topic represents one particular aspect of the Information Extraction discipline. The first two topics are focused on our information extraction methods based on deep language parsing. The first topic relates to how deep language parsing was used in our extraction method in combination with manually designed extraction rules. The second topic deals with a method for automated induction of extraction rules using Inductive Logic Programming. The third topic of the thesis combines information extraction with rule based reasoning. The core of our extraction method was experimentally reimplemented using semantic web technologies, which allows saving the extraction rules in so called shareable extraction ontologies that are not dependent on the original extraction tool. The last topic of the thesis deals with document classification and fuzzy logic. We are investigating the possibility of using information obtained by information extraction techniques to document classification. Our implementation of so called Fuzzy ILP Classifier was experimentally used for the purpose of document classification.
|
|
|
Constraint satisfaction for inductive logic programming
Chovanec, Andrej ; Barták, Roman (advisor) ; Železný, Filip (referee)
Inductive logic programming is a discipline investigating invention of clausal theories from observed examples such that for given evidence and background knowledge we are finding a hypothesis covering all positive examples and excluding all negative ones. In this thesis we extend an existing work on template consistency to general consistency. We present a three-phase algorithm DeMeR decomposing the original problem into smaller subtasks, merging all subsolutions together yielding a complete solution and finally refining the result in order to get a compact final hypothesis. Furthermore, we focus on a method how each individual subtask is solved and we introduce a generate-and-test method based on the probabilistic history-driven approach for this purpose. We analyze each stage of the proposed algorithms and demonstrate its impact on a runtime and a hypothesis structure. In particular, we show that the first phase of the algorithm concentrates on solving the problem quickly at the cost of longer solutions whereas the other phases refine these solutions into an admissible form. Finally, we prove that our technique outperforms other algorithms by comparing its results for identifying common structures in random graphs to existing systems.
|
|
|
Learning for Classical Planning
Chrpa, Lukáš ; Barták, Roman (advisor) ; Železný, Filip (referee) ; Berka, Petr (referee)
This thesis is mainly about classical planning for artificial intelligence (AI). In planning, we deal with searching for a sequence of actions that changes the environment from a given initial state to a goal state. Planning problems in general are ones of the hardest problems not only in the area of AI, but in the whole computer science. Even though classical planning problems do not consider many aspects from the real world, their complexity reaches EXPSPACE-completeness. Nevertheless, there exist many planning systems (not only for classical planning) that were developed in the past, mainly thanks to the International Planning Competitions (IPC). Despite the current planning systems are very advanced, we have to boost these systems with additional knowledge provided by learning. In this thesis, we focused on developing learning techniques which produce additional knowledge from the training plans and transform it back into planning do mains and problems. We do not have to modify the planners. The contribution of this thesis is included in three areas. First, we provided theoretical background for plan analysis by investigating action dependencies or independencies. Second, we provided a method for generating macro-operators and removing unnecessary primitive operators. Experimental evaluation of this...
|
|
|
Methods for class prediction with high-dimensional gene expression data
Šilhavá, Jana ; Matula, Petr (referee) ; Železný, Filip (referee) ; Smrž, Pavel (advisor)
Dizertační práce se zabývá predikcí vysokodimenzionálních dat genových expresí. Množství dostupných genomických dat významně vzrostlo v průběhu posledního desetiletí. Kombinování dat genových expresí s dalšími daty nachází uplatnění v mnoha oblastech. Například v klinickém řízení rakoviny (clinical cancer management) může přispět k přesnějšímu určení prognózy nemocí. Hlavní část této dizertační práce je zaměřena na kombinování dat genových expresí a klinických dat. Používáme logistické regresní modely vytvořené prostřednictvím různých regularizačních technik. Generalizované lineární modely umožňují kombinování modelů s různou strukturou dat. V dizertační práci je ukázáno, že kombinování modelu dat genových expresí a klinických dat může vést ke zpřesnění výsledku predikce oproti vytvoření modelu pouze z dat genových expresí nebo klinických dat. Navrhované postupy přitom nejsou výpočetně náročné. Testování je provedeno nejprve se simulovanými datovými sadami v různých nastaveních a následně s~reálnými srovnávacími daty. Také se zde zabýváme určením přídavné hodnoty microarray dat. Dizertační práce obsahuje porovnání příznaků vybraných pomocí klasifikátoru genových expresí na pěti různých sadách dat týkajících se rakoviny prsu. Navrhujeme také postup výběru příznaků, který kombinuje data genových expresí a znalosti z genových ontologií.
|
guest ::
