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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Задача 5)
(→Решение)
Строка 262: Строка 262:
Получаем линейную регрессию: <math> Y = 0.479 + 0.57X </math>
Получаем линейную регрессию: <math> Y = 0.479 + 0.57X </math>
 +
 +
== Задача 6 ==
 +
 +
Заданы таблицы значений бинарных признаков для классов <math>K_1</math> и <math>K_2</math>. Требуется найти все тупиковые тесты минимальной длины, а также указать для каждого класса по одному представительному набору, который не совпадает по признакам с тупиковым тестом.
 +
 +
{| border = 1
 +
|colspan="4" | Класс 1
 +
|-
 +
| X_1 || X_2 || X_3 || X_4
 +
|-
 +
| 0 || 0 || 0 || 0
 +
|-
 +
| 1 || 0 || 1 || 0
 +
|-
 +
| 0 || 0 || 0 || 1
 +
|}
 +
 +
{| border = 1
 +
|colspan="4" | Класс 2
 +
|-
 +
| X_1 || X_2 || X_3 || X_4
 +
|-
 +
| 1 || 0 || 1 || 1
 +
|-
 +
| 1 || 1 || 0 || 0
 +
|-
 +
| 1 || 1 || 0 || 0
 +
|}
 +
 +
=== Решение ===
 +
 +
Кратчайший тупиковый тест состоит из трёх столбцов: <math> (X_1, X_2, X_4), (X_1, X_3, X_4) </math> или <math> (X_2, X_3, X_4) </math>
 +
 +
Представительный набор определяется для класса и для элемента. Например, для первого элемента первого класса представительным будет набор - <math>(X_1, X_2)</math>, а для первого элемента второго класса - набор <math>(X_3, X_4)</math>
 +
{{Курс МОТП}}
{{Курс МОТП}}

Версия 19:54, 23 апреля 2013

Содержание

Задача 1

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

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 - множество классов (K1,K2), λy - цена ошибки (λ1 = λ2), Py - вероятность появления объекта класса y (априорная вероятность), py(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 классификатор отнесёт объект в класс K2, при x < 0.541 - в класс K1

Изображение:MOTP_2013_1.png

Задача 2

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

f1(x) = 4.8 − 2.3x

f2(x) = − 4.6 − 2.6x

f3(x) = 4.5 − 2.3x

f4(x) = 4.2 − 0.4x

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

Решение

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

(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).

Изображение:MOTP_2013_2.png

Задача 3

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

Класс 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}

Изображение:MOTP_2013_3.png

Ответ: \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 = TP + FN

700 = TN + FP

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

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

Решая систему, получаем, что TP = 258, FP = 77, FN = 42, TN = 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

r(X,Y) = \frac{cov(X,Y)}{\sqrt{DX}\sqrt{DY}}

DX = \overline{(X-\overline{X})^2} = 7.145

DY = \overline{(Y-\overline{Y})^2} = 2.615

r(X,Y) = \frac{4.07}{\sqrt{7.145}\sqrt{2.615}} = 0.94

Воспользуемся методом наименьших квадратов для расчета коэффициентов одномерной линейной регрессии Y = a + bX:

b = \frac{cov(X,Y)}{DX} = \frac{4.07}{7.145} = 0.57

a = \overline{Y} - b\overline{X} = 3.5 - 0.57 \cdot 5.3 = 0.479

Получаем линейную регрессию: Y = 0.479 + 0.57X

Задача 6

Заданы таблицы значений бинарных признаков для классов K1 и K2. Требуется найти все тупиковые тесты минимальной длины, а также указать для каждого класса по одному представительному набору, который не совпадает по признакам с тупиковым тестом.

Класс 1
X_1 X_2 X_3 X_4
0 0 0 0
1 0 1 0
0 0 0 1
Класс 2
X_1 X_2 X_3 X_4
1 0 1 1
1 1 0 0
1 1 0 0

Решение

Кратчайший тупиковый тест состоит из трёх столбцов: (X1,X2,X4),(X1,X3,X4) или (X2,X3,X4)

Представительный набор определяется для класса и для элемента. Например, для первого элемента первого класса представительным будет набор - (X1,X2), а для первого элемента второго класса - набор (X3,X4)


Математические основы теории прогнозирования

Материалы по курсу
Билеты (2009) | Примеры задач (2009) | Примеры задач контрольной работы (2013) | Определения из теории вероятностей

Получено с http://esyr.us/wiki/%D0%9C%D0%9E%D0%A2%D0%9F%2C_%D0%9A%D0%BE%D0%BD%D1%82%D1%80%D0%BE%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_2013
Личные инструменты
Разделы