Алгоритмы *

Примерно полгода назад математическое сообщество услышало новость о том, что исследователи DeepMind создали ИИ-систему, решающую геометрические задачи с Международной математической олимпиады на уровне, близком к золотым медалистам ММО. (Эту новость обсуждали в сабреддите \math, см., например, здесь и здесь.) За этими новостями, как часто бывает с новостями о прогрессе ИИ, последовала волна страха и ужаса, усиленная множеством громких газетных статей с картинками (разумеется, сгенерированными ИИ), на которых искусственные мозги решают ужасно сложные уравнения. По коллективной спине математического сообщества побежали мурашки, снова всплыли на поверхность обычные экзистенциальные вопросы о будущем человеческого интеллекта, а Интернет заполнили мемы о грядущем восстании машин.

Я бы хотел взглянуть на эту тему под новым углом. (Предупреждение: возможно, для вас он не будет новым. Если вы имели дело с евклидовой геометрией, понимаете основы линейной алгебры и внимательно читаете журнал Nature, то могли прийти ко всем этим выводам самостоятельно. Но поскольку некоторые критичные аспекты изложены мелким шрифтом (вероятно, намеренно), я всё равно считаю, что их нужно сделать более очевидными.)

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

Вадим Мартынов, руководитель команды платформы надёжности в Яндекс Go, в своём докладе рассказал, как влияют те или иные решения на надёжность системы и как это учитывать при разработке.

Введение

Карл Давид Тольме Рунге (30 августа 1856 - 3 января 1927) - выдающийся немецкий математик, физик и спектроскопист. Обучался в Берлинском университете, где получил степень PhD, являлся профессором математики в Ганноверском университете, а также главой кафедры прикладной математики в Гёттингене. [1]

в 1901 году Карл открыл "Феномен Рунге" - в численном анализе эффект нежелательных колебаний, возникающий при интерполяции полиномами высоких степеней - о котором пойдёт речь в данной статье. [2]

Но прежде, чем мы окунёмся глубже в изучение данного феномена, давайте поговорим об интерполяционном многочлене Лагранжа, на примере которого мы и разберём Феномен Рунге.

Интерполяционный многочлен Лагранжа

Полином Лагранжа - это математическая функция, позволяющая записать полином n-степени, который будет соединять все заданные точки из набора значений, полученных опытным путём или методом случайной выборки. Многочлен в форме Лагранжа в явном виде содержит значения функций в узлах интерполяции, поэтому он удобен, когда значения функций меняются, а узлы интерполяции неизменны. Число арифметических операции, необходимых для построения многочлена Лагранжа, пропорционально и является наименьшим для всех форм записи. [3]

Полином Лагранжа в общем виде выглядит следующим образом:

Мы будем считать 1000,000,000 число Фибоначчи со всеми цифрами. Для этого я буду использовать продвинутый алгоритм для поиска чисел Фибоначчи. Тут не будет базовых алгоритмов на подобии матричного возведения в степень и проще. Но эта статья будет понятна и школьнику :-)

Уже много лет IT компании проводят алгоритмические собеседования при найме технических специалистов. Подход введенный в FAANG плавно перетек в большинство крупных компаний. Яндекс, Авито, Т-Банк и многие другие хотят проверить алгоритмические знания кандидатов. Но на практике такое собеседование оказывается бесполезным созвоном на 45 минут, который ничего не говорит о кандидате.

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

Но очень мало можно встретить критики и конкретного разбора проблем алгоритмических собеседований и их внедрения в воронку найма. Эта статья будет первой в цикле “в чем проблема алгоритмов”.

Кто-то может сказать: “О, человека не приняли в компанию из-за алгоритмов и он решил обидеться и сказать всем, что алгоритмы бесполезны”. Отчасти это так и было, но я решил не останавливаться на своем чувстве несправедливости и пошел дальше: адаптировал алгоритмы в компании, прошел все этапы в Google и даже решал алгоритмы на протяжении года.

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

Но все это отдельными статьями, ссылки на которые я приложу сюда позже.

Сейчас я просто хочу рассказать свою историю.

Если вы никогда не пробовали смотреть как код на C++ разворачивается компилятором в код Assembly – вас ждёт много сюрпризов, причём, не нужно смотреть какой-то замудренный исходный код полный templates или других сложных конструкций: рассмотрите следущий snippet:

Привет, меня зовут Рома. Я работаю в отделе спецпроектов KTS на позиции Python backend-разработчика. 

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

TLDR

В этой статье мы научим авто самостоятельно парковаться с помощью генетического алгоритма.

Мы создадим первое поколение авто с произвольными геномами, которое будет вести себя примерно так:

Примерно на сороковом поколении авто начнут понимать, что такое авто-парковка, и начнут приближаться к парковочному месту:

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

Свойство: Если какой‑то отрезок AB не включен в триангуляцию Делоне, то существует путь из A в B по отрезкам из триангуляции, такой что каждый из отрезков в нем не длиннее |AB|. На картинке выше отсутствующий отрезок показан красным цветом, а путь — зеленым цветом.

Дальше в статье я приведу пример его использования в задачах, а также формальное его доказательство.

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

Матричное расширение ISA CPU… Что это и что оно делает? Уже из названия понятно, что это расширение позволяет ускорять операции над матрицами на CPU. Но задумывались ли вы когда-нибудь, какие они бывают, когда появились, кто и как их создает?

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

Матричные расширения появились не так давно — чуть более трех лет назад. Несмотря на это, они есть у каждой уважающей себя процессорной архитектуры, в том числе и у относительно молодой открытой RISC-V. Почему их так много и чем они отличаются? Поддерживаются ли разреженные матрицы? Об этом и многом другом вы узнаете из статьи. Приготовьтесь, будет интересно и (спойлер!) без многоэтажных формул. 

Никогда особо не стремился в большие компании, по душе всегда были небольшие уютные игровые студии, где и "отеческий" нагоняй от лида получить легко, да и самому "парой ласковых" объяснить коллегам где они были не правы можно. Но конечно шальные мысли, а вот если бы в Я..., да какой-нибудь еще фейсгугл попробоваться. Жаль только они не делают игры, но мысль эта таилась на закорках подсознания, периодически напоминая о себе в моменты просмотра объявлений, да после писем рекрутеров на linkedin. Около года назад два моих знакомых, которые давно уже живут на другом континенте, но с кем застали еще распад питерского EA, вдруг объявились на страничке в linkedin, оставили отзывы да отсыпали скилов. Сначала я не придал этому особого значения, мало ли чего там себе люди думают, может просто сеть знакомых обновляют, есть у них там за океаном такая забава. И так получилось, что на эти отзывы сагрились hr-боты большого G..., что и привело в дальнейшем к очень интересному опыту взаимодействия с людьми, знакомством с кухней отбора, этапами собеседования и воронкой "смерти" входа. Осторожнее надо быть со своими желаниями.

Где-то уже на хабре были статьи и про G... и про Я..., такие, что читая описания задачек на собесах, волевым решением на следующее утро начинал решать leetcode. Воли обычно хватало где-то на неделю, а потом рутина боевых задач и митинги затаскивали обратно в уютную берлогу не очень большого игростроя. Почему я решил написать об этом только через год после всех событий? Да банально подмахнул на третьем собеседовании NDA о методах проведения интервью, а когда понял ЧТО подписал - уже было поздно.

Это история из цикла «как войти в IT», написанная старпером, ветераном броуновского движения, который помнит динозавров. Поэтому его опыт вхождения в ИТ никому не пригодится, но представляет интерес с точки зрения истории.  

Также поделюсь своим мыслями об интерфейсе инженерного ПО. Участвуя в разработках различного ПО, предназначенного для ускорения разработки сложных систем, периодически приходится выслушивать жалобы от новых пользователей на «кривой и устаревший» интерфейс ПО. Однако инженеры, погруженные в проблемы проектирования реальных железок, вообще не задают нам таких вопросов, либо потому, что уже искривили свои руки о кривой интерфейс, либо им это вообще неважно. Более того, есть два примера, когда реальные высокопрофессиональные инженеры в своей области предъявляли претензии обратного свойства, и первая версия кривая версия GUI была удобнее, а вот улучшения делали какие-то полупокеры. 

К написанию данного текста меня подтолкнула беседа с одним из крутых разрабов из «жирной» конторы, с которым мы пересеклись на яхте в Средиземном море. Узнав, что я тоже из Бауманки, и у меня свой бизнес, он заинтересовался и выспрашивал. Как я смог начать бизнес на софте, почему не пошел в большую контору, типа Yandex, Сбер и прочие. У него тоже знакомство с софтом началось как создание собственной разработки по анализу результатов металлургических испытаний в лаборатории, но закончилось работой прогером по найму. Попивая вино на яхте где-то между Турцией и Грецией в 2023 году, он предположил, что, возможно, если бы он продолжал писать софт для металлургических исследований, то, наверное, сейчас мог плавать на своей яхте, а не арендованной, и не около Турции, а на Карибах (но это не точно). А поскольку фарш невозможно провернуть назад, я решил описать свою историю успеха, так как она забавна и поучительна.

Представьте, что вас отправили в девственный тропический лес, чтобы провести перепись диких животных. Каждый раз, когда вы видите животное, вы делаете снимок. Ваша цифровая камера будет фиксировать общее количество снимков, но вас интересует только количество уникальных животных — всех тех, которых вы ещё не посчитали. Как лучше всего получить это число? «Очевидное решение — запомнить всех животных, которых вы уже видели, и сравнивать каждое новое животное с этим списком», — говорит Лэнс Фортноу, специалист по информатике из Иллинойского технологического института. Но есть и более умные способы, добавил он, потому что если у вас тысячи записей, то очевидный подход далеко не так прост.

Всё становится ещё хуже. Что, если вы — Facebook, и вам нужно подсчитать количество отдельных пользователей, которые заходят на сайт каждый день, даже если некоторые из них заходят с нескольких устройств и в разное время? Теперь мы сравниваем каждый новый вход со списком, который может исчисляться миллиардами.

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

В этой статье мы расскажем о том, как можно организовать обучение больших языковых моделей на кластере и какие проблемы при этом возникают. Рассмотрим альтернативные методы ZeRo и FSDP, которые помогают организовать этот процесс. И объясним, чем YaFSDP отличается от них.

Простые числа удивительны!

С одной стороны, их легко объяснить: это просто числа, которые делятся только на единицу и на себя; с другой стороны, они содержат в себе бесконечную сложность. Они встречаются во множестве разных сфер, от математических концепций и гипотез до любопытных визуализаций и криптографии, лежат в основе многих Интернет-стандартов и протоколов безопасности, которые мы используем ежедневно.

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

Вызов

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

Генерировать простые числа, способные генерировать ключи для алгоритма RSA

На момент написания этой статьи хорошей длиной ключей RSA считаются 2048 битов. Ключи RSA генерируются перемножением двух простых чисел, так что для получения 2048-битного ключа нам нужны два числа длиной примерно 1024 бита. Это ограничивает рамки задачи генерацией 1024-битных простых чисел. Теперь вы знаете, откуда взялось число из заголовка поста.

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

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

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

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

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

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

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

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

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

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

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