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

Abstract

Розроблено інструментарій та алгоритм відтворення ймовірнісних моделей залежностей у класі монопотокових структур (підкласі баєсових мереж). Алгоритм «Proliferator-D» обчислювально ефективний (субкубічної складності) і виконує невелику кількість тестів умовної незалежності тільки першого рангу. Коректність алгоритму обґрунтовується простими припущеннями, емпірично робастними до обсягу вибірки даних. Коли генеративна модель виходить за рамки монопотокових структур, алгоритм плавно деградує до відомого алгоритму Крускала і виводить покриття (апроксимацію) моделі деревом. Запропонований алгоритм нескладно модифікувати з метою підвищення якості редукції (апроксимації) баєсових мереж.

We have developed technique and algorithm for recovery of probabilistic dependency models in class of mono-streams structures (subclass of Bayesian nets) from data. The «Proliferator-D» algorithm is of sub-cubic complexity and needs to execute a first-order independence tests only. The algorithm is justified by simple assumptions and is robust against data sample size. When generic model goes beyond class of mono-streams structures, the algorithm gracefully degrades to Kruskal algorithm and would infer a spanning tree model. Proposed algorithm may be easily modified to improve approximation of Bayesian nets.