Systems, device, and methods for parameter optimization

1. A system for optimizing parameters of a structured prediction model, the system comprising:

a computer-readable medium;

a parameter optimization processor coupled to the computer-readable medium; and

a communication interface coupled to the parameter optimization processor and adapted to receive and transmit electronic representations of structured prediction models to and from the parameter optimization processor, respectively,

the computer-readable medium having stored thereon software instructions that, when executed by the parameter optimization processor, cause the parameter optimization processor to perform operations including:

initializing a group of parameters to respective values corresponding to a state within a set of allowable structured prediction models;

bounding a partition function across a number of variable pairs to generate a plurality of bounds each being a quadratic upper bound on a partition function;

determining new values for the group of parameters that minimize a sum of the plurality of bounds;

setting the group of parameters to the new values;

optimizing the parameters by iteratively performing the bounding, determining and setting; and

stopping the optimizing when a termination condition is reached.

2. The system of claim 1 , wherein the bounding includes updating a partition function value, a gradient and a curvature of the quadratic upper bound.

3. The system of claim 1 , wherein the termination condition includes determining that a difference between a conditional likelihood based on the current parameters and a previous conditional likelihood based on previous parameters is less than a predetermined value.

4. The system of claim 1 , wherein the termination condition includes determining that a difference between a current set of parameters and a previous set of parameters is less than a predetermined threshold value.

5. The system of claim 1 , wherein the termination condition includes performing a predetermined number of iterations.

6. The system of claim 1 , wherein the termination condition includes performing the bounding, determining and setting for a predetermined period of time.

7. The system of claim 1 , wherein the set of allowable models forms a convex hull.

8. The system of claim 1 , wherein each variable pair includes an observed input value and an observed output value.

9. The system of claim 1 , wherein each variable pair includes a first sample and a second sample from an unknown distribution.

10. The system of claim 1 , wherein the structured prediction model includes one of a deep belief network, a machine learning model, a pattern recognition model, a shallow parsing model, a named entity recognition model, a gene finding model, an object recognition model and an image segmentation model.

11. A computerized method for optimizing parameters for a structured prediction system, the method comprising:

initializing a group of parameters to respective values corresponding to a state within a set of allowable models;

bounding a partition function across a number of variable pairs to generate a plurality of bounds, wherein the bounding includes computing a quadratic upper bound on the partition function;

determining new values for the group of parameters that minimize a sum of the plurality of bounds;

setting the group of parameters to the new values;

optimizing the parameters by iteratively performing the bounding, determining and setting; and

stopping the optimizing when a termination condition is reached.

12. The method of claim 11 , wherein the bounding includes updating a partition function value, a gradient and a curvature of the quadratic upper bound.

13. The method of claim 11 , wherein the termination condition includes determining that a difference between a conditional likelihood based on the current parameters and a previous conditional likelihood based on previous parameters is less than a predetermined value.

14. The method of claim 11 , wherein the termination condition includes determining that a difference between a current set of parameters and a previous set of parameters is less than a predetermined threshold value.

15. The method of claim 11 , wherein the termination condition includes performing a predetermined number of iterations.

16. The method of claim 11 , wherein the termination condition includes performing the bounding, determining and setting for a predetermined period of time.

17. The method of claim 11 , wherein the set of allowable models forms a convex hull.

18. The method of claim 11 , wherein each variable pair includes an observed input value and an observed output value.

19. The method of claim 11 , wherein each variable pair includes a first sample and a second sample from an unknown distribution.

20. The method of claim 11 , wherein the structured prediction system includes one of a machine learning system, a pattern recognition system, a shallow parsing system, a named entity recognition system, a gene finding system, an object recognition system and an image segmentation system.

21. The method of claim 11 , wherein the bounding includes:

providing a graphical model arranged as a junction tree;

computing bounds for a set of variables that a clique of the junction tree has in common with a parent clique of the clique;

collecting pre-computed bounds from child cliques of the clique;

updating quadratic bound variables for the clique based on the computed bounds and the collected pre-computed bounds;

terminating the updating when a root clique is reached; and

outputting a curvature of a partition function bound, a partition function value and a gradient,

wherein the computing, collecting and updating are performed recursively beginning with leaf cliques of the junction tree and progressing toward root cliques.

22. The method of claim 11 , wherein the bounding includes:

computing a partition function value;

computing a gradient vector for a number of indices; and

computing a curvature of a bound, wherein the curvature is stored as a group of low rank matrices including a first matrix having singular values, a second matrix having eigenvectors and a third matrix being a diagonal matrix.

23. A computerized method for optimizing parameters for a structured prediction system, the method comprising:

initializing a group of parameters to respective values corresponding to a state within a set of allowable models;

bounding a partition function, wherein the bounding includes one or more of:

a) computing a quadratic upper bound on the partition function;

b) iteratively computing upper bounds on the partition function and selecting parameters to minimize a sum of the bounds;

c) computing a partition function bound for a latent likelihood model;

d) computing a partition function bound for a graphical model; and

e) computing a partition function bound for a high dimensional model using a plurality of matrices to represent a curvature of the partition function bound;

determining new values for the group of parameters based on the bounding;

setting the group of parameters to the new values;

optimizing the parameters by iteratively performing the bounding, determining and setting; and

stopping the optimizing when a termination condition is reached.

24. The method of claim 23 , wherein the optimizing converges monotonically.

25. The method of claim 23 , wherein the optimizing converges monotonically when the bounding includes computing a partition function bound for a latent likelihood model.