ML coding: пишем с нуля на собеседовании

Зачем это нужно

В уроке 11.3.1 вы видели этапы найма. Один из них — ML codingML coding (секция собеседования)EN ML coding interviewЭтап собеседования, где за 30–45 минут пишут кусок ML с нуля: softmax, attention, k-means, AUC. По-китайски такие задания называют «шоусы» — «разорвать руками», то есть написать без библиотек.: вам дают редактор и просят за 30–45 минут написать кусок машинного обучения с нуля. Обычно разрешён NumPy, иногда PyTorch без готовых слоёв. Задача звучит коротко: «напишите softmax», «реализуйте attention с причинной маской», «посчитайте AUC без sklearn». На теорию из уроков 11.3.2 и 11.3.3 это не похоже. Здесь проверяют, умеете ли вы превратить формулу в работающий код под давлением времени и чужого взгляда.

Хорошая новость: всё это вы уже писали. Устойчивый softmax — в уроке 1.3.2, логистическую регрессию — в ДЗ s2-hw01, k-means — в 2.3.2, attention — в 4.4.2, top-p — в 4.1.3, beam search — в 4.1.5, BPE — в 4.2.2 и ДЗ s4-hw01. Плохая новость: на собеседовании нет тестов, подсказок и второй попытки. Ошибка в оси или забытая маска, которую дома нашёл бы pytest, здесь становится вашей ошибкой на глазах интервьюера. Этот урок — про то, как писать такой код быстро, вслух и без типичных ловушек.

Что оценивает интервьюер

Конкретный формат у каждой компании свой: где-то код запускают, где-то читают глазами, где-то просят продолжить после первой версии («а теперь добавьте батч»). Но смотрят почти везде на одно и то же.

Что оценивают	Как это видно	Что делать вам
Понимание задачи	Какие вопросы вы задали до кода	Уточнить формы, оси, типы, крайние случаи
Корректность	Код работает на примере	Проверить на маленьком входе, посчитанном руками
Численная устойчивость	exp, log, деление на ноль	Вычесть максимум, log-sum-exp, eps
Векторизация и сложность	Циклы, лишние копии, $O(\cdot)$	Писать на массивах, назвать сложность по времени и памяти
Проверка себя	Тесты и инварианты	Сумма вероятностей = 1, формы, сравнение с перебором
Коммуникация	Слышно ли ход мысли	Говорить вслух, принимать подсказки

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

Пять шагов на 45 минут

flowchart LR
A["1. Уточнить<br/>вход и выход<br/>3–5 мин"] --> B["2. План вслух<br/>3–5 мин"]
B --> C["3. Простая версия<br/>15–20 мин"]
C --> D["4. Проверка на<br/>маленьком примере<br/>5 мин"]
D --> E["5. Сложность и<br/>крайние случаи<br/>5–10 мин"]
D -->|"нашли ошибку"| C
E -->|"осталось время"| F["Улучшение:<br/>батч, память,<br/>скорость"]

Порядок работы на секции ML coding. Шаг 4 почти всегда возвращает к шагу 3 хотя бы раз — это нормально

1. Уточнить вход и выход. Каких форм массивы? По какой оси считать? Есть ли батч? Логиты или вероятности? Метки — индексы или one-hot? Что вернуть: число, вектор, кортеж? Что делать с пустым входом? Вот так это звучит для задачи «напишите cross-entropy»:

• Кандидат: вход — логиты формы (N, C) и метки (N,) как индексы классов? Интервьюер: да.
• Кандидат: вернуть среднее по батчу? Интервьюер: да, но пусть можно получить и вектор потерь.
• Кандидат: логиты могут быть большими, например 10⁴? Интервьюер: могут.
• Кандидат: тогда считаю через log-sum-exp, а не через log(softmax), иначе получим log(0).

Последняя реплика — уже не вопрос, а сигнал интервьюеру: вы знаете, где здесь ловушка.

2. План вслух. Формула → шаги → формы после каждого шага. «Вычитаю максимум по строке, форма (N, 1). Считаю log-sum-exp, форма (N,). Беру логит верного класса через z[np.arange(N), t], форма (N,). Разность, среднее». Если план неверен, интервьюер часто поправит вас ещё до кода и сэкономит вам 10 минут.

3. Простая версия. Сначала корректность, потом скорость. Но «простая» на NumPy значит векторизованная: векторизациявекторизацияEN vectorizationЗамена циклов Python операциями над целыми массивами, которые выполняются в скомпилированном коде. — естественный способ писать такой код, а не оптимизация. Цикл по объектам выборки будет первым замечанием.

4. Проверка на маленьком примере. Посчитайте ответ руками и прогоните код в голове или в редакторе: cross_entropy([[2, 1, 0]], [0]) должен дать $\log(e^2 + e + 1) - 2 \approx 0.4076$. Добавьте инварианты: суммы вероятностей равны 1, формы совпадают, при равных логитах loss равен $\log C$.

5. Сложность и крайние случаи. Назовите сложность по временисложность алгоритма (O-нотация)EN time complexity, big-O notationКак растёт время работы с размером данных n. O(n) — пропорционально n (поиск в list), O(1) — не зависит от n (поиск в dict и set). и по памятисложность по памятиEN space complexityСколько дополнительной памяти нужно алгоритму в зависимости от размера входа. Перебор всех пар n объектов матрицей — O(n²) памяти: при n = 10⁶ это 10¹² ячеек., перечислите крайние случаи (пустой вход, один класс, −inf, огромные числа) и скажите, что бы вы улучшили, будь у вас ещё 15 минут.

Девять задач: главная ловушка и эталон

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

1. Устойчивый softmax и cross-entropy

Ловушка — численная устойчивостьчисленная устойчивостьEN numerical stabilityСвойство вычисления не терять точность и не переполняться на больших и малых числах. Пример: exp(1000) = inf, поэтому в softmax сначала вычитают максимум.. np.exp(1000) равно inf, и наивный softmax для логитов $[1000, 1001, 1002]$ возвращает nan (бесконечность, делённая на бесконечность). Вычитание максимума не меняет ответ: числитель и знаменатель умножаются на одно и то же $e^{-m}$. Зато все показатели становятся $\le 0$.

Cross-entropy считают сразу из логитов через приём log-sum-expприём log-sum-expEN log-sum-exp tricklog Σ exp(zᵢ) = m + log Σ exp(zᵢ − m), где m = max zᵢ. Все показатели ≤ 0, переполнения нет. На нём держатся устойчивые softmax и cross-entropy.: $\ell = \log \sum_j e^{z_j} - z_t = m + \log \sum_j e^{z_j - m} - z_t$. Вариант «softmax, потом log» ломается с другой стороны: для логитов $[800, 0]$ и верного класса 1 вероятность класса 1 округляется до нуля, и $-\log 0 = \infty$, хотя правильный ответ — ровно 800.

import numpy as np

def stable_softmax(x, axis=-1):
    e = np.exp(x - x.max(axis=axis, keepdims=True))   # keepdims: форма (N, 1) растянется обратно на (N, C)
    return e / e.sum(axis=axis, keepdims=True)

def cross_entropy(z, t):                              # z: (N, C) логиты, t: (N,) номера классов
    m = z.max(axis=1, keepdims=True)
    lse = m[:, 0] + np.log(np.exp(z - m).sum(axis=1))
    return (lse - z[np.arange(len(t)), t]).mean()

print(stable_softmax(np.array([1000.0, 1001.0, 1002.0])))       # [0.09003057 0.24472847 0.66524096]
print(cross_entropy(np.array([[2.0, 1.0, 0.0]]), np.array([0])))  # 0.4076059644443806

Частый дополнительный вопрос — «почему не np.log(softmax(z))?». Ответ — пример с $[800, 0]$ выше. Подробнее — в уроке 1.3.2.

2. Логистическая регрессия на градиентном спуске

Ядро — одна строка градиента: $\nabla_w = X^\top(p - y)/n + 2\lambda w$ (урок 2.2.2). Ловушек три. Первая — цикл по объектам вместо матричного умножения. Вторая — сигмоида 1 / (1 + np.exp(-z)): при $z = -1000$ она переполняется (ответ получится верный, 0, но с предупреждением, а в соседних формулах тот же inf превратится в nan). Устойчивый вариант: e = np.exp(-np.abs(z)), затем np.where(z >= 0, 1 / (1 + e), e / (1 + e)). Третья — L2-штраф на сдвиг $b$: обычно его не штрафуют. Проверка вслух: loss падает от шага к шагу, а веса совпадают с LogisticRegression из sklearn при $C = 1/(2n\lambda)$. Это соответствие ДЗ и проверяет.

3. k-means

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

• Инициализация k-means++инициализация k-means++EN k-means++ initializationПервый центр — случайная точка, каждый следующий — точка с вероятностью, пропорциональной квадрату расстояния до ближайшего выбранного центра. Центры расходятся по разным облакам, и Ллойд реже застревает в плохом минимуме.: следующая точка выбирается с вероятностью $\propto D^2$ — квадрату расстояния до ближайшего выбранного центра.
• Пустой кластер. Среднее пустого массива — nan, и он заражает всё дальше. Решение надо назвать вслух: оставить старый центр или перенести его в самую далёкую точку (так делает sklearn).
• Проверка сходимости. Стоп, когда метки не изменились. Главный инвариант — целевая функция k-meansметод k-средних (k-means)EN k-means (inertia, сумма квадратов расстояний до центров) не растёт ни на одной итерации. Выросла — в коде ошибка.

Память: расстояния через broadcasting (n, 1, d) − (1, k, d) создают тензор $n \cdot k \cdot d$. При $n = 10^6$, $k = 100$, $d = 768$ это 614 ГБ в float64. Формула $\lVert x \rVert^2 - 2x \cdot c + \lVert c \rVert^2$ даёт матрицу $n \times k$ — 800 МБ.

4. Attention с причинной маской

def causal_attention(x, Wq, Wk, Wv):                 # x: (T, d)
    q, k, v = x @ Wq, x @ Wk, x @ Wv
    scores = q @ k.T / np.sqrt(q.shape[-1])            # (T, T); без √d_k softmax «затвердеет»
    T = x.shape[0]
    allowed = np.tril(np.ones((T, T), dtype=bool))     # j ≤ i, диагональ разрешена
    scores = np.where(allowed, scores, -np.inf)
    w = stable_softmax(scores, axis=-1)                # по ключам — последняя ось
    return w @ v

Главная ловушка — причинная (каузальная) маскапричинная (каузальная) маскаEN causal maskЗапрещает токену смотреть на будущие позиции — оценки выше диагонали заменяются на −∞ до softmax. Нужна, чтобы GPT-подобная модель училась предсказывать следующий токен на всех позициях сразу.. np.triu(ones, k=1) как маска запрета верна, np.triu(ones, k=0) запрещает и диагональ. Тогда у позиции 0 не остаётся ни одного ключа, строка состоит из одних $-\infty$, и softmax даёт nan. Проверка за 10 секунд: выход позиции 0 обязан равняться $v_0$, потому что она видит только себя. Ещё один вопрос с подвохом — паддинг слева. Если ключ 0 — паддинг, у позиции 0 снова пустая строка, и её нужно явно занулить. Сложность $O(T^2 d)$ по времени и $O(T^2)$ по памяти: при $T = 32\,768$ матрица весов одной головы в float32 занимает 4.3 ГБ. Именно эту матрицу не хранит FlashAttention (урок 5.7.2).

5. LayerNorm

$y = (x - \mu)/\sqrt{\sigma^2 + \varepsilon} \cdot \gamma + \beta$ по последней оси (урок 3.4.1). Ловушки: не та ось (axis=0 — это уже BatchNorm), забытый keepdims=True, несмещённая дисперсия ddof=1 вместо смещённой и $\varepsilon$ вне корня. Есть и тонкая ловушка: дисперсия через $\mathbb{E}[x^2] - \mu^2$. Для $x = 10^8 + (1, 2, 3, 4)$ правильная дисперсия 1.25, а эта формула в float64 даёт 2.0. Квадраты порядка $10^{16}$ съедают младшие разряды. Двухпроходная формула ((x - mu) ** 2).mean(-1) даёт 1.25.

6. Top-k и top-p с температурой

Порядок как в Hugging Face (урок 4.1.3): разделить логиты на температурутемпература (сэмплирования)EN temperatureЛогиты делятся на T перед softmax. T < 1 — распределение острее, T > 1 — площе, T → 0 — greedy., затем top-ktop-k сэмплированиеEN top-k samplingСэмплирование только из k самых вероятных токенов (остальные получают вероятность 0)., затем top-ptop-p (ядерное) сэмплированиеEN top-p (nucleus) samplingСэмплирование из минимального набора самых вероятных токенов с суммарной вероятностью ≥ p. Holtzman et al., 2019., затем сэмплирование. Правило ядра: токен входит, если вероятностная масса до него меньше $p$. Поэтому самый вероятный токен входит всегда. Для логитов «Мама мыла …» накопленные вероятности равны 0.457, 0.662, 0.799, 0.901, и при $p = 0.9$ в ядре 4 токена. Дополнительные вопросы: что при $T = 0$ (жадный выбор, без деления на ноль), откуда случайность (передайте rng, не трогайте глобальный np.random, иначе результат не воспроизвести), сколько стоит шаг (сортировка $O(V \log V)$; для top-k хватает np.argpartition за $O(V)$).

7. Beam search

Гипотеза — пара «токены, сумма log-вероятностей». На каждом шаге каждую из $B$ живых гипотез продолжают каждым из $V$ токенов. Из всех $B \cdot V$ кандидатов оставляют $B$ лучших, гипотезы с EOS откладывают в законченные (урок 4.1.5). Ловушки: отбор лучших внутри каждой гипотезы вместо общего, забытые законченные гипотезы и отсутствие нормировки по длиненормировка по длине (в beam search)EN length normalizationДеление суммарной log-вероятности гипотезы на L^α, где L — её длина. Без этого beam search предпочитает короткие ответы: каждый новый токен умножает вероятность на число меньше единицы.. Без неё побеждают короткие ответы: гипотеза «сразу EOS» с вероятностью 0.5 (log = −0.69) обгоняет трёхтокенную с вероятностью 0.32 (log = −1.14). Со $\text{score} = \log P / L^{\alpha}$ при $\alpha = 1$ счёт меняется: $-1.14 / 3 = -0.38 > -0.69$. Сложность шага — $O(BV)$, если искать лучших через np.argpartition по матрице $B \times V$.

8. Шаг BPE

def bpe_merge_step(words):                    # {("н", "о", "с"): 5, …} — слово как кортеж токенов → частота
    counts = {}
    for word, freq in words.items():
        for pair in zip(word, word[1:]):      # пара внутри слова даёт +частоту слова
            counts[pair] = counts.get(pair, 0) + freq
    if not counts:
        return dict(words), None
    a, b = min(counts, key=lambda pr: (-counts[pr], pr))   # ничья → наименьшая пара
    new = {}
    for word, freq in words.items():
        out, i = [], 0
        while i < len(word):                  # слева направо, без перекрытий: (a, a, a) → (aa, a)
            if i + 1 < len(word) and (word[i], word[i + 1]) == (a, b):
                out.append(a + b); i += 2
            else:
                out.append(word[i]); i += 1
        new[tuple(out)] = new.get(tuple(out), 0) + freq
    return new, (a, b)

Ловушки: подсчёт без весов-частот, перекрывающиеся слияния и молчаливое правило ничьей. Правило ничьей лучше спросить: у разных реализаций оно своё. В уроке 4.2.2 и в minbpe берут пару, встреченную раньше, в ДЗ s4-hw01 — бóльшую, здесь — наименьшую. На классическом примере Sennrich (low ×5, lower ×2, newest ×6, widest ×3) пары (e, s), (s, t) и (t, </w>) встречаются по 9 раз, и первые три слияния с этим правилом — es, est, est</w>. Для BPEBPE, кодирование пар байтовEN Byte Pair Encoding (BPE)Алгоритм токенизации — многократно сливает самую частую пару соседних токенов в новый токен. Изначально (Gage, 1994) — алгоритм сжатия данных. на байтах всё то же самое, только токены — числа.

9. AUC без библиотек

По определению ROC-AUCROC-AUC (площадь под ROC-кривой)EN ROC AUC (area under the ROC curve)Вероятность того, что случайный положительный пример получит скор выше случайного отрицательного. — доля пар «положительный, отрицательный», где положительный получил скор выше; ничья даёт 1/2 (урок 2.2.3). Перебор пар стоит $O(n_+ n_-)$: при $10^6$ объектов поровну это $2.5 \cdot 10^{11}$ сравнений. Через сортировку выходит $O(n \log n)$:

def auc_rank(y, s):                                   # y: 0/1, s: скоры
    order = np.argsort(s)
    ss = s[order]
    new = np.r_[True, ss[1:] != ss[:-1]]               # начало группы одинаковых скоров
    starts = np.flatnonzero(new)
    ends = np.r_[starts[1:], len(s)]
    ranks = np.empty(len(s))
    ranks[order] = ((starts + 1 + ends) / 2)[np.cumsum(new) - 1]   # средний ранг группы
    n_pos = y.sum()
    return (ranks[y == 1].sum() - n_pos * (n_pos + 1) / 2) / (n_pos * (len(y) - n_pos))

Ловушка — ничьи. Без средних рангов пример $y = [1, 0, 1, 0]$, $s = [0.8, 0.8, 0.3, 0.1]$ даст 0.5 или 0.75 в зависимости от порядка сортировки, а правильный ответ — $(0.5 + 1 + 0 + 1)/4 = 0.625$. Второй вопрос: если в данных один класс, AUC не определён, и честный ответ — исключение, а не 0.5.

Частые ошибки

Ошибка	Как выглядит	Как поймать за минуту
Численная неустойчивость	nan или inf на больших логитах	Прогнать $[1000, 1001]$ и $[800, 0]$
Не та ось	softmax нормирует батч, а не классы	Проверить p.sum(axis=-1) — должны быть единицы
Broadcasting $(n, 1)$ и $(n,)$	y - p молча становится матрицей $n \times n$	Печатать .shape после каждой строки
Забыли маску	Модель «видит будущее», loss подозрительно низкий	Изменить последний токен — выход позиции 0 не должен измениться
Маска на диагонали	nan в первой строке	Проверить, что out[0] = v[0]
$O(n^2)$ там, где можно $O(n \log n)$	AUC через пары, циклы по точкам	Оценить вслух: сколько это при $n = 10^6$?
Изменили вход	x -= x.max() меняет массив вызывающего	Писать x = x - … или копировать
Глобальный генератор	np.random.seed внутри функции, результат не воспроизвести	Принимать rng аргументом

Ошибка с broadcasting самая коварная: код не падает. Если метки пришли столбцом (n, 1), а вероятности — вектором (n,), то p - y даёт матрицу $n \times n$, градиент «считается», loss даже немного падает. Привычка проговаривать форму после каждой строки ловит это сразу.

Как проверить себя за две минуты

1. Пример руками. Два-три числа, ответ посчитан до запуска: softmax([1, 2, 3]) ≈ [0.090, 0.245, 0.665], AUC десяти страниц из урока 2.2.3 — 0.875.
2. Инварианты. Суммы вероятностей — единицы. Inertia в k-means не растёт. Веса attention над диагональю — нули. Формы выхода — те, что вы обещали на шаге 1.
3. Сравнение с перебором. Быстрый AUC сверьте с перебором пар на 20 объектах. Beam search с очень широким лучом сверьте с полным перебором последовательностей.
4. Крайние случаи. Пустой вход, один элемент, все значения равны, $-\infty$, огромные числа, один класс.

Тот же список стоит проговорить вслух после того, как код заработал. Это и есть шаг 5.

Практика

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

Задача 1. Top-p сэмплирование. Таймер: 20 минут.

Top-p сэмплирование с температуройnumpy · нужен интернет6 тестов

import numpy as np

# Задача с собеседования (таймер: 20 минут, вслух, без подсказок).
# «Напишите top-p сэмплирование с температурой. На вход — логиты одного шага, на выход — номер токена».
# Прежде чем писать код, ответьте себе: что будет при temperature = 0? при p = 1? если часть логитов −inf?


def nucleus(probs, p):
    """Ядро top-p: номера токенов в порядке убывания вероятности, пока не набрана масса p.

    probs — np.ndarray (V,), сумма 1. Порядок: np.argsort(-probs, kind="stable")
    (при равных вероятностях меньший номер раньше). Токен входит в ядро, если масса ДО него < p,
    поэтому самый вероятный токен входит всегда.
    Пример: probs = [0.5, 0.3, 0.2], p = 0.6 → [0, 1] (до токена 1 масса 0.5 < 0.6, до токена 2 — 0.8).
    Возвращает np.ndarray номеров.
    """
    # TODO: order; накопленная сумма; маска «масса до токена < p»
    ...


def sample_top_p(logits, p, temperature, rng):
    """Один токен: temperature ≤ 0 → argmax; иначе softmax(logits / T) → ядро → случайный выбор.

    Выбор — rng.choice(ядро, p=перенормированные вероятности ядра). rng — np.random.Generator;
    глобальный np.random не используйте. Логиты −inf допустимы: такие токены не выпадают никогда.
    Возвращает int.
    """
    # TODO: ваш код (не забудьте вычесть максимум перед exp)
    ...


# «Мама мыла …»: раму, посуду, окно, пол, кота, машину, руки, Пекин
LOGITS = np.array([3.0, 2.2, 1.8, 1.5, 0.5, 0.3, 0.2, -2.0])
probs = np.exp(LOGITS - LOGITS.max())
probs /= probs.sum()
print("вероятности:", np.round(probs, 3))
print("ядро при p=0.9:", nucleus(probs, 0.9))        # ожидается [0 1 2 3]
rng = np.random.default_rng(0)
print("10 сэмплов:", [sample_top_p(LOGITS, 0.9, 1.0, rng) for _ in range(10)])

ЗапуститьПроверитьПодсказкаСбросить

Задача 2. AUC без sklearn. Таймер: 25 минут.

ROC-AUC: перебор пар и рангиnumpy · нужен интернет6 тестов

import numpy as np

# Задача с собеседования (таймер: 25 минут, вслух, без подсказок).
# «Посчитайте ROC-AUC без sklearn. Сначала простым способом, потом — за O(n log n)».
# Уточните у «интервьюера»: что делать с одинаковыми скорами? а если в данных один класс?


def auc_pairs(y_true, y_score):
    """AUC по определению: доля пар (положительный, отрицательный), где скор положительного выше.

    Пара с равными скорами даёт 1/2. Сложность O(n_pos · n_neg) — для проверки на малых данных.
    Если в y_true только один класс — raise ValueError.
    Пример: y = [1, 0, 1, 0], s = [0.8, 0.8, 0.3, 0.1] → (0.5 + 1 + 0 + 1) / 4 = 0.625.
    """
    # TODO: pos = s[y == 1], neg = s[y == 0]; сравните все пары сразу через broadcasting
    ...


def auc_rank(y_true, y_score):
    """Тот же AUC за O(n log n) через ранги (формула Манна — Уитни).

    Отсортируйте скоры; ранг — место в сортировке с 1; у одинаковых скоров — СРЕДНИЙ ранг группы.
    AUC = (сумма рангов положительных − n_pos·(n_pos + 1)/2) / (n_pos · n_neg).
    Если в y_true только один класс — raise ValueError.
    """
    # TODO: ваш код
    ...


# Пример из урока 2.2.3: 10 страниц, 4 «математические»
s = np.array([0.95, 0.80, 0.70, 0.60, 0.45, 0.35, 0.30, 0.20, 0.10, 0.05])
y = np.array([1, 1, 0, 1, 0, 1, 0, 0, 0, 0])
print("пары:", auc_pairs(y, s), " ранги:", auc_rank(y, s))   # ожидается 0.875 и 0.875

ЗапуститьПроверитьПодсказкаСбросить

Задача 3. k-means с проверкой сходимости. Таймер: 30 минут.

k-means++ и проверка сходимостиnumpy · нужен интернет5 тестов

import numpy as np

# Задача с собеседования (таймер: 30 минут, вслух, без подсказок).
# «Реализуйте k-means с инициализацией k-means++ и проверкой сходимости. Как убедиться, что он сошёлся?»
# Подумайте заранее: что делать с пустым кластером? какое число не должно расти от итерации к итерации?


def kmeans_pp_init(X, k, rng):
    """k-means++: первый центр — X[rng.integers(n)]; каждый следующий — точка X[i], выбранная
    с вероятностью ∝ D(i)², где D(i) — расстояние до ближайшего уже выбранного центра
    (rng.choice(n, p=D2 / D2.sum())). Возвращает np.ndarray (k, d) — копии точек X.
    """
    # TODO: ваш код
    ...


def kmeans(X, k, seed=0, max_iter=100, tol=1e-6, init=None):
    """Алгоритм Ллойда. Возвращает (centers (k, d), labels (n,), history).

    init — готовые начальные центры (k, d) или None (тогда k-means++ с rng = np.random.default_rng(seed)).
    Перед циклом точки назначаются начальным центрам. Одна итерация:
      1) центр j = среднее точек с меткой j; ПУСТОЙ кластер: центр переезжает в точку, которая дальше всех
         от центра своего кластера (если пустых несколько — по порядку номеров, точки по убыванию расстояния);
      2) новое назначение: метка = номер ближайшего центра;
      3) history.append(inertia) — сумма квадратов расстояний точек до их центров ПОСЛЕ шага 2;
      4) стоп, если метки не изменились или максимальный сдвиг центра ≤ tol.
    len(history) = число выполненных итераций (не больше max_iter).
    """
    # TODO: ваш код
    ...


# «Запустить»: три облака точек
rng = np.random.default_rng(0)
X = np.vstack([c + rng.normal(size=(50, 2)) for c in ([0, 0], [8, 0], [0, 8])])
result = kmeans(X, 3)
if result is not None:
    C, labels, history = result
    print("центры:\n", np.round(C, 2))
    print("inertia по итерациям:", np.round(history, 1))

ЗапуститьПроверитьПодсказкаСбросить

Домашняя работа

s11-hw05-ml-coding — «Тренажёр ML coding: 10 функций с нуля» (ко всему модулю 11.3). На чистом NumPy: stable_softmax, cross_entropy, логистическая регрессия (fit и predict), kmeans, causal_self_attention, layer_norm, sample_top_p, beam_search, bpe_merge_step, roc_auc. Тесты сверяют ответы с torch.nn.functional и sklearn, ручными примерами и полным перебором. Simple — softmax, cross-entropy, LayerNorm, AUC; Medium — плюс attention, top-p и логистическая регрессия; Strong — плюс k-means, beam search, BPE и краевые случаи (огромные логиты, одинаковые скоры, пустой кластер, маска первой позиции); Boss — векторизация на больших входах с проверкой по времени.

Решайте каждую функцию как на собеседовании: таймер на 20–30 минут, вслух, без подсказок и ИИ. Сначала пример руками, потом тесты. Через неделю решите заново те функции, на которых не уложились.

python homework/check.py s11-hw05-ml-coding

🖥 На вашей машине (4×GPU)

Интервьюера можно поднять локально. Одной RTX 4080 хватает для Qwen/Qwen3-8B в vLLM (около 16 ГБ весов в bf16, остальное уйдёт под KV-кэш):

CUDA_VISIBLE_DEVICES=0 vllm serve Qwen/Qwen3-8B --max-model-len 16384 --port 8000
python homework/review.py s11-hw05-ml-coding --api http://localhost:8000/v1 --model Qwen/Qwen3-8B

Первая команда поднимает сервер, вторая отправляет ему ваш код и вывод автогрейдера на ревью по рубрике из README. Для тренировки диалога попросите модель в чате сыграть интервьюера: дать задачу из списка урока, через 25 минут задать два вопроса о крайних случаях и оценить ответ. 8B-модель неплохо ведёт разговор, но в оценке чужого кода ошибается чаще больших моделей, поэтому вердикт проверяйте тестами. Тесты ДЗ идут на CPU около 10 секунд, GPU им не нужен. Подробнее о машине — на странице «Ваша лаборатория».

Китайский угол: «шоусы» и открытые сборники вопросов

В китайском IT задание «напишите с нуля, без библиотек» называют «шоусы» (буквально «разорвать руками»): «шоусы» кода, «шоусы» attention, «шоусы» BPE. Рядом живёт слово «багу» («восьмичленное сочинение» старых императорских экзаменов) — так называют заученные стандартные ответы на теоретические вопросы.

Открытые сборники вопросов к собеседованиям по LLM лежат на GitHub. Их удобно использовать как банк задач для тренировки в этом уроке:

• LLMs_interview_notes «Тысячеликий знаток LLM» — вопросы по темам, в том числе ровно наши задачи (в переводе): «BPE с нуля», «Выпишите формулу LayerNorm», «Выпишите функцию потерь cross-entropy. В чём её физический смысл?». Часть ответов вынесена по внешним ссылкам, поэтому сборник лучше использовать как список вопросов.
• llm_interview_note — конспекты с разделом «Реальные вопросы с собеседований» и отдельной страницей «Стратегии декодирования (Top-k & Top-p & Temperature)». Тот же автор ведёт сборник «Знания для AI-инженера и вопросы собеседований» (ai_interview_note) по глубокому обучению, классическому ML, рекомендательным и поисковым системам.
• llm-algo-leetcode от Datawhale — задачи в формате «условие → поле для решения → тесты»: от PyTorch до Triton и CUDA, инференс, квантование, параллелизм. Это тот же формат, что у ДЗ s11-hw05, только глубже в системную часть.

Ответы в таких сборниках пишут энтузиасты, и они бывают неточными. Решение из сборника прогоняйте через тесты так же, как своё. Термины. Численная устойчивость по-китайски называется дословно, а beam search — буквально «поиск пучком», как и в английском.

Проверь себя

Проверь себя6 вопросов·

1 Что вернёт наивный softmax np.exp(x) / np.exp(x).sum() для x = [1000, 1001, 1002] в float64?

Правильный ответ [0.090, 0.245, 0.665]Массив nan: exp(1000) = inf, а inf / inf не определеноИсключение OverflowError, и программа остановитсяМассив нулей

2 Вы пишете причинное attention. Какая булева матрица «можно смотреть» верна для позиции $i$, которая видит позиции $j \le i$?

np.tril(np.ones((T, T), dtype=bool))np.triu(np.ones((T, T), dtype=bool), k=0)~np.triu(np.ones((T, T), dtype=bool), k=0)np.triu(np.ones((T, T), dtype=bool), k=1)

3 Посчитайте ROC-AUC для меток $y = [1, 0, 1, 0]$ и скоров $s = [0.8, 0.8, 0.3, 0.1]$ (ничья в паре — 1/2).

4 Вам дали задачу «напишите LayerNorm». Какие уточняющие вопросы стоит задать до кода?Можно выбрать несколько ответов

По какой оси нормировать (обычно последней) и есть ли батчЕсть ли обучаемые γ и β и какой формыКакое ε и где оно стоит — под корнем или внеКакой IDE пользуется команда

5 Метки пришли столбцом y.shape == (n, 1), вероятности — вектором p.shape == (n,). Какой формы будет p - y?

(n,)(n, 1)(n, n) — молча, без ошибкиБудет ошибка broadcasting

6 Beam search нашёл две законченные гипотезы: «сразу EOS» с вероятностью 0.5 (длина 1) и трёхтокенную с вероятностью 0.32 (длина 3, EOS включён). Чему равен score второй при $\alpha = 1$, если $\text{score} = \log P / L^{\alpha}$? Округлите до двух знаков.

Проверить ответы

Итоги

• Секция ML coding проверяет не память, а процесс: уточнить вход и выход, проговорить план, написать простую векторизованную версию, проверить на маленьком примере, обсудить сложность и крайние случаи.
• У каждой из девяти типичных задач есть одна главная ловушка: переполнение в softmax, сигмоида и L2 на сдвиге в логистической регрессии, пустой кластер в k-means, маска на диагонали в attention, ось и формула дисперсии в LayerNorm, правило ядра в top-p, нормировка по длине в beam search, правило ничьей в BPE, ничьи и $O(n^2)$ в AUC.
• Самые частые общие ошибки — не та ось, тихий broadcasting $(n, 1)$ и $(n,)$, изменение входа на месте и глобальный генератор случайных чисел.
• Тренироваться нужно в условиях собеседования: с таймером, вслух, без подсказок. Для этого есть три задачи урока и ДЗ s11-hw05-ml-coding.

Дальше: урок 11.3.5 — алгоритмическая секция. Рабочий минимум ML-инженера: сложность $O(\cdot)$, хэш-таблицы, два указателя и скользящее окно, куча для top-k, графы и простое динамическое программирование.