Файл: Учебнометодическое пособие по лабораторному практикуму. Спб ниу итмо, 2013. 35 с. В учебнометодическом пособии предлагаются лабораторные работы, охватывающие основные понятия теории искусственного интеллекта.pdf

18
Yes
?– mother(kat, alex).
No
?– father(victor, alex).
No
Как видно
, для обработки этих запросов интерпретатору необходимо выполнить логический вывод
, а
не просто обратиться к
базе правил
Также видно
, как действует предположение о
замкнутости базы знаний
: поскольку в
базе нет фактов об истинности parent(kat, alex) и
man(victor), то последние два запроса возвращают "
Нет ".
В
Прологе существуют также и
запросы в
виде выражений с
переменными
Посмотрим
, как работают эти запросы
?– mother(kat, X).
X = victor
Yes
?– grandfather(X, alex).
X = serg
Yes
?– grandfather(X, Y).
X = serg, Y = alex
Yes
?– grandfather(X, kat).
No
?– man(X).
X = serg
Yes
Здесь можно отметить следующее
В
подобного рода запросах предполагается квантор существования для входящих в
него переменных
Выражение истинно
, если найдется хотя бы одно подходящее значение
X
(
не имеет значения
, как именно обозначать переменные в
запросе
).
В
действительности
, при нахождении в
базе первого значения
, для которого введенное выражение истинно
, интерпретатор спрашивает пользователя
, продолжать ли поиск
Поиск продолжается при нажатии команды ";" (
или
) до тех пор
, пока не будет дан ответ "
Нет " в
связи с
исчерпанием всех возможностей
, например
,
?– man(X).
X = serg ;
X = alex ;
No
Более сложные выражения в
запросах также допустимы
, например
,
?– mother(kat, X), father(Y, X).
X = victor, Y = serg
Yes

19
Этот запрос позволяет определить
, кто является отцом сына kat.
Следует обратить внимание на некорректность работы программы
, содержащей противоречия вида something(X) :– not(something(X)). а
также циклические определения вида man(X) :– not(woman(X)). woman(X) :– not(man(X)).
Экспериментальная часть
В
данной работе производят построение простейшей базы знаний в
рамках логического представления с
использованием языка
Пролог и
устанавливают возможности и
ограничения
: 1) логических представлений при описании понятий и
взаимосвязей между ними
; 2) интерпретатора отвечать на запросы
Для этого необходимо выполнить следующую последовательность действий
1.
Выбрать систему взаимосвязанных понятий
, подобную системе родственных отношений
, но отличную от нее
2.
Формализовать отношения между понятиями в
форме логических выражений в
рамках исчисления предикатов первого порядка
3.
Реализовать логические выражения как общие правила в
программе на языке
Пролог
; дополнить программу совокупностью частных фактов
Полученная в
результате программа является основой отчета по лабораторной работе
4.
Определить возможности созданной базы знаний по ответу на запросы
, требующие логического вывода
(
т е
ответы на которые не содержатся в
базе в
явном виде
).
Установить запросы
, на которые ответ интерпретатора не соответствует ожидаемому
(
уделить внимание неявному предположению замкнутости базы знаний
).
5.
Проанализировать полученные результаты
Сделать выводы по работе
: сформулировать эмпирически обоснованные преимущества и
недостатки логических представлений для систем взаимосвязанных понятий
Литература
1.
Люгер, Д.Ф. Искусственный интеллект: стратегии и методы
решения сложных проблем
/
Д
Ф
Люгер
. – 4- е
изд
.:
Пер с
англ
. –
М
.:
Изд дом
“
Вильямс
”, 2003. –
С
. 609-684.
2.
Джексон, П. Введение в экспертные системы: учеб. пособие
/
П
Джексон
. –
Пер с
англ
. –
М
.:
Изд дом
“
Вильямс
”, 2001. –
С
. 177-200.
Вопросы для самопроверки:

20 1.
К
какому типу представлений знаний можно отнести язык
Пролог
?
2.
Из каких базовых элементов состоит программа на языке
Пролог
?
3.
Что означает высказывание
, согласно которому программирование на языке
Пролог является декларативным
?
4.
Имеет ли значение порядок
, в
котором в
программе на
Прологе заданы правила и
факты
?
5.
Как реализуется предположение о
замкнутости базы знаний в
языке
Пролог
?
Какие следствия из этого можно сделать
?
6.
В
чем заключается функция интерпретатора языка
Пролог
?
7.
Какие понятия или взаимосвязи между понятиями затруднительно представить на языке
Пролог
?
Какие преимущества и
недостатки
Пролог имеет по сравнению с
другими языками программирования и
с другими представлениями знаний
?
3. Исследование влияния параметров обучающей выборки на
вероятность распознавания новых образов
Цель работы
– ознакомиться с
методами распознавания образов и
освоить их применение в
различных условиях
, определяемых характером обучающей выборки
: ее размером
, наличием в
ней выбросов
, степенью перекрытия классов
Данная работа имеет два варианта выполнения
Вариант 1
Задание по работе:
1.
Изучить теоретическую часть работы
2.
Реализовать методы эталонных образов и
ближайшего соседа
3.
Путем варьирования обучающей выборки определить влияние следующих факторов на вероятности правильного распознавания
: наличие в
обучающей выборке выбросов
, размер обучающей выборки
, форма областей
, занимаемых классами в
пространстве признаков
Теоретическая часть
Постановка
задачи
дискриминантного
распознавания
образов
В
распознавании образов рассматривается вопрос о
разделении объектов на классы
При этом требуется по некоторому описанию объекта
(
такое описание называется образом
) определить его отношение к
тому или иному классу
В
зависимости от способа описания объектов различают дискриминантные
, логические и
синтаксические методы распознавания
В

21 данной лабораторной работе изучаются простейшие дискриминантные методы
В
дискриминантном распознавании образов объекты представляются в
виде векторов
Каждый из компонентов этих векторов рассматривается как признак с
вещественным значением
, а
сам вектор называется вектором признаков
Решающим правилом называется правило
, которое по вектору признаков
, описывающих объект
, позволяет определить соответствующий данному объекту класс
Задача распознавания образов заключается в
восстановлении решающего правила по совокупности примеров
– обучающей выборке
, состоящей из векторов признаков
, для каждого из которых задан также соответствующий класс
Итак
, пусть обучающая выборка состоит из
M пар
i
i
α
,
x
, где
i
x
– образ объекта
(
вектор признаков
), а
i
α
обозначает класс
, к
которому данный объект принадлежит
На основе этой обучающей выборки требуется построить решающее правило
)
(
x
ϕ
, которое для произвольного образа
x
будет определять номер наиболее подходящего класса
В
данной работе рассматривается случай двух классов
Метод
эталонных
образов
Метод эталонных образов
– это один из эвристических методов построения решающих правил
В
основу этого метода положена идея
, которая заключается в
том
, что некоторая совокупность объектов
, объединенных в
отдельный класс
, может быть представлена одним или несколькими эталонными объектами
Эти эталонные объекты являются наиболее типичными представителями класса
Типичность эталонного объекта означает
, что он в
среднем максимально похож на все объекты класса
Поскольку сходство двух объектов может трактоваться как величина
, противоположная расстоянию между ними
, то эталон
– это объект
, для которого минимально среднее расстояние до других объектов
Пусть в
обучающей выборке первому классу соответствует
M
1
элементов
i
,
1
x
, а
второму классу
– M
2
элементов
i
,
2
x
Тогда эталонные образы для каждого из классов могут быть определены как
∑
=
=
1 1
,
1 1
1
,
0 1
M
i
i
M
x
x
,
∑
=
=
2 1
,
2 2
2
,
0 1
M
i
i
M
x
x
(8)
Классы, однако, могут обладать разными свойствами. Простейшим свойством является характерный размер класса, который вычисляется как
∑
=
−
=
1 1
2
,
1 1
,
0 1
1 1
M
i
i
M
r
x
x
,
∑
=
−
=
2 1
2
,
2 2
,
0 2
2 1
M
i
i
M
r
x
x
(9)

22
Тогда для классификации нового образа
x
используется следующая решающая функция
:
2 2
,
0 1
1
,
0
)
(
r
r
x
x
x
x
x
−
−
−
=
κ
(10)
Если значение этой функции отрицательное
, то образ относится к
первому классу
, в
противном случае
– ко второму
Разделяющая поверхность для двух классов задается уравнением
0
)
(
=
κ
x
Метод
ближайшего
соседа
Другой широко распространенный эвристический метод распознавания
– метод ближайшего соседа
(
или его обобщение
– метод
k- ближайших соседей
).
Идея этого метода крайне проста
: новый образ относится к
тому классу
, к
которому он ближе
При этом расстояние от образа до класса определяется как расстояние от образа до ближайшего элемента класса
Тогда на основе обучающей выборки
i
i
α
,
x
, i=1,…,M, может быть построено следующее решающее правило
:
i
i
x
x
x
−
α
=
ϕ
min arg
)
(
(11)
В
соответствии с
данным решающим правилом просматривается вся обучающая выборка
, в
ней находится образ
, расположенный наиболее близко к
данному и
устанавливается
, к
какому классу он принадлежит
(
это известно
, поскольку он находится в
обучающей выборке
).
Этот класс и
приписывается новому образу
Экспериментальная

23 3.
Варьируя обучающую выборку
, определить проценты правильного распознавания каждого из методов
Обучающую выборку следует изменять следующим образом
: добавлять и
исключать из нее элементы
, чтобы менялся размер выборки
, вносить в
обучающую выборку ошибки
(
для нескольких элементов указывать неправильный класс
).
4.
Для определения скорости работы каждого из методов следует варьировать размер обучающей выборки
Для формирования обучающих выборок больших размеров допустимо многократно дублировать содержимое исходной обучающей выборки
Для определения времени классификации нового образа следует многократно
(
в цикле
) вызывать классифицирующую процедуру и
оценивать время для такого многократного вызова
, после чего делить полученное общее время на число вызовов
5.
Проанализировать полученные результаты
Определить
, как влияют ошибки в
обучающей выборке на каждый из методов
, при каких размерах обучающей выборки у
какого из методов больше процент правильного распознавания
(
и при какой форме областей
, занимаемых классами
), как влияет размер обучающей выборки на время классификации нового образа в
каждом из методов
Сделать выводы по работе
Литература
1.
Потапов
,
А
.
С
.
Распознавание
образов
и
машинное
восприятие
:
общий
подход
на
основе
принципа
минимальной
длины
описания
/
А
С
Потапов
. –
СПб
.:
Политехника
, 2007. –
С
. 135-138, 152-155.
2.
Ту
,
Дж
.
Принципы
распознавания
образов
/
Дж
Ту
,
Р
Гонсалес
–
М
.:
Мир
, 1978. –
С
. 90-98.
Вопросы
для
самопроверки
:
1.
К
какому типу методов распознавания относятся методы ближайшего соседа и
эталонных образов
, и
что
, на ваш взгляд
, это означает
?
2.
Какова форма разделяющей поверхности в
методе эталонных образов
?
3.
Какова форма разделяющей поверхности в
методе ближайшего соседа
?
4.
Работа какого из этих двух методов будет в
большей степени нарушена
, если пространство признаков сильно растянуть в
направлении одного из признаков
, оставив остальные направления неизменными
?
5.
В
каком из двух методов время классификации нового образа зависит от размера обучающей выборки
?
6.
Какой из двух методов более чувствителен к
ошибкам в
обучающей выборке
?
Вариант
2

24
Задание
по
работе
:
1.
Изучить теоретическую часть работы
2.
Реализовать метод решающих функций
3.
Путем варьирования обучающей выборки определить влияние следующих факторов на вероятности правильного распознавания
: наличие в
обучающей выборке выбросов
, размер обучающей выборки
, форма областей
, занимаемых классами в
пространстве признаков
Теоретическая
часть
Постановку задачи дискриминантного распознавания образов см в
теоретической части первого варианта выполнения работы
Здесь будет рассмотрен только сам метод решающих функций
Решающей
функцией
)
(x
κ
для двух классов
Α
∈
2 1
, a
a
называется такая функция
R
X
→
κ
:
, что
0
)
(
>
κ
x
, если образ
x
принадлежит классу
1
a , и
0
)
(
<
κ
x
, если образ
x
принадлежит классу
2
a .
Обычно рассматриваются не произвольные решающие функции
, а
лишь функции
, относящиеся к
некоторому параметрическому семейству
, элементы которого
)
,
(
w
x
κ
определяются вектором параметров
)
,...,
(
1
n
w
w
=
w
, где
n – количество параметров
Выбор конкретных значений параметров
i
w соответствует выбору решающей функции
Тогда решение задачи распознавания образов сводится к
определению оптимальных значений параметров по обучающей выборке
Мы рассматриваем задачу построения решающих функций для случая двух классов
1
a и
2
a .
Как и
раньше
, в
задаче распознавания имеются исходные данные
:
(
)
)
,
(
),...,
,
(
),
,
(
2 2
1 1
M
M
A
A
A
D
x
x
x
=
– обучающая выборка из
M элементов
, в
которой
N
i
R
∈
x
– образы
, представленные
N- компонентными векторами признаков
, а
{
}
2 1
, a
a
A
i
∈
– соответствующие им классы
Важное параметрическое семейство составляют
линейные
решающие
функции
Поиск линейных решающих функций проще как с
теоретической
, так и
с практической точки зрения
, а
классификаторы
, построенные на их основе
, являются также и
наиболее эффективными по отношению к
требуемым вычислительным ресурсам
Линейные решающие функции задаются следующим образом
:
x
w
w
x
′
=
+
+
+
+
=
κ
+
1 2
2 1
1
)
,
(
N
N
N
w
x
w
x
w
x
w
,
(12) где
T
N
x
x
x
)
1
,
,...,
,
(
2 1
=
′
x
– пополненный вектор признаков
, а
)
,...,
,
(
1 2
1
+
=
N
w
w
w
w
– вектор весов
, который требуется определить по