2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Связь энтропии сигнала и скорости алгоритма его обработки
Сообщение14.08.2014, 19:50 


14/08/14
1
Можно ли по энтропии потока сообщений оценить снизу среднее количество шагов, которым должен обладать лучший из возможных алгоритмов их классификации?

Пример: линейный поиск в массиве элементов без отношения порядка. Есть искомый элемент $A$, содержащийся не более одного раза, и есть сообщение-массив длиной $N$ вида 0000100, где 0 либо 1 на данной позиции показывает, равен или не равен элемент на данной позиции искомому элементу $A$. Обрабатывая такое сообщение, алгоритм выносит вердикт "не содержит" (множество из единственного элемента 0000...0 ), либо "содержит" (множесто остальных сообщений). В случае равновероятности как равенства, так и неравенства на данной позиции, энтропия вердиктов как случайной величины равна:
$H=-\frac{1 }{N+1}\cdot{\operatorname{\log_2}(\frac{1}{N+1})}-\frac{N }{N+1}\cdot{\operatorname{\log_2}(\frac{N}{N+1})}$
Эта величина меньше единицы и стремится к нулю с ростом $N$:
Изображение
Так как энтропия, округленная до целого сверху, есть средняя длина сообщения при оптимальном кодировании сигнала, то, выходит, существует способ проиндексировать каждое сообщение бинарной строкой средней длиной 1, т.е. в среднем всего лишь за один шаг получить правильный ответ-вердикт.

Однако брутфорсный алгоритм линейного поиска, как известно, в среднем дает $\frac{N+1}{2}$ шагов. Все его улучшения (типа бинарного поиска) требуют привнесения отношения порядка, а у нас - лишь равен/не равен, т.е. есть отношение эквивалентности.

Выходит, что энтропия вердиктов не равна среднему числу шагов некоего лучшего алгоритма?

Тогда вопрос - как связаны эти величины? Возможно, существует добавочный член в виде сложности самой индексации сообщения бинарными строками оптимального кодирования?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group