OpenRaiser/Intern-Atlas huggingface dataset:
Spatial Scaling of Satellite Soil Moisture using Temporal Correlations and Ensemble Learning
Venue: arXiv cs.CV 2016
Year: 2016

A novel algorithm is developed to downscale soil moisture (SM), obtained at satellite scales of 10-40 km by utilizing its temporal correlations to historical auxiliary data at finer scales. Including such correlations drastically reduces the size of the training set needed, accounts for time-lagged relationships, and enables downscaling even in the presence of short gaps in the auxiliary data. The algorithm is based upon bagged regression trees (BRT) and uses correlations between high-resolution remote sensing products and SM observations. The algorithm trains multiple regression trees and automatically chooses the trees that generate the best downscaled estimates. The algorithm was evaluated using a multi-scale synthetic dataset in north central Florida for two years, including two growing seasons of corn and one growing season of cotton per year. The time-averaged error across the region was found to be 0.01 $\mathrm{m}^3/\mathrm{m}^3$, with a standard deviation of 0.012 $\mathrm{m}^3/\mathrm{m}^3$ when 0.02% of the data were used for training in addition to temporal correlations from the past seven days, and all available data from the past year. The maximum spatially averaged errors obtained using this algorithm in downscaled SM were 0.005 $\mathrm{m}^3/\mathrm{m}^3$, for pixels with cotton land-cover. When land surface temperature~(LST) on the day of downscaling was not included in the algorithm to simulate "data gaps", the spatially averaged error increased minimally by 0.015 $\mathrm{m}^3/\mathrm{m}^3$ when LST is unavailable on the day of downscaling. The results indicate that the BRT-based algorithm provides high accuracy for downscaling SM using complex non-linear spatio-temporal correlations, under heterogeneous micro meteorological conditions.
Syntax-Semantics Interaction Parsing Strategies. Inside SYNTAGMA
Venue: arXiv cs.CL 2016
Year: 2016

This paper discusses SYNTAGMA, a rule based NLP system addressing the tricky issues of syntactic ambiguity reduction and word sense disambiguation as well as providing innovative and original solutions for constituent generation and constraints management. To provide an insight into how it operates, the system's general architecture and components, as well as its lexical, syntactic and semantic resources are described. After that, the paper addresses the mechanism that performs selective parsing through an interaction between syntactic and semantic information, leading the parser to a coherent and accurate interpretation of the input text.
Wireless Network Simplification : Beyond Diamond Networks
Venue: arXiv cs.IT 2016
Year: 2016

We consider an arbitrary layered Gaussian relay network with $L$ layers of $N$ relays each, from which we select subnetworks with $K$ relays per layer. We prove that: (i) For arbitrary $L, N$ and $K = 1$, there always exists a subnetwork that approximately achieves $\frac{2}{(L-1)N + 4}$ $\left(\mbox{resp.}\frac{2}{LN+2}\right)$ of the network capacity for odd $L$ (resp. even $L$), (ii) For $L = 2, N = 3, K = 2$, there always exists a subnetwork that approximately achieves $\frac{1}{2}$ of the network capacity. We also provide example networks where even the best subnetworks achieve exactly these fractions (up to additive gaps). Along the way, we derive some results on MIMO antenna selection and capacity decomposition that may also be of independent interest.
A Survey on Security Metrics
Venue: arXiv cs.CR 2016
Year: 2016

The importance of security metrics can hardly be overstated. Despite the attention that has been paid by the academia, government and industry in the past decades, this important problem stubbornly remains open. In this survey, we present a survey of knowledge on security metrics. The survey is centered on a novel taxonomy, which classifies security metrics into four categories: metrics for measuring the system vulnerabilities, metrics for measuring the defenses, metrics for measuring the threats, and metrics for measuring the situations. The insight underlying the taxonomy is that situations (or outcomes of cyber attack-defense interactions) are caused by certain threats (or attacks) against systems that have certain vulnerabilities (including human factors) and employ certain defenses. In addition to systematically reviewing the security metrics that have been proposed in the literature, we discuss the gaps between the state of the art and the ultimate goals.
Task Parallel Incomplete Cholesky Factorization using 2D Partitioned-Block Layout
Venue: arXiv cs.MS 2016
Year: 2016

We introduce a task-parallel algorithm for sparse incomplete Cholesky factorization that utilizes a 2D sparse partitioned-block layout of a matrix. Our factorization algorithm follows the idea of algorithms-by-blocks by using the block layout. The algorithm-by-blocks approach induces a task graph for the factorization. These tasks are inter-related to each other through their data dependences in the factorization algorithm. To process the tasks on various manycore architectures in a portable manner, we also present a portable tasking API that incorporates different tasking backends and device-specific features using an open-source framework for manycore platforms i.e., Kokkos. A performance evaluation is presented on both Intel Sandybridge and Xeon Phi platforms for matrices from the University of Florida sparse matrix collection to illustrate merits of the proposed task-based factorization. Experimental results demonstrate that our task-parallel implementation delivers about 26.6x speedup (geometric mean) over single-threaded incomplete Cholesky-by-blocks and 19.2x speedup over serial Cholesky performance which does not carry tasking overhead using 56 threads on the Intel Xeon Phi processor for sparse matrices arising from various application problems.
When is Clustering Perturbation Robust?
Venue: arXiv cs.LG 2016
Year: 2016

Clustering is a fundamental data mining tool that aims to divide data into groups of similar items. Generally, intuition about clustering reflects the ideal case -- exact data sets endowed with flawless dissimilarity between individual instances. In practice however, these cases are in the minority, and clustering applications are typically characterized by noisy data sets with approximate pairwise dissimilarities. As such, the efficacy of clustering methods in practical applications necessitates robustness to perturbations. In this paper, we perform a formal analysis of perturbation robustness, revealing that the extent to which algorithms can exhibit this desirable characteristic is inherently limited, and identifying the types of structures that allow popular clustering paradigms to discover meaningful clusters in spite of faulty data.
Efficient Processing of Reachability and Time-Based Path Queries in a Temporal Graph
Venue: arXiv cs.DB 2016
Year: 2016

A temporal graph is a graph in which vertices communicate with each other at specific time, e.g., $A$ calls $B$ at 11 a.m. and talks for 7 minutes, which is modeled by an edge from $A$ to $B$ with starting time "11 a.m." and duration "7 mins". Temporal graphs can be used to model many networks with time-related activities, but efficient algorithms for analyzing temporal graphs are severely inadequate. We study fundamental problems such as answering reachability and time-based path queries in a temporal graph, and propose an efficient indexing technique specifically designed for processing these queries in a temporal graph. Our results show that our method is efficient and scalable in both index construction and query processing.
Compressed sensing with corrupted observations
Venue: arXiv cs.IT 2016
Year: 2016

We proposed a weighted l1 minimization to recover a sparse signal vector and the corrupted noise vector from a linear measurement when the sensing matrix A is an m by n row i.i.d subgaussian matrix. We obtain both uniform and nonuniform recovery guarantees when the corrupted observations occupy a constant fraction of the total measurement, provided that the signal vector is sparse enough. In the uniform recovery guarantee, the upper-bound of the cardinality of the signal vector required in this paper is asymptotically optimal. While in the non-uniform recovery guarantee, we allow the proportion of corrupted measurements grows arbitrarily close to 1, and the upper-bound of the cardinality of the signal vector is better than those in a recent literature [1] by a ln(n) factor.
Data recovery from corrupted observations via l1 minimization
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies the problem of recovering a signal vector and the corrupted noise vector from a collection of corrupted linear measurements through the solution of a l1 minimization, where the sensing matrix is a partial Fourier matrix whose rows are selected randomly and uniformly from rows of a full Fourier matrix. After choosing the parameter in the l1 minimization appropriately, we show that the recovery can be successful even when a constant fraction of the measurements are arbitrarily corrupted, moreover, the proportion of corrupted measurement can grows arbitrarily close to 1, provided that the signal vector is sparse enough. The upper-bound on the sparsity of the signal vector required in this paper is asymptotically optimal and is better than those achieved by recent literatures [1, 2] by a ln(n) factor. Furthermore, the assumptions we impose on the signal vector and the corrupted noise vector are loosest comparing to the existing literatures [1-3], which lenders our recovery guarantees are more applicable. Extensive numerical experiments based on synthesis as well as real world data are presented to verify the conclusion of the proposed theorem and to demonstrate the potential of the l1 minimization framework.
Recommender systems inspired by the structure of quantum theory
Venue: arXiv cs.LG 2016
Year: 2016

Physicists use quantum models to describe the behavior of physical systems. Quantum models owe their success to their interpretability, to their relation to probabilistic models (quantization of classical models) and to their high predictive power. Beyond physics, these properties are valuable in general data science. This motivates the use of quantum models to analyze general nonphysical datasets. Here we provide both empirical and theoretical insights into the application of quantum models in data science. In the theoretical part of this paper, we firstly show that quantum models can be exponentially more efficient than probabilistic models because there exist datasets that admit low-dimensional quantum models and only exponentially high-dimensional probabilistic models. Secondly, we explain in what sense quantum models realize a useful relaxation of compressed probabilistic models. Thirdly, we show that sparse datasets admit low-dimensional quantum models and finally, we introduce a method to compute hierarchical orderings of properties of users (e.g., personality traits) and items (e.g., genres of movies). In the empirical part of the paper, we evaluate quantum models in item recommendation and observe that the predictive power of quantum-inspired recommender systems can compete with state-of-the-art recommender systems like SVD++ and PureSVD. Furthermore, we make use of the interpretability of quantum models by computing hierarchical orderings of properties of users and items. This work establishes a connection between data science (item recommendation), information theory (communication complexity), mathematical programming (positive semidefinite factorizations) and physics (quantum models).
Topology recognition with advice
Venue: arXiv cs.DC 2016
Year: 2016

In topology recognition, each node of an anonymous network has to deterministically produce an isomorphic copy of the underlying graph, with all ports correctly marked. This task is usually unfeasible without any a priori information. Such information can be provided to nodes as advice. An oracle knowing the network can give a (possibly different) string of bits to each node, and all nodes must reconstruct the network using this advice, after a given number of rounds of communication. During each round each node can exchange arbitrary messages with all its neighbors and perform arbitrary local computations. The time of completing topology recognition is the number of rounds it takes, and the size of advice is the maximum length of a string given to nodes. We investigate tradeoffs between the time in which topology recognition is accomplished and the minimum size of advice that has to be given to nodes. We provide upper and lower bounds on the minimum size of advice that is sufficient to perform topology recognition in a given time, in the class of all graphs of size $n$ and diameter $D\le αn$, for any constant $α< 1$. In most cases, our bounds are asymptotically tight.
Task Allocation for Distributed Stream Processing
Venue: arXiv cs.DC 2016
Year: 2016

There is a growing demand for live, on-the-fly processing of increasingly large amounts of data. In order to ensure the timely and reliable processing of streaming data, a variety of distributed stream processing architectures and platforms have been developed, which handle the fundamental tasks of (dynamically) assigning processing tasks to the currently available physical resources and routing streaming data between these resources. However, while there are plenty of platforms offering such functionality, the theory behind it is not well understood. In particular, it is unclear how to best allocate the processing tasks to the given resources. In this paper, we establish a theoretical foundation by formally defining a task allocation problem for distributed stream processing, which we prove to be NP-hard. Furthermore, we propose an approximation algorithm for the class of series-parallel decomposable graphs, which captures a broad range of common stream processing applications. The algorithm achieves a constant-factor approximation under the assumptions that the number of resources scales at least logarithmically with the number of computational tasks and the computational cost of the tasks dominates the cost of communication.
Unsupervised convolutional neural networks for motion estimation
Venue: arXiv cs.CV 2016
Year: 2016

Traditional methods for motion estimation estimate the motion field F between a pair of images as the one that minimizes a predesigned cost function. In this paper, we propose a direct method and train a Convolutional Neural Network (CNN) that when, at test time, is given a pair of images as input it produces a dense motion field F at its output layer. In the absence of large datasets with ground truth motion that would allow classical supervised training, we propose to train the network in an unsupervised manner. The proposed cost function that is optimized during training, is based on the classical optical flow constraint. The latter is differentiable with respect to the motion field and, therefore, allows backpropagation of the error to previous layers of the network. Our method is tested on both synthetic and real image sequences and performs similarly to the state-of-the-art methods.
Decision Aids for Adversarial Planning in Military Operations: Algorithms, Tools, and Turing-test-like Experimental Validation
Venue: arXiv cs.AI 2016
Year: 2016

Use of intelligent decision aids can help alleviate the challenges of planning complex operations. We describe integrated algorithms, and a tool capable of translating a high-level concept for a tactical military operation into a fully detailed, actionable plan, producing automatically (or with human guidance) plans with realistic degree of detail and of human-like quality. Tight interleaving of several algorithms -- planning, adversary estimates, scheduling, routing, attrition and consumption estimates -- comprise the computational approach of this tool. Although originally developed for Army large-unit operations, the technology is generic and also applies to a number of other domains, particularly in critical situations requiring detailed planning within a constrained period of time. In this paper, we focus particularly on the engineering tradeoffs in the design of the tool. In an experimental evaluation, reminiscent of the Turing test, the tool's performance compared favorably with human planners.
The Unbounded Benefit of Encoder Cooperation for the $k$-user MAC
Venue: arXiv cs.IT 2016
Year: 2016

Cooperation strategies allow communication devices to work together to improve network capacity. Consider a network consisting of a $k$-user multiple access channel (MAC) and a node that is connected to all $k$ encoders via rate-limited bidirectional links, referred to as the "cooperation facilitator" (CF). Define the cooperation benefit as the sum-capacity gain resulting from the communication between the encoders and the CF and the cooperation rate as the total rate the CF shares with the encoders. This work demonstrates the existence of a class of $k$-user MACs where the ratio of the cooperation benefit to cooperation rate tends to infinity as the cooperation rate tends to zero. Examples of channels in this class include the binary erasure MAC for $k=2$ and the $k$-user Gaussian MAC for any $k\geq 2$.
RioBusData: Outlier Detection in Bus Routes of Rio de Janeiro
Venue: arXiv cs.HC 2016
Year: 2016

Buses are the primary means of public transportation in the city of Rio de Janeiro, carrying around 100 million passengers every month. Recently, real-time GPS coordinates of all operating public buses has been made publicly available - roughly 1 million GPS entries each captured each day. In an initial study, we observed that a substantial number of buses follow trajectories that do not follow the expected behavior. In this paper, we present RioBusData, a tool that helps users identify and explore, through different visualizations, the behavior of outlier trajectories. We describe how the system automatically detects these outliers using a Convolutional Neural Network (CNN) and we also discuss a series of case studies which show how RioBusData helps users better understand not only the flow and service of outlier buses but also the bus system as a whole.
A Complete Uniform Substitution Calculus for Differential Dynamic Logic
Venue: arXiv cs.LO 2016
Year: 2016

This article introduces a relatively complete proof calculus for differential dynamic logic (dL) that is entirely based on uniform substitution, a proof rule that substitutes a formula for a predicate symbol everywhere. Uniform substitutions make it possible to use axioms instead of axiom schemata, thereby substantially simplifying implementations. Instead of subtle schema variables and soundness-critical side conditions on the occurrence patterns of logical variables to restrict infinitely many axiom schema instances to sound ones, the resulting calculus adopts only a finite number of ordinary dL formulas as axioms, which uniform substitutions instantiate soundly. The static semantics of differential dynamic logic and the soundness-critical restrictions it imposes on proof steps is captured exclusively in uniform substitutions and variable renamings as opposed to being spread in delicate ways across the prover implementation. In addition to sound uniform substitutions, this article introduces differential forms for differential dynamic logic that make it possible to internalize differential invariants, differential substitutions, and derivatives as first-class axioms to reason about differential equations axiomatically. The resulting axiomatization of differential dynamic logic is proved to be sound and relatively complete.
Disjunctive Probabilistic Modal Logic is Enough for Bisimilarity on Reactive Probabilistic Systems
Venue: arXiv cs.LO 2016
Year: 2016

Larsen and Skou characterized probabilistic bisimilarity over reactive probabilistic systems with a logic including true, negation, conjunction, and a diamond modality decorated with a probabilistic lower bound. Later on, Desharnais, Edalat, and Panangaden showed that negation is not necessary to characterize the same equivalence. In this paper, we prove that the logical characterization holds also when conjunction is replaced by disjunction, with negation still being not necessary. To this end, we introduce reactive probabilistic trees, a fully abstract model for reactive probabilistic systems that allows us to demonstrate expressiveness of the disjunctive probabilistic modal logic, as well as of the previously mentioned logics, by means of a compactness argument.
Towards a Human-Centred Approach in Modelling and Testing of Cyber-Physical Systems
Venue: arXiv cs.SE 2016
Year: 2016

The ability to capture different levels of abstraction in a system model is especially important for remote integration, testing/verification, and manufacturing of cyber-physical systems (CPSs). However, the complexity of modelling and testing of CPSs makes these processes extremely prone to human error. In this paper we present our ongoing work on introducing human-centred considerations into modelling and testing of CPSs, which allow for agile iterative refinement processes of different levels of abstraction when errors are discovered or missing information is completed.
An Achievable Rate Region for the Two-Way Multiple-Relay Channel
Venue: arXiv cs.IT 2016
Year: 2016

We propose an achievable rate-region for the two-way multiple-relay channel using decode-and-forward block Markovian coding. We identify a conflict between the information flow in both directions. This conflict leads to an intractable number of decode-forward schemes and achievable rate regions, none of which are universally better than the others. We introduce a new concept in decode-forward coding called ranking, and discover that there is an underlying structure to all of these rate regions expressed in the rank assignment. Through this discovery, we characterize the complete achievable rate region that includes all of the rate regions corresponding to the particular decode-forward schemes. This rate region is an extension of existing results for the two-way one-relay channel and the two-way two-relay channel.
Divide and Conquer Local Average Regression
Venue: arXiv cs.LG 2016
Year: 2016

The divide and conquer strategy, which breaks a massive data set into a se- ries of manageable data blocks, and then combines the independent results of data blocks to obtain a final decision, has been recognized as a state-of-the-art method to overcome challenges of massive data analysis. In this paper, we merge the divide and conquer strategy with local average regression methods to infer the regressive relationship of input-output pairs from a massive data set. After theoretically analyzing the pros and cons, we find that although the divide and conquer local average regression can reach the optimal learning rate, the restric- tion to the number of data blocks is a bit strong, which makes it only feasible for small number of data blocks. We then propose two variants to lessen (or remove) this restriction. Our results show that these variants can achieve the optimal learning rate with much milder restriction (or without such restriction). Extensive experimental studies are carried out to verify our theoretical assertions.