Формирование иерархических систем

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

Рис. 2.2. Иерархия классификаторов

Из этого определения, которое трудно назвать шедевром ясности мысли, можно все-таки заключить, что общие понятия, которые образуются не путем перечисления единичных объектов, входящих в него, а путем указания ряда признаков, объявляемых существенными, и отвлечения от остальных (несущественных) признаков, можно также считать абстрактными. Мы будем рассматривать только такие общие понятия и будем называть их также абстрактными. Например, абстрактный треугольник — это любой треугольник, независимо от величины его сторон и углов и его положения на экране, следовательно, это абстрактное понятие. Такое употребление термина «абстрактный» имеет место в обиходе, а также в математике. В то же время, согласно учебнику логики, «треугольник», «квадрат» и т. п. суть конкретные общие понятия, а вот «треугольность» и «квадратность», которые им свойственны, это понятия абстрактные. По существу, здесь в ранг логического возводится чисто грамматическое различие, ибо даже с точки зрения сторонника последнего варианта терминологии обладание абстрактным понятием равнозначно обладанию соответствующим общим понятием.

Все подсистемы промежуточных уровней также являются классификаторами. Непосредственным входом k-го уровня служат состояния классификаторов k-1-го уровня, совокупность которых является для него ситуацией, подлежащей классификации. В иерархической системе, содержащей более одного промежуточного уровня, можно выделить иерархические подсистемы, охватывающие несколько уровней. Например, в качестве входных ситуаций для классификатора третьего уровня можно рассматривать состояния всех связанных с ним классификаторов первого уровня. Иерархические системы можно достраивать «вширь» и «ввысь» подобно тому, как из восьми кубиков можно сложить кубик с вдвое большим ребром, а из этих кубиков — еще больший кубик и т. д.

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

Как возникает иерархия

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

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

Рис. 2.3. Простейшие типы связей между рецепторами

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

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

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

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

 

 

12. Методы поиска в иерархических пространствах.

Методы поиска в иерархических пространствах - методы, предназначенные для работы в областях большой размерности;

Методы поиска решения в иерархических пространствах обычно делятся на:

1) поиск в факторизованном пространстве,

2) поиск в фиксированном множестве пространств

3) поиск в изменяющемся множестве пространств.

            3.2.1. Поиск в факторизованном пространстве

Во многих приложениях требуется найти все решения. Например -

постановка диагноза. Пространство называется факторизованным, если оно

разбивается на непересекающиеся подпространства (классы) частичными

(неполными) решениями. Причем по виду частичного решения можно определить,

что оно не приведет к успеху, т.е. что все полные решения, образованные из

него, не приведут к целевым решениям. Поиск в факторизованном пространстве

осуществляется на основе метола "иерархическая генерация-проверка". Если

пространство поиска удается факторизовать, то поиск даже в очень большом

пространстве можно организовать эффективно.

        3.2.2. Поиск в фиксированном множестве пространств

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

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

непригодности. Например задачи планирования и конструирования. В этих

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

пространства. Абстракция должна подчеркнуть важные особенности

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

и определить последовательность подзадач (план решения), приводящую к

решению основной задачи.

  3.2.3. Поиск в изменяющемся множестве иерархических пространств

 

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

фиксированному набору подзадач. План решения задачи в данном случае должен

иметь переменную структуру и не может быть сведен к фиксированному набору

подзадач. Для решения подобных задач может быть использован метод

нисходящего уточнения. Этот метод базируется на следующих предположениях:

возможно осуществить частичное упорядочение понятий области, приемлемое для

всех решаемых задач;

решения, принимаемые на верхних уровнях, нет необходимости отменять на

более нижних.

 

13. Методы поиска в одном пространстве.

3.1. ПОИСК РЕШЕНИЙ В ОДНОМ ПРОСТРАНСТВЕ

Методы поиска решений в одном пространстве обычно делятся на:

· поиск в пространстве состояний (рассмотрим подробно),

· поиск методом редукции,

· эвристический поиск

· поиск методом "генерация-проверка".

 

3.1.1. Поиск в пространстве состояний

 

Задача поиска в пространстве состояний обычно формулируется в теоретико-графовой интерпретации.

Пусть задана тройка (S₀, F, S_Т), где S₀ - множество начальных состояний (условия задачи), F - множество операторов задачи, отображающих одни состояния в другие, S_Т - множество конечных (целевых) состояний (решений задачи).

Цель: определять такую последовательность операторов, которая преобразует начальные состояния в конечные.

Процесс решения в виде графа G=(Х, Y), где X={х₀, х_1,...} - множество (в общем случае бесконечное) вершин графа, состояний, а Y - множество, содержащее пары вершин (x_i, x_j), (x_i, x_j)ÎX. Если каждая пара (x_i, x_j) неупорядочена, то ее называют ребром, а граф - неориентированным. Если для каждой пары (x_i, x_j) задан порядок (направление), то пару (x_i, x_j) называют дугой (ориентированным ребром), а граф называют ориентированным (направленным). Вершины пары (x_i, x_j) называют концевыми точками ребра (дуги).

Поиск в пространстве состояний естественно представить в виде ориентированного графа. Наличие пары (x_i, x_j) свидетельствует о существовании некоторого оператора f (fÎF), преобразующего состояние, соответствующее вершине x_i, в состояние x_j. Для некоторой вершины x_i выделяем множество всех направленных пар (x_i, x_j)ÎY, т.ь. множество дуг, исходящих из вершины х_i, (родительской вершины), и множество вершин (называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины x_i, соответствует множеству операторов, которые могут быть применены к состоянию, соответствующему вершине х_i.

В множестве вершин X выделяют подмножество вершин Х₀ÍХ, соответствующее множеству начальных состояний (S_o),, и подмножество вершин Х_тÍX, соответствующее множеству конечных (целевых) состояний (S_Т). Множество Х_т может быть задано как явно, так и неявно, т.е. через свойства, которыми должны обладать целевые состояния.

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

Итак, граф G задает пространство состояний, т.е. пространство, в котором осуществляется поиск решения. Построение пространства осуществляется с помощью следующего процесса. Берется некая вершина х₀ÍХ, к ней применяются все возможные операторы, порождающие все дочерние вершины. Этот процесс называют процессом раскрытия вершин. Если получена целевая вершина, то она не раскрывается. Процесс построения пространства состояний заканчивается, когда все нераскрытые вершины являются целевыми, или терминальными (т.е. вершинами, к которым нельзя применить никаких операторов). В связи с тем, что пространство состояний может содержать бесконечное количество вершин, на практике процесс порождения пространства ограничивают либо временем, либо объемом памяти.

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

· поиск в глубину (сначала раскрывается та вершина, которая была построена самой последней). Рис.3.1.а

· поиск в ширину. (вершины раскрываются в том же порядке, в котором они порождаются.) Рис.3.1.б.

 

3.1.2. Поиск методом редукции

 

При поиске методом редукции решение задачи сводится к решению совокупности образующих ее подзадач. Этот процесс повторяется для каждой подзадачи до тех пор, пока каждая из полученного набора подзадач, образующих решение исходной задачи, не будет иметь очевидное решение. Процесс решения задачи разбиением ее на подзадачи можно представить в виде специального направленного графа G, называемого И/ИЛИ-графом; Каждой вершине этого графа ставится в соответствие описание некоторой задачи (подзадачи). В графе выделяют два типа вершин: конъюнктивные вершины и дизъюнктивные вершины.

Решение задачи при поиске методом редукции (при поиске в И/ИЛИ-графе) сводится к нахождению в И/ИЛИ-графе решающего графа.

Цель процесса поиска в И/ИЛИ-графе - показать, что начальная вершина разрешима, т.е. для этой вершины существует решающий граф. Определение разрешимой вершины в И/ИЛИ-графе можно сформулировать рекурсивно следующим образом:

Конечные (целевые) вершины разрешимы, так как их решение известно по исходному предположению.

Вершина ИЛИ разрешима тогда и только тогда, когда разрешима по крайней мере одна из ее дочерних вершин.

Вершина И разрешима тола и только тогда, когда разрешима каждая из ее дочерних вершин.

 

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

 

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

 

3.1.3. Эвристический поиск

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

3.1.4.Поиск методом "генерация-проверка"

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

 

14. Методы поиска при неполных и неточных данных.

3.3. ПОИСК В АЛЬТЕРНАТИВНЫХ ПРОСТРАНСТВАХ

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

· все утверждения, описывающие состояние, являются истинными;

· применение оператора к некоторому состоянию формирует некоторое новое состояние, описание которого состоит только из истинных фактов.

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

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

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

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

Этот метод поиска называют поиском, направляемым зависимостью.

 

15. Методы представления знаний. Интегрированный метод представления знаний.

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

- формальные логические;

- продукционные;

- семантические сети;

- фреймовы;

- сценарии.

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: