
Kernel Methods in Particle Filtering
Coufal, David ; Beneš, Viktor (advisor) ; Klebanov, Lev (referee) ; Studený, Milan (referee)
Kernel Methods in Particle Filtering David Coufal Doctoral thesis  abstract The thesis deals with the use of kernel density estimates in particle filtering. In particular, it examines the convergence of the kernel density estimates to the filtering densities. The estimates are constructed on the basis of an out put from particle filtering. It is proved theoretically that using the standard kernel density estimation methodology is effective in the context of particle filtering, although particle filtering does not produce random samples from the filtering densities. The main theoretical results are: 1) specification of the upper bounds on the MISE error of the estimates of the filtering densities and their partial derivatives; 2) specification of the related lower bounds and 3) providing a suitable tool for checking persistence of the Sobolev character of the filtering densities over time. In addition, the thesis also focuses on designing kernels suitable for practical use. 1


On attempts to characterize facetdefining inequalities of the cone of exact games
Studený, Milan ; Kroupa, Tomáš ; Kratochvíl, Václav
The sets of balanced, totally balanced, exact and supermodular games play an important role in cooperative game theory. These sets of games are known to be polyhedral cones. The (unique) nonredundant description of these cones by means of the socalled facetdefining inequalities is known in cases of balanced games and supermodular games, respectively. The facet description of the cones of exact games and totally balanced games are not known and we present conjectures about what are the facetdefining inequalities for these cones. We introduce the concept of an irreducible minbalanced set system and conjecture that the facetdefining inequalities for the cone of totally balanced games correspond to these set systems. The conjecture concerning exact games is that the facetdefining inequalities for this cone are those which correspond to irreducible minbalanced systems on strict subsets of the set of players and their conjugate inequalities. A consequence of the validity of the conjectures would be a novel result saying that a game m is exact if and only if m and its reflection are totally balanced.


Anotační grafy a Bayesovské sítě
Čoupková, Evženie ; Studený, Milan (advisor) ; Antoch, Jaromír (referee)
There are different models, which describe conditional independence induced by multivariate distributions. Models such as Undirected Graphs, Directed Acyclic Graphs, Essential Graphs and Annotated Graphs are introduced and compared in this thesis. The focus is put on annotated graphs. It is shown that annotated graphs represent equivalence classes of DAGrepresentable relations. An algorithm for reconstruction of an annotated graph from an essential graph as well as the algorithm for the inverse procedure are given. Some properties of a characteristic imset, which is a nongraphical representation, are discussed. A relationship between annotated graphs and characteristic imsets is investigated, an algorithm, which reconstructs an annotated graph from a characteristic imset is given. Powered by TCPDF (www.tcpdf.org)


Recursive linear models and conditional independence structures
Zouhar, Jan ; Studený, Milan (advisor) ; Hlubinka, Daniel (referee)
Linear recursive systems (LRS) describe linear relationships among continuous random variables (typically, normally distributed ones). Acyclic oriented graphs are used to provide a qualitative description of these relationships. In a different branch of statistics, graphs serve as a means to describe conditional independence (CI) structures in systems of random variables. One of the aims of the thesis is to show that within the class of regular Gaussian distributions, both approaches coincide: for a given acyclic oriented graph, the statistical model of LRS specified by the graph is equivalent to a class of Gaussian distributions with CI structures that accord with the same graph. Furthermore, we generalized some of the relations between a graph of LRS and its CI structure outside the scope of Gaussian distributions. Another focus of the thesis is the relation between the graph of a LRS and the covariances among its variables. We derived a relationship that is analogous to the method of path coefficients which was introduced in the 1920s by the American geneticist Sewall Wright.

 

Implementation of Transformation from Acyclic Directed Graph to Essential Graph
Vansa, Tibor ; Studený, Milan (referee) ; Šimeček, Petr (advisor)
Nazev prace: Implenientace algoritnm pro transfonnaci acyklickeho ori entovaneho grafu na esencialni graf Autor: Tibor Vansa Katcdra: Katcdra pravdepodobnosti a matematieke statistiky Vedouci bakalafske prace: Mgr. Petr Simecek, MSc. email vcdouciho: simecektfJatrey.karlin.iiiif.cuni.cz Abstrakt: Cilem pfedlozene prace je seznamit cteiiafe se zakladni tc matikou Bayesovskych siti a jojich pouzitiin. Ty poskytuji pfirozcny na stroj pro praci a infoniiaceini /iati/xuiyini neurcitosti a hraji dulezitou roli v oblasti navrhu a analyzy sanioncicich so algoritmu. Dale pfedstavujo program implomeiitujici algoritmus pro translormaci acyklickeho orien tovaneho grain na osoncialni graf. Jcho jadro tvofi ulgoritmus RNDr. Miltuia Stndeneliu, DrSc. Podslatou zniineneho algoritmu je metoda ko roktniho slucovani komponcnt grain. Klicova slova: Baycsovske site, eaeiicialui graf, korektni sliuY;ovani kom ponent feto'/covcho grafu Title: Implementation of Algorithm for Traiisfurination of Acyclic Di rected Graph to Essential Graph Author: Tibor Vansa, Department: Department of Probahility and Mathematical Statistics Supervisor: Mgr. Petr Simccek,MSc. Supervisor's email address: siniect'kfn^atrey.karlin.mff.cuni.cz Abstract: The aim of the work is to introduce the reader to the theory of Bayesian Networks and their...


Approximate solution of Unconstrained influence diagrams
Fried, Vojtěch ; Vomlelová, Marta (advisor) ; Studený, Milan (referee)
We give an introduction to the theory of probabilistic graphical models and describe several types of them (Bayesian Networks  BN, Influence Diagrams  ID, Unconstrained Influence Diagrams  UID). Unconstrained Influence Diagrams support the possibility for the user to choose the ordering of decisions based on observations. This increases the expressive power of UIDs compared to IDs but makes it harder to find an optimal solution. It is often impossible to find an optimal solution because of exponential complexity increase compared to IDs. Therefore we design and investigate several approximate methods to solve UIDs. The result of these methods is an ordinary ID created from the former UID by adding edges. The optimal solution of the ID should be as close to the original UID as possible. Heuristical methods represent one type of the methods investigated. Heuristical methods use a simplification of the optimal algorithm. During the run of the algorithm heuristics are used to cut off the branches that are not perspective for further calculation. Another type of methods is to create the ID directly. We evaluate our methods experimentally based on randomly generated UIDs of three types and compare their performance namely to the optimal solution and to equally complex random methods.


Basic facts concerning extreme supermodular functions
Studený, Milan
Elementary facts and observations on the cone of supermodular set functions are recalled. The manuscript deals with such operations with set functions which preserve supermodularity\nand the emphasis is put on those such operations which even preserve extremality (of a supermodular function). These involve a few selftransformations of the cone of supermodular set functions. Moreover, projections to the (lessdimensional) linear space of set functions for a subset of the variable set are discussed. Finally, several extensions to the (moredimensional) linear space of set functions for a superset of the variable set are shown to be both preserving supermodularity and extremality.


LP relaxations and pruning for characteristic imsets
Studený, Milan
The geometric approach to learning BN structure is to represent it by a certain vector; a suitable such zeroone vector is the characteristic imset, which allows to reformulate the task of finding global maximum of a score over BN structures as an integer linear programming problem. The main contribution of this report is an LP relaxation of the corresponding polytope, that is, a polyhedral description of the domain of the respective integer linear programming problem.


On polyhedral approximations of polytopes for learning Bayes nets
Studený, Milan ; Haws, D.
We review three vector encodings of Bayesian network structures. The first one has recently been applied by Jaakkola et al., the other two use special integral vectors, called imsets. The central topic is the comparison of outer polyhedral approximations of the corresponding polytopes. We show how to transform the inequalities suggested by Jaakkola et al. to the framework of imsets. The result of our comparison is the observation that the implicit polyhedral approximation of the standard imset polytope suggested in (Studený Vomlel 2010) gives a closer approximation than the (transformed) explicit polyhedral approximation from (Jaakkola et al. 2010). Finally, we confirm a conjecture from (Studený Vomlel 2010) that the abovementioned implicit polyhedral approximation of the standard imset polytope is an LP relaxation of the polytope.
