小编som*_*guy的帖子

以下是我所知道的计算马尔可夫链中的转换并使用它来填充转换矩阵的最基本方法:

def increment_counts_in_matrix_from_chain(markov_chain, transition_counts_matrix):
    for i in xrange(1, len(markov_chain)):
        old_state = markov_chain[i - 1]
        new_state = markov_chain[i]
        transition_counts_matrix[old_state, new_state] += 1

我尝试过3种不同的加速方式:

1)使用基于此Matlab代码的稀疏矩阵单行程:

transition_matrix = full(sparse(markov_chain(1:end-1), markov_chain(2:end), 1))

在Numpy/SciPy中,它看起来像这样:

def get_sparse_counts_matrix(markov_chain, number_of_states):
    return coo_matrix(([1]*(len(markov_chain) - 1), (markov_chain[0:-1], markov_chain[1:])), shape=(number_of_states, number_of_states)) 

我尝试了几个Python调整,比如使用zip():

for old_state, new_state in zip(markov_chain[0:-1], markov_chain[1:]):
    transition_counts_matrix[old_state, new_state] += 1 

和队列:

old_and_new_states_holder = Queue(maxsize=2)
old_and_new_states_holder.put(markov_chain[0])
for new_state in markov_chain[1:]:
    old_and_new_states_holder.put(new_state)
    old_state = old_and_new_states_holder.get()
    transition_counts_matrix[old_state, new_state] += 1

但是这三种方法都没有加速.实际上,除了zip()解决方案之外的所有内容都比我原来的解决方案慢了至少10倍.

还有其他值得研究的解决方案吗？

用于从许多链构建转换矩阵的改进解决方案
上述问题的最佳答案是DSM.但是,对于任何想要根据数百万马尔可夫链列表填充转换矩阵的人来说,最快的方法是:

def fast_increment_transition_counts_from_chain(markov_chain, transition_counts_matrix):
    flat_coords = numpy.ravel_multi_index((markov_chain[:-1], markov_chain[1:]), transition_counts_matrix.shape) …