A Short Note on Analyzing Sequence Complexity in Trajectory Prediction Benchmarks
Ronny Hug Stefan Becker Wolfgang Hübner Michael Arens
cs.LG cs.RO
  
	
Convolutional Spiking Neural Networks 

for Spatio-Temporal Feature Extraction
    Ali Samadzadeh^1, Fatemeh Sadat Tabatabaei Far^1, Ali Javadi^1,
 Ahmad Nickabadi^1, Morteza Haghir Chehreghani^2

^1Amirkabir University of Technology, Tehran, Iran

^2Chalmers University of Technology, Gothenburg, Sweden

{a_samad, tabatabaeifateme, fleissig, nickabadi}@aut.ac.ir, morteza.chehreghani@chalmers.se


    Final Version, December 30, 2023
================================================================================================================================================================================================================================================================================================================================

empty
empty




	
The analysis and quantification of sequence complexity is an open problem frequently encountered when defining trajectory prediction benchmarks.
In order to enable a more informative assembly of a data basis, an approach for determining a dataset representation in terms of a small set of distinguishable prototypical sub-sequences is proposed.
The approach employs a spatial sequence alignment, which enables a following learning vector quantization (LVQ) stage.
A first proof of concept on synthetically generated and real-world datasets shows the viability of the approach.







§ INTRODUCTION
 
An open question frequently encountered in the context of trajectory prediction is the quantification of dataset complexity, leading to hard-to-solve or too simple benchmarks.
Current attempts in standardized benchmarking, e.g. TrajNet++ as mentioned in <cit.>, originate from heuristics or experience-based criteria when assembling the data basis.

Dissecting trajectory datasets, each dataset can be reduced to a small number of prototypical sub-sequences specifying distinct motion patterns, where each sample can be assumed to be a variation of these prototypes. 
Following this assumption, the quantification of dataset complexity could be based on the number and variation of prototypes.
Towards this end, an approach for determining prototypes from a dataset is proposed.
The approach applies a spatial alignment[Not to be confused with a temporal sequence alignment] step followed by vector quantization for clustering aligned samples. 
Experiments are conducted on a synthetically generated dataset and an exemplary standard benchmarking dataset in order to provide a first proof of concept.
Lastly, potential uses of the proposed approach are discussed.



§ SEQUENCE ALIGNMENT


Given a set of trajectories (samples) 𝒳 = {X_1, ..., X_N}, as sequences of M subsequent points X_i = {𝐱^i_1, ..., 𝐱^i_M}, each sample is first normalized by moving it into a self-centered reference frame and scaling it to unit length:

    X^norm_i = {𝐱^i_j - 𝐱̅/𝐱^i_M - 𝐱^i_1 | j ∈ [1,..,M] }.

It has to be noted that this normalization solely serves the purpose of moving all samples into a common value range and is not a good normalization in terms of pooling similar samples. 
Then, all samples are aligned with a single prototype Ŷ = {ŷ_1, ŷ_2, ..., ŷ_M } by using similarity transformations, which are retrieved from a regression model ϕ: X →{𝐭,α,s}.
Ŷ and ϕ are learned by minimizing the mean squared error between each aligned sample X^ϕ_i = ϕ(X^norm_i) and the prototype Ŷ

    ℒ_align(ϕ(X^norm_i), Ŷ) = 1/M∑^M_j=1𝐱^i_j - ŷ_j^2_2

using stochastic gradient descent.
This is different from linear factor models, where the whole training set has to be considered.
With respect to equation <ref> and the similarity transformation, the trivial solution that maps all samples onto the origin has to be avoided.
A brute force approach to this problem is to enforce a minimum scale. 
These steps result in a minimum variance alignment of all samples with respect to the learned prototype.
Further, by learning the prototype and the transformation concurrently, the prototype adapts to the most dominant motion pattern, and the normalized data is aligned accordingly. 





§ LEARNING VECTOR QUANTIZATION
 

Clustering approaches can be applied after alignment, since the alignment approach distributes random errors homogeneously over the sequence. 
For clustering, a vector quantization (LVQ) approach is proposed, which is inspired by <cit.> and can directly be integrated in a deep learning framework.
Here, aligned samples are mapped onto K prototypes 𝒵 = {Z_1, ..., Z_K}, with Z_k = {𝐳^k_1, ..., 𝐳^k_M}, in quantized space.
This results in a concise set of prototypes representing the given dataset.
The prototypes are learned by minimizing the mean squared error between the aligned samples and the respective closest prototype in quantized space:

    ℒ_LVQ   = 1/N · M∑_i=1^N∑^M_j=1𝐱^i_j - z_j(i)^2_2 + γ· L_global, 
    with
    
    	z_j(i)    = 𝐳^argmin_k 1/M∑_jj=1^M𝐱^i_jj - 𝐳^k_jj^2_2_j, 
    
    	L_global   = 1/N · M · K∑_i=1^N∑_j=1^M∑_k=1^K𝐱^i_j - 𝐳^k_j ^2_2.

In addition, a regularization term L_global is employed for driving all prototypes towards the global mean.
Intuitively, this moves low-support prototypes in more reasonable areas within quantized space, while the winner takes all loss in ℒ_LVQ keeps them within range of relevant sample clusters.
Due to the fact that, it is unknown how many prototypes are necessary, unnecessary prototypes can be identified by their similarity to the dominant prototype and thus be sorted out later, in case K is too large.

Initialization. Due to the winner takes all strategy, ℒ_LVQ only updates prototypes that have supporting samples.
While the regularization term tries to account for this, initializing the K prototypes appropriately helps to improve the quantization results.
Thus, a Forgy initialization is applied, i.e. randomly selected samples from the dataset are used as initial prototypes <cit.>. 
This follows common practice of other vector quantization approaches, such as K-means <cit.>. 

Refinement. A heuristic refinement scheme is employed in order to remove unnecessary prototypes when K was too large.
Starting with the prototype which is supported by most training samples, additional prototypes are added based on their dissimilarity to previously added prototypes and their impact on the global error given the refined set of prototypes.
By choosing prototypes that maximize the global error, a wider coverage of motion patterns is ensured.
Thus, unnecessary prototypes, especially those similar to the most dominant prototype, can be sorted out.



§ QUALITATIVE EVALUATION


As a first proof of concept, a qualitative evaluation is conducted on a synthetically generated dataset (SGTD) and the combined hyang scenes <cit.> taken from the stanford drone dataset (SDD, <cit.>).
SGTD consists of 200 randomly distributed trajectories consisting of M=31 points[This number is arbitrary and does not affect the viability of the approach.], with random orientations and different normally distributed speed profiles. 
It covers 4 motion patterns: constant (125 samples), accelerated (33 samples), and curvilinear (29 (left) and 13 (right) samples; direction change by α∼𝒰(80, 90) degrees in either direction).
For SDD-hyang, the rate has been reduced to 6 samples per second.
This achieves a more noticeable difference between subsequent trajectory points.
Further, all trajectory segments containing 54 points[Corresponds to the first quartile with respect to the number of trajectory points for all trajectories] are considered for training. 
Since this is a real-world dataset, the generating features are unknown.
Yet the occurrence of all basic motion patterns (constant, acceleration, decelerated and curvilinear motion) is expected reflecting its complexity. 
For both datasets, K=10 prototypes are used, providing sufficient capacity to capture all relevant features while also allowing to test the proposed regularization and refinement strategies.

The results of the alignment and the learned prototypes are depicted in figure <ref>.
For SGTD (first row), it can be seen that all samples are aligned such that they follow a common mean orientation and similar samples are pooled together.
All 4 prototypes necessary for modeling the dataset were found with correct association between data and prototypes.
For SDD-hyang, there is not an as clear separation between different motion patterns. 
However, a similar behavior can be observed when looking at the aligned data.
Further, as expected, the quantization yields an additional prototype corresponding to a decelerated motion.



§ DISCUSSION AND FUTURE WORK

At last, given the results in section <ref>, future work building on the proposed approach is discussed.

Quantifying Dataset Complexity.
A thorough complexity analysis of standard benchmarking datasets for trajectory prediction, deriving relevant complexity factors from the proposed prototype representation should be considered.
These factors could involve for example the variety of prototypes or the sample association bias.
Analyzing the complexity of these datasets could offer more insight into their viability for evaluating certain aspects of machine learning models.

Deriving a Benchmark from Insights.
Insights gained from dataset complexity analysis could be used for deriving a new benchmark for trajectory prediction, that specifically targets different aspects of a given model.
This could provide a viable complementary benchmark to the recently published TrajNet++ benchmark (mentioned in <cit.>; successor of TrajNet <cit.>).

Data Preprocessing.
The proposed approach may also serve as universal preprocessing stage for trajectory prediction models.
Thus an experimental study should be conducted for comparing preprocessing approaches.


-12cm   
                                  
                                  
                                  
                                  
                                  



IEEEtran




