OpenRaiser/Intern-Atlas huggingface dataset:
Multi-feature combined cloud and cloud shadow detection in GaoFen-1 wide field of view imagery
Venue: arXiv cs.CV 2017
Year: 2017

The wide field of view (WFV) imaging system onboard the Chinese GaoFen-1 (GF-1) optical satellite has a 16-m resolution and four-day revisit cycle for large-scale Earth observation. The advantages of the high temporal-spatial resolution and the wide field of view make the GF-1 WFV imagery very popular. However, cloud cover is an inevitable problem in GF-1 WFV imagery, which influences its precise application. Accurate cloud and cloud shadow detection in GF-1 WFV imagery is quite difficult due to the fact that there are only three visible bands and one near-infrared band. In this paper, an automatic multi-feature combined (MFC) method is proposed for cloud and cloud shadow detection in GF-1 WFV imagery. The MFC algorithm first implements threshold segmentation based on the spectral features and mask refinement based on guided filtering to generate a preliminary cloud mask. The geometric features are then used in combination with the texture features to improve the cloud detection results and produce the final cloud mask. Finally, the cloud shadow mask can be acquired by means of the cloud and shadow matching and follow-up correction process. The method was validated using 108 globally distributed scenes. The results indicate that MFC performs well under most conditions, and the average overall accuracy of MFC cloud detection is as high as 96.8%. In the contrastive analysis with the official provided cloud fractions, MFC shows a significant improvement in cloud fraction estimation, and achieves a high accuracy for the cloud and cloud shadow detection in the GF-1 WFV imagery with fewer spectral bands. The proposed method could be used as a preprocessing step in the future to monitor land-cover change, and it could also be easily extended to other optical satellite imagery which has a similar spectral setting.
Stochastic Characteristics of Qubits and Qubit chains on the D-Wave 2X
Venue: arXiv cs.ET 2017
Year: 2017

This document presents a studies of the stochastic behavior of D-Wave qubits, qubit cells, and qubit chains. The purpose of this paper is to address the algorithmic behavior of execution rather than the physical behavior, though they are related. The measurements from an actual D-Wave adiabatic quantum computer are compare with calculated measurements from a theoretical adiabatic quantum computer running with an effective temperature of zero. In this way the paper attempts to shed light on how the D-Wave's behavior effects how well it minimizes its objective function and why the D-Wave performs as it does.
Cutwidth: obstructions and algorithmic aspects
Venue: arXiv cs.DS 2017
Year: 2017

Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most $k$ are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most $k$. We prove that every minimal immersion obstruction for cutwidth at most $k$ has size at most $2^{O(k^3\log k)}$. As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time $2^{O(k^2\log k)}\cdot n$, where $k$ is the optimum width and $n$ is the number of vertices. While being slower by a $\log k$-factor in the exponent than the fastest known algorithm, given by Thilikos, Bodlaender, and Serna in [Cutwidth I: A linear time fixed parameter algorithm, J. Algorithms, 56(1):1--24, 2005] and [Cutwidth II: Algorithms for partial $w$-trees of bounded degree, J. Algorithms, 56(1):25--49, 2005], our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts.
Optimal Finite-Length and Asymptotic Index Codes for Five or Fewer Receivers
Venue: arXiv cs.IT 2017
Year: 2017

Index coding models broadcast networks in which a sender sends different messages to different receivers simultaneously, where each receiver may know some of the messages a priori. The aim is to find the minimum (normalised) index codelength that the sender sends. This paper considers unicast index coding, where each receiver requests exactly one message, and each message is requested by exactly one receiver. Each unicast index-coding instances can be fully described by a directed graph and vice versa, where each vertex corresponds to one receiver. For any directed graph representing a unicast index-coding instance, we show that if a maximum acyclic induced subgraph (MAIS) is obtained by removing two or fewer vertices from the graph, then the minimum index codelength equals the number of vertices in the MAIS, and linear codes are optimal for the corresponding index-coding instance. Using this result, we solved all unicast index-coding instances with up to five receivers, which correspond to all graphs with up to five vertices. For 9819 non-isomorphic graphs among all graphs up to five vertices, we obtained the minimum index codelength for all message alphabet sizes; for the remaining 28 graphs, we obtained the minimum index codelength if the message alphabet size is $k^2$ for any positive integer $k$. This work complements the result by Arbabjolfaei et al. (ISIT 2013), who solved all unicast index-coding instances with up to five receivers in the asymptotic regime, where the message alphabet size tends to infinity.
Multiple Hypothesis Colorization
Venue: arXiv cs.CV 2017
Year: 2017

In this work we focus on the problem of colorization for image compression. Since color information occupies a large proportion of the total storage size of an image, a method that can predict accurate color from its grayscale version can produce dramatic reduction in image file size. But colorization for compression poses several challenges. First, while colorization for artistic purposes simply involves predicting plausible chroma, colorization for compression requires generating output colors that are as close as possible to the ground truth. Second, many objects in the real world exhibit multiple possible colors. Thus, to disambiguate the colorization problem some additional information must be stored to reproduce the true colors with good accuracy. To account for the multimodal color distribution of objects we propose a deep tree-structured network that generates multiple color hypotheses for every pixel from a grayscale picture (as opposed to a single color produced by most prior colorization approaches). We show how to leverage the multimodal output of our model to reproduce with high fidelity the true colors of an image by storing very little additional information. In the experiments we show that our proposed method outperforms traditional JPEG color coding by a large margin, producing colors that are nearly indistinguishable from the ground truth at the storage cost of just a few hundred bytes for high-resolution pictures!
Intriguingly Simple and Efficient Time-Dependent Routing in Road Networks
Venue: arXiv cs.DS 2017
Year: 2017

We study the earliest arrival problem in road networks with static time-dependent functions as arc weights. We propose and evaluate the following simple algorithm: (1) average the travel time in k time windows, (2) compute a shortest time-independent path within each window and mark the edges in these paths, and (3) compute a shortest time-dependent path in the original graph restricted to the marked edges. Our experimental evaluation shows that this simple algorithm yields near optimal results on well-established benchmark instances. We additionally demonstrate that the error can be further reduced by additionally considering alternative routes at the expense of more marked edges. Finally, we show that the achieved subgraphs are small enough to be able to efficiently implement profile queries using a simple sampling-based approach. A highlight of our introduced algorithms is that they do not rely on linking and merging profile functions.
Dynamical Systems On Weighted Lattices: General Theory
Venue: arXiv cs.SY 2017
Year: 2017

In this work a theory is developed for unifying large classes of nonlinear discrete-time dynamical systems obeying a superposition of a weighted maximum or minimum type. The state vectors and input-output signals evolve on nonlinear spaces which we call complete weighted lattices and include as special cases the nonlinear vector spaces of minimax algebra. Their algebraic structure has a polygonal geometry. Some of the special cases unified include max-plus, max-product, and probabilistic dynamical systems. We study problems of representation in state and input-output spaces using lattice monotone operators, state and output responses using nonlinear convolutions, solving nonlinear matrix equations using lattice adjunctions, stability and controllability. We outline applications in state-space modeling of nonlinear filtering; dynamic programming (Viterbi algorithm) and shortest paths (distance maps); fuzzy Markov chains; and tracking audio-visual salient events in multimodal information streams using generalized hidden Markov models with control inputs.
Sampling-based Gradient Regularization for Capturing Long-Term Dependencies in Recurrent Neural Networks
Venue: arXiv cs.NE 2017
Year: 2017

Vanishing (and exploding) gradients effect is a common problem for recurrent neural networks with nonlinear activation functions which use backpropagation method for calculation of derivatives. Deep feedforward neural networks with many hidden layers also suffer from this effect. In this paper we propose a novel universal technique that makes the norm of the gradient stay in the suitable range. We construct a way to estimate a contribution of each training example to the norm of the long-term components of the target function s gradient. Using this subroutine we can construct mini-batches for the stochastic gradient descent (SGD) training that leads to high performance and accuracy of the trained network even for very complex tasks. We provide a straightforward mathematical estimation of minibatch s impact on for the gradient norm and prove its correctness theoretically. To check our framework experimentally we use some special synthetic benchmarks for testing RNNs on ability to capture long-term dependencies. Our network can detect links between events in the (temporal) sequence at the range approx. 100 and longer.
True Lies
Venue: arXiv cs.AI 2017
Year: 2017

A true lie is a lie that becomes true when announced. In a logic of announcements, where the announcing agent is not modelled, a true lie is a formula (that is false and) that becomes true when announced. We investigate true lies and other types of interaction between announced formulas, their preconditions and their postconditions, in the setting of Gerbrandy's logic of believed announcements, wherein agents may have or obtain incorrect beliefs. Our results are on the satisfiability and validity of instantiations of these semantically defined categories, on iterated announcements, including arbitrarily often iterated announcements, and on syntactic characterization. We close with results for iterated announcements in the logic of knowledge (instead of belief), and for lying as private announcements (instead of public announcements) to different agents. Detailed examples illustrate our lying concepts.
Reviving Threshold-Moving: a Simple Plug-in Bagging Ensemble for Binary and Multiclass Imbalanced Data
Venue: arXiv cs.LG 2017
Year: 2017

Class imbalance presents a major hurdle in the application of data mining methods. A common practice to deal with it is to create ensembles of classifiers that learn from resampled balanced data. For example, bagged decision trees combined with random undersampling (RUS) or the synthetic minority oversampling technique (SMOTE). However, most of the resampling methods entail asymmetric changes to the examples of different classes, which in turn can introduce its own biases in the model. Furthermore, those methods require a performance measure to be specified a priori before learning. An alternative is to use a so-called threshold-moving method that a posteriori changes the decision threshold of a model to counteract the imbalance, thus has a potential to adapt to the performance measure of interest. Surprisingly, little attention has been paid to the potential of combining bagging ensemble with threshold-moving. In this paper, we present probability thresholding bagging (PT-bagging), a versatile plug-in method that fills this gap. Contrary to usual rebalancing practice, our method preserves the natural class distribution of the data resulting in well calibrated posterior probabilities. We also extend the proposed method to handle multiclass data. The method is validated on binary and multiclass benchmark data sets. We perform analyses that provide insights into the proposed method.
Learning Nash Equilibrium for General-Sum Markov Games from Batch Data
Venue: arXiv cs.GT 2017
Year: 2017

This paper addresses the problem of learning a Nash equilibrium in $γ$-discounted multiplayer general-sum Markov Games (MG). A key component of this model is the possibility for the players to either collaborate or team apart to increase their rewards. Building an artificial player for general-sum MGs implies to learn more complex strategies which are impossible to obtain by using techniques developed for two-player zero-sum MGs. In this paper, we introduce a new definition of $ε$-Nash equilibrium in MGs which grasps the strategy's quality for multiplayer games. We prove that minimizing the norm of two Bellman-like residuals implies the convergence to such an $ε$-Nash equilibrium. Then, we show that minimizing an empirical estimate of the $L_p$ norm of these Bellman-like residuals allows learning for general-sum games within the batch setting. Finally, we introduce a neural network architecture named NashNetwork that successfully learns a Nash equilibrium in a generic multiplayer general-sum turn-based MG.
Towards Plane Spanners of Degree 3
Venue: arXiv cs.CG 2017
Year: 2017

Let $S$ be a finite set of points in the plane that are in convex position. We present an algorithm that constructs a plane $\frac{3+4π}{3}$-spanner of $S$ whose vertex degree is at most 3. Let $Λ$ be the vertex set of a finite non-uniform rectangular lattice in the plane. We present an algorithm that constructs a plane $3\sqrt{2}$-spanner for $Λ$ whose vertex degree is at most 3. For points that are in the plane and in general position, we show how to compute plane degree-3 spanners with a linear number of Steiner points.
Robust Keystroke Biometric Anomaly Detection
Venue: arXiv cs.CR 2017
Year: 2017

The Keystroke Biometrics Ongoing Competition (KBOC) presented an anomaly detection challenge with a public keystroke dataset containing a large number of subjects and real-world aspects. Over 300 subjects typed case-insensitive repetitions of their first and last name, and as a result, keystroke sequences could vary in length and order depending on the usage of modifier keys. To deal with this, a keystroke alignment preprocessing algorithm was developed to establish a semantic correspondence between keystrokes in mismatched sequences. The method is robust in the sense that query keystroke sequences need only approximately match a target sequence, and alignment is agnostic to the particular anomaly detector used. This paper describes the fifteen best-performing anomaly detection systems submitted to the KBOC, which ranged from auto-encoding neural networks to ensemble methods. Manhattan distance achieved the lowest equal error rate of 5.32%, while all fifteen systems performed better than any other submission. Performance gains are shown to be due in large part not to the particular anomaly detector, but to preprocessing and score normalization techniques.
Unequal Error Protection Querying Policies for the Noisy 20 Questions Problem
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose an open-loop unequal-error-protection querying policy based on superposition coding for the noisy 20 questions problem. In this problem, a player wishes to successively refine an estimate of the value of a continuous random variable by posing binary queries and receiving noisy responses. When the queries are designed non-adaptively as a single block and the noisy responses are modeled as the output of a binary symmetric channel the 20 questions problem can be mapped to an equivalent problem of channel coding with unequal error protection (UEP). A new non-adaptive querying strategy based on UEP superposition coding is introduced whose estimation error decreases with an exponential rate of convergence that is significantly better than that of the UEP repetition coding introduced by Variani et al. (2015). With the proposed querying strategy, the rate of exponential decrease in the number of queries matches the rate of a closed-loop adaptive scheme where queries are sequentially designed with the benefit of feedback. Furthermore, the achievable error exponent is significantly better than that of random block codes employing equal error protection.
Learning without Forgetting
Venue: arXiv cs.CV 2017
Year: 2017

When building a unified vision system or gradually adding new capabilities to a system, the usual assumption is that training data for all tasks is always available. However, as the number of tasks grows, storing and retraining on such data becomes infeasible. A new problem arises where we add new capabilities to a Convolutional Neural Network (CNN), but the training data for its existing capabilities are unavailable. We propose our Learning without Forgetting method, which uses only new task data to train the network while preserving the original capabilities. Our method performs favorably compared to commonly used feature extraction and fine-tuning adaption techniques and performs similarly to multitask learning that uses original task data we assume unavailable. A more surprising observation is that Learning without Forgetting may be able to replace fine-tuning with similar old and new task datasets for improved new task performance.
maskSLIC: Regional Superpixel Generation with Application to Local Pathology Characterisation in Medical Images
Venue: arXiv cs.CV 2017
Year: 2017

Supervoxel methods such as Simple Linear Iterative Clustering (SLIC) are an effective technique for partitioning an image or volume into locally similar regions, and are a common building block for the development of detection, segmentation and analysis methods. We introduce maskSLIC an extension of SLIC to create supervoxels within regions-of-interest, and demonstrate,on examples from 2-dimensions to 4-dimensions, that maskSLIC overcomes issues that affect SLIC within an irregular mask. We highlight the benefits of this method through examples, and show that it is able to better represent underlying tumour subregions and achieves significantly better results than SLIC on the BRATS 2013 brain tumour challenge data (p=0.001) - outperforming SLIC on 18/20 scans. Finally, we show an application of this method for the analysis of functional tumour subregions and demonstrate that it is more effective than voxel clustering.
High-Performance Tensor Contraction without Transposition
Venue: arXiv cs.MS 2017
Year: 2017

Tensor computations--in particular tensor contraction (TC)--are important kernels in many scientific computing applications. Due to the fundamental similarity of TC to matrix multiplication (MM) and to the availability of optimized implementations such as the BLAS, tensor operations have traditionally been implemented in terms of BLAS operations, incurring both a performance and a storage overhead. Instead, we implement TC using the flexible BLIS framework, which allows for transposition (reshaping) of the tensor to be fused with internal partitioning and packing operations, requiring no explicit transposition operations or additional workspace. This implementation, TBLIS, achieves performance approaching that of MM, and in some cases considerably higher than that of traditional TC. Our implementation supports multithreading using an approach identical to that used for MM in BLIS, with similar performance characteristics. The complexity of managing tensor-to-matrix transformations is also handled automatically in our approach, greatly simplifying its use in scientific applications.
Optimal Tree Hash Modes: the Case of Trees Having their Leaves at All the Levels
Venue: arXiv cs.DC 2017
Year: 2017

A recent work shows how we can optimize a tree based mode of operation for a hash function where the sizes of input message blocks and digest are the same, subject to the constraint that the involved tree structure has all its leaves at the same depth. In this work, we show that we can further optimize the running time of such a mode by using a tree having leaves at all its levels. We make the assumption that the input message block has a size a multiple of that of the digest and denote by $d$ the ratio block size over digest size. The running time is evaluated in terms of number of operations performed by the hash function, i.e. the number of calls to its underlying function. It turns out that a digest can be computed in $\lceil \log_{d+1} (l/2) \rceil+2$ evaluations of the underlying function using $\lceil l/2 \rceil$ processors, where $l$ is the number of blocks of the message. Other results of interest are discussed, such as the optimization of the parallel running time for a tree of restricted height.
Localization, Decomposition, and Dictionary Learning of Piecewise-Constant Signals on Graphs
Venue: arXiv cs.SI 2017
Year: 2017

Motivated by the need to extract meaning from large amounts of complex structured data, we consider three critical problems on graphs: localization, decomposition, and dictionary learning of piecewise-constant signals. These graph-based problems are related to many real-world applications, such as localizing stimulus in brain connectivity networks, and mining traffic events in city street networks, where the key issue is to find the supports of localized activated patterns. Counterparts of these problems in classical signal/image processing, such as impulse detection and foreground detection, have been studied over the past few decades. We use piecewise-constant graph signals to model localized patterns, where each piece indicates a localized pattern that exhibits homogeneous internal behavior and the number of pieces indicates the number of localized patterns. For such signals, we show that decomposition and dictionary learning are natural extensions of localization, the goal of which is not only to efficiently approximate graph signals, but also to accurately find supports of localized patterns. For each of the three problems, i.e., localization, decomposition, and dictionary learning, we propose a specific graph signal model, an optimization problem, and a computationally efficient solver. The proposed solvers directly find the supports of arbitrary localized activated patterns without tuning any thresholds. We then conduct an extensive empirical study to validate the proposed methods on both simulated and real data including the analysis of a large volume of spatio-temporal Manhattan urban data. The analysis validates the effectiveness of the approach and suggests that graph signal processing tools may aid in urban planning and traffic forecasting.