Многомерная интерполяция и аппроксимация на основе теории случайных функций

Материал из MachineLearning.

Версия от 13:41, 29 июля 2009; Бахвалов Юрий (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Вступление
2 Подход к многомерной интерполяции и аппроксимации на основе теории случайных функций.
3 Метод машинного обучения.
4 Демонстрация в среде Matlab.

Вступление

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

Данную статью условно можно поделить на две части.

Первая часть посвящена использованию основ теории случайных функций применительно к задачам многомерной интерполяции и аппроксимации, а также машинному обучению и их теоретическому обоснованию. Цель теоретической части показать, что машинное обучение в его парадигме “обучения с учителем”, задачи многомерной интерполяции и аппроксимации, могут быть обобщены на основе теории случайных функций.
Во второй части изложены практические выводы из положений первой части в виде законченного метода машинного обучения (метода многомерной интерполяции и аппроксимации). Если читателя интересуют сугубо практические вопросы, Вы можете перейти сразу к изложению метода.
Предложенный метод позволяет получить точное решение задачи многомерной интерполяции или аппроксимации (“обучение с учителем”) гарантирующее оптимальность (при определенных минимальных допущениях, указанных в теоретической части). Метод достаточно прост и сводится к системе линейных уравнений, что может у читателя не знакомого с вопросом без изучения теоретической части вызвать подозрения в работоспособности или обобщающей способности метода. Но смею Вас уверить, что столь простая математическая конструкция в данном случае никак не ограничивает возможности. Если постараться объяснить кратко, то способности метода обеспечивает “специальная функция”, полученная в теоретической части, применение которой в системе линейных уравнений гарантированно обеспечивает оптимальное, с точки зрения аппарата случайных функций, решение. Использование данной функции позволяет сводить задачи многомерной интерполяции и аппроксимации или самые разнообразные задачи машинного обучения (с определенными допущениями) к решению системы линейных уравнений, гарантируя оптимальность полученного решения, отсутствие переобучения, осцилляций интерполянта и других нежелательных эффектов (если говорить более строго, то в реальных вычислениях используется лишь приближение теоретической “идеальной” функции в используемой части спектра, функция, которую можно записать алгебраически).

Подход к многомерной интерполяции и аппроксимации на основе теории случайных функций.

Введение.

Цель данной статьи показать, что машинное обучение в его парадигме “обучения с учителем”, задачи многомерной интерполяции и аппроксимации, могут быть обобщены на основе теории случайных функций.

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

Ниже будет показано, что использование понятия случайной функции и связанных с ней теоретических построений позволяет получать точные решения задач машинного обучения как задач многомерной интерполяции (или аппроксимации) гарантируя оптимальность решения с точки зрения критерия вероятности. Существует способ при минимальных допущениях получить оптимальное решение задачи машинного обучения путем решения системы линейных уравнений (с доказательством его единственности и оптимальности). Это позволяет получить точное решение, что снимает проблему поиска глобального оптимума и выбора топологии сети, которые имеют место во многих существующих итеративных алгоритмах “обучения с учителем” искусственных нейронных сетей.

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

Реализациями случайной функции являются функции, вид которых она принимает при наблюдении или, например, при проведении опыта. Сама же случайная функция представляет собой множество своих реализаций, с соответствующим распределением вероятностей. Для любой функции, проявления которой мы можем наблюдать, любую функцию которую мы можем в каком-либо смысле рассматривать, всегда можно поставить в соответствие случайную функцию, реализацией которой мы можем ее считать без каких-либо дополнительных предположений или допущений. Даже если мы рассматриваем какую-то конкретную функцию, например, вида y=2x, то и в этом случае мы можем ее считать частным случаем случайной функции, множество реализаций которой состоит из одного элемента с вероятностью реализации равной единице.

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

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

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

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

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

Многомерная интерполяция.

Рассмотрим задачу многомерной интерполяции, предполагая, что узлы интерполяции принадлежат реализации некоторой случайной функции.

Предположим, что функцию (1) можно считать реализацией некоторой случайной функции $F(x)$ которую можно записать как (2):

(1)

$y=f(x),\;x_i\in R^n, \;y\in R$

(2)

$F(x)=\sum^{m}_{i=1} {V_i \varphi_i (x)}+f_m(x),$

где $\varphi_i (x)$ - координатные функции, $V_i$ - случайные величины, $f_m(x)$ - функция математического ожидания

Под координатными функциями в (2) мы можем понимать любые произвольные функции. Условие заключается в том, что существуют какие-то координатные функции, такие, что мы можем через них записать случайную функцию вида (2). Количество слагаемых в (2) может быть произвольным, т.е. полагаем, что m может быть любым, в том числе и равным бесконечности (как вариант, сумма в (2) может быть обобщена до интеграла). В качестве частного случая (2) можно рассматривать, например, разложение в бесконечный ряд синусов и косинусов, когда реализациями данной случайной функции может быть множество всех непрерывных вещественных функций.
Предполагаем, что в (2) случайные величины $V_i$ независимы, распределены по нормальному закону, с математическими ожиданиями равными нулю и дисперсией равной единице.
Потенциально требование именно к нормальному закону на данном необязательно (но может быть спользовано в дальнейшем, например, при анализе и отображении подмножеств реализаций). Для выполнения следующих нескольких преобразований достаточно было бы потребовать, чтобы совместный закон распределения вероятностей для случайных величин из (2) был симметричным относительно начала координат и монотонно убывал с увеличением расстояний от начала координат.
Требования в (2) для случайных величин к математическому ожиданию равному нулю и дисперсии равной единице сделаны для удобства дальнейших преобразований. Если они не выполняются, можно сделать преобразование, получив снова выражение (2), но чтобы эти требования были выполнены. Предположим, что для какой-либо случайной величины дисперсия не равна единице, тогда мы можем заменить ее и одновременно заменить соответствующую ей координатную функцию (умножив ее на коэффициент), снова получив выражение вида (2). Если же математическое ожидание какой-либо случайной величины в (2) не равно нулю, тогда можно выполнить преобразование, изменив функцию математического ожидания таким образом, чтобы опять свести к виду (2).
Рассмотрим подробнее функцию $f_m(x)$ . В частном случае она может быть равна нулю или константе.
Если эта функция заранее известна, то мы можем исключить ее из дальнейших преобразований, осуществив вычитание ее значений из узлов интерполяции и одновременно удалив из выражения (2). После того как интерполяция по модифицированным узлам будет выполнена мы можем снова прибавить ее к полученному решению для получения окончательного результата.
Если эта функция заранее не известна, тогда мы можем принять ее за некую реализацию еще одной случайной функции которую можно снова выразить через выражение (2), и дальше повторять эту процедуру в случае необходимости.

Исключив функцию математического ожидания, получим выражение случайной функции:

(3)

$F(x)=\sum^{m}_{i=1} {V_i \varphi_i (x)}$

Обозначим через $v_1,v_2,...v_m$ конкретные значения случайных величин из (3), которые они приняли для какой-либо реализации. Тогда плотность распределения вероятностей реализаций в пространстве параметров $v_1,v_2,...v_m$ (т.е. вероятность реализации случайной функции вида (3), когда случайные величины $V_1,V_2,...V_m$ принимают некие конкретные значения $v_1,v_2,...v_m$ ) запишется в виде (4):

(4)

$P(v_1,v_2,...,v_m)=\frac{1}{{(2\pi)}^{\frac{m}{2}}}e^{-\frac{v_1^2+v_2^2+...+v_m^2}{2}}$

Пусть последовательности

(5)

$x_1,x_2,...,x_k\;(x_i\in R^n)$
$y_1,y_2,...,y_k\;(y_i\in R)$

представляют собой координаты и соответствующие им значения узлов интерполяции.

Считая, что узлы интерполяции принадлежат одной из реализаций случайной функции (3), которой соответствует вектор $v_1,v_2,...v_m$ , их можно выразить в виде системы уравнений (6):

(6)

$\{\begin{array}{ccccc} \sum^{m}_{i=1} {v_i\varphi_i(x_1)}=y_1\\ \sum^{m}_{i=1} {v_i\varphi_i(x_2)}=y_2\\ \vdots\\ \sum^{m}_{i=1} {v_i\varphi_i(x_k)}=y_k\\\end{array}$

Используя приведенные выше выражения, можно сказать, что наиболее вероятной реализацией случайной функции вида (3) соответствующей узлам интерполяции будет та, при которой функция плотности вероятности (4) принимает максимальное значение с учетом системы ограничений в виде равенств (6).

Поиск максимума функции (4), равносилен поиску минимума функции (7):

(7)

$v_1^2+v_2^2+...+v_m^2\rightarrow \min$

Отсюда можно сделать вывод, что решение задачи многомерной интерполяции как поиск наиболее вероятной реализации функции (2) или (3) удовлетворяющей узлам интерполяции, сводится к задаче квадратичного программирования с ограничениями в виде равенств.

Для поиска минимума (7) при системе ограничений (6), воспользуемся методом множителей Лагранжа.

Найдем Функцию Лагранжа:

Дисперсия случайной функции. Множество реализаций, удовлетворяющих узлам интерполяции.

Многомерная аппроксимация.

Выводы.

Метод машинного обучения.

Выпишем отдельно ключевые выражения, полученные в теоретической части в виде законченного метода.

Пусть последовательность $x_1,x_2,...,x_k\;(x_i\in R^n)$ представляет собой набор входных векторов для обучения. Пусть соответствующие им $y_1,y_2,...,y_k\;(y_i\in R)$ представляют собой набор выходных значений. Если значения на выходе представляют собой не один, а набор значений (вектора), то представленные преобразования можно рассмотреть последовательно для каждого из выходных параметров.
Метод позволяет определить функцию, связывающую значения на входе и на выходе (которая будет являться наиболее вероятной реализацией случайной функции, о чем шла речь в теоретической части). Метод также позволяет для произвольного входного значения определить среднеквадратическое отклонение ошибки, которую может дать полученная функция.

Функция, связывающая значения обучающей выборки на входе и на выходе будет определяться выражением (103):

(103)

$f^*(x)=q_1K_f(x-x_1)+q_2K_f(x-x_2)+...+q_kK_f(x-x_k)\;,\;x\in R^n$

Функцию $K_f(\tau)$ из (103) определим как (104):

(104)

$K_f(\tau)=C_K(\parallel\tau\parallel^2\ln(\frac{\parallel\tau\parallel^2}{t})+n)$

где $C_K,\;t,\;n\;$ - коэффициенты
$\parallel\tau\parallel$ - норма (длина) вектора $\tau$

Коэффициенты $q_1,q_2,...,q_k$ для (103) вычисляются из системы линейных уравнений (105):

(105)

$\{\begin{array}{ccccc} q_1(K_f(x_1-x_1)+S_m^2(x_1))+q_2K_f(x_1-x_2)+\;...\;+q_kK_f(x_1-x_k)=y_1\\ q_1K_f(x_2-x_1)+q_2(K_f(x_2-x_2)+S_m^2(x_2))+\;...\;+q_kK_f(x_2-x_k)=y_2\\ \vdots \\q_1K_f(x_k-x_1)+q_2K_f(x_k-x_2)+\;...\;+q_k(K_f(x_k-x_k)+S_m^2(x_k))=y_k\\\end{array}$

где $S_m(x)$ - среднеквадратическое отклонение для шума в точке $x$

Значения $S_m(x)$ определяют априорно предполагаемый уровень шума (погрешности) в данных обучения и соответственно степень приближения, с которой функция (103) воспроизведет данные обучения.
Если $S_m(x)=0$ , то это будет соответствовать частному случаю, когда погрешность или любая противоречивость в данных отсутствует и, искомая функция должна точно воспроизвести обучающую выборку. Т.е. задача обучения превращается в задачу многомерной интерполяции.
Если $S_m(x)=const>0$ , то это будет соответствовать случаю, когда предполагается что в данных обучения одинаково на всей выборке содержится шум, имеющий нормальное распределение со среднеквадратическим отклонением равным $S_m(x)=const$ . Задачу обучения можно рассматривать как многомерную аппроксимацию.
Если же уровень шума и его распределение в пространстве обучения неравномерно но известно, его наличие может быть задано в виде функции $S_m(x)$ (или достаточно только ее значений в узлах интерполяции).

Рассмотрим теперь коэффициенты в выражении (104).

Коэффициенты $t$ и $n$ в “идеальном случае” должны быть приблизительно равны и устремлены в бесконечность. В реальных вычислениях в качестве этих коэффициентов можно использовать $t\approx n \approx 10^5 \div 10^6$ при условии нормирования входных значений в диапазоне [-1,1] (они должны быть на несколько порядков больше диапазона изменения входных значений). С увеличением $t$ и $n$ разница от использования функции (104) вместо “идеальной функции” устремляется в область все более низких частот (при разложении искомой функции в спектр) измеряемыми $\omega\approx\sqrt{t}\approx\sqrt{n}$ и все меньше влияет на результаты обучения в области параметрического пространства, где находится обучающая выборка.
Коэффициент $C_K$ ,назовем его “калибровочным”, связан со свойствами априорной случайной функции. Хотя непосредственно случайные функции в представленных выражениях (103) - (105) не используются, эти выражения выведены на их основе. (Если $S_m(x)=0$ и обучение сводится к многомерной интерполяции, значение $C_K$ можно взять произвольным, поскольку при решении системы (105) и вычислении функции (103) он сократится.)

Процедура вычисления $C_K$ (предлагаемый вариант):

Рис.10. Оценка желаемой дисперсии на единичном расстоянии.

Калибровка требуется, чтобы найти баланс между возможными погрешностями, неточностями и противоречиями в данных обучения и возможной нелинейностью самой функции, связывающей вход и выход.
Предположим известно, что искомая функция (103) проходит через некий узел. Для калибровки можно априорно задать желаемый уровень дисперсии множества возможных реализаций $D^1$ на единичном расстоянии от узла. С увеличением $D^1$ при вычислениях (103) – (105) все “ большая роль” будет отводиться возможной нелинейности самой функции, с уменьшением – все больше “списываться” на наличие неточностей в данных обучения. При известном $D^1$ можно вычислить требуемый коэффициент $C_K$ :

(106)

$C_K=\frac{D^1 n}{(2n-\ln{(t)})\ln{(t)}}$

Рис.11. Пример одномерной интерполяции.

На рис.11. представлен пример одномерной интерполяции (при $S_m(x)=0$ ). Как видно из рисунка, интерполяция выполнена качественно (отсутствуют осцилляции, которые, например, часто имеют место при использовании интерполяционного многочлена Лагранжа).
С вводом $S_m(x)=const>0$ , интерполяция легко превращается в аппроксимацию - Рис.12.

Рис.12. Пример одномерной аппроксимации.

Рис.13. Пример двумерной интерполяции.

Рис.14. Пример двумерной аппроксимации.

На Рис. 11 – 14 представлены примеры интерполяции и аппроксимации в одномерном и двумерном случае в целях наглядности результатов. Выражения (103) – (105) могут быть использованы без ограничений для пространства любой размерности.
Для определения среднеквадратического отклонения возможной ошибки были получены выражения:

(107)

$\delta_{\tilde{F}}(x)=sqrt(n-D_a)$

Значение $D_a$ определяется следующим выражением:

(108)

$D_a=a_1K_f(x-x_1)+a_2K_f(x-x_2)+...+a_kK_f(x-x_k)$

А коэффициенты $a_1,a_2,...,a_k$ из (108) находятся решением системы уравнений (109):

(109)

$\{\begin{array}{ccccc}a_1(K_f(x_1-x_1)+S_m^2(x_1))+a_2K_f(x_1-x_2)+\;...\;+a_kK_f(x_1-x_k)=K_f(x-x_1)\\ a_1K_f(x_2-x_1)+a_2(K_f(x_2-x_2)+S_m^2(x_2))+\;...\;+a_kK_f(x_2-x_k)=K_f(x-x_2)\\ \vdots \\a_1K_f(x_k-x_1)+a_2K_f(x_k-x_2)+\;...\;+a_k(K_f(x_k-x_k)+S_m^2(x_k))=K_f(x-x_k)\\\end{array}$

Необходимо отметить, что при расчете среднеквадратического отклонения для каждого значения $x$ , необходимо рассчитать индивидуальное значение $D_a$ и заново решать систему уравнений (109) (хотя вычисления можно упростить, единожды вычислив обратную матрицу).

Рис.15. Пример одномерной интерполяции.

Рис.16. Среднеквадратическое отклонение распределения возможной ошибки как случайной величины для найденной функции на Рис.15

Ожидаемая ошибка функции (103) как случайная величина (исходя из теоретических положений в первой части) будет иметь нормальное распределение с рассчитанным по (107) среднеквадратическим отклонением и математическим ожиданием равным нулю. Зная это, мы можем ее отобразить графически, как показано на Рис.17.

Рис.17. Возможная ожидаемая ошибка, или распределение реализаций случайной функции, удовлетворяющих данным обучения

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

Ниже представлены рисунки, демонстрирующие аппроксимацию.

Рис.18. Пример одномерной аппроксимации.

Рис.19. Распределение реализаций или возможная ожидаемая ошибка (для функции на Рис.18).

Среднеквадратическая ошибка в (107) отражает разброс значений связанный с возможным распределением реализаций. Если требуется учесть возможный шум в самих данных, то для вычисления среднеквадратического отклонения можно воспользоваться выражением:

(110)

$\delta_{\tilde{F}}(x)=sqrt(n-D_a+S_m^2(x))$

Пример. Рассмотрим одномерный случай.

Предположим, распределение шума (его среднеквадратического отклонения) в области аппроксимации определяется выражением:

$S_m(x)=\frac{x^2}{40},\;x\in R$

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

Рис.20. Аппроксимация с учетом распределения шума.

Рис.21. Графическое отображение множества реализаций (с учетом шума).

Демонстрация в среде Matlab.

Предложенный подход к машинному обучению был реализован в виде набора функций в среде Matlab.
Ссылка [52Кб]на файл-архив с функциями.
Кроме самих функций в архиве содержатся программы-демонстрации в виде графического интерфейса пользователя в среде Matlab.

Рис.22. Демонстрация одномерной интерполяции и аппроксимации.