Classification with Tree-augmented Naive Bayes (TAN) and Pgmpy

While working on a classification task recently, I started out with the well-known Naive Bayes classifier but soon realized that I wasn't getting the classification performance I needed.  At the same time, I was keenly aware that many of the feature variables carry a causal relationship between them that the classifier wasn't exploiting.

I needed another classifier with the simplicity and run-time performance of Naive Bayes so I started looking into Tree-augmented Naive Bayes (TAN).  My search for a Python library supporting TAN eventually led me to pgmpy.

Pgmpy is a Python Library for learning (Structure and Parameter) and inference (Statistical and Causal) in Bayesian Networks.

Pgmpy is versatile with capabilities beyond what my task needed.  It also has some structure learning algorithms but not TAN so I thought to contribute one to the library.  In this article, I'll give a tutorial on how to use TAN in pgmpy.

For demonstration purpose, I'll generate sample data from a handcrafted Bayesian Network (BN) model.  With the generated data, I'll train a Naive Bayes classifier and a TAN classifier, and compare their prediction performance.  Our BN graph is illustrated below.  Node C is our class variable while node R, S, T, U and V are the feature variables.  All variables are discrete.

Generate Sample Data

First, import all the packages we will be needing:

import pandas as pd
import numpy as np

 

from pgmpy.models.BayesianModel import BayesianModel
from pgmpy.factors.discrete import TabularCPD
from pgmpy.sampling import BayesianModelSampling
from pgmpy.estimators import TreeSearch, BayesianEstimator

 

from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report
from sklearn.naive_bayes import MultinomialNB

To encode our BN graph, we instantiate BayesianModel with the directed edges of the graph:

# construct naive bayes graph and add interaction between the features
model = BayesianModel([('C', 'R'), ('C', 'S'), ('C', 'T'), ('C', 'U'), ('C', 'V'),

                       ('R', 'S'), ('R', 'T'), ('R', 'U'), ('R', 'V')])

Next, we parameterize the graph by defining the conditional probabilities for each node.  For more information on parameterization, check out the pgmpy tutorials.

# add conditional probability distribution to edges

cpd_c = TabularCPD('C', 2, [[0.5], [0.5]])

cpd_r = TabularCPD('R', 3, [[0.6,0.2],[0.3,0.5],[0.1,0.3]], evidence=['C'],

                            evidence_card=[2])

cpd_s = TabularCPD('S', 3, [[0.1,0.1,0.2,0.2,0.7,0.1],

                            [0.1,0.3,0.1,0.2,0.1,0.2],

                            [0.8,0.6,0.7,0.6,0.2,0.7]],

                            evidence=['C','R'], evidence_card=[2,3])

cpd_t = TabularCPD('T', 2, [[0.7,0.2,0.2,0.5,0.1,0.3],

                            [0.3,0.8,0.8,0.5,0.9,0.7]],

                            evidence=['C','R'], evidence_card=[2,3])

cpd_u = TabularCPD('U', 3, [[0.3,0.8,0.2,0.8,0.4,0.7],

                            [0.4,0.1,0.4,0.1,0.1,0.1],

                            [0.3,0.1,0.4,0.1,0.5,0.2]],

                            evidence=['C','R'], evidence_card=[2,3])

cpd_v = TabularCPD('V', 2, [[0.5,0.6,0.6,0.5,0.5,0.4],

                            [0.5,0.4,0.4,0.5,0.5,0.6]],

                            evidence=['C','R'], evidence_card=[2,3])

model.add_cpds(cpd_c, cpd_r, cpd_s, cpd_t, cpd_u, cpd_v)

With our BN model defined, we can now generate sample data:

# generate sample data from our BN model

inference = BayesianModelSampling(model)

df_data = inference.forward_sample(size=30000, return_type='dataframe')

We'll be using the data to train Naive Bayes and TAN classifier to see which one performs better.  Before that, we split the data into training and test set.

# split data into training and test set

cols_features = df_data.columns.tolist()

cols_features.remove('C')

X = df_data[cols_features].values

y = df_data[['C']].values

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=21, stratify=y)

df_train = pd.DataFrame(np.concatenate((y_train, X_train), axis=1), columns=df_data.columns)

Predicting with Naive Bayes

Now, we are ready to train our Naive Bayes model using the training data and then measure classification performance with the test set.  I'll use the classifier from sklearn but pgmpy also has a Naive Bayes classifier as well shall you choose.

# train naive bayes classifier and predict

model_nb = MultinomialNB().fit(X_train, y_train)

y_pred = model_nb.predict(X_test)

print(classification_report(y_test, y_pred))

In short, Naive Bayes precision and recall are both 72%.

Predicting with TAN

Next up is TAN.  First, let's learn the graph structure from the training data.  To capture the interaction between the feature variables, TAN casts a tree structure over them.  So, you need to pass in the "root_node" parameter.  To be fair, we pretend that we don't know what the real graph looks like, so we pick a random node as the root node:

# learn the TAN graph structure from data

est = TreeSearch(df_train, root_node='U')

dag = est.estimate(estimator_type='tan', class_node='C')

Before we can make predictions, we also need to parameterize the model using the training data.

# construct Bayesian network by parameterizing the graph structure

model = BayesianModel(dag.edges())

model.fit(df_train, estimator=BayesianEstimator, prior_type='K2')

Now we're ready to classify the test data using the TAN model and measure the performance:

# draw inference from BN

X_test_df = pd.DataFrame(X_test, columns=cols_features)

y_pred = model.predict(X_test_df).values

print(classification_report(y_test, y_pred))

Our TAN model precision and recall are both 81% compare to 72% for Naive Bayes.  That's quite a significant improvement!

Predicting with Incomplete Data

As a bonus, now let's try to make predictions on incomplete data.  We will ask pgmpy to predict the class when only feature S, T and U are given.

from pgmpy.inference import VariableElimination

# predict the class given some of the features

infer = VariableElimination(model) 

query = infer.query(variables=['C'], evidence={'S': 0, 'T': 1, 'U': 2})

print(query)

In this case, pgmpy returns the chance of C=1 is 93%.

Instead of predicting the class, let's predict what feature R is likely to be given class C=1 and feature S=1:

# predict the feature given the class and another feature

query = infer.query(variables=['R'], evidence={'C': 1, 'S': 1})

print(query)

In this case, pgmpy returns the chance of R=0 is 27%, R=1 is 32% and R=2 is 41%.

Pretty cool, isn't it?  Like I said in the beginning of the article, pgmpy is versatile and I'm only scratching the surface of what it can do.

Identifying Forename and Surname for Different Ethnicities using Machine Learning

In the previous post, I’ve used logistic regression and tf-idf from Python’s sklearn to predict ethnicity based on a person forename, middle and surname.  In this post, I’ll continue to use the same Wikipedia dataset but this time, the task is to predict if a name is forename or surname.  The motivation is to use such classifier for input form validation and ETL.

To start with, let’s summarize the number of records available:

Ethnicity	Forenames	Surnames	Total
Nordic	1,691	3,230	4,921
EastAsian	2,331	2,784	5,115
Germanic	1,975	3,329	5,304
Africans	2,969	3,170	6,139
Muslim	3,539	4,557	8,096
Japanese	3,864	4,236	8,100
IndianSubContinent	5,133	3,839	8,972
EastEuropean	2,888	6,627	9,515
Hispanic	3,662	6,254	9,916
Jewish	3,676	6,304	9,980
Italian	4,315	8,781	13,096
French	3,802	9,630	13,432
British	6,933	16,062	22,995

We observe that:

1.  Some datasets like Nordic have much fewer records than others
2.  The dataset for French has 2.5 times more surnames than forenames

Our intuition tells us that a general classifier to predict forename and surname for all ethnicities is probably a bad idea as it ignores the subtle differences in name spelling among ethnicities.  The confusion matrix from the previous post on ethnicity prediction speaks to this point.  Therefore, I’ll build a separate forename-surname classifier for each ethnicity.

I will use the same logistic regression approach from the previous post which feature engineers bigrams, trigrams and quadgrams from names.  To address data imbalance in observation #2, I’ll upsample the data of the minority class using the handy Imblearn package.  To address the curse of dimensionality in observation #1, I’ll employ the following approaches to avoid overfitting the training data:

1. Penalize large coefficients in logistic regression
2. Reduce the number of dimensions using SVD

Without further ado, here is the classification performance on a 20% holdout data using upsampling and L2 penalization:

Ethnicity	Precision	Recall	F1
Nordic	79.0%	78.2%	78.4%
EastAsian	63.4%	62.8%	62.8%
Germanic	76.9%	75.9%	76.1%
Africans	59.7%	59.7%	59.7%
Muslim	67.2%	66.4%	66.6%
Japanese	60.4%	60.3%	60.3%
IndianSubContinent	60.6%	60.1%	60.3%
EastEuropean	79.6%	77.2%	77.9%
Hispanic	71.1%	70.6%	70.8%
Jewish	74.8%	74.0%	74.3%
Italian	76.4%	74.0%	74.6%
French	76.4%	75.0%	75.6%
British	74.8%	73.7%	74.2%

The performance is about the same with SVD dimensionality reduction to capture 80 to 90% of variance in the data.  Generally, that reduces the number of features by 80%.

Ethnicity	Precision	Recall	F1
Nordic	78.4%	77.6%	77.8%
EastAsian	64.1%	63.4%	63.5%
Germanic	77.0%	76.0%	76.2%
Africans	60.0%	59.9%	59.9%
Muslim	67.2%	66.4%	66.5%
Japanese	61.3%	61.2%	61.2%
IndianSubContinent	60.6%	60.2%	60.3%
EastEuropean	80.2%	77.9%	78.5%
Hispanic	71.8%	70.9%	71.2%
Jewish	74.8%	73.9%	74.2%
Italian	76.4%	73.7%	74.4%
French	76.8%	75.1%	75.7%

The results are sorted by the size of dataset from smallest to largest.  The result for British is missing due to my old laptop running out of memory during SVD matrix factorization.

Interestingly, focusing on the F1 score, we see that poor performance is not necessarily correlated with small data.  For example, Nordic being the smallest dataset yields rather high F1 score.  The ethnicities with F1 score below 70% are Africans, IndianSubContinent, Japanese, EastAsian and Muslim.

Some of the Muslim names misclassified are:

• navi, rabia, bapsi, khar, ravi, fadela, szold

Some of the EastAsian names misclassified are:

• guanqiu, huang, heshen, dai, eitel, gagnon, ming, kimble, liang, samata

Besides insufficient data being the possible cause of poor classification performance, it's conceivable that some of these misclassified names can be tricky even to humans to decide if it's a forename or surname. For example, "Davis" can be either a forename or surname.

In the meantime, a classifier with 60% accuracy can still be useful.  For example, for input form validation where forename and surname are entered and the goal is to validate if they are entered into the right field, we can use the classifier to predict whether a swap has taken place accidentally by the user.

A swap occurs if the classifier predicts that the input forename is a surname and the input surname is a forename.  For a classifier with 60% accuracy, the chance of erroneously predicting a swap and alerting the user is only 100 x (0.4 x 0.4) = 16%.

Predicting Ethnicity based on Person Name using Machine Learning

Recently, I stumbled upon a Python app called ethnicolr that uses deep learning to predict ethnicity based on a person forename and surname.  The app uses LSTM on sequences of bigrams generated from surname and forename as features.  Three different models were trained using data collected from US Census, Florida voter registration and Wikipedia.  Of the three, the wikipedia dataset appears the most interesting because of the broader categories of ethnicity available than others.  The categories are East Asian, Japanese, Indian SubContinent, Africans, Muslim, British, East European, Jewish, French, Germanic, Hispanic, Italian, and Nordic.  The reported precision and recall of the LSTM model using the wikipedia dataset are both approximately 73%.

Intrigued by the approach, I was curious how the performance would fare by using more traditional classifiers such as logistic regression which tends to take less time to train than LSTM.  The full Jupyter notebook is available here.

In summary, logistic regression produces slightly better precision and recall than LTSM and also took much less time to train (a few minutes versus about an hour on a 5 year old computer).  At the time of writing, average precision is 75% and recall is 76%.  The full confusion matrix is:

Perhaps as expected, some races such as Africans and Jewish are harder to predict than others due to more mixing and displacements over generations.

The major differences between the LSTM and regression model is that the former uses only bigrams while the latter uses bigrams, trigrams and quadgrams as features.  The regression model also weighs the features by applying tf-idf.  In addition, the regression model includes the middle name whenever it’s available though the performance improvement from adding middle name was observed to be negligible.

As a quick demo, the regression model was run on the following world leaders to predict their ethnicity:

Name	Ethnicity
Abe Shinzo	Japanese
Conte Giuseppe	Italian
Johnson Boris	British
Modi Narendra	Indan SubContinent
Netanyahu Benjamin	Jewish
Obama Barrack	Africans
Putin Vladimir	East European
Xi Jinping	East Asian

It's worthy to note that a few other approaches were attempted to improve precision and recall such as applying XGBoost and dataset balancing techniques.  At best, their performance was on par with logistic regression.  It is, of course, conceivable that more tuning might have been required for those methods to excel.