Source-linked AI summary
Artificial Neural Networks Applied to Taxi Destination Prediction
Alexandre de Brébisson, Étienne Simon, Alex Auvolat, Pascal Vincent, Yoshua Bengio
TL;DR
The paper addresses taxi destination prediction from a variable-length trajectory prefix and associated metadata. It presents an almost fully automated neural-network approach using MLPs, bidirectional recurrent networks, and memory-network-inspired models. The solution ranked first among 381 teams in the ECML/PKDD challenge, while the authors identify computational cost and incomplete training as limitations of some models.
Problem
The task is to predict a taxi’s destination from the beginning of its variable-length GPS trajectory and associated metadata such as time, taxi ID, and client information.
Method
The paper develops an almost fully automated neural-network approach spanning MLP, bidirectional recurrent, and memory-network-inspired architectures.
Results
The solution ranked first out of 381 teams in the ECML/PKDD taxi destination prediction challenge.
Takeaways & Limitations
The approach combines recurrent prefix encoding, metadata embeddings, and destination clusters, and the authors suggest it can extend to fixed-length prediction from variable-length sequences.
Takeaways & Limitations
The recurrent and memory-network models are computationally intensive, and the memory-network score may be understated because training stopped after one week without convergence.
Abstract
from arXiv · showhide
We describe our first-place solution to the ECML/PKDD discovery challenge on taxi destination prediction. The task consisted in predicting the destination of a taxi based on the beginning of its trajectory, represented as a variable-length sequence of GPS points, and diverse associated meta-information, such as the departure time, the driver id and client information. Contrary to most published competitor approaches, we used an almost fully automated approach based on neural networks and we ranked first out of 381 teams. The architectures we tried use multi-layer perceptrons, bidirectional recurrent neural networks and models inspired from recently introduced memory networks. Our approach could easily be adapted to other applications in which the goal is to predict a fixed-length output from a variable-length sequence.
1 Introduction
The challenge required predicting taxi destinations from partial GPS trajectories and ride metadata. The authors addressed it with an almost fully automated neural-network approach and won the competition.
- The task predicts a taxi trip’s destination, represented by latitude and longitude, from an initial trajectory prefix and associated metadata.The metadata includes client or taxi-stand identification when available, taxi ID, and ride start time.
- The Porto dataset contains complete trajectories from 442 taxis over one year, with GPS positions measured every 15 seconds.Each ride has a variable-length sequence whose final position is the destination.
- The competition test set contains 320 partial trajectories split equally between public and private subsets for interim comparison and final ranking.The public set was used during the competition, while the private set determined the final leaderboard.
- The approach uses little hand-engineering and is almost fully automated, relying on artificial neural networks.The paper examines MLP, recurrent, and memory-network-inspired architectures and provides code and reproduction instructions online.
2 The Winning Approach
The winning approach converts variable-length taxi prefixes and metadata into a destination prediction using an MLP, learned embeddings, destination clusters, and a city-scale distance objective. It uses fixed endpoint samples for the prefix and a softmax-weighted combination of 3,392 cluster centers.
- MLP architecture: The MLP receives prefix and metadata representations, processes them through 500 ReLU hidden neurons, and predicts the taxi destination.MLPs use fully connected acyclic layers and fixed-size input vectors.
- Input representation: The winning MLP represents each prefix with its first and last k GPS points, using k = 5 and padding shorter prefixes by repeating endpoints.This produces a fixed-size input compatible with the MLP, while standardizing the GPS coordinates.
- Metadata encoding: The model learns embeddings jointly for client ID, taxi ID, and date-time metadata to represent discrete ride information.The embedding parameters are trained together with the rest of the neural network.
- Destination clustering and output: Instead of predicting coordinates directly, the output assigns values to predefined destination clusters and computes the prediction as their softmax-weighted centroid.The clusters were obtained by mean-shift clustering over training destinations, yielding C = 3392 centers.
- Cost and training: Because direct Haversine-distance training performed poorly, the models were trained with the equirectangular distance, which approximates Haversine distance at Porto’s city scale.The competition evaluation metric was mean Haversine distance.
3 Alternative Approaches
The paper evaluates recurrent, bidirectional recurrent, and memory-network-inspired architectures as alternatives for processing variable-length taxi trajectory prefixes. These models reduce the fixed-input constraint of the winning MLP, but the alternatives did not perform as well on this task.
- 3 Alternative Approaches: The alternative architectures performed worse than the simpler winning model on this destination task, though the authors considered them informative for other variable-length-input problems.The memory-network implementation randomly selected m = 10000 candidates because efficient retrieval was challenging.
- 3.1 Recurrent Neural Networks: RNNs read all GPS points sequentially while updating a fixed-length internal state intended to summarize the prefix.The recurrent transition uses the same matrix at each time step.
- 3.1 Recurrent Neural Networks: LSTM RNNs process prefixes from beginning to end, with a five-point sliding-window variant designed to capture short-term dependencies.The window shifts by one point at each recurrent step.
- 3.2 Bidirectional Recurrent Neural Networks: Bidirectional RNNs process each prefix both forwards and backwards, then concatenate the two final internal states to retain information from both ends.This design targets the observed importance of the prefix beginning and end.
- 3.3 Memory Networks: The memory-network-inspired model encodes a prefix and m candidate trajectories into a shared space, uses dot-product similarities, and weights candidate destinations with a softmax.The final prediction is the centroid of candidate destinations weighted by the normalized similarities.
4 Experimental Results
The authors compared models on larger custom validation and testing datasets because the competition test set was too small for reliable model comparison. Table 2 reports testing errors for the tuned model variants on both custom and competition datasets.
- 4.1 Custom Validation Set: 19427 trajectories formed the validation set and 19770 trajectories formed the testing set used for model comparison.The sets were created by extracting and removing random portions of the original training data.
- 4 Experimental Results: The winning Kaggle submission scored 2.03, although its model had not been trained until convergence.The passage also notes that submissions worse than the public benchmark were discarded when computing the competition average.
- 4 Experimental Results: Table 2 reports testing errors for the various tuned models on both the custom testing dataset and the competition datasets.The table distinguishes model inputs and recurrent time-step configurations, including prefix-only, metadata-only, and five-point BRNN variants.
5 Analysis of the results
The competition-winning MLP used destination clusters, while the BRNN with window was strongest on the larger custom test. Embeddings and clusters improved performance, but evaluation and training costs constrain interpretation.
- Model comparison: The competition-winning model was an MLP using destination clusters, whereas the BRNN with window was best on the larger custom test.The authors consider the custom-test scores more confident because that test set is considerably larger.
- Feature representations: Embeddings and destination clusters significantly improved the models.The authors also visualized embeddings with t-SNE and observed clear patterns for departure-time and week-of-year representations.
- Evaluation: The custom test set produced higher scores than the competition's public and private test sets.The authors suggest the competition set contained rides from specific dates and times with particular trajectory distributions.
- Computational cost: All explored models were computationally intensive, although the winning model was least intensive and trained in half a day on a GPU.The recurrent and memory networks were much slower, and the authors believed longer training could improve their scores.
Conclusion
The paper presents an almost fully automated neural-network approach for taxi destination prediction from trajectory prefixes and metadata. Its best model combines bidirectional recurrent encoding, metadata embeddings, and destination clusters, while the output layer and candidate retrieval retain limitations.
- Main approach: The best model combines a bidirectional recurrent network for the prefix, metadata embeddings, and destination clusters for output generation.This is the paper's overall best model according to the conclusion.
- Limitations: The clustering-based output layer restricts final predictions to the convex hull of the destination clusters.The authors suggest learning cluster locations as network parameters as a potential solution.
- Future improvements: The memory-network variant could use more sophisticated candidate retrieval and more complex functions for comparing prefix and candidate representations.The authors mention hand-engineered or learned similarity measures and nonlinear comparisons as possible alternatives.