mtybilly/Instruct2DS huggingface dataset:
Feature Selection Methods for Improving Protein Structure Prediction with Rosetta
Authors: David Baker, Michael I. Jordan, Philip Bradley, Rhiju Das, David E Kim Ben Blum
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Rosetta is one of the leading algorithms for protein structure prediction today. It is a Monte Carlo energy minimization method requiring many random restarts to ﬁnd structures with low energy. In this paper we present a resampling technique for structure prediction of small alpha/beta proteins using Rosetta. From an ini- tial round of Rosetta sampling, we learn properties of the energy landscape that guide a subsequent round of sampling toward lower-energy structures. Rather than attempt to ﬁt the full energy landscape, we use feature selection methods—both L1-regularized linear regression and decision trees—to identify structural features that give rise to low energy. We then enrich these structural features in the second sampling round. Results are presented across a benchmark set of nine small al- pha/beta proteins demonstrating that our methods seldom impair, and frequently improve, Rosetta’s performance.
Selecting Observations against Adversarial Objectives
Authors: Brendan Mcmahan, Carlos Guestrin, Anupam Gupta Andreas Krause
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: In many applications, one has to actively select among a set of expensive observa- tions before making an informed decision. Often, we want to select observations which perform well when evaluated with an objective function chosen by an adver- sary. Examples include minimizing the maximum posterior variance in Gaussian Process regression, robust experimental design, and sensor placement for outbreak detection. In this paper, we present the Submodular Saturation algorithm, a sim- ple and efﬁcient algorithm with strong theoretical approximation guarantees for the case where the possible objective functions exhibit submodularity, an intuitive diminishing returns property. Moreover, we prove that better approximation al- gorithms do not exist unless NP-complete problems admit efﬁcient algorithms. We evaluate our algorithm on several real-world problems. For Gaussian Process regression, our algorithm compares favorably with state-of-the-art heuristics de- scribed in the geostatistics literature, while being simpler, faster and providing theoretical guarantees. For robust experimental design, our algorithm performs favorably compared to SDP-based algorithms.
Spatial Latent Dirichlet Allocation
Authors: Eric Grimson Xiaogang Wang
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: In recent years, the language model Latent Dirichlet Allocation (LDA), which clusters co-occurring words into topics, has been widely appled in the computer vision field. However, many of these applications have difficulty with modeling the spatial and temporal structure among visual words, since LDA assumes that a document is a bag-of-words''. It is also critical to properly designwords'' and “documents” when using a language model to solve vision problems. In this paper, we propose a topic model Spatial Latent Dirichlet Allocation (SLDA), which better encodes spatial structure among visual words that are essential for solving many vision problems. The spatial information is not encoded in the value of visual words but in the design of documents. Instead of knowing the partition of words into documents \textit{a priori}, the word-document assignment becomes a random hidden variable in SLDA. There is a generative procedure, where knowledge of spatial structure can be flexibly added as a prior, grouping visual words which are close in space into the same document. We use SLDA to discover objects from a collection of images, and show it achieves better performance than LDA.
Learning Visual Attributes
Authors: Andrew Zisserman Vittorio Ferrari
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We present a probabilistic generative model of visual attributes, together with an efﬁcient learning algorithm. Attributes are visual qualities of objects, such as ‘red’, ‘striped’, or ‘spotted’. The model sees attributes as patterns of image segments, repeatedly sharing some characteristic properties. These can be any combination of appearance, shape, or the layout of segments within the pattern. Moreover, attributes with general appearance are taken into account, such as the pattern of alternation of any two colors which is characteristic for stripes. To enable learning from unsegmented training images, the model is learnt discriminatively, by optimizing a likelihood ratio. As demonstrated in the experimental evaluation, our model can learn in a weakly supervised setting and encompasses a broad range of attributes. We show that attributes can be learnt starting from a text query to Google image search, and can then be used to recognize the attribute and determine its spatial extent in novel real-world images.
Collapsed Variational Inference for HDP
Authors: Kenichi Kurihara, Max Welling Yee W. Teh
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: A wide variety of Dirichlet-multinomial ‘topic’ models have found interesting ap- plications in recent years. While Gibbs sampling remains an important method of inference in such models, variational techniques have certain advantages such as easy assessment of convergence, easy optimization without the need to maintain detailed balance, a bound on the marginal likelihood, and side-stepping of issues with topic-identiﬁability. The most accurate variational technique thus far, namely collapsed variational latent Dirichlet allocation, did not deal with model selection nor did it include inference for hyperparameters. We address both issues by gen- eralizing the technique, obtaining the ﬁrst variational algorithm to deal with the hierarchical Dirichlet process and to deal with hyperparameters of Dirichlet vari- ables. Experiments show a signiﬁcant improvement in accuracy.
Progressive mixture rules are deviation suboptimal
Authors: Jean-yves Audibert
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We consider the learning task consisting in predicting as well as the best function in a finite reference set G up to the smallest possible additive term. If R(g) denotes the generalization error of a prediction function g, under reasonable assumptions on the loss function (typically satisfied by the least square loss when the output is bounded), it is known that the progressive mixture rule gn satisfies E R(gn) < min_{g in G} R(g) + Cst (log|G|)/n where n denotes the size of the training set, E denotes the expectation wrt the training set distribution. This work shows that, surprisingly, for appropriate reference sets G, the deviation convergence rate of the progressive mixture rule is only no better than Cst / sqrt{n}, and not the expected Cst / n. It also provides an algorithm which does not suffer from this drawback.
Experience-Guided Search: A Theory of Attentional Control
Authors: Michael Mozer David Baldwin
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: People perform a remarkable range of tasks that require search of the visual en- vironment for a target item among distractors. The Guided Search model (Wolfe, 1994, 2007), or GS, is perhaps the best developed psychological account of hu- man visual search. To prioritize search, GS assigns saliency to locations in the visual ﬁeld. Saliency is a linear combination of activations from retinotopic maps representing primitive visual features. GS includes heuristics for setting the gain coefﬁcient associated with each map. Variants of GS have formalized the notion of optimization as a principle of attentional control (e.g., Baldwin & Mozer, 2006; Cave, 1999; Navalpakkam & Itti, 2006; Rao et al., 2002), but every GS-like model must be ’dumbed down’ to match human data, e.g., by corrupting the saliency map with noise and by imposing arbitrary restrictions on gain modulation. We propose a principled probabilistic formulation of GS, called Experience-Guided Search (EGS), based on a generative model of the environment that makes three claims: (1) Feature detectors produce Poisson spike trains whose rates are conditioned on feature type and whether the feature belongs to a target or distractor; (2) the en- vironment and/or task is nonstationary and can change over a sequence of trials; and (3) a prior speciﬁes that features are more likely to be present for target than for distractors. Through experience, EGS infers latent environment variables that determine the gains for guiding search. Control is thus cast as probabilistic infer- ence, not optimization. We show that EGS can replicate a range of human data from visual search, including data that GS does not address.
Hierarchical Penalization
Authors: Yves Grandvalet, Pierre Morizet-mahoudeaux Marie Szafranski
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Hierarchical penalization is a generic framework for incorporating prior informa- tion in the ﬁtting of statistical models, when the explicative variables are organized in a hierarchical structure. The penalizer is a convex functional that performs soft selection at the group level, and shrinks variables within each group. This favors solutions with few leading terms in the ﬁnal combination. The framework, orig- inally derived for taking prior knowledge into account, is shown to be useful in linear regression, when several parameters are used to model the inﬂuence of one feature, or in kernel regression, for learning multiple kernels. Keywords – Optimization: constrained and convex optimization. Supervised learning: regression, kernel methods, sparsity and feature selection.
Linear programming analysis of loopy belief propagation for weighted matching
Authors: Dmitry Malioutov, Alan S. Willsky Sujay Sanghavi
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Loopy belief propagation has been employed in a wide variety of applications with great empirical success, but it comes with few theoretical guarantees. In this paper we investigate the use of the max-product form of belief propagation for weighted matching problems on general graphs. We show that max-product converges to the correct answer if the linear programming (LP) relaxation of the weighted matching problem is tight and does not converge if the LP relaxation is loose. This provides an exact characterization of max-product performance and reveals connections to the widely used optimization technique of LP relaxation. In addition, we demonstrate that max-product is effective in solving practical weighted matching problems in a distributed fashion by applying it to the problem of self-organization in sensor networks.
Learning Horizontal Connections in a Sparse Coding Model of Natural Images
Authors: Bruno A. Olshausen Pierre Garrigues
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: It has been shown that adapting a dictionary of basis functions to the statistics of natural images so as to maximize sparsity in the coefficients results in a set of dictionary elements whose spatial properties resemble those of V1 (primary visual cortex) receptive fields. However, the resulting sparse coefficients still exhibit pronounced statistical dependencies, thus violating the independence assumption of the sparse coding model. Here, we propose a model that attempts to capture the dependencies among the basis function coefficients by including a pairwise coupling term in the prior over the coefficient activity states. When adapted to the statistics of natural images, the coupling terms learn a combination of facilitatory and inhibitory interactions among neighboring basis functions. These learned interactions may offer an explanation for the function of horizontal connections in V1, and we discuss the implications of our findings for physiological experiments.
COFI RANK - Maximum Margin Matrix Factorization for Collaborative Ranking
Authors: Alexandros Karatzoglou, Quoc V. Le, Alex J. Smola Markus Weimer
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: In this paper, we consider collaborative ﬁltering as a ranking problem. We present a method which uses Maximum Margin Matrix Factorization and optimizes rank- ing instead of rating. We employ structured output prediction to optimize directly for ranking scores. Experimental results show that our method gives very good ranking scores and scales well on collaborative ﬁltering tasks.
Infinite State Bayes-Nets for Structured Domains
Authors: Ian Porteous, Evgeniy Bart Max Welling
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: A general modeling framework is proposed that uniﬁes nonparametric-Bayesian models, topic-models and Bayesian networks. This class of inﬁnite state Bayes nets (ISBN) can be viewed as directed networks of ‘hierarchical Dirichlet processes’ (HDPs) where the domain of the variables can be structured (e.g. words in documents or features in images). We show that collapsed Gibbs sampling can be done efﬁciently in these models by leveraging the structure of the Bayes net and using the forward-ﬁltering-backward-sampling algorithm for junction trees. Existing models, such as nested-DP, Pachinko allocation, mixed membership sto- chastic block models as well as a number of new models are described as ISBNs. Two experiments have been performed to illustrate these ideas.
Regularized Boost for Semi-Supervised Learning
Authors: Shihai Wang Ke Chen
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Semi-supervised inductive learning concerns how to learn a decision rule from a data set containing both labeled and unlabeled data. Several boosting algorithms have been extended to semi-supervised learning with various strategies. To our knowledge, however, none of them takes local smoothness constraints among data into account during ensemble learning. In this paper, we introduce a local smoothness regularizer to semi-supervised boosting algorithms based on the universal optimization framework of margin cost functionals. Our regularizer is applicable to existing semi-supervised boosting algorithms to improve their generalization and speed up their training. Comparative results on synthetic, benchmark and real world tasks demonstrate the effectiveness of our local smoothness regularizer. We discuss relevant issues and relate our regularizer to previous work.
Consistent Minimization of Clustering Objective Functions
Authors: Stefanie Jegelka, Michael Kaufmann, Sébastien Bubeck Ulrike V. Luxburg
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Clustering is often formulated as a discrete optimization problem. The objective is to ﬁnd, among all partitions of the data set, the best one according to some quality measure. However, in the statistical setting where we assume that the ﬁnite data set has been sampled from some underlying space, the goal is not to ﬁnd the best partition of the given sample, but to approximate the true partition of the under- lying space. We argue that the discrete optimization approach usually does not achieve this goal. As an alternative, we suggest the paradigm of “nearest neighbor clustering”. Instead of selecting the best out of all partitions of the sample, it only considers partitions in some restricted function class. Using tools from statistical learning theory we prove that nearest neighbor clustering is statistically consis- tent. Moreover, its worst case complexity is polynomial by construction, and it can be implemented with small average case complexity using branch and bound.
The rat as particle filter
Authors: Nathaniel D. Daw Aaron C. Courville
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Although theorists have interpreted classical conditioning as a laboratory model of Bayesian belief updating, a recent reanalysis showed that the key features that theoretical models capture about learning are artifacts of averaging over subjects. Rather than learning smoothly to asymptote (reﬂecting, according to Bayesian models, the gradual tradeoff from prior to posterior as data accumulate), subjects learn suddenly and their predictions ﬂuctuate perpetually. We suggest that abrupt and unstable learning can be modeled by assuming subjects are conducting in- ference using sequential Monte Carlo sampling with a small number of samples — one, in our simulations. Ensemble behavior resembles exact Bayesian models since, as in particle ﬁlters, it averages over many samples. Further, the model is capable of exhibiting sophisticated behaviors like retrospective revaluation at the ensemble level, even given minimally sophisticated individuals that do not track uncertainty in their beliefs over trials.
Non-parametric Modeling of Partially Ranked Data
Authors: Yi Mao Guy Lebanon
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Statistical models on full and partial rankings of n items are often of limited prac- tical use for large n due to computational consideration. We explore the use of non-parametric models for partially ranked data and derive ef(cid:2)cient procedures for their use for large n. The derivations are largely possible through combinatorial and algebraic manipulations based on the lattice of partial rankings. In particular, we demonstrate for the (cid:2)rst time a non-parametric coherent and consistent model capable of ef(cid:2)ciently aggregating partially ranked data of different types.
Multiple-Instance Pruning For Learning Efficient Cascade Detectors
Authors: Paul A. Viola Cha Zhang
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: Cascade detectors have been shown to operate extremely rapidly, with high accuracy, and have important applications such as face detection. Driven by this success, cascade earning has been an area of active research in recent years. Nevertheless, there are still challenging technical problems during the training process of cascade detectors. In particular, determining the optimal target detection rate for each stage of the cascade remains an unsolved issue. In this paper, we propose the multiple instance pruning (MIP) algorithm for soft cascades. This algorithm computes a set of thresholds which aggressively terminate computation with no reduction in detection rate or increase in false positive rate on the training dataset. The algorithm is based on two key insights: i) examples that are destined to be rejected by the complete classifier can be safely pruned early; ii) face detection is a multiple instance learning problem. The MIP process is fully automatic and requires no assumptions of probability distributions, statistical independence, or ad hoc intermediate rejection targets. Experimental results on the MIT+CMU dataset demonstrate significant performance advantages.
Emergence of Multiplication in a Biophysical Model of a Wide-Field Visual Neuron for Computing Object Approaches: Dynamics, Peaks, & Fits
Authors: Matthias S. Keil
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Many species show avoidance reactions in response to looming object approaches.  In locusts, the corresponding escape behavior correlates with the activity  of the lobula giant movement detector (LGMD) neuron.  During an object approach,  its firing rate was reported to gradually increase until a peak is reached,  and then it declines quickly.  The $\eta$-function predicts that the LGMD activity  is a product between an exponential function of angular size $\exp(-\Theta)$ and  angular velocity $\dot{\Theta}$, and that peak activity is reached before time-to-contact  (ttc).  The $\eta$-function has become the prevailing LGMD model because it  reproduces many experimental observations, and even experimental evidence for  the multiplicative operation was reported.  Several inconsistencies remain  unresolved, though.  Here we address these issues with a new model ($\psi$-model),  which explicitly connects $\Theta$ and $\dot{\Theta}$ to biophysical quantities.  The $\psi$-model avoids biophysical problems associated with implementing  $\exp(\cdot)$, implements the multiplicative operation of $\eta$ via divisive  inhibition, and explains why activity peaks could occur after ttc.  It consistently  predicts response features of the LGMD, and provides excellent fits to published  experimental data, with goodness of fit measures comparable to corresponding  fits with the $\eta$-function.
Action-Gap Phenomenon in Reinforcement Learning
Authors: Amir-massoud Farahmand
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Many practitioners of reinforcement learning problems have observed that oftentimes  the performance of the agent reaches very close to the optimal performance even though the estimated (action-)value function is still far from the optimal one.  The goal of this paper is to explain and formalize this phenomenon by introducing the concept of the action-gap regularity.  As a typical result, we prove that for an agent following the greedy policy (\hat{\pi}) with respect to an action-value function (\hat{Q}), the performance loss (E[V^(X) - V^{\hat{X}} (X)]) is upper bounded by (O(|| \hat{Q} - Q^||_\infty^{1+\zeta})), in which (\zeta >= 0) is the parameter quantifying the action-gap regularity.  For (\zeta > 0), our results indicate smaller performance loss compared to what previous analyses had suggested.  Finally, we show how this regularity affects the performance of the family of approximate value iteration algorithms.
Learning Higher-Order Graph Structure with Features by Structure Penalty
Authors: Grace Wahba, Xiaojin Zhu Shilin Ding
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In discrete undirected graphical models, the conditional independence of node labels Y is specified by the graph structure. We study the case where there is another input random vector X (e.g. observed features) such that the distribution P (Y | X) is determined by functions of X that characterize the (higher-order) interactions among the Y ’s. The main contribution of this paper is to learn the graph structure and the functions conditioned on X at the same time. We prove that discrete undirected graphical models with feature X are equivalent to mul- tivariate discrete models. The reparameterization of the potential functions in graphical models by conditional log odds ratios of the latter offers advantages in representation of the conditional independence structure. The functional spaces can be flexibly determined by kernels. Additionally, we impose a Structure Lasso (SLasso) penalty on groups of functions to learn the graph structure. These groups with overlaps are designed to enforce hierarchical function selection. In this way, we are able to shrink higher order interactions to obtain a sparse graph structure.
Efficient Methods for Overlapping Group Lasso
Authors: Jun Liu, Jieping Ye Lei Yuan
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: The group Lasso is an extension of the Lasso for feature selection on (predefined) non-overlapping groups of features. The non-overlapping group structure limits its applicability in practice. There have been several recent attempts to study a more general formulation, where groups of features are given, potentially with overlaps between the groups. The resulting optimization is, however, much more challenging to solve due to the group overlaps. In this paper, we consider the efficient optimization of the overlapping group Lasso penalized problem. We reveal several key properties of the proximal operator associated with the overlapping group Lasso, and compute the proximal operator by solving the smooth and convex dual problem, which allows the use of the gradient descent type of algorithms for the optimization. We have performed empirical evaluations using both synthetic and the breast cancer gene expression data set, which consists of 8,141 genes organized into (overlapping) gene sets. Experimental results show that the proposed algorithm is more efficient than existing state-of-the-art algorithms.
Priors over Recurrent Continuous Time Processes
Authors: Alexandre Bouchard-côté Ardavan Saeedi
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We introduce the Gamma-Exponential Process (GEP), a prior over a large family of continuous time stochastic processes. A hierarchical version of this prior (HGEP; the Hierarchical GEP) yields a useful model for analyzing complex time series. Models based on HGEPs display many attractive properties: conjugacy, exchangeability and closed-form predictive distribution for the waiting times, and exact Gibbs updates for the time scale parameters. After establishing these properties, we show how posterior inference can be carried efficiently using Particle MCMC methods [1]. This yields a MCMC algorithm that can resample entire sequences atomically while avoiding the complications of introducing slice and stick auxiliary variables of the beam sampler [2]. We applied our model to the problem of estimating the disease progression in multiple sclerosis [3], and to RNA evolutionary modeling [4]. In both domains, we found that our model outperformed the standard rate matrix estimation approach.
The Kernel Beta Process
Authors: Yingjian Wang, Lawrence Carin, David B. Dunson Lu Ren
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: A new Le ́vy process prior is proposed for an uncountable collection of covariate- dependent feature-learning measures; the model is called the kernel beta process (KBP). Available covariates are handled efficiently via the kernel construction, with covariates assumed observed with each data sample (“customer”), and latent covariates learned for each feature (“dish”). Each customer selects dishes from an infinite buffet, in a manner analogous to the beta process, with the added constraint that a customer first decides probabilistically whether to “consider” a dish, based on the distance in covariate space between the customer and dish. If a customer does consider a particular dish, that dish is then selected probabilistically as in the beta process. The beta process is recovered as a limiting case of the KBP. An efficient Gibbs sampler is developed for computations, and state-of-the-art results are presented for image processing and music analysis tasks.
Lower Bounds for Passive and Active Learning
Authors: Alexander Rakhlin Maxim Raginsky
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We develop unified information-theoretic machinery for deriving lower bounds for passive and active learning schemes. Our bounds involve the so-called Alexander's capacity function. The supremum of this function has been recently rediscovered by Hanneke in the context of active learning under the name of "disagreement coefficient." For passive learning, our lower bounds match the upper bounds of Gine and Koltchinskii up to constants and generalize analogous results of Massart and Nedelec. For active learning, we provide first known lower bounds based on the capacity function rather than the disagreement coefficient.
k-NN Regression Adapts to Local Intrinsic Dimension
Authors: Samory Kpotufe
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Many nonparametric regressors were recently shown to converge at rates that depend only on the intrinsic dimension of data.  These regressors thus escape the curse of dimension when high-dimensional data has low intrinsic dimension (e.g. a manifold).   We show that $k$-NN regression is also adaptive to intrinsic dimension. In particular our rates are local to a query $x$   and depend only on the way masses of balls centered at $x$ vary with radius.    Furthermore, we show a simple way to choose $k = k(x)$ locally at any $x$ so as to nearly achieve the minimax rate at $x$  in terms of the unknown intrinsic dimension in the vicinity of $x$. We also establish that the minimax rate does not depend   on a particular choice of metric space or distribution, but rather that this minimax rate holds for any metric space and doubling measure.
Variational Learning for Recurrent Spiking Networks
Authors: Daan Wierstra, Wulfram Gerstner Danilo J. Rezende
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We derive a plausible learning rule updating the synaptic efficacies   for feedforward, feedback and lateral connections between observed and latent neurons.    Operating in the context of a generative model for distributions of spike sequences,    the learning mechanism is derived from variational inference principles. The synaptic plasticity rules found   are interesting in that they are strongly reminiscent of experimentally found results on Spike Time    Dependent Plasticity, and in that they differ for excitatory and inhibitory neurons. A simulation   confirms the method's applicability to learning both stationary and temporal spike patterns.
Rapid Deformable Object Detection using Dual-Tree Branch-and-Bound
Authors: Iasonas Kokkinos
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: In this work we use Branch-and-Bound (BB) to efficiently detect objects with deformable part models.  Instead of evaluating the classifier score exhaustively over image locations and scales, we use BB to focus on promising image  locations.  The core problem is to compute bounds that accommodate part deformations; for this we adapt the Dual Trees data structure  to our problem.    We evaluate our approach using  Mixture-of-Deformable Part Models.  We obtain exactly the same results but are 10-20 times faster on average.  We also develop a multiple-object detection  variation of the system, where  hypotheses for 20 categories are inserted in a common   priority queue. For the problem of finding the strongest category in an image this results in up to a 100-fold speedup.
Probabilistic Modeling of Dependencies Among Visual Short-Term Memory Representations
Authors: Robert A. Jacobs Emin Orhan
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Extensive evidence suggests that items are not encoded independently in visual short-term memory (VSTM). However, previous research has not quantitatively considered how the encoding of an item influences the encoding of other items. Here, we model the dependencies among VSTM representations using a multivariate Gaussian distribution with a stimulus-dependent mean and covariance matrix. We report the results of an experiment designed to determine the specific form of the stimulus-dependence of the mean and the covariance matrix. We find that the magnitude of the covariance between the representations of two items is a monotonically decreasing function of the difference between the items' feature values, similar to a Gaussian process with a distance-dependent, stationary kernel function. We further show that this type of covariance function can be explained as a natural consequence of encoding multiple stimuli in a population of neurons with correlated responses.
Bayesian Bias Mitigation for Crowdsourcing
Authors: Michael I. Jordan Fabian L. Wauthier
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Biased labelers are a systemic problem in crowdsourcing, and a  comprehensive toolbox for handling their responses is still being  developed. A typical crowdsourcing application can be divided into  three steps: data collection, data curation, and learning. At present  these steps are often treated separately. We present Bayesian Bias  Mitigation for Crowdsourcing (BBMC), a Bayesian model to unify all  three. Most data curation methods account for the {\it effects} of  labeler bias by modeling all labels as coming from a single latent  truth. Our model captures the {\it sources} of bias by describing  labelers as influenced by shared random effects. This approach can  account for more complex bias patterns that arise in ambiguous or hard  labeling tasks and allows us to merge data curation and learning into  a single computation. Active learning integrates data collection with  learning, but is commonly considered infeasible with Gibbs sampling  inference. We propose a general approximation strategy for Markov  chains to efficiently quantify the effect of a perturbation on the  stationary distribution and specialize this approach to active  learning. Experiments show BBMC to outperform many common heuristics.
Phase transition in the family of p-resistances
Authors: Ulrike V. Luxburg Morteza Alamgir
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We study the family of p-resistances on graphs for p ≥ 1. This family generalizes the standard resistance distance. We prove that for any fixed graph, for p=1, the p-resistance coincides with the shortest path distance, for p=2 it coincides with the standard resistance distance, and for p → ∞ it converges to the inverse of the minimal s-t-cut in the graph. Secondly, we consider the special case of random geometric graphs (such as k-nearest neighbor graphs) when the number n of vertices in the graph tends to infinity. We prove that an interesting phase-transition takes place. There exist two critical thresholds p^* and p^* such that if p < p^, then the p-resistance depends on meaningful global properties of the graph, whereas if p > p^, it only depends on trivial local quantities and does not convey any useful information. We can explicitly compute the critical values: p^* = 1 + 1/(d-1) and p^ = 1 + 1/(d-2) where d is the dimension of the underlying space (we believe that the fact that there is a small gap between p^* and p^* is an artifact of our proofs. We also relate our findings to Laplacian regularization and suggest to use q-Laplacians as regularizers, where q satisfies 1/p^ + 1/q = 1.
On the Analysis of Multi-Channel Neural Spike Data
Authors: David E. Carlson, Lawrence Carin Bo Chen
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Nonparametric Bayesian methods are developed for analysis of multi-channel  spike-train data, with the feature learning and spike sorting performed jointly.  The feature learning and sorting are performed simultaneously across all channels.  Dictionary learning is implemented via the beta-Bernoulli process, with  spike sorting performed via the dynamic hierarchical Dirichlet process (dHDP),  with these two models coupled. The dHDP is augmented to eliminate refractoryperiod  violations, it allows the “appearance” and “disappearance” of neurons over  time, and it models smooth variation in the spike statistics.
Hashing Algorithms for Large-Scale Learning
Authors: Anshumali Shrivastava, Joshua L. Moore, Arnd C. König Ping Li
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Minwise hashing is a standard technique in the context of search for efficiently computing set similarities. The recent development of b-bit minwise hashing provides a  substantial improvement by storing only the lowest b bits of each hashed value. In this paper, we demonstrate that  b-bit minwise hashing can be naturally integrated with linear learning algorithms such as linear SVM and logistic regression, to solve large-scale and high-dimensional statistical learning tasks, especially when the data do not fit in memory.   We  compare $b$-bit minwise hashing with  the Count-Min (CM)  and  Vowpal Wabbit (VW) algorithms, which have essentially the same variances as random projections. Our theoretical and empirical comparisons illustrate that b-bit minwise hashing is significantly more accurate (at the same storage cost) than VW (and random projections) for binary data.
Active learning of neural response functions with Gaussian processes
Authors: Greg Horwitz, Jonathan W. Pillow Mijung Park
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: A sizable literature has focused on the problem of estimating a low-dimensional feature space capturing a neuron's stimulus sensitivity.  However, comparatively little work has addressed the problem of estimating the nonlinear function from feature space to a neuron's output spike rate. Here, we use a Gaussian process (GP) prior over the infinite-dimensional space of nonlinear functions to obtain Bayesian estimates of the "nonlinearity" in the linear-nonlinear-Poisson (LNP) encoding model. This offers flexibility, robustness, and computational tractability compared to traditional methods (e.g., parametric forms, histograms, cubic splines).  Most importantly, we develop a framework for optimal experimental design based on uncertainty sampling.  This involves adaptively selecting stimuli to characterize the nonlinearity with as little experimental data as possible, and relies on a method for rapidly updating hyperparameters using the Laplace approximation.  We apply these methods to data from color-tuned neurons in macaque V1.  We estimate nonlinearities in the 3D space of cone contrasts, which reveal that V1 combines cone inputs in a highly nonlinear manner. With simulated experiments, we show that optimal design substantially reduces the amount of data required to estimate this nonlinear combination rule.
Nonstandard Interpretations of Probabilistic Programs for Efficient Inference
Authors: Noah Goodman, Andreas Stuhlmueller, Jeffrey M. Siskind David Wingate
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Probabilistic programming languages allow modelers to specify a stochastic    process using syntax that resembles modern programming languages.  Because    the program is in machine-readable format, a variety of techniques from    compiler design and program analysis can be used to examine the structure of    the distribution represented by the probabilistic program.  We show how    nonstandard interpretations of probabilistic programs can be used to    craft efficient inference algorithms: information about the structure of a    distribution (such as gradients or dependencies) is generated as a monad-like side    computation while executing the program.  These interpretations can be easily    coded using special-purpose objects and operator overloading.  We implement    two examples of nonstandard interpretations in two different languages, and    use them as building blocks to construct inference algorithms: automatic    differentiation, which enables gradient based methods, and provenance    tracking, which enables efficient construction of global proposals.
The Impact of Unlabeled Patterns in Rademacher Complexity Theory for Kernel Classifiers
Authors: Davide Anguita, Alessandro Ghio, Sandro Ridella Luca Oneto
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We derive here new generalization bounds, based on Rademacher Complexity theory, for model selection and error estimation   of linear (kernel) classifiers, which exploit  the availability of unlabeled samples.   In particular, two results are obtained: the first one shows that, using the unlabeled samples, the  confidence term of the conventional bound can be reduced by a factor of three; the second one  shows that the unlabeled samples can be used to obtain much tighter bounds, by building localized versions  of the hypothesis class containing the optimal classifier.
Regularized Laplacian Estimation and Fast Eigenvector Approximation
Authors: Michael W. Mahoney Patrick O. Perry
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Recently, Mahoney and Orecchia demonstrated that popular diffusion-based procedures to compute a quick approximation to the first nontrivial eigenvector of a data graph Laplacian exactly solve certain regularized Semi-Definite Programs (SDPs). In this paper, we extend that result by providing a statistical interpretation of their approximation procedure. Our interpretation will be analogous to the manner in which l2-regularized or l1-regularized l2 regression (often called Ridge regression and Lasso regression, respectively) can be interpreted in terms of a Gaussian prior or a Laplace prior, respectively, on the coefficient vector of the regression problem. Our framework will imply that the solutions to the Mahoney-Orecchia regularized SDP can be interpreted as regularized estimates of the pseudoinverse of the graph Laplacian. Conversely, it will imply that the solution to this regularized estimation problem can be computed very quickly by running, e.g., the fast diffusion-based PageRank procedure for computing an approximation to the first nontrivial eigenvector of the graph Laplacian. Empirical results are also provided to illustrate the manner in which approximate eigenvector computation implicitly performs statistical regularization, relative to running the corresponding exact algorithm.
The Doubly Correlated Nonparametric Topic Model
Authors: Erik B. Sudderth Dae I. Kim
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Topic models are learned via a statistical model of variation within document collections, but designed to extract meaningful semantic structure.  Desirable traits include the ability to incorporate annotations or metadata associated with documents; the discovery of correlated patterns of topic usage; and the avoidance of parametric assumptions, such as manual specification of the number of topics.  We propose a doubly correlated nonparametric topic (DCNT) model, the first model to simultaneously capture all three of these properties.  The DCNT models metadata via a flexible, Gaussian regression on arbitrary input features; correlations via a scalable square-root covariance representation; and nonparametric selection from an unbounded series of potential topics via a stick-breaking construction.  We validate the semantic structure and predictive performance of the DCNT using a corpus of NIPS documents annotated by various metadata.
Generalized Lasso based Approximation of Sparse Coding for Visual Recognition
Authors: Shin'ichi Satoh Nobuyuki Morioka
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Sparse coding, a method of explaining sensory data with as few dictionary bases as possible, has attracted much attention in computer vision. For visual object category recognition, L1 regularized sparse coding is combined with spatial pyramid representation to obtain state-of-the-art performance. However, because of its iterative optimization, applying sparse coding onto every local feature descriptor extracted from an image database can become a major bottleneck. To overcome this computational challenge, this paper presents "Generalized Lasso based Approximation of Sparse coding" (GLAS). By representing the distribution of sparse coefficients with slice transform, we fit a piece-wise linear mapping function with generalized lasso. We also propose an efficient post-refinement procedure to perform mutual inhibition between bases which is essential for an overcomplete setting. The experiments show that GLAS obtains comparable performance to L1 regularized sparse coding, yet achieves significant speed up demonstrating its effectiveness for large-scale visual recognition problems.
SpaRCS: Recovering low-rank and sparse matrices from compressive measurements
Authors: Aswin C. Sankaranarayanan, Richard Baraniuk Andrew E. Waters
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: We consider the problem of recovering a matrix $\mathbf{M}$ that is the sum of a low-rank matrix $\mathbf{L}$ and a sparse matrix $\mathbf{S}$ from a small set of linear measurements of the form $\mathbf{y} = \mathcal{A}(\mathbf{M}) = \mathcal{A}({\bf L}+{\bf S})$.  This model subsumes three important classes of signal recovery problems:  compressive sensing, affine rank minimization, and robust principal component analysis.  We propose a natural optimization problem for signal recovery under this model and develop a new greedy algorithm called SpaRCS to solve it.  SpaRCS inherits a number of desirable properties from the state-of-the-art CoSaMP and ADMiRA algorithms, including exponential convergence and efficient implementation.  Simulation results with video compressive sensing, hyperspectral imaging, and robust matrix completion data sets demonstrate both the accuracy and efficacy of the algorithm.
Learning Patient-Specific Cancer Survival Distributions as a Sequence of Dependent Regressors
Authors: Russell Greiner, Hsiu-Chin Lin, Vickie Baracos Chun-Nam Yu
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: An accurate model of patient survival time can help in the treatment and care of cancer patients. The common practice of providing survival time estimates based only on population averages for the site and stage of cancer ignores many important individual differences among patients. In this paper, we propose a local regression method for learning patient-specific survival time distribution based on patient attributes such as blood tests and clinical assessments. When tested on a cohort of more than 2000 cancer patients, our method gives survival time predictions that are much more accurate than popular survival analysis models such as the Cox and Aalen regression models. Our results also show that using patient-specific attributes can reduce the prediction error on survival time by as much as 20% when compared to using cancer site and stage only.