Bayesian Nonparametric Modeling of Driver Behavior using HDP Split-Merge Sampling Algorithm
Vadim Smolyakov Julian Straub Sue Zheng John W. Fisher III
stat.ML

[NO \title GIVEN]
    [NO \author GIVEN]
    December 30, 2023
======================

empty
empty
This work was partially funded by the Ford-MIT alliance and by the Office of Naval Research Multidisciplinary Research Initiative (MURI) program, award N00014-11-1-0688.



Modern vehicles are equipped with increasingly complex sensors. These sensors generate large volumes of data that provide opportunities for modeling and analysis.  Here, we are interested in exploiting this data to learn aspects of behaviors and the road network associated with individual drivers.  Our dataset is collected on a standard vehicle used to commute to work and for personal trips.  A Hidden Markov Model (HMM) trained on the GPS position and orientation data is utilized to compress the large amount of position information into a small amount of road segment states. Each state has a set of observations, i.e. car signals, associated with it that are quantized and modeled as draws from a Hierarchical Dirichlet Process (HDP). The inference for the topic distributions is carried out using HDP split-merge sampling algorithm. The topic distributions over joint quantized car signals characterize the driving situation in the respective road state. In a novel manner, we demonstrate how the sparsity of the personal road network of a driver in conjunction with a hierarchical topic model allows data driven predictions about destinations as well as likely road conditions.







§ INTRODUCTION



Vehicles are equipped with an increasing number of sensors and electronics to react dynamically to changing road conditions and to increase driver safety. As a result, large volumes of driver-specific data related to driving conditions and driver behavior are generated.  We are interested in analyzing this data to learn models of driving behavior. Such models could be used to anticipate dangerous situations, to improve the driving schedule of a person, and to tailor various aspects of the driving experience to the individual.


Here, we use data collected from one vehicle's sensors over numerous trips to construct a Hierarchical Dirichlet Process (HDP) model of driving behavior and road conditions. HDPs are commonly used for topic modeling of text corpora <cit.> to uncover the set of topics that comprise each document in the corpus. In our case, the documents are road segments and the words are associated quantized sensor measurements. The topics in the HDP model are sensor distributions in the road segments; these distributions capture the driving conditions in each road segment as encountered by the driver as well as their driving behavior and common driving conditions. To our knowledge this is a new approach for modeling driving behavior. Unlike related work which is based on assumptions about the capabilities and behaviors of humans (i.e. see for an overview <cit.>), our model is purely data driven.

It is important to note that the hierarchy within the HDP model allows sharing of measurements across similar road segments. This is an appealing aspect of the model since it enables us to learn an expressive model for road segments which are visited rarely via similar road segments that are visited more often. 

In order to utilize an HDP model, we first organize the sensor data into "documents" (i.e., road segments and their associated quantized measurements). We consider the case in which a road map is not available, however, it is straightforward to incorporate such information. Additionally, typical drivers often traverse a small subset of the roads in the road network. We use a Hidden Markov Model (HMM) to learn the road segments. The HMM condenses position information from recorded trips into road segment states. The set of hidden states effectively corresponds to a sparse road network which consists only of the roads which the driver has traversed. We then use the trained HMM to associate sensor measurements to road segments to produce "documents" for the HDP model.

In addition to organizing the data for the HDP model, the HMM also provides insight into driver behavior such as typical routes and probable destinations.  Special hidden states are introduced in the HMM to represent starting locations (sources) and destinations. Conseqently, identification of the most likely route between two states and finding the distribution over probable destinations become well-posed questions and allow us to make route and destination predictions.


The contributions of this paper are (1) to show how sparsity in the HMM transition matrix together with starting and absorption states lead to accurate long term predictions of driver routes and destinations and (2) the novel application of a HDP split-merge sampler to model the joint distribution of quantized vehicle signals scalable to a large number of road-segments.

























§ HIDDEN MARKOV MODEL


An HMM is used to model the trips that a driver takes through a road network. We explore two models for the HMM. In the first model, the hidden state corresponds to a road segment, a start location, or a destination. In this model, the future path is independent from the past path when conditioned on the current road segment. We expect this to be a poor model of driver behavior since this is likely an oversimplification; the past can provide considerable information about the future. For instance, drivers often do not return to a previously visited state within a trip (unless they are lost). 

In our second model, we attempt to capture more of the trip history in the current state by augmenting the road states with the start location. Under this model, the road segment at the next time instance depends only on the current road segment and the start location. We will show that this model is more representative of driver behavior and provides accurate predictions of destinations and routes. We describe this second model below. The first model is a simplification of the described model. 




 §.§ Hidden States


Each hidden variable, x_t, in the HMM (see Fig. <ref>) takes on a value from the set of hidden states, 𝒳.  Source states, 𝒳_S, destination states, 𝒳_D, and road segment states augmented by the source state, 𝒳_R ×𝒳_S, compose the set of hidden states: 𝒳 = 𝒳_S ∪𝒳_D ∪ (𝒳_R ×𝒳_S). Destination states are absorbing states which are indicated by key-off events in the data. Similarly, source states are indicated by key-on events. The distribution over the initial state, x_0 ∈𝒳, is parameterized as p(x_0 = m) = θ_m. Conditioned on the current state, x_t, the distribution for the next state, x_t+1, is parameterized as 

    p(x_t+1 = m|x_t=k) = θ_km.

Since physically realizable transitions occur only between road segments in close proximity, we would expect most transition probabilities to be zero. We use a Dirichlet prior on the parameters with α < 1 to favor a sparse transition matrix: 

    p(θ_k1, θ_k2, …, θ_k |𝒳|) ∝∏_i=1^|𝒳|θ_ki^α-1.





 §.§ Observation Model


Each trip contains measurements of position, r_t and heading, h_t. When the vehicle has GPS, the recorded position is the GPS position; otherwise the reported position is obtained by dead reckoning, a process which estimates position by combining the previous position with aggregated incremental changes in a relative coordinate system. Positions which are inferred using dead reckoning are indicated by an inferred-position indicator, q_t; for such measurements, we model a larger uncertainty associated with the measurement. 

In addition to position and heading measurements, there is a key-on event at the start of each trip which indicates that hidden state must be from the set of source states. In the measurement model, we have a binary key-on indicator variable, k^on_t, which takes value 1 if a key-on event occurs at time t. Similarly, there is a key-off event and corresponding indicator variable, k^off_t, which indicates that the hidden state is from the set of destination states. This set of measurements comprise the observation y_t = {r_t, h_t, q_t, k^off_t, k^on_t}. 

Conditioned on the hidden state, the measurement model is as follows:

    p(r_t, h_t, q_t, k^on_t, k^off_t| x_t) =    p(r_t|q_t, x_t)p(h_t|x_t) p(q_t|x_t)
       × p(k^on_t|x_t)p(k^off_t|x_t).

Note that the conditional distribution for position depends on the value on the inferred-position indicator; a larger uncertainty is associated with the position when the position has been inferred. Position is Gaussian with state-dependent parameters: 

    p(r_t|q_t, x_t) = 𝒩(r_t; μ_r,x_t, Σ_r,x_t)    q_t = 0 
    𝒩(r_t; μ_r,x_t, c ·Σ_r,x_t)    q_t = 1

where c > 1 is a constant used to capture the increase in uncertainty of the inferred position. 

Heading is also Gaussian with its own state-dependent parameters:

    p(h_t|x_t) = 𝒩(h_t; μ_h,x_t, Σ_h,x_t).

The inferred position indicator has a Bernoulli distribution with parameter, p_x_t. The key-on and key-off measurements are indicators of source and destination states respectively: k^on_t = 1(x_t ∈𝒳_S), k^off_t = 1(x_t ∈𝒳_D) and have degenerate distributions.

We would expect measurements arising from the same physical location (road segment) to have parameters which do not depend on the source state. Therefore, the measurement parameters are independent of the source state when conditioned on the road segment state. That is, μ_r,x_t = μ_r, x_r for x_t ∈{x_r ×𝒳_S}, where x_r ∈𝒳_R, and likewise for the other measurement parameters. When we estimate the measurement parameters for a road segment, this formulation allows us to aggregate observations from trips which start at different locations but share this physical road. 

Similarly, there will be pairs of source and destination states will correspond to the same physical location. If a trip ends at a given location, the next trip will typically start from the same location. Since this pair of states share physical properties, these states will share measurement parameters. 



 §.§ EM Updates

Given the volume of data under consideration, we find that an EM formulation using explicit state assignments provides a tractable learning approach. This approach yields locally optimal values for the set of parameters ψ = {θ_m, θ_km, μ_r,m, Σ_r,m, μ_h,m, Σ_h,m, p_m} for m,k ∈𝒳 using measurements from N trips. The EM updates consist of iteratively finding the most likely assignment for the hidden states given previous parameter estimates, then using these assignments to improve the parameter estimates. The reader is referred to  <cit.> for an introduction to the EM algorithm. 


To initialize the parameters, we run DP means <cit.> to cluster the measurements based on position and heading; a state is created from each cluster. DP means allows us to initialize the model without pre-specifying the number of states. Measurements assigned to the cluster (state) are used to calculate initial values for measurement model parameters. The transition matrix is initialized as a full matrix with higher probability for states which are closer together. The distribution for the first state is initialized as a uniform distribution. 



 §.§ Predicting Routes and Destinations

Using the HMM model, we can predict a driver route from state a to state b by identifying the sequence of states {x_1^*=a, x_2^*, …, x_N^*=b} with the highest likelihood:

    ∏_i=1^N-1 p(x^*_i+1 | x^*_i)  = max_n max_x_1 = a,   x_n = b{x_1, …, x_n}∈𝒳∏_i=1^n-1  p(x_i+1 | x_i)

It is well known, <cit.>, that this can be formulated as a shortest path problem by defining a graph on the hidden states with edge weights w_ij = -log p(x_j | x_i). 

Additionally, from any road segment state, i, we can find the probability of reaching any destination state, j; this is known as the absorption probability. The absorption probability, a_ij, is the probability of reaching absorbing state, j, if the chain starts from state, i, and can be found by solving the following set of equations: 

    a_jj   = 1   ∀ j ∈𝒳_D 
    
    a_ji   = 0   ∀ j ∈𝒳_D    ∀ i ≠ j 
    
    a_ij   = θ_ij + ∑_k ∈𝒳∖ jθ_ika_kj  ∀ j ∈𝒳_D,  ∀ i ∈𝒳_R

This gives us a probability distribution over destinations when we start from a given road state.










 §.§ Bayesian Nonparametric Topic Modeling of Car Signals


















Thus far, we have formulated an HMM model for driving behavior which has predictive aspects. The model is also used to organize the data into "documents" so that we can perform HDP topic modeling on the dataset. 
In this section we discuss how we combine a standard HDP model with the use of an HMM to discover documents. We also relate our HDP model for car signals to the classical HDP topic model.

To bridge the gap between the classical HDP topic modeling of text corpora and the modeling of car signals, such as velocity, acceleration and rotational speed, note the following correspondences: 

    word   ↔car signals at one instance in time
    document   ↔road segment
    corpus   ↔map


Each learned road segment from the HMM is used as a document in the HDP model. To obtain a set of sensor measurements associated with a road segment, or a set of words from the document, we perform ML assignment of road states for the trips and assign the corresponding sensor measurements to those road states.

Since the car signals are continuous quantities, we quantize them using DP means <cit.> and use a discrete base measure equivalent to the classical text corpus topic model.
This means that words are described by a multidimensional vector, which amounts to modeling the joint distribution over all signals.

In the next section we briefly summarize the HDP model and describe how we use a parallelizable HDP split-merge sampler to perform inference on a large number of discretized car measurements. For a more detailed presentation the reader is referred to the original papers <cit.> and <cit.>. 



 §.§ HDP model


The HDP model describes a set of D documents, which contain N_j words x_ji each. In this context, the documents correspond to trips and the words in a document correspond to quantized sensor measurements from the trip. The distribution of words x_ji is modeled as a mixture of topic distributions θ_k. 



















The graphical model can be described as follows. At the top-level, we have β∼GEM(1,γ) that determines the global topic proportions via the stick-breaking construction <cit.>. Also, shared at the top-level are the global word distributions θ_k ∼ f_θ(θ;λ). At the document-level, π_j is the DP with β as the base measure: π_j ∼DP(α, β), from which topic assignment labels z_ji∼Cat(π_j) are sampled. Finally, the observed signals can be expressed as x_ji∼ f_x(x_ji;θ_z_ji), where the topic assignment z_ji indexes corresponding word distribution θ_z_ji. The dashed nodes are the auxiliary split-merge nodes that learn a two-component mixture model for each cluster. These "sub-clusters" are then used to propose splits and merges that are selected over time. This method combines a Gibbs sampler that is restricted to non-empty clusters with a Metropolis-Hastings (MH) algorithm that proposes sub-cluster splits and merges.




 §.§ Split-Merge HDP Sampler


Because of the large quantity of data, we use highly parallelizable split-merge HDP sampler described in <cit.>. Augmenting the sample space with sub-clusters leads to proposals of likely splits and merges. A combination of a restricted Gibbs sampler (that does not create new clusers) with split/merge moves results in an ergodic Markov chain. 





  §.§.§ Resricted Gibbs Sampler

Let m_jk denote the number of clusters in document j with shared topic k and let n_jtk denote the number of words in document j in cluster t with topic k. Then, the marginal counts n_j..=∑_t,kn_jtk and m_j.=∑_km_jk represent the number of words and topics in document j, respectively. Extending the DA sampling algorithm results in the following restricted posterior distributions:

    p(β|m)   =   Dir(m_.1,...,m_.K,γ)
    
      p(π_j|β,z)   =   Dir(...,αβ_K+n_j.K,αβ_K+1)
    
      p(θ_k|x,z)    ∝    f_x(x_I_k;θ_k)f_θ(θ_k;λ)
    
      p(z_ji|x,π_j,θ)    ∝   ∑_k=1^Kπ_jkf_x(x_ji;θ_k)1[z_ji=k]
    
      p(m_jk|β,z)    =    f_m(m_jk;αβ_k, n_j.k)
       =   Γ (αβ_k)/Γ(αβ_k + n_j.k)s(n_j.k,m_jk)(αβ_k)^m_jk

Since p(β|m) is not known analytically, we use the auxiliary variable m_jk. s(n,m) denotes unsigned Stirling numbers of the first kind. Note that the last components β_K+1 and π_j(K+1) aggregate the weight of all empty topics. Finally, I_k={j,i; z_ji=k} denotes the set of indices in topic k, and f_x and f_θ denote the observation and prior distributions. The equations above can be sampled in parallel and fully specify the restricted Gibbs sampler. 

The method combines a Gibbs sampler that is restricted to non-empty clusters with a Metropolis-Hastings (MH) algorithm that proposes splits and merges.




  §.§.§ Subcluster Splits and Merges

For each topic k, we fit two sub-topics kl and kr referred to as the left and right sub-clusters. Each topic is augmented with global sub-topic proportions β̅_k = {β̅_kl,β̅_kr}, document-level sub-topic proportions π̅_jk={π̅_jkl,π̅_jkr}, and sub-topic parameters θ̅_k = {θ̅_kl,θ̅_kr}. Moreover, each word x_ji is associated with sub-topic assignment z̅_ji∈{l,r}. Then the marginal posterior distributions can be derived <cit.> as:

    p(β̅_k|·)   =   Dir(γ + m̅_.kl,γ + m̅_.kr)
    
      p(π̅_jk|·)   =   Dir(αβ̅_kl+n̅_j.kl,αβ̅_kr+n̅_j.kr)
    
      p(θ̅_kh|·)    ∝    f_x(x_I_kh;θ̅_kh)f_θ(θ̅_kh;λ)
    
      p(z̅_ji|·)    ∝   π̅_jkf_x(x_ji;θ̅_k)1[z̅_ji=k]
    
      p(m̅_jkh|·)    =    f_m(m̅_jkh;αβ̅_kh, n̅_j.kh)

Notice the similarity between these equations and ones derived earlier. Inference is performed by interleaving the sampling equations (1)-(5) with marginal posterior equations (6)-(10).



  §.§.§ Metropolis-Hastings


A Metropolis-Hastings framework proposes splits and merges of sub-clusters and either accepts or rejects them. Let v={β,π,z,θ} and v̅={β̅,π̅,z̅,θ̅} be a set of regular and auxiliary variables, respectively. Then a sampled proposal {v̂,v̂̅̂}∼ q(v̂,v̂̅̂|v) is accepted with probability:

    P_a = min[1, p(x,v̂)p(v̂̅̂|x,v̂)/p(x,v)p(v̅|x,v)·q(v|x,v̂)q(v̅|x,v̂̅̂,v)/q(v̂|x,v)q(v̂̅̂|x,v̅,v̂)]








 §.§ Performance Evaluation










To evaluate the performance of the HDP model, we are computing the average log predictive probability of held-out words. To compute this probability, we split a test document into two sets: held out words w^ and observed words w^. Then we update the model using the observed words. This gives us the posterior parameters {^,^} for the test document which we in turn use to find ϕ^ for the held-out words. Now we can compute the probability of a held-out words as given all training data  as well as the observed words w^ in this document: 

    [            p(w^_n| , w^) = ∑^T_i=1 q(z_n = i|ϕ^); ∑^K_k=1 q(c_i = k| ^) p(w^_n | z_n = i,c_i =k,^) ]


where p(w^_n| z_n^i,c_i^k,^) = ^_k(w^_n)/∑_w _k^(w) is the conditional distribution of a held-out word under the posterior distribution of words in this document. 


As a model to compare the HDP to, we utilize a non-hierarchical model that assumes a Categorical distribution with a Dirichlet prior for the words in each road-state. These distributions are modeled completely independent – not connected via a hierarchy like in the HDP model. This allows us to compute posterior Categorical distributions given the observed words in each road-state.










§ RESULTS

In the following we will first give results for the predictive power of the HMM model before we describe a topic model for the joint distribution of speed and time-of-day measurements.



 §.§ Dataset Description

Our dataset comprises of 1K trips recorded from a standard car used by a single
driver. The routes are mostly commuting to work but also some longer range
trips outside the city.
 
The GPS position and heading measurements of the car are used to train the HMM
model. From various other signals of the car we selected quantized car velocity
and time of day for the HDP topic model. These were selected, since they
contain interesting information both about the driving behavior as well as the
driving situation in a road state.



 §.§ Predicting Routes and Destinations

To evaluate the quality of the learned HMM, we examine the ability of the HMM to predict the destination for 20 held-out trips under the two different models. Additionally, we compare the path of the held-out trips against the most likely route obtained from the transition matrix for the HMM.










Fig. <ref> shows the performance of the two models on a held-out trip. The plots under the maps in the figure show the absorption probabilities for the probable destinations as a function of time. The maps above show the trip, the most likely route between the source and destination state, and the locations of the probable destinations. While the most likely path between source and destination from both models agrees with the observed trip trajectory, we observe that the augmented model is able to identify the correct destination sooner than the first model. In fact, the first model is able to correctly predict the destination after 10% of the trip for only 3 of the held-out trips while the augmented model is able to do so for 11 of the trips. 

In Fig. <ref>, we show the most likely destination for each road segment. For the augmented model, since each state associated with a road segment also has a start location, we've chosen a particular start location to illustrate the differences between these two models. In particular, when starting from the specified start location, we see that trips which traverse beyond destination 7 in Fig. <ref> (bottom) are more likely to terminate at a destination which is further from the starting location. The unaugmented model is unable to make this distinction, so trips which traverse road segments near destination 5 in Fig. <ref> on the top (which corresponds to destination 7 in Fig. <ref> on the bottom) are likely to terminate at that destination.











The results show that the most likely route obtained by the models frequently align exactly with the path of the held-out trips. This can be explained through the sparsity of the transition matrices; since each state can only transition to few states, and very often just one state, long term predictions in this model are quite accurate. 





 §.§ HDP Model




We are quantizing velocity and time-of-day measurements to words that can be fed into the HDP inference algorithm.





Quantization is performed via DP k-means clustering over the individual signals. 

The speed measurements arrive at a rate of 1 Hz from the GPS sensor. 
There are 696k joint observations – velocity/time-of-day pairs – across all
12k road states. As can be seen in Fig. <ref>, these
observations are distributed non-uniformly – we get a lot of measurements on
the daily commute route and few on highways leading outside the city. This
means that the road-state corpus has very imbalanced document sizes when
compared to text corpus modeling. However, our results demonstrate, that this
presents no issue to the inference algorithm.


We empirically found the following set of parameters: γ=10.0 and α=0.1, corresponding to the global and local concentration parameters, respectively. 


Fig. 5 demonstrates that the hierarchy in the HDP is
able to pool measurements from different road-states to obtain a descriptive
topic for these. For each road state we obtain the maximum likelihood (ML)
topic assignment and plot the respective road states in red. This pooling of
observations can for example be observed for topics 0 and 41, which consist of
almost all highway road states as can be seen in the ML topic assignment plots
(compare the red road segments to the highways depicted in map in
Fig. <ref>). 


Using the inferred mixture of topics for each state, we can now compute the ML
estimate of the marginals for the individual sensor signals and plot them
color-coded for each road state. Fig. <ref> shows this for the
marginal
over speed and time-of-day.  Comparing the spatial distribution of the ML speed
estimates computed from the inferred HDP model in Fig. <ref> with ML estimates obtained from the empirical
distribution depicted in Fig. <ref>, we can see that
the HDP model is able to capture the distribution of the input data.  

Additionally, it is clear from the spatial distribution of the ML estimates of driving speeds, that the HDP
model captures for example the fact, that inner city driving is slower than
highway driving. The ML estimates of time-of-day (Fig. <ref> and <ref>) show that the trips outside the city
were not undertaken in the morning or evening.








































































 §.§ Comparison of Inferred HDP Marginals with Empirical Marginals

The combined HMM and HDP models can be used to obtain expected road conditions along various routes. In this example, we look at the speed profile along a typical driver route. The HMM is used to find the most likely route between two locations. The HDP provides the marginal distribution over speed for each road state. 

Since the HDP pools measurements from the different road-states, we expect the inferred HDP marginals to be a more robust estimate than an empirical marginal distribution. Especially for road-states have only a few measurements associated with them, an empirical marginal distribution of the sensor measurements based on just the data associated to that road-state can be a poor estimate of the marginal. We compare the two marginals using the data likelihood of a held-out set under the marginals. 

Since the empirical distribution over sensor measurements has a zero likelihood for measurement values which haven't been previously observed at the road-state, we apply a Dirichlet distribution prior and use the predictive distribution as the empirical marginal. The likelihood of  speed measurements conditioned on time-of-day for the 20 held-out trips is shown in Fig. <ref>. 




                                  
                                  
                                  
                                  
                                  


§ CONCLUSION


We have shown that the inherent sparsity of the learned personal road network allows accurate long term predictions of driver routes. Additionally, augmenting the model with start location yields a more representative model which provides better destination predictions. 
Exploiting the hierarchy of the HDP topic model, we are able to learn expressive topic distributions despite the fact that the number of car signal measurements differs widely between different road states. 
The combination of both types of of models allows us to model the driving behavior of an individual driver. This type of model can for example assist in optimizing the daily commute route or help predict traffic jams. 

As a next step it would be interesting to compare the driver models for different drivers to allow driver classification based on the driving behavior.






















./IEEEtran 


