Jiebe学習ノート:viterbiアルゴリズム
1862 ワード
語句表記:
Jiebaの品詞表記モジュールは依然としてHMMモデルに基づくviterbiアルゴリズムを採用し,状態の記述に({BMES},品詞)二元対を適用している.状態集合は{BMSE}の4つの語位と語性(39類)のデカルト積,すなわち156種の状態である.
テキストの開始位置から逐字スキャンを開始し,各ワードの可能な状態を判断し,状態遷移から得られる期待状態,すなわち次ワードの可能な状態を求める.との結果が空セットの場合は期待状態が次の文字の状態、期待状態セットの場合は空、全体の状態セットがその状態となる.
def viterbi(obs, states, start_p, trans_p, emit_p):#obs: ,states, ,start_p: ,
V = [{}] # tabular
mem_path = [{}]
all_states = trans_p.keys()
for y in states.get(obs[0], all_states): # init
#get turple,
V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)
mem_path[0][y] = ''
for t in xrange(1, len(obs)):
V.append({})
mem_path.append({})
#prev_states = get_top_states(V[t-1])
prev_states = [
x for x in mem_path[t - 1].keys() if len(trans_p[x]) > 0]
# ,x
prev_states_expect_next = set(
(y for x in prev_states for y in trans_p[x].keys()))
#y:
obs_states = set(
states.get(obs[t], all_states)) & prev_states_expect_next
#
if not obs_states:
obs_states = prev_states_expect_next if prev_states_expect_next else all_states
for y in obs_states:
prob, state = max((V[t - 1][y0] + trans_p[y0].get(y, MIN_INF) +
emit_p[y].get(obs[t], MIN_FLOAT), y0) for y0 in prev_states)
V[t][y] = prob
mem_path[t][y] = state
last = [(V[-1][y], y) for y in mem_path[-1].keys()]
# if len(last)==0:
# print obs
prob, state = max(last)
route = [None] * len(obs)
i = len(obs) - 1
while i >= 0:
route[i] = state
state = mem_path[i][state]
i -= 1
return (prob, route)