Тегирование частей речи на основе модели шумного канала и алгоритма Витерби

Это 19-й день моего участия в августовском испытании обновлений. Ознакомьтесь с подробностями мероприятия: Испытание августовского обновления

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

Для предложения S каждое слово в предложении$w_i$Соответствующая часть речи отмечена$z_i$. Теперь проблема заключается в том, что для другого предложения S' сгенерировать каждое слово$w'_i$часть речи$z'_i$

То есть требование делает вероятность$P(Z|S)$самый большой$Z$, что можно получить по теореме Байеса

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

1. предположения HMM, т.е.$w_i$только с$z_i$Связанные, независимые от всех других слов или частей речи. следовательно$P(w_1,...,w_N|z_1,...,z_N)$можно упростить до$\prod_{i=1}^{N}P(w_i|z_i)$
2. Предположим, что моделью языка является биграмма. следовательно$P(z_1,...,z_N)$можно записать как$P(z_1)P(z_2|z_1)···P(z_N|z_{N-1})$,Сейчас$P(z_1)\prod_{j=2}^NP(z_j|z_{j-1})$

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

Определить параметры

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

Первый параметр:$A=P(w_i|z_i)$

параметр$A$значит, учитывая часть речи$z_i$В случае , ему соответствует слово$w_i$Условная вероятность , т. е. всех элементов, помеченных как часть речи$z_i$слов, слова$w_i$доля

Например, если предположить, что часть речи NN (существительное) дана первой, вероятность того, что соответствующее слово — яблоко, определенно выше, чем есть, т. е.$P(\text{apple}\mid \text{NN})>P(\text{eat}\mid \text{NN})$

Для удобства дальнейшего расчета зададим параметр$A$Пространство значений хранится вМатрица с N строк и M столбцов, где N — количество разных частей речи в корпусе, а M — количество разных слов в корпусе. Каждая строка матрицы представляет собой часть речи, каждый столбец представляет слово, а элементы матрицы$a_{ij}$выражается во всех частях речи как$i$слов, слова$j$Видно, что сумма всех вероятностей в одной строке равна 1, т. е.$\sum_{j=1}^Ma_{ij}=1$

Вычислить матрицу A очень просто, сначала определите размер как$N\times M$матрица со всеми нулями, затем перебирает каждую строку в корпусе单词/词性, добавить 1 к значению соответствующей позиции строки "пройденная в данный момент часть речи" и позиции столбца "пройденное в данный момент слово" в матрице соответствия

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

Второй параметр:$\pi=P(z_i)$

параметр$\pi$Указывает, что первая часть предложения$z_i$Вероятность , то есть подсчета всех частей речи в начале предложения$z_i$доля

Например, вероятность начала общего предложения с NN (существительное) выше, чем с VB (глагол), т.е.$P(\text{NN})>P(\text{VB})$

параметр$\pi$Диапазон значений может храниться вдлина$N$векторсередина,$N$количество различных частей речи в корпусе. Можно сделать вывод, что сумма элементов этого вектора равна 1, т. е.$\sum_{i=1}^NP(i)=1$

Сначала инициализируйте вектор с 0$\pi$, длина$N$. Затем перебрать каждую строку в корпусе单词/词性, чтобы определить, находится ли текущее слово в начале предложения, а основание для суждения состоит в том, чтобы увидеть, является ли предыдущее слово завершающим знаком препинания, таким как точка, восклицательный или вопросительный знак. Если это начало предложения, выньте текущую часть речи и добавьте 1 к значению в векторе, соответствующем позиции «пройденной в данный момент части речи».

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

Третий параметр:$B=P(z_i|z_{i-1})$

параметр$B$означает, что данная предшествующая часть речи$z_{i-1}$, текущая часть речи$z_i$Условная вероятность , т. е. вычисляемая в предшествующей части речи как$z_{i-1}$из(前驱词性,当前词性)Сочетательная пара, текущая часть речи$z_i$Доля комбинационных пар

Например, для данной предшествующей части речи VB (глагол) вероятность того, что текущей частью речи является NN (существительное), выше, чем у VB (глагол), т. е.$P(\text{NN}|\text{VB})>P(\text{VB}|\text{VB})$

параметр$B$Является**$N\times N$матрица**,$N$количество различных частей речи в корпусе. Строка матрицы представляет предыдущую часть речи, столбец представляет текущую часть речи, а элементы матрицы$b_{ij}$Предшественник$i$, текущая часть речи$j$Условная вероятность , видно, что сумма всех элементов в одной строке равна 1, то есть$\sum_{j=1}^Nb_{ij}=1$

матрица$B$Расчет очень прост, сначала определите размер как$N\times N$Полностью нулевой квадрат. Затем просмотрите корпус, подсчитайте биграмму последовательности частей речи и добавьте 1 к значению соответствующей строки «предшествующая часть речи» и позиции столбца «текущая часть речи» в квадратной матрице.

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

tag2id, id2tag = {}, {} # tag2id: {"VB":0,...}, id2tag: {0:"VB",...}
word2id, id2word = {}, {}

for line in open('traindata.txt'):
    items = line.split('/')
    word, tag = items[0], items[1].rstrip() # 去掉换行符
    
    if word not in word2id:
        word2id[word] = len(word2id)
        id2word[len(id2word)] = word
    if tag not in tag2id:
        tag2id[tag] = len(tag2id)
        id2tag[len(id2tag)] = tag

N = len(tag2id) # number of tags
M = len(word2id) # number of words
print(N, M)

# define pi, A, B
import numpy as np

pi = np.zeros(N) # pi[i] 表示tag i出现在句子开头的概率, vector
A = np.zeros((N, M)) # A[i][j] 表示给定tag i, 出现word j的概率, matrix
B = np.zeros((N, N)) # B[i][j] 表示前一个是tag i, 后一个是tag j的概率, matrix

pre_tag = -1 # 记录前一个tag的id
for line in open('traindata.txt'):
    items = line.split('/')
    wordid, tagid = word2id[items[0]], tag2id[items[1].rstrip()]
    if pre_tag == -1: # 这意味着是句子的开始
        pi[tagid] += 1
        A[tagid][wordid] += 1
        pre_tag = tagid
    else: # 不是句子开头
        A[tagid][wordid] += 1
        B[pre_tag][tagid] += 1
        
    if items[0] == '.':
        pre_tag = -1
    else:
        pre_tag = tagid

        
# normalize
pi /= sum(pi) # probability
for i in range(N):
    A[i] /= sum(A[i])
    B[i] /= sum(B[i])

Рассчитать оптимальное решение

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

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

Предполагать

Наша цель для заданного текста$S=w_1w_2...w_T$, дай это$T$Каждому слову соответствует часть речи (с$N$необязательная часть речи), чтобы максимизировать значение счета. Процесс подсчета баллов описывается следующим образом.

Черные точки на рисунке дают пример схемы разметки (как путь):

• $w_1$отмечен как$pos_2$
• $w_2$отмечен как$pos_1$
• $w_3$отмечен как$pos_3$
• ...
• $w_T$отмечен как$pos_T$

Значение оценки пути равно

Из приведенной выше формулы видно, что процесс решения подсчета очков делится на$T$шаги, каждый шаг имеет$N$Выбор. потому что мы можем определить$T\times N$Двумерный массив DP of , для удобства описания, будем считать, что индекс массива начинается с 0, гдеDP[i][j]Указывает, начиная с первого слова, при счете до первого$i$слово (т.$i$шаг) и отметьте часть речи как$j$оптимальный путь (максимальная вероятность), когда

Уравнение перехода состояния

Окончательный ответ (наибольшее значение вероятности) равенmax(DP[T-1][0],DP[T-1][1],...,DP[T-1][N-1]). Но одной вероятности мало, нужно еще записать путь, по которому эта вероятность пришла, этот путь и есть часть речи каждого слова. Поэтому нам также необходимо создать дополнительный$T\times N$Двумерный массив , используемый для записи оптимального пути выбора части речи.

Код части алгоритма Витерби выглядит следующим образом

def log(v):
    if v == 0:
        return np.log(v + 0.0000001)
    return np.log(v)

def viterbi(x, pi, A, B):
    """
    x: user input string/sentence
    pi: initial probability of tags
    A: 给定tag，每个单词出现的概率
    B: tag之间的转移概率
    """
    x = [word2id[word] for word in x.split(" ")]
    T = len(x)
    dp = np.zeros((T, N))
    path = np.array([[0 for x in range(N)] for y in range(T)]) # T*N
    for j in range(N): # basecase for dp algorithm
        dp[0][j] = log(pi[j]) + log(A[j][x[0]])
    
    for i in range(1, T): # every words
        for j in range(N): # every tags
            dp[i][j] = -9999999
            for k in range(N): # 从每个k可以到达j
                score = dp[i-1][k] + log(B[k][j]) + log(A[j][x[i]])
                if score > dp[i][j]:
                    dp[i][j] = score
                    path[i][j] = k
    # print best tag sequence
    best_seq = [0] * T # best_seq = [1, 5, 0, 3, 55, ...]
    # step1: 找出最后一个单词的词性
    best_seq[T-1] = np.argmax(dp[T-1]) # 求出最大值所在下标
    
    # step2: 通过从后往前的循环以此求出每个单词的词性
    for i in range(T-2, -1, -1):
        best_seq[i] = path[i + 1][best_seq[i + 1]]
        
    # step3: print
    for i in range(len(best_seq)):
        print(id2tag[best_seq[i]])

# Test
x = "Social Security number , passport number and details about the services provided for the payment"
viterbi(x, pi, A, B)