OpenRaiser/Intern-Atlas huggingface dataset:
Enhanced Local Binary Patterns for Automatic Face Recognition
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents a novel automatic face recognition approach based on local binary patterns. This descriptor considers a local neighbourhood of a pixel to compute the feature vector values. This method is not very robust to handle image noise, variances and different illumination conditions. We address these issues by proposing a novel descriptor which considers more pixels and different neighbourhoods to compute the feature vector values. The proposed method is evaluated on two benchmark corpora, namely UFI and FERET face datasets. We experimentally show that our approach outperforms state-of-the-art methods and is efficient particularly in the real conditions where the above mentioned issues are obvious. We further show that the proposed method handles well one training sample issue and is also robust to the image resolution.
On Realistic Target Coverage by Autonomous Drones
Venue: arXiv cs.RO 2018
Year: 2018

Low-cost mini-drones with advanced sensing and maneuverability enable a new class of intelligent sensing systems. To achieve the full potential of such drones, it is necessary to develop new enhanced formulations of both common and emerging sensing scenarios. Namely, several fundamental challenges in visual sensing remain unsolved including: 1) Fitting sizable targets in camera frames; 2) Effective viewpoints matching target poses; 3) Occlusion by elements in the environment, including other targets. In this paper, we introduce Argus: an autonomous system that utilizes drones to incrementally collect target information through a two-tier architecture. To tackle the stated challenges, Argus employs a novel geometric model that captures both target shapes and coverage constraints. Recognizing drones as the scarcest resource, Argus aims to minimize the number of drones required to cover a set of targets. We prove this problem is NP-hard, and even hard to approximate, before deriving a best-possible approximation algorithm along with a competitive sampling heuristic which runs up to 100x faster according to large-scale simulations. To test Argus in action, we demonstrate and analyze its performance on a prototype implementation. Finally, we present a number of extensions to accommodate more application requirements and highlight some open problems.
Selecting with History
Venue: arXiv cs.DS 2018
Year: 2018

We define a new selection problem, \emph{Selecting with History}, which extends the secretary problem to a setting with historical information. We propose a strategy for this problem and calculate its success probability in the limit of a large sequence.
Monadic Second Order Logic with Measure and Category Quantifiers
Venue: arXiv cs.LO 2018
Year: 2018

We investigate the extension of Monadic Second Order logic, interpreted over infinite words and trees, with generalized "for almost all" quantifiers interpreted using the notions of Baire category and Lebesgue measure.
A Game-Semantic Model of Computation
Venue: arXiv cs.LO 2018
Year: 2018

The present paper introduces a novel notion of `(effective) computability', called viability, of strategies in game semantics in an intrinsic (i.e., without recourse to the standard Church-Turing computability), non-inductive and non-axiomatic manner, and shows, as a main technical achievement, that viable strategies are Turing complete. Consequently, we have given a mathematical foundation of computation in the same sense as Turing machines but beyond computation on natural numbers, e.g., higher-order computation, in a more abstract fashion. As immediate corollaries, some of the well-known theorems in computability theory such as the smn-theorem and the first recursion theorem are generalized. Notably, our game-semantic framework distinguishes `high-level' computational processes that operate directly on mathematical objects such as natural numbers (not on their symbolic representations) and their `symbolic implementations' that define their `computability', which sheds new light on the very concept of computation. This work is intended to be a stepping stone towards a new mathematical foundation of computation, intuitionistic logic and constructive mathematics.
A Simple Scheme for Distributed Passive Load Balancing in Mobile Ad-hoc Networks
Venue: arXiv cs.NI 2018
Year: 2018

Efficient routing is one of the key challenges for next generation vehicular networks in order to provide fast and reliable communication in a smart city context. Various routing protocols have been proposed for determining optimal routing paths in highly dynamic topologies. However, it is the dilemma of those kinds of networks that good paths are used intensively, resulting in congestion and path quality degradation. In this paper, we adopt ideas from multipath routing and propose a simple decentral scheme for Mobile Ad-hoc Network (MANET) routing, which handles passive load balancing without requiring additional communication effort. It can easily be applied to existing routing protocols to achieve load balancing without changing the routing process itself. In comprehensive simulation studies, we apply the proposed load balancing technique to multiple example protocols and evaluate its effects on the network performance. The results show that all considered protocols can achieve significantly higher reliability and improved Packet Delivery Ratio (PDR) values by applying the proposed load balancing scheme.
An algebraic approach to MSO-definability on countable linear orderings
Venue: arXiv cs.LO 2018
Year: 2018

We develop an algebraic notion of recognizability for languages of words indexed by countable linear orderings. We prove that this notion is effectively equivalent to definability in monadic second-order (MSO) logic. We also provide three logical applications. First, we establish the first known collapse result for the quantifier alternation of MSO logic over countable linear orderings. Second, we solve an open problem posed by Gurevich and Rabinovich, concerning the MSO-definability of sets of rational numbers using the reals in the background. Third, we establish the MSO-definability of the set of yields induced by an MSO-definable set of trees, confirming a conjecture posed by Bruy{è}re, Carton, and S{é}nizergues.
Antenna Count for Massive MIMO: 1.9 GHz versus 60 GHz
Venue: arXiv cs.IT 2018
Year: 2018

If we assume line-of-sight propagation and perfect channel state information at the base station -- consistent with slow moving terminals -- then a direct performance comparison between single-cell Massive MIMO at PCS and mmWave frequency bands is straightforward and highly illuminating. Line-of-sight propagation is considered favorable for mmWave because of minimal attenuation, and its facilitation of hybrid beamforming to reduce the required number of active transceivers. We quantify the number of mmWave (60 GHz) service antennas that are needed to duplicate the performance of a specified number of PCS (1.9 GHz) service antennas. As a baseline we consider a modest PCS deployment of 128 antennas serving 18 terminals. We find that, to achieve the same per-terminal max-min 95%-likely downlink throughput, 10000 mmWave antennas are needed. To match the total antenna area of the PCS array would require 128000 half-wavelength mmWave antennas, but a much reduced number is adequate because the large number of antennas also confers greater channel orthogonality. The principal alleged benefit of mmWave technology--vast amounts of inexpensive spectrum--is at least partially offset by the complexity of possibly unwieldy amounts of hardware.
1-Fan-Bundle-Planar Drawings of Graphs
Venue: arXiv cs.CG 2018
Year: 2018

Edge bundling is an important concept heavily used for graph visualization purposes. To enable the comparison with other established near-planarity models in graph drawing, we formulate a new edge-bundling model which is inspired by the recently introduced fan-planar graphs. In particular, we restrict the bundling to the end segments of the edges. Similarly to 1-planarity, we call our model 1-fan-bundle-planarity, as we allow at most one crossing per bundle. For the two variants where we allow either one or, more naturally, both end segments of each edge to be part of bundles, we present edge density results and consider various recognition questions, not only for general graphs, but also for the outer and 2-layer variants. We conclude with a series of challenging questions.
Task-Space Consensus of Networked Robotic Systems: Separation and Manipulability
Venue: arXiv cs.SY 2018
Year: 2018

In this paper, we investigate the task-space consensus problem for multiple robotic systems with both the uncertain kinematics and dynamics and address two main issues, i.e., the separation of the kinematic and dynamic loops in the case of no task-space velocity measurement and the quantification of the manipulability of the system. We propose an observer-based adaptive controller to achieve the manipulable consensus without relying on the measurement of task-space velocities, and also formalize the concept of manipulability to quantify the degree of adjustability of the consensus value. The proposed adaptive controller employs a new distributed observer that does not rely on the joint velocity and a new kinematic parameter adaptation law with a distributed adaptive kinematic regressor matrix that is driven by both the observation and consensus errors. In addition, it is shown that the proposed controller has the separation property, which yields an adaptive kinematic controller that is applicable to most industrial/commercial robots. The performance of the proposed observer-based adaptive schemes is shown by numerical simulations.
Parameterized Aspects of Triangle Enumeration
Venue: arXiv cs.DS 2018
Year: 2018

The task of listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration. We provide both positive results (new enumerative kernelizations, "subcubic" parameterized solving algorithms) as well as negative results (presumable uselessness in terms of "faster" parameterized algorithms of certain parameters such as graph diameter). To this end, we introduce new and extend previous concepts.
A Converse to Banach's Fixed Point Theorem and its CLS Completeness
Venue: arXiv cs.CC 2018
Year: 2018

Banach's fixed point theorem for contraction maps has been widely used to analyze the convergence of iterative methods in non-convex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach's theorem limited. We explore how generally we can apply Banach's fixed point theorem to establish the convergence of iterative methods when pairing it with carefully designed metrics. Our first result is a strong converse of Banach's theorem, showing that it is a universal analysis tool for establishing global convergence of iterative methods to unique fixed points, and for bounding their convergence rate. In other words, we show that, whenever an iterative map globally converges to a unique fixed point, there exists a metric under which the iterative map is contracting and which can be used to bound the number of iterations until convergence. We illustrate our approach in the widely used power method, providing a new way of bounding its convergence rate through contraction arguments. We next consider the computational complexity of Banach's fixed point theorem. Making the proof of our converse theorem constructive, we show that computing a fixed point whose existence is guaranteed by Banach's fixed point theorem is CLS-complete. We thus provide the first natural complete problem for the class CLS, which was defined in [Daskalakis, Papadimitriou 2011] to capture the complexity of problems such as P-matrix LCP, computing KKT-points, and finding mixed Nash equilibria in congestion and network coordination games.
Strongly-Typed Agents are Guaranteed to Interact Safely
Venue: arXiv cs.LG 2018
Year: 2018

As artificial agents proliferate, it is becoming increasingly important to ensure that their interactions with one another are well-behaved. In this paper, we formalize a common-sense notion of when algorithms are well-behaved: an algorithm is safe if it does no harm. Motivated by recent progress in deep learning, we focus on the specific case where agents update their actions according to gradient descent. The paper shows that that gradient descent converges to a Nash equilibrium in safe games. The main contribution is to define strongly-typed agents and show they are guaranteed to interact safely, thereby providing sufficient conditions to guarantee safe interactions. A series of examples show that strong-typing generalizes certain key features of convexity, is closely related to blind source separation, and introduces a new perspective on classical multilinear games based on tensor decomposition.
Automatic segmentation of trees in dynamic outdoor environments
Venue: arXiv cs.CV 2018
Year: 2018

Segmentation in dynamic outdoor environments can be difficult when the illumination levels and other aspects of the scene cannot be controlled. Specifically in orchard and vineyard automation contexts, a background material is often used to shield a camera's field of view from other rows of crops. In this paper, we describe a method that uses superpixels to determine low texture regions of the image that correspond to the background material, and then show how this information can be integrated with the color distribution of the image to compute optimal segmentation parameters to segment objects of interest. Quantitative and qualitative experiments demonstrate the suitability of this approach for dynamic outdoor environments, specifically for tree reconstruction and apple flower detection applications.
Fast and robust curve skeletonization for real-world elongated objects
Venue: arXiv cs.CV 2018
Year: 2018

We consider the problem of extracting curve skeletons of three-dimensional, elongated objects given a noisy surface, which has applications in agricultural contexts such as extracting the branching structure of plants. We describe an efficient and robust method based on breadth-first search that can determine curve skeletons in these contexts. Our approach is capable of automatically detecting junction points as well as spurious segments and loops. All of that is accomplished with only one user-adjustable parameter. The run time of our method ranges from hundreds of milliseconds to less than four seconds on large, challenging datasets, which makes it appropriate for situations where real-time decision making is needed. Experiments on synthetic models as well as on data from real world objects, some of which were collected in challenging field conditions, show that our approach compares favorably to classical thinning algorithms as well as to recent contributions to the field.
A Decomposition of Forecast Error in Prediction Markets
Venue: arXiv cs.GT 2018
Year: 2018

We analyze sources of error in prediction market forecasts in order to bound the difference between a security's price and the ground truth it estimates. We consider cost-function-based prediction markets in which an automated market maker adjusts security prices according to the history of trade. We decompose the forecasting error into three components: sampling error, arising because traders only possess noisy estimates of ground truth; market-maker bias, resulting from the use of a particular market maker (i.e., cost function) to facilitate trade; and convergence error, arising because, at any point in time, market prices may still be in flux. Our goal is to make explicit the tradeoffs between these error components, influenced by design decisions such as the functional form of the cost function and the amount of liquidity in the market. We consider a specific model in which traders have exponential utility and exponential-family beliefs representing noisy estimates of ground truth. In this setting, sampling error vanishes as the number of traders grows, but there is a tradeoff between the other two components. We provide both upper and lower bounds on market-maker bias and convergence error, and demonstrate via numerical simulations that these bounds are tight. Our results yield new insights into the question of how to set the market's liquidity parameter and into the forecasting benefits of enforcing coherent prices across securities.
The Persistent Homotopy Type Distance
Venue: arXiv cs.CG 2018
Year: 2018

We introduce the persistent homotopy type distance dHT to compare real valued functions defined on possibly different homotopy equivalent topological spaces. The underlying idea in the definition of dHT is to measure the minimal shift that is necessary to apply to one of the two functions in order that the sublevel sets of the two functions become homotopically equivalent. This distance is interesting in connection with persistent homology. Indeed, our main result states that dHT still provides an upper bound for the bottleneck distance between the persistence diagrams of the intervening functions. Moreover, because homotopy equivalences are weaker than homeomorphisms, this implies a lifting of the standard stability results provided by the L-infty distance and the natural pseudo-distance dNP. From a different standpoint, we prove that dHT extends the L-infty distance and dNP in two ways. First, we show that, appropriately restricting the category of objects to which dHT applies, it can be made to coincide with the other two distances. Finally, we show that dHT has an interpretation in terms of interleavings that naturally places it in the family of distances used in persistence theory.
A survey on difference hierarchies of regular languages
Venue: arXiv cs.FL 2018
Year: 2018

Difference hierarchies were originally introduced by Hausdorff and they play an important role in descriptive set theory. In this survey paper, we study difference hierarchies of regular languages. The first sections describe standard techniques on difference hierarchies, mostly due to Hausdorff. We illustrate these techniques by giving decidability results on the difference hierarchies based on shuffle ideals, strongly cyclic regular languages and the polynomial closure of group languages.
MmWave vehicle-to-infrastructure communication: Analysis of urban microcellular networks
Venue: arXiv cs.NI 2018
Year: 2018

Vehicle-to-infrastructure (V2I) communication may provide high data rates to vehicles via millimeter-wave (mmWave) microcellular networks. This paper uses stochastic geometry to analyze the coverage of urban mmWave microcellular networks. Prior work used a pathloss model with a line-of-sight probability function based on randomly oriented buildings, to determine whether a link was line-of-sight or non-line-of-sight. In this paper, we use a pathloss model inspired by measurements, which uses a Manhattan distance pathloss model and accounts for differences in pathloss exponents and losses when turning corners. In our model, streets are randomly located as a Manhattan Poisson line process (MPLP) and the base stations (BSs) are distributed according to a Poisson point process. Our model is well suited for urban microcellular networks where the BSs are deployed at street level. Based on this new approach, we derive the coverage probability under certain BS association rules to obtain closed-form solutions without much complexity. In addition, we draw two main conclusions from our work. First, non-line-of-sight BSs are not a major benefit for association or source of interference most of the time. Second, there is an ultra-dense regime where deploying active BSs does not enhance coverage.
Memory-Efficient Global Refinement of Decision-Tree Ensembles and its Application to Face Alignment
Venue: arXiv cs.CV 2018
Year: 2018

Ren et al. recently introduced a method for aggregating multiple decision trees into a strong predictor by interpreting a path taken by a sample down each tree as a binary vector and performing linear regression on top of these vectors stacked together. They provided experimental evidence that the method offers advantages over the usual approaches for combining decision trees (random forests and boosting). The method truly shines when the regression target is a large vector with correlated dimensions, such as a 2D face shape represented with the positions of several facial landmarks. However, we argue that their basic method is not applicable in many practical scenarios due to large memory requirements. This paper shows how this issue can be solved through the use of quantization and architectural changes of the predictor that maps decision tree-derived encodings to the desired output.
Formal Synthesis of Control Strategies for Positive Monotone Systems
Venue: arXiv cs.SY 2018
Year: 2018

We design controllers from formal specifications for positive discrete-time monotone systems that are subject to bounded disturbances. Such systems are widely used to model the dynamics of transportation and biological networks. The specifications are described using signal temporal logic (STL), which can express a broad range of temporal properties. We formulate the problem as a mixed-integer linear program (MILP) and show that under the assumptions made in this paper, which are not restrictive for traffic applications, the existence of open-loop control policies is sufficient and almost necessary to ensure the satisfaction of STL formulas. We establish a relation between satisfaction of STL formulas in infinite time and set-invariance theories and provide an efficient method to compute robust control invariant sets in high dimensions. We also develop a robust model predictive framework to plan controls optimally while ensuring the satisfaction of the specification. Illustrative examples and a traffic management case study are included.
The Shattered Gradients Problem: If resnets are the answer, then what is the question?
Venue: arXiv cs.NE 2018
Year: 2018

A long-standing obstacle to progress in deep learning is the problem of vanishing and exploding gradients. Although, the problem has largely been overcome via carefully constructed initializations and batch normalization, architectures incorporating skip-connections such as highway and resnets perform much better than standard feedforward architectures despite well-chosen initialization and batch normalization. In this paper, we identify the shattered gradients problem. Specifically, we show that the correlation between gradients in standard feedforward networks decays exponentially with depth resulting in gradients that resemble white noise whereas, in contrast, the gradients in architectures with skip-connections are far more resistant to shattering, decaying sublinearly. Detailed empirical evidence is presented in support of the analysis, on both fully-connected networks and convnets. Finally, we present a new "looks linear" (LL) initialization that prevents shattering, with preliminary experiments showing the new initialization allows to train very deep networks without the addition of skip-connections.