[논문] Collaborative Filtering for Implicit Feedback Datasets

rainbow/논문

[논문] Collaborative Filtering for Implicit Feedback Datasets

윌_ 2023. 8. 16. 15:50

1. introduction
2. Preiminaries
3. Previous work
4. Our model
5. Explaining recommendations
6. Exerimenal study
7. Discussion

1. introduction

상품이 많아짐에 따라 고객이 원하는 상품을 나열해서 보여주기 위한 과제가 발생하게 되었다.

그 과제를 해결하기 위한 방법으로 추천시스템이 있는데, 추천시스템은 유저와 상품을 프로파일링하고 둘 간의 관계를 찾아내는 기술에 기반한다.

Implicit data의 특징

이 논문은 implicit data를 다룰 때, explicit data를 다루는 알고리즘과 구분 짓기 위해 implicit data의 몇 가지 특징들을 식별하는 게 중요하다고 말한다.

1) 부정적인 피드백(data)는 없다(=알 수 없다).

어떠한 user가 아이템을 검색하지 않으면 그 값이 0이다. 하지만, user가 아이템을 관심이 없어서 검색하지 않은 것이 아닌 인지를 못한 것일 수 있다.
대부분의 explicit dataset을 다루는 recommender들은 0값을 , 선호하지 않는다고 판단하여 'missing data'로 간주하여 알고리즘에서 생략한다. 그러나 implicit dataset에서는 'missing data'가 data의 대부분이기에 이를 포함시키고 분석을 진행하고, 이를 설명할 수 있어야한다.

2) Implicit data는 본질적으로 noisy하다.

user 행동을 기반으로 선호를 유추할 수 있지만, 이것이 필수적으로 인과관계가 있는것은 아니다.
예를 들어, 윌(user)이 온라인 쇼핑몰 도서(item) 판매 페이지에서 오래 체류한 시간(value)을 가지고, 윌은 해당 도서를 좋아하는 것으로 볼 수 있다. 하지만, 우연히 페이지가 켜두고 다른 업무를 보다 쌓인 시간일 수도 있다. 즉, ‘오래 머물면 해당 도서를 좋아할 것이다.’라는 가정이기 때문에 예시처럼 변수가 많다.

3) Implicit data는 'confidence' 속성을 지닌다.

explicit data가 평점과 같은 preference를 지니는 반면, implicit data는 사용자 행위의 빈도를 신뢰성(confidence)을 반영한다.
즉, large value가 높은 선호도가 아니다. 예를 들어, 선호 기준을 user들의 TV Program(item)의 시청시간(value)으로 본다면 흥행 영화가 도출될 것으로 예상하지만, 정작 시청시간이 큰 값은 오랜 시간 방영하는 시리즈물이다.
하지만, large value는 선호가 아닐 뿐 분명하고 유용한 데이터이기 때문에 confidence로 처리한다.

4) Implicit data은 적절한 평가지표가 필요하다.

명시적 피드백이 있는 경우엔 예측 성공을 계산하기 위해 MSE(Mean Squared Error)같은 평가 지표가 있다.
하지만, Implicit feddback같은 경우에는 적절한 평가지표가 필요하다. 예를 들어, user TV 시청 데이터를 활용할 때, 재차 시청한 영상은 어떻게 평가할 지(ex. 재차 봤으면 그 선호도에 가중치를 줄 지), 동시간대 TV program들은 어떻게 평가할지(한 사람이 두 가지를 동시에 볼 수는 없기에) 와 같은 상황에서는 이를 적절히 평가하기 위해서 그에 맞는 지표가 필요하다.

2. Preliminaries

u, v: 유저

i, j: 상품

r_ui : 유저와 상품 간의 관계

explicit data에서는 유저 u가 상품 i에 대한 점수

implicit data를 유저 u가 상품 i를 몇 번 시청하였는지에 대한 데이터라 가정

→ ‘r_ui = 0.7’ (70%만 시청했다), ‘r_ui = 2’ (2번 시청했다)

3. Previous work

3.1 Neighborhood models

평점 행렬로부터 유저 간 유사성을 사용하거나 아이템 간 유사성을 사용하는 접근법이다. 유사성은 주로 피어슨 상관계수로 값을 낸다. 이웃기반 모델은 다음과 같이 두 가지 모델이 있다.

user-based model

비슷한 유저는 동일한 아이템에 대해 비슷한 평점을 준다. 즉, 윌과 마리가 과거에 영화 평점을 비슷하게 주었다면, 윌이 영화 ‘콘크리트 유토피아’에 준 평점을 이용해, 마리가 아직 시청하지 않은 ‘콘크리트 유토피아’ 평점을 예측할 수 있다는 의미다.

item-based model

비슷한 아이템은 동일한 유저에게 비슷한 평점을 받는다. 즉, 마리가 예전에 본 영화인 ‘기생충’ 평점을 가지고 아직 보지 않은 ‘콘크리트 유토피아’ 평점 예측에 활용 가능하다는 뜻이다.

실제로는 유저 u의 상품 i에 대한 평점을 구하기 위해, 상품 i와 비슷한 상품 k개 유저 u의 평점을 가중평균으로 구하여 i에 대한 예측값을 도출한다.

Q. 피어슨 상관계수로 가장 비슷한 상품 평점을 따르는 것이 아닌, 비슷한 상품 k개로 가중평균을 내는 이유는 무엇일까.

A. user-based model을 예시로 들어보자. 나와 시청 기록이 비슷한 유저의 평점을 가지고 내 평점을 예측한다. 하지만, 시청 기록이 비슷한 유저였지만, 이 사람은 대체로 모든 컨텐츠에 만점을 주는 사람이라면 내 성향과 다르게 평점도 만점으로 예측될 것이다. 이렇게, 유저들마다 스케일이 다르기 때문이다. 어떤 유저는 아이템의 평점을 대체로 높게 주고, 어떤 사람은 아이템의 평점을 대체로 낮게 주는 것처럼 말이다. 따라서 가중 평균을 이용해 특정 아이템의 평점을 예측한다. 이러한 유저 평점 스케일 문제를 맞아주기 위해서 또 다른 방법으로는 사전에 평점 행렬 표준화해주는 작업도 좋다.

3.2 Latent factor models

보다 전반적인 잠재 특성을 반영하기는 위해 CF의 접근법의 대안으로 Latent factor model이 생겼다.

pLSA, neural networks, LDA 등 model은 SVD 기반 행렬 분해 개념이 활용된다.

SVD기반 행렬 = user-latent 행렬 * item-latent 행렬

일반적인 loss of Latent-Factor models (람다 이하는 모델 발산 규제)

4. Our model

implicit feedback에 적합한 모델을 설명하는 section이다.

유저 잠재벡터(x_u), 상품 잠재벡터(y_i) 추정하기

explicit feedback data 활용하는 모델에서 유명한 matrix factorization technique와 유사하다.

다만, 중요한 두 가지 차이점이 있다. 첫번째는, 다른 신뢰도 레벨을 설명할 수 있어야한다. 다음은, 최적화는 모든 u, i 짝에 대해 설명할 수 있어야한다. 이제 유저와 상품 잠재벡터를 추정하는 과정을 살펴보자.

1) 잠재 벡터를 추청하는데 사용할 label data

유저 u의 상품 i에 대한 선호도(implicit dataset에선 confidence를 preference로 봄)을 관심여부(0, 1)로 변환한다. 뒤에 나올 잠재 벡터를 추청하는데 사용할 label data로 만드는 과정이다. 식은 아래와 같다.

2) 선호도 p_ui에 대한 신뢰도

r_ui값이 클수록 상품에 대한 선호가 높음을 의미하지만, 앞서 0,1로 바꿔주는 과정에서 상품 선호 차이에 대한 weight 반영이 빠져버리게 되었다. 이를 반영해주기 위해 c_ui를 활용한다. 예를 들어, 5시간 시청한 상품과 1시간 시청한 상품이 있을때, 5시간 시청한 상품에 더욱 주기 위함이다. 본 논문에서는 알파값을 40으로 잡으니 좋은 결과물이 나왔다고 한다. 데이터나 상황에 따라 다르게 적용해보는 노력이 필요할 듯하다

3) 유저 잠재벡터와 상품 잠재벡터값

유저 잠재벡터와 상품 잠재벡터값은 위 식을 최소화하는 값으로 구할 수 있다.

4) 최적 잠재벡터 값 유도

Time complexity

ALS는 explict dataset에서 unknown data는 missing data로 취급하며 이용되었었다. 반면, implicit dataset에서는 다른 접근이 필요하다. 변수 structure를 활용해 ALS가 implicit dataset에서 작동하도록 한다.

먼저, x_u의 시간복잡도에 대해 알아보자. 과정은 다음과 같다.

모든 user factor를 recomputing 한다.
item- factor 행렬을 n x f 라 하자.
모든 user에 대해 반복적으로 돌기 전에 f x f 행렬 Y^T * Y를 계산한다. ⇒ O(f^2n)
모든 user u 에 대해 n x n 행렬인 대각 C_u를 정의하고 binary한 값으로 이루어진 vector P(P = P_ui) 를 정의한다.
연산 병목화(bottleneck)는 Y^T * C_u * Y를 구할때 발생한다.
- 이를 위해 Y^TC_uY = (Y^TY)+(Y^T*(C_u-I)*Y) 로 나눈다. ⇒ O(f^2n_u)
- 앞 부분 괄호는 앞서 과정 3에서 계산했다.
- 뒤 괄호 C_u-I에서 오직 n_u만이 non-zero값을 가진다. 즉, n_u 또한 r_ui > 0 인 것들이다. 따라서 n_u는 n보다 작다.
C^u * p(u)도 마찬가지로 non-zero가 $n_u$만큼 있기에 시간복잡도는 유지된다. ⇒ O($f^2n$)
(Y^TC_uY+λI)^{-1}의 역행렬 시간복잡도는 다음과 같다. ⇒ O(f^3)
정리한 것을 Xu에 대한 식에 적용해보면 모든 user에 perform됨으로 총 O(f^2N+f^3m)
- 여기서 N = Σ_u n_u를 나타낸다. (전체에서 non-zero값 갯수 합)
- m은 모든 유저 수를 의미

중요한 것은 running time은 input_size와 선형적이라는 점이다. 일반적인 f의 값은 20~200의 값이다.

반대로, y_i의 시간복잡도는 다음과 같다. ⇒ O(f^2N + f^3n)

여기서 n은 상품의 수

5. Explaining recommendations

ALS 알고리즘의 강점은 설명가능한 추천이라는 점이다. 기존 이웃기반 모델들과는 달리 latent factor 모델들은 설명하기가 까다로웠다. 유저 과거 행동과 추천 결과물 사이에 user-factor를 경유하기 때문이다.

해당 논문에서는 다음과 같이 계산할 수 있다고 한다.

유저 u의 아이템 i에 대한 선호를 위와 같이 표현할 수 있다.

앞서 구한 x_u를 대입하면 위와 같이 다시 변환할 수 있다.

위와 같이 f x f 행렬부분이자, 유저 u와 연관된 가중치 행렬을 W^u로 나타낸다고 가정하자.

그렇다면 유저 u에게서의 상품 i와 상품 j 간 유사도를 위와 같이 구할 수 있다.

그러면 유저 u의 상품 i에 대한 예측 선호값을 위와 같이 계산할 수 있게 된다.

위 수식을 활용해 예측선호값을 구한다면, 이 값을 추천하는 기준으로 삼고 근거로 들 수 있게 된다.

또한 사용자의 과거 행동을 두 가지로 구분지을 수 있다.

Cui 값(유저 u와의 신뢰도 값) 2. S^u_ij 값 (타겟 상품 i와의 유사도 값)

6. Experimental study

Data description

1) 유저(user)는 30만 개의 셋탑박스에서 수집되었으며, 상품(item)은 TV 프로그램 1.7만 개, training data는 유저 u와 상품 i에 대한 r_ui를 담고 있다. r_ui는 TV 시청 시간(분)으로 이루어져있다.

프로그램의 중복 시청까지 모두 집계해보니, non-zero value는 3200만 개이다. 유저와 상품 수를 곱해보면 30만 X 1.7만 = 510000만 개가 나올 수 있지만, 3200만 개이기에 굉장히 sparse한 행렬임을 알 수 있다.

2) 4주간 시청 기록을 train data로 활용했고, 이어지는 1주를 test data로 구성하였다.

이어지는 1주를 데이터로 활용하는 이유: TV 프로그램 특성상 그 기간이 길어지면 item이 달라질 수 있기 때문에 타당성을 부여하기 위함

3) TV 시청 데이터는 일주일마다 반복되는 경향이 있기에 이러한 주기적 시청 영향을 데이터에서 제거한다.

반복적으로 보는 프로그램보다 아직 보지 못했던 프로그램이나, 최근에 보지 않았던 프로그램 추천이 더욱 유의미하기 때문
test data에 있는 item이 training data에도 시청된 이력이 있다면 이 또한 제거한다.

Test set에서 half 시간 이하로 본 데이터는 zero로 바꾼다.

유저가 좋아하는 프로그램이라고 판단하기에는 시청 기간이 적다. r_tui<0.5

5) 정제 과정을 거친 r_tui의 non-zero는 약 200만 개다.

6) r_ui에 log scaling 적용한다.

TV 프로그램 시청시간은 중복시청까지 고려하면 한번도 보지 못한 프로그램과 중복시청 프로그램 간의 range가 너무 넓어지기 때문에 range를 좁히기 위해 정규화해준다.

7) 연속적으로 방영되는 프로그램 시청 기록 있을 시 down-weight한다.

TV 채널을 틀고 프로그램 시청 후 이어서 방영되는 프로그램 t, t+1, t+2…에 대한 데이터가 있을때, 이를 유저가 원해서 본 것 인지 아니면 계속 틀어두기만 한 건지 모르기 때문에 down-weight를 적용한다. 아래와 같은 식을 적용하고, a= 2, b = 6 대입하는 것이 경험적으로 결과가 좋았다고 한다. t 번째 프로그램에 대한 가중치인데, t=3일 때 거의 r_ui는 절반으로 줄어든다. 채널 변경없이 t=5가 되면 거의 0에 가까워진다.

Evaluation methodology

1) 각 유저별로 가장 추천할 상품부터 가장 덜 추천하는 상품까지 정렬된 리스트를 산출한다.

2) recall 기반 지표를 활용한다.

implicit data는 비선호를 나타낼 수 없다. 싫어서 안본 것인지, 그냥 몰라서 못본 것인지 구분이 불가하기 때문이다. 그렇기에 모델이 제안한 추천에 대한 반응을 트래킹할 수 없다. 그렇기에 실제
recall = TP / TP + FN
- 선호 예측하고(positive) 맞춤(true) / 선호 예측하고(positive) 맞춤(true) + 비선호 예측하고(negative) 틀림(False))
- 결국 분자, 분모 모두 유저가 본 기록으로 수치화 가능
cf. precison = TP / TP + FP
- 선호 예측하고(positive) 맞춤(true) / 선호 예측하고(positive) 맞춤(true)+ 비선호 예측하고(negative) 맞춤(positive)
- FP를 알 수가 없음 → implicit은 negative함을 증명할 수 없기 때문

3)rank_bar를 활용한다.

recall 기반으로 다음 식을 고안해내었다. 실제 positive data를 이용한 지표다.
rank_ui는 1)에서 추천할 상품 리스트를 가지고 percentile ranking 값을 활용했다.
- 그렇기에 rank_ui = 0%라면 유저 u에게 가장 추천할 상품 i를 의미한다.

이로써 rank_bar의 값이 낮을 수록 모델이 우수함을 의미한다. 유저가 실제로 본 상품과 추천된 상품이 많이 일치함을 의미하는 것이다. 또한 rank_bar값이 50% 이하인 경우에만 모델이 유의미하다는 해석이 가능하다. 랜덤 추천 시스템이 rank_bar = 50% 정도의 수치를 띄기 때문이다.

Evaluation results

본 논문에서는 Our model의 factor의 수(f)를 10~200까지 시도했다. 또한 다른 2개의 모델과 비교했다.

첫 번째 모델은 popularity 모델이다. program의 인기순대로 추천 결과를 정렬한 모델이다. 두 번째 경쟁모델은 neighborhood based(item-item) 모델이다. 모든 neighbor의 set을 이용했으며 cosine similarity를 사용했다.

결과는, popularity 모델은 factor수와 관계없이 rank_bar가 약 16.46%, neighborhood based 모델은 factor 수와 관계없이 rank_bar가 약 10.74%이 도출되었다. popularity 모델은 아무런 자원의 소비없이 유의미한 값이 나왔지만, 이는 개인화 추천과는 거리가 멀다. 모두가 선호하는 상품이 추출되기 때문이다.

Our model은 factor가 증가할수록 rank_bar가 줄어 들었으며 200일경우 8.35% 값을 가졌다. 또한 상위 1%의 추천 program이 전체 test 시청 시간의 27%를 차지했다.

<평가 결과 그 외의 사항>

1. Cui와 Pui로 나눠준 형태인 우리 model은 기존 Latent model보다 성능이 좋았다.

2. 규제화로 적용된 λ는 150으로 수행했다.

3. Program을 인기순으로 15등분해 진행했으며, 인기있는 Program 집단일 수록 예측 성능이 좋았다.

해당 모델에서도 여전히 인기없는 프로그램 추천하는 것이 더 어려웠다.
explicit data와 달리 데이터의 많고 적음이 예측성능에 영향을 덜 끼친다.

4. 모델의 설명성: 기존 latent 모델과 달리 추천의 설명이 가능하다.

앞서 다룬 내용에서 item간 유사도를 구할 수 있기 때문이다. 해당 식은 아래와 같다.

즉 어떤 추천 program과 비슷한 program들의 목록을 알 수 있다.
대략적으로 TOP 5 similar programs가 추천된 program의 약 35~40%를 설명하며, 이는 시청한 다른 많은 프로그램이 추천에 대한 input으로 활용된다는 것을 의미한다.

7. Discussion

<결론>

해당 model은 기존 latent model에서 r_ui 대신 Pui와 Cui를 도입해서 모델의 성능을 향상시켰다. 이 Pui, Cui는 사람들의 선호와 비선호를 명시하지 않는 implicit dataset에서 활용하기에 매우 유용하다. 또한 모든 data를 missing data 까지도 모델에 반영할 수 있다.
모든 data를 다 반영하는 것은 확장성 측면에서 문제가 있다. 일반적으로 user들의 item에대한 availablity는 작기 때문이다. 따라서 이러한 문제점을 모델의 대수적 구조를 탐색하면서 해결한다. zero-preference로 처리하면서 해결한다. <시간복잡도> 부분 참고!
추천 결과에 대해 설명이 가능하다. neighborhood 방식으로 최근접 item을 보여주는 방식으로.

<향후 발전 방안>

zero-preference로 처리한 것들을 나누는 방안이 있다. zero-preference 처리하였지만, 선호하지 않아서가 아닌, 몰라서 혹은 동시간대에 더 선호하는 작품이 했기 때문에 zero-preference처리된 경우가 있을 수 있다.
유저들의 not watch action에 대한 case연구가 필요하다. 우리는 새로운 상품을 유저에게 추천해주기 위해 재차 본 프로그램을 평가에서 제외시키는 작업들을 했는데, 좀 더 유저에 대한 깊은 케이스 스터디가 필요하다.

저작자표시

티스토리