[추천시스템] 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에서 크게 벗어나지는 않았지만, 활용 방법에 따라 꾸며내기 좋은 모델을 개발하지 않았나 싶다.

[포트폴리오] Resume

Updated on 2021-09-30

NAME : DAE-HYUN JIN

e-mail : daehyunjin.statistics@gmail.com

<학력사항>

동국대학교 (2011-03 ~ 2018-02)

산업시스템공학과 전공 • 학사 / 통계학과 복수전공

동국대학교 (2020-03 ~ 2022-02 졸업예정)

통계학전공 전공 • 석사, 

데이터마이닝 연구실 / 기상데이터분석 / 시계열 / 추천시스템

<업무경험>

(주)오뚜기 (2017-12 ~ 2019-12)

품질보증실 식품안전센터 미생물팀 KOLAS 시험원,

비개발경력 / 실험계획 / QA / 정보시스템 DB관리

SSG.COM (2022-02 ~ 현재)

DA(Data Analytics) 수습 입사

<개인 프로젝트 포트폴리오>

1) 동산 잔존가치 예측 모델링 프로젝트 (2020-05 ~ 2020-08)

• skill set : R

동산 가격 DB 데이터를 이용한 의사결정나무 가격 예측모델링

현대자동차, 나이스디앤알 발주 프로젝트로, 특정 제품의 시장 가격 DB를 이용해 시점별 수요 및 가격 예측을 목적으로 한 기초 회귀모형을 개발하는 역할을 맡았습니다. 최종 예측 모형으로 다중회귀모형과 의사결정나무 모형을 개발했습니다.

팀 구성 ― 나이스디앤알, 현대자동차, 동국대학교

2) 2021 전형 요소 타당화를 위한 종단적 연구 (2020-10 ~ 2021-01)

• skill set : SAS, R

학적, 학업성취도 정량, 정성 데이터 분석

동국대학교 교내 연구과제로, 졸업생 중 2013, 2014학년도 신입생의 학적 및 학업성취도 데이터를 이용하여 입학 유형에 대한 세그먼트를 구성한 뒤 유형별 학생 군이 갖는 학점에 대한 진로 등에 대한 정량, 정성적 평가를 맡아 분석을 진행했습니다.

팀 구성 ― 동국대학교

3) 2021 전형 요소 표준화를 위한 종단적 연구(시계열 연구) (2020-10 ~ 2021-01)

• skill set : SAS, R

학적, 학업성취도 시계열 데이터 분석

동국대학교 교내 연구과제로, 졸업생 중 2013, 2014학년도 신입생의 학적 및 학업성취도 데이터를 이용하여 입학 유형에 대한 세그먼트를 구성한 뒤 유형별 학생 군이 갖는 학점에 대한 시계열적 특성과 졸업 후 진로 등에 대한 정량, 정성적 평가를 맡아 분석을 진행했습니다.

팀 구성 ― 동국대학교

4) 동산 잔존가치 예측 모델링 고도화 프로젝트 (2021-04 ~ 2021-07)

• skill set : R

기존 프로젝트 모델링의 고도화, 신규 유형 동산에 대한 신규 모델링

현대자동차, 나이스디앤알 발주 프로젝트로, 특정 제품의 시장 가격 DB를 이용해 시점별 수요 및 가격 예측을 목적으로 한 기초 회귀모형을 개발하는 역할을 맡았습니다. 기존 유형의 제품군에 대한 모델링 최적화 및 신규 유형 제품군에 대한 랜덤포레스트 기반의 모델링을 진행했습니다.

팀 구성 ― 나이스디앤알, 현대자동차, 동국대학교

5) 스포츠 공정성 확보를 위한 인공지능 기반 실시간 승부 조작 위험성 경고 시스템 구현

• skill set : Python, R, SQL

웹 크롤링을 통한 스포츠 배팅 데이터 축적 및 LSTM, RNN 기반의 시계열 이상치 탐색 기법 연구

정보통신과학부 지원 사업으로, 웹 크롤링을 통해 스포츠 배팅 사이트의 DB를 구축하고 딥러닝 기법을 이용한 이상치 탐색 모델을 개발하는 역할을 맡았습니다.

팀 구성 ― 한국체육대학교, 동국대학교

6) Intraday 일사량 예보 성능 개선을 위한 Model Output Statistics 최적화(2021-07~)

• skill set : Python, R, SQL

일사량 예측 MOS 개발

한국에너지기술연구원 발주 프로젝트로, 위성 관측 데이터와 수치예보모델 데이터를 이용한 다중회귀모형 개발을 통해 MOS를 개발하는 역할을 맡았습니다.

팀 구성 ― 한국에너지기술연구원, 동국대학교

7) Feature selecting Autoencoders based collaborative filtering

• skill set : Python

Feature selection을 수행하는 Autoencoders 기반의 새로운 협업필터링 모델 개발

Continuous relaxation을 원리로 하는 응용 autoencoders를 이용하여 seed itemset이 될 수 있는 feature selection을 수행하고, rating elicitation 효과를 얻을 수 있는 collaborative filtering 알고리즘을 개발. 논문 투고중.

<자격사항>

2021-07 빅데이터분석기사

2020-12 ADsP(데이터분석준전문가)

2019-03 식품기사

2018-10 SQLD

2018-05 품질경영기사

2017-11 사회조사분석사 2급

2017-08 정보처리기사

<게재 논문>

2021-06

DOI : https://doi.org/10.5351/KJAS.2021.34.3.439

게재지 : 한국통계학회, 응용통계연구, 34권 3호

주저자 : Y (제 1저자 / 공동 4명)

Mann-Kendall 비모수 검정과 Sen's slope를 이용한 

최근 40년 남한지역 계절별 평균기온의 경향성 분석

A trend analysis of seasonal average temperatures over 40 years 

in South Korea using Mann-Kendall test and Sen's slope

2021-07

https://www.dbpia.co.kr/journal/articleDetail?nodeId=NODE10591841

게재지 : 한국신재생에너지학회 학술대회논문집.(2021):109-109

주저자 : N (제 2저자 / 공동 5명)

태양광 발전량의 1일 예보 성능평가를 위한 다양한 시계열 모델 비교 분석

A comparison of Several Time Series Models for 

Day-ahead Solar Power Generation Forecasting

[포트폴리오] 응용통계연구 논문 게재 (Mann-Kendall 비모수 검정과 Sen's slope를 이용한 최근 40년 남한지역 계절별 평균기온의 경향성 분석)

 

논문제목 : Mann-Kendall 비모수 검정과 Sen's slope를 이용한 최근 40년 남한지역 계절별 평균기온의 경향성 분석

한국통계학회 응용통계연구에 논문게제가 완료되었다. 

[논문 리뷰/추천시스템] Cold-start problem 완화 목적의 새로운 similarity measure 제안 논문

 A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem

Hyung Jun Ahn, A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem, Information Sciences, Volume 178, Issue 1, 2008, Pages 37-51, ISSN 0020-0255, https://doi.org/10.1016/j.ins.2007.07.024. 

일반적으로 추천시스템에서는 Pearson corr 또는 cosine similarity를 사용한다고 알려져있으며, 여러 자료에서도 그렇게 표현되어있고 때에 따라서는 너무나 당연해서 언급조차 되어있지 않은 경우가 많다. 

때문에 본인도 딱히 의문을 품어본 적이 없었는데, 얼마전 연구실 세미나에서 measure에 따라 결과값에 영향이 있겠냐는 박사님 지적에 해당 논문을 찾아보게 되었다.

2008년에 출판된 논문이라 제법 오래된 논문이지만, 여러 measure 별로 성능 비교를 해둔 논문이기도 하고, 새로운 similarity를 제안했기 때문에 여러 논문에서 인용을 한 듯 하여 선택하게 되었다.

아직 논문 리뷰를 잘하는 편이 아니기 때문에, 리뷰 방식은 해오던 습관대로 각 절마다 그 내용을 소개하는 것으로 한다.

Abstract

논문이 써진 당시인 2008년에는 netflix prize에서 우승한 collaborative filtering(CF)이 추천시스템에서 갖게 된 위상이 매우 높았다. 저자는 CF가 갖고있는 위상을 소개하면서 동시에, CF의 주요한 특성인 similarity measure가 Pearson correlation이나 cosine 유사도에 머물러있음을 지적한다. 따라서 본 논문에서는 새롭게 heuristic similarity measure를 제안한 것이 학술적인 contribution이라할 것이고, 새로운 measure를 이용한 실험 결과 CF가 갖고있는 고질적인 문제인 cold-start problem을 가진 데이터셋에서 좀 더 나은 퍼포먼스를 보인다고 한다.

1. Introduction

저자는 e-commerce에서 CF가 갖는 위력에 대해 우선적으로 소개하고 있다. 추후 CF에 대해서만 포스팅을 하나 해야겠다. 

간단히 CF에 대해서 공부했던 바를 정리해보면, CF는 기본적으로 취향이 비슷한 User의 집단이 존재한다고 가정한다. 추천의 대상이 되는 어떤 user가 있으면, 취향이 비슷한 neighbor가 존재할 것이고 이들이 공통적으로 긍정적인 rating을 한 item을 타겟이 되는 user에게 추천하는 방식이 기본적인 아이디어이다. 때문에 CF에서는 neighbor를 찾기위해 유사도 행렬을 이용한다는 점 정도만 짚고 넘어가면 될 것 같다.

다시 돌아와서, 이 논문에서도 CF의 위력은 similarity에 있음을 이야기하고 있고, Pearson 상관계수와 같은 전통적인 벡터 similarity measure가 주로 사용되고 있어 CF의 한계인 cold start problem에서 자유롭지 못함을 지적한다. 

저자는 이러한 문제의식을 드러내며 본 논문의 취지를 밝히고 있으며 그 취지는 heuristic similarity measure의 제안으로 이어진다. 전형적이고 기본적인 골조지만 앞으로 논문 작성 시에 이러한 프레임워크를 적용한다면 좀 더 쉽게 작성할 수 있지 않을까 하는 감상이 든다. 저자는 새로 제안된 방식이 user의 item에 대한 co-ratings에 더욱 세밀하게 집중한 방식이므로, cold-start 문제를 가진 데이터에 대해 더욱 효과적인 measure가 될 수 있다고 주장한다.

2. Literature review

2절에서는 추천시스템 전반에 대한 overview와 CF에 대한 리뷰를 제공한다. 논문이 출판된지 제법 오래되었기 때문에 overview는 큰 의미 없으리라 생각하고, CF에서 사용되고 있는(또는 사용되었던) similarity measure를 정리하는 표(Table 1) 정도만 확인하고 넘어가면 될 것 같다.

Table 1의 measure들은 이후 4절의 experiment에서 비교 실험을 위해 사용된다. 본 논문은 기본적으로 cold start가 있는 신규 user의 진입 상황을 가정하므로, user-item matrix에 대해서 Table 1의 measure들은 다음의 식에 사용된다. : 

\[\overline{r_{u_a}}+\frac{\sum_{h=1}^{m'}\mathrm{sim}(u_a, u_h)(r_{u_h,i_a}-\overline{r_{u_h}})}{\sum_{h=1}^{m'}|\mathrm{sim}(u_a,u_h)|}\]

저자에 따르면 당시에 존재하던 hybrid 방식의 추천시스템들은 기본적으로 cold start problem을 우회하기 위해 content information과 ratings data를 결합하여 사용했다. 즉, 새로 진입한 user나 item에 대해서는 rating-based의 measure는 계산할 수 없기 때문에 당시의 hybrid 추천시스템들은 그러한 방식을 채택했다는 것이다. 

그런데 이러한 당시의 연구 목적과 달리 본 논문에서는 rating record가 '적은' 상황을 가정한 것이며, hybrid RS에서처럼 추가적인 information을 요구하지 않는다. 따라서 기존의 CF에 대해 measure만 변경하여 모델링하면 되기 때문에 저자는 이러한 효율적인 연구목표를 설정한 듯 하다.

3. A new similarity measure

3.1 Diagnosis of the limitations of existing similarity measure

새로운 제안에 앞서, 우선 저자는 기존 measure들이 갖고 있는 문제점을 지적한다. 우선 COR(Pearson's)과 COS(Cosine similarity)는 근본적으로 cold-start에 취약할 수 밖에 없음을 지적한다. 

예컨대 데이터셋의 sparsity level이 0.90이라면, 그러니까 현존하는 <user-item> rating matrix R에 10% 수준의 rating만이 존재한다고 했을때 + 타겟 user가 고작 5개의 item만을 구매했다고하면(이 부분이 정확한지는 모르겠다. 단순히 a user라고 지칭하고 있는데, 아마도 추천을 타겟팅할 user를 이야기하는 것 같다.), COR이나 COS를 계산하는 것이 거의 불가능한 상황이 된다.

이러한 상황을 간략히 정리해보면 다음과 같다. : 

(1) Sparse matrix에서는 co-ratings을 계산하는 것이 매우 제한적이다.

(2) user-user간에 co-rating한 item이 단지 1개에 불과하다면, 기본적으로 COR은 계산될수조차 없고, COS는 co-rating이 어떤 값을 취하든 1의 값을 갖는다.

(3) user에 의해 주어진 rating이 item 별로 모두 같은 경우(논문에서는 flat이라고 표현했음) COR은 계산될 수 없고, 그 외의 correlation formula들은 0으로 계산된다.

(4) 각 user-item rating vector가 평행한 경우(e.g. <2,2> and <3,3>) COS는 1의 값을 갖는다.

(5) 결론적으로 COR과 COS 모두 서로 성향이 완전히 다른 user를 neighbor로 잘못 계산할 수 있다.

또한 (1)~(5)의 문제점들은 dataset이 sparse할수록 더 심각한 문제를 야기한다. 개인적으로 이러한 COR과 COS에 대한 문제점을 단순한 plot(Fig. 1.)으로 표현하여 직관성을 높인 부분이 배울 점이라고 생각한다.

이후의 내용은 실험에 사용될 dataset들이 이러한 문제에 취약하다는 점을 지적하는 내용이므로, 리뷰에서는 생략한다.

3.2 A new similarity measure for CF systems : PIP measure

3.1절에서 COS, COR의 문제점을 짚었으므로, 본 논문이 제안하는 PIP measure는 다음의 목적을 만족할 수 있도록 설계되었다. : 

(A) 제안된 measure는 cold-start recommendation 상황에서 data가 갖는 domain specific meanings를 단순히 전통적인 measure를 사용하는 것에 비해 더욱 잘 이용할 수 있어야 한다.

(B) 실용성을 위해, 제안된 measure는 쉽게 현존하는 CF system에 plug-in할 수 있어야 한다. 

(C) 제안된 measure는 cold-start condition에 있는 new user에서만 향상된 결과를 보일 뿐 아니라, non-cold-start condition에 대해서도 기존의 measure에 대비하여 쓸만한 성능을 보여야 한다.

위와 같은 목적으로 제안된 PIP measure는 Proximity, Impact, Popularity 의 세가지 요소로 이루어지게 되었다.

PIP measure는 user \(i\)와 user \(j\)에 대한 similarity를 다음과 같이 계산한다. : 

\[\mathrm{sim}(u_i,u_j) = \sum_{k\in C_{i,j}} \mathrm{PIP}(r_{ik}, r_{jk})\]

수식에서 \(r_{ik}\)는 user \(i\)의 item \(k\)에 대한 rating이고, \(C_{i,j}\)는 user 간의 co-rated item set이다.
이때, \(\mathrm{PIP}(r_1, r_2)=proximity(r_1, r_2) \times Impact(r_1, r_2) \times Polularity(r_1, r_2)\) 으로 계산된다.

각각의 요소를 Fig. 3.과 Table2에서 description 하고 있다. 결과적으로는 user가 item에 부여한 각각의 rating을 경우에 따라 penalization 하거나 advantage를 부여함으로써 similarity를 입체적으로 계산한다는 감상을 받게 되었다. 이런 점에서 제안된 PIP measure가 heuristic measure라고 저자는 주장하는 듯하다. 

[미완성][추천시스템/기초] MovieLens 데이터셋에 대해.

Analysis of MovieLens dataset(begginers')

여러 추천시스템 관련 연구를 살펴보면, dataset으로 GroupLens에서 배포하는
MovieLens 데이터셋을 이용하는 경우가 대부분이다.

본 게시글에서는 추천시스템 연구에 앞서 MovieLens 데이터셋 중 가장 작은 데이터셋인
'ml-latest-small'에 대한 기초적인 수준의 EDA를 진행하고자 한다(데이터셋 다운로드 경로).

나중에 포트폴리오를 블로그에 천천히 작성할 예정이지만, 필자는 분석 경험이 매우 짧은 편이며 속해있는 연구실 또한 추천시스템을 전문적으로 다루는 연구실이 아니라 데이터마이닝 연구실이다.

혹시라도 전문적인 수준의 글을 접하고 싶어 찾아오셨다면 뒤로가기 해주셔도 좋고,
이녀석 어떤 실수를 했나 구경이나 해볼까 싶으셔서 읽게 되셨다면,
여러 지적해주시면 좋겠다.

Data EDA

분석 환경은 구글 Colab이다.

# 데이터 경로 설정
path = '/content/drive/MyDrive/ml-latest-small/'

# ml-latest-small의 구성
os.listdir(path)
['ratings.csv', 'tags.csv', 'movies.csv', 'links.csv', 'README.txt']

ml-latest-small dataset은 총 4개의 csv 파일로 구성되어있다. 
각 파일에 대한 shape와 head를 찍어보면 아래와 같다.
각 데이터에 대한 설명은 데이터셋의 zip파일에서 readme를 반드시 읽어보길 권한다.

print(ratings_df.shape)
print(ratings_df.head())
(100836, 4)
   userId  movieId  rating  timestamp
0       1        1     4.0  964982703
1       1        3     4.0  964981247
2       1        6     4.0  964982224
3       1       47     5.0  964983815
4       1       50     5.0  964982931

print(tags_df.shape)
print(tags_df.head())
(3683, 4)
   userId  movieId              tag   timestamp
0       2    60756            funny  1445714994
1       2    60756  Highly quotable  1445714996
2       2    60756     will ferrell  1445714992
3       2    89774     Boxing story  1445715207
4       2    89774              MMA  1445715200

print(movies_df.shape)
print(movies_df.head())

(9742, 2)
                                      title                                       genres
movieId                                                                                 
1                          Toy Story (1995)  Adventure|Animation|Children|Comedy|Fantasy
2                            Jumanji (1995)                   Adventure|Children|Fantasy
3                   Grumpier Old Men (1995)                               Comedy|Romance
4                  Waiting to Exhale (1995)                         Comedy|Drama|Romance
5        Father of the Bride Part II (1995)                                       Comedy

print(links_df.shape)
print(links_df.head())

(9742, 3)
   movieId  imdbId   tmdbId
0        1  114709    862.0
1        2  113497   8844.0
2        3  113228  15602.0
3        4  114885  31357.0
4        5  113041  11862.0

구체적인 EDA에 앞서 데이터셋의 구성 중 PK(Primary Key)가 될법한 변수명들이 눈에 띄어 다른이가 그려둔 ERD가 없을까 찾아보게 되었다. 

사실, ERD를 그려보는 것이 데이터셋 각각에 대한 EDA를 진행하는 것에 도움이 될까 싶긴
하지만 내 기초지식의 일부가 산업시스템공학에 존재하므로 그냥 또 '츄라이' 해본다.

그 중 Github에 vivek-bombatkar란 유저가 ERD를 작성한 것을 보았다. (링크)

genom_tags와 genome_scores를 제외하고 바라보면, 현재 우리가 아무 모델링도 가하지
않은 상태의 데이터셋과 일치하는 ERD가 된다. EDA에 앞서 ERD를 수행하는 모습은 일전에 dacon 대회에 참여했을 때 어떤 유저가 사용하는 것을 보고 지금 여기서도 해보게 되었는데, 확실히 데이터셋에 대해서는 직관성을 더 해주는 것 같다. 앞으로도 애용해야 할 듯 하다.

ratings_df의 info를 살펴보면 아래와 같다. 결측값의 존재 여부도 확인한다.

ratings_df.info() 
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 100836 entries, 0 to 100835
Data columns (total 4 columns):
 #   Column     Non-Null Count   Dtype  
---  ------     --------------   -----  
 0   userId     100836 non-null  int64  
 1   movieId    100836 non-null  int64  
 2   rating     100836 non-null  float64
 3   timestamp  100836 non-null  int64  
dtypes: float64(1), int64(3)
memory usage: 3.1 MB

# 결측값의 수 확인
ratings_df.isnull().sum()

userId       0
movieId      0
rating       0
timestamp    0
dtype: int64

다음으로 user의 movie에 대한 평가횟수 / rating의 평균 / rating의 편차를 확인한다.

movieid_user_df = pd.DataFrame({
    'no_user_wat': ratings_df.groupby('movieId')['userId'].count(),
    'ratings_mean': ratings_df.groupby('movieId')['rating'].mean(),
    'ratings_std': ratings_df.groupby('movieId')['rating'].std()
})
movieid_user_df = movieid_user_df.reset_index()
print(movieid_user_df.shape)
print(movieid_user_df.head(10))


(9724, 4)
   movieId      no_user_wat  ratings_mean  ratings_std
0        1              215     3.920930     0.834859
1        2              110     3.431818     0.881713
2        3               52     3.259615     1.054823
3        4                7     2.357143     0.852168
4        5               49     3.071429     0.907148
5        6              102     3.946078     0.817224
6        7               54     3.185185     0.977561
7        8                8     2.875000     1.125992
8        9               16     3.125000     0.974679
9       10              132     3.496212     0.859381

rating이 부여된 횟수(no_user_wat)를 x축으로 하여 분포를 확인하면 아래와 같다.
추천시스템 관련 연구에서는 sparse dataset의 형태를 거르고 넘어갈 수 없다.

movieid_user_df['no_user_wat'].hist()

(내용 추가 예정)

-------------------------------------

우선 여기까지 하고 게시글을 잠시 멈춘다.
분석 목표에 따라 EDA는 다르게 진행되어야 한다.

장르별 분석이 목표라면 링크의 kaggle 자료를 참고해도 좋을 듯 하다(링크).

[미완성][논문 리뷰] PSO(Particle Swarm Optimization)를 이용한 SVM parameter 튜닝 관련 논문

Support vector machine parameter tuning based on particle swarm optimization metaheuristic. 

(Korovkinas K., Danėnas P. and Garšva G. (2020) “Support vector machine parameter tuning based on particle swarm optimization metaheuristic”, Nonlinear Analysis: Modelling and Control, 25(2), pp. 266–281. doi: 10.15388/namc.2020.25.16517.)

이 논문을 리뷰하게 된 까닭은, 현재 수강중인 비선형최적화 강의의 과제를 위해서이기도 하지만 좀 더 확장하여 modified SVM based RS를 구현하는 것에 그 목적이 있다. 논문 선정 기준은 우선 비선형최적화에 대한 주제를 담으면서도, RS에 적용가능한 모델에 적용가능하고, Q1, SCI급 논문인 것으로 선택했다. 

기준은 교내 포탈에서 제공하는 JCR 랭킹,
검색엔진은 http://www.webofscience.com 를 이용했다. 

(Abstract) 

본 논문은 Particle swarm optimization metaheuristic을 이용한 linear SVM의 parameter tuning을 소개함. 해당 방법은 SVM을 이용한 텍스트 데이터의 분류 정확도 향상을 위해 최적 코스트의 parameter를 찾아줌. 추가적으로, majority voting based ensembling 방법이 제안된 방법의 효율성을 증가시키기위하여 적용되었음.

1 Introduction

SVM은 감성 분류 문제에 가장 자주 쓰이는 ML 알고리즘이며, 여러 고난도의 도메인에서 그 성능을 증명해왔음. 

그러나, 현재 시류에서 사람이 그 수준을 결정하는 manual hyper-parameter selection을 위한 그 어떤 휴리스틱 규칙이나 SVM을 위한 rules of thumb도 제공되지 못했음.

대부분 이러한 hyper-parameter 튜닝에 있어서는, 대부분이 몇가지 휴리스틱 알고리즘을 이용하는데, 유전 알고리즘 또는 이 리뷰의 주제가 되는 PSO(Particle Swarm Optimization), colony optimization 등이 그러한 알고리즘임.

이 중 PSO는 다른 진화 알고리즘과 결합되었을 때 더 좋은 성능을 내는데, [47]의 경우가 좋은 예시임.

앙상블 분류 모형은 자주 쓰이지만, 단일 모형에 비해 오히려 성능이 떨어지는 경우가 많음. 저자는 [4]의 ensemble voting 알고리즘이 감성 분류 문제에서 좋은 성능을 보였다는 것에 동기를 부여받아 텍스트 데이터 분류 문제에서의 LSVM(Linear SVM) 성능을 단순한 방법을 이용해 개선코자 함.

2 Relevant algorithms

2.1 Support vector machines

SVM에 대해서는 다른 게시물에서 다루는 중이며 지속 업데이트 될 예정이다. 본 게시글에서는 간단히만 다루도록 한다.

본 논문의 linear SVM은 학습데이터가 매우 커다랄 때를 목적으로 최적화된다. 

훈련 벡터집합 \(x_i\in\mathbb{R}^n\), \(i=1, ... , l\)이 2클래스 집합이고, 분류문제 \(y\in\mathbb{R}^l\)이 \(y_i=\{1,-1\}\)라고 했을 때, 결정 함수(결정 경계의 함수)는 다음과 같다: 

\[sgn(w^Tx)\]

이후 논문에서는  L2 정규화된 L1 loss SVC(support vector classifier)가 해결하는 primal problem과 L2 정규화된 L2 loss SVC가 해결하는 primal problem의 dual representation 된 형태가 주어져 있다. 결과적으로는 L1-정규화가 sparse solution \(w\)를 generate한다. SVM은 기본적으로 결정경계를 찾는 것이 목표이므로, 본 논문에서의 linear SVM 또한 동일한 목적을 갖는다.

2.2 PSO(Particle Swarm Optimization) 알고리즘

PSO 자체는, 따로 게시글을 만들어 다뤄보아야 할 것 같다. 직관적인 이해는 어느정도 했으나, 역시나 수식이 문제다. 우선은 논문에서 다룬 수준에서 겉핥기라도 해보는 것이 좋겠다.

우선 PSO는 논문 reference의 [11]에서 소개된 이론이다. 주로 Genetic algorithm과 비교되는 편인데, 그 이유는 조금 더 찾아보아야겠다. 아마도, optimizer로 사용되는 메타휴리스틱 알고리즘 계열이지 않을까 싶다. NP-hard 문제들에도 제법 많이 사용되는 것으로 보았을 때 objective가 같기 때문일것도 같다. 

PSO는 간단히 말해 개별 입자가 서로 다른 속도(방향의 개념이 포함)로 움직이면서, 개별 입자의 best fit을 찾아나가는 알고리즘이다. 

\(t\)를 discrete time step이라고 할 때, \(a_i(t)\)는 i번째 입자의 위치이고, 이 때 i의 속도는 \(v_i(t)\)이다. 수식으로 나타내면 다음과 같다. : 

\[a_i(t+1)=a_i(t)+v_i(t+1)\]

이때, \(a_i(0)\sim\mathrm{U}(a_{min}, a_{max})\)인데, 어떤 논문 중에서는 이 초기값의 위치를 K-means 등을 이용해 설정하기도 하는 듯하다. 그렇다면 아마도 GMM을 이용한 방법론을 소개한 논문도 있을 것이라 생각된다.

아무튼 이때 속도 \(v_i(t)\)는 개별 입자에 대한 경험적 지식과 그 입자 주변의 이웃 입자의 정보 변화에 모두 영향을 받는다는 가정을 한다. 때문에 Global Best PSO에서 입자 i의 속도는 다음과 같이 계산되고, 앞선 가정은 \(c_1\), \(c_2\)를 통해 수식에서 구현된다. :

\[v_{ij}(t+1)=v_{ij}(t)+c_1r_{1j}(t)[b_{ij}(t)-a_{ij}(t)]+c_2r_{2j}(t)[\widehat{b}_{j}(t)-a_{ij}(t)]\]

수식에서 확인할 수 있듯이, 이때의 i번째 입자가 j번째 차원(\(j=1, ... , n_a\))에서 t-step에서 갖는 속도는 \(v_{ij}(t)\)로 나타낼 수 있다. 

언급했듯이, \(c_1\), \(c_2\)는 속도에 영향을 주는 경험적 + 근접이웃에 의해 결정되는 상수이다. 이 부분도 사실 자세한 조사가 필요하다. 결국은 처음 PSO를 제안한 논문을 확인해야 할 것 같다. 당장에 드는 의문은 이러한 상수 또한 일종의 parameter로 보인다는 것이다. 

\(r_{1j}(t), r_{2j}(t)\sim\mathrm{U}(0,1)\)는 stochastic element를 해당 수식에 부여하는 역할이다.

그리고, \(b_i\)는 personal best position이라 명명된 것으로, 최초의 t-step으로부터 마지막 t-step까지 i번째 입자가 방문했던 모든 position 중 가장 best 인 position을 일컫는다. \(t+1\) 단계에서의 personal best position은 다음과 같이 계산된다. : 

\[\begin{cases}b_i(t) & \text{if  } f(a_i(t+1)) \geq f(b_i(t)) \\ a_i(t+1) &\text{if  } f(a_i(t+1)) < f(b_i(t))\end{cases}\]

이때의 함수 \(f : \mathbb{R}^n_{a} \to \mathbb{R}\)는 fitness function으로, 진화 알고리즘과 같이 사용되는 경우에는 이 함수가 현재의 해가 최적해에 얼마나 근접했는지를 나타낸다. 그러니까, 이 함수가 particle의 퍼포먼스 또는 품질을 measure한다. 관련 reference가 논문의 [12]이다.

결과적으로 global best position인 \(\widehat{b}(t)\)는 t-step에서 다음과 같이 정의된다 : 

\[\widehat{b}(t)\in\{b_0(t), ... , b_{n_s}(t)\}, f(\widehat{b}(t))=\min\{f(b_0(t)), ... , f(b_{n_x}(t))\}\]

이때, \(n_s\)는 swarm에 속한 particle의 총 갯수이다. 

이상으로, 간단한 수준에서 PSO를 살펴보았다. 이론의 사상은 마치 새 떼나 정어리 떼에 비유할 수 있지 않을까 싶고, 수식화 되었다는 것이 흥미롭다. 특히 관심갖게 되는 속성으로는 개별 입자의 속도가 아닐까 싶은데, 매 시점마다 그 속도가 달라진다는 점에서 일반적으로의 속도에 빗대기는 어려워보인다. 허무맹랑한 상상일지 모르겠으나, 속도 외에 다른 물리적인 속성을 부여하면 또 완전히 다른 알고리즘이 탄생할 수 있지 않을까 싶기도 하다.

3 Proposed Method

(내용 추가 예정)