Time series anomaly detection has received substantial attention over the past two decades, leading to the development of hundreds of algorithms. However, comprehensively understanding this vast landscape remains challenging, particularly for non-experts and novices. In this demonstration paper, we present InTimeAD, an interactive web application that provides access to more than 30 state-of-the-art time series anomaly detection algorithms. InTimeAD is intended to explore the performance of existing as well as custom anomaly detection models in an interactive, hands-on manner. By lowering the entry bar, we support practitioners overwhelmed by the large number of existing techniques, while providing a platform for researchers to rapidly analyze their novel anomaly detection algorithms.

Neurosymbolic AI integrates low-level perception with high-level reasoning, making it well suited for tasks that involve both visual recognition and domain-specific constraints. One such task is the digitization of structured documents like handwritten tax forms, which must satisfy numerous known rules. While neural OCR models are becoming increasingly capable at reading handwritten text, they fail to enforce such constraints on their output, leading to invalid predictions. By combining neural OCR outputs with grammar-based stochastic reasoning over these constraints, neurosymbolic OCR can correct both neural perception errors and user mistakes. This paper demonstrates the application of DeepStochLog, a neurosymbolic AI system, to digitize handwritten IRS 1040 tax forms. Its ability to incorporate background knowledge and ease of use make DeepStochLog an attractive framework for constrained OCR applications.

Tree ensembles (e.g., gradient boosting decision trees) are often used in practice because they offer excellent predictive performance while still being easy and efficient to learn. In some contexts, it is important to additionally optimize their size: this is specifically the case when models need to have verifiable properties (verification of fairness, robustness, etc. is often exponential in the ensemble's size), or when models run on battery-powered devices (smaller ensembles consume less energy, increasing battery autonomy). For this reason, compression of tree ensembles is worth studying. This paper presents LOP, a method for compressing a given tree ensemble by pruning or entirely removing trees in it, while updating leaf predictions in such a way that predictive accuracy is mostly unaffected. Empirically, LOP achieves compression factors that are often 10 to 100 times better than that of competing methods.

Time series semantic segmentation is the task of extracting time intervals from the time series data that share a similar meaning within the application domain in an unsupervised manner. State-of-the-art algorithms typically treat this problem as change point detection, resulting in discrete state transitions. However, in real-world applications, states often transition gradually. This leads to a novel, more challenging variation of the traditional time series segmentation task, for which we present PaTSS, a novel, domain-agnostic algorithm to uncover those gradual state transitions. PaTSS learns a distribution over the semantic segments based on an embedding space derived from mined sequential patterns. An extensive experimental evaluation on 107 benchmark time series shows that PaTSS is capable of detecting gradual state transitions, a task current methods are unable to perform.

Abstract There has been an explosion of data collected about sports. Because such data is extremely rich and complex, machine learning is increasingly being used to extract actionable insights from it. Typically, machine learning is used to build models and indicators that capture the skills, capabilities, and tendencies of athletes and teams. Such indicators and models are in turn used to inform decision-making at professional clubs. Designing these indicators requires paying careful attention to a number of subtle issues from a methodological and evaluation perspective. In this paper, we highlight these challenges in sports and discuss a variety of approaches for handling them. Methodologically, we highlight that dependencies affect how to perform data partitioning for evaluation as well as the need to consider contextual factors. From an evaluation perspective, we draw a distinction between evaluating the developed indicators themselves versus the underlying models that power them. We argue that both aspects must be considered, but that they require different approaches. We hope that this article helps bridge the gap between traditional sports expertise and modern data analytics by providing a structured framework with practical examples.

A modern vehicle contains a large number of electronic control units and sensors that are connected to cloud environments. These electronic units generate a huge amount of data that can be leveraged to identify the current driver and adapt to their behavior. For example, driver identification can improve the accuracy of range estimation in battery electric vehicles. This study focuses on identifying drivers based on their behaviour by using multivariate time series data acquired by the sensors available in the vehicle. We propose two different classifiers: one based on Bi-directional stacked Long Short-Term Memory with Attention mechanism (BiLSTM-A) and another based on a Modified Time Series Transformer (MTST). We perform driver identification in two different ways: 1) by applying a classifier on a single time segment; and 2) by using our proposed time-shift ensembles to combine predictions made from multiple time segments. We experimentally evaluate the proposed techniques on a publicly available dataset that comprises 10 drivers. By using all appropriate features, the proposed BiLSTM-A and MTST classifiers identify the driver with an accuracy of 55% and 73%, respectively, from a single time segment of 60 seconds duration. Time-shift ensembles increase the accuracy substantially, to 92% for BiLSTM-A and 97% for MTST when a 460-second time period is used for each prediction. We conclude that the proposed MTST classifier outperforms BiLSTM-A and existing classifiers in the driver identification task, and time-shift ensembles substantially improve the accuracy.

Sleep stage scoring is an essential component of diagnosing sleep disorders. Unfortunately, it is a time-intensive task that requires clinical experts to annotate an entire night's recording for each patient. Therefore, machine learned models offer the potential to alleviate this burden by automating this task. While learned models achieve acceptable accuracy on curated data, these models still produce highly inaccurate scorings for certain patients when deployed in medical centers. This is because particular subsets of the population may not be adequately represented in the data used to train the model. For example, data are not easily accessible (e.g., a given age group like children) or are hard or impossible to collect (e.g., patients with a rare disease or previously unknown pathology). This creates trust issues as incorrect scorings can have severe consequences such as undetected diseases. To address this, we propose augmenting an existing model with a reject option which enables it to abstain from making predictions if the model is at an elevated risk of making a mistake. We show that traditional rejection frameworks can systematically be too cautious in certain circumstances and abstain even when the model can make good predictions. We propose a solution by considering both the data distribution and the model predictions. We demonstrate the efficacy of our method on a real-world sleep scoring use case. Moreover, we found that our approach leads to improved performance on several publicly available benchmarks.

Probabilistic reasoning models (PMs) and probabilistic inference bring advantages when dealing with small datasets or uncertainty on the observed data, and allow to integrate expert knowledge and create interpretable models. The main challenge of using these PMs in practice is that their inference is very compute-intensive. Therefore, custom hardware architectures for the exact and approximate inference of PMs have been proposed in the SotA. The throughput, energy and area efficiency of approximate PM inference accelerators are strongly dominated by the sampler blocks required to sample arbitrary discrete distributions. This paper proposes and studies novel discrete sampler architectures towards efficient and flexible hardware implementations for PM accelerators. Both cumulative distribution table (CDT) and Knuth-Yao (KY) based sampling algorithms are assessed, based on which different sampler hardware architectures were implemented. Innovation is brought in terms of a reconfigurable CDT sampling architecture with a flexible range and a reconfigurable Knuth-Yao sampling architecture that supports both flexible range and dynamic precision. All architectures are benchmarked on real-world Bayesian Networks, demonstrating up to 13 × energy efficiency benefits and 11 × area efficiency improvement of the optimized reconfigurable Knuth-Yao sampler over the traditional linear CDT-based samplers used in the PM SotA.

A growing number of applications like probabilistic machine learning, sparse linear algebra, robotic navigation, etc., exhibit irregular data flow computation that can be modeled with directed acyclic graphs (DAGs). The irregularity arises from the seemingly random connections of nodes, which makes the DAG structure unsuitable for vectorization on CPU or GPU. Moreover, the nodes usually represent a small number of arithmetic operations that cannot amortize the overhead of launching tasks/kernels for each node, further posing challenges for parallel execution. To enable energy-efficient execution, this work proposes DAG processing unit (DPU) version 2, a specialized processor architecture optimized for irregular DAGs with static connectivity. It consists of a tree-structured datapath for efficient data reuse, a customized banked register file, and interconnects tuned to support irregular register accesses. DPU-v2 is utilized effectively through a targeted compiler that systematically maps operations to the datapath, minimizes register bank conflicts, and avoids pipeline hazards. Finally, a design space exploration identifies the optimal architecture configuration that minimizes the energy-delay product. This hardware-software co-optimization approach results in a speedup of $1.4 \times, 3.5 \times $, and $14 \times $ over a state-of-the-art DAG processor ASIP, a CPU, and a GPU, respectively, while also achieving a lower energy-delay product. In this way, this work takes an important step towards enabling an embedded execution of emerging DAG workloads.

Sparse, irregular graphs show up in various applications like linear algebra, machine learning, engineering simulations, robotic control, etc. These graphs have a high degree of parallelism, but their execution on parallel threads of modern platforms remains challenging due to the irregular data dependencies. The execution performance can be improved by efficiently partitioning the graphs such that the communication and thread synchronization overheads are minimized without hurting the utilization of the threads. To achieve this, this article proposesGraphOpt, a tool that models the graph parallelization as a constrained optimization problem and uses the open Google OR-Tools solver to find good partitions. Several scalability techniques are developed to handle large real-world graphs with millions of nodes and edges. Extensive experiments are performed on the graphs of sparse matrix triangular solves (linear algebra) and sum-product networks (machine learning), respectively, showing a mean speedup of 2.0× and 1.8× over previous state-of-the-art libraries, demonstrating the effectiveness of the constrained-optimization-based graph parallelization.

Manufacturing companies rely on technical drawings to develop new designs or adapt designs to customer preferences. The database of historical and novel technical drawings thus represents the knowledge that is core to their operations. With current methods, however, utilizing these drawings is mostly a manual and time consuming effort. In this work, we present a software tool that knows how to interpret various parts of the drawing and can translate this information to allow for automatic reasoning and machine learning on top of such a large database of technical drawings. For example, to find erroneous designs, to learn about patterns present in successful designs, etc. To achieve this, we propose a method that automatically learns a parser capable of interpreting technical drawings, using only limited expert interaction. The proposed method makes use of both neural methods and symbolic methods. Neural methods to interpret visual images and recognize parts of two-dimensional drawings. Symbolic methods to deal with the relational structure and understand the data encapsulated in complex tables present in the technical drawing. Furthermore, the output can be used, for example, to build a similarity based search algorithm. We showcase one deployed tool that is used to help engineers find relevant, previous designs more easily as they can now query the database using a partial design instead of through limited and tedious keyword searches. A partial design can be a part of the two-dimensional drawing, part of a table, part of the contained textual information, or combinations thereof.

While payroll management is a crucial aspect of any business venture, anticipating the future financial impact of changes to the payroll policy is a challenging task due to the complexity of tax legislature. The goal of this work is to automatically explore potential payroll policies and find the optimal set of policies that satisfies the user's needs. To achieve this goal, we overcome two major challenges. First, we translate the tax legislative knowledge into a formal representation flexible enough to support a variety of scenarios in payroll calculations. Second, the legal knowledge is further compiled into a set of constraints from which a constraint solver can find the optimal policy. Furthermore, payroll computation is performed on the individual basis which might be expensive for companies with a large number of employees. To make the optimisation more efficient, we integrate it with a machine learning model that learns from the previous optimisation runs and speeds up the optimisation engine. The results of this work have been deployed by a social insurance fund.

Machine learned models often must abide by certain requirements (e.g., fairness or legal). This has spurred interested in developing approaches that can provably verify whether a model satisfies certain properties. This paper introduces a generic algorithm called Veritas that enables tackling multiple different verification tasks for tree ensemble models like random forests (RFs) and gradient boosted decision trees (GBDTs). This generality contrasts with previous work, which has focused exclusively on either adversarial example generation or robustness checking. Veritas formulates the verification task as a generic optimization problem and introduces a novel search space representation. Veritas offers two key advantages. First, it provides anytime lower and upper bounds when the optimization problem cannot be solved exactly. In contrast, many existing methods have focused on exact solutions and are thus limited by the verification problem being NP-complete. Second, Veritas produces full (bounded suboptimal) solutions that can be used to generate concrete examples. We experimentally show that our method produces state-of-the-art robustness estimates, especially when executed with strict time constraints. This is exceedingly important when checking the robustness of large datasets. Additionally, we show that Veritas enables tackling more real-world verification scenarios.

Imagine being able to ask questions to a black box model such as "Which adversarial examples exist?", "Does a specific attribute have a disproportionate effect on the model's prediction?" or "What kind of predictions could possibly be made for a partially described example?" This last question is particularly important if your partial description does not correspond to any observed example in your data, as it provides insight into how the model will extrapolate to unseen data. These capabilities would be extremely helpful as they would allow a user to better understand the model's behavior, particularly as it relates to issues such as robustness, fairness, and bias. In this paper, we propose such an approach for an ensemble of trees. Since, in general, this task is intractable we present a strategy that (1) can prune part of the input space given the question asked to simplify the problem; and (2) follows a divide and conquer approach that is incremental and can always return some answers and indicates which parts of the input domains are still uncertain. The usefulness of our approach is shown on a diverse set of use cases.

Anomaly detection attempts to identify instances that deviate from expected behavior. Constructing performant anomaly detectors on real-world problems often requires some labeled data, which can be difficult and costly to obtain. However, often one considers multiple, related anomaly detection tasks. Therefore, it may be possible to transfer labeled instances from a related anomaly detection task to the problem at hand. This paper proposes a novel transfer learning algorithm for anomaly detection that selects and transfers relevant labeled instances from a source anomaly detection task to a target one. Then, it classifies target instances using a novel semi-supervised nearest-neighbors technique that considers both unlabeled target and transferred, labeled source instances. The algorithm outperforms a multitude of state-of-the-art transfer learning methods and unsupervised anomaly detection methods on a large benchmark. Furthermore, it outperforms its rivals on a real-world task of detecting anomalous water usage in retail stores.

Probabilistic reasoning is an essential tool for robust decision-making systems because of its ability to explicitly handle real-world uncertainty, constraints and causal relations. Consequently, researchers are developing hybrid models by combining Deep Learning with probabilistic reasoning for safety-critical applications like self-driving vehicles, autonomous drones, etc. However, probabilistic reasoning kernels do not execute efficiently on CPUs or GPUs. This paper, therefore, proposes a custom programmable processor to accelerate sum-product networks, an important probabilistic reasoning execution kernel. The processor has an optimized datapath architecture and memory hierarchy optimized for sum-product networks execution. Experimental results show that the processor, while requiring fewer computational and memory units, achieves a 12x throughput benefit over the Nvidia Jetson TX2 embedded GPU platform.

Methods that learn the structure of Probabilistic Sentential Decision Diagrams (PSDD) from data have achieved state-of-the-art performance in tractable learning tasks. These methods learn PSDDs incrementally by optimizing the likelihood of the induced probability distribution given available data and are thus robust against missing values, a relevant trait to address the challenges of embedded applications, such as failing sensors and resource constraints. However PSDDs are outperformed by discriminatively trained models in classification tasks. In this work, we introduce D-LearnPSDD , a learner that improves the classification performance of the LearnPSDD algorithm by introducing a discriminative bias that encodes the conditional relation between the class and feature variables.

Given its large applicational potential, time series anomaly detection has become a crucial data mining task. Its goal is to identify periods of a time series where there is a deviation from the expected behavior. Existing approaches focus on analyzing whether the currently observed behavior differs from previously seen, normal behavior. In contrast, this paper tackles the the task where the absence of a previously observed behavior is indicative of an anomaly. In other words, a pattern that is expected to recur in the time series is absent. In real-world use cases, absent patterns can be linked to serious problems. For instance, if a scheduled, regular maintenance operation of a machine does not take place, this can be harmful to the machine at a later time. In this paper, we introduce the task of detecting when a specific pattern is absent in a real-valued time series. We propose a novel technique called FZapPa that can address this task. Empirically, FZapPa outperforms existing anomaly techniques on a benchmark of real-world datasets.

Bayesian reasoning is a powerful mechanism for probabilistic inference in smart edge-devices. During such inferences, a low-precision arithmetic representation can enable improved energy efficiency. However, its impact on inference accuracy is not yet understood. Furthermore, general-purpose hardware does not natively support low-precision representation. To address this, we propose ProbLP, a framework that automates the analysis and design of low-precision probabilistic inference hardware. It automatically chooses an appropriate energy-efficient representation based on worst-case error-bounds and hardware energy-models. It generates custom hardware for the resulting inference network exploiting parallelism, pipelining and low-precision operation. The framework is validated on several embedded-sensing benchmarks.

Deep learning methods capable of handling relational data have proliferated over the past years. In contrast to traditional relational learning methods that leverage first-order logic for representing such data, these methods aim at re-representing symbolic relational data in Euclidean space. They offer better scalability, but can only approximate rich relational structures and are less flexible in terms of reasoning. This paper introduces a novel framework for relational representation learning that combines the best of both worlds. This framework, inspired by the auto-encoding principle, uses first-order logic as a data representation language, and the mapping between the the original and latent representation is done by means of logic programs instead of neural networks. We show how learning can be cast as a constraint optimisation problem for which existing solvers can be used. The use of logic as a representation language makes the proposed framework more accurate (as the representation is exact, rather than approximate), more flexible, and more interpretable than deep learning methods. We experimentally show that these latent representations are indeed beneficial in relational learning tasks.

Smart portable applications increasingly rely on edge computing due to privacy and latency concerns. But guaranteeing always-on functionality comes with two major challenges: heavily resource-constrained hardware; and dynamic application conditions. Probabilistic models present an ideal solution to these challenges: they are robust to missing data, allow for joint predictions and have small data needs. In addition, ongoing efforts in field of tractable learning have resulted in probabilistic models with strict inference efficiency guarantees. However, the current notions of tractability are often limited to model complexity, disregarding the hardware's specifications and constraints. We propose a novel resource-aware cost metric that takes into consideration the hardware's properties in determining whether the inference task can be efficiently deployed. We use this metric to evaluate the performance versus resource trade-off relevant to the application of interest, and we propose a strategy that selects the device-settings that can optimally meet users' requirements. We showcase our framework on a mobile activity recognition scenario, and on a variety of benchmark datasets representative of the field of tractable learning and of the applications of interest.

Nowadays, all aspects of a production process are continuously monitored and visualized in a dashboard. Equipment is monitored using a variety of sensors, natural resource usage is tracked, and interventions are recorded. In this context, a common task is to identify anomalous behavior from the time series data generated by sensors. As manually analyzing such data is laborious and expensive, automated approaches have the potential to be much more efficient as well as cost effective. While anomaly detection could be posed as a supervised learning problem, typically this is not possible as few or no labeled examples of anomalous behavior are available and it is oftentimes infeasible or undesirable to collect them. Therefore, unsupervised approaches are commonly employed which typically identify anomalies as deviations from normal (i.e., common or frequent) behavior. However, in many real-world settings several types of normal behavior exist that occur less frequently than some anomalous behaviors. In this paper, we propose a novel constrained-clustering-based approach for anomaly detection that works in both an unsupervised and semi-supervised setting. Starting from an unlabeled data set, the approach is able to gradually incorporate expert-provided feedback to improve its performance. We evaluated our approach on real-world water monitoring time series data from supermarkets in collaboration with Colruyt Group, one of Belgiums largest retail companies. Empirically, we found that our approach outperforms the current detection system as well as several other baselines. Our system is currently deployed and used by the company to analyze water usage for 20 stores on a daily basis.

Running is extremely popular and around 10.6 million people run regularly in the United States alone. Unfortunately, estimates indicated that between 29% to 79% of runners sustain an overuse injury every year. One contributing factor to such injuries is excessive fatigue, which can result in alterations in how someone runs that increase the risk for an overuse injury. Thus being able to detect during a running session when excessive fatigue sets in, and hence when these alterations are prone to arise, could be of great practical importance. In this paper, we explore whether we can use machine learning to predict the rating of perceived exertion (RPE), a validated subjective measure of fatigue, from inertial sensor data of individuals running outdoors. We describe how both the subjective target label and the realistic outdoor running environment introduce several interesting data science challenges. We collected a longitudinal dataset of runners, and demonstrate that machine learning can be used to learn accurate models for predicting RPE.

Low power wide area networks are gaining interest to connect thousands of nodes to the internet of things. However, because the link budget in these networks is huge, nodes suffer from a near-far effect. Nodes far from the base station cannot send to the base station succesfully when closer nodes are transmitting, causing destructive collisions. LoRa, the considered technology in this paper, is a spread spectrum technology. It is known that spread spectrum is also sensitive to this effect. This paper presents a scheme to efficiently optimize the packet error rate fairness inside a LoRaWAN cell. This is achieved by optimizing the power and spreading factor for each node while avoiding near-far problems by allocating distant users to different channels. Simulations show that the packet error rate can be decreased up to 50% for edge nodes in a moderate contention scenario where 1 node per 1000m2transmits every 10 minutes.

We introduce an approach for predicting the behaviour of a machine during a production cycle. Typical data analysis methods assume that continuous behaviour is (fully) observed. This assumption is unrealistic as monitored machines are often interrupted and restarted at irregular points in time. We study the resulting problem, propose a solution and report on a use-case in wire drawing.

Over the last fifteen years, several types of attacks against domain names and the companies relying on them have been observed. The well-known cybersquatting of domain names gave way to typosquatting, the abuse of a user's mistakes when typing a URL in her browser's address bar. Recently, a new attack against domain names surfaced, namely bitsquatting. In bitsquatting, an attacker leverages random bit-errors occurring in the memory of commodity computers and smartphones, to redirect Internet traffic to attacker-controlled domains.

Probabilistic logical languages provide powerful formalisms for knowledge representation and learning. Yet performing inference in these languages is extremely costly, especially if it is done at the propositional level. Lifted inference algorithms, which avoid repeated computation by treating indistinguishable groups of objects as one, help mitigate this cost. Seeking inspiration from logical inference, where lifted inference (e.g., resolution) is commonly performed, we develop a model theoretic approach to probabilistic lifted inference. Our algorithm compiles a first-order probabilistic theory into a first-order deterministic decomposable negation normal form (d-DNNF) circuit. Compilation offers the advantage that inference is polynomial in the size of the circuit. Furthermore, by borrowing techniques from the knowledge compilation literature our algorithm effectively exploits the logical structure (e.g., context-specific independencies) within the first-order model, which allows more computation to be done at the lifted level. An empirical comparison demonstrates the utility of the proposed approach.

Abstract PRISM is an extension of Prolog with probabilistic predicates and built-in support for expectation-maximization learning. Constraint Handling Rules (CHR) is a high-level programming language based on multi-headed multiset rewrite rules. In this paper, we introduce a new probabilistic logic formalism, called CHRiSM, based on a combination of CHR and PRISM. It can be used for high-level rapid prototyping of complex statistical models by means of “chance rules”. The underlying PRISM system can then be used for several probabilistic inference tasks, including probability computation and parameter learning. We define the CHRiSM language in terms of syntax and operational semantics, and illustrate it with examples. We define the notion of ambiguous programs and define a distribution semantics for unambiguous programs. Next, we describe an implementation of CHRiSM, based on CHR(PRISM). We discuss the relation between CHRiSM and other probabilistic logic programming languages, in particular PCHR. Finally, we identify potential application domains.