Моделирование свойств химических соединений с использованием искусственных нейронных сетей и фрагментных дескрипторов (1097754), страница 20
Текст из файла (страница 20)
Инвариантом помеченного графа H ∈ H V( n,E) называется скалярная функция от матричных элементов aij, значения которой не зависят отнумерации вершин графа.Теорема 1. Любой инвариант f(H) помеченного графа H ∈ H V( n,E) можетединственным образом быть представлен в виде:105Nf (H ) = ∑ c j g j (H )(71)j =1где: cj – это некоторые константы, не зависящие от H и зависящие от f; gj(H) –это число вложений графа H j ∈ H V( n,E) в граф H (т.е. количество различных подграфов графа H, изоморфных Hj). Таким образом, множество gj образует базис валгебре инвариантов графов из H V( n,E) .
Кроме того, величина любого инвариантаf(H) для графа H определяется числом подграфов в H, получаемых из H путемудаления ребер всеми неэквивалентными способами.Доказательство. Упорядочим графы из H V( n,E) следующим способом. Сначала пронумеруем произвольным образом все графы с n(n-1)/2 ребрами, потомвсе графы с [n(n-1)/2]-1 ребром и т.д., пока не будут пронумерованы графы, состоящие из изолированных вершин. Обозначим через B квадратную матрицу сэлементами bij = g j ( H i ) , ( i, j = 1, N ).
Очевидно, что: 1) если графы Hi и Hj имеютодинаковое количество ребер, то bij = g j ( H i ) = b ji = g i ( H j ) = 0 и b jj = g j ( H j ) = 1 ; и 2)если графы Hi и Hj имеют разное количество ребер и j < i, то bij = g j ( H i ) = 0 . Таким образом, матрица B является триангулярной, на ее диагонали находятсятолько единицы, а все элементы под диагональю равны нулю. Следовательно,существует обратная матрица B-1. Запишем систему уравнений:NNj =1j =1f ( H i ) = ∑ c j g j ( H i ) = ∑ bij c j( i = 1, N )(72)или в матричной форме f = Bc , где f = ( f ( H 1 ),K, f ( H N )) , c = (c1 ,Kc N ) - вектораколонки. Система уравнений (2) всегда имеет единственное решение: c = B −1 f .Следовательно, существует единственное разложение (71) инварианта f(H) длязаданной нумерации графов Hj.Покажем, что разложение (71) не зависит от нумерации графов Hj. Предположим, что некоторая нумерация приводит к векторам f ′ , c ′ и матрице B’(не обязательно триангулярной).
Переход от первой нумерации ко второй можно осуществить при помощи подстановки π: j → π ( j ) ( i = 1, N ) либо соответствующей матрицы подстановки X размера N×N, причем det X ≠ 0 . Очевидно, чтоXf = f ′ , Xc = c ′ и XBX −1 = B′ . Как было показано выше, по крайней мере для од-106ной нумерации графов в разложении (71) справедливо f = Bc . Умножая обечасти этого уравнения на X, имеем: f ′ = Xf = ( XBX −1 )( Xc ) = B′c ′ .Следователь-но, разложение (71) верно при любой нумерации графов Hj.Теорема 1 доказана. ■Теорема 2.
Любой инвариант f(H) помеченного графа H ∈ H V( n,E) может бытьпредставлен при помощи полинома от переменных, равных числам встречаемости некоторых связных подграфов в H. Количество вершин в таких подграфах истепень полинома меньше либо равно n.Доказательство. Прежде всего покажем, что число встречаемости любогонесвязанного подграфа C в графе H может быть выражено через числа встречаемости некоторых связных подграфов в H. Предположим, что C состоит из kkкомпонент связности, т.е. C = Ui =1 Ci , где {Ci} – связанные подграфы, причемCi ∩ C j = ∅ , i ≠ j .
В общем случае возможно, что некоторые подграфы из {Ci}изоморфны друг другу. Разобьем множество {Ci} на p групп Ωi ( i = 1, p ) такимобразом, чтобы подграфы в каждой из групп были изоморфны друг другу, аподграфы из разных групп, наоборот, друг другу неизоморфны.
Пусть mi – число элементов в Ωi, mi ≥ 1 ,∑pi =1mi = k и i = 1, p . Пронумеруем подграфы из {Ci}следующим образом: сначала пусть идут подграфы из {Ci}, относящиеся кгруппе Ω1, потом относящиеся к группе Ω2 и т.д. Пусть Mi - множество всехподграфов графа H, изоморфных подграфам из группы Ωi, а li – число элементов в Mi ( i = 1, p ). Очевидно, что li ≥ mi .Построим новые подграфы графа H, выбирая всеми возможными способами mi разных элементов из Mi одновременно для всех i = 1, p . Число такихподграфов равно∏pi =1Clmi i , Clmi i = li !/[ mi !(li − mi )!] . Полученные из Mi подграфыможно отнести к двум типам.
В первом случае исходные подграфы из Mi не пересекаются, во втором – пересекаются. Обозначим через t1 и t2 число подграфовпервого и второго типа, соответственно. Очевидно, что t1 + t2 =∏pi =1Clmi i . Заме-тим, что t1 равно числу встречаемости подграфа C в H и совпадает, согласноопределению, с числом подграфов в H, изоморфных C. Подграфы же второго107типа имеют меньше k компонент связности, и сумма t1 + t2 =∏pi =1Clmi i являетсяполиномом степени k = ∑i =1 mi от переменных li ( i = 1, p ).pТаким образом, число встречаемости t1 несвязного подграфа C с k компонентами связности можно выразить через числа встречаемости связных компонент и некоторых подграфов с меньшим чем k числом компонент связности.Применяя многократно этот результат ко всем несвязным подграфам, можноприйти к формулировке теоремы 2.Теорема 2 доказана.
■3.3. Теоретические основы сочетания искусственных нейронных сетей и фрагментных дескрипторовТрадиционно принято считать, что теоретическую основу использованиямногослойных нейронных сетей составляет нейросетевая интерпретация теоремы Колмогорова о представлении непрерывных функций нескольких переменных в виде суперпозиций непрерывных функций одного переменного и сложения [333], которая в исходном виде была сформулирована следующим образом.Теорема.
При любом целом n ≥ 2 существуют такие определенные наединичном отрезке E1 = [0; 1] непрерывные действительные функции ψpq(x),что каждая определенная на n-мерном единичном кубе En непрерывная действительная функция f(x1,…,xn) представима в виде2 n +1⎡nf ( x1 ,K, xn ) = ∑ χ q ⎢∑ψq =1⎣ h=1pq⎤( x p )⎥ ,⎦(73)где функции χq(y) действительны и непрерывны.Эта теорема, появившаяся в 1957 году в результате научной полемикимежду академиками А. Н. Колмогоровым и В. И. Арнольдом, первоначально неимела никакого отношения к нейронным сетям и только в 1987 году была переложена в термины теории нейронных сетей в работе Р.
Хехт-Нильсена (R.Hecht-Nielsen) [334]. В этой своей новой формулировке теорема доказываетпредставимость функции многих переменных достаточно общего вида Rn→Rm спомощью двухслойной (трехслойной с формальным учетом входного слоя)108нейронной сети с прямыми полными связями с n компонентами входного сигнала, 2n+1 компонентой первого (скрытого) слоя с заранее известными ограниченными функциями активации (например, сигмоидными) и m компонентамивторого слоя с неизвестными функциями активации.
Теорема, таким образом, внеконструктивной форме доказывает решаемость задачи представления функции достаточно произвольного вида на нейронной сети и указывает для каждойзадачи минимальные значения числа нейронов сети, необходимых для ее решения. Решаемость задачи представления функции при помощи теоремы Колмогорова в конструктивной форме было найдено несколько позже в работах Д. А.Шпрехера (D. A. Sprecher) [335, 336], в которых приведен численный алгоритмнахождения неизвестных функций активации второго слоя.Поскольку теорема Колмогорова в интерпретации Хехт-Нильсена описывает нейронную сеть, в которой один из слоев содержит нейроны с нефиксированной функцией активации, она не может быть непосредственно применена кнаиболее популярным архитектурам нейронных сетей, например, ко многослойному персептрону либо к нейросетям радиальной базисной функции, в которых все нейроны имеют функции активации фиксированного вида.
Эта проблема была, однако, решена в 1992 г. в работе Куркова (Kůrková) [337], в которой, основываясь на теореме Колмогорова, доказывается способность многослойной нейронной сети с двумя слоями скрытых нейронов с фиксированнымифункциями активации (например, сигмоидными) аппроксимировать любую непрерывную функцию многих переменных, а также оценить, исходя из свойстваппроксимируемой функции, необходимое для этого число скрытых нейронов иточность аппроксимации.С другой стороны, как показано было нами выше (теорема 2 из раздела3.2), любой инвариант помеченного графа может быть представлен при помощи полинома от переменных, равных числам встречаемости некоторыхсвязных подграфов в этом графе, и принимая во внимание, что1) полином является непрерывной функцией,2) молекулярное свойство является инвариантом молекулярного графа, независящим от нумерации его вершин,1093) число встречаемости некоторого подграфа в графе является значениемсоответствующего фрагментного дескриптора для этого графа,мы сразу приходим к формулировке центрального положения данной диссертационной работы: любая сколь угодно сложная зависимость между структуройорганического соединения и его свойством может быть аппроксимирована припомощи многослойной нейронной сети персептронного типа с двумя скрытымислоями нейронов и набора фрагментных дескрипторов.
Следует, однако, отметить, что в большинстве случаев для аппроксимации зависимости «структурасвойство», как показывает опыт, достаточно и одного слоя скрытых нейронов.110ГЛАВА 4. РАЗРАБОТКА НЕЙРОСЕТЕВЫХ ПОДХОДОВДанная глава содержит описание предложенных нами подходов к решению перечисленных в разделе 1.4 проблем, связанных с применением искусственных нейронных сетей для решения прикладных задач, в частности, для поиска количественных корреляций «структура-свойство».4.1. Подход к решению проблемы «переучивания» нейронных сетейОдной из основных проблем, с которой мы столкнулись в начале 1990-ыхгодов уже в ходе самых первых работ по применению аппарата искусственныхнейронных сетей для прогнозирования свойств органических соединений быласвязана с эффектом «переучивания» и необходимостью поиска эффективныхметодов его предотвращения.4.1.1.
Суть эффекта «переучивания» нейросетейЭффект «переучивания» (overtraining) нейросетей был, по-видимому,впервые описан в математической литературе в 1990 г (см. [338]). Он наблюдается при обучении многослойных нейронных сетей с обратным распространением ошибки (т.е. многослойных персептронов) в том случае, когда число примеров в обучающей выборке невелико по сравнению с числом настраиваемыхпараметров нейросети (т.е. синаптических весов и порогов активации нейронов). В настоящее время его принято считать особым проявлением эффекта«переподгонки данных» (overfitting), наблюдаемого во многих методах машинного обучения (о сходстве и различии понятий «переучивания» и «переподгонки» см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
