diff options
| -rw-r--r-- | .gitignore | 7 | ||||
| -rw-r--r-- | Makefile | 23 | ||||
| -rw-r--r-- | doc/biblio.bib | 36 | ||||
| -rw-r--r-- | doc/report.tm | 352 |
4 files changed, 417 insertions, 1 deletions
@@ -1,5 +1,9 @@ .idea/* +# Source archive +submission.tgz +*.pdf + # Byte-compiled / optimized / DLL files __pycache__/ *.py[cod] @@ -58,8 +62,9 @@ docs/_build/ # PyBuilder target/ -# Vim tmpfiles +# Vim & other tmpfiles *.swp +*~ # Random datafiles *.csv diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..2dc587f --- /dev/null +++ b/Makefile @@ -0,0 +1,23 @@ +FILES=config/__init__.py \ + config/dest_mlp_tgtcls_1_cswdtx_alexandre.py \ + data/cuts/__init__.py \ + data/cuts/test_times_0.py \ + data/__init__.py \ + data/csv_to_hdf5.py \ + data/hdf5.py \ + data/init_valid.py \ + data/make_valid_cut.py \ + data/transformers.py \ + model/__init__.py \ + model/mlp.py \ + model/dest_mlp_tgtcls.py \ + data_analysis/cluster_arrival.py \ + doc/report.pdf \ + __init__.py \ + error.py \ + ext_saveload.py \ + ext_test.py \ + train.py + +submission.tgz: $(FILES) + tar czf $@ $(FILES) diff --git a/doc/biblio.bib b/doc/biblio.bib new file mode 100644 index 0000000..d6b7a8c --- /dev/null +++ b/doc/biblio.bib @@ -0,0 +1,36 @@ + +@article{bengio2003neural, + title={A neural probabilistic language model}, + author={Bengio, Yoshua and Ducharme, R{\'e}jean and Vincent, Pascal and Janvin, Christian}, + journal={The Journal of Machine Learning Research}, + volume={3}, + pages={1137--1155}, + year={2003}, + publisher={JMLR. org} +} + +@inproceedings{bergstra2010theano, + title={Theano: a CPU and GPU math expression compiler}, + author={Bergstra, James and Breuleux, Olivier and Bastien, Fr{\'e}d{\'e}ric and Lamblin, Pascal and Pascanu, Razvan and Desjardins, Guillaume and Turian, Joseph and Warde-Farley, David and Bengio, Yoshua}, + booktitle={Proceedings of the Python for scientific computing conference (SciPy)}, + volume={4}, + pages={3}, + year={2010}, + organization={Austin, TX} +} + +@article{bastien2012theano, + title={Theano: new features and speed improvements}, + author={Bastien, Fr{\'e}d{\'e}ric and Lamblin, Pascal and Pascanu, Razvan and Bergstra, James and Goodfellow, Ian and Bergeron, Arnaud and Bouchard, Nicolas and Warde-Farley, David and Bengio, Yoshua}, + journal={arXiv preprint arXiv:1211.5590}, + year={2012} +} + +@inproceedings{glorot2011deep, + title={Deep sparse rectifier neural networks}, + author={Glorot, Xavier and Bordes, Antoine and Bengio, Yoshua}, + booktitle={International Conference on Artificial Intelligence and Statistics}, + pages={315--323}, + year={2011} +} + diff --git a/doc/report.tm b/doc/report.tm new file mode 100644 index 0000000..6165cd1 --- /dev/null +++ b/doc/report.tm @@ -0,0 +1,352 @@ +<TeXmacs|1.99.2> + +<style|generic> + +<\body> + <doc-data|<doc-title|Taxi Destination Prediction Challenge<next-line>Winner + Team's Report>|<doc-author|<author-data|<\author-affiliation> + <em|Montréal, July 2015> + </author-affiliation>>>> + + <center|<tabular*|<tformat|<table|<row|<cell|<name|Alex + Auvolat>>|<cell|<name|Alexandre De Brébisson>>|<cell|<name|Étienne + Simon>>>|<row|<cell|ENS Paris>|<cell|Université de Montréal>|<cell|ENS + Cachan>>|<row|<cell|France>|<cell|Québec, + Canada>|<cell|France>>|<row|<cell|<verbatim|alexis211@gmail.com>>|<cell|<verbatim|<strong|adbrebs@gmail.com>>>|<cell|<verbatim|esimon@esimon.eu>>>>>>> + + <section|Summary> + + Our model is based on a multi-layer perceptron (MLP), a simple feed-forward + neural network architecture. Our MLP model is trained by stochastic + gradient descent (SGD) on the training trajectories. The inputs to our MLP + are the 5 first and 5 last positions of the known part of the trajectory, + as well as embeddings for the context information (date, client and taxi + identification). \ The embeddings are trained with SGD jointly with the MLP + parameters. The MLP outputs probabilities for 3392 target points, and a + mean is calculated to get a unique destination point as an output. We did + no ensembling and used no external data. + + <section|Feature Selection/Extraction> + + We used a mean-shift algorithm on the destination points of all the + training trajectories to extract 3392 classes for the destination point. + These classes were used as a fixed output layer for the MLP architecture. + + We used the embedding method which is common in neural language modeling + approaches (see [1]) to take the metainformation into account in our model. + The following embeddings were used (listed with corresponding + dimensionnality): + + <big-table|<tabular|<tformat|<table|<row|<cell|<tabular|<tformat|<cwith|1|1|1|-1|cell-bborder|1px>|<table|<row|<cell|<strong|Meta-data>>|<cell|<strong|Embedding + Dimension>>|<cell|<strong|Number of classes>>>|<row|<cell|Unique caller + number>|<cell|10>|<cell|57125>>|<row|<cell|Unique stand + number>|<cell|10>|<cell|64>>|<row|<cell|Unique taxi + number>|<cell|10>|<cell|448>>|<row|<cell|Week of + year>|<cell|10>|<cell|54>>|<row|<cell|Day of + week>|<cell|10>|<cell|7>>|<row|<cell|1/4 of hour of the + day>|<cell|10>|<cell|96>>|<row|<cell|Day type (invalid + data)>|<cell|10>|<cell|3>>>>>>>>>>|Embeddings and corresponding dimensions + used by the model> + + The embeddings were first initialized to random variables and were then let + to evolve freely with SGD along with the other model parameters. + + The geographical data input in the network is a centered and normalized + version of the GPS data points. + + We did no other preprocessing or feature selection. + + <section|Modelling Techniques and Training> + + Here is a brief description of the model we used: + + <\itemize> + <item><strong|Input.> The input layer of the MLP is the concatenation of + the following inputs: + + <\itemize> + <item>Five first and five last points of the known part of the + trajectory. + + <item>Embeddings for all the metadata. + </itemize> + + <item><strong|Hidden layer.> We use a single hidden layer MLP. The hidden + layer is of size 500, and the activation function is a Rectifier Linear + Unit (ie <math|f<around*|(|x|)>=max<around*|(|0,x|)>>). See [2] for more + information about ReLUs. + + <item><strong|Output layer.> The output layer predicts a probability + vector for the 3392 output classes that we obtained with our clustering + preprocessing step. If <math|\<b-p\>> is the probability vector output by + our MLP (output by a softmax layer) and <math|c<rsub|i>> is the centroid + of cluster <math|i>, our prediciton is given by: + + <\eqnarray*> + <tformat|<table|<row|<cell|<wide|y|^>>|<cell|=>|<cell|<big|sum><rsub|i>p<rsub|i>*c<rsub|i>>>>> + </eqnarray*> + + Since <math|\<b-p\>> sums to one, this is a valid point on the map. + + <item><strong|Cost.> We directly train using an approximation of the mean + Haversine Distance as a cost. + + <item><strong|SGD and optimization.> We used a minibatch size of 200. The + optimization algorithm is simple SGD with a learning rate of 0.01 and a + momentum of 0.9. + + <item><strong|Validation.> To generate our validation set, we tried to + create a set that looked like the training set. For that we generated + ``cuts'' from the training set, i.e. extracted all the taxi rides that + were occuring at given times. The times we selected for our validation + set are similar to those of the test set, only one year before. + </itemize> + + <section|Code Description> + + Here is a brief description of the Python files in the archive: + + <\itemize> + <item><verbatim|config/*.py> : configuration files for the different + models we have experimented with + + The model which gets the best solution is + <verbatim|mlp_tgtcls_1_cswdtx_alexandre.py> + + <item><verbatim|data/*.py> : files related to the data pipeline: + + <\itemize> + <item><verbatim|__init__.py> contains some general statistics about the + data + + <item><verbatim|csv_to_hdf5.py> : convert the CSV data file into an + HDF5 file usable directly by Fuel + + <item><verbatim|hdf5.py> : utility functions for exploiting the HDF5 + file + + <item><verbatim|init_valid.py> : initializes the HDF5 file for the + validation set + + <item><verbatim|make_valid_cut.py> : generate a validation set using a + list of time cuts. Cut lists are stored in Python files in + <verbatim|data/cuts/> (we used a single cut file) + + <item><verbatim|transformers.py> : Fuel pipeline for transforming the + training dataset into structures usable by our model + </itemize> + + <item><strong|<verbatim|data_analysis/*.py>> : scripts for various + statistical analyses on the dataset + + <\itemize> + <item><verbatim|cluster_arrival.py> : the script used to generate the + mean-shift clustering of the destination points, producing the 3392 + target points + </itemize> + + <item><verbatim|model/*.py> : source code for the various models we tried + + <\itemize> + <item><verbatim|__init__.py> contains code common to all the models, + including the code for embedding the metadata + + <item><verbatim|mlp.py> contains code common to all MLP models + + <item><verbatim|dest_mlp_tgtcls.py> containts code for our MLP + destination prediction model using target points for the output layer + </itemize> + + <item><verbatim|error.py> contains the functions for calculating the + error based on the Haversine Distance + + <item><verbatim|ext_saveload.py> contains a Blocks extension for saving + and reloading the model parameters so that training can be interrupted + + <item><verbatim|ext_test.py> contains a Blocks extension that runs the + model on the test set and produces an output CSV submission file + + <item><verbatim|train.py> contains the main code for the training and + testing + </itemize> + + In the archive we have included only the files listed above, which are + strictly necessary for reproducing our results. More files for the other + models we have tried are available on GitHub at + <hlink|https://github.com/adbrebs/taxi|><hlink||https://github.com/adbrebs/taxi>. + + <section|Dependencies> + + We used the following packages developped at the MILA lab: + + <\itemize> + <item><strong|Thano.> A general GPU-accelerated python math library, with + an interface similar to numpy (see [3, 4]). + <hlink|http://deeplearning.net/software/theano/|> + + <item><strong|Blocks.> A deep-learning and neural network framework for + Python based on Theano. <hlink|https://github.com/mila-udem/blocks|> + + <item><strong|Fuel.> A data pipelining framework for Blocks. + <hlink|https://github.com/mila-udem/fuel|> + </itemize> + + We also used the <verbatim|scikit-learn> Python library for their + mean-shift clustering algorithm. <verbatim|numpy>, <verbatim|cPickle> and + <verbatim|h5py> are also used at various places. + + <section|How To Generate The Solution> + + <\enumerate> + <item>Set the <verbatim|TAXI_PATH> environment variable to the path of + the folder containing the CSV files. + + <item>Run <verbatim|data/csv_to_hdf5.py> to generate the HDF5 file (which + is generated in <verbatim|TAXI_PATH>, along the CSV files). This takes + around 20 minutes on our machines. + + <item>Run <verbatim|data/init_valid.py> to initialize the validation set + HDF5 file. + + <item>Run <verbatim|data/make_valid_cut.py test_times_0> to generate the + validation set. This can take a few minutes. + + <item>Run <verbatim|data_analysis/cluster_arrival.py> to generate the + arrival point clustering. This can take a few minutes. + + <item>Create a folder <verbatim|model_data> and a folder + <verbatim|output> (next to the training script), which will recieve + respectively a regular save of the model parameters and many submission + files generated from the model at a regular interval. + + <item>Run <verbatim|./train.py dest_mlp_tgtcls_1_cswdtx_alexandre> to + train the model. Output solutions are generated in <verbatim|output/> + every 1000 iterations. Interrupt the model with three consecutive Ctrl+C + at any times. The training script is set to stop training after 10 000 + 000 iterations, but a result file produced after less than 2 000 000 + iterations is already the winning solution. The training is quite long + though: we trained our model on a GeForce GTX 680 card and it took about + an afternoon to generate the winning solution. + + When running the training script, set the following Theano flags + environment variable to exploit GPU parallelism: + + <verbatim|THEANO_FLAGS=floatX=float32,device=gpu,optimizer=FAST_RUN> + + Theano is only compatible with CUDA, which requires an Nvidia GPUs. + Training on the CPU is also possible but much slower. + </enumerate> + + <section|Additional Comments and Observations> + + The training examples fed to the model are not full trajectories, since + that would make no sense, but prefixes of those trajectories that are + generated on-the-fly by a Fuel transformer, <verbatim|TaxiGenerateSplits>, + whose code is available in <verbatim|data/transformers.py>. The data + pipeline is as follows: + + <\itemize> + <item>Select a random full trajectory from the dataset + + <item>Generate a maximum of 100 prefixes for that trajectory. If the + trajectory is smaller than 100 data points, generate all possible + prefixes. Otherwise, chose a random subset of prefixes. Keep the final + destination somewhere as it is used as a target for the training. + + <item>Take only the 5 first and 5 last points of the trajectory. + + <item>At this points we have a stream of prefixes sucessively taken from + different trajectories. We create batches of size 200 with the items of + the previous stream, taken in the order in which they come. The prefixes + generated from a single trajectory may end up in two sucessive batches, + or all in a single batch. + </itemize> + + <section|References> + + <\enumerate> + <item><label|gs_cit0>Bengio, Y., Ducharme, R., Vincent, P., & Janvin, C. + (2003). A neural probabilistic language model. + <with|font-shape|italic|The Journal of Machine Learning Research>, + <with|font-shape|italic|3>, 1137-1155. + + <item><label|gs_cit0>Glorot, X., Bordes, A., & Bengio, Y. (2011). Deep + sparse rectifier neural networks. In <with|font-shape|italic|International + Conference on Artificial Intelligence and Statistics> (pp. 315-323). + + <item><label|gs_cit0>Bergstra, J., Bastien, F., Breuleux, O., Lamblin, + P., Pascanu, R., Delalleau, O., ... & Bengio, Y. (2011). Theano: Deep + learning on gpus with python. In <with|font-shape|italic|NIPS 2011, + BigLearning Workshop, Granada, Spain>. + + <item><label|gs_cit0>Bastien, F., Lamblin, P., Pascanu, R., Bergstra, J., + Goodfellow, I., Bergeron, A., ... & Bengio, Y. (2012). Theano: new + features and speed improvements. <with|font-shape|italic|arXiv preprint + arXiv:1211.5590>. + </enumerate> +</body> + +<\initial> + <\collection> + <associate|page-medium|paper> + <associate|page-screen-margin|true> + </collection> +</initial> + +<\references> + <\collection> + <associate|auto-1|<tuple|1|1>> + <associate|auto-10|<tuple|8|?>> + <associate|auto-2|<tuple|2|1>> + <associate|auto-3|<tuple|1|1>> + <associate|auto-4|<tuple|3|2>> + <associate|auto-5|<tuple|4|2>> + <associate|auto-6|<tuple|5|3>> + <associate|auto-7|<tuple|6|3>> + <associate|auto-8|<tuple|7|4>> + <associate|auto-9|<tuple|8|4>> + <associate|gs_cit0|<tuple|4|4>> + </collection> +</references> + +<\auxiliary> + <\collection> + <\associate|table> + <tuple|normal|Embeddings and corresponding dimensions used by the + model|<pageref|auto-3>> + </associate> + <\associate|toc> + <vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|1<space|2spc>Summary> + <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-1><vspace|0.5fn> + + <vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|2<space|2spc>Feature + Selection/Extraction> <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-2><vspace|0.5fn> + + <vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|3<space|2spc>Modelling + Techniques and Training> <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-4><vspace|0.5fn> + + <vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|4<space|2spc>Code + Description> <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-5><vspace|0.5fn> + + <vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|5<space|2spc>Dependencies> + <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-6><vspace|0.5fn> + + <vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|6<space|2spc>How + To Generate The Solution> <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-7><vspace|0.5fn> + + <vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|7<space|2spc>Additional + Comments and Observations> <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-8><vspace|0.5fn> + + <vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|8<space|2spc>References> + <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-9><vspace|0.5fn> + </associate> + </collection> +</auxiliary>
\ No newline at end of file |