OpenRaiser/Intern-Atlas huggingface dataset:
An Exploration of Multicalibration Uniform Convergence Bounds
Venue: arXiv cs.LG 2022
Year: 2022

Recent works have investigated the sample complexity necessary for fair machine learning. The most advanced of such sample complexity bounds are developed by analyzing multicalibration uniform convergence for a given predictor class. We present a framework which yields multicalibration error uniform convergence bounds by reparametrizing sample complexities for Empirical Risk Minimization (ERM) learning. From this framework, we demonstrate that multicalibration error exhibits dependence on the classifier architecture as well as the underlying data distribution. We perform an experimental evaluation to investigate the behavior of multicalibration error for different families of classifiers. We compare the results of this evaluation to multicalibration error concentration bounds. Our investigation provides additional perspective on both algorithmic fairness and multicalibration error convergence bounds. Given the prevalence of ERM sample complexity bounds, our proposed framework enables machine learning practitioners to easily understand the convergence behavior of multicalibration error for a myriad of classifier architectures.
Reducing Redundancy in the Bottleneck Representation of the Autoencoders
Venue: arXiv cs.CV 2022
Year: 2022

Autoencoders are a type of unsupervised neural networks, which can be used to solve various tasks, e.g., dimensionality reduction, image compression, and image denoising. An AE has two goals: (i) compress the original input to a low-dimensional space at the bottleneck of the network topology using an encoder, (ii) reconstruct the input from the representation at the bottleneck using a decoder. Both encoder and decoder are optimized jointly by minimizing a distortion-based loss which implicitly forces the model to keep only those variations of input data that are required to reconstruct the and to reduce redundancies. In this paper, we propose a scheme to explicitly penalize feature redundancies in the bottleneck representation. To this end, we propose an additional loss term, based on the pair-wise correlation of the neurons, which complements the standard reconstruction loss forcing the encoder to learn a more diverse and richer representation of the input. We tested our approach across different tasks: dimensionality reduction using three different dataset, image compression using the MNIST dataset, and image denoising using fashion MNIST. The experimental results show that the proposed loss leads consistently to superior performance compared to the standard AE loss.
Security of EV-Charging Protocols
Venue: arXiv cs.CR 2022
Year: 2022

The field of electric vehicle charging involves a complex combination of actors, devices, networks, and protocols. These protocols are being developed without a clear focus on security. In this paper, we give an overview of the main roles and protocols in use in the Netherlands. We describe a clear attacker model and security requirements, show that in light of this many of the protocols have security issues, and provide suggestions on how to address these issues. The most important conclusion is the need for end-to-end security for data in transit and long-term authenticity for data at rest. In addition, we highlight the need for improved authentication of the EV driver, e.g. by using banking cards. For the communication links we advise mandatory use of TLS, standardization of TLS options and configurations, and improved authentication using TLS client certificates.
Improving Content-Aware Video Streaming in Congested Networks with In-Network Computing
Venue: arXiv cs.NI 2022
Year: 2022

Network congestion and packet loss pose an ever-increasing challenge to video streaming. Despite the research efforts toward making video encoding schemes resilient to lossy network conditions, forwarding devices have not considered monitoring packet content to prioritize packets and minimize the impact of packet loss on video transmission. In this work, we advocate in favor of in-network computing employing a packet drop algorithm and an in-network hardware module to devise a solution for improving content-aware video streaming in congested network. Results show that our approach can reduce intra-predicted packet loss by over 80% at negligible resource usage and performance costs.
Weighted Connected Matchings
Venue: arXiv cs.DM 2022
Year: 2022

A matching $M$ is a $\mathscr{P}$-matching if the subgraph induced by the endpoints of the edges of $M$ satisfies property $\mathscr{P}$. As examples, for appropriate choices of $\mathscr{P}$, the problems Induced Matching, Uniquely Restricted Matching, Connected Matching and Disconnected Matching arise. For many of these problems, finding a maximum $\mathscr{P}$-matching is a knowingly NP-Hard problem, with few exceptions, such as connected matchings, which has the same time complexity as usual Maximum Matching problem. The weighted variant of Maximum Matching has been studied for decades, with many applications, including the well-known Assignment problem. Motivated by this fact, in addition to some recent researches in weighted versions of acyclic and induced matchings, we study the Maximum Weight Connected Matching. In this problem, we want to find a matching $M$ such that the endpoint vertices of its edges induce a connected subgraph and the sum of the edge weights of $M$ is maximum. Unlike the unweighted Connected Matching problem, which is in P for general graphs, we show that Maximum Weight Connected Matching is NP-Hard even for bounded diameter bipartite graphs, starlike graphs, planar bipartite, and bounded degree planar graphs, while solvable in linear time for trees and subcubic graphs. When we restrict edge weights to be non negative only, we show that the problem turns to be polynomially solvable for chordal graphs, while it remains NP-Hard for most of the cases when weights can be negative. Our final contributions are on parameterized complexity. On the positive side, we present a single exponential time algorithm when parameterized by treewidth. In terms of kernelization, we show that, even when restricted to binary weights, Weighted Connected Matching does not admit a polynomial kernel when parameterized by vertex cover under standard complexity-theoretical hypotheses.
Discovering Concepts in Learned Representations using Statistical Inference and Interactive Visualization
Venue: arXiv cs.LG 2022
Year: 2022

Concept discovery is one of the open problems in the interpretability literature that is important for bridging the gap between non-deep learning experts and model end-users. Among current formulations, concepts defines them by as a direction in a learned representation space. This definition makes it possible to evaluate whether a particular concept significantly influences classification decisions for classes of interest. However, finding relevant concepts is tedious, as representation spaces are high-dimensional and hard to navigate. Current approaches include hand-crafting concept datasets and then converting them to latent space directions; alternatively, the process can be automated by clustering the latent space. In this study, we offer another two approaches to guide user discovery of meaningful concepts, one based on multiple hypothesis testing, and another on interactive visualization. We explore the potential value and limitations of these approaches through simulation experiments and an demo visual interface to real data. Overall, we find that these techniques offer a promising strategy for discovering relevant concepts in settings where users do not have predefined descriptions of them, but without completely automating the process.
Orthogonal Matrices for MBAT Vector Symbolic Architectures, and a "Soft" VSA Representation for JSON
Venue: arXiv cs.LG 2022
Year: 2022

Vector Symbolic Architectures (VSAs) give a way to represent a complex object as a single fixed-length vector, so that similar objects have similar vector representations. These vector representations then become easy to use for machine learning or nearest-neighbor search. We review a previously proposed VSA method, MBAT (Matrix Binding of Additive Terms), which uses multiplication by random matrices for binding related terms. However, multiplying by such matrices introduces instabilities which can harm performance. Making the random matrices be orthogonal matrices provably fixes this problem. With respect to larger scale applications, we see how to apply MBAT vector representations for any data expressed in JSON. JSON is used in numerous programming languages to express complex data, but its native format appears highly unsuited for machine learning. Expressing JSON as a fixed-length vector makes it readily usable for machine learning and nearest-neighbor search. Creating such JSON vectors also shows that a VSA needs to employ binding operations that are non-commutative. VSAs are now ready to try with full-scale practical applications, including healthcare, pharmaceuticals, and genomics. Keywords: MBAT (Matrix Binding of Additive Terms), VSA (Vector Symbolic Architecture), HDC (Hyperdimensional Computing), Distributed Representations, Binding, Orthogonal Matrices, Recurrent Connections, Machine Learning, Search, JSON, VSA Applications
Low Ambiguity Zone: Theoretical Bounds and Doppler-Resilient Sequence Design in Integrated Sensing and Communication Systems
Venue: arXiv cs.IT 2022
Year: 2022

In radar sensing and communications, designing Doppler resilient sequences (DRSs) with low ambiguity function for delay over the entire signal duration and Doppler shift over the entire signal bandwidth is an extremely difficult task. However, in practice, the Doppler frequency range is normally much smaller than the bandwidth of the transmitted signal, and it is relatively easy to attain quasi-synchronization for delays far less than the entire signal duration. Motivated by this observation, we propose a new concept called low ambiguity zone (LAZ) which is a small area of the corresponding ambiguity function of interest defined by the certain Doppler frequency and delay. Such an LAZ will reduce to a zero ambiguity zone (ZAZ) if the maximum ambiguity values of interest are zero. In this paper, we derive a set of theoretical bounds on periodic LAZ/ZAZ of unimodular DRSs with and without spectral constraints, which include the existing bounds on periodic global ambiguity function as special cases. These bounds may be used as theoretical design guidelines to measure the optimality of sequences against Doppler effect. We then introduce four optimal constructions of DRSs with respect to the derived ambiguity lower bounds based on some algebraic tools such as characters over finite field and cyclic difference sets.
AdaPrompt: Adaptive Model Training for Prompt-based NLP
Venue: arXiv cs.CL 2022
Year: 2022

Prompt-based learning, with its capability to tackle zero-shot and few-shot NLP tasks, has gained much attention in community. The main idea is to bridge the gap between NLP downstream tasks and language modeling (LM), by mapping these tasks into natural language prompts, which are then filled by pre-trained language models (PLMs). However, for prompt learning, there are still two salient gaps between NLP tasks and pretraining. First, prompt information is not necessarily sufficiently present during LM pretraining. Second, task-specific data are not necessarily well represented during pretraining. We address these two issues by proposing AdaPrompt, adaptively retrieving external data for continual pretraining of PLMs by making use of both task and prompt characteristics. In addition, we make use of knowledge in Natural Language Inference models for deriving adaptive verbalizers. Experimental results on five NLP benchmarks show that AdaPrompt can improve over standard PLMs in few-shot settings. In addition, in zero-shot settings, our method outperforms standard prompt-based methods by up to 26.35\% relative error reduction.
Online Learning for Min Sum Set Cover and Pandora's Box
Venue: arXiv cs.LG 2022
Year: 2022

Two central problems in Stochastic Optimization are Min Sum Set Cover and Pandora's Box. In Pandora's Box, we are presented with $n$ boxes, each containing an unknown value and the goal is to open the boxes in some order to minimize the sum of the search cost and the smallest value found. Given a distribution of value vectors, we are asked to identify a near-optimal search order. Min Sum Set Cover corresponds to the case where values are either 0 or infinity. In this work, we study the case where the value vectors are not drawn from a distribution but are presented to a learner in an online fashion. We present a computationally efficient algorithm that is constant-competitive against the cost of the optimal search order. We extend our results to a bandit setting where only the values of the boxes opened are revealed to the learner after every round. We also generalize our results to other commonly studied variants of Pandora's Box and Min Sum Set Cover that involve selecting more than a single value subject to a matroid constraint.
InterHT: Knowledge Graph Embeddings by Interaction between Head and Tail Entities
Venue: arXiv cs.CL 2022
Year: 2022

Knowledge graph embedding (KGE) models learn the representation of entities and relations in knowledge graphs. Distance-based methods show promising performance on link prediction task, which predicts the result by the distance between two entity representations. However, most of these methods represent the head entity and tail entity separately, which limits the model capacity. We propose two novel distance-based methods named InterHT and InterHT+ that allow the head and tail entities to interact better and get better entity representation. Experimental results show that our proposed method achieves the best results on ogbl-wikikg2 dataset.
Interpretable pipelines with evolutionarily optimized modules for RL tasks with visual inputs
Venue: arXiv cs.LG 2022
Year: 2022

The importance of explainability in AI has become a pressing concern, for which several explainable AI (XAI) approaches have been recently proposed. However, most of the available XAI techniques are post-hoc methods, which however may be only partially reliable, as they do not reflect exactly the state of the original models. Thus, a more direct way for achieving XAI is through interpretable (also called glass-box) models. These models have been shown to obtain comparable (and, in some cases, better) performance with respect to black-boxes models in various tasks such as classification and reinforcement learning. However, they struggle when working with raw data, especially when the input dimensionality increases and the raw inputs alone do not give valuable insights on the decision-making process. Here, we propose to use end-to-end pipelines composed of multiple interpretable models co-optimized by means of evolutionary algorithms, that allows us to decompose the decision-making process into two parts: computing high-level features from raw data, and reasoning on the extracted high-level features. We test our approach in reinforcement learning environments from the Atari benchmark, where we obtain comparable results (with respect to black-box approaches) in settings without stochastic frame-skipping, while performance degrades in frame-skipping settings.
OWL (Observe, Watch, Listen): Audiovisual Temporal Context for Localizing Actions in Egocentric Videos
Venue: arXiv cs.CV 2022
Year: 2022

Egocentric videos capture sequences of human activities from a first-person perspective and can provide rich multimodal signals. However, most current localization methods use third-person videos and only incorporate visual information. In this work, we take a deep look into the effectiveness of audiovisual context in detecting actions in egocentric videos and introduce a simple-yet-effective approach via Observing, Watching, and Listening (OWL). OWL leverages audiovisual information and context for egocentric temporal action localization (TAL). We validate our approach in two large-scale datasets, EPIC-Kitchens, and HOMAGE. Extensive experiments demonstrate the relevance of the audiovisual temporal context. Namely, we boost the localization performance (mAP) over visual-only models by +2.23% and +3.35% in the above datasets.
Forecasting large-scale circulation regimes using deformable convolutional neural networks and global spatiotemporal climate data
Venue: arXiv cs.LG 2022
Year: 2022

Classifying the state of the atmosphere into a finite number of large-scale circulation regimes is a popular way of investigating teleconnections, the predictability of severe weather events, and climate change. Here, we investigate a supervised machine learning approach based on deformable convolutional neural networks (deCNNs) and transfer learning to forecast the North Atlantic-European weather regimes during extended boreal winter for 1 to 15 days into the future. We apply state-of-the-art interpretation techniques from the machine learning literature to attribute particular regions of interest or potential teleconnections relevant for any given weather cluster prediction or regime transition. We demonstrate superior forecasting performance relative to several classical meteorological benchmarks, as well as logistic regression and random forests. Due to its wider field of view, we also observe deCNN achieving considerably better performance than regular convolutional neural networks at lead times beyond 5-6 days. Finally, we find transfer learning to be of paramount importance, similar to previous data-driven atmospheric forecasting studies.
ASRPU: A Programmable Accelerator for Low-Power Automatic Speech Recognition
Venue: arXiv cs.AR 2022
Year: 2022

The outstanding accuracy achieved by modern Automatic Speech Recognition (ASR) systems is enabling them to quickly become a mainstream technology. ASR is essential for many applications, such as speech-based assistants, dictation systems and real-time language translation. However, highly accurate ASR systems are computationally expensive, requiring on the order of billions of arithmetic operations to decode each second of audio, which conflicts with a growing interest in deploying ASR on edge devices. On these devices, hardware acceleration is key for achieving acceptable performance. However, ASR is a rich and fast-changing field, and thus, any overly specialized hardware accelerator may quickly become obsolete. In this paper, we tackle those challenges by proposing ASRPU, a programmable accelerator for on-edge ASR. ASRPU contains a pool of general-purpose cores that execute small pieces of parallel code. Each of these programs computes one part of the overall decoder (e.g. a layer in a neural network). The accelerator automates some carefully chosen parts of the decoder to simplify the programming without sacrificing generality. We provide an analysis of a modern ASR system implemented on ASRPU and show that this architecture can achieve real-time decoding with a very low power budget.
Barwise Compression Schemes for Audio-Based Music Structure Analysis
Venue: arXiv cs.SD 2022
Year: 2022

Music Structure Analysis (MSA) consists in segmenting a music piece in several distinct sections. We approach MSA within a compression framework, under the hypothesis that the structure is more easily revealed by a simplified representation of the original content of the song. More specifically, under the hypothesis that MSA is correlated with similarities occurring at the bar scale, this article introduces the use of linear and non-linear compression schemes on barwise audio signals. Compressed representations capture the most salient components of the different bars in the song and are then used to infer the song structure using a dynamic programming algorithm. This work explores both low-rank approximation models such as Principal Component Analysis or Nonnegative Matrix Factorization and "piece-specific" Auto-Encoding Neural Networks, with the objective to learn latent representations specific to a given song. Such approaches do not rely on supervision nor annotations, which are well-known to be tedious to collect and possibly ambiguous in MSA description. In our experiments, several unsupervised compression schemes achieve a level of performance comparable to that of state-of-the-art supervised methods (for 3s tolerance) on the RWC-Pop dataset, showcasing the importance of the barwise compression processing for MSA.
Semi-Supervised Convolutive NMF for Automatic Piano Transcription
Venue: arXiv cs.SD 2022
Year: 2022

Automatic Music Transcription, which consists in transforming an audio recording of a musical performance into symbolic format, remains a difficult Music Information Retrieval task. In this work, which focuses on piano transcription, we propose a semi-supervised approach using low-rank matrix factorization techniques, in particular Convolutive Nonnegative Matrix Factorization. In the semi-supervised setting, only a single recording of each individual notes is required. We show on the MAPS dataset that the proposed semi-supervised CNMF method performs better than state-of-the-art low-rank factorization techniques and a little worse than supervised deep learning state-of-the-art methods, while however suffering from generalization issues.
Mixture-of-Rookies: Saving DNN Computations by Predicting ReLU Outputs
Venue: arXiv cs.AR 2022
Year: 2022

Deep Neural Networks (DNNs) are widely used in many applications domains. However, they require a vast amount of computations and memory accesses to deliver outstanding accuracy. In this paper, we propose a scheme to predict whether the output of each ReLu activated neuron will be a zero or a positive number in order to skip the computation of those neurons that will likely output a zero. Our predictor, named Mixture-of-Rookies, combines two inexpensive components. The first one exploits the high linear correlation between binarized (1-bit) and full-precision (8-bit) dot products, whereas the second component clusters together neurons that tend to output zero at the same time. We propose a novel clustering scheme based on the analysis of angles, as the sign of the dot product of two vectors depends on the cosine of the angle between them. We implement our hybrid zero output predictor on top of a state-of-the-art DNN accelerator. Experimental results show that our scheme introduces a small area overhead of 5.3% while achieving a speedup of 1.2x and reducing energy consumption by 16.5% on average for a set of diverse DNNs.
Achievable Information-Energy Region in the Finite Block-Length Regime with Finite Constellations
Venue: arXiv cs.IT 2022
Year: 2022

This paper characterizes an achievable information-energy region of simultaneous information and energy transmission over an additive white Gaussian noise channel. This analysis is performed in the finite block-length regime with finite constellations. More specifically, a method for constructing a family of codes is proposed and the set of achievable tuples of information rate, energy rate, decoding error probability (DEP) and energy outage probability (EOP) is characterized. Using existing converse results, it is shown that the construction is information rate, energy rate, and EOP optimal. The achieved DEP is, however, sub-optimal.