OpenRaiser/Intern-Atlas huggingface dataset:
Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
Venue: arXiv cs.DS 2017
Year: 2017

Given a graph $G$ and a parameter $k$, the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset $U\subseteq V(G)$ of size at most $k$ that hits all induced cycles of size at least 4. The existence of a polynomial kernel for CVD was a well-known open problem in the field of Parameterized Complexity. Recently, Jansen and Pilipczuk resolved this question affirmatively by designing a polynomial kernel for CVD of size $O(k^{161}\log^{58}k)$, and asked whether one can design a kernel of size $O(k^{10})$. While we do not completely resolve this question, we design a significantly smaller kernel of size $O(k^{12}\log^{10}k)$, inspired by the $O(k^2)$-size kernel for Feedback Vertex Set. Furthermore, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution.
Towards Physiology-Aware DASH: Bandwidth-Compliant Prioritized Clinical Multimedia Communication in Ambulances
Venue: arXiv cs.NI 2017
Year: 2017

The ultimate objective of medical cyber-physical systems is to enhance the safety and effectiveness of patient care. To ensure safe and effective care during emergency patient transfer from rural areas to center tertiary hospitals, reliable and real-time communication is essential. Unfortunately, real-time monitoring of patients involves transmission of various clinical multimedia data including videos, medical images, and vital signs, which requires use of mobile network with high-fidelity communication bandwidth. However, the wireless networks along the roads in rural areas range from 4G to 2G to low speed satellite links, which poses a significant challenge to transmit critical patient information. In this paper, we present a bandwidth-compliant criticality-aware system for transmission of massive clinical multimedia data adaptive to varying bandwidths during patient transport. Model-based clinical automata are used to determine the criticality of clinical multimedia data. We borrow concepts from DASH, and propose physiology-aware adaptation techniques to transmit more critical clinical data with higher fidelity in response to changes in disease, clinical states, and bandwidth condition. In collaboration with Carle's ambulance service center, we develop a bandwidth profiler, and use it as proof of concept to support our experiments. Our preliminary evaluation results show that our solutions ensure that most critical patient's clinical data are communicated with higher fidelity.
Online Multi-Armed Bandit
Venue: arXiv cs.AI 2017
Year: 2017

We introduce a novel variant of the multi-armed bandit problem, in which bandits are streamed one at a time to the player, and at each point, the player can either choose to pull the current bandit or move on to the next bandit. Once a player has moved on from a bandit, they may never visit it again, which is a crucial difference between our problem and classic multi-armed bandit problems. In this online context, we study Bernoulli bandits (bandits with payout Ber($p_i$) for some underlying mean $p_i$) with underlying means drawn i.i.d. from various distributions, including the uniform distribution, and in general, all distributions that have a CDF satisfying certain differentiability conditions near zero. In all cases, we suggest several strategies and investigate their expected performance. Furthermore, we bound the performance of any optimal strategy and show that the strategies we have suggested are indeed optimal up to a constant factor. We also investigate the case where the distribution from which the underlying means are drawn is not known ahead of time. We again, are able to suggest algorithms that are optimal up to a constant factor for this case, given certain mild conditions on the universe of distributions.
Line-Recovery by Programmable Particles
Venue: arXiv cs.DC 2017
Year: 2017

Shape formation has been recently studied in distributed systems of programmable particles. In this paper we consider the shape recovery problem of restoring the shape when $f$ of the $n$ particles have crashed. We focus on the basic line shape, used as a tool for the construction of more complex configurations. We present a solution to the line recovery problem by the non-faulty anonymous particles; the solution works regardless of the initial distribution and number $f<n-4$ of faults, of the local orientations of the non-faulty entities, and of the number of non-faulty entities activated in each round (i.e., semi-synchronous adversarial scheduler).
When You Must Forget: beyond strong persistence when forgetting in answer set programming
Venue: arXiv cs.AI 2017
Year: 2017

Among the myriad of desirable properties discussed in the context of forgetting in Answer Set Programming (ASP), strong persistence naturally captures its essence. Recently, it has been shown that it is not always possible to forget a set of atoms from a program while obeying this property, and a precise criterion regarding what can be forgotten has been presented, accompanied by a class of forgetting operators that return the correct result when forgetting is possible. However, it is an open question what to do when we have to forget a set of atoms, but cannot without violating this property. In this paper, we address this issue and investigate three natural alternatives to forget when forgetting without violating strong persistence is not possible, which turn out to correspond to the different possible relaxations of the characterization of strong persistence. Additionally, we discuss their preferable usage, shed light on the relation between forgetting and notions of relativized equivalence established earlier in the context of ASP, and present a detailed study on their computational complexity.
On the analysis of signals in a permutation Lempel-Ziv complexity - permutation Shannon entropy plane
Venue: arXiv cs.IT 2017
Year: 2017

The aim of this paper is to introduce the Lempel-Ziv permutation complexity vs permutation entropy plane as a tool to analyze time series of different nature. This two quantities make use of the Bandt and Pompe representation to quantify continuous-state time series. The strength of this plane is to combine two different perspectives to analyze a signal, one being statistic (the permutation entropy) and the other being deterministic (the Lempel-Ziv complexity). This representation is applied (i) to characterize non-linear chaotic maps, (ii) to distinguish deterministic from stochastic processes and (iii) to analyze and differentiate fractional Brownian motion from fractional Gaussian noise and K-noise given a same (averaged) spectrum. The results allow to conclude that this plane is "robust" to distinguish chaotic signals from random signals, as well as to discriminate between different Gaussian and nonGaussian noises.
An Empirical Analysis of the Influence of Fault Space on Search-Based Automated Program Repair
Venue: arXiv cs.SE 2017
Year: 2017

Automated program repair (APR) has attracted great research attention, and various techniques have been proposed. Search-based APR is one of the most important categories among these techniques. Existing researches focus on the design of effective mutation operators and searching algorithms to better find the correct patch. Despite various efforts, the effectiveness of these techniques are still limited by the search space explosion problem. One of the key factors attribute to this problem is the quality of fault spaces as reported by existing studies. This motivates us to study the importance of the fault space to the success of finding a correct patch. Our empirical study aims to answer three questions. Does the fault space significantly correlate with the performance of search-based APR? If so, are there any indicative measurements to approximate the accuracy of the fault space before applying expensive APR techniques? Are there any automatic methods that can improve the accuracy of the fault space? We observe that the accuracy of the fault space affects the effectiveness and efficiency of search-based APR techniques, e.g., the failure rate of GenProg could be as high as $60\%$ when the real fix location is ranked lower than 10 even though the correct patch is in the search space. Besides, GenProg is able to find more correct patches and with fewer trials when given a fault space with a higher accuracy. We also find that the negative mutation coverage, which is designed in this study to measure the capability of a test suite to kill the mutants created on the statements executed by failing tests, is the most indicative measurement to estimate the efficiency of search-based APR. Finally, we confirm that automated generated test cases can help improve the accuracy of fault spaces, and further improve the performance of search-based APR techniques.
Towards Fast-Convergence, Low-Delay and Low-Complexity Network Optimization
Venue: arXiv cs.NI 2017
Year: 2017

Distributed network optimization has been studied for well over a decade. However, we still do not have a good idea of how to design schemes that can simultaneously provide good performance across the dimensions of utility optimality, convergence speed, and delay. To address these challenges, in this paper, we propose a new algorithmic framework with all these metrics approaching optimality. The salient features of our new algorithm are three-fold: (i) fast convergence: it converges with only $O(\log(1/ε))$ iterations that is the fastest speed among all the existing algorithms; (ii) low delay: it guarantees optimal utility with finite queue length; (iii) simple implementation: the control variables of this algorithm are based on virtual queues that do not require maintaining per-flow information. The new technique builds on a kind of inexact Uzawa method in the Alternating Directional Method of Multiplier, and provides a new theoretical path to prove global and linear convergence rate of such a method without requiring the full rank assumption of the constraint matrix.
Cooperative Hierarchical Dirichlet Processes: Superposition vs. Maximization
Venue: arXiv cs.LG 2017
Year: 2017

The cooperative hierarchical structure is a common and significant data structure observed in, or adopted by, many research areas, such as: text mining (author-paper-word) and multi-label classification (label-instance-feature). Renowned Bayesian approaches for cooperative hierarchical structure modeling are mostly based on topic models. However, these approaches suffer from a serious issue in that the number of hidden topics/factors needs to be fixed in advance and an inappropriate number may lead to overfitting or underfitting. One elegant way to resolve this issue is Bayesian nonparametric learning, but existing work in this area still cannot be applied to cooperative hierarchical structure modeling. In this paper, we propose a cooperative hierarchical Dirichlet process (CHDP) to fill this gap. Each node in a cooperative hierarchical structure is assigned a Dirichlet process to model its weights on the infinite hidden factors/topics. Together with measure inheritance from hierarchical Dirichlet process, two kinds of measure cooperation, i.e., superposition and maximization, are defined to capture the many-to-many relationships in the cooperative hierarchical structure. Furthermore, two constructive representations for CHDP, i.e., stick-breaking and international restaurant process, are designed to facilitate the model inference. Experiments on synthetic and real-world data with cooperative hierarchical structures demonstrate the properties and the ability of CHDP for cooperative hierarchical structure modeling and its potential for practical application scenarios.
Distributed Bi-level Energy Allocation Mechanism with Grid Constraints and Hidden User Information
Venue: arXiv cs.SY 2017
Year: 2017

A novel distributed energy allocation mechanism for Distribution System Operator (DSO) market through a bi-level iterative auction is proposed. With the locational marginal price at the substation node known, the DSO runs an upper level auction with aggregators as intermediate agents competing for energy. This DSO level auction takes into account physical grid constraints such as line flows, transformer capacities and node voltage limits. This auction mechanism is a straightforward implementation of projected gradient descent on the social welfare (SW) of all home level agents. Aggregators, which serve home level agents - both buyers and sellers, implement lower level auctions in parallel, through proportional allocation and without asking for utility functions and generation capacities that are considered private information. The overall bi-level auction is shown to be efficient and weakly budget balanced.
Control of an Internet-based Robot System Using the Real-time Transport Protocol
Venue: arXiv cs.RO 2017
Year: 2017

In this paper, we introduce a novel approach in controlling robot systems over the Internet. The Real-time Transport Protocol (RTP) is used as the communication protocol instead of traditionally using TCP and UDP. The theoretic analyses, the simulation studies and the experimental implementation have been performed to evaluate the feasibility and effectiveness of the proposed approach for practical uses.
Energy-Efficient Strip Monitoring by Identical Devices Directed to One Side Along the Strip and Having a Coverage Area in the Form of a Sector
Venue: arXiv cs.CG 2017
Year: 2017

In this paper, we propose several regular covers with identical sectors that observe the strip in the same direction, and we carried out their analysis, which allows choosing the best coverage model and the best parameters of the sector.
Coresets for Triangulation
Venue: arXiv cs.CG 2017
Year: 2017

Multiple-view triangulation by $\ell_{\infty}$ minimisation has become established in computer vision. State-of-the-art $\ell_{\infty}$ triangulation algorithms exploit the quasiconvexity of the cost function to derive iterative update rules that deliver the global minimum. Such algorithms, however, can be computationally costly for large problem instances that contain many image measurements, e.g., from web-based photo sharing sites or long-term video recordings. In this paper, we prove that $\ell_{\infty}$ triangulation admits a coreset approximation scheme, which seeks small representative subsets of the input data called coresets. A coreset possesses the special property that the error of the $\ell_{\infty}$ solution on the coreset is within known bounds from the global minimum. We establish the necessary mathematical underpinnings of the coreset algorithm, specifically, by enacting the stopping criterion of the algorithm and proving that the resulting coreset gives the desired approximation accuracy. On large-scale triangulation problems, our method provides theoretically sound approximate solutions. Iterated until convergence, our coreset algorithm is also guaranteed to reach the true optimum. On practical datasets, we show that our technique can in fact attain the global minimiser much faster than current methods
Realistic Indoor Path Loss Modeling for Regular WiFi Operations in India
Venue: arXiv cs.NI 2017
Year: 2017

Indoor wireless communication using Wireless Fidelity (WiFi) is becoming a major need for the success of Internet of Things (IoT) and cloud robotics in both developed and developing countries. With different operating conditions, interference, obstacles and type of building materials used, it is difficult to predict the path loss components in an indoor environment, which are crucial for the network design. It has been observed that the indoor path loss models proposed for western countries cannot be directly used in Indian scenarios due to variations in building materials utilized, floor plans, etc. In this paper, we have proposed a non-deterministic statistical indoor path loss model- Tata Indoor Path Loss Model (T-IPLM) which can be used for the 2.4 - 2.5 GHz, Industrial Scientific and Medical (ISM) band. To propose and validate, we have conducted several drive tests with different conditions such as busy office premise with obstacles, open office premise, corridor, canteen, and multi-storey office locations, etc. We have also compared T-IPLM with popular path loss models such as ITU-R and Log-distance; T-IPLM matches closely with the drive test results as compared to other models. We believe that T-IPLM model can be used extensively to design accurate indoor communication networks required for regular WiFi communications and deployment and operations of IoT and cloud robotics.
Fast Screening Algorithm for Rotation and Scale Invariant Template Matching
Venue: arXiv cs.CV 2017
Year: 2017

This paper presents a generic pre-processor for expediting conventional template matching techniques. Instead of locating the best matched patch in the reference image to a query template via exhaustive search, the proposed algorithm rules out regions with no possible matches with minimum computational efforts. While working on simple patch features, such as mean, variance and gradient, the fast pre-screening is highly discriminative. Its computational efficiency is gained by using a novel octagonal-star-shaped template and the inclusion-exclusion principle to extract and compare patch features. Moreover, it can handle arbitrary rotation and scaling of reference images effectively. Extensive experiments demonstrate that the proposed algorithm greatly reduces the search space while never missing the best match.
Empirical evaluation of a Q-Learning Algorithm for Model-free Autonomous Soaring
Venue: arXiv cs.LG 2017
Year: 2017

Autonomous unpowered flight is a challenge for control and guidance systems: all the energy the aircraft might use during flight has to be harvested directly from the atmosphere. We investigate the design of an algorithm that optimizes the closed-loop control of a glider's bank and sideslip angles, while flying in the lower convective layer of the atmosphere in order to increase its mission endurance. Using a Reinforcement Learning approach, we demonstrate the possibility for real-time adaptation of the glider's behaviour to the time-varying and noisy conditions associated with thermal soaring flight. Our approach is online, data-based and model-free, hence avoids the pitfalls of aerological and aircraft modelling and allow us to deal with uncertainties and non-stationarity. Additionally, we put a particular emphasis on keeping low computational requirements in order to make on-board execution feasible. This article presents the stochastic, time-dependent aerological model used for simulation, together with a standard aircraft model. Then we introduce an adaptation of a Q-learning algorithm and demonstrate its ability to control the aircraft and improve its endurance by exploiting updrafts in non-stationary scenarios.
Hashed Binary Search Sampling for Convolutional Network Training with Large Overhead Image Patches
Venue: arXiv cs.CV 2017
Year: 2017

Very large overhead imagery associated with ground truth maps has the potential to generate billions of training image patches for machine learning algorithms. However, random sampling selection criteria often leads to redundant and noisy-image patches for model training. With minimal research efforts behind this challenge, the current status spells missed opportunities to develop supervised learning algorithms that generalize over wide geographical scenes. In addition, much of the computational cycles for large scale machine learning are poorly spent crunching through noisy and redundant image patches. We demonstrate a potential framework to address these challenges specifically, while evaluating a human settlement detection task. A novel binary search tree sampling scheme is fused with a kernel based hashing procedure that maps image patches into hash-buckets using binary codes generated from image content. The framework exploits inherent redundancy within billions of image patches to promote mostly high variance preserving samples for accelerating algorithmic training and increasing model generalization.
Learning Fashion Compatibility with Bidirectional LSTMs
Venue: arXiv cs.CV 2017
Year: 2017

The ubiquity of online fashion shopping demands effective recommendation services for customers. In this paper, we study two types of fashion recommendation: (i) suggesting an item that matches existing components in a set to form a stylish outfit (a collection of fashion items), and (ii) generating an outfit with multimodal (images/text) specifications from a user. To this end, we propose to jointly learn a visual-semantic embedding and the compatibility relationships among fashion items in an end-to-end fashion. More specifically, we consider a fashion outfit to be a sequence (usually from top to bottom and then accessories) and each item in the outfit as a time step. Given the fashion items in an outfit, we train a bidirectional LSTM (Bi-LSTM) model to sequentially predict the next item conditioned on previous ones to learn their compatibility relationships. Further, we learn a visual-semantic space by regressing image features to their semantic representations aiming to inject attribute and category information as a regularization for training the LSTM. The trained network can not only perform the aforementioned recommendations effectively but also predict the compatibility of a given outfit. We conduct extensive experiments on our newly collected Polyvore dataset, and the results provide strong qualitative and quantitative evidence that our framework outperforms alternative methods.
A Multi-Armed Bandit Approach for Online Expert Selection in Markov Decision Processes
Venue: arXiv cs.SY 2017
Year: 2017

We formulate a multi-armed bandit (MAB) approach to choosing expert policies online in Markov decision processes (MDPs). Given a set of expert policies trained on a state and action space, the goal is to maximize the cumulative reward of our agent. The hope is to quickly find the best expert in our set. The MAB formulation allows us to quantify the performance of an algorithm in terms of the regret incurred from not choosing the best expert from the beginning. We first develop the theoretical framework for MABs in MDPs, and then present a basic regret decomposition identity. We then adapt the classical Upper Confidence Bounds algorithm to the problem of choosing experts in MDPs and prove that the expected regret grows at worst at a logarithmic rate. Lastly, we validate the theory on a small MDP.
Grounding Spatio-Semantic Referring Expressions for Human-Robot Interaction
Venue: arXiv cs.RO 2017
Year: 2017

The human language is one of the most natural interfaces for humans to interact with robots. This paper presents a robot system that retrieves everyday objects with unconstrained natural language descriptions. A core issue for the system is semantic and spatial grounding, which is to infer objects and their spatial relationships from images and natural language expressions. We introduce a two-stage neural-network grounding pipeline that maps natural language referring expressions directly to objects in the images. The first stage uses visual descriptions in the referring expressions to generate a candidate set of relevant objects. The second stage examines all pairwise relationships between the candidates and predicts the most likely referred object according to the spatial descriptions in the referring expressions. A key feature of our system is that by leveraging a large dataset of images labeled with text descriptions, it allows unrestricted object types and natural language referring expressions. Preliminary results indicate that our system outperforms a near state-of-the-art object comprehension system on standard benchmark datasets. We also present a robot system that follows voice commands to pick and place previously unseen objects.