Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
SIGSPATIAL2020 参加報告
Search
fumihiko takahashi
PRO
December 14, 2020
Research
3
660
SIGSPATIAL2020 参加報告
fumihiko takahashi
PRO
December 14, 2020
Tweet
Share
More Decks by fumihiko takahashi
See All by fumihiko takahashi
明日使えるかもしれないLoss Functionsのアイディアと実装
ftakahashi
PRO
12
1.7k
時系列予測にTransformerは有効か?
ftakahashi
PRO
1
34
ドライブレコーダーの映像で Scene Text Recognitionする
ftakahashi
PRO
0
1.1k
ドライブレコーダーの Scene Text Recognitionにおける Multi-task Learning
ftakahashi
PRO
1
3k
JapanTaxi R&Dの取り組み事例
ftakahashi
PRO
0
62
jsai2019.pdf
ftakahashi
PRO
0
350
Attention機構を使った 配車車両未確定状態における タクシー到着時間予測
ftakahashi
PRO
1
47
Other Decks in Research
See All in Research
SSII2024 [OS2] 大規模言語モデルとVision & Languageのこれから
ssii
PRO
5
1.1k
クロスモーダル表現学習の研究動向: 音声関連を中心として
ryomasumura
3
750
言語間転移学習で大規模言語モデルを賢くする
ikuyamada
8
4.5k
SSII2024 [TS2] 深層学習に潜むバイアス
ssii
PRO
0
420
LLMとの共同執筆は文章の多様性を減らすか?
kuri8ive
3
610
MLtraq: Track your AI experiments at hyperspeed
micheda
1
150
[輪講資料] Text Embeddings by Weakly-Supervised Contrastive Pre-training
hpprc
3
630
待機電力を削減したネットワーク更新型電子ペーパーサイネージの開発と評価 / IOT64
yumulab
0
180
生成AIエージェントの現状を俯瞰する
isidaitc
0
1.8k
この先生きのこるには
verypluming
3
4.2k
大規模言語モデルを用いた その場での要約に基づく レビュー探索インタフェース
yamamotolab
0
170
僕たちがグラフニューラルネットワークを学ぶ理由
joisino
25
9.7k
Featured
See All Featured
How to Ace a Technical Interview
jacobian
273
22k
Designing for humans not robots
tammielis
247
25k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
128
32k
The Cult of Friendly URLs
andyhume
74
5.8k
Debugging Ruby Performance
tmm1
70
11k
Put a Button on it: Removing Barriers to Going Fast.
kastner
58
3.2k
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
10
3.7k
The Brand Is Dead. Long Live the Brand.
mthomps
51
36k
ParisWeb 2013: Learning to Love: Crash Course in Emotional UX Design
dotmariusz
104
6.7k
[RailsConf 2023] Rails as a piece of cake
palkan
31
4.2k
Fantastic passwords and where to find them - at NoRuKo
philnash
40
2.6k
Building a Scalable Design System with Sketch
lauravandoore
457
32k
Transcript
2020.12.10 齋藤 智輝 高橋 文彦 株式会社 Mobility Technologies SIG SPATIAL2020
参加レポート
• 名前:高橋文彦 • 略歴 ◦ 2015年4月 ヤフー株式会社 入社 ◦ 2018年8月
JapanTaxi株式会社 入社 ◦ 2020年4月 株式会社MobilityTechnologies • 領域 ◦ データサイエンス、自然言語処理 • 過去の主な仕事 ◦ ECサイトの検索精度改善 ◦ 形態素解析ツールの開発 ◦ MLを使った お迎え時間予測のロジック、APIの開発 ◦ SceneTextRecognitionの研究開発(画像処理) ◦ マネージャー(10人程度組織) ◦ 論文書いたり • 趣味 ◦ ボードゲーム、一蘭
3 04 論文紹介 Part 2 by 高橋
4 Grab-Posisi-L: A Labelled GPS Trajectory Dataset for Map Matching
in Southeast Asia Links: • Paper • Movie Xiaocheng Huang et al. GrabTaxi Holdings, National University of Singapore
5 ▪マップマッチの正解データセットを作成・公開 ▪いくつかのアプリケーションでの応用を紹介 Summary
6 ▪既存のデータセットの課題 ▪ 場所が限定的 ▪ 中国・アメリカが多い ▪ 街の一部のエリアのみを対象 ▪ 規模が小さい
▪ GPSのsampling rateが低い ▪ 付加情報(方向・GPS精度・速度など)がない Background
7 ▪GPSデータ ▪ Grabのドライバー端末 ▪ シンガポール、ジャカルタ ▪ 2019年4月 ▪ GPS精度,
進行方向, 速度 ▪ mode: 車, バイク ▪ 地図はOSMを使用 ▪統計 ▪ 84,000 軌跡 ▪ 1,003,510 km ▪ 30,104 時間 Dataset
8 1.GPSをHMMでマップマッチ 2.JOSMを使って可視化 3.マップマッチ結果を削除挿入変更で校正 Route Annotation
9 ▪本データセットを使ったいくつかの応用を紹介 1.地図推定 2.マップマッチのロジック改善 3.渋滞検知と予測 4.軌跡補完と次の目的地予測 5.GPSデータから移動手段(車 or バイク)を推定する 6.都市計画
Application
10 ▪背景 ▪ GPSの点のマッチ先の道路候補を、半径d以内の道路と決めている ▪ 半径dが小さすぎる場合精度が低下、大きすぎる場合計算量が膨大になるトレードオフ ▪改善案 ▪ GPSの点ごとに、GPS精度(accuracy level)を使って半径dを動的に変更
▪ 半径d = accuracy level * 2 Application – マップマッチのロジック改善
11 Spatio-Temporal Hierarchical Adaptive Dispatching for Ridesharing Systems Links: •
Paper • Movie Chang Liu et al. Shanghai Jiao Tong University, Didi Chuxing
12 ▪相乗りサービスにおいてプーリング間隔を調整して利益を最大化 ▪ 空間をクラスタリングし、クラスタ毎にオンラインで配車間隔を調整するアルゴリズムを提案 ▪実サービスのデータでシミュレーションし、利益が向上することを確認 Summary
13 ▪一般的な相乗りサービスでは、一定の間 隔で注文をプーリングして配車 ▪配車間隔が長いと、 ▪ より利益の高い組み合わせを作れるが ▪ 注文キャンセルが発生し損失 ▪注文数は空間的にも時間的にも不均一に 分布
▪時空間ごとに配車間隔を調整して利益を 最大化 Background
14 1.配車傾向ごとに空間をクラスタリング (Spatial Clustering) 2.クラスター毎に利益が最大化されるタイミングで配車 (Adaptive Interval) Hierarchical Adaptive Framework
15 ▪配車傾向ごとに空間をクラスタリング ▪方法 1. 過去の相乗り配車履歴から共有配車グラフを作成 2. エッジの重みの分散が閾値以下になるように、クラスタ内の重みの合計を最大化する Framework - Spatial
Clustering
16 ▪利益が最大化されるタイミングで配車 ▪ ただし、将来の利益はわからない ▪アルゴリズム ▪ 1/e-ADI algorithm ▪ 秘書問題として解く
▪ 閾値時間までは配車せず、前回配車からこれまでで利 益が最大になったタイミングで配車 ▪ BI-ADI algorithm ▪ 将来の利益を過去の統計データを利用 ▪ 利益が最大になるタイミングで配車 Framework - Adaptive Interval
17 Framework - Adaptive Interval - Algorithm
18 ▪いずれの設定でも提案手法の方が利益が高い Results unit time intervalごとの利益 最大配車間隔ごとの利益
19 Succinct Trit-array Trie for Scalable Trajectory Similarity Search Links:
• Paper • Movie Shunsuke Kanda et al. RIKEN AIP, Kyoto University, Nagoya University
20 ▪LSHとtrieを使って類似経路検索を高速化・省メモリ化 ▪既存手法に比べて12~34倍高速化、メモリを1/10~1/17 Summary
21 Highly Efficient and Scalable Multi-hop Ride-sharing Links: • Paper
• Movie Yixin Xu et al. The University of Melbourne
22 ▪乗り継ぎ方式の相乗りサービスの取り組み ▪ 実現するための2つのアルゴリズムを提案 ▪車両数が中程度あるときに配車失敗数を4割減らした Summary Vehicle-first algorithm Station-first algorithm