OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Channel Time-Series Person and Soft-Biometric Identification
Venue: arXiv cs.CV 2023
Year: 2023

Multi-channel time-series datasets are popular in the context of human activity recognition (HAR). On-body device (OBD) recordings of human movements are often preferred for HAR applications not only for their reliability but as an approach for identity protection, e.g., in industrial settings. Contradictory, the gait activity is a biometric, as the cyclic movement is distinctive and collectable. In addition, the gait cycle has proven to contain soft-biometric information of human groups, such as age and height. Though general human movements have not been considered a biometric, they might contain identity information. This work investigates person and soft-biometrics identification from OBD recordings of humans performing different activities using deep architectures. Furthermore, we propose the use of attribute representation for soft-biometric identification. We evaluate the method on four datasets of multi-channel time-series HAR, measuring the performance of a person and soft-biometrics identification and its relation concerning performed activities. We find that person identification is not limited to gait activity. The impact of activities on the identification performance was found to be training and dataset specific. Soft-biometric based attribute representation shows promising results and emphasis the necessity of larger datasets.
PAC-Based Formal Verification for Out-of-Distribution Data Detection
Venue: arXiv cs.AI 2023
Year: 2023

Cyber-physical systems (CPS) like autonomous vehicles, that utilize learning components, are often sensitive to noise and out-of-distribution (OOD) instances encountered during runtime. As such, safety critical tasks depend upon OOD detection subsystems in order to restore the CPS to a known state or interrupt execution to prevent safety from being compromised. However, it is difficult to guarantee the performance of OOD detectors as it is difficult to characterize the OOD aspect of an instance, especially in high-dimensional unstructured data. To distinguish between OOD data and data known to the learning component through the training process, an emerging technique is to incorporate variational autoencoders (VAE) within systems and apply classification or anomaly detection techniques on their latent spaces. The rationale for doing so is the reduction of the data domain size through the encoding process, which benefits real-time systems through decreased processing requirements, facilitates feature analysis for unstructured data and allows more explainable techniques to be implemented. This study places probably approximately correct (PAC) based guarantees on OOD detection using the encoding process within VAEs to quantify image features and apply conformal constraints over them. This is used to bound the detection error on unfamiliar instances with user-defined confidence. The approach used in this study is to empirically establish these bounds by sampling the latent probability distribution and evaluating the error with respect to the constraint violations that are encountered. The guarantee is then verified using data generated from CARLA, an open-source driving simulator.
Unsupervised Improvement of Factual Knowledge in Language Models
Venue: arXiv cs.CL 2023
Year: 2023

Masked language modeling (MLM) plays a key role in pretraining large language models. But the MLM objective is often dominated by high-frequency words that are sub-optimal for learning factual knowledge. In this work, we propose an approach for influencing MLM pretraining in a way that can improve language model performance on a variety of knowledge-intensive tasks. We force the language model to prioritize informative words in a fully unsupervised way. Experiments demonstrate that the proposed approach can significantly improve the performance of pretrained language models on tasks such as factual recall, question answering, sentiment analysis, and natural language inference in a closed-book setting.
Minimum Cost Flow in the CONGEST Model
Venue: arXiv cs.DS 2023
Year: 2023

We consider the CONGEST model on a network with $n$ nodes, $m$ edges, diameter $D$, and integer costs and capacities bounded by $\text{poly} n$. In this paper, we show how to find an exact solution to the minimum cost flow problem in $n^{1/2+o(1)}(\sqrt{n}+D)$ rounds, improving the state of the art algorithm with running time $m^{3/7+o(1)}(\sqrt nD^{1/4}+D)$ [Forster et al. FOCS 2021], which only holds for the special case of unit capacity graphs. For certain graphs, we achieve even better results. In particular, for planar graphs, expander graphs, $n^{o(1)}$-genus graphs, $n^{o(1)}$-treewidth graphs, and excluded-minor graphs our algorithm takes $n^{1/2+o(1)}D$ rounds. We obtain this result by combining recent results on Laplacian solvers in the CONGEST model [Forster et al. FOCS 2021, Anagnostides et al. DISC 2022] with a CONGEST implementation of the LP solver of Lee and Sidford [FOCS 2014], and finally show that we can round the approximate solution to an exact solution. Our algorithm solves certain linear programs, that generalize minimum cost flow, up to additive error $ε$ in $n^{1/2+o(1)}(\sqrt{n}+D)\log^3 (1/ε)$ rounds.
Equivariant Parameter Sharing for Porous Crystalline Materials
Venue: arXiv cs.LG 2023
Year: 2023

Efficiently predicting properties of porous crystalline materials has great potential to accelerate the high throughput screening process for developing new materials, as simulations carried out using first principles model are often computationally expensive. To effectively make use of Deep Learning methods to model these materials, we need to utilize the symmetries present in the crystals, which are defined by their space group. Existing methods for crystal property prediction either have symmetry constraints that are too restrictive or only incorporate symmetries between unit cells. In addition, these models do not explicitly model the porous structure of the crystal. In this paper, we develop a model which incorporates the symmetries of the unit cell of a crystal in its architecture and explicitly models the porous structure. We evaluate our model by predicting the heat of adsorption of CO$_2$ for different configurations of the mordenite zeolite. Our results confirm that our method performs better than existing methods for crystal property prediction and that the inclusion of pores results in a more efficient model.
Predicting the Performance-Cost Trade-off of Applications Across Multiple Systems
Venue: arXiv cs.DC 2023
Year: 2023

In modern computing environments, users may have multiple systems accessible to them such as local clusters, private clouds, or public clouds. This abundance of choices makes it difficult for users to select the system and configuration for running an application that best meet their performance and cost objectives. To assist such users, we propose a prediction tool that predicts the full performance-cost trade-off space of an application across multiple systems. Our tool runs and profiles a submitted application on a small number of configurations from some of the systems, and uses that information to predict the application's performance on all configurations in all systems. The prediction models are trained offline with data collected from running a large number of applications on a wide variety of configurations. Notable aspects of our tool include: providing different scopes of prediction with varying online profiling requirements, automating the selection of the small number of configurations and systems used for online profiling, performing online profiling using partial runs thereby make predictions for applications without running them to completion, employing a classifier to distinguish applications that scale well from those that scale poorly, and predicting the sensitivity of applications to interference from other users. We evaluate our tool using 69 data analytics and scientific computing benchmarks executing on three different single-node CPU systems with 8-9 configurations each and show that it can achieve low prediction error with modest profiling overhead.
Dynamic treewidth
Venue: arXiv cs.DS 2023
Year: 2023

We present a data structure that for a dynamic graph $G$ that is updated by edge insertions and deletions, maintains a tree decomposition of $G$ of width at most $6k+5$ under the promise that the treewidth of $G$ never grows above $k$. The amortized update time is ${\cal O}_k(2^{\sqrt{\log n}\log\log n})$, where $n$ is the vertex count of $G$ and the ${\cal O}_k(\cdot)$ notation hides factors depending on $k$. In addition, we also obtain the dynamic variant of Courcelle's Theorem: for any fixed property $φ$ expressible in the $\mathsf{CMSO}_2$ logic, the data structure can maintain whether $G$ satisfies $φ$ within the same time complexity bounds. To a large extent, this answers a question posed by Bodlaender [WG 1993].
Imitation Learning from Nonlinear MPC via the Exact Q-Loss and its Gauss-Newton Approximation
Venue: arXiv cs.LG 2023
Year: 2023

This work presents a novel loss function for learning nonlinear Model Predictive Control policies via Imitation Learning. Standard approaches to Imitation Learning neglect information about the expert and generally adopt a loss function based on the distance between expert and learned controls. In this work, we present a loss based on the Q-function directly embedding the performance objectives and constraint satisfaction of the associated Optimal Control Problem (OCP). However, training a Neural Network with the Q-loss requires solving the associated OCP for each new sample. To alleviate the computational burden, we derive a second Q-loss based on the Gauss-Newton approximation of the OCP resulting in a faster training time. We validate our losses against Behavioral Cloning, the standard approach to Imitation Learning, on the control of a nonlinear system with constraints. The final results show that the Q-function-based losses significantly reduce the amount of constraint violations while achieving comparable or better closed-loop costs.
Grid-SD2E: A General Grid-Feedback in a System for Cognitive Learning
Venue: arXiv cs.AI 2023
Year: 2023

Comprehending how the brain interacts with the external world through generated neural data is crucial for determining its working mechanism, treating brain diseases, and understanding intelligence. Although many theoretical models have been proposed, they have thus far been difficult to integrate and develop. In this study, we were inspired in part by grid cells in creating a more general and robust grid module and constructing an interactive and self-reinforcing cognitive system together with Bayesian reasoning, an approach called space-division and exploration-exploitation with grid-feedback (Grid-SD2E). Here, a grid module can be used as an interaction medium between the outside world and a system, as well as a self-reinforcement medium within the system. The space-division and exploration-exploitation (SD2E) receives the 0/1 signals of a grid through its space-division (SD) module. The system described in this paper is also a theoretical model derived from experiments conducted by other researchers and our experience on neural decoding. Herein, we analyse the rationality of the system based on the existing theories in both neuroscience and cognitive science, and attempt to propose special and general rules to explain the different interactions between people and between people and the external world. What's more, based on this framework, the smallest computing unit is extracted, which is analogous to a single neuron in the brain.
So, I Can Feel Normal: Participatory Design for Accessible Social Media Sites for Individuals with Traumatic Brain Injury
Venue: arXiv cs.HC 2023
Year: 2023

Traumatic brain injury (TBI) can result in chronic sensorimotor, cognitive, psychosocial, and communication challenges that can limit social participation. Social media can be a useful outlet for social participation for individuals with TBI, but there are barriers to access. While research has drawn attention to the nature of access barriers, few studies have investigated technological solutions to address these barriers, particularly considering the perspectives of individuals with TBI. To address this gap in knowledge, we used a participatory approach to engage 10 adults with TBI in conceptualizing tools to address their challenges accessing Facebook. Participants described multifaceted challenges in using social media, including interface overload, social comparisons, and anxiety over self-presentation and communication after injury. They discussed their needs and preferences and generated ideas for design solutions. Our work contributes to designing assistive and accessibility technology to facilitate an equal access to the benefits of social media for individuals with TBI.
Leveraging Deep Learning Approaches for Deepfake Detection: A Review
Venue: arXiv cs.LG 2023
Year: 2023

Conspicuous progression in the field of machine learning and deep learning have led the jump of highly realistic fake media, these media oftentimes referred as deepfakes. Deepfakes are fabricated media which are generated by sophisticated AI that are at times very difficult to set apart from the real media. So far, this media can be uploaded to the various social media platforms, hence advertising it to the world got easy, calling for an efficacious countermeasure. Thus, one of the optimistic counter steps against deepfake would be deepfake detection. To undertake this threat, researchers in the past have created models to detect deepfakes based on ML/DL techniques like Convolutional Neural Networks. This paper aims to explore different methodologies with an intention to achieve a cost-effective model with a higher accuracy with different types of the datasets, which is to address the generalizability of the dataset.
High-Throughput Vector Similarity Search in Knowledge Graphs
Venue: arXiv cs.DB 2023
Year: 2023

There is an increasing adoption of machine learning for encoding data into vectors to serve online recommendation and search use cases. As a result, recent data management systems propose augmenting query processing with online vector similarity search. In this work, we explore vector similarity search in the context of Knowledge Graphs (KGs). Motivated by the tasks of finding related KG queries and entities for past KG query workloads, we focus on hybrid vector similarity search (hybrid queries for short) where part of the query corresponds to vector similarity search and part of the query corresponds to predicates over relational attributes associated with the underlying data vectors. For example, given past KG queries for a song entity, we want to construct new queries for new song entities whose vector representations are close to the vector representation of the entity in the past KG query. But entities in a KG also have non-vector attributes such as a song associated with an artist, a genre, and a release date. Therefore, suggested entities must also satisfy query predicates over non-vector attributes beyond a vector-based similarity predicate. While these tasks are central to KGs, our contributions are generally applicable to hybrid queries. In contrast to prior works that optimize online queries, we focus on enabling efficient batch processing of past hybrid query workloads. We present our system, HQI, for high-throughput batch processing of hybrid queries. We introduce a workload-aware vector data partitioning scheme to tailor the vector index layout to the given workload and describe a multi-query optimization technique to reduce the overhead of vector similarity computations. We evaluate our methods on industrial workloads and demonstrate that HQI yields a 31x improvement in throughput for finding related KG queries compared to existing hybrid query processing approaches.
TransPimLib: A Library for Efficient Transcendental Functions on Processing-in-Memory Systems
Venue: arXiv cs.MS 2023
Year: 2023

Processing-in-memory (PIM) promises to alleviate the data movement bottleneck in modern computing systems. However, current real-world PIM systems have the inherent disadvantage that their hardware is more constrained than in conventional processors (CPU, GPU), due to the difficulty and cost of building processing elements near or inside the memory. As a result, general-purpose PIM architectures support fairly limited instruction sets and struggle to execute complex operations such as transcendental functions and other hard-to-calculate operations (e.g., square root). These operations are particularly important for some modern workloads, e.g., activation functions in machine learning applications. In order to provide support for transcendental (and other hard-to-calculate) functions in general-purpose PIM systems, we present \emph{TransPimLib}, a library that provides CORDIC-based and LUT-based methods for trigonometric functions, hyperbolic functions, exponentiation, logarithm, square root, etc. We develop an implementation of TransPimLib for the UPMEM PIM architecture and perform a thorough evaluation of TransPimLib's methods in terms of performance and accuracy, using microbenchmarks and three full workloads (Blackscholes, Sigmoid, Softmax). We open-source all our code and datasets at~\url{https://github.com/CMU-SAFARI/transpimlib}.
Reactive Multi-agent Coordination using Auction-based Task Allocation and Behavior Trees
Venue: arXiv cs.RO 2023
Year: 2023

This article presents an architecture for multi-agent task allocation and task execution, through the unification of a market-inspired task-auctioning system with Behavior Trees for managing and executing lower level behaviors. We consider the scenario with multi-stage tasks, such as 'pick and place', whose arrival times are not known a priori. In such a scenario, a coordinating architecture is expected to be reactive to newly arrived tasks and the resulting rerouting of agents should be dependent on the stage of completion of their current multi-stage tasks. In the novel architecture proposed in this article, a central auctioning system gathers bids (cost-estimates for completing currently available tasks) from all agents, and solves a combinatorial problem to optimally assign tasks to agents. For every agent, it's participation in the auctioning system and execution of an assigned multi-stage task is managed using behavior trees, which switch among several well-defined behaviors in response to changing scenarios. The auctioning system is run at a fixed rate, allowing for newly added tasks to be incorporated into the auctioning system, which makes the solution reactive and allows for the rerouting of some agents (subject to the states of the behavior trees). We demonstrate that the proposed architecture is especially well-suited for multi-stage tasks, where high costs are incurred when rerouting agents who have completed one or more stages of their current tasks. The scalability analysis of the proposed architecture reveals that it scales well with the number of agents and number of tasks. The proposed framework is experimentally validated in multiple scenarios in a lab environment. A video of a demonstration can be viewed at: https://youtu.be/ZdEkoOOlB2g}.
Side Channel-Assisted Inference Leakage from Machine Learning-based ECG Classification
Venue: arXiv cs.CR 2023
Year: 2023

The Electrocardiogram (ECG) measures the electrical cardiac activity generated by the heart to detect abnormal heartbeat and heart attack. However, the irregular occurrence of the abnormalities demands continuous monitoring of heartbeats. Machine learning techniques are leveraged to automate the task to reduce labor work needed during monitoring. In recent years, many companies have launched products with ECG monitoring and irregular heartbeat alert. Among all classification algorithms, the time series-based algorithm dynamic time warping (DTW) is widely adopted to undertake the ECG classification task. Though progress has been achieved, the DTW-based ECG classification also brings a new attacking vector of leaking the patients' diagnosis results. This paper shows that the ECG input samples' labels can be stolen via a side-channel attack, Flush+Reload. In particular, we first identify the vulnerability of DTW for ECG classification, i.e., the correlation between warping path choice and prediction results. Then we implement an attack that leverages Flush+Reload to monitor the warping path selection with known ECG data and then build a predictor for constructing the relation between warping path selection and labels of input ECG samples. Based on experiments, we find that the Flush+Reload-based inference leakage can achieve an 84.0\% attacking success rate to identify the labels of the two samples in DTW.
Set Covering with Our Eyes Wide Shut
Venue: arXiv cs.DS 2023
Year: 2023

In the stochastic set cover problem (Grandoni et al., FOCS '08), we are given a collection $\mathcal{S}$ of $m$ sets over a universe $\mathcal{U}$ of size $N$, and a distribution $D$ over elements of $\mathcal{U}$. The algorithm draws $n$ elements one-by-one from $D$ and must buy a set to cover each element on arrival; the goal is to minimize the total cost of sets bought during this process. A universal algorithm a priori maps each element $u \in \mathcal{U}$ to a set $S(u)$ such that if $U \subseteq \mathcal{U}$ is formed by drawing $n$ times from distribution $D$, then the algorithm commits to outputting $S(U)$. Grandoni et al. gave an $O(\log mN)$-competitive universal algorithm for this stochastic set cover problem. We improve unilaterally upon this result by giving a simple, polynomial time $O(\log mn)$-competitive universal algorithm for the more general prophet version, in which $U$ is formed by drawing from $n$ different distributions $D_1, \ldots, D_n$. Furthermore, we show that we do not need full foreknowledge of the distributions: in fact, a single sample from each distribution suffices. We show similar results for the 2-stage prophet setting and for the online-with-a-sample setting. We obtain our results via a generic reduction from the single-sample prophet setting to the random-order setting; this reduction holds for a broad class of minimization problems that includes all covering problems. We take advantage of this framework by giving random-order algorithms for non-metric facility location and set multicover; using our framework, these automatically translate to universal prophet algorithms.
DIR-AS: Decoupling Individual Identification and Temporal Reasoning for Action Segmentation
Venue: arXiv cs.CV 2023
Year: 2023

Fully supervised action segmentation works on frame-wise action recognition with dense annotations and often suffers from the over-segmentation issue. Existing works have proposed a variety of solutions such as boundary-aware networks, multi-stage refinement, and temporal smoothness losses. However, most of them take advantage of frame-wise supervision, which cannot effectively tackle the evaluation metrics with different granularities. In this paper, for the desirable large receptive field, we first develop a novel local-global attention mechanism with temporal pyramid dilation and temporal pyramid pooling for efficient multi-scale attention. Then we decouple two inherent goals in action segmentation, ie, (1) individual identification solved by frame-wise supervision, and (2) temporal reasoning tackled by action set prediction. Afterward, an action alignment module fuses these different granularity predictions, leading to more accurate and smoother action segmentation. We achieve state-of-the-art accuracy, eg, 82.8% (+2.6%) on GTEA and 74.7% (+1.2%) on Breakfast, which demonstrates the effectiveness of our proposed method, accompanied by extensive ablation studies. The code will be made available later.