Revolut: Техническое собеседование

По теореме Байеса нужно разделить долю истинно положительных результатов на долю всех положительных результатов, включая ложноположительные среди здоровых людей.

Обозначим D — человек болен, а + — тест положительный. Если P(D)=0,01, чувствительность P(+|D)=0,95, а доля ложноположительных результатов P(+|не D)=0,05, то:

P(D|+) = P(+|D)P(D) / (P(+|D)P(D) + P(+|¬D)P(¬D)).

После подстановки получаем 0,95 * 0,01 / (0,95 * 0,01 + 0,05 * 0,99), то есть около 16,1%. Результат кажется низким из-за малой базовой частоты заболевания: здоровых людей намного больше, поэтому даже небольшая доля ошибок создаёт много ложноположительных результатов.

Типичная ошибка — принять чувствительность 95% за искомую вероятность P(D|+) или забыть учесть распространённость заболевания. На собеседовании важно уточнить, что именно означает «5% ошибок»: долю ложноположительных результатов, долю ложноотрицательных результатов или общую долю ошибок.

Полнота равна TP / (TP + FN), а точность — TP / (TP + FP). Для диагностического теста полнота совпадает с чувствительностью, а точность равна P(болен | тест положительный).

Полнота отвечает на вопрос: какую долю действительно положительных объектов нашла модель. Формула: TP / (TP + FN). Если чувствительность диагностического теста равна 95%, то полнота для класса заболевших тоже равна 95%.

Точность отвечает на вопрос: какая доля положительных предсказаний действительно положительна. Формула: TP / (TP + FP). Для редкого заболевания это не 95%, а P(болен | тест положительный), которую считают по теореме Байеса. При распространённости 1%, чувствительности 95% и доле ложноположительных результатов 5% точность составляет около 16,1%.

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

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

Минимальный размер выборки для A/B-теста конверсии зависит от нескольких величин. Во-первых, от базовой конверсии: дисперсия бернуллиевской случайной величины равна p(1-p), поэтому для разных p потребуются разные размеры выборки. Во-вторых, от минимального обнаружимого эффекта: чем меньше изменение мы хотим заметить, тем больше наблюдений потребуется.

Также важны уровень значимости alpha и статистическая мощность 1-beta. Более строгий уровень значимости снижает вероятность ложноположительного вывода и увеличивает размер выборки. Более высокая мощность снижает вероятность пропустить существующий эффект и тоже требует больше данных. Если группы распределены не поровну, общий размер выборки обычно растёт.

На собеседовании достаточно назвать эти составляющие и объяснить направление их влияния. В приближении z-теста для двух долей размер выборки пропорционален дисперсии и (z_alpha + z_beta)^2 и обратно пропорционален квадрату минимального обнаружимого эффекта.

Правдоподобие равно p^H(1-p)^T, а его логарифм — H log p + T log(1-p). Из равенства производной нулю получаем p_hat = H/(H+T), а отрицательная вторая производная подтверждает максимум.

Для независимых испытаний Бернулли правдоподобие равно L(p)=p^H(1-p)^T. Удобнее максимизировать его логарифм: l(p)=H log p + T log(1-p). Производная равна H/p - T/(1-p). Приравняем её к нулю:

H/p = T/(1-p) => H(1-p)=Tp => H = p(H+T) => p_hat = H/(H+T).

Вторая производная равна -H/p^2 - T/(1-p)^2 и отрицательна при 0 < p < 1. Следовательно, логарифм правдоподобия вогнут, а найденная стационарная точка является глобальным максимумом. Если наблюдались только орлы или только решки, максимум достигается на границе: p=1 или p=0.

Метод наименьших квадратов минимизирует сумму квадратов остатков и даёт решение (X^T X)^-1 X^T y, если X^T X обратима. При независимых нормально распределённых ошибках с нулевым средним оценка максимального правдоподобия совпадает с этим решением.

Линейная регрессия задаёт прогноз y_hat = Xw + b; свободный член обычно включают в X как столбец единиц. Метод наименьших квадратов выбирает параметры, минимизирующие ||y - Xw||^2. Приравнивая производную к нулю, получаем нормальные уравнения X^T X w = X^T y. Если X^T X обратима, то w = (X^T X)^-1 X^T y.

Аналитическое решение через обратную матрицу недоступно или неустойчиво, когда признаки линейно зависимы, матрица X^T X вырождена или плохо обусловлена. На практике используют псевдообратную матрицу, QR- или SVD-разложение, гребневую регуляризацию либо итерационные методы оптимизации.

Метод максимального правдоподобия приводит к той же целевой функции, если остатки независимы, одинаково распределены и имеют нормальное распределение с нулевым средним и постоянной дисперсией: y_i = x_i^T w + eps_i, eps_i ~ N(0, sigma^2). Максимизация произведения нормальных плотностей эквивалентна минимизации суммы квадратов остатков. При гетероскедастичных, зависимых или ненормальных ошибках метод наименьших квадратов всё ещё применим, но вероятностная модель и оценки неопределённости изменятся.

Смещение — систематическая ошибка из-за ограничений модели, а разброс — чувствительность результата к обучающей выборке. Недообучение и переобучение являются наблюдаемыми проявлениями, а разложение ошибки объясняет устойчивость модели и ожидаемую ошибку.

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

Недообучение часто связано с высоким смещением, а переобучение — с высоким разбросом. Но эти понятия шире: модель может одновременно иметь высокие смещение и разброс, если она неверно задана и неустойчива. Хорошая модель должна удерживать оба компонента ошибки на приемлемом уровне. Низкая ошибка на обучающей выборке сама по себе не доказывает устойчивость модели.

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