ISSN 2383-6318(Print) / ISSN 2383-6326(Online) KIISE Transactions on Computing Practices, Vol. 23, No. 10, pp. 599-604, 2017. 10 https://doi.org/10.5626/ktcp.2017.23.10.599 강건한스케줄링을위한마코프의사결정프로세스추론및역강화학습기반일상행동학습 (Robust Scheduling based on Daily Activity Learning by using Markov Decision Process and Inverse Reinforcement Learning) 이상우 곽동현 온경운 허유정 (Sang-Woo Lee) (Dong-Hyun Kwak) (Kyoung-Woon On) (Yujung Heo) 강우영 재이다 장병탁 (Wooyoung Kang) (Ceyda Cinarel) (Byoung-Tak Zhang) 요약유저의일상스케쥴을제안하고예측하는서비스는스마트비서의흥미로운응용이다. 전통적인방법에서는유저의행동을예측하기위하여, 유저가직접자신의행동을기록하거나, e-mail 혹은 SNS 등에서명시적인일정정보를추출하여사용해왔다. 하지만, 유저가모든정보를기록할수없기에, 스마트비서가얻을수있는정보는제한적이며, 유저는유저의일상의 routine 한정보를기록하지않는경향이있다. 본논문에서는스케줄러에적히는정형화된일정인스케줄과비정형화된일정을만드는일상행동패턴들을동시에고려하는접근방법을제안한다. 이를위하여마코프의사결정프로세스 (MDP) 를기반으로하는추론방법과역강화학습 (IRL) 을통한보상함수학습방법을제안한다. 실험결과는우리가 6 주간모은실제생활을기록한데이터셋에서우리의방법이기존방법들보다우수한성능을보임을논증한다. 키워드 : 일정관리, 마코프의사결정프로세스, 역강화학습, 웨어러블디바이스 Abstract A useful application of smart assistants is to predict and suggest users daily behaviors the way real assistants do. Conventional methods to predict behavior have mainly used explicit schedule information logged by a user or extracted from e-mail or SNS data. However, gathering explicit information for smart assistants has limitations, and much of a user s routine behavior is not 본연구는과학기술정보통신부의재원으로정보통신기술진흥센터 (R0126-16- 1072-SW 스타랩 ), 한국산업기술평가관리원 (10044009-HRI.MESSI, 10060086- RISF) 의지원을받았음 이논문은제43회동계학술발표회에서 강건한스케줄링을위한마코프의사결정프로세스추론및역강화학습기반일상행동학습 의제목으로발표된논문을확장한것임 학생회원 : 서울대학교컴퓨터공학부 slee@bi.snu.ac.kr 비회원 : 서울대학교뇌과학협동과정 dhkwak@bi.snu.ac.kr 비회원 : 서울대학교컴퓨터공학부 kwon@bi.snu.ac.kr yjheo@bi.snu.ac.kr 학생회원 : 서울대학교컴퓨터공학부 wykang@bi.snu.ac.kr ceyda@bi.snu.ac.kr 종신회원 : 서울대학교컴퓨터공학부교수 (Seoul Nat'l Univ.) btzhang@bi.snu.ac.kr (Corresponding author임 ) 논문접수 : 2017년 3월 8일 (Received 8 March 2017) 논문수정 : 2017년 6월 14일 (Revised 14 June 2017) 심사완료 : 2017년 7월 29일 (Accepted 29 July 2017) CopyrightC2017 한국정보과학회ː 개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회컴퓨팅의실제논문지제23권제10호 (2017. 10)
600 정보과학회컴퓨팅의실제논문지제 23 권제 10 호 (2017. 10) logged in the first place. In this paper, we suggest a novel approach that combines explicit schedule information with patterns of routine behavior. We propose using inference based on a Markov decision process and learning with a reward function based on inverse reinforcement learning. The results of our experiment shows that the proposed method outperforms comparable models on a life-log dataset collected over six weeks. Keywords: schedule planning, markov decision process, inverse reinforcement learning, wearable devices 1. 서론우리는구글글래스와같은웨어러블기기상의스마트비서가스케줄링을하는문제에관심이있다. 스마트비서가스케줄러에들어있는스케줄뿐아니라, 일상의다양한행동패턴들을참고하여, 유저의삶을예측하고또한제안하는것은스마트비서의흥미로운응용이다 [1]. 기존상용화된스마트비서의스케줄링방법은스케줄러나예약정보등을통하여얻을수있는명시적인일정을중심으로한다. 예컨대, Google Now는호텔예약, 비행기정보, Gmail 등에서찾을수있는명시적스케줄과, GPS 정보를이용하여찾을수있는현재위치정보등을이용하여일정관리를해준다. 그러나스케줄러에미리적혀있는정보, 혹은그에준하는정보에따라서만추론이가능하며, 특별히일상적인행동패턴을고려하는데에는한계가있다. 역으로일상행동패턴을기반하여하루일과를예측하는하는방법도있다. 이방법은평소에갔던곳들을참고하여추론하는것으로, 스마트폰이나웨어러블기기등에기반하여장소및행동패턴을수집, 예측에사용한다. 일상행동패턴을바탕으로하루일과를예측하는데있어, 다양한기계학습모델이사용될수있다. 그중한부류로일련의장소및행동을하나의확률벡터로보고확률그래프모델 (probabilistic graphical model, PGM) 을이용하여예측하는방법이있다. 예컨대, 이전연구중하나에서는사람들의이동정보를스마트폰으로수집한뒤에, 그정보들을바탕으로주성분분석 (principle component analysis, PCA) 을수행, 핵심적인성분들을바탕으로스마트폰사용자들의이동궤적에대한성능을높였다 [2]. 하지만이렇게일상행동을정적인확률벡터로보는경우, 데이터의동적인패턴을파악하는데에어려움이있다. 대안이되는부류로동적모델을사용하여일상행동을예측하는방법이있다. 예컨대, 이전연구중하나에서는, 자동차이동정보를예측하는시스템을위하여 recurrent neural network - restricted Boltzmann machine (RNN-RBM) 모델을사용하였다 [3]. 이러한방법은동적인유저행동을잘모사할수있지만, 예측의범위가길어지면, 오류가누적되면서불안정한예측을하게된다는단점이있다. 우리는스케줄러에기록되는정형화된스케줄과일상행동패턴에따라나타나는비정형화된스케줄을동시에고려하기위하여마코프의사결정프로세스 (MDP) 추론세팅을제안한다. 이는스케줄러의스케줄과일상행동패턴각각에보상 (reward) 값을부여하는것이다. 그뒤에, 유저가보상값을최대화하는방향으로이동하거나, 혹은이동해야한다고가정하고, 그에맞게예측혹은스케줄링을하는것이다. 특별히우리는보상함수학습을위하여역강화학습 (IRL) 을활용한다. 역강화학습은강화학습과반대되는개념으로, 강화학습은보상 (reward) 함수가주어지면, 이를바탕으로최적행동을야기하는정책 (policy) 를찾는다 [4]. 반면, 역강화학습은유저의행동들을바탕으로유저에게주어진보상함수를추정한다. 우리는스케줄링을위하여특수하게고안된 MDP와역강화학습방법을제안하고사용한다. 우리의방법은 MDP를적절히사용함으로써, 정적인보상함수패턴으로부터동적인일상행동패턴을안정적으로얻어낼수있다. 본논문에서는먼저, 본실험에사용되는방법론과실험세팅에대해소개하고초기실험결과를보인다. 그뒤에웨어러블디바이스에기반한전체스케줄링프레임워크에대해설명한다. 그후제안한스케쥴링프레임워크의옹호론과반대론, 그리고후속연구에대해기술한다. 2. 데이터수집방법우리는웨어러블기기기반스케줄링을실험및데모하기위하여데이터를수집하고있다. 크게보면, 다음네가지종류의데이터를수집한다. 1) 10초간격으로웨어러블카메라 narrative clip을통하여수집되는이미지. 2) 스마트폰에서수집되는 GPS. 3) 10분간격으로피험자가기록하는장소와행동정보. 4) 피험자의일정정보와 SMS, e-mail text 정보. 실제일정중에서 mail이나 SNS로확인할수있는공식적인일정만이스케줄러에기록되며, 그렇지않은일정들은기록되지않는다. 또한비정기적인미팅이나근무활동, 여가활동과같은일상적인행동은역시그날행동으로는기록되나그날일정으로서는기록되지않는다.
강건한스케줄링을위한마코프의사결정프로세스추론및역강화학습기반일상행동학습 601 피험자는한명으로, 6주간의장소, 행동, 일정, GPS 정보를수집했다. 또한 narrative clip으로 6주간, 1384760초의이미지정보를수집하였다. 본실험에서는이중피험자가기록한장소와행동정보및일정정보가사용된다. 후속연구에서는실제웨어러블기기를사용하는상황을가정하여, 전체데이터를가지고학습되는방법이실험될것이다. 3. 스케줄링실험세팅본논문에서는그날의일부일정들이알려진상황에서, 유저의기존이동및행동패턴들을반영하여그날하루동안언제어느장소로이동할지를예측하는문제를다루고, 이것을스케줄링이라는단어로기술한다. 그림 1은본논문에서다루는문제를설명하고있다. 본논문에서는스케줄링의추론, 즉그날의하루일과를예측하는일을위하여특수한 MDP 세팅과이를최적화하는알고리즘을제안한다. 실험세팅에서는 10분단위로나뉘는시간 t, 장소 s, 일정 c, 행동 b를생각하자. 그리고, 각장소 s와각시간 t에서얻을수있는보상함수 R(s,t) 와장소 s에서다른장소 s 로이동하는데드는시간 D(s,s ) 를알고있다고가정하자. 일반적으로 R(s,t) 보다 D(s,s ) 가획득하기쉬운데, D(s,s ) 는예컨대지도어플리케이션을사용하여획득할수있는정보이다. 우리의목표함수는스케줄링종료시점 T까지의장소 S 1:T 에대하여다음과같이정의된다. obj ( s ) = = R( s, t) infer 1: t t 1 t T 위목표함수를최적화하기위하여, 각 s와 t에대하여 t 시점이후에얻을수있는예상 reward의최대기대치인누적보상 V(s t, t) 를정의할수있다. 즉, V는보상함수 R이존재할때 T 시점까지최대로얻을수있는보상값의합이다. V가있으면최적경로 S 1:T 를얻을수있다. 이동에패널티에해당하는보상 -p를얻게된다고가정하자. 이경우 V는다음과같이계산된다. V( s, t) = max [ D( s, s') p+ V( s )] + R( s, t) t s' t+ D( s, s') t 우리는보상함수 R(s,t) 를얻기위하여각각의일정과장소, 행동에대하여얻을수있는보상값 w를학습한다. 이러한학습은역강화학습의일종으로이해될수있다. w를학습하기위하여현재까지학습된전체 R 에대한최적장소 trajectory 1:T 와실제장소 trajectory 1:T 를일치하게하는목적함수를설정한다. obj ( s ) = δ ( sˆ, s ) traom 1: T t= 1 t t 여기서델타함수 는두값이같은지를비교한다. t 는 w에대한함수로서이해될수있다. 현재우리는목표함수의최적값을찾기위하여 naïve한 grid search를사용하고있다. 그림 2는앞의 42일동안의데이터를사용하여, 이동장소를예측하는초기실험결과를보여주고있다. Behavior pattern based는피험자의행동패턴의확률을기반으로예측하는모델이고, Scheduler based는스케줄정보를기반으로예측하는모델이며, Scheduler + human s rule은스케줄정보기반모델에피험자가생각하는일상룰을반영하여예측하는모델이다. T 그림 1 스케줄링문제세팅의도식 Fig. 1 Illustration of our scheduling prediction problem
602 정보과학회컴퓨팅의실제논문지제 23 권제 10 호 (2017. 10) 의예측모델에비해좋은성능이보이는것을확인할수있다. 심지어사람이휴리스틱룰을추가하여, 스케쥴기반의예측과혼용하는방법과비교하여도, 제안된방법이시간이지남에따라, 성능에서더앞서나감을확인할수있다. 본절에서는일상행동패턴을확률모델을기반으로모델링하여예측한경우와앞서설명된방법론을바탕으로추론한경우를비교하였다. 이실험은강화학습및역강화학습기반의추론이중요함을논증하기위하여실험되었다. 4. 웨어러블디바이스기반일정자동관리시스템 그림 2 실험결과. x축은날짜, y축은위쪽은정확도. 아래쪽은누적정확도 Fig. 2 Experimental results. x-axis denotes days and y-axis denotes accuracy (top) and accumulated accuracy (bottom) 실험결과를보면, 시간이지남에따라제안한모델의성능이개선되며, 일상패턴의확률모델, 스케쥴기반 우리는앞에서설명된일정예측시스템을확장하여웨어러블디바이스기반일정자동관리시스템을구축하는것을목표로한다. 우리의시스템에대한도식이그림 3에있다. 논문의방법및실험결과와비교하여추가되는내용은다음과같다. 첫째, GPS와이미지스트림으로부터장소와행동을자동으로추출하는알고리즘 [5]. 둘째, 이러한장소와행동을반감독학습및무감독학습으로분석하는알고리즘. 셋째, e-mail과 SNS를기반하여일정을신뢰도있게추론하는알고리즘. 넷째, 장소행동에따른지식추론을실시간으로끊임없이할수있는알고리즘 [6]. 다섯번째, 더일반적인일상행동및보상함수패턴을학습할수있는 MDP. 여섯번째, 더일반적인형태의보상함수를학습하기위한보상학습구조학습. 일곱번째, 추가일정요청에대하여, 자동으로추가일정의구체적시간을추천하고조율하는시스템. 우리는또한예측된일정들을자동으로보여주는시스템을구축하는것을후속연구로계획하고있다. 다양한방법을통하여모델이예측한일정을유저에게보여줄수있으며, 그예로챗봇기반의대화시스템, 지도에일 그림 3 웨어러블센서디바이스기반일정및자동관리방법의전체시스템에대한도식 Fig. 3 System illustration on automatic schedule prediction and recommendation system based on wearable device
강건한스케줄링을위한마코프의사결정프로세스추론및역강화학습기반일상행동학습 603 그림 4 예측된스케쥴을정리하여보여주는시스템의도식 Fig. 4 Illustration on schedule visualizer for the predicted schedule 정을표시하는시스템혹은일련의그림을통하여일정을보여주는시스템이있다. 그림 4는예측된일정을자동으로보여주는시스템에대한예시를나타내고있다. 그림 4의왼쪽은구글지도앱에예측된하루일과를보여주는시스템. 오른쪽은과거에찍었던사진들의나열을통하여예측된하루일과를표현하는시스템이다. 5. 후속연구및논의 본논문은웨어러블스케줄링을위한초기연구경과를소개하고있다. 궁극적으로는우리는웨어러블센서스트림만으로장소와행동, 동적행동패턴, 그리고각유저의동기를실시간으로추출하는알고리즘을만드는것을목표로한다. 이는기존에웨어러블센서로상황을클러스터링하는연구의확장이된다 [7]. 마지막으로프레임워크자체에대한유용성에대해논한다. 일상행동을학습하는프레임워크에대하여스케줄링은다양한일정을가지고있는사람이아니면불필요하다는지적이있을수있다. 스케줄링은유저의기억을보조하는역할로사용되는것이지, 불확실성이있는예측은서비스에사용되기어렵다는것이다. 하지만모든일정이기록될수있는것은아니기에, 본프레임워크는좀더유연한일정관리를해줄수있다는장점이있다. 또한, 불확실성을감안하는여행일정제공및실시간으로변화하는상황에따른추천스케줄링의경우, 효율적으로사용될수있을것으로보여진다. 다른한편으로는예측성능을높일수있으므로, 장소예측과관련된추천서비스의성능향상에도활용될수있다. References [1] V. Pejovic and M. Musolesi, "Anticipatory Mobile Computing: A Survey of the State of the Art and Research Challenges," ACM Computing Serveys, Vol. 47, No. 3, 2015. [2] A. Sadilek and J. Krumm, "Far Out: Predicting Long-Term Human Mobility," Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012. [3] X. Ma, H. Yu, Y. Wang, and Y. Wang, "Large-scale transportation network congestion evolution prediction using deep learning theory," PloS one, Vol. 10, No. 3, 2015. [4] A. Y. Ng and S. Russell, "Algorithm for Inverse Reinforcement Learning," Proceedings of the Seventeenth International Conference on Machine Learning, 2000. [5] D. Castro, S. Hickson, V. Bettadapura, E. Thomaz, G. Abowd, H. Christensen, and I. Essa, "Predicting Daily Activities From Egocentric Images Using Deep Learning," proceedings of the 2015 ACM International symposium on Wearable Computers, 2015. [ 6 ] S.-W. Lee, C.-Y. Lee, D.-H. Kwak, J.-W. Ha, J. Kim, and B.-T. Zhang, "Dual-memory neural networks for modeling cognitive activities of humans via wearable sensors," Neural Networks, Vol. 92, 2017. [7] T. Huynh, M. Fritz, and B. Schiele, "Discovery of Activity Patterns using Topic Models," Proceedings of the 10th international conference on Ubiquitous computing, 2008. 이상우 2012년서울대학교컴퓨터공학부학사 2012년~현재서울대학교컴퓨터공학부석박사통합과정. 관심분야는딥러닝, 베이지안, 평생학습, 멀티모달, 질의응답, 대화시스템
604 정보과학회컴퓨팅의실제논문지제 23 권제 10 호 (2017. 10) 곽동현 2014 년서강대학교컴퓨터과학 & 생명과학과학사. 2017 년서울대학교협동과정뇌과학박사과정수료. 2017 년 ~ 현재네이버서치솔루션에서전문연구요원으로딥러닝기반 QA 시스템연구개발중 온경운 정보과학회컴퓨팅의실제논문지제 23 권제 2 호참조 허유정 2015 년인하대학교컴퓨터공학 &IT 경영학과학사. 2015 년 ~ 현재서울대학교컴퓨터공학부석박사통합과정. 관심분야는인공신경망, 기계학습, 컴퓨터비전 강우영 2014 년전북대학교컴퓨터공학부학사 2017 년서울대학교컴퓨터공학부석사 2017 년 ~ 현재써로마인드로보틱스주임연구원재직. 관심분야는인공지능, 기계학습, 영상처리, 온라인러닝 재이다 2015 년 TOBB University Of Economics And Technology, Turkey 학사. 2015 년 ~ 현재서울대학교컴퓨터공학부석사과정관심분야는딥러닝, 컴퓨터비전, 자연어처리 장병탁정보과학회컴퓨팅의실제논문지제 23 권제 2 호참조