Documentation
¶
Overview ¶
Package model is the HMM library used by the engine and by plugins alike (docs/DESIGN.md §10.6). It provides the primitives — forward filtering, Baum-Welch, log-space arithmetic, Dirichlet smoothing — plus the dag-cbor artifact format that gives a model a CID.
It is a library, not a model. The engine instantiates one to steer expansion; an operator instantiates its own to decide what it emits; neither knows about the other's states or alphabet.
What a model may be used for ¶
The engine's model steers execution and nothing else: frontier ordering, pruning, and operator gating (§10.2). It must never produce a number a user reads — no report score, no finding, no severity. That restriction is what removes the calibration requirement: a miscalibrated model that mis-ranks the frontier wastes network calls, whereas a miscalibrated model in a report makes a false accusation. Nothing in this package is named or shaped like a severity, and Belief deliberately exposes only what graph.BeliefModel needs.
Inference ¶
Forward filtering is the only inference offered at run time: no Viterbi, no backward pass, no belief propagation (§10.1). A node's belief is a pure function of its parent's belief and its own props, which is what makes it available *during* execution, where it can still save a network call. The backward recursion exists in train.go only, because Baum-Welch needs it offline; it is unexported and never runs during a scan.
Numerics ¶
All table arithmetic is in log space. An expansion path is short but an emission is a product over every observed prop, so linear-space probabilities underflow quickly and silently; log space makes the arithmetic stable and turns products into sums.
Index ¶
- Constants
- Variables
- func LogAdd(a, b float64) float64
- func LogSumExp(xs []float64) float64
- func OutcomeSymbol(outcome string) string
- func UniformBelief() graph.BeliefModel
- type Belief
- type Config
- type Corpus
- type Featurizer
- type HMM
- func (h *HMM) Addressed() ([]byte, cid.Cid, error)
- func (h *HMM) CID() (cid.Cid, error)
- func (h *HMM) Focus() []string
- func (h *HMM) Forward(prev []float64, rel string, obs []string) []float64
- func (h *HMM) Lift(b float64) []float64
- func (h *HMM) LogEmission(state int, obs []string) float64
- func (h *HMM) LogLikelihood(c Corpus) float64
- func (h *HMM) LogTransition(rel string, from, to int) float64
- func (h *HMM) Mass(logDist []float64) float64
- func (h *HMM) Prior() []float64
- func (h *HMM) Provenance() Provenance
- func (h *HMM) RelIndex(rel string) int
- func (h *HMM) Rels() []string
- func (h *HMM) Smoothing() Smoothing
- func (h *HMM) States() []string
- func (h *HMM) SymbolIndex(sym string) int
- func (h *HMM) Symbols() []string
- type Path
- type Provenance
- type Result
- type Smoothing
- type Spec
- type Trace
Constants ¶
const ( // AlgorithmUniform is the untrained model — no corpus, no fitting. AlgorithmUniform = "uniform" // AlgorithmBaumWelch is unsupervised EM over recorded expansion traces. AlgorithmBaumWelch = "baum-welch" // AlgorithmManual is a hand-written model, for tests and bootstrapping. AlgorithmManual = "manual" )
Algorithm names recorded in a model's provenance.
const ( // OOVSymbol is the explicit out-of-vocabulary emission symbol. Every // alphabet contains it, and any symbol a featurizer produces that training // never saw is mapped onto it. Without an explicit symbol an unseen prop // would either be dropped — silently discarding evidence — or annihilate // the filter with a zero probability. OOVSymbol = "<oov>" // OOVRelation is the transition table used for a relation the model does // not know. Plans add relations over time; a model trained before one // existed must still be usable rather than panicking mid-scan. OOVRelation = "<oov>" )
const OutcomePrefix = "outcome="
OutcomePrefix namespaces the emission symbol built from a trace's outcome.
The outcome — resolved, absent, refused — is an observation like any other prop, so it belongs in the emission alphabet rather than being dropped. It is prefixed so a featurizer can produce the identical symbol at run time (OutcomeSymbol below) and so it can never collide with a prop named "outcome".
Variables ¶
var LogZero = math.Inf(-1)
LogZero is the log of an impossible event. Log-space arithmetic is closed over it: LogAdd and LogSumExp both handle it without producing NaN.
Functions ¶
func LogAdd ¶
LogAdd returns log(exp(a) + exp(b)) without leaving log space. Subtracting the larger term first keeps exp in range, so LogZero inputs give LogZero rather than NaN.
func LogSumExp ¶
LogSumExp returns log(sum(exp(x))) using the max-shift trick. An empty or all-LogZero input gives LogZero.
func OutcomeSymbol ¶
OutcomeSymbol renders an outcome as the emission symbol training used, so a run-time featurizer and the corpus agree on spelling. An empty outcome produces no symbol.
func UniformBelief ¶
func UniformBelief() graph.BeliefModel
UniformBelief is the model the engine runs with before one has been trained. It returns 1 for every node, so the frontier sorts on (depth, type, key) alone and no candidate is ever pruned: breadth-first, unranked, which is exactly the pre-model behaviour (§10.5).
Types ¶
type Belief ¶
type Belief struct {
// contains filtered or unexported fields
}
Belief adapts an HMM to graph.BeliefModel.
It exists only to steer execution: frontier ordering, pruning, and BeliefAbove gates (§10.2). Nothing it returns is a report score, a finding or a severity, and analyzers never see it. That restriction is what makes a miscalibrated model a waste of network calls rather than a false accusation.
func NewBelief ¶
func NewBelief(h *HMM, f Featurizer) *Belief
NewBelief wraps a model as the engine's (or a plugin's) belief model. A nil featurizer means no observations at all, which leaves belief as the pure transition prior — exactly the state a candidate is in.
func (*Belief) Initial ¶
Initial is the seed's prior. The seed has no parent, so barrier 0 takes it straight from the initial distribution — and carries that distribution forward as the state its children step from.
func (*Belief) Model ¶
Model returns the underlying HMM, so a caller can pin its CID into the plan hash.
func (*Belief) Step ¶
Step is the forward filtering step: the parent's belief pushed through the relation that admitted this node, then conditioned on the node's props as of this barrier.
It is recomputed from scratch at every barrier rather than accumulated, which is what makes it independent of which operator returned first — only which round an edge belongs to matters, and that is deterministic (§10.3).
The parent's full posterior travels in graph.State, so nothing is reconstructed and nothing is lost. An earlier version received only the parent's scalar and had to Lift it back into a distribution — exact for two states, and for three or more the maximum-entropy distribution consistent with that one number, which is not the posterior the parent actually had.
type Config ¶
type Config struct {
// States is the latent alphabet to fit. Unsupervised EM cannot invent
// meaning for these, so the number is a modelling choice: see §16, "state
// cardinality".
States []string
// Focus names the states whose posterior mass becomes belief.
Focus []string
// Iterations caps EM passes.
Iterations int
// Tolerance stops early once the objective improves by less than this.
Tolerance float64
// Seed initializes the symmetry-breaking RNG. It is recorded in the model's
// provenance so that training reproduces exactly (§10.4).
Seed int64
// Smoothing is the Dirichlet prior; every component must be positive.
Smoothing Smoothing
// Date is stamped into provenance. Zero means "now"; tests pass a fixed
// value so the resulting CID is stable.
Date time.Time
}
Config parameterizes Baum-Welch.
type Corpus ¶
type Corpus struct {
Paths []Path
// CIDs are the trace blocks this corpus was read from. They are copied into
// the trained model's provenance so a model always points back at what it
// was fitted on.
CIDs []cid.Cid
}
Corpus is a set of recorded expansion paths and the blocks they came from.
type Featurizer ¶
Featurizer turns a node's view into emission symbols — the observation the forward step conditions on.
It is the whole of what a model knows about the graph. Keeping it a function supplied by the caller is what makes this package a library rather than the engine's model (§10.6): the engine featurizes the props its plan produces, a variant operator featurizes whatever its own model needs, and neither package has to know the other's alphabet.
A featurizer must be a pure function of the view. Anything it reads from outside — a clock, a counter, a map iteration — makes belief depend on something other than (parent belief, props), and the reproducibility the whole barrier design exists to protect is gone.
func PropFeatures ¶
func PropFeatures(fields ...string) Featurizer
PropFeatures builds a Featurizer that renders the named fields as "field=value" emission symbols, skipping fields that are unset.
Skipping rather than emitting "field=" is deliberate: emissions are a product over the symbols present, so an absent prop contributes nothing and a node observed in round g is not penalized for props that only arrive in round g+1.
Field names are sorted so the symbol order is fixed. Order does not change the product, but a stable order keeps traces recorded by one run comparable with another's byte for byte.
Continuous fields — a registration timestamp, a response size — should be bucketed by the caller before they reach here. Rendered exactly, every distinct value becomes its own symbol, the alphabet explodes and every symbol falls to OOV.
type HMM ¶
type HMM struct {
// contains filtered or unexported fields
}
HMM is a discrete hidden Markov model whose transition table is conditioned on the name of the relation taken, so that sharing an IP can transmit far more belief than sharing a TLD (§10).
All tables are held in log space. The type is immutable once built: Forward allocates its own output, so one HMM is safe for concurrent use by every worker in a round.
func Decode ¶
Decode rebuilds a model from its dag-cbor block.
It installs the log tables verbatim rather than re-normalizing them, so an encode/decode round trip is bit-exact and the CID is unchanged. Re-deriving the tables would be a slow way to introduce a rounding difference that changes a model's identity every time it is loaded.
func New ¶
New builds an HMM from a Spec, normalizing every distribution. Rows that sum to zero become uniform rather than an error: a relation nobody has observed is a normal state of affairs, and the honest prior for it is "no information".
func Uniform ¶
func Uniform() *HMM
Uniform is the untrained model. It has one state, so its posterior is a point mass and its belief is exactly 1 for every node, every relation and every observation — bit-identical to graph's default model.
This is the property §10.5 rests on: a uniform model reduces expansion to breadth-first and unranked, so the engine ships and runs correctly before any model exists, and a model that turns out poor can be dropped without invalidating a single result. A single state also makes the reduction exact rather than approximate: with N uniform states the belief would be the constant |focus|/N, equal for every node and therefore still unranked, but no longer the literal 1 that graph's own default returns.
func (*HMM) Addressed ¶
Addressed returns the model's dag-cbor block and its CID.
The encoding is a positional list throughout — no maps anywhere — so there is no key-ordering question to get wrong and no per-cell key repeated across a table with thousands of entries. Field names live in this file, not in the block; the layout version is what protects readers from drift.
The same model encodes to the same bytes and therefore the same CID on every run and every machine. That matters beyond tidiness: the model CID enters the plan hash (§10.4), so a plan pins a traversal only if this is stable.
func (*HMM) CID ¶
CID returns the model's content address. It is what `--model NAME@cid` pins and what enters the plan hash.
func (*HMM) Forward ¶
Forward is the forward filtering step, and the only inference this package performs at run time (§10.1).
prev is the parent's normalized log distribution; the result is this node's, also normalized. Normalizing every step is what keeps a long path from underflowing and makes the result independent of any constant factor in the emission tables.
If the observation is impossible under every state the filter would collapse to NaN, so the result falls back to uniform. That can only happen to a hand-written model with hard zeros: Dirichlet smoothing plus an explicit OOV symbol keeps every trained probability strictly positive.
func (*HMM) Lift ¶
Lift reconstructs a log distribution from a scalar belief.
graph.BeliefModel carries a float64 between parent and child, not a distribution, so the parent's full posterior is not available to Step and has to be reconstructed. Lift puts mass b on the focus states and 1-b on the rest, shaped within each group by the initial distribution — the maximum-entropy choice consistent with both the scalar and the model's own prior.
The reconstruction is exact when the focus set is a single state and there is one non-focus state, which is the canonical binary model, and exact when every state is in focus, which is the uniform model. It is an approximation only for a model with three or more states, where the scalar genuinely cannot carry the shape. See the note in belief.go.
func (*HMM) LogEmission ¶
LogEmission returns log P(obs | state) for a whole observation.
An observation is a set of symbols, one per prop the node has as of the current barrier, and they are combined as a product — a naive-Bayes factorization. Modelling the joint distribution over prop combinations instead would need a table exponential in the number of props and a corpus to match, for a quantity that only has to rank a frontier.
An empty observation contributes nothing, which is the correct answer for a candidate: it has no props yet, so its belief is the transition prior alone (§10.2).
func (*HMM) LogLikelihood ¶
LogLikelihood returns the corpus log-likelihood under this model. It is a training diagnostic — comparing two models on the same corpus — and never a number a user sees.
func (*HMM) LogTransition ¶
LogTransition returns log P(to | from, rel).
func (*HMM) Mass ¶
Mass returns the focus states' share of a log distribution — the scalar the engine calls belief. It is clamped to [0,1] so that accumulated floating point error can never hand the scheduler a value outside the range its thresholds assume.
func (*HMM) Provenance ¶
func (h *HMM) Provenance() Provenance
Provenance returns the training provenance recorded in the model block.
func (*HMM) SymbolIndex ¶
SymbolIndex resolves an emission symbol, falling back to OOVSymbol.
type Path ¶
type Path struct {
Steps []Trace
}
Path is one root-to-leaf expansion path, seed first.
A path and not a graph: the expansion tree gives every node exactly one parent, so seed → node is a sequence, which is what an HMM is defined over (§10.1). Steps[0] is the sequence start, drawn from the initial distribution; its Rel is ignored because the seed has no parent.
type Provenance ¶
type Provenance struct {
// Algorithm is how the tables were produced.
Algorithm string
// Seed is the RNG seed used to initialize training, recorded so that
// training reproduces exactly.
Seed int64
// Date is when training ran, in UTC. It is deliberately inside the block:
// unlike a scan, where timestamps would break cross-run CID equality, a
// model is a build artifact and when it was built is part of what it is.
Date time.Time
// Corpus are the CIDs of the trace blocks trained on, encoded as IPLD
// links so the model block references its corpus in the DAG.
Corpus []cid.Cid
// Iterations is the number of EM iterations actually run.
Iterations int
// LogLikelihood is the corpus log-likelihood of the final tables. It is a
// training diagnostic and never a user-facing number.
LogLikelihood float64
}
Provenance records where a model came from (§10.4). It is part of the addressed block, not a side file, because a model's identity includes what it was fitted on: two models with identical tables but different corpora are not interchangeable, and a plan pinning one must not silently accept the other.
type Result ¶
type Result struct {
// Model is the fitted HMM, with provenance already filled in.
Model *HMM
// LogLikelihood is the corpus log-likelihood before each M-step, plus the
// value for the final model. Under a prior, EM is only guaranteed to
// improve Objective, so this series may dip; it is reported because it is
// the quantity a person actually reads.
LogLikelihood []float64
// Objective is LogLikelihood plus the Dirichlet log-prior, evaluated on the
// same series of models. MAP-EM guarantees this is non-decreasing, and that
// is the guarantee worth testing.
Objective []float64
// Iterations is the number of M-steps performed, which may be fewer than
// Config.Iterations if the run converged.
Iterations int
}
Result is a training run and its diagnostics.
func Train ¶
Train fits an HMM to recorded expansion traces by Baum-Welch (§10.4).
Training is where the backward recursion lives. §10.1 rules it out of run time — a model that only runs after expansion cannot save a network call — but offline, with the whole path in hand, forward-backward is what EM needs and costs nothing at scan time.
Everything that could vary between two runs over the same corpus is pinned: the alphabets are derived in sorted order rather than from map iteration, and parameter initialization comes from an explicit seeded PRNG rather than the global one. Training the same corpus with the same Config twice gives the same tables and therefore the same CID.
type Smoothing ¶
type Smoothing struct {
// Init is the prior on the seed's initial distribution.
Init float64
// Trans is the prior on each transition row, per relation.
Trans float64
// Emit is the prior on each state's emission row. It is what gives
// OOVSymbol its probability mass: the OOV symbol is never observed in
// training, so its entire posterior weight comes from this prior.
Emit float64
}
Smoothing holds the Dirichlet concentration parameters applied to every table row during training (§10.4). Each is the pseudo-count added to every cell of a row before it is normalized.
Smoothing is not cosmetic here. Expansion traces are sparse: a relation may appear a handful of times and a prop value once. Without a prior, an unobserved transition gets probability zero, and a single zero anywhere on a path annihilates the whole forward filter — a node the model has simply never seen becomes impossible rather than merely unlikely, and gets pruned with certainty. The prior is what keeps "unseen" distinct from "ruled out".
The values are also carried in the encoded model, so a retrained model is comparable with the one it replaces.
func DefaultSmoothing ¶
func DefaultSmoothing() Smoothing
DefaultSmoothing is add-one (Laplace) smoothing on every table. It is the weakest prior that still guarantees no zero anywhere, which is the property the forward filter actually needs.
type Spec ¶
type Spec struct {
// States is the latent status alphabet, in a fixed order that is part of
// the model's identity.
States []string
// Focus names the states whose posterior mass is reported as belief. It
// must be non-empty. Naming every state makes belief constant, which is the
// untrained degenerate case.
Focus []string
// Rels is the relation alphabet. OOVRelation is appended if absent.
Rels []string
// Symbols is the emission alphabet. OOVSymbol is appended if absent.
Symbols []string
// Init is P(state) for the seed, which has no parent. Barrier 0 assigns it.
Init []float64
// Trans is P(state | parent state, rel), keyed by relation name; rows are
// indexed by parent state. A relation absent from the map falls back to the
// OOVRelation table, and an absent OOVRelation table is uniform.
Trans map[string][][]float64
// Emit is P(symbol | state). A model with no emissions at all is a pure
// transition prior, which is exactly what a candidate node gets (§10.2).
Emit [][]float64
// Smoothing records the Dirichlet priors the tables were fitted under. It
// is carried for provenance and reused when the model is retrained.
Smoothing Smoothing
// Provenance records how the model was produced.
Provenance Provenance
}
Spec describes a model in ordinary probabilities, which is how a human writes one down. New normalizes and converts to log space; a decoded model bypasses this path so that a round trip is bit-exact (see codec.go).
type Trace ¶
type Trace struct {
// Parent is the belief the run actually acted on when this node was
// admitted. Baum-Welch does not read it: the latent chain already carries
// the parent's state, and conditioning on a number the previous model
// produced would train the new model to imitate the old one. It is
// recorded so a retrained model can be compared against the decisions the
// scan really made, and so a future discriminative fit has it.
Parent float64
// Rel is the relation that admitted this node. It is what the transition
// table is conditioned on. Ignored on the first step of a Path, which has
// no parent.
Rel string
// Props are the emission symbols for this node as of the barrier —
// typically "field=value" strings from a Featurizer. Empty is legitimate: a
// candidate has no props yet.
Props []string
// Outcome is the recorded result for this node, folded into the emission
// alphabet under OutcomePrefix. Empty means none was recorded.
Outcome string
}
Trace is one recorded expansion step: the (parent belief, relation, props, outcome) tuple that `typo --trace FILE` writes (§10.4).
Recording is opt-in for a reason — it persists observation data a normal scan discards — so this type is what a user has consented to keep, and nothing more.
Source Files