Алгоритмы выбора линейных регрессионных моделей (практика)

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

Перейти к: навигация, поиск

Описание библиотеки алгоритмов выбора линейных регрессионных моделей

Библиотека находится по ссылке.

Вспомогательные функции

Содержание

1 Введение
2 Архитектура
- 2.1 Соглашения об интерфейсе функций
- 2.2 Шаблон шапки файла метода
3 Реализованные алгоритмы
4 Литература

Введение

Реализованы алгоритмы выбора линейных регрессионных моделей.

Рассмотрена следующая задача. Задана выборка $\{(\mathbf{x}^i,y_i)\}_{i=1}^m$ ,где $\mathbf{x^i}\in\mathbf{R}^m$ — вектор значений свободных переменных $x_1,x_2,\dots,x_m$ , $y\in\mathbf{R}$ .

Линейная модель представима в виде $\mathbf{y}=A\mathbf{w}$ , где столбцы матрицы — значения свободных переменных и $\mathbf{y}=\{y_1,\ldots,y_N\}$ .

Требуется выбрать множество индексов столбцов матрицы $A$ , задающие модель, которые доставляют минимум заданному критерию качества.

При построении модели выполняется настройка параметров модели с помощью метода наименьших квадратов, оценивается ее качество.

Модель с настроенными параметрами, доставляющая минимум заданному функционалу качества, называется моделью оптимальной структуры.

Кроме алгоритма LARS, все алгоритмы на этапе выбора регрессионных моделей для найденных множеств индексов используют скользящий контроль.

В алгоритме LARS для выбора моделей используется критерий Маллоуза.

Архитектура

Соглашения об интерфейсе функций

Для унификации способов применения методов выбора модели предусмотрен формат интерфейса функции.

На вход каждый метод принимает 3 параметра:

features — матрица признакового описания объектов, в которой строки соответствуют объектам, а столбцы - признакам;
target - столбец значений целевого признака;
Params - структура с параметрами алгоритма; она может обладать следующими полями:
- Common - структура, содержащая общие параметры алгоритмов:
  - maxNFeatures - максимальное допустимое количество отобранных информативных признаков;
- ИмяМетода - для каждого метода структура с его собственными параметрами; например, для метода полного перебора esearch параметры должны быть доступны как поля структуры Params.Esearch.

На вход методам может передаваться структура параметров, содержащая не все поля (поле Params.Common и поля, соответствующие конкретным методам), а также не все их поля (например, может быть не задано Params.Common.maxNFeatures). Если необходимые алгоритму параметры не заданы, должны быть использованы некоторые значения "по умолчанию".

На выходе каждый метод возвращает описание набора информативных признаков и их весов в виде структуры с полями:

isInformative - логический вектор-столбец, представляющий собой маску информативных признаков (выбранным информативным признакам соответствует true, остальным - false);
weight - столбец с весами каждого признака; для неинформативных признаков веса должны быть нулевыми.

Шаблон шапки файла метода

function FeaturesRating = methodName(features, target, Params)
% Description.
%
% Arguments
% Input
%   features - matrix of features, where rows are objects, and colums are feature vectors
%   target   - target feature vector
%   Params   - structure with fields 
%     Common      - common params; structure with fields
%       maxNFeatures - maximum features number to select
%     MethodName  - structure with params for particular method
% Output
%   FeaturesRating - structure with rating for all features; has fields
%     isInformative - logical column of marks is particular feature informative (true) or not (false)
%     weight        - weight of particular feature
%
% Example
% TODO
%
% See also
% TODO
% 
% Revisions
% TODO

TODO Example

Реализованные алгоритмы

Полный перебор [esearch]

Лассо Тибширани [lasso]

Least Angle Regression (LARS) [lars]

Генетический алгоритм [genetic]

метод группового учета аргиментов (МГУА) [gmdh]

алгоритм последовательного добавления признаков с ортогонализацией (FOS) [forwardos]

Гребневая регрессия [ridgeregr]

Случайный поиск с адаптацией (СПА) [rsa]

Алгоритм случайного поиска с адаптацией похож на генетический, но лишен операции скрещивания, зато обладает более сложной операцией мутации — признаки из хороших наборов появляются с большей вероятностью, чем из плохих.

Вход:

$F$ — набор признаков
$X$ — обучающая выборка
$Q$ — критерий качества (степень ошибки)
$d$ — количество шагов осле наождения оптимума
$j_{max}$ — максимальное число признаков в наборе
$T$ — количество итераций
$N$ — количество генерируемых наборов на каждой итерации
$h$ — скорость адаптации (шаг изменения вероятностей)

Алгоритм:

для всех признаков равные вероятности: $\forall i\in\{1,\ldots,m\} p_i:=1/m$
для всех сложностей наборов:
1. для всех итераций:
  1. генерация набора признаков согласно вероятностям: $F_t=\{F_{t1},\ldots,F_{tN}\}$ , $|F_{t1}|=\ldots=|F_{tN}|=j$
  2. лучший набор: $F_t^{min}:=\arg\min_{F_{ti}\in F_t}Q(F_{ti})$
  3. худший набор: $F_t^{max}:=\arg\max_{F_{ti}\in F_t}Q(F_{ti})$
  4. суммарное наказание: $\Delta P:=0$
  5. по всем плохим признакам:
    1. $\Delta p_i:=\min\{p_i,h\}$
    2. $p_i:=p_i-\Delta p_i$
    3. $\Delta P:=\Delta P+\Delta p_i$
  6. по всем хорошим признакам:
    1. $p_i:=p_i+\Delta P/j$
2. лучший набор из просмотренных: $F_{j^*}:=\arg\min_{k\le j}Q(F_k)$
3. если $j\ge j^*+d$ , то вернуть $F_{j^*}$

Поиск самой длинной проекции вектора ответов на биссекторы векторов признаков [maxkselect]

Алгоритм использует идею последовательного уменьшения вектора ответов за счет вычитания проекций на биссекторы векторов признаков. Аналогичная идея используется в алгоритме LARS, но данный алгоритм выбирает вектор для проецирования по другому принципу. Пусть остаток вектора ответов после проецироваиня, так же как и в алгоритме LARS, лежит на биссекторе двух векторов признаков. Тогда, перебрав все такие биссекторы, мы можем оценить длину вычитаемого вектора и длину остатка. Идея заключается в максимизации длины вычитаемого на каждом шаге. Сначала находится пара признаков, для которых длина вычитаемого вектора наибольшая. Затем вектор ответов уменьшается на этот вектор, а соответствующий коэффициент увеличивается.

Вход:

$f_1,\dots,f_n$ — векторы признаков; $\forall i~\|f_i\|=1$
$y$ — вектор ответов

Выход:

$\alpha_1,\dots,\alpha_n$ — коэффициенты линейного разложения вектора ответов по векторам признаков

Алгоритм:

инициализация: $\forall i~\alpha_i:=0$
повторять
1. найти пару признаков $f_p$ , $f_q$ и коэффициент $k$ : $\left(f_p,f_q,k\right)=\arg\max\limits_{(f_i,f_j,k)}|k|:|\langle f_i,y-kf_i\rangle|=|\langle f_j,y-kf_j\rangle|$
2. $y:=y-kf_p$
3. $\alpha_p:=\alpha_p+k$