Гужва А.Г. Нейронные сети. Многоагентные системы. Оптимизационные задачи.

План Нейронные сети: теория Нейронные сети: практика Многоагентные системы Пример

План Нейронные сети: теория – Нейрон (нервная клетка) – Искусственный нейрон – Многослойный персептрон – Задача нелинейной регрессии Нейронные сети: практика Многоагентные системы Пример

Нейрон (нервная клетка) Состоит из: – Сомы – Аксона – Дендритов Мозг человека: – ~10 10 нейронов – ~10 13 связей Время реакции нейрона ~ с.

Объединение нейронов Нейроны (100 мкм) Локальные контуры Отделы ЦНС

Искусственный нейрон Σ Y X1X1 XNXN … w1w1 wNwN 1 w0w0 Нейрон преобразует входные сигналы: Y = (1 * w 0 + X 1 * w 1 + … + X N * w N ) ( )

Математическая модель нейрона (формализм) Σ … Y = f(X) (X W) Входной вектор – X = {1, X 1, …, X N } Веса нейрона – W = {w 0, w 1, …, w N } Передаточная функция ( ) – Скалярная – Дифференцируемая, ограниченная – Монотонно возрастающая X W Y

Примеры передаточных функций

Архитектура нейронных сетей. Многослойные персептроны Входной сигнал Выходной сигнал Входной слой нейронов Скрытые слои нейронов Выходной слой нейронов

Многослойные персептроны (примеры архитектур) Однослойные Многослойные Рекуррентные С обходными связями Автоассоциативная память

Многослойные персептроны (формализм) Семейство параметрических вектор-функций МСП с 1 скрытым слоем (f: R M R P ) – ( ) С 1 – ограниченная монотонно возрастающая действительная функция – и u – матрицы весов (N x (M + 1) и P x (N + 1)) – k = 1..P – N – характеризует сложность конструкции

Задача нелинейной регрессии Дано: Задан конечный обучающий набор векторов X = {x 1 …x n }, x i R M, i = 1..n Имеется зависимость y = y*(x), y*: R M R P, для которой известны y i = y*(x i ) для x i X Задано разбиение X на тренировочный набор данных X Trn и тестовый набор данных X Tst Задан вид семейства нелинейных параметрических функций M переменных y = f(x, )

Задача нелинейной регрессии Требуется: Аппроксимация y* с помощью f(x, ) Найти решение системы уравнений по y*(x 1 ) = f(x 1, ) … y*(x m ) = f(x m, ) при котором достигался бы минимум функционала ошибки: E(, X Tst ) = x X Tst (y*(x) - f(x, )) 2, x i X Trn

Задача нелинейной регрессии Многослойные персептроны Универсальный аппроксиматор – МСП с 1 скрытым слоем достаточно, для равномерной аппроксимации с точностью для любого обучающего множества, представленного точками и желаемыми откликами Чувствительность к размерности данных

Традиционный способ решения задачи нелинейной регрессии для многослойных персептронов (обучение сети) Оптимизационная задача по подбору элементов матриц весов Решение методом наименьших квадратов путем минимизации функционала ошибки: E(, X Trn ) = x X Trn (y*(x) - f(x, )) 2 min E(, X Tst ) используется для контроля останова процесса обучения нейронной сети

Задача нелинейной регрессии Входной сигнал Выходной сигнал Подстроить параметры МСП так, чтобы в ответ на определенные входные сигналы на выходе были бы определенные выходные сигналы

План Нейронные сети: теория Нейронные сети: практика – Решаемые классы задач – Задача восстановления распределения электропроводности Многоагентные системы Пример

Решаемые классы задач Классификация Кластеризация Регрессия \ Прогнозирование Data-driven methods – Все необходимые законы, описывающие поведение объекта, содержатся в данных – «Мусор» на входе -> мусор на выходе

Классификация и распознавание образов. Отнесение объекта к одному из заданных классов на основании его характеристик Примеры: – Диагнозы в медицине – Распознавание речи – Распознавание лиц – Детектирование взрывчатых веществ – Выдача кредитов Да

Классификация и распознавание образов. Объект может быть отнесен к нескольким классам в разной степени «Не знаю»

Кластеризация (Карты Кохонена) Разбиение объектов на группы (кластеры) по принципу схожести их характеристик Человек: «8 групп точек» Машина: «500 точек»

Кластеризация (Карты Кохонена) Иерархическая кластеризация Пример: – Перепись населения

Задачи прогнозирования. Задачи регрессии Предсказание космической погоды База наблюдений за Солнцем 1.5 млн. км (ACE) Параметры межпланетного магнитного поля Скорость солнечного ветра Другие параметры

Методы исследования земной коры Обратная задача: восстановление реальных характеристик пород по наблюдаемым полям

Задача Магнитотеллурического зондирования (МТЗ) Прямая задача МТЗ ( -> ): A k =, Г к R Nk, R Mk A k – заданный дискретный оператор прямой задачи = ( 1 … Mk ) – вектор характеристик МТ поля, измеренных на поверхности Земли = ( 1 … Nk ) – вектор макропараметров среды Г k – область допустимых значений k – класс разрезов

Задача Магнитотеллурического зондирования (МТЗ) Обратная задача МТЗ ( -> ): = A k -1, Г к R Nk, R Mk Система нелинейных уравнений относительно Неустойчива и некорректна – Вид уравнений – Размерность данных Чудовищная размерность данных

Задача Магнитотеллурического зондирования (МТЗ) Решаем прямую задачу для разных геоэлектрических разрезов – Задаем 1, считаем 1 =A k 1, знаем ( 1, 1 ) – … – Задаем N, считаем N =A k N, знаем ( N, N ) Обучаем нейронную сеть ( обратная задача): – Подаем на вход 1, требуем на выходе 1 – … – Подаем на вход N, требуем на выходе N

Задача Магнитотеллурического зондирования (МТЗ), 2D 336 блоков ( ) Электропроводность <

Задача МТЗ. Пример распределения

Задача МТЗ. 1 большая обратная задача МТЗ – Размерность входного вектора 6552 – Размерность выходного вектора небольших задач нелинейной регрессии – Размерность входного вектора 1648 – Размерность выходного вектора 1

Задача МТЗ. Формально. 4 комплекта по 1680 наборов данных – Обучающий набор примеров (x i, y i ) – Размерность вектора входных данных – Размерность вектора желаемых откликов - 1 – Решение задачи нелинейной регрессии – Минимизация функционала ошибки вида W = {u, v} – условное обозначение матрицы весов многослойного персептрона y(x, u, v)

Поиск минимума функции. Градиентный спуск. 1.E=E(W)=E(w 1 …w N ) – функция ошибки 2.W=W 0 3.Считаем градиент функции в точке W grad E(W)=( E/ w 1, …, E/ w N ) 4.W=W - *grad E(W), где ~10 -1 – goto 2 Проблема: последовательный процесс, который попадает в локальные минимумы

Градиентный спуск Локальные минимумы Попадание в локальные минимумы – В точке локального экстремума grad E = 0 – При приближении к локальному экстремуму |grad E| падает

Градиентный спуск Задача регрессии – Обучающий набор данных (x i, y i ), i=1..N – Аппроксимирующая функция y(x,W), где W={u,v} – Функция ошибки E(W) = i=1,N (y(x i,W) - y i ) 2 grad E(W) = 2 * i=1,N (y(x i,W)-y i ) * y/ W(x i ) Проблема: локальные минимумы Параллельно N = Параллельно Размерность w ~ 10 4

Проблема попадания в локальные минимумы grad E(W) = 2 * i=1,N (y(x i,W)-y i ) * y/ W(x i ) – Проблема локальных минимумов Сделать N/10 итераций (т.е. 3000) – Случайно выбрать rnd из 1..N-10 – grad E(W) = 2 * i=rnd,rnd+9 (y(x i,W)-y i ) * y/ W(x i ) – W=W - *grad E(W)

Эффективная реализация Распараллеливание градиентного спуска (группы по 10 точек) Градиентный спуск для большого числа функций (1680) Раскрытие циклов Использование CUBLAS для вычисления значений функции (cublasSgemm)

Результаты Железо: AMD Athlon 64 x2 Dual GHz Основное ограничение: bandwidth внутренней шины данных GPU

Другие работы с использованием CUDA 1.Правильная постановка задачи – «Мусор» на входе -> «мусор» на выходе 2.Как расположить данные в памяти 3.Правильный подбор весов нейронной сети (градиентный спуск) 4.… 5.PROFIT

План Нейронные сети: теория Нейронные сети: практика Многоагентные системы – Задача оптимизации – Многоагентные системы – Генетическое программирование Пример

Задача оптимизации Общая постановка задачи: – Найти min F(X), X R N, X U, где U – множество допустимых значений Сложности: – Большая размерность X – «Нехорошая» F(X) – Комбинаторные задачи кратчайший путь

Задача оптимизации Локально-оценочные методы – Метод вилки – Adaptive Simulated Annealing Градиентные методы – Градиентный спуск Переборные методы – Полный перебор – Монте-Карло Многоагентные системы – Генетические алгоритмы

Многоагентные системы Исследование множества допустимых решений с помощью пробных точек Итерационный процесс. Для каждой пробной точки X: – Оценить значение f(X) – Чем меньше значение, тем в большей мере остальные пробные точки на следующей итерации приблизятся к данной

Многоагентные системы Не менее 100 пробных точек Несколько комплектов точек Целевая функция F может меняться в процессе поиска решения Невысокая точность решения – Использование градиентного спуска

Многоагентные системы Генетические алгоритмы (GA) John Holland (1975) – Биологическая эволюция – Генетическое программирование Ant Colony Optimization (ACO) Marco Dorigo (1992) – Колония муравьев Particle Swarm Optimization (PSO) J. Kennedy, R. Eberhart (1995) – Стаи птиц, косяки рыб

Многоагентные системы и CUDA Многократное вычисление значений целевой функции F Большое число многоагентных систем

Генетическое программирование (ГП) John Koza (1992) Множество допустимых решений U – Множество всевозможных программ, составленных из заданного набора операций и переменных (операндов) Целевая функция F(X), где X U – То, насколько пригодна та или иная программа X для решения некоторой задачи – Чем F(X) меньше, тем лучше

Искусственный муравей Карта NxN клеток, в некоторых клетках - еда Муравей может – Повернуться налево – Повернуться направо – Пойти вперед – Съесть еду на клетке – IF_FOOD_AHEAD Задача: построить алгоритм действий муравья

ГП. Представление программы в виде дерева Возможные операции: – «Выполнить» дерево – Перегенерировать поддерево – Поменять операнд \ оператор – Обменяться поддеревьями + 1IF > TIME * (time > 10) ? 3 : 4 (2 + 3) * 4

ГП. Эволюция 1.Сгенерировать N случайных программ {X} 2.Для каждой программы X {X} вычислить F(X) 3.Сгенерировать новый набор программ {Y} 1.(9%) Либо выбрать программу из {X}, случайно перегенерировать ее поддерево, добавить в {Y} 2.(90%) Либо выбрать две программы из {X}, обменяться случайно выбранными поддеревьями, добавить в {Y} 3.(1%) Либо добавить случайно сгенерированную программу в {Y} 4.{X} = {Y} 5.goto 2 *

ГП. Выбор программ. Вероятность выбора программы X в качестве «родителя» тем выше, чем ниже F(X) Повышение вероятности «размножения» «хороших» программ Аналог мутаций (п. 3.1) Аналог полового скрещивания (п. 3.2) «Родила царица в ночь…» (п. 3.3)

Задача нелинейной регрессии Решение задачи нелинейной регрессии – Обучающий набор: N пар (x i, y i ) – Заданы операторы +, -, *, /, sin, cos, exp, … – Построить аналитическую аппроксимирующую функцию y(x), используя заданные операторы, x и случайные числа Целевая функция F(y) – F(y) = i=1,N (y(x i ) - y i ) 2 y=sin(arccos(exp(x))) ?

ГП. CUDA. Представление программы в виде RPN Инфиксная нотация – 4 * (2 + 3) Обратная польская нотация (RPN) – * Стековая машина – Если на вход подан операнд – положить в стек – Если на вход подана операция – вытащить ряд значений из стека, посчитать, результат операции положить в стек *

Стековая машина Исходное выражение: * *push *push *pop 3, pop 2 2+3=5, push *push *pop 4, pop 5 4*5=20, push 2020 Конец. Ответ – 20 Символ Что делаем? Стек:

CUDA. Псевдокод kernel-а стековой машины float stack[8];// 8 bytes for stack sp = 0; // initialize stack pointer GP_pc = baseAddress[i] ; // load base address of prog i while (instructionArray[GP_pc] != RETURN) { switch (instructionArray[GP_pc]) { case OPERAND: stack[sp++] = data; break;// push data on stack case ADD: stack[sp-2] = stack[sp-1] + stack[sp-2]; sp--; break; case MUL: stack[sp-2] = stack[sp-1] * stack[sp-2]; sp--; break;... } GP_pc++; } Robilliard, D., Marion-Poty, V., Fonplut, C. Genetic programming on graphics processing units. // Genet Program Evolvable Mach (2009), 10:

А что с SIMD? Нити находящиеся на одном SM должны выполнять одну программу X, но для разных входных точек (x i, y i ) Нити разных SM выполняют разные программы X

ГП и CUDA 1.Сгенерировать начальный набор программ 2.Перевести программы в RPN 3.Для каждой оценить целевую функцию Выполняется на CUDA 4.Сгенерировать новый набор программ на основе оценок целевой функции 5.Goto 2

План Нейронные сети: теория Нейронные сети: практика Многоагентные системы Пример

Аппроксимация растровой картинки Подсмотрено у Roger Alsing (2008) – Задача – Аппроксимировать изображение набором полупрозрачных многоугольников

Аппроксимация растровой картинки К. Малевич «Черный супрематический квадрат»

Аппроксимация растровой картинки Да Винчи «Мона Лиза» ?

Задача оптимизации Найти min F(X), X R N, X U, где U – множество допустимых значений Множество допустимых решений U: – Наборы полупрозрачных многоугольников, лежащих в прямоугольнике (0, 0) – (w, h) Целевая функция F(X): – Сумма квадратов разностей R, G и B исходной картинки и предлагаемого решения, суммируем по всем пикселям F(X) Насколько похоже

Как это работает? (Roger Alsing) Каждую итерацию можно следующее: – Добавить многоугольник к набору – Удалить многоугольник из набора – Сдвинуть многоугольник – Сдвинуть точку многоугольника – Добавить точку в многоугольник – Удалить точку из многоугольника – Изменить цвет Проверить, стало ли лучше

Как это работает? Исходная картинка

Примеры работы 250 многоугольников В среднем 9 точек на многоугольник

Примеры работы

CUDA Растеризация многоугольника Растеризация нескольких многоугольников

CUDA «Распилить» картинку на части – 24 части – 150х150 пикселей

CUDA Использование многоагентных систем – Независимая растеризация большого числа наборов многоугольников Много уровней параллелизма Как эффективно оценить степень похожести двух растровых картинки? А нужно ли растеризовать многоугольники? – Цель – оценить степень похожести набора многоугольников на исходную картинку

Можно и так