OpenRaiser/Intern-Atlas huggingface dataset:
Modernizing Historical Documents: a User Study
Venue: arXiv cs.CL 2020
Year: 2020

Accessibility to historical documents is mostly limited to scholars. This is due to the language barrier inherent in human language and the linguistic properties of these documents. Given a historical document, modernization aims to generate a new version of it, written in the modern version of the document's language. Its goal is to tackle the language barrier, decreasing the comprehension difficulty and making historical documents accessible to a broader audience. In this work, we proposed a new neural machine translation approach that profits from modern documents to enrich its systems. We tested this approach with both automatic and human evaluation, and conducted a user study. Results showed that modernization is successfully reaching its goal, although it still has room for improvement.
On List Decoding of 5G-NR Polar Codes
Venue: arXiv cs.IT 2020
Year: 2020

The 5th generation wireless systems (5G) standardization process of the 3rd generation partnership project (3GPP) chose polar codes as a channel coding scheme for the control channel. In case of downlink control information, polar codes are concatenated with distributed distributed cyclic redundancy check (CRC). Whereas CRC bits allow to improve the performance of successive cancellation list (SCL) decoders by improving distance properties, distributed CRC bits allow for path pruning and decoding early-termination. In this paper, we show how to take advantage of the distributed CRC to improve SCL decoding, analyzing various schemes having different earlytermination and error correction properties. Simulation results compare the proposed decoding schemes, showing different tradeoffs between error-correction performance and early-termination with different decoder parameters.
On Characterizations for Subclasses of Directed Co-Graphs
Venue: arXiv cs.DM 2020
Year: 2020

Undirected co-graphs are those graphs which can be generated from the single vertex graph by disjoint union and join operations. Co-graphs are exactly the P_4-free graphs (where P_4 denotes the path on 4 vertices). Co-graphs itself and several subclasses haven been intensively studied. Among these are trivially perfect graphs, threshold graphs, weakly quasi threshold graphs, and simple co-graphs. Directed co-graphs are precisely those digraphs which can be defined from the single vertex graph by applying the disjoint union, order composition, and series composition. By omitting the series composition we obtain the subclass of oriented co-graphs which has been analyzed by Lawler in the 1970s and the restriction to linear expressions was recently studied by Boeckner. There are only a few versions of subclasses of directed co-graphs until now. By transmitting the restrictions of undirected subclasses to the directed classes, we define the corresponding subclasses for directed co-graphs. We consider directed and oriented versions of threshold graphs, simple co-graphs, co-simple co-graphs, trivially perfect graphs, co-trivially perfect graphs, weakly quasi threshold graphs and co-weakly quasi threshold graphs. For all these classes we provide characterizations by finite sets of minimal forbidden induced subdigraphs. Further we analyze relations between these graph classes.
XNect: Real-time Multi-Person 3D Motion Capture with a Single RGB Camera
Venue: arXiv cs.CV 2020
Year: 2020

We present a real-time approach for multi-person 3D motion capture at over 30 fps using a single RGB camera. It operates successfully in generic scenes which may contain occlusions by objects and by other people. Our method operates in subsequent stages. The first stage is a convolutional neural network (CNN) that estimates 2D and 3D pose features along with identity assignments for all visible joints of all individuals.We contribute a new architecture for this CNN, called SelecSLS Net, that uses novel selective long and short range skip connections to improve the information flow allowing for a drastically faster network without compromising accuracy. In the second stage, a fully connected neural network turns the possibly partial (on account of occlusion) 2Dpose and 3Dpose features for each subject into a complete 3Dpose estimate per individual. The third stage applies space-time skeletal model fitting to the predicted 2D and 3D pose per subject to further reconcile the 2D and 3D pose, and enforce temporal coherence. Our method returns the full skeletal pose in joint angles for each subject. This is a further key distinction from previous work that do not produce joint angle results of a coherent skeleton in real time for multi-person scenes. The proposed system runs on consumer hardware at a previously unseen speed of more than 30 fps given 512x320 images as input while achieving state-of-the-art accuracy, which we will demonstrate on a range of challenging real-world scenes.
GPU-based Parallel Computation Support for Stan
Venue: arXiv cs.MS 2020
Year: 2020

This paper details an extensible OpenCL framework that allows Stan to utilize heterogeneous compute devices. It includes GPU-optimized routines for the Cholesky decomposition, its derivative, other matrix algebra primitives and some commonly used likelihoods, with more additions planned for the near future. Stan users can now benefit from large speedups offered by GPUs with little effort and without changes to their existing Stan code. We demonstrate the practical utility of our work with two examples - logistic regression and Gaussian Process regression.
Convergence Rates of Smooth Message Passing with Rounding in Entropy-Regularized MAP Inference
Venue: arXiv cs.LG 2020
Year: 2020

Maximum a posteriori (MAP) inference is a fundamental computational paradigm for statistical inference. In the setting of graphical models, MAP inference entails solving a combinatorial optimization problem to find the most likely configuration of the discrete-valued model. Linear programming (LP) relaxations in the Sherali-Adams hierarchy are widely used to attempt to solve this problem, and smooth message passing algorithms have been proposed to solve regularized versions of these LPs with great success. This paper leverages recent work in entropy-regularized LPs to analyze convergence rates of a class of edge-based smooth message passing algorithms to $ε$-optimality in the relaxation. With an appropriately chosen regularization constant, we present a theoretical guarantee on the number of iterations sufficient to recover the true integral MAP solution when the LP is tight and the solution is unique.
Sequence Labeling Parsing by Learning Across Representations
Venue: arXiv cs.CL 2020
Year: 2020

We use parsing as sequence labeling as a common framework to learn across constituency and dependency syntactic abstractions. To do so, we cast the problem as multitask learning (MTL). First, we show that adding a parsing paradigm as an auxiliary loss consistently improves the performance on the other paradigm. Secondly, we explore an MTL sequence labeling model that parses both representations, at almost no cost in terms of performance and speed. The results across the board show that on average MTL models with auxiliary losses for constituency parsing outperform single-task ones by 1.14 F1 points, and for dependency parsing by 0.62 UAS points.
Approximate Similarity Search Under Edit Distance Using Locality-Sensitive Hashing
Venue: arXiv cs.DS 2020
Year: 2020

Edit distance similarity search, also called approximate pattern matching, is a fundamental problem with widespread database applications. The goal of the problem is to preprocess $n$ strings of length $d$, to quickly answer queries $q$ of the form: if there is a database string within edit distance $r$ of $q$, return a database string within edit distance $cr$ of $q$. Previous approaches to this problem either rely on very large (superconstant) approximation ratios $c$, or very small search radii $r$. Outside of a narrow parameter range, these solutions are not competitive with trivially searching through all $n$ strings. In this work give a simple and easy-to-implement hash function that can quickly answer queries for a wide range of parameters. Specifically, our strategy can answer queries in time $\tilde{O}(d3^rn^{1/c})$. The best known practical results require $c \gg r$ to achieve any correctness guarantee; meanwhile, the best known theoretical results are very involved and difficult to implement, and require query time at least $24^r$. Our results significantly broaden the range of parameters for which we can achieve nontrivial bounds, while retaining the practicality of a locality-sensitive hash function. We also show how to apply our ideas to the closely-related Approximate Nearest Neighbor problem for edit distance, obtaining similar time bounds.
The Role of Memory in Stochastic Optimization
Venue: arXiv cs.LG 2020
Year: 2020

The choice of how to retain information about past gradients dramatically affects the convergence properties of state-of-the-art stochastic optimization methods, such as Heavy-ball, Nesterov's momentum, RMSprop and Adam. Building on this observation, we use stochastic differential equations (SDEs) to explicitly study the role of memory in gradient-based algorithms. We first derive a general continuous-time model that can incorporate arbitrary types of memory, for both deterministic and stochastic settings. We provide convergence guarantees for this SDE for weakly-quasi-convex and quadratically growing functions. We then demonstrate how to discretize this SDE to get a flexible discrete-time algorithm that can implement a board spectrum of memories ranging from short- to long-term. Not only does this algorithm increase the degrees of freedom in algorithmic choice for practitioners but it also comes with better stability properties than classical momentum in the convex stochastic setting. In particular, no iterate averaging is needed for convergence. Interestingly, our analysis also provides a novel interpretation of Nesterov's momentum as stable gradient amplification and highlights a possible reason for its unstable behavior in the (convex) stochastic setting. Furthermore, we discuss the use of long term memory for second-moment estimation in adaptive methods, such as Adam and RMSprop. Finally, we provide an extensive experimental study of the effect of different types of memory in both convex and nonconvex settings.
Perspective Taking in Deep Reinforcement Learning Agents
Venue: arXiv cs.AI 2020
Year: 2020

Perspective taking is the ability to take the point of view of another agent. This skill is not unique to humans as it is also displayed by other animals like chimpanzees. It is an essential ability for social interactions, including efficient cooperation, competition, and communication. Here we present our progress toward building artificial agents with such abilities. We implemented a perspective taking task inspired by experiments done with chimpanzees. We show that agents controlled by artificial neural networks can learn via reinforcement learning to pass simple tests that require perspective taking capabilities. We studied whether this ability is more readily learned by agents with information encoded in allocentric or egocentric form for both their visual perception and motor actions. We believe that, in the long run, building better artificial agents with perspective taking ability can help us develop artificial intelligence that is more human-like and easier to communicate with.
A Survey of Maturity Models from Nolon to DevOps and Their Applications in Process Improvement
Venue: arXiv cs.SE 2020
Year: 2020

This paper traces the history of Maturity Models and their impact on Process Improvement from the early work of Shewhart to their current usage with DevOps. The history of modern process improvement can be traced at least to Shewhart. From his foundational process contributions and those of other innovators a variety of methods and tools to aid in process quality advancement were developed. This paper begins by reviewing those early steps and then focuses on the emergence of Maturity Models in the 1970s with initial approach by Nolan. The broad adoption of Maturity Models that followed through the success of the CMM and then the CMMI approaches is detailed. This then leads to a general survey of additional models developed for such areas as IT Service Management, ITIL, Project Management, Agile Development, DevOps, CERT, and MDM among others. Finally, this paper discusses the application of these models in the support of process improvement and their limitations. Readers of this paper can expect to gain an appreciation for the origins of these models and surrounding methods as well as an ability to conduct comparative analysis of such models to aid in their selection and application. Keywords: Process Improvement, Process Engineering, Maturity Models, Capability Maturity Models, CMM, CMMI, ITSM, ITIL, Agile, DevOps, History of Science, History of Computing, Software Engineering, Quality.
Data Encoding for Byzantine-Resilient Distributed Optimization
Venue: arXiv cs.DC 2020
Year: 2020

We study distributed optimization in the presence of Byzantine adversaries, where both data and computation are distributed among $m$ worker machines, $t$ of which may be corrupt. The compromised nodes may collaboratively and arbitrarily deviate from their pre-specified programs, and a designated (master) node iteratively computes the model/parameter vector for generalized linear models. In this work, we primarily focus on two iterative algorithms: Proximal Gradient Descent (PGD) and Coordinate Descent (CD). Gradient descent (GD) is a special case of these algorithms. PGD is typically used in the data-parallel setting, where data is partitioned across different samples, whereas, CD is used in the model-parallelism setting, where data is partitioned across the parameter space. In this paper, we propose a method based on data encoding and error correction over real numbers to combat adversarial attacks. We can tolerate up to $t\leq \lfloor\frac{m-1}{2}\rfloor$ corrupt worker nodes, which is information-theoretically optimal. We give deterministic guarantees, and our method does not assume any probability distribution on the data. We develop a {\em sparse} encoding scheme which enables computationally efficient data encoding and decoding. We demonstrate a trade-off between the corruption threshold and the resource requirements (storage, computational, and communication complexity). As an example, for $t\leq\frac{m}{3}$, our scheme incurs only a {\em constant} overhead on these resources, over that required by the plain distributed PGD/CD algorithms which provide no adversarial protection. To the best of our knowledge, ours is the first paper that makes CD secure against adversarial attacks. Our encoding scheme extends efficiently to the data streaming model and for stochastic gradient descent (SGD). We also give experimental results to show the efficacy of our proposed schemes.
GTIRB: Intermediate Representation for Binaries
Venue: arXiv cs.PL 2020
Year: 2020

GTIRB is an intermediate representation for binary analysis and rewriting tools including disassemblers, lifters, analyzers, rewriters, and pretty-printers. GTIRB is designed to enable communication between tools in a format that provides the basic information necessary for analysis and rewriting while making no further assumptions about domain (e.g., malware vs. cleanware, or PE vs. ELF) or semantic interpretation (functional vs. operational semantics). This design supports the goals of (1) encouraging tool modularization and re-use allowing researchers and developers to focus on a single aspect of binary analysis and rewriting without committing to any single tool chain and (2) facilitating communication and comparison between tools.
A Formal Axiomatization of Computation
Venue: arXiv cs.CC 2020
Year: 2020

We introduce an axiomatization for the notion of computation. Based on the idea of Brouwer choice sequences, we construct a model, denoted by $E$, which satisfies our axioms and $E \models \mathrm{ P \neq NP}$. In other words, regarding "effective computability" in Brouwer intuitionism viewpoint, we show $\mathrm{ P \neq NP}$.
Estimating Mass Distribution of Articulated Objects using Non-prehensile Manipulation
Venue: arXiv cs.RO 2020
Year: 2020

We explore the problem of estimating the mass distribution of an articulated object by an interactive robotic agent. Our method predicts the mass distribution of an object by using the limited sensing and actuating capabilities of a robotic agent that is interacting with the object. We are inspired by the role of exploratory play in human infants. We take the combined approach of supervised and reinforcement learning to train an agent that learns to strategically interact with the object to estimate the object's mass distribution. Our method consists of two neural networks: (i) the policy network which decides how to interact with the object, and (ii) the predictor network that estimates the mass distribution given a history of observations and interactions. Using our method, we train a robotic arm to estimate the mass distribution of an object with moving parts (e.g. an articulated rigid body system) by pushing it on a surface with unknown friction properties. We also demonstrate how our training from simulations can be transferred to real hardware using a small amount of real-world data for fine-tuning. We use a UR10 robot to interact with 3D printed articulated chains with varying mass distributions and show that our method significantly outperforms the baseline system that uses random pushes to interact with the object.
Stochastic Monotone Submodular Maximization with Queries
Venue: arXiv cs.DS 2020
Year: 2020

We study a stochastic variant of monotone submodular maximization problem as follows. We are given a monotone submodular function as an objective function and a feasible domain defined on a finite set, and our goal is to find a feasible solution that maximizes the objective function. A special part of the problem is that each element in the finite set has a random hidden state, active or inactive, only the active elements contribute to the objective value, and we can conduct a query to an element to reveal its hidden state. The goal is to obtain a feasible solution having a large objective value by conducting a small number of queries. This is the first attempt to consider nonlinear objective functions in such a stochastic model. We prove that the problem admits a good query strategy if the feasible domain has a uniform exchange property. This result generalizes Blum et al.'s result on the unweighted matching problem and Behnezhad and Reyhani's result on the weighted matching problem in both objective function and feasible domain.
$L_p$ Pattern Matching in a Stream
Venue: arXiv cs.DS 2020
Year: 2020

We consider the problem of computing distance between a pattern of length $n$ and all $n$-length subwords of a text in the streaming model. In the streaming setting, only the Hamming distance ($L_0$) has been studied. It is known that computing the exact Hamming distance between a pattern and a streaming text requires $Ω(n)$ space (folklore). Therefore, to develop sublinear-space solutions, one must relax their requirements. One possibility to do so is to compute only the distances bounded by a threshold $k$, see~[SODA'19, Clifford, Kociumaka, Porat] and references therein. The motivation for this variant of this problem is that we are interested in subwords of the text that are similar to the pattern, i.e. in subwords such that the distance between them and the pattern is relatively small. On the other hand, the main application of the streaming setting is processing large-scale data, such as biological data. Recent advances in hardware technology allow generating such data at a very high speed, but unfortunately, the produced data may contain about 10\% of noise~[Biol. Direct.'07, Klebanov and Yakovlev]. To analyse such data, it is not sufficient to consider small distances only. A possible workaround for this issue is the $(1\pm\varepsilon)$-approximation. This line of research was initiated in [ICALP'16, Clifford and Starikovskaya] who gave a $(1\pm\varepsilon)$-approximation algorithm with space~$\tilde{O}(\varepsilon^{-5}\sqrt{n})$. In this work, we show a suite of new streaming algorithms for computing the Hamming, $L_1$, $L_2$ and general $L_p$ ($0 < p < 2$) distances between the pattern and the text. Our results significantly extend over the previous result in this setting. In particular, for the Hamming distance and for the $L_p$ distance when $0 < p \le 1$ we show a streaming algorithm that uses $\tilde{O}(\varepsilon^{-2}\sqrt{n})$ space for polynomial-size alphabets.
Global Optimality Guarantees for Nonconvex Unsupervised Video Segmentation
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we consider the problem of unsupervised video object segmentation via background subtraction. Specifically, we pose the nonsemantic extraction of a video's moving objects as a nonconvex optimization problem via a sum of sparse and low-rank matrices. The resulting formulation, a nonnegative variant of robust principal component analysis, is more computationally tractable than its commonly employed convex relaxation, although not generally solvable to global optimality. In spite of this limitation, we derive intuitive and interpretable conditions on the video data under which the uniqueness and global optimality of the object segmentation are guaranteed using local search methods. We illustrate these novel optimality criteria through example segmentations using real video data.
Restoring Images with Unknown Degradation Factors by Recurrent Use of a Multi-branch Network
Venue: arXiv cs.CV 2020
Year: 2020

The employment of convolutional neural networks has achieved unprecedented performance in the task of image restoration for a variety of degradation factors. However, high-performance networks have been specifically designed for a single degradation factor. In this paper, we tackle a harder problem, restoring a clean image from its degraded version with an unknown degradation factor, subject to the condition that it is one of the known factors. Toward this end, we design a network having multiple pairs of input and output branches and use it in a recurrent fashion such that a different branch pair is used at each of the recurrent paths. We reinforce the shared part of the network with improved components so that it can handle different degradation factors. We also propose a two-step training method for the network, which consists of multi-task learning and finetuning. The experimental results show that the proposed network yields at least comparable or sometimes even better performance on four degradation factors as compared with the best dedicated network for each of the four. We also test it on a further harder task where the input image contains multiple degradation factors that are mixed with unknown mixture ratios, showing that it achieves better performance than the previous state-of-the-art method designed for the task.