OpenRaiser/Intern-Atlas huggingface dataset:
The Power of Choice in Priority Scheduling
Venue: arXiv cs.DS 2017
Year: 2017

Consider the following random process: we are given $n$ queues, into which elements of increasing labels are inserted uniformly at random. To remove an element, we pick two queues at random, and remove the element of lower label (higher priority) among the two. The cost of a removal is the rank of the label removed, among labels still present in any of the queues, that is, the distance from the optimal choice at each step. Variants of this strategy are prevalent in state-of-the-art concurrent priority queue implementations. Nonetheless, it is not known whether such implementations provide any rank guarantees, even in a sequential model. We answer this question, showing that this strategy provides surprisingly strong guarantees: Although the single-choice process, where we always insert and remove from a single randomly chosen queue, has degrading cost, going to infinity as we increase the number of steps, in the two choice process, the expected rank of a removed element is $O( n )$ while the expected worst-case cost is $O( n \log n )$. These bounds are tight, and hold irrespective of the number of steps for which we run the process. The argument is based on a new technical connection between "heavily loaded" balls-into-bins processes and priority scheduling. Our analytic results inspire a new concurrent priority queue implementation, which improves upon the state of the art in terms of practical performance.
Decentralized creation of academic documents using a Network Attached Storage (NAS) server
Venue: arXiv cs.DL 2017
Year: 2017

Scholarly document creation continues to face various obstacles. Scholarly text production requires more complex word processors than other forms of texts because of the complex structures of citations, formulas and figures. The need for peer review, often single-blind or double-blind, creates needs for document management that other texts do not require. Additionally, the need for collaborative editing, security and strict document access rules means that many existing word processors are imperfect solutions for academics. Nevertheless, most papers continue to be written using Microsoft Word (Sadeghi et al. 2017). We here analyze some of the problems with existing academic solutions and then present an argument why we believe that running an open source academic writing solution for academic purposes, such as Fidus Writer, on a Network Attached Storage (NAS) server could be a viable alternative.
Identifying Spatial Relations in Images using Convolutional Neural Networks
Venue: arXiv cs.AI 2017
Year: 2017

Traditional approaches to building a large scale knowledge graph have usually relied on extracting information (entities, their properties, and relations between them) from unstructured text (e.g. Dbpedia). Recent advances in Convolutional Neural Networks (CNN) allow us to shift our focus to learning entities and relations from images, as they build robust models that require little or no pre-processing of the images. In this paper, we present an approach to identify and extract spatial relations (e.g., The girl is standing behind the table) from images using CNNs. Our research addresses two specific challenges: providing insight into how spatial relations are learned by the network and which parts of the image are used to predict these relations. We use the pre-trained network VGGNet to extract features from an image and train a Multi-layer Perceptron (MLP) on a set of synthetic images and the sun09 dataset to extract spatial relations. The MLP predicts spatial relations without a bounding box around the objects or the space in the image depicting the relation. To understand how the spatial relations are represented in the network, a heatmap is overlayed on the image to show the regions that are deemed important by the network. Also, we analyze the MLP to show the relationship between the activation of consistent groups of nodes and the prediction of a spatial relation. We show how the loss of these groups affects the networks ability to identify relations.
RoboCup 2D Soccer Simulation League: Evaluation Challenges
Venue: arXiv cs.MA 2017
Year: 2017

We summarise the results of RoboCup 2D Soccer Simulation League in 2016 (Leipzig), including the main competition and the evaluation round. The evaluation round held in Leipzig confirmed the strength of RoboCup-2015 champion (WrightEagle, i.e. WE2015) in the League, with only eventual finalists of 2016 competition capable of defeating WE2015. An extended, post-Leipzig, round-robin tournament which included the top 8 teams of 2016, as well as WE2015, with over 1000 games played for each pair, placed WE2015 third behind the champion team (Gliders2016) and the runner-up (HELIOS2016). This establishes WE2015 as a stable benchmark for the 2D Simulation League. We then contrast two ranking methods and suggest two options for future evaluation challenges. The first one, "The Champions Simulation League", is proposed to include 6 previous champions, directly competing against each other in a round-robin tournament, with the view to systematically trace the advancements in the League. The second proposal, "The Global Challenge", is aimed to increase the realism of the environmental conditions during the simulated games, by simulating specific features of different participating countries.
Hierarchical Gaussian Descriptors with Application to Person Re-Identification
Venue: arXiv cs.CV 2017
Year: 2017

Describing the color and textural information of a person image is one of the most crucial aspects of person re-identification (re-id). In this paper, we present novel meta-descriptors based on a hierarchical distribution of pixel features. Although hierarchical covariance descriptors have been successfully applied to image classification, the mean information of pixel features, which is absent from the covariance, tends to be the major discriminative information for person re-id. To solve this problem, we describe a local region in an image via hierarchical Gaussian distribution in which both means and covariances are included in their parameters. More specifically, the region is modeled as a set of multiple Gaussian distributions in which each Gaussian represents the appearance of a local patch. The characteristics of the set of Gaussians are again described by another Gaussian distribution. In both steps, we embed the parameters of the Gaussian into a point of Symmetric Positive Definite (SPD) matrix manifold. By changing the way to handle mean information in this embedding, we develop two hierarchical Gaussian descriptors. Additionally, we develop feature norm normalization methods with the ability to alleviate the biased trends that exist on the descriptors. The experimental results conducted on five public datasets indicate that the proposed descriptors achieve remarkably high performance on person re-id.
WLS-Based Self-Localization Using Perturbed Anchor Positions and RSSI Measurements
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of self-localization by a resource-constrained node within a network given radio signal strength indicator (RSSI) measurements from a set of anchor nodes where the RSSI measurements as well as the anchor position information are subject to perturbation. In order to achieve a computationally efficient estimate for the unknown position, we minimize a weighted sum-square-distance-error cost function in an iterative fashion utilizing the gradient-descent method. We calculate the weights in the cost function by taking into account perturbations in both RSSI measurements and anchor node position information while assuming normal distribution for the perturbations in the anchor node position information and log-normal distribution for the RSSI-induced distance estimates. The latter assumption is due to considering the log-distance path-loss model with normally-distributed perturbations for the RSSI measurements in the logarithmic scale. We also derive the Cramer-Rao lower bound associated with the considered position estimation problem. We evaluate the performance of the proposed algorithm considering various arbitrary network topologies and compare it with an existing algorithm that is based on a similar approach but only accounts for perturbations in the RSSI measurements. The experimental results show that the proposed algorithm yields significant improvement in localization performance over the existing algorithm while maintaining its computational efficiency. This makes the proposed algorithm suitable for real-world applications where the information available about the positions of anchor nodes often suffer from uncertainty due to observational noise or error and the computational and energy resources of mobile nodes are limited, prohibiting the use of more sophisticated techniques such as those based on semidefinite or second-order cone programming.
Sequential Channel Estimation in the Presence of Random Phase Noise in NB-IoT Systems
Venue: arXiv cs.IT 2017
Year: 2017

We consider channel estimation (CE) in narrowband Internet-of-Things (NB-IoT) systems. Due to the fluctuations in phase within receiver and transmitter oscillators, and also the residual frequency offset (FO) caused by discontinuous receiving of repetition coded transmit data-blocks, random phase noises are presented in received signals. Although the coherent-time of fading channel can be assumed fairly long due to the low-mobility of NB-IoT user-equipments (UEs), such phase noises have to be considered before combining the the channel estimates over repetition copies to improve their accuracies. In this paper, we derive a sequential minimum-mean-square-error (MMSE) channel estimator in the presence of random phase noise that refines the CE sequentially with each received repetition copy, which has a low-complexity and a small data storage. Further, we show through simulations that, the proposed sequential MMSE estimator improves the mean-square-error (MSE) of CE by 1 dB in the low signal-to-noise ratio (SNR) regime, compared to a traditional sequential MMSE estimator that does not thoroughly consider the impact of random phase noises.
Recommending links through influence maximization
Venue: arXiv cs.DS 2017
Year: 2017

The link recommendation problem consists in suggesting a set of links to the users of a social network in order to increase their social circles and the connectivity of the network. Link recommendation is extensively studied in the context of social networks and of general complex networks due to its wide range of applications. Most of the existing link recommendation methods estimate the likelihood that a link is adopted by users and recommend links that are likely to be established. However, most of such methods overlook the impact that the suggested links have on the capability of the network to spread information. Indeed, such capability is directly correlated with both the engagement of a single user and the revenue of online social networks. In this paper, we study link recommendation systems from the point of view of information diffusion. In detail, we consider the problem in which we are allowed to spend a given budget to create new links so to suggest a bounded number of possible persons to whom become friend in order to maximize the influence of a given set of nodes. We model the influence diffusion in a network with the popular Independent Cascade model.
On Distributed Power Control for Uncoordinated Dual Energy Harvesting Links: Performance Bounds and Near-Optimal Policies
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we consider a point-to-point link between an energy harvesting transmitter and receiver, where neither node has the information about the battery state or energy availability at the other node. We consider a model where data is successfully delivered only in slots where both nodes are active. Energy loss occurs whenever one node turns on while the other node is in sleep mode. In each slot, based on their own energy availability, the transmitter and receiver need to independently decide whether or not to turn on, with the aim of maximizing the long-term time-average throughput. We present an upper bound on the throughput achievable by analyzing a genie-aided system that has noncausal knowledge of the energy arrivals at both the nodes. Next, we propose an online policy requiring an occasional one-bit feedback whose throughput is within one bit of the upper bound, asymptotically in the battery size. In order to further reduce the feedback required, we propose a time-dilated version of the online policy. As the time dilation gets large, this policy does not require any feedback and achieves the upper bound asymptotically in the battery size. Inspired by this, we also propose a near-optimal fully uncoordinated policy. We use Monte Carlo simulations to validate our theoretical results and illustrate the performance of the proposed policies.
On Error Detection in Asymmetric Channels
Venue: arXiv cs.IT 2017
Year: 2017

We study the error detection problem in $ q $-ary asymmetric channels wherein every input symbol $ x_i $ is mapped to an output symbol $ y_i $ satisfying $ y_i \geq x_i $. A general setting is assumed where the noise vectors are (potentially) restricted in: 1) the amplitude, $ y_i - x_i \leq a $, 2) the Hamming weight, $ \sum_{i=1}^n 1_{\{y_i \neq x_i\}} \leq h $, and 3) the total weight, $ \sum_{i=1}^n (y_i - x_i) \leq t $. Optimal codes detecting these types of errors are described for certain sets of parameters $ a, h, t $, both in the standard and in the cyclic ($ \operatorname{mod}\, q $) version of the problem. It is also demonstrated that these codes are optimal in the large alphabet limit for every $ a, h, t $ and every block-length $ n $.
Delta Complexes in Digital Images. Approximating Image Object Shapes
Venue: arXiv cs.CG 2017
Year: 2017

In a computational topology of digital images, simplexes are replaced by Delta sets in approximating image object shapes. For simplicity, simplexes and Delta sets are restricted to the Euclidean plane. A planar simplex is either a vertex, a line segment or a filled triangle. In this study of image shapes, a planar Delta set is a sequence of ordered simplicial complexes. The basic approach is to approximate an image shape by decomposing an image region containing the shape into combinations of Delta sets called Delta complexes. This approach to image shapes is motivated by the ease with which shapes covered by Delta complexes can be measured and compared. A number of basic results directly related to shape analysis are also given in the context of Delta complex proximities.
Translating Event-B machines to Eiffel programs
Venue: arXiv cs.SE 2017
Year: 2017

Formal modelling languages play a key role in the development of software since they enable users to prove correctness of system properties. However, there is still not a clear understanding on how to map a formal model to a specific programming language. In order to propose a solution, this paper presents a source-to-source mapping between Event- B models and Eiffel programs, therefore enabling the proof of correctness of certain system properties via Design-by-Contract (natively supported by Eiffel), while still making use of all features of O-O programming.
Context-Aware System Synthesis, Task Assignment, and Routing
Venue: arXiv cs.RO 2017
Year: 2017

The design and organization of complex robotic systems traditionally requires laborious trial-and-error processes to ensure both hardware and software components are correctly connected with the resources necessary for computation. This paper presents a novel generalization of the quadratic assignment and routing problem, introducing formalisms for selecting components and interconnections to synthesize a complete system capable of providing some user-defined functionality. By introducing mission context, functional requirements, and modularity directly into the assignment problem, we derive a solution where components are automatically selected and then organized into an optimal hardware and software interconnection structure, all while respecting restrictions on component viability and required functionality. The ability to generate \emph{complete} functional systems directly from individual components reduces manual design effort by allowing for a guided exploration of the design space. Additionally, our formulation increases resiliency by quantifying resource margins and enabling adaptation of system structure in response to changing environments, hardware or software failure. The proposed formulation is cast as an integer linear program which is provably $\mathcal{NP}$-hard. Two case studies are developed and analyzed to highlight the expressiveness and complexity of problems that can be addressed by this approach: the first explores the iterative development of a ground-based search-and-rescue robot in a variety of mission contexts, while the second explores the large-scale, complex design of a humanoid disaster robot for the DARPA Robotics Challenge. Numerical simulations quantify real world performance and demonstrate tractable time complexity for the scale of problems encountered in many modern robotic systems.
A distributed algorithm for average aggregative games with coupling constraints
Venue: arXiv cs.SY 2017
Year: 2017

We consider the framework of average aggregative games, where the cost function of each agent depends on his own strategy and on the average population strategy. We focus on the case in which the agents are coupled not only via their cost functions, but also via constraints coupling their strategies. We propose a distributed algorithm that achieves an almost Nash equilibrium by requiring only local communications of the agents, as specified by a sparse communication network. The proof of convergence of the algorithm relies on the auxiliary class of network aggregative games and exploits a novel result of parametric convergence of variational inequalities, which is applicable beyond the context of games. We apply our theoretical findings to a multi-market Cournot game with transportation costs and maximum market capacity.
Pseudo-deterministic Proofs
Venue: arXiv cs.CC 2017
Year: 2017

We introduce pseudo-deterministic interactive proofs (psdAM): interactive proof systems for search problems where the verifier is guaranteed with high probability to output the same output on different executions. As in the case with classical interactive proofs, the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover. We view pseudo-deterministic interactive proofs as an extension of the study of pseudo-deterministic randomized polynomial time algorithms: the goal of the latter is to find canonical solutions to search problems whereas the goal of the former is to prove that a solution to a search problem is canonical to a probabilistic polynomial time verifier. Alternatively, one may think of the powerful prover as aiding the probabilistic polynomial time verifier to find canonical solutions to search problems, with high probability over the randomness of the verifier. The challenge is that pseudo-determinism should hold not only with respect to the randomness, but also with respect to the prover: a malicious prover should not be able to cause the verifier to output a solution other than the unique canonical one.
Feature Enhancement in Visually Impaired Images
Venue: arXiv cs.CV 2017
Year: 2017

One of the major open problems in computer vision is detection of features in visually impaired images. In this paper, we describe a potential solution using Phase Stretch Transform, a new computational approach for image analysis, edge detection and resolution enhancement that is inspired by the physics of the photonic time stretch technique. We mathematically derive the intrinsic nonlinear transfer function and demonstrate how it leads to (1) superior performance at low contrast levels and (2) a reconfigurable operator for hyper-dimensional classification. We prove that the Phase Stretch Transform equalizes the input image brightness across the range of intensities resulting in a high dynamic range in visually impaired images. We also show further improvement in the dynamic range by combining our method with the conventional techniques. Finally, our results show a method for computation of mathematical derivatives via group delay dispersion operations.
Recent Progress of Face Image Synthesis
Venue: arXiv cs.CV 2017
Year: 2017

Face synthesis has been a fascinating yet challenging problem in computer vision and machine learning. Its main research effort is to design algorithms to generate photo-realistic face images via given semantic domain. It has been a crucial prepossessing step of main-stream face recognition approaches and an excellent test of AI ability to use complicated probability distributions. In this paper, we provide a comprehensive review of typical face synthesis works that involve traditional methods as well as advanced deep learning approaches. Particularly, Generative Adversarial Net (GAN) is highlighted to generate photo-realistic and identity preserving results. Furthermore, the public available databases and evaluation metrics are introduced in details. We end the review with discussing unsolved difficulties and promising directions for future research.
Holistic Planimetric prediction to Local Volumetric prediction for 3D Human Pose Estimation
Venue: arXiv cs.CV 2017
Year: 2017

We propose a novel approach to 3D human pose estimation from a single depth map. Recently, convolutional neural network (CNN) has become a powerful paradigm in computer vision. Many of computer vision tasks have benefited from CNNs, however, the conventional approach to directly regress 3D body joint locations from an image does not yield a noticeably improved performance. In contrast, we formulate the problem as estimating per-voxel likelihood of key body joints from a 3D occupancy grid. We argue that learning a mapping from volumetric input to volumetric output with 3D convolution consistently improves the accuracy when compared to learning a regression from depth map to 3D joint coordinates. We propose a two-stage approach to reduce the computational overhead caused by volumetric representation and 3D convolution: Holistic 2D prediction and Local 3D prediction. In the first stage, Planimetric Network (P-Net) estimates per-pixel likelihood for each body joint in the holistic 2D space. In the second stage, Volumetric Network (V-Net) estimates the per-voxel likelihood of each body joints in the local 3D space around the 2D estimations of the first stage, effectively reducing the computational cost. Our model outperforms existing methods by a large margin in publicly available datasets.
Mapping higher-order network flows in memory and multilayer networks with Infomap
Venue: arXiv cs.SI 2017
Year: 2017

Comprehending complex systems by simplifying and highlighting important dynamical patterns requires modeling and mapping higher-order network flows. However, complex systems come in many forms and demand a range of representations, including memory and multilayer networks, which in turn call for versatile community-detection algorithms to reveal important modular regularities in the flows. Here we show that various forms of higher-order network flows can be represented in a unified way with networks that distinguish physical nodes for representing a~complex system's objects from state nodes for describing flows between the objects. Moreover, these so-called sparse memory networks allow the information-theoretic community detection method known as the map equation to identify overlapping and nested flow modules in data from a range of~different higher-order interactions such as multistep, multi-source, and temporal data. We derive the map equation applied to sparse memory networks and describe its search algorithm Infomap, which can exploit the flexibility of sparse memory networks. Together they provide a general solution to reveal overlapping modular patterns in higher-order flows through complex systems.