Ускорение параметрического синтеза линейной регрессии на основе редукционного оценивания коэффициентов

УДК 681.322:517.444

,

Одесский национальный политехнический университет

Ускорение параметрического синтеза линейной регрессии на основе редукционного оценивания коэффициентов

Приведен анализ двух методов ускоренного вычисления коэффициен-тов линейной регрессии при изменении состава учитываемых фак-торов. Рассмотрены сходство и различия предлагаемого редукцион-ного подхода и метода рекуррентного оценивания с использованием ускоренной корректировки обратной матрицы нормальных уравнений на базе метода окаймления.

Ключевые слова: линейная регрессия, включение и исключение регрес-соров, расчет обратной матрицы системы нормальных уравнений, метод окаймления, рекуррентное оценивание регрессионных коэффи-циентов.

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

На сегодняшний день известно достаточно много работ, посвященных уско-ренному вычислению коэффициентов линейной регрессии при изменении состава учитываемых факторов [2-4]. Одним из наиболее быстрых методов на сегодня яв-

© ,

ляется алгоритм рекуррентного оценивания коэффициентов с использованием метода окаймления для корректировки обратной матрицы, изложенный в [1] на стр. 78–80. Однако, на наш взгляд, данный метод не исчерпывает всех ресурсов ускорения вычислений, заложенных в идее рекуррентного оценивания коэффициентов. В связи с этим, авторами предложен редукционный метод оценки коэффициентов регрессии [5], являющийся оригинальным развитием идеи рекуррентного оценивания.

Темой настоящего исследования является сравнение предложенного редукционного подхода и метода рекуррентного вычисления коэффициентов регрессии с использованием метода окаймления для корректировки обратной матрицы. Цель сравнения состоит в выявлении сходства и различия методов, элементов новизны редукционного подхода, сравнении количественных характеристик, таких как число операций, объем хранимых промежуточных данных.

Приведем основные этапы базового метода рекуррентного оценивания коэффициентов.

Пусть на каком-то этапе работы алгоритма определены оценки параметров модели, содержащей s аргументов: . Обозначим

(1)

уравнение измерений или систему N условных уравнений для частной модели, содержащей s неизвестных коэффициентов (из полного числа n).

Расширенную матрицу нормальных уравнений, полученную по МНК для s аргументов, обозначим так

, (2)

причем здесь индекс одновременно соответствует размерности квадратной матрицы и вектора . Если каким-то образом вычислена ,то оценка коэффициентов имеет вид

. (3)

При добавлении одного аргумента матрица нормальной системы принимает вид (с учетом ее симметрии)

, (4)

где — вектор; — скаляры, значения которых определяются вектором измерений (s + 1)-го аргумента.

Структура оценки новых значений коэффициентов

(5)

предоставляет возможность выразить матрицу и соответственно новую оценку через уже известную и элементы «окаймления» .

Действительно, обозначая

(6)

и решая уравнение (или применяя известные формулы обращения блочных матриц), получаем:

; (7)

.

Формулы (7), по существу, дают алгоритм вычисления . Однако записы-вать эту матрицу в явном виде не требуется, поскольку, как следует из (5)–(7),

. (8)

Таким образом, при добавлении к модели одного аргумента новая оценка вектора коэффициентов явно выражается через уже вычисленную (с учетом (3), (8))

. (9)

Рассмотрим теперь кратко суть предлагаемого редукционного подхода [5]. В его основе также лежат соотношения, аналогичные (8) и (9). Так, если подставить выражение (7) для в формулу (8) для , то выражения для новых коэффи-циентов регрессии (9) будут выражены только через старые значения коэффициентов и вспомогательные коэффициенты . В результате получим соотношения, на которых базируется также и редукционный подход:

; (10)

; " j = [1, s], (11)

где — коэффициенты новой модели после включения фактора xs+1; — коэффициенты исходной модели до включения фактора xs+1; ,"j = [1, s] — вспомогательные коэффициенты, аналогичные коэффициентам c в методе окаймления и определяющиеся выражением, соответствующим (7):

, (12)

где — добавочный s + 1 столбец матрицы H размерностью s элементов, соответствующий новому введенному фактору xs+1.

В использовании аналогичных базовых итеративных соотношений и заключается родственность редукционного подхода и рекуррентного алгоритма с использованием метода окаймления.

Различие же между методами кроется в способе вычисления вектора вспомогательных коэффициентов . В рекуррентном методе данный вектор не несет особой смысловой нагрузки, кроме сокращения объема вычислений за счет «вынесения за скобки» общего для нескольких формул фрагмента , вычисляемого в соответствии с (7) через элементы обратной матрицы. При этом на каждом шаге рекуррентного алгоритма, при включении нового регрессора, в явном виде вычисляется обратная матрица с использованием соотношений метода окаймления (7).

Суть же редукционного метода, выраженная в терминах рекуррентных соотношений (6)–(9), заключается в том, что вычисление как вспомогательного вектора , так и новых коэффициентов регрессии осуществляется без привлечения элементов обратных матриц и основывается на использовании последовательности вспомогательных векторов cs, cs–1, …, c1 для предыдущих моделей меньшей размерности. Можно сказать, что редукционный метод основывается на использовании «физического смысла» вспомогательных коэффициентов . В [5] показано, что данный вектор представляет собой коэффициенты линейной регрессии, зависимости, выражающей (редуцирующей) новый вводимый регрессор как линейную функцию предыдущих факторов x1, x2, …, xs. Вместе с тем, поскольку являются подобно коэффициентами линейной регрессии, для них, в свою очередь, также справедливы рекуррентные формулы (8) и (9), выражающие через два вектора регрессионных коэффициентов, размерностью на 1 меньше . Среди этих двух вспомогательных векторов будет вектор cs, выражающий xs через x1, x2, …, xs–1, а также вектор линейных коэффициентов зависимости xs+1 от x1, x2, …, xs–1. Для вычисления второго вектора коэффициентов снова могут быть использованы рекуррентные соотношения, а первый вектор cs имеется в наличии и сохранен в специальной матрице редукционных коэффициентов при включении предыдущего фактора xs.

Формальным выражением описанной идеи являются рекуррентные редукционные соотношения. В общем случае, на некотором i-ом шаге, редукционные коэффициенты модели Xs+1 =F(X1, …, Xi) могут быть вычислены в соответствии со следующими выражениями:

; "i = [1, s], (13)

а коэффициенты регрессии при факторах X1, …, Xi–1 соответственно выразятся:

; " i = [1, s]; j = [1, i – 1], (14)

где cs+1,i — вектор размерностью i коэффициентов текущей декомпозируемой модели Xs+1= F(X1, …, Xi), "i = [1, s]; cs+1, i–1 — вектор размерностью i – 1 коэффициентов модели Xs+1= F(X1, …, Xi–1); ci,i–1 — вектор размерностью i – 1 коэффициентов модели Xi = F(X1, …, Xi–1).

Выражения (13) и (14) позволяют последовательно выразить исходную полную задачу вычисления коэффициентов линейной зависимости xs+1 от факторов x1, x2, …, xs через ряд подзадач вычисления коэффициентов моделей xs+1 = f(x1, x2, …, xs–1), xs+1 = f(x1, x2, …, xs–2), …, xs+1 = f(x1), используя при этом редукционную матрицу С, строками которой являются коэффициенты линейных зависимостей xs = f(x1, x2, …, xs–1), xs+1 = f(x1, x2, …, xs-2), …, x2 = f(x1):

		1	2	3	…	m – 1
	1						- x2 = f(x1)
	2						- x3 = f(x1, x2)
С =	3						- x4 = f(x1, x2, x3)
	…
	m – 1				…		- xm = f(x1, …, xm–1)

После включения очередного регрессора xs+1 коэффициенты редукционной зависимости xs+1 = f(x1, x2, …, xs) образуют новую строку матрицы C и будут в дальнейшем использоваться при включении последующих регрессоров xs+2, xs+3 и т. д.

Описанная схема декомпозиции исходной задачи расчета новых коэффициентов регрессии графически представлена на рисунке, где широкими стрелками показано направление разворачивания процесса декомпозиции моделей, а тонкие соответствуют реальной последовательности вычислений.

Процесс редукционной декомпозиции задачи вычисления

коэффициентов модели Y = F(X1, X2, ..., Xm+1) при включении дополнительного фактора Xm+1.

На базе итеративных редукционных соотношений (13) и (14) разработаны конкретные алгоритмы, реализующие описанную схему вычисления вспомогательных редукционных коэффициентов и искомых коэффициентов регрессии при вк-лючении в модель дополнительного регрессора.

Для рекуррентного метода с использованием обратной матрицы подсчет количества операций корректировки модели при включении дополнительного регрессора дает оценку 1.5s2 + 3.5s выполняемых операторных блока алгоритма, где s – число факторов до введения дополнительного регрессора xs+1. Суммарная трудоемкость вычисления новых коэффициентов регрессии в редукционном методе составляет s2 + 3s выполняемых операторных блока, что более, чем в 1,5 раза меньше, по сравнению с рекуррентным алгоритмом при использовании метода окаймления для корректировки обратной матрицы.

Приведенная оценка объема вычислений достаточно груба и не учитывает разницы по трудоемкости между операциями сложения, умножения и деления. Не учитывалось также общее количество различных циклов, организуемых по ходу вычислений, хотя очевидно, что два операторных блока, будучи реализованными в одном цикле будут выполняться быстрее чем в двух отдельных циклах, поскольку при организации дополнительного цикла появляются накладные расходы на проверку значения параметра цикла и инкремент его значения. Однако приведенные оценки, по всей видимости, позволяют верно оценить порядок величин трудоемкости анализируемых методов. Меньшую трудоемкость редукционного метода можно объяснить за счет ухода от вычисления элементов обратной матрицы и непосредственного использования промежуточных коэффициентов cs, cs–1, …, c1 предыдущих моделей для вычисления аналогичных коэффициентов cs+1 текущей модели.

Выводы

Итак, предложенный редукционный алгоритм, используя, по сравнению с методом окаймления [4], более специфичные и агрегированные данные, позволяет приблизительно на 50 % ускорить вычислением параметров линейно-регрессион-ной модели при включении в нее дополнительного регрессора.

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

Кроме того, в редукционной модели появляется возможность быстрого вычисления коэффициентов множественной корреляции любого из регрессоров относительно прочих регрессоров модели [5].

1. , Помехоустойчивость моделирования. — К.: Наук. думка, 1985. — 216 с.

2. Efroimson M. A. Multiple regression analysis // Mathematical Methods of Digital Computers. —N. Y.: Ralston A. and Wilf H. S., 1960. — Р. 191-203.

3. Дж. Себер. Линейный регрессионный анализ. — М.: Мир, 1980. — 456 с.

4. Обращение матриц и решение систем линейных и нелинейных уравнений методом окаймления // ЖВММФ. — 1979. — Т. 19. — № 4. — С. 803-810.

5. , Редукционный метод построения регрессии в условиях изменяющегося состава факторов // Труды Одесского политехнического университета. — 2001. — Вып. 2. — С. 105-110.

Поступила в редакцию 11.07.2002