Кросс-энтропия

От Joannes Vermorel, январь 2018

Кросс-энтропия — это метрика, которую можно использовать для оценки точности вероятностных прогнозов. Кросс-энтропия имеет тесные связи с методом максимального правдоподобия. Кросс-энтропия имеет первостепенное значение для современных систем прогнозирования, поскольку она является инструментальной для создания превосходящих прогнозов, даже для альтернативных метрик. С точки зрения управления цепями поставок, кросс-энтропия особенно важна, так как поддерживает оценивание моделей, которые также хорошо улавливают вероятности редких событий, часто оказывающихся самыми затратными. Эта метрика существенно отличается от интуиции, лежащей в основе более простых метрик точности, таких как среднеквадратичная ошибка или средняя абсолютная процентная ошибка.

Частотная вероятность против Байесовской вероятности

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

Кросс-энтропия отходит от этой перспективы, принимая байесовскую вероятность. Байесовский подход переворачивает проблему. При попытке количественно осмыслить неопределённое явление, байесовская перспектива начинает с модели, которая напрямую дает оценку вероятности для этого явления. Затем, посредством повторных наблюдений, мы оцениваем, как модель справляется с реальными случаями возникновения явления. По мере увеличения числа наблюдений, измерение (не)адекватности модели улучшается.

Обе перспективы — частотная и байесовская — являются допустимыми и полезными. С точки зрения управления цепями поставок, поскольку сбор наблюдений дорог и несколько негибок — у компаний мало возможностей для генерации заказов на продукт — байесовская перспектива зачастую оказывается более применимой.

Интуиция кросс-энтропии

Прежде чем углубляться в алгебраическую формулировку кросс-энтропии, давайте постараемся прояснить лежащую в её основе интуицию. Пусть у нас есть вероятностная модель — или просто модель в дальнейшем — предназначенная как для объяснения прошлого, так и для предсказания будущего. Для каждого прошедшего наблюдения эта модель предоставляет оценку вероятности того, что данное наблюдение произошло именно так, как оно случилось. Хотя можно сконструировать модель, которая просто запомнит все прошлые наблюдения, приписывая им вероятность ровно 1, такая модель не сможет ничего сказать о будущем. Таким образом, интересная модель каким-то образом аппроксимирует прошлое и, следовательно, выдает вероятности меньше 1 для прошлых событий.

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

Математическое произведение тысяч переменных, которые обычно меньше 0.5 — при условии, что мы имеем дело с довольно неопределённым явлением —, как ожидается, будет невероятно малым числом. Например, даже рассматривая отличную модель для прогнозирования спроса, какова вероятность того, что эта модель способна сгенерировать все данные о продажах, которые компания наблюдала в течение года? Хотя оценка этого числа является нетривиальной, очевидно, что оно было бы поразительно малым.

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

Формальное определение кросс-энтропии

Для двух дискретных случайных величин $${p}$$ и $${q}$$ кросс-энтропия определяется как:

$${H(p, q) = -\sum_x p(x)\log q(x)}$$

Это определение не симметрично. $${P}$$ предполагается как «истинное» распределение, наблюдаемое лишь частично, в то время как $${Q}$$ предполагается как «искусственное» распределение, полученное из построенной статистической модели.

В теории информации кросс-энтропию можно интерпретировать как ожидаемую длину сообщения в битах при кодировании, когда вместо $${P}$$ используется $${Q}$$. Эта перспектива выходит за рамки текущего обсуждения и не имеет первостепенного значения с точки зрения управления цепями поставок.

На практике, поскольку $${P}$$ неизвестно, кросс-энтропия эмпирически оценивается по наблюдениям, при простом предположении, что все собранные наблюдения имеют равную вероятность, то есть $${p(x)=1/N}$$, где $${N}$$ — число наблюдений.

$${H(q) = - \frac{1}{N} \sum_x \log q(x)}$$

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

Превосходство кросс-энтропии

С 1990-х до начала 2010-х годов большая часть статистического сообщества была убеждена, что самый эффективный способ, с чисто числовой точки зрения, оптимизировать заданную метрику, скажем MAPE (средняя абсолютная процентная ошибка), заключается в создании алгоритма оптимизации, непосредственно ориентированного на эту метрику. Однако критически важное, хоть и контринтуитивное, открытие, достигнутое сообществом глубокого обучения, показало, что это не так. Числовая оптимизация — очень сложная задача, и большинство метрик не подходят для эффективной, масштабной числовой оптимизации. Кроме того, в тот же период широкое сообщество науки о данных осознало, что все задачи прогнозирования/предсказания на самом деле являются задачами числовой оптимизации.

С точки зрения управления цепями поставок, вывод таков: даже если целью компании является оптимизация прогностической метрики, такой как MAPE или MSE (среднеквадратичная ошибка), то на практике самый эффективный путь — оптимизировать кросс-энтропию. В компании Lokad, в 2017 году, мы собрали значительное количество эмпирических данных, подтверждающих это утверждение. Более удивительно, что кросс-энтропия также превосходит CRPS (оценка непрерывного ранжирования вероятностей), другую метрику вероятностной точности, даже если полученные модели в конечном итоге оцениваются по CRPS.

Не до конца ясно, что делает кросс-энтропию такой хорошей метрикой для числовой оптимизации. Один из самых убедительных аргументов, подробно изложенный в Ian Goodfellow et all, заключается в том, что кросс-энтропия обеспечивает очень большие значения градиента, что особенно ценно для градиентного спуска, который как раз является самым успешным методом оптимизации в масштабах, доступным на данный момент.

CRPS против кросс-энтропии

Что касается цепей поставок, кросс-энтропия значительно превосходит CRPS как метрика для вероятностных прогнозов, просто потому что она гораздо сильнее акцентирует редкие события. Рассмотрим вероятностную модель спроса, имеющую среднее значение 1000 единиц, при этом вся масса распределения сосредоточена на отрезке от 990 до 1010. Допустим также, что следующая наблюдаемая величина спроса равна 1011.

С точки зрения CRPS, модель является относительно хорошей, поскольку наблюдаемый спрос отличается от среднезапланированного примерно на 10 единиц. В отличие от этого, с точки зрения кросс-энтропии модель имеет бесконечную ошибку: модель действительно предсказывала, что наблюдение 1011 единиц спроса имеет нулевую вероятность — весьма категоричное утверждение — которое, как оказалось, было фактически неверным, о чем свидетельствует факт наблюдения 1011 единиц.

Склонность CRPS отдавать предпочтение моделям, способным делать абсурдные утверждения, например, событие XY никогда не произойдет, в то время как событие все же происходит, во многом объясняет, с точки зрения цепей поставок, почему кросс-энтропия дает лучшие результаты. Кросс-энтропия предпочитает модели, которые, так сказать, не оказываются застигнутыми врасплох, когда происходит невероятное. В цепях поставок невероятное действительно случается, и когда это происходит без предварительной подготовки, необходимость реагировать на это событие оказывается очень затратной.