ECAI 2004 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Yet more efficient EM learning for parameterized logic programs by inter-goal sharing

Yoshitaka Kameya, Taisuke Sato, Neng-Fa Zhou

In the previous research, we presented a graphical EM algorithm for parameterized logic programs, which is based on the structure sharing with tabled search. Also it is shown that this general framework achieves the same time complexity as that of the specialized algorithms, e.g. the Baum-Welch algorithm for hidden Markov models(HMMs). The efficiency is brought by sharing the common paths in the derivation tree for a given goal, but such sharing is incomplete in the sense that it is not allowed to share the paths appearing in the different derivation trees. In this paper, we introduce a general idea of `inter-goal sharing' where the different goals can share the common derivation paths. Inter-goal sharing achieves the full sharing of derivation paths and hence makes EM learning more compact and efficient in practical cases. Then, for PRISM programs, we present a simple implementation of inter-goal sharing, which can be justified both logically and statistically. Finally we show the experimental results with two typical and widely-applied statistical language models, i.e. HMMs and probabilistic context-free grammars. For both artificial and real linguistic data, it is found out that the proposed method runs 2-6 times more compactly and faster than the previous approach.

Keywords: EM algorithm, Tabled search, Structure sharing, Dynamic programming, Statistical language models

Citation: Yoshitaka Kameya, Taisuke Sato, Neng-Fa Zhou: Yet more efficient EM learning for parameterized logic programs by inter-goal sharing. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.490-494.

[prev] [tofc] [next]

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).