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

Обозначим через d (α( L), i ) число компонент сюръективного мультииндекса α( L) равных i , через | L| — число элементов множества L,а через Α( L) — множество всех сюръективных мультииндексов над множеством L.

Предложение 1.Если вектор a представлен в виде , где β i — произвольные действительные коэффициенты, то верно следующее равенство

(16)

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

В множестве , выберем множество X следующим образом: возьмем все ( n- 1)-мерные вектора с координатами ±1, а в качестве n- й координаты во всех векторах возьмем единицу.

Предложение 2.Множество x является максимальным множеством n- мерных векторов с координатами равными ±1 и не содержит пар противоположно направленных векторов.

Доказательство. Из равенства единице последней координаты всех векторов множества 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 1, a 2= a ¹ 2+ a ² 2, a 3= a ¹ 3+ a ² 3,…, 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 1= a 1/|| a 1||

2. b 2=( a 2-( a 2, b 2))/|| a 2-( a 2, b 1) b 1||. Причем a 2-( a 2, b 1) b 1≠ 0, так как ( a 1, a ² 2)=0, ( a ¹ 2-(( a 2, b 1) b 1, a ² 2)=0 и a² 2≠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 . Теорема доказана.

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

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