Motivations

Trong post trước chúng ta đã so sánh và khảo sát vai trò của tiêu chuẩn AUC như là một điều kiện cần của việc lựa chọn mô hình phù hợp gắn liền với mục tiêu của các tổ chức hoạt động vì lợi nhuận như Ngân Hàng. Trong post này chúng ta sẽ tìm hiểu tác động của việc sử dụng các tham số mà tối ưu AUC bằng Bayesian Optimization lên mức lợi nhuận tối đa (maximum profit) giữa Random Forest không được tinh chỉnh và Random Forest được tinh chỉnh.

Findings

Random Forest với tham số tối ưu tìm được bằng Bayesian Optimization có AUC cao hơn AUC của Random Forest mặc định chỉ 2.618% nhưng maximum profit tương ứng thì chênh lệch nhau đến 474.0189% (Figure 2):

Python Codes

Dưới đây là Python codes của các kết quả quan trọng này:

# ===============================
#  Prepare data for training
# ==============================
# Turn off warnings:
import warnings

warnings.simplefilter(action="ignore", category=FutureWarning)

# Load data:
import pandas as pd

df_bank = pd.read_csv("C:/Users/ADMIN/Desktop/DataMining/dmba/GermanCredit.csv")

# Relabel for RESPONSE (1 = default, 0 = nondefault):
df_bank["RESPONSE"] = df_bank["RESPONSE"].map({1: 0, 0: 1})

# Drop OBS# feature:
my_df_binary = df_bank.drop(["OBS#"], axis=1)

# Define input features and target output:
Y = my_df_binary["RESPONSE"]
X = my_df_binary.drop("RESPONSE", axis=1)

# Prepare data:
from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(X, Y, test_size=0.2, random_state=29)

# Train Random Forest and calculate probability of default:
from sklearn.ensemble import RandomForestClassifier

ran = RandomForestClassifier(random_state=29)
ran.fit(X_train, y_train)
pd_ran = ran.predict_proba(X_test)[:, 1]

# ==========================================================================
# Search optimal parameters for Random Forest using Bayesian Optimization
# ==========================================================================

# Define objective function:
from sklearn.model_selection import cross_val_score
from sklearn.model_selection import RepeatedStratifiedKFold

cv = RepeatedStratifiedKFold(n_splits=4, n_repeats=3, random_state=29)

def objective_function(params):
    clf = RandomForestClassifier(**params, n_jobs=-1, random_state=29)
    score = cross_val_score(clf, X_train, y_train, cv=cv, scoring="roc_auc", n_jobs=-1)
    loss_value = -1 * score.mean()
    return loss_value

# Define space of parameters:

from hyperopt.pyll import scope
from hyperopt import hp

param_hyperopt_rf = {
    'max_depth': scope.int(hp.quniform('max_depth', 1, 50, 1)),
    'n_estimators': scope.int(hp.quniform('n_estimators', 50, 1000, 100)),
    'min_samples_split': scope.int(hp.quniform('min_samples_split', 2, 30, 1)),
    'min_samples_leaf': scope.int(hp.quniform('min_samples_leaf', 2, 30, 1))
}

# Search optimal parameters for Random Forest by Bayesian Optimization:
from hyperopt import fmin, tpe, Trials
import numpy as np

tpe = tpe.suggest
tpe_trials = Trials()

rf_bayesian_TPE = fmin(fn=objective_function,
                       space=param_hyperopt_rf,
                       algo=tpe,
                       max_evals=50,
                       trials=tpe_trials,
                       rstate=np.random.RandomState(29))

# Show AUC by interation:
hyperopt_scores = [-1 * trial['result']['loss'] for trial in tpe_trials.trials]
hyperopt_scores = np.maximum.accumulate(hyperopt_scores)

import matplotlib.pyplot as plt

plt.style.use('fivethirtyeight')

plt.figure(figsize=(8, 6))
plt.plot(hyperopt_scores)
plt.xlabel("Interation")
plt.ylabel("AUC")
plt.title("Figure 1: AUC by Interation (TPE Bayesian Optimization)", fontsize=15)
plt.yticks(fontsize=12)
plt.xticks(fontsize=12)
plt.legend(fontsize=8)
plt.show()

# Extract optimal values and parameter names:
best_param_tpe = [x for x in rf_bayesian_TPE.values()]
param_names = [x for x in rf_bayesian_TPE.keys()]

# Reset Random Forest with optimal parameters:
param_hyperopt_rf['max_depth'] = int(best_param_tpe[0])
param_hyperopt_rf['min_samples_leaf'] = int(best_param_tpe[1])
param_hyperopt_rf['min_samples_split'] = int(best_param_tpe[2])
param_hyperopt_rf['n_estimators'] = int(best_param_tpe[3])

# Retrain Random Forest with optimal parameters:
bestRF = RandomForestClassifier(**param_hyperopt_rf, random_state=29, n_jobs=-1)
bestRF.fit(X_train, y_train)

# Recalculate probability of default:
pd_best = bestRF.predict_proba(X_test)[:, 1]

# ================================================================
#  Compare profit between default and turned Random Forest
# ================================================================

# Function calculates profit with given cutoff when interest rate of 10%:
def profit_by_cutoff(cutoff, pred_prob):
    rate = 0.10
    pred_bg = (pred_prob >= cutoff).astype(int)
    gg = X_test[(y_test == 0) & (pred_bg == 0)]
    bg = X_test[(y_test == 1) & (pred_bg == 0)]
    profit = np.sum(rate * gg["AMOUNT"]) - np.sum(bg["AMOUNT"])
    return profit

def profit(cutoff):
    pro_none = profit_by_cutoff(cutoff=cutoff, pred_prob=pd_ran)
    pro_turned = profit_by_cutoff(cutoff=cutoff, pred_prob=pd_best)
    df_pro = pd.DataFrame({"Profit_None": [pro_none],
                           "Profit_Turned": [pro_turned],

                           "Cutoff": [cutoff]})

    return df_pro


# Profit for the two models by a range of cutoff:
df_profit = pd.DataFrame()

for j in np.arange(0.01, 0.3, 0.005):
    df_j = profit(j)
    df_profit = df_profit.append(df_j)

# Compare profit by line graph:

plt.plot("Cutoff", "Profit_None", data=df_profit, label="None", lw=2)
plt.plot("Cutoff", "Profit_Turned", data=df_profit, label="Turned", lw=2)
plt.title("Figure 2: Profit by Default and Turned Random Forest", fontsize=13)
plt.xlabel("Cutoff")
plt.ylabel("Profit")
plt.yticks(fontsize=12)
plt.xticks(fontsize=12)
plt.legend(fontsize=8)
plt.show()

# AUC (2.618% increased):
from sklearn.metrics import roc_auc_score

print(roc_auc_score(y_test, pd_ran))
print(roc_auc_score(y_test, pd_best))

# Gap in maximum profit by two models:
max_pro_turned = np.max(df_profit['Profit_Turned'])
max_pro_default = np.max(df_profit['Profit_None'])
gap = max_pro_turned / max_pro_default
print(gap)

Remove noises by RFE


# ================================
#  Expansion: Remove noises
# ================================

# Function return average ROC:
from sklearn.feature_selection import RFE
from sklearn.pipeline import Pipeline

def average_roc(n_features):
    rfe = RFE(estimator=RandomForestClassifier(random_state=29), n_features_to_select=n_features)
    model = RandomForestClassifier(random_state=29)
    pipeline = Pipeline(steps=[('s', rfe), ('m', model)])
    n_scores = cross_val_score(pipeline, X_test, y_test, scoring='roc_auc', cv=cv, n_jobs=-1)
    return np.mean(n_scores)

my_range = np.arange(5, 40, 1)
avg_auc = []

for j in my_range:
    avg_auc.append(average_roc(j))

df_fet = pd.DataFrame({"n_features": my_range, "auc": avg_auc})
df_max = df_fet[df_fet['auc'] == np.max(df_fet['auc'])]

plt.plot("n_features", "auc", data=df_fet)
plt.scatter('n_features', 'auc', data=df_max, s=80, label=None, color='r')
plt.show()

rfe = RFE(estimator=RandomForestClassifier(random_state=29), n_features_to_select=14)
model = RandomForestClassifier(random_state=29)
pipeline = Pipeline(steps=[('s', rfe), ('m', model)])
pipeline.fit(X_train, y_train)
pd_fet = pipeline.predict_proba(X_test)[:, 1]

print(roc_auc_score(y_test, pd_fet))

cutoff_range = np.arange(0.01, 0.3, 0.005)
profit_fet = []

for j in cutoff_range:
    profit3 = profit_by_cutoff(cutoff=j, pred_prob=pd_fet)
    profit_fet.append(profit3)

df3 = pd.DataFrame({"Cutoff": cutoff_range, "Profit_Fet": profit_fet})

plt.plot("Cutoff", "Profit_None", data=df_profit, label="None", lw=2)
plt.plot("Cutoff", "Profit_Turned", data=df_profit, label="Turned", lw=2)
plt.plot("Cutoff", "Profit_Fet", data=df3, label="Fet", lw=2)
plt.title("Figure 3: Profit", fontsize=13)
plt.xlabel("Cutoff")
plt.ylabel("Profit")
plt.yticks(fontsize=12)
plt.xticks(fontsize=12)
plt.legend(fontsize=8)
plt.show()

Profit Comparision


# ================================================
#                   Prove
# ================================================
# Function calculates average profit with given cutoff
# for CatBoostClassifier and RandomForestClassifier:

from catboost import CatBoostClassifier

def average_pro(cutoff):
    n_times = 10
    randomSeeds = np.arange(1, n_times + 1, 1)

    pro_cat = []
    pro_ran = []

    for j in randomSeeds:
        # For CatBoostClassifier:
        cat = CatBoostClassifier(random_state=j, verbose=False)
        cat.fit(X_train, y_train)
        pd_cat = cat.predict_proba(X_test)[:, 1]
        profit_cat = profit_by_cutoff(cutoff=cutoff, pred_prob=pd_cat)
        pro_cat.append(profit_cat)
        # For RandomForestClassifier:
        ran = RandomForestClassifier(random_state=j)
        ran.fit(X_train, y_train)
        pd_ran = ran.predict_proba(X_test)[:, 1]
        profit_ran = profit_by_cutoff(cutoff=cutoff, pred_prob=pd_ran)
        pro_ran.append(profit_ran)

    df_result = pd.DataFrame({"AvgProCat": [np.mean(pro_cat)],
                              "AvgProRan": [np.mean(pro_ran)],
                              "Cutoff": [cutoff]})

    return df_result

# Avg profit by range of cutoff:
df_avgPro = pd.DataFrame()

for i in cutoff_range:
    df_i = average_pro(cutoff=i)
    df_avgPro = df_avgPro.append(df_i)

# Result:

plt.plot("Cutoff", "AvgProCat", data=df_avgPro, label="CatBoost", lw=2)
plt.plot("Cutoff", "AvgProRan", data=df_avgPro, label="RandomForest", lw=2)
plt.title("Figure 4: Profit", fontsize=13)
plt.xlabel("Cutoff")
plt.ylabel("Profit")
plt.yticks(fontsize=12)
plt.xticks(fontsize=12)
plt.legend(fontsize=8)
plt.show()
LS0tDQp0aXRsZTogJ0VmZmVjdCBvZiBBVUMgb24gbWF4aW11bSBwcm9maXQgKFB5dGhvbiknDQphdXRob3I6ICdBdXRob3I6IE5ndXllbiBDaGkgRHVuZycNCnN1YnRpdGxlOiAiUHl0aG9uIE1hY2hpbmUgTGVhcm5pbmcgU2VyaWVzIg0Kb3V0cHV0Og0KICBodG1sX2RvY3VtZW50OiANCiAgICBjb2RlX2Rvd25sb2FkOiB0cnVlDQogICAgIyBjb2RlX2ZvbGRpbmc6IGhpZGUNCiAgICBoaWdobGlnaHQ6IHplbmJ1cm4NCiAgICAjIG51bWJlcl9zZWN0aW9uczogeWVzDQogICAgdGhlbWU6ICJmbGF0bHkiDQogICAgdG9jOiBUUlVFDQogICAgdG9jX2Zsb2F0OiBUUlVFDQotLS0NCg0KYGBge3Igc2V0dXAsaW5jbHVkZT1GQUxTRX0NCmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gVFJVRSwgd2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0UsIGNhY2hlID0gVFJVRSxldmFsID0gRkFMU0UpDQoNCmBgYA0KDQoNCiMgTW90aXZhdGlvbnMNCg0KVHJvbmcgW3Bvc3QgdHLGsOG7m2NdKGh0dHBzOi8vcnB1YnMuY29tL2NoaWR1bmdrdC82NjQ5NDMpIGNow7puZyB0YSDEkcOjIHNvIHPDoW5oIHbDoCBraOG6o28gc8OhdCB2YWkgdHLDsiBj4bunYSB0acOqdSBjaHXhuqluIEFVQyBuaMawIGzDoCBt4buZdCDEkWnhu4F1IGtp4buHbiBj4bqnbiBj4bunYSB2aeG7h2MgbOG7sWEgY2jhu41uIG3DtCBow6xuaCBwaMO5IGjhu6NwIGfhuq9uIGxp4buBbiB24bubaSBt4bulYyB0acOqdSBj4bunYSBjw6FjIHThu5UgY2jhu6ljIGhv4bqhdCDEkeG7mW5nIHbDrCBs4bujaSBuaHXhuq1uIG5oxrAgTmfDom4gSMOgbmcuIFRyb25nIHBvc3QgbsOgeSBjaMO6bmcgdGEgc+G6vSB0w6xtIGhp4buDdSB0w6FjIMSR4buZbmcgY+G7p2Egdmnhu4djIHPhu60gZOG7pW5nIGPDoWMgdGhhbSBz4buRIG3DoCB04buRaSDGsHUgQVVDIGLhurFuZyBCYXllc2lhbiBPcHRpbWl6YXRpb24gbMOqbiBt4bupYyBs4bujaSBuaHXhuq1uIHThu5FpIMSRYSAobWF4aW11bSBwcm9maXQpIGdp4buvYSBSYW5kb20gRm9yZXN0IGtow7RuZyDEkcaw4bujYyB0aW5oIGNo4buJbmggdsOgIFJhbmRvbSBGb3Jlc3QgxJHGsOG7o2MgdGluaCBjaOG7iW5oLiANCg0KIyBGaW5kaW5ncw0KDQpSYW5kb20gRm9yZXN0IHbhu5tpIHRoYW0gc+G7kSB04buRaSDGsHUgdMOsbSDEkcaw4bujYyBi4bqxbmcgQmF5ZXNpYW4gT3B0aW1pemF0aW9uIGPDsyBBVUMgY2FvIGjGoW4gQVVDIGPhu6dhIFJhbmRvbSBGb3Jlc3QgbeG6t2MgxJHhu4tuaCBjaOG7iSAyLjYxOCUgbmjGsG5nIG1heGltdW0gcHJvZml0IHTGsMahbmcg4bupbmcgdGjDrCBjaMOqbmggbOG7h2NoIG5oYXUgxJHhur9uIDQ3NC4wMTg5JSAoRmlndXJlIDIpOg0KIVtdKEM6L1VzZXJzL0FkbWluL0RvY3VtZW50cy9wcm9maXQuanBnKQ0KDQoNCiMgUHl0aG9uIENvZGVzDQoNCkTGsOG7m2kgxJHDonkgbMOgIFB5dGhvbiBjb2RlcyBj4bunYSBjw6FjIGvhur90IHF14bqjIHF1YW4gdHLhu41uZyBuw6B5OiANCg0KDQpgYGB7cHl0aG9uLCBweXRob24ucmV0aWN1bGF0ZSA9IEZBTFNFfQ0KIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09DQojICBQcmVwYXJlIGRhdGEgZm9yIHRyYWluaW5nDQojID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQ0KIyBUdXJuIG9mZiB3YXJuaW5nczoNCmltcG9ydCB3YXJuaW5ncw0KDQp3YXJuaW5ncy5zaW1wbGVmaWx0ZXIoYWN0aW9uPSJpZ25vcmUiLCBjYXRlZ29yeT1GdXR1cmVXYXJuaW5nKQ0KDQojIExvYWQgZGF0YToNCmltcG9ydCBwYW5kYXMgYXMgcGQNCg0KZGZfYmFuayA9IHBkLnJlYWRfY3N2KCJDOi9Vc2Vycy9BRE1JTi9EZXNrdG9wL0RhdGFNaW5pbmcvZG1iYS9HZXJtYW5DcmVkaXQuY3N2IikNCg0KIyBSZWxhYmVsIGZvciBSRVNQT05TRSAoMSA9IGRlZmF1bHQsIDAgPSBub25kZWZhdWx0KToNCmRmX2JhbmtbIlJFU1BPTlNFIl0gPSBkZl9iYW5rWyJSRVNQT05TRSJdLm1hcCh7MTogMCwgMDogMX0pDQoNCiMgRHJvcCBPQlMjIGZlYXR1cmU6DQpteV9kZl9iaW5hcnkgPSBkZl9iYW5rLmRyb3AoWyJPQlMjIl0sIGF4aXM9MSkNCg0KIyBEZWZpbmUgaW5wdXQgZmVhdHVyZXMgYW5kIHRhcmdldCBvdXRwdXQ6DQpZID0gbXlfZGZfYmluYXJ5WyJSRVNQT05TRSJdDQpYID0gbXlfZGZfYmluYXJ5LmRyb3AoIlJFU1BPTlNFIiwgYXhpcz0xKQ0KDQojIFByZXBhcmUgZGF0YToNCmZyb20gc2tsZWFybi5tb2RlbF9zZWxlY3Rpb24gaW1wb3J0IHRyYWluX3Rlc3Rfc3BsaXQNCg0KWF90cmFpbiwgWF90ZXN0LCB5X3RyYWluLCB5X3Rlc3QgPSB0cmFpbl90ZXN0X3NwbGl0KFgsIFksIHRlc3Rfc2l6ZT0wLjIsIHJhbmRvbV9zdGF0ZT0yOSkNCg0KIyBUcmFpbiBSYW5kb20gRm9yZXN0IGFuZCBjYWxjdWxhdGUgcHJvYmFiaWxpdHkgb2YgZGVmYXVsdDoNCmZyb20gc2tsZWFybi5lbnNlbWJsZSBpbXBvcnQgUmFuZG9tRm9yZXN0Q2xhc3NpZmllcg0KDQpyYW4gPSBSYW5kb21Gb3Jlc3RDbGFzc2lmaWVyKHJhbmRvbV9zdGF0ZT0yOSkNCnJhbi5maXQoWF90cmFpbiwgeV90cmFpbikNCnBkX3JhbiA9IHJhbi5wcmVkaWN0X3Byb2JhKFhfdGVzdClbOiwgMV0NCg0KIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQ0KIyBTZWFyY2ggb3B0aW1hbCBwYXJhbWV0ZXJzIGZvciBSYW5kb20gRm9yZXN0IHVzaW5nIEJheWVzaWFuIE9wdGltaXphdGlvbg0KIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQ0KDQojIERlZmluZSBvYmplY3RpdmUgZnVuY3Rpb246DQpmcm9tIHNrbGVhcm4ubW9kZWxfc2VsZWN0aW9uIGltcG9ydCBjcm9zc192YWxfc2NvcmUNCmZyb20gc2tsZWFybi5tb2RlbF9zZWxlY3Rpb24gaW1wb3J0IFJlcGVhdGVkU3RyYXRpZmllZEtGb2xkDQoNCmN2ID0gUmVwZWF0ZWRTdHJhdGlmaWVkS0ZvbGQobl9zcGxpdHM9NCwgbl9yZXBlYXRzPTMsIHJhbmRvbV9zdGF0ZT0yOSkNCg0KZGVmIG9iamVjdGl2ZV9mdW5jdGlvbihwYXJhbXMpOg0KICAgIGNsZiA9IFJhbmRvbUZvcmVzdENsYXNzaWZpZXIoKipwYXJhbXMsIG5fam9icz0tMSwgcmFuZG9tX3N0YXRlPTI5KQ0KICAgIHNjb3JlID0gY3Jvc3NfdmFsX3Njb3JlKGNsZiwgWF90cmFpbiwgeV90cmFpbiwgY3Y9Y3YsIHNjb3Jpbmc9InJvY19hdWMiLCBuX2pvYnM9LTEpDQogICAgbG9zc192YWx1ZSA9IC0xICogc2NvcmUubWVhbigpDQogICAgcmV0dXJuIGxvc3NfdmFsdWUNCg0KIyBEZWZpbmUgc3BhY2Ugb2YgcGFyYW1ldGVyczoNCg0KZnJvbSBoeXBlcm9wdC5weWxsIGltcG9ydCBzY29wZQ0KZnJvbSBoeXBlcm9wdCBpbXBvcnQgaHANCg0KcGFyYW1faHlwZXJvcHRfcmYgPSB7DQogICAgJ21heF9kZXB0aCc6IHNjb3BlLmludChocC5xdW5pZm9ybSgnbWF4X2RlcHRoJywgMSwgNTAsIDEpKSwNCiAgICAnbl9lc3RpbWF0b3JzJzogc2NvcGUuaW50KGhwLnF1bmlmb3JtKCduX2VzdGltYXRvcnMnLCA1MCwgMTAwMCwgMTAwKSksDQogICAgJ21pbl9zYW1wbGVzX3NwbGl0Jzogc2NvcGUuaW50KGhwLnF1bmlmb3JtKCdtaW5fc2FtcGxlc19zcGxpdCcsIDIsIDMwLCAxKSksDQogICAgJ21pbl9zYW1wbGVzX2xlYWYnOiBzY29wZS5pbnQoaHAucXVuaWZvcm0oJ21pbl9zYW1wbGVzX2xlYWYnLCAyLCAzMCwgMSkpDQp9DQoNCiMgU2VhcmNoIG9wdGltYWwgcGFyYW1ldGVycyBmb3IgUmFuZG9tIEZvcmVzdCBieSBCYXllc2lhbiBPcHRpbWl6YXRpb246DQpmcm9tIGh5cGVyb3B0IGltcG9ydCBmbWluLCB0cGUsIFRyaWFscw0KaW1wb3J0IG51bXB5IGFzIG5wDQoNCnRwZSA9IHRwZS5zdWdnZXN0DQp0cGVfdHJpYWxzID0gVHJpYWxzKCkNCg0KcmZfYmF5ZXNpYW5fVFBFID0gZm1pbihmbj1vYmplY3RpdmVfZnVuY3Rpb24sDQogICAgICAgICAgICAgICAgICAgICAgIHNwYWNlPXBhcmFtX2h5cGVyb3B0X3JmLA0KICAgICAgICAgICAgICAgICAgICAgICBhbGdvPXRwZSwNCiAgICAgICAgICAgICAgICAgICAgICAgbWF4X2V2YWxzPTUwLA0KICAgICAgICAgICAgICAgICAgICAgICB0cmlhbHM9dHBlX3RyaWFscywNCiAgICAgICAgICAgICAgICAgICAgICAgcnN0YXRlPW5wLnJhbmRvbS5SYW5kb21TdGF0ZSgyOSkpDQoNCiMgU2hvdyBBVUMgYnkgaW50ZXJhdGlvbjoNCmh5cGVyb3B0X3Njb3JlcyA9IFstMSAqIHRyaWFsWydyZXN1bHQnXVsnbG9zcyddIGZvciB0cmlhbCBpbiB0cGVfdHJpYWxzLnRyaWFsc10NCmh5cGVyb3B0X3Njb3JlcyA9IG5wLm1heGltdW0uYWNjdW11bGF0ZShoeXBlcm9wdF9zY29yZXMpDQoNCmltcG9ydCBtYXRwbG90bGliLnB5cGxvdCBhcyBwbHQNCg0KcGx0LnN0eWxlLnVzZSgnZml2ZXRoaXJ0eWVpZ2h0JykNCg0KcGx0LmZpZ3VyZShmaWdzaXplPSg4LCA2KSkNCnBsdC5wbG90KGh5cGVyb3B0X3Njb3JlcykNCnBsdC54bGFiZWwoIkludGVyYXRpb24iKQ0KcGx0LnlsYWJlbCgiQVVDIikNCnBsdC50aXRsZSgiRmlndXJlIDE6IEFVQyBieSBJbnRlcmF0aW9uIChUUEUgQmF5ZXNpYW4gT3B0aW1pemF0aW9uKSIsIGZvbnRzaXplPTE1KQ0KcGx0Lnl0aWNrcyhmb250c2l6ZT0xMikNCnBsdC54dGlja3MoZm9udHNpemU9MTIpDQpwbHQubGVnZW5kKGZvbnRzaXplPTgpDQpwbHQuc2hvdygpDQoNCiMgRXh0cmFjdCBvcHRpbWFsIHZhbHVlcyBhbmQgcGFyYW1ldGVyIG5hbWVzOg0KYmVzdF9wYXJhbV90cGUgPSBbeCBmb3IgeCBpbiByZl9iYXllc2lhbl9UUEUudmFsdWVzKCldDQpwYXJhbV9uYW1lcyA9IFt4IGZvciB4IGluIHJmX2JheWVzaWFuX1RQRS5rZXlzKCldDQoNCiMgUmVzZXQgUmFuZG9tIEZvcmVzdCB3aXRoIG9wdGltYWwgcGFyYW1ldGVyczoNCnBhcmFtX2h5cGVyb3B0X3JmWydtYXhfZGVwdGgnXSA9IGludChiZXN0X3BhcmFtX3RwZVswXSkNCnBhcmFtX2h5cGVyb3B0X3JmWydtaW5fc2FtcGxlc19sZWFmJ10gPSBpbnQoYmVzdF9wYXJhbV90cGVbMV0pDQpwYXJhbV9oeXBlcm9wdF9yZlsnbWluX3NhbXBsZXNfc3BsaXQnXSA9IGludChiZXN0X3BhcmFtX3RwZVsyXSkNCnBhcmFtX2h5cGVyb3B0X3JmWyduX2VzdGltYXRvcnMnXSA9IGludChiZXN0X3BhcmFtX3RwZVszXSkNCg0KIyBSZXRyYWluIFJhbmRvbSBGb3Jlc3Qgd2l0aCBvcHRpbWFsIHBhcmFtZXRlcnM6DQpiZXN0UkYgPSBSYW5kb21Gb3Jlc3RDbGFzc2lmaWVyKCoqcGFyYW1faHlwZXJvcHRfcmYsIHJhbmRvbV9zdGF0ZT0yOSwgbl9qb2JzPS0xKQ0KYmVzdFJGLmZpdChYX3RyYWluLCB5X3RyYWluKQ0KDQojIFJlY2FsY3VsYXRlIHByb2JhYmlsaXR5IG9mIGRlZmF1bHQ6DQpwZF9iZXN0ID0gYmVzdFJGLnByZWRpY3RfcHJvYmEoWF90ZXN0KVs6LCAxXQ0KDQojID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0NCiMgIENvbXBhcmUgcHJvZml0IGJldHdlZW4gZGVmYXVsdCBhbmQgdHVybmVkIFJhbmRvbSBGb3Jlc3QNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQ0KDQojIEZ1bmN0aW9uIGNhbGN1bGF0ZXMgcHJvZml0IHdpdGggZ2l2ZW4gY3V0b2ZmIHdoZW4gaW50ZXJlc3QgcmF0ZSBvZiAxMCU6DQpkZWYgcHJvZml0X2J5X2N1dG9mZihjdXRvZmYsIHByZWRfcHJvYik6DQogICAgcmF0ZSA9IDAuMTANCiAgICBwcmVkX2JnID0gKHByZWRfcHJvYiA+PSBjdXRvZmYpLmFzdHlwZShpbnQpDQogICAgZ2cgPSBYX3Rlc3RbKHlfdGVzdCA9PSAwKSAmIChwcmVkX2JnID09IDApXQ0KICAgIGJnID0gWF90ZXN0Wyh5X3Rlc3QgPT0gMSkgJiAocHJlZF9iZyA9PSAwKV0NCiAgICBwcm9maXQgPSBucC5zdW0ocmF0ZSAqIGdnWyJBTU9VTlQiXSkgLSBucC5zdW0oYmdbIkFNT1VOVCJdKQ0KICAgIHJldHVybiBwcm9maXQNCg0KZGVmIHByb2ZpdChjdXRvZmYpOg0KICAgIHByb19ub25lID0gcHJvZml0X2J5X2N1dG9mZihjdXRvZmY9Y3V0b2ZmLCBwcmVkX3Byb2I9cGRfcmFuKQ0KICAgIHByb190dXJuZWQgPSBwcm9maXRfYnlfY3V0b2ZmKGN1dG9mZj1jdXRvZmYsIHByZWRfcHJvYj1wZF9iZXN0KQ0KICAgIGRmX3BybyA9IHBkLkRhdGFGcmFtZSh7IlByb2ZpdF9Ob25lIjogW3Byb19ub25lXSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICJQcm9maXRfVHVybmVkIjogW3Byb190dXJuZWRdLA0KDQogICAgICAgICAgICAgICAgICAgICAgICAgICAiQ3V0b2ZmIjogW2N1dG9mZl19KQ0KDQogICAgcmV0dXJuIGRmX3Bybw0KDQoNCiMgUHJvZml0IGZvciB0aGUgdHdvIG1vZGVscyBieSBhIHJhbmdlIG9mIGN1dG9mZjoNCmRmX3Byb2ZpdCA9IHBkLkRhdGFGcmFtZSgpDQoNCmZvciBqIGluIG5wLmFyYW5nZSgwLjAxLCAwLjMsIDAuMDA1KToNCiAgICBkZl9qID0gcHJvZml0KGopDQogICAgZGZfcHJvZml0ID0gZGZfcHJvZml0LmFwcGVuZChkZl9qKQ0KDQojIENvbXBhcmUgcHJvZml0IGJ5IGxpbmUgZ3JhcGg6DQoNCnBsdC5wbG90KCJDdXRvZmYiLCAiUHJvZml0X05vbmUiLCBkYXRhPWRmX3Byb2ZpdCwgbGFiZWw9Ik5vbmUiLCBsdz0yKQ0KcGx0LnBsb3QoIkN1dG9mZiIsICJQcm9maXRfVHVybmVkIiwgZGF0YT1kZl9wcm9maXQsIGxhYmVsPSJUdXJuZWQiLCBsdz0yKQ0KcGx0LnRpdGxlKCJGaWd1cmUgMjogUHJvZml0IGJ5IERlZmF1bHQgYW5kIFR1cm5lZCBSYW5kb20gRm9yZXN0IiwgZm9udHNpemU9MTMpDQpwbHQueGxhYmVsKCJDdXRvZmYiKQ0KcGx0LnlsYWJlbCgiUHJvZml0IikNCnBsdC55dGlja3MoZm9udHNpemU9MTIpDQpwbHQueHRpY2tzKGZvbnRzaXplPTEyKQ0KcGx0LmxlZ2VuZChmb250c2l6ZT04KQ0KcGx0LnNob3coKQ0KDQojIEFVQyAoMi42MTglIGluY3JlYXNlZCk6DQpmcm9tIHNrbGVhcm4ubWV0cmljcyBpbXBvcnQgcm9jX2F1Y19zY29yZQ0KDQpwcmludChyb2NfYXVjX3Njb3JlKHlfdGVzdCwgcGRfcmFuKSkNCnByaW50KHJvY19hdWNfc2NvcmUoeV90ZXN0LCBwZF9iZXN0KSkNCg0KIyBHYXAgaW4gbWF4aW11bSBwcm9maXQgYnkgdHdvIG1vZGVsczoNCm1heF9wcm9fdHVybmVkID0gbnAubWF4KGRmX3Byb2ZpdFsnUHJvZml0X1R1cm5lZCddKQ0KbWF4X3Byb19kZWZhdWx0ID0gbnAubWF4KGRmX3Byb2ZpdFsnUHJvZml0X05vbmUnXSkNCmdhcCA9IG1heF9wcm9fdHVybmVkIC8gbWF4X3Byb19kZWZhdWx0DQpwcmludChnYXApDQoNCmBgYA0KDQojIFJlbW92ZSBub2lzZXMgYnkgUkZFDQoNCg0KYGBge3B5dGhvbiwgcHl0aG9uLnJldGljdWxhdGUgPSBGQUxTRX0NCg0KIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQ0KIyAgRXhwYW5zaW9uOiBSZW1vdmUgbm9pc2VzDQojID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09DQoNCiMgRnVuY3Rpb24gcmV0dXJuIGF2ZXJhZ2UgUk9DOg0KZnJvbSBza2xlYXJuLmZlYXR1cmVfc2VsZWN0aW9uIGltcG9ydCBSRkUNCmZyb20gc2tsZWFybi5waXBlbGluZSBpbXBvcnQgUGlwZWxpbmUNCg0KZGVmIGF2ZXJhZ2Vfcm9jKG5fZmVhdHVyZXMpOg0KICAgIHJmZSA9IFJGRShlc3RpbWF0b3I9UmFuZG9tRm9yZXN0Q2xhc3NpZmllcihyYW5kb21fc3RhdGU9MjkpLCBuX2ZlYXR1cmVzX3RvX3NlbGVjdD1uX2ZlYXR1cmVzKQ0KICAgIG1vZGVsID0gUmFuZG9tRm9yZXN0Q2xhc3NpZmllcihyYW5kb21fc3RhdGU9MjkpDQogICAgcGlwZWxpbmUgPSBQaXBlbGluZShzdGVwcz1bKCdzJywgcmZlKSwgKCdtJywgbW9kZWwpXSkNCiAgICBuX3Njb3JlcyA9IGNyb3NzX3ZhbF9zY29yZShwaXBlbGluZSwgWF90ZXN0LCB5X3Rlc3QsIHNjb3Jpbmc9J3JvY19hdWMnLCBjdj1jdiwgbl9qb2JzPS0xKQ0KICAgIHJldHVybiBucC5tZWFuKG5fc2NvcmVzKQ0KDQpteV9yYW5nZSA9IG5wLmFyYW5nZSg1LCA0MCwgMSkNCmF2Z19hdWMgPSBbXQ0KDQpmb3IgaiBpbiBteV9yYW5nZToNCiAgICBhdmdfYXVjLmFwcGVuZChhdmVyYWdlX3JvYyhqKSkNCg0KZGZfZmV0ID0gcGQuRGF0YUZyYW1lKHsibl9mZWF0dXJlcyI6IG15X3JhbmdlLCAiYXVjIjogYXZnX2F1Y30pDQpkZl9tYXggPSBkZl9mZXRbZGZfZmV0WydhdWMnXSA9PSBucC5tYXgoZGZfZmV0WydhdWMnXSldDQoNCnBsdC5wbG90KCJuX2ZlYXR1cmVzIiwgImF1YyIsIGRhdGE9ZGZfZmV0KQ0KcGx0LnNjYXR0ZXIoJ25fZmVhdHVyZXMnLCAnYXVjJywgZGF0YT1kZl9tYXgsIHM9ODAsIGxhYmVsPU5vbmUsIGNvbG9yPSdyJykNCnBsdC5zaG93KCkNCg0KcmZlID0gUkZFKGVzdGltYXRvcj1SYW5kb21Gb3Jlc3RDbGFzc2lmaWVyKHJhbmRvbV9zdGF0ZT0yOSksIG5fZmVhdHVyZXNfdG9fc2VsZWN0PTE0KQ0KbW9kZWwgPSBSYW5kb21Gb3Jlc3RDbGFzc2lmaWVyKHJhbmRvbV9zdGF0ZT0yOSkNCnBpcGVsaW5lID0gUGlwZWxpbmUoc3RlcHM9WygncycsIHJmZSksICgnbScsIG1vZGVsKV0pDQpwaXBlbGluZS5maXQoWF90cmFpbiwgeV90cmFpbikNCnBkX2ZldCA9IHBpcGVsaW5lLnByZWRpY3RfcHJvYmEoWF90ZXN0KVs6LCAxXQ0KDQpwcmludChyb2NfYXVjX3Njb3JlKHlfdGVzdCwgcGRfZmV0KSkNCg0KY3V0b2ZmX3JhbmdlID0gbnAuYXJhbmdlKDAuMDEsIDAuMywgMC4wMDUpDQpwcm9maXRfZmV0ID0gW10NCg0KZm9yIGogaW4gY3V0b2ZmX3JhbmdlOg0KICAgIHByb2ZpdDMgPSBwcm9maXRfYnlfY3V0b2ZmKGN1dG9mZj1qLCBwcmVkX3Byb2I9cGRfZmV0KQ0KICAgIHByb2ZpdF9mZXQuYXBwZW5kKHByb2ZpdDMpDQoNCmRmMyA9IHBkLkRhdGFGcmFtZSh7IkN1dG9mZiI6IGN1dG9mZl9yYW5nZSwgIlByb2ZpdF9GZXQiOiBwcm9maXRfZmV0fSkNCg0KcGx0LnBsb3QoIkN1dG9mZiIsICJQcm9maXRfTm9uZSIsIGRhdGE9ZGZfcHJvZml0LCBsYWJlbD0iTm9uZSIsIGx3PTIpDQpwbHQucGxvdCgiQ3V0b2ZmIiwgIlByb2ZpdF9UdXJuZWQiLCBkYXRhPWRmX3Byb2ZpdCwgbGFiZWw9IlR1cm5lZCIsIGx3PTIpDQpwbHQucGxvdCgiQ3V0b2ZmIiwgIlByb2ZpdF9GZXQiLCBkYXRhPWRmMywgbGFiZWw9IkZldCIsIGx3PTIpDQpwbHQudGl0bGUoIkZpZ3VyZSAzOiBQcm9maXQiLCBmb250c2l6ZT0xMykNCnBsdC54bGFiZWwoIkN1dG9mZiIpDQpwbHQueWxhYmVsKCJQcm9maXQiKQ0KcGx0Lnl0aWNrcyhmb250c2l6ZT0xMikNCnBsdC54dGlja3MoZm9udHNpemU9MTIpDQpwbHQubGVnZW5kKGZvbnRzaXplPTgpDQpwbHQuc2hvdygpDQoNCmBgYA0KDQoNCiMgUHJvZml0IENvbXBhcmlzaW9uDQoNCiFbXShDOi9Vc2Vycy9BZG1pbi9Eb2N1bWVudHMvcHJvZml0Mi5qcGcpDQoNCg0KYGBge3B5dGhvbiwgcHl0aG9uLnJldGljdWxhdGUgPSBGQUxTRX0NCg0KIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0NCiMgICAgICAgICAgICAgICAgICAgUHJvdmUNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09DQojIEZ1bmN0aW9uIGNhbGN1bGF0ZXMgYXZlcmFnZSBwcm9maXQgd2l0aCBnaXZlbiBjdXRvZmYNCiMgZm9yIENhdEJvb3N0Q2xhc3NpZmllciBhbmQgUmFuZG9tRm9yZXN0Q2xhc3NpZmllcjoNCg0KZnJvbSBjYXRib29zdCBpbXBvcnQgQ2F0Qm9vc3RDbGFzc2lmaWVyDQoNCmRlZiBhdmVyYWdlX3BybyhjdXRvZmYpOg0KICAgIG5fdGltZXMgPSAxMA0KICAgIHJhbmRvbVNlZWRzID0gbnAuYXJhbmdlKDEsIG5fdGltZXMgKyAxLCAxKQ0KDQogICAgcHJvX2NhdCA9IFtdDQogICAgcHJvX3JhbiA9IFtdDQoNCiAgICBmb3IgaiBpbiByYW5kb21TZWVkczoNCiAgICAgICAgIyBGb3IgQ2F0Qm9vc3RDbGFzc2lmaWVyOg0KICAgICAgICBjYXQgPSBDYXRCb29zdENsYXNzaWZpZXIocmFuZG9tX3N0YXRlPWosIHZlcmJvc2U9RmFsc2UpDQogICAgICAgIGNhdC5maXQoWF90cmFpbiwgeV90cmFpbikNCiAgICAgICAgcGRfY2F0ID0gY2F0LnByZWRpY3RfcHJvYmEoWF90ZXN0KVs6LCAxXQ0KICAgICAgICBwcm9maXRfY2F0ID0gcHJvZml0X2J5X2N1dG9mZihjdXRvZmY9Y3V0b2ZmLCBwcmVkX3Byb2I9cGRfY2F0KQ0KICAgICAgICBwcm9fY2F0LmFwcGVuZChwcm9maXRfY2F0KQ0KICAgICAgICAjIEZvciBSYW5kb21Gb3Jlc3RDbGFzc2lmaWVyOg0KICAgICAgICByYW4gPSBSYW5kb21Gb3Jlc3RDbGFzc2lmaWVyKHJhbmRvbV9zdGF0ZT1qKQ0KICAgICAgICByYW4uZml0KFhfdHJhaW4sIHlfdHJhaW4pDQogICAgICAgIHBkX3JhbiA9IHJhbi5wcmVkaWN0X3Byb2JhKFhfdGVzdClbOiwgMV0NCiAgICAgICAgcHJvZml0X3JhbiA9IHByb2ZpdF9ieV9jdXRvZmYoY3V0b2ZmPWN1dG9mZiwgcHJlZF9wcm9iPXBkX3JhbikNCiAgICAgICAgcHJvX3Jhbi5hcHBlbmQocHJvZml0X3JhbikNCg0KICAgIGRmX3Jlc3VsdCA9IHBkLkRhdGFGcmFtZSh7IkF2Z1Byb0NhdCI6IFtucC5tZWFuKHByb19jYXQpXSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICJBdmdQcm9SYW4iOiBbbnAubWVhbihwcm9fcmFuKV0sDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAiQ3V0b2ZmIjogW2N1dG9mZl19KQ0KDQogICAgcmV0dXJuIGRmX3Jlc3VsdA0KDQojIEF2ZyBwcm9maXQgYnkgcmFuZ2Ugb2YgY3V0b2ZmOg0KZGZfYXZnUHJvID0gcGQuRGF0YUZyYW1lKCkNCg0KZm9yIGkgaW4gY3V0b2ZmX3JhbmdlOg0KICAgIGRmX2kgPSBhdmVyYWdlX3BybyhjdXRvZmY9aSkNCiAgICBkZl9hdmdQcm8gPSBkZl9hdmdQcm8uYXBwZW5kKGRmX2kpDQoNCiMgUmVzdWx0Og0KDQpwbHQucGxvdCgiQ3V0b2ZmIiwgIkF2Z1Byb0NhdCIsIGRhdGE9ZGZfYXZnUHJvLCBsYWJlbD0iQ2F0Qm9vc3QiLCBsdz0yKQ0KcGx0LnBsb3QoIkN1dG9mZiIsICJBdmdQcm9SYW4iLCBkYXRhPWRmX2F2Z1BybywgbGFiZWw9IlJhbmRvbUZvcmVzdCIsIGx3PTIpDQpwbHQudGl0bGUoIkZpZ3VyZSA0OiBQcm9maXQiLCBmb250c2l6ZT0xMykNCnBsdC54bGFiZWwoIkN1dG9mZiIpDQpwbHQueWxhYmVsKCJQcm9maXQiKQ0KcGx0Lnl0aWNrcyhmb250c2l6ZT0xMikNCnBsdC54dGlja3MoZm9udHNpemU9MTIpDQpwbHQubGVnZW5kKGZvbnRzaXplPTgpDQpwbHQuc2hvdygpDQoNCmBgYA0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQo=