Отбор на ML и DL, осень 2019

Болезнь

Некоторая болезнь X имеется у 1% населения и не имеет наблюдаемых симптомов. Для определения её наличия был создан специальный тест, который имеет точность 98% и 97% для положитеьных и отрицательных результатов соответственно. Иными словами:

• Если человек болен, то с вероятностью 98% результат теста будет положительным и с вероятностью 2% отрицательным.

• Если человек здоров, то с вероятностью 97% результат теста будет отрицательным и с вероятностью 3% положительным.

Вы решили пройти тест, и его результат оказался положительным. С какой вероятностью вы действительно больны? (подсказка: не 98%)

Решающий пень

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

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

$$ f(x) = \begin{cases} c_1, & x \leq m \\ c_2, & x > m \end{cases} $$

(Описать, что такое метрика MSE)

Даны $n$ точек. Придумайте алгоритм, который подбирает оптимальные параметры $c_1$, $c_2$ и $m$ за линейное время. Реализуйте его на каком-нибудь языке программирования.

Минимум функции

Найдите минимум функции:

$$ f(x, y) = x^4 + 2x^2y + 10x^2 + 6xy + 10y^2 - 6x + 4 $$

Решать можно как программно, так и аналитически. В любом случае, подробно опишите, как был получен ответ.

Перерыв

Вы устали решать задачки с отборов на курсы Tinkoff Generation и решили устроить перерыв, посмотрев несколько серий нового сериала, о котором все говорят.

Вы начинаете смотреть серии, начиная с первой. Каждая серия длится один час. С постоянной вероятностью $p$ очередная серия вам понравится, и вы начнинаете смотреть следующую, иначе ваш перерыв заканчивается, и вы возвращаетесь к работе.

Сколько в среднем будет длиться ваш перерыв?

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

Шляпы

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

Сколько в среднем гостей получат свои шляпы?

Экзитпол

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

Вы опросили 100 случайных человек на выходе из избирательного участка, из которых 55 сказали, что проголосовали за первого кандидата, и, соответственно, 45 — за второго.

С какой вероятностью первый кандидат победит на выборах?

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

Пьяница

Пьяница стоит на краю утёса. Сделав хоть один шаг вперед, он упадёт. Он делает следующее:

• С вероятностью $p > \frac{1}{2}$ он идёт на один шаг назад.
• С вероятностью $(1-p)$ он идёт на один шаг вперед.

Пьяница трезвеет бесконечно долго и не разворачивается, а также можно считать, что назад он может пройти бесконечно далеко. С какой вероятностью он не упадёт никогда?

Бэггинг

Их какого-то множества размера $n$ выбирают с заменой $n$ элементов. Сколько в среднем в нём будет уникальных элементов?

Подсказка: ответ равен $n \cdot k$, где $k$ это какая-то константа, которую вам нужно найти.