PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

A new Bayesian tree construction : method with decreased time complexity

Autorzy
Wybrane pełne teksty z tego czasopisma
Warianty tytułu
PL
Nowa metoda konstrukcji drzew bayesowskich o zredukowanym czasie wykonania
Języki publikacji
PL
Abstrakty
PL
Sieci bayesowskie mają wiele praktycznych zastosowań związanych z ich zdolnością do zwartej reprezentacji rozkładów prawdopodobieństwa w wielu zmiennych. Istnieją efektywne metody wnioskowania w sieciach bayesowskich. Opracowano wiele algorytmów uczenia sieci z danych. Znanym problemem sieci bayesowskich są ograniczenia co do ilości zmiennych, dla których algorytmy uczące działają w rozsądnym czasie. Wyjątkiem jest tu algorytm Chow/Liu generujący drzewiaste sieci bayesowskie. Niestety, jego kwadratowa złożonośc obliczeniowa w liczbie zmiennych jest poważnym ograniczeniem dla wielu nowych zastosowań wielowymiarowych. W pracy przedstawiony jest nowy algorytm uczenia sieci drzewiastych z danych, który ma liniowe zużycie pamięci, a jednocześnie czas jego wykonania jest proporcjonalny do n ln(n). Zarówno złożoność czasowa jak i przestrzenna przewyższa parametry algorytmu Chow/Liu. Stwarza to nowe perspektywy zastosowań w sytuacjach, gdy trzeba tworzyć sieci liczące dziesiątki tysięcy i więcej węzłów, np. automatycznej kategoryzacji tekstów.
EN
Bayesian networks have many practical applications due to their capability to represent joint probability distribution in many variables in a compact way. There exist efficient reasoning methods for Bayesian networks. Many algorithms for learning Bayesian networks from empirical data have been developed. A well-known problem with Bayesian networks is the practical limitation for the number of variables for which a Bayesian network can be learned in reasonable time. A remarkable exception here is the Chow/Liu algorithm learning tree-like Bayesian networks. However, its quadratic time and space complexity in the number of variables may prove also prohibitive for high dimensional data. The paper presents a novel algorithm overcoming this limitation for the tree-like class of Bayesian networks. The new algorithm space consumption grows linearly with the number of variables n while the execution time is proportional to n ln (n), hence both are better than those of Chow/Liu algorithm. This opens new perspectives in construction of Bayesian networks from data containing tens of thousands and more variables, e.g. in automatic text categorization.
Twórcy
autor
Identyfikator YADDA
bwmeta1.element.baztech-article-BUJ1-0010-0041