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

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

Версия от 20:16, 30 июля 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), воспользуемся методом множителей Лагранжа.

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

(8)

$L(v_1,...,v_m,\lambda_1,...,\lambda_k)=v_1^2+v_2^2+...+v_m^2+\sum^{k}_{j=1} {\lambda_j ((\sum^{m}_{i=1} {v_i\varphi_i(x_j)})-y_j)}$

Обозначим вектором $V^*(v_1^*,v_2^*,...,v_m^*)$ решение задачи.
Из условия $\frac {dL}{d\lambda_j}=0$ опять получим уравнения (6).
Из условия $\frac {dL}{dv_i}=0$ получим:

(9)

$v_i^*=-0.5 \sum^{k}_{j=1} {\lambda_j \varphi_i (x_j),\;i=1,...,m}$

Обозначим последовательности значений координатных функций $(\varphi_1(x_i),\varphi_2,(x_i),...,\varphi_m(x_i))$ как вектора $L_i\;,\;i=1,...,k\;,\;L_i\in R^m$ .

Введем коэффициенты $q_1,q_2,...,q_k\;,$ обозначив $q_i=-0.5\lambda_i\;,\;i=1,..,k$ . Тогда (9) можно записать через новые обозначения в виде линейной комбинации векторов (10):

(10)

$V^*=q_1L_1+q_2L_2+...+q_kL_k$

Выражение (10) можно интерпретировать с геометрической точки зрения. Поиск минимума функции (7), с системой ограничений (6), равносилен опусканию перпендикуляра из начала координат на гиперплоскость, образуемую пересечением гиперплоскостей, заданных в виде уравнений (6) (подставив в (6) значения координатных функций, мы можем понимать их как задание гиперплоскостей и их пересечения в n-мерном пространстве), следовательно, $V^*$ будет являться линейной комбинацией их перпендикуляров.

Систему ограничений (6) можно записать через скалярные произведения векторов (11):

(11)

$\{\begin{array}{ccccc} L_1V^*=y_1\\ L_2V^*=y_2\\ \vdots\\ L_kV^*=y_k\\\end{array}$

Заменив $V^*$ изпользуя (10) получаем систему уравнений:

(12)

$\{\begin{array}{ccccc} q_1L_1L_1+q_2L_1L_2+...+q_kL_1L_k=y_1\\ q_1L_2L_1+q_2L_2L_2+...+q_kL_2L_k=y_2\\ \vdots\\ q_1L_kL_1+q_2L_kL_2+...+q_kL_kL_k=y_k\\\end{array}$

Обозначим как вектор $L_*$ последовательность значений $(\varphi_1(x),\varphi_2(x),...,\varphi_m(x))\;,\;x\in R^n$ .
Тогда наиболее вероятную реализацию $y=f^*(x)$ случайной функции (3) можно выразить как выражение (13):

(13)

$f^*(x)=\sum^{m}_{i=1} {v_i^*\varphi_i(x)}=L_*V^*=q_1L_*L_1+q_2L_*L_2+...+q_kL_*L_k$

Рассмотрим более подробно скалярное произведение $L_iL_j$ :

(14)

$L_iL_j=\sum^{m}_{t=1} {\varphi_t(x_i) \varphi_t(x_j)}=K_f(x_i,x_j)\;,\;x_i,x_j \in R^n$
что является не чем иным как каноническим разложением корреляционной функции.

Тогда систему уравнений (12) можно записать в виде (15):

(15)

$\{\begin{array}{ccccc} q_1K_f(x_1,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_2K_f(x_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_kK_f(x_k,x_k)=y_k\\\end{array}$

а выражение (13), для наиболее вероятной реализации, в виде (16):

(16)

$f^*(x)=q_1K_f(x,x_1)+q_2K_f(x,x_2)+...+q_kK_f(x,x_k)$

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

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

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

Обозначим сформулированные требования в виде набора положений:
1. Плотность вероятности реализаций, преобразующихся друг в друга параллельным переносом системы координат должна быть одинаковой. Предположим, что мы имеем две реализации $f_1(x)$ и $f_2(x)$ такие, что:

(17)

$\forall x \;f_1(x)=f_2(x+t),\;x,t \in R^n\;,\;t=const$

Тогда плотность вероятности реализаций $f_1(x)$ и $f_2(x)$ должна быть равна.
2. Плотность вероятности реализаций, преобразующихся друг в друга одинаковым изменением масштаба по всем направлениям должна быть одинаковой. Предположим, что мы имеем две реализации $f_1(x)$ и $f_2(x)$ такие, что:

(18)

$\forall x \;f_1(x)=kf_2(x/k),\;x \in R^n$
где $k$ - некоторый коэффициент

Тогда плотность вероятности реализаций $f_1(x)$ и $f_2(x)$ должна быть равна.
3. Плотность вероятности реализаций, преобразующихся друг в друга поворотом системы координат должна быть одинаковой. Предположим, что мы имеем две реализации $f_1(x)$ и $f_2(x)$ такие, что:

(19)

$\forall x_1 \;f_1(x_1)=f_2(x_2),\; x_2=Ax_1,\;x_1,x_2 \in R^n$
где $A$ - некоторая матрица поворота

Тогда плотность вероятности реализаций $f_1(x)$ и $f_2(x)$ должна быть равна.

Выполнение первого пункта означает, что случайная функция будет стационарной. В этом случае ее можно записать в виде многомерного спектрального разложения. Обозначим $S(\omega)$ ее спектральную плотность (неотрицательная вещественная функция, симметричная относительно любых частот $\omega$ и $-\omega$ ).

(20)

$f(x)=\frac {1}{{(2\pi)}^{\frac {n}{2}}} \int\limits_{R^n}S^*(\omega)\sqrt{S(\omega)}e^{ix\omega}d\omega$
$x,\omega \in R^n\;,\;x\omega$ - их скалярное произведение

В выражении (20) $S^*(\omega)$ - реализация комплексной случайной функции, каждое значение которой является независимой случайной величиной (кроме дополнительного условия, о котором ниже) имеющей нормальное распределение, единичную дисперсию и математическое ожидание равное нулю, как для вещественной, так и мнимой части. Выражение (20) можно считать частным случаем (3), в котором $m=\infty$ , роль координатных функций выполняет $\sqrt{S(\omega)}e^{ix\omega}$ , а аналогом значений случайных величин выступает $S^*(\omega)$ . Функцию можно считать разложением реализации по базису функций пропорциональному $\sqrt{S(\omega)}e^{ix\omega}$ .
Наложим дополнительное условие на $S^*(\omega)$ (а соответственно, на случайную функцию), поскольку мы рассматриваем в данный момент интерполяцию вещественных функций, то ее значения для любых значений частот $\omega$ и $-\omega$ должны быть комплексно-сопряженными. Чтобы отразить это условие поделим пространство частот $R^n$ на две части $R_1^n$ и $R_2^n$ . Осуществить это разделение нужно таким образом, чтобы любые частоты $\omega$ и $-\omega$ лежали разных частях (например, любой гиперплоскостью, проходящей через начало координат). Тогда $S^*(\omega)$ можно записать как:

(21)

$S^*(\omega)=\{\begin{array}{ccccc} R^*(\omega)+iI^*(\omega),\;\omega\in R_1^n\\ R^*(\omega)-iI^*(\omega),\;\omega\in R_2^n\\\end{array}$

Где $R^*(\omega)$ и $I^*(\omega)$ можно рассматривать как реализации вещественных случайных функций, каждое значение которых одинаково для частот $\omega$ и $-\omega$ , является независимой случайной величиной, имеющей нормальное распределение, математическое ожидание равное нулю и дисперсию равную единице.

При выполнении условия на вещественность реализаций случайную функцию (20) можно записать как (22):

(22)

$f(x)=\frac {1}{{(2\pi)}^{\frac {n}{2}}} (\int\limits_{R_1^n}(R^*(\omega)+iI^*(\omega))\sqrt{S(\omega)}e^{ix\omega}d\omega+\int\limits_{R_2^n}(R^*(\omega)-iI^*(\omega))\sqrt{S(\omega)}e^{ix\omega}d\omega)$

Поскольку $R_1^n$ и $R_2^n$ симметричны относительно $\omega$ и $-\omega$ , то во втором интеграле в (22) можно перейти к области интегрирования $R_1^n$ заменив знак перед частотой. В этом случае получим:

(23)

$f(x)=\frac {1}{{(2\pi)}^{\frac {n}{2}}} (\int\limits_{R_1^n}(R^*(\omega)+iI^*(\omega))\sqrt{S(\omega)}e^{ix\omega}d\omega+\int\limits_{R_1^n}(R^*(-\omega)-iI^*(-\omega))\sqrt{S(-\omega)}e^{-ix\omega}d\omega)$

Выполнив далее преобразования, получим:

(24)

$f(x)=\frac {1}{{(2\pi)}^{\frac {n}{2}}} \int\limits_{R_1^n}\sqrt{S(\omega)}(R^*(\omega)(e^{i\omega x}+e^{-i\omega x})+iI^*(\omega)(e^{i\omega x}-e^{-i\omega x}))d\omega=$
$=\frac {2}{{(2\pi)}^{\frac {n}{2}}} \int\limits_{R_1^n}\sqrt{S(\omega)}(R^*(\omega)\cos(\omega x)-I^*(\omega)\sin(\omega x))d\omega$

Поскольку каждое значение $S^*(\omega)$ (для пар частот $\omega$ и $-\omega$ ) является независимой комплексной случайной величиной, с математическим ожиданием равным нулю и дисперсией равной единице, мы можем получить (25) - аналог выражения (7), минимизация которого при выполнении ограничений на узлы интерполяции обеспечит наиболее вероятную реализацию.

(25)

$\int\limits_{R_1^n}\mid S^*(\omega)\mid^2 d\omega\rightarrow\min$

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

(26)

$\int\limits_{R_1^n} (R^*(\omega)^2+I^*(\omega)^2) d\omega\rightarrow\min$

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

(27)

$\{\begin{array}{ccccc} \frac {2}{{(2\pi)}^{\frac {n}{2}}} \int\limits_{R_1^n}\sqrt{S(\omega)}(R^*(\omega)\cos(\omega x_1)-I^*(\omega)\sin(\omega x_1))d\omega=y_1\\ \frac {2}{{(2\pi)}^{\frac {n}{2}}} \int\limits_{R_1^n}\sqrt{S(\omega)}(R^*(\omega)\cos(\omega x_2)-I^*(\omega)\sin(\omega x_2))d\omega=y_2\\ \vdots\\ \frac {2}{{(2\pi)}^{\frac {n}{2}}} \int\limits_{R_1^n}\sqrt{S(\omega)}(R^*(\omega)\cos(\omega x_k)-I^*(\omega)\sin(\omega x_k))d\omega=y_k\\\end{array}$

Поиск наиболее вероятной реализации будет соответствовать нахождению функций $R^*(\omega)$ и $I^*(\omega)$ таких, при которых выполняются условия (27) и минимизируется значение выражения (26).

Дальнейшие рассуждения можно выполнить аналогично (8) – (16).

Функция Лагранжа примет вид:

(28)

$\int\limits_{R_1^n}(R^*(\omega)^2+I^*(\omega)^2)+\frac {2}{{(2\pi)}^{\frac {n}{2}}} \sum^{k}_{i=1}\lambda_i (\int\limits_{R_1^n}\sqrt{S(\omega)}(R^*(\omega)\cos(\omega x_i)-I^*(\omega)\sin(\omega x_i))d\omega-y_i)$

При дифференцировании (28) по $\lambda_i$ можно снова получить систему (27).
Поскольку любое значение функций $R^*(\omega)$ и $I^*(\omega)$ для произвольного $\omega$ выражения (28) можно считать независимой переменной, то соответственно по каждому из них можно выполнить независимое дифференцирование. В этом случае получим выражения:

(29)

$R^*(\omega)=-\frac{\sqrt{S(\omega)}}{{(2\pi)}^{\frac {n}{2}}}\sum^{k}_{i=1}\lambda_i\cos(\omega x_i)$

(30)

$I^*(\omega)=\frac{\sqrt{S(\omega)}}{{(2\pi)}^{\frac {n}{2}}}\sum^{k}_{i=1}\lambda_i\sin(\omega x_i)$

Подставив решения (29) и (30) в систему (24) получим выражение наиболее вероятной реализации:

(31)

$f(x)=-\frac {2}{{(2\pi)}^{n}}\sum^{k}_{i=1}\lambda_i \int\limits_{R_1^n}S(\omega)(\cos(\omega x_i)\cos(\omega x)+\sin(\omega x_i)\sin(\omega x))d\omega$

Выражение (31) преобразуется в (32):

(32)

$f(x)=-\frac {2}{{(2\pi)}^{n}}\sum^{k}_{i=1}\lambda_i \int\limits_{R_1^n}S(\omega)\cos(\omega(x_i-x))d\omega$

Поскольку подынтегральное выражение в (32) инвариантно к изменению $\omega$ на $-\omega$ , то мы можем перейти целиком в область интегрирования $R^n$ :

(33)

$f(x)=-\frac {1}{{(2\pi)}^{n}}\sum^{k}_{i=1}\lambda_i \int\limits_{R^n}S(\omega)\cos(\omega(x_i-x))d\omega$

Введем коэффициенты:

(34)

$q_i=-\frac{\lambda_i}{(2\pi)^n}$

Выражение для корреляционной функции (на самом деле, из-за введенных коэффициентов, это будет функция пропорциональная корреляционной):

(35)

$K_f(x_1,x_2)=\int\limits_{R^n}S(\omega)\cos(\omega(x_1-x_2))d\omega,\;x_1,x_2\in R^n$

Как видно из (35) спектральная плотность случайной функции играет роль спектра для ее корреляционной функции. Сама же корреляционная функция превращается в автокорреляционную, что и следовало ожидать из условия стационарности:

(36)

$K_f(\tau)=\int\limits_{R^n}S(\omega)\cos(\omega\tau)d\omega,\;\tau\in R^n$

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

Тогда наиболее вероятную реализацию можно выразить:

(37)

$f^*(x)=q_1K_f(x-x_1)+q_2K_f(x-x_2)+...+q_kK_f(x-x_k)$

Найдем систему уравнений для вычисления коэффициентов в (37). Подставив (29) и (30) в (27) получим:

(38)

$\{\begin{array}{ccccc} -\frac {2}{{(2\pi)}^{n}}\sum^{k}_{i=1}\lambda_i \int\limits_{R_1^n}S(\omega)(\cos(\omega x_i)\cos(\omega x_1)+sin(\omega x_i)\sin(\omega x_1))d\omega=y_1\\ -\frac {2}{{(2\pi)}^{n}}\sum^{k}_{i=1}\lambda_i \int\limits_{R_1^n}S(\omega)(cos(\omega x_i)\cos(\omega x_2)+\sin(\omega x_i)\sin(\omega x_2))d\omega=y_2\\ \vdots\\ -\frac {2}{{(2\pi)}^{n}}\sum^{k}_{i=1}\lambda_i \int\limits_{R_1^n}S(\omega)(\cos(\omega x_i)\cos(\omega x_k)+\sin(\omega x_i)\sin(\omega x_k))d\omega=y_k\\\end{array}$

Используя (34) и (36) в (38) получим систему уравнений для вычисления коэффициентов для (37) (аналог (15)):

(39)

$\{\begin{array}{ccccc} q_1K_f(x_1-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_2K_f(x_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_kK_f(x_k-x_k)=y_k\\\end{array}$

Таким образом, мы получили выражения (37) и (39) - аналоги выражение (15) и (16), а также выражение (36) для корреляционной функции. Для раскрытия неопределенности остается определить спектральную плотность $S(\omega)$ случайной функции.
Обозначим как $S_f(\omega)$ спектральное разложение Фурье реализаций рассматриваемой нами случайной функции. Из выражения (20) - спектрального разложения случайной функции видно, что спектр реализаций будет равен:

(40)

$S_f(\omega)=S^*(\omega)sqrt{S(\omega)}$

Теперь вернемся ко второму пункту (выражение (18)).

Обозначим за $S_f^1(\omega)$ спектр некоторой функции $f_1(x)$ , а $S_f^2(\omega)$ - спектр некоторой функции $f_1(x)$ .
Будем считать, что

(41)

$f_2(x)=kf_1(x/k),\;x\in R^n$

т.е. функции подобны, но совпадают в масштабе k:1.
Поскольку

(42)

$f_1(x)=\frac {1}{{(2\pi)}^{\frac{n}{2}}}\int\limits_{R^n}S_f^1(\omega)e^{ix\omega}d\omega$
$x,\omega\in R^n,\;x\omega$ - их скалярное произведение

Получим

$f_2(x)=kf_1(x/k)=k\frac {1}{{(2\pi)}^{\frac{n}{2}}}\int\limits_{R^n}S_f^1(\omega)e^{\frac{ix\omega}{k}}d\omega=$

(43)

$=\frac {1}{{(2\pi)}^{\frac{n}{2}}}\int\limits_{R^n}k^{(n+1)}S_f^1(\omega)e^{\frac{ix\omega}{k}}d\frac{\omega}{k}=\frac {1}{{(2\pi)}^{\frac{n}{2}}}\int\limits_{R^n}k^{(n+1)}S_f^1(\omega k)e^{ix\omega}d\omega$

Откуда можно вывести соотношение спектров подобных функций:

(44)

$S_f^2(\omega)=k^{n+1}S_f^1(\omega k)$

Для обеих рассмотренных функций значение выражения (25) должно быть одинаковым.
Функцию $S^*(\omega)$ для (25) можно выразить через спектры реализаций и спектральную плотность случайной функции:

(45)

$S^*(\omega)=\frac{S_f(\omega)}{\sqrt{S(\omega)}}$

Приравнивая выражение (25) для двух рассмотренных выше реализаций (причем, поскольку под знаком интегрирования берется значение по модулю, мы можем интегрировать по $R^n$ ), а также используя выражения (44) и (45) получаем:

$\int\limits_{R^n}\frac{\mid S_f^1(\omega)\mid^2}{S(\omega)}d\omega=\int\limits_{R^n}\frac{\mid S_f^2(\omega)\mid^2}{S(\omega)}d\omega=\int\limits_{R^n}\frac{k^{2n+2}\mid S_f^1(\omega k)\mid^2}{S(\omega)}d\omega=$

(46)

$=\int\limits_{R^n}\frac{k^{n+2}\mid S_f^1(\omega k)\mid^2}{S(\omega)}d(\omega k)=\int\limits_{R^n}\frac{k^{n+2}\mid S_f^1(\omega)\mid^2}{S(\omega/k)}d\omega$

Из выражения (46), сравнивая начало и конец полученных равенств можно получить соотношение для спектральной плотности:

(47)

$\frac{S(\omega/k)}{S(\omega)}=k^{n+2}$

Чтобы выполнялось третье положение (19), автокорреляционная функция должна обладать радиальной симметрией. Соответственно радиальной симметрией должна обладать и спектральная плотность. Тогда из (47) можно получить выражение для спектральной плотности:

(48)

$S(\omega)=\alpha \mid\omega\mid^{-(n+2)},\;\omega\in R^n$
где $\alpha$ - некоторый коэффициент

или(то же самое):

(49)

$S(\omega_1,\omega_2,...,\omega_n)=\alpha (\omega_1^2+\omega_2^2+...+\omega_n^2)^{-\frac{n+2}{2}}$
$\omega_1,\omega_2,...,\omega_n\in R$

Таким образом, в выражении (48-49) мы получили искомую спектральную плотность случайной функции. При использовании корреляционной функции с таким спектром и решении системы линейных уравнений (39) будет гарантированно получена наиболее вероятная реализация случайной функции (если брать в качестве основы положения (17) – (19)).
Коэффициент $\alpha$ в (48) – (49) может быть любым, поскольку его изменение одновременно увеличит или уменьшит все коэффициенты левой части системы уравнений (39) и в уравнении (37) в одинаковое количество раз, а соответственно и коэффициенты решения, которые при подстановке в (37) дадут ту же самую функцию.
Для непосредственно вычисления выражения функции со спектром (49) можно воспользоваться свойством симметричности функции. В этом случае для упрощения можно сначала рассмотреть одномерный вариант, после чего получить многомерный вариант, воспользовавшись требованием симметричности.

В одномерном случае требуемая спектральная плотность будет:

(50)

$S(\omega)=\mid\omega\mid^{-3}$

Тогда выражение для автокорреляционной функции (36) в одномерном случае примет вид:

(51)

$K(\tau)=\int\limits_{-\infty}^{\infty}\frac{\cos(\omega\tau)}{\mid\omega\mid^3}d\omega$

Выражение (51) можно записать как:

(52)

$K(\tau)=\lim_{\omega_0\rightarrow+0}(2\int\limits_{\omega_0}^{\infty}\frac{\cos(\omega\tau)}{\omega^3}d\omega)$

Последовательно интегрируя по частям, получим:

(53)

$K(\tau)=\lim_{\omega_0\rightarrow+0}(((-\frac{\cos(\omega\tau)}{\omega^2}+\tau^2\frac{\sin(\omega\tau)}{\omega\tau})\mid_{\omega_0}^{\infty})-\tau^2\int\limits_{\omega_0}^{\infty}\frac{\cos(\omega\tau)}{\omega}d\omega)$

В качестве последнего правого слагаемого в (53) был получен интегральный косинус. Рассмотрим его более подробно:

(54)

$-\int\limits_{\omega_0}^{\infty}\frac{\cos(\omega\tau)}{\omega}d\omega=-\int\limits_{\omega_0\tau}^{\infty\tau}\frac{\cos(\omega\tau)}{\omega\tau}d(\omega\tau)=-\int\limits_{\omega_0\mid\tau\mid}^{\infty}\frac{\cos(\omega\mid\tau\mid)}{\omega\mid\tau\mid}d(\omega\mid\tau\mid)$

Интегральный косинус может быть раскрыт:

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

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

Выводы.

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

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

Пусть последовательность $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. Демонстрация одномерной интерполяции и аппроксимации.