|
|
Probabilistic Methods in Discrete Applied Mathematics
Fink, Jiří ; Loebl, Martin (advisor) ; Koubek, Václav (referee) ; Sereni, Jean-Sébastein (referee)
One of the basic streams of modern statistical physics is an effort to understand the frustration and chaos. The basic model to study these phenomena is the finite dimensional Edwards-Anderson Ising model. We present a generalization of this model. We study set systems which are closed under symmetric differences. We show that the important question whether a groundstate in Ising model is unique can be studied in these set systems. Kreweras' conjecture asserts that any perfect matching of the $n$-dimensional hypercube $Q_n$ can be extended to a Hamiltonian cycle. We prove this conjecture. The {\it matching graph} $\mg{G}$ of a graph $G$ has a vertex set of all perfect matchings of $G$, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle. We prove that the matching graph $\mg{Q_n}$ is bipartite and connected for $n \ge 4$. This proves Kreweras' conjecture that the graph $M_n$ is connected, where $M_n$ is obtained from $\mg{Q_n}$ by contracting all vertices of $\mg{Q_n}$ which correspond to isomorphic perfect matchings. A fault-free path in $Q_n$ with $f$ faulty vertices is said to be \emph{long} if it has length at least $2^n-2f-2$. Similarly, a fault-free cycle in $Q_n$ is long if it has length at least $2^n-2f$. If all faulty vertices are...
|
|
|
Anomaly Detection Using Generative Adversarial Networks
Měkota, Ondřej ; Fink, Jiří (advisor) ; Pilát, Martin (referee)
Generative adversarial networks (GANs) are able to capture distribution of its inputs. They are thus used to learn the distribution of normal data and then to detect anoma- lies, even if they are very rare; e.g. Schlegl et al. (2017) proposed an anomaly detection method called AnoGAN. However, a major disadvantage of GANs is instability during training. Therefore, Arjovsky et al. (2017) proposed a new version, called Wasserstein GAN (WGAN). The goal of this work is to propose a model, utilizing WGANs, to detect fraudulent credit card transactions. We develop a new method called AnoWGAN+e, partially based on AnoGAN, and compare it with One Class Support Vector Machines (OC-SVM) (Schöl- kopf et al. (2001)), k-Means ensemble (Porwal et al. (2018)) and other methods. Perfor- mance of studied methods is measured by area under precision-recall curve (AUPRC), and precision at different recall levels on credit card fraud dataset (Pozzolo (2015)). AnoW- GAN+e achieved the highest AUPRC and it is 12% better than the next best method OC-SVM. Furthermore, our model has 20% precision at 80% recall, compared to 8% precision of OC-SVM, and 89% precision at 10% recall as opposed to 79% of k-Means ensemble. 1
|
|
| |
|
|
Evolutionary Algorithms for the Design of Luminaire Optics
Drázdová, Zuzana ; Pilát, Martin (advisor) ; Fink, Jiří (referee)
The goal of this thesis was to explore the possibilities of using evolutionary algorithms to design components with specific purpose. We examined the process of designing an optimal shape of reflector from a highly reflective metal sheet. The main goal of this reflector is to evenly distribute light from a light emitting diode. We created a simplified model of the environment, where our component should be used. Then we used the evolutionary approach to find a suitable reflector shape for an existing device. One selected solution was manufactured and its properties measured. We also used the developed program to search for a design of an optical part for a completely new device proposal. Both tasks were accompanied by a number of problems that originated in an inaccurate task specification and general disparity between the fields of evolutionary computation and industrial components development. We provided an analysis of issues we encountered and presented solutions that can be applied to other similar tasks.
|
|
|
Optimization and Statistics
Fink, Jiří ; Loebl, Martin (advisor)
CONTENTS Nazev prace: Autor: Katedra (ustav-): Vedouci diplomove prace: E-mail vedouciho: Kh'cova slova; Abstrakt: Optimization and Statistics Jifi Fink Katedra aplikovane matematiky Doc. RNDr. Martin Loebl, CSc. loebl@kam.mff, cuni.cz Edwards-Anderson Ising model, Teorie grafu, T-join, Gaussovska distribuce Jedni'm ze zakladnich problemu moderni statisticke fyzikj' je'snada porozumet frus- traci a chaosu. Zakladnfm modelem je konecne dimenzionalni Edwards-Anderson Ising model. V optimalizaci to odpovida zkoumam minimalni'ch T-joinu v konecnych mnzkach s nahodnymi vahami na hranach. V teto praci studujeme "random join", coz je nahodna cesta mezi dvema pevne danj^mi \Tcholy. Puvodni definice je pfilis slozita; a tak jsme ukazali jednodussi. Tato defmice je pouzita k pfesnernu vypoctu "random join" na kruznici. Take jsme ukazali specialm algoritmus, ktery hleda cestu v mrfzce s danymi hranami. Tento algoritmus muze byt pouzit k experimentalnimu studovani "random join". Title: Author: Department: Supervisor: Supervisor's e-mail address: Keywords: Abstract: Optimization and Statistics Jin Fink Department of Applied Mathematics Doc. RNDr. Martin Loebl, CSc. loebl@kam.mff.cuni.cz Edwards-Anderson Ising model, Graph theory, T-join, the Gaussian distribution One of the basic streams of modern statistics physics is...
|
|
|
Searching Image Collections Using Deep Representations of Local Regions
Bátoryová, Jana ; Lokoč, Jakub (advisor) ; Fink, Jiří (referee)
In a known-item search task (KIS), the goal is to find a previously seen image in a multimedia collection. In this thesis, we discuss two different approaches based on the visual description of the image. In the first one, the user creates a collage of images (using images from an external search engine), based on which we provide the most similar results from the dataset. Our results show that preprocessing the images in the dataset by splitting them into several parts is a better way to work with the spatial information contained in the user input. We compared the approach to a baseline, which does not utilize this spatial information and an approach that alters a layer in a deep neural network. We also present an alternative approach to the KIS task, search by faces. In this approach, we work with the faces extracted from the images. We investigate face representation for the ability to sort the faces based on their similarity. Then we present a structure that allows easy exploration of the set of faces. We provide a demo, implementing all presented techniques.
|
|
|
Applications of Gray codes in cache-oblivious algorithms
Mička, Ondřej ; Fink, Jiří (advisor) ; Gregor, Petr (referee)
Modern computers employ a sophisticated hierarchy of caches to decrease the latency of memory accesses. This led to the development of cache-oblivious algorithms that strive to achieve the best possible performance on such memory hierarchies with minimal knowledge of the exact parameters of the hierarchy. A common technique used in the design of cache-oblivious algorithms is a recursion-based divide-and-conquer method. In this work, we show an alternative technique based on the Gray codes. We use the binary reflected Gray code to traverse arrays in the cache-oblivious way, allowing us to design algorithms for problems such as matrix transposition, naive matrix multiplication or naive convolution that match the asymptotic performance of their recursion-based counterparts. The advantage is that our algorithms can be implemented without recursion (or a stack that simulates it) by using a loopless algorithm. We also introduce a variant of the binary reflected Gray code tuned to certain applications of our technique and an almost loopless algorithm to generate it. Apart from the theoretical analysis of our technique's performance, we also examine its practical performance on the problem of matrix transposition.
|
|
|
Anomaly Detection Using Generative Adversarial Networks
Měkota, Ondřej ; Fink, Jiří (advisor) ; Pilát, Martin (referee)
Generative adversarial networks (GANs) are able to capture distribution of its inputs. They are thus used to learn the distribution of normal data and then to detect anoma- lies, even if they are very rare; e.g. Schlegl et al. (2017) proposed an anomaly detection method called AnoGAN. However, a major disadvantage of GANs is instability during training. Therefore, Arjovsky et al. (2017) proposed a new version, called Wasserstein GAN (WGAN). The goal of this work is to propose a model, utilizing WGANs, to detect fraudulent credit card transactions. We develop a new method called AnoWGAN+e, partially based on AnoGAN, and compare it with One Class Support Vector Machines (OC-SVM) (Schöl- kopf et al. (2001)), k-Means ensemble (Porwal et al. (2018)) and other methods. Perfor- mance of studied methods is measured by area under precision-recall curve (AUPRC), and precision at different recall levels on credit card fraud dataset (Pozzolo (2015)). AnoW- GAN+e achieved the highest AUPRC and it is 12% better than the next best method OC-SVM. Furthermore, our model has 20% precision at 80% recall, compared to 8% precision of OC-SVM, and 89% precision at 10% recall as opposed to 79% of k-Means ensemble. 1
|
|
|
The complexity of constrained graph drawing
Hora, Martin ; Jelínek, Vít (advisor) ; Fink, Jiří (referee)
A labeled embedding of a planar graph G is a pair (G, g) consisting of a planar drawing G of G and a function g assigning labels (colors) to the faces of G. We study the problem of Embedding Restriction Satisfiability (ERS) that investi- gates whether a given graph has a labeled embedding satisfying a provided set of conditions. ERS is a relatively new problem, so not much is known about it. Nevertheless, it has great potential. It generalizes several problems looking for a particular drawing of a planar graph, such as the problem of Partially Embedded Planarity. Therefore, ERS may become a focal point in the area of graph draw- ing. In this thesis, we examine the computational complexity of ERS. We show that ERS is NP-complete. After that, we look at the complexity of some specific classes of its instances. We try to locate the boundary between the NP-complete and the polynomial variants of the problem. 1
|
|
|
Worst case driver for Top trees
Ondráček, Lukáš ; Majerech, Vladan (advisor) ; Fink, Jiří (referee)
A top tree data structure solves one of the most general variants of a well- studied dynamic trees problem consisting in maintenance of a tree along with some aggregated information on paths or in individual trees, possibly in a mutable way, under operations of inserting and removing edges. It provides a simple interface separated from both an internal top tree structure representing a hierarchical partitioning of the graph, and a driver ensuring its depth to be logarithmic, which has a crucial role for the efficiency of the data structure. The driver proposed in this thesis is based on biased trees, combining techniques used in the worst-case version of link/cut trees and in the amortized driver for top trees: An input forest is decomposed into heavy paths and interleaving vertices, all of them being represented by biased trees connected together to form exactly the top tree structure. The driver is meant to be a more efficient alternative to the originally proposed one, and a comparably efficient alternative to the driver proposed by Werneck; there is a room for their experimental comparison.
|
guest ::
