OpenRaiser/Intern-Atlas huggingface dataset:
Complexity Analysis of Root Clustering for a Complex Polynomial
Venue: arXiv cs.SC 2021
Year: 2021

Let $F(z)$ be an arbitrary complex polynomial. We introduce the local root clustering problem, to compute a set of natural $\varepsilon$-clusters of roots of $F(z)$ in some box region $B_0$ in the complex plane. This may be viewed as an extension of the classical root isolation problem. Our contribution is two-fold: we provide an efficient certified subdivision algorithm for this problem, and we provide a bit-complexity analysis based on the local geometry of the root clusters. Our computational model assumes that arbitrarily good approximations of the coefficients of $F$ are provided by means of an oracle at the cost of reading the coefficients. Our algorithmic techniques come from a companion paper (Becker et al., 2018) and are based on the Pellet test, Graeffe and Newton iterations, and are independent of Schönhage's splitting circle method. Our algorithm is relatively simple and promises to be efficient in practice.
Homogeneous vector bundles and $G$-equivariant convolutional neural networks
Venue: arXiv cs.LG 2021
Year: 2021

$G$-equivariant convolutional neural networks (GCNNs) is a geometric deep learning model for data defined on a homogeneous $G$-space $\mathcal{M}$. GCNNs are designed to respect the global symmetry in $\mathcal{M}$, thereby facilitating learning. In this paper, we analyze GCNNs on homogeneous spaces $\mathcal{M} = G/K$ in the case of unimodular Lie groups $G$ and compact subgroups $K \leq G$. We demonstrate that homogeneous vector bundles is the natural setting for GCNNs. We also use reproducing kernel Hilbert spaces to obtain a precise criterion for expressing $G$-equivariant layers as convolutional layers. This criterion is then rephrased as a bandwidth criterion, leading to even stronger results for some groups.
On Parameter Optimization and Reach Enhancement for the Improved Soft-Aided Staircase Decoder
Venue: arXiv cs.IT 2021
Year: 2021

The so-called improved soft-aided bit-marking algorithm was recently proposed for staircase codes (SCCs) in the context of fiber optical communications. This algorithm is known as iSABM-SCC. With the help of channel soft information, the iSABM-SCC decoder marks bits via thresholds to deal with both miscorrections and failures of hard-decision (HD) decoding. In this paper, we study iSABM-SCC focusing on the parameter optimization of the algorithm and its performance analysis, in terms of the gap to the achievable information rates (AIRs) of HD codes and the fiber reach enhancement. We show in this paper that the marking thresholds and the number of modified component decodings heavily affect the performance of iSABM-SCC, and thus, they need to be carefully optimized. By replacing standard decoding with the optimized iSABM-SCC decoding, the gap to the AIRs of HD codes can be reduced to 0.26-1.02 dB for code rates of 0.74-0.87 in the additive white Gaussian noise channel with 8-ary pulse amplitude modulation. The obtained reach increase is up to 22% for data rates between 401 Gbps and 468 Gbps in an optical fiber channel.
Incorporating Commonsense Knowledge Graph in Pretrained Models for Social Commonsense Tasks
Venue: arXiv cs.CL 2021
Year: 2021

Pretrained language models have excelled at many NLP tasks recently; however, their social intelligence is still unsatisfactory. To enable this, machines need to have a more general understanding of our complicated world and develop the ability to perform commonsense reasoning besides fitting the specific downstream tasks. External commonsense knowledge graphs (KGs), such as ConceptNet, provide rich information about words and their relationships. Thus, towards general commonsense learning, we propose two approaches to \emph{implicitly} and \emph{explicitly} infuse such KGs into pretrained language models. We demonstrate our proposed methods perform well on SocialIQA, a social commonsense reasoning task, in both limited and full training data regimes.
Interpretable performance analysis towards offline reinforcement learning: A dataset perspective
Venue: arXiv cs.LG 2021
Year: 2021

Offline reinforcement learning (RL) has increasingly become the focus of the artificial intelligent research due to its wide real-world applications where the collection of data may be difficult, time-consuming, or costly. In this paper, we first propose a two-fold taxonomy for existing offline RL algorithms from the perspective of exploration and exploitation tendency. Secondly, we derive the explicit expression of the upper bound of extrapolation error and explore the correlation between the performance of different types of algorithms and the distribution of actions under states. Specifically, we relax the strict assumption on the sufficiently large amount of state-action tuples. Accordingly, we provably explain why batch constrained Q-learning (BCQ) performs better than other existing techniques. Thirdly, after identifying the weakness of BCQ on dataset of low mean episode returns, we propose a modified variant based on top return selection mechanism, which is proved to be able to gain state-of-the-art performance on various datasets. Lastly, we create a benchmark platform on the Atari domain, entitled RL easy go (RLEG), at an estimated cost of more than 0.3 million dollars. We make it open-source for fair and comprehensive competitions between offline RL algorithms with complete datasets and checkpoints being provided.
Wireless Covert Communications Aided by Distributed Cooperative Jamming over Slow Fading Channels
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we study covert communications between {a pair of} legitimate transmitter-receiver against a watchful warden over slow fading channels. There coexist multiple friendly helper nodes who are willing to protect the covert communication from being detected by the warden. We propose an uncoordinated jammer selection scheme where those helpers whose instantaneous channel gains to the legitimate receiver fall below a pre-established selection threshold will be chosen as jammers radiating jamming signals to defeat the warden. By doing so, the detection accuracy of the warden is expected to be severely degraded while the desired covert communication is rarely affected. We then jointly design the optimal selection threshold and message transmission rate for maximizing covert throughput under the premise that the detection error of the warden exceeds a certain level. Numerical results are presented to validate our theoretical analyses. It is shown that the multi-jammer assisted covert communication outperforms the conventional single-jammer method in terms of covert throughput, and the maximal covert throughput improves significantly as the total number of helpers increases, which demonstrates the validity and superiority of our proposed scheme.
Operation-wise Attention Network for Tampering Localization Fusion
Venue: arXiv cs.CV 2021
Year: 2021

In this work, we present a deep learning-based approach for image tampering localization fusion. This approach is designed to combine the outcomes of multiple image forensics algorithms and provides a fused tampering localization map, which requires no expert knowledge and is easier to interpret by end users. Our fusion framework includes a set of five individual tampering localization methods for splicing localization on JPEG images. The proposed deep learning fusion model is an adapted architecture, initially proposed for the image restoration task, that performs multiple operations in parallel, weighted by an attention mechanism to enable the selection of proper operations depending on the input signals. This weighting process can be very beneficial for cases where the input signal is very diverse, as in our case where the output signals of multiple image forensics algorithms are combined. Evaluation in three publicly available forensics datasets demonstrates that the performance of the proposed approach is competitive, outperforming the individual forensics techniques as well as another recently proposed fusion framework in the majority of cases.
Towards exhaustive branch coverage with PathCrawler
Venue: arXiv cs.SE 2021
Year: 2021

Branch coverage of source code is a very widely used test criterion. Moreover, branch coverage is a similar problem to line coverage, MC/DC and the coverage of assertion violations, certain runtime errors and various other types of test objective. Indeed, establishing that a large number of test objectives are unreachable, or conversely, providing the test inputs which reach them, is at the heart of many verification tasks. However, automatic test generation for exhaustive branch coverage remains an elusive goal: many modern tools obtain high coverage scores without being able to provide an explanation for why some branches are not covered, such as a demonstration that they are unreachable. Concolic test generation offers the promise of exhaustive coverage but covers paths more efficiently than branches. In this paper, I explain why, and propose different strategies to improve its performance on exhaustive branch coverage. A comparison of these strategies on examples of real code shows promising results.
Guiding Next-Step Hint Generation Using Automated Tests
Venue: arXiv cs.SE 2021
Year: 2021

Learning basic programming with Scratch can be hard for novices and tutors alike: Students may not know how to advance when solving a task, teachers may face classrooms with many raised hands at a time, and the problem is exacerbated when novices are on their own in online or virtual lessons. It is therefore desirable to generate next-step hints automatically to provide individual feedback for students who are stuck, but current approaches rely on the availability of multiple hand-crafted or hand-selected sample solutions from which to draw valid hints, and have not been adapted for Scratch. Automated testing provides an opportunity to automatically select suitable candidate solutions for hint generation, even from a pool of student solutions using different solution approaches and varying in quality. In this paper we present Catnip, the first next-step hint generation approach for Scratch, which extends existing data-driven hint generation approaches with automated testing. Evaluation of Catnip on a dataset of student Scratch programs demonstrates that the generated hints point towards functional improvements, and the use of automated tests allows the hints to be better individualized for the chosen solution path.
WildGait: Learning Gait Representations from Raw Surveillance Streams
Venue: arXiv cs.CV 2021
Year: 2021

The use of gait for person identification has important advantages such as being non-invasive, unobtrusive, not requiring cooperation and being less likely to be obscured compared to other biometrics. Existing methods for gait recognition require cooperative gait scenarios, in which a single person is walking multiple times in a straight line in front of a camera. We aim to address the challenges of real-world scenarios in which camera feeds capture multiple people, who in most cases pass in front of the camera only once. We address privacy concerns by using only motion information of walking individuals, with no identifiable appearance-based information. As such, we propose a novel weakly supervised learning framework, WildGait, which consists of training a Spatio-Temporal Graph Convolutional Network on a large number of automatically annotated skeleton sequences obtained from raw, real-world, surveillance streams to learn useful gait signatures. We collected the training data and compiled the largest dataset of walking skeletons called Uncooperative Wild Gait, containing over 38k tracklets of anonymized walking 2D skeletons. We release the dataset for public use. Our results show that, with fine-tuning, we surpass the current state-of-the-art pose-based gait recognition solutions. Our proposed method is reliable in training gait recognition methods in unconstrained environments, especially in settings with scarce amounts of annotated data.
A new framework for experimental design using Bayesian Evidential Learning: the case of wellhead protection area
Venue: arXiv cs.LG 2021
Year: 2021

In this contribution, we predict the wellhead protection area (WHPA, target), the shape and extent of which is influenced by the distribution of hydraulic conductivity (K), from a small number of tracing experiments (predictor). Our first objective is to make stochastic predictions of the WHPA within the Bayesian Evidential Learning (BEL) framework, which aims to find a direct relationship between predictor and target using machine learning. This relationship is learned from a small set of training models (400) sampled from the prior distribution of K. The associated 400 pairs of simulated predictors and targets are obtained through forward modelling. Newly collected field data can then be directly used to predict the approximate posterior distribution of the corresponding WHPA. The uncertainty range of the posterior WHPA distribution is affected by the number and position of data sources (injection wells). Our second objective is to extend BEL to identify the optimal design of data source locations that minimizes the posterior uncertainty of the WHPA. This can be done explicitly, without averaging or approximating because once trained, the BEL model allows the computation of the posterior uncertainty corresponding to any new input data. We use the Modified Hausdorff Distance and the Structural Similarity index metrics to estimate the posterior uncertainty range of the WHPA. Increasing the number of injection wells effectively reduces the derived posterior WHPA uncertainty. Our approach can also estimate which injection wells are more informative than others, as validated through a k-fold cross-validation procedure. Overall, the application of BEL to experimental design makes it possible to identify the data sources maximizing the information content of any measurement data.
Evaluating Gender Bias in Natural Language Inference
Venue: arXiv cs.CL 2021
Year: 2021

Gender-bias stereotypes have recently raised significant ethical concerns in natural language processing. However, progress in detection and evaluation of gender bias in natural language understanding through inference is limited and requires further investigation. In this work, we propose an evaluation methodology to measure these biases by constructing a challenge task that involves pairing gender-neutral premises against a gender-specific hypothesis. We use our challenge task to investigate state-of-the-art NLI models on the presence of gender stereotypes using occupations. Our findings suggest that three models (BERT, RoBERTa, BART) trained on MNLI and SNLI datasets are significantly prone to gender-induced prediction errors. We also find that debiasing techniques such as augmenting the training dataset to ensure a gender-balanced dataset can help reduce such bias in certain cases.
Web Content Signing with Service Workers
Venue: arXiv cs.CR 2021
Year: 2021

Securing the communication between a web server and a browser is a fundamental task of securing the World Wide Web. Websites today rely heavily on HTTPS to set up secure connections. In recent years, several incidents undermined this trust and therefore the security of the HTTPS system. In this paper we introduce an approach allowing to secure JavaScript files in case a HTTPS connection between web server and browser is compromised. Our paper presents a solution to safeguard the user's browser so that it only processes content (e.g., JavaScript or HTML) that was genuinely provided by the web application service providers themselves. Our solution makes use of service workers, a recently proposed W3C Candidate Recommendation enabling applications to take advantage of persistent background processing, including hooks to enable bootstrapping of web applications while offline. It demonstrates how service workers are able to validate the integrity of JavaScript files within the client's browser and how service workers are used to detect and mitigate malicious JavaScript files.
A Resilient and Energy-Aware Task Allocation Framework for Heterogeneous Multi-Robot Systems
Venue: arXiv cs.RO 2021
Year: 2021

In the context of heterogeneous multi-robot teams deployed for executing multiple tasks, this paper develops an energy-aware framework for allocating tasks to robots in an online fashion. With a primary focus on long-duration autonomy applications, we opt for a survivability-focused approach. Towards this end, the task prioritization and execution -- through which the allocation of tasks to robots is effectively realized -- are encoded as constraints within an optimization problem aimed at minimizing the energy consumed by the robots at each point in time. In this context, an allocation is interpreted as a prioritization of a task over all others by each of the robots. Furthermore, we present a novel framework to represent the heterogeneous capabilities of the robots, by distinguishing between the features available on the robots, and the capabilities enabled by these features. By embedding these descriptions within the optimization problem, we make the framework resilient to situations where environmental conditions make certain features unsuitable to support a capability and when component failures on the robots occur. We demonstrate the efficacy and resilience of the proposed approach in a variety of use-case scenarios, consisting of simulations and real robot experiments.
Intent-based Network Management and Orchestration for Smart Distribution Grids
Venue: arXiv cs.NI 2021
Year: 2021

5G technology complements the enabling of communication services for different vertical industries such as smart distribution grids. Automation is an integral and necessary part of the power distribution grid operation and management. This paper postulates a framework by which the smart distribution grid can obtain service-oriented communication services using 5G network slicing and intent-based networking (IBN). IBN provides an interface to service users and network stakeholders to cooperate through a high level abstraction model of service provisioning in a network agnostic manner. The automation and adaptability of the distribution grid are facilitated by using the dynamic and closed-loop mechanism of IBN together with network slicing and network function virtualization for network management and orchestration. We identify the automation parts of the power distribution grid and illustrate the intent processing and its inclusion in the definition of network slice instances, service and network configuration models.
An Introduction to Algorithmic Fairness
Venue: arXiv cs.CY 2021
Year: 2021

In recent years, there has been an increasing awareness of both the public and scientific community that algorithmic systems can reproduce, amplify, or even introduce unfairness in our societies. These lecture notes provide an introduction to some of the core concepts in algorithmic fairness research. We list different types of fairness-related harms, explain two main notions of algorithmic fairness, and map the biases that underlie these harms upon the machine learning development process.
Priberam Labs at the NTCIR-15 SHINRA2020-ML: Classification Task
Venue: arXiv cs.CL 2021
Year: 2021

Wikipedia is an online encyclopedia available in 285 languages. It composes an extremely relevant Knowledge Base (KB), which could be leveraged by automatic systems for several purposes. However, the structure and organisation of such information are not prone to automatic parsing and understanding and it is, therefore, necessary to structure this knowledge. The goal of the current SHINRA2020-ML task is to leverage Wikipedia pages in order to categorise their corresponding entities across 268 hierarchical categories, belonging to the Extended Named Entity (ENE) ontology. In this work, we propose three distinct models based on the contextualised embeddings yielded by Multilingual BERT. We explore the performances of a linear layer with and without explicit usage of the ontology's hierarchy, and a Gated Recurrent Units (GRU) layer. We also test several pooling strategies to leverage BERT's embeddings and selection criteria based on the labels' scores. We were able to achieve good performance across a large variety of languages, including those not seen during the fine-tuning process (zero-shot languages).
Cross-Modal and Multimodal Data Analysis Based on Functional Mapping of Spectral Descriptors and Manifold Regularization
Venue: arXiv cs.LG 2021
Year: 2021

Multimodal manifold modeling methods extend the spectral geometry-aware data analysis to learning from several related and complementary modalities. Most of these methods work based on two major assumptions: 1) there are the same number of homogeneous data samples in each modality, and 2) at least partial correspondences between modalities are given in advance as prior knowledge. This work proposes two new multimodal modeling methods. The first method establishes a general analyzing framework to deal with the multimodal information problem for heterogeneous data without any specific prior knowledge. For this purpose, first, we identify the localities of each manifold by extracting local descriptors via spectral graph wavelet signatures (SGWS). Then, we propose a manifold regularization framework based on the functional mapping between SGWS descriptors (FMBSD) for finding the pointwise correspondences. The second method is a manifold regularized multimodal classification based on pointwise correspondences (M$^2$CPC) used for the problem of multiclass classification of multimodal heterogeneous, which the correspondences between modalities are determined based on the FMBSD method. The experimental results of evaluating the FMBSD method on three common cross-modal retrieval datasets and evaluating the (M$^2$CPC) method on three benchmark multimodal multiclass classification datasets indicate their effectiveness and superiority over state-of-the-art methods.
PoseContrast: Class-Agnostic Object Viewpoint Estimation in the Wild with Pose-Aware Contrastive Learning
Venue: arXiv cs.CV 2021
Year: 2021

Motivated by the need for estimating the 3D pose of arbitrary objects, we consider the challenging problem of class-agnostic object viewpoint estimation from images only, without CAD model knowledge. The idea is to leverage features learned on seen classes to estimate the pose for classes that are unseen, yet that share similar geometries and canonical frames with seen classes. We train a direct pose estimator in a class-agnostic way by sharing weights across all object classes, and we introduce a contrastive learning method that has three main ingredients: (i) the use of pre-trained, self-supervised, contrast-based features; (ii) pose-aware data augmentations; (iii) a pose-aware contrastive loss. We experimented on Pascal3D+, ObjectNet3D and Pix3D in a cross-dataset fashion, with both seen and unseen classes. We report state-of-the-art results, including against methods that additionally use CAD models as input.
Breaking O(nr) for Matroid Intersection
Venue: arXiv cs.DS 2021
Year: 2021

We present algorithms that break the $\tilde O(nr)$-independence-query bound for the Matroid Intersection problem for the full range of $r$; where $n$ is the size of the ground set and $r\leq n$ is the size of the largest common independent set. The $\tilde O(nr)$ bound was due to the efficient implementations [CLSSW FOCS'19; Nguyen 2019] of the classic algorithm of Cunningham [SICOMP'86]. It was recently broken for large $r$ ($r=ω(\sqrt{n})$), first by the $\tilde O(n^{1.5}/ε^{1.5})$-query $(1-ε)$-approximation algorithm of CLSSW [FOCS'19], and subsequently by the $\tilde O(n^{6/5}r^{3/5})$-query exact algorithm of BvdBMN [STOC'21]. No algorithm, even an approximation one, was known to break the $\tilde O(nr)$ bound for the full range of $r$. We present an $\tilde O(n\sqrt{r}/ε)$-query $(1-ε)$-approximation algorithm and an $\tilde O(nr^{3/4})$-query exact algorithm. Our algorithms improve the $\tilde O(nr)$ bound and also the bounds by CLSSW and BvdBMN for the full range of $r$.