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

0x00 сводка

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

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

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

0x01 HMM Скрытый Марков

Прежде всего, вам все еще нужно представить HMM и MEMM, чтобы вы могли знать, почему вводится CRF.

Среди них HMM упоминается в предыдущем [Народный анализ] Использование запаса воды в качестве примера для изучения скрытой марковской модели.Также подробно в. Здесь мы в основном говорим о процессе его получения и его недостатках.

1. Модель ХММ

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

В однократной задаче наивной байесовской классификации (где x — наблюдение, а y — скрытое состояние):

P(y|x)=\frac{P(x|y)*P(y)}{P(x)}

Расширение задачи классификации серийных образцов:

P (y_1 ^ n ∣x_1 ^ n) = \ frac {P (x_1 ^ n ∣y_1 ^ n) * P (y_1 ^ n)} {P (x_1 ^ n)}

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

Мы объясним позже с проблемой сериализации классификации тегов части речи. Для данного предложения x_i^n=(x_1,x_2,...,x_n) наша цель состоит в том, чтобы найти для него последовательность меток с наивысшей оценкой (yˆ1,yˆ2,...,yˆn), после чего задача преобразуется в:

\ шляпа y_1 ^ n = arg_ {y_1 ^ n} \ max \ frac {P (x_1 ^ n∣y_1 ^ n) * P (y_1 ^ n)} {P (x_1 ^ n)}

Для маркировки одного и того же предложения знаменатель тот же, поэтому задачу можно преобразовать в:

\ шляпа y_1 ^ n = arg_ {y_1 ^ n} \ max P (x_1 ^ n∣y_1 ^ n) * P (y_1 ^ n)

Напомним формулу совместного распределения

P(X = x \ and \ Y = y) = \ P(Y=y|X=x)P(X=x) = \ P(X=x|Y=y)P(Y=y)

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

Теперь нам нужно ввести два основных предположения HMM, чтобы рассчитать P:

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

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

Эти два допущения можно использовать для вычислений соответственно.

Предположение 1 \ для решения \ текущее состояние \ P(y_1^n) \\ Предположение 2 \ для решения \ текущее наблюдение \ P(x_1^n∣y_1^n)

В исходном случае рассчитано по модели ориентированного графа:

P(y_1^n)=P(y_1)∗P(y_2∣y_1)∗P(y_3∣y_1,y_2)∗...∗P(y_n∣y_1,y_2,...,y_{n−1} )

Давайте положимПредположение 1Для решения метод расчета становится:

P(y_1^n)=P(y_1)∗P(y_2∣y_1)∗P(y_3∣y_2)∗...∗P(y_n∣y_{n−1})

в соответствии сПредположение 2, текущее значение наблюдения связано только с текущим состоянием и не имеет ничего общего с другими временными состояниями и наблюдениями, поэтому

P(x_1^n∣y_1^n)=P(x_1∣y_1)∗P(x_2∣y_2)∗...∗P(x_n∣y_n)

который

Предположение 1Вероятность перехода получена с использованием биграммного приближения.
Предположение 2Получена вероятность эмиссии.

В итоге объединили:

\ шляпа y_1 ^ n = arg \ max_ {y_1 ^ n} ∏_ {t = 1} ^ nP (x_t∣y_t) * P (y_t∣y_ {t−1})

Процесс обучения HMM заключается в изучении этих двух матриц вероятностей в обучающем наборе.(размер (y, y), (x, y))

2. Каковы недостатки HMM

HMM имеет следующие недостатки:

Во многих сериализованных задачах маркировки, особенно когда наблюдения не могут быть пронумерованы, требуется большое количество признаков, чтобы охарактеризовать последовательность наблюдений. Например, при распознавании невидимого названия компании при распознавании текста, в дополнение к традиционному методу распознавания слов, необходимо использовать много характерной информации, такой как заглавные буквы, окончания слов, части речи и т. д. То есть нам нужно параметризовать наблюдения с признаками, а сами наблюдения напрямую используются в HMM.
В задаче распознавания именованных сущностей из-за сложности структуры самой сущности зачастую невозможно использовать простые функции признаков для охвата всех признаков, в то время как допущение НММ делает невозможным использование сложных признаков ( он не может использовать более одной характеристики маркера).
Во многих задачах обработки естественного языка проблема, которую необходимо решить, состоит в том, чтобы решить последовательность состояний, когда последовательность наблюдений известна HMM принимает генеративное совместное распределение вероятностей P (x_1 ^ n, y_1 ^ n) для решения условной вероятности P( y_1^n|x_1^n), этот метод не подходит для работы со многими признаками, описывающими последовательность наблюдений. Для этой цели MEMM напрямую использует модель условной вероятности P(y_1^n|x_1^n).

0x02 MEMM

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

Среди них модель максимальной энтропии описана в предыдущей [Народный анализ] Объясните модель максимальной энтропии простыми словами.а также [Народный анализ] Изучение марковской модели максимальной энтропии с запасом воды в качестве примератакже вводится.

Предполагая, что распределение дискретной случайной величины x есть P(x), энтропия по отношению к распределению P определяется как:

H(P) = -\sum_xP(x)logP(x)

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

Учитывая дискретную случайную величину [公式] иВ условном распределении вероятностей P (y | x) условная энтропия, определенная в условном распределении вероятностей, равна:

H(P) = -\sum_{x,y}\hat{P}(x)P(y|x)logP(y|x)

Среди них p̃(x) — это эмпирическое распределение энтропии выборки в обучающем наборе, то есть частотная статистика каждого значения x, появляющегося в выборке.

Модель максимальной энтропии состоит в том, чтобы узнать подходящее P (y | x) при условии «удовлетворения предварительным ограничениям», чтобы значение условной энтропии H (P) было максимальным.

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

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

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

Марковская модель с максимальной энтропией использует характеристики дискриминантной модели, чтобы непосредственно установить классификатор для состояния в каждый момент времени, а затем перемножить значения вероятности всех классификаторов вместе. Достичь — значит классифицировать всю последовательность. В каждый момент времени t его характеристики исходят не только из текущего наблюдения x_t, но и из предыдущего значения состояния y_{t−1}. Следовательно, в MEMM при заданной последовательности наблюдений i1,...in можно напрямую узнать условную вероятность последовательности состояний in. это

Следующее скрытое состояние Y + 1 HMM определяется только текущим скрытым состоянием метки Y.
Следующее скрытое состояние Y + 1 MEMM определяется только текущим состоянием скрытой метки Y и состоянием наблюдения X.

Проблема маркировки последовательности с MEMMОн определяется как, учитывая последовательность наблюдений x_1 ^ n, решить определенную последовательность состояний y_1 ^ n и сделать условную вероятность максимальной, а условная вероятность удовлетворяет гипотезе Маркова, то есть условная вероятность зависит от текущего состояния наблюдения и предыдущее состояние метки на данный момент:

P(y_1^n|x_1^n) = \prod_{t=1}^n P(y_t|y_{t-1},x_t)

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

Среди них для возможного значения состояния y_{t−1} предыдущего момента и текущего значения наблюдения x_t,Вероятность того, что текущее состояние примет значение y_tСмоделирован классификатором максимальной энтропии как:

P(y_t|y_{t-1},x_t) = \frac{1}{Z(x_t,y^t)}exp(\sum_aλ_af_a(x_t,y_{t-1}))

Среди них a, λ_a, f_a соответственно представляют количество функций признаков, вес функций признаков и a-ю функцию признаков, и эта часть Z() является нормализацией.

3. Каковы недостатки MEMM

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

Вот распространенное утверждение в Интернете:

Текущее состояние S1 Предположим, что следующее состояние S2 имеет два варианта выбора: один p, а другой c. После локальной нормализации вероятность перехода * вероятность излучения p относительно велика по сравнению с c со многими переходными состояниями выхода, потому что состояние выхода p относительно мало, что делает модель более склонной к выбору состояния p.

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

# 以下就是MEMM的viterbi算法

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.
    """
    for ind, word in enumerate(x):
        # 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_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

# 预测代码，可以修改这个以测试  
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

#把上述代码修改下，自己传入feature或者直接传入weight就知道了。
#比如分别传入weight 
#[1, 2, 6, 1, 2]
#[1, 2, 9]
#就会发现，如果传入的列表中item的个数越少，则np.amax(scores)越大。

#所以这就与之前的论断相一致：
#经过局部归一化之后，因为 状态 p 的转出状态比较少，导致 “转移概率 x 发射概率” 相对于转出状态多的 状态 c 而言是比较大的，这会使模型倾向于更多的选择 状态 p 。

#其实 S2 选择 p 节点还是 c 节点只取决于 P(p|S1)、P(c|S1)，即只与 “S1” 的上下文有关，与 “S2” 的上下文无关，这就是MEMM产生偏置的一种情况。

Поскольку у MEMM есть недостатки, люди ввели CRF. Существенное различие между CRF и моделью максимальной энтропии состоит в том, что модель максимальной энтропииКаждое состояние имеет вероятностную модель, которая нормализуется при каждом переходе состояния.. Если состояние имеет только одно последующее состояние, то вероятность перехода из этого состояния в последующее состояние равна 1. Таким образом, он переходит в это последующее состояние независимо от ввода. А CRF состоит в том, чтобы установить единую модель вероятности для всех состояний, так что при нормализации, даже если состояние имеет только одно последующее состояние, его вероятность перехода в последующее состояние не будет равна 1, тем самым решая проблему «смещения метки».

0x03 Знания, связанные с CRF

1. Что такое поле

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

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

Ниже приведено объяснение «поля», которое я нашел в Интернете или где-либо еще. Надеюсь, это поможет вам понять.

Пояснение 1

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

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

Пояснение 2

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

2. Случайное поле

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

举梁山为例子：
  
比如梁山好汉一起去聚义厅开会。
每把椅子是一个位置。给每个椅子赋予一个好汉。这个好汉如何分配? 
每次从梁山上各个小团体(三山派，浔阳帮，宋江嫡系......)中随机取出一人安排到椅子上。

3. Марковское случайное поле

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

Вероятностная модель неориентированного графа:Существует совместное распределение вероятностей P(Y), которое представлено неориентированным графом G=(V,E), в графе G узлы представляют случайные величины, а ребра представляют зависимости между случайными величинами. Если совместное распределение вероятностей P(Y) удовлетворяет попарному, локальному или глобальному марковскому свойству, то совместное распределение вероятностей называется вероятностной неориентированной графической моделью или марковским случайным полем. Давайте введем три понятия по отдельности:

Попарно Марков: две несмежные переменные условно независимы при всех остальных переменных. Это связано с тем, что у двух узлов нет прямого пути, а на всех других путях есть определенные узлы наблюдения, поэтому эти пути также будут заблокированы. На самом деле это означает, что любые два узла без непосредственно соединенного ребра независимы.
локальное марковское свойство: Учитывая все смежные переменные w переменной v, переменная v условно независима от других переменных o. То есть, учитывая значение соседних переменных переменной, значение переменной не будет зависеть от других переменных. То есть значение v связано только со всеми соседними переменными w.
глобальное марковское свойство: пусть наборы узлов A и B будут произвольными наборами узлов, разделенными набором узлов C в неориентированном графе G, как показано на следующем рисунке. Глобальное марковское свойство означает, что x_A и x_B условно независимы при заданном x_C. То есть, когда A и B разделены C, A и B условно независимы, и тогда говорят, что глобальный Марков выполнен.

A ------ C ------- B

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

Следовательно, разложение совместного распределения вероятностей должно быть таким, чтобы xi и xj не попадали в одно и то же разбиение, чтобы все возможные распределения вероятностей, принадлежащие этому графу, удовлетворяли свойству условной независимости. Пусть несмежные переменные не появляются в одном разделе, то есть узлы в каждом разделе полностью связаны. Это приводит нас к понятию графа, клики.

4. Самая большая группа

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

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

比如梁山好汉一起去聚义厅开会。你就会发现，同一个小集团的人会主动聚在一起。

比如打虎将李忠就必然在三山帮这一个小集团中。而九尾龟陶宗旺则必然在黄门山（摩云金翅欧鹏、神算子蒋敬、铁笛仙马麟、九尾龟陶宗旺）小集团中。

李忠和陶宗旺两个人在私下不会有什么交集。而黄门山这四人，每个人和每个人之间都是全联接，都互相熟悉。

如果往黄门山四人中加入其他任何一个梁山好汉之后变成五人团体，则这个五人团体就不再算是黄门山这个小集团了。所以黄门山四人就是极大团。

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

5. Возможная функция

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

математическое определение

Для данной вероятностной модели неориентированного графа пусть ее неориентированным графом будет G, C — наибольшая клика на G, а Y_C — случайная величина, соответствующая C (все узлы наибольшей клики).

φ(Y_C) — это совместная вероятность случайных величин в максимальной клике C, которая используется для моделирования связи между переменными в клике C и является функцией, определяющей распределение вероятностей.

φ(Y_C) называется «потенциальной функцией», соответствующей клике C. В общем, вы определяете потенциальную функцию для каждой максимальной клики в графе.

Конкретные формы

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

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

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

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

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

Для потенциальной функции давайте поймем это по-другому и определим потенциальную функцию как экспоненциальную функцию.

φ_C(Y_C) = ехр \{-E(Y_C)\}

Таким образом, p(x) может быть выражена как экспоненциальная форма суммы ряда E(Yc). E(Yc) называется функцией возможностей.

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

比如梁山上，有各种小团体。每一个团体对应一个势函数。
比如 生辰纲七人组，登州帮，三山帮，揭阳帮，降将帮，大名府帮，黄门山帮，清风山....
  
那么梁山就可以理解为一个能力的集合，他的值就等于各个小团体能量的和。
CRF就是要最小化这些能量，这样梁山才能稳定，最好能均匀分布，这样熵就达到了最大值。

6. Характеристическая функция

Собственные функции — это некоторые эмпирические свойства, и мы используем собственные функции для представления ограничений. Характеристическая функция в предыдущем тексте[Вернакулярный анализ] Изучение марковской модели максимальной энтропии на примере запаса водыТакже подробно.

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

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

В CRF функция представляет собой набор свидетельств, связывающих наблюдаемое нами d с классом c, который мы хотим предсказать. Функция представляет собой функцию f в реальном диапазоне. Как выражаются эти характеристики? Есть две характеристики:

Одним из них является функция перехода, которая включает функцию между двумя состояниями.
Другая функция — это простая функция состояния, то есть функция, которая включает только текущее состояние.

Форма выражения функции относительно проста, то есть удовлетворяете ли вы конфигурации, упомянутой моей функцией, она равна 1, если это так, и 0, если это не так.

Модель присваивает вес каждой функции, и последнее, что нам нужно узнать, это эти веса:

Положительные веса указывают на то, что структура, вероятно, правильная.
Положительные веса указывают на то, что эта структура, вероятно, неверна.

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

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

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

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

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

func1 = if (output = B-NP and feature="U01:DT") return 1 else return 0
func2 = if (output = I-NP and feature="U01:DT") return 1 else return 0
func3 = if (output = O and feature="U01:DT") return 1 else return 0
...
funcXX = if (output = B-NP and feature="U01:NN") return 1 else return 0
funcXY = if (output = O and feature="U01:NN") return 1 else return 0

Шаблон функции признаков генерирует L x N функций признаков, где L — количество случаев выходного класса, а N — количество всех возможных случаев расширенного признака.

7. Вероятностная модель неориентированного графа Совместное распределение вероятностей

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

Для функции распределения вероятностей мы также надеемся сделать то же самое, т. е. для модели вероятностного неориентированного графа пусть неориентированным графом будет G, C — наибольшая клика на G, а YC — случайная величина, соответствующая С. Тогда совместное распределение вероятностей P(Y) вероятностной модели неориентированного графа можно разложить в виде произведения функций ΨC(YC) по всем максимальным кликам C в графе.

Подводя итог, мы получаемТеорема Хаммерсли-Клиффорда, то совместное распределение вероятностей P(Y) всей модели вероятностного неориентированного графа может быть записано как произведение потенциальной функции φ(Y_C) на всех наибольших группах C в графе. который

P(Y) = \frac{1}{Z}\prod_Cφ_C(Y_C) \\Z = \sum_Y\prod_Cφ_C(Y_C)

Среди них C — наибольшая клика неориентированного графа, YC — случайная величина, соответствующая узлу C, ΨC(YC) — строго положительная функция, определенная на C, а произведение выполняется на всех наибольших кликах графа C. неориентированный граф. Z представляет собой коэффициент нормализации, гарантирующий, что P(x) является вероятностью правильного определения.

Другой способ думать о самой большой группе

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

Личное понимание таково: потому что crf хочет рассчитать совместное распределение вероятностей всей последовательности тегов Y вместо определения распределения следующего состояния с учетом текущего состояния. Но с точки зрения каждого узла трудно поддерживать согласованность условной вероятности. Поэтому самая большая группа выбирается как самостоятельная малая группа.

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

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

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

8. С точки зрения запаса воды

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

三山帮指的是二龙山、桃花山和少华山。这个派系一共13人，头领是鲁智深。下面人是：二龙山的鲁智深、杨志、武松、施恩、曹正、张青和孙二娘；桃花山的周通、李忠；少华山的史进、朱武、陈达，杨春。
  
定义特征函数如下  
*********************** 特征函数 之 节点属性
s_1 = 是不是倒拔垂杨柳的僧人
s_2 = 是不是打虎英雄
s_3 = 是不是黑旋风  
s_4 = 是不是五虎将  
s_5 = 是不是八骠骑
s_6 = 是不是小彪将  
s_7 = 是不是一同参赞军务头领  
s_8 = 是不是步军将校一十七员
s_9 = ......

  
*********************** 特征函数 之 边属性  
t_1 = 是不是亲兄弟
t_2 = 是不是叔侄
t_3 = 是不是夫妻
t_4 = 是不是表亲  
t_5 = 是不是师徒
t_6 = 是不是主仆  
t_7 = 是不是曾经共过生死
t_8 = 是不是一起经历过尴尬事
t_9 = 是不是同乡
t_10 = 是不是 "聚会之前就是结拜兄弟" 
t_11 = 是不是同僚  
t_12 = 是不是有同地工作经历    
t_13 = ...... 

定义势函数如下：
*********************** 势函数  
φ = λ1t1 + λ2t2 + λ3t3 + λ4t4 + λ5f5 + ...... + w1t1 + w2t2 + w3t3 + w4t4 + w5t5 + ...... 
  
计算结果如下：
*********************** 计算结果  
s_1 = 鲁智深 ————————————— 倒拔垂杨柳的僧人
s_2 = 武松 ——————————————— 打虎英雄
s_3 = 0
s_4 = 0  
s_5 = 杨志 史进 ——————————— 八骠骑
s_6 = 陈达，杨春，周通 ——————  小彪将
s_7 = 朱武 ————————————————   一同参赞军务头领
s_8 = 李忠，施恩———————————— 步军将校一十七员
......
  
t_1 = 0
t_2 = 0
t_3 = 张青&孙二娘 —————————— 夫妻
t_4 = 0  
t_5 = 0
t_6 = 0  
t_7 = 武松&施恩, 鲁智深&史进, 史进&朱武&陈达&杨春, 武松&张青&孙二娘, 杨志&鲁智深&曹正 ———— 共生死
t_8 = 鲁智深&李忠&周通 ———— 共尴尬
t_9 = 张青&孙二娘&施恩&曹正(河南)，杨志&杨春(山西)，周通&武松(山东)，朱武&李忠(定远县) ———— 老乡
t_10 = 武松&施恩, 鲁智深&史进, 史进&朱武&陈达&杨春, 武松&张青&孙二娘, 周通&李忠  ———— 老兄弟
t_11 = 0  
t_12 = 鲁智深&杨志&史进 (都有延安府相关履历)     
t_13 = ......    
  
  
这里如果按照影响力计算，则 s_1 ~ s_7，t_3，t_7 的权重都相当大。
由此可见三山帮的势函数有多大，有猛人，有帮闲，有主将，有副将，有马军，有步兵，甚至还有军师。他们彼此之间关系则是盘根错节。
其在梁山内部绝对是第二大势力。

0x04 Условное случайное поле (CRF)

1. Условные случайные поля

Когда между случайными величинами есть зависимости, это условное случайное поле. Например:

三山派的好汉不能和宋江嫡系挨着坐。

Условное случайное поле получает на вход последовательность (последовательность наблюдений) вида X = (x1,x2,...,xn),

Дана выходная целевая последовательность (последовательность со скрытым состоянием) Y = (y1, y2, ..., yn), где X, Y в верхнем регистре используются для обозначения последовательности.

В общем случае входная последовательность X называетсянаблюдения, выходная последовательность Y называетсясостояния (скрытые состояния). Случайность относится к случайным переменным X и Y. Условный относится к условной вероятности.

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

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

2. Математические определения

Точное описание условного случайного поля на математическом языке: пусть X и Y — случайные величины, P(Y|X) — условное распределение вероятностей Y при заданном X, если случайная величина Y представляет собой марковское случайное поле, то условное распределение вероятностей P(Y|X) называется условным случайным полем.

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

P (Y | X) = \ frac {exp (w.φ (x, y))} {Z_x}

Обратите внимание, что Z (x) — это глобальная нормализация, которая проходит через все Y. Если Z (x) написано в символе произведения, это локальная нормализация, а это MEMM.

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

Функция потерь CRF состоит из двух частей: оценки истинного пути и общей оценки всех путей. Оценка реального пути должна быть самой высокой из всех путей.

3. linear-CRF

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

?=(?1,?2,...??), ?=(?1,?2,...??)

Линейная CRF, каждый Y связан только с предыдущей или следующей случайной величиной, такой как Y1-Y2-Y3-...Yn. Каждая максимальная клика — это две соседние случайные величины, такие как (Y1, Y2), (Y2, Y3) и т. д.

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

Linear-CRF vs HMM превращает стрелки (направления передачи) в прямые линии. Самый простой сенсорный опыт состоит в том, что каждый круг (вектор) может быть соединен с соседними кругами бессовестно и беспрепятственно.Взаимодействий становится больше, а модель усложняется.Отношения между каждым кругом изменились с «локальных» на «Глобальные». Linear-CRF является одной из наиболее часто используемых структур CRF.Пока последовательность состояний гарантированно удовлетворяет марковскому свойству, это CRF.

4. Примеры

В Интернете есть два хороших примера CRF, выдержки из которых выглядят следующим образом:

Пример 1

Предположим, у вас есть много фотографий одноклассников Сяо Мина в разное время дня, начиная с того момента, когда Сяо Мин надевает штаны, чтобы встать и снять штаны, чтобы заснуть (Сяо Мин — фотоконтроль!). Задача теперь состоит в том, чтобы классифицировать эти фотографии. Например, если на некоторых фотографиях еда, пометьте ее как еду; если некоторые фотографии сделаны во время бега, пометьте их как бег; если некоторые фотографии сделаны во время встречи, пометьте их как встречу. Вопрос в том, что ты собираешься делать?

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

Это возможно?

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

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

Пример 2

RF — случайное поле, MRF — случайное поле Маркова, также известное как модель графа вероятностей, CRF — условное случайное поле, CRF с линейной цепочкой — CRF с линейной цепочкой

Возьмем в качестве примера «личность людей в группе, личность одного человека в группе может повлиять на личность другого»: Определение «все люди, которых я знаю с детства + все люди, которых моя девушка знала с детства» — это пространство, а «характер всех в пространстве» — это переменная, тогда:

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

MRF: Допустим сейчас такое состояние, что незнакомые мне люди вообще не влияют на мою личность (попарная марковщина), тогда это МРФ.

CRF: Я только что сказал, что переменные личности влияют друг на друга, что очень неверно, потому что нужно что-то для измерения личности, поэтому я предположил другое условие, предполагая, что я могунаблюдениеКогда дело доходит до «времени, когда все соприкасаются с ней и ее смехом», то влияние характера в это время не так уж неописуемо Я сказал, что она рождена, чтобы много смеяться, потому что она родилась с оптимистичным характером. Этот человек и этот человек При разговоре с ней вместе он смеется выше среднего, то есть эти два человека имеют большое влияние на его оптимизм.В это время вы принимаете во внимание смех, чтобы изучить характер, и есть условная вероятность, которая является CRF.

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

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

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

5. HMM vs MEMM vs CRF

Предположение

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

вывод предсказания

Среди них в HMM Yi связан только с Yi-1, а выход Xi связан только с Yi. В MEMM Yi определяется Xi и Yi-1.В CRF, если определяется определенный Yi, он будет учитывать все Y и Xi.

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

Все три модели можно использовать в качестве моделей аннотаций последовательности. Но у каждого есть свои особенности.

Модель HMM: предполагает распределение вероятностей между переменными и моделирует совместное распределение всех наблюдаемых переменных. Между переменными Y было сделано марковское предположение. Прямое моделирование вероятности перехода и вероятности выполнения, а также статистической вероятности совпадения.
Модель MEMM: она предназначена для установления совместной вероятности вероятности перехода и вероятности выполнения, а статистика представляет собой условную вероятность. MEMM легко попасть в локальный оптимум, потому что MEMM нормализует только локально,
Модель CRF: критерий максимальной энтропии моделирует условную вероятность p(Y|X).глобальная вероятность, при нормализации учитывается глобальное распределение данных, а не только локальная нормализация, что решает проблему смещения меток в MEMM. Сначала ограничьте CRF линейной цепочкой CRF, затем разницу между линейной цепочкой CRF и HMM:Это разница между дискриминационной моделью и генеративной моделью, а также разница между подгонкой функции и вероятностной моделью.

HMM заключается в создании генеративной модели, то есть p(x,y), которая преобразуется вnoisy-channelмодели, то есть найти arg max p(y) p(x|y), а затем преобразовать его в произведение вероятности перехода состояния p(yi|yi-1) и вероятности выброса p(xi|yi), заплатив Обратите внимание на эту вероятность выброса, которая такая же, как crf. Вероятность выброса отличается. Моделирование — это оценка параметров вероятности перехода состояния и вероятности эмиссии, основанная на статистике большого количества документированных данных. Процесс декодирования использует алгоритм vertibe для вычисления оптимального решения с использованием вероятности перехода состояния и вероятности эмиссии, которая является генеративной моделью.

MEMM должен установить условную модель, а именно p(y|x) , которая преобразуется в вероятность перехода состояния p(yi|x1, ..., xi, yi-1) . Используйте эту зависимость для построения модели лог-линейной маркировки, которая может охватывать больше функций, чем HMM, и использовать локальную нормализацию в процессе лог-линейной, то есть для каждого yi требуется exp(θ . f (hi, yi)) / ∑ exp(θ . f(hi, yi)) . Обратите внимание, что знаменатель формулы нормализации различен для разных yi, потому что разные yi зависят от разных hi. hi есть зависимость от yi, т.е. x1, ..., xi, yi-1. Это также означает, что в процессе декодирования с использованием алгоритма vertibe значение yi, полученное на каждом временном шаге, является более или менее локальным оптимальным, а не обязательно глобальным оптимальным. Процесс моделирования заключается в оценке параметров θ, то есть в получении структурированной оценки максимального правдоподобия.

crf заключается в построении условной модели, то есть p(y|x) , crf также является моделью лог-линейной маркировки, но зависимость становится целойyпоследовательность зависит от всегоxПоследовательность, то есть глобальная нормализация, имеет то преимущество, что в процессе декодирования знаменатель нормализованной формулы один и тот же, а конечный результат должен быть глобальным оптимумом, поэтому только различные вероятности перехода состояний и сумма выбросов вероятностей просто отлично.В процессе декодирования HMM и MEMM оба умножения.Почему crf различные суммирования?Поскольку не нужно вычислять знаменатель, числитель журнала на самом деле сумма различных вероятностей переходов состояний и вероятностей выбросов.

6. Чтение исходного кода

Следующий исходный код взят изCRF++: Yet Another CRF toolkit, разбор основных выдержекАнализ кода CRF++

Вычислительная стоимость

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

Среди них fvector — это начальный набор идентификаторов текущей функциональной функции попадания, для каждого начального идентификатора существует несколько значений y последовательных меток, n->y — метка в текущий момент, так как каждая функция функции должна принимать x одновременно, а y может принять решение о выводе 1 или 0, поэтому добавьте два, чтобы определить идентификатор конечной функции функции. По этому id можно получить конечный вес в альфа-векторе, сложить веса, умножить на коэффициент (то есть на так называемый стоимостной параметр cost_factor) и получить итоговую стоимость.

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

struct Node {
  unsigned int         x;
  unsigned short int   y;
  double               alpha;
  double               beta;
  double               cost;
  double               bestCost;
  Node                *prev;
  const int           *fvector;
  std::vector<Path *>  lpath;
  std::vector<Path *>  rpath;
}

struct Path {
  Node      *rnode;
  Node      *lnode;
  const int *fvector;
  double     cost;
}

//计算节点的特征函数的代价
void FeatureIndex::calcCost(Node *n) const {
  n->cost = 0.0;

  // 遍历节点对应的所有特征函数，因为一个特征函数可能会对应多个输出类别，所以要将目前节点的 y 代入，得到 *f + n->y，就是当前 y 在 f 输出类别中对应的位置。然后就可以从alpha向量中取到最终的权值, 再将权值累加。
#define ADD_COST(T, A)                                                        \
  do { T c = 0;                                                               \
    for (const int *f = n->fvector; *f != -1; ++f) { c += (A)[*f + n->y];  }  \
    n->cost =cost_factor_ *(T)c; } while (0)

  if (alpha_float_) {
    ADD_COST(float,  alpha_float_);
  } else {
    ADD_COST(double, alpha_);
  }
#undef ADD_COST
}

//计算每条边的状态特征函数的代价
void FeatureIndex::calcCost(Path *p) const {
  p->cost = 0.0;

#define ADD_COST(T, A)                                          \
  { T c = 0.0;                                                  \
    for (const int *f = p->fvector; *f != -1; ++f) {            \
      c += (A)[*f + p->lnode->y * y_.size() + p->rnode->y];     \
    }                                                           \
    p->cost =cost_factor_*(T)c; }

  if (alpha_float_) {
    ADD_COST(float,  alpha_float_);
  } else {
    ADD_COST(double, alpha_);
  }
}
#undef ADD_COST
}

прямой-обратный алгоритм

void TaggerImpl::forwardbackward() {
  if (x_.empty()) {
    return;
  }

  //计算所有节点的前向概率
  for (int i = 0; i < static_cast<int>(x_.size()); ++i) {
    for (size_t j = 0; j < ysize_; ++j) {
      node_[i][j]->calcAlpha();
    }
  }

  //计算所有节点的后向概率
  for (int i = static_cast<int>(x_.size() - 1); i >= 0;  --i) {
    for (size_t j = 0; j < ysize_; ++j) {
      node_[i][j]->calcBeta();
    }
  }

  //计算规范化因子
  Z_ = 0.0;
  for (size_t j = 0; j < ysize_; ++j) {
    Z_ = logsumexp(Z_, node_[0][j]->beta, j == 0);
  }

  return;
}

//其中cost是我们刚刚计算的当前节点的M_i(x)，而alpha则是当前节点的前向概率。lpath是入边，一个顶点可能有多个入边。
void Node::calcAlpha() {
  alpha = 0.0;
  for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it) {
    alpha = logsumexp(alpha,
                      (*it)->cost +(*it)->lnode->alpha,
                      (it == lpath.begin()));
  }
  alpha += cost;
}

void Node::calcBeta() {
  beta = 0.0;
  for (const_Path_iterator it = rpath.begin(); it != rpath.end(); ++it) {
    beta = logsumexp(beta,
                     (*it)->cost +(*it)->rnode->beta,
                     (it == rpath.begin()));
  }
  beta += cost;
}

void Node::calcExpectation(double *expected, double Z, size_t size) const {
  const double c = std::exp(alpha + beta - cost - Z);
  for (const int *f = fvector; *f != -1; ++f) {
    expected[*f + y] += c;
  }
  for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it) {
    (*it)->calcExpectation(expected, Z, size);
  }
}

#define MINUS_LOG_EPSILON  50
// log(exp(x) + exp(y));
//    this can be used recursivly
// e.g., log(exp(log(exp(x) + exp(y))) + exp(z)) =
// log(exp (x) + exp(y) + exp(z))
inline double logsumexp(double x, double y, bool flg)
{
    if (flg)
        return y;  // init mode
    const double vmin = std::min(x, y);
    const double vmax = std::max(x, y);
    if (vmax > vmin + MINUS_LOG_EPSILON)
    {
        return vmax;
    }
    else
    {
        return vmax + std::log(std::exp(vmin - vmax) + 1.0);
    }
}

глобальная нормализация

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

Z_ = 0.0;
for (size_t j = 0; j < ysize_; ++j) {
  // 注意，这里是用 node_[0] 位置的 beta 数值，就是说，这个已经是用后向概率的最终结果来计算 Z，这个就已经是考虑了全局情况，如果是用 alpha 计算，也得取最终数值，那就需要取 node_[n][j]->alpha 了
	Z_ = logsumexp(Z_, node_[0][j]->beta, j == 0); 
}

Процесс получения выглядит следующим образом:

Расчет ожидаемой стоимости

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

/**
 * 计算节点期望
 * @param expected 输出期望
 * @param Z 规范化因子
 * @param size 标签个数
 */
void Node::calcExpectation(double *expected, double Z, size_t size) const {

  const double c = std::exp(alpha + beta - cost - Z);

  // 概率求和意味着得到期望
  for (const int *f = fvector; *f != -1; ++f) {
    expected[*f + y] += c;
  }

  // 对应边的期望值
  for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it) {
    (*it)->calcExpectation(expected, Z, size);
  }
}

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

/**
 * 计算边的期望
 * @param expected 输出期望
 * @param Z 规范化因子
 * @param size 标签个数
 */
void Path::calcExpectation(double *expected, double Z, size_t size) const
{
    const double c = std::exp(lnode->alpha + cost + rnode->beta - Z);
    for (const int *f = fvector; *f != -1; ++f)
    {
        expected[*f + lnode->y * size + rnode->y] += c;
    }
}

алгоритм Витерби

void TaggerImpl::viterbi() {
  for (size_t i = 0;   i < x_.size(); ++i) {
    for (size_t j = 0; j < ysize_; ++j) {
      double bestc = -1e37;
      Node *best = 0;
      const std::vector<Path *> &lpath = node_[i][j]->lpath;
      for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it) {
        double cost = (*it)->lnode->bestCost +(*it)->cost +
            node_[i][j]->cost;
        if (cost > bestc) {
          bestc = cost;
          best  = (*it)->lnode;
        }
      }
      node_[i][j]->prev     = best;
      node_[i][j]->bestCost = best ? bestc : node_[i][j]->cost;
    }
  }

  double bestc = -1e37;
  Node *best = 0;
  size_t s = x_.size()-1;
  for (size_t j = 0; j < ysize_; ++j) {
    if (bestc < node_[s][j]->bestCost) {
      best  = node_[s][j];
      bestc = node_[s][j]->bestCost;
    }
  }

  for (Node *n = best; n; n = n->prev) {
    result_[n->x] = n->y;
  }

  cost_ = -node_[x_.size()-1][result_[x_.size()-1]]->bestCost;
}

0x05 Пример запаса воды

Или расширение предыдущего примера

梁山好汉在聚义厅开会，大家共聚一堂，讨论招安事宜。但是群体中好汉会彼此影响投票的选择。

随机场 ：假定不是按照座次排序，而是随意坐，这样大家座位分布是随机的。

最大团 ：虽然是随机场，但是好汉们会自动按照小团体站在一起，比如黄门山四人站在一起，三山帮站在一起。这就形成了很多最大团。

马尔可夫随机场 ：假设现在有这么个条件，彼此不挨着的好汉不能影响彼此的投票决定（成对马尔可夫性），这就是MRF。

条件随机场：假设有一些其他条件需要考虑，比如如果铁笛仙马麟虽然属于黄门山这个最大团，但是他的位置不小心挨着李逵，那么他在投票时候，势必得考虑铁牛兄弟的意见，不然铁牛的拳头不是吃素的。比如曹正虽然属于三山帮，但是林冲是他师傅，所以他投票也得考虑豹子头的意见，这就构成了条件场.....

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

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

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

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