OpenRaiser/Intern-Atlas huggingface dataset:
A divide and conquer method for symbolic regression
Venue: arXiv cs.NE 2017
Year: 2017

Symbolic regression aims to find a function that best explains the relationship between independent variables and the objective value based on a given set of sample data. Genetic programming (GP) is usually considered as an appropriate method for the problem since it can optimize functional structure and coefficients simultaneously. However, the convergence speed of GP might be too slow for large scale problems that involve a large number of variables. Fortunately, in many applications, the target function is separable or partially separable. This feature motivated us to develop a new method, divide and conquer (D&C), for symbolic regression, in which the target function is divided into a number of sub-functions and the sub-functions are then determined by any of a GP algorithm. The separability is probed by a new proposed technique, Bi-Correlation test (BiCT). D&C powered GP has been tested on some real-world applications, and the study shows that D&C can help GP to get the target function much more rapidly.
Towards seamless multi-view scene analysis from satellite to street-level
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we discuss and review how combined multi-view imagery from satellite to street-level can benefit scene analysis. Numerous works exist that merge information from remote sensing and images acquired from the ground for tasks like land cover mapping, object detection, or scene understanding. What makes the combination of overhead and street-level images challenging, is the strongly varying viewpoint, different scale, illumination, sensor modality and time of acquisition. Direct (dense) matching of images on a per-pixel basis is thus often impossible, and one has to resort to alternative strategies that will be discussed in this paper. We review recent works that attempt to combine images taken from the ground and overhead views for purposes like scene registration, reconstruction, or classification. Three methods that represent the wide range of potential methods and applications (change detection, image orientation, and tree cataloging) are described in detail. We show that cross-fertilization between remote sensing, computer vision and machine learning is very valuable to make the best of geographic data available from Earth Observation sensors and ground imagery. Despite its challenges, we believe that integrating these complementary data sources will lead to major breakthroughs in Big GeoData.
Kinetostatic Analysis and Solution Classification of a Planar Tensegrity Mechanism
Venue: arXiv cs.RO 2017
Year: 2017

Tensegrity mechanisms have several interesting properties that make them suitable for a number of applications. Their analysis is generally challenging because the static equilibrium conditions often result in complex equations. A class of planar one-degree-of-freedom (dof) tensegrity mechanisms with three linear springs is analyzed in detail in this paper. The kinetostatic equations are derived and solved under several loading and geometric conditions. It is shown that these mechanisms exhibit up to six equilibrium configurations, of which one or two are stable. Discriminant varieties and cylindrical algebraic decomposition combined with Groebner base elimination are used to classify solutions as function of the input parameters.
Computational Methods for Path-based Robust Flows
Venue: arXiv cs.DM 2017
Year: 2017

Real world networks are often subject to severe uncertainties which need to be addressed by any reliable prescriptive model. In the context of the maximum flow problem subject to arc failure, robust models have gained particular attention. For a path-based model, the resulting optimization problem is assumed to be difficult in the literature, yet the complexity status is widely unknown. We present a computational approach to solve the robust flow problem to optimality by simultaneous primal and dual separation, the practical efficacy of which is shown by a computational study. Furthermore, we introduce a novel model of robust flows which provides a compromise between stochastic and robust optimization by assigning probabilities to groups of scenarios. The new model can be solved by the same computational techniques as the robust model. A bound on the generalization error is proven for the case that the probabilities are determined empirically. The suggested model as well as the computational approach extend to linear optimization problems more general than robust flows.
Towards Blockchain-based Auditable Storage and Sharing of IoT Data
Venue: arXiv cs.DC 2017
Year: 2017

Today the cloud plays a central role in storing, processing, and distributing data. Despite contributing to the rapid development of IoT applications, the current IoT cloud-centric architecture has led into a myriad of isolated data silos that hinders the full potential of holistic data-driven analytics within the IoT. In this paper, we present a blockchain-based design for the IoT that brings a distributed access control and data management. We depart from the current trust model that delegates access control of our data to a centralized trusted authority and instead empower the users with data ownership. Our design is tailored for IoT data streams and enables secure data sharing. We enable a secure and resilient access control management, by utilizing the blockchain as an auditable and distributed access control layer to the storage layer. We facilitate the storage of time-series IoT data at the edge of the network via a locality-aware decentralized storage system that is managed with the blockchain technology. Our system is agnostic of the physical storage nodes and supports as well utilization of cloud storage resources as storage nodes.
Loose Graph Simulations
Venue: arXiv cs.LO 2017
Year: 2017

We introduce loose graph simulations (LGS), a new notion about labelled graphs which subsumes in an intuitive and natural way subgraph isomorphism (SGI), regular language pattern matching (RLPM) and graph simulation (GS). Being a unification of all these notions, LGS allows us to express directly also problems which are "mixed" instances of previous ones, and hence which would not fit easily in any of them. After the definition and some examples, we show that the problem of finding loose graph simulations is NP-complete, we provide formal translation of SGI, RLPM, and GS into LGSs, and we give the representation of a problem which extends both SGI and RLPM. Finally, we identify a subclass of the LGS problem that is polynomial.
Enhanced Experience Replay Generation for Efficient Reinforcement Learning
Venue: arXiv cs.AI 2017
Year: 2017

Applying deep reinforcement learning (RL) on real systems suffers from slow data sampling. We propose an enhanced generative adversarial network (EGAN) to initialize an RL agent in order to achieve faster learning. The EGAN utilizes the relation between states and actions to enhance the quality of data samples generated by a GAN. Pre-training the agent with the EGAN shows a steeper learning curve with a 20% improvement of training time in the beginning of learning, compared to no pre-training, and an improvement compared to training with GAN by about 5% with smaller variations. For real time systems with sparse and slow data sampling the EGAN could be used to speed up the early phases of the training process.
How hard can it be? Estimating the difficulty of visual search in an image
Venue: arXiv cs.CV 2017
Year: 2017

We address the problem of estimating image difficulty defined as the human response time for solving a visual search task. We collect human annotations of image difficulty for the PASCAL VOC 2012 data set through a crowd-sourcing platform. We then analyze what human interpretable image properties can have an impact on visual search difficulty, and how accurate are those properties for predicting difficulty. Next, we build a regression model based on deep features learned with state of the art convolutional neural networks and show better results for predicting the ground-truth visual search difficulty scores produced by human annotators. Our model is able to correctly rank about 75% image pairs according to their difficulty score. We also show that our difficulty predictor generalizes well to new classes not seen during training. Finally, we demonstrate that our predicted difficulty scores are useful for weakly supervised object localization (8% improvement) and semi-supervised object classification (1% improvement).
Learning Optimal Routing for the Uplink in LPWANs Using Similarity-enhanced epsilon-greedy
Venue: arXiv cs.NI 2017
Year: 2017

Despite being a relatively new communication technology, Low-Power Wide Area Networks (LPWANs) have shown their suitability to empower a major part of Internet of Things applications. Nonetheless, most LPWAN solutions are built on star topology (or single-hop) networks, often causing lifetime shortening in stations located far from the gateway. In this respect, recent studies show that multi-hop routing for uplink communications can reduce LPWANs' energy consumption significantly. However, it is a troublesome task to identify such energetically optimal routings through trial-and-error brute-force approaches because of time and, especially, energy consumption constraints. In this work we show the benefits of facing this exploration/exploitation problem by running centralized variations of the multi-arm bandit's epsilon-greedy, a well-known online decision-making method that combines best known action selection and knowledge expansion. Important energy savings are achieved when proper randomness parameters are set, which are often improved when conveniently applying similarity, a concept introduced in this work that allows harnessing the gathered knowledge by sporadically selecting unexplored routing combinations akin to the best known one.
Explaining Transition Systems through Program Induction
Venue: arXiv cs.AI 2017
Year: 2017

Explaining and reasoning about processes which underlie observed black-box phenomena enables the discovery of causal mechanisms, derivation of suitable abstract representations and the formulation of more robust predictions. We propose to learn high level functional programs in order to represent abstract models which capture the invariant structure in the observed data. We introduce the $π$-machine (program-induction machine) -- an architecture able to induce interpretable LISP-like programs from observed data traces. We propose an optimisation procedure for program learning based on backpropagation, gradient descent and A* search. We apply the proposed method to three problems: system identification of dynamical systems, explaining the behaviour of a DQN agent and learning by demonstration in a human-robot interaction scenario. Our experimental results show that the $π$-machine can efficiently induce interpretable programs from individual data traces.
Efficient Coalgebraic Partition Refinement
Venue: arXiv cs.DS 2017
Year: 2017

We present a generic partition refinement algorithm that quotients coalgebraic systems by behavioural equivalence, an important task in reactive verification; coalgebraic generality implies in particular that we cover not only classical relational systems but also various forms of weighted systems. Under assumptions on the type functor that allow representing its finite coalgebras in terms of nodes and edges, our algorithm runs in time $\mathcal{O}(m\cdot \log n)$ where $n$ and $m$ are the numbers of nodes and edges, respectively. Instances of our generic algorithm thus match the runtime of the best known algorithms for unlabelled transition systems, Markov chains, and deterministic automata (with fixed alphabets), and improve the best known algorithms for Segala systems.
Better Text Understanding Through Image-To-Text Transfer
Venue: arXiv cs.CL 2017
Year: 2017

Generic text embeddings are successfully used in a variety of tasks. However, they are often learnt by capturing the co-occurrence structure from pure text corpora, resulting in limitations of their ability to generalize. In this paper, we explore models that incorporate visual information into the text representation. Based on comprehensive ablation studies, we propose a conceptually simple, yet well performing architecture. It outperforms previous multimodal approaches on a set of well established benchmarks. We also improve the state-of-the-art results for image-related text datasets, using orders of magnitude less data.
Information Theoretic Principles of Universal Discrete Denoising
Venue: arXiv cs.IT 2017
Year: 2017

Today, the internet makes tremendous amounts of data widely available. Often, the same information is behind multiple different available data sets. This lends growing importance to latent variable models that try to learn the hidden information from the available imperfect versions. For example, social media platforms can contain an abundance of pictures of the same person or object, yet all of which are taken from different perspectives. In a simplified scenario, one may consider pictures taken from the same perspective, which are distorted by noise. This latter application allows for a rigorous mathematical treatment, which is the content of this contribution. We apply a recently developed method of dependent component analysis to image denoising when multiple distorted copies of one and the same image are available, each being corrupted by a different and unknown noise process. In a simplified scenario, we assume that the distorted image is corrupted by noise that acts independently on each pixel. We answer completely the question of how to perform optimal denoising, when at least three distorted copies are available: First we define optimality of an algorithm in the presented scenario, and then we describe an aymptotically optimal universal discrete denoising algorithm (UDDA). In the case of binary data and binary symmetric noise, we develop a simplified variant of the algorithm, dubbed BUDDA, which we prove to attain universal denoising uniformly.
Symbolic LTLf Synthesis
Venue: arXiv cs.LO 2017
Year: 2017

LTLf synthesis is the process of finding a strategy that satisfies a linear temporal specification over finite traces. An existing solution to this problem relies on a reduction to a DFA game. In this paper, we propose a symbolic framework for LTLf synthesis based on this technique, by performing the computation over a representation of the DFA as a boolean formula rather than as an explicit graph. This approach enables strategy generation by utilizing the mechanism of boolean synthesis. We implement this symbolic synthesis method in a tool called Syft, and demonstrate by experiments on scalable benchmarks that the symbolic approach scales better than the explicit one.
Input Fast-Forwarding for Better Deep Learning
Venue: arXiv cs.CV 2017
Year: 2017

This paper introduces a new architectural framework, known as input fast-forwarding, that can enhance the performance of deep networks. The main idea is to incorporate a parallel path that sends representations of input values forward to deeper network layers. This scheme is substantially different from "deep supervision" in which the loss layer is re-introduced to earlier layers. The parallel path provided by fast-forwarding enhances the training process in two ways. First, it enables the individual layers to combine higher-level information (from the standard processing path) with lower-level information (from the fast-forward path). Second, this new architecture reduces the problem of vanishing gradients substantially because the fast-forwarding path provides a shorter route for gradient backpropagation. In order to evaluate the utility of the proposed technique, a Fast-Forward Network (FFNet), with 20 convolutional layers along with parallel fast-forward paths, has been created and tested. The paper presents empirical results that demonstrate improved learning capacity of FFNet due to fast-forwarding, as compared to GoogLeNet (with deep supervision) and CaffeNet, which are 4x and 18x larger in size, respectively. All of the source code and deep learning models described in this paper will be made available to the entire research community
Predictive Analytics for Enhancing Travel Time Estimation in Navigation Apps of Apple, Google, and Microsoft
Venue: arXiv cs.AI 2017
Year: 2017

The explosive growth of the location-enabled devices coupled with the increasing use of Internet services has led to an increasing awareness of the importance and usage of geospatial information in many applications. The navigation apps (often called Maps), use a variety of available data sources to calculate and predict the travel time as well as several options for routing in public transportation, car or pedestrian modes. This paper evaluates the pedestrian mode of Maps apps in three major smartphone operating systems (Android, iOS and Windows Phone). In the paper, we will show that the Maps apps on iOS, Android and Windows Phone in pedestrian mode, predict travel time without learning from the individual's movement profile. In addition, we will exemplify that those apps suffer from a specific data quality issue which relates to the absence of information about location and type of pedestrian crossings. Finally, we will illustrate learning from movement profile of individuals using various predictive analytics models to improve the accuracy of travel time estimation.
Conscious and controlling elements in combinatorial group testing problems with more defectives
Venue: arXiv cs.DM 2017
Year: 2017

In combinatorial group testing problems Questioner needs to find a defective element $x\in [n]$ by testing subsets of $[n]$. In [18] the authors introduced a new model, where each element knows the answer for those queries that contain it and each element should be able to identify the defective one. In this article we continue to investigate this kind of models with more defective elements. We also consider related models inspired by secret sharing models, where the elements should share information among them to find out the defectives. Finally the adaptive versions of the different models are also investigated.
Towards Interrogating Discriminative Machine Learning Models
Venue: arXiv cs.LG 2017
Year: 2017

It is oftentimes impossible to understand how machine learning models reach a decision. While recent research has proposed various technical approaches to provide some clues as to how a learning model makes individual decisions, they cannot provide users with ability to inspect a learning model as a complete entity. In this work, we propose a new technical approach that augments a Bayesian regression mixture model with multiple elastic nets. Using the enhanced mixture model, we extract explanations for a target model through global approximation. To demonstrate the utility of our approach, we evaluate it on different learning models covering the tasks of text mining and image recognition. Our results indicate that the proposed approach not only outperforms the state-of-the-art technique in explaining individual decisions but also provides users with an ability to discover the vulnerabilities of a learning model.
Traffic Profiling for Mobile Video Streaming
Venue: arXiv cs.MM 2017
Year: 2017

This paper describes a novel system that provides key parameters of HTTP Adaptive Streaming (HAS) sessions to the lower layers of the protocol stack. A non-intrusive traffic profiling solution is proposed that observes packet flows at the transmit queue of base stations, edge-routers, or gateways. By analyzing IP flows in real time, the presented scheme identifies different phases of an HAS session and estimates important application-layer parameters, such as play-back buffer state and video encoding rate. The introduced estimators only use IP-layer information, do not require standardization and work even with traffic that is encrypted via Transport Layer Security (TLS). Experimental results for a popular video streaming service clearly verify the high accuracy of the proposed solution. Traffic profiling, thus, provides a valuable alternative to cross-layer signaling and Deep Packet Inspection (DPI) in order to perform efficient network optimization for video streaming.
A Control Performance Index for Multicopters Under Off-nominal Conditions
Venue: arXiv cs.RO 2017
Year: 2017

In order to prevent loss of control (LOC) accidents,the real-time control performance monitoring problem is studied for multicopters. Different from the existing work, this paper does not try to monitor the performance of the controllers directly. In turn, the disturbances of multicopters under off-nominal conditions are estimated to affect a proposed index to tell the user whether the multicopter will be LOC or not. Firstly, a new degree of controllability (DoC) will be proposed for multicopters subject to control constrains and off-nominal conditions. Then a control performance index (CPI) is defined based on the new DoC to reflect the control performance for multicopters. Besides, the proposed CPI is applied to a new switching control framework to guide the control decision of multicopter under off-nominal conditions. Finally, simulation and experimental results show the effectiveness of the CPI and the proposed switching control framework.
Analysing Timelines of National Histories across Wikipedia Editions: A Comparative Computational Approach
Venue: arXiv cs.DL 2017
Year: 2017

Portrayals of history are never complete, and each description inherently exhibits a specific viewpoint and emphasis. In this paper, we aim to automatically identify such differences by computing timelines and detecting temporal focal points of written history across languages on Wikipedia. In particular, we study articles related to the history of all UN member states and compare them in 30 language editions. We develop a computational approach that allows to identify focal points quantitatively, and find that Wikipedia narratives about national histories (i) are skewed towards more recent events (recency bias) and (ii) are distributed unevenly across the continents with significant focus on the history of European countries (Eurocentric bias). We also establish that national historical timelines vary across language editions, although average interlingual consensus is rather high. We hope that this paper provides a starting point for a broader computational analysis of written history on Wikipedia and elsewhere.
A hierarchical multirate MPC scheme for interconnected systems - $\textit{extended version}$
Venue: arXiv cs.SY 2017
Year: 2017

This paper presents a hierarchical control scheme for interconnected linear systems. At the higher layer of the control structure a robust centralized Model Predictive Control (MPC) algorithm based on a reduced order dynamic model of the overall system optimizes a long-term performance index penalizing the deviation of the state and the control input from their nominal values. At the lower layer local MPC regulators, possibly working at different rates, are designed for the full order models of the subsystems to refine the control action computed at the higher layer. A simulation experiment is presented to describe the implementation aspects and the potentialities of the proposed approach.