DBPIA-NURIMEDIA

Size: px

Start display at page:

Download "DBPIA-NURIMEDIA"

현탁 좌
5 years ago
Views:

1 스마트폰사용자의이동경로및도착지예측을위한다중스위치은닉마코프모델 35 스마트폰사용자의이동경로및도착지예측을위한다중스위치은닉마코프모델 (Muliswich Hidden Markov Models for Roue and Desinaion Predicion of Mobile Phone Users) 이상우 허민오 (Sang-Woo Lee) 장병탁 (Min-Oh Heo) (Byoung-Tak Zhang) 요약기존에는다양한종류의스마트폰센서정보에서상위개념의사용자문맥을파악하기위하여위계적모델이흔히사용되었다. 그러나이러한위계적모델들은추론을하는데많은계산비용이소모되며, 그추론결과역시정확하지않다는단점을가지고있었다. 이러한제약을극복하기위해본논문에서는일반적인은닉마코프모델을확장한다중스위치은닉마코프모델 (mhmm) 을제안한다. mhmm 은이전관측치와현재관측치에동적패턴에따라전이행렬과관측행렬을결정하는다중스위치를가진다. 본논문에서는응용의예로, mhmm 을이동경로및도착지학습문제에적용하였다. 다양한모바일센서를성 이논문은 202년도정부 ( 교육과학기술부 ) 의재원으로한국연구재단의지원을받아수행된연구이며 (No , Videome), 정부 ( 지식경제부 ) 의재원으로한국산업기술평가관리원의지원 ( , mlife) 및교육과학기술부의 BK2-IT 프로그램에서일부지원되었음 이논문은제39회추계학술발표회에서 스마트폰사용자의이동경로및도착지예측을위한다중스위치은닉마코프모델 의제목으로발표된논문을확장한것임 학생회원 : 서울대학교컴퓨터공학부 slee@bi.snu.ac.kr moheo@bi.snu.ac.kr 종신회원 : 서울대학교컴퓨터공학부교수 bzhang@bi.snu.ac.kr (Corresponding auhor임 ) 논문접수 : 203년 2월 일심사완료 : 203년 4월 5일 CopyrighC203 한국정보과학회 ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 컴퓨팅의실제및레터제9권제6호 (203.6) 공적으로전처리하고 mhmm 으로관측치를깔끔하게표현함으로써, 주어진문제를위계적이지않은확률그래프모델로간단하게표현할수있었다. 본논문에서는제안된모델과다른모델을비교하여, 제안된모델이실제문제를해결하는데유용함을보이고자하였다. 키워드 : 스마트폰센서데이터, 행동인식, 이동경로예측문제, 다중스위치은닉마코프모델 Absrac Hierarchical models are effecive for inferring high-level conex from low-level sensory daa from mobile-phone users. However, hierarchical models in previous sudies are hard o capure abrup changes in sequenial observaions immediaely and exacly. Here we propose a hidden Markov model ha is augmened wih muliple swiches o capure and conrol he mode of he dynamical-sysem model based on he change ypes of saes. In conras o hierarchical models, he fla srucure of his muliswich HMM (mhmm) makes exac inference possible and achieves high predicion performance wihin he limiaion of real-ime compuaion. This compac represenaion could well work as we exploi heerogeneous mobile daa successfully. On a small-scale ye real-life smarphone experimens, we demonsrae he successful use of mhmm for predicing he poins of ineres (POIs) of he mobile users and compare is performance o he sandard HMM and he absrac HMM. Keywords: mobile smarphone sensor daa, aciviy recogniion, roue predicion problem, muliswich hidden Markov models. 서론 단순히 GPS 정보를넘어, 스마트폰의다양한센서들을사용하여개인화된사용자문맥을추론하기위한연구들이활발하게진행되고있다 []. 이러한다양한종류의센서정보에서상위개념의사용자문맥을파악하기위하여, 기존에는위계적모델이흔히사용되었다 [2,3]. 이러한모델들은문맥의추론을위하여주로파티클필터 ( 예컨대, Rao-Blackwellised 파티클필터 [4]) 를사용한다. 그러나이러한위계적모델은많은계산비용이소모되며그추론결과역시정확하지않다. 이러한단점을해결하기위하여, 본논문에서는일반적인은닉마코프모델 (hidden Markov model, HMM) 을확장한다중스위치은닉마코프모델 (muliswich hidden Markov models, mhmm) 을제안한다. mhmm 은이전관측치와현재관측치의값에따라전이행렬과관측행렬을결정하는다중스위치를가진다. mhmm은다중스위치를사용하여관측치들의동적패턴에따라추론방식을바꾸는방식을사용함으로써, 기존 HMM

352 정보과학회논문지 : 컴퓨팅의 실제 및 레터 제 9 권 제 6 호(203.6) 에 비하여 표현력을 확장했다. 본 논문에서는 모델의 응용의 예로, mhmm을 이동 경로 및 도착지 예측 문제에 적용하였다. 문제 해결을 위하여, 먼저 다양한 모바일 센서들을 전처리하여 의미 있는 상위 개념의 특징들로 만들었다.

2 Acion recogniion from low-level sensor daa 습과 추론을 수행하였다. 본 논문에서는 제안된 모델과 일반적인 HMM, 그리고 위계적 모델의 일종인 absrac 뀌었다. 이때, GPS값의 변화 속도를 반영하여 전처리 HMM(aHMM)[5]을 비교하여 그 성능을 비교하였다. 성능을 높였다.

2 352 정보과학회논문지 : 컴퓨팅의 실제 및 레터 제 9 권 제 6 호(203.6) 에 비하여 표현력을 확장했다. 본 논문에서는 모델의 응용의 예로, mhmm을 이동 경로 및 도착지 예측 문제에 적용하였다. 문제 해결을 위하여, 먼저 다양한 모바일 센서들을 전처리하여 의미 있는 상위 개념의 특징들로 만들었다. 예컨대, 가속도 센서를 포함한 다양한 센서들을 사용하여, 사용자가 어 떤 교통수단을 사용하여 움직이고 있는 지를 표현하는 이동 수단 을 기계학습 방법을 사용하여 추려내었다. 이 를 바탕으로, mhmm을 통해 위계적이지 않은 확률 그 그림 2 휴대폰 내 다양한 센서를 통한 교통수단 파악 래프 모델을 모델링하여 상위 개념의 특징들을 이용, 학 Fig. 2 Acion recogniion from low-level sensor daa 습과 추론을 수행하였다. 본 논문에서는 제안된 모델과 일반적인 HMM, 그리고 위계적 모델의 일종인 absrac 뀌었다. 이때, GPS값의 변화 속도를 반영하여 전처리 HMM(aHMM)[5]을 비교하여 그 성능을 비교하였다. 성능을 높였다. 다음으로는 그림 2에서 표현된 바와 같 이러한 결과를 바탕으로 제안된 모델이 실제 문제를 해 이 사용자가 어떤 교통수단을 사용하여 움직이고 있는 결하는 데 유용함을 보였다. 지를 표현하는 이동 수단 특징을 추출하였다. 본 실험에 서 이동 수단은 걷기, 뛰기, 버스, 지하철, 기타 의 2. 모바일 데이터와 전처리 총 5가지 상태 값을 가진다. 이동 수단 정보는 GPS, 가 이동 경로 및 도착지 예측 문제란 사용자의 과거와 속도 센서, 명암 정보, Wi-Fi 정보, 인접 도로 정보 등 현재 상태를 반영하는 시계열 관측치들을 받아 들여, 미 을 서포트 벡터 머신(SVM)이나 가우시안 혼합 모델 래에 사용자가 어느 도착지로 이동할 것인지, 그리고 어 (GMM) 등의 기계학습 방법을 통해 분류하여 얻을 수 떤 경로를 통하여 이동할 것인지를 예측하는 문제이다. 있다. 이에 대한 선행 연구 결과가 [6]에 소개되어 있다. 이동 경로 및 도착지 예측 문제를 해결하기 위하여 위에서 얻은 도로 정보와 이동 수단 정보를 이용하여 GPS, 소리 센서, 가속도 센서, Wi-Fi 센서, 시간 정보 이보다 더 상위의 추상화된 특징인 rip [7]이나 poin 등을 포함한 다양한 정보들을 사용하여 상위 개념의 특 of ineres(poi) [8]를 얻을 수 있다. Trip이란 이동 수 징들을 추출하였다. 먼저, 그림 에 표현된 바와 같이 단을 공유하는 일련의 도로 시계열 정보로 정의된다. 같이 실수 값의 GPS 정보들을 GIS 정보를 이용하여 POI는 사용자가 자주 찾는 clusering된 장소를 의미하 인접한 도로 정보에 사영시켰다. 이 과정을 통하여 GPS 며, 이동 경로 도착지의 후보가 된다. 이 외에 추론하는 정보는 도로의 인덱스 값을 가지는 이산화된 정보로 바 데 추가적으로 도움이 되는 요일대 정보나 시간대 정보 그림 GIS 정보를 통한 전처리 Fig. Discreizing of GPS daa using GIS informaion

3 스마트폰사용자의이동경로및도착지예측을위한다중스위치은닉마코프모델 353 그림 4 mhmm 의기본적인개념 Fig. 4 Concep of mhmm expressed in graphical model 그림 3 경로추론과도착지추론을위한전처리과정 Fig. 3 Preprocessing for Roue and Desinaion Inerface 등을추출한다. 앞에서설명한전처리에대한전체적인그림이그림 3에표현되어있다. 3. 다중스위치은닉마코프모델 3. 선행연구스위치를다루는 Dynamic Bayesian Neworks(DBN) 의배경이론에대해설명하면다음과같다. Swich를다루는 HMM 연구의좋은예로는 ahmm[5] 이있다. ahmm은 HHMM[9] 과유사한 hierarchical 모델이다. 다만, 그기본철학과스위치의정의가다소다르며, 이동경로및도착지예측문제에사용되었기에 [2] 본연구의방법과비교가능하다. 이모델은이전관측치가현재관측치에직접적인영향을미치지않는다는점에서본논문에서제안될 mhmm과차이가있다. 한편, 두관측치사이의관계를 HMM에서추론에직접적으로활용하는예로 auoregressive hidden Markov models [0] 를들수있다. 이모델은 auoregression 모델에은닉변수를추가하여추론에사용, 재생성성능을높였다. mhmm 역시이전관측치가이후관측치의확률에관여한다는점에서유사하지만, mhmm에서는 swich 를사용하여, 이전관측치의영향력을제한하고, 모델을간단하게만들었다. 3.2 다중스위치은닉마코프모델 mhmm은현재은닉변수 x, 현재관측치 y, 그리고이전관측치 y - 의함수에따라서전이행렬과관측행렬이변하는 HMM 모델로설명될수있다. 그림 4는 mhmm의기본아이디어를잘설명하고있다. 이러한기본아이디어를그림 5에표현된바와같이확률그래프모델로표현하였다. 이때확률그래프모델을수식으로표현하면다음과같다. px (, w, y x, y ) = p( y x, w, x, y ) p( x w, x, y ) p( w x, y ) = py ( w, x, y ) px ( w, x ) pw ( ) 이때, mhmm에서 py ( w, x, y ) 는다음과같 그림 5 확률그래프모델로표현한 mhmm Fig. 5 mhmm as graphical model 이정의된다. 여기서함수 는확률 p의대체함수이다. f ( x, y, y ) 는몇번째스위치에 x, y, y - 이할 당되는지를알려주는함수이며, 그출력값은스위치번호이다. py ( w, x, y ) = φ( y w, x) δ ( w, f( x, y, y )) 이때, 는항등함수를의미한다. mhmm 모델의특징중하나는현재관측치 y 에대한확률이 x, y, y - 의함수와스위치의항등함수에의해재정의되었다는것이다. 이론적으로스위치가각관측치종류마다한개혹은여러개씩부착될수있으며, 이를다중스위치라고부른다. 다중스위치 w 는관측값의변화에따라다른전이행렬과관측행렬을정의한다. 한편, 위의식에서다음식을얻어낼수있다. px (, y x, y ) = px (, w, y x, y ) w = φ( y w (), i x ) p( x w (), i x ) p( w ()) i s.. w() i = f( x, y, y ) 이를통해서현재까지의관측치를통한현재이동경로에대한확률을추론할수있으며다음과같다. px ( y ) px (, y y ) : : = x x px (, y x, y ) px ( y ) dx : = φ( y w ( i), x ) p( w ( i)) px ( w( i), x ) px ( y ) dx : 위의확률을통하여은닉변수의확률을근사적인방법없이모델에서표현한그대로추론하는 exac inference 가가능하다. 이모델을사용하기위해서는기본적으로스위치를사전에정의해야한다. 그외의 parameer들은학습이가능하다. 본모델을학습시키기위하여 Expec-

4 354 정보과학회논문지 : 컴퓨팅의실제및레터제 9 권제 6 호 (203.6) aion-maximizaion(em) 이사용가능하다. 이를위하여 Forward-Backward algorihm이사용될수있다. 3.3 이동경로및도착지추론문제를위한모델이동경로및도착지추론문제를풀기위해 mhmm 을확장하여모델을구성하였다. 확장된확률그래프모델은그림 6과같다. 그림 6에대해설명하면다음과같 y, y, z, z 이 다. 먼저, 모델의관측치입력으로 : T : T 사용되며, 각각이동도로시계열, 이동수단시계열, 요일대정보, 시간대정보를의미한다. 이동경로에서처 s 음지나가는이동도로 y 를통하여, 이동경로의시작점 sp를추론할수있으며, 역시모델의추론에사용된다. 이동경로및도착지추론문제는이동경로 x:t 와도착지 g 를추론하는문제이다. 이때, 이동경로와도착지의후보는앞에서언급한전처리방법이나그변형을통해얻어질수있다. 본 mhmm 모델링에서는임의의시간 에대하여다음문제를푸는문제로변환되었다. x = arg max px ( y, y, z, z) * : : : : x: g = arg max pg ( y, y, z, z) * : : : : g: T w w 는각각이동도로와이동수단 s a 다중스위치, s a, s s, y = y s s s s s w = 2, y = y & reverse( x, y, y ) s s s s 3, y = y & reverse( x, y, y ) y y 에대한스위치이며, 다음과같이사전에정의된다. a a, a y = y w = 2, oherwise s 여기서, reverse란 rip x 하에서관측치, s y y 이역방향으로이동하는지를나타내는사전에정의된함수이다. 그림 6 이동경로및도착지추론을위한 mhmm Fig. 6 Exended mhmm for roue and desinaion predicion 4. 실험결과앞에서설명한그림 6의모델을가지고진행한실험 seing과그결과에대해서술하면다음과같다. Daa 는한스마트폰유저실험자에게서얻은 23일동안얻은 5개의이동경로이다. 먼저이 daa를 raining se 와 es se 모두로서사용하여, mhmm과 ahmm을비교하였다. ahmm을실험하기위하여 auxiliary 파티클필터가사용되었으며, 파티클의개수는 000개를사용하였다. 한편, mhmm은 exac inference가사용되었다. 위계적모델에서는 layer의수에지승적으로 parameer 가증가하기때문에 exac inference를사용할수없었다. 실험결과는표 에소개되어있다. Bes.95 기준은추론시계열의 95% 지점에서실제도착점을 bes로예측하는지여부와관련된평가기준이며, No Faul 기준은실제도착점을예측하는확률이 % 이하가되는일이일어나는지와관련된평가기준이다. 실험결과에따르면, mhmm과달리 ahmm 은 raining se에대해서도종종정확한추론결과를내지못한다. 이를통해 mhmm이 ahmm보다더안정적인성능을보임을확인할수있다. ahmm이추론을잘해내지못하는이유중하나는, ahmm이파티클필터를사용할때 random walk 현상이일어나안정되지않은확률추론을하기때문이다. 즉, 추론공간이복잡한상황에서위계적모델인 ahmm이위계적이지않은 mhmm 보다이동경로및도착지추론에적합하지않을수있다. 한편, 단일시작지만으로도착지확률을추론했을때예측성능은 65%, 시작때의시간정보를추가했을때예측성능은 80% 였다. 이번에는앞에서설명한데이터를가지고 0-corss validaion을진행하여, mhmm과 HMM을비교하였다. 먼저 parameer를이동경로예측에대한 prior knowledge를적용하여 coun 기반으로만든후실험을수행하였다. 실험결과는그림 7에소개되어있다. HMM보다 mhmm이더좋은표현력을가지고있기때문에, mhmm이단순한 HMM보다더좋은예측성능을냄을확인할수있다. 또한그림 7에서알수있듯이, 단일시작지정보만으로도착지확률을추론했을때예측성능은 25%, 시작때의시간정보를사용했을동시에사용했을때예측성능은 40% 이다. 실험의타당성을보강하기위하여, 학습데이터를 38 일동안모은 09개의이동경로로확장하고, EM을사용하여 parameer를학습한뒤에 leave-one-ou 방법을통하여그성능을비교하였다. 이때 POI로 30개의지점을모았으며, 이는본문제가시작지점을제외한 29개의도착지후보중어느도착지로이동하고있는지를맞추는문제임을의미한다. 추가적인실험에서는

5 스마트폰사용자의이동경로및도착지예측을위한다중스위치은닉마코프모델 355 기힘들기때문에이동경로중간부근에서예측에실패하고있는것으로이해될수있다. 5. 결론본논문에서는이전관측치와현재관측치에따라전이확률과관측확률을변화시키는 mhmm을소개했으며, 이를스마트폰사용자의이동경로와도착지예측에사용하고다른모델과성능을비교하였다. 비록여기에소개된실험결과는매우초기의것이지만, 실험결과는 mhmm이타모델에비하여어떤장점을지니는지를보인다. 이론적으로는고차원의마코프관계나하이퍼그래프혹은위계적모델을사용하여 mhmm을확장하여표현력을확장할수있을것이다 [9]. 응용측면에서는 mhmm은다른추론문제, 예컨대, 스마트폰사용자의현재일상활동 ( 예컨대, 근무, 여가, 수면또는친교 ) 을추론하는문제에도사용될수있을것이다. 그림 7 0-cross validaion에서 HMM과 mhmm의성능비교. ( 왼쪽 ) 시간정보를사용한경우. ( 오른쪽 ) 시간정보를사용하지않은경우. x축은시계열의진행정도, y축은예측정확도이다. Fig. 7 Change of desinaion predicion rae wih wo models. Lef figure shows when ime informaion is no used. Righ figure shows when ime informaion is used 그림 8 daa가추가된 leave-one-ou 실험에서 HMM 과 mhmm의성능비교 Fig. 8 Change of desinaion predicion rae wih wo models 시간정보가사용되었다. 그림 8은 mhmm이 HMM보다우수한분류성능을내는것을보여준다. HMM보다 mhmm보다성능이좋은이유는 mhmm이스위치를통하여과거와현재관측치간의관계를잘표현하였기때문이다. 단순한 HMM 모델은현재사용자가이동하고있는방향을모델링하 참고문헌 [] N. D. Lane, E. Miluzzo, H. Lu, D. Peebles, T. Choudhury, A. T. Campbell, A Survey of Mobile Phone Sensing, IEEE Communcaions Magazine, 200. [2] L. Liao, D. J. Paerson, D. Fox, H. Kauz, Learning and Inferring Transporaion Rouines, Arificial Inelligence, [3] M.-O. Heo, M. Kang, B.-K. Lim, K.-B. Hwang, Y.-T., Park, and B.-T. Zhang,Real-ime roue inference and learning for smarphone users using probabilisic graphical models, Journal of he Korea Informaion Science Sociey: Sofware and Applicaions, 202. (in Korean) [4] A. Douce, N. Freias, K. Murphy, S. Russell, Rao-Blackwellised Paricle Filering for Dynamic Bayesian Neworks. Proceedings of he Conference on Uncerainy in Arificial Inelligence, [5] H. H. Bui, S. Venkaesh, G. Wes, Policy Recogniion in he Absrac Hidden Markov Model, Journal of Arificial Inelligence, [6] L. T. Vinh, S. Lee, H.X. Le, H.Q. Ngo, H. I. Kim, M. Han, Y.-K. Lee, Semi-Markov Condiional Random Fields for Acceleromeer-based Aciviy Recogniion, Applied Inelligence, 20. [7] J. Froehlich, J. Krumm, Roue Predicion from Trip Observaions, SAE Inernaional, [8] D. Ashbrook, T. Sarner, Using GPS o learn significan locaions and predic movemen across muliple users, Ubiquious Compuing, [9] S. Fine, Y. Singer, N. Tishby, The Hierarchical Hidden Markov Model: Analysis and Applicaions, Machine Learning, 998. [0] Y. Ephraim and W. J. J. Robers, Revisiing Auoregressive Hidden Markov Modeling of Speech Signals, IEEE Signal Processing Leers, 2005.

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA 다차원스트림데이터의온라인점진적학습을위한순차적예측모델 419 다차원스트림데이터의온라인점진적학습을위한순차적예측모델 (A Sequential Prediction Model for Online Incremental Learning of Mutidimensional Stream Data) 허민오 이상우 (Min-Oh Heo) 장병탁 (Sang-Woo Lee) (Byoung-Tak