OpenRaiser/Intern-Atlas huggingface dataset:
Exponential Strong Converse for Successive Refinement with Causal Decoder Side Information
Venue: arXiv cs.IT 2019
Year: 2019

We consider the $k$-user successive refinement problem with causal decoder side information and derive an exponential strong converse theorem. The rate-distortion region for the problem can be derived as a straightforward extension of the two-user case by Maor and Merhav (2008). We show that for any rate-distortion tuple outside the rate-distortion region of the $k$-user successive refinement problem with causal decoder side information, the joint excess-distortion probability approaches one exponentially fast. Our proof follows by judiciously adapting the recently proposed strong converse technique by Oohama using the information spectrum method, the variational form of the rate-distortion region and Hölder's inequality. The lossy source coding problem with causal decoder side information considered by El Gamal and Weissman is a special case ($k=1$) of the current problem. Therefore, the exponential strong converse theorem for the El Gamal and Weissman problem follows as a corollary of our result.
Maximum Matchings and Minimum Blocking Sets in $Θ_6$-Graphs
Venue: arXiv cs.CG 2019
Year: 2019

$Θ_6$-Graphs graphs are important geometric graphs that have many applications especially in wireless sensor networks. They are equivalent to Delaunay graphs where empty equilateral triangles take the place of empty circles. We investigate lower bounds on the size of maximum matchings in these graphs. The best known lower bound is $n/3$, where $n$ is the number of vertices of the graph. Babu et al. (2014) conjectured that any $Θ_6$-graph has a (near-)perfect matching (as is true for standard Delaunay graphs). Although this conjecture remains open, we improve the lower bound to $(3n-8)/7$. We also relate the size of maximum matchings in $Θ_6$-graphs to the minimum size of a blocking set. Every edge of a $Θ_6$-graph on point set $P$ corresponds to an empty triangle that contains the endpoints of the edge but no other point of $P$. A blocking set has at least one point in each such triangle. We prove that the size of a maximum matching is at least $β(n)/2$ where $β(n)$ is the minimum, over all theta-six graphs with $n$ vertices, of the minimum size of a blocking set. In the other direction, lower bounds on matchings can be used to prove bounds on $β$, allowing us to show that $β(n)\geq 3n/4-2$.
What Should I Do Now? Marrying Reinforcement Learning and Symbolic Planning
Venue: arXiv cs.CV 2019
Year: 2019

Long-term planning poses a major difficulty to many reinforcement learning algorithms. This problem becomes even more pronounced in dynamic visual environments. In this work we propose Hierarchical Planning and Reinforcement Learning (HIP-RL), a method for merging the benefits and capabilities of Symbolic Planning with the learning abilities of Deep Reinforcement Learning. We apply HIPRL to the complex visual tasks of interactive question answering and visual semantic planning and achieve state-of-the-art results on three challenging datasets all while taking fewer steps at test time and training in fewer iterations. Sample results can be found at youtu.be/0TtWJ_0mPfI
Path Computation for Provisioning in Multi-Technology Multi-Layer Transport Networks
Venue: arXiv cs.NI 2019
Year: 2019

Service providers employ different transport technologies like PDH, SDH/SONET, OTN, DWDM, Ethernet, MPLS-TP etc. to support different types of traffic and service requirements. Dynamic service provisioning requires the use of on-line algorithms that automatically compute the path to be taken to satisfy the given service request. A typical transport network element supports adaptation of multiple technologies and multiple layers of those technologies to carry the input traffic. Further, transport networks are deployed such that they follow different topologies like linear, ring, mesh, protected linear, dual homing etc. in different layers. Path computation for service requests considering the above factors is the focus of this work, where a new mechanism for building an auxiliary graph which models each layer as a node within each network element and creates adaptation edges between them and also supports creation of special edges to represent different types of topologies is proposed. Logical links that represent multiplexing or adaptation are also created in the auxiliary graph. Initial weight assignment scheme for non-adaptation edges that consider both link distance and link capacity is proposed and three dynamic weight assignment functions that consider the current utilization of the links are proposed. Path computation algorithms considering adaptation and topologies are proposed over the auxiliary graph structure. The performance of the algorithms is evaluated and it is found that the weighted number of requests accepted is higher and the weighted capacity provisioned is lesser for one of the dynamic weight function and certain combination of values proposed as part of the weight assignment.
An online supervised learning algorithm based on triple spikes for spiking neural networks
Venue: arXiv cs.NE 2019
Year: 2019

Using precise times of every spike, spiking supervised learning has more effects on complex spatial-temporal pattern than supervised learning only through neuronal firing rates. The purpose of spiking supervised learning after spatial-temporal encoding is to emit desired spike trains with precise times. Existing algorithms of spiking supervised learning have excellent performances, but mechanisms of them still have some problems, such as the limitation of neuronal types and complex computation. Based on an online regulative mechanism of biological synapses, this paper proposes an online supervised learning algorithm of multiple spike trains for spiking neural networks. The proposed algorithm with a spatial-temporal transformation can make a simple direct regulation of synaptic weights as soon as firing time of an output spike is obtained. Besides, it is also not restricted by types of spiking neuron models. Relationship among desired output, actual output and input spike trains is firstly analyzed and synthesized to simply select a unit of pair-spike for a direct regulation. And then a computational method is constructed based on simple triple spikes using this direct regulation. Compared with other learning algorithms, results of experiments show that proposed algorithm has higher learning accuracy and efficiency.
Improving Unsupervised Word-by-Word Translation with Language Model and Denoising Autoencoder
Venue: arXiv cs.CL 2019
Year: 2019

Unsupervised learning of cross-lingual word embedding offers elegant matching of words across languages, but has fundamental limitations in translating sentences. In this paper, we propose simple yet effective methods to improve word-by-word translation of cross-lingual embeddings, using only monolingual corpora but without any back-translation. We integrate a language model for context-aware search, and use a novel denoising autoencoder to handle reordering. Our system surpasses state-of-the-art unsupervised neural translation systems without costly iterative training. We also analyze the effect of vocabulary size and denoising type on the translation performance, which provides better understanding of learning the cross-lingual word embedding and its usage in translation.
Should I stay or should I go: Analysis of the impact of application QoS on user engagement in YouTube
Venue: arXiv cs.NI 2019
Year: 2019

To improve the quality of experience (QoE), especially under moderate to high traffic demand, it is important to understand the impact of the network and application QoS on user experience. This paper comparatively evaluates the impact of impairments, their intensity and temporal dynamics, on user engagement in the context of video streaming. The analysis employed two large YouTube datasets. To characterize the user engagement and the impact of impairments, several new metrics were defined. We assessed whether or not there is a statistically significant relationship between different types of impairments and QoE and user engagement metrics, taking into account not only the characteristics of the impairments but also the covariates of the session (e.g., video duration, mean datarate). After observing the relationships across the entire dataset, we tested whether these relationships also persist under specific conditions with respect to the covariates. The introduction of several new metrics and of various covariates in the analysis are two innovative aspects of this work. We found that the number of negative bitrate changes (BR-) is a stronger predictor of abandonment than rebufferrings (RB). Even positive bitrate changes (BR+) are associated with increases in abandonment. Specifically, BR+ in low resolution sessions is not well received. Temporal dynamics of the impairments have also an impact: a BR- that follows much later a RB appears to be perceived as a worse impairment than a BR- that occurs immediately after a RB. These results can be used to guide the design of the video streaming adaptation as well as suggest which parameters should be varied in controlled field studies.
Building Atomic, Crash-Consistent Data Stores with Disaggregated Persistent Memory
Venue: arXiv cs.DC 2019
Year: 2019

Byte-addressable persistent memories (PM) has finally made their way into production. An important and pressing problem that follows is how to deploy them in existing datacenters. One viable approach is to attach PM as self-contained devices to the network as disaggregated persistent memory, or DPM. DPM requires no changes to existing servers in datacenters; without the need to include a processor, DPM devices are cheap to build; and by sharing DPM across compute servers, they offer great elasticity and efficient resource packing. This paper explores different ways to organize DPM and to build data stores with DPM. Specifically, we propose three architectures of DPM: 1) compute nodes directly access DPM (DPM-Direct); 2) compute nodes send requests to a coordinator server, which then accesses DPM to complete a request (DPM-Central); and 3) compute nodes directly access DPM for data operations and communicate with a global metadata server for the control plane (DPM-Sep). Based on these architectures, we built three atomic, crash-consistent data stores. We evaluated their performance, scalability, and CPU cost with micro-benchmarks and YCSB. Our evaluation results show that DPM-Direct has great small-size read but poor write performance; DPM-Central has the best write performance when the scale of the cluster is small but performs poorly when the scale increases; and DPM-Sep performs well overall.
Text Mining Customer Reviews For Aspect-based Restaurant Rating
Venue: arXiv cs.CL 2019
Year: 2019

This study applies text mining to analyze customer reviews and automatically assign a collective restaurant star rating based on five predetermined aspects: ambiance, cost, food, hygiene, and service. The application provides a web and mobile crowd sourcing platform where users share dining experiences and get insights about the strengths and weaknesses of a restaurant through user contributed feedback. Text reviews are tokenized into sentences. Noun-adjective pairs are extracted from each sentence using Stanford Core NLP library and are associated to aspects based on the bag of associated words fed into the system. The sentiment weight of the adjectives is determined through AFINN library. An overall restaurant star rating is computed based on the individual aspect rating. Further, a word cloud is generated to provide visual display of the most frequently occurring terms in the reviews. The more feedbacks are added the more reflective the sentiment score to the restaurants' performance.
Post-mortem Iris Recognition with Deep-Learning-based Image Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

This paper proposes the first known to us iris recognition methodology designed specifically for post-mortem samples. We propose to use deep learning-based iris segmentation models to extract highly irregular iris texture areas in post-mortem iris images. We show how to use segmentation masks predicted by neural networks in conventional, Gabor-based iris recognition method, which employs circular approximations of the pupillary and limbic iris boundaries. As a whole, this method allows for a significant improvement in post-mortem iris recognition accuracy over the methods designed only for ante-mortem irises, including the academic OSIRIS and commercial IriCore implementations. The proposed method reaches the EER less than 1% for samples collected up to 10 hours after death, when compared to 16.89% and 5.37% of EER observed for OSIRIS and IriCore, respectively. For samples collected up to 369 hours post-mortem, the proposed method achieves the EER 21.45%, while 33.59% and 25.38% are observed for OSIRIS and IriCore, respectively. Additionally, the method is tested on a database of iris images collected from ophthalmology clinic patients, for which it also offers an advantage over the two other algorithms. This work is the first step towards post-mortem-specific iris recognition, which increases the chances of identification of deceased subjects in forensic investigations. The new database of post-mortem iris images acquired from 42 subjects, as well as the deep learning-based segmentation models are made available along with the paper, to ensure all the results presented in this manuscript are reproducible.
Approximate-Closed-Itemset Mining for Streaming Data Under Resource Constraint
Venue: arXiv cs.DB 2019
Year: 2019

Here, we present a novel algorithm for frequent itemset mining for streaming data (FIM-SD). For the past decade, various FIM-SD methods in one-pass approximation settings have been developed to approximate the frequency of each itemset. These approaches can be categorized into two approximation types: parameter-constrained (PC) mining and resource-constrained (RC) mining. PC methods control the maximum error that can be included in the frequency based on a pre-defined parameter. In contrast, RC methods limit the maximum memory consumption based on resource constraints. However, the existing PC methods can exponentially increase the memory consumption, while the existing RC methods can rapidly increase the maximum error. In this study, we address this problem by introducing the notion of a condensed representation, called a $Δ$-covered set, to the RC approximation. This notion is regarded as an extension of the closedness compression and when $Δ= 0$, the solution corresponds to an ordinary closed itemset. The algorithm searches for such approximate closed itemsets that can restore the frequent itemsets and their frequencies under resource constraint while the maximum error is bounded by an integer, $Δ$. We first propose a one-pass approximation algorithm to find the condensed solution. Then, we improve the basic algorithm by introducing a unified PC-RC approximation approach. Finally, we empirically demonstrate that the proposed algorithm significantly outperforms the state-of-the-art PC and RC methods for FIM-SD.
Double Weighted Truncated Nuclear Norm Regularization for Low-Rank Matrix Completion
Venue: arXiv cs.CV 2019
Year: 2019

Matrix completion focuses on recovering a matrix from a small subset of its observed elements, and has already gained cumulative attention in computer vision. Many previous approaches formulate this issue as a low-rank matrix approximation problem. Recently, a truncated nuclear norm has been presented as a surrogate of traditional nuclear norm, for better estimation to the rank of a matrix. The truncated nuclear norm regularization (TNNR) method is applicable in real-world scenarios. However, it is sensitive to the selection of the number of truncated singular values and requires numerous iterations to converge. Hereby, this paper proposes a revised approach called the double weighted truncated nuclear norm regularization (DW-TNNR), which assigns different weights to the rows and columns of a matrix separately, to accelerate the convergence with acceptable performance. The DW-TNNR is more robust to the number of truncated singular values than the TNNR. Instead of the iterative updating scheme in the second step of TNNR, this paper devises an efficient strategy that uses a gradient descent manner in a concise form, with a theoretical guarantee in optimization. Sufficient experiments conducted on real visual data prove that DW-TNNR has promising performance and holds the superiority in both speed and accuracy for matrix completion.
SWIPT Signalling over Frequency-Selective Channels with a Nonlinear Energy Harvester: Non-Zero Mean and Asymmetric Inputs
Venue: arXiv cs.IT 2019
Year: 2019

Simultaneous Wireless Information and Power Transfer (SWIPT) over a point-to-point frequency-selective Additive White Gaussian Noise (AWGN) channel is studied. Considering an approximation of the nonlinearity of the harvester, a general form of delivered power in terms of system baseband parameters is derived, which demonstrates the dependency of the delivered power on higher order moment of the baseband channel input distribution. The optimization problem of maximizing Rate-Power (RP) region is studied. Assuming that the Channel State Information (CSI) is available at both the receiver and the transmitter, and constraining to non-zero mean Gaussian input distributions, an optimization algorithm for power allocation among different subchannels is studied. As a special case, optimality conditions for zero mean Gaussian inputs are derived. Results obtained from numerical optimization demonstrate the superiority of non-zero mean Gaussian inputs (with asymmetric power allocation in each complex subchannel) in yielding a larger RP region compared to their zero mean and non-zero mean (with symmetric power allocation in each complex subchannel) counterparts. This severely contrasts with SWIPT design under linear energy harvesting, for which circularly symmetric Gaussian inputs are optimal.
D2D Data Offloading in Vehicular Environments with Optimal Delivery Time Selection
Venue: arXiv cs.NI 2019
Year: 2019

Within the framework of a Device-to-Device (D2D) data offloading system for cellular networks, we propose a Content Delivery Management System (CDMS) in which the instant for transmitting a content to a requesting node, through a D2D communication, is selected to minimize the energy consumption required for transmission. The proposed system is particularly fit to highly dynamic scenarios, such as vehicular networks, where the network topology changes at a rate which is comparable with the order of magnitude of the delay tolerance. We present an analytical framework able to predict the system performance, in terms of energy consumption, using tools from the theory of point processes, validating it through simulations, and provide a thorough performance evaluation of the proposed CDMS, in terms of energy consumption and spectrum use. Our performance analysis compares the energy consumption and spectrum use obtained with the proposed scheme with the performance of two benchmark systems. The first one is a plain classic cellular scheme, the second is a D2D data offloading scheme (that we proposed in previous works) in which the D2D transmissions are performed as soon as there is a device with the required content within the maximum D2D transmission range...
Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions
Venue: arXiv cs.NE 2019
Year: 2019

While the history of machine learning so far largely encompasses a series of problems posed by researchers and algorithms that learn their solutions, an important question is whether the problems themselves can be generated by the algorithm at the same time as they are being solved. Such a process would in effect build its own diverse and expanding curricula, and the solutions to problems at various stages would become stepping stones towards solving even more challenging problems later in the process. The Paired Open-Ended Trailblazer (POET) algorithm introduced in this paper does just that: it pairs the generation of environmental challenges and the optimization of agents to solve those challenges. It simultaneously explores many different paths through the space of possible problems and solutions and, critically, allows these stepping-stone solutions to transfer between problems if better, catalyzing innovation. The term open-ended signifies the intriguing potential for algorithms like POET to continue to create novel and increasingly complex capabilities without bound. Our results show that POET produces a diverse range of sophisticated behaviors that solve a wide range of environmental challenges, many of which cannot be solved by direct optimization alone, or even through a direct-path curriculum-building control algorithm introduced to highlight the critical role of open-endedness in solving ambitious challenges. The ability to transfer solutions from one environment to another proves essential to unlocking the full potential of the system as a whole, demonstrating the unpredictable nature of fortuitous stepping stones. We hope that POET will inspire a new push towards open-ended discovery across many domains, where algorithms like POET can blaze a trail through their interesting possible manifestations and solutions.
Extracting Secrets from Encrypted Virtual Machines
Venue: arXiv cs.CR 2019
Year: 2019

AMD SEV is a hardware extension for main memory encryption on multi-tenant systems. SEV uses an on-chip coprocessor, the AMD Secure Processor, to transparently encrypt virtual machine memory with individual, ephemeral keys never leaving the coprocessor. The goal is to protect the confidentiality of the tenants' memory from a malicious or compromised hypervisor and from memory attacks, for instance via cold boot or DMA. The SEVered attack has shown that it is nevertheless possible for a hypervisor to extract memory in plaintext from SEV-encrypted virtual machines without access to their encryption keys. However, the encryption impedes traditional virtual machine introspection techniques from locating secrets in memory prior to extraction. This can require the extraction of large amounts of memory to retrieve specific secrets and thus result in a time-consuming, obvious attack. We present an approach that allows a malicious hypervisor quick identification and theft of secrets, such as TLS, SSH or FDE keys, from encrypted virtual machines on current SEV hardware. We first observe activities of a virtual machine from within the hypervisor in order to infer the memory regions most likely to contain the secrets. Then, we systematically extract those memory regions and analyze their contents on-the-fly. This allows for the efficient retrieval of targeted secrets, strongly increasing the chances of a fast, robust and stealthy theft.
Credit Assignment Techniques in Stochastic Computation Graphs
Venue: arXiv cs.LG 2019
Year: 2019

Stochastic computation graphs (SCGs) provide a formalism to represent structured optimization problems arising in artificial intelligence, including supervised, unsupervised, and reinforcement learning. Previous work has shown that an unbiased estimator of the gradient of the expected loss of SCGs can be derived from a single principle. However, this estimator often has high variance and requires a full model evaluation per data point, making this algorithm costly in large graphs. In this work, we address these problems by generalizing concepts from the reinforcement learning literature. We introduce the concepts of value functions, baselines and critics for arbitrary SCGs, and show how to use them to derive lower-variance gradient estimates from partial model evaluations, paving the way towards general and efficient credit assignment for gradient-based optimization. In doing so, we demonstrate how our results unify recent advances in the probabilistic inference and reinforcement learning literature.