Prelim notes: NLP

Language modeling

N-grams are sparse. How do we solve the sparsity problem?

• Laplace smoothing. Add one to each count, then renormalize. Equivalently, the adjusted count $c^* = (c + 1) \cdot N / (N+V)$. This is bad.

• Good-Turing discounting. For every type that occurs $N$ times, allocate mass to it from the types that occur $N+1$ times. In particular, $c^* = (c+1) (N_{c+1} / N_c)$ where $N_c$ is the number of types that occur $c$ times. Observe that the sum of all adjusted counts is $\sum_{i=1}^N N_i \cdot (i+1)(N_{i+1}/N_i) = \sum_{i=2}^N i N_i$ from which we see that a total count of $N_1$ is missing. We divide this among all events observed zero times.

• Linear interpolation. Just take a linear-combination of high- and low-order models, with weights set by search on a held out corpus.

• Kneser-Ney. Intuition is that when we back off to a lower-order model, it might be useful to use something other than the raw count. Example: “Francisco” is very common, but only after “San”. So maybe better to do approximate the probability of a word as the number of different contexts it has appeared in. So general form of K-N is

  $$p(w_i|w_{i-1}) = \frac{C(w_{i-1}w_i) - d}{C(w_{i-1})} + \beta(w_i) \frac{N(\bullet w_i)}{N(\bullet \bullet)}$$

  In fact we have higher-order analogs, where we back down to type models of different granularities.

Speech

General setup: a noisy channel model. Given a sequence of observations $O$, we want to find the most likely sequence of words that produced them; we write $p(W|O) \propto p(O|W) p(W)$. $P(W)$ is just a language model. What does the state space look like for $P(O|W)$? Easiest thing is just an HMM, but the beginning, middle, and end of each phone look different—instead we split each phone state into three substates, and learn a model of these. (Note that this forces us to assume that phone lengths are geometrically distributed—we’ll come back to this.)

What representation of sound do we actually generate? Theoretically possible to make the waveform directly, but get much better performance by doing a bunch of preprocessing, and then generating the processed representation. In particular, we turn each frame of the recording into an MFCC vector, as follows:

1. Preemphasis: apply a high-pass filter to increase the prominence of high frequencies (this prevents high formants from being masked by lower ones).

2. Windowing: divide signal into a bunch of overlapping frames. For these use a Hamming window, which passes the signal through a sinusoidal envelope.

3. DFT

4. Mel filter bank: human auditory perception isn’t uniform, but is instead linear below $\sim$1000 Hz and logarithmic above–transform this way. In practice, this is implemented with a bunch of band-pass-ish filters with triangular responses.

5. Cepstral transform: find the spectrum of the log of the spectrum. Intuitively, this separates out effects of the fundamental (whose overtones show up periodically across the spectrum) from other filter effects. Keep around the first 12 components.

6. Feature computation: from the cepstral transform, use the 12 components, estimates of their first and second derivatives, and corresponding features ($x, \dot{x}, \ddot{x}$) on the total energy in the frame.

The resulting vector is real-valued, so we still need a way of generating it from the discrete hidden state space. Na"ively, just discretize (with clustering alg.\ of your choice), then generate from a categorical; more cleverly, represent each emission function as a mixture of Gaussians. This just increases the hidden state space. In practice, these Gaussians are usually assumed to have diagonal covariance.

How to do this faster?

• Run $k$-means rather than EM when estimating model parameters

• Do coarse-to-fine (where refinement is e.g.\ over LM context length)

• A*

How to do this more accurately?

• Further state refinement—Markovization of state space.

• Discriminative training

Machine translation

Alignment

First thing we need for learning a statistical MT system from parallel data is alignment between source and target words. A couple of ways to do this:

• Model 1. Generative process is

  1. Draw an alignment between source and target uniformly at random.

  2. Draw a target word conditioned on its aligned source word.

  Only parameters here are $p(f|e)$. While EM training, there’s a latent variable associated with each target word indicating what source word it’s aligned to. Global maximum! And MAP estimation is easy as each target word just chooses its most likely source.

• Model 3. Generative process is

  1. For each source word, draw a number of children (“fertility model”) and duplicate accordingly.

  2. Insert NULLs.

  3. Translate lexically.

  4. Distort.

  Main new contribution is a fertility model. Model params are fertility distributions, NULL insertion probability, lexical parameters, distortion parameters. Hidden variables are selected fertilities, alignments per word.

  Inference requires sampling.

• HMM model. Generative process is

  1. Draw a target length conditioned on source length.

  2. Draw a (target-to-source) alignment variable conditioned on the previous alignment variable.

  3. Draw a target word conditioned on the aligned source word.

  In the second step, the distribution is parameterized only by the difference between the two indices, rather than the absolute indices themselves.

  This model captures the intuition that nearby words tend to align near each other. We can do inference with forward–backward, so EM training is easy.

The actual translations we get out of this model tend to be terrible—more useful to let the model memorize large many-to-many alignments. Various hacky ways of extracting these things once we have MAP alignments for each sentence.

Decoding

Now we have a phrase table, with weights on each rule (don’t worry about where these weights came from). How do we translate? Looks like a search problem: incrementally consume some block of words (anywhere) in the source sentence, place them next in the target sentence, and repeat until entire source is used up. Decoder state space looks like (source bitstring, target LM context). Just beam search.

General dynamic programming

• Hypergraph inside–outside.

  For each inside step,

  $$\alpha_i = \sum_{e : \textrm{head}(e) = i} \psi(e) \prod_{j \in e} \alpha_j$$

  For each outside step,

  $$\beta_i = \sum_{e : i \in e} \psi(e) \beta_{\textrm{head}(e)} \prod_{j \neq i \in e} \alpha_j$$

— 11 August 2014

← text, home