Колмогоровская сложность как мера разнообразия
Содержание
Введенная в статье [1] мера разнообразия сама по себе является объектом тщательного исследования, так как мер, удовлетворящих приведенным свойствам, большое количество, и они по-разному влияют на определение того или иного процесса как достаточно или хорошо параметризованного.
Наша задача -- найти меру или класс мер, которые можно было бы принять в качестве унифицированных для построения как можно более параметризованных или, в предельном случае, хорошо параметризованных, процессов, определяющих алгоритмическое ядро механизмов, применяемых для автоматического генерирования музыкального и графического материала.
В качестве перспективного поля исследования предлагается рассмотреть меры разнообразия, построенные на базе колмогоровской сложности [2, 3].
Дадим определения.
Пусть задан язык (описатель) L(V) над множеством значений величины V = {vi} такой, что:
- высказывание на языке L(V) есть строка t;
- каждая строка состоит из ячеек;
- каждая ячейка состоит из натурального числа ni или значения vi из V.
Множество строк языка L(V) обозначим за T(L) = {ti}.
Сегментом segk(tj) строки tj из T(V) будем называть подстроку из tj, состоящую из подряд идущих ячеек, содержащих только значения vi из V, расположенных после ячейки, содержащей значение ni в позиции строки k.
Описатель L(V) работает следующим образом: для заданного распределения sj(V) существует строка (возможно, не одна) tj из T(L), в которой каждое значение ni в позиции k означает повтор сегмента segk(tj) ni раз.
Итак, мерой разнообразия M распределения si(V) будем называть длину минимальной строки ti языка L(V), описывающей распределение si(V). То есть M(si(V)) равна колмогоровской сложности si(V) в языке L(V).
Наша задача -- найти меру или класс мер, которые можно было бы принять в качестве унифицированных для построения как можно более параметризованных или, в предельном случае, хорошо параметризованных, процессов, определяющих алгоритмическое ядро механизмов, применяемых для автоматического генерирования музыкального и графического материала.
В качестве перспективного поля исследования предлагается рассмотреть меры разнообразия, построенные на базе колмогоровской сложности [2, 3].
Дадим определения.
Пусть задан язык (описатель) L(V) над множеством значений величины V = {vi} такой, что:
- высказывание на языке L(V) есть строка t;
- каждая строка состоит из ячеек;
- каждая ячейка состоит из натурального числа ni или значения vi из V.
Множество строк языка L(V) обозначим за T(L) = {ti}.
Сегментом segk(tj) строки tj из T(V) будем называть подстроку из tj, состоящую из подряд идущих ячеек, содержащих только значения vi из V, расположенных после ячейки, содержащей значение ni в позиции строки k.
Описатель L(V) работает следующим образом: для заданного распределения sj(V) существует строка (возможно, не одна) tj из T(L), в которой каждое значение ni в позиции k означает повтор сегмента segk(tj) ni раз.
Итак, мерой разнообразия M распределения si(V) будем называть длину минимальной строки ti языка L(V), описывающей распределение si(V). То есть M(si(V)) равна колмогоровской сложности si(V) в языке L(V).
Приведем пример.
Пусть задана величина V1 = {a,b,c}. Построим для V некоторое распределение si(V1) = "aaaaaabcbcbcaaabcbacbacbacbac".
Для данного распределения на языке L(V1) возможны, например, следующие строки:
1) ti = "1aaaaaabcbcbcaaabcbacbacbacbac" с единственным сегментом seg0(ti), совпадающим со самим распределением; длина строки ti равна 30;
2) ti = "1aaaaaabcbcbc1aaabcbacbacbacbac" с сегментами seg0(ti) = "aaaaaabcbcbc", seg13(ti) = "aaabcbacbacbacbac"; длина строки ti равна 31;
3) ti = "1aaaaaa3bc3a1bcbacbacbacbac" с сегментами seg0(ti) = "aaaaaa", seg7(ti) = "bc", seg10(ti) = "a", seg12(ti) = "bcbacbacbacbac"; длина строки ti равна 27.
И так далее.
Однако, минимальная строка ti на языке L(V1) для данного распределения выглядит так:
ti = "6a3bc3a1b1c3bac". При этом сегменты строки ti суть: seg0(ti) = "a"; seg2(ti) = "bc"; seg5(ti) = "a"; seg7(ti) = "b"; seg9(ti) = "c"; seg11(ti) = "bac". Мера разнообразия M(si(V1)) равна длине строки ti, то есть 15.
Построим еще одно распределение для V2 = {a,b,c,d} : sj(V2) = "aaaaaaaabbbbbbbccccccddddd". Тогда минимальная строка tj на языке L(V2) для данного распределения выглядит так: tj = "8a7b6c5d". При этом сегменты строки tj суть: seg0(tj) = "a"; seg2(tj) = "b"; seg4(tj) = "c"; seg6(tj) = "d". Мера разнообразия M(sj(V2)), соответственно, равна 8.
Приведенные примеры показывают, в принципе, согласованность меры на базе колмогоровской сложности с интуитивными представлениями о разнообразии.
Обращаем внимание на следующий факт. Так как распределение не может быть пустой строкой, то есть в ней всегда присутствует хотя бы одно значение, то в случае, если S(V) содержит все распределения V, имеем Mmin(S(V)) = 2.
Пусть задана величина V1 = {a,b,c}. Построим для V некоторое распределение si(V1) = "aaaaaabcbcbcaaabcbacbacbacbac".
Для данного распределения на языке L(V1) возможны, например, следующие строки:
1) ti = "1aaaaaabcbcbcaaabcbacbacbacbac" с единственным сегментом seg0(ti), совпадающим со самим распределением; длина строки ti равна 30;
2) ti = "1aaaaaabcbcbc1aaabcbacbacbacbac" с сегментами seg0(ti) = "aaaaaabcbcbc", seg13(ti) = "aaabcbacbacbacbac"; длина строки ti равна 31;
3) ti = "1aaaaaa3bc3a1bcbacbacbacbac" с сегментами seg0(ti) = "aaaaaa", seg7(ti) = "bc", seg10(ti) = "a", seg12(ti) = "bcbacbacbacbac"; длина строки ti равна 27.
И так далее.
Однако, минимальная строка ti на языке L(V1) для данного распределения выглядит так:
ti = "6a3bc3a1b1c3bac". При этом сегменты строки ti суть: seg0(ti) = "a"; seg2(ti) = "bc"; seg5(ti) = "a"; seg7(ti) = "b"; seg9(ti) = "c"; seg11(ti) = "bac". Мера разнообразия M(si(V1)) равна длине строки ti, то есть 15.
Построим еще одно распределение для V2 = {a,b,c,d} : sj(V2) = "aaaaaaaabbbbbbbccccccddddd". Тогда минимальная строка tj на языке L(V2) для данного распределения выглядит так: tj = "8a7b6c5d". При этом сегменты строки tj суть: seg0(tj) = "a"; seg2(tj) = "b"; seg4(tj) = "c"; seg6(tj) = "d". Мера разнообразия M(sj(V2)), соответственно, равна 8.
Приведенные примеры показывают, в принципе, согласованность меры на базе колмогоровской сложности с интуитивными представлениями о разнообразии.
Обращаем внимание на следующий факт. Так как распределение не может быть пустой строкой, то есть в ней всегда присутствует хотя бы одно значение, то в случае, если S(V) содержит все распределения V, имеем Mmin(S(V)) = 2.
Данная мера интересна тем, что позволяет сравнивать распределения разных величин V1 и V2, независимо от их природы. Множества их значений |V1| и |V2| могут быть как конечными, так и бесконечными, как счетными, так и несчетными. Множества распределений этих величин S(V1) и S(V2) могут быть как полными, то есть содержать все возможные значения, так и заданными явно, то есть ограниченными. Во всех этих случаях мера разнообразия на базе колмогоровской сложности применима.
Следует отметить, что язык L(V) является простейшим и не единственным из простейших, подходящим для определения меры разнообразия через колмогоровскую сложность. Он обладает определенными недостатками, например, сложность распределения "abcdeabcd" будет максимальной среди распределений аналогичной длины, несмотря на явно повторяющийся сегмент "abcd". Однако, таким или схожим недостатком обладают все меры разнообразия ввиду интуитивности и неопределенности самого понятия "разнообразие".
Обратим внимание на то, как влияет выбор языка L на значение меры и, как следствие, на определение процесса P как достаточно или недостаточно параметризованного.
Например, если L -- язык программирования, а V -- множество конфигураций клеточного автомата P(R, X) для разных правил R и начальных конфигураций X, то очевидно, что любая конфигурация клеточного автомата может быть описана одной и той же минимальной программой на языке L, разница будет лишь в параметрах и начальном состоянии, что не влияет на длину программы. И, таким образом, мера разнообразия для всех конфигураций клеточного автомата будет одинаковой (так как у них одна и та же колмогоровская сложность для выбранного языка L) и, следовательно, клеточный автомат не является достаточно параметризованным процессом: имея одну и ту же меру для всех параметров, строка распределения меры U(P) будет описана строкой минимально возможной длины, Mmin (U(P)).
Если же принять за L описатель строк, приведенный выше, или аналогичный, получаем достаточное разнообразие распределения значений меры для распределения конфигураций клеточного автомата. Достаточно сказать, что конфигурация клеточного автомата может иметь одинаковые значения всех клеток, что соответствует минимальной мере, а также прочие конфигурации, мера которых строго больше минимальной. Согласно определению, разные значения мер для разных параметров процесса являются признаком достаточно параметризованного процесса. Установив этот факт, можно сравнивать клеточные автоматы с разными правилами перехода (то есть рассматривать каждое правило перехода для данного клеточного автомата как отдельный процесс Pi = P(Ri, X)) на предмет, какой из них является более параметризованным.
Следует отметить, что язык L(V) является простейшим и не единственным из простейших, подходящим для определения меры разнообразия через колмогоровскую сложность. Он обладает определенными недостатками, например, сложность распределения "abcdeabcd" будет максимальной среди распределений аналогичной длины, несмотря на явно повторяющийся сегмент "abcd". Однако, таким или схожим недостатком обладают все меры разнообразия ввиду интуитивности и неопределенности самого понятия "разнообразие".
Обратим внимание на то, как влияет выбор языка L на значение меры и, как следствие, на определение процесса P как достаточно или недостаточно параметризованного.
Например, если L -- язык программирования, а V -- множество конфигураций клеточного автомата P(R, X) для разных правил R и начальных конфигураций X, то очевидно, что любая конфигурация клеточного автомата может быть описана одной и той же минимальной программой на языке L, разница будет лишь в параметрах и начальном состоянии, что не влияет на длину программы. И, таким образом, мера разнообразия для всех конфигураций клеточного автомата будет одинаковой (так как у них одна и та же колмогоровская сложность для выбранного языка L) и, следовательно, клеточный автомат не является достаточно параметризованным процессом: имея одну и ту же меру для всех параметров, строка распределения меры U(P) будет описана строкой минимально возможной длины, Mmin (U(P)).
Если же принять за L описатель строк, приведенный выше, или аналогичный, получаем достаточное разнообразие распределения значений меры для распределения конфигураций клеточного автомата. Достаточно сказать, что конфигурация клеточного автомата может иметь одинаковые значения всех клеток, что соответствует минимальной мере, а также прочие конфигурации, мера которых строго больше минимальной. Согласно определению, разные значения мер для разных параметров процесса являются признаком достаточно параметризованного процесса. Установив этот факт, можно сравнивать клеточные автоматы с разными правилами перехода (то есть рассматривать каждое правило перехода для данного клеточного автомата как отдельный процесс Pi = P(Ri, X)) на предмет, какой из них является более параметризованным.
Автор: Грудина Илья Алексеевич
Опубликовано: 28.01.2023
Опубликовано: 28.01.2023
Ссылки
1) Грудина И.А., "Мера разнообразия. Достаточно и хорошо параметризованный процесс" , 2023
2) Колмогоров А. Н., "Три подхода к определению понятия "количество информации", Пробл. передачи информ., 1:1 (1965), 3–11
3) Верещагин Н. К., Успенский В.А., Шень А. , "Колмогоровская сложность и алгоритмическая случайность" - М.: МЦНМО, 2013
2) Колмогоров А. Н., "Три подхода к определению понятия "количество информации", Пробл. передачи информ., 1:1 (1965), 3–11
3) Верещагин Н. К., Успенский В.А., Шень А. , "Колмогоровская сложность и алгоритмическая случайность" - М.: МЦНМО, 2013