Learning Permutations with Exponential Weights
Abstract
We give an algorithm for learning a permutation on-line. The algorithm maintains its uncertainty about the target permutation as a doubly stochastic matrix. This matrix is updated by multiplying the current matrix entries by exponential factors. These factors destroy the doubly stochastic property of the matrix and an iterative procedure is needed to re-normalize the rows and columns. Even though the result of the normalization procedure does not have a closed form, we can still bound the additional loss of our algorithm over the loss of the best permutation chosen in hindsight.
Cite
Text
Helmbold and Warmuth. "Learning Permutations with Exponential Weights." Annual Conference on Computational Learning Theory, 2007. doi:10.1007/978-3-540-72927-3_34Markdown
[Helmbold and Warmuth. "Learning Permutations with Exponential Weights." Annual Conference on Computational Learning Theory, 2007.](https://mlanthology.org/colt/2007/helmbold2007colt-learning/) doi:10.1007/978-3-540-72927-3_34BibTeX
@inproceedings{helmbold2007colt-learning,
title = {{Learning Permutations with Exponential Weights}},
author = {Helmbold, David P. and Warmuth, Manfred K.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2007},
pages = {469-483},
doi = {10.1007/978-3-540-72927-3_34},
url = {https://mlanthology.org/colt/2007/helmbold2007colt-learning/}
}