本篇是TSP問題從DP算法到深度學習系列第四篇，這一篇我們會詳細舉例並比較在 seq-to-seq 或者Markov Chain中的一些常見的搜索概率最大的狀態序列的算法。這些方法在深度學習的seq-to-seq 中被用作decoding。在第五篇中，我們使用強化學習時也會使用了本篇中講到的方法。
TSP問題從DP算法到深度學習1：遞歸DP方法 AC AIZU TSP問題
TSP問題從DP算法到深度學習2：歐氏空間數據集的DP解
TSP問題從DP算法到深度學習3：Pointer Network
在 seq-to-seq 問題中，我們經常會遇到需要從現有模型中找概率最大的可能狀態序列。這類問題在機器學習算法和控制領域廣泛存在，抽象出來可以表達成馬爾可夫鏈模型：給定初始狀態的分布和系統的狀態轉移方程（稱為系統動力，dynamics），找尋最有可能的狀態序列。
舉個例子，假設系統有
狀態轉移矩陣由
至此，系統的所有參數都定下來了。接下去的各個時刻的狀態分布可以通過矩陣乘法來算得。比如，記
矩陣左乘行向量可以理解為矩陣每一行的線性組合，直覺上理解為下一時刻的狀態分布是上一時刻初始狀態分布乘以轉移關係的線性組合。
同樣的，後面每一個時刻都可以由上一個狀態分布向量乘以
下面我們通過多種算法來找出由上述參數定義的系統中前三個時刻的最有可能序列，即概率最大的
令
窮竭搜索若給定一條路徑，計算特定路徑的概率是很直接的，例如，若給定路徑為
因此，我們可以通過枚舉所有
下面是Python 3的窮竭搜索代碼，輸出為最有可能的概率及其路徑。樣例問題的輸出為 0.084 和狀態序列
def search_brute_force(initial: List, transition: List, L: int) -> Tuple[float, Tuple]:
from itertools import combinations_with_replacement
v = [0, 1, 2]
path_all = combinations_with_replacement(v, L)
max_prop = 0.0
max_route = None
prob = 0.0
for path in list(path_all):
for idx, v in enumerate(path):
if idx == 0:
prob = initial[v] # reset to initial state
else:
prev_v = path[idx-1]
prob *= transition[prev_v][v]
if prob > max_prop:
max_prop = max(max_prop, prob)
max_route = path
return max_prop, max_route
貪心搜索窮竭搜索一定會找到最有可能的狀態序列，但是算法複雜度是指數級的
Python 3 實現中我們利用了 numpy 類庫，主要是 np.argmax() 可以讓代碼簡潔。代碼本質上是兩重循環，（一層循環是np.argmax中），對應時間算法複雜度是
def search_greedy(initial: List, transition: List, L: int) -> Tuple[float, Tuple]:
import numpy as np
max_route = []
max_prop = 0.0
states = np.array(initial)
prev_max_v = None
for l in range(0, L):
max_v = np.argmax(states)
max_route.append(max_v)
if l == 0:
max_prop = initial[max_v]
else:
max_prop = max_prop * transition[prev_max_v][max_v]
states = max_prop * states
prev_max_v = max_v
return max_prop, max_route
Beam 搜索貪心策略只考慮了下一步的最大概率狀態，若我們改進一下貪心策略，將下一步的最大
以下是Python 3 的代碼實現，利用了 PriorityQueue 選取
def search_beam(initial: List, transition: List, L: int, K: int) -> Tuple[float, Tuple]:
N = len(initial)
from queue import PriorityQueue
current_q = PriorityQueue()
next_q = PriorityQueue()
from functools import total_ordering
@total_ordering
class PQItem(object):
def __init__(self, prob, route):
self.prob = prob
self.route = route
self.last_v = int(route[-1])
def __eq__(self, other):
return self.prob == other.prob
def __lt__(self, other):
return self.prob > other.prob
for v in range(N):
next_q.put(PQItem(initial[v], str(v)))
for l in range(1, L):
current_q = next_q
next_q = PriorityQueue()
k = K
while not current_q.empty() and k > 0:
item = current_q.get()
prob, route, prev_v = item.prob, item.route, item.last_v
k -= 1
for v in range(N):
nextItem = PQItem(prob * transition[prev_v][v], route + str(v))
next_q.put(nextItem)
max_item = next_q.get()
return max_item.prob, list(map(lambda x: int(x), max_item.route))
Viterbi 動態規劃和之前TSP 動態規划算法的思想一樣，最有可能狀態路徑問題解法有可以將指數時間複雜度
實現代碼中沒有返迴路徑本身而只是其概率值，目的是通過簡潔的三層循環來表達算法精髓。
def search_dp(initial: List, transition: List, L: int) -> float:
N = len(initial)
dp = [[0.0 for c in range(N)] for r in range(L)]
dp[0] = initial[:]
for l in range(1, L):
for v in range(N):
for prev_v in range(N):
dp[l][v] = max(dp[l][v], dp[l - 1][prev_v] * transition[prev_v][v])
return max(dp[L-1])
概率採用以上所有的算法都是確定性的。在NLP 深度學習decoding 時候會帶來一個問題：確定性容易導致生成重複的短語或者句子。比如，確定性算法很容易生成如下句子。
This is the best of best of best of ...一種簡單的方法是採用概率採用的方式迴避這個問題。也就是我們不尋找確定的局部最優或者全局最優的解，而是通過局部路徑或者全局路徑的概率信息進行採樣生成序列。例如，對於窮竭搜索的
def search_prob_greedy(initial: List, transition: List, L: int) -> Tuple[float, Tuple]:
import random
N = len(initial)
max_route = []
max_prop = 0.0
vertices = [i for i in range(N)]
prob = initial[:]
for l in range(0, L):
v_lst = random.choices(vertices, prob)
v = v_lst[0]
max_route.append(v)
max_prop = prob[v]
prob = [prob[v] * transition[v][v_target] for v_target in range(N)]
return max_prop, max_route