서지주요정보
Optimization and learning of graphical models : a stochastic approximation approach = 그래프 모형 최적화와 그래프 모형 학습 알고리즘 : 확률론적 근사법에 따른 접근
서명 / 저자 Optimization and learning of graphical models : a stochastic approximation approach = 그래프 모형 최적화와 그래프 모형 학습 알고리즘 : 확률론적 근사법에 따른 접근 / Hyeryung Jang.
저자명 Jang, Hyeryung ; 장혜령
발행사항 [대전 : 한국과학기술원, 2017].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8031088

소장위치/청구기호

학술문화관(문화관) 보존서고

DEE 17027

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

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.

이 논문에서는 그래프 모형을 최적화하거나 학습하는 반복 알고리즘에 대해 연구하였다. 확률론적 근사법 이론에 기반하여, 주변 사용자로부터 얻는 지역적 정보만을 사용하면서도 정확한 해로 수렴하는 알고리즘을 제시하였다. 첫째로, 네트워크 사용자들의 의견 결정 현상을 그래프 모형을 이용해 수학적으로 모델링하고, 이들이 정보를 주고 받으며 의견 조정을 이룸으로써 발생하는 이득을 극대화하기 위한 분산 알고리즘들을 제시하였다. 구체적으로, 이는 유한한 횟수의 불완전한 마르코프 연쇄 샘플링을 사용하며, 확률론적 근사법에 기반하여 최적화 해로의 수렴성을 보장하기 위한 조건을 규명하고, 또한 게임이론에 근거한 새로운 해석을 제시하고 있다. 둘째로, 은닉 요소를 가진 그래프 모형의 변수를 학습하는 문제를 다루며, 정확한 변수로의 수렴성을 보장할 수 없었던 기존 연구들의 한계점을 해결할 수 있는 새로운 학습 알고리즘을 제시하였다. 구체적으로, 유한한 횟수의 마르코프 연쇄 샘플링을 서로 결합된 두 시간 척도에 적용하여 효율적으로 학습하며, 다 시간 척도를 다루는 확률론적 근사법에 기반하여 올바른 변수로의 수렴성을 증명하였다.

서지기타정보

서지기타정보
청구기호 {DEE 17027
형태사항 v, 89 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 장혜령
지도교수의 영문표기 : Yung Yi
지도교수의 한글표기 : 이융
공동지도교수의 영문표기 : Jinwoo Shin
공동지도교수의 한글표기 : 신진우
학위논문 학위논문(박사) - 한국과학기술원 : 전기및전자공학부,
서지주기 References : p. 80-86
주제 Graphical models
Distributed scheme
Parameter learning
Stochastic approximation theory
Optimization theory
그래프 모형
분산 알고리즘
파라미터 학습
확률론적 근사법
최적화 이론
QR CODE qr code