О расшифровке логических функций

1. Общая характеристика работы.

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

— активный учитель: ученик может сам выбирать, какие вопросы задавать учителю. Учитель отвечает на вопросы ученика. В прикладной среде такой подход называется классификацией с активным учителем (обучение у активного учителя);

— пассивный учитель: ученик никак не влияет на учителя, учитель сам генерирует возможные вопросы ученика и сам же отвечает на них. Другими словами, учитель генерирует примеры с ответами, и ученик должен обучиться по ним. В прикладной среде такой подход называется классификацией с пассивным учителем (обучением у пассивного учителя);

— учитель отсутствует. Ученик получает некоторое множество данных, выделяет в нем какие-либо закономерности и в соответствии с этими закономерностями разбивает множество на классы, такие что в одном классе содержатся «похожие» друг на друга элементы. В прикладной среде такой подход называется кластеризацией.

В настоящей диссертации исследуется сложность расшифровки дискретных функций из различных классов при активном учителе в модели точной расшифровки при помощи запросов на значение функции [1, 2, 3]. Задачу расшифровки псевдо-булевских функций можно рассматривать как задачу расшифровки автоматов без памяти, т. е. как частную подзадачу более общей задачи расшифровки автоматов [4]. Модель точной расшифровки — это модель расшифровки, в которой предполагается, что загаданную учителем функцию ученик должен отгадывать точно, а не приближенно с некоторой вероятностью (как, например, в модели вероятно примерно точной расшифровки). В модели точной расшифровки функция / от п переменных задана при помощи черного ящика и задача ученика (алгоритма расшифровки) состоит в том, чтобы расшифровать /, т. е. полностью восстановить ее таблицу значений. Чтобы расшифровать загаданную функцию, алгоритм расшифровки может делать запросы на значение функции, т. е. подавать произвольные наборы из области определения функции черному ящику. Алгоритм расшифровки подает запросы блоками, учитель одновременно отвечает на все вопросы из одного блока. В стандартной постановке алгоритм расшифровки должен расшифровать загаданную функцию, использовав по возможности наименьшее число запросов на значение функции. В параллельной постановке алгоритм расшифровки должен минимизировать число блоков, требуемых для расшифровки [5].

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

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

Пример 2. Распознавание речи и другие задачи распознавания, в которых «правильные ответы» учителя стоят очень дорого. Использование подхода с активным учителем позволяет минимизировать число запросов к учителю путем их оптимального выбора.

Пример 3. Задачи поиска, в частности, поиска в интернете. Уже несколько лет ведущие поисковые системы «расшифровывают» собственные функции ранжирования страниц сайтов в попытке сделать их наиболее точными. В данном случае расшифровка с активным учителемснова единственная возможность: подбираются конкретные запросы (поисковые запросы) и ответы поисковых систем на них и только по этим запросам специально обученные люди оценивают соответствие запросов и ответов (т.е., функцию ранжирования).

В описанных прикладных задачах существенную роль играют следующие два фактора.

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

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

Неполный список исследований, проведенных в точности в рамках модели точной расшифровки при помощи запросов на значение функции, но не рассматривающих ни задачу параметро-эффективной расшифровки, ни задачу параллельной расшифровки, включает в себя [2, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15].

Некоторые общие результаты по сложности параметро-эффективной (но не параллельной) расшифровки в модели точной расшифровки при помощи запросов на значение функции получены в [16]. И. Вегенер и др. [17] получили точные оценки сложности параметро-эффективной расшифровки некоторых классов булевских функций в этой модели.

Параллельная (но не нараметро-эффективная) расшифровка в модели точной расшифровки при помощи запросов на значение функции исследовалась в [18]. Наконец, параллельная параметро-эффективная расшифровка в этой модели рассматривалась в работах П. Дамашке [5, 19, 20].

В большинстве упомянутых работ рассматривается расшифровка булевских функций. В настоящей диссертации исследована задача параллельной параметро-эффективной расшифровки псевдо-булевских функций. Основные свойства псевдо-булевских функций описаны в [21]. Некоторые классы псевдо-булевских функций описаны в [22].

Параметро-эффективная расшифровка (иначе, расшифровка хунт) исследовалась в рамках нескольких моделей стимулирующего обучения и обучения с учителем. Параметро-эффективный алгоритм расшифровки пороговых функций в рамках модели ограниченной ошибки стимулирующего обучения предложен в [23]. Впоследствии различные аспекты параметро-эффективной расшифровки были рассмотрены в [24, 16]. Пассивное обучение с учителем, т. е. расшифровка по случайной выборке обычно изучается в рамках так называемой модели вероятно примерно точной расшифровки [25]. Параметро-эффективная расшифровка по случайной равномерно распределенной выборке в РАС модели является открытой проблемой [26]. Для ознакомления с недавними результатами по пассивной расшифровке хунт см. [27, 28, 29]. Параллельная расшифровка рассматривалась в [30, 18, 31].

Среди направлений, близких к рассматриваемому направлению расшифровки функций, можно выделить теорию тестового распознавания [32, 33].

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

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

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

В диссертации получены следующие результаты.

1. Для классов монотонных, разбивающих и интервально-постоянных функций получены порядки сложности определения существенных переменных. Для разбивающих функций построен алгоритм ответов на запросы назначение функции, позволивший в случае малого числа существенных переменных получить асимптотику сложности определения существенных переменных. Для полных разбивающих функций при малом и большом числе существенных переменных получены асимптотики сложности определения существенных переменных, отличные от оценок в общем случае. Для получения оценок сложности параллельной расшифровки введено понятие 2-разделяемых функций и показано, что как класс разбивающих функций, так и класс монотонных функций являются 2-разделяемыми (т.е. содержат 2-разделяемые функции), откуда классы псевдо-булевских монотонных функций и интервально-постоянных функций также являются 2-разделяемыми. Для 2-разделяемых классов функций построен алгоритм ответов на запросы на значение функции, позволивший получить порядок параллельной сложности определения существенных переменных таких функций.

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

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

Диссертация имеет теоретический характер и может быть полезна специалистам по расшифровке функций, специалистам по теории алгоритмического обучения, по теории автоматов и их приложений.

Результаты диссертации докладывались.

• на IX Международной конференции «Интеллектуальные системы и компьютерные науки» (2006г.),.

• на IX Международном семинаре «Дискретная математика и ее приложения» (2007г.),.

• па Международной конференции «Современные проблемы математики, механики и их приложений», посвященной 70-летию ректора МГУ академика В. А. Садовничего (2009г.),.

• на Международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2009», «Ломоносов-2010», «Ломоносов-2011» (2009, 2010, 2011гг.). На конференции «Ломоносов-2011» награжден дипломом за лучший доклад на секции «Математика и Механика».

• на Международном семинаре «Дискретная математика» (2010г.).

• на семинаре «Вопросы сложности алгоритмов поиска» под руководством профессора Э. Э. Гасанова, 2005;2010 гг. (неоднократно);

• на научно-исследовательском семинаре кафедры Математической' теории интеллектуальных систем «Теория автоматов», 2008;2010 гг. (неоднократно);

• на семинаре «Кибернетика и информатика» под руководством профессора В. Б. Кудрявцева, МГУ им. М. В. Ломоносова, 2010;2011 гг. (неоднократно);

Основные результаты диссертации опубликованы в восьми статьях [38, 39, 40, 41, 42, 43, 44, 45] и материалах конференций [46, 47, 48, 49, 50, 51].

Диссертация состоит из введения и трех глав. Объем диссертации 117 стр.

Список литературы

содержит 37 наименований.

3.2 Заключение.

Теорема 8 следует из описания алгоритма расшифровки, приведенного в параграфе 3.1.2. Теорема 9 следует из нижних оценок главы 1 и того факта, что для расшифровки функции необходимо хотя бы расшифровать ее существенные переменные. Теорема 10 — основной результат по сложности параллельной расшифровки функций, он вытекает из теорем 8 и 9.