Multinomial Logistic Regression

In this lesson, we will learn how to adapt the logistic regression formula for situations in which our response variable has more than 2 potential classes. In otherwords, we will see how to use logistic regression for multi-class classification problems.

Assume that \(Y\) is a categorical variable with levels \(A\), \(B\), and \(C\), and that we have \(m\) predictors \(X^{(1)}\), \(X^{(2)}\), …, \(X^{(m)}\). Define the following quantities:

\[p_A = P\left[ Y = A ~|~ X \right]\] \[p_B = P\left[ Y = B ~|~ X \right]\] \[p_C = P\left[ Y = C ~|~ X \right]\]

A multinomial logistic regression model has the following form:

\[\ln\left[\frac{p_A}{p_C} \right] = \beta_{0,1} + \beta_{1,1}\cdot X^{(1)} + \beta_{2,1}\cdot X^{(2)} + ... + \beta_{m,1}\cdot X^{(m)}\]

\[\ln\left[\frac{p_B}{p_C} \right] = \beta_{0,2} + \beta_{1,2}\cdot X^{(1)} + \beta_{2,2}\cdot X^{(2)} + ... + \beta_{m,2}\cdot X^{(m)}\]

Please note the following comments regarding this model:

  1. Since \(p_A + p_B + p_C = 1\), if we know \(\ln\left[{p_A}/{p_C} \right]\) and \(\ln\left[{p_B}/{p_C} \right]\), then we can calculate all three probabilities.

  2. In general, if our reponse variable has \(k\) classes, then our multinomial logistic regression model will need to consist of \(k-1\) equations.

  3. The expression \(p_A/p_C\) is referred to as the relative odds ratio of A with respect to C. We will denote this expression by \(\mathrm{Odds}\left [A:C \right]\).

Example: Diagnosing Diabetes

We will now provide an example of performing multinomial logistic regression in R. In our example, we will build a model that attempts to detect the presence of two types of diabetes based on measurements taken from a blood test. Before we load the dataset, lets load some packages. Note that the nnet package is required for multinomial logistic regression.

Load Packages and Data

library(nnet)
library(ggplot2)
library(gridExtra)
library(caret)

Loading the Dataset

Our dateset contains the following variables. Our response variable will be CC.

  • CC - Categorical variable. 1 = Overt diabetes, 2 = Chemical diabetes, 3 - Non-diabetic
  • RW - Relative weight
  • IR - Insulin response
  • SSPG - Steady state plasma glucose
df <- read.table("data/diabetes.txt", sep="\t", header=TRUE)
summary(df)
       RW               IR             SSPG             CC       
 Min.   :0.7100   Min.   : 10.0   Min.   : 29.0   Min.   :1.000  
 1st Qu.:0.8800   1st Qu.:118.0   1st Qu.:100.0   1st Qu.:2.000  
 Median :0.9800   Median :156.0   Median :159.0   Median :3.000  
 Mean   :0.9773   Mean   :186.1   Mean   :184.2   Mean   :2.297  
 3rd Qu.:1.0800   3rd Qu.:221.0   3rd Qu.:257.0   3rd Qu.:3.000  
 Max.   :1.2000   Max.   :748.0   Max.   :480.0   Max.   :3.000  

We need to convert CC to a factor variable.

df$CC <- factor(df$CC, levels= c("3", "2", "1"))
summary(df)
       RW               IR             SSPG       CC    
 Min.   :0.7100   Min.   : 10.0   Min.   : 29.0   3:76  
 1st Qu.:0.8800   1st Qu.:118.0   1st Qu.:100.0   2:36  
 Median :0.9800   Median :156.0   Median :159.0   1:33  
 Mean   :0.9773   Mean   :186.1   Mean   :184.2         
 3rd Qu.:1.0800   3rd Qu.:221.0   3rd Qu.:257.0         
 Max.   :1.2000   Max.   :748.0   Max.   :480.0         

Let’s calculate the proportion of individuals in the training set that are non-diabetic.

mean(df$CC == '3')
[1] 0.5241379

Exploratory Plots

We will generate boxplots to explore the relationships between CC and the other three variables.

p1 <- ggplot(df, aes(x=CC, y=RW, fill=CC)) + geom_boxplot()  
p2 <- ggplot(df, aes(x=CC, y=IR, fill=CC)) + geom_boxplot()  
p3 <- ggplot(df, aes(x=CC, y=SSPG, fill=CC)) + geom_boxplot()

grid.arrange(p1, p2, p3, ncol=3)

Create Model

We will now create our multinomal logistic regression model using the multinom function from the nnet package.

mod <- multinom(CC ~ RW + IR + SSPG, df)
# weights:  15 (8 variable)
initial  value 159.298782 
iter  10 value 69.027793
iter  20 value 68.418245
iter  30 value 68.414665
final  value 68.414644 
converged
summary(mod)
Call:
multinom(formula = CC ~ RW + IR + SSPG, data = df)

Coefficients:
  (Intercept)        RW           IR       SSPG
2   -7.615261  3.472572  0.003586749 0.01641449
1   -1.845230 -5.867196 -0.013353688 0.04550552

Std. Errors:
  (Intercept)       RW          IR        SSPG
2    2.335615 2.446151 0.002349168 0.004981886
1    3.463507 3.866580 0.005019289 0.009241721

Residual Deviance: 136.8293 
AIC: 152.8293 

Generate Predictions

We can use the predict function to generate predictions. If we would like to for predict to return estimated probabilities, then we need to set type="probs".

nd <- data.frame(
  RW = c(0.87, 0.91, 0.85, 1.15),
  IR = c(120, 620, 150, 150),
  SSPG = c(150, 160, 230, 230)  )

predict(mod, nd, type="probs")
          3         2            1
1 0.7351087 0.1340857 0.1308056224
2 0.4024971 0.5973904 0.0001124671
3 0.1467817 0.1034117 0.7498066056
4 0.2580303 0.5152335 0.2267361597

If we would like to for predict to return estimated probabilities, then we need to set type="class".

predict(mod, nd, type="class")
[1] 3 2 1 2
Levels: 3 2 1

Generating Predictions Using Formulas

As practice, let’s use the formulas provided by our model to confim the calculations that predict has given us. We will do this for a single observation.

x <- c(0.87, 120, 150)
x
[1]   0.87 120.00 150.00

We will extract our coefficients from the model.

cf <- summary(mod)$coefficients
cf
  (Intercept)        RW           IR       SSPG
2   -7.615261  3.472572  0.003586749 0.01641449
1   -1.845230 -5.867196 -0.013353688 0.04550552

We now calculate the log-odds.

logodds23 <- cf[1,1]  + sum(x * cf[1,2:4])
logodds13 <- cf[2,1]  + sum(x * cf[2,2:4])

c(logodds13, logodds23)
[1] -1.726306 -1.701539

Next we find the relative odds ratios.

odds13 <- exp(logodds13)
odds23 <- exp(logodds23)

c(odds13, odds23)
[1] 0.1779405 0.1824026

Finally, we calculate our probabilities.

p1 <- odds13 / (odds13 + odds23 + 1)
p2 <- odds23 / (odds13 + odds23 + 1)
p3 <- 1 - p1 - p2
c(p3, p2, p1)
[1] 0.7351087 0.1340857 0.1308056

Evaluating the Model

We will evaluate our model by calculating its accuracy on the training set. To this this, we must first generate predictions based on the training set.

training_pred <- predict(mod, df, type="class")

set.seed(1)
s <- sample(1:145, 10)

training_pred[s]
 [1] 1 1 3 3 1 3 3 2 3 3
Levels: 3 2 1
df$CC[s]
 [1] 3 1 3 3 3 2 3 2 3 3
Levels: 3 2 1

We will now calculate the model’s training accuracy.

accuracy <- mean(training_pred == df$CC)
accuracy
[1] 0.8275862

Additional Classification Metrics

Assume that we have trained a classification model with a response variable Y. Let C refer to a particular class for Y. We say that:

  • An observation is a True Positive for Class C if our model predicts that the model is of class C, and the observed class is actually C.

  • An observation is a False Positive for Class C if our model predicts that the model is of class C, and the observed class is NOT C.

  • An observation is a True Negative for Class C if our model predicts that the model is NOT of class C, and the observed class is NOT C.

  • An observation is a False Negative for Class C if our model predicts that the model is NOT of class C, and the observed class is actually C.

We can define the following metrics to measure the model’s performance on individual classes.

  • Sensitivity = \(\frac{TP}{TP + FN} = \frac{TP}{\textrm{Number of Actual Cs} }\) (Also called: True Positive Rate, Recall, and Probability of Detection)

  • Specificity = \(\frac{TN}{TN + FP} = \frac{TN}{\textrm{Number of Actual non-Cs} }\) (Also called True Negative Rate)

  • Positive Predictive Value = \(\frac{TP}{TP + FP} = \frac{TP}{\textrm{Number of Predicted Cs} }\) (Also called Precision)

  • Negative Predictive Value = \(\frac{TN}{TN + FN} = \frac{TP}{\textrm{Number of predicted non-Cs} }\)

  • Prevalence = \(\frac{TP + FN}{TP + FP + TN + FN} = \frac{\textrm{Number of Actual Cs} }{\textrm{Size of Total Population} }\)

  • Detection Rate = \(\frac{TP}{TP + FP + TN + FN} = \frac{TP }{\textrm{Size of Total Population} }\)

  • Detection Prevalence = \(\frac{TP + FP}{TP + FP + TN + FN} = \frac{\textrm{Number of Predicted Cs} }{\textrm{Size of Total Population} }\)

  • Balanced Accuracy = \((\textrm{sensitivity + specificity})/2 = \frac{TP + TN}{2(TP + FP + TN + FN)} = \frac{\textrm{Number of Correct Predictions}}{2 \cdot ( \textrm{Size of Total Population})}\)

Confusion Matrix

A confusion matrix is a useful tool for evaluating the performance of a classification model. We can create confusion matrices in R using the confusionMatrix function from the carat package.

confusionMatrix(training_pred, df$CC)
Confusion Matrix and Statistics

          Reference
Prediction  3  2  1
         3 69 12  3
         2  5 24  3
         1  2  0 27

Overall Statistics
                                          
               Accuracy : 0.8276          
                 95% CI : (0.7561, 0.8852)
    No Information Rate : 0.5241          
    P-Value [Acc > NIR] : 1.864e-14       
                                          
                  Kappa : 0.7107          
                                          
 Mcnemar's Test P-Value : 0.1077          

Statistics by Class:

                     Class: 3 Class: 2 Class: 1
Sensitivity            0.9079   0.6667   0.8182
Specificity            0.7826   0.9266   0.9821
Pos Pred Value         0.8214   0.7500   0.9310
Neg Pred Value         0.8852   0.8938   0.9483
Prevalence             0.5241   0.2483   0.2276
Detection Rate         0.4759   0.1655   0.1862
Detection Prevalence   0.5793   0.2207   0.2000
Balanced Accuracy      0.8453   0.7966   0.9002
LS0tDQp0aXRsZTogIkxlc3NvbiA0LjIgLSBNdWx0aW5vbWlhbCBMb2dpc3RpYyBSZWdyZXNzaW9uIg0KYXV0aG9yOiAiUm9iYmllIEJlYW5lIg0Kb3V0cHV0Og0KICBodG1sX25vdGVib29rOg0KICAgIHRoZW1lOiBmbGF0bHkNCiAgICB0b2M6IHllcw0KICAgIHRvY19kZXB0aDogNA0KLS0tDQoNCiMjIyAqKk11bHRpbm9taWFsIExvZ2lzdGljIFJlZ3Jlc3Npb24qKg0KDQpJbiB0aGlzIGxlc3Nvbiwgd2Ugd2lsbCBsZWFybiBob3cgdG8gYWRhcHQgdGhlIGxvZ2lzdGljIHJlZ3Jlc3Npb24gZm9ybXVsYSBmb3Igc2l0dWF0aW9ucyBpbiB3aGljaCBvdXIgcmVzcG9uc2UgdmFyaWFibGUgaGFzIG1vcmUgdGhhbiAyIHBvdGVudGlhbCBjbGFzc2VzLiBJbiBvdGhlcndvcmRzLCB3ZSB3aWxsIHNlZSBob3cgdG8gdXNlIGxvZ2lzdGljIHJlZ3Jlc3Npb24gZm9yIG11bHRpLWNsYXNzIGNsYXNzaWZpY2F0aW9uIHByb2JsZW1zLiANCg0KQXNzdW1lIHRoYXQgJFkkIGlzIGEgY2F0ZWdvcmljYWwgdmFyaWFibGUgd2l0aCBsZXZlbHMgJEEkLCAkQiQsIGFuZCAkQyQsIGFuZCB0aGF0IHdlIGhhdmUgJG0kIHByZWRpY3RvcnMgJFheeygxKX0kLCAkWF57KDIpfSQsIC4uLiwgJFheeyhtKX0kLiBEZWZpbmUgdGhlIGZvbGxvd2luZyBxdWFudGl0aWVzOiANCg0KPGNlbnRlcj4NCiQkcF9BID0gUFxsZWZ0WyBZID0gQSB+fH4gWCBccmlnaHRdJCQNCiQkcF9CID0gUFxsZWZ0WyBZID0gQiB+fH4gWCBccmlnaHRdJCQNCiQkcF9DID0gUFxsZWZ0WyBZID0gQyB+fH4gWCBccmlnaHRdJCQNCjwvY2VudGVyPg0KDQpBICoqbXVsdGlub21pYWwgbG9naXN0aWMgcmVncmVzc2lvbioqIG1vZGVsIGhhcyB0aGUgZm9sbG93aW5nIGZvcm06DQoNCiQkXGxuXGxlZnRbXGZyYWN7cF9BfXtwX0N9IFxyaWdodF0gPSBcYmV0YV97MCwxfSArIFxiZXRhX3sxLDF9XGNkb3QgWF57KDEpfSArIFxiZXRhX3syLDF9XGNkb3QgWF57KDIpfSArIC4uLiArIFxiZXRhX3ttLDF9XGNkb3QgWF57KG0pfSQkDQoNCiQkXGxuXGxlZnRbXGZyYWN7cF9CfXtwX0N9IFxyaWdodF0gPSBcYmV0YV97MCwyfSArIFxiZXRhX3sxLDJ9XGNkb3QgWF57KDEpfSArIFxiZXRhX3syLDJ9XGNkb3QgWF57KDIpfSArIC4uLiArIFxiZXRhX3ttLDJ9XGNkb3QgWF57KG0pfSQkDQoNClBsZWFzZSBub3RlIHRoZSBmb2xsb3dpbmcgY29tbWVudHMgcmVnYXJkaW5nIHRoaXMgbW9kZWw6IA0KDQoxLiBTaW5jZSAkcF9BICsgcF9CICsgcF9DID0gMSQsIGlmIHdlIGtub3cgJFxsblxsZWZ0W3twX0F9L3twX0N9IFxyaWdodF0kIGFuZCAkXGxuXGxlZnRbe3BfQn0ve3BfQ30gXHJpZ2h0XSQsIHRoZW4gd2UgY2FuIGNhbGN1bGF0ZSBhbGwgdGhyZWUgcHJvYmFiaWxpdGllcy4gDQoNCjIuIEluIGdlbmVyYWwsIGlmIG91ciByZXBvbnNlIHZhcmlhYmxlIGhhcyAkayQgY2xhc3NlcywgdGhlbiBvdXIgbXVsdGlub21pYWwgbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbCB3aWxsIG5lZWQgdG8gY29uc2lzdCBvZiAkay0xJCBlcXVhdGlvbnMuIA0KDQozLiBUaGUgZXhwcmVzc2lvbiAkcF9BL3BfQyQgaXMgcmVmZXJyZWQgdG8gYXMgdGhlICoqcmVsYXRpdmUgb2RkcyByYXRpbyoqIG9mIEEgd2l0aCByZXNwZWN0IHRvIEMuIFdlIHdpbGwgZGVub3RlIHRoaXMgZXhwcmVzc2lvbiBieSAkXG1hdGhybXtPZGRzfVxsZWZ0IFtBOkMgXHJpZ2h0XSQuDQoNCg0KIyMjICoqRXhhbXBsZTogRGlhZ25vc2luZyBEaWFiZXRlcyoqDQoNCldlIHdpbGwgbm93IHByb3ZpZGUgYW4gZXhhbXBsZSBvZiBwZXJmb3JtaW5nIG11bHRpbm9taWFsIGxvZ2lzdGljIHJlZ3Jlc3Npb24gaW4gUi4gSW4gb3VyIGV4YW1wbGUsIHdlIHdpbGwgYnVpbGQgYSBtb2RlbCB0aGF0IGF0dGVtcHRzIHRvIGRldGVjdCB0aGUgcHJlc2VuY2Ugb2YgdHdvIHR5cGVzIG9mIGRpYWJldGVzIGJhc2VkIG9uIG1lYXN1cmVtZW50cyB0YWtlbiBmcm9tIGEgYmxvb2QgdGVzdC4gQmVmb3JlIHdlIGxvYWQgdGhlIGRhdGFzZXQsIGxldHMgbG9hZCBzb21lIHBhY2thZ2VzLiBOb3RlIHRoYXQgdGhlIGBubmV0YCBwYWNrYWdlIGlzIHJlcXVpcmVkIGZvciBtdWx0aW5vbWlhbCBsb2dpc3RpYyByZWdyZXNzaW9uLiANCg0KIyMjIyAqKkxvYWQgUGFja2FnZXMgYW5kIERhdGEqKg0KDQpgYGB7ciwgbWVzc2FnZT1GQUxTRX0NCmxpYnJhcnkobm5ldCkNCmxpYnJhcnkoZ2dwbG90MikNCmxpYnJhcnkoZ3JpZEV4dHJhKQ0KbGlicmFyeShjYXJldCkNCmBgYA0KDQojIyMjICoqTG9hZGluZyB0aGUgRGF0YXNldCoqDQoNCk91ciBkYXRlc2V0IGNvbnRhaW5zIHRoZSBmb2xsb3dpbmcgdmFyaWFibGVzLiBPdXIgcmVzcG9uc2UgdmFyaWFibGUgd2lsbCBiZSBgQ0NgLiANCg0KKiBgQ0NgIC0gQ2F0ZWdvcmljYWwgdmFyaWFibGUuIDEgPSBPdmVydCBkaWFiZXRlcywgMiA9IENoZW1pY2FsIGRpYWJldGVzLCAzIC0gTm9uLWRpYWJldGljDQoqIGBSV2AgLSBSZWxhdGl2ZSB3ZWlnaHQNCiogYElSYCAtIEluc3VsaW4gcmVzcG9uc2UNCiogYFNTUEdgIC0gU3RlYWR5IHN0YXRlIHBsYXNtYSBnbHVjb3NlDQoNCmBgYHtyfQ0KZGYgPC0gcmVhZC50YWJsZSgiZGF0YS9kaWFiZXRlcy50eHQiLCBzZXA9Ilx0IiwgaGVhZGVyPVRSVUUpDQpzdW1tYXJ5KGRmKQ0KYGBgDQoNCldlIG5lZWQgdG8gY29udmVydCBgQ0NgIHRvIGEgZmFjdG9yIHZhcmlhYmxlLiANCg0KYGBge3J9DQpkZiRDQyA8LSBmYWN0b3IoZGYkQ0MsIGxldmVscz0gYygiMyIsICIyIiwgIjEiKSkNCnN1bW1hcnkoZGYpDQpgYGANCg0KTGV0J3MgY2FsY3VsYXRlIHRoZSBwcm9wb3J0aW9uIG9mIGluZGl2aWR1YWxzIGluIHRoZSB0cmFpbmluZyBzZXQgdGhhdCBhcmUgbm9uLWRpYWJldGljLiANCg0KYGBge3J9DQptZWFuKGRmJENDID09ICczJykNCmBgYA0KDQoNCg0KIyMjIyAqKkV4cGxvcmF0b3J5IFBsb3RzKioNCg0KV2Ugd2lsbCBnZW5lcmF0ZSBib3hwbG90cyB0byBleHBsb3JlIHRoZSByZWxhdGlvbnNoaXBzIGJldHdlZW4gYENDYCBhbmQgdGhlIG90aGVyIHRocmVlIHZhcmlhYmxlcy4gDQoNCmBgYHtyLCBmaWcud2lkdGg9OCwgZmlnLmhlaWdodD0zfQ0KcDEgPC0gZ2dwbG90KGRmLCBhZXMoeD1DQywgeT1SVywgZmlsbD1DQykpICsgZ2VvbV9ib3hwbG90KCkgIA0KcDIgPC0gZ2dwbG90KGRmLCBhZXMoeD1DQywgeT1JUiwgZmlsbD1DQykpICsgZ2VvbV9ib3hwbG90KCkgIA0KcDMgPC0gZ2dwbG90KGRmLCBhZXMoeD1DQywgeT1TU1BHLCBmaWxsPUNDKSkgKyBnZW9tX2JveHBsb3QoKQ0KDQpncmlkLmFycmFuZ2UocDEsIHAyLCBwMywgbmNvbD0zKQ0KYGBgDQoNCiMjIyMgKipDcmVhdGUgTW9kZWwqKg0KDQpXZSB3aWxsIG5vdyBjcmVhdGUgb3VyIG11bHRpbm9tYWwgbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbCB1c2luZyB0aGUgYG11bHRpbm9tYCBmdW5jdGlvbiBmcm9tIHRoZSBgbm5ldGAgcGFja2FnZS4gDQoNCmBgYHtyfQ0KbW9kIDwtIG11bHRpbm9tKENDIH4gUlcgKyBJUiArIFNTUEcsIGRmKQ0Kc3VtbWFyeShtb2QpDQpgYGANCg0KIyMjIyAqKkdlbmVyYXRlIFByZWRpY3Rpb25zKioNCg0KV2UgY2FuIHVzZSB0aGUgYHByZWRpY3RgIGZ1bmN0aW9uIHRvIGdlbmVyYXRlIHByZWRpY3Rpb25zLiBJZiB3ZSB3b3VsZCBsaWtlIHRvIGZvciBwcmVkaWN0IHRvIHJldHVybiBlc3RpbWF0ZWQgcHJvYmFiaWxpdGllcywgdGhlbiB3ZSBuZWVkIHRvIHNldCBgdHlwZT0icHJvYnMiYC4gDQoNCmBgYHtyfQ0KbmQgPC0gZGF0YS5mcmFtZSgNCiAgUlcgPSBjKDAuODcsIDAuOTEsIDAuODUsIDEuMTUpLA0KICBJUiA9IGMoMTIwLCA2MjAsIDE1MCwgMTUwKSwNCiAgU1NQRyA9IGMoMTUwLCAxNjAsIDIzMCwgMjMwKSAgKQ0KDQpwcmVkaWN0KG1vZCwgbmQsIHR5cGU9InByb2JzIikNCmBgYA0KDQpJZiB3ZSB3b3VsZCBsaWtlIHRvIGZvciBwcmVkaWN0IHRvIHJldHVybiBlc3RpbWF0ZWQgcHJvYmFiaWxpdGllcywgdGhlbiB3ZSBuZWVkIHRvIHNldCBgdHlwZT0iY2xhc3MiYC4gDQoNCmBgYHtyfQ0KcHJlZGljdChtb2QsIG5kLCB0eXBlPSJjbGFzcyIpDQpgYGANCg0KIyMjIyAqKkdlbmVyYXRpbmcgUHJlZGljdGlvbnMgVXNpbmcgRm9ybXVsYXMqKg0KDQpBcyBwcmFjdGljZSwgbGV0J3MgdXNlIHRoZSBmb3JtdWxhcyBwcm92aWRlZCBieSBvdXIgbW9kZWwgdG8gY29uZmltIHRoZSBjYWxjdWxhdGlvbnMgdGhhdCBgcHJlZGljdGAgaGFzIGdpdmVuIHVzLiBXZSB3aWxsIGRvIHRoaXMgZm9yIGEgc2luZ2xlIG9ic2VydmF0aW9uLiANCg0KYGBge3J9DQp4IDwtIGMoMC44NywgMTIwLCAxNTApDQp4DQpgYGANCg0KV2Ugd2lsbCBleHRyYWN0IG91ciBjb2VmZmljaWVudHMgZnJvbSB0aGUgbW9kZWwuIA0KDQpgYGB7cn0NCmNmIDwtIHN1bW1hcnkobW9kKSRjb2VmZmljaWVudHMNCmNmDQpgYGANCg0KV2Ugbm93IGNhbGN1bGF0ZSB0aGUgbG9nLW9kZHMuDQoNCmBgYHtyfQ0KbG9nb2RkczIzIDwtIGNmWzEsMV0gICsgc3VtKHggKiBjZlsxLDI6NF0pDQpsb2dvZGRzMTMgPC0gY2ZbMiwxXSAgKyBzdW0oeCAqIGNmWzIsMjo0XSkNCg0KYyhsb2dvZGRzMTMsIGxvZ29kZHMyMykNCmBgYA0KDQpOZXh0IHdlIGZpbmQgdGhlIHJlbGF0aXZlIG9kZHMgcmF0aW9zLiANCg0KYGBge3J9DQpvZGRzMTMgPC0gZXhwKGxvZ29kZHMxMykNCm9kZHMyMyA8LSBleHAobG9nb2RkczIzKQ0KDQpjKG9kZHMxMywgb2RkczIzKQ0KYGBgDQoNCkZpbmFsbHksIHdlIGNhbGN1bGF0ZSBvdXIgcHJvYmFiaWxpdGllcy4gDQoNCmBgYHtyfQ0KcDEgPC0gb2RkczEzIC8gKG9kZHMxMyArIG9kZHMyMyArIDEpDQpwMiA8LSBvZGRzMjMgLyAob2RkczEzICsgb2RkczIzICsgMSkNCnAzIDwtIDEgLSBwMSAtIHAyDQpjKHAzLCBwMiwgcDEpDQpgYGANCg0KIyMjIyAqKkV2YWx1YXRpbmcgdGhlIE1vZGVsKioNCg0KV2Ugd2lsbCBldmFsdWF0ZSBvdXIgbW9kZWwgYnkgY2FsY3VsYXRpbmcgaXRzIGFjY3VyYWN5IG9uIHRoZSB0cmFpbmluZyBzZXQuIFRvIHRoaXMgdGhpcywgd2UgbXVzdCBmaXJzdCBnZW5lcmF0ZSBwcmVkaWN0aW9ucyBiYXNlZCBvbiB0aGUgdHJhaW5pbmcgc2V0LiANCg0KYGBge3J9DQp0cmFpbmluZ19wcmVkIDwtIHByZWRpY3QobW9kLCBkZiwgdHlwZT0iY2xhc3MiKQ0KDQpzZXQuc2VlZCgxKQ0KcyA8LSBzYW1wbGUoMToxNDUsIDEwKQ0KDQp0cmFpbmluZ19wcmVkW3NdDQpkZiRDQ1tzXQ0KYGBgDQoNCldlIHdpbGwgbm93IGNhbGN1bGF0ZSB0aGUgbW9kZWwncyB0cmFpbmluZyBhY2N1cmFjeS4gDQoNCmBgYHtyfQ0KYWNjdXJhY3kgPC0gbWVhbih0cmFpbmluZ19wcmVkID09IGRmJENDKQ0KYWNjdXJhY3kNCmBgYA0KDQojIyMjICoqQWRkaXRpb25hbCBDbGFzc2lmaWNhdGlvbiBNZXRyaWNzKioNCg0KQXNzdW1lIHRoYXQgd2UgaGF2ZSB0cmFpbmVkIGEgY2xhc3NpZmljYXRpb24gbW9kZWwgd2l0aCBhIHJlc3BvbnNlIHZhcmlhYmxlIGBZYC4gTGV0IGBDYCByZWZlciB0byBhIHBhcnRpY3VsYXIgY2xhc3MgZm9yIGBZYC4gV2Ugc2F5IHRoYXQ6DQoNCiogQW4gb2JzZXJ2YXRpb24gaXMgYSAqKlRydWUgUG9zaXRpdmUqKiBmb3IgQ2xhc3MgYENgIGlmIG91ciBtb2RlbCBwcmVkaWN0cyB0aGF0IHRoZSBtb2RlbCBpcyBvZiBjbGFzcyBgQ2AsIGFuZCB0aGUgb2JzZXJ2ZWQgY2xhc3MgaXMgYWN0dWFsbHkgYENgLiANCg0KKiBBbiBvYnNlcnZhdGlvbiBpcyBhICoqRmFsc2UgUG9zaXRpdmUqKiBmb3IgQ2xhc3MgYENgIGlmIG91ciBtb2RlbCBwcmVkaWN0cyB0aGF0IHRoZSBtb2RlbCBpcyBvZiBjbGFzcyBgQ2AsIGFuZCB0aGUgb2JzZXJ2ZWQgY2xhc3MgaXMgTk9UIGBDYC4gDQoNCiogQW4gb2JzZXJ2YXRpb24gaXMgYSAqKlRydWUgTmVnYXRpdmUqKiBmb3IgQ2xhc3MgYENgIGlmIG91ciBtb2RlbCBwcmVkaWN0cyB0aGF0IHRoZSBtb2RlbCBpcyBOT1Qgb2YgY2xhc3MgYENgLCBhbmQgdGhlIG9ic2VydmVkIGNsYXNzIGlzIE5PVCBgQ2AuIA0KDQoqIEFuIG9ic2VydmF0aW9uIGlzIGEgKipGYWxzZSBOZWdhdGl2ZSoqIGZvciBDbGFzcyBgQ2AgaWYgb3VyIG1vZGVsIHByZWRpY3RzIHRoYXQgdGhlIG1vZGVsIGlzIE5PVCBvZiBjbGFzcyBgQ2AsIGFuZCB0aGUgb2JzZXJ2ZWQgY2xhc3MgaXMgYWN0dWFsbHkgYENgLiANCg0KDQpXZSBjYW4gZGVmaW5lIHRoZSBmb2xsb3dpbmcgbWV0cmljcyB0byBtZWFzdXJlIHRoZSBtb2RlbCdzIHBlcmZvcm1hbmNlIG9uIGluZGl2aWR1YWwgY2xhc3Nlcy4NCg0KKiAqKlNlbnNpdGl2aXR5KiogPSAgJFxmcmFje1RQfXtUUCArIEZOfSA9IFxmcmFje1RQfXtcdGV4dHJte051bWJlciBvZiBBY3R1YWwgQ3N9IH0kIChBbHNvIGNhbGxlZDogVHJ1ZSBQb3NpdGl2ZSBSYXRlLCAqKlJlY2FsbCoqLCBhbmQgUHJvYmFiaWxpdHkgb2YgRGV0ZWN0aW9uKQ0KICANCiogKipTcGVjaWZpY2l0eSoqID0gICRcZnJhY3tUTn17VE4gKyBGUH0gPSBcZnJhY3tUTn17XHRleHRybXtOdW1iZXIgb2YgQWN0dWFsIG5vbi1Dc30gfSQgKEFsc28gY2FsbGVkIFRydWUgTmVnYXRpdmUgUmF0ZSkNCg0KKiAqKlBvc2l0aXZlIFByZWRpY3RpdmUgVmFsdWUqKiA9ICAkXGZyYWN7VFB9e1RQICsgRlB9ID0gXGZyYWN7VFB9e1x0ZXh0cm17TnVtYmVyIG9mIFByZWRpY3RlZCBDc30gfSQgKEFsc28gY2FsbGVkICoqUHJlY2lzaW9uKiopDQoNCiogKipOZWdhdGl2ZSBQcmVkaWN0aXZlIFZhbHVlKiogPSAgJFxmcmFje1ROfXtUTiArIEZOfSA9IFxmcmFje1RQfXtcdGV4dHJte051bWJlciBvZiBwcmVkaWN0ZWQgbm9uLUNzfSB9JA0KDQoqICoqUHJldmFsZW5jZSoqID0gICRcZnJhY3tUUCArIEZOfXtUUCArIEZQICsgVE4gKyBGTn0gPSBcZnJhY3tcdGV4dHJte051bWJlciBvZiBBY3R1YWwgQ3N9IH17XHRleHRybXtTaXplIG9mIFRvdGFsIFBvcHVsYXRpb259IH0kDQoNCiogKipEZXRlY3Rpb24gUmF0ZSoqID0gJFxmcmFje1RQfXtUUCArIEZQICsgVE4gKyBGTn0gPSBcZnJhY3tUUCB9e1x0ZXh0cm17U2l6ZSBvZiBUb3RhbCBQb3B1bGF0aW9ufSB9JA0KDQoqICoqRGV0ZWN0aW9uIFByZXZhbGVuY2UqKiA9ICRcZnJhY3tUUCArIEZQfXtUUCArIEZQICsgVE4gKyBGTn0gPSBcZnJhY3tcdGV4dHJte051bWJlciBvZiBQcmVkaWN0ZWQgQ3N9IH17XHRleHRybXtTaXplIG9mIFRvdGFsIFBvcHVsYXRpb259IH0kIA0KDQoqICoqQmFsYW5jZWQgQWNjdXJhY3kqKiA9ICQoXHRleHRybXtzZW5zaXRpdml0eSArIHNwZWNpZmljaXR5fSkvMiA9IFxmcmFje1RQICsgVE59ezIoVFAgKyBGUCArIFROICsgRk4pfSA9IFxmcmFje1x0ZXh0cm17TnVtYmVyIG9mIENvcnJlY3QgUHJlZGljdGlvbnN9fXsyIFxjZG90ICggXHRleHRybXtTaXplIG9mIFRvdGFsIFBvcHVsYXRpb259KX0kDQoNCiMjIyMgKipDb25mdXNpb24gTWF0cml4KioNCg0KQSBjb25mdXNpb24gbWF0cml4IGlzIGEgdXNlZnVsIHRvb2wgZm9yIGV2YWx1YXRpbmcgdGhlIHBlcmZvcm1hbmNlIG9mIGEgY2xhc3NpZmljYXRpb24gbW9kZWwuIFdlIGNhbiBjcmVhdGUgY29uZnVzaW9uIG1hdHJpY2VzIGluIFIgdXNpbmcgdGhlIGBjb25mdXNpb25NYXRyaXhgIGZ1bmN0aW9uIGZyb20gdGhlIGBjYXJhdGAgcGFja2FnZS4gDQoNCg0KYGBge3J9DQpjb25mdXNpb25NYXRyaXgodHJhaW5pbmdfcHJlZCwgZGYkQ0MpDQpgYGANCg0K