OpenRaiser/Intern-Atlas huggingface dataset:
Interactive Differentiable Simulation
Venue: arXiv cs.LG 2020
Year: 2020

Intelligent agents need a physical understanding of the world to predict the impact of their actions in the future. While learning-based models of the environment dynamics have contributed to significant improvements in sample efficiency compared to model-free reinforcement learning algorithms, they typically fail to generalize to system states beyond the training data, while often grounding their predictions on non-interpretable latent variables. We introduce Interactive Differentiable Simulation (IDS), a differentiable physics engine, that allows for efficient, accurate inference of physical properties of rigid-body systems. Integrated into deep learning architectures, our model is able to accomplish system identification using visual input, leading to an interpretable model of the world whose parameters have physical meaning. We present experiments showing automatic task-based robot design and parameter estimation for nonlinear dynamical systems by automatically calculating gradients in IDS. When integrated into an adaptive model-predictive control algorithm, our approach exhibits orders of magnitude improvements in sample efficiency over model-free reinforcement learning algorithms on challenging nonlinear control domains.
ProbAct: A Probabilistic Activation Function for Deep Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Activation functions play an important role in training artificial neural networks. The majority of currently used activation functions are deterministic in nature, with their fixed input-output relationship. In this work, we propose a novel probabilistic activation function, called ProbAct. ProbAct is decomposed into a mean and variance and the output value is sampled from the formed distribution, making ProbAct a stochastic activation function. The values of mean and variances can be fixed using known functions or trained for each element. In the trainable ProbAct, the mean and the variance of the activation distribution is trained within the back-propagation framework alongside other parameters. We show that the stochastic perturbation induced through ProbAct acts as a viable generalization technique for feature augmentation. In our experiments, we compare ProbAct with well-known activation functions on classification tasks on different modalities: Images(CIFAR-10, CIFAR-100, and STL-10) and Text (Large Movie Review). We show that ProbAct increases the classification accuracy by +2-3% compared to ReLU or other conventional activation functions on both original datasets and when datasets are reduced to 50% and 25% of the original size. Finally, we show that ProbAct learns an ensemble of models by itself that can be used to estimate the uncertainties associated with the prediction and provides robustness to noisy inputs.
Strategyproof Multi-Item Exchange Under Single-Minded Dichotomous Preferences
Venue: arXiv cs.GT 2020
Year: 2020

We consider multi-item exchange markets in which agents want to receive one of their target bundles of resources. The model encompasses well-studied markets for kidney exchange, lung exchange, and multi-organ exchange. We identify a general and sufficient condition called weak consistency for the exchange mechanisms to be strategyproof even if we impose any kind of distributional, diversity, or exchange cycle constraints. Within the class of weakly consistent and strategyproof mechanisms, we highlight two important ones that satisfy constrained Pareto optimality and strong individual rationality. Several results in the literature follow from our insights. We also derive impossibility results when constrained Pareto optimality is defined with respect to more permissive individual rationality requirements.
FPC-BI: Fast Probabilistic Consensus within Byzantine Infrastructures
Venue: arXiv cs.DC 2020
Year: 2020

This paper presents a novel leaderless protocol (FPC-BI: Fast Probabilistic Consensus within Byzantine Infrastructures) with a low communicational complexity and which allows a set of nodes to come to a consensus on a value of a single bit. The paper makes the assumption that part of the nodes are Byzantine, and are thus controlled by an adversary who intends to either delay the consensus, or break it (this defines that at least a couple of honest nodes come to different conclusions). We prove that, nevertheless, the protocol works with high probability when its parameters are suitably chosen. Along this the paper also provides explicit estimates on the probability that the protocol finalizes in the consensus state in a given time. This protocol could be applied to reaching consensus in decentralized cryptocurrency systems. A special feature of it is that it makes use of a sequence of random numbers which are either provided by a trusted source or generated by the nodes themselves using some decentralized random number generating protocol. This increases the overall trustworthiness of the infrastructure. A core contribution of the paper is that it uses a very weak consensus to obtain a strong consensus on the value of a bit, and which can relate to the validity of a transaction.
Defining Quantum Neural Networks via Quantum Time Evolution
Venue: arXiv cs.LG 2020
Year: 2020

This work presents a novel fundamental algorithm for for defining and training Neural Networks in Quantum Information based on time evolution and the Hamiltonian. Classical Neural Network algorithms (ANN) are computationally expensive. For example, in image classification, representing an image pixel by pixel using classical information requires an enormous amount of computational memory resources. Hence, exploring methods to represent images in a different paradigm of information is important. Quantum Neural Networks (QNNs) have been explored for over 20 years. The current forefront work based on Variational Quantum Circuits is specifically defined for the Continuous Variable (CV) Model of quantum computers. In this work, a model is proposed which is defined at a more fundamental level and hence can be inherited by any variants of quantum computing models. This work also presents a quantum backpropagation algorithm to train our QNN model and validate this algorithm on the MNIST dataset on a quantum computer simulation.
Direct Acyclic Graph based Ledger for Internet of Things: Performance and Security Analysis
Venue: arXiv cs.DC 2020
Year: 2020

Direct Acyclic Graph (DAG)-based ledger and the corresponding consensus algorithm has been identified as a promising technology for Internet of Things (IoT). Compared with Proof-of-Work (PoW) and Proof-of-Stake (PoS) that have been widely used in blockchain, the consensus mechanism designed on DAG structure (simply called as DAG consensus) can overcome some shortcomings such as high resource consumption, high transaction fee, low transaction throughput and long confirmation delay. However, the theoretic analysis on the DAG consensus is an untapped venue to be explored. To this end, based on one of the most typical DAG consensuses, Tangle, we investigate the impact of network load on the performance and security of the DAG-based ledger. Considering unsteady network load, we first propose a Markov chain model to capture the behavior of DAG consensus process under dynamic load conditions. The key performance metrics, i.e., cumulative weight and confirmation delay are analysed based on the proposed model. Then, we leverage a stochastic model to analyse the probability of a successful double-spending attack in different network load regimes. The results can provide an insightful understanding of DAG consensus process, e.g., how the network load affects the confirmation delay and the probability of a successful attack. Meanwhile, we also demonstrate the trade-off between security level and confirmation delay, which can act as a guidance for practical deployment of DAG-based ledgers.
AI-GAs: AI-generating algorithms, an alternate paradigm for producing general artificial intelligence
Venue: arXiv cs.AI 2020
Year: 2020

Perhaps the most ambitious scientific quest in human history is the creation of general artificial intelligence, which roughly means AI that is as smart or smarter than humans. The dominant approach in the machine learning community is to attempt to discover each of the pieces required for intelligence, with the implicit assumption that some future group will complete the Herculean task of figuring out how to combine all of those pieces into a complex thinking machine. I call this the "manual AI approach". This paper describes another exciting path that ultimately may be more successful at producing general AI. It is based on the clear trend in machine learning that hand-designed solutions eventually are replaced by more effective, learned solutions. The idea is to create an AI-generating algorithm (AI-GA), which automatically learns how to produce general AI. Three Pillars are essential for the approach: (1) meta-learning architectures, (2) meta-learning the learning algorithms themselves, and (3) generating effective learning environments. I argue that either approach could produce general AI first, and both are scientifically worthwhile irrespective of which is the fastest path. Because both are promising, yet the ML community is currently committed to the manual approach, I argue that our community should increase its research investment in the AI-GA approach. To encourage such research, I describe promising work in each of the Three Pillars. I also discuss AI-GA-specific safety and ethical considerations. Because it it may be the fastest path to general AI and because it is inherently scientifically interesting to understand the conditions in which a simple algorithm can produce general AI (as happened on Earth where Darwinian evolution produced human intelligence), I argue that the pursuit of AI-GAs should be considered a new grand challenge of computer science research.
Quantization-Based Regularization for Autoencoders
Venue: arXiv cs.LG 2020
Year: 2020

Autoencoders and their variations provide unsupervised models for learning low-dimensional representations for downstream tasks. Without proper regularization, autoencoder models are susceptible to the overfitting problem and the so-called posterior collapse phenomenon. In this paper, we introduce a quantization-based regularizer in the bottleneck stage of autoencoder models to learn meaningful latent representations. We combine both perspectives of Vector Quantized-Variational AutoEncoders (VQ-VAE) and classical denoising regularization methods of neural networks. We interpret quantizers as regularizers that constrain latent representations while fostering a similarity-preserving mapping at the encoder. Before quantization, we impose noise on the latent codes and use a Bayesian estimator to optimize the quantizer-based representation. The introduced bottleneck Bayesian estimator outputs the posterior mean of the centroids to the decoder, and thus, is performing soft quantization of the noisy latent codes. We show that our proposed regularization method results in improved latent representations for both supervised learning and clustering downstream tasks when compared to autoencoders using other bottleneck structures.
Model-Agnostic Counterfactual Explanations for Consequential Decisions
Venue: arXiv cs.LG 2020
Year: 2020

Predictive models are being increasingly used to support consequential decision making at the individual level in contexts such as pretrial bail and loan approval. As a result, there is increasing social and legal pressure to provide explanations that help the affected individuals not only to understand why a prediction was output, but also how to act to obtain a desired outcome. To this end, several works have proposed optimization-based methods to generate nearest counterfactual explanations. However, these methods are often restricted to a particular subset of models (e.g., decision trees or linear models) and differentiable distance functions. In contrast, we build on standard theory and tools from formal verification and propose a novel algorithm that solves a sequence of satisfiability problems, where both the distance function (objective) and predictive model (constraints) are represented as logic formulae. As shown by our experiments on real-world data, our algorithm is: i) model-agnostic ({non-}linear, {non-}differentiable, {non-}convex); ii) data-type-agnostic (heterogeneous features); iii) distance-agnostic ($\ell_0, \ell_1, \ell_\infty$, and combinations thereof); iv) able to generate plausible and diverse counterfactuals for any sample (i.e., 100% coverage); and v) at provably optimal distances.
Successive Cancellation List Decoding of Semi-random Unit Memory Convolutional Codes
Venue: arXiv cs.IT 2020
Year: 2020

We present in this paper a special class of unit memory convolutional codes (UMCCs), called semi-random UMCCs (SRUMCCs), where the information block is first encoded by a short block code and then transmitted in a block Markov (random) superposition manner. We propose a successive cancellation list decoding algorithm, by which a list of candidate codewords are generated serially until one passes an empirical divergence test instead of the conventional cyclic redundancy check (CRC). The threshold for testing the correctness of candidate codewords can be learned off-line based on the statistical behavior of the introduced empirical divergence function (EDF). The performance-complexity tradeoff and the performance-delay tradeoff can be achieved by adjusting the statistical threshold and the decoding window size. To analyze the performance, a closed-form upper bound and a simulated lower bound are derived. Simulation results verify our analysis and show that: 1) The proposed list decoding algorithm with empirical divergence test outperforms the sequential decoding in high signal-to-noise ratio (SNR) region; 2) Taking the tail-biting convolutional codes (TBCC) as the basic codes, the proposed list decoding of SRUMCCs have comparable performance with the polar codes under the constraint of equivalent decoding delay.
Incidence Networks for Geometric Deep Learning
Venue: arXiv cs.LG 2020
Year: 2020

Sparse incidence tensors can represent a variety of structured data. For example, we may represent attributed graphs using their node-node, node-edge, or edge-edge incidence matrices. In higher dimensions, incidence tensors can represent simplicial complexes and polytopes. In this paper, we formalize incidence tensors, analyze their structure, and present the family of equivariant networks that operate on them. We show that any incidence tensor decomposes into invariant subsets. This decomposition, in turn, leads to a decomposition of the corresponding equivariant linear maps, for which we prove an efficient pooling-and-broadcasting implementation.
A near-optimal algorithm for approximating the John Ellipsoid
Venue: arXiv cs.DS 2020
Year: 2020

We develop a simple and efficient algorithm for approximating the John Ellipsoid of a symmetric polytope. Our algorithm is near optimal in the sense that our time complexity matches the current best verification algorithm. We also provide the MATLAB code for further research.
Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero
Venue: arXiv cs.LG 2020
Year: 2020

There have been increasing challenges to solve combinatorial optimization problems by machine learning. Khalil et al. proposed an end-to-end reinforcement learning framework, S2V-DQN, which automatically learns graph embeddings to construct solutions to a wide range of problems. To improve the generalization ability of their Q-learning method, we propose a novel learning strategy based on AlphaGo Zero which is a Go engine that achieved a superhuman level without the domain knowledge of the game. Our framework is redesigned for combinatorial problems, where the final reward might take any real number instead of a binary response, win/lose. In experiments conducted for five kinds of NP-hard problems including {\sc MinimumVertexCover} and {\sc MaxCut}, our method is shown to generalize better to various graphs than S2V-DQN. Furthermore, our method can be combined with recently-developed graph neural network (GNN) models such as the \emph{Graph Isomorphism Network}, resulting in even better performance. This experiment also gives an interesting insight into a suitable choice of GNN models for each task.
Variational Information Bottleneck for Unsupervised Clustering: Deep Gaussian Mixture Embedding
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we develop an unsupervised generative clustering framework that combines the Variational Information Bottleneck and the Gaussian Mixture Model. Specifically, in our approach, we use the Variational Information Bottleneck method and model the latent space as a mixture of Gaussians. We derive a bound on the cost function of our model that generalizes the Evidence Lower Bound (ELBO) and provide a variational inference type algorithm that allows computing it. In the algorithm, the coders' mappings are parametrized using neural networks, and the bound is approximated by Monte Carlo sampling and optimized with stochastic gradient descent. Numerical results on real datasets are provided to support the efficiency of our method.
Hydras and IPFS: A Decentralised Playground for Malware
Venue: arXiv cs.CR 2020
Year: 2020

Modern malware can take various forms, and has reached a very high level of sophistication in terms of its penetration, persistence, communication and hiding capabilities. The use of cryptography, and of covert communication channels over public and widely used protocols and services, is becoming a norm. In this work, we start by introducing Resource Identifier Generation Algorithms. These are an extension of a well-known mechanism called Domain Generation Algorithms (DGA), which are frequently employed by cybercriminals for bot management and communication. Our extension allows, beyond DNS, the use of other protocols. More concretely, we showcase the exploitation of the InterPlanetary file system (IPFS). This is a solution for the "permanent web", which enjoys a steadily growing community interest and adoption. The IPFS is, in addition, one of the most prominent solutions for blockchain storage. We go beyond the straightforward case of using the IPFS for hosting malicious content, and explore ways in which a botmaster could employ it, to manage her bots, validating our findings experimentally. Finally, we discuss the advantages of our approach for malware authors, its efficacy and highlight its extensibility for other distributed storage services.
RecNets: Channel-wise Recurrent Convolutional Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we introduce Channel-wise recurrent convolutional neural networks (RecNets), a family of novel, compact neural network architectures for computer vision tasks inspired by recurrent neural networks (RNNs). RecNets build upon Channel-wise recurrent convolutional (CRC) layers, a novel type of convolutional layer that splits the input channels into disjoint segments and processes them in a recurrent fashion. In this way, we simulate wide, yet compact models, since the number of parameters is vastly reduced via the parameter sharing of the RNN formulation. Experimental results on the CIFAR-10 and CIFAR-100 image classification tasks demonstrate the superior size-accuracy trade-off of RecNets compared to other compact state-of-the-art architectures.
Adaptive Deep Kernel Learning
Venue: arXiv cs.LG 2020
Year: 2020

Deep kernel learning provides an elegant and principled framework for combining the structural properties of deep learning algorithms with the flexibility of kernel methods. By means of a deep neural network, we learn a parametrized kernel operator that can be combined with a differentiable kernel algorithm during inference. While previous work within this framework has focused on learning a single kernel for large datasets, we learn a kernel family for a variety of few-shot regression tasks. Compared to single deep kernel learning, our algorithm enables the identification of the appropriate kernel for each task during inference. As such, it is well adapted for complex task distributions in a few-shot learning setting, which we demonstrate by comparing against existing state-of-the-art algorithms using real-world, few-shot regression tasks related to the field of drug discovery.
A Topology Layer for Machine Learning
Venue: arXiv cs.LG 2020
Year: 2020

Topology applied to real world data using persistent homology has started to find applications within machine learning, including deep learning. We present a differentiable topology layer that computes persistent homology based on level set filtrations and edge-based filtrations. We present three novel applications: the topological layer can (i) regularize data reconstruction or the weights of machine learning models, (ii) construct a loss on the output of a deep generative network to incorporate topological priors, and (iii) perform topological adversarial attacks on deep networks trained with persistence features. The code (www.github.com/bruel-gabrielsson/TopologyLayer) is publicly available and we hope its availability will facilitate the use of persistent homology in deep learning and other gradient based applications.
Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
Venue: arXiv cs.LG 2020
Year: 2020

Stochastic variance reduced methods have gained a lot of interest recently for empirical risk minimization due to its appealing run time complexity. When the data size is large and disjointly stored on different machines, it becomes imperative to distribute the implementation of such variance reduced methods. In this paper, we consider a general framework that directly distributes popular stochastic variance reduced methods in the master/slave model, by assigning outer loops to the parameter server, and inner loops to worker machines. This framework is natural and friendly to implement, but its theoretical convergence is not well understood. We obtain a comprehensive understanding of algorithmic convergence with respect to data homogeneity by measuring the smoothness of the discrepancy between the local and global loss functions. We establish the linear convergence of distributed versions of a family of stochastic variance reduced algorithms, including those using accelerated and recursive gradient updates, for minimizing strongly convex losses. Our theory captures how the convergence of distributed algorithms behaves as the number of machines and the size of local data vary. Furthermore, we show that when the data are less balanced, regularization can be used to ensure convergence at a slower rate. We also demonstrate that our analysis can be further extended to handle nonconvex loss functions.