Pratyay Banerjee, Masud Moshtaghi, Shivashankar Subramanian, Amita Misra, Ankit Chadha. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Short bursts of repeating patterns [intervals of recurrence (IoR)] manifest themselves in many applications, such as in the time-series data captured from an athlete's movements using a wearable sensor while performing exercises. We present an efficient, online, one-pass, and real-time algorithm for finding and tracking IoR in a time-series data stream. We provide a detailed theoretical analysis of the behavior of any IoR and derive fundamental properties that can be used on real-world data streams. We show that why our method, unlike current state-of-the-art techniques, is robust to variations in repeats of the same pattern adjacent to each other. To evaluate our algorithm, we build a wearable device that runs our algorithm to conduct a user study. Our results show that our algorithm can detect intervals of repeating activities on edge devices with high accuracy (over 70% F1 -Score) and in a real-time environment with only a 1.5-s lag. Our experimental results from real-world datasets demonstrate that our approach outperforms state-of-the-art algorithms in both accuracy and robustness to variations of the signal of recurrence.

Enabling cross-lingual NLP tasks by leveraging multilingual word embedding has recently attracted much attention.An important motivation is to support lower resourced languages, however, most efforts focus on demonstrating the effectiveness of the techniques using embeddings derived from similar languages to English with large parallel content.In this study, we present a noise tolerant piecewise linear technique to learn a non-linear mapping between two monolingual word embedding vector spaces.We evaluate our approach on inferring bilingual dictionaries.We show that our technique outperforms the state of the art in lower resourced settings with an average improvement of 3.7% for precision @10 across 14 mostly low resourced languages.

Cluster analysis is used to explore structure in unlabeled batch data sets in a wide range of applications. An important part of cluster analysis is validating the quality of computationally obtained clusters. A large number of different internal indices have been developed for validation in the offline setting. However, this concept cannot be directly extended to the online setting because streaming algorithms do not retain the data, nor maintain a partition of it, both needed by batch cluster validity indices. In this paper, we develop two incremental versions (with and without forgetting factors) of the Xie-Beni and Davies-Bouldin validity indices, and use them to monitor and control two streaming clustering algorithms (sk-means and online ellipsoidal clustering), In this context, our new incremental validity indices are more accurately viewed as performance monitoring functions. We also show that incremental cluster validity indices can send a distress signal to online monitors when evolving structure leads an algorithm astray. Our numerical examples indicate that the incremental Xie-Beni index with a forgetting factor is superior to the other three indices tested.

Training machine leaning algorithms on augmented data fromdifferent related sources is a challenging task. This problemarises in several applications, such as the Internet of Things(IoT), where data may be collected from devices with differentsettings. The learned model on such datasets can generalizepoorly due to distribution bias. In this paper we considerthe problem of classifying unseen datasets, given several labeledtraining samples drawn from similar distributions. Weexploit the intrinsic structure of samples in a latent subspaceand identify landmarks, a subset of training instances fromdifferent sources that should be similar. Incorporating subspacelearning and landmark selection enhances generalizationby alleviating the impact of noise and outliers, as well asimproving efficiency by reducing the size of the data. However,since addressing the two issues simultaneously resultsin an intractable problem, we relax the objective functionby leveraging the theory of nonlinear projection and solve atractable convex optimisation. Through comprehensive analysis,we show that our proposed approach outperforms stateof-the-art results on several benchmark datasets, while keepingthe computational complexity low.

With the proliferation of sensors and the increased connectivity of citizens, many global cities are increasingly adopting Smart City initiatives. Such initiatives provide real-time monitoring capabilities, and effective modelling techniques allow the prediction of future states in a city. For example, urban electricity smart meter data can be utilised to predict future demand in order to facilitate capacity planning. However, the accuracy of this foresight is often marred by low quality and missing sensor data in real-world systems. In this work, we focus on the problem of reliable forecasting by mitigating the effect of missing data on forecast accuracy. In order to mitigate the effects of missing data, we develop a multi-task learning scheme to jointly learn Gaussian Process Regression models between highly correlated sensors. We demonstrate that our methods are robust in a variety of error generation scenarios. We validate our methods based on publicly available and real-world datasets related to electricity smart meters in a university campus and pedestrian counts in a global city, where we achieve significant improvement over competitive baselines and other effective forecasting methods.

Anomaly detection in data streams has become a major research problem in the era of ubiquitous sensing. We are collecting large amounts of data from non-stationary environments, which makes traditional anomaly detection techniques ineffective. In this paper we propose an unsupervised cluster-based algorithm for modelling normal behaviour in non-stationary data streams and detecting anomalous data points. We show that our method scales linearly with the number of observed data points, while the complexity of our model is independent of the size of the data stream. We have employed a selective clustering approach to optimize the computation time needed to model the normal data. Our experiments on large-scale synthetic and real life datasets show that the accuracy of the proposed algorithm is comparable to the state-of-the-art techniques reported in the literature while providing substantial improvements in terms of computation time.

In time-series forecasting, regression is a popular method, with Gaussian Process Regression widely held to be the state of the art. The versatility of Gaussian Processes has led to them being used in many varied application domains. However, though many real-world applications involve data which follows a working-week structure, where weekends exhibit substantially different behavior to weekdays, methods for explicit modelling of working-week effects in Gaussian Process Regression models have not been proposed. Not explicitly modelling the working week fails to incorporate a significant source of information which can be invaluable in forecasting scenarios. In this work we provide novel kernel-combination methods to explicitly model working-week effects in time-series data for more accurate predictions using Gaussian Process Regression. Further, we demonstrate that prediction accuracy can be improved by constraining the non-convex optimization process of finding optimal hyperparameter values. We validate the effectiveness of our methods by performing multi-step prediction on two real-world publicly available time-series datasets - one relating to electricity Smart Meter data of the University of Melbourne, and the other relating to the counts of pedestrians in the City of Melbourne.

Efficient localized data modeling techniques in Internet of Things (IoT) applications enable the nodes to change their behavior upon observing events of interest. Additionally, battery-powered IoT nodes can conserve their energy resources by limiting their data communications to specific events. Despite the real-time nature of the data collected in the IoT and limited memory and computational resources, most of the current data modeling approaches for the IoT involve batch training. Recently, an online efficient anomaly detection technique called iterative data capture anomaly detection has been proposed for environmental sensing and monitoring applications. However, this approach cannot handle changing environments. So far, efforts in extending this algorithm to adapt to changes in the environment have met with limited success. In this paper, we generalize this algorithm to adapt to changes in the data stream by exponentially weighting past observations. We illustrate the proposed algorithm with numerical results on both real-life and simulated data sets, which demonstrate the efficiency and accuracy of our approach compared to existing methods.

The intrinsic nature of streaming data requires algorithms that are capable of fast data analysis to extract knowledge. Most current unsupervised data analysis techniques rely on the implementation of known batch techniques over a sliding window, which can hinder their utility for the analysis of evolving structure in applications involving large streams of data. This research presents a novel data clustering algorithm, which exploits the correlation between data points in time to cluster the data, while maintaining a set of decision boundaries to identify noisy or anomalous data. We illustrate the proposed algorithm for online clustering with numerical results on both real-life and simulated datasets, which demonstrate the efficiency and accuracy of our approach compared to existing methods.

This paper presents a study to determine users' attitudes toward smart devices. We conducted a web survey to elicit users' ratings for devices and combinations of tasks and devices; the results of this survey led to the development of a Recommender System (RS) for smart devices for particular tasks. We investigated user- and item-based Collaborative Filters, and compared their performance with that of global and demographic RS baselines. We then developed a technique based on Principal Components Analysis to select a subset of the original survey questions that supports the prediction of users' ratings for device-task combinations. Our results show that the accuracy of an RS that asks only a small subset of the survey questions is similar to that of an RS that predicts users' answers to one survey question on the basis of their answers to all the other questions.

The C index is an internal cluster validity index that was introduced in 1970 as a way to define and identify a “best” crisp partition on n objects represented by either unlabeled feature vectors or dissimilarity matrix data. This index is often one of the better performers among the plethora of internal indices available for this task. This paper develops a soft generalization of the C index that can be used to evaluate sets of candidate partitions found by either fuzzy or probabilistic clustering algorithms. We define four generalizations based on relational transformations of the soft partition and, then, compare their performance to eight other popular internal fuzzy cluster indices using two methods of comparison (internal “best-c ” and internal/external (I/E) “best match”), six synthetic datasets, and six real-world labeled datasets. Our main conclusion is that the sum-min generalization is the second best performer in the best-c tests and the best performer in the I/E tests on small data.

Pedestrians movements have a major impact on the dynamics of cities and provide valuable guidance to city planners. In this paper we model the normal behaviours of pedestrian flows and detect anomalous events from pedestrian counting data of the City of Melbourne. Since the data spans an extended period, and pedestrian activities can change intermittently (e.g., activities in winter vs. summer), we applied an Ensemble Switching Model, which is a dynamic anomaly detection technique that can accommodate systems that switch between different states. The results are compared with those produced by a static clustering model (HyCARCE) and also cross-validated with known events. We found that the results from the Ensemble Switching Model are valid and more accurate than HyCARCE.

Evolvable Takagi-Sugeno (T-S) models are fuzzy-rule-based models with the ability to continuously learn and adapt to incoming samples from data streams. The model adjusts both premise and consequent parameters to enhance the performance of the model. This paper introduces a new methodology for the estimation of the premise parameters in the evolvable T-S (eTS) model. Incremental updates for the weighted sample mean and inverse of the covariance matrix enable us to construct an evolvable fuzzy rule base that is used to detect outliers and regime changes in the input stream. We compare our model with Angelov's eTS+ model with artificial and real data.

ABSTRACT Two new incremental models for online anomaly detection in data streams at nodes inwireless sensor networksare discussed. These models are incremental versions of a model that uses ellipsoids to detect first, second, and higher‐ordered anomaliesin arrears. The incremental versions can also be used this way but have additional capabilities offered by processing data incrementally as they arrive in time. Specifically, they can detect anomalies ‘on‐the‐fly’ in near real time. They can also be used to track temporal changes in near real‐time because of sensor drift, cyclic variation, or seasonal changes. One of the new models has a mechanism that enables graceful degradation of inputs in the distant past (fading memory). Three real datasets from single sensors in deployed environmental monitoring networks are used to illustrate various facets of the new models. Examples compare the incremental version with the previous batch and dynamic models and show that the incremental versions can detect various types of dynamic anomalies in near real time. Copyright © 2012 John Wiley & Sons, Ltd.

One of the applications that motivates this research is a system for detection of the anomalies in wireless sensor networks (WSNs). Individual sensor measurements are converted to ellipsoidal summaries; a data matrix D is built using a dissimilarity measure between pairs of ellipsoids; clusters of ellipsoids are suggested by dark blocks along the diagonal of an iVAT (improved Visual Assessment of Tendency) image of D; and finally, the single linkage algorithm extracts clusters from D, using the iVAT image as a guide to the selection of an optimal partition. We illustrate this model for higher dimensional data with synthetic, real and benchmark data sets. Our examples show that two of the four measures, viz, Focal distance and Bhattacharyya distance, provide very similar and reliable bases for estimating cluster structures in sets of higher dimensional ellipsoids, that single linkage can successfully extract the indicated clusters, and that our model can find both first and second order anomalies in WSN data.

Wireless Sensor Networks (WSNs) provide a low cost option for gathering spatially dense data from different environments. However, WSNs have limited energy resources that hinder the dissemination of the raw data over the network to a central location. This has stimulated research into efficient data mining approaches, which can exploit the restricted computational capabilities of the sensors to model their normal behavior. Having a normal model of the network, sensors can then forward anomalous measurements to the base station. Most of the current data modeling approaches proposed for WSNs require a fixed offline training period and use batch training in contrast to the real streaming nature of data in these networks. In addition they usually work in stationary environments. In this paper we present an efficient online model construction algorithm that captures the normal behavior of the system. Our model is capable of tracking changes in the data distribution in the monitored environment. We illustrate the proposed algorithm with numerical results on both real-life and simulated data sets, which demonstrate the efficiency and accuracy of our approach compared to existing methods.

Fuzzy boundaries and unpredictable anomalies displayed in the raw sensor data make the process of defining a strong ellipsoid boundary for the raw data in the ellipsoid-based anomaly detection algorithms in wireless sensor networks a difficult problem. We have shown, using synthetic and real sensor data, that the random variable that represents the difference between any two randomly selected raw data points follows an identically independently distributed Gaussian distribution. We have used this statistical property to calculate ellipsoid boundaries for the Gaussian distribution which displays a robust ellipsoid shape and then to map each point of the distribution function to its corresponding raw data point to isolate anomalies from the sensor data. We have demonstrated the performance of the proposed approach by comparing it with the standard approach using both synthetic datasets and real Intel Berkeley Research Laboratory and Grand St Bernard datasets.