brunch

You can make anything
by writing

C.S.Lewis

by 전영환 May 26. 2019

Airbnb에서는 유사한 집을 어떻게 찾을까

Tech Review of Airbnb #4

Listing Embeddings in Search Ranking

Listing Embeddings for Similar Listing Recommendations and Real-time Personalization in Search Ranking


Airbnb 시장은 잠재적 고객들이 검색 결과를 통해 탐색하는 다양한 리스트들을 보여준다. 그리고 이러한 리스트들은 사용자들이 검색 페이지에서 순위를 결정하는 여러 신호들을 수집하여 만들어진 정교한 Machine Learning 모델을 통해 만들어진다. 고객이 Airbnb Home을 보고 나면, 그들은 검색 결과로 돌아가거나 지금 보고 있는 Home과 유사한 목록을 살펴볼 수 있다. Search Ranking과 유사한 리스트는 사용자가 예약이라는 행동을 하도록 99%의 확률로 유도한다. 


이번 포스트에서는 실시간 검색 랭킹 개인화(Real-Time Personalization in Search Ranking)와 유사 리스트 추천(Similar Listing Recommendation)을 개선하기 위해 사용한 Airbnb의 Listing Embedding 기술을 설명하고자 한다. Airbnb Home들의 Embedding은 검색 세션 데이터를 통해 학습되었으며, 리스트 간의 유사도를 계산하게 해 준다. Embedding은 위치, 가격, 리스트 유형, 리스트 스타일과 구조와 같은 다양한 featrue들의 정보를 포함하고 있다. 우리는 Embedding을 기반으로 한 접근이 Personalization과 Recommendation에 있어 가장 강력하고, 유용하다고 믿는다.



Background On Embeddings


과거의 많은 NLP(Natural Language Processing) Application은 단어를 High-dimensional의 Sparse Vector로 표현하는 기법을 사용했었다. 최근에는 Low-dimensional로 Neural Network를 사용하여 word embedding을 학습하는 방향으로 바뀌고 있다. 이 Network들은 단어의 순서와 함께 등장하는 비율(co-occerence)을 통해 학습되며, 문장 내에서 빈번하게 자주 등장하는 단어는 통계적으로 연관도가 높다는 가정을 하고 있다. Word Representation Learning에 있어 확장성이 좋은 CBOW와 Skip-gram 모델이 개발됨에 따라, Embedding 모델은 대형 텍스트 데이터를 통해 학습한 경우, 많은 전통적 Language task에서 최고의 성능을 보이는 것으로 나타났다.


더 최근에는 Embedding의 개념이 단어의 표현을 넘어 NLP 영역 밖으로도 확장되었다. 웹 검색, 전자 상거래 등의 영역에서도 문장의 Word Sequence를 이용하여 Word Embedding을 시키는 것처럼, User Action의 Sequence를 이용하여 User Action을 Embedding 시킬 수 있다는 것을 깨달았다. 예를 들어, 클릭되거나 구매된 아이템들, 클릭된 질의(Query)나 광고를 활용하여 Item의 Representation을 학습하는 것들이 있다. 이러한 Embedding들은 웹 상의 다양한 추천을 하는데 활용할 수 있다.



Listing Embeddings


주어진 Data set에 N명의 사용자가 클릭한 Session들이 있다고 가정해보자. Session은 L1,.... Ln의 클릭된 Listing들의 Sequence를 갖는다고 하자. 새로운 Session은 연속된 클릭 사이에 최소 30분의 간격을 갖는다. 주어진 Data set에서, 유사한 Listing들이 가까이 모여있는 Embedding space에 Embedding 된 32차원짜리 각 Listing Li의 Embedding을 학습하는 것을 목표로 한다.


Listing의 차원은 실시간 유사도 계산을 위한 Computational Cost와 Offline Performance 간의 Trade-off를 통해, 32차원으로 결정했다.


Embedding을 학습하는 것에는 다양한 방법이 있다. 우리는 Negative Sampling에 초점을 맞추었다. 이것은 Embedding들을 random vector로 초기화하는 것에서 시작한다. 그리고 이 Embedding들을 Session 내의 Listing들을 Window 단위로 읽어가며, Stochastic Gradient Descent 기법으로 업데이트하였다. 각 단계에서 Window의 중심에 있는 Central Listing들은 근처에 있는 positive context listing들과 가까워지도록 학습된다. 동시에 해당 window 내에 없는 무작위로 추출된 listing들인 negative context listing들에 대해서는 멀어지도록 학습된다.



아래에서는 우리의 case에 적용하기 위해, 우리가 수정하여 수행한 것들을 설명하겠다.


Using Booked Listing as Global Context : 우리는 인접 클릭 목록뿐 아니라, 최종 예약 목록까지 잘 예측할 수 있도록 최적화하기 위하여, Booking으로 종료되는 Session들만 이용하여 학습하였다. Session 내에서 Window를 이동하며 학습하는 동안 Booking Listing은 Global Context로 사용하여, Central Listing vector를 업데이트하는데 반영하였다.


Adapting to Congregated Search : 온라인 여행 예약 사이트를 이용하는 대부분의 사용자는 그들이 머물기 원하는 지역 내에서만 검색한다. 결과적으로, Central listing이 주어졌을 때, positive context listing들은 대게 지역 내에서만 존재하며, negative context listing들은 다른 지역에 존재한다. 우리는 이러한 data imbalance가 지역 내 유사성을 학습하는 데 있어 차선으로 학습하는 것을 확인했다. 이러한 문제를 해결하기 위해, central listing의 지역에서 추출된 random negatives Dmn set을 추가하였다.


위의 수정사항을 고려한 Optimization objective는 아래와 같다.

l 은 central listing을 의미하며, vector v(l)은 업데이트된다.

Dp는 central listing과 positive context listing의 pair (l, c)의 set이다. 서로 가깝게 Embedding 되도록 한다.

Dn는 central listing과 negative context listing의 pair (l, c)의 set이다. 서로 멀게 Embedding 되도록 한다.

lb는 Global context로 사용되는 booked listing이다. Central listing vector와 서로 가깝게 Embedding 되도록 한다.

Dn는 central listing과 동일 지역 내의 negative context listing의 pair (l, mn)의 market negatives set이다. 서로 멀게 Embedding 되도록 한다.


8억 개 이상의 검색 클릭 세션을 사용하여 450만 개의 active listing을 Embedding 하였으며, 이것은 좋은 품질을 보이는 것을 확인할 수 있었다.


Cold-start Embeddings. Airbnb에는 호스트들에 의해 새로운 listing들이 생성되고 등록된다. 이러한 listing들은 training data에 나타나지 않았었기 때문에 embedding을 가지고 있지 않다. 새로운 listing들에 대한 embedding들을 생성하기 위해, 3개의 지역적으로 가장 가까운 listing들을 구하고, 새로운 listing들과 동일한 type이며 같은 가격 범위를 가지고 있는 lising들을 구하여 그것들의 평균 vector를 구해서 사용하였다.



What did Embeddings Learn?


Listing들의 특징이 embedding들에 잘 학습되었는지 확인하기 위해, 우리는 다양한 방식을 하용하였다. 첫 번째, 지리적 유사성이 잘 학습되었는지 확인하기 위해, 우리는 K-means clustering 기법을 학습된 embedding들에 적용하여요 보았다. 아래에 있는 그림은 California에 있는 listing들을 100개의 cluster로 나타낸 것이며, 유사한 지역에서는 같이 clustering 된 것을 확인할 수 있다. 두 번째로, 우리는 서로 다른 type(Entire Home, Private Room, Shared Room)과 가격 범위의 listing들 간의 cosine similarity를 확인하였다. 이를 통해, 같은 type과 동일한 가격 범위 내의 listing 간의 cosine similarity가 더 큰 것을 확인할 수 있었다. 결과적으로, 우리는 두 가지 listing의 특정이 embedding에 잘 학습되어 녹아들어 가 있음을 확인했다.



가격과 같은 몇몇 listing의 특징은 학습될 필요가 없다. 왜냐하면 이러한 것들은 listing의 meta-data로부터 추출할 수 있기 때문이다. Architecture, style, feel과 같은 다른 type의 listing의 특징은 listing feature 형태로 추출하기 더욱 어렵다. 이러한 특징을 평가하고 Embedding 공간에서 빠르고 쉽게 탐색하기 위하여, 아래와 같은 Tool을 만들었다.


https://youtu.be/1kJSAG91TrI


이 비디오 Houseboat, treehouse, castle 등과 같은 특별한 architecture의 listing들과 유사한 listing들을 찾을 수 있는 다양한 예시를 보여준다.



Offline Evaluation of Listing Embeddings


실제 검색 traffic에서의 recommendation application을 테스트하기 전, 우리는 몇 가지 오프라인 테스트를 수행하였다. 우리는 hyperparameter들의 선택, training data의 구성, 알고리즘 변경 아이디어, embedding 차원과 관련된 빠른 결정을 하기 위해, 다양한 방식으로 학습된 몇 가지 embedding들을 비교하는데 이 테스트들을 사용하였다.


학습된 embedding들을 평가하는 방법 중 하나는 사용자들이 recommending listing들 중에서 가장 최근 클릭을 바탕으로 얼마나 많이 예약을 하는지이다.


좀 더 구체적으로, 가장 최근에 클릭된 Listing들과 순위를 매겨야 할 후보의 Listing들이 주어졌다고 해보자. 여기에는 결국 사용자가 예약한 목록이 포함되어 있다. 클릭된 listing들의 Embedding과 후보 Listing들의 Embedding 사이의 cosine similarity를 계산하여, 우리는 후보 listing들의 순위를 매기고 그 들 중 예약한 listing의 순위를 살펴볼 수 있다.


아래의 도표에서는, Embedding의 Similarity를 기반으로 re-ranking 하였을 때에 대한 평가이며, 그때 예약된 Listing들의 평균 순위를 볼 수 있다. 또한 어떤 Listing을 예약하기 전에 17번의 클릭까지도 일어나는 것을 알 수 있다.



우리는 몇 가지 embedding의 버전을 비교하였다.

1) d32 regular : original embedding algorithm만을 이용해 학습한 버전

2) d32 booking global : 1번 버전에 예약 listing을 global context로 적용해 학습한 버전

3) d32 booking global + market negatives : 2번 버전에 앞에서 설명한 동일 지역 내의 market negative sample을 적용해 학습한 버전


3가지를 비교하여 보았을 때, 3번 버전의 모델이 가장 좋은 preformance를 보이는 것을 확인할 수 있다.



Similar Listings using Embeddings


모든 Airbnb Home의 페이지는 지금 보고 있는 Home과 동일한 날짜에 사용할 수 있는 유사한 추천 목록을 볼 수 있는 Similar Listing 기능을 제공하고 있다.



기존에 사용한 Similar Listing의 알고리즘을 테스트할 때, Similar Listing은 우리의 메인 검색 랭킹 모델을 동일한 지역에서 적용하여 나온 목록에서 동일한 가격 범위와 listing type을 필터링 한 목록으로 구성하였다.


우리는 A/B 테스트를 수행하여 기존의 Similar Listing 알고리즘과 비교하였으며, Embedding space에서 가장 가까운 k개의 listing 목록을 생성하였다. 더 정확히 말하면, 주어진 listing embedding들이 주어진 상태에서, 특정 listing v(l)과 동일 지역 내의 이용 가능한 listing들의 vector v(lj)들과의 cosine similarity를 계산하였다. 가장 유사하다고 생각되는 k=12개의 listing들을 similar listing으로 사용하였다.


Embedding을 기반으로 한 알고리즘은 A/B 테스트에 있어, similar listing들의 CTR 측면에서 21%의 증가를 보여주었고, 예약 측면에서 4.9%의 게스트의 증가를 보여주었다.



Real time personalization in Search using Embeddings


지금까지 우리는 Embedding들이 실제로 listing들 간의 similarity를 계산하는데 효율적으로 사용될 수 있음을 확인하였다. 우리의 다음 아이디어는 세션 내 personalization(개인화)를 하는데 실시간으로 Search Ranking을 정하는데 이 기능을 적용하는 것이었다. 여기서의 목적은 검색 Session을 시작한 이후, 사용자가 좋아했다고 생각하는 listing들과 유사한 목록은 더 많이 보여주며, 사용자가 덜 좋아했다고 생각하는 listing과 유사한 목록은 더 적게 보여주는 데 있다.


이 목적에 도달하기 위하여, 우리는 각 사용자에 대하여 두 가시 event들의 set을 실시간으로 수집하였다. (Kafka를 사용하였다.)


Hc : 사용자가 최근 2주간 클릭한 listing들의 id의 집합

Hs : 사용자가 최근 2주간 skip 한 listing들의 id의 집합, skipped listing은 클릭된 listing에 비하여 더 높은 순위였으나 클릭되지 않고 제외된 listing들을 얘기한다.


다음으로 사용자가 검색을 할 때, 각 candidate listing들에 대하여 2가지 similarity measure를 계산하였다.


EmbClickSim : candidate listing과 Hc(Clicked) 사이의 similarity들

EmbSkipSim : candidate listing과 Hs(Skipped) 사이의 similarity들


위의 두 가지 Similarity measure는 다음으로 Search Ranking Machine Learning 모델이 Candidate listing의 ranking을 하는 데 있어 추가적인 signal로 사용되었다. (새로운 Ranking model을 생성하는 데 있어 데이터에 label을 붙이는 것으로 사용되었다.)


Embedding similarity가 우리가 의도한 바를 제대로 이용하여 학습하였는지 평가하기 위하여, 우리는 아래의 dependency plot들을 그려보았다. 

위의 왼쪽 그래프는 EmbClick의 값이 클수록 모델 점수가 높아지는 것을, 오른쪽 그래프는 EmbSkipSim의 값이 클수록 모델의 점수가 낮아지는 것을 보여준다.


위의 그래프를 살펴본 결과, 의도한 대로 학습이 잘 된 것을 확인할 수 있다. 이 실험은 성공적이라고 결론 지었으며, 2017년 여름 실제 서비스에 실시간 개인화(real-time personalization) 기능을 탑재하는 것으로 이어졌다.






이 글은 아래의 원문을 번역/의역 및 요약하였습니다. 중간중간 파란색으로 표시된 글씨는 번역자의 견해입니다.


https://medium.com/airbnb-engineering/listing-embeddings-for-similar-listing-recommendations-and-real-time-personalization-in-search-601172f7603e


브런치는 최신 브라우저에 최적화 되어있습니다. IE chrome safari