Лекция 5. Принцип частичной прецедентности_ тестовый алгоритм_ модель ABO (2015 Лекции (Сенько)), страница 2
Описание файла
Файл "Лекция 5. Принцип частичной прецедентности_ тестовый алгоритм_ модель ABO" внутри архива находится в папке "2015 Лекции (Сенько)". PDF-файл из архива "2015 Лекции (Сенько)", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
. . , jr }, что | xuj 0 − xvj 0 |> εj 0 .Главным требованием при выборе ε-порогов является достижениемаксимальной отделимости объектов разных классов при сохранениисходства внутри классов. Поиск тупиковых тестов и тупиковыхпредставительных наборов при модифицированных определенияханалогичен их поиску в первоначальных вариантах методов.Сенько Олег Валентинович ()МОТП, лекция 213 / 24Алгоритмы вычисления оценокТестовый алгоритм и алгоритм с представительными наборамиявляются частью более общей конструкции, основанной на принципечастичной прецедентности и носящей название алгоритмоввычисления оценок.
Существует много вариантов моделей данноготипа. Причём конкретный вид модели определяется выбраннымиспособами задания различных её элементов. Рассмотрим основныесоставляющие модели.Задание системы опорных множеств. Под опорными множествамимодели АВО понимается наборы признаков, по которымосуществляется сравнение распознаваемых и эталонных объектов.Примером системы опорных множеств является множество тупиковыхтестов. Система опорных множеств ΩA некоторого алгоритма A можетзадаваться через систему подмножеств множества {1, . . .
, n} иличерез систему характеристических бинарных векторов.Сенько Олег Валентинович ()МОТП, лекция 214 / 24Алгоритмы вычисления оценокКаждому подмножеству {1, . . . , n} может быть сопоставлен бинарныйвектор размерности n . Пусть {i1 , . . . , ik } ⊆ {1, . . . , n}. .Тогда{i1 , . . . , ik } сопоставляется вектор ω = (ω1 , . . . , ωn ) , всекомпоненты которого равны 0 кроме равных 1 компонент(ωi1 , .
. . , ωik ). . Теоретические исследования свойств тупиковых тестовдля случайных бинарных таблиц показали, что характеристическиевекторы для почти всех тупиковых тестов имеют асимптотически (принеограниченном возрастании размерности таблицы обучения) одну иту же длину. Данный результат является обоснованием выбора вкачестве системы опорных векторов всевозможных наборов,включающих фиксированное число признаков k илиΩA = {ω :| ω |= k}Оптимальное значение k находится в процессе обучения или задаётсяэкспертом. .Сенько Олег Валентинович ()МОТП, лекция 215 / 24Алгоритмы вычисления оценокДругой часто используемой системе опорных множеств соответствуетмножество всех подмножеств {1, . . . , n} за исключением пустогомножества.
Иными словами в систему опорных множеств входитпроизвольный набор признаков или Ω = {ω}\ω0 , где ω0 - вектор, всекомпоненты которого равны 0.Задание функции близости. Пусть опорное множество {i1 , . . . , ik }соответствует характеристическому вектору ω . Фрагмент(xµi1 , . . . , xµik ) описания (xµ1 , . . .
, xµn ) объекта sµ называется ωчастью объекта sµ .Под функцией близости Bω (sµ , sν ) понимается функция отсоответствующих ω-частей сравниваемых объектов, принимающаязначения 1 (объекты близки) или 0 (объекты удалены). Функцииблизости обычно задаются с помощью порговых параметров(ε1 , . . . , εn ), характеризующих близость объектов по отдельнымпризнакам.Сенько Олег Валентинович ()МОТП, лекция 216 / 24Алгоритмы вычисления оценокПример функций близости.1) Bω (sµ , sν ) = 1, если при произвольном i ∈ {1, .
. . , n}, при которомωi = 1, всегда выполняется неравенство| xµi − xνi |< εi .Bω (sµ , sν ) = 0,, если существует такое i0 ∈ {1, . . . , n}, чтоодновременно ωi0 = 1 и | xµi0 − xνi |> ε0i .2) Пусть ε - скалярный пороговый параметр. Функция Bω (sµ , sν ) = 1,если выполняется неравенство[nXωi | xµi − xνi |] < ε.i=1В противном случае Bω (sµ , sν ) = 0.Сенько Олег Валентинович ()МОТП, лекция 217 / 24Алгоритмы вычисления оценок (АВО)Важным элементом АВО является оценка близости распознаваемогообъекта s∗ к эталону sµ по заданной ω- части. Данная оценкаблизости, которая будет обозначаться Γω (s∗ , sµ ), формируется наоснове введённых ранее функций близости и, возможно,дополнительных параметров.A)Γω (s∗ , sµ ) = Bω (s∗ , sµ ).B)Γω (s∗ , sµ ) = pω Bω (s∗ , sµ ),где pω - параметр, характеризующий информативность опорногомножества с характеристическим вектором ω.nXC)Γω (s∗ , sµ ) = γµ (pj ωj )Bω (s∗ , sµ ),j=1где γµ - параметр, характеризующий информативность эталонногообъекта sµ , параметры p1 , .
. . , pn характеризуют информативностьотдельных признаков.Сенько Олег Валентинович ()МОТП, лекция 218 / 24Алгоритмы вычисления оценок (АВО)Оценка объекта s∗ за класс Kl при фиксированном ω. Оценка объектаs∗ за класс Kl при фиксированном характеристическом векторе ωможет вычисляться как среднее значение близости s∗ к эталоннымобъектам из класса Kl1 XΓω (s∗ , sµ ).Γlω (s∗ ) =mlsµ ∈KlОбщая оценка s∗ за класс Kl вычисляется как сумма оценок Γlω (s∗ ) поопорным множествам из системы ΩA :XΓl (s∗ ) =Γlω (s∗ ).(1)ω∈ΩAНаряду с формулой (1) используется формулаXΓl (s∗ ) = νlΓlω (s∗ ).(2)ω∈ΩAСенько Олег Валентинович ()МОТП, лекция 219 / 24Алгоритмы вычисления оценок (АВО)Использование взвешивающих параметров ν1 , .
. . , νL позволяетрегулировать доли правильно распознанных объектов K1 , . . . , KL .Прямое вычисление оценок за классы по формулам (1) и (2) вслучаях, когда в качестве систем опорных множеств используютсянаборы с фиксированным числом признаков или всевозможныенаборы признаков, оказывается практически невозможным при скольлибо высокой размерности признакового пространства из-занеобходимости вычисления огромного числа значений функцийблизости. Однако при равенстве весов всех признаков существуютэффективные формулы для вычисления оценок по формуле (1).Предположим, что оценки близости распознаваемого объекта s∗ кэталону sµ по заданной ω - части вычисляются по формуле (A). Тогдаоценка по формуле (1) принимает видX XΓl (s∗ ) =Bω(s∗ ,sµ )ω∈ΩA sµ ∈KlСенько Олег Валентинович ()МОТП, лекция 220 / 24Алгоритмы вычисления оценок (АВО)PРассмотрим сумму ω∈ΩA Bω (s∗ , sµ ) .
Предположим, что общеечисло признаков, по которым объект s∗ близок к объекту sµ равноd(s∗ , sµ ) . Иными словами d(s∗ , sµ ) =| D(s∗ , sµ ) |, гдеD(s∗ , sµ ) = {i :| x∗i − xµi |< εi } . Очевидно функция близостиBω (s∗ , sµ ) = 1 тогда и только тогда, когда опорное множество,задаваемое характеристическим вектором ω , полностью входит вмножество D(s∗ , sµ ) .
Во всех остальных случаях Bω (s∗ , sµ ) = 0.Сенько Олег Валентинович ()МОТП, лекция 221 / 24Алгоритмы вычисления оценок (АВО)Предположим, что система опорных множеств удовлетворяет условиюΩA = {ω :| ω :|= k} . Очевидно, что число опорных множеств в ΩA ,kудовлетворяющих условию Bω (s∗ , sµ ) = 1 , равно Cd(s. Откуда∗ ,sµ )Pkследует, что ω∈ΩA Bω (s∗ , sµ ) = Cd(s.
Следовательно оценка по∗ ,sµ )формуле (1) может быть записана в видеΓl (s∗ ) =1 Xkγµ Cd(s∗ ,sµ )ml(3)sµ ∈KlПредположим, что система ΩA включает в себя всевозможныеопорные множества. В этом случае число опорных множеств в ΩA ,удовлетворяющих условию Bω (s∗ , sµ ) = 1 , равно 2d(s∗ ,sµ ) − 1 .Следовательно оценка по формуле (1) может быть записана в видеΓl (s∗ ) =1 Xγµ [2d(s∗ ,sµ ) − 1].mlsµ ∈KlСенько Олег Валентинович ()МОТП, лекция 222 / 24Обучение АВОДля обучения алгоритмов АВО в общем случае может бытьиспользован тот же самый подход, который используется дляобучения в методе «Линейная машина».
Предположим, что решаетсязадача обучения алгоритмов для распознавания объектов ,принадлежащихTклассам K1 , . . . , KL При правильного распознаванияобъекта si ∈ Set Kl должен выполняться блок неравенствΓl (si ) > Γl0 (si ),(4)где l0 ∈ {1, . . . , L} \ {l}.
При использовании для вычисления оценокформулы (3) блок (4) приводится к виду1 X1 Xkkγµ Cd(s>γµ Cd(s∗ ,sµ )∗ ,sν )mlmlsµ ∈KlСенько Олег Валентинович ()sν ∈Kl0МОТП, лекция 223 / 24Обучение АВООбучение сводится к поиску такого набора весовых коэффициентовγ1 , . . . , γm при которых выполняется по возможности максимальноечисло блоков неравенств вида (4). Поиск максимальной оптимальныхкоэффициентов может производиться с использованиемэвристического релаксационного метода, аналогичного тому, что былиспользован при обучении алгоритма «Линейная машина».Сенько Олег Валентинович ()МОТП, лекция 224 / 24.