pwc-archive/papers-with-abstracts huggingface dataset:
Accelerated Gradient Methods for Stochastic Optimization and Online Learning
Authors: Chonghai Hu, Weike Pan, James T. Kwok
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Stochastic Optimization

Regularized risk minimization often involves non-smooth optimization, either because of the loss function (e.g., hinge loss) or the regularizer (e.g., $\ell_1$-regularizer). Gradient descent methods, though highly scalable and easy to implement, are known to converge slowly on these problems. In this paper, we develop novel accelerated gradient methods for stochastic optimization while still preserving their computational simplicity and scalability. The proposed algorithm, called SAGE (Stochastic Accelerated GradiEnt), exhibits fast convergence rates on stochastic optimization with both convex and strongly convex objectives. Experimental results show that SAGE is faster than recent (sub)gradient methods including FOLOS, SMIDAS and SCD. Moreover, SAGE can also be extended for online learning, resulting in a simple but powerful algorithm.
Reconstruction of Sparse Circuits Using Multi-neuronal Excitation (RESCUME)
Authors: Tao Hu, Anthony Leonardo, Dmitri B. Chklovskii
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Compressive Sensing

One of the central problems in neuroscience is reconstructing synaptic connectivity in neural circuits. Synapses onto a neuron can be probed by sequentially stimulating potentially pre-synaptic neurons while monitoring the membrane voltage of the post-synaptic neuron. Reconstructing a large neural circuit using such a “brute force” approach is rather time-consuming and inefficient because the connectivity in neural circuits is sparse. Instead, we propose to measure a post-synaptic neuron’s voltage while stimulating simultaneously multiple randomly chosen potentially pre-synaptic neurons. To extract the weights of individual synaptic connections we apply a decoding algorithm recently developed for compressive sensing. Compared to the brute force approach, our method promises significant time savings that grow with the size of the circuit. We use computer simulations to find optimal stimulation parameters and explore the feasibility of our reconstruction method under realistic experimental conditions including noise and non-linear synaptic integration. Multiple-neuron stimulation allows reconstructing synaptic connectivity just from the spiking activity of post-synaptic neurons, even when sub-threshold voltage is unavailable. By using calcium indicators, voltage-sensitive dyes, or multi-electrode arrays one could monitor activity of multiple post-synaptic neurons simultaneously, thus mapping their synaptic inputs in parallel, potentially reconstructing a complete neural circuit.
Riffled Independence for Ranked Data
Authors: Jonathan Huang, Carlos Guestrin
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Card Games

Representing distributions over permutations can be a daunting task due to the fact that the number of permutations of n objects scales factorially in n. One recent way that has been used to reduce storage complexity has been to exploit probabilistic independence, but as we argue, full independence assumptions impose strong sparsity constraints on distributions and are unsuitable for modeling rankings. We identify a novel class of independence structures, called riffled independence, which encompasses a more expressive family of distributions while retaining many of the properties necessary for performing efficient inference and reducing sample complexity. In riffled independence, one draws two permutations independently, then performs the riffle shuffle, common in card games, to combine the two permutations to form a single permutation. In ranking, riffled independence corresponds to ranking disjoint sets of objects independently, then interleaving those rankings. We provide a formal introduction and present algorithms for using riffled independence within Fourier-theoretic frameworks which have been explored by a number of recent papers.
Learning Brain Connectivity of Alzheimer's Disease from Neuroimaging Data
Authors: Shuai Huang, Jing Li, Liang Sun, Jun Liu, Teresa Wu, Kewei Chen, Adam Fleisher, Eric Reiman, Jieping Ye
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Functional Connectivity

Recent advances in neuroimaging techniques provide great potentials for effective diagnosis of Alzheimer’s disease (AD), the most common form of dementia. Previous studies have shown that AD is closely related to alternation in the functional brain network, i.e., the functional connectivity among different brain regions. In this paper, we consider the problem of learning functional brain connectivity from neuroimaging, which holds great promise for identifying image-based markers used to distinguish Normal Controls (NC), patients with Mild Cognitive Impairment (MCI), and patients with AD.  More specifically, we study sparse inverse covariance estimation (SICE), also known as exploratory Gaussian graphical models, for brain connectivity modeling. In particular, we apply SICE to learn and analyze functional brain connectivity patterns from different subject groups, based on a key property of SICE, called the “monotone property” we established in this paper. Our experimental results on neuroimaging PET data of 42 AD, 116 MCI, and 67 NC subjects reveal several interesting connectivity patterns consistent with literature findings, and also some new patterns that can help the knowledge discovery of AD.
Discrete MDL Predicts in Total Variation
Authors: Marcus Hutter
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Time Series, Time Series Analysis, Time Series Forecasting

The Minimum Description Length (MDL) principle selects the model that has the shortest code for data plus model. We show that for a countable class of models, MDL predictions are close to the true distribution in a strong sense. The result is completely general. No independence, ergodicity, stationarity, identifiability, or other assumption on the model class need to be made. More formally, we show that for any countable class of models, the distributions selected by MDL (or MAP) asymptotically predict (merge with) the true measure in the class in total variation distance. Implications for non-i.i.d. domains like time-series forecasting, discriminative learning, and reinforcement learning are discussed.
Particle-based Variational Inference for Continuous Systems
Authors: Andrew Frank, Padhraic Smyth, Alexander T. Ihler
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Variational Inference

Since the development of loopy belief propagation, there has been considerable work on advancing the state of the art for approximate inference over distributions defined on discrete random variables. Improvements include guarantees of convergence, approximations that are provably more accurate, and bounds on the results of exact inference.  However, extending these methods  to continuous-valued systems has lagged behind.  While several methods have been developed to use belief propagation on systems with continuous values, they have not as yet incorporated the recent advances for discrete variables. In this context we extend a recently proposed particle-based belief propagation algorithm to provide a general framework for adapting discrete message-passing algorithms to perform inference in continuous systems.  The resulting algorithms behave similarly to their purely discrete counterparts, extending the benefits of these more advanced inference techniques to the continuous domain.
Modeling Social Annotation Data with Content Relevance using a Topic Model
Authors: Tomoharu Iwata, Takeshi Yamada, Naonori Ueda
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: General Classification, Information Retrieval, Retrieval, text-classification, Text Classification

We propose a probabilistic topic model for analyzing and extracting content-related annotations from noisy annotated discrete data such as web pages stored in social bookmarking services. In these services, since users can attach annotations freely, some annotations do not describe the semantics of the content, thus they are noisy,  i.e.  not content-related. The extraction of content-related annotations can be used as a preprocessing step in machine learning tasks such as text classification and image recognition, or can improve information retrieval performance. The proposed model is a generative model for content and annotations, in which the annotations are assumed to originate either from topics that generated the content or from a general distribution unrelated to the content. We demonstrate the effectiveness of the proposed method by using synthetic data and real social annotation data for text and images.
On the Algorithmics and Applications of a Mixed-norm based Kernel Learning Formulation
Authors: Saketha N. Jagarlapudi, Dinesh G, Raman S, Chiranjib Bhattacharyya, Aharon Ben-Tal, Ramakrishnan K.R.
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Object Categorization

Motivated from real world problems, like object categorization, we study a particular mixed-norm regularization for Multiple Kernel Learning (MKL). It is assumed that the given set of kernels are grouped into distinct components where each component is crucial for the learning task at hand. The formulation hence employs $l_\infty$ regularization for promoting combinations at the component level and $l_1$ regularization for promoting sparsity among kernels in each component. While previous attempts have formulated this as a non-convex problem, the formulation given here is an instance of non-smooth convex optimization problem which admits an efficient Mirror-Descent (MD) based procedure. The MD procedure optimizes over product of simplexes, which is not a well-studied case in literature. Results on real-world datasets show that the new MKL formulation is well-suited for object categorization tasks and that the MD based algorithm outperforms state-of-the-art MKL solvers like \texttt{simpleMKL} in terms of computational effort.
Bayesian Belief Polarization
Authors: Alan Jern, Kai-Min Chang, Charles Kemp
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Situations in which people with opposing prior beliefs observe the same evidence and then strengthen those existing beliefs are frequently offered as evidence of human irrationality. This phenomenon, termed belief polarization, is typically assumed to be non-normative. We demonstrate, however, that a variety of cases of belief polarization are consistent with a Bayesian approach to belief revision. Simulation results indicate that belief polarization is not only possible but relatively common within the class of Bayesian models that we consider.
Regularized Distance Metric Learning:Theory and Algorithm
Authors: Rong Jin, Shijun Wang, Yang Zhou
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Face Recognition, General Classification, Metric Learning

In this paper, we examine the generalization error of regularized distance metric learning. We show that with appropriate constraints, the generalization error of regularized distance metric learning could be independent from the dimensionality, making it suitable for handling high dimensional data. In addition, we present an efficient online learning algorithm for regularized distance metric learning. Our empirical studies with data classification and face recognition show that the proposed algorithm is (i) effective for distance metric learning when compared to the state-of-the-art methods, and (ii) efficient and robust for high dimensional data.
Local Rules for Global MAP: When Do They Work ?
Authors: Kyomin Jung, Pushmeet Kohli, Devavrat Shah
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We consider the question of computing Maximum A Posteriori (MAP) assignment in an arbitrary pair-wise Markov Random Field (MRF). We present a randomized iterative algorithm based on simple local updates. The algorithm, starting with an arbitrary initial assignment, updates it in each iteration by first, picking a random node, then selecting an (appropriately chosen) random local neighborhood and optimizing over this local neighborhood. Somewhat surprisingly, we show that this algorithm finds a near optimal assignment within $2n\ln n$ iterations on average and with high probability for {\em any} $n$ node pair-wise MRF with {\em geometry} (i.e. MRF graph with polynomial growth) with the approximation error depending on (in a reasonable manner) the geometric growth rate of the graph and the average radius of the local neighborhood -- this allows for a graceful tradeoff between the complexity of the algorithm and the approximation error. Through extensive simulations, we show that our algorithm finds extremely good approximate solutions for various kinds of MRFs with geometry.
Potential-Based Agnostic Boosting
Authors: Varun Kanade, Adam Kalai
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Learning Theory

We prove strong noise-tolerance properties of a potential-based boosting algorithm, similar to MadaBoost (Domingo and Watanabe, 2000) and SmoothBoost (Servedio, 2003). Our analysis is in the agnostic framework of Kearns, Schapire and Sellie (1994), giving polynomial-time guarantees in presence of arbitrary noise. A remarkable feature of our algorithm is that it can be implemented without reweighting examples, by randomly relabeling them instead. Our boosting theorem gives, as easy corollaries, alternative derivations of two recent non-trivial results in computational learning theory: agnostically learning decision trees (Gopalan et al, 2008) and agnostically learning halfspaces (Kalai et al, 2005). Experiments suggest that the algorithm performs similarly to Madaboost.
Directed Regression
Authors: Yi-Hao Kao, Benjamin V. Roy, Xiang Yan
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: regression

When used to guide decisions, linear regression analysis typically involves estimation of regression coefficients via ordinary least squares and their subsequent use to make decisions. When there are multiple response variables and features do not perfectly capture their relationships, it is beneficial to account for the decision objective when computing regression coefficients. Empirical optimization does so but sacrifices performance when features are well-chosen or training data are insufficient. We propose directed regression, an efficient algorithm that combines merits of ordinary least squares and empirical optimization. We demonstrate through a computational study that directed regression can generate significant performance gains over either alternative. We also develop a theory that motivates the algorithm.
Breaking Boundaries Between Induction Time and Diagnosis Time Active Information Acquisition
Authors: Ashish Kapoor, Eric Horvitz
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Active Learning, Diagnostic, General Classification

There has been a clear distinction between induction or training time and diagnosis time active information acquisition. While active learning during induction focuses on acquiring data that promises to provide the best classification model, the goal at diagnosis time focuses completely on next features to observe about the test case at hand in order to make better predictions about the case. We introduce a model and inferential methods that breaks this distinction. The methods can be used to extend case libraries under a budget but, more fundamentally, provide a framework for guiding agents to collect data under scarce resources, focused by diagnostic challenges. This extension to active learning leads to a new class of policies for real-time diagnosis, where recommended information-gathering sequences include actions that simultaneously seek new data for the case at hand and for cases in the training set.
Multiple Incremental Decremental Learning of Support Vector Machines
Authors: Masayuki Karasuyama, Ichiro Takeuchi
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

We propose a multiple incremental decremental algorithm  of Support Vector Machine (SVM). Conventional single  cremental decremental SVM can update the trained model  efficiently when single data point is added to or removed  from the training set. When we add and/or remove multiple  data points, this algorithm is time-consuming because we  need to repeatedly apply it to each data point. The roposed  algorithm is computationally more efficient when multiple  data points are added and/or removed simultaneously. The  single incremental decremental algorithm is built on an  optimization technique called parametric programming.  We extend the idea and introduce multi-parametric  programming for developing the proposed algorithm.  Experimental results on synthetic and real data sets indicate that the proposed algorithm can significantly  reduce the computational cost of multiple incremental  decremental operation. Our approach is especially useful  for online SVM learning in which we need to remove old  data points and add new data points in a short amount of  time.
Submodularity Cuts and Applications
Authors: Yoshinobu Kawahara, Kiyohito Nagano, Koji Tsuda, Jeff A. Bilmes
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Active Learning, feature selection

Several key problems in machine learning, such as feature selection and active learning, can be formulated as submodular set function maximization.  We present herein a novel algorithm for maximizing a submodular set function under a cardinality constraint --- the algorithm is based on a cutting-plane method and is implemented as an iterative small-scale binary-integer linear programming procedure. It is well known that this problem is NP-hard, and the approximation factor achieved by the greedy algorithm is the theoretical limit for polynomial time. As for (non-polynomial time) exact algorithms that perform reasonably in practice, there has been very little in the literature although the problem is quite important for many applications. Our algorithm is guaranteed to find the exact solution in finite iterations, and it converges fast in practice due to the efficiency of the cutting-plane mechanism. Moreover, we also provide a method that produces successively decreasing upper-bounds of the optimal solution, while our algorithm provides successively increasing lower-bounds.  Thus, the accuracy of the current solution can be estimated at any point, and the algorithm can be stopped early once a desired degree of tolerance is met.  We evaluate our algorithm on sensor placement and feature selection applications showing good performance.
Individuation, Identification and Object Discovery
Authors: Charles Kemp, Alan Jern, Fei Xu
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Object, Object Discovery

Humans are typically able to infer how many objects their environment contains and to recognize when the same object is encountered twice.  We present a simple statistical model that helps to explain these abilities and evaluate it in three behavioral experiments.  Our first experiment suggests that humans rely on prior knowledge when deciding whether an object token has been previously encountered. Our second and third experiments suggest that humans can infer how many objects they have seen and can learn about categories and their properties even when they are uncertain about which tokens are instances of the same object.
Abstraction and Relational learning
Authors: Charles Kemp, Alan Jern
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Relational Reasoning

Many categories are better described by providing relational information than listing characteristic features.  We present a hierarchical generative model that helps to explain how relational categories are learned and used. Our model learns abstract schemata that specify the relational similarities shared by members of a category, and our emphasis on abstraction departs from previous theoretical proposals that focus instead on comparison of concrete instances. Our first experiment suggests that our abstraction-based account can address some of the tasks that have previously been used to support comparison-based approaches. Our second experiment focuses on one-shot schema learning, a problem that raises challenges for comparison-based approaches but is handled naturally by our abstraction-based account.
Quantification and the language of thought
Authors: Charles Kemp
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

Many researchers have suggested that the psychological complexity of a concept is related to the length of its representation in a language of thought.  As yet, however, there are few concrete proposals about the nature of this language. This paper makes one such proposal: the language of thought allows first order quantification (quantification over objects) more readily than second-order quantification (quantification over features). To support this proposal we present behavioral results from a concept learning study inspired by the work of Shepard, Hovland and Jenkins."
Unsupervised Detection of Regions of Interest Using Iterative Link Analysis
Authors: Gunhee Kim, Antonio Torralba
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12

This paper proposes a fast and scalable alternating optimization technique to detect regions of interest (ROIs) in cluttered Web images without labels. The proposed approach discovers highly probable regions of  object instances by iteratively repeating the following two functions: (1) choose the exemplar set (i.e. small number of high ranked reference ROIs) across the dataset and (2) refine the ROIs of each image with respect to the exemplar set. These two subproblems are formulated as ranking in two different similarity networks of ROI hypotheses by link analysis. The experiments with the PASCAL 06 dataset show that our unsupervised localization performance is better than one of state-of-the-art techniques and comparable to supervised methods. Also, we test the scalability of our approach with five objects in Flickr dataset consisting of more than 200,000 images.
Clustering sequence sets for motif discovery
Authors: Jong K. Kim, Seungjin Choi
Date: 2009-12-01 00:00:00
Proceeding: NeurIPS 2009 12
Tasks: Clustering

Most of existing methods for DNA motif discovery consider only a single set of sequences to find an over-represented motif. In contrast, we consider multiple sets of sequences where we group sets associated with the same motif into a cluster, assuming that each set involves a single motif. Clustering sets of sequences yields clusters of coherent motifs, improving signal-to-noise ratio or enabling us to identify multiple motifs. We present a probabilistic model for DNA motif discovery where we identify multiple motifs through searching for patterns which are shared across multiple sets of sequences. Our model infers cluster-indicating latent variables and learns motifs simultaneously, where these two tasks interact with each other. We show that our model can handle various motif discovery problems, depending on how to construct multiple sets of sequences. Experiments on three different problems for discovering DNA motifs emphasize the useful behavior and confirm the substantial gains over existing methods where only single set of sequences is considered.