Arik Azran
ABSTRACT
We consider the problem of multiclass classification where both labeled and unlabeled data points are given. We introduce and demonstrate a new approach for estimating a distribution over the missing labels where data points are viewed as nodes of a graph, and pairwise similarities are used to derive a transition probability matrix P for a Markov random walk between them. The algorithm associates each point with a particle which moves between points according to P. Labeled points are set to be absorbing states of the Markov random walk, and the probability of each particle to be absorbed by the different labeled points, as the number of steps increases, is then used to derive a distribution over the associated missing label. A computationally efficient algorithm to implement this is derived and demonstrated on both real and artificial data sets, including a numerical comparison with other methods.
- Azran, A., & Ghahramani, Z. (2006). Spectral Methods for Automatic Multiscale Data Clustering. IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Google Scholar
Digital Library
- Belkin, M., & Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation. Google ScholarDigital Library
- Belkin, M., Niyogi, P., & Sindhwani, V. (2005). On manifold regularization. International Workshop on Artificial Intelligence and Statistics (AISTATS).Google Scholar
- Bengio, Y., Delalleau, O., & Roux, N. L. (2006). Label propagation and quadratic criterion. Semi-Supervised Learning, Eds. O. Chapelle, B. Schlkopf and A. Zien. MIT Press.Google Scholar
- Burges, C., & Platt, J. (2006). Semi-supervised learning with conditional harmonic mixing. Semi-Supervised Learning, Eds. O. Chapelle, B. Schlkopf and A. Zien. MIT Press.Google Scholar
- Chapelle, O., Schölkopf, B., & Zien, A. (Eds.). (2006). Semi-Supervised Learning. Cambridge, MA: MIT Press.Google Scholar
- Chapelle, O., & Zien, A. (2005). Semi-supervised classification by low density separation. Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics.Google Scholar
- Joachims, T. (1999). Transductive inference for text classification using support vector machines. International Conference on Machine Learning (ICML). Google ScholarDigital Library
- Joachims, T. (2003). Transductive learning via spectral graph partitioning. International Conference on Machine Learning (ICML).Google Scholar
- Meila, M. (2001). The multicut lemma. UW Statistics Technical Report 417.Google Scholar
- Meila, M., & Shi, J. (2001). A random walks view of spectral segmentation. Tenth International Workshop on Artificial Intelligence and Statistics (AISTATS).Google Scholar
- Seeger, M. (2002). Learning with Labeled and Unlabeled Data (Technical Report). University of Edinbrough.Google Scholar
- Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence. Google ScholarDigital Library
- Szummer, M., & Jaakkola, T. (2002). Partially Labeled Classification with Markov Random Walks. Advances in Neural Information Processing Systems (NIPS), 14.Google Scholar
- Weinberger, K. Q., & Saul, L. K. (2004). Unsupervised learning of image manifolds by semidefinite programming. IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Google ScholarDigital Library
- Weston, J., Leslie, C. S., Ie, E., Zhou, D., Elisseeff, A., & Noble, W. S. (2005). Semi-supervised protein classification using cluster kernels. Bioinformatics. Google ScholarDigital Library
- Zhou, D., & Schlkopf, B. (2004). Learning from labeled and unlabeled data using random walks. Pattern Recognition, Proceedings of the 26th DAGM Symposium.Google Scholar
- Zhou, D., & Schlkopf, B. (2006). Discrete regularization. Semi-Supervised Learning, Eds. O. Chapelle, B. Schlkopf and A. Zien. MIT Press.Google Scholar
- Zhu, X. (2006). Semi-Supervised Learning Literature Survey (Technical Report 1530). Computer Science, University of Wisconsin-Madison.Google Scholar
- Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using gaussian fields and harmonic functions. Advances in Neural Information Processing Systems (NIPS), 16.Google Scholar
- Zhu, X., Lafferty, J., Ghahramani, Z., & kandola, J. (2004). Nonparametric transforms of graph kernels for semi-supervised learning. International Conference on Machine Learning (ICML).Google Scholar
- The rendezvous algorithm: multiclass semi-supervised learning with Markov random walks
Recommendations
Analysis of a randomized rendezvous algorithm
In this paper we propose and analyze a randomized algorithm to get rendezvous between neighbours in an anonymous graph. We examine in particular the probability to obtain at least one rendezvous and the expected number of rendezvous. We study the ...
Time-Optimal Multi-impulse Rendezvous Based on Genetic Algorithm
ISDEA '10: Proceedings of the 2010 International Conference on Intelligent System Design and Engineering Application - Volume 02For the short-range rendezvous problem, an approach of time-optimal multi-impulse rendezvous was put forward using hybrid genetic algorithm. Firstly, based on the state transition matrix of T-H equation, the mathematical models of time-optimal multi-...
Randomized Rendezvous Algorithms for Agents on a Ring with Different Speeds
ICDCN '15: Proceedings of the 16th International Conference on Distributed Computing and NetworkingWe provide randomized rendezvous algorithms for two synchronous robots in a bi-directional ring of length n (n is a real number): the robots are equipped with identical chronometers, execute identical algorithms, but have different speeds u, 1 (where u >...
Comments