Рубрика «цепи маркова»
Петь в такт машине: история караоке и устройство его аппаратов
2024-12-19 в 6:20, admin, рубрики: Алгоритмы, гауссовы смеси, караоке, цепи маркова
Цепи Маркова в Telegram-боте
2024-09-16 в 15:30, admin, рубрики: искусственный интеллект, телграмм-бот, цепи марковаРано или поздно я должен был начать писать статьи для хабра.
Привет, меня зовут Александр и я жёсткая самоучка в области искусственного интеллекта (ИИ). 5 лет назад я задался целью создать сильный искусственный интеллект (СИИ).
Думаю, стоит начать с того, как я создал бота для Телеграма с цепями Маркова.
Цепи Маркова для процедурной генерации зданий
2019-11-21 в 7:42, admin, рубрики: игровые движки, имитация отжига, процедурная генерация, разработка игр, цепи маркова
Примечание: полный исходный код этого проекта можно найти [здесь]. Так как он является частью более масштабного проекта, я рекомендую смотреть коммит на момент выпуска этой статьи, или файл /source/helpers/arraymath.h, а также /source/world/blueprint.cpp.
В этой статье я хочу подробно рассказать о принципах использования цепей Маркова и статистики для процедурной генерации 3D-зданий и других систем.
Я объясню математические основы работы системы и постараюсь сделать объяснение как можно более общим, чтобы вы могли применять эту концепцию в других ситуациях, например, для генерации 2D-подземелий. Объяснение будет сопровождаться изображениями и исходным кодом.
Этот метод является обобщённым способом процедурной генерации систем, удовлетворяющих определённым требованиям, поэтому я рекомендую дочитать хотя бы до конца первого раздела, чтобы вы могли понять, сможет ли эта методика быть полезной в вашем случае, потому что ниже я объясняю необходимые требования.
Читать полностью »
Краткое введение в цепи Маркова
2019-06-14 в 4:49, admin, рубрики: pagerank, марковское свойство, математика, Научно-популярное, поисковые системы, поисковые технологии, ранжирование поиска, стохастические процессы, цепи маркова
В 1998 году Лоуренс Пейдж, Сергей Брин, Раджив Мотвани и Терри Виноград опубликовали статью «The PageRank Citation Ranking: Bringing Order to the Web», в которой описали знаменитый теперь алгоритм PageRank, ставший фундаментом Google. Спустя чуть менее два десятка лет Google стал гигантом, и даже несмотря на то, что его алгоритм сильно эволюционировал, PageRank по-прежнему является «символом» алгоритмов ранжирования Google (хотя только немногие люди могут действительно сказать, какой вес он сегодня занимает в алгоритме).
С теоретической точки зрения интересно заметить, что одна из стандартных интерпретаций алгоритма PageRank основывается на простом, но фундаментальном понятии цепей Маркова. Из статьи мы увидим, что цепи Маркова — это мощные инструменты стохастического моделирования, которые могут быть полезны любому эксперту по аналитическим данным (data scientist). В частности, мы ответим на такие базовые вопросы: что такое цепи Маркова, какими хорошими свойствами они обладают, и что с их помощью можно делать?
Читать полностью »
Теория счастья. Закон зебры и чужой очереди
2018-08-19 в 4:08, admin, рубрики: recreational science, занимательная математика, Занимательные задачки, кривая Лоренца, математика, Научно-популярное, пуассоновский процесс, случайное блуждание, теория вероятности и мат статистика, теория счастья, цепи марковаПродолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.
Опубликованные главы:
• Введение в мерфологию
• Закон арбузной корки и нормальность ненормальности
Мы поговорим о фатуме, землетрясениях, очередях и замечательных процессах: пуассоновском потоке, случайном блуждании и немного о цепях Маркова.
Как построить защиту от фрода в масштабах корпорации. Лекция на YaC 2018
2018-06-03 в 9:06, admin, рубрики: Fraud-мониторинг, rakuten, TLS, YaC, Блог компании Яндекс, защита от ботнета, защита от ботов, информационная безопасность, капча, машинное обучение, фрод, цепи маркова29 мая прошла Yet another Conference 2018 — ежегодная и самая большая конференция Яндекса. На YaC этого года было три секции: о технологиях маркетинга, умном городе и информационной безопасности. По горячим следам мы публикуем один из ключевых докладов третьей секции — от Юрия Леонычева tracer0tong из японской компании Rakuten.
Как мы аутентифицируем? В нашем случае ничего экстраординарного нет, но один метод хочу упомянуть. Кроме традиционных видов — капчи и одноразовых паролей — мы используем Proof of Work, PoW. Нет, мы не майним биткоины на компьютерах пользователей. Мы используем PoW, чтобы замедлить атакующего и иногда даже заблокировать полностью, заставив его решить очень сложную задачу, на которую он потратит очень много времени.
Оптимальная игра в 2048 с помощью марковского процесса принятия решений
2018-04-23 в 21:05, admin, рубрики: 2048, markov chains, марковский процесс принятия решений, математика, цепи маркова
В предыдущей статье про 2048 мы использовали цепи Маркова, чтобы выяснить, что в среднем для победы нужно не менее 938,8 ходов, а также исследовали с помощью комбинаторики и полного перебора количество возможных конфигураций поля игры.
В этом посте мы используем математический аппарат под названием «марковский процесс принятия решений» для нахождения доказуемо оптимальных стратегий игры 2048 для полей размером 2x2 и 3x3, а также на доске 4x4 вплоть до тайла 64. Например, вот оптимальный игрок в игру 2x2 до тайла 32:
Случайное начальное число (random seed) определяет случайную последовательность тайлов, добавляемых игрой на поле. «Стратегия» игрока задаётся таблицей, называемой алгоритмом (policy). Она сообщает нам, в каком направлении нужно сдвигать тайлы в любой возможной конфигурации поля. В этом посте мы рассмотрим способ создания алгоритма, оптимального в том смысле, что он максимизирует шансы игрока на получение тайла 32.
Оказывается, что в игре 2x2 до тайла 32 очень сложно выиграть — даже если играть оптимально, игрок выигрывает только примерно в 8% случаев, то есть игра оказывается не особо интересной. Качественно игры 2x2 сильно отличаются от игр 4x4, но они всё равно полезны для знакомства с основными принципами.
В идеале мы хотим найти оптимальный алгоритм для полной игры на поле 4x4 до тайла 2048, но как мы убедились из предыдущего поста, количество возможных конфигураций поля очень велико. Поэтому невозможно создать оптимальный алгоритм для полной игры, по крайней мере, с помощью используемых здесь методов.
Однако мы можем найти оптимальный алгоритм для укороченной игры 4x4 до тайла 64, и, к счастью, мы увидим, что оптимальная игра на полях 3x3 качественно выглядит похожей на некоторые успешные стратегии полной игры.
Код (исследовательского качества), на котором основана эта статья, выложен в открытый доступ.
Читать полностью »
Математика игры 2048
2017-10-07 в 7:10, admin, рубрики: 2048, комбинаторика, марковский процесс принятия решений, математика, разработка игр, цепи марковаЧасть 1. Расчёт минимального количества ходов для победы с помощью цепей Маркова
После недавнего обновления экран «You win!» игры 2048 начал показывать количество ходов, потребовавшихся для победы, и я задался вопросом: сколько же нужно ходов, чтобы выиграть?
В первой части статьи мы ответим на этот вопрос, смоделировав игру 2048 в виде цепи Маркова и проанализировав её, чтобы показать, что вне зависимости от мастерства игрока для победы в среднем нужно не менее 938,8 ходов. Это даёт нам неплохое мерило отсчёта — если вы можете выигрывать примерно за такое количество ходов, то неплохо играете.
Количество ходов, необходимых для победы, зависит от случайности, потому что игра добавляет тайлы 2 и 4 случайным образом. Анализ также покажет, что распределение минимального количества ходов до победы имеет стандартное отклонение в 8,3 хода, и что его общая форма хорошо аппроксимируется смесью биномиальных распределений.
Читать полностью »
Разработка класса для работы с цепями Маркова
2016-06-01 в 13:31, admin, рубрики: c++, Алгоритмы, теория графов, цепи маркова, метки: цепи марковаСегодня я хотел бы поведать вам о написании класса для упрощения работы с цепями Маркова.
Прошу под кат.
Читать полностью »
Twitter-бот на основе цепей Маркова и фраз из сериалов
2015-02-03 в 16:40, admin, рубрики: flask, python, python3, sqlalchemy, twitter, Программирование, цепи маркова 
Просматривал форумы в поисках вопросов, которые задают python-программистам на собеседованиях и наткнулся на один очень замечательный. Вольно его процитирую: ”Попросили написать генератор бреда на основе марковской цепи n-го порядка”. “А ведь у меня ещё нет такого генератора!” — прокричал мой внутренний голос — “Скорей открывай sublime и пиши!” — продолжал он настойчиво. Что же, пришлось подчиниться.
А здесь я расскажу, как я его сделал.
Читать полностью »