OpenRaiser/Intern-Atlas huggingface dataset:
Language Semantics Interpretation with an Interaction-based Recurrent Neural Networks
Venue: arXiv cs.CL 2021
Year: 2021

Text classification is a fundamental language task in Natural Language Processing. A variety of sequential models is capable making good predictions yet there is lack of connection between language semantics and prediction results. This paper proposes a novel influence score (I-score), a greedy search algorithm called Backward Dropping Algorithm (BDA), and a novel feature engineering technique called the "dagger technique". First, the paper proposes a novel influence score (I-score) to detect and search for the important language semantics in text document that are useful for making good prediction in text classification tasks. Next, a greedy search algorithm called the Backward Dropping Algorithm is proposed to handle long-term dependencies in the dataset. Moreover, the paper proposes a novel engineering technique called the "dagger technique" that fully preserve the relationship between explanatory variable and response variable. The proposed techniques can be further generalized into any feed-forward Artificial Neural Networks (ANNs) and Convolutional Neural Networks (CNNs), and any neural network. A real-world application on the Internet Movie Database (IMDB) is used and the proposed methods are applied to improve prediction performance with an 81% error reduction comparing with other popular peers if I-score and "dagger technique" are not implemented.
Transformer-based Korean Pretrained Language Models: A Survey on Three Years of Progress
Venue: arXiv cs.CL 2021
Year: 2021

With the advent of Transformer, which was used in translation models in 2017, attention-based architectures began to attract attention. Furthermore, after the emergence of BERT, which strengthened the NLU-specific encoder part, which is a part of the Transformer, and the GPT architecture, which strengthened the NLG-specific decoder part, various methodologies, data, and models for learning the Pretrained Language Model began to appear. Furthermore, in the past three years, various Pretrained Language Models specialized for Korean have appeared. In this paper, we intend to numerically and qualitatively compare and analyze various Korean PLMs released to the public.
Differentiable Scripting
Venue: arXiv cs.MS 2021
Year: 2021

In Computational Science, Engineering and Finance (CSEF) scripts typically serve as the "glue" between potentially highly complex and computationally expensive external subprograms. Differentiability of the resulting programs turns out to be essential in the context of derivative-based methods for error analysis, uncertainty quantification, optimization or training of surrogates. We argue that it should be enforced by the scripting language itself through exclusive support of differentiable (smoothed) external subprograms and differentiable intrinsics combined with prohibition of nondifferentiable branches in the data flow. Illustration is provided by a prototype adjoint code compiler for a simple Python-like scripting language.
Scaling Up Influence Functions
Venue: arXiv cs.LG 2021
Year: 2021

We address efficient calculation of influence functions for tracking predictions back to the training data. We propose and analyze a new approach to speeding up the inverse Hessian calculation based on Arnoldi iteration. With this improvement, we achieve, to the best of our knowledge, the first successful implementation of influence functions that scales to full-size (language and vision) Transformer models with several hundreds of millions of parameters. We evaluate our approach on image classification and sequence-to-sequence tasks with tens to a hundred of millions of training examples. Our code will be available at https://github.com/google-research/jax-influence.
Fixed-Parameter Sensitivity Oracles
Venue: arXiv cs.DS 2021
Year: 2021

We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity $f$ for an FPT problem $Π$ on a graph $G$ with parameter $k$ preprocesses $G$ in time $O(g(f,k) \cdot \textsf{poly}(n))$. When queried with a set $F$ of at most $f$ edges of $G$, the oracle reports the answer to the $Π$-with the same parameter $k$-on the graph $G-F$, i.e., $G$ deprived of $F$. The oracle should answer queries in a time that is significantly faster than merely running the best-known FPT algorithm on $G-F$ from scratch. We mainly design sensitivity oracles for the $k$-Path and the $k$-Vertex Cover problem. Following our line of research connecting fault-tolerant FPT and shortest paths problems, we also introduce parameterization to the computation of distance preservers. We study the problem, given a directed unweighted graph with a fixed source $s$ and parameters $f$ and $k$, to construct a polynomial-sized oracle that efficiently reports, for any target vertex $v$ and set $F$ of at most $f$ edges, whether the distance from $s$ to $v$ increases at most by an additive term of $k$ in $G-F$.
The Service Analysis and Network Diagnosis DataPipeline
Venue: arXiv cs.NI 2021
Year: 2021

Modern network performance monitoring toolkits, such as perfSONAR, take a remarkable number of measurements about the local network environment. To gain a complete picture of network performance, however, one needs to aggregate data across a large number of endpoints. The Service Analysis and Network Diagnosis (SAND) data pipeline collects data from diverse sources and ingests these measurements into a message bus. The message bus allows the project to send the data to multiple consumers, including a tape archive, an Elasticsearch database, and a peer infrastructure at CERN. In this paper, we explain the architecture and evolution of the SAND data pipeline, the scale of the resulting dataset, and how it supports a wide variety of network analysis applications.
LightSync: Ultra Light Client for PoW Blockchains
Venue: arXiv cs.CR 2021
Year: 2021

Full nodes in a blockchain network store and verify a copy of the whole blockchain. Unlike full nodes, light clients are low-capacity devices that want to validate certain data on a blockchain. They query the data they want from a full node. If light clients do not verify the data they receive, full nodes might deceive them. SPV, introduced in the Bitcoin paper, is a practical solution to this problem currently used in many PoW blockchains. In SPV, the resources needed to verify a full node's response grow linearly with the blockchain size, making it inefficient over the long run. Another issue with SPV is that the full nodes do not get compensated for the services they provide. In this work, we introduce LightSync, a simple and cost-effective solution for light clients to verify the inclusion of certain data in a PoW blockchain. The resources needed for running LightSync remain constant no matter what the size of the blockchain is. LightSync uses an incentive mechanism that encourages full nodes to participate in the protocol. We perform a thorough analysis of the security of LightSync and discuss the details of deploying it in a real-world environment.
Requirements for Open Political Information: Transparency Beyond Open Data
Venue: arXiv cs.AI 2021
Year: 2021

A politically informed citizenry is imperative for a welldeveloped democracy. While the US government has pursued policies for open data, these efforts have been insufficient in achieving an open government because only people with technical and domain knowledge can access information in the data. In this work, we conduct user interviews to identify wants and needs among stakeholders. We further use this information to sketch out the foundational requirements for a functional political information technical system.
Distilled Domain Randomization
Venue: arXiv cs.LG 2021
Year: 2021

Deep reinforcement learning is an effective tool to learn robot control policies from scratch. However, these methods are notorious for the enormous amount of required training data which is prohibitively expensive to collect on real robots. A highly popular alternative is to learn from simulations, allowing to generate the data much faster, safer, and cheaper. Since all simulators are mere models of reality, there are inevitable differences between the simulated and the real data, often referenced as the 'reality gap'. To bridge this gap, many approaches learn one policy from a distribution over simulators. In this paper, we propose to combine reinforcement learning from randomized physics simulations with policy distillation. Our algorithm, called Distilled Domain Randomization (DiDoR), distills so-called teacher policies, which are experts on domains that have been sampled initially, into a student policy that is later deployed. This way, DiDoR learns controllers which transfer directly from simulation to reality, i.e., without requiring data from the target domain. We compare DiDoR against three baselines in three sim-to-sim as well as two sim-to-real experiments. Our results show that the target domain performance of policies trained with DiDoR is en par or better than the baselines'. Moreover, our approach neither increases the required memory capacity nor the time to compute an action, which may well be a point of failure for successfully deploying the learned controller.
A Meta-Theorem for Distributed Certification
Venue: arXiv cs.DC 2021
Year: 2021

Distributed certification, whether it be proof-labeling schemes, locally checkable proofs, etc., deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate is assigned to each process in the system by a non-trustable oracle, and the processes are in charge of verifying these certificates, so that two properties are satisfied: completeness, i.e., for every legal instance, there is a certificate assignment leading all processes to accept, and soundness, i.e., for every illegal instance, and for every certificate assignment, at least one process rejects. The verification of the certificates must be fast, and the certificates themselves must be small. A large quantity of results have been produced in this framework, each aiming at designing a distributed certification mechanism for specific boolean predicates. This paper presents a "meta-theorem", applying to many boolean predicates at once. Specifically, we prove that, for every boolean predicate on graphs definable in the monadic second-order (MSO) logic of graphs, there exists a distributed certification mechanism using certificates on $O(\log^2n)$ bits in $n$-node graphs of bounded treewidth, with a verification protocol involving a single round of communication between neighbors.
Online Bin Packing with Known T
Venue: arXiv cs.DS 2021
Year: 2021

In the online bin packing problem, a sequence of items is revealed one at a time, and each item must be packed into an available bin instantly upon its arrival. In this paper, we revisit the problem under a setting where the total number of items T is known in advance, also known as the closed online bin packing problem. Specifically, we study both the stochastic model and the random permutation model. We develop and analyze an adaptive algorithm that solves an offline bin packing problem at geometric time intervals and uses the offline optimal solution to guide online packing decisions. Under both models, we show that the algorithm achieves C\sqrt{T} regret (in terms of the number of used bins) compared to the hindsight optimal solution, where C is a universal constant (<= 13) that bears no dependence on the underlying distribution or the item sizes. The result shows the lower bound barrier of Ω(\sqrt{T \log T}) in Shor (1986) can be broken with solely the knowledge of the horizon T, but without a need of knowing the underlying distribution. As to the algorithm analysis, we develop a new approach to analyzing the packing dynamic using the notion of exchangeable random variables. The approach creates a symmetrization between the offline solution and the online solution, and it is used to analyze both the algorithm performance and various benchmarks related to the bin packing problem. For the latter one, our analysis provides an alternative (probably simpler) treatment and tightens the analysis of the asymptotic benchmark of the stochastic bin packing problem in Rhee and Talagrand (1989a,b). As the analysis only relies on a symmetry between the offline and online problems, the algorithm and benchmark analyses can be naturally extended from the stochastic model to the random permutation model.
Contextual Bandit Applications in Customer Support Bot
Venue: arXiv cs.LG 2021
Year: 2021

Virtual support agents have grown in popularity as a way for businesses to provide better and more accessible customer service. Some challenges in this domain include ambiguous user queries as well as changing support topics and user behavior (non-stationarity). We do, however, have access to partial feedback provided by the user (clicks, surveys, and other events) which can be leveraged to improve the user experience. Adaptable learning techniques, like contextual bandits, are a natural fit for this problem setting. In this paper, we discuss real-world implementations of contextual bandits (CB) for the Microsoft virtual agent. It includes intent disambiguation based on neural-linear bandits (NLB) and contextual recommendations based on a collection of multi-armed bandits (MAB). Our solutions have been deployed to production and have improved key business metrics of the Microsoft virtual agent, as confirmed by A/B experiments. Results include a relative increase of over 12% in problem resolution rate and relative decrease of over 4% in escalations to a human operator. While our current use cases focus on intent disambiguation and contextual recommendation for support bots, we believe our methods can be extended to other domains.
Zero-shot hashtag segmentation for multilingual sentiment analysis
Venue: arXiv cs.CL 2021
Year: 2021

Hashtag segmentation, also known as hashtag decomposition, is a common step in preprocessing pipelines for social media datasets. It usually precedes tasks such as sentiment analysis and hate speech detection. For sentiment analysis in medium to low-resourced languages, previous research has demonstrated that a multilingual approach that resorts to machine translation can be competitive or superior to previous approaches to the task. We develop a zero-shot hashtag segmentation framework and demonstrate how it can be used to improve the accuracy of multilingual sentiment analysis pipelines. Our zero-shot framework establishes a new state-of-the-art for hashtag segmentation datasets, surpassing even previous approaches that relied on feature engineering and language models trained on in-domain data.
Analyzing a Carceral Algorithm used by the Pennsylvania Department of Corrections
Venue: arXiv cs.CY 2021
Year: 2021

Scholars have focused on algorithms used during sentencing, bail, and parole, but little work explores what we call carceral algorithms that are used during incarceration. This paper is focused on the Pennsylvania Additive Classification Tool (PACT) used to classify prisoners' custody levels while they are incarcerated. Algorithms that are used during incarceration warrant deeper attention by scholars because they have the power to enact the lived reality of the prisoner. The algorithm in this case determines the likelihood a person would endure additional disciplinary actions, can complete required programming, and gain experiences that, among other things, are distilled into variables feeding into the parole algorithm. Given such power, examining algorithms used on people currently incarcerated offers a unique analytic view to think about the dialectic relationship between data and algorithms. Our examination of the PACT is two-fold and complementary. First, our qualitative overview of the historical context surrounding PACT reveals that it is designed to prioritize incapacitation and control over rehabilitation. While it closely informs prisoner rehabilitation plans and parole considerations, it is rooted in population management for prison securitization. Second, on analyzing data for 146,793 incarcerated people in PA, along with associated metadata related to the PACT, we find it is replete with racial bias as well as errors, omissions, and inaccuracies. Our findings to date further caution against data-driven criminal justice reforms that rely on pre-existing data infrastructures and expansive, uncritical, data-collection routines.
Multi-scale Graph Convolutional Networks with Self-Attention
Venue: arXiv cs.LG 2021
Year: 2021

Graph convolutional networks (GCNs) have achieved remarkable learning ability for dealing with various graph structural data recently. In general, deep GCNs do not work well since graph convolution in conventional GCNs is a special form of Laplacian smoothing, which makes the representation of different nodes indistinguishable. In the literature, multi-scale information was employed in GCNs to enhance the expressive power of GCNs. However, over-smoothing phenomenon as a crucial issue of GCNs remains to be solved and investigated. In this paper, we propose two novel multi-scale GCN frameworks by incorporating self-attention mechanism and multi-scale information into the design of GCNs. Our methods greatly improve the computational efficiency and prediction accuracy of the GCNs model. Extensive experiments on both node classification and graph classification demonstrate the effectiveness over several state-of-the-art GCNs. Notably, the proposed two architectures can efficiently mitigate the over-smoothing problem of GCNs, and the layer of our model can even be increased to $64$.
A Deep-Learning Intelligent System Incorporating Data Augmentation for Short-Term Voltage Stability Assessment of Power Systems
Venue: arXiv cs.LG 2021
Year: 2021

Facing the difficulty of expensive and trivial data collection and annotation, how to make a deep learning-based short-term voltage stability assessment (STVSA) model work well on a small training dataset is a challenging and urgent problem. Although a big enough dataset can be directly generated by contingency simulation, this data generation process is usually cumbersome and inefficient; while data augmentation provides a low-cost and efficient way to artificially inflate the representative and diversified training datasets with label preserving transformations. In this respect, this paper proposes a novel deep-learning intelligent system incorporating data augmentation for STVSA of power systems. First, due to the unavailability of reliable quantitative criteria to judge the stability status for a specific power system, semi-supervised cluster learning is leveraged to obtain labeled samples in an original small dataset. Second, to make deep learning applicable to the small dataset, conditional least squares generative adversarial networks (LSGAN)-based data augmentation is introduced to expand the original dataset via artificially creating additional valid samples. Third, to extract temporal dependencies from the post-disturbance dynamic trajectories of a system, a bi-directional gated recurrent unit with attention mechanism based assessment model is established, which bi-directionally learns the significant time dependencies and automatically allocates attention weights. The test results demonstrate the presented approach manages to achieve better accuracy and a faster response time with original small datasets. Besides classification accuracy, this work employs statistical measures to comprehensively examine the performance of the proposal.
Adapting BERT for Continual Learning of a Sequence of Aspect Sentiment Classification Tasks
Venue: arXiv cs.CL 2021
Year: 2021

This paper studies continual learning (CL) of a sequence of aspect sentiment classification (ASC) tasks. Although some CL techniques have been proposed for document sentiment classification, we are not aware of any CL work on ASC. A CL system that incrementally learns a sequence of ASC tasks should address the following two issues: (1) transfer knowledge learned from previous tasks to the new task to help it learn a better model, and (2) maintain the performance of the models for previous tasks so that they are not forgotten. This paper proposes a novel capsule network based model called B-CL to address these issues. B-CL markedly improves the ASC performance on both the new task and the old tasks via forward and backward knowledge transfer. The effectiveness of B-CL is demonstrated through extensive experiments.
Smart Metering System Capable of Anomaly Detection by Bi-directional LSTM Autoencoder
Venue: arXiv cs.LG 2021
Year: 2021

Anomaly detection is concerned with a wide range of applications such as fault detection, system monitoring, and event detection. Identifying anomalies from metering data obtained from smart metering system is a critical task to enhance reliability, stability, and efficiency of the power system. This paper presents an anomaly detection process to find outliers observed in the smart metering system. In the proposed approach, bi-directional long short-term memory (BiLSTM) based autoencoder is used and finds the anomalous data point. It calculates the reconstruction error through autoencoder with the non-anomalous data, and the outliers to be classified as anomalies are separated from the non-anomalous data by predefined threshold. Anomaly detection method based on the BiLSTM autoencoder is tested with the metering data corresponding to 4 types of energy sources electricity/water/heating/hot water collected from 985 households.
Inconsistent Planning: When in doubt, toss a coin!
Venue: arXiv cs.CC 2021
Year: 2021

One of the most widespread human behavioral biases is the present bias -- the tendency to overestimate current costs by a bias factor. Kleinberg and Oren (2014) introduced an elegant graph-theoretical model of inconsistent planning capturing the behavior of a present-biased agent accomplishing a set of actions. The essential measure of the system introduced by Kleinberg and Oren is the cost of irrationality -- the ratio of the total cost of the actions performed by the present-biased agent to the optimal cost. This measure is vital for a task designer to estimate the aftermaths of human behavior related to time-inconsistent planning, including procrastination and abandonment. As we prove in this paper, the cost of irrationality is highly susceptible to the agent's choices when faced with a few possible actions of equal estimated costs. To address this issue, we propose a modification of Kleinberg-Oren's model of inconsistent planning. In our model, when an agent selects from several options of minimum prescribed cost, he uses a randomized procedure. We explore the algorithmic complexity of computing and estimating the cost of irrationality in the new model.
Guided Imitation of Task and Motion Planning
Venue: arXiv cs.RO 2021
Year: 2021

While modern policy optimization methods can do complex manipulation from sensory data, they struggle on problems with extended time horizons and multiple sub-goals. On the other hand, task and motion planning (TAMP) methods scale to long horizons but they are computationally expensive and need to precisely track world state. We propose a method that draws on the strength of both methods: we train a policy to imitate a TAMP solver's output. This produces a feed-forward policy that can accomplish multi-step tasks from sensory data. First, we build an asynchronous distributed TAMP solver that can produce supervision data fast enough for imitation learning. Then, we propose a hierarchical policy architecture that lets us use partially trained control policies to speed up the TAMP solver. In robotic manipulation tasks with 7-DoF joint control, the partially trained policies reduce the time needed for planning by a factor of up to 2.6. Among these tasks, we can learn a policy that solves the RoboSuite 4-object pick-place task 88% of the time from object pose observations and a policy that solves the RoboDesk 9-goal benchmark 79% of the time from RGB images (averaged across the 9 disparate tasks).