algorithm - 评分系统建议 - 加权机制？

Question

我正在尝试验证用户提供的一系列单词。我正在尝试提出一个评分系统，该系统将确定一系列单词确实是有效单词的可能性。

假设以下输入：

xxx yyy zzz

我做的第一件事是根据我拥有的单词数据库单独检查每个单词。所以，假设它xxx在数据库中，所以我们 100% 确定它是一个有效的词。然后假设yyy数据库中不存在它，但存在其拼写的可能变化（例如yyyy）。我们不会给出yyy100% 的分数，但可能会更低（比如说 90%）。然后zzz在数据库中根本不存在。因此，zzz得分为 0%。

所以我们有这样的事情：

xxx = 100%
yyy = 90%
zzz = 0%

进一步假设用户要么去：

提供所有有效单词的列表（最有可能）
提供所有无效词的列表（可能）
提供有效和无效词的混合列表（不太可能）

总体而言，确定作为xxx yyy zzz一系列有效单词的置信度分数的良好评分系统是什么？我不是在寻找任何太复杂的东西，但是获得分数的平均值似乎并不正确。如果单词列表中的某些单词是有效的，我认为这会增加在数据库中找不到的单词也是实际单词的可能性（这只是数据库的限制，它不包含该特定单词）。

注意：输入通常至少为 2 个单词（大部分是 2 个单词），但可以是 3、4、5（在某些极少数情况下甚至可能更多）。

score 14 · Accepted Answer

编辑我添加了一个新部分，该部分旨在将单词组区分为英语组和非英语组。这是在估计任何给定单词是否为英语的部分下方。

我认为你直觉你在这里解释的评分系统并不能完全解决这个问题。

找到字典中的单词很棒 - 这些单词可以立即给出 100% 并忽略，但是不匹配的单词呢？你如何确定他们的概率？这可以通过包含完全相同字母的句子之间的简单比较来解释：

Abergrandly 收到 wuzkinds
Erbdnerye wcgluszaaindid vker

两个句子都没有任何英语单词，但第一句话看起来是英语 - 它可能是关于某人（Abergrandly）收到（有拼写错误）几个项目（wuzkinds）。第二句话显然只是我的婴儿敲击键盘。

因此，在上面的示例中，即使不存在英语单词，说英语的人说它的可能性也很高。第二句是英语的概率为 0%。

我知道一些有助于检测差异的启发式方法：

字母的简单频率分析

英文字母的典型分布。来自维基百科

在任何语言中，有些字母比其他字母更常见。简单地计算每个字母的出现率并将其与语言平均值进行比较可以告诉我们很多。

有几种方法可以从中计算概率。一种可能是：

准备
1. 计算或获取合适英语语料库中字母的频率。NLTK是一个很好的开始方式。相关的Natural Language Processing with Python 书提供了非常丰富的信息。
考试
1. 计算要测试的短语中每个字母出现的次数
2. 计算线性回归，其中每个字母点的坐标为：
  1. X轴：从1.1以上预测的频率
  2. Y轴：实际计数
3. 对数据执行回归分析
  1. 英语应报告接近 1.0 的正 r。计算 R^2 作为这是英语的概率。
  2. 0 或以下的 r 要么与英语没有相关性，要么字母具有负相关性。不太可能是英语。

优点：

计算非常简单

缺点：

对于小样本（例如“斑马、木琴”）效果不佳
“Rrressseee”似乎是一个很可能的词
不区分我上面给出的两个例句。

Bigram 频率和 Trigram 频率

这是字母频率的扩展，但着眼于字母对或三连音的频率。例如，au 以 99% 的频率跟随 aq（为什么不是 100%？dafuq）。同样，NLTK 语料库非常有用。

有向图频率基于 40,000 个单词的样本

以上来自： http: //www.math.cornell.edu/~mec/2003-2004/cryptography/subs/digraphs.jpg

这种方法在整个行业中被广泛使用，从语音识别到软键盘上的预测文本。

三元组特别有用。考虑到'll'是一个非常常见的有向图。因此，字符串 'llllllllll' 仅包含常见的有向图，而有向图方法使其看起来像一个单词。Trigraphs 解决了这个问题，因为 'llll' 永远不会出现。

使用三元组计算一个单词的概率不能用简单的线性回归模型完成（绝大多数三元组不会出现在单词中，因此大多数点将在 x 轴上）。相反，您可以使用马尔可夫链（使用二元组或三元组的概率矩阵）来计算单词的概率。马尔可夫链的介绍在这里。

首先建立一个概率矩阵：

X 轴：每个二元组（“th”、“he”、“in”、“er”、“an”等）
Y 轴：字母表中的字母。
矩阵成员由二合图之后的字母的概率组成。

要从单词的开头开始计算概率，X 轴有向图需要包括空格-a、空格-b 到空格-z - 例如，有向图“空格”t 表示以 t 开头的单词。

计算单词的概率包括迭代有向图并获得给定有向图的第三个字母的概率。例如，“他们”这个词被分解为以下概率：

h 跟随“空格”t -> 概率x %
e 跟随 th -> 概率y %
y 跟随他 -> 概率z %

总概率 = x * y * z %

此计算通过将“wcgl”突出显示为具有 0% 的概率来解决简单频率分析的问题。

请注意，任何给定单词的概率将非常小，并且在统计上每个额外字符会小 10 倍到 20 倍。但是，通过检查大型语料库中 3、4、5、6 等字符的已知英文单词的概率，您可以确定一个截断值，低于该截断值该单词极不可能出现。每个极不可能的三合字母都会将成为英语的可能性降低 1 到 2 个数量级。

然后，您可以规范化一个单词的概率，例如，对于 8 个字母的英文单词（我已经编造了下面的数字）：

来自马尔可夫链的概率：
- 最佳英语单词的概率 = 10^-7 (10% * 10% * .. * 10%)
- 截止（最不可能的英语单词的概率）= 10^-14 (1% * 1% * .. * 1%)
- 测试词的概率（比如“coattail”）= 10^-12
“标准化”结果
- 取日志：最佳 = -7；测试 = -12；截止 = -14
- 使正面：最佳= 7；测试 = 2; 截止 = 0
- 在 1.0 和 0.0 之间标准化：最佳 = 1.0；测试 = 0.28；截止 = 0.0
- （您可以轻松地将上限和下限调整到 90% 到 10% 之间）

现在我们已经研究了如何获得任何给定单词是英语的更好概率，让我们看看单词组。

该组的定义是最少 2 个单词，但可以是 3、4、5 或（在少数情况下）更多。您没有提到单词之间有任何压倒一切的结构或关联，所以我不假设：

任何组都是一个短语，例如“坦克指挥官”、“红字日”
该组是一个句子或从句，例如“我口渴”、“玛丽需要一封电子邮件”

但是，如果这个假设是错误的，那么对于较大的词组，问题就会变得更容易处理，因为这些词将符合英语的语法规则——我们可以使用NLTK来解析子句以获得更多洞察力。

看一组词是英文的概率

好的，为了了解问题，让我们看一下不同的用例。在下面的：

我将忽略所有单词或所有非单词的情况，因为这些情况是微不足道的
我会考虑你不能被假设在字典中的类似英语的单词，比如奇怪的姓氏（例如 Kardashian）、不寻常的产品名称（例如 stackexchange）等等。
我将使用概率的简单平均值，假设随机乱码为 0%，而类似英语的单词为 90%。

两个字

(50%) 红色 ajkhsdjas
(50%) Hkdfs 星期五
(95%) 卡戴珊计划
(95%) 使用 Stackexchange

从这些示例中，我认为您会同意 1. 和 2. 可能不可接受，而 3. 和 4. 可以。简单的平均计算似乎是两个词组的有用鉴别器。

三个词

用一个可疑的话：

(67%) 红黎明 dskfa
(67%) Hskdkc 共产党宣言
(67%) 经济 jasdfh 危机
(97%) 卡戴珊十五分钟
(97%) stackexchange 用户体验

显然 4. 和 5. 是可以接受的。

但是 1.、2. 或 3. 呢？1.、2. 或 3. 之间是否存在任何实质性差异？可能不会，排除使用贝叶斯统计。但是这些是否应该归类为英语？我想这是你的电话。

用两个可疑的词：

(33%) 红色 ksadjak adsfhd
(33%) jkdsfk dsajjds 宣言
(93%) Stackexchange 向卡戴珊发送电子邮件
(93%) Stackexchange 卡戴珊账户

我会冒险认为 1. 和 2. 是不可接受的，但 3. 和 4. 肯定是。（嗯，除了卡戴珊在这里有一个账户——这不是好兆头）。再次，简单平均值可以用作简单的鉴别器 - 您可以选择它是高于还是低于 67%。

四个字

排列的数量开始变得疯狂，所以我只举几个例子：

一个可疑的词：
1. (75%) 今天的 jhjasd 语言编程
2. (93%) 绝望的卡戴珊电视剧
两个可疑的词：
1. (50%) 今天编程 kasdhjk jhsaer
2. (95%) Stackexchange 实现 Kasdashian 过滤器
三个可疑词：
1. (25%) 编程 sdajf jkkdsf kuuerc
2. (93%) Stackexchange 咬牙切齿的卡戴珊推特甲板

在我看来，很明显哪些词组是有意义的，除了 2.1 之外，哪些词组与简单平均值一致——这又是你的决定。

有趣的是，四个词组的截止点可能与三个词组不同，因此我建议您的实现为每个组设置不同的配置设置。具有不同截止值的结果是，从 2->3 到 3->4 的量子跃迁不符合平滑、连续概率的概念。

为这些组实现不同的截止值直接满足您的直觉“现在，我只是有一种“直觉”感觉我的 xxx yyy zzz 示例确实应该高于 66.66%，但我不确定如何将其表达为公式。” .

五个字

你明白了 - 我不打算在这里再列举了。然而，当你读到五个单词时，它开始获得足够的结构，可以引入几个新的启发式方法：

贝叶斯概率/统计的使用（鉴于前两个词是一个词，第三个词是一个词的概率是多少？）
使用 NLTK 解析组并查看它是否具有语法意义

问题案例

英语有许多非常短的单词，这可能会导致问题。例如：

胡言乱语：r xu r
这是英文吗？我是一个

您可能需要编写代码来专门测试 1 和 2 个字母的单词。

TL;DR 总结

可以测试非字典单词的“英语”（或法语或西班牙语等）如何使用字母和三元组频率。挑选类似英语的单词并给予高分是区分英语组的关键
最多四个词，简单平均具有很大的辨别力，但您可能希望为 2 个词、3 个词和 4 个词设置不同的截止值。
五个字及以上你大概可以开始使用贝叶斯统计
较长的词组如果应该是句子或句子片段，可以使用自然语言工具（例如 NLTK）进行测试。
这是一个启发式过程，最终会出现混淆值（例如“我是一个”）。因此，如果编写一个完美的统计分析例程可能会被大量异常所混淆，那么与简单的平均值相比，它可能不是特别有用。

score 5 · Accepted Answer

也许您可以使用贝叶斯公式。

您已经对每个单词是真实的概率进行了数字猜测。

下一步是对整个列表是好、坏或混合的概率进行有根据的猜测（即将“最有可能”、“可能”和“不太可能”转换为数字。）

score 3 · Accepted Answer

我将给出一个贝叶斯层次模型解决方案。它有一些必须手动设置的参数，但在这些参数方面它非常稳健，如下面的模拟所示。它不仅可以处理单词列表的评分系统，还可以处理输入单词的用户的可能分类。处理可能有点技术性，但最终我们将有一个例程来计算分数作为 3 个数字的函数：列表中的单词数，数据库中完全匹配的单词数，以及部分匹配的人数（如yyyy）。该例程是在 R 中实现的，但如果您从未使用过它，只需下载解释器，将代码复制并粘贴到它的控制台中，您就会看到此处显示的结果。

顺便说一句，英语不是我的第一语言，所以请耐心等待... :-)

一、型号规格：

有 3 类用户，分别命名为 I、II、III。我们假设每个单词列表都是由单个用户生成的，并且该用户是从一组用户中随机抽取的。我们说这个宇宙是 70% 的 I 类、25% 的 II 类和 5% 的 III 类。当然，这些数字是可以更改的。我们到目前为止

概率[用户=我] = 70%

概率[用户=II] = 25%

概率[用户=III] = 5%

给定用户，我们假设条件独立，即用户不会查看之前的单词来决定他是否会输入有效或无效的单词。

用户I倾向于只给出有效词，用户II只给出无效词，用户III是混合的。所以我们设置

概率[字=确定 | 用户=我] = 99%

概率[字=确定 | 用户=II] = 0.001%

概率[字=确定 | 用户=III] = 50%

给定用户的类别，单词无效的概率是互补的。请注意，我们给出了一个非常小但非零的 II 类用户输入有效单词的概率，因为即使是打字机前的猴子也会最终输入一个有效单词。

模型规范的最后一步是关于数据库。我们假设，对于每个单词，查询可能有 3 个结果：完全匹配、部分匹配（如yyyy）或不匹配。在概率方面，我们假设

概率[匹配 | 有效] = 98%（并非所有有效词都会被找到）

概率[部分 | 有效] = 0.2%（罕见事件）

概率[匹配 | INvalid] = 0（数据库可能不完整，但没有无效词）

概率[部分 | 无效] = 0.1%（罕见事件）

不必设置找不到单词的概率，因为它们是互补的。就是这样，我们的模型设置好了。

2.符号和目的

我们有一个离散随机变量 U，取 {1, 2, 3} 中的值和两个离散随机向量 W 和 F，每个向量的大小为 n（= 单词数），其中 W_i 如果单词有效则为 1，如果单词有效，则 W_i 为 2如果单词无效，如果在数据库中找到该单词，则 F_i 为 1，如果部分匹配，则为 2，如果未找到，则为 3。

只有向量 F 是可观察的，其他的都是潜在的。使用贝叶斯定理和我们在模型规范中设置的分布，我们可以计算

(a) 概率[用户=我 | F]，

即，给定观察到的匹配，用户属于 I 类的后验概率；和

(b) Prob[W=所有有效| F]，

即，给定观察到的匹配，所有单词都是有效的后验概率。

根据您的目标，您可以使用一种或另一种作为评分解决方案。例如，如果您有兴趣区分真实用户和计算机程序，则可以使用 (a)。如果您只关心单词列表是否有效，则应使用 (b)。

我将尝试在下一节中简要解释该理论，但这是贝叶斯层次模型中的常用设置。参考文献是 Gelman (2004)，“贝叶斯数据分析”。

如果需要，您可以使用代码跳转到第 4 节。

3. 数学

在这种情况下，我将像往常一样使用轻微的符号滥用，写作

p(x|y) 用于 Prob[X=x|Y=y] 和 p(x,y) 用于 Prob[X=x,Y=y]。

目标 (a) 是计算 p(u|f)，因为 u=1。使用贝叶斯定理：

p(u|f) = p(u,f)/p(f) = p(f|u)p(u)/p(f)。

p(u) 是给定的。p(f|u) 来自：

p(f|u) = \prod_{i=1}^{n} \sum_{w_i=1}^{2} (p(f_i|w_i)p(w_i|u))

p(f|u) = \prod_{i=1}^{n} p(f_i|u)

= p(f_i=1|u)^(m) p(f_i=2|u)^(p) p(f_i=3)^(nmp)

其中 m = 匹配数， p = 部分匹配数。

p(f) 计算如下：

\sum_{u=1}^{3} p(f|u)p(u)

所有这些都可以直接计算出来。

目标 (b) 由下式给出

p(w|f) = p(f|w)*p(w)/p(f)

在哪里

p(f|w) = \prod_{i=1}^{n} p(f_i|w_i)

p(f_i|w_i) 在模型规范中给出。

p(f) 是上面计算的，所以我们只需要

p(w) = \sum_{u=1}^{3} p(w|u)p(u)

在哪里

p(w|u) = \prod_{i=1}^{n} p(w_i|u)

所以一切都准备好实施了。

4. 守则

代码编写为 R 脚本，常量在开头设置，根据上面讨论的内容，输出由函数给出

(a) p.u_f(u, n, m, p)

和

(b) p.wOK_f(n, m, p)

计算选项（a）和（b）的概率，给定输入：

u = 所需的用户类别（设置为 u=1）
n = 词数
m = 匹配
数 p = 部分匹配数

代码本身：

### Constants:

# User:

# Prob[U=1], Prob[U=2], Prob[U=3]

Prob_user = c(0.70, 0.25, 0.05)

# Words:

# Prob[Wi=OK|U=1,2,3]

Prob_OK = c(0.99, 0.001, 0.5)

Prob_NotOK = 1 - Prob_OK

# Database:

# Prob[Fi=match|Wi=OK], Prob[Fi=match|Wi=NotOK]:

Prob_match = c(0.98, 0)

# Prob[Fi=partial|Wi=OK], Prob[Fi=partial|Wi=NotOK]:

Prob_partial = c(0.002, 0.001)

# Prob[Fi=NOmatch|Wi=OK], Prob[Fi=NOmatch|Wi=NotOK]:

Prob_NOmatch = 1 - Prob_match - Prob_partial


###### First Goal: Probability of being a user type I, given the numbers of matchings (m) and partial matchings (p).


# Prob[Fi=fi|U=u]
#
p.fi_u <- function(fi, u)
{
    unname(rbind(Prob_match, Prob_partial, Prob_NOmatch) %*% rbind(Prob_OK, Prob_NotOK))[fi,u]
}

# Prob[F=f|U=u]
#
p.f_u <- function(n, m, p, u)
{
    exp( log(p.fi_u(1, u))*m + log(p.fi_u(2, u))*p + log(p.fi_u(3, u))*(n-m-p) )
}

# Prob[F=f]
#
p.f <- function(n, m, p)
{
    p.f_u(n, m, p, 1)*Prob_user[1] + p.f_u(n, m, p, 2)*Prob_user[2] + p.f_u(n, m, p, 3)*Prob_user[3]
}

# Prob[U=u|F=f]
#
p.u_f <- function(u, n, m, p)
{
    p.f_u(n, m, p, u) * Prob_user[u] / p.f(n, m, p)
}

# Probability user type I for n=1,...,5:

for(n in 1:5) for(m in 0:n) for(p in 0:(n-m))
{
    cat("n =", n, "| m =", m, "| p =", p, "| Prob type I =", p.u_f(1, n, m, p), "\n")
}

##################################################################################################

# Second Goal: Probability all words OK given matchings/partial matchings.

p.f_wOK <- function(n, m, p)
{
    exp( log(Prob_match[1])*m + log(Prob_partial[1])*p + log(Prob_NOmatch[1])*(n-m-p) )
}

p.wOK <- function(n)
{
    sum(exp( log(Prob_OK)*n + log(Prob_user) ))
}

p.wOK_f <- function(n, m, p)
{
    p.f_wOK(n, m, p)*p.wOK(n)/p.f(n, m, p)
}

# Probability all words ok for n=1,...,5:

for(n in 1:5) for(m in 0:n) for(p in 0:(n-m))
{
    cat("n =", n, "| m =", m, "| p =", p, "| Prob all OK =", p.wOK_f(n, m, p), "\n")
}

5. 结果

这是 n=1,...,5 以及 m 和 p 的所有可能性的结果。例如，如果您有 3 个单词、一个匹配、一个部分匹配和一个未找到，您可以 66.5% 确定它是 I 类用户。在相同的情况下，您可以将 42.8% 的分数归因于所有单词都是有效的。

请注意，选项 (a) 不会对所有匹配的情况给出 100% 的分数，但选项 (b) 会。这是意料之中的，因为我们假设数据库没有无效词，因此如果它们都被找到，那么它们都是有效的。OTOH，II 类或 III 类用户输入所有有效单词的可能性很小，但随着 n 的增加，这种可能性会迅速降低。

（一个）

n = 1 | m = 0 | p = 0 | Prob type I = 0.06612505 
n = 1 | m = 0 | p = 1 | Prob type I = 0.8107086 
n = 1 | m = 1 | p = 0 | Prob type I = 0.9648451 
n = 2 | m = 0 | p = 0 | Prob type I = 0.002062543 
n = 2 | m = 0 | p = 1 | Prob type I = 0.1186027 
n = 2 | m = 0 | p = 2 | Prob type I = 0.884213 
n = 2 | m = 1 | p = 0 | Prob type I = 0.597882 
n = 2 | m = 1 | p = 1 | Prob type I = 0.9733557 
n = 2 | m = 2 | p = 0 | Prob type I = 0.982106 
n = 3 | m = 0 | p = 0 | Prob type I = 5.901733e-05 
n = 3 | m = 0 | p = 1 | Prob type I = 0.003994149 
n = 3 | m = 0 | p = 2 | Prob type I = 0.200601 
n = 3 | m = 0 | p = 3 | Prob type I = 0.9293284 
n = 3 | m = 1 | p = 0 | Prob type I = 0.07393334 
n = 3 | m = 1 | p = 1 | Prob type I = 0.665019 
n = 3 | m = 1 | p = 2 | Prob type I = 0.9798274 
n = 3 | m = 2 | p = 0 | Prob type I = 0.7500993 
n = 3 | m = 2 | p = 1 | Prob type I = 0.9864524 
n = 3 | m = 3 | p = 0 | Prob type I = 0.990882 
n = 4 | m = 0 | p = 0 | Prob type I = 1.66568e-06 
n = 4 | m = 0 | p = 1 | Prob type I = 0.0001158324 
n = 4 | m = 0 | p = 2 | Prob type I = 0.007636577 
n = 4 | m = 0 | p = 3 | Prob type I = 0.3134207 
n = 4 | m = 0 | p = 4 | Prob type I = 0.9560934 
n = 4 | m = 1 | p = 0 | Prob type I = 0.004198015 
n = 4 | m = 1 | p = 1 | Prob type I = 0.09685249 
n = 4 | m = 1 | p = 2 | Prob type I = 0.7256616 
n = 4 | m = 1 | p = 3 | Prob type I = 0.9847408 
n = 4 | m = 2 | p = 0 | Prob type I = 0.1410053 
n = 4 | m = 2 | p = 1 | Prob type I = 0.7992839 
n = 4 | m = 2 | p = 2 | Prob type I = 0.9897541 
n = 4 | m = 3 | p = 0 | Prob type I = 0.855978 
n = 4 | m = 3 | p = 1 | Prob type I = 0.9931117 
n = 4 | m = 4 | p = 0 | Prob type I = 0.9953741 
n = 5 | m = 0 | p = 0 | Prob type I = 4.671933e-08 
n = 5 | m = 0 | p = 1 | Prob type I = 3.289577e-06 
n = 5 | m = 0 | p = 2 | Prob type I = 0.0002259559 
n = 5 | m = 0 | p = 3 | Prob type I = 0.01433312 
n = 5 | m = 0 | p = 4 | Prob type I = 0.4459982 
n = 5 | m = 0 | p = 5 | Prob type I = 0.9719289 
n = 5 | m = 1 | p = 0 | Prob type I = 0.0002158996 
n = 5 | m = 1 | p = 1 | Prob type I = 0.005694145 
n = 5 | m = 1 | p = 2 | Prob type I = 0.1254661 
n = 5 | m = 1 | p = 3 | Prob type I = 0.7787294 
n = 5 | m = 1 | p = 4 | Prob type I = 0.988466 
n = 5 | m = 2 | p = 0 | Prob type I = 0.00889696 
n = 5 | m = 2 | p = 1 | Prob type I = 0.1788336 
n = 5 | m = 2 | p = 2 | Prob type I = 0.8408416 
n = 5 | m = 2 | p = 3 | Prob type I = 0.9922575 
n = 5 | m = 3 | p = 0 | Prob type I = 0.2453087 
n = 5 | m = 3 | p = 1 | Prob type I = 0.8874493 
n = 5 | m = 3 | p = 2 | Prob type I = 0.994799 
n = 5 | m = 4 | p = 0 | Prob type I = 0.9216786 
n = 5 | m = 4 | p = 1 | Prob type I = 0.9965092 
n = 5 | m = 5 | p = 0 | Prob type I = 0.9976583

(二)

n = 1 | m = 0 | p = 0 | Prob all OK = 0.04391523 
n = 1 | m = 0 | p = 1 | Prob all OK = 0.836025 
n = 1 | m = 1 | p = 0 | Prob all OK = 1 
n = 2 | m = 0 | p = 0 | Prob all OK = 0.0008622994 
n = 2 | m = 0 | p = 1 | Prob all OK = 0.07699368 
n = 2 | m = 0 | p = 2 | Prob all OK = 0.8912977 
n = 2 | m = 1 | p = 0 | Prob all OK = 0.3900892 
n = 2 | m = 1 | p = 1 | Prob all OK = 0.9861099 
n = 2 | m = 2 | p = 0 | Prob all OK = 1 
n = 3 | m = 0 | p = 0 | Prob all OK = 1.567032e-05 
n = 3 | m = 0 | p = 1 | Prob all OK = 0.001646751 
n = 3 | m = 0 | p = 2 | Prob all OK = 0.1284228 
n = 3 | m = 0 | p = 3 | Prob all OK = 0.923812 
n = 3 | m = 1 | p = 0 | Prob all OK = 0.03063598 
n = 3 | m = 1 | p = 1 | Prob all OK = 0.4278888 
n = 3 | m = 1 | p = 2 | Prob all OK = 0.9789305 
n = 3 | m = 2 | p = 0 | Prob all OK = 0.485069 
n = 3 | m = 2 | p = 1 | Prob all OK = 0.990527 
n = 3 | m = 3 | p = 0 | Prob all OK = 1 
n = 4 | m = 0 | p = 0 | Prob all OK = 2.821188e-07 
n = 4 | m = 0 | p = 1 | Prob all OK = 3.046322e-05 
n = 4 | m = 0 | p = 2 | Prob all OK = 0.003118531 
n = 4 | m = 0 | p = 3 | Prob all OK = 0.1987396 
n = 4 | m = 0 | p = 4 | Prob all OK = 0.9413746 
n = 4 | m = 1 | p = 0 | Prob all OK = 0.001109629 
n = 4 | m = 1 | p = 1 | Prob all OK = 0.03975118 
n = 4 | m = 1 | p = 2 | Prob all OK = 0.4624648 
n = 4 | m = 1 | p = 3 | Prob all OK = 0.9744778 
n = 4 | m = 2 | p = 0 | Prob all OK = 0.05816511 
n = 4 | m = 2 | p = 1 | Prob all OK = 0.5119571 
n = 4 | m = 2 | p = 2 | Prob all OK = 0.9843855 
n = 4 | m = 3 | p = 0 | Prob all OK = 0.5510398 
n = 4 | m = 3 | p = 1 | Prob all OK = 0.9927134 
n = 4 | m = 4 | p = 0 | Prob all OK = 1 
n = 5 | m = 0 | p = 0 | Prob all OK = 5.05881e-09 
n = 5 | m = 0 | p = 1 | Prob all OK = 5.530918e-07 
n = 5 | m = 0 | p = 2 | Prob all OK = 5.899106e-05 
n = 5 | m = 0 | p = 3 | Prob all OK = 0.005810434 
n = 5 | m = 0 | p = 4 | Prob all OK = 0.2807414 
n = 5 | m = 0 | p = 5 | Prob all OK = 0.9499773 
n = 5 | m = 1 | p = 0 | Prob all OK = 3.648353e-05 
n = 5 | m = 1 | p = 1 | Prob all OK = 0.001494098 
n = 5 | m = 1 | p = 2 | Prob all OK = 0.051119 
n = 5 | m = 1 | p = 3 | Prob all OK = 0.4926606 
n = 5 | m = 1 | p = 4 | Prob all OK = 0.9710204 
n = 5 | m = 2 | p = 0 | Prob all OK = 0.002346281 
n = 5 | m = 2 | p = 1 | Prob all OK = 0.07323064 
n = 5 | m = 2 | p = 2 | Prob all OK = 0.5346423 
n = 5 | m = 2 | p = 3 | Prob all OK = 0.9796679 
n = 5 | m = 3 | p = 0 | Prob all OK = 0.1009589 
n = 5 | m = 3 | p = 1 | Prob all OK = 0.5671273 
n = 5 | m = 3 | p = 2 | Prob all OK = 0.9871377 
n = 5 | m = 4 | p = 0 | Prob all OK = 0.5919764 
n = 5 | m = 4 | p = 1 | Prob all OK = 0.9938288 
n = 5 | m = 5 | p = 0 | Prob all OK = 1

score 2 · Accepted Answer

由于单词的顺序在您的描述中并不重要，因此自变量是有效单词的比例。如果分数是完美的 1，即发现所有单词都与 DB 完美匹配，那么您完全可以肯定得到所有有效的结果。如果它为零，即数据库中的所有单词都是完全未命中的，那么您完全肯定会得到完全无效的结果。如果你有 0.5，那么这肯定是不太可能的混合结果，因为其他两个都不可能。

你说混合结果不太可能，而两个极端情况更是如此。你追求的是完全有效的结果的可能性。

让有效词的分数（匹配的“确定性”之和/词的数量）为 f，因此所有有效结果的期望可能性为 L(f)。通过到目前为止的讨论，我们知道 L(1)=1 和 L(f)=0 对于 0<=f<=1/2 。

为了尊重您的信息，即混合结果不太可能低于全有效（和全无效）结果，L 的形状必须单调且快速地从 1/2 上升到 1，并在 f=1 时达到 1。

由于这是启发式的，我们可以选择任何具有此字符的合理函数。如果我们很聪明，它将有一个参数来控制台阶的陡度，也许还有一个参数来控制它的位置。这让我们可以调整中间情况下“不太可能”的含义。

对于 1/2 <= f <= 1，这样的函数之一是：

L(f) = 5 + f * (-24 + (36 - 16 * f) * f) + (-4 + f * (16 + f * (-20 + 8 * f))) * s

0 <= f < 1/2 时为零。虽然看起来很毛茸茸，但它是与 (1/2,0) 和 (1,1) 相交的最简单的多项式，在 f=1 处斜率为 0，在 f=0 处斜率为 s。

您可以设置 0 <= s <= 3 来更改阶梯形状。这是 s=3 的镜头，这可能是您想要的：函数图的屏幕截图

如果您设置 s > 3，它会在稳定下来之前高于 1，这不是我们想要的。

当然还有无限多的其他可能性。如果这个不起作用，请发表评论，我们会寻找另一个。

score 2 · Accepted Answer

如果“平均”由于数据库缺少单词而无法解决，我会说：扩展数据库:)

另一个想法可能是，“权衡”结果，获得调整后的平均值，例如：

100% = 1.00x weight
90%  = 0.95x weight
80%  = 0.90x weight
...
0%   = 0.50x weight

因此，对于您的示例，您将：

(100*1 + 90*0.95 + 0*0.5) / (100*1 + 100*0.95 + 100*0.5) = 0.75714285714
 => 75.7%
regular average would be 63.3%

score 1 · Accepted Answer

当然，平均是垃圾。如果单个单词的概率是准确的，那么所有单词都是正确的概率只是乘积，而不是平均值。如果您对个人概率的不确定性进行了估计，则可以计算出他们的乘积在所有个人概率上都被边缘化了。

algorithm - 评分系统建议 - 加权机制？

6 回答 6

Related

Reference