[RecSys] Embarrassingly Shallow Autoencoders for Sparse Data (2019)

whatSup CheatSheet·2022년 8월 31일
0

RecSys

목록 보기
13/13
post-thumbnail

Intro

최근 협업 필터링에 딥러닝을 적용한 많은 모델들이 좋은 성능을 보여왔습니다. 그러나 컴퓨터비전과 같은 분야와는 다르게 적은 은닉층을 가진 모델이 최고의 추천 정확도를 달성하고 있습니다. (따라서) 이 논문에서 우리는 더 극단적으로 은닉층이 없는 선형 모델을 정의합니다.

입력 벡터는 사용자가 상호작용한 아이템을 나타내며, 모델의 목표(출력에서)는 사용자에게 추천할 최고의 아이템을 예측하는 것입니다. 이 모델은 autoencoder처럼 입력을 출력으로 복원시키는 과정을 통해 수행됩니다. 따라서 우리는 이를 'Embarrassingly Shallow Autoencoders'라고 이름지었습니다.

Model Definition

  • UU: 유저 수
  • II: 아이템 수
  • XX: 유저*아이템 크기의 상호작용 행렬(input data)
    • sparse, binary(implcit data)
    • 상호작용 -> 1, 상호작용하지 않음 -> 0으로 표기
  • BB: 아이템*아이템 크기의 가중치 행렬
    • 모델의 parameter
    • 이때 가중치 행렬의 diag(B)diag(B)는 0으로 제한됩니다(항등행렬 II가 되는 것을 방지(slim논문에서 나왔었던 방법)).
  • Suj=XuBjS_{uj} = X_u*B_j : 아이템 j가 유저 u에게 주어졌을 때의 predicted score

Model Training

가중치 행렬 BB를 학습시키기 위한 목적식은 다음과 같습니다.

  • 목적식으로 square loss를 사용한 이유는 Closed-form solution을 허용하기 떄문입니다.
    • || F||_F : Frobenius norm (vector의 L2 norm을 matrix로 확장한 것(참고))
    • λ\lambda : 모델에 사용되는 유일한 하이퍼파라미터입니다.

Closed-Form Solution

Model Training의 목적식은 Closed-Form으로 풀 수 있습니다.

  • (제약조건이 포함되어 있는 Optimization 문제를 해결하기 위해) 라그랑주 승수법(Lagrangian multipliers)을 통해 제약조건(diag(B)=0diag(B) = 0)을 목적식(minXXBF2+λBF2||X-XB||^2_F+\lambda\cdot||B||^2_F)에 적용합니다.
    • 이때, γ\gamma = (γ1,...,γI)T(\gamma_1, ...,\gamma_{|I|})^T는 Lagrangian multipliers의 vector입니다.
  • (위에서 말한) 제약조건이 포함된 Optimization 문제는 Lagrangian을 최소화함으로써 해결할 수 있는데, 이에 대한 필요조건으로서 우리는 도함수를 0으로 설정(==LL의 도함수를 0으로 만드는 BB를 찾는 것) 하여 항을 재배열한 뒤 가중치 행렬의 추정값 B^\hat{B}을 산출합니다
    • 이때, diagMat()diagMat()는 대각행렬과 단위행렬 II를 의미합니다.
  • 공식(B^\hat{B})의 앞 부분((XTX+λI)1X^TX+\lambda I)^{-1})을 P^\hat{P}로 두고 방정식을 다시 정의하면, 다음과 같이 나옵니다.
    • 마지막 줄에 vector γ~\tilde{\gamma}λ1+γ\lambda\vec{1}+\gamma로 정의됩니다.
      • 1\vec{1}은 1의 벡터를 의미합니다.
    • Lagrangian mulipliers 값인 γ~\tilde{\gamma}는 다음과 같이 diag(B^)=0diag(\hat{B}) = 0 이라는 제약에 의해 결정됩니다.
    • 위 식에서 \odot는 elementwise product이고, γ~\tilde{\gamma}에 대해 다시 정리하면 다음과 같습니다.
      • \oslash는 원소들의 나눗셈을 의미합니다.
    • 이것들을 다시 정리하여 B^\hat{B} 공식에 대입하면 다음과 같이 (Closed-Form으로)정의됩니다.
  • 즉, 결과적으로 학습되는 가중치는 다음과 같습니다.
    • i==j일 땐(diag matrix), 0으로 나오며, 그 외에는 모두 Pij^Pjj^-\frac{\hat{P_{ij}}}{\hat{P_{jj}}}를 통해 나타낼 수 있습니다.
      • P^\hat{P}는 앞서 구한 바와 같이 (XTX+λI)1X^TX+\lambda I)^{-1}를 통해 구할 수 있습니다.

위 계산식을 보면, BB가 결국 Gram-matrix GXTXG\triangleq X^TX (= 아이템-아이템 행렬)에 의해 계산된다는 것을 보여줍니다. 이는 앞선 살펴보았던 목적식에서 square loss를 사용한 결과이며, sparse한 데이터 X에서 BB를 계산하는 데 도움이 됩니다.

  • G=XTXG=X^TX는 co-occurrence matrix를 의미합니다.

    ❗️co-occurence matrix란? (참고한 자료)

    다음과 같이 interaction(XX)이 있다고 가정합시다.

    이를 co-occurrence matrix(G=XTXG=X^TX)로 표현하면(자기자신은 제외), 다음과 같습니다.

    첫 번째 행을 살펴보면, '사과'가 선택됐을 때 강아지, 말, 자전거가 선택되는 빈도를 알 수 있습니다.
    -> 대부분의 Neighborhood-based 접근법과 유사! (뒤에서 EASE와 비교하여 더 다룰 예정입니다.)

  • co-occurrence인 GijG_{ij}의 불확실성은 (대략적으로)포아송 분포(poisson distribution)의 표준편차 Gij\sqrt{ G_{ij}} 에 의해 결정됩니다. 이때 co-occurrence counts가 충분히 크다면, GGBB는 작은 에러로 추정될 수 있습니다.
  • 여기서 흥미로운 사실은 G=XTXG=X^TX의 entry가 다음과 같은 두 가지 요인에 의해 증가된다는 것입니다.
    1. 유저의 활동량이 증가하여 데이터 XX의 밀도가 더 높아진 경우
    2. 데이터 XX의 유저 수가 증가할 경우
  • (2)번의 의미를 생각해보면, XX의 sparsity가 커져도, 유저의 수가 커지게되면 이를 보완할 수 있습니다. 다시 말해, 유저별로 활동량이 많지 않은 sparse한 데이터 하더라도 유저 수가 충분히 많다면, BB를 추정하는 것의 불확실성에는 영향을 주지 않는다는 것입니다.
  • 따라서 (논문 제목에서도 말하고 있듯이) 'Sparse한 데이터에 대해 강점이 있다' 이라고 말할 수 있습니다.

Algorithm


EASE의 학습은 XX가 아니라 GG(=XTXX^TX)가 입력으로 들어가기 때문에, XX의 크기(U|U| X I|I|)보다 GG의 크기(I|I| X I|I|)가 더 작을 경우 특히 효율적입니다. 즉, 아이템 수에 비해 유저 수가 많을 경우에 매우 효율적입니다.

  • 그러나 이는 (반대로 말하면) 아이템 수가 유저 수보다 상대적으로 많다면, 효율적이지 않을 수 있다는 것을 의미하기도 합니다.

Comparison with Neighborhood-based Approaches

본 논문을 통해 저자는 EASE의 closed-form solution은 기존 neighborhood-based 접근이 개념적으로 잘못되었음을 보여준다고 말하고 있습니다.

  • 대부분의 neighborhood-based 접근법에서는 co-occurrence matrix(Gram-matrix, XXX'X)를 사용합니다.
  • 그러나 EASE 모델에서 solution을 구해보니, 이러한 co-occurrence matrix를 그대로 사용하는 것이 아니라, 이를 inverse한 행렬을 사용하는 것이 더 정확한 방법이였다고 말하고 말하고 있습니다.
  • 또한, 다른 (높은 성능을 보이는)모델들과 비교하여 우수한 성능을 보이고 있는 EASE가 원칙적인 neighborhood approach라고 볼 수 있다고 말하고 있습니다.

Reference

profile
AI Engineer : Lv 0

0개의 댓글