Содержание к диссертации
Введение
Глава I. Полные замыкания семейств распознающих операторов . 14
1.1. Описание модели алгоритмов в задачах с дискретной обучающей информацией 14
1.2. Доказательство полноты семейства операторов . 20
Глава 2. Синтез корректного алгоритма 33
2.1. Построение базисных операторов в алгебраических замыканиях 33
2.2. Задача разделения множеств 42
Глава 3. Емкостные характеристики модели алгоритмов с дискретной обучающей информацией
3.1. Оценки для емкости линейного замыкания 54
3.2. Емкость алгебраического замыкания конечной степени 66
Литература
- Описание модели алгоритмов в задачах с дискретной обучающей информацией
- Доказательство полноты семейства операторов
- Построение базисных операторов в алгебраических замыканиях
- Емкость алгебраического замыкания конечной степени
Введение к работе
Теория распознавания и классификации образов в последние десятилетия является одной из центральных областей прикладной математики и математической кибернетики. Методы распознавания образов находят применение в важных прикладных задачах технической и медицинской диагностики, геологического и социологического прогнозирования, систем обработки информации и ряда других областей. Большое число появившихся к настоящему времени алгоритмов для решения задач распознавания позволило придать содержательной постановке таких задач четкие математические формулировки, а также определить некоторые общие требования к классам алгоритмов, способных успешно решать эти задачи. Переход от рассмотрения отдельных распознающих алгоритмов к классам или моделям алгоритмов, а в последнее время - к синтезу моделей из заданной совокупности моделей [12 j - привел к исследованию проблемы выбора алгоритмов, удовлетворяющего определенным экстремальным условиям*
Будем под задачей распознавания
Для ряда распространенных моделей распознавания:алгоритмов вычисления оценок, разделения, статистических, потенциальных функций и других алгебраическими методами установлен ряд результатов относительно существования в модели точной распознающей процедуры для произвольной задачи со стандартной информацией [4 J , fllj , [I8J . В работах /26/ , [Z7] изучены общие
- 4 -вопросы, связанные с полнотой и построением экстремальных моделей алгоритмов.
Стандартная начальная информация to представляет совокупность описаний объектов из множества т^М с известной классификацией в пространстве признаков М/Х...х Мм» Для изученных моделей алгоритмов важную роль играет то обстоятельство,что они применяются преимущественно к задачам, в которых множества описаний являются метрическими (или полуметрическими) пространствами с метриками р^т-трн . При этом метрика (в частности, евклидова) может служить мерой сходства распознаваемых объектов и эталонов по отдельным признакам, принимающим значения из некоторого основного континуума. Задачи такого рода будем называть задачами с непрерывной начальной информацией. Для таких задач при задании функции близости, использующей данные метрики и меры точности измерений /7...,п , можно получить богатые параметрические модели распознавания.
С другой стороны, существует ряд прикладных задач, в которых переменные (признаки) принимают дискретные значения. Эти переменные в отличие от шкал интервалов или порядка представляют скорее качественную, номинальную шкалу наименований, чем числительную шкалу. Необходимость в преимущественно дискретных (в частности, бинарных) измерениях появляется во многих практических системах распознавания либо из-за самой сущности задачи,как, например, классификация симптомов в автоматической диагностике заболеваний, либо из-за выбора признаков (при обработке и распознавании изображений, в геологическом прогнозировании и т.д.). Однако, несмотря на практическую важность задач с дискретной информацией существует немного математических средств, пригодных для их решения. В таких задачах возникают значительные трудности
- 5 -при построении точного классификатора. Для дискретных признаков изменение отдельных значений от одного уровня до другого может вызвать значительное изменение объекта. В отличие от непрерывного случая здесь не существует устойчивости, то есть настолько малых изменений переменных, что они оставляют образ неизмененным [дЗ] . В силу этого факта и отсутствия внутренней упорядоченности, трудно описать распределение векторов признаков простыми параметрическими моделями. При статистическом подходе, чтобы получить оценки распределения, приходится накладывать ряд ограничений (попарная независимость признаков). Другие методы, в частности, геометрические (метод ближайших соседей /9у , линейный дискриминант Фишера) трудноприменимы или малоэффективны в силу того,что евклидова метрика,использующаяся в них, не является, вообще говоря,в таких задачах мерой сходства.Можно выделить теорию "главных событий"/33/ и основанную на ней методику для построения дерева решений, чтобы получить множество прототипов для каждой категории образов /32J. Получающийся при этом алгоритм не всегда ведет к оптимальному дереву решений.
Перечисленные методы имеют свою ценность, но оставляют необходимость общего подхода к выделению информации для классификации объектов с дискретными значениями признаков.
Особую роль в задачах распознавания с дискретными переменными играют алгоритмы, принадлежащие различным подсемействам модели вычисления оценок /ізу . Эти алгоритмы отражают ту идею, что сравнение классифицируемых объектов с эталонами должно происходить по определенным образом выделенным группам признаков -опорным множествам, формируемым по начальной информации, которая в дискретном случае задается таблицей обучения. Вводя параметры -веса эталонов и признаков - получаем параметрическую модель, в
которой можно решать экстремальную задачу нахождения оптимального алгоритма. Функция близости при этом определена на каждом подмножестве признаков и принимает только два значения: близость есть, близости нет.
Из класса алгоритмов, содержащихся в описанной модели, следует выделить тестовые алгоритмы, базирующиеся на введенном в [32] понятии теста для дискретных таблиц. Системой опорных множеств в этих алгоритмах служат наборы тупиковых тестов - минимальных описаний, не содержащихся более, чем в одном классе. Тестовые алгоритмы нашли успешное применение в ряде прикладных задач распознавания [&] , /l9j , [20j Проблема создания вычислительных методов, реализующих тестовые алгоритмы, привела к изучению свойств и характеристик тестов для бинарных таблиц /*23j , /29j, /зо] , и построению алгоритмов синтеза совокупности тупиковых тестов (Ш, /7) - таблиц при определенных соотношениях между (П и
п [ю] .
Сходные идеи проявляются в других алгоритмах описанной модели. Так, в известном алгоритме "Кора" [ъ] в качестве опорных множеств выбираются по каждому классу конъюнкции небольшого числа (двух-трех) переменных таким образом, чтобы каждая конъюнкция соответствовала только одному классу. При этом параметры выбираются из множества {о, I, -Ij . Решение, как и в случае тестовых алгоритмов, принимается путем "голосования" полученных по каждому классу оценок принадлежности. Ряд других алгоритмов квазилинейного типа описан в [z] .
Все рассмотренные алгоритмы относятся к числу эвристических алгоритмов распознавания. Их характерной особенностью является то, что они базируются на некоторых интуитивных предположениях о классах решаемых задач, например, о законе распределения объ-
ектов, о геометрическом расположении распознаваемых образов и т.п. Применимость того или иного алгоритма при решении конкретной задачи определяется достаточно высоким качеством распознавания, В то же время эвристические алгоритмы могут неточно классифицировать часть предметов или явлений, подлежащих классификации. Рассматривая совокупность алгоритмов как параметрическую модель, можно выбирать оптимальный алгоритм, решая экстремальную задачу относительно некоторого функционала качества, например, обобщенной ошибки распознавания контрольной выборки. Другой путь связан с переходом к расширениям исходных моделей алгоритмов при помощи алгебраических операций ГIIJ , ГІ2І . Этот способ позволяет избежать решения трудных задач многопараметрической оптимизации. Основной целью настоящей работы явилось исследование вопросов существования и синтеза алгоритмов в алгебраических пополнениях данных моделей, точно решающих произвольную задачу с дискретной обучающей информацией.
Определение. Алгоритм A (Z) называется корректным для задачи 2 ( То, S?> , заданной обучающей информацией То и описаниями предъявленной выборки S ,... tS* % если
где Д/ - значения предикатов Pj (Sl): S/C/',ta<2,...,f;j*f,zt...,6
Каждый алгоритм из рассматриваемых моделей представляется в виде последовательного выполнения двух операторов: А = ВС Здесь В - распознающий оператор, вычисляющий по каждому классу оценки принадлежности объекта, С - решающее правило алгоритма, производящее окончательную классификацию. В работах ГII], [12J сформулирована общая теорема существования корректного алгоритма над классом задач fz < То ,$*>}.
Теорема. Если семейство распознающих операторов {8}
является полным над классом задач f 2 tlo , S Ф >} , то в ли
нейном замыкании «^f {В/ С при произвольном корректном ре
шающем правиле С для любой задачи Z существует
корректный алгоритм А (Z
Опираясь на эту теорему, для исследуемых моделей удается построить корректные алгебраические расширения фиксированной степени и выделить в них конечный класс алгоритмов, содержащий для любой задачи из заданной совокупности алгоритм, правильно решающий эту задачу.
Следующий важный вопрос, который должен быть решен для рассматриваемых алгоритмов - вопрос о гарантированной оценке качества распознавания.
Алгоритм в замыкании, вырабатываемый по обучающей выборке, как указывалось выше, может безошибочно классифицировать элемен-ты контрольного множества S" . Очевидно, если контрольная выборка достаточно большая и представительная, то лучшее решение задачи распознавания сводится к подбору параметров, позволяющих выбрать алгоритм, совершающий как можно меньше ошибок на этой выборке. Для точного анализа ошибок классификации алгоритма применима теория минимизации эмпирического риска Г б J , I 7 J .
Дело в том, что безошибочность на контрольной выборке сама по себе еще не гарантирует алгоритму хорошего качества распознавания других объектов. Задача построения алгоритма, обеспечивающего высокую точность распознавания, может решаться, как правило, в тех случаях, когда искомый алгоритм заведомо принадлежит достаточно узкому классу алгоритмов. Уточнение понятия "достаточно узкий класс" сделано в работе С 7 3 . Основная идея заключается в следующем. Класс алгоритмов характеризуется вели-
- s -
чиной, называемой емкостью класса и показывающей величину объема максимальной выборки объектов, делящейся всеми возможными способами с помощью алгоритмов данного класса. Исследование ряда классов правил показало, что в большинстве случаев емкость класса ограничена и равна числу настраиваемых при обучении параметров Е6І, Г73, f 331. Для классов с конечной емкостью можно установить гарантированные оценки качества распознавания, другими словами, решая непараметрическую задачу распознавания и не пользуясь никакими сведениями о вероятностных распределениях, получить оценки вероятности ошибки распознавания и минимизировать функционал риска.
В работах Г 23 J , 124 і , рассмотрена задача о выполнении достаточных условий равномерной сходимости частот ошибок распознающих алгоритмов к их вероятностям для подклассов алгебраического замыкания алгоритмов вычисления оценок и получены верхние оценки емкости корректных алгебраических замыканий для задач с непрерывной обучающей информацией.
Для рассматриваемых здесь классов задач и алгоритмов свойство ограниченности емкости всегда имеет место (в силу того, что пространство признаков объектов распознавания конечно), но необходимо оценить ее величину для получения гарантированной оценки вероятности ошибки по конечной выборке. Полученные в работе оценки емкости модели исходных алгоритмов являются линейными относительно произведения размерностей векторов параметров. Они также позволяют оценить объем выборки объектов, достаточный для обеспечения алгоритму, оптимальному на этой выборке, заданного качества классификации. Получены оценки емкости алгебраического замыкания фиксированной степени.
Приведем содержание работы по главам. В первой главе да-
- ю -
ется описание двух основных рассматриваемых моделей алгоритмов, предназначенных для решения задач с дискретной обучающей информацией. Рассматриваются параметрические семейства операторов
с т + п, /Т7+Г7+2 вещественными параметрами, соответ-
ственно, и корректное решающее правило С зачисления в класс по максиму*^, оценки. Обучающая информация задается в виде дискретной таблицы обучения Тптв , разбитой на с классов и содержит описания объектов обучения S/,..., Sm&/%/,xAff7 , где каждое Мс является дискретным множеством значений і -го признака.
В параграфе 1.2 исследуется проблема полноты данных моде
лей. Показано, что линейные замыкания не яв
ляются полными. Этот результат подчеркивает особенность рассмат
риваемых алгоритмов по сравнению с моделями, предназначенными
для задач с непрерывной информацией. В последних дополнитель
ные нелинейные параметры <Гу , . .., п , входящие в функцию
близости, "искривляют" пространство операторов, благодаря чему
возможно получить полные линейные замыкания.
Далее сформулирован критерий полноты алгебраического замыкания семейства операторов относительно задачи Z ^ ? і $^У и доказаны теоремы:
Теорема I.I. Пусть для задачи Z КТо, $У выполнено условие разделимости двух произвольных контрольных объ-
U V
ектов S & S по начальной информации Io . Тогда семейство операторов Ы({B-f}U{AJ}) , где AJ - операторы-константы, / = I, 2, ..., , полно относительно Z
/
/ - II -
Теорема 1.2. Если для задачи Е <То, S?> дополнительно выполняется условие неисчезания любого контрольного объекта S1 по каждому классу Kj , / = I, 2, ...,^7 , /=1,2,...,/ ,то ІМ Ів*} полно относительно Z^Io, .f?>
Теорема 1.3. Пусть Ё - пространство признаков, в котором каждый признак входит в некоторый тупиковый тест таблицы обучения Ткт . Если для задачи Z < Io, S*> выполнено условие разделимости двух произвольных контрольных объектов S Ф S по начальной информации Iff , то алгебраическое замыкание семейства тестовых алгоритмов tf{вг} полно относительно
Вторая глава посвящена вопросу синтеза модели, содержащей корректный алгоритм. В параграфе 2.1 произведено прямое построение операторов из алгебраического замыкания, порождающих базис в пространстве вещественных матриц размера ^ х
Степень корректного алгебраического замыкания является ограни-
г*
ченной величиной, зависящей от параметров задачи E^To,S^> Выделено конечное множество алгоритмов в замыкании, содержащее корректный алгоритм и доказана
Теорема 2.1 Корректный алгоритм может быть записан в виде
A(Z)=[E Е BijBUJ)]C,
где fitj є {о,*/} - значения предикатов Pj ( Sl ),
в a j) є ся {в}.
В параграфе 2.2 рассмотрены критерии проверки выполнимости условий полноты. Сформулирована задача разделения исходного информационного массива на два множества с заданными свойствами .
Приводятся случаи, когда решение этой задачи может быть сведено к анализу некоторого графа (при постоянной системе опорных множеств) и нахождению максимального верхнего нуля монотонной булевой функции (если система опорных множеств является монотонной функцией от разбиения).
В третьей главе исследованы емкостные характеристики семейств рассматриваемых алгоритмов. Б параграфе 3.1 емкость модели исходных алгоритмов оценивается через емкость соответствующего линейного замыкания. Получен следующий результат.
Теорема 3.1. Емкость модели не превос-
ходит произведения размерностей векторов параметров )f ~ ()fi,..., Yrr)
и ySW/V,...,/W: и, соответственно,
Рассмотрены также расширения моделей, получаемые при варьировании таблиц обучения. Показывается, что линейные относительно /77/7 оценки для емкости сохраняются.
В параграфе 3.2 оценивается емкость корректного алгебраичес
кого замыкания конечной степени @ . Показано, что
семейство алгоритмов из (Я щ , содержащее корректный алгоритм,
вкладывается в множество алгоритмов разделения гиперплоскостями
в пространстве размерности С^ +s„j , где Ss dt'm Xloj # в ка
честве следствия получена
Теорема 3.2
(G+S-/)! *»**CI/Cg-,)!~
Далее рассмотрено асимптотическое поведение степени 6? алгебраического замыкания как функции параметров таблицы обучения,
- ІЗ -
при котором емкость оценивается величиной бесконечно малой относительно объема пространства объектов распознавания. Пусть
Тогда
h^G, 4 2П* , /?-~ во.
Основное содержание диссертации изложено в публикациях f14J, і 15 J , f16 J . Результаты работы докладывались на II республиканской конференции молодых ученых УАССР, на семинаре в Вычислительном центре АН СССР, на ряде семинаров в Ижевском механическом институте.
Автор выражает искреннюю признательность Ю.И.ЖУРАВЛЕВУ и сотрудникам лаборатории проблем распознавания Вычислительного центра АН СССР за сотрудничество и поддержку. Автор глубоко благодарен научному руководителю Н.И.КАЛЕДИНУ за помощь и постоянное внимание к работе.
Описание модели алгоритмов в задачах с дискретной обучающей информацией
Рассмотрим класс задач распознавания Z , определенных на множестве допустимых объектов Предполагается, что множество М представимо в виде объединения конечного числа подмножеств AV, ..., /, называемых классами: Є А7= U ЛЇ. /=/ Объекты S Є М допускают описания в виде векторов приз наков: S (ХІ г . .., Xn)t где X; Mi - множеству значений і -го признака. Множества Mi - пространства значений признаков - будут предполагаться дискретными: Mi ={0,4} - бинарные признаки, или Mi-{0,4, . d- tj-d- значные признаки, Д 2, / = 1,2,...,/?. Таким образом, каждый допустимый объект 3 является точкой в П -мерном пространстве признаков М/""х М/т
Разбиение К1г. Ке определено не полностью. О классах из вестна стандартная обучающая информация І0(/СІ,...,/Ґ) , задан ная перечислением конечного списка строк описаний некоторых объ ектов каждого класса. Эта информация может быть записана в виде таблицы обучения Тпт = ІІХі/ІЇт л , разбитой на/ классов, содержащей описания объектов Si,. , Sm ЄМ . Множество Sm — і JV,..., f/77} называется обучающей выборкой.
Назовем классификацией некоторое сюрьективное отображение ф / f- -{/C/, ,,.,/Се] Классифицировать элемент S & М значит вычислить (f(S) или, эквивалентно, определить значения предика тов Pj(S. Для элементов обучающей выборки классификация считается известной и задается информаци онной матрицей //Pj(Si)ll fpx , где PjfSi) -/ , если Si Є/Ту ,Pj (Sc)=D , ecmSi /Су , / = 1,2,..., /77 , J = 1,2,..., . Начальная информация Io ( /TV, ..., № ) за дается парой С Тпт l/Py (fi)///7ix ), Таким образом, зада но сужение р отображения (f на конечном множестве
Ставится задача вычисления по исходной обучающей информации Іо (/СІ ,..., /Се) и набору объектов заданных своими описаниями, значений предикатов Pj (J") :sle ку Набор S {St...tSt} называется контрольной выборкой и представляется контрольной таблицей Тпу, = //Xt/7/ф х/7 , Задачу вычисления значений предикатов Pj(S ) , / =, по информации для данной контрольной выборки S обозначим через I Ia,S ) . Алго ритм, решающий задачу Е Z0,Sr? , восстанавливает отоб ражение р на множестве S" и тем самым осуществляет продолжение ip на о/п U S 9
Рассматриваемая ниже модель алгоритмов для решения задач Z является параметрическим подклассом семейства алгоритмов вычисления оценок Г13 J , формализующего идею близости между уже классифицированным объектом и объектом, подлежащим распознаванию. В применении к задачам с дискретной обучающей информацией эти алгоритмы отражают тот основной факт, что сравнение должно проходить по определенным образом выбранным группам признаков, поскольку в отдельных пространствах признаков дискретная метрика, вообще говоря, не является мерой сходства. В модели реализуется двухуровневая схема распознавания: на первом этапе информация, содержащаяся в таблице обучения, используется для построения групп признаков и формирования алгоритма; на втором - происходит выбор параметров, задающих точный вид алгоритма.
Совокупность подмножеств множества признаков по которым производится сравнение классифицируемого объекта с объектами из обучения, назовем системой опорных множеств. В дальнейшем изложении особую роль будут играть алгоритмы с тестовыми опорными множествами jf83 ,основанные на введенном в Г 32 J понятии теста для дискретных таблиц.
Доказательство полноты семейства операторов
Доказательство. Предположим, что условие I не выполняется. Тогда найдутся класс Kj и объект S є о такие, что /j (Se)=0 для любого оператора из і/?2(2,р,р)/. Если не выполняется условие 2 , то существуют объекты J , S Є S такие, что /у (3й) Г/ (Sv) для всех клас сов Кр / = J,2,..., ъ и для любых операторов Вг(?, ,р)
Таким образом, оба допущения противоречат условию полноты Ь( {Вг (г, fr,Р)] относительно Io,S4 . о о Лемма 1.2 утверждает, что условия I и 2 являются необходимыми для полноты Ы{Вг (г,У ,р)7 над Z(Io,St). Эти условия, однако, недостаточны, как показывает следующий пример. Гіусть І 2 и существуют два класса К С , Л/ и два контрольных объекта »Г , f такие, что / (ZSc , vSu)=0 Р (OSi.&S hf для всех объектов обучения St & Кг t Jj є К/ по всем тупиковым тестам CJ є Л . Тогда, как следует из определения теста, для всех объектов обучения S 4 to L/Kj и для любого распознающего оператора 8 (Z, У , р) П (SV -/у (sv), то есть объекты S и S не могут быть разделены отновитель W О О но классов К с и Kj . Таким образом, хотя условия I и - зо выполняются, алгебраическое замыкание (Я {Вг (, jj ,p)} не содержит базиса в пространстве матриц I/(7с ///ах.
Осуществим некоторое изменение описаний объектов из множества М . В результате этого изменения условие I будет выполняться автоматически, а условие 2 оказывается необходимым и достаточным для полноты Ы Обозначим через t множество вершин п -мерного единичного куба. Каждый объект S М можно отождествить с результатом отображения f (S) :
Пусть /С= {jit., ,t jif} - наибольшее множество столбцов таблицы обучения Тпт , обладающее тем свойством, что каждый столбец Jt принадлежит хотя бы одному тупиковому тесту (А) Є Л. . Рассмотрим в качестве нового пространства признаков множество Е , при этом каждому S& /И ставится в соответствие вектор j/c (S) : результат проектирования отображения f на множество К Г S { ,2 /?} f U)-(fu(Sh- Jj (S))t где fj (S) « pZ/t f (S),t 2 -rK Произведя перенумерацию столбцов в дальнейшем будем считать множеством признаков множество /Ґ- /f 2,..., к } . При переходе к признаковому пространству некоторые объекты в новой таблице обучения Tttme , принадлежащие одному классу, могут представляться одинаковыми векторами, учитываемыми столько раз, какова их кратность; объекты из разных классов, как следует из определения теста, будут по-прежнему представляться попарно различны - зі ми векторами признаков. Будем считать, что 3 состоит из объектов, представляемым попарно различными векторами из В
Пусть задача Z" К То, S$ удовлетворяет условию Z0 (в пространстве признаков ). Теорема 1.3. Алгебраическое замыкание Ы, {В% (Ztf,p)jf семейства распознающих операторов . і 8г (Ъфриъ тестовыми опорными множествами является полным относительно To,S }
Доказательство. Обозначим объекты обучения из 2 S-f, ... , mj , содержащиеся в /-ом классе, через Smj4 Поскольку в пространстве признаков с каждый объект S Є S хотя бы одним признаком отличается от некоторого объекта обучения Sє. /с/ , j= /,Z,.. , d , дизъюнкция, о содержащаяся в условии I , всегда верна. Поэтому для любой пары (,J) , С= /,2,..,ф, / /,2, ,f j либо в группе либо в группе при р(со)ф О , CJ Є. J2 , найдется ненулевой элемент, следовательно, существует набор 2 , Xі , Р такой, что соот ветствующий оператор В (Ж, У, р) строит матрицу оценок IIQijltQx в которой Ясу 0
Способ доказательства этих теорем позволяет провести непосредственное формирование модели, содержащей корректный алгоритм. В настоящей главе такое построение проводится для алгоритмов с тестовыми опорными множествами, причем показано, что базисные распознающие операторы могут быть построены в алгебраическом замыкании конечной степени, не превышающей фиксированной величины, зависящей от параметров задач ZKlotS y Другой аспект синтеза корректной модели состоит в критериях проверки выполнения условий теоремы полноты. При этом возникает задача разделения исходного информационного массива на обучающую и контрольную выборки с заданными свойствами и удовлетворяющими некоторым экстремальным условиям.
Построение базисных операторов в алгебраических замыканиях
Рассмотрим теперь некоторые случаи, когда система опорных множеств J? зависит от разбиения X , то есть&(Х)ФСОП1і. Введем на множествах с , с обычное отношение по координатного частичного порядка :
Пусть X - решение уравнения р(X , й(Х))= О с изотонным отображением О(Х) . Тогда для любого разбиения X 4 X условие разделимости по Sc(X) очевидно выполняется, поэтому X - тоже решение (2.7). Если X - не решение (2.7), то для любого X X также имеем р (х, у (X)) -/ для системы S2(X) . Следовательно, Р(Х,0(Х)) является монотонной булевой функцией.
Таким образом, решение основной задачи в случае изотон ного отображения О(X) сводится к нахождению максимального верхнего нуля монотонной функции F(X,Q(X)) . Последняя задача хорошо известна (см., например, [I7J ) и сводится к вычислению значений функции в некотором множестве точек и до определению ее по монотонности. В шенноновской постановке ми нимальное число L(K) применений оператора, вычисляющего значения произвольной функции Г (Z f, . . , Zfc) для нахож дения максимального верхнего нуля, не превосходит
Реально применяемые методы ограничиваются построением некоторого числа верхних нулей и выбором среди них максимального или используют направленный перебор f 22J . Заметим, что к поиску максимального верхнего нуля монотонной булевой функции сводится задача оптимального разбиения и в случае непрерывной информации об объектах распознавания
Если отображение Q&) не изотонное, то задача нахождения решений сравнения становится значительно сложней и для то-го, чтобы избежать полного перебора по множеству необходимо наличие у Q(Z) "разделяющих" свойств. Рассмотрим случай тестовых опорных множеств, которым, очевидно, соответствует неизотонное отображение.
В работе для бинарных таблиц Т , в которых каждая строка представляет отдельный класс, показано, что если тупиковый тест Т , то столбцы из CJ образуют линейно независимую систему векторов (в 72г ). Нетрудно показать, что этот результат переносится на таблицы 7" с двумя или более классами. Отсюда следует
В предыдущих главах рассматривались вопросы существования и нахождения корректного алгоритма в алгебраических расширениях моделей с дискретной обучающей информацией. Было показано, что при введенных ограничениях на исходную информацию 1о и кон-трольную выборку 5 для любой фиксированной задачи 2 ,S9} в замыканиях фиксированной степени эффективно находится алгоритм, решающий эту задачу, то есть правильно классифицирующий все объекты о , . . В общем случае для произвольного алгоритма А из параметрического класса распознающих алгоритмов {A (S.cttf ( SeM , Ы. - вектор параметров) определим точность на контрольной выборке о " как частоту правильно классифицированных объектов. Задача построения оптимального по точности алгоритма сводится к экстремальной или локально-экстремальной задаче выбора параметров, дающих максимальную точность алгоритма на контрольной выборке (см., например, [ZQJ ). При этом точность алгоритма из рассматриваемых моделей с оптимальными параметрами - весами эталонов и признаков - может быть весьма высокой (а для корректного алгоритма равна I ). Важно, однако, оценить работу алгоритма, оптимального для заданной контрольной выборки, на других объектах из множества М . Другими словами, следует оценить качество распознавания (вероятность ошибки) алгоритма с наименьшим эмпирическим риском, когда мы распространяем его на все пространство описаний объектов распознавания.
Емкость алгебраического замыкания конечной степени
Корректный алгоритм A (Z) для решения произвольно задачи , найденный в параграфе 2.1, содержится в параметрической модели алгоритмов Исследуем величину емкости Так как параметры произвольны, то нижняя оценка емкости очевидна:
Множество различных допустимых объектов в дискретном пространстве признаков конечно и, следовательно, емкость можно рассматривать как величину, характеризующую число различных классов эквивалентности на семействе алгоритмов А ( ,? / / )} .
Пусть S - произвольный объект из - мощ ность системы опорных множеств, выбранных по таблице обучения Тіттв Сопоставим объекту $ (0,4) - матрицу близости И1иЛт г гДе ш =/ если Я (3 Я" vS) /1 tuv -О в противном случае.
Для распознающих операторов В (? , р ) оценки (/(S) принадлежности S к классу /С/ j = /,2, опреде ляются элементами обучения, принадлежащими только классу Поэтому, если в матрицах близости объектов строки с номерами одинаковы, то оценки , вычисленные про извольным распознающим оператором совпадают, то есть JV » 4І не могут быть разделены относительно. Обозначим через 6s } . . . бе мощности множеств объектов из классов, соответственно, входящих в обучающую выборку
Тогда, подсчитывая число матриц близости с попарно различными подматрицами, соответствующими классу мощности б , для семейства { А(р, Р, /В)) , содержащего корректный алгоритм, получаем:
В случае операторов p(E.,ff,p) оценки определяются близостью с объектами обучения, входящими во все классы. По определению изоморфных объектов относительно таблицы обучения (см. параграф 2.2) имеем: Ss j S тогда и только тогда, когда l/tjl/шг //i lv// t Отношение изоморфизма является отношением эквивалентнос ти на множестве . Объекты , принадлежащие од ному классу эквивалентности, имеют совпадающие оценки /j (S ) Г/ (Si) для всех / = ff2t . . ) в и, следовательно, оди наково классифицируются произвольным алгоритмом из алгебраи ческого замыкания. Заметим, что по условию теоремы 1.3 объекты С? из о принадлежат различным классам эквивалентности. Пусть J2 - система тестовых опорных множеств таблицы Тптб /J2/ V , S выборка из /И . Утверждение 3.1. Если /7 (Є-2 -Є + /) (3.19) то в выборку S заведомо входят изоморфные объекты.
Доказательство. Для доказательства достаточ но подсчитать число различных классов эквивалентности на М или число матриц llt-цуІІ rn t По определению теста в произвольном столбце матрицы близости либо все элементы равны нулю, либо в блоке, соответствующему одному из классов, имеется по крайней мере одна единица, в блоках остальных классов нули. Таким образом, имеется не более возможностей. Тогда число различных матриц близости не превосходит причем оценка эта завышена, так как столбцы матрицы/ Ля из-за пересекаемости тестов сильно коррелируют между собой. При выполнении (3.19) должны существовать объекты, принадлежащие одному классу эквивалентности и, следовательно, заведомо одинаково классифицируемые алгоритмами из Z,A CZ, 1, P,j3)j .
Оценка (3.19) верна и для семейства алгоритмов типа "Кора", поскольку в них отбирается для каждого класса некоторое число -р конъюнкции признаков, по которым разделяются объекты разных классов, то есть рассматриваются тесты (не обязательно тупиковые) одинаковой длины. Следствие. Емкость h г л , /-,? не превосхо-дит величины
Оценки (3.18), (3.20) не зависят от вида распознающих операторов и степени алгебраического замыкания, но они являются нетривиальными только если правые части не превосходят объема пространства допустимых объектов. Другого рода оценки можно получить, если учесть, что многие из распознающих операторов, различаясь как матричные представления, не отличаются по результату применения решающего правила.
Похожие диссертации на Корректные алгоритмы распознавания в задачах с дискретной обучающей информацией
