Saturday, August 1, 2020

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'],
cpd_s = TabularCPD('S', 3, [[0.1,0.1,0.2,0.2,0.7,0.1],
                            evidence=['C','R'], evidence_card=[2,3])
cpd_t = TabularCPD('T', 2, [[0.7,0.2,0.2,0.5,0.1,0.3],
                            evidence=['C','R'], evidence_card=[2,3])
cpd_u = TabularCPD('U', 3, [[0.3,0.8,0.2,0.8,0.4,0.7],
                            evidence=['C','R'], evidence_card=[2,3])
cpd_v = TabularCPD('V', 2, [[0.5,0.6,0.6,0.5,0.5,0.4],
                            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()

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()), 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})

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})

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.

Saturday, July 4, 2020

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:


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%.


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%.

Sunday, June 28, 2020

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 ShinzoJapanese
Conte GiuseppeItalian 
Johnson BorisBritish
Modi Narendra Indan SubContinent 
 Netanyahu Benjamin Jewish
Obama BarrackAfricans
Putin VladimirEast European
Xi JinpingEast 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.