Лекции. ММО. Сенько (all in one) (1185303), страница 16
Текст из файла (страница 16)
, ωn );ε = (ε1 , . . . , εn )- вектор положительных пороговыхкоэффициентов, задающих близость объектов по каждому изпризнаков;(p1 , . . . , pn )-вектор положительных параметров, характеризующихважность признаков,(γ1 , . . . , γn ) вектор положительных параметров, характеризующихважность объектов.Сенько Олег Валентинович ()МОТП, лекция 927 / 30Алгебраическая коррекцияДля того, чтобы описать условия существования корректногоалгоритма в алгебраическом замыкании подмножества алгоритмовfвычисления оценок введём дополнительные определения.
Пусть Mнекоторое множество допустимых объектов.Определение 5. Объекты su и sν с описаниями (xu1 , . . . , xun ) иf,(xν1 , . . . , xνn ) называются изоморфными относительно множества Mfесли для произвольного объекта s с описанием (a1 , . . . , an ) ∈ Mвыполняются равенство(| xu1 − a1 |, . . . , | xun − an |) = (| xν1 − a1 |, . .
. , | xνn − an |)Нетрудно видеть что корректный алгоритм в рамках моделивычисления оценок по формуле (7) не может существовать для задачиZ(I, Sec , Pt1 , . . . , PtL ) случаях, когда оказываются выполненнымиследующие два условия.Сенько Олег Валентинович ()МОТП, лекция 928 / 30Алгебраическая коррекцияв выборке Sec существует два объекта s0 и s00 , изоморфныхотносительно выборки эталонов See , которая вместе со своейинформационной матрицей образует начальную информацию I;объекты s0 и s00 принадлежат двум непересекающимся классам.Действительно в этом случае векторы оценок [Γ1 (s0 ), .
. . , ΓL (s0 )] и[Γ1 (s00 ), . . . , ΓL (s00 )] , вычисляемые произвольным оператором измодели АВО будут одинаковы. Следовательно никакое множествооператоров модели АВО не может вычислять базис впространстве вещественных матриц размера L × q.Будем называть задачу Z(I, Sec , Pt1 , . . . , PtL ) регулярной привыполнении трёх условий:никакие два класса полностью не совпадают, т.е. Kl0 6= Kl00 приl0 6= l00 ;никакие два объекта из Sec не являются изоморфнымиотносительно выборки эталонов See ;TSee Sec = ØСенько Олег Валентинович ()МОТП, лекция 929 / 30Алгебраическая коррекцияСправедлива следующая теорема.Теорема 2.
Алгебраическое замыкание подкласса алгоритмов моделиАВО, в которой оценки за классы вычисляются по формуле (5)корректно над множеством регулярных задач.Сенько Олег Валентинович ()МОТП, лекция 930 / 30Лекция 10Коллективные метод,бэггинг, бустинг, голосование по системам закономерностейЛектор – Сенько Олег ВалентиновичКурс «Математические основы теории прогнозирования»4-й курс, III потокСенько Олег Валентинович ()МОТП, лекция 101 / 22Содержание лекции1Коллектиные методы2бэггинг2бустинг3логические закономерности4Статистически взвешенные синдромы5метод комитетовСенько Олег Валентинович ()МОТП, лекция 102 / 22Коллективные методы ("бэггинг")Одним из способов получения ансамбля является использованиеалгоритмов, обученных по разным обучающим выборкам, которыевозникают в результате случайного процесса, лежащего в основеисследуемой задачи.
Обычно при решении прикладной задачи враспоряжении исследователя имеется обучающая выборкаSet = {s1 , . . . , sm } ограниченного объёма. Однако процесс генерациисемейства выборок из генеральной совокупности может бытьимитирован с помощью процедуры бутстрэп (bootstrap), котораяоснована на выборках с возвращениями из Set .
В результатеполучаются выборки Se∗bg , включающие объекты из обучающейвыборки Set . Однако некоторые объекты Set могут встречаться в Se∗bgболее одного раза, а другие объекты отсутствовать. Предположим, чтос помощью процедуры бутстрэп получено T выборок. C помощьюзаранее выбранного метода, используемого для обучения отдельныхалгоритмов распознавания, получим множество, включающее Tebg = {Abg , .
. . , Abg }.распознающих алгоритмов A1TСенько Олег Валентинович ()МОТП, лекция 103 / 22Коллективные методы "бэггинг"Для получения коллективного решения может быть использованпростейший комитетный метод, относящий объект в тот класс, кудаего отнесло большинство алгоритмов . Данная процедура носитназвание бэггинг (bagging), что является сокращением названияBootstrap Aggregating. Процедура бэггинг показывает высокий приростобобщающей способности по сравнению с алгоритмом, обученным спомощью базового метода по исходной обучающей выборке Set , в техслучаях, когда вариационная составляющая ошибки базового методавысока. К таким моделям относятся в частности решающие деревья инейросетевые методы.
При использовании в качестве базового методарешающих деревьев процедура бэггинг приводит к построениюансамблей решающих деревьев (решающих лесов).Основной идеей алгоритма бустинг является пошаговое наращиваниеансамбля алгоритмов. Алгоритм, который присоединяется к ансамблюна шаге k обучается по выборке, которая формируется из объектовисходной обучающей выборки Set .Сенько Олег Валентинович ()МОТП, лекция 104 / 22Коллективные методы "бустинг"В отличие от метода бэггинг объекты выбираются не равноправно, аисходя из некоторого вероятностного распределения, заданного навыборке Set .
Данное распределение вычисляется по результатамклассификации с помощью ансамбля, полученного на предыдущемшаге. Приведём схему одного из наиболее популярных вариантовметода бустинг AdaBoost (Adaptive boosting) более подробно. На1 )первом шаге присваиваем начальные значения весов (w11 , . . . , wmобъектам обучающей выборки. Поскольку веса имеютPвероятностную1интерпретаци, то для них соблюдаются ограничения mj=1 wj = 1,wj1 ∈ [0, 1].
Обычно начальное распределение выбирается1, j = 1, . . . , m. Выбираем число итераций T . Наравномерным wj1 = mитерации k генерируем выборку Sekbs из исходной выборки Set согласноk ). Обучаемраспределению задаваемому весами (w1k , . . . , wmebsраспознающий алгоритм Absk по выборке Sk .Сенько Олег Валентинович ()МОТП, лекция 105 / 22Коллективные методы, "бустинг".Pk kВычисляем взвешенную ошибку по формуле εk = mj=1 wj ej , гдеbskej = 1, если алгоритм Ak неправильно классифицировал объект sj иekj = 0 в противном случае.
В том случае, если εk ≥ 0.5 или εk = 0игнорируем шаг и заново генерируем выборку Sekbs исходя из весовых1коэффициентов wj1 = m, j = 1, . . . , m. В случае если εk ∈ (0, 0.5)εkвычисляем коэффициенты τk = 1−εkи пересчитываем веса объектов по формулеkwjk+1wjk (τk )1−ej=Pmk1−ejkj=1 wj (τk )(1)при j = 1, . . . , m.Процесс, задаваемый формулой (1), продолжается до тех пор, пока невыполнено T итераций . В результате мы получаем совокупность из Tbsраспознающих алгоритмов Abs1 , . . . , AT .Сенько Олег Валентинович ()МОТП, лекция 106 / 22Коллективные методы, "бустинг".Предположим, что нам требуется распознать объект s∗ .
Пустьk ∗βlk (s∗ ) = 1, если s∗ отнесён алгоритмом Absk в класс Kl , и βl (s ) = 0 в∗противном случае. Оценка объекта s за класс Kl вычисляется поформулеTX1∗Γl (s ) =ln βlk (s∗ ).τkk=1s∗Объектбудет отнесён к классу, оценка за которой максимальна.Описанный вариант метода носит название AdaBoost. M1.Эффективность процедур бустинга подтверждается многочисленнымиэкспериментами на реальных данных. В настоящее время существуетбольшое количество вариантов метода, имеющих разное обоснование.Сенько Олег Валентинович ()МОТП, лекция 107 / 22Коллективные методы, основанные на голосовании по системамзакономерностейОдним из эффективных подходов к решению задач прогнозирования ираспознавания является использование коллективных решений посистемам закономерностей. Под закономерностью понимаетсяраспознающий или прогностический алгоритм, определённый нанекоторой подобласти признакового пространства или связанный снекоторым подмножеством признаков.
В качестве примеразакономерностей могут быть приведены представительные наборы,являющиеся по сути подмножествами признаковых описаний,характерных для одного из распознаваемых классов. Аналогомпредставительный наборов в задач с вещественнозначнойинформацией являются логические закономерности классов. Подлогической закономерностью класса Kl понимается областьпризнакового пространства, имеющая форму гиперпараллелепипеда исодержащая только объекты из Kl .Сенько Олег Валентинович ()МОТП, лекция 108 / 22Логическая закономерностьРис 1. Пример логической закономерности.Сенько Олег Валентинович ()МОТП, лекция 109 / 22Логическая закономерностьЛогическая закономерность класса Kj , которую обозначим r(j),описывается с помощью предикатов видаr(j)P tir(j)= ”air(j)≤ Xi ≤ bi(2)где i = 1, .
. . , n. Отметим, что для несущественных дляr(j) r(j)закономерности r(j) признаков отрезок [ai , bi ] соответствуетобласти допустимых значений Xi . Для существенных признаковr(j) r(j)отрезок [ai , bi ] является некоторым подмножеством областидопустимых значений Xi . Полностью r(j) задаётся конъюнкциейпредикатов (2):r(j)Ptr(j) = P tiСенько Олег Валентинович ()& . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
