dataesr/scientific-paragraphs-categorization huggingface dataset:
Introduction We begin by formalizing the task at hand: Problem Statement: Given an unlabeled time series dataset D; find the value of w that maximizes the clustering quality. Where ties exist, report the smallest w. There are many measures of clustering quality; however, measures based on sum-ofsquared residual error do not allow for meaningful comparisons among clusterings with different values of w. Here, we wish to optimize the objective "correctness" of the clustering. Typically, we will not have access to this ground-truth (by definition); however, for the datasets we consider in this work, we do have class labels that allow us to do a post-hoc analysis. Without loss of generality, we will use Rand-Index as the internal scoring function we optimize, and for the external post-hoc analysis of the effectiveness of our ideas.
Thus, to be sure that we get enough actionable annotations to guide the search in the clustering space, we must ask the user to annotate hundreds or thousands of objects. This is clearly undesirable as the user may be unwilling or unable to provide such an effort. We introduce a novel semi-supervised clustering method for time series that does all the clustering up-front and only then asks for user input. This allows us to ask the user to annotate only informative pairs. Our proposed method offers the following advantages: • Our approach is independent of the clustering algorithm. We are only learning the best w for a particular dataset; therefore, we can produce the final clustering using essentially 1  any partitional, hierarchical, spectral, or density-based clustering. • The annotations are solicited after the clustering has been performed, meaning that we only ask the user to annotate pairs that matter.
Clustering quality measure We use Rand-Index as the internal scoring function we optimize, and for the external post-hoc analysis of the effectiveness of our ideas. The Rand-Index penalizes both false positive and false negative decisions during clustering, and therefore it is not possible to optimize in a trivial way. There are some proposed variants, including the Adjusted Rand-Index  (Vinh 2010) ; however, the classic Rand-Index  (Rand 1971 ) is widely accepted and used. Moreover, at least internally, we are only interested in the relative improvements in clustering quality. With Rand-Index, we assess clustering quality based on a series of decisions, one for each of the unique pair of objects in the dataset. A true positive (TP) decision means that we assign two similar objects to a same cluster.
Choosing constraints As we have noted above, the fact that we only need to see the constraints after the clusterings have been performed gives us a unique opportunity to optimize the user time and attention. For every possible pair of time series in our dataset, we can build a constraint vector based on whether the pair are assigned to the same cluster or not (hereafter referred to as linked or not-linked). A candidate constraint be a binary vector C, whose length is the number of values of w under consideration. A '0' at the i th position in C indicates that the pair of time series was not linked under DTW i , whereas a '1' indicates that it was linked. In Fig. 11 , we can see four candidate constraints. Constraint (A) is vacillating, and it is likely of little use to us. We can interpret it as being "volatile," since it constantly switches between linked and not-linked for different values of w.
These constraints are rare and likely indicate a "hybrid" object on the cusp between two distinct clusters. Constraints (B) and (C) are always/never linked, respectively. It is pointless to show such constraints to the user, since they "vote" equally for all values of w. In most datasets we consider, the majority (often the vast majority) of constraints are of these two types. With a little introspection, it is obvious that most constraints are non-volatile, as it suggests that most of the objects being clustered are in stable clusters. If all constraints were highly volatile, it would be difficult to select any clustering that is meaningful in any sense. In contrast to the constraints above, constraint (D) seems to be an ideal constraint. For datasets that need warping invariance, it can be interpreted as: a value for w that is between zero to six is not enough, but anything seven or above works.
Fig. 12  illustrates examples of time series from the Trace dataset that are shown to the user. We hope to avail of the user's domain knowledge, intuitions, and pattern recognition ability. For Fig. 12. left, the user may realize that while the two time series are superficially different, most of the difference can be explained by warping the time axis. Therefore, we would expect the user to annotate this as "must-link. " In contrast, for Fig. 12. right, we hope the user would recognize that despite the similarity of the two time series (they have a relatively small Euclidean distance), one time series misses the short peak that seems to characterize the other sequence. Naturally, we want our algorithm to be insensitive to occasional annotation mistakes. We consider this issue in Section 3.
𝑃𝑉 𝑖 = 𝑁𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑈𝐴 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠 𝑐𝑜𝑟𝑟𝑒𝑐𝑡𝑙𝑦 𝑐𝑙𝑢𝑠𝑡𝑒𝑟𝑒𝑑 𝑎𝑡 𝑤 𝑖 𝑇𝑜𝑡𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑈𝐴 𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑡𝑠 We can see the incremental improvement (anytime algorithm) property of the algorithm by examining the predictions we make for w as we obtain more user annotations. Fig. 13  shows an example of this for two datasets. Note that in both cases, the "shape" of our prediction vector converges to the shape of the ground truth Rand-Index curve after sixteen user annotations. However, it is important to note that this is not necessary for our algorithm to be successful. All we require is that the prediction of the best setting for w concurs with the ground truth. Recall that this prediction is the location of the maximum value with ties broken by choosing the smallest w.
It suffices because it is better than doing nothing. In this spirit, we present a technique to learn w from pseudo annotations. The basic idea is simple. Before we perform any clustering, we randomly sample objects from the dataset. For each object O, we create a copy of it that we denote as Ō. We add some warping to Ō, and place it into the dataset with the (pseudo) constraint must-link(O, Ō). Since we know that object Ō is just a minor variant of O, we can safely assume that if Ō occurred naturally, it would have been in the same cluster as O, and our must-link constraint was warranted. At this point, the list of "user annotations" is like those produced in Table  1. This idea seems to have a tautological paradox to it. It seems that if we add w amount of warping to the dataset, we will discover w warping in that dataset.
However, this is not the case, as discussed Section 2. 2. 3. In line 1, we ensure that the data has an arbitrary structure in its ordering. In line 2, we enter a loop that replaces every second data object with a warped version of the data object that precedes it. Since these two objects differ only by the existence of some warping, we annotate them as 'must-link'. Note that this algorithm produces a new dataset Dnew, which is the same size as D. This is important, as the size of the dataset affects the best setting for w (recall Section 2. 2. 2). The algorithm also outputs PUA, a set of pseudo annotations for Dnew. PUA is essentially identical to UA produced in Table  1  except its annotations are produced without human interventions. Note that with this method of generating annotations, all PUAs are must-link constraints.
Fig. 14  shows some examples of synthetic time series with warping added, and for concreteness Table  3  contains the actual MATLAB code used to add warping. We call this variant of our ideas the PUA (Pseudo User Annotation) algorithm. How well does this idea work compared to using true human annotations? The human annotations are constraints between two real data objects, which is undoubtedly advantageous. However, in most cases, we have only a fraction of D annotated this way. In contrast, every item in Dnew has an annotation, which provides this approach with an advantage if we choose to use them all. Fig. 15  shows how this idea works with Trace and Two Patterns. Here we use 64 out of 1,824 pseudo constraints available for Two Patterns to reach the correct value w = 8. Using all 27 constraints available for Trace, we arrive at w = 15, which gives a Rand-Index of 0.
Related work Zhou et al. recently introduced a paper entitled "Enhancing time series clustering by incorporating multiple distance measures with semi-supervised learning"  (Zhou et al. 2015). However, the method is perhaps better seen as an ensemble-based method for time series clustering. The method has many parameters (at least four: α, β,p,w), and it is not clear how they affect the performance. They only test on twelve of the datasets we consider here, but in every case, they do not perform as well as our proposed approach. For example, for Trace, they obtain a best Normalized Mutual Information (NMI) 2 score of 0. 813, whereas, as we will show in Section 3. 2, we can easily obtain a near-perfect NMI of 0. 97. Beyond this effort, we are not aware of any other work like our approach for semisupervised learning for time series clustering.
Preliminary tests We denote our algorithm as cDTW ss (DTW Semi-Supervised). We compare to two rivals by clustering with cDTW 0 (Euclidean distance) and clustering with cDTW 10. These rival methods account for virtually everything in the literature. For example, R. It is important to state that the only difference between our approach and the two rival methods is the access to the labeled constraints. Otherwise, the underlying clustering algorithm, TADPole  (Begum et al. 2015) , is identical for all approaches and completely deterministic  (Rodriguez and Laio 2014). Thus, any improvements obtained can be completely attributed solely to our ideas. We can measure success as follows. For each dataset, we compute the maximum Rand-Index obtainable under any setting of w from 0 to 20 (as our result shows, and in concurrence with the literature, most datasets in the UCR Archive do not require w greater than 10%  (Ratanamahatana and Keogh 2005) ).
For example, in Fig. 1 , the maximum Rand-Index is 1. 0 for Two Patterns and 0. 89 for Swedish Leaf. Then, we can compute a score, the ratio of the Rand-Index achieved by an approach over this optimal achievable value. The closer this ratio is to 1. 0, the better; we call an approach a success if its score is 0. 99 or higher. We begin by considering the utility of our approach if given only sixteen labels; this is about the amount a person can annotate in one minute. We summarize the result in Table  4. With sixteen labeled constraints, we achieve success of 46 out of 102 datasets, with cDTW 0 and cDTW 10 achieving 34 and 31, respectively. If we double the number of constraints to thirty-two, we extend our success to 50 datasets. Recall that thirty-two annotations require only a few minutes of user effort, and they typically represent less than 0.
0001% of the labeled pairs. Despite this significant improvement over the state-of-the-art, it is natural to wonder about the cases we did not score within 0. 99 of the optimal. In some cases, we just missed out. For example, using thirty-two constraints on the TwoLeadECG, Cricket_Y, NonInvasiveFatalECG_2, and 50words datasets, we were within at least 0. 98 of the optimal. Fig. 16  The Rand-Index vs. the warping window width for three small datasets. Contrast the variability of the curves with the relatively smooth curves shown in Fig. 1. However, in some cases, we do achieve significantly worse than the optimal. Essentially, all such cases can be attributed to very small datasets (or small, relative to the number of clusters). As shown in Fig. 16 , this tends to result in clusterings that are very unstable with small changes in w.
The fact that small datasets have poor stability when clustered is well known (Von Luxburg 2010), and the issue is orthogonal to our contributions. We speculate that if the best value of w is poorly defined and unstable, it may be impossible for any algorithm to learn it. Nevertheless, even in such datasets, we do not do worse than the lower scoring of our two rivals. Rand-Index (the ground truth) The three sequences are dithered for visual clarity. Only their amplitude is original, their offset has no meaning. Increasing values of w 0 5 10 15 20 Lighting2 MedicalImages ScreenType.
Robustness to incorrect constraints The experiments in the previous section assume that all the constraints the user provided are correct. However, this assumption may be unwarranted in many circumstances. Our annotator may indicate that two items cannot-link when they are in the same class, and really must-link, or vice versa. To investigate the robustness of our approach, we revisit some of the experiments above, but this time, we randomly make some of the constraints incorrect. As shown in Fig. 17 , for the ItalyPowerDemand and MiddlePhalanxOutlineAgeGroup dataset, we can achieve near perfect results even if a fraction of the constraints is incorrect. Among the 16 pairs of time series chosen for annotation, we single out the must-link pairs and randomly change the label of some pairs from this list to cannotlink.
Then, we observe the mean best w predicted averaged over 10 runs. We find that it is consistently 0 for the ItalyPowerDemand dataset and 1 for the MiddlePhalanxOutineAgeGroup, which concurs with the objective ground truth. As a practical matter, any system used to garner user feedback should allow three choices to the user, cannot-link, must-link and I-don't-know, which would further enhance robustness by giving the user a chance to simply skip over the difficult or ambiguous case.
𝐷𝑇𝑊 𝐼 (𝑄, 𝐶) = ∑ 𝐷𝑇𝑊(𝑄 𝑚 , 𝐶 𝑚 ) 𝑀 𝑚=1 In Fig. 18 , we consider the 4,480-objects, three-dimensional UWave dataset  (Liu et al. 2009 ), which has become a benchmark for gesture recognition in the last five years. We also consider the Handwriting Accelerometer dataset using all three of the available accelerometer channel readings. Even though all dimensions are not necessary for this task, we only wish to illustrate that our algorithm can correctly predict a good value for w. While there are just over one million possible pairwise constraints, our algorithm can find the optimal w with only sixteen annotations. Note that here, the amount of warping is critical. Too much or too little warping yields poor results. This fact might explain the puzzlingly diversity of accuracy claims made for this dataset in the literature.
" However, simply choosing a better value of w offers improvements that dwarf the claimed improvements of the SDB algorithm. For example, for the Trace dataset, they compare five clustering algorithms using DTW vs. the same five clustering algorithms using SBD. The former achieves Rand-Index values of {0. 87, 0. 75, 0. 75, 0. 83, 0. 77}, and the latter achieves {0. 87, 0. 87, 0. 87, 0. 83, 0. 87}, suggesting an advantage for SBD. However, using the exact same split of the Trace data, we can beat all these approaches significantly without any human intervention, as our PUA algorithm can achieve a 0. 99 Rand-Index. Similarly, we have a large margin of improvements for Two Patterns. For example,  Paparrizos and Gravano (2015)  has the DTW-based algorithms achieving Rand-Index values of {0. 87, 0.
59, 0. 62, 0. 97, 0. 65}, and SBD variants achieving {0. 25, 0. 54, 0. 64, 0. 67, 0. 66}, but PUA learns that cDTW 8 is the best setting and achieves a perfect 1. 0. In a publication of ICML 2011  (Li and Prakash 2011) , the authors introduce a clustering method called CLDS (Complex-valued Linear Dynamical Systems) and claim that the "approach produces significant improvement in clustering quality, 1. 5 to 5 times better than well-known competitors on real motion capture sequences. " The method involves several layers of complicated sub-procedures, so we refer the interested readers to the original paper. The authors demonstrate the utility of their work on the publicly available MOCAPANG-Subject-35, right-foot-marker dataset. The evaluation method is based on the conditional entropy 3 , and they score 0.
We are simply demonstrating that when using any reasonable choice for w with an off-the-shelf clustering method, cDTW can be a very competitive method for the datasets the original authors used to validate their method. A recently published work measures the accuracy of eleven carefully optimized clustering algorithms on the Trace dataset, of which eight use DTW as the distance measure  (Ferreira and Zhao 2016). The Rand-Index of these methods are {0. 87, 0. 76, 0. 86, 0. 86, 0. 91, 0. 86, 0. 86, 0. 87, 0. 87, 0. 84, 0. 75}. However, as noted above, using the exact same split of Trace, we can beat all these approaches without any human intervention, as our PUA algorithm can achieve a Rand-Index of 0. 99. shown in Fig. 19 , with 16 constraints given by the user, we find cDTW 1 to be a good choice and achieve a significantly better NMI of 0.
79 (omitted for brevity: in fact, any number of constraints above four also works this well). Why did the authors of this paper dismiss DTW as a distance measure? They noted that DTW "is one order of magnitude slower than calculating [Euclidean distance]," and further noted that it only took them a brief 3. 1 seconds to cluster this dataset. However, this dataset took several years to collect, and many days of careful human effort in preprocessing. Given that, the difference between taking 3. 1 seconds and taking 30 seconds to do the clustering seems completely inconsequential (but also see Section 3. 2. 5). Of course, the authors are correct in noting that there is sometimes a need for better speed and scalability. However, in many domains, the tradeoff between speed and accuracy will still favor accuracy.
For example, in the UCR Archive, many datasets took hours, days, or weeks to collect (InsectWingbeatSound, ElectricDevices, Fish, Phoneme, etc. ), so the few minutes needed to cluster them is negligible if we can improve accuracy. Finally, a paper in AAAI tests four algorithms for time series clustering; two are based on DTW  (Zhong et al. 2016 ). These algorithms yield NMI scores of {0. 53, 0. 45, 0. 54, 0. 64} for the Trace dataset, but our PUA algorithm can achieve an almost perfect NMI score of 0. 97 (Rand-Index = 0. 99) on this same dataset. These five examples strongly support our claim. Finding a good value for w (using our method, or any method) can produce improvements that make almost all other changes inconsequential.
Thus, we can perform the clusterings in order, from w = 0 to w = 20, at each stage by using any cDTW w calculations as lower bounds in the next level. Thus, the time overhead for our ideas is only slightly more than a single highly optimized clustering. Even to the mustcalculated DTW that remains after the lower-bound pruning procedure, we can still apply the work of  Silva et al. (2018)  to dismiss unpromising alignments. Finally, we note that there are a wide variety of DTW implementations, and the efficiency differences between them overshadow the small overhead of our approach. For example, a recently published paper that tests a DTW-based clustering on some of the datasets we consider, and it notes "several experiments were unable to return results within 20 days"  (Zhong et al. 2016 ).
Case Study: Gesture-based Identification We present a case study in the context of gesture-based identification. The goal is to identify/authenticate users based on loosely defined gestures such as "picking-up" or "shaking" a handheld device  (Guna, Humar, and Pogačnik 2012). Such a gesture-based identification system can be well suited for personalized applications that only target a small group of users and are not security critical. User login for home sharing Netflix is an example. The dataset was kindly shared by the authors of the paper  (Guna, Humar, and Pogačnik 2012) , whose preliminary experiment results show the feasibility of implicit gesturebased user identification. The subset that we use is available for download on our supporting webpage (Supporting Page 2018). The dataset consists of an accelerometer recording of 10 subjects; each performs a "shake" gesture 10 times with a Nintendo Wii Mote remote controller.
The users are instructed to shake the control device in no predefined way, just as they would normally do in their everyday life. Fig. 20  displays some instances of a shake gesture with acceleration measured in three axes. For simplicity, we only use an x-axis reading for the results presented in Fig. 21. quality for this dataset is 0. 92 at w = 8. Using a w = 0 yields a much poorer Rand-Index of only 0. 82. By applying our method to learn w, we will eventually learn that w = 5 is the best, and it gives a Rand-Index of 0. 91 (Fig. 21. bottom). We count this a success, because the achieved Rand-Index scores 0. 99 of the optimal Rand-Index. In retrospect, this is clearly a dataset that would benefit from warping invariance. Although the chosen gesture is identical for all users, there exists a subtle systematic variation in how it is performed by each individual, which explains the good clustering result.
For instances contributed by a particular subject, there may be shifting in the time axis that a small amount of warping can account for. In this case, a suitable choice of w can make a significant difference in the final cluster assignment. 4 Learning Warping Window Width for Time Series Classification universally used collection of benchmark datasets  (Chen et al. 2015). There are now many independent comprehensive empirical studies demonstrating a strong performance of NN-DTW  (Bagnall and Lines 2014; H. Ding et al. 2008; Lines and Bagnall 2015). Nevertheless, in recent years, there have been many proposed algorithms that are able to improve upon NN-DTW's accuracy in the general case. Recent papers note that many claims do not hold under rigorous statistical evaluations: "Based on experiments on 77 problems, we conclude that 1-NN with Euclidean distance is fairly easy to beat but 1-NN with DTW is not"  (Bagnall and Lines 2014)  or "the received wisdom is that DTW is hard to beat"  (Bagnall et al.
2017 ). We will show that it is possible to learn w more robustly; this is particularly useful when the training data is limited. Our approach is based on resampling the training data. Resampling is normally ill advised in small datasets, where using only a subset of the data compounds all the problems inherent with working with limited data. However, we can address this issue by replacing the non-sampled data with synthetic replacements. Our idea is simple, making it very amendable to existing time series classification tools, but as we will show, the performance improvements it allows are statistically significant.
However, this is to mitigate convolutional neural network (CNN) weakness "… that they need a lot of training data to be efficient"  (Guennec, Malinowski, and Tavenard 2016). The synthetic examples do help improve accuracy over the non-augmented datasets; still, it remains unclear if CNNs are generally competitive for time series problems  (Bagnall and Lines 2014) , and this issue is orthogonal to the claims of this work.
An intuition to our proposed approach To understand the effect(s) of dataset size on the most suitable warping window width, we performed the following experiment. We begin with a simple experiment that determines whether what we hope achieve is possible, and it also intuition on how to achieve it. Consider the Two Patterns dataset. Because it has 1000 training objects, we will denote it as Two Patterns 1000. As shown in Fig. 22. left, Two Patterns 1000 is a dataset in which we can correctly learn the best maximum warping window with cross-validation. Suppose the dataset had significantly fewer training instances; we will call this dataset Two Patterns 20. We would expect that the holdout error-rate would increase, and we were advised by Ratanamahatana et al. that we should expect the best value for w to go up slightly  (Ratanamahatana and Keogh 2005).