Material Detail
A Fast Active Learning Algorithm for Link Classification
This video was recorded at Video Journal of Machine Learning Abstracts - Volume 4. We present a very efficient active learning algorithm for link classification in signed networks. Our algorithm is motivated by a stochastic model in which edge labels are obtained through perturbations of an initial sign assignment consistent with a two-clustering of the nodes. We provide a theoretical analysis within this model, showing that we can achieve an optimal (to within a constant factor) number of mistakes on any graph G = (V;E) such that |E| = \Omega(|V|^3/2) by querying O(|V|^3/2) edge labels. More generally, we show an algorithm that achieves optimality to within a factor of O(k) by querying at most order of |V| + (|V|/k)^3/2 edge labels. The running time of this algorithm is at most of order |E| + |V| log |V|.
Quality
- User Rating
- Comments
- Learning Exercises
- Bookmark Collections
- Course ePortfolios
- Accessibility Info
More about this material
- Mobile Compatibility:
- Not specified at this time
- Language:
- English
- Cost Involved:
- No
- Source Code Available:
- No
- Creative Commons:
-
This work is licensed under a Attribution-NonCommercial-NoDerivs 3.0 United States
