OpenRaiser/Intern-Atlas huggingface dataset:
Order-preserving 1-string representations of planar graphs
Venue: arXiv cs.CG 2016
Year: 2016

This paper considers 1-string representations of planar graphs that are order-preserving in the sense that the order of crossings along the curve representing vertex $v$ is the same as the order of edges in the clockwise order around $v$ in the planar embedding. We show that this does not exist for all planar graphs (not even for all planar 3-trees), but show existence for some subclasses of planar partial 3-trees. In particular, for outer-planar graphs it can be order-preserving and outer-string in the sense that all ends of strings are on the outside of the representation.
The Capacity of Private Information Retrieval from Coded Databases
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of private information retrieval (PIR) over a distributed storage system. The storage system consists of $N$ non-colluding databases, each storing a coded version of $M$ messages. In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database. We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information. We show that the PIR capacity in this case is $C=\left(1+\frac{K}{N}+\frac{K^2}{N^2}+\cdots+\frac{K^{M-1}}{N^{M-1}}\right)^{-1}=(1+R_c+R_c^2+\cdots+R_c^{M-1})^{-1}=\frac{1-R_c}{1-R_c^M}$, where $R_c$ is the rate of the $(N,K)$ code used. The capacity is a function of the code rate and the number of messages only regardless of the explicit structure of the storage code. The result implies a fundamental tradeoff between the optimal retrieval cost and the storage cost. The result generalizes the achievability and converse results for the classical PIR with replicating databases to the case of coded databases.
Nonnegative autoencoder with simplified random neural network
Venue: arXiv cs.LG 2016
Year: 2016

This paper proposes new nonnegative (shallow and multi-layer) autoencoders by combining the spiking Random Neural Network (RNN) model, the network architecture typical used in deep-learning area and the training technique inspired from nonnegative matrix factorization (NMF). The shallow autoencoder is a simplified RNN model, which is then stacked into a multi-layer architecture. The learning algorithm is based on the weight update rules in NMF, subject to the nonnegative probability constraints of the RNN. The autoencoders equipped with this learning algorithm are tested on typical image datasets including the MNIST, Yale face and CIFAR-10 datasets, and also using 16 real-world datasets from different areas. The results obtained through these tests yield the desired high learning and recognition accuracy. Also, numerical simulations of the stochastic spiking behavior of this RNN auto encoder, show that it can be implemented in a highly-distributed manner.
Converse Bounds on Modulation-Estimation Performance for the Gaussian Multiple-Access Channel
Venue: arXiv cs.IT 2016
Year: 2016

This paper focuses on the problem of separately modulating and jointly estimating two independent continuous-valued parameters sent over a Gaussian multiple-access channel (MAC) under the mean square error (MSE) criterion. To this end, we first improve an existing lower bound on the MSE that is obtained using the parameter modulation-estimation techniques for the single-user additive white Gaussian noise (AWGN) channel. As for the main contribution of this work, this improved modulation-estimation analysis is generalized to the model of the two-user Gaussian MAC, which will likely become an important mathematical framework for the analysis of remote sensing problems in wireless networks. We present outer bounds to the achievable region in the plane of the MSEs of the two user parameters, which provides a trade-off between the MSEs, in addition to the upper bounds on the achievable region of the MSE exponents, namely, the exponential decay rates of these MSEs in the asymptotic regime of long blocks.
A short review and primer on using video for psychophysiological observations in human-computer interaction applications
Venue: arXiv cs.HC 2016
Year: 2016

The application of psychophysiological measures in human-computer interaction is a growing field with significant potential for future smart personalised systems. Working in this emerging field requires comprehension of an array of physiological signals and analysis techniques. An important aspect in measuring psychophysiological variables in real-world settings is the invasiveness of the measurement setup. Video is a signal which can be captured from a distance without interrupting the subject. Furthermore, the advancements in camera technologies enable detecting a growing variety of psychophysiological phenomena from a video signal with an increasing accuracy. This paper aims to serve as a primer for the novice, enabling rapid familiarisation with the latest core concepts. We put special emphasis on everyday human-computer interface applications to distinguish from the more common clinical or sports uses of psychophysiology. This paper is an extract from a comprehensive review of the entire field of ambulatory psychophysiology, including 12 similar chapters, plus application guidelines and systematic review. Thus any citation should be made using the following reference: B. Cowley, M. Filetti, K. Lukander, J. Torniainen, A. Henelius, L. Ahonen, O. Barral, I. Kosunen, T. Valtonen, M. Huotilainen, N. Ravaja, G. Jacucci. The Psychophysiology Primer: a guide to methods and a broad review with a focus on human-computer interaction. Foundations and Trends in Human-Computer Interaction, vol. 9, no. 3-4, pp. 150--307, 2016.
An Evaluation of Coarse-Grained Locking for Multicore Microkernels
Venue: arXiv cs.OS 2016
Year: 2016

The trade-off between coarse- and fine-grained locking is a well understood issue in operating systems. Coarse-grained locking provides lower overhead under low contention, fine-grained locking provides higher scalability under contention, though at the expense of implementation complexity and re- duced best-case performance. We revisit this trade-off in the context of microkernels and tightly-coupled cores with shared caches and low inter-core migration latencies. We evaluate performance on two architectures: x86 and ARM MPCore, in the former case also utilising transactional memory (Intel TSX). Our thesis is that on such hardware, a well-designed microkernel, with short system calls, can take advantage of coarse-grained locking on modern hardware, avoid the run-time and complexity cost of multiple locks, enable formal verification, and still achieve scalability comparable to fine-grained locking.
Tensor Based Second Order Variational Model for Image Reconstruction
Venue: arXiv cs.CV 2016
Year: 2016

Second order total variation (SOTV) models have advantages for image reconstruction over their first order counterparts including their ability to remove the staircase artefact in the reconstructed image, but they tend to blur the reconstructed image. To overcome this drawback, we introduce a new Tensor Weighted Second Order (TWSO) model for image reconstruction. Specifically, we develop a novel regulariser for the SOTV model that uses the Frobenius norm of the product of the SOTV Hessian matrix and the anisotropic tensor. We then adapt the alternating direction method of multipliers (ADMM) to solve the proposed model by breaking down the original problem into several subproblems. All the subproblems have closed-forms and can thus be solved efficiently. The proposed method is compared with a range of state-of-the-art approaches such as tensor-based anisotropic diffusion, total generalised variation, Euler's elastica, etc. Numerical experimental results of the method on both synthetic and real images from the Berkeley database BSDS500 demonstrate that the proposed method eliminates both the staircase and blurring effects and outperforms the existing approaches for image inpainting and denoising applications.
Decision Making Based on Cohort Scores for Speaker Verification
Venue: arXiv cs.SD 2016
Year: 2016

Decision making is an important component in a speaker verification system. For the conventional GMM-UBM architecture, the decision is usually conducted based on the log likelihood ratio of the test utterance against the GMM of the claimed speaker and the UBM. This single-score decision is simple but tends to be sensitive to the complex variations in speech signals (e.g. text content, channel, speaking style, etc.). In this paper, we propose a decision making approach based on multiple scores derived from a set of cohort GMMs (cohort scores). Importantly, these cohort scores are not simply averaged as in conventional cohort methods; instead, we employ a powerful discriminative model as the decision maker. Experimental results show that the proposed method delivers substantial performance improvement over the baseline system, especially when a deep neural network (DNN) is used as the decision maker, and the DNN input involves some statistical features derived from the cohort scores.
Online Informative Path Planning for Active Classification Using UAVs
Venue: arXiv cs.RO 2016
Year: 2016

In this paper, we introduce an informative path planning (IPP) framework for active classification using unmanned aerial vehicles (UAVs). Our algorithm uses a combination of global viewpoint selection and evolutionary optimization to refine the planned trajectory in continuous 3D space while satisfying dynamic constraints. Our approach is evaluated on the application of weed detection for precision agriculture. We model the presence of weeds on farmland using an occupancy grid and generate adaptive plans according to information-theoretic objectives, enabling the UAV to gather data efficiently. We validate our approach in simulation by comparing against existing methods, and study the effects of different planning strategies. Our results show that the proposed algorithm builds maps with over 50% lower entropy compared to traditional "lawnmower" coverage in the same amount of time. We demonstrate the planning scheme on a multirotor platform with different artificial farmland set-ups.
Scenic Routes Now: Efficiently Solving the Time-Dependent Arc Orienteering Problem
Venue: arXiv cs.DS 2016
Year: 2016

This paper extends the Arc Orienteering Problem (AOP) to large road networks with time-dependent travel times and time-dependent value gain, termed Twofold Time-Dependent AOP or 2TD-AOP for short. In its original definition, the NP-hard Orienteering Problem (OP) asks to find a path from a source to a destination maximizing the accumulated value while not exceeding a cost budget. Variations of the OP and AOP have many practical applications such as mobile crowdsourcing tasks (e.g., repairing and maintenance or dispatching field workers), diverse logistics problems (e.g., crowd control or controlling wildfires) as well as several tourist guidance problems (e.g., generating trip recommendations or navigating through theme parks). In the proposed 2TD-AOP, travel times and value functions are assumed to be time-dependent. The dynamic values model, for instance, varying rewards in crowdsourcing tasks or varying urgency levels in damage control tasks. We discuss this novel problem, prove the benefit of time-dependence empirically and present an efficient approximative solution, optimized for fast response systems. Our approach is the first time-dependent variant of the AOP to be evaluated on a large scale, fine-grained, real-world road network. We show that optimal solutions are infeasible and solutions to the static problem are often invalid. We propose an approximate dynamic programming solution which produces valid paths and is orders of magnitude faster than any optimal solution.
Benchmarking the Graphulo Processing Framework
Venue: arXiv cs.DB 2016
Year: 2016

Graph algorithms have wide applicablity to a variety of domains and are often used on massive datasets. Recent standardization efforts such as the GraphBLAS specify a set of key computational kernels that hardware and software developers can adhere to. Graphulo is a processing framework that enables GraphBLAS kernels in the Apache Accumulo database. In our previous work, we have demonstrated a core Graphulo operation called \textit{TableMult} that performs large-scale multiplication operations of database tables. In this article, we present the results of scaling the Graphulo engine to larger problems and scalablity when a greater number of resources is used. Specifically, we present two experiments that demonstrate Graphulo scaling performance is linear with the number of available resources. The first experiment demonstrates cluster processing rates through Graphulo's TableMult operator on two large graphs, scaled between $2^{17}$ and $2^{19}$ vertices. The second experiment uses TableMult to extract a random set of rows from a large graph ($2^{19}$ nodes) to simulate a cued graph analytic. These benchmarking results are of relevance to Graphulo users who wish to apply Graphulo to their graph problems.
A Transportation $L^p$ Distance for Signal Analysis
Venue: arXiv cs.CV 2016
Year: 2016

Transport based distances, such as the Wasserstein distance and earth mover's distance, have been shown to be an effective tool in signal and image analysis. The success of transport based distances is in part due to their Lagrangian nature which allows it to capture the important variations in many signal classes. However these distances require the signal to be nonnegative and normalized. Furthermore, the signals are considered as measures and compared by redistributing (transporting) them, which does not directly take into account the signal intensity. Here we study a transport-based distance, called the $TL^p$ distance, that combines Lagrangian and intensity modelling and is directly applicable to general, non-positive and multi-channelled signals. The framework allows the application of existing numerical methods. We give an overview of the basic properties of this distance and applications to classification, with multi-channelled, non-positive one and two-dimensional signals, and color transfer.
Understanding and Exploiting Object Interaction Landscapes
Venue: arXiv cs.GR 2016
Year: 2016

Interactions play a key role in understanding objects and scenes, for both virtual and real world agents. We introduce a new general representation for proximal interactions among physical objects that is agnostic to the type of objects or interaction involved. The representation is based on tracking particles on one of the participating objects and then observing them with sensors appropriately placed in the interaction volume or on the interaction surfaces. We show how to factorize these interaction descriptors and project them into a particular participating object so as to obtain a new functional descriptor for that object, its interaction landscape, capturing its observed use in a spatio-temporal framework. Interaction landscapes are independent of the particular interaction and capture subtle dynamic effects in how objects move and behave when in functional use. Our method relates objects based on their function, establishes correspondences between shapes based on functional key points and regions, and retrieves peer and partner objects with respect to an interaction.
Cut Tree Construction from Massive Graphs
Venue: arXiv cs.DS 2016
Year: 2016

The construction of cut trees (also known as Gomory-Hu trees) for a given graph enables the minimum-cut size of the original graph to be obtained for any pair of vertices. Cut trees are a powerful back-end for graph management and mining, as they support various procedures related to the minimum cut, maximum flow, and connectivity. However, the crucial drawback with cut trees is the computational cost of their construction. In theory, a cut tree is built by applying a maximum flow algorithm for $n$ times, where $n$ is the number of vertices. Therefore, naive implementations of this approach result in cubic time complexity, which is obviously too slow for today's large-scale graphs. To address this issue, in the present study, we propose a new cut-tree construction algorithm tailored to real-world networks. Using a series of experiments, we demonstrate that the proposed algorithm is several orders of magnitude faster than previous algorithms and it can construct cut trees for billion-scale graphs.
Interprocedural Semantic Change-Impact Analysis using Equivalence Relations
Venue: arXiv cs.SE 2016
Year: 2016

Change-impact analysis (CIA) is the task of determining the set of program elements impacted by a program change. Precise CIA has great potential to avoid expensive testing and code reviews for (parts of) changes that are refactorings (semantics-preserving). Existing CIA is imprecise because it is coarse-grained, deals with only few refactoring patterns, or is unaware of the change semantics. We formalize the notion of change impact in terms of the trace semantics of two program versions. We show how to leverage equivalence relations to make dataflow-based CIA aware of the change semantics, thereby improving precision in the presence of semantics-preserving changes. We propose an anytime algorithm that allows applying costly equivalence relation inference incrementally to refine the set of impacted statements. We have implemented a prototype in SymDiff, and evaluated it on 322 real-world changes from open-source projects and benchmark programs used by prior research. The evaluation results show an average 35% improvement in the size of the set of impacted statements compared to standard dataflow-based techniques.
Scalable Discrete Supervised Hash Learning with Asymmetric Matrix Factorization
Venue: arXiv cs.CV 2016
Year: 2016

Hashing method maps similar data to binary hashcodes with smaller hamming distance, and it has received a broad attention due to its low storage cost and fast retrieval speed. However, the existing limitations make the present algorithms difficult to deal with large-scale datasets: (1) discrete constraints are involved in the learning of the hash function; (2) pairwise or triplet similarity is adopted to generate efficient hashcodes, resulting both time and space complexity are greater than O(n^2). To address these issues, we propose a novel discrete supervised hash learning framework which can be scalable to large-scale datasets. First, the discrete learning procedure is decomposed into a binary classifier learning scheme and binary codes learning scheme, which makes the learning procedure more efficient. Second, we adopt the Asymmetric Low-rank Matrix Factorization and propose the Fast Clustering-based Batch Coordinate Descent method, such that the time and space complexity is reduced to O(n). The proposed framework also provides a flexible paradigm to incorporate with arbitrary hash function, including deep neural networks and kernel methods. Experiments on large-scale datasets demonstrate that the proposed method is superior or comparable with state-of-the-art hashing algorithms.
Video Summarization using Deep Semantic Features
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents a video summarization technique for an Internet video to provide a quick way to overview its content. This is a challenging problem because finding important or informative parts of the original video requires to understand its content. Furthermore the content of Internet videos is very diverse, ranging from home videos to documentaries, which makes video summarization much more tough as prior knowledge is almost not available. To tackle this problem, we propose to use deep video features that can encode various levels of content semantics, including objects, actions, and scenes, improving the efficiency of standard video summarization techniques. For this, we design a deep neural network that maps videos as well as descriptions to a common semantic space and jointly trained it with associated pairs of videos and descriptions. To generate a video summary, we extract the deep features from each segment of the original video and apply a clustering-based summarization technique to them. We evaluate our video summaries using the SumMe dataset as well as baseline approaches. The results demonstrated the advantages of incorporating our deep semantic features in a video summarization technique.
Ignoring Extreme Opinions in Complex Networks: The Impact of Heterogeneous Thresholds
Venue: arXiv cs.SI 2016
Year: 2016

We consider a class of opinion dynamics on networks where at each time-step, each node in the network disregards the opinions of a certain number of its most extreme neighbors and updates its own opinion as a weighted average of the remaining opinions. When all nodes disregard the same number of extreme neighbors, previous work has shown that consensus will be reached if and only if the network satisfies certain topological properties. In this paper, we consider the implications of allowing each node to have a personal threshold for the number of extreme neighbors to ignore. We provide graph conditions under which consensus is guaranteed for such dynamics. We then study random networks where each node's threshold is drawn from a certain distribution, and provide conditions on that distribution, together with conditions on the edge formation probability, that guarantee that consensus will be reached asymptotically almost surely.
Using Natural Language Processing and Qualitative Analysis to Intervene in Gang Violence: A Collaboration Between Social Work Researchers and Data Scientists
Venue: arXiv cs.CY 2016
Year: 2016

The U.S. has the highest rate of firearm-related deaths when compared to other industrialized countries. Violence particularly affects low-income, urban neighborhoods in cities like Chicago, which saw a 40% increase in firearm violence from 2014 to 2015 to more than 3,000 shooting victims. While recent studies have found that urban, gang-involved individuals curate a unique and complex communication style within and between social media platforms, organizations focused on reducing gang violence are struggling to keep up with the growing complexity of social media platforms and the sheer volume of data they present. In this paper, describe the Digital Urban Violence Analysis Approach (DUVVA), a collaborative qualitative analysis method used in a collaboration between data scientists and social work researchers to develop a suite of systems for decoding the high- stress language of urban, gang-involved youth. Our approach leverages principles of grounded theory when analyzing approximately 800 tweets posted by Chicago gang members and participation of youth from Chicago neighborhoods to create a language resource for natural language processing (NLP) methods. In uncovering the unique language and communication style, we developed automated tools with the potential to detect aggressive language on social media and aid individuals and groups in performing violence prevention and interruption.
Effective Combination of Language and Vision Through Model Composition and the R-CCA Method
Venue: arXiv cs.CL 2016
Year: 2016

We address the problem of integrating textual and visual information in vector space models for word meaning representation. We first present the Residual CCA (R-CCA) method, that complements the standard CCA method by representing, for each modality, the difference between the original signal and the signal projected to the shared, max correlation, space. We then show that constructing visual and textual representations and then post-processing them through composition of common modeling motifs such as PCA, CCA, R-CCA and linear interpolation (a.k.a sequential modeling) yields high quality models. On five standard semantic benchmarks our sequential models outperform recent multimodal representation learning alternatives, including ones that rely on joint representation learning. For two of these benchmarks our R-CCA method is part of the Best configuration our algorithm yields.