Multitask Spectral Learning of Weighted Automata

Guillaume Rabusseau, Borja Balle, Joelle PineauNeurIPS 2017 · OpenReview

Overview

This paper introduces a framework for multitask learning on sequence data using Weighted Finite Automata (WFA). By representing multiple tasks as a single "vector-valued" automaton, the authors develop a spectral learning algorithm that discovers shared structural patterns across tasks. This shared representation significantly improves predictive performance, particularly when data for individual tasks is scarce.

The Challenge: Multitask Learning for Sequence Data

In machine learning, modeling sequences—such as predicting the next word in a sentence or the next state in a robot's environment—is a fundamental problem. Weighted Finite Automata (WFA) are powerful tools for this, but learning them typically requires a large amount of data for every specific task.

However, many tasks are inherently related. For example, learning the grammar of Spanish should theoretically help a model learn the grammar of Italian. Standard "single-task" learning ignores these connections. The authors tackle the challenge of Multitask Learning (MTL) for sequence data: how can we jointly learn multiple WFA-based functions so they "help" each other by sharing an underlying representation?

Methodology: Vector-Valued WFAs and Spectral Learning

The authors introduce two major mathematical and algorithmic innovations to solve this problem:

  1. Vector-Valued WFA (vv-WFA): This is a novel mathematical model where a single automaton outputs a vector of values instead of a single scalar number. Crucially, all tasks represented in the vector share the same initial weights and transition matrices (the "internal logic" of the sequences), but they maintain different final weight vectors (the task-specific outputs).
  2. Multitask Spectral Learning (MT-SL): Traditional WFA learning often relies on the Expectation-Maximization (EM) algorithm, which is prone to getting stuck in local optima. Spectral learning provides an alternative that uses the Singular Value Decomposition (SVD) of a "Hankel matrix" (a matrix containing sequence probabilities) to find a globally optimal solution.
  3. The authors extend this concept to a Hankel tensor to account for multiple tasks simultaneously.
  4. They incorporate a clever projection step: after learning a massive joint representation, the model is projected back down to the specific dimensions relevant to each individual task. This effectively filters out "noise" that might be useful for one task but irrelevant or harmful to another.

Experimental Setup

The researchers evaluated their approach across two distinct domains:

  • Synthetic Data: Randomly generated stochastic WFAs where the authors could precisely control the "relatedness" between tasks (i.e., how many states were shared versus task-specific).
  • Real-World Data (UNIDEP): The Universal Dependencies 1.4 treebank. They used 33 different languages, treating the prediction of Part-of-Speech (PoS) tags as separate but related tasks. This dataset uses a 17-tag universal set, providing a consistent alphabet across all languages.

Key Insights and Results

The Power of Shared Representations

The paper formalizes "relatedness" as the extent to which tasks can share a joint forward feature map. Mathematically, "stacking" the data from multiple tasks horizontally in a matrix allows the SVD to identify the shared "left singular subspace" (the shared features) much more accurately than if each task were processed in isolation. By enforcing a low-rank shared representation, the algorithm effectively ignores noise that doesn't fit the common pattern across tasks.

Synthetic Validation

In controlled tests, the algorithm's performance scaled directly with the number of related tasks. Adding more tasks improved the accuracy of the target task, provided they shared a common underlying structure.

Performance of MT-SL vs single-task SL on synthetic data across different degrees of shared states and task counts.

As seen in the synthetic results, Multitask Spectral Learning (MT-SL) consistently achieves lower perplexity and word error rates compared to single-task Spectral Learning (SL), especially at smaller training sizes and as the number of jointly learned tasks increases (from 2 to 8).

Real-World Performance: Better with Less

The benefits of MT-SL were most dramatic when training data was limited. On the UNIDEP dataset with only 100 training samples per language, MT-SL showed a ~7% relative improvement in perplexity over single-task learning. Furthermore, MT-SL consistently outperformed naive "bagging" (simply pooling all data together), proving that the vv-WFA model successfully distinguishes between what should be shared and what is strictly task-specific.

Limitations and Future Directions

  • The "Relatedness" Assumption: The method fundamentally relies on tasks being genuinely related. If tasks are entirely independent, the multitask approach offers no benefit and may even slightly increase the model's complexity unnecessarily.
  • Rank Selection: The algorithm requires the user to estimate the "rank" (number of states) for both the joint model and individual tasks. In the paper, this was done via a validation set, which can be computationally intensive.
  • Future Work: The authors suggest applying this framework to Reinforcement Learning, where an agent might need to learn multiple related navigation or manipulation tasks simultaneously. They also propose exploring "weighted" multitask learning, where the algorithm could automatically determine how much to trust data from one task when learning another.

Summary updated

Abstract

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 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.
BibTeX
@inproceedings{rabusseau2017multitask,
  author = {Guillaume Rabusseau and Borja Balle and Joelle Pineau},
  title = {{Multitask Spectral Learning of Weighted Automata}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=H1WWKOWubH},
}
Figure