May 7, 2019

2851 words 14 mins read

Paper Group ANR 104

Uniform Information Segmentation. A New Recurrent Neural CRF for Learning Non-linear Edge Features. Automatic 3D Point Set Reconstruction from Stereo Laparoscopic Images using Deep Neural Networks. Global and Local Uncertainty Principles for Signals on Graphs. Deep Perceptual Mapping for Cross-Modal Face Recognition. Increasing the Interpretability …

Uniform Information Segmentation


Title	Uniform Information Segmentation
Authors	Radhakrishna Achanta, Pablo Márquez-Neila, Pascal Fua, Sabine Süsstrunk
Abstract	Size uniformity is one of the main criteria of superpixel methods. But size uniformity rarely conforms to the varying content of an image. The chosen size of the superpixels therefore represents a compromise - how to obtain the fewest superpixels without losing too much important detail. We propose that a more appropriate criterion for creating image segments is information uniformity. We introduce a novel method for segmenting an image based on this criterion. Since information is a natural way of measuring image complexity, our proposed algorithm leads to image segments that are smaller and denser in areas of high complexity and larger in homogeneous regions, thus simplifying the image while preserving its details. Our algorithm is simple and requires just one input parameter - a threshold on the information content. On segmentation comparison benchmarks it proves to be superior to the state-of-the-art. In addition, our method is computationally very efficient, approaching real-time performance, and is easily extensible to three-dimensional image stacks and video volumes.
Tasks
Published	2016-11-27
URL	http://arxiv.org/abs/1611.08896v1
PDF	http://arxiv.org/pdf/1611.08896v1.pdf
PWC	https://paperswithcode.com/paper/uniform-information-segmentation
Repo
Framework

A New Recurrent Neural CRF for Learning Non-linear Edge Features


Title	A New Recurrent Neural CRF for Learning Non-linear Edge Features
Authors	Shuming Ma, Xu Sun
Abstract	Conditional Random Field (CRF) and recurrent neural models have achieved success in structured prediction. More recently, there is a marriage of CRF and recurrent neural models, so that we can gain from both non-linear dense features and globally normalized CRF objective. These recurrent neural CRF models mainly focus on encode node features in CRF undirected graphs. However, edge features prove important to CRF in structured prediction. In this work, we introduce a new recurrent neural CRF model, which learns non-linear edge features, and thus makes non-linear features encoded completely. We compare our model with different neural models in well-known structured prediction tasks. Experiments show that our model outperforms state-of-the-art methods in NP chunking, shallow parsing, Chinese word segmentation and POS tagging.
Tasks	Chinese Word Segmentation, Chunking, Structured Prediction
Published	2016-11-14
URL	http://arxiv.org/abs/1611.04233v1
PDF	http://arxiv.org/pdf/1611.04233v1.pdf
PWC	https://paperswithcode.com/paper/a-new-recurrent-neural-crf-for-learning-non
Repo
Framework

Automatic 3D Point Set Reconstruction from Stereo Laparoscopic Images using Deep Neural Networks


Title	Automatic 3D Point Set Reconstruction from Stereo Laparoscopic Images using Deep Neural Networks
Authors	Balint Antal
Abstract	In this paper, an automatic approach to predict 3D coordinates from stereo laparoscopic images is presented. The approach maps a vector of pixel intensities to 3D coordinates through training a six layer deep neural network. The architectural aspects of the approach is presented and in detail and the method is evaluated on a publicly available dataset with promising results.
Tasks
Published	2016-07-31
URL	http://arxiv.org/abs/1608.00203v1
PDF	http://arxiv.org/pdf/1608.00203v1.pdf
PWC	https://paperswithcode.com/paper/automatic-3d-point-set-reconstruction-from
Repo
Framework

Global and Local Uncertainty Principles for Signals on Graphs


Title	Global and Local Uncertainty Principles for Signals on Graphs
Authors	Nathanael Perraudin, Benjamin Ricaud, David Shuman, Pierre Vandergheynst
Abstract	Uncertainty principles such as Heisenberg’s provide limits on the time-frequency concentration of a signal, and constitute an important theoretical tool for designing and evaluating linear signal transforms. Generalizations of such principles to the graph setting can inform dictionary design for graph signals, lead to algorithms for reconstructing missing information from graph signals via sparse representations, and yield new graph analysis tools. While previous work has focused on generalizing notions of spreads of a graph signal in the vertex and graph spectral domains, our approach is to generalize the methods of Lieb in order to develop uncertainty principles that provide limits on the concentration of the analysis coefficients of any graph signal under a dictionary transform whose atoms are jointly localized in the vertex and graph spectral domains. One challenge we highlight is that due to the inhomogeneity of the underlying graph data domain, the local structure in a single small region of the graph can drastically affect the uncertainty bounds for signals concentrated in different regions of the graph, limiting the information provided by global uncertainty principles. Accordingly, we suggest a new way to incorporate a notion of locality, and develop local uncertainty principles that bound the concentration of the analysis coefficients of each atom of a localized graph spectral filter frame in terms of quantities that depend on the local structure of the graph around the center vertex of the given atom. Finally, we demonstrate how our proposed local uncertainty measures can improve the random sampling of graph signals.
Tasks
Published	2016-03-10
URL	http://arxiv.org/abs/1603.03030v1
PDF	http://arxiv.org/pdf/1603.03030v1.pdf
PWC	https://paperswithcode.com/paper/global-and-local-uncertainty-principles-for
Repo
Framework


Title	Deep Perceptual Mapping for Cross-Modal Face Recognition
Authors	M. Saquib Sarfraz, Rainer Stiefelhagen
Abstract	Cross modal face matching between the thermal and visible spectrum is a much desired capability for night-time surveillance and security applications. Due to a very large modality gap, thermal-to-visible face recognition is one of the most challenging face matching problem. In this paper, we present an approach to bridge this modality gap by a significant margin. Our approach captures the highly non-linear relationship between the two modalities by using a deep neural network. Our model attempts to learn a non-linear mapping from visible to thermal spectrum while preserving the identity information. We show substantive performance improvement on three difficult thermal-visible face datasets. The presented approach improves the state-of-the-art by more than 10% on UND-X1 dataset and by more than 15-30% on NVESD dataset in terms of Rank-1 identification. Our method bridges the drop in performance due to the modality gap by more than 40%.
Tasks	Face Recognition
Published	2016-01-20
URL	http://arxiv.org/abs/1601.05347v2
PDF	http://arxiv.org/pdf/1601.05347v2.pdf
PWC	https://paperswithcode.com/paper/deep-perceptual-mapping-for-cross-modal-face
Repo
Framework

Increasing the Interpretability of Recurrent Neural Networks Using Hidden Markov Models


Title	Increasing the Interpretability of Recurrent Neural Networks Using Hidden Markov Models
Authors	Viktoriya Krakovna, Finale Doshi-Velez
Abstract	As deep neural networks continue to revolutionize various application domains, there is increasing interest in making these powerful models more understandable and interpretable, and narrowing down the causes of good and bad predictions. We focus on recurrent neural networks (RNNs), state of the art models in speech recognition and translation. Our approach to increasing interpretability is by combining an RNN with a hidden Markov model (HMM), a simpler and more transparent model. We explore various combinations of RNNs and HMMs: an HMM trained on LSTM states; a hybrid model where an HMM is trained first, then a small LSTM is given HMM state distributions and trained to fill in gaps in the HMM’s performance; and a jointly trained hybrid model. We find that the LSTM and HMM learn complementary information about the features in the text.
Tasks	Speech Recognition
Published	2016-06-16
URL	http://arxiv.org/abs/1606.05320v2
PDF	http://arxiv.org/pdf/1606.05320v2.pdf
PWC	https://paperswithcode.com/paper/increasing-the-interpretability-of-recurrent
Repo
Framework

MCMC assisted by Belief Propagaion


Title	MCMC assisted by Belief Propagaion
Authors	Sungsoo Ahn, Michael Chertkov, Jinwoo Shin
Abstract	Markov Chain Monte Carlo (MCMC) and Belief Propagation (BP) are the most popular algorithms for computational inference in Graphical Models (GM). In principle, MCMC is an exact probabilistic method which, however, often suffers from exponentially slow mixing. In contrast, BP is a deterministic method, which is typically fast, empirically very successful, however in general lacking control of accuracy over loopy graphs. In this paper, we introduce MCMC algorithms correcting the approximation error of BP, i.e., we provide a way to compensate for BP errors via a consecutive BP-aware MCMC. Our framework is based on the Loop Calculus (LC) approach which allows to express the BP error as a sum of weighted generalized loops. Although the full series is computationally intractable, it is known that a truncated series, summing up all 2-regular loops, is computable in polynomial-time for planar pair-wise binary GMs and it also provides a highly accurate approximation empirically. Motivated by this, we first propose a polynomial-time approximation MCMC scheme for the truncated series of general (non-planar) pair-wise binary models. Our main idea here is to use the Worm algorithm, known to provide fast mixing in other (related) problems, and then design an appropriate rejection scheme to sample 2-regular loops. Furthermore, we also design an efficient rejection-free MCMC scheme for approximating the full series. The main novelty underlying our design is in utilizing the concept of cycle basis, which provides an efficient decomposition of the generalized loops. In essence, the proposed MCMC schemes run on transformed GM built upon the non-trivial BP solution, and our experiments show that this synthesis of BP and MCMC outperforms both direct MCMC and bare BP schemes.
Tasks
Published	2016-05-29
URL	http://arxiv.org/abs/1605.09042v5
PDF	http://arxiv.org/pdf/1605.09042v5.pdf
PWC	https://paperswithcode.com/paper/mcmc-assisted-by-belief-propagaion
Repo
Framework

Statistics of RGBD Images


Title	Statistics of RGBD Images
Authors	Dan Rosenbaum, Yair Weiss
Abstract	Cameras that can measure the depth of each pixel in addition to its color have become easily available and are used in many consumer products worldwide. Often the depth channel is captured at lower quality compared to the RGB channels and different algorithms have been proposed to improve the quality of the D channel given the RGB channels. Typically these approaches work by assuming that edges in RGB are correlated with edges in D. In this paper we approach this problem from the standpoint of natural image statistics. We obtain examples of high quality RGBD images from a computer graphics generated movie (MPI-Sintel) and we use these examples to compare different probabilistic generative models of RGBD image patches. We then use the generative models together with a degradation model and obtain a Bayes Least Squares (BLS) estimator of the D channel given the RGB channels. Our results show that learned generative models outperform the state-of-the-art in improving the quality of depth channels given the color channels in natural images even when training is performed on artificially generated images.
Tasks
Published	2016-04-11
URL	http://arxiv.org/abs/1604.02902v1
PDF	http://arxiv.org/pdf/1604.02902v1.pdf
PWC	https://paperswithcode.com/paper/statistics-of-rgbd-images
Repo
Framework

Make Workers Work Harder: Decoupled Asynchronous Proximal Stochastic Gradient Descent


Title	Make Workers Work Harder: Decoupled Asynchronous Proximal Stochastic Gradient Descent
Authors	Yitan Li, Linli Xu, Xiaowei Zhong, Qing Ling
Abstract	Asynchronous parallel optimization algorithms for solving large-scale machine learning problems have drawn significant attention from academia to industry recently. This paper proposes a novel algorithm, decoupled asynchronous proximal stochastic gradient descent (DAP-SGD), to minimize an objective function that is the composite of the average of multiple empirical losses and a regularization term. Unlike the traditional asynchronous proximal stochastic gradient descent (TAP-SGD) in which the master carries much of the computation load, the proposed algorithm off-loads the majority of computation tasks from the master to workers, and leaves the master to conduct simple addition operations. This strategy yields an easy-to-parallelize algorithm, whose performance is justified by theoretical convergence analyses. To be specific, DAP-SGD achieves an $O(\log T/T)$ rate when the step-size is diminishing and an ergodic $O(1/\sqrt{T})$ rate when the step-size is constant, where $T$ is the number of total iterations.
Tasks
Published	2016-05-21
URL	http://arxiv.org/abs/1605.06619v1
PDF	http://arxiv.org/pdf/1605.06619v1.pdf
PWC	https://paperswithcode.com/paper/make-workers-work-harder-decoupled
Repo
Framework

Compliant Conditions for Polynomial Time Approximation of Operator Counts


Title	Compliant Conditions for Polynomial Time Approximation of Operator Counts
Authors	Tathagata Chakraborti, Sarath Sreedharan, Sailik Sengupta, T. K. Satish Kumar, Subbarao Kambhampati
Abstract	In this paper, we develop a computationally simpler version of the operator count heuristic for a particular class of domains. The contribution of this abstract is threefold, we (1) propose an efficient closed form approximation to the operator count heuristic using the Lagrangian dual; (2) leverage compressed sensing techniques to obtain an integer approximation for operator counts in polynomial time; and (3) discuss the relationship of the proposed formulation to existing heuristics and investigate properties of domains where such approaches appear to be useful.
Tasks
Published	2016-05-25
URL	http://arxiv.org/abs/1605.07989v2
PDF	http://arxiv.org/pdf/1605.07989v2.pdf
PWC	https://paperswithcode.com/paper/compliant-conditions-for-polynomial-time
Repo
Framework

Dealing with a large number of classes – Likelihood, Discrimination or Ranking?


Title	Dealing with a large number of classes – Likelihood, Discrimination or Ranking?
Authors	David Barber, Aleksandar Botev
Abstract	We consider training probabilistic classifiers in the case of a large number of classes. The number of classes is assumed too large to perform exact normalisation over all classes. To account for this we consider a simple approach that directly approximates the likelihood. We show that this simple approach works well on toy problems and is competitive with recently introduced alternative non-likelihood based approximations. Furthermore, we relate this approach to a simple ranking objective. This leads us to suggest a specific setting for the optimal threshold in the ranking objective.
Tasks
Published	2016-06-22
URL	http://arxiv.org/abs/1606.06959v2
PDF	http://arxiv.org/pdf/1606.06959v2.pdf
PWC	https://paperswithcode.com/paper/dealing-with-a-large-number-of-classes
Repo
Framework

The Possibilities and Limitations of Private Prediction Markets


Title	The Possibilities and Limitations of Private Prediction Markets
Authors	Rachel Cummings, David M. Pennock, Jennifer Wortman Vaughan
Abstract	We consider the design of private prediction markets, financial markets designed to elicit predictions about uncertain events without revealing too much information about market participants’ actions or beliefs. Our goal is to design market mechanisms in which participants’ trades or wagers influence the market’s behavior in a way that leads to accurate predictions, yet no single participant has too much influence over what others are able to observe. We study the possibilities and limitations of such mechanisms using tools from differential privacy. We begin by designing a private one-shot wagering mechanism in which bettors specify a belief about the likelihood of a future event and a corresponding monetary wager. Wagers are redistributed among bettors in a way that more highly rewards those with accurate predictions. We provide a class of wagering mechanisms that are guaranteed to satisfy truthfulness, budget balance in expectation, and other desirable properties while additionally guaranteeing epsilon-joint differential privacy in the bettors’ reported beliefs, and analyze the trade-off between the achievable level of privacy and the sensitivity of a bettor’s payment to her own report. We then ask whether it is possible to obtain privacy in dynamic prediction markets, focusing our attention on the popular cost-function framework in which securities with payments linked to future events are bought and sold by an automated market maker. We show that under general conditions, it is impossible for such a market maker to simultaneously achieve bounded worst-case loss and epsilon-differential privacy without allowing the privacy guarantee to degrade extremely quickly as the number of trades grows, making such markets impractical in settings in which privacy is valued. We conclude by suggesting several avenues for potentially circumventing this lower bound.
Tasks
Published	2016-02-24
URL	http://arxiv.org/abs/1602.07362v1
PDF	http://arxiv.org/pdf/1602.07362v1.pdf
PWC	https://paperswithcode.com/paper/the-possibilities-and-limitations-of-private
Repo
Framework

A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits


Title	A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits
Authors	Pratik Gajane, Tanguy Urvoy, Fabrice Clérot
Abstract	We study the K-armed dueling bandit problem which is a variation of the classical Multi-Armed Bandit (MAB) problem in which the learner receives only relative feedback about the selected pairs of arms. We propose a new algorithm called Relative Exponential-weight algorithm for Exploration and Exploitation (REX3) to handle the adversarial utility-based formulation of this problem. This algorithm is a non-trivial extension of the Exponential-weight algorithm for Exploration and Exploitation (EXP3) algorithm. We prove a finite time expected regret upper bound of order O(sqrt(K ln(K)T)) for this algorithm and a general lower bound of order omega(sqrt(KT)). At the end, we provide experimental results using real data from information retrieval applications.
Tasks	Information Retrieval
Published	2016-01-15
URL	http://arxiv.org/abs/1601.03855v1
PDF	http://arxiv.org/pdf/1601.03855v1.pdf
PWC	https://paperswithcode.com/paper/a-relative-exponential-weighing-algorithm-for
Repo
Framework

Consistency constraints for overlapping data clustering


Title	Consistency constraints for overlapping data clustering
Authors	Jared Culbertson, Dan P. Guralnik, Jakob Hansen, Peter F. Stiller
Abstract	We examine overlapping clustering schemes with functorial constraints, in the spirit of Carlsson–Memoli. This avoids issues arising from the chaining required by partition-based methods. Our principal result shows that any clustering functor is naturally constrained to refine single-linkage clusters and be refined by maximal-linkage clusters. We work in the context of metric spaces with non-expansive maps, which is appropriate for modeling data processing which does not increase information content.
Tasks
Published	2016-08-15
URL	http://arxiv.org/abs/1608.04331v1
PDF	http://arxiv.org/pdf/1608.04331v1.pdf
PWC	https://paperswithcode.com/paper/consistency-constraints-for-overlapping-data
Repo
Framework

A New Manifold Distance Measure for Visual Object Categorization


Title	A New Manifold Distance Measure for Visual Object Categorization
Authors	Fengfu Li, Xiayuan Huang, Hong Qiao, Bo Zhang
Abstract	Manifold distances are very effective tools for visual object recognition. However, most of the traditional manifold distances between images are based on the pixel-level comparison and thus easily affected by image rotations and translations. In this paper, we propose a new manifold distance to model the dissimilarities between visual objects based on the Complex Wavelet Structural Similarity (CW-SSIM) index. The proposed distance is more robust to rotations and translations of images than the traditional manifold distance and the CW-SSIM index based distance. In addition, the proposed distance is combined with the $k$-medoids clustering method to derive a new clustering method for visual object categorization. Experiments on Coil-20, Coil-100 and Olivetti Face Databases show that the proposed distance measure is better for visual object categorization than both the traditional manifold distances and the CW-SSIM index based distances.
Tasks	Object Recognition
Published	2016-05-12
URL	http://arxiv.org/abs/1605.03865v1
PDF	http://arxiv.org/pdf/1605.03865v1.pdf
PWC	https://paperswithcode.com/paper/a-new-manifold-distance-measure-for-visual
Repo
Framework