Алгоритмы *

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

Сегодня через API стала доступна новая модель YandexGPT 3 Lite. Одним из ключевых этапов её обучения, как и в случае с другими недавними моделями, стал этап выравнивания (Alignment), включающий в том числе стадию обучения с подкреплением (RL). Пожалуй, без этого этапа мы бы не смогли добиться такого роста в качестве, который был необходим для запуска новых возможностей и сервисов (например, Нейро). Поэтому эту статью мы полностью посвятим особенностям выравнивания моделей. 

На тему Alignment и RL было написано уже немало статей. Кажется, любой ML-инженер уже, так или иначе, сталкивался или читал о них. Поэтому мы хоть и напомним базовую информацию, но всё же сфокусируемся на тех деталях реализации, которые не на слуху. 

По большому счёту, самая первая и самая важная оптимизация, которую можно применить к любой современной системе машинного обучения, заключается в том, чтобы реализовать в этой системе пакетную обработку данных (batching). Для того чтобы получить результат работы системы (inference, инференс) в пакетном режиме — ей, вместо одного элемента входных данных, отправляют N таких элементов. Чаще всего никаких дополнительных нагрузок на систему это не создаёт. Формирование инференса для каждого из элементов, входящих в пакет размера N, занимает в точности столько же времени, сколько нужно для обработки одного элемента входных данных. Почему это так? На первый взгляд может показаться, что обработка пакета данных не может обойтись без некоторых накладных затрат ресурсов. В конце концов — оборудованию приходится выполнять в N раз больше действий.

Если прибегнуть к простейшей модели работы нейронной сети, то получится, что некоторая дополнительная нагрузка на систему, всё же, создаётся. Для выполнения пакетных вычислений нужно выполнить в N раз больше операций. И, на самом деле, если попробовать это на CPU, то окажется, что так оно и есть (среднее время формирования вывода для ResNet-50, Colab).

Думаю все кто так или иначе интересовался сжатием информации или каким-то другим способом кодирования данных - слышали о кодах переменной длины. Я расскажу про свою реализацию этого велосипеда.

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

Как создать бизнес на слитых данных - рассказываю на примере компании SimilarWeb.

Привет всем любителям size coding, сегодня я расскажу о чём-то потрясающем: крошечном движке трассировки лучей (raycasting) и генераторе города, умещающихся в автономном файле HTML размером 256 байтов.

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

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

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

Замечания о математике, алгоритмах и методах, применяемых при компьютерной симуляции флюидов (например, огня и дыма) в режиме реального времени.

Исходный код к этой статье выложен на GitHub.

Огонь как явление очень интересен с точки зрения компьютерной графики. Раньше огонь было принято имитировать. Например, в фильме «Властелин колец» Питера Джексона для изображения огня использовались спрайты с огромным количеством дыма (на тот момент симуляция флюидов обходилась слишком дорого, даже при бюджете блокбастера). Когда требовалось моделировать огонь в режиме реального времени, например, в видеоиграх, использовались почти исключительно нефизические подходы.

▍ Зачем ограничивать частоту?

Хабр, привет! Это снова Антон Разжигаев, аспирант Сколтеха и научный сотрудник лаборатории Fusion Brain в Институте AIRI, где мы продолжаем углубляться в изучение языковых моделей. В прошлый раз мы выяснили, что эмбеддинги трансформеров-декодеров сильно анизотропны. На этот раз я бы хотел рассказать об их удивительной линейности, ведь нашу статью про обнаруженный эффект («Your Transformer is Secretly Linear») несколько дней назад приняли на международную конференцию ACL!

Привет, Хабр! Мы представляем команду GigaCode. В декабре 2023 года наш продукт стал доступен широкой аудитории. До этого GigaCode использовался только внутри компании, и нас часто спрашивали о том, как GigaCode выглядит на фоне других ИИ-ассистентов, как вы сравниваете себя с остальными? Отвечая на эти вопросы, мы начали с простой задачи, которая оказалась не такой уж и простой и вылилась в увлекательное исследование со всем тем, что мы так любим: множеством измерений, математической статистикой и, конечно же, новыми горизонтами. Интересно? Добро пожаловать под кат.

Как и планировалось, следом за реализацией семейства хэш-функций SHA, появляется Стрибог и тоже в двух версиях, для 256 и 512 бит на выходе. Надеюсь эта статья будет полезна другим студентам. Более опытные разработчики в комментариях приветствуются.

Весь код сохранен в репозитории GitVerse.

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

Учёные, занимающиеся информатикой, — это требовательная группа. Им недостаточно получить правильный ответ — цель почти всегда состоит в том, чтобы получить ответ как можно эффективнее.

Возьмем, к примеру, умножение матриц или массивов чисел. В 1812 году французский математик Жак Филипп Мари Бине разработал базовый набор правил, которым мы до сих пор обучаем студентов. Это работает прекрасно, но другие математики нашли способы упростить и ускорить процесс умножения матриц.

В последние годы в нашей повседневной речи плотно закрепилось словосочетание «нейронные сети». Этот термин означает набор методов и программных решений из машинного обучения, дискретной математики и информатики. Но про что совсем часто забывают — он происходит из нейробиологии. Несмотря на очевидное название, нейросети — это не набор операторов IF и ELSE, а модели, вдохновлённые нервной системой живых организмов. Их эффективность в пору, когда у нас есть такие генеративные модели как GigaChat и Kandinsky, наглядно видна каждому. 

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

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

Всем привет! В этой статье я опишу алгоритм работы формата сжатия изображений без потерь. Сжатие использует известные методики, которые и дали ему название. Проект начинался с простых экспериментов, которые вышли из под контроля. Не смотря на то, что формат чаще сжимает лучше чем png, никакого практического применения этот формат не имеет, оставаясь чисто академическим.

Внимание! В статье много картинок.

Внутри Dolt, первой в мире базе данных SQL с полнофункциональными возможностями контроля версий, таится много интересной computer science. Недавно я писал о системе хранения Dolt, в ней есть очень тонкая особенность — применение вероятностного поиска на больших выборках 64-битных целых чисел.

В любом учебном плане по Computer Science есть курс алгоритмов. Моим был CS 102, и одним из пунктов, который объяснялся в нём досконально, было то, что поиск — это, по сути, задача O(log2(N)) при условии, если данные отсортированы. За свою карьеру я многократно встречался с этим в том или ином виде — если сортируешь информацию и сохраняешь её, то стоит ожидать, что для поиска потребуется время O(log2(N)). В общем случае мы соглашаемся на время поиска O(log2(N)), потому что оказывается, что можно перебрать большой объём данных с логарифмическим коэффициентом масштабирования. Эта система работает, потому что мы уже почти автоматически сортируем всё заранее.

Но что если мы добавим дополнительные ограничения на наши данные, которые позволят нам выполнять поиск за константное время?

Будет ли эта статья историей о необязательной оптимизации? Да, будет. В этом конкретном случае поиск будет занимать гораздо меньше времени, чем чтение с диска. Мы говорим о величинах менее чем 0,1% от суммарного времени. Будет ли эта статья историей о преждевременной оптимизации? Нет, не будет. Это бы подразумевало, что мы не осознаём, что время тратится не на то. Эта статья — история о заманчивости алгоритма константного времени.

Связный список — классическая структура данных, которая позволяет быстрые вставки/удаления, но при этом просаживает другие операции (случайный доступ к элементу). Мы пройдёмся от базовой реализации до других возможных вариаций этой структуры данных и, надеюсь, вместе узнаем что‑то новое. Краем глаза увидим возможные применения связных списков. И в конце, для любителей C++, бонус: использование связного списка для сбора диагностики выделений динамической памяти в вашем коде.