OpenRaiser/Intern-Atlas huggingface dataset:
A Simple LSTM model for Transition-based Dependency Parsing
Venue: arXiv cs.CL 2017
Year: 2017

We present a simple LSTM-based transition-based dependency parser. Our model is composed of a single LSTM hidden layer replacing the hidden layer in the usual feed-forward network architecture. We also propose a new initialization method that uses the pre-trained weights from a feed-forward neural network to initialize our LSTM-based model. We also show that using dropout on the input layer has a positive effect on performance. Our final parser achieves a 93.06% unlabeled and 91.01% labeled attachment score on the Penn Treebank. We additionally replace LSTMs with GRUs and Elman units in our model and explore the effectiveness of our initialization method on individual gates constituting all three types of RNN units.
Deep Learning for Medical Image Analysis
Venue: arXiv cs.CV 2017
Year: 2017

This report describes my research activities in the Hasso Plattner Institute and summarizes my Ph.D. plan and several novels, end-to-end trainable approaches for analyzing medical images using deep learning algorithm. In this report, as an example, we explore different novel methods based on deep learning for brain abnormality detection, recognition, and segmentation. This report prepared for the doctoral consortium in the AIME-2017 conference.
Verification of Programs via Intermediate Interpretation
Venue: arXiv cs.PL 2017
Year: 2017

We explore an approach to verification of programs via program transformation applied to an interpreter of a programming language. A specialization technique known as Turchin's supercompilation is used to specialize some interpreters with respect to the program models. We show that several safety properties of functional programs modeling a class of cache coherence protocols can be proved by a supercompiler and compare the results with our earlier work on direct verification via supercompilation not using intermediate interpretation. Our approach was in part inspired by an earlier work by E. De Angelis et al. (2014-2015) where verification via program transformation and intermediate interpretation was studied in the context of specialization of constraint logic programs.
LTE and Wi-Fi Coexistence in Unlicensed Spectrum with Application to Smart Grid: A Review
Venue: arXiv cs.NI 2017
Year: 2017

Long Term Evolution (LTE) is expanding its utilization in unlicensed band by deploying LTE Unlicensed (LTEU) and Licensed Assisted Access LTE (LTE-LAA) technology. Smart Grid can take the advantages of unlicensed bands for achieving two-way communication between smart meters and utility data centers by using LTE-U/LTE-LAA. However, both schemes must co-exist with the incumbent Wi-Fi system. In this paper, several co-existence schemes of Wi-Fi and LTE technology is comprehensively reviewed. The challenges of deploying LTE and Wi-Fi in the same band are clearly addressed based on the papers reviewed. Solution procedures and techniques to resolve the challenging issues are discussed in a short manner. The performance of various network architectures such as listenbefore- talk (LBT) based LTE, carrier sense multiple access with collision avoidance (CSMA/CA) based Wi-Fi is briefly compared. Finally, an attempt is made to implement these proposed LTEWi- Fi models in smart grid technology.
Pix2face: Direct 3D Face Model Estimation
Venue: arXiv cs.CV 2017
Year: 2017

An efficient, fully automatic method for 3D face shape and pose estimation in unconstrained 2D imagery is presented. The proposed method jointly estimates a dense set of 3D landmarks and facial geometry using a single pass of a modified version of the popular "U-Net" neural network architecture. Additionally, we propose a method for directly estimating a set of 3D Morphable Model (3DMM) parameters, using the estimated 3D landmarks and geometry as constraints in a simple linear system. Qualitative modeling results are presented, as well as quantitative evaluation of predicted 3D face landmarks in unconstrained video sequences.
Area Spectral Efficiency and Coverage for Mixed Duplexing Networks with Directional Transmissions
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we consider a system of small cells assuming full duplex (FD) capable base stations (BSs) and half duplex (HD) user equipment (UEs). We investigate a mixed duplexing cellular system composed of FD and HD cells, when BSs are using directional transmissions. A stochastic geometry based model of the proposed system is used to derive the coverage and area spectral efficiency (ASE) of both BSs and UEs. The effect of FD cells on the performance of the mixed system is presented under different degree of directionality at the BSs. We show that enabling directional transmissions at the BSs yields significant ASE and coverage gain in both downlink and uplink directions. With directional transmissions, the ASE increases rapidly with the number of FD cells while the drop in the coverage rate due to FD operations reduces significantly.
Verifying Security Policies in Multi-agent Workflows with Loops
Venue: arXiv cs.LO 2017
Year: 2017

We consider the automatic verification of information flow security policies of web-based workflows, such as conference submission systems like EasyChair. Our workflow description language allows for loops, non-deterministic choice, and an unbounded number of participating agents. The information flow policies are specified in a temporal logic for hyperproperties. We show that the verification problem can be reduced to the satisfiability of a formula of first-order linear-time temporal logic, and provide decidability results for relevant classes of workflows and specifications. We report on experimental results obtained with an implementation of our approach on a series of benchmarks.
Practical Attacks Against Graph-based Clustering
Venue: arXiv cs.CR 2017
Year: 2017

Graph modeling allows numerous security problems to be tackled in a general way, however, little work has been done to understand their ability to withstand adversarial attacks. We design and evaluate two novel graph attacks against a state-of-the-art network-level, graph-based detection system. Our work highlights areas in adversarial machine learning that have not yet been addressed, specifically: graph-based clustering techniques, and a global feature space where realistic attackers without perfect knowledge must be accounted for (by the defenders) in order to be practical. Even though less informed attackers can evade graph clustering with low cost, we show that some practical defenses are possible.
Adaptive SVM+: Learning with Privileged Information for Domain Adaptation
Venue: arXiv cs.CV 2017
Year: 2017

Incorporating additional knowledge in the learning process can be beneficial for several computer vision and machine learning tasks. Whether privileged information originates from a source domain that is adapted to a target domain, or as additional features available at training time only, using such privileged (i.e., auxiliary) information is of high importance as it improves the recognition performance and generalization. However, both primary and privileged information are rarely derived from the same distribution, which poses an additional challenge to the recognition task. To address these challenges, we present a novel learning paradigm that leverages privileged information in a domain adaptation setup to perform visual recognition tasks. The proposed framework, named Adaptive SVM+, combines the advantages of both the learning using privileged information (LUPI) paradigm and the domain adaptation framework, which are naturally embedded in the objective function of a regular SVM. We demonstrate the effectiveness of our approach on the publicly available Animals with Attributes and INTERACT datasets and report state-of-the-art results in both of them.
FirmUSB: Vetting USB Device Firmware using Domain Informed Symbolic Execution
Venue: arXiv cs.CR 2017
Year: 2017

The USB protocol has become ubiquitous, supporting devices from high-powered computing devices to small embedded devices and control systems. USB's greatest feature, its openness and expandability, is also its weakness, and attacks such as BadUSB exploit the unconstrained functionality afforded to these devices as a vector for compromise. Fundamentally, it is virtually impossible to know whether a USB device is benign or malicious. This work introduces FirmUSB, a USB-specific firmware analysis framework that uses domain knowledge of the USB protocol to examine firmware images and determine the activity that they can produce. Embedded USB devices use microcontrollers that have not been well studied by the binary analysis community, and our work demonstrates how lifters into popular intermediate representations for analysis can be built, as well as the challenges of doing so. We develop targeting algorithms and use domain knowledge to speed up these processes by a factor of 7 compared to unconstrained fully symbolic execution. We also successfully find malicious activity in embedded 8051 firmwares without the use of source code. Finally, we provide insights into the challenges of symbolic analysis on embedded architectures and provide guidance on improving tools to better handle this important class of devices.
Technical Report for "User-Centric Participatory Sensing: A Game Theoretic Analysis"
Venue: arXiv cs.GT 2017
Year: 2017

Participatory sensing (PS) is a novel and promising sensing network paradigm for achieving a flexible and scalable sensing coverage with a low deploying cost, by encouraging mobile users to participate and contribute their smartphones as sensors. In this work, we consider a general PS system model with location-dependent and time-sensitive tasks, which generalizes the existing models in the literature. We focus on the task scheduling in the user-centric PS system, where each participating user will make his individual task scheduling decision (including both the task selection and the task execution order) distributively. Specifically, we formulate the interaction of users as a strategic game called Task Scheduling Game (TSG) and perform a comprehensive game-theoretic analysis. First, we prove that the proposed TSG game is a potential game, which guarantees the existence of Nash equilibrium (NE). Then, we analyze the efficiency loss and the fairness index at the NE. Our analysis shows the efficiency at NE may increase or decrease with the number of users, depending on the level of competition. This implies that it is not always better to employ more users in the user-centric PS system, which is important for the system designer to determine the optimal number of users to be employed in a practical system.
The Complexity of Computing a Cardinality Repair for Functional Dependencies
Venue: arXiv cs.DB 2017
Year: 2017

For a relation that violates a set of functional dependencies, we consider the task of finding a maximum number of pairwise-consistent tuples, or what is known as a "cardinality repair." We present a polynomial-time algorithm that, for certain fixed relation schemas (with functional dependencies), computes a cardinality repair. Moreover, we prove that on any of the schemas not covered by the algorithm, finding a cardinality repair is, in fact, an NP-hard problem. In particular, we establish a dichotomy in the complexity of computing a cardinality repair, and we present an efficient algorithm to determine whether a given schema belongs to the positive side or the negative side of the dichotomy.
On Smooth Orthogonal and Octilinear Drawings: Relations, Complexity and Kandinsky Drawings
Venue: arXiv cs.DS 2017
Year: 2017

We study two variants of the well-known orthogonal drawing model: (i) the smooth orthogonal, and (ii) the octilinear. Both models form an extension of the orthogonal, by supporting one additional type of edge segments (circular arcs and diagonal segments, respectively). For planar graphs of max-degree 4, we analyze relationships between the graph classes that can be drawn bendless in the two models and we also prove NP-hardness for a restricted version of the bendless drawing problem for both models. For planar graphs of higher degree, we present an algorithm that produces bi-monotone smooth orthogonal drawings with at most two segments per edge, which also guarantees a linear number of edges with exactly one segment.
Fighting with the Sparsity of Synonymy Dictionaries
Venue: arXiv cs.CL 2017
Year: 2017

Graph-based synset induction methods, such as MaxMax and Watset, induce synsets by performing a global clustering of a synonymy graph. However, such methods are sensitive to the structure of the input synonymy graph: sparseness of the input dictionary can substantially reduce the quality of the extracted synsets. In this paper, we propose two different approaches designed to alleviate the incompleteness of the input dictionaries. The first one performs a pre-processing of the graph by adding missing edges, while the second one performs a post-processing by merging similar synset clusters. We evaluate these approaches on two datasets for the Russian language and discuss their impact on the performance of synset induction methods. Finally, we perform an extensive error analysis of each approach and discuss prominent alternative methods for coping with the problem of the sparsity of the synonymy dictionaries.
Planar Drawings of Fixed-Mobile Bigraphs
Venue: arXiv cs.CG 2017
Year: 2017

A fixed-mobile bigraph G is a bipartite graph such that the vertices of one partition set are given with fixed positions in the plane and the mobile vertices of the other part, together with the edges, must be added to the drawing. We assume that G is planar and study the problem of finding, for a given k >= 0, a planar poly-line drawing of G with at most k bends per edge. In the most general case, we show NP-hardness. For k=0 and under additional constraints on the positions of the fixed or mobile vertices, we either prove that the problem is polynomial-time solvable or prove that it belongs to NP. Finally, we present a polynomial-time testing algorithm for a certain type of "layered" 1-bend drawings.
Efficient Algorithms for Checking Fast Termination in VASS
Venue: arXiv cs.LO 2017
Year: 2017

Vector Addition Systems with States (VASS) consists of a finite state space equipped with d counters, where in each transition every counter is incremented, decremented, or left unchanged. VASS provide a fundamental model for analysis of concurrent processes, parametrized systems, and they are also used as abstract models for programs for bounds analysis. While termination is the basic liveness property that asks the qualitative question of whether a given model always terminates or not, the more general quantitative question asks for bounds on the number of steps to termination. In the realm of quantitative bounds a fundamental problem is to obtain asymptotic bounds on termination time. Large asymptotic bounds such as exponential or higher already suggest that either there is some error in modeling, or the model is not useful in practice. Hence we focus on polynomial asymptotic bounds for VASS. While some well-known approaches (e.g., lexicographic ranking functions) are neither sound nor complete with respect to polynomial bounds, other approaches only present sound methods for upper bounds. In this work our main contributions are as follows: First, for linear asymptotic bounds we present a sound and complete method for VASS, and moreover, our algorithm runs in polynomial time. Second, we classify VASS according the normals of the vectors of the cycles. We show that singularities in the normal are the key reason for asymptotic bounds such as exponential and non-elementary for VASS. In absence of singularities, we show that the asymptotic complexity bound is always polynomial and of the form $Θ(n^k)$, for some k $\leq$ d. We present an algorithm, with time complexity polynomial in the size of the VASS and exponential in dimension d, to compute the optimal k.
Disguised Face Identification (DFI) with Facial KeyPoints using Spatial Fusion Convolutional Network
Venue: arXiv cs.CV 2017
Year: 2017

Disguised face identification (DFI) is an extremely challenging problem due to the numerous variations that can be introduced using different disguises. This paper introduces a deep learning framework to first detect 14 facial key-points which are then utilized to perform disguised face identification. Since the training of deep learning architectures relies on large annotated datasets, two annotated facial key-points datasets are introduced. The effectiveness of the facial keypoint detection framework is presented for each keypoint. The superiority of the key-point detection framework is also demonstrated by a comparison with other deep networks. The effectiveness of classification performance is also demonstrated by comparison with the state-of-the-art face disguise classification methods.
Adversarial nets with perceptual losses for text-to-image synthesis
Venue: arXiv cs.CV 2017
Year: 2017

Recent approaches in generative adversarial networks (GANs) can automatically synthesize realistic images from descriptive text. Despite the overall fair quality, the generated images often expose visible flaws that lack structural definition for an object of interest. In this paper, we aim to extend state of the art for GAN-based text-to-image synthesis by improving perceptual quality of generated images. Differentiated from previous work, our synthetic image generator optimizes on perceptual loss functions that measure pixel, feature activation, and texture differences against a natural image. We present visually more compelling synthetic images of birds and flowers generated from text descriptions in comparison to some of the most prominent existing work.
Incorporating Feedback into Tree-based Anomaly Detection
Venue: arXiv cs.LG 2017
Year: 2017

Anomaly detectors are often used to produce a ranked list of statistical anomalies, which are examined by human analysts in order to extract the actual anomalies of interest. Unfortunately, in realworld applications, this process can be exceedingly difficult for the analyst since a large fraction of high-ranking anomalies are false positives and not interesting from the application perspective. In this paper, we aim to make the analyst's job easier by allowing for analyst feedback during the investigation process. Ideally, the feedback influences the ranking of the anomaly detector in a way that reduces the number of false positives that must be examined before discovering the anomalies of interest. In particular, we introduce a novel technique for incorporating simple binary feedback into tree-based anomaly detectors. We focus on the Isolation Forest algorithm as a representative tree-based anomaly detector, and show that we can significantly improve its performance by incorporating feedback, when compared with the baseline algorithm that does not incorporate feedback. Our technique is simple and scales well as the size of the data increases, which makes it suitable for interactive discovery of anomalies in large datasets.
On Upward Drawings of Trees on a Given Grid
Venue: arXiv cs.CG 2017
Year: 2017

Computing a minimum-area planar straight-line drawing of a graph is known to be NP-hard for planar graphs, even when restricted to outerplanar graphs. However, the complexity question is open for trees. Only a few hardness results are known for straight-line drawings of trees under various restrictions such as edge length or slope constraints. On the other hand, there exist polynomial-time algorithms for computing minimum-width (resp., minimum-height) upward drawings of trees, where the height (resp., width) is unbounded. In this paper we take a major step in understanding the complexity of the area minimization problem for strictly-upward drawings of trees, which is one of the most common styles for drawing rooted trees. We prove that given a rooted tree $T$ and a $W\times H$ grid, it is NP-hard to decide whether $T$ admits a strictly-upward (unordered) drawing in the given grid.
Differentiable cellular automata
Venue: arXiv cs.DM 2017
Year: 2017

We describe a class of cellular automata (CAs) that are end-to-end differentiable. DCAs interpolate the behavior of ordinary CAs through rules that act on distributions of states. The gradient of a DCA with respect to its parameters can be computed with an iterative propagation scheme that uses previously-computed gradients and values. Gradient-based optimization over DCAs could be used to find ordinary CAs with desired properties.
A Note on Plus-Contacts, Rectangular Duals, and Box-Orthogonal Drawings
Venue: arXiv cs.CG 2017
Year: 2017

A plus-contact representation of a planar graph $G$ is called $c$-balanced if for every plus shape $+_v$, the number of other plus shapes incident to each arm of $+_v$ is at most $ c Δ+O(1)$, where $Δ$ is the maximum degree of $G$. Although small values of $c$ have been achieved for a few subclasses of planar graphs (e.g., $2$- and $3$-trees), it is unknown whether $c$-balanced representations with $c<1$ exist for arbitrary planar graphs. In this paper we compute $(1/2)$-balanced plus-contact representations for all planar graphs that admit a rectangular dual. Our result implies that any graph with a rectangular dual has a 1-bend box-orthogonal drawings such that for each vertex $v$, the box representing $v$ is a square of side length $\frac{deg(v)}{2}+ O(1)$.
Optimal Dynamic Cloud Network Control
Venue: arXiv cs.NI 2017
Year: 2017

Distributed cloud networking enables the deployment of a wide range of services in the form of interconnected software functions instantiated over general purpose hardware at multiple cloud locations distributed throughout the network. We consider the problem of optimal service delivery over a distributed cloud network, in which nodes are equipped with both communication and computation resources. We address the design of distributed online solutions that drive flow processing and routing decisions, along with the associated allocation of cloud and network resources. For a given set of services, each described by a chain of service functions, we characterize the cloud network capacity region and design a family of dynamic cloud network control (DCNC) algorithms that stabilize the underlying queuing system, while achieving arbitrarily close to minimum cost with a tradeoff in network delay. The proposed DCNC algorithms make local decisions based on the online minimization of linear and quadratic metrics obtained from an upper bound on the Lyapunov drift-plus-penalty of the cloud network queuing system. Minimizing a quadratic vs. a linear metric is shown to improve the cost-delay tradeoff at the expense of increased computational complexity. Our algorithms are further enhanced with a shortest transmission-plus-processing distance bias that improves delay performance without compromising throughput or overall cloud network cost. We provide throughput and cost optimality guarantees, convergence time analysis, and extensive simulations in representative cloud network scenarios.
Matched disturbance rejection for energy-shaping controlled underactuated mechanical systems
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we present a method of applying integral action to enhance the robustness of energy shaping controllers for underactuated mechanical systems with matched disturbances. Previous works on this problem have required a number of technical assumptions to be satisfied, restricting the class of systems for which the proposed solution applies. The design proposed in this paper relaxes some of these technical assumptions.