Учебное пособие по курсу «Нейроинформатика»

Доказательство. Из равенства единице последней координаты всех векторов множества X следует отсутствие пар противоположно направленных векторов. Пусть x — вектор с координатами ±1, не входящий в множество X, следовательно последняя координата вектора x равна минус единице. Так как в множество X включались все (n-1) — мерные вектора с координатами ±1, то среди них найдется вектор, первые n-1 координата которого равны соответствующим координатам вектора x со знаком минус. Поскольку последние координаты также имеют противоположные знаки, то в множестве X нашелся вектор противоположно направленный по отношению к вектору x. Таким образом множество X максимально.

Таким образом в множестве X содержится ровно 2^n-1 вектор. Каждый вектор x∈X можно представить в виде , где I⊂{1, …, n-1}. Для нумерации векторов множества X будем использовать мультииндекс I. Обозначим через |I| число элементов в мультииндексе I. Используя введенные обозначения можно разбить множество X на n непересекающихся подмножеств: P_i = {x_I, |I|=i}, .

Теорема. При k в множестве {x^⊗k} линейно независимыми являются

векторов.

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

Лемма. Пусть дана последовательность векторов

a₁,a₂=a¹₂+a²₂,a₃=a¹₃+a²₃,…,a_m=a¹_m+a²_m

таких, что (a_i,a²_j)=0 при всех i<j и (a¹_i,a²_i)=0, a²_i≠0 при всех i, тогда все вектора множества {a_i} линейно независимы.

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

1. b₁=a₁/||a₁||

2. b₂=(a₂-(a₂,b₂))/||a₂-(a₂,b₁)b₁||. Причем a₂-(a₂,b₁)b₁ ≠ 0, так как (a₁, a²₂)=0, (a¹₂-((a₂,b₁)b₁,a²₂)=0 и a²₂≠0.

…

j.

Причем , так как (a_i, a²_j)=0, при всех i,

и a²_j≠0.

…

Доказательство теоремы. Произведем линейное преобразование векторов множества x с матрицей

Легко заметить, что при этом преобразовании все единичные координаты переходят в единичные, а координаты со значением –1 в нулевые. Таким образом .

По пятому свойству заключаем, что число линейно независимых векторов в множествах X и Y совпадает. Пусть 1≤m≤k. Докажем, что y_I^⊗k при |I|=m содержит компоненту, ортогональную всем y_J^⊗k, |J|≤m, J≠I.

Из предложения 1 имеем

(17)

Представим (17) в виде двух слагаемых:

(18)

Обозначим первую сумму в (18) через y_I0^⊗k. Докажем, что y_I0^⊗k ортогонален ко всем y_J^⊗k, |J|≤m, J≠I, и второй сумме в (18). Так как I≠J, I⊄J, существует q∈I, q∉J.

Из свойств сюръективного мультииндекса следует, что все слагаемые, входящие в y_I0^⊗k содержат в качестве тензорного сомножителя e_q, не входящий ни в одно тензорное произведение, составляющие в сумме y_J^⊗k. Из свойства 2 получаем, что (y_J^⊗k, y_I0^⊗k) = 0. Аналогично, из того, что в каждом слагаемом второй суммы L≠I, I⊄L следует ортогональность y_I0^⊗k каждому слагаемому второй суммы в (18) и, следовательно, всей сумме.

Таким образом y_I^⊗k содержит компоненту y_I0^⊗k ортогональную ко всем y_J^⊗k, |J|≤m, J≠I и (y_J^⊗k-y_I0^⊗k). Множество тензоров Y_k={y_I^⊗k, |I|≤k} удовлетворяет условиям леммы, и следовательно все тензоры в Y_k линейно независимы. Таким образом, число линейно независимых тензоров в множестве  не меньше чем

Для того, чтобы показать, что число линейно независимых тензоров в множестве {x^⊗k} не превосходит этой величины достаточно показать, что добавление любого тензора из Y к Y_k приводит к появлению линейной зависимости. Покажем, что любой y_I^⊗k при |I|>k может быть представлен в виде линейной комбинации тензоров из Y_k. Ранее было показано, что любой тензор y_I^⊗k может быть представлен в виде (17). Разобьем (17) на три суммы:

(19)

Рассмотрим первое слагаемое в (19) отдельно.

Заменим в последнем равенстве внутреннюю сумму в первом слагаемом на тензоры из Y_k:

(20)

Преобразуем второе слагаемое в (19).

(21)

Преобразуя аналогично (21) второе слагаемое в (20) и подставив результаты преобразований в (19) получим

(22)

В (22) все не замененные на тензоры из Y_k слагаемые содержат суммы по подмножествам множеств мощностью меньше k. Проводя аналогичную замену получим выражение, содержащее суммы по подмножествам множеств мощностью меньше k-1 и так далее. После завершения процедуры в выражении останутся только суммы содержащие вектора из Y_k, то есть y_I^⊗k будет представлен в виде линейной комбинации векторов из Y_k. Теорема доказана.

Лекция 7.1. Двойственные сети

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