Multitask Spectral Learning of Weighted Automata
We consider the problem of estimating multiple related functions computed by weighted automata (WFA). We first present a natural notion of relatedness between WFAs by considering to which extent several WFAs can share a common underlying representation. We then introduce the novel model of vector-valued WFA which conveniently helps us formalize this notion of relatedness. Finally, we propose a spectral learning algorithm for vector-valued WFAs to tackle the multitask learning problem. By jointly learning multiple tasks in the form of a vector-valued WFA, our algorithm enforces the discovery of a representation space shared between tasks. The benefits of the proposed multitask approach are theoretically motivated and showcased through experiments on both synthetic and real world datasets.
SUMMARY
The paper studies the problem of multitask learning of WFAs. It defines a notion of relatedness among tasks, and designs a new algorithm that can exploit such relatedness. Roughly speaking, the new algorithm stacks the Hankel matrices from different tasks together and perform an adapted version of spectral learning, resulting in a vv-WFA that can make vector-valued predictions with a unified state representation. A post-processing step that reduces the dimension of the WFA for each single task is also suggested to reduce noise. The algorithm is compared to the baseline of learning each task separately on both synthetic and real-world data.
COMMENTS
Overall this is a well written paper. However, I do have a concern in the experiment section: it is important to compare to the baseline where all data from different tasks are bagged together and treated as if they came from the same task. At least when all the tasks are the same, this should outperform everyone else as it makes full use of all the data. Of course, when the tasks are not related, such a practice may lead to asymptotic approximation error, but how large is this error practically? If this error is small on the datasets used in the experiment section, then such datasets are not interesting as any algorithm that does some kind of data aggregation would show improvement over single-task learning. If possible I would like to see some results (even if they are primary) on this comparison during rebuttal.
It would be good to also compare to Alg 1 without the projection step to see how much improvement this post-processing procedure brings.
The paper's presentation may be improved by discussing the application scenario of multi-task learning of WFAs. As a starter, one could consider natural language modeling tasks where we need to make predictions in different contexts (e.g., online chat vs newspaper articles) and have access to datasets in each of them. In this example, it is natural to expect that basic grammar is shared across the datasets and can be learned together. Of course, one can always aggregate all datasets into a big one and build a single model (which corresponds to the baseline I mentioned above), and the disadvantage is that the model cannot leverage the context information available at prediction phase.
Two additional suggestions:
- The current algorithm implicitly assumes equal weights among all the tasks. This should work well when the size of the datasets are roughly the same across tasks, but when they differ a lot I suspect that the algorithm could misbehave. In this case you might want to consider a weighted approach; see Kulesza et al, Low-Rank Spectral Learning with Weighted Loss Functions.
- Here is another reason for doing the projection step: consider the case when the m tasks are completely unrelated, and each of them requires n states. Single-task learning would need n*m^2 parameters for each character in the alphabet, while the multi-task learning uses a model of size (nm)^2. The projection step eliminates such redundancy. 
MINOR ISSUE
Line 93: as far as I know, it is not required that empty string is included in prefixes or suffixes. (At least this is true in the PSR literature which I am more familiar with.) The author(s) might want to double check on this.
==============================
Thanks for the rebuttal and the additional results. No complaints! Will keep arguing for acceptance.