nips nips2003 nips2003-165 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Artur Garcez, Luis C. Lamb
Abstract: We show that temporal logic and combinations of temporal logics and modal logics of knowledge can be effectively represented in artificial neural networks. We present a Translation Algorithm from temporal rules to neural networks, and show that the networks compute a fixed-point semantics of the rules. We also apply the translation to the muddy children puzzle, which has been used as a testbed for distributed multi-agent systems. We provide a complete solution to the puzzle with the use of simple neural networks, capable of reasoning about time and of knowledge acquisition through inductive learning. 1
Reference: text
sentIndex sentText sentNum sentScore
1 br) Abstract We show that temporal logic and combinations of temporal logics and modal logics of knowledge can be effectively represented in artificial neural networks. [sent-11, score-0.715]
2 We present a Translation Algorithm from temporal rules to neural networks, and show that the networks compute a fixed-point semantics of the rules. [sent-12, score-0.249]
3 We also apply the translation to the muddy children puzzle, which has been used as a testbed for distributed multi-agent systems. [sent-13, score-0.896]
4 We provide a complete solution to the puzzle with the use of simple neural networks, capable of reasoning about time and of knowledge acquisition through inductive learning. [sent-14, score-0.42]
5 1 Introduction Hybrid neural-symbolic systems concern the use of problem-specific symbolic knowledge within the neurocomputing paradigm (d'Avila Garcez et al. [sent-15, score-0.227]
6 Until recently, neural-symbolic systems were not able to fully represent, reason and learn expressive languages other than propositional and fragments of first-order logic (Cloete & Zurada, 2000). [sent-18, score-0.245]
7 , 2003), a new approach to knowledge representation and reasoning in neural-symbolic systems based on neural networks ensembles has been introduced. [sent-22, score-0.245]
8 This new approach shows that modal logics can be effectively represented in artificial neural networks. [sent-23, score-0.196]
9 , 2003), we move one step further and show that temporal logics can be effectively represented in artificial neural oArtur Garcez is partly supported by the Nuffield Foundation. [sent-27, score-0.218]
10 This is done by providing a translation algorithm from temporal logic theories to the initial architecture of a neural network. [sent-31, score-0.321]
11 A theorem then shows that the translation is correct by proving that the network computes a fixed-point semantics of its corresponding temporal theory (van Emden & Kowalski, 1976) . [sent-32, score-0.26]
12 The result is a new learning system capable of reasoning about knowledge and time. [sent-33, score-0.204]
13 We have validated the Connectionist Temporal Logic (CTL) proposed here by applying it to a distributed time and knowledge representation problem known as the muddy children puzzle (Fagin et al. [sent-34, score-1.136]
14 CTL provides a combined (multi-modal) connectionist system of knowledge and time, which allows the modelling of evolving situations such as changing environments or possible worlds. [sent-36, score-0.233]
15 , combining knowledge and time (Halpern & Vardi, 1986; Halpern et al. [sent-39, score-0.204]
16 , 2003) and combining beliefs, desires and intentions (Rao & Georgeff, 1998) - have been proposed for distributed knowledge representation, little attention has been paid to the integration of a learning component for knowledge acquisition. [sent-40, score-0.272]
17 Purely from t he point of view of knowledge representation in neural-symbolic systems, this work contributes to the long term aim of representing expressive and computationally well-behaved symbolic formalisms in neural networks. [sent-42, score-0.25]
18 We start , in Section 2, by describing the muddy children puzzle, and use it to exemplify the main features of CTL. [sent-44, score-0.8]
19 In Section 3, we formally introduce CTL's Translation Algorithm, which maps knowledge and time theories into artificial neural networks, and prove that the t ranslation is correct. [sent-45, score-0.254]
20 2 Connectionist Reasoning about Time and Knowledge Temporal logic and its combination with other modalities such as knowledge and belief operators have been the subject of intense investigation (Fagin et al. [sent-47, score-0.356]
21 In this section, we use the muddy children puzzle, a testbed for distributed knowledge representation formalisms, t o exemplify how knowledge and t ime can be expressed in a connectionist setting. [sent-49, score-1.199]
22 There is a number n of (truthful and intelligent) children playing in a garden. [sent-52, score-0.24]
23 A certain number of children k (k :S n) has mud on their faces . [sent-53, score-0.293]
24 Each child can see if the other are muddy, but not themselves. [sent-54, score-0.23]
25 Now, consider the following situation: A caret aker announces that at least one child is muddy (k 2': 1) and asks does any of you know if you have mud on your own face? [sent-55, score-0.874]
26 If k = 1 (only one child is muddy), the muddy child answers yes at the first instance since she cannot see any other muddy child. [sent-57, score-1.636]
27 All the other children answer no at the first instance. [sent-58, score-0.24]
28 At the first instance, all children can only answer no. [sent-60, score-0.24]
29 This allows 1 to reason as follows: if 2 had said yes the first time, she would have been the only muddy child. [sent-61, score-0.648]
30 Since 2 said no , she must be seeing someone else muddy; and since I cannot see anyone else muddy apart from 2, I myself must be muddy! [sent-62, score-0.56]
31 Every children can only answer no the first two times round. [sent-65, score-0.24]
32 Again, this allows 1 to reason as follows: if 2 or 3 had said yes the second time, they would have been the only two muddy children. [sent-66, score-0.648]
33 The above cases clearly illustrate the need to distinguish between an agent's individual knowledge and common knowledge about the world in a particular situation. [sent-70, score-0.272]
34 For example, when k = 2, after everybody says no at the first round, it becomes common knowledge that at least two children are muddy. [sent-71, score-0.433]
35 Similarly, when k = 3, after everybody says no twice, it becomes common knowledge that at least three children are muddy, and so on. [sent-72, score-0.433]
36 I In what follows, a modality K j is used to represent the knowledge of an agent j. [sent-74, score-0.337]
37 In addition, the term Pi is used to denote that proposition P is true for agent i. [sent-75, score-0.201]
38 For example, KjPi means that agent j knows that P is true for agent i. [sent-76, score-0.528]
39 We use Pi to say that child i is muddy, and qk to say that at least k children are muddy (k :s; n). [sent-77, score-1.061]
40 Let us consider the case in which three children are playing in the garden (n = 3). [sent-78, score-0.24]
41 Rule ri below states that when child 1 knows that at least one child is muddy and that neither child 2 nor child 3 are muddy then child 1 knows that she herself is muddy. [sent-79, score-2.598]
42 Similarly, rule r~ states that if child 1 knows that there are at least two muddy children and she knows that child 2 is not muddy then she must also be able to know that she herself is muddy, and so on. [sent-80, score-2.182]
43 The rules for children 2 and 3 are interpreted analogously. [sent-81, score-0.332]
44 \KI ""'P2 ---+KIPI K Iq3 ---+KIPI Table 1: Snapshot rules for agent (child) 1 Each set of snapshot rules r~ (1 :s; I :s; n; mE N+) can be implemented in a single hidden layer neural network Ni as follows. [sent-86, score-0.561]
45 Finally, the input neurons are connected to the output neuron through the hidden neuron associated with the rule (ri). [sent-92, score-0.558]
46 Conversely, when a neuron is not activated, we say that its associated concept is false. [sent-99, score-0.182]
47 Weights and biases must be such that the output neuron is activated if and only if the interpretation associated with the input vector satisfies the rule antecedent. [sent-101, score-0.377]
48 In the case of rule ri, the output neuron associated with KIPI must be activated (true) if the input neuron associated with KIql, the input neuron associated with K I ""'P2, and the input neuron associated with K I ""'P3 are all activated (true). [sent-102, score-1.006]
49 C-ILP is a massively parallel computational model based on an artificial neural network that integrates inductive learning from examples and background knowledge with deductive learning through logic programming. [sent-105, score-0.573]
50 FollowINotice that this reasoning process can only start once it is common knowledge that at least one child is muddy, as announced by the caretaker. [sent-106, score-0.465]
51 , 1999)) , a Translation Algorithm maps any logic program P into a single hidden layer neural network N such t hat N computes the least fixed point of P . [sent-108, score-0.324]
52 For each agent (child) , a C-ILP network can be created. [sent-115, score-0.279]
53 Each network can be seen as representing a (learnable) possible world containing information about the knowledge held by an agent in a distributed system . [sent-116, score-0.415]
54 For example, if a ---+ b and b ---+ C are rules of the theory, neuron b will appear on both the input and output layers of the network, and if a is activated then c will be activated through the activation of b. [sent-124, score-0.545]
55 If child 1 is muddy, output neuron PI must be activat ed. [sent-129, score-0.475]
56 Since, child 2 and 3 can see child 1, they will know that PI is muddy. [sent-130, score-0.46]
57 This means that the activation of output neurons KI 'P2 and K I 'P3 in Figure 1 depends on the activation of neurons that are not in this network (NI ), but in N2 and N 3 . [sent-132, score-0.349]
58 Figure 2 illustrat es the interaction between three C-ILP networks in the muddy children puzzle. [sent-134, score-0.871]
59 The arrows connecting the networks implement the fact that when a child is muddy, the other children can see her . [sent-135, score-0.511]
60 , neuron PI is activated in N I , neuron KPI must be activat ed in N2 and N 3 . [sent-138, score-0.477]
61 For the sake of clarit y, the snapshot rules r;" shown in Figure 1 are omitted here, and this is indicat ed in Figure 2Note Pl means 'child 1 is muddy' while KPl means 'child 1 knows she is muddy'. [sent-139, score-0.281]
62 C-ILP represents fact s by not connecting the rule's hidden neuron to any input neuron (in the case of fully-connected n etworks, weights with initial value zero ar e used). [sent-141, score-0.399]
63 I I I I --------- - - - Figure 2: Interaction between agents in t he muddy children puzzle. [sent-145, score-0.88]
64 E ach network represents a possible world or an agent 's current set of beliefs (d' Avila Garcez et al. [sent-148, score-0.319]
65 This is exactly what is required for a complet e solution of the muddy children puzzle, as discussed below. [sent-151, score-0.8]
66 As we have seen, the solution to the muddy children puzzle illustrat ed in Figures 1 and 2 considers only snapshots of knowledge evolution along time rounds without the addition of a time variable (Ruth & Ryan, 2000). [sent-152, score-1.187]
67 A complete solution, however , requires the addition of a t emporal variable to allow reasoning about t he knowledge acquired after each time round. [sent-153, score-0.293]
68 The snapshot solution of Figures 1 and 2 should then be seen as representing the knowledge held by the agents at an arbitrary time t. [sent-154, score-0.307]
69 The knowledge held by the agents at time t + 1 would then b e represented by anot her set of C-ILP networks, appropriat ely connected t o the original set of networks. [sent-155, score-0.244]
70 In addition, if a rule labelled t i makes use of the n ext time t emporal operator 0 then what ever qualifies refers to the next time ti+l in a linear time flow. [sent-158, score-0.252]
71 As a result , the first t emporal rule above stat es that if, at tl, no child knows whether she is muddy or not then, at t 2 , child 1 will know that at least two children are muddy. [sent-159, score-1.557]
72 Similarly, the second rule states that, at t2, if still no child knows whether she is muddy or not then, at t3, child 1 will know that at least three children are muddy. [sent-160, score-1.496]
73 As b efore, analogous temporal rules exist for agents (children) 2 and 3. [sent-161, score-0.247]
74 The temporal rules , together with the snapshot rules , provide a complete solution to the puzzle. [sent-162, score-0.322]
75 4 o In Figure 3, networks are replicat ed to represent an agent's knowledge evolution in time. [sent-164, score-0.21]
76 A network represents an agent 's knowledge today (or at tl), a network repre41t is worth noting that each network remains a simple, single hidden layer neura l network that can be trained with the use of standard Backpropagation or other off-theshelf learning algorithm. [sent-165, score-0.684]
77 In one dimension we encode the knowledge interaction between agents at a given time point, and in the other dimension we encode the agents' knowledge evolution through time. [sent-186, score-0.413]
78 Each Li can be either a positive literal (p) or a negative literal ('p). [sent-196, score-0.184]
79 We use Amin to denote the minimum activation for a neuron to be considered active (true), Amin E (0,1). [sent-198, score-0.254]
80 We number the (annotated) literals 7 of P from 1 to v such that, when a C-ILP network N is created, the input and output layers of N are vectors of length v, where the i-th neuron represents the i-th (annotated) literal. [sent-199, score-0.332]
81 L1, the number of rules in P with the same (annotated) literal as consequent , for each rule Tl; MAXrz (kl' f. [sent-203, score-0.308]
82 , h : Kja, K k f3 -> OKj, means that if agent j knows a and agent k knows f3 at time tl then agent j knows / at time t2. [sent-222, score-1.171]
83 7We use ' (annotated) literals' to refer to any literal, annotated or not annotated ones . [sent-227, score-0.192]
84 For each time point t in P do: For each agent j in P do: Create a C-ILP Neural Network Nj,t. [sent-237, score-0.229]
85 , OKm - 1L k ----+ OKm L k+1,8 do: (a) Add a hidden neuron L O to N m ,t+1 and set h(x) as the activation function of L O; (b) Connect each neuron OKjLi (1 ::; i ::; k) in Nj,t to LO. [sent-246, score-0.471]
86 If L i is a positive (annotated) literal then set the connection weight to W; otherwise, set the connection weight to -W . [sent-247, score-0.198]
87 , OKm-1Lk ----+ KmLk+1 ' do: (a) Add a hidden neuron L O to Nm, t and set h(x) as the activation function of L O; (b) Connect each neuron OKjLi (1 ::; i ::; k) in Nj ,t to L O . [sent-254, score-0.471]
88 If L i is a positive (annotated) literal then set the connection weight to W; otherwise, set the connection weight to -W . [sent-255, score-0.198]
89 In the above algorithm it is worth noting that, whenever a rule consequent is preceded by 0, a forward connection from t to t + 1 and a feedback connection from t + 1 to t need to be added to the ensemble. [sent-259, score-0.26]
90 For example, if t : a ----+ Ob is a rule of P then not only must the activation of neuron a at t activate neuron b at t + 1, but the activation of neuron b at t + 1 must also activate neuron Ob at t . [sent-260, score-0.951]
91 The values of Wand come from C-ILP's Translation Algorithm (d'Avila Garcez & Zaverucha, 1999), and are chosen so that the behaviour of the network matches that of the temporal rules , as the following theorem shows. [sent-263, score-0.245]
92 e Theorem 1 (Correctness of Translation Algorithm) For each set of ground temporal rules P, there exists a neural network ensemble N such that N computes the fixed-point operator T p of P. [sent-264, score-0.245]
93 In this paper, we have illustrated this by providing a full solution to the muddy children puzzle, where agents reason about their knowledge at different time points. [sent-275, score-1.076]
94 A connectionist inductive learning system for modal logic programming (Technical Report 2002/6). [sent-321, score-0.386]
95 A connectionist inductive learning system for modal logic programming. [sent-330, score-0.386]
96 The connectionist inductive le arning and logic programming system . [sent-338, score-0.333]
97 Complete axiomatizations for reasoning about knowledge and time . [sent-353, score-0.232]
98 The complexity of reasoning about knowledge and time I: lower bounds. [sent-360, score-0.232]
99 Toward a new massively parallel computationa l model for logic programming. [sent-369, score-0.213]
100 Approximating the semantics of logic programs by r ecurrent n e ural n etworks. [sent-377, score-0.221]
wordName wordTfidf (topN-words)
[('muddy', 0.56), ('garcez', 0.318), ('children', 0.24), ('child', 0.23), ('agent', 0.201), ('neuron', 0.182), ('logic', 0.18), ('knowledge', 0.136), ('tl', 0.134), ('puzzle', 0.132), ('knows', 0.126), ('kipi', 0.121), ('connectionist', 0.097), ('annotated', 0.096), ('literal', 0.092), ('rules', 0.092), ('ctl', 0.091), ('holldobler', 0.091), ('artificial', 0.09), ('activated', 0.083), ('agents', 0.08), ('rule', 0.079), ('lamb', 0.079), ('network', 0.078), ('gabbay', 0.076), ('temporal', 0.075), ('activation', 0.072), ('reasoning', 0.068), ('translation', 0.066), ('snapshot', 0.063), ('emporal', 0.061), ('fagin', 0.061), ('halpern', 0.061), ('kmlk', 0.061), ('vardi', 0.061), ('zaverucha', 0.061), ('connect', 0.057), ('inductive', 0.056), ('yes', 0.056), ('connection', 0.053), ('eo', 0.053), ('mud', 0.053), ('logics', 0.053), ('modal', 0.053), ('symbolic', 0.051), ('neurons', 0.047), ('pi', 0.045), ('amin', 0.045), ('broda', 0.045), ('consequent', 0.045), ('kalinke', 0.045), ('kiql', 0.045), ('valiant', 0.045), ('ri', 0.045), ('networks', 0.041), ('semantics', 0.041), ('et', 0.04), ('literals', 0.039), ('nm', 0.037), ('ki', 0.037), ('ryan', 0.036), ('hidden', 0.035), ('expressive', 0.033), ('massively', 0.033), ('output', 0.033), ('evolution', 0.033), ('reason', 0.032), ('least', 0.031), ('activat', 0.03), ('avila', 0.03), ('connectionism', 0.03), ('emden', 0.03), ('etworks', 0.03), ('formalisms', 0.03), ('georgeff', 0.03), ('huth', 0.03), ('illustrat', 0.03), ('kibler', 0.03), ('kjl', 0.03), ('knowledg', 0.03), ('kowalski', 0.03), ('kpl', 0.03), ('lloyd', 0.03), ('ob', 0.03), ('okjli', 0.03), ('okm', 0.03), ('pazzani', 0.03), ('preceded', 0.03), ('testbed', 0.03), ('tomorrow', 0.03), ('towell', 0.03), ('wand', 0.03), ('zurada', 0.03), ('time', 0.028), ('labelled', 0.028), ('fj', 0.027), ('shavlik', 0.026), ('everybody', 0.026), ('luis', 0.026), ('lo', 0.026)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999923 165 nips-2003-Reasoning about Time and Knowledge in Neural Symbolic Learning Systems
Author: Artur Garcez, Luis C. Lamb
Abstract: We show that temporal logic and combinations of temporal logics and modal logics of knowledge can be effectively represented in artificial neural networks. We present a Translation Algorithm from temporal rules to neural networks, and show that the networks compute a fixed-point semantics of the rules. We also apply the translation to the muddy children puzzle, which has been used as a testbed for distributed multi-agent systems. We provide a complete solution to the puzzle with the use of simple neural networks, capable of reasoning about time and of knowledge acquisition through inductive learning. 1
2 0.13861027 20 nips-2003-All learning is Local: Multi-agent Learning in Global Reward Games
Author: Yu-han Chang, Tracey Ho, Leslie P. Kaelbling
Abstract: In large multiagent games, partial observability, coordination, and credit assignment persistently plague attempts to design good learning algorithms. We provide a simple and efficient algorithm that in part uses a linear system to model the world from a single agent’s limited perspective, and takes advantage of Kalman filtering to allow an agent to construct a good training signal and learn an effective policy. 1
3 0.1011055 105 nips-2003-Learning Near-Pareto-Optimal Conventions in Polynomial Time
Author: Xiaofeng Wang, Tuomas Sandholm
Abstract: We study how to learn to play a Pareto-optimal strict Nash equilibrium when there exist multiple equilibria and agents may have different preferences among the equilibria. We focus on repeated coordination games of non-identical interest where agents do not know the game structure up front and receive noisy payoffs. We design efficient near-optimal algorithms for both the perfect monitoring and the imperfect monitoring setting(where the agents only observe their own payoffs and the joint actions). 1
4 0.085911371 26 nips-2003-An MDP-Based Approach to Online Mechanism Design
Author: David C. Parkes, Satinder P. Singh
Abstract: Online mechanism design (MD) considers the problem of providing incentives to implement desired system-wide outcomes in systems with self-interested agents that arrive and depart dynamically. Agents can choose to misrepresent their arrival and departure times, in addition to information about their value for different outcomes. We consider the problem of maximizing the total longterm value of the system despite the self-interest of agents. The online MD problem induces a Markov Decision Process (MDP), which when solved can be used to implement optimal policies in a truth-revealing Bayesian-Nash equilibrium. 1
5 0.075382605 45 nips-2003-Circuit Optimization Predicts Dynamic Networks for Chemosensory Orientation in Nematode C. elegans
Author: Nathan A. Dunn, John S. Conery, Shawn R. Lockery
Abstract: The connectivity of the nervous system of the nematode Caenorhabditis elegans has been described completely, but the analysis of the neuronal basis of behavior in this system is just beginning. Here, we used an optimization algorithm to search for patterns of connectivity sufficient to compute the sensorimotor transformation underlying C. elegans chemotaxis, a simple form of spatial orientation behavior in which turning probability is modulated by the rate of change of chemical concentration. Optimization produced differentiator networks with inhibitory feedback among all neurons. Further analysis showed that feedback regulates the latency between sensory input and behavior. Common patterns of connectivity between the model and biological networks suggest new functions for previously identified connections in the C. elegans nervous system. 1
6 0.070450783 110 nips-2003-Learning a World Model and Planning with a Self-Organizing, Dynamic Neural System
7 0.065813296 157 nips-2003-Plasticity Kernels and Temporal Statistics
8 0.064518504 64 nips-2003-Estimating Internal Variables and Paramters of a Learning Agent by a Particle Filter
9 0.062908486 61 nips-2003-Entrainment of Silicon Central Pattern Generators for Legged Locomotory Control
10 0.056960825 65 nips-2003-Extending Q-Learning to General Adaptive Multi-Agent Systems
11 0.056131404 24 nips-2003-An Iterative Improvement Procedure for Hierarchical Clustering
12 0.055481929 183 nips-2003-Synchrony Detection by Analogue VLSI Neurons with Bimodal STDP Synapses
13 0.055382431 185 nips-2003-The Doubly Balanced Network of Spiking Neurons: A Memory Model with High Capacity
14 0.047674563 68 nips-2003-Eye Movements for Reward Maximization
15 0.046626486 127 nips-2003-Mechanism of Neural Interference by Transcranial Magnetic Stimulation: Network or Single Neuron?
16 0.045291632 29 nips-2003-Applying Metric-Trees to Belief-Point POMDPs
17 0.042870346 80 nips-2003-Generalised Propagation for Fast Fourier Transforms with Partial or Missing Data
18 0.040314976 33 nips-2003-Approximate Planning in POMDPs with Macro-Actions
19 0.039312322 125 nips-2003-Maximum Likelihood Estimation of a Stochastic Integrate-and-Fire Neural Model
20 0.038451925 16 nips-2003-A Recurrent Model of Orientation Maps with Simple and Complex Cells
topicId topicWeight
[(0, -0.12), (1, 0.135), (2, 0.049), (3, 0.029), (4, 0.013), (5, -0.019), (6, -0.052), (7, 0.06), (8, -0.069), (9, -0.072), (10, 0.058), (11, 0.025), (12, -0.025), (13, -0.086), (14, 0.022), (15, 0.007), (16, 0.005), (17, -0.014), (18, 0.044), (19, 0.018), (20, 0.018), (21, -0.006), (22, -0.148), (23, 0.168), (24, 0.001), (25, 0.131), (26, 0.016), (27, 0.12), (28, -0.009), (29, -0.013), (30, 0.181), (31, 0.077), (32, 0.077), (33, 0.037), (34, -0.027), (35, -0.038), (36, 0.015), (37, -0.078), (38, -0.002), (39, 0.063), (40, -0.009), (41, 0.034), (42, 0.07), (43, -0.003), (44, -0.066), (45, 0.04), (46, 0.045), (47, -0.05), (48, -0.046), (49, -0.041)]
simIndex simValue paperId paperTitle
same-paper 1 0.9574188 165 nips-2003-Reasoning about Time and Knowledge in Neural Symbolic Learning Systems
Author: Artur Garcez, Luis C. Lamb
Abstract: We show that temporal logic and combinations of temporal logics and modal logics of knowledge can be effectively represented in artificial neural networks. We present a Translation Algorithm from temporal rules to neural networks, and show that the networks compute a fixed-point semantics of the rules. We also apply the translation to the muddy children puzzle, which has been used as a testbed for distributed multi-agent systems. We provide a complete solution to the puzzle with the use of simple neural networks, capable of reasoning about time and of knowledge acquisition through inductive learning. 1
2 0.5988785 105 nips-2003-Learning Near-Pareto-Optimal Conventions in Polynomial Time
Author: Xiaofeng Wang, Tuomas Sandholm
Abstract: We study how to learn to play a Pareto-optimal strict Nash equilibrium when there exist multiple equilibria and agents may have different preferences among the equilibria. We focus on repeated coordination games of non-identical interest where agents do not know the game structure up front and receive noisy payoffs. We design efficient near-optimal algorithms for both the perfect monitoring and the imperfect monitoring setting(where the agents only observe their own payoffs and the joint actions). 1
3 0.57779479 26 nips-2003-An MDP-Based Approach to Online Mechanism Design
Author: David C. Parkes, Satinder P. Singh
Abstract: Online mechanism design (MD) considers the problem of providing incentives to implement desired system-wide outcomes in systems with self-interested agents that arrive and depart dynamically. Agents can choose to misrepresent their arrival and departure times, in addition to information about their value for different outcomes. We consider the problem of maximizing the total longterm value of the system despite the self-interest of agents. The online MD problem induces a Markov Decision Process (MDP), which when solved can be used to implement optimal policies in a truth-revealing Bayesian-Nash equilibrium. 1
4 0.52226627 45 nips-2003-Circuit Optimization Predicts Dynamic Networks for Chemosensory Orientation in Nematode C. elegans
Author: Nathan A. Dunn, John S. Conery, Shawn R. Lockery
Abstract: The connectivity of the nervous system of the nematode Caenorhabditis elegans has been described completely, but the analysis of the neuronal basis of behavior in this system is just beginning. Here, we used an optimization algorithm to search for patterns of connectivity sufficient to compute the sensorimotor transformation underlying C. elegans chemotaxis, a simple form of spatial orientation behavior in which turning probability is modulated by the rate of change of chemical concentration. Optimization produced differentiator networks with inhibitory feedback among all neurons. Further analysis showed that feedback regulates the latency between sensory input and behavior. Common patterns of connectivity between the model and biological networks suggest new functions for previously identified connections in the C. elegans nervous system. 1
5 0.48654762 20 nips-2003-All learning is Local: Multi-agent Learning in Global Reward Games
Author: Yu-han Chang, Tracey Ho, Leslie P. Kaelbling
Abstract: In large multiagent games, partial observability, coordination, and credit assignment persistently plague attempts to design good learning algorithms. We provide a simple and efficient algorithm that in part uses a linear system to model the world from a single agent’s limited perspective, and takes advantage of Kalman filtering to allow an agent to construct a good training signal and learn an effective policy. 1
6 0.46441209 185 nips-2003-The Doubly Balanced Network of Spiking Neurons: A Memory Model with High Capacity
7 0.4105151 175 nips-2003-Sensory Modality Segregation
8 0.38888279 25 nips-2003-An MCMC-Based Method of Comparing Connectionist Models in Cognitive Science
9 0.38195404 187 nips-2003-Training a Quantum Neural Network
10 0.3453756 110 nips-2003-Learning a World Model and Planning with a Self-Organizing, Dynamic Neural System
11 0.33495662 61 nips-2003-Entrainment of Silicon Central Pattern Generators for Legged Locomotory Control
12 0.33008686 157 nips-2003-Plasticity Kernels and Temporal Statistics
13 0.32631847 134 nips-2003-Near-Minimax Optimal Classification with Dyadic Classification Trees
14 0.32247478 183 nips-2003-Synchrony Detection by Analogue VLSI Neurons with Bimodal STDP Synapses
15 0.31842431 127 nips-2003-Mechanism of Neural Interference by Transcranial Magnetic Stimulation: Network or Single Neuron?
16 0.31784329 65 nips-2003-Extending Q-Learning to General Adaptive Multi-Agent Systems
17 0.30337948 104 nips-2003-Learning Curves for Stochastic Gradient Descent in Linear Feedforward Networks
18 0.29494596 16 nips-2003-A Recurrent Model of Orientation Maps with Simple and Complex Cells
19 0.2896615 68 nips-2003-Eye Movements for Reward Maximization
20 0.28434381 80 nips-2003-Generalised Propagation for Fast Fourier Transforms with Partial or Missing Data
topicId topicWeight
[(0, 0.038), (11, 0.01), (29, 0.014), (30, 0.032), (35, 0.023), (52, 0.436), (53, 0.102), (71, 0.05), (76, 0.03), (85, 0.044), (91, 0.11), (99, 0.011)]
simIndex simValue paperId paperTitle
same-paper 1 0.78287375 165 nips-2003-Reasoning about Time and Knowledge in Neural Symbolic Learning Systems
Author: Artur Garcez, Luis C. Lamb
Abstract: We show that temporal logic and combinations of temporal logics and modal logics of knowledge can be effectively represented in artificial neural networks. We present a Translation Algorithm from temporal rules to neural networks, and show that the networks compute a fixed-point semantics of the rules. We also apply the translation to the muddy children puzzle, which has been used as a testbed for distributed multi-agent systems. We provide a complete solution to the puzzle with the use of simple neural networks, capable of reasoning about time and of knowledge acquisition through inductive learning. 1
2 0.3627249 107 nips-2003-Learning Spectral Clustering
Author: Francis R. Bach, Michael I. Jordan
Abstract: Spectral clustering refers to a class of techniques which rely on the eigenstructure of a similarity matrix to partition points into disjoint clusters with points in the same cluster having high similarity and points in different clusters having low similarity. In this paper, we derive a new cost function for spectral clustering based on a measure of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem. Minimizing this cost function with respect to the partition leads to a new spectral clustering algorithm. Minimizing with respect to the similarity matrix leads to an algorithm for learning the similarity matrix. We develop a tractable approximation of our cost function that is based on the power method of computing eigenvectors. 1
3 0.357622 81 nips-2003-Geometric Analysis of Constrained Curves
Author: Anuj Srivastava, Washington Mio, Xiuwen Liu, Eric Klassen
Abstract: We present a geometric approach to statistical shape analysis of closed curves in images. The basic idea is to specify a space of closed curves satisfying given constraints, and exploit the differential geometry of this space to solve optimization and inference problems. We demonstrate this approach by: (i) defining and computing statistics of observed shapes, (ii) defining and learning a parametric probability model on shape space, and (iii) designing a binary hypothesis test on this space. 1
4 0.35440376 4 nips-2003-A Biologically Plausible Algorithm for Reinforcement-shaped Representational Learning
Author: Maneesh Sahani
Abstract: Significant plasticity in sensory cortical representations can be driven in mature animals either by behavioural tasks that pair sensory stimuli with reinforcement, or by electrophysiological experiments that pair sensory input with direct stimulation of neuromodulatory nuclei, but usually not by sensory stimuli presented alone. Biologically motivated theories of representational learning, however, have tended to focus on unsupervised mechanisms, which may play a significant role on evolutionary or developmental timescales, but which neglect this essential role of reinforcement in adult plasticity. By contrast, theoretical reinforcement learning has generally dealt with the acquisition of optimal policies for action in an uncertain world, rather than with the concurrent shaping of sensory representations. This paper develops a framework for representational learning which builds on the relative success of unsupervised generativemodelling accounts of cortical encodings to incorporate the effects of reinforcement in a biologically plausible way. 1
5 0.35388753 30 nips-2003-Approximability of Probability Distributions
Author: Alina Beygelzimer, Irina Rish
Abstract: We consider the question of how well a given distribution can be approximated with probabilistic graphical models. We introduce a new parameter, effective treewidth, that captures the degree of approximability as a tradeoff between the accuracy and the complexity of approximation. We present a simple approach to analyzing achievable tradeoffs that exploits the threshold behavior of monotone graph properties, and provide experimental results that support the approach. 1
6 0.3532429 65 nips-2003-Extending Q-Learning to General Adaptive Multi-Agent Systems
7 0.35276136 73 nips-2003-Feature Selection in Clustering Problems
8 0.35220721 20 nips-2003-All learning is Local: Multi-agent Learning in Global Reward Games
9 0.35207203 93 nips-2003-Information Dynamics and Emergent Computation in Recurrent Circuits of Spiking Neurons
10 0.35191768 78 nips-2003-Gaussian Processes in Reinforcement Learning
11 0.35082993 113 nips-2003-Learning with Local and Global Consistency
12 0.35080487 79 nips-2003-Gene Expression Clustering with Functional Mixture Models
13 0.34995291 80 nips-2003-Generalised Propagation for Fast Fourier Transforms with Partial or Missing Data
14 0.34958091 143 nips-2003-On the Dynamics of Boosting
15 0.34924147 126 nips-2003-Measure Based Regularization
16 0.34846681 86 nips-2003-ICA-based Clustering of Genes from Microarray Expression Data
17 0.34838241 138 nips-2003-Non-linear CCA and PCA by Alignment of Local Models
18 0.34733889 125 nips-2003-Maximum Likelihood Estimation of a Stochastic Integrate-and-Fire Neural Model
19 0.3472428 55 nips-2003-Distributed Optimization in Adaptive Networks
20 0.34711236 68 nips-2003-Eye Movements for Reward Maximization