DETERMINANTAL POINT PROCESSES
Year: 2020

Abstract:
The ability to forecast a set of likely yet diverse possible future behaviors of an agent (e.g., future trajectories of a pedestrian) is essential for safety-critical perception systems (e.g., autonomous vehicles). In particular, a set of possible future behaviors generated by the system must be diverse to account for all possible outcomes in order to take necessary safety precautions. It is not sufficient to maintain a set of the most likely future outcomes because the set may only contain perturbations of a dominating single outcome (major mode). While generative models such as variational autoencoders (VAEs) have been shown to be a powerful tool for learning a distribution over future trajectories, randomly drawn samples from the learned implicit likelihood model may not be diverse – the likelihood model is derived from the training data distribution and the samples will concentrate around the major mode of the data. In this work, we propose to learn a diversity sampling function (DSF) that generates a diverse yet likely set of future trajectories. The DSF maps forecasting context features to a set of latent codes which can be decoded by a generative model (e.g., VAE) into a set of diverse trajectory samples. Concretely, the process of identifying the diverse set of samples is posed as DSF parameter estimation. To learn the parameters of the DSF, the diversity of the trajectory samples is evaluated by a diversity loss based on a determinantal point process (DPP). Gradient descent is performed over the DSF parameters, which in turn moves the latent codes of the sample set to find an optimal set of diverse yet likely trajectories. Our method is a novel application of DPPs to optimize a set of items (forecasted trajectories) in continuous space. We demonstrate the diversity of the trajectories produced by our approach on both low-dimensional 2D trajectory data and high-dimensional human motion data. (Video1)

heading: 1 INTRODUCTION
text: Forecasting future trajectories of vehicles and human has many useful applications in autonomous driving, virtual reality and assistive living. What makes trajectory forecasting challenging is that the future is uncertain and multi-modal – vehicles can choose different routes and people can perform different future actions. In many safety-critical applications, it is important to consider a diverse set of possible future trajectories, even those that are less likely, so that necessary preemptive actions can be taken. For example, an autonomous vehicle should understand that a neighboring car can merge into its lane even though the car is most likely to keep driving straight. To address this requirement, we need to take a generative approach to trajectory forecasting that can fully characterize the multimodal distribution of future trajectories. To capture all modes of a data distribution, variational autoencoders (VAEs) are well-suited generative models. However, random samples from a learned VAE model with Gaussian latent codes are not guaranteed to be diverse for two reasons. First, the sampling procedure is stochastic and the VAE samples can fail to cover some minor modes even with a large number of samples. Second, since VAE sampling is based on the implicit likelihood function encoded in the training data, if most of the training data is centered around a specific mode while other modes have less data (Fig. 1 (a)), the VAE samples will reflect this bias and concentrate around the major mode (Fig. 1 (b)). To tackle this problem, we propose to learn a diversity sampling function (DSF) that can reliably generate a diverse set of trajectory samples (Fig. 1 (c)).
1https://youtu.be/5i71SU IdS4
The proposed DSF is a deterministic parameterized function that maps forecasting context features (e.g., past trajectories) to a set of latent codes. The latent codes are decoded by the VAE docoder into a set of future trajectory samples, denoted as the DSF samples. In order to optimize the DSF, we formulate a diversity loss based on a determinantal point process (DPP) (Macchi, 1975) to evaluate the diversity of the DSF samples. The DPP defines the probability of choosing a random subset from the set of trajectory samples. It models the negative correlations between samples: the inclusion of a sample reduces the probability of including a similar sample. This makes the DPP an ideal tool for modeling the diversity within a set. In particular, we use the expected cardinality of the DPP as the diversity measure, which is defined as the expected size of a random subset drawn from the set of trajectory samples according to the DPP. Intuitively, since the DPP inhibits selection of similar samples, if the set of trajectory samples is more diverse, the random subset is more likely to select more samples from the set. The expected cardinality of the DPP is easy to compute and differentiable, which allows us to use it as the objective to optimize the DSF to enable diverse trajectory sampling.
Our contributions are as follows: (1) We propose a new forecasting approach that learns a diversity sampling function to produce a diverse set of future trajectories; (2) We propose a novel application of DPPs to optimize a set of items (trajectories) in continuous space with a DPP-based diversity measure; (3) Experiments on synthetic data and human motion validate that our method can reliably generate a more diverse set of future trajectories compared to state-of-the-art generative models.

heading: 2 RELATED WORK
text: Trajectory Forecasting has recently received significant attention from the vision community. A large portion of previous work focuses on forecasting 2D future trajectories for pedestrians (Kitani et al., 2012; Ma et al., 2017; Ballan et al., 2016; Xie et al., 2013) or vehicles (Jain et al., 2016a). Some approaches use deterministic trajectory modeling and only forecast one future trajectory (Alahi et al., 2016; Yagi et al., 2018; Robicquet et al., 2016). As there are often multiple plausible future trajectories, several approaches have tried to forecast distributions over trajectories (Lee et al., 2017; Galceran et al., 2015; Gupta et al., 2018). Recently, Rhinehart et al. (2018; 2019) propose a generative model that can accurately forecast multi-modal trajectories for vehicles. Soo Park et al. (2016) also use egocentric videos to predict the future trajectories of the camera wearer. Some work has investigated forecasting higher dimensional trajectories such as the 3D fullbody pose sequence of human motions. Most existing work takes a deterministic approach and forecasts only one possible future motion from past 3D poses (Fragkiadaki et al., 2015; Butepage et al., 2017; Li et al., 2017; Jain et al., 2016b), static images (Chao et al., 2017; Kanazawa et al., 2018) or egocentric videos (Yuan and Kitani, 2019). Differently, some probabilistic approaches (Habibie et al., 2017; Yan et al., 2018) use conditional variational autoencoders (cVAEs) to generate multiple future motions. In constrast to previous work, our approach can generate a diverse set of future motions with a limited number of samples.
Diverse Solutions have been sought after in a number of problems in computer vision and machine learning. A branch of these methods aiming for diversity stems from the M-Best MAP problem (Nilsson, 1998; Seroussi and Golmard, 1994), including diverse M-Best solutions (Batra et al., 2012) and multiple choice learning (Guzman-Rivera et al., 2012; Lee et al., 2016). Alternatively, previous work has used submodular function maximization to select a diverse subset of garments from fashion images (Hsiao and Grauman, 2018). Determinantal point processes (DPPs) (Macchi, 1975; Kulesza et al., 2012) are efficient probabilistic models that can measure both the diversity and quality of items in a subset, which makes it a natural choice for the diverse subset selection problem. DPPs have been applied for document and video summarization (Kulesza and Taskar, 2011; Gong et al., 2014), recommendation systems (Gillenwater et al., 2014), object detection (Azadi et al., 2017), and grasp clustering (Huang et al., 2015). Elfeki et al. (2018) have also used DPPs to mitigate mode collapse in generative adversarial networks (GANs). The work most related ours is (Gillenwater et al., 2014), which also uses the cardinality of DPPs as a proxy for user engagement. However, there are two important differences between our approach and theirs. First, the context is different as they use the cardinality for a subset selection problem while we apply the cardinality as an objective of a continuous optimization problem in the setting of generative models. Second, their main motivation behind using the cardinality is that it aligns better with the user engagement semantics, while our motivation is that using cardinality as a diversity loss for deep neural networks is more stable due to its tolerance of similar trajectories, which are often produced by deep neural networks during stochastic gradient descent.

heading: 3 BACKGROUND

heading: 3.1 VARIATIONAL AUTOENCODERS
text: The aim of multi-modal trajectory forecasting is to learn a generative model over future trajectories. Variational autoencoders (VAEs) are a popular choice of generative models for trajectory forecasting (Lee et al., 2017; Walker et al., 2016) because it can effectively capture all possible future trajectories by explicitly mapping each data point to a latent code. VAEs model the joint distribution pθ(x, z) = p(z)pθ(x|z) of each data sample x (e.g., a future trajectory) and its corresponding latent code z, where p(z) denotes some prior distribution (e.g., Gaussians) and pθ(x|z) denotes the conditional likelihood model. To calculate the marginal likelihood pθ(x) = pθ(x, z)/pθ(z|x), one needs to compute the posterior distribution pθ(z|x) which is typically intractable. To tackle this, VAEs use variational inference (Jordan et al., 1999) which introduces an approximate posterior qφ(z|x) and decomposes the marginal log-likelihood as
log pθ(x) = KL (qφ(z|x)‖pθ(z|x)) + L(x; θ, φ) , (1) where L(x; θ, φ) is the evidence lower bound (ELBO) defined as
L(x; θ, φ) = Eqφ(z|x) [log pθ(x|z)]−KL (qφ(z|x)‖p(z)) . (2) During training, VAEs jointly optimize the recognition model (encoder) qφ(z|x) and the likelihood model (decoder) pθ(x|z) to maximize the ELBO. In the context of multi-modal trajectory forecasting, one can generate future trajectories from p(x) by drawing a latent code z from the prior p(z) and decoding z with the decoder pθ(x|z) to produce a corresponding future trajectory x.

heading: 3.2 DETERMINANTAL POINT PROCESSES
text: Our core technical innovation is a method to learn a diversity sampling function (DSF) that can generate a diverse set of future trajectories. To achieve this, we must equip ourselves with a tool to evaluate the diversity of a set of trajectories. To this end, we make use of determinantal point processes (DPPs) to model the diversity within a set. DPPs promote diversity within a set because the inclusion of one item makes the inclusion of a similar item less likely if the set is sampled according to a DPP.
Formally, given a set of items (e.g., data points) Y = {x1, . . . ,xN}, a point process P on the ground set Y is a probability measure on 2Y , i.e., the set of all subsets of Y . P is called a determinantal point process if a random subset Y drawn according to P has
PL(Y = Y ) = det (LY )∑ Y⊆Y det (LY ) = det (LY ) det(L + I) , (3)
where Y ⊆ Y , I is the identity matrix, L ∈ RN×N is the DPP kernel, a symmetric positive semidefinite matrix, and LY ∈ R|Y |×|Y | is a submatrix of L indexed by elements of Y . The DPP kernel L is typically constructed by a similarity matrix S, where Sij defines the similarity between two items xi and xj . If we use the inner product as the similarity measure, L can be written in the form of a Gram matrix L = S = XTX where X is the stacked feature matrix of Y . As a property of the Gram matrix, det (LY ) equals the squared volume spanned by vectors xi ∈ Y . With this geometric interpretation in mind, one can observe that diverse sets are more probable because their features are more orthogonal, thus spanning a larger volume.
In addition to set diversity encoded in the similarity matrix S, it is also convenient to introduce a quality vector r = [r1, . . . , rN ] to weigh each item according to some unary metric. For example, the quality weight might be derived from the likelihood of an item. To capture both diversity and quality of a subset, the DPP kernel L is often decomposed in the more general form:
L = Diag(r) · S · Diag(r) . (4)
With this decomposition, we can see that both the quality vector r and similarity matrix S contribute to the DPP probability of a subset Y :
PL(Y = Y ) ∝ det (LY ) = ( ∏ xi∈Y r2i ) det (SY ) . (5)
Due to its ability to capture the global diversity and quality of a set of items, we choose DPPs as the probabilistic approach to evaluate and optimize the diversity of the future trajectories drawn by our proposed diversity sampling function.

heading: 4 APPROACH
text: Safety-critical applications often require that the system can maintain a diverse set of outcomes covering all modes of a predictive distribution and not just the most likely one. To address this requirement, we propose to learn a diversity sampling function (DSF) to draw deterministic trajectory samples by generating a set of latent codes in the latent space of a conditional variational autoencoder (cVAE) and decoding them into trajectories using the cVAE decoder. The DSF trajectory samples are evaluated with a DPP-based diversity loss, which in turn optimizes the parameters of the DSF for more diverse trajectory samples.
Formally, the future trajectory x ∈ RT×D is a random variable denoting a D dimensional feature over a future time horizon T (e.g., a vehicle trajectory or a sequence of humanoid poses). The context ψ = {h, f} provides the information to infer the future trajectory x, and it contains the past trajectory h ∈ RH×D of last H time steps and optionally other side information f , such as an obstacle map. In the following, we first describe how we learn the future trajectory model pθ(x|ψ) with a cVAE. Then, we introduce the DSF and the DPP-based diversity loss used to optimize the DSF.

heading: 4.1 LEARNING A CVAE FOR FUTURE TRAJECTORIES
text: In order to generate a diverse set of future trajectory samples, we need to learn a generative trajectory forecasting model pθ(x|ψ) that can cover all modes of the data distribution. Here we use cVAEs (other proper generative models can also be used), which explicitly map data x with the encoder qφ(z|x,ψ) to its corresponding latent code z and reconstruct the data from the latent code using the decoder pθ(x|z,ψ). By maintaining this one-on-one mapping between the data and the latent code, cVAEs attempt to capture all modes of the data. As discussed in Sec. 3.1, cVAEs jointly optimize the encoder and decoder to maximize the variational lower bound:
L(x,ψ; θ, φ) = Eqφ(z|x,ψ) [log pθ(x|z,ψ)]−KL (qφ(z|x,ψ)‖p(z)) . (6)
We use multivariate Gaussians for the prior, encoder and decoder: p(z) = N (z;0, I), qφ(z|x,ψ) = N (z;µ,σ2I), and pθ(x|z,ψ) = N (x; x̃, αI). Both the encoder and decoder are implemented as neural networks. The encoder network fφ outputs the parameters of the posterior distribution: (µ,σ) = fφ(x,ψ). The decoder network gθ outputs the reconstructed future trajectory x̃:
x̃ = gθ(z,ψ). Detailed network architectures are given in Appendix B.1. Based on the Gaussian parameterization of the cVAE, the objective in Eq. 6 can be rewritten as
Lcvae(x,ψ; θ, φ) = − 1
V V∑ v=1 ‖x̃v − x‖2 + β · 1 Dz Dz∑ j=1 ( 1 + 2 log σj − µ2j − σ2j ) , (7)
where we take V samples from the posterior qφ(z|x,ψ), Dz is the number of latent dimensions, and β = 1/α is a weighting factor. The training procedure for the cVAE is detailed in Alg. 2 (Appendix A). Once the cVAE model is trained, sampling from the learned future trajectory model pθ(x|ψ) is efficient: we can sample a latent code z according to the prior p(z) and use the decoder pθ(x|z,ψ) to decode it into a future trajectory x.
Algorithm 1 Training the diversity sampling function (DSF) Sγ(ψ) 1: Input: Training data {x(i),ψ(i)}Mi=1, cVAE decoder network gθ(z,ψ) 2: Output: DSF Sγ(ψ) 3: Initialize γ randomly 4: while not converged do 5: for each ψ(i) do 6: Generate latent codes Z = {z1, . . . , zN} with the DSF Sγ(ψ) 7: Generate the trajectory ground set Y = {x1, . . . ,xN} with the decoder gθ(z,ψ) 8: Compute the similarity matrix S and quality vector r with Eq. 8 and 9 9: Compute the DPP kernel L(γ) = Diag(r) · S · Diag(r) 10: Calculate the diversity loss Ldiverse 11: Update γ with the gradient∇Ldiverse 12: end for 13: end while

heading: 4.2 DIVERSITY SAMPLING FUNCTION (DSF)
text: As mentioned before, randomly sampling from the learned cVAE model according to the implicit likelihood function pθ(x|ψ), i.e., sampling latent codes from the prior p(z), does not guarantee that the trajectory samples are diverse: major modes (those having more data) with higher likelihood will produce most of the samples while minor modes with lower likelihood will have almost no sample. This prompts us to devise a new sampling strategy that can reliably generate a diverse set of samples covering both major and minor modes. We propose to learn a diversity sampling function (DSF) Sγ(ψ) that maps context ψ to a set of latent codes Z = {z1, . . . , zN}. The DSF is implemented as a γ-parameterized neural network which takes ψ as input and outputs a vector of length N ·Dz (see Appendix B.1 for network details). The latent codes Z are decoded into a diverse set of future trajectories Y = {x1, . . . ,xN}, which are denoted as the DSF trajectory samples. We note that N is the sampling budget. To solve for the parameters of the DSF, we propose a diversity loss based on a DPP defined over Y . In this section, we first describe how the DPP kernel L is defined, which involves the construction of the similarity matrix S and quality vector r. We then discuss how we use the DPP kernel L to formulate a diversity loss to optimize the parameters of the DSF.
Recall that the DPP kernel is defined as L = Diag(r) · S · Diag(r), where r defines the quality of each trajectory and S measures the similarity between two trajectories. The DPP kernel L(γ) is a function of γ as it is defined over the ground set Y output by the DSF Sγ(ψ). Similarity. We measure the similarity Sij between two trajectories xi and xj as
Sij = exp ( −k · d2x(xi,xj) ) , (8)
where dx is the Euclidean distance and k is a scaling factor. This similarity design ensures that 0 ≤ Sij ≤ 1 and Sii = 1. It also makes S positive definite since the Gaussian kernel we use is a positive definite kernel.
Quality. It may be tempting to use p(x|ψ) to define the quality of each trajectory sample. However, this likelihood-based measure will clearly favor major modes that have higher probabilities, making it less likely to generate samples from minor modes. This motivates us to design a quality metric that
treats all modes equally. To this end, unlike the similarity metric which is defined in the trajectory space, the quality of each sample is measured in the latent space and is defined as
ri = { ω, if ‖zi‖ ≤ R ω exp ( −zTi zi +R2 ) , otherwise
(9)
Geometrically, let R be the radius of a sphere Φ containing most samples from the Gaussian prior p(z). We treat samples inside Φ equally and only penalize samples outside Φ. In this way, samples from major modes are not preferred over those from minor modes as long as they are inside Φ, while samples far away from the data manifold are heavily penalized as they are outside Φ. The radius R is determined by where ρ percent of the Gaussian samples lie within, and we set ρ = 90. To compute R, we use the percentage point function of the chi-squared distribution which models the distribution over the sum of squares of independent standard normal variables. The base quality ω is a hyperparameter which we set to 1 during training in our experiments. At test time, we can use a larger ω to encourage the DPP to select more items from the ground set Y . The hyperparameter ρ (or R) allows for the trade-off between diversity and quality. When R is small, the quality metric is reduced to a pure likelihood-based metric (proportional to the latent likelihood), which will prefer samples with high likelihood and result in a less diverse sample set. When R is large, most samples will have the same quality, and the resulting samples will be highly diverse but less likely. In practice, the choice of R should be application dependent, as one could imagine autonomous vehicles would need to consider more diverse scenarios including those less likely ones to ensure robustness. We note that after the diverse samples are obtained, it is possible to reassign the quality score for each sample based on its likelihood to allow users to prioritize more likely samples.
Diversity Loss. To optimize the DSF Sγ(ψ), we need to define a diversity loss that measures the diversity of the trajectory ground set Y generated by Sγ(ψ). An obvious choice for the diversity loss would be the negative log likelihood− logPL(γ)(Y = Y) = − log det(L(γ)) + log det(L(γ) + I). However, there is a problem with directly using the DPP log likelihood. The log likelihood heavily penalizes repeated items: if two trajectories inside Y are very similar, their corresponding rows in L will be almost identical, making det(L(γ)) = λ1λ2 . . . λN ≈ 0 (λn is the n-th eigenvalue). In practice, if the number of modes in the trajectory distribution p(x|ψ) is smaller than |Y|, Y will always have similar trajectories, thus making det(L(γ)) always close to zero. In such cases, optimizing the negative log likelihood causes numerical issues, which is observed in our early experiments.
Instead, the expected cardinality of the DPP is a better measure for the diversity of Y , which is defined as EY ∼PL(γ) [|Y |]. Intuitively, since the DPP discourages selection of similar items, if Y is more diverse, a random subset Y drawn according to the DPP is more likely to select more items from Y , thus having larger cardinality. The expected cardinality can be computed as (Eq. 15 and 34 in Kulesza et al. (2012)):
E[|Y |] = N∑ n=1 λn λn + 1 = tr ( I− (L(γ) + I)−1 ) . (10)
The main advantage of the expected cardinality is that it is well defined even when the ground set Y has duplicated items, since it does not require all eigenvalues of L to be non-zero as the log likelihood does. Thus, our diversity loss is defined as Ldiverse(γ) = −tr ( I− (L(γ) + I)−1 ) . The training procedure for Sγ(ψ) is outlined in Alg. 1. Inference. At test time, given current context ψ,we use the learned DSF Sγ(ψ) to generate the future trajectory ground set Y . In some cases, Y may still contain some trajectories that are similar to others. In order to obtain a diverse set of trajectories without repetition, we aim to perform MAP inference for the DPP to find the most diverse subset Y ∗ = arg maxY ∈Y PL(γ)(Y ). A useful property of DPPs is that the log-probability function is submodular (Gillenwater et al., 2012). Even though submodular maximization is NP-hard, we use a greedy algorithm (Nemhauser et al., 1978) which is a popular optimization procedure that works well in practice. As outlined in Alg. 3, the output set Yf is initialized as ∅, and at each iteration, the trajectory which maximizes the log probability
x∗ = arg max x∈Y\Yf
log det ( LYf∪{x} ) (11)
is added to Yf , until the marginal gain becomes negative or Yf = Y .

heading: 5 EXPERIMENTS
text: The primary focus of our experiments is to answer the following questions: (1) Are trajectory samples generated with our diversity sampling function more diverse than samples from the cVAE and other baselines? (2) How does our method perform on both balanced and imbalanced data? (3) Is our method general enough to perform well on both low-dimensional and high-dimensional tasks?
Metrics. A problem with trajectory forecasting evaluation is that in real data each context ψ(i) usually only has one future trajectory x(i), which means we only have one sample from a multi-modal distribution. Let us consider a scenario of three data examples {x(i),ψ(i)}3i=1 as shown in Fig. 2 (red, purple, blue). The contexts (past trajectories) of the three examples are instances of the same trajectory but they are slightly different due to noise. As these three contexts have the same semantic meaning, they should share the future trajectories, e.g., the purple and blue future trajectories are also valid for the red context. If we evaluate each example (x(i),ψ(i)) only with its own future trajectory x(i), a method
can achieve high scores by only forecasting the mode corresponding to x(i) and dropping other modes. This is undesirable because we want a good method to capture all modes of the future trajectory distribution, not just a single mode. To allow for multi-modal evaluation, we propose collecting multiple future trajectories for each example by clustering examples with similar contexts. Specifically, we augment each data example (x(i),ψ(i)) with a future trajectory set X (i) = {x(j)|‖ψ(j) − ψ(i)‖ ≤ ε, j = 1, . . . ,M} and metrics are calculated based on X (i) instead of x(i), i.e., we compute metrics for each x ∈ X (i) and average the results. We use the following metrics for evaluation: (1) Average Displacement Error (ADE): average mean square error (MSE) over all time steps between the ground truth future trajectory x and the closest sample x̃ in the forecasted set of trajectories Yf . (2) Final Displacement Error (FDE): MSE between the final ground truth position xT and the closest sample’s final position x̃T . (3) Average Self Distance (ASD): average L2 distance over all time steps between a forecasted sample x̃i and its closest neighbor x̃j in Yf . (4) Final Self Distance (FSD): L2 distance between the final position of a sample x̃Ti and its closest neighbor’s final position x̃ T j . The ADE and FDE are common metrics used in prior work on trajectory forecasting (Alahi et al., 2016; Lee et al., 2017; Rhinehart et al., 2018; Gupta et al., 2018). However, these two metrics do not penalize repeated samples. To address this, we introduce two new metrics ASD and FSD to evaluate the similarity between samples in the set of forecasted trajectories. Larger ASD and FSD means the forecasted trajectories are more non-repetitive and diverse.
Baselines. We compare our Diversity Sampler Function (DSF) with the following baselines: (1) cVAE: a method that follows the original sampling scheme of cVAE by sampling latent codes from a Gaussian prior p(z). (2) MCL: an approach that uses multiple choice learning (Lee et al., 2016) to optimize the sampler Sγ(ψ) with the following loss: Lmcl = minx̃∈Y ‖x̃−x‖2, where x is the ground truth future trajectory. (3) R2P2: a method proposed in (Rhinehart et al., 2018) that uses a reparametrized pushforward policy to improve modeling of multi-modal distributions for vehicle trajectories. (4) cGAN: generative adversarial networks (Goodfellow et al., 2014) conditioned on the forecasting context. We implement all baselines using similar networks and perform hyperparameter search for each method for fair comparisons. For methods whose samples are stochastic, we use 10 random seeds and report the average results for all metrics.

heading: 5.1 SYNTHETIC 2D TRAJECTORY DATA
text: We first use synthetic data to evaluate our method’s performance for low-dimensional tasks. We design a virtual 2D traffic scene where a vehicle comes to a crossroad and can choose three different future routes: forward, left, and right. We consider two types of synthetic data: (1) Balanced data, which means the probabilities of the vehicle choosing one of the three routes are the same; (2)
Imbalanced data, where the probabilities of the vehicle going forward, left and right are 0.8, 0.1, 0.1, respectively. We synthesize trajectory data by simulating the vehicle’s behavior and adding Gaussian noise to vehicle velocities. Each data example (x(i),ψ(i)) contains future trajectories of 3 steps and past trajectories of 2 steps. We also add an obstacle map around the current position to the context ψ(i). In total, we have around 1100 training examples and 1000 test examples. Please refer to Appendix B for more implementation details.
Table 1 summarizes the quantitative results for both balanced and imbalanced data when the sampling budget N is 10. We can see that our method DSF outperforms the baselines in all metrics in both test settings. As shown in Fig. 3, our method generates more diverse trajectories and is less affected by the imbalanced data distribution. The trajectory samples of our method are also less repetitive, a feature afforded by our DPP formulation. Fig. 4 shows how ADE changes as a function of the sampling budget N .

heading: 5.2 DIVERSE HUMAN MOTION FORECASTING
text: To further evaluate our method’s performance for more complex and high-dimensional tasks, we apply our method to forecast future human motions (pose sequences). We use motion capture to obtain 10 motion sequences including different types of motions such as walking, turning, jogging, bending, and crouching. Each sequence is about 1 minute long and each pose consists of 59 joint angles. We use past 3 poses
(0.1s) to forecast next 30 poses (1s). There are around 9400 training examples and 2000 test examples where we use different sequences for training and testing. More implementation details can be found in Appendix B.
We present quantitative results in Table 2 and we can see that our approach outperforms other methods in all metrics. As the dynamics model used in R2P2 (Rhinehart et al., 2018) does not generalize well for high-dimensional human motion, we find the model fails to converge and we do not compare with it in this experiment. Fig. 4 shows that our method achieves large improvement when the sampling budget is big (N = 50). We also present qualitative results in Fig. 5, where we show the starting pose and the final pose of all 10 forecasted motion samples for each method. We can clearly
see that our method generates more diverse future human motions than the baselines. Please refer to Appendix C and our video for additional qualitative results.

heading: 5.3 ADDITIONAL EXPERIMENTS WITH DIVERSITY-BASED BASELINES
text: In this section, we perform additional experiments on a large human motion dataset (3.6 million frames), Human3.6M (Ionescu et al., 2013), to evaluate the generalization ability of our approach. We predict future motion of 2 seconds based on observed motion of 0.5 seconds. Please refer to Appendix B.3 for implementation details. We also use a new selection of baselines including several variants of our method (DSF) and the cVAE to validate several design choices of our method, including the choice of the expected cardinality over the negative log likelihood (NLL) of the DPP as the diversity loss. Specifically, we use the following new baselines: (1) DSF-NLL: a variant of DSF that uses NLL as the diversity loss instead of the expected cardinality. (2) DSF-COS: a DSF variant that uses cosine similarity to build the similarity matrix S for the DPP kernel L. (3) DSF-NLL: a variant of the cVAE that samples 100 latent codes and performs DPP MAP inference on the latent codes to obtain a diverse set of latent codes, which are then decoded into trajectory samples.
We present quantitative results in Table 3 when the number of samples N is 10 and 50. The baseline DSF-COS is able to achieve very high diversity (ASD and FSD) but its samples are overly diverse and have poor quality which is indicated by the large ADE and FDE. Compared with DSF-NLL,
our method achieves better diversity (ASD and FSD) and similar ADE and FDE when the number of samples is small (N = 10). For a larger number of samples (N = 50), NLL becomes unstable even with a large (1e-3) added to the diagonal. This behavior of NLL, i.e., stable for small N but unstable for large N , matches our intuition that NLL becomes unstable when samples become similar (as discussed in Sec. 4.2), because when there are more samples, it is easier to have similar samples during the SGD updates of the DSF network. The baseline cVAE-LDPP also performs worse than DSF in all metrics even though it is able to outperfom the cVAE. We believe the reason is that diversity in sample space may not be well reflected in the latent space due to the non-linear mapping from latent codes to samples induced by deep neural networks.

heading: 6 CONCLUSION
text: We proposed a novel forecasting approach using a DSF to optimize over the sample space of a generative model. Our method learns the DSF with a DPP-based diversity measure to generate a diverse set of trajectories. The diversity measure is a novel application of DPPs to optimize a set of items in continuous space. Experiments have shown that our approach can generate more diverse vehicle trajectories and human motions compared to state-of-the-art baseline forecasting approaches.
Acknowledgment. This project was sponsored in part by JST CREST (JPMJCR14E1), NSF NRI (1637927) and IARPA (D17PC00340).

heading: A ALGORITHMS
text: Algorithm 2 Training the cVAE 1: Input: Training data {x(i),ψ(i)}Mi=1 2: Output: cVAE encoder network fφ(x,ψ) and decoder network gθ(z,ψ) 3: Initialize φ and θ randomly 4: while not converged do 5: for each (x(i),ψ(i)) do 6: Compute parameters (µ,σ) of the posterior distribution qφ(z|x,ψ) using fφ(x,ψ) 7: Sample V Gaussian noises { 1, . . . , V } from N (0, I) 8: Transform noises to latent samples from qφ(z|x,ψ): zv = µ+ σ v 9: Decode latent samples into reconstructed trajectories {x̃1, . . . , x̃V } using gθ(z,ψ) 10: Calculate the cVAE loss Lcvae according to Eq. 6 11: Update φ and θ with∇φLcvae and∇θLcvae 12: end for 13: end while
Algorithm 3 Inference with the DSF Sγ(ψ) 1: Input: Context ψ, DSF Sγ(ψ), cVAE decoder network gθ(z,ψ) 2: Output: Forecasted trajectory set Yf 3: Generate latent codes Z = {z1, . . . , zN} with the DSF Sγ(ψ) 4: Generate the trajectory ground set Y = {x1, . . . ,xN} with the decoder gθ(z,ψ) 5: Compute the DPP kernel L = Diag(r) · S · Diag(r) 6: Yf ← ∅, U ← Y 7: while U is not empty do 8: x∗ ← arg maxx∈U log det ( LYf∪{x}
) 9: if log det ( LYf∪{x∗} ) − log det ( LYf ) < 0 then
10: break 11: end if 12: Yf ← Yf ∪ {x∗} 13: U ← U \ {x∗} 14: end while
B IMPLEMENTATION DETAILS
B.1 NETWORK ARCHITECTURES
Synthetic data. Fig. 6 (Top) shows the network architecture for synthetic data. The number of latent dimensions is 2. By default, we use ReLU activation for all networks. The future trajectory x ∈ R3×2 consists of 3 future positions of the vehicle. The context ψ contains past trajectories h ∈ R2×2 of 2 time steps and a obstacle map f ∈ {0, 1}28×28 spanning a 4 × 4 area around the current position of the vehicle (the road width is 2). For the encoder, we use a convolutional neural network (CNN) with three 32-channel convolutional layers to process f . The first two layers have kernel size 4 and stride 2 while the last layer has kernel size 6 and stride 1. The obtained CNN features are concatenated with flattened x and h into a unified feature, which is feed into a multilayer perceptron (MLP). The MLP has one 128-dim hidden layer and two heads outputing the mean µ and variance σ of the latent distribution. For the decoder, we concatenate the CNN feature from f with the latent code z ∈ R2 and flattened h into a unified feature. The feature is passed through an MLP with one 128-dim hidden layer which outputs the reconstructed future trajectory x̃ ∈ R3×2. For the diversity sampler function (DSF), we concatenate the CNN feature from f with the flattened h and pass it through an MLP with one 128-dim hidden layer to obtain a set of latent codes {z1, . . . , zN} which are represented by a vector of length 2N . Human motion. Fig. 6 (Bottom) shows the network architecture for synthetic data. The number of latent dimensions is 8. The future trajectory x ∈ R30×59 consists of future poses of 30 time steps (1s). The context ψ contains past poses h ∈ R3×59 of 3 time steps (0.1s). Each pose consists of 59 joint angles. For the encoder, we use two 128-dim bidirectional LSTMs (Bi-LSTMs) and mean pooling to obtain the temporal features for x and h. We then concatenate the temporal features into a unified feature and feed it into an MLP with two hidden layers (300, 200) and two heads to obtain the mean µ and variance σ of the latent distribution. For the decoder, we reuse the Bi-LSTM of
the encoder for the context h and a 128-dim forward LSTM to decode the future trajectory x̃. At each time step t, the forward LSTM takes as input the previous pose x̃t−1 (hH for t = 0), the latent code z ∈ R8 and the temporal features from h, and outputs a 128-dim feature. The feature is then passed through an MLP with two hidden layers (300, 200) to generate the reconstructed pose x̃t. For the DSF, we use a different 128-dim Bi-LSTM to obtain the temporal feature for h, which is feed into an MLP with a 128-dim hidden layer to produce a set of latent codes {z1, . . . , zN} which are represented by a vector of length 8N .
B.2 TRAINING AND EVALUATION
When training the cVAE model using Eq. 7, we take V = 1 sample from the posterior qφ(z|x,ψ). The weighting factor β for the KL term is set to 0.1 for synthetic data and 1e-4 for human motion. We use Adam (Kingma and Ba, 2014) to jointly optimize the encoder and decoder. The learning rate is set to 1e-4 and we use a mini batch size of 32 for synthetic data. We optimize the model for 500 epochs for synthetic data and 100 epochs for human motion.
When training the DSF, the scale factor k for the similarity matrix S is set to 1 for synthetic data and 1e-2 for human motions. For both synthetic data and human motions, we use Adam with learning rate 1e-4 to optimize the DSF for 20 epochs.
Recall that in the metrics section (Sec. 5.1), we need the grouping threshold ε to build the ground truth future trajectory set X (i) = {x(j)|‖ψ(j) −ψ(i)‖ ≤ ε, j = 1, . . . ,M}. For synthetic data, ε is set to 0.1 and we only use past trajectories h to compute the distance between contexts. For human motion, ε is set to 0.5.
B.3 IMPLEMENTATION DETAILS FOR EXPERIMENTS ON HUMAN3.6M
Following previous work (Martinez et al., 2017; Pavlakos et al., 2017; Pavllo et al., 2019), we convert the motion sequences in the dataset into sequences of 3D joint positions, and adopt a 17-joint skeleton. We train on five subjects (S1, S5, S6, S7, S8), and test on two subjects (S9 and S11).
We use the same network architectures (Fig.6 (Bottom)) in this experiment as the one used in the human motion forecasting experiment above. The number of latent dimensions is 128. When training the cVAE model, the weighting factor β is set to 0.1. We sample 5000 training examples every epoch and optimize the cVAE for 500 epochs using Adam and a learning rate of 1e-4. We set the batch size to 64 for the optimization.
The scale factor k for the similarity matrix S of the DPP kernel is set to 5. When learning the DSF, we use a batch size of 64 and sample 1000 training examples every epoch and optimize the DSF for 20 epochs using Adam and a learning rate of 1e-3.
When computing the metrics, we set the grouping threshold ε to 0.1.

heading: C ADDITIONAL VISUALIZATION
text: We also show additional qualitative results for human motion forecasting in Fig. 7. The quality and diversity of the forecasted motions are best seen in our video2.
2https://youtu.be/5i71SU IdS4

Review summaries:
This paper presents a novel approach for forecasting object trajectories (e.g., predicted paths of vehicles) forcing diversity of outputs. The authors adopt determinantal point processes (DPPs) to capture the diversity and propose a diversity sampling function (DSF) which consists of a neural network. Its trainable parameter (i.e., \gamma) maps the past trajectory into a set of latent codes and they are decoded to feasible trajectories by a pre-trained conditional variational autoencoder (cVAE). The DSF is trained by maximizing the diversity of the output trajectory. But, since the standard log-likelihood function can be singular, they additionally present an objective function for diversity by maximizing the expected cardinality, which admits replicated outputs. In experiments, the proposed method finds more diverse paths than other competitors under both for synthetic 2D objects and human motions.