OpenRaiser/Intern-Atlas huggingface dataset:
Defending against Sybil Devices in Crowdsourced Mapping Services
Venue: arXiv cs.SI 2016
Year: 2016

Real-time crowdsourced maps such as Waze provide timely updates on traffic, congestion, accidents and points of interest. In this paper, we demonstrate how lack of strong location authentication allows creation of software-based {\em Sybil devices} that expose crowdsourced map systems to a variety of security and privacy attacks. Our experiments show that a single Sybil device with limited resources can cause havoc on Waze, reporting false congestion and accidents and automatically rerouting user traffic. More importantly, we describe techniques to generate Sybil devices at scale, creating armies of virtual vehicles capable of remotely tracking precise movements for large user populations while avoiding detection. We propose a new approach to defend against Sybil devices based on {\em co-location edges}, authenticated records that attest to the one-time physical co-location of a pair of devices. Over time, co-location edges combine to form large {\em proximity graphs} that attest to physical interactions between devices, allowing scalable detection of virtual vehicles. We demonstrate the efficacy of this approach using large-scale simulations, and discuss how they can be used to dramatically reduce the impact of attacks against crowdsourced mapping services.
On the entropy of a noisy function
Venue: arXiv cs.IT 2016
Year: 2016

Let $0 < ε< 1/2$ be a noise parameter, and let $T_ε$ be the noise operator acting on functions on the boolean cube $\{0,1\}^n$. Let $f$ be a nonnegative function on $\{0,1\}^n$. We upper bound the entropy of $T_ε f$ by the average entropy of conditional expectations of $f$, given sets of roughly $(1-2ε)^2 \cdot n$ variables. In information-theoretic terms, we prove the following strengthening of "Mrs. Gerber's lemma": Let $X$ be a random binary vector of length $n$, and let $Z$ be a noise vector, corresponding to a binary symmetric channel with crossover probability $ε$. Then, setting $v = (1-2ε)^2 \cdot n$, we have (up to lower-order terms): $$ H\Big(X \oplus Z\Big) \ge n \cdot H\left(ε~+~ (1-2ε) \cdot H^{-1}\left(\frac{{\mathbb E}_{|B| = v} H\Big(\{X_i\}_{i\in B}\Big)}{v}\right)\right) $$ As an application, we show that for a boolean function $f$, which is close to a characteristic function $g$ of a subcube of dimension $n-1$, the entropy of $T_ε f$ is at most that of $T_ε g$. This, combined with a recent result of Ordentlich, Shayevitz, and Weinstein shows that the "Most informative boolean function" conjecture of Courtade and Kumar holds for high noise $ε\ge 1/2 - δ$, for some absolute constant $δ> 0$. Namely, if $X$ is uniformly distributed in $\{0,1\}^n$ and $Y$ is obtained by flipping each coordinate of $X$ independently with probability $ε$, then, provided $ε\ge 1/2 - δ$, for any boolean function $f$ holds $I\Big(f(X);Y\Big) \le 1 - H(ε)$.
Normalized Hierarchical SVM
Venue: arXiv cs.LG 2016
Year: 2016

We present improved methods of using structured SVMs in a large-scale hierarchical classification problem, that is when labels are leaves, or sets of leaves, in a tree or a DAG. We examine the need to normalize both the regularization and the margin and show how doing so significantly improves performance, including allowing achieving state-of-the-art results where unnormalized structured SVMs do not perform better than flat models. We also describe a further extension of hierarchical SVMs that highlight the connection between hierarchical SVMs and matrix factorization models.
STFT Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms
Venue: arXiv cs.IT 2016
Year: 2016

The problem of recovering a signal from its Fourier magnitude is of paramount importance in various fields of engineering and applied physics. Due to the absence of Fourier phase information, some form of additional information is required in order to be able to uniquely, efficiently and robustly identify the underlying signal. Inspired by practical methods in optical imaging, we consider the problem of signal reconstruction from the Short-Time Fourier Transform (STFT) magnitude. We first develop conditions under which the STFT magnitude is an almost surely unique signal representation. We then consider a semidefinite relaxation-based algorithm (STliFT) and provide recovery guarantees. Numerical simulations complement our theoretical analysis and provide directions for future work.
A Randomized Rounding Algorithm for Sparse PCA
Venue: arXiv cs.DS 2016
Year: 2016

We present and analyze a simple, two-step algorithm to approximate the optimal solution of the sparse PCA problem. Our approach first solves a L1 penalized version of the NP-hard sparse PCA optimization problem and then uses a randomized rounding strategy to sparsify the resulting dense solution. Our main theoretical result guarantees an additive error approximation and provides a tradeoff between sparsity and accuracy. Our experimental evaluation indicates that our approach is competitive in practice, even compared to state-of-the-art toolboxes such as Spasm.
A Learning-Based Approach to Caching in Heterogenous Small Cell Networks
Venue: arXiv cs.IT 2016
Year: 2016

A heterogenous network with base stations (BSs), small base stations (SBSs) and users distributed according to independent Poisson point processes is considered. SBS nodes are assumed to possess high storage capacity and to form a distributed caching network. Popular files are stored in local caches of SBSs, so that a user can download the desired files from one of the SBSs in its vicinity. The offloading-loss is captured via a cost function that depends on the random caching strategy proposed here. The popularity profile of cached content is unknown and estimated using instantaneous demands from users within a specified time interval. An estimate of the cost function is obtained from which an optimal random caching strategy is devised. The training time to achieve an $ε>0$ difference between the achieved and optimal costs is finite provided the user density is greater than a predefined threshold, and scales as $N^2$, where $N$ is the support of the popularity profile. A transfer learning-based approach to improve this estimate is proposed. The training time is reduced when the popularity profile is modeled using a parametric family of distributions; the delay is independent of $N$ and scales linearly with the dimension of the distribution parameter.
Corona graphs as a model of small-world networks
Venue: arXiv cs.DM 2016
Year: 2016

We introduce recursive corona graphs as a model of small-world networks. We investigate analytically the critical characteristics of the model, including order and size, degree distribution, average path length, clustering coefficient, and the number of spanning trees, as well as Kirchhoff index. Furthermore, we study the spectra for the adjacency matrix and the Laplacian matrix for the model. We obtain explicit results for all the quantities of the recursive corona graphs, which are similar to those observed in real-life networks.
Quantifying and Visualizing Uncertainties in Molecular Models
Venue: arXiv cs.CE 2016
Year: 2016

Computational molecular modeling and visualization has seen significant progress in recent years with sev- eral molecular modeling and visualization software systems in use today. Nevertheless the molecular biology community lacks techniques and tools for the rigorous analysis, quantification and visualization of the associated errors in molecular structure and its associated properties. This paper attempts at filling this vacuum with the introduction of a systematic statistical framework where each source of structural uncertainty is modeled as a ran- dom variable (RV) with a known distribution, and properties of the molecules are defined as dependent RVs. The framework consists of a theoretical basis, and an empirical implementation where the uncertainty quantification (UQ) analysis is achieved by using Chernoff-like bounds. The framework enables additionally the propagation of input structural data uncertainties, which in the molecular protein world are described as B-factors, saved with almost all X-ray models deposited in the Protein Data Bank (PDB). Our statistical framework is also able and has been applied to quantify and visualize the uncertainties in molecular properties, namely solvation interfaces and solvation free energy estimates. For each of these quantities of interest (QOI) of the molecular models we provide several novel and intuitive visualizations of the input, intermediate, and final propagated uncertainties. These methods should enable the end user achieve a more quantitative and visual evaluation of various molecular PDB models for structural and property correctness, or the lack thereof.
Owl and Lizard: Patterns of Head Pose and Eye Pose in Driver Gaze Classification
Venue: arXiv cs.CV 2016
Year: 2016

Accurate, robust, inexpensive gaze tracking in the car can help keep a driver safe by facilitating the more effective study of how to improve (1) vehicle interfaces and (2) the design of future Advanced Driver Assistance Systems. In this paper, we estimate head pose and eye pose from monocular video using methods developed extensively in prior work and ask two new interesting questions. First, how much better can we classify driver gaze using head and eye pose versus just using head pose? Second, are there individual-specific gaze strategies that strongly correlate with how much gaze classification improves with the addition of eye pose information? We answer these questions by evaluating data drawn from an on-road study of 40 drivers. The main insight of the paper is conveyed through the analogy of an "owl" and "lizard" which describes the degree to which the eyes and the head move when shifting gaze. When the head moves a lot ("owl"), not much classification improvement is attained by estimating eye pose on top of head pose. On the other hand, when the head stays still and only the eyes move ("lizard"), classification accuracy increases significantly from adding in eye pose. We characterize how that accuracy varies between people, gaze strategies, and gaze regions.
Multi-agent Reinforcement Learning with Sparse Interactions by Negotiation and Knowledge Transfer
Venue: arXiv cs.MA 2016
Year: 2016

Reinforcement learning has significant applications for multi-agent systems, especially in unknown dynamic environments. However, most multi-agent reinforcement learning (MARL) algorithms suffer from such problems as exponential computation complexity in the joint state-action space, which makes it difficult to scale up to realistic multi-agent problems. In this paper, a novel algorithm named negotiation-based MARL with sparse interactions (NegoSI) is presented. In contrast to traditional sparse-interaction based MARL algorithms, NegoSI adopts the equilibrium concept and makes it possible for agents to select the non-strict Equilibrium Dominating Strategy Profile (non-strict EDSP) or Meta equilibrium for their joint actions. The presented NegoSI algorithm consists of four parts: the equilibrium-based framework for sparse interactions, the negotiation for the equilibrium set, the minimum variance method for selecting one joint action and the knowledge transfer of local Q-values. In this integrated algorithm, three techniques, i.e., unshared value functions, equilibrium solutions and sparse interactions are adopted to achieve privacy protection, better coordination and lower computational complexity, respectively. To evaluate the performance of the presented NegoSI algorithm, two groups of experiments are carried out regarding three criteria: steps of each episode (SEE), rewards of each episode (REE) and average runtime (AR). The first group of experiments is conducted using six grid world games and shows fast convergence and high scalability of the presented algorithm. Then in the second group of experiments NegoSI is applied to an intelligent warehouse problem and simulated results demonstrate the effectiveness of the presented NegoSI algorithm compared with other state-of-the-art MARL algorithms.
Strong data-processing inequalities for channels and Bayesian networks
Venue: arXiv cs.IT 2016
Year: 2016

The data-processing inequality, that is, $I(U;Y) \le I(U;X)$ for a Markov chain $U \to X \to Y$, has been the method of choice for proving impossibility (converse) results in information theory and many other disciplines. Various channel-dependent improvements (called strong data-processing inequalities, or SDPIs) of this inequality have been proposed both classically and more recently. In this note we first survey known results relating various notions of contraction for a single channel. Then we consider the basic extension: given SDPI for each constituent channel in a Bayesian network, how to produce an end-to-end SDPI? Our approach is based on the (extract of the) Evans-Schulman method, which is demonstrated for three different kinds of SDPIs, namely, the usual Ahslwede-Gács type contraction coefficients (mutual information), Dobrushin's contraction coefficients (total variation), and finally the $F_I$-curve (the best possible non-linear SDPI for a given channel). Resulting bounds on the contraction coefficients are interpreted as probability of site percolation. As an example, we demonstrate how to obtain SDPI for an $n$-letter memoryless channel with feedback given an SDPI for $n=1$. Finally, we discuss a simple observation on the equivalence of a linear SDPI and comparison to an erasure channel (in the sense of "less noisy" order). This leads to a simple proof of a curious inequality of Samorodnitsky (2015), and sheds light on how information spreads in the subsets of inputs of a memoryless channel.
Cooking in the kitchen: Recognizing and Segmenting Human Activities in Videos
Venue: arXiv cs.CV 2016
Year: 2016

As research on action recognition matures, the focus is shifting away from categorizing basic task-oriented actions using hand-segmented video datasets to understanding complex goal-oriented daily human activities in real-world settings. Temporally structured models would seem obvious to tackle this set of problems, but so far, cases where these models have outperformed simpler unstructured bag-of-word types of models are scarce. With the increasing availability of large human activity datasets, combined with the development of novel feature coding techniques that yield more compact representations, it is time to revisit structured generative approaches. Here, we describe an end-to-end generative approach from the encoding of features to the structural modeling of complex human activities by applying Fisher vectors and temporal models for the analysis of video sequences. We systematically evaluate the proposed approach on several available datasets (ADL, MPIICooking, and Breakfast datasets) using a variety of performance metrics. Through extensive system evaluations, we demonstrate that combining compact video representations based on Fisher Vectors with HMM-based modeling yields very significant gains in accuracy and when properly trained with sufficient training samples, structured temporal models outperform unstructured bag-of-word types of models by a large margin on the tested performance metric.
Greedy methods, randomization approaches and multi-arm bandit algorithms for efficient sparsity-constrained optimization
Venue: arXiv cs.LG 2016
Year: 2016

Several sparsity-constrained algorithms such as Orthogonal Matching Pursuit or the Frank-Wolfe algorithm with sparsity constraints work by iteratively selecting a novel atom to add to the current non-zero set of variables. This selection step is usually performed by computing the gradient and then by looking for the gradient component with maximal absolute entry. This step can be computationally expensive especially for large-scale and high-dimensional data. In this work, we aim at accelerating these sparsity-constrained optimization algorithms by exploiting the key observation that, for these algorithms to work, one only needs the coordinate of the gradient's top entry. Hence, we introduce algorithms based on greedy methods and randomization approaches that aim at cheaply estimating the gradient and its top entry. Another of our contribution is to cast the problem of finding the best gradient entry as a best arm identification in a multi-armed bandit problem. Owing to this novel insight, we are able to provide a bandit-based algorithm that directly estimates the top entry in a very efficient way. Theoretical observations stating that the resulting inexact Frank-Wolfe or Orthogonal Matching Pursuit algorithms act, with high probability, similarly to their exact versions are also given. We have carried out several experiments showing that the greedy deterministic and the bandit approaches we propose can achieve an acceleration of an order of magnitude while being as efficient as the exact gradient when used in algorithms such as OMP, Frank-Wolfe or CoSaMP.
Analysis of multiview legislative networks with structured matrix factorization: Does Twitter influence translate to the real world?
Venue: arXiv cs.SI 2016
Year: 2016

The rise of social media platforms has fundamentally altered the public discourse by providing easy to use and ubiquitous forums for the exchange of ideas and opinions. Elected officials often use such platforms for communication with the broader public to disseminate information and engage with their constituencies and other public officials. In this work, we investigate whether Twitter conversations between legislators reveal their real-world position and influence by analyzing multiple Twitter networks that feature different types of link relations between the Members of Parliament (MPs) in the United Kingdom and an identical data set for politicians within Ireland. We develop and apply a matrix factorization technique that allows the analyst to emphasize nodes with contextual local network structures by specifying network statistics that guide the factorization solution. Leveraging only link relation data, we find that important politicians in Twitter networks are associated with real-world leadership positions, and that rankings from the proposed method are correlated with the number of future media headlines.
Risk Mitigation for Dynamic State Estimation Against Cyber Attacks and Unknown Inputs
Venue: arXiv cs.SY 2016
Year: 2016

Phasor measurement units (PMUs) can be effectively utilized for the monitoring and control of the power grid. As the cyber-world becomes increasingly embedded into power grids, the risks of this inevitable evolution become serious. In this paper, we present a risk mitigation strategy, based on dynamic state estimation, to eliminate threat levels from the grid's unknown inputs and potential cyber-attacks. The strategy requires (a) the potentially incomplete knowledge of power system models and parameters and (b) real-time PMU measurements. First, we utilize a dynamic state estimator for higher order depictions of power system dynamics for simultaneous state and unknown inputs estimation. Second, estimates of cyber-attacks are obtained through an attack detection algorithm. Third, the estimation and detection components are seamlessly utilized in an optimization framework to determine the most impacted PMU measurements. Finally, a risk mitigation strategy is proposed to guarantee the elimination of threats from attacks, ensuring the observability of the power system through available, safe measurements. Case studies are included to validate the proposed approach. Insightful suggestions, extensions, and open problems are also posed.
Protocol Programming: A Connection of the Digital World
Venue: arXiv cs.PL 2016
Year: 2016

The current computer programmings encapsulate attributes and behaviours into objects, but miss the mechanism to support the connection among objects. A programming paradigm is presented to connect all objects. The connection supports communications. Protocols are defined to coordinate the behaviours between objects, which enable the interaction of objects across different platforms. The connection also provides an efficient mechanism to support the concurrency, parallelism, distribution, pipeline and adaptability, etc. They can be governed transparently, autonomously, even adaptively. In this paper, an implementation is also discussed to show the effectiveness of protocol programming.
Mode Selection, Resource Allocation and Power Control for D2D-Enabled Two-Tier Cellular Network
Venue: arXiv cs.IT 2016
Year: 2016

This paper proposes a centralized decision making framework at the macro base station (MBS) for device to device (D2D) communication underlaying a two-tier cellular network. We consider a D2D pair in the presence of an MBS and a femto access point, each serving a user, with quality of service constraints for all users. Our proposed solution encompasses mode selection (choosing between cellular or reuse or dedicated mode), resource allocation (in cellular and dedicated mode) and power control (in reuse mode) within a single framework. The framework prioritizes D2D dedicated mode if the D2D pair are close to each other and orthogonal resources are available. Otherwise, it allows D2D reuse mode if the D2D satisfies both the maximum distance and an additional interference criteria. For reuse mode, we present a geometric vertex search approach to solve the power allocation problem. We analytically prove the validity of this approach and show that it achieves near optimal performance. For cellular and dedicated modes, we show that frequency sharing maximizes sum rate and solve the resource allocation problem in closed form. Our simulations demonstrate the advantages of the proposed framework in terms of the performance gains achieved in D2D mode.
FEC for Lower In-Order Delivery Delay in Packet Networks
Venue: arXiv cs.IT 2016
Year: 2016

We consider use of FEC to reduce in-order delivery delay over packet erasure channels. We propose a class of streaming codes that is capacity achieving and provides a superior throughput-delay trade-off compared to block codes by introducing flexibility in where and when redundancy is placed. This flexibility results in significantly lower in-order delay for a given throughput for a wide range of network scenarios. Furthermore, a major contribution of this paper is the combination of queuing and coding theory to analyze the code's performance. Finally, we present simulation and experimental results illustrating the code's benefits.
Smoothness for Simultaneous Composition of Mechanisms with Admission
Venue: arXiv cs.GT 2016
Year: 2016

We study social welfare of learning outcomes in mechanisms with admission. In our repeated game there are $n$ bidders and $m$ mechanisms, and in each round each mechanism is available for each bidder only with a certain probability. Our scenario is an elementary case of simple mechanism design with incomplete information, where availabilities are bidder types. It captures natural applications in online markets with limited supply and can be used to model access of unreliable channels in wireless networks. If mechanisms satisfy a smoothness guarantee, existing results show that learning outcomes recover a significant fraction of the optimal social welfare. These approaches, however, have serious drawbacks in terms of plausibility and computational complexity. Also, the guarantees apply only when availabilities are stochastically independent among bidders. In contrast, we propose an alternative approach where each bidder uses a single no-regret learning algorithm and applies it in all rounds. This results in what we call availability-oblivious coarse correlated equilibria. It exponentially decreases the learning burden, simplifies implementation (e.g., as a method for channel access in wireless devices), and thereby addresses some of the concerns about Bayes-Nash equilibria and learning outcomes in Bayesian settings. Our main results are general composition theorems for smooth mechanisms when valuation functions of bidders are lattice-submodular. They rely on an interesting connection to the notion of correlation gap of submodular functions over product lattices.