Введение

Прирост информации от наблюдения другой случайной переменной

В теории информации и машинном обучении, прирост информации является синонимом расхождения Кульбака — Лейблера; это количество информации, полученной о случайной переменной или сигнале при наблюдении другой случайной переменной. Однако, в контексте деревьев решений, этот термин иногда используется как синоним взаимной информации, которая представляет собой условное математическое ожидание расхождения Кульбака — Лейблера унивариантного распределения вероятностей одной переменной от условного распределения этой переменной при заданном значении другой переменной. Прирост информации случайной переменной X, полученный при наблюдении случайной переменной A, принимающей значение a, определяется как расхождение Кульбака — Лейблера априорного распределения для x от апостериорного распределения для x при заданном a. Математическое ожидание прироста информации равно взаимной информации I(X; A) между X и A, то есть уменьшению энтропии X, достигаемому при определении состояния случайной переменной A. В машинном обучении эта концепция может быть использована для определения предпочтительной последовательности атрибутов для исследования, чтобы наиболее быстро сузить возможные состояния X. Такая последовательность (которая зависит от результатов исследования предыдущих атрибутов на каждом этапе) называется деревом решений и применяется в области машинного обучения, известной как обучение деревьев решений. Как правило, атрибут с высокой взаимной информацией следует предпочитать другим атрибутам.

Формальное определение

Пусть T обозначает набор обучающих примеров, каждый из которых имеет вид , где – значение атрибута или признака примера, а y – соответствующая метка класса. Информационный прирост для атрибута a определяется с точки зрения энтропии Шеннона следующим образом. Для значения v, принимаемого атрибутом a, определим как множество обучающих входных данных T, для которых атрибут a равен v. Тогда информационный прирост T для атрибута a равен разности между априорной энтропией Шеннона обучающего набора и условной энтропией . Взаимная информация равна общей энтропии для атрибута, если для каждого из значений атрибута можно сделать однозначную классификацию для результирующего атрибута. В этом случае относительные энтропии, вычитаемые из общей энтропии, равны 0. В частности, значения определяют разбиение данных обучающего набора T на взаимоисключающие и всеохватывающие подмножества, индуцируя категориальное распределение вероятностей по значениям атрибута a. Распределение задается следующим образом. В этом представлении информационный прирост T при заданном a может быть определен как разность между безусловной энтропией Шеннона T и ожидаемой энтропией T, обусловленной a, где ожидаемое значение берется относительно индуцированного распределения на значения a.

Недостатки и решения

Хотя прирост информации обычно является хорошей мерой для определения релевантности признака, он не идеален. Значительная проблема возникает при применении прироста информации к признакам, которые могут принимать большое количество различных значений. Например, предположим, что строится дерево решений для данных, описывающих клиентов компании. Прирост информации часто используется для определения наиболее релевантных признаков, чтобы их можно было протестировать вблизи корня дерева. Одним из входных признаков может быть номер членства клиента, если он является участником программы лояльности компании. Этот признак имеет высокую взаимную информацию, поскольку он уникально идентифицирует каждого клиента, но мы не хотим включать его в дерево решений. Принятие решения о том, как обслуживать клиента, основываясь на его номере членства, вряд ли будет хорошо обобщаться на новых, ранее не встречавшихся клиентах (переобучение). Эта проблема также может возникнуть, если в выборке для тестирования присутствует несколько признаков с большим количеством различных значений. В этом случае это может привести к тому, что прирост информации для каждого из этих признаков будет значительно выше, чем для признаков с меньшим количеством различных значений. Чтобы решить эту проблему, Росс Куинлан предложил выбирать признак с наибольшим отношением прироста информации к энтропии из числа признаков, чей прирост информации равен среднему или выше. Это снижает вероятность выбора в качестве признаков для разбиения тех, которые имеют большое количество различных значений, при этом не давая несправедливого преимущества признакам с очень низкой информационной ценностью, поскольку информационная ценность выше или равна приросту информации.