웹 기반 알고리즘 학습 튜터링 시스템

이승준(Seung-Jun Yi),안기현(Gi-Hyun An),윤소영(So-Yeong Yun),이상호(Sang-Ho Lee) 한국통신학회 2016 한국통신학회 학술대회논문집 Vol.2016 No.11

복잡계망 모델을 사용한 강화 학습 상태 공간의 효율적인 근사

이승준(Seung-Joon Yi),엄재홍(Jae-Hong Eom),장병탁(Byoung-Tak Zhang) 한국정보과학회 2009 정보과학회논문지 : 소프트웨어 및 응용 Vol.36 No.6

여러 가지 실세계 문제들은 마르코프 결정 문제(Markov decision problem) 들로 형식화하여 풀 수 있으나, 풀이 과정의 높은 계산 복잡도 때문에 실세계 문제들을 직접적으로 다루는 데 많은 어려움이 있다. 이를 해결하기 위해 많은 시간적 추상화(Temporal abstraction) 방법들이 제안되어 왔고 이를 자동화하기 위한 여러 방법들 또한 연구되어 왔으나, 이들 방법들은 명시적인 효율성 척도를 갖고 있지 않아 이론적인 성능 보장을 하지 못하는 문제가 있었다. 본 연구에서는 문제의 크기가 커지더라도 좋은 성능이 보장되는 자동적인 시간적 추상화 구현 방법에 대해 제안한다. 이를 위하여 네트워크 척도(Network measurements)를 이용하여 마르코프 결정 문제의 풀이 효율과 상태 궤적 그래프(State trajectory graph)의 위상 특성간의 관계를 분석하고, 네트워크 척도들 중 평균 측지 거리(Mean geodesic distance)가 마르코프 결정 문제의 풀이 성능과 밀접한 관계가 있다는 사실을 알아내었다. 이 사실을 기반으로 하여, 낮은 평균 측지 거리를 보장하는 복잡계망 모델(Complex network model)을 사용하여 시간적 추상화를 만들어 나가는 알고리즘을 제안한다. 제안된 알고리즘은 사실적인 3차원 게임 환경을 비롯한 여러 문제에 대해 테스트되었고, 문제 크기의 증가에도 불구하고 효율적인 풀이 성능을 보여 주었다. A number of temporal abstraction approaches have been suggested so far to handle the high computational complexity of Markov decision problems (MDPs). Although the structure of temporal abstraction can significantly affect the efficiency of solving the MDP, to our knowledge none of current temporal abstraction approaches explicitly consider the relationship between topology and efficiency. In this paper, we first show that a topological measurement from complex network literature, mean geodesic distance, can reflect the efficiency of solving MDP. Based on this, we build an incremental method to systematically build temporal abstractions using a network model that guarantees a small mean geodesic distance. We test our algorithm on a realistic 3D game environment, and experimental results show that our model has subpolynomial growth of mean geodesic distance according to problem size, which enables efficient solving of resulting MDP.

강화 학습을 사용한 동적 게임 환경에서의 빠른 경로 탐색

이승준(Seung Joon Yi),장병탁(Byoung Tak Zhang) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.1

연속적이고 동적인 실세계에서의 경로 탐색 문제는 이동 로봇 분야에서 주된 문제 중 하나였다. 최근 컴퓨터 성능이 크게 발전하면서 컴퓨터 게임들이 실제에 가까운 연속적인 3차원 환경 모델을 사용하기 시작하였고, 그에 따라 보다 복잡하고 동적인 환경 모델 하에서 경로 탐색을 할 수 있는 능력이 요구되고 있다. 강화 학습 기반의 경로 탐색 알고리즘인 평가치 반복(Value iteration) 알고리즘은 실시간 멀티에이전트 환경에 적합한 여러 장점들을 가지고 있으나, 문제가 커질수록 속도가 크게 느려진다는 단점을 가지고 있다. 본 논문에서는 연속적인 3차원 상황에서 빠르게 동적 변화에 적응할 수 있도록 하기 위하여 작은 세상 네트웍 모델을 사용한 환경 모델 및 경로 탐색 알고리즘을 제안한다. 3차원 게임 환경에서의 실험을 통해 제안된 알고리즘이 연속적이고 복잡한 실시간 환경 하에서 우수한 경로를 찾아낼 수 있으며, 환경의 변화가 관측될 경우 이에 빠르게 적응할 수 있음을 화인할 수 있었다.

복잡계 네트워크를 이용한 강화 학습 구현

이승준(Seungjoon yi),장병탁(Byoung-Tak Zhang) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.2Ⅰ

강화 학습(Reinforcement Learning)을 실제 문제에 적용하는 데 있어 가장 큰 문제는 차원성의 저주 (Curse of dimensionality) 이다. 문제가 커짐에 따라 목적을 이루기 위해서 더 많은 단계의 판단이 필요하고 이에 따라 문제의 해결이 지수적으로 어려워지게 된다. 이를 해결하기 위해 문제를 여러 단계로 나누어 단계별로 학습하는 계층적 강화 학습 (Hierarchical Reinforcement Learning) 이 제시된 바 있다. 하지만 대부분의 계층적 강화 학습 방법들은 사전에 문제의 구조를 아는 것을 전제로 하며 큰 사이즈의 문제를 간단히 표현할 방법을 제시하지 않는다. 따라서 이들 방법들도 실제적인 문제에 바로 적용하기에는 적합하지 않다. 이러한 문제점들을 해결하기 위해 복잡계 네트워크(Complex Network) 가 갖는 작은 세상 성질 (Small world property)에 착안하여 자기조직화하는 생장 네트워크(Self organizing growing network)를 기반으로 한 환경 표현 모델이 제안된 바 있다. 이러한 모델에서는 문제 크기가 커지더라도 네트워크의 사이즈가 크게 커지지 않기 때문에 문제의 난이도가 크기에 따라 크게 증가하지 많을 것을 기대할 수 있다.본 논문에서는 이러한 한경 모델을 사용한 강화 학습 알고리즘을 구현하고 실험을 통하여 각 모델이 강화 학습의 문제 사이즈에 따른 성능에 끼치는 영항에 대해 알아보았다.

복잡계의 위상특성을 이용한 MDP 학습의 효율 분석

이승준(Seung Joon Yi),장병탁(Byoung Tak Zhang) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.1

본 논문에서는 마르코프 결정 문제 (Markov decision problem)의 풀이 효율을 잴 수 있는 척도를 알아보기 위해 복잡계 네트워크 (complex network) 의 관점에서 MDP를 하나의 그래프로 나타내고, 그 그래프의 위상학적 성질들을 여러 네트워크 척도 (network measurements)들을 이용하여 측정하고 그 MDP의 풀이 효율과의 관계를 분석하였다. 실세계의 여러 문제들이 MDP로 표현될 수 있고, 모델이 알려진 경우에는 평가치 반복(value iteration)이나 모델이 알려지지 않은 경우에도 강화 학습(reinforcement learning) 알고리즘등을 사용하여 풀 수 있으나, 이들 알고리즘들은 시간 복잡도가 높아 크기가 큰 실세계 문제에 적용하기 쉽지 않다. 이 문제를 해결하기 위해 제안된 것이 MDP를 계층적으로 분할하거나, 여러 단계를 묶어서 수행하는 등의 시간적 추상화(temporal abstraction) 방법들이다. 시간적 추상화를 도입할 경우 MDP가 보다 효율적으로 풀리는 꼴로 바뀐다는 사실에 착안하여, MDP의 풀이 효율을 네트워크 척도를 이용하여 측정할 수 있는 여러 위상학적 성질들을 기반으로 분석하였다. 다양한 구조와 파라미터를 가진 MDP들을 사용해 네트워크 척도들과 MDP의 풀이 효율간의 관계를 분석해 본 결과, 네트워크 척도들 중 평균 측지 거리 (mean geodesic distance) 가 그 MDP의 풀이 효율을 결정하는 가장 중요한 기준이라는 사실을 알 수 있었다.

강화학습을 사용한 개인화된 웹 검색

이승준(Seung Joon Yi),장병탁(Byoung Tak Zhang) 한국지능시스템학회 2001 한국지능시스템학회 학술발표 논문집 Vol.11 No.2

복잡계 네트워크를 이용한 강화 학습에서의 환경 표현

이승준(Seungjoon Yi),장병탁(Byoung-Tak Zhang) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.1B

강화 학습(Reinforcement Learning)을 실제 문제에 적용하는 데 있어 가장 큰 문제는 차원성의 저주(Curse of dimensionality) 였다. 문제가 커짐에 따라 목적을 이루기 위해서 더 많은 단계의 판단이 필요 하고 이에 따라 문제의 해결이 지수적으로 어려워지게 된다. 이를 해결하기 위해 문제를 여러 단계로 나누어 단계별로 학습하는 계층적 강화 학습(Hierarchical Reinforcement Learning)이 제시된 바 있다. 하지만 대부분의 계층적 강화 학습 방법들은 사전에 문제의 구조를 아는 것을 전제로 하며 큰 사이즈의 문제를 간단히 표현할 방법을 제시하지 않는다. 따라서 이들 방법들도 실제적인 문제에 바로 적용하기에는 적합하지 않다. 최근 이루어진 복잡계 네트워크(Complex Network)에 대한 연구에 착안하여 본 논문은 자기조직화하는 생장 네트워크(Self organizing growing network) 를 기반으로 한 간단한 환경 표현 모델을 사용하는 강화 학습 알고리즘을 제안한다. 네트웍은 복잡계 네트웍이 갖는 성질들을 유지하도록 자기 조직화되고, 노드들 간의 거리는 작은 세상 성질(Small World Property)에 따라 전체 네트웍의 큰 사이즈에 비해 짧게 유지된다. 즉 판단해야할 단계의 수가 적게 유지되기 때문에 이 방법으로 차원성의 저주를 피할 수 있다.

마르코프 결정 프로세스의 위상적 계산 복잡도 척도

이승준(Seung-joon Yi),장병탁(Byoung-Tak Zhang) 한국정보과학회 2007 한국정보과학회 학술발표논문집 Vol.34 No.1C

실세계의 여러 문제들은 마르코프 결정 문제(Markov decision problem, MDP)로 표현될 수 있고, 이 MDP는 모델이 알려진 경우에는 평가치 반복(value iteration) 이나 모델이 알려지지 않은 경우에도 강화학습(reinforcement learning) 알고리즘 등을 사용하여 풀 수 있다. 하지만 이들 알고리즘들은 시간 복잡도가 높아 크기가 큰 실세계 문제에 적용하기 쉽지 않아, MDP를 계층적으로 분할하거나, 여러 단계를 묶어서 수행하는 등의 시간적 추상화(temporal abstraction) 방법이 제안되어 왔다. 이러한 시간적 추상화 방법들의 문제점으로는 시간적 추상화의 디자인에 따라 MDP의 풀이 성능이 크게 달라질 수 있으며, 많은 경우 사용자가 이 디자인을 직접 제공해야 한다는 것들이 있다. 최근 사용자의 간섭이 필요 없이 자동적으로 시간적 추상화를 만드는 방법들이 제안된 바 있으나, 이들 방법들 역시 결과 물에 대한 이론적인 성능 보장(performance guarantee)은 제공하지 못하고 있다. 본 연구에서는 이러한 문제점을 해결하기 위해 MDP의 구조와 그 풀이 성능을 연관짓는 복잡도 척도에 대해 살펴본다. 이를 위해 MDP로부터 얻은 상태 경로 그래프(state trajectory graph)의 위상적 성질들을 여러 네트워크 척도(network measurements) 들을 이용하여 측정하고, 이와 MDP의 풀이 성능과의 관계를 다양한 상황에 대해 실험적, 이론적으로 분석해 보았다.

다큐멘타리〈신의 아이들〉의 사례로 본 비상업영화의 보급현황과 대안에 관한 연구

이승준(Yi Seung Jun) 한국영화학회 2009 영화연구 Vol.0 No.39

Many people are talking about the crisis of Korean film industry. However as time goes on more and more non-commercial films are being made in Korea. Compared with 5 years ago, the number of films submitted to the Seoul Independent Film Festival - one of the biggest non-commercial film festivals in Korea - increased more than two times. The documentary Film <Children of god> was made from July 2007 to April 2008. It awarded at the Jeonju International film festival and invited to several film festivals. But it is not easy to regain production expenses and show to the general audience. Film festivals and non-commercial film support groups have been helpful in raising awareness for non-commercial films. In the mid 1990's many important non-commercial film festivals started in Korea. Every year, 700~800 short films were made in Korea. Aside from film festivals, TV and the internet became a distribution channel for short films. Some films shown at movie theaters were 'commercially' successful. There have ever been documentaries with an excellent box office record. More and more films are being made for movie theaters. Nowadays the space for non-commercial films have been broadened. People can watch short films through a few internet sites. As for documentary films, a new method of distribution has appeared. It's called 'community screening'. If there is a group or a organization who wants to show some films to it's members, the film will be shown to them in a public venue like district halls or local cinematheque, etc. It has been successful. Many non-commercial films are shown at movie theater, but most of them are not successful. Even though many films are shown at film festivals, after it is over the films begin to disappear. Most people do not even know the existence of the films and cannot easily find where to watch it. We need to distribute non-commercial films systematically. Above all we should not to forget the sprit of non-commercial films. non-commercial films exist not for making money, but for enriching the culture.

강화학습을 사용한 연관성 피드백

이승준(Seung Joon Yi),장병탁(Byoung Tak Zhang) 한국정보과학회 2002 한국정보과학회 학술발표논문집 Vol.29 No.1B

본 논문은 웹 문서 여과시 사용자 모델링을 위해 사용되는 연관성 피드백 방법을 강화 학습 프레임웍에서 분석하고 강화학습 기반의 새로운 연관성 피드백 알고리즘을 제안한다. 제안된 방법은 강화 학습 프레임웍상에서 기존의 방법을 일반화한 것으로 기존의 연관성 피드백 방법이 현재의 프로파일만을 상태로 사용하는 데 비해 과거 history부터 얻는 추가 정보를 사용하는 방법이다.