not magic neural networks

На янгконе довелось пообщаться Филиппом Ульянкиным, автором канала @ppilif_chanel Вспомнили пост с которого я на него подписалась. Почитайте, довольно интересный :) https://t.me/ppilif_chanel/560

Миллион лет не писал сюда, потому что was cooking, если интересно что, и вдруг по воле случая будете в Белграде 31 мая, приходите на data fest! Расскажу, как мы с командой в Яндексе учили 🤖 робота-доставщика ездить с помощью чистого tabula rasa RL (без imitation learning, как раз те самые тысячи лет в симуляции, что тут не было постов), а потом выкатились в прод на улицы городов России! Внутри будет много интересных моментов из практики, про эффективную архитектуру модели, оптимизацию симулятора и reward'а, и самих алгоритмов обучения, а также про детекцию и митигацию sim2real гапа и ускорение инференса. Да и вообще не одними LLM едины, даешь RL агентов в физический мир! Ну и конечно будет про не секси трюки, которые не напишут в статьях, но без которых ничего бы не заработало. Записаться можно тут: https://ods.ai/events/fest2026-fon-belgrade мой доклад будет в 13:30, а после конфы можно будет замитапиться лично и погудеть за rl, модели мира и e2e (которыми, кстати, занимаюсь сейчас, но об этом позже) ⚡️

Нелинейная регрессия Для нелинейных зависимостей существует нелинейная регрессия. Метод Ньютона–Рафсона обновляет веса по следующей формуле w = w - α * H⁻¹ * ∇L где H - гессиан функции потерь (L''), ∇L – градиент функции потерь (L'). Вместо того чтобы искать H⁻¹, можно сразу искать вектор z = H⁻¹ * ∇L как решение уравнения Hz = ∇L. Я попробовала реализовать данный метод, но он у меня очень плохо сходился. К тому же считать гессиан и обращать его на каждом шаге довольно затратно. Кароче есть немного лучше решение. Распишем гессиан квадратичной функции потерь: dL/dw_j dw_k = 2 sum (df/dw_k * df/dw_j) + 2 sum (f(x_i,w) - y) * d²f/dw_jdw_k Будем полагать, что в некоторой окрестности модель f(x) все таки похожа на линейную. Разложим f(x) в ряд Тейлора в окрестности точки w0 f(x_i, w) ≈ f(x_i, w0) + sum(j=1..p) (df(x_i,w_j)/dw_j)(w_j - w0_j) + o(w_j - w0_j) Членом меньшего порядка o(w_j - w0_j) пренебрегаем, то есть полагаем что ∂²f(x_i, w_j)/∂w_j ∂w_k = 0. Тогда от гессиана останется только dL/dw_j dw_k = 2 sum (df/dw_k * df/dw_j) Введем обозначение F = ( ∂f/∂w_j) - матрица n × p первых производных (ака Якобиан). Тогда формула обновления весов (Метод Ньютона–Гаусса): w = w - α * (Fᵀ F)⁻¹ Fᵀ (f(x, w) - y) Опять таки, вместо того чтобы искать обратную матрицу (Fᵀ F)⁻¹, можно искать сразу результат выражения (Fᵀ F)⁻¹ Fᵀ (f(x, w) - y) как решение СЛУ. Градиентные методы второго порядка сходятся быстрее (требуют меньшего числа итераций), однако каждая итерация стоит дороже. Такое решение контест скушал ❤️ Решение в комментах, а начало поста тут

Решала недавно такую задачку Дана зависимость f(x) = a * tg(x) + (b * sin(x) + c * cos(x))² + d * √x с неизвестными коэффициентами a,b,c,d. На вход подается n (от 10 до 1000) точек (x , f(x)). Нужно восстановить коэффициенты a,b,c,d. Сначала мне показалось, что задача полностью аналогична 206. Восстановление коэффициентов, которую я решала пару лет назад. Идея там была в том, что после раскрытия квадрата выражение становится линейным относительно коэффициентов. f(x) = a * tg(x) + b² * sin²(x) + c² * cos²(x) + 2bc * sin(x) * cos(x) + d * √x После этого можно рассматривать каждое слагаемое как отдельную фичу и решать задачу обычным МНК / линейной регрессией. features = np.column_stack([ np.tan(x), # a np.sin(x) ** 2, # b^2 np.sin(x) * np.cos(x), # 2bc np.cos(x) ** 2, # c^2 np.sqrt(x) # d ]) from sklearn.linear_model import LinearRegression linearModel = LinearRegression(fit_intercept=False) linearModel.fit(features, y) coeffs = linearModel.coef_ Остается аккуратно восстановить b и c. 1) b² ⩾ 0 и c²⩾0 2) Если 2bc < 0, то либо b < 0, либо c < 0. 3) f(x) не различает случаи (b>0, c>0) и (b<0, c<0). a, b2, bc, c2, d = coefs b = max(0, b2) ** 0.5 c = max(0, c2) ** 0.5 if bc < 0: b = -b Однако, решение падает с ошибкой WA. Тесткейс конечно же не достать (люблю контест 🤓). И даже на стресс-тесте его словить не удалось. Но полагаю что есть ситуации, когда b² < 0 или c² < 0, а ограничение max(0, b²) дает слишком большую ошибку.

Сейчас готовлюсь с собесу по NLP. Пользуюсь этим списком вопросов: 100 questions about NLP (@grokaem_seby). Обнаружила в @deep_learning_school_news очень клевые лекции по GPT: Лекция. GPT-модели - 1. Обучение без учителя и даныне в трансформере Лекция. GPT-модели - 2. На заре GPT. История создания GPT-1 Лекция. GPT - 2 Лекция. GPT-3 и Sparse Attention Лекция. Метрики и неожиданные навыки GPT-3 Лекция. Законы масштабирования LLM Лекция. Последствия релиза GPT - 2 Телеграм-канал автора лекций: https://t.me/seeallochnaya Восполнила пробелы, лекции прям огонь. Перекрывается большое количество вопросов и здорово что они объясняются в историческом контексте: мотивации новых методов или модификаций становятся логичными и легко запоминаются. 32. Как считаете attention? 33. Сложность attention? Сравните с сложностью в rnn? 34. Сравните RNN и attention? В каком случае будете использовать attention, а когда RNN? 36. Объясните маскирование в attention. 37. Какая размерность у матриц self-attention? 38. В чем разница между BERT и GPT в рамках подсчета attention? 39. Какая размерность у эмбединового слоя в трансформере? 42. Зачем в трансформерах PreNorm и PostNorm? 43. Объясните разницу между soft и hard (local/global) attention? 44. Объясните multihead attention. 45. Какие другие виды механизмов внимания вы знаете? На что направлены эти модификации? 46. На сколько усложнится self-attention при увеличении числа голов? 53. Объясните разницу между головами и слоями в трансформер моделях. 64. Какие виды токенайзеров вы знаете? Сравните их. 66. Чем обычные токены отличаются от специальных токенов? 68. Как обучается токенизатор? Объясните на примерах WordPiece и BPE. 70. Какой токенизатор используется в BERT, а какой в GPT?

Прикольная задачка с собеса по классическому ML Дано квадратное уравнение (например, 4x^2 - 5x + 1.5 = 0). Нужно написать код, который найдет любой корень методом градиентного спуска.

Можно угарнуть как грациозно бежит полугепард 😂 https://gymnasium.farama.org/environments/mujoco/half_cheetah/

Давно хотела написать разбор PPO. В итоге получился довольно плотный текст с кучей формул. Я хоть и старалась сделать материал максимально понятным, но PPO - больно сложный. Если что-то будет совсем не очевидным - пишите, буду править текст и добавлять пояснений. Честно говоря, публиковать было немного страшно. В прошлый раз, когда я подробно разбирала математику ALS в рексисах, меня закидали какашками, и пост пришлось удалить 🥺 Но хочется верить, что такие математические разборы всё равно нужны. https://habr.com/ru/articles/991622/

Найдите и объясните ошибку в коде 🤓

Написала еще один разбор задачи "Решающий пень". Из интересного - переход от квадратичной сложности к линейной, снова с префиксными суммами ❤️

[Начало поста -> https://t.me/notmagicneuralnetworks/347] Вот тут то и понадобилось дерево Фенвика 🧠 Идея такая, что будем хранить словарь {element: count}, где элементы отсортированы по возрастанию. Заведем массив префисных сумм prefix_sum, где будем хранить сумму count(ов) от нулевого до текущего элемента. Считаем числитель для y[k]. -> Количество элементов, которые строго меньше нашего текущего y[k] это less = prefix_sum[y[k]-1]. -> А количество равных элементов equal = prefix_sum[y[k]] - prefix_sum[y[k]-1] = prefix_sum[y[k]] - less -> Тогда числитель Numerator += less + 0.5 * equal. Заметим, что с каждым новым обработанным y[k] надо изменять массив префиксов (добавлять новый встреченный элемент). Это даст квадратичную сложность. Оптимизируем этот момент, заменив массив префиксов на дерево Фенвика. Итоговая сложность алгоритма будет O(n log n), где n - пробег по массиву меток, а log(n) - изменение элемента или поиск префикс суммы дерева Фенвика. Для интересующихся код залила на сайт: https://coderun.yandex.ru/problem/generalized-auc/analyses/4659

[Начало поста -> https://t.me/notmagicneuralnetworks/347] Зачем же вся эта хрень нужна 🚬 У меня сейчас проходят последние занятия со студентами, на которых я показывала где задачки по алгосам или ML можно порешать. И вспомнила как когда-то я пыталась реализовать обобщенный ROC-AUC, который вечно у меня падал по TL (насчитала 25 попыток). Со скрипом залетело достаточно простое решение с бин поиском по отсортированному y: def roc_auc(n, t, y): t, y = zip(*sorted([(t[i], y[i]) for i in range(n)])) y_sorted = sorted(y) Numerator, Denominator = 0, 0 i = n - 1 while i >= 0: j = i while j >= 0 and t[i] == t[j]: l = bisect.bisect_left(y_sorted, y[j]) y_sorted.pop(l) j -= 1 for k in range(j + 1, i + 1): l = bisect.bisect_left(y_sorted, y[k]) r = bisect.bisect(y_sorted, y[k]) Numerator += l + (r - l) / 2 Denominator += j + 1 i = j return Numerator/Denominator Слабое место тут удаление элемента y_sorted.pop(l), которое дает в худшем случае квадратичную сложность. И было очевидно, что надо думать что-то более оптимальное 😓

[Начало поста -> https://t.me/notmagicneuralnetworks/347] Как посчитать сумму подотрезка лучше объясню на примере. Допустим у нас есть массив a. Для наглядности посчитаем его массив префикс-сумм и дерево Фенвика. a = [1, 2, 3, 4, 5, 6, 7] prefix = [1, 3, 6, 10, 15, 21, 28] tree = [1, 3, 3, 10, 5, 11, 7] (можете поверить) Давайте найдем сумму от 5 до 6 элемента ([6, 7]). Заранее посчитаем ответ 6 + 7 = 13. Если бы мы пользовались префикснымы суммами, то res = prefix[6] - prefix[5-1] = 28 - 15 = 13 В случае дерева Фенвика мы пользуемся этой же формулой, только префиксы надо посчитать: res = prefix[6] - prefix[5-1] = ? + ? Если взглянуть на рисунок, то нам надо сложить такие индексы до 6-го включительно, чтобы все ячейки от 0 до 6 оказались закрашены. Это индексы 6, 5 и 3. Тогда чтобы найти prefix[6] надо сложить tree[6] + tree[5] + tree[3] = 7 + 11 + 10 = 28 Аналогично для prefix[5-1] = prefix[4] = tree[4] + tree[3] = 5 + 10 = 15. Сумма подотрезка: res = prefix[6] - prefix[5-1] = 28 - 15 = 13 Поиск следующего индекса дерева Фенвика считается по чуть более хитрой формуле i = (i & (i + 1)) - 1, где & - логическое умножение. То есть делается цикл: prefix_sum = 0 while i >= 0: prefix_sum += self.tree[i] i = (i & (i + 1)) - 1 Таким образом подсчет суммы будет за O(log(n)). 👍 Остается разобраться с изменением массива. По рисунку можно заметить, что изменение одного элемента в массиве влияет лишь на часть элементов в дереве. Например, если мы изменим первый элемент в массиве, то в дереве нам надо поменять элементы с индексами 0, 2, 3, 7, 15. Изменить их все надо на разницу между старым и новым значением элемента. Формула следующего индекса считается так: index = index | (index + 1), где | - это логическое сложение. delta = num - array[index] array[index] = num while index < n: tree[index] += delta index = index | (index + 1) Так изменение массива тоже занимает O(log(n)). #алгоритмы

Дерево Фенвика Положим у нас есть массив arr и мы хотим найти сумму его подотрезка arr[l:r+1] в массиве. "Решение 1": Сохраняем массив и делаем s = sum(arr[l:r+1]), что дает нам сложность O(n) в худшем случае. "Решение 2": Сохраняем массив префиксных сумм, где prefix[i] = prefix[i-1] + arr[i]. Тогда за O(1) находим сумму подотрезка s = prefix[r] - prefix[l-1]. Теперь немного усложним задачу: пусть элементы в массиве могут меняться. В "Решении 1" изменение массива нас не смущает, оно будет за O(1). Однако оно нам не нравится из-за подсчета суммы за O(n). В "Решении 2" нам придется изменить массив префиксных сумм и в худшем случае это будет O(n). Вот для таких случаев была предложена хитрая структура под названием "Дерево Фенвика". Формулу массива префиксных сумм можно переписать как сумму подотрезка у которого левая граница всегда ноль: prefix[i] = sum(arr[0:i+1]). Дерево Фенвика - это массив таких же сумм, но с бегающей левой границей. И бегает она по весьма интересной формуле: left = right & (right + 1), где & - логическое умножение. FenwickTree[right] = sum(arr[left:right+1]). Посмотрите на график. По осям находятся индексы массива, а закрашены элементы, которые попали в диапазон [l:r+1] (сумму которых надо посчитать). FenwickTree[0] = sum(arr[0:1]) FenwickTree[1] = sum(arr[0:2]) FenwickTree[2] = sum(arr[2:3]) FenwickTree[3] = sum(arr[0:4]) ... FenwickTree[15] = sum(arr[0:16]) #алгоритмы

Мне подарили вот такого Элмо 😊 Очень хороший подарок для датасатониста ❤️ https://t.me/notmagicneuralnetworks/195 https://t.me/notmagicneuralnetworks/197

🤩С наступившим новым годом любимые подписики! 🎅 Высоких вам метрик в жизни и на работе! Поменьше багов и побольше фичей! Вспоминая выступление Леши Гусакова, желаю вам всегда двигаться к глобальному оптимуму, а не застрявать в локальном 🦌 Спасибо большое, что читаете канал 🤗 Пожелаем ему ещё больше интересных и полезных постов и, конечно, экспоненциального роста 😁

Еще что-то забыла поделиться https://habr.com/ru/articles/979394/ Обложку сгенерировала в GPT, ностальгирующий критик очень круто получился ❤️

Первая лекция базового курса посвящена LRU Cache. Противная задачка с алго-собеседований 🦄 Пусть у нас есть кэш фиксированного размера. Когда поступают новые данные, мы сохраняем их в кэше. Если же кэш уже заполнен, то перед добавлением нового элемента необходимо удалить тот, которым НЕ пользовались дольше всего. После этого новый элемент можно безопасно записать. Так же, мы можем попросить вернуть элемент из кэша. Такая структура, собственно, и называется LRU Cache (Least Recently Used Cache). В задачке https://neetcode.io/problems/lru-cache/question?list=neetcode150 надо реализовать такую структуру со всеми операциями за O(1). И для этого вам понадобится двусвязный список.