{'fraction_non_alphanumeric': 0.04981378026070764, 'fraction_numerical': 0.00951050811386007, 'mean_word_length': 4.493971501644136, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 4, 'https://': 1, '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}}
Nearest Subspace Search in The Signed Cumulative Distribution Transform Space for 1D Signal Classification

This paper presents a new method to classify 1D signals using the signed cumulative distribution transform (SCDT). The proposed method exploits certain linearization properties of the SCDT to render the problem easier to solve in the SCDT space. The method uses the nearest subspace search technique in the SCDT domain to provide a non-iterative, effective, and simple to implement classification algorithm. Experiments show that the proposed technique outperforms the state-of-the-art neural networks using a very low number of training samples and is also robust to out-of-distribution examples on simulated data. We also demonstrate the efficacy of the proposed technique in real-world applications by applying it to an ECG classification problem. The python code implementing the proposed classifier can be found in PyTransKit (https://github.com/rohdelab/PyTransKit).


Introduction
Signal classification refers to the automatic prediction of the class label of an unknown signal using the information extracted from the corresponding signal values. It is at the heart of many signal processing applications, e.g. human activity recognition [2], physiological signal classification [3] [4], communication [5], machine health monitoring systems [6], financial time series data [7], etc. In the biomedical domain, the classification of physiological signals, such as ECG, EEG, plays an important role in the diagnosis of several diseases.
Existing signal classification approaches can be categorized into two broad groups: 1) hand-engineered feature-based classifiers and 2) end-to-end learning-based classifiers such as artificial neural networks. Feature based methods [8] [9] usually employ a two-step process: first, extraction of numerical features, e.g. time or frequency domain features, wavelet features, etc. from the raw signal data, and then, application of different multivariate regression-based classification methods, e.g. linear discriminant analysis, support vector machines, random forests, etc. on the extracted features. Convolutional neural networks (CNN) based classification methods have widely been studied recently as they have shown promising results in certain classification tasks [10] [11].
A less commonly used alternative is to use transport transform based classification techniques [12]. Following the linear optimal transport framework proposed by Wang et al. [13], the cumulative distribution transform (CDT) [14] was proposed as a means of classifying strictly positive 1D signals. Aldroubi et al. [15] proposed the signed cumulative distribution transform (SCDT), an extension of the CDT to general signed signals. Both transforms can be applied to 1D signal classification problems in combination with linear classifiers, such as Fisher discriminant analysis, support vector machines, etc. In this paper, we propose a new classification technique for 1D signals that first represents each signal in the SCDT space, and following [16] we then utilize the nearest subspace method to classify each signal. Using a well-known ECG signal database, we show the approach is efficient to compute, highly accurate, requires few training samples, and performs well in out-of-distribution tasks as compared to state of the art end-to-end convolutional neural networks.

The Signed Cumulative Distribution Transform
The signed cumulative distribution transform (SCDT) [15] is an extension of the cumulative distribution transform (CDT) [14], an invertible nonlinear 1D signal transform from the space of smooth positive probability densities to the space of diffeomorphisms. The CDT was introduced for a class of normalized positive smooth functions, which can be described as follows: let s(t), t ∈ Ω s and s 0 (y), y ∈ Ω s0 define a given signal and a (known) reference signal, respectively, such that Ωs s(u)du = Ωs 0 s 0 (u)du = 1 and s 0 (y), s(t) > 0 in their respective domains. The CDT of s(t) is then defined to be the function s * (y) that solves, Now if we define the cumulative distribution functions (CDFs) S(t) = t −∞ s(u)du and S 0 (y) = y −∞ s 0 (u)du, an alternative expression for s * (y) is given by, s * (y) = S −1 (S 0 (y)). ( If a uniform reference signal is used, i.e. s 0 (y) = 1 in Ω s0 = [0, 1], we can write S 0 (y) = y and therefore s * (y) = S −1 (y). Note that we are using the definition of the CDT used in [17], which is slightly different from the formulation used in [14].
Although the CDT can effectively be used in many classification [14] and estimation [17] problems, the framework described above has the limitation that signals themselves must be positive. To overcome this limitation, Aldroubi et al. [15] proposed the SCDT as an extension of the CDT to general finite signed signals. For the non-negative signal s(t) with arbitrary mass, the transform is given by: where s L1 is the L 1 norm of signal s, and s * is simply the CDT (eq. (2)) of the normalized signal 1 Now to extend the transform to a signed signal, the signal s(t) is decomposed as and s − (t) are the absolute values of the positive and negative parts of the signal s(t). The SCDT of s(t) is then defined as: where s + (y) and s − (y) are the transforms, as defined in eq. (3), for the positive signals s + (t) and s − (t), respectively. The SCDT has a number of properties which will help us simplify the signal classification problems.
Composition property: Let s be the SCDT of the signed signal s. The SCDT of the signal s g = g s • g is given by: where, g(t) is an invertible and differentiable increasing function, s • g = s(g(t)), and g (t) = dg(t)/dt [15]. For example, in case of translation and scaling, g(t) = ωt − τ , and the SCDT of the signal s g (t) = ωs(t − µ) can be derived as: Convexity property: Let a set of signals be defined as: S = {s j |s j = g j ϕ • g j , g j ∈ G}, where ϕ is a given signal and G ⊂ T denotes a set of 1D spatial deformations of a specific kind (e.g. translation, scaling, etc.). Convexity property states that the set S = { s j : s j ∈ S} is convex for every ϕ if and only if G −1 = {g −1 j : g j ∈ G} is convex [15]. Note that T is a set of all possible increasing diffeomorphisms from R to R.
The set S can be interpreted as a generative model for a signal class while ϕ being the template signal for that class. In the next section, we discuss the generative model based problem formulation for 1D signal classification problem. Later, we show how the composition and convexity properties of the SCDT help render certain nonlinear signal classes into convex clusters and facilitate simple classification algorithms.

Generative Model and Problem Statement
This section describes a generative model-based problem statement for the 1D signal classification problems. We are concerned with classifying signal patterns that can be modeled as the instances of a certain template observed under some unknown deformations (e.g., translation, dispersion, etc.). For example, we can consider classifying ECG signals for detecting abnormal heart conditions. The ECG segments of a class can be thought of as instances of a template corresponding to that class, each observed under some deformations. We define the signal classes of the above type with the following generative model: Generative model: Let G ⊂ T denotes a set of increasing 1D spatial deformations of a specific kind (e.g., g(t) = k p k t k ∈ G, g (t) > 0). The 1D mass (signal intensity) preserving generative model for class-c is then defined to be the set: where ϕ (c) is the template pattern of class c, s j is the j-th signal from that class, and g j > 0. Considering the generative model, the classification problem is as follows: Classification problem: Let G ⊂ T be the set of spatial deformations and S (c) be defined as in eq. (6). Given training samples {s

Proposed Solution
The generative model described in eq. (6) generally yields nonconvex (hence nonlinear) signal classes. However, the SCDT can simplify the data geometry and thereby simplify the classification problem. Therefore we follow the approach proposed in [16] and employ the composition property of the SCDT on s where, (ϕ (c) + ) * and (ϕ (c) − ) * are the CDTs (defined in eq. (2)) of the positive and negative parts of the template signal ϕ (c) , respectively. The constant terms ϕ (c) + L1 and ϕ (c) − L1 denote the corresponding total masses. Noting that signals can be made to have zero mean, in the proposed solution we ignore the total mass terms (constant scaling factor) and focus on the CDT terms only, which yields a modified transformed signal: The generative model in the transform domain is given by, It can be shown that the generative model given in eq. (8) forms a convex set if G is a convex group [16]. Moreover, as the SCDT is a one-to-one map, it follows that if S (c) ∩ S (p) = ∅, then S (c) ∩ S (p) = ∅. Now, let us define a subspace generated by the convex set S (c) as follows: It can be shown that under certain assumptions, the convex space for a particular class in transform domain does not overlap with the subspace corresponding to a different class [16], i.e. S (c) ∩ V (p) = ∅, c = p.
It follows from the analysis that for a test sample s generated according to the generative model for class c (unknown), d 2 ( s † , V (c) ) ∼ 0, and d 2 ( s † , V (p) ) > 0 for p = c. Here d 2 (·, ·) is the Euclidean distance between s and the nearest point in S (c) or V (c) , and s † = ((s + ) * , (s − ) * ). Therefore, the class of the unknown sample can be predicted by solving, Training Algorithm: Based on the analysis discussed above, we can follow [16] to propose a non-iterative training algorithm. First, we compute the transforms of the training samples to get S (c) for all the classes (Fig. 1). Next, we 2 , ... , which will later be used to predict the class label of an unknown sample. Note that although this algorithm is designed for classifying signal patterns that can be modeled as the instances of a certain template (see the generative model defined in eq. 6), we do not need to estimate the template ϕ (c) for class c. One can simply take the training samples for a particular class c and generate B (c) using the algorithm described above.
Testing Algorithm: Let us consider the problem of predicting class of a test signal s using the proposed model. First, we obtain the transform s † = ((s + ) * , (s − ) * ). We then estimate the distance between s † and the subspace model for each class by d 2 ( s, V (c) ) ∼ s − B (c) B (c) T s 2 L2 . The class of s † is estimated to be: where A (c) = B (c) B (c) T is an orthogonal projection matrix onto the subspace spanned by the columns of B (c) .

Experimental Setup
In this section, we evaluate the performance of the proposed method with respect to some popular CNN-based 1D signal classification techniques. To demonstrate the ability of the proposed classifier, we first consider the problem of classifying three prototype signal classes: a Gabor wave, an apodized sawtooth wave, and an apodized square wave. We then conducted experiments on the synthetic data and compared the results against three different CNNs: a deep [18], a shallow [18], and a compact [19] CNN. Classification performances of the methods were studied in terms of test accuracy, data efficiency, and robustness to the out-of-distribution samples. We also used an ECG dataset to demonstrate the comparative performances of the methods on real data.

Effective and Data Efficient
To demonstrate the effectiveness and data efficiency of the proposed method, we generated a synthetic dataset by applying 4th degree polynomials on the three aforementioned prototype signals. Test results plotted in Fig. 2 show that the proposed method required very few train samples to learn the deformations present in the data, as it achieved near perfect accuracy with only 16 train samples per class. From the figure, it is also evident that none of the CNNs attained perfect accuracy even with a training set as large as 256 samples per class. This experiment shows that the proposed method requires very few training data to outperform the deep learning based classification methods.

Robust to Out-of-Distribution Samples
To demonstrate the robustness to out-of-distribution examples, we used 4th degree polynomials to generate data, but varied the magnitude of the confounding factors (i.e. the coefficients of the polynomials) to generate a gap between training and testing distributions. The 'in distribution' set used during the training process consisted of signals with relatively smaller confounding factors (smaller coefficient values) than the 'out distribution' set used for testing. A similar concept was used in [16] to perform out-of-distribution testing. Fig. 3 shows that the proposed method outperformed the other methods by a greater margin than before under this modified experimental scenario.

Application: ECG Signal Classification
The proposed SCDT-NS classification technique can be applied to classify 1D signals in many applications. One such application is electrocardiogram (ECG) signal classification. To evaluate the performance of the proposed model on ECG data, we used a publicly available dataset [20] reported in [21]. This dataset was collected from MIT-BIH Arrhythmia database [22] hosted at PhysioNet [23]. Although, the dataset has 17 different classes, in this paper we used 3 classes with three highest number of ECG fragments: 1) Normal sinus rhythm (NSR), 2) Atrial fibrillation (AFIB), and 3) Left bundle branch block beat (LBBBB). PQRST locations were detected using the method described in [24] to segment the heartbeats from the ECG fragments. Then we applied the classification methods to classify the ECG heartbeat segments. Note that during experiments, we made sure data from same patients was not included in both training and test sets. This step is often not strictly followed in the computer science (machine learning) literature. Mixing data from the same patient in both the test and training samples tends to lead to high accuracies (∼ 97%), which is attained by all the methods compared here.

Conclusion
In this paper, we introduced a new method for 1D signal classification problems. The proposed approach employs a nearest subspace search algorithm in the signed cumulative distribution transform (SCDT) space to produce a noniterative solution to the classification problem. Several experiments show that the proposed method not only outperforms popular CNN-based methods but also is data efficient and robust to out-of-distribution samples. Moreover, it does not require prior knowledge of the templates of the signal classes or the deformations present in the data to render better accuracy than the comparative methods. Future work will include studying ways to specify general mathematical categories for the space of signal deformations G, as well as way to learn them more efficiently.