OpenRaiser/Intern-Atlas huggingface dataset:
Classification Performance Metric for Imbalance Data Based on Recall and Selectivity Normalized in Class Labels
Venue: arXiv cs.LG 2020
Year: 2020

In the classification of a class imbalance dataset, the performance measure used for the model selection and comparison to competing methods is a major issue. In order to overcome this problem several performance measures are defined and analyzed in several perspectives regarding in particular the imbalance ratio. There is still no clear indication which metric is universal and can be used for any skewed data problem. In this paper we introduced a new performance measure based on the harmonic mean of Recall and Selectivity normalized in class labels. This paper shows that the proposed performance measure has the right properties for the imbalanced dataset. In particular, in the space defined by the majority class examples and imbalance ratio it is less sensitive to changes in the majority class and more sensitive to changes in the minority class compared with other existing single-value performance measures. Additionally, the identity of the other performance measures has been proven analytically.
ByGARS: Byzantine SGD with Arbitrary Number of Attackers
Venue: arXiv cs.LG 2020
Year: 2020

We propose two novel stochastic gradient descent algorithms, ByGARS and ByGARS++, for distributed machine learning in the presence of any number of Byzantine adversaries. In these algorithms, reputation scores of workers are computed using an auxiliary dataset at the server. This reputation score is then used for aggregating the gradients for stochastic gradient descent. The computational complexity of ByGARS++ is the same as the usual distributed stochastic gradient descent method with only an additional inner product computation in every iteration. We show that using these reputation scores for gradient aggregation is robust to any number of multiplicative noise Byzantine adversaries and use two-timescale stochastic approximation theory to prove convergence for strongly convex loss functions. We demonstrate the effectiveness of the algorithms for non-convex learning problems using MNIST and CIFAR-10 datasets against almost all state-of-the-art Byzantine attacks. We also show that the proposed algorithms are robust to multiple different types of attacks at the same time.
Hardness of Approximation of (Multi-)LCS over Small Alphabet
Venue: arXiv cs.CC 2020
Year: 2020

The problem of finding longest common subsequence (LCS) is one of the fundamental problems in computer science, which finds application in fields such as computational biology, text processing, information retrieval, data compression etc. It is well known that (decision version of) the problem of finding the length of a LCS of an arbitrary number of input sequences (which we refer to as Multi-LCS problem) is NP-complete. Jiang and Li [SICOMP'95] showed that if Max-Clique is hard to approximate within a factor of $s$ then Multi-LCS is also hard to approximate within a factor of $Θ(s)$. By the NP-hardness of the problem of approximating Max-Clique by Zuckerman [ToC'07], for any constant $δ>0$, the length of a LCS of arbitrary number of input sequences of length $n$ each, cannot be approximated within an $n^{1-δ}$-factor in polynomial time unless {\tt{P}}$=${\NP}. However, the reduction of Jiang and Li assumes the alphabet size to be $Ω(n)$. So far no hardness result is known for the problem of approximating Multi-LCS over sub-linear sized alphabet. On the other hand, it is easy to get $1/|Σ|$-factor approximation for strings of alphabet $Σ$. In this paper, we make a significant progress towards proving hardness of approximation over small alphabet by showing a polynomial-time reduction from the well-studied \emph{densest $k$-subgraph} problem with {\em perfect completeness} to approximating Multi-LCS over alphabet of size $poly(n/k)$. As a consequence, from the known hardness result of densest $k$-subgraph problem (e.g. [Manurangsi, STOC'17]) we get that no polynomial-time algorithm can give an $n^{-o(1)}$-factor approximation of Multi-LCS over an alphabet of size $n^{o(1)}$, unless the Exponential Time Hypothesis is false.
Provably and Efficiently Approximating Near-cliques using the Turán Shadow: PEANUTS
Venue: arXiv cs.SI 2020
Year: 2020

Clique and near-clique counts are important graph properties with applications in graph generation, graph modeling, graph analytics, community detection among others. They are the archetypal examples of dense subgraphs. While there are several different definitions of near-cliques, most of them share the attribute that they are cliques that are missing a small number of edges. Clique counting is itself considered a challenging problem. Counting near-cliques is significantly harder more so since the search space for near-cliques is orders of magnitude larger than that of cliques. We give a formulation of a near-clique as a clique that is missing a constant number of edges. We exploit the fact that a near-clique contains a smaller clique, and use techniques for clique sampling to count near-cliques. This method allows us to count near-cliques with 1 or 2 missing edges, in graphs with tens of millions of edges. To the best of our knowledge, there was no known efficient method for this problem, and we obtain a 10x - 100x speedup over existing algorithms for counting near-cliques. Our main technique is a space-efficient adaptation of the Turán Shadow sampling approach, recently introduced by Jain and Seshadhri (WWW 2017). This approach constructs a large recursion tree (called the Turán Shadow) that represents cliques in a graph. We design a novel algorithm that builds an estimator for near-cliques, using an online, compact construction of the Turán Shadow.
Accelerated Large Batch Optimization of BERT Pretraining in 54 minutes
Venue: arXiv cs.LG 2020
Year: 2020

BERT has recently attracted a lot of attention in natural language understanding (NLU) and achieved state-of-the-art results in various NLU tasks. However, its success requires large deep neural networks and huge amount of data, which result in long training time and impede development progress. Using stochastic gradient methods with large mini-batch has been advocated as an efficient tool to reduce the training time. Along this line of research, LAMB is a prominent example that reduces the training time of BERT from 3 days to 76 minutes on a TPUv3 Pod. In this paper, we propose an accelerated gradient method called LANS to improve the efficiency of using large mini-batches for training. As the learning rate is theoretically upper bounded by the inverse of the Lipschitz constant of the function, one cannot always reduce the number of optimization iterations by selecting a larger learning rate. In order to use larger mini-batch size without accuracy loss, we develop a new learning rate scheduler that overcomes the difficulty of using large learning rate. Using the proposed LANS method and the learning rate scheme, we scaled up the mini-batch sizes to 96K and 33K in phases 1 and 2 of BERT pretraining, respectively. It takes 54 minutes on 192 AWS EC2 P3dn.24xlarge instances to achieve a target F1 score of 90.5 or higher on SQuAD v1.1, achieving the fastest BERT training time in the cloud.
Sensing-Throughput analysis in NOMA-based CR Network
Venue: arXiv cs.NI 2020
Year: 2020

The Cognitive Radio (CR) network provides the solution to the spectrum deficiency problem by enhancing the spectrum utilization. In recent years, Non-orthogonal multiple access (NOMA) has also gained significant interest in improving the spectrum efficiency of 5G networks. The simultaneous wireless information and power transfer (SWIPT) is a technique for the transfer of wireless information and power simultaneously for the power-limited wireless networks. In this paper, we are doing a comparative analysis between the obtainable throughput and standard throughput with perfect cancellation in the SIC receiver and also developed the golden selection search algorithm to acquire the optimal sensing time for maximizing the throughput in NOMA based CR network by using the SWIPT technique. In addition to the sensing time optimization has also simulated the throughput with the interference probability in perfect and imperfect sensing case.
Dynamic Functional Connectivity and Graph Convolution Network for Alzheimer's Disease Classification
Venue: arXiv cs.CV 2020
Year: 2020

Alzheimer's disease (AD) is the most prevalent form of dementia. Traditional methods cannot achieve efficient and accurate diagnosis of AD. In this paper, we introduce a novel method based on dynamic functional connectivity (dFC) that can effectively capture changes in the brain. We compare and combine four different types of features including amplitude of low-frequency fluctuation (ALFF), regional homogeneity (ReHo), dFC and the adjacency matrix of different brain structures between subjects. We use graph convolution network (GCN) which consider the similarity of brain structure between patients to solve the classification problem of non-Euclidean domains. The proposed method's accuracy and the area under the receiver operating characteristic curve achieved 91.3% and 98.4%. This result demonstrated that our proposed method can be used for detecting AD.
Disentangle Perceptual Learning through Online Contrastive Learning
Venue: arXiv cs.CV 2020
Year: 2020

Pursuing realistic results according to human visual perception is the central concern in the image transformation tasks. Perceptual learning approaches like perceptual loss are empirically powerful for such tasks but they usually rely on the pre-trained classification network to provide features, which are not necessarily optimal in terms of visual perception of image transformation. In this paper, we argue that, among the features representation from the pre-trained classification network, only limited dimensions are related to human visual perception, while others are irrelevant, although both will affect the final image transformation results. Under such an assumption, we try to disentangle the perception-relevant dimensions from the representation through our proposed online contrastive learning. The resulted network includes the pre-training part and a feature selection layer, followed by the contrastive learning module, which utilizes the transformed results, target images, and task-oriented distorted images as the positive, negative, and anchor samples, respectively. The contrastive learning aims at activating the perception-relevant dimensions and suppressing the irrelevant ones by using the triplet loss, so that the original representation can be disentangled for better perceptual quality. Experiments on various image transformation tasks demonstrate the superiority of our framework, in terms of human visual perception, to the existing approaches using pre-trained networks and empirically designed losses.
Adversarial Model for Rotated Indoor Scenes Planning
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we propose an adversarial model for producing furniture layout for interior scene synthesis when the interior room is rotated. The proposed model combines a conditional adversarial network, a rotation module, a mode module, and a rotation discriminator module. As compared with the prior work on scene synthesis, our proposed three modules enhance the ability of auto-layout generation and reduce the mode collapse during the rotation of the interior room. We conduct our experiments on a proposed real-world interior layout dataset that contains 14400 designs from the professional designers. Our numerical results demonstrate that the proposed model yields higher-quality layouts for four types of rooms, including the bedroom, the bathroom, the study room, and the tatami room.
Crossmodal Language Grounding in an Embodied Neurocognitive Model
Venue: arXiv cs.NE 2020
Year: 2020

Human infants are able to acquire natural language seemingly easily at an early age. Their language learning seems to occur simultaneously with learning other cognitive functions as well as with playful interactions with the environment and caregivers. From a neuroscientific perspective, natural language is embodied, grounded in most, if not all, sensory and sensorimotor modalities, and acquired by means of crossmodal integration. However, characterising the underlying mechanisms in the brain is difficult and explaining the grounding of language in crossmodal perception and action remains challenging. In this paper, we present a neurocognitive model for language grounding which reflects bio-inspired mechanisms such as an implicit adaptation of timescales as well as end-to-end multimodal abstraction. It addresses developmental robotic interaction and extends its learning capabilities using larger-scale knowledge-based data. In our scenario, we utilise the humanoid robot NICO in obtaining the EMIL data collection, in which the cognitive robot interacts with objects in a children's playground environment while receiving linguistic labels from a caregiver. The model analysis shows that crossmodally integrated representations are sufficient for acquiring language merely from sensory input through interaction with objects in an environment. The representations self-organise hierarchically and embed temporal and spatial information through composition and decomposition. This model can also provide the basis for further crossmodal integration of perceptually grounded cognitive representations.
Efficient Sampling-Based Maximum Entropy Inverse Reinforcement Learning with Application to Autonomous Driving
Venue: arXiv cs.RO 2020
Year: 2020

In the past decades, we have witnessed significant progress in the domain of autonomous driving. Advanced techniques based on optimization and reinforcement learning (RL) become increasingly powerful at solving the forward problem: given designed reward/cost functions, how should we optimize them and obtain driving policies that interact with the environment safely and efficiently. Such progress has raised another equally important question: \emph{what should we optimize}? Instead of manually specifying the reward functions, it is desired that we can extract what human drivers try to optimize from real traffic data and assign that to autonomous vehicles to enable more naturalistic and transparent interaction between humans and intelligent agents. To address this issue, we present an efficient sampling-based maximum-entropy inverse reinforcement learning (IRL) algorithm in this paper. Different from existing IRL algorithms, by introducing an efficient continuous-domain trajectory sampler, the proposed algorithm can directly learn the reward functions in the continuous domain while considering the uncertainties in demonstrated trajectories from human drivers. We evaluate the proposed algorithm on real driving data, including both non-interactive and interactive scenarios. The experimental results show that the proposed algorithm achieves more accurate prediction performance with faster convergence speed and better generalization compared to other baseline IRL algorithms.
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
Venue: arXiv cs.CC 2020
Year: 2020

The disjointness problem - where Alice and Bob are given two subsets of $\{1, \dots, n\}$ and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be $Θ(n)$, it is also known that if the sets are assumed to be drawn from some restricted set systems then the communication complexity can be much lower. In this work, we explore how communication complexity measures change with respect to the complexity of the underlying set system. The complexity measure for the set system that we use in this work is the Vapnik-Chervonenkis (VC) dimension. More precisely, on any set system with VC dimension bounded by $d$, we analyze how large can the deterministic and randomized communication complexities be, as a function of $d$ and $n$. In this paper, we construct two natural set systems of VC dimension $d$, motivated from geometry. Using these set systems we show that the deterministic and randomized communication complexity can be $\widetildeΘ\left(d\log \left( n/d \right)\right)$ for set systems of VC dimension $d$ and this matches the deterministic upper bound for all set systems of VC dimension $d$. We also study the deterministic and randomized communication complexities of the set intersection problem when sets belong to a set system of bounded VC dimension. We show that there exists set systems of VC dimension $d$ such that both deterministic and randomized (one-way and multi-round) complexity for the set intersection problem can be as high as $Θ\left( d\log \left( n/d \right) \right)$, and this is tight among all set systems of VC dimension $d$.
Attention-Based Neural Networks for Sentiment Attitude Extraction using Distant Supervision
Venue: arXiv cs.CL 2020
Year: 2020

In the sentiment attitude extraction task, the aim is to identify <<attitudes>> -- sentiment relations between entities mentioned in text. In this paper, we provide a study on attention-based context encoders in the sentiment attitude extraction task. For this task, we adapt attentive context encoders of two types: (1) feature-based; (2) self-based. In our study, we utilize the corpus of Russian analytical texts RuSentRel and automatically constructed news collection RuAttitudes for enriching the training set. We consider the problem of attitude extraction as two-class (positive, negative) and three-class (positive, negative, neutral) classification tasks for whole documents. Our experiments with the RuSentRel corpus show that the three-class classification models, which employ the RuAttitudes corpus for training, result in 10% increase and extra 3% by F1, when model architectures include the attention mechanism. We also provide the analysis of attention weight distributions in dependence on the term type.
The Power of Connection: Leveraging Network Analysis to Advance Receivable Financing
Venue: arXiv cs.DS 2020
Year: 2020

Receivable financing is the process whereby cash is advanced to firms against receivables their customers have yet to pay: a receivable can be sold to a funder, which immediately gives the firm cash in return for a small percentage of the receivable amount as a fee. Receivable financing has been traditionally handled in a centralized way, where every request is processed by the funder individually and independently of one another. In this work we propose a novel, network-based approach to receivable financing, which enables customers of the same funder to autonomously pay each other as much as possible, and gives benefits to both the funder (reduced cash anticipation and exposure risk) and its customers (smaller fees and lightweight service establishment). Our main contributions consist in providing a principled formulation of the network-based receivable-settlement strategy, and showing how to achieve all algorithmic challenges posed by the design of this strategy. We formulate network-based receivable financing as a novel combinatorial-optimization problem on a multigraph of receivables. We show that the problem is NP-hard, and devise an exact branch-and-bound algorithm, as well as algorithms to efficiently find effective approximate solutions. Our more efficient algorithms are based on cycle enumeration and selection, and exploit a theoretical characterization in terms of a knapsack problem, as well as a refining strategy that properly adds paths between cycles. We also investigate the real-world issue of avoiding temporary violations of the problem constraints, and design methods for handling it. An extensive experimental evaluation is performed on real receivable data. Results attest the good performance of our methods.
OvA-INN: Continual Learning with Invertible Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

In the field of Continual Learning, the objective is to learn several tasks one after the other without access to the data from previous tasks. Several solutions have been proposed to tackle this problem but they usually assume that the user knows which of the tasks to perform at test time on a particular sample, or rely on small samples from previous data and most of them suffer of a substantial drop in accuracy when updated with batches of only one class at a time. In this article, we propose a new method, OvA-INN, which is able to learn one class at a time and without storing any of the previous data. To achieve this, for each class, we train a specific Invertible Neural Network to extract the relevant features to compute the likelihood on this class. At test time, we can predict the class of a sample by identifying the network which predicted the highest likelihood. With this method, we show that we can take advantage of pretrained models by stacking an Invertible Network on top of a feature extractor. This way, we are able to outperform state-of-the-art approaches that rely on features learning for the Continual Learning of MNIST and CIFAR-100 datasets. In our experiments, we reach 72% accuracy on CIFAR-100 after training our model one class at a time.
A Methodology for Creating AI FactSheets
Venue: arXiv cs.HC 2020
Year: 2020

As AI models and services are used in a growing number of highstakes areas, a consensus is forming around the need for a clearer record of how these models and services are developed to increase trust. Several proposals for higher quality and more consistent AI documentation have emerged to address ethical and legal concerns and general social impacts of such systems. However, there is little published work on how to create this documentation. This is the first work to describe a methodology for creating the form of AI documentation we call FactSheets. We have used this methodology to create useful FactSheets for nearly two dozen models. This paper describes this methodology and shares the insights we have gathered. Within each step of the methodology, we describe the issues to consider and the questions to explore with the relevant people in an organization who will be creating and consuming the AI facts in a FactSheet. This methodology will accelerate the broader adoption of transparent AI documentation.
Role of Edge Device and Cloud Machine Learning in Point-of-Care Solutions Using Imaging Diagnostics for Population Screening
Venue: arXiv cs.CY 2020
Year: 2020

Edge devices are revolutionizing diagnostics. Edge devices can reside within or adjacent to imaging tools such as digital Xray, CT, MRI, or ultrasound equipment. These devices are either CPUs or GPUs with advanced processing deep and machine learning (artificial intelligence) algorithms that assist in classification and triage solutions to flag studies as either normal or abnormal, TB or healthy (in case of TB screening), suspected COVID-19/other pneumonia or unremarkable (in hospital or hotspot settings). These can be deployed as screening point-of-care (PoC) solutions; this is particularly true for digital and portable X-ray devices. Edge device learning can also be used for mammography and CT studies where it can identify microcalcification and stroke, respectively. These solutions can be considered the first line of pre-screening before the imaging specialist actually reviews scans and makes a final diagnosis. The key advantage of these tools is that they are instant, can be deployed remotely where experts are not available to perform pre-screening before the experts actually review, and are not limited by internet bandwidth as the nano learning data centers are placed next to the device.