Байесови мрежи: определение, примери и принципи на действие

ефективност

Ефективни алгоритми могат да извършват изводи и обучение в бейсови мрежи. Мрежите, които моделират променливи (напр. речеви сигнали или протеинови последователности), се наричат динамични мрежи. Обобщенията на Байесовите мрежи, които могат да представят и решават проблеми в условията на неопределеност, се наричат диаграми на влиянието.

Същността на

Формално погледнато, байесовите мрежи са групи от бази данни с достъпност, чиито възли представляват променливи в байесов смисъл: те могат да бъдат наблюдаеми, латентни променливи, неизвестни параметри или хипотези. Ето защо е толкова интересно.

Пример за Бейсова мрежа

Две събития могат да причинят мокра трева: активен разпръсквач или дъжд. Дъждът оказва пряко влияние върху използването на разпръсквача (а именно, че когато вали, разпръсквачът обикновено не е активен). Тази ситуация може да се моделира с помощта на мрежа на Бейс.

Моделиране

Тъй като мрежата на Бейс е пълен модел на променливите и техните взаимоотношения, тя може да се използва за отговор на вероятностни запитвания за тях. Например, тя може да се използва за актуализиране на знанията за състоянието на подмножество променливи, когато се наблюдават други данни (доказателствени променливи). Този интересен процес се нарича вероятностен извод.

A posteriori дава универсално достатъчна статистика за приложения за откриване при избора на стойности за подмножество от променливи. По този начин този алгоритъм може да се разглежда като механизъм за автоматично прилагане на теоремата на Бейс към сложни проблеми. На снимките в статията можете да видите примери за мрежи на доверието на Бейс.

Методи за извод

Най-разпространените методи за точен извод са: изключване на променливи, при което се елиминират (чрез интегриране или сумиране) ненаблюдаемите параметри, които не са от значение за заявката, един по един, като сумата се разпределя върху произведението.

Разпространение "дърво" кликване, което кешира изчисленията, така че много променливи да могат да бъдат търсени едновременно и новите доказателства да се разпространяват бързо; и рекурсивно съвпадение и/или търсене, което позволява компромис между пространство и време и съответства на ефективността на изключването на променливи, когато се използва достатъчно пространство.

Всички тези методи имат специфична сложност, която зависи експоненциално от дължината на мрежата. Най-често срещаните Алгоритмите за приблизително заключение са методи като елиминиране на мини сегменти, кръгово разпространение на убеждения, обобщено разпространение на последните и вариационни методи.

Работа с мрежи

За да се определи напълно една Бейсова мрежа и по този начин да се представи напълно съвместното разпределение на вероятностите, е необходимо за всеки възел X да се определи разпределението на вероятностите за X, обусловено от родителите на X.

Разпределението на X, обусловено от родителите му, може да има всякаква форма. Обикновено се работи с дискретни или Гаусови разпределения, тъй като това опростява изчисленията. Понякога са известни само ограниченията на разпределението. След това ентропията може да се използва за определяне на единственото разпределение, което има най-висока ентропия, като се имат предвид ограниченията.

По подобен начин, в конкретния контекст на динамична Бейсова мрежа, условното разпределение за времевата еволюция на скритото състояние обикновено се задава така, че да максимизира степента на ентропия на предполагаемия случаен процес.

Директното максимизиране на вероятността (или на апостериорната вероятност) често е трудно поради наличието на ненаблюдаеми променливи. Това е особено характерно за мрежата на Бейс вземане на решения.

Класическият подход

Класическият подход към този проблем е алгоритъмът за максимизиране на очакванията, при който се редуват изчисляване на очакваните стойности на ненаблюдаеми променливи, които зависят от наблюдаваните данни, и максимизиране на общата вероятност (или апостериорна стойност), като се приема, че предварително изчислените очаквани стойности са верни. При умерена закономерност този процес води до максималните (или максималните апостериорни) стойности на параметрите.

По-пълен Бейсовски подход към параметрите е да ги разглеждаме като допълнителни ненаблюдавани променливи и да изчислим пълното апостериорно разпределение за всички възли, като се имат предвид наблюдаваните данни, след което да интегрираме параметрите. Този подход може да бъде скъп и да доведе до големи модели, което прави класическите подходи за настройка на параметрите по-достъпни.

В най-простия случай Байесовата мрежа се дефинира от експерт и след това се използва за извършване на изводи. В други приложения задачата за откриване е твърде сложна за хората. В този случай структурата на невронната мрежа на Бейс и параметрите на локалните разпределения трябва да бъдат научени сред данните.

Алтернативен метод

Алтернативен метод за структурно обучение използва оптимизационно търсене. Това изисква функция за оценка и стратегия за търсене. Често срещан алгоритъм за оценка е апостериорната вероятност на структурата при наличие на данни за обучение, като BIC или BDeu.

Времето, необходимо за изчерпателно търсене, което връща структура, която максимизира оценката, е свръхекспоненциално на броя на променливите. Стратегията за локално търсене прави постепенни промени, за да подобри оценката на структурата. Фридман и колегите му разглеждат възможността за използване на взаимната информация между променливите за намиране на правилната структура. Те ограничават набора от кандидати за родители до k възела и търсят внимателно в тях.

Особено бърз метод за точна BN е представянето на проблема като оптимизационна задача и решаването му чрез целочислено програмиране. Ацикличните ограничения се добавят към целочисленото програмиране (ЦП) по време на решаването под формата на равнини на рязане. Такъв метод може да решава задачи с до 100 променливи.

решаване на проблеми

За решаване на проблеми с хиляди променливи, е необходим различен подход. Една от тях е, че, за да може първо да да изберете един ред и след това да намерите оптималната структура на BN спрямо този ред. Това предполага работа в пространството за търсене на възможни подредби, което е удобно, защото е по-малко от пространството на мрежовите структури. След това се избират и оценяват няколко поръчки. Този метод се оказа най-добрият в литературата, когато броят на променливите е огромен.

Друг метод е да се съсредоточим върху подклас от разложими модели, за които MLE имат затворена форма. Тогава е възможно да се намери последователна структура за стотици променливи.

Обучение на бейсови мрежи с ограничена ширина от три реда е необходимо да се осигури точен и лесен извод, тъй като сложността на последния в най-лошия случай е експоненциална по дължината на дървото k (съгласно хипотезата за експоненциалното време). Въпреки това, като глобално свойство на графа, то значително увеличава сложността на процеса на обучение. В този контекст К-дървото може да се използва за ефективно изучаване на.

Развитие

Разработването на бейсовска мрежа на доверие често започва със създаването на DAG G, така че X да удовлетворява локалното свойство на Марков по отношение на G. Понякога това е причинно-следствена DAG. Условните вероятностни разпределения на всяка променлива по нейните родители в G. В много случаи, особено когато променливите са дискретни, ако съвместното разпределение на X е произведение на тези условни разпределения, тогава X се превръща в Бейсова мрежа по отношение на G.

Марковски "одеяло за възли" - този набор от възли. Марковското одеяло прави даден възел независим от останалите под формата на възел със същото име и е достатъчно знание, за да се изчисли неговото разпределение. X е Байесова мрежа по отношение на G, ако всеки възел е условно независим от всички останали възли, като се има предвид марковското му одеяло.