PyConcat.kBestViterbi package¶
Submodules¶
PyConcat.kBestViterbi.kBestViterbi module¶
-
PyConcat.kBestViterbi.kBestViterbi.
exhaustive
(pi, A, O, observations)¶ Exhaustive Search for verification of Viterbi
Parameters: - pi – 2d numpy initial probability matrix
- A – 2d numpy transition matrix
- O – 2d numpy emission matrix
- observations – observation sequence
Returns: the best scoring sequence and a list of all sequences
-
PyConcat.kBestViterbi.kBestViterbi.
exhaustiveWithCosts
(a, b)¶ Exhaustive Search for verification of Viterbi tasks but using costs for concatenative synthesis
Parameters: - a – 2d numpy transition matrix
- b – 2d numpy emission matrix
Returns: sorted list of hidden state sequences
-
PyConcat.kBestViterbi.kBestViterbi.
kViterbiParallel
(pi, a, b, obs, topK)¶ Parallel List Viterbi Decoding using a rank sorted heaps.
Parameters: - pi – 2d numpy initial probability matrix
- a – 2d numpy transition matrix
- b – 2d numpy emission matrix
- obs – observation sequence
- topK – the number of paths we want to return
Returns: tuple containing the path, the probabilities, the delta and phi matrices
-
PyConcat.kBestViterbi.kBestViterbi.
kViterbiParallelWithCosts
(a, b, topK, weights=(1.0, 1.0))¶ Parallel List Viterbi Decoding using a rank sorted heaps.
This is with costs for concatenative synthesis
Parameters: - a – 2d numpy transition matrix
- b – 2d numpy emission matrix
- topK – How many best scoring paths we want to return
- weights – array of weights for the targetCost and concatenationCost
Returns: tuple containing the path, the probabilities, the delta and phi matrices
-
PyConcat.kBestViterbi.kBestViterbi.
viterbi
(pi, a, b, obs)¶ Parallel List Viterbi Decoding using a rank sorted heaps.
Parameters: - pi – 2d numpy initial probability matrix
- a – 2d numpy transition matrix
- b – 2d numpy emission matrix
- obs – observation sequence
Returns: tuple containing the path, the delta, the phi and the probability
-
PyConcat.kBestViterbi.kBestViterbi.
viterbiWithCosts
(a, b, weights=(1.0, 1.0))¶ Viterbi Algorithm with costs for concatenative synthesis
Parameters: - a – 2d numpy transition matrix
- b – 2d numpy emission matrix
- weights – array of weights for the targetCost and concatenationCost
Returns: tuple containing the path, the probabilities, the delta and phi matrices
PyConcat.kBestViterbi.model_tcohn module¶
PyConcat.kBestViterbi.model_wiki module¶
PyConcat.kBestViterbi.networkx_viterbi module¶
-
PyConcat.kBestViterbi.networkx_viterbi.
createPrunedViterbiGraphWithCosts
(a, b, topK, weights=(1.0, 1.0))¶ Return a NetworkX compabitible graph for computing k Best Paths for Viterbi Decoding
Uses costs for concatenative synthesis purposes
Parameters: - a – 2d numpy transition matrix
- b – 2d numpy emission matrix
- topK – the number of paths we want to retain
- weights – the target cost weighting and concatenation cost weighting
Returns: a Directed Acyclic Graph representing a HMM
-
PyConcat.kBestViterbi.networkx_viterbi.
createViterbiGraph
(pi, a, b, obs)¶ Return a NetworkX compabitible graph for computing k Best Paths for Viterbi Decoding
Parameters: - pi – 2d numpy initial probability matrix
- a – 2d numpy transition matrix
- b – 2d numpy emission matrix
- obs – observation sequence
Returns: a Directed Acyclic Graph representing a HMM
-
PyConcat.kBestViterbi.networkx_viterbi.
createViterbiGraphWithCosts
(a, b, weights=(1.0, 1.0))¶ Return a NetworkX compabitible graph for computing k Best Paths for Viterbi Decoding
Uses costs for concatenative synthesis purposes
Parameters: - a – 2d numpy transition matrix
- b – 2d numpy emission matrix
- topK – the number of paths we want to retain
- weights – the target cost weighting and concatenation cost weighting
Returns: a Directed Acyclic Graph representing a HMM
-
PyConcat.kBestViterbi.networkx_viterbi.
kViterbiGraph
(pi, a, b, obs, topK)¶ Compute k Best paths using k shortest paths decoding
Parameters: - pi – the starting probabilities
- a – the transition matrix
- b – the emission matrix
- obs – the observation sequence
- topK – the number of paths to return
Returns: the paths and their costs
-
PyConcat.kBestViterbi.networkx_viterbi.
kViterbiGraphWithCosts
(a, b, topK, weights=(1.0, 1.0))¶ Compute k Best paths using k shortest paths decoding
Uses weighted costs for concatenative synthesis purposes
Parameters: - a – the transition matrix
- b – the emission matrix
- topK – the number of paths to return
- weights – target and concatenation weights
Returns: the paths and their costs
-
PyConcat.kBestViterbi.networkx_viterbi.
shortestPaths
(G, topK, negativeLogSpace=True)¶ Compute the k Shortest Paths, optionally in negative log space
Parameters: - G – A directed acyclic graph
- topK – the number pof paths
- negativeLogSpace – use negative log space
Returns: The paths and their costs
PyConcat.kBestViterbi.simple_paths_with_costs module¶
-
PyConcat.kBestViterbi.simple_paths_with_costs.
all_simple_paths
(G, source, target, cutoff=None)¶ Generate all simple paths in the graph G from source to target.
A simple path is a path with no repeated nodes.
G : NetworkX graph
- source : node
- Starting node for path
- target : node
- Ending node for path
- cutoff : integer, optional
- Depth to stop the search. Only paths of length <= cutoff are returned.
- path_generator: generator
- A generator that produces lists of simple paths. If there are no paths between the source and target within the given cutoff the generator produces no output.
>>> G = nx.complete_graph(4) >>> for path in nx.all_simple_paths(G, source=0, target=3): ... print(path) ... [0, 1, 2, 3] [0, 1, 3] [0, 2, 1, 3] [0, 2, 3] [0, 3] >>> paths = nx.all_simple_paths(G, source=0, target=3, cutoff=2) >>> print(list(paths)) [[0, 1, 3], [0, 2, 3], [0, 3]]
This algorithm uses a modified depth-first search to generate the paths [1]. A single path can be found in O(V+E) time but the number of simple paths in a graph can be very large, e.g. O(n!) in the complete graph of order n.
[1] R. Sedgewick, “Algorithms in C, Part 5: Graph Algorithms”, Addison Wesley Professional, 3rd ed., 2001. all_shortest_paths, shortest_path