The Grow-Shrink Strategy for Learning Markov Network Structures Constrained by Context-Specific Independences
| Autor: | Alejandro Edera, Facundo Bromberg, Yanela Strappa |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Structure (mathematical logic)
Theoretical computer science Computational complexity theory Markov chain Computer science business.industry Machine learning computer.software_genre Set (abstract data type) Knowledge extraction Canonical model Probability distribution Artificial intelligence Representation (mathematics) business computer |
| Zdroj: | Advances in Artificial Intelligence--IBERAMIA 2014 ISBN: 9783319120263 IBERAMIA |
| DOI: | 10.1007/978-3-319-12027-0_23 |
| Popis: | Markov networks are models for compactly representing complex probability distributions. They are composed by a structure and a set of numerical weights. The structure qualitatively describes independences in the distribution, which can be exploited to factorize the distribution into a set of compact functions. A key application for learning structures from data is to automatically discover knowledge. In practice, structure learning algorithms focused on “knowledge discovery” present a limitation: they use a coarse-grained representation of the structure. As a result, this representation cannot describe context-specific independences. Very recently, an algorithm called CSPC was designed to overcome this limitation, but it has a high computational complexity. This work tries to mitigate this downside presenting CSGS, an algorithm that uses the Grow-Shrink strategy for reducing unnecessary computations. On an empirical evaluation, the structures learned by CSGS achieve competitive accuracies and lower computational complexity with respect to those obtained by CSPC. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|