Просмотр

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

У вас нет прав на выполнение этой операции по следующим причинам:

• Запрошенное действие могут выполнять только участники из групп emailconfirmed, Администраторы.
• Вы должны подтвердить ваш адрес электронной почты перед правкой страниц. Пожалуйста, введите и подтвердите ваш адрес эл. почты на странице настроек.

Вы можете просмотреть и скопировать исходный текст этой страницы:

Метод наименьших углов (англ.&nbsp;least angle regression,&nbsp;LARS)&nbsp;- алгоритм отбора признаков в задачах линейной [[регрессия|регрессии]]. Алгоритм предложили Бредли Эфрон, Тревор Хасти и Роберт Тибширани [http://stat.stanford.edu/~imj/WEBLIST/2004/LarsAnnStat04.pdf]. LARS решает следующую задачу. Пусть назначена [[линейная регрессия (пример)|линейная регрессионная модель]]. При большом количестве свободных переменных возникает проблема [[ридж-регрессия|неустойчивого оценивания]] весов модели. LARS предлагает метод выбора такого набора свободных переменных, который имел бы наиболее значимую статистическую связь с зависимой переменной. Также LARS предлагает метод оценки весов. Алгоритм LARS похож на алгоритм [[шаговая регрессия|шаговой регрессии]]. Различие в том, что алгоритм LARS, вместо последовательного добавления свободных переменных, на каждом шаге изменяет их веса. Веса увеличиваются так, чтобы доставить наибольшую корреляцию с вектором [[анализ регрессионных остатков|регрессионных остатков]]. Основным достоинством LARS является то, что он выполняется за число шагов, не превышающее число свободных переменных. Частным случаем алгоритма LARS является алгоритм [[Лассо|LASSO]]. == Постановка задачи == Задана выборка&nbsp;- матрица&nbsp;<tex>X</tex>, столбцы которой соответствуют независимым переменным, а строки&nbsp;- элементам выборки и вектор&nbsp;<tex>\mathbf{y}</tex>, содержащий элементы зависимой переменной. Назначена линейная модель <tex>\mathbf{y}=X\mathbf{\beta}+\mathbf{\varepsilon}</tex>. Обозначим множество столбцов матрицы <tex>X</tex> как <tex>\{\mathbf{x}_1,\ldots,\mathbf{x}_n\}</tex>. Пусть выполнены условия нормировки <center><tex> \|\mathbf{y}\|_1=0, </tex> &nbsp;&nbsp;&nbsp; <tex> \|\mathbf{x}_j\|_1=0, </tex> &nbsp;&nbsp;&nbsp; <tex>\|\mathbf{x}_j\|_2^2=1, </tex> &nbsp;&nbsp;&nbsp;где&nbsp;&nbsp;&nbsp; <tex> j=1,\ldots,n.</tex></center> Предполагается, что векторы <tex>\mathbf{x}_1,\ldots,\mathbf{x}_n</tex> линейно независимы. Критерием качества модели назначена среднеквадратичная ошибка <center><tex> S(\mathbf{\beta}) = \|\mathbf{y}-\mathbf{\mu}\|^2, </tex>&nbsp;&nbsp;&nbsp; где&nbsp;&nbsp;&nbsp;<tex>\mathbf{\mu} = X\mathbf{\beta}.</tex></center> Требуется найти для каждого шага LARS вектор весов&nbsp;<tex>\mathbf{\beta}</tex> и набор столбцов, доставляющий наибольшую корреляцию векторов&nbsp;<tex>\mathbf{\mu}</tex> и&nbsp;<tex>\mathbf{y}</tex>. == Описание алгоритма == LARS последовательными шагами строит оценку коэффициентов <tex>\hat{\mathbf{\beta}}</tex>. На&nbsp;<tex>k</tex>-м шаге только&nbsp;<tex>k</tex> элементов вектора <tex>\hat{\mathbf{\beta}}</tex> отличны от нуля. Алгоритм последовательно вычисляет приближение вектора значений зависимой переменной <center><tex>\mathbf{\mu}=X\mathbf{\beta}.</tex></center> Для приближений используется вектор корреляций столбцов матрицы&nbsp;<tex>X</tex> с&nbsp;вектором остатков&nbsp;<tex>\mathbf{y}-\mathbf{\mu}</tex> <center><tex>\mathbf{c}(\mathbf{\mu})=X^T(\mathbf{y}-\mathbf{\mu}).</tex></center> [[Изображение:lars_2d.png|right|frame| Пример работы алгоритма в случае двух переменных. Пусть вектор&nbsp;<tex>\bar{\mathbf{y}}_2</tex> является проекцией вектора&nbsp;<tex>\mathbf{y}</tex> на линейное подпространство <tex>\text{span}(\mathbf{x}_1,\mathbf{x}_2)</tex>. Назначим начальное приближение&nbsp;<tex>\hat{\mathbf{\mu}}_0= \mathbf{0}</tex>. Вектор регрессионных остатков&nbsp;<tex>\bar{\mathbf{y}}_2-\hat{\mathbf{\mu}}_0</tex> коррелирует с&nbsp;вектором&nbsp;<tex>\mathbf{x}_1</tex> больше, чем с вектором&nbsp;<tex>\mathbf{x}_2</tex>. Первый шаг заключается в оценке&nbsp;<tex>\hat{\mathbf{\mu}}_1=\hat{\mathbf{\mu}}_0+\gamma_1\mathbf{x}_1</tex>. Скаляр&nbsp;<tex>\gamma_1</tex> выбирается таким образом, что вектор остатков&nbsp;<tex>\bar{\mathbf{y}}_2-\hat{\mathbf{\mu}}_0</tex> делит пополам угол между векторами&nbsp;<tex>\mathbf{x}_1</tex> и&nbsp;<tex>\mathbf{x}_2</tex>. Далее получаем значение&nbsp;<tex>\hat{\mathbf{\mu}}_2=\hat{\mathbf{\mu}}_1+\gamma_2\mathbf{u}_2</tex>, где&nbsp;<tex>\mathbf{u}_2</tex>&nbsp;- нормированный вектор, делящий этот угол пополам. Так как мы рассматриваем случай двух переменных, то <tex>\hat{\mathbf{\mu}}_2=\bar{\mathbf{y}}_2</tex>. ]] На <tex>k</tex>-м шаге новое значение приближения вектора значений зависимой переменной&nbsp;<tex>\mathbf{y}</tex> вычисляется&nbsp;как <center><tex>\hat{\mathbf{\mu}}_k=\hat{\mathbf{\mu}}_{k-1}+\gamma_k\mathbf{u}_k.</tex></center> Здесь&nbsp;<tex>\mathbf{u}_k</tex>&nbsp;- нормированный вектор, задающий биссектрису между добавляемым вектором — столбцом матрицы&nbsp;<tex>X</tex> и вектором регрссионных остатков. Он вычисляется следующим образом. Пусть <tex>\mathcal{A}</tex> &nbsp;- подмножество индексов <tex>\{1,\dots,n\}</tex> столбцов матрицы&nbsp;<tex>X</tex>. Это подмножество задает подматрицу <center><tex>X_\mathcal{A} = [s_{j_1}\mathbf{x}_{j_1},\ldots,s_{j_{|\mathcal{A}|}}\mathbf{x}_{j_{|\mathcal{A}|}}], j\in\mathcal{A},</tex></center> где множитель&nbsp;<tex>s\in\{+1, -1\}</tex> и <tex>|\mathcal{A}|</tex>&nbsp;- мощность множества&nbsp;<tex>\mathcal{A}</tex>. Обозначим ковариационную матрицу <center><tex>\mathcal{G} = X_{\mathcal{A}}^TX_{\mathcal{A}} </tex>&nbsp;&nbsp;и&nbsp;&nbsp; <tex>A_{\mathcal{A}} = (\mathbf{1}_{\mathcal{A}}^T\mathcal{G}^{-1}_{\mathcal{A}}\mathbf{1}_{\mathcal{A}})^{-\frac{1}{2}},</tex></center> где <tex>\mathbf{1}_{\mathcal{A}}</tex> &nbsp;- вектор, состоящий из&nbsp;<tex>|\mathcal{A}|</tex> единиц. Вычислим единичный вектор <center><tex>\mathbf{u}_{\mathcal{A}} = X_{\mathcal{A}}\mathbf{w}_{\mathcal{A}}, </tex>&nbsp;&nbsp;где&nbsp;&nbsp;<tex>\mathbf{w}_{\mathcal{A}} = A_{\mathcal{A}}\mathcal{G}_{\mathcal{A}}^{-1}\mathbf{1}_{\mathcal{A}}.</tex></center> Вектор&nbsp;<tex>\mathbf{u}</tex> образует со столбцами матрицы&nbsp;<tex>X_{\mathcal{A}}</tex> одинаковые углы, меньшие <tex>\frac{\pi}{2}</tex>. Справедливы равенства <center><tex>X'_{\mathcal{A}}\mathbf{u}_{\mathcal{A}} = A_{\mathcal{A}}\mathbf{1}_{\mathcal{A}}</tex>&nbsp;&nbsp;и&nbsp;&nbsp;<tex>\|\mathbf{u}_{\mathcal{A}}\|^{2} = 1.</tex></center> == Выполнение алгоритма == Назначим начальную оценку вектора значений зависимой переменной&nbsp;<tex>\hat{\mathbf{\mu}}=\mathbf{0}</tex>. Вычислим текущую оценку&nbsp;<tex>\hat{\mathbf{\mu}}_{\mathcal{A}}</tex> и вектор корреляций <center><tex>\hat{\mathbf{c}} = X^T(\mathbf{y}-\hat{\mathbf{\mu}}_{\mathcal{A}}).</tex></center> Найдем текущий набор индексов&nbsp;<tex>\mathcal{A}</tex>, соответствующих признакам с наибольшими абсолютными значениями корреляций <center><tex>\hat C = \max_{j=1,\ldots,n}\{|\hat c_j|\} </tex>&nbsp;&nbsp;и&nbsp;&nbsp;<tex>\mathcal{A} = \{j:|\hat c_j| = \hat C\}.</tex></center> Пусть&nbsp;<tex>s_j = \text{sign}(\hat c_j)</tex> для <tex>j\in\mathcal{A}.</tex> Построим матрицы <tex>X_{\mathcal{A}}</tex>,&nbsp;<tex>A_{\mathcal{A}}</tex>. Вычислим вектор&nbsp;<tex>\mathbf{u}_{\mathcal{A}}</tex> и вектор скалярных произведений <center><tex>\mathbf{a}=X^T\mathbf{u}_{\mathcal{A}}.</tex></center> Пересчитаем значение вектора <tex>\hat{\mathbf{\mu}}_{\mathcal{A}}</tex> <center><tex>\hat{\mathbf{\mu}}_{\mathcal{A_{+}}} = \hat{\mathbf{\mu}}_{\mathcal{A}} + \hat\gamma\mathbf{u}_{\mathcal{A}},</tex></center> где <center><tex>\hat\gamma = {\min_{j\in\mathcal{A}^c}}^{+}\lbrace\frac{\hat{C}-\hat c_j}{A_{\mathcal{A}}-a_j},\frac{\hat C + \hat c_j}{A_{\mathcal{A}}+a_j}\rbrace. </tex> (*)</center> Минимум берется по всем положительным значениям аргументов для каждого&nbsp;<tex>j</tex>. Алгоритм повторяется&nbsp;<tex>n</tex> раз. == Замечание == Величина&nbsp;<tex>\gamma</tex> в формуле&nbsp;(*) интерпретируется следующим образом. Определим <center><tex>\mathbf{\mu}(\gamma) = {\mathbf{\mu}}_{\mathcal{A}}+\gamma\mathbf{u}_{\mathcal{A}}</tex></center> при условии <tex>\gamma>0</tex>. Корреляция по добавляемому&nbsp;<tex>j</tex>-му признаку равна <center><tex>c_j(\gamma)=\mathbf{x}_j^T(\mathbf{y}-\mathbf{\mu}(\gamma)) = c_{j} - \gamma a_{j}.</tex></center> Для <tex>j\in\mathcal{A}</tex> получаем <center><tex>|c_{j}(\gamma)|=C-\gamma A_{\mathcal{A}}.</tex></center> Это означает, что все рассматриваемые на данном шаге максимальные абсолютные корреляции уменьшаются на одну и ту же величину. Из предыдущих двух соотношений мы видим, что при <tex>j\in \mathcal{A}^c</tex> корреляция <tex>c_j(\gamma)</tex> принимает наибольшее значение при <center><tex>\gamma = \frac{C-c_{j}}{A_{\mathcal{A}}-a_j}.</tex></center> Аналогично, корреляция <tex>-c_j(\gamma)</tex> принимает наибольшее значение при <center><tex>\gamma = \frac{C+c_{j}}{A_{\mathcal{A}}+a_j}.</tex></center> Таким образом,&nbsp;<tex>\gamma</tex> в выражении&nbsp;(*)&nbsp;- минимальная положительная величина, при которой новый индекс&nbsp;<tex>j</tex> может быть добавлен в набор&nbsp;<tex>\mathcal{A}</tex>. Для иллюстрации работы алгоритма задумаем модель <tex>f = w_1+w_2\sqrt(x)+w_3x</tex> ([[Порождение линейных регрессионных моделей (постановка задачи)|более подробно см.]]). <source lang="matlab"> f = inline('w(1)*x.^0 + w(2)*x.^(1/2) + w(3)*x.^1', 'w','x'); % synthetic model b = [1 -2 2]'; % parameters x = [0.1:0.1:1]'; % independent variable y = f(b,x); % dependent variable </source> Пусть имеется выборка, в которой вектор-столбцы матрицы&nbsp;<tex>X</tex> <center><tex>X = \left( \begin{array}{ccccc} x^0_1 & \sqrt{x}_1 & x\sqrt{x}_1 & x_1 & x\log{x}_1 \\ \vdots& \vdots & \vdots &\vdots &\vdots \\ x^0_m & \sqrt{x}_m & x\sqrt{x}_m & x_1 & x\log{x}_m \\ \end{array} \right)</tex></center> и вектор&nbsp;<tex>\mathbf{y}=(y_1,\ldots,y_m)</tex>. <source lang="matlab"> % We use the following features to find the model we thought of g = {'x.^0', 'x.^(1/2)', 'x.^1', 'x.^(3/2)', 'x.*log(x)'}; % make the sample set; columns are independent variables X = eval([ '[' g{1} ' ' g{2} ' ' g{3} ' ' g{4} ' ' g{5} ']']); </source> Принята линейная модель <tex>\mathbf{y}=X\mathbf{\beta}</tex>. Требуется последовательно отобрать вектор-столбцы матрицы&nbsp;<tex>X</tex>, которые имеют наибольшую корреляцию с вектором остатков. Алгоритм LARS в данном примере сделает&nbsp;<tex>n=5</tex> шагов. <source lang="matlab"> [n,p] = size(X); muA = zeros(n,1); % estimation of the dependent variable beta = zeros(p,1); % estimation of parameters betaLtst = beta'; % keep parameters in a storage for i = 1:p % correlation coefficients between each feature (column of X) and vector of residuals c = X'*(y-muA); % note that columns of X are centered and normalized [C, A] = max(abs(c)); % find maximal value of correlation and corresponding index j of column in X % A = find(C == abs(c)); % Aplus = find(C==c); % never used Sj = sign(c(A)); % get sign of j-th correlation coefficient XA = X(:,A).*(ones(n,1)*Sj'); % % XA = X(:,A)*Sj; % G = XA'*XA; % norm of XA oA = ones(1,length(A)); % vector of ones AA =(oA*G^(-1)*oA')^(-0.5); % inverse matrix in the normal equation wA = AA*G^(-1)*oA'; % parameters to compute the unit bisector uA = XA*wA; % compute the unit bisector a = X'*uA; % product vector to compute new gamma if i<p % for all columns of X but the last M = [(C-c)./(AA-a);(C+c)./(AA+a)]; M(find(M<=0)) = +Inf; gamma = min(M); else gamma = C/AA; end muA = muA + gamma*uA; % make new approximation of the dependent variable beta(A) = beta(A) + gamma*wA.*Sj; % make new parameters betaLtst = [betaLtst; beta']; % store the parameters at k-th step end </source> Результатом работы алгоритма является последовательность добавляемых признаков (веса которых отличны от нуля). 0.5739 0 0 0 0 0.5739 0.0311 0 0 0 0.5739 0.0311 0 0 0 0.5739 0.0439 0 0 0 0.5739 0.0439 0.2135 0 0 [[Изображение:lars_parameters.png|frame|На графике показано изменение вектора параметров <tex>\mathbf{\beta}</tex> по шагам LARS. По оси абсцисс отложена сумма параметров, по оси ординат - их значения. Согласно исходной модели, только первые три параметра отличны от нуля.]] [[Изображение:lars_model.png|frame|Ось абсцисс - свободная переменная, ось ординат - зависимая. Точками показаны исходные данные, соответствующие задуманной модели. Красная линия - модель LARS с параметрами <tex>\mathbf{\beta}</tex>, полученными с помощью LARS. Красная линия - модель для параметров, выбранных LARS и настроеных с помощью [[метод наименьших квадратов|метода наименьших квадратов]].]] == Литература == * Tibshirani&nbsp;R. Regression shrinkage and Selection via the Lasso.&nbsp;// Journal of the Royal Statistical Society.Series B(Metodological). 1996&nbsp; Vol.&nbsp;32,&nbsp;\No&nbsp;1, p.267-288. * Efron&nbsp;B., Hastie&nbsp;T., Johnstone&nbsp;J., Tibshirani&nbsp;R. Least Angle Regression.&nbsp;// The Annals of Statistics, 2004. Vol.&nbsp;32, \No&nbsp;2, p.&nbsp;407-499. == См. также == * [http://strijov.com/sources/demo_lars.php Полный текст данного примера] * [[Регрессионный анализ]] * [[Регрессионная модель]] * [[Линейная регрессия (пример)]] * [[Порождение линейных регрессионных моделей (постановка задачи)]] * [[Лассо]] [[Категория:Регрессионный анализ]]

Возврат к странице Метод наименьших углов (пример).