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

가공된 Movie Lens 데이터를 활용하여 사용자가 시청할 및 좋아할 영화를 예측하기 위해 모델을 구현하고 있다!

우리 팀은 아키텍처가 다른 대표 모델 몇 개를 먼저 선정하였고, 이론 공부 팀과 구현팀으로 번갈아가면서 진행하고 있다.

나는 현재 이론팀으로 AutoEncoder 계열 모델에서 먼저 EASE를 맡게 되었다.

간단하지만 수식적으로는 복잡한.. EASE 모델을 파헤쳐보려 한다.

 

 

EASE (Embarrassingly Shallow Autoencoders for Sparse Data)

- Sparse Data(희소 데이터)를 위한 Embarrassingly(당황스러울 정도로) Shallow(얕은) Autoencoders(오토인코더 모델)이다.

- 희소 데이터는 user/item interaction 데이터가 많이 채워지지 않은 데이터로 현실에서 보기 쉽다. 이는 cold start 문제 등을 일으키며 모델 성능을 저하시키는 요인 중 하나이다. 어떻게 희소 데이터를 해결할 수 있을까?라는 의문이 먼저 든다! (뒤에서..)

- 그리고 얕다라는 것은 딥러닝의 특징인 hidden layer가 존재하지 않는 선형 모델을 의미한다.

- 마지막으로 오토인코더 이름이 붙기는 했지만 엄밀히 따지면 오토인코더는 아니다. input으로 받은 데이터가 재생성된 output으로 나온다는 점에서 autoencoder와 아키텍처가 유사하다. (오토인코더는 input에서 hidden layer를 거쳐 latent factor를 얻는 과정을 거친다.)

 

 

그렇다면 EASE는 hidden layer를 사용하지 않고 어떻게 학습할까?

먼저 아래 사진은 논문에 나와있는 모델 구조이다.

https://arxiv.org/abs/1905.03375

입력 데이터, 학습 파라미터, 출력 데이터, 목적 함수를 정의해 보자.

- 입력 데이터 X : 유저 * 아이템 크기의 상호작용 행렬로 상호작용이 일어났다면 1, 일어나지 않았다면 0으로 표기한다.

- 학습 파라미터 B : 아이템 * 아이템 크기의 아이템 간의 가중치 행렬이다. 입력 데이터 X와 행렬곱 연산 결과값과 원래 X와 얼마나 유사한지를 비교하며 학습해 나간다. 

** 학습 파라미터의 대각 성분은 0으로, 대각 성분을 0으로 하지 않으면 단위행렬이 되어버리는 현상이 발생한다. 이는 목적함수 식에서 다시 얘기할 예정! (EASE의 핵심!)

- 출력 데이터 S : 아이템 j가 유저 u에게 주어졌을 때의 predicted score이다.

 

목적 함수를 정의하기 전에, closed form solution 개념을 먼저 살펴보자.

EASE의 경우 학습 파라미터의 최적해가 간단히 식으로 closed form으로 풀 수 있다. 

 

 

Closed form solution 이란?

closed form(닫힌 형태)은 방정식의 해를 해석적으로 표현할 수 있는 종류의 문제이다. closed form solution은 문제에 대한 해답을 식으로 명확하게 제시할 수 있다는 것을 의미한다.

보통 딥러닝의 경우 관측해야 할 학습 파라미터가 많아서 닫힌 형태의 문제에 대한 해답을 식으로 명확하게 제시하기 어렵다. 

앞에서 말했듯이 EASE의 경우 closed form으로 풀 수 있다. 즉 학습을 위한 목적 함수를 식으로 명확하게 나타낼 수 있다.

 

그러면 다시 목적 함수로 돌아와서!

 

 

EASE의 목적함수

EASE는 위 목적 함수로 학습 파라미터 B를 만든다.

우리는 input data X와의 최소 오차를 갖는 값을 구하는 것이 목표이다. 이 부분을 square loss를 사용하여 계산했다. 여기에 과적합을 방지하기 위해 L2-norm 정규화 항이 뒤에 더해졌다.

 

여기서 point는 두 가지가 있다.

1. Frobenius norm 활용 : X와 XB의 차이를 계산하는 square loss와 과적합 방지 계산에 Frobenius norm이 활용됐다.

-> 행렬의 Frobenius norm은 행렬의 모든 성분의 제곱의 합에 제곱근을 구하는 것이다. 행렬 버전의 L2-norm 계산식이라고 생각하면 된다.

여기서 Frobenius norm 찾아보다가 행렬 A의 Frobenius norm은 A.T와 A의 행렬곱의 대각 성분의 합과 같고 이것은 A.T와 A의 행렬곱의 고유값의 합과 같으니까 A의 특이값 제곱의 합과 같게 된다고 한다. 그래서 행렬 A의 Frobenius norm는 A의 특이값에 의존한다고 한다.

특이값의 장점이 반영된 것인지, 특이값에 의존한다라는 의미는 좀 더 찾아봐야겠다.(수학 안녕..) 그런데 multinomial likelihood와 같은 다른 손실 함수를 사용하면 정확률이 높아진다는 말도 있는 거 보니 손실 함수에 적용된 계산 방법은 주어진 task에 맞게 실험해보는 것이 좋아 보인다.

 

2. λ : 모델에 사용되는 유일한 하이퍼파라미터이다. 

 

 

EASE의 목적함수 -> closed-form 으로 풀기!

위 목적함수를 closed-form으로 풀 수 있다. 

우리는 학습 파라미터 B의 대각 성분을 0으로 해야 한다고 했다. 그렇지 않으면 B(item x item)는 단위행렬이 되므로 이는 B의 제약조건이다.

1. 제약조건이 포함되어 있는 최적화 문제를 해결하기 위해 라그랑주 승수법을 통해 (diag(B)=0)을 목적식(위 그림​)에 적용한다.

 

 

2. 제약조건이 포함되어 있는 최적화 문제는 Lagrangian을 최소화함으로써 해결할 수 있는데, 이에 대한 필요조건으로 도함수를 0으로 설정하여 항을 재배열한 뒤 B의 추정값을 산출한다. 

 

3. 그리고 P의 추정값을 아래 식처럼 정의하여 2번 식을 다시 정리한다.

 

4. 라그랑주 승수법 값은 아래와 같이 제약에 의해 결정된다. 그리고 식을 다시 정리하고 B의 추정값 공식에 다시 대입한다.

B의 추정값을 계산하는 과정은 논문에 잘 나와있다! 수식이 어떻게 계산되는지 자세히 알기보단 접근법에 초점을 두려 한다.

 

결과적으로 학습되는 가중치는 아래와 같다.

- i==j일 때 0으로 나오며, 

- 그 외에는 모두 P의 추정값으로 나타낼 수 있다. P는 아래의 식을 통해 구할 수 있다.

그래서 결국 학습 파라미터 B는 X.T와 X행렬곱에 의해 계산된다(중요해진다).

이는 item-to-item matrix로 이러한 꼴을 Gram-matrix라고 한다.

논문에서는 Gram-matrix를 co-occurrence matrix라고 말한다.

 

 

co-occurence matrix란?

- 어떤 한 아이템이 유저에게 선택되었을 때, 다른 아이템도 같이 선택되었을 빈도가 어느 정도인지를 나타내는 행렬이다.

위 그림과 같은 행렬이 있다고 할 때, co-occurrence matrix로 표현하면(자기 자신 제외) 아래와 같다.

-> 사과가 선택되었을 때, 강아지, 말, 자전가가 선택되는 빈도를 알 수 있다. 그래서 대부분의 neighborhood-based 접근법과 유사하다!! 논문에서는 neighborhood-based 모델에서 Gram-matrix를 그대로 사용하는 것은 개념적으로 틀리다고 지적하고, EASE처럼 G의 역행렬을 사용하는 것이 더 정확한 방법이었다고 말하고 있다.

 

 

여기까지 모델 정의 및 학습 방법을 정리해 봤다. 그렇다면 맨 처음 의문을 던졌던 ESAE는 어떻게 희소 행렬 데이터를 위한 모델일까?를 살펴보자

 

어떻게 for sparse data인가?

co-occurrence인 Gij의 불확실성은 포아송 분포의 표준편차에 의해 결정된다. 표준편차가 작다는 것은 데이터점이 평균에 비교적 가깝고 데이터의 불확실성이 낮다는 것을 의미한다.

이때 co-occurrence counts (동시 발생 개수)가 충분히 크다면 G는(B도 마찬가지) 작은 에러로 추정될 수 있다.

 

G의 entry(데이터 element)가 다음 두 가지 요인에 의해 증가된다.

1. 유저의 활동량이 증가하여 데이터 X의 밀도가 더 높아진 경우

2. 데이터 X의 유저 수가 증가할 경우

 

그래서 2번의 경우를 생각해보면 X의 sparsity가 커져도, 유저의 수가 충분히 많다면 이를 보완할 수 있다!! 즉 G의 불확실성에 영향을 주지 않는다.

따라서 sparse 한 데이터를 위한 모델이라고 말할 수 있다.

 

 

연산 효율 증가

 

또 다른 특징으로는 위에서 정의한 바와 같이 목적함수를 최적화하는 해를 구하는 것이 closed form solution이라서 굳이 딥러닝을 사용할 필요 없어 컴퓨팅 자원이 적게 든다.

그리고 파라미터를 업데이트하기 위해 결과적으로 유저와 아이템의 Interaction 행렬인 input data X(user x item)를 자체가 아니라 G(item x item)를 사용하기 때문에 아이템의 수가 유저의 수보다 상대적으로 적으면 연산 효율성이 증가한다. 

반대로 아이템의 수가 유저의 수보다 상대적으로 많으면 연산 효율성이 떨어진다.

 

 

이렇게 EASE 정리가 끝났다

마무리로 정리해보면 EASE는 input data X(user x item)을 학습 파라미터 B를 활용하여 아이템이 유저에게 주어졌을 때 예측 score를 output으로 계산한다. 학습 파라미터를 계산하는 목적함수는 closed form solution으로 쉽게 계산할 수 있다는 것이 큰 장점이다! 여기서 학습 파라미터 B의 대각 원소는 0 이여야 한다.

 

정리한지는 오래됐지만 대회 끝나고 프로젝트로 정신없어서 지금 올린다ㅠㅠ