Learning from Networked Examples

Yuyi Wang, Zheng-Chu Guo, Jan Ramon
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:641-666, 2017.

Abstract

Many machine learning algorithms are based on the assumption that training examples are drawn independently. However, this assumption does not hold anymore when learning from a networked sample because two or more training examples may share some common objects, and hence share the features of these shared objects. We show that the classic approach of ignoring this problem potentially can have a harmful effect on the accuracy of statistics, and then consider alternatives. One of these is to only use independent examples, discarding other information. However, this is clearly suboptimal. We analyze sample error bounds in this networked setting, providing significantly improved results. An important component of our approach is formed by efficient sample weighting schemes, which leads to novel concentration inequalities.

Cite this Paper

BibTeX
@InProceedings{pmlr-v76-wang17a, title = {Learning from Networked Examples}, author = {Wang, Yuyi and Guo, Zheng-Chu and Ramon, Jan}, booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory}, pages = {641--666}, year = {2017}, editor = {Hanneke, Steve and Reyzin, Lev}, volume = {76}, series = {Proceedings of Machine Learning Research}, month = {15--17 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v76/wang17a/wang17a.pdf}, url = {https://proceedings.mlr.press/v76/wang17a.html}, abstract = {Many machine learning algorithms are based on the assumption that training examples are drawn independently. However, this assumption does not hold anymore when learning from a networked sample because two or more training examples may share some common objects, and hence share the features of these shared objects. We show that the classic approach of ignoring this problem potentially can have a harmful effect on the accuracy of statistics, and then consider alternatives. One of these is to only use independent examples, discarding other information. However, this is clearly suboptimal. We analyze sample error bounds in this networked setting, providing significantly improved results. An important component of our approach is formed by efficient sample weighting schemes, which leads to novel concentration inequalities.} }
Endnote
%0 Conference Paper %T Learning from Networked Examples %A Yuyi Wang %A Zheng-Chu Guo %A Jan Ramon %B Proceedings of the 28th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Steve Hanneke %E Lev Reyzin %F pmlr-v76-wang17a %I PMLR %P 641--666 %U https://proceedings.mlr.press/v76/wang17a.html %V 76 %X Many machine learning algorithms are based on the assumption that training examples are drawn independently. However, this assumption does not hold anymore when learning from a networked sample because two or more training examples may share some common objects, and hence share the features of these shared objects. We show that the classic approach of ignoring this problem potentially can have a harmful effect on the accuracy of statistics, and then consider alternatives. One of these is to only use independent examples, discarding other information. However, this is clearly suboptimal. We analyze sample error bounds in this networked setting, providing significantly improved results. An important component of our approach is formed by efficient sample weighting schemes, which leads to novel concentration inequalities.
APA
Wang, Y., Guo, Z. & Ramon, J.. (2017). Learning from Networked Examples. Proceedings of the 28th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 76:641-666 Available from https://proceedings.mlr.press/v76/wang17a.html.

Related Material