Название: Инвариантно-параметрическое представление и обобщенная ассоциативная обработка символьной и смысловой информации(Токмаков Г. П)

Жанр: Информационные системы и технологии

Просмотров: 3837


Скачать книгу целиком

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. Если этот признак обнаруживается, то это означает, что был проверен последний узел блока на совпадение и что процесс поиска элемента

Kv завершился неудачно с выработкой сообщения Пск'Свп. Если этот признак не обнаруживается, значение индекса j получает приращение на значение поля УкзПдб текущего узла дерева, и процедура навигации по дереву поиска снова вырабатывает сообщение ПскСД.В случае выработки сообщения Свп проверяется признак листового узла ПрзКнц. В случае отсутствия этого признака индекс i получает приращение на значение поля УкзПрд текущего узла дерева, а индекс v - на единицу, и цикл поиска текущего элемента последовательности (27) в древовидной структуре завершается с выработкой сообщения ПскСвп. Это означает, что в дереве поиска найден только текущий элемент, а в целом процедура поиска последовательности продолжается. В противном случае цикл поиска завершается выработкой сообщения ПскПрзКнц, что означает и успешное завершение поиска всей последовательности.4.3.2. Пространство обобщенных структур ИПП как дереворешенииВыше мы описали традиционный способ поиска, относящийся к классу слепых, не направленных методов, т.к. порядок раскрытия вершин не связан с информацией о наиболее эффективных путях достижения целевых вершин. Этот способ поиска можно использовать в простых случаях, когда поиск производится в одном пространстве небольшой размерности. При реализации поиска на иерархических пространствах, каковыми являются пространства из системы, приведенной на рис. 53, в процессе анализа последовательности для каждого элемента входной последовательности необходимо решать , в каком из имеющихся пространств производить дальнейший поиск. В таких случаях необходимо использовать знания более высокого уровня, чтобы ограничить число кандидатов для поиска.В этом отношении удобны методы, которые в зависимости от текущей ситуации определяют порядок запуска тех или иных задач. При этом появляется возможность использования дополнительной информации, зависящей от вида решаемой задачи и помогающей сократить поиск. Основная идея заключается в разбиении задачи на подзадачи, которые в свою очередь разбиваются на подзадачи, и так до тех пор, пока исходная задача не сведется к ряду тривиальных задач, имеющих очевидные решения. При этом мы получаем дерево решений типа И-ИЛИ, суть которого заключается в следующем.
Рассмотрим простейшую программу р, для которой необходимо выполнить процедуры q и s. Если эти процедуры завершаются успешно, то процедура р считается успешно завершенной. В противном случае выполняются процедуры г и t, и если обе эти процедуры завершаются успешно, то процедура завершается. Если хотя бы одна процедура при этом терпит неудачу, то и процедура р считается невыполненной. Описанную процедуру р можно реализовать на дереве типа И-ИЛИ, которое при этом примет вид,изображенный на рис. 68 (а).О    -узел ИРис. 68. Граф (а) и логическая структура (б) И-ИЛИ дереваВ теории ИИ дерево И-ИЛИ описывается следующим образом. В каждой своей вершине И-ИЛИ дерево имеет либо метку И, либо метку ИЛИ. Вершина И успешно разрешима только тогда, когда все ее вершины-потомки успешно разрешимы. Вершина типа ИЛИ успешно разрешима тогда, когда хотя бы одна из вершин-потомков успешно разрешима. В процессе решения задачи,начиная с корня дерева (узел р), ветвящийся процесс анализирует результаты выполнения своих вершин-потомков. Если мы находимся в вершине типа И, то проверяется, не терпит ли неудачу хотя бы одна из вершин-потомков. Если мы находимся в вершине типа ИЛИ, то проверяется, не завершается ли хотя бы одна из вершин с успехом.С точки зрения реализации вычислительного процесса И-ИЛИ дерево удобно представлять в виде предлагаемой нами древовидной структуры, приведенной на рис. 68. В этом случае процедуры, относящиеся к вершине типа Д расположены на одной ветви дерева, а процедуры, относящиеся к вершине типа ИЛИ, - на альтернативных ветвях дерева.При не выполнении хотя бы одного узла ветви данная ветвь считается невыполненной, и производится переход на альтернативную ветвь. Как только одна из ветвей дерева выполняется полностью, процедура считается успешно завершенной. В случае,если ни одна ветвь не завершается с успехом, то процедура выходит на узел F (FALSE), что означает неудачное завершение процедуры в целом. В описанной реализации И-ИЛИ дерево не требуется специальных анализирующих процедур, а процесс решения задачи реализуется аналогично процедуре поиска, описанной нами в Главе 2.А теперь задачи q,s,r и t заменим процедурами поиска (см. рис. 66), имеющими место при морфологическом анализе и описанными в предыдущем разделе. В этой системе дерево решений должно быть построено таким образом, чтобы в зависимости от текущей ситуации определяло последовательность выполнения тех или иных операций поиска. Например, при анализе словоформы дерево решений должно содержать информацию о том, что первой морфемой словоформы могут быть либо префиксная, либо корневая морфемы и, соответственно, направлять сигнал запроса данных (ЗД) пространству инвариантов, где содержатся префиксные и корневые морфемы, находящиеся на уровне морфем. По данному запросу на нижестоящем уровне производится поиск в соответствующем пространстве инвариантов,и в случае успеха выдает сигнал выдачи данных (БД) с одним из трех возможных вариантов ответа:обнаружена префиксная морфема;обнаружена корневая морфема;обнаруженная морфема может быть как префиксной, так и корневой.В зависимости от полученного ответа дерево решений уровня лексем должно выполнить одну из следующих возможных процедур:если обнаружена префиксная морфема, выполняется поиск корневой морфемы;если обнаружена корневая морфема, выполняется поиск нулевого суффикса;•     если обнаруженная морфема может быть и префиксной,и корневой одновременно, принимается решение о том, что данная морфема корневая с возможностью последующей отмены этого решения в случае его неподтверждения в ходе дальнейшего анализа; в этом случае состояние задачи возвращается на момент принятия решения, с тем чтобы принять альтернативное решение, что данная морфема является префиксной. Каждый из этих вариантов в свою очередь, в зависимости от текущей ситуации, имеет несколько возможных вариантов продолжения. В результате получаем дерево решений, управляющее процедурой морфологического анализа.Из изложенного материала следует, что в дерево решений закладываются сведения, которые,используя особенности поискового пространства,обеспечивают сокращение времени поиска. Так как при этом не пользуются формализованными процедурами, а полагаются только на интуицию разработчика, этот класс процедур поиска называется эвристическими, а используемая информация, зависящая от вида решаемой задачи, называется эвристической информацией или "знаниями". Однако эвристические методы основаны на догадках, отдельных идеях, относящихся к конкретной проблеме. Требуется разработать формальную процедуру по выявлению "знаний", которая не зависела бы от природы моделируемой ПрдО. Для этого воспользуемся тем фактом, что эвристические методы поиска, как правило, сводятся к сужению области поиска в зависимости от конкретной ситуации. Сужение области поиска означает, что имеется информация, эквивалентная правилам, которая определяет все поисковые варианты и условия их проверки. А теперь снова вернемся к системе морфологического анализа, описанной выше, и сравним процедуру анализа словоформ и пространство обобщенных структур уровня лексем, графическое изображение которого приведено на рис. 39. При этом сравнении мы обнаруживаем, что возможные поисковые варианты определяются типовыми ситуациями, или типовыми структурами объектов ПрдО, выявление которых было формализовано в Главе 2. Выявленные типовые структуры, которые образуют пространство компонентов или пространство обобщенных структур, таким образом, можно рассматривать как хранимую в непроцедурном виде информацию, которую компьютер может автономно использовать при решении проблем. Отсюда следует важный вывод: в рассматриваемом контексте пространство инвариантов ИПП играет роль дерева поиска, а пространство обобщенных структур ИПП —роль дерева решений.С учетом вышеописанного логическую структуру узлов дерева решений в отличие от узлов пространства обобщенных структур необходимо модифицировать, что сводится к добавлению в узлы дерева решений следующих полей:поля для хранения указателя на процедуру поиска (точнее,на пространство инвариантов, которое используется этой процедурой в качестве аргумента);поля для хранения указателя на переменную текущего адреса дерева решений;поля для хранения указателя на переменную текущего адреса входной последовательности;поля для хранения указателя на переменную текущего адреса дерева поиска. Логическая структура узла дерева решений приведена на рис. 69.На примере рассмотрения задачи морфологического уровня мы убедились, что использование процедуры редекса, разработанной в рамках парадигмы функционального программирования, дает неплохие результаты,когда требуется синхронизация задач, когда не требуется отменять ранее принятые решения. Основная задача, которая решается при анализе символьных последовательностей, -преобразование многоуровневых языковых конструкций в адреса функций доступа к понятиям и компонентам понятий, а также функций, обеспечивающих изменение модели ПрдО.
АдрПсл        1Рис. 69. Логическая структура узла дерева решенийПреобразование многоуровневого языкового кода в систему функций смыслового компонента осуществляется в процессе выдвижения предположений о принадлежности входного элемента к тому или иному классу. В ходе дальнейшего анализа входной символьной последовательности на более верхних уровнях эти предположения либо подтверждаются, либо опровергаются. При этом происходит интенсивный обмен информацией между уровнями языкового кода. С учетом сказанного перечислим особенности системы анализа предложения как многоуровневой системы:на уровнях языкового кода имеет место сложная иерархическая зависимость задач и подзадач;между уровнями происходит интенсивный обмен результатами принятых решений, и очень часто возникают ситуации, когда на более верхних уровнях приходится менять принятые на нижних уровнях решения;при отмене ранее принятых решений необходимо вернуться к состоянию принятия решения, принять альтернативное решение и продолжить процесс решения задач "по новому руслу".Вычислительный механизм программирования управляемого данными (механизм редекса) такие возможности не предоставляет. Здесь необходим механизм бектрекинга, рассмотренный в разделе 4.1.4 в рамках парадигмы логического программирования. Поэтому наша задача заключается в дополнении рассмотренного выше механизма редекса механизмом бектрекинга. Для решения поставленной задачи необходимо видоизменить логическую структуру дерева решений, представленного на рис. 68. Согласно традиционной структуре навигация по дереву решений возможна только от предка к порожденному узлу и от одного подобного узла к другому подобному узлу. Для реализации вышеприведенного свойства необходимо обеспечить движение по дереву в обратном направлении, т.е. от потомка к предку.Реализованное свойство необходимо для того, чтобы при возникновении тупиковых ситуаций, т.е. когда ни один из возможных вариантов решения не выполняется, отменить принятое в узле-предке решение и принять альтернативное решение. Для этого сначала необходимо перейти к узлу-предку, а затем - к его очередному подобному узлу. Логическая структура модифицированного дерева решений приведена на рис. 70.

 

 

р

 

 

 

 

 

            С

 

 

Ч

 

 

 

 

 

—с

 

 

5

 

 

 

 

  

 

Л

 

.

 

 

 

 

Г

 

 

 

 

 

—с

 

 

t

 

 

 

 

 

       

л

  

 

 

 

 

 

 

 

 

 

 

F

 

 

 

 

Рис. 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, организованное определенным образом, осуществляет процедуру поиска в поисковом дереве, для чего необходимо считывать входные данные, запустить процедуру поиска для текущего элемента данных, реагировать определенным образом на результаты поиска, считывать результаты поиска. При этом мы получаем обобщенное представление поисковой структуры, называемое "деревом решений". Как мы уже отметили выше, процедуру решения задачи также можно представить как поиск в древовидной структуре. Если в поисковом дереве ищется маршрут, соответствующий входной последовательности, то в дереве решений ищется целевое состояние. Как только такое состояние находится, в поисковом дереве фиксируется выделенный маршрут и выдается его код.

Подпись:
о! Дерево поиска г; (Данные задачи)Дерево поиска Тг (Данные задачи)Дерево поиска Tt (Данные задачи)

Рис. 72. Логическая структура одноуровневого ATIТаким образом, ATI содержит два типа древовидных структур, в которых содержатся данные и логика решения задачи. Причем в обоих типах структур необходимо осуществлять навигацию по дереву. Поэтому требуется еще одна структура, управляющая поисковой процедурой, суть которой заключается в следующем. После установки начального состояния для каждого дерева вызывается некоторый оператор F, который после своего завершения возвращает либо 1 (ПскПрзКнц), либо 0 (ПскСвп), либо -1 (ПскНеСвп). В зависимости от полученного результата осуществляется навигация по древовидной структуре. Кроме этого необходимо предусмотреть структуры для хранения входных и выходных данных. В качестве таких структур используется память типа стек, где хранится код маршрута в поисковом дереве и состояние дерева решений на момент принятия решения. Структура АП представлена на рис. 72.Управляющая структура содержит процедуры управления навигацией дерева решений и дерева поиска, а также процедуру сравнения, которую мы выше назвали процедурным блоком. Выше мы описали работу этих процедур по отдельности, здесь же опишем,как эти процедуры взаимодействуют в процессе обобщенной ассоциативной обработки входных последовательностей.Ш    - Установка текущего адреса дерева поиска О    - Установка текущего адреса дерева решенийф    - Установка начального адреса дерева поиска (5)    - Установка начального адреса дерева решений 7    ~ Переход на следующую ветвь дерева- Переход к следующему узлу ветви дереваРис. 73. Организация взаимодействия между процедурными компонентами АПОбъединение процедурных модулей АП осуществляется соединением их одноименных входов и выходов, как показано на рис. 73. При этом в целом работа АП начинается с приходом сообщения ЗД(Вх). При отсутствии входных данных формируется сообщение ЗД(Вых) и ожидается появление сообщения ВД(Вх) в ответ. После прихода этого сообщения формируется сообщение РешПД которое запускает процедуру навигации по дереву поиска. В свою очередь данная процедура запускает процедуру сравнения входного данного с содержимым текущего узла дерева поиска путем формирования сообщения ПскСД. В ответ процедура сравнения формирует либо сообщение !Свп, либо - Свп. Процедура навигации дерева поиска будет вырабатывать сообщение ПскСД до тех пор, пока процедура сравнения не ответит сообщением Свп. Для процедуры навигации по дереву решения процедура навигации по дереву поиска в процессе своей работы вырабатывает сообщения: ПскСвп, ПскКнц и Пск!Свп. В ответ на эти сообщения навигация по дереву решений продолжается либо в текущей ветви, либо переходит на другую ветвь, либо завершает свою работу выдачей сообщения ВД(Вых).В приведенной схеме вычислительного процесса данные задачи, логика ее решения и управление процессом решения разделены, что приводит к следующим важным последствиям:данные задачи разделены на инвариантную и параметрическую составляющие, и обеспечивают обобщенный характер обработки символьных последовательностей;логика решения задачи представлена как совокупность обобщенных структур, играющей роль дерева решений;процедурные компоненты задачи не зависят от содержания решаемой задачи и могут быть использованы для решения любой задачи.До сих пор, с целью упрощения изложения материала, мы сконцентрировали наше внимание на одноуровневом варианте АП. Однако на практике, как правило, имеют дело с процессами, которые удобно описывать как многоуровневые. Такими, например, являются системы синтеза и распознавания речи, описанные в Главе 1, система морфологического анализа и синтеза и система анализа и синтеза предложений, упомянутые в данной главе. В связи с этим возникает вопрос: каким образом блоки АП, описанного выше, объединяются в многоуровневую иерархическую систему.Объединение блоков АП в многоуровневую систему осуществляется по линии данных и по линии управления. Принцип объединения по линии данных заключается в том, что при анализе выходные данные (i-l)-ro уровня являются входными для г'-го уровня, а выходные данные /-го уровня - входными для го уровня. При синтезе выходные данные (i+l)-vo уровня являются входными для г'-го уровня, а выходные данные г'-го уровня являются входными для (i-l)-vo уровня. Смежные уровни имеют общую память для хранения входных-выходных данных. Логическая структура многоуровневого варианта АП приведена на рис. 74.При объединении блоков АП в многоуровневую систему важно отметить тот факт, что для N уровней мы имеем ту же управляющую структуру, что и при

Подпись: NВыход T Ц Дерево поискаТ N 1 1

Подпись:
Дерево решений T N N-го уровняВход TN и Выход ТN1А        ^ Дерево поиска

Выход Г. и Вход Ti+1 Дерево поиска{ V

Подпись: 1 § Дерево решений Т, i-го уровня i А         ^ Дерево поиска77

Подпись: Вход Tj и Выход Ти1             Дерево поискаТ'

Рис. 74. Логическая структура многоуровневого АП

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

Cen?Cen?

Рис. 75. Организация взаимодействия между уровнями АПОбъединение блоков АП по линии управления представлено на рис. 75 и реализуется следующим образом. Для дерева решений каждого z'-го уровня сообщение ЗД(г+1) является инициатором начала работы г-го уровня. По этому сообщению производится начальная установка необходимых адресов и формирование сообщения ЗД(1) на (i-l)-Vi. уровень. Данный уровень формирует необходимые данные для работы текущего цикла работы z-го уровня, сопровождая их сообщением ВД(г). По поступившему сообщению начинается цикл обработки сформированных данных в соответствии с алгоритмом, описанным для одноуровневого варианта АП. После завершения каждого цикла работы /-й уровень запрашивает данные путем выдачи сообщения ЗД(1). Работа /-го уровня по запросу ЗД(г+1) завершается как только после завершения некоторого цикла работы z'-го уровня будет обнаружен признак РешКнц. При этом формируется сообщение ВД(1+1), а сформированные данные заносятся в выходную для данного уровня область памяти.Что касается верхнего и нижнего уровней АП, следует отметить следующие их особенности. Работы системы в целом начинается с выдачи сообщения ЗД(Ы+1), сформированного во внешних структурах. После этого начинается нисходящий процесс, в ходе которого производится начальная установка всех уровней АП. Процесс нисхождения завершается с формированием сообщения для самого нижнего уровня ЗД(1). Как уже было описано выше, после приема сообщения ЗД(г) процедура навигации дерева решений проверяет наличие необходимых данных в соответствующей области памяти. В данном случае необходимые данные заведомо имеются, так как в начале работы процесса ассоциативной обработки область данных нижнего уровня заполняется входной последовательностью. Поэтому на нижнем уровне сообщение ЗД(0) не формируется, и на этом процесс нисхождения завершается и начинается процесс восхождения.Восхождение представляет собой более сложный процесс и состоит из "подъемов" (выработки сообщений ВД(1+1)), "спусков" (выработки сообщений ЗД(г)), а также движений по горизонтали (обработка текущего входного данного Kv в процедурах навигации дерева решений и дерева поиска и в процедуре сравнения). Процесс восхождения завершается выдачей сообщения ВД(Ы+1), что означает выполнение запроса ЗД(Ы+1) и завершение работы АПв целом.ВЫВОДЫВ предыдущей главе, перед тем как приступить к разработке систем внешнего и внутреннего представлений,были рассмотрены принципы формирования системы знаний человека. В данной главе также рассмотрены механизмы абстрактного мышления, которые затем использованы при разработке задач анализа на базе ИПП символьных структур.Задача анализа символьных конструкций рассматривается с точки зрения преобразования их в элементы смысловых конструкций. Анализ символьных конструкций разворачивается на пяти уровнях. Так как описание уровней языковой подсистемы проведено на единой основе, то и процедуры обработки этих уровней подчинены единым правилам.Решение задачи анализа символьных конструкций рассматривается как поиск в древовидной структуре инвариантов языковых конструкций разных уровней, а логика решения задачи представлена в виде древовидной структуры, составленной из обобщенных структур языковых конструкций. Таким образом, данные и логика решения задачи представлены в виде древовидных структур, а процесс решения задачи представляет собой процесс навигации по древовидным структурам.Описанный процесс рассматривается как механизм обобщенной ассоциативной обработки, так как в его основе лежит сопоставление инвариантных структур, осуществляемое по аналогии с процессом ассоциативной выборки. Обобщенный характер этого процесса определяется тем, что сопоставление инвариантами, хранящимися в памяти осуществляется после того как в ходе анализа входного объекта определяется его ИПП. При этом инвариантная составляющая участвует в процессе ассоциативного опроса,и таким образом определяется класс эквивалентности, к которому он относится, после этого в параметрическом массиве выявленного класса сопоставляется параметрическая часть вычисленного ИПП, и только после этого определяется конкретный экземпляр данного эквивалентности.В разработанной в данной главе вычислительной модели совмещены механизмы редекса и бектрекинга, что обеспечивает обработку входной символьной последовательности с использованием многоуровневого ИПП с гибкой системой принятия решений относительно принадлежности входных объектов к тем или иным инвариантным структурам ИПП.В разработанном вычислительном механизме в качестве дерева решений, реализующего логику решения задачи ? используется пространство обобщенных структур ИПП, а в качестве пространства поиска-пространство инвариантов и массив параметров.В разработанном механизме обобщенной ассоциативной обработки, логика решения задачи, данные задачи и управляющая структура разделены, а взаимодействие между ними осуществляется посредством обмена сообщениями.Управляющие компоненты задачи в разработанном механизме обобщенной ассоциативной обработки не зависят от содержания дерева решений и дерева поиска, что создает возможность реализации их в виде вложенных процедур.ЗАКЛЮЧЕНИЕВ предложенной работе осуществлено решение научной проблемы создания вычислительного механизма обобщенной ассоциативной обработки, базирующегося на ИПП символьной и смысловой информации. Важно отметить, что ИПП обеспечивает описание широкого круга проблем, что позволяет свести решение задач на его основе по единообразным алгоритмам независимо от их содержания. В основе ИПП лежит учет структуры объекта, представленной как взаимосвязь значений свойств компонентов объекта, остающихся инвариантными для всего спектра допустимых преобразований его свойств. Такой подход обеспечивает обобщение объектов в классы на основе их существенных признаков. Кроме инвариантных свойств, в ИПП представлены и так называемые несущественные свойства, обеспечивающие адекватность поведения объектов при вступлении во взаимодействие с другими объектами.Разработанный вычислительный механизм опирается на современные представления о процедурах анализа-синтеза абстрактного мышления человека и включает в себя элементы таких вычислительных механизмов, как управление потоком данных, редукция и поиск с возвратом, составляющих основу вычислительных механизмов при создании систем по новой информационной технологии.Разработанные способы представления данных и вычислительные механизмы на их основе можно реализовать программным способом используя современные средства машинного моделирования. Однако разработанный вычислительный механизм может служить теоретической базой и для создания аппаратных средств построения перспективного класса вычислительных устройств, реализующих моделирование реальной действительности посредством всестороннего учета связей моделируемых объектов. При этом можно обеспечить аппаратную поддержку наиболее интенсивно используемых функций, что может резко повысить эффективность реализации вычислительных процедур. Таковыми являются операции по обработке узлов древовидных структур, составляющие основную долю относительно операций других типов.

 

| Оглавление|