Технология построения многовариантных объектно-ориентированных структур текстов

Вид материала

Диссертация

Содержание PClass = "VerbPhrase" Action Node Name = "V" PClass = "VerbWordForm" /> PClass Name = "РазмерЖесткогоДиска" > Описать понятия предметной области и связи между ними в помощью системы классов Описать способы выражения концептов предметной области в тексте Роль планировщика в технологии "ТОМАТ" Планировщик, осуществляющий полный перебор

Подобный материал:

• Ландшафт области управления данными: аналитический обзор, 531.27kb.
• Развитие объектно-ориентированных систем управления базами данных, 122.52kb.
• Лекция № Элементы управления в графических и объектно-ориентированных интерфейсах, 307.9kb.
• Сводный научный отчет за 2010 г по совместному проекту «Разработка объектно-ориентированных, 204.3kb.
• Врамках настоящей работы на примере четырех произведений будут рассмотрены некоторые, 228.04kb.
• Программа вступительного экзамена по специальности 05. 13. 18 Математическое моделирование,, 115.33kb.
• Рабочая программа учебной дисциплины (модуля) Объектно-ориентированное программирование, 99.17kb.
• Исследование организационных структур управления, 469.08kb.
• Темы: Введение в язык rsl, 123.68kb.
• Программа дисциплины Объектно-ориентированное программирование Рекомендуется для направления, 591.42kb.

Pattern Name = "NP__V" ^ PClass = "VerbPhrase"

Action = "

{ проверяем условия }

! V.Transitive = False;


{ выполняем присваивания }

Text := V.Text;

Person := V.Person;

Number := V.Number;

Gender := V.Gender;

Tense := V.Tense;

Transitive := False;

...

" >


<^ Node Name = "V" PClass = "VerbWordForm" />

Pattern>

3. Извлечение информации из текста
   

Рассмотрим задачу извлечения информации из текста на примере анализа прайс-листов. Задача заключается в построении над строкой текста (представляющей собой запись в прайс-листе) вида

Toshiba Satellite Pro 6000 PIII-850/20GB/256MB/14.1" TFT/DVD/LAN/V.90/WinXP Rus


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

Сначала нужно определить, какими свойствами характеризуется ноутбук в прайс-листе. К ним относятся:

• фирма-производитель,
  
• название модели,
  
• модель и частота процессора,
  
• емкость жесткого диска,
  
• количество оперативной памяти,
  
• размер экрана,
  
• тип CD-привода,
  
• сетевая карта,
  
• модем,
  
  предустановленная операционная система.
  
  Конечно, возможны и другие характеристики, но сейчас мы ограничимся только этими.
  
  Далее определим допустимые значения приведенных характеристик:
  
• Фирма-производитель:
  

Строка из списка известных производителей, например, Toshiba, Fujitsu-Siemens, Compaq, IBM и др.

• Название модели:
  

Строка.

• Модель процессора
  

Перечислимый тип, значениями которого являются, например, следующие: Pentium, PentiumII, PentiumIII, PentiumIV, PentiumCeleron, PentiumM.

• Частота процессора
  

Целое число. Частота процессора связана с моделью процессора и это надо будет учесть при анализе. Так не может быть процессора Pentium II с частотой 850МГц.

• Емкость жесткого диска
  

Целое число в интервале от 2 до 80.

• Количество оперативной памяти
  

Перечислимый тип со значениями mem8, mem16, mem32, mem64 и т.д.

• Размер экрана
  

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

• Тип CD-привода
  

Перечислимый тип, значениями которого являются, например, CDR, CDRW, DVD, CDRWDVD.

• Наличие сетевой карты
  

Логическое значение.

• Наличие встроенного модема
  

Логическое значение.

• Операционная система
  

Характеризуется названием системы (которое можно задать перечислимым типом: Win95, Win98, WinME, Win2000, WinXP) и языком операционной системы, который также можно задать перечислимым типом.

Таким образом, первым в систему классов войдет описание перечислимых типов, которые задают значения некоторых вышеописанных свойств. Далее, поскольку каждая из характеристик выражается в записи прайс-листа своими текстовыми конструкциями, поэтому их нужно представить своим классом технологии "ТОМАТ". Для каждого класса затем нужно задать список шаблонов, которые порождают экземпляры данного объекта на основе их текстового выражения. Затем на основе уже созданных объектов будет создан объект класса Ноутбук и заполнены его свойства.

Приведем в качестве иллюстрации класс РазмерЖесткогоДиска:

<^ PClass Name = "РазмерЖесткогоДиска" >

<Field Name = "Size" DataType = "Real"

Action = "! Size >= 1 and Size <= 80" />

PClass>


<Pattern Name = "Число_GB" PClass = "РазмерЖесткогоДиска"

Action = "

! GB in ['GB', 'Gb', 'Гб', 'ГБ'];

Size := Number.Number;

" >


<Node Name = "Number" PClass = "Number" />

<Node Name = "GB" PClass = "Word" />

Pattern>


Здесь предполагается, что после препроцессора получены первичные объекты, являющиеся объектами например, следующих классов: TextChunk, Number, Word.

4. Выводы
   

Таким образом, сформулируем основные действия, которые необходимо выполнить при разработке системы классов и шаблонов в технологии "ТОМАТ":

• ^ Описать понятия предметной области и связи между ними в помощью системы классов
  

Отношение "быть частным случаем" желательно представить наследованием, технология поддерживает множественное виртуальное наследование. Решение о том, что какая-либо сущность является классом в описании, нужно принимать на основании двух критериев:

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

2.  данная сущность имеет собственные средства выражения в тексте (ей соответствует свой набор тестовых конструкций).

• ^ Описать способы выражения концептов предметной области в тексте
  

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

4. Препроцессор
   

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

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

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

Важной особенностью технологии "ТОМАТ" является следующее. Любая программная реализация ядра ТОМАТа (к которому относится компилятор и исполнитель) может использоваться для любых классов задач без переделки. В случае, если реализация предоставляет программный интерфейс времени исполнения для исполнителя (например, сделанный по технологии COM [Трельсен 2001], [Бокс 2001], [Redmond 1997] или CORBA [Pope 1998], [CORBA Specification 1999]), возможно даже использование единого ядра без его перекомпиляции.

Собственно адаптацию такого универсального ядра к решению некоторого класса задач предлагается проводить путем построение соответствующего задаче препроцессора, который как правило может быть реализован в виде независимого программного продукта. Такой препроцессор может обмениваться данными с ядром на уровне файлов. Например, в базовой реализации технологии "ТОМАТ", описанной в соответствующей главе, препроцессоры генерируют систему объектов, представленную на языке XML [XML 1.0 2000], понимаемым ядром. Разумеется, возможна и более тесная интеграция препроцессора с ядром, например, прямое взаимодействие с помощью некоторого объектно-ориентированного программного интерфейса или даже совместная компиляция (возможно, только на уровне редактора связей) препроцессора с модулями ядра. Такие подходы, хотя и требуют от автора препроцессора глубокого понимания устройства ядра, отличаются особой эффективностью в задачах, где препроцессор вызывается очень часто (например, для обработки каждой web-страницы в задаче индексирования информации в сети WWW).

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

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

5. Планировщик
   

С точки зрения процесса решения задач искусственного интеллекта с помощью технологии "ТОМАТ" планировщик — это самый ответственный компонент технологии. Планировщик в ТОМАТе — это виртуальная машина, которая управляет процессом применения шаблонов. Все остальные компоненты технологии работают под управлением планировщика.

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

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

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

Более того, возможно даже построение планировщика, оперирующего с так называемыми виртуальными объектами. Виртуальным объектом называется объект, поведение которого идентично поведению объекта, но который совершенно необязательно представлен объектом в оперативной памяти компьютера. Виртуальный объект может формироваться из каких-то объектов программной системы, в которую интегрируется технология "ТОМАТ", и, таким образом, планировщик будет напрямую обрабатывать эти объекты, пользуясь понятием объекта только умозрительно.

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

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

1. ^ Роль планировщика в технологии "ТОМАТ"
   

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

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

В некоторых системах, например, в системе "Snoop" С.А. Шарова [Sharoff 1993] алгоритм применения продукционных правил формируется неявно, с использованием порядка следования групп правил и правил в группе. Для большей выразительности обычно добавляется возможность принудительных переходов между правилами и выхода из групп. Примером может служить формализм расширенных сетей переходов [Вудс 1976], для которых возможно построение эффективных универсальных анализаторов [Шевченко 2000]. Подход, основанный на управлении за счет порядка правил, в некоторых системах развивается в полностью императивный, когда порядок, а иногда и позиция в анализируемом материале, применения продукций определяется явно программой на некотором, специфичном для системы, алгоритмическом языке. Этот язык обычно является интерпретируемым, что отрицательно сказывается на эффективности такого решения. Более того, для каждой прикладной задачи приходится писать отдельную, новую, программу применения правил, хотя бы и устроенную по подобию ранее написанных для других задач. Причина этого очевидна — ведь сами правила существенно меняются от задачи к задаче, потому и программа не получается универсальной, даже если идея, в нее заложенная, вполне подходит для решения новой задачи.

Универсальность технологии "ТОМАТ" заключается в том, что, во-первых, она не навязывает использованием некоторого "универсального" алгоритма планировщика, утверждая, что такого не существует, если требование эффективности является принципиальным. Во-вторых, что является сильной стороной технологии, она делает независимым систему правил (банков шаблонов и классов), которая призвана соответствовать семантике предметной области, и алгоритмы, по которым эти правила применяются. Таким образом, для решения задач из одной проблемной области, например, анализа текстов на естественном языке в определенной предметной области с целью извлечь из них информацию (знания) определенного вида, можно спроектировать общую систему правил, которая может незначительно модифицироваться от задачи к задаче, и в то же время применять различные алгоритмы планировщиков, подключая соответствующие модули. Но, что более ценно, планировщик, подтвердивший свою эффективность при решении задач определенного характера, можно использовать и для других задач с похожей структурой, но в другой предметной области, соответственно, требующих принципиально отличной системы классов и шаблонов.

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

2. ^ Планировщик, осуществляющий полный перебор
   

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

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

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

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

В качестве задач с короткими входными текстами можно указать на следующие возможные применения ТОМАТа:

• Построение поискового образа небольшого документа, такого, как web-страница;
  
• Проведение полного структурного анализа запроса пользователя на естественном языке к некоторой системе — примером может быть система "InBase" [Ажичаков, Егорушкин 2001], [Жигалов, Соколова 2001];
  
• Попытка классифицировать текстовый документ по некоторому смысловому признаку — фактически, частный случай задачи рубрикации — в качестве примера можно рассмотреть проект "InDoc" [Кононенко, Сидорова 2001], в котором производится классификация писем, составляющих документооборот.
  

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

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