, где
P(x|z) - апостериорная вероятность (wiki);
P(z|x) - функция правдоподобия (зависит от данных, т.е. текущего изображения);
P(x) - априорная вероятность (не зависит от данных).
Фактически, проблему поиска лучшего разделения можно сформулировать таким образом:
(это формула и выражает MAP), или, что тоже самое
, где
E(x) - энергия изображения.
Рассмотрим каждую часть отдельно.
Функция правдоподобия
Данная функция при x = 0 или x = 1 показывает, относится ли текущий пиксель z к нужной нам области изображения. На рисунке справа можно это увидеть. Для улучшения результата нам необходимо найти максимум:
В результате должно получиться следующее:
Априорная вероятность
Этот параметр позволяет учитывать и соседние пиксели при сегментации. Соединим текущий пиксель с его соседями по вертикали и горизонтали. Тогда:
, где
- функция разделения;
- «Ising prior» (априорная вероятность Изинга, по подсказке yuriv).
При этом всем
Апостериорная вероятность
При определении данного слагаемого воспользуемся распределением Гиббса (wiki):, где
Энергия изображения, где первое слагаемое - значение энергии текущего пикселя самого по себе, а второе - суммарное значение с соседом; w - некий вес, значение которого определяется экспериментально;
Функция правдоподобия;
Априорная вероятность.
Фух, осталось совсем чуть-чуть, самое главное.
Минимизация энергии
Как мы установили в самом начале, минимум энергии соответствует MAP. В этом случае:(искомый минимум энергии)
Результаты
«Что это было и, главное, ЗАЧЕМ?!», спросит читатель. Вот что в итоге может получиться, с указанием разных значений веса w:
Выводы
Особая прелесть данного метода заключается в том, что формулы энергии мы можем задавать любые. Например, можно добиться выделения на изображении исключительно прямых линий, точек пересечения определенного числа прямых/кривых и многое другое. Кстати, любой счастливый обладатель MS Office 2010 может пощупать описанную технологию. Достаточно использовать инструмент Background Removal.Спасибо за внимание!
Уголок копирайтера
Все использованные изображения взяты из работ Carsten Rother. Формулы построены при помощи онлайнВопрос № 38. Полная группа событий. Формула полной вероятности. Формулы Байеса.
Двух событий. Независимость в совокупности. Формулировка теоремы умножения в этом случае.
Вопрос № 37. Условная вероятность. Теорема умножения. Определение независимости
Условная вероятность - вероятность одного события при условии, что другое событие уже произошло.
P(А│В)= р(АВ)/ р(В)
Условная вероятность отражает влияние одного события на вероятность другого.
Теорема умножения.
Вероятность произведения событий определяется формулой Р(А 1 ,А 2 ,….А n)= Р(А 1)Р(А 2/ А 1) …Р(А n / А 1 А 2… А n -1)
Для произведения двух событий отсюда следует, что
Р(АВ)=Р(А/В)Р{B)=Р(В/А)Р{А)
Если одно событие не зависит от другого, если появление одного из них не влияет на вероятность появления другого, то последнее также не зависит от первого. Это дает полное основания называть такие события независимыми. Математически независимость означает, что условная вероятность некоторого события совпадает с его вероятностью (безусловной вероятностью).
1.Говорят что событие А не зависит от события В если
P(А│В)=Р(А)
Если событие А не зависит от события В то и событие В не зависит от события А.
2.Если события А и В независимы то Р(АВ)=Р(А)Р(В)-это равенство используется для определения независимых событий.
Следует различать попарную независимость событий и независимость в совокупности.
События А1,А2,….Аn называются независимыми в совокупности если они попарно независимы и каждое из них не зависит от произведения любого набора из остальных событий.
Если события А1,А2,….Аn независимы в совокупности то
Р(А 1 ,А 2 ,….А n)=Р(А 1)Р(А 2)…Р(А n).
В каждой группе какое-либо событие в результате испытания обязательно произойдет, причем появление одного из них исключает появление всех остальных. Такие события называются полной группой событий.
Определение: Если группа событий такова, что в результате испытания обязательно должно произойти хотя бы одно из них, и любые два из них несовместны, то эта группа событий называется полной группой.
Каждое событие из полной группы называется элементарным событием. Каждое элементарное событие - равновозможное, т.к. нет оснований считать, что какое-либо из них более возможное, чем любое другое событие полной группы.
Два противоположных события составляют полную группу.
Относительной частотой события А называется отношение числа опытов, в результате которых произошло событие А к общему числу опытов.
Отличие относительной частоты от вероятности заключается в том, что вероятность вычисляется без непосредственного произведения опытов, а относительная частота – после опыта.
Формула полной вероятности
(где А – некоторое событие, Н1, Н2 … Hi – попарно несовместимы, образубт полную группу, причем А может произойти вместе с H1, H2 Hi)
P(A)=P(A|H 1) P(H 1)+P(A|H 2)P(H 2)+P(A|H 3)P(H 3)+…+P(A|H n)P(H n)
Формула Байеса
Р(Нi |A)= 
Замечание. События Нi называют гипотезами вероятности, р(Нi) – априорными вероятностями гипотез Нi, а вероятности Р(Нi/А) – апостериорными вероятностями гипотез Нi
Пусть известен результат опыта, а именно то, что произошло событие А. Этот факт может изменить априорные (то есть известные до опыта) вероятности гипотез. Для переоценки вероятностей гипотез при известном результате опыта используется формула Байеса:
Пример. После двух выстрелов двух стрелков, вероятности попаданий которых равны 0,6 и 0,7, в мишени оказалась одна пробоина. Найти вероятность того, что попал первый стрелок.
Решение. Пусть событие А – одно попадание при двух выстрелах,
а гипотезы: Н1 – первый попал, а второй промахнулся,
Н2 – первый промахнулся, а второй попал,
Н3 – оба попали,
Н4 – оба промахнулись.
Вероятности гипотез:
р(Н1) = 0,6·0,3 = 0,18,
р(Н2) = 0,4·0,7 = 0,28,
р(Н3) = 0,6·0,7 = 0,42,
р(Н4) = 0,4·0,3 = 0,12.
Тогда р(А/Н1) = р(А/Н2) = 1,
р(А/Н3) = р(А/Н4) = 0.
Следовательно, полная вероятность р(А) = 0,18·1 + 0,28·1 + 0,42·0 + 0,12·0 = 0,46.
Формула полной вероятности позволяет вычислить вероятность интересующего события через условные вероятности этого события в предположении неких гипотез, а также вероятностей этих гипотез.
Определение 3.1. Пусть событие А может произойти только совместно с одним из событий Н1, Н2,…, Нп, образующих полную группу несовместных событий. Тогда события Н1, Н2,…, Нп называются гипотезами.
Теорема 3.1. Вероятность события А, наступающего совместно с гипотезами Н1, Н2,…, Нп, равна:
где p(Hi) – вероятность i- й гипотезы, а p(A/Hi) – вероятность события А при условии реализации этой гипотезы. Формула (P(A)= ) носит название формулы полной вероятности
Вопрос № 39. Схема Бернулли. Вероятность m успехов в серии из n испытаний
Случайное событие
оценивают числом, определяющим
интенсивность проявления этого события.
Это число называют вероятностью
события P()
.
Вероятность элементарного события –
.
Вероятность события есть численная
мера степени объективности, возможности
этого события. Чем больше вероятность,
тем более возможно событие.
Любое событие, совпадающее со всем пространством исходов S , называетсядостоверным событием , т.е. таким событием, которое в результате эксперимента обязательно должно произойти (например, выпадение любого числа очков от 1 до 6 на игральной кости). Если событие не принадлежит множествуS , то оно считаетсяневозможным (например, выпадение числа очков, большего 6, на игральной кости). Вероятность невозможного события равна 0, вероятность достоверного события равна 1. Все остальные события имеют вероятность от 0 до 1.
События Е
и
называютсяпротивоположными
, еслиЕ
наступает
тогда, когда не наступает
.
Например, событиеЕ
– «выпадение
четного числа очков», тогда событие
– «выпадение нечетного числа очков».
Два событияЕ
1
иЕ
2
называютсянесовместными
, если
не существует никакого исхода, общего
для обоих событий.
Для определения вероятностей случайных событий используют непосредственные или косвенные способы. При непосредственном подсчете вероятности различают априорную и апостериорную схемы подсчетов, когда проводят наблюдения (опыты) или априорно подсчитывают число опытовm , в которых событие проявилось, и общее число произведенных опытовn . Косвенные способы основываются на аксиоматической теории. Поскольку события определяются как множества, то над ними можно совершать все теоретико-множественные операции. Теория множеств, функциональный анализ были предложены академиком А.Н. Колмогоровым и составили основу аксиоматической теории вероятности. Приведем аксиомы вероятностей.
Аксиома I . Поле событий F (S ) является алгеброй множеств .
Эта аксиома указывает на аналогию теории множеств и теории вероятности.
Аксиома
II
.
Каждому
множеству
из
F
(S
)
поставлено в соответствие действительное
число P(
),
называемое вероятностью события
:
при условии S 1 S 2 = (для несовместных событийS 1 иS 2 ), или для множества несовместных событий
где N – количество элементарных событий (возможных исходов).
Вероятность случайного события
|
|
,где
–
вероятности элементарных событий
,
входящих в подмножество
.
Пример 1.1. Определить вероятность выпадения каждого числа при бросании игральной кости, выпадения четного числа, числа4 .
Решение . Вероятность выпадения каждого числа из множества
S = {1, 2, 3, 4, 5, 6}
1/6.
Вероятность выпадения четного числа,
т.е.
={2,
4, 6},
исходя из (1.6)
будетP(
)
= 1/6 + 1/6 + 1/6 = 3/6 = 1/2
.
Вероятность выпадения числа 4
, т.е.
=
{4, 5, 6 }
,
P(
)
= 1/6 + 1/6 + 1/6 = 3/6 = 1/2.
Задания для самостоятельной работы
1. В корзине 20 белых, 30 черных и 50 красных шаров. Определите вероятность того, что первый вынутый из корзинки шар будет белым; черным; красным.
2. В студенческой группе 12 юношей и 10 девушек. Какова вероятность того, что на семинаре по теории вероятности будут отсутствовать: 1) юноша; 2) девушка; 3) два юноши?
3. В течение года 51 день отличался тем, что в эти дни шел дождь (или снег). Какова вероятность того, что вы рискуете попасть под дождь (или снег): 1) отправляясь на работу; 2) отправляясь в поход на 5 дней?
4. Составьте задачу на тему данного задания и решите ее.
1.1.3. Определение апостериорной вероятности (статистической вероятности или частоты
случайного события)
При априорном определении вероятности
предполагалось, что
равновероятны. Это далеко не всегда
соответствует действительности, чаще
бывает, что
при
.
Допущение
приводит к ошибке в априорном определенииP(
)
по установленной схеме. Для определения
,
а в общем случаеP(
)
проводят целенаправленные испытания.
В ходе проведения таких испытаний
(например, результаты испытаний в
примерах 1.2, 1.3) при различном состоянии
разнообразных условий, воздействий,
причинных факторов, т.е. в различныхслучаях,
могут возникнуть различныеисходы
(различные проявления сведений
исследуемого объекта).Каждый
исход испытаний соответствует одному
элементу
или одному подмножеству
множества S
.Если определять
m
как число
благоприятных событию А
исходов, полученных в результате n
испытаний, то апостериорная вероятность
(статистическая вероятность или частота
случайного события А
)
На основании закона больших чисел для
A
|
|
,
n
,т.е. при увеличении числа испытаний частота случайного события (апостериорная, или статистическая, вероятность) стремится к вероятности этого события.
Пример 1.2. Определенная по схеме случаев вероятность выпадения решки при подбрасывании монеты равна 0,5. Требуется подбросить монету 10, 20, 30 ... раз и определить частоту случайного события решка после каждой серии испытаний.
Решение . К. Пуассон подбрасывал монету 24000 раз, при этом решка выпадала 11998 раз. Тогда по формуле (1.7) вероятность выпадения решки
.
Задания для самостоятельной работы
На основании большого статистического материала (n ) были получены значения вероятностей появления отдельных букв русского алфавита и пробела () в текстах, которые приведены в табл.1.1.
Таблица 1.1. Вероятность появления букв алфавита в тексте
|
| ||||||||
|
| ||||||||
|
| ||||||||
|
|
Возьмите страницу любого текста и определите частоту появления различных букв на этой странице. Увеличьте объем испытаний до двух страниц. Полученные результаты сравните с данными таблицы. Сделайте вывод.
При стрельбе по мишеням был получен следующий результат (см. табл.1.2).
Таблица 1.2. Результат стрельбы по мишеням
Какова вероятность того, что цель была бы поражена с первого выстрела, если бы по своим размерам она была меньше «десятки», «девятки» и т.д.?
3. Спланируйте и проведите аналогичные испытания для других событий. Представьте их результаты.
1)Выборка вероятностей всех симптомов для предполагаемых заболеваний. Если заболеваний три (D1,D2,D3), то должно появиться три группы чисел:
P(S 2 /D 1) P(S 2 /D 2) P(S 2 /D 3)
P(S 7 /D 1) P(S 7 /D 2) P(S 7 /D 3)
P(S 9 /D 1) P(S 9 /D 2) P(S 9 /D 3)
Если симптомов много и много возможных диагнозов, что и бывает на практике, то один этот этап выборки осуществить без привлечения ЭВМ принципиально невозможно, что и сделало данный метод возможным лишь с использованием компьютерных технологий.
2)Вычисление условной вероятности симптомокомплекса P(S сi /D j). Вычисляют по формуле, известной из теории вероятностей. Условная вероятность симптомокомплекса представляет собой произведение вероятностей симптомов данного симптомокомплекса при данном диагнозе. Например, для симптомокомплекса из n симптомов для некоторого диагноза J:
P(S ci /Dj)= P(S 1 /D j)*P(S 2 /D j) * ... * P(S n /D j) (1)
Количество получаемых таки образом условных вероятностей равно количеству рассматриваемых в системе диагнозов (т.е. числу столбцов таблицы).
Определение априорной вероятности заболевания.
Априорной вероятностью некоторого диагноза (Dj) называют эмпирическую частоту наблюдения данного заболевания в некоторых конкретных условиях. Априорная вероятность обозначается P(D j) .Она характеризует распределение болезней в данной группе населения. Такой группой может быть контингент данной больницы, данного района, данного города. Априорной (доопытной) она называется потому, что уже известна до получения симптомокомплекса, т.е. к ней новый больной никакого отношения не имеет. Смысл введения в диагностику величины P(D j) состоит в том, что она непостоянна и зависит от географических, сезонных, эпидемиологических и других факторов, которые должны быть учтены при постановке диагноза. Например, в какой-либо больнице наугад было выбрано 100 человек, 70 из них оказались больны гриппом. Значит, вероятность заболевания гриппом у всех пациентов в данной больнице будет равна 70/100=0,7, когда эпидемия гриппа будет ликвидирована, естественно и P(D j) для гриппа в этой больнице будет другой. Величина априорной вероятности диагноза является одной из величин, которая в процессе работы диагностической системы требует мониторинга и текущей коррекции.
Вычисление нормировочного коэффициента (Psc).
Нормировочный коэффициент представляет собой полную вероятность наличия симптомокомплекса при всех заболеваниях. Эта величина несет математический смысл, представляя собой полную сумму попарных произведений условных вероятностей симптомокомплекса для данного диагноза на априорную вероятность этого диагноза:
Psc = P(S сi /D 1) * p(D 1)+ P(S сi /D 2) * p(D 2)+ …+P(S сi /D n) * p(D n)
Полное количество слагаемых в данной сумме равно числу диагнозов, рассматриваемых в данной системе.
5)Вычисление вероятностей диагнозов при данном симптомокомплексе (P(D j /S ci)).
Данный этап являет предпоследним в схеме функционирования системы и основан на использовании теоремы Байеса (формула вероятности гипотез):
P(D j /S ci)=[ P(S сi /D j) x P(D j)] / [ P(Sc) ]
Количество вероятностей диагнозов равно числу диагнозов системы. Иными словами в результате данного этапа работы система вычисляет вероятность каждого из имеющихся диагнозов.
Постановка диагноза.
Этап является наиболее простым и основан на простом сравнении полученных на этапе (5) величин. Наибольшая величина и указывает на тот диагноз, который наиболее вероятен при данном симптомокомплексе. Теоретически возможны случаи, когда вероятность нескольких диагнозов равна. В этом случае необходимо говорить о том, что диагностическая таблица, использующаяся в системе недостаточно совершенна, чтобы “различить” эти диагнозы.