KDD 2018: Didi, ETA tahmin doğruluğunu önemli ölçüde iyileştirmek için WDR modeli önerdi
Uluslararası veri madenciliği alanındaki en büyük konferans olan KDD 2018, Londra'da gerçekleştirildi.Bu yıl KDD,% 20'nin altında kabul oranıyla 293 bildiri dahil olmak üzere dünyanın dört bir yanından toplam 1.480 bildiri başvurusunu çekti. Bunlar arasında, KDD 2018 için ETA tahmini (Tahmini Varış Süresi), akıllı gönderim ve büyük ölçekli trafik yönetimi gibi birden çok araştırma alanını kapsayan dört Didi makalesi seçildi.
Dört bildiri sırasıyla (makalenin indirme adresi makalenin sonuna eklenmiştir)
-
Çok Temsilcili Derin Güçlendirme Öğrenimi ile Verimli Büyük Ölçekli Filo Yönetimi
Kaixiang Lin (Michigan Eyalet Üniversitesi); Renyu Zhao (AI Labs, Didi Chuxing); Zhe Xu (AI Labs, Didi Chuxing); Jiayu Zhou (Michigan Eyalet Üniversitesi)
-
Seyahat Süresi Tahmini için Çok Görevli Temsil Öğrenimi
Yaguang Li (Güney Kaliforniya Üniversitesi); Kun Fu (DiDi AI Labs); Zheng Wang (DiDi AI Labs); Cyrus Shahabi (Güney Kaliforniya Üniversitesi); Jieping Ye (DiDi AI Labs); Yan Liu (Güney Kaliforniya Üniversitesi)
-
Talep Üzerine Araç Paylaşımı Platformlarında Büyük Ölçekli Sipariş Gönderimi: Bir Öğrenme ve Planlama Yaklaşımı
Zhe Xu (AI Labs, Didi Chuxing); Zhixin Li (AI Labs, Didi Chuxing); Qingwen Guan (AI Labs, Didi Chuxing); Dingshui Zhang (AI Labs, Didi Chuxing); Qiang Li (AI Labs, Didi Chuxing); Junxiao Nan (AI Labs, Didi Chuxing); Chunyang Liu (AI Labs, Didi Chuxing); Wei Bian (AI Labs, Didi Chuxing); Jieping Ye (AI Labs, Didi Chuxing)
-
Seyahat Süresini Tahmin Etmeyi Öğrenmek
Zheng Wang (Didi Chuxing); Kun Fu (Didi Chuxing); Jieping Ye (Didi Chuxing)
Bu makale, Didi KDD 2018 Poster bildirisinin ayrıntılı bir yorumudur "Seyahat Süresini Tahmin Etmeyi Öğrenmek" Bu makalede, Didi teknik ekibi, tahmini varış zamanını (ETA) tahmin etmek için derin bir sinir ağı kullanan bir şema tasarladı. ETA'yı bir uzay-zamansal regresyon problemi olarak modelleyerek, zengin ve etkili bir özellik sistemi inşa edilir ve verilen hareket zamanı ve rotası altında daha doğru tahmin yapabilen Geniş-derin-tekrarlayan (WDR) modeli ayrıca önerilmektedir. Bu olay, Leifeng.com akademik kanalının AI Technology Review altındaki "AI Impact Factor" veritabanı projesinde karşılık gelen bir bonusa sahiptir.
Kural modelinden eksiksiz makine öğrenimi çözümüne
ETA, akıllı ulaşım ve konuma dayalı hizmette (LBS) çok önemli, karmaşık ve zorlu bir konudur. Sadece trafik ışıklarının sayısı, yolun hız sınırı ve uzun bir otobana çıkmanın mümkün olup olmadığı gibi trafik sisteminin mekansal özelliklerini dikkate almakla kalmaz; aynı zamanda sabah ve akşam zirvelerindeki düzenli sıkışıklık ve trafik kazaları gibi trafik sisteminin zaman özelliklerini de dikkate alması gerekir. Ara sıra tıkanıklık vb. Aynı zamanda, ulaşım sisteminin işleyişi, ana gövde olarak insan ve araçların katılımını gerektirdiğinden ve dış faktörlerin etkisi kaçınılmaz olduğundan, zaman tahmini problemi, sürücü sürüş alışkanlıkları, yağmurlu ve sisli günler gibi kişiselleştirilmiş ve harici özelliklerin modellenmesini de ortaya koymalıdır. Sürüş hızına müdahale, vb.
Didi platformunda, ETA temel bir hizmettir. Yolculuktan önceki tahmini karşılama süresi, tahmini fiyat ekranı veya sevkıyat, zamanlama, araba paylaşımı veya yolculukta tahmini varış zamanının hesaplanması gibi sistem kararları olsun, yüksek hassasiyetli ETA'nın yardımından ayrılamaz. Didi'nin her gün yaklaşık 70 milyar ETA isteği var ve en yüksek noktasında saniyede yaklaşık 4 milyon ETA isteği işliyor.
ETA'yı hesaplamak için kural modelini kullanmak, harita endüstrisindeki yaygın uygulamalardan biridir. Yani, yolun her bölümünün seyahat süresini ayrı ayrı hesaplamak, bunları toplamak ve trafik ışığı süresine göre bir dengeleme düzeltmesi yapmaktır. Zamanı tanımlamak, tahmin etmek için matematiği kullanın
Olarak ifade edilebilir
onların arasında,
İ-inci yol segmentinin tahmini seyahat süresi ve
J-inci trafik ışığı için tahmini bekleme süresidir. Aşağıdaki şekil bu hesaplama yöntemini daha sezgisel olarak göstermektedir:
Bu, tamamen fiziksel yapıya göre oluşturulmuş bir modeldir ve en kritik kısım, her bir yol kesiminin zamanının ve her bir trafik ışığının zamanının elde edilmesidir. Yol bölümünün trafik durumunun her zaman dinamik olarak değiştiğini göz önünde bulundurarak, daha pratik bir yaklaşım, yol bölümünün gerçek zamanlı trafik süresini tahmin etmek için en son geçmiş verileri (örneğin, son 5 dakika) kullanmak ve aşağıdaki gibi geçmiş ortalama trafik süresini almaktır. Varsayılan değer, yol bölümlerini eksik bilgilerle doldurmak için kullanılır (son zamanlarda bir yol bölümü Didi araçları tarafından geçmediyse, trafik durumu şu anda bilinmemektedir). Trafik ışıkları da benzer bir yaklaşımı kullanarak her trafik ışığının geçmiş ortalama bekleme süresini aşağıdaki gibi verilerden çıkarabilir:
.
Çevrimiçi hizmet az miktarda hesaplamaya ve uygulaması kolay olmasına rağmen, kural modeli deneyime ve sezgiye dayalı çok sayıda yapay kural kullanır.Sadece bilimsel keşif yöntemlerinden yoksun olmakla kalmaz; birçok sınırlaması ve zayıf genişlemesi vardır ve kişiselleştirilmiş özellikler gibi birçok önemli bilgiyi gözden kaçırmak kolaydır. Ek olarak, basit istatistikler karmaşık trafik modellerini analiz etmek için yeterli değildir Çekirdek göstergeler genellikle darboğazlara karşı savunmasızdır ve yeni kurallar eklenerek optimize edilemez.
Didi, devasa seyahat verilerinin potansiyelini daha iyi anlamak için 2015 yılında ETA sorunlarını çözmek için eksiksiz bir makine öğrenimi sistemleri seti oluşturdu. Tip açısından, ETA çok tipik bir regresyon problemidir: girdi özellikleri göz önüne alındığında, model tahmin edilen seyahat süresini temsil eden gerçek bir değer çıkarır. Didi, harita alanında uzamsal bilgiler, zaman bilgileri, trafik bilgileri, kişiselleştirilmiş bilgiler ve genişletilmiş bilgiler dahil olmak üzere sistematik bir dizi özellik ve ifade keşfetti ve oluşturdu. Başlangıç noktası ile bitiş noktasını birbirine bağlayan tüm yolları tam olarak değerlendirebilir. İlgili yol bölümleri, kavşaklar ve trafik ışıklarının yanı sıra geçilen bölgenin POI'si, güzergahın karşılık gelen zaman özellikleri, gerçek zamanlı yol koşulları, sürücünün sürüş davranışı, hava durumu, trafik kontrolü vb.
Didi, kullanıcıların hatalara duyarlılığının daha çok göreceli değerlerle ilişkili olduğunu düşünürse, hedef işlev olarak MAPE'yi (ortalama mutlak yüzde hatası) seçer. MAPE'ye karşılık gelen optimizasyon sorunu:
onların arasında,
Gerçek varış zamanı (ATA) ve
Tahmini zamandır
Regresyon modelini temsil eder. Aşırı oturmayı önlemek için normal öğeler de ekleyebilirsiniz
Regresyon modeline gelince, Didi sektördeki iki popüler modeli, Ağaç Tabanlı model ve Faktorizasyon Makinesi olarak değerlendirdi. Bunların arasında, ağaç modelinin nihai çıktısı, aşağıdaki gibi yazılabilen birden çok ağacın entegrasyon sonucudur:
Modeldeki ağaç sayısıdır. Her ağaç giriş özelliklerine göre değerlendirilecek, giriş verilerinin ait olduğu yaprak düğümü belirleyecek ve ardından yaprak düğüme karşılık gelen puanı tek bir ağacın çıktısı olarak kullanacaktır.
T-inci ağacının tüm yaprak düğümlerinden oluşan puan vektörünü temsil eder,
Belirleyen bir eşleme işlevidir (bir dizi koşulla değerlendirilir)
Ait olması gereken yaprak düğümün sıra numarası. Model için karmaşıklığı ağacın yapısı ve ölçeği tarafından kontrol edilir, yani aşağıdaki düzenli terimler kullanılır.
Sezgisel olarak, ilk terim yaprak düğümlerin sayısıdır
Kontrollü ve ikinci terim, yaprak düğümün çıktı skorunu kontrol etmek için L2 normunu kullanır. ETA görevinin ağaç modeliyle amaç işlevi nihayet şu şekilde yazılabilir:
FM modelinin ana fikri, özellik etkileşiminin ağırlık matrisini ayrıştırmak ve parametre sayısını azaltmak için vektör iç çarpımı şeklinde ifade etmektir. İkinci dereceden FM'nin hesaplanması
Bunların arasında d, genellikle on milyonlarca veya daha yüksek olan karakteristik boyuttur. Ve parametre vektörü
M boyutu nispeten küçüktür ve iyi bir tahmin doğruluğu genellikle onlar düzeyinde elde edilebilir. FM ayrıca ETA'da regresyon modellemesi gerçekleştirebilir, bazı düzenli terimler ekleyebilir ve optimizasyon hedefini alabilir
onların arasında
V vektörünün oluşturduğu matrisin Frobenius normunu temsil eder.
Geniş-Derin-Tekrarlayan model doğruluğu daha da artırır
Bu eksiksiz makine öğrenimi çözümü, Didi için önemli bir ETA doğruluğu iyileştirmesi getirmiş olsa da, çünkü XGBoost gibi çoğu regresyon modeli, alınabilen giriş vektörü sabit uzunlukta olmalı ve bir geziye karşılık gelen yol segmenti ( Bundan sonra bağlantı olarak anılacaktır) Sayı, geniş bir varyasyon aralığına sahiptir, bu nedenle gerçek kullanımda, bağlantı seviyesi özellikleri atılır ve bunun yerine genel istatistiksel değer kullanılır. Dolayısıyla, ayrıntılı bilgi düzeyinde, bu çözümün optimizasyon için hala yeri vardır.
Bilginin kayıpsızlığını en üst düzeye çıkarmak ve modelin bağlantı dizisi bilgilerini modelleme yeteneğini korumak için Didi, ETA'ya yenilikçi bir şekilde derin öğrenmeyi uygular. Bu ETA modelinin ana fikri küresel model + tekrarlayan modeldir. Küresel modelin rolü, önceki nesil modele benzer, güzergahın küresel bilgisini öğrenir; yinelenen model, bağlantı dizileri gibi yerel ayrıntıların öğrenilmesine odaklanır.
Didi, global model bölümünde, tüm modüllerin uçtan uca eğitilebilmesini sağlamak için son yıllarda öneri sistemleri alanında dikkatleri üzerine çeken Geniş ve Derin modeli ele alıyor. Geniş şubesi aslında ikinci dereceden özelliklerin geçişini gerçekleştiren ve geçmiş veriler için belirli bir hafıza işlevine sahip olan FM'den kaynaklanmaktadır. Ve Derin dalı, iyi genelleme kabiliyetine sahip geleneksel çok katmanlı algılayıcı yapısıdır. İki kol, birbirlerinin güçlü yönlerinden öğrenmek için güçlerini birleştirir.
WD modelinin genel yapısı aşağıdaki şekilde gösterilmektedir:
Tekrarlayan model seçimi daha fazladır, sadece RNN ile sınırlı değildir (GRU, LSTM, SRU, vb. Çeşitleri dahil), aynı zamanda tek boyutlu bir evrişim CNN veya saf bir Dikkat modeli de olabilir. En popüler LSTM'yi örnek olarak alın, ek bellek ve geçit ekleyerek basit RNN'lerin kaybolan gradyan problemini hafifletir:
WD modeli ile birleştirildikten sonra, Geniş-Derin-Tekrarlayan model (WDR) elde edilir. Yapı aşağıdaki şekilde gösterilmektedir:
Gördüğünüz gibi, bu modelin üç tür özelliği vardır:
-
Yoğun özellik: başlangıç ve bitiş küresel mesafe, başlangıç ve bitiş noktalarının GPS koordinatları vb. Gibi seyahat planı seviyesinin gerçek sayı özellikleri.
-
Seyrek özellik: Seyahat planı seviyesinin zaman dilim numarası, haftanın günü, hava durumu türü gibi ayrık özellikleri.
-
Sıralı özellik: bağlantı seviyesi özellikleri, gerçek sayı özellikleri doğrudan modele girilir ve ayrık özellikler önce gömülür ve sonra modele girilir. Burada artık her yolculuk için bir özellik vektörü olmadığını, ancak gezideki her bağlantının bir özellik vektörü olduğunu unutmayın. Örneğin, bağlantı uzunluğu, şerit sayısı, işlev seviyesi, gerçek zamanlı trafik hızı vb.
Bunlar arasında, Geniş ve Derin modülleri gezinin genel bilgilerini modellerken, Tekrarlayan modülü, her bağlantı ve her bir kesişme noktasının bilgilerini yakalayabilen gezinin yörüngesinin ayrıntılı modellemesini gerçekleştirir. Nihai özette, Wide modülü, çıktıyı uygun boyuta değiştirmek için afin dönüşümü kullanır.Deep modülü, çıktı olarak doğrudan üst düzey gizli durumu kullanır ve Tekrarlayan modülü, çıktı olarak LSTM'nin son gizli durumunu kullanır. Üç modülün çıkış vektörleri birbirine eklenir ve ETA değerini elde etmek için tahmin için son Regresöre girer. Tüm parametreler, gradyan inişli MAPE kaybına göre eğitilir.
Sistem mimarisi aşağıdaki şekilde gösterilmektedir. Alt katman, harita bilgileri, GPS izleri, sipariş kayıtları ve diğer gerekli ek bilgiler olan veri kaynağıdır. Daha sonra, orijinal veriler belirli bir işleme tabi tutulur ve modelin eğitimi için model tarafından kullanılabilen bir format haline gelir. Burada küçük bir dal olduğunu unutmayın; bu, eğitim tamamlandıktan sonra, küçük bir güncel veri kümesinin finetune için çıkarıldığı ve modeli en son toplanan verilere daha eğimli hale getirdiği anlamına gelir. Çevrimdışı eğitimli model, nihayet harici hizmetler için çevrimiçi sisteme aktarılır.
Çevrimdışı deneylerde Didi, 2017'nin ilk beş ayında Beijing Didi platformundaki verileri uygun şekilde filtreledi ve bunun bir pikap (sürücü yolcuları almaya gitti) veya bir yolculuk (sürücü varış noktasına yolcu gönderdi) olup olmadığına karar verdi, WDR modelinin Önemli gelişme.
Didi ayrıca bir haftalık bir çevrimiçi değerlendirme gerçekleştirdi: Eğriden, modelinin gerçek çevrimiçi sistemde de lider performansa sahip olduğunu görüyoruz.
Didi ekibi, WDR modelinin daha doğru tahminler yapabilmesine rağmen, yol ağının topolojik yapısının nasıl tanıtılacağı, yol planlaması ile nasıl entegre edileceği ve yol durumu algoritmasının ETA ile nasıl birleştirileceği gibi daha fazla araştırılması gereken birçok konu olduğunu belirtti. Uçtan uca öğrenmeye başlayın, tek bir zaman yerine zaman aralığını nasıl tahmin edeceğiniz, çevrimiçi sistemin hizmet performansının nasıl iyileştirileceği vb. Derinlemesine araştırmaya ihtiyaç duyan konulardır.
(Tez adresi: Seyahat Süresini Tahmin Etmeyi Öğrenmek
