Это первая из специальной серии вводных статей Synced, посвященных традиционно теоретическим областям исследований и их влиянию на современное машинное обучение.

1. Введение

Краеугольным камнем теории информации является идея количественной оценки объема информации в сообщении. В более общем смысле, чтобы количественно оценить информацию о событии. Основной мерой, используемой для количественной оценки информации в этом отношении, является энтропия, которой и будет посвящена эта статья.

Обычно теоретико-информационные величины, такие как энтропия и относительная энтропия, возникают снова и снова в ответ на фундаментальные вопросы коммуникации и статистики. Эти величины также нашли свое применение в машинном обучении, где они становятся все более важными.

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

В этом обзоре мы вводим большинство основных определений, необходимых для дальнейшего развития теории информации. После определения таких понятий, как энтропия и взаимная информация, мы устанавливаем полезные свойства, такие как правило цепочки величин. Наконец, мы попытаемся предоставить несколько примеров этих концепций в сфере машинного обучения.

2. Энтропия, относительная энтропия и взаимная информация.

2.1 Энтропия

Сначала введем общее определение энтропии. Пусть X - дискретная случайная величина с алфавитом X и вероятностной функцией масс p (x) = Pr {X = x}, x ∈ X. Энтропия H (X) X определяется как

В качестве логарифма используется основание 2, а энтропия может быть выражена в битах.

Мы можем рассматривать энтропию как меру неопределенности случайной величины X. Возьмем простой пример. Рассмотрим случайную величину X как подбрасывание монеты с Pr {x = Heads} = 1/2 = Pr {x = tails} (a честная монета). H (X) = -p (головы) x журнал p (головы) + (-p (хвосты) x журнал p (решки)) = - (1/2) x журнал (1/2) - (1/2) x log (1/2) = 1. Таким образом, количество битов (энтропия), необходимое для выражения результата подбрасывания монеты (случайная величина X), составляет 1 бит. Другими словами, результат подбрасывания монеты может быть закодирован в один бит информации, то есть 0 = орёл, 1 = решка.

Возьмем второй пример, который является крайним из вышеприведенного случая. Рассмотрим подбрасывание смещенной монеты только с орлами, т. Е. Pr {x = Heads} = 1, Pr {x = tails} = 0. Энтропия H (X) = - (1) x log (1) - (0) x log (0) = 0 + 0 = 0, где мы используем соглашение (0) x log (0) = 0. Таким образом, энтропия подбрасывания смещенной монеты равна 0. Другими словами, нам не нужны биты для описания случай подбрасывания необъективной монеты, потому что мы уже знаем результат. Более того, возвращаясь к концепции неопределенности, подбрасывание смещенной монеты дает 0 или отсутствие неопределенности, поскольку результат всегда известен.

Обратите внимание, что энтропия является функцией распределения X. Она не зависит от фактических значений, принимаемых случайной величиной X, а только от вероятностей.

Энтропию X также можно интерпретировать как ожидаемое значение логарифма случайной величины (1 / p (X)), где X строится в соответствии с функцией массы вероятности p (x). Это определяется как

Обозначим математическое ожидание через E. То есть, если X ∼ p (x), математическое ожидание случайной величины g (X) записывается как

или E g (X) для простоты. Таким образом, мы видим, что H (x) = E g (X), где g (X) = log (1 / p (X)).

Некоторые важные свойства энтропии обсуждаются ниже.

Энтропия неотрицательна, H (X) ≥ 0.
Это легко доказать, поскольку p (x) случайной величины всегда неотрицательно и находится в диапазоне 0 ≤ p (x) ≤ 1. Второе условие означает, что log (1 / p (X)) ≥ 0, и, следовательно, суммирование положительных чисел не может быть отрицательным.

Энтропия может быть изменена от одного основания к другому путем умножения на соответствующий коэффициент, Hb (X) = (logb a) Ha (X).
Это может можно увидеть, применив свойство журнала log_b (p) = log_b x (a log_a) (p)). Это позволяет нам изменить основание логарифма в определении.

2.2 Совместная энтропия и условная энтропия

Определение энтропии, данное в 2.1, относится к одной случайной величине. Теперь расширим определение на пару случайных величин (X, Y).

Совместная энтропия H (X, Y) пары дискретных случайных величин (X, Y) с совместным распределением p (x, y) определяется как

что также может быть выражено как

Условная энтропия случайной величины с учетом другой случайной величины определяется как ожидаемое значение энтропии условных распределений (помните, что энтропия является функцией некоторого распределения), усредненной по условной случайной величине. Условная энтропия H (Y | X) определяется как

Где случайные величины (X, Y) имеют совместное распределение p (x, y).

Полезное свойство (или теорема) - это цепное правило энтропии, условной энтропии и совместной энтропии. Он описывается как

Мы можем думать об этом как об энтропии пары случайных величин, являющейся энтропией одной плюс условной энтропией другой.

Важно отметить, что условная энтропия (в общем случае) не симметрична, т. Е. H (Y | X) ≠ H (X | Y). Однако
H (X) - H (X | Y) = H (Y) - H (Y | X), и часто это свойство используется в теории информации и кодирования.

Еще одно полезное свойство - кондиционирование снижает энтропию. Математически это выражается как

с равенством тогда и только тогда, когда X и Y независимы. Это будет доказано после того, как мы введем взаимную информацию.

2.2 Относительная энтропия и взаимная информация

Теперь мы вводим два связанных понятия: относительная энтропия и взаимная информация. Относительная энтропия, обозначаемая D (p || q), является мерой расстояния между двумя распределениями. В статистике он возникает как ожидаемый логарифм отношения правдоподобия. В машинном обучении относительная энтропия также принята в качестве целевой функции, которую необходимо минимизировать во время обучения. Например, имея набор входных данных и целевых (справочных) данных, мы передаем входные данные в модель для получения тестовых выходных данных. Затем мы можем измерить и сравнить распределения тестовых выходных данных и целевых выходных данных. Чем ближе два распределения (меньшая относительная энтропия), тем лучше модель предсказывает выходные данные для входных данных.

Другой способ интерпретировать относительную энтропию как меру неэффективности предположения, что распределение равно q, когда истинное распределение равно p. Давайте снова воспользуемся примером с подбрасыванием монеты. Рассмотрим монету смещения, где (истинное) распределение равно p, то есть Pr {Heads} = 1, Pr {tails} = 0. Для этой монеты, если мы построим код для описания результата подбрасывания монеты, код будет иметь 0 бит, поскольку мы уже знаем результат. Однако тот, кто не знает, что монета предвзята, может построить код для справедливой монеты с распределением, обозначенным как q, то есть Pr {Heads} = 1/2 = Pr {Tails}. Код будет иметь длину 1 (бит) и может быть описан как H (p) + D (p || q) = 1, где H (p) = 0 и D (p || q) = 1.

Чтобы увидеть этот расчет, мы сначала определим относительную энтропию. Относительная энтропия или расстояние Кульбака – Лейблера между двумя вероятностными массовыми функциями p (x) и q (x) определяется как

В приведенном выше определении мы используем соглашение о том, что

и соглашение (основанное на аргументах непрерывности), что

Таким образом, если существует такой символ x ∈ X, что p (x) ›0 и q (x) = 0, то D (p || q) = ∞. D (p || q) часто можно использовать как меру расстояния, определенную на p и q. Интуитивно понятно, что когда p = q, наше кодирование будет оптимальным, поэтому D (p || q) = 0. В общем, чем ближе q к p, тем меньше будет D (p || q). Обратите внимание, что D (p || q) не равно D (q || p), и они имеют разные интерпретации.

С этим определением вернемся к примеру с монетой и покажем расчеты.

Таким образом, мы получаем H (p) + D (p || q) = 1, как указано. Мы можем думать о H (p) как о минимальном количестве битов, необходимых для выражения события (подбрасывание монеты), а D (p || q) как о штрафе к требуемому количеству битов при использовании неправильного распределения.

Затем мы вводим взаимную информацию, которая является мерой количества информации, которую одна случайная величина содержит о другой случайной величине. Взаимная информация, обозначенная I (X; Y), представляет собой относительную энтропию между совместным распределением p (x, y) и распределением продукта p (x) p (y).

Здесь p (x, y) - совместная функция массы вероятности двух случайных величин X и Y, а p (x), p (y) - функции предельной массы вероятности X и Y соответственно.

Переставляя взаимную информацию, мы видим, что

I(X; Y) = H(X) - H(X|Y).

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

Кроме того, поскольку H (X, Y) = H (X) + H (Y | X), мы можем записать взаимную информацию как

I(X; Y) = H (X) + H (Y) − H (X, Y).

Наконец, отметим, что

I (X; X) = H (X) − H (X|X) = H (X).

То есть взаимная информация случайной величины с самой собой представляет собой энтропию случайной величины. Это причина того, что энтропию иногда называют самоинформацией. Вышеупомянутые три варианта взаимной информации можно резюмировать на следующей диаграмме Венна.

Теперь мы представим условную взаимную информацию. Условная взаимная информация случайных величин X и Y, заданных Z, определяется как

2.3 Полезные свойства и их последствия

Здесь мы обсудим несколько свойств энтропии, относительной энтропии и взаимной информации. Эти свойства позволят нам понять, как они используются в машинном обучении и почему работают. Мы также вводим некоторые необходимые предварительные условия.

Выпуклость функции
Функция f (x) называется выпуклой на интервале (a, b), если для любых x1, x2 ∈ (a, b) и 0 ≤ λ ≤ 1,

f(λ x_1 + (1−λ) x_2 ) ≤ λ f(x_1) + (1−λ) f(x_2).

Кроме того,

  • функция f называется строго выпуклой, если равенство выполняется, только если λ = 0 или λ = 1.
  • функция f вогнута, если −f выпукло.
  • примеры выпуклых функций включают x², e ^ x, xlog (x) (для x≥0) и т. д.
  • примеры вогнутых функций включают sqrt (x) и log (x) для x≥0.
  • линейные функции ax + b бывают как выпуклыми, так и вогнутыми.

Неравенство Дженсена
Неравенство Дженсена утверждает, что если f - выпуклая функция, а X - случайная величина, то

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

где в этом случае функция масс вероятности является распределением двух массовых точек. Предположим, что теорема верна для распределений с k-1 массовыми точками. Тогда мы можем написать p’_i = p_i / (1-p_k) для i = 1, 2, 3,…, (k-1), и это даст нам

где первое неравенство следует из предположения индукции, а второе неравенство следует из определения выпуклости. Неравенство Йенсена используется для доказательства неотрицательности D (p || q).

Неотрицательность D (p || q)
Пусть p (x) и q (x), где x ∈ X, - две вероятностные массовые функции. Тогда D (p || q) ≥ 0 с равенством тогда и только тогда, когда p (x) = q (x) для всех x. Доказательство этого состоит в следующем. Пусть A = {x: p (x) ›0} - опорное множество p (x). потом

где первое неравенство (в строке 3) взято из неравенства Йенсена. Умножив обе стороны на -1, мы получим наше утверждение D (p || q) ≥ 0. Кроме того, поскольку log (t) является строго вогнутой функцией от t, если мы умножим обе стороны на отрицательное значение, log ( 1 / t) становится строго выпуклой функцией от t. Из приведенного выше анализа мы можем понять, почему относительная энтропия или KL-дивергенция важна в контексте машинного обучения.

  • Выпуклость D (p || q) позволяет гарантировать минимальные значения, если найдена допустимая точка.
  • Свойство неотрицательности делает эту функцию хорошей «штрафной» функцией для добавления к проблеме минимизации.

Когда p берется как эмпирическое распределение значений в наших наблюдаемых данных, а q - как распределение, заданное вероятностной моделью, которую необходимо оценить, минимизация KL-дивергенции D (p || q) будет эквивалентна максимизации вероятности наши данные. Вот почему относительная энтропия часто применяется в приложениях машинного обучения.

Цепное правило энтропии и взаимной информации
Сначала мы вводим цепное правило энтропии. Пусть X_1, X_2,…, X_n нарисованы согласно совместному распределению p (x_1, x_2,…, x_n). потом

Это можно легко доказать, непрерывно увеличивая совместную энтропию двух случайных величин, как показано ниже.

Точно так же правило цепочки применимо и к взаимной информации. Вспоминая определение условной взаимной информации, цепное правило информации заключается в следующем.

Доказательства представлены ниже.

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

где последнее неравенство связано с неотрицательностью относительной энтропии.

Давайте подробнее рассмотрим это определение взаимной информации. Обратите внимание, что теперь мы должны думать о распределении по парам (X, Y), глядя на KL-дивергенцию. То есть, когда мы вычисляем KL-дивергенцию, сумма будет взята по всем парам (x, y), где x - значение X, а y - значение Y. Мы можем видеть, что p (X) p ( Y) также дает нам распределение по таким парам. Вот почему интерпретация I (X; Y) как меры ассоциации / зависимости X и Y имеет смысл. Чем более независимы X и Y, тем ближе будут p (X, Y) и p (X) p (Y).

Кондиционирование снижает энтропию
Напомним, что в разделе 2.1 мы заявили, что H (X | Y) ≤ H (X), или «информация не может повредить». Доказательство легко увидеть как

H (X) − H (X|Y) = I(X; Y) ≥ 0,

где неравенство от неотрицательности взаимной информации. Эта теорема имеет очень интуитивный смысл. В нем говорится, что знание другой случайной величины Y может только уменьшить неопределенность в X. Обратите внимание, что это верно только в среднем. В частности, H (X | Y = y) может быть больше, меньше или равно H (X), но в среднем

H (X|Y) = sum_y p(y)H(X|Y=y) ≤ H(X)

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

Мы можем взглянуть на несколько примеров того, как эти концепции применяются в машинном обучении. Например, если X - это категория документа, а Y - слово, I (X; Y) можно использовать для выбора слов, связанных с темами. Такие слова, по-видимому, наиболее полезны для классификации документов по категориям. KL-дивергенция D (p || q) может использоваться для выполнения поиска, если p - это языковая модель униграммы запроса, а q - языковая модель униграммы документа.

Другой пример - использование взаимной информации в качестве критерия для выбора признаков и преобразования признаков. Его можно использовать для характеристики как релевантности, так и избыточности переменных, например выбор функции минимальной избыточности.

3. Перспектива теории информации / кодирования

В этом разделе я хотел бы представить несколько различных интерпретаций этих концепций с более традиционной точки зрения теории информации и кодирования.

Энтропия случайной величины - это мера неопределенности случайной величины; это мера (минимального) количества информации, необходимой в среднем для описания случайной величины.

Давайте вернемся к идее (раздел 2.2) построения «кода» для представления результата эксперимента (или события). Например, если мы хотим закодировать 4 возможных сообщения A, B, C и D. Каковы возможные способы кодирования этого?

Предположим, что каждый символ одинаково вероятен, например, p (A) = p (B) = p (C) = p (D) = (1/4). Сначала давайте вычислим энтропию этого кода ENC_1.

H(ENC_1) = Pr{A}log(1/Pr{A})+Pr{B}log(1/Pr{B})+Pr{C}log(1/Pr{C})+Pr{D}log(1/Pr{D})
         = (1/4)log(4) + (1/4)log(4) + (1/4)log(4) + (1/4)log(4)
         = 2 bits

Если мы используем следующую кодировку ENC_1 = {A↦00, B↦01, C↦10, D↦11}, средняя длина кода составляет 2 бита (рассчитывается ниже). Это равно вычисленной энтропии.

Length(ENC_2) = 2xPr{A}+2xPr{B}+2xPr{C}+2xPr{D}
              = 2x(1/4)+2x(1/4)+2x(1/4)+2x(1/4)
              = 2

Однако, если распределения вероятностей A, B, C и D не равны, это кодирование может быть неоптимальным. Например, пусть {0,8, 0,1, 0,05, 0,05} будет распределением вероятностей A, B, C и D соответственно. Энтропия этого распределения равна

H(ENC_2) = Pr{A}log(1/Pr{A})+Pr{B}log(1/Pr{B})+Pr{C}log(1/Pr{C})+Pr{D}log(1/Pr{D})
         = (0.8)log(1/0.8) + (0.1)log(1/0.1) + (0.05)log(1/0.05) + (0.05)log(1/0.05)
         = 1.0219 bits

Таким образом, мы видим, что для представления информации требуется всего 1,0219 бита. Поскольку 1.02 бит не существует, мы можем создавать только коды, в которых A, B, C, D отображаются в целое число битов. Однако H (ENC_2) говорит нам, что мы можем сделать намного лучше, чем 2 бита ENC_1.

На рисунке 2 показано дерево Хаффмана, чтобы проиллюстрировать идею «снижения стоимости представления символов с высокой вероятностью». Это также известно как энтропийное кодирование.

Под кодировкой на рисунке 12 имеем ENC ’= {A↦0, B↦01, C↦011, D↦111}. Средняя длина теперь L (ENC ’) = 0,8x1 + 0,1x2 + 0,05x3 + 0,05x3 = 1,5 бита. Обратите внимание, что это число все еще далеко от 1,02 бита, но также меньше, чем просто кодирование каждого символа двумя битами. Вот почему мы можем интерпретировать энтропию как минимальное необходимое количество бит для представления распределения.

Далее мы обсудим KL-дивергенцию. Как упоминалось в разделе 2.2, мы можем интерпретировать KL-дивергенцию как среднее количество битов, которые тратятся впустую при кодировании событий из распределения p кодом, основанным на «неправильном» распределении q. Следуя энтропии ENC_2, являющейся минимальным количеством битов, необходимых для представления распределения p = {0,8, 0,1, 0,05, 0,05}, мы теперь рассмотрим KL-дивергенцию, когда мы используем q = {(1/4), ( 1/4), (1/4), (1/4)} для кодирования p.

Мы видим, что если мы используем распределение q (равная вероятность) для построения кода, нам потребуется 2 бита, что в среднем равно H (p) + D (p || q) бит.

H(p) + D(p||q) = 1.0219 + 0.9781
               = 2

Следовательно, именно поэтому D (p || q) можно рассматривать как штраф за использование неправильного предположения о базовом распределении.

Наконец, взаимная информация I (X; Y) дает нам меру того, сколько информации разделяется между двумя случайными величинами X и Y. Это относительная энтропия между совместным распределением и произведением предельных распределений двух случайных величин. Интерпретация взаимной информации - это среднее уменьшение длины кодового слова для Y при условии, что X известен.

4. Заключительные замечания

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

В следующих выпусках этой специальной серии Synced будут представлены другие области исследований, традиционно ориентированные на анализ и оптимизацию, такие как выпуклый анализ, линейное и нелинейное программирование и их влияние на современное машинное обучение.

Автор: Джошуа Чоу | Редактор: H4O и Майкл Саразен

Синхронизированный отчет | Обзор решений искусственного интеллекта в Китае в ответ на пандемию COVID-19 - 87 тематических исследований от 700+ поставщиков ИИ

В этом отчете предлагается взглянуть на то, как Китай использовал технологии искусственного интеллекта в борьбе с COVID-19. Он также доступен на Amazon Kindle. Наряду с этим отчетом мы также представили базу данных, охватывающую 1428 дополнительных решений искусственного интеллекта из 12 сценариев пандемии.

Нажмите здесь, чтобы найти больше отчетов от нас.

Мы знаем, что вы не хотите пропустить какие-либо новости или открытия. Подпишитесь на нашу популярную рассылку Synced Global AI Weekly, чтобы получать еженедельные обновления AI.