Ответы в виде шпор 1-15 (Стратегии эвристического решения задач)

1. Стратегии эвристического решения задач: поиск в пространстве состояний, особенности поиска в глубину и в ширину.
пространство состояний: Вершины графа соответствуют проблемным ситуациям, дуги — разрешенным переходам из одних ситуаций в другие. Задача отыскания плана решения эквивалентна задаче построения пути между стартовой вершиной (начальной ситуацией) и некоторой указанной конечной вершиной (целевой ситуацией). Задача поиска в пространстве состояний — определить последовательность ходов из стартовой вершины, которая приводит к попаданию в целевую вершину.
Кроме того, каждому разрешенному ходу можно приписать его стоимость, и в этом случае необходимо будет найти решение минимальной стоимости. Существует две основных стратегии поиска решения в пространстве состояний: поиск в глубину(время) и поиск в ширину(память). Отметим сначала, что поиск обоими способами можно проводить как от стартовой вершины (поиск на основе данных), так и от целевой вершины. Поиск от цели рекомендован в следующих случаях.
1. Цель поиска задана в явном виде
2. Граф пространства состояний ветвится преимущественно в направлении к цели (рис. 1.3) (пример: при доказательстве теоремы их системы аксиом можно вывести гораздо больше теорем, чем количество самих аксиом). Поиск от данных рекомендован в следующих случаях.
1. Граф пространства состояний ветвится преимущественно в направлении от цели, т. е. существует мало способов обобщения данных.
2. Трудно заранее сформулировать цель решения задачи
2. Стратегии эвристического решения задач: И/ИЛИ-графы, игры, эвристические оценки в играх.
Листьями и/или графа (дерева) являются тривиальные задачи. Решением задачи является не путь, как в случае пространства состояний, а решающее дерево, которое определяется следующим образом.
1. Исходная задача Р является корнем дерева Т.
2. Если вершина Р является ИЛИ - вершиной, то в Т содержится только один из ее приемников вместе со своим решающим деревом.
3. Если Р является И - вершиной, то все ее приемники вместе со своими
решающими деревьями содержатся в Т.
Дугам или вершинам можно приписать стоимости и поставить задачу нахождения оптимального решения. Методы поиска решения здесь те же, что для пространства состояний.
Позиционные игры можно также рассматривать как частный случай И / ИЛИ графов: из некоторой начальной позиции необходимо найти такой ход, чтобы на любой ход противника можно было найти выигрышную стратегию своих дальнейших действий. Формализация задачи такова: позиция игрока, т. е. ситуация, в которой право хода принадлежит игроку — это ИЛИ - вершина, позиция противника, т. е. ситуация, в которой право хода принадлежит противнику — это И - вершина.
Решающее дерево, представляющее собой решение позиционной игры, имеет следующую интерпретацию. Дуга, соединяющая ИЛИ - вершину с И - вершиной следующего уровня, определяет ход игрока, который следует выбрать в соответствующей игровой ситуации. Дуги, соединяющие И - вершину с ИЛИ - вершинами следующего уровня, определяют все ходы, которые может выбрать противник в соответствующей игровой ситуации. В решающем дереве все вершины последнего уровня, входящие в него, должны соответствовать позициям, приносящим выигрыш игроку. Если такое дерево существует, то для любой игровой ситуации, возникающей в ходе игры, оно задает «правильный» ход игрока, приводящий к выигрышу при любой реакции противника
Эвристики:
Альфа - бета процедура (в лекциях это минимаксная процедура). Для получения оценки корневой вершины не обязательно вычислять оценки для всех вершин дерева. Один из участников игры стремится к максимальным оценкам (игрок), а другой к минимальным (противник). Каждой вершине ставится в соответствие две оценки (альфа - бета интервал):
– минимальное гарантированное значение, которое сможет получить первый игрок при любом варианте дальнейшего развития игры;
– максимальное значение, которое первый игрок не сможет превзойти при любом варианте дальнейшего развития игры.
Если альфа - бета интервал для поддерева X лежит целиком ниже интервала для другого поддерева Y, то в поддерево X можно дальше не углубляться (не рассматривать варианты, заканчивающиеся в нем).
Деление на спокойные и активные позиции. В спокойных позициях производится оценка вариантов (на некоторую глубину), а в активных позициях варианты просматриваются вглубь до достижения вершин спокойных позиций.
Сортировка позиций в порядке их перспективности при помощи некоторой быстрой процедуры (например, просмотр вариантов развития игры на небольшую глубину), а затем просмотр поддеревьев в порядке убывания перспективности.
Последовательный просмотр на один, на два, на три уровня вглубь и т. д. Предполагается, что чем глубже просмотр, тем более точные оценки перспективности достигнутых поддеревьев могут быть получены. Когда время, отведенное на обдумывание хода, истекает, выбирается наиболее перспективное продолжение в соответствии с оценками, полученными на достигнутой к этому моменту глубине просмотра.
Библиотека типовых ситуаций

3. Стратегии эвристического решения задач: программирование с помощью образцов, мультиагентные системы.
Программирование с помощью образцов — это способ определения порядка запуска нескольких программных модулей, которые содержат независимые блоки программного кода. Модули запускаются при возникновении в информационной среде заданных конфигураций (т. е. порядок недетерминирован и определяется состоянием данных). Каждый модуль определяется:
1) образцом, который задает условие запуска;
2) действиями, которые необходимо выполнить, если информационная среда
согласуется с образцом.
Алгоритм работы системы.
1. Сопоставление состояния информационной среды с образцами. Результат — конфликтное множество, т. е. совокупность всех потенциально активных модулей.
2. Разрешение конфликтов — выбор одного из модулей, входящих в конфликтное множество (возможны стохастические, эвристические правила выбора и т. д.)
3. Выполнение действий выбранного модуля.
4. Переход к шагу 1.
Отдельный модуль включает: контекст, предусловие, образец, алгоритм, постусловие.
Мультиагентная система состоит из нескольких однотипных независимых решателей (агентов), способных планировать собственные действия и взаимодействовать с другими агентами для решения общей задачи. Принципиальное отличие мультиагентных систем от эволюционных — все агенты решают общую задачу, каждый из них в отдельности заведомо не способен ее решить. Основные свойства, которыми должны обладать агенты.
1. Ситуативность — агент воспринимает окружение, в котором действует, и может его изменять. Каждому агенту известно состояние задачи и действия других агентов, но неизвестны их планы и способы, которыми они решают свои задачи. (пример: виртуальный футбол — игроки команды видят друг друга, но не могут обмениваться информацией о своих планах действия).
2. Автономность — агент может взаимодействовать с задачей без вмешательства других агентов. При этом агенты могут обучаться на своем опыте (в режиме обучения с подкреплением, либо самообучения).
3. Социальность — агент должен включать в свой план действий взаимодействие с другими агентами (обращение к ним с запросами на решение некоторых подзадач).
4. Отличия знаний от данных, представление знаний продукционными правилами.
свойства знаний, которые отличают их от данных
1. Внутренняя интерпретируемость — информация имеет значимые для пользователя метки или идентификаторы, которые хранятся вместе со своим значением.
2. Структурированность — информация объединена в объекты и представляет какие - либо свойства этих объектов, одни объекты иерархически вложены в другие.
3. Связность — между объектами есть связи (горизонтальные и вертикальные). Горизонтальные — отношения между объектами, вертикальные — связи типа «класс»-»экземпляр»
4. Активность — из одних знаний могут быть выведены другие. Т. е. знания включают в себя не только факты, но и процедуры манипулирования ими, а также информацию о том, когда и как следует применять эти процедуры.
5. Наличие семантической метрики — знания могут быть упорядочены с помощью некоторых шкал (абсолютных, относительных или размытых).
6. Нечеткость — знания описываются с помощью квалификаторов типа
«много», «мало», «светлый», «высокий» и меняют смысл в зависимости от ситуации.
— это самый простой и самый распространенный способ представления знаний. Знания представляются совокупностью правил, каждое из которых, по сути, является программой, состоящей из одного оператора: ЕСЛИ условие ТО действие
В состав продукционной системы, т. е. системы, использующей представление знаний в виде продукционных правил (рис. 2.1), входят:
1) база знаний — совокупность знаний, представленных продукционными правилами;
2) база данных, которая отражает текущее состояние системы и содержит вводимые данные.
3) интерпретатор (машина вывода), определяющая, какое из правил продукции необходимо применить следующим.
Основные достоинства продукционных правил как способа представления знаний таковы.
1. Представление знаний с помощью продукционных правил достаточно просто. Это позволяет легко привлекать эксперта - специалиста в соответствующей прикладной области для заполнения базы знаний.
2. Выводы, получаемые на основе формализма «ЕСЛИ ТО» легко интерпретируемы.
3. Ярко выраженная модульность правил позволяет вводить новые и изменять уже введенные правила, не вдаваясь в смысл других введенных правил. Главный недостаток продукционных систем, состоит в том, что реальные
знания часто непредставимы формализмом «Если … то».

5. Представление знаний: семантические сети.
узлы этой сети выражают понятия, а дуги описывают их отношения. Если необходимо связать несколько понятий общей связью, то вводится новая сущность
В иерархической структуре понятий существует два вида типовых отношений:
– IS_A — является — отношение между понятием - классом и понятием -экземпляром этого понятия;
– PART_OF — входит в состав как часть.
Можно выделить следующие типовые виды отношений:
1. Ролевые отношения
• Отношение между событием и инициатором.
• Отношение между событием и объектом, к которому оно относится
• Отношение между событиями
2. Атрибутивные
Между объектом и его свойством.
3. Квантифицированные
(выражающиеся кванторами )
4. Теоретико-множественные
• Между классом и экземпляром класса.
• Между множеством и его экземпляром.
Атрибуты класса часто делят на атрибуты - определения и атрибуты - свойства
– атрибут - определение — понятие - экземпляр наследует атрибут понятия - класса;
– атрибут - свойство — отражает отношение между понятиями - классами и
не наследуются понятием – экземпляром
Особенность семантической сети заключается в том, что невозможно разделить базу знаний и механизм вывода
Достоинства семантических сетей как способа представления знаний таковы.
1. Наглядность представления знаний. Так же, как и в случае с продукционными правилами, формированием базы знаний может заниматься непосредственно эксперт - специалист в предметной области задачи.
2. Возможность независимого наращивания отдельных частей сети при добавлении новых знаний.
С другой стороны, указанные позитивные свойства сопровождаются следующими ограничениями по применимости семантических сетей.
1. Для семантической сети не найдено формальных алгоритмов вывода, которые решали бы задачу поиска ответа на запрос для произвольной конфигурации сети.
2. Опыт показывает, что в семантической сети достаточно сложно находить и устранять противоречия (универсальных формальных методов для этого нет, а с ростом объема сети сложность поиска противоречий «вручную» растет очень быстро).


6. Представление знаний: фреймовые системы.
фрейм — это шаблон структур данных, с помощью которых можно создать описание конкретной ситуации. Фрейм также дополняют информацией, которая касается: способов его применения, последствий его применения, способа оценки результатов его применения
Фреймовая система — это совокупность нескольких фреймов и отношений между ними. Функционирование фреймовой системы заключается в поиске фрейма, соответствующего решению задачи. Текущее состояние фреймовой системы задается текущим фреймом, анализируемым на соответствие решению задачи.
Отдельный фрейм — представляется как список, состоящий из нескольких элементов — слотов. Слоты задают атрибуты фрейма и его отношения с другими фреймами. В каждом слоте задается условие, которое должно выполниться при установлении соответствия между значениями
Основные функции фреймов.
1. Базовый тип. Наиболее важные объекты предметной области запоминаются в виде базовых фреймов, которые используются в качестве стартовых состояний, на основании которых строятся фреймы для новых состояний.
2. Процесс сопоставления — процесс, который проверяет правильность выбора фрейма: сначала с помощью эвристического правила выбирается некоторый базовый фрейм и при заполнении слотов этот фрейм сам подтверждает или не подтверждает соответствие. Если возникло несоответствие, то управление передается другому подходящему фрейму из этой системы. Если все сопоставления неудачны, то считается, что задача не имеет решения
3. Иерархическая структура — информация об атрибутах, которую содержит фрейм верхнего уровня, совместно используется всеми фреймами нижнего уровня, связанными с ним.
4. Связи различия — связи между фреймами, позволяющие находить нужный фрейм в случае неудачного сопоставления с текущим
5. Отношения «абстрактно / конкретно» и «целое / часть» (IS_A, PART_OF)
6. Значение по умолчанию — постепенно заменяются на достоверную информацию. Выводами на основании значений по умолчанию можно восполнить недостаток достоверной информации. Это расширяет возможности системы, но допускает получение неправильных выводов
Содержание фрейма
1. Имя слота — должно быть уникально в пределах фрейма. Существуют
зарезервированные имена (например: указатель на родительский фрейм, список
дочерних фреймов, автор фрейма и т. д.)
2. Указатель наследования — указывает способ наследования атрибута
дочерними фреймами. Стандартные способы наследования:
– unique — слот наследуется, но значение не привязано к родительскому);
– same — значение атрибута тоже наследуется;
– range — ограничение диапазона значений;
– member — ограничение выбора из элементов, перечисленных в слоте
родителя;
– override — при отсутствии указания, значение слота фрейма родителя
наследуется по умолчанию, но можно задать и другое значение;
– independent — слот не наследуется.
3. Родительский фрейм — указатель на фрейм, из которого унаследован
атрибут.
4. Тип значения — определяет, что может быть значением слота (число, строка, булево значение, имя другого фрейма, список, массив, выражение, присоединенная процедура.
5. Демон — процедура, автоматически запускаемая при выполнении некоторого условия. Существует 3 типовых вида демонов:
– IF_NEEDED — запускается, если в момент обращения к слоту его значение
не было установлено;
– IF_ADDED — запускается при подстановке в слот значения;
– IF_REMOVED — запускается при удалении значения слота.
Возможны и другие виды демонов.
6. Присоединенная процедура — запускается по сообщению, переданному из другого фрейма.
Фреймовую систему в составе экспертной системы можно использовать тремя
способами.
1. Как базу данных (рис. 2.6): в этом случае присоединенных процедур и демонов в системе нет
2. Как базу знаний (рис. 2.7): роль присоединенных процедур ограничена, в качестве демонов используются правила
3. Как целую экспертную систему (рис. 2.8): вывод осуществляется с помощью передачи сообщений между фреймами, машина вывода распределена в
системе.
Основное достоинство фреймовых систем — возможность организовать любое необходимое управление выводом. В то же время, поскольку знания задаются процедурами, приобретение новых знаний сильно усложняется

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

Экспертная система может включать в себя следующие элементы.
1. Лингвистический процессор — облегчает обмен информацией между экспертной системой и пользователем. Лингвистический процессор, с одной стороны, ведет грамматический разбор и дает интерпретацию вопросов, команд и другой информации от пользователя. С другой стороны, он оформляет информацию, передаваемую экспертной системой, включая ответы на вопросы и объяснение поведения.
2. Вместо доски объявлений на рис д.б. БД и система взаимодействия со средой.
3. Диспетчер обеспечивает управление заявками и определяет, какое из ожидающий действий следует выбрать для выполнения с помощью эвристики.
4. Интерпретатор выполняет выбранную заявку путем применения соответствующего правила из базы знаний.
5. Компонента обеспечения непротиворечивости пытается поддерживать некоторое непротиворечивое представление для появляющихся решений
6. Компонента оправданий объясняет пользователю действия системы. Как правило, она отвечает на вопросы «почему было достигнуто некоторое заключение, а другие заключения были отброшены ?». Компонента оправданий производит трассировку решения в обратном направлении, находя те промежуточные гипотезы или данные, на которые опирается полученное решение.
7. В базе знаний хранятся факты, правила и другая информация о текущей задаче. Она может иметь любое из ранее рассмотренных представлений каждое из этих условий более подробно.
Разработка возможна, если выполняются следующие условия:
1) существуют эксперты, которые лучше чем новички разбираются в данной проблеме;
2) задача относится к структурированной области, где достаточно просто выделить некоторые понятия;
3) решение не должно основываться на интуиции и здравом смысле, т. е. на знаниях, которые невозможно включить в базу знаний;
4) у экспертов существует единое мнение по поводу способов решения задачи и критериев оценки эффективности полученного решения;
5) эксперты могут выразить словами используемые в своих рассуждениях методы;
6) решение задачи требует только рассуждений а не действий. Отметим, что современные разработки в области искусственного интеллекта позволяют постепенно отказаться от обязательного выполнения требований 4—6.
Разработка оправданна, в следующих случаях:
1) решение имеет значительный экономический эффект;
2) использование для решения задачи экспертов невозможно из - за трудоемкости задачи, нехватки количества экспертов, их занятости;
3) при передаче информации экспертам и приеме от них решений происходит недопустимая потеря времени или информации;
4) решение задачи происходит в окружении, враждебном человеку, и возникают риски, которые сложно точно оценить.
Методы искусственного интеллекта соответствуют задаче, если:
1) решение выполняется посредством обработки символьной информации, а не численных операций;
2) решение задачи имеет эвристическую природу, не известны алгоритмические способы ее решения;
3) проблема достаточно сложна, чтобы оправдать накладные расходы, связанные с разработкой и эксплуатацией экспертной системы.

8. Этапы построения экспертной системы.
эволюционный метод построения программного комплекса.
1. В ходе идентификации инженер знаний и эксперт работают вместе над вопросом выделения предметной области и интересующей их темы. Они также указывают участников процесса создания экспертной системы, определяют необходимые ресурсы, время, вычислительные средства, источники знаний и решают, каковы цели и задачи построения экспертной системы.
2. В ходе концептуализации эксперт и инженер знаний выявляют основные понятия, отношения между ними, характер информационных потоков, необходимых для описания процесса решения задачи в данной предметной области.
3. Формализация связана с ограничением ключевых понятий и отношений между ними в некотором формальном представлении, выбираемом среди инструментальных средств или языков построения экспертных систем. Инженер знаний должен выбрать язык и, с помощью эксперта, представить в рамках этого языка основные понятия и отношения.
4. В ходе реализации инженер знаний комбинирует и реорганизует формализованные знания, добиваясь их совместимости с характеристиками информационных потоков задачи.
5. В ходе тестирования производится оценка работы программы - прототипа и ее изменение с целью приведения в соответствие с требованиями, определяемыми экспертом. При этом наиболее часто изменяются: – характеристики ввода / вывода: например, задаваемые вопросы могут быть трудными или плохо сформулированными для пользователя, или может потребоваться изменить порядок опроса;
Реализация:
1. Универсальные языки программирования (С ++, Lisp).
2. Скелетные экспертные системы — заимствование структуры из уже
существующих экспертных систем. Из старой системы необходимо удалить все
специальные знания о предметной области.
3. Универсальные языки представления знаний.
4. Универсальные оболочки для построения экспертных систем

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





10. Концепция машинного обучения: цель обучения, основные составляющие задачи обучения, режимы обучения.
Постановка задачи обучения
Обучение — это механизм, позволяющей системе искусственного интеллекта приобретать новые знания в результате анализа поступающих на ее вход данных. Цель обучения — обеспечить возможность решения не только конкретной задачи, но и аналогичных задач из заданной предметной области. новые знания поступают в базу знаний системы не только напрямую от пользователя, но и в результате анализа поступающих на вход системы данных
1. Индукция (обобщение знаний). корректное распространение знаний на другие возможные ситуации. Индукция является главной функцией обучения.
2. Использование индуктивного порога. обучающаяся система должна обобщать информацию с привлечением некоторых эвристик, позволяющих отбирать те аспекты доступных ей знаний, которые вероятнее всего окажутся полезными в ходе дальнейшего использования системы.
3. Изменение знаний. Если оказывается, что уже имеющиеся в системе искусственного интеллекта знания входят в противоречие с новыми знаниями, полученными в результате индукции по поступающим данным, то система должна обеспечить коррекцию своей системы знаний, позволяющую исключить такие противоречия
Режимы обучения
1. Обучение с учителем Вместе с примерами задач система искусственного интеллекта получает информацию о том, каково правильное решение этих задач. При этом основная задача обучения — дополнить базу знаний знаниями, позволяющими получать решения, совпадающие с подсказанными учителем
2. Обучение с подкреплением. Примеры задач предъявляются системе искусственного без сообщения правильных решений для них. После выработки системой решения каждой задачи она получает сведения о том, как объект управления прореагировал на эти решения (т. е. насколько правильными они были).
3. Обучение без учителя (самообучение). Примеры задач предъявляются системе искусственного интеллекта без сообщения правильных решений для них, реакция объекта управления на принятые решения также неизвестна. Основная задача обучения в этом случае — формирование категорий (кластеризация): система должна выявить сходные примеры и изменить базу знаний так, чтобы по сходным примерам получать сходные решения, а по существенно различным примерам — различные решения
11. Существующие подходы к организации машинного обучения. Принципы обучения с учителем.
Общее свойство систем искусственного интеллекта, использующих обучение с учителем, состоит в том, что база знаний системы в ходе обучения подстраивается под «правильное» представление знаний. При этом мерой «правильности» служит покрытие «общими» знаниями, представленными базой знаний, «частных» знаний, представленных обучающими примерами. Рассмотренный пример демонстрирует основные свойства систем обучения с учителем:
1) для модификации базы знаний используются операции обобщения и специализации ;
2) количество и порядок предъявления примеров влияют на результат обучения : неудачный порядок может завести программу модификации базы знаний в тупик.
Алгоритм поиска в пространстве версий
Пространство версий — это подмножество пространства состояний, задающее множество всех описаний понятия, согласующихся с обучающими примерами. При добавлении новых примеров пространство версий сужается.
Рассмотрим алгоритм исключения версий, приводящий к решению задачи обучения. Используется множество G — множество максимально общих версий описания понятия, и множество S — множество максимально конкретных версий описания понятия. Алгоритм конкретизирует G и обобщает S до тех пор, пока они не совпадут
Алгоритм построения дерева решений ID3
Данный алгоритм также реализует поиск в пространстве состояний, но, в отличие от поиска в пространстве версий, ориентирован на пакетную обработку обучающий примеров. Это означает, что все множество примеров анализируется параллельно ( все примеры должны быть заданы до начала обучения ). Понятие описывается с помощью дерева решений. Дерево решений — это иерархическое представление соотношения различных свойств у объектов, соответствующих понятию
Задача обучения — построить дерево решений, правильно классифицирующее все обучающие примеры. Пространством состояний является множество всевозможных деревьев решений переходы между элементами пространства состояний — это добавление / удаление ветвей дерева.
Алгоритмы дают низкое качество обучения если:
1) обучающие данные содержат ошибки ;
2) для некоторых примеров данные о значениях каких - либо признаков отсутствуют ;
3) некоторые признаки принимают значение из непрерывного интервала ;
4) вычислительная сложность алгоритма обучения слишком велика, чтобы обработать все обучающие примеры

12. Индуктивные пороги обучения, виды семантических порогов.
1. Синтаксический порог — ограничение допустимых состояний способом их формального описания. Наиболее часто используются следующие синтаксические пороги:
а ) коньюнктивный порог — ограничение допустимых состояний до множества коньюнкций литералов ; исключение дизьюнкиций сильно упрощает задачу обучения, т. к. нет необходимости рассматривать противоречащие друг другу примеры экземпляров описываемого понятия ;
б ) ограничение на количество дизьюнктов : исключительное использование коньюнкции является слишком жестким ограничением при описании достаточно сложных понятий в практических задачах, поэтому малое количество допустимых диьзьюнктов — это компромисс между сложностью обучения и сложностью допустимого описания понятия ;
в ) векторы признаков — описание объектов - примеров понятия с помощью набора признаков, значения которых могут быть различны у разных объектов ;
г ) деревья решений — иерархическое представление соотношения свойств у объектов, соответствующих понятию ( как это было описано выше ).
2. Семантический порог — ограничения на пространство состояний, использующие априорно заданные семантические особенности конкретной прикладной задачи.
Использование семантических индуктивных порогов реализуется при:
– обучении на основе объяснения ; – обучении по аналогии.
Обучение на основе объяснения
При обучении на основе объяснения знания о предметной области являются априорными, а обучающие примеры используются для преобразования неявных зависимостей, содержащихся в этих знаниях, в явные.
Основные элементы задачи символьного обучения на основе объяснения:
1) априорные сведения об области определения — набор правил и фактов, хранимых в базе знаний до начала обучения ; в их число входят также правила, заключением которых является отнесение объекта к искомому понятию
2) обучающие примеры ;
3) целевое правило — новое правило, которое должно быть занесено в базу знаний в результате обучения, и описывающее искомое понятие напрямую через свойства обучающих примеров ;
4) критерий функциональности — дополнительные ограничения на форму целевого правила.
Обучение происходит в два этапа:
1) для обучающего примера строится дерево решения, узлы которого содержат правила, использованные для доказательства того, что этот пример соответствует понятию
2) значения в узлах дерева, относящиеся к конкретному примеру, рекурсивно по всем узлам дерева заменяются на переменные К достоинствам обучения на основе объяснения можно отнести следующее:
1) если обучающие примеры содержат несущественную информацию, она игнорируется алгоритмом обучения и не усложняет его работу ;
2) алгоритм обучения формирует заведомо адекватное обобщение обучающих данных, согласующееся с априорно известными теоретическими сведениями ;
3) количество обучающих примеров может быть очень мало ;
4) обучение на основе объяснения позволяет уточнять и корректировать описание предметной области по результатам анализа примеров : если некоторая ветвь доказательства того, что пример относится к понятию не может быть достроена — это говорит о необходимости дополнения соответствующего раздела теоретического описания предметной области.
Обучение по аналогии. При обучении по аналогии предполагается, что из сходства объектов по одним признакам следует и их сходство по другим признакам. Выделяются потенциальные источники аналогии ( обучающие примеры объектов ) и цель. Задача обучения по аналогии — выделить источник аналогии, который соответствует цели по наиболее полной структуре отношений с другими понятиями из своей предметной области и отобразить другие свойства источника аналогии в предметную область цели.
Этапы решения задачи обучения по аналогии таковы.
1. Поиск источника аналогии — зная целевую проблему, необходимо выбрать потенциальный источник аналогии. При этом нужно выделить те свойства цели и источника, которые подтверждают правдоподобие аналогии, и проиндексировать знания согласно этим свойствам.
2. Развитие аналогии — выделяются дополнительные свойства и отношения найденного источника аналогии.
3. Отображение — отображение атрибутов источника в область определения цели
4. Подтверждение — проверяется корректность сделанного отображения и при необходимости происходит возврат к этапу (3)
5. Собственно обучение — полученные знания сохраняются в форме, которая может быть применена в дальнейшем в области определения цели. Порядок обучения следующий.
1. Из описания источника исключаются лишние свойства : исключаются предикаты с единственным аргументом ( т. к. маловероятно, что они содержат важную семантическую информацию ):
2. Отношения отображаются из источника аналогии в описание цели. Выбираются только те отношения, которые могут быть отображены без изменений, или с изменением параметров : вращается _ вкруг, тяжелее.
3. Устанавливается соотношение между объектами в описании источника аналогии и цели:
4. В описание цели отображаются наиболее высокоуровневые отношения из источника аналогии

13. Принципы машинного самообучения.
примеры задач предъявляются системе искусственного интеллекта без сообщения правильных решений для них. Эти правильные решения, если бы они были известны, можно было бы отнести к нескольким различным классам ( категориям ) решений
Накопительная кластеризация — это наиболее простой и распространенный на практике способ решения задачи самообучения. Накопительная кластеризация опирается на последовательное упорядочивание всех объектов, предъявленных для обучения, по степени их сходства между собой. Общая схема алгоритмов накопительной кластеризации имеет следующий вид:
1) проверяются все пары объектов и выбирается пара с максимальной степенью подобия свойств, которая объявляется новым кластером ;
2) определяются свойства кластера, как некоторая функция свойств его элементов ( например, некоторые усредненные значения свойств элементов );
3) все объекты упорядочиваются по степени подобия свойств уже созданным кластерам ;
4) если объект со свойствами, наиболее схожими с одним из кластеров, имеет степень подобия ему выше некоторого порога, то этот объект включается в кластер и процесс повторяется с шага (2);
5) иначе повторяется с шага (1);
6) и т. д., пока все объекты не войдут в один кластер. Результат работы алгоритма накопительной кластеризации — бинарное дерево, листья которого — это отдельные объекты, корень — сформированный кластер, а промежуточные узлы — последовательные кластеры, полученные в ходе работы алгоритма
Концептуальная кластеризация
Концептуальная кластеризация — это процедура самообучения, основанная на создании определений новых понятий в процессе формирования категорий. Общая схема алгоритмов концептуальной кластеризации имеет следующий вид:
1) выбрать k опорных объектов из множества существующих ;
2) для каждого опорного объекта, используя его в качестве положительного примера, а все остальные — в качестве отрицательных, создать наиболее общее определение покрывающее все положительные и не одного отрицательного примера ;
3) классифицировать все объекты в соответствии с этим описаниями ; заменить каждое максимально общее определение максимально конкретным, покрывающим все объекты этой категории ;
4) выбрать элемент, ближайший к центру каждого класса ( наиболее схожий с ним в смысле накопительной кластеризации );
5) если приемлемые кластеры еще не сформированы, то, используя полученные элементы в качестве опорных, повторить шаги (2)–(4); типичная мера « приемлемости » полученных кластеров — сложность построенных определений ;
6) если не удается сформировать приемлемые кластеры в течение достаточно большого количества итераций, то выбрать новые опорные объекты, наименее схожие с уже сформированными кластерами и повторить процесс. Укажем основные проблемы, возникающие при реализации алгоритмов самообучения.
1. Практически значимые категории часто не определяются необходимыми и достаточными условиями принадлежности к ним, т. е. понятие должно
определяться сложной системой сходства между элементами объектов, относящихся к одному понятию.
2. Важность (« базовость ») понятий не всегда пропорциональна их уровню в иерархии (« стул » — более базовое и легко распознаваемое для человека понятие и чем менее общее « офисный стул » и чем более общее « мебель »).
14. Машинное обучение с подкреплением.
При обучении с подкреплением система искусственного интеллекта должна выработать способ обработки поступающих данных, который максимизирует вознаграждение за принятые ею решения. Введем следующие обозначения:
s(t) — состояние задачи ( среды функционирования системы искусственного интеллекта, термины « среда » и « задача » при обучении с подкреплением имеют один и тот же смысл ) в момент времени t, зависящее от s(t-1), a(t-1);
a(t) — действие системы искусственного интеллекта в момент времени t, зависящее от s(t);
r(t) — вознаграждение в момент времени t, зависящее от s(t-1), a(t-1). Цель функционирования системы искусственного интеллекта заключается в выборе последовательности действий, максимизирующих суммарное вознаграждение по всему времени решения задачи. П : {s} → {a} — политика выполнения действий в зависимости от состояний ;
V( П,s) — ценность состояния s при использовании политики П, т. е. вознаграждение, на которое может рассчитывать система на всех последующих шагах, продолжая действовать из состояния s согласно политике П. Использование функции ценности позволяет системе искусственного интеллекта принимать « непопулярные » меры, которые на данном конкретном шаге дают маленькое вознаграждение, но в последующие моменты времени приводят к получению больших вознаграждений. В ходе функционирования системы искусственного интеллекта она переводит задачу по последовательности состояний за счет действий, выбираемых в соответствии с некоторой политикой. При этом система на каждом шаге получает отклик среды в виде значения вознаграждения. Для выбора действия на очередном шаге она вычисляет ( с помощью некоторой эвристики ) значения ценности каждого из состояний, в которое она может перевести задачу очередным действием, и выбирает действие с максимальной ценностью. Для достаточно сложных систем эвристика, вычисляющая ценность, представляет собой модель функционирования среды

15. Генетические алгоритмы обучения.
При генетическом ( эволюционном ) подходе обучение рассматривается как конкуренция внутри популяции между эволюционирующими кандидатами на роль решения задачи. Генетический алгоритм в общем виде имеет следующую структуру:
1) инициализировать начальное поколение кандидатов ( потенциальных решений );
2) применить к кандидатам генетические операторы рекомбинации ;
3) к полученным в результате шага (2) особям применить генетические операторы мутации ;
4) заменить старое поколение особей, новым — полученным на шаге (3);
5) отобрать особей, являющихся наиболее адекватными решениями поставленной задачи ( согласно заданному критерию качества решения );
6) если решение требуемого качества еще не получено, то перейти к шагу (2), иначе с помощью генетического оператора отбора выбрать лучшее из имеющихся решений
авильных ответов кандидатов на этом множестве. Основная сложность при реализации генетических алгоритмов возникает при выборе сочетания способа кодирования кандидатов и генетических операторов:
1) генетические операторы должны порождать только корректные коды, т. е. коды, которым соответствуют имеющие прикладной смысл кандидаты ( пример : поиск оптимального пути в графе без повторения вершин — если кодировать путь
просто номерами вершин, то результат рекомбинации может содержать повторяющиеся вершины )
2) близкие коды должны соответствовать близким кандидатам, т. е. кандидатам, которые незначительно отличаются с точки зрения своего поведения при решении задачи ( пример : если распознаются целые числа из интервала [7;9], то двоичные коды числе 7 и 8 не имеют ничего общего, т. е. использование кода из примера, рассмотренного выше, не позволит качественно обучиться решению задачи )
3) генетические операторы рекомбинации и мутации должны порождать потомков, которые будут незначительно отличаться от родителей с точки зрения своего поведения при решении задачи ( т. е. эволюция не должна представлять собой хаотическую смену поколений
Генетическое программирование В генетическом программировании в качестве кандидатов, участвующих в процессе генетического отбора, используются программы. В ходе эволюции они обмениваются фрагментами и усложняются. При этом новые кандидаты могут вызывать уже существующих кандидатов в качестве подпрограмм. Программы пишутся в соответствии с функциональной парадигмой программирования. Каждая программа строится в виде дерева, узлами которого могут являться элементы из двух множеств:
– множество функций — задает базовые операции на структурами данных
( например, арифметические операции ) и вызовы других программ ;
– множество структур данных — задает структуры данных и конкретные значения для них, обрабатываемые функциями. Код программы представляет собой конечную последовательность элементов этих двух множеств и задает правила построения ее дерева:
– если в качестве очередного элемента кода указан элемент из множества функций, то к очередной недостроенной ветви дерева присоединяется узел с именем этой функции, сыновьями которого являются аргументы функции
– если в качестве очередного элемента кода указан элемент из множества структур данных, то к очередной недостроенной ветви дерева присоединяется лист с именем этой структуры данных или значением.
Использование клеточных автоматов Данное направление развития методов генетического обучения представляет собой способ замены искусственного отбора кандидатов оператором отбора на естественный отбор в результате взаимодействия кандидатов между собой. Клеточный автомат представляет собой совокупность:
1) множества однотипных конечных автоматов — кандидатов ;
2) заданной для них регулярной топологии ( взаимного расположения );
3) правила выбора для каждого автомата множества соседних автоматов ( т. е. расположенных близко к данному с точки зрения заданной топологии ). Общее свойство (« однотипность ») всех автоматов состоит в том, что текущее состояние каждого автомата определяется функцией от его собственного состояния и состояний соседних автоматов на предыдущем шаге эволюции. Специальной процедуры « уничтожения » старых кандидатов нет — вместо этого у всех автоматов есть состояния, соответствующие их « смерти ». Т. е. если автомат имеет структуру позволяющую так влиять на соседние автоматы, чтобы чаще избегать попадания в это состояние, то он продолжает свое существование в течение большего количества шагов эволюции и оставляет больше кандидатов - потомков