Learning A* priority function from unlabeled data

A technique for increasing efficiency of inference of structure variables (e.g., an inference problem) using a priority-driven algorithm rather than conventional dynamic programming. The technique employs a probable approximate underestimate which can be used to compute a probable approximate solution to the inference problem when used as a priority function (“a probable approximate underestimate function”) for a more computationally complex classification function. The probable approximate underestimate function can have a functional form of a simpler, easier to decode model. The model can be learned from unlabeled data by solving a linear/quadratic optimization problem. The priority function can be computed quickly, and can result in solutions that are substantially optimal. Using the priority function, computation efficiency of a classification function (e.g., discriminative classifier) can be increased using a generalization of the A* algorithm.

BACKGROUND

With processor speed and efficiency increases, computers have frequently employed artificial intelligence techniques to solve complex problems. These artificial intelligence techniques can be used to classify to which of a group of categories, if any, a particular item belongs. More particularly, inference problems involving structured outputs occur in a number of problems such as entity extraction, document classification, spam detection, sophisticated user interfaces, and the like.

Conventionally, dynamic programming has been widely used for decoding probabilistic models with structured outputs such as Hidden Markov Models (HMMs), Conditional Random Fields (CRFs), semi-Markov CRFs, and Stochastic Context Free Grammars (SCFGs). While dynamic programming yields a polynomial time algorithm for decoding these models, it can be too slow. For example, finding the optimal parse in a SCFG requires O(n3) time, where n is the number of tokens in the input. When SCFGs are used for decoding extremely large inputs (such as in information extraction applications) or bioinformatics applications, an O(n3) algorithm can be excessively expensive. Even for simpler models like HMMs, for which decoding is O(n), the hidden constants (a quadratic dependence on the number of states) can make dynamic programming unusable when there are many states.

As a result, a number of alternatives to dynamic programming have been proposed such as Beam search, best-first decoding, and A* algorithm. A* is a graph search algorithm that employs a heuristic estimate that ranks each node by an estimate of the best route that goes through that node. Neither beam search nor best-first decoding are guaranteed to find the optimal solution. While A* is guaranteed to find the optimal solution, using A* requires finding admissible underestimates. Both A* and best-first decoding fall into a class of algorithms called priority-based search techniques. A priority queue of partial solutions is maintained, and at each step, the partial solution with the lowest value of the priority function is taken off the queue. This partial solution is expanded to generate other partial/complete solutions which are added to the queue. This process continues until a complete solution is taken off the priority queue, at which point the search stops. Best-first decoding uses the cost of the current solution as the priority function guiding the search, while A* uses the sum of the cost of the current solution and an optimistic estimate (underestimate) of the cost of completing the solution.

SUMMARY

A technique for increasing efficiency of inference of structure variables (e.g., an inference problem) using a priority-driven algorithm rather than conventional dynamic programming is provided. The technique employs a probable approximate underestimate which can be used to compute a probable approximate solution to the inference problem when used as a priority function (referred to herein as “a probable approximate underestimate function”) for a more computationally complex classification function (e.g., a discriminative classifier). The probable approximate underestimate function can have a functional form of a simpler and easier to decode model. The model can be learned, for example, from unlabeled data by solving a linear/quadratic optimization problem. The priority function can be computed quickly, and can result in solutions that are substantially optimal.

A computer-implemented system for inferring structured variables includes a classification function for classifying data. The classification function employs a priority function that utilizes a probable approximate underestimate learned from unlabeled data. The system provides a structured output of the data based on classification information computed by the classification function.

Using the priority function, the efficiency of a classification function (e.g., semi-Markov CRFs, discriminative parsers, and the like) can be increased using a generalization of an A* algorithm. Further, the technique resolves one of the biggest obstacles to the use of A* as a general decoding procedure (e.g., arriving at an admissible priority function).

DETAILED DESCRIPTION

The disclosed architecture employs a technique for increased efficiency in inferencing of structured variables (e.g., an inference problem) using a priority-driven algorithm rather than conventional dynamic programming. A priority-driven search algorithm returns an optimal answer if a priority function is an underestimate of a true cost function.

The technique employs a probable approximate underestimate which can be used to compute a probable approximate solution to the inference problem when used as a priority function (referred to herein as “a probable approximate underestimate function”) for a more computationally complex classification function. The probable approximate underestimate function can have a functional form of a simpler, easy to decode model than the classification function. Further, in one example, the model can be learned from unlabeled data by solving a linear/quadratic optimization problem. In this manner, the priority function can be computed quickly, and can result in solutions that are substantially optimal.

Using the technique, a classification function (e.g., semi-Markov CRFs, discriminative parsers, and the like) can be sped up using a generalization of the A* algorithm. Further, this technique resolves one of the biggest obstacles to the use of A* as a general decoding procedure, namely that of coming up with an admissible priority function. In one embodiment, applying the technique can result in an algorithm that is substantially more efficient for decoding semi-Markov Conditional Markov Models (e.g., more than three times faster than a dynamic programming algorithm such as the Viterbi algorithm).

Referring initially to the drawings,FIG. 1illustrates a computer-implemented system100for inferring structured variables. The system100includes a classification function110for classifying data and employs a priority function120that utilizes a probable approximate underestimate learned from unlabeled data (e.g., probable approximate underestimate function). In this manner, the priority function120can be computed quickly, and can result in solutions that are substantially optimal.

The classification function110assigns a score to each of a plurality of hypothetical structured variables. Through inference, the classification function110searches for a best scoring hypothesis with the search being guided by the probably approximate priority function120. The system100then provides a structured output of the data based on classification information computed by the classification function110.

The system100is based on a technique for speeding up inference of structured variables using a priority-driven search algorithm rather than conventional dynamic programming. As noted previously, in general, a priority-driven search algorithm returns an optimal answer if the priority function is an underestimate of a true cost function.

In conjunction with the priority function120, the classification function110(e.g., semi-Markov CRFs, discriminative parsers, and the like) can employ a generalization of the A* algorithm, for example, to obtain increase classification efficiency. Further, the technique resolves one of the biggest obstacles to the use of A* as a general decoding procedure (e.g., an admissible priority function).

As priority-based techniques perform additional work at each step when compared to dynamic programming, the priority function120prunes a substantial part of the search space in order to be effective. Further, since the priority function120is computed for each step, for each partial solution, in one embodiment, the priority function120is computed quickly. In this embodiment, for A* to be effective (e.g., faster than the Viterbi algorithm), the underestimate needs to be “tight”, and fast to compute.

This has been one of the main obstacles to the general use of A* as computing tight, inexpensive underestimates can be difficult. Thus, algorithms which are fast, but offer no optimality guarantees (e.g., best-first decoding and beam search) have been introduced. Further, algorithms which prune the search space to find the optimal solution, but are often not as fast as the approximate algorithms have been generated. The priority function120is based on a general technique that can be used to produce solutions (e.g., close to optimal) by allowing tradeoffs between computations requirements and a degree of approximation

In order to more fully discuss the probable approximate underestimate function employed by the priority function120, in general, the prediction/inference problem is to find a mapping f:→Ψ, whereis the input space and Ψ is the output space such that
f(x)=argminyεYcost(y|x)

When there is an underlying probabilistic model, the scoring function cost(y|x) is typically the negative log likelihood −log p(y|x). However, it is to be appreciated there are other models where the cost function is not derived from a purely probabilistic model (e.g., margin based models, voting based models, loss based models, etc.) can be employed.

In many problems, the input and output spaces have associated structure. For example, the space Ξ can be the space of sequences of observations (e.g., words, nucleic/amino acids, etc.) and the output space Ψ can be the space of sequences of labels (e.g., part-of-speech tags, coding/non-coding binary labels, etc.). In these problems, the size of the input/output domains is exponential in the length of the sequences, and hence exhaustive search cannot be used to find argminyεYcost(y|x). In some cases, the cost function also has associated structure, such as the Markov property, which allows for computing argminyεYcost(y|x) in time polynomial in the length of the sequence.

For purposes of explanation, consider an example of labeling sequences of observations where the input space is=On, the output space is Ψ=Λn, and O and Λ are the set of observations and labels, respectively. It is to be appreciated that the techniques set forth herein apply to other structured prediction problems and the hereto appended claims are intended to encompass those structured prediction problems.

Each element l=l1, l2, . . . , lmεΛn=Ψ represents an assignment of a label to every observation in the input. Further, l[l:k]=l1, l2, . . . , lkcan be called a partial output and is an assignment of labels to a prefix of the input sequence. The cost function satisfies the Markov property if it assigns a cost to each partial output satisfying:
cost(l[l:k+1]|x)=cost(l[l:k]|x)+φk(k,lk+1|x)

Once φk(lk,lk+1|x) and cost(ll|x) are specified, the value of cost(l|x) can be computed for every label sequence lεΛn.

In one embodiment, the search for an optimal solution can be formulated as a shortest path problem in a graph G=(V, E) constructed as follows. The node set V comprises all pairs {t,l}1≦t≦n,lεΛ, where t is the time step of a node, and l is the label of the node. There are edges from nodet,lato nodet+1,lbfor every 1≦t<n and la, lbεΛ. The edge (t,la,t+1,lb) is given weight Φt(lb,la|x). Finally, a start node start and a goal node goal are added, and for every lεΛ, edges (start,1,l) with weight cost(l|x), and edges (n,l, goal) with weight 0 are added.

Observe that the label sequence l=1, l2, . . . , lncorresponds to the path start,1,l1,2,l2, . . . , goal, and that the weight of this path (e.g., sum of edges on this path) is exactly cost(l|x). Therefore, the least cost path (of length n) from start to goal corresponds to the desired optimal label sequence. Because there is one-to-one correspondence between label sequences in Ψ and path in G from start to goal, the two can be used interchangeably. The label sequence l corresponds to the path start,1,l1,2,l2, . . . ,n,ln, goal.k,lεl can be used to denote the fact that the nodek,lis on the path lεΨ (e.g., the lk=l).

Continuing, let α(k,l|x) be the cost of the least weight path from start tok,l. The cost of completion of a nodek,lis the cost of the least weight path fromk,lto goal, which can be denoted by β(k,l|x). Observe that α(k,l|x)+β(k,l|x) is the cost of the least weight path from start to goal going throughk,l. That is,

From this, Definition 1 can be provided as follows: a function lower: V→P is an admissible underestimate if for everyk,l, two conditions are met:Condition 1: lower(k,l|x)≦β(k,l|x).Condition 2: lower(n,l|x)=0 for all lεΛ.

Condition (1) requires the function lower to be an optimistic estimate of the cost function, while condition (2) requires the estimate to be 0 for the last states of the path. Conventionally, a well known result provides that if lower is an admissible underestimate, and
prio(k,l|x)=cost(k,l|x)+(lowerk,l|x)
is used as a priority function for a priority driven search, then the optimal solution is guaranteed to be found. The admissible underestimates allow for pruning of parts of the search space, and can enable the algorithm (e.g., classifier) to find the optimal solution faster than the dynamic programming approach. However, maintaining the priority queue adds complexity to the algorithm, and hence for the technique to outperform the dynamic programming approach in practice, the estimate has to be reasonably sharp. For many cases, even when admissible underestimates can be found, the estimates tend to be loose, and hence do not result in a substantial speedup.

As noted previously, the priority function120employs a probable approximate underestimate. The probable approximate underestimate can be understood based on a relaxed notion of admissible underestimates and the effect on a priority driven search.

Consider Definition 2: A function lower˜: V→P is probably an (ε, δ)—approximate underestimate if,
lower˜(k,l|x)≦β(k,lx)+δ.
for everyk,land for a randomly drawn (x,y)ε×Ψ with probability at least 1-ε, and lower˜(n,l|x)=0 for all lεΛ.

In this embodiment, Definition 2 essentially requires lower˜ to be very close to being an underestimate most of the time. In this manner, as discussed below, using lower˜ to guide the priority driven search (e.g., the priority function120) of the system100, a solution which is substantially optimal can be obtained (e.g., almost optimal most of the time).

Consider Lemma 3: If lower˜ is probably an (ε, δ)—approximate underestimate, and
prio(k,l|x)=cost(k,l|x)+lower˜(k,l|x)
is used to guide the priority driven search, then with probability at least 1-ε, a solution within δ of optimal is found.

Proof of this lemma can be based on, if lower˜ satisfies the condition for x, then a solution within δ of the optimal is found. From this, the result follows, as discussed below. Initially, it is assumed that lower˜ satisfies the condition for x and that c=cost(lmin|x) is the cost of an optimal solution lmin.

Continuing, suppose that l is the first complete solution that comes off the priority queue, and assume that cost(l|x)>c+δ. Since lower˜ is an approximate underestimate, lower˜(l|x) must be equal to 0. Therefore, prio(l|x)=cost(l|x)+lower˜(l|x)>c+δ. Since lminhas not yet been pulled off the priority queue, either lminor some nodek,lεlminmust still be on the priority queue. Since there is a path fromk,lto lmin, prio(k,l|x)≦cost(lmin|x)+δ=c+δ must exist. Hence prio(k,lx)≦c+δ<prio(l|x), which means thatk,lshould have been pulled off the priority queue before l, a contradiction.

It is to be appreciated that a probabilistic approximate underestimate is more relevant in a statistical learning context than in a classical artificial intelligence (AI) context. When the state graph is generated from a model with no uncertainty, then the optimal solution is clearly the most desirable solution. In contrast, for machine learning applications the models are statistical in nature, and even the optimal solutions are “incorrect” some percentage of the time. Therefore, if the decoding algorithm fails to come up with the optimal answer for a fraction ε of the cases, then the error rate goes up by at most ε; the fundamental statistical nature of the algorithm does not change. Therefore, relaxation of the correctness requirement, as discussed above, can be beneficial to the decoding algorithm for machine learning algorithms.

Additionally, when the model parameters are estimated from small data sets, the difference between two solutions whose costs are very close may not be statistically significant. In these cases, it may make sense to settle for an approximately optimal algorithm, especially if it will result in a large saving in computation. Therefore, by employing probable approximate underestimates, priority functions can be chosen from a much richer set which can result in much faster inference.

Another consequence of using probably approximate underestimates is learning underestimates. Guaranteed underestimates are often loose, and the effectiveness of a model using these estimates must be verified through experiments. A tighter bound can be obtained by choosing a function that is the “best” underestimate on a finite training set. However, such a function is not guaranteed to be an underestimate on a different data set. However, generalization bounds from statistical learning theory can be used to show that as long as the class of underestimate functions is not too large, and the training data set is not too small, an approximate underestimate with high probability can be obtained. Learned underestimates can be much tighter (e.g., although with some probability of error).

Finally, learned probable approximate underestimates can be applied effectively to a much wider set of statistical models. A common technique for generative models is to estimate completion costs based on a summary of the context and/or grammar summarization. In a discriminative setting, where the costs take on a functional form, an estimate based on any meaningful summary of the context will be very loose. This is especially true in cases where the features are deterministically related. As discussed in greater detail below, a learned probably approximate underestimate can be directly applied to a discriminative model.

As mentioned previously, using a priority driven search algorithm can speed up computation because it can prune away large parts of the search space. However, each individual step is more expensive because priorities have to be computed, and because the priority order has to be maintained. A very good priority function that is very expensive to compute can well result in an overall decrease in speed. Therefore, it is important to consider both how quickly lower˜ can be computed and how sharp it is (e.g., how well it estimates the actual cost) when determining the priority function120.

If lower˜ has a similar structure to the cost function, then it is likely that lower˜ will be a sharp estimate. On the other hand, the more similar lower˜ and cost are, the more similar their computational complexity is, negating the benefit of the priority driven search. In one embodiment, the cost function of a linear-chain semi-Markov model can be approximated using the cost function of a linear chain Markov model.

Linear-chain Conditional Markov Models (CMMs) and semi-Markov CMMs are discriminative models that can be used for labeling sequence data. The input to these models are sequences of observations x=x1, x2. . . xn, and the model produces a sequence of labels drawn from the label sequence Λ. Both models assign costs (probabilities) to label sequences conditional on the input (observation) sequence. A widely used example of a CMM is a Conditional Random Field. However, while a CRF assigns a probability to a label sequencel1, l2. . . ln(conditional on the input observation sequence x), a CMM can be more general, and assign a score which can be based on a general loss function (e.g., the margin to a separating surface or on the number of votes from an ensemble). The cost that a CMM assigns to the label sequencel1, l2. . . ln(conditional on the input observation x) is given by:

Note that this cost could have been derived from the log-probability assigned by a linear-chain CRF whose underlying linear graphical model has (maximal) cliques with potential functions of the form:

A semi-Markov model is one where each hidden state is associated with a set of observations. These models provide a richer mechanism for modeling dependencies between observations associated with a single state. While the most natural language for describing such models is generative, the framework discussed below can be applied to discriminative models as well.

The cost that the semi-Markov CMM assigns to the segment/label sequencel[s1:s2), l[s2,s3), . . . , l[sm−1,sm+1)is given by

costscmm⁡(〈l[s1⁢:⁢s2),l[s2,s3),…⁢,l[sm-1,sm+1)〉⁢❘⁢x)=∑t=1m-1⁢ψ(St+1,St+2)⁡(l[st,st+1),l[st+1,st+2),x)
where the potentials Ψtare given by

Each semi-Markov CMM feature fεΦscmmcan be a function of the observations, the current segment [st+1, st+2), and the current and previous labels l[st−1,st) and l[st+1). Note that Φscmm,is richer than Φcmm, the set of features available to the CMM, because the semi-Markov features f(st, st+1, l[st,st+1), l[st+1,st+2), x) can also depend on the entire segments [st, st+1). As a result, semi-Markov CMMs typically yield higher accuracies than CMMs. However, the decoding time for these models is O(n2). Those skilled in the art will recognize that techniques for improving the efficiency of inference in semi-Markov CMMs by reorganizing the clique potential computation can be employed in conjunction with the technique described herein to yield greater increases in speed.

In one embodiment, costcmmcan be used as a probable approximate underestimate for costscmm. The graph GS=(VS, ES) can be described corresponding to the search problem for semi-Markov Models. The node set Vs={s,r,l: 1≦s<r≦n, lεΛ}∪{start, goal}. As such, each node corresponds to the time range [s, r) and label l. There are edges between nodess,r,l,andr,q,l2for 1≦s<r<q≦n, and this edge has cost

∑f⁢⁢ε⁢⁢Φcmm⁢λf⁢f⁡(s,r,t,l1,l2,x).
A common pruning step is to place a limit W on the length of the largest segment, only allowing nodess,r,lwhich satisfy r−s<W. In this case, the decoding time required for the dynamic programming solution reduces to O(n·W). However, it is often the case that WεO(n), and hence, this may not result in substantial savings.

The cost of completion (cost to goal) is the cost of the least cost path to the goal and any function which is less than this can serve to be an optimistic estimate to the goal. βscmm(sk,sk+1,lk|x) denotes the cost of the least cost path fromsk,sk+1,lkto goal. A completion path is of the formsk,sk+1,lk,sk+1,sk+2,lk+1, . . . ,sm,sm+1,lmwhere sm+1=n, and its cost is given by

So βscmm(sk,sk+1,lk) is the least value of all costs of the above form (this can be computed by dynamic programming in polynomial time). The next step is to estimate a function that will serve as a probabilistic approximate underestimate for β. Given the similarity in the forms of the cost functions of CMMs, costcmm, and the cost functions of the semi-Markov Model, costscmm, it is intuitive to determine if costcmmcan be used to generate the desired probabilistic approximate underestimate for the priority function120.

Given a CMM search graph with nodest,l> and a semi-Markov Model with nodess,r,l, a mapping can be performed:s,r,ls,l(e.g., a many-to-one mapping). βscmm(s,r,l) can be estimated using βcmm(s,l). For this, it is desired that:
βcmm(s,l|x)≦βscmm(s,r,l|x)+δ
for every nodes,r,lεVsfor all but an ε fraction of the input/output pairs.

Therefore, (the parameters of) a CMM are sought, which satisfies this condition. Observe that this is a circularity in the requirements here. The optimal path used for completion in the CMM depends on the costcmm. However, it is desired to pick costcmmbased on the optimal completion path. In one embodiment, the following can be employed to resolve this circularity. Let F=z1, z2, . . . , znbe the label sequence generated by a computationally cheap classifier (e.g., a classifier obtained by boosting small-depth decision trees). For any node,s,lεV, a completion path P(z,s,l)=s,l>,s+1,zs+1, . . . ,sn,zncan be generated. Costcmmcan be selected to satisfy:
costcmm(P(z,s,l))≦βscmm(s,r,l|x)+δ  Eq. (1)

Since the cost of the optimal path is less than the cost of any fixed path:
βcmm(s,l|x)≦costcmm(P(z,s,l)≦βscmm(s,r,lx)+δ

Therefore, if costcmmcan be found probably satisfying this condition, it can be used as a probabilistic approximate underestimate. This condition translates to

The parameters (variables) of the priority function120that can be selected are {λf}fεΦcmm. In one embodiment, these values can be estimated from data as the solution to an optimization problem.

Referring toFIG. 2, a priority function200estimated from data as a solution to an optimization problem is illustrated. First, suppose that a collection of unlabeled sequences {x(i)}i=lN, and a trained semi-Markov model are provided. It is desired to estimate parameters210of a CMM {λf}fεΦcmmso that the resulting cost function satisfies Equation (1) above. For each sequence x(i), let z(i)be the output label sequence from a computationally simple classifier. For each example 1≦i≦N, and for each states,r,l, let:

By taking:
δ(i,s,r,l)δ−μ  Eq. (2)
(where μ≧0 is analogous to a margin) Equation (1) is satisfied. The details are omitted for the sake of brevity, but generalization bounds, much like those obtained for support vector machines (SVMs) can be obtained for the underestimate as well. The reason for introducing the “margin” μ is introduced to enable proof of the generalization bounds (e.g., so that the resulting solution which is an approximate underestimate on the test set is also an approximate underestimate on the training set). Larger values of μ and N make it more likely that the generated CMM will also be an underestimate on the test set. However, in one embodiment, smaller values of μ are desirable because this allows for tighter bounds.

In one embodiment, the value of a cost function220βscmm(s,r,l|x(i)) can be computed for all values ofs,r,lby simply running the dynamic programming algorithm and then reading the values off a table used to store partial results. While this can be an expensive operation, it only has to be done offline, and only once (e.g., per example). Similarly, values of features230of the semi-Markov model f(t, lt−1, lt|x(i)) can be computed for the examples once offline and hence the system of inequalities can be set up.

Observe that |δ(i,s,r,l)| measures the inexactness of the estimate. The smaller this quantity, the better the estimate. If δ(i,s,r,l)is negative, then

∑t=sn⁢∑f⁢⁢εΦcmm⁢λf⁢f⁡(t,lt-1,lt⁢❘⁢x(i))
is an underestimate for βscmm(s,r,l|x(i)). Enforcing the constraint given in Equation (2) ensures that an overestimate, if any cannot be more than δ−μ. In one embodiment, in order to make the estimate as sharp as possible, |δ(i,s,r,l)| is minimized and therefore, the objective function that is used for the constrained optimization is:
λ·∥f∥+Σ|δ(i,s,r,l)|

The term λ·∥f∥ acts as a regularizer. Both the l1and the l2norms can be used as both yield (different) generalization bounds because for a finite dimensional space, all norms differ by at most a constant. The advantage of using the1norm is that it often yields more sparse solutions, yielding added speedups by discarding features whose coefficients are zero. When using the l1norm, the resulting problem is a linear programming problem. When using the l2norm, the resulting problem is a quadratic programming problem (e.g., similar to a standard SVM problem).

Therefore, in this formulation, there are at most |Φcmm|+n2·N|Λ| variables, and at most n2·N|Λ| inequalities (plus the box constraints). Since the procedure only requires unlabeled examples, in one embodiment, the procedure is fed a tremendous amount of data. Since the size of the optimization problem (both the number of variables and the number of constraints) grows linearly with the number of examples N, the problem as formulated above very rapidly exhausts the capacity of most optimization procedures. However, as discussed below, two techniques can be used to extend the range of these procedures: (1) generating sparse problem formulations; and, (2) discarding inessential inequalities.

With respect to generating sparse problem formulations, representing n, equations/inequalities in n2variables using a dense matrix requires O(n1·n2) storage when using a dense matrix representation. When the problem can be formulated so that the equations/inequalities are sparse (e.g., so each inequality involves only a small number of variables), and if the optimization solver is able to exploit the sparsity of the formulation, both efficient representations and efficient solution procedures can be obtained. This allows for the storage of larger problems in memory, and for the problems to be solved more quickly. A slight modification of the formulation presented allows for the reduction of the number of non-zero entries significantly. For a fixed example x(i), consider the set of equations:

Observe that these two systems of equations are equivalent, except the second formulation has substantially fewer non-zero entries even though a few extra variables (e.g., n·N extra variables) have been added.

In another embodiment, in order to reduce the memory footprint, and speeding up the solution, several of the inequalities can be discarded completely. For example, y(i)be the optimal label sequence for the input sequence z(i). Then as long as Equation (1) holds for all the nodes on the optimal label sequence, then the result of Lemma 3 still holds. In fact, it is preferred that nodes that are not part of the optimal sequence get very pessimistic estimates, as this ensures that the nodes are not explored further, increasing the speed of the search algorithm. Therefore, if the inequalities corresponding to the nodes which are not part of the optimal label sequence are discarded, then while the CMM so generated will no longer be an approximate probabilistic underestimate, it is still guaranteed to produce approximately optimal solutions on the training data.

At300, unlabeled data is received (e.g., a collection of raw data). At302, a trained semi-Markov model is received. At304, a cost function is computed (e.g., obtaining values from a dynamic programming algorithm). At306, parameters of a linear-chain conditional Markov Model are computed based on the computed cost function, the trained semi-Markov model and the unlabeled data.

FIG. 4illustrates a method of classifying data. At400, a priority function having a probable approximate underestimate is learned from unlabeled data. At402, input data is received. At404, the input data is classified using the priority function to guide inference of a classifier. At406, information regarding the classified input data is provided (e.g., structured output of the data).

Referring now toFIG. 5, there is illustrated a block diagram of a computing system500operable to execute the disclosed technique. In order to provide additional context for various aspects thereof,FIG. 5and the following discussion are intended to provide a brief, general description of a suitable computing system500in which the various aspects can be implemented. While the description above is in the general context of computer-executable instructions that may run on one or more computers, those skilled in the art will recognize that a novel embodiment also can be implemented in combination with other program modules and/or as a combination of hardware and software.

With reference again toFIG. 5, the exemplary computing system500for implementing various aspects includes a computer502, the computer502including a processing unit504, a system memory506and a system bus508. The system bus508provides an interface for system components including, but not limited to, the system memory506to the processing unit504. The processing unit504can be any of various commercially available processors. Dual microprocessors and other multi-processor architectures may also be employed as the processing unit504. Referring briefly toFIGS. 1 and 5, the classification function110and/or the priority function120can be stored in the system memory506.

The system bus508can be any of several types of bus structure that may further interconnect to a memory bus (with or without a memory controller), a peripheral bus, and a local bus using any of a variety of commercially available bus architectures. The system memory506includes read-only memory (ROM)510and random access memory (RAM)512. A basic input/output system (BIOS) is stored in a non-volatile memory510such as ROM, EPROM, EEPROM, which BIOS contains the basic routines that help to transfer information between elements within the computer502, such as during start-up. The RAM512can also include a high-speed RAM such as static RAM for caching data.

The computer502further includes an internal hard disk drive (HDD)514(e.g., EIDE, SATA), which internal hard disk drive514may also be configured for external use in a suitable chassis (not shown), a magnetic floppy disk drive (FDD)516, (e.g., to read from or write to a removable diskette518) and an optical disk drive520, (e.g., reading a CD-ROM disk522or, to read from or write to other high capacity optical media such as the DVD). The hard disk drive514, magnetic disk drive516and optical disk drive520can be connected to the system bus508by a hard disk drive interface524, a magnetic disk drive interface526and an optical drive interface528, respectively. The interface524for external drive implementations includes at least one or both of Universal Serial Bus (USB) and IEEE 1394 interface technologies.

A number of program modules can be stored in the drives and RAM512, including an operating system530, one or more application programs532, other program modules534and program data536. All or portions of the operating system, applications, modules, and/or data can also be cached in the RAM512. It is to be appreciated that the disclosed architecture can be implemented with various commercially available operating systems or combinations of operating systems.

A user can enter commands and information into the computer502through one or more wired/wireless input devices, for example, a keyboard538and a pointing device, such as a mouse540. Other input devices (not shown) may include a microphone, an IR remote control, a joystick, a game pad, a stylus pen, touch screen, or the like. These and other input devices are often connected to the processing unit504through an input device interface542that is coupled to the system bus508, but can be connected by other interfaces, such as a parallel port, an IEEE 1394 serial port, a game port, a USB port, an IR interface, etc.

A monitor544or other type of display device is also connected to the system bus508via an interface, such as a video adapter546. In addition to the monitor544, a computer typically includes other peripheral output devices (not shown), such as speakers, printers, etc.

The computer502may operate in a networked environment using logical connections via wired and/or wireless communications to one or more remote computers, such as a remote computer(s)548. The remote computer(s)548can be a workstation, a server computer, a router, a personal computer, portable computer, microprocessor-based entertainment appliance, a peer device or other common network node, and typically includes many or all of the elements described relative to the computer502, although, for purposes of brevity, only a memory/storage device550is illustrated. The logical connections depicted include wired/wireless connectivity to a local area network (LAN)552and/or larger networks, for example, a wide area network (WAN)554. Such LAN and WAN networking environments are commonplace in offices and companies, and facilitate enterprise-wide computer networks, such as intranets, all of which may connect to a global communications network, for example, the Internet.

When used in a LAN networking environment, the computer502is connected to the local network552through a wired and/or wireless communication network interface or adapter556. The adaptor556may facilitate wired or wireless communication to the LAN552, which may also include a wireless access point disposed thereon for communicating with the wireless adaptor556.

When used in a WAN networking environment, the computer502can include a modem558, or is connected to a communications server on the WAN554, or has other means for establishing communications over the WAN554, such as by way of the Internet. The modem558, which can be internal or external and a wired or wireless device, is connected to the system bus508via the serial port interface542. In a networked environment, program modules depicted relative to the computer502, or portions thereof, can be stored in the remote memory/storage device550. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers can be used.

Referring now toFIG. 6, there is illustrated a schematic block diagram of an exemplary computing environment600that facilitates inference of structured variables. The system600includes one or more client(s)602. The client(s)602can be hardware and/or software (e.g., threads, processes, computing devices). The client(s)602can house cookie(s) and/or associated contextual information, for example.

The system600also includes one or more server(s)604. The server(s)604can also be hardware and/or software (e.g., threads, processes, computing devices). The servers604can house threads to perform transformations by employing the architecture, for example. One possible communication between a client602and a server604can be in the form of a data packet adapted to be transmitted between two or more computer processes. The data packet may include a cookie and/or associated contextual information, for example. The system600includes a communication framework606(e.g., a global communication network such as the Internet) that can be employed to facilitate communications between the client(s)602and the server(s)604.

Communications can be facilitated via a wired (including optical fiber) and/or wireless technology. The client(s)602are operatively connected to one or more client data store(s)608that can be employed to store information local to the client(s)602(e.g., cookie(s) and/or associated contextual information). Similarly, the server(s)604are operatively connected to one or more server data store(s)610that can be employed to store information local to the servers604.