Энтропийная характеристика алгоритма

[Mihaylo]

Увлекаясь расчетами энтропии для различных задач, я обнаружил интересную вещь.

Смысл заключается в том, что у каждого алгоритма с каждой его выполненной инструкцией уменьшается энтропия от некоторого максимума и вплоть до нуля. Эту энтропию можно вычислить на каждом шаге алгоритма, соответственно можно получить характеристику $H(i)$, где $H$ - энтропия задачи, $i$ - шаг алгоритма. Если алгоритм правильно решает задачу, то энтропия будет равна нулю на последнем шаге $i$.
Интересно рассчитывать энтропийную характеристику $H(i)$ для итеративных и рекурсивных алгоритмов. В некоторых случаях эту характеристику можно получить аналитически.
Например, задача - найти максимальное число в массиве $X = \left\lbrace x_1, x_2, ..., x_n \right\rbrace$, применяется рекурсивный алгоритм вида $M_i = \max (M_{i-1};x_i)$ при $i=2..n$, $M_1 = x_1$, где $M_i$ - максимальное значение на шаге $i$. Энтропийная характеристика алгоритма $H(i)=\log_2(n-i)$. Видно, что перед началом работы алгоритма энтропия максимальна $H(0)=\log_2 n$, а после выполнения алгоритма наступает полная определенность $H(n-1) = \log_2 1 = 0$ (количество итераций алгоритма равно $n-1$).

У некоторых алгоритмов энтропия зависит от входных данных, поэтому для таких алгоритмов могут быть найдены не точные аналитические характеристики, а, например, верхние или нижние оценки или математическое ожидание. В крайнем случае непосредственно в исследуемый алгоритм можно интегрировать алгоритм вычисления энтропии и получать энтропийные характеристики для конкретных входных данных, например, для алгоритма Евклида поиска НОД двух целых чисел.

Рассчитаны энтропийные характеристики для различных алгоритмов сортировок:
- сортировка вставкой (Insertion-Sort) - получен точный аналитический результат;
- пузырьковая сортировка (Bubble-Sort) - найдена нижняя оценка;
- быстрая сортировка (Quick-Sort) - найдено математическое ожидание;
- сортировка слиянием (Merge-Sort) - получен точный аналитический результат;
- пирамидальная сортировка (Heap-Sort) - написан алгоритм вычисления характеристики для конкретных входных данных.

Можно пробовать сопоставлять энтропийные характеристики $H(i)$ различных алгоритмов, решающих одну и ту же задачу. Но при этом следует понимать, что различные алгоритмы выполняются за различное количество итераций, а время выполнения итераций также может сильно разниться. Можно, например, допустить, что все алгоритмы выполняются за одинаковое время 100% и за счет предположения ось $i$ отмасштабируется (ось $H$ уже "отмасштабирована"). Хотя, конечно, вместо всяких допущений лучше отложить по горизонтальной оси реальное время работы алгоритма на заданной процессорной системе.

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

Задумываюсь: а что если энтропийные характеристики находить для алгоритмов machine learning? Это позволит оценивать эффективность работы алгоритма обучения и, например, оптимальным образом принимать решение на каждой итерации - остановиться, перейти на следующую эпоху, переключиться на другой алгоритм обучения и т.д. Для меня все это - непосильная задача, в математике несилен. Может кому-то это станет интересно?

[mihaild]

А определение "энтропии алгоритма" есть?

[Mihaylo]

Ну конечно же есть, только наверное правильнее говорить "энтропия задачи", ведь в процессе работы алгоритма уточняется решение задачи. Или можно говорить "энтропийная характеристика алгоритма" - это характеристика того, как алгоритм в процессе выполнения упорядочивает входные данные некоторой фиксированной задачи.
Это привычная энтропия по Хартли $H = \log N$, где $N$ - размер пространства возможных состояний задачи. Например, в алгоритмах сортировки $N$ - это число возможных комбинаций сортируемых объектов в отсортированном массиве. Следует четко определить (зафиксировать), какую задачу решает алгоритм, так как, например, алгоритмы сортировки помимо непосредственно сортировки решают задачу поиска максимального значения в массиве, а еще задачу поиска минимального значения и бесконечное число других задач.
Число $N$ и энтропия $H$ изменяются в процессе выполнения алгоритма, например, массив частично сортируется, поэтому имеет смысл рассматривать формулу $H(i) = \log N(i)$, где $i$ - номер шага алгоритма.

[Dmitriy40]

С сортировкой относительно просто ввести понятие энтропии, а вот как с задачей поиска цикла минимальной/максимальной длины в произвольном графе? Состояние задачи в процессе не меняется, тем более по последовательным шагам, как к процессу решения притянуть энтропию? И что будет исходным пространством состояний, полное количество всех возможных циклов на множестве вершин и без учёта реальных связей между вершинами? Ну так уменьшение этого количества [допустимых] состояний не строго привязано к шагам алгоритма, вроде бы.

[Xaositect]

Mihaylo в сообщении #1225084 писал(а):

Смысл заключается в том, что у каждого алгоритма с каждой его выполненной инструкцией уменьшается энтропия от некоторого максимума и вплоть до нуля. Эту энтропию можно вычислить на каждом шаге алгоритма, соответственно можно получить характеристику $H(i)$, где $H$ - энтропия задачи, $i$ - шаг алгоритма. Если алгоритм правильно решает задачу, то энтропия будет равна нулю на последнем шаге $i$.
Интересно рассчитывать энтропийную характеристику $H(i)$ для итеративных и рекурсивных алгоритмов. В некоторых случаях эту характеристику можно получить аналитически.
Например, задача - найти максимальное число в массиве $X = \left\lbrace x_1, x_2, ..., x_n \right\rbrace$, применяется рекурсивный алгоритм вида $M_i = \max (M_{i-1};x_i)$ при $i=2..n$, $M_1 = x_1$, где $M_i$ - максимальное значение на шаге $i$. Энтропийная характеристика алгоритма $H(i)=\log_2(n-i)$. Видно, что перед началом работы алгоритма энтропия максимальна $H(0)=\log_2 n$, а после выполнения алгоритма наступает полная определенность $H(n-1) = \log_2 1 = 0$ (количество итераций алгоритма равно $n-1$).

Непонятно, где тут участвует правильность алгоритма. Что будет, если мы будем искать максимум с помощью алгоритма $M_i = \min(M_{i - 1}, x_i)$, т.е. неправильно?

[Mihaylo]

Dmitriy40 в сообщении #1225375 писал(а):

как с задачей поиска цикла минимальной/максимальной длины в произвольном графе?

Сформулируйте эти задачи наиболее точно, от этого сильно зависит энтропия. Число вершин $n$ хотя бы известно по условию задачи?

Dmitriy40 в сообщении #1225375 писал(а):

Состояние задачи в процессе не меняется, тем более по последовательным шагам, как к процессу решения притянуть энтропию?

Надо смотреть алгоритм, ведь он меняет свое собственное представление о задаче, то есть энтропию.

Dmitriy40 в сообщении #1225375 писал(а):

И что будет исходным пространством состояний, полное количество всех возможных циклов на множестве вершин и без учёта реальных связей между вершинами?

Да, возможно полный граф будет служить верхней оценкой, либо найдутся другие подходы.

Dmitriy40 в сообщении #1225375 писал(а):

Ну так уменьшение этого количества [допустимых] состояний не строго привязано к шагам алгоритма, вроде бы.

Да, бывают алгоритмы, у которых энтропия резко уменьшается от входных данных. Оно и понятно, могут быть особые ситуации, когда становится все понятно и определенно с первых попыток поиска решения.

Xaositect в сообщении #1225377 писал(а):

Непонятно, где тут участвует правильность алгоритма. Что будет, если мы будем искать максимум с помощью алгоритма $M_i = \min(M_{i - 1}, x_i)$, т.е. неправильно?

Да, вы правы. Я упоминал "правильность" алгоритма лишь для того, чтобы подчеркнуть, что энтропию алгоритма нужно вычислять с умом, то есть правильно, обдуманно. Честно говоря, не готов говорить об алгоритмах, которые решают задачу неправильно. Наверное это запрещенная ситуация для вычисления энтропии.

[Mihaylo]

Для лучшего понимания идеи можно рассмотреть задачу о разборчивой невесте и оптимальный алгоритм ее решения.
Формулировка задачи и алгоритма взял из Википедии:

Цитата:

1. Невеста ищет себе жениха (существует единственное вакантное место).
2. Есть известное число претендентов — $n$.
3. Невеста общается с претендентами в случайном порядке, с каждым не более одного раза.
4. О каждом текущем претенденте известно, лучше он или хуже любого из предыдущих.
5. В результате общения с текущим претендентом невеста должна либо ему отказать, либо принять его предложение. Если предложение принято, процесс останавливается.
6. Цель — выбрать лучшего претендента.

Цитата:

если число кандидатов достаточно велико (порядка сотни), оптимальная стратегия будет заключаться в том, чтобы отклонить всех первых $n/e$ претендентов и затем выбрать первого, кто будет лучше всех предыдущих. При увеличении $n$ вероятность выбора наилучшего претендента стремится к $1/e$, то есть примерно к 37 %.

Итак, по условию задачи требуется найти номер претендента, на котором нужно остановиться. Перед началом работы алгоритм уже "знает", что желаемый претендент имеет номер от $n/e$ и вплоть до $n$, следовательно начальная энтропия равна $H(0)=\log(n-n/e+1)$. Пока идет отсев претендентов (первая часть алгоритма), энтропия не изменяется. При выполнении второй части алгоритма энтропия начинает падать. При чем энтропия может уменьшаться либо на небольшую величину, либо сразу до нуля (тогда происходит останов). Энтропия уменьшается по следующей закономерности: $H(i)=\log(n-i+1)$.
Итоговая характеристика:

$$H(i)=\begin{cases} \log(n-n/e+1),&\text{если $0\leqslant i\leqslant n/e$;}\\ \log(n-i+1),&\text{если $n/e<i<i_m$;}\\ 0,&\text{если $i=i_m$.} \end{cases}$$

где $i$ - итерация алгоритма и номер текущего претендента, $i_m$ - оптимальный претендент, на котором следует остановиться (определяется только в процессе выполнения алгоритма, следовательно характеристику $H(i)$ можно построить только на конкретных данных).

-- 15.06.2017, 22:13 --

Каждый алгоритм можно разбить на шаги (итерации). Каждый шаг получает о решении какую-то толику смысловой информации от предыдущего шага. Примечательно, что эту толику информации часто можно измерить достаточно точно, но иногда - только оценить.
Чувствую, что получение характеристики $H(i)$ - это всегда не менее сложная задача, чем та самая рассматриваемая задача, которая решается алгоритмом. Ведь вычисление энтропии сводится к вычислению числа комбинаций. Это как #P-трудные задачи соотносятся с P-трудными задачами.

[mihaild]

Так, я кажется понял, чего вы хотите для случая потоковых алгоритмов (т.е. алгоритмов, читающих вход последовательно и не возвращающихся к предыдущим ячейкам) - у нас есть множество различных вариантов, которые алгоритм может выдать после $i$ шагов (в зависимости от того, какой вход будет дальше), и можно брать его логарифм.

Вы это имели в виду?

Если да, то как определение обобщается на случай, когда данные в общей памяти?

[Mihaylo]

mihaild в сообщении #1225860 писал(а):

Вы это имели в виду?

Ну да, Вы правильно рассуждаете, только энтропию можно вычислить и не только для потоковых алгоритмов. Хотя для потоковых гораздо проще получить результат или хотя бы оценку.
Какой бы простой пример непотокового алгоритма рассмотреть?.. Сортировка слиянием - непотоковый алгоритм?

Сортировка слиянием. По визуализации алгоритма видно, что к данным алгоритм обращается по несколько раз.

Между тем, при первых обращениях происходит частичное упорядочивание, это видно по картинке, а значит интуитивно энтропия уменьшается.
Я учел тот факт, что каждый частично упорядоченный элемент при дальнейшей сортировке слиянием заведомо не сможет занять некоторые положения в сортируемом массиве - эти комбинации отсекались и таким образом энтропия уменьшается. Мне удалось получить точную формулу:
$H(i)=\sum\limits_{k=0}^{\frac{n}{2^i}-1}\log \frac{(n-k\cdot 2^i)!}{(n-(k+1)\cdot 2^i)!(2^i)!}$

Надо, конечно, рассмотреть какой-нибудь еще непотоковый алгоритм. Сортировка может выглядеть неубедительно.

[mihaild]

Просто непонятно - если алгоритм сначала считал все данные, то его текущее состояние уже позволяет однозначно предсказать вывод. Где тут разные варианты?

[Mihaylo]

Да, закономерный вопрос.
Решение следующее: каждая итерация передает некоторые ограниченные данные последующей итерации. Несмотря на то, что алгоритм считывал когда-то те или иные входные данные, он может не передать сведения о них в следующую итерацию, то есть попросту "забыть".
Итеративные алгоритмы передают от итерации к итерации в первую очередь значение текущего шага $i$, часто передаются массивы как, например, сортируемый массив в алгоритмах сортировки. Еще итерации на равных правах имеют доступ к глобальным переменным задачи, например, длина массива $n$ и т.д. Совокупность этих неполных данных и образуют некоторую степень неопределенности на каждой итерации. Тут надо строго определить, что известно на данной итерации, а что нет.

[Mihaylo]

Интересно проанализировать какую-нибудь из задач, решаемых методом динамического программирования. В таких алгоритмах обычно на следующую итерацию передается довольно большой объем информации, то есть такие алгоритмы очень эффективны. Мы это чувствуем субъективно, но по-моему мнению эту информацию еще можно измерить объективно и точно (в битах). Или хотя бы оценить.

Задача - найти наидлиннейшую возрастающую подпоследовательность (LIS). Дан массив $a$ из $n$ чисел. Требуется найти в этой последовательности строго возрастающую подпоследовательность наибольшей длины.

Существует два известных решающих алгоритма со скоростью $O(n^2)$ и $O(n \log n)$.
Первый алгоритм попроще. Он состоит из двух частей. Первая часть алгоритма строит массив $d(i)$ размерности $n$. $d(i)$ - это длина наидлиннейшей возрастающей подпоследовательности, оканчивающейся именно в элементе с индексом $i$. Первая часть - содержательная часть алгоритма. Вторая часть просто помогает быстро находить саму подпоследовательность. Она вычисляет массив индексов $p$ размерности $n$. $p(i)$ - индекс последнего элемента подпоследовательности, при котором получилось значение $d(i)$.

Итак, задача сформулирована, алгоритм описан. Наша задача - найти характеристику $H(i)$. Тут важно от словесной перейти к точной математической формулировке. Если требуется найти наидлиннейшую возрастающую подпоследовательность, то математически это можно понимать по-разному, может даже разгореться спор, что это означает.
Варианты:
1. Найти начало подпоследовательности
2. Найти конец подпоследовательности
3. Найти начало и конец подпоследовательности
4. Найти начало и длину подпоследовательности
5. Найти каждый элемент подпоследовательности
6. И т.д.
Каждый из этих вариантов дает разные варианты характеристик $H(i)$. Именно в связи с этим я подчеркивал, что построение энтропийной характеристики требует правильного и тщательного обращения с формулировками задач.
Из всех возможных вариантов математических формулировок задач следует выбирать те, которые показывают богатство/особенности работы алгоритма, а также те, которые позволяют удобно сравнивать алгоритмы, решающие одну и ту же задачу.
Именно поэтому лучше для рассмотренного алгоритма $O(n^2)$ желательно придерживаться формулировки "найти конец и длину подпоследовательности". Между всеми сформулированными задачами разница очень незначительна (кроме "найти каждый элемент подпоследовательности"), всего в один шаг. Этот шаг - принципиальный вопрос или нет, можно решать по-разному. Если судить строго, то это все-таки разные задачи.