[추천시스템] Rating Elicitation에 관하여

About Rating Elicitation

Rating Elicitation은 추천시스템을 처음 이용하는 신규 User에게 Seed itemset을 전달하여 rating을 부여하도록 권유하는 전략이다. 이러한 전략을 사용하는 까닭은, 신규 User의 cold-start problem을 일부 완화시키기 위함이다.

여러 협업필터링 기반의 추천시스템에서 사용된 Active learning에 대한 서베이 논문으로는 [1]이 있는데, rating prediction을 수행한 뒤 top-k방식을 채택해 상위 k개 item을 seed itemset으로 사용하는 경우가 대부분인 것 같다. 

같은 저자의 [2]에서는 CF를 위한 Rating Elicitation 전략에 대해 소개하고 있는데, null entry가 존재하는(sparse matrix란 의미) rating matrix \(R\in\mathbb{R}^{n\times m}\)에 대하여 rating strategy \(S\)를 다음과 같이 설명하고 있다. : \(S(u, N, K, C_u)=L\) which returns a list of \(M<=N\) items \(L=\{i_1, ... , i_M\}\) whose ratings should be asked to the user \(u\), where \(N\) is the maximum number of ratings to be elicited.

추천시스템이 가진 전체 N개 itemset에 대하여, K개의 seed itemset L을 rating 하도록 하고, L을 이용해 \(C_u\)를 예측하는 전략으로 요약할 수 있다. 그러니까, 이 이야기는 학술적으로 들리지만, 실상 현재 추천시스템을 적극 활용하고 있는 여러 플랫폼에서 사용하고 있는 하나의 전략인데 대표적으로는 역시 넷플릭스를 예로 들 수 있다. 넷플릭스의 경우 여러 장르의 영상물 중 78개의 seed itemset을 신규 user에게 rating 하도록 한다. 이때, explicit rating을 권하는 것은 아니고, '좋아하는 컨텐츠를 3개 선택하라'고 권한다. implicit feedback을 하도록 권하는 형태인 것.

(Netflix의 신규 회원에 대한 rating elicitation 화면)

국내 서비스 중에는 에이블리 등의 쇼핑 어플이 해당 전략을 사용하는 것으로 보인다. 아마도, 영화 데이터와 마찬가지로 각 패션 이미지에 대한 라벨 데이터와 feedback으로 구성된 DB를 이용해 추천시스템을 운영할 것이라고 생각해본다. 에이블리도 마찬가지로 78개의 seed itemset을 신규 user에게 전달한다. k의 갯수가 어떻게 지정된 것인지에 대해서는 레퍼런스가 없어서 아쉽다. 다만, 이러한 플랫폼은 어찌됐건 user가 rating 하는 과정에서 지쳐 나가떨어지게 해서는 안되기 때문에 k=78을 적정 수준으로 여긴 듯 하다. 3개 이상을 선택하라고 하는 이유는 적어도 similarity를 최소한의 수준으로 계산하려고 해도 item 2개만 가지고는 \(Similarity(A,B)\) 하나의 값만 계산되기 때문에 그 최소한의 요건으로 3개라는 하한선을 둔 것으로 보인다.

(에이블리의 신규 회원에 대한 rating elicitation 화면)

Representative?

신규 유저에 대한 추천은 이 seed itemset에 대해 rating을 많이 부여할수록 예측 성능이 올라갈 것이다. 그런데 k=78 사이즈의 seed itemset을 신규 유저에게 전달한다고 하여, 신규 user가 충분히 많은 수의 item에 대해 rating할 것이라는 확신을 할 수는 없다. 

곧, 이 문제는 seed itemset이 전체 itemset 또는 category 별 itemset을 대표하는 대표성을 띠어야 한다는 방향으로 이어진다. 때문에 78개의 itemset을 결정하는 방식이 중요하게 된다.

해서, [1],[2]에서 소개된 바와 같이 top-k 방식을 활용하는 경우가 많다. top-k의 대상이 될만한 평가 방법은 다양하다. 예를 들어, 클릭률, 클릭수가 될 수 있고, 또는 플랫폼에 따라 구매자의 수, 리뷰의 수, 아이템에 대한 평점 등으로 활용할 수 있다. 경우에 따라 [3](관련 포스트)과 같이 휴리스틱한 방식의 유사도 measure를 개발에 이 방법에 활용할 수 있을 것이다.

Idea

Rating Elicitation이란 전략에 대해 간단히 알아본 까닭은, 계획 중에 있는 연구에서 얻어지는 부수적인 효과 때문이다. 바로 전 절에서는 seed itemset의 대표성에 대해 잠시 다뤘는데 케이스 스터디를 해보다보면, representative dataset을 결정하는 방식에는 휴리스틱, 메타휴리스틱한 방법들이 많이 존재한다.

local optima에 빠지지 않도록 global representative selection하는 방식의 연구등이 존재하는데, 최근에 읽어본 연구는 [4] 등이 있다. 아쉽게도 해당 방식은 SVM을 이용하는 것이라 추천 시스템에 임베딩할 방법을 아직까지 찾지 못했다.

한 편, 최근에 리뷰한 CAEs와 같은 모델의 경우에는 Feature selection을 위한 모델인데 이 경우 선택된 feature가 seed itemset으로 구성될 수 있도록 latent vector를 계산하는 방식이 가능하다. 즉 목적으로부터 결과가 나오는 것이 아니라, 계산값을 이용하여 부수적 효과를 얻어내는 방식이 가능해보인다. 현재는 이 아이디어를 기초로 한 연구를 진행해보고 있다.

[1] Elahi, Mehdi, Francesco Ricci, and Neil Rubens. "A survey of active learning in collaborative filtering recommender systems." Computer Science Review 20 (2016): 29-50.

[2] Elahi, M., Repsys, V., & Ricci, F. (2011, August). Rating elicitation strategies for collaborative filtering. In International Conference on Electronic Commerce and Web Technologies (pp. 160-171). Springer, Berlin, Heidelberg.

[3] Ahn, H. J. (2008). A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem. Information sciences, 178(1), 37-51.

[4] Y. Ma, X. Liang, G. Sheng, J. T. Kwok, M. Wang and G. Li, "Noniterative Sparse LS-SVM Based on Globally Representative Point Selection," in IEEE Transactions on Neural Networks and Learning Systems, vol. 32, no. 2, pp. 788-798, Feb. 2021, doi: 10.1109/TNNLS.2020.2979466.

[논문 리뷰] 콘크리트 오토인코더(Concrete Autoencoders)

Concrete Auto-encoders for Differentiable Feature Selection and Reconstruction

(Abid, Abubakar et al. “Concrete Autoencoders for Differentiable Feature Selection and Reconstruction.” ICML (2019). https://arxiv.org/abs/1901.09346v2)

 작년에 알게 된 논문이긴 하지만, 근래 들어 오토인코더에 대한 공부를 하면서 좀 더 자세히 살펴본 김에 논문 리뷰를 하게 되었다. 기본적으로 discrete relaxation과 지정된 k개 만큼의 feature selection을 목적으로 한다는 점에서, 내가 활용하고자 하는 용도에 부합한다. (ICML Proceeding이라 조금은 아쉽다.)

Abstract

We introduce the concrete autoencoder, an end-to-end differentiable method for global feature selection, which efficiently identifies a subset of the most informative features and simultaneously learns a neural network to reconstruct the input data from the selected features. Our method is unsupervised, and is based on using a concrete selector layer as the encoder and using a standard neural network as the decoder. During the training phase, the temperature of the concrete selector layer is gradually decreased, which encourages a user-specified number of discrete features to be learned. During test time, the selected features can be used with the decoder network to reconstruct the remaining input features. We evaluate concrete autoencoders on a variety of datasets, where they significantly outperform state-of-theart methods for feature selection and data reconstruction. In particular, on a large-scale gene expression dataset, the concrete autoencoder selects a small subset of genes whose expression levels can be use to impute the expression levels of the remaining genes. In doing so, it improves on the current widely-used expert-curated L1000 landmark genes, potentially reducing measurement costs by 20%. The concrete autoencoder can be implemented by adding just a few lines of code to a standard autoencoder.

 Abstract에서는, CAEs(Concrete Autoencoders)는 end-to-end 방식의 전역 feature selection이 가능한 오토인코더이고, 기본 오토인코더의 인코더 대신 Concrete selector layer를 사용하는 방식이라고 한다. 디코더는 여전히 기본 오토인코더의 것을 사용한다. 구조적으로 기본 오토인코더에서 크게 바뀌는 것이 없기 때문에 적은 코드로도 쉽게 구현가능한 것을 장점으로 내세운다. 기본적으로 Annealing schedule을 활용하는 방식인데, 이것을 simulated annealing이라고 말할 수 있는 것인지는 확인해보아야겠다. 또, 선택된 feature들만 이용하여 test set에 대한 predict 수행이 가능하다고 한다.

1. Introduction

 Feature selection이라는 분야는 고차원 데이터셋을 저차원으로 축소하는 것에 목적을 둔다고 이야기하고 있다. 고차원 데이터셋의 feature가 갖고 있는 redundant한 수준을 측정하는 방식이라고도 한다. 그렇다면, 데이터셋에서 가장 중요한 Feature라는 것은 무엇인가? 아니면, 데이터를 축소하기만 하면 Feature selection인가? 에 대한 질문이 생긴다.

저자는 일반적인 차원축소 문제와 Feature selection의 문제가 엄연히 다름을 명시해두었다. 예를 들어 PCA(주성분분석) 또는 Hinton의 Autoencoder 등의 차원축소 기법들은 물론 데이터를 maximal variance를 유지하거나 또는, reconstruction loss를 최소화하면서도 더 적은 차원에 나타낼 수 있다.

하지만, 이러한 방식들은 오리지널 데이터셋에 존재하는 feature set을 선택하는 것이 아니라, 과잉(redundant)의 feature를 제거하고, 시험적 비용을 감소시키는 것에 목적이 있기 때문에 feature selection과 차원축소 문제는 서로 다르다고 한다.

이들이 이 논문에서 제안하는 CAEs는 discrete relaxation과 Maddison et al.(2016)의 Concrete distribution, 그리고 re-parametrization trick을 활용하여 reconstruction loss를 최소화하는 feature set을 찾는 방식이다.

discrete relaxation 방법으로는 Gumbel-softmax 방법을 활용하며, 이 부분은 후술한다.

2. Problem Formulation

 기본적으로, d-차원의 데이터로부터 발생하는 확률분포 \(p(x)\)가 존재한다고 가정한다. 이 모델이 포커싱하는 대상 자체가 discrete dataset을 이용한 비지도학습에 있다고 하니, 해당 확률분포 \(p(x)\)는 categorical distribution의 \(p_i\)라고 생각해도 좋아 보인다.

 목적은 이 알고리즘 사용자의 목적에 따라 고정된 'k'개 사이즈의 subset인 \(S\subseteq\{1, 2, ... , d\}\)을 학습하는 것과 reconstruction function인 \(f_{\theta}(\cdot)\)를 학습하는 것에 있다. 형태를 살펴보았을 때엔, 이 함수 부분을 디코더로 사용할 것임을 생각할 수 있다. 정리하면 최적화 문제는 다음과 같다. :

\[\arg \min_{S, \theta} E_{p(x)}[||f_{\theta}(x_{s})-x||_{2}]\]

하지만, 현실에서는 확률분포 \(p(x)\)를 알 수 없다 : 대신 \(p(x)\)로부터 i.i.d. 하게 n개의 데이터가 샘플링되었다고 가정한다(결국 추정값을 사용하겠다는 얘기다.)

이 n개의 샘플들은 데이터 행렬 \(X\in\mathbb{R}^{n\times d}\)의 형태로 나타내어질 수 있고, \(X\)로부터 k개 열로만 구성된 sub-matrix \(X_{S}\in\mathbb{R}^{n\times k}\)를 selection 할 수 있다. 또한, \(f_{\theta}(X_{S})\)를 이용해 matrix \(X\)를 복원할 수 있을 것이다. 결국 empirical reconstruction error는 다음과 같다. : 

\[\arg \min_{S, \theta} ||f_{\theta}(X_{S})-X||_{F}\]

(where \(||\cdot||\) denotes Frobenius norm of matrix)

하지만 이 최적화문제는 d-차원에 따라 NP-hard문제가 됨은 자명하기 때문에, back propagation이 불가능하다는 문제점을 야기하므로, 미분가능한 함수를 활용해보는 것으로 실험적 접근을 하겠다고 선언한다.

3. Proposed method

 앞서 언급하였듯이 이들이 제안하는 CAEs는 기본 오토인코더의 변형이며, discrete feature selection을 위한 모델이다. 다만, 기본 AEs에서 fully-connected layer를 encoder로 사용하는 것과 달리 concrete selector layer를 사용한다는 점에서 차이가 난다. 

또한 annealing schedule에 따라 각 layer가 결합되어가는데, (마치 simulated annealing과 같이) layer의 temp \(T\)가 0이 되면, k개 input feature를 선택하게 되는 구조이다.

-> 그렇다면 SA 외에 다른 비선형최적화 기법을 적용하는 것도 가능하지 않을까?

CAEs의 decoder는 reconstuction error function의 역할을 담당하고, 기본 AEs와 구조가 동일하다. : dataset 크기와 복잡도에 맞추어 사용자가 알아서 세팅한다.

결론적으로 제안된 방법은, 임의적으로 복잡한 형태의 reconstruction function을 효과적으로 최적화한다.

3.1 Concrete Selector Layer

 encoder가 되는 Concrete Selector Layer는 Maddison et al.(2016)과 Jang et al.(2016)에서 제안한 Concrete random variable에 그 기초를 둔다. 이 확률 변수를 샘플링함으로서, one-hot vector를 continuous relaxation 할 수 있다. 이 relaxation 과정은 3절에서 annealing schedule과 관련하여 언급한 temperature \(T\in (0,\infty)\)의 통제를 받는다. 

parameter \(\alpha\in\mathbb{R}^{d}\)와 \(T\)를 갖는 Concrete r.v.를 샘플링하기 위해서는, 우선 Gumbel distribution \(g\)에 i.i.d.한 d차원 벡터를 샘플링 해야한다. 이렇게 분포로부터 샘플링 된 \(m_{j}\)는 다음과 같이 정의할 수 있다. :

\[m_{j}= \frac{\exp((\log\alpha_{j}+g_{j})/T)}{\sum_{k=1}^d \exp((\log\alpha_{k}+g_{k})/T)}\]

(where \(m_j\) refers to the \(j^{th}\) element in a particular sample vector.)

temperature \(T\)가 0으로 수렴할수록, concrete r.v.는 이산형 분포에 접근하고, \(m_{j}=1\) with probability \(\alpha_{j}/\sum_{p} \alpha_{p}\)를 결과값으로 갖는다. Kingma & Welling(2013)에서 소개된 re-parametrization trick을 통해 매개변수 \(\alpha\)의 미분을 가능하게 하는것이 Concrete r.v.의 목적이다.

이들은 이러한 목적을 가진 Concrete r.v.을 이용해 다음의 방식으로 input feature selection을 수행한다. Concrete selector layer 전체 k개 노드 각각으로부터 d-차원의 Concrete r.v. \(m^{(i)}, i\in \{1, ... , k\}\)를 샘플링한다. (이 때, \(m^{(i)}\)에서의 i는 노드 인덱스임을 유의한다.)

selector layer 안의 i번째 노드 \(u^{(i)}\)는 \(x\cdot m^{(i)}\)를 결과값으로 내보낼 것이다. 일반적으로 이 값은, input feature의 weighted linear combination으로 볼 수 있으나, \(T\)가 0에 수렴함으로써, 각 노드로부터 concrete selector layer는 단 하나의 input feature만을 결과값으로 갖는다. 네트워크 훈련 이후 테스트에서는, concrete selector layer를 discrete arg max layer로 교체하며, 이 layer는 i번째 뉴런의 결과값으로 \(x_{\arg \max_{j} \alpha_{j}^{(i)}}\)를 갖게된다.

Conclusion

 용법이 적절하여 CAEs를 조만간 작성할 새 논문에서 활용할 예정이다. 실험관련하여서는 논문 리뷰를 하지 않는다. 다만, 유의미한 것은 dataset의 차원이 매우 고차원일 때 사용하거나, bio data와 같이 sequential dataset 형태를 띠는 경우 활용하기 좋다는 점을 부각했다는 것 정도로 정리할 수 있겠다. 

 대체적으로 Gumbel softmax trick에서 크게 벗어나지는 않았지만, 활용 방법에 따라 꾸며내기 좋은 모델을 개발하지 않았나 싶다.