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

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

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

Содержание

Вступление

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

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

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

Введение.

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

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

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

Выводы.

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

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

  • Пусть последовательность 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(предлагаемый вариант):

Изображение:Pic2.jpg
Рис.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) могут быть использованы без ограничений для пространства любой размерности.

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