OpenRaiser/Intern-Atlas huggingface dataset:
Mass Error-Correction Codes for Polymer-Based Data Storage
Venue: arXiv cs.IT 2020
Year: 2020

We consider the problem of correcting mass readout errors in information encoded in binary polymer strings. Our work builds on results for string reconstruction problems using composition multisets [Acharya et al., 2015] and the unique string reconstruction framework proposed in [Pattabiraman et al., 2019]. Binary polymer-based data storage systems [Laure et al., 2016] operate by designing two molecules of significantly different masses to represent the symbols $\{0,1\}$ and perform readouts through noisy tandem mass spectrometry. Tandem mass spectrometers fragment the strings to be read into shorter substrings and only report their masses, often with errors due to imprecise ionization. Modeling the fragmentation process output in terms of composition multisets allows for designing asymptotically optimal codes capable of unique reconstruction and the correction of a single mass error [Pattabiraman et al., 2019] through the use of derivatives of Catalan paths. Nevertheless, no solutions for multiple-mass error-corrections are currently known. Our work addresses this issue by describing the first multiple-error correction codes that use the polynomial factorization approach for the Turnpike problem [Skiena et al., 1990] and the related factorization described in [Acharya et al., 2015]. Adding Reed-Solomon type coding redundancy into the corresponding polynomials allows for correcting $t$ mass errors in polynomial time using $t^2\, \log\,k$ redundant bits, where $k$ is the information string length. The redundancy can be improved to $\log\,k + t$. However, no decoding algorithm that runs polynomial-time in both $t$ and $n$ for this scheme are currently known, where $n$ is the length of the coded string.
Noisy Machines: Understanding Noisy Neural Networks and Enhancing Robustness to Analog Hardware Errors Using Distillation
Venue: arXiv cs.LG 2020
Year: 2020

The success of deep learning has brought forth a wave of interest in computer hardware design to better meet the high demands of neural network inference. In particular, analog computing hardware has been heavily motivated specifically for accelerating neural networks, based on either electronic, optical or photonic devices, which may well achieve lower power consumption than conventional digital electronics. However, these proposed analog accelerators suffer from the intrinsic noise generated by their physical components, which makes it challenging to achieve high accuracy on deep neural networks. Hence, for successful deployment on analog accelerators, it is essential to be able to train deep neural networks to be robust to random continuous noise in the network weights, which is a somewhat new challenge in machine learning. In this paper, we advance the understanding of noisy neural networks. We outline how a noisy neural network has reduced learning capacity as a result of loss of mutual information between its input and output. To combat this, we propose using knowledge distillation combined with noise injection during training to achieve more noise robust networks, which is demonstrated experimentally across different networks and datasets, including ImageNet. Our method achieves models with as much as two times greater noise tolerance compared with the previous best attempts, which is a significant step towards making analog hardware practical for deep learning.
Neural Arithmetic Units
Venue: arXiv cs.NE 2020
Year: 2020

Neural networks can approximate complex functions, but they struggle to perform exact arithmetic operations over real numbers. The lack of inductive bias for arithmetic operations leaves neural networks without the underlying logic necessary to extrapolate on tasks such as addition, subtraction, and multiplication. We present two new neural network components: the Neural Addition Unit (NAU), which can learn exact addition and subtraction; and the Neural Multiplication Unit (NMU) that can multiply subsets of a vector. The NMU is, to our knowledge, the first arithmetic neural network component that can learn to multiply elements from a vector, when the hidden size is large. The two new components draw inspiration from a theoretical analysis of recently proposed arithmetic components. We find that careful initialization, restricting parameter space, and regularizing for sparsity is important when optimizing the NAU and NMU. Our proposed units NAU and NMU, compared with previous neural units, converge more consistently, have fewer parameters, learn faster, can converge for larger hidden sizes, obtain sparse and meaningful weights, and can extrapolate to negative and small values.
Emerging Disentanglement in Auto-Encoder Based Unsupervised Image Content Transfer
Venue: arXiv cs.CV 2020
Year: 2020

We study the problem of learning to map, in an unsupervised way, between domains A and B, such that the samples b in B contain all the information that exists in samples a in A and some additional information. For example, ignoring occlusions, B can be people with glasses, A people without, and the glasses, would be the added information. When mapping a sample a from the first domain to the other domain, the missing information is replicated from an independent reference sample b in B. Thus, in the above example, we can create, for every person without glasses a version with the glasses observed in any face image. Our solution employs a single two-pathway encoder and a single decoder for both domains. The common part of the two domains and the separate part are encoded as two vectors, and the separate part is fixed at zero for domain A. The loss terms are minimal and involve reconstruction losses for the two domains and a domain confusion term. Our analysis shows that under mild assumptions, this architecture, which is much simpler than the literature guided-translation methods, is enough to ensure disentanglement between the two domains. We present convincing results in a few visual domains, such as no-glasses to glasses, adding facial hair based on a reference image, etc.
Unsupervised Learning of the Set of Local Maxima
Venue: arXiv cs.LG 2020
Year: 2020

This paper describes a new form of unsupervised learning, whose input is a set of unlabeled points that are assumed to be local maxima of an unknown value function v in an unknown subset of the vector space. Two functions are learned: (i) a set indicator c, which is a binary classifier, and (ii) a comparator function h that given two nearby samples, predicts which sample has the higher value of the unknown function v. Loss terms are used to ensure that all training samples x are a local maxima of v, according to h and satisfy c(x)=1. Therefore, c and h provide training signals to each other: a point x' in the vicinity of x satisfies c(x)=-1 or is deemed by h to be lower in value than x. We present an algorithm, show an example where it is more efficient to use local maxima as an indicator function than to employ conventional classification, and derive a suitable generalization bound. Our experiments show that the method is able to outperform one-class classification algorithms in the task of anomaly detection and also provide an additional signal that is extracted in a completely unsupervised way.
Robust Speaker Recognition Using Speech Enhancement And Attention Model
Venue: arXiv cs.CL 2020
Year: 2020

In this paper, a novel architecture for speaker recognition is proposed by cascading speech enhancement and speaker processing. Its aim is to improve speaker recognition performance when speech signals are corrupted by noise. Instead of individually processing speech enhancement and speaker recognition, the two modules are integrated into one framework by a joint optimisation using deep neural networks. Furthermore, to increase robustness against noise, a multi-stage attention mechanism is employed to highlight the speaker related features learned from context information in time and frequency domain. To evaluate speaker identification and verification performance of the proposed approach, we test it on the dataset of VoxCeleb1, one of mostly used benchmark datasets. Moreover, the robustness of our proposed approach is also tested on VoxCeleb1 data when being corrupted by three types of interferences, general noise, music, and babble, at different signal-to-noise ratio (SNR) levels. The obtained results show that the proposed approach using speech enhancement and multi-stage attention models outperforms two strong baselines not using them in most acoustic conditions in our experiments.
Recognizing Video Events with Varying Rhythms
Venue: arXiv cs.CV 2020
Year: 2020

Recognizing Video events in long, complex videos with multiple sub-activities has received persistent attention recently. This task is more challenging than traditional action recognition with short, relatively homogeneous video clips. In this paper, we investigate the problem of recognizing long and complex events with varying action rhythms, which has not been considered in the literature but is a practical challenge. Our work is inspired in part by how humans identify events with varying rhythms: quickly catching frames contributing most to a specific event. We propose a two-stage \emph{end-to-end} framework, in which the first stage selects the most significant frames while the second stage recognizes the event using the selected frames. Our model needs only \emph{event-level labels} in the training stage, and thus is more practical when the sub-activity labels are missing or difficult to obtain. The results of extensive experiments show that our model can achieve significant improvement in event recognition from long videos while maintaining high accuracy even if the test videos suffer from severe rhythm changes. This demonstrates the potential of our method for real-world video-based applications, where test and training videos can differ drastically in rhythms of sub-activities.
Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier
Venue: arXiv cs.IT 2020
Year: 2020

In distributed matrix multiplication, a common scenario is to assign each worker a fraction of the multiplication task, by partitioning the input matrices into smaller submatrices. In particular, by dividing two input matrices into $m$-by-$p$ and $p$-by-$n$ subblocks, a single multiplication task can be viewed as computing linear combinations of $pmn$ submatrix products, which can be assigned to $pmn$ workers. Such block-partitioning based designs have been widely studied under the topics of secure, private, and batch computation, where the state of the arts all require computing at least "cubic" ($pmn$) number of submatrix multiplications. Entangled polynomial codes, first presented for straggler mitigation, provides a powerful method for breaking the cubic barrier. It achieves a subcubic recovery threshold, meaning that the final product can be recovered from \emph{any} subset of multiplication results with a size order-wise smaller than $pmn$. In this work, we show that entangled polynomial codes can be further extended to also include these three important settings, and provide a unified framework that order-wise reduces the total computational costs upon the state of the arts by achieving subcubic recovery thresholds.
Non-Uniform Windowed Decoding For Multi-Dimensional Spatially-Coupled LDPC Codes
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we propose a non-uniform windowed decoder for multi-dimensional spatially-coupled LDPC (MD-SC-LDPC) codes over the binary erasure channel. An MD-SC-LDPC code is constructed by connecting together several SC-LDPC codes into one larger code that provides major benefits over a variety of channel models. In general, SC codes allow for low-latency windowed decoding. While a standard windowed decoder can be naively applied, such an approach does not fully utilize the unique structure of MD-SC-LDPC codes. In this paper, we propose and analyze a novel non-uniform decoder to provide more flexibility between latency and reliability. Our theoretical derivations and empirical results show that our non-uniform decoder greatly improves upon the standard windowed decoder in terms of design flexibility, latency, and complexity.
Extending Class Activation Mapping Using Gaussian Receptive Field
Venue: arXiv cs.CV 2020
Year: 2020

This paper addresses the visualization task of deep learning models. To improve Class Activation Mapping (CAM) based visualization method, we offer two options. First, we propose Gaussian upsampling, an improved upsampling method that can reflect the characteristics of deep learning models. Second, we identify and modify unnatural terms in the mathematical derivation of the existing CAM studies. Based on two options, we propose Extended-CAM, an advanced CAM-based visualization method, which exhibits improved theoretical properties. Experimental results show that Extended-CAM provides more accurate visualization than the existing methods.
Network Information Theoretic Security
Venue: arXiv cs.IT 2020
Year: 2020

Shannon showed that to achieve perfect secrecy in point-to-point communication, the message rate cannot exceed the shared secret key rate giving rise to the simple one-time pad encryption scheme. In this paper, we extend this work from point-to-point to networks. We consider a connected network with pairwise communication between the nodes. We assume that each node is provided with a certain amount of secret bits before communication commences. An eavesdropper with unlimited computing power has access to all communication and can hack a subset of the nodes not known to the rest of the nodes. We investigate the limits on information-theoretic secure communication for this network. We establish a tradeoff between the secure channel rate (for a node pair) and the secure network rate (sum over all node pair rates) and show that perfect secrecy can be achieved if and only if the sum rate of any subset of unhacked channels does not exceed the shared unhacked-secret-bit rate of these channels. We also propose two practical and efficient schemes that achieve a good balance of network and channel rates with perfect secrecy guarantee. This work has a wide range of potential applications for which perfect secrecy is desired, such as cyber-physical systems, distributed-control systems, and ad-hoc networks.
On the Computational Complexity of Decision Problems about Multi-Player Nash Equilibria
Venue: arXiv cs.GT 2020
Year: 2020

We study the computational complexity of decision problems about Nash equilibria in $m$-player games. Several such problems have recently been shown to be computationally equivalent to the decision problem for the existential theory of the reals, or stated in terms of complexity classes, $\exists\mathbb{R}$-complete, when $m\geq 3$. We show that, unless they turn into trivial problems, they are $\exists\mathbb{R}$-hard even for 3-player zero-sum games. We also obtain new results about several other decision problems. We show that when $m\geq 3$ the problems of deciding if a game has a Pareto optimal Nash equilibrium or deciding if a game has a strong Nash equilibrium are $\exists\mathbb{R}$-complete. The latter result rectifies a previous claim of NP-completeness in the literature. We show that deciding if a game has an irrational valued Nash equilibrium is $\exists\mathbb{R}$-hard, answering a question of Bilò and Mavronicolas, and address also the computational complexity of deciding if a game has a rational valued Nash equilibrium. These results also hold for 3-player zero-sum games. Our proof methodology applies to corresponding decision problems about symmetric Nash equilibria in symmetric games as well, and in particular our new results carry over to the symmetric setting. Finally we show that deciding whether a symmetric $m$-player games has a non-symmetric Nash equilibrium is $\exists\mathbb{R}$-complete when $m\geq 3$, answering a question of Garg, Mehta, Vazirani, and Yazdanbod.
Domain-Liftability of Relational Marginal Polytopes
Venue: arXiv cs.AI 2020
Year: 2020

We study computational aspects of relational marginal polytopes which are statistical relational learning counterparts of marginal polytopes, well-known from probabilistic graphical models. Here, given some first-order logic formula, we can define its relational marginal statistic to be the fraction of groundings that make this formula true in a given possible world. For a list of first-order logic formulas, the relational marginal polytope is the set of all points that correspond to the expected values of the relational marginal statistics that are realizable. In this paper, we study the following two problems: (i) Do domain-liftability results for the partition functions of Markov logic networks (MLNs) carry over to the problem of relational marginal polytope construction? (ii) Is the relational marginal polytope containment problem hard under some plausible complexity-theoretic assumptions? Our positive results have consequences for lifted weight learning of MLNs. In particular, we show that weight learning of MLNs is domain-liftable whenever the computation of the partition function of the respective MLNs is domain-liftable (this result has not been rigorously proven before).
Direct Visual-Inertial Ego-Motion Estimation via Iterated Extended Kalman Filter
Venue: arXiv cs.RO 2020
Year: 2020

This letter proposes a reactive navigation strategy for recovering the altitude, translational velocity and orientation of Micro Aerial Vehicles. The main contribution lies in the direct and tight fusion of Inertial Measurement Unit (IMU) measurements with monocular feedback under an assumption of a single planar scene. An Iterated Extended Kalman Filter (IEKF) scheme is employed. The state prediction makes use of IMU readings while the state update relies directly on photometric feedback as measurements. Unlike feature-based methods, the photometric difference for the innovation term renders an inherent and robust data association process in a single step. The proposed approach is validated using real-world datasets. The results show that the proposed method offers better robustness, accuracy, and efficiency than a feature-based approach. Further investigation suggests that the accuracy of the flight velocity estimates from the proposed approach is comparable to those of two state-of-the-art Visual Inertial Systems (VINS) while the proposed framework is $\approx15-30$ times faster thanks to the omission of reconstruction and mapping.
Structured GANs
Venue: arXiv cs.CV 2020
Year: 2020

We present Generative Adversarial Networks (GANs), in which the symmetric property of the generated images is controlled. This is obtained through the generator network's architecture, while the training procedure and the loss remain the same. The symmetric GANs are applied to face image synthesis in order to generate novel faces with a varying amount of symmetry. We also present an unsupervised face rotation capability, which is based on the novel notion of one-shot fine tuning.
Optimized implementation of the conjugate gradient algorithm for FPGA-based platforms using the Dirac-Wilson operator as an example
Venue: arXiv cs.DC 2020
Year: 2020

It is now a noticeable trend in High Performance Computing that the systems are becoming more and more heterogeneous. Compute nodes with a host CPU are being equipped with accelerators, the latter being a GPU or FPGA cards or both. In many cases at the heart of scientific applications running on such systems are iterative linear solvers. In this work we present a software package which includes an FPGA implementation of the Conjugate Gradient algorithm using a particular problem of the Dirac-Wilson operator as encountered in numerical simulations of Quantum Chromodynamics. The software is written in OpenCL and C++ and is optimized for maximal performance. Our framework allows for a simple implementation of other linear operators, while keeping the data transport mechanisms unaltered. Hence, our software can serve as a backbone for many applications which are expected to gain a significant boost factor on FPGA accelerators. As such systems are expected to become more and more widespread, the need for highly performant FPGA implementations of the Conjugate Gradient algorithm and its variants will certainly increase and the porting investment can be greatly facilitated by the attached code.
Distributed Artificial Intelligence Solution for D2D Communication in 5G Networks
Venue: arXiv cs.NI 2020
Year: 2020

Device to Device (D2D) Communication is one of the technology components of the evolving 5G architecture, as it promises improvements in energy efficiency, spectral efficiency, overall system capacity, and higher data rates. The above noted improvements in network performance spearheaded a vast amount of research in D2D, which have identified significant challenges that need to be addressed before realizing their full potential in emerging 5G Networks. Towards this end, this paper proposes the use of a distributed intelligent approach to control the generation of D2D networks. More precisely, the proposed approach uses Belief-Desire-Intention (BDI) intelligent agents with extended capabilities (BDIx) to manage each D2D node independently and autonomously, without the help of the Base Station. The paper includes detailed algorithmic description for the decision of transmission mode, which maximizes the data rate, minimizes the power consumptions, while taking into consideration the computational load. Simulations show the applicability of BDI agents in jointly solving D2D challenges.
Moving Objects Detection with a Moving Camera: A Comprehensive Review
Venue: arXiv cs.CV 2020
Year: 2020

During about 30 years, a lot of research teams have worked on the big challenge of detection of moving objects in various challenging environments. First applications concern static cameras but with the rise of the mobile sensors studies on moving cameras have emerged over time. In this survey, we propose to identify and categorize the different existing methods found in the literature. For this purpose, we propose to classify these methods according to the choose of the scene representation: one plane or several parts. Inside these two categories, the methods are grouped according to eight different approaches: panoramic background subtraction, dual cameras, motion compensation, subspace segmentation, motion segmentation, plane+parallax, multi planes and split image in blocks. A reminder of methods for static cameras is provided as well as the challenges with both static and moving cameras. Publicly available datasets and evaluation metrics are also surveyed in this paper.
An n/2 Byzantine node tolerate Blockchain Sharding approach
Venue: arXiv cs.CR 2020
Year: 2020

Traditional Blockchain Sharding approaches can only tolerate up to n/3 of nodes being adversary because they rely on the hypergeometric distribution to make a failure (an adversary does not have n/3 of nodes globally but can manipulate the consensus of a Shard) hard to happen. The system must maintain a large Shard size (the number of nodes inside a Shard) to sustain the low failure probability so that only a small number of Shards may exist. In this paper, we present a new approach of Blockchain Sharding that can withstand up to n/2 of nodes being bad. We categorise the nodes into different classes, and every Shard has a fixed number of nodes from different classes. We prove that this design is much more secure than the traditional models (only have one class) and the Shard size can be reduced significantly. In this way, many more Shards can exist, and the transaction throughput can be largely increased. The improved Blockchain Sharding approach is promising to serve as the foundation for decentralised autonomous organisations and decentralised database.