Модель максимальной энтропии (MaxEnt) также является типичным алгоритмом классификации и похожа на логистическую регрессию тем, что относится к логарифмически-линейной модели классификации. В процессе оптимизации функции потерь используется метод выпуклой оптимизации, аналогичный машине опорных векторов. Использование энтропии напоминает нам об алгоритмах ID3 и C4.5 в алгоритме дерева решений. После понимания модели максимальной энтропии у вас будет более глубокое понимание логистической регрессии, машин опорных векторов и алгоритмов дерева решений. В этой статье будет кратко изложен принцип модели максимальной энтропии.
Обзор энтропии и условной энтропии
Энтропия измеряет неопределенность вещей, и чем более неопределенны вещи, тем больше их энтропия. В частности, выражение энтропии случайной величины X выглядит следующим образом:
где n представляет n различных дискретных значений X. И pi представляет вероятность того, что X примет значение i, а log — это логарифм по основанию 2 или e.
Зная энтропию переменной X, ее легко обобщить на совместную энтропию нескольких переменных Вот выражение совместной энтропии для двух переменных X и Y:
С помощью совместной энтропии можно получить выражение условной энтропии H(Y|X).Условная энтропия похожа на условную вероятность.Она измеряет неопределенность нашего Y после знания X. Выражение выглядит следующим образом:
Их взаимосвязь легко понять с помощью следующей диаграммы. Эллипс слева представляет H(X), эллипс справа представляет H(Y), перекрывающаяся часть посередине представляет собой нашу взаимную информацию или получение информации I(X,Y), а перекрывающаяся часть эллипса на слева H(X|Y) , эллипс справа удаляет перекрывающуюся часть и равен H(Y|X). Объединение двух эллипсов есть H(X,Y).
Определение модели максимальной энтропии
Модель максимальной энтропии предполагает, что модель классификации представляет собой условное распределение вероятностей P(Y|X), где X — признак, а Y — результат.
Учитывая обучающий набор (x(1),y(1)),(x(2),y(2)),...,(Икс(m),y(m)), где x — n-мерный вектор признаков, а y — выход категории. Наша цель — использовать модель максимальной энтропии для выбора наилучшего типа классификации.
Учитывая обучающую выборку, мы можем получить эмпирическое распределение P¯(X,Y) общего совместного распределения P(X,Y) и эмпирическое распределение P¯(X) маргинального распределения P(X). P¯(X,Y) — это количество одновременных вхождений X и Y в обучающем наборе, деленное на общее количество выборок m, а P¯(X) — это количество вхождений X в обучающем наборе, деленное на общее количество образцов m.
Вышеприведенная формула является условием ограничения обучения модели максимальной энтропии, если у нас есть M характеристических функций fi(x,y)(i=1,2...,M) имеет M ограничений. Можно понять, что если в обучающем наборе есть m выборок, то есть M ограничений, соответствующих m выборкам.
Таким образом, мы получаем модель максимальной энтропии, определяемую следующим образом:
Предположим, что набор моделей, удовлетворяющих всем ограничениям, таков:
Условная энтропия, определенная на условном распределении вероятностей P (Y | X), равна:
Наша цель — получить соответствующее значение P(y|x), когда H(P) максимизируется. Здесь мы можем добавить отрицательный знак к H(P), чтобы найти минимальное значение. Цель этого состоит в том, чтобы сделать −H(P ) — выпуклая функция, для нахождения экстремального значения которой удобно использовать метод выпуклой оптимизации.
Оптимизация функции потерь модели максимальной энтропии
В предыдущем разделе мы получили функцию H(P) для модели максимальной энтропии. Его функция потерь −H(P) определяется как:
Ограничения:
Поскольку это выпуклая функция, а соответствующее ограничение является аффинной функцией, в соответствии с теорией выпуклой оптимизации эту задачу оптимизации можно преобразовать в функцию оптимизации без ограничений с помощью функции Лагранжа. В настоящее время лагранжиан, соответствующий потере функция Суточная функция L(P,w) определяется как:
где шi(i=1,2,...m) — множитель Лагранжа. Если вы также изучали машины опорных векторов, вы обнаружите, что используемая здесь теория выпуклой оптимизации та же самая, а затем используется двойственность Лагранжа.
Наша функция Лагранжа, исходная задача выпуклой оптимизации:
Соответствующая двойственная лагранжева задача:
Поскольку исходная задача удовлетворяет условию ККТ в выпуклой теории оптимизации, решение исходной задачи и решение двойственной задачи согласованы. Таким образом, оптимизация нашей функции потерь становится оптимизацией двойственной задачи Лагранжа.
Первый шаг в решении двойственной задачи состоит в том, чтобы найти
Это может быть получено выводом. То, что мы получаем таким образом, является функцией w. Записать как:
является двойственной функцией, и ее решение записывается в виде:
В частности, найдите частную производную L(P,w) по P(y|x):
Пусть частная производная равна 0, выражение P(y|x) относительно w можно решить следующим образом:
Среди них З.w(x) — коэффициент нормализации, определяемый как:
Таким образом, мы получили связь между P(y|x) и w, так что все P(y|x) в двойственной функции ψ(w) можно заменить на w, так что двойственная функция ψ(w ) Все представлены w. Затем мы максимизируем ψ(w), мы можем получить значение вектора w, соответствующее максимизации, и ввести связь между P(y|x) и w, так что мы также можем получить P(y|x) окончательно результат.
Чтобы максимизировать ψ(w), поскольку его можно вывести непрерывно, существует множество методов оптимизации, таких как метод градиентного спуска, метод Ньютона и квазиньютоновский метод. Существует также специальный метод оптимизации для моделей с максимальной энтропией, называемый улучшенным итеративным масштабированием (IIS).
IIS также является эвристическим методом, он предполагает, что текущий вектор параметров равен w, мы надеемся найти новый вектор параметров w + δ, чтобы двойственная функция ψ(w) возрастала. Если такой метод удается найти, его можно повторять до тех пор, пока не будет найден максимум двойственной функции.
Метод, используемый IIS, состоит в том, чтобы найти нижнюю границу B(w|δ) для ψ(w+δ)−ψ(w), получить соответствующее значение δ путем минимизации B(w|δ) и затем решить его итеративно. ж. Для B(w|δ) его минимизация получается взятием частной производной по δ.
Поскольку IIS обычно используется только для модели максимальной энтропии и не имеет широкого применения, процесс алгоритма здесь подробно описываться не будет.Заинтересованные друзья могут напрямую обратиться к статье IIS Улучшенный алгоритм итеративного масштабирования: мягкое введение.
Резюме модели максимальной энтропии
Модель максимальной энтропии является отличной моделью в методе классификации, но поскольку количество ее ограничивающих функций обычно увеличивается с увеличением размера выборки, когда размер выборки велик, итерация решения оптимизации с двойной функцией Процесс очень медленный, а в scikit-learn даже нет библиотеки для модели максимальной энтропии. Но это все равно интересно понять, тем более, что это неразрывно связано со многими методами классификации.
Условно суммируем преимущества и недостатки модели максимальной энтропии как метода классификации:
Преимущества модели максимальной энтропии:
а) Статистическая модель с максимальной энтропией получает модель с наибольшей информационной энтропией среди всех моделей, удовлетворяющих ограничениям, и уровень точности выше, чем у классической модели классификации.
б) Ограничения можно задавать гибко, а приспособленность модели к неизвестным данным и степень подгонки к известным данным можно регулировать количеством ограничений
Недостатки модели максимальной энтропии:
а) Из-за взаимосвязи между количеством функций ограничений и количеством выборок итерационный процесс требует огромного объема вычислений и его трудно применять на практике.
Рекомендуется для вас
Краткое описание алгоритма обнаружения выбросов
Поговорим о функциях активации
Анализ оптимизаций глубокого обучения: Momentum, RMSProp и Adam
Краткое изложение алгоритмов бэггинга и случайного леса