[논문]평가의 시간 순서를 고려한 강화 학습 기반 협력적 여과

이정규; 오병화; 양지훈

doi:10.3745/kipstb.2012.19b.1.031

평가의 시간 순서를 고려한 강화 학습 기반 협력적 여과
A Reinforcement Learning Approach to Collaborative Filtering Considering Time-sequence of Ratings 원문보기

정보처리학회논문지. The KIPS transactions. Part B. Part B, v.19B no.1, 2012년, pp.31 - 36

이정규 ((주)사이람) , 오병화 (서강대학교 컴퓨터공학과) , 양지훈 (서강대학교 컴퓨터공학과)

초록
AI-Helper

최근 사용자의 흥미에 맞는 아이템이나 서비스를 추천해 주는 추천 시스템에 대한 관심이 높아지고 있다. 최근 종료된 Netflix 경연대회(Netflix Prize)가 이 분야에 대한 연구자들의 연구 의욕을 고취시켰고, 특히 협력적 여과(Collaborative Filtering) 방법은 아이템의 종류에 상관없이 적용 가능한 범용성 때문에 활발히 연구되고 있다. 본 논문은 강화 학습을 이용해서 추천 시스템의 협력적 여과 문제를 푸는 방법을 제안한다. 강화 학습을 통해, 영화 평점 데이터에서 각 사용자가 평점을 매긴 순서에 따른 평점 간의 연관 관계를 학습하고자 하였다. 이를 위해 협력적 여과문제를 마르코프 결정 과정(Markov Decision Process)로 수학적으로 모델링하였고, 강화 학습의 가장 대표적인 알고리즘인 Q-learning을 사용해서 평가의 순서의 연관 관계를 학습하였다. 그리고 실제로 평가의 순서가 평가에 미치는 영향이 있음을 실험을 통해서 검증하였다.

Abstract ▼ AI-Helper

In recent years, there has been increasing interest in recommender systems which provide users with personalized suggestions for products or services. In particular, researches of collaborative filtering analyzing relations between users and items has become more active because of the Netflix Prize competition. This paper presents the reinforcement learning approach for collaborative filtering. By applying reinforcement learning techniques to the movie rating, we discovered the connection between a time sequence of past ratings and current ratings. For this, we first formulated the collaborative filtering problem as a Markov Decision Process. And then we trained the learning model which reflects the connection between the time sequence of past ratings and current ratings using Q-learning. The experimental results indicate that there is a significant effect on current ratings by the time sequence of past ratings.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 연구에서는 협력적 여과 문제를 해결하는 새로운 방법으로, 강화 학습 기법(Reinforcement Learning)을 사용하는 방식을 제안한다. 강화 학습은 에이전트가 경험을 통해 환경에 대해 적응해 가는 과정을 모델링한 연구 분야로서, 보행 로봇의 이동, 헬기의 자동 비행, 네트워크 라우팅, 마케팅 전략 선택, 웹 인덱싱 등 많은 분야에서 효율적이라고 평가된다.
SVD는 예측의 정확성이 높을 뿐만 아니라 SVD의 결과로 나오는 행렬이 매우 유용하다. 본 연구에서도 SVD의 예측과 결과 행렬을 사용하였기 때문에 SVD 알고리즘에 대해서 간단히 알아보겠다.

가설 설정

• 전이 확률(Transition Probability): 협력적 여과에 대한 MDP는 결정적(Deterministic) MDP라고 가정한다.
데이터베이스에는 N명의 사용자와 M개의 영화에 대한 선호도가 수치적으로 모아져 있다고 가정한다. 예를 들어, 사용자는 자신이 본 영화에 대해서 1에서 5까지의 평점을 줄 수 있다.

제안 방법

다음 실험으로 각 기본 예측기에 대해 제안 알고리즘을 적용하였을 때 성능 향상을 비교하여 보았다. 5.
첫 번째 실험의 경우, 영화 평균에 비해 큰 폭의 성능 향상을 보였기 때문에 제안 알고리즘이 아이템에 대한 평가의 순서가 사용자의 결정에 끼치는 영향을 의미 있게 학습해냈다고 볼 수 있다. 또 두 번째 실험의 경우 현재 협력적 여과 분야에서 단일 알고리즘 중 가장 효율적이라고 알려져 있는 SVD++의 성능을 더욱 올려놓았다. 이는 제안 알고리즘이 SVD++이 학습할 수 없는 평점 데이터의 순차적인 연관 관계를 추가적으로 학습할 수 있게 해준다는 것을 의미한다.
본 연구에서 추천 시스템의 협력적 여과 분야에서 처음으로 강화 학습 기법을 적용하였다. 비록 협력적 여과가 아닌 다른 추천 시스템에 대한 강화 학습의 적용 예[14]가 있지만 이는 본 연구와 아주 간접적인 연관만 있을 따름이다.
이 대회의 우승팀인 BellKor's Pragmatic Chaos 팀은 위의 세 가지 알고리즘을 기반으로 하여 100여개 이상의 예측기를 학습한 후, 이들을 앙상블(Ensemble)한 예측기로 우승을 하였다.
지금까지 영화 데이터의 협력적 여과 문제를 강화 학습으로 접근하여 해결하는 방식을 제시하였다. 이를 위해 협력적 여과문제를 마르코프 결정 과정으로 사용자의 아이템에 대한 평가의 순서가 사용자의 결정에 끼치는 영향을 수학적으로 모델링하였고, 강화 학습의 가장 대표적인 알고리즘인 Q-learning을 사용해서 평가의 순서의 연관 관계를 학습하였다. 실험을 통해서 실제로 평가의 순서가 평가에 미치는 영향이 있다는 것을 증명하였다.
현재 어떤 영화의 평점을 매겨야 한다면 이 전에 본 영화가 지금 내려야 할 결정에 영향을 끼칠 수 있다. 잔상 효과처럼 사용자의 아이템에 대한 평가의 순서가 사용자의 결정에 끼치는 영향을 수학적으로 모델링하기 위해 본 연구팀은 강화 학습 기법을 협력적 여과 문제에 적용하였다.
협력적 여과 문제에 대한 SVD는 여러 Netflix Prize 참가자에 의해서 다양한 유형으로 발전하였는데 본 연구에서는 Netflix Prize의 1위 팀의 팀원인 Koren이 제안한 SVD++를 사용하였다[9].

대상 데이터

평점을 매긴 순서는 본 연구에서 제안한 알고리즘의 중요한 조건 중에 하나이기 때문에 MovieLens 데이터를 사용하였다. MovieLens 데이터는 71,567명의 사용자와 10,681개의 영화에 대해서 10,000,054개의 평점들로 이루어져 있는 데이터를 사용하였다.
데이터 집합으로는 MovieLens 데이터를 사용하였다[12]. Netflix 데이터 대신 MovieLens 데이터를 사용한 이유는 MovieLens 데이터는 평점의 시간 데이터가 초단위로 기록되어 있기 때문이다.
이때 각 사용자마다 평점을 매긴 영화의 수는 사용자마다 다르다. 먼저 본 영화에 대한 평점 80%를 훈련 데이터 집합으로 사용하고 나머지 20%를 테스트 데이터 집합으로 사용하였다. MovieLens 데이터는 0.
Netflix 데이터에는 사용자가 평점을 매긴 시간이 일 단위로 되어 있기 때문에 하루에 다수의 영화의 평점을 매겼을 경우 그 순서를 알 수 없다. 평점을 매긴 순서는 본 연구에서 제안한 알고리즘의 중요한 조건 중에 하나이기 때문에 MovieLens 데이터를 사용하였다. MovieLens 데이터는 71,567명의 사용자와 10,681개의 영화에 대해서 10,000,054개의 평점들로 이루어져 있는 데이터를 사용하였다.

데이터처리

다음 실험으로 각 기본 예측기에 대해 제안 알고리즘을 적용하였을 때 성능 향상을 비교하여 보았다. 5.1절의 설명에 따라 분리한 테스트 데이터 집합들에 대해 기본 예측기(영화평균, SVD++)와 기본 예측기 + 제안 알고리즘의 RMSE 성능을 비교해보았다. SVD++ 알고리즘 특성의 차원은 10으로 설정하였다.
최적의 매개 변수를 찾기 위해, 수식 (3)의 predictor(i, j)를 영화 j의 평균 평점으로 정하고 α와 γ를 변화시켜 가면서 RMSE를 측정하였다.

이론/모형

4.2절과 같이 정의된 MDP를 기반으로 강화 학습 기법인 Q-learning을 이용해서 Q(s, a)를 학습하였다[11]. Q(s, a)는 일반적으로 다음 식과 같이 정의된다.
목적 함수 f의 두 번째 항은 과적합(Overfitting)을 막기 위한 조정(Regulation) 작용을 한다. 수식 (1)을 최소화하기 위해 경사 강하법(Gradient Descent)을 사용한다.
I ∈ {0, 1}^N×M는 표시 함수(Indicator Function)인데, I_ij = 1 이면 행렬 A에서 사용자 i가 영화 j에 대한 평점을 매겼음을 뜻하고, 매기지 않았으면 0이다. 알고리즘의 성능 평가 방법으로는 Netflix 경연대회에서 사용하는 근 평균 제곱 오차(Root Mean Squared Error, RMSE)를 사용하였다. P ∈ R^{^n×m}이 협력적 여과 알고리즘이 추측한 예측 행렬이라 할 때, RMSE는 다음 수식과 같이 정의된다.

성능/효과

기본 예측기를 영화평균으로 할 경우 α = 0.5, γ = 0.000003에서 가장 좋은 성능을 보여주었고, 기본 예측기를 SVD++으로 할 경우 α = 0.65, γ = 0.000006에서 가장 좋은 성능을 보였다.
이를 위해 협력적 여과문제를 마르코프 결정 과정으로 사용자의 아이템에 대한 평가의 순서가 사용자의 결정에 끼치는 영향을 수학적으로 모델링하였고, 강화 학습의 가장 대표적인 알고리즘인 Q-learning을 사용해서 평가의 순서의 연관 관계를 학습하였다. 실험을 통해서 실제로 평가의 순서가 평가에 미치는 영향이 있다는 것을 증명하였다.
또 두 번째 실험의 경우 현재 협력적 여과 분야에서 단일 알고리즘 중 가장 효율적이라고 알려져 있는 SVD++의 성능을 더욱 올려놓았다. 이는 제안 알고리즘이 SVD++이 학습할 수 없는 평점 데이터의 순차적인 연관 관계를 추가적으로 학습할 수 있게 해준다는 것을 의미한다. Netflix 대회에서 가장 각광받는 예측기의 앙상블 기법에서도, 성능이 좋은 단일 알고리즘을 앙상블 예측기에 하나씩 추가할 때 약 0.
제안 알고리즘의 경우 10초 이내에 학습, 예측, 평가가 완료되었다. 제안 알고리즘은 정해주어야 할 두 가지 매개 변수가 있다.
첫 번째 실험인 기본 예측기를 영화 평균으로 할 경우 0.0272의 RMSE 성능 향상이 있었고, 두 번째 실험인 본 예측기를 SVD++으로 할 경우 0.0046의 RMSE 성능 향상이 있었다. 첫 번째 실험의 경우, 영화 평균에 비해 큰 폭의 성능 향상을 보였기 때문에 제안 알고리즘이 아이템에 대한 평가의 순서가 사용자의 결정에 끼치는 영향을 의미 있게 학습해냈다고 볼 수 있다.

후속연구

다시 말하면 각각의 예측기가 정확하며, 또한 각 예측기마다 볼 수 있는 데이터의 양상이 다양하여야 한다. 제안 알고리즘은 기존 여타의 단일 알고리즘이 고려하지 않는 평점의 순서와 최종 평점과의 관계를 학습해 내기 때문에 다른 예측기와의 차별성이 있으며, 따라서 앙상블의 후보 예측기로 제안 알고리즘을 사용할 경우 앙상블 예측기의 정확도를 더욱 높일 수 있을 것으로 기대된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	추천 시스템이란?	추천 시스템은 많은 양의 이용 가능한 아이템(Item)중에서 사용자(User)의 흥미에 맞는 아이템을 추천해주는 시스템을 말한다. 여러 가지 추천 시스템 기법 중 가장 많이 사용되는 방법은 협력적 여과로서, Amazon.
	추천 시스템 기법 중 많이 사용되는 방법은?	추천 시스템은 많은 양의 이용 가능한 아이템(Item)중에서 사용자(User)의 흥미에 맞는 아이템을 추천해주는 시스템을 말한다. 여러 가지 추천 시스템 기법 중 가장 많이 사용되는 방법은 협력적 여과로서, Amazon.com, CDnow.
	전통적인 협력적 여과 방식에서 사용자 목록과 아이템 목록을 이용해 만든 행렬로 무엇을 나타내는가?	전통적인 협력적 여과 방식에서는 사용자 목록과 아이템 목록을 이용한다[2]. 이를 통해 행렬을 구성하는데, 각 행렬의 항목 값은 사용자의 아이템에 대한 의견을 나타낸다. 사용자의 의견은 평점과 같은 사용자의 평가를 통해 직접적으로 획득하거나, 또는 사용자의 구매 기록이나 이용 패턴, 특정 페이지에서의 시간 기록 등을 분석해서 간접적으로 얻기도 한다.

참고문헌 (14)

B. M. Sarwar and G. Karypis, J. A. Konstan, and J. T Riedl., "Application of Dimensionality Reduction in Recommender System-A Case Study," ACM WebKDD 2000 Web Mining for E-Commerce Workshop, 2000.
B. M. Sarwar and G. Karypis, J. A. Konstan, and J.T. Riedl, "Item-based collaborative filtering recommendation algorithms," Proceedings of the 10th international conference on World Wide Web, pp.285-295, 2001.
Netflix Prize, http://www.netflixprize.com
A. Paterek, "Improving regularized singular value decomposition for collaborative Filtering", KDD-Cup and Workshop, ACM press, 2007.
R, Salakhutdinov, A. Mnih and G. Hinton, "Restricted Boltzmann machines for collaborative Filtering", Proceedings of the 24th International Conference on Machine Learning, 2007.
R. Bell and Y. Koren, "Scalable Collaborative Filtering with Jointly Derived Neighborhood Interpolation Weights", IEEE International Conference on Data Mining, IEEE, 2007.
G. Gorrell and B. Webb, "Generalized hebbian algorithm for incremental latent semantic analysis", Proceedings of Interspeech, 2006.
B. Webb, "Netflix update: Try this at home", http://sifter.org/simon/journal/20061211.html, 2006.
Y. Koren, "Factorization meets the neighborhood: a multifaceted collaborative filtering model", Proceedings of the 14th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining, pp.426-434, 2008.
R. Bellman, "A Markovian Decision Process", Journal of Mathematics and Mechanics 6, 1957.
C. Watkins, "Learning from Delayed Rewards", PhD thesis, Cambridge University, Cambridge, England, 1989.
MovieLens, http://www.movielens.umn.edu
L. Hansen and P. Salamon, "Neural Network Ensembles", IEEE Transaction on Pattern Analysis and Machine Intelligence, Vol.12, pp.993-1001, 1990.

상세보기
G. Shani, D. Heckerman and R. Brafman, "An MDP-based recommender system", Journal of Machine Learning Research, Vol.6, No.2, pp.1265-1295, 2006.

상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증