|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
How to Use Expert Advice in the Case when Actual Values of Estimated Events Remain Unknownстатья
- Авторы: Mitina Olga, Vereshchagin Nikolai K.
- Сборник: Proceedings of the Eigth Annual Conference on Computational Learning Theory, COLT 1995, Santa Cruz, California, USA, July 5-8, 1995
- Год издания: 1995
- Место издания: ACM
- Первая страница: 91
- Последняя страница: 97
- DOI: 10.1145/225298.225309
- Аннотация: The problem how to use experts whose competence is unknown has been studied in several recent papers. It has been assumed that after we have made a prediction we learn the actual value of the predicted event. In some situations, however, we do not learn the actual outcomes. This is the case, for example, in diagnosing a disease, in some kinds of competitions, in making political decisions and so on. In the present paper we consider a model in which we never get to know actual outcomes. The predicted events are binary. Each expert independently on other experts estimates each outcome correctly with some probability depending on expert. His/her estimates of different events are mutually independent, too. The performance of a strategy of using expert advice is measured as the probability of correct estimate on the worst-case outcome sequence. Our main result is the polynomial time strategy such that for any group having at least 3 experts the difference between its performance and the performance of the strategy being optimal for this expert group is $O(\sqrt{\log n / n})$, where n stands for the number of outcomes.
- Добавил в систему: Верещагин Николай Константинович