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

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

Версия 19:54, 23 ноября 2008 (править) Slimper (Обсуждение | вклад) ← К предыдущему изменению		Текущая версия (00:09, 10 января 2010) (править) (отменить) Vokov (Обсуждение | вклад) м (декатегоризация)
(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 Примеры задач 2 Описание критерия 2.1 Асимптотический критерий 3 Свойства критерия Бартелса 4 История 5 Литература 6 См. также 7 Ссылки

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

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

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

Заданы выборка .

Нулевая гипотеза выборка простая, то есть все наблюдения — независимы и одинаково распределены.

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

1. Построить вариационный ряд выборки и найти ранги всех элементов.
2. Статистика критерия Бартелса вычисляется по формуле:

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

• двусторонний критерий (против альтернативы, что данные не случайны)

если , то нулевая гипотеза отвергается;

• левосторонний критерий(против альтернативы, что наблюдения положительно коррелированы)

если , то нулевая гипотеза отвергается;

• правосторонний критерий(против альтернативы, что наблюдения отрицательно коррелированы)

если , то нулевая гипотеза отвергается;

Здесь -- это -квантиль табличного распределения статистики Бартелса с параметром .

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

Распределение статистики Бартелса асимптотически нормально с матожиданием и дисперсией

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

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

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

История

Критерий был предложен Бартелсом в 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 в учебном процессе.