2015 Методичка по ММО (сделана частично_ не все темы), страница 5

Пример:

можно пытаться аппроксимировать кубическим полиномом и получить красивую кривую, а можно взять полином более высокого прядка и кривую будет шатать, при этом она пройдёт через все точки обучающй выборки, но на генеральной совокупности будет хуже.

<картинки на слайде 22 из лекций 1>

Верхний предел точности:

E(Y|X) - среднее по всей совокупности

E(Y -A(X))² = ошибка алгоритма А = E(Y - E(Y|X) + E(Y|X) - A(X))² =

= ∑{ E(Y - E(Y|X))² + 2*E(Y - E(Y|X))_{[=0, т.к. EY = P(X)*E(Y|X) и EE(Y|X) = P(X)E(Y|X)]} * E(E(Y|X) - A(X)) + E(E(Y|X) - A(X))² } =

= ∑{ E(Y - E(Y|X))² + E(E(Y|X) - A(X))² }

Таким образом, алгоритм, который вычисляет отклонение Y от X (т.е. A(X) = E(Y|X)) является лучшим и имеет ошибку равную выражению выше.

<подробнее см вычисления на слайде 24 лекции 1>

1. Байесовский классификатор

Байесовский классификатор имеет наименьшую ошибку распознавания, если предположить, что элементы выборки имеют всю доступную информацию о распределении объектов по классам.

(!!! какую именно “доступную информацию”?, байесовский подход к классификации основан на теореме, утверждающей, что если плотности распределения каждого из классов известны, то искомый алгоритм можно выписать в явном аналитическом виде. Более того, этот алгоритм оптимален, то есть обладает минимальной вероятностью ошибок)

Байесовский классификатор относит объект x к тому классу, в котором максимизируется условная вероятность P(K_i, x).

(мы при этом знаем долю объектов принадлежащих каждому из классов K₁, … K_L)

Задача поиска минимума ошибки сводится к задаче линейного программирования. <вычисления на слайде 28 лекции 1>

Задача линейного программирования даёт некоторое множество, и одна из вершин является решением (минимизацией), при этом если решение задачи достигается в одной точке, то объект нужно будет классифицировать принадлежащим к этому классу, если в нескольких точках, то можно выбрать любой класс, в которых достигается экстремум задачи лп (лин. прогр.).

Для вычисления необходимых для Байесовского классификатора условных вероятностей можно использовать метод максимального правдоподобия (ММП).

функция максимального правдоподобия = произведение плотности вероятности на объектах обучающей выборки.

Важно, что выборка у нас - это независимые одинаково распределённые случайные величины.

Оценка для θ у функции максимльного правдоподобия совпадает с задачей линейного программирования выше, небходимо функцию правдоподобия максимизировать.

Проблема байесовского классификатора: на практике часто неизвестны ни общий вид распределения, ни значения их конкретных параметров.

Методы прогнозирования:

• Статистические методы

• Линейные модели регрессионного анализа

• Различные методы, основанные на линейной разделимости

• Методы, основанные на ядерных оценках

• Нейросетевые методы

• Комбинаторно-логические методы и алгоритмы вычисления оценок

• Алгебраические методы

• Решающие или регрессионные деревья и леса

• Методы, основанные на опорных векторах

Байесовское решающее правило является частным случаем байесовского классификатора, для 2-х классов

Байесовское решающее правило (является оптимальным) P(j=1 | x) / P (j=2 | x) <?> P1 / P2 – где P(j=1 | x) это вероятность того, что данный элемент x будет классифицирован как 1, а P1 – вероятность что мы держим в руках элемент из класса 1.

(выводится из среднего риска для случая с 2-мя классами)

Наивный Байесовский классификатор. Это байесовский классификатор с предположением, что все переменные независимы. (благодаря этому условная вероятность распадается на произведение условных вероятностей отдельно по каждому из признаков, что очень помогает в вычислениях) (точность около 0,67, т.е. так себе)

1. Байесовский классификатор для многомерного нормального распределения

<Сенько, лекция 4, слайды 1 (частично были пропущены)>

Если мы работаем с наивным байесовским классификатором и предположим, что случайные величины распределены по нормальному распределению, то объект с признаковым описанием x будет отнесён построенной аппроксимацией байесовского классификатора к классу, для которого оценка g_i(x) является максимальной.

Следует отметить, что построенный классификатор в общем случае является квадратичным по признакам. Однако классификатор превращается в линейный, если оценки ковариационных матриц разных классов оказываются равными.

1. Линейный дискриминант Фишера (ЛДФ)

Задача распознавания 2-х классов.

Метод основан на том, что в многомерном признаковом пространстве ищется направление w, чтобы средние значения проекции на него объектов обучающей выборки из классов максимально различались.

<Сенько лекция 4 недоделана>

1. Эмпирические методы оценки обобщающей способности

Контрольная выборка - часть объектов из исходной выборки, по которой будет оцениваться обобщающая способность алгоритма. Она не должна входить в обучающую выборку.

Функционал риска - , где сумма идёт по элементам контрольной выборки.

Подробнее про скользящий контроль читай параграф про скользящий контроль

Несмещённость оценки скользящего контроля означает, что математическое ожидание от величины потерь при обучении на всей выборке равна мат ожиданию по всем итерациям скользящего контроля (т.е. среднее значение по всем m итерациям скользящего контроля) от математического ожидания величины потерь при обучении на m-1 элементе выборки.

<слайд 44 лекции 1>

1. Линейная регрессия

1. Линейная регрессия

Линейная регрессия - когда функция классификации для объектов генеральной совокупности ищется среди класса линейных функций.

Традиционный способ поиска коэффициентов линейной регрессии является метод наименьших квадратов (т.е. когда для выборки минимизируется срений риск, а в качестве функции величины потерь - берётся квадрат разности)

Необходимое условие минимума для уравнений всегда одно - равенство нулю производных.

На конце линейных функций линейной регрессии добавляется некоторая ε, которая является случайной величиной, которая нормально распределена имеет нулевое мат. ожидание на выборке и её дисперсия не зависит случайных величин - выборки.

В этом случае метод наименьших квадратов совпадает с методом максимлаьного правдоподобия.

Метод ММП (метод максимального правдоподобия) позволяет восстанавливать плотность распределения вероятностей по случайным выборкам, если общий вид плотности вероятностного распределения известен.

ММП заключается в том, чтобы найти такое θ, при котором функция максимального правдоподобия максимизируется, если взять !!! (это же логическая ошибка, как мы можем говорить, об эквивалентности ММП и МНК, если мы сами по ходу решения подставили линейную функцию в ММП) (важно не то, что мы подставили линейную функцию, а то, что мы предположили, что у линейной функции на конце висит случайная величина с нормальным распределением, так что всё норм) функцию линейного вида из линейной регрессии, то записа функцию МП и взяв логарифм, видно, что её точка максимума достигается тогда же, когда достигается точка максимумав методе МНК (наименьших квадратов).

Для одномерной модели линейной регрессии (у объекта лишь один признак):

Коваривация показывает, как зависит Y от X, если она >0, то функции одновременно растут (или падают), если <0, то одна растёт, а другая падает.

Коэффициент корреляции Пирсона =

+- 1 означаетлинейную зависимость между X и Y

0 означает отсутствие линейной зависимости

интересный вывод, для линейной регрессии b₀ + xb₁

b₁ = cov(Y, X) / D(X)

b₀ = y - b₁*x

<не понимаю, к чему на слайдах с 10 лекции 3 рассказывается про дисперсию и ковариацию - вывод-то какой?>

Многомерная регрессия:

При многомерной регрессии строят матрицу плана - строка матрицы - это вектор значений переменных из обучающей выборки, и первый столбец - забит “1”.

тогда можно записать y = βX + ε, где все буквы - это вектора, а X - это матрица плана.

После взятия производной уравнения выглядят так: -2X^Ty^T + 2X^TXβ^T = 0

Решение для β^T = (X^TX)^-1 * X^Ty^T

В данном случае, чтобы решение существовало, нужно чтобы определитель матрицы был не равен нулю, т.е. чтобы m-мерные вектора были линейно независимы.

Если ветора будут сильно коррелированны, то значение определителя будет близко к нулю, и такое решение обычно является не устойчивым к малым изменениям исходных данных. Это свойство называется мультиколлинеарностью.

На практике высокая устойчивость достигается только когда число объектов в выборках по крайней мере в 3-5 раз превышает число переменных.

Регрессионный анализ в изначальном своём виде не позволяет отбирать признаки.

Гребневая (ridge)

Лассо слишком жёстко отбирает признаки

<Сенько слайды 18 - 30 лекции 3> - там много выкладок, которые приводят к выводам связанным, с кореляцией, ковариацией, ...

1. Обобщённая ошибка

Обобщёные потери - математическое ожидание по всевозжным обучающим выборкам от матожидания по величине потерь.

Обобщённая квадратичная ошибка - обобщённая потеря, в случае когда в качестве величины потери используется квадрат ошибки.

<Сенько слайд 23, потом шло много вычислений, которые я скипаю>

В итоге:

Структура обобщённой ошибки:

1. Шумовая компонента N - является минимально достижимой квадратичной ошибкой прогноза, которая не может быть устранена с использованием только математических средств

2. Составляющая сдвига (Bias) - высокое значение компоненты сдвига соответствует отсутствию в модели алгоритмов, достаточно хорошо аппроксимирующих объективно существующую зависимость Y от переменных X₁, …, X_n.

Составляющая сдвига может быть снижена, например, путём расширения модели за счёт включения в него дополнительных более сложных алгоритмов, что обычно позволяет повысить точность аппроксимации данных.

1. Дисперсионная составляющая (Variance) - характеризует неустойчивость обученных прогнозирующих алгоритмов при статистически возможных изменениях в обучающих выборках.

Дисперсионная составляющая возрастает при небольших размерах обучающей выборки.

Дисперсионная составляющая может быть снижена путём выбора сложности модели, соответствующей размеру обучающих данных.

Bias-Variance дилема: Составляющая сдвига может быть снижена путём увеличения разнообразия модели, однако увеличение разнообразия модели при недостаточном объёме обучающих данных ведёт к росту компоненты сдвига. Наиболее высокая точность прогноза достигается, при поддержании правильного баланса между разнообразием используемой модели и объёмом обучающих данных.

1. Способы регуляризации линейной регрессии

Регуляризация используется для улучшения устойчивости в регрессионном анализе для частного случая - МНК (Метод Наименьших Квадратов).

Суть метода регуляризации: включение дополнительной шумовой компоненты в исходный оптимизируемый функционал.

Типы регуляризаций:

1. регуляризация по Тихонову - добавление штрафной компоненты к оптимизируемому функционалу (по формулам там была модификация значений признаков объектов)

2. гребневая регрессия (ridge) - добавляет сумму квадратов регрессионных компонентов к функционалу (это приводит к положительности дискриминанта и улучшается устойчивость)

3. метод лассо - добавляет модули регрессионных компонент к функционалу (делает отбор переменных (т.к. некоторые регрессионные переменные приравниваются к 0) и применение на маленьких выборках возможным) (при высокой корреляции некоторых переменных, на практике метод лассо ухудшает свои показатели)

4. эластичная сеть - добавление суммы квадрата регрессионных компонент с коэффициентом θ и модуля регрессионных компонент с коэффициентом (1-θ) (вбирает все лучшее из первых двух).

1. Задачи прогнозирования

1. Нейронные методы, персептрон Роззенблатта

В основе нейросетевых методов лежит попытка скопировать компьютером процесс мышления животных.

Нейрон - некоторая сущность, которая суммирует входящие сигналы с учётом весов, применяет к результату активационную функцию и выдаёт результат на выход.

Сигналы, приходящие на вход персептронов рецепторов, интерпретируются как входные признаки.

3 типа нейронов:

1. нейроны-рецепторы

2. внутренние нейроны - имеет множество входных связей от рецепторов или внутренних нейронов

3. реагирующие нейроны - имеет множество входных связей от рецепторов или внутренних нейронов

Все сигналы, входящие в нейрон обрабатываются: z = w₀ + ∑w_iu_i , после чего применяется активационная функция Ф(z) - и это значение становится результатом нейрона и выдаётся другим нейронам (один сигнал с выхода может передаваться многим другим на вход) (u_i - значения с других нейронов, w_i - веса внутри нейрона, w₀ - параметр сдвига)