May 5, 2019

3032 words 15 mins read

Paper Group ANR 535

DynaNewton - Accelerating Newton’s Method for Machine Learning. DOLPHIn - Dictionary Learning for Phase Retrieval. Active Robust Learning. Overview of Annotation Creation: Processes & Tools. From Motion Blur to Motion Flow: a Deep Learning Solution for Removing Heterogeneous Motion Blur. A Deep Primal-Dual Network for Guided Depth Super-Resolution. …

DynaNewton - Accelerating Newton’s Method for Machine Learning


Title	DynaNewton - Accelerating Newton’s Method for Machine Learning
Authors	Hadi Daneshmand, Aurelien Lucchi, Thomas Hofmann
Abstract	Newton’s method is a fundamental technique in optimization with quadratic convergence within a neighborhood around the optimum. However reaching this neighborhood is often slow and dominates the computational costs. We exploit two properties specific to empirical risk minimization problems to accelerate Newton’s method, namely, subsampling training data and increasing strong convexity through regularization. We propose a novel continuation method, where we define a family of objectives over increasing sample sizes and with decreasing regularization strength. Solutions on this path are tracked such that the minimizer of the previous objective is guaranteed to be within the quadratic convergence region of the next objective to be optimized. Thereby every Newton iteration is guaranteed to achieve super-linear contractions with regard to the chosen objective, which becomes a moving target. We provide a theoretical analysis that motivates our algorithm, called DynaNewton, and characterizes its speed of convergence. Experiments on a wide range of data sets and problems consistently confirm the predicted computational savings.
Tasks
Published	2016-05-20
URL	http://arxiv.org/abs/1605.06561v1
PDF	http://arxiv.org/pdf/1605.06561v1.pdf
PWC	https://paperswithcode.com/paper/dynanewton-accelerating-newtons-method-for
Repo
Framework

DOLPHIn - Dictionary Learning for Phase Retrieval


Title	DOLPHIn - Dictionary Learning for Phase Retrieval
Authors	Andreas M. Tillmann, Yonina C. Eldar, Julien Mairal
Abstract	We propose a new algorithm to learn a dictionary for reconstructing and sparsely encoding signals from measurements without phase. Specifically, we consider the task of estimating a two-dimensional image from squared-magnitude measurements of a complex-valued linear transformation of the original image. Several recent phase retrieval algorithms exploit underlying sparsity of the unknown signal in order to improve recovery performance. In this work, we consider such a sparse signal prior in the context of phase retrieval, when the sparsifying dictionary is not known in advance. Our algorithm jointly reconstructs the unknown signal - possibly corrupted by noise - and learns a dictionary such that each patch of the estimated image can be sparsely represented. Numerical experiments demonstrate that our approach can obtain significantly better reconstructions for phase retrieval problems with noise than methods that cannot exploit such “hidden” sparsity. Moreover, on the theoretical side, we provide a convergence result for our method.
Tasks	Dictionary Learning
Published	2016-02-06
URL	http://arxiv.org/abs/1602.02263v2
PDF	http://arxiv.org/pdf/1602.02263v2.pdf
PWC	https://paperswithcode.com/paper/dolphin-dictionary-learning-for-phase
Repo
Framework

Active Robust Learning


Title	Active Robust Learning
Authors	Hossein Ghafarian, Hadi Sadoghi Yazdi
Abstract	In many practical applications of learning algorithms, unlabeled data is cheap and abundant whereas labeled data is expensive. Active learning algorithms developed to achieve better performance with lower cost. Usually Representativeness and Informativeness are used in active learning algoirthms. Advanced recent active learning methods consider both of these criteria. Despite its vast literature, very few active learning methods consider noisy instances, i.e. label noisy and outlier instances. Also, these methods didn’t consider accuracy in computing representativeness and informativeness. Based on the idea that inaccuracy in these measures and not taking noisy instances into consideration are two sides of a coin and are inherently related, a new loss function is proposed. This new loss function helps to decrease the effect of noisy instances while at the same time, reduces bias. We defined “instance complexity” as a new notion of complexity for instances of a learning problem. It is proved that noisy instances in the data if any, are the ones with maximum instance complexity. Based on this loss function which has two functions for classifying ordinary and noisy instances, a new classifier, named “Simple-Complex Classifier” is proposed. In this classifier there are a simple and a complex function, with the complex function responsible for selecting noisy instances. The resulting optimization problem for both learning and active learning is highly non-convex and very challenging. In order to solve it, a convex relaxation is proposed.
Tasks	Active Learning
Published	2016-08-25
URL	http://arxiv.org/abs/1608.07159v1
PDF	http://arxiv.org/pdf/1608.07159v1.pdf
PWC	https://paperswithcode.com/paper/active-robust-learning
Repo
Framework

Overview of Annotation Creation: Processes & Tools


Title	Overview of Annotation Creation: Processes & Tools
Authors	Mark A. Finlayson, Tomaž Erjavec
Abstract	Creating linguistic annotations requires more than just a reliable annotation scheme. Annotation can be a complex endeavour potentially involving many people, stages, and tools. This chapter outlines the process of creating end-to-end linguistic annotations, identifying specific tasks that researchers often perform. Because tool support is so central to achieving high quality, reusable annotations with low cost, the focus is on identifying capabilities that are necessary or useful for annotation tools, as well as common problems these tools present that reduce their utility. Although examples of specific tools are provided in many cases, this chapter concentrates more on abstract capabilities and problems because new tools appear continuously, while old tools disappear into disuse or disrepair. The two core capabilities tools must have are support for the chosen annotation scheme and the ability to work on the language under study. Additional capabilities are organized into three categories: those that are widely provided; those that often useful but found in only a few tools; and those that have as yet little or no available tool support.
Tasks
Published	2016-02-18
URL	http://arxiv.org/abs/1602.05753v1
PDF	http://arxiv.org/pdf/1602.05753v1.pdf
PWC	https://paperswithcode.com/paper/overview-of-annotation-creation-processes
Repo
Framework

From Motion Blur to Motion Flow: a Deep Learning Solution for Removing Heterogeneous Motion Blur


Title	From Motion Blur to Motion Flow: a Deep Learning Solution for Removing Heterogeneous Motion Blur
Authors	Dong Gong, Jie Yang, Lingqiao Liu, Yanning Zhang, Ian Reid, Chunhua Shen, Anton van den Hengel, Qinfeng Shi
Abstract	Removing pixel-wise heterogeneous motion blur is challenging due to the ill-posed nature of the problem. The predominant solution is to estimate the blur kernel by adding a prior, but the extensive literature on the subject indicates the difficulty in identifying a prior which is suitably informative, and general. Rather than imposing a prior based on theory, we propose instead to learn one from the data. Learning a prior over the latent image would require modeling all possible image content. The critical observation underpinning our approach is thus that learning the motion flow instead allows the model to focus on the cause of the blur, irrespective of the image content. This is a much easier learning task, but it also avoids the iterative process through which latent image priors are typically applied. Our approach directly estimates the motion flow from the blurred image through a fully-convolutional deep neural network (FCN) and recovers the unblurred image from the estimated motion flow. Our FCN is the first universal end-to-end mapping from the blurred image to the dense motion flow. To train the FCN, we simulate motion flows to generate synthetic blurred-image-motion-flow pairs thus avoiding the need for human labeling. Extensive experiments on challenging realistic blurred images demonstrate that the proposed method outperforms the state-of-the-art.
Tasks
Published	2016-12-08
URL	http://arxiv.org/abs/1612.02583v1
PDF	http://arxiv.org/pdf/1612.02583v1.pdf
PWC	https://paperswithcode.com/paper/from-motion-blur-to-motion-flow-a-deep
Repo
Framework

A Deep Primal-Dual Network for Guided Depth Super-Resolution


Title	A Deep Primal-Dual Network for Guided Depth Super-Resolution
Authors	Gernot Riegler, David Ferstl, Matthias Rüther, Horst Bischof
Abstract	In this paper we present a novel method to increase the spatial resolution of depth images. We combine a deep fully convolutional network with a non-local variational method in a deep primal-dual network. The joint network computes a noise-free, high-resolution estimate from a noisy, low-resolution input depth map. Additionally, a high-resolution intensity image is used to guide the reconstruction in the network. By unrolling the optimization steps of a first-order primal-dual algorithm and formulating it as a network, we can train our joint method end-to-end. This not only enables us to learn the weights of the fully convolutional network, but also to optimize all parameters of the variational method and its optimization procedure. The training of such a deep network requires a large dataset for supervision. Therefore, we generate high-quality depth maps and corresponding color images with a physically based renderer. In an exhaustive evaluation we show that our method outperforms the state-of-the-art on multiple benchmarks.
Tasks	Super-Resolution
Published	2016-07-28
URL	http://arxiv.org/abs/1607.08569v1
PDF	http://arxiv.org/pdf/1607.08569v1.pdf
PWC	https://paperswithcode.com/paper/a-deep-primal-dual-network-for-guided-depth
Repo
Framework

Assessing Functional Neural Connectivity as an Indicator of Cognitive Performance


Title	Assessing Functional Neural Connectivity as an Indicator of Cognitive Performance
Authors	Brian S. Helfer, James R. Williamson, Benjamin A. Miller, Joseph Perricone, Thomas F. Quatieri
Abstract	Studies in recent years have demonstrated that neural organization and structure impact an individual’s ability to perform a given task. Specifically, individuals with greater neural efficiency have been shown to outperform those with less organized functional structure. In this work, we compare the predictive ability of properties of neural connectivity on a working memory task. We provide two novel approaches for characterizing functional network connectivity from electroencephalography (EEG), and compare these features to the average power across frequency bands in EEG channels. Our first novel approach represents functional connectivity structure through the distribution of eigenvalues making up channel coherence matrices in multiple frequency bands. Our second approach creates a connectivity network at each frequency band, and assesses variability in average path lengths of connected components and degree across the network. Failures in digit and sentence recall on single trials are detected using a Gaussian classifier for each feature set, at each frequency band. The classifier results are then fused across frequency bands, with the resulting detection performance summarized using the area under the receiver operating characteristic curve (AUC) statistic. Fused AUC results of 0.63/0.58/0.61 for digit recall failure and 0.58/0.59/0.54 for sentence recall failure are obtained from the connectivity structure, graph variability, and channel power features respectively.
Tasks	EEG
Published	2016-07-29
URL	http://arxiv.org/abs/1607.08891v1
PDF	http://arxiv.org/pdf/1607.08891v1.pdf
PWC	https://paperswithcode.com/paper/assessing-functional-neural-connectivity-as
Repo
Framework

Local Group Invariant Representations via Orbit Embeddings


Title	Local Group Invariant Representations via Orbit Embeddings
Authors	Anant Raj, Abhishek Kumar, Youssef Mroueh, P. Thomas Fletcher, Bernhard Schölkopf
Abstract	Invariance to nuisance transformations is one of the desirable properties of effective representations. We consider transformations that form a \emph{group} and propose an approach based on kernel methods to derive local group invariant representations. Locality is achieved by defining a suitable probability distribution over the group which in turn induces distributions in the input feature space. We learn a decision function over these distributions by appealing to the powerful framework of kernel methods and generate local invariant random feature maps via kernel approximations. We show uniform convergence bounds for kernel approximation and provide excess risk bounds for learning with these features. We evaluate our method on three real datasets, including Rotated MNIST and CIFAR-10, and observe that it outperforms competing kernel based approaches. The proposed method also outperforms deep CNN on Rotated-MNIST and performs comparably to the recently proposed group-equivariant CNN.
Tasks
Published	2016-12-06
URL	http://arxiv.org/abs/1612.01988v2
PDF	http://arxiv.org/pdf/1612.01988v2.pdf
PWC	https://paperswithcode.com/paper/local-group-invariant-representations-via
Repo
Framework

Deep disentangled representations for volumetric reconstruction


Title	Deep disentangled representations for volumetric reconstruction
Authors	Edward Grant, Pushmeet Kohli, Marcel van Gerven
Abstract	We introduce a convolutional neural network for inferring a compact disentangled graphical description of objects from 2D images that can be used for volumetric reconstruction. The network comprises an encoder and a twin-tailed decoder. The encoder generates a disentangled graphics code. The first decoder generates a volume, and the second decoder reconstructs the input image using a novel training regime that allows the graphics code to learn a separate representation of the 3D object and a description of its lighting and pose conditions. We demonstrate this method by generating volumes and disentangled graphical descriptions from images and videos of faces and chairs.
Tasks
Published	2016-10-12
URL	http://arxiv.org/abs/1610.03777v1
PDF	http://arxiv.org/pdf/1610.03777v1.pdf
PWC	https://paperswithcode.com/paper/deep-disentangled-representations-for
Repo
Framework

Neural Universal Discrete Denoiser


Title	Neural Universal Discrete Denoiser
Authors	Taesup Moon, Seonwoo Min, Byunghan Lee, Sungroh Yoon
Abstract	We present a new framework of applying deep neural networks (DNN) to devise a universal discrete denoiser. Unlike other approaches that utilize supervised learning for denoising, we do not require any additional training data. In such setting, while the ground-truth label, i.e., the clean data, is not available, we devise “pseudo-labels” and a novel objective function such that DNN can be trained in a same way as supervised learning to become a discrete denoiser. We experimentally show that our resulting algorithm, dubbed as Neural DUDE, significantly outperforms the previous state-of-the-art in several applications with a systematic rule of choosing the hyperparameter, which is an attractive feature in practice.
Tasks	Denoising
Published	2016-05-25
URL	http://arxiv.org/abs/1605.07779v2
PDF	http://arxiv.org/pdf/1605.07779v2.pdf
PWC	https://paperswithcode.com/paper/neural-universal-discrete-denoiser
Repo
Framework

Robust Large Margin Deep Neural Networks


Title	Robust Large Margin Deep Neural Networks
Authors	Jure Sokolic, Raja Giryes, Guillermo Sapiro, Miguel R. D. Rodrigues
Abstract	The generalization error of deep neural networks via their classification margin is studied in this work. Our approach is based on the Jacobian matrix of a deep neural network and can be applied to networks with arbitrary non-linearities and pooling layers, and to networks with different architectures such as feed forward networks and residual networks. Our analysis leads to the conclusion that a bounded spectral norm of the network’s Jacobian matrix in the neighbourhood of the training samples is crucial for a deep neural network of arbitrary depth and width to generalize well. This is a significant improvement over the current bounds in the literature, which imply that the generalization error grows with either the width or the depth of the network. Moreover, it shows that the recently proposed batch normalization and weight normalization re-parametrizations enjoy good generalization properties, and leads to a novel network regularizer based on the network’s Jacobian matrix. The analysis is supported with experimental results on the MNIST, CIFAR-10, LaRED and ImageNet datasets.
Tasks
Published	2016-05-26
URL	http://arxiv.org/abs/1605.08254v3
PDF	http://arxiv.org/pdf/1605.08254v3.pdf
PWC	https://paperswithcode.com/paper/robust-large-margin-deep-neural-networks
Repo
Framework

Complexity Results for Manipulation, Bribery and Control of the Kemeny Procedure in Judgment Aggregation


Title	Complexity Results for Manipulation, Bribery and Control of the Kemeny Procedure in Judgment Aggregation
Authors	Ronald de Haan
Abstract	We study the computational complexity of several scenarios of strategic behavior for the Kemeny procedure in the setting of judgment aggregation. In particular, we investigate (1) manipulation, where an individual aims to achieve a better group outcome by reporting an insincere individual opinion, (2) bribery, where an external agent aims to achieve an outcome with certain properties by bribing a number of individuals, and (3) control (by adding or deleting issues), where an external agent aims to achieve an outcome with certain properties by influencing the set of issues in the judgment aggregation situation. We show that determining whether these types of strategic behavior are possible (and if so, computing a policy for successful strategic behavior) is complete for the second level of the Polynomial Hierarchy. That is, we show that these problems are $\Sigma^p_2$-complete.
Tasks
Published	2016-08-08
URL	http://arxiv.org/abs/1608.02406v1
PDF	http://arxiv.org/pdf/1608.02406v1.pdf
PWC	https://paperswithcode.com/paper/complexity-results-for-manipulation-bribery
Repo
Framework

Fast Simulation of Probabilistic Boolean Networks (Technical Report)


Title	Fast Simulation of Probabilistic Boolean Networks (Technical Report)
Authors	Andrzej Mizera, Jun Pang, Qixia Yuan
Abstract	Probabilistic Boolean networks (PBNs) is an important mathematical framework widely used for modelling and analysing biological systems. PBNs are suited for modelling large biological systems, which more and more often arise in systems biology. However, the large system size poses a~significant challenge to the analysis of PBNs, in particular, to the crucial analysis of their steady-state behaviour. Numerical methods for performing steady-state analyses suffer from the state-space explosion problem, which makes the utilisation of statistical methods the only viable approach. However, such methods require long simulations of PBNs, rendering the simulation speed a crucial efficiency factor. For large PBNs and high estimation precision requirements, a slow simulation speed becomes an obstacle. In this paper, we propose a structure-based method for fast simulation of PBNs. This method first performs a network reduction operation and then divides nodes into groups for parallel simulation. Experimental results show that our method can lead to an approximately 10 times speedup for computing steady-state probabilities of a real-life biological network.
Tasks
Published	2016-04-28
URL	http://arxiv.org/abs/1605.00854v1
PDF	http://arxiv.org/pdf/1605.00854v1.pdf
PWC	https://paperswithcode.com/paper/fast-simulation-of-probabilistic-boolean
Repo
Framework

Quantum Enhanced Inference in Markov Logic Networks


Title	Quantum Enhanced Inference in Markov Logic Networks
Authors	Peter Wittek, Christian Gogolin
Abstract	Markov logic networks (MLNs) reconcile two opposing schools in machine learning and artificial intelligence: causal networks, which account for uncertainty extremely well, and first-order logic, which allows for formal deduction. An MLN is essentially a first-order logic template to generate Markov networks. Inference in MLNs is probabilistic and it is often performed by approximate methods such as Markov chain Monte Carlo (MCMC) Gibbs sampling. An MLN has many regular, symmetric structures that can be exploited at both first-order level and in the generated Markov network. We analyze the graph structures that are produced by various lifting methods and investigate the extent to which quantum protocols can be used to speed up Gibbs sampling with state preparation and measurement schemes. We review different such approaches, discuss their advantages, theoretical limitations, and their appeal to implementations. We find that a straightforward application of a recent result yields exponential speedup compared to classical heuristics in approximate probabilistic inference, thereby demonstrating another example where advanced quantum resources can potentially prove useful in machine learning.
Tasks
Published	2016-11-24
URL	http://arxiv.org/abs/1611.08104v1
PDF	http://arxiv.org/pdf/1611.08104v1.pdf
PWC	https://paperswithcode.com/paper/quantum-enhanced-inference-in-markov-logic
Repo
Framework

CLEAR: Covariant LEAst-square Re-fitting with applications to image restoration


Title	CLEAR: Covariant LEAst-square Re-fitting with applications to image restoration
Authors	C-A. Deledalle, N. Papadakis, J. Salmon, S. Vaiter
Abstract	In this paper, we propose a new framework to remove parts of the systematic errors affecting popular restoration algorithms, with a special focus for image processing tasks. Generalizing ideas that emerged for $\ell_1$ regularization, we develop an approach re-fitting the results of standard methods towards the input data. Total variation regularizations and non-local means are special cases of interest. We identify important covariant information that should be preserved by the re-fitting method, and emphasize the importance of preserving the Jacobian (w.r.t. the observed signal) of the original estimator. Then, we provide an approach that has a “twicing” flavor and allows re-fitting the restored signal by adding back a local affine transformation of the residual term. We illustrate the benefits of our method on numerical simulations for image restoration tasks.
Tasks	Image Restoration
Published	2016-06-16
URL	http://arxiv.org/abs/1606.05158v2
PDF	http://arxiv.org/pdf/1606.05158v2.pdf
PWC	https://paperswithcode.com/paper/clear-covariant-least-square-re-fitting-with
Repo
Framework