Редактирование: МОТП, Билеты (2009)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 76 килобайт. Страницы, размер которых приближается к 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://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 величин | |
- | + | ||
- | <div class="definition">''' Метод максимального правдоподобия ''' — метод оценивания неизвестного параметра путём максимизации функции правдоподобия: <math>f_x (x|\theta) = \prod_{i=1}^n f_x(x_i | \theta)</math> для независимой выборки n величин.</div> | ||
- | + | <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://www.machinelearning.ru/wiki/index.php?title=%D0%9B%D0%BE%D0%B3%D0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%80%D0%B5%D0%B3%D1%80%D0%B5%D1%81%D1%81%D0%B8%D1%8F machinelearning]) — метод [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-алгоритм: ([http://en.wikipedia.org/wiki/Expectation-maximization_algorithm en-wiki]], [http://www.machinelearning.ru/wiki/index.php?title=EM_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_(%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80) machinelearning-пример]) | + | <u>EM-алгоритм: ([http://en.wikipedia.org/wiki/Expectation-maximization_algorithm en-wiki]], [http://www.machinelearning.ru/wiki/index.php?title=EM_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_(%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80) machinelearning-пример])</u> |
- | # | + | # выбираем начальное приближение для параметров <math>\mu_j, \Sigma_j, w_j, j \isin [1, l]</math> |
# E-шаг (expectation): находим для каждого элемента выборки вероятность, с которой он принадлежит каждой из компонент смеси. | # E-шаг (expectation): находим для каждого элемента выборки вероятность, с которой он принадлежит каждой из компонент смеси. | ||
# M-шаг (maximization): с учетом вероятностей на предыдущем шаге пересчитываем коэффициенты начального шага. | # M-шаг (maximization): с учетом вероятностей на предыдущем шаге пересчитываем коэффициенты начального шага. | ||
- | # | + | # переход к 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}(A_i|B) = 1</math> или <math>P(B)=\sum_{i=1}^k \mathbb{P}(B|A_i) \mathbb{P}(A_i)</math> |
- | * | + | * в интегральном виде: <math>p(b) =\int p(b,a)da=\int p(b|a)p(a)da</math> |
- | * ''' | + | * '''формула Байеса''' ([http://ru.wikipedia.org/wiki/Формула_Байеса ru:wiki]): <math>P(A|B) = \frac{P(B | A)\, P(A)}{P(B)}</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> |
- | == Графические модели. Основные задачи, возникающие в анализе графических моделей == | + | == Графические модели. Основные задачи, возникающие в анализе графических моделей.== |
'''Графическая модель''' -- ориентированный или неориентированный граф, в котором вершины соответствуют переменным, а ребра - вероятностным отношениям, определяющим непосредственные зависимости. | '''Графическая модель''' -- ориентированный или неориентированный граф, в котором вершины соответствуют переменным, а ребра - вероятностным отношениям, определяющим непосредственные зависимости. | ||
Строка 525: | Строка 530: | ||
<math>\hat{I}=||I_{ij}||_{q \times l}</math> - матрица информации и <math> \hat {\tilde I} = || {\tilde I}_{ij}||_{q \times 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>. | Задаче Z соответствует пара матриц: <math> Z \leftrightarrow (\hat I , \hat{\tilde I})</math>. | ||
- | Определение ''окрестности задачи по Журавлеву'' <math>O(Z)=\{Z^' |Z^' \leftrightarrow (\hat I , \hat{\tilde I}^') | + | Определение ''окрестности задачи по Журавлеву'' <math>O(Z)=\{Z^' \|Z^' \leftrightarrow (\hat I , \hat{\tilde I}^')</math> - т.е. это множество задач <math>Z^'</math>, получающихся всевозможным варьированием матрицы правильных ответов. |
* Разбиваем множество задач на классы эквивалентности. Задача называется регулярной если она разрешима и разрешимы все задачи из класса эквивалентности который она порождает. | * Разбиваем множество задач на классы эквивалентности. Задача называется регулярной если она разрешима и разрешимы все задачи из класса эквивалентности который она порождает. | ||
Строка 545: | Строка 550: | ||
Модель алгоритмов <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>\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> содержится корректный алгоритм) | ||
== Дополнительные к прецедентам ограничения. Пример: перестановочность строк и столбцов в матрицах информации. == | == Дополнительные к прецедентам ограничения. Пример: перестановочность строк и столбцов в матрицах информации. == | ||
Строка 572: | Строка 576: | ||
Для частного случая - матрицы информации, состоящие из нулей и единиц, оценку степени корректирующих полиномов удалось улучшить. Для таких полиномов степень может быть снижена до <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 | ||
- | |||
{{Курс МОТП}} | {{Курс МОТП}} |