Название: Инвариантно-параметрическое представление и обобщенная ассоциативная обработка символьной и смысловой информации(Токмаков Г. П) Жанр: Информационные системы и технологии Просмотров: 3757 |
4.3. обобщенная ассоциативная обработка на базе ипп символьной и смысловой информацииПроанализировав описанную выше процедуру отображения символьной последовательности предложения в ее ИПП, легко заметить, что оно осуществляется в форме редукции графа, состоящей из нисходящей и восходящей стадий, описанных в разделе 4.1.3. В упомянутом разделе было показано, что процедура, реализованная в форме редукции графа, обеспечивает синхронизацию между задачами на основе графа, в то время как в императивных вычислительных механизмах управление синхронизацией должен планировать сам программист. Было также отмечено, что при этом отпадает необходимость в централизованном управлении, так как связи между операциями редукции каждого редекса, называемыми обычно задачами, заложены в древовидной структуре, содержащейся в памяти машины.Чтобы облегчить изложение материала, касающегося применения новых информационных технологий для реализации процедуры анализа-синтеза предложений, опишем этот процесс на одном уровне, так как все ее уровни функционируют по идентичным алгоритмам. С этой целью рассмотрим систему морфологического анализа, приведенную в работе [106], и на этом примере выведем общие принципы использования компонентов ИПП в процессах решения задач.В отмеченной работе сведения о русском языке на уровне лексем в соответствии с ИПП представлены в виде системы пространства инвариантов, представляющего собой словарь основ и массивов параметров с информацией о грамматических категориях словоформ. В процессе функционирования уровень лексем взаимодействует с уровнем морфем, определяя,в каком из пространств инвариантов - префиксно-корневом, суффиксном или флексийном - производить поиск в той или иной ситуации.4.3.1. Пространство инвариантов ИПП как дерево поискаПеречисленные пространства инвариантов организованы в соответствии с принципами, описанными в Главе 3 и представленными на рис. 32. Тип древовидной структуры, выбранный для представления пространств инвариантов, обеспечивает как навигацию в прямом направлении, когда движение осуществляется от корневой ячейки, так и в обратном направлении, когда движение по дереву осуществляется в направлении корневой ячейки. Это свойство выбранной древовидной структуры позволяет использовать одно и то же пространство инвариантов как при анализе, так и при синтезе символьной последовательности.Навигация в прямом направлении осуществляется в соответствии с алгоритмом, приведенным на рис. 66. Напомним, что каждый узел древовидной структуры содержит поле для хранения кода Rj (i=l,...,s; j=l,...,r), поле для хранения указателя на порожденный узел УкзПрд, поле для хранения указателя на подобный узел УкзПдб. Поисковую последовательность можно представить в виде спискаKi,...,Km, (27)элемент которого Kv (v=l,...,m) в каждом цикле будет сравниваться с кодом Rj текущего узла древовидной структуры.Алгоритм поиска начинается с приема сообщения РешПД, после чего проверяется, не является ли этот элемент, сопровождаемый данным сообщением, первым среди элементов искомой последовательности. Если этот элемент оказывается первым, то производится начальная установка, когда индексы древовидной структуры указывают на первый узел (i=lj=l), а индекс поисковой последовательности (27) на первый элемент (v=l).
Рис. 66. Алгоритм поиска в древовидной структуреПосле начальной установки производится проверка наличия признака ПрзКнц. Если проверяемый признак имеет место, вырабатывается сообщение ПскПрзКнц, в противном случае осуществляется переход к следующему узлу ветви путем приращения текущего адреса на значение поля УкзПрд и вырабатывается сообщение ПскСвп. Если входной элемент оказывается не головным, вырабатывается сообщение ПскПД.Собственно процедура сравнения Kv == RJ, запускаемая по сообщению ПскСД, выделена в отдельный блок, в котором производятся сравнение и выработка по результатам сравнения сообщений Свп или !Свп. Блок-схема алгоритма процедуры сравнения, которую назовем процедурным блоком, приведена на рис. 67.Сообщения Свп и /Свп поступают на входы процедуры навигации по дереву поиска. В случае выработки сообщения !Свп проверяется признак конца блока КнцБлк подобных узлов древовидной структуры, среди которых производится поиск текущего элемента Kv. Если этот признак обнаруживается, то это означает, что был проверен последний узел блока на совпадение и что процесс поиска элемента
Рис. 70. Видоизмененная структура И-ИЛИ дереваИта^мы показали, что в качестве дерева решений при реализации преобразования последовательности компонентов в ее ИПП можно использовать пространство обобщенных структур, и провели все необходимые для этого изменения в структуре дерева решений. После этого можно приступить к описанию процедуры навигации по дереву решений, блок-схема алгоритма которой представлена на рис. 71 и описывается следующим образом.Процедура навигации по дереву решения начинается с приема сообщения ЗД(Вх) (запрос данных), по которому производится начальная установка адресов, затем проверяется наличие входных данных. В случае отсутствия вырабатывается сообщение ЗД(Вых). При наличии входного данного вырабатывается сообщение РешПД которое запускает процедуру навигации по дереву поиска. Процедура навигации по дереву поиска после своего завершения вырабатывает одно из следующих сообщений:ПскНеСвп - вызывает переход на следующую ветвь, затем проверяется наличие входного данного: в случае его отсутствия вырабатывается сообщение ЗД(Вых), а в случае наличия - вырабатывается сообщение РешПД;ПскСвп - проверяется наличие входного данного: в случае его отсутствия вырабатывается сообщение ЗД(Вых), а в случае наличия - вырабатывается сообщение РешПД;ПскПрзКнц - проверяется наличие признака ПрзКнц для текущего узла дерева решений. Если этот признак имеет место, то вырабатывается сообщение ВД(Вых), и на этом цикл процедуры завершается. В случае отсутствия проверяемого признака осуществляется переход к следующему узлу дерева решений и производится проверка наличия входного данного: в случае его отсутствия вырабатывается сообщение ЗД(Вых), а в случае наличия - вырабатывается сообщение РешПД;
Переход на другую ветвьУстановка начальных адресовПереход к следующему узлу ветвиУстановка текущих адресов
Рис. 71. Алгоритм решения задач с помощью дерева решенийСообщение ЗД(Вых) запрашивает необходимые данные у внешних процедур, которые отвечают на этот запрос выдачей необходимых данных, которые сопровождаются сообщением ВД(Вх). После поступления этого сообщения процедура навигации по дереву решения производит установку текущих адресов дерева решений,после чего вырабатывает сообщение РешПД.Итак,мы описали процесс навигации в дереве решений, в ходе которого, по сути дела, реализуется управление процессом поиска, не зависящее от содержания задачи, которое заложено в дереве поиска и строится по формализованной процедуре. Процедура навигации аналогична процедуре навигации по дереву поиска и имеет незначительное отличие. Если в дереве поиска навигация осуществляется по результатам операции сравнения кодов текущего узла и входной информации, то в дереве решений - по результатам процедуры поиска в дереве поиска. Однако если для каждого узла выделить поле указателя на процедуру обработки узла, которые возвращают одни и те же сообщения, то процедура навигации для дерева решений и дерева будет практически одинаковой. После того как мы описали все компоненты обобщенной ассоциативной обработки, можно приступить к описанию их совместного функционирования в рамках так называемого логического ассоциативного процессора.4.3.3. Логическая структура ассоциативного процессораИтак, для решения задачи анализа предложений ЕЯ мы применили метод редукции, согласно которому задача разбивается на составляющие ее подзадачи. В нашем случае информация о решаемой задаче представлена в виде ИПП символьных последовательностей, которая состоит из древовидных пространств обобщенных структур и инвариантов и массивов параметров. В данной постановке решение задачи рассматривается как поиск в пространстве инвариантов того пути или маршрута, который соответствует входной последовательности. Отличительная черта рассматриваемого варианта поисковой процедуры от классических заключается в том, что поиск осуществляется под управлением информации, содержащейся в пространстве обобщенных структур, в два этапа: на первом этапе в ходе поиска в пространстве инвариантов определяется класс эквивалентности, к которому относится входная последовательность, а на втором - осуществляется поиск в массиве параметров, относящемся к выявленному классу эквивалентности, в ходе которого определяются свойства, характеризующие конкретный экземпляр выявленного класса эквивалентности.В данной главе статические компоненты ИПП символьных последовательностей, определенных в Главе 3, дополнили процедурными компонентами, которые управляют процессом отображения символьных последовательностей в их ИПП и обратно. Здесь мы рассматриваем особый класс задач, относящийся к обработке символьных последовательностей, для которого в Главе 1 было использовано АЗУ. Рассмотренное АЗУ в отличие от классических позволяет обрабатывать последовательности произвольной длины и обладает достаточной информационной емкостью. Однако было отмечено, что единичный характер представленной в его памяти информации усложняет решение задач интеллектуального характера. В настоящей главе описан вариант ассоциативной обработки символьных последовательностей, который, благодаря использованию ИПП, имеет обобщенный характер. Поэтому описанные выше процедуры обработки символьных последовательностей сформулируем как механизм обобщенной ассоциативной обработки и построим логическую структуру АП, осуществляющего преобразование символьной последовательности в ее ИПП. В работах [95,96,97,98,99,100,101,102,103,104,105,106] предлагается вычислительный механизм, в котором используются изложенные выше принципы обработки информации. АП содержит в своей памяти декларативное описание задачи в виде структур типа "поисковое дерево". Вычислительный процесс, реализуемый в АП, сводится к выбору некоторого маршрута в поисковом дереве, зависящего от входной последовательности, и выдачи некоторого кода, соответствующего выбранному маршруту. В соответствии с данной постановкой задачи ассоциативную выборку можно представить как задачу поиска, которую формально можно определить так. Поиск представляет собой тройку (So, F, St), где S0 - множество начальных условий, F - множество операторов, отображающих одни состояния в другие, St - множество целевых состояний (решений задачи). Множество операторов F, организованное определенным образом, осуществляет процедуру поиска в поисковом дереве, для чего необходимо считывать входные данные, запустить процедуру поиска для текущего элемента данных, реагировать определенным образом на результаты поиска, считывать результаты поиска. При этом мы получаем обобщенное представление поисковой структуры, называемое "деревом решений". Как мы уже отметили выше, процедуру решения задачи также можно представить как поиск в древовидной структуре. Если в поисковом дереве ищется маршрут, соответствующий входной последовательности, то в дереве решений ищется целевое состояние. Как только такое состояние находится, в поисковом дереве фиксируется выделенный маршрут и выдается его код.
Рис. 72. Логическая структура одноуровневого ATIТаким
образом, ATI содержит два типа древовидных структур, в которых содержатся
данные и логика решения задачи. Причем в обоих типах структур необходимо
осуществлять навигацию по дереву. Поэтому требуется еще одна структура,
управляющая поисковой процедурой, суть которой заключается в следующем. После
установки начального состояния для каждого дерева вызывается некоторый оператор
F, который после своего завершения возвращает либо 1 (ПскПрзКнц), либо 0
(ПскСвп), либо -1 (ПскНеСвп). В зависимости от полученного результата
осуществляется навигация по древовидной структуре. Кроме этого необходимо
предусмотреть структуры для хранения входных и выходных данных. В качестве
таких структур используется память типа стек, где хранится код маршрута в
поисковом дереве и состояние дерева решений на момент принятия решения.
Структура АП представлена на рис. 72.Управляющая структура содержит процедуры
управления навигацией дерева решений и дерева поиска, а также процедуру сравнения,
которую мы выше назвали процедурным блоком. Выше мы описали работу этих
процедур по отдельности, здесь же опишем,как эти процедуры взаимодействуют в
процессе обобщенной ассоциативной обработки входных последовательностей.
Выход Г. и Вход Ti+1 Дерево поиска{ V
Рис. 74. Логическая структура многоуровневого АП одноуровневом варианте, так как процедуры навигации и сравнения не зависят от содержания задачи. Переход с одного уровня на другой при многоуровневой обработке осуществляется посредством загрузки адресов деревьев решения и памяти входных выходных данных текущего уровня.
Рис. 75. Организация взаимодействия между уровнями АПОбъединение блоков АП по линии управления представлено на рис. 75 и реализуется следующим образом. Для дерева решений каждого z'-го уровня сообщение ЗД(г+1) является инициатором начала работы г-го уровня. По этому сообщению производится начальная установка необходимых адресов и формирование сообщения ЗД(1) на (i-l)-Vi. уровень. Данный уровень формирует необходимые данные для работы текущего цикла работы z-го уровня, сопровождая их сообщением ВД(г). По поступившему сообщению начинается цикл обработки сформированных данных в соответствии с алгоритмом, описанным для одноуровневого варианта АП. После завершения каждого цикла работы /-й уровень запрашивает данные путем выдачи сообщения ЗД(1). Работа /-го уровня по запросу ЗД(г+1) завершается как только после завершения некоторого цикла работы z'-го уровня будет обнаружен признак РешКнц. При этом формируется сообщение ВД(1+1), а сформированные данные заносятся в выходную для данного уровня область памяти.Что касается верхнего и нижнего уровней АП, следует отметить следующие их особенности. Работы системы в целом начинается с выдачи сообщения ЗД(Ы+1), сформированного во внешних структурах. После этого начинается нисходящий процесс, в ходе которого производится начальная установка всех уровней АП. Процесс нисхождения завершается с формированием сообщения для самого нижнего уровня ЗД(1). Как уже было описано выше, после приема сообщения ЗД(г) процедура навигации дерева решений проверяет наличие необходимых данных в соответствующей области памяти. В данном случае необходимые данные заведомо имеются, так как в начале работы процесса ассоциативной обработки область данных нижнего уровня заполняется входной последовательностью. Поэтому на нижнем уровне сообщение ЗД(0) не формируется, и на этом процесс нисхождения завершается и начинается процесс восхождения.Восхождение представляет собой более сложный процесс и состоит из "подъемов" (выработки сообщений ВД(1+1)), "спусков" (выработки сообщений ЗД(г)), а также движений по горизонтали (обработка текущего входного данного Kv в процедурах навигации дерева решений и дерева поиска и в процедуре сравнения). Процесс восхождения завершается выдачей сообщения ВД(Ы+1), что означает выполнение запроса ЗД(Ы+1) и завершение работы АПв целом.ВЫВОДЫВ предыдущей главе, перед тем как приступить к разработке систем внешнего и внутреннего представлений,были рассмотрены принципы формирования системы знаний человека. В данной главе также рассмотрены механизмы абстрактного мышления, которые затем использованы при разработке задач анализа на базе ИПП символьных структур.Задача анализа символьных конструкций рассматривается с точки зрения преобразования их в элементы смысловых конструкций. Анализ символьных конструкций разворачивается на пяти уровнях. Так как описание уровней языковой подсистемы проведено на единой основе, то и процедуры обработки этих уровней подчинены единым правилам.Решение задачи анализа символьных конструкций рассматривается как поиск в древовидной структуре инвариантов языковых конструкций разных уровней, а логика решения задачи представлена в виде древовидной структуры, составленной из обобщенных структур языковых конструкций. Таким образом, данные и логика решения задачи представлены в виде древовидных структур, а процесс решения задачи представляет собой процесс навигации по древовидным структурам.Описанный процесс рассматривается как механизм обобщенной ассоциативной обработки, так как в его основе лежит сопоставление инвариантных структур, осуществляемое по аналогии с процессом ассоциативной выборки. Обобщенный характер этого процесса определяется тем, что сопоставление инвариантами, хранящимися в памяти осуществляется после того как в ходе анализа входного объекта определяется его ИПП. При этом инвариантная составляющая участвует в процессе ассоциативного опроса,и таким образом определяется класс эквивалентности, к которому он относится, после этого в параметрическом массиве выявленного класса сопоставляется параметрическая часть вычисленного ИПП, и только после этого определяется конкретный экземпляр данного эквивалентности.В разработанной в данной главе вычислительной модели совмещены механизмы редекса и бектрекинга, что обеспечивает обработку входной символьной последовательности с использованием многоуровневого ИПП с гибкой системой принятия решений относительно принадлежности входных объектов к тем или иным инвариантным структурам ИПП.В разработанном вычислительном механизме в качестве дерева решений, реализующего логику решения задачи ? используется пространство обобщенных структур ИПП, а в качестве пространства поиска-пространство инвариантов и массив параметров.В разработанном механизме обобщенной ассоциативной обработки, логика решения задачи, данные задачи и управляющая структура разделены, а взаимодействие между ними осуществляется посредством обмена сообщениями.Управляющие компоненты задачи в разработанном механизме обобщенной ассоциативной обработки не зависят от содержания дерева решений и дерева поиска, что создает возможность реализации их в виде вложенных процедур.ЗАКЛЮЧЕНИЕВ предложенной работе осуществлено решение научной проблемы создания вычислительного механизма обобщенной ассоциативной обработки, базирующегося на ИПП символьной и смысловой информации. Важно отметить, что ИПП обеспечивает описание широкого круга проблем, что позволяет свести решение задач на его основе по единообразным алгоритмам независимо от их содержания. В основе ИПП лежит учет структуры объекта, представленной как взаимосвязь значений свойств компонентов объекта, остающихся инвариантными для всего спектра допустимых преобразований его свойств. Такой подход обеспечивает обобщение объектов в классы на основе их существенных признаков. Кроме инвариантных свойств, в ИПП представлены и так называемые несущественные свойства, обеспечивающие адекватность поведения объектов при вступлении во взаимодействие с другими объектами.Разработанный вычислительный механизм опирается на современные представления о процедурах анализа-синтеза абстрактного мышления человека и включает в себя элементы таких вычислительных механизмов, как управление потоком данных, редукция и поиск с возвратом, составляющих основу вычислительных механизмов при создании систем по новой информационной технологии.Разработанные способы представления данных и вычислительные механизмы на их основе можно реализовать программным способом используя современные средства машинного моделирования. Однако разработанный вычислительный механизм может служить теоретической базой и для создания аппаратных средств построения перспективного класса вычислительных устройств, реализующих моделирование реальной действительности посредством всестороннего учета связей моделируемых объектов. При этом можно обеспечить аппаратную поддержку наиболее интенсивно используемых функций, что может резко повысить эффективность реализации вычислительных процедур. Таковыми являются операции по обработке узлов древовидных структур, составляющие основную долю относительно операций других типов.
|
|