Brown clustering
Brown clustering is a hard
is typically applied to text, grouping words into clusters that are assumed to be semantically related by virtue of their having been embedded in similar contexts.Introduction
In
Technical definition
Brown groups items (i.e.,
As a result, the output can be thought of not only as a binary tree[6] but perhaps more helpfully as a sequence of merges, terminating with one big class of all words. This model has the same general form as a hidden Markov model, reduced to bigram probabilities in Brown's solution to the problem. MI is defined as:
Finding the clustering that maximizes the likelihood of the data is computationally expensive. The approach proposed by Brown et al. is a greedy heuristic.
The work also suggests use of Brown clusterings as a simplistic bigram class-based language model. Given cluster membership indicators ci for the tokens wi in a text, the probability of the word instance wi given preceding word wi-1 is given by:[4]
This has been criticised[citation needed] as being of limited utility, as it only ever predicts the most common word in any class, and so is restricted to |c| word types; this is reflected in the low relative reduction in perplexity found when using this model and Brown.
When applied to Twitter data, for example, Brown clustering assigned a binary tree path to each word in unlabelled tweets during clustering.[7] The prefixes to these paths are used as new features for the tagger.[7]
Variations
Brown clustering has also been explored using trigrams.[8]
Brown clustering as proposed generates a fixed number of output classes. It is important to choose the correct number of classes, which is task-dependent.[9] The cluster memberships of words resulting from Brown clustering can be used as features in a variety of machine-learned natural language processing tasks.[3]
A generalization of the algorithm was published in the AAAI conference in 2016, including a succinct formal definition of the 1992 version and then also the general form.[10] Core to this is the concept that the classes considered for merging do not necessarily represent the final number of classes output, and that altering the number of classes considered for merging directly affects the speed and quality of the final result.
There are no known theoretical guarantees on the greedy heuristic proposed by Brown et al. (as of February 2018). However, the clustering problem can be framed as estimating the parameters of the underlying class-based language model: it is possible to develop a consistent estimator for this model under mild assumptions.[11]
See also
References
- ^ CiteSeerX 10.1.1.94.9004.
- ISBN 978-3-319-47954-5.
- ^ CiteSeerX 10.1.1.714.8528.
- ^ ISBN 9780131873216.
- ISBN 978-3-319-73705-8.
- ISBN 978-3-642-41490-9.
- ^ ISBN 978-3-642-40721-5.
- .
- CiteSeerX 10.1.1.713.5576.
- CiteSeerX 10.1.1.714.8528.
- CiteSeerX 10.1.1.643.6343.