OpenRaiser/Intern-Atlas huggingface dataset:
Easy 4G/LTE IMSI Catchers for Non-Programmers
Venue: arXiv cs.CR 2017
Year: 2017

IMSI Catchers are tracking devices that break the privacy of the subscribers of mobile access networks, with disruptive effects to both the communication services and the trust and credibility of mobile network operators. Recently, we verified that IMSI Catcher attacks are really practical for the state-of-the-art 4G/LTE mobile systems too. Our IMSI Catcher device acquires subscription identities (IMSIs) within an area or location within a few seconds of operation and then denies access of subscribers to the commercial network. Moreover, we demonstrate that these attack devices can be easily built and operated using readily available tools and equipment, and without any programming. We describe our experiments and procedures that are based on commercially available hardware and unmodified open source software.
Learning from Ambiguously Labeled Face Images
Venue: arXiv cs.CV 2017
Year: 2017

Learning a classifier from ambiguously labeled face images is challenging since training images are not always explicitly-labeled. For instance, face images of two persons in a news photo are not explicitly labeled by their names in the caption. We propose a Matrix Completion for Ambiguity Resolution (MCar) method for predicting the actual labels from ambiguously labeled images. This step is followed by learning a standard supervised classifier from the disambiguated labels to classify new images. To prevent the majority labels from dominating the result of MCar, we generalize MCar to a weighted MCar (WMCar) that handles label imbalance. Since WMCar outputs a soft labeling vector of reduced ambiguity for each instance, we can iteratively refine it by feeding it as the input to WMCar. Nevertheless, such an iterative implementation can be affected by the noisy soft labeling vectors, and thus the performance may degrade. Our proposed Iterative Candidate Elimination (ICE) procedure makes the iterative ambiguity resolution possible by gradually eliminating a portion of least likely candidates in ambiguously labeled face. We further extend MCar to incorporate the labeling constraints between instances when such prior knowledge is available. Compared to existing methods, our approach demonstrates improvement on several ambiguously labeled datasets.
Deep Heterogeneous Feature Fusion for Template-Based Face Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Although deep learning has yielded impressive performance for face recognition, many studies have shown that different networks learn different feature maps: while some networks are more receptive to pose and illumination others appear to capture more local information. Thus, in this work, we propose a deep heterogeneous feature fusion network to exploit the complementary information present in features generated by different deep convolutional neural networks (DCNNs) for template-based face recognition, where a template refers to a set of still face images or video frames from different sources which introduces more blur, pose, illumination and other variations than traditional face datasets. The proposed approach efficiently fuses the discriminative information of different deep features by 1) jointly learning the non-linear high-dimensional projection of the deep features and 2) generating a more discriminative template representation which preserves the inherent geometry of the deep features in the feature space. Experimental results on the IARPA Janus Challenge Set 3 (Janus CS3) dataset demonstrate that the proposed method can effectively improve the recognition performance. In addition, we also present a series of covariate experiments on the face verification task for in-depth qualitative evaluations for the proposed approach.
Transfer Deep Learning for Low-Resource Chinese Word Segmentation with a Novel Neural Network
Venue: arXiv cs.CL 2017
Year: 2017

Recent studies have shown effectiveness in using neural networks for Chinese word segmentation. However, these models rely on large-scale data and are less effective for low-resource datasets because of insufficient training data. We propose a transfer learning method to improve low-resource word segmentation by leveraging high-resource corpora. First, we train a teacher model on high-resource corpora and then use the learned knowledge to initialize a student model. Second, a weighted data similarity method is proposed to train the student model on low-resource data. Experiment results show that our work significantly improves the performance on low-resource datasets: 2.3% and 1.5% F-score on PKU and CTB datasets. Furthermore, this paper achieves state-of-the-art results: 96.1%, and 96.2% F-score on PKU and CTB datasets.
The Interplay between Human and Machine Agency
Venue: arXiv cs.HC 2017
Year: 2017

Human-machine networks affect many aspects of our lives: from sharing experiences with family and friends, knowledge creation and distance learning, and managing utility bills or providing feedback on retail items, to more specialised networks providing decision support to human operators and the delivery of health care via a network of clinicians, family, friends, and both physical and virtual social robots. Such networks rely on increasingly sophisticated machine algorithms, e.g., to recommend friends or purchases, to track our online activities in order to optimise the services available, and assessing risk to help maintain or even enhance people's health. Users are being offered ever increasing power and reach through these networks by machines which have to support and allow users to be able to achieve goals such as maintaining contact, making better decisions, and monitoring their health. As such, this comes down to a synergy between human and machine agency in which one is dependent in complex ways on the other. With that agency questions arise about trust, risk and regulation, as well as social influence and potential for computer-mediated self-efficacy. In this paper, we explore these constructs and their relationships and present a model based on review of the literature which seeks to identify the various dependencies between them.
A Logical Study of Some Common Principles of Inductive Definition and its Implications for Knowledge Representation
Venue: arXiv cs.LO 2017
Year: 2017

The definition is a common form of human expert knowledge, a building block of formal science and mathematics, a foundation for database theory and is supported in various forms in many knowledge representation and formal specification languages and systems. This paper is a formal study of some of the most common forms of inductive definitions found in scientific text: monotone inductive definition, definition by induction over a well-founded order and iterated inductive definitions. We define a logic of definitions offering a uniform formal syntax to express definitions of the different sorts, and we define its semantics by a faithful formalization of the induction process. Several fundamental properties of definition by induction emerge: the non-determinism of the induction process, the confluence of induction processes, the role of the induction order and its relation to the inductive rules, how the induction order constrains the induction process and, ultimately, that the induction order is irrelevant: the defined set does not depend on the induction order. We propose an inductive construction capable of constructing the defined set without using the induction order. We investigate borderline definitions of the sort that appears in definitional paradoxes.
Weighted Operator Precedence Languages
Venue: arXiv cs.FL 2017
Year: 2017

In the last years renewed investigation of operator precedence languages (OPL) led to discover important properties thereof: OPL are closed with respect to all major operations, are characterized, besides the original grammar family, in terms of an automata family and an MSO logic; furthermore they significantly generalize the well-known visibly pushdown languages (VPL). In another area of research, quantitative models of systems are also greatly in demand. In this paper, we lay the foundation to marry these two research fields. We introduce weighted operator precedence automata and show how they are both strict extensions of OPA and weighted visibly pushdown automata. We prove a Nivat-like result which shows that quantitative OPL can be described by unweighted OPA and very particular weighted OPA. In a Büchi-like theorem, we show that weighted OPA are expressively equivalent to a weighted MSO-logic for OPL.
Distributed deep learning on edge-devices: feasibility via adaptive compression
Venue: arXiv cs.LG 2017
Year: 2017

A large portion of data mining and analytic services use modern machine learning techniques, such as deep learning. The state-of-the-art results by deep learning come at the price of an intensive use of computing resources. The leading frameworks (e.g., TensorFlow) are executed on GPUs or on high-end servers in datacenters. On the other end, there is a proliferation of personal devices with possibly free CPU cycles; this can enable services to run in users' homes, embedding machine learning operations. In this paper, we ask the following question: Is distributed deep learning computation on WAN connected devices feasible, in spite of the traffic caused by learning tasks? We show that such a setup rises some important challenges, most notably the ingress traffic that the servers hosting the up-to-date model have to sustain. In order to reduce this stress, we propose adaComp, a novel algorithm for compressing worker updates to the model on the server. Applicable to stochastic gradient descent based approaches, it combines efficient gradient selection and learning rate modulation. We then experiment and measure the impact of compression, device heterogeneity and reliability on the accuracy of learned models, with an emulator platform that embeds TensorFlow into Linux containers. We report a reduction of the total amount of data sent by workers to the server by two order of magnitude (e.g., 191-fold reduction for a convolutional network on the MNIST dataset), when compared to a standard asynchronous stochastic gradient descent, while preserving model accuracy.
Model Predictive Control for Distributed Microgrid Battery Energy Storage Systems
Venue: arXiv cs.SY 2017
Year: 2017

This paper proposes a new convex model predictive control strategy for dynamic optimal power flow between battery energy storage systems distributed in an AC microgrid. The proposed control strategy uses a new problem formulation, based on a linear d-q reference frame voltage-current model and linearised power flow approximations. This allows the optimal power flows to be solved as a convex optimisation problem, for which fast and robust solvers exist. The proposed method does not assume real and reactive power flows are decoupled, allowing line losses, voltage constraints and converter current constraints to be addressed. In addition, non-linear variations in the charge and discharge efficiencies of lithium ion batteries are analysed and included in the control strategy. Real-time digital simulations were carried out for an islanded microgrid based on the IEEE 13 bus prototypical feeder, with distributed battery energy storage systems and intermittent photovoltaic generation. It is shown that the proposed control strategy approaches the performance of a strategy based on non-convex optimisation, while reducing the required computation time by a factor of 1000, making it suitable for a real-time model predictive control implementation.
Quantized Compressed Sensing for Partial Random Circulant Matrices
Venue: arXiv cs.IT 2017
Year: 2017

We provide the first analysis of a non-trivial quantization scheme for compressed sensing measurements arising from structured measurements. Specifically, our analysis studies compressed sensing matrices consisting of rows selected at random, without replacement, from a circulant matrix generated by a random subgaussian vector. We quantize the measurements using stable, possibly one-bit, Sigma-Delta schemes, and use a reconstruction method based on convex optimization. We show that the part of the reconstruction error due to quantization decays polynomially in the number of measurements. This is in line with analogous results on Sigma-Delta quantization associated with random Gaussian or subgaussian matrices, and significantly better than results associated with the widely assumed memoryless scalar quantization. Moreover, we prove that our approach is stable and robust; i.e., the reconstruction error degrades gracefully in the presence of non-quantization noise and when the underlying signal is not strictly sparse. The analysis relies on results concerning subgaussian chaos processes as well as a variation of McDiarmid's inequality.
An Efficient Parallel Data Clustering Algorithm Using Isoperimetric Number of Trees
Venue: arXiv cs.DC 2017
Year: 2017

We propose a parallel graph-based data clustering algorithm using CUDA GPU, based on exact clustering of the minimum spanning tree in terms of a minimum isoperimetric criteria. We also provide a comparative performance analysis of our algorithm with other related ones which demonstrates the general superiority of this parallel algorithm over other competing algorithms in terms of accuracy and speed.
An Improved Dictatorship Test with Perfect Completeness
Venue: arXiv cs.CC 2017
Year: 2017

A Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is called a dictator if it depends on exactly one variable i.e $f(x_1, x_2, \ldots, x_n) = x_i$ for some $i\in [n]$. In this work, we study a $k$-query dictatorship test. Dictatorship tests are central in proving many hardness results for constraint satisfaction problems. The dictatorship test is said to have {\em perfect completeness} if it accepts any dictator function. The {\em soundness} of a test is the maximum probability with which it accepts any function far from a dictator. Our main result is a $k$-query dictatorship test with perfect completeness and soundness $ \frac{2k + 1}{2^k}$, where $k$ is of the form $2^t -1$ for any integer $t > 2$. This improves upon the result of \cite{TY15} which gave a dictatorship test with soundness $ \frac{2k + 3}{2^k}$.
Compression Complexity
Venue: arXiv cs.CC 2017
Year: 2017

The Kolmogorov complexity of x, denoted C(x), is the length of the shortest program that generates x. For such a simple definition, Kolmogorov complexity has a rich and deep theory, as well as applications to a wide variety of topics including learning theory, complexity lower bounds and SAT algorithms. Kolmogorov complexity typically focuses on decompression, going from the compressed program to the original string. This paper develops a dual notion of compression, the mapping from a string to its compressed version. Typical lossless compression algorithms such as Lempel-Ziv or Huffman Encoding always produce a string that will decompress to the original. We define a general compression concept based on this observation. For every m, we exhibit a single compression algorithm q of length about m which for n and strings x of length n >= m, the output of q will have length within n-m+O(1) bits of C(x). We also show this bound is tight in a strong way, for every n >= m there is an x of length n with C(x) about m such that no compression program of size slightly less than m can compress x at all. We also consider a polynomial time-bounded version of compression complexity and show that similar results for this version would rule out cryptographic one-way functions.
Proust: A Design Space for Highly-Concurrent Transactional Data Structures
Venue: arXiv cs.DC 2017
Year: 2017

Most STM systems are poorly equipped to support libraries of concurrent data structures. One reason is that they typically detect conflicts by tracking transactions' read sets and write sets, an approach that often leads to false conflicts. A second is that existing data structures and libraries often need to be rewritten from scratch to support transactional conflict detection and rollback. This paper introduces Proust, a framework for the design and implementation of transactional data structures. Proust is designed to maximize re-use of existing well-engineered by providing transactional "wrappers" to make existing thread-safe concurrent data structures transactional. Proustian objects are also integrated with an underling STM system, allowing them to take advantage of well-engineered STM conflict detection mechanisms. Proust generalizes and unifies prior approaches such as boosting and predication.
Online Constrained Forest and Prize-Collecting Network Design
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we study a very general type of online network design problem, and generalize two different previous algorithms, one for an online network design problem due to Berman and Coulston [4] and one for (offline) general network design problems due to Goemans and Williamson [9]; we give an O(log k)-competitive algorithm, where k is the number of nodes that must be connected. We also consider a further generalization of the problem that allows us to pay penalties in exchange for violating connectivity constraints; we give an online O(log k)-competitive algorithm for this case as well.
A monad for full ground reference cells
Venue: arXiv cs.PL 2017
Year: 2017

We present a denotational account of dynamic allocation of potentially cyclic memory cells using a monad on a functor category. We identify the collection of heaps as an object in a different functor category equipped with a monad for adding hiding/encapsulation capabilities to the heaps. We derive a monad for full ground references supporting effect masking by applying a state monad transformer to the encapsulation monad. To evaluate the monad, we present a denotational semantics for a call-by-value calculus with full ground references, and validate associated code transformations.
A comparative study of fluid-particle coupling methods for fully resolved lattice Boltzmann simulations
Venue: arXiv cs.CE 2017
Year: 2017

The direct numerical simulation of particulate systems offers a unique approach to study the dynamics of fluid-solid suspensions by fully resolving the submerged particles and without introducing empirical models. For the lattice Boltzmann method, different variants exist to incorporate the fluid-particle interaction into the simulation. This paper provides a detailed and systematic comparison of two different methods, namely the momentum exchange method and the partially saturated cells method by Noble and Torczynski. Three subvariants of each method are used in the benchmark scenario of a single heavy sphere settling in ambient fluid to study their characteristics and accuracy for particle Reynolds numbers from 185 up to 365. The sphere must be resolved with at least 24 computational cells per diameter to achieve velocity errors below 5%. The momentum exchange method is found to be more accurate in predicting the streamwise velocity component whereas the partially saturated cells method is more accurate in the spanwise components. The study reveals that the resolution should be chosen with respect to the coupling dynamics, and not only based on the flow properties, to avoid large errors in the fluid-particle interaction.
Cache-Aided Full-Duplex Small Cells
Venue: arXiv cs.IT 2017
Year: 2017

Caching popular contents at the edge of the network can positively impact the performance and future sustainability of wireless networks in several ways, e.g., end-to-end access delay reduction and peak rate increase. In this paper, we aim at showing that non-negligible performance enhancements can be observed in terms of network interference footprint as well. To this end, we consider a full-duplex small-cell network consisting of non-cooperative cache-aided base stations, which communicate simultaneously with both downlink users and wireless backhaul nodes. We propose a novel caching model seeking to mimic a geographical policy based on local files popularity and calculate the corresponding cache hit probability. Subsequently we study the performance of the considered network in terms of throughput gain with respect to its cache-free half-duplex counterpart. Numerical results corroborate our theoretical findings and highlight remarkable performance gains when moving from cache-free to cache-aided full-duplex small-cell networks.
Binary, Shortened Projective Reed Muller Codes for Coded Private Information Retrieval
Venue: arXiv cs.IT 2017
Year: 2017

The notion of a Private Information Retrieval (PIR) code was recently introduced by Fazeli, Vardy and Yaakobi who showed that this class of codes permit PIR at reduced levels of storage overhead in comparison with replicated-server PIR. In the present paper, the construction of an $(n,k)$ $τ$-server binary, linear PIR code having parameters $n = \sum\limits_{i = 0}^{\ell} {m \choose i}$, $k = {m \choose \ell}$ and $τ= 2^{\ell}$ is presented. These codes are obtained through homogeneous-polynomial evaluation and correspond to the binary, Projective Reed Muller (PRM) code. The construction can be extended to yield PIR codes for any $τ$ of the form $2^{\ell}$, $2^{\ell}-1$ and any value of $k$, through a combination of single-symbol puncturing and shortening of the PRM code. Each of these code constructions above, have smaller storage overhead in comparison with other PIR codes appearing in the literature. For the particular case of $τ=3,4$, we show that the codes constructed here are optimal, systematic PIR codes by providing an improved lower bound on the block length $n(k, τ)$ of a systematic PIR code. It follows from a result by Vardy and Yaakobi, that these codes also yield optimal, systematic primitive multi-set $(n, k, τ)_B$ batch codes for $τ=3,4$. The PIR code constructions presented here also yield upper bounds on the generalized Hamming weights of binary PRM codes.
Collective Motion under Beacon-referenced Cyclic Pursuit
Venue: arXiv cs.SY 2017
Year: 2017

Cyclic pursuit frameworks, which are built upon pursuit interactions between neighboring agents in a cycle graph, provide an efficient way to create useful global behaviors in a collective of autonomous robots. Previous work had considered cyclic pursuit with a constant bearing (CB) pursuit law, and demonstrated the existence of circling equilibria for the corresponding dynamics. In this work, we propose a beacon-referenced version of the CB pursuit law, wherein a stationary beacon provides an additional reference for the individual agents in a collective. When implemented in a cyclic framework, we show that the resulting dynamics admit relative equilibria corresponding to a circling orbit around the beacon, with the circling radius and the distribution of agents along the orbit determined by parameters of the proposed pursuit law. We also derive necessary conditions for stability of the circling equilibria, which provides a guide for parameter selection. Finally, by introducing a change of variables, we demonstrate the existence of a family of invariant manifolds related to spiraling motions around the beacon which preserve the "pure shape" of the collective, and study the reduced dynamics on a representative manifold.