OpenRaiser/Intern-Atlas huggingface dataset:
Aligned Drawings of Planar Graphs
Venue: arXiv cs.DS 2018
Year: 2018

Let $G$ be a graph that is topologically embedded in the plane and let $\mathcal{A}$ be an arrangement of pseudolines intersecting the drawing of $G$. An aligned drawing of $G$ and $\mathcal{A}$ is a planar polyline drawing $Γ$ of $G$ with an arrangement $A$ of lines so that $Γ$ and $A$ are homeomorphic to $G$ and $\mathcal{A}$. We show that if $\mathcal{A}$ is stretchable and every edge $e$ either entirely lies on a pseudoline or it has at most one intersection with $\mathcal{A}$, then $G$ and $\mathcal{A}$ have a straight-line aligned drawing. In order to prove this result, we strengthen a result of Da Lozzo et al., and prove that a planar graph $G$ and a single pseudoline $\mathcal{L}$ have an aligned drawing with a prescribed convex drawing of the outer face. We also study the less restrictive version of the alignment problem with respect to one line, where only a set of vertices is given and we need to determine whether they can be collinear. We show that the problem is NP-complete but fixed-parameter tractable.
An O(log log m)-competitive Algorithm for Online Machine Minimization
Venue: arXiv cs.DS 2018
Year: 2018

This paper considers the online machine minimization problem, a basic real time scheduling problem. The setting for this problem consists of n jobs that arrive over time, where each job has a deadline by which it must be completed. The goal is to design an online scheduler that feasibly schedules the jobs on a nearly minimal number of machines. An algorithm is c-machine optimal if the algorithm will feasibly schedule a collection of jobs on cm machines if there exists a feasible schedule on m machines. For over two decades the best known result was a O(log P)-machine optimal algorithm, where P is the ratio of the maximum to minimum job size. In a recent breakthrough, a O(log m)-machine optimal algorithm was given. In this paper, we exponentially improve on this recent result by giving a O(log log m)-machine optimal algorithm.
Improved ArtGAN for Conditional Synthesis of Natural Image and Artwork
Venue: arXiv cs.CV 2018
Year: 2018

This paper proposes a series of new approaches to improve Generative Adversarial Network (GAN) for conditional image synthesis and we name the proposed model as ArtGAN. One of the key innovation of ArtGAN is that, the gradient of the loss function w.r.t. the label (randomly assigned to each generated image) is back-propagated from the categorical discriminator to the generator. With the feedback from the label information, the generator is able to learn more efficiently and generate image with better quality. Inspired by recent works, an autoencoder is incorporated into the categorical discriminator for additional complementary information. Last but not least, we introduce a novel strategy to improve the image quality. In the experiments, we evaluate ArtGAN on CIFAR-10 and STL-10 via ablation studies. The empirical results showed that our proposed model outperforms the state-of-the-art results on CIFAR-10 in terms of Inception score. Qualitatively, we demonstrate that ArtGAN is able to generate plausible-looking images on Oxford-102 and CUB-200, as well as able to draw realistic artworks based on style, artist, and genre. The source code and models are available at: https://github.com/cs-chan/ArtGAN
Isogeometric analysis of thin Reissner-Mindlin plates and shells: locking phenomena and B-bar method
Venue: arXiv cs.CE 2018
Year: 2018

We propose a local type of B-bar formulation, addressing locking in degenerated Reissner-Mindlin plate and shell formulations in the context of isogeometric analysis. Parasitic strain components are projected onto the physical space locally, i.e. at the element level, using a least-squares approach. The formulation allows the flexible utilization of basis functions of different order as the projection bases. The present formulation is much cheaper computationally than the classical $\bar{B}$ method. We show the numerical consistency of the scheme through numerical examples, moreover they show that the proposed formulation alleviates locking and yields good accuracy even for slenderness ratios of $1 \times 10^5$, and has the ability to capture deformations of thin shells using relatively coarse meshes. In addition it can be opined that the proposed method is less sensitive to locking and mesh distortion.
Ultra-Reliable Low Latency Cellular Networks: Use Cases, Challenges and Approaches
Venue: arXiv cs.IT 2018
Year: 2018

The fifth-generation cellular mobile networks are expected to support mission critical ultra-reliable low latency communication (URLLC) services in addition to the enhanced mobile broadband applications. This article first introduces three emerging mission critical applications of URLLC and identifies their requirements on end-to-end latency and reliability. We then investigate the various sources of end-to-end delay of current wireless networks by taking the 4G Long Term Evolution (LTE) as an example. Subsequently, we propose and evaluate several techniques to reduce the end-to-end latency from the perspectives of error control coding, signal processing, and radio resource management. We also briefly discuss other network design approaches with the potential for further latency reduction.
Extrinsic Parameter Calibration for Line Scanning Cameras on Ground Vehicles with Navigation Systems Using a Calibration Pattern
Venue: arXiv cs.RO 2018
Year: 2018

Line scanning cameras, which capture only a single line of pixels, have been increasingly used in ground based mobile or robotic platforms. In applications where it is advantageous to directly georeference the camera data to world coordinates, an accurate estimate of the camera's 6D pose is required. This paper focuses on the common case where a mobile platform is equipped with a rigidly mounted line scanning camera, whose pose is unknown, and a navigation system providing vehicle body pose estimates. We propose a novel method that estimates the camera's pose relative to the navigation system. The approach involves imaging and manually labelling a calibration pattern with distinctly identifiable points, triangulating these points from camera and navigation system data and reprojecting them in order to compute a likelihood, which is maximised to estimate the 6D camera pose. Additionally, a Markov Chain Monte Carlo (MCMC) algorithm is used to estimate the uncertainty of the offset. Tested on two different platforms, the method was able to estimate the pose to within 0.06 m / 1.05$^{\circ}$ and 0.18 m / 2.39$^{\circ}$. We also propose several approaches to displaying and interpreting the 6D results in a human readable way.
Dataset Augmentation with Synthetic Images Improves Semantic Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Although Deep Convolutional Neural Networks trained with strong pixel-level annotations have significantly pushed the performance in semantic segmentation, annotation efforts required for the creation of training data remains a roadblock for further improvements. We show that augmentation of the weakly annotated training dataset with synthetic images minimizes both the annotation efforts and also the cost of capturing images with sufficient variety. Evaluation on the PASCAL 2012 validation dataset shows an increase in mean IOU from 52.80% to 55.47% by adding just 100 synthetic images per object class. Our approach is thus a promising solution to the problems of annotation and dataset collection.
A Probabilistic Peeling Decoder to Efficiently Analyze Generalized LDPC Codes Over the BEC
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we analyze the tradeoff between coding rate and asymptotic performance of a class of generalized low-density parity-check (GLDPC) codes constructed by including a certain fraction of generalized constraint (GC) nodes in the graph. The rate of the GLDPC ensemble is bounded using classical results on linear block codes, namely Hamming bound and Varshamov bound. We also study the impact of the decoding method used at GC nodes. To incorporate both bounded-distance (BD) and Maximum Likelihood (ML) decoding at GC nodes into our analysis without resorting on multi-edge type of degree distributions (DDs), we propose the probabilistic peeling decoding (P-PD) algorithm, which models the decoding step at every GC node as an instance of a Bernoulli random variable with a successful decoding probability that depends on both the GC block code as well as its decoding algorithm. The P-PD asymptotic performance over the BEC can be efficiently predicted using standard techniques for LDPC codes such as density evolution (DE) or the differential equation method. Furthermore, for a class of GLDPC ensembles, we demonstrate that the simulated P-PD performance accurately predicts the actual performance of the GLPDC code under ML decoding at GC nodes. We illustrate our analysis for GLDPC code ensembles with regular and irregular DDs. In all cases, we show that a large fraction of GC nodes is required to reduce the original gap to capacity, but the optimal fraction is strictly smaller than one. We then consider techniques to further reduce the gap to capacity by means of random puncturing, and the inclusion of a certain fraction of generalized variable nodes in the graph.
Pairing heaps: the forward variant
Venue: arXiv cs.DS 2018
Year: 2018

The pairing heap is a classical heap data structure introduced in 1986 by Fredman, Sedgewick, Sleator, and Tarjan. It is remarkable both for its simplicity and for its excellent performance in practice. The "magic" of pairing heaps lies in the restructuring that happens after the deletion of the smallest item. The resulting collection of trees is consolidated in two rounds: a left-to-right pairing round, followed by a right-to-left accumulation round. Fredman et al. showed, via an elegant correspondence to splay trees, that in a pairing heap of size $n$ all operations take $O(\log{n})$ amortized time. They also proposed an arguably more natural variant, where both pairing and accumulation are performed in a combined left-to-right round (called the forward variant of pairing heaps). The analogy to splaying breaks down in this case, and the analysis of the forward variant was left open. In this paper we show that inserting an item and deleting the minimum in a forward-variant pairing heap both take amortized time $O(\log{n} \cdot 4^{\sqrt{\log{n}}} )$. This is the first improvement over the $O(\sqrt{n})$ bound showed by Fredman et al. three decades ago. Our analysis relies on a new potential function that tracks parent-child rank-differences in the heap.
Sequence Prediction with Neural Segmental Models
Venue: arXiv cs.CL 2018
Year: 2018

Segments that span contiguous parts of inputs, such as phonemes in speech, named entities in sentences, actions in videos, occur frequently in sequence prediction problems. Segmental models, a class of models that explicitly hypothesizes segments, have allowed the exploration of rich segment features for sequence prediction. However, segmental models suffer from slow decoding, hampering the use of computationally expensive features. In this thesis, we introduce discriminative segmental cascades, a multi-pass inference framework that allows us to improve accuracy by adding higher-order features and neural segmental features while maintaining efficiency. We also show that instead of including more features to obtain better accuracy, segmental cascades can be used to speed up training and decoding. Segmental models, similarly to conventional speech recognizers, are typically trained in multiple stages. In the first stage, a frame classifier is trained with manual alignments, and then in the second stage, segmental models are trained with manual alignments and the out- puts of the frame classifier. However, obtaining manual alignments are time-consuming and expensive. We explore end-to-end training for segmental models with various loss functions, and show how end-to-end training with marginal log loss can eliminate the need for detailed manual alignments. We draw the connections between the marginal log loss and a popular end-to-end training approach called connectionist temporal classification. We present a unifying framework for various end-to-end graph search-based models, such as hidden Markov models, connectionist temporal classification, and segmental models. Finally, we discuss possible extensions of segmental models to large-vocabulary sequence prediction tasks.
Probabilistic Rule Realization and Selection
Venue: arXiv cs.LG 2018
Year: 2018

Abstraction and realization are bilateral processes that are key in deriving intelligence and creativity. In many domains, the two processes are approached through rules: high-level principles that reveal invariances within similar yet diverse examples. Under a probabilistic setting for discrete input spaces, we focus on the rule realization problem which generates input sample distributions that follow the given rules. More ambitiously, we go beyond a mechanical realization that takes whatever is given, but instead ask for proactively selecting reasonable rules to realize. This goal is demanding in practice, since the initial rule set may not always be consistent and thus intelligent compromises are needed. We formulate both rule realization and selection as two strongly connected components within a single and symmetric bi-convex problem, and derive an efficient algorithm that works at large scale. Taking music compositional rules as the main example throughout the paper, we demonstrate our model's efficiency in not only music realization (composition) but also music interpretation and understanding (analysis).
Deep Packet: A Novel Approach For Encrypted Traffic Classification Using Deep Learning
Venue: arXiv cs.LG 2018
Year: 2018

Internet traffic classification has become more important with rapid growth of current Internet network and online applications. There have been numerous studies on this topic which have led to many different approaches. Most of these approaches use predefined features extracted by an expert in order to classify network traffic. In contrast, in this study, we propose a \emph{deep learning} based approach which integrates both feature extraction and classification phases into one system. Our proposed scheme, called "Deep Packet," can handle both \emph{traffic characterization} in which the network traffic is categorized into major classes (\eg, FTP and P2P) and application identification in which end-user applications (\eg, BitTorrent and Skype) identification is desired. Contrary to most of the current methods, Deep Packet can identify encrypted traffic and also distinguishes between VPN and non-VPN network traffic. After an initial pre-processing phase on data, packets are fed into Deep Packet framework that embeds stacked autoencoder and convolution neural network in order to classify network traffic. Deep packet with CNN as its classification model achieved recall of $0.98$ in application identification task and $0.94$ in traffic categorization task. To the best of our knowledge, Deep Packet outperforms all of the proposed classification methods on UNB ISCX VPN-nonVPN dataset.
A Brief Introduction to Machine Learning for Engineers
Venue: arXiv cs.LG 2018
Year: 2018

This monograph aims at providing an introduction to key concepts, algorithms, and theoretical results in machine learning. The treatment concentrates on probabilistic models for supervised and unsupervised learning problems. It introduces fundamental concepts and algorithms by building on first principles, while also exposing the reader to more advanced topics with extensive pointers to the literature, within a unified notation and mathematical framework. The material is organized according to clearly defined categories, such as discriminative and generative models, frequentist and Bayesian approaches, exact and approximate inference, as well as directed and undirected models. This monograph is meant as an entry point for researchers with a background in probability and linear algebra.
Autonomous Quadrotor Landing using Deep Reinforcement Learning
Venue: arXiv cs.AI 2018
Year: 2018

Landing an unmanned aerial vehicle (UAV) on a ground marker is an open problem despite the effort of the research community. Previous attempts mostly focused on the analysis of hand-crafted geometric features and the use of external sensors in order to allow the vehicle to approach the land-pad. In this article, we propose a method based on deep reinforcement learning that only requires low-resolution images taken from a down-looking camera in order to identify the position of the marker and land the UAV on it. The proposed approach is based on a hierarchy of Deep Q-Networks (DQNs) used as high-level control policy for the navigation toward the marker. We implemented different technical solutions, such as the combination of vanilla and double DQNs, and a partitioned buffer replay. Using domain randomization we trained the vehicle on uniform textures and we tested it on a large variety of simulated and real-world environments. The overall performance is comparable with a state-of-the-art algorithm and human pilots.
A Denoising Loss Bound for Neural Network based Universal Discrete Denoisers
Venue: arXiv cs.LG 2018
Year: 2018

We obtain a denoising loss bound of the recently proposed neural network based universal discrete denoiser, Neural DUDE, which can adaptively learn its parameters solely from the noise-corrupted data, by minimizing the \emph{empirical estimated loss}. The resulting bound resembles the generalization error bound of the standard empirical risk minimizers (ERM) in supervised learning, and we show that the well-known bias-variance tradeoff also exists in our loss bound. The key tool we develop is the concentration of the unbiased estimated loss on the true denoising loss, which is shown to hold \emph{uniformly} for \emph{all} bounded network parameters and \emph{all} underlying clean sequences. For proving our main results, we make a novel application of the tools from the statistical learning theory. Finally, we show that the hyperparameters of Neural DUDE can be chosen from a small validation set to significantly improve the denoising performance, as predicted by the theoretical result of this paper.
Privacy Risk Assessment: From Art to Science, By Metrics
Venue: arXiv cs.CR 2018
Year: 2018

Privacy risk assessments aim to analyze and quantify the privacy risks associated with new systems. As such, they are critically important in ensuring that adequate privacy protections are built in. However, current methods to quantify privacy risk rely heavily on experienced analysts picking the "correct" risk level on e.g. a five-point scale. In this paper, we argue that a more scientific quantification of privacy risk increases accuracy and reliability and can thus make it easier to build privacy-friendly systems. We discuss how the impact and likelihood of privacy violations can be decomposed and quantified, and stress the importance of meaningful metrics and units of measurement. We suggest a method of quantifying and representing privacy risk that considers a collection of factors as well as a variety of contexts and attacker models. We conclude by identifying some of the major research questions to take this approach further in a variety of application scenarios.
A Study of AI Population Dynamics with Million-agent Reinforcement Learning
Venue: arXiv cs.AI 2018
Year: 2018

We conduct an empirical study on discovering the ordered collective dynamics obtained by a population of intelligence agents, driven by million-agent reinforcement learning. Our intention is to put intelligent agents into a simulated natural context and verify if the principles developed in the real world could also be used in understanding an artificially-created intelligent population. To achieve this, we simulate a large-scale predator-prey world, where the laws of the world are designed by only the findings or logical equivalence that have been discovered in nature. We endow the agents with the intelligence based on deep reinforcement learning (DRL). In order to scale the population size up to millions agents, a large-scale DRL training platform with redesigned experience buffer is proposed. Our results show that the population dynamics of AI agents, driven only by each agent's individual self-interest, reveals an ordered pattern that is similar to the Lotka-Volterra model studied in population biology. We further discover the emergent behaviors of collective adaptations in studying how the agents' grouping behaviors will change with the environmental resources. Both of the two findings could be explained by the self-organization theory in nature.
Data-Efficient Multirobot, Multitask Transfer Learning for Trajectory Tracking
Venue: arXiv cs.RO 2018
Year: 2018

Transfer learning has the potential to reduce the burden of data collection and to decrease the unavoidable risks of the training phase. In this letter, we introduce a multirobot, multitask transfer learning framework that allows a system to complete a task by learning from a few demonstrations of another task executed on another system. We focus on the trajectory tracking problem where each trajectory represents a different task, since many robotic tasks can be described as a trajectory tracking problem. The proposed multirobot transfer learning framework is based on a combined $\mathcal{L}_1$ adaptive control and an iterative learning control approach. The key idea is that the adaptive controller forces dynamically different systems to behave as a specified reference model. The proposed multitask transfer learning framework uses theoretical control results (e.g., the concept of vector relative degree) to learn a map from desired trajectories to the inputs that make the system track these trajectories with high accuracy. This map is used to calculate the inputs for a new, unseen trajectory. Experimental results using two different quadrotor platforms and six different trajectories show that, on average, the proposed framework reduces the first-iteration tracking error by 74% when information from tracking a different single trajectory on a different quadrotor is utilized.
Robustness Analysis of Visual QA Models by Basic Questions
Venue: arXiv cs.CV 2018
Year: 2018

Visual Question Answering (VQA) models should have both high robustness and accuracy. Unfortunately, most of the current VQA research only focuses on accuracy because there is a lack of proper methods to measure the robustness of VQA models. There are two main modules in our algorithm. Given a natural language question about an image, the first module takes the question as input and then outputs the ranked basic questions, with similarity scores, of the main given question. The second module takes the main question, image and these basic questions as input and then outputs the text-based answer of the main question about the given image. We claim that a robust VQA model is one, whose performance is not changed much when related basic questions as also made available to it as input. We formulate the basic questions generation problem as a LASSO optimization, and also propose a large scale Basic Question Dataset (BQD) and Rscore (novel robustness measure), for analyzing the robustness of VQA models. We hope our BQD will be used as a benchmark for to evaluate the robustness of VQA models, so as to help the community build more robust and accurate VQA models.