Дерево Чау – Лю - Chow–Liu tree

Дерево зависимостей первого порядка, представляющее продукт слева.

В теории вероятностей и статистике Дерево Чау – Лю эффективный метод построения вторичногопорядок аппроксимация продукта совместное распределение вероятностей, впервые описанный в статье Чоу и Лю (1968). Цели такого разложения, как и при таком Байесовские сети в общем, может быть либо Сжатие данных или же вывод.

Представление Чоу – Лю

Метод Чоу – Лю описывает совместное распределение вероятностей ${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 (Pparallel P ^ {prime}) = - сумма I (X_ {i}; X_ {j (i)}) + сумма 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) что изучение дерева Чоу – Лю согласуется с данными выборок (или наблюдений), сделанных i.i.d. из древовидной структуры распределения. Другими словами, вероятность изучения неправильного дерева уменьшается до нуля, когда количество выборок стремится к бесконечности. Основная идея доказательства - непрерывность взаимной информации в попарном маргинальном распределении. Недавно была предоставлена экспоненциальная скорость сходимости вероятности ошибки.^[1]

Вариации на деревьях Чоу – Лю

Очевидная проблема, которая возникает, когда фактическое распределение на самом деле не является деревом зависимостей второго порядка, все же в некоторых случаях может быть решена путем объединения или агрегирования вместе плотно связанных подмножеств переменных для получения "большого узла" дерева Чоу – Лю (Хуанг и Кинг 2002 ), или путем распространения идеи жадного выбора максимального веса ветви на не-древовидные (множественные родительские) структуры (Уильямсон 2000 ). (Подобные методы подстановки и построения переменных распространены в Сеть Байеса литературу, например, для работы с петлями. Видеть Жемчуг (1988).)

Обобщения дерева Чоу – Лю - это так называемые Т-образные вишневые деревья. Доказано, что деревья t-вишни обеспечивают лучшее или, по крайней мере, такое же хорошее приближение для дискретного многомерного распределения вероятностей, как дерево Чоу – Лю. Относительно дерева t-вишни третьего порядка см.Ковач и Сантай 2010 ), для kt-вишневое дерево соединений порядка см. (Сантай и Ковач 2010 ). Дерево соединений t-вишни второго порядка на самом деле является деревом Чоу – Лю.

Смотрите также

Примечания

^ Анализ больших отклонений для изучения древовидных структур с максимальной вероятностью. В. Ю. Ф. Тан, А. Анандкумар, Л. Тонг и А. Виллски. На Международном симпозиуме по теории информации (ISIT), июль 2009 г.

Рекомендации

Chow, C.K .; Лю, К. (1968), "Аппроксимация дискретных распределений вероятностей деревьями зависимости", IEEE Transactions по теории информации, ИТ-14 (3): 462–467, CiteSeerX 10.1.1.133.9772, Дои:10.1109 / tit.1968.1054142.
Хуанг, Кайчжу; Кинг, Ирвин; Лю, Майкл Р. (2002), «Построение дерева Чоу – Лю с большим узлом на основе частых наборов элементов», в Wang, Lipo; Раджапаксе, Джагат С .; Фукусима, Кунихико; Ли, Су-Ён; Яо, Синь (ред.), Труды 9-й Международной конференции по обработке нейронной информации ({ICONIP} '02), Сингапур, стр. 498–502.
Жемчуг, Иудея (1988), Вероятностные рассуждения в интеллектуальных системах: сети правдоподобных выводов, Сан-Матео, Калифорния: Морган Кауфманн
Уильямсон, Джон (2000), "Аппроксимация дискретных распределений вероятностей байесовскими сетями", Материалы Международной конференции по искусственному интеллекту в науке и технологиях, Тасмания, стр. 16–20.
Мейла, Марина (1999), "Ускоренный алгоритм Чоу и Лю: согласование древовидных распределений с разреженными данными большой размерности", Материалы шестнадцатой международной конференции по машинному обучению, Морган Кауфманн, стр. 249–257..
Chow, C.K .; Вагнер, Т. (1973), "Непротиворечивость оценки древовидного распределения вероятностей", IEEE Transactions по теории информации, ИТ-19 (3): 369–371, Дои:10.1109 / tit.1973.1055013.
Kovács, E .; Szántai, T. (2010), "Об аппроксимации дискретного многомерного распределения вероятностей с использованием новой концепции дерева t-вишневых соединений", Конспект лекций по экономике и математическим системам, 633, Часть 1: 39–56, Дои:10.1007/978-3-642-03735-1_3, ISBN 978-3-642-03734-4.
Szántai, T .; Ковач, Э. (2010), «Гиперграфы как средство обнаружения структуры зависимости дискретного многомерного распределения вероятностей», Анналы исследований операций.

[Tan-1] Анализ больших отклонений для изучения древовидных структур с максимальной вероятностью. В. Ю. Ф. Тан, А. Анандкумар, Л. Тонг и А. Виллски. На Международном симпозиуме по теории информации (ISIT), июль 2009 г.

[1]