Low-rank approximation of weighted tree automata
We describe a technique to minimize weighted tree automata (WTA), a powerful formalisms
that subsumes probabilistic context-free grammars (PCFGs) and latent-variable PCFGs. Our
method relies on a singular value decomposition of the underlying Hankel matrix defined by
the WTA. Our main theoretical result is an efficient algorithm for computing the SVD of an
infinite Hankel matrix implicitly represented as a WTA. We evaluate our method on real-
world data originating in newswire treebank. We show that the model achieves lower …
that subsumes probabilistic context-free grammars (PCFGs) and latent-variable PCFGs. Our
method relies on a singular value decomposition of the underlying Hankel matrix defined by
the WTA. Our main theoretical result is an efficient algorithm for computing the SVD of an
infinite Hankel matrix implicitly represented as a WTA. We evaluate our method on real-
world data originating in newswire treebank. We show that the model achieves lower …
[PDF][PDF] Low-Rank Approximation of Weighted Tree Automata (Supplementary Material)
Proof. Let n= rank (f). Let B be an arbitrary minimal WTA computing f. Suppose B induces the
rank factorization Hf= PS. Since the columns of both P and P are basis for the column-span
of Hf, there must exists a change of basis Q∈ Rn× n between P and P. That is, Q is an
invertible matrix such that PQ= P. Furthermore, since PS= Hf= PS= P QS and P has full
column rank, we must have S= QS, or equivalently, Q− 1S= S. Thus, we let A= Bq, which
immediately verifies fA= fB= f. It remains to be shown that A induces the rank factorization …
rank factorization Hf= PS. Since the columns of both P and P are basis for the column-span
of Hf, there must exists a change of basis Q∈ Rn× n between P and P. That is, Q is an
invertible matrix such that PQ= P. Furthermore, since PS= Hf= PS= P QS and P has full
column rank, we must have S= QS, or equivalently, Q− 1S= S. Thus, we let A= Bq, which
immediately verifies fA= fB= f. It remains to be shown that A induces the rank factorization …
Showing the best results for this search. See all results