OpenRaiser/Intern-Atlas huggingface dataset:
BiFold visualization of bipartite datasets
Venue: arXiv cs.SI 2017
Year: 2017

The emerging domain of data-enabled science necessitates development of algorithms and tools for knowledge discovery. Human interaction with data through well-constructed graphical representation can take special advantage of our visual ability to identify patterns. We develop a data visualization framework, called BiFold, for exploratory analysis of bipartite datasets that describe binary relationships between groups of objects. Typical data examples would include voting records, organizational memberships, and pairwise associations, or other binary datasets. BiFold provides a low dimensional embedding of data that represents similarity by visual nearness, analogous to Multidimensional Scaling (MDS). The unique and new feature of BiFold is its ability to simultaneously capture both within-group and between-group relationships among objects, enhancing knowledge discovery. We benchmark BiFold using the {\it Southern Women Dataset}, where social groups are now visually evident. We construct BiFold plots for two US voting datasets: For the presidential election outcomes since 1976, BiFold illustrates the evolving geopolitical structures that underlie these election results. For Senate congressional voting, BiFold identifies a partisan coordinate, separating senators into two parties while simultaneously visualizing a bipartisan-coalition coordinate which captures the ultimate fate of the bills (pass/fail). Finally, we consider a global cuisine dataset of the association between recipes and food ingredients. BiFold allows us to visually compare and contrast cuisines while also allowing identification of signature ingredients of individual cuisines.
Enriched K-Tier HetNet Model to Enable the Analysis of User-Centric Small Cell Deployments
Venue: arXiv cs.IT 2017
Year: 2017

One of the principal underlying assumptions of current approaches to the analysis of heterogeneous cellular networks (HetNets) with random spatial models is the uniform distribution of users independent of the base station (BS) locations. This assumption is not quite accurate, especially for user-centric capacity-driven small cell deployments where low-power BSs are deployed in the areas of high user density, thus inducing a natural correlation in the BS and user locations. In order to capture this correlation, we enrich the existing K-tier Poisson Point Process (PPP) HetNet model by considering user locations as Poisson Cluster Process (PCP) with the BSs at the cluster centers. In particular, we provide the formal analysis of the downlink coverage probability in terms of a general density functions describing the locations of users around the BSs. The derived results are specialized for two cases of interest: (i) Thomas cluster process, where the locations of the users around BSs are Gaussian distributed, and (ii) Matérn cluster process, where the users are uniformly distributed inside a disc of a given radius. Tight closed-form bounds for the coverage probability in these two cases are also derived. Our results demonstrate that the coverage probability decreases as the size of user clusters around BSs increases, ultimately collapsing to the result obtained under the assumption of PPP distribution of users independent of the BS locations when the cluster size goes to infinity. Using these results, we also handle mixed user distributions consisting of two types of users: (i) uniformly distributed, and (ii) clustered around certain tiers.
Multiple Instance Hyperspectral Target Characterization
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, two methods for multiple instance target characterization, MI-SMF and MI-ACE, are presented. MI-SMF and MI-ACE estimate a discriminative target signature from imprecisely-labeled and mixed training data. In many applications, such as sub-pixel target detection in remotely-sensed hyperspectral imagery, accurate pixel-level labels on training data is often unavailable and infeasible to obtain. Furthermore, since sub-pixel targets are smaller in size than the resolution of a single pixel, training data is comprised only of mixed data points (in which target training points are mixtures of responses from both target and non-target classes). Results show improved, consistent performance over existing multiple instance concept learning methods on several hyperspectral sub-pixel target detection problems.
Vulnerability of Fixed-Time Control of Signalized Intersections to Cyber-Tampering
Venue: arXiv cs.SY 2017
Year: 2017

Recent experimental studies have shown that traffic management systems are vulnerable to cyber-attacks on sensor data. This paper studies the vulnerability of fixed-time control of signalized intersections when sensors measuring traffic flow information are compromised and perturbed by an adversary. The problems are formulated by considering three malicious objectives: 1) worst-case network accumulation, which aims to destabilize the overall network as much as possible; 2) worst-case lane accumulation, which aims to cause worst-case accumulation on some target lanes; and 3) risk-averse target accumulation, which aims to reach a target accumulation by making the minimum perturbation to sensor data. The problems are solved using bilevel programming optimization methods. Finally, a case study of a real network is used to illustrate the results.
SMCQL: Secure Querying for Federated Databases
Venue: arXiv cs.DB 2017
Year: 2017

People and machines are collecting data at an unprecedented rate. Despite this newfound abundance of data, progress has been slow in sharing it for open science, business, and other data-intensive endeavors. Many such efforts are stymied by privacy concerns and regulatory compliance issues. For example, many hospitals are interested in pooling their medical records for research, but none may disclose arbitrary patient records to researchers or other healthcare providers. In this context we propose the Private Data Network (PDN), a federated database for querying over the collective data of mutually distrustful parties. In a PDN, each member database does not reveal its tuples to its peers nor to the query writer. Instead, the user submits a query to an honest broker that plans and coordinates its execution over multiple private databases using secure multiparty computation (SMC). Here, each database's query execution is oblivious, and its program counters and memory traces are agnostic to the inputs of others. We introduce a framework for executing PDN queries named SMCQL. This system translates SQL statements into SMC primitives to compute query results over the union of its source databases without revealing sensitive information about individual tuples to peer data providers or the honest broker. Only the honest broker and the querier receive the results of a PDN query. For fast, secure query evaluation, we explore a heuristics-driven optimizer that minimizes the PDN's use of secure computation and partitions its query evaluation into scalable slices.
Scaling Bounded Model Checking By Transforming Programs With Arrays
Venue: arXiv cs.LO 2017
Year: 2017

Bounded Model Checking is one the most successful techniques for finding bugs in program. However, model checkers are resource hungry and are often unable to verify programs with loops iterating over large arrays.We present a transformation that enables bounded model checkers to verify a certain class of array properties. Our technique transforms an array-manipulating (ANSI-C) program to an array-free and loop-free (ANSI-C) program thereby reducing the resource requirements of a model checker significantly. Model checking of the transformed program using an off-the-shelf bounded model checker simulates the loop iterations efficiently. Thus, our transformed program is a sound abstraction of the original program and is also precise in a large number of cases - we formally characterize the class of programs for which it is guaranteed to be precise. We demonstrate the applicability and usefulness of our technique on both industry code as well as academic benchmarks.
Deep Learning Markov Random Field for Semantic Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

Semantic segmentation tasks can be well modeled by Markov Random Field (MRF). This paper addresses semantic segmentation by incorporating high-order relations and mixture of label contexts into MRF. Unlike previous works that optimized MRFs using iterative algorithm, we solve MRF by proposing a Convolutional Neural Network (CNN), namely Deep Parsing Network (DPN), which enables deterministic end-to-end computation in a single forward pass. Specifically, DPN extends a contemporary CNN to model unary terms and additional layers are devised to approximate the mean field (MF) algorithm for pairwise terms. It has several appealing properties. First, different from the recent works that required many iterations of MF during back-propagation, DPN is able to achieve high performance by approximating one iteration of MF. Second, DPN represents various types of pairwise terms, making many existing models as its special cases. Furthermore, pairwise terms in DPN provide a unified framework to encode rich contextual information in high-dimensional data, such as images and videos. Third, DPN makes MF easier to be parallelized and speeded up, thus enabling efficient inference. DPN is thoroughly evaluated on standard semantic image/video segmentation benchmarks, where a single DPN model yields state-of-the-art segmentation accuracies on PASCAL VOC 2012, Cityscapes dataset and CamVid dataset.
A taxonomy of localization techniques based on multidimensional scaling
Venue: arXiv cs.NI 2017
Year: 2017

Localization in Wireless Sensor Networks (WSNs) has been a challenging problem in the last decade. The most explored approaches for this purpose are based on multidimensional scaling (MDS) technique. The first algorithm that introduced MDS for nodes localization in sensor networks is well known as MDS-MAP. Since its appearance in 2003, many variations of MDS-MAP have been proposed in the literature. This paper aims to provide a comprehensive survey of the localization techniques that are based on MDS. We classify MDS-based algorithms according to different taxonomy features and different evaluation metrics.
Project Based Learning of Embedded Systems
Venue: arXiv cs.OH 2017
Year: 2017

Traditional teaching, usually based on lectures and tutorials fosters the idea of instruction-driven learning model where students are passive listeners. Besides this approach, Project Based Learning (PBL) as a different learning paradigm is standing behind constructivism learning theory, where learning from real-world situations is put on the first place. The purpose of this paper is to present our approach in learning embedded systems at our University. It is based on combination of traditional (face-to-face) learning and PBL. Our PBL represents an interdisciplinary project based on wireless sensor monitoring of real-world environment (greenhouse). The students use UML that was shown as an excellent tool for developing such a projects. From the student perspective, we found that this high level of interdisciplinary is very valuable from the point of view of facing the students with real-life problems.
Do the Young Live in a "Smaller World" Than the Old? Age-Specific Degrees of Separation in Human Communication
Venue: arXiv cs.SI 2017
Year: 2017

In this paper, we investigate the phenomenon of "age-specific small worlds" using data from a large-scale mobile communication network approximating interaction patterns at societal scale. Rather than asking whether two random individuals are separated by a small number of links, we ask whether individuals in specific age groups live in a small world in relation to individuals from other age groups. Our analysis shows that there is systematic variation in this age-relative small world effect. Young people live in the "smallest world," being separated from other young people and their parent's generation via a smaller number of intermediaries than older individuals. The oldest people live in the "least small world," being separated from their same age peers and their younger counterparts by a larger number of intermediaries. Variation in the small world effect is specific to age as a node attribute (being absent in the case of gender) and is consistently observed under several data robustness checks. The discovery of age-specific small worlds is consistent with well-known social mechanisms affecting the way age interacts with network connectivity and the relative prevalence of kin ties and non-kin ties observed in this network. This social pattern has significant implications for our understanding of generation-specific dynamics of information cascades, diffusion phenomena, and the spread of fads and fashions.
Propagators and Solvers for the Algebra of Modular Systems
Venue: arXiv cs.AI 2017
Year: 2017

To appear in the proceedings of LPAR 21. Solving complex problems can involve non-trivial combinations of distinct knowledge bases and problem solvers. The Algebra of Modular Systems is a knowledge representation framework that provides a method for formally specifying such systems in purely semantic terms. Formally, an expression of the algebra defines a class of structures. Many expressive formalism used in practice solve the model expansion task, where a structure is given on the input and an expansion of this structure in the defined class of structures is searched (this practice overcomes the common undecidability problem for expressive logics). In this paper, we construct a solver for the model expansion task for a complex modular systems from an expression in the algebra and black-box propagators or solvers for the primitive modules. To this end, we define a general notion of propagators equipped with an explanation mechanism, an extension of the alge- bra to propagators, and a lazy conflict-driven learning algorithm. The result is a framework for seamlessly combining solving technology from different domains to produce a solver for a combined system.
Reconstruction Error Bounds for Compressed Sensing under Poisson Noise using the Square Root of the Jensen-Shannon Divergence
Venue: arXiv cs.IT 2017
Year: 2017

Reconstruction error bounds in compressed sensing under Gaussian or uniform bounded noise do not translate easily to the case of Poisson noise. Reasons for this include the signal dependent nature of Poisson noise, and also the fact that the negative log likelihood (NLL) in case of a Poisson distribution (which is related to the generalized Kullback-Leibler divergence (GKLD)) is not a metric and does not obey the triangle inequality. There exist prior theoretical results in the form of provable error bounds for computationally tractable estimators for compressed sensing problems under Poisson noise. However, these results do not apply to realistic compressive systems, which must obey some crucial constraints such as non-negativity and flux preservation. On the other hand, there exist provable error bounds for such realistic systems in the published literature, but they are for estimators that are computationally intractable. In this paper, we develop error bounds for a computationally tractable estimator which also applies to realistic compressive systems obeying the required constraints. Our technique replaces the GKLD, with an information theoretic metric - namely the square root of the Jensen-Shannon divergence (JSD), which is related to an approximate, symmetrized version of the Poisson NLL. We show that this allows for simple proofs of the error bounds. We propose and prove interesting statistical properties of the square root of JSD and exploit other known ones. Numerical experiments are performed showing the use of the technique in signal and image reconstruction from compressed measurements under Poisson noise. Our technique applies to sparse/ compressible signals in any orthonormal basis, works with high probability for any randomly generated non-negative and flux-preserving sensing matrix and is proposes an estimator whose parameters are purely statistically motivated.
Biconnectivity, $st$-numbering and other applications of DFS using $O(n)$ bits
Venue: arXiv cs.DS 2017
Year: 2017

We consider space efficient implementations of some classical applications of DFS including the problem of testing biconnectivity and $2$-edge connectivity, finding cut vertices and cut edges, computing chain decomposition and $st$-numbering of a given undirected graph $G$ on $n$ vertices and $m$ edges. Classical algorithms for them typically use DFS and some $Ω(\lg n)$ bits\footnote{We use $\lg$ to denote logarithm to the base $2$.} of information at each vertex. Building on a recent $O(n)$-bits implementation of DFS due to Elmasry et al. (STACS 2015) we provide $O(n)$-bit implementations for all these applications of DFS. Our algorithms take $O(m \lg^c n \lg\lg n)$ time for some small constant $c$ (where $c \leq 2$). Central to our implementation is a succinct representation of the DFS tree and a space efficient partitioning of the DFS tree into connected subtrees, which maybe of independent interest for designing other space efficient graph algorithms.
The Capacity of Symmetric Private Information Retrieval
Venue: arXiv cs.IT 2017
Year: 2017

Private information retrieval (PIR) is the problem of retrieving as efficiently as possible, one out of $K$ messages from $N$ non-communicating replicated databases (each holds all $K$ messages) while keeping the identity of the desired message index a secret from each individual database. Symmetric PIR (SPIR) is a generalization of PIR to include the requirement that beyond the desired message, the user learns nothing about the other $K-1$ messages. The information theoretic capacity of SPIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. We show that the capacity of SPIR is $1-1/N$ regardless of the number of messages $K$, if the databases have access to common randomness (not available to the user) that is independent of the messages, in the amount that is at least $1/(N-1)$ bits per desired message bit, and zero otherwise. Extensions to the capacity region of SPIR and the capacity of finite length SPIR are provided.
Object Boundary Detection and Classification with Image-level Labels
Venue: arXiv cs.CV 2017
Year: 2017

Semantic boundary and edge detection aims at simultaneously detecting object edge pixels in images and assigning class labels to them. Systematic training of predictors for this task requires the labeling of edges in images which is a particularly tedious task. We propose a novel strategy for solving this task, when pixel-level annotations are not available, performing it in an almost zero-shot manner by relying on conventional whole image neural net classifiers that were trained using large bounding boxes. Our method performs the following two steps at test time. Firstly it predicts the class labels by applying the trained whole image network to the test images. Secondly, it computes pixel-wise scores from the obtained predictions by applying backprop gradients as well as recent visualization algorithms such as deconvolution and layer-wise relevance propagation. We show that high pixel-wise scores are indicative for the location of semantic boundaries, which suggests that the semantic boundary problem can be approached without using edge labels during the training phase.
Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
Venue: arXiv cs.LG 2017
Year: 2017

In this work, we are interested in generalizing convolutional neural networks (CNNs) from low-dimensional regular grids, where image, video and speech are represented, to high-dimensional irregular domains, such as social networks, brain connectomes or words' embedding, represented by graphs. We present a formulation of CNNs in the context of spectral graph theory, which provides the necessary mathematical background and efficient numerical schemes to design fast localized convolutional filters on graphs. Importantly, the proposed technique offers the same linear computational complexity and constant learning complexity as classical CNNs, while being universal to any graph structure. Experiments on MNIST and 20NEWS demonstrate the ability of this novel deep learning system to learn local, stationary, and compositional features on graphs.
Capacity of Gaussian Many-Access Channels
Venue: arXiv cs.IT 2017
Year: 2017

Classical multiuser information theory studies the fundamental limits of models with a fixed (often small) number of users as the coding blocklength goes to infinity. This work proposes a new paradigm, referred to as {\em many-user information theory}, where the number of users is allowed to grow with the blocklength. This paradigm is motivated by emerging systems with a massive number of users in an area, such as machine-to-machine communication systems and sensor networks. The focus of the current paper is the {\em many-access} channel model, which consists of a single receiver and many transmitters, whose number increases unboundedly with the blocklength. Moreover, an unknown subset of transmitters may transmit in a given block and need to be identified. A new notion of capacity is introduced and characterized for the Gaussian many-access channel with random user activities. The capacity can be achieved by first detecting the set of active users and then decoding their messages.
Sampling-based Incremental Information Gathering with Applications to Robotic Exploration and Environmental Monitoring
Venue: arXiv cs.RO 2017
Year: 2017

In this article, we propose a sampling-based motion planning algorithm equipped with an information-theoretic convergence criterion for incremental informative motion planning. The proposed approach allows dense map representations and incorporates the full state uncertainty into the planning process. The problem is formulated as a constrained maximization problem. Our approach is built on rapidly-exploring information gathering algorithms and benefits from advantages of sampling-based optimal motion planning algorithms. We propose two information functions and their variants for fast and online computations. We prove an information-theoretic convergence for an entire exploration and information gathering mission based on the least upper bound of the average map entropy. A natural automatic stopping criterion for information-driven motion control results from the convergence analysis. We demonstrate the performance of the proposed algorithms using three scenarios: comparison of the proposed information functions and sensor configuration selection, robotic exploration in unknown environments, and a wireless signal strength monitoring task in a lake from a publicly available dataset collected using an autonomous surface vehicle.