OpenRaiser/Intern-Atlas huggingface dataset:
VASS reachability in three steps
Venue: arXiv cs.LO 2020
Year: 2020

This note is a product of digestion of the famous proof of decidability of the reachability problem for vector addition systems with states (VASS), as first established by Mayr in 1981 and then simplified by Kosaraju in 1982. The note is neither intended to be rigorously formal nor complete; it is rather intended to be an intuitive but precise enough description of main concepts exploited in the proof. Very roughly, the overall idea is to provide a decidable condition Theta on a VASS such that Theta implies reachability and its negation implies that the size of VASS can be reduced. With these two properties, the size of input can be incrementally reduced until the problem becomes trivial. We proceed in three steps: we first formulate the condition Theta for plain VASS, then adapt it to more general VASS with unconstrained coordinates, and finally to generalized VASS of Kosaraju.
A Theoretical Analysis of Deep Q-Learning
Venue: arXiv cs.LG 2020
Year: 2020

Despite the great empirical success of deep reinforcement learning, its theoretical foundation is less well understood. In this work, we make the first attempt to theoretically understand the deep Q-network (DQN) algorithm (Mnih et al., 2015) from both algorithmic and statistical perspectives. In specific, we focus on a slight simplification of DQN that fully captures its key features. Under mild assumptions, we establish the algorithmic and statistical rates of convergence for the action-value functions of the iterative policy sequence obtained by DQN. In particular, the statistical error characterizes the bias and variance that arise from approximating the action-value function using deep neural network, while the algorithmic error converges to zero at a geometric rate. As a byproduct, our analysis provides justifications for the techniques of experience replay and target network, which are crucial to the empirical success of DQN. Furthermore, as a simple extension of DQN, we propose the Minimax-DQN algorithm for zero-sum Markov game with two players. Borrowing the analysis of DQN, we also quantify the difference between the policies obtained by Minimax-DQN and the Nash equilibrium of the Markov game in terms of both the algorithmic and statistical rates of convergence.
Nash Equilibria on (Un)Stable Networks
Venue: arXiv cs.SI 2020
Year: 2020

In response to a change, individuals may choose to follow the responses of their friends or, alternatively, to change their friends. To model these decisions, consider a game where players choose their behaviors and friendships. In equilibrium, players internalize the need for consensus in forming friendships and choose their optimal strategies on subsets of k players - a form of bounded rationality. The k-player consensual dynamic delivers a probabilistic ranking of a game's equilibria, and, via a varying k, facilitates estimation of such games. Applying the model to adolescents' smoking suggests that: (a.) the response of the friendship network to changes in tobacco price amplifies the intended effect of price changes on smoking, (b.) racial desegregation of high-schools decreases the overall smoking prevalence, (c.) peer effect complementarities are substantially stronger between smokers compared to between non-smokers. (d.) the magnitude of the spillover effects from small scale policies targeting individuals' smoking choices are roughly double compared to the scale of these policies.
Almost Optimal Distribution-free Junta Testing
Venue: arXiv cs.DS 2020
Year: 2020

We consider the problem of testing whether an unknown $n$-variable Boolean function is a $k$-junta in the distribution-free property testing model, where the distance between function is measured with respect to an arbitrary and unknown probability distribution over $\{0,1\}^n$. Chen, Liu, Servedio, Sheng and Xie showed that the distribution-free $k$-junta testing can be performed, with one-sided error, by an adaptive algorithm that makes $\tilde O(k^2)/ε$ queries. In this paper, we give a simple two-sided error adaptive algorithm that makes $\tilde O(k/ε)$ queries.
Adaptive Density Estimation for Generative Models
Venue: arXiv cs.CV 2020
Year: 2020

Unsupervised learning of generative models has seen tremendous progress over recent years, in particular due to generative adversarial networks (GANs), variational autoencoders, and flow-based models. GANs have dramatically improved sample quality, but suffer from two drawbacks: (i) they mode-drop, i.e., do not cover the full support of the train data, and (ii) they do not allow for likelihood evaluations on held-out data. In contrast, likelihood-based training encourages models to cover the full support of the train data, but yields poorer samples. These mutual shortcomings can in principle be addressed by training generative latent variable models in a hybrid adversarial-likelihood manner. However, we show that commonly made parametric assumptions create a conflict between them, making successful hybrid models non trivial. As a solution, we propose to use deep invertible transformations in the latent variable decoder. This approach allows for likelihood computations in image space, is more efficient than fully invertible models, and can take full advantage of adversarial training. We show that our model significantly improves over existing hybrid models: offering GAN-like samples, IS and FID scores that are competitive with fully adversarial models, and improved likelihood scores.
Signal and System Design for Wireless Power Transfer : Prototype, Experiment and Validation
Venue: arXiv cs.IT 2020
Year: 2020

A new line of research on communications and signals design for Wireless Power Transfer (WPT) has recently emerged in the communication literature. Promising signal strategies to maximize the power transfer efficiency of WPT rely on (energy) beamforming, waveform, modulation and transmit diversity, and a combination thereof. To a great extent, the study of those strategies has so far been limited to theoretical performance analysis. In this paper, we study the real over-the-air performance of all the aforementioned signal strategies for WPT. To that end, we have designed, prototyped and experimented an innovative radiative WPT architecture based on Software-Defined Radio (SDR) that can operate in open-loop and closed-loop (with channel acquisition at the transmitter) modes. The prototype consists of three important blocks, namely the channel estimator, the signal generator, and the energy harvester. The experiments have been conducted in a variety of deployments, including frequency flat and frequency selective channels, under static and mobility conditions. Experiments highlight that a channeladaptive WPT architecture based on joint beamforming and waveform design offers significant performance improvements in harvested DC power over conventional single-antenna/multiantenna continuous wave systems. The experimental results fully validate the observations predicted from the theoretical signal designs and confirm the crucial and beneficial role played by the energy harvester nonlinearity.
Analysis of Divide & Conquer strategies for the 0-1 Minimization Knapsack Problem
Venue: arXiv cs.DM 2020
Year: 2020

We introduce and asses several Divide \& Conquer heuristic strategies aimed to solve large instances of the 0-1 Minimization Knapsack Problem. The method subdivides a large problem in two smaller ones (or recursive iterations of the same principle), to lower down the global computational complexity of the original problem, at the expense of a moderate loss of quality in the solution. Theoretical mathematical results are presented in order to guarantee an algorithmically successful application of the method and to suggest the potential strategies for its implementation. In contrast, due to the lack of theoretical results, the solution's quality deterioration is measured empirically by means of Monte Carlo simulations for several types and values of the chosen strategies. Finally, introducing parameters of efficiency we suggest the best strategies depending on the data input.
Healthy versus pathological learning transferability in shoulder muscle MRI segmentation using deep convolutional encoder-decoders
Venue: arXiv cs.CV 2020
Year: 2020

Automatic segmentation of pathological shoulder muscles in patients with musculo-skeletal diseases is a challenging task due to the huge variability in muscle shape, size, location, texture and injury. A reliable fully-automated segmentation method from magnetic resonance images could greatly help clinicians to plan therapeutic interventions and predict interventional outcomes while eliminating time consuming manual segmentation efforts. The purpose of this work is three-fold. First, we investigate the feasibility of pathological shoulder muscle segmentation using deep learning techniques, given a very limited amount of available annotated pediatric data. Second, we address the learning transferability from healthy to pathological data by comparing different learning schemes in terms of model generalizability. Third, extended versions of deep convolutional encoder-decoder architectures using encoders pre-trained on non-medical data are proposed to improve the segmentation accuracy. Methodological aspects are evaluated in a leave-one-out fashion on a dataset of 24 shoulder examinations from patients with obstetrical brachial plexus palsy and focus on 4 different muscles including deltoid as well as infraspinatus, supraspinatus and subscapularis from the rotator cuff. The most relevant segmentation model is partially pre-trained on ImageNet and jointly exploits inter-patient healthy and pathological annotated data. Its performance reaches Dice scores of 82.4%, 82.0%, 71.0% and 82.8% for deltoid, infraspinatus, supraspinatus and subscapularis muscles. Absolute surface estimation errors are all below 83mm$^2$ except for supraspinatus with 134.6mm$^2$. These contributions offer new perspectives for force inference in the context of musculo-skeletal disorder management.
Tendrils of Crime: Visualizing the Diffusion of Stolen Bitcoins
Venue: arXiv cs.CY 2020
Year: 2020

The first six months of 2018 saw cryptocurrency thefts of $761 million, and the technology is also the latest and greatest tool for money laundering. This increase in crime has caused both researchers and law enforcement to look for ways to trace criminal proceeds. Although tracing algorithms have improved recently, they still yield an enormous amount of data of which very few datapoints are relevant or interesting to investigators, let alone ordinary bitcoin owners interested in provenance. In this work we describe efforts to visualize relevant data on a blockchain. To accomplish this we come up with a graphical model to represent the stolen coins and then implement this using a variety of visualization techniques.
An in-place, subquadratic algorithm for permutation inversion
Venue: arXiv cs.DS 2020
Year: 2020

We assume the permutation $π$ is given by an $n$-element array in which the $i$-th element denotes the value $π(i)$. Constructing its inverse in-place (i.e. using $O(\log{n})$ bits of additional memory) can be achieved in linear time with a simple algorithm. Limiting the numbers that can be stored in our array to the range $[1...n]$ still allows a straightforward $O(n^2)$ time solution. The time complexity can be improved using randomization, but this only improves the expected, not the pessimistic running time. We present a deterministic algorithm that runs in $O(n^{3/2})$ time.
HyPar: Towards Hybrid Parallelism for Deep Learning Accelerator Array
Venue: arXiv cs.DC 2020
Year: 2020

With the rise of artificial intelligence in recent years, Deep Neural Networks (DNNs) have been widely used in many domains. To achieve high performance and energy efficiency, hardware acceleration (especially inference) of DNNs is intensively studied both in academia and industry. However, we still face two challenges: large DNN models and datasets, which incur frequent off-chip memory accesses; and the training of DNNs, which is not well-explored in recent accelerator designs. To truly provide high throughput and energy efficient acceleration for the training of deep and large models, we inevitably need to use multiple accelerators to explore the coarse-grain parallelism, compared to the fine-grain parallelism inside a layer considered in most of the existing architectures. It poses the key research question to seek the best organization of computation and dataflow among accelerators. In this paper, inspired by recent work in machine learning systems, we propose a solution HyPar to determine layer-wise parallelism for deep neural network training with an array of DNN accelerators. HyPar partitions the feature map tensors (input and output), the kernel tensors, the gradient tensors, and the error tensors for the DNN accelerators. A partition constitutes the choice of parallelism for weighted layers. The optimization target is to search a partition that minimizes the total communication during training a complete DNN. To solve this problem, we propose a communication model to explain the source and amount of communications. Then, we use a hierarchical layer-wise dynamic programming method to search for the partition for each layer.
Cost Sensitive Learning in the Presence of Symmetric Label Noise
Venue: arXiv cs.LG 2020
Year: 2020

In binary classification framework, we are interested in making cost sensitive label predictions in the presence of uniform/symmetric label noise. We first observe that $0$-$1$ Bayes classifiers are not (uniform) noise robust in cost sensitive setting. To circumvent this impossibility result, we present two schemes; unlike the existing methods, our schemes do not require noise rate. The first one uses $α$-weighted $γ$-uneven margin squared loss function, $l_{α, usq}$, which can handle cost sensitivity arising due to domain requirement (using user given $α$) or class imbalance (by tuning $γ$) or both. However, we observe that $l_{α, usq}$ Bayes classifiers are also not cost sensitive and noise robust. We show that regularized ERM of this loss function over the class of linear classifiers yields a cost sensitive uniform noise robust classifier as a solution of a system of linear equations. We also provide a performance bound for this classifier. The second scheme that we propose is a re-sampling based scheme that exploits the special structure of the uniform noise models and uses in-class probability $η$ estimates. Our computational experiments on some UCI datasets with class imbalance show that classifiers of our two schemes are on par with the existing methods and in fact better in some cases w.r.t. Accuracy and Arithmetic Mean, without using/tuning noise rate. We also consider other cost sensitive performance measures viz., F measure and Weighted Cost for evaluation. As our re-sampling scheme requires estimates of $η$, we provide a detailed comparative study of various $η$ estimation methods on synthetic datasets, w.r.t. half a dozen evaluation criterion. Also, we provide understanding on the interpretation of cost parameters $α$ and $γ$ using different synthetic data experiments.
On the Possibilities and Limitations of Multi-hop Reasoning Under Linguistic Imperfections
Venue: arXiv cs.CL 2020
Year: 2020

Systems for language understanding have become remarkably strong at overcoming linguistic imperfections in tasks involving phrase matching or simple reasoning. Yet, their accuracy drops dramatically as the number of reasoning steps increases. We present the first formal framework to study such empirical observations. It allows one to quantify the amount and effect of ambiguity, redundancy, incompleteness, and inaccuracy that the use of language introduces when representing a hidden conceptual space. The idea is to consider two interrelated spaces: a conceptual meaning space that is unambiguous and complete but hidden, and a linguistic space that captures a noisy grounding of the meaning space in the words of a language---the level at which all systems, whether neural or symbolic, operate. Applying this framework to a special class of multi-hop reasoning, namely the connectivity problem in graphs of relationships between concepts, we derive rigorous intuitions and impossibility results even under this simplified setting. For instance, if a query requires a moderately large (logarithmic) number of hops in the meaning graph, no reasoning system operating over a noisy graph grounded in language is likely to correctly answer it. This highlights a fundamental barrier that extends to a broader class of reasoning problems and systems, and suggests an alternative path forward: focusing on aligning the two spaces via richer representations, before investing in reasoning with many hops.
TraceCaps: A Capsule-based Neural Network for Semantic Segmentation
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we propose a capsule-based neural network model to solve the semantic segmentation problem. By taking advantage of the extractable part-whole dependencies available in capsule layers, we derive the probabilities of the class labels for individual capsules through a recursive, layer-by-layer procedure. We model this procedure as a traceback pipeline and take it as a central piece to build an end-to-end segmentation network. Under the proposed framework, image-level class labels and object boundaries are jointly sought in an explicit manner, which poses a significant advantage over the state-of-the-art fully convolutional network (FCN) solutions. With the capability to extracted part-whole information, our traceback pipeline can potentially be utilized as the building blocks to design interpretable neural networks. Experiments conducted on modified MNIST and neuroimages demonstrate that our model considerably enhance the segmentation performance compared to the leading FCN variants.
Review on Learning and Extracting Graph Features for Link Prediction
Venue: arXiv cs.SI 2020
Year: 2020

Link prediction in complex networks has attracted considerable attention from interdisciplinary research communities, due to its ubiquitous applications in biological networks, social networks, transportation networks, telecommunication networks, and, recently, knowledge graphs. Numerous studies utilized link prediction approaches in order sto find missing links or predict the likelihood of future links as well as employed for reconstruction networks, recommender systems, privacy control, etc. This work presents an extensive review of state-of-art methods and algorithms proposed on this subject and categorizes them into four main categories: similarity-based methods, probabilistic methods, relational models, and learning-based methods. Additionally, a collection of network data sets has been presented in this paper, which can be used in order to study link prediction. We conclude this study with a discussion of recent developments and future research directions.
Fast Deterministic Algorithms for Highly-Dynamic Networks
Venue: arXiv cs.DC 2020
Year: 2020

This paper provides an algorithmic framework for obtaining fast distributed algorithms for a highly-dynamic setting, in which *arbitrarily many* edge changes may occur in each round. Our algorithm significantly improves upon prior work in its combination of (1) having an $O(1)$ amortized time complexity, (2) using only $O(\log{n})$-bit messages, (3) not posing any restrictions on the dynamic behavior of the environment, (4) being deterministic, (5) having strong guarantees for intermediate solutions, and (6) being applicable for a wide family of tasks. The tasks for which we deduce such an algorithm are maximal matching, $(degree+1)$-coloring, 2-approximation for minimum weight vertex cover, and maximal independent set (which is the most subtle case). For some of these tasks, node insertions can also be among the allowed topology changes, and for some of them also abrupt node deletions.
Blind GB-PANDAS: A Blind Throughput-Optimal Load Balancing Algorithm for Affinity Scheduling
Venue: arXiv cs.PF 2020
Year: 2020

Dynamic affinity load balancing of multi-type tasks on multi-skilled servers, when the service rate of each task type on each of the servers is known and can possibly be different from each other, is an open problem for over three decades. The goal is to do task assignment on servers in a real time manner so that the system becomes stable, which means that the queue lengths do not diverge to infinity in steady state (throughput optimality), and the mean task completion time is minimized (delay optimality). The fluid model planning, Max-Weight, and c-$μ$-rule algorithms have theoretical guarantees on optimality in some aspects for the affinity problem, but they consider a complicated queueing structure and either require the task arrival rates, the service rates of tasks on servers, or both. In many cases that are discussed in the introduction section, both task arrival rates and service rates of different task types on different servers are unknown. In this work, the Blind GB-PANDAS algorithm is proposed which is completely blind to task arrival rates and service rates. Blind GB-PANDAS uses an exploration-exploitation approach for load balancing. We prove that Blind GB-PANDAS is throughput optimal under arbitrary and unknown distributions for service times of different task types on different servers and unknown task arrival rates. Blind GB-PANDAS desires to route an incoming task to the server with the minimum weighted-workload, but since the service rates are unknown, such routing of incoming tasks is not guaranteed which makes the throughput optimality analysis more complicated than the case where service rates are known. Our extensive experimental results reveal that Blind GB-PANDAS significantly outperforms existing methods in terms of mean task completion time at high loads.
Multi-band Weighted $l_p$ Norm Minimization for Image Denoising
Venue: arXiv cs.CV 2020
Year: 2020

Low rank matrix approximation (LRMA) has drawn increasing attention in recent years, due to its wide range of applications in computer vision and machine learning. However, LRMA, achieved by nuclear norm minimization (NNM), tends to over-shrink the rank components with the same threshold and ignore the differences between rank components. To address this problem, we propose a flexible and precise model named multi-band weighted $l_p$ norm minimization (MBWPNM). The proposed MBWPNM not only gives more accurate approximation with a Schatten $p$-norm, but also considers the prior knowledge where different rank components have different importance. We analyze the solution of MBWPNM and prove that MBWPNM is equivalent to a non-convex $l_p$ norm subproblems under certain weight condition, whose global optimum can be solved by a generalized soft-thresholding algorithm. We then adopt the MBWPNM algorithm to color and multispectral image denoising. Extensive experiments on additive white Gaussian noise removal and realistic noise removal demonstrate that the proposed MBWPNM achieves a better performance than several state-of-art algorithms.