random_image

[WWW'19] EASE: Embarrassingly Shallow Autoencoders for Sparse Data

tony | Oct. 25, 2024, 11:29 a.m. | paper-review | machine-learning recommender-system

Netflix에서 발표한 추천 논문. Sparse한 데이터에 대해 강점이 있다는 사실을 수식으로 증명해내고 성능을 보임

Netflix의 senior data scientist 로 근무중인 Harald Steck가 쓴 논문. 추천관련 논문을 자주쓰시는 분이다.

[WWW'19] EASE: Embarrassingly Shallow Autoencoders for Sparse Data

Netflix에서 발표한 논문. 은닉층이 없는 선형 모델만 가지고 아이템 예측하는 모델.

Sparse한 데이터에 대해 강점이 있다는 사실을 수식으로 증명해내고 성능을 보인 논문.

import warnings
from collections import defaultdict

import torch
import numpy as np
import scipy.sparse as sp
import pandas as pd

warnings.filterwarnings(action='ignore')
torch.set_printoptions(sci_mode=True)
import argparse

def get_config(jupyter_notebook=False):
    parser = argparse.ArgumentParser()
    parser.add_argument('--valid_samples', default=10, type=int, help="검증에 사용할 sample 수")
    parser.add_argument('--seed', default=2024, type=int)
    return parser.parse_args(args=[]) if jupyter_notebook else parser.parse_args()

config = get_config(jupyter_notebook=True)

device = 'cuda' if torch.cuda.is_available() else 'cpu'
config
Namespace(valid_samples=10, seed=2024)

데이터셋

import lightning as L
from mmrec.utils.common import get_root_path

ROOT = get_root_path()
L.seed_everything(config.seed)

class MakeMatrixDataSet():
    """
    MatrixDataSet 생성
    """
    def __init__(self, config):
        self.config = config
        df = pd.read_parquet(f"{ROOT}/data/ml-1m/logs.parquet")
        # valid sample 수 만큼 이력이 있는 warm 유저만 필터링하여 학습/평가
        count_user_hist = df.groupby('user_id').item_id.apply(len)
        warm_user_set = set(count_user_hist[count_user_hist > config.valid_samples].index.tolist())
        self.df = df[df.user_id.isin(warm_user_set)]
        
        self.item_encoder, self.item_decoder = self.generate_encoder_decoder('item_id')
        self.user_encoder, self.user_decoder = self.generate_encoder_decoder('user_id')
        self.num_item, self.num_user = len(self.item_encoder), len(self.user_encoder)

        self.df['item_idx'] = self.df['item_id'].apply(lambda x : self.item_encoder[x])
        self.df['user_idx'] = self.df['user_id'].apply(lambda x : self.user_encoder[x])

        self.user_train, self.user_valid = self.generate_sequence_data()

    def generate_encoder_decoder(self, col : str) -> dict:
        """
        encoder, decoder 생성

        Args:
            col (str): 생성할 columns 명
        Returns:
            dict: 생성된 user encoder, decoder
        """

        encoder = {}
        decoder = {}
        ids = self.df[col].unique()

        for idx, _id in enumerate(ids):
            encoder[_id] = idx
            decoder[idx] = _id

        return encoder, decoder
    
    def generate_sequence_data(self) -> dict:
        """
        sequence_data 생성

        Returns:
            dict: train user sequence / valid user sequence
        """
        users = defaultdict(list)
        user_train = {}
        user_valid = {}
        for user, item in zip(self.df['user_idx'], self.df['item_idx']):
            users[user].append(item)
        
        for user in users:

            user_total = users[user]
            valid = np.random.choice(user_total, size = self.config.valid_samples, replace = False).tolist()
            train = list(set(user_total) - set(valid))

            user_train[user] = train
            user_valid[user] = valid # valid_samples 개수 만큼 검증에 활용 (현재 Task와 가장 유사하게)

        return user_train, user_valid
    
    def get_train_valid_data(self):
        return self.user_train, self.user_valid

    def make_matrix(self, user_list, train = True):
        """
        user_item_dict를 바탕으로 행렬 생성
        """
        mat = torch.zeros(size = (user_list.size(0), self.num_item))
        for idx, user in enumerate(user_list):
            if train:
                mat[idx, self.user_train[user.item()]] = 1
            else:
                mat[idx, self.user_train[user.item()] + self.user_valid[user.item()]] = 1
        return mat

    def make_sparse_matrix(self):
        X = sp.dok_matrix((self.num_user, self.num_item), dtype=np.float32)
        for user in self.user_train.keys():
            item_list = self.user_train[user]
            X[user, item_list] = 1.0
                
        return X.tocsr()
Seed set to 2024

모델

논문의 다음과 같은 방식으로 Item-Item 가중치 행렬 $B$를 근사한다. 여기서 $P = (X^T X + \lambda I)^{-1}$

핵심

EASE의 학습은 $X$가 아니라 $G(=X^TX)$가 입력으로 들어가기 때문에

$X$의 크기($\vert U \vert \vert I \vert$)보다 $G$의 크기($\vert I \vert^2$)가 더 작을 경우, 아이템 수에 비해 유저 수가 많을 경우에 매우 효율적

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

Why?

co-occurrence인 $G$의 불확실성은 (대략적으로)포아송 분포(poisson distribution)의 표준편차 $\sqrt{G_{ij}}$ 에 의해 결정 됨.

이때, co-occurrence counts가 충분히 크다면, G와 B는 작은 에러로 추정될 수 있음.

그런데, $G=X^TX$의 entry가 다음과 같은 두 가지 요인에 의해 증가 됨.

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

2번의 의미를 생각해보면, $X$의 sparsity가 커져도, 유저의 수가 커지게되면 이를 보완 가능. 다시 말해, 유저별로 활동량이 많지 않은 sparse한 데이터 하더라도 유저 수가 충분히 많다면, B를 추정하는 것의 불확실성에는 영향을 주지 않는다.

따라서, (논문 제목에서도 말하고 있듯이) 'Sparse한 데이터에 대해 강점이 있다' 이라고 말할 수 있음.

class EASE():
    def __init__(self, X, reg):
        self.X = self._convert_sp_mat_to_sp_tensor(X)
        self.reg = reg
    
    def _convert_sp_mat_to_sp_tensor(self, X):
        """
        Convert scipy sparse matrix to PyTorch sparse matrix

        Arguments:
        ----------
        X = Adjacency matrix, scipy sparse matrix
        """
        coo = X.tocoo().astype(np.float32)
        i = torch.LongTensor(np.mat([coo.row, coo.col]))
        v = torch.FloatTensor(coo.data)
        res = torch.sparse.FloatTensor(i, v, coo.shape).to(device)
        return res
    
    def fit(self):
        '''

        진짜 정말 간단한 식으로 모델을 만듬

        '''
        G = self.X.to_dense().t() @ self.X.to_dense()
        diagIndices = torch.eye(G.shape[0]) == 1
        G[diagIndices] += self.reg

        P = G.inverse()
        B = P / (-1 * P.diag())
        B[diagIndices] = 0

        self.pred = self.X.to_dense() @ B
def get_ndcg(pred_list, true_list):
    idcg = sum((1 / np.log2(rank + 2) for rank in range(1, len(pred_list))))
    dcg = 0
    for rank, pred in enumerate(pred_list):
        if pred in true_list:
            dcg += 1 / np.log2(rank + 2)
    ndcg = dcg / idcg
    return ndcg

# hit == recall == precision
def get_hit(pred_list, true_list):
    hit_list = set(true_list) & set(pred_list)
    hit = len(hit_list) / len(true_list)
    return hit

def evaluate(model, X, user_train, user_valid):

    mat = torch.from_numpy(X)

    NDCG = 0.0 # NDCG@10
    HIT = 0.0 # HIT@10

    recon_mat1 = model.pred.cpu()
    recon_mat1[mat == 1] = -np.inf  # 이미 interaction이 있는 아이템 제거
    rec_list1 = recon_mat1.argsort(dim = 1)

    for user, rec1 in enumerate(rec_list1):
        uv = user_valid[user]

        # ranking
        up = rec1[-10:].cpu().numpy().tolist()[::-1]

        NDCG += get_ndcg(pred_list = up, true_list = uv)
        HIT += get_hit(pred_list = up, true_list = uv)

    NDCG /= len(user_train)
    HIT /= len(user_train)

    return NDCG, HIT
make_matrix_data_set = MakeMatrixDataSet(config = config)
user_train, user_valid = make_matrix_data_set.get_train_valid_data()
X = make_matrix_data_set.make_sparse_matrix()
print(X.shape)

make_matrix_data_set.df
(6032, 3255)
<style scoped> .dataframe tbody tr th:only-of-type { vertical-align: middle; }
.dataframe tbody tr th {
    vertical-align: top;
}

.dataframe thead th {
    text-align: right;
}
</style>
user_id item_id rating timestamp item_idx user_idx
31 1 2624 4 2000-12-31 22:00:19 0 0
22 1 1022 5 2000-12-31 22:00:55 1 0
27 1 1373 4 2000-12-31 22:00:55 2 0
37 1 823 5 2000-12-31 22:00:55 3 0
24 1 1883 3 2000-12-31 22:01:43 4 0
... ... ... ... ... ... ...
1000019 6039 2393 4 2001-08-10 14:40:29 1104 6031
999988 6039 1510 4 2001-08-10 14:41:04 315 6031
1000172 6039 1411 3 2001-08-10 14:41:04 87 6031
1000167 6039 137 3 2001-08-10 14:41:26 410 6031
1000042 6039 975 4 2001-08-20 13:44:15 371 6031

835060 rows × 6 columns

for reg in [1000, 100, 10, 1, 0.1, 0.01]:
    model = EASE(X = X, reg = reg)
    model.fit()
    ndcg, hit = evaluate(model = model, X = X.todense(), user_train = user_train, user_valid = user_valid)
    print(f'reg: {reg}| NDCG@10: {ndcg:.5f}| HIT@10: {hit:.5f}')
reg: 1000| NDCG@10: 0.31457| HIT@10: 0.21139
reg: 100| NDCG@10: 0.29260| HIT@10: 0.19839
reg: 10| NDCG@10: 0.24090| HIT@10: 0.16318
reg: 1| NDCG@10: 0.19303| HIT@10: 0.13105
reg: 0.1| NDCG@10: 0.16777| HIT@10: 0.11424
reg: 0.01| NDCG@10: 0.16271| HIT@10: 0.11119

Last updated on Oct. 25, 2024, 11:33 a.m.

LEAVE A COMMENT

tony | 5 months, 3 weeks ago

EASE 의 후속 연구로 동저자가 낸 다음의 논문도 있음. $EASE^R$ 모델로 불리움.
[RecSys'21] Negative Interactions for Improved Collaborative Filtering: Don’t go Deeper, go Higher

EASE보다 higher order interaction을 배우기 위해 optimization 수식에 higher-order tensors 를 도입(deep learning에서 deeper network를 구축하듯)하고, Negative interaction 을 사용함.  


tony | 5 months, 3 weeks ago

또 다른 최근 후속 연구로 Martin Spišák 가 RecSys 2023 에서 short paper 로 다음의 논문을 게재.

[RecSys'23] SANSA: how to compute EASE on million item datasets

사용자가 아이템을 선호하는 방식과 아이템이 사용자에게 추천되는 방식은 다를 수 있기 때문에 비대칭적인 모델이 더 적합할 수 있다는 것이 논문의 핵심 동기로 작용함.

이 연구는 특히 대규모 데이터셋에서의 확장 가능성에 중점을 두고, 기존 방식 대비 더 높은 성능을 보임. 

이는 복잡한 구조를 더 깊게 만들기보다는 효율적인 구조 변경을 통해 달성된 것으로, 비대칭적 오토인코더가 복잡한 상호작용 패턴을 더 잘 포착할 수 있음을 보여줌.