A new space-saving bayesian tree construction : method for high dimensional spaces

• Autorzy: Kłopotek M.

Warianty tytułu

PL

Nowa metoda konstrukcji drzew bayesowskich z danych dla przestrzeni wysokowymiarowych

• 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 poważnym ograniczeniem dla wielu nowych zastosowań jest tu wymagana pamięć, która rośnie z kwadratem liczby zmiennych. 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 porównywalny z algorytmem Chow/Liu. Stwarza to nowe perspektywy zastosowań w sytuacjach gdy trzeba tworzyć sieci liczące tysiące 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, also this algorithm has an important limitation, related to space consumption. The space required is quadratic in the number of variables. 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 while the execution time is comparable with the Chow/Liu algorithm. This opens new perspectives in construction of Bayesian networks from data containing thousands and more variables, e.g. in automatic text categorization.

Słowa kluczowe

PL

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

EN

machine learning; Bayesian networks; Chow/Liu algorithm; spatial complexity

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2001
• Tom: Nr 925
• Strony: 1--8

Twórcy

autor

Kłopotek M.

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