OpenRaiser/Intern-Atlas huggingface dataset:
Constrained Existence Problem for Weak Subgame Perfect Equilibria with $ω$-Regular Boolean Objectives
Venue: arXiv cs.GT 2018
Year: 2018

We study multiplayer turn-based games played on a finite directed graph such that each player aims at satisfying an omega-regular Boolean objective. Instead of the well-known notions of Nash equilibrium (NE) and subgame perfect equilibrium (SPE), we focus on the recent notion of weak subgame perfect equilibrium (weak SPE), a refinement of SPE. In this setting, players who deviate can only use the subclass of strategies that differ from the original one on a finite number of histories. We are interested in the constrained existence problem for weak SPEs. We provide a complete characterization of the computational complexity of this problem: it is P-complete for Explicit Muller objectives, NP-complete for Co-Büchi, Parity, Muller, Rabin, and Streett objectives, and PSPACE-complete for Reachability and Safety objectives (we only prove NP-membership for Büchi objectives). We also show that the constrained existence problem is fixed parameter tractable and is polynomial when the number of players is fixed. All these results are based on a fine analysis of a fixpoint algorithm that computes the set of possible payoff profiles underlying weak SPEs.
The Power of the Weak
Venue: arXiv cs.LO 2018
Year: 2018

A landmark result in the study of logics for formal verification is Janin & Walukiewicz's theorem, stating that the modal $μ$-calculus ($μ\mathrm{ML}$) is equivalent modulo bisimilarity to standard monadic second-order logic (here abbreviated as $\mathrm{smso}$), over the class of labelled transition systems (LTSs for short). Our work proves two results of the same kind, one for the alternation-free fragment of $μ\mathrm{ML}$ ($μ_D\mathrm{ML}$) and one for weak $\mathrm{mso}$ ($\mathrm{wmso}$). Whereas it was known that $μ_D\mathrm{ML}$ and $\mathrm{wmso}$ are equivalent modulo bisimilarity on binary trees, our analysis shows that the picture radically changes once we reason over arbitrary LTSs. The first theorem that we prove is that, over LTSs, $μ_D\mathrm{ML}$ is equivalent modulo bisimilarity to noetherian $\mathrm{mso}$ ($\mathrm{nmso}$), a newly introduced variant of $\mathrm{smso}$ where second-order quantification ranges over "well-founded" subsets only. Our second theorem starts from $\mathrm{wmso}$, and proves it equivalent modulo bisimilarity to a fragment of $μ_D\mathrm{ML}$ defined by a notion of continuity. Analogously to Janin & Walukiewicz's result, our proofs are automata-theoretic in nature: as another contribution, we introduce classes of parity automata characterising the expressiveness of $\mathrm{wmso}$ and $\mathrm{nmso}$ (on tree models) and of $μ_C\mathrm{ML}$ and $μ_D\mathrm{ML}$ (for all transition systems).
Multidevice mobile sessions: A first look
Venue: arXiv cs.HC 2018
Year: 2018

The increasing number of users with multiple mobile devices underscores the importance of understanding how users interact, often simultaneously, with these multiple devices. However, most device based monitoring studies have focused only on a single device type. In contrast, we study the multidevice usage of a US-based panel through device based monitoring on panelist's smartphone and tablet devices. We present a broad range of results from characterizing individual multidevice sessions to estimating device usage substitution. For example, we find that for panelists, 50% of all device interaction time can be considered multidevice usage.
Abstraction Learning
Venue: arXiv cs.AI 2018
Year: 2018

There has been a gap between artificial intelligence and human intelligence. In this paper, we identify three key elements forming human intelligence, and suggest that abstraction learning combines these elements and is thus a way to bridge the gap. Prior researches in artificial intelligence either specify abstraction by human experts, or take abstraction as a qualitative explanation for the model. This paper aims to learn abstraction directly. We tackle three main challenges: representation, objective function, and learning algorithm. Specifically, we propose a partition structure that contains pre-allocated abstraction neurons; we formulate abstraction learning as a constrained optimization problem, which integrates abstraction properties; we develop a network evolution algorithm to solve this problem. This complete framework is named ONE (Optimization via Network Evolution). In our experiments on MNIST, ONE shows elementary human-like intelligence, including low energy consumption, knowledge sharing, and lifelong learning.
Toward Automated Early Sepsis Alerting: Identifying Infection Patients from Nursing Notes
Venue: arXiv cs.CY 2018
Year: 2018

Severe sepsis and septic shock are conditions that affect millions of patients and have close to 50% mortality rate. Early identification of at-risk patients significantly improves outcomes. Electronic surveillance tools have been developed to monitor structured Electronic Medical Records and automatically recognize early signs of sepsis. However, many sepsis risk factors (e.g. symptoms and signs of infection) are often captured only in free text clinical notes. In this study, we developed a method for automatic monitoring of nursing notes for signs and symptoms of infection. We utilized a creative approach to automatically generate an annotated dataset. The dataset was used to create a Machine Learning model that achieved an F1-score ranging from 79 to 96%.
Maximally Consistent Sampling and the Jaccard Index of Probability Distributions
Venue: arXiv cs.DS 2018
Year: 2018

We introduce simple, efficient algorithms for computing a MinHash of a probability distribution, suitable for both sparse and dense data, with equivalent running times to the state of the art for both cases. The collision probability of these algorithms is a new measure of the similarity of positive vectors which we investigate in detail. We describe the sense in which this collision probability is optimal for any Locality Sensitive Hash based on sampling. We argue that this similarity measure is more useful for probability distributions than the similarity pursued by other algorithms for weighted MinHash, and is the natural generalization of the Jaccard index.
Parallel Separable 3D Convolution for Video and Volumetric Data Understanding
Venue: arXiv cs.CV 2018
Year: 2018

For video and volumetric data understanding, 3D convolution layers are widely used in deep learning, however, at the cost of increasing computation and training time. Recent works seek to replace the 3D convolution layer with convolution blocks, e.g. structured combinations of 2D and 1D convolution layers. In this paper, we propose a novel convolution block, Parallel Separable 3D Convolution (PmSCn), which applies m parallel streams of n 2D and one 1D convolution layers along different dimensions. We first mathematically justify the need of parallel streams (Pm) to replace a single 3D convolution layer through tensor decomposition. Then we jointly replace consecutive 3D convolution layers, common in modern network architectures, with the multiple 2D convolution layers (Cn). Lastly, we empirically show that PmSCn is applicable to different backbone architectures, such as ResNet, DenseNet, and UNet, for different applications, such as video action recognition, MRI brain segmentation, and electron microscopy segmentation. In all three applications, we replace the 3D convolution layers in state-of-the art models with PmSCn and achieve around 14% improvement in test performance and 40% reduction in model size and on average.
End-to-end Image Captioning Exploits Multimodal Distributional Similarity
Venue: arXiv cs.CV 2018
Year: 2018

We hypothesize that end-to-end neural image captioning systems work seemingly well because they exploit and learn `distributional similarity' in a multimodal feature space by mapping a test image to similar training images in this space and generating a caption from the same space. To validate our hypothesis, we focus on the `image' side of image captioning, and vary the input image representation but keep the RNN text generation component of a CNN-RNN model constant. Our analysis indicates that image captioning models (i) are capable of separating structure from noisy input representations; (ii) suffer virtually no significant performance loss when a high dimensional representation is compressed to a lower dimensional space; (iii) cluster images with similar visual and linguistic information together. Our findings indicate that our distributional similarity hypothesis holds. We conclude that regardless of the image representation used image captioning systems seem to match images and generate captions in a learned joint image-text semantic subspace.
Intensity and Rescale Invariant Copy Move Forgery Detection Techniques
Venue: arXiv cs.CV 2018
Year: 2018

In this contemporary world digital media such as videos and images behave as an active medium to carry valuable information across the globe on all fronts. However there are several techniques evolved to tamper the image which has made their authenticity untrustworthy. CopyMove Forgery CMF is one of the most common forgeries present in an image where a cluster of pixels are duplicated in the same image with potential postprocessing techniques. Various state-of-art techniques are developed in the recent years which are effective in detecting passive image forgery. However most methods do fail when the copied image is rescaled or added with certain intensity before being pasted due to de-synchronization of pixels in the searching process. To tackle this problem the paper proposes distinct novel algorithms which recognize a unique approach of using Hus invariant moments and Discreet Cosine Transformations DCT to attain the desired rescale invariant and intensity invariant CMF detection techniques respectively. The experiments conducted quantitatively and qualitatively demonstrate the effectiveness of the algorithm.
Heated-Up Softmax Embedding
Venue: arXiv cs.LG 2018
Year: 2018

Metric learning aims at learning a distance which is consistent with the semantic meaning of the samples. The problem is generally solved by learning an embedding for each sample such that the embeddings of samples of the same category are compact while the embeddings of samples of different categories are spread-out in the feature space. We study the features extracted from the second last layer of a deep neural network based classifier trained with the cross entropy loss on top of the softmax layer. We show that training classifiers with different temperature values of softmax function leads to features with different levels of compactness. Leveraging these insights, we propose a "heating-up" strategy to train a classifier with increasing temperatures, leading the corresponding embeddings to achieve state-of-the-art performance on a variety of metric learning benchmarks.
What can linguistics and deep learning contribute to each other?
Venue: arXiv cs.CL 2018
Year: 2018

Joe Pater's target article calls for greater interaction between neural network research and linguistics. I expand on this call and show how such interaction can benefit both fields. Linguists can contribute to research on neural networks for language technologies by clearly delineating the linguistic capabilities that can be expected of such systems, and by constructing controlled experimental paradigms that can determine whether those desiderata have been met. In the other direction, neural networks can benefit the scientific study of language by providing infrastructure for modeling human sentence processing and for evaluating the necessity of particular innate constraints on language acquisition.
Fourier-Domain Optimization for Image Processing
Venue: arXiv cs.CV 2018
Year: 2018

Image optimization problems encompass many applications such as spectral fusion, deblurring, deconvolution, dehazing, matting, reflection removal and image interpolation, among others. With current image sizes in the order of megabytes, it is extremely expensive to run conventional algorithms such as gradient descent, making them unfavorable especially when closed-form solutions can be derived and computed efficiently. This paper explains in detail the framework for solving convex image optimization and deconvolution in the Fourier domain. We begin by explaining the mathematical background and motivating why the presented setups can be transformed and solved very efficiently in the Fourier domain. We also show how to practically use these solutions, by providing the corresponding implementations. The explanations are aimed at a broad audience with minimal knowledge of convolution and image optimization. The eager reader can jump to Section 3 for a footprint of how to solve and implement a sample optimization function, and Section 5 for the more complex cases.
Attention based visual analysis for fast grasp planning with multi-fingered robotic hand
Venue: arXiv cs.RO 2018
Year: 2018

We present an attention based visual analysis framework to compute grasp-relevant information in order to guide grasp planning using a multi-fingered robotic hand. Our approach uses a computational visual attention model to locate regions of interest in a scene, and uses a deep convolutional neural network to detect grasp type and point for a sub-region of the object presented in a region of interest. We demonstrate the proposed framework in object grasping tasks, in which the information generated from the proposed framework is used as prior information to guide the grasp planning. Results show that the proposed framework can not only speed up grasp planning with more stable configurations, but also is able to handle unknown objects. Furthermore, our framework can handle cluttered scenarios. A new Grasp Type Dataset (GTD) that considers 6 commonly used grasp types and covers 12 household objects is also presented.
Efficiency and detectability of random reactive jamming in carrier sense wireless networks
Venue: arXiv cs.IT 2018
Year: 2018

A natural basis for the detection of a wireless random reactive jammer (RRJ) is the perceived violation by the detector (typically located at the access point (AP)) of the carrier sensing protocol underpinning many wireless random access protocols (e.g., WiFi). Specifically, when the wireless medium is perceived by a station to be busy, a carrier sensing compliant station will avoid transmission while a RRJ station will often initiate transmission. However, hidden terminals (HTs), i.e., activity detected by the AP but not by the sensing station, complicate the use of carrier sensing as the basis for RRJ detection since they provide plausible deniability to a station suspected of being an RRJ. The RRJ has the dual objectives of avoiding detection and effectively disrupting communication, but there is an inherent performance tradeoff between these two objectives. In this paper we capture the behavior of both the RRJ and the compliant stations via a parsimonious Markov chain model, and pose the detection problem using the framework of Markov chain hypothesis testing. Our analysis yields the receiver operating characteristic of the detector, and the optimized behavior of the RRJ. While there has been extensive work in the literature on jamming detection, our innovation lies in leveraging carrier sensing as a natural and effective basis for detection.
CATCH-919 Hand: Design of a 9-actuator 19-DOF Anthropomorphic Robotic Hand
Venue: arXiv cs.RO 2018
Year: 2018

To achieve human-like dexterity for anthropomorphic robotic hands, it is essential to understand the biomechanics and control strategies of the human hand, in order to reduce the number of actuators being used without loosing hand flexibility. To this end, in this article, we propose a new interpretation about the working mechanism of the metacarpal (MCP) joint's extension and the underlying control strategies of the human hand, based on which we further propose a highly flexible finger design to achieve independent movements of interphalangeal (IP) joints and MCP joint. Besides, we consider the hyperextension of fingertip into our design which helps robotic finger present compliant and adaptive posture for touching and pinching. In addition, human thumb muscle functions are reconstructed in the proposed robotic hand design, by replacing 9 human muscle tendons with 3 cables in the proposed task-oriented design, realizing all 33 static and stable grasping postures. Videos are available at https://sites.google.com/view/szwd
Chinese Poetry Generation with a Salient-Clue Mechanism
Venue: arXiv cs.AI 2018
Year: 2018

As a precious part of the human cultural heritage, Chinese poetry has influenced people for generations. Automatic poetry composition is a challenge for AI. In recent years, significant progress has been made in this area benefiting from the development of neural networks. However, the coherence in meaning, theme or even artistic conception for a generated poem as a whole still remains a big problem. In this paper, we propose a novel Salient-Clue mechanism for Chinese poetry generation. Different from previous work which tried to exploit all the context information, our model selects the most salient characters automatically from each so-far generated line to gradually form a salient clue, which is utilized to guide successive poem generation process so as to eliminate interruptions and improve coherence. Besides, our model can be flexibly extended to control the generated poem in different aspects, for example, poetry style, which further enhances the coherence. Experimental results show that our model is very effective, outperforming three strong baselines.
Neural Melody Composition from Lyrics
Venue: arXiv cs.CL 2018
Year: 2018

In this paper, we study a novel task that learns to compose music from natural language. Given the lyrics as input, we propose a melody composition model that generates lyrics-conditional melody as well as the exact alignment between the generated melody and the given lyrics simultaneously. More specifically, we develop the melody composition model based on the sequence-to-sequence framework. It consists of two neural encoders to encode the current lyrics and the context melody respectively, and a hierarchical decoder to jointly produce musical notes and the corresponding alignment. Experimental results on lyrics-melody pairs of 18,451 pop songs demonstrate the effectiveness of our proposed methods. In addition, we apply a singing voice synthesizer software to synthesize the "singing" of the lyrics and melodies for human evaluation. Results indicate that our generated melodies are more melodious and tuneful compared with the baseline method.
Artificial Intelligence for the Public Sector: Opportunities and challenges of cross-sector collaboration
Venue: arXiv cs.AI 2018
Year: 2018

Public sector organisations are increasingly interested in using data science and artificial intelligence capabilities to deliver policy and generate efficiencies in high uncertainty environments. The long-term success of data science and AI in the public sector relies on effectively embedding it into delivery solutions for policy implementation. However, governments cannot do this integration of AI into public service delivery on their own. The UK Government Industrial Strategy is clear that delivering on the AI grand challenge requires collaboration between universities and public and private sectors. This cross-sectoral collaborative approach is the norm in applied AI centres of excellence around the world. Despite their popularity, cross-sector collaborations entail serious management challenges that hinder their success. In this article we discuss the opportunities and challenges from AI for public sector. Finally, we propose a series of strategies to successfully manage these cross-sectoral collaborations.
Dynamic logic assigned to automata
Venue: arXiv cs.LO 2018
Year: 2018

A dynamic logic ${\mathbf B}$ can be assigned to every automaton ${\mathcal A}$ without regard if ${\mathcal A}$ is deterministic or nondeterministic. This logic enables us to formulate observations on ${\mathcal A}$ in the form of composed propositions and, due to a transition functor $T$, it captures the dynamic behaviour of ${\mathcal A}$. There are formulated conditions under which the automaton ${\mathcal A}$ can be recovered by means of ${\mathbf B}$ and $T$.
Arbitrarily Varying Remote Sources
Venue: arXiv cs.IT 2018
Year: 2018

We study a lossy source coding problem for an arbitrarily varying remote source (AVRS) which was proposed in a prior work. An AVRS transmits symbols, each generated in an independent and identically distributed manner, which are sought to be estimated at the decoder. These symbols are remotely generated, and the encoder and decoder observe noise corrupted versions received through a two-output noisy channel. This channel is an arbitrarily varying channel controlled by a jamming adversary. We assume that the adversary knows the coding scheme as well as the source data non-causally, and hence, can employ malicious jamming strategies correlated to them. Our interest lies in studying the rate distortion function for codes with a stochastic encoder, i.e, when the encoder can privately randomize while the decoder is deterministic. We provide upper and lower bounds on this rate distortion function.
The Visual QA Devil in the Details: The Impact of Early Fusion and Batch Norm on CLEVR
Venue: arXiv cs.CV 2018
Year: 2018

Visual QA is a pivotal challenge for higher-level reasoning, requiring understanding language, vision, and relationships between many objects in a scene. Although datasets like CLEVR are designed to be unsolvable without such complex relational reasoning, some surprisingly simple feed-forward, "holistic" models have recently shown strong performance on this dataset. These models lack any kind of explicit iterative, symbolic reasoning procedure, which are hypothesized to be necessary for counting objects, narrowing down the set of relevant objects based on several attributes, etc. The reason for this strong performance is poorly understood. Hence, our work analyzes such models, and finds that minor architectural elements are crucial to performance. In particular, we find that \textit{early fusion} of language and vision provides large performance improvements. This contrasts with the late fusion approaches popular at the dawn of Visual QA. We propose a simple module we call Multimodal Core, which we hypothesize performs the fundamental operations for multimodal tasks. We believe that understanding why these elements are so important to complex question answering will aid the design of better-performing algorithms for Visual QA while minimizing hand-engineering effort.
Dynamic Edge Caching with Popularity Drifting
Venue: arXiv cs.IT 2018
Year: 2018

Caching at the network edge devices such as wireless caching stations (WCS) is a key technology in the 5G network. The spatial-temporal diversity of content popularity requires different content to be cached in different WCSs and periodically updated to adapt to temporal changes. In this paper, we study how the popularity drifting speed affects the number of required broadcast transmissions by the MBS and then design coded transmission schemes by leveraging the broadcast advantage under the index coding framework. The key idea is that files already cached in WCSs, which although may be currently unpopular, can serve as side information to facilitate coded broadcast transmission for cache updating. Our algorithm extends existing index coding-based schemes from a single-request scenario to a multiple-request scenario via a "dynamic coloring" approach. Simulation results indicate that a significant bandwidth saving can be achieved by adopting our scheme.