🚀 @SBERLOGASCI webinar on data science:
👨‍🔬 Кирилл Хоружий "Введение в методы поиска короткого пути на больших графах"
⌚️ Четверг 4 июня, 19.00 (по Москве)

Мы с коллегами организуем проект по применению методов МЛ/RL к задачам теории групп и графов Кэли - если Вы хотите присоединиться - напишите - @alexander_v_c. В четверг Кирилл Хоружий сделает вводный доклад по этой теме - приходите ! (А также подписывайтесь на замечательный канал Кирилла - @diagrams_every_day ).

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

На вебинаре мы рассмотрим методы решения задачи поиска пути в крупных перестановочных графах, таких как Кубик Рубика или Пятнашки, где задача поиска пути становится весьма сложной. Мы обсудим state-of-art подходы, показанные в работах DeepCubeA (2019) (Nature) и Self-Supervision methods (2023) (arXiv).

Возможные варианты решения задачи о поиске пути:
1. Оценка дистанции случайными блужданиями. Из целевой вершины делаем K шагов и обучаем модель предсказывать K, которое хорошо коррелирует с реальной дистанцией (d). Используем эту модель как эвристику для алгоритма A*.
2. DQ-learning. Предсказывать моделью реальную дистанцию, в лучших традициях DQN основываясь на уравнение Беллмана улучшать после обучения предсказанные расстояния и обучаться заново. Затем также на А* искать путь.
3. Обратная диффузия. Делая случайные шаги, мы почти гарантировано отдаляемся от целевой вершины. Научимся по вершине, предсказывать откуда в неё мы пришли, случайно блуждая. Затем через beam search находим наиболее вероятный путь в целевую вершину (самый короткий ~ самый вероятный).

Также обсудим возможные упрощения жизни для модели через алгоритм Метрополиса и существующие эвристики.

Zoom link will be in @sberlogabig just before start. Video records: https://www.youtube.com/c/SciBerloga - subscribe !

📖 Presentation: https://t.me/sberlogasci/10989/15283
📹 Video: https://youtu.be/2J3eGGH-uiM?si=9xgHtcCpBj0wKXC0