2010 Лекции МОТП. Записки (2010 Лекции МОТП. Записки.pdf), страница 12

Например, выбирая первые примеры реализацииразличных этапов будет получена следующая общая формула для вычисления оценокобъекта S за классы K j , j=1,2,…,l.mj1Γj (S ) =∑ ∑ BΩ (Sν , S ) .(m j − m j −1 ) ν =m j −1 +1Ω∈Ω A(6)При выборе системы опорных множеств согласно вариантам a) или b) прямоевычисление оценок (6) представляется весьма трудоемким. Действительно, привычислении оценок (6) согласно a) требуетсяmCnkвычислений значений функцииблизости. В действительности нет необходимости выполнения всех данных вычислений,поскольку при многих вариантах реализации этапов 2-5 и различных системах опорныхмножеств существуют эффективные комбинаторные формулы вычисления оценок.Например, при использовании в качестве системы опорных множеств Ω A = {Ω : Ω = k} ивариантов a) выполнения этапов (2-5), справедлива формулаΓj ( S ) =где d ( S , S i ) =1Cdk ( S ,Si ) ,∑(m j − m j −1 ) Si∈K j{ν : xν(354)( S i ) − xν ( S ) ≤ εν ,ν = 1,2,..., n} .69При использовании вариантов a) выполнения этапов (2-5) и b) для первого этапа,справедлива формулаΓj ( S ) =где1(2 d ( S ,Si ) − 1) ,∑(m j − m j −1 ) Si∈K j(355)d ( S , S i ) = {ν : xν ( S i ) − xν ( S ) ≤ εν ,ν = 1,2,..., n}.Другие, более сложные и общие способы определения этапов (1-5), а такжесоответствующие им эффективные формулы вычисления оценок, приведены в /…/ .1.3.4.

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

Желаемым результатом в обоих случаях являетсянахождение таких значений параметров, при которых будет обеспечена высокая точностьраспознавания.Поиск значений параметров, как процесс «обучения с учителем» используется внейросетевыхподходах, методе потенциальныхфункций,построениилинейныхразделяющих гиперплоскостей. Применяется следующая общая схема обучения. Задаютсяначальные значения параметров (например, случайные из некоторого интервала).Алгоритму предъявляется один из обучающих объектов, класс которого известен. Еслиобъект распознается правильно, предъявляется для распознавания следующий объект.Если объект классифицируется неправильно, происходит коррекция параметров «внужном направлении».

Процесс продолжается до достижения стабилизации работыалгоритма, когда последующее обучение не уменьшает общее число ошибок наобучающей выборке.Более общая постановка процесса «настройки» алгоритмов связана с задачейоптимизации модели, когда каждый конкретный алгоритм модели полностью задаетсянабором значений параметров модели.Пусть дано параметрическое множество распознающих алгоритмов{ A( y}, y ∈ D}и на нем определен числовой функционалϕ ( A)качества алгоритма.70Требуется найти такой алгоритмA* ∈ { A} , который доставляет экстремум функционалу:ϕ ( A*) = extr ϕ ( A) .A∈{ A}Так, например, модель вычислении оценок со способами выполнения этапов (а,а,с,а,а,с)является следующим параметрическим семейством алгоритмов:{ Ak (k , ε , p, γ , δ , c1 , c2 ),1 ≥ k ≥ 0, k − целое, ε ≥ 0,1 ≥ p ≥ 0,1 ≥ γ ≥ 0, c1 > c2 } .Стандартная постановка проблема оптимизации состоит в следующем.Пусть задана таблица контрольных объектовT ' nql , аналогичная таблице обучения, т.е.состоящая из разбитых на l классов m числовых строк – признаковых описаний объектовS 'i = ( x1 ( S 'i ), x 2 ( S 'i ),..., xn ( S 'i )) .

Для определенности считаем, чтоS 'i ∈ K j , i = q j −1 + 1, q j −1 + 2,..., q j , q0 = 0, ql = q.Пусть1, S 'i ∈ K j ,Aα ij = Обозначим α ij = α j ( S 'i ).0, S 'i ∉ K j .Определение. Стандартным функционалом качества распознавания называетсяфункционал ϕ ( A) =1 q l∑∑ α ij − α ijA .ql i =1 j =1В статистической теории распознавания данный критерий называют эмпирическимриском. Очевидными эквивалентными его вариантами являются «доля правильныхответов» или «число правильных ответов».Постановка задачи оптимизации моделей вычисления оценок (и многих других моделей)может быть записана в терминах систем неравенств. Для простоты ограничимся случаемдвух классов и моделью (а,а,с,а,а,а) .Условием правильного распознавания некоторого контрольного объектаS 'i ∈ K j''является выполнение неравенства Γ1 ( Si ) > Γ2 ( Si ) , если объект из первого''класса, и Γ2 ( Si ) > Γ1 ( Si ) , если объект из второго класса.

Тогда число правильнораспознанных объектов при некотором варианте выбора параметров модели будет равночислу выполненных неравенств системы (*).Γ1 ( Si' ) > Γ2 ( Si' ) , i = 1,2,..., m1 ,Γ2 ( Si' ) > Γ1 ( Si' ) , i = m1 + 1, m1 + 2,..., m(*)71Учитывая, что оценки являются билинейными формами от параметровp1 , p 2 ,... p nиγ 1 , γ 2 ,...γ m , задача оптимизации модели может быть сформулирована следующимобразом: «Найти максимальную совместную подсистему системы (**) и некоторое еерешение».mn∑∑ bj =1 i =1kij(ε ) piγ j > 0 , k = 1,2,..., q ,(**)Данная задача является сложной оптимизационной задачей даже для частного случаялинейной системы, когда в (**) фиксированы параметрыпараметрыε 1 , ε 2 ,...ε n , p1 , p2 ,...

pnилиp1 , p2 ,... pn , γ 1 , γ 2 ,...γ m .Примечание. Фундаментальные теоретические результаты, связанные с исследованиемзадачипоискамаксимальныхсовместныхподсистем,полученывУральскомУниверситете (Мазуров, Хачай). Комбинаторные алгоритмы для задач малойразмерности созданы в ВЦ РАН Катериночкиной Н.Н. В системе «РАСПОЗНАВАНИЕ»используетсяОптимизацияэвристическийстандартногоалгоритм,основанныйфункционалакачестванарелаксационномкакспуске.последовательностьвспомогательных оптимизационных задач в пространстве параметров ε прификсированных p, γ и пространстве p, γ , при фиксированных ε , рассматривалась в /…/.72.