Об уточнении оценки веса произвольной пороговой функции

ОБ УТОЧНЕНИИ ОЦЕНКИ ВЕСА ПРОИЗВОЛЬНОЙ ПОРОГОВОЙ ФУНКЦИИ

В.Б. НЕТЫКШО, доц. каф. высшей математикиМГУЛ, канд. техн. наук

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

1 ^

О

где п - количество входных переменных, п ^<х>, приемлемая точность вычислений достигается уже при небольших п. В дальнейшем апостериорные вероятности удалось оценить с использованием геометрического подхода. Необходимо отметить, что никакие ограничения на пороговые функции при этом не накладываются. Формула оценки вероятности единичного значения пороговой функции на основе геометрического подхода была приведена без доказательства. В настоящей статье этот недостаток будет устранен.

В [3] новый метод был распространен и на булевы функции с ограниченной пороговой структурой. Оценка соответствующей вероятности также была дана без указания точности. Суммарная погрешность в худшем случае складывается из погрешностей для каждого события в отдельности. Поэтому достаточно привести доказательство точности оценки единичной вероятности для пороговой функции.

Напомним, в чем состоит сущность геометрического метода оценки вероятностей единичного (нулевого) значения произвольной пороговой функции.

Пусть пороговая функция задана следующим образом

/ f (х) = 1

а.х. > с .

а, >...>а

I И I п I

Опишем около п-мерного единичного куба Уп, на котором задана функция £ сферу 8п с центром в точке с координатами

Г1/ 1/ ^

'2'"

и радиусом

Я =

= >[п/

Очевидно, что все вершины куба Уп лежат на построенной сфере. Введем в п-мерном пространстве евклидову метрику

11а -Ь11 = -Ь)2, Определим множества

Ь е Яп

А =

х е S

I х х. х х.

для всех у = 1,2п, у Ф 7

где х, х. - точки с координатами из множества

'(0, 1}, 1,. = 1Г и множества

А=

х е S

х - х. < х - х.

для всех у = 1,2", у Ф 7 Введенные множества удовлетворяют следующим соотношениям:

2п _

и А = 5 , А п А = о и \А.\ = \А.\

1 =1

для всех 1 Фу;

2п

у\А] = 5 I, |А.| = 5 12-п

¿ш^ |ч I п I I ' I I п I

1=1

для любого 1.

Здесь |5п| - площадь поверхности сферы 5п, |А.| - площадь А.;

Площадь поверхности п-мерной сферы с радиусом

I = у[п/

равна

Я=

\5 I = k п } R"-1 = k п[/2 ] пУг 21-п.

пп

где кп - константа, зависящая от п.

Рассмотрим геометрическую модель пороговой функции. Псевдобулевое равенство задает п-мерную гиперплоскость Ь, которая разбивает п-мерный единичный куб на две части: по одну сторону от плоскости все вершины куба единич-

п

а

1=1

ные, по другую - нулевые. Если удастся вычислить площадь части сферы, расположенной по одну сторону от секущей сферу гиперплоскости, то тем самым будет с некоторой точностью оценена одна из вероятностей р{/ = 1} или р{/ = 0}.

Уравнения построенной сферы и секущей ее плоскости Ь имеют вид соответственно

V Г 112 п V

>1 г — I = — и> ах. = с .

£ I ' 2) 4 1=1 "

Произведем несколько преобразований координат [1].

1 шаг. Осуществим параллельный перенос системы координат так, что центром новой системы является точка с координатами

Г1/ V1 /2

в старой системе. Тогда в новых координатах уравнения сферы и плоскости Ь примут вид

п

Z2 " x = — и

,=, ' 4

1

Еа. I х. + — I = с ^ Е ах. = с - Е —11 = с .

1=1 V 2 / 1=1 I=1 2

Пусть без ограничения общности с' > 0. 2 шаг. Повернем систему координат в плоскости Х1ОХ2 на угол а2, косинус которого равен

а

yR

2 . 2 а, + а2

а синус равен

vfi

22 + а2

В новой системе уравнения Sn и Ь будут выглядеть следующим образом

п

2 2 а + а2

Z2 » "1 "Т" Ч2 ,

x = — и , г x + 7 ax. = c .

' Л /1 1 1 i i

1=1 4 + а22 I=з

1-й шаг. Повернем систему в плоскости Х1ОХ. на угол а , косинус которого равен

i-1 /

7 а,' N 7 а;

s=1 / V ,=1

а синус равен

Уравнения преобразуются

п п ' п

Е Х =~ и \ Е а2 Х1 + Е а;X = с' .

1=1 4 V ^=1 ^=1+1

После п-го шага получим следующие уравнения сферы и плоскости соответственно

Е2 п 2 I

х = — и . > ах = с.

1=1 ' 4 ' 1

Пересечением п-мерных сферы и гиперплоскости является (п - 1)-мерная сфера Sn_1(R'), уравнение которой в последней системе координат имеет вид

Е x2 = (о2

где

R' =

±1

п

77 а2

- радиус сферы Sn_1(R').

Ее площадь поверхности в (n _ 1)-мерном пространстве обозначим через I Sn-1(R') |.

Любая единичная вершина куба V является корнем уравнения n-мерной плоскости Lt

n

7 at xt = t > c

i=1

при некотором t > c. Оценкой вероятности p{f= 1} служит величина, равная площади поверхностей семейства (n _ 1)-мерных сфер, являющихся пересечением n-мерных сферы и плоскости L, заданной уравнением (1), для всех t > c, деленной на площадь поверхности n-мерной сферы, то есть

Р = Р {f = 1}« b b j (R cos ф)| Rdф j cosn-2 фdф

S

где

а = arcsin

Г 1 n ]

c —7 a

2 t=1

R

2

j cosn 2 фdф

b =n, R = 22

Е а

1=1 ;

Рассмотрим интегралы I и I для нечетного числа п = 2т + 1

т f 2m+1 J

i1 = 1 cos фа ф =

j

t=o V t

V 1 -

2i +1

i = j cos2m+' фаф = j (1 -12 )m at = 27I m ( 1V

t=0 V i У

2i +1

i =2

i =1

а

2

а

а

b

а

а

а

b

где

а =

1 п

с —V а.

2 1=1

Я

ь=п,Я=^

I а2

2

2

Теорема

Для вероятности р{/ = 1} верна следующая оценка

Р {Г = 1}-^

(а'-а") sup

фе[а",а']

п-2

cos ф

где

а = arcsm

| cosп 2 ф dф

Г 1 п Л

с -~1 а

21=1

^ I а;

V •=1 у

а = arcsm

Г 1 п Л

с - а1 --Е а

21=1

ЯI'

для всех п > 1.

Доказательство

Рассмотрим множество

R = <! х

ах. > с >.

Без ограничения общности считаем, что а1 > 0, с > 0.

Лемма

Если некоторая вершина Ь = (Ь1,..., Ьп) куба У принадлежит множеству Я, то любая соседняя для нее вершина Ь' = (Ь1,.,Ь. © 1,.,Ьп) принадлежит множеству

R х

I а х >с - а1 [.

Имеем Ь. © 1 = 1 - Ь.. Доказательство леммы следует из цепочки равносильностей

а,Ь + ... + а. (Ь © 1) + ... + аЬ > с - а

11 7 V 7 / п п 1

^ а.Ь +... - аЬ. +... + аЬ > с - а - а. ^

1 1 7 7 п п 1 7

^ а.Ь +... + аЬ. + ... + а Ь > с - а. - а. + 2а. Ь .

1 1 7 7 п п 1 7 7 7

Но

аЬ +. +аЬ +. + а Ь > с

1 1 7 7 п п

тогда

а.Ь +... + аЬ. + ... + а Ь > с - а - а + 2а.Ь..

1 1 7 7 п п 1 7 7 7

так как

а + а > 2а > 2а Ь..

1 1 1 11

Справедливость оценки (2) покажем с помощью математической индукции по размерности пространства п.

Обозначим через |5с| площадь поверхности части сферы, расположенной по одну сторону от плоскости Ь, которая задается уравнением

п

Еа.х = с,

/ / '

1=1

и содержащей единичные и не содержащей нулевые вершины пороговой функции £

1. Пусть п = 2. Будем предполагать, что выполняется неравенство

51

И < р . 5,1

В противном случае перейдем к рассмотрению вероятности 1 - р = р {f = 0}= р = 1}. Легко показать, что существует единственная плоскость Ь такая, при которой Ьр||Ь и

5

15

= р ,

где Ь^ задается уравнением

2

Еа.х. = -,

1 1 '

1=1

а - площадь части окружности, удовлетворяющей неравенству

2

Еа.х. > - .

1 1

1=1

Тогда, сдвигая плоскость Ь на величину -а1 и используя лемму, получим

5 I

I с-а11 >

5

>р

При этом плоскость Ьр также задает функцию £ то есть

п

f (х) = 1« I а,х > - .

Итак, для п = 2 получили двойное нера-

венство

51 5 I

с ^ с-а1

-р^- < Р —р.

5*2

2. Предположим, что для любого т < п и любой пороговой функции верна формула

15,

5Ь

т-Ч < Р < 5 5 Г

\ т\ \ т\

где Ь и Ь1 - ее порог и максимальный по модулю весовой коэффициент, соответственно. 3. Пусть т = п. Рассмотрим подфункции и £0 исходной функции £ в которой переменную с номером п зафиксируем единицей и нулем.

¡=1

Ь

2

1 =1

1=1

1=1

1=2

Эти подфункции - пороговые. Они задаются формулами

f1 (x,..., x , ) = 1 «7 a.x. > c - a и

J n \ 1 ' ' n-1 / ^J i i n

i=1

n-1

f0 (x,...,x , ) = 1 «7 a.x. > c .

J n \ 1 ' ' n-1 / ^J i i

i=1

Обозначим их единичные вероятности

через

P1 = Pifl = 1} и P» = P{fl = 1}. Для рассмотренных подфункций выполняется предположение индукции. То есть справедливы следующие двойные неравенства:

<P, и pà- <p» .

S J S . S J S .

n 1 n 1 n 1 n 1

Проведем над неравенствами (3) некоторые преобразования, получим цепочку равносильных двойных неравенств:

f

S

S

Л

1

< — 2

1

<

P = "( P1 + P» )<

S

S

с—a—a с—a

S J S

II/" Il +1 f II

К c,n к c,n « --u—u-11 <

2n

Kc—a ,n + •fc—a. ,n II nfc I L^c—a < p <--——u—< p <--—,

2n 2n 2n где f и f - пороговые функции со свойством

2n S

и

S

/'1 /"» /"1 /"» i

, f , f и f - их подфункции при

c,n ' J c,n ' j c —0;,n J c—0;,n т •/ ' r

фиксации n-й переменной значениями 1 и 0. Следовательно,

M < p <-

S

S

Тогда для оценки вероятности верна формула погрешности

|S 1 < S c—a1 Si

p \\

S S S

n 1 n \ 1 n \

a

j | Sn—1 (R cos ф)| Rd ф

a i

cos

a —a

<

j cosn 2 ф dф j cosn 2 ф dф

где

a = arcsin

r 1 n N\

c—a

2 i=1

R

\S 1 1 tl 1

n—2 P cos ф al

ф d ф

c — a1 1 n n. ai 2 1=1

Ri n Z a" i=1

, а = а1гат

п

I а

"=1 )

Доказательство окончено.

Следствие При п ^ да точность оценки (2) асимптотически совпадает с погрешностью оценки, полученной с помощью ЦПТ Линдеберга-Леви для функций 1-го и 2-го типов [2, 3], и составляет величину порядка

° Йт).

Библиографический список

1. Корн, Г. Справочник по математике для научных работников и инженеров / Г. Корн, Т. Корн. - М.: Наука, 1984.

2. Нетыкшо, В.Б. О некоторых вероятностных свойствах пороговых функций / В.Б. Нетыкшо // Нейрокомпьютеры: разработка, применение. - 2002. - № 11. - С. 48-56.

3. Нетыкшо, В.Б. Об исследовании и применении вероятностных и геометрических свойств пороговых функций / В.Б. Нетыкшо // Вестн. Моск. гос. ун-та леса - Лесной вестник. - 2003. - № 1(26). - С. 102-112.

b

b

n

2