Sequence Labeling

The smile.sequence package labels each position in a sequence of symbols or feature vectors. It supplies a common labeler abstraction, a generative hidden Markov model, and a discriminative conditional random field.

Class	Model and input	Training	Inference
`HMM`	Generative; integer symbols	Supervised MLE or Baum–Welch update	Viterbi
`HMMLabeler<T>`	Generic wrapper for HMM	Delegates through an ordinal function	Viterbi
`CRF`	Discriminative; feature Tuples	Gradient tree boosting	Forward-backward or Viterbi
`CRFLabeler<T>`	Generic wrapper for CRF	Delegates through a feature function	Forward-backward or Viterbi

SequenceLabeler

SequenceLabeler<T> is a serializable functional interface whose predict(T[] x) method returns one dense, zero-based integer label per input position. Both generic wrappers implement it, so applications can exchange HMM and CRF labelers behind one API.

T[] x: A non-empty observation sequence.
int[] predict(T[] x): A label sequence with the same length as the input.

Hidden Markov Model

A first-order HMM is generative: hidden states emit observed symbols. Its parameters are the initial probabilities π, state-transition matrix A, and symbol-emission matrix B.

π [N]: Initial-state probabilities.
A [N × N]: A[i][j] = P(s_t=j | s_t-1=i).
B [N × M]: B[i][j] = P(o_t=j | s_t=i).

HMM.fit(int[][] observations, int[][] labels) estimates all three from aligned labeled sequences by maximum likelihood. For unlabeled sequences, a pre-initialized model can run an in-place Baum–Welch EM update with update(observations, iterations); each sequence must contain more than two symbols.

import java.util.Arrays;
import smile.sequence.HMM;

int[][] coins = {{0, 0, 1, 0, 1}, {1, 1, 0, 1, 0}};
int[][] states = {{0, 0, 1, 0, 1}, {1, 1, 0, 1, 0}};
HMM hmm = HMM.fit(coins, states);

int[] tosses = {0, 1, 1, 0};
System.out.println(Arrays.toString(hmm.predict(tosses)));
System.out.printf("log P(o) = %.4f%n", hmm.logp(tosses));


Viterbi state sequence and its finite log likelihood

import smile.sequence.hmm

val coins = Array(Array(0, 0, 1, 0, 1), Array(1, 1, 0, 1, 0))
val states = Array(Array(0, 0, 1, 0, 1), Array(1, 1, 0, 1, 0))
val model = hmm(coins, states)

val tosses = Array(0, 1, 1, 0)
println(model.predict(tosses).mkString("[", ", ", "]"))
println(f"log P(o) = ${model.logp(tosses)}%.4f")


Viterbi state sequence and its finite log likelihood

import smile.sequence.HMM

val coins = arrayOf(intArrayOf(0, 0, 1, 0, 1), intArrayOf(1, 1, 0, 1, 0))
val states = arrayOf(intArrayOf(0, 0, 1, 0, 1), intArrayOf(1, 1, 0, 1, 0))
val hmm = HMM.fit(coins, states)

val tosses = intArrayOf(0, 1, 1, 0)
println(hmm.predict(tosses).contentToString())
println("log P(o) = %.4f".format(hmm.logp(tosses)))


Viterbi state sequence and its finite log likelihood

predict decodes the most likely state path with Viterbi. logp(o, s) scores a particular joint observation/state path, while logp(o) computes the stable log marginal likelihood. Prefer log probabilities for long sequences.

HMMLabeler

HMMLabeler<T> keeps an HMM and a ToIntFunction<T> that maps domain symbols to vocabulary indices. Its scoring, prediction, and Baum–Welch methods translate the symbols and delegate to the underlying model.

import java.util.Arrays;
import smile.sequence.HMMLabeler;

String[][] x = {{"H", "H", "T"}, {"T", "T", "H"}};
int[][] y = {{0, 0, 1}, {1, 1, 0}};
var labeler = HMMLabeler.fit(x, y, s -> s.equals("H") ? 0 : 1);
System.out.println(Arrays.toString(labeler.predict(new String[]{"H", "T", "H"})));


[0, 1, 0]

import java.util.function.ToIntFunction
import smile.sequence.hmm

val x = Array(Array("H", "H", "T"), Array("T", "T", "H"))
val y = Array(Array(0, 0, 1), Array(1, 1, 0))
val ordinal = ToIntFunction[String](s => if s == "H" then 0 else 1)
val labeler = hmm(x, y, ordinal)
println(labeler.predict(Array("H", "T", "H")).mkString("[", ", ", "]"))


[0, 1, 0]

import java.util.function.ToIntFunction
import smile.sequence.HMMLabeler

val x = arrayOf(arrayOf("H", "H", "T"), arrayOf("T", "T", "H"))
val y = arrayOf(intArrayOf(0, 0, 1), intArrayOf(1, 1, 0))
val ordinal = ToIntFunction<String> { if (it == "H") 0 else 1 }
val labeler = HMMLabeler.fit(x, y, ordinal)
println(labeler.predict(arrayOf("H", "T", "H")).contentToString())


[0, 1, 0]

Conditional Random Field

A linear-chain CRF models P(y | x) directly. SMILE represents each position as a schema-consistent Tuple and learns label potentials as gradient-boosted regression trees, allowing overlapping and nonlinear features without modeling the input distribution.

predict(Tuple[]) chooses each position’s marginal argmax with forward-backward and usually optimizes token accuracy. viterbi(Tuple[]) returns the single highest-scoring global path when sequence coherence matters.

CRF Options

Hyperparameters are fields of the nested CRF.Options record. Pass an Options instance to fit, or a java.util.Properties map using the keys below (Options.toProperties() / Options.of(props) round-trip). The full constructor is new CRF.Options(ntrees, maxDepth, maxNodes, nodeSize, shrinkage).

ntrees smile.crf.trees: Boosting rounds / trees per class; default 100.
maxDepth smile.crf.max_depth: Maximum tree depth; default 20.
maxNodes smile.crf.max_nodes: Maximum leaf nodes per tree; default 100.
nodeSize smile.crf.node_size: Minimum samples in a leaf; default 5.
shrinkage smile.crf.shrinkage: Learning rate in (0, 1]; default 1.0.

CRFLabeler

CRFLabeler<T> maps each observation through a Function<T, Tuple>. Every returned tuple must share the same StructType. The toy POS-style example below uses token length, capitalization count, and an -ed suffix flag.

import java.util.Arrays;
import java.util.function.Function;
import smile.data.Tuple;
import smile.data.type.*;
import smile.sequence.*;

String[][] x = {{"The", "cat", "sat"}, {"Dogs", "run", "fast"}};
int[][] y = {{2, 0, 1}, {0, 1, 2}}; // noun=0, verb=1, other=2
var schema = new StructType(
    new StructField("length", DataTypes.IntType),
    new StructField("capitals", DataTypes.IntType),
    new StructField("has_ed", DataTypes.IntType));
Function<String, Tuple> features = w -> Tuple.of(schema, new int[]{
    w.length(), (int) w.chars().filter(Character::isUpperCase).count(),
    w.endsWith("ed") ? 1 : 0});
var tagger = CRFLabeler.fit(x, y, features,
    new CRF.Options(20, 5, 16, 1, 0.2));
System.out.println(Arrays.toString(
    tagger.predict(new String[]{"The", "dogs", "barked"})));


Three POS label indices, one per token

import java.util.function.Function
import smile.data.Tuple
import smile.data.`type`.{DataTypes, StructField, StructType}
import smile.sequence.gcrf

val x = Array(Array("The", "cat", "sat"), Array("Dogs", "run", "fast"))
val y = Array(Array(2, 0, 1), Array(0, 1, 2))
val schema = new StructType(
  new StructField("length", DataTypes.IntType),
  new StructField("capitals", DataTypes.IntType),
  new StructField("has_ed", DataTypes.IntType))
val features = Function[String, Tuple](w => Tuple.of(schema, Array(
  w.length, w.count(_.isUpper).toInt, if w.endsWith("ed") then 1 else 0)))
val tagger = gcrf(x, y, features, 20, 5, 16, 1, 0.2)
println(tagger.predict(Array("The", "dogs", "barked")).mkString("[", ", ", "]"))


Three POS label indices, one per token

import java.util.function.Function
import smile.data.Tuple
import smile.data.type.DataTypes
import smile.data.type.StructField
import smile.data.type.StructType
import smile.sequence.CRF
import smile.sequence.CRFLabeler

val x = arrayOf(arrayOf("The", "cat", "sat"), arrayOf("Dogs", "run", "fast"))
val y = arrayOf(intArrayOf(2, 0, 1), intArrayOf(0, 1, 2))
val schema = StructType(
    StructField("length", DataTypes.IntType),
    StructField("capitals", DataTypes.IntType),
    StructField("has_ed", DataTypes.IntType))
val features = Function<String, Tuple> { w -> Tuple.of(schema, intArrayOf(
    w.length, w.count { it.isUpperCase() }, if (w.endsWith("ed")) 1 else 0)) }
val tagger = CRFLabeler.fit(x, y, features, CRF.Options(20, 5, 16, 1, 0.2))
println(tagger.predict(arrayOf("The", "dogs", "barked")).contentToString())


Three POS label indices, one per token

HMM vs CRF

Criterion	HMM	CRF
Model	Generative `P(o, s)`	Discriminative `P(y \| x)`
Input	Discrete vocabulary indices	Arbitrary Tuple features
Training	Fast labeled MLE; optional unlabeled Baum–Welch	Labeled gradient boosting
Decoding	Viterbi	Marginal argmax or Viterbi
Strength	Simple, fast, interpretable baseline	Rich features and usually higher accuracy
Trade-off	Large emission matrix for large vocabularies	Slower training and feature design

Practical Tips

Persist models. All models and wrappers are serializable. Save with Write.object(model, Path.of("tagger.ser")) and restore with Read.object(...).

Evaluate the task metric. Compute token accuracy by summing position-wise matches over all test sequences. For CRF, compare both decoders on held-out data: use predict when per-token accuracy is primary, and viterbi when only a coherent global path is acceptable.

NLP shortcut. For a ready-made HMM part-of-speech tagger, see Natural Language Processing and HMMPOSTagger.

← Time Series Natural Language Processing →