Timezone: »
Oral
A graph-theoretic approach to multitasking
Noga Alon · Daniel Reichman · Igor Shinkar · Tal Wagner · Sebastian Musslick · Jonathan D Cohen · Tom Griffiths · Biswadip dey · Kayhan Ozcimder
A key feature of neural network architectures is their ability to support the simultaneous interaction among large numbers of units in the learning and processing of representations. However, how the richness of such interactions trades off against the ability of a network to simultaneously carry out multiple independent processes -- a salient limitation in many domains of human cognition -- remains largely unexplored. In this paper we use a graph-theoretic analysis of network architecture to address this question, where tasks are represented as edges in a bipartite graph $G=(A \cup B, E)$. We define a new measure of multitasking capacity of such networks, based on the assumptions that tasks that \emph{need} to be multitasked rely on independent resources, i.e., form a matching, and that tasks \emph{can} be performed without interference if they form an induced matching. Our main result is an inherent tradeoff between the multitasking capacity and the average degree of the network that holds \emph{regardless of the network architecture}. These results are also extended to networks of depth greater than $2$. On the positive side, we demonstrate that networks that are random-like (e.g., locally sparse) can have desirable multitasking properties. Our results shed light into the parallel-processing limitations of neural systems and provide insights that may be useful for the analysis and design of parallel architectures.
Author Information
Noga Alon (Tel Aviv University)
Daniel Reichman (University of California, Berkeley)
Igor Shinkar (UC Berkeley)
Tal Wagner (MIT)
Sebastian Musslick
Jonathan D Cohen (Princeton University)
Tom Griffiths (Princeton)
Biswadip dey (Princeton University)
Kayhan Ozcimder (Princeton University)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Poster: A graph-theoretic approach to multitasking »
Wed. Dec 6th 02:30 -- 06:30 AM Room Pacific Ballroom #216
More from the Same Authors
-
2022 : When to choose: The role of information seeking in the speed-accuracy tradeoff »
Javier Alejandro Masís Obando · David Melnikoff · Lisa Feldman Barrett · Jonathan D Cohen -
2023 Poster: Systematic Visual Reasoning through Object-Centric Relational Abstraction »
Taylor Webb · Shanka Subhra Mondal · Jonathan D Cohen -
2022 Poster: Size and depth of monotone neural networks: interpolation and approximation »
Dan Mikulincer · Daniel Reichman -
2022 Poster: Using natural language and program abstractions to instill human inductive biases in machines »
Sreejan Kumar · Carlos G. Correa · Ishita Dasgupta · Raja Marjieh · Michael Y Hu · Robert Hawkins · Jonathan D Cohen · nathaniel daw · Karthik Narasimhan · Tom Griffiths -
2022 Poster: A Benchmark for Compositional Visual Reasoning »
Aimen Zerroug · Mohit Vaishnav · Julien Colin · Sebastian Musslick · Thomas Serre -
2022 Poster: Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks »
Anders Aamand · Justin Chen · Piotr Indyk · Shyam Narayanan · Ronitt Rubinfeld · Nicholas Schiefer · Sandeep Silwal · Tal Wagner -
2021 Workshop: Workshop on Human and Machine Decisions »
Daniel Reichman · Joshua Peterson · Kiran Tomlinson · Annie Liang · Tom Griffiths -
2021 Poster: Few-Shot Data-Driven Algorithms for Low Rank Approximation »
Piotr Indyk · Tal Wagner · David Woodruff -
2018 : Research Panel »
Sinead Williamson · Barbara Engelhardt · Tom Griffiths · Neil Lawrence · Hanna Wallach -
2017 : Revealing human inductive biases and metacognitive processes with rational models »
Tom Griffiths -
2017 Poster: Practical Data-Dependent Metric Compression with Provable Guarantees »
Piotr Indyk · Ilya Razenshteyn · Tal Wagner -
2016 : Bounded Optimality and Rational Metareasoning in Human Cognition »
Tom Griffiths -
2015 Workshop: Bounded Optimality and Rational Metareasoning »
Samuel J Gershman · Falk Lieder · Tom Griffiths · Noah Goodman -
2015 Poster: On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank-One Perturbations of Gaussian Tensors »
Andrea Montanari · Daniel Reichman · Ofer Zeitouni -
2015 Poster: A Theory of Decision Making Under Dynamic Context »
Michael Shvartsman · Vaibhav Srivastava · Jonathan D Cohen -
2014 Poster: Algorithm selection by rational metareasoning as a model of human strategy selection »
Falk Lieder · Dillon Plunkett · Jessica B Hamrick · Stuart J Russell · Nicholas Hay · Tom Griffiths -
2013 Poster: Visual Concept Learning: Combining Machine Vision and Bayesian Generalization on Concept Hierarchies »
Yangqing Jia · Joshua T Abbott · Joseph L Austerweil · Tom Griffiths · Trevor Darrell -
2012 Poster: Human memory search as a random walk in a semantic network »
Joshua T Abbott · Joseph L Austerweil · Tom Griffiths -
2012 Spotlight: Human memory search as a random walk in a semantic network »
Joshua T Abbott · Joseph L Austerweil · Tom Griffiths -
2012 Poster: Burn-in, bias, and the rationality of anchoring »
Falk Lieder · Tom Griffiths · Noah Goodman -
2011 Poster: A rational model of causal inference with continuous causes »
M Pacer · Tom Griffiths -
2011 Poster: An ideal observer model for identifying the reference frame of objects »
Joseph L Austerweil · Abram Friesen · Tom Griffiths -
2011 Poster: Testing a Bayesian Measure of Representativeness Using a Large Image Database »
Joshua T Abbott · Katherine Heller · Zoubin Ghahramani · Tom Griffiths -
2010 Workshop: Transfer Learning Via Rich Generative Models. »
Russ Salakhutdinov · Ryan Adams · Josh Tenenbaum · Zoubin Ghahramani · Tom Griffiths -
2010 Spotlight: Learning invariant features using the Transformed Indian Buffet Process »
Joseph L Austerweil · Tom Griffiths -
2010 Poster: Learning invariant features using the Transformed Indian Buffet Process »
Joseph L Austerweil · Tom Griffiths -
2009 Workshop: Bounded-rational analyses of human cognition: Bayesian models, approximate inference, and the brain »
Noah Goodman · Edward Vul · Tom Griffiths · Josh Tenenbaum -
2009 Poster: Neural Implementation of Hierarchical Bayesian Inference by Importance Sampling »
Lei ShiUpdateMe · Tom Griffiths -
2009 Spotlight: Neural Implementation of Hierarchical Bayesian Inference by Importance Sampling »
Lei ShiUpdateMe · Tom Griffiths -
2009 Poster: Differential Use of Implicit Negative Evidence in Generative and Discriminative Language Learning »
Anne Hsu · Tom Griffiths -
2009 Oral: Differential Use of Implicit Negative Evidence in Generative and Discriminative Language Learning »
Anne Hsu · Tom Griffiths -
2009 Poster: Nonparametric Latent Feature Models for Link Prediction »
Kurt T Miller · Tom Griffiths · Michael Jordan -
2009 Spotlight: Nonparametric Latent Feature Models for Link Prediction »
Kurt T Miller · Tom Griffiths · Michael Jordan -
2008 Workshop: Machine learning meets human learning »
Nathaniel D Daw · Tom Griffiths · Josh Tenenbaum · Jerry Zhu -
2008 Poster: Modeling the effects of memory on human online sentence processing with particle filters »
Roger Levy · Florencia Reali · Tom Griffiths -
2008 Oral: Modeling the effects of memory on human online sentence processing with particle filters »
Roger Levy · Florencia Reali · Tom Griffiths -
2008 Poster: How memory biases affect information transmission: A rational analysis of serial reproduction »
Jing Xu · Tom Griffiths -
2008 Poster: Analyzing human feature learning as nonparametric Bayesian inference »
Joseph L Austerweil · Tom Griffiths -
2008 Poster: Sequential effects: Superstition or rational behavior? »
Angela Yu · Jonathan D Cohen -
2008 Poster: A rational model of preference learning and choice prediction by children »
Chris Lucas · Tom Griffiths · Fei Xu · Christine Fawcett -
2008 Poster: Learning to Use Working Memory in Partially Observable Environments through Dopaminergic Reinforcement »
Michael Todd · Yael Niv · Jonathan D Cohen -
2008 Spotlight: Sequential effects: Superstition or rational behavior? »
Angela Yu · Jonathan D Cohen -
2008 Oral: Learning to Use Working Memory in Partially Observable Environments through Dopaminergic Reinforcement »
Michael Todd · Yael Niv · Jonathan D Cohen -
2008 Spotlight: Analyzing human feature learning as nonparametric Bayesian inference »
Joseph L Austerweil · Tom Griffiths -
2008 Spotlight: A rational model of preference learning and choice prediction by children »
Chris Lucas · Tom Griffiths · Fei Xu · Christine Fawcett -
2008 Spotlight: How memory biases affect information transmission: A rational analysis of serial reproduction »
Jing Xu · Tom Griffiths -
2008 Poster: Modeling human function learning with Gaussian processes »
Tom Griffiths · Chris Lucas · Joseph Jay Williams · Michael Kalish -
2007 Oral: Markov Chain Monte Carlo with People »
Adam Sanborn · Tom Griffiths -
2007 Poster: Markov Chain Monte Carlo with People »
Adam Sanborn · Tom Griffiths -
2007 Poster: A Probabilistic Approach to Language Change »
Alexandre Bouchard-Côté · Percy Liang · Tom Griffiths · Dan Klein -
2006 Poster: Particle Filtering for Nonparametric Bayesian Matrix Factorization »
Frank Wood · Tom Griffiths -
2006 Poster: Adaptor Grammars: A Framework for Specifying Compositional Nonparametric Bayesian Mod »
Mark Johnson · Tom Griffiths · Sharon Goldwater -
2006 Poster: A Nonparametric Bayesian Method for Inferring Features From Similarity Judgments »
Daniel Navarro · Tom Griffiths