Метод релевантных векторов

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
{{Задание|Dimaleks|Константин Воронцов|{{дата|10|1|2009}}, а сейчас {{дата}}}}
{{Задание|Dimaleks|Константин Воронцов|{{дата|10|1|2009}}, а сейчас {{дата}}}}
-
{{UnderConstruction|[[Участник:Dimaleks|Dimaleks]] 19:06, 7 января 2010 (MSK)}}
+
{{UnderConstruction|[[Участник:Dimaleks|Dimaleks]] 20:09, 7 января 2010 (MSK)}}
'''Метод релевантных векторов (RVM, Relevance vector machine)''' — алгоритм восстановления [[регрессия|регрессии]], основанный на Байесовском подходе. В методе используется обобщенная линейная модель с введенной регуляризацией, которая, в Байесовкой интерпретации, равносильна введению априорных распределений на вектор параметров. Главной особенностью является то, что все параметры регуляризируются независимо.
'''Метод релевантных векторов (RVM, Relevance vector machine)''' — алгоритм восстановления [[регрессия|регрессии]], основанный на Байесовском подходе. В методе используется обобщенная линейная модель с введенной регуляризацией, которая, в Байесовкой интерпретации, равносильна введению априорных распределений на вектор параметров. Главной особенностью является то, что все параметры регуляризируются независимо.
Строка 34: Строка 34:
:: <tex>p(\mathbf{t} |X,\mathbf{\alpha} ,\sigma^2) = \frac{1}{\sqrt{\left(2\pi\right)^m \beta^{-1}I+\Phi A ^{-1}\Phi^T \right} }\exp\left( -\frac{1}{2}\mathbf{t} ^T \left( \beta^{-1} I + \Phi A ^{-1} \Phi^T \right)^{-1} \mathbf{t} \right)</tex>,
:: <tex>p(\mathbf{t} |X,\mathbf{\alpha} ,\sigma^2) = \frac{1}{\sqrt{\left(2\pi\right)^m \beta^{-1}I+\Phi A ^{-1}\Phi^T \right} }\exp\left( -\frac{1}{2}\mathbf{t} ^T \left( \beta^{-1} I + \Phi A ^{-1} \Phi^T \right)^{-1} \mathbf{t} \right)</tex>,
-
: где <tex>\Phi</tex> — матрица объектов-признаков.
+
: где <tex>\Phi</tex> — матрица обобщенных признаков.
*Теперь, приравнивая нулю производные обоснованности по <tex>\mathbf{\alpha},\,\beta</tex>, получим итерационные формулы для пересчета параметров:
*Теперь, приравнивая нулю производные обоснованности по <tex>\mathbf{\alpha},\,\beta</tex>, получим итерационные формулы для пересчета параметров:
Строка 54: Строка 54:
*На выходе алгоритма получается разреженное решение, т. е. только небольшое подмножество исходной выборки входит в решающее правило.
*На выходе алгоритма получается разреженное решение, т. е. только небольшое подмножество исходной выборки входит в решающее правило.
*Кроме значения целевой переменной, алгоритм выдает также и дисперсию прогноза.
*Кроме значения целевой переменной, алгоритм выдает также и дисперсию прогноза.
 +
 +
== Псевдокод алгоритма RVM ==
 +
 +
'''Вход:''' Обучающая выборка <tex>\left{ \mathbf{x}_i ,t_i \right}^l_{i=1}</tex>, матрица обобщенных признаков <tex>\Phi = \left{ \phi_j(\mathbf{x}_j) \right}^{n,m}_{i,j=1}</tex><br />
 +
'''Выход:''' Параметры решающего правила: <tex>\mathbf{\omega},\,\Sigma,\,\beta</tex>
 +
::Инициализация: <tex>\alpha_i:=1,\,\,\beta:=1,\,\,AlphaBound:=10^{12},\,\, WeightBound:=10^{-6},\,\, NumberOfIterations:=50;</tex>
 +
::'''для''' <tex>k=1,\ldots,NumberOfIterations</tex> '''повторять'''
 +
:::<tex>A:=\mbox{diag}(\alpha_1,\ldots,\alpha_m);</tex>
 +
:::<tex>\Sigma:=\left( \beta\Phi^T\Phi+A \right)^{-1};</tex>
 +
:::<tex>\mathbf{\omega}_{MP}:=\Sigma\beta\Phi^T \mathbf{t};</tex>
 +
:::'''для''' <tex>j=1,\ldots,m</tex> '''повторять'''
 +
::::'''если''' <tex>\omega_{MP,j} < WeightBound</tex> или <tex>\alpha_j > AlphaBound</tex>'''то'''
 +
:::::<tex>\omega_{MP,j}:=0,\,\,\alpha_j:=+\infty,\,\,\gamma_j:=0;</tex>
 +
::::'''иначе'''
 +
:::::<tex>\gamma_j = \alpha_j^{old}\Sigma_{jj},\,\,\alpha_j = \frac{\gamma_j}{\omega^2_{MP,j};</tex>
 +
:::<tex>\beta_i^{new} = \frac{\textstyle{n-\sum_{i=1}^m\gamma_i}}{\left\parallel \mathbf{t} - \Phi\mathbf{\omega} \right\parallel^2}{\omega^2_{MP,i}</tex>

Версия 17:09, 7 января 2010

Данная статья является непроверенным учебным заданием.
Студент: Участник:Dimaleks
Преподаватель: Участник:Константин Воронцов
Срок: 10 января 2009, а сейчас 31 октября 2024

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

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


Статья в настоящий момент дорабатывается.
Dimaleks 20:09, 7 января 2010 (MSK)


Метод релевантных векторов (RVM, Relevance vector machine) — алгоритм восстановления регрессии, основанный на Байесовском подходе. В методе используется обобщенная линейная модель с введенной регуляризацией, которая, в Байесовкой интерпретации, равносильна введению априорных распределений на вектор параметров. Главной особенностью является то, что все параметры регуляризируются независимо.

Содержание

Решаемая задача

  • Имеется выборка \left(X,t\right) = \left{  \mathbf{x}_i ,t_i \right}^l_{i=1}, где вектор признаков \mathbf{x}_i \in \mathbb {R}^d, а целевая переменная t_i \in \mathbb {R}. Требуется для нового объекта \mathbf{x}_* предсказать значение целевой переменной t_*
  • Предполагается, что t=f(\mathbf{x})+\varepsilon, где \varepsilon \sim \mathfrak{N}(\varepsilon|0,\sigma^2), а
f(\mathbf{x}) = \sum_{j=1}^m \omega_j\phi_j(\mathbf{x}) = \mathbf{\omega}^T\mathbf{\phi}(\mathbf{x})

Подход к решению

  • Следуя байесовскому подходу, воспользуемся методом максимума апостериорной плотности:
\mathbf{\omega}_{MP} = \arg\,\max_{\mathbf{\omega}}\,\,p(\mathbf{\omega} |X,\mathbf{t}) = \arg\,\max_{\mathbf{\omega}} \,\,p(\mathbf{t} |X,\mathbf{\omega}) p(\mathbf{\omega})
  • Для получения разреженного решения введем в качестве априорного распределения на параметры \mathbf{\omega} нормальное распределение с диагональной матрицей ковариации с различными элементами на диагонали:
p(\mathbf{\omega} |\mathbf{\alpha}) = \mathfrak{N}(0,A^{-1})
Здесь A=\mbox{diag}\,(\alpha_1,\ldots,\alpha_m). Такое априорное распределение соответствует независимой регуляризации вдоль каждого веса \omega_i со своим параметром регуляризации \alpha_i \ge 0
  • Для обучения модели (настройки параметров \mathbf{\omega} ,\sigma ) воспользуемся идеей максимизации обоснованности:
p(\mathbf{t} |X,\mathbf{\alpha} ,\sigma^2) = \int p(\mathbf{t} |X,\mathbf{\omega}, \sigma^2)p(\mathbf{\omega} |\mathbf{\alpha} )d\mathbf{\omega} \to \max_{\mathbf{\alpha}, \sigma^2}

Оптимизация обоснованности

  • Заметив, что обоснованность является сверткой двух нормальных распределений, можно представить подынтегральную функцию по формуле Тейлора в точке максимума правдоподобия. Обозначив Q(\mathbf{\omega}) = p(\mathbf{t} |X,\mathbf{\omega}, \sigma^2)p(\mathbf{\omega} |\mathbf{\alpha} ) \mbox{, } H = \bigtriangledown\bigtriangledown\,\log Q(\mathbf{\omega}_{MP}) после некоторых преобразований получим:
\int Q( \mathbf{\omega} )d\mathbf{\omega} = \sqrt{\left(2\pi\right)^m}\frac{Q(\mathbf{\omega} _{MP})}{\sqrt{\det(-H)}}
  • Обозначив, для удобства, \beta=\sigma^{-2}, и "в лоб" раскрывая предыдущее выражение, получим:
p(\mathbf{t} |X,\mathbf{\alpha} ,\sigma^2) = \frac{1}{\sqrt{\left(2\pi\right)^m \beta^{-1}I+\Phi A ^{-1}\Phi^T \right} }\exp\left( -\frac{1}{2}\mathbf{t}  ^T  \left( \beta^{-1} I + \Phi A ^{-1} \Phi^T \right)^{-1} \mathbf{t} \right),
где \Phi — матрица обобщенных признаков.
  • Теперь, приравнивая нулю производные обоснованности по \mathbf{\alpha},\,\beta, получим итерационные формулы для пересчета параметров:
\alpha_i^{new} = \frac{\gamma_i}{\omega^2_{MP,i}
\gamma_i = \alpha_i^{old}\Sigma_{ii}
\beta_i^{new} = \frac{\textstyle{n-\sum_{i=1}^m\gamma_i}}{\left\parallel \mathbf{t} - \Phi\mathbf{\omega} \right\parallel^2}{\omega^2_{MP,i}
Здесь \Sigma = \left( \beta\Phi^T\Phi+A\right)^{-1}\mbox{,   }\; \mathbf{\omega}_{MP} = \beta\Sigma\Phi^T\mathbf{t}
  • Параметр \gamma_i можно интерпретировать как степень, в которой соотвутствующий вес \omega_i определяется данными или регуляризацией. Если \alpha_i велико, то вес \omega_i существенно предопределен априорным распределением, \textstyle \Sigma_{ii} \simeq \alpha_i^{-1} и \gamma_i \simeq 0. С другой стороны, для малых значений \alpha_i значение веса \omega_i полностью определяется данными, \gamma_i \simeq 0.

Принятие решения

  • Зная значения \mathbf{\alpha}_{MP},\,\sigma^2_{MP} можно вычислить апостериорное распределение целевой переменной:
p(t_* |\mathbf{x}_*, X) = \int p(t_* |\mathbf{x}_*, \mathbf{\omega}, \sigma^2_{MP})p(\mathbf{\omega} |X, \mathbf{\alpha}_{MP}, \sigma^2_{MP})d\mathbf{\omega} = \mathfrak{N}(t_*|\mathbf{\omega}^T_{MP} \mathbf{\phi}(\mathbf{x}_*),\,\sigma^2_{MP} + \mathbf{\phi}(\mathbf{x}_*)^T \Sigma \mathbf{\phi}(\mathbf{x}_*))

Обсуждение метода

  • На практике процесс обучения обычно требует 20-50 итераций. На каждой итерации вычисляется \mathbf{\omega}_{MP} (это требует обращения матрицы порядка m\times m), а также пересчитываются значения \mathbf{\alpha},\,\beta(пратктически не требует времени). Как следствие, скорость обучения падает примерно в 20-50 раз по сравнению с линейной регрессией.
  • При использовании ядровых функций в качестве обобщенных признаков необходимо проводить скользящий контроль для различных значений параметров ядра. В этом случае время обучения возрастает еще в несколько раз.
  • На выходе алгоритма получается разреженное решение, т. е. только небольшое подмножество исходной выборки входит в решающее правило.
  • Кроме значения целевой переменной, алгоритм выдает также и дисперсию прогноза.

Псевдокод алгоритма RVM

Вход: Обучающая выборка \left{  \mathbf{x}_i ,t_i \right}^l_{i=1}, матрица обобщенных признаков \Phi = \left{ \phi_j(\mathbf{x}_j) \right}^{n,m}_{i,j=1}
Выход: Параметры решающего правила: \mathbf{\omega},\,\Sigma,\,\beta

Инициализация: \alpha_i:=1,\,\,\beta:=1,\,\,AlphaBound:=10^{12},\,\, WeightBound:=10^{-6},\,\, NumberOfIterations:=50;
для k=1,\ldots,NumberOfIterations повторять
A:=\mbox{diag}(\alpha_1,\ldots,\alpha_m);
\Sigma:=\left( \beta\Phi^T\Phi+A \right)^{-1};
\mathbf{\omega}_{MP}:=\Sigma\beta\Phi^T \mathbf{t};
для j=1,\ldots,m повторять
если \omega_{MP,j} < WeightBound или \alpha_j > AlphaBoundто
\omega_{MP,j}:=0,\,\,\alpha_j:=+\infty,\,\,\gamma_j:=0;
иначе
\gamma_j = \alpha_j^{old}\Sigma_{jj},\,\,\alpha_j = \frac{\gamma_j}{\omega^2_{MP,j};
\beta_i^{new} = \frac{\textstyle{n-\sum_{i=1}^m\gamma_i}}{\left\parallel \mathbf{t} - \Phi\mathbf{\omega} \right\parallel^2}{\omega^2_{MP,i}
Личные инструменты