UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Online Similarity Prediction of Networked Data from Known and Unknown Graphs

Gentile, C; Herbster, M; Pasteris, S; (2013) Online Similarity Prediction of Networked Data from Known and Unknown Graphs. In: Shalev-Shwartz, S and Steinwart, I, (eds.) COLT 2013: 26th Conference on Learning Theory: Proceedings. (pp. pp. 662-695). Journal of Machine Learning Research Green open access

[thumbnail of Gentile_Online_Similarity_Prediction.pdf]
Preview
Text
Gentile_Online_Similarity_Prediction.pdf - Published Version

Download (790kB) | Preview

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 {\em feasible} similarity prediction algorithms on networked data. We initially assume that the network structure is {\em known} to the learner. Here we observe that Matrix Winnow \cite{w07} 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 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 {\em 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.

Type: Proceedings paper
Title: Online Similarity Prediction of Networked Data from Known and Unknown Graphs
Event: COLT 2013: Conference on Learning Theory, 12-14 June 2013, Princeton, New Jersey, USA
Open access status: An open access version is available from UCL Discovery
Publisher version: http://proceedings.mlr.press/v30/
Language: English
Additional information: Published under a Creative Commons Attribution 4.0 International Licence (http://creativecommons.org/licenses/by/4.0).
Keywords: graph transduction, similarity prediction, online learning
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/1390636
Downloads since deposit
18Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item