\dm_csml_event_details UCL ELLIS

Online Similarity Prediction of Networked Data


Stephen Pasteris


UCL, Computer Science


Friday, 10 January 2014






Malet Place Engineering Building 1.02

Event series

DeepMind/ELLIS CSML Seminar Series


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 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
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.