Optimization and learning of graphical models : a stochastic approximation approach = 그래프 모형 최적화와 그래프 모형 학습 알고리즘 : 확률론적 근사법에 따른 접근 a stochastic approximation approach

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 182
  • Download : 0
This thesis studies the problem of optimization and learning in graphical models via stochastic approximation theory. First, in various multi-agent networked environments, the system can benefit from coordinating actions of two interacting agents at some cost of coordination, where a primary goal is to develop a distributed algorithm maximizing the coordination effect. Such pairwise coordinations and nodewise costs in the network can be captured by graphical model framework, which becomes the problem of finding the optimal graph parameter. We propose various distributed algorithms that require only one-hop message passing, which can be interpreted based on either Lagrange duality theory or game theory framework. Our algorithms are motivated by a stochastic approximation method that runs a Markov chain incompletely over time, but provably guarantees the convergence to the optimal solution. In machine learning field, for the problem of parameter learning in graphical models having latent variables, the standard approach, i.e., EM algorithm, is computationally intractable for high dimensional graphs in both E and M steps. Since the substitution of one step to a faster surrogate for combating against intractability can often cause failure in convergence, we propose a new learning algorithm which is computationally efficient and provably ensures convergence to a correct optimum via multi-time-scale stochastic approximation theory, where its key idea is to run only a few cycles of Markov chain in both steps. We demonstrate our theoretical findings through extensive simulations with synthetic data and/or real-world datasets.
Advisors
Yi, Yungresearcher이융researcherShin, Jinwooresearcher신진우researcher
Description
한국과학기술원 :전기및전자공학부,
Publisher
한국과학기술원
Issue Date
2017
Identifier
325007
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 전기및전자공학부, 2017.2,[v, 89 p. :]

Keywords

Graphical models; Distributed scheme; Parameter learning; Stochastic approximation theory; Optimization theory; 그래프 모형; 분산 알고리즘; 파라미터 학습; 확률론적 근사법; 최적화 이론

URI
http://hdl.handle.net/10203/242025
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=675823&flag=dissertation
Appears in Collection
EE-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0