Применение нечетких теоретико-графовых моделей в задачах моделирования и поиска песенных мотивов

Размещено на http://www.allbest.ru/

Применение нечетких теоретико-графовых моделей в задачах моделирования и поиска песенных мотивов

Н.Д. Москин

Петрозаводский государственный университет,

Петрозаводск

В статье рассматриваются нечеткие теоретико-графовые модели семантической структуры песенных мотивов Заонежья XIX - начала XX вв. На их основе строится процедура поиска схожих мотивов, которая была реализована в информационной системе «Фольклор».

фольклорный мотив песенный семантический

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

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

1. Теоретико-графовые модели фольклорных мотивов и задача поиска

Рассмотрим применение теоретико-графовых моделей в задаче поиска мотивов на примере коллекции бесёдных песен Заонежья XIX - начала XX века [Калашникова, 1999].

Бесёдными назывались песни, исполнявшиеся в закрытом помещении - избе - во время заонежских молодежных вечеринок в осенне-зимний период. Предположим, перед исследователем стоит задача обнаружить мотив песни «Затопила млада печь» [Студитский, 1841] в других текстах коллекции (возможно в скрытой форме):

На матушке на Неве

Гуси, лебеди сидели,

Гуси, лебеди сидели,

Серы утки налетели,

Серы утки налетели,

Свежу воду помутили.

Самый простой способ - это поиск по ключевым словам: гуси, лебеди, Нева, серы утки, вода. Однако это решение будет недостаточным по следующим причинам. Во-первых, автор, исполняя произведение, мог заменить существительные, прилагательные и глаголы синонимами или близкими по звучанию словами. Во-вторых, наличие в тексте ключевых слов еще не говорит об их семантической связности, тем более о наличие схожего мотива. Например, объекты «девушка» или «парень» встречаются почти во всех текстах, образуя совершенно разные сюжеты.

Другое решение основано на использовании графов. Как показано в [Москин, 2006], содержательную основу мотива можно представить в виде помеченного мультиграфа, в узлах которого находятся основные персонажи текста, животные, постройки, предметы обихода, явления природы и т. д. Между объектами устанавливаются связи двух типов: локальные и глобальные, соответствующие синтагматическим и парадигматическим отношениям в тексте (например, для данного фрагмента текста искомый граф изображен на рис. 1).

Рис. 1. Граф мотива песни

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

2. Моделирование семантической структуры песенных мотивов при помощи нечетких графов

Введение нечетких объектов и отношений обусловлено следующими причинами:

Задача построения графа мотива является достаточно сложной, требующей привлечения знаний эксперта-фольклориста. В настоящее время ввод и редактирование текстов, а также их теоретико-графовых моделей производится с помощью автоматизированной пошаговой процедуры, которая реализована в информационной системе «Фольклор» [Москин, 2006]. В некоторых случаях у разных экспертов могут возникнуть противоположные мнения относительно того, существует ли определенная связь в графе, к какой группе принадлежит объект, каким образом определить границы фольклорного мотива. Эту важную информацию можно отразить в графе, используя нечеткие объекты и отношения, определив значения функции принадлежности в зависимости от квалификации экспертов.

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

В некоторых случаях это можно сделать автоматически (очевидно, что объекты «девушка» или «парень» принадлежат группе «люди»), а в некоторых случаях требуются дополнительные знания эксперта (объект «коса» можно отнести как к группе «части человеческого тела», так и к группам «разные предметы» или «географические объекты»).

Фольклорный текст очень вариативен, т. е. один и тот же сюжет может быть записан в разных местах разными собирателями. Ниже представлен мотив бесёдной песни «Все мужовья до жон добры», записанной Ф. Студитским в 1841 году [Студитский, 1841]:

Все мужовья до жон добры,

Покупили жонам тафты;

Ещё мой муж не доброй до меня,

Он купил, мутил,

Коровушку купил,

Жены лишнюю работу снарядил.

Рис. 2. Граф мотива песни «Все мужовья до жон добры»

Похожий мотив встречается в записи В. Д. Дашкова, однако имеет другую структуру [Дашков, 1842]:

Все мужья до жен добры,

Накупили женам тафты;

Мой муж не ласков до меня,

Не купил мне шелкова платка.

Он коровку купил,

Мне заботу снарядил.

Как видно на рис. 2 и 3, во втором графе добавилась новая вершина «шелков платок» и соответствующая связь «не купил». Кроме того, отличаются группы объектов «забота» и «работа».

Рис. 3. Граф мотива песни «Все мужья до жен добры»

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

, ,

где - значение функции принадлежности для вершины.

Зададим нечеткое множество ребер

,

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

3. Алгоритм поиска мотивов на основе нечетких теоретико-графовых моделей

Для построения процедуры поиска песенных мотивов модифицируем классический алгоритм Ульмана поиска изоморфизма подграфу [Ullmann, 1976]. Пусть задан нечеткий граф вида с нечетким множеством вершин , носителем которого является четкое множество , и нечетким множеством ребер . Функции и определяют группы объектов и связей соответственно. Данный граф можно представить с помощью двух матриц смежности:

1. , где и для .

2. , где и для .

Рассмотрим матрицу перестановок , для которой выполняются следующие условия:

1. для ;

2. для ;

3. для .

Тогда матрицы и , которые получаются по формулам

и ,

где - транспонированная матрица , также являются матрицами смежности для графа . При этом если , то -я вершина в и становится -й вершиной в и соответственно.

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

.

где и - матрицы смежности графов и размерности и соответственно, где , и . Описание рекурсивной процедуры Backtrack, которая последовательно определяет строка за строкой матрицу перестановок , приводится в [Москин, 2009b].

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

,

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

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

,

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

,

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

4. Реализация процедуры поиска песенных мотивов в информационной системе «Фольклор»

Для организации поиска песенных мотивов на основе теоретико-графовых моделей была реализована соответствующая процедура в информационной системе «Фольклор», разработанной в среде визуального программирования Delphi 7.0 [Москин, 2006]. В настоящее время система содержит 562 текста из четырех фольклорных коллекций, одной из которых является корпус бесёдных песен Заонежья XIX - начала XX века, состоящий из 118 текстов. Искомый мотив можно задать двумя способами: либо пользователь самостоятельно определяет объекты и связи, либо выделяет в тексте границы мотива и программа автоматически строит граф (рис. 4).

Для хранения и последующего редактирования теоретико-графовых моделей песенных мотивов, а также результатов поиска используется язык TextGML, основанный на XML [Москин, 2009b]. Ниже приводится пример разметки мотива, который был рассмотрен во втором параграфе:

<graph id="g1" name="мотив 1-1" directed="true">

Все <node id="n1" type="H" fuzzy="1">мужовья</node> до

<node id="n2" type="H" fuzzy="1">жон</node> добры,

Покупили <node id="n2" type="H" fuzzy="1">жонам</node>

<node id="n3" type="CL" fuzzy="1">тафты</node>;

Ещё мой <node id="n4" type="H" fuzzy="1">муж</node> не доброй до

<node id="n5" type="H" fuzzy="1">меня</node>,

<node id="n4" type="H" fuzzy="1">Он</node> купил, мутил,

<node id="n6" type="A" fuzzy="1">Коровушку</node> купил,

<node id="n5" type="H" fuzzy="1">Жены</node> лишнюю

<node id="n7" type="TR" fuzzy="1">работу</node> снарядил;

<link id="l1" source="n1" target="n2" type="local" fuzzy="1" order="1"/>

<link id="l2" source="n1" target="n3" type="local" fuzzy="1" order="2"/>

<link id="l3" source="n4" target="n5" type="local" fuzzy="1" order="3"/>

<link id="l4" source="n4" target="n6" type="local" fuzzy="1" order="4"/>

<link id="l5" source="n4" target="n7" type="local" fuzzy="1" order="5"/>

<link id="l6" source="n1" target="n4" fuzzy="1" type="global"/>

<link id="l7" source="n2" target="n5" fuzzy="1" type="global"/>

<link id="l8" source="n6" target="n7" fuzzy="1" type="global"/>

</graph>

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

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

Рис. 4. Процедура поиска мотивов

Важным достоинством программы является то, что она способна обнаружить «скрытые» мотивы (например, если составляющие мотивы находятся в нескольких частях текста), которые сложно определить традиционными методами.

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

В данном исследовании при построении теоретико-графовых моделей и интерпретации результатов принимали участие фольклористы Института языка, литературы и истории Карельского научного Центра Российской Академии Наук и сотрудники отдела фольклора музея-заповедника «Кижи».

Список литературы

1. [Берштейн, 2005] Берштейн Л. С., Боженюк А. В. Нечеткие графы и гиперграфы. - М.: Научный мир, 2005.

2. [Варфоломеев и др., 2008] Варфоломеев А. Г., Каргинова Н. В., Кравцов И. В., Москин Н. Д. Применение RuleML для представления и вывода знаний о семантической структуре фольклорных текстов, полученных на основе их теоретико-графовых моделей // Труды XI национальной конференции по искусственному интеллекту с международным участием КИИ-2008. Т. 2. - М.: ЛЕНАНД, 2008.

3. [Дашков, 1842] Описание Олонецкой губернии в историческом, статистическом и этнографическом отношениях. Сост. В. Дашков. - Санкт-Петербург: тип. мин-ва внутренних дел, 1842.

4. [Калашникова, 1999] Калашникова Р. Б. Бесёды и бесёдные песни Заонежья второй половины XIX века. - Петрозаводск: Изд-во ПетрГУ, 1999.

5. [Москин, 2006] Москин Н. Д. Теоретико-графовые модели структуры фольклорных текстов, алгоритмы поиска закономерностей и их программная реализация. Автореф. дисс. на соиск. уч. степени к.т.н. - Петрозаводск, 2006.

6. [Москин, 2009a] Москин Н. Д. Математические модели и алгоритмы в задачах атрибуции фольклорных текстов // Сборник докладов 14-ой Всероссийской конференции «Математические методы распознавания образов». - Суздаль, 2009.

7. [Москин, 2009b] Москин Н. Д. Решение задач визуализации и поиска мотивов в электронной библиотеке фольклорных текстов // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды ХI Всероссийской конференции RCDL'2009. - Петрозаводск: КарНЦ РАН, 2009.

8. [Студитский, 1841] Народные песни Вологодской и Олонецкой губерний, собранные Ф. Студитским. - Санкт-Петербург, 1841.

9. [Ullmann, 1976] Ullmann J. R. An algorithm for subgraph isomorphism // Journal of the Association for Computing Machinery. - 1976. - Vol. 23, № 1.

Размещено на Allbest.ru