Метод еліпсоїдів для знаходження параметрів лінійної регресії

Описано задачу визначення параметрів лінійної регресії у формі задачі мінімізації негладкої функції, що являє собою Lp-норму вектора-нев’язки системи лінійних рівнянь. Наведено загальна схема алгоритма методу еліпсоїдів для мінімізації цієї функції при довільному значенні параметра p ≥ 1. Описано сп...

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Кібернетика та комп’ютерні технології
Дата:	2020
Автор:	Стовба, В.О.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2020
Теми:	Методи оптимізації та екстремальні задачі
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/173148
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Метод еліпсоїдів для знаходження параметрів лінійної регресії / В.О. Стовба // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 3. — С. 14-24. — Бібліогр.: 10 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-173148
record_format	dspace
spelling	Стовба, В.О. 2020-11-23T19:19:06Z 2020-11-23T19:19:06Z 2020 Метод еліпсоїдів для знаходження параметрів лінійної регресії / В.О. Стовба // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 3. — С. 14-24. — Бібліогр.: 10 назв. — укр. 2707-4501 DOI:10.34229/2707-451X.20.3.2 https://nasplib.isofts.kiev.ua/handle/123456789/173148 519.85 Описано задачу визначення параметрів лінійної регресії у формі задачі мінімізації негладкої функції, що являє собою Lp-норму вектора-нев’язки системи лінійних рівнянь. Наведено загальна схема алгоритма методу еліпсоїдів для мінімізації цієї функції при довільному значенні параметра p ≥ 1. Описано спосіб запису задачі апроксимації спостережень квадратичною функцією як задачі визначення параметрів лінійної регресії. Проаналізовано результати обчислювальних експериментів для двох прикладів апроксимації спостережень лінійною та квадратичною функціями з використанням алгоритму методу еліпсоїдів. Цель работы. Расширить алгоритм на базе метода эллипсоидов для решения задачи определения параметров линейной регрессии для произвольных значений параметра p ≥ 2 так, чтобы при больших значениях p решение задачи совпадало с решением, полученным минимаксным методом, который соответствует значению p= ∞. Описать формулировку задачи аппроксимации наблюдений квадратичной функцией как задачи определения параметров линейной регрессии. Проанализировать результаты работы алгоритма для большого количества наблюдений и выбросов. Сравнить результаты работы минимаксного метода и метода эллипсоидов для задачи определения параметров линейной регрессии при больших значениях параметра p. The purpose of the paper is to extend the algorithm based on the ellipsoid method for a linear regression parameters determination problem with an arbitrary value of parameter p ≥ 2 so that under big values of p the solution of the problem equals minimax method solution, which corresponds to p= ∞ case. To describe the formulation of observation approximation problem with quadratic function as linear regression parameters determination problem. To analyze algorithm work results for great number of observations and outliers. To compare the minimax method and the ellipsoid method algorithm work results for linear regression parameters determination problem with big values of parameter p. uk Інститут кібернетики ім. В.М. Глушкова НАН України Кібернетика та комп’ютерні технології Методи оптимізації та екстремальні задачі Метод еліпсоїдів для знаходження параметрів лінійної регресії Метод эллипсоидов для нахождения параметров линейной регрессии Ellipsoid Method for Linear Regression Parameters Determination Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Метод еліпсоїдів для знаходження параметрів лінійної регресії
spellingShingle	Метод еліпсоїдів для знаходження параметрів лінійної регресії Стовба, В.О. Методи оптимізації та екстремальні задачі
title_short	Метод еліпсоїдів для знаходження параметрів лінійної регресії
title_full	Метод еліпсоїдів для знаходження параметрів лінійної регресії
title_fullStr	Метод еліпсоїдів для знаходження параметрів лінійної регресії
title_full_unstemmed	Метод еліпсоїдів для знаходження параметрів лінійної регресії
title_sort	метод еліпсоїдів для знаходження параметрів лінійної регресії
author	Стовба, В.О.
author_facet	Стовба, В.О.
topic	Методи оптимізації та екстремальні задачі
topic_facet	Методи оптимізації та екстремальні задачі
publishDate	2020
language	Ukrainian
container_title	Кібернетика та комп’ютерні технології
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Метод эллипсоидов для нахождения параметров линейной регрессии Ellipsoid Method for Linear Regression Parameters Determination
description	Описано задачу визначення параметрів лінійної регресії у формі задачі мінімізації негладкої функції, що являє собою Lp-норму вектора-нев’язки системи лінійних рівнянь. Наведено загальна схема алгоритма методу еліпсоїдів для мінімізації цієї функції при довільному значенні параметра p ≥ 1. Описано спосіб запису задачі апроксимації спостережень квадратичною функцією як задачі визначення параметрів лінійної регресії. Проаналізовано результати обчислювальних експериментів для двох прикладів апроксимації спостережень лінійною та квадратичною функціями з використанням алгоритму методу еліпсоїдів. Цель работы. Расширить алгоритм на базе метода эллипсоидов для решения задачи определения параметров линейной регрессии для произвольных значений параметра p ≥ 2 так, чтобы при больших значениях p решение задачи совпадало с решением, полученным минимаксным методом, который соответствует значению p= ∞. Описать формулировку задачи аппроксимации наблюдений квадратичной функцией как задачи определения параметров линейной регрессии. Проанализировать результаты работы алгоритма для большого количества наблюдений и выбросов. Сравнить результаты работы минимаксного метода и метода эллипсоидов для задачи определения параметров линейной регрессии при больших значениях параметра p. The purpose of the paper is to extend the algorithm based on the ellipsoid method for a linear regression parameters determination problem with an arbitrary value of parameter p ≥ 2 so that under big values of p the solution of the problem equals minimax method solution, which corresponds to p= ∞ case. To describe the formulation of observation approximation problem with quadratic function as linear regression parameters determination problem. To analyze algorithm work results for great number of observations and outliers. To compare the minimax method and the ellipsoid method algorithm work results for linear regression parameters determination problem with big values of parameter p.
issn	2707-4501
url	https://nasplib.isofts.kiev.ua/handle/123456789/173148
citation_txt	Метод еліпсоїдів для знаходження параметрів лінійної регресії / В.О. Стовба // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 3. — С. 14-24. — Бібліогр.: 10 назв. — укр.
work_keys_str_mv	AT stovbavo metodelípsoídívdlâznahodžennâparametrívlíníinoíregresíí AT stovbavo metodéllipsoidovdlânahoždeniâparametrovlineinoiregressii AT stovbavo ellipsoidmethodforlinearregressionparametersdetermination
first_indexed	2025-11-25T22:47:39Z
last_indexed	2025-11-25T22:47:39Z
_version_	1850573896730804224
fulltext	МЕТОДИ ОПТИМІЗАЦІЇ ТА ЕКСТРЕМАЛЬНІ ЗАДАЧІ 14 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3 КІБЕРНЕТИКА та КОМП'ЮТЕРНІ ТЕХНОЛОГІЇ Описано задачу визначення параметрів ліній- ної регресії у формі задачі мінімізації неглад- кої функції, що являє собою pL -норму век- тора-нев’язки системи лінійних рівнянь. На- ведено загальна схема алгоритма методу еліпсоїдів для мінімізації цієї функції при до- вільному значенні параметра 1p  . Описано спосіб запису задачі апроксимації спостере- жень квадратичною функцією як задачі ви- значення параметрів лінійної регресії. Про- аналізовано результати обчислювальних екс- периментів для двох прикладів апроксимації спостережень лінійною та квадратичною функціями з використанням алгоритму методу еліпсоїдів. Ключові слова: метод еліпсоїдів, лінійна ре- гресія, аномальні спостереження.  В.О. Стовба, 2020 УДК 519.85 DOI:10.34229/2707-451X.20.3.2 В.О. СТОВБА МЕТОД ЕЛІПСОЇДІВ ДЛЯ ЗНАХОДЖЕННЯ ПАРАМЕТРІВ ЛІНІЙНОЇ РЕГРЕСІЇ Вступ. Лінійна регресія – один з найпоширеніших ін- струментів регресійного аналізу в багатьох областях науки. Вона використовується для аналізу експериме- нтальних даних в економіці, психології, соціології, фізиці, хімії, геології тощо. Наприклад, в економіці на її основі будуються багатофакторні моделі продуктив- ності праці та функцій попиту, виробничих функцій та економіко-статистичних моделей [1]. Варто зазначити, що лінійна регресія найчастіше використовується та є найбільш досконало вивченою в економетриці. З іншого боку, ця модель є типовим представником алгоритмів машинного навчання, під- розділу штучного інтелекту. Як і задача класифікації, вона відноситься до класу задач навчання з учителем, де за заданим набором даних про об’єкт, що спостеріга- ється, необхідно спрогнозувати певну цільову змінну. Задачу визначення параметрів лінійної регресії можна сформулювати як задачу мінімізації негладкої функції. В основі такої оптимізаційної задачі стоїть спосіб знаходження вектора невідомих, який мінімізує pL -норму вектора-нев’язки системи лінійних рівнянь, що задається за допомогою матриці плану регресії. Для її розв’язання можна використовувати методи мінімізації негладких функцій, зокрема, субградієнтні методи, такі як метод еліпсоїдів, r-алгоритми тощо. В статті розглянемо задачу мінімізації негладкої функції для визначення параметрів лінійної регресії, та її розв’язання за допомогою методу еліпсоїдів при довільному значенні параметра 1p  . Проаналізуємо результати обчислювальних експериментів для двох прикладів апроксимації спостережень лінійною та квадратичною функціями. Наведемо також спосіб за- пису задачі апроксимації спостережень квадратичною функцією як задачі визначення параметрів лінійної регресії. 1. Постановка задачі. Розглянемо регресійну модель  ,y f x b   , (1) де  ,i ix y , 1,i n – вибірка спостережень, причому m ix  , iy  . Також mb – вектор параметрів https://doi.org/10.34229/2707-451X.20.3.2 МЕТОД ЕЛІПСОЇДІВ ДЛЯ ЗНАХОДЖЕННЯ ПАРАМЕТРІВ ЛІНІЙНОЇ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 15 (коефіцієнтів) регресії, n – вектор похибок спостережень (математичне сподівання   0iE   , 1,i n ). Якщо функція  ,f x b є лінійною, тобто   1 1, ... m mf x b b x b x   , (2) модель (1) називається лінійною регресією. Тут n jx  , 1,j m – регресори або фактори моделі. Необхідно знайти такий вектор параметрів b , при якому вектор похибок  ,y f x b     1,..., T n   буде мінімальним. Якщо в моделі наявний лише один фактор (без урахування константи), говорять про парну регресію, причому модель (1) набуває вигляду 0 1 1 , 1,i i iy b b x i n     , (3) де 1ix – значення першого (і єдиного) фактору в i -му спостереженні. Цю модель можна представи- ти також у матричному вигляді: y Xb  , (4) де  1,..., T ny y y ,  0 1, , T b b b X – n m -матриця факторів, яка має вигляд 11 12 1 1 1 1 n x x X x             . Задачу (3) можна представити як задачу знаходження «найкращої» pL -норми вектора-нев’язки  для системи (4) [2 – 4]. Їй відповідає задача мінімізації негладкої функції   1 1 p n p p ip p i f b Xb y               , (5) тобто знаходження  * arg min mp p b b f b   . (6) Тут p – скалярний параметр, який при 1p  забезпечує опуклість функції  pf b . Задача (5), (6) завжди має розв’язок, а якщо n m та матриця X має повний ранг – цей розв’язок єдиний. В загальному випадку розв’язок не обов’язково єдиний і точка * pb належить множині оптимальних розв’язків, яким відповідає мінімальне значення функції * pf в задачі (5), (6). Для розв’язання цієї задачі доцільно використовувати методи мінімізації негладких опуклих функцій і такі спроби неодноразово виконувались. Наприклад, в роботі [4] запропоновано доволі загальний підхід для оцінки невідомих параметрів у класичній лінійній моделі, що базується на модифікації r-алгоритму Шора – Журбенко. В роботі [5] на основі методу еліпсоїдів [6] розроблено алгоритми та їх програмні реалізації для знаходження точки мінімуму  pf  при двосторонніх обмеженнях на змінні. 2. Мінімізація функції (5) при великих значеннях параметра p. Задачу (5), (6) можна розв’язувати при різних значеннях параметра .p Наприклад, випадок 1p  відповідає методу най- менших модулів (МНМ), випадок 2p  – методу найменших квадратів (МНК), а випадок p  – В.О. СТОВБА 16 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3 мінімаксному методу Чебишева. Кожен з них дає свій розв’язок, який може бути більш якісним та стійким залежно від типу розподілу випадкової величини, що характеризує похибку результатів спостережень. В роботі [7] задачу (5), (6) розв’язано з використанням методу еліпсоїдів для зна- чень параметра 1 2p  . При довільних значеннях параметра p ця задача є загальною задачею безумовної мінімізації опуклої негладкої функції  pF b . Для її розв’язання можна використовува- ти методи мінімізації опуклих функцій, наприклад, метод еліпсоїдів або r-алгоритми. Їх викорис- тання потребує обчислення значення функції  pf b та її субградієнта  fg b в точці b ; перше можна обчислити за формулою (5), друге – за формулою     11 1 sgn n pp T f i i i i ip i g b Xb y x b y x b y x        . (7) При великих значеннях параметра p розрахунок цих величин є доволі трудомісткою задачею. В такому випадку мінімізація функції (5) еквівалентна мінімізації функції   1, maxp i i i n f b x b y    , що відповідає випадку p  . Для спрощення обчислення та його коректності вираз (5) для обчислення значення функції пропонується змінити таким чином:   1/1/ 1/ 1/ 1 1 1 1 pp p p pn n n n p p pmax max i p i i i max pppmaxi i i i maxmax f b                                                1/ 1/ 1 1 p ppn n pi max max i max p maxi i z z                       , де 1, maxmax i i n    , 1i i max z     , 1, .i n (8) Формула (7) для обчислення субградієнта функції модифікується так:       1 11 1 1 1 sgn sgn n n p pp pT T f i i i i i i i ip p i i g b Xb y x b y x b y x x                      1 1 1 11 1 1 1 1 sgn sgn p n n p p pp pmax T T i i i max i i ip pp i imax x z x                            11 1/ 1 1 1 1 1 sgn sgn pp p n n n p p pp T T i i i i max i i i max i i i z x z x                                        1 1/ 1 11 1 1 1 sgn sgn p p pn n n p ppT Ti i i i i i ip maxi i i z x z z x                         , (9) де ix – вектор-рядок матриці X з номером 1,i n . Якщо 0max  всі перетворення є коректними. Умова 0max  коректно опрацьовується в про- грамній реалізації методу за допомогою перевірки відповідної умови. Ідея перетворення виразів (5) і (7) така. При великих значеннях параметра p обчислення pL -норми вектора  може призвести до накопичення обчислювальної похибки при виконанні операцій піднесення до степеню та додавання великих чисел. В модифікованих формулах (8) і (9) МЕТОД ЕЛІПСОЇДІВ ДЛЯ ЗНАХОДЖЕННЯ ПАРАМЕТРІВ ЛІНІЙНОЇ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 17 такі операції проводяться над елементами вектора iz , які або рівні одиниці (їм відповідають максимальні елементи вектора i ), або менші одиниці. Якщо 1iz  вищенаведені операції не змі- нюють його; якщо ж 1iz  , то при великих значеннях параметра p таке значення прямує до нуля та інтерпретується як нуль після досягнення певної границі. Таким чином операції виконуються коректно, а значення функції та її субградієнта обчислюються досить точно навіть при великих значеннях параметра .p 3. Алгоритм методу еліпсоїдів. Ініціалізація. Вибираємо стартові точку 0 ,mx  радіус 0r  та m m -матрицю 0B , яку покладемо рівною одиничній матриці mI . Перейдемо до першої ітерації зі значеннями 0x , 0r та 0B . Нехай на k -й ітерації отримали значення kx , kr та kB . Для переходу на ( 1k  )-у ітерацію виконаємо таку послідовність кроків. Крок 1. Обчислимо  p kf x . Якщо   0p kf x  , тоді STOP: k k та p kx x . Інакше обчисли- мо  p kg x . Якщо  p kf x   та  T k p k k fB g x r   , тоді STOP: k k та p kx x . Інакше пере- ходимо до кроку 2. Крок 2. Покладемо     T k p k k T k p k B g x B g x   . Крок 3. Обчислимо наступну точку 1k k k k kx x h B    , де 1 1 k kh r n   . Крок 4. Обчислимо  1 1 1 1 T k k k k k n B B B n            та 1 2 1 k k n r r n    . Крок 5. Переходимо до ( 1k  )-ї ітерації зі значеннями 1kx  , 1kr  та 1kB  . Теорема [8]. Послідовність точок   * 0 k k k x  задовольняє нерівності  1 * , 0,k k p kB x x r k k    . На кожній ітерації 0k  величина зменшення об’єму еліпсоїда kE   1:n k k kx B x x r    , який локалізує px , є сталою і рівною     1 2 1 1 exp 1 1 21 n k k vol E n n q vol E n nn                   . 4. Приклад 1: лінійна функція. В роботах [3, 7, 9] наводився приклад апроксимації набору з 6 спостережень, що містив аномальне, лінійною функцією. Така задача є прикладом задачі визна- чення параметрів лінійної регресії для функції однієї змінної. В роботі [3] показано, що перевагу варто віддавати методу найменших модулів (МНМ), адже він ігнорує аномальне спостереження і точно відновлює лінійну функцію. Для визначення стійкості класичних методів, що відповідають значенням 1,2,p   , розглянемо аналогічний приклад з більшою кількістю спостережень та ви- щим відсотком аномалій і проведемо серію експериментів з ним. В.О. СТОВБА 18 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3 Розглянемо набір спостережень  ,i ix y , де 1i ix y i   , 1,20i  , які необхідно апроксимувати лінійною функцією y cx d  , де c та d – невідомі. Для імітації 5 % аномальних спостережень змінимо перше спостереження таким чином:    1 1, 0,19x y  . Для досягнення 10 % аномалій окрім першого спостереження змінимо додатково друге:    2 2, 1,19x y  , для 15 % – третє:    3 3, 2,19x y  . Таким чином утворилась група аномалій ліворуч. Для побудови правосторонньої групи аномалій змінимо такі спостереження:    20 20, 19,0x y  ,    19 19, 18,0x y  ,    18 18, 17,0x y  . Додаючи по одній аномалії, отримаємо 5, 10 та 15 % викидів відповідно. Для апроксимації збурених спостережень використаємо алгоритм методу еліпсоїдів зі значеннями параметра 1,2,p   . Результати роботи алгоритму для збурених спостережень ліворуч наведено в табл. 1, праворуч – в табл. 2. ТАБЛИЦЯ 1. Апроксимація збурених ліворуч спостережень  ,i ix y лінійною функцією за допомогою алгоритму методу еліпсоїдів при різних кількостях аномалій та значеннях параметра p Відсоток аномалій p c d  * ,f c d 5 % 1 1.0000 0.0000 19.000 2 0.7285 3.5285 17.145  0.0000 3.0000 16.000 10 % 1 1.0000 0.0000 37.000 2 0.4985 6.6142 21.196  0.0000 3.0000 16.000 15 % 1 1.0000 0.0000 54.000 2 0.3067 9.2857 22.552  0.0000 3.0000 16.000 ТАБЛИЦЯ 2. Апроксимація збурених праворуч спостережень  ,i ix y лінійною функцією за допомогою алгоритму методу еліпсоїдів при різних кількостях аномалій та значеннях параметра p Відсоток аномалій p c d   ,f c d 5 % 1 1.0000 – 7.5265e – 15 19.000 2 0.72857 1.6286 17.145  5.8453e – 14 9.0000 9.0000 10 % 1 1.0000 3.3573e – 15 37.000 2 0.4985 2.9143 21.197  5.5649e – 14 8.5000 8.500 15 % 1 1.0000 2.6091e – 14 54.000 2 0.3067 3.8857 22.553  6.0668e – 14 8.0000 8.0000 МЕТОД ЕЛІПСОЇДІВ ДЛЯ ЗНАХОДЖЕННЯ ПАРАМЕТРІВ ЛІНІЙНОЇ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 19 У першій колонці табл. 1 і 2 наведено процентне відношення аномалій до загального числа спостережень, у колонці 2 – значення параметра ,p в колонках 3–5 – знайдені невідомі параметри та значення функції для них. Як бачимо, метод найменших модулів ( 1)p  точно відновлює ліній- ну функцію при будь-якому відсотку аномалій: параметр c рівний одиниці, а d рівний нулю при аномаліях ліворуч та прямує до нуля при аномаліях праворуч, що відповідає функції y x . Метод найменших квадратів ( 2)p  відхиляється від оптимальної лінійної функції у бік групи аномалій, причому при збільшенні відсотка викидів це відхилення росте. Мінімаксний метод ( )p   апрок- симує спостереження майже горизонтальною лінією, y -компонента якої залишається сталою при зростанні проценту аномалій ліворуч і змінюється, якщо аномалії розташовані праворуч. Таким чином отримані результати демонструють стійкість методу найменших модулів до появи аномалій різного характеру, яка не спостерігається при використанні МНК або мінімаксного методу. Оскільки запропонований алгоритм дозволяє розв’язувати вихідну задачу для довільного зна- чення параметра ,p розглянемо результати його роботи для цього ж прикладу з правосторонньою групою аномалій об’ємом 15 %. Отримані результати порівняємо з результатами роботи мінімакс- ного методу ( ),p   в якому необхідно мінімізувати функцію максимуму   1, max i i i n f b x b y    . (10) Результати тестувань наведено в табл. 3. ТАБЛИЦЯ 3. Апроксимація збурених праворуч спостережень  ,i ix y лінійною функцією за допомогою алгоритму методу еліпсоїдів при великих значеннях параметра p p itn pc * pd  * ,p p pf c d 10 112 4.4854e – 02 6.8507 9.3126 210 120 4.2751e – 03 7.8780 8.1090 310 130 4.2764e – 04 7.9878 8.0109 410 141 4.2763e – 05 7.9988 8.0011 510 151 4.2766e – 06 7.9999 8.0001 610 150 4.2789e – 07 8.0000 8.0000  225 6.0668e – 14 8.0000 8.0000 З табл. 3 видно, що при зростанні p значення параметрів pc та * pd прямують до значень 6.0668e-14 та 8.0000 відповідно. Така поведінка означає, що апроксимуюча пряма все більше наближається до горизонтальної прямої, що відповідає мінімаксному методу Чебишева та випадку p  . Отже, обчислення за допомогою формул (8) та (9) виконуються коректно. 5. Приклад 2: квадратична функція. Цей приклад розглядався в роботі [3] та має таку поста- новку. Наявні 28 спостережень  ,i iu f , 4 iu  , if  , взятих з анкети опитування [10], які необхідно «найкращим чином» наблизити квадратичною функцією   T TQ u u Au b u c   , що визначається такими параметрами: симетричною 4 4 -матрицею ,A вектором 4b та скаляром c . Як аргумент функція  Q u приймає вектор 4u . Цю задачу можна сформулювати як за- дачу мінімізації негладкої функції: знайти В.О. СТОВБА 20 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3    * * * , , , , arg min , ,p p p p A b c A b c F A b c , (11) де     1 1 28 28 1 1 , , p p pp T T p i i i i i i i i F A b c f Q u f u Au b u c                         . (12) Отже, необхідно знайти трійку параметрів * * , ,p p pA b c , що визначають квадратичну функцію     * * * T T p p p pQ u u A u b u c   та мінімізують функцію  , ,pF A b c . Оскільки матриця A є симетрич- ною, загальна кількість параметрів функції  Q u рівна  4 4 1 4 1 15 2 N      , серед яких 10 параметрів задають компоненти матриці A , 4 параметри – компоненти вектора b та 1 параметр задає скаляр c . Задача (5), (6) полягає у знаходженні «найкращої» pL -норми вектора-нев’язки  для системи (4), яка задається матрицею ,X що містить першу компоненту спостережень  ,i ix y , та вектором параметрів .b Якщо 15 невідомих параметрів функції  Q u розмістити у векторі розмірності 15, а також спеціальним чином побудувати матрицю ,X задачу (11), (12) можна переформулювати в термінах задачі (5), (6): знайти 15 * arg minp p X f      . (13) Тут 28f  – друга компонента спостережень  ,i iu f . Вектор параметрів 15 має таку структуру:    11 1,..., ,...,nn ij n i j a a a b b c           , де 11,..., nna a та ,ija i j – діагональні та наддіагональні елементи матриці A , 1,..., nb b – компоненти вектора b , c – невідомий скаляр. Матриця X розмірності 28 15 – блочна матриця та має такий вигляд: 2X U W U e    . Тут   28 1i i U u   – матриця розмірності 28 4 , що складається з векторів-рядків iu – першої компо- ненти спостережень  ,i iu f ; 2U – це матриця ,U кожен елемент якої піднесений до квадрату. Матриця 28 1 2 k l i i k l i i W u u               побудована таким чином: її i -й рядок є набором впорядкованих попарних подвійних добутків компонент вектора ,iu причому ,k l 1 3,k  2 4l  . Нарешті e – одиничний вектор-стовпчик з 28 . Для розв’язання задачі (13) скористаємось алгоритмом методу еліпсоїдів. Вхідними парамет- рами є початкова точка  0 0,...,0 , T x  радіус локалізації 1r  , точність 310f   та значення параметра 1, 1.3, 1.6, 2, 5p  . В табл. 4 наведені відхилення  * i p if Q u для всіх 1,28i  при різних значеннях ,p а також всі 28 спостережень  ,i iu f з анкети опитування. МЕТОД ЕЛІПСОЇДІВ ДЛЯ ЗНАХОДЖЕННЯ ПАРАМЕТРІВ ЛІНІЙНОЇ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 21 ТАБЛИЦЯ 4. Спостереження  ,i iu f та відхилення  * i p if Q u для значень 1,1.3,1.6, 2, 5p  i iu if  * i p if Q u 1p  1.3p  1.6p  2p  5p  1 (2.0, 8.5, 2.5, 4.7) 0.5 0.000 0.000 0.000 0.000 – 0.001 2 (1.5, 9.0, 2.5, 4.7) 0.5 0.000 – 0.002 – 0.007 – 0.009 – 0.013 3 (1.5, 8.5, 2.5, 5.2) 0.5 – 0.001 0.000 – 0.003 – 0.006 – 0.010 4 (1.5, 8.5, 2.5, 5.2) 0.5 – 0.001 0.000 – 0.003 – 0.006 – 0.010 5 (2.0, 8.0, 3.0, 4.7) 0.5 0.000 0.004 0.007 0.009 0.011 6 (2.0, 8.0, 2.5, 5.2) 0.5 0.000 0.008 0.010 0.010 0.011 7 (2.0, 8.5, 2.0, 5.2) 0.5 – 0.001 – 0.002 – 0.003 – 0.005 – 0.007 8 (4.0, 8.8, 5.4, 7.7) 0.9 0.000 – 0.005 – 0.007 – 0.010 – 0.014 9 (3.1, 9.7, 5.4, 7.7) 0.9 0.000 – 0.001 – 0.003 – 0.004 – 0.001 10 (3.1, 8.8, 6.3, 7.7) 0.9 0.000 0.000 0.000 0.000 – 0.006 11 (3.1, 8.8, 5.4, 8.6) 0.9 0.000 0.004 0.004 0.004 – 0.001 12 (4.0, 7.9, 6.3, 7.7) 0.9 0.000 0.000 – 0.002 – 0.004 – 0.011 13 (4.0, 7.9, 5.4, 8.6) 0.9 0.004 0.022 0.020 0.019 0.015 14 (4.0, 8.8, 4.5, 8.6) 0.9 0.000 – 0.002 – 0.005 – 0.006 – 0.007 15 (5.9, 8.7, 4.7, 5.4) 1.0 0.000 – 0.001 – 0.003 – 0.004 – 0.010 16 (4.9, 9.7, 4.7, 5.4) 1.0 0.000 0.010 0.011 0.011 0.013 17 (4.9, 8.7, 5.7, 5.4) 1.0 0.000 0.000 0.011 0.003 0.004 18 (4.9, 8.7, 4.7, 6.4) 1.0 0.000 0.001 0.001 0.001 – 0.002 19 (5.9, 7.7, 5.7, 5.4) 1.0 0.000 – 0.007 – 0.010 – 0.010 – 0.010 20 (5.9, 7.7, 4.7, 6.4) 1.0 0.005 0.017 0.013 0.012 0.012 21 (5.9, 8.7, 3.7, 6.4) 1.0 0.000 – 0.002 – 0.005 – 0.007 – 0.012 22 (2.0, 9.0, 2.2, 7.0) 0.9 0.003 0.010 0.013 0.014 0.015 23 (1.1, 9.9, 2.2, 7.0) 0.9 0.000 – 0.007 – 0.011 – 0.014 – 0.014 24 (1.1, 9.0, 3.1, 7.0) 0.9 0.005 0.021 0.023 0.022 0.017 25 (1.1, 9.0, 2.2, 7.9) 0.9 0.002 0.012 0.013 0.012 0.010 26 (2.0, 8.1, 3.1, 7.9) 0.9 – 0.074 – 0.030 – 0.022 – 0.018 – 0.015 27 (2.0, 8.1, 3.1, 7.9) 0.9 – 0.074 – 0.030 – 0.022 – 0.018 – 0.015 28 (2.0, 9.0, 1.3, 7.9) 0.9 0.000 0.000 0.001 0.004 0.010 Аналізуючи табл. 4, можна зробити декілька висновків. По-перше, якщо при 1p  не враховувати спостереження з номерами 26 і 27, то максимальне відхилення серед інших 26-ти значень становить всього 0.005, тоді як при 2p  воно становить 0.022, причому наявні також інші доволі вагомі відхилення: – 0.018 (номери 26 і 27), 0.019 (номер 13), 0.014 (номери 22–23). Загалом серед всіх відхилень при 1p  є лише декілька відмін- них від нуля (а саме 10), тоді як при 2p  таких відхилень 26. Такі висновки вказують на те, що для даного прикладу МНМ ( 1)p  демонструє суттєво кращі результати, ніж МНК ( 2)p  , відки- даючи аномальні спостереження, тоді як МНК враховує їх, зміщуючи розв’язок. По-друге, по мірі того як значення параметра p прямує від 1 до 2, відхилення зростають. Однак при 5p  вони або несуттєво зменшуються, або залишаються незмінними. Очевидно, залежність значення параметра p від відхилень є нелінійною, тому необхідно провести додаткові дослідження цієї залежності для коректного підбору параметра .p В.О. СТОВБА 22 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3 Однак остаточний вибір значення параметра p визначається конкретним набором спостере- жень. Наприклад, наявність викидів під номерами 26 та 27 може бути спричинена похибкою зчитування даних або помилкою експерта, який визначив значення if ; в такому випадку повторне зчитування та перегляд значень експертом можуть покращити ситуацію. З іншого боку, якщо випадкова величина, яка характеризує похибку результатів спостережень, має нормальний розпо- діл ймовірностей, доцільним буде використання МНК. Якщо ж вона має розподіл Пуассона, краще використовувати МНМ. Можливість використання параметра p дозволяє спростити розв’язання задач, описаних в цьому підрозділі, адже замість трьох методів (МНМ, МНК та мінімаксного мето- ду) можна використовувати лише один, а також гнучко підбирати значення параметра p для отри- мання «найкращих» розв’язків. Висновки. Для розв’язання задачі визначення параметрів лінійної регресії можна використо- вувати як класичні методи – МНК та МНМ при нормальному та пуасонівському розподілах випад- кової величини похибки спостережень відповідно, так і методи мінімізації негладких функцій, якщо змінити постановку задачі. В такому випадку за допомогою значення параметра p можна плавно регулювати розв’язок для відкидання аномальних спостережень або їх урахування у випад- ку надійності. Модифіковані формули для обчислення значення цільової функції та її субградієнту дозволяють використовувати довільні значення параметра 1p  , у тому числі доволі великі. У випадку апроксимації спостережень квадратичною функцією схема зведення дозволяє роз- в’язувати цю задачу як задачу визначення параметрів лінійної регресії. Список літератури 1. Демиденко Е.З. Линейная и нелинейная регрессии. М.: Финансы и статистика, 1981. 304 с. 2. Shor N.Z., Stetsyuk P.I. Constructing Utility Functions by Methods of Nondifferentiable Optimization. In: Construct- ing and Appling Objective Functions, Lecture Notes in Economics and Mathematical Systems. V. 510. Berlin: Spring- er-Verlag, 2002. P. 215–232. https://doi.org/10.1007/978-3-642-56038-5_10 3. Стецюк П.И., Колесник Ю.С., Лейбович М.М. О робастности метода наименьших модулей. Компьютерная математика. 2002. С. 114–123. 4. Стецюк П.И., Колесник Ю.С. К вопросу выбора метода аппроксимации результатов измерения. Интеллекту- альные информационно-аналитические системы и комплексы. 2000. С. 62–67. 5. Стецюк П.И., Стовба В.А., Мартынюк И.С. Алгоритм метода эллипсоидов для нахождения Lp-решения систе- мы линейных уравнений. Теорія оптимальних рішень. 2017. С. 139–146. http://dspace.nbuv.gov.ua/handle/123456789/131449 6. Шор Н.З. Метод отсечения с растяжением пространства для решения задач выпуклого программирования. Кибернетика. 1977. № 1. С. 94–95. 7. Стецюк П.И., Стовба В.А., Жмуд А.А. Метод эллипсоидов для нахождения решения переопределенной СЛАУ. Теорія оптимальних рішень. 2018. № 17. С. 115–123. http://dspace.nbuv.gov.ua/handle/123456789/144980 8. Стецюк П.И., Била Г.Д., Стовба В.А. Метод эллипсоидов для нахождения Lp-решения системы линейных уравнений. Інформатика та системні науки (ІСН-2017): матеріали VIII Всеукраїнської науково-практичної конференції за міжнародною участю. Полтава, 16–18 березня 2017 р. 9. Кларк Ф. Оптимизация и негладкий анализ. М.: Наука, 1988. 280 с. 10. Gruber J. Opening Remarks: A Retrospection over 35 Years of Work. Constructing and Appling Objective Functions, Lecture Notes in Economics and Mathematical Systems. V. 510. Berlin: Springer-Verlag, 2002. P. 3–13. https://doi.org/10.1007/978-3-642-56038-5_1 Одержано 11.10.2020 Стовба Віктор Олександрович, аспірант Інституту кібернетики імені В.М. Глушкова НАН України, Київ. vik.stovba@gmail.com https://doi.org/10.1007/978-3-642-56038-5_10 http://dspace.nbuv.gov.ua/handle/123456789/131449 http://dspace.nbuv.gov.ua/handle/123456789/144980 https://doi.org/10.1007/978-3-642-56038-5_1 ../Downloads/vik.stovba@gmail.com МЕТОД ЕЛІПСОЇДІВ ДЛЯ ЗНАХОДЖЕННЯ ПАРАМЕТРІВ ЛІНІЙНОЇ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 23 УДК 519.85 В.А. Стовба Метод эллипсоидов для нахождения параметров линейной регрессии Институт кибернетики имени В.М. Глушкова НАН Украины, Киев Переписка: vik.stovba@gmail.com Введение. Задача определения параметров линейной регрессии может быть сформулирована как задача минимизации негладкой функции, которая представлена как pL -норма вектора-невязки системы линейных уравнений. Для ее решения можно использовать методы минимизации негладких функций, например, субградиентные методы. В работе [7] рассмотрено приложение метода эллипсоидов для нахождения pL -решения переопределенной системы линейных уравнений при 1 2p  . Цель работы. Расширить алгоритм на базе метода эллипсоидов для решения задачи определения параметров линейной регрессии для произвольных значений параметра 2p  так, чтобы при больших значениях p решение задачи совпадало с решением, полученным минимаксным методом, который соответствует значению p  . Описать формулировку задачи аппроксимации наблюдений квадратич- ной функцией как задачи определения параметров линейной регрессии. Проанализировать результаты работы алгоритма для большого количества наблюдений и выбросов. Сравнить результаты работы минимаксного метода и метода эллипсоидов для задачи определения параметров линейной регрессии при больших значениях параметра .p Результаты. Разработан способ вычисления значения целевой функции и ее субградиента при больших значениях параметра ,p проверенного на примере аппроксимации линейной функцией наблюдений, содержащих аномалии. Алгоритм на основе метода эллипсоидов демонстрирует монотон- ность при изменении параметров линейной регрессии с помощью регулировании параметра ,p позво- ляя, таким образом, отбрасывать или учитывать те или иные наблюдения. В работе [3] показано, что преимущество следует отдавать методу наименьших модулей (МНМ), поскольку он игнорирует аномальные наблюдения и точно восстанавливает линейную функцию. Результаты экспериментов с большим количеством наблюдений и выбросов при 1p  подтвердили этот вывод: МНМ игнорирует группы аномалий и адекватно аппроксимирует наблюдения линейной функцией. Метод наименьших квадратов отклоняется от оптимальной линейной функции, если имеется группа аномалий в той или иной области. При использовании больших значений параметра p решение задачи приближается к решению, получаемому минимаксным методом. Выводы. Алгоритм на основе метода эллипсоидов позволяет находить параметры линейной регрессии при произвольном значении параметра 1p  . Это дает возможность использовать три известных метода: метод наименьших модулей, метод наименьших квадратов и минимаксный метод – как его частные случаи. При этом, устремляя p к единице, можно регулировать интенсивность игнори- рования аномальных наблюдений, что дает возможность использовать информацию из внешних источ- ников (экспертные оценки, показания измерительных приборов, статистические прогнозы и т. п.) для более адекватного восстановления аппроксимирующей функции. Ключевые слова: метод эллипсоидов, линейная регрессия, аномальные наблюдения. UDC 519.85 V. Stovba Ellipsoid Method for Linear Regression Parameters Determination V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv Correspondence: vik.stovba@gmail.com Introduction. Linear regression parameters determination can be formulated as a non-smooth function minimization problem, which is pL -norm of residual of the linear equations system. To solve it non-smooth function minimization methods can be used, e.g. subgradient methods. The article [7] considers ellipsoid meth- od application for finding pL -solution of redefined linear equations system with 1 2p  . ../Downloads/vik.stovba@gmail.com ../Downloads/vik.stovba@gmail.com В.О. СТОВБА 24 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3 The purpose of the paper is to extend the algorithm based on the ellipsoid method for a linear regression parameters determination problem with an arbitrary value of parameter 2p  so that under big values of p the solution of the problem equals minimax method solution, which corresponds to p  case. To describe the formulation of observation approximation problem with quadratic function as linear regression parameters determination problem. To analyze algorithm work results for great number of observations and outliers. To compare the minimax method and the ellipsoid method algorithm work results for linear regression parameters determination problem with big values of parameter .p Results. The way of calculation of objective function and its subgradient values with large values of pa- rameter p was developed and verified on example of observation approximation containing outliers with line- ar function. Algorithm based on ellipsoid method changes linear function parameters monotonically using pa- rameter p adjusting, thereby permits to reject or consider these or those observations. It is shown in [3] that Least Absolute Deviations method (LAD) is advised to be used as far as it ignores outliers and reconstructs lin- ear function accurately. Experiment results with big number of observations and outliers using 1p  confirmed that conclusion: LAD ignores outlier groups and approximates observations with linear function adequately. Least Square Method (LSM) deviates from optimal linear function if a group of outliers is present in particular area. In case of using big values of parameter p problem solution converges to minimax method solution. Conclusions. Algorithm based on ellipsoid method permits to determine linear regression parameters with arbitrary value of parameter 1p  . So, three known methods can be used – LAD, LSM and minimax method – as its special cases. Moreover, directing p to 1, intensity of outliers ignoring can be regulated, that gives a possibility to use external sources of information (expert opinions, measuring devices readings, statistical fore- casts, etc.) for more correct and adequate approximation function reconstruction. Keywords: ellipsoid method, linear regression, outliers.

Метод еліпсоїдів для знаходження параметрів лінійної регресії

Репозитарії

Схожі ресурси