Нейробум: поэзия и проза нейронных сетей

Вид материала

Документы

Содержание Доказательство теоремы Доказательство теоремы.

Подобный материал:

• Ю. Н. Шунин Лекции по теории и приложениям искусственных нейронных сетей,Рига,2007, 190.96kb.
• Я. А. Трофимов международный университет природы, общества и человека «Дубна», Дубна, 71.95kb.
• Курсовая работа по дисциплине " Основы систем искусственного интеллекта" Тема: Опыт, 903.59kb.
• Нейрокомпьютерная техника: Теория и практика, 2147.23kb.
• Заочный Государственный Университет Внастоящее время все большее применение в разработке, 64.47kb.
• Особенности применения нейронных сетей в курсе «Интеллектуальные информационные системы», 82.99kb.
• Применение аппарата нейронных сетей системы matlab для аппроксимации степенных математических, 50.69kb.
• Автоматизированная система рубрикации лекционного материала с использованием нейронных, 114.4kb.
• Ульяновский Государственный Технический Университет Кафедра вычислительной техники, 216.41kb.
• Isbn 5-7262-0634 нейроинформатика 2006, 96.9kb.

^

Доказательство теоремы

В данном разделе приведено доказательство теоремы о числе линейно независимых образов в пространстве k-х тензорных степеней эталонов.

При построении тензорных сетей используются тензоры валентности k следующего вида:

,

(13)

где  – n-мерные вектора над полем действительных чисел.

Если все вектора , то будем говорить о k-й тензорной степени вектора a, и использовать обозначение . Для дальнейшего важны следующие элементарные свойства тензоров вида (13).

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

.

(14)

Доказательство этого свойства следует непосредственно из свойств тензоров общего вида.

2. Если в условиях свойства 1 вектора являются тензорными степенями, то скалярное произведение имеет вид:

.

(15)

Доказательство непосредственно вытекает из свойства 1.

3. Если вектора a и b ортогональны, то есть  то и их тензорные степени любой положительной валентности ортогональны.

Доказательство вытекает из свойства 2.

4. Если вектора a и b коллинеарны, то есть , то .

Следствие. Если множество векторов  содержит хотя бы одну пару противоположно направленных векторов, то система векторов  будет линейно зависимой при любой валентности k.

5. Применение к множеству векторов  невырожденного линейного преобразования B в пространстве  эквивалентно применению к множеству векторов  линейного невырожденного преобразования, индуцированного преобразованием B, в пространстве .

Сюръективным мультииндексом  над конечным множеством L назовем k-мерный вектор, обладающий следующими свойствами:

1. для любого  существует  такое, что ;

2. для любого  существует  такое, что .

Обозначим через  число компонент сюръективного мультииндекса  равных i, через  – число элементов множества L, а через  – множество всех сюръективных мультииндексов над множеством L.

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

(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 содержится ровно  вектор. Каждый вектор  можно представить в виде , где . Для нумерации векторов множества X будем использовать мультииндекс I. Обозначим через  число элементов в мультииндексе I. Используя введенные обозначения можно разбить множество X на n непересекающихся подмножеств: , .

Теорема. При k в множестве  линейно независимыми являются  векторов.

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

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

 

таких, что  при всех  и  при всех i, тогда все вектора множества линейно независимы.

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

1. 
   

2. . Причем , так как ,  и .
   

...

j.        . Причем , так как , при всех i,  и .

...

^ Доказательство теоремы. Произведем линейное преобразование векторов множества X с матрицей . Легко заметить, что при этом преобразовании все единичные координаты переходят в единичные, а координаты со значением -1 в нулевые. Таким образом . По пятому свойству заключаем, что число линейно независимых векторов в множествах X и Y совпадает. Пусть . Докажем, что  при  содержит компоненту, ортогональную всем . Из предложения 1 имеем

.

(17)

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

(18)

Обозначим первую сумму в (18) через . Докажем, что  ортогонален ко всем , и второй сумме в (18). Так как , существует . Из свойств сюръективного мультииндекса следует, что все слагаемые, входящие в  содержат в качестве тензорного сомножителя , не входящий ни в одно тензорное произведение, составляющие в сумме . Из свойства 2 получаем, что . Аналогично, из того, что в каждом слагаемом второй суммы  следует ортогональность  каждому слагаемому второй суммы в (18) и, следовательно, всей сумме.

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

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

(19)

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

.

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

(20)

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

(

(21)

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

(22)

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