OpenRaiser/Intern-Atlas huggingface dataset:
A Linear Kernel for Finding Square Roots of Almost Planar Graphs
Venue: arXiv cs.DS 2016
Year: 2016

A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are of distance 2 from each other. The Square Root problem is that of deciding whether a given graph admits a square root. We consider this problem for planar graphs in the context of the "distance from triviality" framework. For an integer k, a planar+kv graph (or k-apex graph) is a graph that can be made planar by the removal of at most k vertices. We prove that a generalization of Square Root, in which some edges are prescribed to be either in or out of any solution, has a kernel of size O(k) for planar+kv graphs, when parameterized by k. Our result is based on a new edge reduction rule which, as we shall also show, has a wider applicability for the Square Root problem.
Effectiveness of greedily collecting items in open world games
Venue: arXiv cs.AI 2016
Year: 2016

Since Pokemon Go sent millions on the quest of collecting virtual monsters, an important question has been on the minds of many people: Is going after the closest item first a time-and-cost-effective way to play? Here, we show that this is in fact a good strategy which performs on average only 7% worse than the best possible solution in terms of the total distance traveled to gather all the items. Even when accounting for errors due to the inability of people to accurately measure distances by eye, the performance only goes down to 16% of the optimal solution.
Towards the Interactive Effects of Demand Response Participation on Electricity Spot Market Price
Venue: arXiv cs.SY 2016
Year: 2016

The electricity market is threatened by supply scarcity, which may lead to very sharp price spikes in the spot market. On the other hand, demand-side's activities could effectively mitigate the supply scarcity and absorb most of these shocks and therefore smooth out the price volatility. In this paper, the positive effects of employing demand response programs on the spot market price are investigated. A demand-price elasticity based model is used to simulate the customer reaction function in the presence of a real time pricing. The demand achieve by DR program is used to adjust the spot market price by using a price regression model. SAS software is used to run the multiple linear regression model and MATLAB is used to simulate the demand response model. The approach is applied on one week data in summer 2014 of Connecticut in New England ISO. It could be concluded from the results of this study that applying DR program smooths out most of the price spikes in the electricity spot market and considerably reduces the customers' electricity cost.
Adaptive Probabilistic Trajectory Optimization via Efficient Approximate Inference
Venue: arXiv cs.RO 2016
Year: 2016

Robotic systems must be able to quickly and robustly make decisions when operating in uncertain and dynamic environments. While Reinforcement Learning (RL) can be used to compute optimal policies with little prior knowledge about the environment, it suffers from slow convergence. An alternative approach is Model Predictive Control (MPC), which optimizes policies quickly, but also requires accurate models of the system dynamics and environment. In this paper we propose a new approach, adaptive probabilistic trajectory optimization, that combines the benefits of RL and MPC. Our method uses scalable approximate inference to learn and updates probabilistic models in an online incremental fashion while also computing optimal control policies via successive local approximations. We present two variations of our algorithm based on the Sparse Spectrum Gaussian Process (SSGP) model, and we test our algorithm on three learning tasks, demonstrating the effectiveness and efficiency of our approach.
Which techniques does your application use?: An information extraction framework for scientific articles
Venue: arXiv cs.CL 2016
Year: 2016

Every field of research consists of multiple application areas with various techniques routinely used to solve problems in these wide range of application areas. With the exponential growth in research volumes, it has become difficult to keep track of the ever-growing number of application areas as well as the corresponding problem solving techniques. In this paper, we consider the computational linguistics domain and present a novel information extraction system that automatically constructs a pool of all application areas in this domain and appropriately links them with corresponding problem solving techniques. Further, we categorize individual research articles based on their application area and the techniques proposed/used in the article. k-gram based discounting method along with handwritten rules and bootstrapped pattern learning is employed to extract application areas. Subsequently, a language modeling approach is proposed to characterize each article based on its application area. Similarly, regular expressions and high-scoring noun phrases are used for the extraction of the problem solving techniques. We propose a greedy approach to characterize each article based on the techniques. Towards the end, we present a table representing the most frequent techniques adopted for a particular application area. Finally, we propose three use cases presenting an extensive temporal analysis of the usage of techniques and application areas.
Online Learning to Rank with Top-k Feedback
Venue: arXiv cs.LG 2016
Year: 2016

We consider two settings of online learning to rank where feedback is restricted to top ranked items. The problem is cast as an online game between a learner and sequence of users, over $T$ rounds. In both settings, the learners objective is to present ranked list of items to the users. The learner's performance is judged on the entire ranked list and true relevances of the items. However, the learner receives highly restricted feedback at end of each round, in form of relevances of only the top $k$ ranked items, where $k \ll m$. The first setting is \emph{non-contextual}, where the list of items to be ranked is fixed. The second setting is \emph{contextual}, where lists of items vary, in form of traditional query-document lists. No stochastic assumption is made on the generation process of relevances of items and contexts. We provide efficient ranking strategies for both the settings. The strategies achieve $O(T^{2/3})$ regret, where regret is based on popular ranking measures in first setting and ranking surrogates in second setting. We also provide impossibility results for certain ranking measures and a certain class of surrogates, when feedback is restricted to the top ranked item, i.e. $k=1$. We empirically demonstrate the performance of our algorithms on simulated and real world datasets.
A Harmonic Potential Field Approach for Joint Planning & Control of a Rigid, Separable Nonholonomic, Mobile Robot
Venue: arXiv cs.RO 2016
Year: 2016

The main objective of this paper is to provide a tool for performing path planning at the servo level of a mobile robot. The ability to perform, in a provably correct manner, such a complex task at the servo level can lead to a large increase in the speed of operation, low energy consumption and high quality of response. Planning has been traditionally limited to the high level controller of a robot. The guidance velocity signal from this stage is usually converted to a control signal using what is known as an electronic speed controller (ESC). This paper demonstrates the ability of the harmonic potential field (HPF) approach to generate a provably correct, constrained, well behaved trajectory and control signal for a rigid, nonholonomic robot in a stationary, cluttered environment. It is shown that the HPF based, servo level planner can address a large number of challenges facing planning in a realistic situation. The suggested approach migrates the rich and provably correct properties of the solution trajectories from an HPF planner to those of the robot. This is achieved using a synchronizing control signal whose aim is to align the velocity of the robot in its local coordinates, with that of the gradient of the HPF. The link between the two is made possible by representing the robot using what the paper terms separable form. The context-sensitive and goal-oriented control signal used to steer the robot is demonstrated to be well behaved and robust in the presence of actuator noise, saturation and uncertainty in the parameters. The approach is developed, proofs of correctness are provided and the capabilities of the scheme are demonstrated using simulation results.
Convolutional Network for Attribute-driven and Identity-preserving Human Face Generation
Venue: arXiv cs.CV 2016
Year: 2016

This paper focuses on the problem of generating human face pictures from specific attributes. The existing CNN-based face generation models, however, either ignore the identity of the generated face or fail to preserve the identity of the reference face image. Here we address this problem from the view of optimization, and suggest an optimization model to generate human face with the given attributes while keeping the identity of the reference image. The attributes can be obtained from the attribute-guided image or by tuning the attribute features of the reference image. With the deep convolutional network "VGG-Face", the loss is defined on the convolutional feature maps. We then apply the gradient decent algorithm to solve this optimization problem. The results validate the effectiveness of our method for attribute driven and identity-preserving face generation.
Adaptive Data Collection Mechanisms for Smart Monitoring of Distribution Grids
Venue: arXiv cs.SY 2016
Year: 2016

Smart Grid systems not only transport electric energy but also information which will be active part of the electricity supply system. This has led to the introduction of intelligent components on all layers of the electrical grid in power generation, transmission, distribution and consumption units. For electric distribution systems, Information from Smart Meters can be utilized to monitor and control the state of the grid. Hence, it is indeed inherent that data from Smart Meters should be collected in a resilient, reliable, secure and timely manner fulfilling all the communication requirements and standards. This paper presents a proposal for smart data collection mechanisms to monitor electrical grids with adaptive smart metering infrastructures. A general overview of a platform is given for testing, evaluating and implementing mechanisms to adapt Smart Meter data aggregation. Three main aspects of adaptiveness of the system are studied, adaptiveness to smart metering application needs, adaptiveness to changing communication network dynamics and adaptiveness to security attacks. Execution of tests will be conducted in real field experimental set-up and in an advanced hardware in the loop test-bed with power and communication co-simulation for validation purposes.
Towards Designing PLC Networks for Ubiquitous Connectivity in Enterprises
Venue: arXiv cs.NI 2016
Year: 2016

Powerline communication (PLC) provides inexpensive, secure and high speed network connectivity, by leveraging the existing power distribution networks inside the buildings. While PLC technology has the potential to improve connectivity and is considered a key enabler for sensing, control, and automation applications in enterprises, it has been mainly deployed for improving connectivity in homes. Deploying PLCs in enterprises is more challenging since the power distribution network is more complex as compared to homes. Moreover, existing PLC technologies such as HomePlug AV have not been designed for and evaluated in enterprise deployments. In this paper, we first present a comprehensive measurement study of PLC performance in enterprise settings, by analyzing PLC channel characteristics across space, time, and spectral dimensions, using commodity HomePlug AV PLC devices. Our results uncover the impact of distribution lines, circuit breakers, AC phases and electrical interference on PLC performance. Based on our findings, we show that careful planning of PLC network topology, routing and spectrum sharing can significantly boost performance of enterprise PLC networks. Our experimental results show that multi-hop routing can increase throughput performance by 5x in scenarios where direct PLC links perform poorly. Moreover, our trace driven simulations for multiple deployments, show that our proposed fine-grained spectrum sharing design can boost the aggregated and per-link PLC throughput by more than 20% and 100% respectively, in enterprise PLC networks.
Diagonality Measures of Hermitian Positive-Definite Matrices with Application to the Approximate Joint Diagonalization Problem
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we introduce properly-invariant diagonality measures of Hermitian positive-definite matrices. These diagonality measures are defined as distances or divergences between a given positive-definite matrix and its diagonal part. We then give closed-form expressions of these diagonality measures and discuss their invariance properties. The diagonality measure based on the log-determinant $α$-divergence is general enough as it includes a diagonality criterion used by the signal processing community as a special case. These diagonality measures are then used to formulate minimization problems for finding the approximate joint diagonalizer of a given set of Hermitian positive-definite matrices. Numerical computations based on a modified Newton method are presented and commented.
Lexical Query Modeling in Session Search
Venue: arXiv cs.IR 2016
Year: 2016

Lexical query modeling has been the leading paradigm for session search. In this paper, we analyze TREC session query logs and compare the performance of different lexical matching approaches for session search. Naive methods based on term frequency weighing perform on par with specialized session models. In addition, we investigate the viability of lexical query models in the setting of session search. We give important insights into the potential and limitations of lexical query modeling for session search and propose future directions for the field of session search.
Topic Grids for Homogeneous Data Visualization
Venue: arXiv cs.LG 2016
Year: 2016

We propose the topic grids to detect anomaly and analyze the behavior based on the access log content. Content-based behavioral risk is quantified in the high dimensional space where the topics are generated from the log. The topics are being projected homogeneously into a space that is perception- and interaction-friendly to the human experts.
Robust Named Entity Recognition in Idiosyncratic Domains
Venue: arXiv cs.CL 2016
Year: 2016

Named entity recognition often fails in idiosyncratic domains. That causes a problem for depending tasks, such as entity linking and relation extraction. We propose a generic and robust approach for high-recall named entity recognition. Our approach is easy to train and offers strong generalization over diverse domain-specific language, such as news documents (e.g. Reuters) or biomedical text (e.g. Medline). Our approach is based on deep contextual sequence learning and utilizes stacked bidirectional LSTM networks. Our model is trained with only few hundred labeled sentences and does not rely on further external knowledge. We report from our results F1 scores in the range of 84-94% on standard datasets.
Multi-Colored Spanning Graphs
Venue: arXiv cs.CG 2016
Year: 2016

We study a problem proposed by Hurtado et al. (2016) motivated by sparse set visualization. Given $n$ points in the plane, each labeled with one or more primary colors, a \emph{colored spanning graph} (CSG) is a graph such that for each primary color, the vertices of that color induce a connected subgraph. The \textsc{Min-CSG} problem asks for the minimum sum of edge lengths in a colored spanning graph. We show that the problem is NP-hard for $k$ primary colors when $k\ge 3$ and provide a $(2-\frac{1}{3+2\varrho})$-approximation algorithm for $k=3$ that runs in polynomial time, where $\varrho$ is the Steiner ratio. Further, we give a $O(n)$ time algorithm in the special case that the input points are collinear and $k$ is constant.
Multimedia Storage in the Cloud using Amazon Web Services: Implications for Online Education
Venue: arXiv cs.CY 2016
Year: 2016

This report is divided into three parts. Firstly, an explanation of the cloud storage products is given, in particular, the Amazon Simple Storage Service (S3). Secondly, the report discusses a case study about SmugMug's migration to the cloud hosted by Amazon. SmugMug is a premium online photo and video sharing service business, and currently has billions of photos and videos from amateur and professional photographers around the world. This report also includes a step by step explanation of how to modify a website and use Amazon S3 to host videos in the cloud. These findings are evaluated in terms of how useful Amazon S3 can be for an e-learning institute, especially one that is geared towards mobile delivery of content. Finally, the paper covers the copyright, and privacy implications, in order to understand the larger context.
Modelling Chemical Reasoning to Predict Reactions
Venue: arXiv cs.AI 2016
Year: 2016

The ability to reason beyond established knowledge allows Organic Chemists to solve synthetic problems and to invent novel transformations. Here, we propose a model which mimics chemical reasoning and formalises reaction prediction as finding missing links in a knowledge graph. We have constructed a knowledge graph containing 14.4 million molecules and 8.2 million binary reactions, which represents the bulk of all chemical reactions ever published in the scientific literature. Our model outperforms a rule-based expert system in the reaction prediction task for 180,000 randomly selected binary reactions. We show that our data-driven model generalises even beyond known reaction types, and is thus capable of effectively (re-) discovering novel transformations (even including transition-metal catalysed reactions). Our model enables computers to infer hypotheses about reactivity and reactions by only considering the intrinsic local structure of the graph, and because each single reaction prediction is typically achieved in a sub-second time frame, our model can be used as a high-throughput generator of reaction hypotheses for reaction discovery.
The feasibility of launching physical layer attacks in visible light communication networks
Venue: arXiv cs.CR 2016
Year: 2016

One of the areas in which wireless networks based on visible light communication (VLC) are considered superior to traditional radio-based communication is security. The common slogan summarizing VLC security features is: WYSIWYS - "What You See Is What You Send". However, especially in the case of infrastructure downlink communication, security with respect to data snooping, jamming and modification must be carefully provided for. This paper examines the physical layer aspects of VLC networks with respect to possible disruptions caused by rogue transmitters. We present the theoretical system model that we use in simulations to evaluate various rogue transmission scenarios in a typical office environment. We use estimated Bit Error Rate (BER) as a measure of the effectiveness of jamming and rogue data transmission. We find that it is quite easy to disrupt, and in some cases to even hijack legitimate transmission.
Active Robust Learning
Venue: arXiv cs.LG 2016
Year: 2016

In many practical applications of learning algorithms, unlabeled data is cheap and abundant whereas labeled data is expensive. Active learning algorithms developed to achieve better performance with lower cost. Usually Representativeness and Informativeness are used in active learning algoirthms. Advanced recent active learning methods consider both of these criteria. Despite its vast literature, very few active learning methods consider noisy instances, i.e. label noisy and outlier instances. Also, these methods didn't consider accuracy in computing representativeness and informativeness. Based on the idea that inaccuracy in these measures and not taking noisy instances into consideration are two sides of a coin and are inherently related, a new loss function is proposed. This new loss function helps to decrease the effect of noisy instances while at the same time, reduces bias. We defined "instance complexity" as a new notion of complexity for instances of a learning problem. It is proved that noisy instances in the data if any, are the ones with maximum instance complexity. Based on this loss function which has two functions for classifying ordinary and noisy instances, a new classifier, named "Simple-Complex Classifier" is proposed. In this classifier there are a simple and a complex function, with the complex function responsible for selecting noisy instances. The resulting optimization problem for both learning and active learning is highly non-convex and very challenging. In order to solve it, a convex relaxation is proposed.
Modeling and Propagating CNNs in a Tree Structure for Visual Tracking
Venue: arXiv cs.CV 2016
Year: 2016

We present an online visual tracking algorithm by managing multiple target appearance models in a tree structure. The proposed algorithm employs Convolutional Neural Networks (CNNs) to represent target appearances, where multiple CNNs collaborate to estimate target states and determine the desirable paths for online model updates in the tree. By maintaining multiple CNNs in diverse branches of tree structure, it is convenient to deal with multi-modality in target appearances and preserve model reliability through smooth updates along tree paths. Since multiple CNNs share all parameters in convolutional layers, it takes advantage of multiple models with little extra cost by saving memory space and avoiding redundant network evaluations. The final target state is estimated by sampling target candidates around the state in the previous frame and identifying the best sample in terms of a weighted average score from a set of active CNNs. Our algorithm illustrates outstanding performance compared to the state-of-the-art techniques in challenging datasets such as online tracking benchmark and visual object tracking challenge.
Complexity of inheritance of $\mathcal{F}$-convexity for restricted games induced by minimum partitions
Venue: arXiv cs.DM 2016
Year: 2016

Let $G = (N,E,w)$ be a weighted communication graph (with weight function $w$ on $E$). For every subset $A \subseteq N$, we delete in the subset $E(A)$ of edges with ends in $A$, all edges of minimum weight in $E(A)$. Then the connected components of the corresponding induced subgraph constitute a partition of $A$ that we call $P_{\min}(A)$. For every game $(N, v)$, we define the $P_{\min}$-restricted game $(N, \bar{v})$ by $\bar{v}(A) = \sum_{F \in P_{\min}(A)} v(F)$ for all $A \subseteq N$. We prove that we can decide in polynomial time if there is inheritance of $\mathcal{F}$-convexity from $(N, v)$ to the $P_{\min}$-restricted game $(N, \bar{v})$ where $\mathcal{F}$-convexity is obtained by restricting convexity to connected subsets.