close

Вход

Забыли?

вход по аккаунту

?

О сложности представления пороговых функций в традиционных базисах.

код для вставкиСкачать
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
О СЛОЖНОСТИ ПРЕДСТАВЛЕНИЯ ПОРОГОВЫХ ФУНКЦИЙ
В ТРАДИЦИОННЫХ БАЗИСАХ
О.В. ШАБАНИН, ст. преподаватель объединения ТВП, канд. физ.-мат. наук
ервой работой, положившей начало разП
витию пороговой логики, послужила
статья американских ученых Маккалока и
Питтса [6], вышедшая в 1943 г. В ней была
предпринята первая попытка описания
функционирования нервной клетки – нейрона – с помощью логической функции, получившей название пороговой.
Пороговой функцией [1, 2, 7] называется булевая функция f : {0, 1}n → {0, 1}, такая, что существуют действительные числа
w1, ... ,wn, T, удовлетворяющие условию
f (x1, x2, ... , xn ) = 1 ⇔ w1x1 + ... + wn xn > T.
При этом будем говорить, что функция f имеет реализацию [w1, ... ,wn; T].
В конце 50-х гг. ХХ в. пороговые
функции привлекли внимание исследователей простотой своей технической реализации, открывавшей возможности эффективного использования в логических схемах.
60-е гг. прошлого века относятся к периоду
бурного развития пороговой логики, о которой уже говорят как о сложившейся дисциплине. К этому времени относится основное
число работ. Наиболее полную библиографию можно найти в работе Муроги [7]. На
русском языке достаточно полное изложение
пороговой логики приведено в монографиях
М. Дертоузоса [2] и Е.А. Бутакова [1].
В настоящее время интерес к данной
проблематике поддерживается рядом теоретических и прикладных проблем. Например,
одной из наиболее известных NP – полных
задач является задача о ранце:
максимизировать
n
∑ c x
i i
i = 1
n
при условии ∑ a x ≤ b ,
i i
i =1
где xi – булевые;
ci, ai, b – неотрицательные действительные числа.
152
Данные условия являются типичными в задачах линейного программирования.
Ее решение является основой в прикладных
экономических проблемах. Областью допустимых значений здесь является множество
нулей монотонной пороговой функции, и
изучение его строения может дать ответ на
проблему алгоритмической сложности решения подобных задач. Открытие принципов обучения и самообучения порогового
элемента [9] привело к зарождению и бурному развитию нового направления в вычислительной технике – нейрокомпьютерным технологиям [10]. В настоящее время
нейронные сети из пороговых элементов
имеют широкое применение в самых различных областях. Оценка взвешенной суммы является основой широкого класса прикладных задач, таких, как распознавание образов, анализ обстановки и принятие решений. Последние результаты по пороговой
логике достаточно подробно изложены в обзоре Ю.А. Зуева [3].
Необходимые сведения из пороговой
логики
Будем считать, что два вектора
(x1,..., xn) и (y1, ..., yn), xi, yi ∈ {0, 1}, i = 1, 2,..., n
связаны соотношением (x1, ..., xn) ≤ (y1, ..., yn),
если xi ≤ yi для всех i = 1, 2, ..., n; (x1, ... , xn) <
< (y1, ..., yn), xi, yi ∈ {0, 1}, i = 1, 2, ..., n, если
(x1,..., xn) ≤ (y1,..., yn), но (x1, ..., xn) ≠ (y1, ..., yn).
Функция f (x1, x2, ..., xn ) называется
монотонной, если из условия
(x1, ..., xn ) ≤ (y1, ..., yn )
следует f (x1, ..., xn ) ≤ f (у1, ..., yn).
Нижней единицей монотонной функции f (x1, ..., xn ) называется вектор (a1, ..., an ),
такой, что f (a1, ..., an ) = 1 и f (b1, ..., bn ) = 0
для любого (b1, b2, ..., bn) < (a1, ..., an).
Две функции называются однотипными, если одна может быть получена из
ЛЕСНОЙ ВЕСТНИК 1/2006
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
другой перестановкой координат и заменой
некоторых переменных на их отрицания.
Функция f (x1, x2, ..., xn) называется
обобщенно-монотонной, если существует
монотонная функция g(x1, x2, ..., xn), однотипная с функцией f (x1, x2, ..., xn). Известно,
что любая пороговая функция является
обобщенно-монотонной.
Для монотонной функции f обозначим
через Lv (f) количество нижних единиц функции f. Для обобщенно-монотонной функции g
положим Lv (g) – количество нижних единиц
монотонной функции, однотипной с функцией g. Корректность такого определения следует из предыдущего замечания.
Из определений нетрудно видеть, что
любая пороговая функция является обобщенно-монотонной. Учитывая тот факт, что для
монотонной функции нижние единицы и
только они соответствуют простым импликантам в записи дизъюнктивной нормальной
формы (д.н.ф.) [10], легко показать, что сложность д.н.ф. пороговой функции равна Lv (f).
Для двоичной функции f (x1, x2, ..., xn)
введем обозначение
f -1(1) = {(a1, a2, ..., an)∈{0, 1}n :
: f (a1, a2, ..., an) = 1}.
Целочисленный вектор
(Δ0(f), Δ1(f), ..., Δn(f))
называется характеристическим вектором
(вектором Чоу) функции f [1, 2, 6], если
Δ0(f) = 2n–1 – |f–1(1)|,
(Δ1(f), ..., Δn(f)) = Σ(а1, а2, ..., аn),
(а1, а2, ..., аn) ∈ f–1.
(1)
Суммирование векторов ведется в
действительной области.
Основное свойство, определяющее
исключительное внимание к изучению характеристического вектора в пороговой логике, состоит в следующем [1, 2, 7]:
если f(x1, x2, ..., xn) – пороговая функция, то
для любой функции
g(x1, x2, ..., xn) : g ≠ f верно
(Δ0(g), Δ1(g), ..., Δn(g)) ≠
≠ (Δ0(f), Δ1(f), ..., Δn(f)).
ЛЕСНОЙ ВЕСТНИК 1/2006
О сложности д.н.ф. пороговой
функции в «типичном» случае
Под сложностью представления произвольной булевой функции в виде дизъюнктивной нормальной формы (д.н.ф.), или
просто под сложностью д.н.ф. будем понимать число простых импликант, входящих в
запись минимальной д.н.ф. [10]. Достаточно
полный обзор результатов по теории сложности представления булевых функций в
различных базисах из функциональных элементов
можно
найти
в
работе
Р.Г. Нигматуллина «Сложность булевых
функций» [8]. Оценка сложности представления пороговых функций с помощью д.н.ф.
представляет теоретический и практический
интерес. Хорошо известен факт, что наиn
большую сложность д.н.ф., равную ⎛⎜ n 2 ⎞⎟ , в
[
⎝ ]⎠
классе пороговых функций от n переменных
имеет мажоритарная функция [6]. Большая
сложность д.н.ф. пороговых функций служит аргументом для использования в ряде
случаев пороговых представлений булевых
функций вместо представлений в виде д.н.ф.
[7]. С другой стороны, как отмечалось выше,
исследование сложности д.н.ф. пороговых
функций тесно связано с проблемой алгоритмической сложности NP – полных задач.
Поэтому отдельной задачей является оценка
сложности д.н.ф. в типичном случае. Задача
оценки сложности д.н.ф. типичной пороговой функции предложена Ю.А. Зуевым. Ее
постановку можно найти, например, в работе [3]. Наилучшая известная нижняя оценка
получена
в
работе
Ю.А. Зуева
и
Л.И. Липкина [4], где доказано, что почти у
всех пороговых функций сложность д.н.ф.
не меньше n2 / log2n. Для улучшения этой
оценки автором доказана теорема, связывающая сложность д.н.ф. Lv(f) пороговой
функции f с параметрами Чоу.
Теорема 1
Пусть f (x1, x2, ..., xn) пороговая функция с реализацией [w1, ..., wn; T],
w1 ≥ w2 ≥ ... ≥ wn ≥ 0.
153
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
Тогда для числа нижних единиц
функции f выполняется неравенство
Lv (f) ≥ Δi(f) / 2n–i
при всех i = 1, 2, ..., n.
Обозначим через P(n) число двоичных пороговых функций от n переменных.
В работе [5] показано, что при n → ∞
log 2 P ( n ) > n − n log 2 n + O ( n ) .
2
С использованием этой оценки и теоремы 1 доказан основной результат.
Теорема 2
При n → ∞ для почти всех пороговых
функций сложность д.н.ф. Lv(f) удовлетворяет неравенству
log2 Lv( f ) > n − 2 2n log2 n (1 + δ (n)) ,
где δ(n) любая функция с условиями
δ(n) = o(1) и nδ(n) → + ∞ при n → ∞.
Из того, что отрицание пороговой
функции является пороговой функцией, следует, что для сложности представления в
виде конъюнктивной нормальной формы
(к.н.ф.) будет справедлива оценка теоремы 2.
Оценка степени нелинейности
многочлена Жегалкина пороговой
функции
Многочленом Жегалкина булевой
функции f называется ее представление
формулой вида
f ( x1 ,…, xn ) = c0 ⊕ c1 x1 ⊕ … ⊕ cn xn ⊕
⊕c1,2 x1 x2 ⊕ … ⊕ ci1 ,i2 ,…,ik xi1 xi2 … xik ⊕
n + 1⎤
.
Тогда deg f ≥ ⎡
⎢⎣ 2 ⎥⎦
При этом равенство достигается, например, при n = 3 и пороговой функции
f (x1, x2, x3) = 1 ⇔ x1 + x2 + x3 ≥ 2.
Многочлен Жегалкина такой функции имеет вид: x1 x2 ⊕ x1 x3 ⊕ x2 x3.
Оценки расстояний между классами
пороговых и линейных функций
Изучению свойств классов двоичных
функций посвящено большое количество
работ. Задачи оценки расстояний между
функциями из различных классов имеют как
теоретический, так и практический интерес,
связанный с потребностями теории кодирования и прикладными вопросами идентификации функций.
Пусть f1 ( x1 ,…, xn ) и f 2 ( x1 ,…, xn )
– двоичные функции от n переменных. Обозначим
n
d ( f1 , f 2 ) = α ∈ {0,1} / f1 (α ) ≠ f 2 (α )
расстояние между функциями f1 и f 2 (расстояние Хемминга между векторами значений функций).
Для удобства расчетов введем обозначение
Δ i1 ,i2 ,…,ik ( f ) = d f , xi1 ⊕ xi2 ⊕ … ⊕ xik − 2n −1 ,
(
Δ0 ( f ) = f − 2
Наибольшая из длин конъюнкций,
входящих в его запись многочлена Жегалкина функции f, называется его степенью
deg f . Очевидно, что степени многочленов
Жегалкина однотипных функций совпадают.
Введенные выше определения можно
найти в книге С.В. Яблонского «Введение в
дискретную математику».
Теорема 3
Пусть f(x1, x2, ..., xn) – произвольная
пороговая функция, существенно зависящая
от всех переменных.
154
,
где f – число двоичных наборов, на которых
функция f принимает значение «1».
Числа Δ i1 ,i2 ,…,ik ( f ) естественным об-
⊕… ⊕ c1,2,…, n x1 x2 … xn ,
где коэффициенты ci1 ,i2 ,…,ik ∈ {0,1} .
)
n −1
разом связаны с достаточно хорошо изученными коэффициентами Радамахера – Уолша
[6, 7], определяемыми как
1
dα ( f ) = n ∑ (2 f ( x ) − 1) ⋅ [α , x ] ,
2 x
n
где
[α , x ] = ∏ (2 xi − 1)αi ,
i =1
α = (α1 ,…,α n ), x = ( x1 ,…, xn ) .
Тогда при условии
{i1 ,…, ik } = {i / αi = 1}
верно равенство
Δ i1 ,i2 ,…,ik ( f ) = 2n −1 dα ( f ) .
ЛЕСНОЙ ВЕСТНИК 1/2006
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
Обозначим
f i 0 = f ( x1 ,…, xi −1 ,0, xi +1 ,…, xn ) ,
f i1 = f ( x1 ,…, xi −1 ,1, xi +1 ,…, xn )
– подфункции функции f, зависящие от
(n – 1) переменных.
Покажем, что у обобщенно-монотонной функции существует простая связь
между ее подфункциями и расстояниями до
линейной функции от одной переменной.
Теорема 4
Булевая функция f(x1, ..., xn) является
обобщенно-монотонной тогда и только тогда, когда d f 0 , f 1 = Δ ( f ) .
(
i
i
)
i
g(x1, ..., xn) = хi, либо g(x1, ..., xn) = const.
Большинство из приведенных выше
результатов прошло апробацию на различных научных конференциях [12, 13], а также
опубликовано в виде статей [14].
Библиографический список
1.
2.
3.
4.
Теорема 5
Пусть f ( x1 , x2 ,…, xn ) – обобщенномонотонной функция. Тогда для любых
i1 , i2 ,…, ik : 1 ≤ i1 < i2 < …ik ≤ n , для любого
a ∈ {0,1} верны неравенства
при k = 2s
⎛ 2s ⎞
2n −1 − 2n − 2 s ⎜ ⎟ < d f , xi1 ⊕ xi2 ⊕ … ⊕ xi2 s ⊕ a <
⎝ s⎠
⎛ 2s ⎞
< 2 n −1 + 2 n − 2 s ⎜ ⎟ ,
⎝ s⎠
(
)
5.
6.
при k = 2s – 1
⎛ 2s − 2 ⎞
2 n −1 − 2 n − 2 s + 1 ⎜
⎟ < d f , xi1 ⊕ xi2 ⊕ … ⊕ xi2 s −1 ⊕ a <
⎝ s −1 ⎠
⎛ 2s − 2 ⎞
< 2 n −1 + 2 n − 2 s + 1 ⎜
⎟.
⎝ s −1 ⎠
(
)
Следующая теорема дает представления о связи расстояния от данной обобщенномонотонной функции до линейной функции
от одной и от нескольких переменных.
Теорема 6
Пусть f(x1, ..., xn) – обобщенно-монотонная функция.
Тогда для любых
i1 ,…, is :1 ≤ i1 < i2 < … < is ≤ n
выполняется неравенство
Δ i ,..., i ( f ) ≤ min Δ i ( f ) .
1
s
j =1,2,…, s
j
Теорема 7
Для любой пороговой функции
g(x1, ..., xn) выполняется неравенство
Δ 0 ( g ) + Δ1 ( g ) + … Δ n ( g ) ≥ 2n −1
При этом равенство достигается лишь
в случае, когда
ЛЕСНОЙ ВЕСТНИК 1/2006
7.
8.
9.
10.
11.
12.
13.
14.
Бутаков, Е.А. Методы синтеза релейных устройств из пороговых элементов / Е.А. Бутаков. –
М.: Энергия, 1970.
Дертоузос, М. Пороговая логика / М. Дертоузос.
– М.: Мир, 1967.
Зуев, Ю.А. Пороговые функции и пороговые
представления булевых функций / Ю.А. Зуев //
Математические вопоросы кибернетики. –
Вып. 5. – 1994. – С. 5–61.
Зуев, Ю.А. Регулярные булевые функции с заданной сложностью дизъюнктивных нормальных
форм / Ю.А. Зуев, Л.И. Липкин // Методы дискретного анализа в изучении булевых функций и
графов. – Вып. 48. – Новосибирск: ИМ СО АН
СССР, 1989. – С. 17–22.
Зуев, Ю.А. Комбинаторно-вероятностные и геометрические методы в пороговой логике /
Ю.А. Зуев // Дискретная математика. – Т. 3. –
Вып. 2. – 1991. – С. 47 – 57.
McCulloch, W.S., Pitts W. A logical calculus of the
ideas immanent in nevrous activity // Bulletin of Math.
Biophysics. – 1943. – V. 5. – P. 115 – 133. [Рус. пер.
Маккалок У.С., Питтс У. Логическое исчисление
идей, относящихся к нервной активности // Автоматы. – М.: ИЛ, 1956. – С. 362 – 384].
Muroga, S. Threshold logic and its applications. –
New York : Wiley, 1971. – 478 p.
Нигматуллин, Р.Г. Сложность булевых функций /
Р.Г. Нигматуллин. – М.: Наука, 1990.
Piers, W.H. Failure – Tolerant computer dezign. –
New York and London: Academic Press, 1965. [Рус.
пер.: Пирс У. Построение надежных вычислительных машин. – М.: Мир, 1968].
Уоссермен, Ф. Нейрокомпьютерная техника. Теория и практика / Ф. Уоссермен. – М.: Мир, 1992.
Яблонский, С.В. Введение в дискретную математику / С.В. Яблонский. – М.: Наука. – 1979.
Шабанин, О.В. О сложности дизъюнктивной нормальной формы пороговых функций / О.В. Шабанин // Обозрение прикладной и промышленной
математики. VI Всероссийская конференции по
стохастическим методам. Тезисы докладов. – М.:
ТВП. – Т. 6. – Вып. 1. – 1999. – С. 213–214.
Шабанин, О.В. О сложности представления пороговых функций в традиционных базисах / О.В. Шабанин // VI Всероссийская конференция «Нейрокомпьютеры и их применение»: тезисы докладов. –
М.: Изд. «Радиотехника», 2000. – С. 454–455.
Шабанин, О.В. О сложности дизъюнктивной нормальной формы пороговых функций / О.В. Шабанин // Дискретная математика. – Т. 12. – Вып. 2. –
2000. – С. 85–92.
155
Документ
Категория
Без категории
Просмотров
15
Размер файла
285 Кб
Теги
традиционная, функции, пороговых, базиса, сложности, представление
1/--страниц
Пожаловаться на содержимое документа