OpenRaiser/Intern-Atlas huggingface dataset:
Causal Belief Decomposition for Planning with Sensing: Completeness Results and Practical Approximation
Venue: arXiv cs.AI 2019
Year: 2019

Belief tracking is a basic problem in planning with sensing. While the problem is intractable, it has been recently shown that for both deterministic and non-deterministic systems expressed in compact form, it can be done in time and space that are exponential in the problem width. The width measures the maximum number of state variables that are all relevant to a given precondition or goal. In this work, we extend this result both theoretically and practically. First, we introduce an alternative decomposition scheme and algorithm with the same time complexity but different completeness guarantees, whose space complexity is much smaller: exponential in the causal width of the problem that measures the number of state variables that are causally relevant to a given precondition, goal, or observable. Second, we introduce a fast, meaningful, and powerful approximation that trades completeness by speed, and is both time and space exponential in the problem causal width. It is then shown empirically that the algorithm combined with simple heuristics yields state-of-the-art real-time performance in domains with high widths but low causal widths such as Minesweeper, Battleship, and Wumpus.
Multi-agent Collaboration for Feasible Collaborative Behavior Construction and Evaluation
Venue: arXiv cs.RO 2019
Year: 2019

In the case of the two-person zero-sum stochastic game with a central controller, this paper proposes a best collaborative behavior search and selection algorithm based on reinforcement learning, in response to how to choose the best collaborative object and action for the central controller. In view of the existing multi-agent collaboration and confrontation reinforcement learning methods, the methods of traversing all actions in a certain state leads to the problem of long calculation time and unsafe policy exploration. This paper proposes to construct a feasible collaborative behavior set by using action space discretization, establishing models of both sides, model-based prediction and parallel search. Then, we use the deep q-learning method in reinforcement learning to train the scoring function to select the optimal collaboration behavior from the feasible collaborative behavior set. This method enables efficient and accurate calculation in an environment with strong confrontation, high dynamics and a large number of agents, which is verified by the RoboCup Small Size League robots passing collaboration.
Automatic Fact-guided Sentence Modification
Venue: arXiv cs.CL 2019
Year: 2019

Online encyclopediae like Wikipedia contain large amounts of text that need frequent corrections and updates. The new information may contradict existing content in encyclopediae. In this paper, we focus on rewriting such dynamically changing articles. This is a challenging constrained generation task, as the output must be consistent with the new information and fit into the rest of the existing document. To this end, we propose a two-step solution: (1) We identify and remove the contradicting components in a target text for a given claim, using a neutralizing stance model; (2) We expand the remaining text to be consistent with the given claim, using a novel two-encoder sequence-to-sequence model with copy attention. Applied to a Wikipedia fact update dataset, our method successfully generates updated sentences for new claims, achieving the highest SARI score. Furthermore, we demonstrate that generating synthetic data through such rewritten sentences can successfully augment the FEVER fact-checking training dataset, leading to a relative error reduction of 13%.
Automated design of error-resilient and hardware-efficient deep neural networks
Venue: arXiv cs.LG 2019
Year: 2019

Applying deep neural networks (DNNs) in mobile and safety-critical systems, such as autonomous vehicles, demands a reliable and efficient execution on hardware. Optimized dedicated hardware accelerators are being developed to achieve this. However, the design of efficient and reliable hardware has become increasingly difficult, due to the increased complexity of modern integrated circuit technology and its sensitivity against hardware faults, such as random bit-flips. It is thus desirable to exploit optimization potential for error resilience and efficiency also at the algorithmic side, e.g., by optimizing the architecture of the DNN. Since there are numerous design choices for the architecture of DNNs, with partially opposing effects on the preferred characteristics (such as small error rates at low latency), multi-objective optimization strategies are necessary. In this paper, we develop an evolutionary optimization technique for the automated design of hardware-optimized DNN architectures. For this purpose, we derive a set of easily computable objective functions, which enable the fast evaluation of DNN architectures with respect to their hardware efficiency and error resilience solely based on the network topology. We observe a strong correlation between predicted error resilience and actual measurements obtained from fault injection simulations. Furthermore, we analyze two different quantization schemes for efficient DNN computation and find significant differences regarding their effect on error resilience.
The Universal Decompositional Semantics Dataset and Decomp Toolkit
Venue: arXiv cs.CL 2019
Year: 2019

We present the Universal Decompositional Semantics (UDS) dataset (v1.0), which is bundled with the Decomp toolkit (v0.1). UDS1.0 unifies five high-quality, decompositional semantics-aligned annotation sets within a single semantic graph specification---with graph structures defined by the predicative patterns produced by the PredPatt tool and real-valued node and edge attributes constructed using sophisticated normalization procedures. The Decomp toolkit provides a suite of Python 3 tools for querying UDS graphs using SPARQL. Both UDS1.0 and Decomp0.1 are publicly available at http://decomp.io.
Cross Subspace Alignment Codes for Coded Distributed Batch Computation
Venue: arXiv cs.IT 2019
Year: 2019

Coded distributed batch computation distributes a computation task, such as matrix multiplication, $N$-linear computation, or multivariate polynomial evaluation, across $S$ servers through a coding scheme, such that the response from any $R$ servers ($R$ is called the recovery threshold) is sufficient for the user to recover the desired computed value. Current approaches are based on either exclusively matrix-partitioning (Entangled Polynomial (EP) Codes for matrix multiplication), or exclusively batch processing (Lagrange Coded Computing (LCC)). We present three related classes of codes, based on the idea of Cross-Subspace Alignment (CSA) which was introduced originally in the context of private information retrieval. CSA codes are characterized by a Cauchy-Vandermonde matrix structure that facilitates interference alignment along Vandermonde terms, while the desired computations remain resolvable along the Cauchy terms. These codes unify, generalize and improve upon the state-of-art codes for distributed computing. First we introduce CSA codes for matrix multiplication, which yield LCC codes as a special case, and are shown to outperform LCC codes in general over strictly download-limited settings. Next, we introduce Generalized CSA (GCSA) codes for matrix multiplication that bridge the extremes of matrix-partitioning and batch processing approaches. Finally, we introduce $N$-CSA codes for $N$-linear distributed batch computations and multivariate batch polynomial evaluations. $N$-CSA codes include LCC codes as a special case, and are in general capable of achieving significantly lower downloads than LCC codes due to cross-subspace alignment. Generalizations of $N$-CSA codes to include $X$-secure data and $B$-byzantine servers are also obtained.
Expressive Inverse Kinematics Solving in Real-time for Virtual and Robotic Interactive Characters
Venue: arXiv cs.RO 2019
Year: 2019

With new advancements in interaction techniques, character animation also requires new methods, to support fields such as robotics, and VR/AR. Interactive characters in such fields are becoming driven by AI which opens up the possibility of non-linear and open-ended narratives that may even include interaction with the real, physical world. This paper presents and describes ERIK, an expressive inverse kinematics technique aimed at such applications. Our technique allows an arbitrary kinematic chain, such as an arm, snake, or robotic manipulator, to exhibit an expressive posture while aiming its end-point towards a given target orientation. The technique runs in interactive-time and does not require any pre-processing step such as e.g. training in machine learning techniques, in order to support new embodiments or new postures. That allows it to be integrated in an artist-friendly workflow, bringing artists closer to the development of such AI-driven expressive characters, by allowing them to use their typical animation tools of choice, and to properly pre-visualize the animation during design-time, even on a real robot. The full algorithmic specification is presented and described so that it can be implemented and used throughout the communities of the various fields we address. We demonstrate ERIK on different virtual kinematic structures, and also on a low-fidelity robot that was crafted using wood and hobby-grade servos, to show how well the technique performs even on a low-grade robot. Our evaluation shows how well the technique performs, i.e., how well the character is able to point at the target orientation, while minimally disrupting its target expressive posture, and respecting its mechanical rotation limits.
FSPVDsse: A Forward Secure Publicly Verifiable Dynamic SSE scheme
Venue: arXiv cs.CR 2019
Year: 2019

A symmetric searchable encryption (SSE) scheme allows a client (data owner) to search on encrypted data outsourced to an untrusted cloud server. The search may either be a single keyword search or a complex query search like conjunctive or Boolean keyword search. Information leakage is quite high for dynamic SSE, where data might be updated. It has been proven that to avoid this information leakage an SSE scheme with dynamic data must be forward private. A dynamic SSE scheme is said to be forward private, if adding a keyword-document pair does not reveal any information about the previous search result with that keyword. In SSE setting, the data owner has very low computation and storage power. In this setting, though some schemes achieve forward privacy with honest-but-curious cloud, it becomes difficult to achieve forward privacy when the server is malicious, meaning that it can alter the data. Verifiable dynamic SSE requires the server to give a proof of the result of the search query. The data owner can verify this proof efficiently. In this paper, we have proposed a generic publicly verifiable dynamic SSE (DSSE) scheme that makes any forward private DSSE scheme verifiable without losing forward privacy. The proposed scheme does not require any extra storage at owner-side and requires minimal computational cost as well for the owner. Moreover, we have compared our scheme with the existing results and show that our scheme is practical.
Respect Your Emotion: Human-Multi-Robot Teaming based on Regret Decision Model
Venue: arXiv cs.AI 2019
Year: 2019

Often, when modeling human decision-making behaviors in the context of human-robot teaming, the emotion aspect of human is ignored. Nevertheless, the influence of emotion, in some cases, is not only undeniable but beneficial. This work studies the human-like characteristics brought by regret emotion in one-human-multi-robot teaming for the application of domain search. In such application, the task management load is outsourced to the robots to reduce the human's workload, freeing the human to do more important work. The regret decision model is first used by each robot for deciding whether to request human service, then is extended for optimally queuing the requests from multiple robots. For the movement of the robots in the domain search, we designed a path planning algorithm based on dynamic programming for each robot. The simulation shows that the human-like characteristics, namely, risk-seeking and risk-aversion, indeed bring some appealing effects for balancing the workload and performance in the human-multi-robot team.
Dynamics on Games: Simulation-Based Techniques and Applications to Routing
Venue: arXiv cs.GT 2019
Year: 2019

We consider multi-player games played on graphs, in which the players aim at fulfilling their own (not necessarily antagonistic) objectives. In the spirit of evolutionary game theory, we suppose that the players have the right to repeatedly update their respective strategies (for instance, to improve the outcome w.r.t. the current strategy profile). This generates a dynamics in the game which may eventually stabilise to an equilibrium. The objective of the present paper is twofold. First, we aim at drawing a general framework to reason about the termination of such dynamics. In particular, we identify preorders on games (inspired from the classical notion of simulation between transitions systems, and from the notion of graph minor) which preserve termination of dynamics. Second, we show the applicability of the previously developed framework to interdomain routing problems.
Custom Extended Sobel Filters
Venue: arXiv cs.CV 2019
Year: 2019

Edge detection is widely and fundamental feature used in various algorithms in computer vision to determine the edges in an image. The edge detection algorithm is used to determine the edges in an image which are further used by various algorithms from line detection to machine learning that can determine objects based on their contour. Inspired by new convolution techniques in machine learning we discuss here the idea of extending the standard Sobel kernels, which are used to compute the gradient of an image in order to find its edges. We compare the result of our custom extended filters with the results of the standard Sobel filter and other edge detection filters using different image sets and algorithms. We present statistical results regarding the custom extended Sobel filters improvements.
Analyzing Sentence Fusion in Abstractive Summarization
Venue: arXiv cs.CL 2019
Year: 2019

While recent work in abstractive summarization has resulted in higher scores in automatic metrics, there is little understanding on how these systems combine information taken from multiple document sentences. In this paper, we analyze the outputs of five state-of-the-art abstractive summarizers, focusing on summary sentences that are formed by sentence fusion. We ask assessors to judge the grammaticality, faithfulness, and method of fusion for summary sentences. Our analysis reveals that system sentences are mostly grammatical, but often fail to remain faithful to the original article.
Automatic Throughput and Critical Path Analysis of x86 and ARM Assembly Kernels
Venue: arXiv cs.PF 2019
Year: 2019

Useful models of loop kernel runtimes on out-of-order architectures require an analysis of the in-core performance behavior of instructions and their dependencies. While an instruction throughput prediction sets a lower bound to the kernel runtime, the critical path defines an upper bound. Such predictions are an essential part of analytic (i.e., white-box) performance models like the Roofline and Execution-Cache-Memory (ECM) models. They enable a better understanding of the performance-relevant interactions between hardware architecture and loop code. The Open Source Architecture Code Analyzer (OSACA) is a static analysis tool for predicting the execution time of sequential loops. It previously supported only x86 (Intel and AMD) architectures and simple, optimistic full-throughput execution. We have heavily extended OSACA to support ARM instructions and critical path prediction including the detection of loop-carried dependencies, which turns it into a versatile cross-architecture modeling tool. We show runtime predictions for code on Intel Cascade Lake, AMD Zen, and Marvell ThunderX2 micro-architectures based on machine models from available documentation and semi-automatic benchmarking. The predictions are compared with actual measurements.
Optimal Dyck Reachability for Data-Dependence and Alias Analysis
Venue: arXiv cs.PL 2019
Year: 2019

A fundamental algorithmic problem at the heart of static analysis is Dyck reachability. The input is a graph where the edges are labeled with different types of opening and closing parentheses, and the reachability information is computed via paths whose parentheses are properly matched. We present new results for Dyck reachability problems with applications to alias analysis and data-dependence analysis. Our main contributions, that include improved upper bounds as well as lower bounds that establish optimality guarantees, are as follows. First, we consider Dyck reachability on bidirected graphs, which is the standard way of performing field-sensitive points-to analysis. Given a bidirected graph with $n$ nodes and $m$ edges, we present: (i)~an algorithm with worst-case running time $O(m + n \cdot α(n))$, where $α(n)$ is the inverse Ackermann function, improving the previously known $O(n^2)$ time bound; (ii)~a matching lower bound that shows that our algorithm is optimal wrt to worst-case complexity; and (iii)~an optimal average-case upper bound of $O(m)$ time, improving the previously known $O(m \cdot \log n)$ bound. Second, we consider the problem of context-sensitive data-dependence analysis, where the task is to obtain analysis summaries of library code in the presence of callbacks. Our algorithm preprocesses libraries in almost linear time, after which the contribution of the library in the complexity of the client analysis is only linear, and only wrt the number of call sites. Third, we prove that combinatorial algorithms for Dyck reachability on general graphs with truly sub-cubic bounds cannot be obtained without obtaining sub-cubic combinatorial algorithms for Boolean Matrix Multiplication, which is a long-standing open problem. We also show that the same hardness holds for graphs of constant treewidth.
MTab: Matching Tabular Data to Knowledge Graph using Probability Models
Venue: arXiv cs.AI 2019
Year: 2019

This paper presents the design of our system, namely MTab, for Semantic Web Challenge on Tabular Data to Knowledge Graph Matching (SemTab 2019). MTab combines the voting algorithm and the probability models to solve critical problems of the matching tasks. Results on SemTab 2019 show that MTab obtains promising performance for the three matching tasks.
pylustrator: Code generation for reproducible figures for publication
Venue: arXiv cs.GR 2019
Year: 2019

One major challenge in science is to make all results potentially reproducible. Thus, along with the raw data, every step from basic processing of the data, evaluation, to the generation of the figures, has to be documented as clearly as possible. While there are many programming libraries that cover the basic processing and plotting steps (e.g. Matplotlib in Python), no library yet addresses the reproducible composing of single plots into meaningful figures for publication. Thus, up to now it is still state-of-the-art to generate publishable figures using image-processing or vector-drawing software leading to unwanted alterations of the presented data in the worst case and to figure quality reduction in the best case. Pylustrator a open source library based on the Matplotlib aims to fill this gap and provides a tool to easily generate the code necessary to compose publication figures from single plots. It provides a graphical user interface where the user can interactively compose the figures. All changes are tracked and converted to code that is automatically integrated into the calling script file. Thus, this software provides the missing link from raw data to the complete plot published in scientific journals and thus contributes to the transparency of the complete evaluation procedure.
When and Why is Document-level Context Useful in Neural Machine Translation?
Venue: arXiv cs.CL 2019
Year: 2019

Document-level context has received lots of attention for compensating neural machine translation (NMT) of isolated sentences. However, recent advances in document-level NMT focus on sophisticated integration of the context, explaining its improvement with only a few selected examples or targeted test sets. We extensively quantify the causes of improvements by a document-level model in general test sets, clarifying the limit of the usefulness of document-level context in NMT. We show that most of the improvements are not interpretable as utilizing the context. We also show that a minimal encoding is sufficient for the context modeling and very long context is not helpful for NMT.
Towards French Smart Building Code: Compliance Checking Based on Semantic Rules
Venue: arXiv cs.AI 2019
Year: 2019

Manually checking models for compliance against building regulation is a time-consuming task for architects and construction engineers. There is thus a need for algorithms that process information from construction projects and report non-compliant elements. Still automated code-compliance checking raises several obstacles. Building regulations are usually published as human readable texts and their content is often ambiguous or incomplete. Also, the vocabulary used for expressing such regulations is very different from the vocabularies used to express Building Information Models (BIM). Furthermore, the high level of details associated to BIM-contained geometries induces complex calculations. Finally, the level of complexity of the IFC standard also hinders the automation of IFC processing tasks. Model chart, formal rules and pre-processors approach allows translating construction regulations into semantic queries. We further demonstrate the usefulness of this approach through several use cases. We argue our approach is a step forward in bridging the gap between regulation texts and automated checking algorithms. Finally with the recent building ontology BOT recommended by the W3C Linked Building Data Community Group, we identify perspectives for standardizing and extending our approach.
Grammatical Error Correction in Low-Resource Scenarios
Venue: arXiv cs.CL 2019
Year: 2019

Grammatical error correction in English is a long studied problem with many existing systems and datasets. However, there has been only a limited research on error correction of other languages. In this paper, we present a new dataset AKCES-GEC on grammatical error correction for Czech. We then make experiments on Czech, German and Russian and show that when utilizing synthetic parallel corpus, Transformer neural machine translation model can reach new state-of-the-art results on these datasets. AKCES-GEC is published under CC BY-NC-SA 4.0 license at https://hdl.handle.net/11234/1-3057 and the source code of the GEC model is available at https://github.com/ufal/low-resource-gec-wnut2019.
Application of Low-resource Machine Translation Techniques to Russian-Tatar Language Pair
Venue: arXiv cs.CL 2019
Year: 2019

Neural machine translation is the current state-of-the-art in machine translation. Although it is successful in a resource-rich setting, its applicability for low-resource language pairs is still debatable. In this paper, we explore the effect of different techniques to improve machine translation quality when a parallel corpus is as small as 324 000 sentences, taking as an example previously unexplored Russian-Tatar language pair. We apply such techniques as transfer learning and semi-supervised learning to the base Transformer model, and empirically show that the resulting models improve Russian to Tatar and Tatar to Russian translation quality by +2.57 and +3.66 BLEU, respectively.