Hypothesis-free learning is increasingly popular given the large amounts of data becoming available. Structure learning, a hypothesis-free approach, of graphical models is a field of growing interest due to the power of such models and lack of domain knowledge when applied on complex real-world data. State-of-the-art techniques improve on scalability of structure learning, which is often characterized by a large problem space. Nonetheless, these techniques still suffer computational bottlenecks that are yet to be approached.
In this work, we focus on two popular models: dynamical linear systems and Markov random fields. For each case, we investigate major computational bottlenecks of baseline learning techniques. Next, we propose two frameworks that provide higher scalability using appropriate problem reformulation and efficient structure based heuristics. We perform experiments on synthetic and real data to validate our theoretical analysis. Current results show that we obtain a quality similar to expensive baseline techniques but with higher scalability. / Master of Science / Structure learning of graphical models is the process of understanding the interactions and influence between the variables of a given system. A few examples of such systems are road traffic systems, stock markets, and social networks. Learning the structure uncovers the invisible inter-variables relationships that govern their evolution. This process is key to qualitative analysis and forecasting. A classic approach to obtain the structure is through domain experts. For example, a financial expert could draw a graphical structure that encodes the relationships between different software companies based on his knowledge in the field. However, the absence of domain experts in the case of complex and heterogeneous systems has been a great motivation for the field of data driven, hypothesis free structure learning. Current techniques produce good results but unfortunately require a high computational cost and are often slow to execute.
In this work, we focus on two popular graphical models that require computationally expensive structure learning methods. We first propose theoretical analysis of the high computational cost of current techniques. Next, we propose a novel approach for each model. Our proposed methods perform structure learning faster than baseline methods and provide a higher scalability to systems of large number of variables and large datasets as shown in our theoretical analysis and experimental results.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/86263 |
| Date | 14 June 2017 |
| Creators | Chaabene, Walid |
| Contributors | Computer Science, Huang, Bert, Gugercin, Serkan, Zhang, Liqing |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Thesis |
| Format | ETD, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
Page generated in 0.002 seconds