Comments on: Extracting Weighted Automata for Approximate Minimization in Language Modelling https://icgi2020.lis-lab.fr August 23-27, 2021 Tue, 31 Aug 2021 11:11:47 +0000 hourly 1 https://wordpress.org/?v=7.1 By: Anonymous https://icgi2020.lis-lab.fr/extracting-weighted-automata-for-approximate-minimization-in-language-modelling/#comment-48 Wed, 25 Aug 2021 13:19:09 +0000 https://icgi2020.lis-lab.fr/?page_id=498#comment-48 In reply to Clara.

Thank you for your response and explanation in Q&A session! It’s clear to me. Thank you!

]]>
By: Clara https://icgi2020.lis-lab.fr/extracting-weighted-automata-for-approximate-minimization-in-language-modelling/#comment-44 Wed, 25 Aug 2021 08:28:40 +0000 https://icgi2020.lis-lab.fr/?page_id=498#comment-44 In reply to Kaito Suzuki.

Thank you very much for your question! The idea is that the matrix of the WFA needs to have the Hankel property. When you truncate the SVD the result might not be Hankel, so you need to find a way to preserve the property when doing approximation. This can be done in several ways. An alternative example can be found in Balle 2019 (Singular Value Automaton and Approximate Minimization), where the authors truncate a canonical form of WFA instead of the corresponding Hankel matrix. The tools we use, in particular AAK Theory, are needed to guarantee that this property is preserved and that the matrix obtained is still Hankel. In fact, AAK Theorem “returns” a Hankel matrix. On the other hand, when you apply spectral methods to recover WFAs from Hankel matrices, you start from a Hankel matrix, and use the truncated SVD and its relation with rank factorization in order to compute the parameters of the WFA. Note that the truncated SVD in the case of spectral methods is not the full Hankel matrix of the extracted WFA. I hope that I understood your question well and that I answered clearly, please don’t hesitate asking again if I didn’t.

]]>
By: Clara https://icgi2020.lis-lab.fr/extracting-weighted-automata-for-approximate-minimization-in-language-modelling/#comment-43 Wed, 25 Aug 2021 08:05:06 +0000 https://icgi2020.lis-lab.fr/?page_id=498#comment-43 In reply to Jeffrey Heinz.

There are two important challenges to extend the work. The main challenge will be to adapt results from harmonic analysis to the case of non abelian structures. While some work as been done in that direction (Popescu 2003), it is still unclear how we can transfer these results to the setting of multi-letter alphabets. A second major obstacle is that the generalization done by Popescu leads to a proof of AAK Theory that is not constructive, making it difficult to develop an algorithm to optimal approximation.

]]>
By: Kaito Suzuki https://icgi2020.lis-lab.fr/extracting-weighted-automata-for-approximate-minimization-in-language-modelling/#comment-41 Wed, 25 Aug 2021 02:01:01 +0000 https://icgi2020.lis-lab.fr/?page_id=498#comment-41 Thank you for the interesting talk! I am a beginner at spectral learning of WFAs and have a question about the problem setup. Some papers on spectral learning of WFAs seem to recover WFAs from Hankel matrices without considering whether the truncated SVD results have Hankel properties (e.g., Balle 2012). What is the difference between such results and this work? Does optimal spectral-norm approximate minimization require the Hankel properties and AAK theory?

]]>
By: Jeffrey Heinz https://icgi2020.lis-lab.fr/extracting-weighted-automata-for-approximate-minimization-in-language-modelling/#comment-40 Tue, 24 Aug 2021 18:24:40 +0000 https://icgi2020.lis-lab.fr/?page_id=498#comment-40 What do you think the biggest challenge is to extending the algorithm to multi-letter alphabets?

]]>
By: Clara https://icgi2020.lis-lab.fr/extracting-weighted-automata-for-approximate-minimization-in-language-modelling/#comment-39 Tue, 24 Aug 2021 18:15:51 +0000 https://icgi2020.lis-lab.fr/?page_id=498#comment-39 Thank you! Unfortunately, we do not have any experiment yet, as we focused on the theoretical component of the result. We plan to have some toy example and experimental results in our future work, likely after extending the algorithm to multi-letter alphabets. Experiments in this setting would be much more interesting and easier to interpret, as there are many more datasets that could be used.

]]>
By: Jean-Christophe https://icgi2020.lis-lab.fr/extracting-weighted-automata-for-approximate-minimization-in-language-modelling/#comment-15 Mon, 23 Aug 2021 07:33:30 +0000 https://icgi2020.lis-lab.fr/?page_id=498#comment-15 Very interesting work. Please could you give us a toy example of WFA that is extracted from a black box ?

]]>