An Introduction to Recommender System
This chapter's goal
Recommender System field에서의 다양한 work에 대한 overview를 하고, 이 원서에서 개별적으로 나와 있는 다양한 topic들을 연관 짓는 것
Introduction
최근에 Recommender System에서는 Web의 중요성이 증가하고 있습니다. 그 이유는 user가 그들의 like dislike를 쉽게 feedback하는게 가능하기 때문입니다.
여기에서 feedback에 대한 전형적인 방법은 "ratings"입니다. 이를 통해서 특정 평가 시스템에서 선호도를 numerical value로 선택 할 수 있습니다.
다른 form의 feedback은 명백하지는 않지만 Web-centric paradigm에서는 모으기 더 쉽습니다. (implicit)
예를 들어서 어떤 item을 사거나 찾는 행위 자체는 ratings 보다는 customer에게 노력이 덜 듭니다. 이러한 다양한 데이터(사거나 찾는 행위)를 이용해서 customer의 interests를 추론 하는 것이 Recommender Systemd의 basic idea라 할 수 있습니다.
Recommender System에서의 주체는 user 일 수도 있고, item 일 수도 있습니다. Recommendation은 종종 이전의 users, items 간의 interaction을 기반으로 이뤄지기도 합니다.
그리고 앞 내용들과는 다른 내용이면서 주목할 만한 것은 knowledge-based recommender system인데 이는 특정된 user에 대한 requirement 기반입니다. 그리고 이는 domain knowledge 기반 이라고 할 수 있는데 이는 이 챕터의 후반부에 좀 더 자세히 나오니 그 때 설명하겠습니다.
원서에서는 neighborhood models라는 단어가 나오는데 이는 유사한 이웃을 찾는 모델 이라고 생각하면 됩니다. neightborhood models의 대표적인 예로는 _collaborative filtering_이 있습니다.
collaborative filtering은 모르는 ratings를 여러 users의 ratings을 사용해서 추론하는 형식을 의미합니다.
실제로, Recommender Systems 더 복잡해지고 data-rich 될 수 있습니다. 예를 들어서 Content-based recommender systems는 content(item의 profile)가 recommendation process에서 기초적인 역할을 하는데, knowledge-based systems는 contextual data와 같은 요소들도 사용될 수 있는 더 복잡한 모델이라 할 수 있습니다.
Goals of Recommender Systems
Recommendation Systems에서 기초적인 모델 두가지가 있습니다.
Prediction version of problem : item에 대한 user preference의 training data가 있다고 가정하고 training model을 통해 unobserved value를 추정 가능함. (matrix completion problem)
실제로 특정 item에 대한 user의 평가 추측보다는 top-k items를 추천함. 참고로 top-k item추천이 top-k user보다 common함. 이 경우, rating에 대한 절대적인 수치가 중요하지는 않음.
Recommender Systems의 goal은 결국 수익의 증가 입니다. Recommender Systems의 users에게 items를 추천하는 행위가 수익의 증대르 이끌 수 있습니다.(user에게 관련된 items에 주의를 이끌 수 있기 때문에) 하지만 수익 증대에 대해서 위의 이유만으로 분명하게 설명이 안될 때가 있습니다. 이는 business-centric goal(수익 증대)을 성취하기 위한 Recommender Systems에서의 operational and technical goals를 살펴보면 됩니다.Relevance : User와 관련된 item 추천.
Novelty : User가 과거에 보지 못했던 item을 추천 해줄 때 helpful 함.
Serendipity : User의 잠재적인 interst를 찾음. (단순히 User가 전에 모르던 것을 추천 해준다는 Novelty와는 좀 다르다.) 이는 다양한 수익 증대를 일으키고 흥미의 new-trend를 start하기도 한다. 하지만 종종 관계없는 것을 추천하기도 함.
Increasing recommendation diversity : top-k items 추천 시 다른 types의 items를 포함시킴. 이의 경우에 더 좋은 추천이라 할 수 있음.
위와 같은 concrete goals 이외에 soft goals를 살펴봅시다.
- User의 관점에서 recommendation은 결국 user의 만족을 높일 수 있음.
- Merchant의 관점에서, recommendation process는 user의 needs에 대한 insights를 제공하고 UX를 customize 하는 것을 도와줌.
- 사용자에게 추천된 아이템이 왜 추천되었는지 설명해주는 것도 유용함
아래에서부터는 오늘날 실제로 사용 가능한 commercial systems를 봐보겠습니다.
#### GroupLens Recommender System
GroupLens는 Usenet readers로 부터 ratings를 모으고 이를 기반으로 독자가 읽었든 안읽었든 predict합니다.
몇몇의 earliest automated collaborative filtering 알고리즘은 GroupLens Setting을 기반으로 발전하였습니다. 그리고 book, movie 에도 확장하기도 했습니다.(BookLens, MovieLens)
이 field의 초기에 Recommender System에 대한 datasets을 얻기가 쉽지 않았는데, 이 때 GroupLens research team은 datasets을 배포했습니다.
Amazon.com Recommender System
Amazon애서의 recommendation은 rationgs(1pt-5pt까지의 5star rating), buying behavior, browsing behavior를 기반으로 합니다. buying, browsing behavior는 user가 로그인 되어이있을 때 모으기 쉽습니다.
로그인 한 유저에 대해서 언제든지 Web page의 메인에 recommendation이 제공 됩니다.
여기에서 buying, browsing behavior에 대한 데이터는 implicit rating이라 할 수 있습니다.
많은 commercial은 implicit, explicit 지표를 둘 다 사용합니다.
Netflix Movie Recommender System
Netflix Movie Recommender System은 5point ratings와 watching behavior를 통해 recommendation합니다. 그리고 무엇보다도 explanation이 훌륭합니다.
이러한 meaningful explanations를 통해 사용자가 recommendation대로 행동할 가능성을 높이며 UX를 improve 합니다. 이를 통해 고객 유지 및 충성도를 높일 수 있습니다.
Netfilx는 research community에 기여한 바가 큽니다. "Netfilx Prize Contest"를 열었고 여기에서 Netfilx movie ratings dataset이 풀렸고, task는 특정 user-item combination의 ratings를 예측하는 것 이었습니다. (training dataset, qualifying dataset을 제공했음.)
Google News Personalization System
Google news personalization system은 user clicks의 history를 이용한 recommendation을 실행합니다. 여기에서 user는 gmail acccount에 의해 특정됩니다.
Google news personalization system에서 items 는 new articles이고 click은 positive rating으로 볼 수 있습니다.
위와 같이 *"dislike"_의 표현이 없는 경우 **_unary ratings***라 합니다. 그리고 이러한 경우는 user의 행동에서 추론하는 implicit입니다. 하지만 explicit한 경우에도 적용은 가능합니다.
Facebook Friend Recommendations
Facebook friend recommendations는 product recommendation과는 살짝 다른 goal인 SNS에서의 UX 향상을 가집니다.
Facebook은 link prediction을 위해 structural relationship을 기반으로 합니다.
다른 것들과 알고리즘이 아예 다르다고 합니다.
The Spectrum of Recommendation Applications
Table 1.1는 다양한 recommender systems의 적용한 것에 대한 goal의 table 입니다.
많은 Recommender Systems는 다양한 products(books, movies, ...)에 대한 traditional e-commerce에 집중됩니다.
하지만 Table 1.1을 보면 몇몇 systems는 특정 product에 대하지 않습니다. 예를 들어 google search는 search result에 대해 preducts를 광고합니다. 이는 computational advertising의 범주이지만 Recommendation Systems와 매우 밀접합니다.
비슷하게 Facebook의 친구추천 및 online 채용 추천은 reciprocal recommender라고 불리기도 합니다.
이런 모델들은 recommendation algorithms중 몇몇은 traditional recommender systems와는 꽤 다릅니다.
Basic Model of Recommender Systems
Recommender Systems에서 사용되는 두가지 종류의 data가 존재합니다.
- ratings, buying behavior와 같은 user-item interactions - Collaborative filtering
- user, item에 대한 특정 정보 "profile" - Content-based
knowledge-based recommender systems에서는 분명하게 특정된 user requirements에 기반하여 추천합니다. 이는 과거의 행위보다는 external한 knowledge(domain 지식), 제한을 사용하여 추천함을 의미합니다.
이런 모델 이외에 몇몇 recommender systems는 이런 다른 측면들을 결합하여 만들어 집니다. 이를 hybrid systems라 합니다.
Collaborative Filtering Models
CF (Collaborative filtering)은 ratings의 collaborative power를 사용하여 추천합니다. 하지만 여기에는 CF에 대한 matrices가 sparse하다는 어려움이 존재합니다. 영화를 예를 들면 user는 수많은 movie 중 아주 작은 부분만 볼 수 있습니다.
원서에서는 specified = observed, unobserved = missing = unspecified 로 사용합니다.
CF에서 observed ratings는 다양한 user, items에 대해 괸장히 상관되기 때문에 unspecified ratings는 추론 될 수 있습니다.
그래서 User 간의 Similarity를 통해서 incompleted specified values를 추정합니다.
대부분의 CF는 item간의 correlation 혹은 user 간의 correlation에 집중합니다. 아니면 둘 다에 주목하던가. 게다가 몇몇 모델은 classifier가 missing label에 대해 결과를 내놓듯이 missing value에 대한 답을 찾기 위해 신중히 design된 최적화 techniques를 사용합니다.
이와 같이 모델이 여러 카테고리로 나뉠 수 있는데 크게 두가지 methods로 분류헤보겠습니다.
- Memory-based methods : 이는 _neighborhood-based collaborative filtering algorithms_라 불리기도 하며 neighborhoods를 기반으로 ratings를 예측합니다. 여기에서 neighborhoods가 굉장히 중요한데 이는 두가지 방법으로 정의 될 수 있습니다.
- User-based collaborative filtering : target user A와 similar users에 의해 얻은 ratings로 A에게 추천을 해줌.
Basic idea : user A와 비슷한 사람을 찾고 A의 unobserved ratings에 대해 추천함. similar users group ratings의 average similarity는 row(users)간의 computation으로 구함. - Item-based collaborative filtering : user A로부터의 item B에 대한 rating 예측 위해서, 첫번째로 target item B와 비슷한 items에 대한 Set S를 지정함. 두번째로는 user가 이전에 평가 했었던 Set S에서의 ratings를 기반으로 user A가 B를 좋아할지를 예측함. Similarity는 columns(items)간의 computationMemory-based methods의 이점은 간단하고 설명하기 쉽다는 점입니다. 반면에 단점은 sparse rating matrices에서는 잘 작동하지 않는다는 점 입니다. 물론 앞에서 언급 했든 top-k 추천시에는 좀 괜찮다고 합니다.
- User-based collaborative filtering : target user A와 similar users에 의해 얻은 ratings로 A에게 추천을 해줌.
- Model-based methods : 머신러닝이나 data mining을 사용하는 것.
paramter로 이루어진 모델은 optmization framework로 훈련된다.
이는 sparse matrices라도 높은 수준의 수렴을 이뤄냄.
ex ) 결정트리, rule-based models, Bayesian methods, latent factor models.
비록 Memory-based methods가 simplicity에 대해 이점을 가지고 있다 하더라도, 기존의 heuristic한 방법이며 모든 setting에서 잘 작동하지 않을 수도 있습니다.
하지만 Similarity-based models의 경우 heuristic이더라도 사용되기 때문에 memory-based methods도 고려될 수 있습니다.
Types of Ratings
만약 ratings가 like, dislike에 대해 특정한 scale로 specify 된 경우 continuous value로 측정 되기도 합니다. 하지만 거의 그러지는 않고, 보통 interval을 갖는 discrete한 값에 대한 ratings를 가집니다. (interval based ratings라 불림)
가능한 rating의 수는 다양할 수 있습니다. 보통은 5, 7, 10 point를 사용합니다.
Fig 1.1를 보시면 5 star interval rating의 예가 나와있습니다.
이를 통해 user의 흥미 level에 대한 의미론적 해석을 할 수 있습니다. 이 해석은 물론 merchant에 따라 다를 수 있습니다.
Netflix가 merchant인 경우를 생각해보겠습니다. Netflix는 5 star 중 3은 호의적 평ㅇ가, 2는 호의적이지 않은 평가 입니다. (unbalanced rating scale.) 이러한 경우처럼 중립의 rating이 없는 경우 forced choice rating system이라 부릅니다.
정렬된 categorical values가 이용되는 경우는 ordinal ratings라 불립니다. 이는 Fig 1.2 에 나와있고 직접 보시는게 이해가 더 잘 갈듯 싶습니다.
binary ratings는 like or dislike에 대해 측정하는데, 이때 unspecified values는 0, 1로 추정하는게 가능합니다.
unary ratings는 like는 표현 가능하지만 dislike에 대한 지표가 없습니다. 이 경우에 explicit 보다는 implicit data를 사용합니다. (user preference가 activity(구매하는 행위)로부터 유도 된다.) 하지만 구매하지 않은 행위가 dislike를 무조건 의미하지는 않습니다.
Examples of Explicit and Implicit Ratings
이 부분에서는 Fig 1.3에 대해 이야기 해보겠습니다.
왼쪽 orederd ratings를 보면, 6 by 6의 행렬로 표현을 했는데 실제로는 매우 큰 수 m,n의 m by n 행렬로 나타납니다. (이건 예시용)
여기에서 Ordered ratings는 Higher ratings 일수록 더 높은 positive feedback을 받고 빈 공간은 unspecified value를 의미합ㄴ디ㅏ.
이런 ratings matrix가 utility matrix와 단어적인 실제 의미는 다르지만 같은 의미로 불리기도 합니다. 하지만 utility matrix는 domain에 따라 특정된 기준에 의해 ratings에서 utility로 바뀐 값들로 이루어진 걸 의미할 수 있습니다.
CF에 ratings matrix가 아닌 utility matrix로 사용 될 수는 있지만 보통 ratings matrix로 사용된다고 합니다.
Unary는 positive preference utility matrix로 불립니다. Fig 1.3을 살펴보면 Ordered와 동일한 Set을 다루지만 insight가 굉징히 다릅니다.
user U1과 U3는 Ordered 관점에서 서로 상당히 다른데 Unary에서는 굉장히 similar함을 알 수 있습니다. 이게 바로 Negative 표현의 차이에서 옵니다. 다시 말하자면, Unary ratings는 less expressive합니다. (그래서 implicit!)
Unary ratings는 dislike 사용이 불가하기 때문에 존재하는 중요한 effect가 있습니다. 그건 바로 missing entries를 0으로 취급이 가능하다는 것 입니다.
하지만 learning algorithm에서의 마지막 predict는 0보다 커야합니다. 그래서 추천되는 items는 zero assumption에 의해 가장 큰 양수의 prediction error를 갖는 item을 기반으로 합니다.
만약 zero 가정이 없었다면 상당한 overfitting이 발생할지도 모릅니다. 이 때의 overfitting은 다양한 observed value가 없는 경우의 과적합을 의미합니다.
원서에서는
explicit-feedback matrices에서 ratings는 preference에 대응된다.
implicit-feedback matrices에서 ratings는 confidence에 대응된다.
라고는 하는데 이게 무슨 의미인지는 정확히 모르겠습니다. (Confidence가 의미하는 바가 선호도가 아닌 알고 있다는 그런 의미로 사용된건가..?)
위에서 언급했던 Zero assumption 같은 대체는 explicit의 경우에서는 추천되지 않습니다. explicit의 경우에는 like와 dislike가 둘 다 있고 missing entries가 굉장히 많아서 Zero assumption을 적용한다면 매우 큰 영향을 받을 것 입니다.
물론 Zero assumption에 있어서 unary의 경우에도 약간의 bias가 존재합니다. 하지만 상당히 overfitting을 줄일 수 있기 때문에 이 정도 편향은 감수 할 만 합니다.
Relationship with Missing Value Analysis
CF에서의 Matrix는 매우 크고 sparse해서 Missing Data 분석의 특별한 경우로 볼 수 있습니다. 이러한 방법이 Recommender System에서 많이 쓰이지만 매우 크고 sparse한 matrix에 대해서 특별한 조정이 필요할 수도 있습니다. 결론은 많은 classical missing value estimation methods는 CF에 사용 될 수 있다는 것입니다.
Collaborative Filtering as a Generalization of Classification and Regression Modeling
CF는 분류나 회귀 모델링의 일반화으로 볼 수 있습니다.
label은 missing value에 대한 속성(rating?)으로 볼 수 있습니다.
하지만 분류에서는 missing entries에 대한 열이 제한되어 있는데, CF에서는 뒤죽박죽 섞여 있습니다. 그래서 column 단위가 아닌 entry 단위로 수행된다고 볼 수 있습니다.
결국 CF는 entry 단위로 수행되는 예측에 대한 분류, 회귀 modeling 이라고 볼 수 있습니다.
Content-Based Recommender Systems
Content-based recommender systems는 descriptive(text-based) attributes를 토대로 예측합니다. ratings와 buying behavior가 content 정보와 결합하고 이러한 정보를 기반으로 similar items을 추천합니다.
rating로 label된 item description(content)는 training data로 사용됩니다.
각 user에 대해 training documents는 item의 descriptions에 대응하고 class 변수는 specified ratings or buying behavior 입니다.
이를 통해서 user가 이 item을 좋아할지를 예측하는 분류, 회귀 모델을 구축합니다.
Content-based methods는 new item을 추천하는데 이점이 있습니다. 왜냐하면 new item과 비슷한 item들은 rating이 되어있을 수도 있기 때문입니다.
하지만 여러 단점들도 존재하는데,
- Obvious recommendation : user가 어떤 keyword에 대한 item을 한번도 소비하지 않았으면 이 종류의 item은 추천이 불가함. 이는 추천되는 items에 대한 다양성을 감소시킵니다.
- New user : content-based methods는 해당 user의 history를 기반으로 추천합니다. 그래서 새로운 user에 대해서 취약합니다. robust한 추천을 위해서는 많은 데이터가 필요합니다.
결론적으로 Content-based methods와 Collaborative filtering은 서로 다른 trade-off가 존재합니다.
Knowledge-Based Recommender Systems
Knowledge-based는 similarity metrics가 domain 지식을 기반으로 하는 경우입니다. 이는 종종 Content-based 와 유사하다고 여겨지기도 합니다.
Knowledge-based recommender sysetms는 자주 구매하지 않는 item(automobiles, luxury goods ..)에 유용합니다. 이러한 items는 충분한 ratings가 존재하지 않습니다. (cold start problem)
그리고 이러한 품목에 대한 소비자의 선호도는 자동차의 발전에 따라 선호도도 발전하는 것 처럼 진화 할 수 있습니다.
특정 item은 여러 properties에 대응하는 것과 연관된 특징을 갖고 있을 수도 있고, user들은 그 특징을 갖는 items를 좋아 할 수도 있습니다. ex) car option의 조합
ratings가 추천하는데 있어서 사용되지 않는 경우도 knowledge-based라 볼 수 있습니다.
recommendation process는 user requirements와 item descriptions의 유사도에 의해 진행되거나 user의 특정 requirements의 constraints를 기반으로 합니다.
knowledge based는 이를 수월하게 해줍니다. (Table 1.2)
Knowledge based의 interface에 따른 분류.
- Constraint-based recommender systems : domain knowledge 기반 item attribute에 대한 제약을 두는 경우. Fig 1.5
user가 원하는 결과가 나올 때 까지 constraint 조정 가능
- Case-based recommender systems, Fig 1.6 : user에 의해 특정 "case"가 지정되는 경우
이 경우에 Similarity는 비슷한 item을 찾기 위해 item attributes에 정의 됌.
유사도 측정 기준들은 domain-specific way로 결정되기도 합ㄴ디ㅏ. 따라서 유사도 측정 기준은 domain knowledge를 형성함을 알 수 있습니다.
위의 두 경우를 보면 user의 specified requirements를 변경 할 수 있게 해줍니다. (선택사항을 바꿔가며 검색 할 수 있음.)
이제는 knowledge-based recommender systems에서 interactivty가 어떤 형식으로 취해지는지 봐보겠습니다.
- Conversational systems : feedback loop에서의 반복적 과정을 통해 user preference가 구해짐. item domain이 복잡하고 user preference는 반복적인 Conversational systems에 의해서 결정 될 수 있음.
- Search-based systems : user perference는 질문의 sequence에 의해 이끌어 질 수 있음.
- Navigation-based recommendations : user가 추천된 것에 대해 여러 수정 요청을 지정함. 반복적인 change request로 바람직한 item을 이끌어냄
Knowledge-based methods와 Content-based methods 둘 다 items의 attributes를 사용합니다. 그래서 Knowledge-based methods는 CB와 동일한 몇몇 단점들을 가집니다. ( ex) obvious prediction )
이 둘 사이의 다른점으로는, Content based는 past user behavior를 기반으로 하지만 Knowledge-based methods는 active user의 needs와 interests에 대한 지정에 기반으로 한다는 점 입니다.
Utility-Based Recommender Systems
이 방법은 user가 그 item을 좋아할 확률을 계산하기 위한 product feature 기반 utility funciton을 사용합니다. 그래서 적절한 utility function을 지정하는게 중요합니다.
여기에서 Utility-based recommender system에서 utility value는 사전지식에 대한 function을 기반으로 합니다. 그래서 external knowledge를 통한 function이라 생각할 수 있고 knowledge-based의 한 종류라 생각 할 수 있습니다.
Hybrid and Ensemble-Based Recommender Systems
이제 input이 어떤게 들어오느냐와 어떤 상황 마다 사용하는 다른 시스템을 쓴다는 것을 알았습니다. 하지만 다양한 inpout이 들어올 수 있는 경우는 어떻게 해야할까요??
다양한 input이 들어올 수 있는 경우는 이를 수용할 수 있는 flexibility가 필요합니다.
Hybridization : 최선을 위해 다른 형식의 systems가 결합되는것.
Hybridization으로 flexibility를 얻을 수 있습니다.
hybrid model은 ensemble analysis와 매우 유사합니다. 그리고 이러한 Ensemble based Recommender Systems는 다른 여러개 모델 뿐만이 아닌 동일한 모델들도 결합 할 수 있습니다.
Evaluation of Recommender Systems
앞에서 Recommender Systems를 분류 회귀 모델의 일반화 라고 말했던 것 처럼, 약간의 수정이 필요하긴 하지만 evaluation을 위해 기존 분류 평가 기준을 사용 할 수 있습니다.
Summary
Recommender Systems에서 중요한 알고리즘 종류에 대한 overview를 해봤습니다. (장점, 단점, 무슨 상황에서 효율적인지)
어떤 domain, scenario냐에 따라 다르게 연구, 알고리즘도 달라집니다.
