2010 Лекции МОТП. Записки (1185265), страница 4
Текст из файла (страница 4)
для любого его поднабора существуетравный ему поднабор в каком-либо другом классе.Пусть V j − множество тупиковых представительных наборов для класса K j .Оценку объекта S по заданному тупиковому представительному набору uвычисляем по одной из формул:a)Γu ( S ) = B(u , ωS ) , где ω ↔ Ω = {i1 , i1 ,..., i1} (оценка совпадает сблизостью набора и соответствующей ω - части объекта S );21b)Γu ( S ) = γ u B (u , ωS ) (близость умножается на вес набора);c) Γu ( S ) = ( pi1 + pi2 + ...
+ pik ) B (u , ωS ) (вес близости оценивается каксумма весов соответствующих признаков).Тогда Γ j ( S ) =1Vj∑ Γ (S ) .u∈V juВ дальнейшем для краткости прилагательное«тупиковый» будем убирать.Отметим, что для нахождения множества представительных наборов классанеобходимо объединить множества представительных объектов, связанных сотдельными эталонами. Для нахождения же представительных наборов,связанных с фиксированным эталоном, достаточно найти тупиковые тестытаблицы, состоящей из выделенного эталона Sν ∈ Kjи эталоновдополнения CK j данного класса по обучающей выборке.Лекция № 52.4.
Оптимизация моделей распознаванияОписания всех трех приведенных подходов включают неизвестные числовыепараметры. Фактически, каждый из подходов представляет параметрическоемножество алгоритмов распознавания, где конкретный алгоритм задаетсяфиксацией значений параметров.Так в описание тестового алгоритма при голосовании по тупиковым тестаммогут быть введены параметры, характеризующие веса признаков иэталонов.
Пусть выбрано также общее решающее правило c). Тогда модельтестовых алгоритмов Μ T (ε , p, γ , δ ) содержит множество алгоритмов{ AT (ε , p, γ , δ ), ε ≥ 0,1 ≥ p ≥ 0,1 ≥ γ ≥ 0} . Общее число параметров моделиравно 2n + m + l × (l + 1) .Аналогично, модель Μ k ( k , ε , p, γ , δ ) вычисления оценок, в которой системуопорных множеств составляют всевозможные подмножества из k признаков,22является множеством алгоритмов{ Ak (k , ε , p, γ , δ ),1 ≥ k ≥ 0, k − целое,ε ≥ 0,1 ≥ p ≥ 0,1 ≥ γ ≥ 0} . Модельголосования по представительным наборам Μ V ( p, γ , δ ) , при вычисленииоценок объекта по представительному набору согласно c), являетсяпараметрическим множеством алгоритмов { Au (ε , p, δ ), ε ≥ 0,1 ≥ p ≥ 0} .Стандартная постановка задачи поиска наилучших алгоритмов заданноймодели состоит в следующем.Пусть дано параметрическое множество распознающих алгоритмов{ A( y}, y ∈ D} и на нем определен числовой функционал ϕ (A) качестваалгоритм.
Требуется найти такой алгоритм A* ∈ { A} , который доставляетϕ ( A) .экстремум функционалу: ϕ ( A*) = extrA∈{ A}Обычно проблема оптимизации решается следующим образом.T ' nql , аналогичная таблицеПусть задана таблица контрольных объектовобучения, т.е. состоящая из разбитых на l классов m числовых строк –описаний объектовS 'i = ( x1 ( S 'i ), x 2 ( S 'i ),..., xn ( S 'i )) с помощью nпризнаков. Для определенности считаем, чтоS 'i ∈ K j , i = q j −1 + 1, q j −1 + 2,..., q j , q0 = 0, ql = 0 .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Мы будем обычно использовать не данный функционал (доля ошибок), а емуобратную величину – долю правильных ответов.23Пусть используется общее решающее правило c), когда условием правильнойклассификации является выполнение системы из l неравенств.
Тогдаусловием правильного распознавания некоторого объекта Sν ∈ Kjявляетсявыполнение следующей системы неравенств: l jj∑ δ i Γi ( S 'ν ) ≥ δ l +1 , S 'ν ∈ K j ,i =1 l∑ δ i j Γi ( S 'ν ) < δ l j+1 , S 'ν ∉ K j . i =1(7)Пусть Z – система, состоящая из m подсистем (7) относительно переменныхy ∈ D . Тогда задача оптимизации стандартного функционала качестваможет быть сформулирована в терминах систем неравенств следующимобразом.Найти совместную подсистему системы Z при условии y ∈ D ,содержащую максимальное число систем (7), и некоторое его допустимоерешение.2.5.
Оценка информативности признаков и эталоновАлгоритмы вычисления оценок являются удобным инструментом длярешения задач оценки информативности (важности) признаков и эталонов.Под данными характеристиками понимаются числовые оценки того,насколько высок вклад признака/эталона в процессе распознавания.Пусть заданы обучающая и контрольная выборки и некоторый алгоритм.Обозначим через ϕ ( A) значение функционала качества распознаванияалгоритмом, через ϕ ( Ai ) - значение функционала качества алгоритма,построенного по данным обучения без учета i-го признака, а через ϕ ( A j ) значение функционала качества алгоритма, построенного по даннымобучения без j-го эталона.24Определение.
Мерой информативности (весом) признака называетсявеличина pi =ϕ ( A) − ϕ ( Ai ). Мерой представительности (весом) объектаϕ ( A)называется величина γ j =ϕ ( A) − ϕ ( A j ).ϕ ( A)Данный подход естественен, нагляден и пригоден при использовании любогоалгоритма распознавания.При малых выборках данные величины принимают небольшой наборзначений и могут быть грубыми оценками.
В данном случае можноиспользовать другие, эвристические величины, характеризующие фактвлияния признака (объекта).Пусть A – некоторый алгоритм типа вычисления оценок, Γ j ( S 'i ) - оценкаконтрольного объектаS'i за классKj,Γ jfea ( µ ) ( S 'i ) - та же оценка без учетаobj (ν )( S 'i ) оценка контрольного объекта S'i за класс K j безпризнака xµ , Γ jучета эталона Sν .Определение. Мерой информативности (весом) признака называетсяlвеличина pµ =∑ ∑ (Γ ( S ' ) − Γjj =1 S 'i ∈K jifea ( µ )j( S 'i )). Мерой представительностиl∑ ∑ Γ (S ' )j =1 S 'i ∈K jjil(весом) объекта называется величина γ ν =∑ ∑ (Γ ( S ' ) − Γjj =1 S 'i ∈K jiobj (ν )jl∑ ∑ Γ (S ' )j =1 S 'i ∈K jj( S 'i )).i25Данное определение подразумевает, что при удалении признака (эталона)теряется часть сходства объектов к своим классам, и эти потери тем больше,чем более важен данный признак (соответственно объект).Лекция № 63.
Логические закономерности классов.В настоящем разделе будут рассмотрены методы поисказакономерностей вида «если A1 ( S ) & A2 ( S ) & ... & Ak ( S ) то S ∈ K i ». Здесь A1 , A2 ,…, Ak – одноместные предикаты «простейшего вида», зависящие от одногокакого-либо признака. Предполагается, что условия данного видавыполняются если не на всех объектах обучающей выборки из некоторогокласса, то по крайней мере на многих эталонах класса. Отметим, что кданной постановке сводятся задачи выявления логических связей междунабором некоторых независимых величин (признаков) и зависимой. Еслизависимая величина является дискретной, то разбиение на классы задают еезначения, если непрерывной (или с высоким уровнем значности) –интервалами значений.Представительные наборы классов (и их ε - окрестности) также могутрассматриваться как закономерности классов.
Здесь представляет интерес красширению определению понятия представительных наборов путемвведения критериев из качества и создания процедур нахожденияоптимальных наборов. Второй принципиальный вопрос состоит в выборе ε порогов,причем,естественно,данныепорогидолжныбытьиндивидуальными для каждого набора.
В настоящем разделе будетрассмотрен вопрос обобщения представительных наборов – поископтимальных признаковых подпространств и окрестностей значенийпризнаков будут осуществляться в рамках решения различныхоптимизационных задач.Рассмотрим следующее множество элементарных предикатов,параметрически зависящих от числовых неизвестных c j , c j , j = 1,2,..., n :121, c1j ≤ x j ≤ c 2j ,Pj (c , c , x j ) = иначе.0,1jПусть2jΩ ⊆ {1,2,..., n} .Определение.
ПредикатP Ω (c1 , c 2 , x) = & Pj (c1j , c 2j , x j )j∈Ω(1)называется логической закономерностью класса Kλ , если261.Ω12∃ St ∈ Kλ : P (c , c , S t ) = 1,2.Ω12∀ St ∉ Kλ , P (c , c , St ) = 0,3.ϕ ( P Ω (c1 , c 2 , x)) =extrΟ12{ P ( d , d , x )}ϕ ( P Ο (d 1 , d 2 , x)) ,гдеϕ - критерий качества предиката.В 3. поиск экстремума проводится по множеству всевозможныхпредикатов вида (1).Предикат (1), удовлетворяющий только первым двум ограничениям,называется допустимым предикатом рассматриваемого класса.Предикат (1), удовлетворяющий только первому и третьемуограничениям, называется частичной логической закономерностью класса Kλ.Стандартным критерием качества предиката класса Kλ будем называтьследующий критерий: ϕ ( P (c , c , S )) = {Si : Si ∈ K λ , P (c , c , Si ) = 1} .Ω1Ω212Логические закономерности со стандартным критерием качестваимеют простую геометрическую интерпретацию. По данным обучающейвыборки требуется найти прямоугольный гиперпараллелипипед, лежащий внекотором признаковом подпространстве, содержащий максимальное числоэталонов из класса Kλ и только класса Kλ .x i2++St++++++++++x itx i1Рис.1 Геометрическое представление логической закономерностикласса Kλ с опорным эталоном St2.6.1.Нахождение оптимальных логических закономерностей(поиск оптимальных окрестностей представительных наборов ).27Задача поиска логических закономерностей классов для стандартногокритерия качества предикатов является сложной задачей нелинейнойдискретной оптимизации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
