OpenRaiser/Intern-Atlas huggingface dataset:
Scientific Discourse Tagging for Evidence Extraction
Venue: arXiv cs.CL 2021
Year: 2021

Evidence plays a crucial role in any biomedical research narrative, providing justification for some claims and refutation for others. We seek to build models of scientific argument using information extraction methods from full-text papers. We present the capability of automatically extracting text fragments from primary research papers that describe the evidence presented in that paper's figures, which arguably provides the raw material of any scientific argument made within the paper. We apply richly contextualized deep representation learning pre-trained on biomedical domain corpus to the analysis of scientific discourse structures and the extraction of "evidence fragments" (i.e., the text in the results section describing data presented in a specified subfigure) from a set of biomedical experimental research articles. We first demonstrate our state-of-the-art scientific discourse tagger on two scientific discourse tagging datasets and its transferability to new datasets. We then show the benefit of leveraging scientific discourse tags for downstream tasks such as claim-extraction and evidence fragment detection. Our work demonstrates the potential of using evidence fragments derived from figure spans for improving the quality of scientific claims by cataloging, indexing and reusing evidence fragments as independent documents.
Survey on Terahertz Nanocommunication and Networking: A Top-Down Perspective
Venue: arXiv cs.NI 2021
Year: 2021

Recent developments in nanotechnology herald nanometer-sized devices expected to bring light to a number of groundbreaking applications. Communication with and among nanodevices will be needed for unlocking the full potential of such applications. As the traditional communication approaches cannot be directly applied in nanocommunication, several alternative paradigms have emerged. Among them, electromagnetic nanocommunication in the terahertz (THz) frequency band is particularly promising, mainly due to the breakthrough of novel materials such as graphene. For this reason, numerous research efforts are nowadays targeting THz band nanocommunication and consequently nanonetworking. As it is expected that these trends will continue in the future, we see it beneficial to summarize the current status in these research domains. In this survey, we therefore aim to provide an overview of the current THz nanocommunication and nanonetworking research. Specifically, we discuss the applications envisioned to be supported by nanonetworks operating in the THz band, together with the requirements such applications pose on the underlying nanonetworks. Subsequently, we provide an overview of the current contributions on the different layers of the protocol stack, as well as the available channel models and experimentation tools. As the final contribution, we identify a number of open research challenges and outline several potential future research directions.
Topology is irrelevant (in a dichotomy conjecture for infinite domain constraint satisfaction problems)
Venue: arXiv cs.LO 2021
Year: 2021

The tractability conjecture for finite domain Constraint Satisfaction Problems (CSPs) stated that such CSPs are solvable in polynomial time whenever there is no natural reduction, in some precise technical sense, from the 3-SAT problem; otherwise, they are NP-complete. Its recent resolution draws on an algebraic characterization of the conjectured borderline: the CSP of a finite structure permits no natural reduction from 3-SAT if and only if the stabilizer of the polymorphism clone of the core of the structure satisfies some nontrivial system of identities, and such satisfaction is always witnessed by several specific nontrivial systems of identities which do not depend on the structure. The tractability conjecture has been generalized in the above formulation to a certain class of infinite domain CSPs, namely, CSPs of reducts of finitely bounded homogeneous structures. It was subsequently shown that the conjectured borderline between hardness and tractability, i.e., a natural reduction from 3-SAT, can be characterized for this class by a combination of algebraic and topological properties. However, it was not known whether the topological component is essential in this characterization. We provide a negative answer to this question by proving that the borderline is characterized by one specific algebraic identity, namely the pseudo-Siggers identity $αs(x,y,x,z,y,z) \approx βs(y,x,z,x,z,y)$. This accomplishes one of the steps of a proposed strategy for reducing the infinite domain CSP dichotomy conjecture to the finite case. Our main theorem is also of independent mathematical interest, characterizing a topological property of any $ω$-categorical core structure (the existence of a continuous homomorphism of a stabilizer of its polymorphism clone to the projections) in purely algebraic terms (the failure of an identity as above).
Human to Robot Whole-Body Motion Transfer
Venue: arXiv cs.RO 2021
Year: 2021

Transferring human motion to a mobile robotic manipulator and ensuring safe physical human-robot interaction are crucial steps towards automating complex manipulation tasks in human-shared environments. In this work, we present a novel human to robot whole-body motion transfer framework. We propose a general solution to the correspondence problem, namely a mapping between the observed human posture and the robot one. For achieving real-time imitation and effective redundancy resolution, we use the whole-body control paradigm, proposing a specific task hierarchy, and present a differential drive control algorithm for the wheeled robot base. To ensure safe physical human-robot interaction, we propose a novel variable admittance controller that stably adapts the dynamics of the end-effector to switch between stiff and compliant behaviors. We validate our approach through several real-world experiments with the TIAGo robot. Results show effective real-time imitation and dynamic behavior adaptation. This constitutes an easy way for a non-expert to transfer a manipulation skill to an assistive robot.
Natural Language Adversarial Defense through Synonym Encoding
Venue: arXiv cs.CL 2021
Year: 2021

In the area of natural language processing, deep learning models are recently known to be vulnerable to various types of adversarial perturbations, but relatively few works are done on the defense side. Especially, there exists few effective defense method against the successful synonym substitution based attacks that preserve the syntactic structure and semantic information of the original text while fooling the deep learning models. We contribute in this direction and propose a novel adversarial defense method called Synonym Encoding Method (SEM). Specifically, SEM inserts an encoder before the input layer of the target model to map each cluster of synonyms to a unique encoding and trains the model to eliminate possible adversarial perturbations without modifying the network architecture or adding extra data. Extensive experiments demonstrate that SEM can effectively defend the current synonym substitution based attacks and block the transferability of adversarial examples. SEM is also easy and efficient to scale to large models and big datasets.
Linear-Time Recognition of Double-Threshold Graphs
Venue: arXiv cs.DS 2021
Year: 2021

A graph $G = (V,E)$ is a double-threshold graph if there exist a vertex-weight function $w \colon V \to \mathbb{R}$ and two real numbers $\mathtt{lb}, \mathtt{ub} \in \mathbb{R}$ such that $uv \in E$ if and only if $\mathtt{lb} \le \mathtt{w}(u) + \mathtt{w}(v) \le \mathtt{ub}$. In the literature, those graphs are studied also as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs that relates them to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [Algorithmica 2020] ran in $O(n^{3} m)$ time, where $n$ and $m$ are the numbers of vertices and edges, respectively.
Segmentation Transformer: Object-Contextual Representations for Semantic Segmentation
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we address the semantic segmentation problem with a focus on the context aggregation strategy. Our motivation is that the label of a pixel is the category of the object that the pixel belongs to. We present a simple yet effective approach, object-contextual representations, characterizing a pixel by exploiting the representation of the corresponding object class. First, we learn object regions under the supervision of ground-truth segmentation. Second, we compute the object region representation by aggregating the representations of the pixels lying in the object region. Last, % the representation similarity we compute the relation between each pixel and each object region and augment the representation of each pixel with the object-contextual representation which is a weighted aggregation of all the object region representations according to their relations with the pixel. We empirically demonstrate that the proposed approach achieves competitive performance on various challenging semantic segmentation benchmarks: Cityscapes, ADE20K, LIP, PASCAL-Context, and COCO-Stuff. Cityscapes, ADE20K, LIP, PASCAL-Context, and COCO-Stuff. Our submission "HRNet + OCR + SegFix" achieves 1-st place on the Cityscapes leaderboard by the time of submission. Code is available at: https://git.io/openseg and https://git.io/HRNet.OCR. We rephrase the object-contextual representation scheme using the Transformer encoder-decoder framework. The details are presented in~Section3.3.
Efficient Large-Scale Multi-Drone Delivery Using Transit Networks
Venue: arXiv cs.RO 2021
Year: 2021

We consider the problem of controlling a large fleet of drones to deliver packages simultaneously across broad urban areas. To conserve energy, drones hop between public transit vehicles (e.g., buses and trams). We design a comprehensive algorithmic framework that strives to minimize the maximum time to complete any delivery. We address the multifaceted complexity of the problem through a two-layer approach. First, the upper layer assigns drones to package delivery sequences with a near-optimal polynomial-time task allocation algorithm. Then, the lower layer executes the allocation by periodically routing the fleet over the transit network while employing efficient bounded-suboptimal multi-agent pathfinding techniques tailored to our setting. Experiments demonstrate the efficiency of our approach on settings with up to $200$ drones, $5000$ packages, and transit networks with up to $8000$ stops in San Francisco and Washington DC. Our results show that the framework computes solutions typically within a few seconds on commodity hardware, and that drones travel up to $360 \%$ of their flight range with public transit.
Hierarchical Neural Architecture Search via Operator Clustering
Venue: arXiv cs.LG 2021
Year: 2021

Recently, the efficiency of automatic neural architecture design has been significantly improved by gradient-based search methods such as DARTS. However, recent literature has brought doubt to the generalization ability of DARTS, arguing that DARTS performs poorly when the search space is changed, i.e, when different set of candidate operators are used. Regularization techniques such as early stopping have been proposed to partially solve this problem. In this paper, we tackle this problem from a different perspective by identifying two contributing factors to the collapse of DARTS when the search space changes: (1) the correlation of similar operators incurs unfavorable competition among them and makes their relative importance score unreliable and (2) the optimization complexity gap between the proxy search stage and the final training. Based on these findings, we propose a new hierarchical search algorithm. With its operator clustering and optimization complexity match, the algorithm can consistently find high-performance architecture across various search spaces. For all the five variants of the popular cell-based search spaces, the proposed algorithm always obtains state-of-the-art architecture with best accuracy on the CIFAR-10, CIFAR-100 and ImageNet over other well-established DARTS-alike algorithms. Code is available at https://github.com/susan0199/StacNAS.
B-Spline CNNs on Lie Groups
Venue: arXiv cs.LG 2021
Year: 2021

Group convolutional neural networks (G-CNNs) can be used to improve classical CNNs by equipping them with the geometric structure of groups. Central in the success of G-CNNs is the lifting of feature maps to higher dimensional disentangled representations, in which data characteristics are effectively learned, geometric data-augmentations are made obsolete, and predictable behavior under geometric transformations (equivariance) is guaranteed via group theory. Currently, however, the practical implementations of G-CNNs are limited to either discrete groups (that leave the grid intact) or continuous compact groups such as rotations (that enable the use of Fourier theory). In this paper we lift these limitations and propose a modular framework for the design and implementation of G-CNNs for arbitrary Lie groups. In our approach the differential structure of Lie groups is used to expand convolution kernels in a generic basis of B-splines that is defined on the Lie algebra. This leads to a flexible framework that enables localized, atrous, and deformable convolutions in G-CNNs by means of respectively localized, sparse and non-uniform B-spline expansions. The impact and potential of our approach is studied on two benchmark datasets: cancer detection in histopathology slides in which rotation equivariance plays a key role and facial landmark localization in which scale equivariance is important. In both cases, G-CNN architectures outperform their classical 2D counterparts and the added value of atrous and localized group convolutions is studied in detail.
Box Covers and Domain Orderings for Beyond Worst-Case Join Processing
Venue: arXiv cs.DB 2021
Year: 2021

Recent beyond worst-case optimal join algorithms Minesweeper and its generalization Tetris have brought the theory of indexing and join processing together by developing a geometric framework for joins. These algorithms take as input an index $\mathcal{B}$, referred to as a box cover, that stores output gaps that can be inferred from traditional indexes, such as B+ trees or tries, on the input relations. The performances of these algorithms highly depend on the certificate of $\mathcal{B}$, which is the smallest subset of gaps in $\mathcal{B}$ whose union covers all of the gaps in the output space of a query $Q$. We study how to generate box covers that contain small size certificates to guarantee efficient runtimes for these algorithms. First, given a query $Q$ over a set of relations of size $N$ and a fixed set of domain orderings for the attributes, we give a $\tilde{O}(N)$-time algorithm called GAMB which generates a box cover for $Q$ that is guaranteed to contain the smallest size certificate across any box cover for $Q$. Second, we show that finding a domain ordering to minimize the box cover size and certificate is NP-hard through a reduction from the 2 consecutive block minimization problem on boolean matrices. Our third contribution is a $\tilde{O}(N)$-time approximation algorithm called ADORA to compute domain orderings, under which one can compute a box cover of size $\tilde{O}(K^r)$, where $K$ is the minimum box cover for $Q$ under any domain ordering and $r$ is the maximum arity of any relation. This guarantees certificates of size $\tilde{O}(K^r)$. We combine ADORA and GAMB with Tetris to form a new algorithm we call TetrisReordered, which provides several new beyond worst-case bounds. On infinite families of queries, TetrisReordered's runtimes are unboundedly better than the bounds stated in prior work.
A Re-classification of Information Seeking Tasks and Their Computational Solutions
Venue: arXiv cs.AI 2021
Year: 2021

This article presents a re-classification of information seeking (IS) tasks, concepts, and algorithms. The proposed taxonomy provides new dimensions to look into information seeking tasks and methods. The new dimensions include the number of search iterations, search goal types, and procedures to reach these goals. Differences along these dimensions for the information seeking tasks call for suitable computational solutions. The article then reviews machine learning solutions that match each new category. The paper ends with a review of evaluation campaigns for IS systems.
MGP-AttTCN: An Interpretable Machine Learning Model for the Prediction of Sepsis
Venue: arXiv cs.LG 2021
Year: 2021

With a mortality rate of 5.4 million lives worldwide every year and a healthcare cost of more than 16 billion dollars in the USA alone, sepsis is one of the leading causes of hospital mortality and an increasing concern in the ageing western world. Recently, medical and technological advances have helped re-define the illness criteria of this disease, which is otherwise poorly understood by the medical society. Together with the rise of widely accessible Electronic Health Records, the advances in data mining and complex nonlinear algorithms are a promising avenue for the early detection of sepsis. This work contributes to the research effort in the field of automated sepsis detection with an open-access labelling of the medical MIMIC-III data set. Moreover, we propose MGP-AttTCN: a joint multitask Gaussian Process and attention-based deep learning model to early predict the occurrence of sepsis in an interpretable manner. We show that our model outperforms the current state-of-the-art and present evidence that different labelling heuristics lead to discrepancies in task difficulty. For instance, when predicting sepsis five hours prior to onset on our new realistic labels, our proposed model achieves an area under the ROC curve of 0.660 and an area under the PR curve of 0.483, whereas the (less interpretable) previous state-of-the-art model (MGP-TCN) achieves 0.635 AUROC and 0.460 AUPR and the popular commercial InSight model achieves 0.490 AUROC and 0.359 AUPR.
A Novel Adaptive Controller for Robot Manipulators based on Active Inference
Venue: arXiv cs.RO 2021
Year: 2021

More adaptive controllers for robot manipulators are needed, which can deal with large model uncertainties. This paper presents a novel active inference controller (AIC) as an adaptive control scheme for industrial robots. This scheme is easily scalable to high degrees-of-freedom, and it maintains high performance even in the presence of large unmodeled dynamics. The proposed method is based on active inference, a promising neuroscientific theory of the brain, which describes a biologically plausible algorithm for perception and action. In this work, we formulate active inference from a control perspective, deriving a model-free control law which is less sensitive to unmodeled dynamics. The performance and the adaptive properties of the algorithm are compared to a state-of-the-art model reference adaptive controller (MRAC) in an experimental setup with a real 7-DOF robot arm. The results showed that the AIC outperformed the MRAC in terms of adaptability, providing a more general control law. This confirmed the relevance of active inference for robot control.
Threshold-Secure Coding with Shared Key
Venue: arXiv cs.IT 2021
Year: 2021

Cryptographic protocols are often implemented at upper layers of communication networks, while error-correcting codes are employed at the physical layer. In this paper, we consider utilizing readily-available physical layer functions, such as encoders and decoders, together with shared keys to provide a threshold-type security scheme. To this end, we first consider a scenario where the effect of the physical layer is omitted and all the channels between the involved parties are assumed to be noiseless. We introduce a model for threshold-secure coding, where the legitimate parties communicate using a shared key such that an eavesdropper does not get any information, in an information-theoretic sense, about the key as well as about any subset of the input symbols of size up to a certain threshold. Then, a framework is provided for constructing threshold-secure codes from linear block codes while characterizing the requirements to satisfy the reliability and security conditions. Moreover, we propose a threshold-secure coding scheme, based on Reed-Muller (RM) codes, that meets security and reliability conditions. It is shown that the encoder and the decoder of the scheme can be implemented efficiently with quasi-linear time complexity. In particular, a successive cancellation decoder is shown for the RM-based coding scheme. Then we extend the setup to the scenario where the channel between the legitimate parties is no longer noiseless. The reliability condition for noisy channels is then modified accordingly, and a method is described to construct codes attaining threshold security as well as desired reliability. Also, we propose a coding scheme based on RM codes for threshold security and robustness designed for binary erasure channels along with a unified successive cancellation decoder. The proposed threshold-secure coding schemes are flexible and can be adapted for different key lengths.
Using GANs for Sharing Networked Time Series Data: Challenges, Initial Promise, and Open Questions
Venue: arXiv cs.LG 2021
Year: 2021

Limited data access is a longstanding barrier to data-driven research and development in the networked systems community. In this work, we explore if and how generative adversarial networks (GANs) can be used to incentivize data sharing by enabling a generic framework for sharing synthetic datasets with minimal expert knowledge. As a specific target, our focus in this paper is on time series datasets with metadata (e.g., packet loss rate measurements with corresponding ISPs). We identify key challenges of existing GAN approaches for such workloads with respect to fidelity (e.g., long-term dependencies, complex multidimensional relationships, mode collapse) and privacy (i.e., existing guarantees are poorly understood and can sacrifice fidelity). To improve fidelity, we design a custom workflow called DoppelGANger (DG) and demonstrate that across diverse real-world datasets (e.g., bandwidth measurements, cluster requests, web sessions) and use cases (e.g., structural characterization, predictive modeling, algorithm comparison), DG achieves up to 43% better fidelity than baseline models. Although we do not resolve the privacy problem in this work, we identify fundamental challenges with both classical notions of privacy and recent advances to improve the privacy properties of GANs, and suggest a potential roadmap for addressing these challenges. By shedding light on the promise and challenges, we hope our work can rekindle the conversation on workflows for data sharing.
Automated Patch Assessment for Program Repair at Scale
Venue: arXiv cs.SE 2021
Year: 2021

In this paper, we do automatic correctness assessment for patches generated by program repair systems. We consider the human-written patch as ground truth oracle and randomly generate tests based on it, a technique proposed by Shamshiri et al., called Random testing with Ground Truth (RGT) in this paper. We build a curated dataset of 638 patches for Defects4J generated by 14 state-of-the-art repair systems, we evaluate automated patch assessment on this dataset. The results of this study are novel and significant: First, we improve the state of the art performance of automatic patch assessment with RGT by 190% by improving the oracle; Second, we show that RGT is reliable enough to help scientists to do overfitting analysis when they evaluate program repair systems; Third, we improve the external validity of the program repair knowledge with the largest study ever.