On the Influence of the Variable Ordering for Algorithmic Learning using OBDDs
Result description
OBDDs with a fixed variable ordering are used successfully as data structure in experiments with learning heuristics based on examples. In this paper, it is shown that, for some functions, it is necessary to develop an algorithm to learn also a good OBDDvariable ordering. There are functions with the following properties. They have OBDDs of linear size for optimal variable orderings. But for all but a small fraction of all variable orderings one needs large size to represent a list of randomly chosen examples. These properties are shown for simple functions like the multiplexer and the inner product.
Keywords
The result's identifiers
Result code in IS VaVaI
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On the Influence of the Variable Ordering for Algorithmic Learning using OBDDs
Original language description
OBDDs with a fixed variable ordering are used successfully as data structure in experiments with learning heuristics based on examples. In this paper, it is shown that, for some functions, it is necessary to develop an algorithm to learn also a good OBDDvariable ordering. There are functions with the following properties. They have OBDDs of linear size for optimal variable orderings. But for all but a small fraction of all variable orderings one needs large size to represent a list of randomly chosen examples. These properties are shown for simple functions like the multiplexer and the inner product.
Czech name
Vliv uspořádání proměnných na algoritmické učení pomocí OBDD
Czech description
OBDD s pevně zvoleným uspořádáním proměnných jsou úspěšně používány jako datová struktura v experimentech s heuristikami na učení na základě příkladů. V tomto článku je ukázáno, že pro některé funkce je potřeba vyvinout také algoritmus pro nalezení dobrého uspořádání proměnných. Existují funkce s následujícími vlastnostmi. Mají OBDD lineární velikosti pro optimální uspořádání proměnných. Na druhé straně, pro převážnou většinu uspořádání proměnných je nezbytné veliké OBDD pro reprezentaci seznamu náhodněvybraných příkladů. Tyto vlastnosti jsou dokázány pro funkce multiplexoru a vnitřního součinu.
Classification
Type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
GA201/98/0717: Computational models and complexity of computations
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2005
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Information and Computation and Information and Control
ISSN
0890-5401
e-ISSN
—
Volume of the periodical
201
Issue of the periodical within the volume
-
Country of publishing house
US - UNITED STATES
Number of pages
18
Pages from-to
160-177
UT code for WoS article
—
EID of the result in the Scopus database
—
Basic information
Result type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP
BA - General mathematics
Year of implementation
2005