Auto Byte

Science AI

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

• 文本生成问题中的解码问题；

• 贪婪搜索解码算法及其在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 searchdef 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]`