Алгоритмы *

Привет, Хабр! Мы — команда ML‑разработчиков Сбера и Sber AI Lab. Хотим рассказать о нашем open‑source инструменте RePlay, который позволяет создавать рекомендательные системы с нуля, начиная с самых ранних DS‑экспериментов и заканчивая промышленной эксплуатацией. Статья будет интересна ML‑инженерам, разрабатывающим промышленные рекомендательные системы.

Мотивацией для создания RePlay послужил тот факт, что все популярные на сегодняшний день RecSys‑фреймворки в основном нацелены на научные исследования и плохо оптимизированы для промышленной эксплуатации: не в состоянии обработать большой объём данных или требуют для этого значительных модификаций. Подробнее о создании библиотеки вы можете прочитать в соответствующей статье с RecSys 2024. По той же ссылке вы найдёте обзорное видео о RePlay.

Здесь же мы сравним RePlay с главными конкурентами — RecBole и Microsoft Recommenders. Разберём возможности, которые предоставляет каждая из библиотек, а затем, на примере SOTA‑модели, построим рекомендательную систему, начиная с ввода данных и заканчивая генерированием рекомендаций и подсчётом метрик. Сравним полученные модели по качеству и длительности обучения и инференса. В конце расскажем об уникальных возможностях RePlay, которые помогут ещё сильнее облегчить путь разработчика, по сравнению с использованием библиотек‑конкурентов

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

Вероятнее всего, что самым быстрым разбиения данных будет такой код (я использую в качестве псевдокода Python; можете представить, что я пишу это на вашем любимом низкоуровневом языке):

groups = [[] for _ in range(n_groups)]

for element in elements:

groups[element.group].append(element)

Он и в самом деле линеен (то есть асимптотически оптимален), и мы всё равно должны выполнять доступ к произвольным индексам, так что кэш здесь нам ни в чём бы не помог.

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

Возможно, вы слышали о финансовой стратегии ставок по методу Келли. Это система, позволяющая оборачивать себе на пользу известную информацию в азартной игре или связанные с ней предубеждения. Эта стратегия также называется максимально агрессивной или стратегией высокой дисперсии. Дело в том, что если сделать ставку выше, чем позволяет предел Келли, то последствия могут быть катастрофическими.
Недавно мне попалась странная карточная игра, в которой стратегия Келли абсолютно не подразумевала риска, поскольку в игре действует Нулевая дисперсия. В своей знаменитой книге «Математические головоломки» Питер Уинклер называет её «Next Card Bet» («Следующая карточная ставка»). Саму задачу и её решение, по-видимому, сформулировал Томас Кавер. Мне понравилась как сама эта игра в ставки, так и её анализ, поэтому я поделюсь ими с вами здесь.

Привет! Меня зовут Михаил Мазанов, я отвечаю за технологический стек работы с медиаданными в Кинопоиске: от съёмок оригинальных проектов до доставки и просмотра видео на всех экранах. Для нашей пятой ежегодной конференции про стриминг PlayButton 2024 я готовил большой доклад про оптимизацию качества видео Кинопоиска, а для Хабра решил пересобрать его в виде статьи — для тех, кому текстовый формат предпочтительнее видео.

Кроме технических графиков, вас ждёт ещё и наглядная разница в работе алгоритмов сжатия на примере «Рика и Морти» и «Джона Уика».

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

В этом году я со своими студентами провел такое проектно-научное исследование в рамках гранта НИУ «МЭИ» на реализацию программы научных исследований «Приоритет 2030: Технологии будущего». Тематикой работы была «Разработка интеллектуального драйвера IGBT на напряжение 3,3 кВ для 3-уровневых инверторов тяговых электроприводов поездов высокоскоростной железнодорожной магистрали Москва - Санкт-Петербург». Проект выполнялся с апреля по октябрь, и в нём были задействованы кроме меня, как руководителя, студенты 4 курса бакалавриата и 1 курса магистратуры.

Данный проект выполнялся в довольно небольшие сроки (полгода действительно срок довольно маленький для полноценного проекта), но, во-первых, у нас уже были определённые наработки по этой теме, а во-вторых, для данного исследования подразумевается продолжение в рамках следующего этапа ПНИ.

Как вы поняли из заявленной тематики, мы выполняли разработку отечественного драйвера IGBT, в рамках которой реализовали как аппаратное решение, так и программное обеспечение с необходимыми алгоритмами управления драйвера. Интересным моментом здесь было то, что мы пошли по рискованному пути и отказались в разработке от ПЛИС для реализации логики работы драйвера, и выбрали motorcontrol микроконтроллер с довольно развитой периферией, но при этом уступающий по быстродействию современным ПЛИС.

Вопрос на засыпку. Как вы реализуете перемешивание колоды карт?

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

Привет! Сегодня мы продолжаем реализовывать шифрование. В этой статье мы рассмотрим алгоритм шифра "Магма", который был разработан и использовался в СССР.

Интересуешься визуальной одометрией? В этой статье я сравнил алгоритмы ORB, R2D2, SIFT и их комбинации, реализовав их на Java с OpenCV. Подробно разобрал, как они работают, замерил точность, производительность и наглядно показал, какой алгоритм лучше для беспилотников. Если хочешь узнать больше и посмотреть примеры кода на Java, заглядывай!

Привет! Я Иван Косолапов, тимлид команды ETA/RTA. Мы часть сервиса Data Science и занимаемся анализом данных и машинным обучением для задач навигации в 2ГИС.

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

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

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

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

Расскажу, как решая эти задачи, мы добились более точного отображения автобусов на карте в 2ГИС, упростив существующую на тот момент сложную систему.

Сегодня посмотрим на примере задачки из Advent of Code зачем и как можно обойти ошибку aggregate functions are not allowed in a recursive query's recursive term, возникающую при попытке агрегировать какие-то данные внутри шага рекурсии на PostgreSQL — «если нельзя, но очень хочется, то можно».

Добрый день! Меня зовут Кирилл Зиборов, я представляю отдел безопасности распределенных систем Positive Technologies. В этой статье я продолжу рассказывать о том, как мы используем инструменты формальной верификации для предотвращения уязвимостей в различных компонентах блокчейна. Ранее мы верифицировали смарт-контракты дедуктивным методом. В этот раз речь пойдет о протоколах консенсуса — механизмах принятия узлами новых транзакций в цепочку, а именно об алгоритме Istanbul Byzantine Fault Tolerant и в целом о том, как можно гарантировать корректность подобных алгоритмов с помощью метода проверки моделей.

Тридцать восемь лет назад в свои тридцать восемь лет аспирант Мичиганского университета Крис Лэнгтон придумал два простых правила для клеточного автомата. Мы быстро повторим правила Лэнгтона, оживим муравья, написав код онлайн, добавим динамики (плавная анимация) и интерактивности (редактор уровней). Повоюем, постреляем купидоновыми стрелами, порисуем на заборе. А ещё педагогически немного адаптируем код для занятий с детьми (опционально).

Привет, меня зовут Коновалов Андрей, я Data Scientist персональных рекомендаций Wildberries. В этой статье разберем, как можно тюнингом TF-IDF побить BERT4Rec в ретро-тесте рекомендательной системы.

В сервисе Яндекс Переводчик мы поддерживаем перевод между 102 языками. Наша цель — обеспечивать качественный перевод для самых разных типов данных: текстов, документов, HTML, изображений и видео. Сегодня обсудим ключевой компонент для обучения моделей машинного перевода — данные для обучения.

Современные нейросетевые подходы очень требовательны как к объёму данных в обучении, так и к их качеству. Для получения хорошей переводной модели требуются сотни миллионов, а в идеале миллиарды параллельных предложений (пар из предложения и его перевода). Возникает вопрос: откуда их взять и что это за данные?

В этой статье я расскажу о том, как из текстов интернета в 100 ПБ найти терабайты суперчистых данных с переводами между любыми языками. Вы узнаете, почему эта задача требует обучения больше десятка различных вспомогательных ML‑моделей. А ещё коротко подсвечу, какое место в этом процессе занимает наша YandexGPT и что это за зверь такой — YandexGPT‑MT.

Pushy — это WebSocket‑сервер Netflix, который поддерживает долговременные WebSocket‑соединения с устройствами, на которых работает приложение Netflix. Благодаря этому данные с бэкенд‑сервисов можно отправлять на устройства по мере необходимости. При таком подходе нет нужды в постоянного опроса сервисов устройствами. За последние несколько лет Pushy пережил огромный рост, превратившись из сервиса для негарантированной доставки сообщений в неотъемлемую часть экосистемы Netflix. В этом материале вы узнаете о том, как мы развивали и масштабировали сервер Pushy, стремясь к тому, чтобы он хорошо справлялся со своими текущими обязанностями, и к тому, чтобы подготовить его к будущим нагрузкам. Он поддерживает сотни миллионов одновременных WebSocket‑подключений, доставляет адресатам сотни тысяч сообщений в секунду и удерживает стабильный уровень надёжности доставки сообщений в 99,999%.

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

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

Всем привет! С вами снова Костя Логиновских — ведущий разработчик из Cloud.ru. Я уже делился TypeScript-рецептами в предыдущих статьях — вот первая и вторая — и теперь хочу рассказать про еще один. Наши рецепты — это готовый код, который можно применить в конкретных ситуациях, а в некоторых случаях и подогнать ситуацию под код.

Сегодня в меню — функция на обычном TypeScript, которая преобразует тип объекта так, чтобы все ключи внутри него из snake_case стали camelCase. Жду всех под катом!

BM25, или Best Match 25 — это широко используемый алгоритм полнотекстового поиска. Среди прочего, он по умолчанию применяется в Lucene/Elasticsearch и SQLite. В последнее время в рамках «гибридного поиска» часто начали комбинировать полнотекстовый поиск и поиск по схожести векторов. Мне захотелось понять, как работает полнотекстовый поиск и в частности BM25, поэтому в этой статье я постараюсь разобраться в этом.