4.9. АППРОКСИМАЦИЯ ДЛЯ БИНАРНОГО СЛУЧАЯ

4.9.1. РАЗЛОЖЕНИЕ РАДЕМАХЕРА — УОЛША

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

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

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

где

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

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

Нетрудно заметить, что эти полиномы удовлетворяют отношению ортогональности

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

где

Рассматривая как вероятностную функцию видим, что

Поскольку функции Радемахера — Уолша полиномы, видим, что коэффициенту являются в сущности моментами. Так что, если неизвестна, но имеется выборок коэффициенты можно оценить, вычисляя моменты выборок :

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

Теперь выражение (47) дает нам точное разложение для , и в этом случае оно не упрощает наши вычисления. Вместо оценки совместных вероятностей мы должны оценить моментов — коэффициентов Можно, однако, аппроксимировать Р(х), усекая разложение и вычисляя только моменты низкого порядка. Аппроксимация первого порядка, полученная с помощью первых членов, будет линейной относительно х. Аппроксимация второго порядка, содержащая первые членов, будет квадратичной относительно . В целом выражение (47) показывает, что для аппроксимации полиномами Радемахера — Уолша степени k требуется оценка моментов порядка k и ниже. Эти моменты можно оценить, исходя из данных, или вычислить непосредстренно из . В последнем случае тот факт, что можно суммировать сначала по переменным, не включенным в полином, говорит о том, что нужно знать только вероятности каждой переменной порядка k. Например, разложение первого порядка определяется вероятностями

где

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

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

4.9.2. РАЗЛОЖЕНИЕ БАХАДУРА — ЛАЗАРСФЕЛЬДА

Другое интересное разложение получают введением нормированных величин

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

Эти полиномы не ортогональны сами по себе, но они ортогональны, если ввести весовую функцию

т. е.

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

где

В частности, функцию можно представить в виде

где

Вспомнив, что есть произведение нормированных переменных видим, что это коэффициенты корреляции. Очевидно, что . Если определить

то можно представить соотношение (55) как

Оно известно как разложение Бахадура — Лазарсфельда . В нем содержится коэффициентов, d вероятностей первого порядка, коэффициентов корреляции второго порядка, коэффициентов корреляции третьего порядка и т. д. Естественный способ аппроксимировать — это игнорировать все корреляции свыше определенного порядка. Таким образом,

есть аппроксимация первого порядка

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

4.9.3. РАЗЛОЖЕНИЕ ЧОУ

Другой интересный класс аппроксимаций совместного распределения вероятностей основан на тождестве

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

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

Лучить, если допустить, что зависит только от k непосредственно предшествующих переменных.

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

Например, допустим, что

Тогда из (59) следует, что можно записать как Вообще мы получаем разложение В виде произведения

Подставляя 0 или 1 вместо читатель может проверить, что

где

и

Полагая подставляя (62) в соотношение (61), беря логарифм и собирая члены, получаем разложение Чоу

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

Следует сделать несколько замечаний относительно этих результатов. Во-первых, если переменные действительно независимы, мы замечаем, что и последние две суммы в разложении исчезают, оставляя уже знакомые разложения для случая с независимыми переменными. Когда зависимость имеется, мы получаем дополнительные линейные и квадратичные члены. Конечно, линейные члены можно объединить так, чтобы в разложении содержались константа, d линейных членов и квадратичных членов.

Сравнивая это разложение с разложением второго порядка Радемахера — Уолша или Бахадура — Лазерсфельда, для каждого из которых требуется квадратичных членов, видим, что преимущества данного разложения могут быть значительными. Конечно, эти преимущества можно реализовать только в том случае, если мы знаем дерево зависимости — функцию которая показывает ограниченную зависимость одной переменной от предыдущих переменных. Если дерево зависимости нельзя вывести из физической значимости переменных, то может возникнуть необходимость в вычислении всех коэффициентов корреляции просто для того, чтобы найти значимые. Однако следует заметить, что даже в этом случае может быть предпочтительнее использовать разложение так как получаемые при этом приближенные вероятности будут всегда неотрицательными и их сумма будет равна единице.