Редактирование: МОТП, Билеты (2009)

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

Перейти к: навигация, поиск

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 75 килобайт. Страницы, размер которых приближается к 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 метода макс. правдоподобия по Черновой из НГУ]
-
* [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 ru.wiki:Метод максимального правдоподобия]
+
''' Метод максимального правдоподобия ''' -- метод оценивания неизвестного параметра путём максимизации функции правдоподобия: <math>f_x (x|\theta) = \prod_{i=1}^n f_x(x_i | \theta)</math> для независимой выборки n величин
-
* [http://www.nsu.ru/mmf/tvims/chernova/ms/lec/node14.html Метод макс. правдоподобия по Черновой из НГУ]
+
-
<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/Регуляризация_(математика) регуляризация] метода
-
== Решение несовместных СЛАУ ==
+
==Решение несовместных СЛАУ.==
В статистике, машинном обучении и теории обратных задач под регуляризацией понимают добавление некоторой дополнительной информации к условию с целью решить некорректно поставленную задачу или предотвратить переобучение.
В статистике, машинном обучении и теории обратных задач под регуляризацией понимают добавление некоторой дополнительной информации к условию с целью решить некорректно поставленную задачу или предотвратить переобучение.
-
<div class="definition">'''Несовместная СЛАУ''' система линейных уравнений, не имеющая ни одного решения.</div>
+
'''Несовместная СЛАУ''' -- система линейных уравнений, не имеющая ни одного решения.
-
<div class="definition">'''Совместная СЛАУ''' система линейных уравнений, имеющая хотя бы одно решение.</div>
+
'''Совместная СЛАУ''' -- система линейных уравнений, имеющая хотя бы одно решение.
-
<div class="definition">''' Ридж-регуляризация''' (ридж-регрессия, [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>.</div>
+
''' Ридж-регуляризация''' (ридж-регрессия, [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>
-
<div class="definition">''' Нормальное псевдорешение ''' СЛАУ <math>Ax = b</math> вектор <math> x = (A^T A + \lambda I )^{-1} A^T b </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 ru.wiki:Регрессионный анализ]
+
* [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''.
+
'''Задача регрессионного анализа (неформально)'''.
-
<div class="definition">'''Задача регрессионного анализа''' — определение наличия и характера (математического уравнения, описывающего зависимость) связи между переменными. В случае линейной регрессии, зависимость ''X'' от параметра ''t'' проявляется в изменении средних значений ''Y'' при изменении ''t'' (хотя при каждом фиксированном значении ''t'' величина ''X'' остается случайной величиной).</div>
+
Предположим имеется зависимость между неизвестной нам случайно величиной X (мы судим о ней по наблюдаемым признакам, т.е. по случайной выборке) и некоторой переменной (параметром) t.
-
Искомая зависимость среднего значения ''X'' от значений ''Z'' обозначается через функцию ''f''(''t''): <math>E(X | Z = t)=f(t)</math>. Проводя серии экспериментов, требуется по значениям ''t''<sub>1</sub>, &hellip;, ''t''<sub>''n''</sub> и ''X''<sub>1</sub>, &hellip;, ''X''<sub>''n''</sub> оценить как можно точнее функцию ''f''(''t'').
+
'''Задача регрессионного анализа''' — определение наличия и характера (математического уравнения, описывающего зависимость) связи между переменными. В случае линейной регрессии, зависимость X от параметра t проявляется в изменении средних значений Y при изменении t (хотя при каждом фиксированном значении t величина X остается случайной величиной).
-
Однако, наиболее простой и изученной является линейная регрессия, в которой неизвестные настраиваемые параметры (''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>/
+
Искомая зависимость среднего значения 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>
----
----
-
<div class="definition">''' Метод наименьших квадратов ''' — минимизация функции потери ошибки <math>S(t, \hat{t}) = (t - \hat{t})^2</math>.</div>
+
''' Метод наименьших квадратов ''' — минимизация функции потери ошибки <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>.
+
В большинстве случаев предполагается нормальное распределение относительно некоторой точки 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>), получаем эквивалентность данного метода методу наименьших квадратов, т.&nbsp;к. взяв логарифм от формулы выше, получаем:
 
-
<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>
-
<div class="definition">''' Логистическая регрессия''' ([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 сигмоид]).</div>
+
== Логистическая регрессия. Вероятностная постановка.==
 +
''' Логистическая регрессия''' ([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 Expectation-maximization]])</u>
-
# Выбираем начальное приближение для параметров <math>\mu_j, \Sigma_j, w_j, j \isin [1, l]</math>.
+
# выбираем начальное приближение для параметров <math>\mu_j, \Sigma_j, w_j, j \isin [1, l]</math>
# E-шаг (expectation): находим для каждого элемента выборки вероятность, с которой он принадлежит каждой из компонент смеси.
# E-шаг (expectation): находим для каждого элемента выборки вероятность, с которой он принадлежит каждой из компонент смеси.
# M-шаг (maximization): с учетом вероятностей на предыдущем шаге пересчитываем коэффициенты начального шага.
# M-шаг (maximization): с учетом вероятностей на предыдущем шаге пересчитываем коэффициенты начального шага.
-
# Переход к E шагу до тех пор, пока не будет достигнута сходимость.
+
# переход к E шагу до тех пор, пока не будет достигнута сходимость
-
'''Недостатки:'''
+
<u>недостатки:</u>
-
* (!) Не позволяет определить количество компонент смеси (''l'').
+
* (!!) не позволяет определить количество компонент смеси (''l'')
-
** Величина ''l'' является структурным параметром.
+
** величина ''l'' является структурным параметром
-
* В зависимости от выбора начального приближения может сходиться к разным точкам.
+
* в зависимости от выбора начального приближения может сходиться к разным точкам
-
* может сваливаться в локальный экстремум.
+
* может сваливаться в локальный экстремум
-
== Основные правила работы с вероятностями. Условная независимость случайных величин ==
+
==Основные правила работы с вероятностями. Условная независимость случайных величин.==
-
<div class="definition">''' Случайная величина ''' это измеримая функция, заданная на каком-либо вероятностном пространстве. ([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 ru.wiki])</div>
+
''' Случайная величина ''' -- это измеримая функция, заданная на каком-либо вероятностном пространстве. ([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 вики])
-
<div class="definition">''' Функция распределения ''' <math>F_X(x)</math> вероятность того, что случайная величина ''X'' меньше ''x'': <math>F_X(x) = \mathbb{P}(X \leqslant x)</math>.</div>
+
''' Функция распределения ''' <math>F_X(x)</math> -- вероятность того, что случайная величина X меньше x: <math>F_X(x) = \mathbb{P}(X \leqslant x)</math>
-
<div class="definition">''' Плотность вероятности ''':
+
''' Плотность вероятности ''':
-
* В дискретном случае вероятность того, что ''X'' = ''x'';
+
* в дискретном случае -- вероятность того, что X = x
-
* В непрерывном случае производная функции распределения.</div>
+
* в непрерывном случае -- производная функции распределения
-
Далее ''X'', ''Y'' — случайные величины с плотностями вероятности <math>p(x), p(y)</math>.
+
Пусть X, Y - случайные величины с плотностями вероятности <math>p(x), p(y)</math>
-
<div class="definition">Случайные величины ''X'', ''Y'' называются '''независимыми''', если <math>p(x,y) = p(x) \cdot p(y)</math>.</div>
+
Случайные величины X,Y называются независимыми, если <math>p(x,y) = p(x) \cdot p(y)</math>
-
<div class="definition">''' Условная плотность ''' <math>p(x|y) = \frac{p(x,y)}{p(y)}</math>.
+
''' Условная плотность ''' -- <math>p(x|y) = \frac{p(x,y)}{p(y)}</math>
-
* в дискретном случае вероятность того, что наступило событие ''x'', при условие наступления события ''y''.</div>
+
* в дискретном случае - вероятность того, что наступило событие x, при условие наступления события y
-
'''Правило суммирования:''' пусть <math>A_1, \dots, A_k</math> — ''k'' взаимоисключающих события, одно из которых обязательно наступает. Тогда
+
<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>\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>.
+
* в интегральном виде: <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>.
+
* '''формула Байеса''' ([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>.
+
* это значит: вся информация о взаимосвязи между <math>x</math> и <math>y</math> содержится в <math>z</math>
-
* Из безусловной независимости не следует условная независимость.
+
* из безусловной независимости не следует условная независимость
-
* '''Основное свойство условно независимых величин''': <math>p(z|x,y) = \frac{1}{Z} \cdot \frac{p(z|x) p(z|y)}{p(z)}</math>, где <math>Z = \frac{p(x)p(y)}{p(x,y)}</math><!--в презентациях ошибка, [http://www.cmcspec.ru/ipb/index.php?showtopic=536&view=findpost&p=15899 '''проверено''']-->.
+
* <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>
-
== Графические модели. Основные задачи, возникающие в анализе графических моделей ==
+
== Графические модели. Основные задачи, возникающие в анализе графических моделей.==
'''Графическая модель''' -- ориентированный или неориентированный граф, в котором вершины соответствуют переменным, а ребра - вероятностным отношениям, определяющим непосредственные зависимости.
'''Графическая модель''' -- ориентированный или неориентированный граф, в котором вершины соответствуют переменным, а ребра - вероятностным отношениям, определяющим непосредственные зависимости.
Строка 145: Строка 150:
==Скрытые марковские модели. Обучение СММ с учителем.==
==Скрытые марковские модели. Обучение СММ с учителем.==
* [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>
-
# состоит из набора наблюдаемых переменных <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>.
+
<br>
-
# латентные переменные 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> 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: Строка 170:
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: Строка 181:
* Условное распределение <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>.
-
'''Обучение с учителем'''. Известна некоторая последовательность <math>X</math>, для которой заданы <math>T</math>. '''Задача состоит''' в оценке по обучающей выборке набора параметров <math>\Theta</math>.
+
'''Собственно, билет'''<br>
-
 
+
-
==Алгоритм динамического программирования и его применение в скрытых марковских моделях.==
+
-
* см. '''Лекция 3, стр. 9-28'''
+
-
<br/>
+
-
'''Динамическое программирование''' в математике и теории вычислительных систем — метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами, который намного эффективнее, чем решение «в лоб». ([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 дин. прогр. на вики])
+
-
 
+
-
 
+
-
'''Собственно, билет'''.
+
* Пусть известна некоторая последовательность наблюдений <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>
-
''Алгоритм Витерби'' ([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 Алгоритм Витерби на вики] - очень хорошо для понимания зачем все это надо)
+
''Алгоритм Витерби''<br>
-
 
+
Логарифм совместной плотности по распределению:
Логарифм совместной плотности по распределению:
<math>
<math>
Строка 206: Строка 214:
* Предположим имеется графическая модель в которой известная только часть значений переменных.
* Предположим имеется графическая модель в которой известная только часть значений переменных.
* Атомарные распределения известны с точностью до <math>\theta</math>
* Атомарные распределения известны с точностью до <math>\theta</math>
-
* Требуется оценить параметры по наблюдаемым величинам с помощью метода максимального правдоподобия т.е найти <math> \theta_{ML} = \arg \max(p(X|\theta)) </math>
+
* Требуется оценить параметры по наблюдаемым величинам с помощью метода максимального правдоподобия т.е найти <math> \theta_{ML} = \arg \max(p(X|\theta) </math>
* По правилу суммирования вероятностей неполное правдоподобие может быть получено в виде суммирования по скрытым переменным полного правдоподобия <math>p(X|\theta)=\sum_T p(X,T|\theta)</math>
* По правилу суммирования вероятностей неполное правдоподобие может быть получено в виде суммирования по скрытым переменным полного правдоподобия <math>p(X|\theta)=\sum_T p(X,T|\theta)</math>
* Во многих случаях(в частности в байесовских сетях) подсчет полного правдоподобия тривиален
* Во многих случаях(в частности в байесовских сетях) подсчет полного правдоподобия тривиален
Строка 216: Строка 224:
* Инициализируем <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>
+
<math> p(T|X,\theta_{old})=\frac{p(T|X,\theta_{old})}{\sum_T p(X,T|\theta_{old})} </math>
* M-шаг оптимизируем
* 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>\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>
Строка 226: Строка 234:
=== EM-алгоритм для смеси гауссовских распределений ===
=== EM-алгоритм для смеси гауссовских распределений ===
-
см. пункт 1.6
+
Тут много формул, нет сил набивать
недостатки:
недостатки:
* В зависимости от выбора начального приближения может сходится к разным точкам
* В зависимости от выбора начального приближения может сходится к разным точкам
Строка 246: Строка 254:
==Метод релевантных векторов в задаче восстановления регрессии.==
==Метод релевантных векторов в задаче восстановления регрессии.==
-
Лекция 5 Ветров.
 
- 
== Метод релевантных векторов в задаче классификации.==
== Метод релевантных векторов в задаче классификации.==
-
Лекция 5 Ветров.
 
- 
-
[http://courses.graphicon.ru/files/courses/smisa/2008/lectures/lecture11.pdf Еще слайды Ветрова, но не из этого круса] от того более понятными не становятся
 
- 
== Метод главных компонент.==
== Метод главных компонент.==
Строка 260: Строка 262:
* проекция данных на гиперплоскость с наименьшей ошибкой проектирования
* проекция данных на гиперплоскость с наименьшей ошибкой проектирования
* поиск проекции на гиперплоскость с сохранением большей части дисперсии в данных
* поиск проекции на гиперплоскость с сохранением большей части дисперсии в данных
- 
-
[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 Википедия: Метод главных компонент]
 
==Вероятностная формулировка метода главных компонент.==
==Вероятностная формулировка метода главных компонент.==
Строка 365: Строка 365:
Для начала, поговорим об '''алгоритмах голосования'''. Пусть для каждого класса <math>c \in Y</math> построено множество логических закономерностей (правил), специализирующихся на различении объектов данного класса:
Для начала, поговорим об '''алгоритмах голосования'''. Пусть для каждого класса <math>c \in Y</math> построено множество логических закономерностей (правил), специализирующихся на различении объектов данного класса:
-
<math>R_c = \{ \varphi_c^t : X \rightarrow \{0, 1\} | t = 1, . . . , T_c\}</math>, где <math>T_c</math> - количество классов свойств.
+
<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.
Строка 464: Строка 464:
0,~~otherwise
0,~~otherwise
\end{cases}</math>
\end{cases}</math>
-
# Введем дополнительно к п.1 параметр <math>\nu</math> такой, что функция близости будет определятся как <math>\mathcal{N}_{\tilde\Omega}(S_i, S_j) = 1</math>, если не выполнено не больше, чем <math>\nu</math> описанных неравенств. при этом имеет смысл брать <math>0 \leqslant \nu \leqslant \left[\frac{k}{2} - 1\right] </math>
+
# Введем дополнительно к п.1 параметр <math>\nu</math> такой, что <math>\mathcal{N}_{\tilde\Omega}(S_i, S_j) = 1</math>, если не выполнено не больше, чем <math>\nu</math> описанных неравенств. при этом имеет смысл брать <math>0 \leqslant \nu \leqslant \left[\frac{k}{2} - 1\right] </math>
-
# Вместо <math>\nu</math> определяем <math>\nu'</math> и функцию близости так, что <math>\mathcal{N}_{\tilde\Omega}(S_i,S_j) = 1</math>, если из k неравенств не выполнены r, причем <math>\frac{r}{k} < \nu'</math>
+
# Вместо <math>\nu</math> определяем <math>\nu'</math> так, что <math>\mathcal{N}_{\tilde\Omega}(S_i,S_j) = 1</math>, если из k неравенств не выполнены r, причем <math>\frac{r}{k} < \nu'</math> (WTF?!)
-
* К билету был вопрос: какие сколько возможных выборок<math>\varepsilon_i</math> стоит рассматривать. Вообще говоря <math>\varepsilon</math> -действительно так-что континуум. Но смысл будут нести только l*m*n вариантов. где l - число признаков(колчисетво этих <math>\varepsilon</math> ),m - число компонент обучающей выборки, n - число компонент контрольной выборки. Другими словами мы <math>\varepsilon_i</math> задаем какое хотим, но обычно его задают между значениями признаков на выборке, при этом всего у нас m*n сравнений и таким образом m*n вариантов его задать(для одного <math>\varepsilon</math> )
+
== Формулы вычисления оценок. Эвристические обоснования. ==
== Формулы вычисления оценок. Эвристические обоснования. ==
Строка 525: Строка 524:
<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> - т.е. это множество задач <math>Z^'</math>, получающихся всевозможным варьированием матрицы правильных ответов.
+
Определение ''окрестности задачи по Журавлеву'' <math>O(Z)=\{Z^' \|Z^' \leftrightarrow (\hat I , \hat{\tilde I}^')</math> - т.е. это множество задач <math>Z^'</math>, получающихся всевозможным варьированием матрицы правильных ответов.
-
 
+
-
* Разбиваем множество задач на классы эквивалентности. Задача называется регулярной если она разрешима и разрешимы все задачи из класса эквивалентности который она порождает.
+
== Операции над алгоритмами. Расширение моделей. ==
== Операции над алгоритмами. Расширение моделей. ==
Строка 545: Строка 542:
Модель алгоритмов <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> содержится корректный алгоритм)
 
== Дополнительные к прецедентам ограничения. Пример: перестановочность строк и столбцов в матрицах информации. ==
== Дополнительные к прецедентам ограничения. Пример: перестановочность строк и столбцов в матрицах информации. ==
Строка 555: Строка 551:
Пусть рассматривается задача, в которой имеется информация о том, что порядок, в котором анализируются классы несущественен, и кроме прецедентных данных нет сведений о различии классов.
Пусть рассматривается задача, в которой имеется информация о том, что порядок, в котором анализируются классы несущественен, и кроме прецедентных данных нет сведений о различии классов.
Универсальные ограничения, выражающие однородность классов, состоят в том, что отображение, реализуемое корректным алгоритмом, должно коммутировать со всеми подстановками столбцов (при любой перстановке столбцов в матрице информации точно так же должны переставляться столбцы в матрице, порожденной алгоритмом).
Универсальные ограничения, выражающие однородность классов, состоят в том, что отображение, реализуемое корректным алгоритмом, должно коммутировать со всеми подстановками столбцов (при любой перстановке столбцов в матрице информации точно так же должны переставляться столбцы в матрице, порожденной алгоритмом).
 +
 +
=== '''Задачи с однородными объектами''' ===
 +
 +
Пусть рассматривается задача, в которой имеется информация о том, что порядок, в котором анализируются объекты несущественен, и кроме прецедентных данных нет сведений о различии объектов.
 +
Универсальные ограничения, выражающие однородность объектов, состоят в том, что отображение, реализуемое корректным алгоритмом, должно коммутировать со всеми подстановками строк (при любой перстановке строк в матрице информации точно так же должны переставляться строки в матрице, порожденной алгоритмом).
== Задачи с непересекающимися классами. ==
== Задачи с непересекающимися классами. ==
-
Диссертация Рудакова, пункт 2.5
 
== Класс поэлементных операций и отображений. Условия регулярности и полноты. ==
== Класс поэлементных операций и отображений. Условия регулярности и полноты. ==
== Полнота моделей АВО. ==
== Полнота моделей АВО. ==
-
Диссертация Рудакова, пункт 3.5
 
== Полнота полиномиальных семейств корректирующих операций. ==
== Полнота полиномиальных семейств корректирующих операций. ==
Строка 572: Строка 571:
Для частного случая - матрицы информации, состоящие из нулей и единиц, оценку степени корректирующих полиномов удалось улучшить. Для таких полиномов степень может быть снижена до <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
 
- 
{{Курс МОТП}}
{{Курс МОТП}}

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Шаблоны, использованные на этой странице:

Личные инструменты
Разделы