[PYTHON] [Maschinelles Lernen] OOB (Out-Of-Bag) und sein Verhältnis

OOB (Out-Of-Bag), das häufig beim Lesen der Erklärung zu zufälligen Gesamtstrukturen auftritt, wird ausführlich erläutert.

Bootstrap-Sampling

Indem Sie Duplikate aus $ N $ Trainingsmustern $ \ {\ boldsymbol {x} _i, y_i \} _ {i = 1} ^ N $ zulassen und zufällig die gleiche Anzahl von $ N $ auswählen Die Methode zum Erstellen eines Trainingsbeispielsatzes wird als Bootstrap-Abtastung bezeichnet. Random Forest heißt "Forest", weil es viele Entscheidungsbäume mit $ M $ Trainingsmustern erstellt, die mit diesem Bootstrap-Sampling erstellt wurden.

Zu diesem Zeitpunkt wird $ N $ aus $ N $ mit Duplikaten ausgewählt, sodass einige Daten möglicherweise nicht ausgewählt werden. Dies wird als OOB (Out-Of-Bag) bezeichnet. Wird verwendet, um zufällige Gesamtstrukturfehler auszuwerten (z. B. hier) $ i $ th data $ (\ boldsymbol { Die Konzentration auf x} _i, y_i) $, $ M $ wird in einigen dieser Beispielsätze nicht verwendet. Daher besteht die OOB-Fehlerrate darin, nur die nicht verwendeten Bäume zu sammeln, um einen Teilbaum zu bilden und die Genauigkeit zu bewerten.

Wie viel dieses OOB sein wird, scheint es, dass ungefähr 36% der Proben nicht verwendet werden, wenn eine Probe gemacht wird, stimmt das? Lass es uns herausfinden.

Versuchen Sie es mit einer Simulation

Das Ergebnis der zufälligen Auswahl von 100 aus 100 Daten wurde 12 Mal wiederholt, und jedes wurde gezählt und ein Balkendiagramm wurde unten gezeichnet. Der Titel jedes Diagramms zeigt die Anzahl der nicht ausgewählten Daten, dh die Anzahl der OOBs. Man kann sagen, dass die Zahl ungefähr in der Mitte von 30 liegt. Die durchschnittliche Anzahl von 12 OOBs betrug etwa 34,83. Sicher ungefähr 30%.

Python

rd.seed(71)
n_data = 100
result = np.zeros((12, n_data))

OOBs = []
plt.figure(figsize=(16,8))
for i in range(12):
    ax = plt.subplot(4,3,i+1)
    result[i] = rd.randint(1,n_data+1, n_data)
    res = plt.hist(result[i], bins=range(1,n_data+1))
    cnt = Counter(res[0])
    plt.title("# of OOB = {}".format(cnt[0]))
    OOBs.append(cnts[0])
    plt.xlim(0, n_data)
     
plt.tight_layout() 
print("Average of OOB = {}".format(np.mean(OOBs)))

Theoretisch denken

Berücksichtigen Sie die Wahrscheinlichkeit, dass ein Beispiel $ \ boldsymbol {x} _i $ nicht ausgewählt wird. Da es insgesamt $ N $ gibt, ist die Tatsache, dass die Daten, auf die Sie gerade achten, nicht ausgewählt sind, dieselbe wie $ N-1 $, dh die Anzahl der Daten minus einer Ihrer eigenen, also ist die Wahrscheinlichkeit

\left( { N-1 \over N} \right)

ist. Nachdem wir nun $ N $ Stichproben ausgewählt haben, werden wir Stichproben aus $ N $ mal Datensätzen erstellen, also werden wir mit $ N $ multiplizieren.

\left( { N-1 \over N} \right)^{N} = \left( 1-{ 1 \over N} \right)^{N}

Wenn Sie dies berechnen, beträgt es tatsächlich etwa 36%, wenn Sie $ N $ erhöhen. Machen wir das.

Python

res_list = []
for i in range(6):
    n_data = 10**i
    result = (((n_data-1)/n_data)**n_data)*n_data 
    res_list.append([n_data,  result, result/n_data])
df = pd.DataFrame(res_list)
print( tabulate(df, ["Die Anzahl der Daten", "Anzahl der nicht ausgewählten Spalten" , "Nicht gewählte Rate"], tablefmt="pipe"))

Es scheint, dass es richtig auf ungefähr 36% konvergiert hat: kissing_heart:

Beziehung zu Napier Nummer e

** @nykergoto hat uns die Beziehung zur Anzahl der Napiers beigebracht. Vielen Dank! ** ** **

Übrigens diese Wahrscheinlichkeit,

\left( 1-{ 1 \over N} \right)^{N}

Definition der Anzahl der Napiers $ e $,

\lim_{n \rightarrow \infty} \left( 1 + { 1 \over N} \right)^{N}

Es ist ähnlich wie Wenn Sie die Variable hier in $ t = N-1 $ konvertieren

\left( { N-1 \over N} \right)^{N} = \left( { t \over t+1} \right)^{t+1} = \left( { t+1 \over t} \right)^{-(t+1)} = \left( 1 + { 1 \over t} \right)^{-(t+1)} = \left( \left( 1 + { 1 \over t} \right)^{t+1} \right)^{-1}

Wenn dieses $ t $ $ t \ rightarrow \ infty $ ist, ergibt sich aus der Definition der Anzahl der Napiers

\lim_{n \rightarrow \infty}  \left( \left( 1 + { 1 \over t} \right)^{t+1} \right)^{-1} = e^{-1}

Das Verhältnis von OOB, das der nicht ausgewählte Teil des Bootstrap-Beispiels ist, war das Gegenteil der Anzahl von Napiers!

Wenn ich es berechne, sind es sicherlich ungefähr 36%!

Python

np.e**-1

out

0.36787944117144233

Referenz

Python-Code für diesen Artikel (GitHub) 　https://github.com/matsuken92/Qiita_Contents/blob/master/General/OOB-test.ipynb

Scikit-Learn OOB Errors for Random Forests 　http://scikit-learn.org/stable/auto_examples/ensemble/plot_ensemble_oob.html