The impact of state merging on predictive accuracy in probabilistic tree automata : Dietze’s conjecture revisited

• Dietze’s conjecture concerns the problem of equipping a tree automaton M with weights to make it probabilistic, in such a way that the resulting automaton N predicts a given corpus C as accurately as possible. The conjecture states that the accuracy cannot increase if the states in M are merged with respect to an equivalence relation ∼ so that the result is a smaller automaton M∼. Put differently, merging states can never improve predictions. This is under the assumption that both M and M∼ are bottom-up deterministic and accept every tree in C. We prove that the conjecture holds, using a construction that turns any probabilistic version N∼ of M∼ into a probabilistic version N of M, such that N assigns at least as great a weight to each tree in C as N∼ does.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

Nyckelord

Probability distributions

Statistical ML

Tree automata

Publikations- och innehållstyp

ref (ämneskategori)

kon (ämneskategori)