Введение к работе
Актуальность темы
Настоящая работа посвящена извлечению информации из текстов в специфическом подмножестве естественного языка, а именно частично структурированных кратких описаний объектов (товарных предложений компьютерных комплектующих и т.п.). Изначальной проблематикой, мотивировавшей написание данной работы, послужили некоторые вопросы поиска по товарным предложениям в сети интернет.
Рассмотрим существующий в настоящее время процесс поиска и возникающие при этом проблемы. В российском сегменте интернета (рунете) существует достаточно много систем, специализирующихся на поиске среди товарных предложений. Этим системам присущи два недостатка: они либо не обладают семантической информацией о товарных предложениях (за исключением информации о категориях), либо требуют от фирм-партнёров предоставления семантической информации в некотором специальном формате (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 (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», «P4» и «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 XP 2400+, 256Kb, FSB266, Socket A (OEM)». Очень часто подобные спецификации мало напоминают связанный текст на естественном языке (например, спецификация «[BOX] Socket 775 06Mb L2 FSB 1333 Intel Core2 Quad 2.50 Ghz (Q9300)»). Система не предназначена для работы с описаниями типа «Переходник для установки процессора Socket 478 в материнскую плату Socket 423», где много связанного текста на естественном языке и требуется более глубокий уровень его обработки, включая грамматический разбор.
Методы исследования
В процессе научных исследований в работе использовались методы дискретной математики, методы теории алгоритмов, методы комбинаторной оптимизации, методы теории сопоставления записей (record linkage), а так же методы нечёткого текстового поиска.
В работе широко использовались реальные товарные предложения, доступные в российском сегменте интернета. Предложенная модель реализована как часть программного комплекса. Проведён ряд экспериментов с использованием программной реализации.
Научная новизна
Тематика семантического поиска товарных предложений в интернете затрагивалась в проекте автоматизированного извлечения семантической информации для нужд электронной коммерции CROSSMARC. Отличительная черта настоящего исследования состоит в том, что в проекте CROSSMARC информация извлекается из полнотекстовых HTML-документов, в то время как в настоящей работе внимание концентрируется на как можно более полном извлечении атрибутов из относительно небольших частично структурированных описаний.
Предлагаемая в работе математическая модель для задачи извлечения значений атрибутов из кратких текстовых спецификаций отличается от широко используемой в области информационного поиска модели представления текстов как мультимножеств из ключевых слов (модель векторного пространства). Ключевое отличие состоит в аннотировании фраз (состоящих из одного или нескольких соседних слов) значениями атрибутов.
Разрабатываемая на основе предложенной математической модели интеллектуальная система занимает промежуточное положение между следующими двумя большими классами систем.
а) Системами сопоставления записей (обнаружения дубликатов), в большинстве работ использующих некоторую строковую метрику с настраиваемыми (обучаемыми) параметрами.
б) Системами извлечения информации (information extraction), обычно требующими большого объёма составляемых человеком правил и привязанными к конкретной узкой предметной области.
Настоящее исследование можно считать связанным с рекурсивным алгоритмом соответствия полей Монге и Элкана. Однако, в отличие от подходов Монге и Элкана, в данной работе предлагаются более сложные алгоритмы, использующие венгерский алгоритм решения задачи о назначениях, и позволяющие установить взаимно однозначное соответствие между фразами и атрибутами.
Разработанная математическая модель извлечения значений атрибутов из кратких текстовых спецификаций является новым вкладом в развитие теории сопоставления записей и систем извлечения информации.
Практическая значимость
Результаты исследования могут быть использованы на практике в системах электронной коммерции как компонент интеллектуального, ориентированного на конечного потребителя поиска среди товарных предложений различных фирм, так и для внутренней агрегации и инвентаризации товаров, поступающих на склад торговой организации от оптовых поставщиков.
Апробация и реализация результатов работы
По выполненным диссертационным исследованиям опубликовано 6 работ, в том числе три [1], [2], [4] – в ведущих научных журналах, рекомендованных ВАК РФ.
Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных конференциях и семинарах: XLVII научной конференции МФТИ, Москва-Долгопрудный, 2004 г.; III Международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте», Коломна, 2005 г.; Всероссийской научно-технической конференции «Информационные технологии», Воронеж, 2005 г.
Теоретические результаты исследования реализованы в виде комплекса программ. Результаты, полученные на тестовых данных, подтверждают возможность практического применения алгоритмов, разработанных в данном исследовании.
Положения, выносимые на защиту
На защиту выносятся следующие основные положения:
-
Математическая модель процесса извлечения значений атрибутов из кратких текстовых спецификаций.
-
Алгоритм поиска известных системе фраз в текстовой спецификации.
-
Алгоритм поиска соответствия атрибутам для неизвестных фраз, использующий серию поисков оптимального паросочетания в двудольном графе с учётом результатов предыдущего нахождения оптимального паросочетания. Полиномиальный алгоритм для решения этой задачи, использующий поиск оптимального паросочетания в произвольном графе.
-
Строковая метрика, учитывающая особенности предметной области, такие как возможная транслитерация русских букв латинскими.
Структура и объём диссертации
Диссертация состоит из введения, пяти глав, заключения, списка использованных источников и одного приложения. Работа изложена на 143 страницах, список использованных источников содержит 87 наименований.
