Using mathematical programming models to solve XOR problems

Толық мәтін

Введение. Проблема XOR (exclusive OR, исключающее ИЛИ) – одна из наиболее важных классических проблем в области машинного обучения (МО). Поэтому ее решению различными способами посвящено большое количество исследований. Впервые эту проблему сформулировал создатель персептрона Фрэнк Розенблатт в 1961 году [1]. Наиболее просто данная проблема воспринимается, когда она сформулирована в геометрическом виде (рисунок 1). Пусть имеется всего 4 точки: две синих и две красных. Необходимо отделить синие точки от красных одной прямой.

 

Рис.1. Общая геометрическая постановка проблемы XOR

 

Суть проблемы состоит в следующем. На рисунке 1 множество красных точек одной линией (в общем случае гиперплоскостью) нельзя отделить от синих точек. То есть два множества линейно неразделимы. Несмотря на кажущуюся простоту задачи, многие специалисты по искусственному интеллекту (ИИ) посвятили ей свои исследования [2-13] и их разработки, с одной стороны, способствовали развитию методов машинного обучения (МО), но и приводили к так называемой «зиме ИИ» [2, 5]. Конечно, на практике все выглядит несколько сложнее и каждую точку надо воспринимать, как некоторое подмножество генеральной выборки. Обычно рассматриваются две ситуации. Назовем их простая (рисунок 2) и сложная (рисунок 3).

 

Рис. 2. Множества с простой структурой

 

Рис. 3. Множества со сложной структурой

 

При описании проблемы XOR обычно используется следующая схема: объясняется суть проблемы, показывается неэффективность использования ряда методов МО (логистическая регрессия, метод опорных векторов с полиномиальным ядром, случайный лес деревьев и т.п.), далее говорится, что задача решается достаточно простой нейросетью (НС) и поясняется, как это делается методом обратного распространения ошибки. Конечно, метод обратного распространения ошибки в настоящий момент является лидером среди методов обучения НС, но, как всякий метод, он имеет ряд существенных недостатков. Поэтому даже пионер в области Deep Learning Джеффри Хинтон считает, что надо заниматься поиском альтернатив, и предлагает свой новый метод Forward‑Forward [6].

Альтернативным подходом к решению проблемы XOR может быть применение метода комитетов. Комитетный подход к решению задач классификации был предложен Аблоу С.М. в 1965 году [7, 8]. Большой вклад в развитие данного метода за рубежом был сделан в работах Осборна М. Л [9] и Такиямы Р. А. [10]. В нашей стране наиболее полное развитие метод комитетов получил в научных школах распознавания образов Мазурова В. Д. [11, 12] и Журавлева С. Ю. [13]. Различные комитетные конструкции могут быть представлены в виде задач математического программирования (МП) [14] и решаться с помощью стандартных пакетов для решения таких задач, например, IBM ILOC CPLEX. Данный пакет позволяет за приемлемое время решать задачи МП большой размерности. Сведение процесса построения комитетных конструкций к задачам МП предоставляет дополнительные возможности по управлению качеством решающего правила (РП) в процессе его построения, а не постфактум, как это происходит при использовании программ из стандартных библиотек МО [15].

Традиционно рассматриваются комитеты с логикой единогласия, большинства и старшинства. В статьях Такиямы Р.А. [10] приводится модель комитета с произвольной логикой, но эта модель в конечном итоге сводится только к комитетам единогласия и большинства (КБ). Отметим, что комитет единогласия (КЕ) существует не всегда, но имеет наиболее простую структуру. В работах Мазурова В.Д. [11] доказано, что комитет большинства существует всегда. Так как комитет старшинства (КС) можно построить итерационным способом с отсечением хотя бы одного из элементов множества точек классов на каждой итерации, то он тоже существует всегда. Одним из достоинств комитетных конструкций является то, что каждая из них имеет четкие геометрические интерпретации. Поэтому при использовании метода комитетов можно не только получить решающее правило (РП), но и понять структуру данных, что достаточно важно при решении практических задач. Модели классических комитетных конструкций в виде задач МП и их графические интерпретации приведены в [14], причем каждая из них наиболее эффективна по числу членов комитета и метрикам качества РП только при определенной структуре данных. Например, при структуре, соответствующей рисунку 3, все классические комитеты дадут достаточно посредственный результат. Поэтому возникает закономерный вопрос о существовании комитетов с принципиально другой логикой, позволяющей при минимальном числе членов комитета добиться высоких метрик качества РП. Вопрос существования таких комитетных конструкций является отдельной научной проблемой. Один из вариантов ее решения предлагается в данной статье.

Для решения проблемы XOR с простой структурой данных лучше всего использовать итерационный КС или КЕ [14]. На рисунках 2 и 3 направления голосования (градиенты функций) членов комитета показаны черными стрелками. На рисунке 2 видно, что структура множеств позволяет решить задачу классическими КЕ или КС. При структуре множеств, как на рисунке 3, классический КЕ невозможен, а КБ и КС будут избыточно сложными и не дадут хорошего качества РП. Поэтому необходимо использовать отдельную комитетную конструкцию со следующей логикой:

1. Для элементов одного из множеств все члены комитета единогласно голосуют либо за, либо против. Это множество далее будем обозначать как $J_1$.
2. Для элементов другого множества мнение хотя бы одного из членов комитета не совпадает с мнением остальных. Это множество далее будем обозначать как $J_2.$

Следует отметить, что при такой логике комитет единогласия является частным случаем XOR-комитета. При построении новой комитетной конструкции сразу следует учитывать, что в практических задачах построение любых комитетов без погрешности встречается довольно редко и скорее всего свидетельствует о переобучении модели. Естественно, что количество невыполнений условий комитета должно быть минимизировано. Новую комитетную конструкцию назовем XOR-комитет и приведем ее математическую модель. Так как любое наблюдение можно представить, как точку в пространстве входных признаков, то в дальнейшем слова “наблюдение” и “точка множества” будем использовать как слова-синонимы.

1. Математическая модель XOR-комитета

Далее будем использовать следующую систему обозначений:

$J_1$ и $J_2$ – разделяемые множества;

$J$ – множество наблюдений (точек)  $J=J_1\cup J_2$;

$M1$– мощность множества1 (количество наблюдений, точек);

$M2$– мощность множества2 (количество наблюдений, точек) ;

$I$ – множество параметров наблюдений;

$H$ – множество гиперплоскостей (членов комитета, нейронов);

$j,i,h$ – индексы соответствующих множеств;

$P_{ij}$– входные признаки наблюдений (константы);

$L$ – очень большое число;

$E$ – малое число, используемое для строгости ограничений;

$K$– количество гиперплоскостей (членов комитета, нейронов) ;

$a_i^{h }$– коэффициенты гиперплоскостей (переменные);

$b^h$ – свободные члены гиперплоскостей (переменные);

$v_j^h, w_j^{h }–$расстояние от $j$-ой точки до $h$-ой гиперплоскости (переменные);

$z_j^h–$булевы переменные, для фиксации расположения $j$-ой точки

относительно $h$-ой гиперплоскости;

$y_j$ – булева переменная (y=0 – все члены голосуют за, y=1 – все члены голосуют против);

$d_j$ – переменные для коррекции нижних границ комитетной конструкции;

$g_j$ – переменные для коррекции верхних границ комитетной конструкции.

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

$\sum _{}_{i\in I}{P}_{ij}\text{*}{a}_i^h+b^h+v_j^h-w_j^h=0h\in H,j\in J$(1)

$0\le v_j^h\le L\text{*}{z}_j^{h}h\in H,j\in J$(2)

$0\le w_j^h\le L\text{*}\left(1-z_j^h\right)h\in H,j\in J$(3)

Условия (2), (3) запрещают переменным $v_j^h, w_j^h$ одновременно быть больше нуля.

Условия для XOR-комитета, c возможностью их корректировки, могут быть записаны следующим образом:

$\sum _{}_{h\in H}{z}_j^h=K\text{*}{y}_j-d_j+g_{j}j\in J_1$ (4)

$d_j\le Kj\in J_1$ (5)

$g_j\le Kj\in J_1$ (6)

$1-d_j\le \sum _{}_{h\in H}{z}_j^h\le K-1+g_{j}j\in J_2$ (7)

$d_j\le 1j\in J_2$ (8)

$g_j\le 1j\in J_2$ (9)

Следует отметить, что чисто теоретически без разницы, какое из множеств считать за $J_1$, а другое за $J_2$. На рисунке 2 видно, что для смены множеств местами (в модели) достаточно развернуть градиент одной из гиперплоскостей.

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

$v_j^h+w_j^h\ge Eh\in H,j\in J_1$ (10)

Это ограничение будет запрещать точкам одного из множеств попадать на гиперплоскости.

Целевая функция: $\min \sum _{}_{j\in J}(d_j+g_j)$ (11)

При использовании целевой функции (11) будет максимизироваться метрика Accuracy (Аккуратность). Данная метрика качества РП хорошо воспринимается практическими специалистами и хорошо работает при сбалансированных классах. В случае сильной несбалансированности классов лучше использовать метрику AUC ROC (площадь под ROC кривой). В этом случае целевая функция будет:

$\min M2*\sum _{}_{j\in J_1}(d_j+g_j)+M1*\sum _{}_{j\in J_2}(d_j+g_j)$(12)

Подробное описание метрик Accuracy и AUC ROC, а также обоснование, что критерии (11), (12) им соответствуют, приведены в [14]. Дополнительные возможности по управлению качеством РП приведены в [15]. На основе данной модели написаны программы в кодах IBM ILOC CPLEX и на языке Python c использованием пакета MIP (Mixed Integer Programming). Программа на Python зарегистрирована в Федеральном институте промышленной собственности [16].

2. Апробирование XOR-комитета на условных примерах. Для условных примеров были использованы данные, приведенные на рисунках 2 и 3. В таблицах 1 и 2 приведены метрики качества РП, полученные классическими методами МО и различных комитетных конструкций.

 

Таблица 1. Результаты метрик методов МО при простой структуре множеств

Название метода	Accuracy	AUC ROC
Линейное разделение	0.586	0.543
Опорных векторов	0.621	0.591
Логистическая регрессия	0.586	0.484
Ближайших соседей	0.897	0.874
Наивный байес	0.621	0.568
Дерево решений	0.828	0.797
Нейронная сеть из двух нейронов	0.790	0.754
Нейронная сеть из трех нейронов	0.923	0.945
Комитет единогласия из двух членов	0.881	0.885
Комитет единогласия из трех членов	0.881	0.885
Комитет большинства из трех членов	0.706	0.755
Комитет старшинства из двух членов	0.748	0.755
Комитет старшинства из трех членов	0.741	0.759
XOR - комитет из двух членов	0.86	0.836
XOR - комитет из трех членов	0.839	0.834

 

Таблица 2. Результаты метрик методов МО при сложной структуре множеств

Название метода	Accuracy	AUC ROC
Линейное разделение	0.521	0.41
Опорных векторов	0.479	0.391
Логистическая регрессия	0.396	0.354
Ближайших соседей	0.833	0.796
Наивный байес	0.708	0.362
Дерево решений	0.771	0.834
Нейронная сеть из двух нейронов	0.848	0.911
Нейронная сеть 2 скрытых слоя 6 нейронов	0.954	0.923
Комитет единогласия из двух членов	0.852	0.867
Комитет единогласия из трех членов	0.801	0.827
Комитет большинства из трех членов	0.519	0.64
Комитет старшинства из двух членов	0.464	0.639
Комитет старшинства из трех членов	0.561	0.755
XOR - комитет из двух членов	0.966	0.954
XOR - комитет из трех членов	0.966	0.954

 

При простой структуре множеств метрики качества решения комитета единогласия из двух членов лучше метрик нейронной сети из двух нейронов в 1 скрытом слое (активатор ReLU). При трех нейронах метрики нейронной сети становятся лучше метрик комитетов единогласия. XOR-комитет показал результаты, сопоставимые с комитетом единогласия, но несколько хуже. Значит, комитет единогласия наиболее подходит для описания структуры множества синих точек на рисунке 2, так как дает наиболее простое и хорошо интерпретируемое решение.

При сложной структуре множеств наилучшие метрики качества показывает XOR-комитет из двух членов. Нейронная сеть сопоставимые результаты показала только при архитектуре в 2 скрытых слоя (в первом слое 4 нейрона, во втором слое 2 нейрона). Все остальные методы имеют метрики качества значительно хуже.

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

XOR-комитеты представляют собой один из подходов, способный обеспечить как высокую точность, так и интерпретируемость модели, что делает их полезным инструментом для работы с реальными, сложными данными. Заметим, что по сравнению с нейронной сетью используется более простая архитектура – множество было разделено с аналогичным качеством с использованием 2 гиперплоскостей, что значительно проще для анализа данных, тогда как нейронная сеть потребовала 2 слоя и 6 нейронов, что затрудняет интерпретацию решения.

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

Заключение. В данной статье приведена комитетная конструкция с логикой, существенно отличающейся от классических логик единогласия, большинства и старшинства. Естественно, что любой человек не может видеть картину расположения данных в пространствах более трех, но понять их структуру по аналогии с двухмерным пространством возможно на основе методов МО и, особенно, комитетных конструкций. Поэтому при решении конкретной задачи надо применять все доступные методы машинного обучения и сравнивать метрики качества РП, полученных на их основе. При этом надо понимать, что качество решения не сводится только к классическим метрикам Accuracy, Precision, AUC ROC т.п [15]. Обязательно надо учитывать сложность РП и интерпретируемость. Конечно, переход от линейных разделителей к полиномиальным может дать улучшение метрик качества, но увеличит ли это интерпретируемость РП? Аналогично, использование случайного леса с большим количеством деревьев обычно улучшает результат прогноза, но делает его не интерпретируемым. Все эти вопросы наиболее остро встают при сложной структуре исходных данных, поэтому поиск новых методов решения проблемы XOR остается актуальной задачей.

Авторлар туралы

Pavel Chernavin

Ural federal university

Хат алмасуға жауапты Автор.
Email: p.f.chernavin@urfu.ru
ORCID iD: 0000-0003-3214-3906
SPIN-код: 6370-8103

Ph.D., associate professor of the department of Big Data analytics and video analysis methods

Ресей, Yekaterinburg

Nikolai Chernavin

Ural federal university

Email: ch_k@mail.ru
ORCID iD: 0000-0002-2093-9715
SPIN-код: 5722-9436

assistant of the department of Big Data analytics and video analysis methods

Ресей, Yekaterinburg

Fedor Chernavin

Ural federal university

Email: chernavin_fedor@mail.ru
ORCID iD: 0000-0003-4105-231X
SPIN-код: 9237-5190

Ph.D., associate professor of the department of Big Data analytics and video analysis methods

Ресей, Yekaterinburg

Әдебиет тізімі

Қосымша файлдар