May 7, 2019

2912 words 14 mins read

Paper Group ANR 142

Semi-supervised Kernel Metric Learning Using Relative Comparisons. A MIP Backend for the IDP System. A Large Deformation Diffeomorphic Approach to Registration of CLARITY Images via Mutual Information. Small coherence implies the weak Null Space Property. Anytime Inference in Valuation Algebras. Stochastic Averaging for Constrained Optimization wit …

Semi-supervised Kernel Metric Learning Using Relative Comparisons


Title	Semi-supervised Kernel Metric Learning Using Relative Comparisons
Authors	Ehsan Amid, Aristides Gionis, Antti Ukkonen
Abstract	We consider the problem of metric learning subject to a set of constraints on relative-distance comparisons between the data items. Such constraints are meant to reflect side-information that is not expressed directly in the feature vectors of the data items. The relative-distance constraints used in this work are particularly effective in expressing structures at finer level of detail than must-link (ML) and cannot-link (CL) constraints, which are most commonly used for semi-supervised clustering. Relative-distance constraints are thus useful in settings where providing an ML or a CL constraint is difficult because the granularity of the true clustering is unknown. Our main contribution is an efficient algorithm for learning a kernel matrix using the log determinant divergence — a variant of the Bregman divergence — subject to a set of relative-distance constraints. The learned kernel matrix can then be employed by many different kernel methods in a wide range of applications. In our experimental evaluations, we consider a semi-supervised clustering setting and show empirically that kernels found by our algorithm yield clusterings of higher quality than existing approaches that either use ML/CL constraints or a different means to implement the supervision using relative comparisons.
Tasks	Metric Learning
Published	2016-12-01
URL	http://arxiv.org/abs/1612.00086v2
PDF	http://arxiv.org/pdf/1612.00086v2.pdf
PWC	https://paperswithcode.com/paper/semi-supervised-kernel-metric-learning-using
Repo
Framework

A MIP Backend for the IDP System


Title	A MIP Backend for the IDP System
Authors	San Pham, Jo Devriendt, Maurice Bruynooghe, Patrick De Causmaecker
Abstract	The IDP knowledge base system currently uses MiniSAT(ID) as its backend Constraint Programming (CP) solver. A few similar systems have used a Mixed Integer Programming (MIP) solver as backend. However, so far little is known about when the MIP solver is preferable. This paper explores this question. It describes the use of CPLEX as a backend for IDP and reports on experiments comparing both backends.
Tasks
Published	2016-09-02
URL	http://arxiv.org/abs/1609.00759v1
PDF	http://arxiv.org/pdf/1609.00759v1.pdf
PWC	https://paperswithcode.com/paper/a-mip-backend-for-the-idp-system
Repo
Framework

A Large Deformation Diffeomorphic Approach to Registration of CLARITY Images via Mutual Information


Title	A Large Deformation Diffeomorphic Approach to Registration of CLARITY Images via Mutual Information
Authors	Kwame S. Kutten, Nicolas Charon, Michael I. Miller, J. T. Ratnanather, Jordan Matelsky, Alexander D. Baden, Kunal Lillaney, Karl Deisseroth, Li Ye, Joshua T. Vogelstein
Abstract	CLARITY is a method for converting biological tissues into translucent and porous hydrogel-tissue hybrids. This facilitates interrogation with light sheet microscopy and penetration of molecular probes while avoiding physical slicing. In this work, we develop a pipeline for registering CLARIfied mouse brains to an annotated brain atlas. Due to the novelty of this microscopy technique it is impractical to use absolute intensity values to align these images to existing standard atlases. Thus we adopt a large deformation diffeomorphic approach for registering images via mutual information matching. Furthermore we show how a cascaded multi-resolution approach can improve registration quality while reducing algorithm run time. As acquired image volumes were over a terabyte in size, they were far too large for work on personal computers. Therefore the NeuroData computational infrastructure was deployed for multi-resolution storage and visualization of these images and aligned annotations on the web.
Tasks
Published	2016-12-01
URL	http://arxiv.org/abs/1612.00356v3
PDF	http://arxiv.org/pdf/1612.00356v3.pdf
PWC	https://paperswithcode.com/paper/a-large-deformation-diffeomorphic-approach-to
Repo
Framework

Small coherence implies the weak Null Space Property


Title	Small coherence implies the weak Null Space Property
Authors	Stéphane Chrétien, Zhen Wai Olivier Ho
Abstract	In the Compressed Sensing community, it is well known that given a matrix $X \in \mathbb R^{n\times p}$ with $\ell_2$ normalized columns, the Restricted Isometry Property (RIP) implies the Null Space Property (NSP). It is also well known that a small Coherence $\mu$ implies a weak RIP, i.e. the singular values of $X_T$ lie between $1-\delta$ and $1+\delta$ for “most” index subsets $T \subset {1,\ldots,p}$ with size governed by $\mu$ and $\delta$. In this short note, we show that a small Coherence implies a weak Null Space Property, i.e. $\Vert h_T\Vert_2 \le C \ \Vert h_{T^c}\Vert_1/\sqrt{s}$ for most $T \subset {1,\ldots,p}$ with cardinality $T\le s$. We moreover prove some singular value perturbation bounds that may also prove useful for other applications.
Tasks
Published	2016-06-29
URL	http://arxiv.org/abs/1606.09193v1
PDF	http://arxiv.org/pdf/1606.09193v1.pdf
PWC	https://paperswithcode.com/paper/small-coherence-implies-the-weak-null-space
Repo
Framework

Anytime Inference in Valuation Algebras


Title	Anytime Inference in Valuation Algebras
Authors	Abhishek Dasgupta, Samson Abramsky
Abstract	Anytime inference is inference performed incrementally, with the accuracy of the inference being controlled by a tunable parameter, usually time. Such anytime inference algorithms are also usually interruptible, gradually converging to the exact inference value until terminated. While anytime inference algorithms for specific domains like probability potentials exist in the literature, our objective in this article is to obtain an anytime inference algorithm which is sufficiently generic to cover a wide range of domains. For this we utilise the theory of generic inference as a basis for constructing an anytime inference algorithm, and in particular, extending work done on ordered valuation algebras. The novel contribution of this work is the construction of anytime algorithms in a generic framework, which automatically gives us instantiations in various useful domains. We also show how to apply this generic framework for anytime inference in semiring induced valuation algebras, an important subclass of valuation algebras, which includes instances like probability potentials, disjunctive normal forms and distributive lattices. Keywords: Approximation; Anytime algorithms; Resource-bounded computation; Generic inference; Valuation algebras; Local computation; Binary join trees.
Tasks
Published	2016-05-13
URL	http://arxiv.org/abs/1605.04218v1
PDF	http://arxiv.org/pdf/1605.04218v1.pdf
PWC	https://paperswithcode.com/paper/anytime-inference-in-valuation-algebras
Repo
Framework

Stochastic Averaging for Constrained Optimization with Application to Online Resource Allocation


Title	Stochastic Averaging for Constrained Optimization with Application to Online Resource Allocation
Authors	Tianyi Chen, Aryan Mokhtari, Xin Wang, Alejandro Ribeiro, Georgios B. Giannakis
Abstract	Existing approaches to resource allocation for nowadays stochastic networks are challenged to meet fast convergence and tolerable delay requirements. The present paper leverages online learning advances to facilitate stochastic resource allocation tasks. By recognizing the central role of Lagrange multipliers, the underlying constrained optimization problem is formulated as a machine learning task involving both training and operational modes, with the goal of learning the sought multipliers in a fast and efficient manner. To this end, an order-optimal offline learning approach is developed first for batch training, and it is then generalized to the online setting with a procedure termed learn-and-adapt. The novel resource allocation protocol permeates benefits of stochastic approximation and statistical learning to obtain low-complexity online updates with learning errors close to the statistical accuracy limits, while still preserving adaptation performance, which in the stochastic network optimization context guarantees queue stability. Analysis and simulated tests demonstrate that the proposed data-driven approach improves the delay and convergence performance of existing resource allocation schemes.
Tasks
Published	2016-10-07
URL	http://arxiv.org/abs/1610.02143v2
PDF	http://arxiv.org/pdf/1610.02143v2.pdf
PWC	https://paperswithcode.com/paper/stochastic-averaging-for-constrained
Repo
Framework

Identifiability of an X-rank decomposition of polynomial maps


Title	Identifiability of an X-rank decomposition of polynomial maps
Authors	Pierre Comon, Yang Qi, Konstantin Usevich
Abstract	In this paper, we study a polynomial decomposition model that arises in problems of system identification, signal processing and machine learning. We show that this decomposition is a special case of the X-rank decomposition — a powerful novel concept in algebraic geometry that generalizes the tensor CP decomposition. We prove new results on generic/maximal rank and on identifiability of a particular polynomial decomposition model. In the paper, we try to make results and basic tools accessible for general audience (assuming no knowledge of algebraic geometry or its prerequisites).
Tasks
Published	2016-03-04
URL	http://arxiv.org/abs/1603.01566v3
PDF	http://arxiv.org/pdf/1603.01566v3.pdf
PWC	https://paperswithcode.com/paper/identifiability-of-an-x-rank-decomposition-of
Repo
Framework

Unanimously acceptable agreements for negotiation teams in unpredictable domains


Title	Unanimously acceptable agreements for negotiation teams in unpredictable domains
Authors	Victor Sanchez-Anguix, Reyhan Aydogan, Vicente Julian, Catholijn Jonker
Abstract	A negotiation team is a set of agents with common and possibly also conflicting preferences that forms one of the parties of a negotiation. A negotiation team is involved in two decision making processes simultaneously, a negotiation with the opponents, and an intra-team process to decide on the moves to make in the negotiation. This article focuses on negotiation team decision making for circumstances that require unanimity of team decisions. Existing agent-based approaches only guarantee unanimity in teams negotiating in domains exclusively composed of predictable and compatible issues. This article presents a model for negotiation teams that guarantees unanimous team decisions in domains consisting of predictable and compatible, and also unpredictable issues. Moreover, the article explores the influence of using opponent, and team member models in the proposing strategies that team members use. Experimental results show that the team benefits if team members employ Bayesian learning to model their teammates’ preferences.
Tasks	Decision Making
Published	2016-04-16
URL	http://arxiv.org/abs/1604.04725v1
PDF	http://arxiv.org/pdf/1604.04725v1.pdf
PWC	https://paperswithcode.com/paper/unanimously-acceptable-agreements-for
Repo
Framework

Monte Carlo sampling for stochastic weight functions


Title	Monte Carlo sampling for stochastic weight functions
Authors	Daan Frenkel, K. Julian Schrenk, Stefano Martiniani
Abstract	Conventional Monte Carlo simulations are stochastic in the sense that the acceptance of a trial move is decided by comparing a computed acceptance probability with a random number, uniformly distributed between 0 and 1. Here we consider the case that the weight determining the acceptance probability itself is fluctuating. This situation is common in many numerical studies. We show that it is possible to construct a rigorous Monte Carlo algorithm that visits points in state space with a probability proportional to their average weight. The same approach has the potential to transform the methodology of a certain class of high-throughput experiments or the analysis of noisy datasets.
Tasks
Published	2016-12-19
URL	http://arxiv.org/abs/1612.06131v1
PDF	http://arxiv.org/pdf/1612.06131v1.pdf
PWC	https://paperswithcode.com/paper/monte-carlo-sampling-for-stochastic-weight
Repo
Framework

Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes


Title	Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes
Authors	Dan Garber, Ofer Meshi
Abstract	Recently, several works have shown that natural modifications of the classical conditional gradient method (aka Frank-Wolfe algorithm) for constrained convex optimization, provably converge with a linear rate when: i) the feasible set is a polytope, and ii) the objective is smooth and strongly-convex. However, all of these results suffer from two significant shortcomings: large memory requirement due to the need to store an explicit convex decomposition of the current iterate, and as a consequence, large running-time overhead per iteration, and worst case convergence rate that depends unfavorably on the dimension. In this work we present a new conditional gradient variant and a corresponding analysis that improves on both of the above shortcomings. In particular: both memory and computation overheads are only linear in the dimension. Moreover, in case the optimal solution is sparse, the new convergence rate replaces a factor which is at least linear in the dimension in previous works, with a linear dependence on the number of non-zeros in the optimal solution. At the heart of our method, and corresponding analysis, is a novel way to compute decomposition-invariant away-steps. While our theoretical guarantees do not apply to any polytope, they apply to several important structured polytopes that capture central concepts such as paths in graphs, perfect matchings in bipartite graphs, marginal distributions that arise in structured prediction tasks, and more. Our theoretical findings are complemented by empirical evidence which shows that our method delivers state-of-the-art performance.
Tasks	Structured Prediction
Published	2016-05-20
URL	http://arxiv.org/abs/1605.06492v1
PDF	http://arxiv.org/pdf/1605.06492v1.pdf
PWC	https://paperswithcode.com/paper/linear-memory-and-decomposition-invariant
Repo
Framework

Robust Confidence Intervals in High-Dimensional Left-Censored Regression


Title	Robust Confidence Intervals in High-Dimensional Left-Censored Regression
Authors	Jelena Bradic, Jiaqi Guo
Abstract	This paper develops robust confidence intervals in high-dimensional and left-censored regression. Type-I censored regression models are extremely common in practice, where a competing event makes the variable of interest unobservable. However, techniques developed for entirely observed data do not directly apply to the censored observations. In this paper, we develop smoothed estimating equations that augment the de-biasing method, such that the resulting estimator is adaptive to censoring and is more robust to the misspecification of the error distribution. We propose a unified class of robust estimators, including Mallow’s, Schweppe’s and Hill-Ryan’s one-step estimator. In the ultra-high-dimensional setting, where the dimensionality can grow exponentially with the sample size, we show that as long as the preliminary estimator converges faster than $n^{-1/4}$, the one-step estimator inherits asymptotic distribution of fully iterated version. Moreover, we show that the size of the residuals of the Bahadur representation matches those of the simple linear models, $s^{3/4 } (\log (p \vee n))^{3/4} / n^{1/4}$ – that is, the effects of censoring asymptotically disappear. Simulation studies demonstrate that our method is adaptive to the censoring level and asymmetry in the error distribution, and does not lose efficiency when the errors are from symmetric distributions. Finally, we apply the developed method to a real data set from the MAQC-II repository that is related to the HIV-1 study.
Tasks
Published	2016-09-22
URL	http://arxiv.org/abs/1609.07165v1
PDF	http://arxiv.org/pdf/1609.07165v1.pdf
PWC	https://paperswithcode.com/paper/robust-confidence-intervals-in-high
Repo
Framework

Deep Neural Networks for Improved, Impromptu Trajectory Tracking of Quadrotors


Title	Deep Neural Networks for Improved, Impromptu Trajectory Tracking of Quadrotors
Authors	Qiyang Li, Jingxing Qian, Zining Zhu, Xuchan Bao, Mohamed K. Helwa, Angela P. Schoellig
Abstract	Trajectory tracking control for quadrotors is important for applications ranging from surveying and inspection, to film making. However, designing and tuning classical controllers, such as proportional-integral-derivative (PID) controllers, to achieve high tracking precision can be time-consuming and difficult, due to hidden dynamics and other non-idealities. The Deep Neural Network (DNN), with its superior capability of approximating abstract, nonlinear functions, proposes a novel approach for enhancing trajectory tracking control. This paper presents a DNN-based algorithm as an add-on module that improves the tracking performance of a classical feedback controller. Given a desired trajectory, the DNNs provide a tailored reference input to the controller based on their gained experience. The input aims to achieve a unity map between the desired and the output trajectory. The motivation for this work is an interactive “fly-as-you-draw” application, in which a user draws a trajectory on a mobile device, and a quadrotor instantly flies that trajectory with the DNN-enhanced control system. Experimental results demonstrate that the proposed approach improves the tracking precision for user-drawn trajectories after the DNNs are trained on selected periodic trajectories, suggesting the method’s potential in real-world applications. Tracking errors are reduced by around 40-50% for both training and testing trajectories from users, highlighting the DNNs’ capability of generalizing knowledge.
Tasks
Published	2016-10-20
URL	http://arxiv.org/abs/1610.06283v2
PDF	http://arxiv.org/pdf/1610.06283v2.pdf
PWC	https://paperswithcode.com/paper/deep-neural-networks-for-improved-impromptu
Repo
Framework

A Proximal Stochastic Quasi-Newton Algorithm


Title	A Proximal Stochastic Quasi-Newton Algorithm
Authors	Luo Luo, Zihao Chen, Zhihua Zhang, Wu-Jun Li
Abstract	In this paper, we discuss the problem of minimizing the sum of two convex functions: a smooth function plus a non-smooth function. Further, the smooth part can be expressed by the average of a large number of smooth component functions, and the non-smooth part is equipped with a simple proximal mapping. We propose a proximal stochastic second-order method, which is efficient and scalable. It incorporates the Hessian in the smooth part of the function and exploits multistage scheme to reduce the variance of the stochastic gradient. We prove that our method can achieve linear rate of convergence.
Tasks
Published	2016-01-31
URL	http://arxiv.org/abs/1602.00223v2
PDF	http://arxiv.org/pdf/1602.00223v2.pdf
PWC	https://paperswithcode.com/paper/a-proximal-stochastic-quasi-newton-algorithm
Repo
Framework

Experiments in Linear Template Combination using Genetic Algorithms


Title	Experiments in Linear Template Combination using Genetic Algorithms
Authors	Nikhilesh Bhatnagar, Radhika Mamidi
Abstract	Natural Language Generation systems typically have two parts - strategic (‘what to say’) and tactical (‘how to say’). We present our experiments in building an unsupervised corpus-driven template based tactical NLG system. We consider templates as a sequence of words containing gaps. Our idea is based on the observation that templates are grammatical locally (within their textual span). We posit the construction of a sentence as a highly restricted sequence of such templates. This work is an attempt to explore the resulting search space using Genetic Algorithms to arrive at acceptable solutions. We present a baseline implementation of this approach which outputs gapped text.
Tasks	Text Generation
Published	2016-05-24
URL	http://arxiv.org/abs/1605.07366v1
PDF	http://arxiv.org/pdf/1605.07366v1.pdf
PWC	https://paperswithcode.com/paper/experiments-in-linear-template-combination
Repo
Framework

Accurate and Efficient Hyperbolic Tangent Activation Function on FPGA using the DCT Interpolation Filter


Title	Accurate and Efficient Hyperbolic Tangent Activation Function on FPGA using the DCT Interpolation Filter
Authors	Ahmed M. Abdelsalam, J. M. Pierre Langlois, F. Cheriet
Abstract	Implementing an accurate and fast activation function with low cost is a crucial aspect to the implementation of Deep Neural Networks (DNNs) on FPGAs. We propose a high-accuracy approximation approach for the hyperbolic tangent activation function of artificial neurons in DNNs. It is based on the Discrete Cosine Transform Interpolation Filter (DCTIF). The proposed architecture combines simple arithmetic operations on stored samples of the hyperbolic tangent function and on input data. The proposed DCTIF implementation achieves two orders of magnitude greater precision than previous work while using the same or fewer computational resources. Various combinations of DCTIF parameters can be chosen to tradeoff the accuracy and complexity of the hyperbolic tangent function. In one case, the proposed architecture approximates the hyperbolic tangent activation function with 10E-5 maximum error while requiring only 1.52 Kbits memory and 57 LUTs of a Virtex-7 FPGA. We also discuss how the activation function accuracy affects the performance of DNNs in terms of their training and testing accuracies. We show that a high accuracy approximation can be necessary in order to maintain the same DNN training and testing performances realized by the exact function.
Tasks
Published	2016-09-25
URL	http://arxiv.org/abs/1609.07750v1
PDF	http://arxiv.org/pdf/1609.07750v1.pdf
PWC	https://paperswithcode.com/paper/accurate-and-efficient-hyperbolic-tangent
Repo
Framework