PAC Learnability of Node Functions in Networked Dynamical Systems
Abhijin Adiga · Chris J Kuhlman · Madhav Marathe · S. S. Ravi · Anil Vullikanti

Tue Jun 11th 11:35 -- 11:40 AM @ Room 103

We consider the PAC learnability of the local functions at the vertices of a discrete networked dynamical system, assuming that the underlying network is known. Our focus is on the learnability of threshold functions. We show that several variants of threshold functions are PAC learnable and provide tight bounds on the sample complexity. In general, when the input consists of positive and negative examples, we show that the concept class of threshold functions is not efficiently PAC learnable, unless NP = RP. Using a dynamic programming approach, we show efficient PAC learnability when the number of negative examples is small. We also present an efficient learner which is consistent with all the positive examples and at least (1-1/e) fraction of the negative examples. This algorithm is based on maximizing a submodular function under matroid constraints. By performing experiments on both synthetic and real-world networks, we study how the network structure and sample complexity influence the quality of the inferred system.

Author Information

Abhijin Adiga (University of Virginia)
Chris J Kuhlman (Biocomplexity Institute & Initiative, University of Virginia)
Madhav Marathe (Biocomplexity Institute & Initiative, University of Virginia)
S. S. Ravi (University of Virginia and University at Albany -- SUNY)
Anil Vullikanti (Biocomplexity Institute and Dept of Computer Science, University of Virginia)

Related Events (a corresponding poster, oral, or spotlight)