Quality control of regression models based on mathematical programming problems
Abstract (English):
The quality of regression models must be evaluated by many indicators. Quality criteria can be the minimum of square sum or absolute values of deviations of the predicted values from the true ones, the adequacy of value and sign of the coefficients in the regression equations, the model robustness, the minimum of signs necessary to fulfil other indicators, and much more. When constructing regression equations using standard programmes, it is quite difficult to simultaneously take into account several of the listed indicators. The aim of the article is to demonstrate that building regression models based on mathematical programming problems allows simultaneously considering a large set of requirements for the solution quality within one model. The scientific novelty lies in the fact that this approach makes it possible to create more complex regression models that take into account the specifics of particular practical problems. For example, in the general sample, there may be different trends at the same time. In this case, it is necessary to find out how many regression equations are required to describe the available observations with a given accu-racy. A special case of such a formulation is piecewise linear regression. Another example can be the need to predict multiple output parameters with a minimal set of identical input parameters. The article presents the practical results of applying the author’s approach to solving regression problems in agglomeration production and forecasting financial results for the banking sector

Keywords:
mathematical programming, regressions: linear, nonlinear, lasso, ridge, elastic, piecewise linear; minimization of the number of features

Введение

Несмотря на то, что различные подходы к решению задач регрессии развиваются с времен Гаусса и Лежандра, т.е. с конца 18 века, до сих пор остается большое количество проблем при оценке качества как самих моделей регрессии, так и результатов, полученных на их основе. Данные проблемы достаточно хорошо освещены в работах различных авторов [1 – 3]. На наш взгляд, качество моделей регрессии нельзя сводить только к различным метрикам (среднеквадратичная ошибка, средняя абсолютная ошибка и т.п). Метрики, конечно, важны, но более важным является адекватность всей модели в целом конкретной практической ситуации. Кроме хороших метрик модель должна быть робастной и устойчивой, содержать по возможности минимальное число признаков, учитывать мнение специалистов о величине и знаках коэффициентов в уравнениях регрессии и другие пожелания практических специалистов, которые являются заказчиками конкретного исследования. То есть понятие качества модели имеет много составляющих и всеми ими надо уметь управлять в рамках самой модели. По нашему мнению, многие такие пожелания могут быть учтены, если модели регрессии представлять как задачи математического программирования.

Следует отметить, что именно появление проблем и необходимость учета пожеланий практических специалистов приводит к появлению новых моделей регрессии. Проблемы с мультиколлинеарностью признаков, необходимостью минимизации числа признаков, абсурдностью, в ряде случаев, величины коэффициентов в уравнениях линейной регрессии (ЛР) способствовали появлению моделей Lasso, Ridge и ElasticNet [4 – 5]. Недостатки классических моделей ЛР привели к появлению принципиально новых видов регрессии, основанных на нейросетях, деревьях решений, методе ближайших соседей и других подходах, заимствованных из других направлений машинного обучения (МО). Новые методы, в ряде случаев, способны давать более точные прогнозы, но явно проигрывают модификациям классической ЛР по интерпретируемости решений, так как не дают решения в аналитическом виде, т.е. в виде некоторого уравнения.

Вместе с тем, в качестве функций для построения уравнений регрессии можно использовать и нелинейные, желательно сепарабельные функции. Сепарабельные функции линейны относительно коэффициентов при их составляющих. Поэтому переход в пространство признаков более высокой размерности приведет опять к задаче ЛР. Например, вместо линейной функции будем использовать полином второй степени, тогда вместо задачи:

min jJ(iIXijai+b-Yj)^2                                                    (1)

Необходимо будет решить задачу:

min jJ(iI1Xijai+iI2Xij2ai+b-Yj)^2                                    (2)

где ai – коэффициенты уравнения регрессии (искомые переменные); b – свободный член (искомая переменная); Xij  – входной i-ый признак j-го наблюдения (константы); Yj  – выходной признак j-го наблюдения (константы); I1  – множество исходных входных параметров; I2  – множество сгенерированных входных параметров (квадраты исходных); J  – множество наблюдений; i, j – индексы соответствующих множеств.

Очевидно, что задача (2) – это тоже задача обыкновенной ЛР с критерием MSE (Mean Squared Error). Естественно, что вместо параболы можно использовать любой полином или сепарабельную функцию. Поэтому далее возможность нелинейности уравнений регрессии отдельно оговаривать не будем, только заметим, что применение не сепарабельных функций может приводить к абсурдным результатам. Заметим также, что с точки зрения математического программирования (МП) модель (1) – это задача квадратичного программирования, записанная в компактной форме. Для решения таких задач мы использовали программный продукт IBM ILOG CPLEX. Данный пакет упомянут неслучайно, так как он позволяет решать, как задачи квадратичного программирования, так и задачи с целочисленными переменными.

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

Классические модификации моделей линейной регрессии в виде задач МП

В принципе, различные классические модификации моделей ЛР отличаются только функцией цели и возникают из желания уменьшить влияние различных факторов на качество решения. Критерий MSE всем хорош с математической точки зрения, но чувствителен к случайным отклонениям выходных параметров Yj  и приводит к смещению уравнения регрессии в их сторону. Для того чтобы минимизировать влияние случайных отклонений может быть использован критерий MAE (Mean Absolute Error). Задача с этим критерием может быть представлена следующим образом:

minjϵJiϵIXij*ai+b- Yj                                                            (3)

Комбинация моделей (1) и (3) приведет к Huber regression.

Если признаки сильно коррелированы (мультиколлинеарны), то необходимо предусмотреть в модели возможность исключения мультиколлинеарных признаков за счет правильного выбора функцией цели. Для этого существует 3 вида моделей регрессии: гребневая (Ridge), лассо (Lasso) и эластичная (Elastic net). Все эти регрессии совмещают в одной модели 2 критерия.

В случае гребневой регрессии целевая функция будет следующего вида:

min jJ(iIXij*ai+b-Yj)^2+L*(iϵIai2+b2)                                   (4)

где L – большая константа (коэффициент регуляризации).

В случае регрессии лассо величины ai и b регулируются другим способом:

min jJ(iIXij*ai+b-Yj)^2+L*(iϵIai+b)                                  (5)

При объединении гребневой и лассо регрессий получаем эластичную. Так как изменением L можно регулировать величины ai и b, данные модели часто называют моделями регуляризации. Все вышеуказанные модели регрессии представлены как задачи МП и могут быть решены современными пакетами (CPLEX, Gurobi, Mosek Xpress, и т.д.), многие из которых имеют соответствующее API Python. Примеры использования МП в регрессионном анализе приводятся в ряде статей других авторов. Среди иностранных исследований интересный подход к проблеме можно выделить в работах [6 – 8]. Российские авторы также имеют значимые научные результаты в данном направлении, такие как [9, 10].

Модификации моделей ЛР, возникшие при решении практических задач

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

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

minjJzj                                                                           (6)

1-d*Yj-L*zjiIXij*ai+b1+d*Yj+L*zj   jJ                (7)

где d – задаваемая константа в диапазоне 0 < d < 1 (максимально допустимый диапазон отклонения прогнозируемых параметров от выходных); zj – признак непопадания или попадания в диапазон d (булева переменная).

В модели (6) – (7) минимизируется количество наблюдений, не попадающих в заданный диапазон отклонений. Конечно, можно использовать более сложные целевые функции, например:

minjJzj  *L+ jJiIXij*ai+b-Yj                                            (8)

Именно такие модели, использовались при решении задач «Учет в модели ограничения по KPI, установленного руководством» и «Анализ и прогнозирование выхода годного и прочности агломерата» по [11, 12]. Такие модели называются MILP (Mixed Integer Linear Programs) regression. Естественно, данный подход необходимо сравнить с другими моделями регрессии. Такое сравнение приведено в [12].

В ряде случаев мы использовали следующую последовательность действий:

1. Решали задачу на основе модели (6), (7), т.е. устраняли большие отклонения.

2. Отфильтровывали случайные выбросы

3. На уточненном множестве использовали модель (1) или (3).

Отметим, что такой подход к решению задач регрессии является удобным с практической точки зрения, так как позволяет, меняя значения допустимого диапазона, оценивать какое количество наблюдений необходимо исключить из рассмотрения. Естественным образом сразу возникает другая постановка задачи: каким может быть минимальный диапазон отклонений при количестве исключенных наблюдений не выше заданного уровня. Для решения такой задачи достаточно изменить целевую функцию и добавить одно ограничение к системе ограничений (7). Приведем эти дополнительные условия:

mind                                                                              (9)

jϵJzjG                                                                        (10)

где G – верхняя граница количества наблюдений, исключенных из рассмотрения.

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

min jJωj                                                                       (11)

1-d*Yj-L*zjfiIXij*aif+bf1+d*Yj+L*zjf      fF, jJ            (12)

f∈Fzjf ≤k-1+ωj                          jJ                                     (13)

где k – количество функций; F – множество функций; f – индекс функции f = 1 ... k; aif – коэффициенты при параметрах функций; bf  – свободные члены функций; zjf  – признак попадания в диапазон f-ой функции (булева переменная); ωj  – признак непопадания в диапазон всех функций (булева переменная).

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

При решении задач регрессии практически всегда требуется минимизировать число признаков в уравнениях регрессии. В классических моделях регрессии для этого обычно используется метод Лассо. Естественно, что для этих целей могут быть использованы и булевы переменные. Различные разновидности таких моделей с момента их возникновения достаточно подробно описаны в работах Базилевского М.П. [9].

В приведенных нами моделях достаточно часто используются булевы переменные для минимизации числа признаков и обычно это делается в 4 этапа:

1. Решаем серию задач на основе модели (6), (7) при различных значениях d и определяемся со значениями d и G.

2. Ограничиваем условием (10) предельно допустимое количество наблюдений, которые могут быть исключены из рассмотрения.

3. Вводим следующие новые дополнительные булевы переменные и ограничения на их основе:

-L*ziaiL*zi                                                                 (14)

где zi – булева переменная, при 1 информативен, при 0 неинформативен.

4. В качестве целевой функции используем:

mini∈Izi                                                                             (15)

То есть в окончательном виде модель минимизации числа признаков выглядит как (7), (10), (14) – (15). Данный подход был использован при прогнозировании прочностных характеристик агломерата [8].

Исходный набор данных составлял 3200 наблюдений при 240 параметрах и многократно разбивался на тренировочную выборку (2500 наблюдений) и тестовую (700 наблюдений). Для поиска уравнений регрессии в качестве базовой использовалась модель (7), (10), (14), (15). В качестве информативных параметров были оставлены 43 параметра, и практические специалисты смогли обосновать почему именно эти параметры подходят наилучшим образом, т.е. смогли их проинтерпретировать. Отметим, что интерпретируемость полученных решений было обязательным требованием заказчиков исследования, и не интерпретируемые подходы к решению задач регрессии (нейронные сети, случайный лес и т.п.) нам не подходили. Более того, по ходу решения задачи возникали дополнительные требования к коэффициентам уравнений регрессии. Данные требования и интерпретация полученных решений описаны нами в [8, 9].

Прогнозирование нескольких выходных параметров минимальным набором

одинаковых входных параметров

Начнем с того как такая постановка возникла. Для оценки качества агломерата в агломерационном цехе используется 2 показателя: холодная прочность и транспортная. Холодная прочность показывает сколько мелкой фракции образуется при производстве агломерата, а транспортная при его транспортировке по конвейеру до доменной печи. Наличие мелкой фракции в доменной шихте отрицательно влияет на работу доменной печи. Поэтому количество мелкой фракции необходимо уметь прогнозировать и понимать, какие факторы наиболее влияют на ее образование. Возникает вопрос: «Зачем прогнозировать 2 показателя одним набором признаков?». Гораздо проще найти уравнение регрессии для каждого показателя по отдельности. Кроме того, наборы информативных признаков для различных показателей могут отличаться друг от друга. Согласны, но для сбора данных используются определенные датчики, причем некоторые из них достаточно дорогостоящие. Поэтому необходимо выяснить, существует ли набор датчиков, который с заданной точностью позволит прогнозировать 2 различных показателя.

Для построения модели, в рамках которой будем прогнозировать несколько выходных параметров с минимальным набором одинаковых входных параметров, будем использовать следующую систему ограничений:

1-d*Yjt-L*zjtiIXij*ait+bt1+d*Yjt+L*zjt      tTjJ        (16)

jϵJzjtGt    tT                                                               (17)

-L*ziaitL*zi   tT                                                        (18)

miniϵIzi                                                                        (19)

Множество T в данной модели – это множество выходных параметров. Смысл остальных обозначений тот же что и в предыдущих моделях.  В модели (16) – (19) допускается, что при поиске разных уравнений регрессии могут быть исключены разные наборы наблюдений. Для того, чтобы исключался один и тот же набор наблюдений, необходимо ужесточить ограничения (16), (17). При излишнем ужесточении системы ограничений может возникать противоречивость. В таком случае необходимо ослабить некоторые ограничения введением переменных их корректирующих и минимизацией числа таких корректировок.

Заключение

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

Еще хотелось бы отметить один очевидный факт, что готовые уравнения ЛР достаточно легко можно использовать в различных моделях, относящихся к исследованию операций (ИО), особенно если это тоже модели МП. Более того, во многих случаях уравнения ЛР именно для этого и предназначены. Более интересным является то, что модель (16) – (19) в исходном виде может быть объединена с моделями ИО. Обратите внимание на текст, выделенный в данном абзаце жирным шрифтом. Если выбор того или иного подмножества признаков в качестве наиболее информативного влечет за собой определенный набор организационных мероприятий, то их можно оценить в стоимостном выражении, а это означает, что модель можно развивать дальше за счет ввода дополнительных ограничений, не имеющих никакого отношения к МО, или видоизменить функцию цели (19). В этом случае в ней перед zi появятся стоимостные коэффициенты, и в модели можно будет учитывать экономические показатели.

Предлагаемый подход обладает следующими достоинствами:

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

2. Позволяет минимизировать число признаков необходимых для выполнения первого пункта.

3. Математические модели достаточно простые, хорошо воспринимаются практическими специалистами, не требуют знания методов МП и навыков программирования на языках высокого уровня.

4. Модели ЛР на основе МП легко встраиваются в другие модели ИО.

Критики нашего подхода обычно утверждают, что задачи MILP плохо и долго считаются. После этого упоминаются NP-полные задачи и т.п. Конечно, алгоритм с полиномиальным изменением времени счета в зависимости от размерности задачи для решения NP-полных задач до сих пор не найден, но из этого не следует, что не надо решать задачи MILP. C момента появления пакета MPSX-360, а это начало 80-х годов прошлого века, задачи MILP большой размерности успешно решаются. Действительно, время счета задач с сотнями переменных и десятками тысяч наблюдений может составлять несколько часов, но на выходе получается качественное решение, соответствующее требованиям заказчика исследования.

1. Gel'man E., Hill D., Vehtari A. Regressiya: teoriya i praktika. S primerami na R i Stan // M.: DMK press, 2022. - 748 s.

2. Ye A. Machine Learning Regression Algorithms You Need to Know, 2020, URL: https://medium.com/analytics-vidhya/5-regression-algorithms-you-need-to-know-theory-implementation-37993382122d (data obrascheniya 08.12.20220)

3. Willmott C.J., Matsuura Kenji Advantages of the mean absolute error (MAE) over the root mean square error (RMSE) in assessing average model performance. Climate Research, 2005, 30 p. 79-82.

4. Huber, P.J (1964) Robust Estimation of a Location Parameter. Annals of Statistics, 53(1), p. 73-101.

5. Zou, H. & Hastie, T. Regularization and Variable Selection via the Elastic Net. Journal of the Royal Statistical Society Series B, 2005, p. 301-320

6. Gkioulekas Y. & Papageorgiou L.G. Piecewise regression through the Akaike information criterion using mathematical programming. IFAC PapersOnLine, 2018, vol. 51, no. 15, pp. 730-735.

7. Wang V.Q., Shukova S., Lai C.D. On the relationship between regression analysis and mathematical programming. Journal of applied mathematics and deci-sion sciences, 2004, vol. 8, no. 2, pp. 131-140.

8. Yang, L., Liu, S., Tsoka, S. & Papageorgiou, L.G. A regression tree approach using mathematical programming. Expert Systems with Applications, 2017, vol. 78, pp. 347-357.

9. Bazilevskiy M.P. Svedenie zadachi otbora informativnyh regressorov pri ocenivanii liney-noy regressionnoy modeli po metodu naimen'shih kvadratov k zadache chastichno-bulevogo lineynogo programmirovaniya // Modelirovanie, optimizaciya i informacionnye tehnologii (Voronezh), 2018. - T.6. - №1 (20). - C. 108-117.

10. Gorelika V.A., Trembacheva O.S. Reshenie zadachi lineynoy regressii s ispol'zovaniem metodov matrichnoy koprekcii v metrike // Zh. vychisl. matem. i matem. fiz., 2016. - T. 56. - № 2. - C. 202-207.

11. Chernavin P. F., Malygin A. V., Detkova T. V., Kuchin V.Yu. Analiz i prognozirovanie vyhoda godnogo i prochnosti aglomerata na osnove modeley matematicheskogo programmirovaniya // Chernye Metally, 2021. - № 12. - S. 20-24.

12. Chernavin P.F., Gaynanov D. N., Pankraschenko V.N., Chernavin F.P., Chernavin N.P. Mashinnoe obuchenie na osnove zadach matematicheskogo pro-grammirovaniya // M.: Nauka, 2021. - 128 s.