Диссертация (1137435), страница 4
Текст из файла (страница 4)
Очевидно, что проблема#P = P? установления истинности или ложности этого равенства можетостаться нерешенной даже в случае положительного решения проблемыNP = P? Установление #P-полноты задачи подсчета говорит о том, чтовычисление соответствующего числа довольно трудно, например не легче(в смысле полиномиальной сводимости по Тьюрингу) задачи определениячисла всех наборов, выполняющих КНФ.В дальнейшем нам будут необходимы определения эффективностиалгоритмов, размер выхода которых может быть экспоненциален от размера входа.
Следующее определение было предложено в работе [61]. Алгоритм, порождающий (перечисляющий) семейство объектов (называемыхкомбинаторными структурами, combinatorial structures, в [61]) имеет задержку (delay) , если он удовлетворяет следующим условиям при работесо входом длины :1. Он выполняет максимум () вычислительных шагов прежде чемвыдаст первый объект, либо остановится ничего не выдав.2.
После выдачи объекта он либо выполнит не более () машинных26операций прежде чем выдаст очередной объект, либо остановится. Алгоритм с задержкой, ограниченной сверху полиномом от размера входа называется алгоритмом с полиномиальной задержкой [61].Еще более слабое определение эффиктивности перечисляющего алгоритма – это полиномиальность от выхода. Говорят, что алгоритм работаетполиномиальное от выхода время, если время его работы полиномиальноот размера его входа и размера его выхода.
Очевидно, что алгоритм с полиномиальной задержкой является также алгоритмом с полиномиальнымот выхода временем.Вероятностная приближающая схема (Randomized approximationscheme) для задачи подсчета : Σ* → N (например, количество формальных понятий контекста) – это вероятностный алгоритм, который в качествевхода получает ∈ Σ* (например формальный контекст K = (, , )), атакже погрешность > 0, и выдает число ∈ N такое что, для каждоговхода , [(1 − ) () ≤ ≤ (1 + ) ()] ≥34Если время работы вероятностной приближающей схемы полиномиально от || и −1 , то такой алгоритм называется Полностью полиномиальная приближающая схема (fully polynomial randomized approximationscheme), или FPRAS.Для задач случайной генерации (Sampling) почти равномерным генератором(fully polynomial almost uniform sampler (AUS)) называют вероятностный алгоритм, который, получая на вход задачу ∈ Σ* , выдает ееслучайное решение () в соответствии с некоторым распределением .Причем, вариационное расcтояние между и равномерным распределени-27ем Γ не больше , т.е.∑︁|() − Γ()| ≤ .1.2.Модели зависимостей и их вычислениеМашинное (автоматическое) обучение (Machine Learning) - одно из ос-новных направлений искусственного интеллекта и анализа данных.
Сложно дать точное формальное определение машинного обучения, хотя существует множество моделей машинного обучения, для каждой из которых такое определение дается. Можно сказать, что в самых общих чертах,идея машинного обучения заключается в порождении обобщенного описания объектов с целью его дальнейшего использования для классификациидругих объектов по их описаниями. Стадию классификации называют также распознаванием (иногда слово “распознавание” используют в качествесинонима “машинного обучения”).
Обобщенное описание может, к примеру, соответствовать определенному состоянию множества весов если речьидет об обучении в нейронной сети по входящим и выходящим сигналам.В нашей работе речь пойдет об обучении для данных, представимых ввиде некоторых описаний в символьной форме. Обычно задача обученияпри этом ставится следующим образом. Имеется конечное множество объектов (наблюдений) , разделенное на несколько подмножеств (классов).Все объекты имеют описание в некотором формальном языке .
По описаниям объектов из необходимо породить осмысленное правило, сформулированное в языке ′ , которое по описанию объекта из выдавало бы28номер его класса. Осмысленность правила может определяться, например,через оптимальность в смысле некоторого численного “функционала качества обучения” (часто являющегося функцией от длины правила: чемкороче правило - тем лучше) или через какие-либо другие формальныеусловия. Требование “осмысленности” при этом должно обеспечивать то,что порождаемое правило не сводится просто к прямому использованиюсписка всех пар (объект, класс), а является некоторым их “обобщением”.Одними из первых среди теоретических моделей обучаемости рекурсивным функциям стали исследования Соломонова [94] и Голда [56].
В общих чертах модель обучения по Голду может быть представлена следующим образом. Задана бесконечная последовательность примеров, т.е. парвида (аргумент, значение) для некоторой неизвестной функции из класса. Можно ли построить алгоритм, который, получив первых входныхпар, выдает функцию таким образом, что для некоторого , ∀ ≥ , = +1 = .
. . = ? Класс функций называется обучаемым, если любая функция из этого класса обучаема. Возможны различные уточненияприведенных выше определений, касающиеся требования рекурсивности,частичной рекурсивности или предельной вычислимости, последовательности представления примеров и др.В.Н. Вапником и А.Я. Червоненкисом [5] была предложена следующая модель обучения. Пусть есть класс функций на × , и дляпроизвольной функции задано значение в точках из , каждая изкоторых выбирается случайно и независимо в соответствии с некоторымфиксированным, но неизвестным распределением вероятностей ().
Задача обучения состоит в построении для произвольных и функции ∈ ,29для которой с вероятностью большей 1 − математическое ожидание (относительно ()) отклонения значений функции от значений функций не превышает . Аналогичные постановки возможны для других классов функций (например, булевых). Важнейшим результатом исследованийданной модели явилось установление критериев сходимости и скорости сходимости эмпирических моделей к искомой функции для произвольных(бесконечных по размеру) классов функций.Развитием модели Вапника стала модель Вэльянта [97] “вероятно приближенно правильного” (Probably Approximately Correct, PAC) обучения, вкоторой алгоритм обучения, строящий искомую функцию должен использовать “ограниченное” число обучающих примеров и иметь сложность повремени, ограниченную полиномом от входа.В теоретических моделях обучения ключевым является допущение отом, что данные подчиняются некоторой (неизвестной) функции из определенного класса, а сами данные (в моделях Вапника и Вэльянта) возникаютв соответствии с некоторым (неизвестным) распределением вероятности.Эти довольно сильные допущения позволяют строить красивые математические теории, но сами по себе трудно проверяемы и часто "навязывают"природе изучаемых явлений неоправданно сильные условия.
В эмпирических методах обучения (к которым, принадлежит, например, ДСМметод) подобных допущений не делается. Каждый такой метод предлагаетнекоторый инструментарий построения “осмысленных обобщений”, который по началу обосновывается некоторыми методологическими соображениями, а затем либо доказывает свою эффективность на практике (чтосопровождается разработкой типологии ситуаций применения) либо нет.30Задача обучения часто формулируется для двух классов исходныхобъектов, и к такой постановке сводится случай с большим числом классов.В нашей работе мы будем придерживаться постановки с двумя классами.При этом один из классов обычно называется положительным, а другой отрицательным относительно целевого признака.
Исходные объекты, принадлежащие данным классам, называются, соответственно, положительными или отрицательными примерами.Одним из самых распространенных и самых естественных способовописания объектов являются объектно-признаковые матрицы – матрицы,строки которых соответствуют объектам, а столбцы - признакам, принимающим некоторые значения. При этом элемент матрицы указывает нато, какое значение принимает признак с номером для объекта с номером. В простейшем случае признаки принимают значение из двухэлементногомножества {0, 1}. При этом значение 1 элемента матрицы интерпретируется как наличие соответствующего признака у объекта, а 0 - как его отсутствие.
К такому представлению с помощью бинарных (булевых) объектнопризнаковых матриц сводятся и более общие, в которых признаки могутпринимать более чем два значения.Поиск ассоциативных правил является популярным и хорошо изученным методом извлечения интересных зависимостей между признаками в больших базах данных. В статье [87] Пятетский-Шапиро описал анализ и представление строгих правил, найденных в базе данных, используяразличные меры интересности. Основываясь на концепции строгих правилАграваль и др. в [26] ввели понятие ассоциативных правил для поиска закономерностей в купленных продуктах, используя базу данных, продаж на31кассах супермаркетов. Например правило {, } → {},найденное в данных по продажам, указывает на то, что, если покупательпокупает лук и картофель, то скорее всего он купит и мясо для гамбургера.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
