OpenRaiser/Intern-Atlas huggingface dataset:
Source Coding for Synthesizing Correlated Randomness
Venue: arXiv cs.IT 2021
Year: 2021

We consider a scenario wherein two parties Alice and Bob are provided $X_{1}^{n}$ and $X_{2}^{n}$ -- samples that are IID from a PMF $P_{X_1 X_2}$. Alice and Bob can communicate to Charles over (noiseless) communication links of rate $R_1$ and $R_2$ respectively. Their goal is to enable Charles generate samples $Y^{n}$ such that the triple $(X_{1}^{n},X_{2}^{n},Y^{n})$ has a PMF that is close, in total variation, to $\prod P_{X_1 X_2 Y}$. In addition, the three parties may posses pairwise shared common randomness at rates $C_1$ and $C_2$. We address the problem of characterizing the set of rate quadruples $(R_1,R_2,C_1,C_2)$ for which the above goal can be accomplished. We provide a set of sufficient conditions, i.e. an inner bound to the achievable rate region, and necessary conditions, i.e. an outer bound to the rate region for this three party setup. We provide a joint-typicality based random coding argument involving encoding and decoding operations to perform soft covering and a pertinent relaxation of the PMF requirement for the encoders.
Faithful Embeddings for Knowledge Base Queries
Venue: arXiv cs.LG 2021
Year: 2021

The deductive closure of an ideal knowledge base (KB) contains exactly the logical queries that the KB can answer. However, in practice KBs are both incomplete and over-specified, failing to answer some queries that have real-world answers. \emph{Query embedding} (QE) techniques have been recently proposed where KB entities and KB queries are represented jointly in an embedding space, supporting relaxation and generalization in KB inference. However, experiments in this paper show that QE systems may disagree with deductive reasoning on answers that do not require generalization or relaxation. We address this problem with a novel QE method that is more faithful to deductive reasoning, and show that this leads to better performance on complex queries to incomplete KBs. Finally we show that inserting this new QE module into a neural question-answering system leads to substantial improvements over the state-of-the-art.
Entity-Switched Datasets: An Approach to Auditing the In-Domain Robustness of Named Entity Recognition Models
Venue: arXiv cs.CL 2021
Year: 2021

Named entity recognition systems perform well on standard datasets comprising English news. But given the paucity of data, it is difficult to draw conclusions about the robustness of systems with respect to recognizing a diverse set of entities. We propose a method for auditing the in-domain robustness of systems, focusing specifically on differences in performance due to the national origin of entities. We create entity-switched datasets, in which named entities in the original texts are replaced by plausible named entities of the same type but of different national origin. We find that state-of-the-art systems' performance vary widely even in-domain: In the same context, entities from certain origins are more reliably recognized than entities from elsewhere. Systems perform best on American and Indian entities, and worst on Vietnamese and Indonesian entities. This auditing approach can facilitate the development of more robust named entity recognition systems, and will allow research in this area to consider fairness criteria that have received heightened attention in other predictive technology work.
Masked GANs for Unsupervised Depth and Pose Prediction with Scale Consistency
Venue: arXiv cs.CV 2021
Year: 2021

Previous work has shown that adversarial learning can be used for unsupervised monocular depth and visual odometry (VO) estimation, in which the adversarial loss and the geometric image reconstruction loss are utilized as the mainly supervisory signals to train the whole unsupervised framework. However, the performance of the adversarial framework and image reconstruction is usually limited by occlusions and the visual field changes between frames. This paper proposes a masked generative adversarial network (GAN) for unsupervised monocular depth and ego-motion estimation.The MaskNet and Boolean mask scheme are designed in this framework to eliminate the effects of occlusions and impacts of visual field changes on the reconstruction loss and adversarial loss, respectively. Furthermore, we also consider the scale consistency of our pose network by utilizing a new scale-consistency loss, and therefore, our pose network is capable of providing the full camera trajectory over a long monocular sequence. Extensive experiments on the KITTI dataset show that each component proposed in this paper contributes to the performance, and both our depth and trajectory predictions achieve competitive performance on the KITTI and Make3D datasets.
PANDORA Talks: Personality and Demographics on Reddit
Venue: arXiv cs.CL 2021
Year: 2021

Personality and demographics are important variables in social sciences, while in NLP they can aid in interpretability and removal of societal biases. However, datasets with both personality and demographic labels are scarce. To address this, we present PANDORA, the first large-scale dataset of Reddit comments labeled with three personality models (including the well-established Big 5 model) and demographics (age, gender, and location) for more than 10k users. We showcase the usefulness of this dataset on three experiments, where we leverage the more readily available data from other personality models to predict the Big 5 traits, analyze gender classification biases arising from psycho-demographic variables, and carry out a confirmatory and exploratory analysis based on psychological theories. Finally, we present benchmark prediction models for all personality and demographic variables.
Interpretability Analysis for Named Entity Recognition to Understand System Predictions and How They Can Improve
Venue: arXiv cs.CL 2021
Year: 2021

Named Entity Recognition systems achieve remarkable performance on domains such as English news. It is natural to ask: What are these models actually learning to achieve this? Are they merely memorizing the names themselves? Or are they capable of interpreting the text and inferring the correct entity type from the linguistic context? We examine these questions by contrasting the performance of several variants of LSTM-CRF architectures for named entity recognition, with some provided only representations of the context as features. We also perform similar experiments for BERT. We find that context representations do contribute to system performance, but that the main factor driving high performance is learning the name tokens themselves. We enlist human annotators to evaluate the feasibility of inferring entity types from the context alone and find that, while people are not able to infer the entity type either for the majority of the errors made by the context-only system, there is some room for improvement. A system should be able to recognize any name in a predictive context correctly and our experiments indicate that current systems may be further improved by such capability.
QuickSilver: A Modeling and Parameterized Verification Framework for Systems with Distributed Agreement (Extended Version)
Venue: arXiv cs.PL 2021
Year: 2021

The last decade has sparked several valiant efforts in deductive verification of distributed agreement protocols such as consensus and leader election. Oddly, there have been far fewer verification efforts that go beyond the core protocols and target applications that are built on top of agreement protocols. This is unfortunate, as agreement-based distributed services such as data stores, locks, and ledgers are ubiquitous and potentially permit modular, scalable verification approaches that mimic their modular design. We address this need for verification of distributed agreement-based systems through our novel modeling and verification framework, QuickSilver, that is not only modular, but also fully automated. The key enabling feature of QuickSilver is our encoding of abstractions of verified agreement protocols that facilitates modular, decidable, and scalable automated verification. We demonstrate the potential of QuickSilver by modeling and efficiently verifying a series of tricky case studies, adapted from real-world applications, such as a data store, a lock service, a surveillance system, a pathfinding algorithm for mobile robots, and more.
Rethinking the Trigger of Backdoor Attack
Venue: arXiv cs.CR 2021
Year: 2021

Backdoor attack intends to inject hidden backdoor into the deep neural networks (DNNs), such that the prediction of the infected model will be maliciously changed if the hidden backdoor is activated by the attacker-defined trigger, while it performs well on benign samples. Currently, most of existing backdoor attacks adopted the setting of \emph{static} trigger, $i.e.,$ triggers across the training and testing images follow the same appearance and are located in the same area. In this paper, we revisit this attack paradigm by analyzing the characteristics of the static trigger. We demonstrate that such an attack paradigm is vulnerable when the trigger in testing images is not consistent with the one used for training. We further explore how to utilize this property for backdoor defense, and discuss how to alleviate such vulnerability of existing attacks.
Fully Automatic Electrocardiogram Classification System based on Generative Adversarial Network with Auxiliary Classifier
Venue: arXiv cs.LG 2021
Year: 2021

A generative adversarial network (GAN) based fully automatic electrocardiogram (ECG) arrhythmia classification system with high performance is presented in this paper. The generator (G) in our GAN is designed to generate various coupling matrix inputs conditioned on different arrhythmia classes for data augmentation. Our designed discriminator (D) is trained on both real and generated ECG coupling matrix inputs, and is extracted as an arrhythmia classifier upon completion of training for our GAN. After fine-tuning the D by including patient-specific normal beats estimated using an unsupervised algorithm, and generated abnormal beats by G that are usually rare to obtain, our fully automatic system showed superior overall classification performance for both supraventricular ectopic beats (SVEB or S beats) and ventricular ectopic beats (VEB or V beats) on the MIT-BIH arrhythmia database. It surpassed several state-of-art automatic classifiers and can perform on similar levels as some expert-assisted methods. In particular, the F1 score of SVEB has been improved by up to 13% over the top-performing automatic systems. Moreover, high sensitivity for both SVEB (87%) and VEB (93%) detection has been achieved, which is of great value for practical diagnosis. We, therefore, suggest our ACE-GAN (Generative Adversarial Network with Auxiliary Classifier for Electrocardiogram) based automatic system can be a promising and reliable tool for high throughput clinical screening practice, without any need of manual intervene or expert assisted labeling.
The ZX&-calculus: A complete graphical calculus for classical circuits using spiders
Venue: arXiv cs.LO 2021
Year: 2021

We give a complete presentation for the fragment, ZX&, of the ZX-calculus generated by the Z and X spiders (corresponding to copying and addition) along with the not gate and the and gate. To prove completeness, we freely add a unit and counit to the category TOF generated by the Toffoli gate and ancillary bits, showing that this yields the full subcategory of finite ordinals and functions with objects powers of two; and then perform a two way translation between this category and ZX&. A translation to some extension of TOF, as opposed to some fragment of the ZX-calculus, is a natural choice because of the multiplicative nature of the Toffoli gate. To this end, we show that freely adding counits to the semi-Frobenius algebras of a discrete inverse category is the same as constructing the Cartesian completion. In particular, for a discrete inverse category, the category of classical channels, the Cartesian completion and adding counits all produce the same category. Therefore, applying these constructions to TOF produces the full subcategory of finite ordinals and partial maps with objects powers of two. By glueing together the free counit completion and the free unit completion, this yields "qubit multirelations."
Sharing Matters for Generalization in Deep Metric Learning
Venue: arXiv cs.CV 2021
Year: 2021

Learning the similarity between images constitutes the foundation for numerous vision tasks. The common paradigm is discriminative metric learning, which seeks an embedding that separates different training classes. However, the main challenge is to learn a metric that not only generalizes from training to novel, but related, test samples. It should also transfer to different object classes. So what complementary information is missed by the discriminative paradigm? Besides finding characteristics that separate between classes, we also need them to likely occur in novel categories, which is indicated if they are shared across training classes. This work investigates how to learn such characteristics without the need for extra annotations or training data. By formulating our approach as a novel triplet sampling strategy, it can be easily applied on top of recent ranking loss frameworks. Experiments show that, independent of the underlying network architecture and the specific ranking loss, our approach significantly improves performance in deep metric learning, leading to new the state-of-the-art results on various standard benchmark datasets. Preliminary early access page can be found here: https://ieeexplore.ieee.org/document/9141449
AREDSUM: Adaptive Redundancy-Aware Iterative Sentence Ranking for Extractive Document Summarization
Venue: arXiv cs.CL 2021
Year: 2021

Redundancy-aware extractive summarization systems score the redundancy of the sentences to be included in a summary either jointly with their salience information or separately as an additional sentence scoring step. Previous work shows the efficacy of jointly scoring and selecting sentences with neural sequence generation models. It is, however, not well-understood if the gain is due to better encoding techniques or better redundancy reduction approaches. Similarly, the contribution of salience versus diversity components on the created summary is not studied well. Building on the state-of-the-art encoding methods for summarization, we present two adaptive learning models: AREDSUM-SEQ that jointly considers salience and novelty during sentence selection; and a two-step AREDSUM-CTX that scores salience first, then learns to balance salience and redundancy, enabling the measurement of the impact of each aspect. Empirical results on CNN/DailyMail and NYT50 datasets show that by modeling diversity explicitly in a separate step, AREDSUM-CTX achieves significantly better performance than AREDSUM-SEQ as well as state-of-the-art extractive summarization baselines.
Simple Multi-Resolution Representation Learning for Human Pose Estimation
Venue: arXiv cs.CV 2021
Year: 2021

Human pose estimation - the process of recognizing human keypoints in a given image - is one of the most important tasks in computer vision and has a wide range of applications including movement diagnostics, surveillance, or self-driving vehicle. The accuracy of human keypoint prediction is increasingly improved thanks to the burgeoning development of deep learning. Most existing methods solved human pose estimation by generating heatmaps in which the ith heatmap indicates the location confidence of the ith keypoint. In this paper, we introduce novel network structures referred to as multi-resolution representation learning for human keypoint prediction. At different resolutions in the learning process, our networks branch off and use extra layers to learn heatmap generation. We firstly consider the architectures for generating the multi-resolution heatmaps after obtaining the lowest-resolution feature maps. Our second approach allows learning during the process of feature extraction in which the heatmaps are generated at each resolution of the feature extractor. The first and second approaches are referred to as multi-resolution heatmap learning and multi-resolution feature map learning respectively. Our architectures are simple yet effective, achieving good performance. We conducted experiments on two common benchmarks for human pose estimation: MSCOCO and MPII dataset. The code is made publicly available at https://github.com/tqtrunghnvn/SimMRPose.
Tensor Network Rewriting Strategies for Satisfiability and Counting
Venue: arXiv cs.CC 2021
Year: 2021

We provide a graphical treatment of SAT and #SAT on equal footing. Instances of #SAT can be represented as tensor networks in a standard way. These tensor networks are interpreted by diagrams of the ZH-calculus: a system to reason about tensors over C in terms of diagrams built from simple generators, in which computation may be carried out by transformations of diagrams alone. In general, nodes of ZH diagrams take parameters over C which determine the tensor coefficients; for the standard representation of #SAT instances, the coefficients take the value 0 or 1. Then, by choosing the coefficients of a diagram to range over B, we represent the corresponding instance of SAT. Thus, by interpreting a diagram either over the boolean semiring or the complex numbers, we instantiate either the decision or counting version of the problem. We find that for classes known to be in P, such as 2SAT and #XORSAT, the existence of appropriate rewrite rules allows for efficient simplification of the diagram, producing the solution in polynomial time. In contrast, for classes known to be NP-complete, such as 3SAT, or #P-complete, such as #2SAT, the corresponding rewrite rules introduce hyperedges to the diagrams, in numbers which are not easily bounded above by a polynomial. This diagrammatic approach unifies the diagnosis of the complexity of CSPs and #CSPs and shows promise in aiding tensor network contraction-based algorithms.
Low-complexity joint user and power scheduling in downlink NOMA over fading channels
Venue: arXiv cs.NI 2021
Year: 2021

Non-orthogonal multiple access (NOMA) has been considered one of the most promising radio access techniques for next-generation cellular networks. In this paper, we study the joint user and power scheduling for downlink NOMA over fading channels. Specifically, we focus on a stochastic optimization problem to maximize the weighted average sum rate while ensuring given minimum average data rates of users. To address this problem, we first develop an opportunistic user and power scheduling algorithm (OUPS) based on the duality and stochastic optimization theory. By OUPS, the stochastic problem is transformed into a series of deterministic ones for the instantaneous weighted sum rate maximization for each slot. Thus, we additionally develop a heuristic algorithm with very low computational complexity, called user selection and power allocation algorithm (USPA), for the instantaneous weighted sum rate maximization problem. Via simulation results, we demonstrate that USPA provides near-optimal performance with very low computational complexity, and OUPS well guarantees given minimum average data rates.
Online Graph Exploration on Trees, Unicyclic Graphs and Cactus Graphs
Venue: arXiv cs.DS 2021
Year: 2021

We study the problem of exploring all vertices of an undirected weighted graph that is initially unknown to the searcher. An edge of the graph is only revealed when the searcher visits one of its endpoints. Beginning at some start node, the searcher's goal is to visit every vertex of the graph before returning to the start node on a tour as short as possible. We prove that the Nearest Neighbor algorithm's competitive ratio on trees with $n$ vertices is $Θ(\log n)$, i.e. no better than on general graphs. Furthermore, we examine the algorithm Blocking for a range of parameters not considered previously and prove it is 3-competitive on unicyclic graphs as well as $5/2+\sqrt{2}\approx 3.91$-competitive on cactus graphs. The best known lower bound for these two graph classes is 2.
Reasoning Visual Dialog with Sparse Graph Learning and Knowledge Transfer
Venue: arXiv cs.CV 2021
Year: 2021

Visual dialog is a task of answering a sequence of questions grounded in an image using the previous dialog history as context. In this paper, we study how to address two fundamental challenges for this task: (1) reasoning over underlying semantic structures among dialog rounds and (2) identifying several appropriate answers to the given question. To address these challenges, we propose a Sparse Graph Learning (SGL) method to formulate visual dialog as a graph structure learning task. SGL infers inherently sparse dialog structures by incorporating binary and score edges and leveraging a new structural loss function. Next, we introduce a Knowledge Transfer (KT) method that extracts the answer predictions from the teacher model and uses them as pseudo labels. We propose KT to remedy the shortcomings of single ground-truth labels, which severely limit the ability of a model to obtain multiple reasonable answers. As a result, our proposed model significantly improves reasoning capability compared to baseline methods and outperforms the state-of-the-art approaches on the VisDial v1.0 dataset. The source code is available at https://github.com/gicheonkang/SGLKT-VisDial.
Self-Supervised training for blind multi-frame video denoising
Venue: arXiv cs.CV 2021
Year: 2021

We propose a self-supervised approach for training multi-frame video denoising networks. These networks predict frame t from a window of frames around t. Our self-supervised approach benefits from the video temporal consistency by penalizing a loss between the predicted frame t and a neighboring target frame, which are aligned using an optical flow. We use the proposed strategy for online internal learning, where a pre-trained network is fine-tuned to denoise a new unknown noise type from a single video. After a few frames, the proposed fine-tuning reaches and sometimes surpasses the performance of a state-of-the-art network trained with supervision. In addition, for a wide range of noise types, it can be applied blindly without knowing the noise distribution. We demonstrate this by showing results on blind denoising of different synthetic and realistic noises.
From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm
Venue: arXiv cs.NE 2021
Year: 2021

One of the key difficulties in using estimation-of-distribution algorithms is choosing the population size(s) appropriately: Too small values lead to genetic drift, which can cause enormous difficulties. In the regime with no genetic drift, however, often the runtime is roughly proportional to the population size, which renders large population sizes inefficient. Based on a recent quantitative analysis which population sizes lead to genetic drift, we propose a parameter-less version of the compact genetic algorithm that automatically finds a suitable population size without spending too much time in situations unfavorable due to genetic drift. We prove a mathematical runtime guarantee for this algorithm and conduct an extensive experimental analysis on four classic benchmark problems both without and with additive centered Gaussian posterior noise. The former shows that under a natural assumption, our algorithm has a performance very similar to the one obtainable from the best problem-specific population size. The latter confirms that missing the right population size in the original cGA can be detrimental and that previous theory-based suggestions for the population size can be far away from the right values; it also shows that our algorithm as well as a previously proposed parameter-less variant of the cGA based on parallel runs avoid such pitfalls. Comparing the two parameter-less approaches, ours profits from its ability to abort runs which are likely to be stuck in a genetic drift situation.