Рассмотрение некоторых наборов задач, которые охватывают базовую вероятность и статистику (ProbStat) для машинного обучения.

Привет всем, добро пожаловать в мой второй пост! Это будет продолжение моего первого поста. Мы собираемся быть техническими здесь, или я должен сказать несколько «Mathy». Таким образом, для тех, кто какое-то время был вдали от практической математики, я предлагаю просмотреть материал о вероятности, статистике и исчислении. Вы можете сделать это по ходу чтения этой истории, чтобы вам было удобно следовать моему объяснению.

Эта история вдохновлена ​​курсом, который я прошел в Колумбийском университете. С программой и подробными сведениями о курсе можно ознакомиться по этой ссылке: COMS W4771 Machine Learning Fall 2019 by Daniel Hsu.

Как вы могли понять, вы не могли получить доступ к файлам заданий (что и задумано профессором). Таким образом, наборы задач, которые я собираюсь осветить, также будут несколько отличаться, я бы сказал, что это будут некоторые вариации того, что я делал в курсе. Это не будет совсем другим, и я постараюсь изо всех сил, чтобы я мог дать что-то примерно того же уровня.

В этой истории я познакомлю вас с тремя разными задачами, которые, как мне кажется, охватывают все основные концепции, которые вам нужно знать о ProbStat, чтобы начать изучать машинное обучение (в частности, байесовское машинное обучение). Так как большинство решений нетривиальны, я хотел бы предупредить вас, что эта история будет длинной, так что потерпите меня!

Наконец, прежде чем мы начнем, я хотел бы сообщить вам, что этот пост содержит формулы LaTeX. Чтобы они отображались правильно, установите надстройку Math Anywhere и активируйте ее в своем браузере (предлагаю Google Chrome), пока читаете этот пост.

Проблема 1: Описание

Прежде всего, освойте базовую вероятность!

Мы собираемся использовать алгоритм k-ближайших соседей (kNN) в качестве нашей предыстории. Если вы не знакомы с ним или вам нужно немного освежиться, я рекомендую вам взглянуть на эту удивительную историю от коллеги, автора Towards Data Science (TDS).

Давайте ограничим нашу область видимости до $k=1$, т.е. мы найдем только одного ближайшего соседа. Предположим, у нас есть $n$ обучающих примеров, тогда сложность этого алгоритма составляет $O(n)$, потому что нам просто нужно перебрать $n$ примеров, каждый из которых вычисляет разницу в $L_2$, а затем, наконец, выбрать соседа с наименьшим Расстояние $L_2$.

Допустим, вы работаете в компании, и ваш начальник просит вас ускорить расчет этого процесса 1-NN. Его не волнует, что результат не идеален в дюймах, пока он падает до минимум 10% соседей. Например, если имеется 1 миллион данных, выбранный вами сосед должен находиться в пределах 100 000 данных с наименьшим расстоянием $L_2$.

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

Имея контрольную точку $x \in \mathbb{R}^d$, мы говорим, что ближайший сосед с 10%-ным приближением есть $x_{i(x)} s.t. ||x−x_{i(x)}||_2$ входит в число наименьших 10% расстояний до тренировочных точек $||x−x1||_2,…,||x−xn||_2$ с $n $ как количество обучающих примеров

Конечно, указанную выше проблему можно просто решить, взяв образцы $\lceil{0,9n}\rceil + 1$ из обучающих примеров. Другими словами, если у вас есть миллион данных, просто выберите 900 тыс. + 1 данных без замены, и все готово. Однако это не сильно ускоряет вычисления, и это довольно бесполезно.

Итак, позвольте мне предложить кое-что довольно неожиданное, по крайней мере, это то, что я чувствовал, когда работал над задачей, похожей на эту. Что, если я скажу, что, выбрав ровно 50 примеров, назовем это $T=50$, мы могли бы убедиться, что математически вероятность того, что мы получим соседа за пределами этих 10% примеров с наименьшим расстоянием $L_2$, очень мала, скажем не более 0,5%. Это не зависит от количества данных ($n$). Не могли бы вы это доказать?

Проблема 1: Решение

Решение проблемы 1 на самом деле довольно простое, хотя описание проблемы кажется немного громоздким. Видите, что это в основном просто выборка без проблем с заменой. Я подхожу к этой проблеме следующим образом: поскольку мы ищем вероятность того, что все выборочные данные не входят в верхние 10 %, то это то же самое, что вычисление вероятности того, что все выборочные данные (из них 50) находятся в остальные 90% данных.

Таким образом, мы можем записать вероятность, скажем, $p$, как:

$$p = \frac{\text{количество комбинаций выбора 50 примеров из 0,9n данных}}{\text{количество комбинаций выбора 50 образцов из n данных}}$$

$$p=\frac{\binom{\lceil{0,9n}\rceil}{50}}{\binom{n}{50}}=\frac{\frac{\frac{\lceil{0,9n}\rceil!} {(\lceil{0,9n}\rceil-50)!\:50!}}{\frac{n!}{(n-50)!\:50!}}=\frac{\lceil{0,9n} \rceil\:(n-50)!}{n!\:(\lceil{0,9n}\rceil-50)!}=(\frac{(n-50)!}{n!})(\frac {\lceil{0,9n}\rceil!}{(\lceil{0,9n}\rceil-50)!})$$
$$p=\frac{\lceil{0,9n}\rceil(\ lceil{0.9n}\rceil-1)(\lceil{0.9n}\rceil-2)…(\lceil{0.9n}\rceil-49)}{n(n-1)(n-2)…( n-49)} = \ prod_ {i = 0} ^ {49} \ frac {\ lceil {0,9n} \ rceil-i} {ni} $ $

Нам интересно увидеть значение вышеуказанной вероятности независимо от размера данных. Следовательно, мой подход будет заключаться в том, чтобы взять $n \to \infty$. Значение вероятности, которое получается из этого, будет самым высоким (попытайтесь рассуждать, почему это так). Таким образом, мы можем доказать, что шанс не превышает 0,5%.

$$p_{n\to\infty}=\lim_{n\to\infty}\prod_{i=0}^{49}\frac{\lceil{0.9n}\rceil-i}{ni}$$

Использование правила умножения для лимита:

$$p_{n\to\infty}=\prod_{i=0}^{49}\lim_{n\to\infty}\frac{\lceil{0.9n}\rceil-i}{ni}$$

Это довольно легко решить, если бы не функция потолка. Я оставлю читателю в качестве упражнения решить, что делать, если $0,9n$ не является целым числом. Здесь я просто рассмотрю более простой случай, т. е. когда $0,9n$ — целое число:

$$p_{n\to\infty}=\prod_{i=0}^{49}\lim_{n\to\infty}\frac{\lceil{0.9n}\rceil-i}{ni}=\ prod_{i=0}^{49}\lim_{n\to\infty}\frac{0.9ni}{ni}=\prod_{i=0}^{49}\lim_{n\to\infty}\ frac{0.9-i/n}{1-i/n}$$
$$p_{n\to\infty}=\prod_{i=0}^{49}\frac{0.9–0} {1–0}=\prod_{i=0}^{49}0,9={0,9}^{50}= 0,00515377520732012$$

Выше мы видим, что вероятность того, что мы не получим ни одной выборки из 10% лучших примеров (независимо от размера данных), составляет не более 0,5%.

Это довольно примечательно, мы смогли уменьшить сложность с $O(n)$ до $O(50)$, что является постоянным! Однако на деле это не всегда так. В разделе комментариев ниже дайте мне знать, если у вас есть какие-либо идеи о том, почему это так!

PS: Есть еще одна загвоздка, которую вы можете обнаружить: обратите внимание, что выборка без проблемы замены для $n \to\infty$ может рассматриваться как (или рассматриваться как) выборка с проблемой замены!

Проблема 2: Описание

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

Если вы не знакомы с этой темой, подумайте о том, чтобы проверить эту классную статью, также написанную другим автором TDS. Вы также хотели бы ознакомиться с терминами, которые я буду использовать ниже (i.i.d, случайная величина, функция плотности вероятности, вероятность и т. д.). Итак, поехали!

Рассмотрим статистическую модель для i.i.d случайных величин $X_1, X_2, …, X_n$, параметризованных как $\theta \in \Theta$ . Пространство параметров представляет собой положительные действительные числа $\Theta = \{ \theta \in R : \theta › 0 \}$.

Распределение $P_\theta$ $X_1$ выглядит следующим образом:

$X_1 \~ P_\theta$ имеет функцию плотности вероятности (p.d.f.) $f_\theta$, удовлетворяющую:

$$f_\theta \propto 1\text{ для всех } 0 \leq x \leq \theta$$

$$f_\theta = 0 \text{ для } x ‹ 0 \text{ и } x › \theta$$

Выведите простую формулу для MLE для $\theta$, учитывая данные $(X_1, X_2, …, X_n) = (x_1, x_2, …, x_n)$!

Проблема 2: Решение

Мы рассмотрим два определения p.d.f.:

  1. Для $x‹0$ и $x›\theta$ $f_{\theta}(x)=0$. Таким образом, в этом случае вероятность всегда равна нулю, и MLE также будет равен нулю.
  2. Для $0\leq{x}\leq{\theta}$ $f_{\theta}(x)\propto1$. Помните, что $\propto$ означает, что p.d.f. пропорциональна 1, но это не совсем 1, а некоторая константа. Это означает, что $f_{\theta}(x)=c$ для некоторой константы c: $0‹c‹\infty$.
    Используя свойство п.ф.ф. следует интегрировать в единицу, мы можем определить c:
    $$c\int_{0}^{\theta}dx=1$$
    $$cx\Big|_0^{\theta}=1 $$
    $$c[\theta-0]=1$$
    $$c=1/\theta$$
    Следовательно, вероятность для $\{x_1,x_2,x_3 ,…,x_n\}$ будет:
    $$L(\theta|x)=\prod_{i=1}^{n} f_{\theta}(x_i) = c^n = ({ 1/\theta})^n = 1/{\theta^n}$$
    Чтобы максимизировать эту вероятность, мы хотим выбрать наименьшее возможное значение $\theta$. Поскольку мы знаем, что $0\leq{x}\leq{\theta}$, наименьший возможный $\theta$ будет наибольшим $x$ в наборе. Таким образом, формула MLE будет следующей: $ и $\theta›0$, эта формула MLE всегда будет больше или равна MLE для случая 1 ($\geq{0})$. Следовательно, мы можем выбрать это в качестве нашей формулы MLE.

Проблема 3: Описание

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

Поскольку в некоторых странах приближаются дни выборов, я думаю, было бы интересно использовать это здесь в качестве предыстории. Предположим, что в одной из этих стран, назовем ее страной $U$, есть два кандидата в президенты, а именно г-н Мурпт и г-н Небид. Назовите г-на Мерпта как $M$, а г-на Небида как $N$.

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

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

Попросите его/ее дважды подбросить монету и скажите, чтобы он/она не сообщал вам о результате.

Если хотя бы один из бросков выпал головой, скажите ему/ей, чтобы он ответил правдиво (например, если он/она проголосует за $M$, то он/она скажет вам $M$)

Если оба броска выпали решкой, скажите ему/ей дать противоположный ответ (например, если он/она проголосует за $M$, то он/она скажет вам $N$)

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

Теперь мы подходим к основным вопросам.

Рассмотрим статистическую модель для $n$ ответов, собранных по приведенной выше схеме, где ответы рассматриваются как iid {0, 1}-значные случайные величины $Y_1, Y_2, …, Y_n$, а все подбрасывания монеты независимы. Пусть $\theta \in [0, 1]$ обозначает параметр модели, равный доле лиц в популяции, голосующих за $M$.

Затем ответьте на эти три задачи:

Какова вероятность того, что $Y_1=1$? Ответ должен быть дан в терминах $\theta$.

Какова логарифмическая вероятность $\theta$ при данных $y_1, y_2, …, y_n \in {0,1}$? Ответ должен быть дан в терминах $\theta$ и $y_1, y_2, …, y_n$

Предположим, что $n=100$, т.е. мы выбираем всего несколько человек из каждого штата страны, а количество $y_i$, равных 1, равно 40, т.е. $\sum_{i=1}^n{y_i} =40$. Постройте логарифмическую вероятность как функцию $\theta \in [0,1]$. Что представляется $\theta$ с наибольшей вероятностью?

Проблема 3.1: Решение

Пусть X — случайная величина, обозначающая количество выпадений орла при двух подбрасываниях монеты ($X=[0,1,2]$). Затем мы можем определить две вероятности ниже:
$$P(X=0)=P(решка).P(решка)=(1/2)(1/2)=1/4$$
$$P(X\geq1)=1-P(X=0)=1-(1/2)(1/2)=3/4$$

Используя эти вероятности, $Y_1=1$ происходит, когда человек выбирает $M$, получает по крайней мере одну решку $P(X\geq1)$ или когда человек выбирает $N$, не получает $P(X=0)$ орла. Также помните, что выбор $M$ имеет вероятность $\theta$, а выбор $N$ имеет вероятность $1-\theta$. Таким образом, $P(Y_1)=1$ равно:

$$P(Y_1=1)=P(X=0)(1-\тета) + P(X\geq1)\тета$$
$$P(Y_1=1)=(1/4) (1-\тета) + (3/4)\тета$$
$$\boldsymbol{P(Y_1=1)=(1/2)\тета + (1/4)}$$

Задача 3.2: Решение

Поскольку в этой задаче задействована дискретная случайная величина, мы можем моделировать вероятность с помощью той же функции, что и вероятность. Чтобы вычислить вероятность, нам нужно определить два компонента:

  1. Сколько существует комбинаций событий (значение $y_i$), указанных как $\binom{n}{\sum_{i=1}^{n}y_i}$. Например, если $n=2$, есть четыре возможности: [0,0], [0,1], [1,0], [1,1].
  2. Для каждого события, если $y_i=1$, вероятность будет равна $P(y_i=1)$, иначе, если $y_i=0$, будет $P(y_i=0)$. Это можно выразить как $P(y_i=1)^{y_i}P(y_i=0)^{1-y_i}$, что в основном является биномиальным распределением.

Таким образом, вероятность:

$$L(\theta|n,\sum_{i=1}^{n}y_i)=P(\sum_{i=1}^{n}y_i)|n,\theta)$$
$$L(\theta|n,\sum_{i=1}^{n}y_i)=\binom{n}{\sum_{i=1}^{n}y_i}\prod_{i=1}^ {n}P(y_i=1)^{y_i}P(y_i=0)^{1-y_i}$$
$$L(\theta|n,\sum_{i=1}^{n }y_i)=\binom{n}{\sum_{i=1}^{n}y_i}\prod_{i=1}^{n}P(y_i=1)^{y_i}(1-P(y_i =1))^{1-y_i}$$
$$L(\theta|\sum_{i=1}^{n}y_i)=\binom{n}{\sum_{i=1} ^ {n} y_i} \ prod_ {i = 1} ^ {n} ({\ frac {1} {2} \ theta+ \ frac {1} {4}}) ^ {y_i} ({- \ frac {1 }{2}\theta+\frac{3}{4}})^{1-y_i}$$
Тогда логарифмическая вероятность будет следующей:
$$\ln{L(\theta| \sum_{i=1}^{n}y_i)}=\ln{\binom{n}{\sum_{i=1}^{n}y_i}\prod_{i=1}^{n}({ \frac{1}{2}\theta+\frac{1}{4}})^{y_i}({-\frac{1}{2}\theta+\frac{3}{4}})^{1 -y_i}}$$
$$\ln{L(\theta|\sum_{i=1}^{n}y_i)}=\ln{\binom{n}{\sum_{i=1 } ^ {n} y_i}} + \ ln {\ prod_ {i = 1} ^ {n} ({\ frac {1} {2} \ theta+ \ frac {1} {4}}) ^ {y_i} ( {-\frac{1}{2}\theta+\frac{3}{4}})^{1-y_i}}$$
$$\ln{L(\theta|\sum_{i= 1}^{n}y_i)}=\ln{\binom{n}{\sum_{i=1}^{n}y_i}}+\sum_{i=1}^{n}\ln({\ frac{1}{2}\theta+\frac{1}{4}})^{y_i}+\sum_{i= 1}^n\ln({-\frac{1}{2}\theta+\frac{3}{4}})^{1-y_i}$$
$$\ln{L(\theta |\sum_{i=1}^{n}y_i)}=\ln{\binom{n}{\sum_{i=1}^{n}y_i}}+\sum_{i=1}^{n } y_i \ ln ({\ frac {1} {2} \ theta + \ frac {1} {4}}) + \ sum_ {i = 1} ^ n (1-y_i) \ ln ({- \ frac {1 }{2}\theta+\frac{3}{4}})$$
$$\boldsymbol{\ln{L(\theta|\sum_{i=1}^{n}y_i)}= \ ln {\ binom {n} {\ sum_ {i = 1} ^ {n} y_i}} + \ sum_ {i = 1} ^ {n} y_i \ ln ({\ frac {1} {2} \ theta+ \frac{1}{4}})+(n-\sum_{i=1}^n(y_i))\ln({-\frac{1}{2}\theta+\frac{3}{4} })}$$

Задача 3.3: Решение

Выше приведен график логарифмического правдоподобия как функции $\theta\in[0,1]$ при n=100 и $\sum_{i=1}^{n}y_i=40$. Фрагмент кода, который я использую для создания такого графика, находится в этом GitHub Gist: log-вероятность plot.ipynb.

Мы видим, что $\theta$ с наибольшей вероятностью составляет где-то около $0,2$ и $0,4$. Давайте проверим это, получив оптимальную $\theta$ для логарифмической вероятности ниже, то есть $\hat{\theta}_{MLE}$.

Функция, соответствующая графику, получается ниже путем замены заданных значений:

$$L(\theta|n=100,\sum_{i=1}^{n}y_i=40)=\ln{\binom{100}{\sum_{i=1}^{100}y_i}} +\sum_{i=1}^{100}y_i\ln({\frac{1}{2}\theta+\frac{1}{4}})+(100-\sum_{i=1}^{ 100}(y_i))\ln({-\frac{1}{2}\theta+\frac{3}{4}})$$
$$L(\theta|n=100,\sum_ {i = 1} ^ {n} y_i = 40) = \ ln {\ binom {100} {40}} + 40 \ ln ({\ frac {1} {2} \ theta + \ frac {1} {4} })+(100–40)\ln({-\frac{1}{2}\theta+\frac{3}{4}})$$
$$L(\theta|n=100, \sum_{i=1}^{n}y_i=40)=\ln({\frac{100!}{60!40!}})+40\ln({\frac{1}{2}\theta+ \frac{1}{4}})+60\ln({-\frac{1}{2}\theta+\frac{3}{4}})$$
$$\boldsymbol{L( \ тета | n = 100, \ sum_ {i = 1} ^ {n} y_i = 40) = 64,7906 + 40 \ ln ({\ frac {1} {2} \ theta + \ frac {1} {4}}) +60\ln({-\frac{1}{2}\theta+\frac{3}{4}}})$$
Чтобы определить $\theta$ с наибольшей вероятностью, мы можем взять первую производную от $L(\theta)$, а затем найти $\theta$ так, чтобы она равнялась нулю.
$$\frac{d}{d\theta}L(\theta)=0$$< br /> $$\frac{d}{d\theta}\ln({\frac{100!}{60!40!}})+\frac{d}{d\theta}40\ln({\ frac{1}{2}\theta+\frac{1}{4}})+\frac{d}{d\theta}60\ln({-\frac{1}{ 2}\theta+\frac{3}{4}})=0$$
$$\frac{(40)(\frac{1}{2})}{\frac{1}{2} \theta+\frac{1}{4}}+\frac{(60)(-\frac{1}{2})}{-\frac{1}{2}\theta+\frac{3}{4} }=0$$
$$\frac{20}{\frac{1}{2}\theta+\frac{1}{4}}+\frac{-30}{-\frac{1} {2}\theta+\frac{3}{4}}=0$$
$$\frac{-10\theta+15–15\theta-7,5}{(1/2)\theta+1 /4)((-1/2)\тета+3/4)}=0$$
$$\frac{-25\тета+7,5}{(1/2)\тета+1/4 )((-1/2)\theta+3/4)}=0$$
$$\theta=\frac{7.5}{25}=\frac{3}{10}=0.3$$
$$\boldsymbol{\шляпа{\theta}_{mle}=0,3}$$

Мы могли видеть, что это согласуется с тем, что мы видим в сюжете.

Заключительные слова

Я думаю, что это было бы все для этой истории. Приношу свои извинения за то, что мне нужно установить надстройку Math Anywhere, чтобы прочитать эту статью, потому что я не смог найти более удобного способа написания LaTeX на Medium.

Я предпочитаю не загружать изображения для математической записи, а Tex to Unicode мне не подходит. В разделе комментариев ниже, пожалуйста, предложите мне, если вы знаете какой-либо лучший способ представления математических обозначений на Medium, я был бы очень признателен за это.

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

Ваше здоровье,

Джерал