OpenRaiser/Intern-Atlas huggingface dataset:
Acquiring Annotated Data with Cross-lingual Explicitation for Implicit Discourse Relation Classification
Venue: arXiv cs.CL 2019
Year: 2019

Implicit discourse relation classification is one of the most challenging and important tasks in discourse parsing, due to the lack of connective as strong linguistic cues. A principle bottleneck to further improvement is the shortage of training data (ca.~16k instances in the PDTB). Shi et al. (2017) proposed to acquire additional data by exploiting connectives in translation: human translators mark discourse relations which are implicit in the source language explicitly in the translation. Using back-translations of such explicitated connectives improves discourse relation parsing performance. This paper addresses the open question of whether the choice of the translation language matters, and whether multiple translations into different languages can be effectively used to improve the quality of the additional data.
The Data Complexity of Ontology-Mediated Queries with Closed Predicates
Venue: arXiv cs.LO 2019
Year: 2019

In the context of ontology-mediated querying with description logics (DLs), we study the data complexity of queries in which selected predicates can be closed (OMQCs). We provide a non-uniform analysis, aiming at a classification of the complexity into tractable and non-tractable for ontologies in the lightweight DLs DL-Lite and EL, and the expressive DL ALCHI. At the level of ontologies, we prove a dichotomy between FO-rewritable and coNP-complete for DL-Lite and between PTime and coNP-complete for EL. The meta problem of deciding tractability is proved to be in PTime. At the level of OMQCs, we show that there is no dichotomy (unless NP equals PTime) if both concept and role names can be closed. If only concept names can be closed, we tightly link the complexity of query evaluation to the complexity of surjective CSPs. We also identify a class of OMQCs based on ontologies formulated in DL-Lite that are guaranteed to be tractable and even FO-rewritable.
Hierarchically Learned View-Invariant Representations for Cross-View Action Recognition
Venue: arXiv cs.CV 2019
Year: 2019

Recognizing human actions from varied views is challenging due to huge appearance variations in different views. The key to this problem is to learn discriminant view-invariant representations generalizing well across views. In this paper, we address this problem by learning view-invariant representations hierarchically using a novel method, referred to as Joint Sparse Representation and Distribution Adaptation (JSRDA). To obtain robust and informative feature representations, we first incorporate a sample-affinity matrix into the marginalized stacked denoising Autoencoder (mSDA) to obtain shared features, which are then combined with the private features. In order to make the feature representations of videos across views transferable, we then learn a transferable dictionary pair simultaneously from pairs of videos taken at different views to encourage each action video across views to have the same sparse representation. However, the distribution difference across views still exists because a unified subspace where the sparse representations of one action across views are the same may not exist when the view difference is large. Therefore, we propose a novel unsupervised distribution adaptation method that learns a set of projections that project the source and target views data into respective low-dimensional subspaces where the marginal and conditional distribution differences are reduced simultaneously. Therefore, the finally learned feature representation is view-invariant and robust for substantial distribution difference across views even the view difference is large. Experimental results on four multiview datasets show that our approach outperforms the state-ofthe-art approaches.
Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes
Venue: arXiv cs.DS 2019
Year: 2019

Document exchange and error correcting codes are two fundamental problems regarding communications. In the first problem, Alice and Bob each holds a string, and the goal is for Alice to send a short sketch to Bob, so that Bob can recover Alice's string. In the second problem, Alice sends a message with some redundant information to Bob through a channel that can add adversarial errors, and the goal is for Bob to correctly recover the message despite the errors. In a recent work \cite{CJLW18}, the authors constructed explicit deterministic document exchange protocols and binary error correcting codes for edit errors with almost optimal parameters.\ Unfortunately, the constructions in \cite{CJLW18} do not work for other common errors such as block transpositions. In this paper, we generalize the constructions in \cite{CJLW18} to handle a much larger class of errors. These include bursts of insertions and deletions, as well as block transpositions. Specifically, we consider document exchange and error correcting codes where the total number of block insertions, block deletions, and block transpositions is at most $k \leq αn/\log n$ for some constant $0<α<1$. In addition, the total number of bits inserted and deleted by the first two kinds of operations is at most $t \leq βn$ for some constant $0<β<1$, where $n$ is the length of Alice's string or message. We construct explicit, deterministic document exchange protocols with sketch size $ O( (k \log n +t) \log^2 \frac{n}{k\log n + t} )$ and explicit binary error correcting code with $O(k \log n \log \log \log n+t)$ redundant bits.
Soft-PHOC Descriptor for End-to-End Word Spotting in Egocentric Scene Images
Venue: arXiv cs.CV 2019
Year: 2019

Word spotting in natural scene images has many applications in scene understanding and visual assistance. In this paper we propose a technique to create and exploit an intermediate representation of images based on text attributes which are character probability maps. Our representation extends the concept of the Pyramidal Histogram Of Characters (PHOC) by exploiting Fully Convolutional Networks to derive a pixel-wise mapping of the character distribution within candidate word regions. We call this representation the Soft-PHOC. Furthermore, we show how to use Soft-PHOC descriptors for word spotting tasks in egocentric camera streams through an efficient text line proposal algorithm. This is based on the Hough Transform over character attribute maps followed by scoring using Dynamic Time Warping (DTW). We evaluate our results on ICDAR 2015 Challenge 4 dataset of incidental scene text captured by an egocentric camera.
Graph Convolutional Neural Networks based on Quantum Vertex Saliency
Venue: arXiv cs.LG 2019
Year: 2019

This paper proposes a new Quantum Spatial Graph Convolutional Neural Network (QSGCNN) model that can directly learn a classification function for graphs of arbitrary sizes. Unlike state-of-the-art Graph Convolutional Neural Network (GCNN) models, the proposed QSGCNN model incorporates the process of identifying transitive aligned vertices between graphs, and transforms arbitrary sized graphs into fixed-sized aligned vertex grid structures. In order to learn representative graph characteristics, a new quantum spatial graph convolution is proposed and employed to extract multi-scale vertex features, in terms of quantum information propagation between grid vertices of each graph. Since the quantum spatial convolution preserves the grid structures of the input vertices (i.e., the convolution layer does not change the original spatial sequence of vertices), the proposed QSGCNN model allows to directly employ the traditional convolutional neural network architecture to further learn from the global graph topology, providing an end-to-end deep learning architecture that integrates the graph representation and learning in the quantum spatial graph convolution layer and the traditional convolutional layer for graph classifications. We demonstrate the effectiveness of the proposed QSGCNN model in relation to existing state-of-the-art methods. The proposed QSGCNN model addresses the shortcomings of information loss and imprecise information representation arising in existing GCN models associated with the use of SortPooling or SumPooling layers. Experiments on benchmark graph classification datasets demonstrate the effectiveness of the proposed QSGCNN model.
An Efficient Framework for Optimistic Concurrent Execution of Smart Contracts
Venue: arXiv cs.DC 2019
Year: 2019

Blockchain platforms such as Ethereum and several others execute complex transactions in blocks through user-defined scripts known as smart contracts. To append a correct block into blockchain, miners execute these transactions of smart contracts sequentially. Later the validators serially re-execute the smart contract transactions of the block to validate it. If validation is successful then the block is added to the blockchain using a consensus protocol and miner gets the incentive. In the current era of multi-core processors, by employing the serial execution of the transactions, the miners and validators fail to utilize the cores properly and as a result, have poor throughput. By entitling concurrency to smart contracts execution, we can achieve better efficiency and higher throughput. In this proposal, we develop a novel and efficient technique to execute the smart contract transactions concurrently by miner using optimistic Software Transactional Memory systems (STMs). The miner proposes a block which consists of the set of transactions, conflict graph, hash of previous block and final state of each shared data-objects. Later, we propose concurrent validator which re-executes the same smart contracts concurrently and deterministically with the help of conflict graph given by miner and verifies the final states. On successful validation, proposed block appended into the blockchain and miner gets the incentive. We consider a benchmarks from solidity documentation. We execute the smart contract transactions concurrently using Basic Time stamp Ordering (BTO) and Multi-Version Time stamp Ordering (MVTO) protocols as optimistic STMs. BTO and MVTO miner achieves 3.6x and 3.7x average speedups over serial miner respectively. BTO and MVTO validator outperform average 40.8x and 47.1x than serial validator respectively.
Consensus-Driven Propagation in Massive Unlabeled Data for Face Recognition
Venue: arXiv cs.CV 2019
Year: 2019

Face recognition has witnessed great progress in recent years, mainly attributed to the high-capacity model designed and the abundant labeled data collected. However, it becomes more and more prohibitive to scale up the current million-level identity annotations. In this work, we show that unlabeled face data can be as effective as the labeled ones. Here, we consider a setting closely mimicking the real-world scenario, where the unlabeled data are collected from unconstrained environments and their identities are exclusive from the labeled ones. Our main insight is that although the class information is not available, we can still faithfully approximate these semantic relationships by constructing a relational graph in a bottom-up manner. We propose Consensus-Driven Propagation (CDP) to tackle this challenging problem with two modules, the "committee" and the "mediator", which select positive face pairs robustly by carefully aggregating multi-view information. Extensive experiments validate the effectiveness of both modules to discard outliers and mine hard positives. With CDP, we achieve a compelling accuracy of 78.18% on MegaFace identification challenge by using only 9% of the labels, comparing to 61.78% when no unlabeled data are used and 78.52% when all labels are employed.
A Quantitative Approach to Understanding Online Antisemitism
Venue: arXiv cs.CY 2019
Year: 2019

A new wave of growing antisemitism, driven by fringe Web communities, is an increasingly worrying presence in the socio-political realm. The ubiquitous and global nature of the Web has provided tools used by these groups to spread their ideology to the rest of the Internet. Although the study of antisemitism and hate is not new, the scale and rate of change of online data has impacted the efficacy of traditional approaches to measure and understand these troubling trends. In this paper, we present a large-scale, quantitative study of online antisemitism. We collect hundreds of million posts and images from alt-right Web communities like 4chan's Politically Incorrect board (/pol/) and Gab. Using scientifically grounded methods, we quantify the escalation and spread of antisemitic memes and rhetoric across the Web. We find the frequency of antisemitic content greatly increases (in some cases more than doubling) after major political events such as the 2016 US Presidential Election and the "Unite the Right" rally in Charlottesville. We extract semantic embeddings from our corpus of posts and demonstrate how automated techniques can discover and categorize the use of antisemitic terminology. We additionally examine the prevalence and spread of the antisemitic "Happy Merchant" meme, and in particular how these fringe communities influence its propagation to more mainstream communities like Twitter and Reddit. Taken together, our results provide a data-driven, quantitative framework for understanding online antisemitism. Our methods serve as a framework to augment current qualitative efforts by anti-hate groups, providing new insights into the growth and spread of hate online.
Interpretable Visual Question Answering by Reasoning on Dependency Trees
Venue: arXiv cs.CV 2019
Year: 2019

Collaborative reasoning for understanding image-question pairs is a very critical but underexplored topic in interpretable visual question answering systems. Although very recent studies have attempted to use explicit compositional processes to assemble multiple subtasks embedded in questions, their models heavily rely on annotations or handcrafted rules to obtain valid reasoning processes, which leads to either heavy workloads or poor performance on compositional reasoning. In this paper, to better align image and language domains in diverse and unrestricted cases, we propose a novel neural network model that performs global reasoning on a dependency tree parsed from the question; thus, our model is called a parse-tree-guided reasoning network (PTGRN). This network consists of three collaborative modules: i) an attention module that exploits the local visual evidence of each word parsed from the question, ii) a gated residual composition module that composes the previously mined evidence, and iii) a parse-tree-guided propagation module that passes the mined evidence along the parse tree. Thus, PTGRN is capable of building an interpretable visual question answering (VQA) system that gradually derives image cues following question-driven parse-tree reasoning. Experiments on relational datasets demonstrate the superiority of PTGRN over current state-of-the-art VQA methods, and the visualization results highlight the explainable capability of our reasoning system.
Analyzing and improving maximal attainable accuracy in the communication hiding pipelined BiCGStab method
Venue: arXiv cs.NA 2019
Year: 2019

Pipelined Krylov subspace methods avoid communication latency by reducing the number of global synchronization bottlenecks and by hiding global communication behind useful computational work. In exact arithmetic pipelined Krylov subspace algorithms are equivalent to classic Krylov subspace methods and generate identical series of iterates. However, as a consequence of the reformulation of the algorithm to improve parallelism, pipelined methods may suffer from severely reduced attainable accuracy in a practical finite precision setting. This work presents a numerical stability analysis that describes and quantifies the impact of local rounding error propagation on the maximal attainable accuracy of the multi-term recurrences in the preconditioned pipelined BiCGStab method. Theoretical expressions for the gaps between the true and computed residual as well as other auxiliary variables used in the algorithm are derived, and the elementary dependencies between the gaps on the various recursively computed vector variables are analyzed. The norms of the corresponding propagation matrices and vectors provide insights in the possible amplification of local rounding errors throughout the algorithm. Stability of the pipelined BiCGStab method is compared numerically to that of pipelined CG on a symmetric benchmark problem. Furthermore, numerical evidence supporting the effectiveness of employing a residual replacement type strategy to improve the maximal attainable accuracy for the pipelined BiCGStab method is provided.
Sample-Efficient Imitation Learning via Generative Adversarial Nets
Venue: arXiv cs.LG 2019
Year: 2019

GAIL is a recent successful imitation learning architecture that exploits the adversarial training procedure introduced in GANs. Albeit successful at generating behaviours similar to those demonstrated to the agent, GAIL suffers from a high sample complexity in the number of interactions it has to carry out in the environment in order to achieve satisfactory performance. We dramatically shrink the amount of interactions with the environment necessary to learn well-behaved imitation policies, by up to several orders of magnitude. Our framework, operating in the model-free regime, exhibits a significant increase in sample-efficiency over previous methods by simultaneously a) learning a self-tuned adversarially-trained surrogate reward and b) leveraging an off-policy actor-critic architecture. We show that our approach is simple to implement and that the learned agents remain remarkably stable, as shown in our experiments that span a variety of continuous control tasks. Video visualisations available at: \url{https://youtu.be/-nCsqUJnRKU}.
Deep Learning for Generic Object Detection: A Survey
Venue: arXiv cs.CV 2019
Year: 2019

Object detection, one of the most fundamental and challenging problems in computer vision, seeks to locate object instances from a large number of predefined categories in natural images. Deep learning techniques have emerged as a powerful strategy for learning feature representations directly from data and have led to remarkable breakthroughs in the field of generic object detection. Given this period of rapid evolution, the goal of this paper is to provide a comprehensive survey of the recent achievements in this field brought about by deep learning techniques. More than 300 research contributions are included in this survey, covering many aspects of generic object detection: detection frameworks, object feature representation, object proposal generation, context modeling, training strategies, and evaluation metrics. We finish the survey by identifying promising directions for future research.
Hypergames and Cyber-Physical Security for Control Systems
Venue: arXiv cs.SY 2019
Year: 2019

The identification of the Stuxnet worm in 2010 provided a highly publicized example of a cyber attack used to damage an industrial control system physically. This raised public awareness about the possibility of similar attacks against other industrial targets -- including critical infrastructure. In this paper, we use hypergames to analyze how adversarial perturbations, like those used by Stuxnet, can be used to manipulate a system that employs optimal control. Hypergames form an extension of game theory that enables us to model strategic interactions where the players may have significantly different perceptions of the game(s) they are playing. Past work with hypergames has been limited to relatively simple interactions consisting of a small set of discrete choices for each player, but here, we apply hypergames to larger systems with continuous variables. We find that manipulating constraints can be a more effective attacker strategy than directly manipulating objective function parameters. Moreover, the attacker need not change the underlying system to carry out a successful attack -- it may be sufficient to deceive the defender controlling the system. It is possible to scale our approach up to even larger systems, but the ability to do so will depend on the characteristics of the system in question, and we identify several characteristics that will make those systems amenable to hypergame analysis.
Synesthesia: Detecting Screen Content via Remote Acoustic Side Channels
Venue: arXiv cs.CR 2019
Year: 2019

We show that subtle acoustic noises emanating from within computer screens can be used to detect the content displayed on the screens. This sound can be picked up by ordinary microphones built into webcams or screens, and is inadvertently transmitted to other parties, e.g., during a videoconference call or archived recordings. It can also be recorded by a smartphone or "smart speaker" placed on a desk next to the screen, or from as far as 10 meters away using a parabolic microphone. Empirically demonstrating various attack scenarios, we show how this channel can be used for real-time detection of on-screen text, or users' input into on-screen virtual keyboards. We also demonstrate how an attacker can analyze the audio received during video call (e.g., on Google Hangout) to infer whether the other side is browsing the web in lieu of watching the video call, and which web site is displayed on their screen.
Active Inverse Reward Design
Venue: arXiv cs.LG 2019
Year: 2019

Designers of AI agents often iterate on the reward function in a trial-and-error process until they get the desired behavior, but this only guarantees good behavior in the training environment. We propose structuring this process as a series of queries asking the user to compare between different reward functions. Thus we can actively select queries for maximum informativeness about the true reward. In contrast to approaches asking the designer for optimal behavior, this allows us to gather additional information by eliciting preferences between suboptimal behaviors. After each query, we need to update the posterior over the true reward function from observing the proxy reward function chosen by the designer. The recently proposed Inverse Reward Design (IRD) enables this. Our approach substantially outperforms IRD in test environments. In particular, it can query the designer about interpretable, linear reward functions and still infer non-linear ones.
Finite Satisfiability of Unary Negation Fragment with Transitivity
Venue: arXiv cs.LO 2019
Year: 2019

We show that the finite satisfiability problem for the unary negation fragment with arbitrary number of transitive relations is decidable and 2-ExpTime-complete. Our result actually holds for a more general setting in which one can require that some binary symbols are interpreted as arbitrary transitive relations, some as partial orders and some as equivalences. We also consider finite satisfiability of various extensions of our primary logic, in particular capturing the concepts of nominals and role hierarchies known from description logic. As the unary negation fragment can express unions of conjunctive queries our results have interesting implications for the problem of finite query answering, both in the classical scenario and in the description logics setting.