[Uber Engineering 블로그 리뷰 & 번역 - Food Discovery with Uber Eats: Recommending for the Marketplace]

 

 

 

지난 포스팅이 우버잇츠의 검색/추천 에서 <Knowledge Graph + Search Result Process>에 초점을 맞춘 포스팅이었다면, 이번 포스팅은 2부작 성격을 띠며 개인화와 추천에 조금 더 초점을 맞춘 내용이다. 그 중에서도 최적화 모델과 그 구조에 대해 이야기한다. 이 글 역시 마찬가지로 원문에 주관적 해석을 약간 덧붙인 번역문에 가까우니, 영어가 자신있는 분은 원문을 읽는 것을 권장한다.

 

https://eng.uber.com/uber-eats-recommending-marketplace/

 

 

---

 

1. Our recommender system's journey

 

 

Uber Eats의 추천/랭킹 모델의 초기버전 에서는 유저-레스토랑의 주문 발생 확률을 모델링하는 single objective optimizing을 사용했다고 한다. 그리고 점차 ML, Personalization 요소를 넣으면서 개인화된 모델을 개발하기 시작했고, 단순한 CVR 랭커에서 개인화 모델로 발전할수록 효과를 톡톡히 봤다고 한다. 다만, 이 단계에서 추천시스템이 커질수록 발생하는 cold-start 문제를 경험하게 되었다고 한다.

 

 

신규 입점된 레스토랑이 그 레스토랑 자체의 퀄리티에 비해 기대 이하의 주문량을 받고 있거나, 아예 노출도 되지 않는 경우들이 발견된 것이다. 그래서 이를 시스템적으로 해결하기 위한 방안들을 모색하기 시작한다.

 

 

---

 

 

2. The marketplace

 

 

Food-tech 도메인에는 크게 3가지 요소가 있다. 첫 번째는 당연히 앱을 사용하는 유저들이고 두 번째는 레스토랑의 운영자들이다. 그리고 마지막으로 유저와 레스토랑을 연결해주는 배달 파트너가 있다. 

 

이러한 마켓플레이스에서 문제가 발생하는 상황은 무엇일까, 만약 엄청나게 많은 주문이 특정 레스토랑에 몰리는 상황을 가정해보자. 이를테면 '배떡'이라는 브랜드가 갑자기 엄청난 인기를 얻게 되었지만 특정 지역 한 군데 밖에 없는 레스토랑이라고 해보자. 이 때 레스토랑은 갑작스러운 주문 증가를 감당하지 못하기 때문에 준비가 점점 더 늦어지고 설상가상으로 음식의 질까지 낮아질 수도 있다. 혹여나 음식점에서 모든 주문을 훌륭하게 처리하고 시간 내에 다 조리한다고 해도, 충분한 수의 라이더를 모집하는 것은 더 어려운 문제이다. 이러한 공급 역학은 플랫폼 전체에 악순환의 연결고리가 될 수 있다.

 

 

---

 

3. Eaters

 

 

그래서 좋은 큐레이션을 해주는 것은 공급 플랫폼을 잘 유지함에 큰 도움이 될 수 있다. 유저 입장에서 좋은 큐레이션의 기준은 다음과같다.

 

● 식당 자체가 얼마나 인기가 있는가, 그리고 그 인기를 결정짓는 중요한 피쳐는 무엇인가? : 주문 수로 기준을 할 지, 별점을 기반으로 할 지, CTR 혹은 CVR을 기준으로 할 지 등이 있다.

● 식당의 대표적인 특징은 무엇인가? : 배달을 빨리 하는 레스토랑일 수도 있고, 특이한 메뉴를 파는 레스토랑일 수도 있다.

● 컨텍스트 요소는 무엇인가? : 현재 시간대는 언제인지, 배달 경로의 교통 상황은 어떤지, 평일인지 주말인지 등의 요소가 있을 수 있다.

● 유저를 가장 잘 표현하는 요소가 무엇인가? : 지금까지 몇 번이나 주문했는지, 어떤 카테고리의 요리를 가장 자주 주문하는지, 이 사람이 신규 가입 유저인지 등의 유저 요소를 고려할 수 있다.

● 유저-레스토랑 간의 특정한 선호도를 표현하는 요소는 무엇인가? : 어떤 유저가 특정 레스토랑을 얼마나 자주 클릭하는지, 혹은 주문하는지에 대한 것을 살펴보아야 하고, 해당 레스토랑에 어떤 평점을 남겼는지도 확인해 볼 필요가 있다.

● 취향을 어떻게 파악할 것인가? : 이를테면 비슷한 입맛을 가진 유저를 표현하는 것이 있을 수 있고, 비슷한 퀄리티의 요리를 하는 레스토랑을 표현할 수도 있다. CF(Collaborative Filtering)의 관점에서 이를 생각할 수 있다는 것이다.

 

여러 가지 기준을 정의했다면, 각 기준을 반영할 수 있는 모델링 작업과 개발들이 필요하다. 이를테면, 취향 파악을 기반으로 하는 추천서비스를 만든다고 하면 CF를 Baseline 모델로 하는 개발 과정이 필요하다. 혹은 식당의 인기 요소를 기반으로 하는 추천서비스라면, 특정 피처를 기준으로 집계하여 Order by 하는 서비스를 구현할 수도 있다. 이 단계에서 끊임없는 연구와 실험을 하는 것이 Discovery 서비스의 임무이다.

 

 

 

---

 

 

4. Diversity

 

 

이번에는 추천시스템에서 흔히 등장하는 떡밥인 Diversity(혹은 Serendipity)의 이야기를 할 차례이다. 최적화는 분명 추천시스템에서 가장 중요한 관점이지만, 최적화가 항상 최선의 방법은 아니다. 만약 치킨을 좋아해서 지금까지 치킨만 주문했던 유저가 있다고 생각해보자. 대부분의 개인화 모델은 그 유저에게 치킨과 높은 관련성이 있는 레스토랑과 메뉴를 추천해줄 가능성이 높다. 그렇게 되면 치킨만 나오게 되는 재미없는 추천이 된다.

 

그래서 Personalized diversification 알고리즘을 잘 개발하는 것이 개발팀의 목표가 되었고, 이를 위해 유저 프로파일과 레스토랑 프로파일을 벡터 표현으로 하는 optimize combined objective 모델을 만들었다고 한다. 

 

 

 

5. Keeping eaters on our platform

 

 

유저를 플랫폼에 lock-in 시키기 위해 중요한 것은 단순히 그럴싸해 보이는 추천(CTR, CVR이 높아지는 추천)을 잘 하는 것도 있겠지만, 더 나아가서는 실제로 그 레스토랑의 음식에 얼만큼 만족하느냐를 정확하게 예측하는 것이 더 중요할 수도 있다. 그래서 추천시스템에 보다 장기적인 성공의 요소를 집어넣을 필요가 있다. 그래서 delayed signal (재주문 확률 예측) 모델링을 시도했다. 어떤 사람이 특정 레스토랑에서 재주문할 확률을 모델링하는 과정에서 사용한 피쳐는 과거의 주문 경험에 기반한다. 그 요소로는 음식 배달 시간 불일치, 배달 준비 시간, 최종적으로 레스토랑에 내린 별점 등의 요소가 있다.

 

 

---

 

 

6. Restaurant-partners

 

 

플랫폼 생태계를 잘 유지하기 위한 것 중에는 레스토랑 파트너(식당 운영자)에게 주의를 기울여주는 것 역시 포함된다. 인기있는 레스토랑이 되는 것은 전적으로 본인에게 달려있는 것이기는 하지만, 플랫폼의 입장에서 공평한 기회를 주는 것은 매우 중요한 일이다.

 

앞서 언급한 추천시스템들은 주로 과거의 데이터에 의존한다. 그래서 cold-start 문제를 반드시 겪게 되는데, 신규 입점한 레스토랑들에게도 기회를 주려면 이러한 시스템은 그다지 공정하지 못하다. 우버잇츠에서는 이 문제를 해결하기 위해 MAB 프레임워크를 사용한다. 그리고 블로그 원문에 언급된 MAB 알고리즘은 UCB를 예로 들었다.

 

(참고 : MAB와 관련된 내용)

 

 

---

 

 

7. Delivery-partners

 

 

배달 기사는 배차 최적화 시스템(링크)을 제공함으로써 잘 관리하고 있기는 하지만, 앱의 전반적인 추천 경험을 더욱 좋게 만들면 배달 기사의 경험 역시 향상시킬 수 있다는 사실을 발견하였다. 그 원인은 배달 기사의 가장 중요한 동기부여는 바로 배달비 인센티브이기 때문인데, 홈 화면에 노출되는 추천을 배달 기사의 예상 도착시간과 맞물려 잘 추천하게 되면, 큰 관점에서 모든 배달기사가 효율적으로 움직일 수 있게 될 것이다. 그러면 배달 기사 개인이 얻을 수 있는 배달 기회가 많아지게 된다. 배달 기사의 위치나 예상 픽업시간 등과 함께, 최종적인 도착 시간까지 잘 고려해야 한다. 이 내용이 바로 ETA, ETD(Estimated Time of Arrival, Estimated Time of Departure)와 관련된 내용이고, 자세한 것은 역시 링크의 내용을 참고하자.

 

 

---

 

 

8. Multi-objective optimization

 

 

지금까지 설명한 마켓플레이스의 모든 측면을 동시에 최적화하는 그림이 물론 가장 이상적이겠지만, 당연히 현실은 그렇지 않다. 여러 개의 목표들이 서로 trade off의 관계를 갖게 된다. 아래의 그래프는 이러한 trade off의 대표적인 예를 든 것으로, 인기 있는(CVR 높은) 레스토랑의 노출 기회가 줄어들수록, 즉 신규 레스토랑 혹은 소외된 레스토랑의 노출 기회가 많아질수록 전체적인 CVR은 줄어든다는 것이다.

 

 

multi-objective optimization은 이러한 trade off를 절충할 수 있는 수식으로 구성한다. 아래의 수식은 총 주문수와 총 주문액 두 가지 목표를 가진 최적화에 관한 수식이다.

 

수식 1

 

수식에서 사용한 Norm은 Frobenius norm으로, matrix 전체에 대한 L2 norm을 계산하는 것이다. U는 uniform ranking 계수로, matrix 전체 크기로 1을 나눈 값이다. 레스토랑마다 일종의 최소확률을 넣어주는 역할을 하는 것이다. 그리고 여기에서 지칭하는 matrix는 X_ij 와 관련된 매트릭스를 의미하며, 레스토랑 J가 유저 I에게 추천될 확률을 의미한다. 이 확률은 위에서 언급한 ML 모델을 통해 추정된 확률값이며, 수식에 등장하는 나머지 기호들과 설명은 아래와 같다.

 

 

그래서 기대 주문 횟수는 T(X), i-j간의 예상 추천 확률과 impression 대비 전환율(CVR)을 곱한 것의 합이다. 예상 CVR 역시 ML 모델을 통해 추정된 값이다. 그리고 예상 총 주문 금액 G(X)는 i-j간의 예상 추천 확률 X 예상 CVR X 예상 지불 금액을 곱한 것의 모든 합이다.

 

 

이 두 가지 지표를 Objective로 하여, 수식 1의 multi-objective optimization을 수행한다. 정확하게는 G(X)를 최적화 할 때 T(X)의 조건을 다는 개념으로, Lagrangian duality와 KKT 조건으로 이를 수행한다. 즉, G(X)를 f(x)로 하며 T(X)를 g(x)로 하는 라그랑지안 승수법을 이용하여 convex optimization을 하는 라그랑지안 duality, KKT 해결법이라는 것이다(자세한 내용은 링크를 참고하자). 결국 위 수식의 내용과 설명을 종합적으로 요약하면, 매출이 최대화되는 랭킹 optimization 시스템을 만들 건데, 추천 확률과 CVR을 고려하여 실제 구매지표와 파라미터 알파 만큼만 차이가 나게끔 최적화 조건을 추가한 뒤 매출 최대화 모델을 보정한다는 것 같다. 이 과정을 그림으로 나타내면 아래와 같다. demand prediction은 ML 모델로 확률 점추정을 하는 단계이고, Multi-objective Trade-off는 최적화 모델로 ML 결과값을 보정하는 단계이다. 

 

 

좌우당간에 이러한 최적화 문제 해결법을 이용하여 목적을 최적화하는 matrix를 구한 뒤, matrix의 정보를 바탕으로 x_ij 를 정렬하여 유저별로 앱에 노출되는 레스토랑의 최종 순위를 산정한다. 이제 남은 것은 파라미터를 튜닝하는 작업인데, 전통적인 A/B 테스트로는 비효율적이기 때문에 위에서 언급한 MAB를 사용한다고 한다.