# Estimating conditional probabilities on a large corpus of parsed documents

## Scope

I have a large corpus of (parsed) documents where each has multiple terms and few associated codes. My objective is to estimate the conditional probability $$P(code | terms)$$.

## First attempt

After some limited review of the literature, I prototyped a solution using a Bayesian network. First, I turned the corpus into a one-hot-encoded matrix $$M$$. Next, using pgmpy, I estimated the DAG representing the network:

from pgmpy.estimators import BicScore, HillClimbSearch
from pgmpy.inference import VariableElimination
from pgmpy.models import BayesianModel

model_estimation = HillClimbSearch(data, scoring_method=BicScore(data))
estimated_model = model_estimation.estimate()


Next, I built a model, fitted it and instantiated a variable elimination object:

bayes_model = BayesianModel(estimated_model.edges)
bayes_model.fit(ohe_corpus)
inference = VariableElimination(bayes_model)


At this point I could run something like:

inference.query(["code_1", "code_2"], evidence=["term_i", "term_j", "term_k"])


which returns a table with the conditional probabilities. This last step was very fast.

## Synthetic data

As the next phase, I created a synthetic data set and used the pipeline described above to experiment with it. It comes as no surprise that the bottle neck of this approach is the model/DAG estimation phase. Here are some timings I took:

duration_sec  n_codes  n_terms  related_terms_per_doc   noise_terms_per_doc  nodes_count
141.957661        3       15                      6                     2           40
178.062985        3       16                      6                     2           43
904.152860        3       18                      6                     2           48
1031.557014        3       20                      6                     2           52
1040.274353        3       17                      6                     2           48
1135.333175        3       19                      6                     2           52

• n_codes is the number of codes my corpus has
• n_terms is the number of terms my corpus has
• related_terms_per_doc is the number of terms related to the code of the document
• noise_terms_per_doc is the number of terms not related to the code of the document
• nodes_count the number of nodes in the estimated DAG.

In each test I had the same number of documents: 500. For the sake of brevity, I skipped some details how I constructed the synthetic data.

This growth in time might turn to be an issue for my application.

## My questions

1. How feasible this approach is assuming I'm having about 50k documents using thousands of terms and hundreds of codes?
2. I understand that the complexity of the DAG estimation exponentially depends on the number of unique terms and codes in the corpus. Is that correct? I might be OK with an estimation step that takes 12-24 hours but I need to know about this in advance.
3. Assuming that the answers to the above questions are that it is rather impractical, what would be a workaround? One idea I had is to run a PCA on the correlation matrix of the one-hot-encoded terms data and build a DAG on the reduced matrix. However, this proved to be a problem because the switch to floats exploded the number of unique terms. I tried to round the loadings yielded by the PCA, but so far this seems to be a dead-end. What workarounds can I consider to tackle this problem?

I tend to believe that this is a well studied problem and I would be thankful for pointers and ideas.

If you have $$n$$ documents $$D=d_i, i \in 1:n$$. According to Bayesian rule, following equation can be derived for a specific term $$T=t$$ and code $$C=c$$: \begin{align}P(c|t) &= \sum_{i=1}^n P(c,d_i|t) \\&= \sum_{i=1}^n \frac{P(c,t|d_i)P(d_i)}{P(t)} \\&= \frac{ \sum_{i=1}^nP(c,t|d_i)P(d_i)}{P(t)} \\&= \frac{ \sum_{i=1}^nP(c,t|d_i)P(d_i)}{\sum_{i=1}^n P(t|d_i)P(d_i)} \\& \text{put } P(d_i)=1/n\text{ inside,}\\&= \frac{ \sum_{i=1}^nP(c,t|d_i)}{\sum_{i=1}^n P(t|d_i)} \\\end{align} Where $$P(c,t|d_i)$$ is the probability of $$C=c,T=t$$ (among all the $$(C,T)$$ combinations) in document $$d_i$$, and $$P(t|d_i)$$ is the the probability of $$T=t$$ (among all the possible values of $$T$$) in document $$d_i$$. You can calculate $$P(c,t|d_i),i \in 1:n$$ and $$P(t|d_i),i\in 1:n$$ directly from your corpus, put them into above equation will get you the answer.