教程 | 如何使用贪婪搜索和束搜索解码算法进行自然语言处理

• 文本生成问题中的解码问题；
• 贪婪搜索解码算法及其在 Python 中的实现；
• 束搜索解码算法及其在 Python 中的实现。

```# define a sequence of 10 words over a vocab of 5 words
data = [[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1],
[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1],
[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1],
[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1],
[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1]]
data = array(data)```

```# greedy decoder
def greedy_decoder(data):
# index for largest probability each row
return [argmax(s) for s in data]```

```from numpy import array
from numpy import argmax

# greedy decoder
def greedy_decoder(data):
# index for largest probability each row
return [argmax(s) for s in data]

# define a sequence of 10 words over a vocab of 5 words
data = [[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1],
[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1],
[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1],
[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1],
[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1]]
data = array(data)
# decode sequence
result = greedy_decoder(data)
print(result)```

`[4, 0, 4, 0, 4, 0, 4, 0, 4, 0]`

```# beam search
def beam_search_decoder(data, k):
sequences = [[list(), 1.0]]
# walk over each step in sequence
for row in data:
all_candidates = list()
# expand each current candidate
for i in range(len(sequences)):
seq, score = sequences[i]
for j in range(len(row)):
candidate = [seq + [j], score * -log(row[j])]
all_candidates.append(candidate)
# order all candidates by score
ordered = sorted(all_candidates, key=lambda tup:tup[1])
# select k best
sequences = ordered[:k]
return sequences```

```from math import log
from numpy import array
from numpy import argmax

# beam search
def beam_search_decoder(data, k):
sequences = [[list(), 1.0]]
# walk over each step in sequence
for row in data:
all_candidates = list()
# expand each current candidate
for i in range(len(sequences)):
seq, score = sequences[i]
for j in range(len(row)):
candidate = [seq + [j], score * -log(row[j])]
all_candidates.append(candidate)
# order all candidates by score
ordered = sorted(all_candidates, key=lambda tup:tup[1])
# select k best
sequences = ordered[:k]
return sequences

# define a sequence of 10 words over a vocab of 5 words
data = [[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1],
[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1],
[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1],
[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1],
[0.1, 0.2, 0.3, 0.4, 0.5],
[0.5, 0.4, 0.3, 0.2, 0.1]]
data = array(data)
# decode sequence
result = beam_search_decoder(data, 3)
# print result
for seq in result:
print(seq)```

```[[4, 0, 4, 0, 4, 0, 4, 0, 4, 0], 0.025600863289563108]
[[4, 0, 4, 0, 4, 0, 4, 0, 4, 1], 0.03384250043584397]
[[4, 0, 4, 0, 4, 0, 4, 0, 3, 0], 0.03384250043584397]```

• Argmax on Wikipedia（https://en.wikipedia.org/wiki/Arg_max）
• Numpy argmax API（https://docs.scipy.org/doc/numpy-1.9.3/reference/generated/numpy.argmax.html）
• Beam search on Wikipedia（https://en.wikipedia.org/wiki/Beam_search）
• Beam Search Strategies for Neural Machine Translation, 2017.（https://arxiv.org/abs/1702.01806）
• Artificial Intelligence: A Modern Approach (3rd Edition), 2009.（http://amzn.to/2x7ynhW）
• Neural Network Methods in Natural Language Processing, 2017.（http://amzn.to/2fC1sH1）
• Handbook of Natural Language Processing and Machine Translation, 2011.（http://amzn.to/2xQzTnt）
• Pharaoh: a beam search decoder for phrase-based statistical machine translation models, 2004.（https://link.springer.com/chapter/10.1007%2F978-3-540-30194-3_13?LI=true）

0 条评论

相关文章

6695

802

4466

1002

Python+sklearn使用DBSCAN聚类算法案例一则

DBSCAN聚类算法概述： DBSCAN属于密度聚类算法，把类定义为密度相连对象的最大集合，通过在样本空间中不断搜索最大集合完成聚类。 DBSCAN能够在带有噪...

5214

1692

1.2K10

3605

4285