-
Notifications
You must be signed in to change notification settings - Fork 150
ddp
Simple discrete dynamic programming implementation; nothing special. Supports different numbers of labels for each random variable, and has four cost function types, that optimise message passing when possible:
- different - One cost of they have the same label, another if they have a different label.
- linear - Cost calculated as a linear function of the label difference.
- ordered - One cost for same label, another cost for advancing the label by one, infinity for all other options. For when you have an alignment problem.
- full - Arbitrary cost matrix; expensive as there is no opportunity for optimisation.
If you are reading readme.txt then you can generate documentation by running make_doc.py
Contains the following files:
ddp.py - The file a user imports - provides the DDP class that contains all of the functionality.
info.py - Dynamically generated information about the cost functions.
test_*.py - Some test scripts, that are also demos of system usage.
readme.txt - This file, which is included in the html documentation.
make_doc.py - Builds the html documentation.
different: Sets one cost if they have the same label, another if they are different. Initialisation is an object that can be interpreted as a 1D numpy array of length 2 - first entry is the cost of being different, second entry the cost of being the same. It can optionally have a third entry, which will be an (integer) offset applied to the second set of indices (second node in the chain) to define which is the same. If a length 1 array is provided it assumes the cost of being the same is 0.
linear: A falloff based cost function, based on the linear distance between labels. The first variable is at the position of its state index (0, 1, 2 etc), but the second is at (i * scale + offset), where i is the state index. The cost is then the absolute distance between state positions, multiplied by mult. There is also cap, which limits how how the cost can go. You initialise with an entity that can be interpreted as a numpy array, 1D, 4 entries: [mult = 1.0, offset = 0.0, scale = 1.0, cap = inf]. If its too short then the defaults just given are used. Note that mult and cap both have abs applied before use, so you can't have a dissimilarity-encouraging cost.
ordered: For when you are labeling something that is strictly ordered, and the optimisation is where to put the cuts - the output is such that the state indices are increasing. Typically when requesting the best solution you ask for it fixed to use the last state of the last variable. Allows you to set the cost of putting the cut versus not cutting, and also includes the option of skipping a label entirly, with you setting the cost of doing so. Takes as input an object that can be interpreted as a 1D numpy array of floats, of at least length two. The first entry is the cost of staying on the same label, the second of moving to the next label. If included the third is the cost of skipping one label, and so on.
full: Simply uses a complete cost matrix, which is provided as its only parameter as an entity that can be interpreted as a 2D float32 numpy array indexed [first index, second index]. Note that this is O(#first * #second) as there are no tricks here. If the input is a numpy float32 array then it will keep a reference and use it directly - good for memory usage, but be aware that editting such a matrix afterwards will matter. If the matrix is too small in either dimension it will access modulus the size in that dimension - this can be used to repeat costs without the storage cost.
An object for performing discrete dynamic programming - a fairly basic algorithm really. Supports multiple cost function forms however. Constructor takes no parameters; instead you call the prepare(...) method.
backpass(?)
After solving the problem this does the reverse pass, such that you have pointers in both directions for all random variables - this allows you to find the best solution and its cost, under the constraint that a single random variable is set to a given state. Automatically runs solve if it has not already been run.
best(?)
Returns (map solution, cost). The map solution is an array indexed by random variable that gives the state the random variable should be in to obtain the minimum cost state - cost is that minimum cost. You can optionally pass in two indices - the first an index to a random variable, the second its state. In this case it returns the optimal solution under the constraint that the given random variable is set accordingly. If solve has not been run it is run automatically. In the case of constrained solutions for any variable except the last it requires that backpass has been run - it will again automatically do this if it has not. If you only give it one parameter it assumes you mean the last variable with that state.
costs(?)
Given the index of a random variable returns an array indexed by the state of the random variable, that gives the minimum cost solution when the random variable is set to the given state. If this is called without solve and backpass (for any random variable except the last) having been called it will automatically call them.
description(?)
A static method that is given a pair cost type name and then returns a string describing it. Returns None if its not recognised.
names(?)
A static method that returns a list of the pair cost types, as strings (names) that can be used to instanciate them.
pairwise(?)
Allows you to set the pairwise terms - this gets complicated as the system uses a modular system for deciding the cost of label pairs - see the names and description method to find out about the modules avaliable (The provided info.py script prints this all out). Parameters are (offset, name, data): offset - the random variable to offset to - it is the index of then first one, so the cost is between offset and offset+1; name is the name of the cost module system to invoke - if its a single name then we are setting a single pairwise term, but if its a list of them then we are setting multiple costs, starting from offset (['name'] * count is your friend!); data is the data required - this depends on the pairwise cost module being invoked. If a single name is provided it is passed straight through, but if a list of names is provided it is interpreted as a list and the relevent entry passed through for each initialisation. Be warned that it may keep views to the input rather than copies, so its generally best to not edit any data passed in afterwards. This can get quite clever - it will happily handle a data matrix for instance. Be warned that this methods modular nature forces it to be quite intensive - it can be relativly slow. Note that the default state of a pairwise term, which can be set by passing in a zero length string as a name, is to have no link between the adjacent terms - using this you can store multiple independent dynamic programming problems in a single object. I have no idea why you might want to do this, but it seemed like a reasonable default.
prepare(?)
Prepares the object - must be called before you do anything. Wipes out any unary or pairwise potentials that have been set (All unary values are set to 0, all pairwise terms are cut). You provide either two integers as parameters - number of variables followed by number of labels per variable, or one input, which is interpreted as a 1D numpy array of integers: the number of labels per random variable, with the length of the array being the number of random variables.
solve(?)
Solves the problem, such that you can extract the MAP solution. Note that this gets called automatically by the map method if it has not been run, so you can ignore this if you want.
unary(?)
Allows you to set the costs (negative log likelihoods) of the unary term for each random variable. Takes two parameters - the first an offset into the random variables, the second something that can be interpreted as a numpy array. If the array is 1D then it effectivly eats every value within until the end of the array, starting at the first label of the indexed random variable and overflowing into further random variables - this can be very useful if the random variables have variable label counts, as you can pack them densely into the provided array. If the array is 2D then it interprets the first dimension as indexing a random variable, added to the offset, and the second a label for that random variable. In both cases limits are respected, and either the input not used or the unary cost left at whatever value it was previously (It defaults to 0).
variables = Number of random variables in the dynamic programming object.