OpenRaiser/Intern-Atlas huggingface dataset:
Throughput Region of Spatially Correlated Interference Packet Networks
Venue: arXiv cs.IT 2018
Year: 2018

In multi-user wireless packet networks interference, typically modeled as packet collision, is the throughput bottleneck. Users become aware of the interference pattern via feedback and use this information for contention resolution and for packet retransmission. Conventional random access protocols interrupt communication to resolve contention which reduces network throughput and increases latency and power consumption. In this work we take a different approach and we develop opportunistic random access protocols rather than pursuing conventional methods. We allow wireless nodes to communicate without interruption and to observe the interference pattern. We then use this interference pattern knowledge and channel statistics to counter the negative impact of interference. We prove the optimality of our protocols using an extremal rank-ratio inequality. An important part of our contributions is the integration of spatial correlation in our assumptions and results. We identify spatial correlation regimes in which inherently outdated feedback becomes as good as idealized instantaneous feedback, and correlation regimes in which feedback does not provide any throughput gain. To better illustrate the results, and as an intermediate step, we characterize the capacity region of finite-field spatially correlated interference channels with delayed channel state information at the transmitters.
Short-Packet Downlink Transmission with Non-Orthogonal Multiple Access
Venue: arXiv cs.IT 2018
Year: 2018

This work introduces downlink non-orthogonal multiple access (NOMA) into short-packet communications. NOMA has great potential to improve fairness and spectral efficiency with respect to orthogonal multiple access (OMA) for low-latency downlink transmission, thus making it attractive for the emerging Internet of Things. We consider a two-user downlink NOMA system with finite blocklength constraints, in which the transmission rates and power allocation are optimized. To this end, we investigate the trade-off among the transmission rate, decoding error probability, and the transmission latency measured in blocklength. Then, a one-dimensional search algorithm is proposed to resolve the challenges mainly due to the achievable rate affected by the finite blocklength and the unguaranteed successive interference cancellation. We also analyze the performance of OMA as a benchmark to fully demonstrate the benefit of NOMA. Our simulation results show that NOMA significantly outperforms OMA in terms of achieving a higher effective throughput subject to the same finite blocklength constraint, or incurring a lower latency to achieve the same effective throughput target. Interestingly, we further find that with the finite blocklength, the advantage of NOMA relative to OMA is more prominent when the effective throughput targets at the two users become more comparable.
Dynamic texture recognition using time-causal and time-recursive spatio-temporal receptive fields
Venue: arXiv cs.CV 2018
Year: 2018

This work presents a first evaluation of using spatio-temporal receptive fields from a recently proposed time-causal spatio-temporal scale-space framework as primitives for video analysis. We propose a new family of video descriptors based on regional statistics of spatio-temporal receptive field responses and evaluate this approach on the problem of dynamic texture recognition. Our approach generalises a previously used method, based on joint histograms of receptive field responses, from the spatial to the spatio-temporal domain and from object recognition to dynamic texture recognition. The time-recursive formulation enables computationally efficient time-causal recognition. The experimental evaluation demonstrates competitive performance compared to state-of-the-art. Especially, it is shown that binary versions of our dynamic texture descriptors achieve improved performance compared to a large range of similar methods using different primitives either handcrafted or learned from data. Further, our qualitative and quantitative investigation into parameter choices and the use of different sets of receptive fields highlights the robustness and flexibility of our approach. Together, these results support the descriptive power of this family of time-causal spatio-temporal receptive fields, validate our approach for dynamic texture recognition and point towards the possibility of designing a range of video analysis methods based on these new time-causal spatio-temporal primitives.
BKTreebank: Building a Vietnamese Dependency Treebank
Venue: arXiv cs.CL 2018
Year: 2018

Dependency treebank is an important resource in any language. In this paper, we present our work on building BKTreebank, a dependency treebank for Vietnamese. Important points on designing POS tagset, dependency relations, and annotation guidelines are discussed. We describe experiments on POS tagging and dependency parsing on the treebank. Experimental results show that the treebank is a useful resource for Vietnamese language processing.
Discriminative Learning of Prediction Intervals
Venue: arXiv cs.LG 2018
Year: 2018

In this work we consider the task of constructing prediction intervals in an inductive batch setting. We present a discriminative learning framework which optimizes the expected error rate under a budget constraint on the interval sizes. Most current methods for constructing prediction intervals offer guarantees for a single new test point. Applying these methods to multiple test points can result in a high computational overhead and degraded statistical guarantees. By focusing on expected errors, our method allows for variability in the per-example conditional error rates. As we demonstrate both analytically and empirically, this flexibility can increase the overall accuracy, or alternatively, reduce the average interval size. While the problem we consider is of a regressive flavor, the loss we use is combinatorial. This allows us to provide PAC-style, finite-sample guarantees. Computationally, we show that our original objective is NP-hard, and suggest a tractable convex surrogate. We conclude with a series of experimental evaluations.
Stochastic Variance Reduction for Policy Gradient Estimation
Venue: arXiv cs.LG 2018
Year: 2018

Recent advances in policy gradient methods and deep learning have demonstrated their applicability for complex reinforcement learning problems. However, the variance of the performance gradient estimates obtained from the simulation is often excessive, leading to poor sample efficiency. In this paper, we apply the stochastic variance reduced gradient descent (SVRG) to model-free policy gradient to significantly improve the sample-efficiency. The SVRG estimation is incorporated into a trust-region Newton conjugate gradient framework for the policy optimization. On several Mujoco tasks, our method achieves significantly better performance compared to the state-of-the-art model-free policy gradient methods in robotic continuous control such as trust region policy optimization (TRPO)
EffectiveSan: Type and Memory Error Detection using Dynamically Typed C/C++
Venue: arXiv cs.PL 2018
Year: 2018

Low-level programming languages with weak/static type systems, such as C and C++, are vulnerable to errors relating to the misuse of memory at runtime, such as (sub-)object bounds overflows, (re)use-after-free, and type confusion. Such errors account for many security and other undefined behavior bugs for programs written in these languages. In this paper, we introduce the notion of dynamically typed C/C++, which aims to detect such errors by dynamically checking the "effective type" of each object before use at runtime. We also present an implementation of dynamically typed C/C++ in the form of the Effective Type Sanitizer (EffectiveSan). EffectiveSan enforces type and memory safety using a combination of low-fat pointers, type meta data and type/bounds check instrumentation. We evaluate EffectiveSan against the SPEC2006 benchmark suite and the Firefox web browser, and detect several new type and memory errors. We also show that EffectiveSan achieves high compatibility and reasonable overheads for the given error coverage. Finally, we highlight that EffectiveSan is one of only a few tools that can detect sub-object bounds errors, and uses a novel approach (dynamic type checking) to do so.
Robustly Maximal Utilisation of Energy-Constrained Distributed Resources
Venue: arXiv cs.SY 2018
Year: 2018

We consider the problem of dispatching a fleet of distributed energy reserve devices to collectively meet a sequence of power requests over time. Under the restriction that reserves cannot be replenished, we aim to maximise the survival time of an energy-constrained islanded electrical system; and we discuss realistic scenarios in which this might be the ultimate goal of the grid operator. We present a policy that achieves this optimality, and generalise this into a set-theoretic result that implies there is no better policy available, regardless of the realised energy requirement scenario.
Constructing Datasets for Multi-hop Reading Comprehension Across Documents
Venue: arXiv cs.CL 2018
Year: 2018

Most Reading Comprehension methods limit themselves to queries which can be answered using a single sentence, paragraph, or document. Enabling models to combine disjoint pieces of textual evidence would extend the scope of machine comprehension methods, but currently there exist no resources to train and test this capability. We propose a novel task to encourage the development of models for text understanding across multiple documents and to investigate the limits of existing methods. In our task, a model learns to seek and combine evidence - effectively performing multi-hop (alias multi-step) inference. We devise a methodology to produce datasets for this task, given a collection of query-answer pairs and thematically linked documents. Two datasets from different domains are induced, and we identify potential pitfalls and devise circumvention strategies. We evaluate two previously proposed competitive models and find that one can integrate information across documents. However, both models struggle to select relevant information, as providing documents guaranteed to be relevant greatly improves their performance. While the models outperform several strong baselines, their best accuracy reaches 42.9% compared to human performance at 74.0% - leaving ample room for improvement.
A recognition algorithm for simple-triangle graphs
Venue: arXiv cs.DM 2018
Year: 2018

A simple-triangle graph is the intersection graph of triangles that are defined by a point on a horizontal line and an interval on another horizontal line. The time complexity of the recognition problem for simple-triangle graphs was a longstanding open problem, which was recently settled. This paper provides a new recognition algorithm for simple-triangle graphs to improve the time bound from $O(n^2 \overline{m})$ to $O(nm)$, where $n$, $m$, and $\overline{m}$ are the number of vertices, edges, and non-edges of the graph, respectively. The algorithm uses the vertex ordering characterization that a graph is a simple-triangle graph if and only if there is a linear ordering of the vertices containing both an alternating orientation of the graph and a transitive orientation of the complement of the graph. We also show, as a byproduct, that an alternating orientation can be obtained in $O(nm)$ time for cocomparability graphs, and it is NP-complete to decide whether a graph has an orientation that is alternating and acyclic.
Replacement AutoEncoder: A Privacy-Preserving Algorithm for Sensory Data Analysis
Venue: arXiv cs.LG 2018
Year: 2018

An increasing number of sensors on mobile, Internet of things (IoT), and wearable devices generate time-series measurements of physical activities. Though access to the sensory data is critical to the success of many beneficial applications such as health monitoring or activity recognition, a wide range of potentially sensitive information about the individuals can also be discovered through access to sensory data and this cannot easily be protected using traditional privacy approaches. In this paper, we propose a privacy-preserving sensing framework for managing access to time-series data in order to provide utility while protecting individuals' privacy. We introduce Replacement AutoEncoder, a novel algorithm which learns how to transform discriminative features of data that correspond to sensitive inferences, into some features that have been more observed in non-sensitive inferences, to protect users' privacy. This efficiency is achieved by defining a user-customized objective function for deep autoencoders. Our replacement method will not only eliminate the possibility of recognizing sensitive inferences, it also eliminates the possibility of detecting the occurrence of them. That is the main weakness of other approaches such as filtering or randomization. We evaluate the efficacy of the algorithm with an activity recognition task in a multi-sensing environment using extensive experiments on three benchmark datasets. We show that it can retain the recognition accuracy of state-of-the-art techniques while simultaneously preserving the privacy of sensitive information. Finally, we utilize the GANs for detecting the occurrence of replacement, after releasing data, and show that this can be done only if the adversarial network is trained on the users' original data.
Games on graphs with a public signal monitoring
Venue: arXiv cs.GT 2018
Year: 2018

We study pure Nash equilibria in games on graphs with an imperfect monitoring based on a public signal. In such games, deviations and players responsible for those deviations can be hard to detect and track. We propose a generic epistemic game abstraction, which conveniently allows to represent the knowledge of the players about these deviations, and give a characterization of Nash equilibria in terms of winning strategies in the abstraction. We then use the abstraction to develop algorithms for some payoff functions.
The Importance of System-Level Information in Multiagent Systems Design: Cardinality and Covering Problems
Venue: arXiv cs.GT 2018
Year: 2018

A fundamental challenge in multiagent systems is to design local control algorithms to ensure a desirable collective behaviour. The information available to the agents, gathered either through communication or sensing, naturally restricts the achievable performance. Hence, it is fundamental to identify what piece of information is valuable and can be exploited to design control laws with enhanced performance guarantees. This paper studies the case when such information is uncertain or inaccessible for a class of submodular resource allocation problems termed covering problems. In the first part of this work we pinpoint a fundamental risk-reward tradeoff faced by the system operator when conditioning the control design on a valuable but uncertain piece of information, which we refer to as the cardinality, that represents the maximum number of agents that can simultaneously select any given resource. Building on this analysis, we propose a distributed algorithm that allows agents to learn the cardinality while adjusting their behaviour over time. This algorithm is proved to perform on par or better to the optimal design obtained when the exact cardinality is known a priori.
MR to X-Ray Projection Image Synthesis
Venue: arXiv cs.CV 2018
Year: 2018

Hybrid imaging promises large potential in medical imaging applications. To fully utilize the possibilities of corresponding information from different modalities, the information must be transferable between the domains. In radiation therapy planning, existing methods make use of reconstructed 3D magnetic resonance imaging data to synthesize corresponding X-ray attenuation maps. In contrast, for fluoroscopic procedures only line integral data, i.e., 2D projection images, are present. The question arises which approaches could potentially be used for this MR to X-ray projection image-to-image translation. We examine three network architectures and two loss-functions regarding their suitability as generator networks for this task. All generators proved to yield suitable results for this task. A cascaded refinement network paired with a perceptual-loss function achieved the best qualitative results in our evaluation. The perceptual-loss showed to be able to preserve most of the high-frequency details in the projection images and, thus, is recommended for the underlying task and similar problems.
An impure solution to the problem of matching fans
Venue: arXiv cs.LO 2018
Year: 2018

We propose an algorithm to solve the problem of matching fans in interaction net implementations of optimal reduction for the pure untyped lambda calculus without use of any additional agent types. The algorithm relies upon a specific interaction nets reduction strategy and involves side effects in one of interaction rules.
Optimal Placement and Patrolling of Autonomous Vehicles in Visibility-Based Robot Networks
Venue: arXiv cs.RO 2018
Year: 2018

In communication-denied or contested environments, Line-of-Sight (LoS) communication (e.g free space optical communication using infrared or visible light) becomes one of the most reliable and efficient ways to send information between geographically scattered mobile units. In this paper, we consider the problem of planning optimal locations and trajectories for a group of autonomous vehicles to see a set of units that are dispersed in an environment with obstacles. The contributions of the paper are the following: 1) We propose centralized and distributed algorithms to verify that the vehicles and units form a connected network through LoS; 2) We present an algorithm that can maintain visibility-based connectivity, if possible, by relocating a single vehicle; and 3) We study the computational
The Complexity of Graph-Based Reductions for Reachability in Markov Decision Processes
Venue: arXiv cs.LO 2018
Year: 2018

We study the never-worse relation (NWR) for Markov decision processes with an infinite-horizon reachability objective. A state q is never worse than a state p if the maximal probability of reaching the target set of states from p is at most the same value from q, regard- less of the probabilities labelling the transitions. Extremal-probability states, end components, and essential states are all special cases of the equivalence relation induced by the NWR. Using the NWR, states in the same equivalence class can be collapsed. Then, actions leading to sub- optimal states can be removed. We show the natural decision problem associated to computing the NWR is coNP-complete. Finally, we ex- tend a previously known incomplete polynomial-time iterative algorithm to under-approximate the NWR.
Survey of Machine Learning Techniques for Malware Analysis
Venue: arXiv cs.CR 2018
Year: 2018

Coping with malware is getting more and more challenging, given their relentless growth in complexity and volume. One of the most common approaches in literature is using machine learning techniques, to automatically learn models and patterns behind such complexity, and to develop technologies to keep pace with malware evolution. This survey aims at providing an overview on the way machine learning has been used so far in the context of malware analysis in Windows environments, i.e. for the analysis of Portable Executables. We systematize surveyed papers according to their objectives (i.e., the expected output), what information about malware they specifically use (i.e., the features), and what machine learning techniques they employ (i.e., what algorithm is used to process the input and produce the output). We also outline a number of issues and challenges, including those concerning the used datasets, and identify the main current topical trends and how to possibly advance them. In particular, we introduce the novel concept of malware analysis economics, regarding the study of existing trade-offs among key metrics, such as analysis accuracy and economical costs.
Parametric channel estimation for massive MIMO
Venue: arXiv cs.IT 2018
Year: 2018

Channel state information is crucial to achieving the capacity of multi-antenna (MIMO) wireless communication systems. It requires estimating the channel matrix. This estimation task is studied, considering a sparse channel model particularly suited to millimeter wave propagation, as well as a general measurement model taking into account hybrid architectures. The contribution is twofold. First, the Cram{é}r-Rao bound in this context is derived. Second, interpretation of the Fisher Information Matrix structure allows to assess the role of system parameters, as well as to propose asymptotically optimal and computationally efficient estimation algorithms.
The ETH-MAV Team in the MBZ International Robotics Challenge
Venue: arXiv cs.RO 2018
Year: 2018

This article describes the hardware and software systems of the Micro Aerial Vehicle (MAV) platforms used by the ETH Zurich team in the 2017 Mohamed Bin Zayed International Robotics Challenge (MBZIRC). The aim was to develop robust outdoor platforms with the autonomous capabilities required for the competition, by applying and integrating knowledge from various fields, including computer vision, sensor fusion, optimal control, and probabilistic robotics. This paper presents the major components and structures of the system architectures, and reports on experimental findings for the MAV-based challenges in the competition. Main highlights include securing second place both in the individual search, pick, and place task of Challenge 3 and the Grand Challenge, with autonomous landing executed in less than one minute and a visual servoing success rate of over 90% for object pickups.
Permutation Games for the Weakly Aconjunctive $μ$-Calculus
Venue: arXiv cs.LO 2018
Year: 2018

We introduce a natural notion of limit-deterministic parity automata and present a method that uses such automata to construct satisfiability games for the weakly aconjunctive fragment of the $μ$-calculus. To this end we devise a method that determinizes limit-deterministic parity automata of size $n$ with $k$ priorities through limit-deterministic Büchi automata to deterministic parity automata of size $\mathcal{O}((nk)!)$ and with $\mathcal{O}(nk)$ priorities. The construction relies on limit-determinism to avoid the full complexity of the Safra/Piterman-construction by using partial permutations of states in place of Safra-Trees. By showing that limit-deterministic parity automata can be used to recognize unsuccessful branches in pre-tableaux for the weakly aconjunctive $μ$-calculus, we obtain satisfiability games of size $\mathcal{O}((nk)!)$ with $\mathcal{O}(nk)$ priorities for weakly aconjunctive input formulas of size $n$ and alternation-depth $k$. A prototypical implementation that employs a tableau-based global caching algorithm to solve these games on-the-fly shows promising initial results.
Trace norm regularization and faster inference for embedded speech recognition RNNs
Venue: arXiv cs.LG 2018
Year: 2018

We propose and evaluate new techniques for compressing and speeding up dense matrix multiplications as found in the fully connected and recurrent layers of neural networks for embedded large vocabulary continuous speech recognition (LVCSR). For compression, we introduce and study a trace norm regularization technique for training low rank factored versions of matrix multiplications. Compared to standard low rank training, we show that our method leads to good accuracy versus number of parameter trade-offs and can be used to speed up training of large models. For speedup, we enable faster inference on ARM processors through new open sourced kernels optimized for small batch sizes, resulting in 3x to 7x speed ups over the widely used gemmlowp library. Beyond LVCSR, we expect our techniques and kernels to be more generally applicable to embedded neural networks with large fully connected or recurrent layers.