SYSTEMS AND METHODS FOR ENFORCING CONSTRAINTS TO PREDICTIONS
There is disclosed a method and system for determining states satisfying one or more constraints. The method comprises inputting, to a machine learning algorithm (MLA), input data. The MLA outputs a probability distribution. The probability distribution comprises a predicted probability for each of a plurality of pairs, where each pair comprises a class in a set of classes and a corresponding state of the MLA. The states of the probability distribution are added to a set of states to be searched. States that are end states or that fail to satisfy at least one of the constraints are removed from the set of states to be searched. One or more of the set of states to be searched are input to the MLA. The search is repeated with new states output by the MLA. End states output by the MLA may be output as output states.
1 . A method of determining states satisfying one or more constraints, the method comprising:
inputting, to a machine learning algorithm (MLA), input data and a first state of the MLA, wherein the MLA was trained to predict a probability distribution that the input data corresponds to pairs, each pair comprising a class in a set of classes and a next state of the MLA;
outputting, by the MLA and based on the input data and the first state, the probability distribution, wherein the probability distribution comprises a predicted probability for each pair of a plurality of pairs, each pair comprising a class in the set of classes and a corresponding state of the MLA;
adding the first state and each state of the probability distribution to a set of states to be searched;
applying a search to the set of states to be searched, wherein applying the search comprises:
removing, from the set of states to be searched, any states that are end states,
removing, from the set of states to be searched, any states that fail every constraint of the one of the one or more constraints,
selecting, to input to the MLA, one or more states of the set of states to be searched,
inputting, to the MLA, each of the selected one or more states, thereby generating one or more additional probability distributions,
adding, to the set of states to be searched, one or more states of the one or more additional probability distributions thereby generating an updated set of states to be searched, and
repeating the search with the updated set of states to be searched; and
outputting one or more output states selected by the search, wherein each of the one or more output states contains an end state and wherein each of the one or more output states comprise a respective sequence satisfying at least one of the one or more constraints.
2 . The method of claim 1 , further comprising, after selecting a state to input to the MLA, removing, from the set of states to be searched, the selected state.
3 . The method of claim 1 , wherein the probability distribution is a partial probability distribution having a total probability mass that is less than one.
4 . The method of claim 3 , wherein the partial probability distribution comprises a table or a graphical model.
5 . The method of claim 1 , wherein a number of states to be searched before repeating the search is reduced to less than or equal to a pre-determined beam size.
6 . The method of claim 5 , wherein the updated set of states to be searched comprises highest-ranked states of the set of states to be searched.
7 . The method of claim 1 , further comprising:
determining that a first state key associated with a first state of the set of one or more states to be searched is equivalent to a second state key associated with a second state of the set of one or more states to be searched; and
combining the first state and the second state.
8 . The method of claim 7 , wherein combining the first state and the second state comprises:
determining a predicted probability of the first state;
determining a predicted probability of the second state;
summing the predicted probability of the first state and the predicted probability of the second state;
assigning the summed predicted probability to a combined state corresponding to the first state and the second state; and
adding the combined state to the set of one or more states to be searched.
9 . The method of claim 1 , further comprising:
determining that a first state of the set of one or more states to be searched is equivalent to a second state that was previously searched; and
combining the first state and the second state.
10 . The method of claim 1 , wherein the input data comprises a set of inputs, a sequence of inputs, an image, or a sound.
11 . The method of claim 1 , wherein a constraint of the one or more constraints comprises a finite-state automata.
12 . The method of claim 1 , wherein a constraint of the one or more constraints comprises a transducer.
13 . The method of claim 12 , further comprising:
receiving, by the transducer, a first class in the set of classes; and
outputting, by the transducer, a second class in the set of classes that is different from the first class.
14 . The method of claim 13 , wherein the second class comprises an empty class.
15 . The method of claim 12 , wherein the transducer is a weighted finite-state transducer,
and further comprising outputting, by the transducer, a score.
16 . A system comprising:
at least one processor, and
memory storing a plurality of executable instructions which, when executed by the at least one processor, cause the system to:
input, to a machine learning algorithm (MLA), input data and a first state of the MLA, wherein the MLA was trained to predict a probability distribution that the input data corresponds to pairs, each pair comprising a class in a set of classes and a next state of the MLA;
output, by the MLA and based on the input data and the first state, the probability distribution, wherein the probability distribution comprises a predicted probability for each pair of a plurality of pairs, each pair comprising a class in the set of classes and a corresponding state of the MLA;
add the first state and each state of the probability distribution to a set of states to be searched;
apply a search to the set of states to be searched, wherein applying the search comprises:
removing, from the set of states to be searched, any states that are end states,
removing, from the set of states to be searched, any states that fail every constraint of the one of the one or more constraints,
selecting, to input to the MLA, one or more states of the set of states to be searched,
inputting, to the MLA, each of the selected one or more states, thereby generating one or more additional probability distributions,
adding, to the set of states to be searched, one or more states of the one or more additional probability distributions thereby generating an updated set of states to be searched, and
repeating the search with the updated set of states to be searched; and
output one or more output states selected by the search, wherein each of the one or more output states contains an end state and wherein each of the one or more output states comprise a respective sequence satisfying at least one of the one or more constraints.
17 . The system of claim 16 , wherein the instructions further cause the system to:
determine that a first state key associated with a first state of the set of one or more states to be searched is equivalent to a second state key associated with a second state of the set of one or more states to be searched; and
combine the first state and the second state.
18 . The system of claim 17 , wherein the instructions further cause the system to:
determine a predicted probability of the first state;
determine a predicted probability of the second state;
sum the predicted probability of the first state and the predicted probability of the second state;
assign the summed predicted probability to a combined state corresponding to the first state and the second state; and
add the combined state to the set of one or more states to be searched.