crfrs 0.1.0

Generic structured-perceptron sequence labeler with Viterbi decoding
Documentation
//! Online structured-perceptron trainer with averaged weights.
//!
//! Implements the averaged structured perceptron (Collins 2002) with lazy
//! averaging (Daumé 2006) for efficient computation.

use std::collections::HashMap;
use crate::model::{emit_key, trans_key, PerceptronModel, START_LABEL};

/// Configuration for a training run.
#[derive(Debug, Clone)]
pub struct TrainConfig {
    /// Number of full passes over the training data.
    pub epochs: usize,
}

impl Default for TrainConfig {
    fn default() -> Self {
        Self { epochs: 15 }
    }
}

/// Online averaged structured-perceptron trainer.
///
/// Call [`update`](PerceptronTrainer::update) once per training example, then
/// call [`finish`](PerceptronTrainer::finish) to obtain the averaged model.
pub struct PerceptronTrainer {
    labels: Vec<String>,
    weights: HashMap<String, f64>,
    totals: HashMap<String, f64>,
    timestamps: HashMap<String, usize>,
    step: usize,
}

impl PerceptronTrainer {
    /// Creates a new trainer for the given label set.
    pub fn new(labels: Vec<String>) -> Self {
        Self {
            labels,
            weights: HashMap::new(),
            totals: HashMap::new(),
            timestamps: HashMap::new(),
            step: 0,
        }
    }

    /// Updates weights for a single training example.
    ///
    /// `seq_features[t]` is the list of active feature strings for position `t`.
    /// `gold[t]` is the gold label for that position.
    pub fn update(&mut self, seq_features: &[Vec<String>], gold: &[String]) {
        let pred = self.viterbi(seq_features);
        self.step += 1;

        if pred == gold {
            return;
        }

        for (t, (features, gold_label)) in seq_features.iter().zip(gold.iter()).enumerate() {
            let pred_label = &pred[t];

            for f in features {
                self.update_weight(emit_key(f, gold_label), 1.0);
                self.update_weight(emit_key(f, pred_label), -1.0);
            }

            let prev_gold = if t == 0 { START_LABEL } else { &gold[t - 1] };
            let prev_pred = if t == 0 { START_LABEL } else { &pred[t - 1] };
            self.update_weight(trans_key(prev_gold, gold_label), 1.0);
            self.update_weight(trans_key(prev_pred, pred_label), -1.0);
        }
    }

    /// Consumes the trainer and returns the averaged [`PerceptronModel`].
    pub fn finish(mut self) -> PerceptronModel {
        let step = self.step;
        for (key, &w) in &self.weights {
            let ts = self.timestamps.get(key).copied().unwrap_or(0);
            *self.totals.entry(key.clone()).or_insert(0.0) += (step - ts) as f64 * w;
        }
        let weights = self
            .totals
            .into_iter()
            .filter_map(|(k, v)| {
                let avg = if step > 0 { v / step as f64 } else { v };
                if avg.abs() > 1e-10 { Some((k, avg)) } else { None }
            })
            .collect();
        PerceptronModel::from_parts(self.labels, weights)
    }

    // -----------------------------------------------------------------------
    // Private helpers
    // -----------------------------------------------------------------------

    fn update_weight(&mut self, key: String, delta: f64) {
        let step = self.step;
        let w = self.weights.entry(key.clone()).or_insert(0.0);
        let ts = self.timestamps.entry(key.clone()).or_insert(0);
        *self.totals.entry(key).or_insert(0.0) += (step - *ts) as f64 * *w;
        *ts = step;
        *w += delta;
    }

    fn emit_score(&self, features: &[String], label: &str) -> f64 {
        features
            .iter()
            .map(|f| self.weights.get(&emit_key(f, label)).copied().unwrap_or(0.0))
            .sum()
    }

    fn trans_score(&self, prev: &str, curr: &str) -> f64 {
        self.weights
            .get(&trans_key(prev, curr))
            .copied()
            .unwrap_or(0.0)
    }

    fn viterbi(&self, seq_features: &[Vec<String>]) -> Vec<String> {
        let n = seq_features.len();
        if n == 0 {
            return vec![];
        }
        let l = self.labels.len();
        let mut dp = vec![vec![f64::NEG_INFINITY; l]; n];
        let mut back = vec![vec![0usize; l]; n];

        for (i, label) in self.labels.iter().enumerate() {
            dp[0][i] = self.emit_score(&seq_features[0], label)
                + self.trans_score(START_LABEL, label);
        }
        for t in 1..n {
            for (i, label) in self.labels.iter().enumerate() {
                let emit = self.emit_score(&seq_features[t], label);
                let (best_prev, best_score) = (0..l)
                    .map(|pi| {
                        let s = dp[t - 1][pi]
                            + self.trans_score(&self.labels[pi], label)
                            + emit;
                        (pi, s)
                    })
                    .max_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal))
                    .unwrap();
                dp[t][i] = best_score;
                back[t][i] = best_prev;
            }
        }

        let mut path = vec![0usize; n];
        path[n - 1] = (0..l)
            .max_by(|&a, &b| {
                dp[n - 1][a]
                    .partial_cmp(&dp[n - 1][b])
                    .unwrap_or(std::cmp::Ordering::Equal)
            })
            .unwrap_or(0);
        for t in (0..n - 1).rev() {
            path[t] = back[t + 1][path[t + 1]];
        }
        path.into_iter().map(|i| self.labels[i].clone()).collect()
    }
}

// ---------------------------------------------------------------------------
// Convenience entry point
// ---------------------------------------------------------------------------

/// Trains a perceptron model from labeled sequence examples.
///
/// `examples` is a slice of `(features_per_token, gold_labels_per_token)`.
/// `labels` must cover every label that appears in `examples`.
pub fn train(
    examples: &[(Vec<Vec<String>>, Vec<String>)],
    labels: Vec<String>,
    config: TrainConfig,
) -> PerceptronModel {
    let mut trainer = PerceptronTrainer::new(labels);
    for _ in 0..config.epochs {
        for (features, gold) in examples {
            trainer.update(features, gold);
        }
    }
    trainer.finish()
}