January 30, 2020

3303 words 16 mins read

Paper Group ANR 320

MDFN: Multi-Scale Deep Feature Learning Network for Object Detection. Iterated two-phase local search for the Set-Union Knapsack Problem. Krylov Subspace Method for Nonlinear Dynamical Systems with Random Noise. Neuromorphic Acceleration for Approximate Bayesian Inference on Neural Networks via Permanent Dropout. The Optimal Approximation Factor in …

MDFN: Multi-Scale Deep Feature Learning Network for Object Detection


Title	MDFN: Multi-Scale Deep Feature Learning Network for Object Detection
Authors	Wenchi Ma, Yuanwei Wu, Feng Cen, Guanghui Wang
Abstract	This paper proposes an innovative object detector by leveraging deep features learned in high-level layers. Compared with features produced in earlier layers, the deep features are better at expressing semantic and contextual information. The proposed deep feature learning scheme shifts the focus from concrete features with details to abstract ones with semantic information. It considers not only individual objects and local contexts but also their relationships by building a multi-scale deep feature learning network (MDFN). MDFN efficiently detects the objects by introducing information square and cubic inception modules into the high-level layers, which employs parameter-sharing to enhance the computational efficiency. MDFN provides a multi-scale object detector by integrating multi-box, multi-scale and multi-level technologies. Although MDFN employs a simple framework with a relatively small base network (VGG-16), it achieves better or competitive detection results than those with a macro hierarchical structure that is either very deep or very wide for stronger ability of feature extraction. The proposed technique is evaluated extensively on KITTI, PASCAL VOC, and COCO datasets, which achieves the best results on KITTI and leading performance on PASCAL VOC and COCO. This study reveals that deep features provide prominent semantic information and a variety of contextual contents, which contribute to its superior performance in detecting small or occluded objects. In addition, the MDFN model is computationally efficient, making a good trade-off between the accuracy and speed.
Tasks	Object Detection
Published	2019-12-10
URL	https://arxiv.org/abs/1912.04514v1
PDF	https://arxiv.org/pdf/1912.04514v1.pdf
PWC	https://paperswithcode.com/paper/mdfn-multi-scale-deep-feature-learning
Repo
Framework

Iterated two-phase local search for the Set-Union Knapsack Problem


Title	Iterated two-phase local search for the Set-Union Knapsack Problem
Authors	Zequn Wei, Jin-Kao Hao
Abstract	The Set-union Knapsack Problem (SUKP) is a generalization of the popular 0-1 knapsack problem. Given a set of weighted elements and a set of items with profits where each item is composed of a subset of elements, the SUKP involves packing a subset of items in a capacity-constrained knapsack such that the total profit of the selected items is maximized while their weights do not exceed the knapsack capacity. In this work, we present an effective iterated two-phase local search algorithm for this NP-hard combinatorial optimization problem. The proposed algorithm iterates through two search phases: a local optima exploration phase that alternates between a variable neighborhood descent search and a tabu search to explore local optimal solutions, and a local optima escaping phase to drive the search to unexplored regions. We show the competitiveness of the algorithm compared to the state-of-the-art methods in the literature. Specifically, the algorithm discovers 18 improved best results (new lower bounds) for the 30 benchmark instances and matches the best-known results for the 12 remaining instances. We also report the first computational results with the general CPLEX solver, including 6 proven optimal solutions. Finally, we investigate the effectiveness of the key ingredients of the algorithm on its performance.
Tasks	Combinatorial Optimization
Published	2019-03-12
URL	http://arxiv.org/abs/1903.04966v2
PDF	http://arxiv.org/pdf/1903.04966v2.pdf
PWC	https://paperswithcode.com/paper/iterated-two-phase-local-search-for-the-set
Repo
Framework

Krylov Subspace Method for Nonlinear Dynamical Systems with Random Noise


Title	Krylov Subspace Method for Nonlinear Dynamical Systems with Random Noise
Authors	Yuka Hashimoto, Isao Ishikawa, Masahiro Ikeda, Yoichi Matsuo, Yoshinobu Kawahara
Abstract	Operator-theoretic analysis of nonlinear dynamical systems has attracted much attention in a variety of engineering and scientific fields, endowed with practical estimation methods using data such as dynamic mode decomposition. In this paper, we address a lifted representation of nonlinear dynamical systems with random noise based on transfer operators, and develop a novel Krylov subspace method for estimating the operators using finite data, with consideration of the unboundedness of operators. For this purpose, we first consider Perron-Frobenius operators with kernel-mean embeddings for such systems. We then extend the Arnoldi method, which is the most classical type of Kryov subspace method, so that it can be applied to the current case. Meanwhile, the Arnoldi method requires the assumption that the operator is bounded, which is not necessarily satisfied for transfer operators on nonlinear systems. We accordingly develop the shift-invert Arnoldi method for Perron-Frobenius operators to avoid this problem. Also, we describe an approach of evaluating predictive accuracy by estimated operators on the basis of the maximum mean discrepancy, which is applicable, for example, to anomaly detection in complex systems. The empirical performance of our methods is investigated using synthetic and real-world healthcare data.
Tasks	Anomaly Detection
Published	2019-09-09
URL	https://arxiv.org/abs/1909.03634v3
PDF	https://arxiv.org/pdf/1909.03634v3.pdf
PWC	https://paperswithcode.com/paper/krylov-subspace-method-for-nonlinear
Repo
Framework

Neuromorphic Acceleration for Approximate Bayesian Inference on Neural Networks via Permanent Dropout


Title	Neuromorphic Acceleration for Approximate Bayesian Inference on Neural Networks via Permanent Dropout
Authors	Nathan Wycoff, Prasanna Balaprakash, Fangfang Xia
Abstract	As neural networks have begun performing increasingly critical tasks for society, ranging from driving cars to identifying candidates for drug development, the value of their ability to perform uncertainty quantification (UQ) in their predictions has risen commensurately. Permanent dropout, a popular method for neural network UQ, involves injecting stochasticity into the inference phase of the model and creating many predictions for each of the test data. This shifts the computational and energy burden of deep neural networks from the training phase to the inference phase. Recent work has demonstrated near-lossless conversion of classical deep neural networks to their spiking counterparts. We use these results to demonstrate the feasibility of conducting the inference phase with permanent dropout on spiking neural networks, mitigating the technique’s computational and energy burden, which is essential for its use at scale or on edge platforms. We demonstrate the proposed approach via the Nengo spiking neural simulator on a combination drug therapy dataset for cancer treatment, where UQ is critical. Our results indicate that the spiking approximation gives a predictive distribution practically indistinguishable from that given by the classical network.
Tasks	Bayesian Inference
Published	2019-04-29
URL	http://arxiv.org/abs/1904.12904v1
PDF	http://arxiv.org/pdf/1904.12904v1.pdf
PWC	https://paperswithcode.com/paper/neuromorphic-acceleration-for-approximate
Repo
Framework

The Optimal Approximation Factor in Density Estimation


Title	The Optimal Approximation Factor in Density Estimation
Authors	Olivier Bousquet, Daniel Kane, Shay Moran
Abstract	Consider the following problem: given two arbitrary densities $q_1,q_2$ and a sample-access to an unknown target density $p$, find which of the $q_i$'s is closer to $p$ in total variation. A remarkable result due to Yatracos shows that this problem is tractable in the following sense: there exists an algorithm that uses $O(\epsilon^{-2})$ samples from $p$ and outputs~$q_i$ such that with high probability, $TV(q_i,p) \leq 3\cdot\mathsf{opt} + \epsilon$, where $\mathsf{opt}= \min{TV(q_1,p),TV(q_2,p)}$. Moreover, this result extends to any finite class of densities $\mathcal{Q}$: there exists an algorithm that outputs the best density in $\mathcal{Q}$ up to a multiplicative approximation factor of 3. We complement and extend this result by showing that: (i) the factor 3 can not be improved if one restricts the algorithm to output a density from $\mathcal{Q}$, and (ii) if one allows the algorithm to output arbitrary densities (e.g.\ a mixture of densities from $\mathcal{Q}$), then the approximation factor can be reduced to 2, which is optimal. In particular this demonstrates an advantage of improper learning over proper in this setup. We develop two approaches to achieve the optimal approximation factor of 2: an adaptive one and a static one. Both approaches are based on a geometric point of view of the problem and rely on estimating surrogate metrics to the total variation. Our sample complexity bounds exploit techniques from {\it Adaptive Data Analysis}.
Tasks	Density Estimation
Published	2019-02-10
URL	https://arxiv.org/abs/1902.05876v2
PDF	https://arxiv.org/pdf/1902.05876v2.pdf
PWC	https://paperswithcode.com/paper/the-optimal-approximation-factor-in-density
Repo
Framework

Similarity Kernel and Clustering via Random Projection Forests


Title	Similarity Kernel and Clustering via Random Projection Forests
Authors	Donghui Yan, Songxiang Gu, Ying Xu, Zhiwei Qin
Abstract	Similarity plays a fundamental role in many areas, including data mining, machine learning, statistics and various applied domains. Inspired by the success of ensemble methods and the flexibility of trees, we propose to learn a similarity kernel called rpf-kernel through random projection forests (rpForests). Our theoretical analysis reveals a highly desirable property of rpf-kernel: far-away (dissimilar) points have a low similarity value while nearby (similar) points would have a high similarity}, and the similarities have a native interpretation as the probability of points remaining in the same leaf nodes during the growth of rpForests. The learned rpf-kernel leads to an effective clustering algorithm–rpfCluster. On a wide variety of real and benchmark datasets, rpfCluster compares favorably to K-means clustering, spectral clustering and a state-of-the-art clustering ensemble algorithm–Cluster Forests. Our approach is simple to implement and readily adapt to the geometry of the underlying data. Given its desirable theoretical property and competitive empirical performance when applied to clustering, we expect rpf-kernel to be applicable to many problems of an unsupervised nature or as a regularizer in some supervised or weakly supervised settings.
Tasks
Published	2019-08-28
URL	https://arxiv.org/abs/1908.10506v1
PDF	https://arxiv.org/pdf/1908.10506v1.pdf
PWC	https://paperswithcode.com/paper/similarity-kernel-and-clustering-via-random
Repo
Framework

Meta-Sim: Learning to Generate Synthetic Datasets


Title	Meta-Sim: Learning to Generate Synthetic Datasets
Authors	Amlan Kar, Aayush Prakash, Ming-Yu Liu, Eric Cameracci, Justin Yuan, Matt Rusiniak, David Acuna, Antonio Torralba, Sanja Fidler
Abstract	Training models to high-end performance requires availability of large labeled datasets, which are expensive to get. The goal of our work is to automatically synthesize labeled datasets that are relevant for a downstream task. We propose Meta-Sim, which learns a generative model of synthetic scenes, and obtain images as well as its corresponding ground-truth via a graphics engine. We parametrize our dataset generator with a neural network, which learns to modify attributes of scene graphs obtained from probabilistic scene grammars, so as to minimize the distribution gap between its rendered outputs and target data. If the real dataset comes with a small labeled validation set, we additionally aim to optimize a meta-objective, i.e. downstream task performance. Experiments show that the proposed method can greatly improve content generation quality over a human-engineered probabilistic scene grammar, both qualitatively and quantitatively as measured by performance on a downstream task.
Tasks
Published	2019-04-25
URL	http://arxiv.org/abs/1904.11621v1
PDF	http://arxiv.org/pdf/1904.11621v1.pdf
PWC	https://paperswithcode.com/paper/meta-sim-learning-to-generate-synthetic
Repo
Framework

Fast Parallel Algorithms for Feature Selection


Title	Fast Parallel Algorithms for Feature Selection
Authors	Sharon Qian, Yaron Singer
Abstract	In this paper, we propose a new framework for designing fast parallel algorithms for fundamental statistical subset selection tasks that include feature selection and experimental design. Such tasks are known to be weakly submodular and are amenable to optimization via the standard greedy algorithm. Despite its desirable approximation guarantees, however, the greedy algorithm is inherently sequential and in the worst case, its parallel runtime is linear in the size of the data. Recently, there has been a surge of interest in a parallel optimization technique called adaptive sampling which produces solutions with desirable approximation guarantees for submodular maximization in exponentially faster parallel runtime. Unfortunately, we show that for general weakly submodular functions such accelerations are impossible. The major contribution in this paper is a novel relaxation of submodularity which we call differential submodularity. We first prove that differential submodularity characterizes objectives like feature selection and experimental design. We then design an adaptive sampling algorithm for differentially submodular functions whose parallel runtime is logarithmic in the size of the data and achieves strong approximation guarantees. Through experiments, we show the algorithm’s performance is competitive with state-of-the-art methods and obtains dramatic speedups for feature selection and experimental design problems.
Tasks	Combinatorial Optimization, Feature Selection
Published	2019-03-06
URL	https://arxiv.org/abs/1903.02656v2
PDF	https://arxiv.org/pdf/1903.02656v2.pdf
PWC	https://paperswithcode.com/paper/fast-parallel-algorithms-for-feature
Repo
Framework

Deep Generative Models for Reject Inference in Credit Scoring


Title	Deep Generative Models for Reject Inference in Credit Scoring
Authors	Rogelio A. Mancisidor, Michael Kampffmeyer, Kjersti Aas, Robert Jenssen
Abstract	Credit scoring models based on accepted applications may be biased and their consequences can have a statistical and economic impact. Reject inference is the process of attempting to infer the creditworthiness status of the rejected applications. In this research, we use deep generative models to develop two new semi-supervised Bayesian models for reject inference in credit scoring, in which we model the data generating process to be dependent on a Gaussian mixture. The goal is to improve the classification accuracy in credit scoring models by adding reject applications. Our proposed models infer the unknown creditworthiness of the rejected applications by exact enumeration of the two possible outcomes of the loan (default or non-default). The efficient stochastic gradient optimization technique used in deep generative models makes our models suitable for large data sets. Finally, the experiments in this research show that our proposed models perform better than classical and alternative machine learning models for reject inference in credit scoring.
Tasks
Published	2019-04-12
URL	http://arxiv.org/abs/1904.11376v1
PDF	http://arxiv.org/pdf/1904.11376v1.pdf
PWC	https://paperswithcode.com/paper/190411376
Repo
Framework

The ML-EM algorithm in continuum: sparse measure solutions


Title	The ML-EM algorithm in continuum: sparse measure solutions
Authors	Camille Pouchol, Olivier Verdier
Abstract	Linear inverse problems $A \mu = \delta$ with Poisson noise and non-negative unknown $\mu \geq 0$ are ubiquitous in applications, for instance in Positron Emission Tomography (PET) in medical imaging. The associated maximum likelihood problem is routinely solved using an expectation-maximisation algorithm (ML-EM). This typically results in images which look spiky, even with early stopping. We give an explanation for this phenomenon. We first regard the image $\mu$ as a measure. We prove that if the measurements $\delta$ are not in the cone ${A \mu, \mu \geq 0}$, which is typical of short exposure times, likelihood maximisers as well as ML-EM cluster points must be sparse, i.e., typically a sum of point masses. On the other hand, in the long exposure regime, we prove that cluster points of ML-EM will be measures without singular part. Finally, we provide concentration bounds for the probability to be in the sparse case.
Tasks
Published	2019-09-04
URL	https://arxiv.org/abs/1909.01966v2
PDF	https://arxiv.org/pdf/1909.01966v2.pdf
PWC	https://paperswithcode.com/paper/the-ml-em-algorithm-in-continuum-sparse
Repo
Framework

End-to-End Efficient Representation Learning via Cascading Combinatorial Optimization


Title	End-to-End Efficient Representation Learning via Cascading Combinatorial Optimization
Authors	Yeonwoo Jeong, Yoonsung Kim, Hyun Oh Song
Abstract	We develop hierarchically quantized efficient embedding representations for similarity-based search and show that this representation provides not only the state of the art performance on the search accuracy but also provides several orders of speed up during inference. The idea is to hierarchically quantize the representation so that the quantization granularity is greatly increased while maintaining the accuracy and keeping the computational complexity low. We also show that the problem of finding the optimal sparse compound hash code respecting the hierarchical structure can be optimized in polynomial time via minimum cost flow in an equivalent flow network. This allows us to train the method end-to-end in a mini-batch stochastic gradient descent setting. Our experiments on Cifar100 and ImageNet datasets show the state of the art search accuracy while providing several orders of magnitude search speedup respectively over exhaustive linear search over the dataset.
Tasks	Combinatorial Optimization, Quantization, Representation Learning
Published	2019-02-28
URL	http://arxiv.org/abs/1902.10990v2
PDF	http://arxiv.org/pdf/1902.10990v2.pdf
PWC	https://paperswithcode.com/paper/end-to-end-efficient-representation-learning
Repo
Framework

Optimal and Fast Real-time Resources Slicing with Deep Dueling Neural Networks


Title	Optimal and Fast Real-time Resources Slicing with Deep Dueling Neural Networks
Authors	Nguyen Van Huynh, Dinh Thai Hoang, Diep N. Nguyen, Eryk Dutkiewicz
Abstract	Effective network slicing requires an infrastructure/network provider to deal with the uncertain demand and real-time dynamics of network resource requests. Another challenge is the combinatorial optimization of numerous resources, e.g., radio, computing, and storage. This article develops an optimal and fast real-time resource slicing framework that maximizes the long-term return of the network provider while taking into account the uncertainty of resource demand from tenants. Specifically, we first propose a novel system model which enables the network provider to effectively slice various types of resources to different classes of users under separate virtual slices. We then capture the real-time arrival of slice requests by a semi-Markov decision process. To obtain the optimal resource allocation policy under the dynamics of slicing requests, e.g., uncertain service time and resource demands, a Q-learning algorithm is often adopted in the literature. However, such an algorithm is notorious for its slow convergence, especially for problems with large state/action spaces. This makes Q-learning practically inapplicable to our case in which multiple resources are simultaneously optimized. To tackle it, we propose a novel network slicing approach with an advanced deep learning architecture, called deep dueling that attains the optimal average reward much faster than the conventional Q-learning algorithm. This property is especially desirable to cope with real-time resource requests and the dynamic demands of users. Extensive simulations show that the proposed framework yields up to 40% higher long-term average return while being few thousand times faster, compared with state of the art network slicing approaches.
Tasks	Combinatorial Optimization, Q-Learning
Published	2019-02-26
URL	http://arxiv.org/abs/1902.09696v1
PDF	http://arxiv.org/pdf/1902.09696v1.pdf
PWC	https://paperswithcode.com/paper/optimal-and-fast-real-time-resources-slicing
Repo
Framework

First-Order Bayesian Regret Analysis of Thompson Sampling


Title	First-Order Bayesian Regret Analysis of Thompson Sampling
Authors	Sébastien Bubeck, Mark Sellke
Abstract	We address online combinatorial optimization when the player has a prior over the adversary’s sequence of losses. In this framework, Russo and Van Roy proposed an information-theoretic analysis of Thompson Sampling based on the {\em information ratio}, resulting in optimal worst-case regret bounds. In this paper we introduce three novel ideas to this line of work. First we propose a new quantity, the scale-sensitive information ratio, which allows us to obtain more refined first-order regret bounds (i.e., bounds of the form $\sqrt{L^}$ where $L^$ is the loss of the best combinatorial action). Second we replace the entropy over combinatorial actions by a coordinate entropy, which allows us to obtain the first optimal worst-case bound for Thompson Sampling in the combinatorial setting. Finally, we introduce a novel link between Bayesian agents and frequentist confidence intervals. Combining these ideas we show that the classical multi-armed bandit first-order regret bound $\tilde{O}(\sqrt{d L^})$ still holds true in the more challenging and more general semi-bandit scenario. This latter result improves the previous state of the art bound $\tilde{O}(\sqrt{(d+m^3)L^})$ by Lykouris, Sridharan and Tardos.
Tasks	Combinatorial Optimization
Published	2019-02-02
URL	https://arxiv.org/abs/1902.00681v2
PDF	https://arxiv.org/pdf/1902.00681v2.pdf
PWC	https://paperswithcode.com/paper/first-order-regret-analysis-of-thompson
Repo
Framework

Weakly-Supervised Spatio-Temporally Grounding Natural Sentence in Video


Title	Weakly-Supervised Spatio-Temporally Grounding Natural Sentence in Video
Authors	Zhenfang Chen, Lin Ma, Wenhan Luo, Kwan-Yee K. Wong
Abstract	In this paper, we address a novel task, namely weakly-supervised spatio-temporally grounding natural sentence in video. Specifically, given a natural sentence and a video, we localize a spatio-temporal tube in the video that semantically corresponds to the given sentence, with no reliance on any spatio-temporal annotations during training. First, a set of spatio-temporal tubes, referred to as instances, are extracted from the video. We then encode these instances and the sentence using our proposed attentive interactor which can exploit their fine-grained relationships to characterize their matching behaviors. Besides a ranking loss, a novel diversity loss is introduced to train the proposed attentive interactor to strengthen the matching behaviors of reliable instance-sentence pairs and penalize the unreliable ones. Moreover, we also contribute a dataset, called VID-sentence, based on the ImageNet video object detection dataset, to serve as a benchmark for our task. Extensive experimental results demonstrate the superiority of our model over the baseline approaches.
Tasks	Object Detection, Video Object Detection
Published	2019-06-06
URL	https://arxiv.org/abs/1906.02549v1
PDF	https://arxiv.org/pdf/1906.02549v1.pdf
PWC	https://paperswithcode.com/paper/weakly-supervised-spatio-temporally-grounding
Repo
Framework

Federated Generative Privacy


Title	Federated Generative Privacy
Authors	Aleksei Triastcyn, Boi Faltings
Abstract	In this paper, we propose FedGP, a framework for privacy-preserving data release in the federated learning setting. We use generative adversarial networks, generator components of which are trained by FedAvg algorithm, to draw privacy-preserving artificial data samples and empirically assess the risk of information disclosure. Our experiments show that FedGP is able to generate labelled data of high quality to successfully train and validate supervised models. Finally, we demonstrate that our approach significantly reduces vulnerability of such models to model inversion attacks.
Tasks
Published	2019-10-18
URL	https://arxiv.org/abs/1910.08385v1
PDF	https://arxiv.org/pdf/1910.08385v1.pdf
PWC	https://paperswithcode.com/paper/federated-generative-privacy
Repo
Framework