Дерево Чоу — Лю

Метод Чоу — Лю позволяет представить совместное распределение вероятностей ${\displaystyle P(X_{1},X_{2},\ldots ,X_{n})}$ в виде произведения условных и маргинальных распределений второго порядка. Например, шестимерное распределение ${\displaystyle P(X_{1},X_{2},X_{3},X_{4},X_{5},X_{6})}$ может быть аппроксимировано следующим образом:

${\displaystyle P^{\prime }(X_{1},X_{2},X_{3},X_{4},X_{5},X_{6})=P(X_{6}|X_{5})P(X_{5}|X_{2})P(X_{4}|X_{2})P(X_{3}|X_{2})P(X_{2}|X_{1})P(X_{1}),}$

где каждый новый множитель вводит ровно одну новую переменную, а произведение может быть представлено в виде дерева зависимостей первого порядка, как показано на рисунке. Алгоритм Чоу — Лю (описан ниже) определяет, какие именно условные вероятности использовать в данной аппроксимации. В общем случае, если существуют взаимодействия третьего и более высоких порядков, аппроксимация Чоу — Лю остаётся только аппроксимацией и не может полностью воспроизвести структуру исходного распределения. Пёрл (1988) приводит современный анализ дерева Чоу — Лю как байесовской сети.

Чоу и Лю предложили метод отбора множителей второго порядка для аппроксимации, чтобы среди всех таких аппроксимаций (деревьев зависимостей первого порядка) полученная аппроксимация ${\displaystyle P^{\prime }}$ имела наименьшее расстояние Кульбака — Лейблера до реального распределения ${\displaystyle P}$ и была бы «ближайшей» с позиции информационной теории. Дивергенция Кульбака — Лейблера между аппроксимацией второго порядка и исходным распределением определяется как

${\displaystyle D(P\parallel P^{\prime })=-\sum I(X_{i};X_{j(i)})+\sum H(X_{i})-H(X_{1},X_{2},\ldots ,X_{n}),}$

где ${\displaystyle I(X_{i};X_{j(i)})}$ — взаимная информация между переменной ${\displaystyle X_{i}}$ и её родителем ${\displaystyle X_{j(i)}}$, а ${\displaystyle H(X_{1},X_{2},\ldots ,X_{n})}$ — совместная энтропия множества переменных ${\displaystyle \{X_{1},X_{2},\ldots ,X_{n}\}}$. Так как слагаемые ${\displaystyle \sum H(X_{i})}$ и ${\displaystyle H(X_{1},X_{2},\ldots ,X_{n})}$ не зависят от структуры дерева, качество аппроксимации полностью определяется суммой попарных взаимных информаций ${\displaystyle \sum I(X_{i};X_{j(i)})}$. Таким образом, если каждому ребру дерева приписать вес, равный взаимной информации между переменными в его концах, задача оптимальной аппроксимации второго порядка сводится к поиску максимального по весу дерева. Это выражение также иллюстрирует роль зависимостей: если зависимости отсутствуют и первое слагаемое отсутствует, то остаётся только аппроксимация на основе первых маргинальных распределений, а отличие между аппроксимацией и истинным распределением определяется «избыточностью», которую не удаётся учесть при предположении о независимости переменных. При включении зависимостей второго порядка удаётся учесть часть структуры и уменьшить расхождение аппроксимации с исходным распределением.

Чоу и Лю предложили простой алгоритм построения оптимального дерева: на каждом шаге алгоритм добавляет к дереву пару переменных с максимальной взаимной информацией. За подробностями см. оригинальную статью Чоу & Лю (1968). Более эффективный алгоритм для случая разреженных данных приведён в Мейла (1999).

Чоу и Вагнер позже доказали (см. Чоу & Вагнер (1973)), что обучение дерева Чоу — Лю является состоятельным, если выборки (наблюдения) получены независимо и одинаково распределёнными из распределения с древовидной структурой. Иными словами, вероятность построить ошибочное дерево стремится к нулю по мере роста объёма выборки. Главная идея доказательства — непрерывность взаимной информации по попарным маргинальным распределениям. В более поздних работах была оценена экспоненциальная скорость сходимости вероятности ошибки^[2].

Проблема, возникающая при отсутствии точной древовидной структуры второго порядка, может быть частично решена объединением плотно связанных подмножеств переменных в «узлы большего размера» для построения дерева Чоу — Лю с крупными узлами (Хуан, Кинг & Лю 2002), либо расширением жадного выбора максимальных по весу ветвей на нетривиальные структуры с несколькими родителями (Уильямсон 2000). (Похожие методы замещения и построения переменных встречаются в литературе по байесовским сетям, например, для работы с циклами (см. Пёрл (1988))

Обобщением дерева Чоу — Лю являются так называемые t-вишнёвые соединяющие деревья (англ. t-cherry junction trees). Доказано, что t-вишнёвые соединяющие деревья обеспечивают лучшую (или не хуже) аппроксимацию для дискретного многомерного распределения вероятностей по сравнению с деревом Чоу — Лю.

Третье t-вишнёвое соединяющее дерево описано в (Ковач & Сантаи 2010), а для общего ${\displaystyle k}$-го порядка см. (Сантаи & Ковач 2010). Дерево Чоу — Лю соответствует второму t-вишнёвому соединяющему дереву.