Содержание к диссертации
Введение
ГЛАВА I. Вспомогательные сведения из теории вероятностей и статистического последовательного анализа 19
1.1. Необходимые сведения из теории вероятностей.. 19
1.2. Общая постановка задачи оптимального останова 25
ГЛАВА 2. Оптимальный останов алгоритмов обучения 34
2.1. Задача обучения распознаванию образов . 34
2.2. Постановка задачи оптимального останова КСА.. 40
2.3. Оптимальный останов КСА 44
2.3.1. Введение 44
2.3.2. Постановка задачи оптимального останова алгоритмов обучения. Определения 45
2.3.3. Оптимальное правило останова 46
2.3.4. Упрощенное вычисление функции Беллмана . 54
2.3.5. О единственности решения уравнения Беллмана 65
2.4. Свойства правил останова КСА 68
2.4.1. Области останова. Оценки среднего времени достижения 68
2.4.2. Асимптотическое поведение множеств с и функций f(Q) 73
2.4.3. Случай конечного числа состояний 76
2.4.4. Алгоритм вычисления решения уравнения Беллмана 79
Результаты моделирования на ЭВМ 84
2.5. Сравнение правил останова 85
2.5.1. Оптимальные моменты остановки в классах 'Ти /о 85
2.5.2. Эффективность оптимального правила останова в случае конечного числа состояний 96
2.5.3. Сравнение правил останова КСА 103
2.6. Оптимальный останов в задаче обучения распознаванию образов 109
2.6.1. Введение 109
2.6.2. Постановка задачи III
2.6.3. Решение задачи оптимальной остановки 114
2.6.4. Упрошенное нахождение множества останова 122
2.6.5. О единственности решения функционального уравнения 131
Заключение 136
Литература
- Общая постановка задачи оптимального останова
- Постановка задачи оптимального останова КСА..
- О единственности решения уравнения Беллмана
- Эффективность оптимального правила останова в случае конечного числа состояний
Введение к работе
1. Для решения разнообразных задач адаптивного управления и обучения распознаванию образов используются многочисленные алгоритмы идентификации, адаптации, классификации. Это хорошо известные \19, 33, 43, 49, 53 ] процедуры метода наименьших квадратов, стохастической аппроксимации, конечно-сходящиеся алгоритмы.
Работоспособность этих процедур часто обосновывается асимптотическими свойствами доставляемых;- ими оценок, обычно это -состоятельность, скорость сходимости и т.д, Вместе с тем для решения практических задач несомненный интерес представляет вопрос об окончании процесса оценивания { обучения, адаптации ) при условии достаточно высокого качества получаемых при этом оценок.
Задачи такого рода возникают в рамках метода статистического последовательного анализа А.Вальда ^7, 9, 14, 32, 37, 52, 55, 57] . В работах \_1, 12 ] предложены правила останова конечно-сходящихся алгоритмов обучения, гарантирующих высокое качество ( малость вероятности ошибки распознавания ) получаемых при этом оценок, но эти правила не являются оптимальными.
Высокое качество оценивания алгоритма может не являться единственным желательным свойством. В приложениях приходится учитывать затраты машинного времени или стоимость проведения наблюдений ( экспериментов ), т.е. важна эффективность работы соответствующих алгоритмов. В таких случаях может оказаться целесообразным остановить процесс обучения С оценивания ) так, чтобы достигался разумный компромис между противоречивыми требованиями: высоким качеством и достаточно большой эффективностью работы алгоритма. ~ 6 -
Изложенные соображения приводят к формализации момента останова С остановки ) как оптимального, определяя его из условия минимума некоторого функционала.
Характерной чертой рассматриваемых в диссертации задач является то, что момент останова является случайным и определяется на основе данных наблюдения { в главе 2 это {#<] ). Такой способ выбора момента прекращения обучения имеет преимущества { в смысле минимизации функционала J('cr) ) по сравнению с детерминированным моментом останова.
В предлагаемой работе найдены и исследованы оптимальные правила останова рекуррентных процедур в задачах оценивания и обучения распознаванию образов.
2. Перечислим основные положения диссертации, выносящиеся на защиту.
Обоснование возможности применения общих схем теории оптимальных правил остановки к широкому кругу задач обучения и оценивания и исследование свойств соответствующего уравнения Беллмана.
Теоремы об упрощении вычисления оптимального правила останова.
Алгоритм построения функции Беллмана для задачи оптимального останова процесса обучения в случае конечности множества признаков.
Способ аппроксимации оптимального момента останова.
3. Перейдем к изложению материала диссертации.
Первая глава носит вспомогательный характер. В I.I приводятся необходимые в дальнейшем сведения из теории вероятностей и статистического последовательного анализа.
В 1.2 излагаются основные результаты общей теории опти- _ 7 ~ мальных правил остановки, являющихся основой диссертационной работы.
Во второй главе рассматриваются стохастические рекуррентные алгоритмы обучения, предназначенные для нахождения вектора 8* неизвестных параметров опознающей системы. Оценки $^ неизвестного и* строятся в дискретные моменты времени 4'0,1У.. согласно процедуре 0
Здесь элементы обучающей последовательности [ %+ } принадлежат измеримому множеству л К и являются независимыми случайными величинами с распределением F ; во - произвольный случайный вектор с распределением вероятностей J0 \Т(х,@)~ индикатор множества [ т № ру- & ] .
Предполагается, что выполнены условия теоремы 2.1, при которых алгоритм { B.I ) является конечно-сходящимся, т.е. PlZlXfrM Qt)**** J" 1. <В.2)
В 2.2 рассматриваются известные (_1, 12 | правила останова конечно-сходящихся алгоритмов, не обладающие оптимальными свойствами и обосновывается функционал потерь J (t~), используемый для нахождения оптимального момента останова. В задаче обучения опознающих систем этот функционал имеет вид lbr)= НІ^рШ^ІіАі-ІС^е*)}}, <в.з) где с ~гг 0 - штраф за те моменты времени, в которые изменение параметра 9 из ( B.I ) не производилось, ,>/ (0,t]~ дисконтирующий множитель. ~ 8 -Минимум ( В.З ) ищется в классе I марковских моментов, т.е. случайных величин ^Yu) со значениями в /w0 таких, что событие f^-rj измеримо относительно С~ -алгебры "}{.-= Є{90) я/І для любого 4е Л/0 .
Определение оптимального момента останова '?"# из условия минимума { В.З ) в I гарантирует малость вероятности ошибки распознавания р(0)~ Г[Х! №,Р)*0 } (В.4 ) при не слишком больших затратах на обучение.
В 2.3 доказывается теорема, в которой дается способ отыскания оптимального момента останова в задаче обучения. Теорема является уточнением известных теорем об оптимальном останове, приводимых в литературе [37, 52 ] для более общих задач последовательного статистического анализа.
ТЕОРЕМА 2.2. Пусть алгоритм обучения { B.I ) конечно-сходящийся, тогда момент является оптимальным в , где из { В.4 ), функция А (9) является решением функционального уравнения ( уравнения Беллмана )
-м^(рШ)<і[і-р(6)]+оіНЦ,0) j (в.б) в котором оператор /-/ определен на множестве измеримых ограниченных функций j : /К -" R формулой
Ш,в)= [${9+I(x,0)i(x,9)\F{d*l (в.?) X В пунктах 2.3.4 , 2.3.5 показано, что неотрицательное решение - 9 -уравнения Беллмана единственно и может быть найдено методом последовательных приближений р}~- Л* L(9), где монотонно невозрастающие неотрицательные функции { L ] задаются рекуррентными соотношениями faH Ш - п* і юъ 41- K6)W Н (к в) 1, ( В.8 )
Вычисление последовательных итераций ММ быстро усложняется, поэтому приходится ограничиваться первыми приближениями функции jjO) .
Приводится упрощенный способ нахождения ^ , при котором приближенное решение уравнения Беллмана позволяет получить оптимальный момент остановки.
ТЕОРЕМА 2.4. Цусть конечно-сходящийся алгоритм ( B.I ) такой, что существует такое S z 1 , что множество инвариантно при отображении fX*f, о)=~ч(*>Ґ'Ьґ, п), fvc*.о)* шв) для любых Яі , , ^s X . Тогда оптимальный момент останова "?"#. совпадает ( с вероятностью I ) с моментом /Гс^ , где "с; = ты {/<гЛ\/0: Ці(64)= РШ ] . < В.9 )
Этот результат, по-видимому, является некоторым обобщением известного по работам \_37, 52 ] так называемого "монотонного случая".
Указано, что момент "?7, из ( В.9 ) и оптимальный в клас- и момент ;= тій { ой {< н ^ (${)~р(04) 1 ( в.ю ) аппроксимируют при к-^<=« оптимальный м.о. с * .
В 2.4 исследуются свойства оптимального момента 2^ в зависимости от значений параметров С и U из ( В.З ). При этом используются такие характеристики стохастических алгоритмов адаптации как среднее время сходимости и среднее число коррекций. Приводятся нетривиальные оценки этих характеристик.
В случае конечного множества признаков JC предлагается алгоритм вычисления решения уравнения Беллмана в произвольной точке Ь . Алгоритм удобен для реализации на ЭВМ, при меним к произвольным рекуррентным процедурам вида { B.I ) и представляет собой процедуру обхода вершин некоторого дерева. Основными особенностями приводимого алгоритма являются: I)функ ция Беллмана строится в заданной точке в результате однократ ного обхода дерева реализации св. \0Ч^ ] , без использования метода последовательных приближений; 2) для нахождения опера тора Н(У/$) ( см* ( В.6 ) ) функция /(в) восстанавливает ся не во всех точках , а только в тех, которые соответст вуют значениям вектора , полученного в силу ( B.I ) при всех возможных значениях ОС 6 X . Приведены ре зультаты моделирования этого алгоритма на ЭВМ.
В 2.5 на классе марковских моментов останова продемонстрирован основной эффект последовательного анализа: уменьшение значения функционала, вычисленного на оптимальном марковском м.о. по сравнению с детерминированным. Приведенная в этом па- - II - раграфе теорема 2.9 позволяет получить оценки снизу величины
, где yl^c. - оптимальный детерминированный момент останова, определяемый из условия J (к*) = -<*/ TU).
В случае конечного числа состояний марковской цепи, определяемой алгоритмом { B.I ), и малых штрафах С- удается определить эффективность применения методов последовательного анализа в задаче обучения, которая характеризуется величиной &=3>Сс)= Jfn*)/ J С?"*) . Теорема 2.10 позволяет получить, что c/Vn 3QC&) = <=х^ .
Установлена связь момента Л/* первого достижения последовательностью І&4-] поглощающего множества 0 ~ = [ 9 ' х (х, 0) ^ 0 rfoceX \ и немарковского момента z х , называемого времнем сходимости алгоритма { B.I ). Для конечно- сходящихся алгоритмов момент - т о^ ( В.II ) где индикатор JTCx, 0) из { B.I ).
ТЕОРЕМА 2.II. Пусть алгоритм обучения ( B.I ) конечно-сходящийся, тогда момент останова
Л/* = ж.'и [UAs/o ^ ^ о } с вероятностью I совпадает с немарковским моментом с # из ( В.II ).
Если в 2.2 - 2.5 исследовался оптимальный останов в задаче обучения с учителем, то в 2.6 предлагается рассмотреть задачу оптимального останова процесса обучения в случае, когда - 12 -имеется П вариантов классификации тренировочной последовательности 1%і} и нахождение решения и* задачи классификации производится в условиях неопределенности относительно номера варианта. Другими словами, предполагается, что имеется М "учителей" и каждый предлагает, вообще говоря, свой вариант классификации обучающей последовательности изображений, а идентификация параметра 9ч = &*СМ) осуществляется по случайно выбранному М -у варианту классификации (т.е. систему обучает случайно выбранный из заданного набора А* -й "учитель" ).
Такой подход к задаче обучения опознающей системы повышает её гибкость и расширяет возможности обучаемых систем.
Нахождение правила останова в этом случае становится более сложным, решение этой задачи связано с идентификацией параметра А по обучающей выборке. Соответствующий результат сформулирован в теореме 2.12. Также как и в задаче обучения с учителем в рассмотренной задаче приведен способ упрощения вычисления оптимального момента останова, указан способ аппроксимации оптимального Т~* , предложено обоснование функционала, характеризующего качество работы алгоритма обучения.
В приложении обсуждается задача оптимального останова алгоритмов стохастической аппроксимации в схеме наблюдения
Уж = % $* * 4l , % ' <Р(*+), ^М . < B.I2 )
Здесь 9м- - вектор неизвестных параметров, 4^6 ) - заданная матричная функция, l ^, ^ } ~ наблюдаемые в дискретные моменты времени величины, [%} - помеха наблюдения.
Для получения оценок \yi] параметра 6 у- используется рекуррентная модификация метода наименьших квадратов - ІЗ -
Рм-Рі-РіФ^ЦР*, (B-I3) в предположениях: A. Случайные величины IJj. в ( B.I2 ) стохастически неза висимы и
Б, Выполнено неравенство с некоторой ПОСТОЯННОЙ Cf . ___ B. Информационная матрица предельно невырождена, т.е. -civa \~7{ \ ^ ^^
Эти условия, как известно [43, 44 J гарантируют сходимость х п.н. при начальных данных 9о » Р0 ^ 0 ж положительной весовой матрице К
В 2 обосновывается функционал средних потерь, получаемых от использования момента останова ^ , вида
Тог)«М((0*-0*|г+<: 'г- ]. (в.14)
Оптимальный момент останова находится из условия минимума этого функционала в классе | -марковских моментов относительно системы [у{ \ , fl = Є{ %о J. Первое слагаемое в ( В.14 ) растет при возрастании времени оценивания. Величина d. 7> О играет роль стоимости проведения одного наблюдения ( или одной итерации алгоритма ( В. 13 ) ).
Правила останова, пригодные, по крайней мере в принципе, для решения прикладных задач, удается получить при сведении первоначальной задачи к задаче останова некоторой "марковской'.' - 14 - В 3 показано, что в результате такой редукции функционал ( В.14 ) запишется , где функция
3 (?) » аргументом которой является векторно-матричный набор U-fa.ttJijP^Pt) <вл5) имеет вид
Здесь случайные векторы 9± и матрицы / , в предположениях независимости случайных величин 9* и [у^. ] и их гаус-совости, являются апостериорными < байесовскими ) оценками среднего и ковариационной матрицы вектора 9% и пересчитыва-ются согласно рекуррентным формулам Байеса-Стратоновича ( см. формулы { П.І8 ) - ( П.2І ) в тексте ).
Оптимальный момент останова выражается в терминах величин f^j из ( В.15 ), которые в силу { В.13 ) и формул { П.І8 )~ - ( П.2І ) в тексте, удовлетворяют рекуррентным соотношениям типа h~ QtUt.h-i), (B.I7) причем система (?^; Э^; р) образует марковскую случайную функцию и является достаточной [ 52 ] в рассматриваемой задаче оптимального останова. ТЕОРЕМА. П.З. Пусть
1) величины OCj. определяются разностным соотношением **i - №6 %,); величины \1f+] и [W^} из ( В. 12 ) удовлетворяют условиям А - В; вектор 0%. является гауссовской величиной с заданными - 15 -статистическими характеристиками: средним 9 и ковариационной матрицей К$ т 0 ; случайные величины 0С0 и OJt независимы; начальное данное 9 о в алгоритме ( В.13 ) такое, что
Тогда оптимальный в / момент останова ^-у для функционала ( В.14 ) определяется соотношением
Т- = *иіиі(У*Л\/0: ^(h) = lf(h)}. Здесь функция 4(^) из { B.I6 ), фикция X(l) удовлетворяет уравнению Беллмана H()f,l) = $J[Q(u)]/№)^ и Й(Д ]) из { В.17 ), {- (X, 0,(), Р/Р ) , условная гаус-совская плотность р(УИ) случайной величины ^ имеет параметры Там же показано, что средством аппроксимации оптимального м.о. Т~ч являются моменты ^7, < см.утверждение П. 5 ) Средством аппроксимации оптимального ""#. являются также моменты ^ , использующие конечный горизонт прогнозирования ти- ^{/^. гк(^)=^/]. (в-20) Кроме того, J ftTv ) ^ J (Тї) { см. теорему П.6 ), где и ^ из ( В.19 ) и { В.20 ) соответственно. В 4 приводятся условия, при которых оптимальный момент останова допускает упрощенное описание, т.е. для его нахожде^ ния используется первое приближение h (і) функции Беллмана fl\) ( см. (B.I8 ) ). Приведены примеры задач, в которых марковский момент останова не уменьшает значения функционала потерь ( В.14 ) по сера-внению с оптимальным детерминированным. Чтобы не загромождать текст ссылками на формулы, в доказательствах теорем используются ссылки вида ( Д.00 ). Основные результаты диссертации докладывались на семинарах кафедры теоретической кибернетики Ленинградского государственного университета им. А.А.Жданова и изложены в работах \26> - 30] . - 17 -СПИСОК ОБОЗНАЧЕНА = - равно по определению ЛІ ={1,2,... } ДО - вещественное евклидово пространство размерности И X ^ сов (ос }... }?с- ) ~ вектор с I*) компонентами Ыи(л;/} і [J1 ( VA - вектор ) а , если Л < б t ЄСЛИ CL ? б 'ос{)й Х^^ О*, *»,... ) (.Х,У) X J) - скалярное произведение векторов ОС ж Ч \х\ = \(Х,Х) - евклидова норма вектора X и модуль числа X 6 - матрица эрмитово сопряженная матрице /5 (в вещественном случае Ь - В , где б - транспонированная матрица 6 ) 5" - матрица, обратная матрице Ь | 6 ] - евклидова норма матрицы 6 Sp J5 - след { сумма диагональных элементов ) квадратной матрицы Ь f й т?и 0; у} (^ = мл/ 0; у] (>, х, 1 )- вероятностное пространство <о - элемент Jf.-j - индикатор множества f- }}±^Ау J(а{^ ~ 1 с? со//1 /vfe ^ - плотность нормального ( гауссовского ) распределения, где -вектор среднего и К -матрица кова-риации - 18 - /v| - символ математического ожидания М[ ' 1 " условное математическое ожидание М,И = П{ lU-i), и лі. п.н. - "почти наверное" ( с вероятностью I ) или г « п.н. - такое обозначение будет использоваться в тех случаях, когда важно подчеркнуть, относительно какой из вероятностных мер выполняется некоторое свойство "почти наверное" п.в. - "почти всюду" - часто употребляется вместо слов "почти наверное" св. - случайная величина ( случайные величины ) о = > р - импликация, т.е. логическое высказывание "если о^ , то р' " или " oL есть достаточное условие для Р " о1^=>/Ь - эквиваленция, т.е. U - Р> и Р> =? ol Q(t) <—> существует №є ІК такое, что 0^ —Мг Г - нижний { верхний ) предел последовательности {4 {J t ^ ~ единичная матрица /кх ж , Впервые вопросы существования и отыскания способов построения оптимальных моментов остановки рассматривались в работах А.Вальда по рекуррентным модификациям байесовского подхода к задаче статистического оценивания [ 9 ] , а также в работе Блекуэлла. Гиршика [7 3 , в которой рассматривались задачи последовательного различения статистических гипотез. Вскоре после появления этих работ Снеллом [61 ] была сформулирована задача об оптимальной остановке случайных процессов в дискретном времени в следующем виде. Пусть на некотором вероятностном пространстве (Q} W/P) задана наблюдаемая последовательность св. [JL ] , порождающая возрастающую последовательность [Tt } " -подалг , и последовательность св. [ft ] , согласованная с [ % J . Если процесс наблюдения за последовательностью { } прекращается в момент времени с" , то значение е-трактуются как потери { в оригинале - выигрыш ), понесенные в момент времени Z: . Задача состоит в нахождении правила остановки { в классе таких св. Тг-Тгґи)), что fr =/J J ), минимизирующего средние потери Af - - . Дальнейшее развитие теории оптимальных правил остановки 14, 54], было подытожено в фундаментальной монографии Г.Роббинса, Д.Сигмунда, И.Чао [37]. Сформулируем один из основных результатов этой работы в за-даче М - U{ М 5V Определим последовательность І Ґи (о) \ и. А/?ЛУ0, И М С помощью рекуррентных соотношений тогда т-гл/ 0 1) оптимальный в классе / марковский момент определяется соотношением т 2) Существует функция її Ы) = "У (]i (3) (JT Л - У такая, что оптимальный в классе Т марковский момент определяется .« оо , если такого / не существует если при любом / /\\У0 и TV "Т выполнено Доказательство теоремы приведено в _37 і Формула ( I.I ) описывает оптимальный момент останова как функцию увеличивающегося числа переменных, что делает нереальным его использование при решении прикладных задач. Рекуррентные уравнения для функции X и правила оптимального останова в виде, по крайней мере в принципе, пригодном для решения прикладных задач, удается получить в "марковской" постановке проблемы оптимального останова, впервые изложенной в \1Ъ ]. Хотя это направление формально укладывается в схе -му Снелла, однако предположение марковости дает возможность получить более глубокие и конструктивные результаты [8, 13, 14, 39, 40, 46, 56, 60 3. В наиболее законченной форме теория оптимальных правил остановки марковских случайных процессов и последовательностей изложена в монографии А.Н.Ширяева [52 1 . На современном этапе основное развитие теории последовательного статистического анализа { теории оптимальных правил остановки ) идет в плане развития прикладных исследований. Это ра- ." боты по оптимальному останову: процессов полумарковского типа в задачах контроля надежности [39, 60 1, эргодических цепей Маркова [24І ; в задачах: оптимального управления [з, 13 ] , оценивания [16, 23, 34, 41, 62 ] и распознавания образов [_ 57]. Известны работы по оптимальному останову при наличии ограничений (_4, 59 ] . Сформулируем задачу оптимального останова, которой будем придерживаться в настоящей диссертационной работе. Пусть на некотором вероятностном пространстве ( с ;J,P) заданы в дискретные моменты времени і є /\V0 ненаблюдаемая св. с/ и наблюдаемый процесс ( Jt } , которые характеризуют статистические свойства исследуемого объекта { обучаемой системы, дискретной динамической системы ). Пусть [J ] - неубывающая система о -алгебр 7 , характеризующих "информацию"., об бъекте к моменту времени г . Будем полагать, что процесс [ j согласован с системой (j j. В некоторых приложениях получение данных наблюдения (j/ или вычисление оценок неизвестного параметра и с помощью рекуррентных процедур оценивания и обучения связано со значительными затратами тех или иных ресурсов. Естественно прекращать процесс наблюдения, когда такие затраты начинают превалировать над ожидаемыми выгодами, получаемыми от уточнения харак -теристик исследуемого объекта. Предположим, что, прекращая наблюдения в момент 7 , мы понесем потери /%, , с) , тогда средние потери в момент т есть математическое ожидание М(й, , с\ щ 9 (%) і с - стоимость проведения наблюдения. Введем / -класс произвольных марковских моментов относи -те льно СГ алгебры Ц (см. определение 1.4 ). Определим на этом классе функционал Будем интерпретировать Г как случайный момент, в который производится прекращение наблюдений, а значение 1(х)при фиксированном 2Г - как средние потери, соответствующие этому м.о Для известных конечно-сходящихся алгоритмов { см., например, [42, 44] ) момент с # достижения предельного значения параметров, определяемый соотношением не известен, а получить достаточно точные его оценки сверху не удается, кроме того, возможны случаи, когда (1/ =+ . Поэтому в рамках теории систем, обучающихся распознаванию образов , актуален вопрос об останове процесса обучения [і, 12], т.е. задании { нахождении ) момента времени 7Г - момента останова, в который следует закончить настройку параметра и . После этого найденный в результате обучения параметр 9 фиксируется и система считается обученной. Естественно при этом искать такие правила останова, которые гарантировали бы достаточно высокое качество обучения, обычно характеризуемое величиной , где функция f (6) определена в ( 2.2 ). Приведем один из возможных способов останова процесса обучения КСА. Пусть \С - фиксированное натуральное чис-ло. Алгоритм { 2.4 ) заканчивает работу в случайный момент { , определяемый условиями: где 7 из { 2.5 ), J. из { 2.4 ). То есть {={ , если І-момент, в который впервые произошло событие: неравенства (2.3) -выполнились раз подряд. В {_ I при ряде естественных предположений устанавливается неравенство ч если Ю -JJ f Т » где произвольные числа Є, U (о,1) . Неравенство { 2.14 ) означает, что выбором достаточно большого & в приведенном правиле останова будет обеспечено сколь угодно высокое качество обучения. Алгоритм останова ( 2.13 ) прост и не требует знания функции р{0) , хотя обеспечивает её малость. Если вероятность ошибки классификации р(0) известна,можно воспользоваться, разумеется, более простым правилом Л/ = І ЛІ-- f (0t)=O }, (2.15 ) обеспечивающим высокое качество обучения не только в среднем, но и на каждой реализации ос процесса обучения. Высокое качество обучения может не являться единственным желательным свойством обучаемой системы. Иногда важно, чтобы процесс обучения происходил эффективно, т.е. достижение предельного состояния 6 осуществлялось бы по возможности быстрее. Такая ситуация встречается в большинстве задач адаптации при их практической реализации. Поясним это положение. Процесс обучения с учителем, основанный на алгоритме адаптации { 2.4 ), состоит из двух этапов. На первом этапе ( в режиме обучения ) производится поиск параметра # . Обычно требуется, чтобы затраты времени ( средств ) на обучение были не слишком велики. Такие затраты к моменту времени г будем характеризовать величиной, пропорциональной числу коррекций Zf СССР -из { 2.5 ). На втором этапе ( в режиме экзамена ) система счи-. тается обученной и функционирует с фиксированным значением na L раметра 0+ , найденным в момент окончания процесса адаптации. Основное требование к опознающей системе на этом этапе - высокое качество работы, которое мы условились характеризовать величиной P(fy). Для обеспечения эффективности работы опознающей системы на обоих этапах введем функционал средних потерь, зависящий от м.о. f , следующего вида 7ег)= МУУШ ЇуЬ-Т )}, (зле) где С т? О , параметр, характеризующий штраф за те моменты времени, в которые коррекция параметра 0 не производилась, ot (0, 1] - параметр, "учитывающий изменение ценностей со временем" 52 1 , называемый в иностранной литературе [56, 60 ] дисконтирующим множителем. Завершение постановки задачи требует указать класс м.о., в котором будет осуществляться минимизация функционала { 2.16 ). Будем рассматривать в качестве такого класса 1 множество марковских моментов относительно системы .(Г -алгебр (_i77j ( см. I.I ), где вид т+ будет уточнен при рассмотрении конкретных задач распознавания. При d і функционал (t) конечен для любого с є I . ОПРВДЕЛЕНИЕ 2.3. Случайный м.о. .t# , определяемый условием тс ) tnL г) (2Л7) называется оптимальным в классе 1 для функционала J из ( 2.16 ). Чтобы подчеркнуть зависимость 7 от параметров оС.. и С будем употреблять наряду с "?"# обозначение "с с ддд обозначения оптимального м.о. Определение из условия минимума функционала ( 2.16 ) представляется разумным компромисом между противоречивыми требованиями, предъявляемыми к опознающей системе в режимах обучения и экзамена: высоким качеством распознавания, с одной стороны, и малыми затратами на обучение, с другой. Принятая постановка задачи оптимального останова процесса обучения полностью укладывается в рамки теории оптимальных правил остановки [52, 37 \ . Приводимые ниже результаты существенно опираются на эти работы и могут рассматриваться как уточнение изложенных там общих утверждений на случай конкретных задач об останове. Таким образом,получили, что при всех выполнено . По теореме 2.5 это уравнение имеет только нулевое решение Y(v) - 0 t что и требовалось дока--зать. То, что { 2.64 ) задает отношение эквивалентности, очевидно. Фактор-пространство К по отношению эквивалентности обозначим Будем предполагать, что СУ конечно. Тогда процедура { 2.4 ) порождает конечную марковскую цепь со значениями в & и матрицей переходных вероятностей S . Элементы фактор-пространства обозначим [(2 J -о ( см.пример 2.2 ). В силу определения ( 2.64 ) и ( 2.18 ) нетрудно убедиться, что функция р(&) принимает постоянное - 78 -значение на каждом классе эквивалентности. Действительно, для эквивалентных точек 6 0 справедливо J.(%, & ) = АСх, 9 ) п.н. для любого ОС Є Л t поэтому и, следовательно, функция У( W из { 2.24 ) на множествах СЕ) і » г к постоянна. По индукции показывается, что функции /и ((г) , А = /Mo f а потому и предельная функция ЇЩ постоянна на элементах здесь операция минимума берется покомпонентно. В силу устойчивости матрицы L существует ) , и уравне ние ji cct4Uuf\ имеет решение Х= C-(_F-o(h) Сл , причем покомпонентно. Вектор Є - d положителен, поэто-му существует Со т 0 , что при выполнено следовательно, У / и / является решением { 2.65 ). Условие t4 - означает, что (tOc = &0 при С С0\ Иллюстрацией к приведенному утверждению может служить пример 2.2. Равенство с (2 имеет место при с С0 юиіІ-;_ (. Повторяя рассуждения, использованные при доказательстве утверждений 2.5 и 2.6 , легко получить, что существует С О такое, что при с с0 и = і t имеет место равенство Тогда { 2.66 ) непосредственно следует из факта конечности ; ТГ#) и кЩ для цепей с поглощающим состоянием .21 J . Конечность множества (н) позволяет получить численный способ решения уравнения Беллмана { 2.20 ), если воспользоваться методом работы [45] , црименявшимся при выводе соотношений { 2.54 ), С 2.55 ). Алгоритм вычисления решения уравнения Беллмана в произвольной точке. Для решения вопроса о том, следует ли на п -м шаге остановить алгоритм ( 2.4 ) согласно правилу { 2.19 ), необходимо знать значение Х($и) . Как было отмечено выше, функцию t можно найти методом последовательных приближений { 2.24 ). При этом возникают следующие трудности: во-первых, восстанавливать t[u) приходится во всей области /Г\ о , если вероятность ошибки р(@) не является известной функцией от С , а определяется при заданном и конструктивно, например, в силу усиленного закона больших чисел, то определение уже \i[u) становится трудно выполнимой зада -чей. Во-вторых, согласно правилу { 2.19 ) значения функции мШ требуется знать во всех точках $ Ц\ , что является излишним, когда множество состояний обучаемой системы конечно. В-третьих, методом последовательных приближений находятся лишь приближённые значения функции Х[ и) , а оценку качества аппроксимации привести трудно. Предлагаемый алгоритм существенно обходит указанные трудности. Так, знание вероятностей Р(0) требуется лишь в конеч - 80 ном числе точек несоответственно, функция І [О) вычисляется для конечного числа значений, причём их число определяется количеством элементов множества X . При достаточно общих условиях значения функции 4(0) будут вычислены точно. Недостатками алгоритма являются: необходимость многократного/ его применения при отслеживании процесса порождаемого процедурой ( 2.4 ) и существенное использование условия конечности множества X . Пусть требуется найти функцию Y(-) в точке &ь . Для удобства будем считать, что Обозначим элементы А через L = ltji . Всевозможные значения векторов состояний, получаемые в силу алгоритма { 2.4 ) С с начальным условием Ро & п.н. ) при предъявлении элементов обучающей последовательности Xt будем называть деревом реализаций v(i) с корнем в вершине . Введём обозначение Как следует из доказательства теоремы 2.II, условие { 2.7) не использовалось при выводе того факта, что г (г л/ \ 1 . Поэтому, используя факт, что Г\А/ :?)=1и теорему 2.II, имеем: случайная величина f # п.н. конечна. Это эквивалентно С 2.7 ), что и требовалось доказать. Теорема 2.II имеет практическое значение. Для конечно-сходящихся алгоритмов величина 4 - время сходимости - не известна, так как не наблюдаема и поэтому, на первый взгляд, кажется, что нельзя ответить на вопрос, сошёлся алгоритм обучения или нет. Как показано, момент т с вероятностью I совпадает с м.о. л/ , который является функцией наблюдаемых величин, и позволяет нам ответить на вышеуказанный вопрос. Кроме того, если существует штраф с т о за "холостые" шаги алгоритма, то останов следует производить в марковский момент - 2 с . Причём, как доказано в теореме 2.7, с — sV п.н. Введение. Во многих областях современной техники и естествознания возникает задача классификации ( опознавания ) ( см. 2.1 ), которую кратко можно охарактеризовать следующим образом. Пусть множество изображений разбито на два непересекающихся класса { этот случай легко распостра-нить на любое конечное число классов ). Задача распознавания сводится к построению решающего правила ( дискриминантной функции ), разделяющей классы изображений в пространстве признаков по знаку. Будем предполагать ( см. 2.1 ), что семейство дискриминантных функций параметризовано параметром о . Построение оптимальной разделяющей функции заключается в нахождении параметра Q { считается, что он существует ), при котором решающее правило разделяет классы. Процедура определения нужного в называется [12, 42, 49 ] алгоритмом обучения и осуществляется с помощью тренировочной последовательности изображений . Если для каждого изображения из тренировочной последовательности известна априорная классификация, т.е. информация о его принадлежности к определённому классу, то процедура настройки параметра б называется обучением с учителем. Этот случай и рассматривался нами ранее в 2.1 - 2.5. Если указания учителя отсутствуют, то задача нахождения р называется задачей самообучения. В настоящем параграфе будем ; предполагать, что априорная классификация ( указания учителя ) известна неполностью, точ - по нее предполагается, что имеется набор из М вариантов классификации предлагаемой обучающей последовательности ( см. 2.1 ), причём этот набор упорядочен тем или иным способом так, что каждому сопоставлен номер j- і, М . Другими словами, имеется Н учителей и каждый предлагает, вообще говоря, свой вариант классификации входной последовательности изображений, а настройка параметра и осуществляется по случайно выбранному М -у варианту классификации { т е. систему обучает случайно выбранный из заданного набора у -й учитель ). Хотя параметр А не известен, однако при естественных предположениях можно строить дискриминантную функцию и в этих условиях неопределённости, идентифицируя { восстанавливая ) значение параметра М , такую задачу распознавания будем называть задачей в условиях неопределённости. Последовательность решающих правил, получаемых при этом, будет вообще говоря, сходиться к оптимальному правилу при неограниченном увеличении обучающей выборки. Будем как и ранее ( см. 2.3 ) ставить задачу об останове процесса обучения опознающей системы, при котором гарантировалось бы достаточно высокое качество обучения. В параграфе 2.2 рассматривались два этапа работы обучаемой опознающей системы: обучение и экзамен. Эффективность работы алгоритма обучения, как и прежде, будет характеризоваться функционалом средних потерь. Оптимальное правило останова, минимизирующее этот функционал, обеспечивает высокое качество работы опознающей системы, т.е. гарантирует малость вероятности ошибки классификации при не слишком больших затратах времени на обучение. В данном параграфе развивается подход, предложенный в Решение задачи оптимального останова в случае, когда имеется несколько вариантов классификации обучающей последовательности, становится более сложным, её решение связано с идентификацией параметра М по обучающей выборке. Такой подход к задаче обучения опознающей системы повышает её гибкость и расширяет возможности обучаемых систем, так как позволяет действовать в условиях большей априорной неопределённости. Дудем называть введённую выше задачу обучения - задачей обучения в условиях неопределённости. Здесь вектор настраиваемых параметров; tt t R элемент обучающей последовательности -известная функция своих аргументов, определяющая конкретный вид алгоритма; Ар (.%, 0) - индикатор множества где fy(X,9) = Iff ) V( ,0) ; функция V из ( 2.100 ), в которой вместо известного в подставляются оценки 6{ ; функция характеризует "уЕсазания учителя". В соответствии с постановкой задачи значения функции j (x) на обучающей последовательности известны, а значения / неизвестно. Очевидно , что при известном параметре Л1 алгоритмы ( 2.101 ) и { 2.4 ) совпадают. Введем необходимые обозначения. Дудем характеризовать качество работы опознающей системы ( 2.101 ) в режиме обучения величиной, пропорциональнойОбщая постановка задачи оптимального останова
Постановка задачи оптимального останова КСА..
О единственности решения уравнения Беллмана
Эффективность оптимального правила останова в случае конечного числа состояний
Похожие диссертации на Оптимальный останов процессов обучения и оценивания
