Когда мы оцениваем качество случайного леса, например, с использованием AUC, более ли уместно вычислять эти количества по образцам «из пакета» или по совокупности перекрестной проверки?

Я слышал, что вычисление его по образцам OOB дает более пессимистическую оценку, но я не понимаю, почему.

Примечание: хотя я чувствую, что мой ответ, вероятно, правильный, я также чувствую сомнение из-за того, что я все это придумал, подумав об этой проблеме только после прочтения этого вопроса в течение 30-60 минут. Так что вам лучше скептически отнестись к этому и тщательно исследовать это, а не обманывать себя моим, возможно, чрезмерно уверенным стилем письма (я использую большие слова и причудливые греческие символы, не значит, что я прав).

Резюме

Это просто резюме. Все детали упомянуты в разделах и § 2 ниже.$\S1$$\S2$

Давайте предположим случай классификации (может быть расширен до регрессии, но для краткости опущен). По сути, наша цель - оценить погрешность леса деревьев. Как ошибка из пакета, так и перекрестная проверка в k-кратном порядке пытаются определить вероятность того, что:

• Лес дает правильную классификацию (перекрестная проверка в k-кратном порядке смотрит на это так).

Что идентично вероятности того, что:

• Большинство голосов лесных деревьев является правильным (OOBE смотрит на это так).

И оба идентичны. Единственное отличие состоит в том, что перекрестная проверка в k-кратном порядке и OOBE предполагают различный размер обучающих выборок. Например:

• При 10-кратной перекрестной проверке набор обучения составляет 90%, а набор тестирования - 10%.
• Тем не менее, в OOBE, если каждый мешок имеет образцов, так что n $n$$n =$ общее количество образцов во всем наборе образцов, это означает, что обучающий набор составляет практически около 66% (две трети), а набор для тестирования составляет около 33% ( одна треть).

Поэтому, на мой взгляд, единственная причина, по которой OOBE является пессимистичной оценкой ошибки леса, заключается только в том, что обычно обучается с меньшим количеством выборок, чем обычно с кросс-проверкой в ​​k-кратном порядке (где обычно 10-кратное).

В связи с этим я также считаю, что 2-кратная перекрестная проверка будет более пессимистичной оценкой ошибки леса, чем OOBE, а 3-кратная перекрестная проверка будет примерно одинаково пессимистичной по отношению к OOBE.

1. Понимание ошибки из пакета

1.1 Общий взгляд на упаковку

Каждое дерево в RF растет из списка выборок, которые случайным образом взяты из обучающего набора X с заменой. Таким образом, n выборок могут иметь дубликаты, а если n = | X | затем можно обнаружить, что примерно одна треть выборок в X , вероятно, в конечном итоге не окажется в списке из n выборок, которые используются для выращивания данного дерева (это выборки из этого конкретного дерева вне пакета). Этот процесс независимо повторяется для каждого дерева, поэтому у каждого дерева есть свой набор образцов из пакета.$n$$\mathcal{X}$$n$$n = |\mathcal{X}|$$\mathcal{X}$$n$

1.2. Другой взгляд на упаковку

Теперь давайте немного по-другому опишем пакетирование с надеждой найти такое же описание, с которым, надеюсь, будет проще иметь дело.

Я делаю это, заявив , что дерево обучаются по пакетированным образцам в наборе X т ⊆ X . Тем не менее, это не совсем верно, поскольку набор X t не имеет дублированных выборок (именно так работают наборы), в то время как - с другой стороны - в списке n выборок могут быть дубликаты.$t$$\mathcal{X}_t \subseteq \mathcal{X}$$\mathcal{X}_t$$n$

Следовательно, мы можем сказать, что дерево выращивается путем анализа выборок X t и ряда случайно выбранных дубликатов, взятых из X t , а именно: X t , 1 , X t , 2 , … , X t , r ⊆ X t , таких как что: | X т | + r ∑ i = 1 | X т , я | = $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}$$

Нетрудно видеть, что из этого набора множеств мы можем определить список из n- многих выборок, которые содержат дубликаты, просто добавляя элементы в каждый установите C i ∈ C в массив a . Таким образом, для любого 1 ≤ p ≤ n существует хотя бы одно значение i такое, что a [ p ] ∈ C$\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$,

Мы также можем видеть, что список из выборок в массиве a является обобщением сумок, как я определил в разделе 1. Нетрудно видеть, что для некоторого конкретного определения X t, которое я определил в этом разделе ( § 2 ) , список образцов в массиве a может быть в точности идентичен списку образцов, как определено в разделе 1.$n$$a$$\mathcal{X}_t$$\S2$$a$

1.3. Упрощение упаковки

Вместо того, чтобы выращивать дерево помощью выборок в массиве a , мы будем наращивать их по списку экземпляров без дублирования, найденных только в X t .$t$$a$$\mathcal{X}_t$

Я полагаю, что, если достаточно велико, дерево t , которое выращивается путем анализа выборок в X t , идентично другому дереву t ' , которое выращивается из образцов в массиве $n$$t$$\mathcal{X}_t$$t'$$a$ .

Моя причина в том, что вероятность дублирования выборок в $\mathcal{X}_t$ одинаково вероятна для других выборок в том же наборе. Это означает, что когда мы измеряем информационный прирост (IG) некоторого разделения, IG останется идентичным, так как энтропии также останутся идентичными.

И причина, по которой я полагаю, что энтропии не будут систематически изменяться для данного разделения, заключается в том, что эмпирически измеренная вероятность того, что образец имеет конкретную метку в некотором подмножестве (после применения разделения решения), также не изменится.

И причина, по которой вероятности не должны меняться, на мой взгляд, состоит в том, что все выборки в с равной вероятностью будут дублированы в d копий.$\mathcal{X}_t$$d$

1.4 Измерение ошибок из пакета

$\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. Понимание k-кратной перекрестной проверки

$\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$

$\mathcal{K}_t$$\mathcal{K} \setminus \{\mathcal{K}_t\}$

$f$$\mathcal{K} \setminus \{\mathcal{K}_t\}$

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

$f$