автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Извлечение информации из кратких текстовых спецификаций с заданным списком атрибутов

На правах рукописи

ии344Т34и

Ашнхмин Андрей Михайлович

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

Специальность 05.13.18 - Математическое моделирование, численные методы и

комплексы программ

Автореферат диссертации

на соискание ученой степени кандидата физико-математических паук

3 о СЕН 2008

Москва-2008

003447348

Работа выполнена на кафедре интеллектуальных систем Московского физико-технического института (государственного университета).

Научный руководитель: доктор физико-математических наук,

профессор Цурков Владимир Иванович

Официальные оппоненты: доктор физико-математических наук,

профессор Язенин Александр Васильевич;

кандидат физико-математических наук, старший научный сотрудник Аверкин Алексей-Николаевич

Ведущая организация: Институт Системного Анализа РАН

Защита состоится 16 ОК- /Jt&Olfl А* 2008 года в часов

на заседании диссертационного совета^Ц 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу: 141700, г. Долгопрудный Московской обл., Институтский пер. д.9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке МФТИ (ГУ). Автореферат разослан № 2008 г.

Ученый секретарь диссертационного совета

Федько О.С.

Общая характеристика работы

Акгуалыюсгь 1е.мы

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

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

Пользователь может осуществлять поиск по ключевым словам, но отсутствие возможности поиска по семантическим значениям атрибутов существенно повышает долю нерелевантных результатов. Приведём в качестве примера несколько предложений из списка длиной около двух тысяч позиций, выдаваемого популярной в рунете системой поиска товаров по ключевым словам для запроса "Pentium 4 2.8":

1. INTEL Pentium4 2.8GHz 512kb 533MHz mPGA-478 BOX

2. INTEL PENTIUM 4-2800 Prescott Socket-775 (1 MB, 800MHz, BOX)

3. 306504-B21 Hewlett-Packard X2.8/400-512 ML530G2 ALL 306504-B21

4. Intel P4 2800E/1024Kb/533Mhz/S478 Prescott OEM [RK80546PE0721M]

5. Intel Socket 478 0512k FSB 533 Pentium IV 2.8 GHz

6. Intel P4-2.8GHZ Процессор Pentium IV 2.8 ГГц/ 512KB, Northwood, 533MHz, Socket 478, OEM /

Как видно, система определяет, что «4» и «IV», «2.8» и «2800», «Р4» и «Pentium 4» являются синонимами (скорее всего, это априорная информация, занесенная в систему экспертом). Но из-за отсутствия семантической информации о товарных предложениях совпадающие и различающиеся предложения идут вперемешку. Так, пятое и шестое предложения семантически

эквивалентны, остальные - нет. Пользователь вынужден выполнять дополнительную обработку результатов поиска.

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

• CPU Intel Core 2 Duo E4300, 1,8GHz, 2Mb, 800MHz Socket-775 OEM

• Socket 775 2Mb L2 FSB 0800 Intel Core2 Duo 1.8 Ghz (E4300)

• Процессор Intel "Core 2 Duo E4300" (1.80ГГц, 2МБ, 800МГц, EM64T)

Socket775

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

Актуальность темы исследования обусловлена тем, что большинство аналитиков предсказывают стабильный рост электронной коммерции в будущем; значимость электронной коммерции для рунета была отмечена на выступлении Президента Российской Федерации Д.А. Медведева на открытии 12-го Российского интернет-форума РИФ-2008. Увеличение огромного количества документов в интернете, помимо очевидных преимуществ, порождает проблемы поиска нужной (релевантной) информации, так называемые проблемы информационной перегруженности. Ещё большие трудности возникают перед компьютерными агентами (software agents), так как подавляющее большинство документов в интернете предназначено для чтения людьми.

Цель работы, задачи исследовании

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

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

Подчеркнём специфику рассматриваемых описаний объектов. Разрабатываемая система рассчитана на строковые спецификации, фактически представляющие перечисления значений атрибутов. Типичным примером такового описания является «AMD Athlon ХР 2400+, 256Kb, FSB266, Socket А (OEM)». Очень часто подобные спецификации мало напоминают связанный текст на естественном языке (например, спецификация «[BOX] Socket 775 06Mb L2 FSB 1333 Intel® Core™2 Quad 2.50 Ghz (Q9300)»). Система не предназначена для работы с описаниями типа «Переходник для установки процессора Socket 478 в материнскую плату Socket 423», где много связанного текста на естественном языке и требуется более глубокий уровень его обработки, включая грамматический разбор.

Me i оды исследонания

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

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

Научили шиш них

Тематика семантического поиска товарных предложений в интернете затрагивалась в проекте автоматизированного извлечения семантической

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

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

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

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

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

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

1 Pazienza, М Т Combining ontological knowledge and wrapper induction techniques into an e-retail system / Maria Teresa Pazienza, O. Stellato, Michele Vindigni // Workshop on Adaptive Text Extraction and Mining (ATEM03) held with ECML/PKDD - Cavtat, 2003.

2 Пападимитриу X. Комбинаторная оптимизация Алгоритмы и сложность / Пападимитриу X., Стайглиц К , пер с англ. В. Б Алексеева - М : Мир, 1985

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

ПрЛК'1 ИЧОСКЛИ лмчимость

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

Апробации и реализация результатов работы

По выполненным диссертационным исследованиям опубликовано 6 работ, в том числе три [1], [2], [4] - в ведущих научных журналах, рекомендованных ВАК РФ.

Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных конференциях и семинарах: XLVII научной конференции МФТИ, Москва-Долгопрудный, 2004 г.; III Международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 2005 г.; Всероссийской научно-технической конференции «Информационные технологии», Воронеж, 2005 г.; научных семинарах отдела сложных систем Вычислительного центра им. A.A. Дородницына РАН, 2005-2008 гг.; научных семинарах кафедры интеллектуальных систем Московского физико-технического института, 2005-2008 гг.

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

Положения, выносимые на защиту

На защиту выносятся следующие основные положения:

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

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

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

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

Gl рук гурл и объём диссер i лщш

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

Содержание работы

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

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

Вводится предположение, состоящее в том, что все рассматриваемые объекты принадлежат одной категории с, например категории центральных процессоров для настольных персональных компьютеров. Предполагается известным множество атрибутов А для категории с, причём атрибуты разделены на обязательные и необязательные, т.е. А = Атю Аа, АтпАо=0, где Ат - обязательные атрибуты, а А0 - необязательные. Атрибуты необязательны в том смысле, что для одних объектов категории они могут присутствовать, а для других - нет. Например, процессоры серии Core 2 Duo имеют модельный номер, а ранние процессоры серии Pentium 4 - нет.

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

же значению некоторого атрибута (т.е. контекстом в данном случае является атрибут). Далее в работе термины «синсет» и «значение атрибута» используются как взаимозаменяемые. Множество {"1,8СНг", "1.8 вИг", "1.80ГГц", "1,80 ГГц"} - это пример синсета, являющегося значением атрибута «Тактовая частота» для категории процессоров. В каждом синсете выделяется некоторая фраза се 5, которая объявляется канонической, и которая используется для нормативного (желаемого экспертом) описания объекта. Скажем, для приведённого примера синсета канонической может быть фраза "1,80 ГГц".

Для иллюстрации приведём значения атрибутов товарного предложения одного процессора (Intel Core 2 Duo Е4300 в коробочной поставке).

Русское название атрибута Английское название атрибута Значение (каноническая фраза)

Производитель Vendor Intel

Серия Line Core 2 Duo

Модельный номер Model Number E4300

Тактовая частота Frequency 1,8 ГГц

Объём кэша 2-го уровня L2 Cache 2 МБ

Частота системной шины FSB 800 МГц

Разъём Socket LGA775

Тип поставки Packaging BOX

Таблица 1. Значения атрибутов товарного предложения одного процессора

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

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

Краткую текстовую спецификацию х (частично структурированное описание объекта), являющуюся последовательностью символов - строкой

текста, после прохождения лексического анализа можно рассматривать как последовательность слов w,,l<i<n. Например, принимая пробелы и запятые за разделители, спецификацию "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"). Слово if представляет собой некоторую подстроку x\begir^}v]...end\\v\\ спецификации х, где begin[\v] - начальный символ слова w, a end{w] - конечный. Фраза р определяется как результат конкатенация (с сохранением промежуточных разделительных символов исходной строки) одного или нескольких подряд идущих слов w,,...,\k>\,i + k-\<n. Т.е. имеет место равенство р = w, Ф...Ф=x[begin[wl~\...end[wl+k_x}}, где Ф обозначает конкатенацию с сохранением разделительных символов из х. Например, конкатенация слов "Г' и "8GHz" из приведённого выше примера представляет собой фразу "1,8GHZ". Под сегментацией Р = (pt,..,pn) спецификации х будем понимать разбиение х на фразы: х = р, Ф ...Ф р„.

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

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

Интерес представляет функция совокупной релевантности г((р1,а1),...(рт,ат)) сопоставления последовательности фраз соответствующим атрибутам. Используя естественное предположение о взаимной независимости по предпочтениям, функцию совокупной релевантности можно представить как аддитивную по атрибутам функцию релевантности, т.е. r{4P\,^),...(pm,am)) = 'YJf{j)l,a,). Если нормировать функции релевантности /

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

r((pi,ai),...(pm,am)) = £w,r4(p;), где весовые коэффициенты w, зависят лишь /

от обязательности/необязательности атрибута (весовой коэффициент обязательных атрибутов больше).

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

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

argmaxmaxr(iU),

А/ /'

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

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

Sea

доставляющий максимум, пусть будет S' =argmaxr(p,S). Если максимум т

Sea

больше или равен некоторому пороговому значению , то в качестве синсета, соответствующего фразе р, системой предлагается S*. Если т меньше порога но больше или равен некоторому порогу ¿i2,0<ß2 <//,, то в качестве синсета, соответствующего фразе р, предлагается новый (не известный ранее) синсет S' атрибута a. S' полагается равным {р}, т.е. содержащим единственно фразу р, которая полагается канонической. Задача автоматического построения канонической фразы в данном исследовании не рассматривается. Если же m<ß2, то фраза р полагается неотносящейся к атрибуту а и игнорируется.

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

11

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

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

Определив функцию подобия двух строк, можно определить функцию релевантности r(p,S) фразы р синсету S как максимальное значение функции подобия фразы р фразам синсета S: r(p,S) = max f(p,q). А функцию

q<-S

релевантности г(р,а) фразы р атрибуту а можно определить как максимум функции релевантности фразы р синсетам атрибута а: r(p,a)=maxr(p,S).

Sea

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

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

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

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

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

12

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

Схема работы алгоритма на псевдокоде3 выглядит так: Lookup_Known_Phrases(A'S, IV, FA)

1 ОР<-0

2 for / 1 to length[W]

3 do for j i to length[if]

4 do if слова lv[i].....iv\j] идут подряд в x

5 then Insert_Sorted(OP, W[i]Ф... 0 W\j\)

6 IR 0

7 while ОРФ0

8 do p <- Dequeu(OP)

9 if Contains(0, p) and Filter_By_Attributes(A:5[p], FA) Ф 0

10 then lR[p] *- Filter_By_Attributes(AT5[p], FA)

11 Remove_OverIaps(OP, p)

12 AL*- 0

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

14 do Insert_All(/i£, Extract_Attributes(v))

15 if —0

3 Алгоритмы, построение и анализ. / Томас X. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн - 2-ое изд - М : Издательский дом «Вильяме», 2007

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

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

18 do iv[p][attribute|>]] <- length|>]

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

20 /? <— 0

2 I for (для) всех ключей /; ассоц. массива РА

22 do for (для) всех j из /ЛИ

23 do if attribute^] = />ЛМ

24 then Л[р]<- s

25 Remove(/v/, attribute^])

26 Remove_OverIaps(W,p)

27 if Л = 0

28 then return 0

29 Put_All(/?, Lookup_Known_Phrases(0, IV, FA))

30 return R

В диссертации даются пояснения к работе алгоритма, и обосновывается оценка общего времени работы - 0(n2[log(m) + п2]), где т - количество фраз из известных синсетов, п - количество слов в спецификации.

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

(V/ </?->/,=«;,)& (1р = /и, + тр,Л) & (V/ > р -> lp = т^,)]. Обратное

отношение будем называть слиянием двух соседних элементов.

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

После поиска фраз из известных синсетов в обрабатываемой спецификации х мы получаем разбиение атрибутов на два класса: атрибуты Ат, поставленные в соответствие фразам х, и атрибуты Af, оставшиеся без

соответствия (А^ = А \ Ат) - свободные атрибуты. Слова также

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

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

Пусть имеется всего / участков без соответствия, имеющих длины п,,

1 </</. При ограничении в максимум к слов в фразе число разбиений / /

составляет £ = Y\s{nl,k)=Y\f^. Теоретически в худшем случае £ растёт

I I

экспоненциально с ростом и, но в лучшем случае без соответствия известным фразам из синсетов остаётся небольшое число слов.

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

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

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

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

Теорема 1. Если для некоторого двудольного графа С с помощью венгерского алгоритма было найдено оптимальное паросочетание, то для графа С, полученного из £? изменением весов рёбер, инцидентных некоторой вершине V, оптимальное паросочетание можно найти за время 0(|К|2), используя результаты венгерского алгоритма для графа С.

Схема доказательства теоремы. Разметка, допустимая для С, останется допустимой в С, если мы обновим только значение для вершины V. Поэтому паросочетание в подграфе равенства £, графа О будет паросочетанием в подграфе равенства Е] графа С, если из него удалить ребро, инцидентное V. Поэтому, для нахождения оптимального паросочетания в С требуется выполнение только одной фазы венгерского алгоритма, что требует 0(\У |2) операций.

Описанная выше оптимизация позволяет сократить общее время нахождения соответствия атрибутам для неизвестных фраз с 0(£-и3) до

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

Пусть имеется ц возможных фраз спецификации, оставшихся без соответствия, и /? свободных (оставшихся без соответствия) атрибутов, для каждой пары фраза-атрибут известно значение функции релевантности г(р,а)> 0, требуется найти частично определённое взаимно однозначное

соответствие фраз атрибутам {(р,,а,)}, максимизирующее сумму ^г(р,,а,), и

I

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

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

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

Существует алгоритм нахождения паросочетания максимального веса в произвольном графе, родственный венгерскому. Время его работы составляет 0{\ V |4), что в нашем случае есть 0((д + /з)4).

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

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

17

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вероятность события А при условии, что произошло некоторое событие В, называется условной вероятностью и обозначается через Р(А\В). По

правилу Байеса Р(А [ В) = ^р^^ ~ ^/^д^ f(/l). Пусть Е - решение, в

поддержке которого участвует гипотеза Н. При подтверждении решения мы повышаем оценку достоверности гипотезы H по правилу Р(П\Е) + аР(Н)

/>(//) =-1—---—, где а - коэффициент инерции для повышения.

1 + а

Оценка достоверности действительно повышается, так как, если H входит в Е

(£ = [//,'&...&//,''Jv.. v [//,"'&...&//£], Я = //',), то Р(Е\Н)>Р(Е). При

отклонении решения мы понижаем оценку достоверности гипотезы H по

_„„ч Р{111 Е) + fiP(H) _ ,,

правилу Р(//) =-!-j——-, где fi - коэффициент инерции для

о/ nm Р(А&В) Р(В\ A) \-P(B\A)d...

понижения. Р(А\В) = ——=—-- 1 Р(А) =-1—1—-Р(А), поэтому

Р(В) Р{В) 1 -Р(В)

оценка достоверности действительно понижается. Коэффициенты инерции

позволяют сглаживать резкие скачки в оценке достоверности, кроме того, они

не позволяют оценкам достоверности принимать краевые значения 0 и 1.

Если достоверность вывода вычисляется, считая различные вхождения одной и той же гипотезы независимыми, то надо соответствующим образом учесть это при использовании правила Байеса. Пусть при оценке достоверности вывода имеется п вхождений гипотезы Я, тогда имеем дя, & н2 &...&//„ I Е)=^\М1&Н2&...&Н„)ПИ]&И2&...&Ип)__

Р(Е)

Р(Е\Н)Р\Н) ..

——р^ — > отсюда, повышенная оценка достоверности гипотезы II (без

инерции) вычисляется как />'(#) = !^/>'(#, &Я2 &...&Я) =

?]Р{Я, & Я2 & ...& Я„ I Е)=„ £УШй * Р(Н). Для пониженной оценки

V

достоверности имеем Р\Н) = Р{Н).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[2] - алгоритм приближённой оценки вероятности;

[4] - правила переоценки достоверности гипотез;

[5], [6] - математическая модель унификации товарных предложений.

Ашихмин Андрей Михайлович

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

Автореферат

Подписано в печать 08 09 2008 г Формат 60x84 1/16 Бумага офсетная Печать офсетная Уел печ л 1,0 Тираж 80 экз Заказ

Государственное образовательное учреждение высшего профессионального образования Московский физико-технический институт (государственный университет) Отдел автоматизированных систем «ФИЗТЕХ-ПОЛИГРАФ»

141700, Московская обл , г Долгопрудный, Институтский пер, 9

Введение.

Глава 1. Математическая модель проблемы.

Основные определения.

Предлагаемая схема извлечения значений атрибутов.

Релевантность фразы синсету и атрибуту.

Глава 2. Алгоритмы нахождения соответствия фраз атрибутам.

Число разбиений последовательности слов на фразы.

Поиск известных системе фраз.

Оптимальное паросочетание в двудольном графе. Венгерский алгоритм.

Генерация разбиений на фразы из ограниченного числа слов.

Соответствие атрибутам для неизвестных фраз.

Сведение к поиску паросочетания в произвольном графе.

Глава 3. Строковые метрики.

Основные определения. Расстояние Левенштейна.

Аффинные метрики.

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

Обучение параметров метрики.

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

Краткое описание программной реализации. Методика тестирования.

Виды ошибок. Результаты тестирования.

Глава 5. Унификация спецификаций при отсутствии списка атрибутов.

Постановка задачи.

Нахождение соответствующей типовой спецификации.

Обучение.

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

Рассмотрим существующий в настоящее время процесс поиска и возникающие при этом проблемы. В российском сегменте интернета {рунете) существует достаточно много систем, специализирующихся на поиске среди товарных предложений (например, [80], [87]). Этим системам присущи два недостатка: они либо не обладают семантической информацией о товарных !< предложениях (за исключением информации о категориях), либо требуют от фирм-партнёров предоставления семантической информации в некотором { специальном формате, например Yandex Market Language [83].

Пользователь может осуществлять поиск по ключевым словам, но * отсутствие возможности поиска по семантическим значениям атрибутов существенно повышает долю нерелевантных результатов. Приведём в качестве примера несколько предложений из списка длиной около двух тысяч позиций, выдаваемого популярной в рунете системой поиска товаров по ключевым словам для запроса "Pentium 4 2.8":

1. INTEL Pentium4 2.8GHz 512kb 533MHz mPGA-478 BOX

2. INTEL PENTIUM 4-2800 Prescott Socket-775 (1MB, 800MHz, BOX)

3. 306504-B21 Hewlett-Packard X2.8/400-512 ML530G2 ALL 306504-B21

4. Intel P4 2800E/1024Kb/533Mhz/S478 Prescott OEM [RK80546PE0721M]

5. Intel Socket 478 0512k FSB 533 Pentium IV 2.8 GHz

6. Intel P4-2.8GHZ Процессор Pentium IV 2.8 ГГц/ 512KB, Northwood, 533MHz, Socket 478, OEM /

Как видно, система определяет, что «4» и «IV», «2.8» и «2800», «Р4» и «Pentium 4» являются синонимами (скорее всего, это априорная информация, занесённая в систему экспертом). Но из-за отсутствия семантической информации о товарных предложениях совпадающие и различающиеся предложения идут вперемешку. Так, пятое и шестое предложения семантически, эквивалентны, остальные - нет. Пользователь вынужден выполнять дополнительную обработку результатов поиска.

Вариации в написаниях товарных предложений могут быть связаны с принятым стилем, опечатками, использованием сокращений, употреблением терминов без перевода с английского языка, выбором синонимов. В качестве иллюстрации приведём описание в нескольких популярных в рунете электронных магазинах [82], [71], [84] одного и того же процессора для настольных компьютеров:

• CPU Intel Core 2 Duo E4300, 1,8GHz, 2Mb, 800MHz Socket-775 OEM

• Socket 775 2Mb L2 FSB 0800 Intel Core2 Duo 1.8 Ghz (E4300)

• Процессор Intel "Core 2 Duo E4300" (1.80ГГц, 2МБ, 800МГц, EM64T)

Socket775

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

Актуальность темы исследования обусловлена тем, что большинство аналитиков предсказывают стабильный рост электронной коммерции в будущем [36]; значимость электронной коммерции для рунета была отмечена на выступлении Президента Российской Федерации Д.А. Медведева на открытии 12-го Российского интернет-форума РИФ 2008. Увеличение огромного количества документов в интернете, помимо очевидных преимуществ, порождает проблемы поиска нужной (релевантной) информации, так называемые проблемы информационной перегруженности. Ещё большие трудности возникают перед компьютерными агентами (software agents), так как подавляющее большинство документов в интернете предназначено для чтения людьми.

Инициатива семантической паутины (Semantic Web, [53]) была предложена с целью решения части этих проблем. К сожалению, её недостатком является утомительность для человека создания метаданных (семантической информации), приспособленных для компьютерной обработки. Для заполнения («накачки») семантической паутины многие исследователи предлагают использовать методы извлечения информации (information extraction), или методы неглубокой обработки текстов на естественном языке [29], [35]. Большинство работ в области извлечения информации имеют предметом исследования связанные тексты по определённой тематике. Специфика настоящего исследования состоит в том, что предметом исследования являются не просто тексты по определённой тематике, а краткие текстовые описания, в сущности представляющие перечисление значений атрибутов (краткую спецификацию) объекта с использованием множества профессиональных терминов и сокращений. Очень часто такие спецификации мало напоминают связанный текст на естественном языке (например, спецификация «[BOX] Socket 775 06Mb L2 FSB 1333 Intel® Core™2 Quad 2.50 Ghz (Q9300)»).

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

Подчеркнём специфику рассматриваемых описаний объектов. Разрабатываемая система рассчитана на строковые спецификации, фактически представляющие перечисления значений атрибутов. Типичным примером такового описания является «AMD Athlon ХР 2400+, 256Kb, FSB266, Socket А (OEM)». Система не предназначена для работы с описаниями типа «Переходник для установки процессора Socket 478 в материнскую плату Socket 423», где много связанного текста на естественном языке и требуется более глубокий уровень его обработки, включая грамматический разбор.

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

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

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

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

Разрабатываемая на основе предложенной математической модели интеллектуальная система занимает промежуточное положение между следующими двумя большими классами систем. а) Системами сопоставления записей (обнаружения дубликатов, [16]), в большинстве работ использующих некоторую строковую метрику с настраиваемыми (обучаемыми) параметрами [4], [5]. б) Системами извлечения информации [19], [7], обычно требующими большого объёма составляемых человеком правил и привязанными к конкретной узкой предметной области.

Замечание. Термин «сопоставление записей» (record linkage) используется статистиками, эпидемиологами, историками и другими. Коммерческие базы данных и системы обработки электронной почты ссылаются на него как «обработка с целью слияния/очистки» (merge/purge processing) или «очищение списков» (list washing). Специалисты в области информатики часто используют термины «согласование данных» (data matching) или «задача идентификации объекта» (object identity problem). Другие наименования, описывающие то же понятие, включают «разрешение сущностей» (entity resolution), «устранение неоднозначности сущностей» (entity disambiguation), «обнаружение дубликатов» (duplicate detection), «согласование записей» (record matching), «идентификация экземпляров» (instance identification), «исключение дубликатов» (deduplication) и «закалка базы данных» (database hardening). Эта путаница в терминологии привела к малому числу связей между разными сообществами исследователей (см. [8], [13]). Кроме того, к сожалению, проблема сопоставления записей слабо описана в русскоязычной технической литературе.

Настоящее исследование можно считать связанным с рекурсивным алгоритмом соответствия полей [40]. Однако, в отличие от [40], в данной работе предлагаются более сложные алгоритмы, использующие венгерский алгоритм [30], [31], [42] решения задачи о назначениях, и позволяющие установить взаимно-однозначное соответствие между фразами и атрибутами.

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

На защиту выносятся следующие основные положения:

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

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

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

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

Результаты исследования могут быть использованы на практике в системах электронной коммерции как компонент интеллектуального,

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

Рис. 1. Интеллектуальный поиск среди товарных предложений

По выполненным диссертационным исследованиям опубликовано 6 работ [65], [64], [66], [63], [62], [67], в том числе три [65], [63], [62] - в ведущих научных журналах, рекомендованных ВАК РФ.

Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных конференциях и семинарах: XLVII научной конференции МФТИ, Москва-Долгопрудный, 2004 г.; III Международном научно-практическом семинаре «Интегрированные модели и sT мягкие вычисления в искусственном интеллекте», Коломна, 2005 г.; Всероссийской научно-технической конференции «Информационные технологии», Воронеж, 2005 г. научных семинарах отдела сложных систем Вычислительного центра им. А.А. Дородницына РАН, 2005-2008 гг.; научных семинарах кафедры интеллектуальных систем Московского физико-технического института, 2005-2008 гг.

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

Заключение

Подведём основные итоги исследования.

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

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

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

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

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

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

Полезно расширить систему добавлением в неё возможности автоматического построения канонических фраз в синсетах. Допустим, что канонической записью значений атрибута «Тактовая частота» являются фразы вида «1,6 ГГц», «2,66 ГГц», «2,8 ГГц», «3,0 ГГц», а в некоторой спецификации появляется ещё не занесённая в базу частота в 3,2 ГГц, обозначенная как «3.20ГТц». Разработанная в диссертации система способна определить, что «3.20ГГц» представляет новое значение атрибута «Тактовая частота», но неспособна составить для этой фразы канонический вариант «3,2 ГГц». Полезными для решения этой задачи могут оказаться исследования в области автоматического построения грамматик, основанного на индуктивном логическом программировании [49].

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

Нелишним было бы привлечение некоторых методов более глубокой обработки текстов на естественном языке, таких как грамматический анализ [86], [47], использование тезаурусов общеупотребительной лексики, например WordNet [15], и других приёмов. Это позволило бы обрабатывать спецификации вида «Переходник для установки процессора Socket 478 в материнскую плату Socket 423», хотя, конечно, следует заметить, что проблема обработки произвольных текстов на естественном языке далека от темы данной работы и является очень глубокой.

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

1. Allchin, D. Error Types / Allchin, Douglas // Perspectives on Science. 2001 -Vol. 9, No.l - p. 38-58.

2. Alpaydin, E. Introduction to Machine Learning / Ethem Alpaydin. MIT Press, 2004. - 415 p. - (Adaptive Computation and Machine Learning).

3. Arnold K. The Java™ Programming Language / Ken Arnold, James Gosling, David Holmes. 4th ed. - Addison-Wesley Professional, 2005. - 928 p.

4. Bilenko, M. Learning to combine trained distance metrics for duplicate detection in databases / Mikhail Bilenko and Raymond J. Mooney // Technical Report AI 02-296, Artificial Intelligence Lab, University of Texas at Austin. -2002.

5. Chapman S. String similarity metrics for information integration Electronic resource. / Sam Chapman Electronic publication. - 2006-. - Access http://www.dcs.shef.ac.uk/~sam/stringmetrics.html, free.

6. Chinchor, N. A. Overview of MUC-7/MET-2 / Nancy A. Chinchor // Proceedings of the Seventh Message Understanding Conference(MUC7) -1998.

7. Christen, P. Febrl Freely extensible biomedical record linkage / Christen, Peter, Churches, Tim // ANU Computer Science Technical Reports. - 2002.

8. Cohen, W.W. A Comparison of String Distance Metrics for Name-Matching Tasks / William W. Cohen, Pradeep Ravikumar, Stephen E. Fienberg // Proceedings of the IJCAI-2003. 2003. - p. 73-78.

9. Damerau, F.J. A technique for computer detection and correction of spelling errors / F.J. Damerau // Communications of the ACM. 1964. - v. 7, n. 4 - p. 171-176.

10. Debreu, G. Topological methods in cardinal utility theory / G. Debreu // Mathematical methods in the social sciences. Stanford, California : Stanford University Press, 1960.

11. Description logic handbook / F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider. Cambridge University Press, 2003. - 574 p.

12. Elmagarmid, A. Duplicate Record Detection: A Survey / Elmagarmid, A.K. Ipeirotis, P.G. Verykios, V.S. // IEEE Transactions on Knowledge and Data Engineering 2007 - Vol. 19, Iss. 1-p. 1-16.

13. Extensible Markup Language (XML) Electronic resource. / W3C Electronic publication. - W3C,1996- - Access http://www.w3.org/XML, free.

14. Fellbaum, C. WordNet: An Electronic Lexical Database / Christiane Fellbaum. The MIT Press, 1998. - 445 p.

15. Fellegi, I.P. A Theory for record linkage / Ivan P Fellegi, Alan В Sunter // Journal of the American Statistical Association 1969 - Vol. 64, No. 328 - p. 1183-1210.

16. Fiscus, J. Multiple dimension Levenshtein edit distance calculations for evaluating automatic speech recognition systems during simultaneous speech / Jonathan Fiscus, Jerome Ajot, Nicolas Radde, Christophe Laprun // Proceeding of LREC — 2006.

17. Fred, A. A comparative study of string dissimilarity measures in structural clustering / A. Fred and J. Leitao // Proc. Int'l Conf. Advances in Pattern Recognition. 1998. - p. 385-394.

18. GATE: A framework and graphical development environment for robust NLP tools and applications / H. Cunningham, D. Maynard, K. Bontcheva, V. Tablan

19. Proceedings of the 40th Anniversary Meeting of the Association for Computational Linguistics (ACL'02). Philadelphia, 2002.

20. Gotoh, O. An improved algorithm for matching biological sequences / Gotoh, O. // Journal of Molecular Biology. 1982 - Vol. 162, No. 3 - p. 705-708.

21. Graham, T. Unicode: A Primer / Tony Graham. Wiley, 2000. - 528 p.

22. Hamming. R. W. Error detecting and error correcting codes / Richard W. Hamming // The Bell System Technical Journal. 1950. - Vol. 26, No. 2 — p. 147-160.

23. HeJ3, A. An iterative algorithm for ontology mapping capable of using training data / Andreas HeB // The Semantic Web: Research and Applications. — 2006 -p. 19-33 (Lecture notes in computer science).

24. Hidden Markov models and the Baum-Welch algorithm / Lloyd R. Welch // IEEE Information Theory Society Newsletter. 2003. - 53 (4).

25. Jaro, M. A. Advances in record linking methodology as applied to the 1985 census of Tampa Florida / M. A. Jaro // Journal of the American Statistical Society. 1989.-Vol. 84-p. 1183-1210.

26. Jaro, M. A. Probabilistic linkage of large public health data file / M. A. Jaro // Statistics in Medicine. 1995 - Vol. 14 - p. 491^98.

27. Kalai, A. Probabilistic and on-line methods in machine learning: PhD. Thesis / Adam Kalai, Santosh Vempala; Carnegie Mellon University. Pittsburgh, 2001.

28. KIM: Semantic Annotation Platform / Borislav Popov, Atanas Kiryakov, Angel Kirilov, Dimitar Manov, Damyan Ognyanoff, Miroslav Goranov // The

29. SemanticWeb. ISWC 2003. 2003. - Volume 2870/2003 - p. 834-849. -(Lecture notes in computer science).

30. Kuhn, H. W. The Hungarian method for the assignment problem / Harold W. Kuhn // Naval Research Logistics Quarterly. 1955 - V. 2 - p. 83-97.

31. Kuhn, H. W. Variants of the Hungarian method for assignment problems/ Harold W. Kuhn // Naval Research Logistics Quarterly. 1956 - V. 3 — p. 253-258.

32. Maedche, Er. Bootstrapping an ontology-based information extraction system / Er Maedche, Giinter Neumann, Steffen Staab // Studies in Fuzziness and Soft Computing. Intelligent Exploration of the Web. 2003. - p. 345-359.

33. Maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains, A / L. E. Baum, T. Petrie, G. Soules, and N. Weiss // The Annals of Mathematical Statistics. 1970. - vol. 41, no. 1 - p. 164-171.

34. McDowell, L.K. Ontology-driven information extraction with OntoSyphon / Luke K. McDowell and Michael Cafarella // The SemanticWeb. ISWC 2006. -2006. Volume 4273/2006 - p. 428-444. - (Lecture notes in computer science).

35. Means, G. Meta capitalism: the E-business revolution & the design of 21st century companies and markets / Grady Means, David Schneider — New York : Wiley, 2000. -208 p.

36. Merging the results of approximate match operations / Sudipto Guha, Nick Koudas, Amit Marathe, Divesh Srivastava // Proceedings of the Thirtieth international conference on Very large data bases. 2004. - Vol. 30 — p. 636647.

37. Mohri, M. Weighted finite-state transducers in speech recognition / Mehryar Mohri, Fernando Pereira, Michael Riley // Computer Speech & Language. -2002. Vol. 16, Iss. 1 - p. 69-88.

38. Monge, A.E. Integrating external information sources to guide worldwide web information retrieval / Alvaro E. Monge, Charles P. Elkan // AAAi 1995 Fall Symposium on Knowledge Navigation and Retrieval. 1995 - p. 1-12.

39. Monge, A.E. The field matching problem: Algorithms and applications / Alvaro E. Monge and Charles P. Elkan // Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. 1996 — p. 267-270.

40. Monge, A.E. The WEBFIND tool for finding scientific papers over the worldwide web / Alvaro E. Monge, Charles P. Elkan // Proceedings of the Third International Congress on Computer Science Research. 1996.

41. Munkres, J. Algorithms for the assignment and transportation problems / James Munkres // Journal of the Society of Industrial and Applied Mathematics. -1957-Vol. 5, No l,p. 32-38.

42. Needleman, S.B. A general method applicable to the search for similarities in the amino acid sequence of two proteins / Needleman S.B., Wunsch C.D. // Journal of Molecular Biology. 1970 - Vol. 48, No. 3 - p. 443-453.

43. Pazienza, M.T. Combining ontological knowledge and wrapper induction techniques into an e-retail system / Maria Teresa Pazienza, O. Stellato, Michele Vindigni // Workshop on Adaptive Text Extraction and Mining (ATEM03) held with ECML/PKDD Cavtat, 2003.

44. Pereira, F. Definite clause grammars for language analysis / F. Pereira, D. Warren // Readings in natural language processing. 1986. — p. 101-124.

45. Pulman, S. Grammar learning using inductive logic programming / Stephen Pulman and James Cussens // Oxford University Working Papers in Linguistics, Philology and Phonetics. 2001. - Vol. 6 - p. 31-45.

46. Rennie, J.D.M. Improving Multiclass Text Classification with the Support Vector Machine / Jason D. M. Rennie, Ryan Rifkin // Massachusetts Institute of Technology. Al Memo AIM-2001-026. 2001.

47. Salton, G. A vector space model for automatic indexing / G. Salton, A. Wong, and C. S. Yang // Communications of the ACM 1975 - Vol. 18, No. 11 - p. 613-620.

48. Sebastiani, F. Machine learning in automated text categorization / Fabrizio Sebastiani // ACM Computing Surveys. 2002. - Vol. 34, No. 1 - p. 1-47.

49. Spinning the semantic web: Bringing the World Wide Web to its full potential / Edited by Dieter Fensel, James A. Hendler, Henry Lieberman and Wolfgang Wahlster; foreword by Tim Berners-Lee The MIT Press, 2003. - 503 p.

50. Stoilos, G. A string metric for ontology alignment / Giorgos Stoilos, Giorgos Stamou, Stefanos Kollias // International Semantic Web Conference. — 2005 — p. 624-637.

51. String metric Electronic resource. / Wikipedia. Electronic publication. -Wikimedia Foundation, Inc., 2008. Accesshttp://en.wikipedia.org/wiki/String metric, free.

52. Unit testing Electronic resource. / Wikipedia. Electronic publication. -Wikimedia Foundation, Inc., 2008. Access http://en.wikipedia.org/wiki/Unittesting, free.

53. Winkler, W. E. The state of record linkage and current research problems / William E. Winkler. Washington, DC : Statistical Research Division, U.S. Census Bureau, 1999.

54. Алгоритмы: построение и анализ. / Томас X. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. — 2-ое изд. — М. : Издательский дом «Вильяме», 2007. — 1296 с.

55. Асанов М.О. Дискретная математика: графы, матроиды, алгоритмы / Асанов М.О., Баранский В.А., Расин В.В. Ижевск : НИЦ «Регулярная и хаотическая динамика», 2001. — 288 с.

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

57. Ашихмин А. М. Оценка вероятности несовместных и условно независимых логических комбинаций булевых случайных переменных / A.M. Ашихмин, И.В. Севастьянов // Труды Института системного анализа

58. Российской академии наук. Динамика неоднородных систем. Москва, 2006.- с. 110-115.

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

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

61. ГОСТ 7. 79-2000 (ИСО 9-95). Правила транслитерации кирилловского письма латинским алфавитом: Офиц. изд. / Межгос. совет по стандартизации, метрологии и сертификации. Минск: Межгос. совет по стандартизации, метрологии и сертификации, 2002. — 19 с.

62. Гула А.Ю. Задачи идентификации физических и юридических лиц в хранилищах данных / А.Ю. Гула, А.П. Игнатенко, А.В. Чадюк // Проблеми програмування. — 2008. № 2-3. Спещальний випуск.

63. Компиляторы: принципы, технологии и инструментарий / Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман 2-ое изд. - М. : Издательский дом «Вильяме», 2008. - 1184 с.

64. Кузьмин О.В. Обобщённые пирамиды Паскаля и их приложения. / О.В. Кузьмин. — Новосибирск : Наука, 2000. — 294 с.

65. Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов / Левенштейн В.И. // Докл. АН СССР 1965 - 163, № 4 — с. 845-848.

66. Мальцев А. И. Алгебраические системы. / Мальцев А. И. — М.: Наука, 1970.-392 с.

67. НИКС: Компьютерный супермаркет Электронный ресурс. / НИКС -Компьютерный Супермаркет Электрон, магазин - М. : «НИКС -Компьютерный Супермаркет», 1991-2008. - Режим доступа: http://nix.ru, свободный.

68. Новиков Ф. А. Дискретная математика для программистов. / Новиков Ф. А. СПб.: Питер, 2001. - 304 с.7 8.0 Л ДИ- OLDI Электронный ресурс. / ОЛДИ — Электрон, магазин М. :

69. ОЛДИ, 2000-. Режим доступа: http://oldi.ru, свободный. 79.Пападимитриу X. Комбинаторная оптимизация: Алгоритмы и сложность / Пападимитриу X., Стайглиц К.; пер. с англ. В. Б. Алексеева. — М. : Мир, 1985.-510с.

70. Прайс.РУ Price.RU Электронный ресурс. / ООО "Прайс Экспресс" -Электрон, дан. - М. : ООО "Прайс Экспресс", 1997-2008 - Режим доступа: http://price.ru, свободный.

71. Рассел, С., Норвиг, П. Искусственный интеллект: современный подход / С. Рассел, П. Норвиг. 2-ое изд. - М. : Издательский дом «Вильяме», 2006. - 1408 с.

72. Санрайз-ПРО Электронный ресурс. / Sunrise Электрон, магазин — М. : Sunrise, 2001-2008 - Режим доступа: http://pro.sunrise.ru, свободный.

73. Требования к методу передачи данных. Описание формата данных YML Электронный ресурс. / Яндекс Электрон, дан. - М. : Яндекс, 2008 -Режим доступа: http://partner.market.yandex.ru/legal/tt, свободный.

74. Ф-Центр Электронный ресурс. / Компания «Ф-Центр» — Электрон, магазин — М. : Компания «Ф-Центр», 1998-2008 Режим доступа: http://www.fcenter.ru, свободный.

75. Хачатрян А. Р. Неточный вывод на знаниях / Хачатрян А. Р. // Искусственный интеллект. В 3-х кн. Кн. 2. Модели и методы: Справочник / Под ред. Д. А. Поспелова. - М.: Радио и связь, 1990. С. 105110.

76. Хомский Н. Синтаксические структуры / Хомский Н.; пер. с англ. К. И. Бабицкого и В. А. Успенского // Новое в лингвистике. II. М. : ИИЛ, 1962. -с. 412-527.

77. Яндекс.Маркет Электронный ресурс. / Яндекс Электрон, дан. — М. : Яндекс, 1997-2008 - Режим доступа: http://market.yandex.ru, свободный.