Обучение на примерах

Обучение на примерах (англ. Learning from Examples) - вид обучения, при котором интеллектуальной системе предъявляется набор положительных и отрицательных примеров, связанных с какой-либо заранее неизвестной закономерностью. В интеллектуальных системах вырабатываются решающие правила, с помощью которых происходит разделение множества примеров на положительные и отрицательные. Качество разделения, как правило, проверяется экзаменационной выборкой примеров. ^[1]

Математическая формализация

Пусть $X~$ — множество описаний объектов, $Y~$ — множество допустимых ответов. Существует неизвестная целевая зависимость — отображение $y^{*}\colon X\to Y$, значения которой известны только на объектах конечной обучающей выборки $X^m = \{(x_1,y_1),\dots,(x_m,y_m)\}$. Требуется построить алгоритм $a\colon X\to Y$, который приближал бы неизвестную целевую зависимость как на элементах выборки, так и на всём множестве $X~$.

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

Функции потерь и функционалы качества

Вводится функция потерь ${\mathcal L}(y,y')$, характеризующая величину отклонения ответа $y=a(x)~$ от правильного ответа $y'=y^{*}(x)~$ на произвольном объекте $x\in X$.

Типичный выбор функции потерь:

• В задачах классификации ${\mathcal L}(y,y') = [y'\neq y]~$;
• В задачах регрессии ${\mathcal L}(y,y') = (y'-y)^2~$.

Вводится функционал качества, характеризующий среднюю ошибку (эмпирический риск) алгоритма $a~$ на произвольной выборке $X^m~$

$Q(a,X^m) = \frac{1}{m} \sum_{i=1}^m {\mathcal L}(a(x_i),y^{*}(x_i)).$

Метод минимизации эмпирического риска — один из наиболее распространённых подходов к обучению алгоритмов по прецедентам. Он заключается в том, чтобы в заданной модели алгоритмов $A= \{a\colon X\to Y\}$ найти алгоритм, минимизирующий среднюю ошибку на обучающей выборке:

$a = \mathrm{arg}\min_{a\in A} Q(a,X^m).$

Тем самым задача обучения сводится к оптимизации и может быть решена численными методами оптимизации.

Обобщающая способность и проблема переобучения

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

Легко указать пример алгоритма, который минимизирует эмпирический риск до нуля, но при этом не обладает способностью к обобщению. Получив обучающую выборку $X^m~$, он запоминает её, и потом сравнивает предъявляемый объект $x~$ с обучающими объектами $x_i~$ из $X^m~$. В случае совпадения $x=x_i~$ алгоритм выдаёт правильный ответ $y_i~$. Иначе выдаётся произвольный ответ. Эмпирический риск принимает наименьшее возможное значение, равное нулю. Однако этот алгоритм не способен восстановить зависимость вне объектов обучения. Этот пример убедительно показывает, что для успешного обучения необходимо не только запоминать, но и обобщать.

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

Признаковое пространство

Признаком называется отображение $f\colon X\to D_f~$, где $D_f~$ — множество допустимых значений признака. Если заданы признаки $f_1,\dots,f_n~$, то вектор ${\mathbf x} = (f_1(x),\dots,f_n(x))$ называется признаковым описанием объекта $x\in X$. Признаковые описания допустимо отождествлять с самими объектами. При этом множество $X = D_{f_1}\times\dots\times D_{f_n}$ называют признаковым пространством.

В зависимости от множества $D_f$ признаки делятся на следующие типы:

• бинарный признак: $D_f=\{0,1\}$;
• номинальный признак: $D_f$ — конечное множество;
• порядковый признак: $D_f$ — конечное упорядоченное множество;
• количественный признак: $D_f$ — множество действительных чисел.

Часто встречаются прикладные задачи с разнотипными признаками, для их решения подходят далеко не все методы.

Решаемые задачи

Задача восполнения пропущенных данных

Исходная информация представляется в виде признаковых описаний. Значения некоторых признаков для некоторых объектов могут отсутствовать. Такие случаи часто возникают на практике. Например, экпериментатор может не записать результат наблюдения; респондент может отказаться отвечать на вопрос анкеты; пациент может не пройти данный вид обследования; и т. д. Однако многие методы анализа данных требуют, чтобы входная матрица признаковых описаний была заполнена полностью. Для заполнения отсутствующих значений часто применяют следующий подход. Считая данный признак целевым, строят алгоритм, прогнозирующий его значение в зависимости от других признаков. Пропущенные значения заполняют прогнозами. Эта операция проделывается со всеми признаками, имеющими пропущенные значения.

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

Алгоритмы

• Метод обратного распространения ошибки
• Сообщение минимальной длины
• Наивный байесовский классификатор
• Метод опорных векторов

Примечания

1. ↑ А.Н.Аверкин, М.Г.Гаазе-Рапопорт, Д.А.Поспелов "Толковый словарь по искусственному интеллекту" [1]

Литература

1. Айвазян С. А., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: основы моделирования и первичная обработка данных. — М.: Финансы и статистика, 1983.
2. Айвазян С. А., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: исследование зависимостей. — М.: Финансы и статистика, 1985.
3. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
4. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
5. Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8.
6. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. ISBN 5-86134-060-9.
7. Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004. ISBN 966-00-0341-2.
8. Hastie, T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2nd ed. — Springer-Verlag, 2009. — 746 p. — ISBN 978-0-387-84857-0.
9. Mitchell T. Machine Learning. — McGraw-Hill Science/Engineering/Math, 1997. ISBN 0-07-042807-7.

Ссылки

• www.MachineLearning.ru — профессиональный вики-ресурс, посвященный машинному обучению и интеллектуальному анализу данных