Quantum One Technical: math, ML theory and algorithms

Нули появляются от множителей 10 = 2 * 5. Двоек в 100! больше, поэтому считаем пятерки: floor(100/5) + floor(100/25) = 20 + 4 = 24.

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

Для 100! числа, кратные 5, дают 20 пятерок: 5, 10, ..., 100. Но числа, кратные 25, дают дополнительную пятерку: 25, 50, 75, 100. Значит, ответ:

Обобщение для n!: складываем floor(n / 5), floor(n / 25), floor(n / 125) и так далее, пока степень 5 не превысит n.

Bagging усредняет независимые модели и снижает дисперсию, boosting последовательно исправляет ошибки и уменьшает смещение. p-value — вероятность не менее экстремальных данных при верной нулевой гипотезе, а Байес объединяет априорную вероятность и правдоподобие наблюдения.

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

p-value вычисляется в предположении, что нулевая гипотеза верна. Это не вероятность истинности самой гипотезы и не размер эффекта. Формула Байеса отвечает на другой вопрос: апостериорная вероятность пропорциональна априорной вероятности, умноженной на правдоподобие наблюдения. В прикладной задаче нужно явно назвать базовую частоту события, чувствительность и специфичность сигнала — иначе легко переоценить редкий положительный исход.

Задний - 50%. Среди 10 000 человек около 100 больны, и 99 из них имеют положительный результат теста; среди 9 900 здоровых людей возникает 99 ложных срабатываний, поэтому положительные результаты разделяют 99 больных против 99 здоровых.

Используйте теорему Байеса:

P(sick | positive) = P(positive | sick) P(sick) / P(positive).

Здесь P(sick) = 0,01, P(positive | sick) = 0,99 и P(positive | healthy) = 0,01. Знаменатель:

0,99 * 0,01 + 0,01 * 0,99 = 0,0099 + 0,0099 = 0,0198.

Числитель составляет 0,99 * 0,01 = 0,0099, поэтому задний - 0,0099 / 0,0198 = 0,5.

Интуитивная версия подсчета часто безопаснее в интервью. Из 10 000 человек 100 больны и 9 900 здоровы. Тест ловит около 99 больных людей и ложно показывает около 99 здоровых людей. Таким образом, положительный результат с одинаковой вероятностью будет истинным положительным или ложным положительным.

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

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

SHAP решает задачу интерпретации уже построенного предсказания: значение признака показывает, насколько он сдвинул результат относительно базового ожидания. Это локальное объяснение, а не доказательство причинности. Квантильная регрессия вместо среднего оценивает, например, медиану или 90-й процентиль через pinball loss. Она полезна, когда цена недооценки и переоценки различается или нужен интервал возможных исходов.

Сложность считают по числу операций и памяти в худшем или ожидаемом случае. Жадный алгоритм требует доказательства свойства выбора. Честный бит из смещённой монеты получают по схеме фон Неймана: HT даёт 0, TH даёт 1, HH и TT повторяют.

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

С неизвестно смещённой, но независимой монетой нельзя использовать один бросок. Два исхода HT и TH имеют одинаковую вероятность p(1-p). Поэтому HT можно объявить нулём, TH — единицей, а HH и TT отбросить и повторить пару. Метод остаётся честным при любом постоянном p между нулём и единицей, но ожидаемое число бросков резко растёт для сильно смещённой монеты. Важно отдельно назвать предположение о независимости бросков.