Расшифровка пороговых и близких к ним функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Золотых, Николай Юрьевич
АВТОР
|
||||
|
доктора физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Нижний Новгород
МЕСТО ЗАЩИТЫ
|
||||
|
2013
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
ЗОЛОТЫХ Николай Юрьевич
Расшифровка пороговых и близких к ним функций
01.01.09 - Дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук
005544339
у ЯНВ 2014
Москва-2013
005544339
Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Нижегородский государственный университет им. Н. И. Лобачевского»
Научный консультант:
Шевченко Валерий Николаевич, доктор физико-математических наук, профессор, ФГБОУ ВПО «Нижегородский государственный университет им. Н. И. Лобачевского», заведующий кафедрой
Официальны еоппоненты:
Леонтьев Владимир Константинович, доктор физико-математических наук профессор, ФГБУН Вычислительный центр им. А. А. Дородницына РАН, главный научный сотрудник
Зуев Юрий Анатольевич, доктор физико-математических наук, профессор, ФГ БОУ ВПО Московский государственный университет технологий и управления им. К. Г. Разумовского, профессор
Хачай Михаил Юрьевич, доктор физико-математических наук, доцент, ФГБУН Институт математики и механики им. Н. Н. Красовского УрО РАН, заведующий отделом
Ведущая организация: ФГБУН Институт математики им. С. Л. Соболева СО РАН
Защита состоится 21 февраля 2014 г. в 11 час. 00 мин. на заседании диссертационного совета Д 501.001.44 при Московском государственном университете им. М. В. Ломоносова по адресу: 119991, ГСПТ1, Москва, Ленинские горы, МГУ, 2Тй учебный корпус, факультет ВМК, аудитория 685
С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ им. М. В. Ломоносова.
Автореферат разослан
Ученый секретарь диссертационного совета В. А. Костенко
Общая характеристика работы
Актуальность темы исследований. В целом ряде разделов математической кибернетики возникает задача восстановления (расшифровки) неизвестной дискретной функции из заданного класса с помощью последовательных вопросов о ее значении в точке. Требуется отыскать алгоритм расшифровки, использующий по возможности минимальное число вопросов о значении функции и приемлемое время для промежуточных вычислений.
Наиболее известной проблемой из этой серии является впервые рассмотренная В. К. Коробковым и Т. Л.Резником задача расшифровки монотонных булевых и многозначных функций [26, 27]. Известна сводимость к последней проблеме целого класса задач математической логики, математической экономики, целочисленного линейного программирования, теории распознавания образов.
В.Н.Шевченко рассмотрел задачу расшифровки пороговых функций А:-знач-ной логики [37-39]. Пороговые функции возникают во многих разделах математической кибернетики и дискретной математики и приложениях, например, в дискретной оптимизации [33, 39], распознавании образов [20, 21, 48], теории графов [19], при синтезе схем из функциональных элементов [29, 30, 32], нейронных сетей [42], в цифровой обработке сигналов [18, 50]. Их можно интерпретировать как характеристические функции подмножеств множества {0,1,..., к — 1}", обладающих специальным свойством «линейной отделимости». В связи с последней возможностью естественно стремление расширить их область определения. Значительный интерес имеют постановки задач, в которых функции определены на множестве М целочисленных решений заданной системы линейных неравенств. Функция, отображающая М в множество {0,1}, называется пороговой, если найдется гиперплоскость, разделяющая множества ее нулей и единиц (точек, в которых функция равна нулю или единице соответственно). К расшифровке таких функций сводятся специальные задачи теории распознавания образов с линейной разделяющей поверхностью. Большое значение задача расшифровки пороговых функций имеет в машинном обучении [48]. Другой смежной областью является связанная с большим кругом приложений теория тестов [28, 31, 34]. Таким образом, до-
статочно важным является целый ряд проблем, связанных с пороговыми функциями и их расшифровкой. Как правило, возникающие задачи — весьма сложные. Широко известной трудной проблемой, например, является оценка числа пороговых булевых функций. Для этой величины известна лишь установленная Ю.А.Зуевым [23] асимптотика ее логарифма. Асимптотика логарифма числа пороговых функций Аг-значной логики установлена А. А. Ирматовым и Ж. Д. Ковиянич [25]. Обстоятельный обзор результатов по пороговым булевым функциям и пороговым представлениям булевых функций содержится в [24].
Естественной мерой сложности алгоритма расшифровки является минимальное число вопросов, достаточное для расшифровки любой функции из заданного класса (оракульная сложность). Другой характеристикой является вычислительная трудоемкость — число операций, выполненных алгоритмом в худшем случае.
В.Н.Шевченко [38] предложил алгоритм расшифровки пороговой функции к-значной логики, имеющий при любом фиксированном п полиномиальные от 1о§ к оракульную сложность и вычислительную трудоемкость. Верхнюю оценку сложности алгоритма В.Н.Шевченко уточнил Т.Не§есШз [46], см. также [47]. В.Н.Шевченко [38] также показал, что полиномиального от и алгоритма, решающего данную задачу, не существует. Таким образом, для задачи расшифровки пороговой функции приведенные результаты заставляют ограничиться поиском алгоритмов, полиномиальных при фиксированном п. Для оценки их качества и для характеризации сложности всей задачи расшифровки пороговых функций необходимы результаты о близости предлагаемых алгоритмов к оптимальным. В частности, представляет интерес поиск нижних оценок сложности расшифровки, что приводит к исследованию структурных и мощностных свойств так называемого разрешающего множества [26] пороговой функции — такого множества точек из области определения М, значений функции в которых достаточно для однозначного восстановления функции в остальных точках. Дальнейшие результаты в этих направлениях означали бы более глубокое исследование структурных свойств и, возможно, мощностных характеристик класса пороговых функций.
До исследований автора нетривиальных нижний оценок сложности расшифровки пороговых функций (при фиксированном п и к —> <*>) известно не
было. М. Anthony, G. Brightwell, J. Shawe-Taylor [43] получили верхнюю оценку средней мощности минимального разрешающего множества пороговой функции. W. J. Bultman и W. Maass [44] исследовали сложность расшифровки пороговой функции, зависящей от двух переменных (использовалась несколько отличная терминология).
Цель работы заключается в построении эффективных алгоритмов расшифровки пороговых и близких к ним функций, определенных на множестве целочисленных решений заданной системы линейных неравенств; установлении нижних оценок сложности задачи расшифровки; анализе структурных и мощностных свойств минимального разрешающего множества пороговой функции. Особое внимание уделяется пороговым функциям Л-значной логики, зависящих от п переменных.
Методы исследований. При построении алгоритмов расшифровки использовались результаты и методы целочисленного линейного программирования, теории систем линейных неравенств, теории чисел, комбинаторики. Некоторые алгоритмы используют и развивают подходы, предложенные В.Н.Шевченко при разработке им алгоритма расшифровки пороговых функций ft-значной логики. При построении верхних и нижний оценок сложности расшифровки успешно применяются результаты о числе вершин выпуклой оболочки целочисленных решений систем линейных неравенств, полученные В.Н.Шевченко и его учениками [39]. Данный подход был применен и усовершенствован диссертантом для получения верхней оценки числа неприводимых точек политопа, что использовалось при построении неулучшаемой (по порядку при фиксированном п) верхней оценки мощности минимального разрешающего множества пороговой функции. Предложен новый подход, на основе которого получена нетривиальная нижняя оценка сложности расшифровки пороговой функции Л-значной логики.
Научная новизна. Диссертация посвящена изучению задачи расшифровки пороговых и близких к ним функций, заданных на множестве целочисленных решений системы линейных неравенств (целых точек политопа). Особое внимание уделяется важному частному случаю — пороговым функциям ¿-значной логики. Все полученные результаты являются новыми и могут быть
кратко сформулированы следующим образом:
1) Разработан алгоритм расшифровки функций, заданных на множестве целочисленных точек политопа и обладающих свойством, что множества нулей и единиц каждой такой функции можно описать системами линейных неравенств. При любой фиксированной размерности п и некоторых дополнительных ограничениях алгоритм является полиномиальным от размера линейной системы, описывающей политоп.
2) Для пороговых функций, определенных на множестве целочисленных точек политопа, предложен алгоритм расшифровки, при фиксированной размерности полиномиальный от размера задания политопа. Установлена нижняя оценка сложности этой задачи. Оракульная сложность предложенного алгоритма при фиксированном п близка по порядку к нижней оценке сложности.
3) Для пороговых функций /с-значной логики предложен алгоритм расшифровки, полиномиальный при фиксированном п. Установлена нижняя оценка сложности этой задачи. Оракульная сложность предложенного алгоритма при фиксированном п близка по порядку к нижней оценке сложности.
4) Описано строение минимального разрешающего множества пороговой функции Аг-значной логики. Найдены верхняя и нижняя оценка длины обучения в классе таких функций; при фиксированном п эти оценки совпадают по порядку.
5) Разработан алгоритм расшифровки пороговых функций Лг-значной логики, зависящих от двух переменных. Для этих функций установлен порядок сложности расшифровки, найдены точное значение длины обучения и асимптотическое значение средней мощности минимального разрешающего множества.
6) Установлена связь задачи расшифровки пороговой функции двух переменных с проблемой нахождения диофантовых приближений вещественных чисел. Предложен полиномиальный алгоритм приближения веще-
ственного числа, заданного оракулом, и полиномиальный алгоритм приближения алгебраического числа, заданного минимальным многочленом.
7) Предлагается новая модификация («графовый» тест проверки смежности экстремальных лучей) метода двойного описания построения вершинного описания полиэдра. Теоретическая оценка сложности построенной модификации и результаты экспериментов показали преимущество алгоритма по сравнению с классическим его вариантом.
Теоретическая и практическая значимость. Работа носит теоретический характер. Полученные в диссертации результаты могут быть использованы при дальнейших исследованиях пороговых функций, в частности, при изучении их структуры, числа, соотношения с другими близкими функциями и т. п. Диссертация имеет ценность для таких приложений, как дискретная оптимизация, распознавание образов, машинное обучение. Новая модификация метода двойного описания может использоваться в практических приложениях, где встречается задача построения общего решения системы линейных неравенств и двойственная к ней задача, например, в оптимизации, вычислительной физике, биоинформатике и др.
Результаты диссертации могут найти применение в исследованиях, проводимых в Московском государственном университете им. М. В. Ломоносова, ¡ Вычислительном центре им. А. А. Дородницына РАН, Институте прикладной математики им. М. В. Келдыша РАН, Институте математики им. С. JI. Соболева Сибирского отделения РАН, Нижегородском государственном университете им. Н. И. Лобачевского.
Апробация работы. Результаты диссертации докладывались и обсуждались на Международных семинарах «Дискретная математика и ее приложения» (Москва, 1995, 1998, 2001, 2004, 2007, 2012), на XVI Международной конференции «Проблемы теоретической кибернетики» (Нижний Новгород, 2011), на Международных конференциях «Математические алгоритмы» (Нижний Новгород, 1994, 1995), на Международной конференции «Алгебра и линейная оптимизация», посвященной 100-летию С.Н.Черникова (Екатеринбург, 2012) на Всероссийской конференции «Проблемы оптимизации и эко-
номические приложения» (Омск, 2006), на Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2007, 2011), на Российских конференциях «Дискретный анализ и исследование операций» (Новосибирск, 2004), «Дискретная оптимизация и исследование операций» (Алтай, 2010), на школе-семинаре «Синтез и сложность управляющих систем» (Нижний Новгород, 1994; Нижний Новгород, 2000; Пенза, 2002; Нижний Новгород, 2003), на Молодежной научной школе по дискретной математике и ее приложениям под руководством чл.-корр. РАН О. Б. Лупанова (Москва, 1997; Москва, 2000; Нижний Новгород, 2001), на заседаниях спецсеминара «Дискретная математика и математическая кибернетика» ВМК МГУ, Нижегородского семинара по дискретной математики.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Общий объем работы — 208 страниц. Список литературы содержит 167 наименований. В первой главе содержатся результаты о пороговых и близких к ним функциях, которые далее используются для построения алгоритмов расшифровки и установлении нижних оценок сложности. Во второй главе предлагаются алгоритмы расшифровки пороговых и близких к ним функций. Третья глава посвящена нижним оценкам сложности задачи расшифровки. В ней также описаны результаты о структурных и мощностных свойствах разрешающего множества пороговой функции. В четвертой главе устанавливается связь между задачей расшифровки пороговой функцией и задачей нахождения наилучшего диофантового приближения.
Публикации. По теме диссертации автором опубликовано 17 работ [117], из них 11 — в изданиях, рекомендованных ВАК [2, 3, 6, 8-10, 12-16]. Все основные результаты принадлежат автору. В работах, выполненных совместно с В. Н. Шевченко и А. Ю. Чирковым, диссертанту принадлежат формулировки и доказательства результатов, включенных в диссертацию. Диссертация продолжает исследования, начатые автором в его кандидатской диссертации [22].
Финансовая поддержка. Диссертация выполнена при финансовой поддержке РФФИ (гранты №№ 93-01-00491-а, 96-01-00639-а, 00-01-00599-а, 05-01-00552-а, 09-01-00545-а); ФЦП «Исследования и разработки по приоритет-
ным направлениям развития научно-технологического комплекса России на 2007-2013 годы», (государственный контракт №11.519.11.4015); ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы (государственные контракты №02.740.11.5131, № 14.В37.21.0393).
Краткое содержание и основные результаты
Во введении диссертации обосновывается актуальность темы, приводится обзор литературы и излагаются основные результаты.
Глава 1 посвящена изучению основных свойств пороговых и близких к ним функций, определенных в целочисленных точках политопа. В разделе 1.1 вводятся основные классы рассматриваемых функций и даются необходимые и достаточные условия принадлежности функций тому или иному из этих классов. Обозначим через У(п,1,у) множество выпуклых политопов Р С R", каждый из которых можно задать системой / линейных неравенств с целочисленными коэффициентами, ограниченными по абсолютной величине числом у; пусть !Ш(н, I, у) = {Р П Z" : Р G /, у)}. Для некоторых и > 2, I > п, у > 2 рассмотрим множество М € 9Л(и, /,у); предположим, что М £ 0. Множество всех функций, отображающих М в {0,1}, обозначим через Я(А/). Пусть Ек = {0, ...,к— 1}. Класс Я (£2) объединяет функции булевой логики, а Е'[) при к > 2 является подклассом тех функций £-значной логики, множество значений которых есть {0,1}- Для / 6 3(А/) обозначим через M0(f) и M\(f) множество нулей и единиц функции / соответственно, т.е. Mv(f) = {х 6 М : f{x) = v} (v = 0,1). Обозначим через Nv(f) = Vert Mv(f) множество вершин (крайних точек) политопа Conv My(f) (v = 0,1).
Для каждого v € {0,1} обозначим через "3V(M) множество таких функций / 6 5(А/), для которых Mv(f) можно описать в виде некоторой системы линейных неравенств Ах < а0, т. е. My(f) - {.х 6 А/ : Ах < а0}. Систему Ах < а о назовем характеристической. Обозначим через mv(f) наименьшее число неравенств в системе Ах < до, при котором возможно такое описание. Если для некоторого v е {0,1} справедливо / € "5ЛЩ и mv(f) - 1, то функция /
п
называется пороговой. Пусть для такой / неравенство 2 ajxj < "о, которое
j= i
назовем пороговым, описывает множество Mo(f). Можно считать, что aj G Z
(J = 0,1,..., и). Обозначим через 1 (М) множество всех пороговых функций, заданных на М.
В разделе 1.2 для функций из классов %{М), ЗК-^О получены
верхние оценки величины коэффициентов характеристической системы, а в разделе 1.3 — верхние оценки величин |ЛГу(/)| (v = 0,1). Также в разделе 1.3 исследуется задача построения множеств Nv(f) по заданной характеристической системе функции /.
Мощностные свойства классов Х(М), ЗоОЮ, 5i(М) изучаются в разделе 1.4. Рассмотрим класс 3v(M,m) (v = 0,1) таких функций / из 5У(М), для которых mY(f) = т. Доказано, что при у > 1, т > 1 справедлива асимптотическая оценка log |5У(Л/,от)| <; тпъ log(y \/п) (п <»). Отсюда для класса пороговых функций при у > 1 получаем log |I(Ai)| % пъ log(y фг) (п
.. Соотношения между классами %(М) и So (А/) П 3i(A/) исследуются в разделе 1.5. В частности, построены примеры, показывающие, что если к > 2 и п > 3, то Х(££) является собственным подмножеством класса Зо(-Е£) П Приведено доказательство, что если к > 3, то = 2го(Е\) П 5i(£*) (данное утверждение приведено в [39, стр. 169] без доказательства).
Раздел 1.6 посвящен задаче построения вершин и экстремальных лучей полиэдра Р = {х е R" : Ах < а0}, где А е Zmy", а0 е Zm. Эта задача возникает как вспомогательная при построении алгоритмов расшифровки пороговых и близких к ним функций, но также появляется в большом числе других приложений и представляет несомненный самостоятельный интерес. Стандартным способом она сводится к построению экстремальных лучей полиэдрального (многогранного) конуса {(х, х0) е Rn+1 : Ах < х0а0, х0 > 0}. Для решения задачи известны различные методы, один из них — хорошо известный «метод двойного описания» [49] (другие распространенные названия — алгоритм Моц-кина-Бургера [35] или алгоритм Фурье-Моцкина [40, 41]).
На каждой итерации алгоритм определяет множество всех пар смежных экстремальных лучей некоторого конуса С = {х € R" : Ах > 0}, где А е Zmxn. Пусть U — множество экстремальных лучей конуса С, |i/| = s. Обозначим Z(u) = {i: а,и = 0}, где а, — i-я строка матрицы А, и € U. Хорошо известное «комбинаторное правило» [45] проверки смежности утверждает, что для смежности лучей и и v из U необходимо и достаточно, чтобы в U не существовало
луча w, отличного от и и v, такого, что Z(u) П Z(v) С Z(w). Мы предлагаем следующую «графовую» модификацию комбинаторного теста. По конусу С построим простой граф G: множество вершин графа G есть множество U, а {и, v} образует ребро в G тогда и только тогда, когда |Z(u) Л Z(v)| > п — 1. Множество всех ребер графа G обозначим E{G). Мы доказываем, что для того, чтобы лучи и и v из U были смежны необходимо и достаточно, чтобы в U(C) не существовало луча w, отличного от и и v, такого, что {и, w} 6 E(G), {v,w} G E(G) и Z(m) П Z(v) С Z(w). Трудоемкость построения всех пар экстремальных лучей по комбинаторному правилу составляет 0(ms3), а по его «графовой» модификации 0(ms2 + msö2), где 6 равно максимуму из степеней вершин в графе G. Так как 6 < s, то трудоемкость «графового» теста всегда асимптотически не превосходит верхней оценки трудоемкости «комбинаторного». Во многих задачах i!<jh преимущество нового алгоритма более существенно. Результаты вычислительного эксперимента подтверждают это превосходство. Диссертантом предлагаются также другие модификации метода двойного описания.
Результаты первой главы диссертации опубликованы в работах [2, 8, 11].
В главе 2 предлагаются алгоритмы расшифровки пороговых и близких к ним функций. Пусть каждая функция / из некоторого класса g' С g(Ai) задана оракулом, позволяющим по произвольной точке х G М определить f(x). Под расшифровкой функции из известного класса 3' понимается задача, в которой по заданным С 6 Z'xn, с0 € Z' и заданному оракулу функции / е 3', где М = {х € Z" : Сх < Со}, необходимо найти такие точки х(2\ х^ из М, значений в которых достаточно для однозначного определения / в остальных точках из М.
Пусть sä — алгоритм расшифровки функции в классе 3'- Предположим, что при расшифровке функции / G 3' алгоритм sä обращается к оракулу в т(.с/, /) точках и выполняет ,f) операций. Оракулъной сложностью алгоритмам/ назовем величину
тл/ОО = шахф/,/). Вычислительной трудоемкостью алгоритма л/ назовем число операций, вы-
полненных алгоритмом в худшем случае:
РмОО = тахр(.с/,/).
Пусть, как обычно, М = {х е Z" : Сх < с0} € /,у), С 6 ZUn, с0 е Z', I ctj I < (' = 1.2,..., /; j = 0,1,..., и). Алгоритм si назовем полиномиальным, если функция рм{&/) ограничена некоторым полиномом от трех переменных п, I, logy. Будем говорить, что алгоритм si полиномиален при фиксированной размерности п (квазиполиномиален), если найдется многочлен р„(-, •), степень и коэффициенты которого зависят только от л, такой, что рм№) < Pn(L log у). Очевидно, < Рм№) и поэтому верхняя оценка вычислительной трудо-
емкости алгоритма является таковой и для его оракульной сложности.
Если из контекста ясно, о каком множестве М идет речь, то вместо tm(s/) и pm(s/) будем писать соответственно t(jz^) и p(sf).
Для классов Х(М), Vso(M), Si (A/), g0(Af) Л Si(Ai) от алгоритмов расшифровки будем требовать, чтобы они возвращали также коэффициенты xapaicre-ристических систем функции /. В случае пороговой функции — коэффициенты порогового неравенства.
В диссертации рассматриваются алгоритмы (условные тесты), в которых выбор точки для нового обращения к оракулу, определяется ответами на предыдущие вопросы. Что же касается алгоритмов, не учитывающих ответы на предыдущие вопросы (безусловные тесты), то для рассматриваемых классов они оказываются весьма неэффективными. Множество U С М называется безусловным тестом для класса функций 5', если для любых двух /, g из 3', f*g, найдется точка х е U, такая, что f(x) Ф g(x). В разделе 2.2 показано, что классы %(М), Ъ\(М), 5оСЮ П (М) обладают единственным безусловным тестом U = М.
В разделе 2.3 рассматривается задача расшифровки в Зо(М) П 5i(M). Вначале (в подразделе 2.3.1) строится вспомогательный оракульный алгоритм s/om, решающий задачу максимизации линейной функции на множестве Mv(f), где / € 2г1_у(М). Алгоритм siol„ для любого v £ {0,1}, любой заданной оракулом функции / 6 3?!-у{М) и любого вектора а = (ai,...,a„) 6 Z" находит
точку р = (pi, ... ,р„) е MJJ), такую, что
£üjPj = max < £ajXj : (хи...,хп) е Mv(f) I ,
j= 1 U=i J
или устанавливает, что Mv(f) = 0. При фиксированном п алгоритм имеет полиномиальную от / и log or вычислительную трудоемкость и совершает не более „Юи-i/LfJ l0g"(a + 1) (при п > 2) и не более 8 + 2 log у (при п =. I) обращений к оракулу, где а = max{y, \aj\,j = 1,..и}.
В подразделе 2.3.2 предлагается алгоритм ¡¡¿q расшифровки в классе 5i(M). Обозначим через ЩМ, К) множество таких функций / € 5o(A/)n5i(A<), для которых min {mo(f), m\(f)} < h. В классе g(M, h), где M 6 9Л(и,/,у), при любом фиксированном и алгоритм имеет полиномиальную от А, / и logy вычислительную трудоемкость р(М>) и оракульную сложность
т(^о) = о((/ + log^^^J+^y +1))
(асимптотика при фиксированном п).
Очевидно, алгоритм применим и для расшифровки функций из класса Z(M). Для последнего случая однако существует более эффективный алгоритм si\, описанный в разделе 2.4. Вначале (в подразделе 2.4.1) строится вспомогательный алгоритм si*. Обозначим через %+{М) множество тех функций из ЦМ), для которых существует пороговое неравенство с коэффициентом а0 > 0. Алгоритм sif проводит расшифровку при допущении / е Х+(М). На его основе в разделе 2.4.2 построен алгоритм st\ расшифровки в классе 1(М), для которого при фиксированном п величина р(М) ограничена полиномом от / и logy и
т(М) < 1 бл'^-'/Ш log"(y + 1) = ОJ log"(y +1)).
(асимптотика при фиксированном и). В классе при любом фиксирован-
ном п алгоритм имеет оракульную сложность
т(М) = 0(log"i).
В разделе 2.5 для расшифровки функций из класса Ч(Е\) удалось построить более эффективный алгоритм s/г- Алгоритм sit имеет полиномиальную
вычислительную трудоемкость и оракульную сложность
< 6 log(A: - 1) + 4.
В разделе 2.6 исследуется задача расшифровки пороговой функции, заданной более информативным — <<расширенным» — оракулом, который в отличие от «обычного» оракула принимает на вход произвольные точки из Q", а не только из М. Расширенный оракул связан с конкретным пороговым неравенством функции /. По заданной точке х £ Q" он возвращает 0, если пороговое неравенство выполнено, и 1 в противном случае. Под расшифровкой пороговой функции /, заданной с помощью расширенного оракула, будем понимать процедуру восстановления коэффициентов ее любого возможного порогового неравенства с помощью обращений к этому оракулу. Предложен алгоритм s/„x расшифровки функции из класса заданной с помощью расширенного
оракула, для которого вычислительная трудоемкость p(£/cxt) при фиксированном и ограничена полиномом от log k, а для оракульной сложности справедливо
и4
J&ext = — log(/i + 1) + It? \ogk (я -» °о, к -> со).
Результаты второй главы опубликованы в [1, 2, 4, 9, 12, 16].
В главе 3 устанавливаются нижние оценки сложности расшифровки пороговых функций. Под сложностью расшифровки в некотором классе g' Q ЩЩ понимается величина
r(g') = min r(.s/) = minmaxr(^/, Л, ■с/ я/ /еЗ'
где минимум берется по всем алгоритмам si расшифровки в классе g'. Множество ГСМ называется разрешающим для / в классе g', если для любой функции g € g', / Ф g, найдется по крайней мере одна точка z е Т, такая, что g(z) Ф f(z). Разрешающее множество, никакое собственное подмножество которого не является разрешающим для /, называется минимальным или тупиковым. Разрешающее множество минимальной мощности называется наименьшим. Его мощность обозначим через сr(g',/). Длиной обучения назовем величину
cr(g') = max £г(3', f) = max min f).
fetf /€3'
Справедливы неравенства r(g') > crffl), т(З') > log |g'|, являющиеся ключевыми для получения в диссертации нижних оценок сложности расшифровки. Средней мощностью минимального разрешающего множества в классе Зг' называется
I /eg-
Для класса пороговых функций Х(М) будем использовать следующие сокращенные обозначения:
T(M) = T(Z(M)), сг(М) = a(Z(M)), а(М) = а{Х(М)).
В разделе 3.2 получены некоторые вспомогательные результаты о строении конуса K(f) разделяющих функционалов функции / е %(М). K{f) описывается следующей системой линейных неравенств относительно переменных яо.^ь • • • ,ап+\'-
X ajxj < а0 j= 1
для всех (xi,...,xn)e Mo(f);
< X а1хз ^ + а„+1 для всех (*ь-..,х„)е М\(/); к ап+1 > 0.
Показано, что конус К{/) полномерный (телесный) и в важном случае АЙШт М = п — острый. Из теории линейных неравенств выводится лемма о двойственном описании конуса К(/). В частности, если АйШт М = п, то К(/) имеет единственное с точностью до положительных множителей минимальное порождающее множество (остов) •
{¿« = (6® ь« /= 1.....
В разделе 3.3 исследуется структура разрешающего множества пороговой функции. Множество Т = ТЬиГь Г„ С Му(/) (V = 0,1) является разрешающим для / 6 %{М) тогда и только тоща, когда система неравенств
1 ajxj < ай >1
для всех (xi,...,x„) е Т;
Ё ajxj >ай+ an+i для всех (xh...,x„) £ Т;
j= I
an+i>0.
описывает конус K(f). Отсюда, в частности, получаем единственность минимального разрешающего множества функции / 6 I(Af) (это обобщение известного результата о булевых пороговых функциях). Обозначим его через T(f) = Т0(Л U ТШ Ty(f) С MY(f) (у = 0,1). Имеем также Nv(f) С Гу(/) (v = 0,1) (это обобщение результата [39]).
Пусть Affdim А/ = п и / € %{М). Не нарушая общности, будем считать, что в остове конуса K(f) компонента j > 0 (i = 1,... ,{л) и , = 0 (¡' = H+l,...,s). Пусть а = (аи... ап) 6 Z",
М0(/, а) = i (уь. • ■ ,уп) 6 М: £ ajyj = max £ ajXj I, [ ;=i >=1 J
М(У, a) = < 6>i,. • • ,y„) G M : £ ajyj = min £ a,*,- I . [ j=i J
Обозначим через Nv(f, а) множество крайних точек (вершин) выпуклой оболочки множества MY(f,a). Доказано, что если Affdim М — п, тогда для любой функции / 6 X(Ai) ¡1
Т(Л = U (W. ЬЩ и Nx(f, 6(0)) = у (n0(J, а) и NX(J, a)),
i=l а
в последнем случае объединение берется по всем а = (ai, аг • • ■ > ап) £ Z" таким, что неравенство
л а
max.
является пороговым для функции /.
В разделе 3.4 на основе анализа структуры разрешающего множества, проведенного ранее, выводятся нижние оценки длины обучения в классе Х(М). Доказано, что для любых п > 2 и / > п найдется такое у0> что Для всех у > уо существует политоп Р 6 ?Р(л, /, у) такой, что при фиксированном п
т{М) > сг(М) = n(/i-n/2J log"-1 у),
где М = РГ\Z". Для класса пороговых функций Ar-значной логики установлена оценка при фиксированном п
rw > aißQ > Gl°g*-*-3-(*-l)log(*-2)r2 = 2
Kk>- ки- 4(и — 1)3"-1(и — 2)"~2((и — 2)!)
В разделе 3.5 предлагается другая характеризация минимального разрешающего множества Г(/) пороговой функции / е Х(М). Пусть £>(/) = Сопе (мй{]~) - М\(/)); если / — тождественная константа, то 2(/) — нулевой конус;
ЛоСЛ = Сопу(М0СО) + ее/), ЛгСЛ = Сопу(М,С/)) - Ш).
Доказано, что если / 6 Х(Л/), то
Гу(/) = УеПДу(/) (у = 0,1).
Отсюда получаем, что если х,у 6 Гу(/) (у = 0,1) и х Ф у, то
гх-^ЛоСЯи^СЯ (0.1).
В общем случае удобного описания множеств йу(/) (у = 0,1), которое позволило бы достаточно точно оценить | Уе11Ду(/)|, не найдено. Тем не менее, в разделе 3.6 такое описание получено для подкласса Х'(Е£) таких пороговых функций /, для каждой из которых найдется пороговое неравенство, в котором
а0 е Ъ, а} 6 2, 0 < а0 < а£к — 1)0"= 1»2.....")•
Говорят, что множество в С 2" обладает свойством разделенности, если из условий х,у е С и х Ф у следует 2х-у £ [36]. Если/ € Х'(££), то из (0.1) получаем, что каждое из множеств 7о(/) и Т\{/) обладает свойством разделенности. Далее для получения верхних оценок |7о(/)| и \Т\(/)1 используется подход [36, 39]. Доказано, что для любой функции / е Х'(££) при п > 2
\ТШ < «(1 +1о8«)(1 + %(* + 1))"~2 (у = 0,1).
В разделе 3.7 получены верхние оценки количества неприводимых точек в полиэдре (далее, в разделе 3.8, эти оценки используются для получения верхней оценки сг(^) = 0(\о^2 к) при фиксированном п > 2). Пусть Р — полиэдр в К". Точка х £ Р е V называется неприводимой в Р (а, точнее, в Р П 2"), если х нельзя представить в виде х = + г) ни для каких двух различных у и 2 из Р П 1Р. Пусть Р, Р\,Р2,...,Р* — политопы в К". Если
Р = и Ри то {Р,, Р2,...,Р5} называется покрытием политопа Р. Если пересе-¡=1
чение любых двух политопов в покрытии либо пусто, либо является их общей
гранью, то покрытие называется правильным разбиением. Если все политопы в правильном разбиении — симплексы, то разбиение называется триангуляцией. Основная идея получения верхней оценки числа неприводимых точек в политопе заключается в следующем. В подразделе 3.7.1 получена оценка количества неприводимых точек в параллелепипеде. В подразделе 3.7.2 показано, как для произвольного политопа Р построить его покрытие параллелепипедами Pi, Pi, ...,PS. Для этого сначала строится триангуляция политопа, а затем каждый симплекс триангуляции покрывается параллелепипедами. Легко видеть, что любая неприводимая в Р П Z" точка х неприводима и в Р, П Z" для любого I, если х G Л'. Это свойство позволяет в подразделе 3.7.3 оценить количество неприводимых точек в Р. А именно, доказано, что если Р можно задать системой т линейных неравенств и PnZ" С Щ, то количество неприводимых в Р П 271 точек есть log" 1 к). Заметим, что полученная оценка представ-
ляет самостоятельный интерес. В разделе 3.8 она используется для получения неулучшаемой верхней оценки длины обучения в классе пороговых функций.
В разделе 3.8, используя результаты разделов 3.6 и 3.7, мы показываем,
что
oiEl) = 0(1 og"-2 к) (к <*>).
Объединяя нижнюю и верхнюю оценки длины обучения, получаем, что при фиксированном и > 2
о-(Щ) = ©(log"-2*) (*-»«>).
В разделе 3.9 изучается задача построения минимального разрешающего множества пороговой функции / G Z(M), М = PDZ", по известным коэффициентам порогового неравенства и по известной системе, описывающей политоп Р. Для решения этой задача предлагается полиномиальная от logy и / процедура (п фиксировано). Показано, как изменить алгоритм чтобы сложность нового алгоритма отличалась бы от сложности оптимального (по числу обращений к оракулу в худшем случае) алгоритма расшифровки не более, чем в 0(пъ log(ny))
раз. Для класса сложность алгоритма si° отличается от сложности оптимального алгоритма не более, чем в 0{n2\og(nk)) раз и при фиксированном п
T(^)<r«) = 0(logn-1fc).
В разделе 3.10 рассматривается случай пороговых функций двух переменных. Из результатов предыдущих разделов вытекает
Для длины обучения в классе !(£*) в подразделе 3.10.1 установлено точное значение
ст(Е2к) = 4.
В подразделе 3.10.2 получена асимптотика среднего значения мощности минимального разрещающего множества в классе
В подразделе 3.10.3 получены следствия из этих результатов, касающиеся специальных разбиений плоскости прямыми.
Пороговые булевы функции рассматриваются в разделе 3.11. Справедливо следующее равенство: о-(Е%) = т(Е$) = = 2я. В данном разделе также показано, что сложность расшифровки в классе пороговых монотонных булевых функций совпадает со сложностью расшифровки в классе монотонных булевых функций.
В разделе 3.12 полученные результаты о верхних и нижних оценках сложности расшифровки применяются к анализу оракульной сложности задачи о рюкзаке.
Результаты третьей главы диссертации опубликованы в работах [3, 5-7, 10, 11, 14, 15, 17].
В главе 4 показана связь задачи расшифровки пороговой функции двух переменных с проблемой нахождения диофантовых приближений вещественных чисел. Рассмотрим следующую задачу. Для а 6 К, а > 0, 0 е N требуется среди всех рациональных дробей со знаменателем, не превосходящим найти наилучшее приближение ^ к а:
а-* Я
Предположим, что вещественное число а задано оракулом, позволяющим по произвольному г € (2 определить, выполняется или нет неравенство а < г.
В разделе 4.2 показано, как использовать алгоритм для решения задачи наилучшего приближения к заданному таким образом числу. Время работы построенной процедуры ограничено полиномом от log А:, где к = шах {О, \aQ~\}. В разделе 4.3 на основе полученных результатов строится полиномиальный алгоритм нахождения наилучших приближений алгебраических вещественных чисел, заданных минимальным многочленом.
Результаты четвертой главы диссертации опубликованы в работе [13].
В заключении обсуждаются основные результаты диссертации
Список публикаций
1. Золотых Н. Ю. Алгоритм расшифровки пороговой функции fc-значной логики на плоскости с числом обращений к оракулу O(Iogzt) // Труды Первой Международной конференции «Математические алгоритмы».— Н.Новгород: Издательство Нижегород. гос. ун-та, 1995. —С. 21-26.
2. Золотых Н. Ю. О пороговых и близких к ним функциях, определенных в целочисленных точках политопа // Дискретный анализ и исследование операций. Серия 1. - 1998. — Т. 5, № 2. — С. 40-54.
3. Золотых Н. Ю. Оракульная сложность задачи о рюкзаке // Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Математическое моделирование и оптимальное управление. — 2000, — № 1, — С. 84-87.
4. Золотых Н. Ю. Пороговые функции, зависящие от двух переменных: сложность расшифровки и мощность разрешающего множества // Материалы четвертой молодежной научной школы по дискретной математике и ее приложениям. — М.: Издательство механико-матем. факультета МГУ, 2000. — С. 48-54.
5. Золотых Н. Ю. О сложности расшифровки пороговых функций, зависящих от двух переменных // Материалы XI Межгосударственной школы-семинара «Синтез и сложность управляющих систем». Часть I. — М.: Издательство Центра прикладных исследований при механико-математическом ф-те МГУ, 2001,- С. 74-79.
6. Золотых Н. Ю. О сложности решения одного класса задач целочисленного линейного программирования // Дискретный анализ и исследование операций. Серия 2. - 2003. - Т. 10, № 1. - С. 3-10.
7. Золотых Н. Ю. Оценки мощности минимального разрешающего множества пороговой функции многозначной логики // Математические вопросы кибернетики. Вып. 17, — М.: Физматлит, 2008. — С. 159-168.
8. Золотых Н. Ю. Новая модификация метода двойного описания для построения остова многогранного конуса // Журнал вычислительной математики и математической физики. — 2012,— Т. 52, № 1.— С. 153-163.
9. Золотых Н. Ю. Расшифровка пороговой функции, заданной расширенным оракулом // Вестник Нижегородского университета им.Н.И.Лобачевского. - 2012.- № 3,- С. 175-178.
10. Золотых Н. Ю., Чирков А. Ю. О верхней оценке мощности минимального разрешающего множества пороговой функции // Дискретный анализ и исследование операций. — 2012. — Т. 19, № 5. — С. 35-46.
11. Золотых Н. Ю., Чирков А. Ю. Сложность расшифровки пороговых функций многозначной логики // Материалы XI Международного семинара «Дискретная математика и ее приложения», посвященного 80-летию со дня рождения академика О. Б. Лупанова (18—23 июня 2012 г.). — М.: Издательство механико-матем. факультета МГУ, 2012. — С. 63-77.
12. Золотых Н. Ю„ Шевченко В. Н. Расшифровка пороговых функций ¿-значной логики // Дискретный анализ и исследование операций.— 1995. — Т. 2, № 3. — С. 18-23.
13. Золотых Н. Ю., Шевченко В. Н. Расшифровка пороговых функций и диофантовы приближения // Вестник Нижегородского университета им.Н.И.Лобачевского. Серия: Математическое моделирование и оптимальное управление, — 1998.— № 1,— С. 199-207.
14. Золотых Н. Ю„ Шевченко В. Н. Об оценке сложности расшифровки поро-
говых функций ¿-значной логики // Журнал вычислительной математики и математической физики, — 1999,— Т. 39, № 2.— С. 346-352.
15. Шевченко В. //., Золотых Н. Ю. О сложности расшифровки пороговых функций fc-значной логики // Доклады РАН,— 1998.— Т. 362, № 5.— С. 606-608.
16. Shevchenko V. N., Zolotykh N. Y. Decoding of threshold functions defined on the integer points of a polytope // Pattern recognition and image analysis. — 1997. - V. 7, N. 2. - P. 235-240.
17. Shevchenko V. N„ Zolotykh N. К Lower bounds for the complexity of learning half-spaces with membership queries // Lecture Notes in Computer Science. V. 1501,- Springer-Verlag, 1998,- P. 61-71.
Цитированная литература
18. Арханге.1ьский С. В. Информационный анализ цифровых сигналов. — Самара: Издательство Саратовского университета, Самарский филиал, 1991.
19. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. — М.: Наука, 1990.
20. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. Вып. 33.— М.: Наука, 1978.-С. 5-68.
21. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999.
22. Золотых Н. Ю. Расшифровка пороговых и близких к ним функций многозначной логики: Дис. ... канд. физ.-матем. наук / Нижегородский гос. университет им. Н.И.Лобачевского. — Нижний Новгород, 1998.
23. Зуев Ю. А. Асимптотика логарифма числа пороговых функций алгебры логики // Доклады АН СССР. - 1989. - Т. 306, № 3. - С. 528-530.
24. Зуев Ю. А. Пороговые функции и пороговые представления булевых функций // Математические вопросы кибернетики. Вып. 5. — М.: Физматлит, 1994,-С. 5-61.
25. Ирматов А. А., Ковиянич Ж. Д. Об асимптотике логарифма числа пороговых функций А>значной логики // Дискретная математика. — 1998. — Т. 10, № 3,- С. 35-56.
26. Коробков В. К. Оценка числа монотонных функций алгебры логики и сложности алгоритма отыскания разрешающего множества для произвольной монотонной функции алгебры логики // Доклады Академии Наук СССР. — 1963. - Т. 150, № 4. - С. 744-747.
27. Коробков В. К, Резник Т. Л. О некоторых алгоритмах вычисления монотонных функций алгебры логики // Доклады Академии Наук СССР. — 1962,- Т. 147, № 5,- С. 1022-1025.
28. Кудрявцев В. Б. Теория тестового распознавания // Дискретная математика. - 2006. - Т. 18, № 3. — С. 3-34.
29. Лупанов О. Б. О возможности синтеза схем из произвольных элементов // Труды математического института им. В. А.Стеклова. Т. 51.— М.: АН СССР, 1958.-С. 158-173.
30. Лупанов О. Б. О синтезе схем из пороговых элементов // Проблемы кибернетики. Вып. 26. - М.: Наука, 1973. - С. 109-140.
31. Мошков М. Ю. Условные тесты // Проблемы кибернетики. Вып. 40. — М.: Наука, 1983.-С. 131-170.
32. Нечипорук Э. И. О синтезе схем из пороговых элементов // Проблемы кибернетики. Вып. 11.— М.: Наука, 1964, — С. 49-62.
33. Схрейвер А. Теория линейного и целочисленного программирования. В 2-х тт. — М.: Мир, 1991.
34. Чегис И. А., Яблонский С. В. Логические способы контроля работы электрических схем // Труды Матем. Института АН СССР,— 1958,— Т. 51,— С. 270-360.
35. Черников С. Н. Линейные неравенства. — М.: Наука, 1968.
36. Шевченко В. Н. О числе крайних точек в целочисленном программировании //Кибернетика, — 1981, —№ 2,— С. 133-134.
37. Шевченко В. Н. О некоторых функциях многозначной логики, связанных с целочисленным программированием // Методы дискретного анализа в теории графов и схем. Вып. 42. — Новосибирск: Институт матем. СО АН СССР, 1985.- С. 99-108.
38. Шевченко В. Н. О расшифровке пороговых функции многозначной логики // Комбинаторно-алгебраические методы в прикладной математике. — Горький: Издательство Горьковского университета, 1987. — С. 155-163.
39. Шевченко В. Н. Качественные вопросы целочисленного программирования. — М.: Физматлит, 1995.
40. Шевченко В. Н. Триангуляции выпуклых многогранников и их булевы функции // Математические вопросы кибернетики. Вып. 16.— М.: Физматлит, 2007. - С. 43-56.
41. Шевченко В. Н., Груздев Д. В. Модификация алгоритма Фурье-Моцкина для построения триангуляции // Дискретный анализ и исследование операций. Серия 2. - 2003. - Т. 10, № 10. - С. 53-64.
42. Anthony М., Bartlett Р. L. Neural network learning: theoretical foundations.— Cambridge: Cambridge Univesity Press, 1999.
43. Anthony M., Brightwell G., Shawe-Taylor J. On specifying boolean functions by labelled examples // Discrete Applied Mathematics. — 1995. — V. 61, N. 1. — P. 1-25.
44. Bultman W. J., Maass W. Fast identification of geometric objects with membership queries // Information and Computation.— 1995.— V. 118, N. 1,— P. 48-64.
45. Burger E. Über homogene lineare Ungleichungssysteme // Zeitschrift fur Angewandte Mathematik und Mechanik. - 1956.- V. 36, N. 3/4.- P. 135-139.
46. Hegediis T. Geometrical concept learning and convex polytopes // Proc. 7 annual conf. on Computational learning theory (COLT'94). — New York: ACM Press, 1994,-P. 228-236.
47. Hegediis T. Generalized teaching dimensions and the query complexity of learning II Proc. 8 annual conf. on Computational learning theory (COLT'95). — New York: ACM Press, 1995,- P. 108-117.
48. Mitchell T. Machine Learning.— McGraw-Hill Science/Engineering/Math, 1997.
49. Motzkin Т., RaiffaH., Thompson G„ Thrall R. The double description method// Contributions to Theory of Games / Ed. by H. Kuhn, A.W.Tucker. — Princeton,
RI: Princeton University Press, 1953. — V. 2. - P. 51-73. — [Рус. пер.: Моцкин Т. С., Райфа X, Томпсон Дж. Л., Тролл Р. М. Метод двойного описания // Матричные игры / Под ред. Н. Н. Воробьева. — М.: Физматгиз, 1961].
50. Widrow В., LehrM. A. Adaptive signal processing. — Englewood-Cliffs, N. J.: Prentice-Hall, 1985.
Формат 60x84 1/16. Бумага офсетная. Печать цифровая. Усл. печ. л. 1. Тираж 100 экз. Заказ №06/1201
Нижегородский государственный университет им. Н.И. Лобачевского
На правах рукописи
05201450550
ЗОЛОТЫХ Николай Юрьевич
Расшифровка пороговых и близких к ним функций
01.01.09 - Дискретная математика и математическая кибернетика
ДИССЕРТАЦИЯ на соискание ученой степени доктора физико-математических наук
Научный консультант д. ф.-м. н., проф. Шевченко В. Н.
Нижний Новгород - 2013
Содержание
Список обозначений 5
Введение 10
Глава 1. Свойства пороговых и близких к ним функций 32
1.1. Определения исследуемых классов функций ..............32
1.2. Величина коэффициентов характеристической системы . 35
1.3. Число вершин в РоС/) и ................................38
1.4. Мощностные свойства исследуемых классов функций . . 44
1.5. Соотношение между классами %{М) и ^о(М) П <$\(М) . . 47
1.6. Построение двойственного описания полиэдра............53
1.6.1. Введение..............................................54
1.6.2. Определения и предварительные сведения .... 58
1.6.3. Метод двойного описания ..........................60
1.6.4. Порядок добавления неравенств....................62
1.6.5. Методы проверки смежности экстремальных лучей 64
1.6.6. Уменьшение количества рассматриваемых пар смежных лучей ......................................68
1.6.7. Вычислительный эксперимент......................69
Глава 2. Алгоритмы расшифровки пороговых и близких к ним
функций 74
2.1. Постановка задачи............................................74
2.2. Безусловные тесты для пороговых функций................78
2.3. Расшифровка функций в классе П ЗгКМ)............79
2.3.1. Оракульный алгоритм максимизация
линейной функции ..................................80
2.3.2. Алгоритм расшифровки в классе П . 83
2.4. Расшифровка пороговых функций ..........................87
2.4.1. Расшифровка функций из класса %+{М) ..........88
2.4.2. Расшифровка функций из класса %{М)............95
2.4.3. Модификация алгоритма............................97
2.5. Расшифровка пороговых функций двух переменных ... 99
2.6. Расшифровка пороговых функций, заданных расширенным оракулом...................107
Глава 3. Нижние оценки сложности расшифровки 113
3.1. Введение............................113
3.2. Свойства конуса разделяющих функционалов.......117
3.3. Структура разрешающего множества пороговой функции 120
3.4. Оценки длины обучения в классе пороговых функций . . 125
3.5. Другая характеризация минимального разрешающего множества пороговой функции...............131
3.6. Верхняя оценка мощности минимального разрешающего множества для одного подкласса пороговых функций . . 136
3.7. Неприводимые целочисленные точки политопов.....140
3.7.1. Неприводимые точки в параллелепипеде.....141
3.7.2. Покрытие политопа параллелепипедами.....144
3.7.3. Неприводимые точки в политопе.........148
3.8. Верхние оценки длины обучения в классе пороговых функций............................150
3.9. Построение минимального разрешающего множества пороговой функции......................153
3.10. Минимальное разрешающее множество пороговой функции двух переменных..................156
3.10.1. Мощность разрешающего множества.......157
3.10.2. Среднее значение мощности минимального разрешающего множества пороговой функции
двух переменных ..................162
3.10.3. Свойства специальных разбиений плоскости прямыми.......................167
3.11. Сложность расшифровки пороговых булевых функций . . 170
3.12. Оракульная сложность задачи о рюкзаке..........171
Глава 4. Расшифровка пороговых функций и диофантовы
приближения 174
4.1. Диофантовы приближения вещественных чисел .....174
4.2. Связь задачи расшифровки с задачей приближения .... 177
4.3. Диофантовы приближения алгебраических чисел.....182
Заключение 184
Литература 188
Список обозначений
N — множество натуральных чисел; Z — кольцо целых чисел; Q — поле рациональных чисел; R — поле вещественных чисел; Ек = {0.1.....Аг— 1>;
X" — множество «-мерных арифметических векторов (рассматриваемых как строчки или как столбцы) с компонентами из X;
Хпхт — множество матриц размером п х т с элементами из X;
|_orJ — целая часть числа а (наибольшее целое, не превосходящее а);
[а] — минимальное целое число, не меньшее а;
loga — логарифм а по основанию 2;
— длина двоичного разложения рационального числа м? = где
и е v е № (и;) = 1 + ["ьисм + 1)] + [~1о§(у + 1)];
(Ь) — длина двоичного разложения вектора Ь - {¡3\,...,рп) £ О":
AffdimX — аффинная размерность множества X С К.";
СопуХ — выпуклая оболочка векторов множества ХСР;
СопеХ — коническая оболочка векторов множества 1С I" (множество всех линейных комбинаций с неотрицательными коэффициентами);
VolX -
я-мерный объем области X с К.";
Arca X — площадь плоской фигуры Ici2;
VcrtX — множество вершин области ConvX;
áQtA — определитель квадратной матрицы A; det(öi, ■ ■ -, ап) — определитель матрицы, составленной из столбцов а\,а2,..., ап\
р(а, ао) = {xG s" : ах < üq] — полиэдр в пространстве $п, где f — подполе поля R, А Е $Ып, ао Е см. стр. 32;
м(а, а0) = р(а, а0) П Z"; см. стр. 32;
N(A, ао) - Vert Conv М(А, ао); см. стр. 33;
^(и, /, у) — множество политопов р С ш", каждый из которых можно задать системой / линейных неравенств с целочисленными коэффициентами, ограниченными по модулю величиной у; см. стр. 33;
ЯП(л, /, у) = {Р П Z" : Р Е Щп, I, у)}; см. стр. 33;
%{М) — множество всех функций / : M —> {0,1}, M G Ш(п,1,у); см. стр. 33;
в частности, — множество всех булевых функций п пере-
менных;
МАЛ = {х £ M : f{x) = v}5 / Е (у = 0,1); см. стр. 33;
Pyif) = Conv My(f) (v = 0,1); см. стр. 33;
Nv(f) = Vert Pv(f) (у = 0,1); см. стр. 34;
K(f) — конус разделяющих функционалов пороговой функции / Е £(Л/); см. стр. 35;
0СО = Сопе(М)00 -Мх00); см.стр. 131; ДоСЯ = РоОО + еСО;см.стр.131; ^100 - ЛОО-бСО; см.стр. 131;
— множество функций / из Зг(М), для каждой из которых множество Му(/) можно описать некоторой системой линейных неравенств (у = 0,1); см. стр. 33;
х(п,у) = (л + 1)^(у \/я)"2; см. стр. 37;
£(#1,/и) = Г[|Ь') + Г^-1); см.стр.38;
— множество пороговых функций, заданных на М\ см. стр. 35;
в частности, %{Е— множество булевых пороговых функций п переменных;
Щу{/) — пороговое у-число функции / € (V = 0,1); см. стр. 34;
5У(М,И) — множество тех функций / 6 <$У(М), для которых ту(/) = Н (у = 0,1); см.стр.45;
ЩМ,И) — множество таких / е п З^С^Х что min {то(/), т\(/)} <
/г; см. стр. 76;
/) — количество обращений к оракулу при расшифровке алгоритмом функции /; см.стр.74;
т= тах /) — оракульная сложность алгоритма где Я.
/еЯ'
ЩМ); если М ясно из контекста, то вместо иногда ис-
пользуется т(<£/); см.стр.75;
р(з/,/) — количество операций при расшифровке алгоритмом л/ функции /; см. стр. 74;
Рм(^) = такрШ, Л — вычислительная трудоемкость алгоритма я?, где ^ если М ясно из контекста, то вместо рм№) иногда
используется см. стр. 74;
т(3') = тттм(й/) — оракульная сложность расшифровки функции в классе см. стр. 113;
~~ мощность наименьшего разрешающего множества функции / относительно класса 5'; см. стр. 113;
сг(50 = тахсг(5',/) — длина обучения в классе 5'; см. стр. 113;
/65'
1
= - X <^(5'5 /) — средняя мощность минимального разрешающего множества в см. стр. 114; т(М) = т(Х(М)); <г(Л = сг{%(М), /); сг(М) = о-(Х(Щ; а{М) = а{%{М))\ см.стр. 115;
— минимальное разрешающее множество для / Е £(М); см. стр. 121; Ту(Л = ГС/) П МУСЛ (у = 0,1); см. стр. 121;
© 1 — задача построения множеств крайних точек А^С/) и всех неравенств-граней политопа Ру{/) для функции / Е см. стр. 44;
©2 — задача построения минимального разрешающего множества Т(/) для функции / Е см. стр. 153;
£¿0 — алгоритм расшифровки в классе ^о(Л^) П %\{М)\ см. стр. 84;
8
— алгоритм расшифровки в классе 2(М); см. стр. 95;
— вспомогательный алгоритм при построении \ см. стр. 91;
— модификация алгоритма \ см.стр.97;
— модификация алгоритма см. стр. 154;
¿^г — алгоритм расшифровки в классе %{ЕР х Eq)\ см. стр. 104; srf' — алгоритм расшифровки в классе [Ю4]; см. стр. 79;
srf" — алгоритм расшифровки в классе [139]; см. стр. 96;
«й^хt — алгоритма расшифровки пороговой функции, заданной расширенным оракулом; см. стр. 109;
^опт — оракульный алгоритм максимизации линейной функции на множестве Mv(f), где / G {$ri_v(A/); см. стр. 81;
DDM — «метод двойного описания» — алгоритм построения множества всех экстремальных лучей полиэдрального (многогранного) конуса [153]; см. стр. 60;
DDM.M1 — модификация алгоритма DDM; см. стр. 62;
Graph. Adj — «графовая модификация» комбинаторного теста проверки смежности экстремальных лучей; см. стр. 67;
I — конец доказательства.
Другие обозначения вводятся в тексте.
Если вектор умножается слева на матрицу, он считается столбцом, если справа — строкой. Равенства и неравенства между векторами понимаются в координатном смысле.
Введение
В работе исследуется задача расшифровки функций, определенных на множестве целочисленных решений заданной системы линейных неравенств и обладающих определенными свойствами линейной отделимости. В частности, с этой точки зрения изучается класс пороговых функций Аг-значной логики, принимающих значения 0,1.
Очевидно, что в общем случае для однозначного определения функции, определенной на конечном множестве М и принимающей значения 0,1, необходимо знать ее значения во всех точках области определения. Если же функция принадлежит классу более узкому, чем множество всех таких функций, то для однозначного определения ее значений во всех точках М иногда достаточно знать значения лишь на некотором его подмножестве. Задача расшифровки в классе ставится следующим образом. С помощью вопросов о значении неизвестной функции / требуется определить f(x) для всех х из множества Т С М, которое бы позволило определить f(x) для остальных точек области определения М. Предполагается, что выбор очередного вопроса определяется ответами на предыдущие. Таким образом, мы имеем дело с «черным ящиком», реализующим функцию из Требуется определить, какую именно функцию он реализует.
Естественной мерой сложности алгоритмов расшифровки служит число вопросов, которые приходится задавать в худшем случае. Алгоритм минимальной сложности, решающий поставленную задачу для класса назовем оптимальным. Сложность оптимального алгоритма назовем сложностью расшифровки в классе
Впервые исследуемая задача рассматривалась В. К. Коробковым и Т. JI. Резником [47, 49, 51] для класса монотонных булевых функций. По-
строив специальный алгоритм и доказав его оптимальность, Ж. Ансель [134] окончательно установил сложность расшифровки таких функций. Н.А.Соколов [79] для поставленной задачи дал алгоритм, являющийся оптимальным как по числу вопросов, так и по требуемой памяти. Расшифровка монотонных многозначных и конечнозначных функций рассматривалась В.К.Коробковым, В.Б.Алексеевым, Н.А.Соколовым,
A. В. Сержантовым, А. А. Сапоженко, М. В. Горяиновым [2, 14, 48, 73, 74, 78] и др. Близкая задача поиска максимального верхнего нуля монотонной функции рассматривалась в работах [43-45, 70, 76, 77]; см. также [50, 75, 80]. Другие сведения о монотонных функциях и задаче расшифровки монотонных функций приведены в обзоре А. Д. Коршунова [54]. Задачам расшифровки в различных классах функций посвящены многочисленные работы; упомянем [13, 65, 66, 98, 99].
Задача расшифровки пороговой функции впервые была поставлена
B.Н.Шевченко [104]. Пороговые функции возникают во многих разделах математической кибернетики и дискретной математики и приложениях, например, в дискретной оптимизации [81, 105], распознавании образов [19, 20, 152], теории графов [18], при синтезе схем из функциональных элементов [57, 58, 64], нейронных сетей [83, 116], в цифровой обработке сигналов [3, 4, 163], машинном обучении [125, 152]. Обстоятельный обзор результатов по пороговым булевым функциям и пороговым представлениям булевых функций содержится в [39].
Пороговой функцией £-значной логики называется такое отображение / гиперкуба Е'£ = {0, 1,... ,к - 1}" в множество {0,1}, что существует гиперплоскость, разделяющая множества нулей и единиц функции (точек, в которых /(х) равна 0 или 1 соответственно). В [104] было показано, что для однозначного задания такой функции достаточно знать ее значения в вершинах выпуклых оболочек множеств нулей и
единиц. Установленная В.Н.Шевченко [103] оценка числа этих вершин позволила в [104] построить алгоритм расшифровки пороговой функции, сложность которого при любом фиксированном числе переменных п ограничена некоторым полиномом от log к. Этот алгоритм опирается на процедуру, предложенную В.Н.Шевченко [102] нахождения вершин выпуклой оболочки множества целочисленных решений системы линейных неравенств. В свою очередь эта процедура использует алгоритм Лснстры (Н. W. Lenstra) [147] решения таких систем. Данный подход оказался достаточно эффективным и развивался в работах [107, 138] и др. Улучшение верхних оценок сложности алгоритмов расшифровки пороговых функций происходило в этих работах за счет уточнения [10, 95, 97, 102, 105, 127] верхних оценок числа крайних точек. Хегедус (Т. Hegediis) [138] показал, что сложность алгоритма В. Н. Шевченко при фиксированном п есть к). Дальнейший прогресс на этом
пути, по-видимому, не возможен, так как установленная в [127] оценка не улучшаема но порядку [8, 94, 119].
Близкие вопросы рассматриваются в [121, 122, 131, 145, 149, 150] и
др.
Основной из известных ранее результатов о нижней оценке сложности расшифровки пороговой функции А'-значной логики — о невозможности построения алгоритма расшифровки полиномиальной от п сложности [104]. Это заставляет, с одной стороны, искать алгоритмы полиномиальной при фиксированном п сложности (так называемые квазиполиномиальные алгоритмы), а, с другой стороны, пытаться установить более точные нижние оценки, явным образом включающие параметр к. Диссертантом получены результаты в обоих направлениях. С одной стороны, предлагается алгоритм расшифровки, сложность которого при фиксированном п > 2 есть <9(log"~' к). С другой стороны, получена ниж-
няя оценка сложности этой задачи Q(\og"~2 к).
Нижняя оценка получена на основе анализа структуры и мощности так называемого разрешающего множества [49, 51] пороговой функции — такого множества точек области определения, значений в которых достаточно для однозначного восстановления / в остальных точках, т.е. для однозначной идентификации /. Максимальное значение мощности минимального разрешающего множества (где максимум берется по всем функциям из класса 50 длиной обучения (teaching dimension [132]) в классе На основе результатов [104, 127] в [138] показано, что длина обучения в классе пороговых функции ^-значной логики при фиксированном п есть 0(log'!_1 к). Диссертантом предложена новая характери-зация минимального разрешающего множества и на этой основе при фиксированном п установлена оценка длины обучения ©(log"-1 к). Для п - 2 длина обучения равна 4.
В [117] исследуется среднее значение мощности минимального разрешающего множества. Установлено, что мощность минимального разрешающего множества булевой пороговой функции в среднем не превосходит п2. Этот результат может быть обобщен [12] на случай &-значной логики. В этом случае справедлива верхняя оценка л2 log к. Для п = 2 среднее значение мощности минимального разрешающего множества асимптотически равно
Дальнейшие исследования разрешающих множеств пороговых функций, возможно, позволят получить новые результаты, касающиеся мощ-ностных свойств класса пороговых функций &-значной логики.
Заметим, что задача оценки числа дискретных функций различных классов, как правило, является весьма сложной. Задача оценки мощности пороговых булевых функций исследуется с середины 1960-х гг. Верхняя оценка получается из классического результата JT. Шлёфли [14] о чис-
ле открытых областей, получаемых при разбиении /г-мерного пространства гиперплоскостями. С.Яджима и Т. Ибараки [166] получили первую нетривиальную нижнюю оценку. Асимптотика логарифма числа пороговых функций была установлена только в 1989 г. Ю.А.Зуевым [37, 38]. При этом использовался один комбинаторно-вероятностный результат о ±1-матрицах, полученный А. М. Одлыжко [157]. Другой подход к получению асимптотики логарифма числа пороговых функций, также использующий лемму Одлыжко, предложил А. А. Ирматов [40]. Асимптотика самого числа пороговых функций до сих пор не известна. Обстоятельный обзор результатов по пороговым булевым функциям и пороговым представлениям булевых функций содержится в [39]. Мощность множества пороговых функций /хзначной логики исследовалась в [103, 105]. Асимптотика логарифма числа пороговых функций Аг-значной логики установлена А. А. Ирматовым и Ж. Д. Ковиянич [42].
Другим примером может служить проблема Дедекинда — оценка числа монотонных булевых функций, как известно, сильно связанная с задачей расшифровки в этом классе [49, 134]. В. К. Коробковым [49], а также Ж. Анселем [134] найден порядок логарифма числа этих функций. Д. Клейтмен [143] установил асимптотику логарифма количества монотонных булевых, В.Б.Алексеев [1] — монотонных £-значных функций. Асимптотика числа монотонных булевых функций найдена Д.А.Коршуновым [52, 53]. Компактно этот результат изложил А. А. Сапоженко [71]; см. также [54, 72].
Ранее задача расшифровки пороговых функций рассматривалась лишь для случая булевых, многозначных или конечнозначных логик. Постановка задачи, в которой функции определены на множестве целочисленных решений системы линейных неравенств (в целочисленных точках некоторого политопа Р), является новой. В этом случае функция
/ : М = Р П —> {О, 1} называется пороговой, если в Ж" существует гиперплоскость, разделяющая множества ее нулей и единиц. Другим интересным для теории и приложений обобщением является расшифровка в классе функция, зада�
