Описание окрестности точки наибольшего правдоподобия моделей (пример)

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

(Различия между версиями)
Перейти к: навигация, поиск
(Алгоритм)
(Алгоритм)
Строка 73: Строка 73:
На втором шаге мы будем удалять признаки по одному из нашей модели согласно тому же критерию качества (2).
На втором шаге мы будем удалять признаки по одному из нашей модели согласно тому же критерию качества (2).
-
Пусть на <tex>k</tex>-ом шагу алгоритма имеется множество признаков <tex>A</tex>, которое определяет матрицу <tex>X_A</tex>: <tex>\mathbf{y} = X_A \mathbf{w}</tex>. На нулевом шаге <tex>A_0 = \emptyset</tex>. Опишем <tex>k</tex>-ый шаг алгоритма.
+
Пусть на <tex>k</tex>-ом шагу алгоритма имеется множество признаков <tex>A</tex>, которое определяет матрицу <tex>X_A</tex>: <tex>\mathbf{y} = X_A \mathbf{w}</tex>.
 +
На нулевом шаге <tex>A_0 = \emptyset</tex>. Опишем <tex>k</tex>-ый шаг алгоритма.
-
1. "Шаг 1: добавление признаков"
 
-
Добавляем признак такой <tex>j \in J \setminus A_{k-1}</tex> к активному набору
+
===1. "Шаг 1: добавление признаков"===
 +
 
 +
Добавляем такой признак <tex>j \in J \setminus A_{k-1}</tex> к активному набору
<tex>A_k = A_{k-1} \cup \{j\}</tex>,
<tex>A_k = A_{k-1} \cup \{j\}</tex>,
который доставляет минимум функционалу (2).
который доставляет минимум функционалу (2).
Строка 86: Строка 88:
-
Повторяем шаг 1, пока выполнено условие:
+
Пусть <center><tex>k^* = \arg\max_{t=1,\ldots,k} Evidence_t</tex></center>
-
<tex>k^* = \arg\max_{t=1,\ldots,k} Evidence_t</tex>
+
Если выполнено условие:
-
Если <tex>k - k^* \geq d</tex>, то идём к шагу 2.
+
<center><tex>k - k^* \geq d</tex>,</center>
 +
то идём к шагу 2, иначе - повторяем шаг 1.
 +
d - заданная константа.
-
2. "Шаг 2: удаление признаков"
 
-
Добавляем признак такой <tex>j \in J \setminus A_{k-1}</tex> к активному набору
+
===2. "Шаг 2: удаление признаков"===
-
<tex>A_k = A_{k-1} \cup \{j\}</tex>,
+
 
 +
Удаляем такой признак <tex>j \in A_{k-1}</tex> из активного набора
 +
<tex>A_k = A_{k-1} \setminus \{j\}</tex>,
который доставляет минимум функционалу (2).
который доставляет минимум функционалу (2).
Строка 104: Строка 109:
-
Повторяем шаг 1, пока выполнено условие:
+
Пусть <center><tex>k^* = \arg\max_{t=1,\ldots,k} Evidence_t</tex></center>
 +
 
 +
Если выполнено условие:
 +
 
 +
<center><tex>k - k^* \geq d</tex>,</center>
-
<tex>k^* = \arg\max_{t=1,\ldots,k} Evidence_t</tex>
+
то идём к шагу 1, иначе - повторяем шаг 2.
-
Если <tex>k - k^* \geq d</tex>, то идём к шагу 2.
+
d - заданная константа.
== Вычислительный эксперимент ==
== Вычислительный эксперимент ==

Версия 00:40, 16 декабря 2010

Содержание

Постановка задачи

Пусть задана выборка D = \{(\mathbf{x}^i, y^i\)} из m пар.

\{\mathbf{x}^i\}^m_{i=1} - множество из m объектов, \mathbf{x}^i = [x^i_1, \ldots, x^i_n]^T \in\mathbb{R}^n , где n - количество признаков, а y^i\in\mathbb{R} - соответствующая зависимая переменная.

\mathbf{x}_j = [x^1_j, \ldots, x^m_j]^T \in\mathbb{R}^m - вектор значений j-ого признака, а \mathbf{y} = [y^1, \ldots, y^m]^T \in\mathbb{R}^m - вектор целевого признака.


D = ([\mathbf{x}_1, \ldots, \mathbf{x}_n], \mathbf{y}) = (X, \mathbf{y})


Пусть I = \{1, \ldots, m\} - множество индексов объектов, J = \{1, \ldots,n\} - множество индексов признаков. A\subseteq J - подмножество активных признаков. Множество A задаёт регрессионную модель f_A, а c_f = |A| - сложность модели.

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


\mathbf{y} = f_A(X, \mathbf{w}) + \mathbf{\varepsilon} = X \mathbf{w} + \mathbf{\varepsilon} ,       (1)


где \mathbf{w} = [\ldots, w_j, \ldots]^T_{j\in A} - вектор параметров регрессии, а случайная аддитивная переменная \mathbf{\varepsilon} регрессионной модели имеет нормальное распределение \varepsilon \in N(0, \sigma^2).


Распределение зависимой переменной будет иметь следующий вид:

p(y|x, \mathbf{w}, \sigma^2, f) = \frac{exp(-\frac{1}{\sigma^2}S)}{(2\pi\sigma^2){\frac{n}{2}}},


где S - сумма квадратов невязок y^i - f(\mathbf{x}^i, \mathbf{w}). Согласно оценки точки наибольшего правдоподобия, данное распределение задаёт критерий качества модели, равный сумме квадратов регрессионных остатков.

S = \sum_{i\in \Theta} (y^i - f(\mathbf{x}^i, \mathbf{w}))^2 ,       (2)


где \Theta \subseteq I - некоторое множество индексов. Этот критерий используется при выборе модели в дальнейшем.


Требуется найти такую модель оптимальной структуры признаков F, которая доставляет наименьшее значение функционалу качества (2).

Порождение свободных переменных

Множества измеряемых признаков бывает недостаточно для построения модели удовлетворительного качества. Требуется расширить множество признаков с помощью функциональных преобразований.

Предлагается следующий способ порождения новых признаков:

Пусть задано множество свободных переменных Z = \{\xi_u\}^U_{u=1} и конечное множество порождающих функций G = \{g_v\}^V_{v=1}.

Обозначим a_i = g_v(\xi_u), где индекс i = (v - 1)U + u.

Рассмотрим декартово произведение Z \times G, где элементу (g_v,\xi_u) ставится в соответствие суперпозиция g_v(\xi_u), однозначно определяемая индексами v,u.

В качестве модели, описывающей отношение между зависимой переменной y и свободными переменными a_i, используется полином Колмогорова-Габора:


y=w_0+\sum_{\alpha=1}^{UV}w_{\alpha}a_{\alpha} + \sum_{\alpha=1}^{UV}\sum_{\beta=1}^{UV}w_{{\alpha}{\beta}}a_{\alpha}a_{\beta} + \ldots +\sum_{\alpha=1}^{UV}\ldots\sum_{\psi=1}^{UV}w_{{\alpha} \ldots {\psi}}a_{\alpha}\ldots a_{\psi}
,


где \mathbf{w} = (w_0, w_{\alpha}, w_{\alpha\beta}, \ldots , w_{{\alpha} \ldots {\psi}})^T и {\alpha, \beta, \ldots , \psi = 1 \ldots UV}.


 \{0\} \cup \{\alpha\} \cup \{\alpha,\beta\} \cup \ldots \cup \{\alpha,\beta \ldots \psi\} \rightarrow \Omega - множество индексов, размерности N.

\xi_u~ \longrightarrow\longrightarrow\longrightarrow^{g_v}\longrightarrow\longrightarrow ~g_v(\xi_u) ~=^{def} a_i~\longrightarrow\longrightarrow^{\prod^{UV}_{\alpha=1}}\longrightarrow^{\ldots}\longrightarrow^{\prod^{UV}_{\psi=1}}\longrightarrow  ~x_j

Алгоритм

Рассмотрим алгоритм, состоящий из двух шагов.

На первом шаге мы будем добавлять признаки один за другим к нашей модели согласно критерию качества модели (2).

На втором шаге мы будем удалять признаки по одному из нашей модели согласно тому же критерию качества (2).

Пусть на k-ом шагу алгоритма имеется множество признаков A, которое определяет матрицу X_A: \mathbf{y} = X_A \mathbf{w}.

На нулевом шаге A_0 = \emptyset. Опишем k-ый шаг алгоритма.


1. "Шаг 1: добавление признаков"

Добавляем такой признак j \in J \setminus A_{k-1} к активному набору A_k = A_{k-1} \cup \{j\}, который доставляет минимум функционалу (2).


j = \arg\min_{j\in J \setminus A_{k-1}} S(X_A_k, \mathbf{y})


Пусть
k^* = \arg\max_{t=1,\ldots,k} Evidence_t

Если выполнено условие:

k - k^* \geq d,

то идём к шагу 2, иначе - повторяем шаг 1.

d - заданная константа.


2. "Шаг 2: удаление признаков"

Удаляем такой признак j \in A_{k-1} из активного набора A_k = A_{k-1} \setminus \{j\}, который доставляет минимум функционалу (2).


j = \arg\min_{j\in J \setminus A_{k-1}} S(X_A_k, \mathbf{y})


Пусть
k^* = \arg\max_{t=1,\ldots,k} Evidence_t

Если выполнено условие:

k - k^* \geq d,

то идём к шагу 1, иначе - повторяем шаг 2.

d - заданная константа.

Вычислительный эксперимент

Исходный код

Литература

  1. Стрижов В.В Методы выбора регрессионных моделей. — ВЦ РАН, 2010.

 

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