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
770
SIGSPATIAL2020 参加報告
fumihiko takahashi
PRO
December 14, 2020
Tweet
Share
More Decks by fumihiko takahashi
See All by fumihiko takahashi
単一の深層学習モデルによる不確実性の定量化の紹介 ~その予測結果正しいですか?~
ftakahashi
PRO
3
520
明日使えるかもしれないLoss Functionsのアイディアと実装
ftakahashi
PRO
16
3.6k
時系列予測にTransformerは有効か?
ftakahashi
PRO
2
210
ドライブレコーダーの映像で Scene Text Recognitionする
ftakahashi
PRO
0
1.2k
ドライブレコーダーの Scene Text Recognitionにおける Multi-task Learning
ftakahashi
PRO
1
3.2k
JapanTaxi R&Dの取り組み事例
ftakahashi
PRO
0
73
jsai2019.pdf
ftakahashi
PRO
0
390
Attention機構を使った 配車車両未確定状態における タクシー到着時間予測
ftakahashi
PRO
1
68
Other Decks in Research
See All in Research
Poster: Feasibility of Runtime-Neutral Wasm Instrumentation for Edge-Cloud Workload Handover
chikuwait
0
430
한국어 오픈소스 거대 언어 모델의 가능성: 새로운 시대의 언어 이해와 생성
inureyes
PRO
0
260
Remote Sensing Vision-Language Foundation Models without Annotations via Ground Remote Alignment
satai
3
180
公立高校入試等に対する受入保留アルゴリズム(DA)導入の提言
shunyanoda
0
300
大規模日本語VLM Asagi-VLMにおける合成データセットの構築とモデル実装
kuehara
5
1.7k
Zipf 白色化:タイプとトークンの区別がもたらす良質な埋め込み空間と損失関数
eumesy
PRO
8
1.5k
CoRL2024サーベイ
rpc
2
1.8k
チュートリアル:Mamba, Vision Mamba (Vim)
hf149
6
3.2k
The many faces of AI and the role of mathematics
gpeyre
1
1.7k
メタヒューリスティクスに基づく汎用線形整数計画ソルバーの開発
snowberryfield
3
820
情報処理学会関西支部2024年度定期講演会「自然言語処理と大規模言語モデルの基礎」
ksudoh
10
2.7k
[輪講] Transformer Layers as Painters
nk35jk
4
720
Featured
See All Featured
KATA
mclloyd
29
14k
Fontdeck: Realign not Redesign
paulrobertlloyd
83
5.4k
Become a Pro
speakerdeck
PRO
27
5.2k
Fantastic passwords and where to find them - at NoRuKo
philnash
51
3.1k
Facilitating Awesome Meetings
lara
53
6.3k
Build your cross-platform service in a week with App Engine
jlugia
229
18k
Building a Modern Day E-commerce SEO Strategy
aleyda
39
7.2k
Gamification - CAS2011
davidbonilla
81
5.2k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
102
18k
Building a Scalable Design System with Sketch
lauravandoore
462
33k
Producing Creativity
orderedlist
PRO
344
40k
The Cost Of JavaScript in 2023
addyosmani
48
7.6k
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