Участник:Slimper/Песочница

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

< Участник:Slimper(Различия между версиями)
Перейти к: навигация, поиск
м (декатегоризация)
 
(30 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
==Постановка задачи оптимизации==
+
'''Критерий Бартелса (Bartels test)''' — [[непараметрический статистический критерий]], используемый для проверки случайности последовательности наблюдаемых значений. Критерий является ранговым, поэтому он инвариантен по отношению к любому монотонному преобразованию шкалы измерения. Критерий Бартелса можно применять для анализа регрессионных остатков.
-
Пусть задано множество <tex> X \subset R^n </tex> и на этом множестве определена ''целевая функция'' (''objective function'') <tex>f : R^n \mapsto R</tex>. Задача оптимизации состоит в нахождении на множестве <tex>X</tex> точной верхней или точной нижней грани ''целевой функции''. <br/>
+
Также его можно применять при анализе [[временной ряд|временных рядов]] для выявления тренда.
-
Множество точек, на которых достигается нижняя грань целевой функции обозначается <tex>X_* </tex>. <br/>
+
-
::<tex>X_* = \{x \in X| f(x) = inf \limits_{x \in X} f(x) \} </tex> <br/>
+
-
Если <tex> X = R^n </tex>, то задача оптимизации называется ''безусловной'' (''unconstrained'').
+
== Примеры задач ==
-
Если <tex> X \neq R^n </tex>, то задача оптимизации называется ''условной'' (''constrained'').
+
'''Пример 1.'''
 +
Ряд значений состоит из подсчитанного на протяжении нескольких лет количества туристов, посещавших страну в течение года.
 +
Требуется установить, являются ли число туристов, случайным, или оно
 +
подчиняется какой-то закономерности.
-
==Метод сопряжённых градиентов==
+
== Описание критерия ==
-
''Метод сопряжённых градиентов'' (''conjugate gradient method'') первоначально был разработан для решения систем линейных уравнений с положительно определённой матрицей. Позже этот метод обобщили для решения задач безусловной оптимизации в <tex>R^n</tex>
+
Заданы выборка <tex>x^n = (x_1,\ldots,x_n),x_i \in \mathbb{R}</tex>.
-
==Линейный метод сопряжённых градиентов ==
+
-
=== Изложение метода ===
+
-
Рассмотрим сначала метод сопряжённых градиентов для решения следующей задачи оптимизации: <br/>
+
-
<tex>F(x) = \frac{1}{2} \langle Ax, x \rangle - \langle b, x \rangle \to inf, \quad x \in R^n</tex> <br/>
+
-
Здесь <tex>A</tex> - симметричная положительно определённая матрица размера <tex>n \times n</tex>.
+
-
Такая задача оптимизации называется квадратичной.
+
-
Заметим, что <tex>F'(x) = Ax - b</tex>. Условие экстремума функции <tex>F'(x) = 0</tex> эквивалентно системе <tex> Ax - b = 0</tex>
+
-
Функция <tex>F</tex> достигает своей нижней грани в единственной точке <tex>x_*</tex>, определяемой уравнением <tex> Ax_* = b</tex> . Таким образом, данная задача оптимизации сводится к решению системы линейных уравнений <tex> Ax = b</tex> <br/>
+
-
Идея метода сопряжённых градиентов состоит в следующем: <br/>
+
-
Пусть <tex> \{p_k \} _{k = 1}^n </tex> - базис в <tex>R^n </tex> . Тогда для любой точки <tex> x_0 \in R^n </tex> вектор <tex>x_* - x_0</tex> раскладывается по базису <tex>x_* - x_0 = \alpha_1 p_1 + \dots \alpha_n p_n </tex>
+
-
Таким образом, <tex>x_*</tex> представимо в виде <br/>
+
-
::<tex>x_* = x_0 + \alpha_1 p_1 + \dots \alpha_n p_n </tex>
+
-
Каждое следующее приближение вычисляется по формуле: <br/>
+
-
::<tex>x_k = x_0 + \alpha_1 p_1 + \dots \alpha_n p_k </tex> <br/>
+
-
'''Определение.''' Два вектора <tex>p</tex> и <tex>q</tex> называются ''сопряжёнными'' относительно симметричной матрицы B, если <tex> \langle Bp,q \rangle = 0</tex>
+
-
Опишем способ построения базиса <tex> \{p_k \}_{k = 1}^n </tex> в методе сопряжённых градиентов
+
'''[[Нулевая гипотеза]]''' <tex>H_0:\;</tex> выборка <tex>x^n</tex> [[простая выборка|простая]], то
-
В качестве начального приближения <tex> x_0 </tex> выбираем произвольный вектор.
+
есть все наблюдения <tex>x_i</tex> — независимы и одинаково распределены.
-
На каждой итерации <tex>\alpha_k</tex> выбираются по правилу: <br/>
+
-
::<tex>\alpha_k = argmin \limits_{\alpha_k} F(x_{k-1} + \alpha_k p_k)</tex>
+
-
<br/>
+
-
Базисные вектора <tex> \{p_k \} </tex> вычисляются по формулам: <br/>
+
-
<tex> p_1 = -F'(x_0) </tex>
+
-
<br/>
+
-
<tex> p_{k+1} = - F'(x_{k}) + \beta_{k} p_{k} </tex>
+
-
<br/>
+
-
Коэффициенты <tex>\beta_k</tex> выбираются так, чтобы векторы <tex>p_k</tex> и <tex>p_{k + 1} </tex>были сопряжёнными относительно А. <br/>
+
-
::<tex>\beta_k = \frac{ \langle F'(x_{k}), Ap_k \rangle}{ \langle Ap_k, p_k \rangle} </tex>
+
-
<br/>
+
-
Если обозначить за <tex>r_k = b - Ax_k = -f'(x_{k})</tex> , то после нескольких упрощений получим окончательные формулы, используемые при применении метода сопряжённых градиентов на практике: <br/>
+
-
::<tex>r_0 = b - Ax_0</tex> <br/>
+
-
::<tex> p_0 = r_0 </tex> <br/>
+
-
<tex>
+
-
\begin{equation*}
+
-
\alpha_k = \frac{ \langle r_k, r_k \rangle }{ \langle Ap_k, p_k \rangle } \\
+
-
x_{k + 1} = x_k + \alpha_k p_k \\
+
-
r_{k + 1} = r_k - \alpha_k Ap_k \\
+
-
\beta_k = \frac{ \langle r_{k + 1}, r_{k + 1} \rangle }{\langle r_k, r_k \rangle} \\
+
-
p_{k + 1} = r_{k + 1} + b_k p_k \\
+
-
\end{equation*}
+
-
</tex>
+
-
<br/>
+
-
=== Анализ метода ===
+
-
Для метода сопряжённых градиентов справедлива следующая теорема:
+
-
Пусть <tex>F(x) = \frac{1}{2} <Ax, x> </tex>
+
-
==== Сходимость метода ====
+
-
Если все вычисления точные, и исходные то метод сходится к решению системы не более чем за <tex>m</tex> итераций, где
+
-
<tex>m</tex> - число различных собственных значений матрицы A. На практике чаще всего используют следующий критерий останова:
+
-
норма погрешности <tex>r_k</tex> становится меньше некоторого заданного порога <tex>r_0</tex>.
+
-
==== Вычислительная сложность ====
+
-
На каждой итерации метода выполняется <tex>O(n^2)</tex> операций. Такое количество операций требуется для вычисления произведения
+
-
<tex>Ap_k</tex> - это самая трудоёмкая процедура на каждой итерации. Отальные вычисления требуют O(n) операций.
+
-
Суммарная вычислительная сложность метода не превышает <tex>O(n^3)</tex> - так как число итераций не больше n.
+
-
== Общий случай ==
+
-
Расссматриваем задачу <tex>F(x) \to min, \quad x \in R^n </tex>.
+
-
<tex>F(x) </tex> - непрерывно дифференцируемая в <tex>R^n </tex> функция.
+
-
Чтобы получить из метода сопряжённых градиентов метод для решения данной задачи, нужно получить для <tex>p_k, \alpha_k, \beta_k </tex> формулы, в кторые не входит матрица А:
+
-
::<tex>\alpha_k = argmin \limits_{\alpha_k} F(x_{k-1} + \alpha_k p_k)</tex>
+
-
::<tex> p_{k+1} = - F'(x_{k}) + \beta_{k} p_{k} </tex>
+
-
<tex> \beta_k </tex> можно вычислять по одной из трёх формул:
+
-
::<tex> \beta_k = - \frac{\langle F'(x_{k + 1} ), F'(x_{k + 1}) \rangle}{\langle F'(x_k), F'(x_k) \rangle} </tex>
+
'''Статистика критерия:'''
-
::<tex> \beta_k = \frac{\langle F'(x_{k + 1}), F'(x_k) - F'(x_{k + 1} ) \rangle}{\langle F'(x_k}), F'(x_k) \rangle} </tex>
+
# Построить [[вариационный ряд]] выборки <tex>x^{(1)}(x_1,\ldots,x_n)</tex> и найти ранги <tex>r(x_i)</tex> всех элементов.
-
::<tex> \beta_k = \frac{\langle F''(x_{k+1} )p_{k},F'(x_{k + 1}) \rangle}{\langle F''(x_{k})p_k, p_k \rangle} </tex>
+
# Статистика критерия Бартелса вычисляется по формуле:
 +
::<tex>B = \frac{ \sum_{i = 1}^n (r(x_i) - r(x_{i + 1}) )^2 }{ \sum(R_i - \frac{n + 1}{2})^2}</tex>
 +
Варианты критерия (при [[уровень значимости|уровне значимости]] <tex>\alpha</tex>):
 +
 +
* двусторонний критерий (против альтернативы, что данные не случайны)
 +
::если <tex> B \in \left[ B_{n,\alpha/2},\, B_{n,1-\alpha/2} \right] </tex>, то нулевая гипотеза отвергается;
 +
 +
* левосторонний критерий(против альтернативы, что наблюдения положительно коррелированы)
 +
::если <tex> B < B_{n,\alpha} </tex>, то нулевая гипотеза отвергается;
 +
* правосторонний критерий(против альтернативы, что наблюдения отрицательно коррелированы)
 +
::если <tex> B > B_{n,\alpha} </tex>, то нулевая гипотеза отвергается;
 +
 +
Здесь <tex> B_{n,\alpha} </tex> -- это <tex>\alpha</tex>-[[квантиль]] табличного распределения статистики Бартелса с параметром <tex>n</tex>.
 +
 +
===Асимптотический критерий ===
 +
Распределение статистики Бартелса асимптотически нормально
 +
с матожиданием <tex>\mathbb{E}B = 2</tex> и дисперсией
 +
::<tex> \mathbb{D}B = \frac{4(n - 2)(5n^2 - 2n - 9)}{5n(n + 1)(n - 1)^2} </tex>
 +
 +
Поэтому при
 +
<tex>n \ge 20</tex> используется нормированная статистика Бартелса
 +
::<tex>B' = \frac{B - \mathbb{E}B}{\sqrt{\mathbb{D}B} } </tex>
 +
 +
== Свойства критерия Бартелса==
 +
Бартелс с помошью численного моделирования показал , что во многих случаях критерий Бартелса имеет большую мощность, чем [[Критерий Вальда-Вольфовица|критерий серий]].
 +
 +
== История ==
 +
Критерий был предложен Бартелсом в 1982 году.
== Литература ==
== Литература ==
-
Васильев Ф. П. Методы оптимизации - Издательство «Факториал Пресс», 2002 <br/>
+
 
-
Nocedal J., Wright S.J. Numerical Optimization ,Springer, 1999
+
# ''Gibbons J. D., Chakraborti S.'' Nonparametric Statistical Inference, 4th Ed. — CRC, 2003 — 608&nbsp;с.
 +
# ''Кобзарь А. И.'' Прикладная математическая статистика. — М.:&nbsp;Физматлит, 2006. — 816&nbsp;с.
 +
 
 +
== См. также ==
 +
* [[Проверка статистических гипотез]] — о методологии проверки статистических гипотез.
 +
* [[Статистика (функция выборки)]]
 +
* [[Критерий Вальда-Вольфовица|Критерий серий]] — другой критерий для проверки случайности ряда наблюдений
 +
 
 +
== Ссылки ==
 +
 
 +
{{Задание|Slimper|Vokov|08 января 2010}}

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

Критерий Бартелса (Bartels test)непараметрический статистический критерий, используемый для проверки случайности последовательности наблюдаемых значений. Критерий является ранговым, поэтому он инвариантен по отношению к любому монотонному преобразованию шкалы измерения. Критерий Бартелса можно применять для анализа регрессионных остатков. Также его можно применять при анализе временных рядов для выявления тренда.

Содержание

Примеры задач

Пример 1. Ряд значений состоит из подсчитанного на протяжении нескольких лет количества туристов, посещавших страну в течение года. Требуется установить, являются ли число туристов, случайным, или оно подчиняется какой-то закономерности.

Описание критерия

Заданы выборка x^n = (x_1,\ldots,x_n),x_i \in \mathbb{R}.

Нулевая гипотеза H_0:\; выборка x^n простая, то есть все наблюдения x_i — независимы и одинаково распределены.

Статистика критерия:

  1. Построить вариационный ряд выборки x^{(1)}(x_1,\ldots,x_n) и найти ранги r(x_i) всех элементов.
  2. Статистика критерия Бартелса вычисляется по формуле:
B = \frac{ \sum_{i = 1}^n (r(x_i) - r(x_{i + 1}) )^2 }{ \sum(R_i - \frac{n + 1}{2})^2}

Варианты критерия (при уровне значимости \alpha):

  • двусторонний критерий (против альтернативы, что данные не случайны)
если  B \in \left[ B_{n,\alpha/2},\, B_{n,1-\alpha/2} \right] , то нулевая гипотеза отвергается;
  • левосторонний критерий(против альтернативы, что наблюдения положительно коррелированы)
если  B < B_{n,\alpha} , то нулевая гипотеза отвергается;
  • правосторонний критерий(против альтернативы, что наблюдения отрицательно коррелированы)
если  B > B_{n,\alpha} , то нулевая гипотеза отвергается;

Здесь  B_{n,\alpha} -- это \alpha-квантиль табличного распределения статистики Бартелса с параметром n.

Асимптотический критерий

Распределение статистики Бартелса асимптотически нормально с матожиданием \mathbb{E}B = 2 и дисперсией

 \mathbb{D}B = \frac{4(n - 2)(5n^2 - 2n - 9)}{5n(n + 1)(n - 1)^2}

Поэтому при n \ge 20 используется нормированная статистика Бартелса

B' = \frac{B - \mathbb{E}B}{\sqrt{\mathbb{D}B} }

Свойства критерия Бартелса

Бартелс с помошью численного моделирования показал , что во многих случаях критерий Бартелса имеет большую мощность, чем критерий серий.

История

Критерий был предложен Бартелсом в 1982 году.

Литература

  1. Gibbons J. D., Chakraborti S. Nonparametric Statistical Inference, 4th Ed. — CRC, 2003 — 608 с.
  2. Кобзарь А. И. Прикладная математическая статистика. — М.: Физматлит, 2006. — 816 с.

См. также

Ссылки

Данная статья является непроверенным учебным заданием.
Студент: Участник:Slimper
Преподаватель: Участник:Vokov
Срок: 08 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Личные инструменты