공동 저자: Javen Xu , Hakan Baba 및 Adriana Deneault

소개

그래프 학습 방법은 기본 관계 구조를 캡처하는 흥미로운 통찰력을 나타낼 수 있습니다. 그래프 학습 방법은 제품 또는 콘텐츠 추천 시스템 및 네트워크 분석과 같은 분야에서 많은 산업 응용 분야를 가지고 있습니다.

이 게시물에서는 Lyft에서 그래프 학습 방법을 사용하여 임베딩(고차원 정보의 압축 벡터 표현)을 생성하는 방법에 대해 설명합니다. 탑승자, 운전자, 위치 및 시간을 임베딩하여 발견한 흥미로운 승차 공유 통찰력을 공유할 것입니다. 예제에서 볼 수 있듯이 그래프의 훈련된 임베딩은 기존의 간단한 기능으로 캡처하기 어려운 정보와 패턴을 나타낼 수 있습니다.

Lyft 데이터 및 임베딩

Lyft에는 운전자, 탑승자, 위치 및 시간 간의 복잡한 상호 작용을 캡처하는 반구조화된 데이터가 있습니다. 우리는 이러한 상호 작용을 나타내는 그래프를 구성할 수 있습니다(예: 라이더와 그들이 방문한 모든 위치를 연결하여 그래프를 형성할 수 있음). 이러한 그래프에서 임베딩을 생성하여 탑승자 또는 운전자의 전체 승차 이력을 간결하게 표현할 수 있습니다. 이러한 임베딩을 통해 방대하고 다양한 정보를 기계 친화적인 표현으로 효율적으로 요약할 수 있습니다.

예를 들어 샌프란시스코 베이 지역 주변에는 9,000개 이상의 Geohash-6 (Gh6) 수준 위치가 있습니다 . 임베딩 없이 Bay Area 주변의 운전자 승차 이력을 설명하려면 정확하게 설명하기 위해 길이가 9,000이 넘는 히스토그램 또는 벡터가 필요합니다. 벡터에는 운전자가 각 Gh6에서 시작한 승차 횟수가 포함되며 운전자가 일부 Gh6에 가본 적이 없는 경우 많은 0이 포함됩니다.

그래프 학습을 통해 동일한 정보를 나타내는 저차원 임베딩 벡터를 훈련할 수 있습니다. 고유한 차원 감소로 인해 정확한 세부 정보를 캡처하지 못할 수도 있지만 아래의 Lyft Ride Insights에서 볼 수 있듯이 잘 훈련된 임베딩은 드라이버의 여행 기록에 대한 전반적인 그림을 캡처할 수 있습니다.

또 다른 이점은 임베딩이 d 차원 벡터 공간의 단일 지점을 설명하는 d 차원 벡터이며 이러한 공간은 정의된 다른 엔터티에서 공유할 수 있다는 것입니다. 엔터티는 임베딩 벡터로 표현하려는 입력 그래프의 포인트 또는 노드이며 엔터티 유형별로 그룹화됩니다. 예를 들어 동일한 그래프에서 하나는 탑승자 엔터티를 나타내고 다른 하나는 동일한 그래프의 위치 엔터티를 나타내는 두 개의 임베딩 벡터를 구성할 수 있습니다. 여기서 그래프의 연결된 가장자리는 이 탑승자가 이 위치를 방문했음을 의미합니다. 유사도 기능 으로(문제 설정에서 정의됨) 두 임베딩 벡터 사이의 유사성 점수를 계산하여 직접 비교할 수 있습니다. 이 그래프에서 유사성 점수는 라이더가 선택한 위치를 얼마나 자주 방문했는지 설명합니다.

그래프는 다양한 엔터티 유형(예: 탑승자, 위치, 운전자)과 관계(예: 탑승, 하차)를 통합할 수 있지만 간단한 그래프도 여전히 유용할 수 있습니다. 우리의 예에서 볼 수 있듯이 두 개의 엔터티 유형과 한 가지 유형의 관계만 있어도 그래프 기반 임베딩은 여전히 ​​귀중한 통찰력을 제공할 수 있습니다.

방법론

간단히 말해서 그래프 기반 임베딩

다중 엔터티 그래프는 엔터티를 노드로 그리고 해석 가능한 관계가 있는 엔터티 간에 연결(예: 에지)을 만들어 구성됩니다. 그래프 기반 임베딩의 아이디어는 임베딩 공간의 유사성(예: 내적 )이 그래프의 근접성을 근사하도록 노드를 인코딩하는 것입니다. 두 엔터티는 원본 그래프에서 직접 연결되거나(예: "1도" 연결 거리) 거리가 매우 가까운 경우(예: "2도" 연결) 임베딩과의 유사성 점수가 높습니다.

1) 각 노드를 저차원 벡터에 매핑하는 인코더 와 2) 벡터 공간의 관계가 원래 네트워크의 관계에 매핑되는 방법을 지정하는 유사성 함수 의 두 가지 주요 구성 요소가 있습니다 .

학습 과정에서 임베딩(예: 출력) 공간의 크기를 지정할 수 있습니다. 적절한 차원을 선택함으로써 원본 입력 그래프의 엔터티 간의 복잡한 관계를 훨씬 더 작고 컴팩트한 차원 벡터 공간에서 캡처할 수 있습니다. 임베딩 공간에서 벡터 내적을 사용하여 거리 계산을 수행하여 서로 다른 엔터티 간의 "유사성" 또는 "거리"를 정량적으로 측정할 수도 있습니다.

다음으로 임베딩 교육의 세부 사항을 설명하기 위해 간단한 Lyft 승차 그래프를 예로 사용합니다.

Lyft 및 Embeddings 교육에서 그래프 타기

Lyft는 탑승자, 드라이버, 위치 및 시간과 같은 요소에 대한 탑승 선호도에 대해 알아보는 데 관심이 있습니다.

위치를 예로 들면 그림 2와 같은 그래프를 구성할 수 있습니다. 각 라이더, 드라이버 및 위치는 별도의 엔터티로 표시되며 라이더 또는 드라이버가 특정 위치에서 승차를 시작한 위치에 연결이 그려집니다.

우리의 훈련 알고리즘은 Pytorch BigGraph 패키지에서 확장됩니다. 학습 시작 시 획득하려는 임베딩 벡터의 d 차원을 지정하고 알고리즘은 이러한 d 차원 임베딩 벡터에 임의의 값을 초기 매개변수로 할당합니다. 일반적으로 원본 그래프가 많은 수의 엔터티와 복잡하게 연결된 에지로 복잡한 경우 더 높은 출력 임베딩 차원을 선택합니다. 임베딩 차원이 높을수록 그래프에서 더 많은 정보를 캡처합니다.

교육의 목표는 각 엔터티(예: 노드)에 대한 d 차원 임베딩 벡터를 학습하여 임의의 두 엔터티 간에 계산된 유사성이 해당 관계를 반영하도록 하는 것입니다. 예를 들어 공간에서 매우 가까운 두 엔터티는 멀리 떨어진 두 엔터티보다 더 긍정적인 유사성 점수를 갖습니다.

각 교육 주기 동안 각 엔터티에 대해 원래 입력 그래프의 엔터티에 연결된 모든 에지는 양수(+) 인스턴스로 간주되는 반면, 알고리즘은 음수(-) 인스턴스에 대해 연결되지 않은 엔터티에서 무작위로 샘플링합니다. 승차 그래프에서 샘플은 아래 그림 3과 같습니다. 위의 그림 2에는 양수 레이블이 지정된 가장자리가 있지만 음수 레이블이 지정된 가장자리는 없습니다.

엔티티에 대한 임베딩 벡터는 선택된 비교기를 사용하여 쌍으로 비교되어 유사성 점수를 생성합니다. 간단한 선택은 두 벡터의 내적으로 계산되는 코사인 유사성입니다.

모든 긍정 및 부정 샘플의 점수가 결정되면 손실 메트릭은 학습을 가능하게 하기 위해 점수를 에포크당 단일 손실 값으로 집계합니다. 일반적인 손실 함수는 순위 손실, 로지스틱 손실 및 소프트맥스 손실 입니다 .

마지막으로 모든 모델 매개변수를 업데이트하는 Adagrad 최적화 방법 을 사용하여 손실을 최소화합니다 .

Lyft 라이드 인사이트

이제 라이드 그래프 임베딩이 밝혀낸 흥미로운 인사이트를 보여줄 수 있습니다. 우리의 분석은 익명 또는 집계된 정보에 초점을 맞추고 학습된 임베딩에서 라이더 및 드라이버에 대한 개인적인 특성이나 통찰력을 도출하는 것을 목표로 하지 않는다는 빠른 면책 조항입니다.

운전자 승차 패턴 비교

첫 번째 예는 임베딩이 풍부한 고차원 정보를 컴팩트하게 캡처하는 방법을 보여줍니다. 재미있는 연습으로 Bay Area 주변의 다양한 운전자 위치 패턴을 탐색하는 그래프를 구성합니다.

입력은 운전자와 Gh6을 엔터티로 사용하는 그래프이며, 몇 달 동안(예: 임베딩 교육 기간) 요청된 각 승차에 대해 운전자와 승차 픽업 Gh6을 연결하는 에지입니다. 출력은 각 Gh6 위치 및 각 드라이버에 대한 32차원 임베딩입니다.

임베딩을 통해 모든 드라이버 쌍과 Gh6 사이의 유사성을 계산했습니다. 이 예에서 유사성은 운전자가 Gh6 위치에서 차량을 픽업한 빈도를 나타냅니다. 유사성 점수가 높을수록 드라이버 파트너가 해당 위치에서 픽업한 승차 횟수가 더 많습니다.

우리는 두 개의 드라이버(드라이버 A와 B)를 선택하고 임베딩의 내적을 통해 모든 Gh6의 유사성 점수를 계산했습니다. 그림 4는 각각 드라이버 A 및 드라이버 B에 대한 모든 Gh6의 유사성을 보여줍니다. 점수가 높을수록 음영이 짙어집니다.

유사성 플롯에서 운전자의 뚜렷한 승차 패턴을 명확하게 시각화할 수 있습니다. 드라이버 A(왼쪽 패널)가 SF City 드라이버 임을 알 수 있습니다 . 그들은 때때로 반도 지역에서 타기 위해 약간 남쪽으로 운전하거나 노스 베이 지역에서 타기 위해 약간 북쪽으로 운전하지만 이스트 베이 또는 사우스 베이 지역으로 가는 경우는 거의 없습니다.

대조적으로 드라이버 B(오른쪽 패널)는 주로 가장 어두운 음영이 집중되는 프리몬트 지역에서 더 많은 라이드를 픽업한 이스트 베이 드라이버 입니다. 그들은 때때로 다리를 통해 사우스 베이의 페닌슐라 지역으로 운전하지만 샌프란시스코 시내 지역으로는 거의 가지 않습니다.

이러한 흥미로운 승차 패턴은 설명할 위치에 대한 승차 빈도의 큰 히스토그램이 필요할 수 있습니다. 임베딩을 사용하면 32차원 벡터만으로 운전자의 승차 패턴에 대한 매우 풍부한 그림을 얻을 수 있습니다!

일주일 내내 라이딩 패턴

다음 예에서는 시간 임베딩 기능을 사용하여 하루 중 시간이나 주중 시간과 같은 단순한 시간 기능으로는 명확하지 않을 수 있는 숨겨진 관계와 통찰력을 발견하는 데 어떻게 도움이 되는지 보여줍니다.

우리는 운전자와 주중 시간을 엔터티로 사용하여 그래프를 구성하고 운전자와 해당 시간 동안 시작하여 운전자가 픽업하는 각 승차에 대한 주중 시간을 연결하는 에지를 구성했습니다. 출력은 각 요일 및 각 운전자에 대한 간단한 4차원 임베딩이었습니다. 이전 예제의 수천 개의 Gh6에 비해 168시간의 엔터티만 있기 때문에 4차원 임베딩 벡터만 사용했습니다. 이 그래프를 사용하여 주중 매 시간과 격주 시간 간의 유사성을 비교하고 일주일 내내 주행 패턴을 관찰할 수 있습니다.

우리는 미국의 모든 지역에서 현지 시간으로 토요일 오후 8시와 월요일 정오에 2개의 기준 시간을 선택하고 이들과 매 주 시간의 유사성 점수를 계산했습니다. 이 두 기준 시간은 매우 독특한 주행 패턴을 나타내기 때문에 선택되었습니다.

그림 5의 왼쪽 플롯에서 "x = Su" 조금 앞의 혹은 토요일 오후 8시가 자신과의 유사성 점수가 가장 높다는 것을 보여줍니다. 이는 예상되는 것입니다. 흥미로운 점은 토요일 오후 8시와 그 다음으로 가장 비슷한 시간이 금요일 오후 8시에 이어 일요일 오후 8시로 나타난다는 것입니다. 그 다음으로 가장 유사한 시간은 월요일부터 목요일까지 오후 8시이지만 금요일 오후 8시보다 유사성 수준이 현저히 낮습니다.

월요일 오후 12시가 기준 시간이면 다른 그림이 나타납니다. 그림 5의 오른쪽 플롯은 정오에 월요일부터 금요일까지 가장 유사하고 토요일이나 일요일 정오에 덜 유사합니다.

이것은 무엇을 의미 하는가? 동인과 요일을 엔터티로 포함하는 그래프 구성에 따라 유사한 경우 약간 다르게 해석될 수 있습니다. 주당 1시간에 더 가까운 운전자가 그 시간에 더 많은 라이드를 제공했다는 해석이 가능합니다 .

이 두 플롯의 단순한 대조를 통해 우리는 Lyft 플랫폼에서 독특한 드라이버 및 승차 그룹을 거의 골라낼 수 있습니다. 주말 "파티 시간" 드라이버 및 승차 대 주중 "통근 시간" 운전자 및 승차. 이 정보는 모두 모델에 쉽게 입력할 수 있는 각 주 시간에 대한 4차원 벡터로 표현됩니다. 임베딩을 통해 우리는 기능으로 시간만 사용했다면 놓쳤을 이 숨겨진 관계를 우아하게 캡처하고 전달할 수 있습니다!

무엇 향후 계획

몇 가지 성공적인 임베딩 애플리케이션을 본 후 Lyft의 많은 기계 학습(ML) 모델러가 이를 활용할 수 있도록 플랫폼을 구축하고 있습니다. 데이터 그래프를 구성하고 임베딩을 구축하는 접근 방식은 매우 유연하며 Lyft 차량 공유 비즈니스의 다양한 복잡성을 연구하는 데 적용할 수 있습니다. 발견된 통찰력은 다양한 승차 패턴, 시장 역학을 이해하고 궁극적으로 승객과 운전자를 위한 더 나은 제품과 승차 서비스를 구축하는 데 도움이 될 수 있습니다.

임베딩 플랫폼 이니셔티브의 범위에서 맞춤형 임베딩을 구축하고 이를 ML 모델의 혁신적인 기능으로 사용하기 위해 많은 개별 모델링 프로젝트가 지원됩니다. 우리는 데이터 및 기능 품질, 자동화된 재교육, 거버넌스, 규정 준수 및 지원되는 팀을 위한 교육 서비스 인프라 문제를 동시에 해결하고 있습니다.

우리는 Lyft 마켓플레이스에서 가장 흥미로운 엔터티에 대한 새로운 임베딩을 유지하고 많은 일반적인 사용 사례에서 쉽게 액세스할 수 있는 기능으로 사용할 수 있도록 할 계획입니다.

[1] Stanford CS224W 과정 강의 슬라이드의 그림.