OpenRaiser/Intern-Atlas huggingface dataset:
Waypoint Routing on Bounded Treewidth Graphs
Venue: arXiv cs.DS 2021
Year: 2021

In the \textsc{Waypoint Routing Problem} one is given an undirected capacitated and weighted graph $G$, a source-destination pair $s,t\in V(G)$ and a set $W\subseteq V(G)$, of \emph{waypoints}. The task is to find a walk which starts at the source vertex $s$, visits, in any order, all waypoints, ends at the destination vertex $t$, respects edge capacities, that is, traverses each edge at most as many times as is its capacity, and minimizes the cost computed as the sum of costs of traversed edges with multiplicities. We study the problem for graphs of bounded treewidth and present a new algorithm for the problem working in $2^{O(\mathrm{tw})}\cdot n$ time, significantly improving upon the previously known algorithms. We also show that this running time is optimal for the problem under Exponential Time Hypothesis.
An exploration of the influence of path choice in game-theoretic attribution algorithms
Venue: arXiv cs.LG 2021
Year: 2021

We compare machine learning explainability methods based on the theory of atomic (Shapley, 1953) and infinitesimal (Aumann and Shapley, 1974) games, in a theoretical and experimental investigation into how the model and choice of integration path can influence the resulting feature attributions. To gain insight into differences in attributions resulting from interventional Shapley values (Sundararajan and Najmi, 2019; Janzing et al., 2019; Chen et al., 2019) and Generalized Integrated Gradients (GIG) (Merrill et al., 2019) we note interventional Shapley is equivalent to a multi-path integration along $n!$ paths where $n$ is the number of model input features. Applying Stoke's theorem we show that the path symmetry of these two methods results in the same attributions when the model is composed of a sum of separable functions of individual features and a sum of two-feature products. We then perform a series of experiments with varying degrees of data missingness to demonstrate how interventional Shapley's multi-path approach can yield less consistent attributions than the single straight-line path of Aumann-Shapley. We argue this is because the multiple paths employed by interventional Shapley extend away from the training data manifold and are therefore more likely to pass through regions where the model has little support. In the absence of a more meaningful path choice, we therefore advocate the straight-line path since it will almost always pass closer to the data manifold. Among straight-line path attribution algorithms, GIG is uniquely robust since it will still yield Shapley values for atomic games modeled by decision trees.
Evaluation for Weakly Supervised Object Localization: Protocol, Metrics, and Datasets
Venue: arXiv cs.CV 2021
Year: 2021

Weakly-supervised object localization (WSOL) has gained popularity over the last years for its promise to train localization models with only image-level labels. Since the seminal WSOL work of class activation mapping (CAM), the field has focused on how to expand the attention regions to cover objects more broadly and localize them better. However, these strategies rely on full localization supervision for validating hyperparameters and model selection, which is in principle prohibited under the WSOL setup. In this paper, we argue that WSOL task is ill-posed with only image-level labels, and propose a new evaluation protocol where full supervision is limited to only a small held-out set not overlapping with the test set. We observe that, under our protocol, the five most recent WSOL methods have not made a major improvement over the CAM baseline. Moreover, we report that existing WSOL methods have not reached the few-shot learning baseline, where the full-supervision at validation time is used for model training instead. Based on our findings, we discuss some future directions for WSOL.
Deep Multi-task Learning for Facial Expression Recognition and Synthesis Based on Selective Feature Sharing
Venue: arXiv cs.CV 2021
Year: 2021

Multi-task learning is an effective learning strategy for deep-learning-based facial expression recognition tasks. However, most existing methods take into limited consideration the feature selection, when transferring information between different tasks, which may lead to task interference when training the multi-task networks. To address this problem, we propose a novel selective feature-sharing method, and establish a multi-task network for facial expression recognition and facial expression synthesis. The proposed method can effectively transfer beneficial features between different tasks, while filtering out useless and harmful information. Moreover, we employ the facial expression synthesis task to enlarge and balance the training dataset to further enhance the generalization ability of the proposed method. Experimental results show that the proposed method achieves state-of-the-art performance on those commonly used facial expression recognition benchmarks, which makes it a potential solution to real-world facial expression recognition problems.
Point Set Voting for Partial Point Cloud Analysis
Venue: arXiv cs.CV 2021
Year: 2021

The continual improvement of 3D sensors has driven the development of algorithms to perform point cloud analysis. In fact, techniques for point cloud classification and segmentation have in recent years achieved incredible performance driven in part by leveraging large synthetic datasets. Unfortunately these same state-of-the-art approaches perform poorly when applied to incomplete point clouds. This limitation of existing algorithms is particularly concerning since point clouds generated by 3D sensors in the real world are usually incomplete due to perspective view or occlusion by other objects. This paper proposes a general model for partial point clouds analysis wherein the latent feature encoding a complete point clouds is inferred by applying a local point set voting strategy. In particular, each local point set constructs a vote that corresponds to a distribution in the latent space, and the optimal latent feature is the one with the highest probability. This approach ensures that any subsequent point cloud analysis is robust to partial observation while simultaneously guaranteeing that the proposed model is able to output multiple possible results. This paper illustrates that this proposed method achieves state-of-the-art performance on shape classification, part segmentation and point cloud completion.
IOCA: High-Speed I/O-Aware LLC Management for Network-Centric Multi-Tenant Platform
Venue: arXiv cs.AR 2021
Year: 2021

In modern server CPUs, last-level cache (LLC) is a critical hardware resource that exerts significant influence on the performance of the workloads, and how to manage LLC is a key to the performance isolation and QoS in the cloud with multi-tenancy. In this paper, we argue that besides CPU cores, high-speed network I/O is also important for LLC management. This is because of an Intel architectural innovation -- Data Direct I/O (DDIO) -- that directly injects the inbound I/O traffic to (part of) the LLC instead of the main memory. We summarize two problems caused by DDIO and show that (1) the default DDIO configuration may not always achieve optimal performance, (2) DDIO can decrease the performance of non-I/O workloads which share LLC with it by as high as 32%. We then present IOCA, the first LLC management mechanism for network-centric platforms that treats the I/O as the first-class citizen. IOCA monitors and analyzes the performance of the cores, LLC, and DDIO using CPU's hardware performance counters, and adaptively adjusts the number of LLC ways for DDIO or the tenants that demand more LLC capacity. In addition, IOCA dynamically chooses the tenants that share its LLC resource with DDIO, to minimize the performance interference by both the tenants and the I/O. Our experiments with multiple microbenchmarks and real-world applications in two major end-host network models demonstrate that IOCA can effectively reduce the performance degradation caused by DDIO, with minimal overhead.
A Study on Encodings for Neural Architecture Search
Venue: arXiv cs.LG 2021
Year: 2021

Neural architecture search (NAS) has been extensively studied in the past few years. A popular approach is to represent each neural architecture in the search space as a directed acyclic graph (DAG), and then search over all DAGs by encoding the adjacency matrix and list of operations as a set of hyperparameters. Recent work has demonstrated that even small changes to the way each architecture is encoded can have a significant effect on the performance of NAS algorithms. In this work, we present the first formal study on the effect of architecture encodings for NAS, including a theoretical grounding and an empirical study. First we formally define architecture encodings and give a theoretical characterization on the scalability of the encodings we study Then we identify the main encoding-dependent subroutines which NAS algorithms employ, running experiments to show which encodings work best with each subroutine for many popular algorithms. The experiments act as an ablation study for prior work, disentangling the algorithmic and encoding-based contributions, as well as a guideline for future work. Our results demonstrate that NAS encodings are an important design decision which can have a significant impact on overall performance. Our code is available at https://github.com/naszilla/nas-encodings.
Boundary thickness and robustness in learning models
Venue: arXiv cs.LG 2021
Year: 2021

Robustness of machine learning models to various adversarial and non-adversarial corruptions continues to be of interest. In this paper, we introduce the notion of the boundary thickness of a classifier, and we describe its connection with and usefulness for model robustness. Thick decision boundaries lead to improved performance, while thin decision boundaries lead to overfitting (e.g., measured by the robust generalization gap between training and testing) and lower robustness. We show that a thicker boundary helps improve robustness against adversarial examples (e.g., improving the robust test accuracy of adversarial training) as well as so-called out-of-distribution (OOD) transforms, and we show that many commonly-used regularization and data augmentation procedures can increase boundary thickness. On the theoretical side, we establish that maximizing boundary thickness during training is akin to the so-called mixup training. Using these observations, we show that noise-augmentation on mixup training further increases boundary thickness, thereby combating vulnerability to various forms of adversarial attacks and OOD transforms. We can also show that the performance improvement in several lines of recent work happens in conjunction with a thicker boundary.
Third-Order Asymptotics of Variable-Length Compression Allowing Errors
Venue: arXiv cs.IT 2021
Year: 2021

This study investigates the fundamental limits of variable-length compression in which prefix-free constraints are not imposed (i.e., one-to-one codes are studied) and non-vanishing error probabilities are permitted. Due in part to a crucial relation between the variable-length and fixed-length compression problems, our analysis requires a careful and refined analysis of the fundamental limits of fixed-length compression in the setting where the error probabilities are allowed to approach either zero or one polynomially in the blocklength. To obtain the refinements, we employ tools from moderate deviations and strong large deviations. Finally, we provide the third-order asymptotics for the problem of variable-length compression with non-vanishing error probabilities. We show that unlike several other information-theoretic problems in which the third-order asymptotics are known, for the problem of interest here, the third-order term depends on the permissible error probability.
Power Minimization for Age of Information Constrained Dynamic Control in Wireless Sensor Networks
Venue: arXiv cs.IT 2021
Year: 2021

We consider a system where multiple sensors communicate timely information about various random processes to a sink. The sensors share orthogonal sub-channels to transmit such information in the form of status update packets. A central controller can control the sampling actions of the sensors to trade-off between the transmit power consumption and information freshness which is quantified by the Age of Information (AoI). We jointly optimize the sampling action of each sensor, the transmit power allocation, and the sub-channel assignment to minimize the average total transmit power of all sensors subject to a maximum average AoI constraint for each sensor. To solve the problem, we develop a dynamic control algorithm using the Lyapunov drift-plus-penalty method and provide optimality analysis of the algorithm. According to the Lyapunov drift-plus-penalty method, to solve the main problem we need to solve an optimization problem in each time slot which is a mixed integer non-convex optimization problem. We propose a low-complexity sub-optimal solution for this per-slot optimization problem that provides near-optimal performance and we evaluate the computational complexity of the solution. Numerical results illustrate the performance of the proposed dynamic control algorithm and the performance of the sub-optimal solution for the per-slot optimization problems versus the different parameters of the system. The results show that the proposed dynamic control algorithm achieves more than $60~\%$ saving in the average total transmit power compared to a baseline policy.
Algorithmic Fairness in Education
Venue: arXiv cs.CY 2021
Year: 2021

Data-driven predictive models are increasingly used in education to support students, instructors, and administrators. However, there are concerns about the fairness of the predictions and uses of these algorithmic systems. In this introduction to algorithmic fairness in education, we draw parallels to prior literature on educational access, bias, and discrimination, and we examine core components of algorithmic systems (measurement, model learning, and action) to identify sources of bias and discrimination in the process of developing and deploying these systems. Statistical, similarity-based, and causal notions of fairness are reviewed and contrasted in the way they apply in educational contexts. Recommendations for policy makers and developers of educational technology offer guidance for how to promote algorithmic fairness in education.
India's rank and global share in scientific research -- how publication counting method and subject selection can vary the outcomes
Venue: arXiv cs.DL 2021
Year: 2021

During the last two decades, India has emerged as a major knowledge producer in the world, however different reports put it at different ranks, varying from 3rd to 9th places. The recent commissioned study reports of Department of Science and Technology (DST) done by Elsevier and Clarivate Analytics, rank India at 5thand 9th places, respectively. On the other hand, an independent report by National Science Foundation (NSF) of United States (US), ranks India at 3rd place on research output in Science and Engineering area. Interestingly, both, the Elsevier and the NSF reports use Scopus data, and yet surprisingly their outcomes are different. This article, therefore, attempts to investigate as to how the use of same database can still produce different outcomes, due to differences in methodological approaches. The publication counting method used and the subject selection approach are the two main exogenous factors identified to cause these variations. The implications of the analytical outcomes are discussed with special focus on policy perspectives.
Cues to gender and racial identity reduce creativity in diverse social networks
Venue: arXiv cs.SI 2021
Year: 2021

The characteristics of social partners have long been hypothesized as influential in guiding group interactions. Understanding how demographic cues impact networks of creative collaborators is critical for elevating creative performances therein. We conducted a randomized experiment to investigate how the knowledge of peers' gender and racial identities distorts people's connection patterns and the resulting creative outcomes in a dynamic social network. Consistent with prior work, we found that creative inspiration links are primarily formed with top idea-generators. However, when gender and racial identities are known, not only is there (1) an increase of 82.03% in the odds of same-gender connections (but not for same-race connections), but (2) the semantic similarity of idea-sets stimulated by these connections also increase significantly compared to demography-agnostic networks, negatively impacting the outcomes of divergent creativity. We found that ideas tend to be more homogeneous within demographic groups than between, taking away diversity-bonuses from similarity-based links and partly explaining the results. These insights can inform intelligent interventions to enhance network-wide creative performances.
The Impossibility Theorem of Machine Fairness -- A Causal Perspective
Venue: arXiv cs.LG 2021
Year: 2021

With the increasing pervasive use of machine learning in social and economic settings, there has been an interest in the notion of machine bias in the AI community. Models trained on historic data reflect biases that exist in society and propagated them to the future through their decisions. There are three prominent metrics of machine fairness used in the community, and it has been shown statistically that it is impossible to satisfy them all at the same time. This has led to an ambiguity with regards to the definition of fairness. In this report, a causal perspective to the impossibility theorem of fairness is presented along with a causal goal for machine fairness.
Projected Latent Markov Chain Monte Carlo: Conditional Sampling of Normalizing Flows
Venue: arXiv cs.LG 2021
Year: 2021

We introduce Projected Latent Markov Chain Monte Carlo (PL-MCMC), a technique for sampling from the high-dimensional conditional distributions learned by a normalizing flow. We prove that a Metropolis-Hastings implementation of PL-MCMC asymptotically samples from the exact conditional distributions associated with a normalizing flow. As a conditional sampling method, PL-MCMC enables Monte Carlo Expectation Maximization (MC-EM) training of normalizing flows from incomplete data. Through experimental tests applying normalizing flows to missing data tasks for a variety of data sets, we demonstrate the efficacy of PL-MCMC for conditional sampling from normalizing flows.
Distributed Training of Graph Convolutional Networks
Venue: arXiv cs.LG 2021
Year: 2021

The aim of this work is to develop a fully-distributed algorithmic framework for training graph convolutional networks (GCNs). The proposed method is able to exploit the meaningful relational structure of the input data, which are collected by a set of agents that communicate over a sparse network topology. After formulating the centralized GCN training problem, we first show how to make inference in a distributed scenario where the underlying data graph is split among different agents. Then, we propose a distributed gradient descent procedure to solve the GCN training problem. The resulting model distributes computation along three lines: during inference, during back-propagation, and during optimization. Convergence to stationary solutions of the GCN training problem is also established under mild conditions. Finally, we propose an optimization criterion to design the communication topology between agents in order to match with the graph describing data relationships. A wide set of numerical results validate our proposal. To the best of our knowledge, this is the first work combining graph convolutional neural networks with distributed optimization.
In-place implementation of Quantum-Gimli
Venue: arXiv cs.CR 2021
Year: 2021

We present an in-place implementation of the cryptographic permutation \textbf{Gimli}, a NIST round 2 candidate for lightweight cryptography, and provide an upper bound for the required quantum resource in depth and gate-counts. In particular, we do not use any ancilla qubits and the state that our circuit produces is not entangled with any input. This offers further freedom in the usability and allows for a widespread use in different applications in a plug-and-play manner.
Unsupervised object-centric video generation and decomposition in 3D
Venue: arXiv cs.CV 2021
Year: 2021

A natural approach to generative modeling of videos is to represent them as a composition of moving objects. Recent works model a set of 2D sprites over a slowly-varying background, but without considering the underlying 3D scene that gives rise to them. We instead propose to model a video as the view seen while moving through a scene with multiple 3D objects and a 3D background. Our model is trained from monocular videos without any supervision, yet learns to generate coherent 3D scenes containing several moving objects. We conduct detailed experiments on two datasets, going beyond the visual complexity supported by state-of-the-art generative approaches. We evaluate our method on depth-prediction and 3D object detection -- tasks which cannot be addressed by those earlier works -- and show it out-performs them even on 2D instance segmentation and tracking.
Analyzing and Mitigating Data Stalls in DNN Training
Venue: arXiv cs.DC 2021
Year: 2021

Training Deep Neural Networks (DNNs) is resource-intensive and time-consuming. While prior research has explored many different ways of reducing DNN training time, the impact of input data pipeline, i.e., fetching raw data items from storage and performing data pre-processing in memory, has been relatively unexplored. This paper makes the following contributions: (1) We present the first comprehensive analysis of how the input data pipeline affects the training time of widely-used computer vision and audio Deep Neural Networks (DNNs), that typically involve complex data preprocessing. We analyze nine different models across three tasks and four datasets while varying factors such as the amount of memory, number of CPU threads, storage device, GPU generation etc on servers that are a part of a large production cluster at Microsoft. We find that in many cases, DNN training time is dominated by data stall time: time spent waiting for data to be fetched and preprocessed. (2) We build a tool, DS-Analyzer to precisely measure data stalls using a differential technique, and perform predictive what-if analysis on data stalls. (3) Finally, based on the insights from our analysis, we design and implement three simple but effective techniques in a data-loading library, CoorDL, to mitigate data stalls. Our experiments on a range of DNN tasks, models, datasets, and hardware configs show that when PyTorch uses CoorDL instead of the state-of-the-art DALI data loading library, DNN training time is reduced significantly (by as much as 5x on a single server).