spn

package
v0.1.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 14, 2018 License: BSD-3-Clause Imports: 12 Imported by: 10

Documentation

Overview

Package spn contains the structure of an SPN.

Package containing graph manipulation functions.

Index

Constants

View Source 
const (
	// GaussMax is the maximum value of a standard gaussian, namely 1/sqrt(2*pi).
	GaussMax = 0.398942280 // 1/sqrt(2*pi) := max value of a standard Gaussian
)

Variables

This section is empty.

Functions

func BreadthFirst 

func BreadthFirst(G SPN, f func(SPN) bool)

BreadthFirst applies a function f to each node of the graph G. The graph traversal is node using a breadth-first search approach. If f returns false, then the search ends. Else, it continues.

func Complete 

func Complete(S SPN) bool

Complete returns whether the SPN is complete.

func ComputeHeight 

func ComputeHeight(S SPN) int

ComputeHeight computes the height of a certain SPN S.

func ComputeScope 

func ComputeScope(S SPN) []int

ComputeScope computes the scope of a certain SPN S.

func CountNodes 

func CountNodes(G SPN) (int, int, int)

CountNodes counts the number of nodes, returning the number of sum, product and leaf nodes in this order.

func Decomposable 

func Decomposable(S SPN) bool

Decomposable returns whether the SPN is decomposable.

func DepthFirst 

func DepthFirst(G SPN, f func(SPN) bool)

DepthFirst applies a function f to each node of the graph G. The graph traversal is node using a depth-first search approach. If f returns false, then the search ends. Else, it continues.

func Inference 

func Inference(S SPN, I VarSet) float64

Inference simply returns the value of S(I), without storing values for later use.

func InferenceY 

func InferenceY(S SPN, I VarSet, Y, y int) float64

InferenceY returns the value of S(I, Y=y). This convenience function allows for fast computation of soft inference values without having to create another VarSet for each valuation of Y.

func Marshal 

func Marshal(S SPN) []byte

func PostOrder 

func PostOrder(G SPN, C common.Collection) common.Collection

func PrintSPN 

func PrintSPN(S SPN, filename string)

Print writes a text representation of SPN S to file of name filename.

func RegisterGobType 

func RegisterGobType(t interface{})

RegisterGobType registers a new SPN type to be marshalled. If you want to create a new SPN type and be able to serialize it, you must implement interfaces GobEncoder and GobDecoder as well as call this function with a pointer to a concrete type (e.g. RegisterGobType(&NewSPNType{})). All basic SPN nodes are already registered.

func StoreMAP 

func StoreMAP(S SPN, I VarSet, tk int, storage *Storer) (SPN, int, VarSet)

StoreMAP takes an SPN S and stores the MAP values for an instance I on a DP table storage at the position designated by the ticket tk. Returns S and the ticket used (if tk < 0, StoreMAP creates a new ticket).

func TopSortDFS 

func TopSortDFS(G SPN, C common.Collection) common.Collection

TopSortDFS finds a topological sort using a DFS. The argument C indicates how the topological sorting should be ordered (it C is a queue, the function returns an inversed topological sort (dependency ordering); if C is a stack, the function returns the topological sorting).

func TopSortTarjan 

func TopSortTarjan(G SPN, C common.Collection) common.Collection

TopSortTarjan returns the topological sorting of a graph G. It follows the version described in [Tarjan, 1974] but in a non-recursive fashion. The argument C indicates how the topological sorting should be ordered (it C is a queue, the function returns an inversed topological sort (dependency ordering); if C is a stack, the function returns the topological sorting).

func TopSortTarjanFunc 

func TopSortTarjanFunc(G SPN, C common.Collection, f func(SPN) bool) common.Collection

TopSortTarjanFunc traverses the graph G following TopSortTarjan, but at each step we also perform a function f. Useful for computing inline operations at each topological sort insertion. If f returns false, then the topological sort halts immediately, preserving the Queue at the moment of falsehood. The argument C indicates how the topological sorting should be ordered (it C is a queue, the function returns an inversed topological sort (dependency ordering); if C is a stack, the function returns the topological sorting).

func TopSortTarjanRec 

func TopSortTarjanRec(G SPN, C common.Collection) common.Collection

TopSortTarjan returns the topological sorting of a graph G. It follows the version described in [Tarjan, 1974]. The argument C indicates how the topological sorting should be ordered (it C is a queue, the function returns an inversed topological sort (dependency ordering); if C is a stack, the function returns the topological sorting).

func TraceMAP 

func TraceMAP(S SPN, I VarSet) map[SPN]int

TraceMAP returns the max child index of each sum node in a map. We assume decomposability and completeness. When this condition is not met, one arbitrary MAP state is chosen. When the SPN is both decomposable and complete, it is easy to see that the induced MAP trace of the SPN's graph is a tree, and thus no two paths from the root to a leaf intersect. For the negative case, there can be two paths that do intersect, and thus we could have randomly chosen different max children in case of ties. In this case, TraceMAP chooses the first child it finds to meet the criteria.

Types

type Dataset 

type Dataset []map[int]int

Dataset is a dataset indexed by instances.

type Gaussian 

type Gaussian struct {
	Node
	// contains filtered or unexported fields
}

Gaussian represents a gaussian distribution.

func NewGaussian 

func NewGaussian(varid int, counts []int) *Gaussian

NewGaussian constructs a new Gaussian from a counting slice.

func NewGaussianFit 

func NewGaussianFit(varid int, counts []float64) *Gaussian

NewGaussianFit constructs a new Gaussian from GoNum's Fit function.

func NewGaussianMode 

func NewGaussianMode(varid int, counts []int) *Gaussian

NewGaussianMode constructs a new Gaussian centered on the Mode instead of the Mean.

func NewGaussianParams 

func NewGaussianParams(varid int, mu float64, sigma float64) *Gaussian

NewGaussianParams constructs a new Gaussian from a mean and variance.

func NewGaussianRaw 

func NewGaussianRaw(varid int, vals []float64) *Gaussian

NewGaussianRaw constructs a new Gaussian from a slice of values.

func (*Gaussian) ArgMax 

func (g *Gaussian) ArgMax(val VarSet) (VarSet, float64)

ArgMax returns both the arguments and the value of the MAP state given a certain valuation.

func (*Gaussian) GobDecode 

func (g *Gaussian) GobDecode(data []byte) error

GobDecode unserializes this gaussian node.

func (*Gaussian) GobEncode 

func (g *Gaussian) GobEncode() ([]byte, error)

GobEncode serializes this gaussian node.

func (*Gaussian) Max 

func (g *Gaussian) Max(val VarSet) float64

Max returns the MAP given a valuation.

func (*Gaussian) Params 

func (g *Gaussian) Params() (float64, float64)

Params returns mean and standard deviation.

func (*Gaussian) Sc 

func (g *Gaussian) Sc() []int

Sc returns the scope of this node.

func (*Gaussian) SubType 

func (g *Gaussian) SubType() string

SubType returns this leaf's subtype.

func (*Gaussian) Type 

func (g *Gaussian) Type() string

Type returns the type of this node.

func (*Gaussian) Value 

func (g *Gaussian) Value(val VarSet) float64

Value returns the probability of a certain valuation. That is Pr(X=val[varid]), where Pr is a probability function over a gaussian distribution.

type Indicator 

type Indicator struct {
	Node
	// contains filtered or unexported fields
}

Indicator is an indicator node of a variable value X=x. Its value is 1 if X=x or is not set, and 0 otherwise.

func NewIndicator 

func NewIndicator(varid int, v int) *Indicator

NewIndicator constructs a new indicator node.

func (*Indicator) ArgMax 

func (i *Indicator) ArgMax(val VarSet) (VarSet, float64)

ArgMax returns the MAP and the MAP state.

func (*Indicator) GobDecode 

func (i *Indicator) GobDecode(data []byte) error

func (*Indicator) GobEncode 

func (i *Indicator) GobEncode() ([]byte, error)

func (*Indicator) Max 

func (i *Indicator) Max(val VarSet) float64

Max returns the MAP.

func (*Indicator) Sc 

func (i *Indicator) Sc() []int

Sc returns the scope of this node.

func (*Indicator) Type 

func (i *Indicator) Type() string

Type returns the type of this node.

func (*Indicator) Value 

func (i *Indicator) Value(val VarSet) float64

Value returns the probability of a certain valuation. In the case of an indicator node, 1 if X=x or is not set and 0 otherwise.

type Mode 

type Mode struct {
	// contains filtered or unexported fields
}

Mode of a univariate distribution.

type Multinomial 

type Multinomial struct {
	Node
	// contains filtered or unexported fields
}

Multinomial represents a multinomial distribution.

func NewCountingMultinomial 

func NewCountingMultinomial(varid int, counts []int) *Multinomial

NewCountingMultinomial constructs a new Multinomial from a count slice.

func NewEmptyMultinomial 

func NewEmptyMultinomial(varid, m int) *Multinomial

NewEmptyMultinomial constructs a new empty Multinomial for learning. Argument m is the cardinality of varid.

func NewMultinomial 

func NewMultinomial(varid int, dist []float64) *Multinomial

NewMultinomial constructs a new Multinomial.

func NewScopedCountingMultinomial 

func NewScopedCountingMultinomial(varid int, esc []int, counts []int) *Multinomial

NewScopedCountingMultinomial does the same as NewCountingMultinomial except it allows multiple variable scope.

func (*Multinomial) ArgMax 

func (m *Multinomial) ArgMax(val VarSet) (VarSet, float64)

ArgMax returns both the arguments and the value of the MAP state given a certain valuation.

func (*Multinomial) GobDecode 

func (m *Multinomial) GobDecode(data []byte) error

GobDecode unserializes this multinomial node.

func (*Multinomial) GobEncode 

func (m *Multinomial) GobEncode() ([]byte, error)

GobEncode serializes this multinomial node.

func (*Multinomial) Max 

func (m *Multinomial) Max(val VarSet) float64

Max returns the MAP state given a valuation.

func (*Multinomial) Mean 

func (m *Multinomial) Mean() float64

Mean returns the mean of the distribution.

func (*Multinomial) MuSigma 

func (m *Multinomial) MuSigma() (float64, float64)

MuSigma returns the mean and standard deviation of the distribution.

func (*Multinomial) Pr 

func (m *Multinomial) Pr() []float64

Pr returns the discrete probability distribution.

func (*Multinomial) StdDev 

func (m *Multinomial) StdDev() float64

StdDev returns the standard deviation of the distribution.

func (*Multinomial) SubType 

func (m *Multinomial) SubType() string

SubType returns this leaf's subtype.

func (*Multinomial) Type 

func (m *Multinomial) Type() string

Type returns the type of this node.

func (*Multinomial) Value 

func (m *Multinomial) Value(val VarSet) float64

Value returns the probability of a certain valuation. That is Pr(X=val[varid]), where Pr is a probability function over a Multinomial distribution.

type Node 

type Node struct {
	// contains filtered or unexported fields
}

Node represents a node in an SPN.

func (*Node) AddChild 

func (n *Node) AddChild(c SPN)

AddChild adds a child to this node.

func (*Node) ArgMax 

func (n *Node) ArgMax(val VarSet) (VarSet, float64)

ArgMax returns the MAP value and state given an evidence. (virtual)

func (*Node) Ch 

func (n *Node) Ch() []SPN

Ch returns the set of children of this node.

func (*Node) Compute 

func (n *Node) Compute(cv []float64) float64

Compute returns the soft value of this node's type given the children's values.

func (*Node) Height 

func (n *Node) Height() int

Returns the height of the graph.

func (*Node) Max 

func (n *Node) Max(val VarSet) float64

Max returns the MAP value of this node given an evidence. (virtual)

func (*Node) Parameters 

func (n *Node) Parameters() *parameters.P

Parameters returns the parameters of this object. If no bound parameter is found, binds default parameter values and returns.

func (*Node) Sc 

func (n *Node) Sc() []int

Sc returns the scope of this node.

func (*Node) SubType 

func (n *Node) SubType() string

SubType returns the subtype of this node.

func (*Node) Type 

func (n *Node) Type() string

Type returns the type of this node.

func (*Node) Value 

func (n *Node) Value(val VarSet) float64

Value returns the value of this node given an instantiation. (virtual)

type Product 

type Product struct {
	Node
}

Product represents a product node in an SPN.

func NewProduct 

func NewProduct() *Product

NewProduct returns a new Product node.

func (*Product) AddChild 

func (p *Product) AddChild(c SPN)

AddChild adds a child.

func (*Product) ArgMax 

func (p *Product) ArgMax(val VarSet) (VarSet, float64)

ArgMax returns both the arguments and the value of the MAP state given a certain valuation.

func (*Product) Compute 

func (p *Product) Compute(cv []float64) float64

Compute returns the soft value of this node's type given the children's values.

func (*Product) GobDecode 

func (p *Product) GobDecode(data []byte) error

func (*Product) GobEncode 

func (p *Product) GobEncode() ([]byte, error)

func (*Product) Max 

func (p *Product) Max(val VarSet) float64

Max returns the MAP state given a valuation.

func (*Product) Parameters 

func (p *Product) Parameters() *parameters.P

Parameters returns the parameters of this object. If no bound parameter is found, binds default parameter values and returns.

func (*Product) Sc 

func (p *Product) Sc() []int

Sc returns the scope of this node.

func (*Product) Type 

func (p *Product) Type() string

Type returns the type of this node.

func (*Product) Value 

func (p *Product) Value(val VarSet) float64

Value returns the value of this SPN given a set of valuations.

type SPN 

type SPN interface {
	// Value returns the value of this node given an instantiation.
	Value(val VarSet) float64
	// Compute returns the soft value of this node's type given the children's values.
	Compute(cv []float64) float64
	// Max returns the MAP value of this node given an evidence.
	Max(val VarSet) float64
	// ArgMax returns the MAP value and state given an evidence.
	ArgMax(val VarSet) (VarSet, float64)
	// Ch returns the set of children of this node.
	Ch() []SPN
	// Sc returns the scope of this node.
	Sc() []int
	// Type returns the type of this node.
	Type() string
	// SubType returns the subtype of this node.
	SubType() string
	// AddChild adds a child to this node.
	AddChild(c SPN)
	// Returns the height of the graph.
	Height() int
	// Parameters returns the parameters of this object.
	Parameters() *parameters.P
	// contains filtered or unexported methods
}

An SPN is a node.

func NormalizeSPN 

func NormalizeSPN(S SPN) SPN

NormalizeSPN recursively normalizes the SPN S.

func StoreInference 

func StoreInference(S SPN, I VarSet, tk int, storage *Storer) (SPN, int)

StoreInference takes an SPN S and stores the values for an instance I on a DP table storage at the position designated by the ticket tk. Returns S and the ticket used (if tk < 0, StoreInference creates a new ticket).

func Unmarshal 

func Unmarshal(buffer []byte) SPN

type Storer 

type Storer struct {
	// contains filtered or unexported fields
}

Storer allows for a mapping of node -> value, storing values for later use without having to recompute node values or derivatives (basically a Dynamic Programming table).

Let T be an array of DP tables. T has n entries, with each entry T[i] being a distinct DP table and independent of other tables T[j], j != i. We start with T having zero entries. We call a ticket a key k such that T[k] is a new empty DP table. Each ticket is unique and represent distinct DP tables. A table T[k][S] has m entries, with each entry T[k][S][l] a float64.

See NewTicket, Table and Value.

func NewStorer 

func NewStorer() *Storer

NewStorer creates a new Storer pointer with an empty set of tables.

func (*Storer) Delete 

func (s *Storer) Delete(k int)

Delete frees the memory at T[k]. A combination of Delete and NewTicket is NOT equivalent to using Reset. Prefer Reset over Delete + NewTicket.

func (*Storer) Entry 

func (s *Storer) Entry(k int, S SPN, l int) (float64, bool)

Entry returns the entry at Table T[k][S], given an SPN S and a position l, returning two values: the entry value and whether the position T[k][S][l] exists.

func (*Storer) Exists 

func (s *Storer) Exists(k int, S SPN, i int) bool

Exists returns whether a certain (key, value) pair exists in a Storer at second level.

func (*Storer) ExistsSPN 

func (s *Storer) ExistsSPN(k int, S SPN) bool

ExistsSPN returns whether a certain (key, value) pair exists in a Storer at first level.

func (*Storer) NewTicket 

func (s *Storer) NewTicket() int

NewTicket creates a new Ticket k and creates an empty map T[k].

func (*Storer) Purge 

func (s *Storer) Purge()

Purge deletes all tables in this storer.

func (*Storer) Reset 

func (s *Storer) Reset(k int) int

Reset resets the values at T[k], deleting the map and creating a new one over it. The ticket remains the same. Reset returns the ticket k.

func (*Storer) ResetTickets 

func (s *Storer) ResetTickets(K ...int)

ResetEntries resets all store tables whose tickets were given.

func (*Storer) Single 

func (s *Storer) Single(k int, S SPN) (float64, bool)

Single returns the first entry at Table T[k][S]. Equivalent to Entry(k, S, 0).

func (*Storer) Store 

func (s *Storer) Store(k int, S SPN, l int, e float64) bool

Store stores entry e in position T[k][S][l]. Returns whether the operation was successful.

func (*Storer) StoreSingle 

func (s *Storer) StoreSingle(k int, S SPN, v float64) bool

StoreSingle sets the first entry of Table T[k][S] to v. Returns whether the operation was successful. Equivalent to Store(k, S, 0, v).

func (*Storer) Table 

func (s *Storer) Table(k int) (StorerTable, bool)

Table returns the table at ticket position k (i.e. returns T[k]). It returns a double value, with the first being the table (if it exists), and the second a boolean indicating if such table exists.

func (*Storer) Value 

func (s *Storer) Value(k int, S SPN) (map[int]float64, bool)

Value returns the value of the SPN S in table T[k], returning two values: its value and whether the position T[k][S] exists.

type StorerTable 

type StorerTable map[SPN]map[int]float64

StorerTable is a DP table for Storer.

func (StorerTable) Entry 

func (s StorerTable) Entry(S SPN, l int) (float64, bool)

Entry returns the entry at T[S][l], given an SPN S and a position l, returning two values: the entry value and whether the position T[S][l] exists.

func (StorerTable) Exists 

func (t StorerTable) Exists(S SPN, i int) bool

Exists returns whether a certain (key, value) pair exists in a StorerTable at second level.

func (StorerTable) ExistsSPN 

func (t StorerTable) ExistsSPN(S SPN) bool

ExistsSPN returns whether a certain (key, value) pair exists in a StorerTable at first level.

func (StorerTable) Single 

func (t StorerTable) Single(S SPN) (float64, bool)

Single returns the first entry of this table. Equivalent to Entry(S, 0)

func (StorerTable) Store 

func (t StorerTable) Store(S SPN, l int, e float64) bool

Store stores entry e in position [S][l]. Returns whether the operation was successful.

func (StorerTable) StoreSingle 

func (t StorerTable) StoreSingle(S SPN, v float64) bool

StoreSingle sets the first entry of this table to v. Returns whether the operation was successful. Equivalent to Store(S, 0, v)

func (StorerTable) Value 

func (t StorerTable) Value(S SPN) (map[int]float64, bool)

Value returns the value of the SPN S in this StorerTable, returning two values: its value and whether the position exists.

type Sum 

type Sum struct {
	Node
	// contains filtered or unexported fields
}

Sum represents a sum node in an SPN.

func NewSum 

func NewSum() *Sum

NewSum creates a new Sum node.

func (*Sum) AddChild 

func (s *Sum) AddChild(c SPN)

AddChild adds a child.

func (*Sum) AddChildW 

func (s *Sum) AddChildW(c SPN, w float64)

AddChildW adds a new child to this sum node with a weight w.

func (*Sum) AddWeight 

func (s *Sum) AddWeight(w float64)

AddWeight adds a new weight to the sum node.

func (*Sum) ArgMax 

func (s *Sum) ArgMax(val VarSet) (VarSet, float64)

ArgMax returns both the arguments and the value of the MAP state given a certain valuation.

func (*Sum) Compute 

func (s *Sum) Compute(cv []float64) float64

Compute returns the soft value of this node's type given the children's values.

func (*Sum) ComputeHard 

func (s *Sum) ComputeHard(cv []float64, scount float64) float64

ComputeHard returns the soft value using hard weights (unit weights). Expects only children values, and not weighted child value. Parameter scount is the smooth sum count constant.

func (*Sum) GobDecode 

func (s *Sum) GobDecode(data []byte) error

GobDecode unserializes this sum node, but does not recurse over its children.

func (*Sum) GobEncode 

func (s *Sum) GobEncode() ([]byte, error)

GobEncode serializes this sum node, but does not recurse over its children.

func (*Sum) Max 

func (s *Sum) Max(val VarSet) float64

Max returns the MAP value of this node given an evidence.

func (*Sum) Parameters 

func (s *Sum) Parameters() *parameters.P

Parameters returns the parameters of this object. If no bound parameter is found, binds default parameter values and returns.

func (*Sum) Sc 

func (s *Sum) Sc() []int

Sc returns the scope of this node.

func (*Sum) Type 

func (s *Sum) Type() string

Type returns the type of this node.

func (*Sum) Value 

func (s *Sum) Value(val VarSet) float64

Value returns the value of this node given an instantiation.

func (*Sum) Weights 

func (s *Sum) Weights() []float64

Weights returns weights if sum node. Returns nil otherwise.

type VarSet 

type VarSet map[int]int

VarSet is a variable set specifying variables and their respective instantiations.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.