2. Языки инженерии знаний.

• Язык логического программирования PROLOG

• Язык функционального программирования LISP

• Многофункциональные программные среды(Одной из первых многофункциональных сред искусственного интеллекта является LOOPS. в которой в рамках единой архитектуры обмена сообщениями были объединены четыре парадигмы программирования):

  • Процедурно-ориентированное программирование. Эта парадигма была представлена языком LISP

  • Программирование, ориентированное на правила. Эта парадигма аналогична предыдущей, но роль процедур играют правила "условие-действие".

  • Объектно-ориентированное программирование.

  • Программирование, ориентированное на данные.

3 Средства автоматизации разработки экспертных систем.

• Дополнительные модули-под дополнительными модулями понимаются те полезные программы, которые можно выполнять вместе с приложением.

4.Оболочки экспертных систем-(программный продукт, обладающий средствами представления знаний для определенных предметных областей)

• Оболочка, shell

• CLIPS

• DYNACLIPS

• FuzzyCLIPS

6. Методы обучения интеллектуальных систем. Деревья решений и их применение для автоматизированного построения баз знаний.

Каким образом формировать базы знаний:

• Формирование содержимого БЗ

• Методы распознавания образов

1. Классификация методов обучения

   1. Обучение без логического вывода

      1. Ввод программы

      2. Ввод данных

   2. Создание и коррекция БЗ

      1. Прямой ввод содержимого БЗ с исп-ем экранных редакторов и компиляторов

      2. Создание БЗ в процессе диалога с ЭС

      3. Извлечение знаний их различных текстов, написанных на естественном или огр. подм-ве естест-го языка

   3. Обучение по примерам

      1. Прямое обучение(Все обучающие примеры записываться в память и сравниваться с эталоном)

2. Недостатики(Прямого обучение) – (Бол. Объем информции,Избыточность информации,Слабая помехоустойчивость)

   1. Деревья решений(наиб. Попульрный)

   2. Индуктивное обучение

   3. Генетические алгоритмы

Деревья решений

Вершины – признаки

Дуги-значения признаков

Листья-концепт

По дереву строим правила например:

If((p1=V1) and (p2=V1)) then C1

If((p1=V3) and (p3=V2) and (p2=V1)) then C1

Построение дерева решений.

Vi– кол-во значений, которые может приниматьi-й признак

fi- стоймость измеренияi-го признака

Pr(Cj) – априорная вер-ть концептаCj

Pr(Sv(y)/Cj) – вероят-ть ветвиSv(y) при условий наличия классаCj

Ветвь Sv(y) – это мн-во пар(признак, значение)

Pr(Cj/Sv(y)) – Вер-ть классаCjпри условии наличия ветвиSv(y)

Wji– стоимость ошибочной классификации при отнесении к классуCj, если в дейтс-ти классCi

Pr(Cj/Sv(y)) =

Стоимость потерь:

– стоимость потерь для веткиSv(y)

– это один шаг динамического программирование

6. Методы индуктивного обучения и их реализация в пакете Геконал.

Идея индуктивного обучения: обобщение имеющихся обучающих примеров.

Обобщить – выкинуть ненужную информацию.

x₁x₂x₃ . . . . . . . . . .x_n\

. |> 1 класс

. /

. . . . . . . . . . . . . . . . . . \

. |> 2 класс

. /

.

.

. . . . . . . . . . . . . . . . . . \

. |> kкласс

. /

Выборки разбиты на классы.

Индуктивное обучение:

1. Номинализация (переход к конечному числу признаков)

- логические признаки{да(1) нет(2)}

- целочисленные признаки:

а) Тождественное копирование. Исходные значения признаков рассматриваются как номинальные значения, т.к. выборка конечна, то признаки принимают конечное число значений.

б) Ручная кластеризация

в) Атоматический кластер-анализ.

Должна быть согласованность метрик.

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

Например: цвет {красный(1) зеленый(2) синий(3)}

- вещественные признаки

а) Ручная кластеризация (один из способов интервального шкалирования.

Делим на интервалы:

Оценка плотности распределения

выбранный признак

б) Автоматический кластер анализ.

Алгоритм АВП – это алгоритм адаптивного выбора подкласса.

Рассмотрим суть на двумерном пространстве:

Для каждого класса формируется набор подклассов.

– плотность нормального распределения;

М – количество кластеров.

Научная подоплека – каждая плотность распределения может быть оценена как бесконечная сумма плотностей нормального распределения.

µ_i– оценка среднегоj-го кластера

ε_j– ковариация матр.j-го кластера.

p_j– весовые коэффициенты – вероятности появления отдельных кластеров

(x₁,x₂)-> номер кластера

------------------------------------------------------------------------------------------------------

Индуктивное обучение:

1. Номинализация.

2. Построение миноров эталонов для каждого класса.

3. Учет пересечений и оценка факторов уверенности.

4. Генерация правил.

-----------------------------------------------------------------------------------------------------

Пример:

1) После номинализации:

3 класса:

IклассIIклассIIIкласс

1 1 1 2 2 2 3 3 3

1 2 1 1 1 2 3 2 3

1 2 2 2 2 2 1 1 2 \

3 2 1 1 1 2 | – > подобные

1 1 2 / заменяются . на 1 экземпляр

2) Построение миноров эталонаов Минор эталон – это вектор, компоненты которого принимают значения из диапазона возможных значений “-“ (значение данного признака не имеет значения). Минор-эталон покрывает вектор, если его компоненты, отличные от “-“ совпадают с каким вектора.

Необхоимо найти для каждого класса миноры-эталоны, покрывающие в совокупности все исходные номинализированные обучающие примеры одного класса и не покрывающие ни один пример из др. классов.

Порядок минора эталона – количество элементов (в строке?) отличных от “-“

Строятся миноры эталоны порядка 1, не покрывающие ни один об. пример из др. классов.

Кл. 1 - - 1

Кл. 2 2 - -

Кл. 3 - 3 -

Кл. 3 - - 3

Второй порядок:

Кл. 1 1 2 –

Третий порядок:

Ничего не дает

Вектора пересечений – это непокрытые вектора. В примере это:

Кл. 1: 1 1 2

Кл. 2: 3 2 3

3) Учет пересечений и оценка факторов уверенности.

К минорам-эталонам добавляем вектора пересечений.

Кл. 1 - - 1 100%

- - 1 100%

Кл. 2 2 - - 100%

1 1 2 25%

Кл. 3 - 3 - 100%

- - 3 100%

1 1 2 75%

Также на данном этапе вохможна минимизация миноров эталонов.

4) Далее по полученным минорам эталонам строим правила.

Например:

IF(признак<50) -> класс 1CF=100 % (сам в ахуе)

----------------------------------------------Про ГЕКОНАЛ----------------------------------------------

Геконал обеспечивает решение следующих задач:

- графическое отображение предъявленной статистической выборки путем проецирования выбранного пространства классификационных признаков на двухмерную экранную плоскость;

- гистограммирование распределений значений отдельных классификационных признаков;

- построение наборов частных решающих правил (частных классификаторов) в выбираемых алфавитах классификационных признаков с помощью встроенных процедур ручного и автоматического кластер-анализа и проведение их тестирования с целью предварительной оценки качества;

- проведение кластер-анализа предъявленной статистической информации с помощью алгоритма адаптивного выбора подклассов (АВП) с дополнительной возможностью предварительного оценивания центров кластеров по критерию MaxMin расстояния;

6. Генетические алгоритмы.

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

Популяция – это конечное множество особей.

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

Хромосомы (другие названия – цепочки или кодовые последовательности) – это упорядоченные последовательности генов.

Ген (также называемый свойством, знаком или детектором) – это атомарный элемент генотипа, в частности, хромосомы.

Проиллюстрируем примеры хромосомы и генов для двоичного способа кодирования параметров задачи: 00110011010 (все вместе – хромосома, одна цифра – ген)

Генотип или структура – это набор хромосом данной особи. Следовательно, особями популяции могут быть генотипы либо единичные хромосомы (в довольно распространенном случае, когда генотип состоит из одной хромосомы).

Фенотип – это набор значений, соответствующих данному генотипу, т.е. декодированная структура или множество параметров задачи (решение, точка пространства поиска).

Каждая хромосома может кодировать только один параметр задачи. Но так как в одном генотипе может быть несколько хромосом, то один генотип может закодировать несколько параметров. Например: генотип включает в себя две хромосомы, каждая хромосома состоит из 3 генов, значит, первые 3 гена генотипа кодируют один параметр, а вторые 3 гена – второй параметр.

Аллель – это значение конкретного гена. Локус или позиция указывает место размещения данного гена в хромосоме (цепочке). Локи – это множество позиций генов.

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

Классический генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:

1. 1. инициализация, или выбор исходной популяции хромосом;

2. оценка приспособленности хромосом в популяции – расчет функции приспособленности для каждой хромосомы; f(x) – нетривиальная оценочная функция жизнестойкости каждого экземпляра (здают заранее).

3. проверка условия остановки алгоритма;

4. селекция хромосом – выбор тех хромосом, которые будут участвовать в создании потомков для следующей популяции;

5. применение генетических операторов – мутации и скрещивания; мутация – самопроизвольное изменение одной из хромосом (0100101->0100100) инверсия – (0100101->1011010)

6. кроссинговер (кроссовер) . Где точка – точка кроссовера. Кароч меняются циферками. 0110.111 1011.001 0110 001 1011 111

7. формирование новой популяции;

8. выбор «наилучшей» хромосомы.

Блок-схема основного генетического алгоритма изображена на рисунке.

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

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

6. Стратегии поиска. Критерии оценки качества методов поиска.

Классификация методов поиска:

1. По общему направлению поиска

- в прямом направлении

- в обратном

- привет от группы 9303:)

- двунаправленный поиск

2) По типу перебора

- слепой перебор

- поиск в ширину

- поиск в ширину

- направленный перебор

Показатели оценки:

1. Направленность

p=L/T; L – длина найденного пути, T – общее количество вершин (состояний) в ходе поиска.

S₀

S_f

p=2/6=1/3

2. Эффективность ветвления (B)

- это постоянное число приемников, которыми могла бы обладать каждая вершина в дереве (u) с глубиной равной длине пути к цели и числом вершин пройденных в ходе поиска

S₀

S_f

p=1/6, L=2, T=12;

B+B²+…+B^L=T

p=L*(B-1)/(B(B^L-1))

B=3