В описании может быть указание на категорию, например, «Процессор Intel "Core 2 Duo E4300" (1.80ГГц, 2МБ, 800МГц, EM64T) Socket775». Поэтому дополнительно вводится понятие необязательного атрибута принадлежности категории, состоящего из единственного синсета (т.к. категория зафиксирована).

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

Краткую текстовую спецификацию (частично структурированное описание объекта), являющуюся последовательностью символов - строкой текста, после прохождения лексического анализа можно рассматривать как последовательность слов . Например, принимая пробелы и запятые за разделители, спецификацию “CPU Intel Core 2 Duo E4300, 1,8GHz, 2Mb, 800MHz Socket-775 OEM” можно рассматривать как последовательность слов (“CPU”, “Intel”, “Core”, “2”, “Duo”, “ E4300”, “1”, “8GHz”, “2Mb”, “800MHz”, “Socket-775”, “OEM”). Слово представляет собой некоторую подстроку спецификации , где - начальный символ слова , а - конечный. Фраза определяется как результат конкатенация (с сохранением промежуточных разделительных символов исходной строки) одного или нескольких подряд идущих слов . Т.е. имеет место равенство , где обозначает конкатенацию с сохранением разделительных символов из . Например, конкатенация слов “1” и “8GHz” из приведённого выше примера представляет собой фразу “1,8GHZ”. Под сегментацией спецификации будем понимать разбиение на фразы: .

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

Далее в работе показывается возможность построения функции релевантности фразы атрибуту . Большее значение функции релевантности означает большую степень достоверности того, что фраза принадлежит одному из синсетов атрибута. Например, можно утверждать, что для атрибута «Тактовая частота» центральных процессоров для персональных компьютеров справедливо < < (тактовая частота современных процессоров превышает 1 ГГц).

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

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

На первом этапе максимизируется функция совокупной релевантности по всем возможным разбиениям на последовательность фраз и по всем возможным сопоставлениям фраз атрибутам. Аргумент максимизации, представляющий оптимальное разбиение на фразы с соответствующими атрибутами, передаётся на второй этап. Описанию алгоритма максимизации посвящена вторая глава. Сказанное можно записать в виде формулы:

,

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

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

Найденное соответствие фраз синсетам предъявляется эксперту для верификации. Человек проверяет предложенное соответствие и задаёт правильные сочетания фраза - синсет. Заданное человеком соответствие фраз синсетам сравнивается с предложенным системой; на основании сравнения определяется число ошибок. Возможные ошибки описаны в четвёртой главе. По заданному экспертом соответствию новые фразы (и синсеты) заносятся в базу знаний.

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

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

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

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

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

Рекурсивная функция Lookup_Known_Phrases принимает на вход ассоциативный массив (map) KB, ключами которого являются фразы из известных синсетов, а значениями - множество синсетов, в которые фраза входит; последовательность (массив) ещё не распознанных слов W спецификации x; множество атрибутов, которым ещё не найдено соответствие. Возвращает функция ассоциативный массив , ключами которого являются фразы спецификации x, а значениями - сопоставленные фразам синсеты. Внутренняя переменная описывает промежуточный результат и является ассоциативным массивом, ключами которого являются фразы спецификации, а значениями - множества синсетов - кандидатов на соответствие. Вспомогательная переменная представляет множество атрибутов, которым на данной итерации возможно сопоставить фразы. Переменная w представляет собой матрицу весов, индексами которой являются фразы и атрибуты. Переменная PA является ассоциативным массивом, соответствующим (частичной) биекции фраз на атрибуты, максимизирующей длину распознанных фраз.

Схема работы алгоритма на псевдокоде выглядит так:

Lookup_Known_Phrases(KB, W, FA)

1 OP <

2 for i < 1 to length[W]

3 do for j < i to length[W]

4 do if слова W[i],…,W[j] идут подряд в x

5 then Insert_Sorted(OP, W[i]…W[j])

6 <

7 while OP ?

8 do p < Dequeu(OP)

9 if Contains(KB, p) and Filter_By_Attributes(KB[p], FA) ?

10 then IR[p] < Filter_By_Attributes(KB[p], FA)

11 Remove_Overlaps(OP, p)

12 AL <

13 for (для) всех значений v ассоц. массива IR

14 do Insert_All(AL, Extract_Attributes(v))

15 w < 0

16 for (для) всех ключей p ассоц. массива IR

17 do for (для) всех s из IR[p]

18 do w[p][attribute[s]] < length[p]

19 PA < Hungarian_Algorithm(keys[IR], AL, w)

20 R <

21 for (для) всех ключей p ассоц. массива PA

22 do for (для) всех s из IR[p]

23 do if attribute[s] = PA[p]

24 then R[p] < s

25 Remove(FA, attribute[s])

26 Remove_Overlaps(W, p)

27 if R =

28 then return

29 Put_All(R, Lookup_Known_Phrases(KB, W, FA))

30 return R

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

Будем говорить, что последовательность получена расщеплением элемента последовательности , если длина последовательности ровно на единицу больше длины последовательности и . Обратное отношение будем называть слиянием двух соседних элементов.

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

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

Рис. 1. Найденное соответствие фраз спецификации атрибутам (белый фон). Участки без соответствия и свободные атрибуты (чёрный фон).

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

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

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

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

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

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

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

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

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

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

Построим следующий взвешенный граф. Множеством его вершин будут фразы и атрибуты. Любая пара фраза-атрибут соединена ребром, имеющим вес равный значению функции релевантности. Фразы, пересекающиеся в исходной спецификации, соединены рёбрами с нулевым весом. Рёбер, соединяющих два атрибута, нет. Также нет рёбер, соединяющих две непересекающиеся фразы. Пример такого графа приведён на рис. 2.

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

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

Рис. 2. Пример графа соответствия фраз атрибутам для двух атрибутов и трёх слов.

В главе 3 вводятся общие понятия о строковых метриках, упоминаются расстояние Левенштейна и метрика Нидельмана-Вунша, описываются аффинные модели; предлагается метрика, использующая специфику рассматриваемой предметной области, являющаяся аффинной модификацией метрики Нидельмана-Вунша.

Стоимость замены и удаления (добавления) различных символов можно назначить, руководствуясь несколькими простыми соображениями. Прежде всего, стоимость замены символов, отличающихся только регистром, должна быть очень незначительной, возможно нулевой, т.к. в товарных предложениях (и не только) использование регистра играет скорее роль оформления, как например название фирмы “ASUS” в описаниях материнских плат “MB ASUS P5Q Deluxe Socket 775 P45” и “MB Asus M3N-HT Deluxe/HDMI S AM2”, взятых из одного и того же интернет-магазина.

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

Стоимость замены точки на запятую должна быть небольшой, в частности потому, что в одних товарных предложениях рунета целая и дробная часть числа отделяются запятой, согласно правилам русского языка, но во многих других описаниях разделителем служит точка, как это принято в англоязычных странах. Реальные примеры: «3,16GHz» и «2.66 ГГц».

Вообще, данный пример показывает, что в случае товарных предложений компьютерных комплектующих часто смешиваются русские и английские обозначения; иногда используется транслитерация. Довольно естественно требовать того, чтобы стоимость русско-английской транслитерации букв была меньше стоимости произвольной замены букв. Подобная мера позволит системе находит соответствия между такими парами слов, как «CPU» и «ЦПУ».

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

Стоит также отметить, что в программной реализации алгоритма поиска соответствия фраз атрибутам функция релевантности фразы атрибуту, нормированная на отрезок [0,1], умножается на коэффициент , где - некоторый небольшой коэффициент, - длина фразы, с целью мягкого штрафа за оставшиеся без соответствия участки спецификации.

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

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

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

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

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

В получаемых результатах работы системы возможны ошибки следующих видов:

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

2. Система не выделяет в исходной спецификации некоторую фразу, в то время как человек выделяет её и сопоставляет ей некоторый синсет. Иными словами, осуществляется пропуск существующих фраз.

3. Система правильно выделяет фразу, но сопоставляет ей неправильное значение атрибута.

Заметим, что традиционное разделение ошибок на ошибки первого и второго типа не совсем подходит описываемой системе.

Графики количества ошибок приведены в диссертации.

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

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

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

Вероятность события А при условии, что произошло некоторое событие В, называется условной вероятностью и обозначается через . По правилу Байеса . Пусть - решение, в поддержке которого участвует гипотеза Н. При подтверждении решения мы повышаем оценку достоверности гипотезы Н по правилу , где - коэффициент инерции для повышения. Оценка достоверности действительно повышается, так как, если Н входит в Е (, ), то . При отклонении решения мы понижаем оценку достоверности гипотезы Н по правилу , где - коэффициент инерции для понижения. , поэтому оценка достоверности действительно понижается. Коэффициенты инерции позволяют сглаживать резкие скачки в оценке достоверности, кроме того, они не позволяют оценкам достоверности принимать краевые значения 0 и 1.

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

В заключении приведены основные результаты исследования и намечены направления дальнейшей работы.

В приложении приведены основные компоненты реализованного программного комплекса.

Основные результаты и выводы диссертации

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

2. Предложен алгоритм поиска известных фраз в спецификации.

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

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

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

Список публикаций по теме диссертации

1. Ашихмин А. М. На пути к семантической паутине: поиск среди товарных предложений / А.М. Ашихмин // Труды Института системного анализа Российской академии наук. Динамика неоднородных систем. - Москва, 2007. - с. 184-189.

2. Ашихмин А. М. Оценка вероятности несовместных и условно независимых логических комбинаций булевых случайных переменных / А.М. Ашихмин, И.В. Севастьянов // Труды Института системного анализа Российской академии наук. Динамика неоднородных систем. - Москва, 2006. - с. 110-115.

3. Ашихмин А. М. Приведение кратких спецификаций к типовому виду в задаче автоматизированной обработки прейскурантов / Ашихмин А. М. // Труды XLVII научной конференции МФТИ. Часть VII. Управление и прикладная математика. - Москва - Долгопрудный, 2004. - c. 174.

4. Ашихмин А. М. Применение вероятностной логики для семантического поиска товаров в Интернете / Ашихмин А. М., Севастьянов И. В. // Известия АН. Теория и системы управления. - Москва, 2005. - № 5 - c. 130-136.

5. Ашихмин А. М. Семантический поиск в автоматизированной системе электронной торговли / Ашихмин А. М., Захаров В. Н., Севастьянов И. В. // Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сборник научных трудов III-ого Международного научно-практического семинара - Москва-Коломна, 2005. - с. 330-334.

6. Ашихмин А. М. Семантический поиск среди товарных предложений в Интернете / А.М. Ашихмин, В.Н. Захаров, И.В. Севастьянов // Информационные технологии: Материалы Всерос. научно-техн. конф. - Воронеж, 2005. - с. 114-116.

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