Как разобрать CFG с произвольным количеством соседей?

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

Я нашел SVM-CFG, который выглядит идеально, проблема в том, что он предназначен для синтаксического анализа строки, где каждый терминал в строке имеет не более двух соседей (слова до и после). В нашей визуальной грамматике каждый сегмент может находиться рядом с произвольным количеством других сегментов.

Каков наилучший способ анализа этих визуальных грамматик? В частности, могу ли я кодировать свои данные для использования SVM-CFG? Или мне придется написать свою собственную библиотеку ядра/парсинга?


machine-learning image-segmentation svm context-free-grammar
person CAnderegg    schedule 06.05.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

SVM-CFG — это конкретная реализация алгоритма оптимизации секущей плоскости, используемого в SVM-struct (описано здесь http://www.cs.cornell.edu/People/tj/publications/tsochantaridis_etal_04a.pdf, раздел 4).

На каждом шаге алгоритм секущей плоскости вызывает функцию для поиска структурированного выходного назначения с наивысшей оценкой (в SVM-CFG это синтаксический анализ с наивысшей оценкой).

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

Вы можете расширить SVM-struct, чтобы возвращать анализ изображения с наивысшей оценкой, но для этого не существует алгоритма с полиномиальным временем!

Вот ссылка на современный метод анализа изображений: http://www.socher.org/uploads/Main/SocherLinNgManning_ICML2011.pdf. Они сталкиваются с той же проблемой для нахождения анализа сегментации изображения с наивысшей оценкой, поэтому они используют жадный алгоритм для нахождения приблизительного решения (см. раздел 4.2). Возможно, вы сможете включить аналогичный жадный алгоритм в структуру SVM.

person user1149913    schedule 24.06.2012