OpenRaiser/Intern-Atlas huggingface dataset:
Reinforced Data Sampling for Model Diversification
Venue: arXiv cs.LG 2020
Year: 2020

With the rising number of machine learning competitions, the world has witnessed an exciting race for the best algorithms. However, the involved data selection process may fundamentally suffer from evidence ambiguity and concept drift issues, thereby possibly leading to deleterious effects on the performance of various models. This paper proposes a new Reinforced Data Sampling (RDS) method to learn how to sample data adequately on the search for useful models and insights. We formulate the optimisation problem of model diversification $δ{-div}$ in data sampling to maximise learning potentials and optimum allocation by injecting model diversity. This work advocates the employment of diverse base learners as value functions such as neural networks, decision trees, or logistic regressions to reinforce the selection process of data subsets with multi-modal belief. We introduce different ensemble reward mechanisms, including soft voting and stochastic choice to approximate optimal sampling policy. The evaluation conducted on four datasets evidently highlights the benefits of using RDS method over traditional sampling approaches. Our experimental results suggest that the trainable sampling for model diversification is useful for competition organisers, researchers, or even starters to pursue full potentials of various machine learning tasks such as classification and regression. The source code is available at https://github.com/probeu/RDS.
Asymptotic Singular Value Distribution of Linear Convolutional Layers
Venue: arXiv cs.LG 2020
Year: 2020

In convolutional neural networks, the linear transformation of multi-channel two-dimensional convolutional layers with linear convolution is a block matrix with doubly Toeplitz blocks. Although a "wrapping around" operation can transform linear convolution to a circular one, by which the singular values can be approximated with reduced computational complexity by those of a block matrix with doubly circulant blocks, the accuracy of such an approximation is not guaranteed. In this paper, we propose to inspect such a linear transformation matrix through its asymptotic spectral representation - the spectral density matrix - by which we develop a simple singular value approximation method with improved accuracy over the circular approximation, as well as upper bounds for spectral norm with reduced computational complexity. Compared with the circular approximation, we obtain moderate improvement with a subtle adjustment of the singular value distribution. We also demonstrate that the spectral norm upper bounds are effective spectral regularizers for improving generalization performance in ResNets.
Learning Diverse Representations for Fast Adaptation to Distribution Shift
Venue: arXiv cs.LG 2020
Year: 2020

The i.i.d. assumption is a useful idealization that underpins many successful approaches to supervised machine learning. However, its violation can lead to models that learn to exploit spurious correlations in the training data, rendering them vulnerable to adversarial interventions, undermining their reliability, and limiting their practical application. To mitigate this problem, we present a method for learning multiple models, incorporating an objective that pressures each to learn a distinct way to solve the task. We propose a notion of diversity based on minimizing the conditional total correlation of final layer representations across models given the label, which we approximate using a variational estimator and minimize using adversarial training. To demonstrate our framework's ability to facilitate rapid adaptation to distribution shift, we train a number of simple classifiers from scratch on the frozen outputs of our models using a small amount of data from the shifted distribution. Under this evaluation protocol, our framework significantly outperforms a baseline trained using the empirical risk minimization principle.
Generalized SHAP: Generating multiple types of explanations in machine learning
Venue: arXiv cs.LG 2020
Year: 2020

Many important questions about a model cannot be answered just by explaining how much each feature contributes to its output. To answer a broader set of questions, we generalize a popular, mathematically well-grounded explanation technique, Shapley Additive Explanations (SHAP). Our new method - Generalized Shapley Additive Explanations (G-SHAP) - produces many additional types of explanations, including: 1) General classification explanations; Why is this sample more likely to belong to one class rather than another? 2) Intergroup differences; Why do our model's predictions differ between groups of observations? 3) Model failure; Why does our model perform poorly on a given sample? We formally define these types of explanations and illustrate their practical use on real data.
Nefele: Process Orchestration for the Cloud
Venue: arXiv cs.DC 2020
Year: 2020

Virtualization, either at OS- or hardware level, plays an important role in cloud computing. It enables easier automation and faster deployment in distributed environments. While virtualized infrastructures provide a level of management flexibility, they lack practical abstraction of the distributed resources. A developer in such an environment still needs to deal with all the complications of building a distributed software system. Different orchestration systems are built to provide that abstraction; however, they do not solve the inherent challenges of distributed systems, such as synchronization issues or resilience to failures. This paper introduces Nefele, a decentralized process orchestration system that automatically deploys and manages individual processes, rather than containers/VMs, within a cluster. Nefele is inspired by the Single System Image (SSI) vision of mitigating the intricacies of remote execution, yet it maintains the flexibility and performance of virtualized infrastructures. Nefele offers a set of APIs for building cloud-native applications that lets the developer easily build, deploy, and scale applications in a cloud environment. We have implemented and deployed Nefele on a cluster in our datacenter and evaluated its performance. Our evaluations show that Nefele can effectively deploy, scale, and monitor processes across a distributed environment, while it incorporates essential primitives to build a distributed software system.
Meta-Reinforcement Learning Robust to Distributional Shift via Model Identification and Experience Relabeling
Venue: arXiv cs.LG 2020
Year: 2020

Reinforcement learning algorithms can acquire policies for complex tasks autonomously. However, the number of samples required to learn a diverse set of skills can be prohibitively large. While meta-reinforcement learning methods have enabled agents to leverage prior experience to adapt quickly to new tasks, their performance depends crucially on how close the new task is to the previously experienced tasks. Current approaches are either not able to extrapolate well, or can do so at the expense of requiring extremely large amounts of data for on-policy meta-training. In this work, we present model identification and experience relabeling (MIER), a meta-reinforcement learning algorithm that is both efficient and extrapolates well when faced with out-of-distribution tasks at test time. Our method is based on a simple insight: we recognize that dynamics models can be adapted efficiently and consistently with off-policy data, more easily than policies and value functions. These dynamics models can then be used to continue training policies and value functions for out-of-distribution tasks without using meta-reinforcement learning at all, by generating synthetic experience for the new task.
A Practical Sparse Approximation for Real Time Recurrent Learning
Venue: arXiv cs.LG 2020
Year: 2020

Current methods for training recurrent neural networks are based on backpropagation through time, which requires storing a complete history of network states, and prohibits updating the weights `online' (after every timestep). Real Time Recurrent Learning (RTRL) eliminates the need for history storage and allows for online weight updates, but does so at the expense of computational costs that are quartic in the state size. This renders RTRL training intractable for all but the smallest networks, even ones that are made highly sparse. We introduce the Sparse n-step Approximation (SnAp) to the RTRL influence matrix, which only keeps entries that are nonzero within n steps of the recurrent core. SnAp with n=1 is no more expensive than backpropagation, and we find that it substantially outperforms other RTRL approximations with comparable costs such as Unbiased Online Recurrent Optimization. For highly sparse networks, SnAp with n=2 remains tractable and can outperform backpropagation through time in terms of learning speed when updates are done online. SnAp becomes equivalent to RTRL when n is large.
Low-resource Languages: A Review of Past Work and Future Challenges
Venue: arXiv cs.CL 2020
Year: 2020

A current problem in NLP is massaging and processing low-resource languages which lack useful training attributes such as supervised data, number of native speakers or experts, etc. This review paper concisely summarizes previous groundbreaking achievements made towards resolving this problem, and analyzes potential improvements in the context of the overall future research direction.
SMS in PACE 2020
Venue: arXiv cs.DS 2020
Year: 2020

We describe SMS, our submission to the exact treedepth track of PACE 2020. SMS computes the treedepth of a graph by branching on the small minimal separators of the graph.
Application of Mean Curvature Flow for Surface Parametrizations
Venue: arXiv cs.CG 2020
Year: 2020

This is an expository article describing the conformalized mean curvature flow, originally introduced by Kazhdan, Solomon, and Ben-Chen. We are interested in applying mean curvature flow to surface parametrizations. We discuss our own implementation of their algorithm and some limitations.
How to Avoid Being Eaten by a Grue: Structured Exploration Strategies for Textual Worlds
Venue: arXiv cs.AI 2020
Year: 2020

Text-based games are long puzzles or quests, characterized by a sequence of sparse and potentially deceptive rewards. They provide an ideal platform to develop agents that perceive and act upon the world using a combinatorially sized natural language state-action space. Standard Reinforcement Learning agents are poorly equipped to effectively explore such spaces and often struggle to overcome bottlenecks---states that agents are unable to pass through simply because they do not see the right action sequence enough times to be sufficiently reinforced. We introduce Q*BERT, an agent that learns to build a knowledge graph of the world by answering questions, which leads to greater sample efficiency. To overcome bottlenecks, we further introduce MC!Q*BERT an agent that uses an knowledge-graph-based intrinsic motivation to detect bottlenecks and a novel exploration strategy to efficiently learn a chain of policy modules to overcome them. We present an ablation study and results demonstrating how our method outperforms the current state-of-the-art on nine text games, including the popular game, Zork, where, for the first time, a learning agent gets past the bottleneck where the player is eaten by a Grue.
F4Tele: FSO for Data Center Network Management and Packet Telemetry
Venue: arXiv cs.NI 2020
Year: 2020

The proliferation of bandwidth-hungry applications and services forces datacenter (DC) administrators to optimize the utilization of available resources. Precisely, the network share of management traffic has grown significantly because DC networks are becoming more sophisticated and require a massive amount of data for efficient debugging and troubleshooting. Accordingly, we use free space optics communication (FSO) with wavelength division multiplexing (WDM) technology to build a flexible yet high-performance logical network responsible for management traffic. The FSO-WDM can provide reconfigurable multi-terabit topology over line-of-sight (LoS) links. Due to space and processing capacity reasons, we can not offer direct connections from every data rack to the network management racks. Alternatively, the data racks are grouped together as each group is serviced for a duration of time matches its average arrival-rate. Since the data racks showed different arrival-rates, the hotspot racks are allocated with longer service time. The evaluation results show that F4Tele carried out high throughput close to the expensive solution (benchmark).
Returning the Favor: What Wireless Networking Can Offer to AI and Edge Learning
Venue: arXiv cs.DC 2020
Year: 2020

Machine learning (ML) and artificial intelligence (AI) have recently made a significant impact on improving the operations of wireless networks and establishing intelligence at the edge. In return, rare efforts were made to explore how adapting, optimizing, and arranging wireless networks can contribute to implementing ML/AI at the edge. This article aims to address this void by setting a vision on how wireless networking researchers can leverage their expertise to return the favor to edge learning. It will review the enabling technologies, summarize the inaugural works on this path, and shed light on different directions to establish a comprehensive framework for mobile edge learning (MEL).
Understanding Unintended Memorization in Federated Learning
Venue: arXiv cs.LG 2020
Year: 2020

Recent works have shown that generative sequence models (e.g., language models) have a tendency to memorize rare or unique sequences in the training data. Since useful models are often trained on sensitive data, to ensure the privacy of the training data it is critical to identify and mitigate such unintended memorization. Federated Learning (FL) has emerged as a novel framework for large-scale distributed learning tasks. However, it differs in many aspects from the well-studied central learning setting where all the data is stored at the central server. In this paper, we initiate a formal study to understand the effect of different components of canonical FL on unintended memorization in trained models, comparing with the central learning setting. Our results show that several differing components of FL play an important role in reducing unintended memorization. Specifically, we observe that the clustering of data according to users---which happens by design in FL---has a significant effect in reducing such memorization, and using the method of Federated Averaging for training causes a further reduction. We also show that training with a strong user-level differential privacy guarantee results in models that exhibit the least amount of unintended memorization.
PLVER: Joint Stable Allocation and Content Replication for Edge-assisted Live Video Delivery
Venue: arXiv cs.NI 2020
Year: 2020

The live streaming services have gained extreme popularity in recent years. Due to the spiky traffic patterns of live videos, utilizing the distributed edge servers to improve viewers' quality of experience (QoE) has become a common practice nowadays. Nevertheless, current client-driven content caching mechanism does not support caching beforehand from the cloud to the edge, resulting in considerable cache missing in live video delivery. State-of-the-art research generally sacrifices the liveness of delivered videos in order to deal with the above problem. In this paper, by jointly considering the features of live videos and edge servers, we propose PLVER, a proactive live video push scheme to resolve the cache miss problem in live video delivery. Specifically, PLVER first conducts a one-tomultiple stable allocation between edge clusters and user groups, to balance the load of live traffic over the edge servers. Then it adopts proactive video replication algorithms to speed up the video replication among the edge servers. We conduct extensive trace-driven evaluations, covering 0.3 million Twitch viewers and more than 300 Twitch channels. The results demonstrate that with PLVER, edge servers can carry 28% and 82% more traffic than the auction-based replication method and the caching on requested time method, respectively.
A Blockchain-based Decentralized Data Sharing Infrastructure for Off-grid Networking
Venue: arXiv cs.DC 2020
Year: 2020

Off-grid networks are recently emerging as a solution to connect the unconnected or provide alternative services to networks of possibly untrusted participants. The systems currently used, however, exhibit limitations due to their centralized nature and thus prove inadequate to secure trust. Blockchain technology can be the tool that will enable trust and transparency in such networks. In this paper, we introduce a platform for secure and privacy-respecting decentralized data sharing among untrusted participants in off-grid networks. The proposed architecture realizes this goal via the integration of existing blockchain frameworks (Hyperledger Fabric, Indy, Aries) with an off-grid network device and a distributed file system. We evaluate the proposed platform through experiments and show results for its throughput and latency, which indicate its adequate performance for supporting off-grid decentralized applications.
Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners
Venue: arXiv cs.LG 2020
Year: 2020

We study the problem of best arm identification in linearly parameterised multi-armed bandits. Given a set of feature vectors $\mathcal{X}\subset\mathbb{R}^d,$ a confidence parameter $δ$ and an unknown vector $θ^*,$ the goal is to identify $\arg\max_{x\in\mathcal{X}}x^Tθ^*$, with probability at least $1-δ,$ using noisy measurements of the form $x^Tθ^*.$ For this fixed confidence ($δ$-PAC) setting, we propose an explicitly implementable and provably order-optimal sample-complexity algorithm to solve this problem. Previous approaches rely on access to minimax optimization oracles. The algorithm, which we call the \textit{Phased Elimination Linear Exploration Game} (PELEG), maintains a high-probability confidence ellipsoid containing $θ^*$ in each round and uses it to eliminate suboptimal arms in phases. PELEG achieves fast shrinkage of this confidence ellipsoid along the most confusing (i.e., close to, but not optimal) directions by interpreting the problem as a two player zero-sum game, and sequentially converging to its saddle point using low-regret learners to compute players' strategies in each round. We analyze the sample complexity of PELEG and show that it matches, up to order, an instance-dependent lower bound on sample complexity in the linear bandit setting. We also provide numerical results for the proposed algorithm consistent with its theoretical guarantees.
Special-case Algorithms for Blackbox Radical Membership, Nullstellensatz and Transcendence Degree
Venue: arXiv cs.CC 2020
Year: 2020

Radical membership testing, and the special case of Hilbert's Nullstellensatz (HN), is a fundamental computational algebra problem. It is NP-hard; and has a famous PSPACE algorithm due to effective Nullstellensatz bounds. We identify a useful case of these problems where practical algorithms, and improved bounds, could be given, when the transcendence degree $r$ of the input polynomials is smaller than the number of variables $n$. If $d$ is the degree bound on the input polynomials, then we solve radical membership (even if input polynomials are blackboxes) in around $d^r$ time. The prior best was $> d^n$ time (always, $d^n\ge d^r$). Also, we significantly improve effective Nullstellensatz degree-bound, when $r\ll n$. Structurally, our proof shows that these problems reduce to the case of $r+1$ polynomials of transcendence degree $\ge r$. This input instance (corresponding to none or a unique annihilator) is at the core of HN's hardness. Our proof methods invoke basic algebraic-geometry.
Delay-Constrained Topology-Transparent Distributed Scheduling for MANETs
Venue: arXiv cs.NI 2020
Year: 2020

Transparent topology is common in many mobile ad hoc networks (MANETs) such as vehicle ad hoc networks (VANETs), unmanned aerial vehicle (UAV) ad hoc networks, and wireless sensor networks due to their decentralization and mobility nature. There are many existing works on distributed scheduling scheme design for topology-transparent MANETs. Most of them focus on delay-unconstrained settings. However, with the proliferation of real-time applications over wireless communications, it becomes more and more important to support delay-constrained traffic in MANETs. In such applications, each packet has a given hard deadline: if it is not delivered before its deadline, its validity will expire and it will be removed from the system. This feature is fundamentally different from the traditional delay-unconstrained one. In this paper, we for the first time investigate distributed scheduling schemes for a topology-transparent MANET to support delay-constrained traffic. We analyze and compare probabilistic ALOHA scheme and deterministic sequence schemes, including the conventional time division multiple access (TDMA), the Galois field (GF) sequence scheme proposed in \cite{chlamtac1994making}, and the combination sequence scheme that we propose for a special type of sparse network topology.We use both theoretical analysis and empirical simulations to compare all these schemes and summarize the conditions under which different individual schemes perform best.
A New Algorithm for Tessellated Kernel Learning
Venue: arXiv cs.LG 2020
Year: 2020

The accuracy and complexity of machine learning algorithms based on kernel optimization are limited by the set of kernels over which they are able to optimize. An ideal set of kernels should: admit a linear parameterization (for tractability); be dense in the set of all kernels (for robustness); be universal (for accuracy). The recently proposed Tesselated Kernels (TKs) is currently the only known class which meets all three criteria. However, previous algorithms for optimizing TKs were limited to classification and relied on Semidefinite Programming (SDP) - limiting them to relatively small datasets. By contrast, the 2-step algorithm proposed here scales to 10,000 data points and extends to the regression problem. Furthermore, when applied to benchmark data, the algorithm demonstrates significant improvement in performance over Neural Nets and SimpleMKL with similar computation time.
Split-Merge Pooling
Venue: arXiv cs.CV 2020
Year: 2020

There are a variety of approaches to obtain a vast receptive field with convolutional neural networks (CNNs), such as pooling or striding convolutions. Most of these approaches were initially designed for image classification and later adapted to dense prediction tasks, such as semantic segmentation. However, the major drawback of this adaptation is the loss of spatial information. Even the popular dilated convolution approach, which in theory is able to operate with full spatial resolution, needs to subsample features for large image sizes in order to make the training and inference tractable. In this work, we introduce Split-Merge pooling to fully preserve the spatial information without any subsampling. By applying Split-Merge pooling to deep networks, we achieve, at the same time, a very large receptive field. We evaluate our approach for dense semantic segmentation of large image sizes taken from the Cityscapes and GTA-5 datasets. We demonstrate that by replacing max-pooling and striding convolutions with our split-merge pooling, we are able to improve the accuracy of different variations of ResNet significantly.