[Вернакулярный анализ] Изучение марковской модели максимальной энтропии на примере запаса воды

машинное обучение

[Вернакулярный анализ] Изучение марковской модели максимальной энтропии на примере запаса воды

0x00 сводка

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

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

В процессе объяснения и изложения я ставлю перед собой требования: найти пример в жизни или в известной книге, а затем объяснить его своими словами.

0x01 фон

в предыдущем [Народный анализ] Использование запаса воды в качестве примера для изучения скрытой марковской модели.В книге мы объясняли Скрытую марковскую модель на примере «прорыва Лян Чжуншу из особняка Дамин», но на самом деле ситуация может быть сложнее.Например, когда Лян Чжуншу прорвался и встретил Сун Цзяна, возможность его Выбор снова прорваться через Сун Цзяна будет ниже, потому что Сун Цзян должен быть окружен большинством героев в Ляншане, а прорваться через него слишком сложно. Но если вы столкнетесь с Ши Цзинем, опасность не так велика.

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

Идея Марковской модели с максимальной энтропией (MEMM) сочетает в себе HMM и максимальную энтропию, которые могут извлекать признаки для обобщения возможностей модели и объединять контекстные зависимости для непосредственного определения и снижения нагрузки на моделирование. Далее будет подробно описано.

1. Недостатки скрытых марковских моделей

HMM — это генеративная модель, которая определяет совместное распределение вероятностей, где y и x представляют собой случайные переменные для последовательности наблюдений и соответствующей последовательности меток соответственно. Чтобы иметь возможность определить это совместное распределение вероятностей, генерирующая модель должна перечислить все возможные последовательности наблюдений, что очень сложно в реальном рабочем процессе, поэтому нам нужно рассматривать элементы последовательности наблюдений как изолированные индивидуумы, то есть , предполагая, что каждый Элемент независим друг от друга, а наблюдения в любой момент зависят только от состояния в этот момент.

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

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

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

2. Характеристики модели максимальной энтропии

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

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

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

3. Введение МЭММ

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

  • MEMM решает проблему предположения о независимости выхода HMM. Поскольку HMM ограничивается только зависимостью между наблюдениями и состояниями, MEMM вводит пользовательскую функцию признаков, которая может не только выражать зависимость между наблюдениями, но и выражатьМежду текущим наблюдением и несколькими состояниями до и послеСложная зависимость ; (эта сложная зависимость выполняется с помощью функциональной функции, например, что такое «предыдущее слово/послесловие» слова)
  • MEMM учитывает зависимости между соседними состояниями. И, учитывая всю последовательность наблюдений, экспрессионная способность MEMM сильнее;
  • MEMM не учитывает P(X), что снижает нагрузку на моделирование. В то же время мы узнали, что целевая функция согласуется с функцией прогнозирования;

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

А MEMM — это дискриминационная модель. Он использует функцию для прямого распознавания и изучения границы, а MEMM определяется функциональной функцией.Поскольку здесь исключается предположение о независимости, совместное распределение вероятностей не может быть задано, можно рассчитать только апостериорную вероятность, поэтому это дискриминантная модель.. Но опять же, MEMM также имеет методы оценки максимального правдоподобия, градиентный спуск, итерацию Ньютона, квазиньютоновский спуск, BFGS, L-BFGS и многое другое.

0x02 Модель максимальной энтропии

Поскольку мы узнали о HMM в предыдущей статье, эта статья посвящена введению модели максимальной энтропии.

1. Логистическая регрессия

Как правило, классификатор машинного обучения решает, какую выходную метку y присвоить входу x, выбирая метку с наибольшим P(y|x) из всех возможных y_i. В задачах классификации логистическая регрессия работает, вычисляя вероятность принадлежности к каждому возможному классу для данного наблюдения, а затем выбирая класс, который дает наибольшую вероятность.

Логистическая регрессия — это алгоритм обучения с учителем для классификации, суть которого — линейная регрессия. Логистическая регрессия обучается с помощью условных оценок максимального правдоподобия. Это означает, что мы выберем параметр w, который максимизирует вероятность появления метки y в обучающих данных для заданного входного значения x. Обычно для нахождения максимального значения этой функции, то есть для нахождения оптимальных весов, можно использовать стохастический градиентный спуск, L-BFGS или сопряженные градиенты.

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

2. Принцип максимальной энтропии

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

Суть принципа максимальной энтропии состоит в том, что в предпосылке известного частичного знания наиболее разумным выводом о неизвестном распределении является: «наиболее неопределенный или случайный вывод» после согласования с известным знанием является единственным беспристрастным выводом, который мы можем сделать. Выбор, любой другой выбор означает, что мы добавляем дополнительные ограничения и предположения, которые не могут быть сделаны на основе имеющейся у нас информации.

例如，投掷一个骰子，如果问"每个面朝上的概率分别是多少"，你会说是等概率，即各点出现的概率均为1/6。因为对这个"一无所知"的色子，什么都不确定，而假定它每一个朝上概率均等则是最合理的做法。从投资的角度来看，这是风险最小的做法，而从信息论的角度讲，就是保留了最大的不确定性，也就是说让熵达到最大。

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

3. Модель максимальной энтропии

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

Потому что если мы хотим построить модель с максимальной энтропией для достижения классификации, то мы определяем модель p(y|x), которая должна быть: выбрать модель с наибольшей энтропией среди моделей при условии «удовлетворения априорным ограничениям» , то есть пусть может возникнуть неточная информация и т.п. Таким образом, мы получаем окончательную классификационную модель.

То есть, учитывая набор обучающих примеров, мы хотим найти распределение, удовлетворяющее следующим двум условиям:

  • удовлетворять известным ограничениям (удовлетворяет входным ограничениям)
  • максимизировать неопределенность

4. Известные ограничения

Контекстные и функциональные функции

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

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

Проблема в том, что данные расположены непослушным образом, и каждое измерение x уже приняло значение, ожидающее, пока мы его классифицируем, поэтому появляется эта штука: функция признаков. Мы используем функции признаков для представления ограничений, то есть функции признаков используются, чтобы указать, принадлежит ли элемент к определенному подмножеству.

Например, помните, что w — это слово предложения s, а w имеет много измерений, тогда функция признаков, используемая для представления этих измерений, может быть:

  • w в начале предложения
  • w в конце предложения
  • w имеет префикс xxx
  • Суффикс w - xxx
  • Слово перед w равно xxx

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

Характеристика Функция

Учитывая обучающий набор данных

T={(x1,y1),(x2,y2)...(xN,yN)}T = \{ (x_1, y_1), (x_2, y_2) ... (x_N, y_N) \}

Чтобы представить данные, мы извлекаем ряд признаков из данных. Вообще говоря, «особенности» относятся к характеристикам входа, тогда как «особенности» в модели максимальной энтропии относятся к общим характеристикам входа и выхода. Каждый признак и каждая категория могут образовывать признак и должны учитываться по принципу умножения. То есть мы можемКаждое значение каждой функции измерения X связано с определенной категорией.в паре иТакже используйте параметр, чтобы описать близость пары.

Его можно понять так: это разделение «входных признаков» в общем смысле на «общие признаки входа и выхода».

Например, оказалось:

{X=1}==>{Y=Classi}\{ X = 1 \} ==> \{ Y = Class_i \}

это

f(x,y)={1когда x, y удовлетворяют факту0когда факт не удовлетворенf(x,y) = \begin{cases} 1 & \text{когда x,y удовлетворяют факту} \\[2ex] 0 & \text{когда факт не удовлетворяет} \end{cases}

Например, каждая функция признаков может быть бинарной функцией от контекста до 0-1.

f(x,y)={1еслиx= "есть" и у = v0otherwisef(x,y) = \begin{cases} 1 & \text{if $x$ = "is" and y = v} \\[2ex] 0 & \text{otherwise} \end{cases}

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

Веса

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

использовать

Функция признаков используется для формального представления релевантной информации о знаниях X.: Среди всех признаков, какие признаки являются наиболее репрезентативными, а какие второстепенными, вам нужно выбрать самостоятельно и построить набор ограничений. Набор функций признаков отображает контекст из контекстного пространства в пространство признаков.

Появление характеристической функции улучшает способность модели к обобщению. Так как же сделать так, чтобы линейная модель H(x) имела аналогичную функцию? Ответом является функция признаков, так что входные данные x обрабатываются серией функций признаков, чтобы стать g(x), а затем отправляются в модель для классификации, например H(x) = H(g(x)) .

Собственная функция f(x,y) представляет собой не только количество, но и некоторое упрощение x и y (особенно x). Набор данных (x, y) обычно не запускает только одну функцию. В дополнение к форме «x принимает определенное значение, y принимает определенное значение», функция также может быть в форме «x принимает значение определенного типа, y принимает значение определенного типа» и в более общем смысле. , "x и y принимают определенное значение" форму отношения. Именно эти общие формы признаков позволяют достаточно обобщить модель максимальной энтропии. Когда набор данных запускает более одной функции, в exp содержится более одной суммы весов, и аналитическое решение не может быть получено.

С точки зрения модели максимальной энтропии n «признаков» каждого входа и k категорий вместе образуют nk признаков, и в модели имеется nk весов, которые взаимно однозначно соответствуют признакам. Каждая категория запускает n из nk функций. Совокупность признаков можно рассматривать как набор n признаковых функций.

5. Модель удовлетворяет известным ограничениям

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

соответствовать

Возвращаясь к набору обучающих данных, который мы дали ранее

T={(x1,y1),(x2,y2)...(xN,yN)}T = \{ (x_1, y_1), (x_2, y_2) ... (x_N, y_N) \}

Если данные (x1, y1) удовлетворяют характеристической функции f1(x,y), то если обученная нами модель M также может получить f1(x1,y1) = 1, это означает, что M может обрабатывать данные в (x1, y1) y1) хорошо подходит для f1 на данный момент.

Распределения вероятностей

Теперь для заданного набора обучающих данных обработайте обучающие данные как сгенерированные случайными величинами (?,?). Мы можем определить эмпирическое распределение ?˜(x,y) совместного распределения P(x,y) и эмпирическое распределение ?˜(x) маргинального распределения P(x) из обучающих данных, а именно:

?˜(X=x,Y=y)=count((X=x,Y=y))N?˜(X=x, Y=y) = \frac{count((X=x, Y=y))}{N}
?˜(X=x)=count((X=x))N?˜(X=x) = \frac{count((X=x))}{N}

Среди них count((X=x, Y=y) представляет частоту появления выборки (x,y) в обучающих данных, count((X=x)) представляет частоту появления x в обучающих данных. N представляет собой общее количество обучающих выборок.

ожидать

Два ожидания описаны ниже.

**Ожидание 1:** Теперь мы наблюдаем набор наборов данных и с помощью простой статистики можем узнать совместную вероятность любой комбинации Контекста x и Результата y. С совместной вероятностью можно рассчитать математическое ожидание наблюдаемой характеристической функции f, называемойОжидания наблюдения/ожидания опыта. То есть ожидаемое значение характеристической функции f(x,y) по отношению к эмпирическому распределению ?˜(x,y).

Eref(f)=∑x,yp~(x,y)f(x,y)=∑x,yf(x,y)NE_{ref}(f) = \sum_{x,y}p̃(x,y)f(x,y) = \frac{\sum_{x,y}f(x,y)}{N}

Поскольку функция признаков является полезной функцией для построения вероятностной модели, следует использовать модель максимальной энтропии, чтобы удовлетворить ограничение «ожидание наблюдения/ожидание опыта»,

**Ожидание 2:** Предположим, у нас есть модель, тогда мы можем найти математическое ожидание этой характеристической функции с точки зрения этой модели, называемоймодельные ожидания. То есть ожидаемое значение характеристической функции f (x, y) по отношению к модели p (y | x) и эмпирическому распределению p̃ (x).

Eq(f)=∑x,yp(x,y)f(x,y)≈∑x,yp~(x)p(y∣x)f(x,y)E_q(f) = \sum_{x,y}p(x,y)f(x,y) \ приблизительно\sum_{x,y}p̃(x)p(y|x)f(x,y)
  • E_ref на самом деле представляеттренировочные данныеДоля данных, соответствующих характеристической функции. Это можно понимать как собранные данные.
  • E_q на самом деле означаетПредыдущие данные моделиПропорция, удовлетворяющая ограничениям. Под ним можно понимать данные, полученные в ходе обучения.

Целью машинного обучения является изучение некоторой внутренней информации, содержащейся в данных, из набора данных, поэтому мы надеемся, что наша модель сможет хорошо отразить явление, содержащееся в данных. Такматематическое ожидание f, как видно из моделидолжно быть равноожидание f, наблюдаемое по данным. То есть Eq(f) = Eref(f). Другими словами, доля априорных данных, соответствующих ограничениям, равна доле обучающих данных, соответствующих характеристической функции, что фактически означает, что модель удовлетворяет ограничениям.

коллекция моделей

Предположим, что у нас есть n собственных функций, тогда у нас есть n наборов уравнений Eq(fi)=Eref(fi), i∈1,2,…,n.

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

C={p∣pеP\andEq(fi)=Eref(fi),iе(1,2,...,n)}C = \{p|p∈ P \и E_q(f_i)=E_{ref}(f_i), i∈(1,2,...,n) \}

Теперь нужно найти подходящую модель для описания данных, то есть искать p в P. Модель с максимальной энтропией находится из набора моделей C, удовлетворяющего ограничениям, которые максимизируют энтропию P(Y|X).

6. Максимизируйте неопределенность модели

Для этой модели p эта модель должна удовлетворять приведенному выше уравнению ожидаемого набора функций признаков (другими словами, ограничениям набора ожидаемых функций признаков). Начиная со всего распределения вероятностей, составленного из всех характеристических функций, необходимо удерживать неизвестные события в наиболее неупорядоченном состоянии (наиболее неупорядоченное состояние — это случай равнораспределения вероятностей). Мерой беспорядка является энтропия! Таким образом, существуют ограничения, но также для максимально возможного поддержания наиболее неупорядоченного состояния, чтобы как можно более равномерно не присваивать возможности неопределенному контексту. Целевое состояниеКогда ограничения соблюдены, состояние с наибольшей энтропией. Под энтропией здесь понимаетсяУсловная энтропия(Беспорядок y, когда x известен)

После определения ограничений ситуация получения максимальной энтропии фактически такова: получение максимального значения энтропии при ограничениях. То есть модель максимальной энтропии заключается в выборе модели с наибольшим условным распределением вероятностей p(y|x) в наборе моделей, удовлетворяющих ограничениям, и ее формализация выглядит следующим образом:

  • Согласно эмпирическому распределению получается набор моделей C, удовлетворяющий набору ограничений, то есть модель должна удовлетворять следующим двум ограничениям
Eref(fi)=Eq(fi),i=1,2,..,n∑yp(y∣x)=1E_{ref}(f_i) = E_q(f_i), i =1,2,..,n \\ \sum_y p(y|x) = 1
  • Наша цель обучения, целевая функция, состоит в том, чтобы максимизировать следующую формулу при этих двух ограничениях.
H(P)={−∑x,yp~(x)p(x∣y)logp(y∣x)}H(P) = \{-\sum_{x,y}p̃(x)p(x|y)logp(y|x) \}

Первое ограничение выше — это E_ref (доля данных, которые соответствуют функции признаков в обучающих данных) = E_q (доля априорных данных модели, которые соответствуют ограничениям), то есть модель уже соответствует ограничениям. Второе ограничение состоит в том, что распределение вероятностей должно быть равно 1.

Формула для нахождения максимального значения представляет собой формулу условной энтропии, определенную на условном распределении вероятностей p(y|x).Решение, полученное путем нахождения максимального значения, является моделью, изученной с помощью модели максимальной энтропии.

который

max?е?H(P)=max?е?{−∑x,yp~(x)p(x∣y)logp(y∣x)}max_{?∈?} H(P) = max_{?∈?} \{ -\sum_{x,y}p̃(x)p(x|y)logp(y|x) \}

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

7. Метод множителей Лагранжа.

Наконец, модель MaxEnt сформулирована как задача оптимизации с ограничениями. Для «нахождения максимального значения при ограничениях» легко придумать метод множителей Лагранжа и ввести множители Лагранжа: w0,w1,...,wn, определить функцию Лагранжа ? (?,?), преобразовывать с ограничениями в .

Теперь эту проблему можно формализовать как минимаксную задачу, которую легко решить с помощью лагранжевой двойственности. После решения оптимального w∗ получается требуемая модель MaxEnt.

Наконец, через сериючрезвычайно сложныйчтобы получить формулу, которую нужно максимизировать (здесь fi(x,y) представляет характеристическую функцию, а wi представляет вес характеристической функции):

max?е?∑?,??˜(?,?)∑?=1?????(?,?)+∑??˜(?)?????(?)max_{?∈?}∑_{?,?}?˜(?,?)∑_{?=1}^??_??_?(?,?)+∑_??˜(?)??(??

Здесь fi(x,y) представляет характеристическую функцию, wi представляет вес характеристической функции, Pw(y|x) представляет собой модель MaxEnt, а оптимальное решение записывается как w∗.

8. Оценка максимального правдоподобия

Но описанный выше процесс все еще слишком сложен. Есть ли простой и легкий способ? Ответ — оценка максимального правдоподобия MLE. Можно сделать математическое доказательство того, что максимизация двойной функции в обучении модели максимальной энтропии эквивалентна оценке максимального правдоподобия модели максимальной энтропии. Функция оценки максимального правдоподобия является выпуклой функцией, которая является самой простой моделью для оптимизации в задаче оптимизации, и мы можем получить глобальное оптимальное решение.

Вероятность модели максимальной энтропии рассчитывается с использованием (смоделированного) истинного распределения p(x,y) и (на основе данных) эмпирического распределения p̃(x,y)перекрестная энтропия для определения.

Имеются обучающие данные для получения эмпирического распределения ?˜(?,?) и функция правдоподобия решаемой модели вероятности ?(?|?):

??˜(??)=???∏?,??(?∣?)?˜(?,?)=∑?,??˜(?,?)????(?∣?)?_?˜(?_?)=???∏_{?,?}?(?|?)^{?˜(?,?)}=∑_{?,?}?˜(?,?)?(?|)

Пусть ??(?) обозначает ???(1−?0) , подставляем Pw(y|x) в формулу, чтобы получить:

??˜(??)=∑?,??˜(?,?)????(?∣?)=∑x,y?˜(x,y)∑i=1nwifi(x,y)−∑x?˜(x)logZw(x)?_?˜(?_?)=∑_{?,?}?˜(?,?)????(?|?) = \sum_{x,y}?˜(x,y)\sum_{i=1}^nw_if_i (x,y) - \sum_x?˜(x)logZ_w(x)

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

0x03 Реализация алгоритма модели максимальной энтропии

1. Обзор алгоритма

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

То есть есть n характеристических функций fi(x), тогда есть n наборов уравнений Eq(fi)=Eref(fi), i∈1,2,…,n. Это наборы ограничений. Наша тренировочная цель — целевая функция или энтропия H(p(y|x)). Мы ищем «набор комбинаций характеристической функции f (x, y) и ее веса λ», который максимизирует энтропию H (p (y | x)). Другими словами, мы хотим рассчитать математическое ожидание на основе параметров модели. Наконец, оптимизируйте как можно больше, чтобы ожидание модели было таким же, как и предыдущее ожидание, а энтропия была наибольшей.

Ход алгоритма следующий:

  1. Инициализировать λ=0

  2. цикл

    λi(t+1)=λi(t)+1ClogEref(fi)Eq(fi)λ_i^{(t+1)} = λ_i^{(t)} + \frac{1}{C} log \frac {E_{ref}(f_i)}{E_q(f_i)}
    C=maxx,y∑i=1nfi(x,y)C = max_{x,y}\sum_{i=1}^nf_i(x,y)

  3. Повторяйте 2 до сходимости

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

испытывать ожиданияEref(fi)=∑x,yp̃ (x,y)fi(x,y), чтобы найти Eref(fi), нужно только подсчитать количество пар (x,y) в обучающих данных, которые соответствуют fi, и затем разделите на количество N обучающих экземпляров.

модельные ожиданияСначала вам нужно найти p(y|x). Эту условную вероятность можно добавить, просто умножив все (x, y) fi на соответствующий параметр λi. Фактор нормализации представляет собой сумму p(y|x) для каждого результата y. После получения p(y|x) требуется уравнение (fi), просто перечислите все p(y|x), соответствующие (x, y), которые соответствуют fi, умножьте на количество вхождений Context x и разделите на N может.

С модельными ожиданиями и ожиданиями опыта просто поместите их в алгоритм для итерации.

Следующий код взят изeasyME

2. Структура данных и инициализация

//我们做分类问题，看到的数据往往是每个实例对应一个类别。比如说词性标注中一个词对应一个标注。为了下面讨论的方便，将类别称为Outcome，将每个实例的上下文环境叫做Context。 实例被称为Event，一个实例是 Outcome y 与Context的二元组
//一个多维的向量x。x的每个维度都是一个特征，可以认为 x 对应了一个 Context（特征的集合）。然后这条样本对应了一个label（Outcome）
struct Event {
    size_t classId; //将类别称为Outcome
    std::vector<size_t> context; //将每个实例的上下文环境叫做Context, 可以认为是一系列 feature 的列表, 每个 feature 被映射成一个数字。
    size_t count; //符合该上下文环境的(x,y)二元组的个数
}

// X的每一维度特征下的每个取值与某个类别配对，并同样的用一个参数（权重）来描绘这个配对的紧密程度
class DataManager {
  typedef std::pair<size_t, double> Pair;
  typedef std::vector<Pair> Param;
  std::vector<Event> mEventSet;
  std::vector<Param> mParamSet; //这个就是最后模型参数（权重）
  //fetId 特征纬度，classPos 类别
  void DataManager::incLambda(size_t fetId, size_t classPos, double incer) {
      mParamSet[fetId][classPos].second += incer; //更新模型参数（权重）
  }
}

//初始化
bool MaxEntModel::initModel(const char * trainFileName, bool freq, bool isSelectFeature) {
    string line, str;
    vector<size_t> context;
    size_t count = 1;
    // each line is a event, it looks like this: (count) className fetName ... fetName
    while(getline(fin, line)){
        istringstream sin(line);
        // with freq ?
        if(freq) sin >> count;
        sin >> str;
        size_t classId = mClassMap.insertString(str);
        context.clear();
        while(sin >> str){
            size_t fetId = mFetMap.insertString(str);
            context.push_back(fetId); //由此能看出，context是一系列的 feature
        }
        mModelInfo.addEvent(count, classId, context);
    }
    if(!freq) mModelInfo.processEventSet();
    mModelInfo.getAllFeatures();  
}

//在最大熵模型的视角下，每条输入的n个“特征”与k个类别共同组成了nk个特征，模型中有nk个权重，与特征一一对应。每个类别会触发nk个特征中的n个。特征的全体可以看做是n个特征函数组成的一个集合。
//Event是 实例是Outcome与Context的二元组，count是满足这个组合的数据个数，即，符合该上下文环境的(x,y)二元组的个数
void DataManager::addEvent(size_t count, size_t classId, const std::vector<size_t> & fetVec) {
	  mTotEvent += count;
    mEventSet.push_back(Event(count, classId, fetVec));
}

void DataManager::getAllFeatures() {
    size_t eventNum = getEventNum();
    for(size_t i = 0; i < eventNum; ++i){
        int cid = getEventClassId(i);
        for(context_iterator it = getContextBegin(i),
                end = getContextEnd(i);
                it != end; ++it){
            int fid = *it;
            addFeature(cid, fid);
        }
    }
    endAddFeature();
}

void DataManager::addFeature(size_t classId, size_t fetId, double weight = 0.0) {
    if(mParamSet.size() < fetId + 1) mParamSet.resize(fetId + 1);
    if(classId > mMaxCid) mMaxCid = classId;
    if(fetId > mMaxFid) mMaxFid = fetId;
    mParamSet[fetId].push_back(std::make_pair(classId, weight));
}

DataManager::context_iterator DataManager::getContextBegin(size_t eventId) {
    return mEventSet[eventId].context.begin();
}

3. Получите ожидания

//Eref(fi)，训练数据之中符合特征函数的数据的占比。可以理解为就是收集到的数据。 
//统计训练数据中符合fi的(x,y)二元组的个数，然后除以训练实例的个数N
void DataManager::getObserves(vector<vector<double> > & observed) {
	size_t mMaxFid = getFetNum();
	size_t eventNum = getEventNum();
    observed.clear();
    observed.resize(mMaxFid + 1);
    for(size_t i = 1; i <= mMaxFid; ++i){
        DataManager::param_iterator begin = getParamBegin(i);
        DataManager::param_iterator end = getParamEnd(i);
        size_t n = end - begin;
        observed[i].resize(n, 0);
    }
    //每个event就是一个实例，一个实例是Outcome与Context的二元组
    for(size_t i = 0; i < eventNum; ++i){ 
        size_t classId = getEventClassId(i); //该event实例对应的类 Outcome
        size_t count = getEventCount(i); //满足该event实例的(x,y)的个数
        for(DataManager::context_iterator it = getContextBegin(i),end = getContextEnd(i);
                it != end; ++it){ //遍历context的所有feature
            int fid = *it;
            int pos = getClassPosition(classId, fid); //找到mParamSet中该类的位置
            if(pos != -1)
                observed[fid][pos] += count; //统计训练数据中符合该fi的(x,y)二元组的个数，因为每个event的context包含了多个feature，所以要对特定fid进行累加
        }
    }
}

//E_q(f)，模型先验数据中符合约束条件的占比。可以理解为是训练时得到的数据。
double DataManager::getExpects(vector<vector<double> > & expected) {
    vector<double> probs;
    expected.clear();
    expected.resize(mParamSet.size());
    for(size_t i = 0; i < mParamSet.size(); ++i)
        expected[i].resize(mParamSet[i].size(), 0);
    double logLike = 0;
    for(size_t i = 0, eventNum = getEventNum(); i < eventNum; ++i){ 
        context_iterator ctxtBegin = getContextBegin(i);
        context_iterator ctxtEnd = getContextEnd(i);
        getAllProbs(ctxtBegin, ctxtEnd, probs); //
        size_t count = getEventCount(i); // 满足的个数
        size_t classId = getEventClassId(i); // 类别
        vector<double> newProbs;
        for(size_t i = 0; i < probs.size(); ++i)
        	newProbs.push_back(probs[i] * count);
        for(context_iterator it = ctxtBegin; it != ctxtEnd; ++it){
          size_t fid = *it;
          param_iterator pBegin = getParamBegin(fid);
          param_iterator pEnd = getParamEnd(fid);
          for(param_iterator pit = pBegin; pit != pEnd; ++pit){
            int pos = pit - pBegin;
            size_t cid = pit->first;
            expected[fid][pos] += newProbs[cid];
          }
				}
				logLike += log(probs[classId]) * count;
    }
   return logLike;
}

//求p(y|x)。这个条件概率可以通过简单地将所有(x,y)符合的fi和对应的参数λi乘起来后相加。 归一化因子是各个Outcome y 的p(y|x)的和。在求得p(y|x)后，要求Eq(fi)，只需要枚举所有符合fi的(x,y)对应的p(y|x)，乘以Context x 出现的次数再除以N就可以。 
size_t DataManager::getAllProbs(
        const context_iterator begin,
        const context_iterator end,
        vector<double> & probs) {
    probs.clear();
    probs.resize(mMaxCid + 1, 0);
    for(context_iterator cit = begin; cit != end; ++cit){
        size_t fid = *cit;
        for(param_iterator it = getParamBegin(fid),
                pend = getParamEnd(fid);
                it != pend; ++it){
            size_t cid = it->first; // Outcome y
            probs[cid] += it->second; //参数λi
        }
    }
    size_t maxK = 0;
    double sum = 0;
    for(size_t i = 1; i <= mMaxCid; i++){
        probs[i] = exp(probs[i]);
        sum += probs[i]; //参数λi乘起来后相加。
        if(probs[i] > probs[maxK])
            maxK = i;
    }
    for(size_t i = 1; i <= mMaxCid; ++i)
        probs[i] /= sum; //除以N
    return maxK;
}

4. Конкретный тренировочный процесс

void MaxEntTrainer::_initTrainer(void) {
    mEventNum = mModelInfo.getEventNum();
    mMaxFid = mModelInfo.getFetNum();
    mMaxCid = mModelInfo.getClassNum();
    mTotEvent = mModelInfo.getAllEventFreq();
    mModelInfo.getObserves(mObserved);
}

// Calculate the ith GIS parameter updates with Gaussian prior
// using Newton-Raphson method
// the update rule is the solution of the following equation:
//                                   lambda_i + delta_i
// E_ref = E_q * exp (C * delta_i) + ------------------ * N
//                                       sigma_i^2
// note: E_ref and E_q were not divided by N
// this function is copied from Le Zhang's work
double MaxEntTrainer::_newton(double f_q, double f_ref, double lambdaNow, double mEps)
{
    size_t maxiter = 50;
    double x0 = 0.0;
    double x = 0.0;

    for (size_t mIter = 1; mIter <= maxiter; ++mIter) {
        double t = f_q * exp(mSlowF * x0);
        double fval = t + mTotEvent * (lambdaNow + x0) / mSigma2 - f_ref;
        double fpval = t * mSlowF + mTotEvent / mSigma2;
        if (fpval == 0) {
            cerr << "Warning: zero-derivative encountered in newton() method." << endl;
            return x0;
        }
        x = x0 - fval/fpval;
        if (fabs(x-x0) < mEps)
            return x;
        x0 = x;
    }
    cerr << "Failed to converge after 50 iterations in newton() method" << endl;
    exit(-1);
}

bool GisTrainer::train() {
    vector<vector<double> > expected;
    double preLogLike = -1e10;
    for(size_t it = 0; it < mIter; ++it) {
        double newLogLike = mModelInfo.getExpects(expected);
        for(size_t i = 1; i <= mMaxFid; ++i) {
            DataManager::param_iterator begin = mModelInfo.getParamBegin(i);
            DataManager::param_iterator end = mModelInfo.getParamEnd(i);
            for(DataManager::param_iterator it = begin; it != end; ++it) {
                size_t j = it - begin;
                double inc = 0;
                if(mSigma2) {
                    inc = _newton(expected[i][j], mObserved[i][j], it->second);
                } else if(mAlpha) {
                	if(mObserved[i][j] - mAlpha <= 0)
                    	continue;
                  inc = (log(mObserved[i][j] - mAlpha) - log(expected[i][j])) / mSlowF;
                	if(it->second + inc <= 0)
                    	inc = -it->second;
                } else {
				         	inc = (log(mObserved[i][j]) - log(expected[i][j])) / mSlowF;
        				}
                mModelInfo.incLambda(i, j, inc); //更新模型参数（权重）
            }
        }
        if(fabs((newLogLike - preLogLike) / preLogLike) < mEps)
            break;
        preLogLike = newLogLike;
    }
    return true;
}

0x04 Использовать максимальную энтропию для классификации текста

Код ниже взят изМаксимальная энтропия для классификации текста, вы можете узнать из приведенного выше подтверждения.

def get_ctgy(fname):#根据文件名称获取类别的数字编号
        index = {'fi':0,'lo':1,'co':2,'ho':3,'ed':4,'te':5,
                 'ca':6,'ta':7,'sp':8,'he':9,'ar':10,'fu':11}
        return index[fname[:2]]

def updateWeight():
        #EP_post是 单词数*类别 的矩阵
        for i in range(wordNum):
            for j in range(ctgyNum):
                EP_post[i][j] = 0.0 #[[0.0 for x in range(ctgyNum)] for y in range(wordNum)]
        # prob是 文本数*类别 的矩阵，记录每个文本属于每个类别的概率
        cond_prob_textNum_ctgyNum = [[0.0 for x in range(ctgyNum)] for y in range(textNum)]
        #计算p(类别|文本)

        for i in range(textNum):#对每一个文本
                zw = 0.0  #归一化因子
                for j in range(ctgyNum):#对每一个类别
                        tmp = 0.0
                       #texts_list_dict每个元素对应一个文本，该元素的元素是单词序号：频率所组成的字典。
                        for (feature,feature_value) in texts_list_dict[i].items():
                            #v就是特征f(x,y)，非二值函数，而是实数函数，
                            #k是某文本中的单词，v是该单词的次数除以该文本不重复单词的个数。
                                #feature_weight是 单词数*类别 的矩阵，与EP_prior相同
                                tmp+=feature_weight[feature][j]*feature_value #feature_weight是最终要求的模型参数，其元素与特征一一对应，即一个特征对应一个权值
                        tmp = math.exp(tmp)
                        zw+=tmp #zw关于类别求和
                        cond_prob_textNum_ctgyNum[i][j]=tmp                        
                for j in range(ctgyNum):
                        cond_prob_textNum_ctgyNum[i][j]/=zw
        #上面的部分根据当前的feature_weight矩阵计算得到prob矩阵（文本数*类别的矩阵，每个元素表示文本属于某类别的概率），
        #下面的部分根据prob矩阵更新feature_weight矩阵。

        for x in range(textNum):
                ctgy = category[x] #根据文本序号获取类别序号
                for (feature,feature_value) in texts_list_dict[x].items(): #该文本中的单词和对应的频率
                        EP_post[feature][ctgy] += (cond_prob_textNum_ctgyNum[x][ctgy]*feature_value)#认p(x)的先验概率相同        
        #更新特征函数的权重w
        for i in range(wordNum):
                for j in range(ctgyNum):
                        if (EP_post[i][j]<1e-17) |  (EP_prior[i][j]<1e-17) :
                                continue                        
                        feature_weight[i][j] += math.log(EP_prior[i][j]/EP_post[i][j])        

def modelTest():
        testFiles = os.listdir('data\\test\\')
        errorCnt = 0
        totalCnt = 0

        #matrix是类别数*类别数的矩阵，存储评判结果
        matrix = [[0 for x in range(ctgyNum)] for y in range(ctgyNum)]
        for fname in testFiles: #对每个文件
                lines = open('data\\test\\'+fname)
                ctgy = get_ctgy(fname) #根据文件名的前两个字符给出类别的序号
                probEst = [0.0 for x in range(ctgyNum)]         #各类别的后验概率
                for line in lines: #该文件的每一行是一个单词和该单词在该文件中出现的频率
                        arr = line.split('\t')
                        if not words_dict.has_key(arr[0]) : 
                            continue        #测试集中的单词如果在训练集中没有出现则直接忽略
                        word_id,freq = words_dict[arr[0]],float(arr[1])
                        for index in range(ctgyNum):#对于每个类别
                            #feature_weight是单词数*类别墅的矩阵
                            probEst[index] += feature_weight[word_id][index]*freq
                ctgyEst = 0
                maxProb = -1
                for index in range(ctgyNum):
                        if probEst[index]>maxProb:
                            ctgyEst = index
                            maxProb = probEst[index]
                totalCnt+=1
                if ctgyEst!=ctgy: 
                    errorCnt+=1
                matrix[ctgy][ctgyEst]+=1
                lines.close()
        #print "%-5s" % ("类别"),
        #for i in range(ctgyNum):
        #    print "%-5s" % (ctgyName[i]),  
        #print '\n',
        #for i in range(ctgyNum):
        #    print "%-5s" % (ctgyName[i]), 
        #    for j in range(ctgyNum):
        #        print "%-5d" % (matrix[i][j]), 
        #    print '\n',
        print "测试总文本个数:"+str(totalCnt)+"  总错误个数:"+str(errorCnt)+"  总错误率:"+str(errorCnt/float(totalCnt))

def prepare():
        i = 0
        lines = open('data\\words.txt').readlines()
        #words_dict给出了每一个中文词及其对应的全局统一的序号，是字典类型，示例：{'\xd0\xde\xb5\xc0\xd4\xba': 0}
        for word in lines:
                word = word.strip()
                words_dict[word] = i
                i+=1
        #计算约束函数f的经验期望EP(f)
        files = os.listdir('data\\train\\') #train下面都是.txt文件
        index = 0
        for fname in files: #对训练数据集中的每个文本文件
                file_feature_dict = {}
                lines = open('data\\train\\'+fname)
                ctgy = get_ctgy(fname) #根据文件名的前两个汉字，也就是中文类别来确定类别的序号

                category[index] = ctgy #data/train/下每个文本对应的类别序号
                for line in lines: #每行内容：古迹  0.00980392156863
                        # line的第一个字符串是中文单词，第二个字符串是该单词的频率
                        arr = line.split('\t')
                        #获取单词的序号和频率
                        word_id,freq= words_dict[arr[0]],float(arr[1])

                        file_feature_dict[word_id] = freq
                        #EP_prior是单词数*类别的矩阵
                        EP_prior[word_id][ctgy]+=freq
                texts_list_dict[index] = file_feature_dict
                index+=1
                lines.close()
                
def train():
        for loop in range(4):
            print "迭代%d次后的模型效果：" % loop
            updateWeight()
            modelTest()


textNum = 2741  # data/train/下的文件的个数
wordNum = 44120 #data/words.txt的单词数，也是行数
ctgyNum = 12


#feature_weight是单词数*类别的矩阵
feature_weight = np.zeros((wordNum,ctgyNum))#[[0 for x in range(ctgyNum)] for y in range(wordNum)]

ctgyName = ['财经','地域','电脑','房产','教育','科技','汽车','人才','体育','卫生','艺术','娱乐']
words_dict = {}

# EP_prior是个12（类）* 44197（所有类的单词数）的矩阵，存储对应的频率
EP_prior = np.zeros((wordNum,ctgyNum))
EP_post = np.zeros((wordNum,ctgyNum))
#print np.shape(EP_prior)
texts_list_dict = [0]*textNum #所有的训练文本 
category = [0]*textNum        #每个文本对应的类别

print "初始化:......"
prepare()
print "初始化完毕，进行权重训练....."
train()

0x05 Марковская модель максимальной энтропии MEMM

1. Формула моделирования

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

В отличие от зависимости o HMM от i, текущее состояние MEMM зависит от предыдущего состояния и текущего наблюдения, текущее скрытое состояние i MEMM должно зависеть от наблюдаемого узла o в текущий момент и скрытого узла i-1 в предыдущий момент. Таким образом, в MEMM, учитывая последовательность наблюдений i1,...in, можно напрямую узнать условную вероятность последовательности состояний in:

P(I∣O)=∏t=1nP(ii∣ii−1,oi),i=1,...,nP(I|O) = \prod_{t=1}^n P(i_i|i_{i-1},o_i), i = 1, ...,n

А вероятность P(i|i',o) моделируется классификатором максимальной энтропии (причина названия MEMM):

P(i∣i'',o)=1Z(o,i')exp(∑aλafa(o,i))P(i|i^{''},o) = \frac{1}{Z(o,i^{'})}exp(\sum_aλ_af_a(o,i))

Эта часть Z(o,i) нормирована, f(o,i)Характеристика Функция, чтобы быть конкретным, эта функция должна быть определена. Модель MEMM позволяет напрямую ** «определять функции» **. λ — это вес характеристической функции, который является неизвестным параметром и должен быть изучен на этапе обучения.

Итак, в целом формула моделирования MEMM выглядит следующим образом:

P(I∣O)=∏t=1nexp(∑aλafa(o,i))Z(o,ii−1'),i=1,...,nP(I|O) = \prod_{t=1}^n \frac{exp(\sum_aλ_af_a(o,i))}{Z(o,i^{'}_{i-1})}, i = 1, ..., п

Причина, по которой эта часть формулы растет таким образом, определяется МЭ-моделью.

При использовании алгоритма Витерби для декодирования формула, соответствующая MEMM, имеет вид:

нt(j)=maxinнt−1(i)*P(yj∣yi,xt)1≤j≤n,1<t<Tν_t(j)= max_i^n ν_{t-1}(i)∗P(y_j∣y_i,x_t) \\ 1≤j≤n,1

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

Полный процесс:

  • шаг 1. Сначала задайте характеристическую функцию f(o,i)
  • шаг 2. На заданных данных обучаем модель и определяем параметры, то есть определяется модель MEMM
  • шаг 3. Используйте определенную модель, чтобы решить проблему маркировки последовательности или проблему вероятности последовательности.

2. MEMM vs HMM

Модель HMM непосредственно моделирует вероятность перехода состояния (состояние-состояние) и вероятность эмиссии (состояние-наблюдение), а также вычисляет вероятность совместного возникновения. Модель MEMM устанавливает совместную вероятность вероятности перехода состояния и вероятности эмиссии, а статистика представляет собой условную вероятность. Но MEMM легко попасть в локальный оптимум, потому что MEMM нормализуется только локально.

Например, для задачи аннотации «Я люблю Пекинскую площадь Тяньаньмэнь»,

       标注为" s s b e b c e"

Для HMM вероятность того, что метка установлена, равна P = P(s переносится на s)P('I' представлено как s)P(s переносится в b)P («любовь», выраженная как s)...*P().Во время обучения должны быть подсчитаны матрица вероятности перехода состояния и матрица производительности.

Для MEMM вероятность того, что эта метка установлена, равна P = P (перенос s в s | «I» представлен как s)P('I' представлено как s)P (s переносится на b | ​​«любовь» представляется как s)P («любовь», выраженная как s).. Во время обучения должны быть рассчитаны матрица вероятности перехода условного состояния и матрица производительности.

3. Сравнение кода

Следующий код взят изGitHub.com/Алекс Кардс/…

HMMTag

Ниже приведен код HMM, который рассчитывает эмиссию/транзакцию.

def predict_viterbi(x, trans_c, emiss_c, word_tags_map, interp_weights):
    """
    For each word in vector x predict his tag. Prediction is done by viterbi algorithm. Check all tags options/globally.
    :param x: X vector of words.
    :param trans_c: Transaction counts.
    :param emiss_c: Emission counts.
    :param word_tags_map: Word to tags map.
    :param interp_weights: Interpolation weights.
    :return: Vector of all tags respectively to words in vector x.
    """
    y = []
    v = [{(mle_train.START_SYMBOL, mle_train.START_SYMBOL): 0.0}]
    bp = []
    for ind, word in enumerate(x):
        # Convert word if it was'nt seen in the corpus, to signature word.
        if word not in word_tags_map:
            word = mle_train.subcategorize(word)
        # Pruning of tags to lower amount of possible tags for this word.
        available_tags = word_tags_map[word]

        max_score = {}
        max_tags = {}
        # Calculate for each word best scores/probabilities and best tags for each word.
        for pp_t, p_t in v[ind]:
            for curr_tag in available_tags:
                score = get_score(word, curr_tag, p_t, pp_t, trans_c, emiss_c, interp_weights)
                score += v[ind][(pp_t, p_t)]

                if (p_t, curr_tag) not in max_score or score > max_score[(p_t, curr_tag)]:
                    max_score[(p_t, curr_tag)] = score
                    max_tags[(p_t, curr_tag)] = pp_t

        v.append(max_score)
        bp.append(max_tags)
    # Calculate last 2 best tags.
    max_score = float("-inf")
    prev_last_tag, last_tag = None, None
    for prev_t, curr_t in v[len(x)]:
        score = v[len(x)][(prev_t, curr_t)]
        if score > max_score:
            max_score = score
            last_tag = curr_t
            prev_last_tag = prev_t
    y.append(last_tag)
    if len(x) > 1:
        y.append(prev_last_tag)

    prev_t = last_tag
    prev_prev_t = prev_last_tag
    # By backtracking extract all the path of best tags for each word starting by last 2 tags we calculated above.
    for i in range(len(v) - 2, 1, -1):
        curr_t = bp[i][(prev_prev_t, prev_t)]
        y.append(curr_t)
        prev_t = prev_prev_t
        prev_prev_t = curr_t
    # Reverse the path.
    y = reversed(y)
    return y
  
def get_score(word, curr_tag, p_t, pp_t, trans_c, emiss_c, interp_weights):
    """
    Calculate probability. Prob = e_prob + q_prob.
    :param word: Curr word.
    :param curr_tag: Curr tag.
    :param p_t: Previous tag.
    :param pp_t: Previous of previous tag.
    :param trans_c: Transaction counts.
    :param emiss_c: Emission counts.
    :param interp_weights: Interpolation weights.
    :return:
    """
    e = mle_train.get_e(word, curr_tag, emiss_c, trans_c)
    q = mle_train.get_q(pp_t, p_t, curr_tag, trans_c, interp_weights)
    if e != 0 and q != 0:
        score = math.log(e) + math.log(q)
    else:
        score = float('-inf')
    return score  
  
def get_e(word, tag, emiss_c, trans_c):
    """
    Calculate e probability.
    :param word: Current word to analyze.
    :param tag: Current tag to analyze.
    :param emiss_c: Emission counts.
    :param trans_c: Transaction counts.
    :return: Probability value.
    """
    key = '{} {}'.format(word, tag)
    count_word_tag = float(emiss_c.get(key, 0))
    key = '{}'.format(tag)
    count_tag = float(trans_c.get(key, 0))
    try:
        e_prob = count_word_tag / count_tag
    except ZeroDivisionError:
        e_prob = 0

    return e_prob


def get_q(pp_t, p_t, curr_tag, trans_c, interpolation_weights):
    """
    Calculate q probability.
    :param pp_t: Previous of previous tag to analyze.
    :param p_t: Previous tag to analyze.
    :param curr_tag: Current tag to analyze.
    :param trans_c: Transaction counts.
    :param interpolation_weights: Interpolation weight.
    :return:
    """
    lambda_1 = interpolation_weights[0]
    lambda_2 = interpolation_weights[1]
    lambda_3 = interpolation_weights[2]
    # Calculate trigram prob = count_trigram_abc / count_bigram_ab
    key = '{} {} {}'.format(pp_t, p_t, curr_tag)
    count_trigram_abc = float(trans_c.get(key, 0))
    key = '{} {}'.format(pp_t, p_t)
    count_bigram_ab = float(trans_c.get(key, 0))
    try:
        trigram_prob = count_trigram_abc / count_bigram_ab
    except ZeroDivisionError:
        trigram_prob = 0
    # Calculate bigram prob = count_trigram_bc / count_unigram_b
    key = '{} {}'.format(p_t, curr_tag)
    count_bigram_bc = float(trans_c.get(key, 0))
    key = '{}'.format(p_t)
    count_unigram_b = float(trans_c.get(key, 0))
    try:
        bigram_prob = count_bigram_bc / count_unigram_b
    except ZeroDivisionError:
        bigram_prob = 0
    # Calculate unigram prob = count_unigram_c / num_words
    key = '{}'.format(curr_tag)
    count_unigram_c = float(trans_c.get(key, 0))
    key = '{}'.format(NUM_WORDS_SYMBOL)
    num_words = float(trans_c.get(key, 0))
    try:
        unigram_prob = count_unigram_c / num_words
    except ZeroDivisionError:
        unigram_prob = 0
    # Apply interpolation weight on the probabilities.
    interpolation = lambda_1 * trigram_prob + lambda_2 * bigram_prob + lambda_3 * unigram_prob
    return interpolation

MEMMTag

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

def predict_viterbi(x, f_map, tags_s, word_t_map, lib_model):
    """
    For each word in vector x predict his tag. Prediction is done by viterbi algorithm. Check all tags options/globally.
    :param x: X vector of all words to be tagged.
    :param f_map: Features map.
    :param tags_s: Tags set.
    :param word_t_map: Word to tags map.
    :param lib_model: Liblinear model.
    :return: Return best predicted list of tags for each word in x respectively.
    """
    y = []
    v = [{(extract.START_SYMBOL, extract.START_SYMBOL): 0.0}]
    bp = []
    for ind, word in enumerate(x):
        # Check if word was seen in the corpus.
        if word not in word_t_map:
            is_rare = True
            available_tags = tags_s
        else:
            is_rare = False
            # Pruning of tags to lower amount of possible tags for this word.
            available_tags = word_t_map[word]

        max_score = {}
        max_tags = {}
        # Calculate for each word best scores/probabilities and best tags for each word.
        for pp_t, p_t in v[ind]:
            for curr_tag in available_tags:
                # 一个word对应的feature列表，可能的tag列表
                word_features = extract.generate_word_features(is_rare, p_t, pp_t, word, ind, x)
                features_vec = features_to_vec(word_features, f_map)
                scores = lib_model.predict(features_vec)
                score = np.amax(scores)
                if (p_t, curr_tag) not in max_score or score > max_score[(p_t, curr_tag)]:
                    max_score[(p_t, curr_tag)] = score
                    max_tags[(p_t, curr_tag)] = pp_t

        v.append(max_score)
        bp.append(max_tags)
    # Calculate last 2 best tags.
    max_score = float("-inf")
    prev_last_tag, last_tag = None, None
    for prev_t, curr_t in v[len(x)]:
        score = v[len(x)][(prev_t, curr_t)]
        if score > max_score:
            max_score = score
            last_tag = curr_t
            prev_last_tag = prev_t

    y.append(last_tag)
    if len(x) > 1:
        y.append(prev_last_tag)

    prev_t = last_tag
    prev_prev_t = prev_last_tag
    # By backtracking extract all the path of best tags for each word starting by last 2 tags we calculated above.
    for i in range(len(v) - 2, 1, -1):
        curr_t = bp[i][(prev_prev_t, prev_t)]
        y.append(curr_t)
        prev_t = prev_prev_t
        prev_prev_t = curr_t
    y = reversed(y)
    return y

Извлечь функции

def load_model(feature_map_fname):
    """
    Load the model from features map file.
    :param feature_map_fname: Features map file name.
    :return: Tags set, index to tag map, word to tags map and features map.
    """
    features_map = defaultdict(int)
    ind_to_tags_map = defaultdict(str)
    tags_set = set()
    word_to_tags_map = defaultdict(set)

    with open(feature_map_fname, 'r') as f:
        all_data = f.readlines()
    # Booleans to separate the reading process from the file.
    is_features_section = False
    is_words_to_tags_section = False
    is_tags_section = True
    for ind, line in enumerate(all_data):
        line = line.strip()
        if line == '^':
            is_words_to_tags_section = True
            is_tags_section = False
            continue
        if line == '^^':
            is_features_section = True
            is_words_to_tags_section = False
            continue
        if is_tags_section:
            key, value = line.split()
            tags_set.add(key)
            ind_to_tags_map[int(value)] = key
        if is_words_to_tags_section:
            key, value = line.split('^')
            word_to_tags_map[key] = value.split() # 该word可能对应的tag: 动词，名词......
        if is_features_section:
            key, value = line.split()
            features_map[key] = int(value) # load事先定义好的特征，有 string 和 int两种表示方法
    return features_map, tags_set, ind_to_tags_map, word_to_tags_map

# ExtractFeatures.py, MMEMTag.predict_viterbi会调用
def generate_word_features(is_rare, p_t, pp_t, curr_word, word_ind, words):
    """
    Generate for current word list of features as listed on table one.
    :param is_rare: Boolean that corresponds to type of the word. Rare or not.
    :param p_t: Previous tag.
    :param pp_t: Previous of previous tag.
    :param curr_word: Current word.
    :param word_ind: Current word index.
    :param words: List of all words in the sentence.
    :return: List of all word features.
    """
    word_features = []
    # Check if word is rare.
    if is_rare:
        # Generate the suffixes and prefixes depends on min of (word length or 4).
        for i in range(1, min(5, len(curr_word))):
            word_features.append('prefix' + str(i) + '=' + curr_word[:i]) # 前面的字
        for i in range(1, min(5, len(curr_word))):
            word_features.append('suffix' + str(i) + '=' + curr_word[-i:]) # 后面的字
        # Check with regex if word contains digit.
        if re.search(r'\d', curr_word):
            word_features.append('has_digit=true') # 是不是数字
        # Check with regex if word contains upper case letter.
        if re.search(r'[A-Z]', curr_word):
            word_features.append('has_upper_letter=true') # 大写开头
        # Check if word contains hyphen symbol.
        if '-' in curr_word: 
            word_features.append('has_hyphen=true') # 有破折号
    else:
        # Otherwise word is not rare and this word as feature.
        key = 'form={}'.format(curr_word) 
        word_features.append(key)
    # Generate previous tags.
    key = 'pt={}'.format(p_t)
    word_features.append(key)
    key = 'ppt={}^{}'.format(pp_t, p_t)
    word_features.append(key)
    # Generate next words and words that appeared before in the sentence.
    if word_ind > 0:
        key = 'pw={}'.format(words[word_ind - 1])
        word_features.append(key)
    if word_ind > 1:
        key = 'ppw={}'.format(words[word_ind - 2])
        word_features.append(key)
    if word_ind < len(words) - 1:
        key = 'nw={}'.format(words[word_ind + 1])
        word_features.append(key)
    if word_ind < len(words) - 2:
        key = 'nnw={}'.format(words[word_ind + 2])
        word_features.append(key)
    return word_features # word对应的，用string表示的，特征名字列表

# MEMMTag.py
def features_to_vec(word_features, f_map):
    """
    Convert word features to vector of features indexes whose liblinear model can understand.
    :param word_features: Word features to convert.
    :param f_map: Features map.
    :return: Vector of features.
    """
    features_vec = []
    for feature in word_features:
        if feature in features_map:
            features_vec.append(f_map[feature])

    features_vec = sorted(features_vec)
    return features_vec

логистическая регрессия

LibLinear, простой пакет для решения крупномасштабной регуляризованной линейной классификации и регрессии.

  • nr_class: количество классов, если это регрессия, то это число равно 2.
  • nr_feature: размер выборки обучающих данных (исключая смещение).
  • смещение: если смещение >= 0, мы добавляем дополнительную функцию в конце каждого образца.
  • Метка: метка каждого класса для регрессии, нулевая.
  • w: nr_w x nвесовая матрица. n — это nr_feature (размер объекта) или nr_feature+1 (при наличии смещения). Если nr_class=2 и -s не равно 4 (не мультиклассовая SVM Crammer и Singer), то nr_w равно 1, для других случаев nr_w равно nr_class.
  • гдеРазмер объекта x количество категорий, что соответствует вышеупомянутому «с точки зрения модели максимальной энтропии, n признаков каждого входа и k категорий вместе образуют nk признаков, и в модели есть nk весов, которые соответствуют признакам один за другим. Каждый Категория запускает n" из nk функций.

Конкретный код:

class LiblinearLogregPredictor(object):
  def __init__(self, model_file_name):
        # dict of feat-num -> numpy array, where array is the per-class values
        self.weights = {}
        with open(model_file_name) as fh:
            solver_type = fh.next().strip()
            nr_classes = fh.next().strip()
            label = fh.next().strip()
            nr_feature = fh.next().strip()
            bias = fh.next().strip()
            w = fh.next().strip()
            assert(w == "w")
            assert(nr_classes.startswith("nr_class"))
            assert(nr_feature.startswith("nr_feature"))
            assert(label.startswith("label"))
            nr_classes = int(nr_classes.split()[-1])
            for i, ws in enumerate(fh, 1):
                ws = [float(x) for x in ws.strip().split()]
                # skip unused features
                if all([x == 0 for x in ws]):
                    continue
                assert len(ws) == nr_classes, "bad weights line %s" % ws
                self.weights[i] = np.array(ws)
            self.bias = float(bias.split()[-1])
            self.labels = label.split()[1:]

    # feature_ids是int类型的特征列表，weights是权值矩阵
    def predict(self, feature_ids): 
        weights = self.weights
        scores = np.zeros(len(self.labels))
        for f in feature_ids:
            if f in weights:
                scores += weights[f]
        scores = 1/(1+np.exp(-scores))
        scores = scores/np.sum(scores)
        return scores

0x06 Продолжение применения Water Margin

После стольких ворчаний я наконец добрался до примера приложения. Возьмем в качестве примера «прорыв Лян Чжуншу из особняка Дамин». См. выше [Народный анализ] Использование запаса воды в качестве примера для изучения скрытой марковской модели..

Модель скрытой марковской модели относительно проста, но в реальности ситуация может быть сложнее.Например, когда Лян Чжуншу прорвался и встретился с Сун Цзяном, вероятность того, что он снова решит прорваться от Сун Цзяна, будет ниже, потому что Сун Цзян должен быть окружен большинством героев в Ляншане, и прорваться через него сложно, слишком большой. Но если вы столкнетесь с Ши Цзинем, опасность не так велика.

Теперь, когда алгоритм доступен, он фактически зависит от того, как построить характеристическую функцию. Как видно из предыдущего кода, операция получения признака, соответствующего слову, выглядит следующим образом

word_features = extract.generate_word_features(is_rare, p_t, pp_t, word, ind, x)
features_vec = features_to_vec(word_features, f_map)
scores = lib_model.predict(features_vec)

Мы строим различную сопутствующую информацию

*********************** 特征函数
f_1 = 是不是梁山总头领
f_2 = 是不是打虎英雄
f_3 = 是不是五虎将
f_4 = 是不是八骠骑

*********************** 下一次突围的门（ 对应词性标注中的tag ）
t_1 = 逆时针上一门
t_2 = 当前门
t_3 = 顺时针下一门
t_3 = 对门
  
*********************** 好汉（ 对应词性标注中的word ） 
h_1 = 林冲
h_2 = 武松
h_3 = 史进
h_3 = 宋江
  
*********************** 遇见好汉的序列（ 对应词性标注中的句子 ）  
武松，宋江，史进，林冲

Матрица весов Измерение функции признаков x Количество категорий, это значение выдумывается произвольно

весовая матрица={12141818141218181818121418181412}весовая матрица = \left\{ \begin{matrix} \frac12 & \frac14 & \frac18 & \frac18\\ \frac14 & \frac12 & \frac18 & \frac18\\ \frac18 & \frac18 & \frac12 & \frac14\ \ \frac18 & \frac18 & \frac14 & \frac12\\ \end{matrix} \right\}

Алгоритм можно ввести в расчет.

Ну, собственно, в этот раз описание приложения меньше ^_^.

0xEE Личная информация

★★★★★★Думая о жизни и технологиях★★★★★★

Публичный аккаунт WeChat:мысли Росси

Если вы хотите получать своевременные новости о статьях, написанных отдельными лицами, или хотите видеть технические материалы, рекомендованные отдельными лицами, обратите внимание.

ссылка 0xFF

Принцип максимальной энтропии

Глубина | Объединение логистической регрессии для построения максимальной энтропийной марковской модели

Система вероятностных графических моделей: HMM, MEMM, CRF

blog.CSDN.net/Aston посылает сатану посылает сатану…

Марковская модель максимальной энтропии (MEMM) Марковская модель максимальной энтропии Воплощение максимальной энтропии

Смещение маркера Скрытое Марковское максимальное значение энтропии Марковское HMM MEMM

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

Обработка естественного языка 4 — Марковская модель с максимальной энтропией (MEMM)

Примечания к изучению модели алгоритма сегментации слов (2) - MEMM

Изучение алгоритма CRF - самостоятельно реализовать простую сегментацию слов CRF (java)

GitHub.com/1000-7/Сина…

Как понять шаблон функции в crf++?

Лекция 5 Массачусетского технологического института по обработке естественного языка: максимальная энтропия и лог-линейные модели (часть II)

NLP-Maximum-entropy Markov model

Hidden Markov model vs. Maximum-entropy Markov model

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

Математический вывод в модели максимальной энтропии

GitHub.com/Hankucangshan/макс Э…

Максимальная энтропия для классификации текста

Говоря об особенностях модели максимальной энтропии

Простая реализация модели максимальной энтропии

Как объяснить итерационный метод Ньютона простым для понимания способом?

Как понять особенности в модели максимальной энтропии?

Серьезная путаница с моделями максимальной энтропии: почему нет аналитического решения?

От логистической регрессии к моделям максимальной энтропии

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

Машинное обучение — модель максимальной энтропии

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

[Принцип максимальной энтропии](woo woo woo.cn blog on.com/snowball begging/ah…)

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

Изучение алгоритма CRF - самостоятельно реализовать простую сегментацию слов CRF (java)

Категории