OpenRaiser/Intern-Atlas huggingface dataset:
Texture Characterization by Using Shape Co-occurrence Patterns
Venue: arXiv cs.CV 2017
Year: 2017

Texture characterization is a key problem in image understanding and pattern recognition. In this paper, we present a flexible shape-based texture representation using shape co-occurrence patterns. More precisely, texture images are first represented by tree of shapes, each of which is associated with several geometrical and radiometric attributes. Then four typical kinds of shape co-occurrence patterns based on the hierarchical relationship of the shapes in the tree are learned as codewords. Three different coding methods are investigated to learn the codewords, with which, any given texture image can be encoded into a descriptive vector. In contrast with existing works, the proposed method not only inherits the strong ability to depict geometrical aspects of textures and the high robustness to variations of imaging conditions from the shape-based method, but also provides a flexible way to consider shape relationships and to compute high-order statistics on the tree. To our knowledge, this is the first time to use co-occurrence patterns of explicit shapes as a tool for texture analysis. Experiments on various texture datasets and scene datasets demonstrate the efficiency of the proposed method.
Modeling Semantic Expectation: Using Script Knowledge for Referent Prediction
Venue: arXiv cs.CL 2017
Year: 2017

Recent research in psycholinguistics has provided increasing evidence that humans predict upcoming content. Prediction also affects perception and might be a key to robustness in human language processing. In this paper, we investigate the factors that affect human prediction by building a computational model that can predict upcoming discourse referents based on linguistic knowledge alone vs. linguistic knowledge jointly with common-sense knowledge in the form of scripts. We find that script knowledge significantly improves model estimates of human predictions. In a second study, we test the highly controversial hypothesis that predictability influences referring expression type but do not find evidence for such an effect.
Fast and scalable minimal perfect hashing for massive key sets
Venue: arXiv cs.DS 2017
Year: 2017

Minimal perfect hash functions provide space-efficient and collision-free hashing on static sets. Existing algorithms and implementations that build such functions have practical limitations on the number of input elements they can process, due to high construction time, RAM or external memory usage. We revisit a simple algorithm and show that it is highly competitive with the state of the art, especially in terms of construction time and memory usage. We provide a parallel C++ implementation called BBhash. It is capable of creating a minimal perfect hash function of $10^{10}$ elements in less than 7 minutes using 8 threads and 5 GB of memory, and the resulting function uses 3.7 bits/element. To the best of our knowledge, this is also the first implementation that has been successfully tested on an input of cardinality $10^{12}$. Source code: https://github.com/rizkg/BBHash
Local Lexing
Venue: arXiv cs.LO 2017
Year: 2017

We introduce a novel parsing concept called local lexing. It integrates the classically separated stages of lexing and parsing by allowing lexing to be dependent upon the parsing progress and by providing a simple mechanism for constraining lexical ambiguity. This makes it possible for language design to be composable not only at the level of context-free grammars, but also at the lexical level. It also makes it possible to include lightweight error-handling directly as part of the language specification instead of leaving it up to the implementation. We present a high-level algorithm for local lexing, which is an extension of Earley's algorithm. We have formally verified the correctness of our algorithm with respect to its local lexing semantics in Isabelle/HOL.
Training Deep Neural Networks via Optimization Over Graphs
Venue: arXiv cs.LG 2017
Year: 2017

In this work, we propose to train a deep neural network by distributed optimization over a graph. Two nonlinear functions are considered: the rectified linear unit (ReLU) and a linear unit with both lower and upper cutoffs (DCutLU). The problem reformulation over a graph is realized by explicitly representing ReLU or DCutLU using a set of slack variables. We then apply the alternating direction method of multipliers (ADMM) to update the weights of the network layerwise by solving subproblems of the reformulated problem. Empirical results suggest that the ADMM-based method is less sensitive to overfitting than the stochastic gradient descent (SGD) and Adam methods.
Gathering Anonymous, Oblivious Robots on a Grid
Venue: arXiv cs.DC 2017
Year: 2017

We consider a swarm of $n$ autonomous mobile robots, distributed on a 2-dimensional grid. A basic task for such a swarm is the gathering process: All robots have to gather at one (not predefined) place. A common local model for extremely simple robots is the following: The robots do not have a common compass, only have a constant viewing radius, are autonomous and indistinguishable, can move at most a constant distance in each step, cannot communicate, are oblivious and do not have flags or states. The only gathering algorithm under this robot model, with known runtime bounds, needs $\mathcal{O}(n^2)$ rounds and works in the Euclidean plane. The underlying time model for the algorithm is the fully synchronous $\mathcal{FSYNC}$ model. On the other side, in the case of the 2-dimensional grid, the only known gathering algorithms for the same time and a similar local model additionally require a constant memory, states and "flags" to communicate these states to neighbors in viewing range. They gather in time $\mathcal{O}(n)$. In this paper we contribute the (to the best of our knowledge) first gathering algorithm on the grid that works under the same simple local model as the above mentioned Euclidean plane strategy, i.e., without memory (oblivious), "flags" and states. We prove its correctness and an $\mathcal{O}(n^2)$ time bound in the fully synchronous $\mathcal{FSYNC}$ time model. This time bound matches the time bound of the best known algorithm for the Euclidean plane mentioned above. We say gathering is done if all robots are located within a $2\times 2$ square, because in $\mathcal{FSYNC}$ such configurations cannot be solved.
Path Assignment Techniques For Vehicle Tracking
Venue: arXiv cs.SY 2017
Year: 2017

Many driver assistance systems such as Adaptive Cruise Control require the identification of the closest vehicle that is in the host vehicle's path. This entails an assignment of detected vehicles to the host vehicle path or neighboring paths. After reviewing approaches to the estimation of the host vehicle path and lane assignment techniques we introduce two methods that are motivated by the rationale to filter measured data as late in the processing stages as possible in order to avoid delays and other artifacts of intermediate filters. These filters generate discrete posterior probability distributions from which a path or "lane" index is extracted by a median estimator. The relative performance of those methods is illustrated by a ROC using experimental data and labeled ground truth data.
Distributed Mapping with Privacy and Communication Constraints: Lightweight Algorithms and Object-based Models
Venue: arXiv cs.RO 2017
Year: 2017

We consider the following problem: a team of robots is deployed in an unknown environment and it has to collaboratively build a map of the area without a reliable infrastructure for communication. The backbone for modern mapping techniques is pose graph optimization, which estimates the trajectory of the robots, from which the map can be easily built. The first contribution of this paper is a set of distributed algorithms for pose graph optimization: rather than sending all sensor data to a remote sensor fusion server, the robots exchange very partial and noisy information to reach an agreement on the pose graph configuration. Our approach can be considered as a distributed implementation of the two-stage approach of Carlone et al., where we use the Successive Over-Relaxation (SOR) and the Jacobi Over-Relaxation (JOR) as workhorses to split the computation among the robots. As a second contribution, we extend %and demonstrate the applicability of the proposed distributed algorithms to work with object-based map models. The use of object-based models avoids the exchange of raw sensor measurements (e.g., point clouds) further reducing the communication burden. Our third contribution is an extensive experimental evaluation of the proposed techniques, including tests in realistic Gazebo simulations and field experiments in a military test facility. Abundant experimental evidence suggests that one of the proposed algorithms (the Distributed Gauss-Seidel method or DGS) has excellent performance. The DGS requires minimal information exchange, has an anytime flavor, scales well to large teams, is robust to noise, and is easy to implement. Our field tests show that the combined use of our distributed algorithms and object-based models reduces the communication requirements by several orders of magnitude and enables distributed mapping with large teams of robots in real-world problems.
Energy Efficiency Challenges of 5G Small Cell Networks
Venue: arXiv cs.NI 2017
Year: 2017

The deployment of a large number of small cells poses new challenges to energy efficiency, which has often been ignored in fifth generation (5G) cellular networks. While massive multiple-input multiple outputs (MIMO) will reduce the transmission power at the expense of higher computational cost, the question remains as to which computation or transmission power is more important in the energy efficiency of 5G small cell networks. Thus, the main objective in this paper is to investigate the computation power based on the Landauer principle. Simulation results reveal that more than 50% of the energy is consumed by the computation power at 5G small cell BS's. Moreover, the computation power of 5G small cell BS can approach 800 watt when the massive MIMO (e.g., 128 antennas) is deployed to transmit high volume traffic. This clearly indicates that computation power optimization can play a major role in the energy efficiency of small cell networks.
Axioms for behavioural congruence of single-pass instruction sequences
Venue: arXiv cs.PL 2017
Year: 2017

In program algebra, an algebraic theory of single-pass instruction sequences, three congruences on instruction sequences are paid attention to: instruction sequence congruence, structural congruence, and behavioural congruence. Sound and complete axiom systems for the first two congruences were already given in early papers on program algebra. The current paper is the first one that is concerned with an axiom system for the third congruence. The presented axiom system is especially notable for its axioms that have to do with forward jump instructions.
System Modeling in the COSMA Environment
Venue: arXiv cs.DC 2017
Year: 2017

The aim of this paper is to demonstrate how the COSMA environment can be used for system modeling. This environment is a set of tools based on Concurrent State Machines paradigm and is developed in the Institute of Computer Science at the Warsaw University of Technology. Our demonstration example is a distributed brake control system dedicated for a railway transport. The paper shortly introduces COSMA. Next it shows how the example model can be validated by our temporal logic analyzer.
Underwater Optical Image Processing: A Comprehensive Review
Venue: arXiv cs.CV 2017
Year: 2017

Underwater cameras are widely used to observe the sea floor. They are usually included in autonomous underwater vehicles, unmanned underwater vehicles, and in situ ocean sensor networks. Despite being an important sensor for monitoring underwater scenes, there exist many issues with recent underwater camera sensors. Because of lights transportation characteristics in water and the biological activity at the sea floor, the acquired underwater images often suffer from scatters and large amounts of noise. Over the last five years, many methods have been proposed to overcome traditional underwater imaging problems. This paper aims to review the state-of-the-art techniques in underwater image processing by highlighting the contributions and challenges presented in over 40 papers. We present an overview of various underwater image processing approaches, such as underwater image descattering, underwater image color restoration, and underwater image quality assessments. Finally, we summarize the future trends and challenges in designing and processing underwater imaging sensors.
Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
Venue: arXiv cs.LG 2017
Year: 2017

In the Best-$k$-Arm problem, we are given $n$ stochastic bandit arms, each associated with an unknown reward distribution. We are required to identify the $k$ arms with the largest means by taking as few samples as possible. In this paper, we make progress towards a complete characterization of the instance-wise sample complexity bounds for the Best-$k$-Arm problem. On the lower bound side, we obtain a novel complexity term to measure the sample complexity that every Best-$k$-Arm instance requires. This is derived by an interesting and nontrivial reduction from the Best-$1$-Arm problem. We also provide an elimination-based algorithm that matches the instance-wise lower bound within doubly-logarithmic factors. The sample complexity of our algorithm strictly dominates the state-of-the-art for Best-$k$-Arm (module constant factors).
Complexity of mixed equilibria in Boolean games
Venue: arXiv cs.GT 2017
Year: 2017

Boolean games are a succinct representation of strategic games wherein a player seeks to satisfy a formula of propositional logic by selecting a truth assignment to a set of propositional variables under his control. The framework has proven popular within the multiagent community, however, almost invariably, the work to date has been restricted to the case of pure strategies. Such a focus is highly restrictive as the notion of randomised play is fundamental to the theory of strategic games -- even very simple games can fail to have pure-strategy equilibria, but every finite game has at least one equilibrium in mixed strategies. To address this, the present work focuses on the complexity of algorithmic problems dealing with mixed strategies in Boolean games. The main result is that the problem of determining whether a two-player game has an equilibrium satisfying a given payoff constraint is NEXP-complete. Based on this result, we then demonstrate that a number of other decision problems, such as the uniqueness of an equilibrium or the satisfaction of a given formula in equilibrium, are either NEXP or coNEXP-complete. The proof techniques developed in the course of this are then used to show that the problem of deciding whether a given profile is in equilibrium is coNP^#P-hard, and the problem of deciding whether a Boolean game has a rational-valued equilibrium is NEXP-hard, and whether a two-player Boolean game has an irrational-valued equilibrium is NEXP-complete. Finally, we show that determining whether the value of a two-player zero-sum game exceeds a given threshold is EXP-complete.
Separation of AC$^0[\oplus]$ Formulas and Circuits
Venue: arXiv cs.CC 2017
Year: 2017

This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the $\mathrm{AC}^0[\oplus]$ basis (unbounded fan-in AND, OR, NOT and MOD$_2$ gates). We show, for all $d(n) \le O(\frac{\log n}{\log\log n})$, that there exist {\em polynomial-size depth-$d$ circuits} that are not equivalent to {\em depth-$d$ formulas of size $n^{o(d)}$} (moreover, this is optimal in that $n^{o(d)}$ cannot be improved to $n^{O(d)}$). This result is obtained by a combination of new lower and upper bounds for {\em Approximate Majorities}, the class of Boolean functions $\{0,1\}^n \to \{0,1\}$ that agree with the Majority function on $3/4$ fraction of inputs. $\mathrm{AC}^0[\oplus]$ formula lower bound: We show that every depth-$d$ $\mathrm{AC}^0[\oplus]$ formula of size $s$ has a {\em $1/8$-error polynomial approximation} over $\mathbb{F}_2$ of degree $O(\frac{1}{d}\log s)^{d-1}$. This strengthens a classic $O(\log s)^{d-1}$ degree approximation for \underline{circuits} due to Razborov. Since the Majority function has approximate degree $Θ(\sqrt n)$, this result implies an $\exp(Ω(dn^{1/2(d-1)}))$ lower bound on the depth-$d$ $\mathrm{AC}^0[\oplus]$ formula size of all Approximate Majority functions for all $d(n) \le O(\log n)$. Monotone $\mathrm{AC}^0$ circuit upper bound: For all $d(n) \le O(\frac{\log n}{\log\log n})$, we give a randomized construction of depth-$d$ monotone $\mathrm{AC}^0$ circuits (without NOT or MOD$_2$ gates) of size $\exp(O(n^{1/2(d-1)}))$ that compute an Approximate Majority function. This strengthens a construction of \underline{formulas} of size $\exp(O(dn^{1/2(d-1)}))$ due to Amano.
Model-Free MLE Estimation for Online Rotor Angle Stability Assessment with PMU Data
Venue: arXiv cs.SY 2017
Year: 2017

Recent research has demonstrated that the rotor angle stability can be assessed by identifying the sign of the system maximal Lyapunov exponent (MLE). A positive (negative) MLE implies unstable (stable) rotor angle dynamics. However, because the MLE may fluctuate between positive and negative values for a long time after a severe disturbance, it is difficult to determine the system stability when observing a positive or negative MLE without knowing its further fluctuation trend. In this paper, a new approach for online rotor angle stability assessment is proposed to address this problem. The MLE is estimated by a recursive least square (RLS) based method based on real-time rotor angle measurements, and two critical parameters, the Theiler window and the MLE estimation initial time step, are carefully chosen to make sure the calculated MLE curves present distinct features for different stability conditions. By using the proposed stability assessment criteria, the developed approach can provide timely and reliable assessment of the rotor angle stability. Extensive tests on the New-England 39-bus system and the Northeast Power Coordinating Council 140-bus system verify the effectiveness of the proposed approach.
On Seeking Consensus Between Document Similarity Measures
Venue: arXiv cs.AI 2017
Year: 2017

This paper investigates the application of consensus clustering and meta-clustering to the set of all possible partitions of a data set. We show that when using a "complement" of Rand Index as a measure of cluster similarity, the total-separation partition, putting each element in a separate set, is chosen.
Analyzing and Visualizing Scalar Fields on Graphs
Venue: arXiv cs.DB 2017
Year: 2017

The value proposition of a dataset often resides in the implicit interconnections or explicit relationships (patterns) among individual entities, and is often modeled as a graph. Effective visualization of such graphs can lead to key insights uncovering such value. In this article we propose a visualization method to explore graphs with numerical attributes associated with nodes (or edges) -- referred to as scalar graphs. Such numerical attributes can represent raw content information, similarities, or derived information reflecting important network measures such as triangle density and centrality. The proposed visualization strategy seeks to simultaneously uncover the relationship between attribute values and graph topology, and relies on transforming the network to generate a terrain map. A key objective here is to ensure that the terrain map reveals the overall distribution of components-of-interest (e.g. dense subgraphs, k-cores) and the relationships among them while being sensitive to the attribute values over the graph. We also design extensions that can capture the relationship across multiple numerical attributes (scalars). We demonstrate the efficacy of our method on several real-world data science tasks while scaling to large graphs with millions of nodes.
Estimation of the volume of the left ventricle from MRI images using deep neural networks
Venue: arXiv cs.CV 2017
Year: 2017

Segmenting human left ventricle (LV) in magnetic resonance imaging (MRI) images and calculating its volume are important for diagnosing cardiac diseases. In 2016, Kaggle organized a competition to estimate the volume of LV from MRI images. The dataset consisted of a large number of cases, but only provided systole and diastole volumes as labels. We designed a system based on neural networks to solve this problem. It began with a detector combined with a neural network classifier for detecting regions of interest (ROIs) containing LV chambers. Then a deep neural network named hypercolumns fully convolutional network was used to segment LV in ROIs. The 2D segmentation results were integrated across different images to estimate the volume. With ground-truth volume labels, this model was trained end-to-end. To improve the result, an additional dataset with only segmentation label was used. The model was trained alternately on these two datasets with different types of teaching signals. We also proposed a variance estimation method for the final prediction. Our algorithm ranked the 4th on the test set in this competition.
Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
Venue: arXiv cs.LG 2017
Year: 2017

Stochastic Gradient Langevin Dynamics (SGLD) is a popular variant of Stochastic Gradient Descent, where properly scaled isotropic Gaussian noise is added to an unbiased estimate of the gradient at each iteration. This modest change allows SGLD to escape local minima and suffices to guarantee asymptotic convergence to global minimizers for sufficiently regular non-convex objectives (Gelfand and Mitter, 1991). The present work provides a nonasymptotic analysis in the context of non-convex learning problems, giving finite-time guarantees for SGLD to find approximate minimizers of both empirical and population risks. As in the asymptotic setting, our analysis relates the discrete-time SGLD Markov chain to a continuous-time diffusion process. A new tool that drives the results is the use of weighted transportation cost inequalities to quantify the rate of convergence of SGLD to a stationary distribution in the Euclidean $2$-Wasserstein distance.
T-ROME: A Simple and Energy Efficient Tree Routing Protocol for Low-Power Wake-up Receivers
Venue: arXiv cs.NI 2017
Year: 2017

Wireless sensor networks are deployed in many monitoring applications but still suffer from short lifetimes originating from limited energy sources and storages. Due to their low-power consumption and their on-demand communication ability, wake-up receivers represent an energy efficient and simple enhancement to wireless sensor nodes and wireless sensor network protocols. In this context, wake-up receivers have the ability to increase the network lifetime. In this article, we present T-ROME, a simple and energy efficient cross-layer routing protocol for wireless sensor nodes containing wake-up receivers. The protocol makes use of the different transmission ranges of wake-up and main radios in order to save energy by skipping nodes during data transfer. With respect to energy consumption and latency, T-ROME outperforms existing protocols in many scenarios. Here, we describe and analyze the cross layer multi-hop protocol by means of a Markov chain model that we verify using a laboratory test setup.