Smoothing sparse data
This is more for overview of my own than for teaching or exercise.
Other data analysis, data summarization, learning

Contents
Feature model notes
Bag of words/features (assumption)
The bagofwords model (more broadly bagoffeatures model) use single words/features as an (unordered) set.
The implied assumption are that the features are independent, so order and adjacency is unimportant.
From the ngram perspective, unigram models amount to this.
You can also see it as a voting system.
In text processing
One common example is Naive Bayes spam filtering , because its naivety essentially is this assumption that feature order does not matter.
Though realworld naive bayes spam filtering would take more complex features than single words (and may reintroduce order via ngrams or such), simple example versions may use 1grams.
Other types of classifiers also make this assumption, or make it easy.
In image recognition / image search
The bagoffeatures refers to models that recognize parts of a whole, and used in a number image tasks, such as feature extraction, object/image recognition, image search, (more flexible) nearduplicate detection, and such.
The idea that you can describe an image by the collection of small things we recognize in it, and that combined presence is typically already a strong indicator (particularly when you add some hypothesis testing). Exact placement can be useful, but often easily secondary.
See also:
Naive Bayes
Some background
A certain Reverend Thomas Bayes said a number of things about probability, used mostly in Bayesian inference in statistics, and in Naive Bayes classification.
Classification, in general, is usually based on a trained model:
 deciding on a set of distinct target classes (say, exclusives as 'spam' vs. 'not spam', or rough article subjects (preferably exclusive, or classification itself does not make that much sense, although the valueforclass assignments still may)
 deciding some features to look at, that classification will be based on
 learning the importance of features to each class (often using good examples for each class)
Given something unseen to classify, you extract its features the same way you did for the training set, and see which class compares best. Classification is regularly many fuzzy measures of fit followed by a hard choice of which seems best.
Naive Bayes refers to one of the simpler algorithms that does classification this way.
Its definition has a few notational conventions:
 Each training class is referred to as c in the set of classes C (c_{1}...c_{i})
 We eventually want to judge an unseen document D
 and what we want for D is is the class for which the probability the document fits that class is highest
You can express such Bayesian classification as:
the c for which P(cD) is highest
or, a bit more formally yet,
c = maxarg( P(c_{i}D) )
Bayesian Inversion
The P(cD) above is not obvious to calculate, because it immediately asks us for a best choice for a document, but a thorough answer will probably depend on knowledge the document's features, all classes, and all documents.
So we need to break the problem down before we can give an estimation of the probability P(cD).
The first step is to rewrite using the concept of Bayesian inversion, based on Bayes's rule (which pops up in various other types of probability calculations and estimations).
P(c) * P(Dc) P(cD) =  P(D)
...applied for each class c in C.
P(c) is the base probability of each class, that is, the probability that a document is in class c given no document information.
 This is sometimes assumed to be equal for all classes (in which case it falls away),
 sometimes it is estimated, for example using the assumption that the amount of documents for each class (in the training set) is strong indication of how commonly one of its items is seen.
P(D) is the chance of finding the document, in general.
 This is usually assumed to be independent of the classification problem.
 Because of that, and because it is hard to realistically estimate for an unseen document, it is often assumed to be equal for all documents (so falls away).
P(Dc) is the interesting one. It asks for the probability that a particular document in a particular class.
 This is still abstract, and not yet a directly calculable answer, but it is a smaller problem than we had a few paragraphs up: Unlike the earlier form (P(cD)), it deals not with an immediate choice between alternatives, but only with an calculation/estimation of fit, of 'how well does a specific Document fit in this specific class?' .
 This degree of fit for a document in a class can be done with any method that judges similarity, as long as it is (fairly) stable/consistent between documents, and it can be calculated (roughly) equally well for seen and unseen documents.
Long story somewhat shorter,
Bayesian inversion reduces the classification problem from
 "Choose best class immediately"
to
 "find the class for which our estimation of fit is highest" (by making an estimator that can judge individual documents, and can do so stably / comparably well for all documents)
or from:
maxarg( P(c_{i}D) )
to:
maxarg( P(c_{i}) * P(Dc_{i}) )
or, assuming equal baseclass probabilities, to:
maxarg( P(Dc_{i}) )
Features, Words, and Naivety
So let's talk about an implementation.
If we want to calculate a class's fit based on features, we need to choose those features, and a method to calculate an arbitrary document's fit to those features.
It's nice if each feature is fairly robust in that it does not react in an unnecessarily noisy way, and productive for the classification task at hand.
In Naive Bayes introductions, the choice of features is often words (some introductions talk mainly of words, some talk more broadly about features), and the probabilities are based on the relative occurrence of each chosen word.
Words are a specific implementation choice, but are a nice introduction, in part because it speaks to the imagination in cases such as spam (even though it's limited for this, given that spammers know and try to defeat this model).
If you're programming such a toy example, then the amount of words is often reduced to maybe a thousand.
The actual selection is interesting, in that they ought to be distinguishing within the training set ("the" may be common but not useful), but not be so unusual that they are rare within unseen documents.
There are cleverer ways of choosing words, and you probably want to consider the Zipf distribution of words, but to keep the example simple, let's say we take the most common 1000 in the training set, minus some obvious stopwords.
Naive Bayes is often explained by saying we want a probability based on n features in feature set F: P(cf_{1}..f_{n}), which Bayesinverses and denominatoreliminates to:
P(c) * P(f_{1}..f_{n}c)
...which roughly means "how do features in this new document compare to the one for the class?"
Technically, P(f_{1}..f_{n}c) should expand to a very long formula, as each feature depends on others. That's where the naivety of Naive Bayes comes in: the Naive Bayes assumption is simply that all features are independent of all others. This is rarely true, but is much simpler to work with, is evaluated much faster, and works better than you might expect. (this also effectively makes it a bagofwords model)
It means calculation of the probability of the class based of the features simplifies to a simple multiplication of individual feature values / probabilities. Given there are n features:
P(c) * Π_{i=1 to n} P(f_{i}c)
Note that the wordsasfeatures setup is a #Bag_of_words.2Ffeatures_.28assumption.29 assumption: it plus the naivety means that word order is ignored. This means that potentially indicative phrases, collocations, and such are represented only weakly at best, by their words' independent probabilities being slightly higher. Word ngrams are one possible fix, but will likely run you into a sparseness problem since ngrams are implicitly rarer than single words.
Even just bigrams may be problematic  if you take all possible ones from a large set of documents, you'll find that most documents have a tiny fraction of the overall real use.
Bayesian classification as a procedure...
Naive Bayes training comes down to:
 Deciding which set of features (F) you will use.
 Train, which calculates characteristics for each class, namely:
 P(c) for each class (see above), and more importantly,
 all P(fc): the probability of each feature f in each class c
Later, when classifying an unseen document, you calculate P(c) * P(f_{1}..f_{n}c) for it:
 for each c in C:
 take P(c), times
 the calculated probability of each feature in class c, i.e. each P(fc) based on the document.
 Choose the one with the highest probability, and you've got a classifier.
Choosing your features, and further discussion
Naive Bayes with simple word features works fairly well on various types of text, since it essentially notices differences in vocabulary use, the theory being that that is indicative of the document class. Common words can be useful when they aren't uniformly common between all classes, uncommon ones since they tend to up the probability of just a few classes.
You could simply use all words in all documents and end up with tens of thousands of features, although it would help speed to prune that a little. Which ones to leave is a choice you can be halfway smart about  although note that too much tweaking just means it will work better on the training data, with no guarantees for unseen data.
Also note that when you preprocess the training data, you need to process the unseen documents the same way. When choosing the features, you should consider what this may do to unseen documents.
A feature probability of zero is evil to calculations as it randomly destroys comparability in the both training and classification steps. It can happen fairly easily, such as when a word in the vocabulary doesn't occur in a document. A common solution is to cheat and pretend you did actually see it a little. There are a few different ways; some disturb the relative probabilities less than others.
You can add other features. The main property they should have is that their probabilities compare well, are in the same sort of scale. You could for example add important words a few times, a hackish way of weighing them more. You could for example add select word bigrams or add character ngrams.
You can alter the model further, observing that what you actually do is perclass strengthening or weakening of a probability that it will win. It doesn't even have to be a simple probability, even; you could for example include sentence length, which is not a direct probability, so you would have to e.g. remember the average sentence length in each class, calculate the average for the unseen document and define some metric of similarity. This isn't Naive Bayes anymore, but as a probabilitybased classifier it may work a little better if you choose your alterations well.
Pseudocode
This example pseudocode uses only word features, and some basic addone(verify) smoothing to avoid the zero problem.
Training (word features)
U = feature universe D = document set (text,class pairs) C = set of classes in D foreach c in C: BaseProb(c) = D with class c / D Text = concatenation of documents in current class N = tokens in Text foreach token t in U: P(tc) = ( numoccurence(t in Text) + 1 ) / (numtokens(Text)+U )
Classifying (word features)
foreach c in C: p=P(c) foreach token in Document p = p*P(tokenc)
...then collect each of these probabilities and choose the class with the highest probability.
In reality, the probabilities quickly become very small and you run into the problem that standard 32bit or 64bit floating point numbers cannot accurately contain them.
A common workaround for this is to add the logs of the probabilities (yielding negative numbers) instead of multiplying the probabilities. These values are much less likely to scale out of control, and they are as just as monotonous as the probabilities.
Ngram notes
Ngrams are contiguous sequence of length n.
They are most often seen in computational linguistics.
Applied to sequences of characters it can be useful e.g. in language identification,
but the more common application is to words.
As ngrams models only include dependency information when those relations are expressed through direct proximity, they are poor language models, but useful to things working off probabilities of combinations of words, for example for statistical parsing, collocation analysis, text classification, sliding window methods (e.g. sliding window POS tagger), (statistical) machine translation, and more
 This,is
 is,a
 a,sentence
 sentence,.
Skipgrams
An extension of ngrams that allow allowing a certain amount of arbitrarily positioned omissions from the input.
Skipgrams come from speech analysis, processing phonemes.
In wordlevel analysis their purpose is a little different. You could say that we acknowledge the sparsity problem, and decide to get more out of the data we have (focusing on context) rather than trying to smooth.
Continuous bag of words
Sparse data smoothing
This article is an attempt at a decent overview, introduction, summary, or such.
It may currently just contain a mess of information. If it is likely to keep sucking it will probably be removed later. 
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, fix, 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.
In genera, 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, fix, 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.
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. Assuming 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
Absolute discounting
Heldout estimation
See also
 Chen & Goodman, An Empirical Study of Smoothing Techniques for Language Modeling [1]
 ...its references