OpenRaiser/Intern-Atlas huggingface dataset:
Optimizing over a Restricted Policy Class in Markov Decision Processes
Venue: arXiv cs.LG 2018
Year: 2018

We address the problem of finding an optimal policy in a Markov decision process under a restricted policy class defined by the convex hull of a set of base policies. This problem is of great interest in applications in which a number of reasonably good (or safe) policies are already known and we are only interested in optimizing in their convex hull. We show that this problem is NP-hard to solve exactly as well as to approximate to arbitrary accuracy. However, under a condition that is akin to the occupancy measures of the base policies having large overlap, we show that there exists an efficient algorithm that finds a policy that is almost as good as the best convex combination of the base policies. The running time of the proposed algorithm is linear in the number of states and polynomial in the number of base policies. In practice, we demonstrate an efficient implementation for large state problems. Compared to traditional policy gradient methods, the proposed approach has the advantage that, apart from the computation of occupancy measures of some base policies, the iterative method need not interact with the environment during the optimization process. This is especially important in complex systems where estimating the value of a policy can be a time consuming process.
On the Suitability of $L_p$-norms for Creating and Preventing Adversarial Examples
Venue: arXiv cs.CR 2018
Year: 2018

Much research effort has been devoted to better understanding adversarial examples, which are specially crafted inputs to machine-learning models that are perceptually similar to benign inputs, but are classified differently (i.e., misclassified). Both algorithms that create adversarial examples and strategies for defending against them typically use $L_p$-norms to measure the perceptual similarity between an adversarial input and its benign original. Prior work has already shown, however, that two images need not be close to each other as measured by an $L_p$-norm to be perceptually similar. In this work, we show that nearness according to an $L_p$-norm is not just unnecessary for perceptual similarity, but is also insufficient. Specifically, focusing on datasets (CIFAR10 and MNIST), $L_p$-norms, and thresholds used in prior work, we show through online user studies that "adversarial examples" that are closer to their benign counterparts than required by commonly used $L_p$-norm thresholds can nevertheless be perceptually different to humans from the corresponding benign examples. Namely, the perceptual distance between two images that are "near" each other according to an $L_p$-norm can be high enough that participants frequently classify the two images as representing different objects or digits. Combined with prior work, we thus demonstrate that nearness of inputs as measured by $L_p$-norms is neither necessary nor sufficient for perceptual similarity, which has implications for both creating and defending against adversarial examples. We propose and discuss alternative similarity metrics to stimulate future research in the area.
Polynomial Treedepth Bounds in Linear Colorings
Venue: arXiv cs.DS 2018
Year: 2018

Low-treedepth colorings are an important tool for algorithms that exploit structure in classes of bounded expansion; they guarantee subgraphs that use few colors have bounded treedepth. These colorings have an implicit tradeoff between the total number of colors used and the treedepth bound, and prior empirical work suggests that the former dominates the run time of existing algorithms in practice. We introduce $p$-linear colorings as an alternative to the commonly used $p$-centered colorings. They can be efficiently computed in bounded expansion classes and use at most as many colors as $p$-centered colorings. Although a set of $k<p$ colors from a $p$-centered coloring induces a subgraph of treedepth at most $k$, the same number of colors from a $p$-linear coloring may induce subgraphs of larger treedepth. We establish a polynomial upper bound on the treedepth in general graphs, and give tighter bounds in trees and interval graphs via constructive coloring algorithms. We also give a co-NP-completeness reduction for recognizing $p$-linear colorings and discuss ways to overcome this limitation in practice. This preprint extends results that appeared in [9]; for full proofs omitted from [9], see previous versions of this preprint.
Relational Reasoning for Markov Chains in a Probabilistic Guarded Lambda Calculus
Venue: arXiv cs.PL 2018
Year: 2018

We extend the simply-typed guarded $λ$-calculus with discrete probabilities and endow it with a program logic for reasoning about relational properties of guarded probabilistic computations. This provides a framework for programming and reasoning about infinite stochastic processes like Markov chains. We demonstrate the logic sound by interpreting its judgements in the topos of trees and by using probabilistic couplings for the semantics of relational assertions over distributions on discrete types. The program logic is designed to support syntax-directed proofs in the style of relational refinement types, but retains the expressiveness of higher-order logic extended with discrete distributions, and the ability to reason relationally about expressions that have different types or syntactic structure. In addition, our proof system leverages a well-known theorem from the coupling literature to justify better proof rules for relational reasoning about probabilistic expressions. We illustrate these benefits with a broad range of examples that were beyond the scope of previous systems, including shift couplings and lump couplings between random walks.
Identification of LTV Dynamical Models with Smooth or Discontinuous Time Evolution by means of Convex Optimization
Venue: arXiv cs.SY 2018
Year: 2018

We establish a connection between trend filtering and system identification which results in a family of new identification methods for linear, time-varying (LTV) dynamical models based on convex optimization. We demonstrate how the design of the cost function promotes a model with either a continuous change in dynamics over time, or causes discontinuous changes in model coefficients occurring at a finite (sparse) set of time instances. We further discuss the introduction of priors on the model parameters for situations where excitation is insufficient for identification. The identification problems are cast as convex optimization problems and are applicable to, e.g., ARX models and state-space models with time-varying parameters. We illustrate usage of the methods in simulations of jump-linear systems, a nonlinear robot arm with non-smooth friction and stiff contacts as well as in model-based, trajectory centric reinforcement learning on a smooth nonlinear system.
A unified framework for designing EPTAS's for load balancing on parallel machines
Venue: arXiv cs.DS 2018
Year: 2018

We consider a general load balancing problem on parallel machines. Our machine environment in particular generalizes the standard models of identical machines, and the model of uniformly related machines, as well as machines with a constant number of types, and machines with activation costs. The objective functions that we consider contain in particular the makespan objective and the minimization of the $\ell_p$-norm of the vector of loads of the machines both with possibly job rejection. We consider this general model and design an efficient polynomial time approximation scheme (EPTAS) that applies for all its previously studied special cases. This EPTAS improves the current best approximation scheme for some of these cases where only a polynomial time approximation scheme (PTAS) was known into an EPTAS.
Attention-Based Guided Structured Sparsity of Deep Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

Network pruning is aimed at imposing sparsity in a neural network architecture by increasing the portion of zero-valued weights for reducing its size regarding energy-efficiency consideration and increasing evaluation speed. In most of the conducted research efforts, the sparsity is enforced for network pruning without any attention to the internal network characteristics such as unbalanced outputs of the neurons or more specifically the distribution of the weights and outputs of the neurons. That may cause severe accuracy drop due to uncontrolled sparsity. In this work, we propose an attention mechanism that simultaneously controls the sparsity intensity and supervised network pruning by keeping important information bottlenecks of the network to be active. On CIFAR-10, the proposed method outperforms the best baseline method by 6% and reduced the accuracy drop by 2.6x at the same level of sparsity.
Introduction to the SP theory of intelligence
Venue: arXiv cs.AI 2018
Year: 2018

This article provides a brief introduction to the "Theory of Intelligence" and its realisation in the "SP Computer Model". The overall goal of the SP programme of research, in accordance with long-established principles in science, has been the simplification and integration of observations and concepts across artificial intelligence, mainstream computing, mathematics, and human learning, perception, and cognition. In broad terms, the SP system is a brain-like system that takes in "New" information through its senses and stores some or all of it as "Old" information. A central idea in the system is the powerful concept of "SP-multiple-alignment", borrowed and adapted from bioinformatics. This the key to the system's versatility in aspects of intelligence, in the representation of diverse kinds of knowledge, and in the seamless integration of diverse aspects of intelligence and diverse kinds of knowledge, in any combination. There are many potential benefits and applications of the SP system. It is envisaged that the system will be developed as the "SP Machine", which will initially be a software virtual machine, hosted on a high-performance computer, a vehicle for further research and a step towards the development of an industrial-strength SP Machine.
Deep Learning Architectures for Face Recognition in Video Surveillance
Venue: arXiv cs.CV 2018
Year: 2018

Face recognition (FR) systems for video surveillance (VS) applications attempt to accurately detect the presence of target individuals over a distributed network of cameras. In video-based FR systems, facial models of target individuals are designed a priori during enrollment using a limited number of reference still images or video data. These facial models are not typically representative of faces being observed during operations due to large variations in illumination, pose, scale, occlusion, blur, and to camera inter-operability. Specifically, in still-to-video FR application, a single high-quality reference still image captured with still camera under controlled conditions is employed to generate a facial model to be matched later against lower-quality faces captured with video cameras under uncontrolled conditions. Current video-based FR systems can perform well on controlled scenarios, while their performance is not satisfactory in uncontrolled scenarios mainly because of the differences between the source (enrollment) and the target (operational) domains. Most of the efforts in this area have been toward the design of robust video-based FR systems in unconstrained surveillance environments. This chapter presents an overview of recent advances in still-to-video FR scenario through deep convolutional neural networks (CNNs). In particular, deep learning architectures proposed in the literature based on triplet-loss function (e.g., cross-correlation matching CNN, trunk-branch ensemble CNN and HaarNet) and supervised autoencoders (e.g., canonical face representation CNN) are reviewed and compared in terms of accuracy and computational complexity.
Stochastic Control of Computation Offloading to a Helper with a Dynamically Loaded CPU
Venue: arXiv cs.IT 2018
Year: 2018

Due to densification of wireless networks, there exist abundance of idling computation resources at edge devices. These resources can be scavenged by offloading heavy computation tasks from small IoT devices in proximity, thereby overcoming their limitations and lengthening their battery lives. However, unlike dedicated servers, the spare resources offered by edge helpers are random and intermittent. Thus, it is essential for a user to intelligently control the amounts of data for offloading and local computing so as to ensure a computation task can be finished in time consuming minimum energy. In this paper, we design energy-efficient control policies in a computation offloading system with a random channel and a helper with a dynamically loaded CPU. Specifically, the policy adopted by the helper aims at determining the sizes of offloaded and locally-computed data for a given task in different slots such that the total energy consumption for transmission and local CPU is minimized under a task-deadline constraint. As the result, the polices endow an offloading user robustness against channel-and-helper randomness besides balancing offloading and local computing. By modeling the channel and helper-CPU as Markov chains, the problem of offloading control is converted into a Markov-decision process. Though dynamic programming (DP) for numerically solving the problem does not yield the optimal policies in closed form, we leverage the procedure to quantify the optimal policy structure and apply the result to design optimal or sub-optimal policies. For different cases ranging from zero to large buffers, the low-complexity of the policies overcomes the "curse-of-dimensionality" in DP arising from joint consideration of channel, helper CPU and buffer states.
Dual polarization nonlinear Fourier transform-based optical communication system
Venue: arXiv cs.ET 2018
Year: 2018

New services and applications are causing an exponential increase in internet traffic. In a few years, current fiber optic communication system infrastructure will not be able to meet this demand because fiber nonlinearity dramatically limits the information transmission rate. Eigenvalue communication could potentially overcome these limitations. It relies on a mathematical technique called "nonlinear Fourier transform (NFT)" to exploit the "hidden" linearity of the nonlinear Schrödinger equation as the master model for signal propagation in an optical fiber. We present here the theoretical tools describing the NFT for the Manakov system and report on experimental transmission results for dual polarization in fiber optic eigenvalue communications. A transmission of up to 373.5 km with bit error rate less than the hard-decision forward error correction threshold has been achieved. Our results demonstrate that dual-polarization NFT can work in practice and enable an increased spectral efficiency in NFT-based communication systems, which are currently based on single polarization channels.
Improving OCR Accuracy on Early Printed Books by combining Pretraining, Voting, and Active Learning
Venue: arXiv cs.CV 2018
Year: 2018

We combine three methods which significantly improve the OCR accuracy of OCR models trained on early printed books: (1) The pretraining method utilizes the information stored in already existing models trained on a variety of typesets (mixed models) instead of starting the training from scratch. (2) Performing cross fold training on a single set of ground truth data (line images and their transcriptions) with a single OCR engine (OCRopus) produces a committee whose members then vote for the best outcome by also taking the top-N alternatives and their intrinsic confidence values into account. (3) Following the principle of maximal disagreement we select additional training lines which the voters disagree most on, expecting them to offer the highest information gain for a subsequent training (active learning). Evaluations on six early printed books yielded the following results: On average the combination of pretraining and voting improved the character accuracy by 46% when training five folds starting from the same mixed model. This number rose to 53% when using different models for pretraining, underlining the importance of diverse voters. Incorporating active learning improved the obtained results by another 16% on average (evaluated on three of the six books). Overall, the proposed methods lead to an average error rate of 2.5% when training on only 60 lines. Using a substantial ground truth pool of 1,000 lines brought the error rate down even further to less than 1% on average.
Discovering Key Nodes in a Temporal Social Network
Venue: arXiv cs.SI 2018
Year: 2018

[Background]Discovering key nodes plays a significant role in Social Network Analysis(SNA). Effective and accurate mining of key nodes promotes more successful applications in fields like advertisement and recommendation. [Methods] With focus on the temporal and categorical property of users' actions - when did they re-tweet or reply a message, as well as their social intimacy measured by structural embeddings, we designed a more sensitive PageRank-like algorithm to accommodate the growing and changing social network in the pursue of mining key nodes. [Results] Compared with our baseline PageRank algorithm, key nodes selected by our ranking algorithm noticeably perform better in the SIR disease simulations with SNAP Higgs dataset. [Conclusion] These results contributed to a better understanding of disseminations of social events over the network.
Role colouring graphs in hereditary classes
Venue: arXiv cs.CC 2018
Year: 2018

We study the computational complexity of computing role colourings of graphs in hereditary classes. We are interested in describing the family of hereditary classes on which a role colouring with k colours can be computed in polynomial time. In particular, we wish to describe the boundary between the "hard" and "easy" classes. The notion of a boundary class has been introduced by Alekseev in order to study such boundaries. Our main results are a boundary class for the k-role colouring problem and the related k-coupon colouring problem which has recently received a lot of attention in the literature. The latter result makes use of a technique for generating regular graphs of arbitrary girth which may be of independent interest.
Improved Explainability of Capsule Networks: Relevance Path by Agreement
Venue: arXiv cs.CV 2018
Year: 2018

Recent advancements in signal processing and machine learning domains have resulted in an extensive surge of interest in deep learning models due to their unprecedented performance and high accuracy for different and challenging problems of significant engineering importance. However, when such deep learning architectures are utilized for making critical decisions such as the ones that involve human lives (e.g., in medical applications), it is of paramount importance to understand, trust, and in one word "explain" the rational behind deep models' decisions. Currently, deep learning models are typically considered as black-box systems, which do not provide any clue on their internal processing actions. Although some recent efforts have been initiated to explain behavior and decisions of deep networks, explainable artificial intelligence (XAI) domain is still in its infancy. In this regard, we consider capsule networks (referred to as CapsNets), which are novel deep structures; recently proposed as an alternative counterpart to convolutional neural networks (CNNs), and posed to change the future of machine intelligence. In this paper, we investigate and analyze structures and behaviors of the CapsNets and illustrate potential explainability properties of such networks. Furthermore, we show possibility of transforming deep learning architectures in to transparent networks via incorporation of capsules in different layers instead of convolution layers of the CNNs.
Cluster Naturalistic Driving Encounters Using Deep Unsupervised Learning
Venue: arXiv cs.LG 2018
Year: 2018

Learning knowledge from driving encounters could help self-driving cars make appropriate decisions when driving in complex settings with nearby vehicles engaged. This paper develops an unsupervised classifier to group naturalistic driving encounters into distinguishable clusters by combining an auto-encoder with k-means clustering (AE-kMC). The effectiveness of AE-kMC was validated using the data of 10,000 naturalistic driving encounters which were collected by the University of Michigan, Ann Arbor in the past five years. We compare our developed method with the $k$-means clustering methods and experimental results demonstrate that the AE-kMC method outperforms the original k-means clustering method.
Neural Aesthetic Image Reviewer
Venue: arXiv cs.CV 2018
Year: 2018

Recently, there is a rising interest in perceiving image aesthetics. The existing works deal with image aesthetics as a classification or regression problem. To extend the cognition from rating to reasoning, a deeper understanding of aesthetics should be based on revealing why a high- or low-aesthetic score should be assigned to an image. From such a point of view, we propose a model referred to as Neural Aesthetic Image Reviewer, which can not only give an aesthetic score for an image, but also generate a textual description explaining why the image leads to a plausible rating score. Specifically, we propose two multi-task architectures based on shared aesthetically semantic layers and task-specific embedding layers at a high level for performance improvement on different tasks. To facilitate researches on this problem, we collect the AVA-Reviews dataset, which contains 52,118 images and 312,708 comments in total. Through multi-task learning, the proposed models can rate aesthetic images as well as produce comments in an end-to-end manner. It is confirmed that the proposed models outperform the baselines according to the performance evaluation on the AVA-Reviews dataset. Moreover, we demonstrate experimentally that our model can generate textual reviews related to aesthetics, which are consistent with human perception.
Avoiding overfitting of multilayer perceptrons by training derivatives
Venue: arXiv cs.NE 2018
Year: 2018

Resistance to overfitting is observed for neural networks trained with extended backpropagation algorithm. In addition to target values, its cost function uses derivatives of those up to the $4^{\mathrm{th}}$ order. For common applications of neural networks, high order derivatives are not readily available, so simpler cases are considered: training network to approximate analytical function inside 2D and 5D domains and solving Poisson equation inside a 2D circle. For function approximation, the cost is a sum of squared differences between output and target as well as their derivatives with respect to the input. Differential equations are usually solved by putting a multilayer perceptron in place of unknown function and training its weights, so that equation holds within some margin of error. Commonly used cost is the equation's residual squared. Added terms are squared derivatives of said residual with respect to the independent variables. To investigate overfitting, the cost is minimized for points of regular grids with various spacing, and its root mean is compared with its value on much denser test set. Fully connected perceptrons with six hidden layers and $2\cdot10^{4}$, $1\cdot10^{6}$ and $5\cdot10^{6}$ weights in total are trained with Rprop until cost changes by less than 10% for last 1000 epochs, or when the $10000^{\mathrm{th}}$ epoch is reached. Training the network with $5\cdot10^{6}$ weights to represent simple 2D function using 10 points with 8 extra derivatives in each produces cost test to train ratio of $1.5$, whereas for classical backpropagation in comparable conditions this ratio is $2\cdot10^{4}$.