31. A method for performing speech-to-text conversion, the method comprising: at an electronic device having a processor and memory: receiving speech input; traversing, based on the speech input, a sequence of states and arcs of a weighted finite state transducer (WFST), wherein: the sequence of states and arcs represents one or more history candidate words and a non-terminal class; and a first probability of the non-terminal class given the one or more history candidate words is determined by traversing the sequence of states and arcs of the WFST; traversing a negating finite state transducer (FST), wherein traversing the negating FST negates the first probability of the non-terminal class given the one or more history candidate words; composing a virtual FST using a neural network language model and based on the sequence of states and arcs of the WFST, wherein one or more virtual states of the virtual FST represent a current candidate word corresponding to the non-terminal class; traversing the one or more virtual states of the virtual FST, wherein a probability of the current candidate word given the one or more history candidate words and the non-terminal class is determined by traversing the one or more virtual states of the virtual FST; determining, based on the probability of the candidate word given the one or more history candidate words and the non-terminal class, text corresponding to the speech input; based on the determined text, performing one or more tasks to obtain a result; and causing the result to be presented in spoken or visual form.
31. A method for performing speech-to-text conversion, the method comprising: at an electronic device having a processor and memory: receiving speech input; traversing, based on the speech input, a sequence of states and arcs of a weighted finite state transducer (WFST), wherein: the sequence of states and arcs represents one or more history candidate words and a non-terminal class; and a first probability of the non-terminal class given the one or more history candidate words is determined by traversing the sequence of states and arcs of the WFST; traversing a negating finite state transducer (FST), wherein traversing the negating FST negates the first probability of the non-terminal class given the one or more history candidate words; composing a virtual FST using a neural network language model and based on the sequence of states and arcs of the WFST, wherein one or more virtual states of the virtual FST represent a current candidate word corresponding to the non-terminal class; traversing the one or more virtual states of the virtual FST, wherein a probability of the current candidate word given the one or more history candidate words and the non-terminal class is determined by traversing the one or more virtual states of the virtual FST; determining, based on the probability of the candidate word given the one or more history candidate words and the non-terminal class, text corresponding to the speech input; based on the determined text, performing one or more tasks to obtain a result; and causing the result to be presented in spoken or visual form. 32. The method of claim 31 , further comprising: determining, using the neural network language model, a second probability of the non-terminal class given the one or more history candidate words, wherein the virtual FST is composed using the second probability of the non-terminal class given the one or more history candidate words.