Original title: Equivalence Problem in Compositional Models
Translated title: Problém ekvivalentu v kompozitních modelech
Authors: Kratochvíl, Václav
Document type: Papers
Conference/Event: WUPES 2009, Liblice (CZ), 2009-09-19 / 2009-09-23
Year: 2009
Language: eng
Abstract: [eng] [cze]
Structure of each Compositional model can be visualized by a tool called persegram. Every persegram over a finite non-empty set of variables N induces an independence model over N, which is a list of conditional independence statements over N. The Equivalence problem is how to characterize (in graphical terms) whether all independence statements in the model induced by persegram P are in the model induced by a second persegram P' and vice versa. Three different operations preserving independence model were introduced in previous papers. If combined, one is able to generate the (whole) class of equivalent persegrams. This characterization is indirect: Two persegrams P,P' are equivalent if there exists a sequence of persegrams from P,P' such that only so called IE-operations are performed to get next persegram in the sequence. In this paper we give the motivation and introduction for direct characterization of equivalence. Persegram (speciální tabulka značek) zachycující strukturu kompozicionálního modelu nad množinou proměnných N indukuje množinu podmíněných nezávislostí - tzv. nezávislostní model nad N. Jak vyjádřit že dva dané persegramy indukují stejný nezávislostní model je označováno jako problém ekvivalence. V předchozích článcích byly zavedeny tři elementární operace nad persegramem zachovávající indukovaný nezávislostní model. Označujeme je jako IE-operace. Pomocí nich lze generovat celou třídu, ve výše uvedeném smyslu vekvivalentních, persegramů. Lze také odvodit tzv. nepřímou charakterizaci: Dva persegramy P,P' jsou ekvivalentí, pokud mezi P,P' existuje posloupnost persegramů taková, že pouze IE-operace byly použity aby se získa další persegram v řadě. V tomto článku najde čtenář náznak přímé charakterizace. Navzdory faktu, že finální přímá charakterizace není uvedena, je zavedeno několik invariantních vlastností ekvivalentních persegramů, které k přímé charakterizaci nejspíše povedou.
Keywords: Compositional model; Equivalence problem
Project no.: CEZ:AV0Z10750506 (CEP)
Host item entry: WUPES'09, ISBN 978-80-245-1543-4

Institution: Institute of Information Theory and Automation AS ČR (web)
Document availability information: Fulltext is available at external website.
External URL: http://library.utia.cas.cz/separaty/2009/MTR/kratochvil-equivalence problem in compositional models.pdf
Original record: http://hdl.handle.net/11104/0177030

Permalink: http://www.nusl.cz/ntk/nusl-40627


The record appears in these collections:
Research > Institutes ASCR > Institute of Information Theory and Automation
Conference materials > Papers