6. О выборе потенциальной функции в пространстве вершин m-мерного куба.

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

Нам будет удобно считать, что координаты вершин куба принимают значение ±1, т. е. что центр куба расположен в начале координат, а ребро

имеет евклидову длину 2. В качестве расстояния между двумя вершинами куба примем обычное расстояние по Хэммингу

равное числу несовпадающих разрядов в кодах рассматриваемых вершин. Пространство вершин -мерного куба с метрикой (96) далее называется пространством Хэмминга. Это пространство содержит точек. Пространство Хэмминга есть симметрическое пространство. Чтобы показать это, рассмотрим два вида «элементарных» точечных преобразований этого пространства в себя — отражение (замена на и перенумерация координат. Эти элементарные преобразования являются изометрическими, что сразу следует из определения расстояния по формуле (96), так как при замене на на и при перемене мест расстояние не изменяется. Требуемое определением симметрического пространства изометрическое преобразование совмещающее две пары вершин , находящихся на одинаковом расстоянии, в случае пространства Хэмминга может быть получено последовательным применением конечного числа элементарных преобразований указанных двух типов. Вместе с тем

можно показать, что и любое изометрическое преобразование может быть получено таким же образом.

Выясним теперь, каким образом линейное пространство функций, заданных на пространстве Хэмминга, расслаивается на подпространства Рассмотрим нормированную систему функций (14) (см. § 1), состоящую из функции-константы и функций:

так что функции, выписанные в строке, имеют вид (см. § 1)

причем индексы принимают все возможные значения от 1 до удовлетворяющие условию Поэтому в строке содержится ровно функций, а общее их число (включая функцию-константу) равно т. е. равно числу точек пространства Хэмминга. Принимая во внимание, что рассмотренная система функций ортонормирована, заключаем, что она составляет ортонормированный базис в линейном пространстве функций, заданных на пространстве Хэмминга.

Покажем, что функции, выписанные в строке (97), принадлежат одному слою и составляют в нем базис. Действительно, функции из любой строки в (97) переходят друг в друга с точностью до знака при элементарных изометрических преобразованиях (перенумерациях и отражениях), а выше указывалось, что любое

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

Из сказанного выше следует, что общее количество слоев с учетом нулевого слоя равно т. е., в соответствии с общей теорией, — числу различных расстояний в рассматриваемом симметрическом пространстве, а размерность слоя равна

Подсчитаем значения для пространства Хэмминга.

Для слоя имеем

где суммирование проводится по всем наборам индексов упорядоченным в соответствии с неравенствами причем каждый из индексов пробегает значения от 1 до

Обозначим тогда

Рассмотрим совокупность всех Если расстояние между точками х и у равно то в соответствии с (96) среди будет отрицательных положительных значений. Все слагаемые можно разбить на группы, содержащие по отрицательных сомножителей Если то если же то т. е. всегда Каждое такое слагаемое равно Их число равно Теперь, суммируя по получим

По этой формуле можно подсчитать, в частности,

и т. д. Подсчитаем значения

Поэтому

и, следовательно, в соответствии с формулой (83) значение функционала качества (40) с ядром (81) на функциях из слоя равно

Формула (99) показывает, что значения функционала увеличиваются с ростом номера слоя Это находится в полном соответствии с интуитивными представлениями

об усложнении функций (97) при переходе в (97) от верхних строчек к нижним. Действительно, можно показать, что каждая из функций, записанная в строке, обладает следующим свойством: среди вершин куба, находящихся на минимальном расстоянии от любой заданной вершины х, имеется в точности вершин, в которых значения функции отличаются знаком от ее значения в в остальных соседних вершинах значения функции совпадают со значением в х. Модули же значений всех функций (97) одинаковы во всех вершинах и равны На рис. 10 показаны примеры функций из 1, 2 и 3-го слоев трехмерного куба

Рис. 10.

На рисунке означают знаки функций в соответствующих вершинах.

В соответствии с замечанием в конце пункта 4, значения (99) функционала характеризуют сложность функций С ростом номера функция усложняется. В данном случае функция является полиномом порядка по и, соответственно, с ростом

растет число ее перемен знака, экстремумов и других интуитивных показателей сложности.

Перейдем теперь к вопросу о разложении в ряд функции расстояния (в частности, потенциальной функции), заданной в пространстве Хэмминга, по системе (98) функций При этом, разумеется, можно воспользоваться формулой (76), где функция (число точек на сфере радиуса в данном случае, как легко показать, имеет вид

Однако практическое использование формулы (76) приводит к сложным вычислениям, связанным с суммированием рядов. В ряде случаев оказывается возможным вычислять (точно или приближенно) коэффициенты разложения не прибегая к прямому вычислению по формуле (76), а используя следующее тождество:

Для доказательства формулы (100) рассмотрим следующее выражение:

Раскрывая в этом выражении скобки и располагая члены по степеням и, убеждаемся, что множители при совпадают с т. е.

С другой стороны, замечаем, что число пар при которых произведения в точности равно соответственно, число пар для которых равно Поэтому

Из сравнения (102) и (103) следует формула (100).

В качестве примера точного вычисления коэффициентов используем это тождество для разложения

в ряд функции (где а — некоторая константа). С этой целью положим в формуле (100) величину параметра и такой, что

При этом из (100) следует тождество:

или (после замены параметра и его значением, выраженным через а) тождество

Таким образом, для функции коэффициенты разложения равны

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

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

где произвольная достаточно гладкая функция, заданная на отрезке Функция от не зависит, а функция разумеется, явно зависит от Для вычисления коэффициентов разложения функции умножим обе части формулы (100) на

Суммируя затем по в пределах от 0 до от, вспоминая (76) и полагая получим:

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

причем погрешность убывает с ростом от равномерно по например, как если потребовать лишь непрерывность и как если дважды дифференцируема.

Допустим теперь, что разлагается в ряд Тэйлора в окрестности точки Тогда, приравнивая коэффициенты этого ряда соответствующим коэффициентам ряда в правой части (106), получим выражение для подсчета коэффициентов

являющееся асимптотически точным при Однако при конечном от формулой (107) имеет смысл пользоваться лишь для относительно небольших значений так как при возрастании правая часть (107) оказывается сравнимой с ошибкой этой формулы. Оценки погрешности при использовании формулы (107) легко могут быть проведены, если использовать известные результаты об оценке точности аппроксимации полиномами С. Н. Бернштейна.

Формула (107) позволяет проверить, может ли служить функция потенциальной функцией в пространстве Хэмминга.