Редактирование: МОТП, Билеты (2009)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 65 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
= Часть 1 (Ветров) = | = Часть 1 (Ветров) = | ||
- | == Метод максимального правдоподобия. Его достоинства и недостатки == | + | == Метод максимального правдоподобия. Его достоинства и недостатки.== |
- | * [http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D1%80%D0%B0%D0%B2%D0%B4%D0%BE%D0%BF%D0%BE%D0%B4%D0%BE%D0%B1%D0%B8%D1%8F | + | * [http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D1%80%D0%B0%D0%B2%D0%B4%D0%BE%D0%BF%D0%BE%D0%B4%D0%BE%D0%B1%D0%B8%D1%8F вики:Метод максимального правдоподобия] |
- | * [http://www.nsu.ru/mmf/tvims/chernova/ms/lec/node14.html | + | * [http://www.nsu.ru/mmf/tvims/chernova/ms/lec/node14.html метода макс. правдоподобия по Черновой из НГУ] |
- | + | ''' Метод максимального правдоподобия ''' -- метод оценивания неизвестного параметра путём максимизации функции правдоподобия: <math>f_x (x|\theta) = \prod_{i=1}^n f_x(x_i | \theta)</math> для независимой выборки n величин | |
- | + | ||
+ | <u>Недостатки:</u> | ||
* нужно знать априорное распределение (с точностью до параметров) наблюдаемой величины | * нужно знать априорное распределение (с точностью до параметров) наблюдаемой величины | ||
* хорошо применим при допущении, что <math>n \rightarrow \infty </math> (асимптотически оптимален), что в реальности не так | * хорошо применим при допущении, что <math>n \rightarrow \infty </math> (асимптотически оптимален), что в реальности не так | ||
* проблема выбора структурных параметров, позволяющих избегать переобучения (проблема вообще всех методов машинного обучения) | * проблема выбора структурных параметров, позволяющих избегать переобучения (проблема вообще всех методов машинного обучения) | ||
- | * необходима [http://ru.wikipedia.org/wiki/Регуляризация_(математика) регуляризация] метода | + | * необходима [http://ru.wikipedia.org/wiki/Регуляризация_(математика) регуляризация] метода |
- | == Решение несовместных СЛАУ == | + | ==Решение несовместных СЛАУ.== |
В статистике, машинном обучении и теории обратных задач под регуляризацией понимают добавление некоторой дополнительной информации к условию с целью решить некорректно поставленную задачу или предотвратить переобучение. | В статистике, машинном обучении и теории обратных задач под регуляризацией понимают добавление некоторой дополнительной информации к условию с целью решить некорректно поставленную задачу или предотвратить переобучение. | ||
- | + | '''Несовместная СЛАУ''' -- система линейных уравнений, не имеющая ни одного решения. | |
- | + | '''Совместная СЛАУ''' -- система линейных уравнений, имеющая хотя бы одно решение. | |
- | + | ''' Ридж-регуляризация''' (ридж-регрессия, [http://en.wikipedia.org/wiki/Tikhonov_regularization регуляризация Тихонова]) матрицы <math>A^T A</math> -- матрица <math>A^T A + \lambda I</math>, где <math>\lambda</math> -- коэффициент регуляризации. Всегда невырождена при <math>\lambda > 0</math> | |
- | + | ''' Нормальное псевдорешение ''' СЛАУ <math>Ax = b</math> -- вектор <math> x = (A^T A + \lambda I )^{-1} A^T b </math> | |
* всегда единственно | * всегда единственно | ||
* при небольших <math>\lambda</math> определяет псевдорешение с наименьшей нормой | * при небольших <math>\lambda</math> определяет псевдорешение с наименьшей нормой | ||
* любое псевдорешение имеет минимальную невязку | * любое псевдорешение имеет минимальную невязку | ||
- | </div> | ||
- | == Задача восстановления линейной регрессии. Метод наименьших квадратов == | + | == Задача восстановления линейной регрессии. Метод наименьших квадратов.== |
* [http://www.nsu.ru/mmf/tvims/chernova/ms/lec/node60.html лекции Черновой из НГУ] | * [http://www.nsu.ru/mmf/tvims/chernova/ms/lec/node60.html лекции Черновой из НГУ] | ||
- | * [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7 | + | * [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7 вики:Регрессионный анализ] |
- | '''Задача регрессионного анализа (неформально)' | + | '''Задача регрессионного анализа (неформально)'''. |
- | + | Предположим имеется зависимость между неизвестной нам случайно величиной X (мы судим о ней по наблюдаемым признакам, т.е. по случайной выборке) и некоторой переменной (параметром) t. | |
- | + | '''Задача регрессионного анализа''' — определение наличия и характера (математического уравнения, описывающего зависимость) связи между переменными. В случае линейной регрессии, зависимость X от параметра t проявляется в изменении средних значений Y при изменении t (хотя при каждом фиксированном значении t величина X остается случайной величиной). | |
- | + | Искомая зависимость среднего значения X от значений Z обозначается через функцию f(t): <math>E(X | Z = t)=f(t).</math> Проводя серии экспериментов, требуется по значениям t1,...tn и X1,...,Xn оценить как можно точнее функцию f(t). | |
- | '''Пример''' (''простой пример на пальцах''): [http://en.wikipedia.org/wiki/Linear_Regression#Example Linear Regression Example] | + | Однако, наиболее простой и изученной является линейная регрессия, в которой неизвестные настраиваемые параметры (w<sub>j</sub>) входят в решающее правило '''линейно''' с коэффициентами <math>\psi_j(x)</math>: <math>y(x,w)=\sum_{j=1}^m w_j \psi_j(x)=w^T \psi(x)</math> |
+ | |||
+ | '''Пример''' (''простой пример на пальцах''): [http://en.wikipedia.org/wiki/Linear_Regression#Example Linear Regression Example] | ||
<math>S(t, \hat{t})</math> — функция потерь от ошибки. ''На пальцах: берем найденную путем регрессии функцию <math>\hat{t}(x)</math> и сравниваем её выдачу на тех же наборах <math>x</math>, что и заданные результаты эксперимента <math>t(x)</math>.'' | <math>S(t, \hat{t})</math> — функция потерь от ошибки. ''На пальцах: берем найденную путем регрессии функцию <math>\hat{t}(x)</math> и сравниваем её выдачу на тех же наборах <math>x</math>, что и заданные результаты эксперимента <math>t(x)</math>.'' | ||
* <math>S_1(t, \hat{t}) = (t - \hat{t})^2</math> | * <math>S_1(t, \hat{t}) = (t - \hat{t})^2</math> | ||
- | * <math>S_2(t, \hat{t}) = |t - \hat{t}|</math> | + | * <math>S_2(t, \hat{t}) = |t - \hat{t}|^2</math> |
* <math>S_3(t, \hat{t}) = \delta^{-1}(t - \hat{t})</math> | * <math>S_3(t, \hat{t}) = \delta^{-1}(t - \hat{t})</math> | ||
- | Основная задача — минимизировать эту функцию, что значит минимизировать <math>\mathbb{E} S(t, \hat{t}(x,w)) = \int\int S(t, \hat{t}(x,w)) p(x,t) dx dt \rightarrow \min_{w}</math> | + | Основная задача — минимизировать эту функцию, что значит минимизировать <math>\mathbb{E} S(t, \hat{t}(x,w)) = \int\int S(t, \hat{t}(x,w)) p(x,t) dx dt \rightarrow \min_{w}</math> |
---- | ---- | ||
- | + | ''' Метод наименьших квадратов ''' — минимизация функции потери ошибки <math>S(t, \hat{t}) = (t - \hat{t})^2</math> | |
- | + | <u>Особенности квадратичной функции потерь:</u> | |
- | * | + | * <u>Достоинтсва</u> |
- | ** | + | ** гладкая (непрерывная и дифференцируемая) |
- | ** | + | ** решение может быть получено в явном виде |
- | * | + | * <u>Недостатки</u> |
- | ** | + | ** решение неустойчиво |
- | ** | + | ** не применима к задачам классификации |
- | == Задача восстановления линейной регрессии. Вероятностная постановка == | + | ==Задача восстановления линейной регрессии. Вероятностная постановка.== |
Представим регрессионную переменную как случайную величину с плотностью распределения <math>p(t|x)</math>. | Представим регрессионную переменную как случайную величину с плотностью распределения <math>p(t|x)</math>. | ||
- | В большинстве случаев предполагается нормальное распределение относительно некоторой точки | + | В большинстве случаев предполагается нормальное распределение относительно некоторой точки y(x) : <math>t = y(x) + \varepsilon~;~~\varepsilon \sim N(\varepsilon | 0, \sigma^2)</math>. |
- | Максимизируя правдоподобие (оно задается следующей формулой: <math>p(t|y)=\prod_{i=1}^n \dfrac{1}{\sqrt{2\pi\sigma^2}}\, \exp\left(-\dfrac{(t_i-y_i)^2}{2\sigma^2}\right) \rightarrow \max</math>), получаем эквивалентность данного метода методу наименьших квадратов, т. к. взяв логарифм от формулы выше, получаем: | ||
- | <math>\sum_{i=1}^n (t_i-y_i)^2 = \sum_{i=1}^n (t_i-w^T \phi (x_i))^2 \rightarrow \min_w</math> | ||
- | == | + | Максимизируя правдоподобие (оно задается следующей формулой: <math>p(t|y)=\prod_{i=1}^n \dfrac{1}{\sqrt{2\pi\sigma^2}}\, \exp\left(-\dfrac{(t_i-y_i)^2}{2\sigma^2}\right) \rightarrow \max</math>), получаем эквивалентность данного метода методу наименьших квадратов, т.к. взяв логарифм от формулы выше, получаем: |
+ | |||
+ | <math>\sum_{i=1}^n (t_i-y_i)^2 = \sum_{i=1}^n (t_i-w^T \phi (x_i))^2 \rightarrow \min_w</math> | ||
- | + | == Логистическая регрессия. Вероятностная постановка.== | |
+ | ''' Логистическая регрессия''' ([http://en.wikipedia.org/wiki/Logistic_regression en-wiki]) — метод [http://ru.wikipedia.org/wiki/Задача_классификации классификации объектов] на два класса, работающий при помощи логистической функции регрессии: <math>p(t|x, w) = \frac{1}{1 + e^{-t y(x)}}</math> ([http://en.wikipedia.org/wiki/Sigmoid_function сигмоид]). | ||
Эта функция является функцией правдоподобия по w и распределением вероятности по t, т.к. <math>\sum_t p(t|x,w)=1, \ \ p(t|x,w)>0</math>. | Эта функция является функцией правдоподобия по w и распределением вероятности по t, т.к. <math>\sum_t p(t|x,w)=1, \ \ p(t|x,w)>0</math>. | ||
- | == ЕМ-алгоритм для задачи разделения гауссовской смеси == | + | == ЕМ-алгоритм для задачи разделения гауссовской смеси.== |
Пусть имеется выборка <math>X \sim \sum_{j=1}^l w_j \mathcal{N} (x | \mu_j , \Sigma_j)</math>, где ''l'' - число компонент смеси. | Пусть имеется выборка <math>X \sim \sum_{j=1}^l w_j \mathcal{N} (x | \mu_j , \Sigma_j)</math>, где ''l'' - число компонент смеси. | ||
- | EM-алгоритм: | + | <u>EM-алгоритм:</u> |
- | # | + | # выбираем начальное приближение для параметров <math>\mu_j, \Sigma_j, w_j, j \isin [1, l]</math> |
- | # E-шаг | + | # E-шаг: вычисляем распределение скрытых переменных, которые определяют, к какой компоненте смеси на данном шаге отностися каждый объект |
- | # M-шаг | + | # M-шаг: с учетом вероятностей на предыдущем шаге пересчитываем коэффициенты начального шага |
- | # | + | # переход к E шагу до тех пор, пока не будет достигнута сходимость |
- | + | <u>недостатки:</u> | |
- | * (!) | + | * (!!) не позволяет определить количество компонент смеси (''l'') |
- | ** | + | ** величина ''l'' является структурным параметром |
- | * | + | * в зависимости от выбора начального приближения может сходиться к разным точкам |
- | * может сваливаться в локальный экстремум | + | * может сваливаться в локальный экстремум |
- | == Основные правила работы с вероятностями. Условная независимость случайных величин == | + | ==Основные правила работы с вероятностями. Условная независимость случайных величин.== |
- | + | ''' Случайная величина ''' -- это измеримая функция, заданная на каком-либо вероятностном пространстве. ([http://ru.wikipedia.org/wiki/%D0%A1%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D0%B0%D1%8F_%D0%B2%D0%B5%D0%BB%D0%B8%D1%87%D0%B8%D0%BD%D0%B0 вики]) | |
- | + | ''' Функция распределения ''' <math>F_X(x)</math> -- вероятность того, что случайная величина X меньше x: <math>F_X(x) = \mathbb{P}(X \leqslant x)</math> | |
- | + | ''' Плотность вероятности ''': | |
- | * | + | * в дискретном случае -- вероятность того, что X = x |
- | * | + | * в непрерывном случае -- производная функции распределения |
- | + | Пусть X, Y - случайные величины с плотностями вероятности <math>p(x), p(y)</math> | |
- | + | Случайные величины X,Y называются независимыми, если <math>p(x,y) = p(x) \cdot p(y)</math> | |
- | + | ''' Условная плотность ''' -- <math>p(x|y) = \frac{p(x,y)}{p(y)}</math> | |
- | * в дискретном случае | + | * в дискретном случае - вероятность того, что наступило событие x, при условие наступления события y |
- | + | <u>Правило суммирования:</u> пусть <math>A_1, \dots, A_k</math> -- k взаимоисключающих события, одно из которых обязательно наступает. Тогда | |
* <math>\mathbb{P}(A_i \cup A_j) = \mathbb{P}(A_i) + \mathbb{P}(A_j)</math> | * <math>\mathbb{P}(A_i \cup A_j) = \mathbb{P}(A_i) + \mathbb{P}(A_j)</math> | ||
* <math>\sum_{i=1}^k \mathbb{P}(A_i) = 1</math> | * <math>\sum_{i=1}^k \mathbb{P}(A_i) = 1</math> | ||
- | * | + | * формула полной вероятности: <math>\sum_{i=1}^k \mathbb{P}(B|A_i) = 1</math> |
- | + | ||
- | + | ||
Случайные величины называются '''условно независимыми''' от <math>z</math>, если <math>p(x,y|z) = p(x|z)p(y|z)</math> | Случайные величины называются '''условно независимыми''' от <math>z</math>, если <math>p(x,y|z) = p(x|z)p(y|z)</math> | ||
- | * | + | * это значит: вся информация о взаимосвязи между <math>x</math> и <math>y</math> содержится в <math>z</math> |
- | * | + | * из безусловной независимости не следует условная независимость |
- | * | + | * <u>основное свойство условно независимых величин</u>: <math>p(z|x,y) = \frac{1}{Z} \cdot \frac{p(z|x) p(z|y)}{p(z)}</math>, где <math>Z = p(x)p(y)p(z)</math> |
- | == Графические модели. Основные задачи, возникающие в анализе графических моделей == | + | == Графические модели. Основные задачи, возникающие в анализе графических моделей.== |
'''Графическая модель''' -- ориентированный или неориентированный граф, в котором вершины соответствуют переменным, а ребра - вероятностным отношениям, определяющим непосредственные зависимости. | '''Графическая модель''' -- ориентированный или неориентированный граф, в котором вершины соответствуют переменным, а ребра - вероятностным отношениям, определяющим непосредственные зависимости. | ||
Строка 134: | Строка 135: | ||
==Байесовские сети. Примеры.== | ==Байесовские сети. Примеры.== | ||
- | + | [http://ru.wikipedia.org/wiki/%D0%91%D0%B0%D0%B9%D0%B5%D1%81%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%81%D0%B5%D1%82%D1%8C_%D0%B4%D0%BE%D0%B2%D0%B5%D1%80%D0%B8%D1%8F На википедии] | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
== Марковские сети. Примеры.== | == Марковские сети. Примеры.== | ||
==Скрытые марковские модели. Обучение СММ с учителем.== | ==Скрытые марковские модели. Обучение СММ с учителем.== | ||
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%BA%D1%80%D1%8B%D1%82%D0%B0%D1%8F_%D0%BC%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D1%8C На википедии] | * [http://ru.wikipedia.org/wiki/%D0%A1%D0%BA%D1%80%D1%8B%D1%82%D0%B0%D1%8F_%D0%BC%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D1%8C На википедии] | ||
- | * [http://ru.wikibooks.org/wiki/%D0%A1%D0%BA%D1%80%D1%8B%D1%82%D1%8B%D0%B5_%D0%BC%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8 | + | * [http://ru.wikibooks.org/wiki/%D0%A1%D0%BA%D1%80%D1%8B%D1%82%D1%8B%D0%B5_%D0%BC%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8 Викибуки] |
+ | * '''Лекция 3, стр. 9-28''' | ||
+ | * [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%92%D0%B8%D1%82%D0%B5%D1%80%D0%B1%D0%B8 Алгоритм Витерби] - очень хорошо для понимания зачем все это надо | ||
+ | * [http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Динамическое программирование] | ||
- | <br | + | '''Общие сведения'''<br> |
- | '''Скрытая Марковская модель | + | ''Динамическое программирование'' в математике и теории вычислительных систем — метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами, который намного эффективнее, чем решение «в лоб». <br> |
- | + | <br> | |
- | + | ||
- | + | ''Скрытая Марковская модель'' (первого порядка) — это вероятностная модель последовательности, которая | |
- | + | * Состоит из набора наблюдаемых переменных <math> X = {x_1 , \dots , x_N }, n_n \in R_d</math> и латентных (скрытых) переменных <math>T = {t_1, \dots, t_N },\;t_n \in \{0, 1\}^K,\;\sum_{j = 1}^{K}t_{nj}=1</math>. | |
+ | * Латентные переменные T являются бинарными и кодируют K состояний, поэтому их иногда называют переменными состояния. | ||
+ | * Значение наблюдаемого вектора <math>x_n</math> , взятого в момент времени <math>n</math>, зависит только от скрытого состояния <math>t_n</math>, которое в свою очередь зависит только от скрытого состояния в предыдущий момент времени <math>t_{n-1}</math>. | ||
+ | * Для полного задания модели достаточно задать все условные распределения вида <math>p(x_n |t_n ),\;p(t_n |t_{n-1})</math> и априорное распределение <math>p(t_1)</math>. | ||
Пусть имеется <math>K</math> возможных состояний. Закодируем состояние в каждый момент времени <math>n</math> бинарным вектором <math>t_n = (t_{n1},\dots, t_{nK})</math>, где <math>t_{nj} = 1</math>, если в момент <math>n</math> модель находится в состоянии <math>j</math> и <math>t_{nj} = 0</math>, иначе. | Пусть имеется <math>K</math> возможных состояний. Закодируем состояние в каждый момент времени <math>n</math> бинарным вектором <math>t_n = (t_{n1},\dots, t_{nK})</math>, где <math>t_{nj} = 1</math>, если в момент <math>n</math> модель находится в состоянии <math>j</math> и <math>t_{nj} = 0</math>, иначе. | ||
Строка 159: | Строка 160: | ||
p(t_n |t_{n-1}) = \prod_{i=1}^K\prod_{j=1}^K A_{ij}^{t_{n-1,i}t_{nj}} | p(t_n |t_{n-1}) = \prod_{i=1}^K\prod_{j=1}^K A_{ij}^{t_{n-1,i}t_{nj}} | ||
</math> | </math> | ||
- | Пусть в первый момент времени <math>p(t_{1j} = 1) = \pi_j</math>. Тогда <math> p(t_1) = \prod_{j=1}^K \pi_j^{t_{1j}}</math> | + | Пусть в первый момент времени <math>p(t_{1j} = 1) = \pi_j</math>. Тогда |
+ | <math> | ||
+ | p(t_1) = \prod_{j=1}^K \pi_j^{t_{1j}} | ||
+ | </math> | ||
* Хотя матрица A может быть произвольного вида с учетом ограничений на неотрицательность и сумму элементов строки, с точки зрения СММ представляет интерес диагональное преобладание матрицы перехода. | * Хотя матрица A может быть произвольного вида с учетом ограничений на неотрицательность и сумму элементов строки, с точки зрения СММ представляет интерес диагональное преобладание матрицы перехода. | ||
Строка 167: | Строка 171: | ||
* Условное распределение <math>p(x_n |t_n)</math> определяется текущим состоянием <math>t_n</math> | * Условное распределение <math>p(x_n |t_n)</math> определяется текущим состоянием <math>t_n</math> | ||
* Обычно предполагают, что оно нам известно с точностью до параметров <math>\phi_k,\;k \in \{1,\dots, K\}</math>, т.е. если <math>t_{n1} = 1</math>, то <math>x_n</math> взят из распределения <math>p(x_n |\phi_1 )</math>, если <math>t_{n2} = 1</math>, то <math>x_n</math> взят из распределения <math>p(x_n |\phi_2 )</math>, и т.д. | * Обычно предполагают, что оно нам известно с точностью до параметров <math>\phi_k,\;k \in \{1,\dots, K\}</math>, т.е. если <math>t_{n1} = 1</math>, то <math>x_n</math> взят из распределения <math>p(x_n |\phi_1 )</math>, если <math>t_{n2} = 1</math>, то <math>x_n</math> взят из распределения <math>p(x_n |\phi_2 )</math>, и т.д. | ||
- | * Таким образом <math> p(x_n |t_n) = \prod_{j=1}^K(p(x_n |\phi_k ))^{t_{nk}} </math> | + | * Таким образом |
+ | <math> | ||
+ | p(x_n |t_n) = \prod_{j=1}^K(p(x_n |\phi_k ))^{t_{nk}} | ||
+ | </math> | ||
Обозначим полный набор параметров <math>\Theta = \{\pi, A, \phi\}</math>. | Обозначим полный набор параметров <math>\Theta = \{\pi, A, \phi\}</math>. | ||
- | ''' | + | '''Собственно, билет'''<br> |
- | + | ||
- | + | ||
- | + | ||
- | <br | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
* Пусть известна некоторая последовательность наблюдений <math>X</math> и набор параметров СММ <math>\Theta</math>. Требуется определить наиболее вероятную последовательность состояний <math>T</math>, т.е. найти <math>arg\;max_T p(T|X, \Theta)</math>. | * Пусть известна некоторая последовательность наблюдений <math>X</math> и набор параметров СММ <math>\Theta</math>. Требуется определить наиболее вероятную последовательность состояний <math>T</math>, т.е. найти <math>arg\;max_T p(T|X, \Theta)</math>. | ||
* Заметим, что <math>p(X|\Theta)</math> не зависит от <math>T</math>, поэтому <math>arg\;max_T p(T|X, \Theta) = arg\;max_T \frac{p(X, T|\Theta)}{p(X|\Theta)} = arg\;max_T p(X, T|\Theta) = arg\;max_T log\,p(X, T|\Theta)</math>. | * Заметим, что <math>p(X|\Theta)</math> не зависит от <math>T</math>, поэтому <math>arg\;max_T p(T|X, \Theta) = arg\;max_T \frac{p(X, T|\Theta)}{p(X|\Theta)} = arg\;max_T p(X, T|\Theta) = arg\;max_T log\,p(X, T|\Theta)</math>. | ||
* Но это же классическая задача динамического программирования! | * Но это же классическая задача динамического программирования! | ||
<br> | <br> | ||
- | ''Алгоритм Витерби'' | + | ''Алгоритм Витерби''<br> |
- | + | ||
Логарифм совместной плотности по распределению: | Логарифм совместной плотности по распределению: | ||
<math> | <math> | ||
Строка 201: | Строка 199: | ||
== ЕМ-алгоритм и его применение в скрытых марковских моделях.== | == ЕМ-алгоритм и его применение в скрытых марковских моделях.== | ||
- | |||
- | === Максимум неполного правдоподобия === | ||
- | |||
- | * Предположим имеется графическая модель в которой известная только часть значений переменных. | ||
- | * Атомарные распределения известны с точностью до <math>\theta</math> | ||
- | * Требуется оценить параметры по наблюдаемым величинам с помощью метода максимального правдоподобия т.е найти <math> \theta_{ML} = \arg \max(p(X|\theta)) </math> | ||
- | * По правилу суммирования вероятностей неполное правдоподобие может быть получено в виде суммирования по скрытым переменным полного правдоподобия <math>p(X|\theta)=\sum_T p(X,T|\theta)</math> | ||
- | * Во многих случаях(в частности в байесовских сетях) подсчет полного правдоподобия тривиален | ||
- | * При оптимизации правдоподобия удобно переходить к логарифму, в частности ранее в курсе мы получили явные формулы для <math>\arg \max_\theta(p(X|\theta)=\arg \max_\theta log(p(X|\theta)</math> в СММ | ||
- | * Прямая оптимизация логарифма неполного правдоподобия очень затруднительн, даже в итерационной форме, т.к. фунционал имеет вид "логарифма суммы",в то время как удобно оптимизировать "сумму логарифов". | ||
- | |||
- | === Схема ЕМ-алгоритма === | ||
- | * на входе: выборка X, зависящая от набора параметров <math>\theta</math> | ||
- | * Инициализируем <math>\theta</math> некоторыми начальным приближением | ||
- | * Е-шаг: оцениваем распределение скрытой компоненты | ||
- | <math> p(T|X,\theta_{old})=\frac{p(X|T,\theta_{old})}{\sum_T p(X,T|\theta_{old})} </math> | ||
- | * M-шаг оптимизируем | ||
- | <math>\mathbb E_{T|X,\theta_{old}} log(p(X,T|\theta))=\sum_T p(X|T,\theta_{old})log( p(X,t|\theta)) \to \max_{\theta} </math> <br> | ||
- | Если бы мы точно знали значение <math>T=T_0</math>, то вместо мат. ожидания по всевозможным(с учетом наблюдаемых данных) <math> T|X,\theta_{old} </math> мы бы оптимизировали <math> log(p(X,T_0|\theta)) </math> | ||
- | *Переход к E-шагу пока процесс не сойдется | ||
- | *Оптимизация проводится итерационно методом покоординатного спуска: на каждой итерации последовательно уточняются возможные значения Т (Е-шаг), а потом пересчитываются значения <math>\theta</math> (М-шаг) | ||
- | *Во многих случаях на М-шаге можно получить явные формулы, т.к. там происходит оптимизация выпуклой комбинации логарифмов полных правдоподобий, имеющей вид взвешенной "суммы лоагрифмов" | ||
- | |||
- | |||
- | === EM-алгоритм для смеси гауссовских распределений === | ||
- | см. пункт 1.6 | ||
- | недостатки: | ||
- | * В зависимости от выбора начального приближения может сходится к разным точкам | ||
- | * ЕМ-алгоритм находит локальный экстремум, в котором значение правдоподобия может оказаться намного ниже, чем в глобальном варианте | ||
- | * ЕМ-алгоритм не позволяет определить количество компонентов смеси l | ||
- | * !!Величина l является структурным параметром(в начале лекций говорилось о них) | ||
- | |||
== Условная независимость в скрытых марковских моделях. Алгоритм «вперед-назад».== | == Условная независимость в скрытых марковских моделях. Алгоритм «вперед-назад».== | ||
- | * ''Лекция 4, Слайды 16-28'' | ||
- | * [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B2%D0%BF%D0%B5%D1%80%D1%91%D0%B4-%D0%BD%D0%B0%D0%B7%D0%B0%D0%B4 вики] | ||
- | |||
- | '''Алгоритм «вперёд-назад»''' -- алгоритм для вычисления апостериорных вероятностей последовательности состояний при наличии последовательности наблюдений. Или по другому, алгоритм для того, чтобы вычислить вероятность специфической последовательности наблюдений. Это работает в контексте скрытых Марковских моделей. | ||
- | * работает за линейное по количеству наблюдаемых переменных (<math>N</math>) | ||
- | |||
- | Алгоритм включает три шага: | ||
- | # вычисление прямых вероятностей | ||
- | # вычисление обратных вероятностей | ||
- | # вычисление сглаженных значений | ||
- | |||
==Метод релевантных векторов в задаче восстановления регрессии.== | ==Метод релевантных векторов в задаче восстановления регрессии.== | ||
- | Лекция 5 Ветров. | ||
- | |||
== Метод релевантных векторов в задаче классификации.== | == Метод релевантных векторов в задаче классификации.== | ||
- | Лекция 5 Ветров. | ||
- | |||
- | [http://courses.graphicon.ru/files/courses/smisa/2008/lectures/lecture11.pdf Еще слайды Ветрова, но не из этого круса] от того более понятными не становятся | ||
- | |||
== Метод главных компонент.== | == Метод главных компонент.== | ||
Строка 260: | Строка 209: | ||
* проекция данных на гиперплоскость с наименьшей ошибкой проектирования | * проекция данных на гиперплоскость с наименьшей ошибкой проектирования | ||
* поиск проекции на гиперплоскость с сохранением большей части дисперсии в данных | * поиск проекции на гиперплоскость с сохранением большей части дисперсии в данных | ||
- | |||
- | [http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82 Википедия: Метод главных компонент] | ||
==Вероятностная формулировка метода главных компонент.== | ==Вероятностная формулировка метода главных компонент.== | ||
Строка 306: | Строка 253: | ||
== Нелинейные методы уменьшения размерности. Ассоциативные нейронные сети и GTM.== | == Нелинейные методы уменьшения размерности. Ассоциативные нейронные сети и GTM.== | ||
- | '' Лекция 6, слайды 51-55 '' | ||
= Часть 2 (Рудаков) = | = Часть 2 (Рудаков) = | ||
Строка 365: | Строка 311: | ||
Для начала, поговорим об '''алгоритмах голосования'''. Пусть для каждого класса <math>c \in Y</math> построено множество логических закономерностей (правил), специализирующихся на различении объектов данного класса: | Для начала, поговорим об '''алгоритмах голосования'''. Пусть для каждого класса <math>c \in Y</math> построено множество логических закономерностей (правил), специализирующихся на различении объектов данного класса: | ||
- | <math>R_c = | + | <math>R_c = { \varphi_c^t : X \rightarrow {0, 1} | t = 1, . . . , T_c}</math>, где <math>T_c</math> - количество классов свойств. |
Считается, что если <math>\varphi_c^t (x) = 1</math>, то правило <math>\varphi_c^t</math> относит объект <math>x \in X</math> к классу c. Если же <math>\varphi_c^t(x) = 0 </math>, то правило <math>\varphi_c^t</math> воздерживается от классификации объекта x. | Считается, что если <math>\varphi_c^t (x) = 1</math>, то правило <math>\varphi_c^t</math> относит объект <math>x \in X</math> к классу c. Если же <math>\varphi_c^t(x) = 0 </math>, то правило <math>\varphi_c^t</math> воздерживается от классификации объекта x. | ||
Строка 456: | Строка 402: | ||
* совокупность из всех подмножеств из k элементов. его мощность: <math>C^n_k</math> | * совокупность из всех подмножеств из k элементов. его мощность: <math>C^n_k</math> | ||
- | ''' Функция близости ''' <math>\mathcal{N} | + | ''' Функция близости ''' <math>\mathcal{N}(\tilde w S, \tilde w S_i)</math> -- задает расстояние между <math>\tilde w</math> частями распознаваемого объекта <math>S</math> и эталонного объекта <math>S_i</math>. В дальнейшем рассматриваются только такие функции, <math>\mathcal{N}</math>, которые принимают значения 0 или 1 |
<u>Три вида функции близости:</u> | <u>Три вида функции близости:</u> | ||
- | # | + | # введем неотрицательные параметры <math>\varepsilon_i > 0 ~,~ i \in [1,n]</math>. Пусть <math>\tilde w S = \{\alpha_{u_1}, \dots, \alpha_{u_k}\}~,~~ \tilde w S_i = \{\alpha_{u_{i1}}, \dots, \alpha_{u_{ik}}\}</math>. Тогда <math>\mathcal{N}(\tilde w S, \tilde w S_i) = |
\begin{cases} | \begin{cases} | ||
- | 1,~~\rho(\alpha_{ | + | 1,~~\rho(\alpha_{u_j}, \alpha_{u_{ij}} \leqslant \varepsilon_{u_j})~~\forall j \in [1,k]\\ |
- | 0,~~ | + | 0,~~else |
\end{cases}</math> | \end{cases}</math> | ||
- | # | + | # введем дополнительно к п.1 параметра <math>\nu</math> такой, что <math>\mathcal{N}(\tilde w S, \tilde w S_i) = 1</math>, если не выполнено не больше, чем <math>\nu</math> описанных неравенств. при этом имеет смысл брать <math>0 \leqslant \nu \leqslant \left[\frac{q}{2} - 1\right] </math> |
- | # | + | # вместо <math>\nu</math> определяем <math>\nu'</math> так, что <math>\mathcal{N}(\tilde w S, \tilde w S_i) = 1</math>, если из k неравенств не выполнены r, причем <math>\frac{r}{k} < \nu'</math> |
- | + | ||
== Формулы вычисления оценок. Эвристические обоснования. == | == Формулы вычисления оценок. Эвристические обоснования. == | ||
Строка 472: | Строка 417: | ||
''' Формула вычисления оценок: ''' | ''' Формула вычисления оценок: ''' | ||
- | <math>\Gamma_1^j ( | + | <math>\Gamma_1^j (s) = \sum_{w \in \Omega} \sum_{k : P_j(s_k) = 1} \gamma_k \cdot p_w \cdot \mathcal{N}(s, s_k)</math>, где: |
- | * <math> | + | * <math>w \in \Omega</math> -- опорные множества |
- | * <math>P_j( | + | * <math>k : P_j(s_k) = 1</math> -- все объекты обучающей выборки, которые входят в данный класс |
- | * <math>\gamma_k</math> -- вес объекта | + | * <math>\gamma_k</math> -- вес объекта |
- | * <math> | + | * <math>p_w</math> -- вес опорного множества |
- | <math>\Gamma_0^j ( | + | <math>\Gamma_0^j (s) = \sum_{w \in \Omega} \sum_{k : P_j(s_k) = 0} \gamma_k \cdot p_w \cdot (1 - \mathcal{N}(s, s_k))</math>, где: |
- | * <math>P_j( | + | * <math>k : P_j(s_k) = 0</math> -- все объекты обучающей выборки, которые ''' не ''' входят в данный класс |
- | + | <math>\Gamma^j(s) = x_1 \cdot \Gamma_1^j (s) + x_2 \cdot \Gamma_0^j (s)</math>, где <math>x_1, x_2</math> -- коэффициенты, которые определяют работу с соответствующими характеристиками. | |
- | + | ||
- | <math>\Gamma^j( | + | |
== Задачи оптимизации АВО. Совместные подсистемы систем неравенств. == | == Задачи оптимизации АВО. Совместные подсистемы систем неравенств. == | ||
- | + | ||
- | + | [http://www.mipt.ru/nauka/51conf/dokl/In_prac_fupm/m_3rhk32/m_3rhknp.html оптимизация АВО по метрикам] | |
== Функционалы качества. Сложность моделей алгоритмов и проблема переобучения. == | == Функционалы качества. Сложность моделей алгоритмов и проблема переобучения. == | ||
'''Функционал качества''' алгоритма. | '''Функционал качества''' алгоритма. | ||
- | Пусть задана таблица контрольных объектов (множество объектов, на которых мы будет проверять качество работы нашего алгоритма распознавания). Для контрольных объектов мы должны знать, | + | Пусть задана таблица контрольных объектов (множество объектов, на которых мы будет проверять качество работы нашего алгоритма распознавания). Для контрольных объектов мы должны знать, как какому классу свойств относится каждый из объектов (иначе как мы будет проверять корректность работы нашего алгоритма). Подаем контрольные объекты на вход алгоритму. Доля правильных ответов, выданных алгоритмов - это и есть ''функционал качества''. |
Строка 503: | Строка 446: | ||
== Общие пространства начальных и финальных информаций. Задачи синтеза корректных алгоритмов. == | == Общие пространства начальных и финальных информаций. Задачи синтеза корректных алгоритмов. == | ||
- | [http://www.ccas.ru/frc/thesis/RudakovDocDisser.pdf Диссертация Рудакова], пункт 1.1 | ||
- | |||
В самой общей постановке задача синтеза алгоритмов преобразования информаций состоит в следующем. Имеется множество начальных информаций <math>\Im_i</math> и множество конечных информаций <math>\Im_j</math>. Требуется построить алгоритм реализующий отображение из <math>\Im_i</math> в <math>\Im_j</math>, удовлетворяющее заданной системе ограничений. | В самой общей постановке задача синтеза алгоритмов преобразования информаций состоит в следующем. Имеется множество начальных информаций <math>\Im_i</math> и множество конечных информаций <math>\Im_j</math>. Требуется построить алгоритм реализующий отображение из <math>\Im_i</math> в <math>\Im_j</math>, удовлетворяющее заданной системе ограничений. | ||
Строка 516: | Строка 457: | ||
[http://www.ccas.ru/frc/thesis/RudakovDocDisser.pdf Диссертация Рудакова], пункт 1.5 | [http://www.ccas.ru/frc/thesis/RudakovDocDisser.pdf Диссертация Рудакова], пункт 1.5 | ||
- | |||
- | '''Разрешимые''' задачи - это задачи, для которых множество допустимых отображений их <math>\mathfrak{I}_i</math> в <math>\mathfrak{I}_f</math> непусто, т.е. существуют семейства алгоритмов, содержащие их решения. | ||
- | Задача Z из множества задач <math>\mathfrak{Z} </math> называется ''полной'' относительно семейства <math>\mathfrak{M} </math> отображений из <math>\mathfrak{I}_i</math> в <math>\mathfrak{I}_f</math>, если в <math>\mathfrak{M} </math> содержатся допустимые отображения для всех задач из класса эквивалентности, содержащего Z. | ||
- | Задача Z называется '''регулярной''', если для нее существует семейство отображений <math>\mathfrak{M} </math>, относительно которого она полна. | ||
- | |||
- | '''Регулярность по Журавлеву''': | ||
- | Пусть есть <math>q</math> объектов и <math>l</math> классов и | ||
- | <math>\hat{I}=||I_{ij}||_{q \times l}</math> - матрица информации и <math> \hat {\tilde I} = || {\tilde I}_{ij}||_{q \times l}</math> - матрица правильных ответов. | ||
- | Задаче Z соответствует пара матриц: <math> Z \leftrightarrow (\hat I , \hat{\tilde I})</math>. | ||
- | Определение ''окрестности задачи по Журавлеву'' <math>O(Z)=\{Z^' |Z^' \leftrightarrow (\hat I , \hat{\tilde I}^')\}</math> - т.е. это множество задач <math>Z^'</math>, получающихся всевозможным варьированием матрицы правильных ответов. | ||
- | |||
- | * Разбиваем множество задач на классы эквивалентности. Задача называется регулярной если она разрешима и разрешимы все задачи из класса эквивалентности который она порождает. | ||
== Операции над алгоритмами. Расширение моделей. == | == Операции над алгоритмами. Расширение моделей. == | ||
Строка 542: | Строка 471: | ||
Диссертация Рудакова 1.3 + 1.5 пункты. | Диссертация Рудакова 1.3 + 1.5 пункты. | ||
Диссертация Рудакова, пункт 3.5 | Диссертация Рудакова, пункт 3.5 | ||
- | |||
- | |||
- | Модель алгоритмов <math>\mathfrak{M}</math> категории <math>\Phi_0</math> называется полной, если любая регулярная задача <math>Z</math> из множества <math>\mathfrak{Z}_{[R]}</math> полна относительно <math>\mathfrak{M}</math>, т.е. если для любой регулярной задачи <math>Z</math> модель алгоритмов от любой матрицы исходных информаций этой задачи приводит в множество конечных информаций. | ||
- | (т.е. в модели алгоритмов <math>\mathfrak{M}</math> для каждой регулярной задачи из множества <math>\mathfrak{Z}_{[R]}</math> содержится корректный алгоритм) | ||
== Дополнительные к прецедентам ограничения. Пример: перестановочность строк и столбцов в матрицах информации. == | == Дополнительные к прецедентам ограничения. Пример: перестановочность строк и столбцов в матрицах информации. == | ||
Строка 555: | Строка 480: | ||
Пусть рассматривается задача, в которой имеется информация о том, что порядок, в котором анализируются классы несущественен, и кроме прецедентных данных нет сведений о различии классов. | Пусть рассматривается задача, в которой имеется информация о том, что порядок, в котором анализируются классы несущественен, и кроме прецедентных данных нет сведений о различии классов. | ||
Универсальные ограничения, выражающие однородность классов, состоят в том, что отображение, реализуемое корректным алгоритмом, должно коммутировать со всеми подстановками столбцов (при любой перстановке столбцов в матрице информации точно так же должны переставляться столбцы в матрице, порожденной алгоритмом). | Универсальные ограничения, выражающие однородность классов, состоят в том, что отображение, реализуемое корректным алгоритмом, должно коммутировать со всеми подстановками столбцов (при любой перстановке столбцов в матрице информации точно так же должны переставляться столбцы в матрице, порожденной алгоритмом). | ||
+ | |||
+ | === '''Задачи с однородными объектами''' === | ||
+ | |||
+ | Пусть рассматривается задача, в которой имеется информация о том, что порядок, в котором анализируются объекты несущественен, и кроме прецедентных данных нет сведений о различии объектов. | ||
+ | Универсальные ограничения, выражающие однородность объектов, состоят в том, что отображение, реализуемое корректным алгоритмом, должно коммутировать со всеми подстановками строк (при любой перстановке строк в матрице информации точно так же должны переставляться строки в матрице, порожденной алгоритмом). | ||
== Задачи с непересекающимися классами. == | == Задачи с непересекающимися классами. == | ||
- | Диссертация Рудакова, пункт 2.5 | ||
== Класс поэлементных операций и отображений. Условия регулярности и полноты. == | == Класс поэлементных операций и отображений. Условия регулярности и полноты. == | ||
== Полнота моделей АВО. == | == Полнота моделей АВО. == | ||
- | Диссертация Рудакова, пункт 3.5 | ||
== Полнота полиномиальных семейств корректирующих операций. == | == Полнота полиномиальных семейств корректирующих операций. == | ||
Строка 572: | Строка 500: | ||
Для частного случая - матрицы информации, состоящие из нулей и единиц, оценку степени корректирующих полиномов удалось улучшить. Для таких полиномов степень может быть снижена до <math>\lceil \log_2 (q * l ) \rceil</math> | Для частного случая - матрицы информации, состоящие из нулей и единиц, оценку степени корректирующих полиномов удалось улучшить. Для таких полиномов степень может быть снижена до <math>\lceil \log_2 (q * l ) \rceil</math> | ||
- | |||
- | |||
- | Полезная информация к билету из [http://www.ccas.ru/frc/thesis/RudakovDocDisser.pdf Диссертации Рудакова] | ||
- | * Определение корректирующих операций - п. 1.3 стр 27 | ||
- | * Полнота полиномиальных семейств к.о. - п. 5.6 стр 116 | ||
- | * Определение 0,1-полноты - определение 6.1.2 стр 119 | ||
- | * Теорема о логарифмической границе степени корректирующих полиномов - теорема 6.1.3, стр 120 | ||
- | |||
- | |||
- | {{Курс МОТП}} |