Метод комитетов

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

Версия от 13:21, 25 июля 2026; Kirill Bazhutov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Первоначальная версия статьи написана с использованием LLM Gemini и проверена участником Kirill Bazhutov 17:21, 25 июля 2026 (MSD)


Метод комитетов (англ. Method of committees, Committee machine) — метод машинного обучения, распознавания образов и исследования операций, в котором решение строится не одной решающей функцией, а конечной совокупностью функций или допустимых частичных решений — комитетом. Ответ комитета определяется заранее заданным правилом согласования голосов его членов: большинством, квалифицированным большинством, взвешенным голосованием, старшинством и другими правилами.

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

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

Содержание

Формальная постановка

Комитет системы требований

Пусть Y — пространство возможных решений, а

D_1,\ldots,D_m \subseteq Y

— множества решений, удовлетворяющих отдельным требованиям. Обычное решение системы должно принадлежать пересечению

\bigcap_{j=1}^{m}D_j.

Если это пересечение пусто, система несовместна. Конечная последовательность

K=(y_1,\ldots,y_q), \quad y_i\in Y,

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

\left|\left\{i \in \{1,\ldots,q\}: y_i \in D_j\right\}\right| > \frac{q}{2}, \quad j=1,\ldots,m.

Таким образом, каждый член комитета может нарушать часть требований, но каждое требование поддерживается большинством членов. Это и есть обобщение понятия решения на несовместный случай.

Более общая пороговая конструкция называется p-комитетом:

\left|\left\{i: y_i \in D_j\right\}\right| > pq, \quad j=1,\ldots,m,

где 0 \le p < 1. При p=1/2 получается обычный комитет большинства; значения p>1/2 задают квалифицированное большинство.

Комитет для системы линейных неравенств

Для системы

\langle a_j,x\rangle > b_j, \quad j=1,\ldots,m,

членами комитета служат векторы x^{(1)},\ldots,x^{(q)}. Для каждого неравенства более половины этих векторов должны его удовлетворять:

\left|\left\{i: \langle a_j, x^{(i)} \rangle > b_j\right\}\right| > \frac{q}{2}.

Такой комитет может существовать и тогда, когда вектора, удовлетворяющего всем неравенствам одновременно, нет.

Разделяющий комитет в классификации

Пусть A, B \subset \mathbb{R}^n — обучающие множества двух классов. Аффинный комитет

Q=(f_1,\ldots,f_q), \quad f_i(x)=c_i^{T}x-d_i,

разделяет A и B, если:

\left|\left\{i: f_i(a) > 0\right\}\right| > \frac{q}{2}, \quad \forall a \in A,
\left|\left\{i: f_i(b) < 0\right\}\right| > \frac{q}{2}, \quad \forall b \in B.

Решение для нового объекта может быть записано в виде:

h(x) = \operatorname{sign}\left(\sum_{i=1}^{q}\operatorname{sign}f_i(x)\right).

При равенстве числа голосов правило должно предусматривать ничью: отказ от классификации, дополнительный решающий член или иной способ разрешения равенства. Для любых конечных непересекающихся множеств A и B аффинный разделяющий комитет существует всегда, даже если классы не являются линейно разделимыми.[1]

Минимальным называется комитет с наименьшим возможным числом членов. Поиск минимального аффинного разделяющего комитета в общем случае является NP-трудной задачей.[1]

Основные правила принятия решения

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

Комитет большинства

Каждый член имеет один голос, а принимается вариант, получивший строго больше половины голосов. Для бинарной классификации:

h(x) = \left\{ \begin{array}{ll} +1, & \sum_{i=1}^{q} I[h_i(x)=+1] > q/2, \\ -1, & \sum_{i=1}^{q} I[h_i(x)=-1] > q/2. \end{array} \right.

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

Квалифицированное большинство и p-комитет

Решение принимается, если доля поддержавших его членов превышает заданный порог p>1/2. Чем выше порог, тем осторожнее правило и тем шире область отказа от решения. В задачах несовместных ограничений p-комитет требует, чтобы каждое ограничение выполняла доля членов, превышающая p.

Взвешенный комитет

Членам назначаются веса w_i \ge 0. При бинарных голосах h_i(x) \in \{-1,+1\} решение задаётся знаком взвешенной суммы:

h(x)=\operatorname{sign}\left(\sum_{i=1}^{q}w_i h_i(x)-\theta\right),

где \theta — порог. Обычное большинство получается при одинаковых весах и соответствующем пороге. В разных источниках такие конструкции могут называться взвешенными комитетами; их не следует смешивать с p-комитетом, в котором буквой p обозначена требуемая доля голосов.

Комитет единогласия

В бинарной классификации комитет единогласия обычно задаётся асимметрично. Для всех объектов одного класса требуется одинаковый голос каждого члена, а для каждого объекта другого класса — хотя бы один противоположный голос. Например:

f_i(a) > 0, \quad \forall a \in A, \quad i=1,\ldots,q,
\left|\left\{i: f_i(b) < 0\right\}\right| \ge 1, \quad \forall b \in B.

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

Комитет старшинства

Члены упорядочены по приоритету:

h_1 \succ h_2 \succ \ldots \succ h_q.

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

Комитет старшинства можно представить взвешенным голосованием, если вес каждого старшего члена превышает сумму весов всех младших:

w_i > \sum_{j=i+1}^{q}w_j, \quad i=1,\ldots,q-1.

Тогда голос старшего члена нельзя перевесить совокупностью младших голосов. В отличие от большинства, такая схема моделирует не равноправие решающих правил, а иерархию их надёжности или компетентности.[1]

Комитетные логики

Голосование большинства, единогласие, пороговые и иерархические правила являются частными способами агрегирования. В более общих комитетных конструкциях итог задаётся логической функцией от голосов членов. В работах школы В. Д. Мазурова и М. Ю. Хачая такое направление связано с логикой комитетных структур (MK-логикой), предназначенной для формального описания коллективных решений при противоречивых данных.[1]

Научная школа В. Д. Мазурова

Возникновение метода

Идея «комитетной машины» появилась в ранних работах по обучаемым системам распознавания, в частности у Н. Нильссона. В них сложное решающее правило составлялось из нескольких линейных пороговых элементов. В работах В. Д. Мазурова эта идея была связана с теорией несовместных систем неравенств и получила самостоятельное развитие как метод обобщённых решений.

В статье «О комитете системы выпуклых неравенств» 1968 года было введено и исследовано комитетное решение для системы ограничений.[1] В работах конца 1960-х — начала 1970-х годов В. Д. Мазуров изучал релаксационные процессы для противоречивых систем линейных неравенств и применение комитетов к распознаванию образов. Статья «Комитеты систем неравенств и задача распознавания» 1971 года непосредственно связала комитетные конструкции с построением классификаторов.

Основные идеи школы

Ключевые направления, получившие развитие в работах В. Д. Мазурова и его соавторов, включают:

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

Монография В. Д. Мазурова «Метод комитетов в задачах оптимизации и классификации» 1990 года систематизировала геометрические, оптимизационные и алгоритмические основы направления. В ней метод строится через анализ совместных и несовместных подсистем ограничений и применяется к задачам классификации и оптимального планирования.

В 1990-е—2010-е годы теория развивалась в совместных работах В. Д. Мазурова, М. Ю. Хачая, А. И. Рыбина, М. И. Поберия и других исследователей екатеринбургской школы. Были исследованы комитетные правила для выбора, диагностики и прогнозирования, связь с теорией игр и коллективным принятием решений, системы линейных неравенств, минимальные аффинные комитеты, их вычислительная сложность и аппроксимируемость.[1][1] В работе 2013 года была отдельно рассмотрена связь бустинга с приближённым построением минимального аффинного разделяющего комитета.[1]

Построение комитетов

Единственного универсального алгоритма построения комитета нет. Типичная схема для несовместной системы ограничений состоит из следующих этапов:

  1. Выявление совместных подсистем исходных требований, часто максимальных по включению.
  2. Нахождение одного или нескольких решений каждой выбранной совместной подсистемы.
  3. Формирование множества кандидатов в члены комитета.
  4. Выбор членов и, при необходимости, их весов так, чтобы каждое исходное требование получило установленное число или долю голосов.
  5. Минимизация размера комитета либо другой функции качества.

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

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

Сходство и различия с ансамблевым обучением

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

Характеристика Метод комитетов в школе В. Д. Мазурова Ансамблевое обучение
Исходная задача Несовместная система ограничений, противоречивые данные или отсутствие одного разделяющего правила Повышение качества и устойчивости прогнозирования
Члены композиции Частичные решения совместных подсистем, аффинные или иные решающие функции Произвольные базовые модели: деревья, линейные модели, нейронные сети и другие
Основное условие Каждое требование или обучающий объект должно получить заданную долю правильных голосов Обычно минимизируется ошибка или функция потерь на обучении и валидации
Агрегация Большинство, p-порог, веса, единогласие, старшинство, логическая комитетная конструкция Голосование, усреднение, взвешенная сумма или обучаемая метамодель
Типичные методы построения Совместные подсистемы ограничений, релаксационные и комбинаторные алгоритмы Бэггинг, случайные подпространства, бустинг, стэкинг
Теоретический акцент Обобщённая разрешимость, существование и минимальный размер комитета Обобщающая способность, смещение и дисперсия, статистическая согласованность

В бэггинге модели обучаются на бутстрап-выборках, в бустинге — последовательно исправляют ошибки композиции, а в стэкинге их ответы объединяет обучаемая метамодель. Эти способы могут использовать голосование, но сами по себе не требуют, чтобы базовые модели были решениями совместных подсистем несовместной задачи. И наоборот, существование комитета на обучающей системе ограничений не гарантирует хорошего качества на новых данных: для этого необходим отдельный статистический анализ обобщающей способности.

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

Преимущества и ограничения

Преимущества:

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

Ограничения:

  • построение минимального комитета является комбинаторно сложной задачей;
  • число совместных подсистем и кандидатов может быстро расти с размером задачи;
  • результат зависит от выбранного класса членов и правила голосования;
  • при чётном числе голосов, воздержаниях или равенстве взвешенных сумм требуется правило разрешения ничьей;
  • выполнение комитетных условий на обучающей выборке само по себе не обеспечивает обобщение на новые объекты;
  • большой комитет увеличивает вычислительные затраты и затрудняет интерпретацию.

См. также

Примечания


Литература

  • Nilsson N. J. Learning Machines: Foundations of Trainable Pattern-Classifying Systems. — McGraw-Hill, 1965.
  • Мазуров В. Д. Комитеты систем неравенств и задача распознавания // Кибернетика. — 1971. — № 3. — С. 140–146.
  • Мазуров В. Д. Метод комитетов в задачах оптимизации и классификации. — Наука, 1990. — 248 с. — ISBN 5-02-013976-9
  • Мазуров В. Д. Модели интерпретации противоречивых данных и метод комитетов // Труды Института математики и механики УрО РАН. — 1992. — Т. 1. — С. 193–203.
  • Zhou Z.-H. Ensemble Methods: Foundations and Algorithms. — Chapman and Hall/CRC, 2012. — ISBN 978-1439830031
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BA%D0%BE%D0%BC%D0%B8%D1%82%D0%B5%D1%82%D0%BE%D0%B2»
Личные инструменты