Smoothing sparse data
This is more for overview of my own than for teaching or exercise.

Contents
Feature models and smoothing
Sparse data smoothing
...in particular in feature models
The problem
This article/section is a stub — probably a pile of halfsorted notes, is not wellchecked so may have incorrect bits. (Feel free to ignore, or tell me) 
(For relative brevity, the below omits details on training and validation, including terms like heldout, deleted interpolation. While important to execution, it's something you can look up when implementing)
Data sparsity is problematic for various statistical data models, such as simple maximum likelihood models, such as bagofwords, ngram, HMM, and others.
For example, in the set of all possible word trigrams (for language modeling or such), most have not happened in many years of text, and probably never will.
When you base probability (or such) fairly directly on appearance count, you can get a few problems:
 components that occur very few times  relative probabilities make less sense on the rare end of the scale. Consider two items: one that appears once, one that appears three times. How fair is it to say that one is 300% as probable as the other, particularly when comparing two things that are almost never happen?
 most of your trained data is spent on things you really don't care about
 items that were not in your training data / trained model. It's hard to say what you want in such a case;
 If you take a zero count to mean zero probability, you say it will never happen and it should drop out completely, which is a decision too harsh for most goals
 ignoring components of an item can be that are not in training data may work well enough, except you can run into problems where the unseen items consists significantly of unknown components (or where the unknowns would in reality be the more telling ones, if looked at more specifically). You would get more variation in your estimations than you'ld want.
 misspellings and different word order can sometimes make likelihood estimations take an unnecessary nosedive
When we're talking about likelihood, all ways of smoothing over these problems amount to changing the probability mass distribution somehow.
The most basic solutions are to fake the unknowns by pretending they exist but are simply rare. Some may try to be cleverer and boost some more than others.
The probability mass shift is also the reason many of the names have discounting in them: You take some probability from the likelier items to give them to rarer things. Do it too eagerly and you overestimate the rare and underestimate common things.
In some ways, assuming very low probability for unseen items (using only items we have halfway decent information on) has roughly the same effect and flaws as ignoring them, e.g. the nosedive mentioned. Smarter fallbacks of likelihood, even if more approximate, are often preferable.
For ngram models
The larger the n in the ngram, the larger the problem, because the more likely it is that you don't have something in your training data  you could say you need exponentially more data to get a decent estimation for larger n. For many types of data, n≥4 is already problematic. More data is good, but at some point a little fallback and smoothing is easier.
While not always mentioned along with smoothing, very low counts in count data are also a little weird. For example, if some ngram appeard once and another twice, is it really twice as probable? (statistically, using very little information is problematic)
The smarter estimation (than assuming rareness) in such models often fall back onto a n1 (onepieceshorter) items.
Various solutions
This article/section is a stub — probably a pile of halfsorted notes, is not wellchecked so may have incorrect bits. (Feel free to ignore, or tell me) 
Additive smoothing (addone, addδ)
The simplest workaround to the zeromultiplication/zeroprobability problem is addone smoothing, a.k.a. Laplace smoothing, which adds one to every count (generally: to known_vocabulary + unknowns). In other words, pretend you saw everything a little more.
This is only really a fix to the zeromultiplication problem. The way it shifts the probability mass is not very natural  it gives a disproportional boost to rare things, and a lot of probability mass is taken away from unknowns when there a lot of unknowns.
It means underestimating commonly seen things somewhat, and overestimating unknowns (particularly relative to known but rare items). The effect depends on how much you add, and how high the counts are.
(In some methods this doesn't matter much because none of changes the order of the items, just the actual values. In some cases it will completely break things, though; it's a bad idea in ngram models where you mix ngrams of different lengths)
Addδ smoothing, a.k.a. Lidstone smoothing, is a variation that adds a smaller number, something between 0 and 1 and possibly based on the trained data. It mainly just plays with the magnitude of the distribution shift.
If the value is 0.5 this is also known as Expected Likelihood Estimation (ELE) and the JeffreysPerks Law. (verify)
All of these amount to saying that unknowns do exist and are very unlikely (and has less effect on wellknown items), and handle all unknowns identically. If you can estimate more cleverly than that you probably should  and in many underlying models that's not very hard.
Various (parts of) methods of cleverness are somewhat portable between specific models.
Absolute discounting
WittenBell discounting
Intuitively: Unseen ngrams are just ones that are unseen until now. So give it an estimation (probability of seeing a new ngram like this?(verify)).
(Can be considered an instance of JelinekMercer smoothing(verify))
GoodTuring smoothing / GoodTuring Discounting
Redistributes the probability mass. Assumes binomial distribution (though leaves better known things alone).
Its most basic definition is more of an idea, and not robust by itself, but a good base for some more advanced smoothers (involving backoff/interpolation)
See also:
ChurchGale smoothing
GoodTuring plus bucketing.
KneserNey Smoothing
Probably the best available with the smoothing category, in that it uses fewcount items cleverly effectively.
Similar to WittenBell in that it considers context, and can be considered an extension to absolute discounting
Works better with interpolation than with backoff
Modified KneserNey Smoothing (introduced in Chen & Goodman) is an variation that seems to fairly consistently perform somewhat better.
Combined estimators
These aren't really just smoothing anymore, including many the variations of interpolation and backoff  which uses information on shorter items to estimate longer items with unseen parts. Intuitively: that data is necessarily not as sparse, and certainly a better estimate than additive smoothing.
For example, if both "john likes" and "john spork" are unknown, then you can estimate that 'john likes' is more likely by using the unigram 'likes' and 'spork'. If the trigram john likes mnemonics is unseen, you may find you have the bigram bigram john likes.
While not actually what you asked, it's still a much better estimation than additive smoothing gives you, particularly since that would happen a lot for larger n.
Backoff: if there is no information on a given ngram, use (n1)grams within it.
Interpolation: Estimate probability of every ngram is estimated using (n1)grams  which is a recursive definition. It's also a relatively general idea that can be and is tweaked in many ways.
These are sensible ways of using larger ngrams without necessarily causing a huge shift in probability mass.
It's not very hard to alter a backoff algorithm into an interpolating one, and vise versa, though most algorithms are primarily seen as just one.
(Simple) Linear interpolation is a weighed combination of basic maximum likelihood and use of lowerorder ngrams (a recursive definition).
We want to weigh each ngram based on training data  and we want to train that from a data set distinct from that used for ML training.
The common (named) choices:
Even with deleted interpolation, you won't easily get enough data.
JelinekMercer smoothing  interpolating method that tries to get more coverage using further fuzziness, namely bucketing (), based on counts. Which can help even fairly small training sets perform decently.
There are variations that use different bucketing criteria
Apparently not used much anymore; there are simpler options that
Katz smoothing, a.k.a. Katz backoff (ngram based)  Extends GoodTuring redistributing counts but using differentorder models (can be said to be backoff). Often introduced for bigrams and unigrams, but can be taken recursively.
Reverts to use shorter ngram context if count for the ngram is lower than a given threshold.
Things that need to reserve data (JelinekMercer, WittenBell, ) are not used so much anymore, because there are methods that don't require it (e.g. KneserNey), which tend to work better.
>
See also:
Unsorted
Classbased smoothing
Heldout estimation
See also
 Chen & Goodman, An Empirical Study of Smoothing Techniques for Language Modeling [1]
 ...its references