mtybilly/Instruct2DS huggingface dataset:
A neural network implementing optimal state estimation based on dynamic spike train decoding
Authors: Omer Bobrowski, Ron Meir, Shy Shoham, Yonina Eldar
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: It is becoming increasingly evident that organisms acting in uncertain dynamical environments often employ exact or approximate Bayesian statistical calculations in order to continuously estimate the environmental state, integrate information from multiple sensory modalities, form predictions and choose actions. What is less clear is how these putative computations are implemented by cortical neural networks. An additional level of complexity is introduced because these networks observe the world through spike trains received from primary sensory afferents, rather than directly. A recent line of research has described mechanisms by which such computations can be implemented using a network of neurons whose activ- ity directly represents a probability distribution across the possible “world states”. Much of this work, however, uses various approximations, which severely re- strict the domain of applicability of these implementations. Here we make use of rigorous mathematical results from the theory of continuous time point process ﬁltering, and show how optimal real-time state estimation and prediction may be implemented in a general setting using linear neural networks. We demonstrate the applicability of the approach with several examples, and relate the required network properties to the statistical nature of the environment, thereby quantify- ing the compatibility of a given network with its environment.
Computational Equivalence of Fixed Points and No Regret Algorithms, and Convergence to Equilibria
Authors: Elad Hazan, Satyen Kale
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We study the relation between notions of game-theoretic equilibria which are based on stability under a set of deviations, and empirical equilibria which are reached by rational players. Rational players are modelled by players using no regret algorithms, which guarantee that their payoff in the long run is almost as much as the most they could hope to achieve by consistently deviating from the algorithm's suggested action. We show that for a given set of deviations over the strategy set of a player, it is possible to efficiently approximate fixed points of a given deviation if and only if there exist efficient no regret algorithms resistant to the deviations. Further, we show that if all players use a no regret algorithm, then the empirical distribution of their plays converges to an equilibrium.
Catching Change-points with Lasso
Authors: Céline Levy-leduc, Zaïd Harchaoui
Published in: Advances in Neural Information Processing Systems 20  (NIPS 2007) (Main Conference Track), 2007

Abstract: We propose a new approach for dealing with the estimation of the location of change-points in one-dimensional piecewise constant signals observed in white noise. Our approach consists in reframing this task in a variable selection context. We use a penalized least-squares criterion with a l1-type penalty for this purpose. We prove that, in an appropriate asymptotic framework, this method provides consistent estimators of the change-points. Then, we explain how to implement this method in practice by combining the LAR algorithm and a reduced version of the dynamic programming algorithm and we apply it to synthetic and real data.
Feature Selection Methods for Improving Protein Structure Prediction with Rosetta
Authors: Ben Blum, David Baker, Michael I. Jordan, Philip Bradley, Rhiju Das, David E Kim
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: Andreas Krause, Brendan Mcmahan, Carlos Guestrin, Anupam Gupta
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: Xiaogang Wang, Eric Grimson
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: Vittorio Ferrari, Andrew Zisserman
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: Yee W. Teh, Kenichi Kurihara, Max Welling
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.
Experience-Guided Search: A Theory of Attentional Control
Authors: David Baldwin, Michael Mozer
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: Marie Szafranski, Yves Grandvalet, Pierre Morizet-mahoudeaux
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: Sujay Sanghavi, Dmitry Malioutov, Alan S. Willsky
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: Pierre Garrigues, Bruno A. Olshausen
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: Markus Weimer, Alexandros Karatzoglou, Quoc V. Le, Alex J. Smola
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: Max Welling, Ian Porteous, Evgeniy Bart
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: Ke Chen, Shihai Wang
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: Ulrike V. Luxburg, Stefanie Jegelka, Michael Kaufmann, Sébastien Bubeck
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: Aaron C. Courville, Nathaniel D. Daw
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: Guy Lebanon, Yi Mao
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: Cha Zhang, Paul A. Viola
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.
Learning Higher-Order Graph Structure with Features by Structure Penalty
Authors: Shilin Ding, Grace Wahba, Xiaojin Zhu
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: Lei Yuan, Jun Liu, Jieping Ye
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: Ardavan Saeedi, Alexandre Bouchard-côté
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: Lu Ren, Yingjian Wang, Lawrence Carin, David B. Dunson
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: Maxim Raginsky, Alexander Rakhlin
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.
Variational Learning for Recurrent Spiking Networks
Authors: Danilo J. Rezende, Daan Wierstra, Wulfram Gerstner
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.
Probabilistic Modeling of Dependencies Among Visual Short-Term Memory Representations
Authors: Emin Orhan, Robert A. Jacobs
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: Fabian L. Wauthier, Michael I. Jordan
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: Morteza Alamgir, Ulrike V. Luxburg
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: Bo Chen, David E. Carlson, Lawrence Carin
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: Ping Li, Anshumali Shrivastava, Joshua L. Moore, Arnd C. König
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: Mijung Park, Greg Horwitz, Jonathan W. Pillow
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: David Wingate, Noah Goodman, Andreas Stuhlmueller, Jeffrey M. Siskind
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: Luca Oneto, Davide Anguita, Alessandro Ghio, Sandro Ridella
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: Patrick O. Perry, Michael W. Mahoney
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: Dae I. Kim, Erik B. Sudderth
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: Nobuyuki Morioka, Shin'ichi Satoh
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: Andrew E. Waters, Aswin C. Sankaranarayanan, Richard Baraniuk
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: Chun-Nam Yu, Russell Greiner, Hsiu-Chin Lin, Vickie Baracos
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.
Prediction strategies without loss
Authors: Michael Kapralov, Rina Panigrahy
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Consider a sequence of bits where we are trying to predict the next bit from the previous bits. Assume we are allowed to say `predict 0' or `predict 1', and our payoff is $+1$ if the prediction is correct and $-1$ otherwise. We will say that at each point in time the loss of an algorithm is the number of wrong predictions minus the number of right predictions so far.  In this paper we are interested in algorithms that have essentially zero (expected) loss over any string at any point in time and yet have small regret with respect to always predicting $0$ or always predicting $1$. For a sequence of length $T$ our algorithm has  regret $14\epsilon T $ and loss   $2\sqrt{T}e^{-\epsilon^2 T} $ in expectation for all strings. We show that the tradeoff between loss and regret is optimal up to constant factors.    Our techniques extend to the general setting of $N$ experts, where the related problem of trading off regret to the best expert for regret to the 'special' expert has been studied by Even-Dar et al. (COLT'07). We obtain essentially zero loss with respect to the special expert and optimal loss/regret tradeoff,  improving upon the results of Even-Dar et al (COLT'07) and settling the main question left open in their paper.     The strong loss bounds of the algorithm have some surprising consequences. First, we obtain a parameter free algorithm for the experts problem that has optimal regret bounds with respect to $k$-shifting optima, i.e. bounds with respect to the optimum that is allowed to change arms multiple times. Moreover, for {\em any window of size $n$} the regret of our algorithm to any expert never exceeds $O(\sqrt{n(\log N+\log T)})$, where $N$ is the number of experts and $T$ is the time horizon, while maintaining the essentially zero loss property.
Maximum Margin Multi-Instance Learning
Authors: Hua Wang, Heng Huang, Farhad Kamangar, Feiping Nie, Chris H. Ding
Published in: Advances in Neural Information Processing Systems 24  (NIPS 2011) (Main Conference Track), 2011

Abstract: Multi-instance learning (MIL) considers input as bags of instances, in which labels are assigned to the bags. MIL is useful in many real-world applications. For example, in image categorization semantic meanings (labels) of an image mostly arise from its regions (instances) instead of the entire image (bag). Existing MIL methods typically build their models using the Bag-to-Bag (B2B) distance, which are often computationally expensive and may not truly reflect the semantic similarities. To tackle this, in this paper we approach MIL problems from a new perspective using the Class-to-Bag (C2B) distance, which directly assesses the relationships between the classes and the bags. Taking into account the two major challenges in MIL, high heterogeneity on data and weak label association, we propose a novel Maximum Margin Multi-Instance Learning (M3 I) approach to parameterize the C2B distance by introducing the class specific distance metrics and the locally adaptive significance coefficients. We apply our new approach to the automatic image categorization tasks on three (one single-label and two multilabel) benchmark data sets. Extensive experiments have demonstrated promising results that validate the proposed method.