OpenRaiser/Intern-Atlas huggingface dataset:
Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice
Venue: arXiv cs.DS 2021
Year: 2021

Optimization problems with set submodular objective functions have many real-world applications. In discrete scenarios, where the same item can be selected more than once, the domain is generalized from a 2-element set to a bounded integer lattice. In this work, we consider the problem of maximizing a monotone submodular function on the bounded integer lattice subject to a cardinality constraint. In particular, we focus on maximizing DR-submodular functions, i.e., functions defined on the integer lattice that exhibit the diminishing returns property. Given any epsilon > 0, we present a randomized algorithm with probabilistic guarantees of O(1 - 1/e - epsilon) approximation, using a framework inspired by a Stochastic Greedy algorithm developed for set submodular functions by Mirzasoleiman et al. We then show that, on synthetic DR-submodular functions, applying our proposed algorithm on the integer lattice is faster than the alternatives, including reducing a target problem to the set domain and then applying the fastest known set submodular maximization algorithm.
Subspace Graph Physics: Real-Time Rigid Body-Driven Granular Flow Simulation
Venue: arXiv cs.LG 2021
Year: 2021

An important challenge in robotics is understanding the interactions between robots and deformable terrains that consist of granular material. Granular flows and their interactions with rigid bodies still pose several open questions. A promising direction for accurate, yet efficient, modeling is using continuum methods. Also, a new direction for real-time physics modeling is the use of deep learning. This research advances machine learning methods for modeling rigid body-driven granular flows, for application to terrestrial industrial machines as well as space robotics (where the effect of gravity is an important factor). In particular, this research considers the development of a subspace machine learning simulation approach. To generate training datasets, we utilize our high-fidelity continuum method, material point method (MPM). Principal component analysis (PCA) is used to reduce the dimensionality of data. We show that the first few principal components of our high-dimensional data keep almost the entire variance in data. A graph network simulator (GNS) is trained to learn the underlying subspace dynamics. The learned GNS is then able to predict particle positions and interaction forces with good accuracy. More importantly, PCA significantly enhances the time and memory efficiency of GNS in both training and rollout. This enables GNS to be trained using a single desktop GPU with moderate VRAM. This also makes the GNS real-time on large-scale 3D physics configurations (700x faster than our continuum method).
Hex Me If You Can
Venue: arXiv cs.CG 2021
Year: 2021

HEXME consists of tetrahedral meshes with tagged features, and of a workflow to generate them. The main purpose of HEXME meshes is to enable consistent and fair evaluation of hexahedral meshing algorithms and related techniques. The tetrahedral meshes have been generated with Gmsh, starting from 63 computer-aided design (CAD) models coming from various databases. To highlight and label the various and challenging aspects of hexahedral mesh generation, the CAD models are classified into three categories: simple, nasty and industrial. For each CAD model, we provide three kinds of tetrahedral meshes. The mesh generation yielding those 189 tetrahedral meshes is defined thanks to Snakemake, a modern workflow management system, which allows us to define a fully automated, extensible and sustainable workflow. It is possible to download the whole dataset or to pick some meshes by browsing the online catalog. Since there is no doubt that the hexahedral meshing techniques are going to progress, the HEXME dataset is also built with evolution in mind. A public GitHub repository hosts the HEXME workflow, in which external contributions and future releases are possible and encouraged.
Probabilistic Regression with Huber Distributions
Venue: arXiv cs.CV 2021
Year: 2021

In this paper we describe a probabilistic method for estimating the position of an object along with its covariance matrix using neural networks. Our method is designed to be robust to outliers, have bounded gradients with respect to the network outputs, among other desirable properties. To achieve this we introduce a novel probability distribution inspired by the Huber loss. We also introduce a new way to parameterize positive definite matrices to ensure invariance to the choice of orientation for the coordinate system we regress over. We evaluate our method on popular body pose and facial landmark datasets and get performance on par or exceeding the performance of non-heatmap methods. Our code is available at github.com/Davmo049/Public_prob_regression_with_huber_distributions
Toward Compact Parameter Representations for Architecture-Agnostic Neural Network Compression
Venue: arXiv cs.CV 2021
Year: 2021

This paper investigates deep neural network (DNN) compression from the perspective of compactly representing and storing trained parameters. We explore the previously overlooked opportunity of cross-layer architecture-agnostic representation sharing for DNN parameters. To do this, we decouple feedforward parameters from DNN architectures and leverage additive quantization, an extreme lossy compression method invented for image descriptors, to compactly represent the parameters. The representations are then finetuned on task objectives to improve task accuracy. We conduct extensive experiments on MobileNet-v2, VGG-11, ResNet-50, Feature Pyramid Networks, and pruned DNNs trained for classification, detection, and segmentation tasks. The conceptually simple scheme consistently outperforms iterative unstructured pruning. Applied to ResNet-50 with 76.1% top-1 accuracy on the ILSVRC12 classification challenge, it achieves a $7.2\times$ compression ratio with no accuracy loss and a $15.3\times$ compression ratio at 74.79% accuracy. Further analyses suggest that representation sharing can frequently happen across network layers and that learning shared representations for an entire DNN can achieve better accuracy at the same compression ratio than compressing the model as multiple separate parts. We release PyTorch code to facilitate DNN deployment on resource-constrained devices and spur future research on efficient representations and storage of DNN parameters.
Influence Dynamics Among Narratives: A Case Study of the Venezuelan Presidential Crisis
Venue: arXiv cs.SI 2021
Year: 2021

It is widely understood that diffusion of and simultaneous interactions between narratives -- defined here as persistent point-of-view messaging -- significantly contributes to the shaping of political discourse and public opinion. In this work, we propose a methodology based on Multi-Variate Hawkes Processes and our newly-introduced Process Influence Measures for quantifying and assessing how such narratives influence (Granger-cause) each other. Such an approach may aid social scientists enhance their understanding of socio-geopolitical phenomena as they manifest themselves and evolve in the realm of social media. In order to show its merits, we apply our methodology on Twitter narratives during the 2019 Venezuelan presidential crisis. Our analysis indicates a nuanced, evolving influence structure between 8 distinct narratives, part of which could be explained by landmark historical events.
A Transient Semantics for Typed Racket
Venue: arXiv cs.PL 2021
Year: 2021

Mixed-typed languages enable programmers to link typed and untyped components in various ways. Some offer rich type systems to facilitate the smooth migration of untyped code to the typed world; others merely provide a convenient form of type Dynamic together with a conventional structural type system. Orthogonal to this dimension, Natural systems ensure the integrity of types with a sophisticated contract system, while Transient systems insert simple first-order checks at strategic places within typed code. Furthermore, each method of ensuring type integrity comes with its own blame-assignment strategy. Typed Racket has a rich migratory type system and enforces the types with a Natural semantics. Reticulated Python has a simple structural type system extended with Dynamic and enforces types with a Transient semantics. While Typed Racket satisfies the most stringent gradual-type soundness properties at a significant performance cost, Reticulated Python seems to limit the performance penalty to a tolerable degree and is nevertheless type sound. This comparison raises the question of whether Transient checking is applicable to and beneficial for a rich migratory type system. This paper reports on the surprising difficulties of adapting the Transient semantics of Reticulated Python to the rich migratory type system of Typed Racket. The resulting implementation, Shallow Typed Racket, is faster than the standard Deep Typed Racket but only when the Transient blame assignment strategy is disabled. For language designers, this report provides valuable hints on how to equip an existing compiler to support a Transient semantics. For theoreticians, the negative experience with Transient blame calls for a thorough investigation of this strategy.
Sliding Network Coding for URLLC
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we propose a network coding (NC) based approach to ultra-reliable low-latency communication (URLLC) over erasure channels. In transmitting multiple data packets, we demonstrate that the use of random NC can improve the reliability in terms of decoding error probability, while it incurs a longer decoding delay than a well-known K-repetition. To avoid a long decoding delay, we consider a sliding NC (SNC) design that allows a highly reliable transmission of each data packet with a guaranteed decoding delay. A few design examples are derived and their decoding error rates are analyzed. Through the analysis, we can show that the decoding error rate of SNC is much lower than that of K-repetition at the same spectral efficiency, which means a more reliable transmission can be achieved using SNC than K-repetition.
Exploring Language Patterns in a Medical Licensure Exam Item Bank
Venue: arXiv cs.CL 2021
Year: 2021

This study examines the use of natural language processing (NLP) models to evaluate whether language patterns used by item writers in a medical licensure exam might contain evidence of biased or stereotypical language. This type of bias in item language choices can be particularly impactful for items in a medical licensure assessment, as it could pose a threat to content validity and defensibility of test score validity evidence. To the best of our knowledge, this is the first attempt using machine learning (ML) and NLP to explore language bias on a large item bank. Using a prediction algorithm trained on clusters of similar item stems, we demonstrate that our approach can be used to review large item banks for potential biased language or stereotypical patient characteristics in clinical science vignettes. The findings may guide the development of methods to address stereotypical language patterns found in test items and enable an efficient updating of those items, if needed, to reflect contemporary norms, thereby improving the evidence to support the validity of the test scores.
Broadband Digital Over-the-Air Computation for Asynchronous Federated Edge Learning
Venue: arXiv cs.IT 2021
Year: 2021

This paper presents the first broadband digital over-the-air computation (AirComp) system for phase asynchronous OFDM-based federated edge learning systems. Existing analog AirComp systems often assume perfect phase alignment via channel precoding and utilize uncoded analog modulation for model aggregation. In contrast, our digital AirComp system leverages digital modulation and channel codes to overcome phase asynchrony, thereby achieving accurate model aggregation in the asynchronous multi-user OFDM systems. To realize a digital AirComp system, we propose a non-orthogonal multiple access protocol that allows simultaneous transmissions from multiple edge devices, and present a joint channel decoding and aggregation (Jt-CDA) decoder (i.e., full-state joint decoder). To reduce the computation complexity, we further present a reduced-complexity Jt-CDA decoder (i.e., reduced-state joint decoder), and its arithmetic sum bit error rate performance is similar to that of the full-state joint decoder for most signal-to-noise ratio (SNR) regimes. Simulation results on test accuracy (of CIFAR10 dataset) versus SNR show that: 1) analog AirComp systems are sensitive to phase asynchrony under practical setup, and the test accuracy performance exhibits an error floor even at high SNR regime; 2) our digital AirComp system outperforms an analog AirComp system by at least 1.5 times when SNR 9dB, demonstrating the advantage of digital AirComp in asynchronous multi-user OFDM systems.
Edge-Enhanced Global Disentangled Graph Neural Network for Sequential Recommendation
Venue: arXiv cs.IR 2021
Year: 2021

Sequential recommendation has been a widely popular topic of recommender systems. Existing works have contributed to enhancing the prediction ability of sequential recommendation systems based on various methods, such as recurrent networks and self-attention mechanisms. However, they fail to discover and distinguish various relationships between items, which could be underlying factors which motivate user behaviors. In this paper, we propose an Edge-Enhanced Global Disentangled Graph Neural Network (EGD-GNN) model to capture the relation information between items for global item representation and local user intention learning. At the global level, we build a global-link graph over all sequences to model item relationships. Then a channel-aware disentangled learning layer is designed to decompose edge information into different channels, which can be aggregated to represent the target item from its neighbors. At the local level, we apply a variational auto-encoder framework to learn user intention over the current sequence. We evaluate our proposed method on three real-world datasets. Experimental results show that our model can get a crucial improvement over state-of-the-art baselines and is able to distinguish item features.
Teacher-Student Training and Triplet Loss to Reduce the Effect of Drastic Face Occlusion
Venue: arXiv cs.CV 2021
Year: 2021

We study a series of recognition tasks in two realistic scenarios requiring the analysis of faces under strong occlusion. On the one hand, we aim to recognize facial expressions of people wearing Virtual Reality (VR) headsets. On the other hand, we aim to estimate the age and identify the gender of people wearing surgical masks. For all these tasks, the common ground is that half of the face is occluded. In this challenging setting, we show that convolutional neural networks (CNNs) trained on fully-visible faces exhibit very low performance levels. While fine-tuning the deep learning models on occluded faces is extremely useful, we show that additional performance gains can be obtained by distilling knowledge from models trained on fully-visible faces. To this end, we study two knowledge distillation methods, one based on teacher-student training and one based on triplet loss. Our main contribution consists in a novel approach for knowledge distillation based on triplet loss, which generalizes across models and tasks. Furthermore, we consider combining distilled models learned through conventional teacher-student training or through our novel teacher-student training based on triplet loss. We provide empirical evidence showing that, in most cases, both individual and combined knowledge distillation methods bring statistically significant performance improvements. We conduct experiments with three different neural models (VGG-f, VGG-face, ResNet-50) on various tasks (facial expression recognition, gender recognition, age estimation), showing consistent improvements regardless of the model or task.
Improving Spectral Efficiency of Wireless Networks through Democratic Spectrum Sharing
Venue: arXiv cs.NI 2021
Year: 2021

Wireless devices need spectrum to communicate. With the increase in the number of devices competing for the same spectrum, it has become nearly impossible to support the throughput requirements of all the devices through current spectrum sharing methods. In this work, we look at the problem of spectrum resource contention fundamentally, taking inspiration from the principles of globalization. We develop a distributed algorithm whereby the wireless nodes democratically share the spectrum resources and improve their spectral efficiency and throughput without additional power or spectrum resources. We validate the performance of our proposed democratic spectrum sharing (DSS) algorithm over real-world Wi-Fi networks and on synthetically generated networks with varying design parameters. Compared to the greedy approach, DSS achieves significant gains in throughput (~60%), area spectral efficiency ($\sim$50\%) and fairness in datarate distribution (~20%). Due to the distributed nature of the proposed algorithm, we can apply it to wireless networks of any size and density.
SPINE: Soft Piecewise Interpretable Neural Equations
Venue: arXiv cs.LG 2021
Year: 2021

Relu Fully Connected Networks are ubiquitous but uninterpretable because they fit piecewise linear functions emerging from multi-layered structures and complex interactions of model weights. This paper takes a novel approach to piecewise fits by using set operations on individual pieces(parts). This is done by approximating canonical normal forms and using the resultant as a model. This gives special advantages like (a)strong correspondence of parameters to pieces of the fit function(High Interpretability); (b)ability to fit any combination of continuous functions as pieces of the piecewise function(Ease of Design); (c)ability to add new non-linearities in a targeted region of the domain(Targeted Learning); (d)simplicity of an equation which avoids layering. It can also be expressed in the general max-min representation of piecewise linear functions which gives theoretical ease and credibility. This architecture is tested on simulated regression and classification tasks and benchmark datasets including UCI datasets, MNIST, FMNIST, and CIFAR 10. This performance is on par with fully connected architectures. It can find a variety of applications where fully connected layers must be replaced by interpretable layers.
Calculus of Consent via MARL: Legitimating the Collaborative Governance Supplying Public Goods
Venue: arXiv cs.AI 2021
Year: 2021

Public policies that supply public goods, especially those involve collaboration by limiting individual liberty, always give rise to controversies over governance legitimacy. Multi-Agent Reinforcement Learning (MARL) methods are appropriate for supporting the legitimacy of the public policies that supply public goods at the cost of individual interests. Among these policies, the inter-regional collaborative pandemic control is a prominent example, which has become much more important for an increasingly inter-connected world facing a global pandemic like COVID-19. Different patterns of collaborative strategies have been observed among different systems of regions, yet it lacks an analytical process to reason for the legitimacy of those strategies. In this paper, we use the inter-regional collaboration for pandemic control as an example to demonstrate the necessity of MARL in reasoning, and thereby legitimizing policies enforcing such inter-regional collaboration. Experimental results in an exemplary environment show that our MARL approach is able to demonstrate the effectiveness and necessity of restrictions on individual liberty for collaborative supply of public goods. Different optimal policies are learned by our MARL agents under different collaboration levels, which change in an interpretable pattern of collaboration that helps to balance the losses suffered by regions of different types, and consequently promotes the overall welfare. Meanwhile, policies learned with higher collaboration levels yield higher global rewards, which illustrates the benefit of, and thus provides a novel justification for the legitimacy of, promoting inter-regional collaboration. Therefore, our method shows the capability of MARL in computationally modeling and supporting the theory of calculus of consent, developed by Nobel Prize winner J. M. Buchanan.
Q-Learning Based Energy-Efficient Network Planning in IP-over-EON
Venue: arXiv cs.NI 2021
Year: 2021

During network planning phase, optimal network planning implemented through efficient resource allocation and static traffic demand provisioning in IP-over-elastic optical network (IP-over-EON) is significantly challenging compared with the fixed-grid wavelength division multiplexing (WDM) network due to increased flexibility in IP-over-EON. Mathematical optimization models used for this purpose may not provide solution for large networks due to large computational complexity. In this regard, a greedy heuristic may be used that intuitively selects traffic elements in sequence from static traffic demand matrix and attempts to find the best solution. However, in general, such greedy heuristics offer suboptimal solutions, since appropriate traffic sequence offering the optimal performance is rarely selected. In this regard, we propose a reinforcement learning technique (in particular a Q-learning method), combined with an auxiliary graph (AG)-based energy efficient greedy method to be used for large network planning. The Q-learning method is used to decide the suitable sequence of traffic allocation such that the overall power consumption in the network reduces. In the proposed heuristic, each traffic from the given static traffic demand matrix is successively selected using the Q-learning technique and provisioned using the AG-based greedy method.
Doing More by Doing Less: How Structured Partial Backpropagation Improves Deep Learning Clusters
Venue: arXiv cs.DC 2021
Year: 2021

Many organizations employ compute clusters equipped with accelerators such as GPUs and TPUs for training deep learning models in a distributed fashion. Training is resource-intensive, consuming significant compute, memory, and network resources. Many prior works explore how to reduce training resource footprint without impacting quality, but their focus on a subset of the bottlenecks (typically only the network) limits their ability to improve overall cluster utilization. In this work, we exploit the unique characteristics of deep learning workloads to propose Structured Partial Backpropagation(SPB), a technique that systematically controls the amount of backpropagation at individual workers in distributed training. This simultaneously reduces network bandwidth, compute utilization, and memory footprint while preserving model quality. To efficiently leverage the benefits of SPB at cluster level, we introduce JigSaw, a SPB aware scheduler, which does scheduling at the iteration level for Deep Learning Training(DLT) jobs. We find that JigSaw can improve large scale cluster efficiency by as high as 28\%.