Изменения

Перейти к: навигация, поиск

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

13 934 байта добавлено, 13:49, 10 марта 2020
Источники информации
==Понятие модели==
Пусть дана обучающая выборка <tex>(X, TY)</tex>, где <tex> X </tex> {{---}} множество значений признаков, описывающих объекты, а <tex> T Y </tex> {{---}} конечное множество, содержащее для каждого элемента из X его классификациюметок.
Пусть множество всевозможных значений признаков задана функция <tex> g: X \times \Theta \hat{X} rightarrow Y </tex>, множество всевозможных классификаций где <tex> \hat{T} Theta </tex>{{---}} множество дополнительных параметров (весов) функции.
Пусть задана Описанная выше функция <tex> f: \hat{X} -g </tex> W -для фиксированного значения весов <tex> \hat{T} theta \in \Theta </tex>, где W - множество дополнительных параметров (весов) функцииназывается '''решающим правилом'''.
Описанная выше функция <tex> f </tex> для фиксированного значения весов <tex> w \in W </tex> называется '''решающим правиломМодель'''{{---}} совокупность всех решающих правил, которые получаются путем присваивания весам всех возможных допустимых значений.
'''Модель''' Формально модель <tex> A = \{{---}g(x, \theta) | \theta \in \Theta\} это совокупность всех решающих правил, которые получаются путем присваивания весам всех возможных допустимых значений</tex>.
Формально модель Модель определяется множеством допустимых весов <tex> M = \{fTheta </tex> и структурой решающего правила <tex> g(.x, w\theta)| w \in W\} </tex>.
Модель определяется множеством допустимых весов <tex> W </tex> === Понятие гиперпараметров модели ==='''Гиперпараметры модели''' {{---}} параметры, значения которых задается до начала обучения модели и структурой решающего правила <tex> f(не изменяется в процессе обучения.,У модели может не быть гиперпараметров.) </tex>
==Понятие гиперпараметров модели=='''Гиперпараметры Параметры модели''' {{---}} это параметры, значения которых задается до начала которые изменяются и оптимизируются в процессе обучения модели и не изменяется в процессе итоговые значения этих параметров являются результатом обучения. У модели может не быть гиперпараметров.
'''Параметры Примерами гиперпараметров могут служить количество слоев нейронной сети, а также количество нейронов на каждом слое. Примерами параметров могут служить веса ребер нейронной сети. Для нахождения оптимальных гиперпараметров модели''' {{-могут применяться различные алгоритмы [[Настройка гиперпараметров | настройки гиперпараметров]]<sup>[на 28.01.19 не создан]</sup>. === Пример ===[[Файл:Linear--}} это параметры, которые изменяются и оптимизируются в процессе обучения модели и итоговые значения этих параметров являются результатом обучения regression.png|300px|thumb|[http://www.machinelearning.ru/wiki/index.php?title=%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29 Рис 1. Пример линейной регрессии]]]В качестве примера моделиприведем [[Линейная регрессия | линейную регрессию]].
Примерами гиперпараметров могут служить количество слоев нейронной сетиЛинейная регрессия задается следующей формулой: <tex> g(x, а также количество нейронов на каждом слое\theta) = \theta_0 + \theta_1x_1 + . Примерами параметров могут служить .. + \theta_kx_k = \theta_0 + \sum_{i=1}^k \theta_ix_i = \theta_0 + x^T\theta</tex>, где <tex> x^T = (x_1, x_2, ..., x_k) </tex> {{---}} вектор признаков,  <tex> \theta = (\theta_1, \theta_2, ..., \theta_k)</tex> {{---}} веса ребер нейронной сетимодели, настраиваемые в процессе обучения. Гиперпараметром модели является число слагаемых в функции <tex> g(x, \theta) </tex>.
Для нахождения оптимальных гиперпараметров модели могут применяться различные алгоритмы Более подробный пример линейной регрессии можно посмотреть в статье [[Настройка гиперпараметров Переобучение | настройки гиперпараметровпереобучение]]<sup>[на 08.01.19 не создан]</sup>.
== Задача выбора модели ==
'''Выбрать модель''' Пусть <tex> A </tex> {{---}} определить множество весов модель алгоритма, характеризующаяся гиперпараметрами <tex> W \lambda = \{\lambda_1, ..., \lambda_m\}, \lambda_1 \in \Lambda_1, ..., \lambda_m \in \Lambda_m </tex> и структуру решающего правила . Тогда с ней связано пространство гиперпараметров <tex> \Lambda = \Lambda_1 \times ... \times \Lambda_m </tex> f(За <tex> A_{\lambda}</tex> обозначим алгоритм, то есть модель алгоритма, для которой задан вектор гиперпараметров <tex> \lambda \in \Lambda </tex>. Для выбора наилучшего алгоритма необходимо зафиксировать меру качества работы алгоритма.Назовем эту меру <tex> Q(A_{\lambda}, D) </tex>. Задачу выбора наилучшего алгоритма можно разбить на две подзадачи: подзадачу выбора лучшего алгоритма из портфолио и подзадачу настройки гиперпараметров.
Пусть есть две модели ==== Подзадача выбора лучшего алгоритма из портфолио ====Дано некоторое множество алгоритмов с фиксированными структурными параметрами <tex> M_1 \mathcal{A} = \{f_1(A^1_{\lambda_1}, ..., w)| w A^m_{\in W_1lambda_m}\} </tex> и обучающая выборка <tex> M_2 D = \{f_2d_1, ..., d_n\}</tex>. Здесь <tex> d_i = (.x_i, wy_i)| w \in W_2(X, Y)</tex>. Требуется выбрать алгоритм <tex> A^*_{\lambda_*} </tex>, который окажется наиболее эффективным с точки зрения меры качества <tex> Q </tex>. Необходимо выбрать наилучшую ==== Подзадача оптимизации гиперпараметров ====Подзадача оптимизации гиперпараметров заключается в подборе таких <tex> \lambda^* \in \Lambda </tex>, при которых заданная модель из этих двухалгоритма <tex> A </tex> будет наиболее эффективна.
Стоит отметитьГиперпараметры могут выбираться из ограниченного множества или с помощью перебора из неограниченного множества гиперпараметров, это зависит от непосредственной задачи. Во втором случае актуален вопрос максимального времени, что недостаточно обучить обе модели которое можно потратить на обучающей выборке и выбрать тупоиск наилучших гиперпараметров, так как чем больше времени происходит перебор, которая тем лучше работает на обучающей выборкегиперпараметры можно найти, потому что лучшая работа но при этом может быть следствием переобучения. Также выбирать модель надо исходя ограничен временной бюджет, из желаемого времени обучения и времени получения ответа - более сложная модель может давать более точные результаты, но работать значительно дольше более простой моделиза чего перебор придется прервать.
=== Методы выбора модели ===
'''Методы Модель можно выбрать из некоторого множества моделей, проверив результат работы каждой модели из множества с помощью ручного тестирования, но ручное тестирование серьезно ограничивает количество моделей, которые можно перебрать, а также требует больших трудозатрат. Поэтому в большинстве случаев используются алгоритмы, позволяющие автоматически выбирать модель. Далее будут рассмотрены некоторые из таких алгоритмов.[[Файл:Scikit-learn-scheme.png|900px|thumb|center|[https://www.codeastar.com/choose-machine-learning-models-python/ Рис 2. Схема выбора модели''' в библиотеке scikit-learn для Python]]]==== Кросс-валидация ===={{main|Кросс---валидация}} алгоритмы, позволяющие проводить автоматический выбор модели.
==== Кросс-валидация ====Алгоритм Основная идея алгоритма кросс-валидации работает следующим образом:# Обучающая выборка разбивается на <tex> k </tex> непересекающихся одинаковых по объему частей;# Производится <tex> k </tex> итераций. На каждой итерации происходит следующее:## Модель обучается на <tex> k {{--- 1 </tex> части обучающей выборки;## Модель тестируется }} разбить обучающую выборку на части обучающей выборки, которая не участвовала в обучении;# В результате можно посчитать различные метрики, показывающие, насколько модель удачная, например, среднюю ошибку на частях, которые не участвовали в обучающей выборкеобучающую и тестовую.Таким образом эмулируется , будет возможным эмулировать наличие тестовой выборки, которая не участвует участвующей в обучении, но для которой известны правильные ответы.
Достоинства и недостатки кросс-валидации:
# Кросс-валидация плохо применима в задачах кластерного анализа и прогнозирования временных рядов.
==== Мета-обучение ===={{main|Мета-обучение}} Целью мета-обучения является решение задачи выбора алгоритма из портфолио алгоритмов для решения поставленной задачи без непосредственного применения каждого из них. Решение этой задачи в рамках мета-обучения сводится к задаче [https://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81_%D1%83%D1%87%D0%B8%D1%82%D0%B5%D0%BB%D0%B5%D0%BC обучения с учителем]. Для этого используется заранее отобранное множество наборов данных <tex> D </tex>. Для каждого набора данных <tex> d \in D </tex> вычисляется вектор мета-признаков, которые описывают свойства этого набора данных. Ими могут быть: число категориальных или численных признаков объектов в <tex> d </tex>, число возможных меток, размер <tex> d </tex> и многие другие<ref>[https://www.fruct.org/publications/ainl-fruct/files/Fil.pdf Datasets meta-feature description for recommending feature selection algorithm]</ref>. Каждый алгоритм запускается на всех наборах данных из <tex> D </tex>. После этого вычисляется эмпирический риск, на основе которого формируются метки классов. Затем мета-классификатор обучается на полученных результатах. В качестве описания набора данных выступает вектор мета-признаков, а в качестве метки — алгоритм, оказавшийся самым эффективным с точки зрения заранее выбранной меры качества.  Достоинства и недостатки мета-обучения:# Алгоритм, обучающийся большое время, запускается меньшее количество раз, что сокращает время работы;# Точность алгоритма может быть ниже, чем при кросс-валидации. ====[http://www.machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%92%D0%B0%D0%BF%D0%BD%D0%B8%D0%BA%D0%B0-%D0%A7%D0%B5%D1%80%D0%B2%D0%BE%D0%BD%D0%B5%D0%BD%D0%BA%D0%B8%D1%81%D0%B0 Теория Вапника-Червоненкиса Червоненкинса] ====
Идея данной теории заключается в следующем: чем более «гибкой» является модель, тем хуже ее обобщающая способность. Данная идея базируется на том, что «гибкое» решающее правило способно настраиваться на малейшие шумы, содержащиеся в обучающей выборке.
Очевидно, что чем больше емкость, тем более «гибкой» является модель и, соответственно, тем хуже. Значит нужно добиваться минимально возможного количества ошибок на обучении при минимальной возможной емкости.
Существует формула Вапника, связывающая ошибку на обучении <tex> P_{train}(w\theta) </tex>, емкость <tex> h(W\theta) </tex> и ошибку на генеральной совокупности <tex> P_{test}(w\theta) </tex>:
<tex> P_{test}(w\theta) <= P_{train}(w\theta) + \sqrt{\frac{h(W\Theta) * (\log{(\frac{2d}{h(W\Theta)})} + 1) - \log{(\frac{\eta}{4})}}{n}} </tex>, где <tex> d </tex> {{---}} размерность пространства признаков.
Неравенство верно с вероятностью <tex> 1 - \eta </tex> <tex> \forall w \theta \in W \Theta </tex>.
Алгоритм выбора модели согласно теории Вапника-Червоненкиса: Последовательно последовательно анализируя модели с увеличивающейся емкостью, необходимо выбирать модель с наименьшей верхней оценкой тестовой ошибки.
Достоинства теории Вапника-Червоненкиса:
# Для большинства моделей емкость не поддается оценке;
# Многие модели с бесконечной емкостью показывают хорошие результаты на практике.
 
== Существующие системы автоматического выбора модели ==
===Автоматизированный выбор модели в библиотеке [https://www.ml4aad.org/wp-content/uploads/2018/07/automl_book_draft_auto-weka.pdf auto-WEKA] для Java===
Библиотека используется для одновременного поиска оптимальной модели и оптимальных гиперпараметров модели для задач классификации и регрессии (начиная с версии 2.0).
 
Библиотека позволяет автоматически выбирать из 27 базовых алгоритмов, 10 мета-алгоритмов и 2 ансамблевых алгоритмов лучший, одновременно настраивая его гиперпараметры при помощи алгоритма [https://www.ml4aad.org/automated-algorithm-design/algorithm-configuration/smac/ SMAC]. Решение достигается полным перебором: оптимизация гиперпараметров запускается на всех алгоритмах по очереди. Недостатком такого подхода является слишком большое время выбора модели.
===Автоматизированный выбор модели в библиотеке [https://epistasislab.github.io/tpot/ Tree-base Pipeline Optimization Tool (TPOT)] для Python.===
[[Файл:TPOT-scheme.jpeg|500px|thumb|[https://raw.githubusercontent.com/EpistasisLab/tpot/master/images/tpot-ml-pipeline.png Рис 3. Схема выбора модели в библиотеке TPOT]]]
Библиотека используется для одновременного поиска оптимальной модели и оптимальных гиперпараметров модели для задачи классификации.
 
Выбор модели осуществляется на основе конвейера, организованного в древовидной структуре. Каждая вершина дерева {{---}} один из четырех операторов конвейера (preprocessing, decomposition, feature selection, modeling). Каждый конвейер начинается с одной или нескольких копий входного набора данных, которые являются листьями дерева и которые подаются в операторы в соответствии со структурой конвейера. Данные модифицируются оператором в вершине и поступают на вход следующей вершины. В библиотеке используются генетические алгоритмы для нахождения лучших конвейеров.
 
После создания конвеера, оценивается его производительность и случайным образом изменяются части конвеера для поиска наибольшей эффективности. Время работы TPOT может варьироваться в зависимости от размера входных данных. При начальных настройках в 100 поколений с размером популяции 100, за время работы оценивается 10000 конфигураций конвеера. По времени это сравнимо с [https://en.wikipedia.org/wiki/Hyperparameter_optimization#Grid_search поиском по сетке] для 10000 комбинаций гиперпараметров. Это 10000 конфигураций модели со [[Кросс-валидация | скользящим контролем]] по 10 блокам, что означает, что около 100000 моделей создается и оценивается на обучающих данных в одном поиске по сетке. Поэтому, для некоторых наборов данных требуется всего несколько минут, чтобы найти высокопроизводительную модель для работы, а некоторым может потребоваться несколько дней.
 
После поиска конвейера его также можно экспортировать в файл Python.
 
===Автоматизированный выбор модели в библиотеке [https://automl.github.io/auto-sklearn/stable/ auto-sklearn] для Python===
[[Файл:Auto-sklearn-scheme.png|500px|thumb|[https://papers.nips.cc/paper/5872-efficient-and-robust-automated-machine-learning.pdf Рис 4. Схема выбора модели в библиотеке auto-sklearn]]]
Библиотека используется для одновременного поиска оптимальной модели и оптимальных гиперпараметров модели для задачи классификации.
 
Сначала используется мета-обучение на основе различных признаков и мета-признаков набора данных, чтобы найти наилучшие модели. После этого используется подход [https://en.wikipedia.org/wiki/Bayesian_optimization Байесовской оптимизации], чтобы найти наилучшие гиперпараметры для наилучших моделей.
 
На рисунке 5 показаны общие компоненты Auto-sklearn. Он состоит из 15 алгоритмов классификации, 14 методов предварительной обработки и 4 методов предварительной обработки данных. Мы параметризовали каждый из них, что привело к пространству, состоящему из 110 гиперпараметров. Большинство из них являются условными гиперпараметрами, которые активны, только если выбран соответствующий компонент. Отметим, что SMAC может обрабатывать эту обусловленность изначально.
 
[[Файл:model_5.png|900px|center|thumb| Рис 5. Структурированное пространство конфигурации. Квадратные прямоугольники обозначают родительские гиперпараметры, прямоугольники с закругленными краями являются листовыми гиперпараметрами. Серые прямоугольники отмечают активные гиперпараметры, которые образуют пример конфигурации и конвейера машинного обучения. Каждый конвейер содержит один препроцессор, классификатор и до трех методов препроцессора данных, а также соответствующие гиперпараметры.]]
== См. также ==
* [[Настройка гиперпараметров]]<sup>[на 0828.01.19 не создан]</sup>
* [[Переобучение]]
* [[Мета-обучение]]<sup>* [на 08.01.19 не создан[Линейная регрессия]]</sup>
== Примечания ==
# [http:<references//www.machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%92%D0%B0%D0%BF%D0%BD%D0%B8%D0%BA%D0%B0-%D0%A7%D0%B5%D1%80%D0%B2%D0%BE%D0%BD%D0%B5%D0%BD%D0%BA%D0%B8%D1%81%D0%B0 Теория Вапника-Червоненкинса]># [https://en.wikipedia.org/wiki/Cross-validation_(statistics) Кросс-валидация]
== Источники информации ==
# * [http://www.machinelearning.ru/wiki/images/0/05/BMMO11_4.pdf Выбор machinelearning.ru {{---}} Задачи выбора модели] - презентация на MachineLearning.ru# * [https://en.wikipedia.org/wiki/Hyperparameter_(machine_learning) ГиперпараметрыWikipedia {{---}} Hyperparameter] - статья на Википедии# * [https://machinelearningmastery.com/difference-between-a-parameter-and-a-hyperparameter/ Разница между параметрами What is the Difference Between a Parameter and a Hyperparameter?]* [http://jmlda.org/papers/doc/2016/no2/Efimova2016Reinforcement.pdf Применение обучения с подкреплением для одновременного выбора модели алгоритма классификации и гиперпараметрамиее структурных параметров] * [https://7bce9816- описание разницы между параметрами и гиперпараметрами моделиa-62cb3a1a-s-sites.googlegroups.com/site/automl2017icml/accepted-papers/AutoML_2017_paper_23.pdf?attachauth=ANoY7cr6uPaUoNh3gc3A-A1UbLXQgNEATEkfZmKD8kozB3hpCYtM9JwnOevEsW9W42CwurzJKrxxEatcB4DCjWNB_Ndvy1uC0lbQyCTlDIfrW6eYJXvdbFJPilYfmf8_ryilH0IwG0ddntLYy-VA3Fm1JeM495fTZxorYth0DDKiqtKvSR92dGl8CM_mUB7sun0R6wurCxM36QqcYEaf5kIm13MM0reWlR3aPZVNe_-AefOCpoXznR-wH04mSWjH8jmlk5Bw51AN&attredirects=0 Fast Automated Selection of Learning Algorithm And its Hyperparameters by Reinforcement Learning]* Shalamov V., Efimova V., Muravyov S., and Filchenkov A. "Reinforcement-based Method for Simultaneous Clustering Algorithm Selection and its Hyperparameters Optimization." Procedia Computer Science 136 (2018): 144-153.  [[Категория: Машинное обучение]]
84
правки

Навигация