A new Bayesian tree construction : method with decreased time complexity

• Autorzy: Kłopotek, M.

Warianty tytułu

PL

Nowa metoda konstrukcji drzew bayesowskich o zredukowanym czasie wykonania

• Języki publikacji: PL

Abstrakty

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.

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.

Słowa kluczowe

PL

systemy uczące się; sieci bayesowskie; algorytm Chow/Liu; złożoność przestrzenna; złożoność czasowa

EN

machine learning; Bayesian networks; Chow/Liu algorithm; time and space complexity

• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2001
• Tom: Nr 927
• Strony: 1-11

Twórcy

autor

Kłopotek, M.

• Instytut Podstaw Informatyki PAN ul. Ordona 21 01-237 Warszawa,