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

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

Версия 19:54, 23 ноября 2008 (править) Slimper (Обсуждение | вклад) ← К предыдущему изменению		Версия 14:37, 5 января 2010 (править) (отменить) Slimper (Обсуждение | вклад) К следующему изменению →
Строка 1:		Строка 1:
-	==Постановка задачи оптимизации==	+	'''Ранговые критерии''' — это статистические тесты, в которых вместо выборочных значений используются их [[ранг]]и(номера элементов в упорядоченной по возрастанию выборке). Большинство ранговых критериев являются
-	Пусть задано множество <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^m = (x_1,\ldots,x_m),\; x_i \in \mathbb{R};\;\; y^n = (y_1,\ldots,y_n),\; y_i \in \mathbb{R}</tex>,взятые из неизвестных непрерывных распределений <tex>F(x)</tex> и <tex>G(y)</tex> соответственно.
		+
		+	Нулевая гипотеза — <tex>H_0: \quad F(x) = G(y - \mu)</tex>
		+
		+	Наиболее частая альтернативная гипотеза - <tex>H_1: \quad F(x) \ne G(y - \mu)</tex>.
		+
		+	'''Список критериев'''
		+	* [[Критерий Уилкоксона-Манна-Уитни]]
		+	* [[Критерий Фишера-Йэйтса-Терри-Гёфдинга]]
		+	* [[Критерий Ван дер Вардена ]]
		+	* [[Медианный критерий]]
		+	* [[Критерий Хаги]]
		+	* [[E-Критерий]]
		+
		+	Кроме критерие, проверяющих гипотезу сдвига для двух совокупностей, существует большое
		+	количество тестов для проверки гипотезы сдвига среди нескольких совокупностей. Здесь приведены
		+	некоторые из них.
		+	*[[Критерий Крускала-Уоллиса]]
		+	*[[Критерий Краузе]]
		+	*[[Критерий Пейджа]]
		+	*[[Критерий Вилкоксона-Вилкокс]]
		+	*[[Критерий Джонкхиера]]
		+	*[[Критерий Неменьи]]
		+	*[[Критерий Хеттманспергера ]]
		+	*[[Критерий Фридмена-Кендалла-Бэбингтона-Смита ]]
		+	*[[Критерий Хеттманспергера ]]
-	Если <tex> X = R^n </tex>, то задача оптимизации называется ''безусловной'' (''unconstrained'').
-	Если <tex> X \neq R^n </tex>, то задача оптимизации называется ''условной'' (''constrained'').
-	==Метод сопряжённых градиентов==
-	''Метод сопряжённых градиентов'' (''conjugate gradient method'') первоначально был разработан для решения систем линейных уравнений с положительно определённой матрицей. Позже этот метод обобщили для решения задач безусловной оптимизации в <tex>R^n</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> x_0 </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> \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>
	== Литература ==		== Литература ==
-	Васильев Ф. П. Методы оптимизации - Издательство «Факториал Пресс», 2002 <br/>	+	# ''Кобзарь А. И.'' Прикладная математическая статистика. — М.:&nbsp;Физматлит, 2006. — 816&nbsp;с.
-	Nocedal J., Wright S.J. Numerical Optimization ,Springer, 1999	+	# ''Hajek J., Sidak Z., Sen K. P.'' Theory of rank tests(second edition). — Academic Press, 1999. - 450&nbsp;p.
		+
		+	== См. также ==
		+	* [[Проверка статистических гипотез]] — о методологии проверки статистических гипотез.
		+	* [[Статистика (функция выборки)]]
		+
		+	== Ссылки ==
		+
		+
		+	{{Задание|Slimper|Vokov|08 января 2010}}

---

Версия 14:37, 5 января 2010

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

Содержание 1 Классификация ранговых критериев 1.1 Критерии для проверки гипотезы случайности 1.2 Критерии для проверки гипотезы симметрии 1.3 Критерии для проверки гипотезы независимости 1.4 Критерии для проверки гипотезы сдвига 2 Литература 3 См. также 4 Ссылки

Классификация ранговых критериев

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

Критерии для проверки гипотезы случайности

Критерии для проверки гипотезы симметрии

Критерии для проверки гипотезы независимости

Критерии для проверки гипотезы сдвига

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

Нулевая гипотеза —

Наиболее частая альтернативная гипотеза - .

Список критериев

• Критерий Уилкоксона-Манна-Уитни
• Критерий Фишера-Йэйтса-Терри-Гёфдинга
• Критерий Ван дер Вардена
• Медианный критерий
• Критерий Хаги
• E-Критерий

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

• Критерий Крускала-Уоллиса
• Критерий Краузе
• Критерий Пейджа
• Критерий Вилкоксона-Вилкокс
• Критерий Джонкхиера
• Критерий Неменьи
• Критерий Хеттманспергера
• Критерий Фридмена-Кендалла-Бэбингтона-Смита
• Критерий Хеттманспергера

Литература

1. Кобзарь А. И. Прикладная математическая статистика. — М.: Физматлит, 2006. — 816 с.
2. Hajek J., Sidak Z., Sen K. P. Theory of rank tests(second edition). — Academic Press, 1999. - 450 p.

См. также

• Проверка статистических гипотез — о методологии проверки статистических гипотез.
• Статистика (функция выборки)

Ссылки

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