Блок Приближения координатного спуска для моделей GPR

Для большого количества наблюдений использование точного метода оценки параметра и составление предсказаний по новым данным может оказаться дорогим (см. «Точный метод GPR»). Одним из приближения методов, которые помогают решить эту проблему для предсказания, является метод Блока координатного спуска (BCD). Можно делать прогнозы с помощью метода BCD, сначала задав метод предсказания с помощью 'PredictMethod','bcd' аргумент пары "имя-значение" в вызове fitrgp, а затем использование predict функция.

Идея метода BCD состоит в том, чтобы вычислить

$\hat{α} = {(K (X, X) + σ^{2} I_{N})}^{- 1} (y - H β)$

иным образом, чем точный метод. Оценки BCD $\hat{α}$ путем решения следующей задачи оптимизации:

$\hat{α} = {arg min}_{α} f (α)$

где

$f (α) = \frac{1}{2} α^{T} [K (X, X) + σ^{2} I_{N}] α - α^{T} (y - H β) .$

fitrgp использует блок координатного спуска (BCD), чтобы решить вышеописанную задачу оптимизации. Для пользователей, знакомых с машинами опорных векторов (SVM), последовательная минимальная оптимизация (SMO) и ISDA (итерационный алгоритм одиночных данных), используемые для соответствия SVM, являются особыми случаями BCD. fitrgp выполняет два шага для каждого обновления BCD - выбор блоков и обновление блоков. На фазе выбора блоков, fitrgp использует комбинацию случайных и жадных стратегий для выбора набора $α$ коэффициенты для оптимизации следующего. На фазе обновления блоков выбранное $α$ коэффициенты оптимизируются при сохранении других $α$ коэффициенты, фиксированные к их предыдущим значениям. Эти два шага повторяются до сходимости. BCD не хранит $n * n$ матрица $K (X, X)$ в памяти, но он просто вычисляет фрагменты $K (X, X)$ матрица при необходимости. В результате BCD является более память эффективным по сравнению с 'PredictMethod','exact'.

Практический опыт указывает, что не нужно решать задачу оптимизации для вычислений $α$ к очень высокой точности. Для примера разумно остановить итерации, когда $| | \nabla f (α) | |$ капли ниже $η | | \nabla f (α_{0}) | |$ , где $α_{0}$ - начальное значение $α$ и $η$ является малой константой (скажем, $η = 10^{- 3}$ ). Результаты из 'PredictMethod','exact' и 'PredictMethod','bcd' эквивалентны, кроме вычислений BCD $α$ по-другому. Следовательно, 'PredictMethod','bcd' можно рассматривать как эффективный способ работы с памятью 'PredictMethod','exact'. BCD часто быстрее, чем 'PredictMethod','exact' для больших n. Однако вы не можете вычислить интервалы предсказания, используя 'PredictMethod','bcd' опция. Это потому, что вычисление интервалов предсказания требует решения задачи, подобной той, которая решена для вычислений $α$ для каждой тестовой точки, что снова дорого.

Подгонка моделей GPR с использованием BCD- Приближения

Открыть скрипт

Этот пример показывает подгонку модели Gaussian Process Regression (GPR) к данным с большим количеством наблюдений, используя приближение координат блока (BCD).

Малый n - PredictMethod 'exact' и 'bcd' Получайте те же результаты

Сгенерируйте небольшой набор наборов данных.

    rng(0,'twister');
    n = 1000;
    X = linspace(0,1,n)';
    X = [X,X.^2];
    y = 1 + X*[1;2] + sin(20*X*[1;-2])./(X(:,1)+1) + 0.2*randn(n,1);

Создайте модель GPR с помощью 'FitMethod','exact' и 'PredictMethod','exact'.

    gpr = fitrgp(X,y,'KernelFunction','squaredexponential',...
        'FitMethod','exact','PredictMethod','exact');

Создайте другую модель GPR с помощью 'FitMethod','exact' и 'PredictMethod','bcd'.

    gprbcd = fitrgp(X,y,'KernelFunction','squaredexponential',...
        'FitMethod','exact','PredictMethod','bcd','BlockSize',200);

'PredictMethod','exact' и 'PredictMethod','bcd' должен быть эквивалентным. Они вычисляют то же самое $\hat{\alpha}$ , но просто по-разному. Итерации можно также увидеть при помощи 'Verbose',1 аргумент пары "имя-значение" в вызове fitrgp .

Вычислите подобранные значения двумя методами и сравните их:

    ypred    = resubPredict(gpr);
    ypredbcd = resubPredict(gprbcd);

    max(abs(ypred-ypredbcd))

ans =

   5.8853e-04

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

Теперь постройте график данных вместе с подобранными значениями для 'PredictMethod','exact' и 'PredictMethod','bcd'.

    figure;
    plot(y,'k.');
    hold on;
    plot(ypred,'b-','LineWidth',2);
    plot(ypredbcd,'m--','LineWidth',2);
    legend('Data','PredictMethod Exact','PredictMethod BCD','Location','Best');
    xlabel('Observation index');
    ylabel('Response value');

Видно, что 'PredictMethod','exact' и 'PredictMethod','bcd' получить почти одинаковые подгонки.

Большие n - Используйте 'FitMethod','sd' и 'PredictMethod','bcd'

Сгенерируйте большой набор данных, подобный предыдущему.

    rng(0,'twister');
    n = 50000;
    X = linspace(0,1,n)';
    X = [X,X.^2];
    y = 1 + X*[1;2] + sin(20*X*[1;-2])./(X(:,1)+1) + 0.2*randn(n,1);

Для n = 50000, матрица K (X, X) составила бы 50000 на 50000. Для хранения K (X, X) в памяти потребуется около 20 ГБ оперативной памяти. Чтобы соответствовать модели GPR этому набору данных, используйте 'FitMethod','sd' со случайным подмножеством m = 2000 точек. The 'ActiveSetSize' аргумент пары "имя-значение" в вызове fitrgp задает размер активного набора m. Для вычислений $\alpha$ 'PredictMethod','bcd' с 'BlockSize' от 5000. The 'BlockSize' аргумент пары "имя-значение" в fitrgp задает количество элементов $\alpha$ вектора, оптимизируемых программным обеспечением при каждой итерации. A 'BlockSize' из 5000 предполагает, что компьютер, который вы используете, может хранить матрицу 5000 на 5000 в памяти.

   gprbcd = fitrgp(X,y,'KernelFunction','squaredexponential',...,
        'FitMethod','sd','ActiveSetSize',2000,'PredictMethod','bcd','BlockSize',5000);

Постройте график данных и настроенных значений.

    figure;
    plot(y,'k.');
    hold on;
    plot(resubPredict(gprbcd),'m-','LineWidth',2);
    legend('Data','PredictMethod BCD','Location','Best');
    xlabel('Observation index');
    ylabel('Response value');

График похож на график для меньших n.

Ссылки

[1] Grippo, L. and M. Sciandrone. «О сходимости блочного нелинейного метода гаусс-сейфеля при выпуклых ограничениях». Буквы по операциям. Том 26, стр. 127-136, 2000.

[2] Bo, L. and C. Sminchisescu. Координатное спуск блока жадности для регрессии Гауссова процесса большой шкалы. В трудах двадцать четвертой конференции по неопределенности в искусственном интеллекте (UAI2008): http://arxiv.org/abs/1206.3238, 2012.

См. также

fitrgp | predict

Документация