PAC Learnability of Node Functions in Networked Dynamical Systems

Abhijin Adiga, Chris J Kuhlman, Madhav Marathe, S Ravi, Anil Vullikanti
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:82-91, 2019.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-adiga19a, title = {{PAC} Learnability of Node Functions in Networked Dynamical Systems}, author = {Adiga, Abhijin and Kuhlman, Chris J and Marathe, Madhav and Ravi, S and Vullikanti, Anil}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {82--91}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/adiga19a/adiga19a.pdf}, url = {https://proceedings.mlr.press/v97/adiga19a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T PAC Learnability of Node Functions in Networked Dynamical Systems %A Abhijin Adiga %A Chris J Kuhlman %A Madhav Marathe %A S Ravi %A Anil Vullikanti %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-adiga19a %I PMLR %P 82--91 %U https://proceedings.mlr.press/v97/adiga19a.html %V 97 %X 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.
APA
Adiga, A., Kuhlman, C.J., Marathe, M., Ravi, S. & Vullikanti, A.. (2019). PAC Learnability of Node Functions in Networked Dynamical Systems. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:82-91 Available from https://proceedings.mlr.press/v97/adiga19a.html.

Related Material