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

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

Source: pdf

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

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu 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. [sent-10, score-0.924]

2 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. [sent-11, score-1.257]

3 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). [sent-12, score-0.583]

4 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. [sent-13, score-0.36]

5 To approximate belief propagation in such a graph we exploit a recently introduced generalization of the particle ﬁlter. [sent-14, score-0.443]

6 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. [sent-15, score-0.701]

7 1 Introduction Recent approaches to person detection and tracking exploit articulated body models in which the body is viewed as a kinematic tree in 2D [14], 2. [sent-16, score-1.468]

8 These schemes have been effective for tracking people wearing increasingly complex clothing in increasingly complex cluttered backgrounds [21]. [sent-19, score-0.256]

9 Hierarchical body models lead to “top-down” search algorithms that make it difﬁcult to incorporate “bottom-up” information about salient body parts available from special-purpose detectors (e. [sent-21, score-1.148]

10 As a result, few, if any, of the above methods deal with the problem of automatic initialization of the body model. [sent-24, score-0.602]

11 To address these problems, we propose a “loose-limbed” body model in which the limbs are not rigidly connected but are rather “attracted” to each other (hence the title “Attractive People”). [sent-27, score-0.66]

12 Instead of representing the body as a single 33-dimensional kinematic tree, each limb is treated quasi-independently with soft constraints between the position and orientation of adjacent parts. [sent-28, score-0.987]

13 The model resembles a Push Puppet toy which has elastic connections between the limbs (Figure 1a). [sent-29, score-0.248]

14 This type of model is not new for ﬁnding or tracking articulated objects and dates back at least to Fischler and Elschlager’s pictorial structures [9]. [sent-30, score-0.377]

15 The work described here, like the previous work above, exploits this notion of ﬂexible “spring”-like constraints [8] deﬁned over individually modeled body parts [11, 17, 23], though we extend the approach to locate the parts in 3-space rather than the 2-dimensional image plane. [sent-34, score-0.813]

16 The body is treated as a graphical model [13], where each node in the graph corresponds to an independently parameterized body part. [sent-35, score-1.092]

17 The spatial constraints between body parts are deﬁned as directed edges in the graph. [sent-36, score-0.596]

18 Each node in the graph also has a corresponding image likelihood function that models the probability of observing various image measurements conditioned on the position and orientation of the part. [sent-38, score-0.465]

19 Person detection (or tracking) then exploits belief propagation [24] to estimate the belief distribution over the parameters which takes into account the constraints and the observations. [sent-39, score-0.498]

20 This graphical inference problem is carried out using a recently proposed method that allows the parameters of the individual parts to be modeled using continuous-valued random variables rather than the discrete variables used in previous approaches. [sent-40, score-0.287]

21 This is vital in our problem setting, since the discretization used in [8] is impractical once the body is modeled in 3-space. [sent-41, score-0.494]

22 The algorithm extends the ﬂexibility of particle ﬁlters to the problem of belief propagation and, in our context, allows the model to cope with general constraints between limbs, permits realistic appearance models, and provides resilience to clutter. [sent-45, score-0.479]

23 We develop the loose-limbed model in detail, formulate the constraints between limbs using mixture models, and outline the inference method. [sent-46, score-0.381]

24 Using images from calibrated cameras we illustrate the inference of 3D human pose with belief propagation. [sent-47, score-0.501]

25 We simulate noisy, bottom-up, feature detectors for the limbs and show how the inference method can resolve ambiguities and cope with clutter. [sent-48, score-0.455]

26 While our focus here is on static detection and pose estimation, the body model can be extended in time to include temporal constraints on the limb motion; we save tracking for future work. [sent-49, score-1.137]

27 Nodes represent limbs and arrows represent conditional dependencies between limbs. [sent-52, score-0.292]

28 2 A self-assembling body model The body is represented by a graphical model in which each graph node corresponds to a body part (upper leg, torso, etc. [sent-54, score-1.625]

29 Each part has an associated conﬁguration vector deﬁning the part’s position and orientation in 3-space. [sent-56, score-0.211]

30 Placing each part in a global coordinate frame enables the part detectors to operate independently while the full body is assembled by inference over the graphical model. [sent-57, score-0.944]

31 Edges in the graphical model correspond to spatial and angular relationships between adjacent body parts, as illustrated in Figure 1b. [sent-58, score-0.58]

32 As is standard for graphical models we assume the variables in a node are conditionally independent of those in non-neighboring nodes given the values of the node’s neighbors1 . [sent-59, score-0.145]

33 The ﬁxed parameters Φi = (li , wi , wi , op , od ) correspond respectively i i to the part length, width at the proximal and distal ends and the offset of the proximal and distal joints along the axis of the limb as shown in Figure 1c. [sent-61, score-0.886]

34 The estimated parameters XT = (xT , ΘT ) represent the conﬁguration of the part i in a global coordinate frame i i i where xi ∈ R3 and Θi ∈ SO(3) are the 3D position of the proximal joint and the angular orientation of the part respectively. [sent-62, score-0.568]

35 Each directed edge between parts i and j has an associated conditional distribution ψij (Xi , Xj ) that encodes the compatibility between pairs of part conﬁgurations; that is, it models the probability of conﬁguration Xj of part j conditioned on the Xi of part i. [sent-64, score-0.5]

36 For notational convenience we deﬁne an ordering on body parts going from the torso out towards the extremities and refer to conditionals that go along this ordering as “forward” conditionals. [sent-65, score-0.885]

37 Conversely, the conditionals that go from the extremities towards the torso are referred to as “backward” conditionals. [sent-66, score-0.333]

38 These intuitively correspond to kinematic and inverse-kinematic constraints respectively. [sent-67, score-0.12]

39 Conditional distributions were constructed by hand to capture the physical constraints of the joints and limbs of the human body. [sent-68, score-0.349]

40 A typical range of motion information for the various joints is approximated by the model. [sent-69, score-0.183]

41 In general, these conditionals can, and should, be learned from motion capture data. [sent-70, score-0.203]

42 Because we have chosen the local coordinate frame to be centered at the proximal joint of 1 Self-occlusion and self-intersection violate this assumption. [sent-71, score-0.173]

43 (a) (b) Figure 2: (a) For the forwards conditional the location of part i tightly constrains the proximal joint of part j (light dots) while the position of the distal joint (dark dots) lies along an arc around the principal axis of rotation, approximated by a Gaussian mixture. [sent-74, score-0.603]

44 (b) For the backwards conditional part i constrains the distal joint of part j (dark dots), so the proximal joint position (light dots) lies in a non-Gaussian volume again approximated using a mixture distribution. [sent-75, score-0.628]

45 a part, the forward and backward conditionals are not symmetric. [sent-76, score-0.21]

46 These functions allow the mean and variance of the mixture components to be function of the limb pose X i . [sent-80, score-0.501]

47 Figure 2a and b illustrate the forward and backward conditionals respectively. [sent-82, score-0.21]

48 For the forward case, we examine the distribution of calf conﬁgurations conditioned on the thigh. [sent-83, score-0.115]

49 To illustrate the conditional distribution we sample from it and plot the endpoints of the sampled limb conﬁgurations. [sent-84, score-0.368]

50 In the forward direction the conditional distribution over x j (the position of the proximal joint of part j) is well approximated by a Gaussian so each mixture component has the same mean and covariance for xj . [sent-85, score-0.594]

51 This distribution over rotations is modeled by giving each mixture component a different mean rotation, Θj , spaced evenly around the principal axis of the joint. [sent-88, score-0.146]

52 This angular uncertainty is illustrated by the dark dots. [sent-89, score-0.096]

53 For the backward conditional we show the distribution over torso conﬁgurations conditioned on the thigh. [sent-90, score-0.379]

54 The location of xi restricts xj to lie near a hemisphere, and the orientation Θi and principal axis of rotation further restrict xj to a strip on that hemisphere which can be seen in Figure 2b (light dots). [sent-94, score-0.388]

55 Thus each mixture component in (1) is spaced evenly in Θj and xj to represent this range of uncertainty. [sent-95, score-0.155]

56 The combined uncertainty in torso location and orientation can be seen in the distribution of the dark dots representing the distal torso joint. [sent-96, score-0.616]

57 Image Likelihoods The inference algorithm outlined in the next section combines the body model described above with a probabilistic image likelihood model. [sent-97, score-0.595]

58 In particular, we deﬁne φ i (Xi ) to be the likelihood of observing the image measurements conditioned on the pose of limb i. [sent-98, score-0.589]

59 Following related work [18], the likelihoods are estimated independently for each image view by projecting the 3D model of a limb into the corresponding image projection plane. [sent-101, score-0.489]

60 These likelihoods are then combined across views, assuming independence, and are weighted by the observability of the limb in a given view (more weight is given to views in which the limb lies parallel to the image projection plane). [sent-102, score-0.695]

61 For more information on the formulation of the image likelihoods see [20]. [sent-103, score-0.129]

62 3 Non-parametric Belief Propagation Having deﬁned the model it remains to specify an algorithm which will perform inference and estimate a belief distribution for each of the body parts. [sent-104, score-0.671]

63 If it were feasible to discretize the Xi we could apply traditional belief propagation or a specialized inference algorithm as set out in [8]. [sent-105, score-0.331]

64 It is a generalization of particle ﬁltering [7] which allows inference over arbitrary graphs rather than just a chain. [sent-107, score-0.156]

65 This generalization is achieved by treating the particle set which is propagated in a standard particle ﬁlter as an approximation to the “message” used in the belief propagation algorithm, and replacing the conditional distribution from the previous time step by a product of incoming message sets. [sent-108, score-0.611]

66 A message mij from node i → j is written mij (Xj ) = ψij (Xi , Xj )φi (Xi ) mkj (Xi )dXi , (2) k∈Ai \j where Ai is the set of neighbors of node i and φi (Xi ) is the local likelihood associated with node i. [sent-109, score-0.607]

67 The message mij (Xj ) can be approximated by importance sampling N = (N − 1)/Mij times from a proposal function f (Xi ), and then doing importance correction. [sent-110, score-0.383]

68 ) As discussed in [12] the samples may be stratiﬁed into groups with different proposal functions f (·), so some samples come from the product of all incoming messages Ai into the node, some from Ai \j (i. [sent-112, score-0.154]

69 Ai excluding j) and some from a static importance function Q(Xi ) — we use a limb proposal distribution based on local image measurements. [sent-114, score-0.412]

70 For reasons of space we present only a simpliﬁed algorithm to update message mij in Figure 3 which does not include the stratiﬁcation but the full algorithm can be found in [12]. [sent-115, score-0.248]

71 Draw N = (N − 1)/Mij samples from the proposal function: sn ∼ f (Xi ), n ∈ [1, N ]. [sent-120, score-0.103]

72 Compute importance corrections for n ∈ [1, N ]: n ηij = φi (˜n ) sij k∈Ai \j f (˜n ) sij mki (˜n ) sij . [sent-122, score-0.237]

73 Store normalized weights and mixture components for n ∈ [1, N ], m ∈ [1, Mij ]: (a) n = (n − 1)Mij + m (b) µn = Fijm (˜n ) sij ij (c) Λn = Gijm (˜n ) sij ij n (d) πij = (1 − λ0 ) n ηij δijm N k=1 k ηij . [sent-124, score-0.535]

74 Assign outlier component: πij = λ0 , µN = µ0 , ΛN = Λ0 ij ij ij ij Figure 3: The simpliﬁed PAMPAS non-parametric belief propagation algorithm. [sent-126, score-0.94]

75 4 Experiments We illustrate the approach by recovering 3D body pose given weak bottom-up information and clutter. [sent-127, score-0.606]

76 The development of bottom-up part detectors is beyond the scope of this paper. [sent-128, score-0.223]

77 After 10 iterations of belief propagation, the algorithm has discarded the samples which originated in clutter and has correctly assigned the limbs. [sent-131, score-0.239]

78 The ﬁgure shows the initialization and the ﬁnal distribution over limb poses which is computed by sampling from the belief distribution. [sent-132, score-0.571]

79 Note that the torso is well localized even though there was no bottom-up detector for it. [sent-133, score-0.201]

80 5 Conclusion We present a new body model and inference method that supports the goals of automatically locating and tracking an articulated body in three dimensions. [sent-134, score-1.291]

81 We show that a “looselimbed” model with continuous-valued parameters can effectively represent a person’s location and pose, and that inference over such a model can be tractably performed using belief propagation over particle sets. [sent-135, score-0.422]

82 Moreover, we demonstrate robust location of the person starting from imperfect initialization using a simulated body-part detector. [sent-136, score-0.184]

83 It is straightforward to extend the graphical model across time to implement a person (a) (b) Figure 4: Inferring attractive people: Two experiments are shown; (a) and (b) show results for two different time instants in a walking cycle. [sent-140, score-0.216]

84 Left: Initialization samples drawn from noisy simulated part detectors. [sent-142, score-0.131]

85 Part detectors are assumed to have high failure rate, generating 50% of the samples far away from any true body part. [sent-143, score-0.647]

86 the left thigh samples are equally distributed over left and right thigh and calf. [sent-146, score-0.147]

87 We use 100 particles to model the messages between the nodes, and show 20 samples from the belief distribution, as well as the average of the top 10 percent of the belief samples as the ”best” pose estimate. [sent-149, score-0.561]

88 For brevity, (b) only shows the best pose from a single view. [sent-150, score-0.153]

89 Constructing reliable detectors using only low-level information (static appearance) is a challenging problem but we have the advantage of being robust to imperfect detection as noted above. [sent-154, score-0.178]

90 We also intend to learn the conditional distributions between parts from a database of motion capture data. [sent-155, score-0.303]

91 Together these advances should allow reliable use of the presented body model in the person tracking framework. [sent-156, score-0.708]

92 Finding deformable shapes using loopy belief propagation, ECCV Vol. [sent-174, score-0.153]

93 Automatic partitioning of high dimensional search spaces associated with articulated body motion capture, CVPR, pp. [sent-187, score-0.73]

94 Shi, Inferring human upper body motion, Tech report CMU-RI-TR-03-05, 2003. [sent-217, score-0.498]

95 A dynamic Bayesian network approach to c ﬁgure tracking using learned dynamic models, ICCV, pp. [sent-252, score-0.169]

96 Finding and tracking people from the bottom up, CVPR, Vol. [sent-257, score-0.256]

97 Stochastic tracking of 3D human ﬁgures using 2D image motion, ECCV, vol. [sent-270, score-0.291]

98 Covariance scaled sampling for monocular 3D body tracking, CVPR, vol. [sent-283, score-0.49]

99 Yu, Tracking articulated body by dynamic Markov network, ICCV, pp. [sent-297, score-0.604]

100 Object segmentation by graph partitioning Concurrent object recognition and segmentation by graph partitioning, Advances in Neural Info. [sent-312, score-0.124]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('body', 0.453), ('limb', 0.283), ('limbs', 0.207), ('mij', 0.17), ('tracking', 0.169), ('torso', 0.166), ('ij', 0.156), ('belief', 0.153), ('pose', 0.153), ('articulated', 0.151), ('detectors', 0.143), ('proximal', 0.132), ('conditionals', 0.119), ('propagation', 0.113), ('cvpr', 0.101), ('parts', 0.099), ('initialization', 0.098), ('isard', 0.095), ('particle', 0.091), ('xj', 0.09), ('people', 0.087), ('person', 0.086), ('conditional', 0.085), ('motion', 0.084), ('distal', 0.083), ('eccv', 0.083), ('ijm', 0.083), ('graphical', 0.082), ('part', 0.08), ('sij', 0.079), ('message', 0.078), ('image', 0.077), ('kinematic', 0.076), ('conditioned', 0.076), ('dots', 0.076), ('orientation', 0.074), ('deutscher', 0.072), ('fijm', 0.072), ('gijm', 0.072), ('iccv', 0.066), ('inference', 0.065), ('mixture', 0.065), ('node', 0.063), ('pampas', 0.062), ('xi', 0.059), ('position', 0.057), ('pictorial', 0.057), ('providence', 0.057), ('sudderth', 0.057), ('joints', 0.053), ('backward', 0.052), ('likelihoods', 0.052), ('proposal', 0.052), ('samples', 0.051), ('automatic', 0.051), ('dark', 0.051), ('outlier', 0.05), ('ai', 0.048), ('brown', 0.048), ('extremities', 0.048), ('fischler', 0.048), ('instants', 0.048), ('ioffe', 0.048), ('sidenbladh', 0.048), ('thigh', 0.048), ('calibrated', 0.047), ('approximated', 0.046), ('angular', 0.045), ('exploit', 0.045), ('human', 0.045), ('guration', 0.044), ('constraints', 0.044), ('partitioning', 0.042), ('burl', 0.041), ('coughlan', 0.041), ('elastic', 0.041), ('felzenszwalb', 0.041), ('puppet', 0.041), ('singularities', 0.041), ('frame', 0.041), ('graph', 0.041), ('modeled', 0.041), ('cope', 0.04), ('axis', 0.04), ('forward', 0.039), ('appearance', 0.038), ('rotational', 0.038), ('push', 0.038), ('cameras', 0.038), ('con', 0.038), ('sampling', 0.037), ('hemisphere', 0.035), ('clutter', 0.035), ('intend', 0.035), ('ls', 0.035), ('strati', 0.035), ('detector', 0.035), ('gurations', 0.035), ('detection', 0.035), ('black', 0.035)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999976 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

2 0.19168481 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.

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

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

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

Author: D. Philipona, J.k. O'regan, J.-p. Nadal, Olivier Coenen

Abstract: Is there a way for an algorithm linked to an unknown body to infer by itself information about this body and the world it is in? Taking the case of space for example, is there a way for this algorithm to realize that its body is in a three dimensional world? Is it possible for this algorithm to discover how to move in a straight line? And more basically: do these questions make any sense at all given that the algorithm only has access to the very high-dimensional data consisting of its sensory inputs and motor outputs? We demonstrate in this article how these questions can be given a positive answer. We show that it is possible to make an algorithm that, by analyzing the law that links its motor outputs to its sensory inputs, discovers information about the structure of the world regardless of the devices constituting the body it is linked to. We present results from simulations demonstrating a way to issue motor orders resulting in “fundamental” movements of the body as regards the structure of the physical world. 1

5 0.11843538 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

6 0.11507702 117 nips-2003-Linear Response for Approximate Inference

7 0.11493079 80 nips-2003-Generalised Propagation for Fast Fourier Transforms with Partial or Missing Data

8 0.11246504 50 nips-2003-Denoising and Untangling Graphs Using Degree Priors

9 0.1109255 169 nips-2003-Sample Propagation

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

11 0.10439552 32 nips-2003-Approximate Expectation Maximization

12 0.096567877 58 nips-2003-Efficient Multiscale Sampling from Products of Gaussian Mixtures

13 0.092909522 152 nips-2003-Pairwise Clustering and Graphical Models

14 0.089805804 142 nips-2003-On the Concentration of Expectation and Approximate Inference in Layered Networks

15 0.082960509 33 nips-2003-Approximate Planning in POMDPs with Macro-Actions

16 0.079129502 133 nips-2003-Mutual Boosting for Contextual Inference

17 0.077466659 69 nips-2003-Factorization with Uncertainty and Missing Data: Exploiting Temporal Coherence

18 0.075562835 189 nips-2003-Tree-structured Approximations by Expectation Propagation

19 0.07469596 138 nips-2003-Non-linear CCA and PCA by Alignment of Local Models

20 0.073808827 49 nips-2003-Decoding V1 Neuronal Activity using Particle Filtering with Volterra Kernels

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.24), (1, -0.022), (2, -0.018), (3, 0.142), (4, -0.11), (5, -0.257), (6, 0.149), (7, 0.028), (8, 0.083), (9, -0.106), (10, -0.042), (11, 0.113), (12, -0.026), (13, 0.02), (14, 0.051), (15, -0.014), (16, 0.068), (17, 0.026), (18, -0.013), (19, -0.038), (20, 0.04), (21, -0.05), (22, 0.015), (23, 0.143), (24, 0.01), (25, -0.2), (26, 0.05), (27, 0.001), (28, -0.001), (29, -0.018), (30, -0.039), (31, 0.069), (32, -0.135), (33, -0.131), (34, 0.07), (35, -0.08), (36, 0.194), (37, 0.022), (38, 0.098), (39, 0.053), (40, -0.079), (41, -0.037), (42, 0.061), (43, -0.063), (44, -0.005), (45, -0.09), (46, 0.061), (47, -0.018), (48, -0.041), (49, -0.034)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96193254 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

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

Author: Claudio Fanti, Marzia Polito, Pietro Perona

3 0.61994368 37 nips-2003-Automatic Annotation of Everyday Movements

Author: Deva Ramanan, David A. Forsyth

4 0.46638623 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.

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

Author: D. Philipona, J.k. O'regan, J.-p. Nadal, Olivier Coenen

6 0.46058258 32 nips-2003-Approximate Expectation Maximization

7 0.43028551 74 nips-2003-Finding the M Most Probable Configurations using Loopy Belief Propagation

8 0.4123877 69 nips-2003-Factorization with Uncertainty and Missing Data: Exploiting Temporal Coherence

9 0.39902571 80 nips-2003-Generalised Propagation for Fast Fourier Transforms with Partial or Missing Data

10 0.39486048 169 nips-2003-Sample Propagation

11 0.36196864 142 nips-2003-On the Concentration of Expectation and Approximate Inference in Layered Networks

12 0.36015353 30 nips-2003-Approximability of Probability Distributions

13 0.3476671 29 nips-2003-Applying Metric-Trees to Belief-Point POMDPs

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

15 0.33703965 135 nips-2003-Necessary Intransitive Likelihood-Ratio Classifiers

16 0.32942486 7 nips-2003-A Functional Architecture for Motion Pattern Processing in MSTd

17 0.32441312 54 nips-2003-Discriminative Fields for Modeling Spatial Dependencies in Natural Images

18 0.32194349 130 nips-2003-Model Uncertainty in Classical Conditioning

19 0.31923044 175 nips-2003-Sensory Modality Segregation

20 0.31772447 12 nips-2003-A Model for Learning the Semantics of Pictures

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.05), (11, 0.058), (29, 0.022), (30, 0.012), (35, 0.066), (53, 0.048), (59, 0.012), (66, 0.281), (68, 0.011), (71, 0.092), (76, 0.046), (85, 0.108), (91, 0.096)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.92232281 195 nips-2003-When Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts?

Author: David Donoho, Victoria Stodden

Abstract: We interpret non-negative matrix factorization geometrically, as the problem of ﬁnding a simplicial cone which contains a cloud of data points and which is contained in the positive orthant. We show that under certain conditions, basically requiring that some of the data are spread across the faces of the positive orthant, there is a unique such simplicial cone. We give examples of synthetic image articulation databases which obey these conditions; these require separated support and factorial sampling. For such databases there is a generative model in terms of ‘parts’ and NMF correctly identiﬁes the ‘parts’. We show that our theoretical results are predictive of the performance of published NMF code, by running the published algorithms on one of our synthetic image articulation databases. 1

same-paper 2 0.85533202 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.80117363 188 nips-2003-Training fMRI Classifiers to Detect Cognitive States across Multiple Human Subjects

Author: Xuerui Wang, Rebecca Hutchinson, Tom M. Mitchell

Abstract: We consider learning to classify cognitive states of human subjects, based on their brain activity observed via functional Magnetic Resonance Imaging (fMRI). This problem is important because such classiﬁers constitute “virtual sensors” of hidden cognitive states, which may be useful in cognitive science research and clinical applications. In recent work, Mitchell, et al. [6,7,9] have demonstrated the feasibility of training such classiﬁers for individual human subjects (e.g., to distinguish whether the subject is reading an ambiguous or unambiguous sentence, or whether they are reading a noun or a verb). Here we extend that line of research, exploring how to train classiﬁers that can be applied across multiple human subjects, including subjects who were not involved in training the classiﬁer. We describe the design of several machine learning approaches to training multiple-subject classiﬁers, and report experimental results demonstrating the success of these methods in learning cross-subject classiﬁers for two different fMRI data sets. 1

4 0.73892152 98 nips-2003-Kernel Dimensionality Reduction for Supervised Learning

Author: Kenji Fukumizu, Francis R. Bach, Michael I. Jordan

Abstract: We propose a novel method of dimensionality reduction for supervised learning. Given a regression or classiﬁcation problem in which we wish to predict a variable Y from an explanatory vector X, we treat the problem of dimensionality reduction as that of ﬁnding a low-dimensional “effective subspace” of X which retains the statistical relationship between X and Y . We show that this problem can be formulated in terms of conditional independence. To turn this formulation into an optimization problem, we characterize the notion of conditional independence using covariance operators on reproducing kernel Hilbert spaces; this allows us to derive a contrast function for estimation of the effective subspace. Unlike many conventional methods, the proposed method requires neither assumptions on the marginal distribution of X, nor a parametric model of the conditional distribution of Y . 1

5 0.58102262 191 nips-2003-Unsupervised Context Sensitive Language Acquisition from a Large Corpus

Author: Zach Solan, David Horn, Eytan Ruppin, Shimon Edelman

Abstract: We describe a pattern acquisition algorithm that learns, in an unsupervised fashion, a streamlined representation of linguistic structures from a plain natural-language corpus. This paper addresses the issues of learning structured knowledge from a large-scale natural language data set, and of generalization to unseen text. The implemented algorithm represents sentences as paths on a graph whose vertices are words (or parts of words). Signiﬁcant patterns, determined by recursive context-sensitive statistical inference, form new vertices. Linguistic constructions are represented by trees composed of signiﬁcant patterns and their associated equivalence classes. An input module allows the algorithm to be subjected to a standard test of English as a Second Language (ESL) proﬁciency. The results are encouraging: the model attains a level of performance considered to be “intermediate” for 9th-grade students, despite having been trained on a corpus (CHILDES) containing transcribed speech of parents directed to small children. 1

6 0.56933051 109 nips-2003-Learning a Rare Event Detection Cascade by Direct Feature Selection

7 0.56564718 147 nips-2003-Online Learning via Global Feedback for Phrase Recognition

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

9 0.55720955 124 nips-2003-Max-Margin Markov Networks

10 0.55411035 9 nips-2003-A Kullback-Leibler Divergence Based Kernel for SVM Classification in Multimedia Applications

11 0.55259615 50 nips-2003-Denoising and Untangling Graphs Using Degree Priors

12 0.54897094 47 nips-2003-Computing Gaussian Mixture Models with EM Using Equivalence Constraints

13 0.54816842 3 nips-2003-AUC Optimization vs. Error Rate Minimization

14 0.54552901 115 nips-2003-Linear Dependent Dimensionality Reduction

15 0.54436529 117 nips-2003-Linear Response for Approximate Inference

16 0.54294413 54 nips-2003-Discriminative Fields for Modeling Spatial Dependencies in Natural Images

17 0.54143202 28 nips-2003-Application of SVMs for Colour Classification and Collision Detection with AIBO Robots

18 0.53819251 20 nips-2003-All learning is Local: Multi-agent Learning in Global Reward Games

19 0.53756464 100 nips-2003-Laplace Propagation

20 0.53728521 41 nips-2003-Boosting versus Covering