Đồng tác giả: Javen Xu , Hakan Baba và Adriana Deneault

giới thiệu

Các phương pháp học đồ thị có thể tiết lộ những hiểu biết thú vị giúp nắm bắt các cấu trúc quan hệ cơ bản. Phương pháp học đồ thị có nhiều ứng dụng công nghiệp trong các lĩnh vực như hệ thống đề xuất sản phẩm hoặc nội dung và phân tích mạng.

Trong bài đăng này, chúng tôi thảo luận về cách chúng tôi sử dụng các phương pháp học đồ thị tại Lyft để tạo nhúng — biểu diễn véc-tơ nhỏ gọn của thông tin nhiều chiều. Chúng tôi sẽ chia sẻ những hiểu biết thú vị về trình chiếu chung được phát hiện bằng cách nhúng người đi xe, trình điều khiển, địa điểm và thời gian. Như các ví dụ sẽ hiển thị, nhúng được đào tạo từ biểu đồ có thể biểu thị thông tin và mẫu khó nắm bắt bằng các tính năng đơn giản, truyền thống.

Dữ liệu và nhúng Lyft

Tại Lyft, chúng tôi có dữ liệu bán cấu trúc thu thập các tương tác phức tạp giữa tài xế, hành khách, địa điểm và thời gian. Chúng ta có thể xây dựng các biểu đồ biểu thị các tương tác này (ví dụ: có thể tạo biểu đồ bằng cách kết nối người lái với tất cả các địa điểm họ đã đến). Từ những biểu đồ này, chúng tôi có thể tạo các phần nhúng để thể hiện ngắn gọn toàn bộ lịch sử đi xe của người lái xe hoặc người lái xe. Những nhúng này cho phép chúng tôi tóm tắt hiệu quả thông tin rộng lớn và đa dạng trong một biểu diễn thân thiện với máy.

Ví dụ: có hơn 9.000 địa điểm cấp Geohash-6 (Gh6) xung quanh Khu vực Vịnh San Francisco. Nếu chúng tôi muốn mô tả lịch sử lái xe của người lái xe quanh Vùng Vịnh mà không cần nhúng, chúng tôi sẽ cần biểu đồ hoặc vectơ có độ dài hơn 9.000 để mô tả chính xác. Vectơ sẽ chứa số lượt đi mà người lái xe đã bắt đầu trong mỗi Gh6, với rất nhiều số 0 nếu người lái xe chưa từng tham gia một số Gh6.

Với việc học đồ thị, chúng tôi có thể đào tạo một vectơ nhúng có chiều thấp hơn biểu thị cùng một thông tin. Nó có thể không ghi lại các chi tiết chính xác do giảm kích thước vốn có, nhưng như chúng tôi sẽ trình bày trong Lyft Ride Insights bên dưới, các nhúng được đào tạo tốt có thể ghi lại bức tranh tổng thể về lịch sử hành trình của người lái xe.

Một lợi ích khác là các phép nhúng là các vectơ d chiều mô tả các điểm đơn lẻ trong không gian vectơ d chiều và các không gian đó có thể được chia sẻ bởi các thực thể được xác định khác nhau. Các thực thể là các điểm hoặc nút trong biểu đồ đầu vào mà chúng ta muốn được biểu diễn bằng cách nhúng các vectơ và được nhóm lại với nhau theo các loại thực thể. Chẳng hạn, chúng ta có thể xây dựng hai vectơ nhúng, một đại diện cho thực thể người lái xe và một đại diện cho thực thể vị trí từ cùng một biểu đồ, trong đó cạnh được kết nối trong biểu đồ có nghĩa là người lái xe này đã đến vị trí này. Với chức năng tương tự(được xác định trong phần thiết lập vấn đề), chúng ta có thể so sánh trực tiếp hai vectơ nhúng bằng cách tính điểm tương đồng giữa chúng. Trong biểu đồ này, điểm tương đồng sẽ mô tả tần suất người lái của chúng tôi đã đến địa điểm đã chọn này.

Mặc dù biểu đồ có thể kết hợp nhiều loại thực thể khác nhau (ví dụ: người lái, vị trí, tài xế) và các mối quan hệ (ví dụ: lấy, bỏ), nhưng biểu đồ đơn giản vẫn có thể cung cấp thông tin. Như các ví dụ của chúng tôi sẽ cho thấy, ngay cả khi chỉ có hai loại thực thể và một loại mối quan hệ, các nhúng dựa trên biểu đồ vẫn có thể cung cấp thông tin chuyên sâu có giá trị.

phương pháp luận

Tổng quan về Nhúng dựa trên đồ thị

Biểu đồ đa thực thể được xây dựng bằng cách vẽ các thực thể dưới dạng các nút và tạo các kết nối (tức là các cạnh) giữa các thực thể có mối quan hệ có thể hiểu được. Ý tưởng về nhúng dựa trên biểu đồ là mã hóa các nút sao cho độ tương tự trong không gian nhúng (ví dụ: tích vô hướng ) xấp xỉ độ gần trong biểu đồ. Hai thực thể có điểm tương đồng cao với các lần nhúng của chúng nếu chúng được kết nối trực tiếp trong biểu đồ gốc (tức là khoảng cách kết nối “1 độ”) hoặc có khoảng cách rất gần (tức là kết nối “2 độ”).

Có hai thành phần chính: 1) một bộ mã hóa ánh xạ từng nút tới một vectơ chiều thấp và 2) một hàm tương tự chỉ định cách các mối quan hệ trong không gian vectơ ánh xạ tới các mối quan hệ trong mạng ban đầu.

Chúng tôi có thể chỉ định kích thước của không gian nhúng (tức là đầu ra) trong quá trình đào tạo. Bằng cách chọn một chiều thích hợp, chúng tôi có thể nắm bắt được các mối quan hệ phức tạp giữa các thực thể từ biểu đồ đầu vào ban đầu trong một không gian vectơ chiều thấp hơn và nhỏ gọn hơn nhiều. Chúng ta thậm chí có thể thực hiện các phép tính khoảng cách với các tích vectơ trong không gian nhúng để có được thước đo định lượng về “sự tương đồng” hoặc “khoảng cách” giữa các thực thể khác nhau.

Tiếp theo, chúng tôi sẽ sử dụng biểu đồ đi xe Lyft đơn giản làm ví dụ để minh họa chi tiết về đào tạo nhúng.

Ride Graphs tại Đào tạo Lyft và Embeddings

Tại Lyft, chúng tôi quan tâm đến việc tìm hiểu về hành khách, tài xế và sở thích đi xe của họ liên quan đến các yếu tố như địa điểm và thời gian.

Lấy vị trí làm ví dụ, chúng ta có thể xây dựng một biểu đồ như Hình 2. Mỗi người lái xe, người lái xe và vị trí được biểu diễn dưới dạng một thực thể riêng biệt và các kết nối được vẽ khi người lái xe hoặc người lái xe đã bắt đầu chuyến đi từ một vị trí nhất định.

Thuật toán đào tạo của chúng tôi mở rộng từ gói BigGraph của Pytorch . Khi bắt đầu đào tạo, chúng tôi chỉ định kích thước d của vectơ nhúng mà chúng tôi muốn thu được và thuật toán gán các giá trị ngẫu nhiên cho các vectơ nhúng chiều d này làm tham số ban đầu. Theo nguyên tắc chung, chúng tôi chọn thứ nguyên nhúng đầu ra cao hơn nếu biểu đồ gốc phức tạp với số lượng lớn các thực thể và các cạnh được kết nối phức tạp. Thứ nguyên nhúng cao hơn sẽ thu được nhiều thông tin hơn từ biểu đồ.

Mục tiêu của đào tạo là học các vectơ nhúng d chiều cho mỗi thực thể (tức là nút) sao cho độ tương tự được tính toán giữa hai thực thể bất kỳ phản ánh mối quan hệ của chúng. Ví dụ: hai thực thể ở rất gần trong không gian sẽ có điểm tương đồng tích cực hơn so với hai thực thể ở xa.

Trong mỗi chu kỳ đào tạo, đối với mỗi thực thể, mọi cạnh được kết nối với thực thể trong biểu đồ đầu vào ban đầu được coi là một thể hiện dương (+), trong khi thuật toán lấy mẫu ngẫu nhiên từ các thực thể không được kết nối cho các thể hiện âm (-). Trong biểu đồ chuyến đi của chúng tôi, các mẫu sẽ giống như Hình 3 bên dưới. Lưu ý cách các cạnh được dán nhãn dương tồn tại trong Hình 2 ở trên, nhưng các cạnh được dán nhãn âm thì không.

Các vectơ nhúng cho các thực thể được so sánh theo từng cặp bằng cách sử dụng bộ so sánh đã chọn để tạo ra điểm tương đồng. Một lựa chọn đơn giản là độ tương tự cosin, được tính bằng tích vô hướng của hai vectơ.

Sau khi điểm số của tất cả các mẫu dương tính và âm tính đã được xác định, chỉ số tổn thất sẽ tổng hợp điểm số thành một giá trị tổn thất duy nhất trên mỗi kỷ nguyên để cho phép học hỏi. Hàm tổn thất phổ biến là tổn thất xếp hạng, tổn thất hậu cần và tổn thất softmax .

Cuối cùng, tổn thất được giảm thiểu bằng cách sử dụng phương pháp tối ưu hóa Adagrad để cập nhật tất cả các tham số mô hình.

Thông tin chi tiết về chuyến đi Lyft

Giờ đây, chúng tôi có thể hiển thị thông tin chi tiết thú vị mà tính năng nhúng biểu đồ đi xe đã tiết lộ. Tuyên bố từ chối trách nhiệm nhanh rằng phân tích của chúng tôi tập trung vào thông tin ẩn danh hoặc tổng hợp và chúng tôi không nhằm mục đích rút ra bất kỳ đặc điểm cá nhân hoặc thông tin chi tiết nào về người lái và trình điều khiển của chúng tôi từ các nhúng đã học.

So sánh mô hình đi xe của người lái xe

Ví dụ đầu tiên sẽ cho thấy cách nhúng có thể nắm bắt một cách gọn gàng thông tin phong phú về chiều cao. Như một bài tập thú vị, chúng tôi xây dựng một biểu đồ khám phá các kiểu vị trí khác nhau của những người lái xe xung quanh Vùng Vịnh.

Đầu vào là một biểu đồ với Trình điều khiển và Gh6 dưới dạng các thực thể và các cạnh kết nối trình điều khiển và Gh6 đón của chuyến đi cho mỗi chuyến đi được yêu cầu trong thời gian vài tháng (tức là giai đoạn đào tạo nhúng). Đầu ra là nhúng 32 chiều cho từng vị trí Gh6 và cho từng trình điều khiển.

Với các phần nhúng, chúng tôi đã tính toán mức độ tương tự giữa mọi cặp trình điều khiển và Gh6. Trong ví dụ này, sự giống nhau sẽ báo hiệu tần suất người lái xe đón các chuyến xe từ một địa điểm Gh6. Điểm tương đồng càng cao thì người lái xe đã chọn được càng nhiều chuyến đi từ vị trí đó.

Chúng tôi đã chọn hai trình điều khiển — trình điều khiển A và B, đồng thời tính toán điểm tương đồng của mọi Gh6 với chúng thông qua tích vô hướng của các phần nhúng của chúng. Hình 4 cho thấy sự tương đồng của mọi Gh6 với Trình điều khiển A và Trình điều khiển B, tương ứng với điểm cao hơn có màu tối hơn.

Từ các biểu đồ tương tự, chúng ta có thể hình dung rõ ràng các kiểu đi xe khác nhau của các tài xế. Chúng tôi thấy rằng Trình điều khiển A (bảng điều khiển bên trái) là Trình điều khiển SF City . Đôi khi, họ lái xe xuống phía nam một chút để đi chơi ở khu vực Bán đảo hoặc đi lên phía bắc một chút để đi chơi ở khu vực Vịnh Bắc, nhưng họ hiếm khi đi đến khu vực Vịnh Đông hoặc Vịnh Nam.

Ngược lại, Người lái xe B (bảng bên phải) chủ yếu là Người lái xe ở East Bay , người đã chọn nhiều chuyến đi hơn ở khu vực Fremont, nơi tập trung nhiều bóng tối nhất. Đôi khi họ lái xe đến khu vực Bán đảo của South Bay qua các cây cầu, nhưng hiếm khi đến khu vực thành phố San Francisco.

Những kiểu đi xe thú vị này có thể yêu cầu một biểu đồ lớn về tần suất đi xe đối với các vị trí cần mô tả. Với các phần nhúng, chúng tôi có thể có được bức tranh phong phú về kiểu đi xe của người lái xe chỉ bằng một vectơ 32 chiều!

Mô hình đi xe trong suốt tuần

Trong ví dụ tiếp theo, chúng tôi sẽ chỉ ra cách sử dụng các tính năng nhúng theo thời gian có thể giúp khám phá các mối quan hệ và thông tin chi tiết ẩn có thể không rõ ràng với các tính năng thời gian đơn giản như giờ trong ngày hoặc giờ trong tuần.

Chúng tôi đã xây dựng một biểu đồ với Tài xế và giờ trong tuần dưới dạng các thực thể và các cạnh kết nối tài xế và một giờ trong tuần cho mỗi chuyến xe mà tài xế đón bắt đầu trong giờ đó. Đầu ra là một nhúng bốn chiều đơn giản cho mỗi giờ trong tuần và cho mỗi trình điều khiển. Chúng tôi chỉ sử dụng các vectơ nhúng bốn chiều vì chỉ có 168 thực thể mỗi tuần so với hàng nghìn Gh6 trong ví dụ trước. Với biểu đồ này, chúng ta có thể so sánh sự giống nhau giữa mỗi giờ trong tuần với mọi giờ khác trong tuần và quan sát các kiểu đi xe trong tuần.

Chúng tôi đã chọn hai giờ tham khảo — 8 giờ tối thứ Bảy và trưa thứ Hai theo giờ địa phương ở tất cả các vùng ở Hoa Kỳ và tính điểm tương đồng của mỗi giờ trong tuần với chúng. Hai giờ tham chiếu này được chọn vì chúng đại diện cho các kiểu đi xe rất đặc biệt.

Trên đồ thị bên trái của Hình 5, phần nhô ra một chút trước “x = Su” cho thấy 8 giờ tối Thứ Bảy có điểm tương đồng cao nhất với chính nó, điều được mong đợi. Điều thú vị là những giờ tương tự nhất tiếp theo với 8 giờ tối Thứ Bảy dường như là 8 giờ tối Thứ Sáu, sau đó là 8 giờ tối Chủ Nhật. Tương tự nhất tiếp theo là từ Thứ Hai đến Thứ Năm lúc 8 giờ tối, mặc dù chúng có mức độ tương đồng thấp hơn rõ rệt so với 8 giờ tối vào Thứ Sáu.

Khi thứ Hai lúc 12 giờ trưa là thời gian tham chiếu, một bức tranh khác sẽ xuất hiện. Biểu đồ bên phải của Hình 5, giống nhất với từ Thứ Hai đến Thứ Sáu vào buổi trưa và ít giống hơn với Thứ Bảy hoặc Chủ Nhật vào buổi trưa.

Điều đó có nghĩa là gì? Dựa trên cách chúng tôi xây dựng biểu đồ bao gồm trình điều khiển và giờ trong tuần dưới dạng các thực thể, tương tự trong trường hợp đó có thể được hiểu hơi khác một chút. Một cách giải thích có thể là những người lái xe giống với một giờ trong tuần hơn đã thực hiện nhiều chuyến xe hơn vào thời điểm đó.

Với sự tương phản đơn giản của hai biểu đồ này, chúng ta gần như có thể chọn ra các nhóm lái xe và đi xe riêng biệt trên nền tảng Lyft — những lái xe và chuyến đi “vào giờ tiệc tùng” cuối tuần so với những lái xe và chuyến đi “vào giờ đi làm” vào các ngày trong tuần. Tất cả thông tin này được thể hiện trong các vectơ 4 chiều cho mỗi giờ trong tuần có thể dễ dàng cung cấp làm đầu vào cho một mô hình. Thông qua các nhúng, chúng tôi có thể nắm bắt và truyền tải một cách tinh tế mối quan hệ ẩn giấu này mà chúng tôi sẽ bỏ lỡ nếu chúng tôi chỉ sử dụng giờ trong tuần làm tính năng!

Cái gì tiếp theo

Sau khi chứng kiến ​​một số ứng dụng nhúng thành công, chúng tôi đang xây dựng một nền tảng để hỗ trợ nhiều nhà lập mô hình máy học (ML) tại Lyft sử dụng chúng. Cách tiếp cận để xây dựng biểu đồ dữ liệu và xây dựng phần nhúng rất linh hoạt và có thể được áp dụng để nghiên cứu những điểm phức tạp khác nhau của hoạt động kinh doanh dịch vụ chia sẻ xe Lyft. Thông tin chi tiết được khám phá có thể giúp chúng tôi hiểu các kiểu đi xe khác nhau, động lực thị trường và cuối cùng là xây dựng các sản phẩm tốt hơn cũng như các dịch vụ đi xe cho hành khách và tài xế của chúng tôi.

Trong phạm vi của sáng kiến ​​Nền tảng nhúng, nhiều dự án lập mô hình riêng biệt được hỗ trợ để xây dựng các phần nhúng tùy chỉnh và sử dụng chúng làm tính năng đổi mới trong các mô hình ML. Chúng tôi đồng thời giải quyết các vấn đề về chất lượng dữ liệu và tính năng, đào tạo lại tự động, quản trị, tuân thủ và cơ sở hạ tầng phục vụ đào tạo cho các nhóm được hỗ trợ của chúng tôi.

Chúng tôi dự định duy trì các nhúng mới cho các thực thể thú vị nhất trên thị trường Lyft và cung cấp chúng dưới dạng các tính năng dễ truy cập cho nhiều trường hợp sử dụng phổ biến.

[1] Hình từ slide bài giảng khóa học Stanford CS224W .