Archive for Февраль 2012

Предсказание последовательности с помощью экспертов

Февраль 7, 2012

Представьте себе конечную последовательность нулей и единиц, которая появляется бит за битом. Перед появлением очередного бита мы хотим его предсказать. Для этого у нас есть {n} экспертов: каждый из них перед появлением бита говорит, чему по его мнению он будет равен. Пусть {R_i} — число ошибок {i}-го эксперта. Если бы мы заранее знали, какой эксперт самый хороший, то мы бы могли обойтись {\min(R_1, R_2, \ldots, R_n)} ошибками. Однако, даже без такого априорного знания мы можем обойтись

\displaystyle   \frac{2 \ln n}{\varepsilon} + 2 (1 + \varepsilon) \cdot \min(R_1, R_2, \ldots, R_n) \ \ \ \ \ (1)

ошибками, где {\varepsilon} — сколько угодно маленькая положительная константа.

Алгоритм очень простой. Давайте приписывать экспертам веса {w_1, w_2, \ldots, w_n}. Изначально положим все {w_i} единицам. Биты предсказывать будем так: посчитаем сумму весов экспертов, которые проголосовали за ноль, и сумму тех, кто проголосовал за единицу. Назовем значение, суммарный вес которого больше. После того, как мы узнали настоящее значение бита, умножим веса всех экспертов, которые ошиблись, на {1 - \varepsilon}.

Докажем, что количество ошибок при такой стратегии ограничено (1). Будем следить за потенциалом {\Phi := w_1 + w_2 + \ldots + w_n}. Изначально {\Phi = n}. Докажем, что при каждой нашей ошибке {\Phi} домножается не более, чем на {1 - \varepsilon / 2}. Действительно, при нашей ошибке суммарный вес экспертов, которые ошиблись, составляет по крайней мере {\Phi / 2}. Значит, после обновления весов экспертов новое значение {\Phi} не превзойдет

\displaystyle  \Phi \cdot \left(\frac12 + \frac12 \cdot (1 - \varepsilon) \right) = \Phi \cdot \left(1 - \frac{\varepsilon}{2}\right).

Таким образом, если мы сделали {k} ошибок, то {\Phi \leq n \cdot (1 - \varepsilon / 2)^k}. Но так как в каждый момент {w_i \leq \Phi}, то имеем

\displaystyle  (1 - \varepsilon)^{R_i} \leq n \cdot \left(1 - \varepsilon / 2\right)^k

для любого {i}. Отсюда после несложных преобразований получаем (1).

Реклама