Байесовское программирование — это формальная система и методология определения вероятностных моделей и решения задач, когда не вся необходимая информация является доступной.
Эдвин Томпсон Джейнс предложил рассматривать вероятность как альтернативу и расширение логики для рациональных рассуждений с неполной и неопределенной информацией. В своей основополагающей книге «Теория вероятности: логика науки» он развил эту теорию и предложил то, что он назвал «роботом», который был не физическим устройством, а машиной вывода, автоматизирующей вероятностные рассуждения — что-то вроде Пролога для теории вероятности вместо логики. Байесовское программирование является формальной и конкретной реализацией этого «робота».
Байесовское программирование также можно рассматривать как формальную алгебраическую систему для задания графовых моделей, таких как, например, байесовские сети, , фильтры Кальмана или скрытые марковские модели. Действительно, байесовское программирование обобщает байесовские сети и имеет выразительную мощность эквивалентную .
Формальная система Байесовская программа является средством задания семейства распределений вероятности.
Ниже представлены составляющие элементы байесовской программы:
Программа строится из описания () и вопроса (). Описание строится с помощью какого-либо определения (, ), заданного программистом, и идентификации () или процесса обучения для параметров, не полностью описанных в определении, с применением набора данных (). Определение строится из набора значимых переменных (), декомпозиции () и набора форм (). Формы являются или параметрическими формами, или вопросами к другим байесовским программам. Вопрос задает распределение вероятности, которое необходимо вычислить.
Описание Описание задает эффективный метод вычисления совместного распределения вероятности набора переменных для заданного набора экспериментальных данных и некоторого определения . Это совместное распределение обозначается как .
Чтобы задать предварительное знание , программист должен выполнить следующее: Определить набор значимых переменных , на которых задано совместное распределение вероятности. Разложить совместное распределение (разбить его на подходящие независимые или условные вероятности). Определить формы каждого из этих распределений (например, для каждой переменной выбрать одно из перечня распределений вероятности).
Декомпозиция Пусть множество содержит подмножеств, переменные определены как , каждая из которых соответствует одному из этих подмножеств. Каждая переменная получается как конъюнкция переменных , относящихся к -тому подмножеству. Рекурсивное применение теоремы Байеса приводит к
Применение гипотезы условной независимости позволяют проделать дальнейшие упрощения. Гипотеза условной независимости для переменной определяется выбором некоторой переменной среди переменных, присутствующих в конъюнкции . Обозначая через конъюнкцию выбранных переменных и принимая
Получаем
Такое упрощение совместного распределения в виде произведения более простых распределений называется декомпозицией, выведенной с помощью .
Это обеспечивает, чтобы каждая переменная появлялась слева от черточки условности не менее одного раза, что является необходимым и достаточным условием написания математически верных выкладок.
Формы Каждое распределение , встречающееся в произведении, далее связывается или с параметрической формой (то есть функцией ), или с вопросом к другой байсовской программе .
Когда это форма , в общем случае является вектором параметров, которые могут зависеть или от , или , или от обоих. Когда некоторые из этих параметров вычисляются с применением набора данных , происходит обучение.
Важная особенность байесовского программирования — это способность использовать вопросы к другим байесовским программам как составляющую определения новой байесовской программы. получается выводом, произведенным другой байесовской программой, заданной определением и данными . Это похоже на вызов подпрограммы в классическом программировании, и предоставляет простой способ построения иерархических моделей.
Вопрос Пусть дано описание (то есть ), вопрос получается разбиением на три множества: исследуемые () переменные, известные () переменные и свободные () переменные.
Три переменные , и определяются как конъюнкция переменных, принадлежащих к этим множествам.
Вопрос определяется как набор распределений
составленный из «конкретизированных вопросов» как кардинал , где каждый конкретизированный вопрос является распределением
Вывод Для заданного совместного распределения всегда возможно вычислить любой вопрос, применяя следующий общий вывод:
где первое равенство следует из правила обособления (), второе вытекает из теоремы Байеса, а третье соответствует второму применению обособления. Знаменатель оказывается нормирующим членом (), и его можно заменить постоянной .
Теоретически это позволяет решать любые задачи байесовского вывода. Однако на практике почти во всех случаях затраты на исчерпывающее и точное вычисление оказываются слишком большими.
Заменяя совместное распределение его декомпозицией, получаем
которое обычно является выражением, значительно более простым для вычисления, поскольку размерность задачи значительно снижена разложением на произведение распределений меньшей размерности.
Пример
Байесовское обнаружение спама Целью байесовской фильтрации спама является устранение мусорных электронных писем.
Формулировка этой задачи достаточно простая. Электронные письма должны классифицироваться по одной из двух категорий: не-спам и спам. Единственной доступной информацией для классификации электронных писем является их содержание: набор слов. Использование слов без принятия во внимания их порядка в предложении часто называют моделью мешка слов.
Кроме того, классификатор должен быть способным адаптироваться к своему пользователю и учиться из опыта. Начиная со стандартной начальной настройки, классификатор должен изменять свои внутренние параметры, если пользователь не соглашается с его решением. Он, следовательно, будет адаптироваться к пользовательским критериям различия между не-спамом и спамом. Он будет улучшать собственные результаты, сталкиваясь со все большим количеством классифицированных электронных писем.
Переменные Следующие переменные необходимы для написания этой программы: : двоичная переменная, ложь, если электронное письмо не является спамом, и истина в противном случае. : двоичных переменных. является истиной, если -ое слово словаря присутствует в тексте. Эти двоичных переменных суммируют всю информацию об электронной почте.
Декомпозиция Начиная с определения совместного распределения и рекурсивно применяя теорему Байеса, получаем:
Это точное математическое выражение.
Оно может быть радикально упрощено, если предположить, что вероятность появления слова при известной категории текста (спам или нет) является независимой от появления других слов. Такое предположение является наивным байесовским, и поэтому этот фильтр спама является наивной байсовской моделью.
Например, программист может предположить, что
и в итоге получить
Это предположение известно как наивное байесовское предположение. Оно является «наивным» в том смысле, что независимость между словами, очевидно, не является истинной. Например, оно полностью пренебрегает тем, что появление пары слов может быть более значимым, чем изолированные появления. Однако программист может принять эту гипотезу, и может разрабатывать эту модель и связанный с ней вывод, чтобы проверить, насколько надежной и эффективной она является.
Параметрические формы Чтобы иметь возможность вычислить совместное распределение, программист теперь должен указать распределений, присутствующих в разложении: определено априорно, например, как Каждая из форм может быть задана с помощью (это на базе для преодоления проблемы нулевой частоты до сих пор не встречавшихся слов):
где — количество появлений -го слова в неспамовых электронных письмах, а — общее количество неспамовых электронных писем. Аналогично, — количество появлений -го слова в спамовых электронных письмах, а — общее количество спамовых электронных писем.
Идентификация форм еще не определены полностью, поскольку параметров , , и еще не имеют значений.
Идентификация этих параметров может быть осуществлена или пакетной обработкой группы классифицированных электронных писем, или инкрементальным обновлением параметров с помощью классификации электронных писем пользователем в процессе их поступления.
Оба метода могут быть объединены: система может стартовать с начальными стандартными значениями этих параметров, выданных из обобщенной базы данных, а затем некоторое инкрементальное обучение подгоняет классификатор под каждого отдельного пользователя.
Вопрос Вопрос, который задается программе: «какова вероятность того, что данный текст является спамом, если известно, какие слова в нем присутствуют, а какие — нет?» Его можно формализовать как
что может быть вычислено следующим образом:
В этом выражении знаменатель оказывается нормализующей константой. Его не обязательно вычислять для того, чтобы выяснить, имеем ли мы дело со спамом. Например, простой прием для вычисления отношения:
Такое вычисление является более быстрым и удобным, поскольку оно требует всего лишь произведений.
Байесовская программа Программа байесовского фильтра спама полностью определяется как
Фильтр Байеса, фильтр Кальмана и скрытая модель Маркова Байесовские фильтры (которые часто называют ) являются общими вероятностными моделями для процессов, разворачивающихся во времени. Многочисленные модели являются частными случаями этого общего подхода, например, фильтр Кальмана или скрытая марковская модель.
Переменные Переменные — временной ряд переменных состояния, которые рассматриваются на временном горизонте в диапазоне от до . Переменные — временной ряд переменных наблюдения на этом же горизонте.
Декомпозиция Декомпозиция основывается на: , называемой моделью системы, моделью перехода или динамической моделью, которая формализует переход от состояния в момент времени в состояние в момент времени ; , называемой моделью наблюдения, которая выражает, что может наблюдаться в момент времени , когда система находится в состоянии ; исходном состоянии в момент времени : .
Параметрические формы Выбор параметрических форм не ограничен, и различные варианты ведут к различным хорошо известным моделям: см. ниже фильтры Кальмана и скрытые марковские модели.
Вопрос Обычный вопрос для этих моделей — : каково распределение вероятности состояния в момент времени , если известны наблюдения от момента до ?
Самый общий случай — это байесовская фильтрация, для которой , что означает, что определяется состояние в настоящий момент времени при известных предыдущих наблюдениях.
Однако также возможно осуществлять и экстраполяцию будущего состояния, используя прошлые наблюдения, или осуществлять сглаживание , чтобы восстановить прошлое состояние из наблюдений, сделанных или до, или после некоторого момента времени.
Могут задаваться и более сложные вопросы, как показано ниже в разделе СММ.
Байесовские фильтры имеют очень интересное рекурсивное свойство, что значительно способствует их привлекательности. может быть вычислено просто с помощью по следующей формуле:
Еще одна интересная точка зрения на это уравнение — рассмотреть существование двух фаз: фазы предвидения и фазы оценки: В течение фазы предвидения состояние предсказывается с помощью динамической модели и оценки состояния в предыдущий момент:
В течение фазы оценки предсказание или подтверждается, или признается недействительным с помощью последнего наблюдения:
Байесовская программа
Фильтр Кальмана Хорошо известные фильтры Кальмана являются частным случаем байесовских фильтров.
Они задаются следующей байесовской программой:
Переменные являются непрерывными.