devmoon

이전에 Item2Vec이나 Matrix Factorization을 사용할 때, 벡터공간에 유저나 아이템을 투영시켜서 현재 아이템과 가장 가까운 벡터를 찾아 추천하는 방법을 사용했었다. 아이템의 개수가 100개 정도라면 모든 벡터와 현재 벡터를 비교해서 얼마나 유사한지, 얼마나 가까이 있는지 연산을 할 수가 있지만, 아이템의 개수가 1억 개가 넘어간다면 이를 어떻게 처리해야 할지도 생각해보아야 한다. 따라서 이번에는 완벽하게 가까운 벡터를 찾아낼 수는 없지만, 높은 정확도를 가지고 가까운 벡터를 찾도록 도와주는 ANN에 대해서 소개한다. Brute Force KNN K-NN은 현재 나(벡터)와 가장 가까운 $k$개의 벡터를 의미한다. 가장 단순하게 생각했을 때, 모든 벡터와의 거리 연산, 유사도 연산을 사..

ABSTRACT 당시 NLP분야에서 Neural embedding algorithm을 통해 단어를 잠재 벡터로 표현하는 방법에 대한 뛰어난 성과가 발표되었다. 그 방법 중 하나로 word2vec 이라고도 알려진 Skip-gram with Negative Sampling (SGNS)가 특히 좋은 성능을 보여주었다. 여기에 영감을 받아 저자들은 추천 시스템의 아이템 기반 협업 필터링(IBCF)에 word2vec을 적용시킨 item2vec을 발표한다. INTRODUCTION AND RELATED WORK 당시 추천 시스템의 핵심은 아이템 간 유사도를 구하는 것이었다. 저자는 많은 추천 시스템들이 유저와 아이템의 저차원 입베딩을 학습하는데 초점을 맞추고 있지만, 아이템 유사도 자체를 구하는 것이 중요하다고 한다..

ABSTRACT 최근에 발표되었던 Skip-gram 모델은 단어의 문법적, 의미적인 유사도를 잘 표현하는 벡터를 학습하는 효과적인 모델이었다. 이번 논문에서는 벡터 표현력의 품질과 학습 속도를 향상할 수 있는 몇 가지 방법에 대해 소개한다. 그 예로, 자주 등장하는 단어들을 subsampling 하여 큰 속도 향상과 기존보다 균형 잡힌 단어 표현력을 학습시킬 수 있었다고 한다. 또한 기존에 사용하던 Hierarchical softmax를 대체하는 negative sampling에 대해 소개한다. 기존 모델로 얻어낸 벡터의 한계는 구(Phrase)를 잘 해석하지 못한다는 점이었다. 예를 들어, Canada와 Air를 더하였을 때, Air Canada의 정보를 잘 구해내지 못하였다. 따라서 저자는 이런 문제..

Heavy Light Decomposition, 줄여서 HLD라고 불리는 알고리즘은 하나의 트리를 여러 개의 서브 트리로 분할하는 방법이다. 이름에 나와있듯이 트리를 무거운(Heavy) 서브트리와 가벼운(Light) 서브 트리로 분할하게 된다. 일반적으로 이 알고리즘은 세그먼트 트리를 트리위에서 적용하기 위해 사용한다. 예를 들자면, 트리위의 어떤 두 정점 $u$와 $v$가 주어졌을 때, 두 정점을 잇는 경로 길이의 합이나 경로 사이에 존재하는 가중치의 최솟값을 여러 번 구하는 문제이다. 가장 먼저 1차원 배열 위에서의 세그먼트 트리의 적용이 아닌 트리 위에서의 세그먼트 트리 적용이기 때문에 어떤식으로 정점들을 구성해서 세그먼트 트리를 사용할 수 있도록 변형할지 생각해봐야 한다. 이를 위해 아래와 같이 ..

ABSTRACT 저자들은 이번 논문에서 단어들을 벡터 공간에 효과적으로 표현하는 2개의 새로운 모델을 소개한다. 각각의 모델들은 단어의 유사도를 기준으로 평가되었으며, 기존에 존재하던 신경망 기반의 모델들과 어떤 성능적 차이가 있는지 보여준다. 결과로 기존의 신경망 모델보다 더 적은 계산량을 가지고 훨씬 좋은 성능을 보임을 증명하였을 뿐만 아니라, 구문론적 그리고 의미론적 관점에서 단어의 유사도를 측정하는 성능이 저자들이 가진 데이터셋에 대해 SOTA에 해당하는 성능을 보였다. INTRODUCTION 많은 NLP의 모델들 그리고 여러 기술들에서 단어를 가장 작은 단위로 다루게 된다. 단어를 기본 단위로 두게 되면 여러 장점들을 가져올 수 있는데 대표적으로 일단 단순하고 강건(Robust)하며 많은 데이터..

ABSTRACT 아이템 추천이라는 작업은 아이템 목록에서 유저의 선호도에 맞추어 좋아할 만한 아이템들을 추천하는 것을 말한다. 저자들은 그런 추천 시스템을 만들기 위해 Implicit Feedback을 사용하였다. 물론 기존에도 Implicit Feedback을 사용하여 아이템 추천을 하는 Matrix Factorization (MF)이나 k-nearest-neighbor (kNN) 모델이 존재했었다. 하지만 이 2가지 모델들은 아이템을 추천할 때, 유저의 선호도에 맞추어 아이템들에 ranking을 매기고자 했는데 학습과정에서 ranking을 직접 최적화하는 부분이 없다는 한계가 있었다. 이에 저자들은 BPR-OPT 라는 새로운 최적화 방법을 소개한다. BPR-OPT는 베이즈 이론에서 등장하는 사후 확률..

1. 문제 출처 https://www.acmicpc.net/problem/13309 13309번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 2. 문제 접근 특정 구간내에 그래프가 연결되어 있는지의 정보를 O(log N)의 시간만에 알아내기 위해 세그먼트 트리 자료구조를 사용해야 했다. 하지만, 트리 구조이기 때문에 트리구조를 체인으로 분할 하는 heavy-light-decomposition 을 적용하여 문제를 해결해야 한다. 먼저 트리의 루트는 항상 1이라고 고정된 상태이기 때문에, 1을 루트로..

이번 논문은 추천 시스템에서 정말 중요한 개념 중 하나인 Matrix Factorization에 대해서 소개하고, 그 성능을 증가시키기 위한 여러 가지 기법에 대해 기술한 논문이다. 개인적으로 추천 시스템의 기초가 되는 논문이라고 생각되어서 선정하게 되었고, 규제화(regularization)부터 시작해서 시간적 요소를 반영하는 것까지 생각한 것들이 흥미롭게 읽은 논문이다. 당시에 진행하던 Netflix Prize 대회는 넷플릭스의 영화를 사용자에게 얼마나 더 잘 추천하는지를 겨루는 대회였다. 해당 대회에서 Matrix Factorization 기법을 사용한 추천의 성능이 이웃기반 추천 시스템보다 우월했다. 따라서 저자는 Matrix Factorization 기법에 다른 테크닉을 추가하여 성능을 더 끌어..