Struct LogWeight 

pub struct LogWeight(/* private fields */);

Log weight for numerically stable probability computation.

The log semiring addresses numerical stability issues inherent in probability computation by working in the negative log domain. This enables handling of very small probabilities (e.g., $10^{-100}$) that would underflow in linear probability space, while maintaining mathematically equivalent probabilistic semantics.

Mathematical Definition

The log semiring is defined as $(\mathbb{R} \cup \{+\infty\}, \oplus_{\log}, +, +\infty, 0)$:

Operation	Definition	Interpretation
$a \oplus b$	$-\log(e^{-a} + e^{-b})$	Combine probabilities
$a \otimes b$	$a + b$	Multiply probabilities
$\bar{0}$	$+\infty$	Impossible event ($p = 0$)
$\bar{1}$	$0$	Certain event ($p = 1$)

Relationship to Probability Semiring

The log semiring is isomorphic to the probability semiring through the transformation $w = -\log p$ where $p$ is a probability:

• If $p, q$ are probabilities: $-\log p \oplus -\log q = -\log(p + q)$
• If $p, q$ are probabilities: $-\log p \otimes -\log q = -\log(p \times q)$

This preserves probabilistic semantics while providing numerical stability.

Use Cases

Large-Vocabulary Speech Recognition

use arcweight::prelude::*;

// Acoustic model probabilities (very small values)
let acoustic_prob = LogWeight::from_probability(1e-50);  // Converts to log space
let language_prob = LogWeight::from_probability(0.001);

// Combine probabilities safely
let combined = acoustic_prob.times(&language_prob);  // Multiplication in log space

// Convert back to probability if needed
let final_prob = combined.to_probability();
println!("Final probability: {:.2e}", final_prob);  // ~1e-53

Machine Translation with Large Models

use arcweight::prelude::*;

// Translation model scores (often very small probabilities)
let phrase_prob = LogWeight::from_probability(1e-20);
let alignment_prob = LogWeight::from_probability(1e-15);
let reordering_prob = LogWeight::from_probability(0.1);

// Combine all model scores
let translation_score = phrase_prob
    .times(&alignment_prob)
    .times(&reordering_prob);

// Alternative translations (add probabilities)
let alternative1 = LogWeight::from_probability(1e-35);
let alternative2 = LogWeight::from_probability(2e-35);
let combined_alternatives = alternative1.plus(&alternative2);  // LogSumExp

Neural Language Model Integration

use arcweight::prelude::*;

// Softmax probabilities from neural networks
let word_probs = vec![
    LogWeight::from_probability(0.4),   // Most likely word
    LogWeight::from_probability(0.3),   // Second choice
    LogWeight::from_probability(0.2),   // Third choice
    LogWeight::from_probability(0.1),   // Least likely
];

// Compute probability of any of these words
let any_word_prob = word_probs.into_iter()
    .fold(LogWeight::zero(), |acc, prob| acc.plus(&prob));

// Should be close to 1.0 (sum of probabilities)
assert!((any_word_prob.to_probability() - 1.0).abs() < 1e-10);

Sequence Analysis in Bioinformatics

use arcweight::prelude::*;

// DNA sequence alignment with very long sequences
let base_prob = LogWeight::from_probability(0.25);  // Each base equally likely
let sequence_length = 1000;

// Probability of specific sequence (would underflow in linear space)
let mut sequence_prob = LogWeight::one();
for _ in 0..sequence_length {
    sequence_prob = sequence_prob.times(&base_prob);
}

// Convert to scientific notation for display
println!("Sequence probability: {:.2e}", sequence_prob.to_probability());

Working with FSTs

use arcweight::prelude::*;

let log_p1 = LogWeight::from_probability(0.5);   // Convert from probability
let log_p2 = LogWeight::from_probability(0.25);  // Convert from probability

// Addition performs log-sum-exp (combines probabilities)
let sum = log_p1 + log_p2;  // -log(0.5 + 0.25) = -log(0.75)
assert!((sum.to_probability() - 0.75).abs() < 1e-6);

// Multiplication is addition in log space (multiplies probabilities)
let product = log_p1 * log_p2;  // -log(0.5 × 0.25) = -log(0.125)
assert!((product.to_probability() - 0.125).abs() < 1e-10);

// Identity elements
assert_eq!(LogWeight::zero(), LogWeight::INFINITY);  // Impossible event
assert_eq!(LogWeight::one(), LogWeight::new(0.0));   // Certain event

Numerical Stability Implementation

The log semiring implements numerically stable log-sum-exp operation:

-log(e^(-a) + e^(-b)) = -max(a,b) - log(1 + e^(-|a-b|))

This formulation prevents overflow/underflow by:

• Working with the larger magnitude value first
• Computing the difference in a stable manner
• Using the identity: log(1 + x) ≈ x for small x

Performance Characteristics

• Arithmetic: Addition is expensive (log-sum-exp), multiplication is O(1)
• Memory: 8 bytes per weight (single f64)
• Precision: Double precision for high-accuracy probability computation
• Conversion: Efficient probability ↔ log conversions available
• Range: Handles probabilities from ~10^-308 to 1.0

Conversion Utilities

use arcweight::prelude::*;

// Convert from probability to log weight
let prob = 0.001;
let log_weight = LogWeight::from_probability(prob);
assert_eq!(log_weight.value(), &(-prob.ln()));

// Convert back to probability
let recovered_prob = log_weight.to_probability();
assert!((recovered_prob - prob).abs() < 1e-15);

// Handle edge cases
let zero_prob = LogWeight::from_probability(0.0);
assert!(<LogWeight as num_traits::Zero>::is_zero(&zero_prob));
assert_eq!(zero_prob.to_probability(), 0.0);

Advanced Usage

Normalization in Log Space

use arcweight::prelude::*;

// Normalize a probability distribution in log space
let log_probs = vec![
    LogWeight::new(1.0),  // Unnormalized log probabilities
    LogWeight::new(2.0),
    LogWeight::new(0.5),
];

// Compute log partition function (log of sum of probabilities)
let log_z = log_probs.iter()
    .fold(LogWeight::zero(), |acc, &p| acc.plus(&p));

// Normalize each probability
let normalized: Vec<_> = log_probs.iter()
    .map(|&p| p.divide(&log_z).unwrap())
    .collect();

// Verify normalization (sum should be 1.0)
let sum = normalized.iter()
    .fold(LogWeight::zero(), |acc, &p| acc.plus(&p));
assert!((sum.to_probability() - 1.0).abs() < 1e-10);

Integration with FST Algorithms

Log weights work with all FST algorithms while providing numerical stability:

• Shortest Path: Finds maximum probability paths
• Forward-Backward: Stable computation of path probabilities
• Composition: Combines probabilistic models
• Determinization: Maintains probability distributions

Algebraic Properties

• Commutative: Both $\oplus$ and $\otimes$ are commutative
• Not idempotent: $a \oplus a \neq a$ in general
• No path property: $a \oplus b \notin \{a, b\}$ in general
• Divisible: Division is subtraction: $a \oslash b = a - b$

See Also

• ProbabilityWeight for simple probability computation
• TropicalWeight for optimization problems

References

• Mohri, M. (2002). Semiring frameworks and algorithms for shortest-distance problems. Journal of Automata, Languages and Combinatorics, 7(3), 321–350.

• Mohri, M., Pereira, F., & Riley, M. (2002). Weighted finite-state transducers in speech recognition. Computer Speech & Language, 16(1), 69–88.

Implementations

impl LogWeight

pub const INFINITY: Self

Positive infinity (zero element)

pub fn new(value: f64) -> Self

Create a new log weight

pub fn from_probability(p: f64) -> Self

Convert from probability

pub fn to_probability(&self) -> f64

Convert to probability

Trait Implementations

impl Add for LogWeight

type Output = LogWeight

The resulting type after applying the + operator.

fn add(self, rhs: Self) -> Self::Output

Performs the + operation.

impl Clone for LogWeight

fn clone(&self) -> LogWeight

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Copy for LogWeight

impl Debug for LogWeight

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for LogWeight

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Display for LogWeight

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl DivisibleSemiring for LogWeight

fn divide(&self, other: &Self) -> Option<Self>

Division operation

impl Eq for LogWeight

impl Hash for LogWeight

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl Mul for LogWeight

type Output = LogWeight

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Self::Output

Performs the * operation.

impl One for LogWeight

fn one() -> Self

Returns the multiplicative identity element of Self, 1.

fn set_one(&mut self)

Sets self to the multiplicative identity element of Self, 1.

fn is_one(&self) -> bool

where Self: PartialEq,

Returns true if self is equal to the multiplicative identity.

impl Ord for LogWeight

fn cmp(&self, other: &LogWeight) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for LogWeight

fn eq(&self, other: &LogWeight) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for LogWeight

fn partial_cmp(&self, other: &LogWeight) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Semiring for LogWeight

type Value = f64

Type of the underlying value

fn new(value: Self::Value) -> Self

Create a new weight from a value

fn value(&self) -> &Self::Value

Get the underlying value

fn properties() -> SemiringProperties

Semiring properties

fn approx_eq(&self, other: &Self, epsilon: f64) -> bool

Approximate equality for floating-point weights

fn plus(&self, other: &Self) -> Self

Semiring addition (⊕)

fn times(&self, other: &Self) -> Self

Semiring multiplication (⊗)

fn plus_assign(&mut self, other: &Self)

In-place semiring addition

fn times_assign(&mut self, other: &Self)

In-place semiring multiplication

fn is_zero(&self) -> bool

Check if weight is zero (additive identity)

fn is_one(&self) -> bool

Check if weight is one (multiplicative identity)

impl Serialize for LogWeight

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl SimdOps<LogWeight> for LogWeight

fn simd_plus(left: &[LogWeight], right: &[LogWeight], result: &mut [LogWeight])

Perform parallel semiring addition (plus operation) on weight arrays.

fn simd_times(left: &[LogWeight], right: &[LogWeight], result: &mut [LogWeight])

Perform parallel semiring multiplication (times operation) on weight arrays.

fn simd_min(weights: &[LogWeight]) -> LogWeight

Find minimum weight in array using SIMD parallel reduction.

fn simd_max(weights: &[LogWeight]) -> LogWeight

Find maximum weight in array using SIMD parallel reduction.

impl StructuralPartialEq for LogWeight

impl Zero for LogWeight

fn zero() -> Self

Returns the additive identity element of Self, 0.

fn is_zero(&self) -> bool

Returns true if self is equal to the additive identity.

fn set_zero(&mut self)

Sets self to the additive identity element of Self, 0.