Kiedy oceniamy jakość Losowego Lasu, na przykład za pomocą AUC, czy bardziej odpowiednie jest obliczenie tych ilości na podstawie próbek po wyjęciu z torby lub na podstawie zestawu krzyżowego sprawdzania poprawności?

Słyszałem, że obliczenie go na próbkach OOB daje bardziej pesymistyczną ocenę, ale nie rozumiem dlaczego.

Uwaga: Chociaż uważam, że moja odpowiedź jest prawdopodobnie prawidłowa, mam również wątpliwości, ponieważ wszystko to wymyśliłem, myśląc o tym problemie dopiero po przeczytaniu tego pytania przez około 30–60 minut. Więc lepiej bądźcie sceptyczni i przyjrzyjcie się temu i nie dajcie się zwieść mojemu prawdopodobnie zbyt pewnemu stylowi pisania (użycie dużych słów i wymyślnych greckich symboli nie oznacza, że ​​mam rację).

streszczenie

To tylko podsumowanie. Wszystkie szczegóły są wymienione w sekcjach $\S1$ i $\S2$ poniżej.

Załóżmy przypadek klasyfikacji (można go rozszerzyć również na regresję, ale pominąć dla zwięzłości). Zasadniczo naszym celem jest oszacowanie błędu lasu drzew. Zarówno błąd „out-of-bag”, jak i k-krotna walidacja krzyżowa próbują powiedzieć nam prawdopodobieństwo, że:

• Las podaje prawidłową klasyfikację (k-krotna weryfikacja krzyżowa patrzy na to w ten sposób).

Co jest identyczne z prawdopodobieństwem, że:

• Większość głosów drzew leśnych to poprawny głos (OOBE patrzy na to w ten sposób).

I oba są identyczne. Jedyną różnicą jest to, że k-krotna walidacja krzyżowa i OOBE zakładają różną wielkość próbek do nauki. Na przykład:

• W 10-krotnej walidacji krzyżowej zestaw do nauki wynosi 90%, natomiast zestaw do testów wynosi 10%.
• Jednak w OOBE, jeśli każdy worek ma próbek, tak że całkowita liczba próbek w całym zestawie próbek, oznacza to, że zestaw uczenia wynosi praktycznie około 66% (dwie trzecie), a zestaw testowy wynosi około 33% ( jedna trzecia).n $n$$n =$

Dlatego, moim zdaniem, jedynym powodem, dla którego OOBE jest pesymistycznym oszacowaniem błędu lasu, jest to, że zwykle ćwiczy na mniejszej liczbie próbek niż zwykle w przypadku k-krotnej walidacji krzyżowej (gdzie 10-krotność jest powszechna).

Z tego powodu uważam również, że 2-krotna walidacja krzyżowa będzie bardziej pesymistycznym oszacowaniem błędu lasu niż OOBE, a 3-krotna walidacja krzyżowa będzie mniej więcej tak samo pesymistyczna jak w przypadku OOBE.

1. Zrozumienie błędu braku worka

1.1 Wspólny pogląd na pakowanie

Każde drzewo w RF jest hodowane przez listę próbek losowo pobranych z zestawu uczenia z zamiennikiem. W ten sposób wiele próbek może mieć duplikaty, a jeślinastępnie można stwierdzić, że około jedna trzecia próbek w prawdopodobnie nie znajdzie się na liście próbek używanych do wyhodowania danego drzewa (są to próbki wyjęte z torby to konkretne drzewo. Proces ten jest niezależnie powtarzany dla każdego drzewa, więc każde drzewo ma inny zestaw próbek wyjętych z torby.X n n = | X | X$n$$\mathcal{X}$$n$$n = |\mathcal{X}|$$\mathcal{X}$$n$

1.2 Kolejny pogląd na pakowanie

Teraz ponownie opiszmy nieco inaczej pakowanie, aby znaleźć taki sam opis, który, miejmy nadzieję, będzie łatwiejszy w obsłudze.

Robię to, stwierdzając, że drzewo jest trenowane przez spakowane próbki w zbiorze . Nie jest to jednak do końca prawdą, ponieważ zestaw nie ma zduplikowanych próbek (tak działają zestawy), podczas gdy - z drugiej strony - lista próbek może mieć duplikaty.X t ⊆ X X t$t$$\mathcal{X}_t \subseteq \mathcal{X}$$\mathcal{X}_t$$n$

Dlatego możemy powiedzieć, że drzewo jest hodowane przez analizę próbek plus pewną liczbę losowo wybranych duplikatów z , a mianowicie , na przykład: X t X t X t , 1 , X t , 2 , … , X t , r ⊆ X t | X t | + r ∑ i = 1 | X t , i | = $t$$\mathcal{X}_t$ $\mathcal{X}_t$$\mathcal{X}_{t,1}, \mathcal{X}_{t,2}, \ldots, \mathcal{X}_{t,r} \subseteq \mathcal{X}_t$

$$\begin{equation} |\mathcal{X}_t| + \sum_{i=1}^r|\mathcal{X}_{t,i}| = n \end{equation}$$

Trywialne jest, aby zobaczyć, że z tej kolekcji zestawów możemy zdefiniować listę wielu próbek, które zawierają duplikaty, po prostu dodając elementy w każdym zestawie do tablicy . W ten sposób dla każdego istnieje co najmniej jedna wartość taka, że .$\mathcal{C} = \{\mathcal{X}_t, \mathcal{X}_{t,1}, \ldots, \mathcal{X}_{t,r}\}$$n$$\mathcal{C}_i \in \mathcal{C}$$a$$1 \le p \le n$$i$$a[p] \in \mathcal{C}_i$

Widzimy również, że lista próbek w tablicy jest uogólnieniem tworzenia worków, jak zdefiniowałem w sekcji 1. Trywialne jest, aby zobaczyć, że w przypadku określonej definicji , którą zdefiniowałem w tej sekcji ( ), lista próbek w tablicy może być dokładnie identyczna z listą próbek zdefiniowaną w Sekcji 1.$n$$a$$\mathcal{X}_t$$\S2$$a$

1.3 Uproszczenie pakowania

Zamiast hodować drzewo według próbek w tablicy , będziemy je rozwijać na podstawie wolnej od duplikacji listy instancji, które można znaleźć tylko w .$t$$a$$\mathcal{X}_t$

Uważam, że jeśli jest wystarczająco duże, drzewo które jest hodowane przez analizę próbek w jest identyczne z innym drzewem które jest hodowane z próbek w tablicy .$n$$t$$\mathcal{X}_t$$t'$$a$

Moim powodem jest to, że prawdopodobieństwo duplikowania próbek w jest równie prawdopodobne w przypadku innych próbek w tym samym zestawie. Oznacza to, że kiedy mierzymy zysk informacji (IG) jakiegoś podziału, IG pozostanie identyczny, ponieważ entropie również pozostaną identyczne.$\mathcal{X}_t$

Powodem, dla którego uważam, że entropie nie zmieniają się systematycznie dla danego podziału, jest to, że zmierzone empirycznie prawdopodobieństwo próbki posiadającej określoną etykietę w pewnym podzbiorze (po zastosowaniu podziału decyzji) również się nie zmieni.

Powodem, dla którego prawdopodobieństwo nie powinno się zmienić w moim przekonaniu jest to, że wszystkie próbki w są równie prawdopodobne, że zostaną zduplikowane w kopie .$\mathcal{X}_t$$d$

1.4 Pomiar błędów braku opakowania

Niech będzie próbkami z drzewa . To znaczy . Zatem błąd pojedynczego drzewa to: A całkowity błąd lasu przy wielu drzewach to: , która może być uważane za empirycznie zmierzone prawdopodobieństwo, że większość głosów wszystkich drzew w lesie jest poprawna .$\mathcal{O}_t$$t$$\mathcal{O}_t = \mathcal{X} \setminus \mathcal{X}_t$$t$

$$\begin{equation} \frac{\text{total $\mathbf{x}$ in $\mathcal{O}_t$ correctly classified by $t$}}{|\mathcal{O}_t|} \end{equation}$$ $n_t$ $$\begin{equation} \frac{\sum_{t=1}^{n_t} \text{total $\mathbf{x}$ in $\mathcal{O}_t$ correctly classified by $t$}}{\sum_{t=1}^{n_t}|\mathcal{O}_t|} \end{equation}$$

2. Zrozumienie k-krotnej walidacji krzyżowej

Najpierw dzielimy zestaw uczenia na wiele równych partycji, mianowicie . To znaczy , a dla każdego , (to sugeruje porcjowanie).$\mathcal{X}$$n_k$$\mathcal{K} = \{\mathcal{K}_1, \mathcal{K}_2, \ldots, \mathcal{K}_{n_k}\}$$\mathcal{K}_1 \cup \mathcal{K}_2 \cup \ldots \cup \mathcal{K}_{n_k} = \mathcal{X}$$\mathcal{K}_i, \mathcal{K}_j \in \mathcal{K}$$\mathcal{K}_i \cap \mathcal{K}_j = \emptyset$

Niech będzie testem fold, a będzie zbiorem do nauki.$\mathcal{K}_t$$\mathcal{K} \setminus \{\mathcal{K}_t\}$

Niech będzie lasem niektórych drzew zbudowanym przy użyciu jako zestawu do nauki.$f$$\mathcal{K} \setminus \{\mathcal{K}_t\}$

Wówczas k-krotna walidacja krzyżowa lasu to: ∑ n k t = 1 suma  x  w  K t  poprawnie sklasyfikowana przez  $f$

$$\begin{equation} \frac{\sum_{t=1}^{n_k} \text{total $\mathbf{x}$ in $\mathcal{K}_t$ correctly classified by $f$}}{\sum_{t=1}^{n_k} |\mathcal{K}_t|} \end{equation}$$

Co jest również prawdopodobne, że las poprawnie klasyfikuje dowolną próbkę wejściową.$f$