Online Similarity Prediction of Networked Data from Known and Unknown Graphs

Claudio Gentile, Mark Herbster, Stephen Pasteris
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:662-695, 2013.

Abstract

We consider online similarity prediction problems over networked data. We begin by relating this task to the more standard class prediction problem, showing that, given an arbitrary algorithm for class prediction, we can construct an algorithm for similarity prediction with “nearly” the same mistake bound, and vice versa. After noticing that this general construction is computationally infeasible, we target our study to feasible similarity prediction algorithms on networked data. We initially assume that the network structure is known to the learner. Here we observe that Matrix Winnow (Warmuth, 2007) has a near-optimal mistake guarantee, at the price of cubic prediction time per round. This motivates our effort for an efficient implementation of a Perceptron-like algorithm with a weaker mistake guarantee but with only poly-logarithmic prediction time. Our focus then turns to the challenging case of networks whose structure is initially unknown to the learner. In this novel setting, where the network structure is only incrementally revealed, we obtain a mistake-bounded algorithm with a quadratic prediction time per round.

Cite this Paper

BibTeX
@InProceedings{pmlr-v30-Gentile13, title = {Online Similarity Prediction of Networked Data from Known and Unknown Graphs}, author = {Gentile, Claudio and Herbster, Mark and Pasteris, Stephen}, booktitle = {Proceedings of the 26th Annual Conference on Learning Theory}, pages = {662--695}, year = {2013}, editor = {Shalev-Shwartz, Shai and Steinwart, Ingo}, volume = {30}, series = {Proceedings of Machine Learning Research}, address = {Princeton, NJ, USA}, month = {12--14 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v30/Gentile13.pdf}, url = {https://proceedings.mlr.press/v30/Gentile13.html}, abstract = {We consider online similarity prediction problems over networked data. We begin by relating this task to the more standard class prediction problem, showing that, given an arbitrary algorithm for class prediction, we can construct an algorithm for similarity prediction with “nearly” the same mistake bound, and vice versa. After noticing that this general construction is computationally infeasible, we target our study to feasible similarity prediction algorithms on networked data. We initially assume that the network structure is known to the learner. Here we observe that Matrix Winnow (Warmuth, 2007) has a near-optimal mistake guarantee, at the price of cubic prediction time per round. This motivates our effort for an efficient implementation of a Perceptron-like algorithm with a weaker mistake guarantee but with only poly-logarithmic prediction time. Our focus then turns to the challenging case of networks whose structure is initially unknown to the learner. In this novel setting, where the network structure is only incrementally revealed, we obtain a mistake-bounded algorithm with a quadratic prediction time per round.} }
Endnote
%0 Conference Paper %T Online Similarity Prediction of Networked Data from Known and Unknown Graphs %A Claudio Gentile %A Mark Herbster %A Stephen Pasteris %B Proceedings of the 26th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2013 %E Shai Shalev-Shwartz %E Ingo Steinwart %F pmlr-v30-Gentile13 %I PMLR %P 662--695 %U https://proceedings.mlr.press/v30/Gentile13.html %V 30 %X We consider online similarity prediction problems over networked data. We begin by relating this task to the more standard class prediction problem, showing that, given an arbitrary algorithm for class prediction, we can construct an algorithm for similarity prediction with “nearly” the same mistake bound, and vice versa. After noticing that this general construction is computationally infeasible, we target our study to feasible similarity prediction algorithms on networked data. We initially assume that the network structure is known to the learner. Here we observe that Matrix Winnow (Warmuth, 2007) has a near-optimal mistake guarantee, at the price of cubic prediction time per round. This motivates our effort for an efficient implementation of a Perceptron-like algorithm with a weaker mistake guarantee but with only poly-logarithmic prediction time. Our focus then turns to the challenging case of networks whose structure is initially unknown to the learner. In this novel setting, where the network structure is only incrementally revealed, we obtain a mistake-bounded algorithm with a quadratic prediction time per round.
RIS
TY - CPAPER TI - Online Similarity Prediction of Networked Data from Known and Unknown Graphs AU - Claudio Gentile AU - Mark Herbster AU - Stephen Pasteris BT - Proceedings of the 26th Annual Conference on Learning Theory DA - 2013/06/13 ED - Shai Shalev-Shwartz ED - Ingo Steinwart ID - pmlr-v30-Gentile13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 30 SP - 662 EP - 695 L1 - http://proceedings.mlr.press/v30/Gentile13.pdf UR - https://proceedings.mlr.press/v30/Gentile13.html AB - We consider online similarity prediction problems over networked data. We begin by relating this task to the more standard class prediction problem, showing that, given an arbitrary algorithm for class prediction, we can construct an algorithm for similarity prediction with “nearly” the same mistake bound, and vice versa. After noticing that this general construction is computationally infeasible, we target our study to feasible similarity prediction algorithms on networked data. We initially assume that the network structure is known to the learner. Here we observe that Matrix Winnow (Warmuth, 2007) has a near-optimal mistake guarantee, at the price of cubic prediction time per round. This motivates our effort for an efficient implementation of a Perceptron-like algorithm with a weaker mistake guarantee but with only poly-logarithmic prediction time. Our focus then turns to the challenging case of networks whose structure is initially unknown to the learner. In this novel setting, where the network structure is only incrementally revealed, we obtain a mistake-bounded algorithm with a quadratic prediction time per round. ER -
APA
Gentile, C., Herbster, M. & Pasteris, S.. (2013). Online Similarity Prediction of Networked Data from Known and Unknown Graphs. Proceedings of the 26th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 30:662-695 Available from https://proceedings.mlr.press/v30/Gentile13.html.

Related Material