Статистические критерии отбора признаков в комбинаторных алгоритмах распознавания

Выделение "куч"

Во многих случаях представление о том, что условие часто выполняется на объектах одного класса и редко - на объектах другого, естественно формализовать в "пороговом" виде, считая условие z признаком класса A, если p₁(z) > Q и p₂(z) q; соответственно, признак класса B - это условие z, для которого выполнены неравенства p₁(z) q и p₂(z) > Q. Проще говоря, мы требуем, чтобы в области истинности z была, так сказать, куча объектов одного из классов. Незначительным усложнением будет использование Q_i и q_i вместо Q и q.

Условие z бесполезно, если

p₁(z) Q и p₂(z) > q или q < p₁(z) < Q или q < p₂(z) < Q. Снова выберем бесполезность условия в качестве нулевой гипотезы и будем проверять ее по частям, соответствующим разным классам, по отдельности и с уровнем значимости Снова всякий раз, когда допущена ошибка первого рода (нулевая гипотеза отвергнута, когда она истинна), скажем, что в описание класса проник предрассудок. При описанной процедуре проверки вероятность появления предрассудка (в отдельном испытании) не превосходит

Опишем теперь критерий проверки нулевой гипотезы.

Вероятность того, что условие z истинно на k объектах из m_i объектов i-го класса равняется

Отсюда следует, что

P{#_i(z) A_i} = 1 - B(m_i, A_i-1,p_i(z)) = B(m_i, m_i-A_i, 1-p_i(z)),

где B(k,s,p) - кумулятивная функция биномиального распределения, т.е. вероятность того, что в k испытаниях, в каждом из которых вероятность "успеха" равняется p, будет наблюдено не более s "успехов".

Если p(z)Q, то

B(m_i, m_i-A_i, 1-p_i(z)) B(m_i, m_i-A_i, 1-Q).

Отсюда следует, что критические значения A_i и a_i для проверки указанных частей нулевой гипотезы определяются соотношениями

B(m_i, m_i-a_i, 1-q) /2 B(m_i, m_i-a_i-1, 1-q), (5.1)
B(m_i, m_i-A_i, 1-Q) /2 B(m_i, m_i-A_i, 1-Q), (5.2)

в противном случае объявляем его бесполезным.

Остается еще решить, как выбирать пороги q и Q.

Представляется очень естественным в качестве нижнего порога q выбирать вероятность истинности условия в предположении, что объекты соответствующего класса распределены в факторном пространстве равномерно. Для условия ранга r эта вероятность равняется 2^r. Это же значение можно взять в качестве "первого приближения" и для вероятности Q. Если результаты перебора покажут, что полезных условий много, значение Q можно увеличить (а q уменьшить) и провести новый цикл перебора (сиречь обучения).

В случае, когда ситуация описывается второй из рассмотренных в предыдущем разделе моделью, можно предложить несколько более развернутые соображения о выборе порогов. Легко показать, что оптимальная классификация, основывающаяся лишь на априорных вероятностях классов, состоит в том, чтобы все объекты относить к классу с большей априорной вероятностью, причем вероятность ошибки такого априорного решающего правила равна I₀ = min {, }. Для каждого условия z можно оценить вероятность p(A|z) = p{ A | z() = 1} и аналогичную вероятность p(B|z). Как и раньше, объекты, на которых z выполнено, нужно относить к классу с наибольшей апостериорной вероятностью. Вероятность ошибки такого апостериорного решающего правила равна I_z = min{p(A|z), p(B|z)}. Потребуем, чтобы апостериорное решающее правило, основанное на признаке класса, ошибалось не чаще, чем априорное, т.е. чтобы было выполнено неравенство I_z < I₀. При > оно удовлетворяется, если для признаков первого класса выполнено p₁(z) > p₂(z), а для признаков второго класса - более жесткое неравенство p₁(z) <p₂(z). Отсюда следует, что при > условие z естественно считать полезным, если

p₁(z)> Q₁ и p₂(z) q₂ или p₁(z) q₁ и p₂(z) > Q₂, где Q₁q₂ и Q₂ q₁. В качестве pi1

выбираются их оценки по обучающей выборке, а в качестве "первого приближения" для q_i - снова величины 2^-r. Критические области определяются соотношениями B(m_i, m_i-a_i, 1-q_i)/2 < B(m_i, m_i-a_i-1, 1-q_i),
B(m_i, m_i-A_i, 1-Q) /2 < B(m_i, m_i-A_i-1, 1-Q_i).

Заметим теперь, что при оценке полезности условия мы оперируем вероятностями p_i(z), хотя свойства условия, позволяющие нам называть его признаком класса, естественнее формулируются в терминах апостериорных вероятностей классов. Так, условие z естественно называть признаком класса A, если p(A|z) > p(B|z). Несмотря на то, что вероятности p(A|z) и p(B|z) имеют смысл лишь в рамках модели с случайными маргиналами, расширив толкование цели поиска описания, мы можем обосновать выбор порогов q_i в обеих рассмотренных моделях.

Неравенство p(A|z) > p(B|z) выполнено тогда и только тогда, когда

p(z|A) > (1-)p(z|B), (6) где (напомню) pi1

- априорная вероятность класса A. Предположим теперь, что применять найденные признаки мы собираемся при другой априорной вероятности piA

класса A. Очевидно, что при этом, вообще говоря, условие может перестать быть признаком класса. Другими словами, не при всяких p(z|A) и p(z|B) неравенство (6) выполнено при любом значении piA

. Более того, легко видеть, что неравенство (6) выполнено при любом значении gamma

тогда и только тогда, когда p(z|B) = 0. Таким образом, если мы собираемся использовать найденные признаки при произвольных априорных вероятностях классов, мы должны положить q₂ = 0. Предположим теперь, что найденные описания будут применяться лишь при >. Нетрудно показать, что при этом неравенство (6) будет выполнено тогда и только тогда, когда (1-) p(z|B)p(z|A). Отсюда следует, что необходимо выбирать (1-) q₂ Q₁ и уж заведомо (1-) q₂.

Вы можете попасть на эту страницу по одному из следующих адресов:
http://learn.at/infoscope/AI/patt_rec/feat_sel/FSelect2.html
http://read.at/infoscope/AI/patt_rec/feat_sel/FSelect2.html
http://now.at/infoscope/AI/patt_rec/feat_sel/FSelect2.html

Дата последней модификации: 10 октября 2000 г.

Hosted by www.Geocities.ws