OpenRaiser/Intern-Atlas huggingface dataset:
A Topological Perspective on Distributed Network Algorithms
Venue: arXiv cs.DC 2020
Year: 2020

More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that combinatorial topology can also be useful for analyzing distributed algorithms in failure-free networks of arbitrary structure. To illustrate this, we analyze consensus, set-agreement, and approximate agreement in networks, and derive lower bounds for these problems under classical computational settings, such as the LOCAL model and dynamic networks.
P4-IPsec: Site-to-Site and Host-to-Site VPN with IPsec in P4-Based SDN
Venue: arXiv cs.NI 2020
Year: 2020

In this work, we present P4-IPsec, a concept for IPsec in software-defined networks (SDN) using P4 programmable data planes. The prototype implementation features ESP in tunnel mode and supports different cipher suites. P4-capable switches are programmed to serve as IPsec tunnel endpoints. We also provide a client agent to configure tunnel endpoints on Linux hosts so that site-to-site and host-to-site application scenarios can be supported which are the base for virtual private networks (VPNs). While traditional VPNs require complex key exchange protocols like IKE to set up and renew tunnel endpoints, P4-IPsec benefits from an SDN controller to accomplish these tasks. One goal of this experimental work is to investigate how well P4-IPsec can be implemented on existing P4 switches. We present a prototype for the BMv2 P4 software switch, evaluate its performance, and publish its source code on GitHub. We explain why we could not provide a useful implementation with the NetFPGA SUME board. For the Edgecore Wedge 100BF-32X Tofino-based switch, we presented two prototype implementations to cope with a missing crypto unit. As another contribution of this paper, we provide technological background of P4 and IPsec and give a comprehensive review of security applications in P4, IPsec in SDN, and IPsec data plane implementations. According to our knowledge, P4-IPsec is the first implementation of IPsec for P4-based SDN.
Asymmetric LOCO Codes: Constrained Codes for Flash Memories
Venue: arXiv cs.IT 2020
Year: 2020

In data storage and data transmission, certain patterns are more likely to be subject to error when written (transmitted) onto the media. In magnetic recording systems with binary data and bipolar non-return-to-zero signaling, patterns that have insufficient separation between consecutive transitions exacerbate inter-symbol interference. Constrained codes are used to eliminate such error-prone patterns. A recent example is a new family of capacity-achieving constrained codes, named lexicographically-ordered constrained codes (LOCO codes). LOCO codes are symmetric, that is, the set of forbidden patterns is closed under taking pattern complements. LOCO codes are suboptimal in terms of rate when used in Flash devices where block erasure is employed since the complement of an error-prone pattern is not detrimental in these devices. This paper introduces asymmetric LOCO codes (A-LOCO codes), which are lexicographically-ordered constrained codes that forbid only those patterns that are detrimental for Flash performance. A-LOCO codes are also capacity-achieving, and at finite-lengths, they offer higher rates than the available state-of-the-art constrained codes designed for the same goal. The mapping-demapping between the index and the codeword in A-LOCO codes allows low-complexity encoding and decoding algorithms that are simpler than their LOCO counterparts.
Rehearsal-Free Continual Learning over Small Non-I.I.D. Batches
Venue: arXiv cs.LG 2020
Year: 2020

Robotic vision is a field where continual learning can play a significant role. An embodied agent operating in a complex environment subject to frequent and unpredictable changes is required to learn and adapt continuously. In the context of object recognition, for example, a robot should be able to learn (without forgetting) objects of never before seen classes as well as improving its recognition capabilities as new instances of already known classes are discovered. Ideally, continual learning should be triggered by the availability of short videos of single objects and performed on-line on on-board hardware with fine-grained updates. In this paper, we introduce a novel continual learning protocol based on the CORe50 benchmark and propose two rehearsal-free continual learning techniques, CWR* and AR1*, that can learn effectively even in the challenging case of nearly 400 small non-i.i.d. incremental batches. In particular, our experiments show that AR1* can outperform other state-of-the-art rehearsal-free techniques by more than 15% accuracy in some cases, with a very light and constant computational and memory overhead across training batches.
Adaptive Exploration for Unsupervised Person Re-Identification
Venue: arXiv cs.CV 2020
Year: 2020

Due to domain bias, directly deploying a deep person re-identification (re-ID) model trained on one dataset often achieves considerably poor accuracy on another dataset. In this paper, we propose an Adaptive Exploration (AE) method to address the domain-shift problem for re-ID in an unsupervised manner. Specifically, in the target domain, the re-ID model is inducted to 1) maximize distances between all person images and 2) minimize distances between similar person images. In the first case, by treating each person image as an individual class, a non-parametric classifier with a feature memory is exploited to encourage person images to move far away from each other. In the second case, according to a similarity threshold, our method adaptively selects neighborhoods for each person image in the feature space. By treating these similar person images as the same class, the non-parametric classifier forces them to stay closer. However, a problem of the adaptive selection is that, when an image has too many neighborhoods, it is more likely to attract other images as its neighborhoods. As a result, a minority of images may select a large number of neighborhoods while a majority of images have only a few neighborhoods. To address this issue, we additionally integrate a balance strategy into the adaptive selection. We evaluate our methods with two protocols. The first one is called "target-only re-ID", in which only the unlabeled target data is used for training. The second one is called "domain adaptive re-ID", in which both the source data and the target data are used during training. Experimental results on large-scale re-ID datasets demonstrate the effectiveness of our method. Our code has been released at https://github.com/dyh127/Adaptive-Exploration-for-Unsupervised-Person-Re-Identification.
Neural Reasoning, Fast and Slow, for Video Question Answering
Venue: arXiv cs.CV 2020
Year: 2020

What does it take to design a machine that learns to answer natural questions about a video? A Video QA system must simultaneously understand language, represent visual content over space-time, and iteratively transform these representations in response to lingual content in the query, and finally arriving at a sensible answer. While recent advances in lingual and visual question answering have enabled sophisticated representations and neural reasoning mechanisms, major challenges in Video QA remain on dynamic grounding of concepts, relations and actions to support the reasoning process. Inspired by the dual-process account of human reasoning, we design a dual process neural architecture, which is composed of a question-guided video processing module (System 1, fast and reactive) followed by a generic reasoning module (System 2, slow and deliberative). System 1 is a hierarchical model that encodes visual patterns about objects, actions and relations in space-time given the textual cues from the question. The encoded representation is a set of high-level visual features, which are then passed to System 2. Here multi-step inference follows to iteratively chain visual elements as instructed by the textual elements. The system is evaluated on the SVQA (synthetic) and TGIF-QA datasets (real), demonstrating competitive results, with a large margin in the case of multi-step reasoning.
Polytopes, lattices, and spherical codes for the nearest neighbor problem
Venue: arXiv cs.DS 2020
Year: 2020

We study locality-sensitive hash methods for the nearest neighbor problem for the angular distance, focusing on the approach of first projecting down onto a low-dimensional subspace, and then partitioning the projected vectors according to Voronoi cells induced by a suitable spherical code. This approach generalizes and interpolates between the fast but suboptimal hyperplane hashing of Charikar [STOC'02] and the asymptotically optimal but practically often slower hash families of Andoni-Indyk [FOCS'06], Andoni-Indyk-Nguyen-Razenshteyn [SODA'14] and Andoni-Indyk-Laarhoven-Razenshteyn-Schmidt [NIPS'15]. We set up a framework for analyzing the performance of any spherical code in this context, and we provide results for various codes from the literature, such as those related to regular polytopes and root lattices. Similar to hyperplane hashing, and unlike cross-polytope hashing, our analysis of collision probabilities and query exponents is exact and does not hide order terms which vanish only for large $d$, facilitating an easy parameter selection. For the two-dimensional case, we derive closed-form expressions for arbitrary spherical codes, and we show that the equilateral triangle is optimal, achieving a better performance than the two-dimensional analogues of hyperplane and cross-polytope hashing. In three and four dimensions, we numerically find that the tetrahedron, $5$-cell, and $16$-cell achieve the best query exponents, while in five or more dimensions orthoplices appear to outperform regular simplices, as well as the root lattice families $A_k$ and $D_k$. We argue that in higher dimensions, larger spherical codes will likely exist which will outperform orthoplices in theory, and we argue why using the $D_k$ root lattices will likely lead to better results in practice, due to a better trade-off between the asymptotic query exponent and the concrete costs of hashing.
Santha-Vazirani sources, deterministic condensers and very strong extractors
Venue: arXiv cs.CC 2020
Year: 2020

The notion of semi-random sources, also known as Santha-Vazirani (SV) sources, stands for a sequence of n bits, where the dependence of the i'th bit on the previous i-1 bits is limited for every $i\in[n]$. If the dependence of the i'th bit on the remaining n-1 bits is limited, then this is a strong SV-source. Even the strong SV-sources are known not to admit (universal) deterministic extractors, but they have seeded extractors, as their min-entropy is $Ω(n)$. It is intuitively obvious that strong SV-sources are more than just high-min-entropy sources, and this work explores the intuition. Deterministic condensers are known not to exist for general high-min-entropy sources, and we construct for any constants $ε, δ\in (0,1)$ a deterministic condenser that maps n bits coming from a strong SV-source with bias at most $δ$ to $Ω(n)$ bits of min-entropy rate at least $1-ε$. In conclusion we observe that deterministic condensers are closely related to very strong extractors - a proposed strengthening of the notion of strong (seeded) extractors: in particular, our constructions can be viewed as very strong extractors for the family of strong Santha-Vazirani distributions. The notion of very strong extractors requires that the output remains unpredictable even to someone who knows not only the seed value (as in the case of strong extractors), but also the extractor's outputs corresponding to the same input value with each of the preceding seed values (say, under the lexicographic ordering). Very strong extractors closely resemble the original notion of SV-sources, except that the bits must satisfy the unpredictability requirement only on average.
Hardware/Software Co-Exploration of Neural Architectures
Venue: arXiv cs.LG 2020
Year: 2020

We propose a novel hardware and software co-exploration framework for efficient neural architecture search (NAS). Different from existing hardware-aware NAS which assumes a fixed hardware design and explores the neural architecture search space only, our framework simultaneously explores both the architecture search space and the hardware design space to identify the best neural architecture and hardware pairs that maximize both test accuracy and hardware efficiency. Such a practice greatly opens up the design freedom and pushes forward the Pareto frontier between hardware efficiency and test accuracy for better design tradeoffs. The framework iteratively performs a two-level (fast and slow) exploration. Without lengthy training, the fast exploration can effectively fine-tune hyperparameters and prune inferior architectures in terms of hardware specifications, which significantly accelerates the NAS process. Then, the slow exploration trains candidates on a validation set and updates a controller using the reinforcement learning to maximize the expected accuracy together with the hardware efficiency. Experiments on ImageNet show that our co-exploration NAS can find the neural architectures and associated hardware design with the same accuracy, 35.24% higher throughput, 54.05% higher energy efficiency and 136x reduced search time, compared with the state-of-the-art hardware-aware NAS.
Trace-Relating Compiler Correctness and Secure Compilation
Venue: arXiv cs.PL 2020
Year: 2020

Compiler correctness is, in its simplest form, defined as the inclusion of the set of traces of the compiled program into the set of traces of the original program, which is equivalent to the preservation of all trace properties. Here traces collect, for instance, the externally observable events of each execution. This definition requires, however, the set of traces of the source and target languages to be exactly the same, which is not the case when the languages are far apart or when observations are fine-grained. To overcome this issue, we study a generalized compiler correctness definition, which uses source and target traces drawn from potentially different sets and connected by an arbitrary relation. We set out to understand what guarantees this generalized compiler correctness definition gives us when instantiated with a non-trivial relation on traces. When this trace relation is not equality, it is no longer possible to preserve the trace properties of the source program unchanged. Instead, we provide a generic characterization of the target trace property ensured by correctly compiling a program that satisfies a given source property, and dually, of the source trace property one is required to show in order to obtain a certain target property for the compiled code. We show that this view on compiler correctness can naturally account for undefined behavior, resource exhaustion, different source and target values, side-channels, and various abstraction mismatches. Finally, we show that the same generalization also applies to many secure compilation definitions, which characterize the protection of a compiled program against linked adversarial code.
Learning Functions over Sets via Permutation Adversarial Networks
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we consider the problem of learning functions over sets, i.e., functions that are invariant to permutations of input set items. Recent approaches of pooling individual element embeddings can necessitate extremely large embedding sizes for challenging functions. We address this challenge by allowing standard neural networks like LSTMs to succinctly capture the function over the set. However, to ensure invariance with respect to permutations of set elements, we propose a novel architecture called SPAN that simultaneously learns the function as well as adversarial or worst-case permutations for each input set. The learning problem reduces to a min-max optimization problem that is solved via a simple alternating block coordinate descent technique. We conduct extensive experiments on a variety of set-learning tasks and demonstrate that SPAN learns nearly permutation-invariant functions while still ensuring accuracy on test data. On a variety of tasks sampled from the domains of statistics, graph functions and linear algebra, we show that our method can significantly outperform state-of-the-art methods such as DeepSets and Janossy Pooling. Finally, we present a case study of how learning set-functions can help extract powerful features for recommendation systems, and show that such a method can be as much as 2% more accurate than carefully hand-tuned features on a real-world recommendation system.
VarGNet: Variable Group Convolutional Neural Network for Efficient Embedded Computing
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we propose a novel network design mechanism for efficient embedded computing. Inspired by the limited computing patterns, we propose to fix the number of channels in a group convolution, instead of the existing practice that fixing the total group numbers. Our solution based network, named Variable Group Convolutional Network (VarGNet), can be optimized easier on hardware side, due to the more unified computing schemes among the layers. Extensive experiments on various vision tasks, including classification, detection, pixel-wise parsing and face recognition, have demonstrated the practical value of our VarGNet.
Multi-Task Semi-Supervised Adversarial Autoencoding for Speech Emotion Recognition
Venue: arXiv cs.SD 2020
Year: 2020

Inspite the emerging importance of Speech Emotion Recognition (SER), the state-of-the-art accuracy is quite low and needs improvement to make commercial applications of SER viable. A key underlying reason for the low accuracy is the scarcity of emotion datasets, which is a challenge for developing any robust machine learning model in general. In this paper, we propose a solution to this problem: a multi-task learning framework that uses auxiliary tasks for which data is abundantly available. We show that utilisation of this additional data can improve the primary task of SER for which only limited labelled data is available. In particular, we use gender identifications and speaker recognition as auxiliary tasks, which allow the use of very large datasets, e.g., speaker classification datasets. To maximise the benefit of multi-task learning, we further use an adversarial autoencoder (AAE) within our framework, which has a strong capability to learn powerful and discriminative features. Furthermore, the unsupervised AAE in combination with the supervised classification networks enables semi-supervised learning which incorporates a discriminative component in the AAE unsupervised training pipeline. This semi-supervised learning essentially helps to improve generalisation of our framework and thus leads to improvements in SER performance. The proposed model is rigorously evaluated for categorical and dimensional emotion, and cross-corpus scenarios. Experimental results demonstrate that the proposed model achieves state-of-the-art performance on two publicly available datasets.
Unsupervised Adversarial Domain Adaptation for Cross-Lingual Speech Emotion Recognition
Venue: arXiv cs.SD 2020
Year: 2020

Cross-lingual speech emotion recognition (SER) is a crucial task for many real-world applications. The performance of SER systems is often degraded by the differences in the distributions of training and test data. These differences become more apparent when training and test data belong to different languages, which cause a significant performance gap between the validation and test scores. It is imperative to build more robust models that can fit in practical applications of SER systems. Therefore, in this paper, we propose a Generative Adversarial Network (GAN)-based model for multilingual SER. Our choice of using GAN is motivated by their great success in learning the underlying data distribution. The proposed model is designed in such a way that can learn language invariant representations without requiring target-language data labels. We evaluate our proposed model on four different language emotional datasets, including an Urdu-language dataset to also incorporate alternative languages for which labelled data is difficult to find and which have not been studied much by the mainstream community. Our results show that our proposed model can significantly improve the baseline cross-lingual SER performance for all the considered datasets including the non-mainstream Urdu language data without requiring any labels.
A Linear Systems Theory of Normalizing Flows
Venue: arXiv cs.LG 2020
Year: 2020

Normalizing Flows are a promising new class of algorithms for unsupervised learning based on maximum likelihood optimization with change of variables. They offer to learn a factorized component representation for complex nonlinear data and, simultaneously, yield a density function that can evaluate likelihoods and generate samples. Despite these diverse offerings, applications of Normalizing Flows have focused primarily on sampling and likelihoods, with little emphasis placed on feature representation. A lack of theoretical foundation has left many open questions about how to interpret and apply the learned components of the model. We provide a new theoretical perspective of Normalizing Flows using the lens of linear systems theory, showing that optimal flows learn to represent the local covariance at each region of input space. Using this insight, we develop a new algorithm to extract interpretable component representations from the learned model, where components correspond to Cartesian dimensions and are scaled according to their manifold significance. In addition, we highlight a stability concern for the learning algorithm that was previously unaddressed, providing a theoretically-grounded solution to mediate the problem. Experiments with toy manifold learning datasets, as well as the MNIST image dataset, provide convincing support for our theory and tools.
The Age of Incorrect Information: A New Performance Metric for Status Updates
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we introduce a new performance metric in the framework of status updates that we will refer to as the Age of Incorrect Information (AoII). This new metric deals with the shortcomings of both the Age of Information (AoI) and the conventional error penalty functions as it neatly extends the notion of fresh updates to that of fresh "informative" updates. The word informative in this context refers to updates that bring new and correct information to the monitor side. After properly motivating the new metric, and with the aim of minimizing its average, we formulate a Markov Decision Process (MDP) in a transmitter-receiver pair scenario where packets are sent over an unreliable channel. We show that a simple "always update" policy minimizes the aforementioned average penalty along with the average age and prediction error. We then tackle the general, and more realistic case, where the transmitter cannot surpass a specific power budget. The problem is formulated as a Constrained Markov Decision Process (CMDP) for which we provide a Lagrangian approach to solve. After characterizing the optimal transmission policy of the Lagrangian problem, we provide a rigorous mathematical proof to showcase that a mixture of two Lagrange policies is optimal for the CMDP in question. Equipped with this, we provide a low complexity algorithm that finds the AoII-optimal operating point of the system in the constrained scenario. Lastly, simulation results are laid out to showcase the performance of the proposed policy and highlight the differences with the AoI framework.