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

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

(Различия между версиями)

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

Содержание

1 Постановка задачи
2 Порождение свободных переменных
3 Алгоритм
4 Вычислительный эксперимент
5 Литература
6 Исходный код

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

Пусть задана выборка $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$ - некоторое множество индексов. Этот критерий используется при выборе модели в дальнейшем.

Мультиколлинеарность отслеживается с помощью фактора инфляции дисперсии (VIF), связанного с корреляцей данного признака с другими:

$VIF_j = \frac{1}{1 - R_j^2}$ (3)

Коэффициент детерминации j-ого признака относительно остальных вычисляется следующим образом:

$R_j^2 = 1 - \frac{||\mathbf{x}_j - X_{A\setminus\{j\}\mathbf{w}}||^2}{||\mathbf{x}_j - 1 \overline{x_j}||^2},$

где $\overline{x_j}$ - среднее значение вектроа $\mathbf{x}_j$

Требуется найти такую модель оптимальной структуры признаков $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: добавление признаков

Добавляем такой признак $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$

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

$|Evidence_k - \max_{t\in\{1,...,k-1\}}(Evidence_{t})| \geq \triangle E$ ,

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

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

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

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

$j = \arg\max_{j\in A_{k-1}} VIF_j$

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

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

$|Evidence_k - \max_{t\in\{1,...,k-1\}}(Evidence_{t})| \geq \triangle E$ ,

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

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

Критерий останова

Алгоритм заканчивает работу, если правдоподобие $Evidence_k$ перестаёт увеличиваться.

Тогда мы нашли оптимальный набор признаков.

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

Генерирование случайных данных:

m = 300; %число объектов
U = 6; %число начальных признаков
V = 4; %количестов порождающих функций
d = 1; %на сколько шагов можно уйти от максимума
 
C = rand(m,U)
w = rand(U,1)
e = 0.1 * randn(m,1)
y = C*w + e

Порождение новых признаков:

G = [Z, Z.^2, tan(Z), exp(Z)]; %множество порождающих функиций m на V*U
X = [ones(m,1), G]; %множество признаков m на N
 
N = size(X,1)
for i = 1 : U*V
    for j = 1 : U*V
        if i >= j
            X = [X, G(:,i).*G(:,j)];
            N = N + 1;
        end
    end
end

Вычисление номера признака, доставляющего минимум функционалу качества (2):

for i = 1:numel(ind)
   mask2 = mask;
   mask2(ind(i),1) = 1;
 
   X_mask2 = getXmask(X, mask2);
   [w, sse_] = lsqlin(X_mask2,y,[],[]);
 
   if i == 1
      sse_best = sse_;
   elseif sse_< sse_best
      sse_best = sse_;
      index_best = ind(i);
   end
end

Вычисление правдоподобия:

X_ = getXmask( X, mask );
xRegression=X_;
yRegression=y;
activeSet = 1:size(xRegression,2); % количество активных признаков
 
[weightM,alphaM,beta,weightH,alphaMH,betaH,gammaH] = ...
   getLinParam(xRegression,yRegression,activeSet);
beta;
evid_ = abs(getEvid( xRegression,yRegression,weightM,alphaM,beta ));

На графике выведем зависимость правдоподобия(ocь Y) от шага алгоритма(ось X)

evidence
plot(linspace(1,numel(evidence),numel(evidence)), evidence);

Эксперимент 1.

Количество объектов = 300, количество начальных признаков = 6, количество признаков = 230

Порождающие функции: $g = \{x,~x^2,~\tan(x),~\exp(x)\}$

Эксперимент 2.

Количество объектов = 300, количество начальных признаков = 6, количество признаков = 230

Порождающие функции: $g = \{x,~x^2,~\tan(x),~\exp(x)\}$

Эксперимент 3.

Количество объектов = 500, количество начальных признаков = 6, количество признаков = 230

Порождающие функции: $g = \{x,~x^2,~\tan(x),~\exp(x)\}$

Эксперимент 4.

Количество объектов = 500, количество начальных признаков = 6, количество признаков = 230

Порождающие функции: $g = \{\frac{1}{x}, x,~x^2,~\tan(x),~\exp(x)\}$

Эксперимент 5.

Количество объектов = 900, количество начальных признаков = 7, количество признаков = 441

Порождающие функции: $g = \{\frac{1}{x}, x,~x^2,~\tan(x),~\exp(x)\}$

Литература

Стрижов В.В Методы выбора регрессионных моделей. — ВЦ РАН, 2010.
Стрижов В.В Методы индуктивного порождения регрессионных моделей. — ВЦ РАН, 2008.
Vadim Strijov, Katya Krymova, Gerhard Wilhelm Weber Evidence Optimization for Consequently Generated Models. — Computing Center of the Russian Academy of Science, Moscow, Russia, 2010.

Исходный код

Minaev2010Maximum

Данная статья была создана в рамках учебного задания.

Студент: Участник:Павел Минаев

Преподаватель: В.В.Стрижов

Срок: 24 декабря 2010

В настоящее время задание завершено и проверено. Данная страница может свободно правиться другими участниками проекта MachineLearning.ru.

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

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9E%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%BA%D1%80%D0%B5%D1%81%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%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_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B5%D0%B9_%28%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%29»

Категория: Практика и вычислительные эксперименты

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

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

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

Содержание

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

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

Алгоритм

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

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

Критерий останова

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

Литература

Исходный код

Просмотры

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

Навигация

Поиск

Инструменты

@@ Строка 38: / Строка 38: @@
 где <tex>\Theta \subseteq I</tex> - некоторое множество индексов. Этот критерий используется при выборе модели в дальнейшем.
+Мультиколлинеарность отслеживается с помощью фактора инфляции дисперсии (VIF), связанного с корреляцей данного признака с другими:
+<center><tex>VIF_j = \frac{1}{1 - R_j^2}</tex> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (3)</center>
+Коэффициент детерминации j-ого признака относительно остальных вычисляется следующим образом:
+<center><tex>R_j^2 = 1 - \frac{||\mathbf{x}_j - X_{A\setminus\{j\}\mathbf{w}}||^2}{||\mathbf{x}_j - 1 \overline{x_j}||^2},</tex></center>
+где <tex>\overline{x_j}</tex> - среднее значение вектроа <tex>\mathbf{x}_j</tex>
@@ Строка 78: / Строка 92: @@
-===1. "Шаг 1: добавление признаков"===
+===Шаг 1: добавление признаков===
 Добавляем такой признак <tex>j \in J \setminus A_{k-1}</tex> к активному набору
@@ Строка 92: / Строка 106: @@
 Если выполнено условие:
-<center><tex>k - k^* \geq d</tex>,</center>
+<center><tex>|Evidence_k - \max_{t\in\{1,...,k-1\}}(Evidence_{t})|  \geq \triangle E</tex>,</center>
 то идём к шагу 2, иначе - повторяем шаг 1.
@@ Строка 98: / Строка 112: @@
 d - заданная константа.
+===Шаг 2: удаление признаков===
-===2. "Шаг 2: удаление признаков"===
 Удаляем такой признак <tex>j \in A_{k-1}</tex> из активного набора
 <tex>A_k = A_{k-1} \setminus \{j\}</tex>,
-который доставляет минимум функционалу (2).
+который имеет наибольший фактора инфляции дисперсии, то есть доставляет максимум функционалу (3).
-<center><tex>j = \arg\min_{j\in J \setminus A_{k-1}} S(X_A_k, \mathbf{y})</tex></center>
+<center><tex>j = \arg\max_{j\in A_{k-1}} VIF_j</tex></center>
@@ Строка 113: / Строка 126: @@
 Если выполнено условие:
-<center><tex>k - k^* \geq d</tex>,</center>
+<center><tex>|Evidence_k - \max_{t\in\{1,...,k-1\}}(Evidence_{t})|  \geq \triangle E</tex>,</center>
 то идём к шагу 1, иначе - повторяем шаг 2.
@@ Строка 119: / Строка 132: @@
 d - заданная константа.
+===Критерий останова===
-===3. "Конец"===
+Алгоритм заканчивает работу, если правдоподобие <tex>Evidence_k</tex> перестаёт увеличиваться.
-Алгоритм заканчивает работу, если переменная правдоподобие <tex>Evidence_k</tex> перестайтся увеличиваться.
 Тогда мы нашли оптимальный набор признаков.
@@ Строка 127: / Строка 139: @@
 == Вычислительный эксперимент ==
-== Исходный код ==
+Генерирование случайных данных:
+<source lang="matlab">
+m = 300; %число объектов
+U = 6; %число начальных признаков
+V = 4; %количестов порождающих функций
+d = 1; %на сколько шагов можно уйти от максимума
+C = rand(m,U)
+w = rand(U,1)
+e = 0.1 * randn(m,1)
+y = C*w + e
+</source>
+Порождение новых признаков:
+<source lang="matlab">
+G = [Z, Z.^2, tan(Z), exp(Z)]; %множество порождающих функиций m на V*U
+X = [ones(m,1), G]; %множество признаков m на N
+N = size(X,1)
+for i = 1 : U*V
+    for j = 1 : U*V
+        if i >= j
+            X = [X, G(:,i).*G(:,j)];
+            N = N + 1;
+        end
+    end
+end
+</source>
+Вычисление номера признака, доставляющего минимум функционалу качества (2):
+<source lang="matlab">
+for i = 1:numel(ind)
+   mask2 = mask;
+   mask2(ind(i),1) = 1;
+   X_mask2 = getXmask(X, mask2);
+   [w, sse_] = lsqlin(X_mask2,y,[],[]);
+   if i == 1
+      sse_best = sse_;
+   elseif sse_< sse_best
+      sse_best = sse_;
+      index_best = ind(i);
+   end
+end
+</source>
+Вычисление правдоподобия:
+<source lang="matlab">
+X_ = getXmask( X, mask );
+xRegression=X_;
+yRegression=y;
+activeSet = 1:size(xRegression,2); % количество активных признаков
+[weightM,alphaM,beta,weightH,alphaMH,betaH,gammaH] = ...
+   getLinParam(xRegression,yRegression,activeSet);
+beta;
+evid_ = abs(getEvid( xRegression,yRegression,weightM,alphaM,beta ));
+</source>
+'''На графике выведем зависимость правдоподобия(ocь Y) от шага алгоритма(ось X)'''
+<source lang="matlab">
+evidence
+plot(linspace(1,numel(evidence),numel(evidence)), evidence);
+</source>
+[[Изображение:evid_1.png|thumb|left]]
+[[Изображение:evid_3.png|thumb|left]]
+[[Изображение:evid_2.png|thumb|left]]
+[[Изображение:evid_4.png|thumb|left]]
+[[Изображение:evid_5.png|thumb|left]]
+Эксперимент 1.
+Количество объектов = 300,
+количество начальных признаков = 6,
+количество признаков = 230
+Порождающие функции: <tex>g = \{x,~x^2,~\tan(x),~\exp(x)\}</tex>
+Эксперимент 2.
+Количество объектов = 300,
+количество начальных признаков = 6,
+количество признаков = 230
+Порождающие функции: <tex>g = \{x,~x^2,~\tan(x),~\exp(x)\}</tex>
+Эксперимент 3.
+Количество объектов = 500,
+количество начальных признаков = 6,
+количество признаков = 230
+Порождающие функции: <tex>g = \{x,~x^2,~\tan(x),~\exp(x)\}</tex>
+Эксперимент 4.
+Количество объектов = 500,
+количество начальных признаков = 6,
+количество признаков = 230
+Порождающие функции: <tex>g = \{\frac{1}{x}, x,~x^2,~\tan(x),~\exp(x)\}</tex>
+Эксперимент 5.
+Количество объектов = 900,
+количество начальных признаков = 7,
+количество признаков = 441
+Порождающие функции: <tex>g = \{\frac{1}{x}, x,~x^2,~\tan(x),~\exp(x)\}</tex>
 == Литература ==
 # {{книга
@@ Строка 144: / Строка 316: @@
 |автор        = Vadim Strijov, Katya Krymova, Gerhard Wilhelm Weber
 |заглавие     =  Evidence Optimization for Consequently Generated Models
-|издательство = ВЦ РАН
+|издательство = Computing Center of the Russian Academy of Science, Moscow, Russia
 |год          = 2010
 }}
+== Исходный код ==
+[https://mlalgorithms.svn.sourceforge.net/svnroot/mlalgorithms/MIPT2006-2010OldProj/Minaev2010Maximum/  Minaev2010Maximum]
+{{ЗаданиеВыполнено|Павел Минаев|В.В.Стрижов|24 декабря 2010||Strijov}}
+[[Категория:Практика и вычислительные эксперименты]]