Технологии искусственного интеллекта. Упрощенная структура экспертных систем

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

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

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

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

· которые недостаточно хорошо понимаются или изучены;

· для которых нет четко заданных алгоритмических решений;

· которые могут быть исследованы с помощью механизма символических рассуждений.

Специфика ЭС состоит в том, что они используют:

· механизм автоматического рассуждения (вывода);

· а также " слабые методы", такие как поиск или эвристики.

Основными требованиями к ЭС являются:

1) использование знаний, связанных с конкретной предметной областью;

2) возможность приобретение знаний от эксперта;

3) определение реальной и достаточно сложной задачи;

4) наделение системы способностями эксперта.

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

· имеют огромный багаж знаний о конкретной предметной области;

· имеют большой опыт работы в этой области;

· и что самое главное - умеют точно сформулировать, правильно поставить и решить задачу.

Экспертные системы призваны заменить специалистов в конкретной предметной области, то есть позволить решить задачу без эксперта.

Любая система состоит из некоторой совокупности основных блоков и компонентов, между которыми существуют определенные взаимодействия. Не исключением являются и экспертные системы. Упрошенная базовая структура ЭС имеет следующий вид:

Для успешного выполнения функций, возлагаемых на экспертные системы, в их составе необходимы, как минимум пять компонентов:

· База знаний реализует функции представления знаний в конкретной предметной области и управление ими.

· Механизм логических выводов выполняет логические выводы на основании знаний, имеющихся в базе знаний.

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

· Модуль приобретения знаний необходим для получения знаний от эксперта, поддержки базы знаний и дополнения ее при необходимости.

· Модуль ответов и объяснений формирует заключение экспертной системы и представляет различные комментарии, прилагаемые к заключению, а так­же объясняет мотивы заключения.

Следует особо подчеркнуть важность механизма объяснений в составе экспертных систем, так как:

· без него пользователю трудно будет понять заключение, полученное при консультации или решении какого-либо вопроса;

· этот механизм важен для эксперта, он позволяет определить, как работает система и выяснить, как используются предоставленные им знания.

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

База знаний содержит факты и правила. Факты - это фразы без условий, они содержат утверждения, которые всегда абсолютно верны. Правила содержат утверждения, истинность которых зависит от некоторых условий, образующих тело правила.

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

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

Одной из основных проблем, характерных для СОЗ, является проблема представления знаний. Это объясняется тем, что форма представления знаний оказывает существенное влияние на характеристики и свойства системы.

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

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

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

· модель на базе логики;

· продукционная модель;

· модель на базе семантических сетей;

· модель, основанная на использовании фреймов и др.

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

Система знаний отображается совокупностью таких формул и, представленная в ЭВМ, образует БЗ. Формулы неделимы и при модификации БЗ могут лишь добавляться или удаляться. Логические методы обеспечивают развитый аппарат вывода новых фактов из тех, которые явно представлены в БЗ. Основным примитивом манипуляции знаниями является операция вывода.

Технологии искусственного интеллекта. Основные понятия распознавания образов

Пусть x ∈ Χ – описание объекта (или образ), а Χ – пространство описаний (множество всех возможных образов). В дискриминантном подходе к распознаванию пространство X=R^N – пространство признаков, а образ x – N-компонентный вектор признаков: x=(x₁, …, x_N)

Через A=(a₁, …, a_d) обозначим некоторое множество, состоящее из d элементов, 1< d < +∞, где a_i – i-й класс образов, а Α – множество классов (также называемое алфавитом классов).

Решающим правилом назовем отображение ϕ: Α → Χ, которое ставит в соответствие элементу пространства описаний класс из заданного множества.

Решающее правило может также задаваться неявно через целевую функцию ρ: Χ × Α → R, определяющую степень соответствия (например, в форме вероятности) между описанием объекта и каждым классом.

Решающее правило можно определить через целевую функцию как

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

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

Задача классификации (распознавания без обучения) заключается в определении по описанию объекта того класса, к которому он принадлежит. При этом решающие правила считаются известными. Иными словами, распознавание единичного образа (далее будет использоваться термин «классификация» во избежание путаницы) сводится к применению решающего правила ϕ к данному образу x.

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

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

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

Решающей функцией κ (x) для двух классов a1, a2 ∈ Α назовем такую функцию κ: X → R, что κ (x)> 0, если образ x принадлежит классу a1, и κ (x)< 0, если образ x принадлежит классу a2.

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

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

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

В случае нескольких классов возможны различные определения решающей функции. Один из способов заключается в том, чтобы непосредственно воспользоваться определением для случая двух классов и ввести d² решающих функций κ _ij(x) (где d – это количество классов), каждая из которых разделяет два разных класса a_i, a_j ∈ Α. Для таких решающих функций верно κ _ij(x) > 0, если образ x не может принадлежать классу a_j, и κ _ij(x)< 0, если образ не может принадлежать классу a_i. Решающее правило примет форму

ϕ (x)= a_i⇔ ∀ j κ _ij(x)> 0.

Поскольку верно равенство κ _ij(x) = -κ _ij(x), а функции κ _ij(x) лишены смысла, всего требуется построить d(d -1)/2 решающих функций.

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

ϕ (x)= a_i⇔ κ _j(x)< 0.

Естественно, должно выполняться условие κ _i(x)> 0 ⇒ ∀ j: j≠ i κ _j(x)< 0.

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

В общем случае решающую функцию можно определить как функцию, разделяющую два подмножества множества классов. Видно, что это определение обобщает оба подхода: в первом производится разделение таких множеств, как {a_i} и {a_j}, а во втором случае – { a_i } и A\{a_i}. Разделение подмножеств классов может позволить еще уменьшить количество решающих функций, но их число не может быть меньше [log₂ d].

Для простоты будем рассматривать случай двух классов. В задаче распознавания образов в качестве исходных данных выступает обучающая выборка: (x₁, A₁), (x₂, A₂),..., (x_M, A_M), где x∈ R^N и A_i∈ {a1, a2}, состоящая из M элементов. На основе этих данных требуется построить решающее правило ϕ: Α → Χ или решающую функцию κ (x).

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

В основу метода эталонных образов положена идея, которая заключается в том, что некоторая совокупность объектов, объединенных в отдельный класс, может быть представлена одним или несколькими эталонными объектами. Эти эталонные объекты являются наиболее типичными представителями класса. Типичность эталонного объекта означает, что он в среднем максимально похож на все объекты класса. Поскольку сходство двух объектов может трактоваться как величина, противоположная расстоянию между ними в пространстве описаний (образов), то эталон – это объект, для которого минимально среднее расстояние до других объектов.

Пусть в обучающей выборке первому классу соответствует M1 элементов x_{1, i}, а второму классу – M2 элементов x_2, i. Тогда эталонные образы для каждого из классов могут быть определены как оценки математических ожиданий (средние):

.

Классы, однако, могут обладать разными свойствами. Простейшим свойством является компактность класса в пространстве признаков. Этот параметр может быть оценен через средне-квадратичное отклонение (СКО):

.

Тогда для классификации нового образа x используется следующая решающая функция:

.

Если значение этой функции отрицательное, то образ относится к первому классу, в противном случае – ко второму. Разделяющая поверхность для двух классов задается уравнением κ (x)=0.

Другой широко распространенный эвристический метод распознавания – метод ближайшего соседа (или его обобщение – метод k ближайших соседей). Идея этого метода крайне проста: новый образ относится к тому классу, к которому он ближе. При этом расстояние от образа до класса определяется как расстояние от образа до ближайшего элемента класса.

Тогда на основе обучающей выборки x_i, α _i, i=1, …, M, может быть построено следующее решающее правило:

.

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

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

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

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

.

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

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

Однако мера сходства может задаваться в параметрическом виде (с автоматическим выбором значений параметров). Наиболее типичный пример – расстояние Махаланобиса, которое имеет вид

s(x, y)= (x-y)^TC^-1(x-y),

где C – некоторая матрица, элементы которой и являются параметрами данной функции расстояния. На практике в качестве этой матрицы берется ковариационная матрица распределения векторов данного класса.

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

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

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