Лекции. ММО. Сенько (all in one) (1185303), страница 9
Текст из файла (страница 9)
, 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Лекция 6Нейросетевые методы,перцептрон Розенблатта, многослойный перцептронЛектор – Сенько Олег ВалентиновичКурс «Математические основы теории прогнозирования»4-й курс, III потокСенько Олег Валентинович ()МОТП, лекция 61 / 26Содержание лекции1Нейросетевые методы2перцептрон Розенблатта2многослойный перцептрон3метод обратного распространения ошибкиСенько Олег Валентинович ()МОТП, лекция 62 / 26Нейросетевые методыВ основе нейросетевых методов лежит попытка компьютерногомоделирования процессов обучения, используемых в живыхорганизмах.
Когнитивные способности живых существ связаны сфункционированием сетей связанных между собой биологическихнейронов – клеток нервной системы. Для моделированиябиологических нейросетей используются сети, узлами которыхявляются искусственные нейроны (т.е. математические моделинейронов), Можно выделить три типа искусственных нейронов:нейроны-рецепторы, внутренние нейроны и реагирующие нейроны.Каждый внутренний или реагирующий нейрон имеет множествовходных связей, по которым поступают сигналы от рецепторов илидругих внутренних нейронов.
Пример модели внутреннего илиреагирующего нейрона представлен на рисунке 1.Сенько Олег Валентинович ()МОТП, лекция 63 / 26Нейросетевые методыРис.1. Модель внутреннего или реагирующего нейрона.Представленный на рисунке 1 нейрон имеет r внешних связей, покоторым на него поступают входные сигналы u1 , . . . , ur . Поступившиесигналы суммируются с весами w1 , .
. . , wr . PНа выходе нейронавырабатывается сигнал Φ(z), где z = w0 + ri=1 wi ui , w0 - Pпараметрсдвига.Может быть использована также форма записи z = ri=0 wi ui ,где фиктивный «сигнал» u0 тождественно равен 1.Сенько Олег Валентинович ()МОТП, лекция 64 / 26Нейросетевые методыФункцию Φ(z) обычно называют активационной функцией. Могутиспользоваться различные виды активационных функций, включаяпороговую функцию, задаваемую с помощью пороговой величиныb: Φ(z) = 1 при z ≥ b, Φ(z) = 0 при z < b;- сигмоидная функция Φ(z) =константа;1,1+e−azгде a-вещественнаягиперболический тангенс;тождественное преобразование Φ(z) = z.Методы, основанные на использовании искусственных нейронов могутбыть использованы для решения самых разнообразных задачраспознавания. При этом сигналы, поступающие на вход перцептрона,интерпретируются как входные признаки X1 , .
. . , Xn .Сенько Олег Валентинович ()МОТП, лекция 65 / 26Перцептрон РозенблаттаПервой нейросетевой моделью стал перцептрон Розенблатта,предложенный в 1957 году. В данной модели используетсяединственный реагирующий нейрон. Модель, реализующая линейнуюразделяющую функцию в пространстве входных сигналов, может бытьиспользована для решении задач распознавания с двумя классами,помеченными метками 1 или -1. В качестве активационной функциииспользуется пороговая функция: Φ(z) = 1 при z ≥ 0, Φ(z) = −1 приz < 0. Особенностью модели Розенблатта является очень простая, новместе с тем эффективная, процедура обучения, вычисляющаязначения весовых коэффициентов (w0 , .
. . , wn ). Настройка параметровпроизводится по обучающим выборкам, совершенно аналогичных тем,которые используются для обучения статистических алгоритмов. Напервом этапе производится преобразование векторов сигналов(признаковых описаний) для объектов обучающей выборки. В наборисходных признаков добавляется тождественно равная 1 нулеваякомпонента. Затем вектора описаний из класса K2 умножаются на -1.Вектора описаний из класса K1 не изменяютсяСенько Олег Валентинович ()МОТП, лекция 66 / 26Перцептрон РозенблаттаПроцедура обучения перцептрона. .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
