Графические модели (курс лекций)/2014/Задание 1

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(распределение по вариантам)
Текущая версия (20:47, 18 февраля 2014) (править) (отменить)
(добавил Ибадова)
 
(9 промежуточных версий не показаны.)
Строка 4: Строка 4:
'''Начало выполнения задания''': 12 февраля 2014 г.<br>
'''Начало выполнения задания''': 12 февраля 2014 г.<br>
-
'''Срок сдачи''': {{важно|26 февраля 2014 г., 23:59.}}
+
'''Срок сдачи''': {{важно|26 февраля 2014 г. (среда), 23:59.}}
Среда для выполнения задания — MATLAB.
Среда для выполнения задания — MATLAB.
 +
== Вероятностные модели посещаемости курса ==
== Вероятностные модели посещаемости курса ==
-
Рассмотрим модель посещаемости студентами одного курса лекции. Пусть аудитория данного курса состоит из студентов профильной кафедры, а также студентов других кафедр. Обозначим через <tex>a</tex> количество студентов, распределившихся на профильную кафедру, а через <tex>b</tex> — количество студентов других кафедр на курсе. Пусть студенты профильной кафедры посещают курс с некоторой вероятностью <tex>p_1</tex>, а студенты остальных кафедр — с вероятностью <tex>p_2</tex>. Обозначим через <tex>c</tex> количество студентов на данной лекции. Тогда случайная величина <tex>c|a,b</tex> есть сумма двух случайных величин, распределенных по биномиальному закону <tex>B(a,p_1)</tex> и <tex>B(b,p_2)</tex> соответственно. Пусть далее на лекции по курсу ведется запись студентов. При этом каждый студент записывается сам, а также, быть может, записывает своего товарища, которого на лекции на самом деле нет. Пусть студент записывает своего товарища с некоторой вероятностью <tex>p_3</tex>. Обозначим через <tex>d</tex> общее количество записавшихся на данной лекции. Тогда случайная величина <tex>d|c</tex> представляет собой сумму <tex>c</tex> и случайной величины, распределенной по биномиальному закону <tex>B(c,p_3)</tex>. Для завершения задания вероятностной модели осталось определить априорные вероятности для <tex>a</tex> и для <tex>b</tex>. Пусть обе эти величины распределены равномерно в своих интервалах <tex>[a_{min},a_{max}]</tex> и <tex>[b_{min},b_{max}]</tex>. Таким образом, мы определили следующую вероятностную модель:<br>
+
Рассмотрим модель посещаемости студентами одного курса лекции. Пусть аудитория данного курса состоит из студентов профильной кафедры, а также студентов других кафедр. Обозначим через <tex>a</tex> количество студентов, распределившихся на профильную кафедру, а через <tex>b</tex> — количество студентов других кафедр на курсе. Пусть студенты профильной кафедры посещают курс с некоторой вероятностью <tex>p_1</tex>, а студенты остальных кафедр — с вероятностью <tex>p_2</tex>. Обозначим через <tex>c</tex> количество студентов на данной лекции. Тогда случайная величина <tex>c|a,b</tex> есть сумма двух случайных величин, распределенных по биномиальному закону <tex>B(a,p_1)</tex> и <tex>B(b,p_2)</tex> соответственно. Пусть далее на лекции по курсу ведется запись студентов. При этом каждый студент записывается сам, а также, быть может, записывает своего товарища, которого на лекции на самом деле нет. Пусть студент записывает своего товарища с некоторой вероятностью <tex>p_3</tex>. Обозначим через <tex>d</tex> общее количество записавшихся на данной лекции. Тогда случайная величина <tex>d|c</tex> представляет собой сумму <tex>c</tex> и случайной величины, распределенной по биномиальному закону <tex>B(c,p_3)</tex>. Для завершения задания вероятностной модели осталось определить априорные вероятности для <tex>a</tex> и для <tex>b</tex>. Пусть обе эти величины распределены равномерно в своих интервалах <tex>[a_{min},a_{max}]</tex> и <tex>[b_{min},b_{max}]</tex> (дискретное равномерное распределение). Таким образом, мы определили следующую вероятностную модель:<br>
'''Модель 1'''<br>
'''Модель 1'''<br>
{| class = "standard"
{| class = "standard"
Строка 23: Строка 24:
|}
|}
-
<br>Рассмотрим несколько упрощенную версию модели 1. Известно, что биномиальное распределение <tex>B(n,p)</tex> при большом количестве испытаний и маленькой вероятности успеха может быть с высокой точностью приближено пуассоновским распределением <tex>Poiss(\lambda)</tex> с <tex>\lambda = np</tex>. Известно также, что сумма двух пуассоновских распределений с параметрами <tex>\lambda_1</tex> и <tex>\lambda_2</tex> есть пуассоновское распределение с параметром <tex>\lambda_1+\lambda_2</tex>. Таким образом, мы можем сформулировать вероятностную модель, которая является приближенной версией модели 1:<br>
+
<br>Рассмотрим несколько упрощенную версию модели 1. Известно, что биномиальное распределение <tex>B(n,p)</tex> при большом количестве испытаний и маленькой вероятности успеха может быть с высокой точностью приближено пуассоновским распределением <tex>Poiss(\lambda)</tex> с <tex>\lambda = np</tex>. Известно также, что сумма двух пуассоновских распределений с параметрами <tex>\lambda_1</tex> и <tex>\lambda_2</tex> есть пуассоновское распределение с параметром <tex>\lambda_1+\lambda_2</tex> (для биномиальных распределений аналогичное неверно). Таким образом, мы можем сформулировать вероятностную модель, которая является приближенной версией модели 1:<br>
'''Модель 2'''<br>
'''Модель 2'''<br>
<tex>p(a,b,c,d)=p(d|c)p(c|a,b)p(a)p(b)</tex>,<br>
<tex>p(a,b,c,d)=p(d|c)p(c|a,b)p(a)p(b)</tex>,<br>
Строка 96: Строка 97:
Присланный вариант задания должен содержать в себе:
Присланный вариант задания должен содержать в себе:
* Текстовый файл в формате PDF с указанием ФИО и номера варианта, содержащий описание всех проведенных исследований.
* Текстовый файл в формате PDF с указанием ФИО и номера варианта, содержащий описание всех проведенных исследований.
-
* Все исходные коды с необходимыми комментариями.
+
* Архив, содержащий все исходные коды с необходимыми комментариями.
-
Исходные коды должны включать в себя реализацию оценки распределений в виде отдельных функций. Прототип для функции оценки распределения <tex>p(c|a,d)</tex> для модели 2 имеет следующий вид:<br>
+
Исходные коды должны включать в себя реализацию оценки распределений в виде отдельных функций (отдельных m-файлов). Прототип для функции оценки распределения <tex>p(c|a,d)</tex> для модели 2 имеет следующий вид:<br>
{|class="standard"
{|class="standard"
!''Оценка распределения <tex>p(c|a,d)</tex> для модели 2''
!''Оценка распределения <tex>p(c|a,d)</tex> для модели 2''
Строка 174: Строка 175:
| align="center"|5 || Зиннурова Эльвира || 1
| align="center"|5 || Зиннурова Эльвира || 1
|-
|-
-
| align="center"|6 || Ломов Никита || 1
+
| align="center"|6 || Корольков Михаил || 3
|-
|-
-
| align="center"|7 || Львов Сергей || 2
+
| align="center"|7 || Ломов Никита || 1
|-
|-
-
| align="center"|8 || Найдин Олег || 2
+
| align="center"|8 || Львов Сергей || 2
|-
|-
-
| align="center"|9 || Никифоров Андрей || 1
+
| align="center"|9 || Найдин Олег || 2
|-
|-
-
| align="center"|10 || Новиков Александр || 3
+
| align="center"|10 || Никифоров Андрей || 1
|-
|-
-
| align="center"|11 || Петров Григорий || 2
+
| align="center"|11 || Новиков Александр || 3
|-
|-
-
| align="center"|12 || Подоприхин Дмитрий || 3
+
| align="center"|12 || Петров Григорий || 2
|-
|-
-
| align="center"|13 || [[Участник:Alex.Ryzhkov|Рыжков Александр]] || 3
+
| align="center"|13 || Подоприхин Дмитрий || 3
|-
|-
-
| align="center"|14 || Сокурский Юрий || 2
+
| align="center"|14 || [[Участник:Alex.Ryzhkov|Рыжков Александр]] || 3
|-
|-
-
| align="center"|15 || Ульянов Дмитрий || 3
+
| align="center"|15 || Сокурский Юрий || 2
|-
|-
-
| align="center"|16 || Харациди Олег || 1
+
| align="center"|16 || Ульянов Дмитрий || 3
|-
|-
-
| align="center"|17 || Шабашев Федор || 3
+
| align="center"|17 || Харациди Олег || 1
|-
|-
-
| align="center"|18 || [[Участник:SdvAnd|Шадриков Андрей]] || 3
+
| align="center"|18 || Шабашев Федор || 3
|-
|-
-
|}
+
| align="center"|19 || [[Участник:SdvAnd|Шадриков Андрей]] || 3
 +
|-
 +
| align="center"|20 || Новиков Максим (420) || 1
 +
|-
 +
| align="center"|21 || Шахуро Влад (420) || 2
 +
|-
 +
| align="center"|22 || Грингауз Александр (320) || 3
 +
|-
 +
| align="center"|22 || Ибадов Тимур (420) || 1
 +
|- |}

Текущая версия

Содержание


Начало выполнения задания: 12 февраля 2014 г.
Срок сдачи: 26 февраля 2014 г. (среда), 23:59.

Среда для выполнения задания — MATLAB.


Вероятностные модели посещаемости курса

Рассмотрим модель посещаемости студентами одного курса лекции. Пусть аудитория данного курса состоит из студентов профильной кафедры, а также студентов других кафедр. Обозначим через a количество студентов, распределившихся на профильную кафедру, а через b — количество студентов других кафедр на курсе. Пусть студенты профильной кафедры посещают курс с некоторой вероятностью p_1, а студенты остальных кафедр — с вероятностью p_2. Обозначим через c количество студентов на данной лекции. Тогда случайная величина c|a,b есть сумма двух случайных величин, распределенных по биномиальному закону B(a,p_1) и B(b,p_2) соответственно. Пусть далее на лекции по курсу ведется запись студентов. При этом каждый студент записывается сам, а также, быть может, записывает своего товарища, которого на лекции на самом деле нет. Пусть студент записывает своего товарища с некоторой вероятностью p_3. Обозначим через d общее количество записавшихся на данной лекции. Тогда случайная величина d|c представляет собой сумму c и случайной величины, распределенной по биномиальному закону B(c,p_3). Для завершения задания вероятностной модели осталось определить априорные вероятности для a и для b. Пусть обе эти величины распределены равномерно в своих интервалах [a_{min},a_{max}] и [b_{min},b_{max}] (дискретное равномерное распределение). Таким образом, мы определили следующую вероятностную модель:
Модель 1

p(a,b,c,d)=p(d|c)p(c|a,b)p(a)p(b),

d|c \sim c + B(c,p_3),
c|a,b \sim B(a,p_1) + B(b,p_2),
a \sim R[a_{min},a_{max}],
b \sim R[b_{min},b_{max}].

Графическая модель для вероятностной модели 1
Графическая модель для вероятностной модели 1


Рассмотрим несколько упрощенную версию модели 1. Известно, что биномиальное распределение B(n,p) при большом количестве испытаний и маленькой вероятности успеха может быть с высокой точностью приближено пуассоновским распределением Poiss(\lambda) с \lambda = np. Известно также, что сумма двух пуассоновских распределений с параметрами \lambda_1 и \lambda_2 есть пуассоновское распределение с параметром \lambda_1+\lambda_2 (для биномиальных распределений аналогичное неверно). Таким образом, мы можем сформулировать вероятностную модель, которая является приближенной версией модели 1:
Модель 2
p(a,b,c,d)=p(d|c)p(c|a,b)p(a)p(b),
d|c \sim c + B(c,p_3),
c|a,b \sim Poiss(ap_1+bp_2),
a \sim R[a_{min},a_{max}],
b \sim R[b_{min},b_{max}].


Рассмотрим теперь модель посещаемости нескольких лекций курса. Будем считать, что посещаемости отдельных лекций являются независимыми. Тогда:
Модель 3

p(a,b,c_1,\dots,c_N,d_1,\dots,d_N)=\prod_{n=1}^Np(d_n|c_n)p(c_n|a,b)p(a)p(b),

d_n|c_n \sim c_n + B(c_n,p_3),
c_n|a,b \sim B(a,p_1) + B(b,p_2),
a \sim R[a_{min},a_{max}],
b \sim R[b_{min},b_{max}].

Графическая модель для вероятностной модели 3
Графическая модель для вероятностной модели 3


По аналогии с моделью 2 можно сформулировать упрощенную модель для модели 3:
Модель 4
p(a,b,c_1,\dots,c_N,d_1,\dots,d_N)=\prod_{n=1}^Np(d_n|c_n)p(c_n|a,b)p(a)p(b),
d_n|c_n \sim c_n + B(c_n,p_3),
c_n|a,b \sim Poiss(ap_1+bp_2),
a \sim R[a_{min},a_{max}],
b \sim R[b_{min},b_{max}].


Задание состоит из трех вариантов. Распределение студентов по вариантам см. ниже.

Вариант 1

Рассматривается модель 2 с параметрами a_{min}=15, a_{max}=30, b_{min}=250, b_{max}=350, p_1 = 0.5, p_2 = 0.05, p_3 = 0.5. Провести на компьютере следующие исследования:

  1. Найти математические ожидания и дисперсии априорных распределений для всех параметров a, b, c, d.
  2. Пронаблюдать, как происходит уточнение прогноза для величины c по мере прихода новой косвенной информации. Для этого построить графики и найти мат.ожидание и дисперсию для распределений p(c), p(c|b), p(c|a,b), p(c|a,b,d) при параметрах a,b,d, равных мат.ожиданиям своих априорных распределений, округленных до ближайшего целого.
  3. Определить, какая из величин a,b,d вносит больший вклад в уточнение прогноза для величины c (в смысле дисперсии распределения). Для этого убедиться в том, что \mathbb{D}[c|d]<\mathbb{D}[c|b] и \mathbb{D}[c|d]<\mathbb{D}[c|a] для любых допустимых значений a,b,d. Найти множество точек (a,b) таких, что \mathbb{D}[c|b]<\mathbb{D}[c|a]. Являются ли множества \{(a,b)|\mathbb{D}[c|b]<\mathbb{D}[c|a]\} и \{(a,b)|\mathbb{D}[c|b]\ge\mathbb{D}[c|a]\} линейно разделимыми?
  4. Провести временные замеры по оценке всех необходимых распределений p(c),p(c|a),p(c|b),p(c|d),p(c|a,b),p(c|a,b,d),p(d).
  5. Провести исследования из пп. 1-4 для точной модели 1 и сравнить результаты с аналогичными для модели 2. Привести пример оценки параметра, в котором разница между моделью 1 и 2 проявляется в большой степени.

Взять в качестве диапазона допустимых значений для величины c интервал [0,a_{max}+b_{max}], а для величины d — интервал [0,2*(a_{max}+b_{max})].

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

Вариант 2

Рассматривается модель 2 с параметрами a_{min}=15, a_{max}=30, b_{min}=250, b_{max}=350, p_1 = 0.5, p_2 = 0.05, p_3 = 0.5. Провести на компьютере следующие исследования:

  1. Найти математические ожидания и дисперсии априорных распределений для всех параметров a, b, c, d.
  2. Пронаблюдать, как происходит уточнение прогноза для величины b по мере прихода новой косвенной информации. Для этого построить графики и найти мат.ожидание и дисперсию для распределений p(b), p(b|a), p(b|a,d) при параметрах a,d, равных мат.ожиданиям своих априорных распределений, округленных до ближайшего целого.
  3. Определить, при каких соотношениях параметров p_1,p_2 изменяется относительная важность параметров a,b для оценки величины c. Для этого найти множество точек \{(p_1,p_2)|\mathbb{D}[c|b]<\mathbb{D}[c|a]\} при a,b, равных мат.ожиданиям своих априорных распределений, округленных до ближайшего целого. Являются ли множества \{(p_1,p_2)|\mathbb{D}[c|b]<\mathbb{D}[c|a]\} и \{(p_1,p_2)|\mathbb{D}[c|b]\ge\mathbb{D}[c|a]\} линейно разделимыми?
  4. Провести временные замеры по оценке всех необходимых распределений p(c),p(c|a),p(c|b),p(b|a),p(b|a,d),p(d).
  5. Провести исследования из пп. 1-4 для точной модели 1 и сравнить результаты с аналогичными для модели 2. Привести пример оценки параметра, в котором разница между моделью 1 и 2 проявляется в большой степени.

Взять в качестве диапазона допустимых значений для величины c интервал [0,a_{max}+b_{max}], а для величины d — интервал [0,2*(a_{max}+b_{max})].

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

Вариант 3

Рассматривается модель 4 с параметрами a_{min}=15, a_{max}=30, b_{min}=250, b_{max}=350, p_1 = 0.5, p_2 = 0.05, p_3 = 0.5, N = 50. Провести на компьютере следующие исследования:

  1. Найти математические ожидания и дисперсии априорных распределений для всех параметров a, b, c_n, d_n.
  2. Реализовать генератор выборки d_1,\dots,d_N из модели при заданных значениях параметров a,b.
  3. Пронаблюдать, как происходит уточнение прогноза для величины b по мере прихода новой косвенной информации. Для этого построить графики и найти мат.ожидание и дисперсию для распределений p(b), p(b|d_1), \dots, p(b|d_1,\dots,d_N), где выборка d_1,\dots,d_N 1) сгенерирована из модели при параметрах a,b, равных мат.ожиданиям своих априорных распределений, округленных до ближайшего целого и 2) d_1=\dots=d_N, где d_n равно мат.ожиданию своего априорного распределения, округленного до ближайшего целого. Провести аналогичный эксперимент, если дополнительно известно значение a. Сравнить результаты двух экспериментов.
  4. Провести временные замеры по оценке всех необходимых распределений p(c_n),p(d_n),p(b|d_1,\dots,d_n),p(b|a,d_1,\dots,d_n).
  5. Провести исследования из пп. 1-4 для точной модели 3 и сравнить результаты с аналогичными для модели 4.

Взять в качестве диапазона допустимых значений для величины c интервал [0,a_{max}+b_{max}], а для величины d — интервал [0,2*(a_{max}+b_{max})].

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

Оформление задания

Выполненное задание следует отправить письмом по адресу bayesml@gmail.com с заголовком письма «[ГМ14] Задание 1 <ФИО>». Убедительная просьба присылать выполненное задание только один раз с окончательным вариантом. Также убедительная просьба строго придерживаться заданных ниже прототипов реализуемых функций.

Присланный вариант задания должен содержать в себе:

  • Текстовый файл в формате PDF с указанием ФИО и номера варианта, содержащий описание всех проведенных исследований.
  • Архив, содержащий все исходные коды с необходимыми комментариями.

Исходные коды должны включать в себя реализацию оценки распределений в виде отдельных функций (отдельных m-файлов). Прототип для функции оценки распределения p(c|a,d) для модели 2 имеет следующий вид:

Оценка распределения p(c|a,d) для модели 2
[p, c, m, v] = p2c_ad(a, d, params)
ВХОД
a — значение параметра a;
d — значение параметра d;
params — набор параметров вероятностной модели, структура с полями 'amin', 'amax', 'bmin', 'bmax', 'p1', 'p2', 'p3';
ВЫХОД
p — распределение вероятности, вектор-столбец длины length(c);
c — носитель распределения, вектор-столбец;
m — математическое ожидание распределения;
v — дисперсия распределения.

Прототипы функций для других распределений выглядят аналогично. Если в распределении переменных до или после | несколько, то в названии функции они идут в алфавитном порядке. Функция для оценки распределения p(b|a,d_1,\dots,d_N) для модели 3 имеет название p3b_ad, а входной параметр d является одномерным массивом длины N.

Генерация из распределения p(d_1,\dots,d_N|a,b) для модели 3
d = m3_generate(N, a, b, params)
ВХОД
N — количество лекций;
a — значение параметра a;
b — значение параметра b;
params — набор параметров вероятностной модели, структура с полями 'amin', 'amax', 'bmin', 'bmax', 'p1', 'p2', 'p3';
ВЫХОД
d — значения d_1,\dots,d_N, вектор-столбец длины N.

Распределение студентов по вариантам

№ п/п Студент Вариант
1 Алешин Илья 1
2 Антипов Алексей 1
3 Арбузова Дарья 2
4 Горелов Алексей 2
5 Зиннурова Эльвира 1
6 Корольков Михаил 3
7 Ломов Никита 1
8 Львов Сергей 2
9 Найдин Олег 2
10 Никифоров Андрей 1
11 Новиков Александр 3
12 Петров Григорий 2
13 Подоприхин Дмитрий 3
14 Рыжков Александр 3
15 Сокурский Юрий 2
16 Ульянов Дмитрий 3
17 Харациди Олег 1
18 Шабашев Федор 3
19 Шадриков Андрей 3
20 Новиков Максим (420) 1
21 Шахуро Влад (420) 2
22 Грингауз Александр (320) 3
22 Ибадов Тимур (420) 1
Личные инструменты