Лекции. ММО. Сенько (all in one) (2015 Лекции (Сенько))

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

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

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

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

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

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

. . , m;xj – значение вектора переменных X1 , . . . , Xn для объекта sj ;m – число объектов в S̃t .Сенько Олег Валентинович ()ММО - основные понятия7 / 47Обучающая выборкаОбычно предполагается, что обучающая выборка можетрассматриваться как независимая выборка объектов из Ω. Инымисловами предполагается, что S̃t является элементом декартовапроизведения Ωm = Ω× .

. . ×Ω. При этом предполагается, что на Ωmзадана σ-алгебра Σm , содержащая всевозможные декартовыпроизведения вида a1 × . . . ×am , где ai ∈ Σ, i = 1, . . . , m, ивероятностная мера P m , удовлетворяющая условиюP m (a1 × . . . ×am ) =mYP (ai ).i=1Сенько Олег Валентинович ()ММО - основные понятия8 / 47Методы, основанные на обучении по прецедентамВ процессе обучения производится поиск эмпирическихзакономерностей, связывающих прогнозируемую переменную Y спеременными X1 , . .

. , Xn . Данные закономерности далее используютсяпри прогнозировании. Методы, основанные на обучении попрецедентам, также принято называть методами машинного обучения(machine learning).Сенько Олег Валентинович ()ММО - основные понятия9 / 47Типы прогнозируемых величинПрогнозируемая величина Y может иметь различную природу:принимать значения из отрезка непрерывной оси;принимать значения из конечного множества;являться кривой, описывающей вероятность возникновениянекоторого критического события до различных моментоввремени.Задачи, в которых прогнозируемая величина принимает значения измножества, содержащего несколько элементов, принято называтьзадачей распознавания. Например, к задачам распознавания относятсязадачи прогнозирования категориальных переменных.Сенько Олег Валентинович ()ММО - основные понятия10 / 47Примеры задач машинного обученияЗадача распознавания (классификации) ириса на три класса.

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

. . , 9}, признаки X1 , X2 , . . . , X784 ∈ [0, 255] – пикселыизображения размера 28×28.Примеры объектов:Данные: http://yann.lecun.com/exdb/mnist/Сенько Олег Валентинович ()ММО - основные понятия12 / 47Примеры задач машинного обученияЗадача прогноза стоимости жилья в различныхпригородахБостона(задачавосстановлениярегрессии).Целевая переменная Y – цена жилья. Признаки:уровень криминала в районеконцентрация окисей азотадоля жилья, построенного до 1940 годасреднее расстояние до основных районов концентрации рабочихместуровень налогообложенияотношение числа учителей к числу учеников в школахи другиеДанные: http://archive.ics.uci.edu/ml/datasets/HousingСенько Олег Валентинович ()ММО - основные понятия13 / 47Способы поиска закономерностейОсновным способом поиска закономерностей является поиск внекотором априори заданном семействе алгоритмов прогнозирования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Сенько Олег Валентинович ()ММО - основные понятия14 / 47Частные случаи функции потерьПри прогнозировании непрерывных величин могут использоватьсяλ[yj , A(xj )] = (yj − A(xj ))2 – квадрат ошибки,λ[yj , A(xj )] = |yj − A(xj )| – модуль ошибки.В случае задачи распознавания функция потерь может быть равной 0при правильной классификации и 1 при ошибочной.

При этомфункционал эмпирического риска равен числу ошибочныхклассификаций.Сенько Олег Валентинович ()ММО - основные понятия15 / 47Примеры поиска закономерностейРассмотрим задачу восстановления регрессии по одному признаку.Здесь Ỹ = 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Сенько Олег Валентинович ()123−30−3ММО - основные понятия−2−1012316 / 47Примеры поиска закономерностейРассмотрим задачу классификации на два класса по двум признакам.Здесь Ỹ = {1, 2}, X̃ = R2 .Поиск зависимости в семействе линейных разделителей:(1, если ax1 + bx2 + c ≥ 0,y=2, иначе.3210−1−2−3−3−2−101Сенько Олег Валентинович ()23ММО - основные понятия17 / 47Обобщающая способностьТочность алгоритма прогнозирования на всевозможных новых неиспользованных для обучения объектах, которые возникают врезультате процесса, соответствующего рассматриваемой задачепрогнозирования, принято называть обобщающей способностью.Иными словами обобщающую способность алгоритма прогнозированияможно определить как точность на всей генеральной совокупности.Мерой обобщающей способности служит математическое ожиданиепотерь по генеральной совокупности EΩ {λ[Y, A(x)]}.Сенько Олег Валентинович ()ММО - основные понятия18 / 47Обобщающая способностьОбобщающая способность может быть записана в видеZEΩ {λ[Y, A(x)]} =E{λ[Y, A(x)]|x}p(x)dx1 .