Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: algorytm Chow/Liu

Sortuj według:

Ogranicz wyniki do:

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

Kłopotek M.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

2001

Nr 925

1-8

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.

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.

A new Bayesian tree construction : method with decreased time complexity

Kłopotek M.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

2001

Nr 927

1-11

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.

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.