Лекция 2 (2012 Лекции МОТП (Сенько))

МАТЕМАТИЧЕСКИЕОСНОВЫ ТЕОРИИПРОГНОЗИРОВАНИЯЛекторСенько Олег ВалентиновичЛекция 2Методы прогнозирования (распознавания)• Множество (модель) алгоритмовM  {A : X  Y }внутрикоторого производится поиск оптимального алгоритмапрогнозированивместеоптимизационнойзадачисобудемспособомназыватьрешенияметодомпрогнозирования или методом распознавания, еслипрогнозируемаявеличинапринадлежитконечномумножеству. В качестве примера рассмотрим известныйизвестный метод решения задачи распознавания –Линейная машинаЛинейная машинаМетод «Линейная машина» предназначен для решения задачираспознавания с классами K1 ,, K L .

Алгоритм распознавания имеетследующий вид.В процессе обучения классам K1 ,функция от переменных X1 ,:, K L ставятся в соответствие линейные, Xnf1 ( X 1 ,, X n )  w01  w11 X 1   w1n X nf L ( X1,, X n )  w0L  w1L X 1   wnL X nЛинейная машинаТаким образом алгоритм распознавания задаётся матрицей параметров w01 w11 wL wL 0 1w1n wnL Пусть требуется распознать объектx*. Вычисляются значения функцийотнесён классу Ki , i {1,s* ,описание которого задаётся векторомf1 ,, f L в точке x* .

Объектs*будет, L} , если выполняется набор неравенств,fi (x* )  f j (x* ), j {1, , L} \ {i}Линейная машинаМетод обученияПроцесс обучения по выборке St  {( y1, x1 ), ,( ym , xm )}состоит в поиске таких значений параметров, w01 w11 wL wL 0 1w1n wnL при которых максимальное число объектов Stоказывается правильно распознанным, Пусть J ( j )  i , еслиy j  Ki . Максимальная точность на выборке St соответствуетвыполнению максимального числа блоков неравенств.Линейная машинаМетод обученияf J (1) (x1 )  f j (x1 ), j  {1,, L} \ {J (1)}(1)f J ( m ) (x m )  f j (x m ), j  {1,, L} \ {J (m)}Каждый из блоков включает l  1 неравенств. Таким образомсуммарное число неравенств составляет m(l  1) ..

Неравенства из системы (1) могут быть записаны в виде2Ln zi 1 j 12Litjw  ziji 1it0t {1,, m(l  1)} (2)Линейная машинаМетод обученияЕсли в уравнении tблока rJ (r )  i , то z  xrj , z  1itjЕсли в уравненииБлока rсистемы (2), соответствующим номеруit0t системы (2), соответствующим номеруj  i  L , то z itj   xrj , z0it  1itВо всех остальных случаях коэффициенты z j равны 0Для поиска максимальной совместной подсистемы блоковнеравенств системы (1) используется релаксационныйалгоритм.Линейная машинаМетод обучения. Релаксационный алгоритм.• На начальном этапе каждое из уравнений системы (2)•нормируется на величину( L*N )z itjj 1( z itj ) 2• В результате мы переходим к системе неравенств2Ln2Lit iitˆˆzwz j j  0i 1 j 1t {1,, m(l  1)} (3)i 1• Релаксационный алгоритм состоит в вычислении релаксационной(i )последовательности матриц параметров w :W(0) , W(1) ,, W( i ) ,Линейная машинаМетод обучения.

Релаксационный алгоритм.При этом( i 1)W W  (i )(i )(i ), где скаляр  (i ) и матрица (i )вычисляются по невыполненным неравенствам из системыПустьI (i ) - множество неравенств невыполненных на(i )i- ой итерации. Тогда    dt, где d - матрицаttI ( i )размерностипередwij(n  1)  L, в позиции(i, j ) которой стоит коэффициентв t-ом уравнении системы (3).Линейная машинаМетод обучения. Релаксационный алгоритм.• Коэффициент  пропорционален суммарной величиненарушения неравенств из набора I ( i ) , нормированнойна сумму квадратов коэффициентов матрицы  (i )(i )2L(i )2Ln{ zˆ   zˆ w }tI iit0i 1Li 1 j 1n 1 (i 1 j 1ij)2itjijЛинейная машинаМетод обучения.

Релаксационный алгоритм.Процесс поиска решений.Задаётся произвольная начальная точка. В начале каждойитерации подсчитывается число полностью выполненныхблоков неравенств. Если оно максимально относительно(i )Wвсех предыдущих итераций, то текущее приближениезапоминается как лучшее на данный момент решение.Процесс продолжается до выполнения одного из критериевостановки.Линейная машинаМетод обучения. Релаксационный алгоритм.• Критерии остановки1) Отсутствие невыполненных неравенств2) Число итераций превысило некоторую заранее заданнуювеличину3) В течение нескольких итераций число полностьювыполненных блоков неравенств не изменяетсяЛинейная машина.ЗадачаИмеется задача распознавания с 3 мя классами и 2-мяпризнаками.

Предполагается, что с использованиемметода ЛМ для каждого класса найдены линейныеразделяющие функцииf1 ( x1 , x2 )  4.0  2 x1  x2f 2 ( x1 , x2 )  2.0  x1  3 x2f3 ( x1 , x2 )  1.0  x1  2 x2Требуется изобразить на двумерной диаграмме области,соответствующие отнесению классам !, 2 и 3Линейная машина.Решение задачиОбласть, где одновременно выполняются неравенства1) f1 ( x1 , x2 )  f 2 ( x1 , x2 )2) f1 ( x1 , x2 )  f3 ( x1 , x2 )Соответствует классу 1.Неравенства 1 и 2 эквивалентны неравенствам1) 6  x1  2 x2  02) 3  x1  3x2  0Линейная машина.Решение задачиТеоретические подходы к исследованиюобобщающей способностиОбобщающая способность ( ОС) алгоритма прогнозированияможет быть эффективно оценена по выборке данных спомощью методов:А) оценивание ОС на новой контрольной выборкеБ) Кросс-проверкаB) Скользящий контрольТеоретические подходы к исследованию обобщающейспособностиОднако большой интерес представляют теоретическиеметоды оценки обобщающей способности, которыепозволили бы ответить на вопросы:Будет ли обладать достаточной обобщающей способностью,алгоритм прогнозирования, найденный внутри некотороймодели M  {A : X  Y }?Какие требования необходимо предъявить к M , чтобыобеспечить эффективное обучение?Ответы на данные вопросы даёт теория ВапникаЧервоненкиса.Теоретические подходы к исследованию обобщающейспособностиТеория Вапника-ЧервоненкисаДалее будет рассмативается задача распознавания.Предположим,o что по обучающей выборкенайденStSt -  err ( Ao )алгоритм A с минимальной долей ошибок наДостижение высокой обучающей способности соответствуетнизкой доле ошибок на всей генеральной совокупности или,иными словами, низкой вероятности ошибок для алгоритмаAo .ТеорияВапника-Червоненкисаустанавливаетусловиягарантированной сходимости частоты ошибки к еёвероятности при возрастании объёма обучающей выборкТеоретические подходы к исследованию обобщающейспособностиТеория Вапника-ЧервоненкисаПусть k - число ошибочных классификаций, сделанныхна обучающей выборке длины m некоторымагоритмом A .Частота ошибок  err ( A)распределена побиномиальному законуm kk [ p ( A)]k [1  p ( A)]P[ err ( A)]  Cmerrerrгде perr ( A) - вероятность ошибочной классификации для AТеоретические подходы к исследованию обобщающейспособностиТеория Вапника-ЧервоненкисаВероятность выполнения неравенства| err ( A)  perr ( A)| задаётся суммой| k  Perr ( A)|mkkCm [ perr ( A)] [1 perr ( A)]m k (1)Теоретические подходы к исследованию обобщающейспособностиТеория Вапника-ЧервоненкисаВ силу интегральной теоремы Муавра–Лапласа сумма(1) при большихможет быть оценена сверху спомощью выражения: 2m22 2e2 m2 [1  perr ( A)]perr ( A ) где12Таким образомPr{|  err ( A)  perr ( A) |  } 22 m 2 me2 212 me2 2 m( 2)Теоретические подходы к исследованию обобщающейспособностиТеория Вапника-ЧервоненкисаНа самом деле в процессе обучения оценивается большоечисло всевозможных алгоритмов модели .

Алгоритмы сминимальной частотой ошибки могут соответствовать какраз очень высоким отклонения частот от вероятностей.Достижение высокой обобщающей способностигарантируется при выполнении условия равномернойсходимости:P {max |  err ( A)  perr ( A) |  }  0AMприmТеоретические подходы к исследованию обобщающейспособностиТеория Вапника-ЧервоненкисаОбозначим какA m событие, заключающееся в выполнении дляалгоритма A неравенства |  err ( A)  perr ( A) |  навыборкеStдлины m .обучающейТогда, принимая во вниманиенеравенство Буля, получаемP {max |  err ( A)  perr ( A) |  }  P {AMA m } AM P { Am}AMПринимая во внимание неравенство (2) получаемP {max |  err ( A)  perr ( A) |  } lAAAM12 me2 2 m(3)Теоретические подходы к исследованию обобщающейспособностиТеория Вапника-ЧервоненкисаСначала рассмотрим случай когда модель M конечна исодержитN различных алгоритмов.

Тогда очевидноP {max |  err ( A)  perr ( A) |  } AMN2 me2 2 mВ теории Вапника-Червоненкиса предлагается использовать дляоценки разнообразия модели Mчисло входящих в негоалгоритмов, делающих ошибки на одних и тех же объектахобучающей выборки S. tТеоретические подходы к исследованию обобщающейспособностиТеория Вапника-ЧервоненкисаЧисло таких алгоритмов задаётся коэффициентомразнообразия (M,Sl ,) который определяется как числоспособов, которыми S может быть разбита на двеtподвыборки алгоритмами из модели M. . Для оценокналичия равномерной сходимости при обучении помодели M используется функция роста: максимальноезначение коэффициентов разнообразия на множестве mвсевозможных обучающих выборок длины mμ( A,m)  max (M,St )St mТеоретические подходы к исследованию обобщающейспособностиТеория Вапника-ЧервоненкисаУчитывая, что число отличных друг от друга алгоритмов вуказанном ранее смысле ограничено сверху функциейроста, получаем верхнюю оценку вероятностивыполнения неравенства | err ( A)  perr ( A)|  :P {max |  err ( A)  perr ( A) |  } AMμ(M, m)2 me2 2 m( 4)Теоретические подходы к исследованию обобщающейспособностиТеория Вапника-ЧервоненкисаСвойства функции ростаСуществует два типа моделейДля первого типа при любом объёме m существуетвыборка произвольное разбиение которой на дваподмножестваможетбытьреализованоалгоритмами из M .Иными словами μ(M,m)  2m mДля второго типа существует такой объём m *, длякоторого отсутствуют выборки, разделимые на двапротзвольных подмножества алгоритмами из M ,Иными словами  m* μ( A,m* )  2m*Теоретические подходы к исследованию обобщающейспособностиТеория Вапника-ЧервоненкисаВо втором случае говорится, что ёмкость модели Mконечна и равна m * .