Метод релевантных векторов
Материал из MachineLearning.
Строка 1: | Строка 1: | ||
{{Задание|Dimaleks|Константин Воронцов|{{дата|10|1|2009}}, а сейчас {{дата}}}} | {{Задание|Dimaleks|Константин Воронцов|{{дата|10|1|2009}}, а сейчас {{дата}}}} | ||
- | {{UnderConstruction|[[Участник:Dimaleks|Dimaleks]] | + | {{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
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
![]() | Статья в настоящий момент дорабатывается. Dimaleks 20:09, 7 января 2010 (MSK) |
Метод релевантных векторов (RVM, Relevance vector machine) — алгоритм восстановления регрессии, основанный на Байесовском подходе. В методе используется обобщенная линейная модель с введенной регуляризацией, которая, в Байесовкой интерпретации, равносильна введению априорных распределений на вектор параметров. Главной особенностью является то, что все параметры регуляризируются независимо.
Содержание |
Решаемая задача
- Имеется выборка
, где вектор признаков
, а целевая переменная
. Требуется для нового объекта
предсказать значение целевой переменной
- Предполагается, что
, где
, а
Подход к решению
- Следуя байесовскому подходу, воспользуемся методом максимума апостериорной плотности:
- Для получения разреженного решения введем в качестве априорного распределения на параметры
нормальное распределение с диагональной матрицей ковариации с различными элементами на диагонали:
- Здесь
. Такое априорное распределение соответствует независимой регуляризации вдоль каждого веса
со своим параметром регуляризации
- Для обучения модели (настройки параметров
) воспользуемся идеей максимизации обоснованности:
Оптимизация обоснованности
- Заметив, что обоснованность является сверткой двух нормальных распределений, можно представить подынтегральную функцию по формуле Тейлора в точке максимума правдоподобия. Обозначив
после некоторых преобразований получим:
- Обозначив, для удобства,
, и "в лоб" раскрывая предыдущее выражение, получим:
-
,
-
- где
— матрица обобщенных признаков.
- Теперь, приравнивая нулю производные обоснованности по
, получим итерационные формулы для пересчета параметров:
- Здесь
- Параметр
можно интерпретировать как степень, в которой соотвутствующий вес
определяется данными или регуляризацией. Если
велико, то вес
существенно предопределен априорным распределением,
и
. С другой стороны, для малых значений
значение веса
полностью определяется данными,
.
Принятие решения
- Зная значения
можно вычислить апостериорное распределение целевой переменной:
Обсуждение метода
- На практике процесс обучения обычно требует 20-50 итераций. На каждой итерации вычисляется
(это требует обращения матрицы порядка
), а также пересчитываются значения
(пратктически не требует времени). Как следствие, скорость обучения падает примерно в 20-50 раз по сравнению с линейной регрессией.
- При использовании ядровых функций в качестве обобщенных признаков необходимо проводить скользящий контроль для различных значений параметров ядра. В этом случае время обучения возрастает еще в несколько раз.
- На выходе алгоритма получается разреженное решение, т. е. только небольшое подмножество исходной выборки входит в решающее правило.
- Кроме значения целевой переменной, алгоритм выдает также и дисперсию прогноза.
Псевдокод алгоритма RVM
Вход: Обучающая выборка , матрица обобщенных признаков
Выход: Параметры решающего правила:
- Инициализация:
- для
повторять
- для
повторять
- если
или
то
- иначе
- если
- Инициализация: