Базовые алгоритмы. Реализация на Python и С++ на примере классических игр

От издательства....11

Часть I. ВВЕДЕНИЕ В ОБУЧЕНИЕ НА ГРАФАХ....12

Глава 1. Начало работы с обучением на графах....13

Почему именно графы?....13

Зачем использовать обучение на графах?....15

Зачем использовать графовые нейронные сети?....18

Выводы....21

Дополнительное чтение....21

Глава 2. Теория графов для графовых нейронных сетей....22

Технические требования....23

Знакомство со свойствами графа....23

Ориентированные графы (directed graphs)....23

Взвешенные графы (weighted graphs)....25

Связные графы (connected graphs)....26

Типы графов....28

Знакомство с основными понятиями теории графов....29

Фундаментальные объекты....30

Меры центральности для графов....31

Представление графа в виде матрицы смежности....33

Изучение графовых алгоритмов....35

Поиск в ширину (breadth-first search)....36

Поиск в глубину (depth-first search)....38

Выводы....39

Часть II. ОСНОВЫ....41

Глава 3. Создание представлений узлов с помощью DeepWalk....42

Технические требования....43

Знакомство с Word2Vec....43

CBOW против skip-gram....44

Создание скип-грамм....45

Модель skip-gram....47

DeepWalk и случайные блуждания....51

Реализация DeepWalk....54

Выводы....59

Дополнительное чтение....59

Глава 4. Улучшение эмбеддингов с помощью смещенных случайных блужданий в Node2Vec....60

Технические требования....61

Знакомство с Node2Vec....61

Определение окрестности....61

Внесение смещений в случайные блуждания....62

Реализация Node2Vec....67

Создание рекомендательной системы фильмов....72

Выводы....77

Дополнительное чтение....78

Глава 5. Включение информации о характеристиках узлов с помощью простых нейронных сетей....79

Технические требования....80

Знакомство с графовыми наборами данных....80

Набор данных Cora....80

Набор данных Facebook Page-Page....83

Классификация узлов с помощью простых нейронных сетей....85

Классификация узлов с помощью простых графовых нейронных сетей....90

Выводы....96

Дополнительное чтение....96

Глава 6. Знакомство с графовыми сверточными нейронными сетями....97

Технические требования....98

Создание сверточного слоя графа....98

Сравнение сверточных и линейных слоев графа....102

Прогнозирование веб-трафика с помощью регрессии узлов....108

Выводы....115

Дополнительное чтение....116

Глава 7. Графовые нейронные сети с механизмом внимания....117

Технические требования....118

Знакомство со слоем внимания графа....118

Линейное преобразование....119

Функция активации....119

Нормализация с по­мощью softmax....120

Многоголовое внимание....120

Улучшенный слой внимания графа....121

Реализация слоя внимания графа в NumPy....122

Реализация GAT в PyTorch Geometric....126

Выводы....133

Часть III. ПРОДВИНУТЫЕ МЕТОДЫ....134

Глава 8. Масштабирование графовых нейронных сетей с помощью GraphSAGE....135

Технические требования....136

Знакомство с GraphSAGE....136

Семплирование соседей....136

Агрегация....139

Классификация узлов на примере набора данных PubMed....140

Индуктивное обучение на белок-белковых взаимодействиях....147

Выводы....154

Дополнительное чтение....154

Глава 9. Определение выразительности для классификации графов....155

Технические требования....156

Определение выразительности....156

Знакомство с графовой сетью изоморфизма....158

Классификация графов с помощью графовой сети изоморфизма....160

Классификация графов....160

Реализация графовой сети изоморфизма (GIN)....161

Выводы....172

Дополнительное чтение....173

Глава 10. Прогнозирование связей с помощью графовых нейронных сетей....174

Технические требования....175

Прогнозирование связей с помощью традиционных методов....175

Эвристические методы....175

Матричная факторизация....177

Прогнозирование связей с помощью эмбеддингов узлов....179

Знакомство с графовыми автоэнкодерами....179

Знакомство с вариационными графовыми автоэнкодерами....180

Реализация VGAE....181

Прогнозирование связей с помощью SEAL....185

Знакомство с фреймворком SEAL....185

Реализация фреймворка SEAL....187

Выводы....193

Дополнительное чтение....193

Глава 11. Генерация графов с помощью графовых нейронных сетей....195

Технические требования....196

Генерация графов с помощью традиционных методов....196

Модель Эрдеша–Реньи....196

Модель «малого мира»....199

Генерация графов с помощью графовых нейронных сейтей....200

Вариационные графовые автоэнкодеры....201

Авторегрессионные модели....203

Генеративные состязательные сети (GAN)....204

Генерация молекул с помощью MolGAN....206

Выводы....211

Дополнительное чтение....211

Глава 12. Обучение на гетерогенных графах....213

Технические требования....214

Нейронная сеть передачи сообщений....214

Знакомство с гетерогенными графами....216

Преобразование гомогенных GNN в гетерогенные GNN....220

Реализация иерархической нейронной сети с самовниманием....227

Выводы....230

Дополнительное чтение....231

Глава 13. Темпоральные графовые нейронные сети....232

Технические требования....233

Знакомство с динамическими графами....233

Прогнозирование веб-трафика....234

Знакомство с EvolveGCN....234

Реализация EvolveGCN....237

Прогнозирование случаев COVID-19....244

Знакомство с MPNN-LSTM....245

Реализация MPNN-LSTM....246

Выводы....251

Дополнительное чтение....252

Глава 14. Интерпретация графовых нейронных сетей....253

Технические требования....254

Знакомство с методами интерпретации....254

Интерпретация графовых нейронных сетей с помощью GNNExplainer....255

Знакомство с GNNExplainer....255

Реализация GNNExplainer....257

Интерпретация графовых нейронных сетей с помощью Captum....262

Знакомство с Captum и методом интегрированных градиентов....262

Реализация метода интегрированных градиентов....263

Выводы....268

Дополнительное чтение....268

Часть IV. ЗАДАЧИ....270

Глава 15. Прогнозирование трафика с помощью A3T-GCN....271

Технические требования....272

Исследование набора данных PeMS-M....272

Обработка набора данных....277

Реализация архитектуры A3T-GCN....282

Выводы....287

Дополнительное чтение....288

Глава 16. Построение рекомендательной системы с помощью LightGCN....289

Технические требования....290

Исследование набора данных Book-Crossing....290

Предварительная обработка набора данных Book-Crossing....296

Реализация архитектуры LightGCN....300

Выводы....312

Дополнительное чтение....312

Глава 17. Обнаружение аномалий с по­мощью гетерогенных графовых нейронных сетей....314

Технические требования....315

Исследование набора данных CIDDS-001....315

Предварительная обработка набора данных CIDDS-001....320

Реализация гетерогенной GNN....328

Выводы....334

Дополнительное чтение....335

Глава 18. Раскрытие потенциала графовых нейронных сетей в реальных задачах....336

Предметный указатель....338

В книге дается базовая алгоритмическая подготовка, классические алгоритмы разобраны одновременно на двух языках — C++ и Python на примере широко известных и интуитивно понятных компьютерных игр. Наглядно излагается реализация циклов, перебора, рекурсии, эвристики, рассматривается работа с деревьями решений, на примере шахмат предлагается знакомство с прямоугольными координатами, дается введение в самообучающиеся алгоритмы. Книга ориентирована как на начинающих программистов, так и на читателей, планирующих перейти на C++ или Python как на второй язык. Примеры, рассмотренные в книге, помогут сделать первые шаги на пути к профессиональному программированию игр.

Для программистов

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

В настоящее время алгоритмы в университетском курсе преподаются в основном на двух языках программирования — C++ и Python. Фундаментальные книги по алгоритмам найдутся в библиотеке любого серьезного программиста, однако не так много найдется простых алгоритмических книг, дающих базовое представление о джентльменском наборе алгоритмов и позволяющих сразу перейти к их реализации. Именно эту нишу и заполняет предлагаемая книга.

Вы изучите:

• генерацию случайных чисел на примере броска игральной кости,
• работу с прямоугольными координатами на примере игры «Ферзя в угол»,
• эвристический выбор на примере игры «Морской бой»,
• рекурсивный перебор на примере игры «Калах»,
• деревья решений на примере игры «Угадай животное»
• и другое

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