nips nips2003 nips2003-22 knowledge-graph by maker-knowledge-mining

22 nips-2003-An Improved Scheme for Detection and Labelling in Johansson Displays

Source: pdf

Author: Claudio Fanti, Marzia Polito, Pietro Perona

Abstract: Consider a number of moving points, where each point is attached to a joint of the human body and projected onto an image plane. Johannson showed that humans can eﬀortlessly detect and recognize the presence of other humans from such displays. This is true even when some of the body points are missing (e.g. because of occlusion) and unrelated clutter points are added to the display. We are interested in replicating this ability in a machine. To this end, we present a labelling and detection scheme in a probabilistic framework. Our method is based on representing the joint probability density of positions and velocities of body points with a graphical model, and using Loopy Belief Propagation to calculate a likely interpretation of the scene. Furthermore, we introduce a global variable representing the body’s centroid. Experiments on one motion-captured sequence suggest that our scheme improves on the accuracy of a previous approach based on triangulated graphical models, especially when very few parts are visible. The improvement is due both to the more general graph structure we use and, more signiﬁcantly, to the introduction of the centroid variable. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract Consider a number of moving points, where each point is attached to a joint of the human body and projected onto an image plane. [sent-8, score-0.294]

2 This is true even when some of the body points are missing (e. [sent-10, score-0.245]

3 because of occlusion) and unrelated clutter points are added to the display. [sent-12, score-0.13]

4 We are interested in replicating this ability in a machine. [sent-13, score-0.048]

5 To this end, we present a labelling and detection scheme in a probabilistic framework. [sent-14, score-0.354]

6 Our method is based on representing the joint probability density of positions and velocities of body points with a graphical model, and using Loopy Belief Propagation to calculate a likely interpretation of the scene. [sent-15, score-0.417]

7 Furthermore, we introduce a global variable representing the body’s centroid. [sent-16, score-0.115]

8 Experiments on one motion-captured sequence suggest that our scheme improves on the accuracy of a previous approach based on triangulated graphical models, especially when very few parts are visible. [sent-17, score-0.22]

9 The improvement is due both to the more general graph structure we use and, more signiﬁcantly, to the introduction of the centroid variable. [sent-18, score-0.131]

10 1 Introduction Perceiving and analyzing human motion is a natural and useful task for our visual system. [sent-19, score-0.147]

11 As Johannson experiments show [4], the instantaneous information on the position and velocity of a few features, such as the joints of the body, present suﬃcient information to detect human presence and understand the gist of human activity. [sent-21, score-0.258]

12 This is true even if clutter features are detected in the scene, and if some body parts features are occluded (generalized Johansson display). [sent-22, score-0.614]

13 Selecting features in a frame, as well as computing their velocity across frames, is a task for which good quality solutions exist in the literature [5] and we will not consider it here. [sent-23, score-0.092]

14 We therefore assume that a number of features that are associated to the body have been detected and their velocity has been computed. [sent-24, score-0.394]

15 We will not assume that all such features have been found, nor that all the features that were detected are associated to the body. [sent-25, score-0.161]

16 the detection of the presence of a human in the scene and the labelling of the point features as parts of the body or as clutter. [sent-28, score-0.848]

17 We generalize an approach presented in [3] where the pattern of point positions and velocities associated to human motion was modelled with a triangulated graphical model. [sent-29, score-0.354]

18 We are interested here in exploring the beneﬁt of allowing long-range connections, and therefore loops in the graph representing correlations between cliques of variables. [sent-30, score-0.168]

19 Furthermore, while [3] obtained translation invariance at the level of individual cliques, we study the possibility of obtaining translation invariance globally by introducing a variable representing the ensemble model of the body. [sent-31, score-0.455]

20 Algorithms based on loopy belief propagation (LBP) are applied to eﬃciently compute high-likelihood interpretations of the scene, and therefore detection and labelling. [sent-32, score-0.404]

21 2 Problem Deﬁnition We identify M = 16 relevant body parts (intuitively corresponding to the main joints). [sent-47, score-0.341]

22 Each marked point on a display (referred to as a detection or observation) is denoted by yi ∈ R4 and is endowed with four values, i. [sent-48, score-0.265]

23 yi = [yi,a , yi,b , yi,va , yi,vb ]T corresponding to its horizontal and vertical positions and velocities. [sent-50, score-0.104]

24 Our goal here is to ﬁnd the most probable assignment of a subset of detections to the body parts. [sent-51, score-0.332]

25 In general N ≥ M however some or all of the M parts might not be present in a given display. [sent-56, score-0.12]

26 The binary random variable δ i indicates whether the ith part has been detected or not (i ∈ {1 . [sent-57, score-0.087]

27 N } is used to further specify the correspondence of a body part i to a particular detection λi . [sent-67, score-0.326]

28 Since this makes sense only if the body part is detected, we assume by convention that λi = 0 if δi = 0. [sent-68, score-0.221]

29 A pair h = [λ, δ] is called a labelling hypothesis. [sent-69, score-0.249]

30 Any particular labelling hypothesis determines a partition of the set of indices corresponding to detections into foreground and background: [1 . [sent-70, score-0.525]

31 We say that m = |F| parts have been detected and M − m are missing. [sent-80, score-0.175]

32 Based on the partition induced on λ by δ, we can deﬁne two vectors λf = λF and λb = λB , each identifying the detections that were assigned to the foreground and those assigned to the background respectively. [sent-81, score-0.268]

33 Finally, the set of detections y remains partitioned into the vectors yλf and yλb of the foreground and background detections respectively. [sent-82, score-0.379]

34 More speciﬁcally, when all M parts are observed (δ = [1 . [sent-84, score-0.12]

35 ˆ ˆ ˆ Our goal is to ﬁnd an hypothesis h = [λ, δ] such that ˆ ˆ [λ, δ] = arg max{Q(λ, δ)} = arg max{fyλ |λδ (yλ |λ, δ)}. [sent-89, score-0.137]

36 λδ 2 (1) λδ Learning the Model’s Parameters and Structure In this section we will assume some familiarity with the connections between probability density functions and graphical models. [sent-90, score-0.062]

37 Let us initially assume that the moving human being we want to detect is centrally positioned in the frame. [sent-91, score-0.133]

38 In the learning process we want to estimate the parameters of fy f |λδ (yλf |λδ), λ where the labeling of the training set is known, N = M (no clutter is present) and δ = [1 . [sent-93, score-0.86]

39 A fully connected graphical model would be the most accurate description of the training set, however, the search for the optimal labelling, given a display, would be computationally infeasible. [sent-97, score-0.062]

40 We recall that the BIC score is consistent, and that since the probability distribution factorizes family-wise, the score decomposes additively. [sent-103, score-0.144]

41 We therefore attempt to determine the highest scoring graph by mean of a greedy hillclimbing algorithm, with random restarts. [sent-105, score-0.082]

42 To prevent getting stuck in local maxima, we randomly restart a number of times once we cannot get any score improvements, and then we pick the graph achieving the highest score overall. [sent-107, score-0.223]

43 As opposed to previous approaches [3], no decomposability of the graph is imposed, and exact belief propagation methods that pass through the construction of a junc- tion tree are not applicable. [sent-109, score-0.269]

44 When the junction property is satisﬁed, the maximum spanning tree algorithm allows an eﬃcient construction of the junction tree. [sent-110, score-0.154]

45 The tree with the most populated separators between cliques is produced in linear time. [sent-111, score-0.105]

46 Here, we propose instead a construction of the junction graph that (greedily) attempts to minimize the complexity of the induced subgraph associated with each variable. [sent-112, score-0.149]

47 Light shaded vertices represent variables associated to diﬀerent body parts, edges indicate conditional (in)dependencies, following the standard Graphical Models conventions. [sent-114, score-0.271]

48 [Left] Hand made decomposable graph from [3], used for comparison. [sent-115, score-0.134]

49 3 Detection and Labelling with Expectation Maximization One could solve the maximization problem (1) by means of Belief Propagation (BP), however, we require our system to be invariant with respect to translations in the ﬁrst two coordinates (position) of the observations. [sent-117, score-0.061]

50 We ﬁnally use an EM-like procedure to estimate γ obtaining, as a by-product, the maximizing hypothesis h we are after. [sent-121, score-0.103]

51 1 E-Step As the hypothesis h is unobservable we replace the complete-data log-likelihood, with its expected value ˆ ˜ Lc (f , h) = Efh [log fyλ |γ (¯λ |γ)] y ˜ ¯ (2) ˜ where the expectation is taken with respect to a generic distribution fh (h). [sent-123, score-0.117]

52 It’s (k) (k−1) ˜ known that the E-step maximizing solution is fh (h) ∝ fyλ |γ (¯λ |γ y ). [sent-124, score-0.082]

53 y ¯ h Given the current estimate γ (k−1) of γ, the hypothesis h(k) can be determined by maximizing the (discrete) potential Π(h) = log fyλf |γh (¯λf |γ (k−1) h) · fyλb |h (yλb |h) y ¯ with a Max-Sum Loopy Belief Propagation (LBP) on the associated junction graph. [sent-128, score-0.194]

54 For a root node, its marginal pmf is multiplied into one of its children. [sent-131, score-0.042]

55 we compute γ (k+1) = arg max{log fyλ |γ (¯λ(k) |γ)} y ¯ γ (3) The maximizing γ can be obtained from 0= T ¯ −1 ¯ ¯ γ [(yλ − µ − Jγ) Σ (yλ − µ − Jγ)] where J4 = diag(1, 1, 0, 0) and J = [ J4 J4 ··· (4) T J4 ] . [sent-136, score-0.068]

56 3 Detection Criteria Let σ be a (discrete) indicator random variable for the event that the Johansson’s display represents a scene with a human body. [sent-141, score-0.275]

57 In the following section we will describe a way for determining whether a human body is actually present (detection). [sent-143, score-0.294]

58 By deﬁning fσ |y (1|y) R(y) = fσ|y (0|y) , we claim that a human body is present whenever R(y) > 1. [sent-144, score-0.294]

59 By Bayes rule, R(y) can be rewritten as R(y) = fy|σ (y|1) fy|σ (y|1) fσ (1) · = · Rp fy|σ (y|0) fσ (0) fy|σ (y|0) 1 Experimentally it is observed that when LBP converges, the determined maximum is either global or, although local, the potential’s value is very close to its global optimum. [sent-145, score-0.108]

60 In order to compute the R(y) we marginalize over the labelling hypothesis h. [sent-147, score-0.318]

61 When σ = 0, the only admissible hypotheses must have δ = 0T (no body parts are present) which translates into fδ|σ (δ|σ) = P [δ = δ|σ = 0] = 1k (δ − 0T ). [sent-148, score-0.341]

62 Also, fλ|δσ (λ|δ1) = N −N as no labelling is more likely than any other, before we have seen the detections. [sent-149, score-0.249]

63 All N detections are labelled by λ as background and their conditional density is UN (A). [sent-150, score-0.225]

64 When σ = 1, we have fδ|σ (δ|1) = P [δ = δ] = 2−M as we assume that each body 1 part appears (or not) in a given display with probability 2 , independently of all other parts. [sent-152, score-0.351]

65 However, we will assume that the ML labelling ˆ hσ is predominant over all other labelling, so that in the estimate of σ we can approximate marginalization with maximization and therefore write R(y) ≈ Rp AN ˆˆ fy|λδσ (y|λδ1) 2M ˆ ˆ where λ, δ is the maximizing hypothesis when σ = 1. [sent-155, score-0.413]

66 4 Experimental Results In our experiment we use two sequences W1 and W22 of about 7,000 frames each, representing a human subject walking back and forth along a straight line. [sent-156, score-0.175]

67 Both sequences were acquired and labelled with a motion capture system. [sent-157, score-0.131]

68 Each pair of consecutive frames is used to produce a Johannson display with positions and velocities. [sent-158, score-0.223]

69 A 700 frames random sample from W2 is then used to test of our algorithm. [sent-160, score-0.045]

70 We evaluate the performance of our technique and compare it with the hand-made, decomposable graphical model of [3]. [sent-161, score-0.138]

71 There, translation invariance is achieved by using relative positions within each clique. [sent-162, score-0.245]

72 We refer to it as to the local version of translation invariance (as opposed to the global version proposed in this paper). [sent-163, score-0.28]

73 We ﬁrst explore the beneﬁts of just relaxing the decomposability constrain, still implementing the translation invariance locally. [sent-164, score-0.245]

74 The lower two dashed curves of Figure 2 already show a noticeable improvement, especially when fewer body parts are visible. [sent-165, score-0.341]

75 However, the biggest increase in performance is brought by global translation invariance as it is evident from the upper two curves of Figure 2. [sent-166, score-0.251]

76 20 10 12 0 3 4 5 6 7 8 9 10 11 12 Number of Visible parts Figure 2: Detection and Labeling Performance. [sent-184, score-0.12]

77 [Left] Labeling: On each display from the sequence W2, we randomly occlude between 3 and 10 parts and superimpose 30 randomly positioned clutter points. [sent-185, score-0.391]

78 For any given number of visible parts, the four curves represent the percentage of correctly labeled parts out of the total labels in all 700 displays of W2. [sent-186, score-0.223]

79 Each curve reﬂects a combination of either Local or Global translation invariance and Decomposable or Loopy graph. [sent-187, score-0.197]

80 of detecting a person when the display shows one) for a ﬁxed Pf alse−alarm = 10% (probability of stating that a person is present when only 30 points of clutters are presented). [sent-189, score-0.204]

81 Again, we vary the number of visible points between 4, 7 and 11. [sent-190, score-0.089]

82 Furthermore, to avoid local maxima, we restart the algorithm at most 10 times using a randomly generated schedule to pass the messages. [sent-192, score-0.071]

83 Finally, when global invariance is used, we re-initialize γ up to 10 times. [sent-193, score-0.175]

84 On average, about 5 restarts for γ, 5 diﬀerent scheduling and 3 iterations of EM suﬃce to achieve a labeling with a likelihood comparable with the one of the ground truth labeling. [sent-195, score-0.061]

85 5 Discussion, Conclusions and Future Work Generalizing our model from decomposable [3] to loopy produced a gain in performance. [sent-196, score-0.236]

86 Further improvement would be expected when allowing larger cliques in the junction graph, at a considerable computational cost. [sent-197, score-0.172]

87 A more sensible improvement was obtained by adding a global variable modeling the centroid of the ﬁgure. [sent-198, score-0.159]

88 Taking [3] as a reference, there is about a 10x increase in computational cost when we either allow a loopy graph or account for translations with the centroid. [sent-199, score-0.25]

89 The local translation invariance model required the computation of relative positions within the same clique. [sent-202, score-0.274]

90 These could not be computed in the majority of cliques when a large number of body parts were occluded, even with the more accurate loopy graphical model. [sent-203, score-0.644]

91 Moreover, the introduction of the centroid variable is also valuable in light of a possible extension of the algorithm to multi-frame tracking. [sent-204, score-0.079]

92 In addition, the model parameters and structure are estimated under the hypothesis of no occlusion or clutter. [sent-206, score-0.132]

93 An algorithm that considers these two phenomena in the learning phase could likely achieve better results in realistic situations, when clutter and occlusion are signiﬁcant. [sent-207, score-0.169]

94 Finally, the step towards using displays directly obtained from gray-level image sequences remains a challenge that will be the goal of future work. [sent-208, score-0.066]

95 1 Acknowledgements We are very grateful to Max Welling, who ﬁrst proposed the idea of using LBP to solve for the optimal labelling in a 2001 Research Note, and who gave many useful suggestion. [sent-210, score-0.249]

96 Computer Vision and Pattern Recognition, vol II, pages 771-777, Kauai, Hawaii, December 2001. [sent-220, score-0.035]

97 Perona, “Monocular perception of biological motion clutter and partial occlusion”, Proc. [sent-228, score-0.207]

98 of 6th European Conferences on Computer Vision, vol II, pages 719-733, Dublin, Ireland, June/July, 2000. [sent-229, score-0.035]

99 Weiss, “On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs”, IEEE Transactions on Information Theory 47:2 pages 723-735. [sent-249, score-0.139]

100 Weiss, “Bethe free energy, Kikuchi approximations and belief propagation algorithms”, Advances in Neural Information Processing Systems 13, Vancouver, Canada, December 2000. [sent-256, score-0.139]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('fy', 0.693), ('labelling', 0.249), ('body', 0.221), ('loopy', 0.16), ('lbp', 0.143), ('display', 0.13), ('invariance', 0.121), ('parts', 0.12), ('detections', 0.111), ('clutter', 0.106), ('detection', 0.105), ('foreground', 0.096), ('goncalves', 0.096), ('johannson', 0.096), ('johansson', 0.096), ('cliques', 0.081), ('perona', 0.079), ('translation', 0.076), ('decomposable', 0.076), ('motion', 0.074), ('human', 0.073), ('propagation', 0.073), ('rp', 0.072), ('hypothesis', 0.069), ('belief', 0.066), ('junction', 0.065), ('visible', 0.065), ('occlusion', 0.063), ('graphical', 0.062), ('labeling', 0.061), ('background', 0.061), ('graph', 0.058), ('detected', 0.055), ('global', 0.054), ('un', 0.053), ('velocity', 0.052), ('song', 0.05), ('positions', 0.048), ('decomposability', 0.048), ('fanti', 0.048), ('fh', 0.048), ('replicating', 0.048), ('centroid', 0.047), ('frames', 0.045), ('di', 0.045), ('factorizes', 0.042), ('pmf', 0.042), ('restart', 0.042), ('december', 0.04), ('features', 0.04), ('scene', 0.04), ('erent', 0.038), ('displays', 0.038), ('lc', 0.038), ('pasadena', 0.038), ('triangulated', 0.038), ('joints', 0.035), ('score', 0.035), ('vol', 0.035), ('bic', 0.035), ('positioned', 0.035), ('maximizing', 0.034), ('su', 0.034), ('arg', 0.034), ('velocities', 0.033), ('variable', 0.032), ('compatible', 0.032), ('marginalization', 0.032), ('pdf', 0.032), ('decomposes', 0.032), ('occluded', 0.032), ('translations', 0.032), ('vancouver', 0.03), ('yi', 0.03), ('representing', 0.029), ('maximization', 0.029), ('labelled', 0.029), ('subscript', 0.029), ('local', 0.029), ('sequences', 0.028), ('maxima', 0.028), ('perception', 0.027), ('generalizing', 0.027), ('usa', 0.027), ('em', 0.027), ('improvement', 0.026), ('associated', 0.026), ('vertical', 0.026), ('vision', 0.025), ('lab', 0.025), ('detect', 0.025), ('person', 0.025), ('weiss', 0.025), ('conditional', 0.024), ('max', 0.024), ('tree', 0.024), ('det', 0.024), ('highest', 0.024), ('points', 0.024), ('ml', 0.023)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000002 22 nips-2003-An Improved Scheme for Detection and Labelling in Johansson Displays

Author: Claudio Fanti, Marzia Polito, Pietro Perona

2 0.19014984 35 nips-2003-Attractive People: Assembling Loose-Limbed Models using Non-parametric Belief Propagation

Author: Leonid Sigal, Michael Isard, Benjamin H. Sigelman, Michael J. Black

Abstract: The detection and pose estimation of people in images and video is made challenging by the variability of human appearance, the complexity of natural scenes, and the high dimensionality of articulated body models. To cope with these problems we represent the 3D human body as a graphical model in which the relationships between the body parts are represented by conditional probability distributions. We formulate the pose estimation problem as one of probabilistic inference over a graphical model where the random variables correspond to the individual limb parameters (position and orientation). Because the limbs are described by 6-dimensional vectors encoding pose in 3-space, discretization is impractical and the random variables in our model must be continuousvalued. To approximate belief propagation in such a graph we exploit a recently introduced generalization of the particle ﬁlter. This framework facilitates the automatic initialization of the body-model from low level cues and is robust to occlusion of body parts and scene clutter. 1

3 0.10327482 32 nips-2003-Approximate Expectation Maximization

Author: Tom Heskes, Onno Zoeter, Wim Wiegerinck

Abstract: We discuss the integration of the expectation-maximization (EM) algorithm for maximum likelihood learning of Bayesian networks with belief propagation algorithms for approximate inference. Specifically we propose to combine the outer-loop step of convergent belief propagation algorithms with the M-step of the EM algorithm. This then yields an approximate EM algorithm that is essentially still double loop, with the important advantage of an inner loop that is guaranteed to converge. Simulations illustrate the merits of such an approach. 1

4 0.086741678 74 nips-2003-Finding the M Most Probable Configurations using Loopy Belief Propagation

Author: Chen Yanover, Yair Weiss

Abstract: Loopy belief propagation (BP) has been successfully used in a number of diﬃcult graphical models to ﬁnd the most probable conﬁguration of the hidden variables. In applications ranging from protein folding to image analysis one would like to ﬁnd not just the best conﬁguration but rather the top M . While this problem has been solved using the junction tree formalism, in many real world problems the clique size in the junction tree is prohibitively large. In this work we address the problem of ﬁnding the M best conﬁgurations when exact inference is impossible. We start by developing a new exact inference algorithm for calculating the best conﬁgurations that uses only max-marginals. For approximate inference, we replace the max-marginals with the beliefs calculated using max-product BP and generalized BP. We show empirically that the algorithm can accurately and rapidly approximate the M best conﬁgurations in graphs with hundreds of variables. 1

5 0.084630258 189 nips-2003-Tree-structured Approximations by Expectation Propagation

Author: Yuan Qi, Tom Minka

Abstract: Approximation structure plays an important role in inference on loopy graphs. As a tractable structure, tree approximations have been utilized in the variational method of Ghahramani & Jordan (1997) and the sequential projection method of Frey et al. (2000). However, belief propagation represents each factor of the graph with a product of single-node messages. In this paper, belief propagation is extended to represent factors with tree approximations, by way of the expectation propagation framework. That is, each factor sends a “message” to all pairs of nodes in a tree structure. The result is more accurate inferences and more frequent convergence than ordinary belief propagation, at a lower cost than variational trees or double-loop algorithms. 1

6 0.083811834 80 nips-2003-Generalised Propagation for Fast Fourier Transforms with Partial or Missing Data

7 0.08326783 37 nips-2003-Automatic Annotation of Everyday Movements

8 0.077258006 133 nips-2003-Mutual Boosting for Contextual Inference

9 0.074799187 69 nips-2003-Factorization with Uncertainty and Missing Data: Exploiting Temporal Coherence

10 0.067227386 29 nips-2003-Applying Metric-Trees to Belief-Point POMDPs

11 0.064071067 192 nips-2003-Using the Forest to See the Trees: A Graphical Model Relating Features, Objects, and Scenes

12 0.064041764 124 nips-2003-Max-Margin Markov Networks

13 0.061472386 154 nips-2003-Perception of the Structure of the Physical World Using Unknown Multimodal Sensors and Effectors

14 0.060874715 169 nips-2003-Sample Propagation

15 0.060131904 109 nips-2003-Learning a Rare Event Detection Cascade by Direct Feature Selection

16 0.055595472 152 nips-2003-Pairwise Clustering and Graphical Models

17 0.05433568 30 nips-2003-Approximability of Probability Distributions

18 0.050941087 174 nips-2003-Semidefinite Relaxations for Approximate Inference on Graphs with Cycles

19 0.050814997 50 nips-2003-Denoising and Untangling Graphs Using Degree Priors

20 0.049202729 7 nips-2003-A Functional Architecture for Motion Pattern Processing in MSTd

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.177), (1, -0.033), (2, -0.014), (3, 0.085), (4, -0.088), (5, -0.219), (6, 0.084), (7, 0.024), (8, 0.03), (9, -0.036), (10, -0.039), (11, 0.101), (12, 0.013), (13, 0.005), (14, -0.002), (15, -0.027), (16, 0.056), (17, -0.043), (18, 0.008), (19, -0.045), (20, 0.026), (21, -0.074), (22, -0.004), (23, 0.021), (24, 0.042), (25, -0.164), (26, 0.053), (27, 0.053), (28, -0.013), (29, 0.005), (30, 0.026), (31, 0.054), (32, -0.185), (33, -0.041), (34, 0.002), (35, -0.097), (36, 0.141), (37, -0.029), (38, -0.028), (39, -0.028), (40, -0.051), (41, 0.027), (42, 0.068), (43, -0.091), (44, -0.109), (45, -0.115), (46, 0.139), (47, -0.071), (48, -0.023), (49, -0.048)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.94141954 22 nips-2003-An Improved Scheme for Detection and Labelling in Johansson Displays

Author: Claudio Fanti, Marzia Polito, Pietro Perona

2 0.79308683 35 nips-2003-Attractive People: Assembling Loose-Limbed Models using Non-parametric Belief Propagation

Author: Leonid Sigal, Michael Isard, Benjamin H. Sigelman, Michael J. Black

3 0.5060817 50 nips-2003-Denoising and Untangling Graphs Using Degree Priors

Author: Quaid D. Morris, Brendan J. Frey

Abstract: This paper addresses the problem of untangling hidden graphs from a set of noisy detections of undirected edges. We present a model of the generation of the observed graph that includes degree-based structure priors on the hidden graphs. Exact inference in the model is intractable; we present an eﬃcient approximate inference algorithm to compute edge appearance posteriors. We evaluate our model and algorithm on a biological graph inference problem. 1 Introduction and motivation The inference of hidden graphs from noisy edge appearance data is an important problem with obvious practical application. For example, biologists are currently building networks of all the physical protein-protein interactions (PPI) that occur in particular organisms. The importance of this enterprise is commensurate with its scale: a completed network would be as valuable as a completed genome sequence, and because each organism contains thousands of diﬀerent types of proteins, there are millions of possible types of interactions. However, scalable experimental methods for detecting interactions are noisy, generating many false detections. Motivated by this application, we formulate the general problem of inferring hidden graphs as probabilistic inference in a graphical model, and we introduce an eﬃcient algorithm that approximates the posterior probability that an edge is present. In our model, a set of hidden, constituent graphs are combined to generate the observed graph. Each hidden graph is independently sampled from a prior on graph structure. The combination mechanism acts independently on each edge but can be either stochastic or deterministic. Figure 1 shows an example of our generative model. Typically one of the hidden graphs represents the graph of interest (the true graph), the others represent diﬀerent types of observation noise. Independent edge noise may also be added by the combination mechanism. We use probabilistic inference to compute a likely decomposition of the observed graph into its constituent parts. This process is deemed “untangling”. We use the term “denoising” to refer to the special case where the edge noise is independent. In denoising there is a single hidden graph, the true graph, and all edge noise in the observed graph is due E1 1 eij E2 i 2 eij j xij i j i j X Figure 1: Illustrative generative model example. Figure shows an example where an observed graph, X, is a noisy composition of two constituent graphs, E 1 and E 2 . All graphs share the same vertex set, so each can be represented by a symmetric matrix of random binary variables (i.e., an adjacency matrix). This generative model is designed to solve a toy counter-espionage problem. The vertices represent suspects and each edge in X represents an observed call between two suspects. The graph X reﬂects zero or more spy rings (represented by E 1 ), telemarketing calls (represented by E 2 ), social calls (independent edge noise), and lost call records (more independent edge noise). The task is to locate any spy rings hidden in X. We model the distribution of spy ring graphs using a prior, P (E 1 ), that has support only on graphs where all vertices have degree of either 2 (i.e., are in the ring) or 0 (i.e., are not). Graphs of telemarketing call patterns are represented using a prior, P (E 2 ), under which all nodes have degrees of > 3 (i.e., are telemarketers), 1 (i.e., are telemarketees), or 0 (i.e., are neither). The displayed hidden graphs are one likely untangling of X. to the combination mechanism. Prior distributions over graphs can be speciﬁed in various ways, but our choice is motivated by problems we want to solve, and by a view to deriving an eﬃcient inference algorithm. One compact representation of a distribution over graphs consists of specifying a distribution over vertex degrees, and assuming that graphs that have the same vertex degrees are equiprobable. Such a prior can model quite rich distributions over graphs. These degree-based structure priors are natural representions of graph structure; many classes of real-world networks have a characteristic functional form associated with their degree distributions [1], and sometimes this form can be predicted using knowledge about the domain (see, e.g., [2]) or detected empirically (see, e.g., [3, 4]). As such, our model incorporates degree-based structure priors. Though exact inference in our model is intractable in general, we present an eﬃcient algorithm for approximate inference for arbitrary degree distributions. We evaluate our model and algorithm using the real-world example of untangling yeast proteinprotein interaction networks. 2 A model of noisy and tangled graphs For degree-based structure priors, inference consists of searching over vertex degrees and edge instantiations, while comparing each edge with its noisy observation and enforcing the constraint that the number of edges connected to every vertex must equal the degree of the vertex. Our formulation of the problem in this way is inspired by the success of the sum-product algorithm (loopy belief propagation) for solving similar formulations of problems in error-correcting decoding [6, 7], phase unwrapping [8], and random satisﬁability [9]. For example, in error-correcting decoding, inference consists of searching over conﬁgurations of codeword bits, while comparing each bit with its noisy observation and enforcing parity-check constraints on subsets of bits [10]. For a graph on a set of N vertices, eij is a variable that indicates the presence of an edge connecting vertices i and j: eij = 1 if there is an edge, and eij = 0 otherwise. We assume the vertex set is ﬁxed, so each graph is speciﬁed by an adjacency matrix, E = {eij }N . The degree of vertex i is denoted by di and the i,j=1 degree set by D = {di }N . The observations are given by a noisy adjacency matrix, i=1 X = {xij }N . Generally, edges can be directed, but in this paper we focus on i,j=1 undirected graphs, so eij = eji and xij = xji . Assuming the observation noise is independent for diﬀerent edges, the joint distribution is P (X, E, D) = P (X|E)P (E, D) = P (xij |eij ) P (E, D). j≥i P (xij |eij ) models the edge observation noise. We use an undirected model for the joint distribution over edges and degrees, P (E, D), where the prior distribution over di is determined by a non-negative potential fi (di ). Assuming graphs that have the same vertex degrees are equiprobable, we have N eij ) , fi (di )I(di , P (E, D) ∝ i j=1 where I(a, b) = 1 if a = b, and I(a, b) = 0 if a = b. The term I(di , j eij ) ensures that the number of edges connected to vertex i is equal to di . It is straightforward to show that the marginal distribution over di is P (di ) ∝ fi (di ) D\di nD j=i fj (dj ) , where nD is the number of graphs with degrees D and the sum is over all degree variables except di . The potentials, fi , can be estimated from a given degree prior using Markov chain Monte Carlo; or, as an approximation, they can be set to an empirical degree distribution obtained from noise-free graphs. Fig 2a shows the factor graph [11] for the above model. Each ﬁlled square corresponds to a term in the factorization of the joint distribution and the square is connected to all variables on which the term depends. Factor graphs are graphical models that unify the properties of Bayesian networks and Markov random ﬁelds [12]. Many inference algorithms, including the sum-product algorithm (a.k.a. loopy belief propagation), are more easily derived using factor graphs than Bayesian networks or Markov random ﬁelds. We describe the sum-product algorithm for our model in section 3. (a) I(d ,e + e +e +e 4 14 24 34 44 d1 e11 e12 e14 4 d3 d2 e13 f 4(d ) e22 e23 e24 (b) ) d1 d4 e33 e34 e1 e44 11 x11 x11 x12 x13 x14 x22 x23 x24 x33 d1 1 x34 x44 e2 11 e1 12 x12 e2 12 d1 2 e1 13 e1 e2 13 e1 14 x13 e1 22 x14 e2 14 d1 3 23 x22 e2 22 x23 e2 23 4 e1 e1 24 e2 24 e1 33 x24 34 x33 e2 33 x34 e2 34 e1 44 x44 e2 44 P( x44 | e44 ) (c) d4 s41 e14 e24 d2 1 d4 e34 e44 e14 s42 e24 s43 e34 d2 2 d2 3 d2 4 s44 P( x e44 44 1 ,e 2 ) 44 44 |e Figure 2: (a) A factor graph that describes a distribution over graphs with vertex degrees di , binary edge indicator variables eij , and noisy edge observations xij . The indicator function I(di , j eij ) enforces the constraint that the sum of the binary edge indicator variables for vertex i must equal the degree of vertex i. (b) A factor graph that explains noisy observed edges as a combination of two constituent graphs, with edge indicator variables e 1 and e2 . ij ij (c) The constraint I(di , j eij ) can be implemented using a chain with state variables, which leads to an exponentially faster message-passing algorithm. 2.1 Combining multiple graphs The above model is suitable when we want to infer a graph that matches a degree prior, assuming the edge observation noise is independent. A more challenging goal, with practical application, is to infer multiple hidden graphs that combine to explain the observed edge data. In section 4, we show how priors over multiple hidden graphs can be be used to infer protein-protein interactions. When there are H hidden graphs, each constituent graph is speciﬁed by a set of edges on the same set of N common vertices. For the degree variables and edge variables, we use a superscript to indicate which hidden graph the variable is used to describe. Assuming the graphs are independent, the joint distribution over the observed edge data X, and the edge variables and degree variables for the hidden graphs, E 1 , D1 , . . . , E H , DH , is H P (X, E 1 , D1 , . . . , E H , DH ) = P (xij |e1 , . . . , eH ) ij ij j≥i P (E h , Dh ), (1) h=1 where for each hidden graph, P (E h , Dh ) is modeled as described above. Here, the likelihood P (xij |e1 , . . . , eH ) describes how the edges in the hidden graphs combine ij ij to model the observed edge. Figure 2b shows the factor graph for this model. 3 Probabilistic inference of constituent graphs Exact probabilistic inference in the above models is intractable, here we introduce an approximate inference algorithm that consists of applying the sum-product algorithm, while ignoring cycles in the factor graph. Although the sum-product algorithm has been used to obtain excellent results on several problems [6, 7, 13, 14, 8, 9], we have found that the algorithm works best when the model consists of uncertain observations of variables that are subject to a large number of hard constraints. Thus the formulation of the model described above. Conceptually, our inference algorithm is a straight-forward application of the sumproduct algorithm, c.f. [15], where messages are passed along edges in the factor graph iteratively, and then combined at variables to obtain estimates of posterior probabilities. However, direct implementation of the message-passing updates will lead to an intractable algorithm. In particular, direct implementation of the update for the message sent from function I(di , j eij ) to edge variable eik takes a number of scalar operations that is exponential in the number of vertices. Fortunately there exists a more eﬃcient way to compute these messages. 3.1 Eﬃciently summing over edge conﬁgurations The function I(di , j eij ) ensures that the number of edges connected to vertex i is equal to di . Passing messages through this function requires summing over all edge conﬁgurations that correspond to each possible degree, di , and summing over di . Speciﬁcally, the message, µIi →eik (eik ), sent from function I(di , j eij ) to edge variable eik is given by I(di , di {eij | j=1,...,N, j=k} eij ) j µeij →Ii (eij ) , j=k where µeij →Ii (eij ) is the message sent from eij to function I(di , j eij ). The sum over {eij | j = 1, . . . , N, j = k} contains 2N −1 terms, so direct computation is intractable. However, for a maximum degree of dmax , all messages departing from the function I(di , j eij ) can be computed using order dmax N binary scalar operations, by introducing integer state variables sij . We deﬁne sij = n≤j ein and note that, by recursion, sij = sij−1 + eij , where si0 = 0 and 0 ≤ sij ≤ dmax . This recursive expression enables us to write the high-complexity constraint as the sum of a product of low-complexity constraints, N I(di , eij ) = j I(si1 , ei1 ) {sij | j=1,...,N } I(sij , sij−1 + eij ) I(di , siN ). j=2 This summation can be performed using the forward-backward algorithm. In the factor graph, the summation can be implemented by replacing the function I(di , j eij ) with a chain of lower-complexity functions, connected as shown in Fig. 2c. The function vertex (ﬁlled square) on the far left corresponds to I(si1 , ei1 ) and the function vertex in the upper right corresponds to I(di , siN ). So, messages can be passed through each constraint function I(di , j eij ) in an eﬃcient manner, by performing a single forward-backward pass in the corresponding chain. 4 Results We evaluate our model using yeast protein-protein interaction (PPI) data compiled by [16]. These data include eight sets of putative, but noisy, interactions derived from various sources, and one gold-standard set of interactions detected by reliable experiments. Using the ∼ 6300 yeast proteins as vertices, we represent the eight sets of putative m interactions using adjacency matrices {Y m }8 m=1 where yij = 1 if and only if putative interaction dataset m contains an interaction between proteins i and j. We similarly use Y gold to represent the gold-standard interactions. m We construct an observed graph, X, by setting xij = maxm yij for all i and j, thus the observed edge set is the union of all the putative edge sets. We test our model (a) (b) 40 0 untangling baseline random empirical potential posterior −2 30 log Pr true positives (%) 50 20 10 −4 −6 −8 0 0 5 10 −10 0 false positives (%) 10 20 30 degree (# of nodes) Figure 3: Protein-protein interaction network untangling results. (a) ROC curves measuring performance of predicting e1 when xij = 1. (b) Degree distributions. Compares the empirical ij degree distribution of the test set subgraph of E 1 to the degree potential f 1 estimated on the ˆ ij training set subgraph of E 1 and to the distribution of di = j pij where pij = P (e1 = 1|X) is estimated by untangling. on the task of discerning which of the edges in X are also in Y gold . We formalize this problem as that of decomposing X into two constituent graphs E 1 and E 2 , the gold true and the noise graphs respectively, such that e1 = xij yij and e2 = xij − e1 . ij ij ij We use a training set to ﬁt our model parameters and then measure task performance on a test set. The training set contains a randomly selected half of the ∼ 6300 yeast proteins, and the subgraphs of E 1 , E 2 , and X restricted to those vertices. The test contains the other half of the proteins and the corresponding subgraphs. Note that interactions connecting test set proteins to training set proteins (and vice versa) are ignored. We ﬁt three sets of parameters: a set of Naive Bayes parameters that deﬁne a set of edge-speciﬁc likelihood functions, Pij (xij |e1 , e2 ), one degree potential, f 1 , which ij ij is the same for every vertex in E1 and deﬁnes the prior P (E 1 ), and a second, f 2 , that similarly deﬁnes the prior P (E 2 ). The likelihood functions, Pij , are used to both assign likelihoods and enforce problem constraints. Given our problem deﬁnition, if xij = 0 then e1 = e2 = 0, ij ij otherwise xij = 1 and e1 = 1 − e2 . We enforce the former constraint by setij ij ting Pij (xij = 0|e1 , e2 ) = (1 − e1 )(1 − e2 ), and the latter by setting Pij (xij = ij ij ij ij 1|e1 , e2 ) = 0 whenever e1 = e2 . This construction of Pij simpliﬁes the calculation ij ij ij ij of the µPij →eh messages and improves the computational eﬃciency of inference beij cause when xij = 0, we need never update messages to and from variables e1 and ij e2 . We complete the speciﬁcation of Pij (xij = 1|e1 , e2 ) as follows: ij ij ij ym Pij (xij = 1|e1 , e2 ) ij ij = m ij θm (1 − θm )1−yij , if e1 = 1 and e2 = 0, ij ij ym m ij ψm (1 − ψm )1−yij , if e1 = 0 and e2 = 1. ij ij where {θm } and {ψm } are naive Bayes parameters, θm = i,j m yij e1 / ij i,j e1 and ij ψm = i,j m yij e2 / ij i,j e2 , respectively. ij The degree potentials f 1 (d) and f 2 (d) are kernel density estimates ﬁt to the degree distribution of the training set subgraphs of E 1 and E 2 , respectively. We use Gaussian kernels and set the width parameter (standard deviation) σ using leaveone-out cross-validation to maximize the total log density of the held-out datapoints. Each datapoint is the degree of a single vertex. Both degree potentials closely followed the training set empirical degree distributions. Untangling was done on the test set subgraph of X. We initially set the µ Pij →e1 ij messages equal to the likelihood function Pij and we randomly initialized the 1 µIj →e1 messages with samples from a normal distribution with mean 0 and variij ance 0.01. We then performed 40 iterations of the following message update order: 2 2 1 1 µe1 →Ij , µIj →e1 , µe1 →Pij , µPij →e2 , µe2 →Ij , µIj →e2 , µe2 →Pij , µPij →e1 . ij ij ij ij ij ij ij ij We evaluated our untangling algorithm using an ROC curve by comparing the actual ˆ test set subgraph of E 1 to posterior marginal probabilities,P (e1 = 1|X), estimated ij by our sum-product algorithm. Note that because the true interaction network is sparse (less than 0.2% of the 1.8 × 107 possible interactions are likely present [16]) and, in this case, true positive predictions are of greater biological interest than true negative predictions, we focus on low false positive rate portions of the ROC curve. Figure 3a compares the performance of a classiﬁer for e1 based on thresholding ij ˆ P (eij = 1|X) to a baseline method based on thresholding the likelihood functions, Pij (xij = 1|e1 = 1, e2 = 0). Note because e1 = 0 whenever xij = 0, we exclude ij ij ij the xij = 0 cases from our performance evaluation. The ROC curve shows that for the same low false positive rate, untangling produces 50% − 100% more true positives than the baseline method. Figure 3b shows that the degree potential, the true degree distribution, and the predicted degree distribution are all comparable. The slight overprediction of the true degree distribution may result because the degree potential f 1 that deﬁnes P (E 1 ) is not equal to the expected degree distribution of graphs sampled from the distribution P (E 1 ). 5 Summary and Related Work Related work includes other algorithms for structure-based graph denoising [17, 18]. These algorithms use structural properties of the observed graph to score edges and rely on the true graph having a surprisingly large number of three (or four) edge cycles compared to the noise graph. In contrast, we place graph generation in a probabilistic framework; our algorithm computes structural ﬁt in the hidden graph, where this computation is not aﬀected by the noise graph(s); and we allow for multiple sources of observation noise, each with its own structural properties. After submitting this paper to the NIPS conference, we discovered [19], in which a degree-based graph structure prior is used to denoise (but not untangle) observed graphs. This paper addresses denoising in directed graphs as well as undirected graphs, however, the prior that they use is not amenable to deriving an eﬃcient sumproduct algorithm. Instead, they use Markov Chain Monte Carlo to do approximate inference in a hidden graph containing 40 vertices. It is not clear how well this approach scales to the ∼ 3000 vertex graphs that we are using. In summary, the contributions of the work described in this paper include: a general formulation of the problem of graph untangling as inference in a factor graph; an eﬃcient approximate inference algorithm for a rich class of degree-based structure priors; and a set of reliability scores (i.e., edge posteriors) for interactions from a current version of the yeast protein-protein interaction network. References [1] A L Barabasi and R Albert. Emergence of scaling in random networks. Science, 286(5439), October 1999. [2] A Rzhetsky and S M Gomez. Birth of scale-free molecular networks and the number of distinct dna and protein domains per genome. Bioinformatics, pages 988–96, 2001. [3] M Faloutsos, P Faloutsos, and C Faloutsos. On power-law relationships of the Internet topology. Computer Communications Review, 29, 1999. [4] Hawoong Jeong, B Tombor, R´ka Albert, Z N Oltvai, and Albert-L´szl´ Barab´si. e a o a The large-scale organization of metabolic networks. Nature, 407, October 2000. [5] J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Mateo CA., 1988. [6] D. J. C. MacKay and R. M. Neal. Near Shannon limit performance of low density parity check codes. Electronics Letters, 32(18):1645–1646, August 1996. Reprinted in Electronics Letters, vol. 33, March 1997, 457–458. [7] B. J. Frey and F. R. Kschischang. Probability propagation and iterative decoding. In Proceedings of the 1996 Allerton Conference on Communication, Control and Computing, 1996. [8] B. J. Frey, R. Koetter, and N. Petrovic. Very loopy belief propagation for unwrapping phase images. In 2001 Conference on Advances in Neural Information Processing Systems, Volume 14. MIT Press, 2002. [9] M. M´zard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of random e satisﬁability problems. Science, 297:812–815, 2002. [10] B. J. Frey and D. J. C. MacKay. Trellis-constrained codes. In Proceedings of the 35 th Allerton Conference on Communication, Control and Computing 1997, 1998. [11] F. R. Kschischang, B. J. Frey, and H.-A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, Special Issue on Codes on Graphs and Iterative Algorithms, 47(2):498–519, February 2001. [12] B. J. Frey. Factor graphs: A uniﬁcation of directed and undirected graphical models. University of Toronto Technical Report PSI-2003-02, 2003. [13] Kevin P. Murphy, Yair Weiss, and Michael I. Jordan. Loopy belief propagation for approximate inference: An empirical study. In Uncertainty in Artiﬁcial Intelligence 1999. Stockholm, Sweden, 1999. [14] W. Freeman and E. Pasztor. Learning low-level vision. In Proceedings of the International Conference on Computer Vision, pages 1182–1189, 1999. [15] M. I. Jordan. An Inroduction to Learning in Graphical Models. 2004. In preparation. [16] C von Mering et al. Comparative assessment of large-scale data sets of protein-protein interactions. Nature, 2002. [17] R Saito, H Suzuki, and Y Hayashizaki. Construction of reliable protein-protein interaction networks with a new interaction generality measure. Bioinformatics, pages 756–63, 2003. [18] D S Goldberg and F P Roth. Assessing experimentally derived interactions in a small world. Proceedings of the National Academy of Science, 2003. [19] S M Gomez and A Rzhetsky. Towards the prediction of complete protein–protein interaction networks. In Paciﬁc Symposium on Biocomputing, pages 413–24, 2002.

4 0.50164366 37 nips-2003-Automatic Annotation of Everyday Movements

Author: Deva Ramanan, David A. Forsyth

Abstract: This paper describes a system that can annotate a video sequence with: a description of the appearance of each actor; when the actor is in view; and a representation of the actor’s activity while in view. The system does not require a ﬁxed background, and is automatic. The system works by (1) tracking people in 2D and then, using an annotated motion capture dataset, (2) synthesizing an annotated 3D motion sequence matching the 2D tracks. The 3D motion capture data is manually annotated off-line using a class structure that describes everyday motions and allows motion annotations to be composed — one may jump while running, for example. Descriptions computed from video of real motions show that the method is accurate.

5 0.45292482 74 nips-2003-Finding the M Most Probable Configurations using Loopy Belief Propagation

Author: Chen Yanover, Yair Weiss

6 0.43732405 30 nips-2003-Approximability of Probability Distributions

7 0.43091553 32 nips-2003-Approximate Expectation Maximization

8 0.39666721 80 nips-2003-Generalised Propagation for Fast Fourier Transforms with Partial or Missing Data

9 0.38828111 169 nips-2003-Sample Propagation

10 0.3815091 154 nips-2003-Perception of the Structure of the Physical World Using Unknown Multimodal Sensors and Effectors

11 0.36570793 69 nips-2003-Factorization with Uncertainty and Missing Data: Exploiting Temporal Coherence

12 0.35313338 168 nips-2003-Salient Boundary Detection using Ratio Contour

13 0.31472564 189 nips-2003-Tree-structured Approximations by Expectation Propagation

14 0.31225315 192 nips-2003-Using the Forest to See the Trees: A Graphical Model Relating Features, Objects, and Scenes

15 0.30787155 133 nips-2003-Mutual Boosting for Contextual Inference

16 0.28432617 75 nips-2003-From Algorithmic to Subjective Randomness

17 0.2799257 118 nips-2003-Link Prediction in Relational Data

18 0.27944896 43 nips-2003-Bounded Invariance and the Formation of Place Fields

19 0.27898705 124 nips-2003-Max-Margin Markov Networks

20 0.27565217 7 nips-2003-A Functional Architecture for Motion Pattern Processing in MSTd

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.394), (11, 0.048), (29, 0.012), (30, 0.01), (35, 0.064), (53, 0.087), (71, 0.058), (76, 0.053), (85, 0.06), (91, 0.094), (99, 0.019)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.97005594 29 nips-2003-Applying Metric-Trees to Belief-Point POMDPs

Author: Joelle Pineau, Geoffrey J. Gordon, Sebastian Thrun

Abstract: Recent developments in grid-based and point-based approximation algorithms for POMDPs have greatly improved the tractability of POMDP planning. These approaches operate on sets of belief points by individually learning a value function for each point. In reality, belief points exist in a highly-structured metric simplex, but current POMDP algorithms do not exploit this property. This paper presents a new metric-tree algorithm which can be used in the context of POMDP planning to sort belief points spatially, and then perform fast value function updates over groups of points. We present results showing that this approach can reduce computation in point-based POMDP algorithms for a wide range of problems. 1

2 0.96385729 171 nips-2003-Semi-Definite Programming by Perceptron Learning

Author: Thore Graepel, Ralf Herbrich, Andriy Kharechko, John S. Shawe-taylor

Abstract: We present a modiﬁed version of the perceptron learning algorithm (PLA) which solves semideﬁnite programs (SDPs) in polynomial time. The algorithm is based on the following three observations: (i) Semideﬁnite programs are linear programs with inﬁnitely many (linear) constraints; (ii) every linear program can be solved by a sequence of constraint satisfaction problems with linear constraints; (iii) in general, the perceptron learning algorithm solves a constraint satisfaction problem with linear constraints in ﬁnitely many updates. Combining the PLA with a probabilistic rescaling algorithm (which, on average, increases the size of the feasable region) results in a probabilistic algorithm for solving SDPs that runs in polynomial time. We present preliminary results which demonstrate that the algorithm works, but is not competitive with state-of-the-art interior point methods. 1

3 0.95979989 53 nips-2003-Discriminating Deformable Shape Classes

Author: Salvador Ruiz-correa, Linda G. Shapiro, Marina Meila, Gabriel Berson

Abstract: We present and empirically test a novel approach for categorizing 3-D free form object shapes represented by range data . In contrast to traditional surface-signature based systems that use alignment to match speciﬁc objects, we adapted the newly introduced symbolic-signature representation to classify deformable shapes [10]. Our approach constructs an abstract description of shape classes using an ensemble of classiﬁers that learn object class parts and their corresponding geometrical relationships from a set of numeric and symbolic descriptors. We used our classiﬁcation engine in a series of large scale discrimination experiments on two well-deﬁned classes that share many common distinctive features. The experimental results suggest that our method outperforms traditional numeric signature-based methodologies. 1 1

same-paper 4 0.91502821 22 nips-2003-An Improved Scheme for Detection and Labelling in Johansson Displays

Author: Claudio Fanti, Marzia Polito, Pietro Perona

5 0.73260784 42 nips-2003-Bounded Finite State Controllers

Author: Pascal Poupart, Craig Boutilier

Abstract: We describe a new approximation algorithm for solving partially observable MDPs. Our bounded policy iteration approach searches through the space of bounded-size, stochastic ﬁnite state controllers, combining several advantages of gradient ascent (efﬁciency, search through restricted controller space) and policy iteration (less vulnerability to local optima).

6 0.70496446 33 nips-2003-Approximate Planning in POMDPs with Macro-Actions

7 0.65196681 116 nips-2003-Linear Program Approximations for Factored Continuous-State Markov Decision Processes

8 0.64748335 113 nips-2003-Learning with Local and Global Consistency

9 0.63767028 78 nips-2003-Gaussian Processes in Reinforcement Learning

10 0.63262004 106 nips-2003-Learning Non-Rigid 3D Shape from 2D Motion

11 0.62553859 81 nips-2003-Geometric Analysis of Constrained Curves

12 0.61380476 6 nips-2003-A Fast Multi-Resolution Method for Detection of Significant Spatial Disease Clusters

13 0.60786957 12 nips-2003-A Model for Learning the Semantics of Pictures

14 0.60503721 48 nips-2003-Convex Methods for Transduction

15 0.60503429 138 nips-2003-Non-linear CCA and PCA by Alignment of Local Models

16 0.60330099 172 nips-2003-Semi-Supervised Learning with Trees

17 0.6014908 80 nips-2003-Generalised Propagation for Fast Fourier Transforms with Partial or Missing Data

18 0.60056078 147 nips-2003-Online Learning via Global Feedback for Phrase Recognition

19 0.60023642 158 nips-2003-Policy Search by Dynamic Programming

20 0.59867305 34 nips-2003-Approximate Policy Iteration with a Policy Language Bias