|
Реферат: Методы поиска решений в экспертных системах (Компьютеры)
Поволжская государственная академия телекоммуникация и информатики
Факультет второго высшего образования
Кафедра Информационные системы в экономике
Доклад по курсу: «Проектирование информационных систем в экономике»
Выполнила: Гусарова Г.А.
Принял: Димов Э.М.
МЕТОДЫ ПОИСКА РЕШЕНИЙ В ЭКСПЕРТНЫХ СИСТЕМАХ
Методы решения задач, основанные на сведении 'их к поиску, зависят от
особенностей предметной области, в которой решается задача, и от
требований, предъявляемых пользователем к решению. Особенности предметной
области:
объем пространства, в котором предстоит искать решение;
степень изменяемости области во времени и пространстве (статические и
динамические области);
полнота модели, описывающей область, если модель не полна, то для описания
области используют несколько моделей, дополняющих друг друга;
определенность данных о решаемой задаче, степень точности (ошибочности) и
полноты (неполноты) данных.
Требования пользователя к результату задачи, решаемой с помощью
поиска, можно характеризовать
1) количеством решений : одно решение, несколько решений, все решения.
2) свойствами результата: ограничения, которым должен удовлетворять
полученный результат
3) и (или) способом его получения.
Существующие методы решения задач, используемые в экспертных системах,
можно классифицировать следующим образом:
методы поиска в одном пространстве - методы, предназначенные для
использования в следующих условиях: области небольшой размерности, полнота
модели, точные и полные данные;
методы поиска в иерархических пространствах - методы, предназначенные для
работы в областях большой размерности;
методы поиска при неточных и неполных данных ;
методы поиска, использующие несколько моделей, предназначенные для работы с
областями, для адекватного описания которых одной модели недостаточно.
Предполагается, что перечисленные методам при необходимости должны
объединяться для того, чтобы позволить решать задачи, сложность которых
возрастает одновременно по нескольким параметрам.
3.1. ПОИСК РЕШЕНИЙ В ОДНОМ ПРОСТРАНСТВЕ
Методы поиска решений в одном пространстве обычно делятся на:
1) поиск в пространстве состояний (рассмотрим подробно),
2) поиск методом редукции,
3) эвристический поиск
4) поиск методом "генерация-проверка".
3.1.1. Поиск в пространстве состояний
Задача поиска в пространстве состояний обычно формулируется в
теоретико-графовой интерпретации.
Пусть задана тройка (S0, F, SТ), где S0 - множество начальных
состояний (условия задачи), F - множество операторов задачи, отображающих
одни состояния в другие, SТ - множество конечных (целевых) состояний
(решений задачи).
Цель: определять такую последовательность операторов, которая
преобразует начальные состояния в конечные.
Процесс решения в виде графа G=(Х, Y), где X={х0, х1,...} - множество
(в общем случае бесконечное) вершин графа, состояний, а Y - множество,
содержащее пары вершин (xi, xj), (xi, xj)(X. Если каждая пара (xi, xj)
неупорядочена, то ее называют ребром, а граф - неориентированным. Если для
каждой пары (xi, xj) задан порядок (направление), то пару (xi, xj) называют
дугой (ориентированным ребром), а граф называют ориентированным
(направленным). Вершины пары (xi, xj) называют концевыми точками ребра
(дуги).
Поиск в пространстве состояний естественно представить в виде
ориентированного графа. Наличие пары (xi, xj) свидетельствует о
существовании некоторого оператора f (f(F), преобразующего состояние,
соответствующее вершине xi, в состояние xj. Для некоторой вершины xi
выделяем множество всех направленных пар (xi, xj)(Y, т.ь. множество дуг,
исходящих из вершины хi, (родительской вершины), и множество вершин
(называемых дочерними вершинами), в которые эти дуги приводят. Множество
дуг, исходящих из вершины xi, соответствует множеству операторов, которые
могут быть применены к состоянию, соответствующему вершине хi.
В множестве вершин X выделяют подмножество вершин Х0(Х,
соответствующее множеству начальных состояний (So),, и подмножество вершин
Хт(X, соответствующее множеству конечных (целевых) состояний (SТ).
Множество Хт может быть задано как явно, так и неявно, т.е. через свойства,
которыми должны обладать целевые состояния.
Отметим, что граф С может быть задан явно и неявно. Неявное задание
графа G стоит в определении множества Х0(Х (соответствующего множеству
начальных состояний) и множества операторов, которые, будучи применимы к
некоторой вершине графа, дают все ее дочерние вершины.
Итак, граф G задает пространство состояний, т.е. пространство, в
котором осуществляется поиск решения. Построение пространства
осуществляется с помощью следующего процесса. Берется некая вершина х0(Х, к
ней применяются все возможные операторы, порождающие все дочерние вершины.
Этот процесс называют процессом раскрытия вершин. Если получена целевая
вершина, то она не раскрывается. Процесс построения пространства состояний
заканчивается, когда все нераскрытые вершины являются целевыми, или
терминальными (т.е. вершинами, к которым нельзя применить никаких
операторов). В связи с тем, что пространство состояний может содержать
бесконечное количество вершин, на практике процесс порождения пространства
ограничивают либо временем, либо объемом памяти.
На практике требуется обеспечить полноту поиска, т.е. организовать
поиск так, чтобы все целевые вершины были найдены, если они существуют.
Надежным способом обеспечения полноты является полный перебор всех вершин.
Для задания процесса перебора необходимо определить. порядок, в котором
будут перебираться вершины графа. Обычно выделяют два основных способа
поиска:
поиск в глубину (сначала раскрывается та вершина, которая была построена
самой последней). Рис.3.1.а
поиск в ширину. (вершины раскрываются в том же порядке, в котором они
порождаются.) Рис.3.1.б.
Целевые вершины помечены черными квадратами, а терминальные - белыми
квадратами. При использовании каждого из способов могут быть найдены все
решения. При переборе всего пространства оба метода будут анализировать
одинаковое количество вершин, однако метод поиска в ширину будет требовать
существенно больше памяти, так как он запоминает все пути поиска (а не
один, как при поиске в глубину).
[pic]
3.1.2. Поиск методом редукции
При поиске методом редукции решение задачи сводится к решению
совокупности образующих ее подзадач. Этот процесс повторяется для каждой
подзадачи до тех пор, пока каждая из полученного набора подзадач,
образующих решение исходной задачи, не будет иметь очевидное решение.
Процесс решения задачи разбиением ее на подзадачи можно представить в виде
специального направленного графа G, называемого И/ИЛИ-графом; Каждой
вершине этого графа ставитсяв соответствие описание некоторой задачи
(подзадачи). В графе выделяют два типа вершин: конъюнктивные вершины и
дизъюнктивные вершины.
Решение задачи при поиске методом редукции (при поиске в И/ИЛИ-графе)
сводится к нахождению в И/ИЛИ-графе решающего графа.
Цель процесса поиска в И/ИЛИ-графе - показать, что начальная вершина
разрешима, т.е. для этой вершины существует решающий граф. Определение
разрешимой вершины в И/ИЛИ-графе можно сформулировать рекурсивно следующим
образом:
1. Конечные (целевые) вершины разрешимы, так как их решение известно по
исходному предположению.
1. Вершина ИЛИ разрешима тогда и только тогда, когда разрешима по крайней
мере одна из ее дочерних вершин.
1. Вершина И разрешима тола и только тогда, когда разрешима каждая из ее
дочерних вершин.
[pic]
Решающий граф определяется как подграф из разрешимых вершин, который
показывает, что начальная вершина разрешима (в соответствии с приведенным
выше определением). На рис. 3.3. разрешимые вершины зачернены, а
неразрешимые оставлены белыми.
[pic]
Для графа И/ИЛИ, так же как для поиска в пространстве состояний, можно
определить поиск в глубину и поиск в ширину как в прямом, так и в обратном
направлении. На рис. 3.4. приведен пример поиска в ширину (рис. 3.4., а) и
поиска в глубину (рис. 3.4., б). На рисунке вершины пронумерованы в том
порядке, в котором они раскрывались, конечные вершины обозначены
квадратами, разрешимые вершины зачернены, дуги решающего графа выделены
двойными линиями.
[pic]
3.1.3. Эвристический поиск
При увеличении пространства поиска методы слепого поиска требуют
чрезмерных затрат времени и (или) памяти. Это привело к созданию
эвристических методов поиска, т.е. методов, использующих некоторую
информацию о предметной области для рассмотрения не всего пространства
поиска, а таких путей в нем, которые с наибольшей вероятностью приводят .к
цели. '
3.1.4.Поиск методом "генерация-проверка"
Процесс поиска может быть сформулирован в терминах "генерация-проверка".
Для осуществления процесса поиска необходимо генерировать очередное
возможное решение (состояние или подзадачу) и проверить, не является ли оно
результирующим.
3.2. ПОИСК В ИЕРАРХИИ ПРОСТРАНСТВ
Методы поиска в одном пространстве не позволяют решать сложные задачи,
так как с увеличением размера пространства время поиска экспоненциально
растет. При большом размере пространства поиска можно попробовать разбить
общее пространство на подпространства и осуществлять поиск сначала в них.
Пространство поиска представлено иерархией пространств.
Методы поиска решения в иерархических пространствах обычно делятся на:
1) поиск в факторизованном пространстве,
2) поиск в фиксированном множестве пространств
3) поиск в изменяющемся множестве пространств.
3.2.1. Поиск в факторизованном пространстве
Во многих приложениях требуется найти все решения. Например -
постановка диагноза. Пространство называется факторизованным, если оно
разбивается на непересекающиеся подпространства (классы) частичными
(неполными) решениями. Причем по виду частичного решения можно определить,
что оно не приведет к успеху, т.е. что все полные решения, образованные из
него, не приведут к целевым решениям. Поиск в факторизованном пространстве
осуществляется на основе метола "иерархическая генерация-проверка". Если
пространство поиска удается факторизовать, то поиск даже в очень большом
пространстве можно организовать эффективно.
3.2.2. Поиск в фиксированном множестве пространств
Применение метода факторизации пространства ограничено тем, что для
ряда областей не удается по частичному решению сделать заключение о его
непригодности. Например задачи планирования и конструирования. В этих
случаях могут быть применены методы поиска, использующие идею абстрактного
пространства. Абстракция должна подчеркнуть важные особенности
рассматриваемой задачи, позволить разбить задачу на более простые подзадачи
и определить последовательность подзадач (план решения), приводящую к
решению основной задачи.
3.2.3. Поиск в изменяющемся множестве иерархических пространств
В ряде приложений не удается все решаемые задачи свести к
фиксированному набору подзадач. План решения задачи в данном случае должен
иметь переменную структуру и не может быть сведен к фиксированному набору
подзадач. Для решения подобных задач может быть использован метод
нисходящего уточнения. Этот метод базируется на следующих предположениях:
возможно осуществить частичное упорядочение понятий области, приемлемое для
всех решаемых задач;
решения, принимаемые на верхних уровнях, нет необходимости отменять на
более нижних.
3.3. ПОИСК В АЛЬТЕРНАТИВНЫХ ПРОСТРАНСТВАХ
Рассмотренные выше методы поиска исходят из молчаливой предпосылки,
что знания о предметной области и данные о решаемой задаче являются точными
и полными и для них справедливо следующее:
все утверждения, описывающие состояние, являются истинными;
применение оператора к некоторому состоянию формирует некоторое новое
состояние, описание которого состоит только из истинных фактов.
Однако при решении любых практических задач и особенно при решении
неформализованных задач распространена обратная ситуация. Эксперту
приходится работать в условиях неполноты и неточности знаний (данных) и,
как правило, в условиях дефицита времени. Когда эксперт решает задачу, он
использует методы, отличающиеся от формальных математических рассуждений. В
этом случае эксперт делает правдоподобные предположения, которые он не
может доказать; тем самым вопрос об их истинности остается открытым. Все
утверждения, полученные на основе этих правдоподобных предположений, также
не могут быть доказаны.
Итак, для того чтобы система могла делать умозаключения, основанные на
здравом смысле, при работе с неполными (неточными) данными и знаниями, она
должна быть способна делать предположения, а при получении новой
информации, показывающей ошибочность предположений, отказываться как от
сделанных предположений, так и от умозаключений, полученных на основе этих
предположений. Мнение системы о том, какие факты имеют место, изменяется в
ходе рассуждения, т.е. можно говорить о ревизии мнений. Таким образом, даже
если рассматривать проблемную область как статическую, неполнота (и
неточность) знаний и данных влечет за собой рассмотрение этой области при
различных (и даже противоположных) предположениях, что, в свою очередь,
приводит к представлению области в виде альтернативных пространств,
соответствующих различным, возможно, противоречивым и (или)
взаимодополняющим предположениям и мнениям.
Все неудачи, возникшие при поиске в одном направлении, не запоминаются
при переходе к поиску в другом направлении. Та же самая причина неудачи
может заново обнаруживаться и на новом направлении.
Осуществлять возврат целесообразно не к состоянию, непосредственно
предшествующему данному, а к тому состоянию, которое является причиной
возникновения неудачи. В используемых нами терминах причиной неудач
являются предположения, т.е. недоказуемые утверждения. Поэтому при
обнаружении неудачи необходимо возвращаться в состояние, где это
предположение было сделано, и испытывать другое предположение.
Этот метод поиска называют поиском, направляемым зависимостью.
3.4. ПОИСК С ИСПОЛЬЗОВАНИЕМ НЕСКОЛЬКИХ МОДЕЛЕЙ
Все методы поиска, рассмотренные до сих пор, использовали при
представлении проблемной области какую-то одну модель, т.е. рассматривали
область с какой-то одной точки зрения. При решении сложных задач в условиях
ограниченных ресурсов использование нескольких моделей может значительно
повысить мощность системы. Объединение в одной системе нескольких моделей
дает возможность преодолеть следующие трудности.
переход с одной модели на другую позволяет обходить тупики, возникающие при
поиске в процессе распространения ограничений.
использование нескольких моделей позволяет в ряде случаев уменьшить
вероятность потери хорошего решения (следствие неполного поиска, вызванного
ограниченностью ресурсов) за счет конструирования полного решения из
ограниченного числа частичных кандидатов путем их расширения и комбинации.
наличие нескольких моделей позволяет системе справляться с неточностью
(ошибочностью) данных.
Следует отметить, что использование нескольких моделей требует
дополнительных знаний о том, как создавать и объединять различные точки
зрения.
3.5. ВЫБОР МЕТОДА РЕШЕНИЯ ЗАДАЧ
Выбор метода решения задачи зависит прежде всего от сложности задачи,
которая определяется особенностями проблемной области и требованиями,
предъявляемыми пользователем к решению задачи. Для преодоления трудностей,
вызванных большим пространством поиска, используются методы, основанные на
введении иерархии пространств (конкретных, абстрактных и метапространств).
Простейший из этих методов основывается на факторизуемости пространства
решений, что позволяет производить раннее отсечение. Метод обеспечивает
получение всех решений. Если пространство поиска не удается факторизовать,
но при этом не требуется получать все решения или выбирать лучшее, то могут
быть применены методы, использующие иерархию однородных абстрактных
пространств. Если пространство поиска таково, что любая задача может быть
сведена к известной
заранее последовательности подзадач, то используется фиксированное
абстрактное пространство.
Эффективность этого метода определяется возможностью использовать
безвозвратную стратегию. В случае, если подзадачи взаимозависимы, т.е. для
решения некоторой подзадачи может требоваться информация, получаемая другой
подзадачей, и подзадачи не могут быть упорядочены, целесообразно применять
принцип наименьших свершений. Этот подход позволяет приостанавливать
решение подзадачи, для которой недостает информации, переходить к решению
другой подзадачи и возвращаться к исходной задаче, когда отсутствующая
информация станет доступной. (поиск в иерархии пространстве)
Для преодоления трудностей, вызванных неполнотой и (или) неточностью
данных (знаний), используют вероятностные, размытые и точные методы. Все
эти методы основываются на идее увеличения надежности путем комбинирования
фактов и использования метазнаний о возможностях комбинирования фактов.
Для преодоления неадекватности модели проблемной области используются
методы, ориентированные на использование нескольких моделей. Эти методы
позволяют объединить возможности различных моделей, описывающих проблемную
область с различных точек зрения. Кроме того, использование нескольких
моделей позволяет уменьшить вероятность потери хорошего решения, несмотря
на неполноту поиска, вызванную ограниченностью вычислительных ресурсов.
-----------------------
Рис.3.1.
Рис.3.2.
Рис.3.3.
Рис.3.4.
Реферат на тему: Методы приобретения знаний в интеллектуальных системах
Введение.
Инженерия знаний – это область информационной технологий, цель которой
– накапливать и применять знания, не как объект обработки их человеком, но
как объект для обработки их на компьютере. Для этого необходимо
проанализировать знания и особенности их обработки человеком и
компьютером, а также разработать их машинное представление. К сожалению
точного и неоспоримого определения, что собой представляют знания, до сих
пор не дано. Но тем не менее цель инженерии знаний – обеспечить
использование знаний в компьютерных системах на более высоком уровне, чем
до сих пор – актуальна. Но следует заметить, что возможность использования
знаний осуществима только тогда, когда эти знания существуют, что вполне
объяснимо. Технология накопления и суммирования знаний идет бок о бок с
технологией использования знаний, они взаимно дополняют друг друга и ведут
к созданию одной технологии, технологии обработки знаний.
В данной работе я постарался описать методы решения одной из проблем
данного комплекса – это проблемы приобретения знаний, или говоря другими
словами – обучения.
Методы приобретения знаний.
Приобретение знаний реализуется с помощью двух функций: получения
информации извне и ее систематизации. При этом в зависимости от способности
системы обучения к логическим выводам возможны различные формы приобретения
знаний, а также различные формы получаемой информации. Форма представления
знаний для их использования определяется внутри системы, поэтому форма
информации, которую она может принимать, зависит от того, какие способности
имеет система для формализации информации до уровня знаний. Если
обучающаяся система совсем лишена такой способности, то человек должен
заранее подготовить все, вплоть до формализации информации, т. е. чем выше
способности машины к логическим выводам, тем меньше нагрузка на человека.
Функции, необходимые обучающейся системе для приобретения знаний,
различаются в зависимости от конфигурации системы. В дальнейшем при
рассмотрении систем инженерии знаний предполагается, что Существует система
с конфигурацией, показанной на рис, 1.1, которая включает базу знаний и
механизм логических выводов, использующий эти знания при решении задач.
Если база знаний пополняется знаниями о стандартной форме их представления,
то этими знаниями также можно воспользоваться. Следовательно, от функций
обучения требуется преобразование полученной извне информации в знания и
пополнение ими базы знаний.
Рис.1 Базовая структура систем обработки знаний
Можно предложить следующую классификацию систем приобретения знаний,
которая будет опираться на способность системы к восприятию знаний в разных
форматах, качественно различающихся между собой и способностью к
формализации (рис 2).
Рис 2.Классификация методов приобретения знаний.
Обучение без выводов.
Категорию А можно назвать обучением без выводов или механическим
запоминанием, это простой процесс получения информации, при котором
необязательны функции выводов, а полученная информация в виде программ или
данных используется для решения задач в неизменном виде. Другими словами,
это способ получения информации, характерный для существующих компьютеров.
Категория Б—это получение информации извне, представленной в форме знаний,
т. е. В форме, которую можно использовать для выводов. Обучающейся Системе
необходимо иметь функцию преобразования входной информации в формат,
удобный для дальнейшего использования и включения в базу знании.
Приобретение знаний на этом этапе происходит в наиболее простой форме: это
знания, предварительно подготовленные человеком во внутреннем формате,
какими являются большинство специальных знании, изначально заданных в
экспертных системах. В случае прикладных систем инженерии знаний необходимо
преобразовать специальные знания из какой-либо области в машинный формат,
но для этого нужен посредник, хорошо знающий как проблемную область, так и
инженерию знаний. Таких посредников называют инженерами по знаниям. В общем
случае для замены функции посредника можно использовать и специальные
подпрограммы. Т.е. необходимо иметь функции выводов достаточно высокого
уровня, но можно ограничиться и выводами на сравнительно низком уровне, а
остальное доверить человеку — в этом и состоит приобретение знаний в
диалоге. Примером служит хорошо известная система TEIRESIAS. Это система-
консультант в области медицины, разработанная на базе системы MYCIN.
Специалисты в проблемной области являются преподавателями обучающейся
системы, а ученик — система инженерии знаний — изучает ответы на
поставленные задачи и корректирует те правила в базе знаний, которые ранее
приводили к ошибкам. Для подготовки знаний в экспертной системе необходимы
вспомогательные средства типа редактора знаний, причем в процессе
приобретения знаний в диалоге не только редактируются отдельные правила и
факты, но и восполняются недостатки существующих правил, т. е. ведется
редактирование базы знаний.
Если знания заданы во внешнем формате, например на естественном языке, то
следует преобразовать их во внутренний формат. Для этого необходимо
понимать внешнее представление, т. е. естественный язык, графические данные
и т. п. Фактически приобретение знаний и их понимание тесно связаны.
Проблема понимания сводится не только к преобразованию структуры
предложений — необходимо получить формат, удобный для применения.
Аналогичная проблема — преобразование во внутренний формат советов,
подсказок по решению задач, что называется «операционализацией» знаний В
этом заключается центральная проблема искусственного интеллекта; она, в
частности, изучает преобразование советов, подсказок, представленных в
терминах проблемной области, в процедуры. Например, система UNDERSTAND
выполняет операционализацию представления задачи о ханойской башне на
английском языке путем построения соответствующих состояний и операций,
приводящих к этим состоя* киям.
Приобретение знаний на метауровне
Выше было рассмотрено обучение на объектном уровне, а еще более сложная
проблема - приобретение знаний на метауровне, т. е. знаний, основой которых
является информация по управлению решением задач с использованием знаний на
объектном уровне. Для знаний на метауровне пока не установлены ни формы
представления и использования, ни связь со знаниями на объектном уровне, ни
другая техника их систематизации. Поскольку не определена форма их
представления с точки зрения использования, то трудно говорить о
приобретении знаний на метауровне. Тем не менее с этой проблемой связаны
многие надежды в инженерии знаний,
Приобретение знаний из примеров
Метод приобретение знаний из примеров отличается от предыдущего метода,
тем , что здесь выполняется сбор отдельных фактов, их преобразование и
обобщение, а только затем они будут использованы в качестве знаний. И
соответственно от уровня сложности системы вывода в системе будут возникать
разные по степени общности и сложности знания. Необходимо также упомянуть
о том, что этот метод приобретения знаний почти не нашёл практического
применения, это может быть связано с тем, что входная информация
представляет собой не систематизированный набор данных и для их обработки
требуется наличие в системе обширных знаний по конкретной области.
По сравнению с предыдущим методом приобретения знаний, этот метод имеет
большую степень свободы и соответственно необходимо описать общие положения
этого принципа.
1. Языки представления. Обучение по примерам — это процесс сбора отдельных
фактов, их обобщение и систематизация, поэтому необходим унифицированный
язык представления примеров и общих правил. Эти правила, будучи результатом
обучения, должны стать объектами для использования знаний, поэтому и
образуют язык представления знаний. И наоборот, язык представления знаний
должен учитывать и определять указанные выше условия приобретения знаний.
2. Способы описания объектов. В случае обучения .по примерам из описаний
отдельных объектов создаются еще более общие описания объектов некоторого
класса, при этом возникает важная проблема: как описать данный класс
объектов. В полном классе некоторых объектов следует определить меньший
класс объектов, обладающих общим свойством (объекты только в этом классе
обладают заданным свойством), но в действительности проще определить список
объектов и убедиться, что все объекты в нем обладают общим свойством. Для
некоторого типа задач можно эффективно использовать ложные примеры или
контрпримеры, убедительно показывающие, что данные объекты не входят в этот
класс.. Иллюстрацией применения контрпримеров может служить понятие «почти
то».
3. Правила обобщения. Для сбора отдельных примеров и создания общих правил
необходимы правила обобщения. Предложено несколько способов их описания:
замена постоянных атрибутов языка на переменные, исключение описаний с
ограниченным применением и т. п. Очевидно, что эти способы тесно связаны с
языком представления знаний.
4. Управление обучением. В процессе обучения по примерам можно применять
различные стратегии структуризации информации и необходимо управлять этим
процессом в ответ на входные данные. Существуют два классических метода:
метод «снизу-вверх», при .котором, последовательно выбираются и
структурируются отдельные сообщения, и метод «сверху-вниз», при котором
сначала выдвигается гипотеза, а затем она корректируется по мере
поступления информации. На практике эти методы комбинируются, хотя
управление обучением с максимальным эффектом не такая уж простая проблема.
При изучении метода приобретения знаний по примерам можно выделить
следующий ряд методов:
Параметрическое обучение
Обучение по аналогии
Обучение по индукции.
Параметрическое обучение.
Наиболее простая форма обучения по примерам или наблюдениям состоит в
определении общего вида правила, которое должно стать результатом вывода, и
последующей корректировки входящих в это правило параметров в зависимости
от данных. При этом используют психологические модели обучения, системы
управления обучением и другие методы.
Примером обучающейся системы этой категории в области искусственного
интеллекта является система Meta-Dentral. Эта система выводит новые правила
путем коррекции правил продукций в процессе обучения или на основе исходных
массспектральных данных параметрическое обучение в ней представлено в
несколько специфичном виде, но все же она относятся к указанной выше
категории, поскольку в системе задана основная структура знаний, которая
корректируется последовательно по отдельным данным.
Ярким примером применения этого метода приобретения знаний могут также
служить системы распознавания образов (обсуждавшиеся ранее в другом
докладе). В них ясно просматривается основной принцип этого метода - в ходе
обучения нейронная сеть автоматически по определенным заранее законам
корректирует веса связей между элементами и значения самих элементов.
Метод обучения по индукции.
Среди всех форм обучения необходимо особо выделить обучение на основе
выводов по индукции - это обучение с использованием выводов высокого
уровня, как и при обучении по аналогии. В процессе этого обучения путем
обобщения совокупности имеющихся данных выводятся общие правила. Возможно
обучение с преподавателем, когда входные данные задает человек, наблюдающий
за состоянием обучающейся системы, и обучение без преподавателя, когда
данные поступают в систему случайно. И в том и в другом случае выводы могут
быть различными, они имеют и различную степень сложности в зависимости от
того, задаются ли только корректные данные или в том числе и некорректные
данные и т. п. Так или иначе, обучение этой категории включает открытие
новых правил, построение теорий, создание структур и другие действия,
причем модель теории или структуры, которые следует создать, заранее не
задаются, поэтому их необходимо разработать так, чтобы можно было объяснить
все правильные данные и контрпримеры.
Индуктивные выводы возможны в случае, когда представление результата вывода
частично определяется из представления входной информации. В последнее
время обращают на себя внимание программы генерации программ по образцу с
использованием индуктивных выводов.
Как уже было сказано, индуктивный вывод — это вывод из заданных данных
объясняющего их общего правила. Например, пусть известно, что есть
некоторый многочлен от одной переменной. Давайте посмотрим, как выводится
f(х), если последовательно задаются в качестве данных пары значений (0,
f(0)), (1, f(1)), .... Вначале задается (0, 1), и естественно, что есть
смысл вывести постоянную функцию f(х)=1. Затем задается (1, 1), эта пара
удовлетворяет предложенной функции f{х)= 1. Следовательно в этот момент нет
необходимости менять вывод. Наконец, задается (2, 3), что плохо согласуется
с нашим выводом, поэтому откажемся от пего и после нескольких проб и ошибок
выведем новую функцию f(х)==х2—х+1, которая удовлетворяет всем заданным до
сих пор фактам (0, 1), (1, 1), (2,3). Далее мы убедимся, что эта же функция
удовлетворяет фактам (3, 7), (4, 13), (5, 21) ..., поэтому нет
необходимости менять этот вывод. Таким образом, из последовательности пар
переменная-функция можно вывести многочлен второй степени. Грубо говоря,
такой метод вывода можно назвать индуктивным.
Как видно из этого примера, при выводе в каждый момент времени объясняются
все данные, полученные до этого момента. Разумеется, данные, полученные
позже, уже могут и не удовлетворять этому выводу. В таких случаях
приходится менять вывод. Следовательно, в общем случае индуктивный
вывод—это неограниченно долгий процесс. И это не удивительно, если
вспомнить процесс освоения человеком языков, процесс совершенствования
программного обеспечения и т. п.
Для точного определения индуктивного вывода необходимо уточнить:
множество правил—объектов вывода,
метод представления правил,
способ показа примеров,
метод вывода и
критерий правильности вывода.
В качестве правил—объектов вывода—можно рассматривать главным образом
индуктивные функции, формальные языки, программы и т. п. Кроме того, эти
правила могут быть представлены в виде машины Тьюринга для вычисления
функций, грамматики языков, операторов Пролога и другим способом. Машина
Тьюринга—это математическая модель компьютера, ее в принципе можно считать
программой. В случае когда объектом вывода является формальный язык, он сам
определяет правила, а его грамматика — метод представления правил, поэтому
говорят о грамматическом выводе.
Для показа примеров функции f можно использовать последовательность пар
(х,f(х)) входных и выходных значений так, как указано выше,
последовательность действий машины Тьюринга, вычисляющей и другие данные.
Задание машине выводов пары входных и выходных значений (х, f(х)) функции f
соответствует заданию системе автоматического синтеза программ входных
значений х и выходных значений f(х), которые должны быть получены
программой вычисления f в ответ на х. В этом смысле автоматический синтез
программ по примерам также можно считать индуктивным выводом функции f.
Формальные языки — это множество слов; поэтому, например, для языка L можно
рассматривать ва типа слов, принадлежащих и не принадлежащих этому языку.
Первые назовем положительными, а вторые — отрицательными данными. Другими
словами, есть два способа показа примеров формального языка: с помощью
положительных и отрицательных данных. Когда объектом служат сами программы,
тогда то же самое можно говорить о функциях языка Лисп, но для Пролога
показ примеров осуществляется в виде фактов. Например, (3>4, истина),
(2 предположение -> выходные данные.
Другими словами, при выводе последовательно получают примеры как входные
данные, вычисляют предположение па данный момент и выдают результат
вычислений. Предположение в каждый момент времени основано на ограниченном
числе примеров, полученных до сих пор, поэтому обычно в качестве метода
вывода используют машину Тьюринга, вычисляющую предположение по
ограниченному числу примеров. Такую машину назовем машиной выводов.
Учитывая, что индуктивный вывод, как уже было отмечено, это неограниченно
продолжающийся процесс, критерием правильности вывода, как правило, считают
понятие идентификации в пределе. Это понятие введено Голдом, оно
используется почти всегда в теории индуктивных выводов. Говорят, что машина
вывода М идентифицирует в пределе правило R, если при показе примеров К
последовательность выходных данных, генерируемых М, сходится к некоторому
представлению т, а именно: все выходные данные, начиная с некоторого
момента времени, совпадают с т, при этом т называют правильным
представлением К.. Кроме того, говорят, что множество правил Г позволяет
сделать индуктивный вывод, если существует некоторая машина выводов М,
которая идентифицирует в пределе любое правило К из множества Г. Обратите
внимание на то, что слова «позволяет сделать индуктивный вывод» не имеют
смысла для единственного правила, а относятся только к множеству правил.
Обучение по аналогии.
Приобретение новых понятий возможно путем преобразования существующих
знаний, похожих на те, которые собираются получить. Это важная функция,
которую называют обучением на основе выводов по аналогии или просто
обучением по аналогии. В нашей жизни много примеров, когда новые понятия
или технические приемы приобретаются с помощью аналогии
Выводы по аналогии - один из важных объектов исследования искусственного
интеллекта, наиболее интересные результаты здесь получены П. Уинстоном. Он
использует выводы по аналогии, основываясь на следующей гипотезе: «Если две
ситуации подобны по нескольким признакам, то они подобны и еще По одному
признаку». Подобие двух ситуаций распознается путем обнаружения наилучших
совпадений по наиболее важным признакам.
Аналогия—это метод выводов, при которых обнаруживается подобие между
несколькими заданными объектами; благодаря переносу фактов и знаний,
справедливых для одних объектов, на основе этого подобия на совсем другие
объекты либо определяется. способ решения задач, либо предсказываются
неизвестные факты и знания. Следовательно, когда человек сталкивается с
неизвестной задачей, он на первых порах использует этот естественный метод
вывода.
Направления исследования аналогии
Одна из важнейших проблем инженерии знаний— приобретение знаний. Под
приобретением здесь понимается получение знаний в виде, пригодном для их
использования компьютерами, поэтому многие исследователи указывают, что
ключом к знаниям является теория и методология машинного обучения. В общем
случае машинное обучение включает приобретение новых декларативных знаний,
систематизацию и хранение новых знаний, а также обнаружение новых фактов.
Среди указанных форм обучения аналогия, о которой будет идти далее речь,
связана, и частности, с проблемой машинного обнаружения новых фактов.
Под новыми фактами мы будем понимать факты, которые дедуктивно не
выводятся из некоторых существующих знаний. Получение новых знаний также
рассматривалось выше в отношении к индуктивному выводу . В общем случае при
индуктивных выводах по заданным данным создается гипотеза, их объясняющая,
а с помощью дедукции из этой гипотезы можно вывести новые факты. С другой
стороны, при аналогии новые факты предсказываются путем использования
некоторых преобразований уже известных знаний.
Индукция и аналогия крайне необходимы при обработке интеллектуальной
информации, и поэтому желательно изложить основы их совместного применения.
Шапиро ввел строгую формализацию индуктивных выводов в части вывода моделей
с использованием логики предикатов первого порядка; в теории индуктивных
выводов есть заметные успехи.
С целью обзора исследований аналогии, проведенных до настоящего времени,
выделим два типа аналогии: для решения задач и для предсказаний. Аналогия
первого типа применяется главным образом для повышения эффективности
решения задач, которые, вообще говоря, можно решить и без аналогии.
Например, благодаря использованию решений аналогичных задач в областях
программирования и доказательства теорем можно прийти к выводам о
программах или доказательствах. С другой стороны, используя аналогию для
предсказаний, благодаря преобразованию знаний на основе подобия между
объектами можно сделать заключение о том, что, возможно, справедливы новые
факты. Например, если объектами аналогии является некая система аксиом, то
знаниями могут быть теоремы, справедливые в этой системе. При этом,
используя схожесть между системами аксиом, можно преобразовать теорему в
одной из систем в логическую формулу для другой системы и сделать вывод о
том, что эта формула есть теорема. Другими словами, аналогия используется и
для решения некоторых строго сформулированных задач и для предсказаний, а
также для приобретения не заданной ранее информации.
Примером использования метода приобретений знаний по аналогии может служить
система доказательства теорем. При этом общая схема вывода выглядит
следующим образом.
Рис. 3 Стратегия абстрагирования.
-----------------------
Человек
Механизмы выводов обучающей системы
Механизмы выводов пользовательской системы
База знаний
Методы приобретения знаний
Обучение на примерах
Обучение на метауровне
Обучение без выводов
Получение данных представленных в виде знаний (Категория Б)
Простое запоминание данных (Категория А)
Получение знаний, представленных во внешнем формате и их понимание
Получение знаний, представленных во внутреннем формате в режиме диалога
Получение готового набора знаний, представленных во внутреннем формате
Задача
(доказать T)
Абстрактная задача
(доказать T`)
Решение P
Абстрактное решение P`
Абстрагирование
Традиционное решение задачи
| |
