OpenRaiser/Intern-Atlas huggingface dataset:
Conversational Negation using Worldly Context in Compositional Distributional Semantics
Venue: arXiv cs.CL 2021
Year: 2021

We propose a framework to model an operational conversational negation by applying worldly context (prior knowledge) to logical negation in compositional distributional semantics. Given a word, our framework can create its negation that is similar to how humans perceive negation. The framework corrects logical negation to weight meanings closer in the entailment hierarchy more than meanings further apart. The proposed framework is flexible to accommodate different choices of logical negations, compositions, and worldly context generation. In particular, we propose and motivate a new logical negation using matrix inverse. We validate the sensibility of our conversational negation framework by performing experiments, leveraging density matrices to encode graded entailment information. We conclude that the combination of subtraction negation and phaser in the basis of the negated word yields the highest Pearson correlation of 0.635 with human ratings.
The Greedy and Recursive Search for Morphological Productivity
Venue: arXiv cs.CL 2021
Year: 2021

As children acquire the knowledge of their language's morphology, they invariably discover the productive processes that can generalize to new words. Morphological learning is made challenging by the fact that even fully productive rules have exceptions, as in the well-known case of English past tense verbs, which features the -ed rule against the irregular verbs. The Tolerance Principle is a recent proposal that provides a precise threshold of exceptions that a productive rule can withstand. Its empirical application so far, however, requires the researcher to fully specify rules defined over a set of words. We propose a greedy search model that automatically hypothesizes rules and evaluates their productivity over a vocabulary. When the search for broader productivity fails, the model recursively subdivides the vocabulary and continues the search for productivity over narrower rules. Trained on psychologically realistic data from child-directed input, our model displays developmental patterns observed in child morphology acquisition, including the notoriously complex case of German noun pluralization. It also produces responses to nonce words that, despite receiving only a fraction of the training data, are more similar to those of human subjects than current neural network models' responses are.
Symmetric Private Information Retrieval with User-Side Common Randomness
Venue: arXiv cs.IT 2021
Year: 2021

We consider the problem of symmetric private information retrieval (SPIR) with user-side common randomness. In SPIR, a user retrieves a message out of $K$ messages from $N$ non-colluding and replicated databases in such a way that no single database knows the retrieved message index (user privacy), and the user gets to know nothing further than the retrieved message (database privacy). SPIR has a capacity smaller than the PIR capacity which requires only user privacy, is infeasible in the case of a single database, and requires shared common randomness among the databases. We introduce a new variant of SPIR where the user is provided with a random subset of the shared database common randomness, which is unknown to the databases. We determine the exact capacity region of the triple $(d, ρ_S, ρ_U)$, where $d$ is the download cost, $ρ_S$ is the amount of shared database (server) common randomness, and $ρ_U$ is the amount of available user-side common randomness. We show that with a suitable amount of $ρ_U$, this new SPIR achieves the capacity of conventional PIR. As a corollary, single-database SPIR becomes feasible. Further, the presence of user-side $ρ_U$ reduces the amount of required server-side $ρ_S$.
Unlimited Sampling from Theory to Practice: Fourier-Prony Recovery and Prototype ADC
Venue: arXiv cs.IT 2021
Year: 2021

Following the Unlimited Sampling strategy to alleviate the omnipresent dynamic range barrier, we study the problem of recovering a bandlimited signal from point-wise modulo samples, aiming to connect theoretical guarantees with hardware implementation considerations. Our starting point is a class of non-idealities that we observe in prototyping an unlimited sampling based analog-to-digital converter. To address these non-idealities, we provide a new Fourier domain recovery algorithm. Our approach is validated both in theory and via extensive experiments on our prototype analog-to-digital converter, providing the first demonstration of unlimited sampling for data arising from real hardware, both for the current and previous approaches. Advantages of our algorithm include that it is agnostic to the modulo threshold and it can handle arbitrary folding times. We expect that the end-to-end realization studied in this paper will pave the path for exploring the unlimited sampling methodology in a number of real world applications.
Unsupervised Acute Intracranial Hemorrhage Segmentation with Mixture Models
Venue: arXiv cs.CV 2021
Year: 2021

Intracranial hemorrhage occurs when blood vessels rupture or leak within the brain tissue or elsewhere inside the skull. It can be caused by physical trauma or by various medical conditions and in many cases leads to death. The treatment must be started as soon as possible, and therefore the hemorrhage should be diagnosed accurately and quickly. The diagnosis is usually performed by a radiologist who analyses a Computed Tomography (CT) scan containing a large number of cross-sectional images throughout the brain. Analysing each image manually can be very time-consuming, but automated techniques can help speed up the process. While much of the recent research has focused on solving this problem by using supervised machine learning algorithms, publicly-available training data remains scarce due to privacy concerns. This problem can be alleviated by unsupervised algorithms. In this paper, we propose a fully-unsupervised algorithm which is based on the mixture models. Our algorithm utilizes the fact that the properties of hemorrhage and healthy tissues follow different distributions, and therefore an appropriate formulation of these distributions allows us to separate them through an Expectation-Maximization process. In addition, our algorithm is able to adaptively determine the number of clusters such that all the hemorrhage regions can be found without including noisy voxels. We demonstrate the results of our algorithm on publicly-available datasets that contain all different hemorrhage types in various sizes and intensities, and our results are compared to earlier unsupervised and supervised algorithms. The results show that our algorithm can outperform the other algorithms with most hemorrhage types.
MATE-KD: Masked Adversarial TExt, a Companion to Knowledge Distillation
Venue: arXiv cs.CL 2021
Year: 2021

The advent of large pre-trained language models has given rise to rapid progress in the field of Natural Language Processing (NLP). While the performance of these models on standard benchmarks has scaled with size, compression techniques such as knowledge distillation have been key in making them practical. We present, MATE-KD, a novel text-based adversarial training algorithm which improves the performance of knowledge distillation. MATE-KD first trains a masked language model based generator to perturb text by maximizing the divergence between teacher and student logits. Then using knowledge distillation a student is trained on both the original and the perturbed training samples. We evaluate our algorithm, using BERT-based models, on the GLUE benchmark and demonstrate that MATE-KD outperforms competitive adversarial learning and data augmentation baselines. On the GLUE test set our 6 layer RoBERTa based model outperforms BERT-Large.
An Open-Source Multi-Goal Reinforcement Learning Environment for Robotic Manipulation with Pybullet
Venue: arXiv cs.RO 2021
Year: 2021

This work re-implements the OpenAI Gym multi-goal robotic manipulation environment, originally based on the commercial Mujoco engine, onto the open-source Pybullet engine. By comparing the performances of the Hindsight Experience Replay-aided Deep Deterministic Policy Gradient agent on both environments, we demonstrate our successful re-implementation of the original environment. Besides, we provide users with new APIs to access a joint control mode, image observations and goals with customisable camera and a built-in on-hand camera. We further design a set of multi-step, multi-goal, long-horizon and sparse reward robotic manipulation tasks, aiming to inspire new goal-conditioned reinforcement learning algorithms for such challenges. We use a simple, human-prior-based curriculum learning method to benchmark the multi-step manipulation tasks. Discussions about future research opportunities regarding this kind of tasks are also provided.
Optimal transport with some directed distances
Venue: arXiv cs.IT 2021
Year: 2021

We present a toolkit of directed distances between quantile functions. By employing this, we solve some new optimal transport (OT) problems which e.g. considerably flexibilize some prominent OTs expressed through Wasserstein distances.
Lightweight compression of neural network feature tensors for collaborative intelligence
Venue: arXiv cs.LG 2021
Year: 2021

In collaborative intelligence applications, part of a deep neural network (DNN) is deployed on a relatively low-complexity device such as a mobile phone or edge device, and the remainder of the DNN is processed where more computing resources are available, such as in the cloud. This paper presents a novel lightweight compression technique designed specifically to code the activations of a split DNN layer, while having a low complexity suitable for edge devices and not requiring any retraining. We also present a modified entropy-constrained quantizer design algorithm optimized for clipped activations. When applied to popular object-detection and classification DNNs, we were able to compress the 32-bit floating point activations down to 0.6 to 0.8 bits, while keeping the loss in accuracy to less than 1%. When compared to HEVC, we found that the lightweight codec consistently provided better inference accuracy, by up to 1.3%. The performance and simplicity of this lightweight compression technique makes it an attractive option for coding a layer's activations in split neural networks for edge/cloud applications.
Robust Dynamic Multi-Modal Data Fusion: A Model Uncertainty Perspective
Venue: arXiv cs.LG 2021
Year: 2021

This paper is concerned with multi-modal data fusion (MMDF) under unexpected modality failures in nonlinear non-Gaussian dynamic processes. An efficient framework to tackle this problem is proposed. In particular, a notion termed modality "\emph{usefulness}", which takes a value of 1 or 0, is used for indicating whether the observation of this modality is useful or not. For $n$ modalities involved, $2^n$ combinations of their "\emph{usefulness}" values exist. Each combination defines one hypothetical model of the true data generative process. Then the problem of concern is formalized as a task of nonlinear non-Gaussian state filtering under model uncertainty, which is addressed by a dynamic model averaging (DMA) based particle filter (PF) algorithm. This DMA algorithm employs $2^n$ models, while all models share the same state-transition function and a unique set of particle values. That makes its computational complexity only slightly larger than a single model based PF algorithm, especially for scenarios in which $n$ is small. Experimental results show that the proposed solution outperforms remarkably state-of-the-art methods. Code and data are available at https://github.com/robinlau1981/fusion.
Towards Human-Free Automatic Quality Evaluation of German Summarization
Venue: arXiv cs.CL 2021
Year: 2021

Evaluating large summarization corpora using humans has proven to be expensive from both the organizational and the financial perspective. Therefore, many automatic evaluation metrics have been developed to measure the summarization quality in a fast and reproducible way. However, most of the metrics still rely on humans and need gold standard summaries generated by linguistic experts. Since BLANC does not require golden summaries and supposedly can use any underlying language model, we consider its application to the evaluation of summarization in German. This work demonstrates how to adjust the BLANC metric to a language other than English. We compare BLANC scores with the crowd and expert ratings, as well as with commonly used automatic metrics on a German summarization data set. Our results show that BLANC in German is especially good in evaluating informativeness.
GIPA: General Information Propagation Algorithm for Graph Learning
Venue: arXiv cs.LG 2021
Year: 2021

Graph neural networks (GNNs) have been popularly used in analyzing graph-structured data, showing promising results in various applications such as node classification, link prediction and network recommendation. In this paper, we present a new graph attention neural network, namely GIPA, for attributed graph data learning. GIPA consists of three key components: attention, feature propagation and aggregation. Specifically, the attention component introduces a new multi-layer perceptron based multi-head to generate better non-linear feature mapping and representation than conventional implementations such as dot-product. The propagation component considers not only node features but also edge features, which differs from existing GNNs that merely consider node features. The aggregation component uses a residual connection to generate the final embedding. We evaluate the performance of GIPA using the Open Graph Benchmark proteins (ogbn-proteins for short) dataset. The experimental results reveal that GIPA can beat the state-of-the-art models in terms of prediction accuracy, e.g., GIPA achieves an average test ROC-AUC of $0.8700\pm 0.0010$ and outperforms all the previous methods listed in the ogbn-proteins leaderboard.
HyKnow: End-to-End Task-Oriented Dialog Modeling with Hybrid Knowledge Management
Venue: arXiv cs.CL 2021
Year: 2021

Task-oriented dialog (TOD) systems typically manage structured knowledge (e.g. ontologies and databases) to guide the goal-oriented conversations. However, they fall short of handling dialog turns grounded on unstructured knowledge (e.g. reviews and documents). In this paper, we formulate a task of modeling TOD grounded on both structured and unstructured knowledge. To address this task, we propose a TOD system with hybrid knowledge management, HyKnow. It extends the belief state to manage both structured and unstructured knowledge, and is the first end-to-end model that jointly optimizes dialog modeling grounded on these two kinds of knowledge. We conduct experiments on the modified version of MultiWOZ 2.1 dataset, where dialogs are grounded on hybrid knowledge. Experimental results show that HyKnow has strong end-to-end performance compared to existing TOD systems. It also outperforms the pipeline knowledge management schemes, with higher unstructured knowledge retrieval accuracy.
High-level Intellectual Property Obfuscation via Decoy Constants
Venue: arXiv cs.CR 2021
Year: 2021

This paper presents a high-level circuit obfuscation technique to prevent the theft of intellectual property (IP) of integrated circuits. In particular, our technique protects a class of circuits that relies on constant multiplications, such as filters and neural networks, where the constants themselves are the IP to be protected. By making use of decoy constants and a key-based scheme, a reverse engineer adversary at an untrusted foundry is rendered incapable of discerning true constants from decoy constants. The time-multiplexed constant multiplication (TMCM) block of such circuits, which realizes the multiplication of an input variable by a constant at a time, is considered as our case study for obfuscation. Furthermore, two TMCM design architectures are taken into account; an implementation using a multiplier and a multiplierless shift-adds implementation. Optimization methods are also applied to reduce the hardware complexity of these architectures. The well-known satisfiability (SAT) and automatic test pattern generation (ATPG) attacks are used to determine the vulnerability of the obfuscated designs. It is observed that the proposed technique incurs small overheads in area, power, and delay that are comparable to the hardware complexity of prominent logic locking methods. Yet, the advantage of our approach is in the insight that constants -- instead of arbitrary circuit nodes -- become key-protected.
Efficient Stepping Algorithms and Implementations for Parallel Shortest Paths
Venue: arXiv cs.DS 2021
Year: 2021

In this paper, we study the single-source shortest-path (SSSP) problem with positive edge weights, which is a notoriously hard problem in the parallel context. In practice, the $Δ$-stepping algorithm proposed by Meyer and Sanders has been widely adopted. However, $Δ$-stepping has no known worst-case bounds for general graphs. The performance of $Δ$-stepping also highly relies on the parameter $Δ$. There have also been lots of algorithms with theoretical bounds, such as Radius-stepping, but they either have no implementations available or are much slower than $Δ$-stepping in practice. We propose a stepping algorithm framework that generalizes existing algorithms such as $Δ$-stepping and Radius-stepping. The framework allows for similar analysis and implementations of all stepping algorithms. We also propose a new ADT, lazy-batched priority queue (LaB-PQ), that abstracts the semantics of the priority queue needed by the stepping algorithms. We provide two data structures for LaB-PQ, focusing on theoretical and practical efficiency, respectively. Based on the new framework and LaB-PQ, we show two new stepping algorithms, $ρ$-stepping and $Δ^*$-stepping, that are simple, with non-trivial worst-case bounds, and fast in practice. The stepping algorithm framework also provides almost identical implementations for three algorithms: Bellman-Ford, $Δ^*$-stepping, and $ρ$-stepping. We compare our code with four state-of-the-art implementations. On five social and web graphs, $ρ$-stepping is 1.3--2.5x faster than all the existing implementations. On two road graphs, our $Δ^*$-stepping is at least 14\% faster than existing implementations, while $ρ$-stepping is also competitive. The almost identical implementations for stepping algorithms also allow for in-depth analyses and comparisons among the stepping algorithms in practice.
Global Wheat Challenge 2020: Analysis of the competition design and winning models
Venue: arXiv cs.CV 2021
Year: 2021

Data competitions have become a popular approach to crowdsource new data analysis methods for general and specialized data science problems. In plant phenotyping, data competitions have a rich history, and new outdoor field datasets have potential for new data competitions. We developed the Global Wheat Challenge as a generalization competition to see if solutions for wheat head detection from field images would work in different regions around the world. In this paper, we analyze the winning challenge solutions in terms of their robustness and the relative importance of model and data augmentation design decisions. We found that the design of the competition influence the selection of winning solutions and provide recommendations for future competitions in an attempt to garner more robust winning solutions.
Strategic Successive Refinement Coding for Bayesian Persuasion with Two Decoders
Venue: arXiv cs.IT 2021
Year: 2021

We study the multi-user Bayesian persuasion game between one encoder and two decoders, where the first decoder is better informed than the second decoder. We consider two perfect links, one to the first decoder only, and the other to both decoders. We consider that the encoder and both decoders are endowed with distinct and arbitrary distortion functions. We investigate the strategic source coding problem in which the encoder commits to an encoding while the decoders select the sequences of symbols that minimize their respective distortion functions. We characterize the optimal encoder distortion value by considering successive refinement coding with respect to a specific probability distribution which involves two auxiliary random variables, and captures the incentives constraints of both decoders.
Quantized Proximal Averaging Network for Analysis Sparse Coding
Venue: arXiv cs.LG 2021
Year: 2021

We solve the analysis sparse coding problem considering a combination of convex and non-convex sparsity promoting penalties. The multi-penalty formulation results in an iterative algorithm involving proximal-averaging. We then unfold the iterative algorithm into a trainable network that facilitates learning the sparsity prior. We also consider quantization of the network weights. Quantization makes neural networks efficient both in terms of memory and computation during inference, and also renders them compatible for low-precision hardware deployment. Our learning algorithm is based on a variant of the ADAM optimizer in which the quantizer is part of the forward pass and the gradients of the loss function are evaluated corresponding to the quantized weights while doing a book-keeping of the high-precision weights. We demonstrate applications to compressed image recovery and magnetic resonance image reconstruction. The proposed approach offers superior reconstruction accuracy and quality than state-of-the-art unfolding techniques and the performance degradation is minimal even when the weights are subjected to extreme quantization.
Community evolution in retweet networks
Venue: arXiv cs.SI 2021
Year: 2021

Communities in social networks often reflect close social ties between their members and their evolution through time. We propose an approach that tracks two aspects of community evolution in retweet networks: flow of the members in, out and between the communities, and their influence. We start with high resolution time windows, and then select several timepoints which exhibit large differences between the communities. For community detection, we propose a two-stage approach. In the first stage, we apply an enhanced Louvain algorithm, called Ensemble Louvain, to find stable communities. In the second stage, we form influence links between these communities, and identify linked super-communities. For the detected communities, we compute internal and external influence, and for individual users, the retweet h-index influence. We apply the proposed approach to three years of Twitter data of all Slovenian tweets. The analysis shows that the Slovenian tweetosphere is dominated by politics, that the left-leaning communities are larger, but that the right-leaning communities and users exhibit significantly higher impact. An interesting observation is that retweet networks change relatively gradually, despite such events as the emergence of the Covid-19 pandemic or the change of government.