Эволюционирующие искусственные нейронные сети Спицын В.Г., Цой Ю.Р. Кафедра вычислительной техники, Томский политехнический университет qai@mail.ru 2006. - презентация

1 Эволюционирующие искусственные нейронные сети Спицын В.Г., Цой Ю.Р. Кафедра вычислительной техники, Томский политехнический университет 2006 г.

2 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Содержание 1. Введение 2. Искусственные нейронные сети (ИНС) 3. Эволюционные вычисления (ЭВ) 4. Нейроэволюционный (НЭ) подход 5. Задачи с качественной оценкой ИНС 6. Пример применения НЭ для обработки изображений 7. Перспективы НЭ подхода 8. Конференции и журналы 9. Интернет-ресурсы

3 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Введение Примеры: 1. Управление и принятие решений. По имеющимся данным (X) необходимо выбрать одно из возможных действий (Y). 2. Классификация и распознавание. Зная входные признаки (X) объекта нужно определить принадлежность этого объекта к одному из известных классов (Y). 3. Аппроксимация и моделирование. Необходимо определить с заданной погрешностью значение выходного сигнала (Y) по имеющимся входным сигналам (X). Многие задачи можно в общем виде рассматривать как задачи построения отображения: X Y, где X и Y – соответственно пространства входных и выходных параметров.

4 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Искусственные нейронные сети (ИНС) (1/2) Формальный нейрон: x0x0 x1x1 xnxn... Сумматор Преобра- зователь w0w0 w1w1 w2w2 – функция активации нейрона Примеры функций активации:

5 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Искусственные нейронные сети (ИНС) (2/2) Пример многослойной ИНС: Выходной сигнал (в векторной форме): Основные параметры ИНС: - Структура. - Веса связей. ИНС может аппроксимировать любую непрерывную функцию, если функции активации будут нелинейными (Колмогоров, 1956, 1957; Арнольд, 1957; Горбань, 1998).

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

7 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Эволюционные вычисления (2/2) Основное преимущество ЭВ: Представляют универсальный проблемно-независимый подход к поиску оптимальных и субоптимальных решений. Основные разновидности ЭВ: 1. Генетический алгоритм. 2. Эволюционное программирование. 3. Эволюционные стратегии. 4. Генетическое программирование. Сложность настроенного эволюционного алгоритма часто имеет порядок O(NlnN) - O(N 2 lnN).

8 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Нейроэволюционный подход (1/6) Нейроэволюционный подход = Эволюционные вычисления + Искусственные нейронные сети Некоторые задачи: - настройка весов связей ИНС; - настройка структуры ИНС; - одновременная настройка структуры и весов связей ИНС; - настройка параметров алгоритма обучения ИНС; - фильтрация данных для обучения ИНС.

9 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Нейроэволюционный подход (2/6) Настройка весов связей ИНС Плюсы: + независимость от структуры и параметров ИНС; + отсутствие необходимости в обучающей выборке. Минусы: - трудность «тонкой» настройки весов; - требования к объему памяти; - проблема конкурирующих решений. Хромосома ……

10 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Нейроэволюционный подход (3/6) Проблема конкурирующих решений (competing conventions problem, Whitley et al., 1990) Также известна как проблема перестановок (permutations problem, Saravanan, Fogel, 1995). Считается, что случайная рекомбинация идентичных ИНС приведет к разрушению имеющихся «хороших» НС.

11 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Нейроэволюционный подход (4/6) Настройка структуры ИНС Хромосома Структура ИНС Плюсы: + возможность автоматического поиска топологии ИНС; + независимость от характеристик функции активации нейронов. Минусы: - сложность оценки структуры ИНС; - сложность организации поиска топологии ИНС.

12 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Нейроэволюционный подход (5/6) Настройка структуры ИНС (продолжение) Способы кодирования информации о структуре ИНС: 1. Прямое кодирование (direct encoding). Пример: список связей, матрица смежности и др. 2. Косвенное кодирование (indirect encoding) Кодирование параметров (например, количество слоев и нейронов) Использование специализированных грамматик Эволюция грамматических правил Эволюция последовательности использования правил.

13 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Нейроэволюционный подход (6/6) Одновременная настройка весов и структуры ИНС Хромосома* …… Плюсы: + независимость от структуры и параметров ИНС; + отсутствие необходимости в обучающей выборке; + возможность автоматического поиска топологии ИНС. Минусы: - трудность «тонкой» настройки весов; - требования к объему памяти. - сложность организации поиска топологии ИНС. структура * Хромосома представлена схематично

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

15 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Задачи с качественной оценкой ИНС (2/4) Предлагается использование приближенной, интегральной оценки ИНС, отражающей внешние, качественные аспекты ее функционирования. Будем называть оценку ИНС качественной неполной оценкой или, коротко, качественной оценкой, если эта оценка позволяет с требуемой точностью оценить качество функционирования ИНС, но при этом ее значения недостаточно для подстройки весов связей ИНС с использованием градиентных алгоритмов. Примеры качественной оценки: 1. Время поддержания стабильности системы управления. 2. Успешность действий интеллектуального агента. 3. Качество (информативность и т.д.) обработанных данных.

16 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Пример применения НЭ для обработки изображений (1/5) Используется локально-адаптивный подход: Каждый пиксель изображения обрабатывается в соответствии с характеристиками пикселей в его окрестности. – вектор характеристик пикселя на пересечении i-й строки и j-го столбца изображения Преобразование яркости в векторном виде:

17 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Пример применения НЭ для обработки изображений (2/5) Вход ИНС (обучение): - средняя яркость в окрестности 3х3; - дисперсия в окрестности 3х3; - средняя яркость на всем изображении. ИНС Рассматривается попиксельная обработка изображений. Вход ИНС (тестирование): - яркость пикселя (x,y); - приближенная дисперсия локальной яркости; - приближенное среднее локальной яркости. Оценка ИНС: средняя оценка качества обработанных изображений.

18 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Пример применения НЭ для обработки изображений (3/5) Исходное изображение1 этап, окрестность 5х52 этап Пример: Двухэтапная обработка изображений: 1 этап. НС обработка с использованием локальных характеристик (среднее и дисперсия яркости). 2 этап. Автовыравнивание уровней.

19 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Пример применения НЭ для обработки изображений (2/5) Сравнение различных алгоритмов для 1-го этапа обработки: Исходное изображениеАвтоконтрастНС обработка Нижнее исходное изображение взято из работы Woodell G.A., Jobson D.J., Rahman Z., Hines G.D. Enhancement of imagery in poor visibility conditions // Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security and Homeland Defense IV, Proc. SPIE 5778, Далее (Woodell et al., 2005).

20 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Пример применения НЭ для обработки изображений (4/5) Сравнение с алгоритмом Multi-Scale Retinex (MSR) (Woodell et al., 2005): Двухэтапная обработка с локальными характеристиками Multi-Scale Retinex (MSR)

21 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Пример применения НЭ для обработки изображений (5/5) 12, ,033 0,211 Некоторые из обученных ИНС могут использоваться в качестве детектора края с сохранением части тоновой информации при точном вычислении локальных характеристик. Усиление границ достигается посредством настройки параметра а функции активации нейронов: Исходные изображения взяты из работы (Woodell et al., 2005). a = 5, окрестность 3х3 a = 2, окрестность 3х3

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

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

24 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Конференции и журналы (1/2) Конференции: IEEE International Joint Conference on Neural Networks (IJCNN) ( IEEE Congress on Evolutionary Computation (CEC) ( International Conference on Artificial Neural Networks (ICANN) ( Genetic and Evolutionary Computation Conference (GECCO) ( Parallel Problems Solving from Nature (PPSN) ( Нейроинформатика ( Национальная конференция по искусственному интеллекту (КИИ) (

25 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Конференции и журналы (2/2) Журналы: IEEE Transactions on Neural Networks ( IEEE Transactions on Evolutionary Computation ( Evolutionary Computation ( «Нейрокомпьютеры: разработка и применение» ( Электронный журнал «Нейроинформатика» ( «Интеллектуальные системы» (

26 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Интернет-ресурсы (1/2) IEEE Computer Intelligence Society: Special Interest Group for Genetic and Evolutionary Computation (SIGEVO): Российская ассоциация нейроинформатики: Российская ассоциация искусственного интеллекта: Neural Networks Research Group: Страница З. Яо (Xin Yao):

27 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Интернет-ресурсы (2/2) Страница В.Г. Редько: Страница С.А. Терехова: Citeseer: (БНБ) Большая Научная Библиотека: Библиотека ДВО СО РАН: Поиск книг:

28 Спасибо за внимание! По материалам статьи: Использованы карикатуры с сайта

29 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Приложение 1. Оценка качества изображений. Оценка качества обработанного изображения: – количество пикселей на краях на обработанном изображении, a и b – соответственно ширина и высота изображения в пикселях, l i – доля пикселей обработанного изображения с i-м уровнем яркости.

30 Спицын В.Г., Цой Ю.Р. Эволюционирующие искусственные нейронные сети. IV Всероссийская конференция «Молодежь и современные ИТ», Томск, 28 февраля – 2 марта, Приложение 2. Приближенное вычисление локальных характеристик изображения где - средняя яркость на всем изображении, Предполагая плавное изменение яркости на изображении, а также малый размер окрестности, можно свести вычисления локальных характеристик по всем пикселям окрестности к вычислению по произвольной строке или столбцу окрестности. Для более точных вычислений используются следующие формулы: Рассматривается прямоугольная окрестность пикселя (x,y), ограниченная точками (j 1 ; i 1 ) и (j 2 ; i 2 ), причем i 2 i 1, j 2 j 1..