Презентацию к лекции Вы можете скачать здесь.
Машинное обучение (machine learning) – это область научного знания, имеющая дело с
алгоритмами, "способными обучаться". Необходимость использования методов машинного
обучения объясняется тем, что для многих сложных – "интеллектуальных" – задач (например,
распознавание рукописного текста, речи и т. п.) очень сложно (или даже невозможно) разработать
"явный" алгоритм их решения, однако часто можно научить компьютер обучиться решению этих
задач. Одним из первых, кто использовал термин "машинное обучение", был изобретатель первой
самообучающейся компьютерной программы игры в шашки А. Л. Самуэль в 1959 г. [10]. Под
обучением он понимал процесс, в результате которого компьютер способен показать поведение,
которое в нее не было заложено "явно". Это определение не выдерживает критики, так как не
понятно, что означает наречие "явно". Более точное определение дал намного позже
Т. М. Митчелл [9]: говорят, что компьютерная программа обучается на основе опыта E по
отношению к некоторому классу задач T и меры качества P, если качество решения задач из T,
измеренное на основе P, улучшается с приобретением опыта E.
Заметим, что фаза обучения может предшествовать фазе работы алгоритма (например, детектирование лиц на фотокамере), но может иметь место обратная ситуация: обучение (и дополнительное обучение) может проходить в процессе функционирования самого алгоритма (например, определение спама).
В настоящее время машинное обучение имеет многочисленные сферы приложения, такие, как компьютерное зрение, распознавание речи, компьютерная лингвистика и обработка естественных языков, медицинская диагностика, биоинформатика, техническая диагностика, финансовые приложения, поиск и рубрикация текстов, интеллектуальные игры, экспертные системы и др.
Различают дедуктивное и индуктивное обучение. В задачах дедуктивного обучения имеются знания, каким-либо образом формализованные. Требуется вывести из них правило, применительное к конкретному случаю. Дедуктивное обучение относят к области экспертных систем и здесь рассматриваться не будет. Основная задача индуктивного обучения заключается в восстановлении некоторой зависимости по эмпирическим данным. Индуктивное обучение подразделяется на обучение с учителем, обучение без учителя, обучение с подкреплением (reinforcement learning), активное обучение и др.
Обстоятельными учебниками по машинному обучению являются [1, 8, 9] и др. Также рекомендуем русскоязычный ресурс www.machinelearning.ru и сайт курса по машинному обучению одного из авторов настоящего пособия www.uic.unn.ru/~zny/ml.
Рассмотрим постановку задачи обучения с учителем (supervised learning). Пусть $$$\mathcal{X}$$ – некоторое множество, элементы которого называются объектами или примерами, ситуациями, входами (samples); а $$$\mathcal{Y}$$ – множество, элементы которого называются ответами или откликами, метками, выходами (responses). Имеется некоторая зависимость (детерминированная или вероятностная), позволяющая по $$x\in\mathcal{X}$$ предсказать $$y\in\mathcal{Y}$$ . В частности, если зависимость детерминированная, то существует функция $$f^*:\mathcal{X}\rightarrow\mathcal{Y}$$ . Зависимость известна только на объектах обучающей выборки
$$\lbrace (x^{(i)},y^{(i)}):x^{(i)}\in\mathcal{X},y^{(i)}\in\mathcal{Y}\,\,(i=1,2,...,N) \rbrace$$Упорядоченная пара "объект-ответ" $$(x^{(i)},y^{(i)})\in\mathcal{X}\times\mathcal{Y}$$ называется прецедентом.
Задача обучения с учителем заключается в восстановлении зависимости между входом и выходом по имеющейся обучающей выборке, т. е. необходимо построить функцию (решающее правило) $$f:\mathcal{X}\rightarrow\mathcal{Y}$$ , по новым объектам $$x\in\mathcal{X}$$ предсказывающую ответ $$y=f(x)\in\mathcal{Y}$$ :
$$y=f(x) \approx f^*(x).$$Функция $$f$$ при этом выбирается из некоторого множества возможных моделей $$$\mathcal{F}$$ . Процесс нахождения $$f$$ называется обучением (learning), а также настройкой или подгонкой (fitting) модели. Алгоритм построения функции по заданной обучающей выборке называется алгоритмом обучения. Некоторый класс алгоритмов называется методом обучения. Иногда термины "алгоритм" и "метод" используются как синонимы.
Алгоритмы обучения, конечно же, оперируют не с самими объектами, а их описаниями. Наиболее распространенным является признаковое описание. При таком подходе объект представляется как вектор $$x=(x_1,x_2,\,...,x_d)$$ , где $$x_j \in Q_j\,\,(j=1,2,\,...,d)$$. Таким образом,
$$\mathcal{X}=Q_1 \times Q_2 \times ... \times Q_d.$$Компонента $$x_j$$ называется j-м признаком, или свойством (feature), или атрибутом объекта x. Если
$$Q_j=\mathbb{R}$$ , то j-й признак называется количественным или вещественным. Если $$Q_j$$ конечно, то j-й
признак называется номинальным, или категориальным, или фактором. Если при этом $$\lvert Q_j \rvert=2$$ ,
то признак называется бинарным. Если $$Q_j$$ конечно и упорядочено, то признак называется
порядковым. Множество $$\mathcal{X}$$ называется пространством признаков.
В зависимости от того, какие значения может принимать ответ , различают разные классы задач обучения с учителем. Если $$\mathcal{Y}=\mathbb{R}$$ , то говорят о задаче восстановления регрессии. Решающее правило $$f$$ при этом называют регрессией. Если $$\mathcal{Y}$$ конечно, например,$$\mathcal{Y}=\lbrace 1,2,...,K \rbrace$$, то говорят о задаче классификации. Решающее правило $$f$$ при этом называют классификатором. В последнем случае можно интерпретировать как номер класса, к которому принадлежит объект $$x$$ . К задачам обучения относят также задачи ранжирования, прогнозирования и др.
Сделаем два замечания, касающиеся качества решения задачи.
Во-первых, найденное решающее правило должно обладать обобщающей способностью. Иными словами, построенный классификатор или функция регрессии должны отражать общую зависимость выхода от входа, основываясь лишь на известных данных о прецедентах обучающей выборки. При решении прикладных задач, как правило, говорить о восстановлении истинной взаимосвязи не приходится, и, следовательно, речь может идти лишь об отыскании некоторой аппроксимации. Таким образом, обученная модель должна выдавать в среднем достаточно точные предсказания на новых (не входящих в обучающую выборку) прецедентах.
Во-вторых, следует уделить внимание проблеме эффективной вычислимости функции $$f$$ . Аналогичное требование предъявляется и к алгоритму обучения: настройка модели должна происходить за приемлемое время.
Пусть для задачи обучения с учителем определена функция потерь, или функцию штрафа, $$L(y,y')=L(y,f(x))$$, представляющая собой неотрицательную функцию от истинного значения выхода $$y$$ и предсказанного с помощью модели значения $$y'=f(x)$$. Например, для задачи восстановления регрессии часто используют квадратичный штраф
$$L(y,f(x))=\frac 1 2$ (y-f(x))^2$$или абсолютный штраф:
$$L(y,f(x))=\lvert y-f(x) \rvert .$$Для задачи классификации можно взять ошибку предсказания
$$L(y,f(x))=I(y \neq f(x)),$$где $$I( \cdot )$$ – индикаторная функция:
$$I(условие)=\begin{cases} 1,\text{условие выполнено,}\\ 0,\text{условие не выполнено.} \end{cases}$$Математическое ожидание функции потерь
$$R(f)=\mathrm{E} \,\,L(Y,f(X))$$называется средней ошибкой, или средним риском. В качестве решающего правила разумно взять функцию $$f^*$$, минимизирующую эту ошибку:
$$f^*=arg\,\, min_{f\in \mathcal{F}}R(f)=arg\,\, min_{f\in \mathcal{F}}\mathrm{E} \,\,L(Y,f(X)),$$Часто закон распределения совместной случайной величины $$(X,Y)$$ не известен, поэтому данный критерий не применим. Вместо среднего риска $$R(f)$$ рассмотрим эмпирический риск, или эмпирическую ошибку,
$$\hat{R}(f)=\frac 1 N$ \sum^{N}_{i=1} {L(y^{(i)},f(x^{(i)}))}.$$Критерий (1) заменим следующим:
$$f=arg\,\, min_{f\in \mathcal{F}}\sum^{N}_{i=1} {L(y^{(i)},f(x^{(i)}))},$$где прецеденты $$(x^{(i)},y^{(i)}),(i=1,...,N)$$ составляют обучающую выборку.
В итоге задача свелась к отысканию функции $$f$$ из допустимого множества $$\mathcal{F}$$ , удовлетворяющей условию (2), при условии, что $$\mathcal{F}$$ и $$L$$ фиксированы и известны. Это так называемый принцип минимизации эмпирического риска. Как правило, класс $$\mathcal{F}$$ параметризован, т. е. имеется его описание в вида $$\mathcal{F}=\lbrace f(x)=f(x,\theta ): \theta \in \Theta \rbrace$$, где $$\Theta$$ – некоторое известное множество. В процессе настройки модели алгоритмом обучения выбираются значения набора параметров $$\Theta$$ , обеспечивающих точное или приближенное выполнение условия (2), т. е. минимизации ошибки на прецедентах обучающей выборки. Однако данное условие не подходит для оценки обобщающей способности алгоритма. Более того, значения $$\hat{R}(f)$$ и $$R(f)$$ могут различаться значительно. Ситуация, когда $$\hat{R}(f)$$ мало, а $$R(f)$$ чересчур велико, называется переобучением.
На практике все имеющиеся данные разбивают на обучающую и тестовую выборки. Обучение производится с использованием обучающей выборки, а оценка качества предсказания на основе данных тестовой выборки.
Другим практическим методом оценки обобщающей способности решающего правила является
метод q-кратного перекрестного (скользящего) контроля (CV – cross validation). Все имеющиеся
данные разбиваются на примерно равных (по числу прецедентов) частей. Далее, отделяя из
выборки одну за другой каждую из этих частей, используют оставшиеся данные (составленные из
q-1 частей) как обучающую выборку, а отделенную часть – как тестовую. Итоговая оценка
ошибки определяется как средняя по всем разбиениям. Заметим, что само итоговое решающее
правило строится по всей имеющейся обучающей выборке.
Часто используют значения q=5 или 10. Если q=N-1, то говорят о методе скльзящего
контроля с одним отделяемым объектом (LOO – leave-one-out estimate).
Метод $$k$$ ближайших соседей (k nearest-neighbor, k-NN) относится к наиболее простым и в то же время универсальным методам, используемым как для решения задач классификации, так и восстановления регрессии. В случае классификации новый объект классифицируется путем отнесения его к классу, являющемуся преобладающим среди $$k$$ ближайших (в пространстве признаков) объектов из обучающей выборки. Если $$k=1$$ , то новый объект относится к тому же классу, что и ближайший объект из обучающей выборки.
Аналогичный способ используется и в задаче восстановления регрессии, с той лишь разницей, что в качестве ответа для объекта выступает среднее ответов k ближайших к нему объектов из обучающей выборки.
Опишем метод более формально. Пусть $$N_k(x)$$ – множество ближайших к $$x$$ объектов из обучающей выборки. Тогда для задачи классификации положим
$$f(x)=arg\,\, max_y \lvert \lbrace i:y^{(i)}=y,x^{(i)}\in N_k(x) \rbrace \rvert,$$а для задачи восстановления регрессии –
$$f(x)=\frac 1 k$ \sum_{x^{(i)} \in N_k(x)} {y^{(i)}}.$$В некоторых случаях данные ответы учитываются с весами, обратно пропорциональными расстоянию до объекта. Это особенно полезно для решения задачи классификации с несбалансированными данными, т. е. когда число объектов, относящихся к разным классам, сильно различно.
Для определения ближайших соседей обычно используется евклидово расстояние
$$\rho(x,x')=\sqrt{\sum^d_{j=1} {\lvert x_j-x_j' \rvert ^2}},$$однако оно применимо только для признаков, описываемых количественными переменными. Если все переменные качественные, то можно использовать расстояние Хэмминга
$$\rho(x,x')=\sum^d_{j=1} {I(x_j \neq x_j')}.$$В общем случае используют функцию
$$\rho(x,x')=\sum^d_{j=1} {a_j\rho_j(x_j,x_j')},$$где $$a_j$$ – неотрицательные параметры, $$\rho_j(x_j,x_j')=(x_j-x_j')^2$$ для качественных переменных, $$\rho_j(x_j,x_j')=I(x_j \neq x_j')$$ для качественных переменных. Заметим, что функция расстояния не обязательно должна быть метрикой и неравенство треугольника может быть не выполнено.
Для повышения точности модели также могут использоваться специальные алгоритмы обучения метрики расстояния (например, Large Margin Nearest Neighbour [8]).
Одним из основных параметров, влияющих на обобщающую способность алгоритма, является число "ближайших соседей" $$k$$ . В целом, выбор определенного значения обусловлен характером данных задачи. Большие значения $$k$$ могут привести как к более точному описанию границы, разделяющей классы, так и переобучению. Обычно для выбора $$k$$ применяют различные эвристики, в частности, метод перекрестного контроля.
Один из самых популярных методов машинного обучения – машина опорных векторов (SVM – Support Vector Machine) – является развитием идей, предложенных в 1960–1970 гг. В. Н. Вапником и А. Я. Червоненкисом. Окончательное очертание метод принял в 1995 г., когда было показано, как в этом методе можно эффективно использовать ядра [4].
Рассмотрим вначале случай двух линейно разделимых классов. Для удобства будем их кодировать числами 1,-1 т. е. $$\mathcal{Y}=\lbrace 1,-1\rbrace$$.
Оптимальной разделяющей гиперплоскостью называется гиперплоскость, такая, что расстояние от нее до ближайшей точки из обучающей выборки (не важно из какого класса) максимально. Таким образом, оптимальная разделяющая гиперплоскость максимизирует зазор (отступ) – расстояние от нее до точек из обучающей выборки. Часто это приводит к хорошим результатам и на объектах тестовой выборки.
Математическая постановка задачи выглядит следующим образом:
Требуется найти
$$max_{\beta,\beta_0,w} w,$$при ограничениях
$$y^{(i)}(\beta x^{(i)}+\beta_0)\geqslant w\,\,\,\,(i=1,2,...,N),$$ $$\lvert \lvert \beta \rvert \rvert =1,$$где $$\beta x^{(i)}$$ означает скалярное произведение
$$\beta x^{(i)}=\sum^d_{j=1} {\beta_j x^{(i)}_j},$$а $$\lvert \lvert \beta \rvert \rvert$$ – евклидову норму
$$\lvert \lvert \beta \rvert \rvert=\sqrt{\sum^d_{j=1} {\beta_j ^2}.$$Эквивалентная формулировка:
$$max_{\beta,\beta_0} \lvert \lvert \beta \rvert \rvert^2,$$при ограничениях
$$y^{(i)}(\beta x^{(i)}+\beta_0)\geqslant 1\,\,\,\,(i=1,2,...,N),$$Можно показать, что решение этой задачи имеет вид
$$\beta=\sum^N_{j=1} {a_iy^{(i)}x^{(i)}}, \,\,\,\, где\,a_i\geqslant 0,$$уравнение разделяющей гиперплоскости есть $$\beta x+\beta_0=0$$ и классификатор определяется правилом
$$f(x)=sign(\beta x+\beta_0)$$Если $$a_i>0$$ то $$x^{(i)}$$ называется опорной точкой или опорным вектором. Легко видеть, что опорные точки лежат на границе разделяющей полосы
$$-1 \leqslant \beta x+\beta_0 \leqslant 1$$следовательно, $$\beta_0=y^{(i)}-\beta x^{(i)}$$, где $$x^{(i)}$$ – произвольный опорный вектор.
В случае линейно не разделимых классов разрешим некоторым объектам из обучающей выборки "слегка" заходить за разделяющую гиперплоскость:
$$max_{\beta,\beta_0,\xi,w} w,$$при ограничениях
$$y^{(i)}(x^{(i)}\beta+\beta_0)\geqslant w(1-\xi_i),\,\,\xi_i\geqslant 0,\,\,\,\,(i=1,2,...,N),$$ $$\lvert \lvert \beta \rvert \rvert =1,$$ $$\sum^N_{j=1} {\xi_i \leqslant \Xi},$$где $$\Xi$$ – некоторая константа (параметр метода). При $$\Xi=0$$ получаем предыдущий случай (линейно разделимых классов). Значение $$\xi_i$$ пропорционально величине, на которую $$x^{(i)}$$ заходит за границу разделяющей полосы. В частности, -й объект будет классифицирован неправильно тогда и только тогда, когда $$\xi_i>1$$ . Чем меньше $$\Xi$$, тем меньше объектов классифицируется неправильно. С другой стороны, $$\Xi$$ должно быть достаточно велико, чтобы задача была совместной.
Эквивалентная формулировка:
$$max_{\beta,\beta_0,\xi} \frac 1 2$ \lvert \lvert \beta \rvert \rvert +C\sum^N_{j=1} {\xi_i},$$при ограничениях
$$y^{(i)}(x^{(i)}\beta+\beta_0)\geqslant 1-\xi_i,\,\,\xi_i\geqslant 0,\,\,\,\,(i=1,2,...,N).$$Здесь параметр $$C \geqslant 0$$ регулирует величину штрафа за то, что некоторые точки выходят за границу разделяющей полосы. Построенная задача является задачей квадратического программирования. Для ее решения можно использовать общие методы для решения таких задач, однако существуют весьма эффективные специальные методы.
Можно показать, что решение задачи единственно, если в обучающей выборке есть по крайней мере один представитель каждого из классов.
Дальнейшее усовершенствование метода – использование спрямляющих пространств. Пусть удается перейти от исходного пространства признаков $$\mathcal{X}$$ к новому пространству $$\mathcal{H}$$ (которое называется спрямляющим) с помощью некоторого отображения $$h:\mathcal{X} \rightarrow \mathcal{H}$$:
$$h(x)=(h_1(x),h_2(x),...,h_M(x)),$$где $$h_m(x)$$ – базисные функции $$(m=1,2,...,M)$$. Новый классификатор определяется теперь функцией
$$f(x)=sign(h(x)\beta x+\beta_0)$$Здесь $$h(x)\beta x+\beta_0=0$$ – разделяющая поверхность. Если отображение подобрано удачно, в новом пространстве классы могут быть линейно разделимы или близки к таковым.
Оказывается, все вычисления при обучении и при расчете функции $$f(x)$$ можно организовать так, что $$h(x)$$ встречается только в выражениях вида
$$K(x,x')=h(x)h(x').$$В частности уравнение разделяющей поверхности имеет вид
$$\biggl(\sum^N_{j=1} {a_iy^{(i)}h(x^{(i)})}\biggr)h(x)+\beta_0=0$$что эквивалентно
$$\sum^N_{j=1} {a_iy^{(i)}h(x^{(i)})}h(x)+\beta_0=0$$или
$$\sum^N_{j=1} {a_iy^{(i)}K(x^{(i)},x)}+\beta_0=0$$Функция $$K(x,x')$$ называется ядром. На практике, таким образом, вместо того, чтобы испытывать различные функции $$h$$ можно (так и поступают) подбирать наиболее подходящее ядро $$K(x,x')$$.
Заметим, что не любая функция $$K: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$$ представима в виде $$K(x,x')=h(x)h(x')$$, т. е. может быть использована в качестве ядра. Приведем перечень некоторых популярных функций- ядер:
Для того чтобы использовать метод опорных векторов для задачи классификации с числом классом K>2 , возможно использовать две стратегии:
K(K-1)/2 классификаторов на всех возможных
подзадачах бинарной классификации. Новый объект классифицируется всеми
построенными решающими правилами, затем выбирается преобладающий класс. Деревья решений [3] являются одним из наиболее наглядных и универсальных алгоритмов обучения. К достоинствам деревьев решений следует отнести:
Кроме того, существуют эффективные алгоритмы их настройки (обучения), например, CART – Classification and Regression Trees [3] или See5/C5.0.
Основная идея деревьев решений состоит в рекурсивном разбиении пространства признаков с помощью разбиений (splits): гиперплоскостей, параллельных координатным гиперплоскостям (если признак – количественный), либо по категориям (если признак номинальный). В каждом из полученных в конце процедуры "ящиков" $$R_1,R_2,...,R_M$$ функция аппроксимируется константой:
В алгоритме CART разбиения имеют вид:
Дерево строится рекурсивно с помощью следующей жадной процедуры, на каждом шаге максимально уменьшая значение функции, описывающей неоднородность данных, содержащихся в узле дерева. Пусть на текущем шаге имеется разбиение пространства признаков на области (ящики) $$R_1,R_2,...,R_M$$.
Разбиения проводятся до тех пор, пока в строящиеся вершины попадает достаточное количество точек обучающей выборки, или пока дерево не достигнет заданной глубины.
Используют различные способы измерить неоднородность, например,
где $$N_m$$ – количество точек из обучающей выборки, попавших в область $$R_m$$ .
Другой важный параметр модели – это глубина дерева решений, регулирующая, "как сильно" будет разбито пространство признаков. Небольшое число разбиений может привести к тому, что построенная модель не будет учитывать некоторые особенности распределения признаков, описывающих те или иные классы, и таким образом приведет к уменьшению точности предсказания. Чрезмерное число разбиений может привести к переобучению модели и снижению еe обобщающей способности.
Для того чтобы избежать переобучения, используется процедура отсечений (prunning) [3].
Один из общих подходов в машинном обучении заключается в использовании композиции "слабых" решающих правил. Итоговое правило строится путем взвешенного голосования ансамбля базовых правил. Для построения базовых правил и вычисления весов в последнее время часто используются две идеи:
Эксперименты показывают, что, как правило, бустинг работает на больших обучающих выборках, тогда как баггинг – на малых.
Одной из реализаций идеи баггинга является случайный лес [2].
Случайный лес, а точнее – случайные леса (random forests), является одним из наиболее универсальных и эффективных алгоритмов обучения с учителем, применимым как для задач классификации, так и для задач восстановления регрессии. Идея метода [2] заключается в использовании ансамбля из M деревьев решений (например, M=500), которые обучаются независимо друг от друга. Итоговое решающее правило заключается в голосовании всех деревьев, входящих в состав ансамбля.
Для построения каждого дерева решений используется следующая процедура:
p=d/3 , sz=1 для задачи
восстановления регрессии $$p=\sqrt d$$, sz=3. Одной из модификаций метода случайных деревьев является алгоритм крайне случайных деревьев (extremely random forests), в котором на каждом этапе для выбора признака, по которому будет проводиться разбиение, используется вновь сгенерированная случайная бутстрэп-выборка.
Среди достоинств алгоритма случайных деревьев можно выделить высокое качество предсказания, способность эффективно обрабатывать данные с большим числом классов и признаков, внутреннюю оценку обобщающей способности модели. Легко построить параллельную высоко масштабируемую версию алгоритма. Кроме того, доказано, что данный алгоритм не переобучается (с ростом M). Также метод обладает всеми преимуществами деревьев решений, в том числе отсутствием необходимости предобработки входных данных, обработкой как вещественных, так и категориальных признаков, поддержкой работы с отсутствующими значениями.
Градиентный бустинг деревьев решений (Gradient Boosting Trees – GBT) [6, 7] – другой универсальный алгоритм машинного обучения, основанный на использовании ансамбля деревьев решений. В отличие от случайного леса градиентный бустинг является развитием бустинг-идеи. Алгоритм минимизирует эмпирический риск жадным пошаговым алгоритмом, аналогичным методу градиентного спуска. Рассмотрим, например, задачу восстановления регрессии используют. Рассмотрим суммарный штраф на обучающей выборке как функцию от значений решающего правила f в точках $$x^{(1)},x^{(2)},...,x^{(N)}$$:
$$L(f)=L(f(x^{(1)}),f(x^{(2)}),...,f(x^{(N)}))=\sum^N_{i=1} {L(y^{(i)},f(x^{(i)})}$$Тогда градиент функции L(f) равен
$$grad\,\,L(f)=\Biggl( \frac {\delta L(y^{(1)},f(x^{(1)}))} {\delta f(x^{(1)})},\frac {\delta L(y^{(2)},f(x^{(2)}))} {\delta f(x^{(2)})},...,\frac {\delta L(y^{(N)},f(x^{(N)}))} {\delta f(x^{(N)})} \Biggr)$$На предварительном этапе алгоритм строит оптимальную константную модель $$f=g_0$$. На m-й
итерации конструируется дерево решений $$g_m$$
(небольшой глубины), аппроксимирующее
компоненты вектора антиградиента, вычисленного для текущей модели f. После этого значения в
узлах построенного дерева $$g_m$$
перевычисляются, так, чтобы минимизировать суммарную
величину штрафа $$L(f+g_m)$$ Далее осуществляем присваивание $$f \leftarrow f+vg_m$$, что и завершает
m-ю итерацию. Здесь v – параметр регуляризации (shrinkage), призванный бороться с возможным
переобучением. Он выбирается из интервала (0,1].
Для решения задачи восстановления регрессии часто используются следующие штрафные функции:
квадратичный штраф
$$L(y,f(x))=\frac {1}{2} (y-f(x))^2,$$абсолютный штраф
$$L(y,f(x))=\lvert y-f(x) \rvert .$$или функция Хьюбера
$$L(y,f(x))=\frac {1}{2} (y-f(x))^2=\begin{cases} \frac {1}{2} (y-f(x))^2,\text{при $\lvert y-f(x) \rvert \leqslant \delta$,}\\ \delta(\lvert y-f(x) \rvert - \frac {\delta}{2})^2,\text{при $\lvert y-f(x) \rvert > \delta$.} \end{cases}$$Заметим, что функция Хьюбера и квадратичный штраф дифференцируемы всюду, тогда как абсолютный штраф – везде, кроме точек, в которых $$y=f(x)$$.
Для задачи классификации с K классами метод остается прежним, только вместо одной функции
f конструируют сразу K функций $$f_k\,\,(k=1,2,...,K)$$. В качестве штрафа можно использовать
кросс-энтропию
где
$$p_y(x)=\frac {e^{f_y(x)}} {\sum^K_{k=1}e^{f_y(x)} }$$– есть оценка вероятности того, что $$f(x)=y$$. Итоговый классификатор определяется как
$$f(x)=arg\,\,max_yp_y(x).$$Более подробное описание алгоритма см. в [6, 7].
Другим популярным методом, использующим идею бустинга, является алгоритм AdaBoost и его модификации [5].
В задачах обучения без учителя (unsupervised learning) у объектов не известны выходы, и требуется найти некоторые закономерности в данных. К задачам обучения без учителя относят задачи кластеризации, понижения размерности, визуализации и др. Здесь рассматривается только кластеризация.
Задача кластеризации – это задача разбиения заданного набора объектов на кластеры, т. е. группы близких по своему признаковому описанию объектов. "Похожие" друг на друга объекты должны входить в один кластер, "не похожие" объекты должны попасть в разные кластеры.
Близость ("похожесть") объектов измеряется на основе функции расстояния $$\rho(x,x'):\mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$$
Рассмотрим один из алгоритмов, решающих задачу кластеризации – метод центров тяжестей ( -means). На вход алгоритма поступает набор данных
$$x^{(1)},x^{(2)},...,x^{(N)}, \,\,\, где \,\,\, x^{(i)}\in Q_1 \times Q_2 \times ... \times Q_d \,\,(i=1,2,...,N)$$и натуральное число K – количество кластеров, на которые нужно разбить данные. Алгоритм реализует пошаговую процедуру минимизации
$$min_{C,m_k}\sum^N_{i=1} {\rho(x^{(i)},m_k)},$$где $$m_k$$ – центр тяжести объектов, относящихся к k-му кластеру:
$$m_k=\frac {\sum_{C(i)=k} {x^{(i)}}} {\lvert \lbrace i:C(i)=k \rbrace \rvert} (k=1,2,...,K)$$При этом не гарантируется нахождение глобального минимума. На предварительном этапе строится некоторое разбиение входных данных на K групп (например, случайно). Пусть $$C(i)$$ – номер группы, к которой принадлежит -й объект. В ходе работы алгоритма значения $$C(i)$$ обновляются. В конце работы алгоритма значения $$C(i)$$ будут соответствовать разбиению данных на кластеры. Каждая итерация представляет собой последовательность следующих шагов:
Итерации завершаются, когда наступает стабилизация значений $$C(i)$$ , либо по достижении максимального значения числа итераций.
Метод центров тяжестей работает с явными описаниями объектов $$x^{(i)}$$ Модификацией этого метода является метод медиан, или метод срединных точек, ( K–medians, или K–medoids). На вход этого алгоритма подается число кластеров K и матрица расстояний $$D=(d_{ii'})$$, где $$d_{ii'}=\rho(x^{(i)},x^{(i')})(i,i'=1,2,...,N)$$. Заметим, что сама функция $$\rho(x,x')$$ может быть не известна.
Алгоритм ничем не отличается от предыдущего, но вместо центра тяжестей, для каждой группы будем находить медиану, или срединную точку, $$m_k=x_{i^*_k}$$, где
$$i^*_k=argmin_{C(i)=k} \sum_{C(i')=k} {d^2_{ii'}}.$$Каждая итерация представляет собой последовательность следующих шагов:
Как правило, результаты работы алгоритмов центров тяжестей и медиан (если они оба применимы к данным) близки.
Презентацию к лекции Вы можете скачать здесь.
Машинное обучение (machine learning) – это область научного знания, имеющая дело с
алгоритмами, "способными обучаться". Необходимость использования методов машинного
обучения объясняется тем, что для многих сложных – "интеллектуальных" – задач (например,
распознавание рукописного текста, речи и т. п.) очень сложно (или даже невозможно) разработать
"явный" алгоритм их решения, однако часто можно научить компьютер обучиться решению этих
задач. Одним из первых, кто использовал термин "машинное обучение", был изобретатель первой
самообучающейся компьютерной программы игры в шашки А. Л. Самуэль в 1959 г. [10]. Под
обучением он понимал процесс, в результате которого компьютер способен показать поведение,
которое в нее не было заложено "явно". Это определение не выдерживает критики, так как не
понятно, что означает наречие "явно". Более точное определение дал намного позже
Т. М. Митчелл [9]: говорят, что компьютерная программа обучается на основе опыта E по
отношению к некоторому классу задач T и меры качества P, если качество решения задач из T,
измеренное на основе P, улучшается с приобретением опыта E.
Заметим, что фаза обучения может предшествовать фазе работы алгоритма (например, детектирование лиц на фотокамере), но может иметь место обратная ситуация: обучение (и дополнительное обучение) может проходить в процессе функционирования самого алгоритма (например, определение спама).
В настоящее время машинное обучение имеет многочисленные сферы приложения, такие, как компьютерное зрение, распознавание речи, компьютерная лингвистика и обработка естественных языков, медицинская диагностика, биоинформатика, техническая диагностика, финансовые приложения, поиск и рубрикация текстов, интеллектуальные игры, экспертные системы и др.
Различают дедуктивное и индуктивное обучение. В задачах дедуктивного обучения имеются знания, каким-либо образом формализованные. Требуется вывести из них правило, применительное к конкретному случаю. Дедуктивное обучение относят к области экспертных систем и здесь рассматриваться не будет. Основная задача индуктивного обучения заключается в восстановлении некоторой зависимости по эмпирическим данным. Индуктивное обучение подразделяется на обучение с учителем, обучение без учителя, обучение с подкреплением (reinforcement learning), активное обучение и др.
Обстоятельными учебниками по машинному обучению являются [1, 8, 9] и др. Также рекомендуем русскоязычный ресурс www.machinelearning.ru и сайт курса по машинному обучению одного из авторов настоящего пособия www.uic.unn.ru/~zny/ml.
Рассмотрим постановку задачи обучения с учителем (supervised learning). Пусть $$$\mathcal{X}$$ – некоторое множество, элементы которого называются объектами или примерами, ситуациями, входами (samples); а $$$\mathcal{Y}$$ – множество, элементы которого называются ответами или откликами, метками, выходами (responses). Имеется некоторая зависимость (детерминированная или вероятностная), позволяющая по $$x\in\mathcal{X}$$ предсказать $$y\in\mathcal{Y}$$ . В частности, если зависимость детерминированная, то существует функция $$f^*:\mathcal{X}\rightarrow\mathcal{Y}$$ . Зависимость известна только на объектах обучающей выборки
$$\lbrace (x^{(i)},y^{(i)}):x^{(i)}\in\mathcal{X},y^{(i)}\in\mathcal{Y}\,\,(i=1,2,...,N) \rbrace$$Упорядоченная пара "объект-ответ" $$(x^{(i)},y^{(i)})\in\mathcal{X}\times\mathcal{Y}$$ называется прецедентом.
Задача обучения с учителем заключается в восстановлении зависимости между входом и выходом по имеющейся обучающей выборке, т. е. необходимо построить функцию (решающее правило) $$f:\mathcal{X}\rightarrow\mathcal{Y}$$ , по новым объектам $$x\in\mathcal{X}$$ предсказывающую ответ $$y=f(x)\in\mathcal{Y}$$ :
$$y=f(x) \approx f^*(x).$$Функция $$f$$ при этом выбирается из некоторого множества возможных моделей $$$\mathcal{F}$$ . Процесс нахождения $$f$$ называется обучением (learning), а также настройкой или подгонкой (fitting) модели. Алгоритм построения функции по заданной обучающей выборке называется алгоритмом обучения. Некоторый класс алгоритмов называется методом обучения. Иногда термины "алгоритм" и "метод" используются как синонимы.
Алгоритмы обучения, конечно же, оперируют не с самими объектами, а их описаниями. Наиболее распространенным является признаковое описание. При таком подходе объект представляется как вектор $$x=(x_1,x_2,\,...,x_d)$$ , где $$x_j \in Q_j\,\,(j=1,2,\,...,d)$$. Таким образом,
$$\mathcal{X}=Q_1 \times Q_2 \times ... \times Q_d.$$Компонента $$x_j$$ называется j-м признаком, или свойством (feature), или атрибутом объекта x. Если
$$Q_j=\mathbb{R}$$ , то j-й признак называется количественным или вещественным. Если $$Q_j$$ конечно, то j-й
признак называется номинальным, или категориальным, или фактором. Если при этом $$\lvert Q_j \rvert=2$$ ,
то признак называется бинарным. Если $$Q_j$$ конечно и упорядочено, то признак называется
порядковым. Множество $$\mathcal{X}$$ называется пространством признаков.
В зависимости от того, какие значения может принимать ответ , различают разные классы задач обучения с учителем. Если $$\mathcal{Y}=\mathbb{R}$$ , то говорят о задаче восстановления регрессии. Решающее правило $$f$$ при этом называют регрессией. Если $$\mathcal{Y}$$ конечно, например,$$\mathcal{Y}=\lbrace 1,2,...,K \rbrace$$, то говорят о задаче классификации. Решающее правило $$f$$ при этом называют классификатором. В последнем случае можно интерпретировать как номер класса, к которому принадлежит объект $$x$$ . К задачам обучения относят также задачи ранжирования, прогнозирования и др.
Сделаем два замечания, касающиеся качества решения задачи.
Во-первых, найденное решающее правило должно обладать обобщающей способностью. Иными словами, построенный классификатор или функция регрессии должны отражать общую зависимость выхода от входа, основываясь лишь на известных данных о прецедентах обучающей выборки. При решении прикладных задач, как правило, говорить о восстановлении истинной взаимосвязи не приходится, и, следовательно, речь может идти лишь об отыскании некоторой аппроксимации. Таким образом, обученная модель должна выдавать в среднем достаточно точные предсказания на новых (не входящих в обучающую выборку) прецедентах.
Во-вторых, следует уделить внимание проблеме эффективной вычислимости функции $$f$$ . Аналогичное требование предъявляется и к алгоритму обучения: настройка модели должна происходить за приемлемое время.
Пусть для задачи обучения с учителем определена функция потерь, или функцию штрафа, $$L(y,y')=L(y,f(x))$$, представляющая собой неотрицательную функцию от истинного значения выхода $$y$$ и предсказанного с помощью модели значения $$y'=f(x)$$. Например, для задачи восстановления регрессии часто используют квадратичный штраф
$$L(y,f(x))=\frac 1 2$ (y-f(x))^2$$или абсолютный штраф:
$$L(y,f(x))=\lvert y-f(x) \rvert .$$Для задачи классификации можно взять ошибку предсказания
$$L(y,f(x))=I(y \neq f(x)),$$где $$I( \cdot )$$ – индикаторная функция:
$$I(условие)=\begin{cases} 1,\text{условие выполнено,}\\ 0,\text{условие не выполнено.} \end{cases}$$Математическое ожидание функции потерь
$$R(f)=\mathrm{E} \,\,L(Y,f(X))$$называется средней ошибкой, или средним риском. В качестве решающего правила разумно взять функцию $$f^*$$, минимизирующую эту ошибку:
$$f^*=arg\,\, min_{f\in \mathcal{F}}R(f)=arg\,\, min_{f\in \mathcal{F}}\mathrm{E} \,\,L(Y,f(X)),$$Часто закон распределения совместной случайной величины $$(X,Y)$$ не известен, поэтому данный критерий не применим. Вместо среднего риска $$R(f)$$ рассмотрим эмпирический риск, или эмпирическую ошибку,
$$\hat{R}(f)=\frac 1 N$ \sum^{N}_{i=1} {L(y^{(i)},f(x^{(i)}))}.$$Критерий (1) заменим следующим:
$$f=arg\,\, min_{f\in \mathcal{F}}\sum^{N}_{i=1} {L(y^{(i)},f(x^{(i)}))},$$где прецеденты $$(x^{(i)},y^{(i)}),(i=1,...,N)$$ составляют обучающую выборку.
В итоге задача свелась к отысканию функции $$f$$ из допустимого множества $$\mathcal{F}$$ , удовлетворяющей условию (2), при условии, что $$\mathcal{F}$$ и $$L$$ фиксированы и известны. Это так называемый принцип минимизации эмпирического риска. Как правило, класс $$\mathcal{F}$$ параметризован, т. е. имеется его описание в вида $$\mathcal{F}=\lbrace f(x)=f(x,\theta ): \theta \in \Theta \rbrace$$, где $$\Theta$$ – некоторое известное множество. В процессе настройки модели алгоритмом обучения выбираются значения набора параметров $$\Theta$$ , обеспечивающих точное или приближенное выполнение условия (2), т. е. минимизации ошибки на прецедентах обучающей выборки. Однако данное условие не подходит для оценки обобщающей способности алгоритма. Более того, значения $$\hat{R}(f)$$ и $$R(f)$$ могут различаться значительно. Ситуация, когда $$\hat{R}(f)$$ мало, а $$R(f)$$ чересчур велико, называется переобучением.
На практике все имеющиеся данные разбивают на обучающую и тестовую выборки. Обучение производится с использованием обучающей выборки, а оценка качества предсказания на основе данных тестовой выборки.
Другим практическим методом оценки обобщающей способности решающего правила является
метод q-кратного перекрестного (скользящего) контроля (CV – cross validation). Все имеющиеся
данные разбиваются на примерно равных (по числу прецедентов) частей. Далее, отделяя из
выборки одну за другой каждую из этих частей, используют оставшиеся данные (составленные из
q-1 частей) как обучающую выборку, а отделенную часть – как тестовую. Итоговая оценка
ошибки определяется как средняя по всем разбиениям. Заметим, что само итоговое решающее
правило строится по всей имеющейся обучающей выборке.
Часто используют значения q=5 или 10. Если q=N-1, то говорят о методе скльзящего
контроля с одним отделяемым объектом (LOO – leave-one-out estimate).
Метод $$k$$ ближайших соседей (k nearest-neighbor, k-NN) относится к наиболее простым и в то же время универсальным методам, используемым как для решения задач классификации, так и восстановления регрессии. В случае классификации новый объект классифицируется путем отнесения его к классу, являющемуся преобладающим среди $$k$$ ближайших (в пространстве признаков) объектов из обучающей выборки. Если $$k=1$$ , то новый объект относится к тому же классу, что и ближайший объект из обучающей выборки.
Аналогичный способ используется и в задаче восстановления регрессии, с той лишь разницей, что в качестве ответа для объекта выступает среднее ответов k ближайших к нему объектов из обучающей выборки.
Опишем метод более формально. Пусть $$N_k(x)$$ – множество ближайших к $$x$$ объектов из обучающей выборки. Тогда для задачи классификации положим
$$f(x)=arg\,\, max_y \lvert \lbrace i:y^{(i)}=y,x^{(i)}\in N_k(x) \rbrace \rvert,$$а для задачи восстановления регрессии –
$$f(x)=\frac 1 k$ \sum_{x^{(i)} \in N_k(x)} {y^{(i)}}.$$В некоторых случаях данные ответы учитываются с весами, обратно пропорциональными расстоянию до объекта. Это особенно полезно для решения задачи классификации с несбалансированными данными, т. е. когда число объектов, относящихся к разным классам, сильно различно.
Для определения ближайших соседей обычно используется евклидово расстояние
$$\rho(x,x')=\sqrt{\sum^d_{j=1} {\lvert x_j-x_j' \rvert ^2}},$$однако оно применимо только для признаков, описываемых количественными переменными. Если все переменные качественные, то можно использовать расстояние Хэмминга
$$\rho(x,x')=\sum^d_{j=1} {I(x_j \neq x_j')}.$$В общем случае используют функцию
$$\rho(x,x')=\sum^d_{j=1} {a_j\rho_j(x_j,x_j')},$$где $$a_j$$ – неотрицательные параметры, $$\rho_j(x_j,x_j')=(x_j-x_j')^2$$ для качественных переменных, $$\rho_j(x_j,x_j')=I(x_j \neq x_j')$$ для качественных переменных. Заметим, что функция расстояния не обязательно должна быть метрикой и неравенство треугольника может быть не выполнено.
Для повышения точности модели также могут использоваться специальные алгоритмы обучения метрики расстояния (например, Large Margin Nearest Neighbour [8]).
Одним из основных параметров, влияющих на обобщающую способность алгоритма, является число "ближайших соседей" $$k$$ . В целом, выбор определенного значения обусловлен характером данных задачи. Большие значения $$k$$ могут привести как к более точному описанию границы, разделяющей классы, так и переобучению. Обычно для выбора $$k$$ применяют различные эвристики, в частности, метод перекрестного контроля.
Один из самых популярных методов машинного обучения – машина опорных векторов (SVM – Support Vector Machine) – является развитием идей, предложенных в 1960–1970 гг. В. Н. Вапником и А. Я. Червоненкисом. Окончательное очертание метод принял в 1995 г., когда было показано, как в этом методе можно эффективно использовать ядра [4].
Рассмотрим вначале случай двух линейно разделимых классов. Для удобства будем их кодировать числами 1,-1 т. е. $$\mathcal{Y}=\lbrace 1,-1\rbrace$$.
Оптимальной разделяющей гиперплоскостью называется гиперплоскость, такая, что расстояние от нее до ближайшей точки из обучающей выборки (не важно из какого класса) максимально. Таким образом, оптимальная разделяющая гиперплоскость максимизирует зазор (отступ) – расстояние от нее до точек из обучающей выборки. Часто это приводит к хорошим результатам и на объектах тестовой выборки.
Математическая постановка задачи выглядит следующим образом:
Требуется найти
$$max_{\beta,\beta_0,w} w,$$при ограничениях
$$y^{(i)}(\beta x^{(i)}+\beta_0)\geqslant w\,\,\,\,(i=1,2,...,N),$$ $$\lvert \lvert \beta \rvert \rvert =1,$$где $$\beta x^{(i)}$$ означает скалярное произведение
$$\beta x^{(i)}=\sum^d_{j=1} {\beta_j x^{(i)}_j},$$а $$\lvert \lvert \beta \rvert \rvert$$ – евклидову норму
$$\lvert \lvert \beta \rvert \rvert=\sqrt{\sum^d_{j=1} {\beta_j ^2}.$$Эквивалентная формулировка:
$$max_{\beta,\beta_0} \lvert \lvert \beta \rvert \rvert^2,$$при ограничениях
$$y^{(i)}(\beta x^{(i)}+\beta_0)\geqslant 1\,\,\,\,(i=1,2,...,N),$$Можно показать, что решение этой задачи имеет вид
$$\beta=\sum^N_{j=1} {a_iy^{(i)}x^{(i)}}, \,\,\,\, где\,a_i\geqslant 0,$$уравнение разделяющей гиперплоскости есть $$\beta x+\beta_0=0$$ и классификатор определяется правилом
$$f(x)=sign(\beta x+\beta_0)$$Если $$a_i>0$$ то $$x^{(i)}$$ называется опорной точкой или опорным вектором. Легко видеть, что опорные точки лежат на границе разделяющей полосы
$$-1 \leqslant \beta x+\beta_0 \leqslant 1$$следовательно, $$\beta_0=y^{(i)}-\beta x^{(i)}$$, где $$x^{(i)}$$ – произвольный опорный вектор.
В случае линейно не разделимых классов разрешим некоторым объектам из обучающей выборки "слегка" заходить за разделяющую гиперплоскость:
$$max_{\beta,\beta_0,\xi,w} w,$$при ограничениях
$$y^{(i)}(x^{(i)}\beta+\beta_0)\geqslant w(1-\xi_i),\,\,\xi_i\geqslant 0,\,\,\,\,(i=1,2,...,N),$$ $$\lvert \lvert \beta \rvert \rvert =1,$$ $$\sum^N_{j=1} {\xi_i \leqslant \Xi},$$где $$\Xi$$ – некоторая константа (параметр метода). При $$\Xi=0$$ получаем предыдущий случай (линейно разделимых классов). Значение $$\xi_i$$ пропорционально величине, на которую $$x^{(i)}$$ заходит за границу разделяющей полосы. В частности, -й объект будет классифицирован неправильно тогда и только тогда, когда $$\xi_i>1$$ . Чем меньше $$\Xi$$, тем меньше объектов классифицируется неправильно. С другой стороны, $$\Xi$$ должно быть достаточно велико, чтобы задача была совместной.
Эквивалентная формулировка:
$$max_{\beta,\beta_0,\xi} \frac 1 2$ \lvert \lvert \beta \rvert \rvert +C\sum^N_{j=1} {\xi_i},$$при ограничениях
$$y^{(i)}(x^{(i)}\beta+\beta_0)\geqslant 1-\xi_i,\,\,\xi_i\geqslant 0,\,\,\,\,(i=1,2,...,N).$$Здесь параметр $$C \geqslant 0$$ регулирует величину штрафа за то, что некоторые точки выходят за границу разделяющей полосы. Построенная задача является задачей квадратического программирования. Для ее решения можно использовать общие методы для решения таких задач, однако существуют весьма эффективные специальные методы.
Можно показать, что решение задачи единственно, если в обучающей выборке есть по крайней мере один представитель каждого из классов.
Дальнейшее усовершенствование метода – использование спрямляющих пространств. Пусть удается перейти от исходного пространства признаков $$\mathcal{X}$$ к новому пространству $$\mathcal{H}$$ (которое называется спрямляющим) с помощью некоторого отображения $$h:\mathcal{X} \rightarrow \mathcal{H}$$:
$$h(x)=(h_1(x),h_2(x),...,h_M(x)),$$где $$h_m(x)$$ – базисные функции $$(m=1,2,...,M)$$. Новый классификатор определяется теперь функцией
$$f(x)=sign(h(x)\beta x+\beta_0)$$Здесь $$h(x)\beta x+\beta_0=0$$ – разделяющая поверхность. Если отображение подобрано удачно, в новом пространстве классы могут быть линейно разделимы или близки к таковым.
Оказывается, все вычисления при обучении и при расчете функции $$f(x)$$ можно организовать так, что $$h(x)$$ встречается только в выражениях вида
$$K(x,x')=h(x)h(x').$$В частности уравнение разделяющей поверхности имеет вид
$$\biggl(\sum^N_{j=1} {a_iy^{(i)}h(x^{(i)})}\biggr)h(x)+\beta_0=0$$что эквивалентно
$$\sum^N_{j=1} {a_iy^{(i)}h(x^{(i)})}h(x)+\beta_0=0$$или
$$\sum^N_{j=1} {a_iy^{(i)}K(x^{(i)},x)}+\beta_0=0$$Функция $$K(x,x')$$ называется ядром. На практике, таким образом, вместо того, чтобы испытывать различные функции $$h$$ можно (так и поступают) подбирать наиболее подходящее ядро $$K(x,x')$$.
Заметим, что не любая функция $$K: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$$ представима в виде $$K(x,x')=h(x)h(x')$$, т. е. может быть использована в качестве ядра. Приведем перечень некоторых популярных функций- ядер:
Для того чтобы использовать метод опорных векторов для задачи классификации с числом классом K>2 , возможно использовать две стратегии:
K(K-1)/2 классификаторов на всех возможных
подзадачах бинарной классификации. Новый объект классифицируется всеми
построенными решающими правилами, затем выбирается преобладающий класс. Деревья решений [3] являются одним из наиболее наглядных и универсальных алгоритмов обучения. К достоинствам деревьев решений следует отнести:
Кроме того, существуют эффективные алгоритмы их настройки (обучения), например, CART – Classification and Regression Trees [3] или See5/C5.0.
Основная идея деревьев решений состоит в рекурсивном разбиении пространства признаков с помощью разбиений (splits): гиперплоскостей, параллельных координатным гиперплоскостям (если признак – количественный), либо по категориям (если признак номинальный). В каждом из полученных в конце процедуры "ящиков" $$R_1,R_2,...,R_M$$ функция аппроксимируется константой:
В алгоритме CART разбиения имеют вид:
Дерево строится рекурсивно с помощью следующей жадной процедуры, на каждом шаге максимально уменьшая значение функции, описывающей неоднородность данных, содержащихся в узле дерева. Пусть на текущем шаге имеется разбиение пространства признаков на области (ящики) $$R_1,R_2,...,R_M$$.
Разбиения проводятся до тех пор, пока в строящиеся вершины попадает достаточное количество точек обучающей выборки, или пока дерево не достигнет заданной глубины.
Используют различные способы измерить неоднородность, например,
где $$N_m$$ – количество точек из обучающей выборки, попавших в область $$R_m$$ .
Другой важный параметр модели – это глубина дерева решений, регулирующая, "как сильно" будет разбито пространство признаков. Небольшое число разбиений может привести к тому, что построенная модель не будет учитывать некоторые особенности распределения признаков, описывающих те или иные классы, и таким образом приведет к уменьшению точности предсказания. Чрезмерное число разбиений может привести к переобучению модели и снижению еe обобщающей способности.
Для того чтобы избежать переобучения, используется процедура отсечений (prunning) [3].
Один из общих подходов в машинном обучении заключается в использовании композиции "слабых" решающих правил. Итоговое правило строится путем взвешенного голосования ансамбля базовых правил. Для построения базовых правил и вычисления весов в последнее время часто используются две идеи:
Эксперименты показывают, что, как правило, бустинг работает на больших обучающих выборках, тогда как баггинг – на малых.
Одной из реализаций идеи баггинга является случайный лес [2].
Случайный лес, а точнее – случайные леса (random forests), является одним из наиболее универсальных и эффективных алгоритмов обучения с учителем, применимым как для задач классификации, так и для задач восстановления регрессии. Идея метода [2] заключается в использовании ансамбля из M деревьев решений (например, M=500), которые обучаются независимо друг от друга. Итоговое решающее правило заключается в голосовании всех деревьев, входящих в состав ансамбля.
Для построения каждого дерева решений используется следующая процедура:
p=d/3 , sz=1 для задачи
восстановления регрессии $$p=\sqrt d$$, sz=3. Одной из модификаций метода случайных деревьев является алгоритм крайне случайных деревьев (extremely random forests), в котором на каждом этапе для выбора признака, по которому будет проводиться разбиение, используется вновь сгенерированная случайная бутстрэп-выборка.
Среди достоинств алгоритма случайных деревьев можно выделить высокое качество предсказания, способность эффективно обрабатывать данные с большим числом классов и признаков, внутреннюю оценку обобщающей способности модели. Легко построить параллельную высоко масштабируемую версию алгоритма. Кроме того, доказано, что данный алгоритм не переобучается (с ростом M). Также метод обладает всеми преимуществами деревьев решений, в том числе отсутствием необходимости предобработки входных данных, обработкой как вещественных, так и категориальных признаков, поддержкой работы с отсутствующими значениями.
Градиентный бустинг деревьев решений (Gradient Boosting Trees – GBT) [6, 7] – другой универсальный алгоритм машинного обучения, основанный на использовании ансамбля деревьев решений. В отличие от случайного леса градиентный бустинг является развитием бустинг-идеи. Алгоритм минимизирует эмпирический риск жадным пошаговым алгоритмом, аналогичным методу градиентного спуска. Рассмотрим, например, задачу восстановления регрессии используют. Рассмотрим суммарный штраф на обучающей выборке как функцию от значений решающего правила f в точках $$x^{(1)},x^{(2)},...,x^{(N)}$$:
$$L(f)=L(f(x^{(1)}),f(x^{(2)}),...,f(x^{(N)}))=\sum^N_{i=1} {L(y^{(i)},f(x^{(i)})}$$Тогда градиент функции L(f) равен
$$grad\,\,L(f)=\Biggl( \frac {\delta L(y^{(1)},f(x^{(1)}))} {\delta f(x^{(1)})},\frac {\delta L(y^{(2)},f(x^{(2)}))} {\delta f(x^{(2)})},...,\frac {\delta L(y^{(N)},f(x^{(N)}))} {\delta f(x^{(N)})} \Biggr)$$На предварительном этапе алгоритм строит оптимальную константную модель $$f=g_0$$. На m-й
итерации конструируется дерево решений $$g_m$$
(небольшой глубины), аппроксимирующее
компоненты вектора антиградиента, вычисленного для текущей модели f. После этого значения в
узлах построенного дерева $$g_m$$
перевычисляются, так, чтобы минимизировать суммарную
величину штрафа $$L(f+g_m)$$ Далее осуществляем присваивание $$f \leftarrow f+vg_m$$, что и завершает
m-ю итерацию. Здесь v – параметр регуляризации (shrinkage), призванный бороться с возможным
переобучением. Он выбирается из интервала (0,1].
Для решения задачи восстановления регрессии часто используются следующие штрафные функции:
квадратичный штраф
$$L(y,f(x))=\frac {1}{2} (y-f(x))^2,$$абсолютный штраф
$$L(y,f(x))=\lvert y-f(x) \rvert .$$или функция Хьюбера
$$L(y,f(x))=\frac {1}{2} (y-f(x))^2=\begin{cases} \frac {1}{2} (y-f(x))^2,\text{при $\lvert y-f(x) \rvert \leqslant \delta$,}\\ \delta(\lvert y-f(x) \rvert - \frac {\delta}{2})^2,\text{при $\lvert y-f(x) \rvert > \delta$.} \end{cases}$$Заметим, что функция Хьюбера и квадратичный штраф дифференцируемы всюду, тогда как абсолютный штраф – везде, кроме точек, в которых $$y=f(x)$$.
Для задачи классификации с K классами метод остается прежним, только вместо одной функции
f конструируют сразу K функций $$f_k\,\,(k=1,2,...,K)$$. В качестве штрафа можно использовать
кросс-энтропию
где
$$p_y(x)=\frac {e^{f_y(x)}} {\sum^K_{k=1}e^{f_y(x)} }$$– есть оценка вероятности того, что $$f(x)=y$$. Итоговый классификатор определяется как
$$f(x)=arg\,\,max_yp_y(x).$$Более подробное описание алгоритма см. в [6, 7].
Другим популярным методом, использующим идею бустинга, является алгоритм AdaBoost и его модификации [5].
В задачах обучения без учителя (unsupervised learning) у объектов не известны выходы, и требуется найти некоторые закономерности в данных. К задачам обучения без учителя относят задачи кластеризации, понижения размерности, визуализации и др. Здесь рассматривается только кластеризация.
Задача кластеризации – это задача разбиения заданного набора объектов на кластеры, т. е. группы близких по своему признаковому описанию объектов. "Похожие" друг на друга объекты должны входить в один кластер, "не похожие" объекты должны попасть в разные кластеры.
Близость ("похожесть") объектов измеряется на основе функции расстояния $$\rho(x,x'):\mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$$
Рассмотрим один из алгоритмов, решающих задачу кластеризации – метод центров тяжестей ( -means). На вход алгоритма поступает набор данных
$$x^{(1)},x^{(2)},...,x^{(N)}, \,\,\, где \,\,\, x^{(i)}\in Q_1 \times Q_2 \times ... \times Q_d \,\,(i=1,2,...,N)$$и натуральное число K – количество кластеров, на которые нужно разбить данные. Алгоритм реализует пошаговую процедуру минимизации
$$min_{C,m_k}\sum^N_{i=1} {\rho(x^{(i)},m_k)},$$где $$m_k$$ – центр тяжести объектов, относящихся к k-му кластеру:
$$m_k=\frac {\sum_{C(i)=k} {x^{(i)}}} {\lvert \lbrace i:C(i)=k \rbrace \rvert} (k=1,2,...,K)$$При этом не гарантируется нахождение глобального минимума. На предварительном этапе строится некоторое разбиение входных данных на K групп (например, случайно). Пусть $$C(i)$$ – номер группы, к которой принадлежит -й объект. В ходе работы алгоритма значения $$C(i)$$ обновляются. В конце работы алгоритма значения $$C(i)$$ будут соответствовать разбиению данных на кластеры. Каждая итерация представляет собой последовательность следующих шагов:
Итерации завершаются, когда наступает стабилизация значений $$C(i)$$ , либо по достижении максимального значения числа итераций.
Метод центров тяжестей работает с явными описаниями объектов $$x^{(i)}$$ Модификацией этого метода является метод медиан, или метод срединных точек, ( K–medians, или K–medoids). На вход этого алгоритма подается число кластеров K и матрица расстояний $$D=(d_{ii'})$$, где $$d_{ii'}=\rho(x^{(i)},x^{(i')})(i,i'=1,2,...,N)$$. Заметим, что сама функция $$\rho(x,x')$$ может быть не известна.
Алгоритм ничем не отличается от предыдущего, но вместо центра тяжестей, для каждой группы будем находить медиану, или срединную точку, $$m_k=x_{i^*_k}$$, где
$$i^*_k=argmin_{C(i)=k} \sum_{C(i')=k} {d^2_{ii'}}.$$Каждая итерация представляет собой последовательность следующих шагов:
Как правило, результаты работы алгоритмов центров тяжестей и медиан (если они оба применимы к данным) близки.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.