January 29, 2020

3484 words 17 mins read

Paper Group ANR 597

A Direct $\tilde{O}(1/ε)$ Iteration Parallel Algorithm for Optimal Transport. Sampling Strategies for GAN Synthetic Data. The Labeling Distribution Matrix (LDM): A Tool for Estimating Machine Learning Algorithm Capacity. Resource Abstraction for Reinforcement Learning in Multiagent Congestion Problems. Topological Data Analysis of Time Series Data …

A Direct $\tilde{O}(1/ε)$ Iteration Parallel Algorithm for Optimal Transport


Title	A Direct $\tilde{O}(1/ε)$ Iteration Parallel Algorithm for Optimal Transport
Authors	Arun Jambulapati, Aaron Sidford, Kevin Tian
Abstract	Optimal transportation, or computing the Wasserstein or ``earth mover’s’’ distance between two distributions, is a fundamental primitive which arises in many learning and statistical settings. We give an algorithm which solves this problem to additive $\epsilon$ with $\tilde{O}(1/\epsilon)$ parallel depth, and $\tilde{O}\left(n^2/\epsilon\right)$ work. Barring a breakthrough on a long-standing algorithmic open problem, this is optimal for first-order methods. Blanchet et. al. ‘18, Quanrud ‘19 obtained similar runtimes through reductions to positive linear programming and matrix scaling. However, these reduction-based algorithms use complicated subroutines which may be deemed impractical due to requiring solvers for second-order iterations (matrix scaling) or non-parallelizability (positive LP). The fastest practical algorithms run in time $\tilde{O}(\min(n^2 / \epsilon^2, n^{2.5} / \epsilon))$ (Dvurechensky et. al. ‘18, Lin et. al. ‘19). We bridge this gap by providing a parallel, first-order, $\tilde{O}(1/\epsilon)$ iteration algorithm without worse dependence on dimension, and provide preliminary experimental evidence that our algorithm may enjoy improved practical performance. We obtain this runtime via a primal-dual extragradient method, motivated by recent theoretical improvements to maximum flow (Sherman ‘17). \|
Tasks
Published	2019-06-03
URL	https://arxiv.org/abs/1906.00618v1
PDF	https://arxiv.org/pdf/1906.00618v1.pdf
PWC	https://paperswithcode.com/paper/190600618
Repo
Framework

Sampling Strategies for GAN Synthetic Data


Title	Sampling Strategies for GAN Synthetic Data
Authors	Binod Bhattarai, Seungryul Baek, Rumeysa Bodur, Tae-Kyun Kim
Abstract	Generative Adversarial Networks (GANs) have been used widely to generate large volumes of synthetic data. This data is being utilized for augmenting with real examples in order to train deep Convolutional Neural Networks (CNNs). Studies have shown that the generated examples lack sufficient realism to train deep CNNs and are poor in diversity. Unlike previous studies of randomly augmenting the synthetic data with real data, we present our simple, effective and easy to implement synthetic data sampling methods to train deep CNNs more efficiently and accurately. To this end, we propose to maximally utilize the parameters learned during training of the GAN itself. These include discriminator’s realism confidence score and the confidence on the target label of the synthetic data. In addition to this, we explore reinforcement learning (RL) to automatically search a subset of meaningful synthetic examples from a large pool of GAN synthetic data. We evaluate our method on two challenging face attribute classification data sets viz. AffectNet and CelebA. Our extensive experiments clearly demonstrate the need of sampling synthetic data before augmentation, which also improves the performance of one of the state-of-the-art deep CNNs in vitro.
Tasks
Published	2019-09-10
URL	https://arxiv.org/abs/1909.04689v1
PDF	https://arxiv.org/pdf/1909.04689v1.pdf
PWC	https://paperswithcode.com/paper/sampling-strategies-for-gan-synthetic-data
Repo
Framework

The Labeling Distribution Matrix (LDM): A Tool for Estimating Machine Learning Algorithm Capacity


Title	The Labeling Distribution Matrix (LDM): A Tool for Estimating Machine Learning Algorithm Capacity
Authors	Pedro Sandoval Segura, Julius Lauw, Daniel Bashir, Kinjal Shah, Sonia Sehra, Dominique Macias, George Montanez
Abstract	Algorithm performance in supervised learning is a combination of memorization, generalization, and luck. By estimating how much information an algorithm can memorize from a dataset, we can set a lower bound on the amount of performance due to other factors such as generalization and luck. With this goal in mind, we introduce the Labeling Distribution Matrix (LDM) as a tool for estimating the capacity of learning algorithms. The method attempts to characterize the diversity of possible outputs by an algorithm for different training datasets, using this to measure algorithm flexibility and responsiveness to data. We test the method on several supervised learning algorithms, and find that while the results are not conclusive, the LDM does allow us to gain potentially valuable insight into the prediction behavior of algorithms. We also introduce the Label Recorder as an additional tool for estimating algorithm capacity, with more promising initial results.
Tasks
Published	2019-12-23
URL	https://arxiv.org/abs/1912.10597v2
PDF	https://arxiv.org/pdf/1912.10597v2.pdf
PWC	https://paperswithcode.com/paper/the-labeling-distribution-matrix-ldm-a-tool
Repo
Framework

Resource Abstraction for Reinforcement Learning in Multiagent Congestion Problems


Title	Resource Abstraction for Reinforcement Learning in Multiagent Congestion Problems
Authors	Kleanthis Malialis, Sam Devlin, Daniel Kudenko
Abstract	Real-world congestion problems (e.g. traffic congestion) are typically very complex and large-scale. Multiagent reinforcement learning (MARL) is a promising candidate for dealing with this emerging complexity by providing an autonomous and distributed solution to these problems. However, there are three limiting factors that affect the deployability of MARL approaches to congestion problems. These are learning time, scalability and decentralised coordination i.e. no communication between the learning agents. In this paper we introduce Resource Abstraction, an approach that addresses these challenges by allocating the available resources into abstract groups. This abstraction creates new reward functions that provide a more informative signal to the learning agents and aid the coordination amongst them. Experimental work is conducted on two benchmark domains from the literature, an abstract congestion problem and a realistic traffic congestion problem. The current state-of-the-art for solving multiagent congestion problems is a form of reward shaping called difference rewards. We show that the system using Resource Abstraction significantly improves the learning speed and scalability, and achieves the highest possible or near-highest joint performance/social welfare for both congestion problems in large-scale scenarios involving up to 1000 reinforcement learning agents.
Tasks
Published	2019-03-13
URL	http://arxiv.org/abs/1903.05431v1
PDF	http://arxiv.org/pdf/1903.05431v1.pdf
PWC	https://paperswithcode.com/paper/resource-abstraction-for-reinforcement
Repo
Framework

Topological Data Analysis of Time Series Data for B2B Customer Relationship Management


Title	Topological Data Analysis of Time Series Data for B2B Customer Relationship Management
Authors	Rodrigo Rivera-Castro, Polina Pilyugina, Alexander Pletnev, Ivan Maksimov, Wanyi Wyz, Evgeny Burnaev
Abstract	Topological Data Analysis (TDA) is a recent approach to analyze data sets from the perspective of their topological structure. Its use for time series data has been limited to the field of financial time series primarily and as a method for feature generation in machine learning applications. In this work, TDA is presented as a technique to gain additional understanding of the customers’ loyalty for business-to-business customer relationship management. Increasing loyalty and strengthening relationships with key accounts remain an active topic of discussion both for researchers and managers. Using two public and two proprietary data sets of commercial data, this research shows that the technique enables analysts to better understand their customer base and identify prospective opportunities. In addition, the approach can be used as a clustering method to increase the accuracy of a predictive model for loyalty scoring. This work thus seeks to introduce TDA as a viable tool for data analysis to the quantitate marketing practitioner.
Tasks	Time Series, Topological Data Analysis
Published	2019-05-26
URL	https://arxiv.org/abs/1906.03956v2
PDF	https://arxiv.org/pdf/1906.03956v2.pdf
PWC	https://paperswithcode.com/paper/topological-data-analysis-of-time-series-data
Repo
Framework

Adaptive and Efficient Algorithms for Tracking the Best Expert


Title	Adaptive and Efficient Algorithms for Tracking the Best Expert
Authors	Shiyin Lu, Lijun Zhang
Abstract	In this paper, we consider the problem of prediction with expert advice in dynamic environments. We choose tracking regret as the performance metric and develop two adaptive and efficient algorithms with data-dependent tracking regret bounds. The first algorithm achieves a second-order tracking regret bound, which improves existing first-order bounds. The second algorithm enjoys a path-length bound, which is generally not comparable to the second-order bound but offers advantages in slowly moving environments. Both algorithms are developed under the online mirror descent framework and draw inspiration from existing algorithms that attain data-dependent bounds of static regret. The key idea is to use a clipped simplex in the updating step of online mirror descent. Finally, we extend our algorithms and analysis to online matrix prediction and provide the first data-dependent tracking regret bound for this problem.
Tasks
Published	2019-09-05
URL	https://arxiv.org/abs/1909.02187v2
PDF	https://arxiv.org/pdf/1909.02187v2.pdf
PWC	https://paperswithcode.com/paper/more-adaptive-algorithms-for-tracking-the
Repo
Framework

Non-Asymptotic Analysis of Monte Carlo Tree Search


Title	Non-Asymptotic Analysis of Monte Carlo Tree Search
Authors	Devavrat Shah, Qiaomin Xie, Zhi Xu
Abstract	In this work, we consider the popular tree-based search strategy within the framework of reinforcement learning, the Monte Carlo Tree Search (MCTS), in the context of infinite-horizon discounted cost Markov Decision Process (MDP). While MCTS is believed to provide an approximate value function for a given state with enough simulations, the claimed proof in the seminal works is incomplete. This is due to the fact that the variant, the Upper Confidence Bound for Trees (UCT), analyzed in prior works utilizes “logarithmic” bonus term for balancing exploration and exploitation within the tree-based search, following the insights from stochastic multi-arm bandit (MAB) literature. In effect, such an approach assumes that the regret of the underlying recursively dependent non-stationary MABs concentrates around their mean exponentially in the number of steps, which is unlikely to hold as pointed out in literature, even for stationary MABs. As the key contribution of this work, we establish polynomial concentration property of regret for a class of non-stationary MAB. This in turn establishes that the MCTS with appropriate polynomial rather than logarithmic bonus term in UCB has the claimed property. Using this as a building block, we argue that MCTS, combined with nearest neighbor supervised learning, acts as a “policy improvement” operator: it iteratively improves value function approximation for all states, due to combining with supervised learning, despite evaluating at only finitely many states. In effect, we establish that to learn an $\varepsilon$ approximation of the value function with respect to $\ell_\infty$ norm, MCTS combined with nearest neighbor requires a sample size scaling as $\widetilde{O}\big(\varepsilon^{-(d+4)}\big)$, where $d$ is the dimension of the state space. This is nearly optimal due to a minimax lower bound of $\widetilde{\Omega}\big(\varepsilon^{-(d+2)}\big)$.
Tasks
Published	2019-02-14
URL	https://arxiv.org/abs/1902.05213v4
PDF	https://arxiv.org/pdf/1902.05213v4.pdf
PWC	https://paperswithcode.com/paper/on-reinforcement-learning-using-monte-carlo
Repo
Framework

Automatic Diagnosis of the Short-Duration 12-Lead ECG using a Deep Neural Network: the CODE Study


Title	Automatic Diagnosis of the Short-Duration 12-Lead ECG using a Deep Neural Network: the CODE Study
Authors	Antônio H. Ribeiro, Manoel Horta Ribeiro, Gabriela M. M. Paixão, Derick M. Oliveira, Paulo R. Gomes, Jéssica A. Canazart, Milton P. S. Ferreira, Carl R. Andersson, Peter W. Macfarlane, Wagner Meira Jr., Thomas B. Schön, Antonio Luiz P. Ribeiro
Abstract	We present a Deep Neural Network (DNN) model for predicting electrocardiogram (ECG) abnormalities in short-duration 12-lead ECG recordings. The analysis of the digital ECG obtained in a clinical setting can provide a full evaluation of the cardiac electrical activity and have not been studied in an end-to-end machine learning scenario. Using the database of the Telehealth Network of Minas Gerais, under the scope of the CODE (Clinical Outcomes in Digital Electrocardiology) study, we built a novel dataset with more than 2 million ECG tracings, orders of magnitude larger than those used in previous studies. Moreover, our dataset is more realistic, as it consists of 12-lead ECGs recorded during standard in-clinic exams. Using this data, we trained a residual neural network with 9 convolutional layers to map ECG signals with a duration of 7 to 10 seconds into 6 different classes of ECG abnormalities. High-performance measures were obtained for all ECG abnormalities, with F1 scores above $80%$ and specificity indexes over $99%$. We compare the performance with cardiology and emergency resident medical doctors as well as medical students and, considering the F1 score, the DNN matches or outperforms the medical residents and students for all abnormalities. These results indicate that end-to-end automatic ECG analysis based on DNNs, previously used only in a single-lead setup, generalizes well to the 12-lead ECG. This is an important result in that it takes this technology much closer to standard clinical practice.
Tasks	ECG Classification, Electrocardiography (ECG)
Published	2019-04-02
URL	http://arxiv.org/abs/1904.01949v1
PDF	http://arxiv.org/pdf/1904.01949v1.pdf
PWC	https://paperswithcode.com/paper/automatic-diagnosis-of-the-short-duration-12
Repo
Framework

Comparison of D-Wave Quantum Annealing and Classical Simulated Annealing for Local Minima Determination


Title	Comparison of D-Wave Quantum Annealing and Classical Simulated Annealing for Local Minima Determination
Authors	Yaroslav Koshka, M. A. Novotny
Abstract	Restricted Boltzmann Machines trained with different numbers of iterations were used to provide a diverse set of energy functions each containing many local valleys (LVs) with different energies, widths, escape barrier heights, etc. They were used to verify the previously reported possibility of using the D-Wave quantum annealer (QA) to find potentially important LVs in the energy functions of Ising spin glasses that may be missed by classical searches. For classical search, extensive simulated annealing (SA) was conducted to find as many LVs as possible regardless of the computational cost. SA was conducted long enough to ensure that the number of SA-found LVs approaches that and eventually significantly exceeds the number of the LVs found by a single call submitted to the D-Wave. Even after a prohibitively long SA search, as many as 30-50% of the D-Wave-found LVs remained not found by the SA. In order to establish if LVs found only by the D-Wave represent potentially important regions of the configuration space, they were compared to those that were found by both techniques. While the LVs found by the D-Wave but missed by SA predominantly had higher energies and lower escape barriers, there was a significant fraction having intermediate values of the energy and barrier height. With respect to most other important LV parameters, the LVs found only by the D-Wave were distributed in a wide range of the parameters’ values. It was established that for large or small, shallow or deep, wide or narrow LVs, the LVs found only by the D-Wave are distinguished by a few-times smaller size of the LV basin of attraction (BoA). Apparently, the size of the BoA is not or at least is less important for QA search compared to the classical search, allowing QA to easily find many potentially important (e.g., wide and deep) LVs missed by even prohibitively lengthy classical searches.
Tasks
Published	2019-11-08
URL	https://arxiv.org/abs/1911.03338v1
PDF	https://arxiv.org/pdf/1911.03338v1.pdf
PWC	https://paperswithcode.com/paper/comparison-of-d-wave-quantum-annealing-and
Repo
Framework

A General Spatio-Temporal Clustering-Based Non-local Formulation for Multiscale Modeling of Compartmentalized Reservoirs


Title	A General Spatio-Temporal Clustering-Based Non-local Formulation for Multiscale Modeling of Compartmentalized Reservoirs
Authors	Soheil Esmaeilzadeh, Amir Salehi, Gill Hetz, Feyisayo Olalotiti-lawal, Hamed Darabi, David Castineira
Abstract	Representing the reservoir as a network of discrete compartments with neighbor and non-neighbor connections is a fast, yet accurate method for analyzing oil and gas reservoirs. Automatic and rapid detection of coarse-scale compartments with distinct static and dynamic properties is an integral part of such high-level reservoir analysis. In this work, we present a hybrid framework specific to reservoir analysis for an automatic detection of clusters in space using spatial and temporal field data, coupled with a physics-based multiscale modeling approach. In this work a novel hybrid approach is presented in which we couple a physics-based non-local modeling framework with data-driven clustering techniques to provide a fast and accurate multiscale modeling of compartmentalized reservoirs. This research also adds to the literature by presenting a comprehensive work on spatio-temporal clustering for reservoir studies applications that well considers the clustering complexities, the intrinsic sparse and noisy nature of the data, and the interpretability of the outcome. Keywords: Artificial Intelligence; Machine Learning; Spatio-Temporal Clustering; Physics-Based Data-Driven Formulation; Multiscale Modeling
Tasks
Published	2019-04-28
URL	http://arxiv.org/abs/1904.13236v1
PDF	http://arxiv.org/pdf/1904.13236v1.pdf
PWC	https://paperswithcode.com/paper/a-general-spatio-temporal-clustering-based
Repo
Framework

NPTC-net: Narrow-Band Parallel Transport Convolutional Neural Network on Point Clouds


Title	NPTC-net: Narrow-Band Parallel Transport Convolutional Neural Network on Point Clouds
Authors	Pengfei Jin, Tianhao Lai, Rongjie Lai, Bin Dong
Abstract	Convolution plays a crucial role in various applications in signal and image processing, analysis and recognition. It is also the main building block of convolution neural networks (CNNs). Designing appropriate convolution neural networks on manifold-structured point clouds can inherit and empower recent advances of CNNs to analyzing and processing point cloud data. However, one of the major challenges is to define a proper way to “sweep” filters through the point cloud as a natural generalization of the planar convolution and to reflect the point cloud’s geometry at the same time. In this paper, we consider generalizing convolution by adapting parallel transport on the point cloud. Inspired by a triangulated surface based method [Stefan C. Schonsheck, Bin Dong, and Rongjie Lai, arXiv:1805.07857.], we propose the Narrow-Band Parallel Transport Convolution (NPTC) using a specifically defined connection on a voxelized narrow-band approximation of point cloud data. With that, we further propose a deep convolutional neural network based on NPTC (called NPTC-net) for point cloud classification and segmentation. Comprehensive experiments show that the proposed NPTC-net achieves similar or better results than current state-of-the-art methods on point clouds classification and segmentation.
Tasks
Published	2019-05-29
URL	https://arxiv.org/abs/1905.12218v2
PDF	https://arxiv.org/pdf/1905.12218v2.pdf
PWC	https://paperswithcode.com/paper/nptc-net-narrow-band-parallel-transport
Repo
Framework

On Inductive Biases in Deep Reinforcement Learning


Title	On Inductive Biases in Deep Reinforcement Learning
Authors	Matteo Hessel, Hado van Hasselt, Joseph Modayil, David Silver
Abstract	Many deep reinforcement learning algorithms contain inductive biases that sculpt the agent’s objective and its interface to the environment. These inductive biases can take many forms, including domain knowledge and pretuned hyper-parameters. In general, there is a trade-off between generality and performance when algorithms use such biases. Stronger biases can lead to faster learning, but weaker biases can potentially lead to more general algorithms. This trade-off is important because inductive biases are not free; substantial effort may be required to obtain relevant domain knowledge or to tune hyper-parameters effectively. In this paper, we re-examine several domain-specific components that bias the objective and the environmental interface of common deep reinforcement learning agents. We investigated whether the performance deteriorates when these components are replaced with adaptive solutions from the literature. In our experiments, performance sometimes decreased with the adaptive components, as one might expect when comparing to components crafted for the domain, but sometimes the adaptive components performed better. We investigated the main benefit of having fewer domain-specific components, by comparing the learning performance of the two systems on a different set of continuous control problems, without additional tuning of either system. As hypothesized, the system with adaptive components performed better on many of the new tasks.
Tasks	Continuous Control
Published	2019-07-05
URL	https://arxiv.org/abs/1907.02908v1
PDF	https://arxiv.org/pdf/1907.02908v1.pdf
PWC	https://paperswithcode.com/paper/on-inductive-biases-in-deep-reinforcement
Repo
Framework

Towards better healthcare: What could and should be automated?


Title	Towards better healthcare: What could and should be automated?
Authors	Wolfgang Frühwirt, Paul Duckworth
Abstract	While artificial intelligence (AI) and other automation technologies might lead to enormous progress in healthcare, they may also have undesired consequences for people working in the field. In this interdisciplinary study, we capture empirical evidence of not only what healthcare work could be automated, but also what should be automated. We quantitatively investigate these research questions by utilizing probabilistic machine learning models trained on thousands of ratings, provided by both healthcare practitioners and automation experts. Based on our findings, we present an analytical tool (Automatability-Desirability Matrix) to support policymakers and organizational leaders in developing practical strategies on how to harness the positive power of automation technologies, while accompanying change and empowering stakeholders in a participatory fashion.
Tasks
Published	2019-10-21
URL	https://arxiv.org/abs/1910.09444v1
PDF	https://arxiv.org/pdf/1910.09444v1.pdf
PWC	https://paperswithcode.com/paper/towards-better-healthcare-what-could-and
Repo
Framework

Artificial Neural Network Surrogate Modeling of Oil Reservoir: a Case Study


Title	Artificial Neural Network Surrogate Modeling of Oil Reservoir: a Case Study
Authors	Oleg Sudakov, Dmitri Koroteev, Boris Belozerov, Evgeny Burnaev
Abstract	We develop a data-driven model, introducing recent advances in machine learning to reservoir simulation. We use a conventional reservoir modeling tool to generate training set and a special ensemble of artificial neural networks (ANNs) to build a predictive model. The ANN-based model allows to reproduce the time dependence of fluids and pressure distribution within the computational cells of the reservoir model. We compare the performance of the ANN-based model with conventional reservoir modeling and illustrate that ANN-based model (1) is able to capture all the output parameters of the conventional model with very high accuracy and (2) demonstrate much higher computational performance. We finally elaborate on further options for research and developments within the area of reservoir modeling.
Tasks
Published	2019-05-20
URL	https://arxiv.org/abs/1905.07859v1
PDF	https://arxiv.org/pdf/1905.07859v1.pdf
PWC	https://paperswithcode.com/paper/artificial-neural-network-surrogate-modeling
Repo
Framework

Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimization


Title	Momentum Schemes with Stochastic Variance Reduction for Nonconvex Composite Optimization
Authors	Yi Zhou, Zhe Wang, Kaiyi Ji, Yingbin Liang, Vahid Tarokh
Abstract	Two new stochastic variance-reduced algorithms named SARAH and SPIDER have been recently proposed, and SPIDER has been shown to achieve a near-optimal gradient oracle complexity for nonconvex optimization. However, the theoretical advantage of SPIDER does not lead to substantial improvement of practical performance over SVRG. To address this issue, momentum technique can be a good candidate to improve the performance of SPIDER. However, existing momentum schemes used in variance-reduced algorithms are designed specifically for convex optimization, and are not applicable to nonconvex scenarios. In this paper, we develop novel momentum schemes with flexible coefficient settings to accelerate SPIDER for nonconvex and nonsmooth composite optimization, and show that the resulting algorithms achieve the near-optimal gradient oracle complexity for achieving a generalized first-order stationary condition. Furthermore, we generalize our algorithm to online nonconvex and nonsmooth optimization, and establish an oracle complexity result that matches the state-of-the-art. Our extensive experiments demonstrate the superior performance of our proposed algorithm over other stochastic variance-reduced algorithms.
Tasks
Published	2019-02-07
URL	https://arxiv.org/abs/1902.02715v3
PDF	https://arxiv.org/pdf/1902.02715v3.pdf
PWC	https://paperswithcode.com/paper/momentum-schemes-with-stochastic-variance
Repo
Framework