Жадные алгоритмы в машинном обучении

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

Перейти к: навигация, поиск
Статья написана с использованием LLM ChatGPT, GPT-5.6 Thinking и проверена участником Vadim Iamaletdinov 21:24, 19 июля 2026 (MSD)


Содержание

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

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

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

Основная идея

Пусть частичное решение после t шагов обозначено S_t, а множество допустимых продолжений — C(S_t). Для каждого кандидата c оценивается локальная выгода

\Delta(c\mid S_t)=Q(S_t\cup\{c\})-Q(S_t),

где Q — критерий качества. Жадный шаг выбирает кандидата

c_t=\arg\max_{c\in C(S_t)}\Delta(c\mid S_t)

и обновляет решение:

S_{t+1}=S_t\cup\{c_t\}.

Алгоритм останавливается после достижения заданного размера, исчерпания допустимых кандидатов или выполнения критерия остановки.

Эта схема может принимать разные формы. В дереве решений элементом решения является очередное разбиение вершины; при отборе признаков — новый признак; в разреженном приближении — новый элемент словаря; в бустинге — очередной базовый алгоритм.

Почему используются жадные стратегии

Во многих задачах машинного обучения требуется выбрать структуру из огромного числа вариантов. Например, для p признаков существует

2^p

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

{p\choose k}.

Даже при умеренных p и k полный перебор становится невозможным. Аналогично число возможных деревьев решений, списков правил и последовательностей базовых моделей растёт комбинаторно.

Жадный поиск уменьшает пространство вариантов: вместо сравнения всех законченных решений алгоритм сравнивает кандидатов только для следующего шага. Если на каждом из k шагов проверяется не более p кандидатов, а одна проверка стоит C, грубая оценка трудоёмкости имеет вид

O(kpC).

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

Пример локально неудачного выбора

Рассмотрим выбор двух признаков из множества \{A,B,C\}. Пусть качество отдельных признаков равно:

Набор Качество
\{A\} 9
\{B\} 8
\{C\} 7

Жадный алгоритм сначала выберет A. Предположим, что качества пар равны:

Набор Качество
\{A,B\} 10
\{A,C\} 10
\{B,C\} 20

После выбора A алгоритм может получить только качество 10, тогда как оптимальная пара \{B,C\} имеет качество 20. Причина состоит во взаимодействии признаков: B и C по отдельности уступают A, но вместе оказываются значительно полезнее.

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

Основные варианты жадного поиска

Прямой выбор

Прямой выбор начинает с пустого решения и последовательно добавляет наиболее полезные элементы:

  1. оценить всех ещё не выбранных кандидатов;
  2. добавить кандидата с наибольшим улучшением;
  3. повторять до достижения ограничения или прекращения улучшения.

Этот вариант прост и естественен, когда требуется небольшое решение из большого множества элементов.

Обратное исключение

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

Прямо-обратный поиск

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

Поиск с несколькими продолжениями

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

Стохастический жадный выбор

При большом числе кандидатов можно оценивать случайное подмножество кандидатов или использовать приближённые оценки выигрыша. Это уменьшает время работы ценой дополнительной случайности и возможной потери качества.

Построение решающих деревьев

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

Пусть в вершине находится выборка R, а разбиение создаёт подвыборки R_L и R_R. Уменьшение критерия неоднородности можно записать как

\Delta I=I(R)-\frac{|R_L|}{|R|}I(R_L)-\frac{|R_R|}{|R|}I(R_R).

Алгоритм выбирает разбиение с максимальным \Delta I. В классификации функцией I может служить энтропия или индекс Джини, в регрессии — разброс целевой переменной.

Работа Р. Куинлана 1986 года описала семейство методов индукции деревьев, использующих последовательный выбор информативных признаков.[1] Методы CART также строят дерево локальными разбиениями, а затем используют обрезку для управления сложностью.[1]

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

Отбор признаков

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

j_t=\arg\max_{j\notin S_t}Q(S_t\cup\{j\}).

После этого

S_{t+1}=S_t\cup\{j_t\}.

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

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

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

Разреженное приближение

Пусть объект y требуется приблизить линейной комбинацией небольшого числа элементов словаря d_1,\ldots,d_p:

y\approx\sum_{j\in S}\alpha_jd_j.

Matching Pursuit начинает с остатка r_0=y и на каждом шаге выбирает элемент словаря, наиболее коррелирующий с текущим остатком:

j_t=\arg\max_j|\langle d_j,r_t\rangle|.

После выбора коэффициент и остаток обновляются. В Orthogonal Matching Pursuit после добавления нового элемента коэффициенты для всего выбранного набора пересчитываются совместно методом наименьших квадратов.

Matching Pursuit был предложен как адаптивный жадный способ разложения сигналов по избыточному словарю.[1] Для Orthogonal Matching Pursuit известны условия точного восстановления разреженного сигнала по случайным измерениям.[1]

Жадное разреженное приближение применяется в сжатии сигналов, выборе словаря, разреженной регрессии и восстановлении по неполным измерениям.

Бустинг как последовательное построение модели

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

F_T(x)=F_0(x)+\sum_{t=1}^{T}\eta_t h_t(x).

На шаге t новый базовый алгоритм выбирается так, чтобы улучшить текущую композицию F_{t-1}. В градиентном бустинге базовый алгоритм приближает направление уменьшения функции потерь.

Дж. Фридман представил градиентный бустинг как жадное приближение функции в пространстве базовых алгоритмов.[1]

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

Последовательное построение правил

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

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

Преимущество таких моделей — интерпретируемость. Недостаток — раннее правило изменяет выборку, доступную следующим правилам, и может необратимо отнять у них полезные объекты.

Жадная кластеризация и выбор представителей

В задаче k-центров требуется выбрать k центров так, чтобы максимальное расстояние от объекта до ближайшего центра было как можно меньше. Алгоритм дальнего соседа начинает с произвольного центра и каждый раз добавляет объект, наиболее удалённый от уже выбранных центров:

x_t=\arg\max_x\min_{c\in S_t}d(x,c).

Для метрической задачи k-центров этот алгоритм даёт решение, радиус которого не более чем в два раза превышает оптимальный.[1]

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

Субмодулярность и гарантии

Для функции множества F субмодулярность выражает убывающую отдачу: добавление одного элемента к меньшему множеству приносит не меньший выигрыш, чем добавление к большему. Для A\subseteq B и e\notin B выполняется

F(A\cup\{e\})-F(A)\geq F(B\cup\{e\})-F(B).

Если F не убывает, субмодулярна и требуется выбрать не более k элементов, стандартный жадный алгоритм имеет гарантию

F(S_{\rm greedy})\geq(1-1/e)F(S_{\rm opt}).

Классический анализ приближённого максимизирования субмодулярных функций был дан Г. Немхаузером, Л. Уолси и М. Фишером.[1]

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

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

Когда жадный алгоритм может быть точным

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

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

Полезно различать три уровня утверждений:

  • алгоритм точен для математической оптимизационной задачи;
  • алгоритм имеет оценку приближения;
  • алгоритм является практической эвристикой без общей гарантии.

Жадное декодирование

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

y_t=\arg\max_y P(y\mid y_1,\ldots,y_{t-1},x).

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

Лучевой поиск хранит несколько частичных последовательностей и поэтому часто находит лучший итоговый вариант, но требует больше памяти и вычислений. Жадное декодирование следует отличать от жадного обучения модели: оно применяется после обучения для построения ответа.

Жадная стратегия в обучении с подкреплением

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

a_t=\arg\max_a Q(s_t,a).

Если оценки ещё неточны, постоянный жадный выбор может препятствовать исследованию среды. Поэтому применяется, например, \varepsilon-жадная стратегия: с высокой вероятностью выбирается лучшее известное действие, а с небольшой вероятностью — случайное.

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

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

Жадные алгоритмы имеют несколько практических достоинств:

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

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

Ограничения

Необратимость ранних ошибок

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

Зависимость от критерия

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

Нестабильность

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

Коррелированные кандидаты

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

Переобучение при выборе

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

Стоимость оценки кандидатов

Слово «жадный» не всегда означает «дешёвый». Если на каждом шаге требуется переобучать модель для каждого кандидата, общая стоимость может быть высокой. Применяются кеширование, ленивое обновление оценок, случайное подмножество кандидатов и параллельные вычисления.

Как проверять жадный метод

Для корректной оценки полезно:

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

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

Практический шаблон проектирования

При разработке жадного метода необходимо определить пять компонентов:

Компонент Вопрос
Частичное решение Что уже построено после нескольких шагов?
Кандидаты Какие действия допустимы на следующем шаге?
Локальный критерий Как измеряется полезность одного продолжения?
Обновление Пересчитываются ли параметры после добавления?
Остановка Когда прекращается построение?

Например, для прямого отбора признаков частичное решение — текущий набор признаков, кандидаты — ещё не выбранные признаки, локальный критерий — качество модели после добавления, обновление — переобучение модели, остановка — заданное число признаков или отсутствие улучшения.

Применения

Жадные стратегии используются:

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

Эти методы объединяет не общий тип модели, а принцип последовательного локального выбора.

История

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

В 1960–1980-х годах последовательный выбор признаков, правил и разбиений стал важной частью распознавания образов и построения деревьев. Методы CART и ID3 закрепили жадное построение деревьев в прикладном машинном обучении.[1][1]

В 1990-х годах matching pursuit развил жадное построение разреженных представлений.[1] В 2001 году градиентный бустинг был сформулирован как жадное приближение функции.[1]

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

См. также

Примечания


Литература

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B2_%D0%BC%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%BC_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B8»
Личные инструменты