July 27, 2019

3114 words 15 mins read

Paper Group ANR 654

Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions. Incident Light Frequency-based Image Defogging Algorithm. DE-PACRR: Exploring Layers Inside the PACRR Model. Learning of Coordination Policies for Robotic Swarms. Principal Boundary on Riemannian Manifolds. Third-Person Imitation Learning. Semantically Consistent R …

Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions


Title	Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions
Authors	Dimitris Bertsimas, Bart Van Parys
Abstract	We present a novel binary convex reformulation of the sparse regression problem that constitutes a new duality perspective. We devise a new cutting plane method and provide evidence that it can solve to provable optimality the sparse regression problem for sample sizes n and number of regressors p in the 100,000s, that is two orders of magnitude better than the current state of the art, in seconds. The ability to solve the problem for very high dimensions allows us to observe new phase transition phenomena. Contrary to traditional complexity theory which suggests that the difficulty of a problem increases with problem size, the sparse regression problem has the property that as the number of samples $n$ increases the problem becomes easier in that the solution recovers 100% of the true signal, and our approach solves the problem extremely fast (in fact faster than Lasso), while for small number of samples n, our approach takes a larger amount of time to solve the problem, but importantly the optimal solution provides a statistically more relevant regressor. We argue that our exact sparse regression approach presents a superior alternative over heuristic methods available at present.
Tasks
Published	2017-09-28
URL	http://arxiv.org/abs/1709.10029v1
PDF	http://arxiv.org/pdf/1709.10029v1.pdf
PWC	https://paperswithcode.com/paper/sparse-high-dimensional-regression-exact
Repo
Framework

Incident Light Frequency-based Image Defogging Algorithm


Title	Incident Light Frequency-based Image Defogging Algorithm
Authors	Wenbo Zhang, Xiaorong Hou
Abstract	Considering the problem of color distortion caused by the defogging algorithm based on dark channel prior, an improved algorithm was proposed to calculate the transmittance of all channels respectively. First, incident light frequency’s effect on the transmittance of various color channels was analyzed according to the Beer-Lambert’s Law, from which a proportion among various channel transmittances was derived; afterwards, images were preprocessed by down-sampling to refine transmittance, and then the original size was restored to enhance the operational efficiency of the algorithm; finally, the transmittance of all color channels was acquired in accordance with the proportion, and then the corresponding transmittance was used for image restoration in each channel. The experimental results show that compared with the existing algorithm, this improved image defogging algorithm could make image colors more natural, solve the problem of slightly higher color saturation caused by the existing algorithm, and shorten the operation time by four to nine times.
Tasks	Image Restoration
Published	2017-03-03
URL	http://arxiv.org/abs/1703.01248v1
PDF	http://arxiv.org/pdf/1703.01248v1.pdf
PWC	https://paperswithcode.com/paper/incident-light-frequency-based-image
Repo
Framework

DE-PACRR: Exploring Layers Inside the PACRR Model


Title	DE-PACRR: Exploring Layers Inside the PACRR Model
Authors	Andrew Yates, Kai Hui
Abstract	Recent neural IR models have demonstrated deep learning’s utility in ad-hoc information retrieval. However, deep models have a reputation for being black boxes, and the roles of a neural IR model’s components may not be obvious at first glance. In this work, we attempt to shed light on the inner workings of a recently proposed neural IR model, namely the PACRR model, by visualizing the output of intermediate layers and by investigating the relationship between intermediate weights and the ultimate relevance score produced. We highlight several insights, hoping that such insights will be generally applicable.
Tasks	Ad-Hoc Information Retrieval, Information Retrieval
Published	2017-06-27
URL	http://arxiv.org/abs/1706.08746v2
PDF	http://arxiv.org/pdf/1706.08746v2.pdf
PWC	https://paperswithcode.com/paper/de-pacrr-exploring-layers-inside-the-pacrr
Repo
Framework

Learning of Coordination Policies for Robotic Swarms


Title	Learning of Coordination Policies for Robotic Swarms
Authors	Qiyang Li, Xintong Du, Yizhou Huang, Quinlan Sykora, Angela P. Schoellig
Abstract	Inspired by biological swarms, robotic swarms are envisioned to solve real-world problems that are difficult for individual agents. Biological swarms can achieve collective intelligence based on local interactions and simple rules; however, designing effective distributed policies for large-scale robotic swarms to achieve a global objective can be challenging. Although it is often possible to design an optimal centralized strategy for smaller numbers of agents, those methods can fail as the number of agents increases. Motivated by the growing success of machine learning, we develop a deep learning approach that learns distributed coordination policies from centralized policies. In contrast to traditional distributed control approaches, which are usually based on human-designed policies for relatively simple tasks, this learning-based approach can be adapted to more difficult tasks. We demonstrate the efficacy of our proposed approach on two different tasks, the well-known rendezvous problem and a more difficult particle assignment problem. For the latter, no known distributed policy exists. From extensive simulations, it is shown that the performance of the learned coordination policies is comparable to the centralized policies, surpassing state-of-the-art distributed policies. Thereby, our proposed approach provides a promising alternative for real-world coordination problems that would be otherwise computationally expensive to solve or intangible to explore.
Tasks
Published	2017-09-19
URL	http://arxiv.org/abs/1709.06620v1
PDF	http://arxiv.org/pdf/1709.06620v1.pdf
PWC	https://paperswithcode.com/paper/learning-of-coordination-policies-for-robotic
Repo
Framework

Principal Boundary on Riemannian Manifolds


Title	Principal Boundary on Riemannian Manifolds
Authors	Zhigang Yao, Zhenyue Zhang
Abstract	We consider the classification problem and focus on nonlinear methods for classification on manifolds. For multivariate datasets lying on an embedded nonlinear Riemannian manifold within the higher-dimensional ambient space, we aim to acquire a classification boundary for the classes with labels, using the intrinsic metric on the manifolds. Motivated by finding an optimal boundary between the two classes, we invent a novel approach – the principal boundary. From the perspective of classification, the principal boundary is defined as an optimal curve that moves in between the principal flows traced out from two classes of data, and at any point on the boundary, it maximizes the margin between the two classes. We estimate the boundary in quality with its direction, supervised by the two principal flows. We show that the principal boundary yields the usual decision boundary found by the support vector machine in the sense that locally, the two boundaries coincide. Some optimality and convergence properties of the random principal boundary and its population counterpart are also shown. We illustrate how to find, use and interpret the principal boundary with an application in real data.
Tasks
Published	2017-10-21
URL	http://arxiv.org/abs/1711.06705v2
PDF	http://arxiv.org/pdf/1711.06705v2.pdf
PWC	https://paperswithcode.com/paper/principal-boundary-on-riemannian-manifolds
Repo
Framework

Third-Person Imitation Learning


Title	Third-Person Imitation Learning
Authors	Bradly C. Stadie, Pieter Abbeel, Ilya Sutskever
Abstract	Reinforcement learning (RL) makes it possible to train agents capable of achieving sophisticated goals in complex and uncertain environments. A key difficulty in reinforcement learning is specifying a reward function for the agent to optimize. Traditionally, imitation learning in RL has been used to overcome this problem. Unfortunately, hitherto imitation learning methods tend to require that demonstrations are supplied in the first-person: the agent is provided with a sequence of states and a specification of the actions that it should have taken. While powerful, this kind of imitation learning is limited by the relatively hard problem of collecting first-person demonstrations. Humans address this problem by learning from third-person demonstrations: they observe other humans perform tasks, infer the task, and accomplish the same task themselves. In this paper, we present a method for unsupervised third-person imitation learning. Here third-person refers to training an agent to correctly achieve a simple goal in a simple environment when it is provided a demonstration of a teacher achieving the same goal but from a different viewpoint; and unsupervised refers to the fact that the agent receives only these third-person demonstrations, and is not provided a correspondence between teacher states and student states. Our methods primary insight is that recent advances from domain confusion can be utilized to yield domain agnostic features which are crucial during the training process. To validate our approach, we report successful experiments on learning from third-person demonstrations in a pointmass domain, a reacher domain, and inverted pendulum.
Tasks	Imitation Learning
Published	2017-03-06
URL	https://arxiv.org/abs/1703.01703v2
PDF	https://arxiv.org/pdf/1703.01703v2.pdf
PWC	https://paperswithcode.com/paper/third-person-imitation-learning
Repo
Framework

Semantically Consistent Regularization for Zero-Shot Recognition


Title	Semantically Consistent Regularization for Zero-Shot Recognition
Authors	Pedro Morgado, Nuno Vasconcelos
Abstract	The role of semantics in zero-shot learning is considered. The effectiveness of previous approaches is analyzed according to the form of supervision provided. While some learn semantics independently, others only supervise the semantic subspace explained by training classes. Thus, the former is able to constrain the whole space but lacks the ability to model semantic correlations. The latter addresses this issue but leaves part of the semantic space unsupervised. This complementarity is exploited in a new convolutional neural network (CNN) framework, which proposes the use of semantics as constraints for recognition.Although a CNN trained for classification has no transfer ability, this can be encouraged by learning an hidden semantic layer together with a semantic code for classification. Two forms of semantic constraints are then introduced. The first is a loss-based regularizer that introduces a generalization constraint on each semantic predictor. The second is a codeword regularizer that favors semantic-to-class mappings consistent with prior semantic knowledge while allowing these to be learned from data. Significant improvements over the state-of-the-art are achieved on several datasets.
Tasks	Zero-Shot Learning
Published	2017-04-10
URL	http://arxiv.org/abs/1704.03039v1
PDF	http://arxiv.org/pdf/1704.03039v1.pdf
PWC	https://paperswithcode.com/paper/semantically-consistent-regularization-for
Repo
Framework

A complete characterization of optimal dictionaries for least squares representation


Title	A complete characterization of optimal dictionaries for least squares representation
Authors	Mohammed Rayyan Sheriff, Debasish Chatterjee
Abstract	Dictionaries are collections of vectors used for representations of elements in Euclidean spaces. While recent research on optimal dictionaries is focussed on providing sparse (i.e., $\ell_0$-optimal,) representations, here we consider the problem of finding optimal dictionaries such that representations of samples of a random vector are optimal in an $\ell_2$-sense. For us, optimality of representation is equivalent to minimization of the average $\ell_2$-norm of the coefficients used to represent the random vector, with the lengths of the dictionary vectors being specified a priori. With the help of recent results on rank-$1$ decompositions of symmetric positive semidefinite matrices and the theory of majorization, we provide a complete characterization of $\ell_2$-optimal dictionaries. Our results are accompanied by polynomial time algorithms that construct $\ell_2$-optimal dictionaries from given data.
Tasks
Published	2017-10-18
URL	http://arxiv.org/abs/1710.06763v1
PDF	http://arxiv.org/pdf/1710.06763v1.pdf
PWC	https://paperswithcode.com/paper/a-complete-characterization-of-optimal
Repo
Framework

PQTable: Non-exhaustive Fast Search for Product-quantized Codes using Hash Tables


Title	PQTable: Non-exhaustive Fast Search for Product-quantized Codes using Hash Tables
Authors	Yusuke Matsui, Toshihiko Yamasaki, Kiyoharu Aizawa
Abstract	In this paper, we propose a product quantization table (PQTable); a fast search method for product-quantized codes via hash-tables. An identifier of each database vector is associated with the slot of a hash table by using its PQ-code as a key. For querying, an input vector is PQ-encoded and hashed, and the items associated with that code are then retrieved. The proposed PQTable produces the same results as a linear PQ scan, and is 10^2 to 10^5 times faster. Although state-of-the-art performance can be achieved by previous inverted-indexing-based approaches, such methods require manually-designed parameter setting and significant training; our PQTable is free of these limitations, and therefore offers a practical and effective solution for real-world problems. Specifically, when the vectors are highly compressed, our PQTable achieves one of the fastest search performances on a single CPU to date with significantly efficient memory usage (0.059 ms per query over 10^9 data points with just 5.5 GB memory consumption). Finally, we show that our proposed PQTable can naturally handle the codes of an optimized product quantization (OPQTable).
Tasks	Quantization
Published	2017-04-21
URL	http://arxiv.org/abs/1704.06556v1
PDF	http://arxiv.org/pdf/1704.06556v1.pdf
PWC	https://paperswithcode.com/paper/pqtable-non-exhaustive-fast-search-for
Repo
Framework

Active Learning for Accurate Estimation of Linear Models


Title	Active Learning for Accurate Estimation of Linear Models
Authors	Carlos Riquelme, Mohammad Ghavamzadeh, Alessandro Lazaric
Abstract	We explore the sequential decision making problem where the goal is to estimate uniformly well a number of linear models, given a shared budget of random contexts independently sampled from a known distribution. The decision maker must query one of the linear models for each incoming context, and receives an observation corrupted by noise levels that are unknown, and depend on the model instance. We present Trace-UCB, an adaptive allocation algorithm that learns the noise levels while balancing contexts accordingly across the different linear functions, and derive guarantees for simple regret in both expectation and high-probability. Finally, we extend the algorithm and its guarantees to high dimensional settings, where the number of linear models times the dimension of the contextual space is higher than the total budget of samples. Simulations with real data suggest that Trace-UCB is remarkably robust, outperforming a number of baselines even when its assumptions are violated.
Tasks	Active Learning, Decision Making
Published	2017-03-02
URL	http://arxiv.org/abs/1703.00579v2
PDF	http://arxiv.org/pdf/1703.00579v2.pdf
PWC	https://paperswithcode.com/paper/active-learning-for-accurate-estimation-of
Repo
Framework

Concentration of Multilinear Functions of the Ising Model with Applications to Network Data


Title	Concentration of Multilinear Functions of the Ising Model with Applications to Network Data
Authors	Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath
Abstract	We prove near-tight concentration of measure for polynomial functions of the Ising model under high temperature. For any degree $d$, we show that a degree-$d$ polynomial of a $n$-spin Ising model exhibits exponential tails that scale as $\exp(-r^{2/d})$ at radius $r=\tilde{\Omega}_d(n^{d/2})$. Our concentration radius is optimal up to logarithmic factors for constant $d$, improving known results by polynomial factors in the number of spins. We demonstrate the efficacy of polynomial functions as statistics for testing the strength of interactions in social networks in both synthetic and real world data.
Tasks
Published	2017-10-11
URL	http://arxiv.org/abs/1710.04170v1
PDF	http://arxiv.org/pdf/1710.04170v1.pdf
PWC	https://paperswithcode.com/paper/concentration-of-multilinear-functions-of-the
Repo
Framework

A learning framework for winner-take-all networks with stochastic synapses


Title	A learning framework for winner-take-all networks with stochastic synapses
Authors	Hesham Mostafa, Gert Cauwenberghs
Abstract	Many recent generative models make use of neural networks to transform the probability distribution of a simple low-dimensional noise process into the complex distribution of the data. This raises the question of whether biological networks operate along similar principles to implement a probabilistic model of the environment through transformations of intrinsic noise processes. The intrinsic neural and synaptic noise processes in biological networks, however, are quite different from the noise processes used in current abstract generative networks. This, together with the discrete nature of spikes and local circuit interactions among the neurons, raises several difficulties when using recent generative modeling frameworks to train biologically motivated models. In this paper, we show that a biologically motivated model based on multi-layer winner-take-all (WTA) circuits and stochastic synapses admits an approximate analytical description. This allows us to use the proposed networks in a variational learning setting where stochastic backpropagation is used to optimize a lower bound on the data log likelihood, thereby learning a generative model of the data. We illustrate the generality of the proposed networks and learning technique by using them in a structured output prediction task, and in a semi-supervised learning task. Our results extend the domain of application of modern stochastic network architectures to networks where synaptic transmission failure is the principal noise mechanism.
Tasks
Published	2017-08-14
URL	http://arxiv.org/abs/1708.04251v2
PDF	http://arxiv.org/pdf/1708.04251v2.pdf
PWC	https://paperswithcode.com/paper/a-learning-framework-for-winner-take-all
Repo
Framework

Automated Image Analysis Framework for the High-Throughput Determination of Grapevine Berry Sizes Using Conditional Random Fields


Title	Automated Image Analysis Framework for the High-Throughput Determination of Grapevine Berry Sizes Using Conditional Random Fields
Authors	Ribana Roscher, Katja Herzog, Annemarie Kunkel, Anna Kicherer, Reinhard Töpfer, Wolfgang Förstner
Abstract	The berry size is one of the most important fruit traits in grapevine breeding. Non-invasive, image-based phenotyping promises a fast and precise method for the monitoring of the grapevine berry size. In the present study an automated image analyzing framework was developed in order to estimate the size of grapevine berries from images in a high-throughput manner. The framework includes (i) the detection of circular structures which are potentially berries and (ii) the classification of these into the class ‘berry’ or ‘non-berry’ by utilizing a conditional random field. The approach used the concept of a one-class classification, since only the target class ‘berry’ is of interest and needs to be modeled. Moreover, the classification was carried out by using an automated active learning approach, i.e no user interaction is required during the classification process and in addition, the process adapts automatically to changing image conditions, e.g. illumination or berry color. The framework was tested on three datasets consisting in total of 139 images. The images were taken in an experimental vineyard at different stages of grapevine growth according to the BBCH scale. The mean berry size of a plant estimated by the framework correlates with the manually measured berry size by $0.88$.
Tasks	Active Learning
Published	2017-12-15
URL	http://arxiv.org/abs/1712.05647v1
PDF	http://arxiv.org/pdf/1712.05647v1.pdf
PWC	https://paperswithcode.com/paper/automated-image-analysis-framework-for-the
Repo
Framework

Transductive Zero-Shot Hashing via Coarse-to-Fine Similarity Mining


Title	Transductive Zero-Shot Hashing via Coarse-to-Fine Similarity Mining
Authors	Hanjiang Lai, Yan Pan
Abstract	Zero-shot Hashing (ZSH) is to learn hashing models for novel/target classes without training data, which is an important and challenging problem. Most existing ZSH approaches exploit transfer learning via an intermediate shared semantic representations between the seen/source classes and novel/target classes. However, due to having disjoint, the hash functions learned from the source dataset are biased when applied directly to the target classes. In this paper, we study the transductive ZSH, i.e., we have unlabeled data for novel classes. We put forward a simple yet efficient joint learning approach via coarse-to-fine similarity mining which transfers knowledges from source data to target data. It mainly consists of two building blocks in the proposed deep architecture: 1) a shared two-streams network, which the first stream operates on the source data and the second stream operates on the unlabeled data, to learn the effective common image representations, and 2) a coarse-to-fine module, which begins with finding the most representative images from target classes and then further detect similarities among these images, to transfer the similarities of the source data to the target data in a greedy fashion. Extensive evaluation results on several benchmark datasets demonstrate that the proposed hashing method achieves significant improvement over the state-of-the-art methods.
Tasks	Transfer Learning
Published	2017-11-08
URL	http://arxiv.org/abs/1711.02856v1
PDF	http://arxiv.org/pdf/1711.02856v1.pdf
PWC	https://paperswithcode.com/paper/transductive-zero-shot-hashing-via-coarse-to
Repo
Framework

Optimized Data Pre-Processing for Discrimination Prevention


Title	Optimized Data Pre-Processing for Discrimination Prevention
Authors	Flavio P. Calmon, Dennis Wei, Karthikeyan Natesan Ramamurthy, Kush R. Varshney
Abstract	Non-discrimination is a recognized objective in algorithmic decision making. In this paper, we introduce a novel probabilistic formulation of data pre-processing for reducing discrimination. We propose a convex optimization for learning a data transformation with three goals: controlling discrimination, limiting distortion in individual data samples, and preserving utility. We characterize the impact of limited sample size in accomplishing this objective, and apply two instances of the proposed optimization to datasets, including one on real-world criminal recidivism. The results demonstrate that all three criteria can be simultaneously achieved and also reveal interesting patterns of bias in American society.
Tasks	Decision Making
Published	2017-04-11
URL	http://arxiv.org/abs/1704.03354v1
PDF	http://arxiv.org/pdf/1704.03354v1.pdf
PWC	https://paperswithcode.com/paper/optimized-data-pre-processing-for
Repo
Framework