Лекция 1. Задачи прогнозирования_ обобщающая способность_ скользящий контроль (2014 Лекции (Сенько))

Лекция 1Задачи прогнозирования,обобщающая способность, байесовский классификатор,скользящий контрольЛектор – Сенько Олег ВалентиновичКурс «Математические основы теории прогнозирования»4-й курс, III потокСенько Олег Валентинович ()МОТП, лекция 11 / 50Содержание лекции1Основные понятия теории прогнозирования по прецедентам2Обобщающая способность и эффект переобучения3Байесовский классификатор4Поиск оптимальных алгоритмов прогнозирования5Методы оценки обобщающей способности и скользящийконтрольСенько Олег Валентинович ()МОТП, лекция 12 / 50Задачи прогнозированияЗадачи диагностики и прогнозирования некоторой величины Y подоступным значениям переменных X1 , .

. . , Xn часто возникают вразличных областях человеческой деятельности:постановка медицинского диагноза или результатов лечения посовокупности клинических и лабораторных показателей;прогноз свойств ещё не синтезированного химическогосоединения по его молекулярной формул;диагностика хода технологического процесса;диагностика состояния технического оборудования;прогноз финансовых индикаторов;и многие другие задачиСенько Олег Валентинович ()МОТП, лекция 13 / 50Модели прогнозированияДля решения подобных задач могут быть использованы методы,основанные на использовании точных знаний. Например, могутиспользоваться методы математического моделирования, основанныена использовании физических законов. Однако сложность точныхматематических моделей нередко оказывается слишком высокой.Кроме того при использовании физических моделей часто требуетсязнание различных параметров, характеризующих рассматриваемоеявление или процесс.

Значения некоторых из таких параметров частоизвестны только приблизительно или неизвестны вообще. Все этиобстоятельства ограничивают возможности эффективногоиспользования физических моделей.Сенько Олег Валентинович ()МОТП, лекция 14 / 50Прогнозирования по прецендентамВ прикладных исследованиях нередко возникают ситуации, когдаматематическое моделирование, основанное на использовании точныхзаконов оказывается затруднительны, но в распоряженииисследователей оказывается выборка прецедентов - результатовнаблюдений исследуемого процесса или явления, включающихзначения прогнозируемой величины Y и переменных X1 , .

. . , Xn . Вэтих случаях для решения задач диагностики и прогнозирования могутбыть использованы методы, основанные на обучении по прецедентам.Сенько Олег Валентинович ()МОТП, лекция 15 / 50Типы переменных Y, X1 , . . . , XnВ задачах и методах, рассматриваемых в настоящем курсе,переменные X1 , . . . , Xn являются непрерывными или дискретнымискалярными величинами. При этом переменная Xi считаетсянепрерывной, если она принимает значения из некоторогоподмножества R, имеющего мощность континуума.

Например,непрерывная переменная может принимать значения из некоторогоинтервала числовой оси. Непрерывные переменные также называютвещественными. Переменная Xi считается дискретной, если онапринимает значения из некоторого конечного или счётного множестваdei . Дискретная переменная Xi называется порядковой, еслисуществует нумерация элементов dei , соответствующая общепринятымпредставлениям об их взаимной близости. В противном случае Xiназывается номинальной. Следует выделить также бинарныепеременные, принимающие значения из множества с двумяэлементами Обычно такие переменные указывают на наличие илиотсутствие какого-либо свойства у описываемых объектов.Сенько Олег Валентинович ()МОТП, лекция 16 / 50Типы задач прогнозированияПрогнозируемая величина Y также может иметь различную природу.Методы прогнозирования разделяются в зависимости от типапрогнозируемой величины.Задачи прогнозирования непрерывной Y обычно решаются спомощью методов регрессионного анализа.Задачи, в которых прогнозируемая величина принимает значенияиз множества, содержащего относительно небольшое числоэлементов, принято называть задачей распознавания.

Например, кзадачам распознавания относятся задачи прогнозированияноминальных переменных.Следует выделить также задачи, в которых Y являться кривой,описывающей вероятность возникновения некоторогокритического события до различных моментов времени.Подобные задачи решаются с помощью методов анализавыживаемости (надёжности).Сенько Олег Валентинович ()МОТП, лекция 17 / 50Описания прогнозируемых объектовОтметим, что всегда можно построить взаимно-однозначноесоответствие между областью значения лискретной переменной инекоторым множеством чисел. Поэтому переменные X1 , .

. . , Xnпрактически всегда можно считать числовыми, а множество значенийX1 , . . . , Xn можно считать вектором x в пространстве Rn .Встречаются задачи прогнозирования, в которых переменныеX1 , . . . , Xn являются только вещественными или только дискретными.Однако во многих задачах для прогнозирования используютсяодновременно непрерывные и дискретные переменные.Сенько Олег Валентинович ()МОТП, лекция 18 / 50Прогнозирование по прецедентам.

Генеральная совокупностьПредположим, что задача прогнозирования решается для некоторогопроцесса или явления F . Множество объектов, которые потенциальномогут возникать в рамках F , называется генеральной совокупностью,далее обозначаемой Ω . Предполагается, что прогнозируемая величинаY и переменные X1 , . . . , Xn заданы на Ω. Однако значение Y длянекоторых объектов Ω может по разным причинам оказатьсянедоступным исследователю.

При этом значения по крайней меречасти переменных X1 , . . . , Xn известны. Целью математическихметодов прогнозирования, рассматриваемых в курсе, являетсяпостроение алгоритма, вычисляющего недоступные значений Y поизвестным значениям переменных X1 , . . . , Xn . Обычно генеральнаясовокупность рассматривается как множество элементарных событий,на котором заданы - алгебра событий Σ и вероятностная мера P . Тоесть генеральная совокупность рассматривается как вероятностноепространство hΩ, Σ, P i.Сенько Олег Валентинович ()МОТП, лекция 19 / 50Методы, основанные на обучении по прецедентамПоиск алгоритма, вычисляющего осуществляется по выборкепрецедентов, которая обычно является случайной выборкой объектовиз Ω с известными значениями Y, X1 , . .

. , Xn , Выборку прецедентовтакже принято называть обучающей выборкой.Обучающая выборка имеет вид S̃t = {(y1 , x1 ), . . . , (ym , xm )}, гдеyj – значение переменной Y для объекта sj , j = 1, . . . , m;xj – значение вектора переменных X1 , . . . , Xn для объекта sj ;m – число объектов в S̃t .Сенько Олег Валентинович ()МОТП, лекция 110 / 50Обучающая выборкаОбычно предполагается, что объекты обучающей выборки S̃t случайнои независимо друг от друга извлекаются из генеральной совокупностиΩ. Иными словами предполагается, что S̃t является элементомдекартова произведения Ωm = Ω× .

. . ×Ω. При этом считается, что наΩm задана σ-алгебра Σm , содержащая всевозможные декартовыпроизведения вида a1 × . . . ×am , где ai ∈ Σ, i = 1, . . . , m, ивероятностная мера P m , удовлетворяющая условиюmP (a1 × . . . ×am ) =mYP (ai ).i=1Пусть x1 , . . . , xm значения переменной X на объектах обучающейвыборки S̃t . Тогда x1 , .

. . , xm могут интерпретироваться какнезависимые одинаково распределённые случайные величины(н.о.р.с.в).Сенько Олег Валентинович ()МОТП, лекция 111 / 50Методы, основанные на обучении по прецедентамВ процессе обучения производится поиск эмпирическихзакономерностей, связывающих прогнозируемую переменную Y спеременными X1 , . . . , Xn . Данные закономерности далее используютсяпри прогнозировании.

Методы, основанные на обучении попрецедентам, также принято называть методами машинного обучения(machine learning).Сенько Олег Валентинович ()МОТП, лекция 112 / 50Примеры задач машинного обученияЗадача распознавания (классификации) ириса на три класса. Здесьцелевая переменная Y ∈ {setosa, versicolor, virginica}, признакиX1 , . . . , X4 ∈ R.Классы:SetosaVersicolorVirginicaПризнаки:длина чашелистика (см)ширина чашелистика (см)длина лепестка (см)ширина лепестка (см)Данные: http://archive.ics.uci.edu/ml/datasets/IrisСенько Олег Валентинович ()МОТП, лекция 113 / 50Примеры задач машинного обученияЗадача распознавания рукописных цифр.

Целевая переменнаяY ∈ {0, 1, . . . , 9}, признаки X1 , X2 , . . . , X784 ∈ [0, 255] – пикселыизображения размера 28×28.Примеры объектов:Данные: http://yann.lecun.com/exdb/mnist/Сенько Олег Валентинович ()МОТП, лекция 114 / 50Примеры задач машинного обученияЗадача прогноза стоимости жилья в различныхпригородахБостона(задачавосстановлениярегрессии).Целевая переменная Y – цена жилья. Признаки:уровень криминала в районеконцентрация окисей азотадоля жилья, построенного до 1940 годасреднее расстояние до основных районов концентрации рабочихместуровень налогообложенияотношение числа учителей к числу учеников в школахи другиеДанные: http://archive.ics.uci.edu/ml/datasets/HousingСенько Олег Валентинович ()МОТП, лекция 115 / 50Способы поиска закономерностейОсновным способом поиска закономерностей является поиск внекотором априори заданном семействе алгоритмов прогнозированияM̃ = {A : X̃ → Ỹ } алгоритма, наилучшим образомаппроксимирующего связь переменных из набора X1 , .

. . , Xn спеременной Y на обучающей выборке, гдеX̃ – область возможных значений векторов переменных X1 , . . . , Xn ;Ỹ – область возможных значений переменной Y .Пусть λ[yj , A(xj )] – величина «потерь», произошедших в результатеиспользования A(xj ) в качестве прогноза значения Y . Тогда одним изспособов обучения является минимизация функционалаэмпирического риска на обучающей выборке:m1 Xλ[yj , A(xj )] → min .Q(S̃t , A) =mA∈M̃j=1Сенько Олег Валентинович ()МОТП, лекция 116 / 50Частные случаи функции потерьПри прогнозировании непрерывных величин могут использоватьсяλ[yj , A(xj )] = (yj − A(xj ))2 – квадрат ошибки,λ[yj , A(xj )] = |yj − A(xj )| – модуль ошибки.В случае задачи распознавания функция потерь может быть равной 0при правильной классификации и 1 при ошибочной. При этомфункционал эмпирического риска равен числу ошибочныхклассификаций.Сенько Олег Валентинович ()МОТП, лекция 117 / 50Примеры поиска закономерностейРассмотрим задачу восстановления регрессии по одному признаку.Здесь Ỹ = R, X̃ = R.

Поиск зависимости между регрессионнойпеременной Y и признаком X в рамках семейства отображений M̃осуществляется с помощью минимизации функционала эмпирическогориска с функцией потерь λ[y, A(x)] = (y − A(x))2 (т.н. методнаименьших квадратов).Поиск зависимости в семействе Поиск зависимости в семействелинейных функцийкубических функцийM̃ = {y = ax + b, a, b ∈ R}:M̃ = {y = ax3 + bx2 + cx + d,a, b, c, d ∈ R}:500−5−5−10−10−15−15−20−20−25−25−30−3−2−10Сенько Олег Валентинович ()12−30−33МОТП, лекция 1−2−1012318 / 50Примеры поиска закономерностейРассмотрим задачу классификации на два класса по двум признакам.Здесь Ỹ = {1, 2}, X̃ = R2 .Поиск зависимости в семействе линейных разделителей:(1, если ax1 + bx2 + c ≥ 0,y=2, иначе.3210−1−2−3−3−2−101Сенько Олег Валентинович ()23МОТП, лекция 119 / 50Обобщающая способностьТочность алгоритма прогнозирования на всевозможных новых неиспользованных для обучения объектах, которые возникают врезультате процесса, соответствующего рассматриваемой задачепрогнозирования, принято называть обобщающей способностью.Иными словами обобщающую способность алгоритма прогнозированияможно определить как точность на всей генеральной совокупности.Мерой обобщающей способности служит математическое ожиданиепотерь по генеральной совокупности EΩ {λ[Y, A(x)]}.Сенько Олег Валентинович ()МОТП, лекция 120 / 50Обобщающая способностьОбобщающая способность может быть записана в видеZEΩ {λ[Y, A(x)]} =E{λ[Y, A(x)]|x}p(x)dx1 .