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

Когда составляющие вектора х дискретны, задача оценки плотности распределения становится задачей оценки вероятности Р(х— =Vft). По идее задача эта еще проще, нужно только считать, сколько раз наблюдается х, чтобы получить значение ѵ^, и воспользоваться законом больших чисел. Однако рассмотрим случай, когда d составляющих вектора х бинарны {имеют значения О или 1). Поскольку имеется 2“^ возможных векторов ѵ^, мы должны оценить 2“^ вероятностей, что представляет собой огромную задачу при больших значениях d, часто возникающих в работе по распознаванию образов.

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

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

где.

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

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

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

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

где

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

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

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

Теперь выражение (47) дает нам точное разложение для Р(х), и в этом случае оно не упрощает наши вычисления. Вместо оценки 2“* совместных вероятностей мы должны оценить 2“' моментов — коэффициентов йі- Можно, однако, аппроксимировать Р(х), усекая разложение и вычисляя только моменты низкого порядка. Аппроксимация первого порядка, полученная с помощью первых 1+4 членов, будет линейной относительно х. Аппроксимация второго порядка, содержащая первые l+d+d{d—l)/2 членов, будет квадратичной относительно х^). В целом выражение (47) показывает, что для аппроксимации полиномами Радемахера — Уолша степени k требуется оценка моментов порядка k и ниже. Эти моменты можно оценить, исходя из данных, или вычислить непосредстренно из Р (х). В последнем случае тот факт, что можно суммировать сначала по переменным, не включенным в полином, говорит о том, что нужно знать только вероятности каждой переменной порядка Например, разложение первого порядка определяется вероятностями =Р(Хі=1);

где

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

то можно использовать отношения ортогональноети, чтобы показать, что сумма квадратичной ошибки S (Я(х) — Р(х))* минимизируется выбором Ьі=йі. Таким образом, усеченное разложение является оптимальным в смысле среднеквадратичной ошибки. Кроме того, коль скоро в аппроксимацию входит постоянный полином фо, можно легко показать, что 2ІР~(х) = 1, что и требуется. Однако ничто не может предотвратить превращение Р(х) в отрицательную величину для некоторого х. Действительно, если фо не входит в полином, то SP (х)—О и по крайней мере одна из вероятностей должна быть отрицательной. Этого досадного результата можно избежать путем разложения log Р (х), а не Р (х), хотя в этом случае мы уже не сможем больше быть уверены в том, что суммирование полученной аппроксимации для Р{\) даст единицу.