Может ли значение коэффициента усиления информации быть отрицательным?

Ответ 1

IG(Y|X) = H(Y) - H(Y|X) >= 0, так как H(Y) >= H(Y|X) наихудший случай состоит в том, что X и Y независимы, поэтому H(Y|X)=H(Y)

Другим способом думать об этом является то, что, наблюдая, что случайная величина X принимает какое-то значение, мы либо не получаем никакой информации о Y (вы не теряете ее).

ИЗМЕНИТЬ

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

Предположим, что проблема классификации, где мы даем заданный набор экземпляров и меток (дискретных классов).

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

Это, в свою очередь, эквивалентно выбору функции с наибольшим усилением информации, поскольку

InfoGain = entropyBeforeSplit - entropyAfterSplit

где энтропия после расщепления представляет собой сумму энтропий каждой ветки, взвешенной по количеству экземпляров вниз по этой ветки.

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

Возьмем этот простой пример проблемы двоичной классификации. На некотором node мы имеем 5 положительных экземпляров и 4 отрицательных (всего 9). Поэтому энтропия (до расщепления):

H([4,5]) = -4/9*lg(4/9) -5/9*lg(5/9) = 0.99107606

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

    [4+,5-]
     /   \        H([4,0],[0,5]) =  4/9*( -4/4*lg(4/4) ) + 5/9*( -5/5*lg(5/5) )
    /     \                      =  0           // zero entropy, perfect split
[4+,0-]  [0+,5-]

затем

IG = H([4,5]) - H([4,0],[0,5]) = H([4,5])       // highest possible in this case

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

    [4+,5-]
     /   \        H([4,5],[0,0]) =  9/9 * H([4,5]) + 0
    /     \                      =  H([4,5])    // the entropy as before split
[4+,5-]  [0+,0-]

и

IG = H([4,5]) - H([4,5],[0,0]) = 0              // lowest possible in this case

Теперь, где-то между этими двумя случаями, вы увидите любое количество таких случаев, как:

    [4+,5-]
     /   \        H([3,2],[1,3]) =  5/9 * ( -3/5*lg(3/5) -2/5*lg(2/5) )
    /     \                       + 4/9 * ( -1/4*lg(1/1) -3/4*lg(3/4) )
[3+,2-]  [1+,3-]

и

IG = H([4,5]) - H([3,2],[1,3]) = [...] = 0.31331323

поэтому независимо от того, как вы разделили эти 9 экземпляров, вы всегда получаете положительный выигрыш в информации. Я понимаю, что это не математическое доказательство (перейдите к MathOverflow для этого!), Я просто подумал, что реальный пример может помочь.

(Примечание: все вычисления в соответствии с Google)

Ответ 2

Для всех, кто сталкивается с этим вопросом, несмотря на свой возраст, я предлагаю этот ответ и совет.

Во-первых, ответ отрицательный, он не может быть отрицательным. Абсолютная наихудшая возможность - это не изменение, а IG - ноль. Если вы хотите получить доказательство, посмотрите полное доказательство на MathOverFlow, как указал Амро.

Теперь за советом. Если вы делаете только первый уровень дерева решений, кажется очевидным, что он никогда не станет отрицательным. Однако, когда я строил свое первое дерево с помощью Information Gain, я оказался с отрицательным выигрышем от моего третьего разветвления. Это не показалось мне полезным или возможным, поэтому я попытался проверить свою математику. Математика была прекрасна. Часть я неправильная была первой частью базовой формулы. Я использовал ответ с уровня выше в качестве начальной энтропии, но это неправильно, потому что оно включает в себя информацию из других наборов данных. Вы должны убедиться, что для вашей начальной энтропии вы определяете энтропию только для этой ветки! Это означает, что ваша "начальная энтропия" может быть на самом деле выше, чем на уровне до этого.

Другими словами, при вычислении IG убедитесь, что вы используете только текущий набор данных.

Ответ 3

Конечно, это возможно.

Информационное усиление - это просто изменение информационной энтропии из одного состояния в другое:

IG (Ex, a) = H (Ex) - H (Ex | a)

Это изменение состояния может идти в любом направлении - оно может быть положительным или отрицательным.

Это легко увидеть на примере:

Алгоритмы дерева решений работают следующим образом: при заданном node вы вычисляете свою энтропию информации (для независимой переменной).

Вы можете думать об этом так: информационная энтропия относится к категориальным/дискретным переменным, поскольку дисперсия относится к непрерывным переменным). Разница, конечно, является лишь квадратом стандартного отклонения. Например, если мы прогнозируем цену, основанную на различных критериях, и мы произвольно группируем наш набор данных в две группы, в которых цены для группы A (50, 60 и 70) и цены для группы B (50, 55, 60), группа B имеет самую низкую дисперсию, то есть они близки друг к другу. Разумеется, дисперсия не может быть отрицательной (потому что после того, как вы суммируете расстояния каждой точки от среднего, вы ее квадратизируете), но разница в дисперсии, безусловно, может.

Чтобы понять, как это связано с информационной энтропией/информационным усилением, предположим, что мы не прогнозируем цену, а что-то еще, например, станет ли посетитель нашего сайта зарегистрированным пользователем или подписчиком премиум-класса или нет. Необязательная переменная здесь является дискретной, а не непрерывной, как цена, поэтому вы не можете рассчитать дисперсию значимым образом. Вместо этого используется информационная энтропия. (Если вы сомневаетесь в близкой аналогии между дисперсией и IE, вы должны знать, что большинство алгоритмов дерева решений, способных обрабатывать как дискретные, так и непрерывные переменные, в последнем случае алгоритм будет использовать дисперсию как критерий расщепления, а не использовать IG. )

В любом случае, после вычисления энтропии информации для данного node, вы затем разбиваете данные на этот node (который является полным набором данных, если вы находитесь в корневом каталоге node), при каждом значении для каждой переменной, затем для каждого разделения, вычислить IE для обеих групп и взять средневзвешенный IE. Затем выполните разделение, которое приведет к наименьшему средневзвешенному IE и сравните его с IE node (который, очевидно, представляет собой только одну группу). Если этот взвешенный средний IE для раскола ниже IE node, тогда вы разбиваете данные на этом node (формируете ветку), если нет, то вы останавливаете, то есть node нельзя разделить - вы находитесь внизу.

В целом, в основе алгоритма дерева решений лежит критерий определения того, следует ли разделить node - то, как они построены. Этот критерий заключается в том, является ли IG положительным или отрицательным.