nips nips2010 nips2010-39 knowledge-graph by maker-knowledge-mining

39 nips-2010-Bayesian Action-Graph Games

Source: pdf

Author: Albert X. Jiang, Kevin Leyton-brown

Abstract: Games of incomplete information, or Bayesian games, are an important gametheoretic model and have many applications in economics. We propose Bayesian action-graph games (BAGGs), a novel graphical representation for Bayesian games. BAGGs can represent arbitrary Bayesian games, and furthermore can compactly express Bayesian games exhibiting commonly encountered types of structure including symmetry, action- and type-speciﬁc utility independence, and probabilistic independence of type distributions. We provide an algorithm for computing expected utility in BAGGs, and discuss conditions under which the algorithm runs in polynomial time. Bayes-Nash equilibria of BAGGs can be computed by adapting existing algorithms for complete-information normal form games and leveraging our expected utility algorithm. We show both theoretically and empirically that our approaches improve signiﬁcantly on the state of the art. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 BAGGs can represent arbitrary Bayesian games, and furthermore can compactly express Bayesian games exhibiting commonly encountered types of structure including symmetry, action- and type-speciﬁc utility independence, and probabilistic independence of type distributions. [sent-7, score-0.763]

2 Bayes-Nash equilibria of BAGGs can be computed by adapting existing algorithms for complete-information normal form games and leveraging our expected utility algorithm. [sent-9, score-0.854]

3 Much of current research on computation of solution concepts has focused on complete-information games, in which the game being played is common knowledge among the players. [sent-15, score-0.395]

4 However, in many multi-agent situations, players are uncertain about the game being played. [sent-16, score-0.663]

5 The ﬁrst is representational: the straightforward tabular representation of Bayesian game utility functions (the Bayesian Normal Form) requires space exponential in the number of players. [sent-21, score-0.694]

6 For large games, it becomes infeasible to store the game in memory, and performing even computations that are polynomial time in the input size are impractical. [sent-22, score-0.407]

7 Harsanyi [10] showed that a Bayesian game can be interpreted as an equivalent complete-information game via “induced normal form” or “agent form” interpretations. [sent-25, score-0.776]

8 Most games of interest have highly-structured payoff functions, and thus it is possible to overcome the ﬁrst obstacle by representing them compactly. [sent-30, score-0.393]

9 BAGGs can represent arbitrary Bayesian games, and furthermore can compactly express Bayesian games with commonly encountered types of structure. [sent-35, score-0.402]

10 BAGGs represent utility functions in a way similar to the AGG representation, and like AGGs, are able to exploit anonymity and action-speciﬁc utility independencies. [sent-37, score-0.579]

11 Furthermore, BAGGs can compactly express Bayesian games exhibiting type-speciﬁc independence: each player’s utility function can have different kinds of structure depending on her instantiated type. [sent-38, score-0.627]

12 Computational tasks on the agent form can be done efﬁciently by leveraging our expected utility algorithm for BAGGs. [sent-44, score-0.424]

13 There has been some research on heuristic methods for ﬁnding Bayes-Nash equilibria for certain classes of auction games using iterated best response (see e. [sent-48, score-0.515]

14 [23] proposed a incomplete information version of the graphical game representation, and presented efﬁcient algorithms for computing approximate Bayes-Nash equilibria in the case of tree games. [sent-55, score-0.549]

15 [7] considered a similar extension of the graphical game representation and analyzed the problem of ﬁnding a pure-strategy Bayes-Nash equilibrium. [sent-57, score-0.404]

16 Bayesian games can be interpreted as dynamic games with a initial move by Nature; thus, also related is the literature on representations for dynamic games, including multi-agent inﬂuence diagrams (MAIDs) [17] and temporal action-graph games (TAGGs) [14]. [sent-61, score-0.996]

17 A complete-information game is a tuple (N, {Ai }i∈N , {ui }i∈N ) where N = {1, . [sent-69, score-0.398]

18 A mixed strategy σi for player i is a probability distribution over Ai . [sent-79, score-0.429]

19 We denote by ui (σ) the expected utility of player i under the mixed strategy proﬁle σ. [sent-81, score-0.838]

20 A game representation is a data structure that stores all information needed to specify a game. [sent-83, score-0.404]

21 A normal form representation of a game uses a matrix to represent each utility function ui . [sent-84, score-0.836]

22 A Bayesian game is a tuple (N, {Ai }i∈N , Θ, P, {ui }i∈N ) where N = {1, . [sent-89, score-0.398]

23 , n} is the set of players; each Ai is player i’s action set, and A = i Ai is the set of action proﬁles; Θ = i Θi is the set of type proﬁles, where Θi is player i’s set of types; P : Θ → R is the type distribution and ui : A × Θ → R is the utility function for player i. [sent-92, score-1.874]

24 Each player i observes her type θi and, based on this observation, chooses from her set of actions Ai . [sent-103, score-0.401]

25 Each player i’s utility is then given by ui (a, θ), where a is the resulting action proﬁle. [sent-104, score-0.908]

26 The expected utility of i given θi under a mixed strategy proﬁle σ is the expected value of i’s utility under the resulting joint distribution of a and θ, conditioned on i receiving type θi : P (θ−i |θi ) ui (σ|θi ) = σj (aj |θj ). [sent-112, score-0.892]

27 ui (a, θ) a θ−i (1) j A mixed strategy proﬁle σ is a Bayes-Nash equilibrium if for all i, for all θi , for all ai ∈ Ai , ui (σ|θi ) ≥ ui (σ θi →ai |θi ), where σ θi →ai is the mixed strategy proﬁle that is identical to σ except that i plays ai with probability 1 given θi . [sent-113, score-1.065]

28 Without additional structure, we cannot do better than representing each utility function ui : A×Θ → R as a table and the type distribution as a table as well. [sent-115, score-0.474]

29 We say a Bayesian game has independent type distributions if players’ types are drawn independently, i. [sent-118, score-0.463]

30 Given a permutation of players π : N → N and an action proﬁle a = (a1 , . [sent-122, score-0.528]

31 We say a Bayesian game has symmetric utility functions if |Ai | = |Aj | and |Θi | = |Θj | for all i, j ∈ N , and if for all permutations π : N → N , we have ui (a, θ) = uπ(i) (aπ , θπ ) for all i ∈ N . [sent-134, score-0.752]

32 A Bayesian game is symmetric if its type distribution and utility functions are symmetric. [sent-135, score-0.707]

33 The utility functions of such ||A a game range over at most |Θi ||Ai | n−2+|Θii|−1i | unique utility values. [sent-136, score-0.895]

34 |Θi ||A A Bayesian game exhibits conditional utility independence if each player i’s utility depends on the action proﬁle a and her own type θi , but does not depend on the other players’ types. [sent-137, score-1.522]

35 Then the utility function of each player i ranges over at most |A||Θi | unique utility values. [sent-138, score-0.846]

36 1 Complete-information interpretations Harsanyi [10] showed that any Bayesian game can be interpreted as a complete-information game, such that Bayes-Nash equilibria of the Bayesian game correspond to Nash equilibria of the completeinformation game. [sent-141, score-1.092]

37 A Bayesian game can be converted to its induced normal form, which is a complete-information game with the same set of n players, in which each player’s set of actions is her set of pure strategies in the Bayesian game. [sent-143, score-0.871]

38 Each player’s utility under an action proﬁle is deﬁned to be equal to the player’s expected utility under the corresponding pure strategy proﬁle in the Bayesian game. [sent-144, score-0.883]

39 Alternatively, a Bayesian game can be transformed to its agent form, where each type of each player in the Bayesian game is turned into one player in a complete-information game. [sent-145, score-1.52]

40 Formally, given a 3 Bayesian game (N, {Ai }i∈N , Θ, P, {ui }i∈N ), we deﬁne its agent form as the complete-information ˜ ˜ ˜ game (N , {Aj,θj }(j,θj )∈N , {˜j,θj }(j,θj )∈N ), where N consists of j∈N |Θj | players, one for every u ˜ ˜ type of every player of the Bayesian game. [sent-146, score-1.21]

41 For each player (j, θj ) ∈ N of the agent form game, her action set A(j,θj ) is Aj , the ˜= action set of j in the Bayesian game. [sent-148, score-0.879]

42 For all a ∈ A, uj,θ (˜) is equal to the expected utility of ˜ ˜ function of player (j, θj ) is uj,θ : A ˜ ˜ a j j ˜ player j of the Bayesian game given type θj , under the pure strategy proﬁle sa , where for all i and all a ˜ θi , si (θi ) = a(i,θi ) . [sent-151, score-1.431]

43 A similar correspondence exists for mixed strategy proﬁles: each mixed strategy proﬁle σ of the Bayesian game corresponds to a mixed strategy σ of the agent form, with σ(i,θi ) (ai ) = σi (ai |θi ) for all i, θi , ai . [sent-153, score-1.016]

44 This implies a correspondence between Bayes Nash equilibria of a ˜ σ Bayesian game and Nash equilibria of its agent form. [sent-155, score-0.802]

45 σ is a Bayes-Nash equilibrium of a Bayesian game if and only if σ is a Nash ˜ equilibrium of its agent form. [sent-157, score-0.744]

46 Our approach is to adapt concepts from the AGG representation [1, 13] to the Bayesian game setting. [sent-169, score-0.421]

47 At a high level, a BAGG is a Bayesian game on an action graph, a directed graph on a set of action nodes A. [sent-170, score-0.918]

48 To play the game, each player i, given her type θi , simultaneously chooses an action node from her type-action set Ai,θi ⊆ A. [sent-171, score-0.663]

49 Each action node thus corresponds to an action choice that is available to one or more of the players. [sent-172, score-0.516]

50 Once the players have made their choices, an action count is tallied for each action node α ∈ A, which is the number of agents that have chosen α. [sent-173, score-0.886]

51 A player’s utility depends only on the action node she chose and the action counts on the neighbors of the chosen node. [sent-174, score-0.826]

52 An action graph G = (A, E) is a directed graph where A is the set of action nodes, and E is a set of directed edges, with self edges allowed. [sent-177, score-0.542]

53 For each player i and each instantiation of her type θi ∈ Θi , her type-action set Ai,θi ⊆ A is the set of possible action choices of i given θi . [sent-182, score-0.595]

54 Deﬁne player i’s total action set to be A∪ = θi ∈Θi Ai,θi . [sent-184, score-0.534]

55 i We denote by A = i A∪ the set of action proﬁles, and by a ∈ A an action proﬁle. [sent-185, score-0.448]

56 A conﬁguration c is a vector of |A| non-negative integers, specifying for each action node the numbers of players choosing that action. [sent-190, score-0.596]

57 In other words, their utilities may depend on the number of players that chose the action node α, but not the identities of those players. [sent-206, score-0.652]

58 Secondly, the (lack of) edges between nodes in the action graph expresses action- and type-speciﬁc independencies of utilities of the game: depending on player i’s chosen action node (which also encodes information about her type), her utility depends on conﬁgurations over different sets of nodes. [sent-207, score-1.219]

59 An arbitrary Bayesian game given in Bayesian normal form can be encoded as a BAGG storing the same number of utility values. [sent-209, score-0.685]

60 Bayesian games with symmetric utility functions exhibit anonymity structure, which can be expressed in BAGGs by sharing action nodes. [sent-212, score-0.886]

61 1 BAGGs with function nodes In this section we extend the basic BAGG representation by introducing function nodes to the action graph. [sent-227, score-0.397]

62 In this extended representation, the action graph G’s vertices consist of both the set of action nodes A and the set of function nodes F. [sent-230, score-0.604]

63 As before, for each action node α we deﬁne a utility function uα : C (α) → R. [sent-236, score-0.56]

64 Such a function node p simply counts the number of players that chose any action in ν(p). [sent-245, score-0.619]

65 Consider a symmetric Bayesian game involving n players; each player plans to open a new coffee shop in a downtown area, but has to decide on the location. [sent-257, score-0.855]

66 Each player has T types, representing her private information about her cost of opening a coffee shop. [sent-260, score-0.418]

67 Conditioned on player i choosing some location, her utility depends on: (a) her own type; (b) the number of players that chose the same block; (c) the number of players that chose any of the surrounding blocks; and (d) the number of players that chose any other location. [sent-262, score-1.559]

68 The Bayesian normal form representation of this game has size n[T (B + 1)]n . [sent-263, score-0.462]

69 Since the game is symmetric, we label the types as {1, . [sent-265, score-0.402]

70 A contains one action O corresponding to not entering and T B other action nodes, with each location corresponding to a set of T action nodes, each representing the choice of that location by a player with a different type. [sent-269, score-1.021]

71 For each location (x, y) we create three function nodes: pxy representing the number of players choosing this location, pxy representing the number of players choosing any surrounding blocks, and pxy representing the number of players choosing any other block. [sent-274, score-1.224]

72 Each of these function nodes is a counting function node, whose neighbors are action nodes corresponding to the appropriate locations (for all types). [sent-275, score-0.412]

73 Each action node for location (x, y) has three neighbors, pxy , pxy , and pxy . [sent-276, score-0.487]

74 Our overall approach is to interpret the Bayesian game as a complete-information game, and then to apply existing algorithms for ﬁnding Nash equilibria of complete-information games. [sent-279, score-0.52]

75 1 that a Bayesian game can be transformed into its induced normal form or |Θ | its agent form. [sent-285, score-0.57]

76 In the induced normal form, each player i has |Ai | i actions (corresponding to her pure strategies of the Bayesian game). [sent-286, score-0.463]

77 Solving such a game would be infeasible for large |Θi |; just to represent an Nash equilibrium requires space exponential in |Θi |. [sent-287, score-0.513]

78 1 to the setting of BAGGs: now the action set of player (i, θi ) of the agent form corresponds to the type-action set Ai,θi of the BAGG. [sent-291, score-0.655]

80 A key computational task required by both Nash equilibrium algorithms in their inner loops is the computation of expected utility of the agent form. [sent-297, score-0.556]

81 1 that for all (i, θi ) the expected utility ui,θi (˜ ) of ˜ σ the agent form is equal to the expected utility ui (σ|θi ) of the Bayesian game. [sent-300, score-0.833]

82 Note that the expected utility ui (σ|θi ) can then be computed as the sum ui (σ|θi ) = ai ui (σ θi →ai |θi )σi (ai |θi ). [sent-307, score-0.8]

83 For games represented in Bayesian normal form, this algorithm runs in time polynomial in the representation size. [sent-309, score-0.466]

84 Each strategy variable Dj has domain A∪ , and given its parent θj , its CPD chooses an action from A∪ according to the j j θ mixed strategy σj i →ai . [sent-322, score-0.398]

85 For each j action node α, the parents of its action-count variable c(α) are strategy variables that have α in their domains. [sent-324, score-0.392]

86 Furthermore, the expected utility ui (σ ti →ai |θi ) is exactly the expected value of the variable U ai conditioned on the instantiated type θi . [sent-331, score-0.684]

87 For all i ∈ N , all θi ∈ Θi and all ai ∈ Ai,θi , we have ui (σ θi →ai |θi ) = E[U ai |θi ]. [sent-333, score-0.464]

88 In particular, recall that in the induced network, each action count variable c(α)’s parents are all strategy variables that have α in their domains, implying large in-degrees for action count variables. [sent-336, score-0.65]

89 It also corresponds to anonymity structure for complete-information game representations like symmetric games and AGGs [13]. [sent-342, score-0.753]

90 CPU time in seconds e 100 10000 1000 10000 CPU time in seconds econds nds CPU time in seconds 1000 10000 100000 BAGG-AF NF-AF INF 10000 CPU time in seconds econds ds 100000 NF-AF 1000 100 10 1 2 3 4 5 6 7 number of players Figure 4: simplicial subdivision. [sent-373, score-0.423]

91 Bayesian games with independent type distributions are an important class of games and have many applications, such as independent-private-value auctions. [sent-376, score-0.725]

92 For contribution-independent BAGGs with independent type distributions, expected utility can be computed in time polynomial in the size of the BAGG. [sent-379, score-0.395]

93 The ﬁrst (denoted INF) computes a Nash equilibrium on the induced normal form; the second (denoted NFAF) computes a Nash equilibrium on the normal form representation of the agent form. [sent-386, score-0.578]

94 We created games of different sizes by varying the number of players, the number of types per player and the number of locations. [sent-390, score-0.703]

95 Figure 1 shows running time results for Coffee Shop games with n players, 2 types per player on a 2 × 3 grid, with n varying from 3 to 7. [sent-397, score-0.726]

96 Figure 2 shows running time results for Coffee Shop games with 3 players, 2 types per player on a 2 × x grid, with x varying from 3 to 10. [sent-398, score-0.726]

97 Figure 3 shows results for Coffee Shop games with 3 players, T types per player on a 1 × 3 grid, with T varying from 2 to 8. [sent-399, score-0.703]

98 The data points represent the median running time of 10 game instances, with the error bars indicating the maximum and minimum running times. [sent-400, score-0.405]

99 Figure 4 shows running time results for Coffee Shop games with n players, 2 types per player on a 1 × 3 grid, with n varying from 3 to 6. [sent-404, score-0.726]

100 Bayesian equilibria of ﬁnite two-person games with incomplete information. [sent-477, score-0.522]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('game', 0.359), ('games', 0.332), ('player', 0.31), ('players', 0.304), ('baggs', 0.291), ('utility', 0.268), ('action', 0.224), ('nash', 0.215), ('ai', 0.179), ('bagg', 0.172), ('equilibria', 0.161), ('pro', 0.144), ('bayesian', 0.144), ('equilibrium', 0.132), ('agent', 0.121), ('ui', 0.106), ('le', 0.094), ('shop', 0.076), ('simplicial', 0.075), ('coffee', 0.069), ('node', 0.068), ('aj', 0.067), ('pxy', 0.065), ('mixed', 0.064), ('nodes', 0.064), ('type', 0.061), ('normal', 0.058), ('govindan', 0.057), ('strategy', 0.055), ('subdivision', 0.054), ('representation', 0.045), ('parents', 0.045), ('types', 0.043), ('aggs', 0.043), ('anonymity', 0.043), ('counting', 0.041), ('tuple', 0.039), ('les', 0.039), ('representing', 0.039), ('bn', 0.038), ('cpds', 0.038), ('dj', 0.035), ('jiang', 0.035), ('expected', 0.035), ('count', 0.035), ('cpd', 0.035), ('gw', 0.035), ('pure', 0.033), ('utilities', 0.033), ('agg', 0.032), ('blowup', 0.032), ('completeinformation', 0.032), ('daskalakis', 0.032), ('harsanyi', 0.032), ('tbn', 0.032), ('induced', 0.032), ('independence', 0.032), ('newton', 0.032), ('guration', 0.031), ('agents', 0.031), ('polynomial', 0.031), ('actions', 0.03), ('wilson', 0.029), ('incomplete', 0.029), ('cpu', 0.029), ('graph', 0.028), ('compactly', 0.027), ('bns', 0.024), ('running', 0.023), ('chose', 0.023), ('causal', 0.022), ('obstacle', 0.022), ('exponential', 0.022), ('auction', 0.022), ('downtown', 0.022), ('econds', 0.022), ('gambit', 0.022), ('gottlob', 0.022), ('howson', 0.022), ('ibn', 0.022), ('laan', 0.022), ('oliehoek', 0.022), ('subclasses', 0.022), ('tbns', 0.022), ('interpretations', 0.02), ('symmetric', 0.019), ('plays', 0.019), ('played', 0.019), ('directed', 0.019), ('treewidths', 0.019), ('xin', 0.019), ('neighbors', 0.019), ('compact', 0.018), ('network', 0.018), ('varying', 0.018), ('heckerman', 0.017), ('clique', 0.017), ('concepts', 0.017), ('der', 0.017), ('computations', 0.017)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999952 39 nips-2010-Bayesian Action-Graph Games

Author: Albert X. Jiang, Kevin Leyton-brown

2 0.16476743 226 nips-2010-Repeated Games against Budgeted Adversaries

Author: Jacob D. Abernethy, Manfred K. Warmuth

Abstract: We study repeated zero-sum games against an adversary on a budget. Given that an adversary has some constraint on the sequence of actions that he plays, we consider what ought to be the player’s best mixed strategy with knowledge of this budget. We show that, for a general class of normal-form games, the minimax strategy is indeed efﬁciently computable and relies on a “random playout” technique. We give three diverse applications of this new algorithmic template: a cost-sensitive “Hedge” setting, a particular problem in Metrical Task Systems, and the design of combinatorial prediction markets. 1

3 0.14892301 268 nips-2010-The Neural Costs of Optimal Control

Author: Samuel Gershman, Robert Wilson

Abstract: Optimal control entails combining probabilities and utilities. However, for most practical problems, probability densities can be represented only approximately. Choosing an approximation requires balancing the beneﬁts of an accurate approximation against the costs of computing it. We propose a variational framework for achieving this balance and apply it to the problem of how a neural population code should optimally represent a distribution under resource constraints. The essence of our analysis is the conjecture that population codes are organized to maximize a lower bound on the log expected utility. This theory can account for a plethora of experimental data, including the reward-modulation of sensory receptive ﬁelds, GABAergic effects on saccadic movements, and risk aversion in decisions under uncertainty. 1

4 0.13434787 192 nips-2010-Online Classification with Specificity Constraints

Author: Andrey Bernstein, Shie Mannor, Nahum Shimkin

Abstract: We consider the online binary classiﬁcation problem, where we are given m classiﬁers. At each stage, the classiﬁers map the input to the probability that the input belongs to the positive class. An online classiﬁcation meta-algorithm is an algorithm that combines the outputs of the classiﬁers in order to attain a certain goal, without having prior knowledge on the form and statistics of the input, and without prior knowledge on the performance of the given classiﬁers. In this paper, we use sensitivity and speciﬁcity as the performance metrics of the meta-algorithm. In particular, our goal is to design an algorithm that satisﬁes the following two properties (asymptotically): (i) its average false positive rate (fp-rate) is under some given threshold; and (ii) its average true positive rate (tp-rate) is not worse than the tp-rate of the best convex combination of the m given classiﬁers that satisﬁes fprate constraint, in hindsight. We show that this problem is in fact a special case of the regret minimization problem with constraints, and therefore the above goal is not attainable. Hence, we pose a relaxed goal and propose a corresponding practical online learning meta-algorithm that attains it. In the case of two classiﬁers, we show that this algorithm takes a very simple form. To our best knowledge, this is the ﬁrst algorithm that addresses the problem of the average tp-rate maximization under average fp-rate constraints in the online setting. 1

5 0.12640692 91 nips-2010-Fast detection of multiple change-points shared by many signals using group LARS

Author: Jean-philippe Vert, Kevin Bleakley

Abstract: We present a fast algorithm for the detection of multiple change-points when each is frequently shared by members of a set of co-occurring one-dimensional signals. We give conditions on consistency of the method when the number of signals increases, and provide empirical evidence to support the consistency results. 1

6 0.12473826 230 nips-2010-Robust Clustering as Ensembles of Affinity Relations

7 0.12336045 193 nips-2010-Online Learning: Random Averages, Combinatorial Parameters, and Learnability

8 0.095156997 4 nips-2010-A Computational Decision Theory for Interactive Assistants

9 0.086271837 100 nips-2010-Gaussian Process Preference Elicitation

10 0.08074636 15 nips-2010-A Theory of Multiclass Boosting

11 0.079936668 244 nips-2010-Sodium entry efficiency during action potentials: A novel single-parameter family of Hodgkin-Huxley models

12 0.079694234 236 nips-2010-Semi-Supervised Learning with Adversarially Missing Label Information

13 0.065540656 66 nips-2010-Double Q-learning

14 0.065433756 281 nips-2010-Using body-anchored priors for identifying actions in single images

15 0.065024331 40 nips-2010-Beyond Actions: Discriminative Models for Contextual Group Activities

16 0.065017439 196 nips-2010-Online Markov Decision Processes under Bandit Feedback

17 0.063239254 229 nips-2010-Reward Design via Online Gradient Ascent

18 0.062617213 171 nips-2010-Movement extraction by detecting dynamics switches and repetitions

19 0.060839199 197 nips-2010-Optimal Bayesian Recommendation Sets and Myopically Optimal Choice Query Sets

20 0.059418492 168 nips-2010-Monte-Carlo Planning in Large POMDPs

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.138), (1, -0.052), (2, 0.012), (3, 0.048), (4, -0.065), (5, 0.053), (6, -0.096), (7, 0.005), (8, 0.021), (9, 0.199), (10, -0.018), (11, 0.046), (12, -0.056), (13, -0.103), (14, 0.121), (15, -0.014), (16, -0.07), (17, 0.08), (18, -0.049), (19, 0.008), (20, 0.018), (21, 0.085), (22, 0.047), (23, -0.087), (24, 0.054), (25, -0.042), (26, 0.091), (27, 0.0), (28, -0.121), (29, 0.206), (30, 0.129), (31, 0.101), (32, 0.139), (33, -0.104), (34, 0.165), (35, -0.037), (36, -0.117), (37, 0.057), (38, 0.037), (39, 0.015), (40, 0.034), (41, -0.207), (42, 0.033), (43, 0.009), (44, -0.045), (45, -0.0), (46, 0.001), (47, -0.015), (48, -0.129), (49, 0.06)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97663176 39 nips-2010-Bayesian Action-Graph Games

Author: Albert X. Jiang, Kevin Leyton-brown

2 0.60530901 226 nips-2010-Repeated Games against Budgeted Adversaries

Author: Jacob D. Abernethy, Manfred K. Warmuth

3 0.4988133 244 nips-2010-Sodium entry efficiency during action potentials: A novel single-parameter family of Hodgkin-Huxley models

Author: Anand Singh, Renaud Jolivet, Pierre Magistretti, Bruno Weber

Abstract: Sodium entry during an action potential determines the energy efﬁciency of a neuron. The classic Hodgkin-Huxley model of action potential generation is notoriously inefﬁcient in that regard with about 4 times more charges ﬂowing through the membrane than the theoretical minimum required to achieve the observed depolarization. Yet, recent experimental results show that mammalian neurons are close to the optimal metabolic efﬁciency and that the dynamics of their voltage-gated channels is signiﬁcantly different than the one exhibited by the classic Hodgkin-Huxley model during the action potential. Nevertheless, the original Hodgkin-Huxley model is still widely used and rarely to model the squid giant axon from which it was extracted. Here, we introduce a novel family of HodgkinHuxley models that correctly account for sodium entry, action potential width and whose voltage-gated channels display a dynamics very similar to the most recent experimental observations in mammalian neurons. We speak here about a family of models because the model is parameterized by a unique parameter the variations of which allow to reproduce the entire range of experimental observations from cortical pyramidal neurons to Purkinje cells, yielding a very economical framework to model a wide range of different central neurons. The present paper demonstrates the performances and discuss the properties of this new family of models. 1

4 0.46003258 125 nips-2010-Inference and communication in the game of Password

Author: Yang Xu, Charles Kemp

Abstract: Communication between a speaker and hearer will be most efﬁcient when both parties make accurate inferences about the other. We study inference and communication in a television game called Password, where speakers must convey secret words to hearers by providing one-word clues. Our working hypothesis is that human communication is relatively efﬁcient, and we use game show data to examine three predictions. First, we predict that speakers and hearers are both considerate, and that both take the other’s perspective into account. Second, we predict that speakers and hearers are calibrated, and that both make accurate assumptions about the strategy used by the other. Finally, we predict that speakers and hearers are collaborative, and that they tend to share the cognitive burden of communication equally. We ﬁnd evidence in support of all three predictions, and demonstrate in addition that efﬁcient communication tends to break down when speakers and hearers are placed under time pressure.

5 0.43886682 91 nips-2010-Fast detection of multiple change-points shared by many signals using group LARS

Author: Jean-philippe Vert, Kevin Bleakley

6 0.4053736 268 nips-2010-The Neural Costs of Optimal Control

7 0.3992826 4 nips-2010-A Computational Decision Theory for Interactive Assistants

8 0.39535215 281 nips-2010-Using body-anchored priors for identifying actions in single images

9 0.39501303 168 nips-2010-Monte-Carlo Planning in Large POMDPs

10 0.38976043 192 nips-2010-Online Classification with Specificity Constraints

11 0.38507977 66 nips-2010-Double Q-learning

12 0.37769058 197 nips-2010-Optimal Bayesian Recommendation Sets and Myopically Optimal Choice Query Sets

13 0.36188874 139 nips-2010-Latent Variable Models for Predicting File Dependencies in Large-Scale Software Development

14 0.34554386 40 nips-2010-Beyond Actions: Discriminative Models for Contextual Group Activities

15 0.34224916 171 nips-2010-Movement extraction by detecting dynamics switches and repetitions

16 0.33810917 15 nips-2010-A Theory of Multiclass Boosting

17 0.33055902 28 nips-2010-An Alternative to Low-level-Sychrony-Based Methods for Speech Detection

18 0.32610005 100 nips-2010-Gaussian Process Preference Elicitation

19 0.30393049 193 nips-2010-Online Learning: Random Averages, Combinatorial Parameters, and Learnability

20 0.301862 236 nips-2010-Semi-Supervised Learning with Adversarially Missing Label Information

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(13, 0.026), (17, 0.018), (27, 0.516), (30, 0.047), (35, 0.019), (45, 0.16), (50, 0.027), (52, 0.019), (60, 0.031), (77, 0.032), (90, 0.014)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.98245728 119 nips-2010-Implicit encoding of prior probabilities in optimal neural populations

Author: Deep Ganguli, Eero P. Simoncelli

Abstract: unkown-abstract

2 0.96631801 128 nips-2010-Infinite Relational Modeling of Functional Connectivity in Resting State fMRI

Author: Morten Mørup, Kristoffer Madsen, Anne-marie Dogonowski, Hartwig Siebner, Lars K. Hansen

Abstract: Functional magnetic resonance imaging (fMRI) can be applied to study the functional connectivity of the neural elements which form complex network at a whole brain level. Most analyses of functional resting state networks (RSN) have been based on the analysis of correlation between the temporal dynamics of various regions of the brain. While these models can identify coherently behaving groups in terms of correlation they give little insight into how these groups interact. In this paper we take a different view on the analysis of functional resting state networks. Starting from the deﬁnition of resting state as functional coherent groups we search for functional units of the brain that communicate with other parts of the brain in a coherent manner as measured by mutual information. We use the inﬁnite relational model (IRM) to quantify functional coherent groups of resting state networks and demonstrate how the extracted component interactions can be used to discriminate between functional resting state activity in multiple sclerosis and normal subjects. 1

3 0.95073819 60 nips-2010-Deterministic Single-Pass Algorithm for LDA

Author: Issei Sato, Kenichi Kurihara, Hiroshi Nakagawa

Abstract: We develop a deterministic single-pass algorithm for latent Dirichlet allocation (LDA) in order to process received documents one at a time and then discard them in an excess text stream. Our algorithm does not need to store old statistics for all data. The proposed algorithm is much faster than a batch algorithm and is comparable to the batch algorithm in terms of perplexity in experiments.

4 0.92787379 121 nips-2010-Improving Human Judgments by Decontaminating Sequential Dependencies

Author: Harold Pashler, Matthew Wilder, Robert Lindsey, Matt Jones, Michael C. Mozer, Michael P. Holmes

Abstract: For over half a century, psychologists have been struck by how poor people are at expressing their internal sensations, impressions, and evaluations via rating scales. When individuals make judgments, they are incapable of using an absolute rating scale, and instead rely on reference points from recent experience. This relativity of judgment limits the usefulness of responses provided by individuals to surveys, questionnaires, and evaluation forms. Fortunately, the cognitive processes that transform internal states to responses are not simply noisy, but rather are inﬂuenced by recent experience in a lawful manner. We explore techniques to remove sequential dependencies, and thereby decontaminate a series of ratings to obtain more meaningful human judgments. In our formulation, decontamination is fundamentally a problem of inferring latent states (internal sensations) which, because of the relativity of judgment, have temporal dependencies. We propose a decontamination solution using a conditional random ﬁeld with constraints motivated by psychological theories of relative judgment. Our exploration of decontamination models is supported by two experiments we conducted to obtain ground-truth rating data on a simple length estimation task. Our decontamination techniques yield an over 20% reduction in the error of human judgments. 1

same-paper 5 0.90145135 39 nips-2010-Bayesian Action-Graph Games

Author: Albert X. Jiang, Kevin Leyton-brown

6 0.88051486 266 nips-2010-The Maximal Causes of Natural Scenes are Edge Filters

7 0.81459427 81 nips-2010-Evaluating neuronal codes for inference using Fisher information

8 0.78580064 161 nips-2010-Linear readout from a neural population with partial correlation data

9 0.76719654 6 nips-2010-A Discriminative Latent Model of Image Region and Object Tag Correspondence

10 0.73566288 127 nips-2010-Inferring Stimulus Selectivity from the Spatial Structure of Neural Network Dynamics

11 0.73092717 21 nips-2010-Accounting for network effects in neuronal responses using L1 regularized point process models

12 0.72022599 97 nips-2010-Functional Geometry Alignment and Localization of Brain Areas

13 0.70598865 98 nips-2010-Functional form of motion priors in human motion perception

14 0.69515443 194 nips-2010-Online Learning for Latent Dirichlet Allocation

15 0.69256097 268 nips-2010-The Neural Costs of Optimal Control

16 0.68213648 44 nips-2010-Brain covariance selection: better individual functional connectivity models using population prior

17 0.67957866 19 nips-2010-A rational decision making framework for inhibitory control

18 0.67247212 123 nips-2010-Individualized ROI Optimization via Maximization of Group-wise Consistency of Structural and Functional Profiles

19 0.6674003 17 nips-2010-A biologically plausible network for the computation of orientation dominance

20 0.65770984 244 nips-2010-Sodium entry efficiency during action potentials: A novel single-parameter family of Hodgkin-Huxley models