Модель алгоритма и её выбор

Понятие модели

Пусть дана обучающая выборка [math](X, T)[/math], где [math] X [/math] — множество значений признаков, [math] T [/math] — множество, содержащее для каждого элемента из X его классификацию.

Пусть множество всевозможных значений признаков [math] \hat{X} [/math], множество всевозможных классификаций [math] \hat{T} [/math].

Пусть задана функция [math] f: \hat{X} -\gt W -\gt \hat{T} [/math], где W - множество дополнительных параметров (весов) функции.

Описанная выше функция [math] f [/math] для фиксированного значения весов [math] w \in W [/math] называется решающим правилом.

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

Формально модель [math] M = \{f(., w)| w \in W\} [/math].

Модель определяется множеством допустимых весов [math] W [/math] и структурой решающего правила [math] f(.,.) [/math]

Понятие гиперпараметров модели

Гиперпараметры модели — это параметры, значения которых задается до начала обучения модели и не изменяется в процессе обучения. У модели может не быть гиперпараметров.

Параметры модели — это параметры, которые изменяются и оптимизируются в процессе обучения модели и итоговые значения этих параметров являются результатом обучения модели.

Примерами гиперпараметров могут служить количество слоев нейронной сети, а также количество нейронов на каждом слое. Примерами параметров могут служить веса ребер нейронной сети.

Для нахождения оптимальных гиперпараметров модели могут применяться различные алгоритмы настройки гиперпараметров^{[на 08.01.19 не создан]}.

Задача выбора модели

Выбрать модель — определить множество весов [math] W [/math] и структуру решающего правила [math] f(., .) [/math]

Пусть есть две модели [math] M_1 = \{f_1(., w)| w \in W_1\} [/math] и [math] M_2 = \{f_2(., w)| w \in W_2\} [/math]. Необходимо выбрать наилучшую модель из этих двух.

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

Методы выбора модели

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

Кросс-валидация

Алгоритм кросс-валидации работает следующим образом:

1. Обучающая выборка разбивается на [math] k [/math] непересекающихся одинаковых по объему частей;
2. Производится [math] k [/math] итераций. На каждой итерации происходит следующее:
   1. Модель обучается на [math] k - 1 [/math] части обучающей выборки;
   2. Модель тестируется на части обучающей выборки, которая не участвовала в обучении;
3. В результате можно посчитать различные метрики, показывающие, насколько модель удачная, например, среднюю ошибку на частях, которые не участвовали в обучающей выборке.

Таким образом эмулируется наличие тестовой выборки, которая не участвует в обучении, но для которой известны правильные ответы.

Достоинства и недостатки кросс-валидации:

1. Ошибка в процедуре кросс-валидации является достаточно точной оценкой ошибки на генеральной совокупности;
2. Проведение кросс-валидации требует значительного времени на многократное повторное обучение алгоритмов и применимо лишь для "быстрых" алгоритмов машинного обучения;
3. Кросс-валидация плохо применима в задачах кластерного анализа и прогнозирования временных рядов.

Теория Вапника-Червоненкиса

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

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

По аналогии емкость обобщается на другие задачи машинного обучения.

Очевидно, что чем больше емкость, тем более "гибкой" является модель и, соответственно, тем хуже. Значит нужно добиваться минимально возможного количества ошибок на обучении при минимальной возможной емкости.

Существует формула Вапника, связывающая ошибку на обучении [math] P_{train}(w) [/math], емкость [math] h(W) [/math] и ошибку на генеральной совокупности [math] P_{test}(w) [/math]:

[math] P_{test}(w) \lt = P_{train}(w) + \sqrt{\frac{h(W) * (\log{(\frac{2d}{h(W)})} + 1) - \log{(\frac{\eta}{4})}}{n}} [/math], где [math] d [/math] — размерность пространства признаков.

Неравенство верно с вероятностью [math] 1 - \eta [/math] [math] \forall w \in W [/math]

Алгоритм выбора модели согласно теории Вапника-Червоненкиса: Последовательно анализируя модели с увеличивающейся емкостью, необходимо выбирать модель с наименьшей верхней оценкой тестовой ошибки.

Достоинства теории Вапника-Червоненкиса:

1. Серьезное теоретическое обоснование, связь с ошибкой на генеральной совокупности;
2. Теория продолжает развиваться и в наши дни.

Недостатки теории Вапника-Червоненкиса:

1. Оценки ошибки на генеральной совокупности сильно завышены;
2. Для большинства моделей емкость не поддается оценке;
3. Многие модели с бесконечной емкостью показывают хорошие результаты на практике.

См. также

• Настройка гиперпараметров^{[на 08.01.19 не создан]}
• Переобучение
• Мета-обучение^{[на 08.01.19 не создан]}

Примечания

1. Теория Вапника-Червоненкинса
2. Кросс-валидация

Источники информации

1. Выбор модели - презентация на MachineLearning.ru
2. Гиперпараметры - статья на Википедии
3. Разница между параметрами и гиперпараметрами - описание разницы между параметрами и гиперпараметрами модели