TL;DR¶

We applied a probilistic machine learing approach to a dataset of hitchhiking waiting times around the world. In comparison to previous endeavors we are able to make waiting time predictions for any spot on the globe that results in a complete world map that is also more accurate than previous partial maps despite our chosen performance metric and experienced hitchhikers. In addition we are able to model uncertainties of waiting time predictions to not pretend that our predictions are accurate where there is no evidence and to call hitchhikers to share their experience especially in the regions where we lack data till this day.

To achieve this we applied a Gaussian process on data points in a 2D feature space (longitude, latitude) and quite noisy target values (waiting times). Specifically we made use of a kernel that involves three radial basis function kernels that each model a different scale on which waiting times in hitchhiking depend on each other. Besides that we built the model so that its predictions are inherently constrained to positive waiting times. Eventually we demonstrated how domain expertise can be used to tune the models hyperparameters.

The GP-kernel we applied would look as follows for 1-dimensional inputs:

$$k_{3\_RBFs}(x, x') = \sum_{i \in \{a, b, c\}}{\sigma_i}^2 \exp(- \frac{(x - x')^2}{2 l_i^2}) + \sigma_n \mathbb{I}(x = x')$$

The data challenges we had to face and migth be transferable to other GP problems:

• extremely noisy target values
• target values are not normally distributed and constrained to be greater than 0
• 2D feature-space
• varying density of data in the feature-space that prohibits the use of a simple RBF kernel

Our work resulted in a model that enabled us to draw the following map where a region becomes more grayed out if the model is more uncertain about how long a hitchhiker would wait in that region.

You can find the original notebook and helper code here.

Applying Gaussian process models to predict world-wide hitchhiking waiting times¶

What do we want to achieve?

A world map of estimated hitchhiking waiting times! For this purpose, we have to develop a predictive model that estimates the waiting time for hitchhiking at any location given the waiting times that were recorded on https://hitchmap.com/ since 2005 (most extensively from 2010 to 2016). For the following we are using the hitchwiki dump from 04/11/2024.

The map should be visually appealing. By that we mean that changes in the waiting time should not be too drastic and it should look organic in the way that there are no hard straight edges visible.

We are quantifying the quality of the map by the average deviation of the predicted waiting time from the actual waiting time. As the the problem at hand is a regression problem, this evaluation metric is referred to as mean absolute error (MAE). The rational behind this choice is that the MAE is easy to interpret and that we are dealing with extremely noisy data (ther is measurement noise for each data point especially for longer waiting times and there are outliers in the data caused by (bad) luck on the road) thus we want to avoid that the model gets punished too much by outliers as a root mean squared error (RMSE) would do. Still we are reporting the RMSE as well to give a more complete picture of the model performance.

Finally we want to build a model in which we can build in knowledge about hitchhiking in general but not about the the underlying world map. This importantly involves not building a sub-model for each region from a set of predefined regions as this process would be too manual, teadious and subjective.

Which assuptions do we make?

We assume that hitchhiking success in a certain spot depends mostly on the density of the traffic and the attitude of the drivers. In this work we focus a little more on the latter assuming that cultural differences mostly determine how quickly one is picked up on the road.

Throughout this notebook we are using a metric coordinate system which enables us to measure distances between spots in a convenient way.

Getting started with simple models¶

To get a feeling for the models we are viewing a 1D-example first. To achieve this we are only using data points with roughly the same latitude value. Specifically we are cutting horizontally through Germany at 51° latitude (roughly from Aachen to Görlitz), collecting all points that lie within a 10km strip around this cut and project them to 51° latitude.

Here we want to introduce the models that we will compare across all following experiments.

• As a minimal benchmark we use model that always predicts the average waiting time - calling it AVERAGE.
• Getting just a little more complex we are dividing the world into same-sized tiles and predict the average of all points in one tile for all locations that lie in that tile - calling it TILES.
• As proposed by the single existing hitchhiking heatmap that is around since 2019 we assume that each recorded waiting time gives us some certainty that it is the correct approximated waiting time in the region around it. The decrease in certainty or the area a single point influences is modelled by a bivariate normal distribution (2D Gaussian) with its mean at the point and a standard deviation of e.g. 50 km. To make a prediction at a new point the waiting times from all known points are weighted by the value of their Gaussian at the new point and then averaged by the total number of points - calling it WEIGHTED AVERAGED GAUSSIANS (not quite happy with the naming - open for suggestions). Although such a model can create quite visully appealing maps for small regions with a lot of data it has a few shortcomings when trying to apply it to a world map. In regions with few data hard edges between and circles around data points occur. Those effects are caused by the tailes of the Gaussian and the precision of numbers we can store and can be observed further below. We tried some approaches to mitigate those effects here (namely dynamically setting the size of the circle each data point influences and iteratively increasing the circel-size around each point to fill the parts of the map where no prediction was possible before) but could not yield satisfactory results.
• Eventually we apply a Gaussian process (GP) model that we will focus on and train in the following.

In the following we will compare the GP to the other models to develop a first understanding of it and make first improvements to the model.

With a first intuition for each of the models we want to take a look at some of the model choices in the Gaussian process.

The first thing to note is the transformation of the target values (waiting times). For GPs we can and have to specify our assumptions about the kinds of fuctions that can be leared from the data. These are called the prior. In general the prior assumes a 0-mean for the data and that the data points are normally distributed around this mean. It is obvious that waiting times have to be above 0 and are thus constrained which implies that the original data cannot be normally distributed.

To address this in our model we are applying a log-transformation to the waiting times and centering these transformed target values around 0. This removes the constraint on the waiting times as it maps positive real numbers to all real numbers. The log-transformation most importantly prevents the function that will be predicted by our GP model to drop below 0 which might otherwise occur especially when assuming that the waiting times can deviate a lot from the mean and there is lot of noise in the data.

We can take a look how the target values look like after being transformed.

Keep in mind the when feeding transformed targets into our GP model we will have to invert the transformation when making predictions.

The form of the function a GP can predict is most importantly determined by its kernel (or covariance) function which determines how strong waiting times are correlated depending on their relative distance to each other and thus how known waiting times influence predictions in a new spot. A common choice for a kernel is the radial basis function kernel (RBF) which in general results in smooth predicted functions.

The specific form of a RBF is determined by a variance (determining how much the function can deviate from the mean) and a lengthscale (determining how far each point can influence the form of the function) parameter. Besides that the covariance function allows to model the noise in each data point (how accurate they are). For now we assume the same noise for each record of waiting time and get another parameter to tune. It is a good first choice for the variance parameter to set it to the variance of the training data. That is why we fix it in the following experiment. With this two hyperparameters remain that we want to set so that it results in a model that best reflects the underlying data.

Although we are evaluating on mean absolute error, what we consider a good model is determined by the log marginal likelihood that is the probability of observing the data at hand given a certain choice of parameters - also called GP evidence maximization. So this becomes the loss function we are optimizing. In comparison to direcly optimizing the MAE it is less prone to overfitting to the data.

We will first view how the parameters to tweak influence the log marginal likelihood and from that on reason about a good choice of parameter values applying what we know about hitchhiking.

Broadly we consider a lengthscale between 100m and 10'000km and a noise of 0.1 to 10 in the transformed target value space (the range for reasonable noise levels can be obtained from the above plot of the target values in the transformed space).

We can observe that there are three local minima for the log marginal likelihood that strongly differ in the RBF kernel lengthscale. Further analysing we can find out that the global minimun lies at a 3240m lengthscale (the left minimum) and the other local minima lie at 167km and 1510km lengthscale. One can say that the lengthscale is about the distance until which points influence each other (see the graphic below). With our hitchhiking knowledge in mind we can safely say that hitchhiking culture rather changes within a magnitude of 100km than 1000km (and certainly within 1km but that would disable us to make predictions in most locations as we have too few data) and thus decide for parameter values that result in a non-global minimum. As a consequence we are setting the bounds in which the lengthscale should lie to 10km to 1000km from now on and assume that if we find an optimal lengthscale that lies within those reasonable bounds it is the local optimum that we want to achieve.

It is interesting to not that we can observe increasing data noise for larger lengthscales due to the fact that smoother functions are less able to fit to the povided training data points.

To close this first section we are having a first look at the uncertainties that we can retieve from the GP model. The uncertainties (manifesting in the 95% confidence intervals) are only slightly higher where we have less training data. But overall the uncertainty seems quite even - the cause for this still has to be investigated. Still the tiny differences were of use for our final map.

Making predictions in longitude-latitude space¶

Now we have layed the foundation to move on to the actual problem where points are represeted by longitude (x-axis) and latitude (y-axis). With this we are faced with a 2D-version of the above problem and we can build up on the insights we have gained so far.

We will develop predictive models for Germany, Europe and eventually the whole world. The rational behind this is that more challenges will emerge the broader the map gets and the more difference we get in the density of data points. That is why we want to first look at the regions where the majority of the data concentrates. Besides that we want to make sure that the resulting predictive model is particularly precise and informative where most of the hitchhiking traffic occurs which is Europe (see map below).

Gradually we will build more and more complex models with more free hyperparameters and more complex kernel functions.

Country level - Germany¶

First we are taking a look at Germany. We consider the same four models as in the 1D example and compare their performace. From now on we will use 5-fold cross-validation if the runtime for training the model permits. For the displayed maps we are using a low resolution as prediction with GPs is costly namely $\mathcal{O}(n^2)$ if $n$ was the number of training samples.

Continet level - Europe¶

Global level¶

Tweaking the Gaussian process¶

On all three maps the learning GP model shows better performance than the other three naive models regarding MAE. Thus it seems to be worth it to further develop and improve the GP. In addition the maps built by the GP strongly fullfil our visual requirements.

So far we modelled the GP so that the RBF lengthscale is the same in longitude and latitude direction. We believe that this is a reasonable choice as there is no obvious reason why a single data point should influenc one direction more than the other. Still there might be broad (non-obvious) structures in the way land mass is shaped or highways are built that could favor one of the directions. Below we can observe that accoding to the models data points have a stronger influence in the north-south-direction than in the east-west-direction.

Through the maps on differently-sized regions we could observe that RBF lengthscales became larger with broader maps. Thus we can assume that there are different levels on which a similar attitude towards hitchhiking exists for example on a regional, state on country level. This is also what we can report from experience.

As we can see the regional differences we observe in the map of Germany are no longer visible on the other maps. To mitigate this effect and to incorporate those findings into our model we have to allow it to choose and mix different lengthscales. One way to achieve this is to use multiple RBFs in the kernel by summing them up. Let us use three RBFs as an rather arbitrary choice for now.

Now the variance parameter (factor in front of the squared exponential kernel) fulfills the important function to weight (mix) the RBFs with different lengthscale differently. If the variance was fixed the optized model would likely have the same lengthscale for each RBF. Another measure we are applying to prevent same lengthscales is to define non-overlapping lengthscale-bounds for the three RBFs thus hopefully getting a small, medium and large lengthscale. We are choosing narrower variance bounds for the RBF with the smallest lengthscale as allowing short lengthscales and high variance often results in overfitting to the data which we want to prevent.

Saving our currently best model and training on all available data¶

Exploiting the probabilistic approach¶

Eventually we can turn towards one of the reasons we applied a probabilistic model such as the GP in the first place. Alongside the mean of the predictive distribution (the function we are using to make predictions) it gives us uncertainties about the predictions via the standard deviations of the predictive distribution. Those are especially handy when we communicate the results of this work via a map to also convey that predictions made in certain area of the world are uncertain because of a lack of training data in that region and thus should not be trusted.

Further ideas and work¶

There are a few ideas how all this could be developed further.

1. As stated in the beginning there is measurement and outlier noise in the data. So far we did not model measurement noise specifically. An idea would be to assume that measurement noise increases with waiting time. One might be able to learn a function that represents this kind of noise. Giving an example one might assume that for a recorded waiting time of 5min it only deviates from the real waiting time whereas for 4h there is a 30min deviation.

2. Combining multiple RBF functions in one kernel is a quite simple way to model a variety of lengthscales. Being more sophisticated one could apply multiple rational quadratic kernels instead as this kernel models a distribution over lengthscales.

3. Applying the log-transformation to the data before applying the GP allowed us to never get negative predictions. On the other end one might not want to get predictions larger than the longest recorded waiting time and thus constrain the upper bound as well. For example this could be achieved by applying a probit-transformation. However we did not see that too large predictions were a problem so far.

4. As training a GP on a large dataset such as for the whole world takes some time we could not search further over the parameters of our final model although one ideally would not want to end up with parameter values at the interval bounds as it shows that the model is not optimal. For optimization and finding local optima one could have a look at Bayesian optimization.

5. On could go beyond longitude and latitude as features for each data points e.g. also taking the date or day of the week into account. We are afraid we do not have enough data at the moment to build meaningful models that way.

6. Finding a more suitable initial distribution than log-normal of the data. Currently the correcy inverse transformation does not yield good results (thus we modified it). Could check numeric_transformer.get_transformer_with_least_skew() for this.

7. Curretly we are not conciously tackling any biases related to that people only hitchhike in regions where they know it works, that we have no data of unsuccessful rides and that most recorded hikes are contributed by people with a positive attitude towards their hitchhiking experience and frequent hitchhikers and thus likely lower waiting times

More GP resources I liked¶

• https://distill.pub/2019/visual-exploration-gaussian-processes/
• https://ndcbe.github.io/cbe67701-uncertainty-quantification/10.03-Gaussian-Process-Regression.html
• https://domino.ai/blog/fitting-gaussian-process-models-python
• https://scikit-learn.org/stable/auto_examples/gaussian_process/plot_gpr_co2.html#sphx-glr-auto-examples-gaussian-process-plot-gpr-co2-py

To cite this work please use the follwing BibTeX citation

@misc{wenke_heatchmap_2024,
  author = {Wenke, Till},
  title = {Heatchmap: A Gaussian process approach to predict hitchhiking waiting times},
  year = {2024},
  note = {https://tillwenke.github.io/2024/04/21/hitchmap-gp.html},
}