Оценочная и сравнительная классификация алгоритмов

Глава 14:
Оценочная и сравнительная классификация алгоритмов

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Введение
Вопросы:
Оценка ожидаемой ошибки обучающего алгоритма: будет ли погрешность метода ближайшего соседа (k-NN) при k=1 (1-NN) менее 2%?
Сравнение ожидаемых ошибок двух алгоритмов: метод ближайшего соседа (k-NN) более точен чем многослойный персептрон (MLP) ?
Обучение/проверка/тестирование выборки
Методы ресамплинга: Кросс-валидация по K блокам (K-fold cross-validation)

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Предпочтение алгоритма
Критерии (зависимые от применения):
Ошибка неверной классификации, или риск (функции потерь)
Время обучения/ уровень сложности
Время тестирования/ уровень сложности
Интерпретируемость
Лёгкая программируемость
Обучение с учетом издержек классификации (Cost-sensitive learning)

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Ресамплинг и кросс-валидация по K блокам
Необходимость многократного обучения/ оценки выборки {Xi,Vi}i: Обучения/оценки выборка из i блоков
Кросс-валидация по K блокам: разделение X на k блоков, Xi, i=1,...,K
Ti делится на K-2 частей

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Кросс-валидация 5×2
Кросс-валидация: 5 раз по 2 блока (Dietterich, 1998)

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Выборка с возвратом (Bootstrapping)
Возьмём образцы из выборки с последующим их возвратом
Вероятность того, что мы не выберем образец после N попыток
то есть, только 36.8% образцов являются новыми!

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Ошибки измерения
Уровень ошибки = (FN+FP) / N
Возврат = TP / (TP+FN) = чувствительность = коэффициент совпадений
Точность = TP / (TP+FP)
Определенность = TN / (TN+FP)
Частота ложных тревог = FP / (FP+TN) = 1 - Specificity

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Кривая ошибок (ROC Curve)

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Интервальная оценка
X = { xt }t where xt ~ N ( μ, σ2)
m ~ N ( μ, σ2/N)
100(1- α) %
доверительный интервал

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Когда σ2 не известна:

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Проверка гипотезы
Отклоняем недостоверную гипотезу если она не подкреплена выборкой с достаточной достоверностью
X = { xt }t где xt ~ N ( μ, σ2)
H0: μ = μ0 или H1: μ ≠ μ0
Принимаем H0 с уровнем значимости α если μ0 находится в 100(1- α) доверительном интервале
Двусторонний тест

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Односторонняя проверка: H0: μ ≤ μ0 или H1: μ > μ0
Принимаем если
Дисперсия неизвестна: используем t, вместо z
Принимаем H0: μ = μ0 если

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Оценка ошибки:
H0: p ≤ p0 или H1: p > p0
Одиночная обучающая/оценочная выборка: биноминальный тест
Если вероятность ошибки p0, то вероятность того что в N проверочных выборок будет e или менее ошибок
1- α
Принимается если эта вероятность
меньше чем1- α
N=100, e=20

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Нормальная аппроксимация биноминального распределения
Количество ошибок X приблизительно равно N со средним значением Np0 и дисперсией Np0(1-p0)
Принимается, если вероятность
того, что X = e меньше чем z1-α
1- α

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
t-тест для парных выборок
Многократное обучение/оценка выборки
xti = 1 если объект t неверно классифицирован на свертке i
Уровень ошибки на свертке i:
С помощью m и s2 - математического ожидания и дисперсии pi мы принимаем p0 или меньшую ошибку если
меньше чем tα,K-1

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Сравнительные классификаторы: H0: μ0 = μ1 или H1: μ0 ≠ μ1
Однократное обучение/оценка выборки: тест Мак-Нимара
Под H0, мы понимаем e01= e10=(e01+ e10)/2
Принимаем если< X2α,1

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Кросс-валидация по K блокам CV t-тест для парных выборок
Используем кросс-валидацию по K блокам cv чтобы получить K обучающих/оценочных блоков
pi1, pi2:Ошибки функции классификации 1 и 2 на блоке i
pi = pi1 – pi2 : спаренное различие на блоке i
Нулевая гипотеза это имеет ли pi среднее значение, равное 0

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Кросс-валидация 5×2 cv t-тест для парных выборок
Используем 5×2 cv чтобы получить 2 блока из 5 обучений/оценок репликаций (Dietterich, 1998)
pi(j) : разница между ошибками 1 и 2 на блоках j=1, 2 репликации i=1,...,5
Двусторонняя проверка: принимаем H0: μ0 = μ1 если находится в интервале (-tα/2,5,tα/2,5)
Односторонняя проверка: принимаем H0: μ0 ≤ μ1 если < tα,5

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Кросс-валидация 5×2 cv F-тест для парных выборок
Двусторонняя проверка: Принимаем H0: μ0 = μ1 если < Fα,10,5

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)
Сравнение L>2 алгоритмов: анализ отклонений (Дисперсионный анализ)
Ошибки L алгоритмов на K блоках
Мы строим две оценочные функции для σ2 .
Первая действительна если H0 истина, другая действительна всегда.
Мы отклоняем H0 если две оценочные функции не совпадают.

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)

Lecture Notes for E Alpaydın 2004 Introduction to Machine Learning © The MIT Press (V1.1)