OpenRaiser/Intern-Atlas huggingface dataset:
Video action recognition for lane-change classification and prediction of surrounding vehicles
Venue: arXiv cs.CV 2022
Year: 2022

In highway scenarios, an alert human driver will typically anticipate early cut-in/cut-out maneuvers of surrounding vehicles using visual cues mainly. Autonomous vehicles must anticipate these situations at an early stage too, to increase their safety and efficiency. In this work, lane-change recognition and prediction tasks are posed as video action recognition problems. Up to four different two-stream-based approaches, that have been successfully applied to address human action recognition, are adapted here by stacking visual cues from forward-looking video cameras to recognize and anticipate lane-changes of target vehicles. We study the influence of context and observation horizons on performance, and different prediction horizons are analyzed. The different models are trained and evaluated using the PREVENTION dataset. The obtained results clearly demonstrate the potential of these methodologies to serve as robust predictors of future lane-changes of surrounding vehicles proving an accuracy higher than 90% in time horizons of between 1-2 seconds.
Group Testing with a Graph Infection Spread Model
Venue: arXiv cs.IT 2022
Year: 2022

We propose a novel infection spread model based on a random connection graph which represents connections between $n$ individuals. Infection spreads via connections between individuals and this results in a probabilistic cluster formation structure as well as a non-i.i.d. (correlated) infection status for individuals. We propose a class of two-step sampled group testing algorithms where we exploit the known probabilistic infection spread model. We investigate the metrics associated with two-step sampled group testing algorithms. To demonstrate our results, for analytically tractable exponentially split cluster formation trees, we calculate the required number of tests and the expected number of false classifications in terms of the system parameters, and identify the trade-off between them. For such exponentially split cluster formation trees, for zero-error construction, we prove that the required number of tests is $O(\log_2n)$. Thus, for such cluster formation trees, our algorithm outperforms any zero-error non-adaptive group test, binary splitting algorithm, and Hwang's generalized binary splitting algorithm. Our results imply that, by exploiting probabilistic information on the connections of individuals, group testing can be used to reduce the number of required tests significantly even when infection rate is high, contrasting the prevalent belief that group testing is useful only when infection rate is low.
An Improved Approximation Algorithm for the Minimum $k$-Edge Connected Multi-Subgraph Problem
Venue: arXiv cs.DS 2022
Year: 2022

We give a randomized $1+\frac{5.06}{\sqrt{k}}$-approximation algorithm for the minimum $k$-edge connected spanning multi-subgraph problem, $k$-ECSM.
Real-Time LSM-Trees for HTAP Workloads
Venue: arXiv cs.DB 2022
Year: 2022

Real-time analytics systems employ hybrid data layouts in which data are stored in different formats throughout their lifecycle. Recent data are stored in a row-oriented format to serve OLTP workloads and support high insert rates, while older data are transformed to a column-oriented format for OLAP access patterns. We observe that a Log-Structured Merge (LSM) Tree is a natural fit for a lifecycle-aware storage engine due to its high write throughput and level-oriented structure, in which records propagate from one level to the next over time. To build a lifecycle-aware storage engine using an LSM-Tree, we make a crucial modification to allow different data layouts in different levels, ranging from purely row-oriented to purely column-oriented, leading to a Real-Time LSM-Tree. We give a cost model and an algorithm to design a Real-Time LSM-Tree that is suitable for a given workload, followed by an experimental evaluation of LASER - a prototype implementation of our idea built on top of the RocksDB key-value store.
HyperNTF: A Hypergraph Regularized Nonnegative Tensor Factorization for Dimensionality Reduction
Venue: arXiv cs.LG 2022
Year: 2022

Tensor decomposition is an effective tool for learning multi-way structures and heterogeneous features from high-dimensional data, such as the multi-view images and multichannel electroencephalography (EEG) signals, are often represented by tensors. However, most of tensor decomposition methods are the linear feature extraction techniques, which are unable to reveal the nonlinear structure within high-dimensional data. To address such problem, a lot of algorithms have been proposed for simultaneously performs linear and non-linear feature extraction. A representative algorithm is the Graph Regularized Non-negative Matrix Factorization (GNMF) for image clustering. However, the normal 2-order graph can only models the pairwise similarity of objects, which cannot sufficiently exploit the complex structures of samples. Thus, we propose a novel method, named Hypergraph Regularized Non-negative Tensor Factorization (HyperNTF), which utilizes hypergraph to encode the complex connections among samples and employs the factor matrix corresponding with last mode of Canonical Polyadic (CP) decomposition as low-dimensional representation. Extensive experiments on synthetic manifolds, real-world image datasets, and EEG signals, demonstrating that HyperNTF outperforms the state-of-the-art methods in terms of dimensionality reduction, clustering, and classification.
Minimal Schedule with Minimal Number of Agents in Attack-Defence Trees
Venue: arXiv cs.MA 2022
Year: 2022

Expressing attack-defence trees in a multi-agent setting allows for studying a new aspect of security scenarios, namely how the number of agents and their task assignment impact the performance, e.g. attack time, of strategies executed by opposing coalitions. Optimal scheduling of agents' actions, a non-trivial problem, is thus vital. We discuss associated caveats and propose an algorithm that synthesises such an assignment, targeting minimal attack time and using minimal number of agents for a given attack-defence tree.
Resolution Limits of Non-Adaptive 20 Questions Search for Multiple Targets
Venue: arXiv cs.IT 2022
Year: 2022

We study the problem of simultaneous search for multiple targets over a multidimensional unit cube and derive fundamental resolution limits of non-adaptive querying procedures using the 20 questions estimation framework. The performance criterion that we consider is the achievable resolution, which is defined as the maximal $L_\infty$ norm between the location vector and its estimated version where the maximization is over all target location vectors. The fundamental resolution limit is defined as the minimal achievable resolution of any non-adaptive query procedure, where each query has binary yes/no answers. We drive non-asymptotic and second-order asymptotic bounds on the minimal achievable resolution, using tools from finite blocklength information theory. Specifically, in the achievability part, we relate the 20 questions problem to data transmission over a multiple access channel, use the information spectrum method by Han and borrow results from finite blocklength analysis for random access channel coding. In the converse part, we relate the 20 questions problem to data transmission over a point-to-point channel and adapt finite blocklength converse results for channel coding. Our results extend the purely first-order asymptotic analyses of Kaspi \emph{et al.} (ISIT 2015) for the one-dimensional case: we consider channels beyond the binary symmetric channel and derive non-asymptotic and second-order asymptotic bounds on the performance of optimal non-adaptive query procedures.
Through the Data Management Lens: Experimental Analysis and Evaluation of Fair Classification
Venue: arXiv cs.LG 2022
Year: 2022

Classification, a heavily-studied data-driven machine learning task, drives an increasing number of prediction systems involving critical human decisions such as loan approval and criminal risk assessment. However, classifiers often demonstrate discriminatory behavior, especially when presented with biased data. Consequently, fairness in classification has emerged as a high-priority research area. Data management research is showing an increasing presence and interest in topics related to data and algorithmic fairness, including the topic of fair classification. The interdisciplinary efforts in fair classification, with machine learning research having the largest presence, have resulted in a large number of fairness notions and a wide range of approaches that have not been systematically evaluated and compared. In this paper, we contribute a broad analysis of 13 fair classification approaches and additional variants, over their correctness, fairness, efficiency, scalability, robustness to data errors, sensitivity to underlying ML model, data efficiency, and stability using a variety of metrics and real-world datasets. Our analysis highlights novel insights on the impact of different metrics and high-level approach characteristics on different aspects of performance. We also discuss general principles for choosing approaches suitable for different practical settings, and identify areas where data-management-centric solutions are likely to have the most impact.
Dynamic Privacy Budget Allocation Improves Data Efficiency of Differentially Private Gradient Descent
Venue: arXiv cs.LG 2022
Year: 2022

Protecting privacy in learning while maintaining the model performance has become increasingly critical in many applications that involve sensitive data. Private Gradient Descent (PGD) is a commonly used private learning framework, which noises gradients based on the Differential Privacy protocol. Recent studies show that \emph{dynamic privacy schedules} of decreasing noise magnitudes can improve loss at the final iteration, and yet theoretical understandings of the effectiveness of such schedules and their connections to optimization algorithms remain limited. In this paper, we provide comprehensive analysis of noise influence in dynamic privacy schedules to answer these critical questions. We first present a dynamic noise schedule minimizing the utility upper bound of PGD, and show how the noise influence from each optimization step collectively impacts utility of the final model. Our study also reveals how impacts from dynamic noise influence change when momentum is used. We empirically show the connection exists for general non-convex losses, and the influence is greatly impacted by the loss curvature.
Tameness and the power of programs over monoids in DA
Venue: arXiv cs.CC 2022
Year: 2022

The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class $\mathsf{NC^1}$. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condition on a class of monoids that entails a natural characterization of the regular languages recognizable by programs over monoids from the class. Second, we prove that the class known as $\mathbf{DA}$ satisfies tameness and hence that the regular languages recognized by programs over monoids in $\mathbf{DA}$ are precisely those recognizable in the classical sense by morphisms from $\mathbf{QDA}$. Third, we show by contrast that the well studied class of monoids called $\mathbf{J}$ is not tame. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from $\mathbf{DA}$.
Hyperspectral Image Denoising via Multi-modal and Double-weighted Tensor Nuclear Norm
Venue: arXiv cs.CV 2022
Year: 2022

Hyperspectral images (HSIs) usually suffer from different types of pollution. This severely reduces the quality of HSIs and limits the accuracy of subsequent processing tasks. HSI denoising can be modeled as a low-rank tensor denoising problem. Tensor nuclear norm (TNN) induced by tensor singular value decomposition plays an important role in this problem. In this letter, we first reconsider three inconspicuous but crucial phenomenons in TNN. In the Fourier transform domain of HSIs, different frequency slices (FS) contain different information; different singular values (SVs) of each FS also represent different information. The two physical phenomenons lie not only in the spectral mode but also in the spatial modes. Then based on them, we propose a multi-modal and double-weighted TNN. It can adaptively shrink the FS and SVs according to their physical meanings in all modes of HSIs. In the framework of the alternating direction method of multipliers, we design an effective alternating iterative strategy to optimize our proposed model. Denoised experiments on both synthetic and real HSI datasets demonstrate their superiority against related methods.
Assets in Software Engineering: What are they after all?
Venue: arXiv cs.SE 2022
Year: 2022

During the development and maintenance of software-intensive products or services, we depend on various artefacts. Some of those artefacts, we deem central to the feasibility of a project and the product's final quality. Typically, these central artefacts are referred to as assets. However, despite their central role in the software development process, little thought is yet invested into what eventually characterises as an asset, often resulting in many terms and underlying concepts being mixed and used inconsistently. A precise terminology of assets and related concepts, such as asset degradation, are crucial for setting up a new generation of cost-effective software engineering practices. In this position paper, we critically reflect upon the notion of assets in software engineering. As a starting point, we define the terminology and concepts of assets and extend the reasoning behind them. We explore assets' characteristics and discuss what asset degradation is as well as its various types and the implications that asset degradation might bring for the planning, realisation, and evolution of software-intensive products and services over time. We aspire to contribute to a more standardised definition of assets in software engineering and foster research endeavours and their practical dissemination in a common, more unified direction.
Star Discrepancy Subset Selection: Problem Formulation and Efficient Approaches for Low Dimensions
Venue: arXiv cs.CG 2022
Year: 2022

Motivated by applications in instance selection, we introduce the star discrepancy subset selection problem, which consists of finding a subset of m out of n points that minimizes the star discrepancy. First, we show that this problem is NP-hard. Then, we introduce a mixed integer linear formulation (MILP) and a combinatorial branch-and-bound (BB) algorithm for the star discrepancy subset selection problem and we evaluate both approaches against random subset selection and a greedy construction on different use-cases in dimension two and three. Our results show that the MILP and BB are efficient in dimension two for large and small $m/n$ ratio, respectively, and for not too large n. However, the performance of both approaches decays strongly for larger dimensions and set sizes. As a side effect of our empirical comparisons we obtain point sets of discrepancy values that are much smaller than those of common low-discrepancy sequences, random point sets, and of Latin Hypercube Sampling. This suggests that subset selection could be an interesting approach for generating point sets of small discrepancy value.
TCLR: Temporal Contrastive Learning for Video Representation
Venue: arXiv cs.CV 2022
Year: 2022

Contrastive learning has nearly closed the gap between supervised and self-supervised learning of image representations, and has also been explored for videos. However, prior work on contrastive learning for video data has not explored the effect of explicitly encouraging the features to be distinct across the temporal dimension. We develop a new temporal contrastive learning framework consisting of two novel losses to improve upon existing contrastive self-supervised video representation learning methods. The local-local temporal contrastive loss adds the task of discriminating between non-overlapping clips from the same video, whereas the global-local temporal contrastive aims to discriminate between timesteps of the feature map of an input clip in order to increase the temporal diversity of the learned features. Our proposed temporal contrastive learning framework achieves significant improvement over the state-of-the-art results in various downstream video understanding tasks such as action recognition, limited-label action classification, and nearest-neighbor video retrieval on multiple video datasets and backbones. We also demonstrate significant improvement in fine-grained action classification for visually similar classes. With the commonly used 3D ResNet-18 architecture with UCF101 pretraining, we achieve 82.4\% (+5.1\% increase over the previous best) top-1 accuracy on UCF101 and 52.9\% (+5.4\% increase) on HMDB51 action classification, and 56.2\% (+11.7\% increase) Top-1 Recall on UCF101 nearest neighbor video retrieval. Code released at github.com/DAVEISHAN/TCLR.
Q4EDA: A Novel Strategy for Textual Information Retrieval Based on User Interactions with Visual Representations of Time Series
Venue: arXiv cs.HC 2022
Year: 2022

Knowing how to construct text-based Search Queries (SQs) for use in Search Engines (SEs) such as Google or Wikipedia has become a fundamental skill. Though much data are available through such SEs, most structured datasets live outside their scope. Visualization tools aid in this limitation, but no such tools come close to the sheer amount of information available through general-purpose SEs. To fill this gap, this paper presents Q4EDA, a novel framework that converts users' visual selection queries executed on top of time series visual representations, providing valid and stable SQs to be used in general-purpose SEs and suggestions of related information. The usefulness of Q4EDA is presented and validated by users through an application linking a Gapminder's line-chart replica with a SE populated with Wikipedia documents, showing how Q4EDA supports and enhances exploratory analysis of United Nations world indicators. Despite some limitations, Q4EDA is unique in its proposal and represents a real advance towards providing solutions for querying textual information based on user interactions with visual representations.
A Decentralized Analysis of Multiparty Protocols
Venue: arXiv cs.PL 2022
Year: 2022

Protocols provide the unifying glue in concurrent and distributed software today; verifying that message-passing programs conform to such governing protocols is important but difficult. Static approaches based on multiparty session types (MPST) use protocols as types to avoid protocol violations and deadlocks in programs. An elusive problem for MPST is to ensure both protocol conformance and deadlock freedom for implementations with interleaved and delegated protocols. We propose a decentralized analysis of multiparty protocols, specified as global types and implemented as interacting processes in an asynchronous $π$-calculus. Our solution rests upon two novel notions: router processes and relative types. While router processes use the global type to enable the composition of participant implementations in arbitrary process networks, relative types extract from the global type the intended interactions and dependencies between pairs of participants. In our analysis, processes are typed using APCP, a type system that ensures protocol conformance and deadlock freedom with respect to binary protocols, developed in prior work. Our decentralized, router-based analysis enables the sound and complete transference of protocol conformance and deadlock freedom from APCP to multiparty protocols.
SPAD-Based Optical Wireless Communication with Signal Pre-Distortion and Noise Normalization
Venue: arXiv cs.IT 2022
Year: 2022

In recent years, there has been a growing interest in exploring the application of single-photon avalanche diode (SPAD) in optical wireless communication (OWC). As a photon counting detector, SPAD can provide much higher sensitivity compared to the other commonly used photodetectors. However, SPAD-based receivers suffer from significant dead-time-induced non-linear distortion and signal dependent noise. In this work, we propose a novel SPAD-based OWC system in which the non-linear distortion caused by dead time can be successfully eliminated by the pre-distortion of the signal at the transmitter. In addition, another system with joint pre-distortion and noise normalization functionality is proposed. Thanks to the additional noise normalization process, for the transformed signal at the receiver, the originally signal dependent noise becomes signal independent so that the conventional signal detection techniques designed for AWGN channels can be employed to decode the signal. Our numerical results demonstrate the superiority of the proposed SPAD-based systems compared to the existing systems in terms of BER performance and achievable data rate.
BF++: a language for general-purpose program synthesis
Venue: arXiv cs.AI 2022
Year: 2022

Most state of the art decision systems based on Reinforcement Learning (RL) are data-driven black-box neural models, where it is often difficult to incorporate expert knowledge into the models or let experts review and validate the learned decision mechanisms. Knowledge-insertion and model review are important requirements in many applications involving human health and safety. One way to bridge the gap between data and knowledge driven systems is program synthesis: replacing a neural network that outputs decisions with a symbolic program generated by a neural network or by means of genetic programming. We propose a new programming language, BF++, designed specifically for automatic programming of agents in a Partially Observable Markov Decision Process (POMDP) setting and apply neural program synthesis to solve standard OpenAI Gym benchmarks.
Untargeted Poisoning Attack Detection in Federated Learning via Behavior Attestation
Venue: arXiv cs.CR 2022
Year: 2022

Federated Learning (FL) is a paradigm in Machine Learning (ML) that addresses data privacy, security, access rights and access to heterogeneous information issues by training a global model using distributed nodes. Despite its advantages, there is an increased potential for cyberattacks on FL-based ML techniques that can undermine the benefits. Model-poisoning attacks on FL target the availability of the model. The adversarial objective is to disrupt the training. We propose attestedFL, a defense mechanism that monitors the training of individual nodes through state persistence in order to detect a malicious worker. A fine-grained assessment of the history of the worker permits the evaluation of its behavior in time and results in innovative detection strategies. We present three lines of defense that aim at assessing if the worker is reliable by observing if the node is really training, advancing towards a goal. Our defense exposes an attacker's malicious behavior and removes unreliable nodes from the aggregation process so that the FL process converge faster. Through extensive evaluations and against various adversarial settings, attestedFL increased the accuracy of the model between 12% to 58% under different scenarios such as attacks performed at different stages of convergence, attackers colluding and continuous attacks.