nips nips2008 nips2008-211 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Erik Talvitie, Satinder P. Singh
Abstract: We present a novel mathematical formalism for the idea of a “local model” of an uncontrolled dynamical system, a model that makes only certain predictions in only certain situations. As a result of its restricted responsibilities, a local model may be far simpler than a complete model of the system. We then show how one might combine several local models to produce a more detailed model. We demonstrate our ability to learn a collection of local models on a large-scale example and do a preliminary empirical comparison of learning a collection of local models and some other model learning methods. 1
Reference: text
sentIndex sentText sentNum sentScore
1 edu Abstract We present a novel mathematical formalism for the idea of a “local model” of an uncontrolled dynamical system, a model that makes only certain predictions in only certain situations. [sent-3, score-0.339]
2 We demonstrate our ability to learn a collection of local models on a large-scale example and do a preliminary empirical comparison of learning a collection of local models and some other model learning methods. [sent-6, score-0.573]
3 It can be much simpler to answer abstract questions like “Where will the ball bounce? [sent-11, score-0.344]
4 We call sequences of observations tests and let T be the set of all possible tests of all lengths. [sent-31, score-0.808]
5 The set of all def histories H is defined: H = {t ∈ T : p(t|φ) > 0} ∪ {φ}. [sent-50, score-0.365]
6 A union test T ⊆ T is a set of tests such that if t ∈ T then no prefix of t is in T . [sent-60, score-0.491]
7 The measure of complexity that we will adopt is called the linear dimension [6] and is defined as the rank of the “system dynamics matrix” (the infinite matrix of predictions whose ij th entry is p(tj |hi ) for all tj ∈ T and hi ∈ H). [sent-64, score-0.419]
8 2 Local Models In contrast to a complete model, a local model has limited prediction responsibilities and hence makes only certain predictions in certain situations. [sent-68, score-0.482]
9 Given a set of tests of interest T I and a set of histories of interest HI , a local model is any model that generates the predictions of interest: p(t|h) for all t ∈ T I and h ∈ HI . [sent-70, score-1.365]
10 We will assume, in general, that the tests of interest are union tests. [sent-71, score-0.589]
11 A set of histories of interest HI is semi-Markov iff h, h′ ∈ HI ∪ {φ} and ht ∈ HI for some t ∈ T , implies that either h′ t ∈ HI or p(h′ t|φ) = 0. [sent-75, score-0.493]
12 The ball moves along the line, changing direction when it hits the edge. [sent-78, score-0.365]
13 Figure 1: 1D Ball Bounce One natural local model would make one-step predictions about only one pixel, p. [sent-82, score-0.419]
14 It has two tests of interest: the set of all one-step tests in which the pixel p is black, and the set of all one-step tests in which p is white. [sent-83, score-1.278]
15 This local model answers the question “What is the chance the ball will be in pixel p next? [sent-85, score-0.597]
16 Another, even more restricted local model would be one that has the same tests of interest, but whose histories of interest are only those that end with pixel p being black. [sent-88, score-1.137]
17 This local model would essentially answer the question “When the ball is in pixel p, what is the chance that it will stick? [sent-89, score-0.627]
18 ” In order to make this prediction, the local model can ignore all detail; the prediction for the test of interest is always 0. [sent-90, score-0.421]
19 In general, as in the examples above, we expect that many details about the world are irrelevant to making the predictions of interest and could be ignored in order to simplify the local model. [sent-93, score-0.511]
20 [10], given tests and histories of interest, we will show how to convert a primitive observation sequence into an 2 abstract observation sequence that ignores unnecessary detail. [sent-97, score-0.926]
21 A complete model of the abstracted system can be used as a local model in the original, primitive system. [sent-98, score-0.509]
22 First, we construct an intermediate system which makes predictions for all tests, but only updates at histories of interest. [sent-100, score-0.607]
23 Then we further abstract the system by ignoring details irrelevant to making predictions for just the tests of interest. [sent-101, score-0.716]
24 1 Abstracting Details for Local Predictions Incorporating Histories Of Interest: Intuitively, since a local model is never asked to make a prediction at a history outside of HI , one way to simplify it is to only update its predictions at histories of interest. [sent-103, score-0.882]
25 Essentially, it “wakes up” whenever a history of interest occurs, sees what observation sequence happened since it was last awake, updates, and then goes dormant until the next history of interest. [sent-104, score-0.463]
26 We call the sequences of observations that happen between histories of interest bridging tests. [sent-105, score-0.899]
27 The set of bridging tests T B is induced by the set of histories of interest. [sent-106, score-1.092]
28 A test t ∈ T is a bridging test iff for all j < |t|, and all h ∈ HI , ht[1. [sent-108, score-0.493]
29 Conceptually, we transform the primitive observation sequence into a sequence of abstract observations in which each observation corresponds to a bridging test. [sent-115, score-0.678]
30 Note that even when the primitive system has a small number of observations, the T E system can have infinitely many, because there can be an infinity of bridging tests. [sent-117, score-0.714]
31 However, because it does not Figure 2: Mapping experience in the original update between histories of interest, a model of T E system to experience in the TE system, and may be simpler than a model of the original system. [sent-118, score-0.582]
32 This system has linear dimension O(2k), intuitively because the ball has 2 possible directions and k possible positions. [sent-121, score-0.416]
33 The bridging tests, then, are all possible ways the ball could travel to an edge and back. [sent-123, score-0.679]
34 The probability of each bridging test depends only on the current direction of the ball. [sent-124, score-0.431]
35 If the linear dimension of a dynamical system is n then, given a semi-Markov set of histories of interest HI , the linear dimension of the induced T E system, nT E ≤ n. [sent-128, score-0.674]
36 (Sketch) The linear dimension of a system is the rank of the system dynamics matrix (SDM) corresponding to the system [6]. [sent-130, score-0.383]
37 The matrix corresponding to the T E system is the submatrix of the SDM of the original system with only columns and rows corresponding to histories and tests that are sequences of bridging tests. [sent-131, score-1.334]
38 We next show that a model of the TE system can make predictions for all tests t ∈ T in all histories of interest h ∈ HI . [sent-134, score-1.186]
39 Specifically, we show that the prediction for any test in a history of interest can be expressed as a prediction of a union test in T E. [sent-135, score-0.458]
40 For the following, note that every history of interest h ∈ HI can be written as a corresponding sequence of bridging tests, which we will call sh . [sent-136, score-0.775]
41 Also, we will use the subscript T E to distinguish predictions pT E (t|h) in T E from predictions p(t|h) in the original system. [sent-137, score-0.384]
42 First suppose t can be written as a sequence of bridging tests st . [sent-142, score-0.878]
43 If t does not correspond to a sequence of bridging tests, we can re-write it as the concatenation of two tests: t = t1 t2 such that t1 is the longest prefix of t that is a sequence of bridging tests (which may be null) and t2 ∈ T B . [sent-144, score-1.254]
44 To calculate p(t2 |ht1 ) note that 3 def there must be a set of bridging tests Bt2 which have t2 as a prefix: Bt2 = {b ∈ T B : b[1. [sent-147, score-0.845]
45 The probability of seeing t2 is the probability of seeing any of the bridging tests in Bt2 . [sent-151, score-0.786]
46 Since tests of interest are union tests, to make the prediction of interest p(T |h) for some T ∈ T I and h ∈ HI using a model of T E, we have simply p(T |h) = pT E (ST |sh ) = t∈T pT E (St |sh ). [sent-154, score-0.822]
47 A model of T E is simpler than a complete model of the system because it only makes predictions at histories of interest. [sent-155, score-0.747]
48 We can further simplify our modeling task by focusing on predicting the tests of interest. [sent-157, score-0.384]
49 Since all histories are of interest, bridging tests are single observations, and T E is exactly equivalent to the original system. [sent-159, score-1.092]
50 However, note that in order to make the predictions of interest, one must only know whether the ball is neighboring or on the pixel. [sent-160, score-0.502]
51 So, we need only distinguish observations in which the ball is nearby, and we can group the rest into one abstract observation: “the ball is far from the pixel. [sent-161, score-0.594]
52 ” In general we will attempt to abstract away unnecessary details of bridging tests by aliasing bridging tests that are equivalent with respect to making the predictions of interest. [sent-162, score-1.764]
53 Specifically, we will define a partition, or a many-to-one mapping, from T E observations (the bridging tests T B ) to abstract observations A. [sent-163, score-0.866]
54 We will then use a model of the abstract system with A as its observations (see Figure 2) as our local model. [sent-164, score-0.343]
55 So, A must have the following properties: (1) we must be able to express the tests of interest as a union of sequences of abstract observations in A and (2) an abstracted history must contain enough detail to make accurate predictions for the tests of interest. [sent-165, score-1.451]
56 We assume that tests of interest are unions of one-step tests (i. [sent-168, score-0.924]
57 One natural example that satisfies this assumption is where the local model makes one-step predictions for a particular dimension of a vector-valued observation. [sent-171, score-0.416]
58 There is no fundamental barrier to treating tests of interest that are arbitrary union tests, but the development of the general case is more complex. [sent-172, score-0.589]
59 Note that if a union test T ⊂ O, then the equivalent T E union test, ST , consists of every bridging def test that begins with an observation in T . [sent-173, score-0.739]
60 So, if T I partitions O, then S I ={ST : T ∈ T I } partitions B the bridging tests, T , according to their first observation. [sent-174, score-0.402]
61 For instance, in our 1D Ball Bounce, in order to make accurate predictions for one pixel it does not suffice to observe that pixel and ignore the rest. [sent-177, score-0.527]
62 An observation abstraction A is accurate with respect to T I iff for any two primitive histories h1 = o1 . [sent-182, score-0.584]
63 The system we are abstracting is T E, so the observations are bridging tests. [sent-189, score-0.58]
64 Furthermore, an accurate refinement is one that only aliases two histories if they result in the same predictions for the tests of interest. [sent-192, score-0.932]
65 Thus, we can use an abstract history to make exactly the same predictions for the tests of interest that we would make if we had access to the primitive history. [sent-193, score-0.982]
66 If the linear dimension of a dynamical system is n then the linear dimension of any local model M, nM ≤ nT E ≤ n. [sent-197, score-0.435]
67 4 Learning a local model: We are given tests and histories of interest and an accurate abstraction. [sent-201, score-1.026]
68 To learn a local model, we first translate the primitive trajectories into T E trajectories using the histories of interest, and then translate the T E trajectories into abstract trajectories using the accurate abstraction (as in Figure 2). [sent-202, score-0.852]
69 Each local model M ∈ M has tests of interest TM , I histories of interest HM , and is an exact model of the abstract system induced by a given accurate def I refinement, AM . [sent-207, score-1.391]
70 At any history h, the set of models Mh = {M ∈ M : h ∈ HM } is available to make predictions for their tests of interest. [sent-208, score-0.789]
71 However, we may wish to make predictions that are not specifically of interest to any local model. [sent-209, score-0.511]
72 We will make a modeling assumption that allows us to efficiently combine the predictions of local models: Definition 7. [sent-211, score-0.414]
73 i=1 A domain expert specifying the structure of a collection of local models should strive to satisfy this property as best as possible since, given this assumption, a collection of local models can be used to make many more predictions than can be made by each individual model. [sent-219, score-0.763]
74 We can compute the predictions of finer-grained tests (intersections of tests of interest) by multiplying predictions together. [sent-220, score-1.152]
75 We can also compute the predictions of unions of tests of interest using the standard formula: Pr(A ∪ B) = Pr(A) + Pr(B) − Pr(A ∩ B). [sent-221, score-0.732]
76 At any history h for which Mh = ∅, a collection of local models can be used to make predictions for any union test that can be constructed by unioning/intersecting the tests of interest of the models in Mh . [sent-222, score-1.292]
77 A collection of local models can selectively focus on making the most important predictions well, ignoring or approximating less important predictions to save on representational complexity. [sent-225, score-0.684]
78 As such, if every one-step test is expressible as an intersection of tests of interest of models in Mh at every h, then M is a complete model. [sent-238, score-0.686]
79 If it does not, predictions made using M will be approximate, even if each local model in M makes its predictions of interest exactly. [sent-240, score-0.705]
80 When learning a collection of local models in this paper, we assume that tests and histories of interest as well as an accurate refinement for each model are given. [sent-242, score-1.171]
81 Automatically splitting a system into simple local models is an interesting, challenging problem, and ripe ground for future research. [sent-245, score-0.329]
82 Thus our structural assumptions can be verified using statistical tests on the data while DBN assumptions cannot be directly verified. [sent-252, score-0.384]
83 These distributions are like local models that make one-step predictions about their variable. [sent-255, score-0.445]
84 Update rules are essentially local models with pre and post-conditions playing the roles of histories and tests of interest. [sent-263, score-0.959]
85 In the image is a 2 × 2 pixel ball and a wall of 6 × 4 pixel bricks. [sent-275, score-0.529]
86 After the ball hits a brick, the brick disappears. [sent-276, score-0.516]
87 When the ball hits the bottom wall, it bounces at a randomly selected angle. [sent-277, score-0.365]
88 ” After the ball hits a dark brick, all bricks require two hits rather than one to break. [sent-280, score-0.604]
89 After the ball hits a light brick, all bricks require only one hit to break. [sent-281, score-0.552]
90 Quite naturally, we have local models to predict how the bricks (rows 1-2), the ball (row 3), and the background (row 4) will behave. [sent-288, score-0.648]
91 This structure satisfies the mutual conditional independence property, and since every pixel is predicted by some model at every history, we can make fully detailed 64× 42 pixel one-step predictions. [sent-289, score-0.411]
92 To take advantage of this, for each type of local model 1 Note: there are 30 bricks b, 2,688 pixels p, 2,183 possible positions p for the ball, and 9 possible directions d the ball could come from, including the case in the first step, where the ball simply appears in a pixel. [sent-295, score-0.943]
93 (12 in total, since there is a ball model for each of the 9 directions) we combine all translated trajectories associated with various positions and use them to train a single shared model. [sent-307, score-0.387]
94 Our learned local models were first-order Markov except the one responsible for predicting what will happen to a brick when the ball hits it. [sent-314, score-0.76]
95 We learned a model of the 1D Ball Bounce of size 5 and 20 using two collections of local models with no parameter tying (using PSRs and POMDPs as local models respectively), two flat models (a PSR and a POMDP), and a DBN 2 . [sent-333, score-0.645]
96 One predicts the color of the pixel in the next time step in histories when the ball is not in the immediate neighborhood about the pixel. [sent-335, score-0.751]
97 The other model applies when the ball is in the pixel. [sent-337, score-0.335]
98 This model distinguishes bridging tests in which the ball went to the left, the right, or stayed on the pixel in the first step. [sent-339, score-1.262]
99 This collection of local models satisfies the mutual conditional independence property and allows prediction of primitive one-step tests. [sent-340, score-0.44]
100 The collections of local models both perform well, outperforming the flat models (dashed lines). [sent-352, score-0.336]
wordName wordTfidf (topN-words)
[('bridging', 0.402), ('tests', 0.384), ('histories', 0.306), ('ball', 0.277), ('predictions', 0.192), ('hi', 0.171), ('local', 0.159), ('brick', 0.151), ('bricks', 0.151), ('satinder', 0.147), ('psr', 0.134), ('interest', 0.127), ('pixel', 0.126), ('history', 0.119), ('dbn', 0.119), ('bounce', 0.117), ('oi', 0.113), ('system', 0.109), ('pomdp', 0.095), ('primitive', 0.094), ('episodes', 0.094), ('nement', 0.094), ('hits', 0.088), ('talvitie', 0.084), ('union', 0.078), ('sdm', 0.075), ('dynamical', 0.072), ('sh', 0.068), ('arcade', 0.067), ('psrs', 0.067), ('abstraction', 0.063), ('models', 0.061), ('mh', 0.061), ('st', 0.059), ('def', 0.059), ('collections', 0.055), ('wolfe', 0.054), ('pt', 0.054), ('tying', 0.054), ('accurate', 0.05), ('pre', 0.049), ('relational', 0.049), ('collection', 0.049), ('trajectories', 0.045), ('abstracted', 0.044), ('singh', 0.044), ('pixels', 0.044), ('color', 0.042), ('game', 0.041), ('uncontrolled', 0.04), ('observations', 0.04), ('independence', 0.039), ('prediction', 0.038), ('observation', 0.038), ('distinguishes', 0.038), ('dbns', 0.038), ('simpler', 0.037), ('hit', 0.036), ('erik', 0.036), ('model', 0.035), ('pomdps', 0.034), ('te', 0.034), ('britton', 0.034), ('soni', 0.034), ('complete', 0.033), ('world', 0.033), ('make', 0.033), ('sequence', 0.033), ('iff', 0.033), ('hm', 0.033), ('pr', 0.031), ('ignoring', 0.031), ('combine', 0.03), ('dimension', 0.03), ('experience', 0.03), ('answer', 0.03), ('markov', 0.029), ('unions', 0.029), ('abstracting', 0.029), ('michael', 0.029), ('test', 0.029), ('james', 0.028), ('observable', 0.027), ('ht', 0.027), ('toolkit', 0.027), ('happened', 0.027), ('nir', 0.027), ('every', 0.026), ('likelihood', 0.026), ('rank', 0.026), ('predictive', 0.026), ('responsibilities', 0.025), ('daphne', 0.025), ('happen', 0.024), ('submatrix', 0.024), ('dogs', 0.024), ('intelligence', 0.023), ('re', 0.023), ('state', 0.023), ('applies', 0.023)]
simIndex simValue paperId paperTitle
same-paper 1 1.0 211 nips-2008-Simple Local Models for Complex Dynamical Systems
Author: Erik Talvitie, Satinder P. Singh
Abstract: We present a novel mathematical formalism for the idea of a “local model” of an uncontrolled dynamical system, a model that makes only certain predictions in only certain situations. As a result of its restricted responsibilities, a local model may be far simpler than a complete model of the system. We then show how one might combine several local models to produce a more detailed model. We demonstrate our ability to learn a collection of local models on a large-scale example and do a preliminary empirical comparison of learning a collection of local models and some other model learning methods. 1
2 0.11887159 141 nips-2008-Multi-Agent Filtering with Infinitely Nested Beliefs
Author: Luke Zettlemoyer, Brian Milch, Leslie P. Kaelbling
Abstract: In partially observable worlds with many agents, nested beliefs are formed when agents simultaneously reason about the unknown state of the world and the beliefs of the other agents. The multi-agent filtering problem is to efficiently represent and update these beliefs through time as the agents act in the world. In this paper, we formally define an infinite sequence of nested beliefs about the state of the world at the current time t, and present a filtering algorithm that maintains a finite representation which can be used to generate these beliefs. In some cases, this representation can be updated exactly in constant time; we also present a simple approximation scheme to compact beliefs if they become too complex. In experiments, we demonstrate efficient filtering in a range of multi-agent domains. 1
3 0.061469372 65 nips-2008-Domain Adaptation with Multiple Sources
Author: Yishay Mansour, Mehryar Mohri, Afshin Rostamizadeh
Abstract: This paper presents a theoretical analysis of the problem of domain adaptation with multiple sources. For each source domain, the distribution over the input points as well as a hypothesis with error at most ǫ are given. The problem consists of combining these hypotheses to derive a hypothesis with small error with respect to the target domain. We present several theoretical results relating to this problem. In particular, we prove that standard convex combinations of the source hypotheses may in fact perform very poorly and that, instead, combinations weighted by the source distributions benefit from favorable theoretical guarantees. Our main result shows that, remarkably, for any fixed target function, there exists a distribution weighted combining rule that has a loss of at most ǫ with respect to any target mixture of the source distributions. We further generalize the setting from a single target function to multiple consistent target functions and show the existence of a combining rule with error at most 3ǫ. Finally, we report empirical results for a multiple source adaptation problem with a real-world dataset.
4 0.059290122 146 nips-2008-Multi-task Gaussian Process Learning of Robot Inverse Dynamics
Author: Christopher Williams, Stefan Klanke, Sethu Vijayakumar, Kian M. Chai
Abstract: The inverse dynamics problem for a robotic manipulator is to compute the torques needed at the joints to drive it along a given trajectory; it is beneficial to be able to learn this function for adaptive control. A robotic manipulator will often need to be controlled while holding different loads in its end effector, giving rise to a multi-task learning problem. By placing independent Gaussian process priors over the latent functions of the inverse dynamics, we obtain a multi-task Gaussian process prior for handling multiple loads, where the inter-task similarity depends on the underlying inertial parameters. Experiments demonstrate that this multi-task formulation is effective in sharing information among the various loads, and generally improves performance over either learning only on single tasks or pooling the data over all tasks. 1
5 0.058011163 180 nips-2008-Playing Pinball with non-invasive BCI
Author: Matthias Krauledat, Konrad Grzeska, Max Sagebaum, Benjamin Blankertz, Carmen Vidaurre, Klaus-Robert Müller, Michael Schröder
Abstract: Compared to invasive Brain-Computer Interfaces (BCI), non-invasive BCI systems based on Electroencephalogram (EEG) signals have not been applied successfully for precisely timed control tasks. In the present study, however, we demonstrate and report on the interaction of subjects with a real device: a pinball machine. Results of this study clearly show that fast and well-timed control well beyond chance level is possible, even though the environment is extremely rich and requires precisely timed and complex predictive behavior. Using machine learning methods for mental state decoding, BCI-based pinball control is possible within the first session without the necessity to employ lengthy subject training. The current study shows clearly that very compelling control with excellent timing and dynamics is possible for a non-invasive BCI. 1
6 0.057313543 247 nips-2008-Using Bayesian Dynamical Systems for Motion Template Libraries
7 0.057061736 88 nips-2008-From Online to Batch Learning with Cutoff-Averaging
8 0.056534622 181 nips-2008-Policy Search for Motor Primitives in Robotics
9 0.055562444 177 nips-2008-Particle Filter-based Policy Gradient in POMDPs
10 0.055154499 121 nips-2008-Learning to Use Working Memory in Partially Observable Environments through Dopaminergic Reinforcement
11 0.055125259 138 nips-2008-Modeling human function learning with Gaussian processes
12 0.054744966 97 nips-2008-Hierarchical Fisher Kernels for Longitudinal Data
13 0.05274022 86 nips-2008-Finding Latent Causes in Causal Networks: an Efficient Approach Based on Markov Blankets
14 0.05071095 76 nips-2008-Estimation of Information Theoretic Measures for Continuous Random Variables
15 0.050534677 1 nips-2008-A Convergent $O(n)$ Temporal-difference Algorithm for Off-policy Learning with Linear Function Approximation
16 0.049764626 108 nips-2008-Integrating Locally Learned Causal Structures with Overlapping Variables
17 0.04945042 178 nips-2008-Performance analysis for L\ 2 kernel classification
18 0.048657525 77 nips-2008-Evaluating probabilities under high-dimensional latent variable models
19 0.048580874 152 nips-2008-Non-stationary dynamic Bayesian networks
20 0.047602594 234 nips-2008-The Infinite Factorial Hidden Markov Model
topicId topicWeight
[(0, -0.15), (1, 0.054), (2, 0.042), (3, -0.041), (4, 0.054), (5, -0.008), (6, 0.015), (7, 0.053), (8, 0.063), (9, 0.016), (10, 0.006), (11, 0.057), (12, 0.028), (13, -0.003), (14, 0.015), (15, 0.015), (16, -0.014), (17, -0.028), (18, -0.064), (19, 0.067), (20, 0.02), (21, -0.022), (22, 0.058), (23, 0.082), (24, 0.103), (25, -0.051), (26, -0.019), (27, 0.012), (28, 0.087), (29, 0.087), (30, 0.072), (31, 0.055), (32, 0.037), (33, -0.017), (34, -0.003), (35, -0.1), (36, 0.13), (37, 0.072), (38, -0.014), (39, 0.043), (40, -0.065), (41, -0.039), (42, 0.113), (43, 0.008), (44, -0.002), (45, 0.012), (46, -0.059), (47, 0.05), (48, -0.072), (49, 0.073)]
simIndex simValue paperId paperTitle
same-paper 1 0.93505287 211 nips-2008-Simple Local Models for Complex Dynamical Systems
Author: Erik Talvitie, Satinder P. Singh
Abstract: We present a novel mathematical formalism for the idea of a “local model” of an uncontrolled dynamical system, a model that makes only certain predictions in only certain situations. As a result of its restricted responsibilities, a local model may be far simpler than a complete model of the system. We then show how one might combine several local models to produce a more detailed model. We demonstrate our ability to learn a collection of local models on a large-scale example and do a preliminary empirical comparison of learning a collection of local models and some other model learning methods. 1
2 0.74300432 141 nips-2008-Multi-Agent Filtering with Infinitely Nested Beliefs
Author: Luke Zettlemoyer, Brian Milch, Leslie P. Kaelbling
Abstract: In partially observable worlds with many agents, nested beliefs are formed when agents simultaneously reason about the unknown state of the world and the beliefs of the other agents. The multi-agent filtering problem is to efficiently represent and update these beliefs through time as the agents act in the world. In this paper, we formally define an infinite sequence of nested beliefs about the state of the world at the current time t, and present a filtering algorithm that maintains a finite representation which can be used to generate these beliefs. In some cases, this representation can be updated exactly in constant time; we also present a simple approximation scheme to compact beliefs if they become too complex. In experiments, we demonstrate efficient filtering in a range of multi-agent domains. 1
3 0.61232424 33 nips-2008-Bayesian Model of Behaviour in Economic Games
Author: Debajyoti Ray, Brooks King-casas, P. R. Montague, Peter Dayan
Abstract: Classical game theoretic approaches that make strong rationality assumptions have difficulty modeling human behaviour in economic games. We investigate the role of finite levels of iterated reasoning and non-selfish utility functions in a Partially Observable Markov Decision Process model that incorporates game theoretic notions of interactivity. Our generative model captures a broad class of characteristic behaviours in a multi-round Investor-Trustee game. We invert the generative process for a recognition model that is used to classify 200 subjects playing this game against randomly matched opponents. 1
4 0.57041621 212 nips-2008-Skill Characterization Based on Betweenness
Author: Ozgur Simsek, Andre S. Barreto
Abstract: We present a characterization of a useful class of skills based on a graphical representation of an agent’s interaction with its environment. Our characterization uses betweenness, a measure of centrality on graphs. It captures and generalizes (at least intuitively) the bottleneck concept, which has inspired many of the existing skill-discovery algorithms. Our characterization may be used directly to form a set of skills suitable for a given task. More importantly, it serves as a useful guide for developing incremental skill-discovery algorithms that do not rely on knowing or representing the interaction graph in its entirety. 1
5 0.50872856 111 nips-2008-Kernel Change-point Analysis
Author: Zaïd Harchaoui, Eric Moulines, Francis R. Bach
Abstract: We introduce a kernel-based method for change-point analysis within a sequence of temporal observations. Change-point analysis of an unlabelled sample of observations consists in, first, testing whether a change in the distribution occurs within the sample, and second, if a change occurs, estimating the change-point instant after which the distribution of the observations switches from one distribution to another different distribution. We propose a test statistic based upon the maximum kernel Fisher discriminant ratio as a measure of homogeneity between segments. We derive its limiting distribution under the null hypothesis (no change occurs), and establish the consistency under the alternative hypothesis (a change occurs). This allows to build a statistical hypothesis testing procedure for testing the presence of a change-point, with a prescribed false-alarm probability and detection probability tending to one in the large-sample setting. If a change actually occurs, the test statistic also yields an estimator of the change-point location. Promising experimental results in temporal segmentation of mental tasks from BCI data and pop song indexation are presented. 1
6 0.46440205 110 nips-2008-Kernel-ARMA for Hand Tracking and Brain-Machine interfacing During 3D Motor Control
7 0.46048325 186 nips-2008-Probabilistic detection of short events, with application to critical care monitoring
8 0.4427951 88 nips-2008-From Online to Batch Learning with Cutoff-Averaging
9 0.43517512 169 nips-2008-Online Models for Content Optimization
10 0.43278149 236 nips-2008-The Mondrian Process
11 0.43186679 125 nips-2008-Local Gaussian Process Regression for Real Time Online Model Learning
12 0.42686966 119 nips-2008-Learning a discriminative hidden part model for human action recognition
13 0.41986629 10 nips-2008-A rational model of preference learning and choice prediction by children
14 0.41228008 108 nips-2008-Integrating Locally Learned Causal Structures with Overlapping Variables
15 0.41173494 98 nips-2008-Hierarchical Semi-Markov Conditional Random Fields for Recursive Sequential Data
16 0.40797392 86 nips-2008-Finding Latent Causes in Causal Networks: an Efficient Approach Based on Markov Blankets
17 0.40280759 153 nips-2008-Nonlinear causal discovery with additive noise models
18 0.39969805 13 nips-2008-Adapting to a Market Shock: Optimal Sequential Market-Making
19 0.39563027 144 nips-2008-Multi-resolution Exploration in Continuous Spaces
20 0.38494954 180 nips-2008-Playing Pinball with non-invasive BCI
topicId topicWeight
[(4, 0.021), (6, 0.056), (7, 0.058), (12, 0.067), (15, 0.013), (28, 0.227), (44, 0.207), (54, 0.014), (57, 0.081), (59, 0.023), (63, 0.032), (77, 0.038), (78, 0.012), (83, 0.063)]
simIndex simValue paperId paperTitle
1 0.86089903 31 nips-2008-Bayesian Exponential Family PCA
Author: Shakir Mohamed, Zoubin Ghahramani, Katherine A. Heller
Abstract: Principal Components Analysis (PCA) has become established as one of the key tools for dimensionality reduction when dealing with real valued data. Approaches such as exponential family PCA and non-negative matrix factorisation have successfully extended PCA to non-Gaussian data types, but these techniques fail to take advantage of Bayesian inference and can suffer from problems of overfitting and poor generalisation. This paper presents a fully probabilistic approach to PCA, which is generalised to the exponential family, based on Hybrid Monte Carlo sampling. We describe the model which is based on a factorisation of the observed data matrix, and show performance of the model on both synthetic and real data. 1
same-paper 2 0.85255998 211 nips-2008-Simple Local Models for Complex Dynamical Systems
Author: Erik Talvitie, Satinder P. Singh
Abstract: We present a novel mathematical formalism for the idea of a “local model” of an uncontrolled dynamical system, a model that makes only certain predictions in only certain situations. As a result of its restricted responsibilities, a local model may be far simpler than a complete model of the system. We then show how one might combine several local models to produce a more detailed model. We demonstrate our ability to learn a collection of local models on a large-scale example and do a preliminary empirical comparison of learning a collection of local models and some other model learning methods. 1
3 0.7814545 4 nips-2008-A Scalable Hierarchical Distributed Language Model
Author: Andriy Mnih, Geoffrey E. Hinton
Abstract: Neural probabilistic language models (NPLMs) have been shown to be competitive with and occasionally superior to the widely-used n-gram language models. The main drawback of NPLMs is their extremely long training and testing times. Morin and Bengio have proposed a hierarchical language model built around a binary tree of words, which was two orders of magnitude faster than the nonhierarchical model it was based on. However, it performed considerably worse than its non-hierarchical counterpart in spite of using a word tree created using expert knowledge. We introduce a fast hierarchical language model along with a simple feature-based algorithm for automatic construction of word trees from the data. We then show that the resulting models can outperform non-hierarchical neural models as well as the best n-gram models. 1
4 0.7805773 231 nips-2008-Temporal Dynamics of Cognitive Control
Author: Jeremy Reynolds, Michael C. Mozer
Abstract: Cognitive control refers to the flexible deployment of memory and attention in response to task demands and current goals. Control is often studied experimentally by presenting sequences of stimuli, some demanding a response, and others modulating the stimulus-response mapping. In these tasks, participants must maintain information about the current stimulus-response mapping in working memory. Prominent theories of cognitive control use recurrent neural nets to implement working memory, and optimize memory utilization via reinforcement learning. We present a novel perspective on cognitive control in which working memory representations are intrinsically probabilistic, and control operations that maintain and update working memory are dynamically determined via probabilistic inference. We show that our model provides a parsimonious account of behavioral and neuroimaging data, and suggest that it offers an elegant conceptualization of control in which behavior can be cast as optimal, subject to limitations on learning and the rate of information processing. Moreover, our model provides insight into how task instructions can be directly translated into appropriate behavior and then efficiently refined with subsequent task experience. 1
5 0.77456808 116 nips-2008-Learning Hybrid Models for Image Annotation with Partially Labeled Data
Author: Xuming He, Richard S. Zemel
Abstract: Extensive labeled data for image annotation systems, which learn to assign class labels to image regions, is difficult to obtain. We explore a hybrid model framework for utilizing partially labeled data that integrates a generative topic model for image appearance with discriminative label prediction. We propose three alternative formulations for imposing a spatial smoothness prior on the image labels. Tests of the new models and some baseline approaches on three real image datasets demonstrate the effectiveness of incorporating the latent structure. 1
6 0.77414685 176 nips-2008-Partially Observed Maximum Entropy Discrimination Markov Networks
7 0.77265936 118 nips-2008-Learning Transformational Invariants from Natural Movies
8 0.77225637 138 nips-2008-Modeling human function learning with Gaussian processes
9 0.77221423 113 nips-2008-Kernelized Sorting
10 0.77196324 50 nips-2008-Continuously-adaptive discretization for message-passing algorithms
11 0.77176332 197 nips-2008-Relative Performance Guarantees for Approximate Inference in Latent Dirichlet Allocation
12 0.77101338 195 nips-2008-Regularized Policy Iteration
13 0.7708866 48 nips-2008-Clustering via LP-based Stabilities
15 0.76997817 205 nips-2008-Semi-supervised Learning with Weakly-Related Unlabeled Data : Towards Better Text Categorization
16 0.76925296 247 nips-2008-Using Bayesian Dynamical Systems for Motion Template Libraries
17 0.76836777 101 nips-2008-Human Active Learning
18 0.76674038 201 nips-2008-Robust Near-Isometric Matching via Structured Learning of Graphical Models
19 0.76635057 227 nips-2008-Supervised Exponential Family Principal Component Analysis via Convex Optimization
20 0.7660743 246 nips-2008-Unsupervised Learning of Visual Sense Models for Polysemous Words