OpenRaiser/Intern-Atlas huggingface dataset:
Space-time multilevel Monte Carlo methods and their application to cardiac electrophysiology
Venue: arXiv cs.CE 2021
Year: 2021

We present a novel approach aimed at high-performance uncertainty quantification for time-dependent problems governed by partial differential equations. In particular, we consider input uncertainties described by a Karhunen-Loeeve expansion and compute statistics of high-dimensional quantities-of-interest, such as the cardiac activation potential. Our methodology relies on a close integration of multilevel Monte Carlo methods, parallel iterative solvers, and a space-time discretization. This combination allows for space-time adaptivity, time-changing domains, and to take advantage of past samples to initialize the space-time solution. The resulting sequence of problems is distributed using a multilevel parallelization strategy, allocating batches of samples having different sizes to a different number of processors. We assess the performance of the proposed framework by showing in detail its application to the solution of nonlinear equations arising from cardiac electrophysiology. Specifically, we study the effect of spatially-correlated perturbations of the heart fibers conductivities on the mean and variance of the resulting activation map. As shown by the experiments, the theoretical rates of convergence of multilevel Monte Carlo are achieved. Moreover, the total computational work for a prescribed accuracy is reduced by an order of magnitude with respect to standard Monte Carlo methods.
RNN-Test: Towards Adversarial Testing for Recurrent Neural Network Systems
Venue: arXiv cs.CL 2021
Year: 2021

While massive efforts have been investigated in adversarial testing of convolutional neural networks (CNN), testing for recurrent neural networks (RNN) is still limited and leaves threats for vast sequential application domains. In this paper, we propose an adversarial testing framework RNN-Test for RNN systems, focusing on the main sequential domains, not only classification tasks. First, we design a novel search methodology customized for RNN models by maximizing the inconsistency of RNN states to produce adversarial inputs. Next, we introduce two state-based coverage metrics according to the distinctive structure of RNNs to explore more inference logics. Finally, RNN-Test solves the joint optimization problem to maximize state inconsistency and state coverage, and crafts adversarial inputs for various tasks of different kinds of inputs. For evaluations, we apply RNN-Test on three sequential models of common RNN structures. On the tested models, the RNN-Test approach is demonstrated to be competitive in generating adversarial inputs, outperforming FGSM-based and DLFuzz-based methods to reduce the model performance more sharply with 2.78% to 32.5% higher success (or generation) rate. RNN-Test could also achieve 52.65% to 66.45% higher adversary rate on MNIST-LSTM model than relevant work testRNN. Compared with the neuron coverage, the proposed state coverage metrics as guidance excel with 4.17% to 97.22% higher success (or generation) rate.
LGN-CNN: a biologically inspired CNN architecture
Venue: arXiv cs.NE 2021
Year: 2021

In this paper we introduce a biologically inspired Convolutional Neural Network (CNN) architecture called LGN-CNN that has a first convolutional layer composed by a single filter that mimics the role of the Lateral Geniculate Nucleus (LGN). The first layer of the neural network shows a rotational symmetric pattern justified by the structure of the net itself that turns up to be an approximation of a Laplacian of Gaussian (LoG). The latter function is in turn a good approximation of the receptive field profiles (RFPs) of the cells in the LGN. The analogy with the visual system is established, emerging directly from the architecture of the neural network. A proof of rotation invariance of the first layer is given on a fixed LGN-CNN architecture and the computational results are shown. Thus, contrast invariance capability of the LGN-CNN is investigated and a comparison between the Retinex effects of the first layer of LGN-CNN and the Retinex effects of a LoG is provided on different images. A statistical study is done on the filters of the second convolutional layer with respect to biological data. In conclusion, the model we have introduced approximates well the RFPs of both LGN and V1 attaining similar behavior as regards long range connections of LGN cells that show Retinex effects.
On the Behaviour of Coalgebras with Side Effects and Algebras with Effectful Iteration
Venue: arXiv cs.LO 2021
Year: 2021

For every finitary monad $T$ on sets and every endofunctor $F$ on the category of $T$-algebras we introduce the concept of an ffg-Elgot algebra for $F$, that is, an algebra admitting coherent solutions for finite systems of recursive equations with effects represented by the monad $T$. The goal is to study the existence and construction of free ffg-Elgot algebras. To this end, we investigate the locally ffg fixed point $φF$, i.e. the colimit of all $F$-coalgebras with free finitely generated carrier, which is shown to be the initial ffg-Elgot algebra. This is the technical foundation for our main result: the category of ffg-Elgot algebras is monadic over the category of $T$-algebras.
Curriculum Self-Paced Learning for Cross-Domain Object Detection
Venue: arXiv cs.CV 2021
Year: 2021

Training (source) domain bias affects state-of-the-art object detectors, such as Faster R-CNN, when applied to new (target) domains. To alleviate this problem, researchers proposed various domain adaptation methods to improve object detection results in the cross-domain setting, e.g. by translating images with ground-truth labels from the source domain to the target domain using Cycle-GAN. On top of combining Cycle-GAN transformations and self-paced learning in a smart and efficient way, in this paper, we propose a novel self-paced algorithm that learns from easy to hard. Our method is simple and effective, without any overhead during inference. It uses only pseudo-labels for samples taken from the target domain, i.e. the domain adaptation is unsupervised. We conduct experiments on four cross-domain benchmarks, showing better results than the state of the art. We also perform an ablation study demonstrating the utility of each component in our framework. Additionally, we study the applicability of our framework to other object detectors. Furthermore, we compare our difficulty measure with other measures from the related literature, proving that it yields superior results and that it correlates well with the performance metric.
Unsupervised Domain Adaptation for Object Detection via Cross-Domain Semi-Supervised Learning
Venue: arXiv cs.CV 2021
Year: 2021

Current state-of-the-art object detectors can have significant performance drop when deployed in the wild due to domain gaps with training data. Unsupervised Domain Adaptation (UDA) is a promising approach to adapt models for new domains/environments without any expensive label cost. However, without ground truth labels, most prior works on UDA for object detection tasks can only perform coarse image-level and/or feature-level adaptation by using adversarial learning methods. In this work, we show that such adversarial-based methods can only reduce the domain style gap, but cannot address the domain content distribution gap that is shown to be important for object detectors. To overcome this limitation, we propose the Cross-Domain Semi-Supervised Learning (CDSSL) framework by leveraging high-quality pseudo labels to learn better representations from the target domain directly. To enable SSL for cross-domain object detection, we propose fine-grained domain transfer, progressive-confidence-based label sharpening and imbalanced sampling strategy to address two challenges: (i) non-identical distribution between source and target domain data, (ii) error amplification/accumulation due to noisy pseudo labeling on the target domain. Experiment results show that our proposed approach consistently achieves new state-of-the-art performance (2.2% - 9.5% better than prior best work on mAP) under various domain gap scenarios. The code will be released.
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning
Venue: arXiv cs.DS 2021
Year: 2021

We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\{-1,1\}^n$, which makes $\tilde O (\sqrt{n}/\varepsilon^2)$ queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on $\{-1,1\}^n$, and a quantitative analysis of how such a restriction affects the mean vector of the distribution. Along the way, we consider the problem of mean testing with independent samples and provide a nearly-optimal algorithm.
Machine Learning-powered Iterative Combinatorial Auctions
Venue: arXiv cs.GT 2021
Year: 2021

We present a machine learning-powered iterative combinatorial auction (MLCA). The main goal of integrating machine learning (ML) into the auction is to improve preference elicitation, which is a major challenge in large combinatorial auctions (CAs). In contrast to prior work, our auction design uses value queries instead of prices to drive the auction. The ML algorithm is used to help the auction decide which value queries to ask in every iteration. While using ML inside a CA introduces new challenges, we demonstrate how we obtain a design that is individually rational, satisfies no-deficit, has good incentives, and is computationally practical. We benchmark our new auction against the well-known combinatorial clock auction (CCA). Our results indicate that, especially in large domains, MLCA can achieve significantly higher allocative efficiency than the CCA, even with only a small number of value queries.
General $E(2)$-Equivariant Steerable CNNs
Venue: arXiv cs.CV 2021
Year: 2021

The big empirical success of group equivariant networks has led in recent years to the sprouting of a great variety of equivariant network architectures. A particular focus has thereby been on rotation and reflection equivariant CNNs for planar images. Here we give a general description of $E(2)$-equivariant convolutions in the framework of Steerable CNNs. The theory of Steerable CNNs thereby yields constraints on the convolution kernels which depend on group representations describing the transformation laws of feature spaces. We show that these constraints for arbitrary group representations can be reduced to constraints under irreducible representations. A general solution of the kernel space constraint is given for arbitrary representations of the Euclidean group $E(2)$ and its subgroups. We implement a wide range of previously proposed and entirely new equivariant network architectures and extensively compare their performances. $E(2)$-steerable convolutions are further shown to yield remarkable gains on CIFAR-10, CIFAR-100 and STL-10 when used as a drop-in replacement for non-equivariant convolutions.
Attention-Privileged Reinforcement Learning
Venue: arXiv cs.AI 2021
Year: 2021

Image-based Reinforcement Learning is known to suffer from poor sample efficiency and generalisation to unseen visuals such as distractors (task-independent aspects of the observation space). Visual domain randomisation encourages transfer by training over visual factors of variation that may be encountered in the target domain. This increases learning complexity, can negatively impact learning rate and performance, and requires knowledge of potential variations during deployment. In this paper, we introduce Attention-Privileged Reinforcement Learning (APRiL) which uses a self-supervised attention mechanism to significantly alleviate these drawbacks: by focusing on task-relevant aspects of the observations, attention provides robustness to distractors as well as significantly increased learning efficiency. APRiL trains two attention-augmented actor-critic agents: one purely based on image observations, available across training and transfer domains; and one with access to privileged information (such as environment states) available only during training. Experience is shared between both agents and their attention mechanisms are aligned. The image-based policy can then be deployed without access to privileged information. We experimentally demonstrate accelerated and more robust learning on a diverse set of domains, leading to improved final performance for environments both within and outside the training distribution.
A New Characterization of Path Graphs
Venue: arXiv cs.DM 2021
Year: 2021

Path graphs are intersection graphs of paths in a tree.~In this paper we give a "6\ good characterization" of path graphs, namely, we prove that path graph membership is in $NP\cap CoNP$ without resorting to existing polynomial time algorithms. The characterization is given in terms of the collection of the \emph{attachedness graphs} of a graph, a novel device to deal with the connected components of a graph after the removal of clique separators. On the one hand, the characterization refines and simplifies the characterization of path graphs due to Monma and Wei [C.L.~Monma,~and~V.K.~Wei, Intersection {G}raphs of {P}aths in a {T}ree, J. Combin. Theory Ser. B, 41:2 (1986) 141--181], which we build on, by reducing a constrained vertex coloring problem defined on the \emph{attachedness graphs} to a vertex 2-coloring problem on the same graphs. On the other hand, the characterization allows us to exhibit two exhaustive lists of obstructions to path graph membership in the form of minimal forbidden induced/partial 2-edge colored subgraphs in each of the \emph{attachedness graphs}.
Collective Dynamics of Dark Web Marketplaces
Venue: arXiv cs.CY 2021
Year: 2021

Dark markets are commercial websites that use Bitcoin to sell or broker transactions involving drugs, weapons, and other illicit goods. Being illegal, they do not offer any user protection, and several police raids and scams have caused large losses to both customers and vendors over the past years. However, this uncertainty has not prevented a steady growth of the dark market phenomenon and a proliferation of new markets. The origin of this resilience have remained unclear so far, also due to the difficulty of identifying relevant Bitcoin transaction data. Here, we investigate how the dark market ecosystem re-organises following the disappearance of a market, due to factors including raids and scams. To do so, we analyse 24 episodes of unexpected market closure through a novel datasets of 133 million Bitcoin transactions involving 31 dark markets and their users, totalling 4 billion USD. We show that coordinated user migration from the closed market to coexisting markets guarantees overall systemic resilience beyond the intrinsic fragility of individual markets. The migration is swift, efficient and common to all market closures. We find that migrants are on average more active users in comparison to non-migrants and move preferentially towards the coexisting market with the highest trading volume. Our findings shed light on the resilience of the dark market ecosystem and we anticipate that they may inform future research on the self-organisation of emerging online markets.
Graph Pruning for Model Compression
Venue: arXiv cs.CV 2021
Year: 2021

Previous AutoML pruning works utilized individual layer features to automatically prune filters. We analyze the correlation for two layers from the different blocks which have a short-cut structure. It shows that, in one block, the deeper layer has many redundant filters which can be represented by filters in the former layer. So, it is necessary to take information from other layers into consideration in pruning. In this paper, a novel pruning method, named GraphPruning, is proposed. Any series of the network is viewed as a graph. To automatically aggregate neighboring features for each node, a graph aggregator based on graph convolution networks(GCN) is designed. In the training stage, a PruningNet that is given aggregated node features generates reasonable weights for any size of the sub-network. Subsequently, the best configuration of the Pruned Network is searched by reinforcement learning. Different from previous work, we take the node features from a well-trained graph aggregator instead of the hand-craft features, as the states in reinforcement learning. Compared with other AutoML pruning works, our method has achieved the state-of-the-art under the same conditions on ImageNet-2012.
Optimizing Data Usage via Differentiable Rewards
Venue: arXiv cs.LG 2021
Year: 2021

To acquire a new skill, humans learn better and faster if a tutor, based on their current knowledge level, informs them of how much attention they should pay to particular content or practice problems. Similarly, a machine learning model could potentially be trained better with a scorer that "adapts" to its current learning state and estimates the importance of each training data instance. Training such an adaptive scorer efficiently is a challenging problem; in order to precisely quantify the effect of a data instance at a given time during the training, it is typically necessary to first complete the entire training process. To efficiently optimize data usage, we propose a reinforcement learning approach called Differentiable Data Selection (DDS). In DDS, we formulate a scorer network as a learnable function of the training data, which can be efficiently updated along with the main model being trained. Specifically, DDS updates the scorer with an intuitive reward signal: it should up-weigh the data that has a similar gradient with a dev set upon which we would finally like to perform well. Without significant computing overhead, DDS delivers strong and consistent improvements over several strong baselines on two very different tasks of machine translation and image classification.
Do you trade with your friends or become friends with your trading partners? A case study in the G1 cryptocurrency
Venue: arXiv cs.SI 2021
Year: 2021

We study the interplay between social ties and financial transactions made through a recent cryptocurrency called $\breve{G}1$. It has the particularity of combining the usual transaction record with a reliable network of identified users. This gives the opportunity to observe exactly who sent money to whom over a social network. This social network is a key piece of this cryptocurrency, which therefore puts much effort in ensuring that nodes correspond to unique, well identified, real living human users, linked together only if they met at least once in real world. Using this data, we study how social ties impact the structure of transactions and conversely. We show that users make transactions almost exclusively with people they are connected with in the social network. Instead, they tend to build social connections with people they will never make transactions with.
Rigging the Lottery: Making All Tickets Winners
Venue: arXiv cs.LG 2021
Year: 2021

Many applications require sparse neural networks due to space or inference time restrictions. There is a large body of work on training dense networks to yield sparse networks for inference, but this limits the size of the largest trainable sparse model to that of the largest trainable dense model. In this paper we introduce a method to train sparse neural networks with a fixed parameter count and a fixed computational cost throughout training, without sacrificing accuracy relative to existing dense-to-sparse training methods. Our method updates the topology of the sparse network during training by using parameter magnitudes and infrequent gradient calculations. We show that this approach requires fewer floating-point operations (FLOPs) to achieve a given level of accuracy compared to prior techniques. We demonstrate state-of-the-art sparse training results on a variety of networks and datasets, including ResNet-50, MobileNets on Imagenet-2012, and RNNs on WikiText-103. Finally, we provide some insights into why allowing the topology to change during the optimization can overcome local minima encountered when the topology remains static. Code used in our work can be found in github.com/google-research/rigl.
Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
Venue: arXiv cs.DM 2021
Year: 2021

Let $G$ be an $n$-node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC'17) for bimodular integer programs can be used to find a maximum weight stable set in $G$ in strongly polynomial time. Building on structural results characterizing sufficiently connected graphs without two disjoint odd cycles, we construct a size-$O(n^2)$ extended formulation for the stable set polytope of $G$.
General supervised learning as change propagation with delta lenses
Venue: arXiv cs.LO 2021
Year: 2021

Delta lenses are an established mathematical framework for modelling and designing bidirectional model transformations. Following the recent observations by Fong et al, the paper extends the delta lens framework with a a new ingredient: learning over a parameterized space of model transformations seen as functors. We define a notion of an asymmetric learning delta lens with amendment (ala-lens), and show how ala-lenses can be organized into a symmetric monoidal (sm) category. We also show that sequential and parallel composition of well-behaved ala-lenses are also well-behaved so that well-behaved ala-lenses constitute a full sm-subcategory of ala-lenses.
Abstract Argumentation and the Rational Man
Venue: arXiv cs.AI 2021
Year: 2021

Abstract argumentation has emerged as a method for non-monotonic reasoning that has gained popularity in the symbolic artificial intelligence community. In the literature, the different approaches to abstract argumentation that were refined over the years are typically evaluated from a formal logics perspective; an analysis that is based on models of economically rational decision-making does not exist. In this paper, we work towards addressing this issue by analyzing abstract argumentation from the perspective of the rational man paradigm in microeconomic theory. To assess under which conditions abstract argumentation-based decision-making can be considered economically rational, we derive reference independence as a non-monotonic inference property from a formal model of economic rationality and create a new argumentation principle that ensures compliance with this property. We then compare the reference independence principle with other reasoning principles, in particular with cautious monotony and rational monotony. We show that the argumentation semantics as proposed in Dung's seminal paper, as well as other semantics we evaluate -- with the exception of naive semantics and the SCC-recursive CF2 semantics -- violate the reference independence principle. Consequently, we investigate how structural properties of argumentation frameworks impact the reference independence principle, and identify cyclic expansions (both even and odd cycles) as the root of the problem. Finally, we put reference independence into the context of preference-based argumentation and show that for this argumentation variant, which explicitly models preferences, reference independence cannot be ensured in a straight-forward manner.