Метод релевантных векторов
Материал из MachineLearning.
Строка 5: | Строка 5: | ||
== Решаемая задача == | == Решаемая задача == | ||
- | *Имеется выборка <tex>\left(X,t\right) = \left{ \mathbf{x}_i ,t_i \right}^l_{i=1}</tex>, где вектор признаков <tex>\mathbf{x}_i \in \mathbb {R}^ | + | *Имеется выборка <tex>\left(X,t\right) = \left{ \mathbf{x}_i ,t_i \right}^l_{i=1}</tex>, где вектор признаков <tex>\mathbf{x}_i \in \mathbb{R}^m</tex>, а целевая переменная <tex>t_i \in \mathbb {R}</tex>. Требуется для нового объекта <tex>\mathbf{x}_*</tex> предсказать значение целевой переменной <tex>t_*</tex> |
*Предполагается, что <tex>t=f(\mathbf{x})+\varepsilon</tex>, где <tex>\varepsilon \sim \mathfrak{N}(\varepsilon|0,\sigma^2)</tex>, а | *Предполагается, что <tex>t=f(\mathbf{x})+\varepsilon</tex>, где <tex>\varepsilon \sim \mathfrak{N}(\varepsilon|0,\sigma^2)</tex>, а | ||
Строка 32: | Строка 32: | ||
* Обозначив, для удобства, <tex>\beta=\sigma^{-2}</tex>, и "в лоб" раскрывая предыдущее выражение, получим: | * Обозначив, для удобства, <tex>\beta=\sigma^{-2}</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} | + | :: <tex>p(\mathbf{t} |X,\mathbf{\alpha} ,\sigma^2) = \frac{1}{\sqrt{\left(2\pi\right)^m \det\left(\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> — матрица обобщенных признаков. | ||
Строка 39: | Строка 39: | ||
::<tex>\alpha_i^{new} = \frac{\gamma_i}{\omega^2_{MP,i}</tex> | ::<tex>\alpha_i^{new} = \frac{\gamma_i}{\omega^2_{MP,i}</tex> | ||
::<tex>\gamma_i = \alpha_i^{old}\Sigma_{ii}</tex> | ::<tex>\gamma_i = \alpha_i^{old}\Sigma_{ii}</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> | + | ::<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> |
:Здесь <tex>\Sigma = \left( \beta\Phi^T\Phi+A\right)^{-1}\mbox{, }\; \mathbf{\omega}_{MP} = \beta\Sigma\Phi^T\mathbf{t}</tex> | :Здесь <tex>\Sigma = \left( \beta\Phi^T\Phi+A\right)^{-1}\mbox{, }\; \mathbf{\omega}_{MP} = \beta\Sigma\Phi^T\mathbf{t}</tex> | ||
Строка 65: | Строка 65: | ||
'''Вход:''' Обучающая выборка <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>\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>\mathbf{\omega},\,\Sigma,\,\beta</tex> | ||
- | ::Инициализация: <tex>\alpha_i:=1,\,\,\beta:=1,\,\,AlphaBound:=10^{12},\,\, WeightBound:=10^{-6},\,\, NumberOfIterations:=50;</tex> | + | ::Инициализация: <tex>\alpha_i\,:=\,1,\,\,\beta\,:=\,1,\,\,AlphaBound\,:=\,10^{12},\,\, WeightBound\,:=\,10^{-6},\,\, NumberOfIterations\,:=\,50;</tex> |
::'''для''' <tex>k=1,\ldots,NumberOfIterations</tex> '''повторять''' | ::'''для''' <tex>k=1,\ldots,NumberOfIterations</tex> '''повторять''' | ||
- | :::<tex>A:=\mbox{diag}(\alpha_1,\ldots,\alpha_m);</tex> | + | :::<tex>A\,:=\,\mbox{diag}(\alpha_1,\ldots,\alpha_m);</tex> |
- | :::<tex>\Sigma:=\left( \beta\Phi^T\Phi+A \right)^{-1};</tex> | + | :::<tex>\Sigma\,:=\,\left( \beta\Phi^T\Phi+A \right)^{-1};</tex> |
- | :::<tex>\mathbf{\omega}_{MP}:=\Sigma\beta\Phi^T \mathbf{t};</tex> | + | :::<tex>\mathbf{\omega}_{MP}\,:=\,\Sigma\beta\Phi^T \mathbf{t};</tex> |
:::'''для''' <tex>j=1,\ldots,m</tex> '''повторять''' | :::'''для''' <tex>j=1,\ldots,m</tex> '''повторять''' | ||
- | ::::'''если''' <tex>\omega_{MP,j} < WeightBound</tex> или <tex>\alpha_j > AlphaBound</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>\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>\gamma_j = \alpha_j^{old}\Sigma_{jj},\,\,\alpha_j = \frac{\gamma_j}{\omega^2_{MP,j}</tex><tex>;</tex> |
- | :::<tex>\beta_i | + | :::<tex>\beta_i = \frac{\textstyle{n-\sum_{i=1}^m\gamma_i}}{{\left\parallel \mathbf{t} - \Phi\mathbf{\omega} \right\parallel}^2}{\omega^2_{MP,i}\,;</tex> |
==См. также== | ==См. также== |
Версия 18:04, 7 января 2010
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
![]() | Статья в настоящий момент дорабатывается. Dimaleks 20:09, 7 января 2010 (MSK) |
Метод релевантных векторов (RVM, Relevance vector machine) — алгоритм восстановления регрессии, основанный на Байесовском подходе. В методе используется обобщенная линейная модель с введенной регуляризацией, которая, в Байесовкой интерпретации, равносильна введению априорных распределений на вектор параметров. Главной особенностью является то, что все параметры регуляризируются независимо.
Содержание |
Решаемая задача
- Имеется выборка
, где вектор признаков
, а целевая переменная
. Требуется для нового объекта
предсказать значение целевой переменной
- Предполагается, что
, где
, а
Подход к решению
- Следуя байесовскому подходу, воспользуемся методом максимума апостериорной плотности:
- Для получения разреженного решения введем в качестве априорного распределения на параметры
нормальное распределение с диагональной матрицей ковариации с различными элементами на диагонали:
- Здесь
. Такое априорное распределение соответствует независимой регуляризации вдоль каждого веса
со своим параметром регуляризации
- Для обучения модели (настройки параметров
) воспользуемся идеей максимизации обоснованности:
Оптимизация обоснованности
- Заметив, что обоснованность является сверткой двух нормальных распределений, можно представить подынтегральную функцию по формуле Тейлора в точке максимума правдоподобия. Обозначив
, после некоторых преобразований получим:
- Обозначив, для удобства,
, и "в лоб" раскрывая предыдущее выражение, получим:
-
,
-
- где
— матрица обобщенных признаков.
- Теперь, приравнивая нулю производные обоснованности по
, получим итерационные формулы для пересчета параметров:
- Здесь
- Параметр
можно интерпретировать как степень, в которой соответствующий вес
определяется данными или регуляризацией. Если
велико, то вес
существенно предопределен априорным распределением,
и
. С другой стороны, для малых значений
значение веса
полностью определяется данными,
.
Принятие решения
- Зная значения
можно вычислить апостериорное распределение целевой переменной:
Обсуждение метода
- На практике процесс обучения обычно требует 20-50 итераций. На каждой итерации вычисляется
(это требует обращения матрицы порядка
), а также пересчитываются значения
(пратктически не требует времени). Как следствие, скорость обучения падает примерно в 20-50 раз по сравнению с линейной регрессией.
- При использовании ядровых функций в качестве обобщенных признаков необходимо проводить скользящий контроль для различных значений параметров ядра. В этом случае время обучения возрастает еще в несколько раз.
- На выходе алгоритма получается разреженное решение, т. е. только небольшое подмножество исходной выборки входит в решающее правило.
- Кроме значения целевой переменной, алгоритм выдает также и дисперсию прогноза.
Псевдокод алгоритма RVM
Вход: Обучающая выборка , матрица обобщенных признаков
Выход: Параметры решающего правила:
- Инициализация:
- для
повторять
- для
повторять
- если
или
, то
- иначе
- если
- Инициализация:
См. также
Байесовский классификатор
Линейная регрессия
ЕМ-алгоритм, его модификации и обобщения