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

.

По определению (8) и (9) существует метка , , такая что

,

(10)

и метка , , такая что

,

(11)

и, конечно же, справедливо неравенство

.

(12)

С учетом супермодулярности функции запишем неравенство (6) в виде

,

подставим вместо слагаемых в правой части этого неравенства правые части неравенств (10), (11), и (12) и таким образом доказываем справедливость неравенства

.

(13)

Справедливой является следующая цепочка:

.

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

4. Перестановочно супермодулярные задачи

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

.

(16)

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

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

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

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

.

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

.

3. Определить разметку так, что

, .

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

.

Учитывая, что все слагаемые в правой части этого неравенства – целые числа, получаем, что найденная разметка оптимальна.

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

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

Для любой весовой функции и любой вершины определим новую весовую функцию так , что

, если , а в противном случае.

(17)

Преобразование весовой функции в функции назовем - исключением дужек.

Алгоритм решения перестановочно супермодулярной задачи с целочисленными весами дужек состоит в следующем.

1. Определить порядок просмотра объектов из так, что , .

2. Определить число .

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

4. Построить - согласованное подмножество множества дужек .

5. Определить наибольшее целое число , не превосходящее число

Комментарий. Число есть качество искомой оптимальной разметки,

.

6. Для выполнить

6.1. Построить множество

.

Комментарий. Значение искомой разметки принадлежит .

6.2. Для каждой метки

6.2.1. Преобразовать весовую функцию в в соответствии с формулой (17), то есть выполнить - исключение дужек.

6.2.2. С помощью диффузии получить функцию , эквивалентную , такую, что .

6.2.3. Если

,

то определить и перейти на 6.3; в противном случае продолжить выполнение цикла 6.2 для очередной еще не рассмотренной метки из множества .

Комментарий. Если исходная функция перестановочно супермодулярна, то условие (18) выполнится по крайней мере для одной метки из .

6.3. ; , .

Если , продолжить цикл 6.

7. Завершить работу алгоритма.

Комментарий. Метки образуют разметку с качеством .

Мы видим, что для реализации указанного алгоритма совсем не обязательно знать ту конкретную нумерацию , , вершин, которая определяет перестановочную супермодулярность решаемой задачи. Тем не менее, если на вход алгоритма подать перестановочно супермодулярную задачу, то алгоритм ее гарантированно решает без знания номеров , , . Более того, алгоритм решает и некоторые задачи, не являющиеся перестановочно супермодулярными. Это те задачи, в которых гарантируется выход из цикла 6.2, то есть выполнение условия (18) по крайней мере для одной метки и для каждого объекта . В силу этого алгоритм можно весьма просто доопределить так, чтобы алгоритм завершил работу, если при обработке очередного объекта условие (18) нарушается для всех меток . Завершение работы по этому условию должно пониматься как отказ от решения задачи. Таким образом, областью определения алгоритма становится множество всех возможных задач, и для каждой задачи, предложенной для решения, алгоритм за конечное время выходит на одно из двух возможных завершений работы. Одно из них понимается как отказ от решения предложенной задачи. При втором завершении результатом работы является разметка, гарантированно являющаяся оптимальной.

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

Заключение

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

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

Неподвижной точкой алгоритма диффузии является согласованная весовая функция. Это не отличает его от многих других известных алгоритмов, от самого раннего [10], до более поздних [2, 7, 13], что определяет общие достоинства и общие недостатки всех этих алгоритмов. Все они выполняют эквивалентное преобразование весовой функции и в конечном итоге находят оценку сверху для качества оптимальной разметки, названной в статье энергией весовой функции. Некоторые задачи преобразуются алгоритмом диффузии так, что их энергия становится сколь-угодно близкой к качеству оптимальной разметки, а иногда и равной этому качеству. Это – общее для всех этих алгоритмов достоинство. Их общий недостаток состоит в том, что эквивалентное преобразование весовой функции в согласованную функцию совсем не гарантирует получение наименьшего значения энергии. Это значит, что существуют такие весовые функции, которые можно эквивалентно преобразовать так, что их энергия становится равной качеству оптимальной разметки, но этот наилучший эквивалент не будет найден алгоритмом диффузии, равно как и другими родственными с ним алгоритмами [2, 7, 10, 13]. Более подробно этот недостаток рассмотрен в работе [5], где предложены пути для его преодоления.

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

Литература

1. М. И. Шлезингер. Синтаксический анализ двумерных зрительных сигналов в условиях помех. Кибернетика, 4:113–130, 1976.

2. V. Kolmogorov. Convergent tree-reweighted message passing for
energy minimization. IEEE Trans. Pattern Analysis and Machine Intelligence. – 2006. – 28. - № 10. - Р.

3. Y. Boykov, O. Veksler, R. Zabih. Fast approximate energy minimization
via graph cuts. IEEE Trans. Pattern Analysis and Machine Intelligence. – 2001.- 23.- № 11. - P.

4. M. I. Schlesinger and B. Flach. Some solvable subclasses of structural recognition problems. Czech Pattern Recognition Workshop. – Praha. – 2000. – P. 55-62.

5. , Гигиняк (max,+)-задач структурного распознавания с помощью их эквивалентных преобразований //. Управляющие системы и машины.- 2007, № 1 , с. 3 ‑ 15.

6. , Гигиняк (max,+)-задач структурного распознавания с помощью их эквивалентных преобразований II //. Управляющие системы и машины.- 2007, № 2 , с. 5 ‑ 17.

7. T. Werner. A Linear Programming Approach to Max-sum Problem: A Review. IEEE Trans. on Pattern Recognition and Machine Intelligence (PAMI) 29(7), July 2007.

8. Dmitrij Schlesinger. Exact Solution of Permuted Submodular MinSum Problems.
A. L.Yuille et al. (Eds.): EMMCVPR 2007, LNCS 4679, pp. 28–38, 2007.

9. Фихтенгольц дифференциального и интегрального исчисления. Москва: ФИЗМАТЛИТ, 2001. т.с.

10. , . Двумерное программирование в задачах анализа изображений. // Автоматика и телемеханика. - М№ 8. - C. 149-168.

11. H. Ishikawa, D. Geiger. Segmentation by grouping junctions. // IEEE p. Vision and Pattern Recogn. – 1998. – P. 125–131.

12. М. Шлезингер, В. Главач. Десять лекций по статистическому и структурному распознаванию. – К.: Наук. думка, 2004. - 545 с.

13. M. Wainwright, T. Jaakkola, and A. Willsky. Exact MAP estimates by (hyper)tree agreement. In S. T. S. Becker and K. Obermayer, editors, Advances in Neural Information Processing Systems 15, pages 809–816. MIT Press, 2003.

Приложение

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

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

.

(1)

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

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

.

Для разметки , такой, что , равенство (1) также выполняется. Действительно, в соответствии с определением - диффузии новые веса дужек вида , , , вычисляются по формуле

,

где

.

Веса всех остальных дужек остаются неизменными. Поэтому для такой разметки справедлива следующая цепочка равенств:

.

Лемма доказана.

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

Лемма 2. Пусть - весовая функция, полученная в результате применения - диффузии к произвольной весовой функции . В таком случае все величины

, ,

равны друг другу.

Лемма 3. Пусть - весовая функция, полученная в результате применения - диффузии к произвольной весовой функции . В таком случае все величины