Uber 앱을 사용해보면 가고 싶은 목적지를 설정했을 때 예상도착시간 을 확인할 수 있습니다. 도착지까지 걸리는 시간을 앱을 통해서 보여주는 것은 모빌리티 서비스를 이용하는 소비자들에게 여러가지 좋은 경험을 제공할 수 있습니다.
공급자 입장에서도 여정 시간을 예측하는 것 (ETA: Estimating Travel Time) 은 매우 중요한데요. ETA 모델은 교통 상황 모니터링(traffic monitoring), 경로 설계(route planning), 배차(order dispatch) 등에 아주 중요하게 활용됩니다. 실제로 Uber 에서는 ETA 만을 전담하는 데이터 팀을 운영하고 있을 정도로 관련된 기술력을 매우 고도화하여 운영하고 있습니다.
오늘은 Deep Learning 을 활용해 ETA에서 높은 성능을 보인 논문을 한 편 리뷰해보려고 하는데요. 소개드릴 논문은 When Will You Arrive? Estimating Travel Time Based on Deep Neural Networks 입니다.
1. Introduction
유저가 특정 장소로 이동하는 경로를 탐색할 때 정확한 travel time estimation (이하 ETA) 을 제공하는 것은 더 나은 경로를 설정할 수 있고 혼잡한 여정을 피할 수 있도록 도와줍니다. GoogleMap, Uber, DiDi와 같은 대부분의 교통과 관련된 앱들은 TTE를 제공하는데요. ETA는 앱 상에서 사용자들의 경험을 증진시키기 위해서 아주 중요합니다. 하지만 높은 성능을 갖는 ETA 모델을 만들기 위해서는 몇 가지 도전 과제가 있습니다.
1. Individual vs Collective
ETA를 할 수 있는 방법은 크게 2가지로 나뉩니다. 각각의 방식은 trade-off 방식입니다.
- Individual: 전체 경로를 작은 단위로 나누어서 예측한 후 각각의 예측 결과를 합치는 방식입니다. 이 방식은 각각의 segment 에서는 높은 예측 결과를 갖지만 전체 경로에 존재하는 교차로, 신호등 등과 같은 복잡한 교통 상황을 반영할 수 없다는 단점이 있습니다. 또한 최종적으로 예측 결과를 합칠 때 각각의 segment 에서 존재했던 local error가 누적된다는 단점이 있습니다.
- Collective: 전체 경로에 대한 여정 시간을 한번에 예측하는 방식입니다. 이 방식은 전체적인 교통 상황을 한번에 포착할 수 있다는 장점이 있습니다. 하지만 예측하고자 하는 경로가 길어질 수록 예측 신뢰도가 낮아진다는 단점이 있습니다. 또한 전체 경로를 segment 단위로 대부분의 경로를 표현할 수 있는데 Collective 방식의 경우 실제 존재하지 않는 경로가 등장할 수도 있습니다.
2. 다양한 복합적인 요인들 (Diverse complex factors)
교통 상황은 공간적인 상관성이 존재하며 시간에 의존적입니다. 또한 외부요소에 큰 영향을 받습니다. 같은 경로 안에서 다양한 운전 패턴이 등장할 수 있습니다. 또한 동일한 경로여도 새벽 시간에 이동하는 것과 퇴근 시간에 이동하는 것은 큰 차이가 있습니다. 뿐만 아니라 날씨, 운전자의 습관에도 큰 영향을 받습니다.
ETA 모델을 만들기 위해서는 이와 같은 문제점들을 해결할 수 있어야 하는데요. 논문에서 제안한 DeepTTE는 ETA를 수행하는 2가지 방식의 장단점을 적절하게 조화시키면서 다양한 복합적인 요인을 고려한 End-to-End Framework 입니다.
2. Preliminary
모델 구조에 대해 설명하기 앞서서 논문에서 정의한 내용들을 먼저 짚고 넘어가려고 합니다.
2.1 Definition 1 (Historical Trajectory)
- Historical trajectory T: 주행 기록을 timestamp에 따른 (위도,경도) 로 표현했습니다. 또한 각각의 값에 대응되는 External factor (시작 시간, 주, 날씨, 드라이버ID) 도 함께 기록했습니다.
2.2 Definition 2 (Objective)
- Train: 경로 P와 External factor가 주어졌을 때 Definition 1에 따라서 이를 Historical trajetory T 형태로 표현했습니다. 이를 바탕으로 travel time을 예측할 수 있는 모델을 학습시켰습니다.
- Test: 우리의 목표는 경로 P를 통해 목적지까지 도착하는 시간을 예측하는 것 입니다. Test 단계에서 주어진 데이터를 Train 데이터와 같은 형태로 만들어주었습니다. 이 과정에서 경로 P에 대한 timestamp를 명시하지 않았는데요. 그 대신에 같은 거리 간격으로 trajetory를 표현했습니다.
3. Model Architecture
DeepTTE는 크게 3가지 요소 (attribute component, spatio-temporal learning component, multi-task learning component) 로 구분되어 있습니다. 전체적인 아키텍처는 아래의 그림에 표현되어 있습니다. 각각의 기능에 대해서 자세히 알아봅시다.
3.1 Attribute component
경로에 대한 여정시간을 예측하는 것은 시작 시간, 주, 날씨, 드라이버의 습관과 같은 External factors 에 영향을 받습니다. attribute component는 이와 같은 feature들을 통합하는 역할을 합니다. External factors 들 간의 유의미한 패턴을 학습하기 위해 각각의 입력 변수들을 라벨 인코딩해주었습니다.
- 드라이버ID (DriverID): 고유 드라이버 ID
- 날씨 (Weather): rainy, sunny, windy
- 주 (WeekID): 요일
- 시간 (Time): 1,440 timeslot (하루를 분으로 나눔)
이와 같은 Categorical 데이터들을 저차원으로 임베딩시켜주었습니다. 이를 통해 유사한 주행 패턴들을 비슷한 공간에 매핑시킬 수 있습니다. 그 이후 특정 경로의 시작 지점에서 끝 지점까지의 거리인 travel distance 와 Concat 시켜주었습니다. 이를 앞으로는 attr 이라고 부르겠습니다.
3.2 Spatio-Temporal Component
Spatio-Temporal component는 크게 2개로 구분됩니다.
3.2.1 Geo-Conv Layer
Definition 1 에 따르면 Historical Trajecory T 는 위도, 경도로 표현되는 GPS Point 를 의미합니다. 일반적으로 Spatio-Temporal Datamining 에서는 GPS Point 를 표현하기 위해 도시를 grid cell로 나누고 해당 cell 에 GPS Point 를 매핑시킵니다. 하지만 이 방식은 같은 cell 안에 있는 운전자의 행동을 모두 같은 취급을 한다는 단점이 있습니다.
DeepTTE 에서는 이와 같은 단점을 보완하고자 Geo-Conv Layer 라는 방식을 사용했습니다. GPS Point로 부터 공간적인 패턴을 포착하기 위해 Conv Layer 를 사용했는데요. 앞서 설명한 데이터 표현 방식보다 더 정교한 공간 패턴 학습을 위해 GPS Point 들을 channel 이 16개인 1D-CNN 을 학습시켰습니다.
그림의 왼쪽에서 local path 로 표현한 부분은 Convolution Layer 가 GPS Point 를 훑는 범위입니다. (실제 길을 생각하면 GPS trajetory 전체는 entire path 가 되겠네요.) 1D-CNN 을 통해 local path 의 공간적인 패턴을 학습할 수 있습니다. 하지만 ETA는 전체 GPS trajetory 의 거리와 밀접한 관계가 있습니다. 이를 반영하기 위해 그림의 오른쪽 부분의 Distant part 를 concat 시켰습니다. Distant part 란 local path 의 지도상의 거리를 의미합니다.
요약하면 1D-CNN 을 통해 local-path 의 feature map 을 추출한 후 local-path 간의 거리를 표현한 Distant part 를 concat 한 layer 가 Geo-Conv Layer 가 되겠습니다.
3.2.2 Recurrent Layer
앞선 과정을 통해 local-path의 공간적인 패턴을 학습할 수 있었습니다. Recurrent Layer 에서는 시간적인 패턴도 학습하려고 합니다. 이를 위해 Geo-Conv Layer 를 통해 얻어진 feature map과 Attribute component 를 통해 얻어진 attr 를 concat 한 값에 LSTM 을 적용했습니다.
그림이 살짝 모호한 감이 있는데 파란색 블록이 Geo-Conv Layer 를 통해 얻어진 feature map 이고 빨간색 블록이 attr 입니다. (attr에 distant part가 포함되어 있어서 Geo-Conv Layer에 distant part가 concat 되는 부분을 생략한 것 같습니다.)
3.3 Multi-task Learning Component
Multi-task Learning Component 는 이전의 Attribute component와 Spatio-Temporal Component를 결합하여 실제 입력된 경로의 여정 시간을 예측하는 단계입니다. 앞서 ETA를 수행하는 방식에는 Individual, Collective 2가지가 있으며 서로 trade-off 관계라고 소개한 적이 있습니다. 이 단계에서는 각각의 방식을 조화시킬 수 있는 방식을 소개하고 있습니다.
3.3.1 Estimate the local path
Individual 방식을 모방하기 위해 Spatio-Temporal Component에서 Geo-Conv Layer와 LSTM을 거친 결과 값에 2층의 Fully connected layers 를 적용했습니다. 이를 통해 local-path들의 ETA를 도출할 수 있습니다.
3.3.2 Estimate the entire path
이번에는 Collective 방식을 모방하여 entire-path 에 대한 ETA를 도출해보려고 합니다. 생각할 수 있는 간단한 방식은 앞서 Fully connected layers 를 통과하기 직전의 값을 활용하는 방식입니다. 앞서 Individual 방식의 단점은 local-error 가 누적된다는 것 이었습니다. 특정 local-path 의 교통 상황이 좋지 않을 때 발생하는 오차는 ETA 값에 큰 영향을 미칠 수 있습니다. 특정 local-path 에 발생하는 상황을 표현하기 위해 각각의 local-path 을 학습한 feature map 에 Attention 을 사용했습니다. 또한 attr 에도 Attention 을 적용한 후 두 값을 concat 해주었습니다. 마지막으로 Concat된 Attention 값들을 Residual fully-connected Blocks 에 통과시켰습니다. 이를 통해 entire-path 를 도출해 낼 수 있습니다.
4. Model Training
- Metrics: 짧은 경로에서의 10분의 오차와 긴 경로에서의 10분이라는 오차는 정말 큰 차이입니다. 이를 감안하기 위해 objective function에 relative error 인 MAPE를 사용했습니다.
- Evaluate: local-path에는 RMSE를 적용하고 entire-path에는 MAE 를 적용했습니다. 이 두 loss는 trade-off 관계이기 때문에 weighted combination 을 적용한 값을 모델의 성능으로 취급했습니다. train, test 에서 Estimate the local path, Estimate the entire path 는 다르게 동작합니다.
- train: 전체 모델을 할 때 local-path 값을 활용해야 하니 Estimate the local path 단계는 필수적입니다.
- test: 우리가 최종적으로 필요한 것은 전체 path에 대한 ETA 입니다. 때문에 test 단계에서는 Estimate the entire path 만 동작합니다.
5. Conclusion
정확한 ETA를 위해 DeepTTE 는 시공간적인 패턴을 동시에 학습했습니다. 또한 ETA에 영향을 줄 수 있는 다양한 외부 요소인 운전자의 습관, 날씨, 날짜 등을 함께 고려했습니다. 이를 통해 individual 방식과 collective 방식을 조화시킬 수 있는 End-to-End 모델을 구현할 수 있었습니다.
6. 느낀점
모델 아키텍처를 공부하면서 Deep Learning 에서 활용되는 다양한 기술들을 적절하고 논리적으로 사용했다는 느낌을 받았습니다. 특히 local-path의 공간정보를 학습하기 위해 Attention 을 활용한 점은 아이디어가 매우 대단한 것 같습니다. 또한 짧은 경로에서의 오차와 긴 경로에서의 오차는 큰 차이가 있다는 점을 고려하기 위해 MAPE를 사용한 점도 매우 인상적이었습니다. 역시 창의력은 알고있는 지식을 논리적으로 잘 연결할 수 있는 능력인 것 같습니다. 이런 논문을 쓰거나 관련된 기술들을 실무에 적용하기 위해서는 기본기를 더욱 충실하게 공부해야 겠습니다. 지금 까지 긴 글 읽어주셔서 감사합니다.
