Алгоритмы *

Часть вторая

В части первой этой статьи я рассказал, почему для игры M.E.R.C. мы выбрали процедурную генерацию уровней, и описал требования к ней. Также я описал процесс генерирования структуры процедурного уровня и соединения множества фрагментов для создания целостного уровня. Во второй части статьи мы обсудим решение проблем освещения и NavMesh в Unity и создание NPC на основании темпа.

Добро пожаловать во вторую часть руководства по нейронным сетям. Сразу хочу принести извинения всем кто ждал вторую часть намного раньше. По определенным причинам мне пришлось отложить ее написание. На самом деле я не ожидал, что у первой статьи будет такой спрос и что так много людей заинтересует данная тема. Взяв во внимание ваши комментарии, я постараюсь предоставить вам как можно больше информации и в то же время сохранить максимально понятный способ ее изложения. В данной статье, я буду рассказывать о способах обучения/тренировки нейросетей (в частности метод обратного распространения) и если вы, по каким-либо причинам, еще не прочитали первую часть, настоятельно рекомендую начать с нее. В процессе написания этой статьи, я хотел также рассказать о других видах нейросетей и методах тренировки, однако, начав писать про них, я понял что это пойдет вразрез с моим методом изложения. Я понимаю, что вам не терпится получить как можно больше информации, однако эти темы очень обширны и требуют детального анализа, а моей основной задачей является не написать очередную статью с поверхностным объяснением, а донести до вас каждый аспект затронутой темы и сделать статью максимально легкой в освоении. Спешу расстроить любителей “покодить”, так как я все еще не буду прибегать к использованию языка программирования и буду объяснять все “на пальцах”. Достаточно вступления, давайте теперь продолжим изучение нейросетей.

Brainfuck — язык программирования, созданный с одной целью: написать для него интерпретатор. Их было написано так много, что даже не буду давать на них ссылки. В этой статье на пальцах объясняется простой, но эффективный способ его оптимизации.

В этой статье мы поговорим о понимании языка (о лингвистических вычислениях, таких как назначение меток, синтаксический анализ и так далее) и обратим особое внимание на два API: Linguistic Analysis API и интеллектуальную службу распознавания речи (LUIS). Если вы любите английский язык так же как русский и увлекаетесь обучением искусственного интеллекта, добро пожаловать под кат.

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

Часть первая

Процедурная генерация уровней — отличный способ добавить в игру больше контента и неожиданных сценариев. Для сюжетных миссий M.E.R.C. мы хотели создать большой набор сделанных вручную уровней, но осознавали, что нашей небольшой инди-команде не хватит времени или ресурсов на изготовление контента для такой большой игры. Кроме того, мы стремились добавить случайность и повысить реиграбельность игры. Процедурная генерация уровней позволила нам создать большой, бесконечно изменчивый мир, который мы не смогли бы получить, строя отдельные уровни вручную. Использование процедурной генерации позволяет добавить больше контента и улучшить игровой процесс.

Что такое M.E.R.C.? M.E.R.C. — это тактический симулятор отряда в реальном времени с видом сверху. Игрок одновременно управляет отрядом из четырёх наёмников в антиутопическом мире Неотопии, отдаёт приказы и активирует особые умения. Каждый наёмник отряда имеет собственные особые боевые, технические и хакерские навыки, которые необходимо использовать в миссиях. Визуально M.E.R.C. напоминает стиль «Бегущего по лезвию»: тёмные дождливые трущобы и крыши города со множеством извилистых улиц и неоновым освещением. Сюжет заключается в войне могущественных корпораций за контроль над Неотопией. Отряд нанимают для выполнения различных заданий корпораций, таких как похищение учёных конкурентов или убийство сотрудников-перебежчиков. Каждая полученная миссия влияет на отношения с разными корпорациями и в результате изменяет игровой мир. Учитывая всё это, давайте рассмотрим требования к процедурной генерации уровней.

Введение

Расчетные сетки широко применяются при решении численных задач с помощью методов конечных разностей. Качество построения такой сетки в значительной степени определяет успех в решении, поэтому иногда сетки достигают огромных размеров. В этом случае на помощь приходят многопроцессорные системы, ведь они позволяют решить сразу 2 задачи:

1. Повысить скорость работы программы.
2. Работать с сетками такого размера, который не помещается в оперативной памяти одного процессора.

При таком подходе сетка, покрывающая расчетную область, разбивается на множество доменов, каждый из которых обрабатывается отдельным процессором. Основная проблема здесь заключается в «честности» разбиения: нужно выбрать такую декомпозицию, при которой вычислительная нагрузка распределена равномерно между процессорами, а накладные расходы, вызванные дублированием вычислений и необходимостью передачи данных между процессорами, малы.

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

В этой статье я хочу рассказать о нашем собственном симуляторе, созданном для моделирования физики поездов в Assassin's Creed Syndicate. Действие игры происходит в Лондоне 1868 года, в период промышленной революции, когда развитие общества зависело от пара и стали. Для меня было огромным удовольствием поработать над уникальной возможностью реализации мира Лондона викторианской эпохи. Внимание к историческим и реальным деталям привело нас к созданию этой физической симуляции.

Введение

Сегодня писать свои физические движки не очень популярно. Однако бывают ситуации, в которых создание собственного физического симулятора с нуля чрезвычайно полезно. Такие ситуации могут возникать, когда есть особая необходимость в новой геймплейной функции или части симулируемого игрового мира. Именно такая проблема возникла у нас при разработке системы железных дорог и управления поездами в Лондоне 19-го столетия.

Стандартная система соединения европейских поездов приведена на Рис. 1 слева. Такая же система использовалась в поездах 19-го века в Лондоне [1]. Когда мы начали работу над поездами, то быстро осознали, что можно создать интересные взаимодействия и зависимости, симулируя стяжку физически. Поэтому вместо жёсткого скрепления вагонов мы соединили их подвижным сцепным устройством, управляющим движением всех вагонов поезда.


Рис. 1. Слева — детали винтовой стяжки (источник: Википедия [1]). Справа — соединительная система в Assassin’s Creed Syndicate.

Есть две булевы функции аргументов, одна — константная, другая — сбалансированная. На какую сам сядешь, на какую фронтендера посадишь? Вот только функции неизвестны, а вызвать их разрешается лишь один раз.

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

Предисловие

→ Первая часть

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

В этой части мы поговорим о том, что же такое случайная и псевдослучайная генерации, какие алгоритмы могут дать нам равновероятно ничем не похожие друг на друга лабиринты и в чем их минусы. Героями нашего сегодняшнего приключения станут алгоритм Уилсона и алгоритм Олдоса-Бродера для создания случайного остовного дерева (Uniform Spanning Tree). ОСТОРОЖНО ТРАФИК.

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

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

Ситуация несколько усложняется, когда понятия имеют природу множеств (рисунок ниже). Тогда возможны формулировки типа: «понятие C содержит понятия A и B», «понятия A и B различны», «понятия A и B имеют нечто общее». Если положить, что близость определяется в интервале от 0 до 1, то про рисунок слева можно сказать: «близость A и C равна 1, близость B и C равна 1, близость A и B равна 0).

Часть первая — Affinity Propagation
Часть вторая — DBSCAN
Часть третья — кластеризация временных рядов
Часть четвёртая — Self-Organizing Maps (SOM)
Часть пятая — Growing Neural Gas (GNG)

Если вы спросите начинающего аналитика данных, какие он знает методы классификации, вам наверняка перечислят довольно приличный список: статистика, деревья, SVM, нейронные сети… Но если спросить про методы кластеризации, в ответ вы скорее всего получите уверенное «k-means же!» Именно этот золотой молоток рассматривают на всех курсах машинного обучения. Часто дело даже не доходит до его модификаций (k-medians) или связно-графовых методов.

Не то чтобы k-means так уж плох, но его результат почти всегда дёшев и сердит. Есть более совершенные способы кластеризации, но не все знают, какой когда следует применять, и очень немногие понимают, как они работают. Я бы хотел приоткрыть завесу тайны над некоторыми алгоритмами. Начнём с Affinity propagation.

В продолжение статьи «Сравнение технологических подходов к решению задач по извлечению данных» рассмотрим технологии, наиболее часто упоминающиеся в связи с понятием «искусственный интеллект» в контексте поисковых задач. На habrahabr.ru опубликовано множество статей на эту тему, например, об использовании нейросетей в поиске Яндкса, в которой говорится что «Фактически, формулу ранжирования пишет машина (получалось около 300 мегабайт)», о глубоком обучении, о вероятностном программировании и т.д.

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

В качестве основы для наших рассуждений мы можем выбрать любую из приведенных ниже технологий. Ввиду того, что наиболее часто упоминается нейронные сети, их и возьмем. Набрав что-то про нейросети в поисковой строке, мы получим огромную массу статей о «невообразимых» успехах, достигнутых нейронными сетями. Это и сообщения о новых аппаратных решениях, например, и спиновые электронные устройства, и заявления IBM, о том что нейронные сети по анализу слов смогут выявлять психические болезни, и «супергеройское» зрение, и множество других чудес науки. Поэтому, попробуем сделать краткий обзор текущего положения дел.

15 февраля стартует Machine Learning Boot Camp III — третье состязание по машинному обучению и анализу данных от Mail.Ru Group. Сегодня рассказываем о прошедшем контесте и открываем тайны нового! Итак, в ходе предстоящего конкурса нужно будет угадать, останется ли участник в онлайн-игре или уйдет из нее. Выборки для задачи построены на двенадцати игровых признаках для 25000 пользователей. Естественно, все данные анонимизированы.

А что если пришельцы действительно захотят посетить Землю? Будут ли мировые лидеры способствовать изучению их языка? Когда Дени Вильнёв начал работать над научно-фантастическим фильмом “Прибытие”, ему и его команде пришлось обратиться к настоящим ученым Стивену и Кристоферу Вольфрамам, дабы представить подлинную науку на большом экране. Кристоферу была поставлена задача анализа и написания кода для вымышленного нелинейного, визуального языка.

В своей первой статье на Хабре, я рассказал о своем алгоритме для поиска похожих изображений. Сегодня я хочу рассказать о второй (улучшенной) версии своего алгоритма.

Статья будет несколько короче предыдущей т.к. расскажу только об отличиях двух алгоритмов. Поэтому желательно прочесть предыдущею статью, что бы «быть в теме».

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

Общая идея такова. Если у нас есть построенное дерево игры, то для подсчета числа чистых стратегий в «наших» узлах мы складываем результаты по поддеревьям Fold, Call, Bet/Raise, а в узлах противников умножаем. Если нужно подсчитать число стратегий для другого игрока, можно использовать то же самое дерево, изменится только операция (сложение/умножение) в каждом узле.
Конечно, если задача — только посчитать число стратегий, можно обойтись и без прямого построения дерева (как это и сделано в приведенном коде).

Рассматривается Fixed Limit Texas Hold'em, где ставки повышаются не более 4 раз. Вычисления ведем только для префлопа!

Код и результаты — под катом.

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

Взаимодействие с окружающим миром приводит к накоплению опыта. Если в этом опыте есть какие-либо закономерности, то они могут быть выделены и впоследствии использованы. Наличие закономерностей можно интерпретировать, как присутствие чего-то общего в воспоминаниях, составляющих опыт. Соответственно, выделение таких общих сущностей принято называть обобщением.

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

Я размышлял, в основном с точки зрения преподавателя, о том, как научить отлаживать модели машинного обучения. Лично мне кажется полезным рассмотреть модель с точки зрения ошибок разного рода: байесовская ошибка (насколько ошибочен лучший из возможных классификаторов), ошибка аппроксимации (что мы потеряем из-за ограничения класса гипотезы), ошибка оценки (связанная с ограниченной длиной выборки), ошибка оптимизации (что случится, если не найти глобальный оптимум для задачи оптимизации). Я понял, что полезно попытаться отнести ошибку к определенной области, а потом устранять недостатки в этой конкретной области.

Здравствуйте, уважаемые читатели. Мы вновь попробуем посоветоваться с вами по поводу актуальности орейлевской новинки. На сей раз речь пойдет о статистике для Data Science.

Объем оригинала — 250 стр., дата выхода — 25 февраля.


В книге рассмотрены лаконичные кейсы с небольшим количеством графиков и примеров на языке R.

Чтобы размышлять и голосовать было интереснее — под катом найдете статью, автор которой попытался уловить и описать разницу между статистикой и Data Science