Модели распознавания_ основанные на различных способах обучения. Часть 2 (1185316), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Определение 3.Пусть - признаковое описание объекта . Набор называется представительным набором для класса , если для произвольной строки таблицы соответствующей объекту

такое, что существует такое из множества , что .

Определение 4. Представительный набор называется тупиковым, если никакое его собственное подмножество представительным набором не является.

На этапе обучения для каждого из классов по таблице ищется множество всевозможных тупиковых представительных наборов. Обозначим через - множество всевозможных представительных наборов для класса . Предположим, что нам требуется распознать объект с описанием . Пусть - представительный набор. Функция равна 1, если , и равна 0 в противном случае.

Оценка за класс вычисляется по формуле

.

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

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

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

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

Аналогичным образом вводится модифицированное определение представительного набора.

Главным требованием при выборе - порогов является достижение максимальной отделимости объектов разных классов при сохранении сходства внутри классов.

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

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

Существует много вариантов моделей данного типа. Причём конкретный вид модели определяется выбранными способами задания различных её элементов. Рассмотрим основные составляющие модели

Задание системы опорных множеств. Под опорными множествами модели АВО понимается наборы признаков, по которым осуществляется сравнение распознаваемых и эталонных объектов. Примером системы опорных множеств является множество тупиковых тестов. Система опорных множеств некоторого алгоритма может задаваться через систему подмножеств множества или через систему характеристических бинарных векторов.

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

Данный результат является обоснованием выбора в качестве системы опорных векторов всевозможных наборов, включающих фиксированное число признаков или

. Оптимальное значение находится в процессе обучения или задаётся экспертом. Другой часто используемой системе опорных множеств

соответствует множество всех подмножеств за исключением пустого множества.

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

Фрагмент описания объекта называется - частью объекта _. Под функцией близости понимается функция от соответствующих -частей сравниваемых объектов, принимающая значения 1 (объекты близки) или 0 (объекты удалены).

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

Примеры функций близости.

1. , если при произвольном , при котором , всегда выполняется неравенство . , если существует такое , что одновременно и .

2. Пусть - скалярный пороговый параметр. Функция , если выполняется неравенство . В противном случае .

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

A) ,

B) , где - параметр, характеризующий информативность опорного множества с характеристическим вектором .

С) , где - параметр, характеризующий информативность эталона , параметры характеризуют информативность отдельных признаков.

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

Общая оценка за класс вычисляется как сумма оценок по опорным множествам из системы :

(1)

Наряду с формулой (1) используется формула

(2)

Использование взвешивающих параметров позволяет регулировать доли правильно распознанных объектов .

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

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

Тогда оценка по формуле (1) принимает вид

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

Предположим, что система опорных множеств удовлетворяет условию . Очевидно, что число опорных множеств, удовлетворяющих условию , равно . Откуда следует, что . Следовательно оценка по формуле (1) может быть записана в виде

. (3)

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

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

для распознавания объектов , принадлежащих классам . При правильного распознавания объекта должна выполняться система неравенств

где .

В наиболее общем из приведённых выше вариантов модели АВО обучение может быть сведено к поиску максимальной совместной подсистемы системы неравенств

Поиск максимальной совместной подсистемы системы (2) может производиться с использованием эвристического релаксационного метода, аналогичного тому, что был использован при обучении алгоритма «Линейная машина».

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

Характеристики

Список файлов лекций