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

МАТЕМАТИЧЕСКИЕОСНОВЫ ТЕОРИИПРОГНОЗИРОВАНИЯЛекторСенько Олег ВалентиновичЛекция IЗадачи диагностики и прогнозирования некоторойвеличины Y по доступным значениямX 1, , X nпеременныхчасто возникают вразличных областях человеческой деятельности:- постановка медицинского диагноза по результатаманализов;- прогноз результатов лечения;- прогноз свойств ещё не синтезированногохимического соединения по его молекулярнойформул;- диагностика хода технологического процесса;- Диагностика состояния техническогооборудования;- прогноз финансовых индикаторов;- и многие другие задачиТипы прогнозируемых величинПрогнозируемая величина Y может иметь различную природу:-принимать значения из отрезка непрерывной оси;принимать значения из конечного множества;являться кривой, описывающей вероятность дожития до какого-то моментавремени.Вслучаях когда прогнозируемая величина являетсякатегориальной и принимает значения из множества,содержащего несколько элементов,элементов задачу прогнозированияпринято называть задачей распознавания.Методы, основанные на обучениипо прецедентамВ случаях, когда существует выборка прецедентов, для которыхизвестны значения прогнозируемойвеличины Y ипеременных X 1 ,  , X nдля решения задачпрогнозирования могут быть использованы методы, основанныеупо прецедентам.р ц дВыборкур у прецедентовр ц дприняторна обученииназыватьОбучающейущ выборкойрОбучающая выборка имеет вид St  {( y1 , x1 ), ,( ym , x m )} ,где y j - значение переменной Y для jj-гого объекта;x j - значение вектора переменных X 1 ,  , X n для j-го объекта;j  1, , m ;m - число объектов в St ;Методы, основанные на обучениипо прецедентамВ процессе обучения производится поиск эмпирическихзакономерностей,связывающихпрогнозируемуюX 1, , X nпеременную Y с переменными.Данные закономерности далее используются припрогнозированиипрогнозировании.Методы, основанные на обучении по прецедентам, такжеприняторо называтьаз аМетодами машинного обучения (Machine learning)ПримерыПримерыСпособы поиска закономерностейОсновным способом поиска закономерностей является поиск внекоторомаприоризаданномсемействеалгоритмовпрогнозированияM  { A : X  Y}алгоритма,наилучшим образомаппроксимирующей связьподмножества переменных набораX 1 ,  , X n с переменнойY на обучающей выборке,где X - область возможных значений векторов переменных ,,X 1 ,  , X n Y - область возможных значений переменной .

YПустьпотерь , произошедших в результате[ y j , A( x j )] - величина “потерь”A( x j )использованияв качестве прогноза значения Y . Тогдаодним из способов обучения является минимизация функционалаэмпирического риска на обучающей выборкеQ ( St , A) m1mj 1[ y j , A( x j )]Способы поиска закономерностейЧЧастныеслучаи ффункции потерьб[ y j , A( x j )]  [ y j  A( x j )]2 квадрат ошибки[ y j , A( x j )] | y j  A( x j ) | модуль ошибкиВ случаеузадачидраспознаваниярфункцияфу ц потерьр можетбыть равной 0 при правильной классификации и 1в при ошибочном. При этом функционалэмпирического риска равен числу ошибочныхбклассификаций.Обобщающая способностьТочность алгоритма прогнозирования на всевозможных новых неиспользованных для обучения объектах, которые возникают врезультате процесса,процесса соответствующего рассматриваемойзадаче прогнозирования принято называтьОбобщающей способностьюИными словами обобщающую способность алгоритмапрогнозирования можно определить как точность на всейгенеральной совокупности.

Мерой обобщающей способностислужитуE {[Y , A( x)]}   [Y , A( x)]P ( d  )Обобщающая способностьМатематическое ожидание берётсяб ёповероятностному пространству содержащему всевозможные объектыпроцесса, соответствующего решаемойзадачеПри решении задач прогнозированияосновной целью является достижениемаксимальной обучающей способностиЭффект переобученияM  { A : X  Y} , увеличение её• Расширение моделисложности всегда приводит к повышению точностиаппроксимации на обучающей выборке.

Однакоповышение точности на обучающей выборке, связанноес увеличением сложности модели, часто не ведёт кувеличению обобщающей способности. Более того,обобщающая способность можетдаже снижаться.Различие между точностью на обучающей выборке иобобщающей способностью при этом возрастает.Данный эффект называется эффектом переобучения.Эффект переобученияЭффект переобученияДля какого алгоритма достигаетсямаксимальная обобщающая способность?Для произвольного прогнозирующего алгоритма величина мматематическое ожидание риска в точке x записываетсякак[Y , A(x)]Px ( d ,) гдеPx ( a )  P ( a ) / P[( x)](x)( x) - множество объектов для которых векторравен x2[Y,A(x)][YA(x)]В случае, если[Y  A( x)]2 Px ( d  ) [Y  E ( x )Y  E ( x )Y  A( x)]2 Px ( d  ) {[Y  E ( x )Y ]2  [ E ( x )Y  A( x)]2  2[ E ( x )Y  A( x)][Y  E ( x )Y ]}Px ( d  )(x)X 1, , X n[Y , A( x)]Px ( d  ) (x)(x)(x)Для какого алгоритма достигаетсямаксимальная обобщающая способностьОднако {2[ E ( x )Y  A(x)][Y  E ( x )Y ]}P(d ) (x)2[ E ( x )Y  A( x)](x){[Y  E ( x )Y ]}P ( d  ) 0xОткуда следует, что(x)[Y  A( x)]2 Px ( d  )  [ E ( x )Y  A( x)]2 [Y  E ( x )Y ]2 Px ( d  ) (1)(x)Из формулы (1) хорошо видно, что наилучший прогноздолжен обеспечивать алгоритм вычисляющий прогнозE ( x )Y  E (Y | x)равныйДля какого алгоритма достигаетсямаксимальная обобщающая способностьБайесовский классификаторПусть в точкеобъекты из классовx  RnK1 ,  , K Lвстречаются с вероятностямиP ( K1 | x),  , P ( K L | x) .Тогда распознаваемыйобъектобе со ззначениема е е векторае ора прогностическихро ос еспеременных x должен быть отнесён в класс K*с максимальным значением P ( K* | x)Байесовский классификаторПокажем,чтоприсправедливостипредположения о том, что всю доступнуюинформациюфо распределении объектовбпоклассам содержат переменные X 1 ,  , X n,байесовский классификатор обеспечиваетнаименьшую ошибку распознавания.ППустьиспользуется классификатор,фотносящиййклассам K1 ,  , K L доли объектов 1 ,  , L , соответственно.Байесовский классификаторПоэтому объекты,ботнесённые в класс K i попрежнему распределены с вероятностямиP ( K1 | x),  , P ( K L | x) , а вероятность ошибочныхрешений среди объектов отнесённых в класс K iсоставляет1  P ( K i | x)Общая вероятность ошибочных классификаций вточке x составляетL [1  P( Ki 1iLi| x)]  1   i P ( K i | x)i 1(1)Байесовский классификаторЗадача поиска минимума ошибкиЗб (2) сводится к задачелинейного программированияL P( Ki 1i| x)  maxiпри ограниченияхLi 1i  0i1прирi  1,, , LБайесовский классификаторРешение задачи линейного программирования находитсяв вершине симплекса задаваемого ограничения и являетсяббинарнымвектором размерности L(0, …, 1, …, 0).

При этом 1 находится в позиции,соответствующей максимальной условной вероятностиP ( K i | x)МЕТОДЫ ПРОГНОЗИРОВАНИЯ• ООднако для вычисления условных математическихожиданий E (Y | x)или условных вероятностей• P ( K i | x) необходимызнаниявероятностныхраспределений, присущих решаемой задаче. Дляподавляющего числа приложений ни общий видраспределенийраспределений,ни значения конкретных ихпараметров неизвестны.• В связи с эти возникло большое числоразнообразных подходов к решению задачпрогнозирования, использование которых позволялодобиваться определённых успехов при решенииконкретных задач.МЕТОДЫ ПРОГНОЗИРОВАНИЯ• ССтатистические методы• Линейные модели регрессионного анализа• Различные методы,методы основанные на линейнойразделимости• Методы, основанные на ядерных оценках• Нейросетевые методы• Комбинаторно-логическиео б а ор о о ес е методые од и аалгоритмыорвычисления оценок• Алгебраические методы• Решающие или регрессионные деревья и леса• Методы, основанные на опорных векторахЭмпирические методы оценкиобобщающей способностиОбобщающаяОббспособностьбможет оценивать по случайнойй йвыборке объектов из одной и той же генеральнойсовокупности,у, соответствующейу щисследуемомудуу процессу,р ц у,которую принято называть контрольной выборкой.Контрольная выборка не должна содержать изобучающей выборки.выборки• Контрольная выборка имеет вид Sc  {( y1 , x1 ), ,( ymc , x mc )}где y j - значение переменной Y для j-го объекта;x j - значение вектора переменных X 1 ,  , X nдля j-гообъекта;mc - число объектов в Sc ;Эмпирические методы оценкиобобщающей способности• Обобщающая способность A можетцс помощью фуфункционалацоцениватьсярискаQ ( Sc , A) Причисел1mmcj 1[ y j , A( x j )]mc  Q ( Sc , A)согласно закону большихE {[Y , A( x)]}Эмпирические методы оценкиобобщающей способностиОбОбычнопри решении задачи прогнозирования попрецедентам в распоряжении исследователей сразуоказывается весь массив существующихущу щ эмпирическихрданных Sin .

Для оценки точности прогнозированиямогут быть использованы следующие стратегии.Sin случайным1) ВыборкаВ бйобразомбрасщепляется навыборку St для обучения алгоритма прогнозированияи выборку Sc для оценки точности2) Процедура кросс-проверки. Выборка Sin случайнымобразом расщепляется на выборки S A и SB . Напервом шаге S A используется для обучения и SB дляконтроля. На следующем шаге S A и SB меняютсяместамиЭмпирические методы оценкиобобщающей способности• 3) Процедура скользящего контроля выполняется пополной выборке Sin заm | Sin | шагов .jSна j -ом шаге формируется обучающая выборка t  Sin \ s j ,где s j  ( y j , x j )j- ый объект Sin ,и контрольная выборка Sc , состоящая из единственногообъекта s j .ППроцедураскользящего контроля вычисляет оценкуобобщающей способностиm1Qsc ( Sin , A)   [ y j , A( x j , St j )]m j 1Несмещённость оценки скользящегоконтроляПусть  m вероятностное пространство, элементамикоторого являются выборки по m объектов изгенеральной совокупности, соответствующейрассматриваемому процессуПод несмещённостью оценки скользящего контроляпонимается выполнение следующего равенстваE m {Qsc [ Sm , A]}  Em 1 E {[Y , A( x, Sm 1 )]}Несмещённость оценкискользящего контроляПокажем, что несмещённость имеет место, если выборкаSin является случайной выборкой из одной и той жегенеральной совокупности.совокупностиВ этом случае пространство  m явлется декартовымпроизведением m пространств  (  m       )с вероятностной мерой P m , удовлетворяющей условиюmP (a1    a m )   P (ai )mi1Несмещённость оценкискользящего контроляm1E m {Qsc [ Sm , A]  E m {  [ y j , A( x j , St j )]} m j 11 m j )]}E{[y,A(x,Sjjtm j 1 mОднако выборка S j является элементом пространства  m.1t( y j , x j ) является элементом  .

ООбОбъектОткудаE m {[ y j , A( x j , St j )]}  E m 1 E {[Y , A( x, Sm 1 )]}и )]}E m {Qsc [ Sm , A]}  EmE{[Y,A(x,Sm 1m 1.