{'fraction_non_alphanumeric': 0.031508165225744476, 'fraction_numerical': 0.011207172590457892, 'mean_word_length': 4.671145814418013, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Convex Online Video Frame Subset Selection using Multiple Criteria for Data Efficient Autonomous Driving

Training vision-based Urban Autonomous driving models is a challenging problem, which is highly researched in recent times. Training such models is a data-intensive task requiring the storage and processing of vast volumes of (possibly redundant) driving video data. In this paper, we study the problem of developing data-efficient autonomous driving systems. In this context, we study the problem of multi-criteria online video frame subset selection. We study convex optimization-based solutions and show that they are unable to provide solutions with high weightage to the loss of selected video frames. We design a novel convex optimization-based multi-criteria online subset selection algorithm that uses a thresholded concave function of selection variables. We also propose and study a submodular optimization-based algorithm. Extensive experiments using the driving simulator CARLA show that we are able to drop 80% of the frames while succeeding to complete 100% of the episodes w.r.t. the model trained on 100% data, in the most difficult task of taking turns. This results in a training time of less than 30% compared to training on the whole dataset. We also perform detailed experiments on prediction performances of various affordances used by the Conditional Affordance Learning (CAL) model and show that our subset selection improves performance on the crucial affordance"Relative Angle"during turns.


Introduction
Many A.I. applications, including autonomous driving systems [19,10], process large amount of video data for training complex deep learning models. However, much of the input video contains redundant information from the task point of view. For example, in case of autonomous driving, training using many frames on straight road sections may not be necessary; while one may need a lot of frames in the turns for training. In this paper, we study the problem of selecting video frame subsets, which are most informative as training data for one or more such tasks. We are also interested in developing a selection algorithm that can be deployed on edge devices, thus minimizing edge to core transfer.
Autonomous driving models typically involve multiple prediction tasks, e.g. prediction of 6 affordances in conditional affordance learning (CAL) model [19]. The importance of prediction accuracy of a particular task towards the end objective is a complex function of the situation. For example, we find that error in prediction of relative angle during the turns is critical towards achieving higher episode completion, since the vehicle is able to easily recover from such errors during straight stretches. Hence, we are interested in designing a video frame subset selection algorithm which is able to incorporate multiple criteria arising from the different tasks, situations (e.g. turns, presence of pedestrians, etc) and existing model properties (e.g. prediction loss).
The problem of video frame subset selection has been studied in various contexts, including video summarization [11,16], video recognition [23], video fast forwarding [14], etc. Broadly, the techniques can be classified into two classes: (1) deep reinforcement learning based methods, which learn a frame skipping network, with reward for better performance [14,22], or more confidence [23] on the end task; and (2) external criteria based methods which optimize a global criterion between selected frames and whole video, e.g. perceptual similarity [11], manifold spanning [13], etc. For our setting, the first class of methods are too expensive, since they require multiple evaluations of the end task objective, which in our case is the fraction of test episodes completed.
In this paper, we build on the online subset selection framework [11], where at each step, an existing set of selected frames is supplemented by the most relevant frames from an incoming set, based on the total dissimilarity between selected frames and incoming frames. This framework was extended to incorporate pointwise loss of the selected frames in a composite criteria [8]. These techniques were applied to video summarization [11] and semantic segmention [8]. To the best of our knowledge, these techniques have not been used in the autonomous driving setting. Moreover, through a rigorous analysis, we show that, the additive incorporation of pointwise loss criteria in [8] suffers from selection of fewer frames from incoming set as we provide higher weightage to the pointwise criteria. This is due to the fact that additive incorporation suffers from multiple counting of loss of selected points thus leading to selection of fewer frames. We propose a novel thresholded formulation (ThreshMCOSS) of incorporation of pointwise criteria, which leads to a convex selection objective leading to efficient algorithm.
We also propose a natural set-function based criteria for incorporation of pointwise multiple criteria, which is also shown to be a sub-modular function, thus opening up the possiblity of using approximate submodular optimization algorithms. In an thorough empirical study, we show that both on synthetic data, as well as data from selection of video frames for autonomous driving, the convex relaxation based algorithm performs better than state of the approximations algorithms for submodular maximization [3,4].
We perform the autonomous driving experiments by training on a dataset of more than 100,000 video frames collected from our testbed of CARLA simulator [10], and testing on 40 episodes of from 4 different settings, with more than 6000 video frames. Through extensive experimentation, we find that bucketwise relative angle loss as a good criteria along with total multi-task loss and SIFT similarity between pairs of frames provides an ideal selection criteria. Our experiments using the CAL model [19], show that we can achieve a 100:20 compression (selecting 1 in 5 frames) which does not lead to any loss in episode completion, even though the accuracies on individual tasks decrease marginally.

Related Work
We describe two broad classes of relevant prior works: (a) Learning model for self driving cars, and (b) Subset selection. The autonomous driving literature has witnessed many different kinds of learning approaches: (1) modular pipeline or mediated perception [10] [24], and reinforcement learning [10] [15] [18]. Deep Imitation Learning based method Conditional Affordance Learning (CAL) [19] learns models for multiple affordances in a multi-task setting, using driving video data collected from the driving simulator CARLA [10]. It claims better episode completion over other imitation learning based approaches e.g. CARLA [10] or conditional imitation learning [7]. Hence, in this work we demonstrate effectiveness of our frame subset selection algorithms using CAL as the learning model with driving simulator CARLA [10]. However, our approach is complementary to recent reinforcement learning based approaches e.g. [18], as discussed in section 2. Video frame subset selection: Recent online subset selection approaches can be divided into two broad classes (1) deep learning based, and (2) based on optimization of some input criteria. The first class of techniques [14], [22] [23] depend on selection networks added to the pipeline of existing tasks and are trained jointly. They are able to learn complex selection criteria through deep models, but do not come with any stated selection criteria, w.r.t. which the selection is optimal. These methods are jointly trained with the end objective, e.g. video recognition for [22] and [23], and are typically too expensive to be deployed on edge devices.
The second class of techniques, which are also closest to us, selects the data points based on different defined criteria. These criteria include reconstruction error [6], linear dependency [13], perceptual similarity [11] or criteria based on end tasks such as distinctiveness and uncertainty [12] [8]. [13] recently proposed an online approach based on linear dependence criteria. However for the current problem, we build on the pairwise criteria based approach proposed in [11], and extended to include multiple pairwise and pointwise criteria [8]. While these approaches were used for the problems of Video summrization [11] and semantic segmentation [8], their setting provides flexibility of incorporating multiple different types of criteria, which is relevant to our application. We provide detailed comparison with these approaches.

Data Efficient Autonomous Driving
In this section, we describe the problem of data efficient training of autonomous driving models, with the core idea being selection of relevant video segments in an online setting. We formulate this problem as an online subset selec-tion problem (OSS) for selecting subsets of video frames, given input signals from existing selected video frames, and the trained model, which throw up multiple input criteriaboth for pairs of input frames and for single input frame. Section 2.1 describes the setup of data efficient autonomous driving and its connection to multi-criteria OSS problem formulation. Section 2.2 points out a drawback with existing multi-criteria OSS formulation. Sections 2.3 and 2.4 describe our new formulations for the multi-criteria OSS problem.

Problem setup and OSS
Training of vision based autonomous driving models [19,18] requires processing of large amounts of annotated video data. In many cases, the videos are collected in episodes over a period of time, leading to processing and training of models in batches which are ordered in time. Hence, the batchwise OSS scheme discussed in [11], is an ideal setting for selection of video frames in this context. We denote a complete dataset as D = {(x i , y i ), i = 1, . . . , n} where n is the total number of datapoints (annotated video frames) in the dataset, x i are the features extracted from video frames, and labels y i corresponding to various learning tasks, e.g. affordances [19]. Let X t = {(x i , y i ), i = 1, . . . , m}, t = 1, . . . , T denote the t th batch of episodes collected, where m denotes the number frames in a batch 1 . Hence mT = n. We also define the cumulative sets C t = ∪ t i=1 X i denoting all data collected till batch t. We are interested in constructing representative set R t ⊆ C t , which consists of a representative set of frames till batch t. The intention here is that an autonomous driving model M t trained on the cummulative set C t , should perform similarly to another model M t trained on the representative set of frames R t in terms of an end performance metric, e.g. the episode completion metric used in [19]. Furthermore, the size of R t should be small so that R t uses lower storage space and communication bandwidth, and training of M t potentially takes lower time. An algorithm for selection of R t+1 from X t+1 , given C t , and M t thus constitutes a data efficient scheme for training of autonomous driving models, since we are only storing and processing R t 's. Note that, this scheme can also be used in the reinforcement learning schemes for improvement of driving policies such as the one described in [18], where X t can be taken from the replay buffer at iteration t.
For the OSS formulation, we focus on an input batch of episodes X t+1 . The selection algorithm uses two input sets of frames R t and X t+1 , here referred to as the old set (superscript o) and new set (superscript n) respectively, following notation used in [11]. Let d o ij denote a dissimilarity measure between new frame i (from X t+1 ) and old frame j (from R t ), and d n ij denote the dissimilarity between 1 Equal batch size is for simplicity of exposition, not a requirement new frames i and j (both from X t+1 ). The OSS formulation minimizes the a composite criteria with two parts: (1) total dissimilarity between the "representative frames" (either from new or old set) and the incoming frame it represents, and (2) number of representative frames from the new set. Let z o ij , z n ij be the relaxed binary assignment variables Hence any solution for optimal representative allocation should satisfy the constraint: asserting that every frame i ∈ X t+1 has exactly one representative. The objective function can be written as: Das et al. [8] has incorporated both pairwise scores (e.g. distance d ij between pairs of frames i, j) and pointwise scores (e.g. negative loss −L i for the frame i). The modified cumulative dissimilarity function Q ij is a weighted sum of d ij and L j -the loss incurred by the representative point.
Let L n i denote the pointwise attribute (here loss value) for datapoint i in X t+1 and analogously for L o i (denoting loss for datapoint i in R t ). The final formulation is: j . This is a convex optimization problem which can be solved efficiently for moderate sizes of sets X t+1 and R t using off the shelve solvers, e.g. CVXPY [9]. We call this formulation multi-critria OSS (MCOSS).

Analysis of Multi-Criteria OSS
While applying MCOSS to our problem, we noticed that as we give higher weightage to the pointwise component by choosing lower value of ρ, the number of selected points decreases. From an application point of view, this allows the pointwise score to have a limited impact on the set of points selected. This might be tolerable in certain applications, e.g. semantic segmentation where the perceptual dissimilarity measure contains sufficient information for frame subset selection. However for the application of autonomous driving, we find that task-wise and situation-wise losses have much more impact on the quality of frames selected.
To understand the mechanism through which this problem arises, we observe that using only pointwise metric yields a maximum of one representative for all images belonging to incoming set X t+1 . This is the setting when ρ = 0. We have in which case only one point will be selected (see Corollary 1.1). Otherwise the representative will be from R t , in which case no points are selected.
While the above intuitions are motivated for special case of ρ = 0, the ideas also apply to more general values of 0 < ρ ≤ 1. We further illustrate this by characterising the solution of formulation 1 in the following theorem.
Theorem 1 Let z o ij and z n ij be the optimal solution for formulation 1. A new frame j ∈ X t+1 is selected as a representative frame for at least one incoming frame i ∈ X t+1 , i.e. z n ij = 1, only if the following conditions hold: Due to space constraints, we provide the formal proof in the supplementary material. Note that the first condition states that there is at least one frame i in the incoming set whose cumulative dissimilarity Q n ij is lower than all other points. The second condition signifies that cumulative dissimilarity Q n ij between a representative j and the point it is representing i is lower than minimal contribution from a potential representative k from existing set of selected examples k ∈ R t . Next, we provide two corollaries to illustrate our point. Corollary 1.1 illustrates the conditions in theorem 1 for the special case of ρ = 0. Since, the dependence on i is removed, it is easy to see that at most one j ∈ X t+1 will satisfy the condition.
ij and z n ij be the optimal solution for formulation 1. A new frame j ∈ X t+1 is selected as a representative frame for at least one incoming frame i ∈ X t+1 , i.e. z n ij = 1, only if the following conditions hold: • L n j > L n j for all j ∈ X t+1 and j = j ij , z o ij , and for ρ = 0, j ∈ X t+1 is not a representative frame, then for some ρ ≥ 0, theorem 1 will not be satisfied by any pair i, j ∈ X t+1 . Corollary 1.2 states that if a frame j ∈ X t+1 is not a representative, and satisfies the conditions on ∆ d (i, j) and ∆ L (j), then it will stop being a representative for some value of ρ ≥ 0. By rearranging the terms in second condition of theorem 1, we get: Hence the second condition of theorem 1 is not satisfied by any i ∈ X t+1 for the given candidate representative frame j ∈ X t+1 . These results motivate us to look for better formulations of multi-criteria OSS problem.

Submodular Multi-Criteria OSS
In this section, we describe an algorithm for multicriteria OSS problem based on submodular optimization. The problem can be posed as a set function incorporating both pairwise and pointwise attributes and can be solved using submodular optimisation. The natural criteria used for selection is the pre-defined modified cumulative dissimilarity function Q ij .
For every set S, the set function f (S) can be defined as: Here, the problem is solved by selecting a representative j which contributes the least dissimilarity value Q ij to the incoming instances i ∈ X. By definition, we can say Remark 1 -f(S) is submodular.
For proof, see Supplementary. We can thus pose it as a submodular maximisation problem by solving the problem min S⊆X f (S). We call this formulation submodular multicriteria OSS (SubMCOSS). We define a greedy submodular maximisation approach for solving the optimisation problem in Algorithm 1. The algorithm is a randomised greedy algorithm that examines the dataset k times to select the representatives for the incoming data. Next, we show a thresholded convex approach for solving the multi-criteria OSS problem.

Thresholded Convex multi-criteria OSS
SubMCOSS , described in previous section uses the natural formulation of weighted linear aggregation of pointwise and pairwise loss function. However, the algorithm for submodular optimization is a randomized approximation algorithm, and also computationally expensive due to multiple sampling runs required for a good optimal subset (see for each x ∈ X \S i−1 do 10: f The key observation which helps us in designing the novel algorithm is that in MCOSS (equation 1) it is possible for a frame j ∈ X t+1 to contribute −m(1 − ρ)L n j by becoming a representative for every point i ∈ X t+1 (see that the terms involving pointwise loss add up to −(1 − ρ)( m i=1 z n ij )L n j ). However, in reality it only adds one data point to the training set with the pointwise score of −L n j . This problem is alleviated by using a coefficient of L n j which is an indicator of whether j is a representative point or not, rather than ( m i=1 z n ij which counts the number of points represented by j. This is achieved by using a concave function S j of z ij : where is an input parameter. The modified objective function becomes: . Note that G is a convex function of z o ij , z n ij since S is a concave function. Also note that , each potential representative j ∈ X t+1 can contribute a maximum of its own pointwise score L j , since S j can take a maximum value of 1. Another drawback of MCOSS (equation 1) is that compression ratio has no direct relation with the parameter λ. We use a constraint based cardinality criteria in order to have more precise control over the number of representative selected. The user provided parameter frac specifies and upper bound over the fraction of incoming frames to be selected as representatives. Overcoming these drawbacks our final convex optimisation based multi-criteria OSS problem formulation is: This can be efficiently solved using any convex solver, e.g. CVXPY [9]. We call this formulation thresholded multi-criteria OSS (ThreshMCOSS). is a user input which is designed to be the maximum value taken by the variable i z ij , when none of the z ij denote a representative relation to be true. In an ideal situation (when we achieve a {0, 1} solution to z ij ), any positive value for is sufficient. In practise, we set to a value less than 1, e.g. = 0.9. Next, we experimentally demonstrate the utility of our method.

Experiments
In this section, we provide our experimental setup by describing the dataset and the subset selection methods. We then show a comparison of approximate online subset selection methods over synthetic data and collected driving data from the CARLA simulator [10]. Next, we compare the performance of various subset selection methods in the autonomous driving application from two aspects: episode completion and affordance prediction.

Experimental Setup Dataset:
We use the open-source driving simulator CARLA [10] for generating our driving dataset. We collect the training data by driving the agent vehicle using the CAL controller [19] with the ground truth affordances as input. The collected data comprises of 262 driving episodes and with a total of 100,000 video frames. For each video frame, we collect: (1) front center camera image, and (2) six affordances (Discrete: Red Light, Hazard Stop, Speed Sign ; Continuous: Relative Angle, Centerline Distance, Vehicle Distance) [19]. We used approximately 85% of the video frames as the training data, and the remaining as test set. Subset selection on Autonomous Driving: We use Conditional Affordance Learning [19] (CAL) model as the driving model. We carry out training on NVIDIA Tesla P100 for 50 epochs using Adam Optimizer with learning rate varying between 10 −3 to 10 −4 . We use SIFT dissimilarity as the pairwise metric (d ij ) for all selection methods and two variations of losses (L j ) as pointwise metric -total loss (TL), bucket specific relative angle loss aided with other multi-task losses (BML). We observe that among all 6 affordances, relative angle which provides the steering angle of the car, is the most essential affordance for episode completion.So,for pointwise metric, we provide the highest weightage to the losses corresponding to buckets of relative angle meant for turns and intersection, followed by the other affordances. We report results with the following methods of selection for compression ratios 100:20 and 100:7: Subset selection and Training Times: Table 1 shows the amount of total time taken for training and subset selection for each compression ratio. Compression ratio of 100:20 takes about 1/3rd the total time taken to train the whole set (WS). This follows for the other compression ratio too and hence saves both time and space, essential in the current IoT setting with massively huge data.
Metrics reported: We have reported metrics for the two subtasks: episode completion and affordance accuracies. An episode corresponds to a source-destination pair provided to the agent vehicle. The episode completion is measured in terms of number of successfully completed episodes. The accuracies of discrete affordances are measured in terms of Micro Accuracy (MIC) and Macro Accuracy (MAC), while the continuous affordances are measured in terms of Mean Absolute Error (MAE).
Affordance Selection: We have reported results for five affordances -Red light, Hazard Stop, Relative Angle, Centerline Distance and Vehicle Distance. Considering the setup of our dataset collection, from Figure 1, we can observe that the two affordances Speed Sign and Hazard Stop suffer from class imbalance. Alongside, prediction accuracy of Speed Sign does not have an impact on episode completion. Hence, we refrain from reporting its accuracy. In this section, we compare the optimal subsets reported by the baseline method [8], submodular method and the proposed convex optimization based method in terms of final objective function values. Figure 2a shows the objective function values for the three approaches, for 10 randomly synthesized problem instances (d matrix of dimension 100 × 100 and L vector of dimension 100). For the submodular method, we report a box plot of results over 100 runs of the algorithm to capture the randomness. While all three methods find approximate solutions, the proposed convex method consistently finds lower values of objective function, followed by [8], and submodular optimization. For real data (CARLA data for our further experiments), we report the same in Figure 2b , for 10 episodes in our collected data. We can clearly observe that function values attained by our proposed method lies below that of the other approximate methods, thus proving our method to be an efficient approach.

Comparison of approximate online subset selection methods
Next, we discuss the application of the subset selection methods on autonomous driving.

Comparison of Methods: Episode Completion
In this section, we will study the performance of different subset selection techniques on the basis of episode completion which is the main intended objective.
We consider four tasks under episode completion which had been originally defined in [10] We show in Table 2 the performance of CAL model [19] trained on subsets, obtained by various selection techniques, by simulating it with the CARLA [10] simulator.
We report number of successfully completed episodes (out of a total of 10 episodes) for each subtask in training and test conditions. We observe that the tasks -Straight and Straight Dynamic are fairly easy to accomplish for all subset selection methods. The challenge arises in the other two tasks where we see a large number of unsuccessful episodes.
The completion of episodes in turns, largely depends on the affordance Relative Angle which as we mentioned, provides the steering angle of the agent vehicle. We observe that Uniform Skip (US) is unable to complete majority of the turns in training or test conditions. This is due to the inherent nature of selection of US method, which does not take the important frame sequences into consideration.
On the other hand, OS, OL, MCOSS, SBML complete some of the turn episodes, with TCBML completing the highest of all methods (100% both in training and test conditions) followed by TCTL. This is due to the efficient usage of combination of pointwise metric along with pairwise metric in the selection of instances. We also report the episode completion numbers for 100:7 compression ratio in Table 2, for MCOSS and SBML and the thresholded convex methods. We can observe that TCTL and TCBML continue to perform better compared to the other baselines with TCBML completing 80% and 90% episodes in training and test conditions even after dropping 93% of the frames.
We show an anecdotal example of a failed episode from MCOSS [8] method in Figure 3 and try to analyse the reason behind it. In Figure 3, we firstly show a plot of an episode with distance covered vs Relative Angle affordance. The cumulative distance is chosen as an axis of reference in order to make the comparison spatially similar for all the methods. Overall, the agent vehicle in the simulator is resilient to errors. However, we can observe the gradual deviation of MCOSS [8] method and its accumulated errors which lead to an incomplete episode. We can also relate the region of failures to the corresponding relative angle errors in Figure 3 (middle) where we observe that overall, MCOSS [8] is having a higher error compared to proposed method TCBML and model trained on WS. We also show the fraction of selected instances by both the selection methods, in Figure 3 (right) from the same region, and we can observe that TCBML selects more fraction of instances in the area right before the turn and during the turn, which eventually help in its completion. We discuss the next subtask -affordance prediction in the following subsection.

Comparison of Methods: Affordance Accuracies
In this section, we will study the performance of different subset selection methods on the basis of their performance in affordance predictions.
We show in Table 3 the performance of CAL [19] driving model for four affordances, on subsets obtained by different subset selection techniques for 100:20 compression ratio. We also show the % difference in performance of our proposed method TCBML with that of WS. We notice that all the methods can classify the affordances reasonably well for both red light and hazard stop affordance. This is due to weighted cross-entropy losses used for the large number of imbalanced classes as seen initially in Figure 1. We can also see that TCTL and TCBML outperform all other methods in predicting vehicle distance affordance. In case of centerline distance, all the methods work similarly with OS and OL performing the worst.
In case of Relative Angle affordance, we have grouped the values into three different buckets meant for Left Turn, Straight Road, Right Turn. We observe in Figure 4 that the MAE for straight road buckets for all selection methods are very low in range. This is essentially due to the skewness in Relative Angle affordance. However, TCTL and TCBML outperform all other methods in turn buckets which have in usual, lesser number of datapoints. We can  also observe that TCBML selects more fraction of instances for both Left and Right turns while relaxes comparatively in the Straight Road. SBML also has close fraction of instances to TCBML for left turn, however it drops down in the fraction of right turns. The difference in MAE becomes more evident with increase in compression ratio. We have added the result for 100:7 in the Supplementary. This is indicative of the fact that the proposed thresholded convex method gives more importance to the frames which are non-redundant and also having higher losses, thus leading to better performance. Thus, we can clearly see that our proposed methods TCTL and TCBML are performing better quantitatively in terms of affordance predictions and qualitatively in terms of deployment of the model.

Conclusion
In this paper, we propose a novel thresholded convex optimisation based online video frame subset selection technique involving pairwise and pointwise similarity for optimal learning for the task of self-driving. We also propose a natural set-function based criteria to incorporate pointwise criteria using submodular optimisation. We show the effectiveness of our improved subset selection method (TCBML and TCTL) in the aspect of episode completion and affordance predictions. We did extensive experiments to show that even after dropping 80% of frames, we succeed in completing all the episodes involving the difficult task of turns.
A new point j from the set X t+1 is selected as a representative by minimizing the above function, only if all of the following hold: Proof: The condition for the function value of a representative to be low holds true here similarly. The first condition states that a new frame j ∈ X t+1 is termed as a representative if its total contribution value towards the set of incoming frames is ≥ . The second condition states that an element can be a representative from X t+1 if its cost is atmost max(|d o ik − d n ij |, |L o k − L n j |) times higher than the best representative from the existing set R t (k = argmin j m i=1 z o i,j Q o i,j ).

Comparison of methods: Relative Angle affordance for 100:7 compression ratio
We draw a comparison among the subset selection methods on the basis of prediction of the affordance 'Relative Angle' for the compression ratio 100:7.
We can clearly observe that the proposed methods CTL and CBML have a lower Mean Absolute Error (MAE) compared to MCL and SBML. This is essentially due to the effective selection of significant instances which help in better prediction of relative angle values.