(В настоящее время это просто заметка). LW используется для вычисления апостериорного распределения, это больше похоже на метод выборки, основанный на доказательствах, чтобы сократить вычислительную сложность по сравнению с выборкой Гиббса. Следующий контент включает один пример LW с http://www.eng.utah.edu/~mccully/cs5300lw/.

Вероятность взвешивания

Цель этой веб-страницы — предоставить подробный пример взвешивания правдоподобия. Подготовлено Дуэйном А. Маккалли, Университет штата Юта, весна 2009 г.

Образец сети

Рассмотрим сеть сигнализации (стр. 494, рис. 14.2).

Генерация весов правдоподобия

Простое описание алгоритма взвешивания правдоподобия, описанного на странице 515 (рис. 14.14), выглядит следующим образом:

Во время выборки сети состояние одних узлов будет известно, а других нет. Узлы, значения которых известны, называются переменными свидетельства. Итак, учитывая доказательства, нам нужно запросить оставшиеся узлы, чтобы определить состояние всей сети. Когда это завершено, этой выборке присваивается вес вероятности путем перемножения вероятностей каждой переменной свидетельства с учетом ее родителей. Этот результат сохраняется в карте, которую мы назовем W, которая связывает все переменные в сети со своим весом. Чуть подробнее:

  1. Временная переменная w имеет значение 1. В ней будет храниться рассчитанный вес этой выборки.
  2. Временная переменная x установлена ​​пустой. Это будет содержать состояние каждого узла для этого образца. Например, если бы состояние сети, включая переменные-свидетельства и переменные, которые были запрошены, было следующим: Ограбление=false, Землетрясение=false, Тревога =false, JohnCalls=true, MaryCalls=false, это можно представить как x = (~b,~e, ~а,j,~m).
  3. Проверяется каждый узел в сети. Если узел является доказательством, то выполняем следующий расчет:
  4. w = wp(currentNode | родители текущего узла)
  5. Если текущий узел не является свидетельством, то он выбирается для определения его состояния. Это не влияет на расчет веса.
  6. Независимо от того, является ли рассматриваемый узел свидетельством или его состояние обнаружено путем выборки, его состояние добавляется к x.

7. После того, как вся сеть будет проверена для этого образца, у нас останутся x и w, представляющие состояние сети и вес вероятности, который будет связан с этим состояние соответственно. Это добавляется к W с использованием x в качестве ключа и w в качестве значения данных. Если x уже существует в W, то w добавляется к значению данных, связанному с x в В.

Теперь мы создадим набор образцов для вышеупомянутой сети тревог:

Образец 1

  1. Доказательства: Взлом=false и Землетрясение=false. Теперь мы запросим оставшиеся узлы в сети, чтобы определить их состояние.
  2. Теперь мы устанавливаем вес w равным 1,0 и x пустым.
  3. Взлом – это переменная-указатель со значением false. Поэтому мы устанавливаем
    w = wp(Burglary=False) = (1,0)(0,999) = 0,999
    x = (~b).
  4. Землетрясение – это переменная-свидетельство со значением false. Поэтому мы устанавливаем
    w = wp(Earthquake=False) = (0,999)(0,998) = 0,997
    x = (~b,~e).
  5. Мы получаем выборку из p(Тревога|Ограбление=false), Землетрясение=false) = ‹0,001, 0,999›; предположим, что это возвращает false.
    x = (~b,~e,~a).
  6. Мы выбираем из p(JohnCalls|Alarm=false) = ‹0,05, 0,95›; предположим, что это возвращает false.
    x = (~b,~e,~a,~j).
  7. Мы делаем выборку из p(MaryCalls|Alarm=false) = ‹0,01, 0,99›; предположим, что это возвращает false.
    x = (~b,~e,~a,~j,~m).

В этом примере взвешенная выборка: Ограбление=false, Землетрясение=false, Тревога=false, JohnCalls=false, MaryCalls=false с весом 0,997. Теперь в книге говорится о «W, векторе взвешенных значений над X». Таким образом, в соответствии с этой терминологией мы думаем об отображении в C++, ключом которого является кортеж (~b,~e,a,j,m), а отображаемым значением является вес. Или, в питоне, объект dict(). Любой вес, вычисленный с помощью описанного выше алгоритма, добавляется к любому существующему весу, соответствующему ключу в W. Поскольку это наш первый образец, в W нет такого ключа, поэтому существующий вес фактически равен нулю. Вот как выглядит W на данный момент (пример столбца для удобства ссылок): W SampleKeyWeight 1~b~e~a~ j~m0,997

Образец 2

  1. Доказательства: Тревога=false и JohnCalls=true. Теперь мы запросим оставшиеся узлы в сети, чтобы определить их состояние.
  2. Теперь мы устанавливаем вес w равным 1,0 и x пустым.
  3. Кража со взломом не является свидетельствующей переменной, поэтому мы выбираем ее; предположим, что он возвращает false.
    x = (~b).
  4. Землетрясение не является свидетельствующей переменной, поэтому мы выбираем ее; предположим, что он возвращает false.
    x = (~b,~e).
  5. Тревога – это переменная-свидетельство со значением false. Поэтому мы устанавливаем
    w = wp(Тревога=false | Взлом=false, Землетрясение=ложь) = (1,0)(0,999) = 0,999
    x = (~b,~e,~a).
  6. JohnCalls – это свидетельствующая переменная со значением true. Поэтому мы устанавливаем
    w = wp(JohnCalls=true | Alarm=false) = (0,999)(0,05) = 0,05
    x = (~b,~e,~a,j).
  7. MaryCalls не является свидетельствующей переменной, поэтому мы выбираем ее; предположим, что он возвращает false.
    x = (~b,~e,~a,j,~m).

Основываясь на вышесказанном, теперь мы добавляем (~b,~e,~a,j,~m) к W с весом 0,05: W SampleKeyWeight 1~b~ e~a~j~m0,997 2~b~e~aj~m0,05

Образец 3

  1. Доказательства: JohnCalls=true и MaryCalls=true. Теперь мы запросим оставшиеся узлы в сети, чтобы определить их состояние.
  2. Теперь мы устанавливаем вес w равным 1,0 и x пустым.
  3. Кража со взломом не является свидетельствующей переменной, поэтому мы выбираем ее; предположим, что он возвращает false.
    x = (~b).
  4. Землетрясение не является свидетельствующей переменной, поэтому мы выбираем ее; предположим, что он возвращает false.
    x = (~b,~e).
  5. Тревога не является свидетельствующей переменной, поэтому мы выбираем ее; предположим, что он возвращает true.
    x = (~b,~e,a).
  6. JohnCalls – это свидетельствующая переменная со значением true. Поэтому мы устанавливаем
    w = wp(JohnCalls=true | Alarm=true) = (1,0)(0,90) = 0,90
    x = (~b,~e,a,j).
  7. MaryCalls – это свидетельствующая переменная со значением true. Поэтому мы устанавливаем
    w = wp(MaryCalls=true | Alarm=true) = (0,90)(0,70) = 0,63
    x = (~b,~e,a,j,m).

Основываясь на вышесказанном, теперь мы добавляем (~b,~e,a,j,m) к W с весом 0,63: W SampleKeyWeight 1~b~e~ a~j~m0,997 2~b~e~aj~m0,05 3~b~eajm0,63

Образец 4

  1. Доказательства: Взлом=false, Землетрясение=false и JohnCalls=true. Теперь мы запросим оставшиеся узлы в сети, чтобы определить их состояние.
  2. Теперь мы устанавливаем вес w равным 1,0 и x пустым.
  3. Взлом – это переменная-указатель со значением false. Поэтому мы устанавливаем
    w = wp(Burglary=False) = (1,0)(0,999) = 0,999
    x = (~b).
  4. Землетрясение – это переменная-свидетельство со значением false. Поэтому мы устанавливаем
    w = wp(Earthquake=False) = (0,999)(0,998) = 0,997
    x = (~b,~e).
  5. Тревога не является свидетельствующей переменной, поэтому мы выбираем ее; предположим, что он возвращает false.
    x = (~b,~e,~a).
  6. JohnCalls – это свидетельствующая переменная со значением true. Поэтому мы устанавливаем
    w = wp(JohnCalls=true | Alarm=false) = (0,997)(0,05) = 0,05
    x = (~b,~e,~a,j).
  7. MaryCalls не является свидетельствующей переменной, поэтому мы выбираем ее; предположим, что он возвращает false.
    x = (~b,~e,~a,j,~m).

Основываясь на вышеизложенном, теперь мы добавляем (~b,~e,~a,j,~m) к W с весом 0,05. Однако обратите внимание, что (~b,~e,~a,j,~m) соответствует ключу для выборки 2. Следовательно, вес 0,05 добавляется к существующему весу 0,05, что дает 0,10: W SampleKeyWeight 1~b~e~a~j~m0,997 2~b~e~aj~m0,10 3~b~eajm0,63

Образец 5

  1. Доказательства: Кража со взломом=true и Землетрясение=false. Теперь мы запросим оставшиеся узлы в сети, чтобы определить их состояние.
  2. Теперь мы устанавливаем вес w равным 1,0 и x пустым.
  3. Взлом – это переменная-указатель со значением true. Поэтому мы устанавливаем
    w = wp(Burglary=True) = (1,0)(0,001) = 0,001
    x = (б).
  4. Землетрясение – это переменная-свидетельство со значением false. Поэтому мы устанавливаем
    w = wp(Earthquake=False) = (0,001)(0,998) = 0,001
    x = (b,~e).
  5. Тревога не является свидетельствующей переменной, поэтому мы выбираем ее; предположим, что он возвращает false.
    x = (b,~e,~a).
  6. JohnCalls не является свидетельствующей переменной, поэтому мы выбираем ее; предположим, что он возвращает false.
    x = (b,~e,~a,~j,~m).
  7. MaryCalls не является свидетельствующей переменной, поэтому мы выбираем ее; предположим, что он возвращает false.
    x = (b,~e,~a,~j,~m).

Основываясь на вышеизложенном, теперь мы добавляем (b,~e,~a,~j,~m) к W с весом 0,001. W SampleKeyWeight 1~b~e~a~j~m0,997 2~b~e~aj~m0,10 3~b~eajm0,63 4b~e ~a~j~m0.001

Использование весов правдоподобия

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

  • Чтобы вычислить вероятность независимого события, такого как P(Взлом=истина), мы суммируем веса для каждой выборки, где Взлом=истина, и делим на сумма всех весов. Например, в приведенных выше данных единственная выборка, в которой Burglary=true, — это выборка 4 с весом 0,001. Следовательно, p(Кража со взломом=true) = (0,001) / (0,997 + 0,10 + 0,63 + 0,001) = 0,001 / 1,728 = 0,00058
  • Чтобы вычислить вероятность события X=true, которое зависит от другого события, Y=true, мы суммируем веса всех выборок, где X=true и Y=true и разделите его на сумму весов всех выборок, где Y=true. Например, если мы хотим вычислить p(a | j), нам нужно просуммировать веса всех выборок, где у нас есть и a, и j (что означает Alarm=True и JohnCalls=True ). Мы находим, что только выборка 3 соответствует этому критерию с весом 0,63. Теперь суммируем веса всех выборок, содержащих j. Только образцы 2 и 3 соответствуют этому критерию с весами 0,10 и 0,63 соответственно. Собрав все это вместе, мы имеем p(a | j) = 0,63/(0,10 + 0,63) = 0,63/0,73 = 0,863.
  • В приведенных выше данных вероятность события, которое никогда не наблюдалось, равна нулю. Это потому, что у нас есть информация о каждом узле в сети сигнализации в каждой выборке. Например, если мы хотим вычислить p(b | a), нам нужно просуммировать веса для всех выборок, где у нас есть и b, и a. Таких образцов нет. Следовательно, сумма равна нулю, а вероятность равна нулю.

Книга

Искусственный интеллект — современный подход
Второе издание
Стюарт Дж. Рассел и Питер Норвиг
Прентис Холл, Pearson Education, Inc., Нью-Джерси
2003 ISBN 0–13–790395–2

использованная литература

Страница 514 книги.
День 17 Слайды 32–35