ISSN 2383-6318(Print) / ISSN 2383-6326(Online) KIISE Transactions on Computing Practices, Vol. 21, No. 2, pp. 154-159, 2015. 2 http://dx.doi.org/10.5626/ktcp.2015.21.2.154 일상생활계획을위한스마트폰 - 사용자상호작용기반지속발전가능한사용자맞춤위치 - 시간 - 행동추론방법 (Smartphone-User Interactive based Self Developing Place-Time-Activity Coupled Prediction Method for Daily Routine Planning System) 이범진 김지섭 류제환 (Beom-Jin Lee) (Jiseob Kim) (Je-Hwan Ryu) 허민오 김주석 장병탁 (Min-Oh Heo) (Joo-Seuk Kim) (Byoung-Tak Zhang) 요약과거어플리케이션다양성만지향하던사용자의수요가최근스마트폰의고도화된센서와기계학습이결합된지능형어플리케이션으로의선호로전향되고있다. 이러한경향을반영하여본논문에서는스마트폰에축적된사용자의라이프로깅데이터에서의미있는정보를추출하고, 추출한정보를통해사용자의인지적행동을대신가능한인지에이전트 (Cognitive Agent) 개념의스마트폰 - 사용자상호작용사용자맞춤위치 - 시간 - 행동추론기법을제안한다. 제안방법은사용자의라이프로깅데이터를 DPGMM (Dirichlet Process Gaussian Mixture Model) 클러스터링기법으로사용자주요관심지역 POI(Point of Interest) 를자동으로추출하고, 평생학습이가능한강화학습의한종류인 POMDP(Partially Observable Markov Decision Process) 를사용하여사용자의위치 - 시간 - 행동을추론한다. 제안방법으로구현한사용자맞춤일과계획시스템의시간별사용자일과추론결과는 70% 이상의성능을보였으며, 하루일과계획지능형서비스의새로운방향을제시하고있다. 키워드 : 기계학습, 위치기반서비스, 지능형앱, 강화학습 Abstract Over the past few years, user needs in the smartphone application market have been shifted from diversity toward intelligence. Here, we propose a novel cognitive agent that plans the daily routines of users using the lifelog data collected by the smart phones of individuals. The 이논문은 2013년도삼성전자의지원을받아수행된연구이며, 정부의재원으로 2014년도미래창조과학부 (NRF-2010-0017734-Videome) 및정보통신기술진흥센터 (10035348-mLife, 14-824-09-014-Machine Learning Center, 10044009- HRI.MESSI) 의지원을일부받았음 이논문은 2014 한국컴퓨터종합학술대회에서 하루일과계획을위한스마트폰- 사용자상호작용기반지속발전가능한사용자맞춤위치 -시간- 행동추론방법 의제목으로발표된논문을확장한것임 학생회원 : 서울대학교컴퓨터공학부 bjlee@bi.snu.ac.kr jkim@bi.snu.ac.kr moheo@bi.snu.ac.kr 비회원 : 서울대학교뇌과학협동과정 jhryu@bi.snu.ac.kr 비회원 : 삼성전자빅데이터센터 (MSC) jooseuk.kim@samsung.com 종신회원 : 서울대학교컴퓨터공학부교수 (Seoul National Univ.) btzhang@bi.snu.ac.kr (Corresponding author임 ) 논문접수 : 2014년 9월 15일 (Received 15 September 2014) 논문수정 : 2014년 11월 4일 (Revised 4 November 2014) 심사완료 : 2014년 11월 19일 (Accepted 19 November 2014) CopyrightC2015 한국정보과학회ː 개인목적이나교육목적인경우, 이저작물의전체또는일부에대한복사본혹은디지털사본의제작을허가합니다. 이때, 사본은상업적수단으로사용할수없으며첫페이지에본문구와출처를반드시명시해야합니다. 이외의목적으로복제, 배포, 출판, 전송등모든유형의사용행위를하는경우에대하여는사전에허가를얻고비용을지불해야합니다. 정보과학회컴퓨팅의실제논문지제21권제2호 (2015. 2)
일상생활계획을위한스마트폰 - 사용자상호작용기반지속발전가능한사용자맞춤위치 - 시간 - 행동추론방법 155 proposed method first employs DPGMM (Dirichlet Process Gaussian Mixture Model) to automatically extract the users POI (Point of Interest) from the lifelog data. After extraction, the POI and other meaningful features such as GPS, the user s activity label extracted from the log data is then used to learn the patterns of the user s daily routine by POMDP (Partially Observable Markov Decision Process). To determine the significant patterns within the user s time dependent patterns, collaboration was made with the SNS application Foursquare to record the locations visited by the user and the activities that the user had performed. The method was evaluated by predicting the daily routine of seven users with 3300 feedback data. Experimental results showed that daily routine scheduling can be established after seven days of lifelogged data and feedback data have been collected, demonstrating the potential of the new method of place-time-activity coupled daily routine planning systems in the intelligence application market. Keywords: machine learning, reinforcement learning, location-based service, intelligent App 1. 서론스마트폰의대규모시장성으로인한다양한스마트폰의보급과스마트폰의내장된고성능센서를활용한위치기반서비스가고도화되고있다. 과거 GPS 센서만을이용한서비스에서발전된종래기술은과거서비스의문제점을해결하려는시도로사용자의스마트폰사용내역을가공하여생성된사용자프로파일링 [1-3] 을활용하여사용자맞춤서비스를제공하거나기계학습의확률모델 [3-8] 을사용하여저수준모바일데이터와고수준행동간연관규칙을찾고이를통해사용자의행동을추론하여지능형서비스를제공하는시스템이존재한다. 지능형서비스를제공하기위해사용된기존기계학습기법들로는나이브베이즈 (Naïve Bayes)[4], 베이지안네트워크 (Bayesian Network)[5] 와같은순차적의존성을고려하지않는모델들이있고, HMM(Hidden Markov Model)[6], 동적베이지안네트워크 (Dynamic Bayesian Network, DBN)[7] 처럼순차적의존성을고려한모델들이존재한다. 그외데이터를벡터양자화 (vector quantization) 하거나, KNN(K-Nearest Neighbor)[8] 와같이클러스터링하여양자화한후확률모델을같이사용하여지능형서비스를제공하는기법들도존재한다. 다양한시도들이좋은결과를보이고있지만기존방법들은일괄처리 (batch) 방식으로학습하기때문에변화를적용하는모델의재학습을위해선축적된로그데이터를이용하여다중의계산적반복절차가필수불가결하고모델과사용자가직접상호작용하는방법은고려하지않기에사용자의변화까지는추론하지못하고있다. 이러한문제점을해결하기위해본논문에서는사용자의행동을추론할수있는단위의 POI를자동적으로추출하는점증적클러스터링기법과사용자의라이프로그를모두기록하고사용자의의도가실시간으로반영되어추후사용자의의도를추론할수있는스마트폰- 사용자일체화 [9] 개념을도입한강화학습모델에추출된 POI를적용하여사용자맞춤행동예측서비스를제 공, 능동적평생학습 [10] 가능한플랫폼하에지속적으로사용자피드백에반응하고성능향상이가능한일과계획시스템을제안하였다. 2. 연구내용및방법본논문에서제시하는전체시스템흐름은그림 1과같다. 사용자의스마트폰에지속적으로축적되는사용자개인의라이프로그데이터를분석하고, DPGMM을통해 POI를추출한다. 이렇게추출된 POI와피드백데이터는 POMDP를학습시키는데사용되고사용자에맞는위치-시간별행동 (Activity) 을추론한다. 즉, 사용자맞춤일과계획서비스가제공가능해진다. 그림 1 전체시스템의흐름도 Fig. 1 Overall system flow chart 2.1 수집데이터사용자의다양한행동패턴추론을실험하기위해다양한직업군의지원자 7명을대상으로 40일간라이프로깅데이터와피드백데이터를수집하였다. 표 1은라이프로깅데이터와피드백데이터의사용자별수집현황
156 정보과학회컴퓨팅의실제논문지제 21 권제 2 호 (2015.2) 표 1 다양한수집자에대한라이프로그와피드백데이터 Table 1 Lifelog and feedback data collected from various users 동은 SNS 앱인포스퀘어 (Foursquare) 에서제공되는총 17가지행동으로구분하였다 ( 그림 2). 이는 POI에서사용자가수행하는직접적인행동패턴을추론하는데사용한다. 2.2 DPGMM 클러스터링기법제안하는시스템에서 DPGMM 클러스터링을사용하는가장큰목적은사용자의 POI를추출하는데있다. POI는사용자의잦은방문과해당지역에서스마트폰을가장많이사용하는지점이라고정의하게되는데이 POI는사용자별로다양하게분포하게된다. 기존정적클러스터링방법은클러스터의개수를설계자가직접지정해주어야하는문제점이있다. 하지만본시스템에서사용하는 DPGMM은자동적으로클러스터의개수를찾고클러스터링을함으로써다양한사용자들의기호에맞는 POI를추출할수있다. 아래는 DPGMM의클러스터링기법의수식과그래픽모델표현 ( 그림 4) 이다. 그림 2 모든사용자피드백데이터행동별총량 Fig. 2 Total amount of various user activities z i: i th instance label y i: i th instance N: Total No. of instance k: Labe index n k: No. of instance in index k θ k: Parameter of k α: Dirichlet parameter 그림 4 DPGMM 의그래픽모델표현 Fig. 4 DPGMM graphical model Existing Cluster : New Cluster : 그림 3 수집된라이프로그와피드백데이터형식 Fig. 3 Structure of the collected lifelog and feedback data 이며라이프로깅데이터와피드백데이터는그림 3과같은형식으로수집되었다. 수집된피드백데이터의행 2.3 POMDP 기반위치- 시간- 행동추론모델기존스마트폰을이용한지능형서비스는사용자의시간별행동에대한개별적인추론결과를제시하거나단편적행동패턴을제시했다. 하지만본논문에서는사용자가의도하는일련의행동순서를추론할수있는그림 5와같은 POMDP 강화학습모델을제시한다. 제시하는모델은사용자최적의행동일과 ( 정책 ) 를 PBVI Point-based Value Iteration) 알고리즘기반으로 POI 와시간에따른행동을추론한다. 제안하는 POMDP 모델 M은아래와같이구성되었다. 본논문이해결하고자하는문제는모델이사용자가현재의도하는행동에대해불확실성이존재하고, 시간과 POI에따라그의도가변화할수있기때문에상태의확신정도에의해사용자의상태를판별하는 POMDP 모델을사용하였다. 현재의도에서다음의도를선택하
일상생활계획을위한스마트폰 - 사용자상호작용기반지속발전가능한사용자맞춤위치 - 시간 - 행동추론방법 157 는데사용되는보상은시그모이드함수를통과시켜사용자의라이프로그가축적됨에따라행동피드백변화에민감하게반응할수있도록하였고, 사용자의피드백에맞추어자동적으로업데이트되어사용자에게가장적합한위치-시간-행동추론을수행할수있게설계하였다. 입력되는사용자의피드백데이터의변화에따라최적일과추론또한변화함을확인하였다. 3.2 DPGMM 클러스터링결과그림 6은사용자의피드백지점인 POI( 그림 6 왼쪽 ) 와라이프로깅데이터를 DPGMM으로클러스터링한결과 ( 그림 6 오른쪽 ) 가상당수일치함을볼수있다. 그리 그림 5 제시하는 POMDP 그래픽모델표현 Fig. 5 Graphical model representation of the proposed POMDP L( 지평길이 ): 24 ( 하루 24시간의 1시간단위 ) S( 상태 ): 현재사용자가의도하는행동집합 A( 행동 ): 다음사용자가의도하는행동집합 O( 관찰값 ): Time( 시간대역 ), 클러스터링된개인관심지역 St( 상태전이 ): R( 보상 ): 사용자시간, 의도별변화보상 b(s): 상태확신확률 π: 최적정책 arg Pr 그림 6 DPGMM을이용한한사용자의 POI와실제피드백기반 POI 비교 Fig. 6 Comparison of DPGMM clustered POI and feedbackbased POI for one user 3. 실험분석및결과 3.1 수집데이터분석사용자의일과를계획하고서비스를제공하기위해서는수집한피드백데이터에패턴이존재하는지여부가중요하다. 이를확인하기위해그림 2에서정의한 17가지행동에따른분포를확인해보았다. 17가지행동중사용자를구별할수있는다양한행동이존재하지만모든사용자가공통적으로수행하는생활패턴이존재하며이는수집한데이터를활용하여사용자맞춤의위치 -시간-행동일과계획서비스를제공할수있는가능성을제기한다. 실험은수집자들이실제로자주방문하는곳과 DPGMM 을이용하여추출한 POI를비교해보고, POMDP에추출된 POI를적용하여사용자최적하루일과를추론한결과와실제사용자의하루일과에대해수집된피드백데이터의일치율을비교해보았다. 그리고지속적으로 그림 7 (a) 순차적인시간, 위치에따른 POMDP 추론결과, (b) 고정위치, 고정시간을기준으로미래일과를예측한결과, (c) 베이지안모델과 POMDP의추론결과비교 Fig. 7 (a) Time and place-dependent activity sequential prediction results. (b) Routine plan results. (c) Comparison of individual time and place prediction results Bayesian Network
158 정보과학회 컴퓨팅의 실제 논문지 제 21 권 제 2 호(2015.2) 고 오른쪽의 추출된 POI에 같은색으로 지정된 부분은 능 저하 현상이 나타났으며 데이터수가 증가한다면 높 사용자가 비슷한 행동을 하는 지점들로 군집되어 있음을 은 일과예측 성능이 예상된다. 위 결과들의 신빙성을 입 확인할 수 있다. 해당 결과를 추출하기 위해 DPGMM 증하기 위하여 그림 7(c)는 베이지안 네트워크와 비교를 의 변수 조정 파라미터 α 값은 1로 했으며 가장 최적의 하였고 그 결과 평균적으로 높은 성능을 보이고 있었으 값을 적용하여 실험한 결과이다. 며 그림 9에서는 사용자들의 confusion matrix를 확인 3.3 POMDP 사용자 맞춤 일과 추론 결과 할 수 있다. 이를 통해 다양하게 분포되어 있는 행동들 그림 7(a)는 실제 사용자의 순차적 위치 이동 피드백 을 높은 확률로 추론하는 것을 확인 할 수 있다. 마지막 과 POMDP로 추론한 순차적 의도 예측결과 약 70% 으로 본 시스템의 cold start 문제는 그림 8에서와 같이 이상의 일치함을 확인할 수 있다. 그 중 사용자 1은 데 제시하는 사용자 행동 추론 결과의 개수에 큰 상관없이 이터 문제로 인해 성능의 저하를 보이고 있다. 약 9일 이후에는 성능이 안정화됨을 확인할 수 있다. 고정된 위치와 시간에서 사용자 별 최적 일과를 추론 한 결과인 그림 7(b)는 평균 약 50%의 성능을 확인 할 수 있으나 이는 피드백 데이터가 부족한 수집자들의 성 4. 결론 및 향후 연구 본 논문에서는 실시간성과 사용자 상호작용이 불가능 한 확률모델만을 기반으로 스마트폰에서 지능형 서비스 를 제공하는 기존 방법과는 달리 평생학습의 강화학습 법을 적용하여 스마트폰과 사용자가 직접 상호작용 가 능하고 실시간으로 반응 가능한 지능형 서비스의 방법 을 제시하였다. 본 방법은 사용자의 피드백을 이용하여 사용자의 위치-시간대별 변화하는 행동을 모델에 적용 하여 즉각적 사용자 맞춤 서비스 제공이 가능함을 보였 다. 본 방법을 가장 최적으로 사용할 수 있는 방법은 사 용자에게 다양한 서비스를 제공하여 사용 횟수 증가를 유도하고 그에 따라 축적되는 라이프 로그를 의도하는 그림 8 상위 K개 결과 제시 변화에 따른 성능 비교 행동으로 추론 할 수 있는 피드백 가공방법을 고안한다 Fig. 8 Evaluation results depending on top K results 면 최적의 서비스 제공할 수 있을 것으로 예상한다. 그림 9 사용자들의 행동 추론 결과 confusion matrix. 좌측, 상단-17가지 행동, 우측-각 행동 별 사용자의 피드백 총량 바 그래프 Fig. 9 Confusion matrix of individual users. Right: top-17 activities, Left: bar graph illustrating total count of each activity
일상생활계획을위한스마트폰 - 사용자상호작용기반지속발전가능한사용자맞춤위치 - 시간 - 행동추론방법 159 References [1] G. Hache, E. D. Lemaire, N. Baddour, "Mobility Change-of-state Detection using a Smartphonebased Approach," Proc. of the IEEE International Workshop on Medical Measurements and Applications, pp. 43-46, 2010. [2] H. Verkasalo, "Analysis of Smartphone User Behavior," Proc. of Mobile Business and 9th Global Mobility Roundtable, pp. 258-263, 2010. [3] A. Papliatseyeu, M. Oscar, "Mobile Habits: Inferring and Predicting User Activities with a Locationaware Smartphone," 3rd Symposium of Ubiquitous Computing and Ambient Intelligence, Vol. 51, pp. 343-352, 2009. [4] B. Longstaff, S. Reddy, D. Estrin, "Improving Activity Classification for Health Applications on Mobile Devices using Active and Semi-supervised Learning," Proc. of Pervasive Computing Technologies for Healthcare, pp. 1-7, 2010. [5] G. M. Weiss, J. Lockhart, "The Impact of Personalization on Smartphone based Activity Recognition," AAAI Workshop on Activity Context Representation: Techniques and Languages, 2012. [6] Y. Lee and S.-B. Cho, "Activity Recognition using Hierarchical Hidden Markov Models on a Smartphone with 3D Accelerometer," Hybrid Artificial Intelligent Systems, pp. 460-467, Springer Berlin Heidelberg, 2011. [7] S.-I. Yang, J.-H. Hong, S.-B. Cho, "Activity Recognition based on Multi-modal Sensors using Dynamic Bayesian Networks," Journal of KIISE: Computing Practices and Letters, Vol. 15, No. 1, pp. 72-76, 2009. (in Korean) [8] S. Kaghyan, H. Sarukhanyan, "Activity Recognition using K-nearest Neighbor Algorithm on Smartphone with Tri-axial Accelerometer," Journal of IJIMA : ITHEA International Scientific Society, Vol. 1, pp. 146-156, 2012. [9] B. T. Zhang, "Communication as Moving Target Tracking," Alignment in Communication: Towards a New Theory of Communication, pp. 133-148, John Benjamins Publishing, 2013. [10] B. T. Zhang, "Information-Theoretic Objective Functions for Lifelong Learning," AAAI Spring Symposium on Lifelong Machine Learning, pp. 62-69, 2013. 김지섭 2011년 2월서울대학교기계항공공학부 ( 컴퓨터공학부전공 ). 2011년 3월~ 현재서 울대학교컴퓨터공학부석. 박사통합과정 관심분야는 Deep Learning, Manifold Learning 류제환 2013년 2월서울대학교화학생물공학부학사. 2013년~현재서울대학교뇌과학협동과정석사과정. 관심분야는분자컴퓨팅, 인공신경망, 브레인이미징 허민오 2001 년 ~2004 년 ( 주 ) 인티연구원. 2005 년고려대학교전기전자전파공학부학사. 2005 년 ~ 현재서울대학교컴퓨터공학부석박사통합과정. 관심분야는인지기계학습, 확률기반모델링방법론, online learning 김주석 2002 년 2 월서울대학교전기공학부학사 2007 년 4 월 University of Michigan, Electrical Engineering 석사. 2011 년 8 월 University of Michigan, Electrical Engineering 박사. 2011 년 ~ 현재삼성전자빅데이터센터책임연구원. 관심분야는 Machine Learning and Statistical Analysis 장병탁정보과학회컴퓨팅의실제논문지제 21 권제 1 호참조 이범진 정보과학회컴퓨팅의실제논문지제 21 권제 1 호참조