October 20, 2019

3225 words 16 mins read

Paper Group ANR 11

What Is It Like Down There? Generating Dense Ground-Level Views and Image Features From Overhead Imagery Using Conditional Generative Adversarial Networks. Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval. End-to-End Race Driving with Deep Reinforcement Learning. Selection Problems in the Presence o …

What Is It Like Down There? Generating Dense Ground-Level Views and Image Features From Overhead Imagery Using Conditional Generative Adversarial Networks


Title	What Is It Like Down There? Generating Dense Ground-Level Views and Image Features From Overhead Imagery Using Conditional Generative Adversarial Networks
Authors	Xueqing Deng, Yi Zhu, Shawn Newsam
Abstract	This paper investigates conditional generative adversarial networks (cGANs) to overcome a fundamental limitation of using geotagged media for geographic discovery, namely its sparse and uneven spatial distribution. We train a cGAN to generate ground-level views of a location given overhead imagery. We show the “fake” ground-level images are natural looking and are structurally similar to the real images. More significantly, we show the generated images are representative of the locations and that the representations learned by the cGANs are informative. In particular, we show that dense feature maps generated using our framework are more effective for land-cover classification than approaches which spatially interpolate features extracted from sparse ground-level images. To our knowledge, ours is the first work to use cGANs to generate ground-level views given overhead imagery and to explore the benefits of the learned representations.
Tasks
Published	2018-06-13
URL	http://arxiv.org/abs/1806.05129v2
PDF	http://arxiv.org/pdf/1806.05129v2.pdf
PWC	https://paperswithcode.com/paper/what-is-it-like-down-there-generating-dense
Repo
Framework

Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval


Title	Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval
Authors	Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma
Abstract	This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest $\mathbf{x}^{\natural}\in\mathbb{R}^{n}$ from $m$ quadratic equations/samples $y_{i}=(\mathbf{a}_{i}^{\top}\mathbf{x}^{\natural})^{2}$, $1\leq i\leq m$. This problem, also dubbed as phase retrieval, spans multiple domains including physical sciences and machine learning. We investigate the efficiency of gradient descent (or Wirtinger flow) designed for the nonconvex least squares problem. We prove that under Gaussian designs, gradient descent — when randomly initialized — yields an $\epsilon$-accurate solution in $O\big(\log n+\log(1/\epsilon)\big)$ iterations given nearly minimal samples, thus achieving near-optimal computational and sample complexities at once. This provides the first global convergence guarantee concerning vanilla gradient descent for phase retrieval, without the need of (i) carefully-designed initialization, (ii) sample splitting, or (iii) sophisticated saddle-point escaping schemes. All of these are achieved by exploiting the statistical models in analyzing optimization algorithms, via a leave-one-out approach that enables the decoupling of certain statistical dependency between the gradient descent iterates and the data.
Tasks
Published	2018-03-21
URL	http://arxiv.org/abs/1803.07726v2
PDF	http://arxiv.org/pdf/1803.07726v2.pdf
PWC	https://paperswithcode.com/paper/gradient-descent-with-random-initialization
Repo
Framework

End-to-End Race Driving with Deep Reinforcement Learning


Title	End-to-End Race Driving with Deep Reinforcement Learning
Authors	Maximilian Jaritz, Raoul de Charette, Marin Toromanoff, Etienne Perot, Fawzi Nashashibi
Abstract	We present research using the latest reinforcement learning algorithm for end-to-end driving without any mediated perception (object recognition, scene understanding). The newly proposed reward and learning strategies lead together to faster convergence and more robust driving using only RGB image from a forward facing camera. An Asynchronous Actor Critic (A3C) framework is used to learn the car control in a physically and graphically realistic rally game, with the agents evolving simultaneously on tracks with a variety of road structures (turns, hills), graphics (seasons, location) and physics (road adherence). A thorough evaluation is conducted and generalization is proven on unseen tracks and using legal speed limits. Open loop tests on real sequences of images show some domain adaption capability of our method.
Tasks	Domain Adaptation, Object Recognition, Scene Understanding
Published	2018-07-06
URL	http://arxiv.org/abs/1807.02371v2
PDF	http://arxiv.org/pdf/1807.02371v2.pdf
PWC	https://paperswithcode.com/paper/end-to-end-race-driving-with-deep
Repo
Framework

Selection Problems in the Presence of Implicit Bias


Title	Selection Problems in the Presence of Implicit Bias
Authors	Jon Kleinberg, Manish Raghavan
Abstract	Over the past two decades, the notion of implicit bias has come to serve as an important component in our understanding of discrimination in activities such as hiring, promotion, and school admissions. Research on implicit bias posits that when people evaluate others – for example, in a hiring context – their unconscious biases about membership in particular groups can have an effect on their decision-making, even when they have no deliberate intention to discriminate against members of these groups. A growing body of experimental work has pointed to the effect that implicit bias can have in producing adverse outcomes. Here we propose a theoretical model for studying the effects of implicit bias on selection decisions, and a way of analyzing possible procedural remedies for implicit bias within this model. A canonical situation represented by our model is a hiring setting: a recruiting committee is trying to choose a set of finalists to interview among the applicants for a job, evaluating these applicants based on their future potential, but their estimates of potential are skewed by implicit bias against members of one group. In this model, we show that measures such as the Rooney Rule, a requirement that at least one of the finalists be chosen from the affected group, can not only improve the representation of this affected group, but also lead to higher payoffs in absolute terms for the organization performing the recruiting. However, identifying the conditions under which such measures can lead to improved payoffs involves subtle trade-offs between the extent of the bias and the underlying distribution of applicant characteristics, leading to novel theoretical questions about order statistics in the presence of probabilistic side information.
Tasks	Decision Making
Published	2018-01-04
URL	http://arxiv.org/abs/1801.03533v1
PDF	http://arxiv.org/pdf/1801.03533v1.pdf
PWC	https://paperswithcode.com/paper/selection-problems-in-the-presence-of
Repo
Framework

Helix: Holistic Optimization for Accelerating Iterative Machine Learning


Title	Helix: Holistic Optimization for Accelerating Iterative Machine Learning
Authors	Doris Xin, Stephen Macke, Litian Ma, Jialin Liu, Shuchen Song, Aditya Parameswaran
Abstract	Machine learning workflow development is a process of trial-and-error: developers iterate on workflows by testing out small modifications until the desired accuracy is achieved. Unfortunately, existing machine learning systems focus narrowly on model training—a small fraction of the overall development time—and neglect to address iterative development. We propose Helix, a machine learning system that optimizes the execution across iterations—intelligently caching and reusing, or recomputing intermediates as appropriate. Helix captures a wide variety of application needs within its Scala DSL, with succinct syntax defining unified processes for data preprocessing, model specification, and learning. We demonstrate that the reuse problem can be cast as a Max-Flow problem, while the caching problem is NP-Hard. We develop effective lightweight heuristics for the latter. Empirical evaluation shows that Helix is not only able to handle a wide variety of use cases in one unified workflow but also much faster, providing run time reductions of up to 19x over state-of-the-art systems, such as DeepDive or KeystoneML, on four real-world applications in natural language processing, computer vision, social and natural sciences.
Tasks
Published	2018-12-14
URL	http://arxiv.org/abs/1812.05762v1
PDF	http://arxiv.org/pdf/1812.05762v1.pdf
PWC	https://paperswithcode.com/paper/helix-holistic-optimization-for-accelerating
Repo
Framework

How to Use Heuristics for Differential Privacy


Title	How to Use Heuristics for Differential Privacy
Authors	Seth Neel, Aaron Roth, Zhiwei Steven Wu
Abstract	We develop theory for using heuristics to solve computationally hard problems in differential privacy. Heuristic approaches have enjoyed tremendous success in machine learning, for which performance can be empirically evaluated. However, privacy guarantees cannot be evaluated empirically, and must be proven — without making heuristic assumptions. We show that learning problems over broad classes of functions can be solved privately and efficiently, assuming the existence of a non-private oracle for solving the same problem. Our first algorithm yields a privacy guarantee that is contingent on the correctness of the oracle. We then give a reduction which applies to a class of heuristics which we call certifiable, which allows us to convert oracle-dependent privacy guarantees to worst-case privacy guarantee that hold even when the heuristic standing in for the oracle might fail in adversarial ways. Finally, we consider a broad class of functions that includes most classes of simple boolean functions studied in the PAC learning literature, including conjunctions, disjunctions, parities, and discrete halfspaces. We show that there is an efficient algorithm for privately constructing synthetic data for any such class, given a non-private learning oracle. This in particular gives the first oracle-efficient algorithm for privately generating synthetic data for contingency tables. The most intriguing question left open by our work is whether or not every problem that can be solved differentially privately can be privately solved with an oracle-efficient algorithm. While we do not resolve this, we give a barrier result that suggests that any generic oracle-efficient reduction must fall outside of a natural class of algorithms (which includes the algorithms given in this paper).
Tasks
Published	2018-11-19
URL	http://arxiv.org/abs/1811.07765v1
PDF	http://arxiv.org/pdf/1811.07765v1.pdf
PWC	https://paperswithcode.com/paper/how-to-use-heuristics-for-differential
Repo
Framework

What is not where: the challenge of integrating spatial representations into deep learning architectures


Title	What is not where: the challenge of integrating spatial representations into deep learning architectures
Authors	John D. Kelleher, Simon Dobnik
Abstract	This paper examines to what degree current deep learning architectures for image caption generation capture spatial language. On the basis of the evaluation of examples of generated captions from the literature we argue that systems capture what objects are in the image data but not where these objects are located: the captions generated by these systems are the output of a language model conditioned on the output of an object detector that cannot capture fine-grained location information. Although language models provide useful knowledge for image captions, we argue that deep learning image captioning architectures should also model geometric relations between objects.
Tasks	Image Captioning, Language Modelling
Published	2018-07-21
URL	http://arxiv.org/abs/1807.08133v1
PDF	http://arxiv.org/pdf/1807.08133v1.pdf
PWC	https://paperswithcode.com/paper/what-is-not-where-the-challenge-of
Repo
Framework

Generating Material Maps to Map Informal Settlements


Title	Generating Material Maps to Map Informal Settlements
Authors	Patrick Helber, Bradley Gram-Hansen, Indhu Varatharajan, Faiza Azam, Alejandro Coca-Castro, Veronika Kopackova, Piotr Bilinski
Abstract	Detecting and mapping informal settlements encompasses several of the United Nations sustainable development goals. This is because informal settlements are home to the most socially and economically vulnerable people on the planet. Thus, understanding where these settlements are is of paramount importance to both government and non-government organizations (NGOs), such as the United Nations Children’s Fund (UNICEF), who can use this information to deliver effective social and economic aid. We propose a method that detects and maps the locations of informal settlements using only freely available, Sentinel-2 low-resolution satellite spectral data and socio-economic data. This is in contrast to previous studies that only use costly very-high resolution (VHR) satellite and aerial imagery. We show how we can detect informal settlements by combining both domain knowledge and machine learning techniques, to build a classifier that looks for known roofing materials used in informal settlements. Please find additional material at https://frontierdevelopmentlab.github.io/informal-settlements/.
Tasks
Published	2018-11-30
URL	https://arxiv.org/abs/1812.00786v2
PDF	https://arxiv.org/pdf/1812.00786v2.pdf
PWC	https://paperswithcode.com/paper/generating-material-maps-to-map-informal
Repo
Framework

A Consistent Method for Learning OOMs from Asymptotically Stationary Time Series Data Containing Missing Values


Title	A Consistent Method for Learning OOMs from Asymptotically Stationary Time Series Data Containing Missing Values
Authors	Tianlin Liu
Abstract	In the traditional framework of spectral learning of stochastic time series models, model parameters are estimated based on trajectories of fully recorded observations. However, real-world time series data often contain missing values, and worse, the distributions of missingness events over time are often not independent of the visible process. Recently, a spectral OOM learning algorithm for time series with missing data was introduced and proved to be consistent, albeit under quite strong conditions. Here we refine the algorithm and prove that the original strong conditions can be very much relaxed. We validate our theoretical findings by numerical experiments, showing that the algorithm can consistently handle missingness patterns whose dynamic interacts with the visible process.
Tasks	Time Series
Published	2018-08-11
URL	http://arxiv.org/abs/1808.03873v2
PDF	http://arxiv.org/pdf/1808.03873v2.pdf
PWC	https://paperswithcode.com/paper/a-consistent-method-for-learning-ooms-from
Repo
Framework

Improved asynchronous parallel optimization analysis for stochastic incremental methods


Title	Improved asynchronous parallel optimization analysis for stochastic incremental methods
Authors	Rémi Leblond, Fabian Pedregosa, Simon Lacoste-Julien
Abstract	As datasets continue to increase in size and multi-core computer architectures are developed, asynchronous parallel optimization algorithms become more and more essential to the field of Machine Learning. Unfortunately, conducting the theoretical analysis asynchronous methods is difficult, notably due to the introduction of delay and inconsistency in inherently sequential algorithms. Handling these issues often requires resorting to simplifying but unrealistic assumptions. Through a novel perspective, we revisit and clarify a subtle but important technical issue present in a large fraction of the recent convergence rate proofs for asynchronous parallel optimization algorithms, and propose a simplification of the recently introduced “perturbed iterate” framework that resolves it. We demonstrate the usefulness of our new framework by analyzing three distinct asynchronous parallel incremental optimization algorithms: Hogwild (asynchronous SGD), KROMAGNON (asynchronous SVRG) and ASAGA, a novel asynchronous parallel version of the incremental gradient algorithm SAGA that enjoys fast linear convergence rates. We are able to both remove problematic assumptions and obtain better theoretical results. Notably, we prove that ASAGA and KROMAGNON can obtain a theoretical linear speedup on multi-core systems even without sparsity assumptions. We present results of an implementation on a 40-core architecture illustrating the practical speedups as well as the hardware overhead. Finally, we investigate the overlap constant, an ill-understood but central quantity for the theoretical analysis of asynchronous parallel algorithms. We find that it encompasses much more complexity than suggested in previous work, and often is order-of-magnitude bigger than traditionally thought.
Tasks
Published	2018-01-11
URL	http://arxiv.org/abs/1801.03749v3
PDF	http://arxiv.org/pdf/1801.03749v3.pdf
PWC	https://paperswithcode.com/paper/improved-asynchronous-parallel-optimization
Repo
Framework

Efficient Encodings of Conditional Cardinality Constraints


Title	Efficient Encodings of Conditional Cardinality Constraints
Authors	Abdelhamid Boudane, Said Jabbour, Badran Raddaoui, Lakhdar Sais
Abstract	In the encoding of many real-world problems to propositional satisfiability, the cardinality constraint is a recurrent constraint that needs to be managed effectively. Several efficient encodings have been proposed while missing that such a constraint can be involved in a more general propositional formulation. To avoid combinatorial explosion, Tseitin principle usually used to translate such general propositional formula to Conjunctive Normal Form (CNF), introduces fresh propositional variables to represent sub-formulas and/or complex contraints. Thanks to Plaisted and Greenbaum improvement, the polarity of the sub-formula $\Phi$ is taken into account leading to conditional constraints of the form $y\rightarrow \Phi$, or $\Phi\rightarrow y$, where $y$ is a fresh propositional variable. In the case where $\Phi$ represents a cardinality constraint, such translation leads to conditional cardinality constraints subject of the present paper. We first show that when all the clauses encoding the cardinality constraint are augmented with an additional new variable, most of the well-known encodings cease to maintain the generalized arc consistency property. Then, we consider some of these encodings and show how they can be extended to recover such important property. An experimental validation is conducted on a SAT-based pattern mining application, where such conditional cardinality constraints is a cornerstone, showing the relevance of our proposed approach.
Tasks
Published	2018-03-31
URL	http://arxiv.org/abs/1804.00211v1
PDF	http://arxiv.org/pdf/1804.00211v1.pdf
PWC	https://paperswithcode.com/paper/efficient-encodings-of-conditional
Repo
Framework

An efficient branch-and-bound algorithm for submodular function maximization


Title	An efficient branch-and-bound algorithm for submodular function maximization
Authors	Naoya Uematsu, Shunji Umetani, Yoshinobu Kawahara
Abstract	The submodular function maximization is an attractive optimization model that appears in many real applications. Although a variety of greedy algorithms quickly find good feasible solutions for many instances while guaranteeing (1-1/e)-approximation ratio, we still encounter many real applications that ask optimal or better feasible solutions within reasonable computation time. In this paper, we present an efficient branch-and-bound algorithm for the non-decreasing submodular function maximization problem based on its binary integer programming (BIP) formulation with a huge number of constraints. Nemhauser and Wolsey developed an exact algorithm called the constraint generation algorithm that starts from a reduced BIP problem with a small subset of constraints taken from the constraints and repeats solving a reduced BIP problem while adding a new constraint at each iteration. However, their algorithm is still computationally expensive due to many reduced BIP problems to be solved. To overcome this, we propose an improved constraint generation algorithm to add a promising set of constraints at each iteration. We incorporate it into a branch-and-bound algorithm to attain good upper bounds while solving a smaller number of reduced BIP problems. According to computational results for well-known benchmark instances, our algorithm achieved better performance than the state-of-the-art exact algorithms.
Tasks
Published	2018-11-10
URL	http://arxiv.org/abs/1811.04177v1
PDF	http://arxiv.org/pdf/1811.04177v1.pdf
PWC	https://paperswithcode.com/paper/an-efficient-branch-and-bound-algorithm-for
Repo
Framework

Adaptive Memory Networks


Title	Adaptive Memory Networks
Authors	Daniel Li, Asim Kadav
Abstract	We present Adaptive Memory Networks (AMN) that processes input-question pairs to dynamically construct a network architecture optimized for lower inference times for Question Answering (QA) tasks. AMN processes the input story to extract entities and stores them in memory banks. Starting from a single bank, as the number of input entities increases, AMN learns to create new banks as the entropy in a single bank becomes too high. Hence, after processing an input-question(s) pair, the resulting network represents a hierarchical structure where entities are stored in different banks, distanced by question relevance. At inference, one or few banks are used, creating a tradeoff between accuracy and performance. AMN is enabled by dynamic networks that allow input dependent network creation and efficiency in dynamic mini-batching as well as our novel bank controller that allows learning discrete decision making with high accuracy. In our results, we demonstrate that AMN learns to create variable depth networks depending on task complexity and reduces inference times for QA tasks.
Tasks	Decision Making, Question Answering
Published	2018-02-01
URL	http://arxiv.org/abs/1802.00510v1
PDF	http://arxiv.org/pdf/1802.00510v1.pdf
PWC	https://paperswithcode.com/paper/adaptive-memory-networks
Repo
Framework

Leishmaniasis Parasite Segmentation and Classification using Deep Learning


Title	Leishmaniasis Parasite Segmentation and Classification using Deep Learning
Authors	Marc Górriz, Albert Aparicio, Berta Raventós, Verónica Vilaplana, Elisa Sayrol, Daniel López-Codina
Abstract	Leishmaniasis is considered a neglected disease that causes thousands of deaths annually in some tropical and subtropical countries. There are various techniques to diagnose leishmaniasis of which manual microscopy is considered to be the gold standard. There is a need for the development of automatic techniques that are able to detect parasites in a robust and unsupervised manner. In this paper we present a procedure for automatizing the detection process based on a deep learning approach. We train a U-net model that successfully segments leismania parasites and classifies them into promastigotes, amastigotes and adhered parasites.
Tasks
Published	2018-12-30
URL	http://arxiv.org/abs/1812.11586v1
PDF	http://arxiv.org/pdf/1812.11586v1.pdf
PWC	https://paperswithcode.com/paper/leishmaniasis-parasite-segmentation-and
Repo
Framework

Efficient online algorithms for fast-rate regret bounds under sparsity


Title	Efficient online algorithms for fast-rate regret bounds under sparsity
Authors	Pierre Gaillard, Olivier Wintenberger
Abstract	We consider the online convex optimization problem. In the setting of arbitrary sequences and finite set of parameters, we establish a new fast-rate quantile regret bound. Then we investigate the optimization into the L1-ball by discretizing the parameter space. Our algorithm is projection free and we propose an efficient solution by restarting the algorithm on adaptive discretization grids. In the adversarial setting, we develop an algorithm that achieves several rates of convergence with different dependencies on the sparsity of the objective. In the i.i.d. setting, we establish new risk bounds that are adaptive to the sparsity of the problem and to the regularity of the risk (ranging from a rate 1 / $\sqrt T$ for general convex risk to 1 /T for strongly convex risk). These results generalize previous works on sparse online learning. They are obtained under a weak assumption on the risk ({\L}ojasiewicz’s assumption) that allows multiple optima which is crucial when dealing with degenerate situations.
Tasks
Published	2018-05-23
URL	http://arxiv.org/abs/1805.09174v1
PDF	http://arxiv.org/pdf/1805.09174v1.pdf
PWC	https://paperswithcode.com/paper/efficient-online-algorithms-for-fast-rate
Repo
Framework