学习总结

在ER中，有一类算法依靠参考结构化数据库的模型实现，以便提高ER的速度。但是这类算法常常在运行中产生了大量重复计算，降低了效率。由此，通过介绍以下方法，来解决这个问题：

块分割

给定的字符串：

 X=x1,...xn;其中既有单词又有标点

子序列：

s1,...,sp;对X进行分割后，生成的包含一个或多个单词的字符串sp=(tp,up,y);tp起始位置，up为结束位置，y为特征

特征集合：

Y=y1,..,yj；先后有序令y表示X中子序列的特征

例子：
x1x2x3表示一个人名；x5x6x7x8表示一个题目；
人名，题目用yj表示；
子序列s1=x1x2x3。
其中s1的起始位置用t1表示（这里t1=2），结束位置用u1=3表示。
并且

最大不超过X的长度，最小不低于1.

第二个子串的起始位置在第一个子串结束位置之后的第一个单词，也就是相邻子串之间没有空隙，是连续的。

最后一个子串up结束的位置为X序列结束位置，第一个子串s1起始位置为X序列第一个单词。
注意up的下标p，对应子序列sp中的p，下标的计数p跟子串个数S相关，把X分成10个子串，那么P=10，且起始位置tp与结束位置up的下标是一致的，例s1（t1，u1），s2（t2，u2）

特征提取函数：

y'表示前一个特征，y表示当前特征，X表示字符串，tj，uj同上描述。
特征提取函数集g1,...gv，每个一个特征函数（就是一种分割方法）都会有一个与其对应的权重wk。
通过使用维特比算法从这些特征函数中找到使得权重和最大的特征提取函数序列，换句话说，权重和最大表示了该特征提取函数序列对X进行了最优化分割。
这一过程是在训练中完成。接下来将介绍最优化分割。

最优化分割：

s*表示在所有s1,...,sp中，得分最高的一个si。
由于每个特征提取函数g都会生成一个序列s1,...,sp，所以需要维特比算法找到一条路径，使得改路径上的每一个s都达到最大值。

表示可能的分割序列的集合，所谓分割序列，意思是由不同的特征提取函数生成不同的分割序列，s1：y---si:y

该算法将形成一条路径，该路径上每一个si：y都是整个Si：y集合中的最大值,用

表示

y'表示前一个特征，其作用是概率传递，意思是，在计算完第一个特征值后，其值将影响下一个特征值的计算，以此类推，形成一条路径。若没有y'，则退化成简单最大值计算问题。

  y1       y2     y3  . . .                   ym    s1       s1max  .   . . .                   s1    s2max    s2          .                      s2    s3       s3                .                s3    .         .               .                 .     .         .                 .               .    .         .     .   . . .  . .              .     si       si     .   . . .  . .   .   .   .  si  

i行m个列，每次计算从m个列中选取一个，计算到下一个列的距离(从第i行的m个节点中挑一个计算到i+1行m个节点的距离)，m*m，一共计算i行， 其复杂度为O(IM2)
σ(1,y)表示在序列s2中，y1特征得到了最大值。依据公式（1），在对y2计算时，将选取s2作为起点，将其值传入下一步计算。也就是说y2的最大值受y1影响。
从m个分词中挑选一个分词，计算该分词到下一个分词的值（以前一个分词为起点，把下一个所有特征的分词都计算一遍）。

维特比算法

维特比算法是一个特殊但应用最广的动态规划算法，利用动态规划，可以解决任何一个图中的最短路径问题。其优点是利用动态规划降低复杂度。而维特比算法是针对一个特殊的图——篱笆网络的有向图（Lattice )的最短路径问题而提出的。 它之所以重要，是因为凡是使用隐含马尔可夫模型描述的问题都可以用它来解码。
假设整个篱笆有向图中每一列节点最多有m个（也就是图的宽度为D），并且图一共有N列，那么，每次计算至多计算m*m次（从i列的m个节点中挑一个计算到i+1列m个节点的距离）。至多计算N次。那么复杂度骤减为O（Nm2）m的平方，远远小于穷举O（mN)m的n次方。
马尔科夫链是对多参数条件概率计算的化简，假设某一点的条件概率只和其之前某点相关，与其他点无关。这样就形成了概率传递链。

为了比较算法的优劣，我们设计了一个时间下线，即在最好的情况下的时间消耗。用空间换时间是优化算法的一个常用的方法。存储大量中间生成组件，并重复利用，避免了重新生成部件的过程，减少了时间，但存储空间变大了。

关键字：算法, 序列, 特征, 计算

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！