2014 dxdy logo

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

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




 
 Связь энтропии сигнала и скорости алгоритма его обработки
Сообщение14.08.2014, 19:50 
Можно ли по энтропии потока сообщений оценить снизу среднее количество шагов, которым должен обладать лучший из возможных алгоритмов их классификации?

Пример: линейный поиск в массиве элементов без отношения порядка. Есть искомый элемент $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 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group