路径和问题:腐烂的橘子BFS 二进制矩阵中的最短路径BFS

64. 最小路径和

994. 腐烂的橘子

1091. 二进制矩阵中的最短路径

 

对话系统的评价指标

对于某一轮对话而言,可以使用响应的适当性、流畅度、相关性;对于多轮对话而言,我们更关注流畅性、对话深度、多样性、一致连贯性等指标;而对于整个对话系统,我们则希望他可以涵盖更多的话题、回复真实可信等等。

一.词重叠评价指标

该指标认为回答应该和真实回答之间存在大量的词重叠

1.BLEU

candidate(Predicted):机器生成的结果;reference(Gold Standard):参考句,类似于参考答案,可以多句;

Step 1:Modified n-gram Precision计算(也即Pn

当n=1/2/3/4时的precision;首先统计候选译文里每个词(n-gram)出现的次数,然后统计每个词(n-gram)在参考译文中出现的次数,Max表示3个参考译文中的最大值,Min表示候选译文和Max两个的最小值。

以unigram为例,bigram、trigram、4-gram相同:

Step 2:Brevity Penalty 计算

if c > r: return 1 else: return math.exp(1 – r / c) c:候选句的长度;r:参考句的最大长度

Step 3:Pn * Bp
2.ROUGE

①ROUGE-N

②ROUGE-L

③ROUGE-W

④ROUGE-S

3.METEOR

二、词向量评价指标

词向量则是通过Word2Vec、Sent2Vec等方法将句子转换为向量表示,这样一个句子就被映射到一个低维空间,句向量在一定程度上表征了其含义,在通过余弦相似度等方法就可以计算两个句子之间的相似程度。

1.Greedy Matching

2.Embedding Average

3.Vector Extrema

跟上面的方法类似,也是先通过词向量计算出句向量,在使用句向量之间的余弦相似度表示二者的相似度。不过句向量的计算方法略有不同,这里采用向量极值法进行计算。

三、perplexity困惑度

四、人工指标

ref:

二叉树中所有距离为 K 的结点BFS+DFS 二叉树的堂兄弟节点BFS/DFS

863. 二叉树中所有距离为 K 的结点

993. 二叉树的堂兄弟节点

 

判断二分图BFS 最短的桥DFS+BFS

785. 判断二分图

934. 最短的桥

相似的题目引用:

单词接龙DFS 被围绕的区域DFS 岛屿数量DFS

N叉树的层序遍历 01矩阵 BFS

N叉树的最大深度 打开转盘锁 层次遍历