S. V. N. Vishwanathan

ICLR Conference 2016 Conference Paper

BlackOut: Speeding up Recurrent Neural Network Language Models With Very Large Vocabularies

• Shihao Ji 0001
• S. V. N. Vishwanathan
• Nadathur Satish
• Michael J. Anderson
• Pradeep Dubey

We propose BlackOut, an approximation algorithm to efficiently train massive recurrent neural network language models (RNNLMs) with million word vocabularies. BlackOut is motivated by using a discriminative loss, and we describe a new sampling strategy which significantly reduces computation while improving stability, sample efficiency, and rate of convergence. One way to understand BlackOut is to view it as an extension of the DropOut strategy to the output layer, wherein we use a discriminative training loss and a weighted sampling scheme. We also establish close connections between BlackOut, importance sampling, and noise contrastive estimation (NCE). Our experiments, on the recently released one billion word language modeling benchmark, demonstrate scalability and accuracy of BlackOut; we outperform the state-of-the art, and achieve the lowest perplexity scores on this dataset. Moreover, unlike other established methods which typically require GPUs or CPU clusters, we show that a carefully implemented version of BlackOut requires only 1-10 days on a single machine to train a RNNLM with a million word vocabulary and billions of parameters on one billion words. Although we describe BlackOut in the context of RNNLM training, it can be used to any networks with large softmax output layers.

NeurIPS Conference 2015 Conference Paper

A Structural Smoothing Framework For Robust Graph Comparison

• Pinar Yanardag
• S. V. N. Vishwanathan

In this paper, we propose a general smoothing framework for graph kernels by taking \textit{structural similarity} into account, and apply it to derive smoothed variants of popular graph kernels. Our framework is inspired by state-of-the-art smoothing techniques used in natural language processing (NLP). However, unlike NLP applications which primarily deal with strings, we show how one can apply smoothing to a richer class of inter-dependent sub-structures that naturally arise in graphs. Moreover, we discuss extensions of the Pitman-Yor process that can be adapted to smooth structured objects thereby leading to novel graph kernels. Our kernels are able to tackle the diagonal dominance problem, while respecting the structural similarity between sub-structures, especially under the presence of edge or label noise. Experimental evaluation shows that not only our kernels outperform the unsmoothed variants, but also achieve statistically significant improvements in classification accuracy over several other graph kernels that have been recently proposed in literature. Our kernels are competitive in terms of runtime, and offer a viable option for practitioners.

ICML Conference 2012 Conference Paper

Robust Classification with Adiabatic Quantum Optimization

• Vasil S. Denchev
• Nan Ding 0002
• S. V. N. Vishwanathan
• Hartmut Neven

SODA Conference 2011 Conference Paper

New Approximation Algorithms for Minimum Enclosing Convex Shapes

• Ankan Saha
• S. V. N. Vishwanathan
• Xinhua Zhang

UAI Conference 2011 Conference Paper

Smoothing Multivariate Performance Measures

• Xinhua Zhang
• Ankan Saha
• S. V. N. Vishwanathan

NeurIPS Conference 2011 Conference Paper

t-divergence Based Approximate Inference

• Nan Ding
• Yuan Qi
• S. V. N. Vishwanathan

Approximate inference is an important technique for dealing with large, intractable graphical models based on the exponential family of distributions. We extend the idea of approximate inference to the t-exponential family by defining a new t-divergence. This divergence measure is obtained via convex duality between the log-partition function of the t-exponential family and a new t-entropy. We illustrate our approach on the Bayes Point Machine with a Student's t-prior.

ICML Conference 2010 Conference Paper

Large Scale Max-Margin Multi-Label Classification with Priors

• Bharath Hariharan
• Lihi Zelnik-Manor
• S. V. N. Vishwanathan
• Manik Varma

NeurIPS Conference 2010 Conference Paper

Lower Bounds on Rate of Convergence of Cutting Plane Methods

• Xinhua Zhang
• Ankan Saha
• S. V. N. Vishwanathan

In a recent paper Joachims (2006) presented SVM-Perf, a cutting plane method (CPM) for training linear Support Vector Machines (SVMs) which converges to an $\epsilon$ accurate solution in $O(1/\epsilon^{2})$ iterations. By tightening the analysis, Teo et al. (2010) showed that $O(1/\epsilon)$ iterations suffice. Given the impressive convergence speed of CPM on a number of practical problems, it was conjectured that these rates could be further improved. In this paper we disprove this conjecture. We present counter examples which are not only applicable for training linear SVMs with hinge loss, but also hold for support vector methods which optimize a \emph{multivariate} performance score. However, surprisingly, these problems are not inherently hard. By exploiting the structure of the objective function we can devise an algorithm that converges in $O(1/\sqrt{\epsilon})$ iterations.

NeurIPS Conference 2010 Conference Paper

Multiple Kernel Learning and the SMO Algorithm

• Zhaonan Sun
• Nawanol Ampornpunt
• Manik Varma
• S. V. N. Vishwanathan

Our objective is to train $p$-norm Multiple Kernel Learning (MKL) and, more generally, linear MKL regularised by the Bregman divergence, using the Sequential Minimal Optimization (SMO) algorithm. The SMO algorithm is simple, easy to implement and adapt, and efficiently scales to large problems. As a result, it has gained widespread acceptance and SVMs are routinely trained using SMO in diverse real world applications. Training using SMO has been a long standing goal in MKL for the very same reasons. Unfortunately, the standard MKL dual is not differentiable, and therefore can not be optimised using SMO style co-ordinate ascent. In this paper, we demonstrate that linear MKL regularised with the $p$-norm squared, or with certain Bregman divergences, can indeed be trained using SMO. The resulting algorithm retains both simplicity and efficiency and is significantly faster than the state-of-the-art specialised $p$-norm MKL solvers. We show that we can train on a hundred thousand kernels in approximately seven minutes and on fifty thousand points in less than half an hour on a single core.

NeurIPS Conference 2010 Conference Paper

Multitask Learning without Label Correspondences

• Novi Quadrianto
• James Petterson
• Tibério Caetano
• Alex Smola
• S. V. N. Vishwanathan

We propose an algorithm to perform multitask learning where each task has potentially distinct label sets and label correspondences are not readily available. This is in contrast with existing methods which either assume that the label sets shared by different tasks are the same or that there exists a label mapping oracle. Our method directly maximizes the mutual information among the labels, and we show that the resulting objective function can be efficiently optimized using existing algorithms. Our proposed approach has a direct application for data integration with different label spaces for the purpose of classification, such as integrating Yahoo! and DMOZ web directories.

NeurIPS Conference 2010 Conference Paper

t-logistic regression

• Nan Ding
• S. V. N. Vishwanathan

We extend logistic regression by using t-exponential families which were introduced recently in statistical physics. This gives rise to a regularized risk minimization problem with a non-convex loss function. An efficient block coordinate descent optimization scheme can be derived for estimating the parameters. Because of the nature of the loss function, our algorithm is tolerant to label noise. Furthermore, unlike other algorithms which employ non-convex loss functions, our algorithm is fairly robust to the choice of initial values. We verify both these observations empirically on a number of synthetic and real datasets.

UAI Conference 2009 Conference Paper

The Entire Quantile Path of a Risk-Agnostic SVM Classifier

• Jin Yu
• S. V. N. Vishwanathan
• Jian Zhang 0003

It is obvious that the hinge loss l(·) is non-negative and convex in w. The loss function measures the discrepancy between y and the prediction given by sign(w> x), while the L2 regularizer with regularization constant λ > 0 controls the complexity of the solution w. It has been shown (Lin, 2002) that the minimizer of the hinge loss is exactly sign(η(x) − 1/2), where η(x) = P (Y = 1|X = x) is the probability of Y = 1 conditioned on X = x. Thus the SVM solution should approach the Bayes rule as the sample size gets large with appropriately chosen function class. A quantile binary classifier uses the rule: Classify x as +1 if P (Y = 1|X = x) ≥ τ, and as −1 otherwise, for a fixed quantile parameter τ ∈ [0, 1]. It has been shown that Support Vector Machines (SVMs) in the limit are quantile classifiers with τ = 12. In this paper, we show that by using asymmetric cost of misclassification SVMs can be appropriately extended to recover, in the limit, the quantile binary classifier for any τ. We then present a principled algorithm to solve the extended SVM classifier for all values of τ simultaneously. This has two implications: First, one can recover the entire conditional distribution P (Y = 1|X = x) = τ for τ ∈ [0, 1]. Second, we can build a risk-agnostic SVM classifier where the cost of misclassification need not be known apriori. Preliminary numerical experiments show the effectiveness of the proposed algorithm. 1 One problem of the standard SVM is that even though we can use the resulting SVM classifier ŵ = arg minw J(w) to classify a new observation x, the prediction w> x does not have probabilistic interpretation. More importantly, the SVM classification results cannot be directly applied to situations where the misclassification cost is asymmetric, i. e. when the cost of a false positive error is different from that of a false negative error. To address such a problem, several methods have been proposed to convert the SVM output into well-calibrated probabilistic scores, such as (Platt, 2000). However, such methods either rely on parametric assumption or lack theoretical justification about the transformed scores.

ICML Conference 2009 Conference Paper

Tutorial summary: Survey of boosting from an optimization perspective

• Manfred K. Warmuth
• S. V. N. Vishwanathan

ICML Conference 2008 Conference Paper

A quasi-Newton approach to non-smooth convex optimization

• Jin Yu
• S. V. N. Vishwanathan
• Simon Günter
• Nicol N. Schraudolph

NeurIPS Conference 2007 Conference Paper

Bundle Methods for Machine Learning

• Quoc Le
• Alex Smola
• S. V. N. Vishwanathan

We present a globally convergent method for regularized risk minimization prob- lems. Our method applies to Support Vector estimation, regression, Gaussian Processes, and any other regularized risk minimization setting which leads to a convex optimization problem. SVMPerf can be shown to be a special case of our approach. In addition to the unified framework we present tight convergence bounds, which show that our algorithm converges in O(1/
) steps to
precision for general convex problems and in O(log(1/
)) steps for continuously differen- tiable problems. We demonstrate in experiments the performance of our approach.

ICML Conference 2007 Conference Paper

Conditional random fields for multi-agent reinforcement learning

• Xinhua Zhang
• Douglas Aberdeen
• S. V. N. Vishwanathan

JMLR Journal 2007 Journal Article

Fast Iterative Kernel Principal Component Analysis

• Simon Günter
• Nicol N. Schraudolph
• S. V. N. Vishwanathan

We develop gain adaptation methods that improve convergence of the kernel Hebbian algorithm (KHA) for iterative kernel PCA (Kim et al., 2005). KHA has a scalar gain parameter which is either held constant or decreased according to a predetermined annealing schedule, leading to slow convergence. We accelerate it by incorporating the reciprocal of the current estimated eigenvalues as part of a gain vector. An additional normalization term then allows us to eliminate a tuning parameter in the annealing schedule. Finally we derive and apply stochastic meta-descent (SMD) gain vector adaptation (Schraudolph, 1999, 2002) in reproducing kernel Hilbert space to further speed up convergence. Experimental results on kernel PCA and spectral clustering of USPS digits, motion capture and image denoising, and image super-resolution tasks confirm that our methods converge substantially faster than conventional KHA. To demonstrate scalability, we perform kernel PCA on the entire MNIST data set. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

ICML Conference 2007 Conference Paper

Learning to compress images and videos

• Li Cheng 0001
• S. V. N. Vishwanathan

ICML Conference 2006 Conference Paper

Accelerated training of conditional random fields with stochastic gradient methods

• S. V. N. Vishwanathan
• Nicol N. Schraudolph
• Mark Schmidt 0001
• Kevin Murphy 0002

We apply Stochastic Meta-Descent (SMD), a stochastic gradient optimization method with gain vector adaptation, to the training of Conditional Random Fields (CRFs). On several large data sets, the resulting optimizer converges to the same quality of solution over an order of magnitude faster than limited-memory BFGS, the leading method reported to date. We report results for both exact and inexact inference techniques.

ICML Conference 2006 Conference Paper

Fast and space efficient string kernels using suffix arrays

• Choon Hui Teo
• S. V. N. Vishwanathan

NeurIPS Conference 2006 Conference Paper

Fast Computation of Graph Kernels

• Karsten Borgwardt
• Nicol Schraudolph
• S. V. N. Vishwanathan

Using extensions of linear algebra concepts to Reproducing Kernel Hilbert Spaces (RKHS), we define a unifying framework for random walk kernels on graphs. Re- duction to a Sylvester equation allows us to compute many of these kernels in O(n3) worst-case time. This includes kernels whose previous worst-case time complexity was O(n6), such as the geometric kernels of G¨artner et al. [1] and the marginal graph kernels of Kashima et al. [2]. Our algebra in RKHS allow us to exploit sparsity in directed and undirected graphs more effectively than previ- ous methods, yielding sub-cubic computational complexity when combined with conjugate gradient solvers or fixed-point iterations. Experiments on graphs from bioinformatics and other application domains show that our algorithms are often more than 1000 times faster than existing approaches.

NeurIPS Conference 2006 Conference Paper

Fast Iterative Kernel PCA

• Nicol Schraudolph
• Simon Günter
• S. V. N. Vishwanathan

We introduce two methods to improve convergence of the Kernel Hebbian Algorithm (KHA) for iterative kernel PCA. KHA has a scalar gain parameter which is either held constant or decreased as 1/t, leading to slow convergence. Our KHA/et algorithm accelerates KHA by incorporating the reciprocal of the current estimated eigenvalues as a gain vector. We then derive and apply Stochastic MetaDescent (SMD) to KHA/et; this further speeds convergence by performing gain adaptation in RKHS. Experimental results for kernel PCA and spectral clustering of USPS digits as well as motion capture and image de-noising problems confirm that our methods converge substantially faster than conventional KHA.

NeurIPS Conference 2006 Conference Paper

implicit Online Learning with Kernels

• Li Cheng
• Dale Schuurmans
• Shaojun Wang
• Terry Caelli
• S. V. N. Vishwanathan

We present two new algorithms for online learning in reproducing kernel Hilbert spaces. Our first algorithm, ILK (implicit online learning with kernels), employs a new, implicit update technique that can be applied to a wide variety of convex loss functions. We then introduce a bounded memory version, SILK (sparse ILK), that maintains a compact representation of the predictor without compromising solution quality, even in non-stationary environments. We prove loss bounds and analyze the convergence rate of both. Experimental evidence shows that our proposed algorithms outperform current methods on synthetic and real data.

JMLR Journal 2006 Journal Article

Step Size Adaptation in Reproducing Kernel Hilbert Space

• S. V. N. Vishwanathan
• Nicol N. Schraudolph
• Alex J. Smola

This paper presents an online support vector machine (SVM) that uses the stochastic meta-descent (SMD) algorithm to adapt its step size automatically. We formulate the online learning problem as a stochastic gradient descent in reproducing kernel Hilbert space (RKHS) and translate SMD to the nonparametric setting, where its gradient trace parameter is no longer a coefficient vector but an element of the RKHS. We derive efficient updates that allow us to perform the step size adaptation in linear time. We apply the online SVM framework to a variety of loss functions, and in particular show how to handle structured output spaces and achieve efficient online multiclass classification. Experiments show that our algorithm outperforms more primitive methods for setting the gradient step size. [abs] [ pdf ][ bib ] &copy JMLR 2006. ( edit, beta )

NeurIPS Conference 2004 Conference Paper

Binet-Cauchy Kernels

• Alex Smola
• S. V. N. Vishwanathan

We propose a family of kernels based on the Binet-Cauchy theorem and its ex- tension to Fredholm operators. This includes as special cases all currently known kernels derived from the behavioral framework, diffusion processes, marginalized kernels, kernels on graphs, and the kernels on sets arising from the subspace angle approach. Many of these kernels can be seen as the extrema of a new continuum of kernel functions, which leads to numerous new special cases. As an application, we apply the new class of kernels to the problem of clustering of video sequences with encouraging results.

NeurIPS Conference 2003 Conference Paper

Laplace Propagation

• Eleazar Eskin
• Alex Smola
• S. V. N. Vishwanathan

We present a novel method for approximate inference in Bayesian mod- els and regularized risk functionals. It is based on the propagation of mean and variance derived from the Laplace approximation of condi- tional probabilities in factorizing distributions, much akin to Minka’s Expectation Propagation. In the jointly normal case, it coincides with the latter and belief propagation, whereas in the general case, it provides an optimization strategy containing Support Vector chunking, the Bayes Committee Machine, and Gaussian Process chunking as special cases.

ICML Conference 2003 Conference Paper

SimpleSVM

• S. V. N. Vishwanathan
• Alexander J. Smola
• M. Narasimha Murty

NeurIPS Conference 2002 Conference Paper

Fast Kernels for String and Tree Matching

• Alex Smola
• S. V. N. Vishwanathan

In this paper we present a new algorithm suitable for matching discrete objects such as strings and trees in linear time, thus obviating dynarrtic programming with quadratic time complexity. Furthermore, prediction cost in many cases can be reduced to linear cost in the length of the se(cid: 173) quence to be classified, regardless of the number of support vectors. This improvement on the currently available algorithms makes string kernels a viable alternative for the practitioner.