다차원스트림데이터의온라인점진적학습을위한순차적예측모델 419 다차원스트림데이터의온라인점진적학습을위한순차적예측모델 (A Sequential Prediction Model for Online Incremental Learning of Mutidimensional Stream Data) 허민오 이상우 (Min-Oh Heo) 장병탁 (Sang-Woo Lee) (Byoung-Tak Zhang) 요약실생활속에서존재하는다양한센서데이터스트림은실시간으로끊임없이유입되면서도장기적으로분포가변할수있는특성을지닌다. 이러한데이터의학습에는점진적인학습을수행하면서도동시에순차적예측이가능한모델을필요로한다. 이에따라, 본고에서는다차원스트림데이터를위한시계열예측을다루는새로운모델을제안한다. 이모델은순차적인정보를지닌패턴들의집합과해당패턴들이나타난빈도를이용하여표현되며, 이를기반으로시계열예측을수행한다. 본모델의타당성을평가하기위해, 분포를아는문자서열을생성하여조건부확률분포가학습됨을보였다. 또한, 스마트폰내 GPS 센서를이용하여수집한실제사용자의이동데이터를이산화하여이제까지이동해온도로를통해다음에이동할도로를예측하는문제를해결하고, 그분석결과를통해본모델의 본연구는 2012년도정부 ( 산업통상자원부 ) 의재원으로한국산업기술평가원지원으로수행된연구이며 (KEIT-10035348, mlife), 한국연구재단의지원 (NRF-2010-0017734-Videome, NRF-2013M3B5A2035921-HyperIntelligence) 및 BK21-IT 프로그램에서일부지원되었음 이논문은제39회추계학술발표회에서 다차원스트림데이터의온라인점진적학습을위한순차적예측모델 의제목으로발표된논문을확장한것임 학생회원 : 서울대학교컴퓨터공학부 moheo@bi.snu.ac.kr slee@bi.snu.ac.kr 종신회원 : 서울대학교컴퓨터공학부교수 btzhang@bi.snu.ac.kr (Corresponding author임 ) 논문접수 : 2013년 2월 7일심사완료 : 2013년 5월 10일 CopyrightC2013 한국정보과학회 ː개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회논문지 : 컴퓨팅의실제및레터제19권제8호 (2013.8) 특성을실험적으로확인하였다. 키워드 : 데이터스트림, 온라인점진학습, 순차적예측, 스마트폰센서데이터 Abstract Data streams from real-world sensors inherently have features of open-ended inflow and of changeable distribution in the long term (e.g., concept drift). To learn these data, we need sequential prediction models learnable online incrementally. Here, we propose novel models for multidimensional time-series data stream. The models are represented with a set of sequential patterns and the corresponding frequencies, and perform probabilistic sequential prediction tasks based on them. As model regularization, the maximum number of patterns is able to be limited. To validate the learning methods, we show that they successfully learn conditional distributions with random generated strings. Moreover, next-position prediction task also performed using street sequences from GPS sensors embedded in smartphones. From them, we validate the characteristics of the model experimentally. Keywords: data stream, online incremental learning, sequential prediction, smartphone sensor data 1. 서론 최근스마트폰과같이실생활속에쉽게다양한센서데이터를제공하는기기가나타남에따라, 실시간으로끊임없이유입되면서도장기적으로분포가변할수있는데이터가늘어나고있다 [1]. 전통적인시계열형태의순차적데이터모델링기법은오프라인학습이주로사용되었으며, 장기적인변화를다루기위해서는긴기간의데이터수집이불가피하였다 [2-4]. 즉, 한번확보하였던데이터를이용하여모델을구축한후, 문제해결에활용하는방식을주로취해왔다. 흔히사용하는시계열데이터모델링방법으로재귀적뉴럴네트워크 (recurrent neural network (RNN))[2], 은닉마코프모델 (hidden Markov model (HMM))[3] 이사용되는데, 주로단기적인패턴학습에사용된다. 특히, HMM과같이모델에마코프가정을적용하였을경우, 이전시간의값에따라현재값이결정된다. 끊임없이유입되는데이터, 즉, 스트림데이터를학습하기위해서는오프라인형태가아니라, 시간의흐름에따라함께학습을수행하는온라인학습 (online learning) 이가능해야한다 [5]. 장기적관점에서사용자의환경변화에영향을받아유입되는데이터의분포가변할경우에도지속적인학습을통해 concept drift를다룰수있어야함을의미한다 [6,7]. 또한, 이러한과정을지속적으로수행하면서도사용자의요청에따라현재모델을
420 정보과학회논문지 : 컴퓨팅의실제및레터제 19 권제 8 호 (2013.8) 이용하여추론하는것이가능해야한다. 즉, 스트림데이터를이용하여점진적인온라인학습을수행하면서도동시에순차적예측이가능한모델이요구되고있다. 본고에서는스트림데이터를위한시계열예측을다루는새로운모델을제안한다. 이모델은순차적인정보를나타내는패턴들의집합과해당패턴들이나타난빈도를모델로서가지고있으며, 이를기반으로시계열예측을시도한다. 점진적인온라인학습은데이터가유입되는매시점마다등장한패턴의빈도를늘리는것으로단순하게진행되며, 유입된데이터와비교하여정보가부족하거나수정이필요하다고판단될경우, 패턴집합내에새로운패턴을추가하거나수정 / 삭제를수행한다. 이후, 본논문은다음과같이구성된다. 2장에서는다루려는순차적예측문제를설명하고, 3장에서스트림데이터의점진적온라인학습을위한모델과학습및추론방법을소개한다. 4장에서는실험을통해모델의적용예를보인후, 5장에서결론을맺는다. 3. 모델표현과학습및추론방법앞에서설명한순차적예측문제를다룰수있으면서도점진적으로온라인학습을수행하기위하여, 스트림데이터를패턴집합과그빈도로바꾸어표현하는모델을도입한다. 이모델에서는최근스트림데이터에서나타난순차적패턴의빈도를갱신하는것으로학습을수행하며, 존재하지않는패턴이나타날경우에는패턴집합에새로이추가한다. 또한, 패턴이무한히늘어나는것을막기위해오랫동안사용되지않으면패턴이삭제되도록한다. 추론과정으로서, 어떤시점에사용자가특정입력이주어졌을때 n 시간이후나타날값이무엇일지예측하는문제에대한답을하기위하여, 이모델로부터사후확률을구하고최대확률에해당되는값을출력하는것으로요약할수있다. 그림 1에학습, 추론과정을간략히나타내었다. 2. 스트림상에서의순차적예측문제 순차적예측문제는최근 k 개의이산변수에대한입력이주어졌을때, 바로다음단계또는 n 단계후의입력이무엇일지예측하는문제로서, 다음과같이표현된다. xˆ = arg max P( X = x X ) (1) t+ n t+ n t k: t x 여기서, n 과 k 는임의의양의정수이다. 여기서, n 이 1이고시계열길이전체가조건으로주어질경우 ( 즉, k = t-1) 에는전통적인 filtering 문제이며, n 이 0보다큰경우에는 prediction 문제이다. 이러한문제를다루는일반적인접근방법은식 (1) 에서관심대상인 n 과 k 를결정하고, 시계열데이터의조건부확률분포를학습하여확률이최대가되는값을구하는방법이다. 특히, filtering 문제에대한대표적모델로는은닉마코프모델 (HMM) 이있다 [3]. 하지만, 이러한방법론은기본적으로스트림상의확률분포가변하지않는다는가정을가지고있으며, concept drift와같이스트림상의분포가변하는것을다루는모델로는적합하지않다. 본고에서는전체입력길이보다작은임의의정수 k 가주어진경우에대하여, 순차적예측문제를다루고자한다. 또한, 스트림데이터의특성상실시간으로유입되는형태를가지므로, 학습및추론과정이점진적이어야하며, 온라인학습이가능해야한다 [8]. 즉, 학습및추론에필요한계산비용이크지않아야한다. 이러한특성을고려하여순차적예측을수행하는방법을다음장에서소개한다. 그림 1 제안방법의기능개요도 Fig. 1 Overall functional structure of the proposed methods 3.1 모델정의앞에서간략히설명한모델을엄밀히정의한다. 모델 M=<H, w> 은패턴의집합 H 와패턴의빈도 w 의쌍으로정의된다. H 는임의의순차적패턴 E 를원소로갖는색인된집합이며, i 번째패턴을 E i 로표기한다. 또한, w 는각 E 가스트림데이터에서등장한빈도를원소로갖는색인된집합이며, E i 에대한원소를 w i 로표기한다. 모든 E 는특정시점을기준으로시간차이와값을표현하는순차패턴을나타낸다. 이를표현하기위해, 상대적시간색인 u 와인자색인 f 가부여된이산변수 X f u 와변수에할당된값 c 로이루어진 3-tuple (f,u,c) 를원소로하는집합 K 를정의하자. P E (K ) 는 K 의멱집합 P (K ) 의부분집합으로, 시간과인자쌍이중복되지않는것들을원소로하는집합이며, 패턴 E 는 P E(K ) 의임의의원소이자, (f,u,c) 들의집합이된다. 즉,
다차원스트림데이터의온라인점진적학습을위한순차적예측모델 421 P ( X) = { E E P ( X ), i, j in E, ( f, u ) ( f, u )} (2) E i i j j 단, i, j 는 E 안에있는원소의색인을나타내는양의정수이다. 3.2 추론방법 t-k 시점부터 t 까지의값이질의로서주어졌을때, t+n 시점에대한예측을다룰경우, 조건부확률 P 가최대가되는 x 가결정되며, 주어진 M 으로부터다음과같은근사적인비례관계를얻는다. Eiu, n c wi δ Ei, u n xt kt : δ Ei, u= 0 xt+ n Ei H t+ n t kt : = t kt : Eiu, n c wi δ ( Ei, u n, xt kt :) Ei H PX ( X x ) (, ) (, ) (3) 상기식에서 δ ( Eiu, n, xt kt : ) 은 i 번째패턴 Ei 에서 시간색인이 n 보다큰부분의값이질의와동일하면 ( 또는가까우면 ) 1, 아니면 0을출력하는함수이며, δ ( E =, x+ ) 는패턴 Ei 의 u =0인원소와예측하려는 iu, 0 t n 값이동일 ( 또는가까움 ) 여부를출력하는함수이다. 즉, 식 (3) 은다음두단계를하나의수식으로표현한것이다. 모델이가진패턴집합내에서 1) 질의와관련된패턴들을 matching과정을통해찾고, 2) 그안에서빈도정보, 패턴내시간차이정보와패턴의경우의수를이용하여사후조건부확률을계산하게된다. 3.3 학습방법모델 M 은이상적으로는고려하는시간색인길이 k 에따라패턴 E 의개수가지수적으로증가한다. 이를극복하기위해데이터에나타나지않은패턴의빈도는 0이므로, 실제모델에는아직추가될필요가없으며, k 가클경우, 모든조합을다다룰수없으므로가능한패턴중일부를무작위로선택하여모델에반영한다. 이를수행하는학습알고리즘을그림 2에제시하였다. 스트림데이터가입력됨에따라, 스트림데이터의 X t-w ~ X t 상에서무작위로시점과인자를선택하여 h 개의후보를만든후, M 안에해당패턴이없을경우 M 에포함시킨다. 그후, 포함된패턴에대해서입력되는데이터와비교, 맞는패턴에대해해당 w 를증가시킨다. 여기서, 데이터스트림의특성에따라학습된모델이수렴하지않고새로운패턴이무한히발견될경우, 모델도이를포함시켜야하며, 이는계산불능문제를야기시킨다. 이를회피하기위한부분이필요하며, 그림 2의 revise 부분이이에해당된다. 두가지전략이사용될수있다. 첫번째전략은패턴수의상한선을정해두고, 새로운패턴을추가해야할경우, w, E 를기준으로모델에영향이작은패턴부터삭제하는전략이다. 두번째전략은각패턴마다 fading constant를두어문턱값이상사용되지않은패턴을삭제하는전략이다. 그림 2 간략히표현한학습알고리즘 Fig. 2 Briefly sketched Learning Algorithm 4. 실험결과본절에서는실험을통해제안한모델이분포학습을잘하는지확인한후, 실세계데이터를이용하여순차적예측문제에적용할것이다. 먼저, 분포학습특성을확인하기위해, 특정분포로부터무작위로생성한데이터를제안한모델에학습시키고이로부터원본분포와의차이를분석한다. 실생활속응용으로서, [9] 에서쓰인스마트폰으로수집한 GPS 위치정보데이터를스트림형태로입력시키면서, 이후시점에위치할도로예측문제를다루었다. 4.1 조건부확률분포학습분포학습여부를확인하기위해서는분포를알고있는데이터가필요하다. 이를위해, 다음과같이스트림데이터의대체데이터를생성하였다. 숫자 1,2,3,4 를가능한알파벳으로한문자열을무작위로만들되, 이전두개의문자에만의존적으로다음문자가나타나도록하였다. 이때, 4 4 4개의가능한패턴에대한이산적확률을명시해야한다. 패턴 1 2 3, 2 3 4, 3 4 1, 4 1 2 는다른가능한패턴에비해 4배더나타날확률이높도록하여길이 1000짜리시계열데이터를생성하였고, 이데이터를입력스트림으로사용하여학습하였다. 무작위로생성하였으므로, 사전에정한분포와생성된데이터에대한실제분포는차이가존재하지만, 입력이많아질수록그차이가줄어든다 ( 그림 3(a)). 또한, 조건부확률의경우에는 X t-1 X t-2 의값에따라매시점다른분포를나타내야하므로 (b) 에서와같이변동이관측된다. 이데이터로학습을위해사용한모델은 n =1, k =4, 각 E 가가질수있는최대원소수 ( 이후, order라고부름 ) 는 4로파라미터를설정한모델이다. 그림 4에서볼수있듯이, 학습을진행함에따라제안한모델이예측한확률과등장패턴에따른통계사이의거리가점차줄어드는것을확인할수있다. 이는입력데이터스트림이분포를유지할경우, k 값이생성확률의조건과딱맞지않더라도분포를학습할수있음을의미한다.
422 정보과학회논문지 : 컴퓨팅의실제및레터제 19 권제 8 호 (2013.8) 그림 3 학습을위한문자열스트림의생성분포와각시점까지의패턴통계와의차이 Fig. 3 Difference between the generating distribution and pattern statistics in the training stream of string 그림 4 조건부분포학습결과 Fig. 4 Result of learning the conditional distribution 4.2 스마트폰센서스트림을이용한위치예측문제상기방법론은스마트폰내에임베딩된다양한센서로부터다음시점또는미래시점의센서값을예측하는문제에사용될수있으며, 이예측치로부터사용자의컨텍스트를추론하는문제를다룰수있다. 본고에서는개념증명으로서 GPS 센서로부터얻은위치정보로부터다음시점의위치예측문제에적용한결과를보고한다. 이를위한테스트용스트림데이터로서, [9] 에서사용된로그기록기인 Action Logger를이용하여실제사용자 (1명) 의이동로그를 1초간격으로 4건 ( 각 1247초, 1170 초, 1719초, 1338초 ) 을수집하였다. 실수인 GPS 값을대신하여이산화를위해네비게이션모듈을이용하여가까운도로로사영시켰다 ( 그림 5). 이과정은 GPS의관측노이즈를줄이는효과를가지지만, 갈림길또는이면도로가있는경우다른도로로사영되기도하므로, 여전히노이즈를가진이산화된순차데이터가된다. 상기데이터를입력데이터스트림으로하여학습과추론을함께수행하였다. (n =1, k =10, order: 2~3, 2~4, 2~5 사용 ) 학습이진행됨에따라그림 6(a) 와같이매치된각패턴의빈도수가늘어나게된다. k는고려할과거값의길이를나타내며, 학습된모델은 k-order Markov 모델을근사하게된다. Order가커지면지수적으로경우의수가늘어나므로, 직접모델링을시도할경 우연산가능범위를쉽게넘어선다. 이를위해비교모델로서 naïve Bayes 모델을사용하여 k-order Markov 모델을근사하였다. 또한, order 값이커지면고려해야할패턴의다양성이커짐에따라모델내의총패턴수도늘어나게된다. 학습을수행하며온라인으로추론한결과는다음과같다. 초기에 1번로그까지만학습했을때보다 1~2, 1~3, 1~4 등여러로그가추가된모델은그에따른방해가생겨예측정확도는다소하락한다. 하지만 order를늘리면더많은정보를이용하게되어성능이증가하는것을볼수있다. 학습과정에서무작위로패턴을추가하였기때문에 4번까지반복학습을수행하더라도그림 6(b) 와같이모델내의패턴수는완만하게증가한다. 5. 결론및향후연구본고에서는스트림데이터를다룰수있는점진적온라인학습모델을소개하고추론및학습방법을보였다. 제시방법의타당성을확인하기위해분포를아는데이터스트림과학습된모델이근사하는조건부확률을비교하였으며, 실생활의응용예로서스마트폰센서데이터학습결과를제시하였다. 향후에는장기적의존성을다룰수있는모델과추론 / 학습방법에관한연구를진행할예정이며, 이를예측
다차원 스트림 데이터의 온라인 점진적 학습을 위한 순차적 예측 모델 423 그림 5 학습에 사용한 이동 로그의 예 (1번 로그). GPS 값(위)을 도로로 변경하여(아래) 학습데이터로 이용 st nd Fig. 5 GPS based log sequence sample in training dataset. Raw GPS values (1 row) are converted into streets (2 row) 그림 6 스마트폰 센서 데이터를 이용한 학습 및 예측 결과 Fig. 6 Learning & prediction result with smartphone sensor data stream 및 스트림 데이터 요약에 적용하고자 한다. 본 연구를 통해 더욱 개선된 추론/학습 방법에 대한 연구와 다른 응용에의 적용을 기대한다. References [ 1 ] N. D. Lane, E. Miluzzo, H. Lu, D. Peebles, T. Choudhury, and A. T. Campbell, "A Survey of Mobile Phone Sensing," IEEE Communications Magazine, vol.48, no.9, pp.140-150, 2010. [ 2 ] S. Haykin, Neural Networks and Learning Machine, Prentice Hall, 2009. [ 3 ] D. Koller and N. Friedman, Probabilistic Graphical Models: Principles and Techniques, MIT Press, 2009. [ 4 ] D. Barber, T. Cemgil, and S. Chiappa, Bayesian Time Series Models, Cambridge University Press, 2011. [ 5 ] S. Shalev-Shwartz, "Online Learning and Online Convex Optimization," Foundations and Trends in Machine Learning, vol.4, no.2, pp.107-194, 2012. [ 6 ] G. Widmer and M. Kurat, "Learning in the Presence of Concept Drift and Hidden Contexts," Machine Learning, vol.23, pp.69-101, 1996. [ 7 ] I. Zliobaite, "Learning under Concept Drift: an Overview," Technical Report, Faculty of Mathematics and Informatics, Vilnius University, 2009. [ 8 ] C. Aggarwal, Data Streams: Models and Algorithms, Springer, 2007. [ 9 ] M.-O. Heo, M. Kang, B.-K. Lim, K.-B. Hwang, Y.-T. Park and B.-T. Zhang, "Real-time Route Inference and Learning for Smartphone Users using Probabilistic Graphical Models," Journal of KIISE: Software and Applications, vol.39, no.6, pp.425-435, 2012.