Алгоритмы *

Доброго утречка. Прогреемся?

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

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

Привет, Хабр. Мы — Савченко Андрей — директор по науке, и Иван Карпухин — senior researcher в в Sber AI Lab — Центре практического искусственного интеллекта Сбера, расскажем о нашем исследовании, представленном на конференции AAAI 2026.

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

На первый взгляд эти две области никак не связаны между собой. В одном случае модель ищет автомобили, людей и дорожные знаки на фотографии, а в другом — пытается предсказать будущие покупки клиента банка, последовательность медицинских процедур или активность пользователя в социальной сети. Но если отбросить подробности реализации и посмотреть на задачу более абстрактно, то мы обнаружим сходство. В компьютерном зрении необходимо ответить всего на два вопроса: что находится на изображении и где именно расположен объект. В прогнозировании событий задача выглядит почти так же: какое событие произойдёт и когда именно это случится. Двумерное пространство изображения превращают в одномерную временную ось. Эта аналогия впоследствии позволила перенести целый класс методов из object detection в моделирование последовательностей событий.

Привет! Меня зовут Евгений Астафуров, я ведущий разработчик в Отделе экспериментальных технологий AI VK. Мы разрабатываем Discovery AI — набор ИИ‑технологий для интеллектуального поиска, рекомендаций и взаимодействия с контентом. В него вошли нейропоиск, анализ контекста, персонализация, генеративные модели и рекомендательные алгоритмы, чтобы помогать пользователям находить нужную информацию, получать релевантные ответы и новый контент.

В этой статье подробно разберу архитектуру технологии нейропоиска в Discovery AI, которая объединяет большую языковую модель (LLM), поиск, инференс и данные многомиллиардной контентной базы VK. Технология становится важным компонентом развития рекомендательных и поисковых систем в наших продуктах и будет поэтапно внедряться в сервисы для пользователей, авторов и бизнеса (Дзен, VK, Медиапроекты Mail, VK Видео и другие). 

И снова здравствуйте! Продолжаю свой рассказ о поиске «универсального рецепта» для обучения моделей в Luna Line. Теперь речь пойдет о сегментации. Если вы пропустили предыдущую публикацию по классификации, то вам лучше начать читать с нее, чтобы не запутаться. 

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

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

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

Мы пройдём путь от первых ML‑экспериментов до регулярных испытаний на реальных машинах. Разберём, чем Open Loop отличается от Closed Loop, почему качество предсказаний не определяет качество вождения и почему безопасность для нас важнее любой архитектуры.

Статья о пет-проекте — попытке создать мини-библиотеку по линейной алгебре с небольшим функционалом для работы с матрицами.

Представьте себе площадь: людную, шумную, и на ней стоят двое, назовем их Алиса и Коля. Им нужно договориться о пароле, но шептаться друг с другом нельзя. А еще вокруг толпа, и в толпе стоит Ева, которая записывает каждое слово. Никаких записок, никаких встреч за кулисами, только крик через всю площадь.

Звучит как безнадежная задача. Все, что Алиса крикнет Коле, услышит и Ева. Любая информация, которая дойдет до Коли, дойдет и до нее. Кажется, что общий секрет в таких условиях невозможен в принципе.

А теперь плохая новость для нашей интуиции: именно это сейчас происходит на вашем устройстве.

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

Внутри TTS работает каскад из трёх компонентов: языковая модель предсказывает аудиотокены по тексту, диффузионный декодер восстанавливает мел‑спектрограмму из латентов, а вокодер превращает её в звуковую волну. Долгое время самой тяжёлой была языковая модель, но после её оптимизации на первый план вышел декодер латентов — его forward pass запускается на каждом шаге семплинга диффузии, а шагов — десятки. Именно его мы и взялись ускорять.

Если вы хоть раз пытались сделать печатную плату сложнее «мигалки на светодиоде», вы знаете цену «геометрического ада».

ЛУТ (лазерно-утюжная технология) — это лотерея. Классический фотометод требует идеального шаблона, а профессиональный фотоплоттер стоит как подержанный автомобиль. Казалось бы, решение на поверхности: взять доступный китайский лазерный гравер за $100 и вперёд. Но тут начинается новый «ад»: оси изначально кривые, реальный шаг моторов живёт своей жизнью, а заготовка почти всегда лежит на столе с перекосом в пару градусов. Малейшее отклонение — и прецизионный Gerber превращается в бесполезный кусок текстолита.

Я решил эту проблему иначе. Зачем часами юстировать механику, если можно переложить всё на математику и нейросети?

Представляю LPP-Laser — флагманское направление открытой модульной платформы LPP (Linear Path Platform). Система не требует от станка совершенства. Она просто «натягивает» ваш проект на реальность.

Представим задачу: хайлоад-сервис гонит поток данных — логи, IP-адреса, ID пользователей, миллиарды записей в сутки. Ваша задача — посчитать количество уникальных посетителей за неделю.

Первым решением может показаться завести HashSet и кидать туда ключи, а в конце посмотреть размер. Решение неплохое, но когда речь заходит о миллиардах записей — память будет слабым местом. Один IP-адрес (4 байта) как ключ в HashSet потянет за собой накладные расходы на ноды, указатели и хеши. На практике один элемент сжирает не меньше 50–100 байт. Поток в миллиард уникальных записей потребует под сотню гигабайт оперативной памяти. Это дорого, а если инстансов десять — то просто нереально.

Но существует алгоритм, который способен решить эту задачу примерно в 1.5 килобайта памяти с погрешностью около 2%? Без хранения самих данных и гигантских кластеров. Достаточно одного прохода по потоку и пары битовых трюков — именно так и работает HyperLogLog, алгоритм родом из математической статистики, который перевернул подход к подсчёту уникальности в Big Data.

HyperLogLog используют в Redis, BigQuery, ClickHouse, Presto. В этой статье мы разберем и реализуем этот алгоритм на C, а также узнаем его предысторию.

Всем привет! Меня зовут Гриша Дядиченко, я технический директор и основатель White Label Games. Уже больше десяти лет работаю с компьютерной графикой, AR/VR и компьютерным зрением — в основном это заказная разработка, плюс собственные прототипы по вечерам, до которых дотягиваются руки.

Делал я как-то на работе, по вечерам в свободное время, VR-шутер. Стрельбу, понятное дело, заложил себе на выходные: ну а что, raycast из ствола, событие попадания, отнял здоровье — делов-то. К вечеру воскресенья оно даже работало. Только ощущалось так, будто тыкаешь противника палкой: ни веса, ни отдачи, ни чувства, что ты вообще попал. Знакомо, наверное, каждому, кто хоть раз ставил в сцену оружие и жал «выстрел» — механически всё верно, а стрельба вялая и какая-то ненастоящая. Половина лечения тут — чистая полировка: вспышки, звук, тряска камеры, импакт-эффекты. А вот вторая половина — невидимая математика под капотом: та, что решает, ощущается стрельба честной и отзывчивой или кривой и несправедливой. Спред, который мозг считывает как «нечестный». Отдача, которую можно выучить. Попадание, которое по сети то засчитывается, то нет. Вот это всё и разберём.

Сталкивались ли вы с ситуацией, когда в шутере вы точно попали по противнику, а сервер сказал «промах»? Или с тем, что AI-противник стреляет в вас сверхскоростным снарядом и ни разу не попадает в движущуюся цель? Или с тем, что AK-47 в Counter-Strike рисует «семёрку» из пуль вверх и влево — и это, конечно же, никакой не баг, а вполне продуманная механика? Под капотом у всех этих ситуаций — конкретная математика.

Привет, Хабр! Меня зовут Анастасия Белозерова, я тимлид исследовательской команды, работающей над продуктом Luna Line в VisionLabs (входит в MWS AI). Мы занимаемся созданием no-code-платформы для компьютерного зрения, которая позволяет пользователю (не программисту, а агроному, например) разметить данные, нажать на кнопку и получить идеально обученную CV-модель под свои рабочие задачи, даже если у него для этого данных всего-то 50 картинок. 

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

Кто желает не читать, а смотреть и слушать, вот тут лежит видеозапись моего доклада по этой теме на Митапе D﹥﹤Vision. 

Но давайте сначала коротко расскажу о продукте.

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

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

Была, правда, одна экспериментальная попытка с Meta* на выборах США в 2020-м. Тогда выявили, что алгоритмическая лента усиливает «нецивильный» контент примерно на 40%. Вот только авторы работы не зафиксировали изменения в установках и не смогли ответить на главный вопрос: через какой психологический механизм лента влияет на пользователей и можно ли это исправить, не сломав их интерес к самой соцсети?

Этот пробел закрыла группа исследователей под руководством Уильяма Брэди (ассистент-профессор управления и организаций в Kellogg School of Management), которая весной этого года опубликовала результаты своей работы в научном журнале Nature.

Как им это удалось и что из этого вышло, расскажу в этой статье.

Проверил реализацию Boyer-Moore в TheAlgorithms/Python (190K+ звёзд). Оказалось, что сдвиг bad character записывается в переменную for-цикла, что в Python не имеет эффекта. Алгоритм выдаёт правильные результаты, но работает как brute-force O(nm) вместо O(n/m). Плюс ещё две находки: бесконечный цикл в типичных реализациях full BM и ошибка в оригинальной статье 1977 года, которую исправили только в 1980-м.

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

С алгоритмом SimHash его объединяет то, что оба они просто потрясающе красивы! Настолько, что вот прям хочется про них рассказать.

Про SimHash в следующий раз, а вот если интересно чем же мне так понравился MinHash, добро пожаловать под кат!

Всем привет! Меня зовут Гриша Дядиченко, я технический директор и основатель White Label Games. Уже больше десяти лет работаю с компьютерной графикой, AR/VR и компьютерным зрением — в основном это заказная разработка, плюс собственные прототипы по вечерам, до которых дотягиваются руки.

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

Чтож, давайте по порядку. Как это устроено у настоящих скворцов над Римом и причём тут код, какие именно три правила Рейнольдса и как они балансируются весами, как сетка побеждает O(N²) и где она сама ломается, что такое ORCA и как она разруливает встречные потоки в коридоре, как steering behaviors дают агенту цель и обход препятствий, и что лежит под капотом конкретных шипнутых игр от AC Unity до World War Z.

Разбираем такие инструменты анализа сигналов, как конволюция и деконволюция, глазами инженера-нефтяника. Посмотрим на базовые методы и их продвинутые версии, на приёмы работы с данными: что эти инструменты дают и где у них границы. Много картинок, много мультиков, поменьше занудства, побольше практики.

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

Оказалось, что классика вроде «Съешь ещё этих мягких французских булок» не подходит — в моём наборе каждая буква была только один раз. А те панграммы, где буквы не повторяются (можно найти, например, у Лебедева в «Ководстве») — «Эй, жлоб! Где туз? Прячь юных съёмщиц в шкаф.» или «— Любя, съешь щипцы, — вздохнёт мэр, — кайф жгуч» — они, скажем так, на любителя. Слишком много восклицаний, междометий и прямой речи. Хотелось чего-то более пристойное и связное.

У меня получилось найти следующую панграмму:

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

В ней все 33 буквы русского алфавита, каждая по одному разу. В статье — как я её искал, фильтры словаря и то, как устроен поиск.

Я хотел просто пожарить кесадилью. В холодильнике лежали зеленые оливки (солено-кислые), сулугуни и фарш, а на полке консервированная кукуруза. И вот стою я над сковородкой и думаю: а оливки с кукурузой вообще сочетаются? А сулугуни не пересолит блюдо вместе с оливками? Сколько чего вообще класть?

В любой другой ситуации я бы загуглил рецепт. Но не тут-то было, я же великий комбинатор оптимизатор, и у меня в голове сразу всплыло: «это же задача оптимизации». Тем же вечером у меня был ноутбук с обученной нейросетью вместо ужина. Рассказываю, как дошел до жизни такой, и как из этого, внезапно, получился реально вкусный рецепт.

Стоит открыть исходники любого современного игрового движка – неважно, это C++-рендер, сделанный на коленке, или какая-нибудь гигантская экосистема вроде Unity или Unreal Engine – вы первым делом натыкаетесь на одни и те же знакомые сущности. Все вокруг живет в Vector3: координаты, направления движения, точки столкновений. Каждая частица указывает, куда она смотрит, с помощью Quaternion. А если требуется что-то покруче – переносить и одновременно крутить объект, то Matrix4x4. Это уже как стандарт де-факто: кто пробовал крутить объекты руками, тот точно переписывал код с этими структурами. Ещё конечно же отдельно существуют лучи, плоскости, сферы, bounding boxes, а между ними тянутся километры функций вроде dot(), cross(), normalize(), lookAt(), inverse(), project() и бесконечных преобразований типов.

Привыкаешь к этому быстро. Нам кажется совершенно естественным тасовать эти типы между собой – уж слишком давно так делается по всей индустрии. Но стоит лишь чуток задуматься, и начинает прорезаться легкий когнитивный диссонанс: выходит, вся наша графика построена на наборах несовместимых между собой математических запчастей. Для одного действия нам нужен один тип данных, для второго – другой, а пересчитать простое столкновение луча со сферой или плоскостью без пятого велосипеда никак не получается. Вроде бы всё работает и даже неплохо работает… Но ощущение конструктора из костылей не отпускает.

И самое интересное заключается в том, что так было не обязательно.