Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Лекция 5. Принцип частичной прецедентности_ тестовый алгоритм_ модель ABO

Лекция 5. Принцип частичной прецедентности_ тестовый алгоритм_ модель ABO (2015 Лекции (Сенько)), страница 2

PDF-файл Лекция 5. Принцип частичной прецедентности_ тестовый алгоритм_ модель ABO (2015 Лекции (Сенько)), страница 2 (ММО) Методы машинного обучения (63152): Лекции - 10 семестр (2 семестр магистратуры)Лекция 5. Принцип частичной прецедентности_ тестовый алгоритм_ модель ABO (2015 Лекции (Сенько)) - PDF, страница 2 (63152) - СтудИзба2020-08-25СтудИзба

Описание файла

Файл "Лекция 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.

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5076
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее