Estimating conditional probabilities on a large corpus of parsed documents

Question

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.

Answer 1

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.

Hope it helps!