OpenRaiser/Intern-Atlas huggingface dataset:
A Formal Approach to Cyber-Physical Attacks
Venue: arXiv cs.CR 2017
Year: 2017

We apply formal methods to lay and streamline theoretical foundations to reason about Cyber-Physical Systems (CPSs) and cyber-physical attacks. We focus on %a formal treatment of both integrity and DoS attacks to sensors and actuators of CPSs, and on the timing aspects of these attacks. Our contributions are threefold: (1) we define a hybrid process calculus to model both CPSs and cyber-physical attacks; (2) we define a threat model of cyber-physical attacks and provide the means to assess attack tolerance/vulnerability with respect to a given attack; (3) we formalise how to estimate the impact of a successful attack on a CPS and investigate possible quantifications of the success chances of an attack. We illustrate definitions and results by means of a non-trivial engineering application.
UMDFaces: An Annotated Face Dataset for Training Deep Networks
Venue: arXiv cs.CV 2017
Year: 2017

Recent progress in face detection (including keypoint detection), and recognition is mainly being driven by (i) deeper convolutional neural network architectures, and (ii) larger datasets. However, most of the large datasets are maintained by private companies and are not publicly available. The academic computer vision community needs larger and more varied datasets to make further progress. In this paper we introduce a new face dataset, called UMDFaces, which has 367,888 annotated faces of 8,277 subjects. We also introduce a new face recognition evaluation protocol which will help advance the state-of-the-art in this area. We discuss how a large dataset can be collected and annotated using human annotators and deep networks. We provide human curated bounding boxes for faces. We also provide estimated pose (roll, pitch and yaw), locations of twenty-one key-points and gender information generated by a pre-trained neural network. In addition, the quality of keypoint annotations has been verified by humans for about 115,000 images. Finally, we compare the quality of the dataset with other publicly available face datasets at similar scales.
Alternating Direction Method of Multipliers for Sparse Convolutional Neural Networks
Venue: arXiv cs.NE 2017
Year: 2017

The storage and computation requirements of Convolutional Neural Networks (CNNs) can be prohibitive for exploiting these models over low-power or embedded devices. This paper reduces the computational complexity of the CNNs by minimizing an objective function, including the recognition loss that is augmented with a sparsity-promoting penalty term. The sparsity structure of the network is identified using the Alternating Direction Method of Multipliers (ADMM), which is widely used in large optimization problems. This method alternates between promoting the sparsity of the network and optimizing the recognition performance, which allows us to exploit the two-part structure of the corresponding objective functions. In particular, we take advantage of the separability of the sparsity-inducing penalty functions to decompose the minimization problem into sub-problems that can be solved sequentially. Applying our method to a variety of state-of-the-art CNN models, our proposed method is able to simplify the original model, generating models with less computation and fewer parameters, while maintaining and often improving generalization performance. Accomplishments on a variety of models strongly verify that our proposed ADMM-based method can be a very useful tool for simplifying and improving deep CNNs.
Combining policy gradient and Q-learning
Venue: arXiv cs.LG 2017
Year: 2017

Policy gradient is an efficient technique for improving a policy in a reinforcement learning setting. However, vanilla online variants are on-policy only and not able to take advantage of off-policy data. In this paper we describe a new technique that combines policy gradient with off-policy Q-learning, drawing experience from a replay buffer. This is motivated by making a connection between the fixed points of the regularized policy gradient algorithm and the Q-values. This connection allows us to estimate the Q-values from the action preferences of the policy, to which we apply Q-learning updates. We refer to the new technique as 'PGQL', for policy gradient and Q-learning. We also establish an equivalency between action-value fitting techniques and actor-critic algorithms, showing that regularized policy gradient techniques can be interpreted as advantage function learning algorithms. We conclude with some numerical examples that demonstrate improved data efficiency and stability of PGQL. In particular, we tested PGQL on the full suite of Atari games and achieved performance exceeding that of both asynchronous advantage actor-critic (A3C) and Q-learning.
On the optimal feedforward torque control problem of anisotropic synchronous machines: Quadrics, quartics and analytical solutions
Venue: arXiv cs.SY 2017
Year: 2017

The optimal feedforward torque control problem is tackled and solved analytically for synchronous machines while stator resistance and cross-coupling inductance are explicitly considered. Analytical solutions for the direct and quadrature optimal reference currents are found for all major operation strategies such as Maximum Torque per Current (MTPC) (or often called as Maximum Torque per Ampere (MTPA)), Maximum Current (MC), Field Weakening (FW), Maximum Torque per Voltage (MTPV) and Maximum Torque per Flux (MTPF). Numerical methods (approximating the optimal solutions only) or simplifying assumptions (neglecting stator resistance and/or cross-coupling inductance) are no longer necessary. The presented results are based on one simple idea: all optimization problems (e.g. MTPC, MTPV or MTPF) with their respective constraints (e.g. current or voltage limit) and the computation of the intersection point(s) of voltage ellipse, current circle, or torque, MTPC, MTPV and MTPF hyperbolas are reformulated implicitly as quadrics (quadratic surfaces) which allow to solve the feedforward torque control problem by invoking the Lagrangian formalism and by finding the roots of a fourth-order polynomial analytically. The proposed solutions are applicable to any anisotropic (or isotropic) synchronous machine independent of the underlying current control strategy.
Robust Distance-Based Formation Control of Multiple Rigid Bodies with Orientation Alignment
Venue: arXiv cs.SY 2017
Year: 2017

This paper addresses the problem of distance- and orientation-based formation control of a class of second-order nonlinear multi-agent systems in 3D space, under static and undirected communication topologies. More specifically, we design a decentralized model-free control protocol in the sense that each agent uses only local information from its neighbors to calculate its own control signal, without incorporating any knowledge of the model nonlinearities and exogenous disturbances. Moreover, the transient and steady state response is solely determined by certain designer-specified performance functions and is fully decoupled by the agents' dynamic model, the control gain selection, the underlying graph topology as well as the initial conditions. Additionally, by introducing certain inter-agent distance constraints, we guarantee collision avoidance and connectivity maintenance between neighboring agents. Finally, simulation results verify the performance of the proposed controllers.
Please Lower Small Cell Antenna Heights in 5G
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we present a new and significant theoretical discovery. If the absolute height difference between base station (BS) antenna and user equipment (UE) antenna is larger than zero, then the network capacity performance in terms of the area spectral efficiency (ASE) will continuously decrease as the BS density increases for ultra-dense (UD) small cell networks (SCNs). This performance behavior has a tremendous impact on the deployment of UD SCNs in the 5th-generation (5G) era. Network operators may invest large amounts of money in deploying more network infrastructure to only obtain an even worse network performance. Our study results reveal that it is a must to lower the SCN BS antenna height to the UE antenna height to fully achieve the capacity gains of UD SCNs in 5G. However, this requires a revolutionized approach of BS architecture and deployment, which is explored in this paper too.
Differentiable Functional Program Interpreters
Venue: arXiv cs.PL 2017
Year: 2017

Programming by Example (PBE) is the task of inducing computer programs from input-output examples. It can be seen as a type of machine learning where the hypothesis space is the set of legal programs in some programming language. Recent work on differentiable interpreters relaxes the discrete space of programs into a continuous space so that search over programs can be performed using gradient-based optimization. While conceptually powerful, so far differentiable interpreter-based program synthesis has only been capable of solving very simple problems. In this work, we study modeling choices that arise when constructing a differentiable programming language and their impact on the success of synthesis. The main motivation for the modeling choices comes from functional programming: we study the effect of memory allocation schemes, immutable data, type systems, and built-in control-flow structures. Empirically we show that incorporating functional programming ideas into differentiable programming languages allows us to learn much more complex programs than is possible with existing differentiable languages.
An Efficient Quasi-physical Quasi-human Algorithm for Packing Equal Circles in a Circular Container
Venue: arXiv cs.CG 2017
Year: 2017

This paper addresses the equal circle packing problem, and proposes an efficient Quasi-physical Quasi-human (QPQH) algorithm. QPQH is based on a modified Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm which we call the local BFGS and a new basin hopping strategy based on a Chinese idiom: alternate tension with relaxation. Starting from a random initial layout, we apply the local BFGS algorithm to reach a local minimum layout. The local BFGS algorithm fully utilizes the neighborhood information of each circle to considerably speed up the running time of the gradient descent process, and the efficiency is very apparent for large scale instances. When yielding a local minimum layout, the new basin-hopping strategy is to shrink the container size to different extent to generate several new layouts. Experimental results indicate that the new basin-hopping strategy is very efficient, especially for a type of layout with comparatively dense packing in the center and comparatively sparse packing around the boundary of the container. We test QPQH on the instances of n = 1,2,...,320, and obtain 66 new layouts which have smaller container sizes than the current best-known results reported in literature.
The Data Complexity of Description Logic Ontologies
Venue: arXiv cs.AI 2017
Year: 2017

We analyze the data complexity of ontology-mediated querying where the ontologies are formulated in a description logic (DL) of the ALC family and queries are conjunctive queries, positive existential queries, or acyclic conjunctive queries. Our approach is non-uniform in the sense that we aim to understand the complexity of each single ontology instead of for all ontologies formulated in a certain language. While doing so, we quantify over the queries and are interested, for example, in the question whether all queries can be evaluated in polynomial time w.r.t. a given ontology. Our results include a PTime/coNP-dichotomy for ontologies of depth one in the description logic ALCFI, the same dichotomy for ALC- and ALCI-ontologies of unrestricted depth, and the non-existence of such a dichotomy for ALCF-ontologies. For the latter DL, we additionally show that it is undecidable whether a given ontology admits PTime query evaluation. We also consider the connection between PTime query evaluation and rewritability into (monadic) Datalog.
On interestingness measures of formal concepts
Venue: arXiv cs.AI 2017
Year: 2017

Formal concepts and closed itemsets proved to be of big importance for knowledge discovery, both as a tool for concise representation of association rules and a tool for clustering and constructing domain taxonomies and ontologies. Exponential explosion makes it difficult to consider the whole concept lattice arising from data, one needs to select most useful and interesting concepts. In this paper interestingness measures of concepts are considered and compared with respect to various aspects, such as efficiency of computation and applicability to noisy data and performing ranking correlation.
Deep Unsupervised Clustering with Gaussian Mixture Variational Autoencoders
Venue: arXiv cs.LG 2017
Year: 2017

We study a variant of the variational autoencoder model (VAE) with a Gaussian mixture as a prior distribution, with the goal of performing unsupervised clustering through deep generative models. We observe that the known problem of over-regularisation that has been shown to arise in regular VAEs also manifests itself in our model and leads to cluster degeneracy. We show that a heuristic called minimum information constraint that has been shown to mitigate this effect in VAEs can also be applied to improve unsupervised clustering performance with our model. Furthermore we analyse the effect of this heuristic and provide an intuition of the various processes with the help of visualizations. Finally, we demonstrate the performance of our model on synthetic data, MNIST and SVHN, showing that the obtained clusters are distinct, interpretable and result in achieving competitive performance on unsupervised clustering to the state-of-the-art results.
Peeling Bipartite Networks for Dense Subgraph Discovery
Venue: arXiv cs.SI 2017
Year: 2017

Finding dense bipartite subgraphs and detecting the relations among them is an important problem for affiliation networks that arise in a range of domains, such as social network analysis, word-document clustering, the science of science, internet advertising, and bioinformatics. However, most dense subgraph discovery algorithms are designed for classic, unipartite graphs. Subsequently, studies on affiliation networks are conducted on the co-occurrence graphs (e.g., co-author and co-purchase) that project the bipartite structure to a unipartite structure by connecting two entities if they share an affiliation. Despite their convenience, co-occurrence networks come at a cost of loss of information and an explosion in graph sizes, which limit the quality and the efficiency of solutions. We study the dense subgraph discovery problem on bipartite graphs. We define a framework of bipartite subgraphs based on the butterfly motif (2,2-biclique) to model the dense regions in a hierarchical structure. We introduce efficient peeling algorithms to find the dense subgraphs and build relations among them. We can identify denser structures compared to the state-of-the-art algorithms on co-occurrence graphs in real-world data. Our analyses on an author-paper network and a user-product network yield interesting subgraphs and hierarchical relations such as the groups of collaborators in the same institution and spammers that give fake ratings.
The Little Engine that Could: Regularization by Denoising (RED)
Venue: arXiv cs.CV 2017
Year: 2017

Removal of noise from an image is an extensively studied problem in image processing. Indeed, the recent advent of sophisticated and highly effective denoising algorithms lead some to believe that existing methods are touching the ceiling in terms of noise removal performance. Can we leverage this impressive achievement to treat other tasks in image processing? Recent work has answered this question positively, in the form of the Plug-and-Play Prior ($P^3$) method, showing that any inverse problem can be handled by sequentially applying image denoising steps. This relies heavily on the ADMM optimization technique in order to obtain this chained denoising interpretation. Is this the only way in which tasks in image processing can exploit the image denoising engine? In this paper we provide an alternative, more powerful and more flexible framework for achieving the same goal. As opposed to the $P^3$ method, we offer Regularization by Denoising (RED): using the denoising engine in defining the regularization of the inverse problem. We propose an explicit image-adaptive Laplacian-based regularization functional, making the overall objective functional clearer and better defined. With a complete flexibility to choose the iterative optimization procedure for minimizing the above functional, RED is capable of incorporating any image denoising algorithm, treat general inverse problems very effectively, and is guaranteed to converge to the globally optimal result. We test this approach and demonstrate state-of-the-art results in the image deblurring and super-resolution problems.
Diverse Neural Network Learns True Target Functions
Venue: arXiv cs.LG 2017
Year: 2017

Neural networks are a powerful class of functions that can be trained with simple gradient descent to achieve state-of-the-art performance on a variety of applications. Despite their practical success, there is a paucity of results that provide theoretical guarantees on why they are so effective. Lying in the center of the problem is the difficulty of analyzing the non-convex loss function with potentially numerous local minima and saddle points. Can neural networks corresponding to the stationary points of the loss function learn the true target function? If yes, what are the key factors contributing to such nice optimization properties? In this paper, we answer these questions by analyzing one-hidden-layer neural networks with ReLU activation, and show that despite the non-convexity, neural networks with diverse units have no spurious local minima. We bypass the non-convexity issue by directly analyzing the first order optimality condition, and show that the loss can be made arbitrarily small if the minimum singular value of the "extended feature matrix" is large enough. We make novel use of techniques from kernel methods and geometric discrepancy, and identify a new relation linking the smallest singular value to the spectrum of a kernel function associated with the activation function and to the diversity of the units. Our results also suggest a novel regularization function to promote unit diversity for potentially better generalization.
Using Neural Networks to Compute Approximate and Guaranteed Feasible Hamilton-Jacobi-Bellman PDE Solutions
Venue: arXiv cs.LG 2017
Year: 2017

To sidestep the curse of dimensionality when computing solutions to Hamilton-Jacobi-Bellman partial differential equations (HJB PDE), we propose an algorithm that leverages a neural network to approximate the value function. We show that our final approximation of the value function generates near optimal controls which are guaranteed to successfully drive the system to a target state. Our framework is not dependent on state space discretization, leading to a significant reduction in computation time and space complexity in comparison with dynamic programming-based approaches. Using this grid-free approach also enables us to plan over longer time horizons with relatively little additional computation overhead. Unlike many previous neural network HJB PDE approximating formulations, our approximation is strictly conservative and hence any trajectories we generate will be strictly feasible. For demonstration, we specialize our new general framework to the Dubins car model and discuss how the framework can be applied to other models with higher-dimensional state spaces.
Optimization Models for Flexible and Adaptive SDN Network Virtualization Layers
Venue: arXiv cs.NI 2017
Year: 2017

Network hypervisors provide the network virtualization layer for Software Defined Networking (SDN). They enable virtual network (VN) tenants to bring their SDN controllers to program their logical networks individually according to their demands. In order to make use of the high flexibility of virtual SDN networks and to provide high performance, the deployment of the virtualization layer needs to adapt to changing VN demands. This paper initializes the study of the optimization of dynamic SDN network virtualization layers. Based on the definition of reconfiguration events, we formalized mixed integer programs to analyze the multi-objective problem of adapting virtualization layers. Our initial simulation results demonstrate Pareto frontiers of conflicting objectives, namely control plane latency and hypervisor and control path reconfigurations.
Linguistically Regularized LSTMs for Sentiment Classification
Venue: arXiv cs.CL 2017
Year: 2017

Sentiment understanding has been a long-term goal of AI in the past decades. This paper deals with sentence-level sentiment classification. Though a variety of neural network models have been proposed very recently, however, previous models either depend on expensive phrase-level annotation, whose performance drops substantially when trained with only sentence-level annotation; or do not fully employ linguistic resources (e.g., sentiment lexicons, negation words, intensity words), thus not being able to produce linguistically coherent representations. In this paper, we propose simple models trained with sentence-level annotation, but also attempt to generating linguistically coherent representations by employing regularizers that model the linguistic role of sentiment lexicons, negation words, and intensity words. Results show that our models are effective to capture the sentiment shifting effect of sentiment, negation, and intensity words, while still obtain competitive results without sacrificing the models' simplicity.
AntMonitor: A System for On-Device Mobile Network Monitoring and its Applications
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we present a complete system for on-device passive monitoring, collection, and analysis of fine grained, large-scale packet measurements from mobile devices. First, we describe the design and implementation of AntMonitor as a userspace mobile app based on a VPN-service but only on the device (without the need to route through a remote VPN server) and using only the minimum resources required. We evaluate our prototype and show that it significantly outperforms prior state-of-the-art approaches: it achieves throughput of over 90 Mbps downlink and 65 Mbps uplink, which is 2x and 8x faster than mobile-only baselines and is 94% of the throughput without VPN, while using 2-12x less energy. Second, we show that AntMonitor is uniquely positioned to serve as a platform for passive on-device mobile network monitoring and to enable a number of applications, including: (i) real-time detection and prevention of private information leakage from the device to the network; (ii) passive network performance monitoring; and (iii) application classification and user profiling. We showcase preliminary results from a pilot user study at a university campus.