МОТП, Контрольная 2013

Материал из eSyr's wiki.

Версия от 19:23, 23 апреля 2013; SkyHawk (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Задача 1
- 1.1 Решение
2 Задача 2
- 2.1 Решение
3 Задача 3
- 3.1 Решение
4 Задача 4
- 4.1 Решение:
5 Задача 5
- 5.1 Решение

Задача 1

Рассматривается задача классификации объектов на два класса по одному признаку. Предполагается, что значение признака x для объектов из классов $K 1$ , $K 2$ распределено по закону Рэлея:

$p(x|K_j) = \beta_j x e^{(-\frac{\beta_j}{2}x^2)}$

Пусть $β 1 = 7.3$ $β 2 = 1.3.$ Требуется найти области значений признака x, соответствующие отнесению объектов в каждый из двух классов байесовским классификатором, если априорные вероятности классов равны, соответственно, 0.3 и 0.7.

Решение

По определению баесовского классификатора:

$a(x) = \mathrm{arg}\max_{y\in Y} \lambda_{y} P_y p_y(x),$

где $x$ - классифицируемый пример, $a (x)$ - классификатор, $Y$ - множество классов ( $K 1, K 2$ ), $λ y$ - цена ошибки ( $λ 1 = λ 2$ ), $P y$ - вероятность появления объекта класса $y$ (априорная вероятность), $p y (x)$ - плотность распределения класса $y$ в точке $x$ .

Построим множество, на котором $\lambda_{1} P_1 p_1(x) \lessgtr \lambda_{2} P_2 p_2(x).$ Для этого решим уравнение:

$\lambda_{1} 0.3 p(x|K_1) \lessgtr \lambda_{2} 0.7 p(x|K_2)$

$0.3 \cdot 7.3 \cdot x e^{(-\frac{7.3}{2}x^2)} \lessgtr 0.7 \cdot 1.3 \cdot x e^{(-\frac{1.3}{2}x^2)}$

$e^{(-3x^2)} \lessgtr 0.4155$

$-3x^2 \lessgtr \ln(0.4155) \lessgtr -0.878$

$x \gtrless 0.541$

Таким образом, при $x > 0.541$ классификатор отнесёт объект в класс $K 2$ , при $x < 0.541$ - в класс $K 1$

Задача 2

Имеется задача распознавания с 4-мя классами и одним признаком. Предполагается, что с использованием метода "Линейная машина" для каждого класса найдены следующие линейные разделяющие функции:

$f 1 (x) = 4.8 - 2.3 x$

$f 2 (x) = - 4.6 - 2.6 x$

$f 3 (x) = 4.5 - 2.3 x$

$f 4 (x) = 4.2 - 0.4 x$

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

Решение

Для нахождения требуемых областей, решим системы неравенств:

$(1) \begin{cases} f_1(x) > f_2(x) \\ f_1(x) > f_3(x) \\ f_1(x) > f_4(x) \end{cases}$

$\begin{cases} 4.8 - 2.3 x > -4.6 - 2.6 x \\ 4.8 - 2.3 x > 4.5 - 2.3 x \\ 4.8 - 2.3 x > 4.2 - 0.4 x \end{cases}$

$\begin{cases} x > -31.3 \\ 4.8 > 4.5 \\ x < 0.3 \end{cases}$

Таким образом, объект будет отнесён в класс 1 при $x \in (-31.3, 0.3).$

Аналогично:

$(2) \begin{cases} f_2(x) > f_1(x) \\ f_2(x) > f_3(x) \\ f_2(x) > f_4(x) \end{cases}$

$\begin{cases} -4.6 - 2.6 x > 4.8 - 2.3 x \\ -4.6 - 2.6 x > 4.5 - 2.3 x \\ -4.6 - 2.6 x > 4.2 - 0.4 x \end{cases}$

$\begin{cases} x < -31.3 \\ x < -30.3 \\ x < -4 \end{cases}$

Oбъект будет отнесён в класс 2 при $x \in (-\inf, -31.3).$

$(3) \begin{cases} f_3(x) > f_1(x) \\ f_3(x) > f_2(x) \\ f_3(x) > f_4(x) \end{cases}$

$\begin{cases} 4.5 - 2.3 x > 4.8 - 2.3 x \\ 4.5 - 2.3 x > -4.6 - 2.6 x \\ 4.5 - 2.3 x > 4.2 - 0.4 x \end{cases}$

$x \in \empty$ , поэтому никакой объект не будет отнесён к классу 3.

$(3) \begin{cases} f_4(x) > f_1(x) \\ f_4(x) > f_2(x) \\ f_4(x) > f_3(x) \end{cases}$

$\begin{cases} x > 0.3 \\ x > -4 \\ x > 0.2 \end{cases}$

Oбъект будет отнесён в класс 4 при $x \in (0.3, +\inf).$

Задача 3

Предполагается, что линейный дискриминант Фишера используется для распознавания объектов из двух классов по паре признаков $x 1$ и $x 2$ . Требуется вычислить вектор, задающий направление перпендикуляра к прямой, разделяющей объекты двух классов:

Класс 1: $\begin{pmatrix} 2.3 \\ 1.8 \end{pmatrix} , \begin{pmatrix} 3.0 \\ 1.9 \end{pmatrix} , \begin{pmatrix} 3.2 \\ 2.1 \end{pmatrix} , \begin{pmatrix} 3.1 \\ 0.6 \end{pmatrix}$

Класс 2: $\begin{pmatrix} -0.9 \\ -3.6 \end{pmatrix} , \begin{pmatrix} -0.1 \\ -3.8 \end{pmatrix} , \begin{pmatrix} 0.1 \\ -2.8 \end{pmatrix}$

Решение

Перпендикуляр к прямой, разделяющей объекты двух классов, описывается уравнением:

$\vec{w} = ( \Sigma_1 + \Sigma_2 )^{-1}(\vec{\mu_1} - \vec{\mu_2}),$

где $\vec{\mu_i}$ - матожидания объектов каждого класса, а $Σ i$ - ковариационная матрица.

Посчитаем матождиания:

$\vec{\mu_1} = \frac{1}{4} \left( \begin{pmatrix} 2.3 \\ 1.8 \end{pmatrix} + \begin{pmatrix} 3.0 \\ 1.9 \end{pmatrix} + \begin{pmatrix} 3.2 \\ 2.1 \end{pmatrix} + \begin{pmatrix} 3.1 \\ 0.6 \end{pmatrix} \right) = \begin{pmatrix} 2.9 \\ 1.6 \end{pmatrix}$

$\vec{\mu_2} = \frac{1}{3} \left( \begin{pmatrix} -0.9 \\ -3.6 \end{pmatrix} + \begin{pmatrix} -0.1 \\ -3.8 \end{pmatrix} + \begin{pmatrix} 0.1 \\ -2.8 \end{pmatrix} \right) = \begin{pmatrix} -0.3 \\ -3.4 \end{pmatrix}$

Посчитаем ковариационные матрицы:

$\Sigma_1 = \frac{1}{4} \left( \begin{pmatrix} (2.3-2.9)\cdot(2.3-2.9) & (2.3 - 2.9)\cdot(1.8 - 1.6)\\ (1.8 - 1.6)\cdot(2.3 - 2.9)& (1.8 - 1.6)\cdot(1.8 - 1.6) \end{pmatrix} + ... \right) = \begin{pmatrix} 0.125& -0.035 \\ -0.035& 0.345 \end{pmatrix}$

$\Sigma_2 = \begin{pmatrix} 0.187& 0.093 \\ 0.093& 0.187 \end{pmatrix}$

$\left( \Sigma_1 + \Sigma_2 \right)^{-1} = \begin{pmatrix} 0.312& 0.058 \\ 0.058& 0.532 \end{pmatrix}^{-1} = \frac{1}{0.163}\begin{pmatrix} 0.532& -0.058 \\ -0.058& 0.312 \end{pmatrix} = \begin{pmatrix} 3.26& -0.36 \\ -0.36& 1.91 \end{pmatrix}$

$\vec{w} = \begin{pmatrix} 3.26& -0.36 \\ -0.36& 1.91 \end{pmatrix} \left( \begin{pmatrix} 2.9 \\ 1.6 \end{pmatrix} - \begin{pmatrix} -0.3 \\ -3.4 \end{pmatrix} \right) = \begin{pmatrix} 3.26& -0.36 \\ -0.36& 1.91 \end{pmatrix} \begin{pmatrix} 3.2 \\ 5 \end{pmatrix} = \begin{pmatrix} 8.63 \\ 8.4 \end{pmatrix}$

Ответ: $\begin{pmatrix} 8.63 \\ 8.4 \end{pmatrix}$

Задача 4

При проведении выборов на ряде избирательных участков производятся фальсификации результатов голосования. Посылка наблюдателя на такой участок предотвращает фальсификации. Пусть известно несколько точек ROC-кривой для метода идентификации "грязных" участков. Требуется определить оптимальную стратегию распределения наблюдателей по участкам и максимальный выигрыш относительно стратегии равномерного распределения по участкам, если всего участков 1000, наблюдателей --- 200 и доля "грязных" участков --- 30%. При этом под оптимальностью понимается максимизация количества честных участков.

Чувствительность	Ложная тревога
0.86	0.11
0.90	0.31
0.92	0.32

Решение:

Чувствительность - отношение числа верно распознаных примеров позитивного класса к общему размеру класса: $\frac{TP}{TP + FN}$

Ложная тревога - отношение числа ошибочно распознанных примеров позитивного класса к размеру негативного класса: $\frac{FP}{FP + TN}$

Позитивный исход - идентификация "грязного" участка.

В случае стратегии равномерного распределения наблюдателей по всем участкам, на выбранном участке будет наблюдатель с вероятностью $\frac{200}{1000} = 20%$ . Всего чистых участков: $1000 \cdot 70% + 1000 \cdot 30% \cdot 20% = 760.$

Рассмотрим первый алгоритм.

$300 = T P + F N$

$700 = T N + F P$

$0.86 = \frac{TP}{TP + FN}$

$0.11 = \frac{FP}{FP + TN}$

Решая систему, получаем, что $T P = 258$ , $F P = 77$ , $F N = 42$ , $T N = 623$ . Всего метод возвращает 258+77 = 335 результатов. Наблюдателей в распоряжении - меньше, поэтому распределим их равномерно среди участков, которые вернул метод. Вероятность того, что наблюдатель попадёт на произвольны среди выбранных классификатором участков, равна $\frac{200}{335} = 0.597$ , поэтому среди выбранных участков наблюдатели попадут в среднем на $258 \cdot 0.597 = 154$ участка, и всего чистыми будут $700 + 154 = 854$ участка. Выигрыш составил $854 - 760 = 94$ участка.

Аналогично для других точек.

Задача 5

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

Y	5.9	4.0	2.4	1.7
X	8.3	7.6	3.0	2.3

Решение

$cov(X,Y) = \overline{(X - \overline{X})(Y - \overline{Y})}$

$\overline{X} = 5.3$

$\overline{Y} = 3.5$

$cov(X,Y) = \frac{1}{4}((5.9 - 3.5)\cdot(8.3 - 5.3) + (4.0 - 3.5)\cdot(7.6 - 5.3) + (2.4 - 3.5)\cdot(3.0 - 5.3) + (1.7 - 3.5)\cdot(2.3 - 5.3)) = 4.07$