OpenRaiser/Intern-Atlas huggingface dataset:
Minimizing Task Space Frechet Error via Efficient Incremental Graph Search
Venue: arXiv cs.RO 2018
Year: 2018

We present an anytime algorithm that generates a collision-free configuration-space path that closely follows a desired path in task space, according to the discrete Frechet distance. By leveraging tools from computational geometry, we approximate the search space using a cross-product graph. We use a variant of Dijkstra's graph-search algorithm to efficiently search for and iteratively improve the solution. We compare multiple proposed densification strategies and empirically show that our algorithm outperforms a set of state-of-the-art planners on a range of manipulation problems. Finally, we offer a proof sketch of the asymptotic optimality of our algorithm.
Graph Embedding with Rich Information through Heterogeneous Network
Venue: arXiv cs.AI 2018
Year: 2018

Graph embedding has attracted increasing attention due to its critical application in social network analysis. Most existing algorithms for graph embedding only rely on the typology information and fail to use the copious information in nodes as well as edges. As a result, their performance for many tasks may not be satisfactory. In this paper, we proposed a novel and general framework of representation learning for graph with rich text information through constructing a bipartite heterogeneous network. Specially, we designed a biased random walk to explore the constructed heterogeneous network with the notion of flexible neighborhood. The efficacy of our method is demonstrated by extensive comparison experiments with several baselines on various datasets. It improves the Micro-F1 and Macro-F1 of node classification by 10% and 7% on Cora dataset.
Interleaved Training and Training-Based Transmission Design for Hybrid Massive Antenna Downlink
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we study the beam-based training design jointly with the transmission design for hybrid massive antenna single-user (SU) and multiple-user (MU) systems where outage probability is adopted as the performance measure. For SU systems, we propose an interleaved training design to concatenate the feedback and training procedures, thus making the training length adaptive to the channel realization. Exact analytical expressions are derived for the average training length and the outage probability of the proposed interleaved training. For MU systems, we propose a joint design for the beam-based interleaved training, beam assignment, and MU data transmissions. Two solutions for the beam assignment are provided with different complexity-performance tradeoff. Analytical results and simulations show that for both SU and MU systems, the proposed joint training and transmission designs achieve the same outage performance as the traditional full-training scheme but with significant saving in the training overhead.
Protein Folding Optimization using Differential Evolution Extended with Local Search and Component Reinitialization
Venue: arXiv cs.AI 2018
Year: 2018

This paper presents a novel Differential Evolution algorithm for protein folding optimization that is applied to a three-dimensional AB off-lattice model. The proposed algorithm includes two new mechanisms. A local search is used to improve convergence speed and to reduce the runtime complexity of the energy calculation. For this purpose, a local movement is introduced within the local search. The designed evolutionary algorithm has fast convergence speed and, therefore, when it is trapped into the local optimum or a relatively good solution is located, it is hard to locate a better similar solution. The similar solution is different from the good solution in only a few components. A component reinitialization method is designed to mitigate this problem. Both the new mechanisms and the proposed algorithm were analyzed on well-known amino acid sequences that are used frequently in the literature. Experimental results show that the employed new mechanisms improve the efficiency of our algorithm and that the proposed algorithm is superior to other state-of-the-art algorithms. It obtained a hit ratio of 100% for sequences up to 18 monomers, within a budget of $10^{11}$ solution evaluations. New best-known solutions were obtained for most of the sequences. The existence of the symmetric best-known solutions is also demonstrated in the paper.
RRT* Combined with GVO for Real-time Nonholonomic Robot Navigation in Dynamic Environment
Venue: arXiv cs.RO 2018
Year: 2018

Challenges persist in nonholonomic robot navigation in dynamic environments. This paper presents a framework for such navigation based on the model of generalized velocity obstacles (GVO). The idea of velocity obstacles has been well studied and developed for obstacle avoidance since being proposed in 1998. Though it has been proved to be successful, most studies have assumed equations of motion to be linear, which limits their application to holonomic robots. In addition, more attention has been paid to the immediate reaction of robots, while advance planning has been neglected. By applying the GVO model to differential drive robots and by combining it with RRT*, we reduce the uncertainty of the robot trajectory, thus further reducing the range of concern, and save both computation time and running time. By introducing uncertainty for the dynamic obstacles with a Kalman filter, we dilute the risk of considering the obstacles as uniformly moving along a straight line and guarantee the safety. Special concern is given to path generation, including curvature check, making the generated path feasible for nonholonomic robots. We experimentally demonstrate the feasibility of the framework.
Scalable Gaussian Processes with Billions of Inducing Inputs via Tensor Train Decomposition
Venue: arXiv cs.LG 2018
Year: 2018

We propose a method (TT-GP) for approximate inference in Gaussian Process (GP) models. We build on previous scalable GP research including stochastic variational inference based on inducing inputs, kernel interpolation, and structure exploiting algebra. The key idea of our method is to use Tensor Train decomposition for variational parameters, which allows us to train GPs with billions of inducing inputs and achieve state-of-the-art results on several benchmarks. Further, our approach allows for training kernels based on deep neural networks without any modifications to the underlying GP model. A neural network learns a multidimensional embedding for the data, which is used by the GP to make the final prediction. We train GP and neural network parameters end-to-end without pretraining, through maximization of GP marginal likelihood. We show the efficiency of the proposed approach on several regression and classification benchmark datasets including MNIST, CIFAR-10, and Airline.
Superpixel Based Segmentation and Classification of Polyps in Wireless Capsule Endoscopy
Venue: arXiv cs.CV 2018
Year: 2018

Wireless Capsule Endoscopy (WCE) is a relatively new technology to record the entire GI trace, in vivo. The large amounts of frames captured during an examination cause difficulties for physicians to review all these frames. The need for reducing the reviewing time using some intelligent methods has been a challenge. Polyps are considered as growing tissues on the surface of intestinal tract not inside of an organ. Most polyps are not cancerous, but if one becomes larger than a centimeter, it can turn into cancer by great chance. The WCE frames provide the early stage possibility for detection of polyps. Here, the application of simple linear iterative clustering (SLIC) superpixel for segmentation of polyps in WCE frames is evaluated. Different SLIC superpixel numbers are examined to find the highest sensitivity for detection of polyps. The SLIC superpixel segmentation is promising to improve the results of previous studies. Finally, the superpixels were classified using a support vector machine (SVM) by extracting some texture and color features. The classification results showed a sensitivity of 91%.
A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics
Venue: arXiv cs.DS 2018
Year: 2018

We present a unified polynomial-time approximation scheme (PTAS) for the prize collecting traveling salesman problem (PCTSP) and the prize collecting Steiner tree problem (PCSTP) in doubling metrics. Given a metric space and a penalty function on a subset of points known as terminals, a solution is a subgraph on points in the metric space, whose cost is the weight of its edges plus the penalty due to terminals not covered by the subgraph. Under our unified framework, the solution subgraph needs to be Eulerian for PCTSP, while it needs to be connected for PCSTP. Before our work, even a QPTAS for the problems in doubling metrics is not known. Our unified PTAS is based on the previous dynamic programming frameworks proposed in [Talwar STOC 2004] and [Bartal, Gottlieb, Krauthgamer STOC 2012]. However, since it is unknown which part of the optimal cost is due to edge lengths and which part is due to penalties of uncovered terminals, we need to develop new techniques to apply previous divide-and-conquer strategies and sparse instance decompositions.
Image Disguise based on Generative Model
Venue: arXiv cs.CV 2018
Year: 2018

To protect image contents, most existing encryption algorithms are designed to transform an original image into a texture-like or noise-like image, which is, however, an obvious visual sign indicating the presence of an encrypted image, results in a significantly large number of attacks. To solve this problem, in this paper, we propose a new image encryption method to generate a visually same image as the original one by sending a meaning-normal and independent image to a corresponding well-trained generative model to achieve the effect of disguising the original image. This image disguise method not only solves the problem of obvious visual implication, but also guarantees the security of the information.
Feature-Guided Black-Box Safety Testing of Deep Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

Despite the improved accuracy of deep neural networks, the discovery of adversarial examples has raised serious safety concerns. Most existing approaches for crafting adversarial examples necessitate some knowledge (architecture, parameters, etc.) of the network at hand. In this paper, we focus on image classifiers and propose a feature-guided black-box approach to test the safety of deep neural networks that requires no such knowledge. Our algorithm employs object detection techniques such as SIFT (Scale Invariant Feature Transform) to extract features from an image. These features are converted into a mutable saliency distribution, where high probability is assigned to pixels that affect the composition of the image with respect to the human visual system. We formulate the crafting of adversarial examples as a two-player turn-based stochastic game, where the first player's objective is to minimise the distance to an adversarial example by manipulating the features, and the second player can be cooperative, adversarial, or random. We show that, theoretically, the two-player game can con- verge to the optimal strategy, and that the optimal strategy represents a globally minimal adversarial image. For Lipschitz networks, we also identify conditions that provide safety guarantees that no adversarial examples exist. Using Monte Carlo tree search we gradually explore the game state space to search for adversarial examples. Our experiments show that, despite the black-box setting, manipulations guided by a perception-based saliency distribution are competitive with state-of-the-art methods that rely on white-box saliency matrices or sophisticated optimization procedures. Finally, we show how our method can be used to evaluate robustness of neural networks in safety-critical applications such as traffic sign recognition in self-driving cars.
Moderate Environmental Variation Promotes the Evolution of Robust Solutions
Venue: arXiv cs.NE 2018
Year: 2018

Previous evolutionary studies demonstrated how evaluating evolving agents in variable environmental conditions enable them to develop solutions that are robust to environmental variation. We demonstrate how the robustness of the agents can be further improved by exposing them also to environmental variations throughout generations. These two types of environmental variations play partially distinct roles as demonstrated by the fact that agents evolved in environments that do not vary throughout generations display lower performance than agents evolved in varying environments independently from the amount of environmental variation experienced during evaluation. Moreover, our results demonstrate that performance increases when the amount of variations introduced during agents evaluation and the rate at which the environment varies throughout generations are moderate. This is explained by the fact that the probability to retain genetic variations, including non-neutral variations that alter the behavior of the agents, increases when the environment varies throughout generations but also when new environmental conditions persist over time long enough to enable genetic accommodation.
Experimental Biological Protocols with Formal Semantics
Venue: arXiv cs.PL 2018
Year: 2018

Both experimental and computational biology is becoming increasingly automated. Laboratory experiments are now performed automatically on high-throughput machinery, while computational models are synthesized or inferred automatically from data. However, integration between automated tasks in the process of biological discovery is still lacking, largely due to incompatible or missing formal representations. While theories are expressed formally as computational models, existing languages for encoding and automating experimental protocols often lack formal semantics. This makes it challenging to extract novel understanding by identifying when theory and experimental evidence disagree due to errors in the models or the protocols used to validate them. To address this, we formalize the syntax of a core protocol language, which provides a unified description for the models of biochemical systems being experimented on, together with the discrete events representing the liquid-handling steps of biological protocols. We present both a deterministic and a stochastic semantics to this language, both defined in terms of hybrid processes. In particular, the stochastic semantics captures uncertainties in equipment tolerances, making it a suitable tool for both experimental and computational biologists. We illustrate how the proposed protocol language can be used for automated verification and synthesis of laboratory experiments on case studies from the fields of chemistry and molecular programming.
Lightweight MPI Communicators with Applications to Perfectly Balanced Quicksort
Venue: arXiv cs.DC 2018
Year: 2018

MPI uses the concept of communicators to connect groups of processes. It provides nonblocking collective operations on communicators to overlap communication and computation. Flexible algorithms demand flexible communicators. E.g., a process can work on different subproblems within different process groups simultaneously, new process groups can be created, or the members of a process group can change. Depending on the number of communicators, the time for communicator creation can drastically increase the running time of the algorithm. Furthermore, a new communicator synchronizes all processes as communicator creation routines are blocking collective operations. We present RBC, a communication library based on MPI, that creates range-based communicators in constant time without communication. These RBC communicators support (non)blocking point-to-point communication as well as (non)blocking collective operations. Our experiments show that the library reduces the time to create a new communicator by a factor of more than 400 whereas the running time of collective operations remains about the same. We propose Janus Quicksort, a distributed sorting algorithm that avoids any load imbalances. We improved the performance of this algorithm by a factor of 15 for moderate inputs by using RBC communicators. Finally, we discuss different approaches to bring nonblocking (local) communicator creation of lightweight (range-based) communicators into MPI.
Full-Duplex Heterogeneous Networks with Decoupled User Association: Rate Analysis and Traffic Scheduling
Venue: arXiv cs.IT 2018
Year: 2018

Full-duplex (FD) transmission in a point-to-point (P2P) link, wherein bidirectional traffic flows simultaneously share the same spectrum, has the capability of doubling the link rate by completely removing self-interferences. However, the rate gain of FD transmission in an interference-limited network is not as clear as a P2P link due to the interferences induced by complex FD and half-duplex (HD) transmission behaviors in the network. To thoroughly investigate the achievable link rates of users and base stations (BSs) in a heterogeneous network (HetNet) with decoupled user association, a general approach is proposed to model a HetNet in which all BSs and users can perform HD or FD transmission depending on their traffic patterns. We first characterize the decoupled rate-optimal user association scheme and use it to define the downlink and uplink rates in the HetNet. The tight lower bounds on the link rates of the FD users and BSs are found in a neat form that characterizes general channel fading, user and BS intensities and imperfect self-interference cancellation. These bounds outline the rate regions of the FD users that inspire proposing the opportunistic FD scheduling algorithms maximizing the sum rate of each bidirectional traffic and stabilize each of the queues in the HetNet.
Higher-Order Program Verification via HFL Model Checking
Venue: arXiv cs.PL 2018
Year: 2018

There are two kinds of higher-order extensions of model checking: HORS model checking and HFL model checking. Whilst the former has been applied to automated verification of higher-order functional programs, applications of the latter have not been well studied. In the present paper, we show that various verification problems for functional programs, including may/must-reachability, trace properties, and linear-time temporal properties (and their negations), can be naturally reduced to (extended) HFL model checking. The reductions yield a sound and complete logical characterization of those program properties. Compared with the previous approaches based on HORS model checking, our approach provides a more uniform, streamlined method for higher-order program verification.
Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection (Technical Report)
Venue: arXiv cs.FL 2018
Year: 2018

We consider the problem of approximate reduction of non-deterministic automata that appear in hardware-accelerated network intrusion detection systems (NIDSes). We define an error distance of a reduced automaton from the original one as the probability of packets being incorrectly classified by the reduced automaton (wrt the probabilistic distribution of packets in the network traffic). We use this notion to design an approximate reduction procedure that achieves a great size reduction (much beyond the state-of-the-art language-preserving techniques) with a controlled and small error. We have implemented our approach and evaluated it on use cases from Snort, a popular NIDS. Our results provide experimental evidence that the method can be highly efficient in practice, allowing NIDSes to follow the rapid growth in the speed of networks.
Linear State Estimation via 5G C-RAN Cellular Networks using Gaussian Belief Propagation
Venue: arXiv cs.IT 2018
Year: 2018

Machine-type communications and large-scale information processing architectures are among key (r)evolutionary enhancements of emerging fifth-generation (5G) mobile cellular networks. Massive data acquisition and processing will make 5G network an ideal platform for large-scale system monitoring and control with applications in future smart transportation, connected industry, power grids, etc. In this work, we investigate a capability of such a 5G network architecture to provide the state estimate of an underlying linear system from the input obtained via large-scale deployment of measurement devices. Assuming that the measurements are communicated via densely deployed cloud radio access network (C-RAN), we formulate and solve the problem of estimating the system state from the set of signals collected at C-RAN base stations. Our solution, based on the Gaussian Belief-Propagation (GBP) framework, allows for large-scale and distributed deployment within the emerging 5G information processing architectures. The presented numerical study demonstrates the accuracy, convergence behavior and scalability of the proposed GBP-based solution to the large-scale state estimation problem.
What is the Connection Between Issues, Bugs, and Enhancements? (Lessons Learned from 800+ Software Projects)
Venue: arXiv cs.SE 2018
Year: 2018

Agile teams juggle multiple tasks so professionals are often assigned to multiple projects, especially in service organizations that monitor and maintain a large suite of software for a large user base. If we could predict changes in project conditions changes, then managers could better adjust the staff allocated to those projects.This paper builds such a predictor using data from 832 open source and proprietary applications. Using a time series analysis of the last 4 months of issues, we can forecast how many bug reports and enhancement requests will be generated next month. The forecasts made in this way only require a frequency count of this issue reports (and do not require an historical record of bugs found in the project). That is, this kind of predictive model is very easy to deploy within a project. We hence strongly recommend this method for forecasting future issues, enhancements, and bugs in a project.
Complexity of locally-injective homomorphisms to tournaments
Venue: arXiv cs.DM 2018
Year: 2018

For oriented graphs $G$ and $H$, a homomorphism $f: G \rightarrow H$ is locally-injective if, for every $v \in V(G)$, it is injective when restricted to some combination of the in-neighbourhood and out-neighbourhood of $v$. Two of the possible definitions of local-injectivity are examined. In each case it is shown that the associated homomorphism problem is NP-complete when $H$ is a reflexive tournament on three or more vertices with a loop at every vertex, and solvable in polynomial time when $H$ is a reflexive tournament on two or fewer vertices.
Distortion-free Golden-Hadamard Codebook Design for MISO Systems
Venue: arXiv cs.IT 2018
Year: 2018

In this letter, a novel Golden-Hadamard codebook (GHC) scheme is proposed to improve the performance of the traditional precoded Alamouti coding for multiple-input and single-output systems. Although the traditional discrete Fourier transform codebook (DFTC) performs satisfactorily with Alamouti coding and offers numerous benefits for the Rayleigh fading channel, this scheme inherently generates huge codeword distortion, which leads to a lower minimum chordal distance (MCD). Furthermore, the uncertain format of all prior versions of codebooks results in poorer minimum determinant (MD) values. Hence, the proposed GHC scheme successfully deals with the issues of traditional DFTC to achieve a better codebook format that completely overcome both MCD and MD problems. The effectiveness of the proposed GHC scheme is confirmed, in terms of bit-error-rate through Monte Carlo simulations.