2008
NIPS
NeurIPS 2008
Online Prediction on Large Diameter Graphs
Abstract
Current on-line learning algorithms for predicting the labelling of a graph have an important limitation in the case of large diameter graphs; the number of mistakes made by such algorithms may be proportional to the square root of the number of vertices, even when tackling simple problems. We overcome this problem with an efficient algorithm which achieves a logarithmic mistake bound. Furthermore, current algorithms are optimised for data which exhibits cluster-structure; we give an additional algorithm which performs well locally in the presence of cluster structure and on large diameter graphs.
🌉
Interdisciplinary Bridge
— Knowledge & Reasoning and Machine Learning and Mathematics & Optimization
📈
Trend Setter
— Knowledge Graphs
🧭
Keyword Pioneer
— online prediction
🐣
Hot Topic Early Bird
— online learning
🐝
Cross-Pollinator
— Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio
Authors
Topics
Machine Learning > Core Methods > Classification
Knowledge & Reasoning > Representation > Knowledge Graphs
Mathematics & Optimization > Mathematics > Graph Theory
Mathematics & Optimization > Optimization > Online Algorithms
Machine Learning > Learning Types > Online Learning
Machine Learning > Optimization & Theory > Online Algorithms
Computer Science > Foundations > Graph Theory