Байесовское программирование

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

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

Байесовское программирование также можно рассматривать как алгебраические формы для определения графических моделей, таких как, например, байесовские сети, динамические байесовские сети, фильтры Калмана или скрытые модели Маркова. Действительно, байесовское программирование является более общим, чем байесовские сети, и имеет мощность выражения, эквивалентную вероятностным графам факторов.

• 1 Формализм
  • 1.1 Описание
    • 1.1.1 Разложение
    • 1.1.2 Формы
  • 1.2 Вопрос
  • 1.3 Вывод
• 2 Пример
  • 2.1 Обнаружение байесовского спама
    • 2.1.1 Переменные
    • 2.1.2 Разложение
    • 2.1.3 Параметрические формы
    • 2.1.4 Идентификация
    • 2.1.5 Вопрос
    • 2.1.6 Байесовская программа
  • 2.2 Байесовский фильтр, фильтр Калмана и скрытая марковская модель
    • 2.2.1 Переменные
    • 2.2.2 Разложение
    • 2.2.3 Параметрические формы
    • 2.2.4 Вопрос
    • 2.2.5 Байесовская программа
    • 2.2.6 Фильтр Калмана
    • 2.2.7 Скрытая марковская модель
• 3 Приложения
  • 3.1 Академические приложения
    • 3.1.1 Робототехника
    • 3.1.2 Науки о жизни
  • 3.2 Распознавание образов
• 4 Теории возможностей
• 5 Вероятностное программирование
• 6 См. Также
• 7 Ссылки
• 8 Дополнительная литература
• 9 Внешние ссылки

Байесовская программа i s средство определения распределений вероятностей.

Составные элементы байесовской программы представлены ниже:

$Программа\; \{Описание\; \{Спецификация\; (\pi )\; \{Идентификация\; форм\; декомпозиции\; чис\; (на\; основе\; \delta ))\; Вопрос\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Program\}\}\; \{\backslash \; begin\; \{cases\; \}\; \{\backslash \; text\; \{Описание\}\}\; \{\backslash \; begin\; \{cases\}\; \{\backslash \; text\; \{Specification\}\}\; (\backslash \; pi)\; \{\backslash \; begin\; \{cases\}\; \{\backslash \; text\; \{Variables\}\}\; \backslash \backslash \; \{\backslash \; text\; \{Decomposition\}\}\; \backslash \backslash \; \{\; \backslash \; text\; \{Forms\}\}\; \backslash \backslash \backslash \; end\; \{case\}\}\; \backslash \backslash \; \{\backslash \; text\; \{Идентификация\; (на\; основе\}\}\; \backslash \; delta)\; \backslash \; end\; \{ases\}\}\; \backslash \backslash \; \{\backslash \; text\; \{Question\}\}\; \backslash \; end\; \{case\}\}\; \}$

1. Программа состоит из описания и вопроса.
2. Описание строится с использованием некоторой спецификации ($\pi \; \{\backslash \; displaystyle\; \backslash \; pi\}$) как указано программистом, и процесс идентификации или обучения параметров, не полностью определенных спецификаций, с использованием набора набора данных ($\delta \; \{\backslash \; displaystyle\; \backslash \; delta\}$).
3. Спецификация строения из соответствующих чисел, декомпозиция и набор форм.
4. Формы - это либо набор параметров формы, либо вопросы к другим r Байесовские программы.
5. Вопрос определить, какое распределение вероятностей необходимо вычислить.

Описание

Цель описания - указать эффективный метод вычислений совместной вероятности распределения по набору число $\{X\; 1,\; X\; 2,\; \cdots ,\; XN\}\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; \{X\_\; \{1\},\; X\_\; \{2\},\; \backslash \; cdots,\; X\_\; \{N\}\; \backslash \; right\; \backslash \}\}$с учетом набора экспериментальных данных $\delta \; \{\backslash \; displaystyle\; \backslash \; delta\}$и некоторой спецификации $\pi \; \{\backslash \; displaystyle\; \backslash \; pi\}$. Это совместное распре деление обозначается как: $P\; (X\; 1\; \wedge \; X\; 2\; \wedge \; \cdots \; \wedge \; XN\; \mid \; \delta \; \wedge \; \pi )\; \{\backslash \; displaystyle\; P\; \backslash \; left\; (X\_\; \{1\}\; \backslash \; wedge\; X\_\; \{2\}\; \backslash \; wedge\; \backslash \; cdots\; \backslash \; wedge\; X\_\; \{N\}\; \backslash \; mid\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\}$.

Чтобы указать предварительные знания $\pi \; \{\backslash \; displaystyle\; \backslash \; pi\}$, программист должен выполнить следующее:

1. Определите набор соответствующих переменных $\{X\; 1,\; X\; 2,\; \cdots ,\; XN\}\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; \{X\_\; \{1\},\; X\_\; \{2\},\; \backslash \; cdots,\; X\_\; \{N\}\; \backslash \; right\; \backslash \}\}$, на котором определено совместное распределение.
2. Разбейте объединенное распределение (разбейте его на соответствующие независимые или условные вероятности ).
3. Определите форму каждого из распределений (например, для каждой из распределений вероятностей 412>Разложение

   Задано разделение $\{X\; 1,\; X\; 2,\dots ,\; XN\}\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; \{X\_\; \{1\},\; X\_\; \{2\},\; \backslash \; ldots,\; X\_\; \{N\}\; \backslash \; right\; \backslash \}\}$обеспечивается $K\; \{\backslash \; displaystyle\; K\}$подмножества, $K\; \{\backslash \; displaystyle\; K\}$переменные значения d $L\; 1,\; \cdots ,\; LK\; \{\backslash \; displaystyle\; L\_\; \{1\},\; \backslash \; cdots,\; L\_\; \{K\}\}$, каждый из которых соответствует одному из этих подмножеств. Каждая переменная $L\; k\; \{\backslash \; displaystyle\; L\_\; \{k\; \}\}$как конъюнкция получается чис $\{X\; k\; 1,\; X\; k\; 2,\; \cdots \}\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; \{X\_\; \{k\_\; \{1\}\},\; X\_\; \{k\_\; \{2\}\},\; \backslash \; cdots\; \backslash \; right\; \backslash \}\}$, принадлежащие $kth\; \{\backslash \; displaystyle\; k\; ^\; \{th\}\}$подмножество. Рекурсивное применение теоремы Байеса приводит к:

   $P\; (X\; 1\; \wedge \; X\; 2\; \wedge \; \cdots \; \wedge \; XN\; \mid \; \delta \; \wedge \; \pi )\; =\; P\; (L\; 1\; \wedge \; \cdots \; \wedge \; LK\; \mid \; \delta \; \wedge \; \pi )\; =\; P\; (L\; 1\; \mid \; \delta \; \wedge \; \pi )\; \times \; P\; (L\; 2\; \mid \; L\; 1\; \wedge \; \delta \; \wedge \; \pi )\; \times \; \cdots \; \times \; P\; (LK\; \mid \; LK\; -\; 1\; \wedge \; \cdots \; \wedge \; L\; 1\; \wedge \; \delta \; \wedge \; \pi )\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; P\; \backslash \; left\; (X\_\; \{1\}\; \backslash \; клин\; X\_\; \{2\}\; \backslash \; клин\; \backslash \; cdots\; \backslash \; wedge\; X\_\; \{N\}\; \backslash \; mid\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\; \backslash \backslash \; =\; \{\}\; P\; \backslash \; left\; (L\_\; \{1\}\; \backslash \; wedge\; \backslash \; cdots\; \backslash \; wedge\; L\_\; \{K\}\; \backslash \; mid\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\; \backslash \backslash \; =\; \{\}\; P\; \backslash \; left\; (L\_\; \{1\}\; \backslash \; mid\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\; \backslash \; times\; P\; \backslash \; left\; (L\_\; \{2\}\; \backslash \; mid\; L\_\; \{1\}\; \backslash \; wedge\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\; \backslash \; times\; \backslash \; cdots\; \backslash \; times\; P\; \backslash \; left\; (L\_\; \{K\}\; \backslash \; mid\; L\_\; \{K-1\}\; \backslash \; wedge\; \backslash \; cdots\; \backslash \; wedge\; L\_\; \{1\}\; \backslash \; wedge\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\; \backslash \; end\; \{align\}\}\}$

   Условная независимость гипотезы позволяют дальнейшие упрощения. Гипотеза условной независимости для модели $L\; k\; \{\backslash \; displaystyle\; L\_\; \{k\}\}$определен выбор некоторой переменной $X\; n\; \{\backslash \; displaystyle\; X\_\; \{n\}\}$среди чисел, входящие в соединение $L\; k\; -\; 1\; \wedge \; \cdots \; \wedge \; L\; 2\; \wedge \; L\; 1\; \{\backslash \; displaystyle\; L\_\; \{k-1\}\; \backslash \; wedge\; \backslash \; cdots\; \backslash \; wedge\; L\_\; \{2\}\; \backslash \; wedge\; L\_\; \{1\}\}$, маркировка $R\; k\; \{\backslash \; displaystyle\; R\_\; \{k\}\}$как соединение этих выбранных чисел и установка:

   $P\; (L\; k\; \mid \; L\; k\; -\; 1\; \wedge \; \cdots \; \wedge \; L\; 1\; \wedge \; \delta \; \wedge \; \pi )\; знак\; равно\; п\; (L\; К\; \mid \; р\; К\; \wedge \; \delta \; \wedge \; \pi )\; \{\backslash \; Displaystyle\; P\; \backslash \; left\; (L\_\; \{k\}\; \backslash \; mid\; L\_\; \{k-1\}\; \backslash \; клин\; \backslash \; cdots\; \backslash \; клин\; L\_\; \{1\}\; \backslash \; клин\; \backslash \; дельта\; \backslash \; клин\; \backslash \; pi\; \backslash \; right)\; =\; P\; \backslash \; left\; (L\_\; \{k\}\; \backslash \; mid\; R\_\; \{k\}\; \backslash \; wedge\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\}$

   Затем получаем:

   $P\; (X\; 1\; \wedge \; X\; 2\; \wedge \; \cdots \; \wedge \; XN\; \mid \; \delta \; \wedge \; \pi )\; знак\; равно\; P\; (L\; 1\; \mid \; \delta \; \wedge \; \pi )\; \times \; P\; (L\; 2\; \mid \; R\; 2\; \wedge \; \delta \; \wedge \; \pi )\; \times \; \cdots \; \times \; P\; (LK\; \mid \; RK\; \wedge \; \delta \; \wedge \; \pi )\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{\; align\}\; P\; \backslash \; left\; (X\_\; \{1\}\; \backslash \; wedge\; X\_\; \{2\}\; \backslash \; wedge\; \backslash \; cdots\; \backslash \; wedge\; X\_\; \{N\}\; \backslash \; mid\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\; \backslash \backslash \; =\; \{\}\; P\; \backslash \; left\; (L\_\; \{\; 1\}\; \backslash \; mid\; \backslash \; delta\; \backslash \; клин\; \backslash \; pi\; \backslash \; right)\; \backslash \; times\; P\; \backslash \; left\; (L\_\; \{2\}\; \backslash \; mid\; R\_\; \{2\}\; \backslash \; wedge\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\; \backslash \; times\; \backslash \; cdots\; \backslash \; times\; P\; \backslash \; left\; (L\_\; \{K\}\; \backslash \; mid\; R\_\; \{K\}\; \backslash \; wedge\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\; \backslash \; end\; \{align\}\}\}$

   Такое упрощенное совместное распределение как продукт более простого распределения называется декомпозицией, полученной с использованием цепного правила .

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

   Формы

   Каждое распределение $P\; (L\; k\; \mid \; R\; k\; \wedge \; \delta \; \wedge \; \pi )\; \{\backslash \; displaystyle\; P\; \backslash \; left\; (L\_\; \{k\}\; \backslash \; mid\; R\_\; \{k\}\; \backslash \; wedge\; \backslash \; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\}$, появляющееся в продукте, затем ассоциируется либо с параметрической формой (т. е. функция $f\; \mu \; (L\; k)\; \{\backslash \; displaystyle\; f\; \_\; \{\backslash \; mu\})\; \backslash \; left\; (L\_\; \{k\}\; \backslash \; right)\}$) или вопрос по другой байесовской программе $P\; (L\; k\; \mid \; R\; k\; \wedge \; \delta \; \wedge \; \pi )\; =\; P\; (L\; \mid \; Р\; \wedge \; \delta \; ^\; \wedge \; \pi \; ^)\; \{\backslash \; displaystyle\; P\; \backslash \; left\; (L\_\; \{k\}\; \backslash \; mid\; R\_\; \{k\}\; \backslash \; wedge\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\; =\; P\; \backslash \; left\; (L\; \backslash \; mid\; R\; \backslash \; wedge\; \{\backslash \; widehat\; \{\backslash \; delta\}\}\; \backslash \; клин\; \{\backslash \; widehat\; \{\backslash \; pi\}\}\; \backslash \; right)\}$.

   Когда это форма $f\; \mu \; (L\; k)\; \{\backslash \; displaystyle\; f\; \_\; \{\backslash \; mu\}\; \backslash \; left\; (L\_\; \{k\}\; \backslash \; right)\}$, как правило, $\mu \; \{\backslash \; displaystyle\; \backslash \; mu\}$- векторные параметры, которые могут зависеть от $R\; k\; \{\backslash \; displaystyle\; R\_\; \{k\}\}$или $\delta \; \{\backslash \; displaystyle\; \backslash \; delta\}$или и то, и другое. Обучение происходит, когда некоторые из этих параметров вычисляются с использованием набора данных $\delta \; \{\backslash \; displaystyle\; \backslash \; delta\}$.

   Важной особенностью байесовского программирования является способность использовать в качестве других байесовских программам в компонентах новую байесовскую программу. $п\; (L\; К\; \mid \; р\; К\; \wedge \; \delta \; \wedge \; \pi )\; \{\backslash \; displaystyle\; P\; \backslash \; left\; (L\_\; \{k\}\; \backslash \; mid\; R\_\; \{k\}\; \backslash \; wedge\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\}$получается с помощью некоторых выводов, сделанных другой байесовской программой, определенной спецификациями $\pi \; ^\; \{\backslash \; displaystyle\; \{\backslash \; widehat\; \{\backslash \; pi\}\}\}$и данных $\delta \; ^\; \{\backslash \; displaystyle\; \{\backslash \; широкая\; шляпа\; \{\backslash \; delta\}\}\}$. Это похоже на вызов подпрограммы в классическом программировании и обеспечивает простой способ построения иерархических моделей.

   Вопрос

   Учитывая описание (т. Е. $P\; (X\; 1\; \wedge \; X\; 2\; \wedge \; \cdots \; \wedge \; XN\; \mid \; \delta \; \wedge \; \pi )\; \{\backslash \; displaystyle\; P\; \backslash \; left\; (X\_\; \{1\}\; \backslash \; wedge\; X\_\; \{2\}\; \backslash \; wedge\; \backslash \; cdots\; \backslash \; wedge\; X\_\; \{N\}\; \backslash \; mid\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\}$), вопрос получается разделением $\{X\; 1,\; X\; 2,\; \cdots ,\; XN\}\; \{\backslash \; displaystyle\; \backslash \; left\; \backslash \; \{X\_\; \{1\},\; X\_\; \{2\},\; \backslash \; cdots,\; X\_\; \{N\}\; \backslash \; right\; \backslash \}\}$на три набора: искомые переменные, известные переменные и свободные переменные.

   3 переменные $S\; получен\; \{\backslash \; displaystyle\; Searched\}$, $K\; nown\; \{\backslash \; displaystyle\; Known\}$и $F\; ree\; \{\backslash \; displaystyle\; Free\}$выбор как совокупность, принадлежащих этим множествам.

   Вопрос определяется как набор распределений:

   $P\; (S\; получено\; \mid \; Известно\; \wedge \; \delta \; \wedge \; \pi )\; \{\backslash \; displaystyle\; P\; \backslash \; left\; (Искать\; \backslash \; mid\; \{\backslash \; text\; \{Known\}\}\; \backslash \; wedge\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\}$

   последовательность из множества «конкретных вопросов» как кардинал $Известный\; \{\backslash \; displaystyle\; Known\}$, каждый конкретный вопрос представляет собой распределение:

   $P\; (Поиск\; \mid \; Известный\; \wedge \; \delta \; \wedge \; \pi )\; \{\backslash \; displaystyle\; P\; \backslash \; left\; (\{\backslash \; text\; \{Searched\}\}\; \backslash \; mid\; \{\backslash \; text\; \{Known\}\}\; \backslash \; wedge\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\}$

   Вывод

   Учитывая совместное распределение $п\; (Икс\; 1\; \wedge \; Икс\; 2\; \wedge \; \cdots \; \wedge \; XN\; \mid \; \delta \; \wedge \; \pi )\; \{\backslash \; displaystyle\; P\; \backslash \; left\; (X\_\; \{1\}\; \backslash \; wedge\; X\_\; \{2\}\; \backslash \; wedge\; \backslash \; cdots\; \backslash \; wedge\; X\_\; \{N\}\; \backslash \; mid\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\}$, всегда можно вычислить любой возможный вопрос, используя следующий общий вывод:

   $P (Поиск ∣ Известный ∧ δ ∧ π) = ∑ Свободный [P (Поиск ∧ Свободный ∣ Известный ∧ δ ∧ π)] = ∑ Свободный [P (Поиск ∧ Свободный ∧ Известный ∣ δ ∧ π)] P (Известный ∣ δ ∧ π) = ∑ Свободный [P (Поиск ∧ Свободный ∧ Известный ∣ δ ∧ π)] ∑ Свободный поиск [P (поиск ∧ свободный ∧ известный ∣ δ ∧ π)] = 1 Z × ∑ свободный [P (поиск ∧ свободный ∧ известный ∣ δ ∧ π)] {\ displaystyle {\ begin {align} P \ left ({\ text {Поиск}} \ mid {\ text {Known}} \ wedge \ delta \ wedge \ pi \ right) \\ = {} \ sum _ {\ text {Свободно}} \ left [P \ left ({\ text {Поиск}} \ wedge {\ text {Free}} \ mid {\ text {Known}} \ wedge \ delta \ wedge \ pi \ right) \ right] \\ = {} {\ frac {\ displaystyle \ sum _ {\ text {Free}} \ left [P \ left ({\ text {Searched}} \ wedge {\ text {Free}} \ wedge {\ text {Известно}} \ середина \ дельта \ клин \ пи \ вправо) \ вправо]} {\ displaystyle P \ left ({\ text {Known}} \ mid \ delta \ клин \ пи \ вправо)}} \\ = { } {\ frac {\ displaystyle \ sum _ {\ text {Свободно}} \ left [P \ left ({\ text {Searched}} \ wedge {\ text {Free}} \ wedge {\ text {Known}} \ mid \ delta \ wedge \ pi \ right) \ right]} {\ displaystyle \ sum _ {{\ text {Free}} \ wedge {\ text {Searched}}} \ left [P \ left ({\ text {Searched}} \ wedge {\ text {Free}} \ wedge {\ text {Known}} \ mid \ delta \ wedge \ pi \ right) \ right]}} \\ = {} {\ frac {1} {Z}} \ times \ sum _ {\ text {Free}} \ left [P \ left ({\ text {Searched}} \ wedge {\ text {Free}} \ wedge {\ text {Kn own}} \ mid \ delta \ wedge \ pi \ right) \ right] \ end {выравнивается}}}$

   где первое равенство следует из правил маргинализации, второе - из теоремы Байеса а третье соответствует второму применению маргинализации. Знаменатель выглядит как нормализационный член и может быть заменен константой $Z\; \{\backslash \; displaystyle\; Z\}$.

   Теоретически это позволяет решить любую проблему байесовского вывода. Однако на практике стоимости исчерпывающих и точных вычислений $P\; (поиск\; \mid \; Известный\; \wedge \; \delta \; \wedge \; \pi )\; \{\backslash \; displaystyle\; P\; \backslash \; left\; (\{\backslash \; text\; \{Searched\}\}\; \backslash \; mid\; \{\backslash \; text\; \{Known\}\}\; \backslash \; wedge\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\}$почти во всех случаях слишком велико.

   Заменяя совместное распределение его разложением, получаем:

   $P\; (Поиск\; \mid \; Известный\; \wedge \; \delta \; \wedge \; \pi )\; =\; 1\; Z\; \sum \; Свободный\; [\prod \; k\; =\; 1\; K\; [P\; (L\; i\; \mid \; K\; i\; \wedge \; \pi )]\; ]\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; P\; \backslash \; left\; (\{\backslash \; text\; \{Searched\}\}\; \backslash \; mid\; \{\backslash \; text\; \{Known\}\}\; \backslash \; wedge\; \backslash \; delta\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\; \backslash \backslash \; =\; \{\}\; \{\backslash \; frac\; \{1\}\; \{Z\}\}\; \backslash \; sum\; \_\; \{\backslash \; text\; \{Free\}\}\; \backslash \; left\; [\backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{K\}\; \backslash \; left\; [P\; \backslash \; left\; (L\_\; \{i\}\; \backslash \; mid\; K\_\; \{i\})\; \backslash \; wedge\; \backslash \; pi\; \backslash \; right)\; \backslash \; right]\; \backslash \; right]\; \backslash \; end\; \{align\}\}\}$

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

   Пример

   Байесовское обнаружение спама

   Целью байесовской фильтрации спама устранение нежелательных сообщений электронной почты.

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

   . Кроме того, классификатор должен уметь адаптироваться к своему пользователю и учиться на опыте. Новый стандартный стандартный режим, классификатор должен изменить свои внутренние параметры. Таким образом, он будет адаптироваться к критериям пользователя, чтобы различать спам и не спам. Это улучшит свои результаты, поскольку он сталкивается со всеми более засекреченными электронными письмами.

   Переменные

   Переменные, необходимые для написания этой программы, следующие:

   1. $S\; pam\; \{\backslash \; displaystyle\; Spam\}$: двоичная переменная, ложь, если электронная почта не Не будет спамом, и в противном случае будет потеряна правда.
   2. $W\; 0,\; W\; 1,\dots ,\; WN\; -\; 1\; \{\backslash \; displaystyle\; W\_\; \{0\},\; W\_\; \{1\},\; \backslash \; ldots,\; W\_\; \{N-1\}\}$: $N\; \{\backslash \; displaystyle\; N\}$двоичные переменные. $W\; n\; \{\backslash \; displaystyle\; W\_\; \{n\}\}$истинно, если $n-е\; \{\backslash \; displaystyle\; n\; ^\; \{th\}\}$слово словаря присутствует в тексте.

   Эти $N\; +\; 1\; \{\backslash \; displaystyle\; N\; +\; 1\}$двоичныепеременные суммируют всю информацию об электронном письме.

   Разложение

   Исходя из совместного распределения и рекурсивно применяя теорему Байеса, получаем:

   $P\; (Спам\; \wedge \; W\; 0\; \wedge \; \cdots \; \wedge \; WN\; -\; 1)\; =\; P\; (\; Спам)\; \times \; P\; (W\; 0\; \mid \; Спам)\; \times \; P\; (W\; 1\; \mid \; Спам\; \wedge \; W\; 0)\; \times \; \cdots \; \times \; P\; (WN\; -\; 1\; \mid \; Спам\; \wedge \; W\; 0\; \wedge \; \cdots \; \wedge \; WN\; -\; 2)\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{выровнено\}\; P\; (\{\backslash \; text\; \{Spam\}\}\; \backslash \; wedge\; W\_\; \{0\}\; \backslash \; wedge\; \backslash \; cdots\; \backslash \; wedge\; W\_\; \{N-1\})\; \backslash \backslash \; =\; \{\}\; P\; (\{\backslash \; text\; \{Spam\}\})\; \backslash \; times\; P\; (W\_\; \{0\}\; \backslash \; mid\; \{\backslash \; text\; \{Spam\}\})\; \backslash \; times\; P\; (W\_\; \{1\}\; \backslash \; mid\; \{\backslash \; text\; \{Spam\}\}\; \backslash \; wedge\; W\_\; \{0\})\; \backslash \backslash \; \backslash \; times\; \backslash \; cdots\; \backslash \backslash \; \backslash \; times\; P\; \backslash \; left\; (W\_\; \{N-1\}\; \backslash \; mid\; \{\backslash \; text\; \{Spam\}\}\; \backslash \; wedge\; W\_\; \{0\}\; \backslash \; wedge\; \backslash \; cdots\; \backslash \; wedge\; W\_\; \{N-2\}\; \backslash \; right)\; \backslash \; end\; \{align\}\}\}$

   Это это точное математическое выражение.

   Его можно значительно упростить, если предположить, что вероятность появления слова, зная характер текста (спам или нет), не зависит от других появления слов. Это наивное байесовское допущение, и это делает этот спам-фильтр наивной байесовской моделью.

   Например, программист может предположить, что:

   $P\; (W\; 1\; \mid \; Спам\; \wedge \; W\; 0)\; =\; P\; (W\; 1\; \mid \; Спам)\; \{\backslash \; displaystyle\; P\; (W\_\; \{1\}\; \backslash \; mid\; \{\backslash \; text\; \{\; Спам\}\}\; \backslash \; land\; W\_\; \{0\})\; =\; P\; (W\_\; \{1\}\; \backslash \; mid\; \{\backslash \; text\; \{Spam\}\})\}$

   , чтобы в итоге получить:

   $P\; (Spam\; \wedge \; W\; 0\; \wedge \dots \; \wedge \; WN\; -\; 1)\; =\; P\; (спам)\; \prod \; N\; =\; 0\; N\; -\; 1\; [P\; (W\; n\; \mid \; спам)]\; \{\backslash \; displaystyle\; P\; (\{\backslash \; text\; \{Spam\}\}\; \backslash \; land\; W\_\; \{0\}\; \backslash \; land\; \backslash \; ldots\; \backslash \; land\; W\_\; \{\; N\; -1\})\; =\; P\; (\{\backslash \; text\; \{Spam\}\})\; \backslash \; prod\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; [P\; (W\_\; \{n\}\; \backslash \; mid\; \{\backslash \; text\; \{Spam\}\})]\}$

   Такое предположение известно как наивное предположение Байеса. Это «наивно» в том смысле, что независимость между словами явно не совсем верна. Например, он полностью игнорирует то, что появление пар слов может иметь большее значение, чем отдельные проявления. Однако программист может принять эту гипотезу и разработать модель и связанные с ней выводы, чтобы проверить, насколько она надежна и эффективна.

   теперь Параметрические формы

   иметь возможность вычислить совместное распределение, программист должен указать $N\; +\; 1\; \{\backslash \; displaystyle\; N\; +\; 1\}$появляющиеся распределения в разложении:

   1. $P\; (Спам)\; \{\backslash \; displaystyle\; P\; (\{\backslash \; text\; \{Spam\}\})\}$заранее определено, например, $P\; ([Spam\; =\; 1])\; =\; 0,75\; \{\backslash \; displaystyle\; P\; ([\{\backslash \; text\; \{Spam\}\}\; =\; 1])\; =\; 0,75\}$
   2. Каждая из $N\; \{\backslash \; displaystyle\; N\}$формирует $P\; (W\; n\; \mid \; Спам)\; \{\; \backslash \; displaystyle\; P\; (W\_\; \{n\}\; \backslash \; mid\; \{\backslash \; text\; \{Spam\}\})\}$можно указать с помощью правил следовать Лапласа (это псевдосчет -основанный метод сглаживания для решения проблемы нулевой частоты слов, ранее не встречавшихся):
      1. $P\; (W\; n\; \mid \; [Spam\; =\; false])\; =\; 1\; +\; afn\; 2\; +\; af\; \{\backslash \; displaystyle\; P\; (W\_\; \{n\}\; \backslash \; mid\; [\{\backslash \; text\; \{Spam\}\}\; =\; \{\backslash \; text\; \{false\}\}])\; =\; \{\backslash \; frac\; \{1\; +\; a\_\; \{f\}\; ^\; \{n\}\}\; \{2\; +\; a\_\; \{f\}\}\}\}$
      2. $P\; (\; W\; n\; \mid \; [Spam\; =\; true])\; =\; 1\; +\; atn\; 2\; +\; at\; \{\backslash \; displaystyle\; P\; (W\_\; \{n\}\; \backslash \; mid\; [\{\backslash \; text\; \{Spam\}\}\; =\; \{\backslash \; text\; \{true\}\}])\; =\; \{\backslash \; frac\; \{1\; +\; a\_\; \{t\}\; ^\; \{n\}\}\; \{2\; +\; a\_\; \{t\}\}\}\}$

   где $afn\; \{\backslash \; displaystyle\; a\_\; \{f\}\; ^\; \{n\; \}\}$обозначает количество появлений $n-го\; \{\backslash \; displaystyle\; n\; ^\; \{th\}\}$слова в электронных письмах, не являющиеся спамом, а $af\; \{\backslash \; displaystyle\; a\_\; \{f\}\}$обозначает общее количество электронных писем, не являющихся спамом. Аналогично, $atn\; \{\backslash \; displaystyle\; a\_\; \{t\}\; ^\; \{n\}\}$обозначает количество появлений $n-го\; \{\backslash \; displaystyle\; n\; ^\; \{th\}\}$слово в спам-сообщениях, а $в\; \{\backslash \; displaystyle\; a\_\; \{t\}\}$обозначает общее количество спам-сообщений.

   Идентификация

   $N\; \{\backslash \; displaystyle\; N\}$формирует $P\; (W\; n\; \mid \; Спам)\; \{\backslash \; displaystyle\; P\; (W\_\; \{n\}\; \backslash \; mid\; \{\backslash \; text\; \{Spam\}\})\}$еще не решено полностью, потому что $2\; N\; +\; 2\; \{\backslash \; displaystyle\; 2N\; +\; 2\}$параметры $afn\; =\; 0,\; \dots ,\; N\; -\; 1\; \{\backslash \; displaystyle\; a\_\; \{f\}\; ^\; \{n\; =\; 0,\; \backslash \; ldots,\; N-1\}\}$, $atn\; =\; 0,\dots ,\; N\; -\; 1\; \{\backslash \; displaystyle\; a\_\; \{t\}\; ^\; \{n\; =\; 0,\; \backslash \; ldots,\; N-1\}\}$, $af\; \{\backslash \; displaystyle\; a\_\; \{f\}\}$и $at\; \{\backslash \; displaystyle\; a\_\; \{t\}\}$не имеют значений пока что.

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

   Метод может начать с начальных стандартных значений этих параметров, полученных из общих баз данных, количество инкрементного обучения настраивает классификатор каждого отдельного пользователя.

   Вопрос

   Вопрос, задаваемый программой: «какова вероятность того, что данный текст будет спамом, зная, какие слова появляются, а какие нет в этом тексте?» Его можно формализовать следующим образом:

   $P\; (Спам\; \mid \; w\; 0\; \wedge \; \cdots \; \wedge \; w\; N\; -\; 1)\; \{\backslash \; displaystyle\; P\; (\{\backslash \; text\; \{Spam\}\}\; \backslash \; mid\; w\_\; \{0\}\; \backslash \; wedge\; \backslash \; cdots\; \backslash \; wedge\; w\_\; \{N\; -1\})\}$

   который может быть вычислен следующим образом: