Во многих раундах собеседований по ML кандидатов просят продемонстрировать свои навыки кодирования. некоторые из распространенных и основных проблем машинного обучения. Такие раунды помогают определить как навыки кодирования, так и навыки машинного обучения, необходимые для того, чтобы стать первоклассным инженером машинного обучения в некоторых ведущих компаниях.
Давайте рассмотрим некоторые из распространенных проблем кодирования ML, которые задают в таких интервью:
Проблема 1:
Учитывая API rand7(), который генерирует однородное случайное целое число в диапазоне [1, 7], напишите функцию rand10(), которая генерирует однородное случайное целое число в диапазоне [1, 10]. Вы можете вызывать только API rand7(), и вам не следует вызывать какой-либо другой API. Пожалуйста, не используйте встроенный в язык случайный API.
Решение:
rand7()-1 генерирует случайное целое число от 0 до 6.
Чтобы сгенерировать случайные целые числа между [1, 10], нам нужно сгенерировать 10 равновероятных чисел или диапазон, который делится на 10 частей.
Пусть a=rand7()-1 и b= rand7(), тогда 7a+b будет генерировать случайные целые числа между [1, 49] каждое с равной вероятностью 1/49.
Если значение 7a+b находится в диапазоне [1,40], то мы можем использовать этот диапазон, чтобы поровну разделить на 10 частей размера 4, как показано ниже:
[1,4] [5,8] [9,12] [13,16] [17,20] [21,24] [25,28] [29,32] [33,36] [37,40]
Таким образом, если значение 7a+b находится между [1,4], мы возвращаем 1, если значение находится между [5,8], возвращаем 2 и так далее.
Таким образом, верните int((7a+b-1)/4)+1, если 1 ≤ 7a+b ≤ 40.
Вероятность того, что цикл while возвращает значение при каждом вызове, составляет 40/49, потому что из 49 возможных вариантов 7a+b только 40 допустимы. Таким образом, ожидаемое количество повторений цикла while для каждого вызова составляет 49/40.
Для произвольного диапазона [a, b] с помощью rand7() сначала нормализуйте диапазон до [1, b-a+1], затем найдите наименьшее P, такое что b-a+1 ≤ 7^P. Затем найдите наибольшее K такое, что K*(b-a+1) ≤ 7^P.
Пусть Q = 7^(P-1)*(rand7()-1) + 7^(P-2)*(rand7()-1) + … + 7*(rand7()-1) + rand7()
Q генерирует целые числа в диапазоне [1, 7^P].
Рассмотрим только диапазон [1, K*(b-a+1)] из значений Q. Среди этого диапазона, если мы разделим его на b-a+1 равных частей размера K каждая, то для любого целого числа в 1-я часть, т.е. [1, K], мы возвращаем 1, для 2-й части [K+1, 2K] возвращаем 2 и так далее.
Таким образом, int((Q-1)/K)+1 вернет случайное целое число в диапазоне [1, b-a+1]. Чтобы вернуться в диапазоне [a, b], добавьте к выходным данным a-1, т. е. a+int((Q-1)/K).
Ожидаемое количество раз выполнения цикла равно 7^P/K*(b-a+1).
Проблема 2:
Вам дан индексированный 0 массив положительных целых чисел w, где w[i]описывает вес индекса ith.
Вам нужно реализовать функцию pickIndex(), которая случайно выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w).
Решение:
Сохраните совокупные суммы весов до индекса i для каждого индекса i в массиве. Сгенерируйте случайное целое число M из диапазона [1, sum(w)].
Найдите наименьший индекс j, такой что cum_sum[j] ≥ M. Верните j.
Поскольку массив кумулятивных сумм представляет собой отсортированный массив, мы можем выполнить бинарный поиск, чтобы найти индекс j s.t. M ≤ cum_sum[j].
Временная сложность составляет O(logN) для каждого вызова pickIndex().
Эта проблема имеет очень широкое применение, например:
- Случайный выбор сервера балансировщиком нагрузки на основе отрицательного значения текущей нагрузки в качестве весов.
- Случайная выборка данных из дискретного распределения вероятностей.
- Генерация искусственных данных для имитации трафика.
Проблема 3:
Вам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм для выбора случайного целого числа в диапазоне [0, n - 1], которое не находится в диапазоне blacklist. Любое целое число, которое находится в указанном диапазоне, но не в blacklist, должно быть возвращено равновероятно.
Оптимизируйте свой алгоритм так, чтобы он сводил к минимуму количество вызовов встроенной случайной функции вашего языка.
Решение:
Отсортируйте целые числа в черном списке.
Затем сгенерируйте интервалы вида [черный список[i-1]+1, черный список[i]-1], т. е. разделите весь диапазон целых чисел таким образом, чтобы исключить целые числа из черного списка
Например, если диапазон целых чисел — [1, 100], а отсортированные целые числа из черного списка — [10, 25, 40, 90], то сгенерированные диапазоны — [1,9] [11,24] [26,39], [41,89] [91,100].
Затем на основе размера каждого диапазона выберите диапазон с вероятностью = размер диапазона/сумма размеров всех диапазонов.
Это можно сделать, используя алгоритм, представленный в задаче 2.
После выбора диапазона случайным образом выберите целое число в этом диапазоне.
Вероятность выбора числа = Вероятность выбора диапазона * Вероятность выбора числа в этом диапазоне.
Если размер диапазона равен S, то вероятность = S/сумма(размер диапазонов)*1/S = 1/сумма(размер диапазонов)
Поскольку сумма (размер диапазонов) = N-len(черный список), то каждое число, не входящее в черный список, выбирается единообразно.
Проблема 4:
Дан методbiad_toss(), который генерирует 0 или 1. Он генерирует 1 с некоторой вероятностью p (не обязательно 0,5). Напишите метод, который генерирует 0 или 1 с вероятностью 0,5.
Решение:
Если мы дважды вызовем методbiad_toss(), то возможны 00, 01, 10, 11. Вероятность 00 равна (1-p)², 01 равна (1-p)*p, 10 равна p*(1- р), а 11 — это р².
Поскольку вероятности 01 и 10 равны, то есть p*(1-p), мы можем вернуть 0, если получим 01, и 1, если получим 10.
Ожидаемое количество раз выполнения цикла: 1/p*(1-p).
Проблема 5:
Дан бесконечный поток чисел. Напишите метод, возвращающий K случайных отсчетов из потока без замены.
Решение:
Это можно решить с помощью отбора проб из резервуара.
Для каждого числа в потоке мы отслеживаем его индекс.
Если размер выборочного массива меньше K, добавьте число в конец массива.
Если размер выборочного массива более чем равен K, то генерируется случайное целое число между 0 и текущим индексом числа в потоке. Если случайное целое число находится в диапазоне от 0 до K-1, то замените индекс в массиве, соответствующий случайному целому числу, на текущее число.
Нам нужно доказать, что вероятность каждого числа в потоке оказаться в выборке равна K/N, где K — длина массива выборок, а N — длина потока.
Предположим, что длина потока равна N.
Для чисел с индексом ‹ K оно является частью выборки, если оно не заменено каким-либо числом с индексом ≥ K.
Вероятность того, что число с индексом J ‹ K является частью выборки = Вероятность того, что случайное целое число, сгенерированное с индексом K, не равно J и Вероятность того, что случайное целое число, сгенерированное с индексом K+1, не равно J и … Вероятность того, что случайное целое число сгенерировано с индекс N-1 не равен J.
Вероятность того, что случайное целое число, сгенерированное с индексом K, не равно J = K/K+1
Вероятность того, что случайное целое число, сгенерированное с индексом K+1, не равно J = K+1/K+2
Вероятность того, что случайное целое число, сгенерированное с индексом N-1, не равно J = N-1/N
Таким образом
Вероятность того, что число с индексом J ‹ K является частью выборки = K/(K+1)*(K+1)/(K+2)*…*(N-1)/N=K/N.
Для чисел с индексом J ≥ K он является частью выборки, если случайное целое число X, сгенерированное между 0 и J, равно ‹ K, а случайное целое число, сгенерированное с индексом › J, не равно X.
Вероятность того, что число с индексом J ≥ K является частью выборки = Вероятность того, что случайное целое число X, сгенерированное между 0 и J, равно ‹ K, и Вероятность того, что случайное целое число, сгенерированное с индексом J+1, не равно X, и Вероятность того, что случайное целое число сгенерировано с индексом J+2 не равно X и … Вероятность того, что случайное число, сгенерированное по индексу N-1, не равно X.
Вероятность того, что случайное целое число X сгенерировано между 0 и J, равна ‹ K = K/(J+1)
Вероятность того, что случайное целое число, сгенерированное с индексом J+1, не равно X = J+1/(J+2)
Вероятность того, что случайное целое число, сгенерированное с индексом J+2, не равно X = J+2/(J+3)
Вероятность того, что случайное целое число, сгенерированное с индексом N-1, не равно X = N-1/N
Таким образом
Вероятность того, что число с индексом J ≥ K является частью выборки = K/(J+1)*(J+1)/(J+2)*(J+2)/(J+3)*…*(N- 1)/Н=К/Н.
Проблема 6:
Случайным образом перемешать массив.
Решение:
Произвольно выберите индекс j от i до Len(arr)-1. Затем поменяйте местами arr[j] на arr[i] и увеличьте i на 1.
Проблема 7:
Подбрасывайте правильную монету несколько раз, пока не выпадет две решки подряд (ЧЧ). Какова вероятность выпадения HH не более чем за N (N > 1) бросков? Можете ли вы написать рекурсивную функцию и реализацию для вычисления вероятности?
Решение:
Пусть F(n, H) — количество последовательностей длины n, заканчивающихся на HH и начинающихся с H, а F(n, T) — количество последовательностей длины n, заканчивающихся на HH и начинающихся с T.
Таким образом, F(n+1, T) = F(n, H) + F(n, T), потому что если последовательность начинается с T, то оставшаяся последовательность может начинаться либо с H, либо с T.
F(n+1, H) = F(n, T), поскольку если последовательность начинается с H, то оставшаяся последовательность может начинаться только с T (HH запрещен).
Пусть G(n+1) = F(n+1, H) + F(n+1, T) = F(n, T) + F(n, H) + F(n, T) = F(n -1, Н) + F(n-1, T) + F(n, H) + F(n, T)
G(n+1) = G(n) + G(n-1)
G(1) = 0, G(2) = 1
Вероятность P(n) = (1/2²)*G(2) + (1/2³)*G(3) + (1/2⁴)*G(4) + …. + (1/2^n)*G(n)
Проблема 8:
Вычислите nCr, где n ≥ r и 1 ≤ n ≤ 1000, 1 ≤ r ≤ n.
Решение:
nCr = n-1Cr + n-1Cr-1
Таким образом, мы будем использовать динамическое программирование для вычисления значений:
Сложность времени и пространства составляет O(N²).
Проблема 9:
Внедрите стратифицированную выборку.
Учитывая данные обучения, метки классов и долю данных проверки на класс «test_size». Напишите метод для выборки данных обучения, тестовых данных, меток обучения и тестовых меток, чтобы каждый класс имел долю данных/меток «test_size» для проверки и долю данных/меток 1-test_size для обучения.
Решение:
Одним из решений является первая группа на основе меток классов, затем для каждой группы вызывается метод выборки, чтобы получить проверочные образцы, а затем использовать оставшиеся в качестве обучающих образцов.
Поскольку здесь размер данных фиксирован, вместо использования выборки резервуара, как описано выше (для потоковой передачи данных), мы будем использовать другой, более чистый метод:
Сгенерируйте однородное случайное число от 0 до 1. Если оно ≤ test_size, добавьте текущие данные и метку в проверочный набор, иначе добавьте их в обучающий набор.
Но нужно ли нам сначала группировать по ярлыкам классов?
Если мы перебираем все данные, то какова вероятность того, что я выберу точку для добавления в проверочный набор s.t. вероятность на класс - test_size.
Пусть P(y=1) будет вероятностью выбора данных/метки, а P(Ci) будет вероятностью класса Ci или доли класса Ci в данных.
Тогда P(y=1) = P(y=1|C1)*P(C1) + P(y=1|C2)*P(C2) + … + P(y=1|Cm)*P(Cm ), где есть «m» классов.
Мы знаем, что P(y=1|C1) = P(y=1|C2) = …. = test_size, т. е. вероятность выбора данных/метки для проверки при условии, что метка класса равна test_size.
Таким образом, P(y=1) = test_size*(P(C1) + P(C2) + … + P(Cm)) = test_size, поскольку P(C1) + P(C2) + … + P(Cm) = 1
Таким образом, вместо группировки по метке класса мы можем перебрать все данные и выбрать данные/метку, если uniform(0,1) ≤ test_size.
Сначала это может быть не интуитивно понятным, так как может показаться, что мы сэмплируем долю test_size по всем данным, а не по классам, но обратите внимание, что распределение классов уже обрабатывается, когда я перебираю все данные. Таким образом, класс с большим количеством образцов будет иметь больше шансов.
Проблема 10:
Вам даны истинные метки и предсказанные вероятности из модели логистической регрессии для N тестовых примеров. Приблизительно вычислите баллы AUC для кривых ROC и PR.
Решение:
Для ROC нам нужны значения TPR и FPR.
TPR = TP/(Количество всех данных с истинной меткой = 1)
FPR = FP/(Количество всех данных с истинной меткой = 0)
Для каждого порога вероятности найдите значения TPR и FPR.
При заданном пороге T TP = количество данных с вероятностью ≥ T, имеющих истинную метку = 1, и FP = количество данных с вероятностью ≥ T, имеющих истинную метку = 0. Также, когда T уменьшается, TPR и FPR увеличиваются, и наоборот.
Мы можем эффективно решить эту проблему, отсортировав данные по вероятности.
После сортировки по вероятности, начиная с конца, если в индексе i истинная метка = 1, то мы увеличиваем TP на 1, в противном случае мы увеличиваем FP на 1, потому что мы предполагаем, что порог равен вероятности [i].
Чтобы вычислить AUC, мы используем формулу трапеции: 0,5 * ширина * (высота1 + высота2), где ширина — это разница в FPR между двумя последовательными пороговыми значениями, а высота1 — это TPR при пороге T (i), а высота2 — это TPR при пороге. Т(я+1).
Точно так же мы можем вычислить AUC для кривой PR.
Точность = TP/(количество данных, которые, по прогнозам, будут положительными, т. е. количество точек с вероятностью ≥ порога).
Отзыв = TP/(Количество всех данных с истинной меткой = 1).
Проблема 11:
Реализуйте базовый классификатор бинарной логистической регрессии. Он должен выполнять следующие операции:
- Модель поезда
- Прогнозировать данные тестирования
Предположим, что данные обучения и тестирования представлены в виде двумерной матрицы, а метки классов представляют собой одномерный массив.
Решение:
Важные методы для рассмотрения:
- Вычисление сигмовидных оценок
- Расчет логистических потерь
- Градиентный спуск (пакетный или стохастический)
Проблема 12:
Реализуйте простой классификатор дерева решений. Он должен выполнять следующие операции:
- Модель поезда
- Прогнозировать данные тестирования
Предположим, что данные обучения и тестирования представлены в виде двумерной матрицы, а метки классов представляют собой одномерный массив.
Решение:
Важные методы для рассмотрения:
- Прирост вычислительной информации
- Разделение узла на функцию и значение функции.
