Ученые решили фундаментальную математическую проблему — «задачу о двуруком бандите»
В Новгородском университете решили математическую «задачу о двуруком бандите» и внесли вклад в решение фундаментальной математической проблемы. Полученные результаты научного исследования можно применять в оптимизации пакетной обработки больших данных.
Фундаментальное исследование — это экспериментальное или теоретическое исследование, направленное на получение новых знаний. Такие исследования не преследуют цель немедленного практического применения и ориентированы на долгосрочную перспективу развития. Например, когда-то давно английский министр финансов спросил у физика Майкла Фарадея, для чего могут быть полезны его исследования по электричеству. На это ученый ответил, что однажды результаты его исследований будут обложены налогами.
Что касается задачи о двуруком бандите, то это сравнительно новая математическая проблема. Она поставлена в середине XX века независимо друг от друга американским математиком Гербертом Роббинсом и советским кибернетиком Михаилом Львовичем Цетлиным. И принадлежит к науке, которая называется reinforcement learning (в переводе с англ «подкрепляемое обучение»). Открытия в этой области сегодня напрямую относятся к исследованиям в области искусственного интеллекта.
Чем опасен «двурукий бандит»?
Суть проблемы решения «задачи о двуруком бандите» лежала в следующем.
Двурукий бандит — это игральный автомат с двумя рукоятками. Нажатие на каждую рукоятку приносит игроку единичный случайный выигрыш. Например, с некоторыми вероятностями он может выиграть один рубль при нажатии на каждую рукоятку. Обе вероятности фиксированы, различны, но неизвестны игроку.
Теперь поясним, что значит случайный выигрыш. Скажем, пусть вероятность выигрыша на первой рукоятке равна 0,7, а в игре можно нажимать рукоятки 10 раз. Если все 10 раз нажимать только первую рукоятку, то выигрыш может быть самым разным — от 0 до 10 рублей. Но если этот эксперимент повторить много раз, то выигрыш составит в среднем семь рублей за одну игру. Точно так же, если на второй рукоятке вероятность выигрыша равна 0,5, то средний выигрыш за выбор этой рукоятки 10 раз составит пять рублей за одну игру.
Целью игрока является максимизация именно этого среднего выигрыша за одну игру против автомата. При этом он может чередовать рукоятки в процессе игры. Если бы обе вероятности были известны, то оптимальной стратегией игрока было бы всегда выбирать рукоятку, которой соответствует большая вероятность единичного выигрыша. Однако, поскольку эти вероятности неизвестны, в процессе игры надо как-то сравнить обе рукоятки и обеспечить преимущественное применение лучшей.
Бандит выходит за пределы игрального зала
У задачи о двуруком бандите уже есть различные практические применения. Например, в интернете ее алгоритмы используют для продвижения товаров, подстраиваясь под неизвестные предпочтения пользователей. Исследование же, проведенное в Новгородском университете, направлено на оптимизацию так называемой пакетной обработки больших данных.
— Представим себе группу из 1000 пациентов, для лечения которых имеются два альтернативных лекарства, — объясняет на примере использования математического решения в Big Data автор проекта, Александр Колногоров, профессор кафедры прикладной математики и информатики, главный научный сотрудник Научно-исследовательского центра НовГУ.
— Применение каждого лекарства к лечению пациента дает с некоторой вероятностью единичный доход, если пациент поправился, и ничего, если продолжает болеть. Процесс лечения всех пациентов можно рассматривать как игру против двурукого бандита, а лекарства – как рукоятки, которые можно нажимать 1000 раз. Целью игры является максимизация среднего количества поправившихся пациентов.
Проблема в том, что пациентов нельзя лечить по очереди, так как результат действия лекарства требует значительного времени (к примеру, если он проявится через неделю, то на лечение 1000 пациентов потребуется 1000 недель, или около 19 лет). Но можно поступить другим образом: сначала дать оба лекарства двум сравнительно небольшим группам (допустим, из 100 пациентов). Посчитать через неделю, в какой группе поправилось больше людей. И дать целительное лекарство остальным 800 людям. В итоге все лечение займет две недели. Причем при правильном выборе размеров начальных групп эффективность такой пакетной обработки достаточно высока.
Универсальность математического метода
Как подчеркнул ученый, алгоритмы задачи о двуруком бандите также можно использовать в параллельной обработке данных. Этот способ существенно уменьшит продолжительность этого процесса и сделает стратегии его управления более универсальными. Это будет происходить за счет того, что распределения суммарных доходов в пакетах имеют распределение Гаусса. При этом в случае Big Data такое управление является почти таким же эффективным, как и оптимальное управление обработкой данных по одному случаю. Ведь доля данных, обработанных с ошибкой в обоих случаях, будет практически одинакова.
Для решения математической задачи использовались продвинутые математические методы. Были найдены оптимальные алгоритмы управления обработки данных, разбитых на большое число пакетов, и их точное математическое описание. Этого удалось добиться благодаря решению уравнений динамического программирования и дифференциальных уравнений в частных производных. Все это позволило построить ряд намного более простых с точки зрения реализации алгоритмов пакетной обработки, которые лишь немного (примерно на 10%) уступают в эффективности оптимальным.
Результаты исследования представлены на международных научных конференциях (по стохастическим методам и теории оптимизации и исследованию операций). Опубликованы в научных журналах: «Проблемы передачи информации», «Автоматика и телемеханика», «Математическая теория игр и ее приложения». Рекомендации по возможному практическому применению раскрыты в отчетах по проекту.
В данный момент ученые продолжают работу над обобщением результатов на случай «многорукого бандита». Или игрального автомата с числом рукояток больше двух. Потому что результаты, полученные для двурукого бандита, могут быть автоматически перенесены для решения многорукого.
Научное исследование новгородских ученых было проведено на средства гранта Российского фонда фундаментальных исследований, полученного в 2020 году, и Министерства образования и науки, полученного в 2014 году. Средства пошли на закупку оборудования и оплату научной деятельности рабочей группы.
Материал подготовлен при грантовой поддержки Минобрнауки России в рамках «Десятилетие науки и технологий».
Telegram 
Дзен 
VK Хотя сам факт наличия непонятных объектов на снимках, которые американские астронавты сделали на Луне, известен давно, десятилетиями их списывали на химические дефекты светочувствительной эмульсии фотопленки или блики света в линзах камер. Новая публикация на сайте Пентагона признает их реально существующими объектами, хотя и не делает выводов о их природе.
Крупные травоядные утконосые майазавры известны своим развитым социальным поведением. Они жили семьями и строили гнезда для своих детенышей. Даже название вида переводится с греческого языка как «ящер — хорошая мать». Исследование окаменелых зубов майазавров показало, что они выращивали детенышей совсем не так, как это считалось типичным для животных глубокой древности.
Десятого мая 1940 года вермахт пришел в движение. Через 42 суток англо-французские армии были разгромлены, а Франция капитулировала. Как это произошло, ведь союзники имели больше солдат, танков и пушек, чем немцы? В СССР причиной посчитали нежелание французов воевать, немцы же, говорили советские военные, не внесли в стратегию ничего нового. Реальность была строго обратной: разгром Франции был новым словом в войне, и такой же сценарий Гитлер применил против СССР через год. Что именно произошло и отчего советское руководство не смогло осознать случившееся?
Нейробиологи СПбГУ продемонстрировали, что активация рецептора следовых аминов TAAR1 эффективно подавляет агрессивное поведение, вызванное полным отсутствием серотонина в мозге. В дальнейшем этот результат поможет в разработке лекарственных препаратов, направленных на коррекцию патологических форм агрессии, возникающих при посттравматическом стрессовом расстройстве (ПТСР) и шизофрении.
Крупные травоядные утконосые майазавры известны своим развитым социальным поведением. Они жили семьями и строили гнезда для своих детенышей. Даже название вида переводится с греческого языка как «ящер — хорошая мать». Исследование окаменелых зубов майазавров показало, что они выращивали детенышей совсем не так, как это считалось типичным для животных глубокой древности.
Астрономы впервые использовали гравитационные волны, чтобы косвенно оценить параметры одного из ключевых процессов термоядерного горения в массивных светилах. Именно от него зависит, какие звезды взрываются, какие превращаются в черные дыры и как во Вселенной появляются углерод и кислород — элементы, без которых не было бы ни планет, ни жизни.
В последнее время пуски с российских северных космодромов осуществляют без предварительного уведомления, чего не было в прошлом. Вероятно, дело в недавно упомянутых главой «Роскосмоса» атаках на Плесецк во время пуска. Сегодняшний запуск обеспечил вывод на орбиту космических аппаратов военного назначения.
Химические связи в материале, из которого сделана электроника, разрываются не из-за накопительного износа от протекания тока через них, а из-за электронов с конкретной энергией.
Термоядерные электростанции не смогут конкурировать по цене с возобновляемыми источниками энергии из-за медленного удешевления технологии. По расчетам, расходы на каждую новую установку падали максимум на 8% — много раз ниже ранних ожиданий венчурных инвесторов. Это перечеркивает экономический смысл финансовых вливаний, и мир может никогда не увидеть дешевой термоядерной энергии.
Вы попытались написать запрещенную фразу или вас забанили за частые нарушения.
Понятно
Что-то в вашем комментарии показалось подозрительным, поэтому перед публикацией он пройдет модерацию.
Понятно
Из-за нарушений правил сайта на ваш аккаунт были наложены ограничения. Если это ошибка, напишите нам.
Понятно
Наши фильтры обнаружили в ваших действиях признаки накрутки. Отдохните немного и вернитесь к нам позже.
Понятно
Мы скоро изучим заявку и свяжемся с Вами по указанной почте в случае положительного исхода. Спасибо за интерес к проекту.
Понятно