OpenRaiser/Intern-Atlas huggingface dataset:
Semi-Supervised Data Programming with Subset Selection
Venue: arXiv cs.LG 2021
Year: 2021

The paradigm of data programming, which uses weak supervision in the form of rules/labelling functions, and semi-supervised learning, which augments small amounts of labelled data with a large unlabelled dataset, have shown great promise in several text classification scenarios. In this work, we argue that by not using any labelled data, data programming based approaches can yield sub-optimal performances, particularly when the labelling functions are noisy. The first contribution of this work is an introduction of a framework, \model which is a semi-supervised data programming paradigm that learns a \emph{joint model} that effectively uses the rules/labelling functions along with semi-supervised loss functions on the feature space. Next, we also study \modelss which additionally does subset selection on top of the joint semi-supervised data programming objective and \emph{selects} a set of examples that can be used as the labelled set by \model. The goal of \modelss is to ensure that the labelled data can \emph{complement} the labelling functions, thereby benefiting from both data-programming as well as appropriately selected data for human labelling. We demonstrate that by effectively combining semi-supervision, data-programming, and subset selection paradigms, we significantly outperform the current state-of-the-art on seven publicly available datasets. \footnote{The source code is available at \url{https://github.com/ayushbits/Semi-Supervised-LFs-Subset-Selection}}
Automated Search for Resource-Efficient Branched Multi-Task Networks
Venue: arXiv cs.CV 2021
Year: 2021

The multi-modal nature of many vision problems calls for neural network architectures that can perform multiple tasks concurrently. Typically, such architectures have been handcrafted in the literature. However, given the size and complexity of the problem, this manual architecture exploration likely exceeds human design abilities. In this paper, we propose a principled approach, rooted in differentiable neural architecture search, to automatically define branching (tree-like) structures in the encoding stage of a multi-task neural network. To allow flexibility within resource-constrained environments, we introduce a proxyless, resource-aware loss that dynamically controls the model size. Evaluations across a variety of dense prediction tasks show that our approach consistently finds high-performing branching structures within limited resource budgets.
Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbation
Venue: arXiv cs.CR 2021
Year: 2021

Graph neural networks (GNNs) have recently gained much attention for node and graph classification tasks on graph-structured data. However, multiple recent works showed that an attacker can easily make GNNs predict incorrectly via perturbing the graph structure, i.e., adding or deleting edges in the graph. We aim to defend against such attacks via developing certifiably robust GNNs. Specifically, we prove the certified robustness guarantee of any GNN for both node and graph classifications against structural perturbation. Moreover, we show that our certified robustness guarantee is tight. Our results are based on a recently proposed technique called randomized smoothing, which we extend to graph data. We also empirically evaluate our method for both node and graph classifications on multiple GNNs and multiple benchmark datasets. For instance, on the Cora dataset, Graph Convolutional Network with our randomized smoothing can achieve a certified accuracy of 0.49 when the attacker can arbitrarily add/delete at most 15 edges in the graph.
The Fairness-Accuracy Pareto Front
Venue: arXiv cs.LG 2021
Year: 2021

Algorithmic fairness seeks to identify and correct sources of bias in machine learning algorithms. Confoundingly, ensuring fairness often comes at the cost of accuracy. We provide formal tools in this work for reconciling this fundamental tension in algorithm fairness. Specifically, we put to use the concept of Pareto optimality from multi-objective optimization and seek the fairness-accuracy Pareto front of a neural network classifier. We demonstrate that many existing algorithmic fairness methods are performing the so-called linear scalarization scheme which has severe limitations in recovering Pareto optimal solutions. We instead apply the Chebyshev scalarization scheme which is provably superior theoretically and no more computationally burdensome at recovering Pareto optimal solutions compared to the linear scheme.
ETC-NLG: End-to-end Topic-Conditioned Natural Language Generation
Venue: arXiv cs.CL 2021
Year: 2021

Plug-and-play language models (PPLMs) enable topic-conditioned natural language generation by pairing large pre-trained generators with attribute models used to steer the predicted token distribution towards the selected topic. Despite their computational efficiency, PPLMs require large amounts of labeled texts to effectively balance generation fluency and proper conditioning, making them unsuitable for low-resource settings. We present ETC-NLG, an approach leveraging topic modeling annotations to enable fully-unsupervised End-to-end Topic-Conditioned Natural Language Generation over emergent topics in unlabeled document collections. We first test the effectiveness of our approach in a low-resource setting for Italian, evaluating the conditioning for both topic models and gold annotations. We then perform a comparative evaluation of ETC-NLG for Italian and English using a parallel corpus. Finally, we propose an automatic approach to estimate the effectiveness of conditioning on the generated utterances.
Uplink-Downlink Duality Between Multiple-Access and Broadcast Channels with Compressing Relays
Venue: arXiv cs.IT 2021
Year: 2021

Uplink-downlink duality refers to the fact that under a sum-power constraint, the capacity regions of a Gaussian multiple-access channel and a Gaussian broadcast channel with Hermitian transposed channel matrices are identical. This paper generalizes this result to a cooperative cellular network, in which remote access-points are deployed as relays in serving the users under the coordination of a central processor (CP). In this model, the users and the relays are connected over noisy wireless links, while the relays and the CP are connected over noiseless but rate-limited fronthaul links. Based on a Lagrangian technique, this paper establishes a duality relationship between such a multiple-access relay channel and broadcast relay channel, under the assumption that the relays use compression-based strategies. Specifically, we show that under the same total transmit power constraint and individual fronthaul rate constraints, the achievable rate regions of the Gaussian multiple-access and broadcast relay channels are identical, when either independent compression or Wyner-Ziv and multivariate compression strategies are used. The key observations are that if the beamforming vectors at the relays are fixed, the sum-power minimization problems under the achievable rate and fronthaul constraints in both the uplink and the downlink can be transformed into either a linear programming or a semidefinite programming problem depending on the compression technique, and that the uplink and downlink problems are Lagrangian duals of each other. Moreover, the dual variables corresponding to the downlink rate constraints become the uplink powers; the dual variables corresponding to the downlink fronthaul constraints become the uplink quantization noises. This duality relationship enables an efficient algorithm for optimizing the downlink transmission and relaying strategies based on the uplink.
O'Reach: Even Faster Reachability in Large Graphs
Venue: arXiv cs.DS 2021
Year: 2021

One of the most fundamental problems in computer science is the reachability problem: Given a directed graph and two vertices s and t, can s reach t via a path? We revisit existing techniques and combine them with new approaches to support a large portion of reachability queries in constant time using a linear-sized reachability index. Our new algorithm O'Reach can be easily combined with previously developed solutions for the problem or run standalone. In a detailed experimental study, we compare a variety of algorithms with respect to their index-building and query times as well as their memory footprint on a diverse set of instances. Our experiments indicate that the query performance often depends strongly not only on the type of graph, but also on the result, i.e., reachable or unreachable. Furthermore, we show that previous algorithms are significantly sped up when combined with our new approach in almost all scenarios. Surprisingly, due to cache effects, a higher investment in space doesn't necessarily pay off: Reachability queries can often be answered even faster than single memory accesses in a precomputed full reachability matrix.
Why Shouldn't All Charts Be Scatter Plots? Beyond Precision-Driven Visualizations
Venue: arXiv cs.HC 2021
Year: 2021

A central concept in information visualization research and practice is the notion of visual variable effectiveness, or the perceptual precision at which values are decoded given visual channels of encoding. Formative work from Cleveland & McGill has shown that position along a common axis is the most effective visual variable for comparing individual values. One natural conclusion is that any chart that is not a dot plot or scatterplot is deficient and should be avoided. In this paper we refute a caricature of this "scatterplots only" argument as a way to call for new perspectives on how information visualization is researched, taught, and evaluated.
Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio
Venue: arXiv cs.DS 2021
Year: 2021

We show, assuming the Strong Exponential Time Hypothesis, that for every $\varepsilon > 0$, approximating directed Diameter on $m$-arc graphs within ratio $7/4 - \varepsilon$ requires $m^{4/3 - o(1)}$ time. Our construction uses nonnegative edge weights but even holds for sparse digraphs, i.e., for which the number of vertices $n$ and the number of arcs $m$ satisfy $m = n \log^{O(1)} n$. This is the first result that conditionally rules out a near-linear time $5/3$-approximation for Diameter.
Each Part Matters: Local Patterns Facilitate Cross-view Geo-localization
Venue: arXiv cs.CV 2021
Year: 2021

Cross-view geo-localization is to spot images of the same geographic target from different platforms, e.g., drone-view cameras and satellites. It is challenging in the large visual appearance changes caused by extreme viewpoint variations. Existing methods usually concentrate on mining the fine-grained feature of the geographic target in the image center, but underestimate the contextual information in neighbor areas. In this work, we argue that neighbor areas can be leveraged as auxiliary information, enriching discriminative clues for geolocalization. Specifically, we introduce a simple and effective deep neural network, called Local Pattern Network (LPN), to take advantage of contextual information in an end-to-end manner. Without using extra part estimators, LPN adopts a square-ring feature partition strategy, which provides the attention according to the distance to the image center. It eases the part matching and enables the part-wise representation learning. Owing to the square-ring partition design, the proposed LPN has good scalability to rotation variations and achieves competitive results on three prevailing benchmarks, i.e., University-1652, CVUSA and CVACT. Besides, we also show the proposed LPN can be easily embedded into other frameworks to further boost performance.
BumbleBee: Application-aware adaptation for container orchestration
Venue: arXiv cs.DC 2021
Year: 2021

Modern applications have embraced separation of concerns as a first-order organizing principle through the use of containers, container orchestration, and service meshes. However, adaptation to unexpected network variation has not followed suit. We present BumbleBee, a lightweight extension to the container ecosystem that supports application-aware adaptation. BumbleBee provides a simple abstraction for making decisions about network data using application semantics. Because this abstraction is placed within the communications framework of a modern service mesh, it is closer to the point at which changes are detected, providing more responsive and effective adaptation than possible at endpoints.
Shadow-Catcher: Looking Into Shadows to Detect Ghost Objects in Autonomous Vehicle 3D Sensing
Venue: arXiv cs.CR 2021
Year: 2021

LiDAR-driven 3D sensing allows new generations of vehicles to achieve advanced levels of situation awareness. However, recent works have demonstrated that physical adversaries can spoof LiDAR return signals and deceive 3D object detectors to erroneously detect "ghost" objects. Existing defenses are either impractical or focus only on vehicles. Unfortunately, it is easier to spoof smaller objects such as pedestrians and cyclists, but harder to defend against and can have worse safety implications. To address this gap, we introduce Shadow-Catcher, a set of new techniques embodied in an end-to-end prototype to detect both large and small ghost object attacks on 3D detectors. We characterize a new semantically meaningful physical invariant (3D shadows) which Shadow-Catcher leverages for validating objects. Our evaluation on the KITTI dataset shows that Shadow-Catcher consistently achieves more than 94% accuracy in identifying anomalous shadows for vehicles, pedestrians, and cyclists, while it remains robust to a novel class of strong "invalidation" attacks targeting the defense system. Shadow-Catcher can achieve real-time detection, requiring only between 0.003s-0.021s on average to process an object in a 3D point cloud on commodity hardware and achieves a 2.17x speedup compared to prior work
Local error quantification for Neural Network Differential Equation solvers
Venue: arXiv cs.LG 2021
Year: 2021

Neural networks have been identified as powerful tools for the study of complex systems. A noteworthy example is the neural network differential equation (NN DE) solver, which can provide functional approximations to the solutions of a wide variety of differential equations. Such solvers produce robust functional expressions, are well suited for further manipulations on the quantities of interest (for example, taking derivatives), and capable of leveraging the modern advances in parallelization and computing power. However, there is a lack of work on the role precise error quantification can play in their predictions: usually, the focus is on ambiguous and/or global measures of performance like the loss function and/or obtaining global bounds on the errors associated with the predictions. Precise, local error quantification is seldom possible without external means or outright knowledge of the true solution. We address these concerns in the context of dynamical system NN DE solvers, leveraging learnt information within the NN DE solvers to develop methods that allow them to be more accurate and efficient, while still pursuing an unsupervised approach that does not rely on external tools or data. We achieve this via methods that can precisely estimate NN DE solver prediction errors point-wise, thus allowing the user the capacity for efficient and targeted error correction. We exemplify the utility of our methods by testing them on a nonlinear and a chaotic system each.
BSF-skeleton: A Template for Parallelization of Iterative Numerical Algorithms on Cluster Computing Systems
Venue: arXiv cs.DC 2021
Year: 2021

This article describes a method for creating applications for cluster computing systems using the parallel BSF skeleton based on the original BSF (Bulk Synchronous Farm) model of parallel computations developed by the author earlier. This model uses the master/slave paradigm. The main advantage of the BSF model is that it allows to estimate the scalability of a parallel algorithm before its implementation. Another important feature of the BSF model is the representation of problem data in the form of lists that greatly simplifies the logic of building applications. The BSF skeleton is designed for creating parallel programs in C++ using the MPI library. The scope of the BSF skeleton is iterative numerical algorithms of high computational complexity. The BSF skeleton has the following distinctive features. - The BSF-skeleton completely encapsulates all aspects that are associated with parallelizing a program. - The BSF skeleton allows error-free compilation at all stages of application development. - The BSF skeleton supports OpenMP programming model and workflows.
Modality Attention and Sampling Enables Deep Learning with Heterogeneous Marker Combinations in Fluorescence Microscopy
Venue: arXiv cs.CV 2021
Year: 2021

Fluorescence microscopy allows for a detailed inspection of cells, cellular networks, and anatomical landmarks by staining with a variety of carefully-selected markers visualized as color channels. Quantitative characterization of structures in acquired images often relies on automatic image analysis methods. Despite the success of deep learning methods in other vision applications, their potential for fluorescence image analysis remains underexploited. One reason lies in the considerable workload required to train accurate models, which are normally specific for a given combination of markers, and therefore applicable to a very restricted number of experimental settings. We herein propose Marker Sampling and Excite, a neural network approach with a modality sampling strategy and a novel attention module that together enable (i) flexible training with heterogeneous datasets with combinations of markers and (ii) successful utility of learned models on arbitrary subsets of markers prospectively. We show that our single neural network solution performs comparably to an upper bound scenario where an ensemble of many networks is naïvely trained for each possible marker combination separately. In addition, we demonstrate the feasibility of this framework in high-throughput biological analysis by revising a recent quantitative characterization of bone marrow vasculature in 3D confocal microscopy datasets and further confirm the validity of our approach on an additional, significantly different dataset of microvessels in fetal liver tissues. Not only can our work substantially ameliorate the use of deep learning in fluorescence microscopy analysis, but it can also be utilized in other fields with incomplete data acquisitions and missing modalities.
Rethinking the Objectives of Extractive Question Answering
Venue: arXiv cs.CL 2021
Year: 2021

This work demonstrates that using the objective with independence assumption for modelling the span probability $P(a_s,a_e) = P(a_s)P(a_e)$ of span starting at position $a_s$ and ending at position $a_e$ has adverse effects. Therefore we propose multiple approaches to modelling joint probability $P(a_s,a_e)$ directly. Among those, we propose a compound objective, composed from the joint probability while still keeping the objective with independence assumption as an auxiliary objective. We find that the compound objective is consistently superior or equal to other assumptions in exact match. Additionally, we identified common errors caused by the assumption of independence and manually checked the counterpart predictions, demonstrating the impact of the compound objective on the real examples. Our findings are supported via experiments with three extractive QA models (BIDAF, BERT, ALBERT) over six datasets and our code, individual results and manual analysis are available online.
Zero-Resource Knowledge-Grounded Dialogue Generation
Venue: arXiv cs.CL 2021
Year: 2021

While neural conversation models have shown great potentials towards generating informative and engaging responses via introducing external knowledge, learning such a model often requires knowledge-grounded dialogues that are difficult to obtain. To overcome the data challenge and reduce the cost of building a knowledge-grounded dialogue system, we explore the problem under a zero-resource setting by assuming no context-knowledge-response triples are needed for training. To this end, we propose representing the knowledge that bridges a context and a response and the way that the knowledge is expressed as latent variables, and devise a variational approach that can effectively estimate a generation model from a dialogue corpus and a knowledge corpus that are independent with each other. Evaluation results on three benchmarks of knowledge-grounded dialogue generation indicate that our model can achieve comparable performance with state-of-the-art methods that rely on knowledge-grounded dialogues for training, and exhibits a good generalization ability over different topics and different datasets.
The Double Exponential Runtime is Tight for 2-Stage Stochastic ILPs
Venue: arXiv cs.CC 2021
Year: 2021

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called $2$-stage stochastic. A $2$-stage stochastic ILP is an integer program of the form $\min \{c^T x \mid \mathcal{A} x = b, \ell \leq x \leq u, x \in \mathbb{Z}^{r + ns} \}$ where the constraint matrix $\mathcal{A} \in \mathbb{Z}^{nt \times r +ns}$ consists of $n$ matrices $A_i \in \mathbb{Z}^{t \times r}$ on the vertical line and $n$ matrices $B_i \in \mathbb{Z}^{t \times s}$ on the diagonal line aside. First, we show a stronger hardness result for a number theoretic problem called Quadratic Congruences where the objective is to compute a number $z \leq γ$ satisfying $z^2 \equiv α\bmod β$ for given $α, β, γ\in \mathbb{Z}$. This problem was proven to be NP-hard already in 1978 by Manders and Adleman. However, this hardness only applies for instances where the prime factorization of $β$ admits large multiplicities of each prime number. We circumvent this necessity proving that the problem remains NP-hard, even if each prime number only occurs constantly often. Then, using this new hardness result for the Quadratic Congruences problem, we prove a lower bound of $2^{2^{δ(s+t)}} |I|^{O(1)}$ for some $δ> 0$ for the running time of any algorithm solving $2$-stage stochastic ILPs assuming the Exponential Time Hypothesis (ETH). Here, $|I|$ is the encoding length of the instance. This result even holds if $r$, $||b||_{\infty}$, $||c||_{\infty}, ||\ell||_{\infty}$ and the largest absolute value $Δ$ in the constraint matrix $\mathcal{A}$ are constant. This shows that the state-of-the-art algorithms are nearly tight. Further, it proves the suspicion that these ILPs are indeed harder to solve than the closely related $n$-fold ILPs where the contraint matrix is the transpose of $\mathcal A$.