OpenRaiser/Intern-Atlas huggingface dataset:
Correctness and Performance for Stateful Chained Network Functions
Venue: arXiv cs.NI 2018
Year: 2018

Network functions virtualization (NFV) allows operators to employ NF chains to realize custom policies, and dynamically add instances to meet demand or for failover. NFs maintain detailed per- and cross-flow state which needs careful management, especially during dynamic actions. Crucially, state management must: (1) ensure NF chain-wide correctness and (2) have good performance. To this end, we built \name, an NFV framework that leverages an external state store coupled with state management algorithms and metadata maintenance for correct operation even under a range of failures. Our evaluation shows that CHC can support ~10Gbps per-NF throughput and <0.6mus increase in median per-NF packet processing latency, and chain-wide correctness at little additional cost.
Deep Multi-scale Convolutional Neural Network for Dynamic Scene Deblurring
Venue: arXiv cs.CV 2018
Year: 2018

Non-uniform blind deblurring for general dynamic scenes is a challenging computer vision problem as blurs arise not only from multiple object motions but also from camera shake, scene depth variation. To remove these complicated motion blurs, conventional energy optimization based methods rely on simple assumptions such that blur kernel is partially uniform or locally linear. Moreover, recent machine learning based methods also depend on synthetic blur datasets generated under these assumptions. This makes conventional deblurring methods fail to remove blurs where blur kernel is difficult to approximate or parameterize (e.g. object motion boundaries). In this work, we propose a multi-scale convolutional neural network that restores sharp images in an end-to-end manner where blur is caused by various sources. Together, we present multi-scale loss function that mimics conventional coarse-to-fine approaches. Furthermore, we propose a new large-scale dataset that provides pairs of realistic blurry image and the corresponding ground truth sharp image that are obtained by a high-speed camera. With the proposed model trained on this dataset, we demonstrate empirically that our method achieves the state-of-the-art performance in dynamic scene deblurring not only qualitatively, but also quantitatively.
Prediction with a Short Memory
Venue: arXiv cs.LG 2018
Year: 2018

We consider the problem of predicting the next observation given a sequence of past observations, and consider the extent to which accurate prediction requires complex algorithms that explicitly leverage long-range dependencies. Perhaps surprisingly, our positive results show that for a broad class of sequences, there is an algorithm that predicts well on average, and bases its predictions only on the most recent few observation together with a set of simple summary statistics of the past observations. Specifically, we show that for any distribution over observations, if the mutual information between past observations and future observations is upper bounded by $I$, then a simple Markov model over the most recent $I/ε$ observations obtains expected KL error $ε$---and hence $\ell_1$ error $\sqrtε$---with respect to the optimal predictor that has access to the entire past and knows the data generating distribution. For a Hidden Markov Model with $n$ hidden states, $I$ is bounded by $\log n$, a quantity that does not depend on the mixing time, and we show that the trivial prediction algorithm based on the empirical frequencies of length $O(\log n/ε)$ windows of observations achieves this error, provided the length of the sequence is $d^{Ω(\log n/ε)}$, where $d$ is the size of the observation alphabet. We also establish that this result cannot be improved upon, even for the class of HMMs, in the following two senses: First, for HMMs with $n$ hidden states, a window length of $\log n/ε$ is information-theoretically necessary to achieve expected $\ell_1$ error $\sqrtε$. Second, the $d^{Θ(\log n/ε)}$ samples required to estimate the Markov model for an observation alphabet of size $d$ is necessary for any computationally tractable learning algorithm, assuming the hardness of strongly refuting a certain class of CSPs.
Incorporating Quotation and Evaluation Into Church's Type Theory
Venue: arXiv cs.LO 2018
Year: 2018

${\rm CTT}_{\rm qe}$ is a version of Church's type theory that includes quotation and evaluation operators that are similar to quote and eval in the Lisp programming language. With quotation and evaluation it is possible to reason in ${\rm CTT}_{\rm qe}$ about the interplay of the syntax and semantics of expressions and, as a result, to formalize syntax-based mathematical algorithms. We present the syntax and semantics of ${\rm CTT}_{\rm qe}$ as well as a proof system for ${\rm CTT}_{\rm qe}$. The proof system is shown to be sound for all formulas and complete for formulas that do not contain evaluations. We give several examples that illustrate the usefulness of having quotation and evaluation in ${\rm CTT}_{\rm qe}$.
ActionFlowNet: Learning Motion Representation for Action Recognition
Venue: arXiv cs.CV 2018
Year: 2018

Even with the recent advances in convolutional neural networks (CNN) in various visual recognition tasks, the state-of-the-art action recognition system still relies on hand crafted motion feature such as optical flow to achieve the best performance. We propose a multitask learning model ActionFlowNet to train a single stream network directly from raw pixels to jointly estimate optical flow while recognizing actions with convolutional neural networks, capturing both appearance and motion in a single model. We additionally provide insights to how the quality of the learned optical flow affects the action recognition. Our model significantly improves action recognition accuracy by a large margin 31% compared to state-of-the-art CNN-based action recognition models trained without external large scale data and additional optical flow input. Without pretraining on large external labeled datasets, our model, by well exploiting the motion information, achieves competitive recognition accuracy to the models trained with large labeled datasets such as ImageNet and Sport-1M.
Noisy subspace clustering via matching pursuits
Venue: arXiv cs.LG 2018
Year: 2018

Sparsity-based subspace clustering algorithms have attracted significant attention thanks to their excellent performance in practical applications. A prominent example is the sparse subspace clustering (SSC) algorithm by Elhamifar and Vidal, which performs spectral clustering based on an adjacency matrix obtained by sparsely representing each data point in terms of all the other data points via the Lasso. When the number of data points is large or the dimension of the ambient space is high, the computational complexity of SSC quickly becomes prohibitive. Dyer et al. observed that SSC-OMP obtained by replacing the Lasso by the greedy orthogonal matching pursuit (OMP) algorithm results in significantly lower computational complexity, while often yielding comparable performance. The central goal of this paper is an analytical performance characterization of SSC-OMP for noisy data. Moreover, we introduce and analyze the SSC-MP algorithm, which employs matching pursuit (MP) in lieu of OMP. Both SSC-OMP and SSC-MP are proven to succeed even when the subspaces intersect and when the data points are contaminated by severe noise. The clustering conditions we obtain for SSC-OMP and SSC-MP are similar to those for SSC and for the thresholding-based subspace clustering (TSC) algorithm due to Heckel and Bölcskei. Analytical results in combination with numerical results indicate that both SSC-OMP and SSC-MP with a data-dependent stopping criterion automatically detect the dimensions of the subspaces underlying the data. Moreover, experiments on synthetic and on real data show that SSC-MP compares very favorably to SSC, SSC-OMP, TSC, and the nearest subspace neighbor algorithm, both in terms of clustering performance and running time. In addition, we find that, in contrast to SSC-OMP, the performance of SSC-MP is very robust with respect to the choice of parameters in the stopping criteria.
Modelling and Analysis of Quantum Key Distribution Protocols, BB84 and B92, in Communicating Quantum Processes(CQP) language and Analysing in PRISM
Venue: arXiv cs.CR 2018
Year: 2018

Proof of security of cryptographic protocols theoretically establishes the strength of a protocol and the constraints under which it can perform, it does not take into account the overall design of the protocol. In the past model checking has been successfully applied to classical cryptographic protocols to weed out design flaws which would have otherwise gone unnoticed. Quantum cryptographic protocols differ from their classical counterparts, in their ability to detect the presence of an eavesdropper. Although unconditional security has been proven for both BB84 and B92 protocols, in this paper we show that identifying an eavesdropper's presence is constrained on the number of qubits exchanged. We first model the protocols in CQP and then explain the mechanism by which we have translated this into a PRISM model. We mainly focus on the protocols' ability to detect an active eavesdropper and the extent to which an eavesdropper can retrieve the shared key without being detected by either party. We then conclude by comparing the performance of the protocols.
FLSSS: A Novel Algorithmic Framework for Combinatorial Optimization Problems in the Subset Sum Family
Venue: arXiv cs.DS 2018
Year: 2018

This article details the algorithmics in FLSSS, an R package for solving various subset sum problems. The fundamental algorithm engages the problem via combinatorial space compression adaptive to constraints, relaxations and variations that are often crucial for data analytics in practice. Such adaptation conversely enables the compression algorithm to drain every bit of information a sorted superset could bring for rapid convergence. Multidimensional extension follows a novel decomposition of the problem and is friendly to multithreading. Data structures supporting the algorithms have trivial space complexity. The framework offers exact algorithms for the multidimensional knapsack problem and the generalized assignment problem.
Cost Efficiency Optimization of 5G Wireless Backhaul Networks
Venue: arXiv cs.NI 2018
Year: 2018

The wireless backhaul network provides an attractive solution for the urban deployment of fifth generation (5G) wireless networks that enables future ultra dense small cell networks to meet the ever-increasing user demands. Optimal deployment and management of 5G wireless backhaul networks is an interesting and challenging issue. In this paper we propose the optimal gateways deployment and wireless backhaul route schemes to maximize the cost efficiency of 5G wireless backhaul networks. In generally, the changes of gateways deployment and wireless backhaul route are presented in different time scales. Specifically, the number and locations of gateways are optimized in the long time scale of 5G wireless backhaul networks. The wireless backhaul routings are optimized in the short time scale of 5G wireless backhaul networks considering the time-variant over wireless channels. Numerical results show the gateways and wireless backhaul route optimization significantly increases the cost efficiency of 5G wireless backhaul networks. Moreover, the cost efficiency of proposed optimization algorithm is better than that of conventional and most widely used shortest path (SP) and Bellman-Ford (BF) algorithms in 5G wireless backhaul networks.
A coalgebraic treatment of conditional transition systems with upgrades
Venue: arXiv cs.LO 2018
Year: 2018

We consider conditional transition systems, that model software product lines with upgrades, in a coalgebraic setting. By using Birkhoff's duality for distributive lattices, we derive two equivalent Kleisli categories in which these coalgebras live: Kleisli categories based on the reader and on the so-called lattice monad over $\mathsf{Poset}$. We study two different functors describing the branching type of the coalgebra and investigate the resulting behavioural equivalence. Furthermore we show how an existing algorithm for coalgebra minimisation can be instantiated to derive behavioural equivalences in this setting.
Maximum Matching on Trees in the Online Preemptive and the Incremental Dynamic Graph Models
Venue: arXiv cs.DS 2018
Year: 2018

We study the Maximum Cardinality Matching (MCM) and the Maximum Weight Matching (MWM) problems, on trees and on some special classes of graphs, in the Online Preemptive and the Incremental Dynamic Graph models. In the {\em Online Preemptive} model, the edges of a graph are revealed one by one and the algorithm is required to always maintain a valid matching. On seeing an edge, the algorithm has to either accept or reject the edge. If accepted, then the adjacent edges are discarded, and all rejections are permanent. In this model, the complexity of the problems is settled for deterministic algorithms. Epstein et al. gave a $5.356$-competitive randomized algorithm for MWM, and also proved a lower bound of $1.693$ for MCM. The same lower bound applies for MWM. In this paper we show that some of the results can be improved in the case of trees and some special classes of graphs. In the online preemptive model, we present a $64/33$-competitive (in expectation) randomized algorithm for MCM on trees. Inspired by the above mentioned algorithm for MCM, we present the main result of the paper, a randomized algorithm for MCM with a "worst case" update time of $O(1)$, in the incremental dynamic graph model, which is $3/2$-approximate (in expectation) on trees, and $1.8$-approximate (in expectation) on general graphs with maximum degree $3$. Note that this algorithm works only against an oblivious adversary. Hence, we derandomize this algorithm, and give a $(3/2 + ε)$-approximate deterministic algorithm for MCM on trees, with an amortized update time of $O(1/ε)$. We also present a minor result for MWM in the online preemptive model, a $3$-competitive (in expectation) randomized algorithm on growing trees (where the input revealed upto any stage is always a tree, i.e. a new edge never connects two disconnected trees).
PAM: Parallel Augmented Maps
Venue: arXiv cs.DS 2018
Year: 2018

Ordered (key-value) maps are an important and widely-used data type for large-scale data processing frameworks. Beyond simple search, insertion and deletion, more advanced operations such as range extraction, filtering, and bulk updates form a critical part of these frameworks. We describe an interface for ordered maps that is augmented to support fast range queries and sums, and introduce a parallel and concurrent library called PAM (Parallel Augmented Maps) that implements the interface. The interface includes a wide variety of functions on augmented maps ranging from basic insertion and deletion to more interesting functions such as union, intersection, filtering, extracting ranges, splitting, and range-sums. We describe algorithms for these functions that are efficient both in theory and practice. As examples of the use of the interface and the performance of PAM, we apply the library to four applications: simple range sums, interval trees, 2D range trees, and ranked word index searching. The interface greatly simplifies the implementation of these data structures over direct implementations. Sequentially the code achieves performance that matches or exceeds existing libraries designed specially for a single application, and in parallel our implementation gets speedups ranging from 40 to 90 on 72 cores with 2-way hyperthreading.
High Performance Software in Multidimensional Reduction Methods for Image Processing with Application to Ancient Manuscripts
Venue: arXiv cs.CV 2018
Year: 2018

Multispectral imaging is an important technique for improving the readability of written or printed text where the letters have faded, either due to deliberate erasing or simply due to the ravages of time. Often the text can be read simply by looking at individual wavelengths, but in some cases the images need further enhancement to maximise the chances of reading the text. There are many possible enhancement techniques and this paper assesses and compares an extended set of dimensionality reduction methods for image processing. We assess 15 dimensionality reduction methods in two different manuscripts. This assessment was performed both subjectively by asking the opinions of scholars who were experts in the languages used in the manuscripts which of the techniques they preferred and also by using the Davies-Bouldin and Dunn indexes for assessing the quality of the resulted image clusters. We found that the Canonical Variates Analysis (CVA) method which was using a Matlab implementation and we have used previously to enhance multispectral images, it was indeed superior to all the other tested methods. However it is very likely that other approaches will be more suitable in specific circumstance so we would still recommend that a range of these techniques are tried. In particular, CVA is a supervised clustering technique so it requires considerably more user time and effort than a non-supervised technique such as the much more commonly used Principle Component Analysis Approach (PCA). If the results from PCA are adequate to allow a text to be read then the added effort required for CVA may not be justified. For the purposes of comparing the computational times and the image results, a CVA method is also implemented in C programming language and using the GNU (GNUs Not Unix) Scientific Library (GSL) and the OpenCV (OPEN source Computer Vision) computer vision programming library.
A Survey of Deep Network Solutions for Learning Control in Robotics: From Reinforcement to Imitation
Venue: arXiv cs.RO 2018
Year: 2018

Deep learning techniques have been widely applied, achieving state-of-the-art results in various fields of study. This survey focuses on deep learning solutions that target learning control policies for robotics applications. We carry out our discussions on the two main paradigms for learning control with deep networks: deep reinforcement learning and imitation learning. For deep reinforcement learning (DRL), we begin from traditional reinforcement learning algorithms, showing how they are extended to the deep context and effective mechanisms that could be added on top of the DRL algorithms. We then introduce representative works that utilize DRL to solve navigation and manipulation tasks in robotics. We continue our discussion on methods addressing the challenge of the reality gap for transferring DRL policies trained in simulation to real-world scenarios, and summarize robotics simulation platforms for conducting DRL research. For imitation leaning, we go through its three main categories, behavior cloning, inverse reinforcement learning and generative adversarial imitation learning, by introducing their formulations and their corresponding robotics applications. Finally, we discuss the open challenges and research frontiers.
Information-Directed Random Walk for Rare Event Detection in Hierarchical Processes
Venue: arXiv cs.IT 2018
Year: 2018

The problem of detecting a few anomalous processes among a large number of data streams is considered. At each time, aggregated observations can be taken from a chosen subset of the processes, where the chosen subset conforms to a given tree structure. The random observations are drawn from a general distribution that may depend on the size of the chosen subset and the number of anomalous processes in the subset. We propose a sequential search strategy by devising an information-directed random walk (IRW) on the tree-structured observation hierarchy. Subject to a reliability constraint, the proposed policy is shown to be asymptotically optimal with respect to the detection accuracy. Furthermore, it achieves the optimal logarithmic-order sample complexity with respect to the size of the search space provided that the Kullback-Leibler divergence between aggregated observations in the presence and the absence of anomalous processes are bounded away from zero at all levels of the tree structure as the size of the search space approaches infinity. Sufficient conditions on the decaying rate of the aggregated observations to pure noise under which a sublinear scaling in the size of the search space is preserved are also identified for the Bernoulli case.
Patent Retrieval: A Literature Review
Venue: arXiv cs.IR 2018
Year: 2018

With the ever increasing number of filed patent applications every year, the need for effective and efficient systems for managing such tremendous amounts of data becomes inevitably important. Patent Retrieval (PR) is considered the pillar of almost all patent analysis tasks. PR is a subfield of Information Retrieval (IR) which is concerned with developing techniques and methods that effectively and efficiently retrieve relevant patent documents in response to a given search request. In this paper we present a comprehensive review on PR methods and approaches. It is clear that, recent successes and maturity in IR applications such as Web search cannot be transferred directly to PR without deliberate domain adaptation and customization. Furthermore, state-of-the-art performance in automatic PR is still around average in terms of recall. These observations motivate the need for interactive search tools which provide cognitive assistance to patent professionals with minimal effort. These tools must also be developed in hand with patent professionals considering their practices and expectations. We additionally touch on related tasks to PR such as patent valuation, litigation, licensing, and highlight potential opportunities and open directions for computational scientists in these domains.
Towards Faithful Graph Visualizations
Venue: arXiv cs.CG 2018
Year: 2018

Readability criteria have been addressed as a measurement of the quality of graph visualizations. In this paper, we argue that readability criteria are necessary but not sufficient. We propose a new kind of criteria, namely faithfulness, to evaluate the quality of graph layouts. We introduce a general model for quantify faithfulness, and contrast it with the well established readability criteria. We show examples of common visualization techniques, such as multidimensional scaling, edge bundling and several other visualization metaphors for the study of faithfulness.
SalGAN: Visual Saliency Prediction with Generative Adversarial Networks
Venue: arXiv cs.CV 2018
Year: 2018

We introduce SalGAN, a deep convolutional neural network for visual saliency prediction trained with adversarial examples. The first stage of the network consists of a generator model whose weights are learned by back-propagation computed from a binary cross entropy (BCE) loss over downsampled versions of the saliency maps. The resulting prediction is processed by a discriminator network trained to solve a binary classification task between the saliency maps generated by the generative stage and the ground truth ones. Our experiments show how adversarial training allows reaching state-of-the-art performance across different metrics when combined with a widely-used loss function like BCE. Our results can be reproduced with the source code and trained models available at https://imatge-upc.github.io/saliency-salgan-2017/.