[추천시스템 논문] SoRec: Social Recommendataion using probilistic matrix factorization 리뷰

SoRec: Social Recommendataion using probilistic matrix factorization 리뷰 

https://dl.acm.org/doi/pdf/10.1145/1458082.1458205?casa_token=r_PBboPCHBcAAAAA:zh1uQnvai_DfD5CvXnaD728LF8diLve6zzkbsV5SSEoX924EmTdrFZfAmJsvKvYD4KayDzrgC0RAYmU 

SoRec | Proceedings of the 17th ACM conference on Information and knowledge management

 

 

 1. Introduction

추천 시스템의 대표 종류인 협업 필터링이란 비슷한 유저나 아이템 정보를 이용해서 유저의 선호를 추측하는 방법입니다.

 

기존 협업필터링에는 다음과 같은 한계가 있습니다.

(1) 첫 번째로 대부분의 데이터에서 유저와 아이템 간의 관계를 나타내는 행렬을 만들면 채워진 칸보다 빈 칸이 더 많습니다. 유저 간 겹치는 아이템이 많아야 성능이 좋은 memory based 협업 필터링은 희소성 문제로 성능이 그다지 좋지 않았습니다

(2) 두 번째로 협업 필터링 방법들 대부분 한 번도 평점을 매긴 적이 없는 처음 보는 유저에 대해서는 예측할 방도가 없었습니다.

(3) 마지막으로 현실 세계에서 사람은 주위의 친구들과 둘러싼 환경에 의해 더 영향을 많이 받는데 협업 필터링에서는 이런 사회적 교류를 고려하지 못하고 있습니다.

 

저자는 특히 마지막 (3)에 주목합니다.
기존 추천시스템은 유저가 독립적이라고 가정하기 때문에 유저 간의 교류나 연결성을 무시하게 됩니다.

하지만 사람들의 사회적 교류는 생각보다 사람들의 관심사에 더 큰 영향을 보이고 있었습니다. Sinha라는 저자의 논문에서는 친구랑 시스템이 추천한 아이템 중 질이나 유용성에 있어 친구 추천이 훨씬 선호되고 있었습니다. 또 다른 논문은 MSN 메신저의 채팅 데이터와 검색 기록을 조사했고,
그 결과 자주 채팅하는 사람들끼리 비슷한 관심사를 보이는 것으로 밝혀졌습니다.

따라서 추천시스템의 정확도를 개선시키기 위해서는 유저가 매긴 평점뿐만 아니라 소셜 네트워크 역시 고려해야 하는 것을 알게 되었습니다.

 

이러한 배경 속에 등장한 SoRec은 소셜 네트워크 그래프와 유저 아이템 행렬을 결합한 추천시스템인 Social recommendation을 제안하고 있습니다. 저자는 두 가지 다른 데이터를 결합하기 위해 user latent feature space 즉 유저에 관한 잠재요인 벡터를 공유하는 방법을 제시합니다.

 

본 논문의 contribution을 요약하면 다음 세 가지와 같습니다.

우선 Sorec 모델은 PMF의 확장모델로 social network라는 사이드 정보를 잘 활용해서 기존 sota 모델보다 더 좋은 성능을 보였습니다.
두 번째로 SoRec모델은 정보가 부족한 유저들에 대해서도 더 잘 예측하는 것으로 밝혀졌습니다.
마지막으로 SoRec은 연산 시간에 있어서도 데이터 개수에 따라 기하급수적으로 증가하지 않고, 선형적으로 증가해, 큰 데이터셋에서 무리 없게 적용가능했습니다.

 

2. Related Work

SoRec은 PMF와 Trust aware collaborative filtering이라는 두 개의 모델을 바탕으로 발전한 모델입니다.

 

우선 PMF는 latent factor인 잠재요인을 활용한 모델 중 가장 대표적인 모델로, 유저와 아이템 행렬을 더 낮은 차원으로 표현하여 빈칸을 예측합니다. PMF는 이 잠재 요인과 유저들의 평점 분포를 가우시안 분포에 따르도록 모델링하여 성능 향상에 기여하였습니다. 

 

SoRec이 참고한 또 다른 모델은 Trust aware collaborative filtering method입니다.

이 메소드는 유저들의 소셜 네트워크 정보를 추천시스템에 활용했다는 의의가 있는 모델입니다.
하지만 이 모델은 유사도 함수를 활용하는 memory based model이었기 때문에 정보가 적은 유저들은 잘 대응하지 못했고, 큰 데이터셋에 활용하기 어렵다는 문제도 있었습니다. 하지만 SoRec은 잠재 요인 기반 모델이라서 이러한 문제점을 어느 정도 극복할 수 있었습니다.

 

 

3. Social Recommendation Framework

세번째 장에서는 본격적으로 모델의 목적함수에 대해 알아볼 예정입니다.

 

3.1. Toy Example

Social recommendation을 하기 위해서 SoRec 모델은 두 개의 데이터를 활용합니다. 첫번째는 소셜 네트워크 그래프이고 두번째는 유저와 아이템 간 평점을 기록한 user item matrix입니다.

 

첫번째 소셜 네트워크 그래프의 예시부터 살펴보면 그래프의 노드는 유저를 뜻하며 노드를 잇는 엣지는 유저 간의 관계를 의미합니다. 그림의 예시에서는 6명의 유저가 있고 8개의 관계성이 존재합니다. 각 엣지 위에 적힌 가중치는 한 유저가 다른 유저에 대해 얼마만큼 신뢰하는지를 보여줍니다. 

 

다음으로 (b)는 기존 행렬분해에서 많이 등장했던 유저 아이템 행렬입니다. user item matrix에서 나타나는 유저와 social network graph에서 나타나는 유저는 동일하게 6명으로 각각이 동일 인물을 의미하는 것을 알 수 있습니다.

만약 user item matrix로 행렬 분해을 하게 되면 가장 오른쪽 예시와 같습니다.  U는 유저의 잠재요인 벡터가 되고 V는 아이템의 잠재요인 벡터가 됩니다. PMF 같은 기존 mf 모델들은 U와 V의 내적을 활용하여 빈 값을 예측했었습니다.
SoRec은 user item matrix 뿐만 아니라 소셜 네트워크 그래프 정보도 활용하게 되면 더 예측이 잘 되는지 알아보고자 했습니다. 

 

 

 

 

그림은 Social Recommendation 모델의 전체 구조를 보여줍니다.

가장 가운데의 U는 user latent feature space를 의미하고, V는 아이템 latent feature space를 의미합니다.

그래서 PMF와 다르게 새롭게 등장한 Z는 social graph의 factor matrix를 의미합니다. U와 Z의 크기는 유저 명 수에 의존하고 V의 크기는 아이템의 개수에 의존합니다.

그다음 R과 C는 각각 데이터셋인 rating matrix와 social network matrix를 의미합니다.
U와 V를 내적해서 R을 예측하게 되고 U와 Z를 내적해서 C를 예측하게 됩니다.

 

3.2. Social Network Matrix Factorization

Social recommendation은 두개의 데이터셋을 예측하게 됩니다. 그 중 C social matrix에 대한 내용부터 알아보도록 하겠습니다. SoRec은 PMF와 굉장히 유사한 증명 과정을 보입니다.
SORec은 목적 함수를 정의하기 위해 베이즈 정리를 활용했습니다.

 

 

베이즈 정리란 두 확률 변수의 사전 확률과 사후 확률 사이의 관계를 나타내는 정리입니다.

 

SoRec은 PMF 논문처럼 그래프 데이터셋 C에 대한 조건부 확률을 두 latent vector을 내적한 값을 평균으로 갖고 있는 가우시안 분포를 정의합니다.

작은 cik는 user i가 user k에 대해 얼마나 신뢰하고 있는지 trust value을 의미합니다.
N()은 안의 값을 각각 평균과 분산을 갖는 가우시안 분포를 의미합니다. 옆에 둘러싸고 있는 I는 indicator function으로 user i가 user k를 알면 1, 모르면 0의 값을 갖습니다.

logistic function은 Ui와 Zk의 내적 결과를 0에서 1 사이 값으로 만들기 위해 사용됩니다.

 

latent factor인 U와 Z의 사전 확률은 일반적으로 평균 0과 알려진 분산을 가진 가우시안 분포로 모델링됩니다. (2) 식을 보면 가우시안 분포에서 평균을 의미하는 위치에 0이 있기 때문에 0을 평균으로 갖는 가우시안 분포임을 알 수 있습니다.

 

따라서 U와 Z에 대한 사후확률은 사전확률과 가능도의 곱과 비례하게 되고 이 정리와 방금 구한 식들을 활용하면 3번 식을 구할 수 있습니다.

 

 

기존에 정의했던 cik 즉 유저가 다른 유저를 신뢰하는 값을 의미합니다.

하지만 현재 cik는 소셜 네트워크 그래프 정보를 일부 무시하고 있습니다.

이 노이즈를 최소화하고자, 모델은 cik 값에 추가적인 정보를 반영하게 됩니다.

만약 user i가 user k를 좋아하더라도 user i가 많은 유저를 좋아하면 confidence of trust value인 cik는 줄어들게 만들었고, 반면 user k 가 많은 유저로부터 신뢰받고 있다면 cik 값은 증가하게 했습니다.

 

3.3. User-Item Matrix factorization

user item matrix 역시 같은 과정을 거칩니다. 만약 user item matrix인 R과 분산이 주어지면,. latent factor인 U와 V에 대한 분포가 어떨지 그 확률을 구하게 됩니다.

 

user-item matrix R에 대한 조건부 확률은 두 latent vector을 내적한 값을 평균으로 갖고 있는 가우시안 분포로 정의할 수 있습니다. latent factor인 U와 V의 사전 확률은 평균 0으로 가진 가우시안 분포로 모델링됩니다.

 

 

따라서 user item 행렬 분해도 social recommendation 행렬 분해와 비슷한 식을 구할 수 있습니다.

 

3.4. Matrix Factorization for Social Recommendation

하지만 가우시안 분포 공식 안에는 exp로 표현되는 지수 함수가 있습니다. 지수 함수 결과는 자칫하면 너무 큰 숫자가 될 수 있기 때문에, 양 쪽에 로그를 씌워서 식을 변경합니다.

 

로그 사후확률 식을 최대화하는 것은 이 L 목적 함수를 최소화하는 것과 같게 됩니다.

 

 

목적함수의 로컬 미니멈은 graident descent를 진행해서 찾을 수 있으며
논문은 모델의 복잡도를 줄이기 위해서 람다U = 람다V= 람다Z를 모두 같다고 가정했습니다.

 

3.5. Complexity Analysis

gradient descent에서 SoRec의 시간 복잡도를 알아낼 수 있습니다.

SoRec 모델의 시간 복잡도를 빅오 표기법으로 표현하면 O(ρRl + ρCl)이 됩니다.
여기서 ρ(rho)는 각 행렬의 비어있지 않은 데이터의 개수를 의미합니다.

이 식은 데이터 개수에 따라 계산 시간이 선형적으로 증가한다는 뜻으로 데이터가 많다고 해서 연산 시간이 기하급수적으로 커지지 않는 점을 알 수 있습니다.

 

 

4. Experimental Analysis

4장에서는 SoRec모델을 다른 Sota 모델과 비교한 실험 내용을 담고 있습니다.

 

4.1. Description of the Epinions Dataset

SoRec은 이-피니언스 데이터셋을 실험 데이터셋으로 선정하였습니다. 이-피니언스 닷컴은 1999년에 만들어진 지식 공유 사이트로, 유저는 회원가입을 하여 여러 가지 토픽에 대해 의견을 나누거나 리뷰를 남길 수 있습니다. Epinions의 유저는 다른 유저를 trust하거나 block할 수 있었는데 Epinions 사이트는 이를 활용해 유저가 자기가 trust한 유저의 리뷰를 먼저 보도록 리뷰들을 재정렬해주었습니다. 이러한 특성 덕분에 Epinions는 SoRec 모델의 아주 적절한 데이터셋이었습니다.

데이터셋은 약 4만명의 유저와 13만 개의 아이템으로 구성되어 있고 총 리뷰 수는 66만개였습니다. 유저 간의 trust 관계를 나타내는 데이터셋은 약 48만 개의 데이터가 있었습니다.

 

4.2. Metrics

논문은 평가지표로 MAE인 평균절대오차를 사용했습니다.

 

4.3. Comparison

SoRec은 MMMF, PMF, CPMF 모델과 성능을 비교했고, 실험에서 파라미터 람다C는 10, 람다 UVZ는 0.001로 고정했습니다.

그 결과 SORec은 다른 모델에 비해 최대 11%, 최소 7% 성능이 향상했습니다.

특히 SoRec 모델이 PMF의 확장판임을 감안하면 item matrix만 사용했을 때보다 Social network graph까지 활용했을 때 성능이 확실하게 좋아졌습니다.

 

4.4. Impact of parameter lambada C

SoRec 모델은 두 가지 데이터셋을 사용했습니다. lambdaC는 두 데이터셋의 사용 비율을 결정해줍니다. 만약 lamdba C = 0이면 user item matrix만 사용한다고 볼 수 있고, lambda C가 무한대면 social network를 대부분 사용한다고 볼 수 있습니다.

위의 표는 lambdaC의 변화에 따른 MAE 점수 변화를 보여주고 있는데 여기서 lamdba C가 10~20일 때 가장 성능이 좋고, 양 끝으로 갈수록 MAE 값이 높아지고 있습니다.

이 현상은 두 데이터셋 중 순수하게 하나만 쓰는 것보다 혼합해서 사용하는 것이 더 좋다는 것을 보여주고 있습니다.

 

4.5. Performance of different users

논문이 또 알아내고자 했던 점은 유저가 내린 평점이 적을 때 social network graph가 도움이 되는지였습니다. 이를 확인하기 위해 SoRec은 유저가 내린 평점 개수에 따라 다음 10개의 그룹으로 나눈 후 실험을 진행했습니다.

그 결과 SoRec은 유저의 rating이 비교적 많았을 때도 성능이 좋지만, 아래 분포처럼 rating이 적은 유저가 많을 땐 더 눈에 띄게 잘 예측했습니다.

 

4.6. Efficiency Analysis

저자는 실제 훈련 시간을 통해 데이터셋의 증가에 따라 학습 시간이 선형적으로 증가하고 있음을 설명합니다. 20% 데이터를 쓸 때는 5분도 걸리지 않았고 99% 데이터를 활용할 때 18분만 필요했습니다. 즉 데이터가 4배 이상 커져도, 시간이 크게 증가하지 않은 것을 알 수 있습니다.

 

 

5. Conclusion and future work

본논문은 새로운 social recommendation framework를 제안합니다. user-item rating matrix와 social newtork를 pmf 방식으로 결합했습니다. 실험은 우리 모델이 여타 sota모델에 비해 성능이 우수한 것을 보여주고 큰 데이터셋에서도 활용 가능한것을 알 수 있습니다. 더 나아가 datafusion 방식은 social recommendation뿐만 아니라 social search, 정보 복원 데이터 마이닝 등 다양한 태스크에서 활용 가능한 것을 알 수 있습니다.