nips nips2004 nips2004-16 knowledge-graph by maker-knowledge-mining

16 nips-2004-Adaptive Discriminative Generative Model and Its Applications

Source: pdf

Author: Ruei-sung Lin, David A. Ross, Jongwoo Lim, Ming-Hsuan Yang

Abstract: This paper presents an adaptive discriminative generative model that generalizes the conventional Fisher Linear Discriminant algorithm and renders a proper probabilistic interpretation. Within the context of object tracking, we aim to ﬁnd a discriminative generative model that best separates the target from the background. We present a computationally efﬁcient algorithm to constantly update this discriminative model as time progresses. While most tracking algorithms operate on the premise that the object appearance or ambient lighting condition does not signiﬁcantly change as time progresses, our method adapts a discriminative generative model to reﬂect appearance variation of the target and background, thereby facilitating the tracking task in ever-changing environments. Numerous experiments show that our method is able to learn a discriminative generative model for tracking target objects undergoing large pose and lighting changes.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 com Abstract This paper presents an adaptive discriminative generative model that generalizes the conventional Fisher Linear Discriminant algorithm and renders a proper probabilistic interpretation. [sent-6, score-0.529]

2 Within the context of object tracking, we aim to ﬁnd a discriminative generative model that best separates the target from the background. [sent-7, score-0.702]

3 We present a computationally efﬁcient algorithm to constantly update this discriminative model as time progresses. [sent-8, score-0.352]

4 Numerous experiments show that our method is able to learn a discriminative generative model for tracking target objects undergoing large pose and lighting changes. [sent-10, score-0.999]

5 Object tracking can be formulated as a continuous state estimation problem where the unobservable states encode the locations or motion parameters of the target objects, and the task is to infer the unobservable states from the observed images over time. [sent-12, score-0.572]

6 , hypotheses) of the target in the next frame based on its prior and current knowledge. [sent-15, score-0.181]

7 Among these possible locations, the tracker then determines the most likely location of the target object based on the new observation. [sent-17, score-0.453]

8 Such a formulation indicates that the performance of a tracker is largely based on a good observation model for validating all hypotheses. [sent-21, score-0.198]

9 Indeed, learning a robust observation model has been the focus of most recent object tracking research within this framework, and is also the focus of this paper. [sent-22, score-0.589]

10 Most of the existing approaches utilize static observation models and construct them before a tracking task starts. [sent-23, score-0.377]

11 To account for all possible variation in a static observation model, it is imperative to collect a large set of training examples with the hope that it covers all possible variations of the object’s appearance. [sent-24, score-0.242]

12 However, it is well known that the appearance of an object varies signiﬁcantly under different illumination, viewing angle, and shape deformation. [sent-25, score-0.502]

13 An alternative approach is to develop an adaptive method that contains a number of trackers that track different features or parts of a target object [3]. [sent-27, score-0.467]

14 The tracking method then adaptively selects the trackers that are robust at current situation to predict object locations. [sent-29, score-0.544]

15 Although this approach improves the ﬂexibility and robustness of a tracking method, each tracker has a static observation model which has to be trained beforehand and consequently restricts its application domains severely. [sent-30, score-0.501]

16 , robotics applications, where the tracker is expected to track a previously unseen target once it is detected. [sent-33, score-0.265]

17 To the best of our knowledge, considerably less attention is paid to developing adaptive observation models to account for appearance variation of a target object (e. [sent-34, score-0.768]

18 , lighting conditions and viewing angles) as tracking task progresses. [sent-38, score-0.398]

19 Our approach is to learn a model for determining the probability of a predicted image location being generated from the class of the target or the background. [sent-39, score-0.242]

20 That is, we formulate a binary classiﬁcation problem and develop a discriminative model to distinguish observations from the target class and the background class. [sent-40, score-0.43]

21 While conventional discriminative classiﬁers simply predict the class of each test sample, a good model within the abovementioned tracking framework needs to select the most likely sample that belongs to target object class from a set of samples (or hypotheses). [sent-41, score-1.015]

22 In other words, an observation model needs a classiﬁer with proper probabilistic interpretation. [sent-42, score-0.188]

23 In this paper, we present an adaptive discriminative generative model and apply it to object tracking. [sent-43, score-0.621]

24 The proposed model aims to best separate the target and the background in the ever-changing environment. [sent-44, score-0.183]

25 , belonging to the target object class) and negative examples (i. [sent-47, score-0.391]

26 First, in the generative stage, we use a probabilistic principal component analysis to model the density of the positive examples. [sent-51, score-0.215]

27 The result of this state is a Gaussian, which assigns high probability to examples lying in the linear subspace which captures the most variance of the positive examples. [sent-52, score-0.164]

28 Second, in the discriminative stage, we use negative examples (speciﬁcally, negative examples that are assigned high probability by our generative model) to produce a new distribution which reduces the probability of the negative examples. [sent-53, score-0.465]

29 This is done by learning a linear projection that, when applied to the data and the generative model, increases the distance between the negative examples and the mean. [sent-54, score-0.255]

30 Our experimental results show that our algorithm can reliably track moving objects whose appearance changes under different poses, illumination, and self deformation. [sent-56, score-0.347]

31 2 Probabilistic Tracking Algorithm We formulate the object tracking problem as a state estimation problem in a way similar to [5] [9]. [sent-57, score-0.538]

32 Denote ot as an image region observed at time t and Ot = {o1 , . [sent-58, score-0.636]

33 , ot } is a set of image regions observed from the beginning to time t. [sent-61, score-0.636]

34 An object tracking problem is a process to infer state st from observation Ot , where state st contains a set of parameters referring to the tracked object’s 2-D position, orientation, and scale in image ot . [sent-62, score-1.925]

35 Assuming a Markovian state transition, this inference problem is formulated with a recursive equation: p(st |Ot ) = kp(ot |st ) p(st |st−1 )p(st−1 |Ot−1 )dst−1 (1) where k is a constant, and p(ot |st ) and p(st |st−1 ) correspond to the observation model and dynamic model, respectively. [sent-63, score-0.197]

36 In (1), p(st−1 |Ot−1 ) is the state estimation given all the prior observations up to time t − 1, and p(ot |st ) is the likelihood that observing image ot at state st . [sent-64, score-1.097]

37 For object tracking, an ideal distribution of p(st |Ot ) should peak at ot , i. [sent-66, score-0.816]

38 While the integral in (1) predicts the regions where object is likely to appear given all the prior observations, the observation model p(ot |st ) determines the most likely state that matches the observation at time t. [sent-69, score-0.461]

39 In our formulation, p(ot |st ) measures the probability of observing ot as a sample being generated by the target object class. [sent-70, score-0.933]

40 Note that Ot is an image sequence and if the images are acquired at high frame rate, it is expected that the difference between ot and ot−1 is small though object’s appearance might vary according to different of viewing angles, illuminations, and possible self-deformation. [sent-71, score-0.982]

41 Instead of adopting a complex static model to learn p(ot |st ) for all possible ot , a simpler model sufﬁces by adapting this model to account for the appearance changes. [sent-72, score-1.015]

42 In addition, since ot and ot−1 are most likely similar and computing p(ot |st ) depends on p(ot−1 |st−1 ), the prior information p(ot−1 |st−1 ) can be used to enhance the distinctiveness between the object and its background in p(ot |st ). [sent-73, score-0.873]

43 The idea of using an adaptive observation model for object tracking and then applying discriminative analysis to better predict object location is the focus of the rest the paper. [sent-74, score-1.061]

44 Nevertheless, most existing tracking methods do not update the observation models as time progresses. [sent-77, score-0.399]

45 In this paper, we follow the work by Tipping and Bishop [10] and propose an adaptive observation model based on PCA within a formal probabilistic framework. [sent-78, score-0.184]

46 3 A Discriminative Generative Observation Model In this work, we track a target object based on its observations in the videos, i. [sent-80, score-0.431]

47 Since the size of image region ot might change according to different st , we ﬁrst convert ot to a standard size and use it for tracking. [sent-83, score-1.547]

48 In the following, we denote yt as the standardized appearance vector of ot . [sent-84, score-0.976]

49 The dimensionality of the appearance vector yt is usually high. [sent-85, score-0.38]

50 In our experiments, the standard image size is a 19 × 19 patch and thus yt is a 361-dimensional vector. [sent-86, score-0.174]

51 We thus model the appearance vector with a graphical model of low-dimensional latent variables. [sent-87, score-0.36]

52 1 A Generative Model with Latent Variables A latent model relates a n-dimensional appearance vector y to a m-dimensional vector of latent variables x: y = Wx + µ + (2) where W is a n × m projection matrix associating y and x, µ is the mean of y, and is additive noise. [sent-89, score-0.401]

53 Together with (2), we have a generative observation model: p(ot |st ) = p(yt |W, µ, ) ∼ N (yt |µ, W W T + σ 2 In ) (3) This latent variable model follows the form of probabilistic principle component analysis, and its parameters can be estimated from a set of examples [10]. [sent-92, score-0.36]

54 σ2 = 1 λi n − m i=m+1 (4) To model all possible appearance variations of a target object (due to pose, illumination and view angle change), one could resort to a mixture of PPCA models. [sent-108, score-0.674]

55 On the other hand, at any given time a linear PPCA model sufﬁces to model gradual appearance variation if the model is constantly updated. [sent-110, score-0.464]

56 In this paper, we use a single PPCA, and dynamically adapt the model parameters W , µ, and σ 2 to account for appearance change. [sent-111, score-0.34]

57 1 Probability computation with Probabilistic PCA Once the model parameters are known, we can compute the probability that a vector y is a sample of this generative appearance model. [sent-114, score-0.422]

58 From (6), if the σ is set to a value much smaller than the actual one, the distance to the subspace will be favored and ignore the contribution of Mahalanobis distance, thereby rendering an inaccurate estimate. [sent-120, score-0.179]

59 The choice of σ is even more critical in situations where the appearance changes dynamically and requires σ to be adjusted accordingly. [sent-121, score-0.28]

60 2 Online Learning of Probabilistic PCA Unlike the analysis in the previous section where model parameters are estimated based on a ﬁxed set of training examples, our generative model has to learn and update its parameters on line. [sent-125, score-0.276]

61 Starting with a single example (the appearance of the tracked object in the ﬁrst video frame), our generative model constantly updates its parameters as new observations arrive. [sent-126, score-0.837]

62 Our generative model starts with a single example and gradually adapts the model parameters. [sent-150, score-0.253]

63 If we update σ based on (4), we will start with a very small value of σ since there are only a few samples at our disposal at the outset, and the algorithm could quickly lose track of the target because of an inaccurate probability estimate. [sent-151, score-0.343]

64 2 Discriminative Generative Model As is observed in Section 2, the object’s appearance at ot−1 and ot do not change much. [sent-155, score-0.872]

65 Therefore, we can use the observation at ot−1 to boost the likelihood measurement in ot . [sent-156, score-0.695]

66 , samples that are not generated from the class of the target object) that the generative model is likely to confuse at Ot . [sent-165, score-0.38]

67 , y k } where y i is the appearance vector collected in ot−1 based on state parameter si , we want to ﬁnd a linear projection V ∗ that projects Y onto t−1 a subspace such that the likelihood of Y in the subspace is minimized. [sent-169, score-0.567]

68 , p = 1 and V = v T , and thus k vT S v L(V, W, µ, σ) = − log(2π) + log |v T Cv| + T (10) 2 v Cv Note that v T Cv is the variance of the object samples in the projected space, and we need to impose a constraint, e. [sent-174, score-0.312]

69 In (11), v is a projection that keeps the object’s samples in the projected space close to the µ (with variance v T Cv = 1), while keeping negative samples in Y away from µ. [sent-178, score-0.215]

70 By projecting observation samples onto a low dimensional subspace, we enhance the discriminative power of the generative model. [sent-181, score-0.494]

71 In the meanwhile, we reduce the time required to compute probabilities, which is also a critical improvement for real time applications like object tracking. [sent-182, score-0.22]

72 The rank of A is usually small in vision applications, and V can be computed efﬁciently, thereby facilitating tracking the process. [sent-194, score-0.371]

73 4 Proposed Tracking Algorithm In this section, we summarize the proposed tracking algorithm and demonstrate how the abovementioned learning and inference algorithms are incorporated for object tracking. [sent-195, score-0.515]

74 Our algorithm localizes the tracked object in each video frame using a rectangular window. [sent-196, score-0.406]

75 Denote yt 1 N as the appearance vector of ot , and Yt = {yt , . [sent-208, score-0.976]

76 , yt } as a set of appearance vectors that corresponds to the set of state vectors St . [sent-211, score-0.438]

77 The posterior probability that the tracked object is at ci in video frame ot is then deﬁned as i p(st = ci |Ot ) = κp(yt |V, W, µ, σ)p(st = ci |s∗ ) (17) t−1 ∗ where κ is a constant. [sent-212, score-1.097]

78 ∗ Once s∗ is determined, the corresponding observation yt will be a new example to update t i i W and µ. [sent-214, score-0.273]

79 Appearance vectors yt with large p(yt |V, W, µ, σ) but whose corresponding state parameters ci are away from s∗ will be used as new examples to update V . [sent-215, score-0.324]

80 t Our tracking assumes o1 and s∗ are given (through object detection) and thus obtains the 1 ﬁrst appearance vector y1 which in turn is used an the initial value of µ, but V and W are unknown at the outset. [sent-216, score-0.726]

81 When V and W are not available, our tracking algorithm is based on template matching (with µ being the template). [sent-217, score-0.26]

82 The matrix W is computed after a small number of appearance vectors are observed. [sent-218, score-0.246]

83 In our tracking the system, we adaptively adjust σ according to Σm in W . [sent-223, score-0.289]

84 5 Experimental Results We tested the proposed algorithm with numerous object tracking experiments. [sent-226, score-0.507]

85 To examine whether our model is able to adapt and track objects in the dynamically changing environment, we recorded videos containing appearance deformation, large illumination change, and large pose variations. [sent-227, score-0.603]

86 85, and the batch size for update is set to 5 as a trade-off of computational efﬁciency as well as effectiveness of modeling appearance change due to fast motion. [sent-230, score-0.341]

87 Figure 1: A target undergoes pose and lighting variation. [sent-236, score-0.326]

88 Figures 1 and 2 show snapshots of some tracking results enclosed with rectangular windows. [sent-237, score-0.285]

89 The ﬁrst row shows the sampled images in the current frame that have the largest likelihoods of being the target locations according our discriminative generative model. [sent-239, score-0.548]

90 The second row shows the sample images in the current video frame that are selected online for updating the discriminative generative model. [sent-240, score-0.442]

91 The results in Figure 1 show the our method is able to track targets undergoing pose and lighting change. [sent-241, score-0.274]

92 Figure 2 shows tracking results where the object appearances change signiﬁcantly due to variation in pose and lighting as well as cast shadows. [sent-242, score-0.737]

93 These experiments demonstrate that our tracking algorithm is able to follow objects even when there is a large appearance change due to pose or lighting variation. [sent-243, score-0.755]

94 Empirical results show that such methods do not perform well as they do not update the object representation to account for appearance change. [sent-245, score-0.556]

95 Figure 2: A target undergoes large lighting and pose variation with cast shadows. [sent-246, score-0.376]

96 6 Conclusion We have presented a discriminative generative framework that generalizes the conventional Fisher Linear Discriminant algorithm with a proper probabilistic interpretation. [sent-247, score-0.458]

97 For object tracking, we aim to ﬁnd a discriminative generative model that best separates the target class from the background. [sent-248, score-0.725]

98 With a computationally efﬁcient algorithm that constantly update this discriminative model as time progresses, our method adapts the discriminative generative model to account for appearance variation of the target and background, thereby facilitating the tracking task in different situations. [sent-249, score-1.535]

99 Our experiments show that the proposed model is able to learn a discriminative generative model for tracking target objects undergoing large pose and lighting changes. [sent-250, score-1.034]

100 Eigentracking: Robust matching and tracking of articulated objects using view-based representation. [sent-262, score-0.302]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('ot', 0.596), ('st', 0.285), ('tracking', 0.26), ('appearance', 0.246), ('um', 0.221), ('object', 0.22), ('discriminative', 0.189), ('cv', 0.172), ('generative', 0.141), ('yt', 0.134), ('target', 0.117), ('lighting', 0.102), ('tracker', 0.089), ('subspace', 0.079), ('pose', 0.075), ('observation', 0.074), ('update', 0.065), ('samples', 0.064), ('frame', 0.064), ('svd', 0.064), ('constantly', 0.063), ('ppca', 0.059), ('track', 0.059), ('state', 0.058), ('illumination', 0.056), ('videos', 0.056), ('variation', 0.05), ('conventional', 0.049), ('tracked', 0.049), ('video', 0.048), ('lncs', 0.047), ('fisher', 0.047), ('singular', 0.046), ('facilitating', 0.044), ('sy', 0.044), ('latent', 0.044), ('discriminant', 0.043), ('static', 0.043), ('objects', 0.042), ('adapts', 0.042), ('qa', 0.042), ('buxton', 0.04), ('verlag', 0.04), ('ross', 0.04), ('image', 0.04), ('ci', 0.04), ('proper', 0.04), ('probabilistic', 0.039), ('mahalanobis', 0.038), ('inaccurate', 0.038), ('tipping', 0.038), ('undergoing', 0.038), ('locations', 0.037), ('viewing', 0.036), ('adaptive', 0.036), ('arg', 0.036), ('abovementioned', 0.035), ('forgetting', 0.035), ('progresses', 0.035), ('trackers', 0.035), ('unobservable', 0.035), ('uy', 0.035), ('observations', 0.035), ('model', 0.035), ('dynamically', 0.034), ('thereby', 0.034), ('vision', 0.033), ('projection', 0.032), ('im', 0.032), ('cipolla', 0.032), ('undergoes', 0.032), ('pca', 0.032), ('lim', 0.031), ('background', 0.031), ('formulated', 0.03), ('change', 0.03), ('illinois', 0.03), ('arrived', 0.03), ('adaptively', 0.029), ('distance', 0.028), ('projected', 0.028), ('va', 0.028), ('numerous', 0.027), ('negative', 0.027), ('examples', 0.027), ('eigenvalues', 0.027), ('location', 0.027), ('deformation', 0.026), ('enhance', 0.026), ('si', 0.025), ('rectangular', 0.025), ('likelihood', 0.025), ('incremental', 0.025), ('account', 0.025), ('bishop', 0.024), ('projects', 0.023), ('class', 0.023), ('ces', 0.023), ('newly', 0.023), ('collect', 0.023)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000002 16 nips-2004-Adaptive Discriminative Generative Model and Its Applications

Author: Ruei-sung Lin, David A. Ross, Jongwoo Lim, Ming-Hsuan Yang

2 0.39471635 83 nips-2004-Incremental Learning for Visual Tracking

Author: Jongwoo Lim, David A. Ross, Ruei-sung Lin, Ming-Hsuan Yang

Abstract: Most existing tracking algorithms construct a representation of a target object prior to the tracking task starts, and utilize invariant features to handle appearance variation of the target caused by lighting, pose, and view angle change. In this paper, we present an efﬁcient and effective online algorithm that incrementally learns and adapts a low dimensional eigenspace representation to reﬂect appearance changes of the target, thereby facilitating the tracking task. Furthermore, our incremental method correctly updates the sample mean and the eigenbasis, whereas existing incremental subspace update methods ignore the fact the sample mean varies over time. The tracking problem is formulated as a state inference problem within a Markov Chain Monte Carlo framework and a particle ﬁlter is incorporated for propagating sample distributions over time. Numerous experiments demonstrate the effectiveness of the proposed tracking algorithm in indoor and outdoor environments where the target objects undergo large pose and lighting changes. 1

3 0.2718614 102 nips-2004-Learning first-order Markov models for control

Author: Pieter Abbeel, Andrew Y. Ng

Abstract: First-order Markov models have been successfully applied to many problems, for example in modeling sequential data using Markov chains, and modeling control problems using the Markov decision processes (MDP) formalism. If a ﬁrst-order Markov model’s parameters are estimated from data, the standard maximum likelihood estimator considers only the ﬁrst-order (single-step) transitions. But for many problems, the ﬁrstorder conditional independence assumptions are not satisﬁed, and as a result the higher order transition probabilities may be poorly approximated. Motivated by the problem of learning an MDP’s parameters for control, we propose an algorithm for learning a ﬁrst-order Markov model that explicitly takes into account higher order interactions during training. Our algorithm uses an optimization criterion different from maximum likelihood, and allows us to learn models that capture longer range effects, but without giving up the beneﬁts of using ﬁrst-order Markov models. Our experimental results also show the new algorithm outperforming conventional maximum likelihood estimation in a number of control problems where the MDP’s parameters are estimated from data. 1

4 0.18281205 73 nips-2004-Generative Affine Localisation and Tracking

Author: John Winn, Andrew Blake

Abstract: We present an extension to the Jojic and Frey (2001) layered sprite model which allows for layers to undergo afﬁne transformations. This extension allows for afﬁne object pose to be inferred whilst simultaneously learning the object shape and appearance. Learning is carried out by applying an augmented variational inference algorithm which includes a global search over a discretised transform space followed by a local optimisation. To aid correct convergence, we use bottom-up cues to restrict the space of possible afﬁne transformations. We present results on a number of video sequences and show how the model can be extended to track an object whose appearance changes throughout the sequence. 1

5 0.14584418 28 nips-2004-Bayesian inference in spiking neurons

Author: Sophie Deneve

Abstract: We propose a new interpretation of spiking neurons as Bayesian integrators accumulating evidence over time about events in the external world or the body, and communicating to other neurons their certainties about these events. In this model, spikes signal the occurrence of new information, i.e. what cannot be predicted from the past activity. As a result, ﬁring statistics are close to Poisson, albeit providing a deterministic representation of probabilities. We proceed to develop a theory of Bayesian inference in spiking neural networks, recurrent interactions implementing a variant of belief propagation. Many perceptual and motor tasks performed by the central nervous system are probabilistic, and can be described in a Bayesian framework [4, 3]. A few important but hidden properties, such as direction of motion, or appropriate motor commands, are inferred from many noisy, local and ambiguous sensory cues. These evidences are combined with priors about the sensory world and body. Importantly, because most of these inferences should lead to quick and irreversible decisions in a perpetually changing world, noisy cues have to be integrated on-line, but in a way that takes into account unpredictable events, such as a sudden change in motion direction or the appearance of a new stimulus. This raises the question of how this temporal integration can be performed at the neural level. It has been proposed that single neurons in sensory cortices represent and compute the log probability that a sensory variable takes on a certain value (eg Is visual motion in the neuron’s preferred direction?) [9, 7]. Alternatively, to avoid normalization issues and provide an appropriate signal for decision making, neurons could represent the log probability ratio of a particular hypothesis (eg is motion more likely to be towards the right than towards the left) [7, 6]. Log probabilities are convenient here, since under some assumptions, independent noisy cues simply combine linearly. Moreover, there are physiological evidence for the neural representation of log probabilities and log probability ratios [9, 6, 7]. However, these models assume that neurons represent probabilities in their ﬁring rates. We argue that it is important to study how probabilistic information are encoded in spikes. Indeed, it seems spurious to marry the idea of an exquisite on-line integration of noisy cues with an underlying rate code that requires averaging on large populations of noisy neurons and long periods of time. In particular, most natural tasks require this integration to take place on the time scale of inter-spike intervals. Spikes are more efﬁciently signaling events ∗ Institute of Cognitive Science, 69645 Bron, France than analog quantities. In addition, a neural theory of inference with spikes will bring us closer to the physiological level and generate more easily testable predictions. Thus, we propose a new theory of neural processing in which spike trains provide a deterministic, online representation of a log-probability ratio. Spikes signals events, eg that the log-probability ratio has exceeded what could be predicted from previous spikes. This form of coding was loosely inspired by the idea of ”energy landscape” coding proposed by Hinton and Brown [2]. However, contrary to [2] and other theories using rate-based representation of probabilities, this model is self-consistent and does not require different models for encoding and decoding: As output spikes provide new, unpredictable, temporally independent evidence, they can be used directly as an input to other Bayesian neurons. Finally, we show that these neurons can be used as building blocks in a theory of approximate Bayesian inference in recurrent spiking networks. Connections between neurons implement an underlying Bayesian network, consisting of coupled hidden Markov models. Propagation of spikes is a form of belief propagation in this underlying graphical model. Our theory provides computational explanations of some general physiological properties of cortical neurons, such as spike frequency adaptation, Poisson statistics of spike trains, the existence of strong local inhibition in cortical columns, and the maintenance of a tight balance between excitation and inhibition. Finally, we discuss the implications of this model for the debate about temporal versus rate-based neural coding. 1 Spikes and log posterior odds 1.1 Synaptic integration seen as inference in a hidden Markov chain We propose that each neuron codes for an underlying ”hidden” binary variable, xt , whose state evolves over time. We assume that xt depends only on the state at the previous time step, xt−dt , and is conditionally independent of other past states. The state xt can switch 1 from 0 to 1 with a constant rate ron = dt limdt→0 P (xt = 1|xt−dt = 0), and from 1 to 0 with a constant rate roﬀ . For example, these transition rates could represent how often motion in a preferred direction appears the receptive ﬁeld and how long it is likely to stay there. The neuron infers the state of its hidden variable from N noisy synaptic inputs, considered to be observations of the hidden state. In this initial version of the model, we assume that these inputs are conditionally independent homogeneous Poisson processes, synapse i i emitting a spike between time t and t + dt (si = 1) with constant probability qon dt if t i xt = 1, and another constant probability qoﬀ dt if xt = 0. The synaptic spikes are assumed to be otherwise independent of previous synaptic spikes, previous states and spikes at other synapses. The resulting generative model is a hidden Markov chain (ﬁgure 1-A). However, rather than estimating the state of its hidden variable and communicating this estimate to other neurons (for example by emitting a spike when sensory evidence for xt = 1 goes above a threshold) the neuron reports and communicates its certainty that the current state is 1. This certainty takes the form of the log of the ratio of the probability that the hidden state is 1, and the probability that the state is 0, given all the synaptic inputs P (xt =1|s0→t ) received so far: Lt = log P (xt =0|s0→t ) . We use s0→t as a short hand notation for the N synaptic inputs received at present and in the past. We will refer to it as the log odds ratio. Thanks to the conditional independencies assumed in the generative model, we can compute this Log odds ratio iteratively. Taking the limit as dt goes to zero, we get the following differential equation: ˙ L = ron 1 + e−L − roﬀ 1 + eL + i wi δ(si − 1) − θ t B. A. xt ron .roff dt qon , qoff st xt ron .roff i t st dt s qon , qoff qon , qoff st dt xt j st Ot It Gt Ot Lt t t dt C. E. 2 0 -2 -4 D. 500 1000 1500 2000 2500 2 3000 Count Log odds 4 20 Lt 0 -2 0 500 1000 1500 2000 2500 Time Ot 3000 0 200 400 600 ISI Figure 1: A. Generative model for the synaptic input. B. Schematic representation of log odds ratio encoding and decoding. The dashed circle represents both eventual downstream elements and the self-prediction taking place inside the model neuron. A spike is ﬁred only when Lt exceeds Gt . C. One example trial, where the state switches from 0 to 1 (shaded area) and back to 0. plain: Lt , dotted: Gt . Black stripes at the top: corresponding spikes train. D. Mean Log odds ratio (dark line) and mean output ﬁring rate (clear line). E. Output spike raster plot (1 line per trial) and ISI distribution for the neuron shown is C. and D. Clear line: ISI distribution for a poisson neuron with the same rate. wi , the synaptic weight, describe how informative synapse i is about the state of the hidden i qon variable, e.g. wi = log qi . Each synaptic spike (si = 1) gives an impulse to the log t off odds ratio, which is positive if this synapse is more active when the hidden state if 1 (i.e it increases the neuron’s conﬁdence that the state is 1), and negative if this synapse is more active when xt = 0 (i.e it decreases the neuron’s conﬁdence that the state is 1). The bias, θ, is determined by how informative it is not to receive any spike, e.g. θ = i i i qon − qoﬀ . By convention, we will consider that the ”bias” is positive or zero (if not, we need simply to invert the status of the state x). 1.2 Generation of output spikes The spike train should convey a sparse representation of Lt , so that each spike reports new information about the state xt that is not redundant with that reported by other, preceding, spikes. This proposition is based on three arguments: First, spikes, being metabolically expensive, should be kept to a minimum. Second, spikes conveying redundant information would require a decoding of the entire spike train, whereas independent spike can be taken into account individually. And ﬁnally, we seek a self consistent model, with the spiking output having a similar semantics to its spiking input. To maximize the independence of the spikes (conditioned on xt ), we propose that the neuron ﬁres only when the difference between its log odds ratio Lt and a prediction Gt of this log odds ratio based on the output spikes emitted so far reaches a certain threshold. Indeed, supposing that downstream elements predicts Lt as best as they can, the neuron only needs to ﬁre when it expects that prediction to be too inaccurate (ﬁgure 1-B). In practice, this will happen when the neuron receives new evidence for xt = 1. Gt should thereby follow the same dynamics as Lt when spikes are not received. The equation for Gt and the output Ot (Ot = 1 when an output spike is ﬁred) are given by: ˙ G = Ot = ron 1 + e−L − roﬀ 1 + eL + go δ(Ot − 1) go 1. when Lt > Gt + , 0 otherwise, 2 (1) (2) Here go , a positive constant, is the only free parameter, the other parameters being constrained by the statistics of the synaptic input. 1.3 Results Figure 1-C plots a typical trial, showing the behavior of L, G and O before, during and after presentation of the stimulus. As random synaptic inputs are integrated, L ﬂuctuates and eventually exceeds G + 0.5, leading to an output spike. Immediately after a spike, G jumps to G + go , which prevents (except in very rare cases) a second spike from immediately following the ﬁrst. Thus, this ”jump” implements a relative refractory period. However, ron G decays as it tends to converge back to its stable level gstable = log roff . Thus L eventually exceeds G again, leading to a new spike. This threshold crossing happens more often during stimulation (xt = 1) as the net synaptic input alters to create a higher overall level of certainty, Lt . Mean Log odds ratio and output ﬁring rate ¯ The mean ﬁring rate Ot of the Bayesian neuron during presentation of its preferred stimulus (i.e. when xt switches from 0 to 1 and back to 0) is plotted in ﬁgure 1-D, together with the ¯ mean log posterior ratio Lt , both averaged over trials. Not surprisingly, the log-posterior ratio reﬂects the leaky integration of synaptic evidence, with an effective time constant that depends on the transition probabilities ron , roﬀ . If the state is very stable (ron = roﬀ ∼ 0), synaptic evidence is integrated over almost inﬁnite time periods, the mean log posterior ratio tending to either increase or decrease linearly with time. In the example in ﬁgure 1D, the state is less stable, so ”old” synaptic evidence are discounted and Lt saturates. ¯ In contrast, the mean output ﬁring rate Ot tracks the state of xt almost perfectly. This is because, as a form of predictive coding, the output spikes reﬂect the new synaptic i evidence, It = i δ(st − 1) − θ, rather than the log posterior ratio itself. In particular, the mean output ﬁring rate is a rectiﬁed linear function of the mean input, e. g. + ¯ ¯ wi q i −θ . O= 1I= go i on(oﬀ) Analogy with a leaky integrate and ﬁre neuron We can get an interesting insight into the computation performed by this neuron by linearizing L and G around their mean levels over trials. Here we reduce the analysis to prolonged, statistically stable periods when the state is constant (either ON or OFF). In this case, the ¯ ¯ mean level of certainty L and its output prediction G are also constant over time. We make the rough approximation that the post spike jump, go , and the input ﬂuctuations are small ¯ compared to the mean level of certainty L. Rewriting Vt = Lt − Gt + go 2 as the ”membrane potential” of the Bayesian neuron: ˙ V = −kL V + It − ∆go − go Ot ¯ ¯ ¯ where kL = ron e−L + roﬀ eL , the ”leak” of the membrane potential, depends on the overall ¯ level of certainty. ∆go is positive and a monotonic increasing function of go . A. s t1 dt s t1 s t1 dt B. C. x t1 x t3 dt x t3 x t3 dt x t1 x t1 x t1 x t2 x t3 x t1 … x tn x t3 x t2 … x tn … dt dt Lx2 D. x t2 dt s t2 dt x t2 s t2 x t2 dt s t2 dt Log odds 10 No inh -0.5 -1 -1 -1.5 -2 5 Feedback 500 1000 1500 2000 Tiger Stripes 0 -5 -10 500 1000 1500 2000 2500 Time Figure 2: A. Bayesian causal network for yt (tiger), x1 (stripes) and x2 (paws). B. A nett t work feedforward computing the log posterior for x1 . C. A recurrent network computing t the log posterior odds for all variables. D. Log odds ratio in a simulated trial with the net2 1 1 work in C (see text). Thick line: Lx , thin line: Lx , dash-dotted: Lx without inhibition. t t t 2 Insert: Lx averaged over trials, showing the effect of feedback. t The linearized Bayesian neuron thus acts in its stable regime as a leaky integrate and ﬁre (LIF) neuron. The membrane potential Vt integrates its input, Jt = It − ∆go , with a leak kL . The neuron ﬁres when its membrane potential reaches a constant threshold go . After ¯ each spikes, Vt is reset to 0. Interestingly, for appropriately chosen compression factor go , the mean input to the lin¯ ¯ earized neuron J = I − ∆go ≈ 0 1 . This means that the membrane potential is purely driven to its threshold by input ﬂuctuations, or a random walk in membrane potential. As a consequence, the neuron’s ﬁring will be memoryless, and close to a Poisson process. In particular, we found Fano factor close to 1 and quasi-exponential ISI distribution (ﬁgure 1E) on the entire range of parameters tested. Indeed, LIF neurons with balanced inputs have been proposed as a model to reproduce the statistics of real cortical neurons [8]. This balance is implemented in our model by the neuron’s effective self-inhibition, even when the synaptic input itself is not balanced. Decoding As we previously said, downstream elements could predict the log odds ratio Lt by computing Gt from the output spikes (Eq 1, ﬁg 1-B). Of course, this requires an estimate of the transition probabilities ron , roﬀ , that could be learned from the observed spike trains. However, we show next that explicit decoding is not necessary to perform bayesian inference in spiking networks. Intuitively, this is because the quantity that our model neurons receive and transmit, eg new information, is exactly what probabilistic inference algorithm propagate between connected statistical elements. 1 ¯ Even if go is not chosen optimally, the inﬂuence of the drift J is usually negligible compared to the large ﬂuctuations in membrane potential. 2 Bayesian inference in cortical networks The model neurons, having the same input and output semantics, can be used as building blocks to implement more complex generative models consisting of coupled Markov chains. Consider, for example, the example in ﬁgure 2-A. Here, a ”parent” variable x1 t (the presence of a tiger) can cause the state of n other ”children” variables ([xk ]k=2...n ), t of whom two are represented (the presence of stripes,x2 , and motion, x3 ). The ”chilt t dren” variables are Bayesian neurons identical to those described previously. The resulting bayesian network consist of n + 1 coupled hidden Markov chains. Inference in this architecture corresponds to computing the log posterior odds ratio for the tiger, x1 , and the log t posterior of observing stripes or motion, ([xk ]k=2...n ), given the synaptic inputs received t by the entire network so far, i.e. s2 , . . . , sk . 0→t 0→t Unfortunately, inference and learning in this network (and in general in coupled Markov chains) requires very expensive computations, and cannot be performed by simply propagating messages over time and among the variable nodes. In particular, the state of a child k variable xt depends on xk , sk , x1 and the state of all other children at the previous t t t−dt time step, [xj ]2

6 0.1316395 44 nips-2004-Conditional Random Fields for Object Recognition

7 0.12930462 40 nips-2004-Common-Frame Model for Object Recognition

8 0.12356246 183 nips-2004-Temporal-Difference Networks

9 0.1218861 12 nips-2004-A Temporal Kernel-Based Model for Tracking Hand Movements from Neural Activities

10 0.11826867 13 nips-2004-A Three Tiered Approach for Articulated Object Action Modeling and Recognition

11 0.10869755 91 nips-2004-Joint Tracking of Pose, Expression, and Texture using Conditionally Gaussian Filters

12 0.10287748 99 nips-2004-Learning Hyper-Features for Visual Identification

13 0.10203411 134 nips-2004-Object Classification from a Single Example Utilizing Class Relevance Metrics

14 0.085804164 163 nips-2004-Semi-parametric Exponential Family PCA

15 0.083604112 55 nips-2004-Distributed Occlusion Reasoning for Tracking with Nonparametric Belief Propagation

16 0.08275298 88 nips-2004-Intrinsically Motivated Reinforcement Learning

17 0.075028054 142 nips-2004-Outlier Detection with One-class Kernel Fisher Discriminants

18 0.073459044 5 nips-2004-A Harmonic Excitation State-Space Approach to Blind Separation of Speech

19 0.068615422 59 nips-2004-Efficient Kernel Discriminant Analysis via QR Decomposition

20 0.067342274 110 nips-2004-Matrix Exponential Gradient Updates for On-line Learning and Bregman Projection

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.225), (1, -0.023), (2, 0.114), (3, -0.274), (4, 0.231), (5, -0.093), (6, 0.006), (7, -0.204), (8, -0.016), (9, 0.146), (10, 0.094), (11, 0.11), (12, 0.213), (13, 0.24), (14, 0.053), (15, -0.041), (16, -0.034), (17, -0.187), (18, -0.056), (19, 0.058), (20, -0.168), (21, -0.036), (22, 0.159), (23, -0.005), (24, -0.171), (25, 0.058), (26, -0.038), (27, 0.066), (28, 0.125), (29, -0.05), (30, -0.107), (31, 0.073), (32, 0.105), (33, 0.109), (34, -0.074), (35, 0.009), (36, -0.02), (37, 0.054), (38, -0.001), (39, -0.028), (40, 0.014), (41, -0.0), (42, -0.08), (43, 0.085), (44, -0.013), (45, -0.027), (46, -0.022), (47, 0.047), (48, -0.013), (49, -0.001)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97699594 16 nips-2004-Adaptive Discriminative Generative Model and Its Applications

Author: Ruei-sung Lin, David A. Ross, Jongwoo Lim, Ming-Hsuan Yang

2 0.85650575 83 nips-2004-Incremental Learning for Visual Tracking

Author: Jongwoo Lim, David A. Ross, Ruei-sung Lin, Ming-Hsuan Yang

3 0.72040814 73 nips-2004-Generative Affine Localisation and Tracking

Author: John Winn, Andrew Blake

4 0.56983739 102 nips-2004-Learning first-order Markov models for control

Author: Pieter Abbeel, Andrew Y. Ng

5 0.48745018 40 nips-2004-Common-Frame Model for Object Recognition

Author: Pierre Moreels, Pietro Perona

Abstract: A generative probabilistic model for objects in images is presented. An object consists of a constellation of features. Feature appearance and pose are modeled probabilistically. Scene images are generated by drawing a set of objects from a given database, with random clutter sprinkled on the remaining image surface. Occlusion is allowed. We study the case where features from the same object share a common reference frame. Moreover, parameters for shape and appearance densities are shared across features. This is to be contrasted with previous work on probabilistic ‘constellation’ models where features depend on each other, and each feature and model have different pose and appearance statistics [1, 2]. These two differences allow us to build models containing hundreds of features, as well as to train each model from a single example. Our model may also be thought of as a probabilistic revisitation of Lowe’s model [3, 4]. We propose an efﬁcient entropy-minimization inference algorithm that constructs the best interpretation of a scene as a collection of objects and clutter. We test our ideas with experiments on two image databases. We compare with Lowe’s algorithm and demonstrate better performance, in particular in presence of large amounts of background clutter.

6 0.38543254 13 nips-2004-A Three Tiered Approach for Articulated Object Action Modeling and Recognition

7 0.37676233 44 nips-2004-Conditional Random Fields for Object Recognition

8 0.33864889 29 nips-2004-Beat Tracking the Graphical Model Way

9 0.33296224 99 nips-2004-Learning Hyper-Features for Visual Identification

10 0.32775038 88 nips-2004-Intrinsically Motivated Reinforcement Learning

11 0.32234812 183 nips-2004-Temporal-Difference Networks

12 0.31495008 12 nips-2004-A Temporal Kernel-Based Model for Tracking Hand Movements from Neural Activities

13 0.30423331 91 nips-2004-Joint Tracking of Pose, Expression, and Texture using Conditionally Gaussian Filters

14 0.2899313 186 nips-2004-The Correlated Correspondence Algorithm for Unsupervised Registration of Nonrigid Surfaces

15 0.28524798 55 nips-2004-Distributed Occlusion Reasoning for Tracking with Nonparametric Belief Propagation

16 0.26982382 191 nips-2004-The Variational Ising Classifier (VIC) Algorithm for Coherently Contaminated Data

17 0.26830626 28 nips-2004-Bayesian inference in spiking neurons

18 0.24873626 134 nips-2004-Object Classification from a Single Example Utilizing Class Relevance Metrics

19 0.24468412 193 nips-2004-Theories of Access Consciousness

20 0.23514065 158 nips-2004-Sampling Methods for Unsupervised Learning

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(8, 0.066), (13, 0.101), (15, 0.23), (26, 0.047), (31, 0.034), (33, 0.164), (35, 0.046), (39, 0.043), (50, 0.034), (71, 0.126), (76, 0.017)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.95781398 83 nips-2004-Incremental Learning for Visual Tracking

Author: Jongwoo Lim, David A. Ross, Ruei-sung Lin, Ming-Hsuan Yang

same-paper 2 0.93279397 16 nips-2004-Adaptive Discriminative Generative Model and Its Applications

Author: Ruei-sung Lin, David A. Ross, Jongwoo Lim, Ming-Hsuan Yang

3 0.91311646 24 nips-2004-Approximately Efficient Online Mechanism Design

Author: David C. Parkes, Dimah Yanovsky, Satinder P. Singh

Abstract: Online mechanism design (OMD) addresses the problem of sequential decision making in a stochastic environment with multiple self-interested agents. The goal in OMD is to make value-maximizing decisions despite this self-interest. In previous work we presented a Markov decision process (MDP)-based approach to OMD in large-scale problem domains. In practice the underlying MDP needed to solve OMD is too large and hence the mechanism must consider approximations. This raises the possibility that agents may be able to exploit the approximation for selﬁsh gain. We adopt sparse-sampling-based MDP algorithms to implement efﬁcient policies, and retain truth-revelation as an approximate BayesianNash equilibrium. Our approach is empirically illustrated in the context of the dynamic allocation of WiFi connectivity to users in a coffeehouse. 1

4 0.90871346 93 nips-2004-Kernel Projection Machine: a New Tool for Pattern Recognition

Author: Laurent Zwald, Gilles Blanchard, Pascal Massart, Régis Vert

Abstract: This paper investigates the effect of Kernel Principal Component Analysis (KPCA) within the classiﬁcation framework, essentially the regularization properties of this dimensionality reduction method. KPCA has been previously used as a pre-processing step before applying an SVM but we point out that this method is somewhat redundant from a regularization point of view and we propose a new algorithm called Kernel Projection Machine to avoid this redundancy, based on an analogy with the statistical framework of regression for a Gaussian white noise model. Preliminary experimental results show that this algorithm reaches the same performances as an SVM. 1

5 0.88737899 9 nips-2004-A Method for Inferring Label Sampling Mechanisms in Semi-Supervised Learning

Author: Saharon Rosset, Ji Zhu, Hui Zou, Trevor J. Hastie

Abstract: We consider the situation in semi-supervised learning, where the “label sampling” mechanism stochastically depends on the true response (as well as potentially on the features). We suggest a method of moments for estimating this stochastic dependence using the unlabeled data. This is potentially useful for two distinct purposes: a. As an input to a supervised learning procedure which can be used to “de-bias” its results using labeled data only and b. As a potentially interesting learning task in itself. We present several examples to illustrate the practical usefulness of our method.

6 0.88398677 197 nips-2004-Two-Dimensional Linear Discriminant Analysis

7 0.88003021 178 nips-2004-Support Vector Classification with Input Data Uncertainty

8 0.87775415 183 nips-2004-Temporal-Difference Networks

9 0.87650824 201 nips-2004-Using the Equivalent Kernel to Understand Gaussian Process Regression

10 0.87406081 92 nips-2004-Kernel Methods for Implicit Surface Modeling

11 0.87354112 168 nips-2004-Semigroup Kernels on Finite Sets

12 0.87218654 79 nips-2004-Hierarchical Eigensolver for Transition Matrices in Spectral Methods

13 0.87138361 110 nips-2004-Matrix Exponential Gradient Updates for On-line Learning and Bregman Projection

14 0.87009925 148 nips-2004-Probabilistic Computation in Spiking Populations

15 0.86929142 55 nips-2004-Distributed Occlusion Reasoning for Tracking with Nonparametric Belief Propagation

16 0.86889219 60 nips-2004-Efficient Kernel Machines Using the Improved Fast Gauss Transform

17 0.86699343 91 nips-2004-Joint Tracking of Pose, Expression, and Texture using Conditionally Gaussian Filters

18 0.86447054 131 nips-2004-Non-Local Manifold Tangent Learning

19 0.86328894 133 nips-2004-Nonparametric Transforms of Graph Kernels for Semi-Supervised Learning

20 0.86099005 73 nips-2004-Generative Affine Localisation and Tracking