OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Armed Bandits for Correlated Markovian Environments with Smoothed Reward Feedback
Venue: arXiv cs.LG 2019
Year: 2019

We study a multi-armed bandit problem in a dynamic environment where arm rewards evolve in a correlated fashion according to a Markov chain. Different than much of the work on related problems, in our formulation a learning algorithm does not have access to either a priori information or observations of the state of the Markov chain and only observes smoothed reward feedback following time intervals we refer to as epochs. We demonstrate that existing methods such as UCB and $\varepsilon$-greedy can suffer linear regret in such an environment. Employing mixing-time bounds on Markov chains, we develop algorithms called EpochUCB and EpochGreedy that draw inspiration from the aforementioned methods, yet which admit sublinear regret guarantees for the problem formulation. Our proposed algorithms proceed in epochs in which an arm is played repeatedly for a number of iterations that grows linearly as a function of the number of times an arm has been played in the past. We analyze these algorithms under two types of smoothed reward feedback at the end of each epoch: a reward that is the discount-average of the discounted rewards within an epoch, and a reward that is the time-average of the rewards within an epoch.
Increasing the Degree of Parallelism Using Speculative Execution in Task-based Runtime Systems
Venue: arXiv cs.DC 2019
Year: 2019

Task-based programming models have demonstrated their efficiency in the development of scientific applications on modern high-performance platforms. They allow delegation of the management of parallelization to the runtime system (RS), which is in charge of the data coherency, the scheduling, and the assignment of the work to the computational units. However, some applications have a limited degree of parallelism such that no matter how efficient the RS implementation, they may not scale on modern multicore CPUs. In this paper, we propose using speculation to unleash the parallelism when it is uncertain if some tasks will modify data, and we formalize a new methodology to enable speculative execution in a graph of tasks. This description is partially implemented in our new C++ RS called SPETABARU, which is capable of executing tasks in advance if some others are not certain to modify the data. We study the behavior of our approach to compute Monte Carlo and replica exchange Monte Carlo simulations.
Narcissus: Deriving Correct-By-Construction Decoders and Encoders from Binary Formats
Venue: arXiv cs.PL 2019
Year: 2019

It is a neat result from functional programming that libraries of parser combinators can support rapid construction of decoders for quite a range of formats. With a little more work, the same combinator program can denote both a decoder and an encoder. Unfortunately, the real world is full of gnarly formats, as with the packet formats that make up the standard Internet protocol stack. Most past parser-combinator approaches cannot handle these formats, and the few exceptions require redundancy -- one part of the natural grammar needs to be hand-translated into hints in multiple parts of a parser program. We show how to recover very natural and nonredundant format specifications, covering all popular network packet formats and generating both decoders and encoders automatically. The catch is that we use the Coq proof assistant to derive both kinds of artifacts using tactics, automatically, in a way that guarantees that they form inverses of each other. We used our approach to reimplement packet processing for a full Internet protocol stack, inserting our replacement into the OCaml-based MirageOS unikernel, resulting in minimal performance degradation.
Feature Selective Small Object Detection via Knowledge-based Recurrent Attentive Neural Network
Venue: arXiv cs.CV 2019
Year: 2019

At present, the performance of deep neural network in general object detection is comparable to or even surpasses that of human beings. However, due to the limitations of deep learning itself, the small proportion of feature pixels, and the occurence of blur and occlusion, the detection of small objects in complex scenes is still an open question. But we can not deny that real-time and accurate object detection is fundamental to automatic perception and subsequent perception-based decision-making and planning tasks of autonomous driving. Considering the characteristics of small objects in autonomous driving scene, we proposed a novel method named KB-RANN, which based on domain knowledge, intuitive experience and feature attentive selection. It can focus on particular parts of image features, and then it tries to stress the importance of these features and strengthenes the learning parameters of them. Our comparative experiments on KITTI and COCO datasets show that our proposed method can achieve considerable results both in speed and accuracy, and can improve the effect of small object detection through self-selection of important features and continuous enhancement of proposed method, and deployed it in our self-developed autonomous driving car.
$H$-colouring $P_t$-free graphs in subexponential time
Venue: arXiv cs.DM 2019
Year: 2019

A graph is called $P_t$-free if it does not contain the path on $t$ vertices as an induced subgraph. Let $H$ be a multigraph with the property that any two distinct vertices share at most one common neighbour. We show that the generating function for (list) graph homomorphisms from $G$ to $H$ can be calculated in subexponential time $2^{O\left(\sqrt{tn\log(n)}\right)}$ for $n=|V(G)|$ in the class of $P_t$-free graphs $G$. As a corollary, we show that the number of 3-colourings of a $P_t$-free graph $G$ can be found in subexponential time. On the other hand, no subexponential time algorithm exists for 4-colourability of $P_t$-free graphs assuming the Exponential Time Hypothesis. Along the way, we prove that $P_t$-free graphs have pathwidth that is linear in their maximum degree.
Robust Distributed Control Beyond Quadratic Invariance
Venue: arXiv cs.SY 2019
Year: 2019

The problem of robust distributed control arises in several large-scale systems, such as transportation networks and power grid systems. In many practical scenarios controllers might not have enough information to make globally optimal decisions in a tractable way. We propose a novel class of tractable optimization problems whose solution is a controller complying with any specified information structure. The approach we suggest is based on decomposing intractable information constraints into two subspace constraints in the disturbance feedback domain. We discuss how to perform the decomposition in an optimized way. The resulting control policy is globally optimal when a condition known as Quadratic Invariance (QI) holds, whereas it is feasible and it provides a provable upper bound on the minimum cost when QI does not hold. Finally, we show that our method can lead to improved performance guarantees with respect to previous approaches, by applying the developed techniques to the platooning of autonomous vehicles.
Analog simulator of integro-differential equations with classical memristors
Venue: arXiv cs.ET 2019
Year: 2019

An analog computer makes use of continuously changeable quantities of a system, such as its electrical, mechanical, or hydraulic properties, to solve a given problem. While these devices are usually computationally more powerful than their digital counterparts, they suffer from analog noise which does not allow for error control. We will focus on analog computers based on active electrical networks comprised of resistors, capacitors, and operational amplifiers which are capable of simulating any linear ordinary differential equation. However, the class of nonlinear dynamics they can solve is limited. In this work, by adding memristors to the electrical network, we show that the analog computer can simulate a large variety of linear and nonlinear integro-differential equations by carefully choosing the conductance and the dynamics of the memristor state variable. To the best of our knowledge, this is the first time that circuits based on memristors are proposed for simulations. We study the performance of these analog computers by simulating integro-differential models related to fluid dynamics, nonlinear Volterra equations for population growth, and quantum models describing non-Markovian memory effects, among others. Finally, we perform stability tests by considering imperfect analog components, obtaining robust solutions with up to $13\%$ relative error for relevant timescales.
Runlength-Limited Sequences and Shift-Correcting Codes: Asymptotic Analysis
Venue: arXiv cs.IT 2019
Year: 2019

This work is motivated by the problem of error correction in bit-shift channels with the so-called $ (d,k) $ input constraints (where successive $ 1 $'s are required to be separated by at least $ d $ and at most $ k $ zeros, $ 0 \leq d < k \leq \infty $). Bounds on the size of optimal $ (d,k) $-constrained codes correcting a fixed number of bit-shifts are derived, with a focus on their asymptotic behavior in the large block-length limit. The upper bound is obtained by a packing argument, while the lower bound follows from a construction based on a family of integer lattices. Several properties of $ (d, k) $-constrained sequences that may be of independent interest are established as well; in particular, the exponential growth-rate of the number of $ (d, k) $-constrained constant-weight sequences is characterized. The results are relevant for magnetic and optical information storage systems, reader-to-tag RFID channels, and other communication models where bit-shift errors are dominant and where $ (d, k) $-constrained sequences are used for modulation.
Reviving and Improving Recurrent Back-Propagation
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we revisit the recurrent back-propagation (RBP) algorithm, discuss the conditions under which it applies as well as how to satisfy them in deep neural networks. We show that RBP can be unstable and propose two variants based on conjugate gradient on the normal equations (CG-RBP) and Neumann series (Neumann-RBP). We further investigate the relationship between Neumann-RBP and back propagation through time (BPTT) and its truncated version (TBPTT). Our Neumann-RBP has the same time complexity as TBPTT but only requires constant memory, whereas TBPTT's memory cost scales linearly with the number of truncation steps. We examine all RBP variants along with BPTT and TBPTT in three different application domains: associative memory with continuous Hopfield networks, document classification in citation networks using graph neural networks and hyperparameter optimization for fully connected networks. All experiments demonstrate that RBPs, especially the Neumann-RBP variant, are efficient and effective for optimizing convergent recurrent neural networks. Code is released at: \url{https://github.com/lrjconan/RBP}.
Network Service Orchestration: A Survey
Venue: arXiv cs.NI 2019
Year: 2019

Business models of network service providers are undergoing an evolving transformation fueled by vertical customer demands and technological advances such as 5G, Software Defined Networking~(SDN), and Network Function Virtualization~(NFV). Emerging scenarios call for agile network services consuming network, storage, and compute resources across heterogeneous infrastructures and administrative domains. Coordinating resource control and service creation across interconnected domains and diverse technologies becomes a grand challenge. Research and development efforts are being devoted to enabling orchestration processes to automate, coordinate, and manage the deployment and operation of network services. In this survey, we delve into the topic of Network Service Orchestration~(NSO) by reviewing the historical background, relevant research projects, enabling technologies, and standardization activities. We define key concepts and propose a taxonomy of NSO approaches and solutions to pave the way towards a common understanding of the various ongoing efforts around the realization of diverse NSO application scenarios. Based on the analysis of the state of affairs, we present a series of open challenges and research opportunities, altogether contributing to a timely and comprehensive survey on the vibrant and strategic topic of network service orchestration.
Information-Theoretic Security or Covert Communication
Venue: arXiv cs.CR 2019
Year: 2019

Information-theoretic secrecy, in particular the wiretap channel formulation, provides protection against interception of a message by adversary Eve and has been widely studied in the last two decades. In contrast, covert communications under an analogous formulation provides protection against even the detection of the presence of the message by an adversary, and it has drawn significant interest recently. These two security topics are generally applicable in different scenarios; however, here we explore what can be learned by studying them under a common framework. Under a similar but not identical mathematical formulation, we introduce power optimization problems for each of the secrecy and the covert communications scenario, and we exploit common aspects of the problems to employ similar tools in their respective optimizations. Moreover, due to the practical limitations, we assume only channel
Revenue Management on an On-Demand Service Platform
Venue: arXiv cs.GT 2019
Year: 2019

I consider the optimal hourly (or per-unit-time in general) pricing problem faced by a freelance worker (or a service provider) on an on-demand service platform. Service requests arriving while the worker is busy are lost forever. Thus, the optimal hourly prices need to capture the average hourly opportunity costs incurred by accepting jobs. Due to potential asymmetries in these costs, price discrimination across jobs based on duration, characteristics of the arrival process, etc., may be necessary for optimality, even if the customers' hourly willingness to pay is identically distributed. I first establish that such price discrimination is not necessary if the customer arrival process is Poisson: in this case, the optimal policy charges an identical hourly rate for all jobs. This result holds even if the earnings are discounted over time. I then consider the case where the customers belong to different classes that are differentiated in their willingness to pay. I present a simple and practical iterative procedure to compute the optimal prices in this case under standard regularity assumptions on the distributions of customer valuations. I finally show that these insights continue to hold in the presence of competition between multiple quality-differentiated workers, assuming a natural customer choice model in which a customer always chooses the best available worker that she can afford.
Weakly Supervised Object Localization on grocery shelves using simple FCN and Synthetic Dataset
Venue: arXiv cs.CV 2019
Year: 2019

We propose a weakly supervised method using two algorithms to predict object bounding boxes given only an image classification dataset. First algorithm is a simple Fully Convolutional Network (FCN) trained to classify object instances. We use the property of FCN to return a mask for images larger than training images to get a primary output segmentation mask during test time by passing an image pyramid to it. We enhance the FCN output mask into final output bounding boxes by a Convolutional Encoder-Decoder (ConvAE) viz. the second algorithm. ConvAE is trained to localize objects on an artificially generated dataset of output segmentation masks. We demonstrate the effectiveness of this method in localizing objects in grocery shelves where annotating data for object detection is hard due to variety of objects. This method can be extended to any problem domain where collecting images of objects is easy and annotating their coordinates is hard.
Technical Report: When Does Machine Learning FAIL? Generalized Transferability for Evasion and Poisoning Attacks
Venue: arXiv cs.CR 2019
Year: 2019

Recent results suggest that attacks against supervised machine learning systems are quite effective, while defenses are easily bypassed by new attacks. However, the specifications for machine learning systems currently lack precise adversary definitions, and the existing attacks make diverse, potentially unrealistic assumptions about the strength of the adversary who launches them. We propose the FAIL attacker model, which describes the adversary's knowledge and control along four dimensions. Our model allows us to consider a wide range of weaker adversaries who have limited control and incomplete knowledge of the features, learning algorithms and training instances utilized. To evaluate the utility of the FAIL model, we consider the problem of conducting targeted poisoning attacks in a realistic setting: the crafted poison samples must have clean labels, must be individually and collectively inconspicuous, and must exhibit a generalized form of transferability, defined by the FAIL model. By taking these constraints into account, we design StingRay, a targeted poisoning attack that is practical against 4 machine learning applications, which use 3 different learning algorithms, and can bypass 2 existing defenses. Conversely, we show that a prior evasion attack is less effective under generalized transferability. Such attack evaluations, under the FAIL adversary model, may also suggest promising directions for future defenses.
$\tilde{O}(n^{1/3})$-Space Algorithm for the Grid Graph Reachability Problem
Venue: arXiv cs.DS 2019
Year: 2019

The directed graph reachability problem takes as input an $n$-vertex directed graph $G=(V,E)$, and two distinguished vertices $s$ and $t$. The problem is to determine whether there exists a path from $s$ to $t$ in $G$. This is a canonical complete problem for class NL. Asano et al. proposed an $\tilde{O}(\sqrt{n})$ space and polynomial time algorithm for the directed grid and planar graph reachability problem. The main result of this paper is to show that the directed graph reachability problem restricted to grid graphs can be solved in polynomial time using only $\tilde{O}(n^{1/3})$ space.
The Subpower Membership Problem for Finite Algebras with Cube Terms
Venue: arXiv cs.LO 2019
Year: 2019

The subalgebra membership problem is the problem of deciding if a given element belongs to an algebra given by a set of generators. This is one of the best established computational problems in algebra. We consider a variant of this problem, which is motivated by recent progress in the Constraint Satisfaction Problem, and is often referred to as the Subpower Membership Problem (SMP). In the SMP we are given a set of tuples in a direct product of algebras from a fixed finite set $\mathcal{K}$ of finite algebras, and are asked whether or not a given tuple belongs to the subalgebra of the direct product generated by a given set. Our main result is that the subpower membership problem SMP($\mathcal{K}$) is in P if $\mathcal{K}$ is a finite set of finite algebras with a cube term, provided $\mathcal{K}$ is contained in a residually small variety. We also prove that for any finite set of finite algebras $\mathcal{K}$ in a variety with a cube term, each one of the problems SMP($\mathcal{K}$), SMP($\mathbb{HS} \mathcal{K}$), and finding compact representations for subpowers in $\mathcal{K}$, is polynomial time reducible to any of the others, and the first two lie in NP.
Sequence pairs with asymptotically optimal aperiodic correlation
Venue: arXiv cs.IT 2019
Year: 2019

The Pursley-Sarwate criterion of a pair of finite complex-valued sequences measures the collective smallness of the aperiodic autocorrelations and the aperiodic crosscorrelations of the two sequences. It is known that this quantity is always at least 1 with equality if and only if the sequence pair is a Golay pair. We exhibit pairs of complex-valued sequences whose entries have unit magnitude for which the Pursley-Sarwate criterion tends to 1 as the sequence length tends to infinity. Our constructions use different carefully chosen Chu sequences.
Linear model predictive safety certification for learning-based control
Venue: arXiv cs.SY 2019
Year: 2019

While it has been repeatedly shown that learning-based controllers can provide superior performance, they often lack of safety guarantees. This paper aims at addressing this problem by introducing a model predictive safety certification (MPSC) scheme for polytopic linear systems with additive disturbances. The scheme verifies safety of a proposed learning-based input and modifies it as little as necessary in order to keep the system within a given set of constraints. Safety is thereby related to the existence of a model predictive controller (MPC) providing a feasible trajectory towards a safe target set. A robust MPC formulation accounts for the fact that the model is generally uncertain in the context of learning, which allows proving constraint satisfaction at all times under the proposed MPSC strategy. The MPSC scheme can be used in order to expand any potentially conservative set of safe states for learning and we prove an iterative technique for enlarging the safe set. Finally, a practical data-based design procedure for MPSC is proposed using scenario optimization.
Evaluating Sentence-Level Relevance Feedback for High-Recall Information Retrieval
Venue: arXiv cs.IR 2019
Year: 2019

This study uses a novel simulation framework to evaluate whether the time and effort necessary to achieve high recall using active learning is reduced by presenting the reviewer with isolated sentences, as opposed to full documents, for relevance feedback. Under the weak assumption that more time and effort is required to review an entire document than a single sentence, simulation results indicate that the use of isolated sentences for relevance feedback can yield comparable accuracy and higher efficiency, relative to the state-of-the-art Baseline Model Implementation (BMI) of the AutoTAR Continuous Active Learning ("CAL") method employed in the TREC 2015 and 2016 Total Recall Track.
Iterative Low-Rank Approximation for CNN Compression
Venue: arXiv cs.CV 2019
Year: 2019

Deep convolutional neural networks contain tens of millions of parameters, making them impossible to work efficiently on embedded devices. We propose iterative approach of applying low-rank approximation to compress deep convolutional neural networks. Since classification and object detection are the most favored tasks for embedded devices, we demonstrate the effectiveness of our approach by compressing AlexNet, VGG-16, YOLOv2 and Tiny YOLO networks. Our results show the superiority of the proposed method compared to non-repetitive ones. We demonstrate higher compression ratio providing less accuracy loss.
Real Time Surveillance for Low Resolution and Limited-Data Scenarios: An Image Set Classification Approach
Venue: arXiv cs.CV 2019
Year: 2019

This paper proposes a novel image set classification technique based on the concept of linear regression. Unlike most other approaches, the proposed technique does not involve any training or feature extraction. The gallery image sets are represented as subspaces in a high dimensional space. Class specific gallery subspaces are used to estimate regression models for each image of the test image set. Images of the test set are then projected on the gallery subspaces. Residuals, calculated using the Euclidean distance between the original and the projected test images, are used as the distance metric. Three different strategies are devised to decide on the final class of the test image set. We performed extensive evaluations of the proposed technique under the challenges of low resolution, noise and less gallery data for the tasks of surveillance, video-based face recognition and object recognition. Experiments show that the proposed technique achieves a better classification accuracy and a faster execution time compared to existing techniques especially under the challenging conditions of low resolution and small gallery and test data.