Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания (стр. 1 )

Кибернетика. Проблемы искусственного интеллекта

УДК 004.93’1: 519.157

АНАЛИЗ АЛГОРИТМОВ ДИФФУЗИИ ДЛЯ РЕШЕНИЯ
ОПТИМИЗАЦИОННЫХ ЗАДАЧ СТРУКТУРНОГО

РАСПОЗНАВАНИЯ

,

(Киев)

Ключевые слова: структурное распознавание, разметки, дискретная оптимизация, перестановочная супермодулярность.

Введение

Ряд прикладных задач распознавания изображений сводится к дискретной оптимизации особого вида [1], [2], [3], [4], [5], [6] известной как задача разметки. Множество всех возможных задач этого вида образует NP-полный класс и поэтому здесь не известен общий алгоритм их решения. Известные алгоритмы, достаточно полно описанные в обзоре [7], решают тот или иной подкласс этих задач или решают задачи приближенно.

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

По своему характеру алгоритмы диффузии близки к эвристическим алгоритмам, известными в англоязычной терминологии как belief propagation, message passing и под другими выразительными названиями. Подобно этим алгоритмам, алгоритм диффузии привлекателен своей простой и наглядной формулировкой и возможностью его распараллеливания при реализации. Однако эти достоинства отходят на задний план, пока не установлена прямая связь этого алгоритма с задачами разметки. Цель данной работы состоит в том, чтобы, по крайней мере частично, восполнить указанный пробел.

1. Определение основных понятий и формулировка результата

Пусть и - два конечных множества, элементы которых называются соответственно объектами и метками, - функция, называемая разметкой, , - метка объекта , - множество всех возможных разметок.

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

Упорядоченную пару , , , назовем вершиной, а неупорядоченную пару вершин, такую, что , назовем дужкой. Будем говорить, что вершина входит в разметку , если . Будем говорить, что дужка входит в разметку , если в эту разметку входит и вершина, и вершина .

Обозначим множество всех возможных дужек,

,

и введем в рассмотрение функцию

,

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

.

Определим качество разметки как сумму весов входящих в неё дужек,

.

Задача разметки состоит в отыскании разметки с максимальным качеством,

.

(1)

Пусть некоторое непустое подмножество дужек. Назовем его согласованным, если для любой тройки , , объектов, таких, что

, ,

и любой пары меток , таких, что

,

(2)

существует метка , такая, что

.

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

.

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

Величину будем называть несогласованностью весовой функции , и если , то функцию назовем согласованной. Несогласованность является конструктивно вычисляемой характеристикой функции .

Пусть - весовая функция, а - некоторая вершина. Определим преобразование функции в функцию, которое назовем - диффузией.

1. Вес дужек , не содержащих вершину , не меняется,

.

2. Для каждого объекта вычисляется вес максимальной дужки, содержащей вершину ,

.

3. Вес каждой дужки, содержащей вершину , вычисляется по формуле

, , .

Для объекта определим операцию - диффузии как выполнение - диффузии для всех .

Определим, наконец, операцию диффузии, как преобразования весовой функции в весовую функцию . Эта операция состоит в следующем.

1. Выбрать произвольный порядок , , , просмотра объектов из .

2. Для выполнить - диффузию.

Преобразование весовой функции в функцию с помощью диффузии является эквивалентным преобразованием в том смысле, что равенство

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

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

(3)

для любой исходной функции . Предположение, что некоторый элемент этой последовательности окажется неподвижной точкой, скорее всего, неверно. Более того, насколько известно, в настоящее время не доказано и не опровергнуто даже более слабое утверждение, сформулированное в обзоре [7 ].

Гипотеза. Для любой весовой функции последовательность

имеет предел , такой что .

Справедливость этой гипотезы позволила бы рассматривать диффузию, как инструмент для отыскания “приблизительно” неподвижной точки. При этом возникли бы новые вопросы, требующие ответа. А именно, каким должно быть условие останова, которое позволило бы утверждать, что функция , полученная на некоторой -ой итерации, уже “приблизительно” неподвижна; каким образом из получения “приблизительно” неподвижной весовой функции следует возможность “приблизительного” решения задачи; и, наконец, как следует конкретизировать само понятие “приблизительно”. Отсутствие ответов на эти вопросы, равно как и недоказанность самой гипотезы, из которой эти вопросы следуют – все это свидетельствует о недостаточной теоретической исследованности алгоритмов диффузии, о чем кратко упоминалось во введении.

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

Теорема. Пусть для исходной весовой функции построена последовательность , такая что , . В таком случае

.

Доказательство теоремы приводится в приложении.

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

2. Ациклические задачи

Пусть - множество пар соседних объектов, не образующее циклов.

Пусть - весовая функция, - найденная с помощью алгоритма диффузии весовая функция, эквивалентная и такая, что . Это значит, что для любой разметки выполняется равенство

.

Из того факта, что , следует существование согласованного подмножества дужек , для которых справедливо неравенство

.

Покажем, что существует разметка , составленная из дужек, входящих в . Эта разметка находится следующим образом.

1. Представим объекты из множества в виде последовательности

так, что каждое из подмножеств , , оказывается связным.

2. Выберем метки и так, что

.

(4)

В силу согласованности множества условие (4) выполнимо.

3. Для найти объект , такой, что и выбрать метку так, что

.

(5)

В силу согласованности условие (5) выполнимо. Для построенной разметки выполняются условия

, ,

а следовательно, и неравенства

, .

Для этой же разметки справедлива цепочка

.
.
.

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

3. Супермодулярные задачи

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

.

(6)

Пусть , , , , - любые числа, с помощью которых функция преобразуется в функцию со значениями

.

(7)

Нетрудно убедиться, что если неравенство (6) выполняется для весовой функции , то оно выполняется и для весовой функции , значения которой определяются выражением (7). Следовательно, неравенство (6) не нарушается в процессе диффузии, так как преобразования весов дужек при диффузии имеет именно вид (7).

Пусть - супермодулярная весовая функция, а - эквивалентная ей функция, полученная в процессе диффузии и такая, что . Построим разметку по следующим правилам.

1. Построим согласованное множество дужек таких, что

.

Такое непустое множество существует, так как .

2. Для каждого объекта определим множество меток

.

(8)

В силу согласованности множества множество непустое для каждого объекта .

3. Определим разметку со значениями

.

(9)

Введем обозначение

,

и докажем, что для любой пары и соседних объектов для найденной разметки выполняется неравенство