OpenRaiser/Intern-Atlas huggingface dataset:
Persistent AUV Operations Using a Robust Reactive Mission and Path Planning (RRMPP) Architecture
Venue: arXiv cs.RO 2019
Year: 2019

Providing a higher level of decision autonomy and accompanying prompt changes of an uncertain environment is a true challenge of AUVs autonomous operations. The proceeding approach introduces a robust reactive structure that accommodates an AUV's mission planning, task-time management in a top level and incorporates environmental changes by a synchronic motion planning in a lower level. The proposed architecture is developed in a hierarchal modular format and a bunch of evolutionary algorithms are employed by each module to investigate the efficiency and robustness of the structure in different mission scenarios while water current data, uncertain static-mobile/motile obstacles, and vehicles Kino-dynamic constraints are taken into account. The motion planner is facilitated with online re-planning capability to refine the vehicle's trajectory based on local variations of the environment. A small computational load is devoted for re-planning procedure since the upper layer mission planner renders an efficient overview of the operation area that AUV should fly thru. Numerical simulations are carried out to investigate robustness and performance of the architecture in different situations of a real-world underwater environment. Analysis of the simulation results claims the remarkable capability of the proposed model in accurate mission task-time-threat management while guarantying a secure deployment during the mission.
Neural Recovery Machine for Chinese Dropped Pronoun
Venue: arXiv cs.CL 2019
Year: 2019

Dropped pronouns (DPs) are ubiquitous in pro-drop languages like Chinese, Japanese etc. Previous work mainly focused on painstakingly exploring the empirical features for DPs recovery. In this paper, we propose a neural recovery machine (NRM) to model and recover DPs in Chinese, so that to avoid the non-trivial feature engineering process. The experimental results show that the proposed NRM significantly outperforms the state-of-the-art approaches on both two heterogeneous datasets. Further experiment results of Chinese zero pronoun (ZP) resolution show that the performance of ZP resolution can also be improved by recovering the ZPs to DPs.
Locally Weighted Ensemble Clustering
Venue: arXiv cs.LG 2019
Year: 2019

Due to its ability to combine multiple base clusterings into a probably better and more robust clustering, the ensemble clustering technique has been attracting increasing attention in recent years. Despite the significant success, one limitation to most of the existing ensemble clustering methods is that they generally treat all base clusterings equally regardless of their reliability, which makes them vulnerable to low-quality base clusterings. Although some efforts have been made to (globally) evaluate and weight the base clusterings, yet these methods tend to view each base clustering as an individual and neglect the local diversity of clusters inside the same base clustering. It remains an open problem how to evaluate the reliability of clusters and exploit the local diversity in the ensemble to enhance the consensus performance, especially in the case when there is no access to data features or specific assumptions on data distribution. To address this, in this paper, we propose a novel ensemble clustering approach based on ensemble-driven cluster uncertainty estimation and local weighting strategy. In particular, the uncertainty of each cluster is estimated by considering the cluster labels in the entire ensemble via an entropic criterion. A novel ensemble-driven cluster validity measure is introduced, and a locally weighted co-association matrix is presented to serve as a summary for the ensemble of diverse clusters. With the local diversity in ensembles exploited, two novel consensus functions are further proposed. Extensive experiments on a variety of real-world datasets demonstrate the superiority of the proposed approach over the state-of-the-art.
Keeping Your Distance is Hard
Venue: arXiv cs.CC 2019
Year: 2019

We study the computational complexity of distance games, a class of combinatorial games played on graphs. A move consists of colouring an uncoloured vertex subject to it not being at certain distances determined by two sets, D and S. D is the set of forbidden distances for colouring vertices in different colors, while S is the set of forbidden distances for the same colour. The last player to move wins. Well-known examples of distance games are Node-Kayles, Snort, and Col, whose complexities were shown to be PSPACE-hard. We show that many more distance games are also PSPACE-hard.
Optimal Sparsification for Some Binary CSPs Using Low-degree Polynomials
Venue: arXiv cs.CC 2019
Year: 2019

This paper analyzes to what extent it is possible to efficiently reduce the number of clauses in NP-hard satisfiability problems, without changing the answer. Upper and lower bounds are established using the concept of kernelization. Existing results show that if NP is not contained in coNP/poly, no efficient preprocessing algorithm can reduce n-variable instances of CNF-SAT with d literals per clause, to equivalent instances with $O(n^{d-e})$ bits for any e > 0. For the Not-All-Equal SAT problem, a compression to size $Õ(n^{d-1})$ exists. We put these results in a common framework by analyzing the compressibility of binary CSPs. We characterize constraint types based on the minimum degree of multivariate polynomials whose roots correspond to the satisfying assignments, obtaining (nearly) matching upper and lower bounds in several settings. Our lower bounds show that not just the number of constraints, but also the encoding size of individual constraints plays an important role. For example, for Exact Satisfiability with unbounded clause length it is possible to efficiently reduce the number of constraints to n+1, yet no polynomial-time algorithm can reduce to an equivalent instance with $O(n^{2-e})$ bits for any e > 0, unless NP is a subset of coNP/poly.
Online Stochastic Matching: New Algorithms and Bounds
Venue: arXiv cs.DS 2019
Year: 2019

Online matching has received significant attention over the last 15 years due to its close connection to Internet advertising. As the seminal work of Karp, Vazirani, and Vazirani has an optimal (1 - 1/e) competitive ratio in the standard adversarial online model, much effort has gone into developing useful online models that incorporate some stochasticity in the arrival process. One such popular model is the "known I.I.D. model" where different customer-types arrive online from a known distribution. We develop algorithms with improved competitive ratios for some basic variants of this model with integral arrival rates, including (a) the case of general weighted edges, where we improve the best-known ratio of 0.667 due to Haeupler, Mirrokni and Zadimoghaddam to 0.705; and (b) the vertex-weighted case, where we improve the 0.7250 ratio of Jaillet and Lu to 0.7299. We also consider an extension of stochastic rewards, a variant where each edge has an independent probability of being present. For the setting of stochastic rewards with non-integral arrival rates, we present a simple optimal non-adaptive algorithm with a ratio of 1 - 1/e. For the special case where each edge is unweighted and has a uniform constant probability of being present, we improve upon 1 - 1/e by proposing a strengthened LP benchmark.
Multi-View Kernel Consensus For Data Analysis
Venue: arXiv cs.LG 2019
Year: 2019

The input data features set for many data driven tasks is high-dimensional while the intrinsic dimension of the data is low. Data analysis methods aim to uncover the underlying low dimensional structure imposed by the low dimensional hidden parameters by utilizing distance metrics that consider the set of attributes as a single monolithic set. However, the transformation of the low dimensional phenomena into the measured high dimensional observations might distort the distance metric, This distortion can effect the desired estimated low dimensional geometric structure. In this paper, we suggest to utilize the redundancy in the attribute domain by partitioning the attributes into multiple subsets we call views. The proposed methods utilize the agreement also called consensus between different views to extract valuable geometric information that unifies multiple views about the intrinsic relationships among several different observations. This unification enhances the information that a single view or a simple concatenations of views provides.
Eliminating Depth Cycles among Triangles in Three Dimensions
Venue: arXiv cs.CG 2019
Year: 2019

Given $n$ pairwise openly disjoint triangles in 3-space, their vertical depth relation may contain cycles. We show that, for any $\varepsilon>0$, the triangles can be cut into $O(n^{3/2+\varepsilon})$ connected semi-algebraic pieces, whose description complexity depends only on the choice of $\varepsilon$, such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. We are not aware of any previous study of this problem, in this full generality, with a subquadratic bound on the number of pieces. This work extends the recent study by two of the authors (Aronov, Sharir~2018) on eliminating depth cycles among lines in 3-space. Our approach is again algebraic, and makes use of a recent variant of the polynomial partitioning technique, due to Guth, which leads to a recursive procedure for cutting the triangles. In contrast to the case of lines, our analysis here is considerably more involved, due to the two-dimensional nature of the objects being cut, so additional tools, from topology and algebra, need to be brought to bear. Our result essentially settles a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.
Robust Control for Signal Temporal Logic Specifications using Average Space Robustness
Venue: arXiv cs.SY 2019
Year: 2019

Control systems that satisfy temporal logic specifications have become increasingly popular due to their applicability to robotic systems. Existing control methods, however, are computationally demanding, especially when the problem size becomes too large. In this paper, a robust and computationally efficient model predictive control framework for signal temporal logic specifications is proposed. We introduce discrete average space robustness, a novel quantitative semantic for signal temporal logic, that is directly incorporated into the cost function of the model predictive controller. The optimization problem entailed in this framework can be written as a convex quadratic program when no disjunctions are considered and results in a robust satisfaction of the specification. Furthermore, we define the predicate robustness degree as a new robustness notion. Simulations of a multi-agent system subject to complex specifications demonstrate the efficacy of the proposed method.
Revenue Gaps for Static and Dynamic Posted Pricing of Homogeneous Goods
Venue: arXiv cs.GT 2019
Year: 2019

We consider the problem of maximizing the expected revenue from selling $k$ homogeneous goods to $n$ unit-demand buyers who arrive sequentially with independent and identically distributed valuations. In this setting the optimal posted prices are dynamic in the sense that they depend on the remaining numbers of goods and buyers. We investigate how much revenue is lost when a single static price is used instead for all buyers and goods, and prove upper bounds on the ratio between the maximum revenue from dynamic prices and that from static prices. These bounds are tight for all values of $k$ and $n$ and vary depending on a regularity property of the underlying distribution. For general distributions we obtain a ratio of $2-k/n$, for regular distributions a ratio that increases in $n$ and is bounded from above by $1/(1-k^k/(e^{k}k!))$, which is roughly $1/(1-1/(\sqrt{2πk}))$. The lower bounds hold for the revenue gap between dynamic and static prices. The upper bounds are obtained via an ex-ante relaxation of the revenue maximization problem, as a consequence the tight bounds of $2-k/n$ in the general case and of $1/(1-1/(\sqrt{2πk}))$ in the regular case apply also to the potentially larger revenue gap between the optimal incentive-compatible mechanism and the optimal static price. Our results imply that for regular distributions the benefit of dynamic prices vanishes while for non-regular distributions dynamic prices may achieve up to twice the revenue of static prices.
ARMv8 Shellcodes from 'A' to 'Z'
Venue: arXiv cs.CR 2019
Year: 2019

We describe a methodology to automatically turn arbitrary ARMv8 programs into alphanumeric executable polymorphic shellcodes. Shellcodes generated in this way can evade detection and bypass filters, broadening the attack surface of ARM-powered devices such as smartphones.
A Comparative Study for the Nuclear Norms Minimization Methods
Venue: arXiv cs.CV 2019
Year: 2019

The nuclear norm minimization (NNM) is commonly used to approximate the matrix rank by shrinking all singular values equally. However, the singular values have clear physical meanings in many practical problems, and NNM may not be able to faithfully approximate the matrix rank. To alleviate the above-mentioned limitation of NNM, recent studies have suggested that the weighted nuclear norm minimization (WNNM) can achieve a better rank estimation than NNM, which heuristically set the weight being inverse to the singular values. However, it still lacks a rigorous explanation why WNNM is more effective than NMM in various applications. In this paper, we analyze NNM and WNNM from the perspective of group sparse representation (GSR). Concretely, an adaptive dictionary learning method is devised to connect the rank minimization and GSR models. Based on the proposed dictionary, we prove that NNM and WNNM are equivalent to L1-norm minimization and the weighted L1-norm minimization in GSR, respectively. Inspired by enhancing sparsity of the weighted L1-norm minimization in comparison with L1-norm minimization in sparse representation, we thus explain that WNNM is more effective than NMM. By integrating the image nonlocal self-similarity (NSS) prior with the WNNM model, we then apply it to solve the image denoising problem. Experimental results demonstrate that WNNM is more effective than NNM and outperforms several state-of-the-art methods in both objective and perceptual quality.
A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
Venue: arXiv cs.SI 2019
Year: 2019

Multilayer networks allow one to represent diverse and coupled connectivity patterns --- e.g., time-dependence, multiple subsystems, or both --- that arise in many applications and which are difficult or awkward to incorporate into standard network representations. In the study of multilayer networks, it is important to investigate mesoscale (i.e., intermediate-scale) structures, such as dense sets of nodes known as communities, to discover network features that are not apparent at the microscale or the macroscale. The ill-defined nature of mesoscale structure and its ubiquity in empirical networks make it crucial to develop generative models that can produce the features that one encounters in empirical networks. Key purposes of such generative models include generating synthetic networks with empirical properties of interest, benchmarking mesoscale-detection methods and algorithms, and inferring structure in empirical multilayer networks. In this paper, we introduce a framework for the construction of generative models for mesoscale structures in multilayer networks. Our framework provides a standardized set of generative models, together with an associated set of principles from which they are derived, for studies of mesoscale structures in multilayer networks. It unifies and generalizes many existing models for mesoscale structures in fully-ordered (e.g., temporal) and unordered (e.g., multiplex) multilayer networks. One can also use it to construct generative models for mesoscale structures in partially-ordered multilayer networks (e.g., networks that are both temporal and multiplex). Our framework has the ability to produce many features of empirical multilayer networks, and it explicitly incorporates a user-specified dependency structure between layers.
Designing Workflow Systems Using Building Blocks
Venue: arXiv cs.SE 2019
Year: 2019

We suggest there is a need for a fresh perspective on the design and development of workflow systems and argue for a building blocks approach. We outline a description of this approach and define the properties of software building blocks. We discuss RADICAL-Cybertools as one implementation of the building blocks concept, showing how they have been designed and developed in accordance with this approach. Four case studies are presented, covering a dozen science problems. We discuss how RADICAL-Cybertools have been used to develop new workflow systems capabilities and integrated to enhance existing ones, illustrating the applicability and potential of software building blocks. In doing so, we have begun an investigation of an alternative approach to thinking about the design and implementation of workflow systems.
SegMatch: Segment based loop-closure for 3D point clouds
Venue: arXiv cs.RO 2019
Year: 2019

Loop-closure detection on 3D data is a challenging task that has been commonly approached by adapting image-based solutions. Methods based on local features suffer from ambiguity and from robustness to environment changes while methods based on global features are viewpoint dependent. We propose SegMatch, a reliable loop-closure detection algorithm based on the matching of 3D segments. Segments provide a good compromise between local and global descriptions, incorporating their strengths while reducing their individual drawbacks. SegMatch does not rely on assumptions of "perfect segmentation", or on the existence of "objects" in the environment, which allows for reliable execution on large scale, unstructured environments. We quantitatively demonstrate that SegMatch can achieve accurate localization at a frequency of 1Hz on the largest sequence of the KITTI odometry dataset. We furthermore show how this algorithm can reliably detect and close loops in real-time, during online operation. In addition, the source code for the SegMatch algorithm will be made available after publication.
Hierarchical Multistage Gaussian Signaling Games in Noncooperative Communication and Control Systems
Venue: arXiv cs.GT 2019
Year: 2019

We analyze in this paper finite horizon hierarchical signaling games between (information provider) senders and (decision maker) receivers in a dynamic environment. The underlying information evolves in time while sender and receiver interact repeatedly. Different from the classical communication (control) models, however, the sender (sensor) and the receiver (controller) have different objectives and there is a hierarchy between the players such that the sender leads the game by announcing his policies beforehand. He needs to anticipate the reaction of the receiver and the impact of the actions on the horizon while controlling the transparency of the disclosed information at each interaction. With quadratic cost functions and multivariate Gaussian processes, evolving according to first order auto-regressive models, we show that memoryless "linear" sender signaling rules are optimal (in the sense of game-theoretic hierarchical equilibrium) within the general class of measurable policies in the noncooperative communication context. In the noncooperative control context, we also analyze the hierarchical equilibrium for linear signaling rules and provide an algorithm to compute the optimal linear signaling rules numerically with global optimality guarantees.
Deep Convolutional Networks as Models of Generalization and Blending Within Visual Creativity
Venue: arXiv cs.NE 2019
Year: 2019

We examine two recent artificial intelligence (AI) based deep learning algorithms for visual blending in convolutional neural networks (Mordvintsev et al. 2015, Gatys et al. 2015). To investigate the potential value of these algorithms as tools for computational creativity research, we explain and schematize the essential aspects of the algorithms' operation and give visual examples of their output. We discuss the relationship of the two algorithms to human cognitive science theories of creativity such as conceptual blending theory and honing theory, and characterize the algorithms with respect to generation of novelty and aesthetic quality.
Efficient Random Sampling -- Parallel, Vectorized, Cache-Efficient, and Online
Venue: arXiv cs.DS 2019
Year: 2019

We consider the problem of sampling $n$ numbers from the range $\{1,\ldots,N\}$ without replacement on modern architectures. The main result is a simple divide-and-conquer scheme that makes sequential algorithms more cache efficient and leads to a parallel algorithm running in expected time $\mathcal{O}(n/p+\log p)$ on $p$ processors, i.e., scales to massively parallel machines even for moderate values of $n$. The amount of communication between the processors is very small (at most $\mathcal{O}(\log p)$) and independent of the sample size. We also discuss modifications needed for load balancing, online sampling, sampling with replacement, Bernoulli sampling, and vectorization on SIMD units or GPUs.
A Projective Simulation Scheme for Partially-Observable Multi-Agent Systems
Venue: arXiv cs.AI 2019
Year: 2019

We introduce a kind of partial observability to the projective simulation (PS) learning method. It is done by adding a belief projection operator and an observability parameter to the original framework of the efficiency of the PS model. I provide theoretical formulations, network representations, and situated scenarios derived from the invasion toy problem as a starting point for some multi-agent PS models.
Multi-view Generative Adversarial Networks
Venue: arXiv cs.LG 2019
Year: 2019

Learning over multi-view data is a challenging problem with strong practical applications. Most related studies focus on the classification point of view and assume that all the views are available at any time. We consider an extension of this framework in two directions. First, based on the BiGAN model, the Multi-view BiGAN (MV-BiGAN) is able to perform density estimation from multi-view inputs. Second, it can deal with missing views and is able to update its prediction when additional views are provided. We illustrate these properties on a set of experiments over different datasets.
The Non-convex Geometry of Low-rank Matrix Optimization
Venue: arXiv cs.IT 2019
Year: 2019

This work considers two popular minimization problems: (i) the minimization of a general convex function $f(\mathbf{X})$ with the domain being positive semi-definite matrices; (ii) the minimization of a general convex function $f(\mathbf{X})$ regularized by the matrix nuclear norm $\|\mathbf{X}\|_*$ with the domain being general matrices. Despite their optimal statistical performance in the literature, these two optimization problems have a high computational complexity even when solved using tailored fast convex solvers. To develop faster and more scalable algorithms, we follow the proposal of Burer and Monteiro to factor the low-rank variable $\mathbf{X} = \mathbf{U}\mathbf{U}^\top $ (for semi-definite matrices) or $\mathbf{X}=\mathbf{U}\mathbf{V}^\top $ (for general matrices) and also replace the nuclear norm $\|\mathbf{X}\|_*$ with $(\|\mathbf{U}\|_F^2+\|\mathbf{V}\|_F^2)/2$. In spite of the non-convexity of the resulting factored formulations, we prove that each critical point either corresponds to the global optimum of the original convex problems or is a strict saddle where the Hessian matrix has a strictly negative eigenvalue. Such a nice geometric structure of the factored formulations allows many local search algorithms to find a global optimizer even with random initializations.