![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Технологии искусственного интеллекта. Упрощенная структура экспертных систем
Системы, основанные на знаниях (СОЗ) — это системы программного обеспечения, основными структурными элементами которых являются база знаний и механизм логических выводов. Среди СОЗ можно выделить интеллектуальные информационно-поисковые системы и экспертные системы (ЭС). Экспертные системы — это сложные программные комплексы, аккумулирующие знания специалистов в конкретных предметных областях и тиражирующие этот эмпирический опыт для консультаций менее квалифицированных пользователей. Они работают таким образом, что имитируют образ действий человека-эксперта, и существенно отличаются от точных, хорошо аргументированных алгоритмов. Они не похожи на математические процедуры большинства традиционных разработок. Области применения систем, основанных на знаниях, весьма разнообразны: бизнес, производство, военные приложения, медицина, социология, геология, космос, сельское хозяйство, управление, юриспруденция и др. Если при традиционном процедурном программировании компьютеру необходимо сообщить что и как он должен делать, то общим для экспертных систем является то, что они имеют дело со сложными проблемами: · которые недостаточно хорошо понимаются или изучены; · для которых нет четко заданных алгоритмических решений; · которые могут быть исследованы с помощью механизма символических рассуждений. Специфика ЭС состоит в том, что они используют: · механизм автоматического рассуждения (вывода); · а также " слабые методы", такие как поиск или эвристики. Основными требованиями к ЭС являются: 1) использование знаний, связанных с конкретной предметной областью; 2) возможность приобретение знаний от эксперта; 3) определение реальной и достаточно сложной задачи; 4) наделение системы способностями эксперта. Эксперты - это квалифицированные специалисты в своих областях деятельности - финансисты, экономисты, врачи, адвокаты и т.д. Эксперты нужны тогда, когда задача плохо изучена или для ее решения нет известных методов или теорий. Общим для всех специалистов-экспертов является то, что они: · имеют огромный багаж знаний о конкретной предметной области; · имеют большой опыт работы в этой области; · и что самое главное - умеют точно сформулировать, правильно поставить и решить задачу. Экспертные системы призваны заменить специалистов в конкретной предметной области, то есть позволить решить задачу без эксперта. Любая система состоит из некоторой совокупности основных блоков и компонентов, между которыми существуют определенные взаимодействия. Не исключением являются и экспертные системы. Упрошенная базовая структура ЭС имеет следующий вид:
Для успешного выполнения функций, возлагаемых на экспертные системы, в их составе необходимы, как минимум пять компонентов: · База знаний реализует функции представления знаний в конкретной предметной области и управление ими. · Механизм логических выводов выполняет логические выводы на основании знаний, имеющихся в базе знаний. · Пользовательский интерфейс необходим для получения и модификации знаний эксперта, а также для правильной передачи ответов пользователю, иначе пользоваться системой крайне неудобно. · Модуль приобретения знаний необходим для получения знаний от эксперта, поддержки базы знаний и дополнения ее при необходимости. · Модуль ответов и объяснений формирует заключение экспертной системы и представляет различные комментарии, прилагаемые к заключению, а также объясняет мотивы заключения. Следует особо подчеркнуть важность механизма объяснений в составе экспертных систем, так как: · без него пользователю трудно будет понять заключение, полученное при консультации или решении какого-либо вопроса; · этот механизм важен для эксперта, он позволяет определить, как работает система и выяснить, как используются предоставленные им знания. Язык представления знаний, используемый для разработки ЭС, называется языком разработки ЭС, а система программного обеспечения, включающая указанные выше функции, называется инструментом для разработки ЭС или оболочкой ЭС. База знаний содержит факты и правила. Факты - это фразы без условий, они содержат утверждения, которые всегда абсолютно верны. Правила содержат утверждения, истинность которых зависит от некоторых условий, образующих тело правила. Факты содержат краткосрочную информацию в том смысле, что они могут меняться, например, в ходе время консультации. Правила представляют собой долговременную информацию о том, как порождать новые факты или гипотезы из того, что сейчас известно. Основное различие от обычной методики использования БД состоит в том, что БЗ обладает большими «творческими» возможностями. Факты в БД обычно пассивны: они там либо там есть, либо их нет. База знаний, с другой стороны, активно пытается пополнить недостающую информацию. Одной из основных проблем, характерных для СОЗ, является проблема представления знаний. Это объясняется тем, что форма представления знаний оказывает существенное влияние на характеристики и свойства системы. Для возможности оперирования знаниями из реального мира с помощью компьютерной техники, необходимо осуществить их моделирование (по аналогии с построением концептуальных и логических моделей в БД). При этом необходимо отличать знания, предназначенные для обработки компьютером от знаний, используемых человеком. При проектировании модели представления знаний следует учитывать такие факторы, как однородность представления знаний и простота их понимания. Однородность представления приводит к упрощению механизма управления логическим выводом и управлением знаниями. Простота понимания предполагает доступность понимания представления знаний и экспертам, и пользователем системы. В противном случае затрудняется приобретение знаний и их оценка. Однако выполнить эти требования в равной степени, как для простых, так и сложных задач довольно трудно. В настоящее время для представления знаний используют следующие виды моделей: · модель на базе логики; · продукционная модель; · модель на базе семантических сетей; · модель, основанная на использовании фреймов и др. Основная идея логического подхода состоит в том, чтобы рассматривать всю систему знаний необходимую для решения прикладных задач, как совокупность фактов (утверждений). Факты представляются как формулы в некоторой логике (первого или высшего порядка, многозначной, нечеткой или др.). Система знаний отображается совокупностью таких формул и, представленная в ЭВМ, образует БЗ. Формулы неделимы и при модификации БЗ могут лишь добавляться или удаляться. Логические методы обеспечивают развитый аппарат вывода новых фактов из тех, которые явно представлены в БЗ. Основным примитивом манипуляции знаниями является операция вывода.
Технологии искусственного интеллекта. Основные понятия распознавания образов
Пусть x ∈ Χ – описание объекта (или образ), а Χ – пространство описаний (множество всех возможных образов). В дискриминантном подходе к распознаванию пространство X=RN – пространство признаков, а образ x – N-компонентный вектор признаков: x=(x1, …, xN) Через A=(a1, …, ad) обозначим некоторое множество, состоящее из d элементов, 1< d < +∞, где ai – i-й класс образов, а Α – множество классов (также называемое алфавитом классов). Решающим правилом назовем отображение ϕ: Α → Χ, которое ставит в соответствие элементу пространства описаний класс из заданного множества. Решающее правило может также задаваться неявно через целевую функцию ρ: Χ × Α → R, определяющую степень соответствия (например, в форме вероятности) между описанием объекта и каждым классом. Решающее правило можно определить через целевую функцию как Во многих практических задачах вводится матрица потерь Lij, определяющая стоимость ошибочного отнесения объекта класса i к классу j, а задача формулируется, как минимизация ожидаемых потерь в ходе классификации. Однако учет потерь при классификации нужен лишь при принятии решения, к какому классу отнести данный объект, но не на процедуру вывода вероятностей принадлежности объекта тому или иному классу. Конечно, в подходах, не опирающихся на теорию вероятностей, матрица потерь непосредственно влияет на решающее правило, но суть подходов не меняется и в том случае, если эта матрица не используется. В связи с этим, для простоты изложения матрица потерь будет опускаться. Теперь сформулируем задачи распознавания образов как задачи машинного обучения. В зависимости от имеющейся информации и характера обучающей выборки можно выделить следующие задачи. Задача классификации (распознавания без обучения) заключается в определении по описанию объекта того класса, к которому он принадлежит. При этом решающие правила считаются известными. Иными словами, распознавание единичного образа (далее будет использоваться термин «классификация» во избежание путаницы) сводится к применению решающего правила ϕ к данному образу x. Собственно задача распознавания образов (обучения с учителем) заключается в построении решающего правила, которое считалось известным в задаче классификации. В качестве исходной информации здесь выступает обучающая выборка, каждый элемент которой представляет собой описание объекта (задача) и соответствующий ему класс (ответ). В задаче кластеризации (группирования) количество исходной информации меньше, а именно, в ней не определено пространство классов Α, которое и требуется сформировать, опираясь на заданный набор образов, не разбитых на классы в отличие от задачи распознавания с учителем. Иными словами, здесь в обучающей выборке имеется только набор задач, предоставленных без правильных ответов. Задача классификации в рамках дискриминантного подхода является очень простой, коль скоро известно решающее правило. Обычно, однако, решающее правило здесь представляется в специфической форме. Введем следующее определение. Решающей функцией κ (x) для двух классов a1, a2 ∈ Α назовем такую функцию κ: X → R, что κ (x)> 0, если образ x принадлежит классу a1, и κ (x)< 0, если образ x принадлежит классу a2. На основе подобной решающей функции не составляет проблем сформировать решающее правило. Преимущество решающих функций в том, что у них не только аргументы, но и принимаемые значения имеют непрерывный характер, что позволяет применять к ним обширный аппарат математического анализа. Уравнение κ (x) = 0 задает поверхность, разделяющую два класса и называемую дискриминантной поверхностью. Поскольку при принятии решения об отнесении образа к тому или иному классу абсолютные значения функции κ (x) внутри классов роли не играют (то есть не имеет значения, как именно распределены образы внутри классов), всю необходимую информацию о том, как следует разделять классы, несет именно эта поверхность, описывающая границу между классами в пространстве признаков. Это и объясняет название дискриминантного подхода. Разделяющая поверхность удобна для принятия решений при классификации образов. Однако класс может быть задан не через его границы с другими классами, а как отдельная область в пространстве признаков. Если области, соответствующие двум классам, не пересекаются, то эти классы называются разделимыми в данном пространстве признаков. Иными словами, разделимость классов означает, что для них существует решающая функция, корректно классифицирующая любой образ. Напротив, если области пересекаются, то такой функции не существует, и классы называются неразделимыми. В случае нескольких классов возможны различные определения решающей функции. Один из способов заключается в том, чтобы непосредственно воспользоваться определением для случая двух классов и ввести d2 решающих функций κ ij(x) (где d – это количество классов), каждая из которых разделяет два разных класса ai, aj ∈ Α. Для таких решающих функций верно κ ij(x) > 0, если образ x не может принадлежать классу aj, и κ ij(x)< 0, если образ не может принадлежать классу ai. Решающее правило примет форму ϕ (x)= ai⇔ ∀ j κ ij(x)> 0. Поскольку верно равенство κ ij(x) = -κ ij(x), а функции κ ij(x) лишены смысла, всего требуется построить d(d -1)/2 решающих функций. Другой способ заключается в отделении данного класса одновременно ото всех остальных. Для этого необходимо d дискриминантных функций κ i(x), а решающее правило примет форму ϕ (x)= ai⇔ κ j(x)< 0. Естественно, должно выполняться условие κ i(x)> 0 ⇒ ∀ j: j≠ i κ j(x)< 0. Второй вариант кажется предпочтительнее, так как требует меньшего количества решающих функций. Однако построение таких решающих функций сложнее, особенно если они выбираются из простых семейств. В общем случае решающую функцию можно определить как функцию, разделяющую два подмножества множества классов. Видно, что это определение обобщает оба подхода: в первом производится разделение таких множеств, как {ai} и {aj}, а во втором случае – { ai } и A\{ai}. Разделение подмножеств классов может позволить еще уменьшить количество решающих функций, но их число не может быть меньше [log2 d]. Для простоты будем рассматривать случай двух классов. В задаче распознавания образов в качестве исходных данных выступает обучающая выборка: (x1, A1), (x2, A2),..., (xM, AM), где x∈ RN и Ai∈ {a1, a2}, состоящая из M элементов. На основе этих данных требуется построить решающее правило ϕ: Α → Χ или решающую функцию κ (x). Задача обучения сводится к заданию адекватного критерия качества результата обучения (в данном случае – критерия качества решающей функции). Два наиболее широко распространенных эвристических метода – это метод эталонных образов и метод ближайшего соседа. В основу метода эталонных образов положена идея, которая заключается в том, что некоторая совокупность объектов, объединенных в отдельный класс, может быть представлена одним или несколькими эталонными объектами. Эти эталонные объекты являются наиболее типичными представителями класса. Типичность эталонного объекта означает, что он в среднем максимально похож на все объекты класса. Поскольку сходство двух объектов может трактоваться как величина, противоположная расстоянию между ними в пространстве описаний (образов), то эталон – это объект, для которого минимально среднее расстояние до других объектов. Пусть в обучающей выборке первому классу соответствует M1 элементов x1, i, а второму классу – M2 элементов x2, i. Тогда эталонные образы для каждого из классов могут быть определены как оценки математических ожиданий (средние):
Классы, однако, могут обладать разными свойствами. Простейшим свойством является компактность класса в пространстве признаков. Этот параметр может быть оценен через средне-квадратичное отклонение (СКО):
Тогда для классификации нового образа x используется следующая решающая функция:
Если значение этой функции отрицательное, то образ относится к первому классу, в противном случае – ко второму. Разделяющая поверхность для двух классов задается уравнением κ (x)=0. Другой широко распространенный эвристический метод распознавания – метод ближайшего соседа (или его обобщение – метод k ближайших соседей). Идея этого метода крайне проста: новый образ относится к тому классу, к которому он ближе. При этом расстояние от образа до класса определяется как расстояние от образа до ближайшего элемента класса. Тогда на основе обучающей выборки xi, α i, i=1, …, M, может быть построено следующее решающее правило:
В соответствии с данным решающим правилом просматривается вся обучающая выборка, в ней находится образ, расположенный наиболее близко к данному и устанавливается, к какому классу он принадлежит (это известно, поскольку он находится в обучающей выборке). Этот класс и приписывается новому образу. Метод ближайшего соседа весьма чувствителен к выбросам, то есть тем образам обучающей выборки, для которых указаны ошибочные классы. В методе k-ближайших соседей выбирается k образов обучающей выборки, наиболее близко расположенных к классифицируемому образу, и определяется, к какому классу относится больше всего из них. Поскольку выбросов, как правило, значительно меньше, чем правильных примеров, можно надеяться, что среди k ближайших соседей выбросов будет мало, и они не окажут влияния на результат классификации. У метода эталонных образов также имеются модификации, в частности, в одной из них каждый класс может описываться несколькими эталонами, а классификация осуществляется так же, как и в методе ближайшего соседа, но вместо образов выборки ищется ближайший эталон. В предельном случае каждый образ выборки может выступать в роли эталона и метод эталонных образов превратится в обычный метод ближайшего соседа. Таким образом, эти два метода – два крайних случая классификации с использованием функций расстояния. Оба метода могут быть расширены за счет использования неевклидовой метрики. В общем случае используется произвольная функция расстояния s(x, y). В методе ближайшего соседа решающее правило просто преобразуется к виду:
Помимо евклидового расстояния могут использоваться и другие функции расстояния, например, нормированное скалярное произведение. Выбор меры сходства основывается на знании природы входных данных. Например, если объектами являются прямые линии, а векторы признаков – это векторы, описывающих их направление, то использовать в качестве меры сходства угол между ними будет предпочтительнее, чем евклидово расстояние. Если же рассматриваются отрезки прямых линий, то необходимо также учитывать и различие их длин, что приведет к специфической для данных объектов мере сходства. Выбор меры сходства обычно задается человеком, а не осуществляется автоматически. Однако мера сходства может задаваться в параметрическом виде (с автоматическим выбором значений параметров). Наиболее типичный пример – расстояние Махаланобиса, которое имеет вид s(x, y)= (x-y)TC-1(x-y), где C – некоторая матрица, элементы которой и являются параметрами данной функции расстояния. На практике в качестве этой матрицы берется ковариационная матрица распределения векторов данного класса. В общем случае расстоянию Махаланобиса соответствует некоторый эллипс, описанный вокруг класса образов и учитывающий вытянутость и ориентацию этого класса. Таким образом, расстояние Махаланобиса является более общим, чем евклидово расстояние, даже если в последнем учитываются размеры классов. Однако обоснование выбора в качестве матрицы C ковариационной матрицы не может быть осуществлено в рамках метода эталонных образов, что показывает ограниченность эвристических методов и необходимость более строго математического анализа проблемы. Эвристичность описанных методов заключается в предположении, согласно которому близко расположенные образы, вероятнее всего принадлежат одному и тому же классу. Даже использование неевклидовой метрики не нарушает этого предположения. Стоит отметить, что в методе ближайшего соседа, по сути, производится просто запоминание частных примеров без какого-либо обобщения. Работоспособность метода ближайшего соседа обеспечивается только предположением о совпадении классов у близко расположенных образов. Эта эвристика присутствует и в других дискриминантных методах распознавания: предположение о существовании разделяющей поверхности означает, что решающее правило непрерывно везде, кроме границы классов, имеющей размерность на 1 меньше, чем размерность пространства признаков. Таким образом, неявное предположение о непрерывности является мощнейшей эвристикой, но в то же время оно накладывает и определенные ограничения, которые нужно иметь в виду при проектировании систем распознавания.
|