brown-clustering

KO | EN

gitlite — search

#machine-learning #react-native #claude-code #sql #api #computer-vision #cpp #cross-platform #android #terminal

brown-clustering

(★ 22)

Brown clustering in Python

File Explorer

ZIP Download

- __init__.py
- core.py
- corpus.py
- helpers.py
- validation.py
- demo.py
- others.py
.gitignore
LICENSE
README.md

# Use via CDN

jsDelivr

jsDelivr serves any public GitHub repository as a CDN with zero setup. Pick a version and a file to get a ready-to-paste link and snippet.

Version

File

Link

Example

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

Brown clustering in Python

The code will be released after Nov 25 for pedagogical reasons.

## Design
This project follows the both the original paper and the fixed window size optimization from another thesis.
* http://aclweb.org/anthology/J/J92/J92-4003.pdf
* http://people.csail.mit.edu/pliang/papers/meng-thesis.pdf

During reading the paper from MIT, I noticed that it contains some mistakes. To be specific, the equation 4.5 is wrong.
At the same time, the original paper dose not use fixed window size optimization (of course). So I derived the correct
equations of merging two cluster or appending a cluster, and use the terms from original paper as much as possible.

## Complexity
Assuming the corpus contains `n` words and `v` unique words. and the `m` is the fixed window size. This implementation
has `O(v*m^2+n)` complexity.

## Data Processing
This implementation only require you to provide corpus, as a list of sentences. Laplace smoothing and 2-gram will be
applied as a part of the algorithm. If you don't need any smoothing you can pass 0 as smoothing parameter `alpha`.

## Evaluation
This project contains multiple implementation, and one does not contain any optimization. This project contains some
unit tests which can make sure that different implementations will give exact same result.

## Dependencies
* `numpy` is used for `ndarray`
* `nltk` is used for `ngram`

I was not hesitated to use them considering that both of them are extremely popular. And if you don't like them, it
would be a very easy task to replace `ndarray` and `ngram` with some simple python code.

## The Same Page
### What is n
`n` is not number of words in corpus. Actually, n is the number of 2-grams. so `n` increased after Laplace smoothing.
### pl(i), pr(j) and p(i), p(j) and p(i, j)
In original paper `pl(i)=SUM(p(i, j) for each j)`. If you have start and end symbols in clusters, it's not difficult to 
find out that `pl(i) = pr(i) = c(i)/n`. So instead of sum them, we can directly keep 1-gram information and use that to
calculate `p(i) = pl(i) = pr(i)`.
### Laplace Smoothing
In order to make above true even after smoothing, we should add double the lambda for 1-gram. Wrong smoothing will end
with wrong clustering result.
### Likelihood, Quality and Average Mutual Information 
`Likelihood(C) = Quality(C) = AverageMutualInformation(C) + some constant`, both papers contains the idea of calculating
 AMI instead of Likelihood or Quality. In this project, `benefit` is the delta value you gain when you merge two clusters.

brown-clustering

Owner Repos

File Explorer

# Use via CDN

Was this content helpful?

Recent Feedback

brown-clustering

Owner Repos

File Explorer

# Use via CDN

Was this content helpful?

Recent Feedback

Download README