OpenRaiser/Intern-Atlas huggingface dataset:
A Constant-Factor Approximation for Generalized Malleable Scheduling under $M^\natural$-Concave Processing Speeds
Venue: arXiv cs.DM 2021
Year: 2021

In generalized malleable scheduling, jobs can be allocated and processed simultaneously on multiple machines so as to reduce the overall makespan of the schedule. The required processing time for each job is determined by the joint processing speed of the allocated machines. We study the case that processing speeds are job-dependent $M^\natural$-concave functions and provide a constant-factor approximation for this setting, significantly expanding the realm of functions for which such an approximation is possible. Further, we explore the connection between malleable scheduling and the problem of fairly allocating items to a set of agents with distinct utility functions, devising a black-box reduction that allows to obtain resource-augmented approximation algorithms for the latter.
Neural Motion Planning for Autonomous Parking
Venue: arXiv cs.RO 2021
Year: 2021

This paper presents a hybrid motion planning strategy that combines a deep generative network with a conventional motion planning method. Existing planning methods such as A* and Hybrid A* are widely used in path planning tasks because of their ability to determine feasible paths even in complex environments; however, they have limitations in terms of efficiency. To overcome these limitations, a path planning algorithm based on a neural network, namely the neural Hybrid A*, is introduced. This paper proposes using a conditional variational autoencoder (CVAE) to guide the search algorithm by exploiting the ability of CVAE to learn information about the planning space given the information of the parking environment. A non-uniform expansion strategy is utilized based on a distribution of feasible trajectories learned in the demonstrations. The proposed method effectively learns the representations of a given state, and shows improvement in terms of algorithm performance.
Resilient Consensus-based Multi-agent Reinforcement Learning with Function Approximation
Venue: arXiv cs.LG 2021
Year: 2021

Adversarial attacks during training can strongly influence the performance of multi-agent reinforcement learning algorithms. It is, thus, highly desirable to augment existing algorithms such that the impact of adversarial attacks on cooperative networks is eliminated, or at least bounded. In this work, we consider a fully decentralized network, where each agent receives a local reward and observes the global state and action. We propose a resilient consensus-based actor-critic algorithm, whereby each agent estimates the team-average reward and value function, and communicates the associated parameter vectors to its immediate neighbors. We show that in the presence of Byzantine agents, whose estimation and communication strategies are completely arbitrary, the estimates of the cooperative agents converge to a bounded consensus value with probability one, provided that there are at most $H$ Byzantine agents in the neighborhood of each cooperative agent and the network is $(2H+1)$-robust. Furthermore, we prove that the policy of the cooperative agents converges with probability one to a bounded neighborhood around a local maximizer of their team-average objective function under the assumption that the policies of the adversarial agents asymptotically become stationary.
Learning Pure Nash Equilibrium in Smart Charging Games
Venue: arXiv cs.GT 2021
Year: 2021

Reinforcement Learning Algorithms (RLA) are useful machine learning tools to understand how decision makers react to signals. It is known that RLA converge towards the pure Nash Equilibria (NE) of finite congestion games and more generally, finite potential games. For finite congestion games, only separable cost functions are considered. However, non-separable costs, which depend on the choices of all players instead of only those choosing the same resource, may be relevant in some circumstances, like in smart charging games. In this paper, finite congestion games with non-separable costs are shown to have an ordinal potential function, leading to the existence of an action-dependent continuous potential function. The convergence of a synchronous RLA towards the pure NE is then extended to this more general class of congestion games. Finally, a smart charging game is designed for illustrating convergence of such learning algorithms.
Faster Primal-Dual Convergence for Min-Max Resource Sharing and Stronger Bounds via Local Weak Duality
Venue: arXiv cs.DS 2021
Year: 2021

We revisit the (block-angular) min-max resource sharing problem, which is a well-known generalization of fractional packing and the maximum concurrent flow problem. It consists of finding an $\ell_{\infty}$-minimal element in a Minkowski sum $\mathcal{X}= \sum_{C \in \mathcal{C}} X_C$ of non-empty closed convex sets $X_C \subseteq \mathbb{R}^{\mathcal{R}}_{\geq 0}$, where $\mathcal{C}$ and $\mathcal{R}$ are finite sets. We assume that an oracle for approximate linear minimization over $X_C$ is given. In this setting, the currently fastest known FPTAS is due to Müller, Radke, and Vygen. For $δ\in (0,1]$, it computes a $σ(1+δ)$-approximately optimal solution using $\mathcal{O}((|\mathcal{C}|+|\mathcal{R}|)\log |\mathcal{R}| (δ^{-2} + \log \log |\mathcal{R}|))$ oracle calls, where $σ$ is the approximation ratio of the oracle. We describe an extension of their algorithm and improve on previous results in various ways. Our FPTAS, which, as previous approaches, is based on the multiplicative weight update method, computes close to optimal primal and dual solutions using $\mathcal{O}\left(\frac{|\mathcal{C}|+ |\mathcal{R}|}{δ^2} \log |\mathcal{R}|\right)$ oracle calls. We prove that our running time is optimal under certain assumptions, implying that no warm-start analysis of the algorithm is possible. A major novelty of our analysis is the concept of local weak duality, which illustrates that the algorithm optimizes (close to) independent parts of the instance separately. Interestingly, this implies that the computed solution is not only approximately $\ell_{\infty}$-minimal, but among such solutions, also its second-highest entry is approximately minimal. We prove that this statement cannot be extended to the third-highest entry.
Small or Far Away? Exploiting Deep Super-Resolution and Altitude Data for Aerial Animal Surveillance
Venue: arXiv cs.CV 2021
Year: 2021

Visuals captured by high-flying aerial drones are increasingly used to assess biodiversity and animal population dynamics around the globe. Yet, challenging acquisition scenarios and tiny animal depictions in airborne imagery, despite ultra-high resolution cameras, have so far been limiting factors for applying computer vision detectors successfully with high confidence. In this paper, we address the problem for the first time by combining deep object detectors with super-resolution techniques and altitude data. In particular, we show that the integration of a holistic attention network based super-resolution approach and a custom-built altitude data exploitation network into standard recognition pipelines can considerably increase the detection efficacy in real-world settings. We evaluate the system on two public, large aerial-capture animal datasets, SAVMAP and AED. We find that the proposed approach can consistently improve over ablated baselines and the state-of-the-art performance for both datasets. In addition, we provide a systematic analysis of the relationship between animal resolution and detection performance. We conclude that super-resolution and altitude knowledge exploitation techniques can significantly increase benchmarks across settings and, thus, should be used routinely when detecting minutely resolved animals in aerial imagery.
Temporally-Consistent Surface Reconstruction using Metrically-Consistent Atlases
Venue: arXiv cs.CV 2021
Year: 2021

We propose a method for unsupervised reconstruction of a temporally-consistent sequence of surfaces from a sequence of time-evolving point clouds. It yields dense and semantically meaningful correspondences between frames. We represent the reconstructed surfaces as atlases computed by a neural network, which enables us to establish correspondences between frames. The key to making these correspondences semantically meaningful is to guarantee that the metric tensors computed at corresponding points are as similar as possible. We have devised an optimization strategy that makes our method robust to noise and global motions, without a priori correspondences or pre-alignment steps. As a result, our approach outperforms state-of-the-art ones on several challenging datasets. The code is available at https://github.com/bednarikjan/temporally_coherent_surface_reconstruction.
MS-LaTTE: A Dataset of Where and When To-do Tasks are Completed
Venue: arXiv cs.CL 2021
Year: 2021

Tasks are a fundamental unit of work in the daily lives of people, who are increasingly using digital means to keep track of, organize, triage and act on them. These digital tools -- such as task management applications -- provide a unique opportunity to study and understand tasks and their connection to the real world, and through intelligent assistance, help people be more productive. By logging signals such as text, timestamp information, and social connectivity graphs, an increasingly rich and detailed picture of how tasks are created and organized, what makes them important, and who acts on them, can be progressively developed. Yet the context around actual task completion remains fuzzy, due to the basic disconnect between actions taken in the real world and telemetry recorded in the digital world. Thus, in this paper we compile and release a novel, real-life, large-scale dataset called MS-LaTTE that captures two core aspects of the context surrounding task completion: location and time. We describe our annotation framework and conduct a number of analyses on the data that were collected, demonstrating that it captures intuitive contextual properties for common tasks. Finally, we test the dataset on the two problems of predicting spatial and temporal task co-occurrence, concluding that predictors for co-location and co-time are both learnable, with a BERT fine-tuned model outperforming several other baselines. The MS-LaTTE dataset provides an opportunity to tackle many new modeling challenges in contextual task understanding and we hope that its release will spur future research in task intelligence more broadly.
Predictive coding, precision and natural gradients
Venue: arXiv cs.LG 2021
Year: 2021

There is an increasing convergence between biologically plausible computational models of inference and learning with local update rules and the global gradient-based optimization of neural network models employed in machine learning. One particularly exciting connection is the correspondence between the locally informed optimization in predictive coding networks and the error backpropagation algorithm that is used to train state-of-the-art deep artificial neural networks. Here we focus on the related, but still largely under-explored connection between precision weighting in predictive coding networks and the Natural Gradient Descent algorithm for deep neural networks. Precision-weighted predictive coding is an interesting candidate for scaling up uncertainty-aware optimization -- particularly for models with large parameter spaces -- due to its distributed nature of the optimization process and the underlying local approximation of the Fisher information metric, the adaptive learning rate that is central to Natural Gradient Descent. Here, we show that hierarchical predictive coding networks with learnable precision indeed are able to solve various supervised and unsupervised learning tasks with performance comparable to global backpropagation with natural gradients and outperform their classical gradient descent counterpart on tasks where high amounts of noise are embedded in data or label inputs. When applied to unsupervised auto-encoding of image inputs, the deterministic network produces hierarchically organized and disentangled embeddings, hinting at the close connections between predictive coding and hierarchical variational inference.
A discrete complement of Lyapunov's inequality and its information theoretic consequences
Venue: arXiv cs.IT 2021
Year: 2021

We establish a reversal of Lyapunov's inequality for monotone log-concave sequences, settling a conjecture of Havrilla-Tkocz and Melbourne-Tkocz. A strengthened version of the same conjecture is disproved through counter example. We also derive several information theoretic inequalities as consequences. In particular sharp bounds are derived for the varentropy, Rényi entropies, and the concentration of information of monotone log-concave random variables. Moreover, the majorization approach utilized in the proof of the main theorem, is applied to derive analogous information theoretic results in the symmetric setting, where the Lyapunov reversal is known to fail.
LoMEF: A Framework to Produce Local Explanations for Global Model Time Series Forecasts
Venue: arXiv cs.LG 2021
Year: 2021

Global Forecasting Models (GFM) that are trained across a set of multiple time series have shown superior results in many forecasting competitions and real-world applications compared with univariate forecasting approaches. One aspect of the popularity of statistical forecasting models such as ETS and ARIMA is their relative simplicity and interpretability (in terms of relevant lags, trend, seasonality, and others), while GFMs typically lack interpretability, especially towards particular time series. This reduces the trust and confidence of the stakeholders when making decisions based on the forecasts without being able to understand the predictions. To mitigate this problem, in this work, we propose a novel local model-agnostic interpretability approach to explain the forecasts from GFMs. We train simpler univariate surrogate models that are considered interpretable (e.g., ETS) on the predictions of the GFM on samples within a neighbourhood that we obtain through bootstrapping or straightforwardly as the one-step-ahead global black-box model forecasts of the time series which needs to be explained. After, we evaluate the explanations for the forecasts of the global models in both qualitative and quantitative aspects such as accuracy, fidelity, stability and comprehensibility, and are able to show the benefits of our approach.
Learning to Evolve on Dynamic Graphs
Venue: arXiv cs.LG 2021
Year: 2021

Representation learning in dynamic graphs is a challenging problem because the topology of graph and node features vary at different time. This requires the model to be able to effectively capture both graph topology information and temporal information. Most existing works are built on recurrent neural networks (RNNs), which are used to exact temporal information of dynamic graphs, and thus they inherit the same drawbacks of RNNs. In this paper, we propose Learning to Evolve on Dynamic Graphs (LEDG) - a novel algorithm that jointly learns graph information and time information. Specifically, our approach utilizes gradient-based meta-learning to learn updating strategies that have better generalization ability than RNN on snapshots. It is model-agnostic and thus can train any message passing based graph neural network (GNN) on dynamic graphs. To enhance the representation power, we disentangle the embeddings into time embeddings and graph intrinsic embeddings. We conduct experiments on various datasets and down-stream tasks, and the experimental results validate the effectiveness of our method.
Image Classification with Consistent Supporting Evidence
Venue: arXiv cs.CV 2021
Year: 2021

Adoption of machine learning models in healthcare requires end users' trust in the system. Models that provide additional supportive evidence for their predictions promise to facilitate adoption. We define consistent evidence to be both compatible and sufficient with respect to model predictions. We propose measures of model inconsistency and regularizers that promote more consistent evidence. We demonstrate our ideas in the context of edema severity grading from chest radiographs. We demonstrate empirically that consistent models provide competitive performance while supporting interpretation.
A Systematic Methodology to Compute the Quantum Vulnerability Factors for Quantum Circuits
Venue: arXiv cs.ET 2021
Year: 2021

Quantum computing is one of the most promising technology advances of the latest years. Once only a conceptual idea to solve physics simulations, quantum computation is today a reality, with numerous machines able to execute quantum algorithms. One of the hardest challenges in quantum computing is reliability. Qubits are highly sensitive to noise, which can make the output useless. Moreover, lately it has been shown that superconducting qubits are extremely susceptible to external sources of faults, such as ionizing radiation. When adopted in large scale, radiation-induced errors are expected to become a serious challenge for qubits reliability. In this paper, we propose an evaluation of the impact of transient faults in the execution of quantum circuits. Inspired by the Architectural and Program Vulnerability Factors, widely adopted to characterize the reliability of classical computing architectures and algorithms, we propose the Quantum Vulnerability Factor (QVF) as a metric to measure the impact that the corruption of a qubit has on the circuit output probability distribution. First, we model faults based on the latest studies on real machines and recently performed radiation experiments. Then, we design a quantum fault injector, built over Qiskit, and characterize the propagation of faults in quantum circuits. We report the finding of more than 15,000,000 fault injections, evaluating the reliability of three quantum circuits and identifying the faults and qubits that are more likely than others to impact the output. With our results, we give guidelines on how to map the qubits in the real quantum computer to reduce the output error and to reduce the probability of having a radiation-induced corruption to modify the output. Finally, we compare the simulation results with experiments on physical quantum computers.
Speech Emotion Recognition Using Deep Sparse Auto-Encoder Extreme Learning Machine with a New Weighting Scheme and Spectro-Temporal Features Along with Classical Feature Selection and A New Quantum-Inspired Dimension Reduction Method
Venue: arXiv cs.SD 2021
Year: 2021

Affective computing is very important in the relationship between man and machine. In this paper, a system for speech emotion recognition (SER) based on speech signal is proposed, which uses new techniques in different stages of processing. The system consists of three stages: feature extraction, feature selection, and finally feature classification. In the first stage, a complex set of long-term statistics features is extracted from both the speech signal and the glottal-waveform signal using a combination of new and diverse features such as prosodic, spectral, and spectro-temporal features. One of the challenges of the SER systems is to distinguish correlated emotions. These features are good discriminators for speech emotions and increase the SER's ability to recognize similar and different emotions. This feature vector with a large number of dimensions naturally has redundancy. In the second stage, using classical feature selection techniques as well as a new quantum-inspired technique to reduce the feature vector dimensionality, the number of feature vector dimensions is reduced. In the third stage, the optimized feature vector is classified by a weighted deep sparse extreme learning machine (ELM) classifier. The classifier performs classification in three steps: sparse random feature learning, orthogonal random projection using the singular value decomposition (SVD) technique, and discriminative classification in the last step using the generalized Tikhonov regularization technique. Also, many existing emotional datasets suffer from the problem of data imbalanced distribution, which in turn increases the classification error and decreases system performance. In this paper, a new weighting method has also been proposed to deal with class imbalance, which is more efficient than existing weighting methods. The proposed method is evaluated on three standard emotional databases.
Full-attention based Neural Architecture Search using Context Auto-regression
Venue: arXiv cs.CV 2021
Year: 2021

Self-attention architectures have emerged as a recent advancement for improving the performance of vision tasks. Manual determination of the architecture for self-attention networks relies on the experience of experts and cannot automatically adapt to various scenarios. Meanwhile, neural architecture search (NAS) has significantly advanced the automatic design of neural architectures. Thus, it is appropriate to consider using NAS methods to discover a better self-attention architecture automatically. However, it is challenging to directly use existing NAS methods to search attention networks because of the uniform cell-based search space and the lack of long-term content dependencies. To address this issue, we propose a full-attention based NAS method. More specifically, a stage-wise search space is constructed that allows various attention operations to be adopted for different layers of a network. To extract global features, a self-supervised search algorithm is proposed that uses context auto-regression to discover the full-attention architecture. To verify the efficacy of the proposed methods, we conducted extensive experiments on various learning tasks, including image classification, fine-grained image recognition, and zero-shot image retrieval. The empirical results show strong evidence that our method is capable of discovering high-performance, full-attention architectures while guaranteeing the required search efficiency.
SocialBERT -- Transformers for Online SocialNetwork Language Modelling
Venue: arXiv cs.CL 2021
Year: 2021

The ubiquity of the contemporary language understanding tasks gives relevance to the development of generalized, yet highly efficient models that utilize all knowledge, provided by the data source. In this work, we present SocialBERT - the first model that uses knowledge about the author's position in the network during text analysis. We investigate possible models for learning social network information and successfully inject it into the baseline BERT model. The evaluation shows that embedding this information maintains a good generalization, with an increase in the quality of the probabilistic model for the given author up to 7.5%. The proposed model has been trained on the majority of groups for the chosen social network, and still able to work with previously unknown groups. The obtained model, as well as the code of our experiments, is available for download and use in applied tasks.