Also, unsupervised learning of PCFGs is possible using the EM approach. This is important, since it amounts to grammar discovery.  The only assumption we start with, theoretically, is that there is some maximum number of nonterminal symbols, and each can be expanded into any two nonterminals or into any word (Chomsky normal form). Also we associate some more or less arbitrary initial expansion probabilities with these rules. The probabilities are iteratively revised using expected values of the frequency of occurrence of the possible expansions, based on the current PCFG model, conditioned on the corpus. The analogue of the forward-backward algorithm for computing these expectations is the inside-outside algorithm. Inside probabilities specify the probability that a certain proper segment of a given sentence will be derived from a specified nonterminal symbol. Outside probabilities specify the probability that all but a certain segment of the given sentence will be derived from the start (sentence) symbol, where that “missing” segment remains to be generated from a specified nonterminal symbol. The inside and outside probabilities play roles analogous to the backward and forward probabilities in HMM learning respectively. Conceptually, they require summations over exponentially many possible parse trees for a given sentence, but in fact inside probabilities can be computed efficiently by the CYK algorithm (section 2), and outside probabilities can also be computed efficiently, using a top-down recursive “divide and conquer” algorithm that makes use of previously computed inside probabilities.