Mel-Weighted Single Frequency Filtering Spectrogram for Dialect Identification

In this study, we propose Mel-weighted single frequency filtering (SFF) spectrograms for dialect identification. The spectrum derived using SFF has high spectral resolution for harmonics and resonances while simultaneously maintaining good time-resolution of some speech excitation features such as impulse-like events. The SFF spectrum can represent speech characteristics such as burst time and glottal closure instances better than the short-time Fourier transform (STFT) spectrum. Our hypothesis is that these intricate representations in the SFF spectrum should help in distinguishing dialects. Therefore, we built a dialect identification system which uses an unsupervised, bottleneck feature representation of the Mel-weighted SFF spectrogram (Mel-SFF spectrogram) with sequence-to-sequence deep autoencoders. The language invariance of the proposed system was evaluated using two datasets: the UT-Podcast database (English) and the STYRIALECT database (German). The proposed representations gave a relative improvement of 9.47% and 4.69% in unweighted average recall (UAR) compared to the best baseline method on the development and test datasets, respectively, of the UT-Podcast database. The proposed representations also gave a comparable performance to the best baseline method for the STYRIALECT database. In addition, the fusion of the autoencoder bottleneck features computed from the Mel-SFF and Mel-STFT spectrograms improved the overall performance indicating complementary information between these features. By further analyzing the performance of the proposed representation with different utterance lengths using the UT-Podcast database, we observed that the proposed representation performed better on short utterances. The improved performance given by the Mel-weighted SFF spectrogram for recognizing dialects in both databases supports our hypothesis.

I. INTRODUCTION
In listening to speech, humans not only analyse the speech signal's linguistic content but they also make conclusions about the speaker's regional origin, social background and emotional state. Dialect identification refers to a research area where the goal is to find the regional origin of the speaker using the temporal and spectral characteristics of his or her speech signal. Each dialect group has its own pronunciation pattern and vocabulary compared to other dialect groups. These variations in speech due to dialect have been shown The associate editor coordinating the review of this manuscript and approving it for publication was Jing Liang .
to decrease the performance of automatic speech recognition (ASR) systems. An efficient dialect identification system followed by a dialect-specific pronunciation dictionary and a dialect-specific language model can improve the performance of ASR [1]- [3]. In addition, dialect information can be used in speaker profiling in biometrical applications, it can help solve dialect related issues in speaker and language identification, and it can also be used in the development of dialect-personalized voice assistants.
Dialect identification studies in the literature can be classified into two groups: text-dependent and text-independent [4]. In the former, the transcription of an utterance for which the dialect needs to be identified should be known apriori. VOLUME 8, 2020 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ FIGURE 1. Block diagram describing the steps involved in the single frequency filtering (SFF) method [33].
The dialect is determined by finding the closest dialect match for a word/utterance by either phone modeling or word modeling. Phone/word sequences are modeled using n-gram models. For the dialect identification task, different phone modeling approaches are widely used and they include phone recognition followed by language modeling (PRLM) and parallel phone recognition followed by language modeling (PPRLM) [5]- [8].
Dialect identification studies belonging to the second class, text-independent dialect identification, model dialectal variations using acoustic features derived from speech signals [9]- [13]. The acoustic features used in this area include shifted delta cepstral coefficients (SDCs) [14], prosody based features, frame-by-frame phone posteriors, supervectors [15]- [17], and i-vectors obtained from acoustic features and speech attributes [18]- [21]. In one of the recent studies in language identification, bottleneck features (BNFs) derived from a pre-trained deep neural network with i-vector modeling showed significant improvement over the SDC features, and the developed BNF-based system stands out as state of the art [22], [23]. A shortcoming of this approach is that the deep neural network had to be trained over a transcribed corpus which contains only English speech without phonetic variations in pronunciation [24].
This article studies text-independent dialect identification without taking advantage of any pre-trained models or transcriptions. The proposed system takes advantage of an autoencoder which is trained using the Mel-weighted single frequency filtering (Mel-SFF) spectrogram to obtain BNFs which are used in the classification. A baseline system with a similar architecture is trained using the Mel-weighted short-time Fourier transform (Mel-STFT) spectrogram. The autoencoder architecture used is similar to the one developed in [25], [26]. This autoencoder model converts a variable-length feature vector to a fixed-length representation in an unsupervised manner. This architecture was chosen in the current study because it was shown in [25] to be the best performing system in dialect classification compared to two reference techniques. The spectrum computed by single frequency filtering (SFF) has been shown to give good spectral resolution to indicate harmonics and resonances [27] and good temporal resolution to model speech excitation features such as impulse-like events [28]. The SFF spectrum has also shown promising performance in determining burst-onset points related to voice-onset time (VOT) and glottal closure instances compared to the short-time Fourier transform (STFT) spectrum [28]- [30]. Previous studies in dialect identification have shown the significance of VOT for identification of accent [31]. Inspired by this, we propose to use the Mel-weighted SFF spectrogram with autoencoders to derive fixed-length speech representations for dialect identification.
The organization of the paper is as follows: Section II describes the SFF method and the computation of the Mel-weighted SFF spectrogram. Section III provides a detailed description of the proposed dialect identification system. The experimental setup is described in Section IV. Results are presented in Section V. Finally, Section VI summarizes the study.

II. SFF AND COMPUTATION OF THE MEL-WEIGHTED SFF SPECTROGRAM
This section describes the steps involved in the SFF method and in the computation of the Mel-weighted SFF spectrogram.

A. SFF
The SFF method is used to derive the amplitude envelope of the speech signal at every sample for a given frequency [32]. The SFF spectrum has been shown to be useful in finding burst-onset points [29] and glottal closure instants [30], and it has been demonstrated to exhibit high spectral resolution for important speech features such as harmonics and resonances [27].
In SFF, the pre-emphasized speech signal is used for deriving the amplitude envelope at each frequency by frequency-shifting the signal and by filtering it using a single-pole filter as shown in Figure 1. The pole of the filter is located on the negative real axis close to the unit circle in the z-plane, i.e., the angle of the pole corresponds to the Nyquist frequency ( fs 2 ). Therefore, the effect of other frequency components will be reduced giving high spectral resolution. The steps to derive the SFF spectrum are given below [32].
• Speech signal (s[n]) is pre-emphasized to remove low-frequency variations. The pre-emphasis is computed as follows where α is set to 0.95 in the present study.  • The pre-emphasized speech signal x[n] is multiplied by complex sinusoid e jω k n as follows whereω k = π − 2πf k f s , f k is the desired frequency and f s is the sampling frequency.
• Signal x k [n] is passed through a single-pole filter. The transfer function of the filter is defined as where r ≈ 1, i.e., the pole is close to the unit circle on the negative real axis in the z-plane. In this study, r is set to 0.99.
• The output of the filter is given by • The amplitude envelope (v k [n]) of the signal with the desired frequency f k is given by where y kr [n] and y ki [n] are the real and imaginary parts of y k [n]. The amplitude envelope can be computed for several frequencies using a frequency interval ( f ) as follows 2048 . From the amplitude envelope v k [n], the SFF spectrum of the signal is obtained at each instant of time.

B. COMPUTATION OF THE MEL-WEIGHTED SFF SPECTROGRAM
This section describes the computation of the Mel-weighted SFF spectrogram. The procedure, depicted in Figure 2, consists of the extraction of the filter-bank energies obtained by filtering the SFF spectrum with triangular Mel-spaced filters followed by logarithm. The resulting Mel-filter bank energies (MFBE) are referred to as MFBE-SFF or simply as the Mel-weighted SFF spectrum. For convenience, we refer to the spectrogram obtained by using this process as the Mel-weighted SFF spectrogram or Mel-SFF spectrogram.
As explained in Section II-A, SFF provides the spectrum at each instant of time. Instead of considering the spectrum at each time instant, computational load is reduced in the current study by considering the spectrum unchanged in a segment of T ms. One of the following four approaches can be used in defining the spectrum using the segment of T ms. (a) Average SFF spectrum (S avg ): In this approach, the SFF spectrum is computed by averaging the amplitude envelope v k [n] defined in Eq. 5 for every frequency k over the entire segment. (b) Minimum SFF spectrum (S min ): In this approach, the SFF spectrum is selected as the instantaneous spectrum of v k [n] which shows the minimum spectral energy (sum of the squared amplitude envelope values) over the entire segment. (c) Maximum SFF spectrum (S max ): In this approach, the SFF spectrum is selected as the instantaneous spectrum of v k [n] which shows the maximum spectral energy over the entire segment. (d) Uniform SFF spectrum (S uniform ): In this approach, the SFF spectrum is computed by sampling v k [n] at regular intervals defined by the segment duration. The performance of the above four approaches was compared in this study. As will be reported in Section V, it was observed that S avg gave the best performance. Therefore, the Mel-SFF spectrogram computed using S avg was used as a spectral representation of speech and this representation was further processed in an unsupervised manner by an autoencoder to obtain fixed-sized BNFs to be used in dialect identification.

III. PROPOSED SYSTEM
The proposed system has three stages: the Mel-SFF spectrogram extraction, obtaining an unsupervised representation from spectrograms using an autoencoder and classification. The block diagram shown in Figure 3 describes the proposed system architecture. For convenience, we refer to the unsupervised representation from the STFT spectrogram as VOLUME 8, 2020  In addition, we also studied a system using feature fusion where the unsupervised representations (BNFs) derived from Mel-SFF spectrograms (BNF Mel-SFF ) were combined with the unsupervised representations (BNFs) derived from conventional Mel-STFT spectrograms (BNF Mel-STFT ). The fusion system, depicted in Figure 4, is discussed in Section III-C.

A. MEL-SFF SPECTROGRAM CONFIGURATION
The time-domain speech signal is processed as described by Eqs. 1-5 in Section II to compute the SFF spectrogram. Instead of considering the spectrum at every sample, averaging of the spectrogram is computed as explained in Section II-B. We varied the average energy operation (S avg explained in Section II-B) by considering seven values of T (6.25 ms, 12.5 ms, 18.75 ms, 25 ms, 31.25 ms, 37.5 ms, 43.75 ms). The best performance was obtained with T = 37.5 ms. Therefore, this segment duration value is used throughout this study unless otherwise mentioned. Mel-filter bank energies are obtained from the spectrum using linearly spaced 128 filters in the Mel-scale. To eliminate the effect of background noise, the spectral values are clipped using a threshold as in [25]. In this study, five thresholds (−30 dB, −40 dB, −50 dB, −60 dB, and −70 dB) are explored. Spectrograms are normalized to be in the range of [−1, 1] to match with the decoder output function in the autoencoder. The clipping and normalization operations are conducted in the same way in computing the proposed Mel-SFF spectrogram and in computing its reference spectrogram, the conventional Mel-STFT spectrogram.

B. SEQUENCE-TO-SEQUENCE AUTOENCODERS
Sequence-to-sequence autoencoders compress high-dimensional frame-level representations to low-dimensional utterance-level latent representations by capturing the relevant information to reproduce the input sequence. The low-dimensional utterance-level representations capture the required information compactly, which can be used for classification. A sequence-to-sequence recurrent neural network (RNN) with an autoencoder framework is used to convert the Mel-SFF spectrogram to an utterance-level fixed representation. The autoencoder framework has two modules, the encoder and the decoder. In both modules, sequence-to-sequence RNNs are used. Motivated by [26], we used gated recurrent cell units (GRU) throughout the study.
The encoder converts the Mel-SFF spectrogram to a fixed-length representation. A fully-connected layer with a tanh activation function converts the output of the encoder to a hidden input format which is considered the BNF. The BNFs extracted from the trained autoencoder are used for dialect identification.
The BNFs are passed to the decoder as hidden inputs and the decoder learns to reproduce the Mel-SFF spectrogram sample by sample. The estimated output is recurrently passed to the next time-steps as hidden state input. The autoencoder network is trained by minimizing the root mean square error (RMSE) between the estimated decoder output and the original Mel-SFF spectrogram. The initial hidden state input for the first time steps of the RNNs in the encoder and the initial input in the decoder are set to 0 for all utterances. The autoencoders of this study are implemented using the AuDeep toolkit [26], [34].

C. FUSION SYSTEM
In order to investigate whether there is complementary information between the STFT and SFF spectrograms, we developed a fusion system. The block diagram of the fusion system is shown in Figure 4. In this system, the bottleneck features extracted from the autoencoders trained on the Mel-SFF spectrogram (the proposed BNF Mel-SFF system) and Mel-STFT spectrogram (the baseline BNF Mel-STFT system) are concatenated to train the classifier. Two separate autoencoders are trained, each one capturing the underlying latent space representations from respective input spectrograms. The classifier trained using these fused features is used for dialect identification in a similar manner as the system described in Section III-D.

D. CLASSIFICATION
The third stage in the proposed system is classification. We experimented with three different classifiers: Gaussian linear classifier (GLC), multi-class logistic regression (MCLR) and support vector machine (SVM). GLC is a generative classifier model and MCLR as well as SVM are discriminative classifier models. GLC was implemented based on [35]. For MCLR and SVM, we used the implementations from [36]. Both MCLR and SVM use the one-vs-rest strategy to classify dialects.

IV. EXPERIMENTAL SETUP
In this section, the databases used in the study are described. In addition, the section discusses the baseline systems and the evaluation metrics adopted in the study.

A. DATABASES
Two speech databases, STYRIALECT and UT-Podcast, are used in the study. The STYRIALECT database includes the dialects of Styria in German [25]. The database consists of 5227 utterances for training and 2570 utterances for development. The STYRIALECT test set is not provided with labels and therefore the results of this database are reported only for the development set in this study. The sampling frequency is 16 kHz and the duration of each utterance is 2 s. The database has three classes (Styrian dialects of German) with different distributions. More details about the database can be found in [25].
The UT-Podcast database consists of three major dialects (US, UK, and AU) of English [37]. This data is collected from different websites for each dialect and it covers a wide range of topics. Since the data is collected from online podcasts, speech is more spontaneous than in STYRIALECT and not very well structured. Therefore, the collected speech captures all the dialectal traits (pronunciation, vocabulary, and grammatical variations). The speech signals are segmented in such a way that each utterance is 17 s in duration and contains 46 words on average. The sampling frequency is 8 kHz. The database is divided into train and test sets as described in [37].
For the experiments in this study, half of the original test set of the database is used for development and the other half for testing.

B. BASELINE CONFIGURATIONS
The proposed system is compared to three baseline systems. The first baseline is the ComParE'19 system, which uses the BNFs of a sequence-to-sequence autoencoder, which is trained using the Mel-STFT spectrogram [25]. This system will be referred to as the BNF Mel-STFT system. The second baseline is an i-vector system which is trained using Mel frequency cepstral coefficients (MFCCs) [20], [38]. The third baseline is an i-vector system, which is trained using the BUT/phonexia bottleneck features [39]. The second and third system will be referred to as the i-vector MFCC system and the i-vector BUT-BNF system, respectively.
In the BNF Mel-STFT system, spectral analysis of speech is computed with STFT using 80-ms frames with the Hann window and a shift of 40 ms. Mel-bank energies are computed from the spectrum using 128 channels. Amplitude clipping is performed on the Mel-STFT spectrogram to reduce the effect of noise captured in the recordings. Five clipping thresholds, denoted as −40 dB, −50 dB, −60 dB, −70 dB, and −80 dB, are generated as in [25]. The baseline BNF Mel-STFT system uses a similar autoencoder architecture as the proposed BNF Mel-SFF system in order to make a fair comparison between the use of the two Mel-weighted spectrograms in dialet identification. The RNNs in the autoencoder have two layers with 256 GRUs in each layer and the encoder network is unidirectional while the decoder network is bidirectional. The network is trained for 16 epochs with a drop out of 30%. The BNF Mel-STFT system is trained in a similar manner as in the proposed BNF Mel-SFF system to obtain unsupervised representations (BNFs) from the Mel-weighted spectrograms. These representations (BNFs) are used to train the classifier, which is then used for the dialect prediction.
The other two baseline systems (the i-vector MFCC system and the i-vector BUT-BNF system) differ only in the feature representations used for i-vector training. In the former, i-vectors are extracted from 13 static mean normalized MFCC features and their shifted delta coefficients. In the latter, BNFs are extracted from a multi-lingual phone recognizer neural network. For our experiments, we considered a pre-trained phone recognizer from BUT/phonexia [39] which was trained using 17 Babel languages. For both systems, 100-dimensional i-vectors are extracted using 256 Gaussian mixture components and the obtained i-vectors are transformed by a whitening transformation to be used in the dialect prediction [20], [38].

C. EVALUATION METRICS
The evaluation metrics used are the unweighted average recall (UAR) and accuracy. UAR gives the unbiased scores for the classification and therefore it is considered as the primary evaluation metric for this study. These evaluation metrics were chosen in order not to create any bias towards the majority class as the classes are unevenly distributed.

V. RESULTS
In this section, the results obtained in dialect identification using the proposed system and the baseline systems are reported separately for the STYRIALECT database and the UT-Podcast database.

A. RESULTS FOR THE STYRIALECT DATABASE
In this section, different variants of the SFF spectrogram computation methods described in Section II-B are first investigated to find the best approach for the proposed BNF Mel-SFF system in dialect identification. Then, the proposed system with the best approach is compared to the baseline systems and to the fusion system. In both parts, SVM is used as a classifier. Finally, we validate the performance of the proposed system and the fusion system with different classifiers (SVM, MCLR and GLC) in comparison to the best baseline system obtained from the former analysis.  In order to find out which of the four spectrogram computation approaches described in Section II-B is best, we conducted dialect identification experiments by using all these approaches and by using four values for the clipping threshold (−40 dB, −50 dB, −60 dB, and −70 dB). The obtained results (in UAR %) are plotted in Figure 5. It can be observed that S avg outperformed the other approaches for all threshold values. Therefore, the feature extraction from the Mel-SFF spectrogram was computed in all further experiments of this study using S avg with a segment duration of 37.5 ms.
The dialect identification results reported in UAR [in %] and accuracy [in %] are shown in Table 1 for the proposed BNF Mel-SFF method and for the three reference methods by using the SVM classifier. The first column refers to the systems under comparison. In addition to the BNF Mel-SFF system and the three reference systems, the table also includes the fusion system (the lowest row of the first column). The second column includes the different clipping thresholds. From the table, it can be observed that the MFCC-based i-vector system performed better than the BUT/phonexia i-vector system. The BNF Mel-STFT system showed the best performance among all the systems at the threshold of −70 dB. Among the three baseline systems, the BNF Mel-STFT system gave the best performance in both metrics.
The proposed BNF Mel-SFF system showed better performance in UAR at the threshold of −40 dB when compared to the BNF Mel-STFT baseline system. In addition, the proposed system showed comparable performance with BNF Mel-STFT at the threshold levels of −50 dB and −60 dB. Furthermore, the fusion system outperformed the best baseline configuration at the thresholds of −40 dB by 0.42% in UAR.
Furthermore, we compared the dialect identification performance with the three different classifiers described in Section III-D using the BNF Mel-STFT baseline system, TABLE 1. Performance in UAR (%) and accuracy of the three baseline systems, the proposed system and the fusion system using the development data of STYRIALECT. SVM is used as the classifier. The utterance length is 2 s. the proposed BNF Mel-SFF system and the fusion system. The results reported in Table 2 are shown for the best configurations from Table 1, i.e., with the threshold of −70 dB for the BNF Mel-STFT system and with the threshold of −40 dB for the BNF Mel-SFF system and for the fusion system. From these experiments, it can be observed that the SVM classifier performed better than the other two classifiers. Furthermore, it can also be observed that the fusion of the BNFs derived from the Mel-STFT and Mel-SFF spectrograms improved the overall performance compared to any of the individual feature extraction methods.

B. RESULTS FOR THE UT-PODCAST DATABASE
From the results reported for the STYRIALECT database in Section V-A, it can be observed that the performance of the i-vector MFCC and i-vector BUT-BNF systems is poorer compared to the other systems. Hence, these two systems were removed in evaluating the UT-Podcast database. Table 3 presents the UAR results for the three remaining systems separately for the development and test sets and for the three different classifiers. The configurations of these systems are as in Sections III-A and IV-B, except that the clipping threshold is fixed to −40 dB. The autoencoder is trained for 128 epochs with batch size 4 and 128 GRUs in each layer.
From the table, it can be observed that the BNF Mel-SFF system performed better than the BNF Mel-STFT system for all classifiers. As in the results discussed in Section V-A, SVM showed higher performance compared to the two other classifiers. The proposed BNF Mel-SFF system gave a relative improvement of 9.47% and 4.69% in UAR for the development and test set, respectively, when compared to the baseline BNF Mel-STFT system. The results above support our hypothesis: Since the SFF spectrum is extracted in principle at every sample, the temporal resolution of the spectrogram is preserved. The hidden BNFs derived from the SFF spectrogram showing high spectral and temporal resolution result in better discrimination of speech sounds across dialects.
Furthermore, from the results reported in Tables 2 and 3, it can be observed that the fusion of the BNFs derived from the Mel-STFT and Mel-SFF spectrograms improved the overall performance compared to any of the individual systems. The improvement achieved with the fusion system for both databases shows that there is complementary information between the spectral representations computed by STFT and SFF.
It is to be noted that the results reported in Table 3 were obtained by using the speech sounds of UT-Podcast over the entire length of the utterance (i.e., 17 s). In order to study the effect of the utterance length for dialect identification, additional experiments were carried out using utterance lengths of 10 s and 2 s for the UT-Podcast database. The results reported in Table 4 show that the proposed BNF Mel-SFF system performed consistently for all utterance lengths. Furthermore, it can be observed that the proposed system showed a clearly larger improvement (15.35% relative) compared to the STFT-based reference system for shorter utterances than for longer utterances (4.69% relative). Furthermore, the fusion system showed an improvement for both utterance lengths compared to the individual reference systems, again indicating complementary information between the features.

VI. SUMMARY AND CONCLUSION
This study explored the use of the Mel-weighted single frequency filtering spectrogram for dialect identification using the STYRIALECT and UT-Podcast databases. Dialects were identified by training an autoencoder with the Mel-SFF spectrogram and by feeding the bottleneck features of the autoencoder to a classifier. The proposed Mel-SFF spectrogram gave better performance compared to the i-vector based baseline systems. Furthermore, the fusion of the unsupervised representations (BNFs) computed from the Mel-SFF and Mel-STFT spectrograms using the sequence-to-sequence autoencoders yielded the best UAR score (46.9%) for the STYRIALECT database. In UT-Podcast, the proposed and fusion systems gave a relative UAR improvement of 4.69% and 7.71% compared to the Mel-STFT spectrogram-based baseline system, respectively. Furthermore, the proposed system showed better performance especially in short utterances compared to the baseline system in the experiments with the UT-Podcast data. Therefore, we conclude that the high spectral and temporal resolution of the SFF spectrum leads to an improvement in dialect identification for the studied German and English dialects. In addition, we conclude that the proposed Mel-SFF spectrogram system distinguishes dialects better from short utterances than its STFT-based reference system. In the future, we plan to explore the Mel-SFF spectrogram derived features for dialect identification in noisy conditions [27], [28], [30] and for larger corpora.


Streaming Object Detection for 3-D Point Clouds

Autonomous vehicles operate in a dynamic environment, where the speed with which a vehicle can perceive and react impacts the safety and efficacy of the system. LiDAR provides a prominent sensory modality that informs many existing perceptual systems including object detection, segmentation, motion estimation, and action recognition. The latency for perceptual systems based on point cloud data can be dominated by the amount of time for a complete rotational scan (e.g. 100 ms). This built-in data capture latency is artificial, and based on treating the point cloud as a camera image in order to leverage camera-inspired architectures. However, unlike camera sensors, most LiDAR point cloud data is natively a streaming data source in which laser reflections are sequentially recorded based on the precession of the laser beam. In this work, we explore how to build an object detector that removes this artificial latency constraint, and instead operates on native streaming data in order to significantly reduce latency. This approach has the added benefit of reducing the peak computational burden on inference hardware by spreading the computation over the acquisition time for a scan. We demonstrate a family of streaming detection systems based on sequential modeling through a series of modifications to the traditional detection meta-architecture. We highlight how this model may achieve competitive if not superior predictive performance with state-of-the-art, traditional non-streaming detection systems while achieving significant latency gains (e.g. 1/15'th - 1/3'rd of peak latency). Our results show that operating on LiDAR data in its native streaming formulation offers several advantages for self driving object detection -- advantages that we hope will be useful for any LiDAR perception system where minimizing latency is critical for safe and efficient operation.

Introduction
Autonomous driving systems require detection and localization of objects to effectively respond to a dynamic en- LiDAR accrues a point cloud incrementally based on a rotation around the z axis. Instead of artificially waiting for a complete point cloud scene based on a 360 • rotation (baseline), we perform inference on subsets of the rotation to pipeline computation (streaming). Gray boxes indicate the duration for a complete rotation of a LiDAR (e.g. 100 ms [58,15]). Green boxes denote inference time. The expected latency for detection -defined as the time between a measurement and a detection decreases substantially in a streaming architecture (dashed line). At 100 ms scan time, the expected latency reduces from ∼ 120 ms (baseline) versus ∼ 30 ms (streaming), i.e. >3× (see text for details). The table compares the detection accuracy (mAP) for the baseline on pedestrians and vehicles to several streaming variants [34].
vironment [15,3]. As a result, self-driving cars (SDCs) are equipped with an array of sensors to robustly identify objects across highly variable environmental conditions [7,59]. In turn, driving in the real world requires responding to this large array of data with minimal latency to maxi-mize the opportunity for safe and effective navigation [30]. LiDAR represents one of the most prominent sensory modalities in SDC systems [7,59] informing object detection [65,69,63,64], region segmentation [41,37] and motion estimation [29,67]. Existing approaches to LiDARbased perception derive from a family of camera-based approaches [54,44,21,5,27,11], requiring a complete 360 • scan of the environment. This artificial requirement to have the complete scan limits the minimum latency a perception system can achieve, and effectively inserts the LiDAR scan period into the latency 1 . Unlike CCD cameras, many Li-DAR systems are streaming data sources, where data arrives sequentially as the laser rotates around the z axis [2,23].
Object detection in LiDAR-based perception systems [65,69,63,64] presents a unique and important opportunity for re-imagining LiDAR-based meta-architectures in order to significantly minimize latency. Previous work in camerabased detection systems reduced latency ∼ 2× by introducing a "single-stage" meta-architecture [44,53,39], however the resulting systems typically suffer from a notable drop in detection accuracy [26] (but see [39,35]). LiDARbased perception systems offer an opportunity for significantly improving latency, but without detrimenting detection accuracy by leveraging the streaming nature of the data. In particular, streaming LiDAR data permits the design of meta-architectures which operate on the data as it arrives, in order to pipeline the sensory readout with the inference computation to significantly reduce latency ( Figure 1).
In this work, we propose a series of modifications to standard meta-architectures that may generically adapt an object detection system to operate in a streaming manner. This approach combines traditional elements of single-stage detection systems [53,44] as well as design elements of sequence-based learning systems [6,28,20]. The goal of this work is to show how we can modify an existing object detection system -with a minimum set of changes and the addition of new operations -to efficiently and accurately emit detections as data arrives ( Figure 1). We find that this approach matches or exceeds the performance of several baseline systems [34,48], while substantially reducing latency. For instance, a family of streaming models on pedestrian detection achieves up to 60.1 mAP compared to 54.9 mAP for a baseline non-streaming model, while reducing the expected latency > 3×. In addition, the resulting model better utilizes computational resources by pipelining the computation throughout the duration of a LiDAR scan. We demonstrate through this work that designing architectures to leverage the native format of LiDAR data achieves substantial latency gains for perception systems generically 1 LiDAR typically operates with a 5-20 Hz scan rate. We focus on 10 Hz (i.e. 100 ms period), because several prominent academic datasets employ this scan rate [58,15], however our results may be equally applied across the range of scan rates available. that may improve the safety and efficacy of SDC systems.

Object detection in camera images
Object detection has a long history in computer vision as a central task in the field. Early work focused on framing the problem as a two-step process consisting of an initial search phase followed by a final discrimination of object location and identity [14,10,60]. Such strategies proved effective for academic datasets based on camera imagery [12,40].
The re-emergence of convolutional neural networks (CNN) for computer vision [33,32] inspired the field to harness both the rich image features and final training objective of a CNN model for object detection [55]. In particular, the features of a CNN trained on an image classification task proved sufficient for providing reasonable candidate locations for objects [17]. Subsequent work demonstrated that a single CNN may be trained in an end-to-end fashion to sub-serve for both stages of an object detection system [54,16]. The resulting two-stage systems, however, suffered from relatively poor computational performance, as the second stage necessitated performing inference on all candidate locations leading to trade-offs between thoroughly sampling the scene for candidate locations and predictive performance for localizing objects [26].
The computational demands of a two-stage systems paired with the complexity of training such a system motivated researchers to consider one-stage object detection, where by a single inference pass in a CNN suffices for localizing objects [44,53]. One-stage object detection systems lead to favorable computational demands at the sacrifice of predictive performance [26] (but see [39,38] for subsequent progress).

Object detection in videos
Object detection for videos reflects possibly the closest set of methods relevant to our proposed work. In video object detection, the goal is to detect and track the one or more objects over subsequent camera image frames. Strategies for tackling this problem include breaking up the problem into a computationally-heavy detection phase and a computationally-light tracking phase [42], and building blended CNN recurrent architectures for providing memory between time steps of each frame [46,43].
Recent methods have also explored the potential to persist and update a memory of the scene. Glimpses of a scene are provided to the model; for example, views from specific perspectives [24] or cropped regions [4], and the model is required to piece together the pieces to make predictions.
In our work, we examine the possibility of dividing a single frame into slices that can be processed in a streaming fashion. A time step in our setup correspond to a slice of one frame. An object may appear across multiple slices, but generally, each slice contains distinct objects. This may require similar architectures to video object detection (e.g., convolutional LSTMs) in order to provide a memory and state of earlier slices for refining or merging detections [62,49,61].

Object detection in point clouds
The prominence of LiDAR systems in self-driving cars necessitated the application of object detection to point cloud data [15,3]. Much work has employed object detection systems originally designed for camera images to point cloud data by projecting such data from a Bird's Eye View (BEV) [65,45,64,34] (but see [47]) or a 3-D voxel grid [69,63]. Alternatively, some methods have re-purposed two stage object detector design with a region-proposal stage but replacing the feature extraction operations [66,57,50].
In parallel, others have pursued replacing a discretization operation with a featurization based on native pointcloud data [51,52]. Such methods have led to methods for building detection systems that blend aspects of point cloud featurization and traditional object detectors on cameras [34,68,48] to achieve favorable performance for a given computational budget.

Streaming LiDAR inputs
A LiDAR system for an SDC measures the distance to objects by shining multiple lasers at fixed inclinations and measuring the reflectance in a sensor [7,59]. The lasers precess around the z axis, and make a complete rotation at a 5-20 Hz scan rate. Typically, SDC perception systems artificially wait for a complete 360 • rotation before processing the data.
In this work, we simulate a streaming system with the Waymo Open Dataset [58] by artificially manipulating the point cloud data 2 . The native format of point cloud data are range images whose resolution in height and width correspond to the number of lasers and the rotation speed and laser pulse rate [47]. In this work, we artificially slice the input range image into n vertical strips along the image width to provide an experimental setup to experiment with streaming detection models.

Streaming object detection
This work introduces a meta-architecture for adapting object detection systems for point clouds to operate in a 2 KITTI [15] is the most popular LiDAR detection dataset, however this dataset provides annotations within a 90 • frustum. The Waymo Open Dataset provides a completely annotated 360 • point cloud which is necessary to demonstrate the efficacy of the streaming architecture across all angular orientations. A streaming object detection system processes a spatially restricted slice of the scene. We introduce two stateful components: Stateful NMS (red) and a LSTM (blue) between input slices. Detections produced by the model are denoted in green boxes. Dashed line denotes feature pyramid uniquely employed in [34]. streaming fashion. We employ two models as a baseline to demonstrate how the proposed changes to the metaarchitecture are generic, and may be employed in notably different detection systems.
We first investigate PointPillars [34] as a baseline model because it provides competitive performance in terms of predictive accuracy and computational budget. The model divides the x-y space into a top-down 2D grid, where each grid cell is referred to as a pillar. The points within each non-zero pillar are featurized using a variant of a multilayer perceptron architecture designed for point cloud data [51,52]. The resulting d-dimensional point cloud features are scattered to the grid and a standard multi-scale, convolutional feature pyramid [38,69] is computed on the spatiallyarranged point cloud features to result in a global activation map. The second model investigated is StarNet [48]. StarNet is an entirely point-based detection system which uses sampling instead of a learned region proposal to operate on targeted regions of a point cloud. StarNet avoids usage of global information, but instead targets the computational demand to regions of interest, resulting in a locally targeted activation map. See the Appendix for architecture details for both models. For both PointPillars and StarNet, the resulting activation map is regressed on to a 7-dimensional target parameterizing the 3D bounding box as well as a classification logit [63]. Ground truth labels are assigned to individual anchors based on intersection-overunion (IoU) overlap [63,34]. To generate the final predictions, we employ oriented, 3-D multi-class non-maximal suppression (NMS) [17].
In the streaming object detection setting, models are limited to a restricted view of the scene. We carve up the scene into n slices (Section 3.1) and only supply an individual slice to the model (Figure 2). We simplify the parameterization by requiring that slices are non-overlapping (i.e., the stride between slices matches the slice width). We explore a range of n in the subsequent experiments.
For the PointPillars convolutional backbone, we assume that sparse operators are employed in the convolutional backbone to avoid computation on empty pillars [19]. Note that no such implementation is required for StarNet because the model is designed to only operate on populate regions of the point cloud [48].

Stateful non-maximum suppression
Objects which subtend large angles of the LiDAR scan present unique challenges to a steaming detection system which necessarily have a limited range of sensor input (Table 1). Hence, we explore a modified NMS technique that maintains state. Generically, NMS with state may take into account detections in the previous k slices to determine if a new detection is indeed unique. Therefore, detections from the current slice can be suppressed by those in previous slices. Stateful NMS does not require a complete Li-DAR rotation and may likewise operate in a streaming fashion. In our experiments, for a broad range of n, we found that k = 1 achieves as good of performance as k=n − 1 which would correspond to a global NMS available to a non-streaming system. We explore the selection of k in Section 4.2.

Adding state with recurrent architectures
Given a restricted view of the point cloud scene, streaming models can be limited by the context available to make predictions. To increase the amount of context that the model has access to, we consider augmenting the baseline model to maintain a recurrent memory across consecutive slices. This memory may be placed in the intermediate representations of the network.
We select a standard single layer LSTM as our recurrent architecture, although any other RNN architecture may suffice [25]. The LSTM is inserted after the final global representation from either baseline model before regressing on to the detection targets. For instance, in the PointPillars baseline model, this corresponds to inserting the LSTM after the convolutional representation. The memory input is then the spatial average pooling for all activations of the final con-volutional layer before the feature pyramid 3 . Note that the LSTM memory does not hard code the spatial location of the slice it is processing.
Based on earlier preliminary experiments, we employed LSTM with 128 hidden dimensions and 256 output dimensions. The output of the LSTM is summed with the final activation map by broadcasting across all spatial dimensions in the hidden representation. More sophisticated elaborations are possible, but are not explored in this work [42,46,43,62,49,61].

Results
We present all results on the Waymo Open Dataset [58]. All models are trained with Adam [31] using the Lingvo machine learning framework [56] built on top of Tensor-Flow [1] 4 . We perform hyper-parameter tuning through cross-validated studies and final evaluations on the corresponding test datasets. In our experiments, we explore how the proposed meta-architecture for streaming 3-D object detection compares to a standard object detection system, i.e. PointPillars [34] and StarNet [48]. All experiments use the first return from the medium range LiDAR (labeled TOP) in the Waymo Open Dataset, ignoring the four short range LiDARs for simplicity. This results in slightly lower baseline and final accuracy as compared to previous results [48,58,68].
We begin with a simple, generic modification to the baseline architecture by limiting its spatial view to a single slice. This modification permits the model to operate in a streaming fashion, but suffers from a severe performance degradation. We address these issues through stateful variants of non-maximum suppression (NMS) and recurrent architectures (RNN). We demonstrate that the resulting streaming meta-architecture restores competitive performance with favorable computation and latency benefits. Importantly, such a meta-architecture may be applied generically to most other point cloud detection models [48,69,63,65,45,64,47].

Spatially localized detection degrades baseline models
As a first step in building a streaming object detection system, we modify a baseline model to operate on a spatially restricted region of the point cloud. Again, we emphasize that these changes are generic, and may be introduced to most object detectors for LiDAR. Such a model trains on a restricted view of the LiDAR subtending an angle in the x-y plane (Figure 2). By operating on a spatially  [34] and (bottom) StarNet [48]. The solid black line (localized rf) corresponds to the modified baseline that operates on a spatially restricted region. Dashed lines corresponds to baseline models that processes the entire laser spin (vehicle = 51.0%; pedestrian = 54.9%). Each curve represents a streaming architecture (see text).
restricted region of data, the model may in principle operate with a reduced latency since inference can proceed before a complete LiDAR rotation ( Figure 1). Two free parameters that govern a localized receptive field are the angle of restriction and the stride between subsequent inference operations. To simplify this analysis, we parameterize the angle based on the number of slices n where the angular width is 360 • /n. We specify the stride to match the angle such that each inference performs inference on non-overlapping slices; overlapping slices is an option, but requires recomputing features on the same points. We compare the performance of the streaming models against the baselines in Figure 3.
As the number of slices n grows, the streaming model receives a decreasing fraction of the scene and the predictive performance monotonically decreases (black solid line). This reduction in accuracy may be expected because less sensory data is available for each inference operation. All objects sizes appear to be severely degraded by the localized receptive field, although there is a slight negative trend for increasing sizes ( Table 1). The negative trend is consistent with the observation that vehicle mAP drops off faster than pedestrians, as vehicles are larger and will more frequently cross slices boundaries. For instance, at n=16, the mean average precision is 35.0% and 48.8% for vehicles and pedestrians, respectively. A large number of slices n=128 severely degrades model performance for both types.
Beyond only observing fewer points with smaller slices, we observe that even at a modest 8 slices the mAP drops compared to the baseline for both pedestrians and vehicles. Our hypothesis is that when NMS only operates per slice, there are false positives or false negatives created on any object that crosses a border of two consecutive slices. Because a partial view of the object leads to a detection in slice k, another partial view in slice k + 1 may lead to duplicate detections for the same object. Either one or both of the detections may be low quality or suppressed, leading to a reduction in mAP. As a result, we next turn to investigating ways in which we can improve NMS in the intra-frame scenario to restore performance compared to the baseline while retaining the streaming model's latency benefits.    [34]. Localized indicates the mAP for a spatially restricted receptive field. Global NMS boosts performance significantly but is a non-streaming heuristic. Stateful NMS achieves comparable results but is amenable to a streaming architecture.

Adding state to non-maximum suppression boosts performance
The lack of state in a spatially localized model across slices impedes predictive performance. In subsequent sections, we consider several options for offering state with changes to the meta-architecture. We first consider revisiting the non-maximum suppression (NMS) operation. NMS provides a standard heuristic method for improving precision by removing highly overlapping predictions [14,17]. With a spatially localized receptive field, NMS has no ability to suppress overlapping detections arising from distinct slices of the LiDAR spin.
We can verify this failure mode by modifying NMS to operate over the concatenation of all detections across all n slices in a complete rotation of the LiDAR. We term this operation global NMS. (Note that global NMS does not enable a streaming detection system because a complete LiDAR rotation is required to finish inference.) We compute the detection accuracy for global NMS as a point of reference to measure how many of the failures of a spatially localized receptive field can be rescued. Indeed, Table 2 (localized vs. global) indicates that applying global NMS improves predictive performance significantly.
We wish to develop a new form of NMS that achieves the same performance as global NMS but may operate in a streaming fashion. We construct a simple form of stateful NMS that stores detections from the previous slice of the LiDAR scene and use the previous slice's detections to rule out overlapping detections (Section 3.3). Stateful NMS does not require a complete LiDAR rotation and may operate in a streaming fashion. Table 2 (global vs. stateful) indicates that stateful NMS provides predictive performance that is comparable to a global NMS operation within ±0.1 mAP. Indeed, stateful NMS boosts performance of the spatially restricted receptive field across all ranges of slices for both baseline models (Figure 3, red curve). This observation is also consistent with the fact that a large fraction of the failures across object size are largely systematically recovered ( Table 1), suggesting that indeed duplicate detections across boundaries hamper model performance. These results suggest that this generic change to introduce state into the NMS heuristic may recover much of the performance drop due to a spatially localized receptive field.

Adding a learned recurrent model further boosts performance
Adding stateful NMS substantially improves streaming detection performance, however, the network backbone and learned components of the system only operate on the current slice of the scene and the outputs of the previous slice.
In this section, we examine how a recurrent model may improve predictive performance by providing access to (1) more than just the previous LiDAR slice, and (2) the lowerlevel features of the model, instead of just the outputs. In particular, we provide an alteration to the meta-architecture by adding a recurrent layer to the global representation of the network featurization ( Figure 2). We investigated variations of recurrent architectures and hyper-parameters, and settled on a simple single layer LSTM, but most RNN's produces similar results.
The blue curve of Figure 3 shows the results of adding a recurrent bottleneck on top of a spatially localized receptive field and a stateful NMS for both baseline architectures. Generically, we observe that predictive performance increases across the entire range of n. The performance gains are more notable across increasing number of slices n, as well as all vehicle object sizes (Table 1). These results are expected given that we observed systematic failure introduced for large objects that subtend multiple slices ( Figure  3). For instance, with PointPillars at n = 32 slices, the mAP for vehicles is boosted from 39.2% to 48.9% through the addition of a learned, recurrent architecture (Figure 3 Figure 5: Worst-case latency from the initial measurement of the vehicle to the detection for non-streaming (baseline) and streaming detection model (stateful NMS and RNN), broken down by phase. Scan phase latency is based on 10 Hz LiDAR period [58]. Inference phase latency estimated from baseline GPU implementation [34]. Numbers on top of bar are vehicle mAP from the detection model.
complete LiDAR scan.
Although a streaming model sacrifices slightly in terms of predictive performance, we expect that the resulting streaming model would realize substantial gains in terms of computational demand and latency. In the following section we explore this question in detail.

Streaming detection reduces latency and peak computational demand
The impetus for pursuing a streaming based model for detection on LiDAR is that we expect such a system to improve end-to-end latency for detecting objects. We define this latency as the duration of time between the earliest observation of an object (i.e. the earliest time at which reflecting LiDAR points are received) and the identification of a localized, labeled object. In practice, for a non-streaming model the latency corresponds to the summation of the time for a complete (worst-case) 360 o rotation and the subsequent inference operation on the complete LiDAR scene. The latency in a streaming detection system should be improved for two reasons: (1) the computational demand for processing a fraction of the LiDAR spin should be roughly 1 n of the complete scene and (2) the inference operation does not require artificially waiting for the full LiDAR spin and may be pipelined. In this section, we focus our analysis on [34] because of previously reported latencies.
To test the first point, we compute the theoretical peak computational demand (in FLOPS) for running single frame inference on the baseline model as well as streaming models. Figure 4 compares the peak FLOPS versus the detection accuracy across varying slices n for each of the 3 streaming architectures. We display the compute of each approach in terms of the fraction of peak FLOPS required for the nonstreaming baseline model (Note the log x-axis). We observe that a model with a localized receptive field (black curve) reveals a trade-off in accuracy versus the amount of computational demand. However, subsequent models with stateful NMS (red curve) and stateful NMS and RNN (blue curve) require much fewer peak FLOPS to achieve most of the detection performance of the baseline. Furthermore, the stateful NMS and RNN achieves nearly baseline predictive performance across a wide range of slices n with a computational cost of roughly 1 n . Thus, the streaming model requires less peak computational demand with minimal degradation in predictive performance.
Taking into account both the earlier triggering of inference and the reduced computational demand for each slice, we next investigate how streaming models can reduce endto-end latency for detecting objects. Unfortunately, latency is very heavily determined by the inference hardware, as well as the rotational period of the LiDAR system. To estimate reasonable speed up gains, we test these ideas on a previously reported implementation speed for the PointPillars model [34] (Section 6), and employ the rotational period of the Waymo Open Dataset (i.e. 100 ms for 10 Hz) [58]. Figure 5 plots the latency versus the detection accuracy across the streaming model variants; we assume that the scan time is equivalent to the worst case delay between the first measurement of the object and the triggering of inference (the end of the slice): e.g., with 4 slices and 10Hz period, each slice triggers inference every 25ms. We estimate inference latency by scaling the floating point computation time [34] by the fraction of point cloud scene 1 n observed within an angular wedge necessary for inference.
The streaming models reduce end-to-end latency significantly in comparison to a non-streaming baseline model. In fact, we observe that for n = 8, a streaming model with a stateful NMS and RNN achieves competitive detection accuracy with the non-streaming model, but with 1 15 of the latency (17ms vs 116ms). We take these results to indicate as a proof of concept that a streaming detection system may significantly reduce end-to-end latency without significantly sacrificing predictive accuracy.

Increasing model size exceeds baseline, maintaining favorable computational demand
The resulting streaming models achieve competitive predictive performance but with a fraction of the peak computational demand and latency. We next ask if one may further improve streaming model performance, while maintaining a decreased peak computational demand. It is wellknown in the deep learning literature that increasing model size may lead to increased predictive performance (e.g. [8,9,36]). Broadly speaking, we attempt to double the computational cost of each baseline network in order to attempt to boost the overall performance. For instance, for PointPillars we increase the size of the feature pyramid by systematically increasing the spatial resolution of the activation map. Specifically, we increase the top-down view grid size from 384 to 512 for pedestrian models, and from 512 to 784 for vehicle models, resulting in models with 1.75× and 2.23× relative expense, respectively. For Star-Net, we increase the size of all hidden unit representation by a factor of 1.44×. Figure 6 shows the predictive accuracy of the resulting both streaming baseline models on vehicles (left) and pedestrians (right) across slices n in comparison to the nonstreaming baseline for both architectures. As a point of reference, we show the relative peak computational cost of these larger models when run in a non-streaming node (green star). The x-axis measures logarithmically the peak computational demand of the resulting model expressed as a fraction of the non-streaming baseline model. Importantly, we observe that even though the peak computational demand is a small fraction of the non-streaming baseline model, the predictive performance matches or exceeds the non-streaming baseline model (e.g. 60.1 mAP versus 54.9 mAP for pedestrians with PointPillars). Note that in order to achieve these gains in the non-streaming model requires increasing the peak computational cost by 2.25× (green star). Moreover, at the lower peak FLOPS count, the stateful NMS and RNN model retains the most accuracy of the original baseline, yet may achieve > 3× latency gains. We take these results to indicate that much opportunity exists for further improving streaming models to well exceed a non-streaming model, while maintaining significantly reduced latency compared to a non-streaming architecture.

Discussion
In this work, we have described streaming object detection for point clouds for self-driving car perceptions systems. Such a problem offers an opportunity for blending ideas from object detection [54,16,44,53], tracking [42,43,13] and sequential modeling [61]. Streaming object detection offers the opportunity to detect objects in a SDC environment that significantly minimizes latency (e.g. 3-15×) and better utilizes limited computational resources.
We find that simple methods based on restricting the receptive field, adding temporal state to the non-maximum suppression, and learning a perception state across time via recurrence suffice for providing competitive if not superior detection performance on a large-scale self-driving dataset. The resulting system achieves favorable computational performance (∼ 1/10 th ) and improved expected latency (∼ 1/15 th ) with respect to a baseline non-streaming system. Such gains provide headroom to scale up the system to surpass baseline performance (60.1 vs 54.9 mAP) while maintaining a peak computational budget far below a non-streaming model. This work offers opportunity for further improving this methodology, or application to new streaming sensors (e.g. high-resolution cameras that emit rasterized data in slices). While this work focuses on streaming models for a single frame, it is possible to also extend the models to incorporate data across multiple frames. We note that a streaming model may be amendable towards tracking problems since it already incorporates state. Finally, we have explored metaarchitecture changes with respect to two competitive object detection baselines [34,48]. We hope our work will encourage further research on other point cloud based perception systems to test their efficacy in a streaming setting [65,45,64,34,47,69,63,48]. localized RF + stateful NMS + stateful NMS and RNN Figure 6: A larger streaming model may exceed the baseline performance, but with a fraction of the peak computational budget. Results presented for vehicle (left) and pedestrian (right) detection on the larger (top) PointPillars [34] and (bottom) StarNet [48] relative to the original non-streaming baseline. Green star indicates the relative peak FLOPS and accuracy of the larger non-streaming model. Axes and legend follow Figure 4. Computational cost varies inversely with the number of slices(n) from 4 to 64.


Patch Quality and Diversity of Invariant-Guided Search-Based Program Repair

Most automatic program repair techniques rely on test cases to specify correct program behavior. Due to test cases' frequently incomplete coverage of desired behavior, however, patches often overfit and fail to generalize to broader requirements. Moreover, in the absence of perfectly correct outputs, methods to ensure higher patch quality, such as merging together several patches or a human evaluating patch recommendations, benefit from having access to a diverse set of patches, making patch diversity a potentially useful trait. We evaluate the correctness and diversity of patches generated by GenProg and an invariant-based diversity-enhancing extension described in our prior work. We find no evidence that promoting diversity changes the correctness of patches in a positive or negative direction. Using invariant- and test case generation-driven metrics for measuring semantic diversity, we find no observed semantic differences between patches for most bugs, regardless of the repair technique used.

I. INTRODUCTION
Software bugs are troublesome: a study of software bugs in 2017 found that just 606 known bugs affected half of the population and $1.7 trillion USD of assets [1]. They are also cumbersome for programmers, who spend, on average, approximately half of their time diagnosing and squashing bugs [2]. Efforts in automated program repair attempt to alleviate these societal and developmental costs by automating the bug repair process. Most program repair tools require the user to input a program and a set of test cases, which specify desired program behavior. Test cases, however, frequently fail to fully cover the actual specifications of a program. Consequently, program repair techniques frequently produce incorrect patches that overfit to the provided test suite and fail to generalize to broader requirements not explicitly specified in the provided tests [3]- [6]. Producing correct patches that adhere to broader, implicit specifications is thus a desideratum of program repair techniques.
Inconsistency in the quality of patches generated by automated program repair tools can perhaps be alleviated with, among other means, a human in the loop judging patches and/or by combining information from patches to produce a superior patch [7]. In both cases, providing a set of diverse patches may be useful. For the human in the loop adjudicating patches, a diversity of patches means a diversity of options to choose from. For the approach of merging patches into a better patch, a diversity of patches means a diversity of information to merge together. Producing diverse patches may thus also be desirable for these applications.
We thus evaluate patch correctness and diversity for two program repair techniques: GenProg [8], a search-based program repair technique based on genetic programming, and a invariant-driven diversity-promoting repair technique derived from GenProg and described in our prior work [9]. To evaluate patch correctness, we use held-out tests, a practice previously used in evaluating program repair tools [5], [6]. To evaluate patch diversity, we use semantic diversity metrics based on inferred invariants [9] and automatic test case generation tools [7]. This paper's main contributions are: • An evaluation of patch correctness for GenProg [8] and our diversity-promoting repair technique [9].
• An evaluation of patch diversity using both invariantbased [9] and test generation-based [7] semantic diversity for GenProg and our diversity-promoting repair technique.

A. GenProg and Attempts at Improvement
GenProg [8] is a search-based automated program repair technique. GenProg accepts, as input, a faulty program's source code, failing test cases (negative tests) that demonstrate the fault, and passing test cases (positive tests) that demonstrate desirable program behavior to preserve. To produce a bug patch, GenProg treats bug repair as an optimization problem: which patch(es) in the space of possible patches passes as many test cases as possible? The globally optimal solutions are patches that pass all test cases, which Gen-Prog assumes to be correct. GenProg solves this optimization problem using genetic programming. To traverse the space of patches, GenProg mutates and recombines code at the statement level, creating a population of variant programs, or candidate patches. In contrast to approaches that randomly traverse the space of patches, such as TrpAutoRepair [10], GenProg guides the traversal by observing the number of test cases that each candidate patch passes. For each candidate patch, GenProg computes a fitness score equal to a weighted sum of the number of positive and negative patches that the candidate patch passes. Candidate patches with higher fitness are more likely to reproduce through further mutation and recombination, and their offspring will carry the code edits of the parent candidate patch, unless if negated by further code edits.
GenProg's reliance on test cases as a measurement of program correctness makes the approach vulnerable to overfitting, where GenProg constructs a patch that conforms to the test suite, but breaks other implicit software requirements not covered by the provided tests. The weakness of test cases as a specification for program behavior is not specific to GenProg; the problem is common among program repair techniques that rely on test cases as a metric of program correctness. Qi et al. [3] found that almost all repairs produced by GenProg, AE [11], and RSRepair [12]-techniques which depend on test cases to specify desired behavior-are incorrect. They also find that many patches introduce undesirable effects, such as deleting functionality or introducing security vulnerabilities. Other studies, which we discuss in more detail in Section V, have also found a high proportion of incorrect patches among various program repair techniques [4]- [6].
Moreover, GenProg's test case-based fitness function should, in theory, identify and favor partial solutions that pass more test cases than the original program. In practice, however, the intuition fails to hold. Instead, distinct candidate patches often receive the same fitness score, resulting in a fitness landscape with large, flat plateaus [13], [14]. In the common case where a bug is revealed by only a single negative test, there may not exist any intermediate fitness values between the fitness of the original program and a "correct" patch. The fitness function's inability to differentiate between candidate patches undermines GenProg's ability to compose more complex patches. Despite being capable of constructing multi-edit repairs, much of GenProg's patches actually reduce down to single-edit repairs [3]. A potential explanation of test cases' weakness at discriminating candidate patches may lie in the binary nature of test cases. Test cases generally only pass or fail, and generally do not provide indications of partial correctness. As a result, test cases lack granularity in the semantic information they provide, and a test case-based fitness function would thus also be not granular. Thus, a test suite might determine different patches with differing levels of partial correctness to be equally incorrect.
Our previous work [9] attempts to improve on GenProg's search strategy by incorporating additional semantic information from inferred invariants. Using semantic information derived from invariants, we determine which patches appear to be more semantically unique and diverse, which we favor for selection and further exploration. By leveraging added semantic information to diversify the search of the repair space, we sought to discourage the search process from being trapped in locally optimal fitness values, which are undesirable in genetic algorithms [15]. Moreover, producing multiple semantically diverse patches may be desirable for patch recommendation systems, where a human in the loop may choose between several semantically diverse patches, or for combining multiple low quality patches into a higher quality patch [7]. We describe the approach's method of measuring and promoting semantic diversity in II-B. An evaluation on a refactored subset of IntroClassJava [16] reveals that while our prior work was able to successfully diversify the search for a repair and better differentiate between candidate patches, we had no statistically significant evidence of an improvement in repair efficiency or success.
There exist other previous efforts to incorporate more semantic information to improve GenProg's search process. Fast et al. [17] attempts to learn correlations between invariant behavior and program success or failure. Their approach uses known patches for a bug to train a linear model that maps the behavior of invariants and test cases to fitness values. de Souza et al. [13] uses dynamic analysis to track changes in variable values at pre-determined source code checkpoints. They produce a checkpoints metric based on these changes, which they incorporate into the fitness function.

B. Daikon and Invariant-Based Semantic Diversity
Daikon [18] is a dynamic analysis tool that infers likely program invariants. Program invariants are properties which hold true at indicated program locations. Given a program and a method to execute the program (such as test cases), Daikon collects execution traces and analyzes which invariants, as described by a grammar, are statistically likely to be true for the program, as evidenced by program values in the collected trace.
Our previous work [9] introduces a measurement of semantic difference based on inferred invariants in the context of program repair. Given a set of likely invariants inferred from the original faulty program, we construct an invariant profile-a string representation of the reachability and truth of the set of invariants in a program-for each candidate patch. We construct this invariant profile by instrumenting candidate patches to detect whether each invariant is reached and ever violated during program execution, with the results recorded separately for executions of positive and negative tests. The semantic distance between two programs is the Hamming distance between the two programs' string-based invariant profiles. The semantic diversity of a program within a population of programs is the semantic distance between the program and the rest of the population, which we compute by summing the semantic distance between the program and each other program in the population. We promote semantic diversity by using our semantic diversity metric as an optimization objective along with test cases.

C. EvoSuite and Test Generation-Based Semantic Diversity
EvoSuite [19] is a search-based automatic test case generation tool for Java programs. Given a Java bytecode program, EvoSuite produces JUnit tests [20]. To generate tests, EvoSuite uses a combination of mutation analysis and concolic execution to produce and evolve a test suite that maximizes code coverage. Mutating the program simulates the introduction of faults, and EvoSuite uses genetic programming to create tests that detect these mutations, with concolic execution activated after a preset number of generations. Soto [7] proposes a measurement for semantic distance based on the output of test case generators. Given two programs P and Q to compare, Soto uses EvoSuite to generate test suites T P and T Q and merges them to produce T P ∪ T Q . To describe the semantics of P and Q, Soto evaluates each program on the merged test suite T P ∪ T Q to produce a string-based report. The semantic distance between P and Q is the Hamming distance between the two programs' reports, normalized by the length of the reports (|T P ∪ T Q |).

III. ANALYSIS
We evaluate the correctness and semantic diversity of patches generated by GenProg [8] and the program repair approach described by our prior work [9]. We address the following research questions: RQ1: Does promoting semantic diversity using invariants change the correctness of repairs generated?
Since both repair approaches rely on test cases to specify desired program behavior, both techniques risk creating patches that overfit to the provided tests and fail to generalize to broader, implicit requirements. Previous evaluation of GenProg found that many of its repairs are, in fact, incorrect due to weak test suites [3]. Promoting semantic diversity may inadvertently encourage an accumulation of negative, fault-creating edits that test cases might fail to detect, since these edits may result in a change in invariant-observed semantic behavior and thus be favored. Conversely, if truly correct patches are sparser in semantic space than falsely correct patches, then broadening and diversifying the search throughout semantic space might result in a higher chance of encountering truly correct repairs. We thus investigate patch correctness for both repair techniques. RQ2: Does promoting semantic diversity using invariants change the semantic diversity of repairs generated? By encouraging a broad and diverse search through semantic space, we hypothesize that our previously described approach would produce semantically diverse patches. A diverse set of patches may be useful for applications with a human in the loop, such as patch recommendation systems, or for combining multiple patches into a better patch [7]. We thus evaluate patch diversity for both repair techniques. To evaluate our research questions, we use the modified version of IntroClassJava [16] created for our prior work [9]. IntroClassJava is a derivative of IntroClass [21], a set of buggy programs written by students in an introductory programming class. Every IntroClassJava bug comes with a set of blackbox tests and white-box tests. Black-box tests derive from the program's specifications and are written manually by the class's instructor. White-box tests derive from generating tests using KLEE [22], a symbolic execution-based test generator, on a C reference implementation, with manually written tests to cover branches that KLEE cannot generate a test for. We use white-box tests as input to GenProg and our diversitypromoting repair technique, and we use black-box tests as a held-out test suite to evaluate the correctness of patches generated by both techniques as part of RQ1. Note that this evaluation setup differs from the setup used in evaluating our  prior work [9], where we inputted both white-box and blackbox tests to both repair techniques. We discard any patches found during the initialization process of either technique, as GenProg and our diversitypromoting technique differ only after the initialization process, where selective pressure begins to shape the search for a repair. As a result, both techniques traverses the search space identically during initialization, and any patches found during initialization do not illustrate the differences in behavior of the two techniques. Therefore, we exclude such patches from analysis. For our preliminary experiments described here, we use four bugs from the six bugs successfully repaired by either repair technique in our prior work [9]. We use a subset of our previously repaired bugs-which pass all white-box and black-box tests-in order to guarantee that there exists at least one "correct" patch that passes both sets of tests within the search space of the techniques. Out of the six bugs, we exclude smallext-af81-000 as the bug does not have any failing white-box tests, and we exclude smallest-8839-002 as both techniques found patches exclusively during the initialization process in our testing. We thus use the four remaining bugs.
For both techniques, we use the append, replace, and delete mutation operators, one-point crossover, tournament selection with a tournament size of k = 2, a population size of 40, and a limit of 10 generations. We repeat each experiment with random seeds 0-9 inclusive. We conduct our experiments on a computer with the following specifications: Ubuntu Server 16.04 LTS, 4x Intel Xeon E7-4820, 128 GB of RAM, and 2 TB of magnetic hard disk storage.

A. Evaluation of RQ1: Patch Correctness
We evaluate patch correctness by testing each patch against its held-out black-box tests. Table I provides the proportion of "correct" patches generated by each technique. The proportion of patches that the black-box tests deem correct are almost identical for both techniques. A two-sided Fisher's exact test reveals no statistically significant evidence (p > 0.05) of a difference in the number of correct and incorrect patches generated by both techniques. Moreover, most bugs demonstrate all-or-nothing behavior, where almost all repairs generated by   [9] and EvoSuite-generated tests [7]. either technique are correct or incorrect, suggesting that the strength of test suites takes precedence over the search strategy in producing correct patches.

B. Evaluation of RQ2: Patch Diversity
We evaluate patch diversity using both invariant-based and test generation-based metrics of semantic diversity. To measure invariant-based diversity, we treated the set of repairs for a particular bug as a population and used the metric for invariant-based semantic diversity described in our prior work [9]. To measure test generation-based semantic diversity, we used the metric for semantic distance described by Soto [7], and summed the semantic distance between a patch and every other patch for a particular bug to compute a patch's semantic diversity. Table II provides the average semantic diversity of patches generated by both techniques. For both techniques and almost all bugs, neither metric for semantic diversity discerned any semantic difference between any patches for a particular bug.
The semantic indistinguishability of patches suggests either a lack of patch diversity or weakness in the two metrics of semantic distance. We intend to conduct a manual patch analysis to investigate patch semantics and determine the cause of indistinguishability in future work.

A. Test Case Weakness
Using held-out test cases to evaluate patch correctness poses the risk of a patch overfitting to both the white-box and blackbox tests. While patches deemed correct by the held-out tests may still be incorrect, using held-out tests nevertheless allows us to determine whether patches generalize to requirements not specified in the inputted tests but evaluated in the held-out tests. Manual correctness analysis and formal verification may provide stronger evidence of correctness.

B. Sample Size
Our early results evaluate only four bugs and 51 patches. The four bugs are chosen as test subjects as there exist known patches within the search space that are correct with respect to both white-box and black-box tests. We propose to broaden our evaluation to more software bugs in future work.

C. Bug Benchmark
We use a subset of IntroClassJava [16] programs as a benchmark for evaluation. These buggy programs are small (< 30 LOC) and are written by introductory programming students as part of class assignments, rather than by professional software engineers as a part of real-world software. Moreover, the bugs' test suites were designed to have very high specification coverage (with black-box tests) or branch coverage (with white-box tests) [21], which is not always true in real-world software. Evaluating IntroClassJava programs and their bugs does not simulate an application of program repair on industriallysized software. We propose to evaluate patch correctness and diversity on benchmark datasets containing larger, real-world programs, such as Defects4J [23] or Bugs.Jar [24].

V. RELATED WORK
This section discusses other prior efforts in evaluating patch quality. We are not aware of prior efforts in evaluating patch diversity at the time of writing.
Qi et al. [3] evaluates the correctness of patches generated by the search-based program repair tools GenProg [8], AE [11], and RSRepair [12]. They find that the vast majority of patches generated by these tools are incorrect. When they write additional test cases to expose the errors found and input them into GenProg to better guide the search, GenProg was unable to find any patches. They also found that most patches generated by all three techniques are semantically reducible to functionality deletion and often introduce undesired effects, such as security flaws or loss of functionality.
Martinez et al. [4] evaluates the correctness of patches that GenProg generates for the Defects4J [23] benchmark, a set of real-world Java bugs in open source software. Manual analysis reveals that a large majority of patches were incorrect.
Smith et al. [5] evaluates the correctness of patches generated by the search-based program repair tools GenProg [8] and TrpAutoRepair [10], as well as compare the correctness of tool-generated patches to patches written by novice student programmers. They use IntroClass as a benchmark and also use held-out tests to evaluate patch correctness in a manner similar to our evaluation. They find that a large majority of patches are incorrect based on the held-out tests, but also that there's no statistically significant difference between the correctness rate of tool and novice human-generated tests.
Le et al. [6] evaluates the correctness of patches generated by semantics-based program repair techniques, which use symbolic execution and program synthesis, rather than a search through the space of possible patches, to generate a repair. They evaluate the semantics-based repair tool Angelix [25] and variations of the tool with different synthesis engines [26] on the IntroClass [21] and Codeflaws [27] benchmarks, both of which supply two separate test suites per bug. Similar to our evaluation of patch correctness, they use one of the two independent test suites as held-out tests for evaluating patch correctness. They find that a large majority of patches generated by all techniques are incorrect based on the held-out tests, revealing that the problem of patch overfitting extends to semantic-based repair techniques as well.
Xin and Reiss [28] proposes DiffTGen, a technique for evaluating patch correctness by generating test cases based on differences in program syntax between a buggy program and its patch. If running these generated tests produces different output, the difference is sent to an oracle (a human in their evaluation) for correctness analysis. DiffTGen identified 49.4% of overfitting patches generated by various program repair techniques. Their tool can also enhance automated program repair techniques by augmenting test suites with additional generated tests.

VI. CONCLUSION
Our initial results do not suggest evidence of diversity promotion causing an increase or decrease in patch correctness. We moreover find that our metrics for semantic diversity were unable to distinguish between patches for almost every bug, regardless of repair technique used. We propose to further investigate the cause of semantic patch indistinguishability with further analyses, including manual analysis. Moreover, we intend to broaden the scope of bugs for investigation, including real-world bugs in larger, industrially-sized software.