Вычислительные регуляторные сети Ю.Р. Цой Томский политехнический университет Томск 2007

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Введение Адаптация и механизмы адаптации в живой природе одни из важнейших вопросов естествознания. Адаптация тесно связана с понятиями: изменчивость, эволюция, самоорганизация Вопросы: 1. Что обеспечивает адаптацию организмов? (полинуклеотидные последовательности, окружающая среда) 2. Как возникли механизмы адаптации? (точно не известно) 3. Можно ли придумать аналог для искусственных систем? (точно не известно)

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Введение Для понимания адаптации необходимо моделировать открытые системы, так как в таких системах можно более полно рассматривать возникновение новых, непредусмотренных изначально видов взаимодействий в парах «объект-среда» и «объект- объект». Данная работа – попытка автора создать основу для исследования адаптации и реализации адаптивных систем, а также попытка осмыслить, в каком направлении развиваются эволюционные вычисления.

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Каверзные вопросы Действительно ли нейроэволюционный (НЭ) алгоритм используется для поиска только искусственной нейронной сети (ИНС)? Когда можно сказать, что закодированное в хромосоме решение представляет именно ИНС, а не что-нибудь другое?

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Пример (алгоритм NEvA) Хромосома: 0->3 (0.25) 1->3 (-1.78) 3->2 (-0.6) Является ли этот граф ИНС? Ответ зависит от интерпретации графа! Действительно ли НЭ алгоритм используется для поиска только ИНС? Ответ зависит от интерпретации декодированного решения!

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Вывод (промежуточный) Можно разработать эволюционный алгоритм для поиска графов в общем виде и этот алгоритм потенциально будет применим к очень широкому кругу задач. … и новые вопросы 1. Как облегчить разработку такого алгоритма? 2. Как кодировать решение, если необходимо найти очень большой граф? (количество вершин порядка 10 4 и более)

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Проблемы поиска очень больших графов 1. Прямое кодирование информации о графе требует много памяти. 2. Сложность модификации графа и поиска решения. Использование элементарных операций (добавление/удаление вершин и ребер) не позволяет осуществлять быстрый поиск, а применение более сложных специфичных операций затруднено ввиду желаемой «общности» алгоритма.

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Что если… ? Возможным решением этих проблем является использование генетического кодирования, более компактного, чем прямое представление графа, и допускающего как существенные, так и незначительные изменения структуры сети при использовании элементарных операций над этой сетью. Для описания такой кодировки и алгоритма, работающего с ней, будем использовать следующие понятия: Генные регуляторные сети Безмасштабные сети

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Генные регуляторные сети Генная регуляторная сеть (gene regulatory network) - набор взаимодействующих сегментов (генов) ДНК в клетке.

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Неявное «связывание» генов Интересным свойством ГРС является то, что в ГРС отсутствует понятие «связи», как самостоятельной единицы. Если пренебречь конечной скоростью распределения вещества в пространстве, то для связывания двух генов необходимо и достаточно, чтобы один ген производил некоторый белок, а другой ген этот белок использовал.

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Безмасштабные сети Граф владельцев акций компаний на Фондовой Бирже Нью-Йорка, 2001 г. (вершины – компании, ребра – владение не менее 5% акций) Источник: Caldarelli G. The Structure of Biological and Social Systems // SIAM News, Volume 37, Number 3, April 2004.

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Безмасштабные сети Другие примеры: 1. Интернет. 2. Социальные сети. 3. Сети химических реакций. 4. Сети соавторства в научных публикациях. 5. Экологические сети (отношение «хищник-жертва»). 6. и др. Некоторые предпосылки к существованию безмасштабных сетей: 1. Различная способность узлов к образованию связей. 2. Неоднородность распределения информации.

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Вычислительная регуляторная сеть (ВРС) Каждый узел имеет наборы входных и выходных сигналов с уникальными идентификаторами. Два узла называются связанными, если идентификаторы выходных сигналов одного узла совпадают с идентификаторами входных сигналов другого узла. узел сеть

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Вычислительная регуляторная сеть (ВРС) Каждому узлу поставлена в соответствие функция Полагаем, что РС находится в некоторой среде, в которой могут присутствовать некоторые сигналы независимо от состояния РС. Правило обновления сигналов среды: Выходной сигнал с идентификатором для i -го узла:

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Вычислительная регуляторная сеть (ВРС) Вектор сигналов среды x1x1 x2x2 x3x3 …xNxN x N+1 … ВРС 3 2 N+1 Среда Сигналы ВРС N 1 5 -источник сигнала с идентификатором

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Особенности ВРС Неявная связанность узлов за счет использования узлами сигналов с одинаковыми идентификаторами. Возможность существования множественных связей между двумя узлами. Функционирование в некоторой среде, в которой могут присутствовать как сигналы, отличные от входных и выходных для данной ВРС, так и другие ВРС.

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. ВРС и ИНС Если в узлах ВРС используются функции активации нейронов, то ВРС можно рассматривать как аналог ИНС с точки зрения вычисляемых функций, поскольку, всегда существует прямое и обратное преобразование ВРС в ИНС. Исходя из этого можно утверждать, что при определенных условиях ВРС являются универсальными аппроксиматорами, и эквивалентны машинам Тьюринга.

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Алгоритм эволюции ВРС (SARN – Self-Adaptive Regulatory Network) Особь включает в себя: 1. Информацию об узлах ВРС и их параметрах (тип узла, идентификаторы входных и выходных сигналов, веса сигналов и др.) 2. Вектор параметров мутации 3. Вектор истории мутаций Применяется турнирная селекция Используется только оператор мутации Реализация алгоритма (open-source):

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Операторы модификации (мутации) ВРС Оператор изменения веса входного сигнала узла. Оператор изменения веса выходного сигнала узла. Оператор изменения величины спонтанной активности узла. Оператор изменения типа узла. Оператор изменения идентификатора входного сигнала узла. Оператор изменения идентификатора выходного сигнала узла. Оператор включения/выключения узла. Оператор добавления/удаления входного сигнала узла. Оператор добавления/удаления выходного сигнала узла. Оператор добавления/удаления узла. Оператор расщепления узла. Каждому оператору соответствует свой параметр мутации m i

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Пример работы оператора расщепления узла Оператор предназначен для последовательного разделения узла и добавления новых идентификаторов сигналов с существующую сеть. Исходный узелРезультат работы оператора Вероятность P(i) выбора i -го узла сети зависит от степени d i его связанности

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Выбор оператора мутации Вероятность выбора k -го оператора пропорциональна величине Вероятность мутации Правило обновления параметров мутации: - количество мутаций i-го типа, имевших место для данной особи, начиная с самого первого поколения., где

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Эффекты мутации Несмотря на элементарность действий, осуществляемых многими из вышеперечисленных операторов, эффект может носить значительный характер для всей ВРС, поскольку эти операторы влияют не только на структуру ВРС (локальный эффект), но и на характеристики сигналов (глобальный эффект), распространяемых по ВРС. До мутацииПосле мутации

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Эксперименты Формула Функции, вычисляемые в узлах ВРС Задачи: 1.Исключающее ИЛИ 2.Proben1 (card1, diabetes1, glass1, heart1, horse1, thyroid1) Целевая функция: - среднеквадратичная ошибка - сложность сети - среднее изменение энергии сигналов

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Эксперименты: XOR SARNNEvA ПГА * ЭГА * ОРИ * 4612,537693,71261,99711,97619,7 СКО2594,073577,982427,72890,27407,70 Неудачи ,89 ** 7, ,74 *** 15,35 17 Структура ИНС: «2-4-1» * Для алгоритмов ПГА (Простой ГА), ЭГА (ГА с Элитизмом) и ОРИ (ОР с Инерционностью) y x1x1 x2x2 1 ** Среднее количество узлов; *** Средняя степень узла

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Эксперименты: XOR = 1 = 10 = 100 Количество вычислений целевой функции, N FE 52023,4±49830,618355,97±3262,224612,53±2594,07 Время поиска, поколения 259,65±197,1241,4±36,5822,62±13,02 Время поиска, сек. 3,05±4,200,50±0,580,32±0,34 Среднее количество узлов 10,03±4,958,54±3,606,89±2,31 Успешных запусков, % 100% Количество мутаций в сумме по всем решениям

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Эксперименты: XOR = 1 =

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Эксперименты: XOR

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Эксперименты: Proben1 Название проблемы Ошибка, SARN Структура ИНС, SARN, N : Ошибка, Proben1 docs Структура ИНС, Proben1 docs, N H : N C Cards112,79 %2 : 5413,37 %0 : 102 Diabetes134,90 %1 : 16,11124,1 %4 : 24 Glass128,30 %1,5 : 53,832,7 %8 : 120 Heart121,74 %1 : 70,919,72 %8 : 296 Horse132,97 %1,429 : 169,2929,19 %4 : 244 Thyroid12,11 %1,3 : 65,62,32 %24 : > 450 Данные предварительных экспериментов N – количество узлов ВРС – средняя степень узла N H – количество скрытых нейронов ИНС N C – количество связей

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Моделирование открытых систем Вектор сигналов среды x1x1 x2x2 x3x3 …xNxN x N+1 … ВРС Среда Сигналы ВРС Взаимодействие «объект-среда» - источник сигнала

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. ВРС2 ВРС3 Моделирование открытых систем Вектор сигналов среды x1x1 x2x2 x3x3 …xNxN x N+1 … ВРС1 Среда Сигналы ВРС1 Взаимодействие «объект-объект» - источник сигнала Сигналы ВРС2Сигналы ВРС3 x4x4 xMxM

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Заключение ВРС: Что нового при сравнении с ИНС? 1. Другое описание структуры (без описания связей). 2. Элементарные операции (добавление/удаление узлов, изменение весов сигналов и др.) над ВРС могут носить как локальный (точечный), так и глобальный (масштабный) характер. 3. Произвольные функции в узлах сети. 4. Возможность описывать, не меняя кодировки, сетевые структуры с простыми модулями (за счет существования множественных выходов узлов). 5. Изначальная ориентация на «существование» ВРС в некоторой сложной среде.

Цой Ю. Р. Вычислительные регуляторные сети. «Нейроинформатика – 2008», г. Москва. Заключение 1. Как зависит эволюция структуры ВРС от эволюции вектора m параметров мутации и от используемых операторов? 2. Можно ли провести содержательную интерпретацию работы ВРС на основании данных об изменении энергии сигналов с течением времени? 3. Каким образом можно регулировать распределение степеней узлов, а также параметра кластеризации ВРС? 4. Можно ли использовать ВРС для решения задач моделирования и оптимизации? Работа выполнена при поддержке гранта РФФИ (проект ).

Спасибо за внимание! Цой Ю.Р. Вычислительные регуляторные сети